參數獨立的加權局部均值偽近鄰分類算法

蔡瑞光，張德生，肖燕婷

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

（?通信作者電子郵箱2151577901@qq.com）

0 引言

數據挖掘［1］是在大型數據存儲中自動發現有用信息的過程，分類屬于數據挖掘的四大任務之一。分類器能夠把數據集中的測試樣本映射到特定類別的分類函數或分類模型，已被廣泛應用于文字以及人臉識別、醫學、文本分類、商務、圖像處理、自然語言理解、垃圾郵件識別等領域。

局部均值K近鄰（Local Mean-basedK-Nearest Neighbor，LMKNN）算法是文獻［2］提出的一種經典的分類算法，其核心思想是先找到待分類樣本在訓練集中每類樣本中的k個近鄰的局部均值點，再將測試樣本分到離它最近的局部均值點所屬的類別。偽近鄰（Pseudo Nearest Neighbor rule for pattern classification，PNN）算法是文獻［3］提出的一種用偽最近鄰代替真正最近鄰的分類算法，首先找到待測樣本在每類訓練樣本中的偽最近鄰，再將其分到距離測試樣本最近的偽最近鄰所屬于的類。局部均值偽最近鄰（Local Mean-based Pseudo Nearest Neighbor，LMPNN）算法［4］是將經典的局部均值K近鄰（LMKNN）算法和偽最近鄰（PNN）算法相結合，充分利用了樣本的局部信息，降低了離群點對分類結果的影響。該算法的主要特點是簡單、快速且易于實現，至今仍被廣泛地應用。但該算法也有明顯的不足之處，參數的設置具有主觀敏感性，分類結果受k值的影響較大；將每個屬性值和類別均同等對待，忽略了每個屬性值和類別對分類結果的不同程度的影響。因此，確定最佳k值和屬性權重成為眾多學者的研究方向。

針對LMPNN 算法存在的不足之處，文獻［5］提出了基于局部均值與類均值的近鄰分類算法，該算法利用測試樣本對每個訓練類中k個近鄰的局部均值的信息和整體均值的信息進行預測分類。文獻［6］提出了基于局部均值表示的K近鄰分 類（Local Mean Representation-basedK-Nearest Neighbor classification，LMRKNN）算法，該算法首先尋找每個測試樣本在每類中的k個近鄰并用k個近鄰計算k個局部均值；其次，使用每類的k個局部均值線性表示測試樣本；最后，計算基于表示的距離作為測試樣本的分類決策函數。文獻［7］提出了基于加權均值表示的K近鄰分類（Weighted Local Mean Representation-basedK-Nearest Neighbor classification，WLMRKNN）算法，該算法充分利用k個近鄰的局部信息，并且賦予由k個近鄰計算的多局部均值不同的自適應權重表示測試樣本，且WLMRKNN 是對LMRKNN 分類器權重的擴展。文獻［8］提出了基于局部均值表示的調和近鄰分類（K-Harmonic Nearest Neighbor classification based on Local Mean Representation，LMRKHNN）算法，該算法計算測試樣本與每一個局部均值之間的距離，并用這些距離計算調和距離作為分類測試樣本的決策函數。文獻［9］提出了基于稀疏系數和殘差的k近鄰加權分類算法，該算法分別利用稀疏系數和殘差對距離度量進行加權，來充分考慮樣本的空間分布和屬性之間的相關程度。

上述幾種改進算法雖然都具有較好的分類效果，但是仍然存在k值設置困難和類別權重仍然敏感的問題，本文將基于成功歷史記錄的自適應參數差分進化（Success-History based parameter Adaptation for Differential Evolution，SHADE）算法與LMPNN算法結合用于解決數據分類問題，提出參數獨立的加權局部均值偽近鄰分類（Parameter Independent Weighted Local Mean-based Pseudo Nearest Neighbor classification，PIW-LMPNN）算法。PIW-LMPNN 并未將特定類別的最優權重和最優值作為兩個獨立的問題，而是采用一種新穎的實值編碼方案——SHADE 算法將兩個優化問題共軛為一個單目標連續非凸優化問題去解決。將新的分類算法在 15 個 UCI（UC Irvine machine learning）以 及 KEEL（Knowledge Extraction based on Evolutionary Learning）數據集上進行測試，實驗仿真結果表明，將SHADE 算法與LMPNN 算法結合能有效解決分類問題，其算法的穩定性以及求解精度得到了明顯的提升。

