基于局部密度和相似度的自適應SNN算法

劉娜　生龍

摘要：在近鄰算法中，近鄰樣本和目標樣本之間的絕對距離和相似性為目標樣本類別的判斷提供重要的決策依據，K值的大小也會直接決定了近鄰算法的預測效果。然而，SNN算法在預測過程中，使用固定的經驗K值來預測不同局部密度的目標樣本，具有一定的片面性。因此，為實現SNN算法中K值的合理調節，提高算法的預測準確度和穩定性，提出一種基于局部密度和相似度的自適應SNN算法（AK-SNN）。算法的性能在UCI數據集上進行驗證，結果顯示該算法取得優于KNN和SNN的預測效果和魯棒性。

關鍵詞：KNN;SNN;相似度計算;局部密度;自適應;AK-SNN

中圖分類號： TP301? ? ? ? 文獻標識碼：A

文章編號：1009-3044（2021）06-0006-04

Abstract：In the nearest-neighbor algorithm， the absolute distance and similarity between the nearest-neighbor samples and the object sample provide significant decision basis for judging class of the object sample， and the size of K directly determines the prediction effect of the nearest-neighbor algorithm. However， in prediction process of SNN algorithm， it uses empirical K value selection to predict target samples with different local densities， which has some one-sidedness. Therefore， an adaptive SNN algorithm （AK-SNN） based on local density and similarity is proposed to realize reasonable adjustment of K in the SNN algorithm and improve the prediction accuracy and stability of the algorithm. The performance of the algorithm is verified on the UCI dataset， and the results show that the proposed algorithm achieves better prediction effect and robustness than KNN and SNN.

Key words：KNN; SNN; similarity calculation; local density; AK-SNN

引言

近鄰算法具有容易實現、訓練時間短等特點，是一種高效實用的分類算法。KNN（K-Nearest Neighbor） [1]作為近鄰算法中最為常用的分類算法，被廣泛應用于手寫體識別[2]，數據挖掘與金融等方面。但算法中依然存在一些問題：1）距離度量方式的問題;2）最近鄰樣本集的選擇存在偏好問題[3];3）K值大小對于算法性能影響問題。

為解決KNN存在的問題，周青等將特征熵融入KNN中，提出了一種FECD-KNN分類算法，該算法將特征熵作為類相關度，以其差異值計算樣本距離，從而建立距離測度與類別間的內在聯系[4]。黃光華等提出了一種基于交叉驗證和距離加權的改進KNN算法[5]，減小算法的空間復雜度，改善預測性能。張兵等人提出了基于局部密度和純度的自適應選取K值的方法，提高算法準確率[6]。茹強喜和劉永利用主分量分析（PCA）與粗糙集理論（RS）對高維樣本集降維，并使用模擬退火算法實現隨機屬性子集選擇，最終利用多重K近鄰分類器進行組合實現樣本類別預測，有效地改進了K近鄰法的分類精度和效率[7]。Xiao Xingjiang等提出了一種基于特征值熵加權的KNN算法，用于改善特征貢獻對類別判定的影響[8]。Zhang Shichao提出了殼近鄰（SNN， Shell Nearest Neighbor），克服了KNN算法的選擇偏好問題[9]。

在傳統SNN算法中，K值的大小對算法性能依然具有較大影響，并且該算法不具備K值的自動調節能力。為實現對近鄰數K的優化選取并保障所選近鄰樣本的相似性，提出一種基于局部密度和相似度的自適應SNN算法（AK-SNN）。

1 相關工作

1.1 KNN算法

KNN算法由Cover和Hart提出，通過距離將與目標樣本最靠近的k個訓練集樣本選擇出來，用來預測目標樣本的種類。該算法的距離計算使用歐氏距離，歐氏距離代表的是不同樣本在空間分布中的相對位置，歐氏距離越小，表示不同樣本之間在空間分布上距離越近，其公式如下：

上圖中，菱形表示負類樣本，正方形表示正類樣本，三角形表示目標樣本。利用KNN算法是對目標樣本預測，K=3時，最靠近目標樣本的3個訓練集樣本中存在2個負類樣本和1個正類樣本，因此根據多數類投票機制目標樣本的預測類別為負類;當K=7時，最靠近目標樣本的7個訓練集樣本中存在4個正類樣本和3個負類樣本，則目標樣本類別被預測為正類。

