改進KNN算法描述及實現(xiàn)

100多種java算法大全源碼包

• 類型：編程輔助大�。�1.0M語言：中文 評分：9.0
• 標(biāo)簽：

立即下載

前記
    隨著文本信息量的快速增長, 文本分類己成為信息檢索、知識挖掘和管理等領(lǐng)域的關(guān)鍵技術(shù)。文本分類的精確程度取決于特征提取的科學(xué)性和分類算法的科學(xué)性�，F(xiàn)有的文本分類方法主要有支持向量機(SVM)、k 最近鄰(KNN)、決策樹、線性最小二乘法估計(LLSF)和貝葉斯分類算法(Bayes)等。KNN 算法是 VSM(向量空間模型)下最好的分類算法之一。

1. 何為KNN？
    以下是引用wiki的一個定義：

    k-nearest neighbors algorithm (k-NN) is a method for classifying objects based on closest training examples in the feature space. k-NN is a type of instance-based learning, or lazy learning where the function is only approximated locally and all computation is deferred until classification. The k-nearest neighbor algorithm is amongst the simplest of all machine learning algorithms: an object is classified by a majority vote of its neighbors, with the object being assigned to the class most common amongst its k nearest neighbors (k is a positive integer, typically small). If k = 1, then the object is simply assigned to the class of its nearest neighbor.

    K最近鄰(k-Nearest Neighbor，KNN)分類算法，是一個理論上比較成熟的方法，也是最簡單的機器學(xué)習(xí)算法之一。該方法的思路是：如果一個樣本在特征空間中的k個最相似(即特征空間中最鄰近)的樣本中的大多數(shù)屬于某一個類別，則該樣本也屬于這個類別。KNN算法中，所選擇的鄰居都是已經(jīng)正確分類的對象。該方法在定類決策上只依據(jù)最鄰近的一個或者幾個樣本的類別來決定待分樣本所屬的類別。 KNN方法雖然從原理上也依賴于極限定理，但在類別決策時，只與極少量的相鄰樣本有關(guān)。由于KNN方法主要靠周圍有限的鄰近的樣本，而不是靠判別類域的方法來確定所屬類別的，因此對于類域的交叉或重疊較多的待分樣本集來說，KNN方法較其他方法更為適合。

    　KNN算法不僅可以用于分類，還可以用于回歸。通過找出一個樣本的k個最近鄰居，將這些鄰居的屬性的平均值賦給該樣本，就可以得到該樣本的屬性。更有用的方法是將不同距離的鄰居對該樣本產(chǎn)生的影響給予不同的權(quán)值(weight)，如權(quán)值與距離成正比。

2. KNN算法的決策過程
    　如下圖，綠色圓要被決定賦予哪個類，是紅色三角形還是藍色四方形？如果K=3，由于紅色三角形所占比例為2/3，綠色圓將被賦予紅色三角形那個類，如果K=5，由于藍色四方形比例為3/5，因此綠色圓被賦予藍色四方形類。

 3. 存在的不足
    該算法在分類時有個主要的不足是，當(dāng)樣本不平衡時，如一個類的樣本容量很大，而其他類樣本容量很小時，有可能導(dǎo)致當(dāng)輸入一個新樣本時，該樣本的K個鄰居中大容量類的樣本占多數(shù)。因此可以采用權(quán)值的方法（和該樣本距離小的鄰居權(quán)值大）來改進。該方法的另一個不足之處是計算量較大，因為對每一個待分類的文本都要計算它到全體已知樣本的距離，才能求得它的K個最近鄰點。目前常用的解決方法是事先對已知樣本點進行剪輯，事先去除對分類作用不大的樣本。該算法比較適用于樣本容量比較大的類域的自動分類，而那些樣本容量較小的類域采用這種算法比較容易產(chǎn)生誤分。

4. 改進的KNN算法
a. 快速KNN算法。FKNN：http://www.docin.com/p-9581757.html **（實際應(yīng)用中結(jié)合lucene）**

b. 加權(quán)歐氏距離公式。在傳統(tǒng)的歐氏距離中,各特征的權(quán)重相同,也就是認定各個特征對于分類的貢獻是相同的,顯然這是不符合實際情況的。同等的權(quán)重使得特征向量之間相似度計算不夠準(zhǔn)確, 進而影響分類精度。加權(quán)歐氏距離公式,特征權(quán)重通過靈敏度方法獲得**。（根據(jù)業(yè)務(wù)需求調(diào)整，例如關(guān)鍵字加權(quán)、詞性加權(quán)等）**

5. 算法的實現(xiàn)
以下實現(xiàn)語料庫基于搜狗文本分類語料庫：http://www.sogou.com/labs/dl/c.html

a. 傳統(tǒng)knn實現(xiàn)。主要分為訓(xùn)練和計算兩個步驟，以下是代碼片段：
    1. 訓(xùn)練文本，構(gòu)建語料庫。

     (1)訓(xùn)練指定文件夾中的語料 － 》  (2)讀取單個文件，構(gòu)建語料庫 －》 (3)對文本進行分詞（基于中科院分詞器），構(gòu)建 詞組 向量模型  －》重復(fù)(2)(3)





 

b. 改進的KNN算法實現(xiàn)

1. 利用lucene對所有語料庫建立索引


2. 改進lucene search score機制

3. 獲取最近N篇語料

4. 計算類目

6. 測試案例
待續(xù)

7. 后感
文本分類的進一步改進不在算法方面，應(yīng)該立足于影響文本分類最底層、最根本的因素：文本表示中的特征項，提高特征項的完整獨立程度。關(guān)鍵短語是具有強文本表示功能的特征短語，在表示文本時，能將文本的內(nèi)容特征（如主題類別）鮮明地表示出來。關(guān)鍵短語具有結(jié)構(gòu)穩(wěn)定、語義完整和強統(tǒng)計意義的特點，能克服向量空間模型和其他算法的缺點，更適合作為文本表示的特征，有利于提高文本分類的效果。