论文部分内容阅读
【摘 要】根据用户定义的某一主题，在爬虫算法中加入反作弊思想后，用爬虫算法遍历网络，收集与主题相关的页面进行智能分析，同时将文本过滤转化为文本分类，为了增强通用性，在算法中加入了松弛变量，最后在NB分类个器上验证算法的性能。试验表明，分类精度达到将近90%。
【关键词】主题爬虫；文本分类；反作弊；松弛变量
由于Web用户的信息检索需求是千变万化的，这样对于不同领域就需要建立相应的主题搜索引擎，要求的主题搜索引擎数量将非常多，而且随着人类社会知识更新速度的不断加剧，这个问题将更严重；另外，用户检索需求所属的领域有时是难以确定，造成用户无所适从。从而导致主题爬虫技术面临以下几个问题：（1）查准率不高；（2）查全率低；（3）查询主题不易精确表达，而且往往带有欺骗性，也很大程度影响了查准率和查全率。本文针对WebSpam算法，在其中加入反作弊方程，提高了主题爬虫的效率，在一定程度上满足了用户的特定检索要求。
1.基于反作弊技术的主题爬虫算法
1.1 主题爬虫简介
主题爬虫（Topical Crawler，Focused Crawler or Topic.driven crawler）[1-3]，是一个智能化的Web下载系统，它按照用户给定的主题，自动在Web上遍历，将与主题相关的页面下载下来，满足用户对特定主题的检索需求。
1.2 算法描述
首先训练一个线性分类器，分类器采用支持向量机（Support Vector Machine，SVM）来训练，由：
（1-1）
来定义，为参数，用来权衡算法的适应性和复杂性。在这里，使用表示分类样本的损耗，作为参数调整项，补充分类样本。
由于超链接可以用有向图表示，边集为E。超链接并不是随机出现的，通过分析可以发现，超链接所指向的源结点和目标结点一般是主题相似的。基于以上发现，将上面的公式1-1扩充，加入新的部分：
（1-2）
其中，为有向边的权值，上述公式的前两部分为线性SVM的描述，第三部分为超链接特性的表述，矩阵用来表述有向图的结构。公式1-2所描述的理论[4][5]已经被实现，的值可采用，表示由超链接联系的源地址和目标地址有相似的预测值。与M.Belkin[5]等人相反，本文采用的图结构是专门面向Web Spam分类的，使用有向图来进行分类时，由于带有Spam的页面会制造大量链接指向真正的页面，但相反的链接却不存在。即可用来代替公式1-2。
1.3 添加松弛变量
通过分析，上面公式中的特征向量之间的距离可能不够松弛，同时，像这样的线性分类器也是不够灵活的。根据文献[5]中的论述，可以为每个结点引入参数，公式变为：。可以看做松弛变量，用于提高分类器的适应性。最后模型可以表述为：
（1-3）
2.反作弊算法试验分析
公式1-3中三个部分分别表示结点特征①、Spam单向性②和松弛变量③。这三个部分在区分Spam页面的作用不同，因此选择不同的组合，来验证每个部分的重要性。
只选择结点特征：只选用给定的有向图特征来训练分类器，而忽略Spam单向性。在公式1-3中，进行下列赋值=0，γ=0，这样公式1-3直接就变成了标准线性分类器。
选择结点特征与Spam单向性：同时选择结点特征和Spam单向性两个部分，而忽略松弛变量这个部分，即=0。
选择松弛变量和Spam单向性：忽略结点特征这一项，查看分类器在无结点特征，仅靠松弛变量的调整和结点之间的超链接有向图特征这两项训练SVM分类器。
仅选择结点特征和松弛变量：忽略Spam单向性这一项，仅靠结点特征和松弛变量的调整，训练SVM分类器，查看结点之间的超链接Spam单向性对分类效果的影响。
同时选择3个部分：应用改进的Anti-spam算法训练分类器，通过实验对比查看这种方式的效果。
以上五种Anti-Spam的变种算法的结果如图3.1所示：从图3.1可以看出，忽略超链接Spam单向性，仅选择网站的特征项分类结果大致是一样的。基本和Web Spam相当，继续挖掘Spam的特性，对于提高分类精确度，更好的过滤Spam页面，具有重要意义。和现有的作弊算法相比，时间复杂度较高，如果分类样本比例达到90%以上，同时考虑节点特征、Spam的单向性和松弛变量，分类精度将会达到90%左右，当然只是针对Web Spam的。
3.结论
主要分析了当前主题爬虫存在的问题，提出了基于Web反作弊的Anti-Spam及其变种算法，Anti-Spam及其变种算法使用SVM来训练分类器。另外，从实验中可以看出，决定分类的关键属性是超链接有向图自身的特性，与网站本身的特性相关比较小。在今后的算法改进中，应当注重研究网站之间的超链接特性和主题漂移[6]。当然，通过样本聚类比例的分析，分类精度虽然有所提高，要更好的过滤Spam页面，需要借助于文本过滤技术。
图3.1 五种Anti-Spam的变种算法的结果
参考文献：
[1]罗刚，王振东.自己动手写网络爬虫[M].清华大学出版社，2010，4（第二版）：331-338.
[2]王亮.搜索引擎零距离[M].清华大学出版社，2009，6（第一版）：200-216.
[3]赫枫龄，左万历.利用超链接信息改进网页爬行器的搜索策略[J].吉林大学学报：信息科学版，2005，23（1）：59-62.
[4]高琪，张永平.超链接导向搜索算法中主题漂移的研究[J].计算机应用，2009，29（11）：3101-3102.
[5]Lili Yan，Yingbin Wei.Research on page rank and hyperlink-Introduced Topic search in Web Structure Mining[J].IEEE express Conference Publing，ITAP2011：1015-1018.
[6]ZHAO Yan-Yan，QIN Bing，LIU Ting.Sentiment Analysis[J].Journal of Software，Science Press，2010，8：13-14.
[7]WANG Huan，WU Gang，YANG Shu.Forestry Web Yellow Page Category System Based on Text Classification[J].Computer Systems & Applications，Science Press，Vol.21，No.1，
pp.21-24，2012.
[8]FENG Yong，LI Hua，ZHONG Jiang，YE Chun-Xiao.Text Classification Algorithm Based on Adaptive Chinese Word Segmentation and Proximal SVM[J].Computer Science，Chongqing branch Keqing Printing Company Limited，Vol.37，No.1，pp.252-254，2010.
基金项目：渭南师范学院大学生创新基金项目（项目编号：12XK050）。
【关键词】主题爬虫；文本分类；反作弊；松弛变量
由于Web用户的信息检索需求是千变万化的，这样对于不同领域就需要建立相应的主题搜索引擎，要求的主题搜索引擎数量将非常多，而且随着人类社会知识更新速度的不断加剧，这个问题将更严重；另外，用户检索需求所属的领域有时是难以确定，造成用户无所适从。从而导致主题爬虫技术面临以下几个问题：（1）查准率不高；（2）查全率低；（3）查询主题不易精确表达，而且往往带有欺骗性，也很大程度影响了查准率和查全率。本文针对WebSpam算法，在其中加入反作弊方程，提高了主题爬虫的效率，在一定程度上满足了用户的特定检索要求。
1.基于反作弊技术的主题爬虫算法
1.1 主题爬虫简介
主题爬虫（Topical Crawler，Focused Crawler or Topic.driven crawler）[1-3]，是一个智能化的Web下载系统，它按照用户给定的主题，自动在Web上遍历，将与主题相关的页面下载下来，满足用户对特定主题的检索需求。
1.2 算法描述
首先训练一个线性分类器，分类器采用支持向量机（Support Vector Machine，SVM）来训练，由：
（1-1）
来定义，为参数，用来权衡算法的适应性和复杂性。在这里，使用表示分类样本的损耗，作为参数调整项，补充分类样本。
由于超链接可以用有向图表示，边集为E。超链接并不是随机出现的，通过分析可以发现，超链接所指向的源结点和目标结点一般是主题相似的。基于以上发现，将上面的公式1-1扩充，加入新的部分：
（1-2）
其中，为有向边的权值，上述公式的前两部分为线性SVM的描述，第三部分为超链接特性的表述，矩阵用来表述有向图的结构。公式1-2所描述的理论[4][5]已经被实现，的值可采用，表示由超链接联系的源地址和目标地址有相似的预测值。与M.Belkin[5]等人相反，本文采用的图结构是专门面向Web Spam分类的，使用有向图来进行分类时，由于带有Spam的页面会制造大量链接指向真正的页面，但相反的链接却不存在。即可用来代替公式1-2。
1.3 添加松弛变量
通过分析，上面公式中的特征向量之间的距离可能不够松弛，同时，像这样的线性分类器也是不够灵活的。根据文献[5]中的论述，可以为每个结点引入参数，公式变为：。可以看做松弛变量，用于提高分类器的适应性。最后模型可以表述为：
（1-3）
2.反作弊算法试验分析
公式1-3中三个部分分别表示结点特征①、Spam单向性②和松弛变量③。这三个部分在区分Spam页面的作用不同，因此选择不同的组合，来验证每个部分的重要性。
只选择结点特征：只选用给定的有向图特征来训练分类器，而忽略Spam单向性。在公式1-3中，进行下列赋值=0，γ=0，这样公式1-3直接就变成了标准线性分类器。
选择结点特征与Spam单向性：同时选择结点特征和Spam单向性两个部分，而忽略松弛变量这个部分，即=0。
选择松弛变量和Spam单向性：忽略结点特征这一项，查看分类器在无结点特征，仅靠松弛变量的调整和结点之间的超链接有向图特征这两项训练SVM分类器。
仅选择结点特征和松弛变量：忽略Spam单向性这一项，仅靠结点特征和松弛变量的调整，训练SVM分类器，查看结点之间的超链接Spam单向性对分类效果的影响。
同时选择3个部分：应用改进的Anti-spam算法训练分类器，通过实验对比查看这种方式的效果。
以上五种Anti-Spam的变种算法的结果如图3.1所示：从图3.1可以看出，忽略超链接Spam单向性，仅选择网站的特征项分类结果大致是一样的。基本和Web Spam相当，继续挖掘Spam的特性，对于提高分类精确度，更好的过滤Spam页面，具有重要意义。和现有的作弊算法相比，时间复杂度较高，如果分类样本比例达到90%以上，同时考虑节点特征、Spam的单向性和松弛变量，分类精度将会达到90%左右，当然只是针对Web Spam的。
3.结论
主要分析了当前主题爬虫存在的问题，提出了基于Web反作弊的Anti-Spam及其变种算法，Anti-Spam及其变种算法使用SVM来训练分类器。另外，从实验中可以看出，决定分类的关键属性是超链接有向图自身的特性，与网站本身的特性相关比较小。在今后的算法改进中，应当注重研究网站之间的超链接特性和主题漂移[6]。当然，通过样本聚类比例的分析，分类精度虽然有所提高，要更好的过滤Spam页面，需要借助于文本过滤技术。
图3.1 五种Anti-Spam的变种算法的结果
参考文献：
[1]罗刚，王振东.自己动手写网络爬虫[M].清华大学出版社，2010，4（第二版）：331-338.
[2]王亮.搜索引擎零距离[M].清华大学出版社，2009，6（第一版）：200-216.
[3]赫枫龄，左万历.利用超链接信息改进网页爬行器的搜索策略[J].吉林大学学报：信息科学版，2005，23（1）：59-62.
[4]高琪，张永平.超链接导向搜索算法中主题漂移的研究[J].计算机应用，2009，29（11）：3101-3102.
[5]Lili Yan，Yingbin Wei.Research on page rank and hyperlink-Introduced Topic search in Web Structure Mining[J].IEEE express Conference Publing，ITAP2011：1015-1018.
[6]ZHAO Yan-Yan，QIN Bing，LIU Ting.Sentiment Analysis[J].Journal of Software，Science Press，2010，8：13-14.
[7]WANG Huan，WU Gang，YANG Shu.Forestry Web Yellow Page Category System Based on Text Classification[J].Computer Systems & Applications，Science Press，Vol.21，No.1，
pp.21-24，2012.
[8]FENG Yong，LI Hua，ZHONG Jiang，YE Chun-Xiao.Text Classification Algorithm Based on Adaptive Chinese Word Segmentation and Proximal SVM[J].Computer Science，Chongqing branch Keqing Printing Company Limited，Vol.37，No.1，pp.252-254，2010.
基金项目：渭南师范学院大学生创新基金项目（项目编号：12XK050）。