1.2 SNN算法

殼近鄰（Shelly Nearest Neighbor）即SNN[10]，是一種改進的KNN算法。該算法根據目標樣本特征，在訓練集中尋找其最左最右近鄰樣本，并與利用KNN算法獲得的k個近鄰樣本取交集，以獲得與目標樣本更相關的近鄰樣本集，從而剔除異類樣本，解決KNN在預測過程中的偏好問題，提高了算法的魯棒性。

SNN算法的具體步驟如下：

1） 初始化訓練集D，目標樣本和近鄰數K。

2） 對于目標樣本Xo，根據公式1）計算訓練集D與其最近的k個樣本，構成目標樣本的K近鄰集KNN（Xo， K）。

3） 根據目標樣本的第i個特征（i = 1， 2，... ，q），在訓練集中計算目標樣本第i個特征下的最左和最右近鄰樣本，構成特征最近鄰集SD（Xoi）。

4） 根據3）中的方式，獲得目標樣本Xo的q個特征的最左和最右近鄰，構成Xo的特征最近鄰集SD（Xo）。

5） 獲得目標樣本的殼近鄰集：SN（Xo）=KNN（Xo， K）∩SD（Xo）

6） 根據殼近鄰集SN（Xo），預測目標樣本Xo的類別。

由于SNN算法解決了KNN算法的選擇偏好問題，多數情況該算法也取得了良好的預測效果。但在實際運行中，當人為設定K值過大時，若目標樣本的局部密度較大，則會增加非同類樣本選為目標樣本殼近鄰集的概率，降低了算法預測的準確度。當K值過小時，若目標樣本的局部密度較小，會使目標樣本的SNN集合出現空集，導致預測結果不理想或者無法預測目標樣本的類別。因此，依據樣本的局部密度，實現K值的適當調節有利于提高SNN算法的預測性能。

2 AK-SNN算法介紹

根據目標樣本在訓練集中的局部密度和近鄰數K兩個因素對SNN算法預測性能的影響，提出一種基于局部密度和相似度的自適應SNN算法（AK-SNN）。該算法中，為保障AK-SNN所選擇的近鄰樣本與目標樣本之間的相似度，將相似度與SNN算法相結合的方法以提高獲取近鄰樣本的可靠程度，并根據目標樣本的局部密度實現SNN的K值自適應調節以增強算法的預測能力。

2.1 相似度計算

余弦相似度（Cosine similarity）作為樣本相似度的衡量指標，通過計算兩個樣本向量夾角的余弦值評估兩個樣本之間的相似性，其計算公式如下：

2.2局部密度

局部密度（Local density），表示局部范圍內樣本分布的密集程度[11]。目標樣本具有越高的局部密度，則說明在固定的截斷范圍內，具有更多的樣本。對于目標樣本Xo，其局部密度計算方法如公式（3）和（4）。

公式中，Dcutoff代表截斷距離，D（Xo， XT）表示目標樣本Xo與樣本XT之間的絕對距離，并通過公式（1）計算獲得，N表示數據集D中的樣本個數。

在SNN算法預測過程中，當近鄰數K的大小憑經驗確定后，目標樣本不同的局部密度會導致所獲取的殼近鄰樣本質量的差異。當目標樣本的局部密度較高時，這使得周圍的近鄰樣本較多，大大增加非同類樣本的選中概率，因此，K值應適當減小以提高選中樣本的可靠程度。相反，當局部密度較低時，為防止因殼近鄰集為空集而導致的SNN算法失效，K值應適當增加。本文中，為保障SNN算法在不同密度下實現自適應的調節K的大小，設定了不同密度下的K值調節標準。在調節標準中，將數據集的全局平均密度作為K值調節的參考依據，當目標樣本的局部密度處于設定的密度區間時，K值進行加減2或4的操作，以防止K出現偶數，影響SNN的預測。K值調節標準如表1。

3 實驗

為驗證算法的性能，在不同數據集下將該算法與KNN、SNN做性能對比實驗。選擇4組UCI數據集，并將每組數據集的90%作為實驗的訓練集，10%作為測試集，并利用測試集用于檢驗算法的性能。實驗中，分別使用KNN算法、SNN算法和AK-SNN算法對測試集進行類別預測。表2中展示的是所用數據集信息。

3.1 實驗結果

