趙俊杰

(安徽財(cái)經(jīng)大學(xué) 工商管理學(xué)院，安徽 蚌埠 233030)

最近鄰分類算法KNN(K Nearest Neighbor)是一種非參數(shù)的分類算法，在基于統(tǒng)計(jì)的模式識(shí)別中非常有效。對(duì)于未知和非正態(tài)分布可以獲得較高的分類準(zhǔn)確率，具有健壯性強(qiáng)、概念清晰等諸多優(yōu)點(diǎn)，在許多領(lǐng)域都有成功的應(yīng)用[1-4]。

KNN算法的關(guān)鍵技術(shù)是搜索模式空間找出最接近未知樣本的K個(gè)訓(xùn)練樣本，未知樣本被分配到K個(gè)最近鄰者中最公共的類，其近鄰性用歐氏距離定義。KNN方法最大的一個(gè)缺陷是對(duì)樣本庫(kù)容量的依賴性較強(qiáng)[5]，因此不適用于小樣本情況下的自動(dòng)分類。此外在KNN分類算法中，確定待分類樣本類別需要計(jì)算其與訓(xùn)練樣本庫(kù)中所有樣本的相似度，計(jì)算量較大，甚至導(dǎo)致KNN算法在很多分類問(wèn)題中失去實(shí)用性[6]。雖然眾多學(xué)者提出了多種KNN的改進(jìn)方法[7-10]，但這些方法都是建立在樣本選擇基礎(chǔ)上的，即以損失分類精度換取分類的速度。為此，學(xué)者Guvenir[11]提出一種基于特征投影的K最近鄰算法 KNNFP(K Nearest Neighbor on Feature Projection)。該算法首先分別計(jì)算各維特征投影的K個(gè)最近鄰，然后根據(jù)投票準(zhǔn)則確定最終的樣本類別。由于各維特征值可以事先進(jìn)行排序，進(jìn)而可以進(jìn)行最優(yōu)搜索，使算法的效率大大提高。然而，因該算法事先假定每個(gè)特征對(duì)模式分類貢獻(xiàn)相同，降低了算法本身的分類精度。

針對(duì)KNNFP算法存在的問(wèn)題，本文提出一種基于特征加權(quán)的KNNFP改進(jìn)算法WKNNFP(Weights KNNFP)。該算法考慮各維特征對(duì)模式分類貢獻(xiàn)的不同，給不同的特征賦予不同的權(quán)值，提高重要特征的作用，從而提高了算法的分類精度。對(duì)不同實(shí)際數(shù)據(jù)進(jìn)行測(cè)試均顯示出改進(jìn)算法的優(yōu)良性能。由于故障診斷是基于某種屬性對(duì)系統(tǒng)狀態(tài)特征進(jìn)行分類歸屬故障模式的過(guò)程[12-15]，因此,本文最后將該算法應(yīng)用到軸承故障診斷領(lǐng)域，證明了該算法在工程應(yīng)用的有效性。

1 基于特征加權(quán)的KNNFP算法(WKNNFP)

1.1 算法概述

在利用KNNFP算法對(duì)樣本進(jìn)行分類時(shí)，總是假設(shè)特征提取相當(dāng)完善，構(gòu)成模式矢量的特征是獨(dú)立且無(wú)冗余的。其特點(diǎn)是以每一個(gè)特征維度投影值來(lái)存儲(chǔ),在訓(xùn)練階段，每一個(gè)樣本都是簡(jiǎn)單地以在每一個(gè)特征上的投影值進(jìn)行計(jì)算。如果這個(gè)訓(xùn)練樣本其中的一個(gè)特征值不存在，則這個(gè)樣本在這個(gè)特征維度上沒(méi)有投影值存儲(chǔ)。為了對(duì)樣本進(jìn)行分類，首先在每一個(gè)特征維度上分別進(jìn)行預(yù)分類。這個(gè)預(yù)分類實(shí)質(zhì)上就是在這個(gè)單一特征上施行KNN算法。

KNNFP算法認(rèn)為各維特征對(duì)分類的貢獻(xiàn)是相同的，而事實(shí)上，構(gòu)成樣本特征矢量的各維特征來(lái)自不同的傳感器，存在測(cè)量精度及可靠性等差異，樣本矢量的各維特征對(duì)分類的影響也不盡相同。因此，本文將探討一種改進(jìn)的K最近鄰特征投影算法(WKNNFP)。該算法考慮了各維特征對(duì)模式分類的不同貢獻(xiàn)，以求提高分類的精度。

