資源描述：
《基于聚類的knn算法改進(jìn)》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫(kù)。
1、基于聚類的KNN算法改進(jìn)摘要：通過(guò)研究KNN算法，提岀了一種利用訓(xùn)練集文本聚類結(jié)果改進(jìn)KNN算法的方法，首先將訓(xùn)練集文本采用DBSCAN算法聚進(jìn)行聚類，將訓(xùn)練集文本分為若干個(gè)簇，然后采用KNN算法對(duì)測(cè)試文檔進(jìn)行測(cè)試，最后用距離最近的n個(gè)簇中的若干訓(xùn)練集文本使用KNN算法對(duì)測(cè)試文本進(jìn)行分類。實(shí)驗(yàn)表明，改進(jìn)后的算法降低了計(jì)算量，提高了效率，同時(shí)對(duì)聚類結(jié)果有了一定的改進(jìn)。關(guān)鍵詞：KNN算法;DBSCAN算法；訓(xùn)練集中圖分類號(hào)：TP391文獻(xiàn)標(biāo)識(shí)碼：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＞引言文本自動(dòng)分類是指對(duì)未知類別的文檔進(jìn)行自動(dòng)處理，判斷它所屬類別。隨著各種形式的文本文檔以指數(shù)級(jí)的速度增長(zhǎng)，有效的信息檢索、內(nèi)容管理等應(yīng)用變得愈加重要和困難。文本自動(dòng)分類作為一個(gè)有效的解決辦法，已成為一項(xiàng)具有實(shí)用價(jià)值的關(guān)鍵技術(shù)?，F(xiàn)如今已有諸多分類技術(shù)和方法被提出來(lái)，例如KNN算法(K-NearestNeighbou
5、r)!^貝葉斯網(wǎng)絡(luò)(BayesNetwork)2、支持向量機(jī)（SVM）3等。其中KNN算法簡(jiǎn)單、有效，計(jì)算時(shí)間和空間線性于訓(xùn)練集的規(guī)模被廣泛采用。但由KNN算法具體步驟可以知道：KNN是非積極學(xué)習(xí)方法，基本上不學(xué)習(xí);再者每個(gè)訓(xùn)練集樣本需要與訓(xùn)練集中樣本進(jìn)行計(jì)算,計(jì)算量非常大；還有因?yàn)橐c單個(gè)訓(xùn)練集樣本進(jìn)行計(jì)算，易受單個(gè)樣本的影響4。針對(duì)其局限性，我們提出改進(jìn)的KNN算法就是在訓(xùn)練集樣本中先進(jìn)行聚類,然后利用KNN算法計(jì)算測(cè)試集樣本與訓(xùn)練集樣本簇之間的距離，選用較近的n個(gè)簇，用這n個(gè)簇中的訓(xùn)練集樣本和測(cè)試集樣本再采用KNN算法來(lái)確定測(cè)試集樣本的分類。2.1、傳統(tǒng)的kNN算法對(duì)于測(cè)試
6、集中每一個(gè)測(cè)試文本，都需要計(jì)算它與訓(xùn)練集中每個(gè)文本的距離，然后把距離排序找到離該測(cè)試文本最近的k個(gè)文本，根據(jù)測(cè)試文本與訓(xùn)練文本的距離來(lái)給該測(cè)試文檔的候選類別按公式（1）評(píng)分。如果有屬于同一個(gè)類別的,就將該類別中的文本的打分求和作為該類別的得分。最后,將得分排序，測(cè)試文本將被分配給得分最高的那個(gè)類別。（1）x是一個(gè)測(cè)試集文本，c是訓(xùn)練集的類別，d是距離X最近的k個(gè)文本之一；sim(x,d)是文本x與文本d的相似度，這里指的是距離；l(d,c)是表示d是否屬于類c,如果屬于類c則為I,否則為0。2.2、改進(jìn)的IKNN算法首先對(duì)訓(xùn)練集文本進(jìn)行聚類，采用DBSCAN算法算法過(guò)程如下：第一
7、步：如果文本對(duì)象P未被歸入某個(gè)簇或標(biāo)記為噪聲，就檢查它的指定半徑鄰域r,如果指定半徑鄰域內(nèi)包含的對(duì)象數(shù)目大于等于給定的值m,就建立新簇C,將p的指定半徑領(lǐng)域r中所有點(diǎn)加入該簇C；第二步：對(duì)C中所有尚未被處理(歸入某個(gè)簇或標(biāo)記為噪聲)的對(duì)象q,檢查它的指定半徑鄰域，如果該鄰域內(nèi)包含對(duì)象數(shù)目大于等于給定的值m,將該鄰域中沒(méi)有歸入任何一個(gè)簇的對(duì)象加入C；第三步：重復(fù)第二步，繼續(xù)檢查C中未被處理對(duì)象，直到?jīng)]有新的對(duì)象加入當(dāng)前簇C：第四步:重復(fù)以上步驟，直到所有對(duì)象都被處理。其中關(guān)鍵參數(shù)為
