一种新的基于SVM_KNN的Web文本分类算法

总第246期2010年第4期

计算机与数字工程

Computer&DigitalEngineeringVol.38No.4

59

一种新的基于SVM-KNN的Web文本分类算法

曹建芳 王鸿斌

(忻州师范学院计算机系 忻州 034000)

*

摘 要 在应用基本的支持向量机算法的基础上,提出了一种新的Web文本分类算法。将SVM算法和KNN算法进行结合,提出了基于SVM-KNN的Web文本分类算法,用KNN算法来弥补传统SVM算法的不足,以简单的思想和较小的实现代价对传统SVM算法进行有效的改进,收到了良好的分类效果。

关键词 SVM;KNN;Web文本分类;机器学习中图分类号 TP311

ANewWebTextClassificationBasedonSVM-KNN

CaoJianfang WangHongbin

(ComputerDepartment,XinzhouTeachersUniversity,Xinzhou 034000)

Abstract AnewWebtextclassificationalgorithmhasbeenputforwardbasedonbasicsupportvectormachinealgo-rithm.TheSVM-KNN-basedalgorithmforWebtextclassificationhasbeenproposed,whichcombinedSVMalgorithmandKNNalgorithmsusingtheKNNalgorithmtocompensateforthedeficienciesoftraditionalSVMalgorithmandtakingsimpleideasandsmallercosttoimprovetraditionalSVMalgorithm.Themethodinthispaperhasgainedgoodeffect.

KeyWords supportvectormachine,K-nearestneighbor,Webtextclassification,machinelearningClassNumber TP311

1 引言

SVM算法凭借其多种优点在Web文本分类中占着重要地位,得到了广泛应用。但是传统的SVM算法也存在着明显的缺点,比如对于不同的应用问题核函数参数选择较难,对于复杂问题精度不够高等

[1,5]

一种方法是将SVM算法和其它分类算法进行结合,实现算法互补。本文将这种思想引入Web文本分类,将SVM算法和KNN算法进行结合,提出了SVM-KNN组合文本分类算法,通过SVM以外的算法KNN来弥补传统SVM算法的不足,以简单的思想和较小的实现代价对传统SVM算法进行有效的改进。在实现时,本文采用样本相似度代替样本距离,用效果稳定的夹角余弦函数公式计算代替常用的欧式距离公式,在实验中获得了很好的效果。

,这些缺点使得SVM算法的分类精

确度难以进一步提高,一定程度上制约了SVM算法的应用。

现在已经存在一些方法对传统SVM进行改进,比如建立分类性能的评价函数,然后对SVM中的核函数参数进行评价和优化,或者使用直推方法对给定待定样本选择最优的核函数参数等[3]。但是这些方法在对SVM进行改进的同时付出了较高的实现代价,设计和计算的复杂度都较高。有

2 SVM-KNN算法思想

对SVM分类器分类结果出错样本的分布进行分析研究可以发现,SVM分类器的出错样本多集中在分界面的附近,而远离分界面的样本基本能

*

收稿日期:2009年12月5日,修回日期:2010年1月18日基金项目:忻州师范学院科研基金项目(编号:200904)资助。

:,:

60曹建芳等:一种新的基于SVM-KNN的Web文本分类算法第38卷

够得到正确的分类。由此可见,对分界面附近的样本进行正确分类是提高SVM分类器分类准确率的关键。

根据SVM理论可知,分界面附近的点多是支持向量,选择支持向量作为每个类的代表点,此时可以把所有的支持向量看作一个KNN分类器[11]。这样,传统的SVM分类器便成为一个包含两个分类器的复合分类器,对于向量空间不同分布的样本采用不同的分类方法。具体的,当样本和SVM最优超平面(分界面)的距离大于一个给定的阈值,即样本与分界面的距离较远时,采用SVM分类器进行分类,反之则使用KNN分类器进行分类。

这样,在保持了传统SVM分类算法的优点的基础上,以KNN算法弥补SVM算法的薄弱环节,可以提高SVM分类器的准确率;同时,

图1 SVM-KNN算法

else取xIT;2)代入公式f(x)=sgn

i=1

EAyK(x

*

i

i

l

i

#x)+b*

进行计算;

3)if|f(x)|>E,then直接计算f(x)作为输出;elseif|f(x)|FE,then

传递参数x、Tsv、K,代入KNN算法进行分类,返回结果作为输出;

4)T=T-{x},转步骤1)。

步骤3)中所使用的KNN分类算法和前面介绍的KNN分类算法流程相同,将支持向量集Tsv作为分类算法的代表点集合即可。其中,计算待分类样本和每个支持向量的相似度时不再使用欧式距离公式,而是使用夹角余弦函数公式:

cos(X,Y)=

E(X

i

i

@Yi)

(X

i

2

i

)@

(Y

i

2i

)

由于添加的KNN分类

经过已有相关项目的文本分类实验证明,在面对高维特征向量时,夹角余弦函数能够获得更稳定的效果。

分类阈值E通常设为1左右,当E为0时,KNN分类器则被屏蔽,SVM-KNN算法就变成传统的SVM算法。

器是基于SVM分类器的支持向量的,以所有的支持向量集作为KNN算法的训练集,使KNN算法的计算复杂度很低,所以,增加KNN分类器其实增加的运算量很小。其具体思想如图1所示。

SVM算法可以看作是每个类只有一个代表点的KNN(K=1)分类器,由于每个类的支持向量只取一个代表点,难以保证这个点能够很好地代表该类。这时将SVM算法与KNN相结合,将每个类的所有支持向量作为代表点,从而获得更好的分类精度。具体地,对于待分类样本x,计算x与两类支持向量代表点x+和x-的相似度差,如果相似度差大于给定的阈值,即x离分界面较远,如图1中区域Ñ和Ò,用SVM分类器一般都可以进行正确分类。当相似度差小于或等于给定的阈值,即x离分界面较近,即落入区域Ó时,如果仍用SVM分类则难以保证其准确性,很容易出错,这时采用KNN分类器对测试样本分类,将每个支持向量作为代表点,计算待 …… 此处隐藏：3173字，全部文档内容请下载后查看。喜欢就下载吧 ……