基于簇的K最近邻

  本文关键词：基于决策树和K最近邻算法的文本分类研究，由笔耕文化传播整理发布。

优化算法

42622009,30(18)计算机工程与设计ComputerEngineeringandDesign

Ifdi(i=1)，看作第一簇，分配簇ID=0，簇的中心向量

就是文本向量，将簇ID放入中心向量词条的簇链表中

else基于已经生成的(还没有完全生成，只生成了一部

分)词条到簇的倒排索引结构，找到和di的词条有交集的簇(Clus)，所有这样的簇组成簇集合(CS)

j=1

while(j≤|CS|)(|CS|表示CS的长度)

Ifdi与CSj的中心向量(ccvj)的相似度Sim(di，ccvj)>=

中心向量相似阈值(预先给定)

Ifdi和CSj中每个文本的相似度都>=文本相似阈

值(预先给定)，分别记下簇ID、最大相似度，并设置标志表明文本能够归入已有的簇，j++，计算下一簇

Elsej++，计算下一簇Elsej++，计算下一簇

If能够归入已有簇，选择相似度最大的一簇加入，簇中成员发生变化，更新中心向量，如果中心向量中加入了新的词条，将簇ID放入新词条的簇链表中

Else自成一簇，簇ID为已有最大簇ID加一，，簇的中心向量就是文本向量，将簇ID放入中心向量词条的簇链表中

i++

3.3基于簇的KNN分类算法

把待分类文本d表示成文档向量V(w1，w2，…，wn)基于词条到簇的倒排索引结构，找到向量V中每个词条

ti(1≤i≤n)(n表示文档向量的长度)的簇链表li(1≤i≤n)

合并li，去掉重复的簇ID，得到簇集合(CS)

For(1≤j≤|CS|)(|CS|表示CS的长度)

依次计算d与CSj的中心向量(ccvj)的相似度Sim(d，ccvj)按照相似度排序，得到最近的m个簇Clusi(1≤i≤m)For(1≤i≤m)

计算d与Clusi中每个文本的相似度

按照相似度排序，得到最近的k个文本，根据这k个文本的类别得到待分类文本的类别。

4实验结果

我们从阿里巴巴网站上下载了30多万描述产品的网页，

其中30万的网页做训练集，其余的网页做测试集。下载的网页含有类标签，总共有2602个产品类，这些产品类有电子类、服装类等。

这些网页经过初步处理，写成了文本。文本由3部分组成，产品所属的类、产品的名字、产品的描述。训练文本分词、特征提取后，使用了公式(2)设置特征项的权重。生成簇的实验结果如表1所示。

表1

生成簇的实验结果

中心向量相似阈值

训练集文本总数

簇总数0.81193385150.8520万1154360.85

30万

163653

随着训练文本数的增加，簇总数在整个训练文本总数中所占比重逐步下降，从实验结果来看在训练样本较多的情况下，簇总数约为训练文本总数的一半左右。因此在训练文本总数较大的情况下，基于簇的文本分类能极大地降低相似度的计算次数，提高分类速度。基于簇的KNN分类器的实验结果如表2所示。

基于簇的KNN分类器的准确度经过多次实验得到的结

果大约是93%，由于很多的产品页(描述产品的网页)存在一些缺陷，例如厂家将自己的产品归入多个不同的类，产品的描述多变、不够规范，类目较细，所以试验得出的分类精度是切合实际的。

5结束语

本文针对传统KNN算法在寻找待分类文本的k个邻居

时，相似度计算过多的缺点，提出了基于簇的KNN分类算法。从实验结果来看，在训练样本较多的情况下，簇总数约为训练文本总数的一半左右，因此基于簇的KNN分类算法使时间复杂度降低到原来的一半左右，提高了分类器的性能。如果能够找到较好的训练样本，有望提高分类精度。

同时本文根据相同的特征项出现在文本中的位置不同，对分类的贡献也不同，应赋予不同的权重这一假设，改进了TF-IDF公式。

参考文献:

[1]台德艺,谢飞,胡学刚.文本分类技术研究[J].合肥学院学报(自然科学版),2007,17(3):61-64.

[2]王煜.基于决策树和K最近邻算法的文本分类研究[D].天津大学,2006.

[3]卢苇,彭雅.几种常用文本分类算法性能比较与分析[J].湖南大学学报:自然科学版,2007,34(6):67-69.

[4]刘华.基于关键短语的文本分类研究[J].中文信息学报.2007年,第21卷,第4期:34-41.

[5]

KristofCoussenment,DirkVandenPoel.Inprovingcustomercomplaintmanagementbyautomaticemailclassificationusinglinguisticstylefeaturesaspredictors[EB/OL].,2007.[6]

林永民,朱卫东.模糊KNN在文本分类中的应用研究[J].计算机应用与软件,2008,25(9):185-187.

[7]黄旭,朱艳琴,罗喜召.实时文本分类系统的研究与实现[J].计算机工程,2008,34(18):87-88.

[8]

秦玉平,艾青,王秀坤,等.基于支持向量机的兼类文本分类算法研究[J].计算机工程与设计,2008,29(2):408-410.

  本文关键词：基于决策树和K最近邻算法的文本分类研究，由笔耕文化传播整理发布。