一種改進的K值最近鄰自動分類方法

摘 要：K值最近鄰法是常用的一種自動分類算法。當待分類文本與樣本集中多個決策樣本的距離相等的時候，固定的K值取法不能充分利用樣本集，給分類結果帶來一定的隨機性，影響了自動分類的準確性。本文通過對K值最近鄰算法的原理進行深入分析，提出了一種K值動態(tài)選取的方案，使得K值最近鄰算法的分類準確性有了顯著的提高。

關鍵詞：K值最近鄰算法；自動分類；決策樣本選??；KNN

中圖分類號：TP302.1

隨著互聯(lián)網的發(fā)展，互聯(lián)網網頁信息數(shù)量急劇增加，根據(jù)中國互聯(lián)網絡信息中心（CNNIC）第31次報告，截至2012年12月底，中國網頁數(shù)量為1227億個，其中文本信息網頁占絕大多數(shù)。網頁數(shù)量的急劇增加使得對互聯(lián)網信息的分類需求越發(fā)迫切。文本自動分類是數(shù)據(jù)挖掘領域中一種重要的技術，它從一組已知的訓練樣樣本中發(fā)現(xiàn)分類模型，并且使用這個分類模型來預測待分類樣本的類別[1]。

K值最近鄰算法（KNN算法）[2]是比較常見的一種用來做文本自動分類的算法，最初的近鄰法由Cover和Hart于1968年提出[3]。該方法的思路是：如果一個文獻在特征空間中的K個最近鄰文獻中的大多數(shù)屬于一個類別，則該文獻也屬于這個類別。KNN算法使用后驗概率的估值作為后驗概率，是一個次優(yōu)方法。KNN算法只與鄰近的樣本有關，通過鄰近樣本所屬的類別來決策，這就使它對于具體的分類體系沒有較大的依賴，比較適合于文本自動分類。

一般認為，KNN算法的主要缺點有：一是計算量較大，因為對每一個待分類的文獻，都要計算它到全體已知樣本的距離，才能求得它的K個最近鄰點。常用的解決方法一是事先對已經樣本點進行剪輯，去除對分類作用不大的樣本，另一種方法是用空間換時間，事先將所有樣本點的兩兩距離計算出來并存入相應的位置以備檢索。二是處理過程中，所有的臨近K值對結果點的影響效果是一樣的，不管這個點離它有多遠。而在實際應用中，可以采取附加權值的方法，放大臨近點對結果的影響。

業(yè)界對KNN算法的研究多專注于減少計算量的角度。參考文獻[3]提出用概念樹來管理類別特征從而減少運算量的思路，參考文獻[4][5]提出通過對分類體系各類別均建立代表點來減少運算量的思路，參考文獻[6][7]是通過多步驟分級計算來減少計算量提高系統(tǒng)有效性，參考文獻[8]則提出利用每次k-NN查詢中保存的近鄰點到被查詢點的距離汁算出近鄰點孤立程度上界的提前修剪算法。這些思路和方法，都取得了一定的效果，提高了自動分類系統(tǒng)的有效性。各類文獻中關于充分利用樣本庫的資源來進一步提高分類準確率的方面，討論的不多。

1 等距離樣本不公問題及解決

KNN算法嚴重依賴樣本庫。一方面來說，如果樣本庫分布不均勻，某些類型偏多某些類型偏少，則會對分類結果的正確性產生較大的影響，另一方便來說，如果不能充分利用樣本庫的資源，也可能使得分類結果產生一定的偏差。

KNN算法最重要的步驟就是要計算待分類文本與樣本庫中各文本的距離，并排序，然后取出前K個文本。文本的距離有多種計算方法，其中一個常用的有效方法是：提取文本的屬性向量，然后計算代表文本的屬性向量之間的距離，即用向量的距離代表文本的距離。在實際的開發(fā)測試過程中我們發(fā)現(xiàn)，在樣本數(shù)量比較大的時候，兩個向量之間的距離相同是比較常見的現(xiàn)象，這就導致了等距離文本也是比較常見的。

設T為待分類的文本，Si（i=1，2，3，…N，N為樣本總數(shù)）為知識庫中的樣本，定義Dti為待分文本T到樣本Si的距離，根據(jù)KNN算法，我們應該取Dti（i=1，2，3，…N）中最小的K（K≤N）個值，并按照這K個值對應的K個樣本來進行分類決策。

設di為Dti（i=1，2，3，…N）按照從小到大進行排序以后所得的序列，其對應的樣本為Si，即T到Si的距離為di，并有d1≤d2≤d3≤…≤dN。按照KNN算法，取di（i=1，2，3，…N）的前K個值即為距離待分文本T最近的K個樣本Si（i=1，2，3，…K）到待分文本T的距離，只需要根據(jù)Si（i=1，2，3，…K）這K個樣本進行分類決策即可。

然而，我們發(fā)現(xiàn)，如果dK=dK+1，那么我們采用Sk而不采用Sk+1進行分類決策就對樣本Sk+1不公平，我們沒有任何理由選取Sk卻不選Sk+1作為分類決策樣本，因為這兩個樣本到待分文本T的距離是完全相等的。但是由于我們只能選取K個樣本，Sk與Sk+1必舍其一，這樣得到的最后的分類結果可能不是最優(yōu)。事實上，在我們實驗中發(fā)現(xiàn)，dK-1

