基于C4.5算法的BBS反垃圾内容分析.docVIP

基于C4.5算法的BBS反垃圾内容分析 //.paper.edu 摘 要：随着互联网的高速发展，不同形式的网站也大量涌现。同时，在经济利益的驱使下， 垃圾网页也日益增多，如何提高用户检索信息的质量就显得尤为重要。文通过对 BBS 论坛 结构分析，针对论坛总结出一种基于 C4.5 算法的回帖判别方法，使其不仅可以用于判断回 帖内容是否贡献于主贴，还可以排除回帖垃圾(Spam)内容。这样可以提高用户检索体验，减 少无用信息的干扰。 关键词：BBS网页结构，C4.5算法，垃圾网页，Spam内容。 1．引言 随着互联网的高速发展，网页数量呈几何级数增长，各种网站也如雨后春笋般涌现出来， 同时也出现了很多具有专业知识的论坛，无论是中文社区还是英文社区，传统形式的网站已 经不再是人们获取网络知识的唯一渠道，很多已经转移到这些专业知识的论坛。比较有代表 性讨论编程相关的CSDN，笔记本相关知识的Thinkpadcn ，讨论PDA和手机相关知识的 Xpda[1]，大型综合性社区baidu知道[2]，sina爱问[3] 等等。同样对于用户来说，是获取知识的 很好途径，通过流量访问统计，这些论坛或者大型社区的日在线人数在万人左右。所以如何 利用好这些社区，如何获得相关的知识，就显得尤为重要，同时可以看出Google由于自身算 法的原因，在返回这些论坛内容结果时，并不尽如人意。所以开发相应的论坛自身检索系统 就显得尤为重要，同时可以看出目前存在的这些论坛检系统，相对来说比较简单，无论是对 于用户检索词的处理，还是对待返回结果的处理上，这样就会导致论坛检索效率底下，同时 论坛这种需要相当人力管理的组织结构，存在着人力管理成本和可能存在的“公正性”问题， 也会影响用户的检索体验。 所以本文提出了基于论坛这种特殊的组织结构，基于对内容的分析，对网页进行解析， 提取重要性属性，采用改进决策树C4.5算法，对相应的回帖内容进行相关计算，给出相应重 要度得分，提供一种重要度的衡量指标，尽量减少无用信息和垃圾内容广告内容，以提高用 户检索体验。 2．决策树C4.5算法介绍 机器学习中，决策树是一个预测模型；他代表的是对象属性与对象值之间的一种映射关 系。树中每个节点表示某个对象，而每个分叉路径则代表的某个可能的属性值，而每个叶结 点则对应从根节点到该叶节点所经历的路径所表示的对象的值。决策树仅有单一输出，若欲 有复数输出，可以建立独立的决策树以处理不同输出。 2.1 C4.5算法介绍 C4.5[4]算法是构造决策树分类规则的一种算法，它是ID3[5]算法的扩展。ID3算法只能处 理离散型的描述性属性，而C4.5 算法还能够处理描述属性值为连续型的情况。选取节点的 标准是最大信息增益率，具体的算法步骤如下： Step1.对数据源进行数据预处理，将连续型的属性变量进行离散化处理形成决策树的训 -1- //.paper.edu 练集(如果没有连续取值的属性则忽略)； (1)根据原始数据，找到该连续型属性的最小取值 ，最大取值0a 1na + ； (2)在区间[a,b]内插入 n个数值等分为 n+1个小区间； (3)分别以 ，i=1,2,…n为分段点，将区间ia 0 1[ , ]na a + 划分为两个子区间： 0[ , ]ia a ， 对应该连续型的属性变量两类取值，有 n种划分方式； 1 1[ ,i na a+ + ] Step2.计算每个属性的信息增益和信息增益率； (1)计算属性 A的信息增益 Gain(A) 信息增益 Gain(A)的计算和 ID3算法中的完全一致； (2)计算属性 A的信息增益率 Gain-Ratio(A) ( )( ) ( ) Gain AGain Ratio A I A ?? = (1) 对于取值连续的属性而言，分别计算以 (i=1,2,…,n)为分割点，对应分类的信息增益率， 选择最大信息增益率对应的 作为该属性分类的分割点。 ia ia 选择信息增益率最大的属性，作为当前的属性节点，得到决策树的根节点。 Step3.根节点属性每一个可能的取值对应一个子集，对样本子集递归地执行以上 Step2 过程，直到划分的每个子集中的观测数据在分类属性上取值都相同，生成决策树。 Step4.根据构造的决策树提取分类规则，对新的数据集进行分类。 类似算法的主要思想都是，逐步找出能够为各个层次的分类提供最大信息量的变量，由 此可以确定决策树从根到枝，再从枝到叶的结构。决策树生成的过程也就是对训练数据 集进行分类的过程。 2.2 C4.5算法相对于 ID3算法的优点 C4.5算法继承了 ID3算法的优点，并在