1 LMPNN算法

在特征空間Rd中，假定訓練集T=有L個類標號ω1，ω2，…，ωL，并且是訓練集中類別為ωj的訓練樣本集合。N和Nj分別代表訓練集T中樣本的個數和類別為ωj的訓練集中樣本的個數。算法步驟如下:

步驟1 計算待測試樣本x到中樣本的歐氏距離:

步驟2 將類別ωj中的歐氏距離按升序排列，并取前k個近鄰

步驟3 計算待測試樣本x在類別ωj中前i個近鄰的局部均值向量:

步驟4 給每一類中的局部均值向量分配不同的權重。在ωj類中，第i個局部均值向量的權值為:

步驟5 計算每類ωj中的偽近鄰。

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

例1 圖1中，是一個三類二維分類問題。測試樣本來自于第1 類樣本集。在表1 中，當k=2，3，4 時，首先使用LMPNN分類器，測試實例在k為2 和4 時被誤分為第2 類，在k為3 時被正確分類。其次，在使用LMPNN 分類器之前，使用一組關于類別的特定權重時（如式（6）所示），測試實例均被正確分為第1 類。所以，LMPNN 分類器的性能依賴于預先設置的k值和屬性權重。

圖1 測試樣本與訓練樣本Fig.1 Test samples and training samples

表1 不同k值下的偽近鄰分類Tab.1 Pseudo neighbor classification under different k values

2 SHADE算法

差分進化（Differential Evolution，DE）算法［10］是一種基于種群的全局搜索算法，許多實際問題利用DE 已得到有效解決。由于其算法結構簡單易于執行、控制參數少且有較強的搜索能力，差分進化算法吸引了眾多學者的關注和研究。但是該算法的性能在很大程度上依賴于縮放比例因子F和交叉概率CR等參數的選擇。SHADE 算法［11］是DE 的最新變體，該算法是利用自適應技術智能地計算F和CR的最優值，在一定程度上彌補了DE算法的不足。

SHADE 是一種基于群智能的隨機優化算法，具有種群內信息共享以及記憶個體最優解的優點，即通過種群內個體間的競爭與合作來實現對優化問題的求解，其本質是一種基于實值編碼的貪婪遺傳算法［12］。首先隨機初始化種群Y0=[y1，0，y2，0，…，yN，0]，N為種群規模。其 中，個 體yi，0=[yi，1，0，yi，2，0，…，yi，d，0]用于表示特征問題解，d為優化問題的維數。算法的基本思想為:對當前的種群進行變異和交叉操作后，產生一個新的種群，其次運用貪婪的思想對兩個種群進行選擇，產生新的一代種群。具體而言，首先通過式（7）對每一個個體yi，g實施變異操作，得到與其相對應的變異個體，即:

在變異策略DE/current-to-pbest/1 中，把被淘汰的個體存儲在一個集合A中，P表示當代種群組成的集合。表 示隨機從當代種群中適應度靠前的N×p(p∈[0，1])個個體中選擇一個；yi，g和yr1，g是從集合P中隨機選擇的兩個個體是從種群和A合并后的集合中隨機選擇的一個個體；Fi為收縮因子。其次，利用式（8）對y i，g和變異個體vi，g實施交叉操作，生成個體ui，g，即:

其中:rand(j)為[0，1]的隨機數；CRi為[0，1]的交叉因子；rnbr(i)為{1，2，…，d}的隨機變量。最后，運用貪婪思想對個體進行選擇，如式（9）所示，在個體ui，g和個體y i，g中保留較優個體進入下一代迭代。

其中f為適應度函數。

交叉因子CRi和收縮因子Fi的計算式如下:

其中:randci(α，β)和randni(α，β)分別服從柯西分布和正態分布；(i=1，2，…，H)的初始值均為0.5，ri∈[1，H]。根據式（12）～（13）進行更新:

將每一代SCR和SF的平均值都存儲在歷史矩陣MCR和MF中，并且保留了一組參數H，隨著搜索的進行來指導控制參數的自適應。因此，即使某個特定的SCR和SF中包含一組較差的值，也無法直接負面地影響已存儲在存儲器中的參數。此外，SHADE 算法使用較少的迭代次數相較經典DE 算法產生了更好的結果，保留了全局搜索策略，并通過基于差分形式的變異操作和基于概率選擇的交叉操作引導種群進化。