設(shè)一個(gè)給定的測(cè)試樣本為 x，特征為 t，定義在特征t上的最近鄰算法為K Bagging(t,x,k)，該函數(shù)計(jì)算測(cè)試樣本x在特征t投影值上最近的k個(gè)鄰居。然后對(duì)每一個(gè)類別進(jìn)行k次投票，因此每一特征維度上就有k次投票機(jī)會(huì)。測(cè)試樣本的類別由這些特征投影上的k次投票結(jié)果綜合決定。其中，在計(jì)算測(cè)試樣本x在特征t投影值上最近的k個(gè)鄰居時(shí)，需要根據(jù)特征屬性的不同分別進(jìn)行處理，對(duì)于數(shù)值型特征t，在其上的投影值分別設(shè)為u和v，則計(jì)算在特征t的距離公式為：

對(duì)于類屬型特征，則計(jì)算在特征f的距離公式為：

WKNNFP與KNNFP算法的不同之處在于根據(jù)不同特征對(duì)分類貢獻(xiàn)的不同，WKNNFP給每一個(gè)特征以不同的權(quán)值，使得每一個(gè)特征上的投票結(jié)果對(duì)最終測(cè)試樣本類別的影響權(quán)重是不同的。

1.2 權(quán)值的確定

采用ReliefF算法來(lái)確定特征的權(quán)值。基本的Relief算法[16]是Kira和Rendell在 1992年提出的，其要點(diǎn)是根據(jù)特征值在同類實(shí)例中以及相近的不同類實(shí)例中的區(qū)分能力來(lái)評(píng)價(jià)特征的相關(guān)度。Relief算法對(duì)數(shù)據(jù)類型沒(méi)有限制，可以較好地去除無(wú)關(guān)特征，但此算法僅適用于訓(xùn)練樣本是兩類的情況。1994年,Kononemko[17]擴(kuò)展了Relief算法，提出Relief F算法。RelliefF可以處理不完整數(shù)據(jù)、噪聲數(shù)據(jù)和多重類別問(wèn)題。

設(shè)X={x1,x2,…,xn}是待分類的對(duì)象全體，其中xi={xi1,xi2,…,xiN}表示第i個(gè)樣本的N個(gè)特征值。對(duì)于任意的一個(gè)樣本 xi，首先找出S個(gè)與xi同類的最近鄰樣本 yj(j=1,2,…,S)，然后在每一個(gè)與xi不同類的子集中找出S個(gè)最近鄰的樣本 mlj(j=1,2,…,S,l≠class(xj))。 設(shè) dis_t是N×1的矩陣，表示yj與xi在特征上的差異，對(duì)于數(shù)值型特征，表示為：

對(duì)于類屬型特征，表示為：

設(shè)dis_m是N×1的矩陣，表示 mlj與 xi在特征上的差異。對(duì)于數(shù)值型特征，表示為：

對(duì)于類屬型特征，表示為：

式中，P(l)為第l類出現(xiàn)的概率，可以用第 l類的樣本數(shù)比上數(shù)據(jù)集中的總數(shù)。若用w表示各維特征的權(quán)值(w是N×1的矩陣)，則ReliefF算法中特征權(quán)值w的更新公式如下：

如此重復(fù)若干次，就可以得到特征集中每一個(gè)特征的權(quán)重。

1.3 WKNNFP算法流程

WKNNFP算法的具體實(shí)現(xiàn)如下：

(1)輸入測(cè)試樣本x，并指定最近鄰個(gè)數(shù) k值。對(duì)于每一個(gè)類別c設(shè)置投票結(jié)果為零，V[c]=0。

(2)對(duì)于每一個(gè)特征 t，計(jì)算每一個(gè)特征投影的 k個(gè)鄰居，Bagging=kBagging(t,x,k)。

(3)對(duì)于每一個(gè)類別c，分別計(jì)算它們的投票結(jié)果:

V[c]=V[c]+W[t]×CNT(c,Bagging)。

其中CNT(c,Bagging)函數(shù)計(jì)算特征 t的k個(gè)鄰居中類別為c的個(gè)數(shù)，W[t]為特征t的權(quán)值。

(4)判斷各類投票結(jié)果中的最大值，將最大值所對(duì)應(yīng)類別作為測(cè)試樣本x的類別,并輸出測(cè)試樣本的類別cx。

2 WKNNFP算法分類性能評(píng)價(jià)試驗(yàn)