使用不同的數據集Balance scale、Biodeg[12]、Parkinson multiple sound Recording[13]和Wisconsin diagnostic breast cancer，將對比算法KNN和SNN，以及AK-SNN在K值初設值固定的條件下，進行了10次獨立重復實驗，以降低實驗的偶然性，并將三種算法的準確度求取平均值。10次獨立試驗的預測結果展示在圖2的（a），（b），（c），（d）中，圖中橫坐標表示獨立試驗的次數，縱坐標表示算法的預測準確度。

從圖2展示的實驗結果中可以分析得出，在10次獨立實驗中，三種算法在準確度、度上均有所浮動。其中KNN算法在預測準確度上最低，產生了較為明顯的上下浮動。由于SNN克服了KNN算法在最近鄰樣本選擇上的偏好問題，使得SNN算法相比較于KNN具有較高準確度，并且具有較小的上下浮動。AK-SNN算法在實驗中取得了高于對比算法的預測精度，具有較小的上下浮動。相比于SNN算法和KNN算法，AK-SNN算法利用相似度保障了樣本之間的相似性，并通過目標樣本的局部密度，實現對K值的自適應調節，使得算法具有較高的預測準確度和較強的魯棒性。

分別計算不同數據集在不同算法下10次獨立重復實驗獲得預測結果的平均準確度，結果如表3所示。

從表3中可以了解到，AK-SNN算法在4種不同那個的數據集上分別取得了0.8406，0.8979，0.8578和0.9373的平均預測準確度，并且算法在4種數據集上均取得了優于KNN和SNN算法的預測平均準確度。

4 結論

鑒于近鄰數K對SNN算法預測準確度的直接影響，為提高算法整體分類性能，提出一種基于局部密度和相似度的自適應SNN算法。一方面，利用目標樣本的局部密度，并根據設定的調節策略實現對K值的自適應調節;另一方面，利用相似度，確保了所選近鄰樣本與目標樣本之間的相似性。實驗結果顯示，AK-SNN算法，在不同數據集和不同特征個數的條件下，具有較高的預測精度。此外，相比較于SNN和KNN算法，該算法具有良好的魯棒性。

參考文獻：

[1] Rani P.A Review of various KNN Techniques[J].International Journal for Research in Applied Science and Engineering Technology，2017，V（VIII）：1174-1179.

[2] 李詩語，王峰，曹彬，等.基于KNN算法的手寫數字識別[J].電腦知識與技術，2017，13（25）：175-177.

[3] Abu Alfeilat H A，Hassanat A B A，Lasassmeh O，et al.Effects of distance measure choice on K-nearest neighbor classifier performance：a review[J].Big Data，2019，7（4）：221-248.

[4] 周靖，劉晉勝.基于特征熵相關度差異的KNN算法[J].計算機工程，2011，37（17）：146-148.

[5] 黃光華，殷鋒，馮九林.一種交叉驗證和距離加權方法改進的KNN算法研究[J].西南民族大學學報（自然科學版），2020，46（2）：172-177.

[6] 張兵，蒙祖強，沈亮亮，等.基于局部密度和純度的自適應k近鄰算法[J].廣西科學院學報，2017，33（1）：19-24.

[7] 茹強喜，劉永.一種提高K近鄰分類的新方法[J].電腦知識與技術，2010，6（8）：1989-1991.

[8] Xiao X ， Ding H . Enhancement of K-nearest neighbor algorithm based on weighted entropy of attribute value[M]. 2012.

[9] Zhang S C.Shell-neighbor method and its application in missing data imputation[J].Applied Intelligence，2011，35（1）：123-133.

[10] Huawen Liu， Xindong Wu， Shichao Zhang. Neighbor selection for multilabel classification[M]. Elsevier Science Publishers B. V. 2016.

[11] 黎雋男，呂佳.基于近鄰密度和半監督KNN的集成自訓練方法[J].計算機工程與應用，2018，54（20）：132-138.

[12] Mansouri K，Ringsted T，Ballabio D，et al.Quantitative structure–activity relationship models for ready biodegradability of chemicals[J].Journal of Chemical Information and Modeling，2013，53（4）：867-878.

[13] Sakar B E，Isenkul M E，Sakar C O，et al.Collection and analysis of a Parkinson speech dataset with multiple types of sound recordings[J].IEEE Journal of Biomedical and Health Informatics，2013，17（4）：828-834.

【通聯編輯：唐一東】