謝紅，趙洪野

哈爾濱工程大學(xué)信息與通信工程學(xué)院，黑龍江哈爾濱 150001

基于卡方距離度量的改進(jìn)KNN算法

謝紅，趙洪野

哈爾濱工程大學(xué)信息與通信工程學(xué)院，黑龍江哈爾濱 150001

K-近鄰算法（K-nearestneighbor，KNN）是一種思路簡(jiǎn)單、易于掌握、分類(lèi)效果顯著的算法。決定K-近鄰算法分類(lèi)效果關(guān)鍵因素之一就是距離的度量，歐氏距離經(jīng)常作為K-近鄰算法中度量函數(shù)，歐式距離將樣本的不同特征量賦予相同的權(quán)重，但是不同特征量對(duì)分類(lèi)結(jié)果準(zhǔn)確性影響是不同的。采用更能體現(xiàn)特征量之間相對(duì)關(guān)系的卡方距離度量作為KNN算法的度量函數(shù)，并且采用靈敏度法進(jìn)行特征權(quán)重計(jì)算，克服歐氏距離的不足。分類(lèi)實(shí)驗(yàn)結(jié)果顯示，基于卡方距離的改進(jìn)算法的各項(xiàng)評(píng)價(jià)指標(biāo)優(yōu)于傳統(tǒng)的KNN算法。

K-近鄰算法；卡方距離；距離度量；二次式距離；歐式距離；靈敏度法

可用于分類(lèi)的方法有：決策樹(shù)、遺傳算法、神經(jīng)網(wǎng)絡(luò)、樸素貝葉斯、支持向量機(jī)、基于投票的方法、KNN分類(lèi)、最大熵［1］等。K-近鄰分類(lèi)算法［2］（K-nearest neighbor，KNN）是Covert和Hart于1968年首次提出并應(yīng)用于文本分類(lèi)的非參數(shù)的分類(lèi)算法。KNN算法的思路清晰，容易掌握和實(shí)現(xiàn)，省去了創(chuàng)建復(fù)雜模型的過(guò)程，只需要訓(xùn)練樣本集和測(cè)試樣本集，而當(dāng)新樣本加入到樣本集時(shí)不需要重新訓(xùn)練。雖然KNN算法有著諸多優(yōu)點(diǎn)，但也存在著以下不足。首先，分類(lèi)速度慢、計(jì)算復(fù)雜度高，需要計(jì)算測(cè)試樣本與所有的訓(xùn)練樣本的距離來(lái)確定k個(gè)近鄰；其次，特征權(quán)重對(duì)分類(lèi)精度的影響較大。針對(duì)上述缺點(diǎn)，一些學(xué)者提出相應(yīng)的改進(jìn)方法。為了提高分類(lèi)速度，降低計(jì)算復(fù)雜度，Juan L［3］建立了一個(gè)有效的搜索樹(shù)TKNN，提高了K-近鄰的搜索速度，彭凱等［4］提出基于余弦距離度量學(xué)習(xí)的偽K近鄰文本分類(lèi)算法，Lim等［5］用向量夾角的余弦引入權(quán)重系數(shù)，桑應(yīng)賓［6］提出一種基于特征加權(quán)的K Nearest Neighbor算法，來(lái)提高分類(lèi)準(zhǔn)確率。文獻(xiàn)［7-8］對(duì)輸入的樣本進(jìn)行簡(jiǎn)單的線性變換映射到新的向量空間，在新的向量空間對(duì)樣本進(jìn)行分類(lèi)，可以有效提高分類(lèi)性能。本文主要是對(duì)距離度量函數(shù)進(jìn)行改進(jìn)，用卡方距離度量函數(shù)替換歐氏距離度量函數(shù)，并在新的度量函數(shù)下計(jì)算特征量的權(quán)重系數(shù)，來(lái)提高分類(lèi)的準(zhǔn)確率。

1 KNN算法

