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

李 毅，張德生，張 曉

西安理工大學理學院，西安 710054

分類[1]是數據挖掘中最重要的任務之一，它是通過對已知訓練集進行學習，建立分類器預測未知樣本標簽的一種方法，在模式識別領域屬于監督學習。目前，分類算法主要包括支持向量機[2]、決策樹[3]、人工神經網絡[4]、貝葉斯分類器[5]和KNN算法[6]等，其中KNN算法因具有較高的分類精度和易于實現等優點，在人臉識別[7]、故障檢測[8]和醫學研究[9]等領域得到了廣泛應用。

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

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

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

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

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

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

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

1 預備知識

1.1 符號說明

本文常用的符號見表1。

表1 符號說明Table 1 Symbol description

1.2 LMPNN算法

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

算法1LMPNN算法

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

輸出：待測樣本x的類標號。

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

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

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

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

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

步驟5預測待測樣本x所屬類：

2 本文算法

2.1 雙層搜索規則

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

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

即，用傳統的近鄰規則在Tj中查找待測樣本x的k近鄰所形成的集合。

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

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

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

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

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

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

2.2 注意力機制

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

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

其中

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

2.3 多調和平均距離

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

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

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

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

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

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

2.4 IPLMPNN算法

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

算法2ⅠPLMPNN算法

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

輸出：待測樣本x的類標號。

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

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

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

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

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

步驟6預測待測樣本x的類標號：

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

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

2.5 算法復雜度分析

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

3 實驗與分析

3.1 數據集

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

表2 數據集Table 2 Data sets

3.2 實驗結果與分析

實驗以分類準確率為評價標準。對樣本數量較小的數據集采用10次3折或5折交叉驗證法，對樣本數量較大的數據集采用10 次10 折交叉驗證法，最終將實驗得到的準確率平均值作為分類結果。對近鄰參數k逐一取值1，2，…，15，采用交叉驗證法得到每個k值所對應的平均準確率，將最高的平均準確率所對應的k值選擇為最優k值。

3.2.1 實驗參數設置

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

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

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

3.2.2 IPLMPNN算法在最優k 值下的性能分析

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

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

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

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

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

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

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

4 結束語

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