最近鄰分類算法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ì)樣本庫容量的依賴性較強(qiáng)[5]，因此不適用于小樣本情況下的自動(dòng)分類。此外在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個(gè)最近鄰，然后根據(jù)投票準(zhǔn)則確定最終的樣本類別。由于各維特征值可以事先進(jìn)行排序，進(jìn)而可以進(jìn)行最優(yōu)搜索，使算法的效率大大提高。然而，因該算法事先假定每個(gè)特征對(duì)模式分類貢獻(xiàn)相同，降低了算法本身的分類精度。
    針對(duì)KNNFP算法存在的問題，本文提出一種基于特征加權(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)行分類歸屬故障模式的過程[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ú)立且無冗余的。其特點(diǎn)是以每一個(gè)特征維度投影值來存儲(chǔ),在訓(xùn)練階段，每一個(gè)樣本都是簡(jiǎn)單地以在每一個(gè)特征上的投影值進(jìn)行計(jì)算。如果這個(gè)訓(xùn)練樣本其中的一個(gè)特征值不存在，則這個(gè)樣本在這個(gè)特征維度上沒有投影值存儲(chǔ)。為了對(duì)樣本進(jìn)行分類，首先在每一個(gè)特征維度上分別進(jìn)行預(yù)分類。這個(gè)預(yù)分類實(shí)質(zhì)上就是在這個(gè)單一特征上施行KNN算法。
    KNNFP算法認(rèn)為各維特征對(duì)分類的貢獻(xiàn)是相同的，而事實(shí)上，構(gòu)成樣本特征矢量的各維特征來自不同的傳感器，存在測(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的距離公式為：

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

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算法考慮了樣本特征對(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ì)來自UCI的實(shí)際數(shù)據(jù)進(jìn)行分類,試驗(yàn)中使用的數(shù)據(jù)來自James Cook大學(xué)數(shù)學(xué)與統(tǒng)計(jì)中心。該數(shù)據(jù)的測(cè)量來自對(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)證法來比較傳統(tǒng)KNNFP算法和改進(jìn)的WKNNFP算法的分類性能。K值取1~10，分類結(jié)果如圖2所示。從試驗(yàn)結(jié)果可以看出，WKNNFP算法具有良好的分類性能。這說明本文提出的改進(jìn)算法對(duì)高維特征數(shù)據(jù)同樣是有效的。

    圖3為WKNNFP算法得到的各維特征的權(quán)值，從圖中可以看出，第2維和第8維特征的權(quán)值較小，說明這兩個(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算法具有良好的分類性能，這說明本文提出的改進(jìn)算法對(duì)混合特征數(shù)據(jù)同樣是有效的。

    圖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值的選擇和分類精度之間卻沒有明顯的關(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)室。振動(dòng)信號(hào)的收集來自安裝在感應(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é)果說明,利用本文改進(jìn)的WKNNFP算法對(duì)故障診斷是有效的，并且優(yōu)于傳統(tǒng)的KNNFP算法。

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

    針對(duì)傳統(tǒng)KNNFP分類算法中假設(shè)各維特征對(duì)分類的貢獻(xiàn)相同而導(dǎo)致分類性能下降這一不足，本文提出一種基于特征加權(quán)的KNNFP算法。通過實(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)域。
參考文獻(xiàn)
[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].中國圖像圖形學(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.