基于可拓距離的K近鄰算法

向長城

(湖北民族學(xué)院 理學(xué)院，湖北 恩施 445000)

將物理或抽象對象的集合按照對象相似性進(jìn)行分類的過程稱為聚類.聚類分析的算法可以分為劃分法(partitioning methods)、層次法(hierarchical methods)、基于密度的方法(density-based methods)、基于網(wǎng)格的方法(grid-based methods)、基于模型的方法(model-based methods).最近鄰方法(K nearest neighbor,KNN)[1,2]工作原理是首先找到被分類對象在訓(xùn)練數(shù)據(jù)集中的K個最近的鄰居,然后根據(jù)這些鄰居的分類屬性進(jìn)行投票,將得出的預(yù)測值賦給被分類對象的分類屬性.其優(yōu)點(diǎn)在于分類準(zhǔn)確率要高，無須事先知道屬性值分布,自從KNN方法被提出以來,就在故障診斷、數(shù)據(jù)聚內(nèi)、圖像識別、文本分類[3,4]等領(lǐng)域得到廣泛的應(yīng)用.

相似性度量是KNN中的關(guān)鍵部分,傳統(tǒng)上的相似性采用歐式距離等將各個屬性取值的差異通過距離函數(shù)來計(jì)算.但對于同一屬性內(nèi)取值的差異怎樣計(jì)算，歐式距離顯然是不妥的.而由我國學(xué)者蔡文教授發(fā)明的可拓學(xué)中用來定量描述事物關(guān)聯(lián)函數(shù)[5]，不僅可以描述同一屬性取值的差異，而且還可以提高聚類的準(zhǔn)確率.在關(guān)聯(lián)函數(shù)的基礎(chǔ)上，設(shè)計(jì)了可拓距離，主要是用屬性值與屬性值區(qū)間描述的.本文利用可拓距離與KNN算法的思想，提出了可拓K近鄰算法(extension K nearest neighbors,EKNN)，并通過故障診斷與UCI的Iris數(shù)據(jù)集進(jìn)了驗(yàn)證.

本文介紹了EKNN算法的設(shè)計(jì),給出了新方法在故障診斷的過程和與其他算法在一些通用數(shù)據(jù)庫分類準(zhǔn)確率的比較結(jié)果，并對結(jié)論進(jìn)行了分析與評價.

1 EKNN聚類算法

1.1 KNN算法

KNN基本思想是[3]:假定有n個類別為w1,w2,…,wn的樣本集合,每類有標(biāo)明類別的樣本Ni個(i= 1,2,…,n),設(shè)樣本的m個指標(biāo)有構(gòu)成一個m維特征空間,所有的樣本點(diǎn)在這個m維特征空間里都有惟一的點(diǎn)與它對應(yīng).則對任何一個待識別的樣本x=,其中ar(x)表示樣本x的第r個屬性，則兩樣本xi,xj間的距離定義為d(xi,xj),其中:

(1)

通過構(gòu)造距離公式(1),可以找到樣本x的k個近鄰.

又設(shè)這N個樣本中,來自w1類的樣本有N1個,來自w2類的樣本有N2個,…,來自wn類的樣本有Nn個.則對于一待分類的查詢實(shí)例x,使用KNN進(jìn)行分類的具體步驟是:

首先在訓(xùn)練樣本數(shù)據(jù)集中選出最接近x的K個實(shí)例,并用x1,x2,…,xk表示,設(shè)k1,k2,…,kn分別是k個近鄰中屬于類w1,w2,…,wn的樣本數(shù).

定義序偶對，x為訓(xùn)練數(shù)據(jù)集中的樣本點(diǎn),f(x)為一目標(biāo)函數(shù):f(x):R2→W,其中,W={w1,w2,…,wn},n為數(shù)據(jù)樣本分類的總數(shù)，wi對應(yīng)n維空間中的數(shù)據(jù)樣本劃分的第i種類型(i=1,2,…,n),則f(x)的計(jì)算表示為:

(2)

其中,若a=b,則σ(a,b)=1,否則σ(a,b)=0.

1.2 EKNN判別分析方法

可拓學(xué)是我國學(xué)者蔡文教授為解決不相容問題于1983年提出的一種方法，用形式化的語言對系統(tǒng)進(jìn)行的定性和定量描述，其基于區(qū)間和點(diǎn)的關(guān)聯(lián)函數(shù)的提出，為模式識別和模式分類提出了新的方法和思想.該算法首先按照樣本的指標(biāo)或者維數(shù)建立物元模型:

(3)

其中aj(x)為樣本物元Sx的第j個指標(biāo)Ij的值，j=1,2,…,m.

其次將N個向量xj(j=1,2,…,N)劃分為n個組w1,w2,…,wn,又設(shè)這N個組中,來自w1類的樣本有N1個,來自w2類的樣本有N2個,…,來自wn類的樣本有Nn個.并求每組的中心,使得相似性(或距離)指標(biāo)的價值函數(shù)(目標(biāo)函數(shù))達(dá)到最小.其函數(shù)采用式(1)歐式距離.

計(jì)算該類別的中心物元為建立:

(4)

(5)

圖1 一維可拓距離函數(shù)

圖2 180對傳感器數(shù)據(jù)

可拓距離函數(shù)定義為：

(6)

按照可拓距離值的大小從小到大對相應(yīng)類別的進(jìn)行排序，根據(jù)閾值σ選取最臨近的K個類別.如果所有EDi≤σ(i=1,2,…,n)只有K′個，并且K≥K′，則令K=K′.