3 參數獨立的加權局部均值偽近鄰分類算法

通過對LMPNN 的描述可知，該分類器對k值選擇仍然敏感，且對所有實例都使用一組相同的權重，均等地對待每一類中的每一個屬性，并未考慮每類中代表性屬性的影響，且忽略了利用有用的信息來區分特定的類別。為此，提出了參數獨立的加權局部均值偽近鄰分類（PIW-LMPNN）算法，無需人為設定參數，可得到一組與類相關的最佳權重集，并同時通過優化得到最優k值。其基本思想為:對每類中的樣本施加特定類的屬性權重，引入了基于類的屬性加權方法，通過SHADE為每個類找到一組最佳權重，使每類代表性的屬性權重達到最高，同時將冗余的、嘈雜的屬性的權重降到最低；SHADE 同時可以經過優化得到最優k值；最后運用LMPNN 分類器預測測試樣本的類別。

3.1 目標函數

引入目標函數（14），通過SHADE 算法使其最小化，得到的參數值可以有效提高LMPNN算法的性能。

其中I是一個指示函數，如式（15）所示:

目標函數的域應與分類器的參數空間的域相關，表示為Z∈RD。h(·)是LMPNN 算法中的相異度度量。此外，z∈Z是e(·)的候選解，可以從中解出參數k和w的最佳選擇。接下來的任務是對z進行編碼，由SHADE 進行演化的同時計算得到k和w。z為D維向量，其中D=(L×d)+1，水平連接w的每一行并為k添加一個額外的單元格（如圖2 所示）。雖然能夠對w和k進行同時編碼，但是z的這種表示形式不能直接用于實踐中的優化，因為w是一個實值矩陣，其每一行的取值都應在0～1 的范圍內。另一方面，k值是一個在1～的范圍內的整數。在更新之后，通過從演化解z中提取w和k可以解決此問題。

圖2 通過SHADE算法優化后的最佳權重和k值Fig.2 Optimal weights and k value after optimization of SHADE algorithm

3.2 本文算法

所提出的PIW-LMPNN 分類器首先初始化N個解Z，其中(0 ≤z(f)≤1，?z∈Zandf=1，2，…，D)，接下來對每一個參數進行更新，在提取相應的w和k后，通過計算e(·)進行評估。對于w，更新和提取可以通過對每個權重集[z(rd-d+1)，z(rd-d+2)，…，z(rd)]進行歸一化來完成，取值范圍為0～1。對于k，z(D)的取值范圍在ε～1，其中ε是一個非常小的正實數（對于z(D)≤0，取z( D)=ε；對于z(D)≥1，取z(D)=1；否則z(D)的取值保持不變）。如式（16）所示，修改后的z(D)乘以k的最大允許值并四舍五入到下一個整數。

種群通過SHADE 算法進行更新。在SHADE 的每次迭代中，通過進化生成新的解，找出當前種群中使目標函數最小化時對應的w和k。將獲得的參數與訓練集T一起使用，計算LMPNN 的分類誤差，當其誤差小于相應父代的誤差時，新解決方案才成為總體的一部分。最后將所得的全局最優的w和k用于對測試樣本進行分類。具體算法描述如算法1所示。

算法1 PIW-LMPNN算法。

輸入 訓練集T，測試樣本x，H=100；

輸出 測試樣本x的類別c。

步驟1 在[0，1]隨機初始化種群Z=[ztj]N×D；

步驟2 利用SHADE 算法優化目標函數e(·)，找出最優的w*和k*；

步驟3 使用w*和k*以及式（17）去尋找測試樣本x在每類中的近鄰集合

步驟4 通過式（2）計算得到測試樣本x在每類中局部均值的集合

步驟5 通過式（3）～（4）計算測試樣本x在每類中的偽近鄰，以及測試樣本到偽近鄰的距離

步驟6 通過式（5）預測測試樣本x的類別c。

4 實驗與結果分析

為了驗證PIW-LMPNN 算法的分類性能，本文選取15 個常用數據集進行仿真實驗。其中，數據集包含數據量為150～2 536，特征維數為4～73，類別數為2～11。表2 給出了二分類問題的混淆矩陣。其中:TP（True Positive）表示將正類預測為正類數；TN（True Negative）表示將負類預測為負類數；FP（False Positive）表示將負類數預測為正類數；FN（False Negative）表示將正類數預測為負類數。表3 給出了本文實驗數據的部分信息。

