基于内容的文本分类算法综述

    律佳

    【摘要】随着信息技术的发展，人们已经从信息缺乏的时代过渡到信息极为丰富的数字化时代，可以获得越来越多的数字化信息，而这些信息大都是半结构化或非结构化数据，为了从中快速有效地获得自己需要的信息，我们需要研究基于内容的文本信息分类技术。

    【关键词】k-元最近邻居算法；贝叶斯算法；决策树算法；支持向量机算法

    1.引言

    目前很多分类算法被研究者从不同角度提出，判断不同分类算法的好坏可以由准确率、速度、健壮性、可伸缩性、可解释性等几个标准来衡量。经典的分类算法在不同的领域取得成功，比如贝叶斯算法、决策树分类算法、KNN算法和支持向量机算法等。

    2.文本分类算法

    2.1贝叶斯（Na?ve Bayesian）算法

    贝叶斯是一种概率方法，设每个数据样本用一个 维特征向量来描述n个属性的值，即：，假定有m个类，分别用表示。给定一个未知的数据样本x（即没有类标号），若朴素贝叶斯分类法将未知的样本x分配给类，则一定是

    根据贝叶斯定理，由于对于所有类为常数，最大化后验概率可转化为最大化先验概率。如果训练数据集有许多属性和元组，计算的开销可能非常大，为此，通常假设各属性的取值互相独立，这样先验概式（2）可以从训练数据集求得。

    根据此方法，对一个未知类别的样本x，可以先分别计算出X属于每一个类别的概率，然后选择其中概率最大的类别作为其类别。

    贝叶斯定理给出了最小化误差的最优解决方法，可用于分类和预测。其特点是：

    ①贝叶斯分类并不把一个对象绝对地指派给某一类，而是通过计算得出属于某一类的概率，具有最大概率的类便是该对象所属的类。

    ②一般情况下在贝叶斯分类中所有的属性都参与分类。

    ③贝叶斯分类对象的属性可以是离散的、连续的，也可以是混合的。

    2.2决策树（Decision Tree）算法

    在决策树的内部结点进行属性值的比较，并根据不同的属性值从该结点向下分支，叶结点是要学习划分的类。从根到叶结点的一条路径就对应着一条合取规则，整个决策树就对应着一组析取表达式规则。

    2.2.1 ID3算法

    70年代末。由J Ross Quinlan提出了ID3算法，ID3的具体方法是：检测所有的属性，选择信息增益最大的属性产生决策树结点，由该属性的不同取值建立分支，再对各分支的子集递归调用该方法建立决策树结点的分支，直到所有子集仅包含同一类别的数据为止。最后得到一棵决策树，它可以用来对新的样本进行分类。

    ID3算法的特点：算法的理论清晰，方法简单，学习能力较强。但是ID3算法只对比较小的数据集有效，且对噪声比较敏感，当训练数据集加大时，决策树可能会随之改变。

    2.2.2 C4.5算法

    C4.5算法继承了ID3算法的优点，并在以下几方面对ID3算法进行了改进：

    ①用信息增益率来选择属性，克服了用信息增益选择属性时偏向选择取值多的属性的不足。

    ②在树构造过程中进行剪枝。

    ③能够完成对连续属性的离散化处理。

    ④能够对不完整数据进行处理。

    C4.5算法的特点：产生的分类规则易于理解，准确率较高。但在构造树的过程中，C4.5算法需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效；C4.5算法只适合于能够驻留于内存的数据集，当训练集大得无法在内存容纳时程序无法运行。

    2.3 k-元最近邻居（K-Nearest Neighbor，KNN）算法

    k-元最近邻居算法中，所选择的邻居都是已经正确分类的对象。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。通过找出一个样本的k个最近邻居，将这些邻居的属性的平均值赋给该样本，就可以得到该样本的属性。KNN算法具有以下特点：

    ①KNN算方法不依赖对基础数据的严格规定，并能适应任何情况。②KNN算法由于判定边界的任何特定子部分都依赖于少数输入点和它们的特定位置，因而是摆动和不稳定的，即它具有高方差和低偏倚。③当样本不平衡时，如一个类的样本容量很大，而其他类样本容量很小时，有可能导致当输入一个新样本时，该样本的K个邻居中大容量类的样本占多数。

    2.4支持向量机（SVM-Support Vector Machine）算法

    支持向量机算法是Vapnik等人根据统计学习理论提出的一种新的机器学习方法，其思想是以机构风险最小化原则为理论基础，通过适当选择函数子集及该子集中的判定函数使学习机的实际风险达到最小，保证了通过有限训练样本得到的小误差分类器对独立测试集的测试误差仍然小。从算法本身及凸优化知识角度，可以得出该算法的下列特点：

    ①分类器有支持向量唯一决定。②多数情况下，支持向量的数目远远小于训练集中的总样本数量，从某种意义上说，压缩了数据，保留了类别信息。③算法复杂度主要由训练集样本数量决定，而与训练本身的维数关系不大。

    3.分类算法的评价标准

    分类算法可以根据下列标准进行评价和比较。

    ①预测的准确率。它包括模型正确地预测新的或先前未见过的样本的类标号的能力。②计算速度。分类的时间包括构造模型和使用模型进行分类的时间。③强壮性。指正确预测含有噪声和空缺值的数据集的能力。④可伸缩性。指对海量数据集有效地构造模型的能力。⑤模型描述的简洁性和可解释性。模型描述愈简洁、愈容易理解，则愈受欢迎。

    4.结束语

    基于内容的文本分类技术的出现逐渐受到重视，是源于网络用户对信息获取在数量得到满足后的更高的一种要求。本文对目前比较优秀的各种分类算法进行了介绍、分析。综合提出了评价分类算法好坏的5条标准。实际上，上述这些算法的准确度差别不大，在当今数据量急剧增长的时代，算法的执行速度、可伸缩性以及输出结果的可理解性等特性更为重要。此外，由于分类的效果一般和数据的特点有关，目前还不存在能适合各种不同数据的优良分类方法，一种各方面特性都很好的分类算法仍有待进一步研究。

    参考文献

    [1]明均仁，张帆.网络文本信息过滤的意义及其模型初探.图书与情报[J].2007，37-4

    [2]孙建军，成颖.信息检索技术[M].科学出版社，2004：81～683