网络作弊检测是搜索引擎的重要挑战之一,该文提出基于遗传规划的集成学习方法 (简记为GPENL)来检测网络作弊。该方法首先通过欠抽样技术从原训练集中抽样得到t个不同的训练集;然后使用c个不同的分类算法对t个训练集进行训练得到t*c个基分类器;最后利用遗传规划得到t*c个基分类器的集成方式。新方法不仅将欠抽样技术和集成学习融合起来提高非平衡数据集的分类性能,还能方便地集成不同类型的基分类器。在WEBSPAM-UK2006数据集上所做的实验表明无论是同态集成还是异态集成,GPENL均能提高分类的性能,且异态集成比同态集成更加有效;GPENL比AdaBoost、Bagging、RandomForest、多数投票集成、EDKC算法和基于Prediction Spamicity的方法取得更高的F-度量值。
Abstract
Web spam detection is a challenging issue for web search engines. This paper proposes a Genetic Programming-based ensemble learning approach (GPENL) to detect web spam. First, the method gets t different training sets by the under-sampling from the original training set. Then, c different classification algorithms are used on t training sets to get t*c base classifiers. Finally, an integrated approach of t*c base classifiers is obtained by Genetic Programming. The new method can not only merge the under-sampling technology and ensemble learning to improve the classification performance on imbalanced datasets, but also conveniently integrate different types of base classifiers. The experiments on WEBSPAM-UK2006 show that this method improve the classification performance whether the base classifiers belong to the same type or not, and in most cases the heterogeneous classifier ensembles work better than the homogeneous ones; and GPENL can get higher F-measure than those done by AdaBoost, Bagging, RandomForest, Vote, EDKC algorithm and the method based on Prediction Spamicity.
Key wordsweb spam; ensemble learning; genetic programming; classification on the imbalanced dataset
关键词
网络作弊 /
集成学习 /
遗传规划 /
非平衡数据集分类
{{custom_keyword}} /
Key words
web spam /
ensemble learning /
genetic programming /
classification on the imbalanced dataset
{{custom_keyword}} /
{{custom_sec.title}}
{{custom_sec.title}}
{{custom_sec.content}}
参考文献
[1] Becchetti L., Castillo I C., Donato I D., et al. Using Rank Propagation and Probabilistic Counting for Link Based Spam Detection[C]//Proceedings of WebKDD 2006, Vol 4811: 127-146.
[2] Ntoulas A., Najork M., Manasse M., et al. Detecting spam web pages through content analysis [C]//Proceedings of the 15th International Conference on World Wide Web, WWW 2006: 83-92.
[3] Gyngyi Z., Garcia-Molina H., Pedersen J.. Combating web spam with trustrank [C]//Proceedings of the 30th International Conference on Very Large Data Bases, 2004, 30: 576-587.
[4] L. Becchetti, C. Castillo, D. Donato, et al. Link-based characterization and detection of Web Spam [C]//Proceedings of AIRWeb, 2006.
[5] Castillo C., Donato D., Murdock V., et al. Know your neighbors: Web spam detection using the Web topology [C]//Proceedings of SIGIR2007: 423-430.
[6] Na Dai, Brian D. Davison, Xiaoguang Qi. Looking into the Past to Better Classify Web Spam [C]//Proceedings of AIRWeb 09, Madrid, Spain (April 21, 2009).
[7] Yiqun Liu, Rongwei Cen, Min Zhang, et al. Identifying Web Spam with User Behavior Analysis [C]//Proceedings of AIRWeb 2008, Beijing, China, April 22.
[8] Xu-Ying Liu, Jian-xin Wu, Zhi-Hua Zhou. Exploratory under-sampling for class-imbalance learning [J]. IEEE Systems, Man, and Cybernetics Society, 2009, 39 (2): 539-550.
[9] Koza J.R.. Genetic Programming: On the Programming of Computers by Means of Natural Selection [M]. MIT Press, Cambridge, 1992.
[10] 孙丽娜. 集成异种分类器分类稀有类[D]. 郑州大学硕士学位论文, 2007: 31-33.
[11] Guang-Gang Geng, Chun-Heng Wang, Qiu-Dan Li, et al. Boosting the Performance of Web Spam Detection with Ensemble Under-Sampling Classification [C]//Proceedings of FSKD(4) 2007: 583-587.
[12] Zhi-Hua Zhou, Jianxin Wu, Wei Tang. Ensembling Neural Networks: Many Could Be Better Than All [J]. Artificial Intelligence, 2002, 137: 239-263.
[13] Jung-Yi Lin, Hao-Ren Ke,Been-Chian Chien, et al. Designing a classifier by a layered multi-population genetic programming approach [J]. Pattern Recognition, 2007, 40: 2211-2225.
{{custom_fnGroup.title_cn}}
脚注
{{custom_fn.content}}
基金
国家自然科学基金资助项目(60970047,61103151,61173068);山东省自然科学基金资助项目(Y2008G19);山东省高等学校优秀青年教师国内访问学者资助项目
{{custom_fund}}
PDF(1588 KB)