為評(píng)價(jià)WKNNFP算法的分類性能，分別對(duì)各種具有不同屬性特征的數(shù)據(jù)集進(jìn)行測(cè)試實(shí)驗(yàn)，并與傳統(tǒng)的KNNFP算法分類性能進(jìn)行比較。

2.1 對(duì)常用的IRIS四維數(shù)據(jù)分類性能評(píng)價(jià)試驗(yàn)

為了測(cè)試本文提出的算法對(duì)數(shù)值型數(shù)據(jù)的分類性能,采用著名的IRIS實(shí)際數(shù)據(jù)作為測(cè)試樣本集。IRIS數(shù)據(jù)由四維空間中的150個(gè)樣本點(diǎn)組成，每一個(gè)樣本的4個(gè)分量分別表示為 Petal Length、Petal Width、Sepal Length和Sepal Width。整個(gè)樣本集包含了3個(gè)IRIS種類：Setosa、Versicolor和Virginica，每類各有50個(gè)樣本。IRIS數(shù)據(jù)經(jīng)常被作為檢驗(yàn)分類算法性能的標(biāo)準(zhǔn)數(shù)據(jù)。本文分別采用傳統(tǒng)的KNNFP算法和改進(jìn)的WKNNFP算法對(duì)IRIS樣本進(jìn)行分類，測(cè)試兩種算法的誤分率，以比較它們的分類性能。本試驗(yàn)采用6折迭交叉驗(yàn)證法，即將整個(gè)數(shù)據(jù)集六等分得到6個(gè)子集，其中5個(gè)子集作為訓(xùn)練集，另1個(gè)子集作為測(cè)試集，這樣每一個(gè)樣本都能作為訓(xùn)練樣本5次，測(cè)試樣本1次。K值取1～10，分類結(jié)果如圖1所示。

圖1 WKNNFP與KNNFP算法對(duì)IRIS數(shù)據(jù)分類性能比較

從圖1中可知，由于WKNNFP算法考慮了樣本特征對(duì)分類性能的貢獻(xiàn)程度,使得分類性能有所提高。得到的加權(quán)矩陣為w=[0.150 65 0.150 0 0.317 0 0.357 4]。從得到的加權(quán)矩陣可以看出,各維特征對(duì)分類的貢獻(xiàn)是不一樣的,第4維特征貢獻(xiàn)最大,而第2維特征貢獻(xiàn)最小。

2.2 對(duì)高維數(shù)據(jù)分類性能評(píng)價(jià)試驗(yàn)

評(píng)價(jià)試驗(yàn)分別采用傳統(tǒng)KNNFP算法和改進(jìn)的WKNNFP算法對(duì)來(lái)自UCI的實(shí)際數(shù)據(jù)進(jìn)行分類,試驗(yàn)中使用的數(shù)據(jù)來(lái)自James Cook大學(xué)數(shù)學(xué)與統(tǒng)計(jì)中心。該數(shù)據(jù)的測(cè)量來(lái)自對(duì)意大利同一地區(qū)的三個(gè)不同品種的葡萄酒化學(xué)反應(yīng)的分析。葡萄酒實(shí)際數(shù)據(jù)共有178個(gè)記錄，每個(gè)記錄由13個(gè)數(shù)值特征描述，其中品種1包含59個(gè)數(shù)據(jù)，品種 2包含 71個(gè)數(shù)據(jù)，品種 3包含 48個(gè)數(shù)據(jù)。本次試驗(yàn)采用8折迭交叉驗(yàn)證法來(lái)比較傳統(tǒng)KNNFP算法和改進(jìn)的WKNNFP算法的分類性能。K值取1～10，分類結(jié)果如圖2所示。從試驗(yàn)結(jié)果可以看出，WKNNFP算法具有良好的分類性能。這說(shuō)明本文提出的改進(jìn)算法對(duì)高維特征數(shù)據(jù)同樣是有效的。

圖2 WKNNFP與KNNFP算法對(duì)葡萄酒數(shù)據(jù)分類結(jié)果比較

圖3為WKNNFP算法得到的各維特征的權(quán)值，從圖中可以看出，第2維和第8維特征的權(quán)值較小，說(shuō)明這兩個(gè)特征對(duì)分類起的作用較小。而第1維特征對(duì)分類的貢獻(xiàn)最大。對(duì)照實(shí)際數(shù)據(jù)發(fā)現(xiàn)在樣本的第1維特征上不同品種呈現(xiàn)不同的特征值，這也證明了新算法不僅提高了分類算法的性能，而且還可以用于模式識(shí)別中的特征提取和優(yōu)選。