表2 分類結果混淆矩陣Tab.2 Confusion matrix of classification results

表3 數據集詳細信息Tab.3 Detailed information of datasets

4.1 評價指標和非參數檢驗

以分類準確率、綜合評價指標以及非參數檢驗——Wilcoxon 符號秩檢驗、Friedman 秩方差檢驗以及Hollander-Wolfe兩處理等作為評價指標比較PIW-LMPNN和其他分類算法的性能。

4.1.1 分類準確率

分類準確率（Acc）的計算式如下:

TP和TN的值越大表明分類正確的樣本數越多，則分類準確率越高［13］。

4.1.2 綜合評價指標

綜合評價指標（F-Measure）是精確率（Precision，P）和召回率（Recall，R）的加權調和平均，如式（20）所示。

其中:P是指正確判別為該類的樣本數與分類器實際判別屬于該類的樣本總數的比值，如式（21）所示；R是指正確判別為該類的樣本數與原樣本集中實際屬于該類的樣本總數的比值，如式（22）所示。

當a=1時，F1=。F1是一種綜合考慮P與R的評價指標，具有較好的獨立性、時間無關性、可擴展性和較低的計算復雜度。當F1的值越大時，表示分類器越有效。

4.1.3 Wilcoxon符號秩檢驗

兩配對樣本分布差異的非參數檢驗是利用兩個配對樣本對樣本來自的兩個總體的分布是否存在顯著差異進行檢驗。Wilcoxon 符號秩檢驗［14］的原假設是兩配對樣本來自的兩總體的分布無顯著差異，計算式如下:

其中，θi表示兩個對比算法在15 個數據集上的分類準確率的差，將其差值的絕對值按升序排列，對應的秩記為rank(θi)，R+與R-分別表示正秩和與負秩和。將R=min(R+，R-)作為檢驗統計量，顯著性水平α為0.05，在大樣本情況下可以使用正態近似:

計算得到Z值以后，查正態分布表對應的概率p值，若概率p值小于顯著性水平α，則拒絕原假設。

4.1.4 Friedman秩方差檢驗

Friedman秩方差檢驗［15］是一種實現多個總體分布是否存在顯著差異的非參數檢驗方法，適用于兩個因素的各種水平的組合都有一個觀測值的情況。假定第一個因子有k個水平，第二個因子有b個水平，因此一共有k×b個觀測值。設各總體的位置參數為θ1，θ2，…，θk，假設檢驗問題為:

檢驗統計量為:

Q值近似自由度為v=k-1 的χ2分布。若實測Q＜，則不拒絕H0；反之，則接受H1。

4.1.5 Hollander-Wolfe兩處理比較

當Friedman 秩方差檢驗的分析結果有差異時，卻不能表明哪兩個分類器之間有差異顯著性。所以本文將運用兩樣本（處理）間的比較［16］，計算式如下:

其中，R·i和R·j分別為第i個和第j個樣本的秩和。有:

