周承如 熊太松 吳宏偉 楊園園 宋 君

（1.江蘇大學(xué)計算機科學(xué)與通信工程學(xué)院 鎮(zhèn)江 212013）（2.成都信息工程大學(xué)計算機學(xué)院 成都 610225）

1 引言

隨著信息和網(wǎng)絡(luò)技術(shù)的發(fā)展，日常生活中產(chǎn)生的數(shù)據(jù)呈現(xiàn)爆炸式增長的趨勢，因此人們迫切需要一種有效的工具來對數(shù)據(jù)進行挖掘與處理。K-近鄰分類（KNN）算法因其簡潔有效性被看作數(shù)據(jù)挖掘領(lǐng)域十大經(jīng)典算法之一［1］，被廣泛運用于人臉識別、圖像分類、計算機視覺和信息檢索等方面［2～3］。許多提出的基于KNN 的分類算法雖然思想簡單易于實現(xiàn)［4］，但其分類性能依然受到三個主要問題的約束：1）KNN 算法所選擇的所有近鄰點具有相同權(quán)重，導(dǎo)致不同近鄰點對分類只起到了相同作用，降低了KNN算法的分類性能［5］。2）k值敏感性問題［6］，分類性能容易受到近鄰個數(shù)k 值大小的影響，近鄰個數(shù)k 微小的變化都會使分類獲得不同結(jié)果。3）簡單的最大投票原則［7］作為決策函數(shù)不能弱化近鄰域中噪聲點存在帶來的影響，相反這些噪聲點與有效近鄰點具有相同分類貢獻。

針對上述存在的問題，學(xué)者們在KNN 算法的基礎(chǔ)上進行了大量的研究，同時提出許多改進算法。文獻［8］提出了一種基于樣本間距離加權(quán)的KNN 分類算法（The Distance-Weighted K Nearest Neighbor Rule，WKNN），在WKNN 中與測試樣本距離不同的近鄰可以獲得一個自適應(yīng)的權(quán)重，距離更近的近鄰對于分類結(jié)果起到的作用更大，提高了算法的分類性能，然而WKNN 依然受到k值敏感性的影響。文獻［9］提出了基于局部均值的KNN 分類（A Local Mean Based Nonparametric Classifier，LMKNN）算法，LMKNN 使用傳統(tǒng)近鄰的k 個均值作為新的近鄰，可以獲得更多的樣本間信息來為分類提供幫助，并且減少近鄰域中出現(xiàn)噪聲點的可能性，然而該算法中不同局部均值具有相同的權(quán)重?；趨f(xié)作表示［10］（Collaborative Representation Classifier，CRC）的分類是一種有代表性的低計算復(fù)雜度的分類方法，它有著特定的封閉解，對分類有著一定幫助。但是CRC 的分類性能容易受到噪聲點和異類相似點的影響，在實際場景中的分類易受到干擾。

本文提出了基于局部多均值協(xié)作表示的K-近質(zhì)心近鄰分類（LMRKNCN）算法，LMRKNCN 結(jié)合了局部均值定理、質(zhì)心準則和協(xié)作表示方法，旨在改善KNN 算法中存在的一些不足，同時提高分類性能。通過在一些UCI 數(shù)據(jù)集上與其他較新的算法進行實驗比較，驗證了LMRKNCN 的有效性與魯棒性。

2 相關(guān)工作

首先統(tǒng)一介紹本文中使用的符號，對于一個訓(xùn)練樣本集X，其中包含了L 種類別和共n 個訓(xùn)練樣本，訓(xùn)練集特征維度為d，可表示為X=［X1，X2，…，XL］∈Rd×n。訓(xùn)練集中所有類別標簽表示為C=｛c1，c2，…，cL｝，其中第i 類訓(xùn)練樣本子集包含m 個樣本可以表示為任意一個訓(xùn)練樣本的類別標簽是ci∈C，測試樣本表示為y。

2.1 K-近鄰分類算法

在KNN 算法中，對于一個測試樣本y，y的類別標簽c判別過程如下。

根據(jù)式（1）歐幾里得距離計算y 與全部樣本X的距離。

選取距離最小的k 個訓(xùn)練樣本作為測試樣本y的近鄰。查找k 個近鄰中每類樣本的個數(shù)，將擁有近鄰個數(shù)最多的類別標簽分配給待測點y。

因此K-近鄰算法的基本思想是根據(jù)距離大小找出關(guān)于待測樣本點的k 個近鄰，并遵循最大投票原則分配類別標簽給待測點。

2.2 局部均值原則［9］

對于一個有k 個點的點集X=［x1，x2，…，xk］，這些點的k個局部均值求解如下：