2.3 對(duì)具有混合特征的數(shù)據(jù)集分類性能評(píng)價(jià)試驗(yàn)

在數(shù)據(jù)挖掘中，經(jīng)常會(huì)遇到數(shù)據(jù)的特征中既包含數(shù)值型特征，也包含類屬型特征的混合特征數(shù)據(jù)。本試驗(yàn)采用KNNFP算法和改進(jìn)的WKNNFP算法對(duì)實(shí)際的動(dòng)物園混合數(shù)據(jù)進(jìn)行分類，以評(píng)價(jià)兩種算法的分類性能。動(dòng)物園數(shù)據(jù)共有101個(gè)記錄，每一個(gè)記錄由15個(gè)類屬特征和1個(gè)數(shù)值特征描述。由于數(shù)據(jù)較少，因此本次試驗(yàn)采用3折迭交叉驗(yàn)證法，K值取 1～10，分類結(jié)果如圖4所示。從試驗(yàn)結(jié)果可以看出，WKNNFP算法具有良好的分類性能，這說(shuō)明本文提出的改進(jìn)算法對(duì)混合特征數(shù)據(jù)同樣是有效的。

圖3 WKNNFP算法得到的葡萄酒數(shù)據(jù)的各維特征值

圖4 WKNNFP與KNNFP算法對(duì)動(dòng)物數(shù)據(jù)分類結(jié)果比較

圖5為WKNNFP算法得到的各維類屬特征的權(quán)值，從圖中可以看出，第4維特征的權(quán)值最大。而第15維特征對(duì)應(yīng)的權(quán)值最小，對(duì)分類的貢獻(xiàn)最小。從試驗(yàn)中可以發(fā)現(xiàn)，取不同的K值，改進(jìn)的WKNNFP算法都要優(yōu)于傳統(tǒng)的KNNFP算法,而K值的選擇和分類精度之間卻沒(méi)有明顯的關(guān)系,因此需要根據(jù)具體的應(yīng)用做出優(yōu)化選擇。

3 WKNNFP算法在故障診斷中的應(yīng)用

圖5 WKNNFP算法得到的動(dòng)物數(shù)據(jù)的各維特征值

為了驗(yàn)證本文提出的改進(jìn)算法在工程應(yīng)用中的有效性，將本文算法應(yīng)用到機(jī)械設(shè)備故障診斷中。試驗(yàn)數(shù)據(jù)來(lái)自美國(guó)Case Western Reserve University電氣工程實(shí)驗(yàn)室。振動(dòng)信號(hào)的收集來(lái)自安裝在感應(yīng)電機(jī)輸出軸支撐軸承上端機(jī)殼上的振動(dòng)加速度傳感器。實(shí)驗(yàn)?zāi)M了滾動(dòng)軸承的七種狀態(tài)：正常運(yùn)行狀態(tài)，外圈輕微故障，內(nèi)圈輕微故障，滾動(dòng)體輕微故障，外圈嚴(yán)重故障，內(nèi)圈嚴(yán)重故障及滾動(dòng)體嚴(yán)重故障。其中，輕微和嚴(yán)重故障的故障尺寸大小分別為0.18 mm和0.36 mm。

試驗(yàn)中采用 500個(gè)正常樣本、500個(gè)內(nèi)圈故障、500個(gè)外圈故障和500個(gè)滾動(dòng)體故障樣本點(diǎn)作為樣本集，每個(gè)樣本含1 024個(gè)采樣點(diǎn)，利用Harr小波對(duì)每個(gè)樣本進(jìn)行五級(jí)分解，將每一級(jí)小波分解系數(shù)絕對(duì)值的平均值和方差作為特征，共10個(gè)特征。實(shí)驗(yàn)采用6折迭交叉驗(yàn)證法，試驗(yàn)結(jié)果如圖6所示。圖6中結(jié)果說(shuō)明,利用本文改進(jìn)的WKNNFP算法對(duì)故障診斷是有效的，并且優(yōu)于傳統(tǒng)的KNNFP算法。

圖6 WKNNFP、KNNFP、KNN算法對(duì)軸承數(shù)據(jù)分類結(jié)果比較

圖7為WKNNFP算法得到的各維數(shù)值特征的權(quán)值。從圖中可以看出，第5、6維特征的權(quán)值最大，特征空間中第5、6維特征是描述信號(hào)第3層小波分解的特征，正好對(duì)應(yīng)區(qū)分能力最大的本征頻譜區(qū)域，因此這兩維特征對(duì)分類的貢獻(xiàn)最大。這也說(shuō)明本文提出的方法可以實(shí)現(xiàn)故障診斷特征的優(yōu)選。

