资源描述：
《基于聚类的knn算法改进》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、基于聚类的KNN算法改进摘要：通过研究KNN算法，提岀了一种利用训练集文本聚类结果改进KNN算法的方法，首先将训练集文本采用DBSCAN算法聚进行聚类，将训练集文本分为若干个簇，然后采用KNN算法对测试文档进行测试，最后用距离最近的n个簇中的若干训练集文本使用KNN算法对测试文本进行分类。实验表明，改进后的算法降低了计算量，提高了效率，同时对聚类结果有了一定的改进。关键词：KNN算法;DBSCAN算法；训练集中图分类号：TP391文献标识码：AAnimprovedKNNAlgorithmBasedonClusteringFANDong-huil2,WANGZhi-hel,CHEN
2、Jian-hual,XUHu-yin1(1>CollegeofMathematicsandInformationScienee,NorthwestNormalUniversity,Lanzhou730070,china2、ZhumadianVocationalandTechnicalCollegehenan463000)Abstract:BystudyingtheKNNalgorithm,IproposedthemethodatrainingsetoftextclusteringresultsusingKNNalgorithmtoimprove,firstthetrainings
3、etusingtextDBSCANalgorithmtoclustertogether,thetextisdividedintoanumberoftrainingsetclusters,thenusingKNNalgorithmtestdocumentfortesting,andfinallywiththenearestclusterofnnumberoftrainingsetinthetexttextusingKNNalgorithmtoclassifythetest.Experimentsshowthattheimprovedalgorithmreducestheamount
4、ofcomputation,improveefficiency,whileacertainimprovementofclusteringresults・Keywords:featureselection;documentfrequency;wordfrequency1＞引言文本自动分类是指对未知类别的文档进行自动处理，判断它所属类别。随着各种形式的文本文档以指数级的速度增长，有效的信息检索、内容管理等应用变得愈加重要和困难。文本自动分类作为一个有效的解决办法，已成为一项具有实用价值的关键技术。现如今已有诸多分类技术和方法被提出来，例如KNN算法(K-NearestNeighbou
5、r)!^贝叶斯网络(BayesNetwork)2、支持向量机（SVM）3等。其中KNN算法简单、有效，计算时间和空间线性于训练集的规模被广泛采用。但由KNN算法具体步骤可以知道：KNN是非积极学习方法，基本上不学习;再者每个训练集样本需要与训练集中样本进行计算,计算量非常大；还有因为要与单个训练集样本进行计算，易受单个样本的影响4。针对其局限性，我们提出改进的KNN算法就是在训练集样本中先进行聚类,然后利用KNN算法计算测试集样本与训练集样本簇之间的距离，选用较近的n个簇，用这n个簇中的训练集样本和测试集样本再采用KNN算法来确定测试集样本的分类。2.1、传统的kNN算法对于测试
6、集中每一个测试文本，都需要计算它与训练集中每个文本的距离，然后把距离排序找到离该测试文本最近的k个文本，根据测试文本与训练文本的距离来给该测试文档的候选类别按公式（1）评分。如果有属于同一个类别的,就将该类别中的文本的打分求和作为该类别的得分。最后,将得分排序，测试文本将被分配给得分最高的那个类别。（1）x是一个测试集文本，c是训练集的类别，d是距离X最近的k个文本之一；sim(x,d)是文本x与文本d的相似度，这里指的是距离；l(d,c)是表示d是否属于类c,如果属于类c则为I,否则为0。2.2、改进的IKNN算法首先对训练集文本进行聚类，采用DBSCAN算法算法过程如下：第一
7、步：如果文本对象P未被归入某个簇或标记为噪声，就检查它的指定半径邻域r,如果指定半径邻域内包含的对象数目大于等于给定的值m,就建立新簇C,将p的指定半径领域r中所有点加入该簇C；第二步：对C中所有尚未被处理(归入某个簇或标记为噪声)的对象q,检查它的指定半径邻域，如果该邻域内包含对象数目大于等于给定的值m,将该邻域中没有归入任何一个簇的对象加入C；第三步：重复第二步，继续检查C中未被处理对象，直到没有新的对象加入当前簇C：第四步:重复以上步骤，直到所有对象都被处理。其中关键参数为