使用局部均值作為近鄰可以反映出樣本間的相似性，獲得更多有效的樣本信息，同時減少了近鄰區(qū)域中噪聲點存在的概率，這些優(yōu)勢在小樣本環(huán)境下更為明顯。一些基于局部均值的分類算法［11］已經(jīng)被證明具有優(yōu)秀的分類性能。

2.3 近質(zhì)心近鄰原則［12］

對于一個待測點y，其近質(zhì)心近鄰點必須滿足兩個原則。距離最近原則：近質(zhì)心近鄰點應(yīng)盡可能地靠近y，與y具有相似性。空間對稱原則：近質(zhì)心近鄰點在空間上應(yīng)盡可能地均勻分布在y 的周圍。

給定一組測試點x={x1,x2,…,xp}，其質(zhì)心點計算方法如下：

因此通過如下兩個迭代循環(huán)可以找到關(guān)于待測點的k個近質(zhì)心近鄰點。

1）找出y的第一個近質(zhì)心近鄰點，該點也是KNN算法中的最近近鄰點。

2）找出y 的第i 個近質(zhì)心近鄰點（i≥2）：計算訓(xùn)練集X中的每個點與之前已經(jīng)找出的i-1個近質(zhì)心近鄰點,…,，然后計算這些近質(zhì)心點到待測點y 的距離，選擇其中距離最小的近質(zhì)心點所對應(yīng)的X中的點為。

使用近質(zhì)心近鄰能夠獲得樣本間的空間分布信息，在基于空間距離的分類決策方法中，能夠提高分類的準確性。

2.4 協(xié)作表示分類

其中常用的協(xié)作表示模型有：

其中S是協(xié)作表示系數(shù)，λ是正則化參數(shù)。對式（4）求關(guān)于系數(shù)向量S的偏導(dǎo)，可以得到最優(yōu)系數(shù)解為

其中I是單位矩陣。使用基于測試樣本與每類訓(xùn)練樣本的殘差大小作為分類決策函數(shù)，可表示為

將最小類別殘差對應(yīng)的標簽分配給測試樣本。

3 LMRKNCN算法

3.1 LMRKNCN基本思想

LMRKNCN 結(jié)合了局部均值和近質(zhì)心近鄰原則，首先求出每類訓(xùn)練樣本關(guān)于測試樣本的k 個近質(zhì)心近鄰，再計算k 個近質(zhì)心近鄰的k 個局部多均值近鄰點。同時為了克服基于KNN 算法中不同貢獻值的近鄰卻具有相同權(quán)重和簡單的最大投票原則問題，LMRKNCN 繼續(xù)求出k 個局部均值近鄰點所對應(yīng)的協(xié)作表示系數(shù)，協(xié)作表示系數(shù)相當(dāng)于賦予近鄰們不同的權(quán)重。最后基于樣本間的殘差大小作為該算法的分類決策函數(shù)，分別求出測試樣本與每類訓(xùn)練樣本中k 個局部多均值近鄰點協(xié)作表示后樣本的殘差，將最小殘差所對應(yīng)的類別標簽分配給測試樣本。

3.2 LMRKNCN算法介紹

給定一個測試樣本y，首先根據(jù)式（1）使用歐氏距離法計算每類訓(xùn)練樣本與測試樣本的距離。接著找出每類中距離測試樣本最近的訓(xùn)練樣本作為第一個近質(zhì)心近鄰點，也是傳統(tǒng)KNN 算法中的第一個近鄰點。根據(jù)近質(zhì)心近鄰原則依次找出剩余k-1 個近質(zhì)心近鄰。再通過局部均值原則式（2）計算出這k個近質(zhì)心近鄰的k個局部多均值。接著由式（5）求解所得k 個局部均值質(zhì)心點對應(yīng)的協(xié)作表示系數(shù)，用k 個近質(zhì)心局部均值點協(xié)作表示測試樣本。計算測試樣本y與每類k個近質(zhì)心局部均值點協(xié)作表示后樣本的殘差，將最小殘差所對應(yīng)的類別標簽分配給測試樣本y。LMRKNCN 算法具體步驟將以Matlab偽代碼的形式進行說明。

3.3 LMRKNCN理論分析

LMKNN 與LMRKNCN 都是基于樣本間的距離作為決策函數(shù)，然而兩種算法所選擇的近鄰點對于分類結(jié)果起到的作用是不同。LMKNN中近鄰點主要是k個局部均值點，根據(jù)式（2）求出測試樣本y關(guān)于類別cj的k 個局部均值記作：…,]。測試樣本y 與類cj中第i 個局部均值的歐氏距離為d(y,)。文獻［13］對距離平方求解關(guān)于近鄰的導(dǎo)數(shù)，求導(dǎo)結(jié)果表示了每個近鄰的權(quán)重，也就是其對于分類的貢獻比例。