圖7 軸承數(shù)據(jù)的各維特征值

針對(duì)傳統(tǒng)KNNFP分類算法中假設(shè)各維特征對(duì)分類的貢獻(xiàn)相同而導(dǎo)致分類性能下降這一不足，本文提出一種基于特征加權(quán)的KNNFP算法。通過(guò)實(shí)驗(yàn)證明，WKNNFP改進(jìn)算法利用ReleifF計(jì)算特征權(quán)重，考慮了各種特征對(duì)分類貢獻(xiàn)的大小，提高了重要特征的作用，使其對(duì)數(shù)據(jù)的分類性能大大提高。同時(shí)改進(jìn)算法還有助于分析各維特征對(duì)分類的貢獻(xiàn)程度，可以有效地進(jìn)行特征提取與優(yōu)選。本文的方法在實(shí)際應(yīng)用中非常方便，具有很好的推廣價(jià)值，不僅適合于軸承故障檢測(cè)，同樣也適用于其他分類應(yīng)用領(lǐng)域。

[1]周小鵬,馮奇.基于最近鄰法的短時(shí)交通流預(yù)測(cè)[J].同濟(jì)大學(xué)學(xué)報(bào)(自然科學(xué)版),2006,30(10):1494-1497.

[2]孫發(fā)圣,肖懷鐵.基于K最近鄰的支持向量機(jī)快速訓(xùn)練算法[J].電光與控制,2008,15(6):44-47.

[3]聶方彥.基于PCA與改進(jìn)的最近鄰法則的異常檢測(cè)[J].計(jì)算機(jī)工程與設(shè)計(jì),2008,29(10):2502-2504.

[4]劉海博,郗亞輝.用于文本分類的快速KNN算法[J].河北大學(xué)學(xué)報(bào)(自然科學(xué)版),2008,28(3):322-326.

[5]楊建良,王勇成.基于KNN與自動(dòng)檢索的迭代近鄰法在自動(dòng)分類中的應(yīng)用[J].情報(bào)學(xué)報(bào),2004,23(2):137-141.

[6]王曉曄,王正歐.K-最近鄰分類技術(shù)的改進(jìn)算法[J].電子信息學(xué)報(bào),2005,27(3):487-491.

[7]周曉飛，姜文瀚.基于子空間樣本選擇的最近凸包分類器[J].計(jì)算機(jī)工程.2008,34(12):167-171.

[8]姜文瀚,周曉飛.基于樣本選擇的最近鄰?fù)拱诸惼鱗J].中國(guó)圖像圖形學(xué)報(bào),2008,13(1):109-113.

[9]李榮陸,胡運(yùn)發(fā).基于密度的KNN文本分類器訓(xùn)練樣本裁剪方法[J].計(jì)算機(jī)研究與發(fā)展,2004,41(4):539-545.

[10]王煜,張明.用于文本分類的改進(jìn)KNN算法[J].計(jì)算機(jī)工程與應(yīng)用,2007,43(13):159-165.

[11]AKKUS A,GUVENIR H K.Nearest neighbor classification on feature projections proceedings of the 13th international conference on machine learning[C].Lorenza Saitta,Bari,Italy,2003:12-19.

[12]陶新民,杜寶祥,徐勇.基于 HOS奇異值譜和 SVDD的軸承故障檢測(cè)方法[J].振動(dòng)工程學(xué)報(bào),2008,21(2):203-208.

[13]崔寶珍,王澤兵.小波分析-模糊聚類法用于滾動(dòng)軸承故障診斷[J].振動(dòng)、測(cè)試與診斷,2008,28(2):151-154.

[14]魯卿,馮金富.一種基于 WFCM 的故障診斷方法[J].振動(dòng)、測(cè)試與診斷,2007,27(4):308-311.

[15]黃晉英,畢世華.獨(dú)立分量分析在齒輪箱故障診斷中的應(yīng)用[J].振動(dòng)、測(cè)試與診斷,2008,28(2):126-130.

[16]李潔,高新波,焦李成.基于特征加權(quán)的模糊聚類新算法[J].電子學(xué)報(bào),2006,34(1):89-92.

[17]KONONENKO I.Estimating attributes analysis and extensions of relief[C].Proceedings of the 7th European Conference on Machine Learning.Berlin:Springer,1994,171-182.