KNN作為一種基于實(shí)例的分類(lèi)算法，被認(rèn)為是向量模型下最好的分類(lèi)算法之一［9］。KNN算法從測(cè)試樣本點(diǎn)y開(kāi)始生長(zhǎng)，不斷的擴(kuò)大區(qū)域，直到包含進(jìn)k個(gè)訓(xùn)練樣本點(diǎn)為止，并把測(cè)試樣本點(diǎn)y的類(lèi)別歸為這最近的k個(gè)訓(xùn)練樣本點(diǎn)出現(xiàn)頻率最大的類(lèi)別。KNN算法的主要操作過(guò)程如下：

1）建立測(cè)試樣本集和訓(xùn)練樣本集。訓(xùn)練樣本集表示為

4）選擇k個(gè)近鄰訓(xùn)練樣本。對(duì)于測(cè)試樣本點(diǎn)y按照式（1）找到在訓(xùn)練樣本集中離測(cè)試樣本點(diǎn)y最近的k個(gè)訓(xùn)練樣本點(diǎn)。

5）測(cè)試樣本y類(lèi)別的判別規(guī)則。即對(duì)步驟4）中得到的k個(gè)近鄰訓(xùn)練樣本點(diǎn)進(jìn)行統(tǒng)計(jì)，計(jì)算k個(gè)訓(xùn)練樣本點(diǎn)每個(gè)類(lèi)別所占的個(gè)數(shù)，把測(cè)試樣本的類(lèi)別歸為所占個(gè)數(shù)最多的訓(xùn)練樣本所屬的類(lèi)別。

2 卡方距離度量

選擇不同的距離計(jì)算方式會(huì)對(duì)KNN算法的分類(lèi)準(zhǔn)確率產(chǎn)生直接的影響，傳統(tǒng)的KNN算法使用歐氏距離作為距離的度量，歐氏距離的度量方式只考慮各個(gè)特征量絕對(duì)距離，往往忽視各特征量的相對(duì)距離。分類(lèi)中相對(duì)距離更加具有實(shí)際意義，卡方距離能有效反應(yīng)各特征量的相對(duì)距離變化，同時(shí)根據(jù)每個(gè)特征量對(duì)分類(lèi)貢獻(xiàn)的不同，結(jié)合靈敏度法計(jì)算卡方距離下的特征量的權(quán)重。

2.1 卡方距離模型

卡方距離是根據(jù)卡方統(tǒng)計(jì)量得出的，卡方距離已經(jīng)被應(yīng)用到很多的距離描述問(wèn)題，并且取得相當(dāng)好的效果。卡方距離公式為

2.2 卡方距離與二次卡方距離的關(guān)系

2個(gè)直方圖統(tǒng)計(jì)量X、Y是非負(fù)值而且有界限的，則2個(gè)直方圖距離的二次式距離公式為

如果矩陣A是協(xié)方差矩陣的逆，該二次式距離就是馬氏距離。如A是單位矩陣，二次式距離就是歐氏距離。QC代表二次卡方距離。而二次卡方距離［10］公式為

實(shí)際上二次卡方距離是二次式距離的標(biāo)準(zhǔn)形式，當(dāng)m＝0.5，W是單位矩陣時(shí)，此時(shí)的QC距離是卡方距離，其形式為

當(dāng)m＝0，二次卡方距離就是二次式距離。由此可見(jiàn)卡方距離和歐氏距離、馬氏距離一樣可以對(duì)特征向量進(jìn)行有效的度量。

2.3 權(quán)重調(diào)整系數(shù)的計(jì)算方法

卡方距離體現(xiàn)了特征量之間的相對(duì)關(guān)系，但是仍然對(duì)每個(gè)特征量賦予相同的權(quán)重，實(shí)際情況是不同特征對(duì)分類(lèi)的貢獻(xiàn)不同，因此，本文在卡方距離的基礎(chǔ)上采用靈敏度法對(duì)不同的特征賦予不同的權(quán)重。特征權(quán)重的計(jì)算方法如下：

1）用卡方距離代替歐氏距離對(duì)測(cè)試樣本進(jìn)行分類(lèi)，統(tǒng)計(jì)分類(lèi)錯(cuò)誤的樣本個(gè)數(shù)n。

4）第q個(gè)特征量的權(quán)重系數(shù)定義為

