一種改進的局部均值偽近鄰算法

李 毅，張德生，張 曉

西安理工大學(xué)理學(xué)院，西安 710054

分類[1]是數(shù)據(jù)挖掘中最重要的任務(wù)之一，它是通過對已知訓(xùn)練集進行學(xué)習(xí)，建立分類器預(yù)測未知樣本標(biāo)簽的一種方法，在模式識別領(lǐng)域?qū)儆诒O(jiān)督學(xué)習(xí)。目前，分類算法主要包括支持向量機[2]、決策樹[3]、人工神經(jīng)網(wǎng)絡(luò)[4]、貝葉斯分類器[5]和KNN算法[6]等，其中KNN算法因具有較高的分類精度和易于實現(xiàn)等優(yōu)點，在人臉識別[7]、故障檢測[8]和醫(yī)學(xué)研究[9]等領(lǐng)域得到了廣泛應(yīng)用。

KNN 算法的基本思想[10]是將待分類樣本與訓(xùn)練樣本之間的歐氏距離按升序排列，選取距離最小的k個近鄰，將待分類樣本分配給標(biāo)簽頻率最高的類別。盡管KNN算法有許多優(yōu)點，但仍有一些不足：KNN算法對近鄰參數(shù)k比較敏感；選取近鄰時未考慮樣本的分布信息；采用單一的多數(shù)投票原則或最短距離原則進行分類決策。

針對KNN 算法存在的不足，研究學(xué)者提出了不同的改進方法[11-15]。文獻[11]提出了一種新的基于距離加權(quán)最近鄰規(guī)則的雙加權(quán)投票方法（DWKNN），該算法降低了參數(shù)k的敏感性。文獻[12]提出了利用距離加權(quán)來進行局部學(xué)習(xí)的偽最近鄰規(guī)則，同時提出了基于局部平均向量和類統(tǒng)計量的非參數(shù)分類器（PNN），該方法減少了異常值對分類性能的影響。文獻[13]對于PNN 算法中距離加權(quán)系數(shù)主觀確定的問題，提出了一種基于BP神經(jīng)網(wǎng)絡(luò)的自適應(yīng)偽最近鄰分類算法（BPANN），降低了分類過程中主觀因素帶來的不確定性。文獻[14]提出了一種基于局部均值的偽近鄰算法（LMPNN），該算法使用k個局部均值向量代替k個最近鄰，減少了KNN算法中異常值和維數(shù)對分類性能的影響?；诨ソ彽乃枷?，文獻[15]提出了一種基于雙向選擇的偽近鄰分類算法（BS-PNN），降低了噪聲點對分類的影響。

不同于文獻[11]，LMPNN 算法計算各類的局部均值向量，使用偽近鄰規(guī)則進行分類決策；文獻[12]和[13]利用每類的k個最近鄰計算偽近鄰進行分類決策，而LMPNN 算法搜索每類的k個最近鄰作為類原型，利用最近鄰集合的k個局部均值向量找到各類基于局部均值的偽近鄰，根據(jù)待測樣本與新的偽近鄰之間的加權(quán)距離進行分類，能夠更加準(zhǔn)確地找到偽近鄰，提高了算法的分類準(zhǔn)確率。LMPNN 算法雖取得了較好的分類效果，但仍存在以下不足：（1）在選取k個近鄰時，只考慮待測樣本到訓(xùn)練樣本的距離，沒有考慮樣本的分布信息，并且沒有從訓(xùn)練樣本的角度確定待測樣本是否為其k近鄰；（2）對于分類測試樣本，不同的多局部均值應(yīng)該有不同的權(quán)重，但LMPNN 算法對每類的第i個局部均值向量主觀賦予相同的權(quán)重1/i；（3）使用歐氏距離進行分類決策，不能較好地反映局部均值對分類的作用。

針對LMPNN 算法的上述不足，本文進行了改進，提出了一種改進的局部均值偽近鄰算法（ⅠPLMPNN）。

（1）引入了雙層搜索規(guī)則查找待測樣本的雙層近鄰集，提高了近鄰集的選擇質(zhì)量；