LMRKNCN 使用測試樣本y 與每類k 個近質(zhì)心局部均值點協(xié)作表示后的殘差作為分類決策函數(shù)：

不同近質(zhì)心局部均值點對于分類應(yīng)該有著不同的貢獻，在基于協(xié)作表示分類的方法中使用樣本殘差作為分類決策函數(shù)，可以直觀地表示樣本對分類起到的貢獻。對式（10）求導(dǎo)，也就是求殘差Ej關(guān)于近質(zhì)心局部均值的偏導(dǎo)，求導(dǎo)過程如下：

根據(jù)式（10）求導(dǎo)的結(jié)果可知，在基于樣本殘差的分類決策函數(shù)中，每個近質(zhì)心局部均值點對應(yīng)的協(xié)作表示系數(shù)也是不同。如果使用簡單的最大投票原則作為分類依據(jù)，那么不同的近質(zhì)心局部均值點對于分類只起到了相同貢獻。 因此LMRKNCN 給不同的局部均值匹配一個協(xié)作表示系數(shù)作為權(quán)重，可以提高分類性能。

4 實驗結(jié)果與分析

使用Matlab（實驗矩陣）軟件實現(xiàn)了LMRKNCN算法模型。為了驗證LMRKNCN 的分類有效性，將其與KNN，LMKNN，KNCN 和LMRKNCN 相關(guān)對比算法在6組UCI［14］真實數(shù)據(jù)集上進行實驗分析。表1詳細介紹了數(shù)據(jù)集的相關(guān)屬性。

表1 數(shù)據(jù)集描述

為了客觀地研究所提LMRKNCN 算法的分類性能，對每一個數(shù)據(jù)集進行10 次拆分，所有的樣本每次都會被隨機拆分成為測試樣本和訓(xùn)練樣本，以此來確保實驗的分類效率和分類結(jié)果的可參考價值。通過改變所選取近鄰的個數(shù)k 和可變參數(shù)λ，來研究LMRKNCN 與其他對比算法的分類錯誤率，旨在證明LMRKNCN 能夠減少樣本中噪聲點存在帶來的影響。近鄰個數(shù)k 的變化范圍是從1～15 并且步長為1，可變參數(shù)λ的數(shù)值范圍設(shè)為λ∈｛0.001，0.01，0.1，1，10｝。在所有數(shù)據(jù)集上運行10次，取10次實驗的平均分類誤差作為最終的實驗結(jié)果。

4.1 實驗結(jié)果與分析

圖1展示了所有方法在不同的k值下的分類錯誤率。

圖1 數(shù)據(jù)集上的分類錯誤率

此外，為了更直觀地展示LMRKNCN 與其余對比算法的分類性能，表2 列出了LMRKNCN 以及對比方法在真實數(shù)據(jù)集上的最小錯誤率和所對應(yīng)的k值與對應(yīng)的實驗偏差。在每個真實數(shù)據(jù)集上的最優(yōu)分類結(jié)果以及對應(yīng)的分類算法被用黑色加粗加斜字體標注出來。每個數(shù)據(jù)集上的最優(yōu)分類結(jié)果以及對應(yīng)的分類算法被用黑色加粗加斜字體標注出來。

分析圖中變化的分類錯誤率曲線可知：

1）在k值較小時，增大k值，LMRKNCN 的分類錯誤率呈現(xiàn)快速下降，隨后趨于穩(wěn)定的趨勢。而其余對比算法的錯誤率隨著k 值增大呈現(xiàn)無序變化或逐漸增大的規(guī)律。

2）LMRKNCN 的最低分類錯誤率通常在k 值較大時獲得，而其余對比算法在k 值較小或k 為1時獲得最低分類錯誤率。說明LMRKNCN 能夠抑制k值敏感性問題。

3）LMRKNCN與對比算法相比，在實驗所取的k 值范圍內(nèi)能夠獲得最低的分類錯誤率，對應(yīng)著最佳的分類性能。

從表2 可知，LMRKNCN 的分類性能明顯優(yōu)于其余對比分類算法，尤其是在小樣本數(shù)據(jù)集上。并且LMRKNCN最優(yōu)的分類性能通常在k值較大時取得。又進一步證明LMRKNCN 對于模式識別具有較好的有效性，同時減少了噪聲點給分類性能帶來的影響。

表2 最佳分類結(jié)果（均值±標準差%，對應(yīng)的k值）