3 基于卡方距離的改進(jìn)KNN算法

本文在傳統(tǒng)的KNN的基礎(chǔ)上，采用卡方距離度量學(xué)習(xí)、應(yīng)用靈敏度法計(jì)算不同特征的權(quán)重，應(yīng)用新的距離度量函數(shù)代替歐式距離進(jìn)行度量，得到基于卡方距離的KNN（CSKNN）算法。

3.1 CSKNN算法基本流程

算法流程圖如圖1所示，基本流程如下。

1）創(chuàng)建測(cè)試樣本集和訓(xùn)練樣本集，訓(xùn)練樣本集表示為X，測(cè)試樣本集表示為Y。

2）給k設(shè)定一個(gè)初值。

3）計(jì)算測(cè)試樣本點(diǎn)和每個(gè)訓(xùn)練樣本點(diǎn)的加權(quán)卡方距離。公式如下所示：

4）在步驟3）所得的距離按照降序排列，選擇離測(cè)試樣本點(diǎn)較近的k個(gè)訓(xùn)練樣本。

5）統(tǒng)計(jì)步驟4）中得到的k個(gè)近鄰訓(xùn)練樣本點(diǎn)所屬的類(lèi)別，把測(cè)試樣本的類(lèi)別歸為k個(gè)訓(xùn)練樣本點(diǎn)中出現(xiàn)次數(shù)最多的類(lèi)別。

6）根據(jù)分類(lèi)結(jié)果，評(píng)價(jià)其查全率R、查準(zhǔn)率P、F1宏值以及分類(lèi)精度，判斷分類(lèi)效果是否達(dá)最好，若是，則結(jié)束；若否，返回步驟2）對(duì)k值進(jìn)行調(diào)整。

圖1 算法流程圖

3.2 實(shí)驗(yàn)結(jié)果及分析

實(shí)驗(yàn)采用MATLAB R2010a軟件進(jìn)行仿真，在Intel（R）Celeron（R）CPU 2.60GHz，2 GB內(nèi)存，Windows 7系統(tǒng)的計(jì)算機(jī)上運(yùn)行。采用3組數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)來(lái)驗(yàn)證算法分類(lèi)的有效性，3組數(shù)據(jù)集來(lái)自用于機(jī)器學(xué)習(xí)的UCI數(shù)據(jù)庫(kù)，表1給出了3組數(shù)據(jù)集的基本信息。

表1 實(shí)驗(yàn)用到的UCI數(shù)據(jù)集

對(duì)分類(lèi)算法進(jìn)行評(píng)價(jià)指標(biāo)分為宏平均指標(biāo)和微平均指標(biāo)，宏平均指標(biāo)體現(xiàn)的是對(duì)類(lèi)平均情況的評(píng)價(jià)，微平均則更加注重對(duì)樣本平均情況的評(píng)價(jià)。為了對(duì)比本文算法和傳統(tǒng)KNN算法的性能，采用分類(lèi)性能評(píng)價(jià)指標(biāo)為宏平均查全率(R)、宏平均查準(zhǔn)率(P )和F1測(cè)量值，同時(shí)分類(lèi)精度(C)也是評(píng)價(jià)分類(lèi)方法的重要指標(biāo)。

查全率公式為

式中：A表示分類(lèi)正確的樣本數(shù)，B表示測(cè)試樣本的總數(shù)。

在實(shí)驗(yàn)中本文選擇數(shù)據(jù)集的1／3作為訓(xùn)練樣本，數(shù)據(jù)集的2／3作為測(cè)試樣本。在k＝5時(shí)，實(shí)驗(yàn)結(jié)果如表2所示；在k＝8時(shí)實(shí)驗(yàn)結(jié)果如表3所示。

表2 k＝5時(shí)3組UCI數(shù)據(jù)集實(shí)驗(yàn)對(duì)比結(jié)果

表3 k＝8時(shí)3組UCI數(shù)據(jù)集實(shí)驗(yàn)對(duì)比結(jié)果