（2）引入了注意力機制計算局部均值點與待測樣本之間的距離加權(quán)系數(shù)，體現(xiàn)了局部均值向量對待測樣本的重要程度；

（3）提出了新的多調(diào)和平均距離進行分類決策，降低了噪聲點的影響和近鄰參數(shù)k的敏感性。

1 預(yù)備知識

1.1 符號說明

本文常用的符號見表1。

表1 符號說明Table 1 Symbol description

1.2 LMPNN算法

在P維特征空間中，假定有訓(xùn)練樣本集T={y1,y2,…,yN}，其類標(biāo)簽為，給定一個待測樣本x，LMPNN算法的步驟如下：

算法1LMPNN算法

輸入：待測樣本x，訓(xùn)練集T={y1,y2,…,yN}，類標(biāo)號，類cj對應(yīng)的訓(xùn)練集Tj={y|l(y)=cj}，近鄰個數(shù)k。

輸出：待測樣本x的類標(biāo)號。

步驟1計算待測樣本x到Tj中每個樣本y的歐氏距離：

將得到的距離按升序排列，取前k個近鄰記為y(1),y(2),…,y(k)。

步驟2計算待測樣本x在Tj中的第i個局部均值向量：

步驟3在Tj中，對k個近鄰點所對應(yīng)的局部均值點按照到待測樣本x的距離升序排列，并為第i個局部均值點賦予對應(yīng)的權(quán)值：

步驟4查找x在Tj中的偽近鄰點,x到的距離d()被定義為k個局部均值點到x的歐氏距離的加權(quán)總和，即：

步驟5預(yù)測待測樣本x所屬類：

2 本文算法

2.1 雙層搜索規(guī)則

LMPNN算法采用式（1）確定待測樣本的近鄰集，僅考慮了待測樣本和訓(xùn)練樣本之間的距離，對噪聲點仍然敏感。針對這一問題，本文引入雙層搜索規(guī)則查找待測樣本的近鄰集合，提高近鄰集的選擇質(zhì)量，降低噪聲點的影響。根據(jù)步驟1至步驟4查找待測樣本的雙層近鄰集[16]。

步驟1對于待測樣本x，其在訓(xùn)練樣本集Tj的第一層近鄰集為：

即，用傳統(tǒng)的近鄰規(guī)則在Tj中查找待測樣本x的k近鄰所形成的集合。

步驟2對于待測樣本x，其在訓(xùn)練樣本集Tj的第二層近鄰集為：

其中，rNN1st(x)是NN1st(x)的半徑，即x到NN1st(x)中第k個近鄰的距離。

步驟3對于待測樣本x，其在訓(xùn)練樣本集Tj的擴展近鄰集為：

其中，c是NN2nd(x)的質(zhì)心。

步驟4對于待測樣本x，其在訓(xùn)練樣本集Tj的雙層近鄰集為：

其中，(y)代表集合T*=Tj∪{x} 中y的kb個近鄰形成的集合，kb一般不小于k。計算(x)中的k*個近鄰與x的歐氏距離，按照升序排列記為y?(1),y?(2),…。需要指出的是表示集合的基數(shù)。k*一般受kb取值影響，其值可能大于k，也可能不超過k。由雙層近鄰集(x)計算x在Tj中的第i個局部均值向量：

2.2 注意力機制

LMPNN 算法式（4）中的由權(quán)值Wi和局部均值點到x的距離兩部分的乘積組成。然而，由式（3）計算的權(quán)值Wi對任意的k個近鄰點均是固定的，使得LMPNN 算法不能得到較優(yōu)的距離加權(quán)值。由此本文引入注意力機制對其進行改進，考慮每個局部均值向量對待測樣本分類的影響。

注意力機制模型[17]能夠根據(jù)信息的重要程度賦予相應(yīng)的權(quán)重。注意力機制的步驟主要分為以下三步：首先，使用評分函數(shù)計算兩樣本點的相似度；其次，利用softmax 函數(shù)歸一化，使其成為一個和為1 的概率分布，得到注意力系數(shù)；最后，根據(jù)注意力系數(shù)和相應(yīng)點的加權(quán)和得到注意力值。根據(jù)注意力機制，設(shè)置Tj中第i個局部均值點（見式（10））對應(yīng)的權(quán)值為：

