最近鄰分類算法KNN(K Nearest Neighbor) 是一種非參數(shù)的分類算法，在基于統(tǒng)計(jì)的模式識別中非常有效。對于未知和非正態(tài)分布可以獲得較高的分類準(zhǔn)確率，具有健壯性強(qiáng)、概念清晰等諸多優(yōu)點(diǎn)，在許多領(lǐng)域都有成功的應(yīng)用[1-4]。
    KNN算法的關(guān)鍵技術(shù)是搜索模式空間找出最接近未知樣本的K個訓(xùn)練樣本，未知樣本被分配到K個最近鄰者中最公共的類，其近鄰性用歐氏距離定義。KNN 方法最大的一個缺陷是對樣本庫容量的依賴性較強(qiáng)[5]，因此不適用于小樣本情況下的自動分類。此外在KNN分類算法中，確定待分類樣本類別需要計(jì)算其與訓(xùn)練樣本庫中所有樣本的相似度，計(jì)算量較大，甚至導(dǎo)致KNN算法在很多分類問題中失去實(shí)用性[6]。雖然眾多學(xué)者提出了多種KNN的改進(jìn)方法[7-10]，但這些方法都是建立在樣本選擇基礎(chǔ)上的，即以損失分類精度換取分類的速度。為此，學(xué)者Guvenir[11]提出一種基于特征投影的K最近鄰算法KNNFP(K Nearest Neighbor on Feature Projection)。該算法首先分別計(jì)算各維特征投影的K個最近鄰，然后根據(jù)投票準(zhǔn)則確定最終的樣本類別。由于各維特征值可以事先進(jìn)行排序，進(jìn)而可以進(jìn)行最優(yōu)搜索，使算法的效率大大提高。然而，因該算法事先假定每個特征對模式分類貢獻(xiàn)相同，降低了算法本身的分類精度。
    針對KNNFP算法存在的問題，本文提出一種基于特征加權(quán)的KNNFP改進(jìn)算法WKNNFP(Weights KNNFP)。該算法考慮各維特征對模式分類貢獻(xiàn)的不同，給不同的特征賦予不同的權(quán)值，提高重要特征的作用，從而提高了算法的分類精度。對不同實(shí)際數(shù)據(jù)進(jìn)行測試均顯示出改進(jìn)算法的優(yōu)良性能。由于故障診斷是基于某種屬性對系統(tǒng)狀態(tài)特征進(jìn)行分類歸屬故障模式的過程[12-15]，因此,本文最后將該算法應(yīng)用到軸承故障診斷領(lǐng)域，證明了該算法在工程應(yīng)用的有效性。
1 基于特征加權(quán)的KNNFP算法(WKNNFP)
1.1 算法概述
    在利用KNNFP算法對樣本進(jìn)行分類時，總是假設(shè)特征提取相當(dāng)完善，構(gòu)成模式矢量的特征是獨(dú)立且無冗余的。其特點(diǎn)是以每一個特征維度投影值來存儲,在訓(xùn)練階段，每一個樣本都是簡單地以在每一個特征上的投影值進(jìn)行計(jì)算。如果這個訓(xùn)練樣本其中的一個特征值不存在，則這個樣本在這個特征維度上沒有投影值存儲。為了對樣本進(jìn)行分類，首先在每一個特征維度上分別進(jìn)行預(yù)分類。這個預(yù)分類實(shí)質(zhì)上就是在這個單一特征上施行KNN算法。
    KNNFP算法認(rèn)為各維特征對分類的貢獻(xiàn)是相同的，而事實(shí)上，構(gòu)成樣本特征矢量的各維特征來自不同的傳感器，存在測量精度及可靠性等差異，樣本矢量的各維特征對分類的影響也不盡相同。因此，本文將探討一種改進(jìn)的K最近鄰特征投影算法(WKNNFP)。該算法考慮了各維特征對模式分類的不同貢獻(xiàn)，以求提高分類的精度。
    設(shè)一個給定的測試樣本為x，特征為t，定義在特征t上的最近鄰算法為K Bagging(t,x,k)，該函數(shù)計(jì)算測試樣本x在特征t投影值上最近的k個鄰居。然后對每一個類別進(jìn)行k次投票，因此每一特征維度上就有k次投票機(jī)會。測試樣本的類別由這些特征投影上的k次投票結(jié)果綜合決定。其中，在計(jì)算測試樣本x在特征t投影值上最近的k個鄰居時，需要根據(jù)特征屬性的不同分別進(jìn)行處理，對于數(shù)值型特征t，在其上的投影值分別設(shè)為u和v，則計(jì)算在特征t的距離公式為：

    WKNNFP與KNNFP算法的不同之處在于根據(jù)不同特征對分類貢獻(xiàn)的不同，WKNNFP給每一個特征以不同的權(quán)值，使得每一個特征上的投票結(jié)果對最終測試樣本類別的影響權(quán)重是不同的。