從表2中可以看出，當(dāng)k＝5時(shí)，在Iris數(shù)據(jù)集上，改進(jìn)算法的查全率、查準(zhǔn)率和F1值都增加約2%。在Haberman數(shù)據(jù)集上，改進(jìn)算法的查全率增加了2.3%、但是在查準(zhǔn)率和F1值上低于傳統(tǒng)的KNN算法。在Pima-India diabetes數(shù)據(jù)集上，相比于傳統(tǒng)算法查全率增加了4.3%，查準(zhǔn)率增加了7.8%，F(xiàn)1值增加了8%。從表3的實(shí)驗(yàn)對(duì)比結(jié)果容易得出，當(dāng)k＝8時(shí)，在Iris數(shù)據(jù)集上，改進(jìn)算法的查全率增加了2.5%、查準(zhǔn)率增加了3.1%、F1值增加了3.1%。在Haberman數(shù)據(jù)集上，改進(jìn)算法的查全率上增加了9.2%、查準(zhǔn)率和F1值分別增加了5.2%和5.9%。在Pima-India diabetes數(shù)據(jù)集上，相比于傳統(tǒng)算法，查全率增加了2.8%，查準(zhǔn)率增加了4.7%，F(xiàn)1值增加了4.5%。

通過(guò)分析表2、3可知，當(dāng)k＝5時(shí)，除在Haber-man數(shù)據(jù)集上的查準(zhǔn)率和F1值低于傳統(tǒng)KNN算法，在其他數(shù)據(jù)集上改進(jìn)的KNN算法的各項(xiàng)指標(biāo)均高于傳統(tǒng)的KNN算法。而當(dāng)k＝8時(shí)，改進(jìn)的KNN算法的各項(xiàng)指標(biāo)均明顯優(yōu)于傳統(tǒng)的KNN算法

分類(lèi)精度也是評(píng)價(jià)分類(lèi)效果的重要指標(biāo)，k的取值對(duì)分類(lèi)精度的影響非常明顯，k的取值過(guò)小，從訓(xùn)練樣本中得到信息相對(duì)較小，分類(lèi)精度就會(huì)下降；但是k也不能過(guò)大，這是因?yàn)檫x擇了太多的近鄰樣本，對(duì)從訓(xùn)練樣本中得到的分類(lèi)信息造成大的干擾。因此在選取k值的時(shí)候，就不得不做出某種折中。

為了說(shuō)明k值對(duì)分類(lèi)精度造成的影響，本文選取k＝3、5、8、10、12、15時(shí)，在3組UCI數(shù)據(jù)集上進(jìn)行測(cè)試，得到分類(lèi)精度隨k值變化曲線。Iris數(shù)據(jù)集的分類(lèi)準(zhǔn)確度隨k值得變化曲線如圖2所示。Haberman數(shù)據(jù)集的分類(lèi)準(zhǔn)確度隨k值得變化曲線如圖3所示。Pima-India diabetes數(shù)據(jù)集的分類(lèi)準(zhǔn)確度隨k值得變化曲線如圖4所示。

圖2 Iris數(shù)據(jù)集分類(lèi)精度隨k值變化曲線

圖3 Haberman數(shù)據(jù)集分類(lèi)精度隨k值變化曲線

圖4 Pima-India diabetes數(shù)據(jù)集分類(lèi)精度隨k值變化曲線

分析圖2～4可知，分類(lèi)精度隨著k值的不同而發(fā)生變化，改進(jìn)的算法和傳統(tǒng)的算法在分類(lèi)精度達(dá)到最大時(shí)的k值并不相同，對(duì)不同的數(shù)據(jù)集分類(lèi)精度達(dá)到最大時(shí)k值也可能不相同，Haberman數(shù)據(jù)集上在k＝3、5時(shí)改進(jìn)的KNN算法分類(lèi)精度低于傳統(tǒng)的KNN算法，在k取其他值時(shí)分類(lèi)精度明顯高于傳統(tǒng)算法，在Iris和Pima-India diabetes數(shù)據(jù)集上分類(lèi)精度明顯得到提高。

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