其中

反映局部均值點和待測樣本x的相似度。

2.3 多調(diào)和平均距離

針對LMPNN算法式（4）中距離對近鄰參數(shù)k以及噪聲點均敏感的問題，本文在已有的調(diào)和平均距離[18]基礎(chǔ)上，提出一種新的多調(diào)和平均距離，定義如下。

Tj中第i個局部均值向量到待測樣本x的多調(diào)和平均距離為：

其中，表示Tj中第r(r=1,2,…,i)個局部均值向量，表示待測樣本x與的歐氏距離。

式（14）中用替代式（13）中的d(x,y)，將每類中的k*個近鄰用k*個局部均值向量替代。具體分析如下：

其中，y?(1),y?(2),…,y?(k*)為使用雙層搜索規(guī)則得到x在Tj中的k*個近鄰。

d(x,y)易受到單個近鄰的影響，若近鄰集合中有噪聲點，分類結(jié)果因噪聲點的影響可能導(dǎo)致待測樣本的誤分類。由式（15）可知，考慮了x與的差分向量，并且使用u?rj代替近鄰點，在進行分類決策時受單個近鄰點的影響較小，降低了噪聲點的影響。另外，式（14）的i相較于式（13）中的k是變化的，從而能降低近鄰參數(shù)k的敏感性。

2.4 IPLMPNN算法

本文算法的基本思想為：首先，在Tj中通過雙層搜索規(guī)則選取待測樣本x的雙層近鄰集。使用篩選后的近鄰計算局部均值向量。其次，引入注意力機制計算注意力系數(shù)，利用式（11）為多局部均值向量分配不同的權(quán)重。最后，使用新的多調(diào)和平均距離式（14）進行分類決策。由此，提出了ⅠPLMPNN算法，具體步驟見算法2。

算法2ⅠPLMPNN算法

輸入：待測樣本x，訓(xùn)練集T={y1,y2,…,yN}，類標(biāo)號，類cj對應(yīng)的訓(xùn)練集Tj={y|l(y)=cj}，第一層近鄰個數(shù)k。

輸出：待測樣本x的類標(biāo)號。

步驟1根據(jù)雙層搜索規(guī)則查找待測樣本x在Tj中的k*近鄰，表示為。計算中的k*個近鄰到x的歐氏距離，按照升序排列為y?(1),y?(2),…,y?(k*)。

步驟2根據(jù)（10）式計算待測樣本x在Tj中的第i個局部均值向量，令形成的集合為

步驟3在Tj中，根據(jù)式（11）和式（12）計算每個局部均值向量對待測樣本x的影響權(quán)重。

步驟4在Tj中，根據(jù)式（14）計算待測樣本x到局部均值向量的多調(diào)和平均距離。

步驟5查找x在Tj中的偽近鄰點,x到的距離被定義為k*個局部均值點到x的調(diào)和平均距離的加權(quán)和，即：

步驟6預(yù)測待測樣本x的類標(biāo)號：

ⅠPLMPNN 算法的流程圖如圖1 所示。首先，將樣本數(shù)據(jù)預(yù)處理，查找待測樣本的雙層近鄰集；然后，由局部均值向量和待測樣本計算注意力系數(shù)，得到距離權(quán)重系數(shù)；最后，由新的多調(diào)和平均距離計算得到偽近鄰點，對待測樣本進行分類。

圖1 ⅠPLMPNN算法流程圖Fig.1 ⅠPLMPNN algorithm flow chart

2.5 算法復(fù)雜度分析

