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

關(guān)鍵詞：K值最近鄰算法；自動(dòng)分類；決策樣本選??；KNN

中圖分類號(hào)：TP302.1

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

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

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

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

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

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

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

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

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

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

圖1 等距離樣本不公問題

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

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

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

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

2 測(cè)試結(jié)果

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

表1 分類結(jié)果對(duì)照表

方法分準(zhǔn)篇數(shù)分準(zhǔn)率

固定K82482.4%

基本修正方案88588.5%

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

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

3 結(jié)束語(yǔ)

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

參考文獻(xiàn)：

[1]張著英，黃玉龍，王翰虎.一個(gè)高效的KNN分類法[J].計(jì)算機(jī)科學(xué)，2008（03）：170.

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

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

[4]陳可華.文本自動(dòng)分類新探究[J].赤峰學(xué)院學(xué)報(bào)（自然科學(xué)版），2011（04）：34.

[5]陳可華.基于多代表點(diǎn)的文本分類研究[J].鄭州大學(xué)學(xué)報(bào)（工學(xué)版），2010（06）：116.

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

[7]何亮，宋擒豹，沈鈞毅.一種新的組合k-近鄰預(yù)測(cè)方法[J].西安交通大學(xué)學(xué)報(bào)，2009（04）：5.

[8]邵紀(jì)東，榮岡，顧海杰.度量空間中基于距離孤立點(diǎn)的快速挖掘[J].浙江大學(xué)學(xué)報(bào)（工學(xué)版），2009（02）：297.

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

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