介紹了基于卡方距離的改進(jìn)KNN算法，用特征權(quán)重調(diào)整系數(shù)的卡方距離代替歐氏距離作為距離度量，克服了歐氏距離對(duì)每個(gè)特征量賦予相同權(quán)重的缺點(diǎn)。通過(guò)MATLAB仿真分析驗(yàn)證了改進(jìn)算法在查全率、查準(zhǔn)率、F1值以及分類(lèi)精度上得到了提高，盡管k值沒(méi)有一個(gè)統(tǒng)一的確定方法，但是在相同k值的條件下，改進(jìn)KNN算法的分類(lèi)效果明顯高于傳統(tǒng)的KNN算法。

［1］奉國(guó)和.自動(dòng)文本分類(lèi)技術(shù)研究［J］.情報(bào)雜志，2004，2（4）：108-111.

［2］COVER TM，HARTP E.Nearest neighbor pattern classifi-cation［J］.IEEE Transactions on Information Theory，1967，13（1）：21-27.

［3］LI J.TKNN：an improved KNN algorithm based on tree structure［C］//Seventh International IEEE Conference on Computational Intelligence and Security.Sanya，China，2011：1390-1394.

［4］彭凱，汪偉，楊煜普.基于余弦距離度量學(xué)習(xí)的偽K近鄰文本分類(lèi)算法［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2013，34（6）：2200-2203.

［5］LIM H.An improve KNN learning based Korean text classifi-er with heuristic information［C］//The 9thInternational Conference on Neural Information Processing.Singapore，2002：731-735

［6］桑應(yīng)賓.一種基于特征加權(quán)的K-Nearest-Neighbor算法［J］.海南大學(xué)學(xué)報(bào)，2008，26（4）：352-355.

［7］WEINBERGER K Q，SAUL L K.Distancemetric learning for large margin nearest neighbor classification［J］.The Journal of Machine Learning Research，2009（10）：207-244.

［8］KEDEM D，TYREE S，WEINBERGER K Q，et al.Non-lin-ear metric learning［C］//Neural Information Processing Systems Foundation.Lake Tahoe，USA，2012：2582-2590.

［9］蘇金樹(shù)，張博鋒，徐昕.基于機(jī)器學(xué)習(xí)的文本分類(lèi)技術(shù)研究進(jìn)展［J］.軟件學(xué)報(bào)，2006，17（9）：1848-1859.

［10］PELE O，WERMAN M.The quadratic-Chi histogram dis-tance family［C］//The 11thEuropean Conference on Com-puter Vision.Crete，Greece，2010：749-762.

An improved KNN algorithm based on Chi-square distancemeasure

XIE Hong，ZHAO Hongye
College of Information and Communication Engineering，Harbin Engineering University，Harbin 150001，China

The K-nearest neighbor（KNN）algorithm is one of the classification algorithms，and it isobvious in clas-sification effect，is simple and can be grasped easily.One of themost significant factorswhich determine the effect of the K-nearestneighbor classification is distancemeasure.Euclidean distance isusually considered as themeasure function of the K-nearest neighbor algorithm，it assigns the same weight to different characteristics of the samples，but different characteristic parameter has different influence on the accuracy of the classification results.This paper adopts Chi-square distance which canmore reflect the relative relationship between characteristics asmeasure func-tion of KNN algorithm and uses sensitivitymethod to compute the characteristic weight，so as to overcome the short-coming of Euclidean distance.The result of classification test shows evaluation indexes of the improved algorithm based on Chi-square distance are better than the traditional KNN algorithm.

K-nearestneighbor algorithm；Chi-square distance；distancemeasure；quadratic-form distance；Euclid-ean distance；sensitivitymethod

TP391.4

：A

：1009-671X（2015）01-010-05

10.3969／j.issn.1009-671X.201401002

http：//www.cnki.net／kcms／detail／23.1191.U.20150112.1433.001.htm l

2014-01-06.

日期：2015-01-12.

黑龍江省自然科學(xué)基金資助項(xiàng)目（F201339）.

趙洪野（1992-），男，碩士研究生；謝紅（1962-），女，教授，博士生導(dǎo)師.

謝紅，E-mail：xiehong＠hrbeu.edu.cn.