假設(shè)數(shù)據(jù)集的規(guī)模為N，特征維數(shù)為P，近鄰個數(shù)為k，類別個數(shù)為M。ⅠPLMPNN算法的時間復(fù)雜度主要來源于以下5 個方面：（1）計算待測樣本到每類訓(xùn)練樣本的歐氏距離，找到k個近鄰，時間復(fù)雜度為O(NP+Nk)；（2）使用雙層搜索規(guī)則查找待測樣本的雙層最近鄰，時間復(fù)雜度為O((k2+k)M)；（3）計算每類的k個局部均值向量，得到k個局部均值向量與待測樣本之間的多調(diào)和平均距離，時間復(fù)雜度為O(MPk+M(1+k)k)；（4）將注意力權(quán)重分配給每類的局部均值向量，得到每個類的偽近鄰點，時間復(fù)雜度為O(Mk+MPk)；（5）使用決策函數(shù)確定待測樣本的類別，時間復(fù)雜度為O(M) 。因此，ⅠPLMPNN 算法總的時間復(fù)雜度為O(NP+Nk+MPk+Mk2)。

3 實驗與分析

3.1 數(shù)據(jù)集

為了驗證ⅠPLMPNN 算法的有效性，選擇UCⅠ和KEEL 中的14 個數(shù)據(jù)集（如表2 所示）進行實驗。所有實驗均在MATLAB R2017b環(huán)境下完成。

表2 數(shù)據(jù)集Table 2 Data sets

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

實驗以分類準(zhǔn)確率為評價標(biāo)準(zhǔn)。對樣本數(shù)量較小的數(shù)據(jù)集采用10次3折或5折交叉驗證法，對樣本數(shù)量較大的數(shù)據(jù)集采用10 次10 折交叉驗證法，最終將實驗得到的準(zhǔn)確率平均值作為分類結(jié)果。對近鄰參數(shù)k逐一取值1，2，…，15，采用交叉驗證法得到每個k值所對應(yīng)的平均準(zhǔn)確率，將最高的平均準(zhǔn)確率所對應(yīng)的k值選擇為最優(yōu)k值。

3.2.1 實驗參數(shù)設(shè)置

實驗1對于ⅠPLMPNN算法步驟1中的參數(shù)kb，不同于傳統(tǒng)近鄰規(guī)則中的近鄰參數(shù)k,kb一般大于k需通過實驗確定。這里，取kb=k,kb=1.2k,kb=1.4k,kb=1.6k,kb=1.8k,kb=2.0k，利用ⅠPLMPNN算法對表2的數(shù)據(jù)集進行實驗，實驗結(jié)果如表3 所示，加粗數(shù)字表示各數(shù)據(jù)集的最優(yōu)值。

表3 k 與kb 在不同關(guān)系下的分類準(zhǔn)確率Table 3 Classification accuracy under different relationships of k and kb單位：%

表3 的實驗結(jié)果表明kb在6 種相應(yīng)取值下，ⅠPLMPNN 算法分別在4 個，7 個，5 個，4 個，3 個，2 個數(shù)據(jù)集上得到了最高的分類準(zhǔn)確率。并且kb=1.2k在14個數(shù)據(jù)集上的平均準(zhǔn)確率為86.72%，在6種取值中排名第一。實驗結(jié)果表明kb=1.2k有最好的分類性能，所以在實驗2 和實驗3 中設(shè)置kb=1.2k，以實現(xiàn)更好的分類效果。

3.2.2 IPLMPNN算法在最優(yōu)k 值下的性能分析

實驗2為了評估ⅠPLMPNN算法在最優(yōu)k值下的分類性能，將KNN[8]、DWKNN[11]、PNN[12]、MLM-KHNN[18]、KGNN[19]、RCKNCN[20]、DC-LAKNN[21]和LMPNN[14]算法與ⅠPLMPNN算法的平均準(zhǔn)確率進行對比。得到的平均分類準(zhǔn)確率如表4 所示，加粗數(shù)字表示9 種算法的最優(yōu)值。需要說明的是，其他8種算法的平均準(zhǔn)確率也是最優(yōu)k值下對應(yīng)的結(jié)果(k=1,2,…,15)。

表4 最優(yōu)k 值下ⅠPLMPNN算法與其他8種算法的平均準(zhǔn)確率Table 4 Average accuracy of ⅠPLMPNN and other eight algorithms corresponding to optimal k value 單位：%