4.2 時間復(fù)雜度分析

對KNN，KNCN，LMKNN，LMKNCN和LMRKNCN算法的時間復(fù)雜度進行分析比較，進一步研究所提LMRKNCN 算法的分類性能。基于KNN 的分類算法，其運行時間主要由查找近鄰點所需時間來決定，因此只需分析四種算法查詢近鄰點的時間復(fù)雜度。在時間復(fù)雜度的計算中，涉及到的符號：n 為訓(xùn)練樣本數(shù)，d為樣本的特征數(shù)，k為近鄰個數(shù)，m為每類中的樣本數(shù)，L 為類別數(shù)。由文獻［15］可知，KNN 對測試樣本進行分類的時間通過計算歐幾里德距離尋找測試樣本的k個近鄰，因此KNN的時間復(fù)雜度為O（dn+kn+k）。在KNCN 算法中，根據(jù)近質(zhì)心選擇原則，對于一個待測點，查找該點的一個近質(zhì)心近鄰點最多需要進行n 次距離計算，n 次質(zhì)心點和n 次距離進行比較，因此查找一個待測點的K-近質(zhì)心近鄰點的時間復(fù)雜度為O（2dn+kn）。在LMKNN方法中，對任意待測點，首先需要分別在每類中查找k 個近鄰，在一個類別中需要進行m 次距離和m 次距離之間的比較，所需時間復(fù)雜度為O（dm+km），因此在有L 個類別的數(shù)據(jù)集上，LMKNN查找k 個近鄰的時間復(fù)雜度為O（dn+kn）。對于LMKNCN 算法，對于給定的待測點，需要查找每類訓(xùn)練樣本的k 個近質(zhì)心近鄰，這需要的時間復(fù)雜度為O（2dm+km），所以在有L 個類別的數(shù)據(jù)集上，一共需要的時間復(fù)雜度為O（2dn+kn）。本文所提算LMRKNCN 算法，同樣使用近質(zhì)心選擇原則找出每類訓(xùn)練樣本的k 個近鄰，所以與LMKNCN 算法相同，時間復(fù)雜度為O（2dn+kn）。

為了更直觀地展示，我們將所有算法的時間復(fù)雜度列入表3 中。觀察表3，可以得出：LMRKNCN與其他對比算法的時間復(fù)雜度比較接近，進一步說明了LMRKNCN算法的可實施性。

表3 時間復(fù)雜度

5 結(jié)語

為了針對基于KNN 算法中存在的問題，提高基于KNN 算法的分類識別率，本文提出了LMRKNCN 算法。LMRKNCN 在KNCN 與LMKNN算法的基礎(chǔ)上進行了改進，首先找出測試樣本關(guān)于每類的k 個近質(zhì)心近鄰，通過近質(zhì)心近鄰求解局部均值，使用協(xié)作表示系數(shù)作為表示的自適應(yīng)權(quán)重，最后使用基于樣本殘差分類決策函數(shù)，計算測試樣本與每類k 個近質(zhì)心局部均值近鄰點協(xié)作表示后預(yù)測樣本的殘差，將最小殘差所對應(yīng)的類別標簽分配給測試樣本。為了改善在小樣本情況下識別率容易受到k 值敏感性影響的問題，LMRKNCN 使用了近質(zhì)心近鄰和局部均值，近質(zhì)心近鄰可以將近鄰更幾何地分布在測試樣本附近，同時使用局部均值可以減少近鄰邊境區(qū)域中噪聲點對識別結(jié)果帶來的影響。與LMKNCN 的不同在于，LMRKNCN 對所得局部均值求解協(xié)作表示系數(shù)并用近質(zhì)心局部均值點協(xié)作表示測試樣本，可以改善因簡單的最大投票導(dǎo)致不同近鄰之間無區(qū)分度的問題。將LMRKNCN 與KNN，KNCN，LMKNN 和LMKNCN 在多個真實數(shù)據(jù)集上進行對比實驗，實驗結(jié)果表明LMRKNCN 的分類性能優(yōu)于其余對比算法，尤其是在小樣本數(shù)據(jù)集中對分類具有有效性和魯棒性。綜上所述LMRKNCN 在模式識別領(lǐng)域是一種有效的分類算法。

在本文工作的基礎(chǔ)上，筆者下一步將繼續(xù)收集其余高維度數(shù)據(jù)集并對LMRKNCN 的分類性能進行驗證，同時針對不同的數(shù)據(jù)集擴大k 的取值范圍，來使不同數(shù)據(jù)集獲得自適應(yīng)的動態(tài)最優(yōu)k 值和最佳的分類性能。