基于特征加權的KNNFP改進算法及在故障診斷中的應用*

趙俊杰

(安徽財經大學 工商管理學院，安徽 蚌埠 233030)

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

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

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

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

1.1 算法概述

在利用KNNFP算法對樣本進行分類時，總是假設特征提取相當完善，構成模式矢量的特征是獨立且無冗余的。其特點是以每一個特征維度投影值來存儲,在訓練階段，每一個樣本都是簡單地以在每一個特征上的投影值進行計算。如果這個訓練樣本其中的一個特征值不存在，則這個樣本在這個特征維度上沒有投影值存儲。為了對樣本進行分類，首先在每一個特征維度上分別進行預分類。這個預分類實質上就是在這個單一特征上施行KNN算法。

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

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

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

WKNNFP與KNNFP算法的不同之處在于根據不同特征對分類貢獻的不同，WKNNFP給每一個特征以不同的權值，使得每一個特征上的投票結果對最終測試樣本類別的影響權重是不同的。

1.2 權值的確定

采用ReliefF算法來確定特征的權值。基本的Relief算法[16]是Kira和Rendell在 1992年提出的，其要點是根據特征值在同類實例中以及相近的不同類實例中的區(qū)分能力來評價特征的相關度。Relief算法對數據類型沒有限制，可以較好地去除無關特征，但此算法僅適用于訓練樣本是兩類的情況。1994年,Kononemko[17]擴展了Relief算法，提出Relief F算法。RelliefF可以處理不完整數據、噪聲數據和多重類別問題。

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

對于類屬型特征，表示為：

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

對于類屬型特征，表示為：

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

如此重復若干次，就可以得到特征集中每一個特征的權重。

1.3 WKNNFP算法流程

WKNNFP算法的具體實現如下：

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

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

(3)對于每一個類別c，分別計算它們的投票結果:

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

其中CNT(c,Bagging)函數計算特征 t的k個鄰居中類別為c的個數，W[t]為特征t的權值。

(4)判斷各類投票結果中的最大值，將最大值所對應類別作為測試樣本x的類別,并輸出測試樣本的類別cx。

2 WKNNFP算法分類性能評價試驗

為評價WKNNFP算法的分類性能，分別對各種具有不同屬性特征的數據集進行測試實驗，并與傳統(tǒng)的KNNFP算法分類性能進行比較。

2.1 對常用的IRIS四維數據分類性能評價試驗

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

圖1 WKNNFP與KNNFP算法對IRIS數據分類性能比較

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

2.2 對高維數據分類性能評價試驗

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

圖2 WKNNFP與KNNFP算法對葡萄酒數據分類結果比較

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

2.3 對具有混合特征的數據集分類性能評價試驗

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

圖3 WKNNFP算法得到的葡萄酒數據的各維特征值

圖4 WKNNFP與KNNFP算法對動物數據分類結果比較

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

3 WKNNFP算法在故障診斷中的應用

圖5 WKNNFP算法得到的動物數據的各維特征值

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

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

圖6 WKNNFP、KNNFP、KNN算法對軸承數據分類結果比較

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

圖7 軸承數據的各維特征值

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

[1]周小鵬,馮奇.基于最近鄰法的短時交通流預測[J].同濟大學學報(自然科學版),2006,30(10):1494-1497.

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

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

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

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

[6]王曉曄,王正歐.K-最近鄰分類技術的改進算法[J].電子信息學報,2005,27(3):487-491.

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

[8]姜文瀚,周曉飛.基于樣本選擇的最近鄰凸包分類器[J].中國圖像圖形學報,2008,13(1):109-113.

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

[10]王煜,張明.用于文本分類的改進KNN算法[J].計算機工程與應用,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的軸承故障檢測方法[J].振動工程學報,2008,21(2):203-208.

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

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

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

[16]李潔,高新波,焦李成.基于特征加權的模糊聚類新算法[J].電子學報,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.