根據(jù)式(2)計(jì)算f(x).那個類別的個數(shù)越多，則樣本點(diǎn)是該類.

2 實(shí)驗(yàn)驗(yàn)證

2.1 故障診斷

在本節(jié)用EKNN算法對故障進(jìn)行識別.其樣本數(shù)據(jù)集如圖2所示，采用只有兩個傳感器的系統(tǒng)，來描述五個故障狀態(tài)和正常狀態(tài).這6類數(shù)據(jù)分別代表了系統(tǒng)5個故障類型狀態(tài)和正常狀態(tài)，建立類別物元分別為:

其每個類別的中心物元通過計(jì)算可以得到：

通過采集測試物元并對其分類，建立測試物元分別為：

其中xi(i=1,2,…,6)為檢策樣本點(diǎn)，在圖3中用“☆”標(biāo)記.

以ND、FD1、FD2、FD3、FD4、FD5分別表示相關(guān)測試物元與正常類別、5個故障類別的可拓距離.根據(jù)式(6)和故障診斷的實(shí)際要求，取σ=3，K=3，其結(jié)果表1.

圖3 樣本數(shù)據(jù)和測試數(shù)據(jù)分布圖

表1測試物元可拓距離表

Tab.1 Testing matter element ED table

X1X2X3X4X5X6ND2.852.992.563.091.0153.10FD12.2530.4027.1514.5017.900.50FD212.2625.2022.6524.4014.9010.40FD318.4219.1728.9230.6721.1716.67FD428.902.757.7016.6512.1530.15FD524.127.272.4811.887.3725.37

表2 各類算法分類正確率比較表

表3 不同數(shù)據(jù)集分類成功率

在表1中，第一列所表示物元，其可拓距離閾值取為σ=3，且3>ND>FD1，所以K=2，由式(2)可知，樣本點(diǎn)x1屬于第一種故障類型.同理可知，x2,x3,x5,x6分別為第四類、第五類、正常和第二類故障類型，其中第四類樣本點(diǎn)，ND、FD1、FD2、FD3、FD4、FD5均大于3，此時可知該樣本點(diǎn)不屬于已有的類別.分析其原因可知，系統(tǒng)在原來基礎(chǔ)上已經(jīng)發(fā)生了新的變化，可能是系統(tǒng)新的故障類型出現(xiàn).此時需要對該類型故障進(jìn)行學(xué)習(xí)和記憶，并且作為一種新的故障類別加入到故障診斷數(shù)據(jù)庫中.

2.2 數(shù)據(jù)集聚類

Fisher的Iris植物樣本數(shù)據(jù)共有150個樣本，每個樣本均為4維sepal length,sepal width,petal length and petal width模式向量,代表植物的4種特征數(shù)據(jù).其中Iris-setosa、Iris-virginica，Iris-versicolor各50個樣本組成三類數(shù)據(jù).表2為分別用遺傳算法(SGA)[6]、模糊C-均值算法(FCM)[6]，免疫遺傳算法(IGA)[6]做了3次實(shí)驗(yàn)與EKNN算法的比較.

表3為數(shù)據(jù)集合IRIS與其他三個數(shù)據(jù)集DIABETES[7]、IONOSPHERE[7]、SONAR[7]分別用EKNN與AIS[8],AIS2[8]的比較.

通過表2可知，本文EKNN算法的分類準(zhǔn)確率較SGA，F(xiàn)CM，IGA算法更高，其中FCM準(zhǔn)確率最低，在表3中發(fā)現(xiàn)EKNN算法在性能上優(yōu)越于AIS,AIS2法，尤其在維數(shù)較大時，其準(zhǔn)確率更高.

3 結(jié)論

通過上述兩個實(shí)例說明，本文構(gòu)造的基于可拓距離的K近鄰算法在數(shù)據(jù)聚類和故障診斷方面分類準(zhǔn)確率高，對于算法運(yùn)算速度問題研究和改進(jìn)，是下一步的重點(diǎn)工作.

[1]Thierry Denoeux.A k-Nearest Neighbor Classification Rule Based on Dempster-Shafer Theory[J].IEEE Trans,on Systems Man and Cybernetics,1995,25(5):804-813.

[2]Lalla Meriem Zouhalm,Thierry Denoeux.An Evidence-Theoretic k2NN Rule with Parameter Optimization[J].IEEE Trans,on Systems Man and Cybernetics,1998,28(2):263-271.

[3] Pan J S,Qiao Y L,Sun S H.A fast K nearest neighbors classification algorithm[J].IEICE Trans Fundamentals,2004,E87-A(4):961-963.

[4]朱大奇,于盛林.基于DS證據(jù)理論的數(shù)據(jù)融合算法及其在電路故障診斷中的應(yīng)用[J].電子學(xué)報,2002,30(2):221-223.

[5]蔡文,楊春燕,林偉初.可拓工程方法[M].北京:科學(xué)出版社,2000:1-50.

[6]時念云,蔣紅芬.基于免疫單親遺傳和模糊C均值的聚類算法[J].控制工程,2006,13(2):158-160.

[7]Machine Learning Repository,Center for Marchine Learning and Intelligent Sytem[OL].[1993-03-08].http://archive.ics.uci.edu/ml/machire-learning-databases/iris.

[8]A Watkins and Timmis J. Artificial immune recognition system (airs):Revisions and renements[C]//Timmis and P.J.Benltey.1st International Conference on Articial Immune Systems.kent,UK:University of Kent at Canter Bury Printing Unit,2002:173-181.