圖1 等距離樣本不公問題

仔細分析等距離樣本不公問題，我們發(fā)現(xiàn)固定決策樣本個數(shù)K是產生問題的直接原因，那么能不能動態(tài)修訂K值，使得在分類過程中能更加充分的利用已知樣本從而獲取更高的分類準確率呢？

將K值變大或變小都能解決等距離樣本不公的問題。如果存在正整數(shù)m或n，能滿足dK-m0，那么針對待分類文本T的決策樣本就取S1到SK-m這K-m個樣本作為決策樣本，或者取S1到SK+n共計K+n個樣本作為決策樣本，這樣取到的決策樣本對于待分類文本T來說，用于分類決策的樣本都是公平的。我們稱此方案為基本修正方案。

基本修正方案解決了等距離樣本不公問題，但在極端情況下，會出現(xiàn)K為1或者K為樣本總量的情況。如果K值取無限大，相當于所有的樣本都參與決策，決策起來反而變得困難。如果K值取1，相當于只有距離最近的一個樣本參與決策，使用到的決策樣本數(shù)太少，決策信息不足。以上兩種極端情形都會使得分類準確率明顯下降。為了提高總體分準率，在基本修正方案的基礎上做些修改，可以得到一個次優(yōu)修正方案：次優(yōu)修正方案的思路是：設定一個區(qū)間[Kmin，Kmax]，使得K在這個范圍內波動，如果存在dKmin-1=dKmin，或者存在dKmax=dKmax+1，K仍然取Kmin或Kmax，而不再持續(xù)的增大或縮小K值，這種思路沒有完全解決等距離樣本不公問題，但他還是解決了部分問題并且使得K值處于一個可控的范圍之內。

動態(tài)修改KNN算法中K值過程的本質，其實是針對不同的待分類文本的特點，在一定的范圍內，動態(tài)選取決策樣本數(shù)量的過程。由于每個待分類文檔相互獨立，沒有相關性，所以實際上并不需要要求對每個待分類文檔都采用相同的決策樣本數(shù)量。根據(jù)待分文本的特點動態(tài)選取決策樣本數(shù)量是有效提高分類準確率的可行的思路。

2 測試結果

我們采用已手工分類的100000篇網絡文章作為基礎，選取其中99000作為樣本庫，涉及19個大類，另外1000篇作為待分文本。采用KNN算法對1000篇待分文本進行自動分類。分別采用固定K值法、基本修正方案法和次優(yōu)修正方案法三種方法來進行分類，并對分類結果與已知的手工結果作對比以獲取分準率。固定K值法時取K=7，次優(yōu)修正方案法取Kmin=5，Kmax=9。測試結果如下表：

表1 分類結果對照表

方法分準篇數(shù)分準率

固定K82482.4%

基本修正方案88588.5%

次優(yōu)修正方案89289.2%

可以看出，動態(tài)修改K值后可以更加充分的使用到已知樣本的信息，分類準確率會有5%到7%的提高。

3 結束語

KNN算法簡單、準確，在文本自動分類系統(tǒng)設計中是一種常用的算法。優(yōu)化并提高KNN算法的分類準確率將有助于提高文本自動分類系統(tǒng)的分類準確率，從而提高文本自動分類系統(tǒng)的實用性。本文發(fā)現(xiàn)了KNN分類過程中等距離樣本不公問題，并給出了有效的解決方案，提高了KNN算法的分類準確率。但是目前對于Kmin和Kmax等初始參數(shù)的選取上，還停留在實驗驗證階段，如何更加準確的選出這些參數(shù)值，還有待于后續(xù)進一步地研究。

參考文獻：

[1]張著英，黃玉龍，王翰虎.一個高效的KNN分類法[J].計算機科學，2008（03）：170.

[2]張寧，賈自艷，史忠植.使用KNN算法的文本分類[J].計算機工程，200（08）：171.

[3]盧志翔.一種基于KNN用戶興趣快速分類算法[J].計算機光盤軟件與應用，2010（14）：48.

[4]陳可華.文本自動分類新探究[J].赤峰學院學報（自然科學版），2011（04）：34.

[5]陳可華.基于多代表點的文本分類研究[J].鄭州大學學報（工學版），2010（06）：116.

[6]吳春穎，王士同.一種改進的KNN Web文本分類方法[J].計算機應用研究，2008（11）：3275.

[7]何亮，宋擒豹，沈鈞毅.一種新的組合k-近鄰預測方法[J].西安交通大學學報，2009（04）：5.

[8]邵紀東，榮岡，顧海杰.度量空間中基于距離孤立點的快速挖掘[J].浙江大學學報（工學版），2009（02）：297.

作者簡介：李偉（1978-），男，河南商丘人，工程師，碩士，研究方向：web服務系統(tǒng)設計開發(fā)、數(shù)據(jù)挖掘。

作者單位：中國銀聯(lián)技術開發(fā)中心，上海 201201