1.2 權(quán)值的確定
    采用ReliefF算法來確定特征的權(quán)值?；镜腞elief算法[16]是Kira和Rendell在1992年提出的，其要點(diǎn)是根據(jù)特征值在同類實(shí)例中以及相近的不同類實(shí)例中的區(qū)分能力來評價特征的相關(guān)度。Relief算法對數(shù)據(jù)類型沒有限制，可以較好地去除無關(guān)特征，但此算法僅適用于訓(xùn)練樣本是兩類的情況。1994年,Kononemko[17]擴(kuò)展了Relief算法，提出Relief F算法。RelliefF可以處理不完整數(shù)據(jù)、噪聲數(shù)據(jù)和多重類別問題。

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

    從圖1中可知，由于WKNNFP算法考慮了樣本特征對分類性能的貢獻(xiàn)程度,使得分類性能有所提高。得到的加權(quán)矩陣為w=[0.150 65 0.150 0 0.317 0 0.357 4]。從得到的加權(quán)矩陣可以看出,各維特征對分類的貢獻(xiàn)是不一樣的,第4維特征貢獻(xiàn)最大,而第2維特征貢獻(xiàn)最小。
2.2 對高維數(shù)據(jù)分類性能評價試驗(yàn)
    評價試驗(yàn)分別采用傳統(tǒng)KNNFP算法和改進(jìn)的WKNNFP算法對來自UCI的實(shí)際數(shù)據(jù)進(jìn)行分類,試驗(yàn)中使用的數(shù)據(jù)來自James Cook大學(xué)數(shù)學(xué)與統(tǒng)計(jì)中心。該數(shù)據(jù)的測量來自對意大利同一地區(qū)的三個不同品種的葡萄酒化學(xué)反應(yīng)的分析。葡萄酒實(shí)際數(shù)據(jù)共有178個記錄，每個記錄由13個數(shù)值特征描述，其中品種1包含59個數(shù)據(jù)，品種2包含71個數(shù)據(jù)，品種3包含48個數(shù)據(jù)。本次試驗(yàn)采用8折迭交叉驗(yàn)證法來比較傳統(tǒng)KNNFP算法和改進(jìn)的WKNNFP算法的分類性能。K值取1~10，分類結(jié)果如圖2所示。從試驗(yàn)結(jié)果可以看出，WKNNFP算法具有良好的分類性能。這說明本文提出的改進(jìn)算法對高維特征數(shù)據(jù)同樣是有效的。

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

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

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

3 WKNNFP算法在故障診斷中的應(yīng)用
    為了驗(yàn)證本文提出的改進(jìn)算法在工程應(yīng)用中的有效性，將本文算法應(yīng)用到機(jī)械設(shè)備故障診斷中。試驗(yàn)數(shù)據(jù)來自美國Case Western Reserve University電氣工程實(shí)驗(yàn)室。振動信號的收集來自安裝在感應(yīng)電機(jī)輸出軸支撐軸承上端機(jī)殼上的振動加速度傳感器。實(shí)驗(yàn)?zāi)M了滾動軸承的七種狀態(tài)：正常運(yùn)行狀態(tài)，外圈輕微故障，內(nèi)圈輕微故障，滾動體輕微故障，外圈嚴(yán)重故障，內(nèi)圈嚴(yán)重故障及滾動體嚴(yán)重故障。其中，輕微和嚴(yán)重故障的故障尺寸大小分別為0.18 mm和0.36 mm。
    試驗(yàn)中采用500個正常樣本、500個內(nèi)圈故障、500個外圈故障和500個滾動體故障樣本點(diǎn)作為樣本集，每個樣本含1 024個采樣點(diǎn)，利用Harr小波對每個樣本進(jìn)行五級分解，將每一級小波分解系數(shù)絕對值的平均值和方差作為特征，共10個特征。實(shí)驗(yàn)采用6折迭交叉驗(yàn)證法，試驗(yàn)結(jié)果如圖6所示。圖6中結(jié)果說明,利用本文改進(jìn)的WKNNFP算法對故障診斷是有效的，并且優(yōu)于傳統(tǒng)的KNNFP算法。

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

    針對傳統(tǒng)KNNFP分類算法中假設(shè)各維特征對分類的貢獻(xiàn)相同而導(dǎo)致分類性能下降這一不足，本文提出一種基于特征加權(quán)的KNNFP算法。通過實(shí)驗(yàn)證明，WKNNFP改進(jìn)算法利用ReleifF計(jì)算特征權(quán)重，考慮了各種特征對分類貢獻(xiàn)的大小，提高了重要特征的作用，使其對數(shù)據(jù)的分類性能大大提高。同時改進(jìn)算法還有助于分析各維特征對分類的貢獻(xiàn)程度，可以有效地進(jìn)行特征提取與優(yōu)選。本文的方法在實(shí)際應(yīng)用中非常方便，具有很好的推廣價值，不僅適合于軸承故障檢測，同樣也適用于其他分類應(yīng)用領(lǐng)域。
參考文獻(xiàn)
[1] 周小鵬,馮奇.基于最近鄰法的短時交通流預(yù)測[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)的最近鄰法則的異常檢測[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 與自動檢索的迭代近鄰法在自動分類中的應(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].中國圖像圖形學(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的軸承故障檢測方法[J].振動工程學(xué)報(bào),2008,21(2):203-208.
[13] 崔寶珍,王澤兵.小波分析-模糊聚類法用于滾動軸承故障診斷[J].振動、測試與診斷,2008,28(2):151-154.
[14] 魯卿,馮金富.一種基于WFCM 的故障診斷方法[J]. 振動、測試與診斷,2007,27(4):308-311.
[15] 黃晉英,畢世華.獨(dú)立分量分析在齒輪箱故障診斷中的應(yīng)用[J].振動、測試與診斷,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.