當實測|Dij|≥時，表示兩樣本間有差異；反之則無差異。其中，α*=α/[k(k-1)］，α為顯著性水平，為標準正態分布分位數。

4.2 實驗結果

實驗基于Intel（R）Core（TM）i7-4700 CPU@3.60 GHz 環境，算法采用Matlab 和R 語言編程實現。將本文PIW-LMPNN算法與其他8 種分類算法進行對比，表4 給出了9 種分類算法的準確率和F1 值，表5 給出了PIW-LMPNN 算法與其他對比算法的Wilcoxon 符號秩檢驗，表6 給出了9 種分類算法的Friedman 檢驗的平均等級，表7 給出了PIW-LMPNN 算法與8種對比算法的兩處理的Hollander-Wolfe計算。

表4 在不同數據集上分類準確率、F1值及最優k值Tab.4 Classification accuracy，F1 value and optimal k value on different datasets

表5 PIW-LMPNN與其他對比算法的Wilcoxon符號秩檢驗結果Tab.5 Wilcoxon signed-rank test results of PIW-LMPNN and other comparison algorithms

表6 不同分類算法的Friedman檢驗中的平均秩Tab.6 Average rank of different classification algorithms in Friedman test

表7 在α=0.05時兩處理的Hollander-Wolfe計算結果Tab.7 Hollander-Wolfe calculation results for pairwise processing when α=0.05

在本文的仿真實驗中，KNN、FKNN（Fuzzy K Nearest Neighbor）、WKNN（distance-Weighted K-Nearest-Neighbor）、LMPNN［4］、LMKNN［2］、MLMNN（Multi-Local Means based Nearest Neighbor method）［17］、WRKNN（Weighted Representation-based K-Nearest Neighbor classification）和WLMRKNN 這8 種分類算法對k值均采用逐一驗證的方法。具體設置如下:首先k的取值范圍為1～（n表示樣本數量）；其次，重復5次m折交叉驗證得到每個k值所對應的平均準確率，將平均準確率最高時所對應的k值選擇為最優k值。根據文獻［11］可知，當H的值取為100 時，目標函數的最大評估次數（maximum number of Fitness Evaluations，FEs）為1000×d，在大多數數據集上取得了較好的效果。

4.3 結果分析

在表4 中給出了PIW-LMPNN 算法和其他8 種分類算法在15 個數據集上的最優k值、分類準確率以及F1 值。由表4可見，PIW-LMPNN 在除band 數據集以外的14 個數據集上的分類準確率均高于其他比較算法。band數據集在本文算法中的分類準確率為70.49%，雖然低于WRKNN 和WLMRKNN 算法，但仍高于其余6 種算法的準確率。除此之外，還可以看到PIW-LMPNN 算法在iris、wine、wdbc、vehi、seg 和der 這6 個數據集中的分類準確率得到了明顯的提升。PIW-LMPNN 在15個數據集中獲得了最高的平均準確率（如圖3 所示）。除此之外，由表4 可知，對于實驗所選取的15 個數據集，在9 個算法中，14 個數據集的最好的F1 值都是由本文所提出的PIWLMPNN 算法得到的，也就是說，本文算法的精確率和召回率的綜合性能較好。整體而言，PIW-LMPNN 算法的整體性能優于其他對比算法，所提算法的分類準確率和F1值分別最大提高了約28個百分點和23.1個百分點。

圖3 不同分類算法的準確率比較Fig.3 Accuracy comparison of different classification algorithms

表5 給出了本文算法與所有對比算法的Wilcoxon 符號秩檢驗的結果。由表5 可知，R+的值遠遠大于R-的值，檢驗統計量Z的值小于-1.96，概率p值均小于0.05。Wilcoxon 符號秩檢驗結果表明，在顯著性水平α=0.05 的條件下，PIWLMPNN算法的分類性能明顯優于其他對比算法。

在Friedman 秩方差分析法中，首先將表4 中的所有算法在每一個數據集上的分類準確率進行排序，排名越大，其分類結果越好。在表6 中列舉了每個分類算法的平均排序，PIWLMPNN 算法的平均排序Ri和其他對比算法的平均排序有較大的區別。實際測量Q=52.554 ＞=15.507，故接 受H1，認為9個分類算法存在顯著差異。

Friedman 秩方差分析法已檢驗出分類算法之間有差異，接下來將進一步研究本文算法與每一個對比算法兩兩之間是否存在差異。由表7中9種分類算法性能比較結果可知，本文算法與其他8 種對比算法有顯著的差異。Friedman 秩方差分析和Hollander-Wolfe兩處理比較表明了本文算法和基于KNN的分類算法是不同的，并且PIW-LMPNN 算法的分類性能明顯優于其他對比算法。

5 結語

LMPNN 是一種有效的分類算法。在每一類中，能夠根據選取的k個近鄰計算得到測試樣本的偽近鄰，進而通過決策函數預測測試樣本的類別。但是，該分類算法依賴于預先設置的k值，而且忽略了每個屬性對分類結果的不同的重要影響程度，將每個屬性同等對待。針對這些問題，本文提出了一種參數獨立的加權局部均值偽近鄰分類（PIW-LMPNN）算法。該算法將SHADE 算法和LMPNN 算法結合，首先對訓練集樣本進行優化得到最佳k值和一組與類別相關的最佳權重，然后計算樣本間的距離時賦予每類的每個屬性不同的權重進行分類。

在15 個實際數據集上的實驗結果表明，改進后的分類算法克服了LMPNN 算法對k值的敏感性和均等對待特征屬性的不足，且具有較強的泛化能力。下一步的主要工作是研究所提算法在復雜實際問題中的應用。