表4 的結(jié)果表明，除Heart、Ⅰris、Letter 和Thyroid 數(shù)據(jù)集外，ⅠPLMPNN算法在其他10個數(shù)據(jù)集上得到了最高的平均分類準(zhǔn)確率。特別在Glass、Ⅰonosphere、Seeds和Sonar 這4 個數(shù)據(jù)集上的分類準(zhǔn)確率較LMPNN 算法有了明顯提升。在Letter 和Thyroid 數(shù)據(jù)集上取得最高準(zhǔn)確率的是RCKNCN算法，其結(jié)果為96.37%和95.40%，分別比ⅠPLMPNN 算法高0.05 個百分點和0.22 個百分點。在Heart 和Ⅰris 數(shù)據(jù)集上取得最高準(zhǔn)確率的分別是MLM-KHNN 算法和LMPNN 算法，其準(zhǔn)確率分別為80.16%、95.13%，比ⅠPLMPNN 算法高0.13 個百分點和0.12 個百分點。雖然ⅠPLMPNN 算法在這4 個數(shù)據(jù)集上的準(zhǔn)確率略低，但仍高于大多數(shù)對比算法。并且ⅠPLMPNN 算法在14 個數(shù)據(jù)集中獲得了最高的平均準(zhǔn)確率86.37%，與其他8種算法相比有明顯的優(yōu)勢。

3.2.3 IPLMPNN算法在不同k 值下的性能分析

實驗3為了驗證ⅠPLMPNN 算法在不同k值下的分類性能，將8 種對比算法與ⅠPLMPNN 算法在10 次交叉驗證中得到的平均分類準(zhǔn)確率進行比較。利用表2的Ⅰonosphere、Seeds、Segment、Glass4 個數(shù)據(jù)集進行仿真實驗。圖2為9種算法的平均分類準(zhǔn)確率折線圖。

圖2 不同算法在4個數(shù)據(jù)集上隨著變化的k 值的平均分類準(zhǔn)確率Fig.2 Average accuracy of each algorithm with variation of k values for four data sets

從圖2可以看出，當(dāng)k ＜5 時，ⅠPLMPNN算法較其他對比算法更為陡峭，準(zhǔn)確率增長趨勢更大。當(dāng)k在5到10之間時，ⅠPLMPNN算法在Ⅰonosphere、Segment、Glass數(shù)據(jù)集上呈現(xiàn)出較為平穩(wěn)的變化趨勢，在Seeds 數(shù)據(jù)集上呈現(xiàn)增長趨勢。當(dāng)k ＞10 時，KNN、DWKNN、PNN、KGNN算法的準(zhǔn)確率隨著k值的增大而減小，LMPNN、MLM-KHNN、DC-LAKNN、ⅠPLMPNN 算法的準(zhǔn)確率較為平穩(wěn)，且略有增長，RCKNCN 算法在Ⅰonosphere 和Glass數(shù)據(jù)集上變化較為平穩(wěn)，在Segment數(shù)據(jù)集上準(zhǔn)確率隨著k值的增大而增大，而在Seeds 數(shù)據(jù)集上準(zhǔn)確率呈現(xiàn)下降趨勢。說明了9種算法中ⅠPLMPNN算法在不同近鄰參數(shù)k下的分類性能是具有優(yōu)勢的，降低了參數(shù)k的敏感性。

4 結(jié)束語

針對LMPNN算法存在的不足，本文對其進行了改進，提出了一種改進的局部均值偽近鄰算法（ⅠPLMPNN）。ⅠPLMPNN算法首先通過引入新的近鄰選取規(guī)則選取待測樣本的高質(zhì)量近鄰點，然后基于注意力機制計算各類的距離加權(quán)系數(shù)，最后使用改進的多調(diào)和平均距離作為新的分類決策規(guī)則，降低了近鄰參數(shù)k對算法的影響。實驗結(jié)果表明，ⅠPLMPNN 算法在分類準(zhǔn)確率上取得了令人滿意的結(jié)果。由于ⅠPLMPNN算法的時間復(fù)雜度較高，因此，下一步的研究工作將提高ⅠPLMPNN算法的計算效率，并將改進的算法應(yīng)用到實際問題中。