前記
隨著文本信息量的快速增長, 文本分類己成為信息檢索、知識挖掘和管理等領(lǐng)域的關(guān)鍵技術(shù)。文本分類的精確程度取決于特征提取的科學(xué)性和分類算法的科學(xué)性。現(xiàn)有的文本分類方法主要有支持向量機(jī)(SVM)、k 最近鄰(KNN)、決策樹、線性最小二乘法估計(jì)(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)分類算法，是一個理論上比較成熟的方法，也是最簡單的機(jī)器學(xué)習(xí)算法之一。該方法的思路是：如果一個樣本在特征空間中的k個最相似(即特征空間中最鄰近)的樣本中的大多數(shù)屬于某一個類別，則該樣本也屬于這個類別。KNN算法中，所選擇的鄰居都是已經(jīng)正確分類的對象。該方法在定類決策上只依據(jù)最鄰近的一個或者幾個樣本的類別來決定待分樣本所屬的類別。 KNN方法雖然從原理上也依賴于極限定理，但在類別決策時(shí)，只與極少量的相鄰樣本有關(guān)。由于KNN方法主要靠周圍有限的鄰近的樣本，而不是靠判別類域的方法來確定所屬類別的，因此對于類域的交叉或重疊較多的待分樣本集來說，KNN方法較其他方法更為適合。
KNN算法不僅可以用于分類，還可以用于回歸。通過找出一個樣本的k個最近鄰居，將這些鄰居的屬性的平均值賦給該樣本，就可以得到該樣本的屬性。更有用的方法是將不同距離的鄰居對該樣本產(chǎn)生的影響給予不同的權(quán)值(weight)，如權(quán)值與距離成正比。
2. KNN算法的決策過程
如下圖，綠色圓要被決定賦予哪個類，是紅色三角形還是藍(lán)色四方形？如果K=3，由于紅色三角形所占比例為2/3，綠色圓將被賦予紅色三角形那個類，如果K=5，由于藍(lán)色四方形比例為3/5，因此綠色圓被賦予藍(lán)色四方形類。
3. 存在的不足
該算法在分類時(shí)有個主要的不足是，當(dāng)樣本不平衡時(shí)，如一個類的樣本容量很大，而其他類樣本容量很小時(shí)，有可能導(dǎo)致當(dāng)輸入一個新樣本時(shí)，該樣本的K個鄰居中大容量類的樣本占多數(shù)。因此可以采用權(quán)值的方法（和該樣本距離小的鄰居權(quán)值大）來改進(jìn)。該方法的另一個不足之處是計(jì)算量較大，因?yàn)閷γ恳粋�待分類的文本都要計(jì)算它到全體已知樣本的距離，才能求得它的K個最近鄰點(diǎn)。目前常用的解決方法是事先對已知樣本點(diǎn)進(jìn)行剪輯，事先去除對分類作用不大的樣本。該算法比較適用于樣本容量比較大的類域的自動分類，而那些樣本容量較小的類域采用這種算法比較容易產(chǎn)生誤分。
4. 改進(jìn)的KNN算法
a. 快速KNN算法。FKNN：http://www.docin.com/p-9581757.html **（實(shí)際應(yīng)用中結(jié)合lucene）**
b. 加權(quán)歐氏距離公式。在傳統(tǒng)的歐氏距離中,各特征的權(quán)重相同,也就是認(rèn)定各個特征對于分類的貢獻(xiàn)是相同的,顯然這是不符合實(shí)際情況的。同等的權(quán)重使得特征向量之間相似度計(jì)算不夠準(zhǔn)確, 進(jìn)而影響分類精度。加權(quán)歐氏距離公式,特征權(quán)重通過靈敏度方法獲得**。（根據(jù)業(yè)務(wù)需求調(diào)整，例如關(guān)鍵字加權(quán)、詞性加權(quán)等）**
5. 算法的實(shí)現(xiàn)
以下實(shí)現(xiàn)語料庫基于搜狗文本分類語料庫：http://www.sogou.com/labs/dl/c.html
a. 傳統(tǒng)knn實(shí)現(xiàn)。主要分為訓(xùn)練和計(jì)算兩個步驟，以下是代碼片段：
1. 訓(xùn)練文本，構(gòu)建語料庫。
(1)訓(xùn)練指定文件夾中的語料 － 》 (2)讀取單個文件，構(gòu)建語料庫 －》 (3)對文本進(jìn)行分詞（基于中科院分詞器），構(gòu)建 詞組 向量模型 －》重復(fù)(2)(3)
b. 改進(jìn)的KNN算法實(shí)現(xiàn)
1. 利用lucene對所有語料庫建立索引
2. 改進(jìn)lucene search score機(jī)制
3. 獲取最近N篇語料
.png)
4. 計(jì)算類目
6. 測試案例
待續(xù)
7. 后感
文本分類的進(jìn)一步改進(jìn)不在算法方面，應(yīng)該立足于影響文本分類最底層、最根本的因素：文本表示中的特征項(xiàng)，提高特征項(xiàng)的完整獨(dú)立程度。關(guān)鍵短語是具有強(qiáng)文本表示功能的特征短語，在表示文本時(shí)，能將文本的內(nèi)容特征（如主題類別）鮮明地表示出來。關(guān)鍵短語具有結(jié)構(gòu)穩(wěn)定、語義完整和強(qiáng)統(tǒng)計(jì)意義的特點(diǎn)，能克服向量空間模型和其他算法的缺點(diǎn)，更適合作為文本表示的特征，有利于提高文本分類的效果。
喜歡 
頂
難過
囧
圍觀
無聊
