劉娜　生龍

摘要：在近鄰算法中，近鄰樣本和目標(biāo)樣本之間的絕對(duì)距離和相似性為目標(biāo)樣本類(lèi)別的判斷提供重要的決策依據(jù)，K值的大小也會(huì)直接決定了近鄰算法的預(yù)測(cè)效果。然而，SNN算法在預(yù)測(cè)過(guò)程中，使用固定的經(jīng)驗(yàn)K值來(lái)預(yù)測(cè)不同局部密度的目標(biāo)樣本，具有一定的片面性。因此，為實(shí)現(xiàn)SNN算法中K值的合理調(diào)節(jié)，提高算法的預(yù)測(cè)準(zhǔn)確度和穩(wěn)定性，提出一種基于局部密度和相似度的自適應(yīng)SNN算法（AK-SNN）。算法的性能在UCI數(shù)據(jù)集上進(jìn)行驗(yàn)證，結(jié)果顯示該算法取得優(yōu)于KNN和SNN的預(yù)測(cè)效果和魯棒性。

關(guān)鍵詞：KNN;SNN;相似度計(jì)算;局部密度;自適應(yīng);AK-SNN

中圖分類(lèi)號(hào)： TP301? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：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

引言

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

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

在傳統(tǒng)SNN算法中，K值的大小對(duì)算法性能依然具有較大影響，并且該算法不具備K值的自動(dòng)調(diào)節(jié)能力。為實(shí)現(xiàn)對(duì)近鄰數(shù)K的優(yōu)化選取并保障所選近鄰樣本的相似性，提出一種基于局部密度和相似度的自適應(yīng)SNN算法（AK-SNN）。

1 相關(guān)工作

1.1 KNN算法

KNN算法由Cover和Hart提出，通過(guò)距離將與目標(biāo)樣本最靠近的k個(gè)訓(xùn)練集樣本選擇出來(lái)，用來(lái)預(yù)測(cè)目標(biāo)樣本的種類(lèi)。該算法的距離計(jì)算使用歐氏距離，歐氏距離代表的是不同樣本在空間分布中的相對(duì)位置，歐氏距離越小，表示不同樣本之間在空間分布上距離越近，其公式如下：

上圖中，菱形表示負(fù)類(lèi)樣本，正方形表示正類(lèi)樣本，三角形表示目標(biāo)樣本。利用KNN算法是對(duì)目標(biāo)樣本預(yù)測(cè)，K=3時(shí)，最靠近目標(biāo)樣本的3個(gè)訓(xùn)練集樣本中存在2個(gè)負(fù)類(lèi)樣本和1個(gè)正類(lèi)樣本，因此根據(jù)多數(shù)類(lèi)投票機(jī)制目標(biāo)樣本的預(yù)測(cè)類(lèi)別為負(fù)類(lèi);當(dāng)K=7時(shí)，最靠近目標(biāo)樣本的7個(gè)訓(xùn)練集樣本中存在4個(gè)正類(lèi)樣本和3個(gè)負(fù)類(lèi)樣本，則目標(biāo)樣本類(lèi)別被預(yù)測(cè)為正類(lèi)。

1.2 SNN算法

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

SNN算法的具體步驟如下：

1） 初始化訓(xùn)練集D，目標(biāo)樣本和近鄰數(shù)K。

2） 對(duì)于目標(biāo)樣本Xo，根據(jù)公式1）計(jì)算訓(xùn)練集D與其最近的k個(gè)樣本，構(gòu)成目標(biāo)樣本的K近鄰集KNN（Xo， K）。

3） 根據(jù)目標(biāo)樣本的第i個(gè)特征（i = 1， 2，... ，q），在訓(xùn)練集中計(jì)算目標(biāo)樣本第i個(gè)特征下的最左和最右近鄰樣本，構(gòu)成特征最近鄰集SD（Xoi）。

4） 根據(jù)3）中的方式，獲得目標(biāo)樣本Xo的q個(gè)特征的最左和最右近鄰，構(gòu)成Xo的特征最近鄰集SD（Xo）。

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

6） 根據(jù)殼近鄰集SN（Xo），預(yù)測(cè)目標(biāo)樣本Xo的類(lèi)別。

由于SNN算法解決了KNN算法的選擇偏好問(wèn)題，多數(shù)情況該算法也取得了良好的預(yù)測(cè)效果。但在實(shí)際運(yùn)行中，當(dāng)人為設(shè)定K值過(guò)大時(shí)，若目標(biāo)樣本的局部密度較大，則會(huì)增加非同類(lèi)樣本選為目標(biāo)樣本殼近鄰集的概率，降低了算法預(yù)測(cè)的準(zhǔn)確度。當(dāng)K值過(guò)小時(shí)，若目標(biāo)樣本的局部密度較小，會(huì)使目標(biāo)樣本的SNN集合出現(xiàn)空集，導(dǎo)致預(yù)測(cè)結(jié)果不理想或者無(wú)法預(yù)測(cè)目標(biāo)樣本的類(lèi)別。因此，依據(jù)樣本的局部密度，實(shí)現(xiàn)K值的適當(dāng)調(diào)節(jié)有利于提高SNN算法的預(yù)測(cè)性能。

2 AK-SNN算法介紹

根據(jù)目標(biāo)樣本在訓(xùn)練集中的局部密度和近鄰數(shù)K兩個(gè)因素對(duì)SNN算法預(yù)測(cè)性能的影響，提出一種基于局部密度和相似度的自適應(yīng)SNN算法（AK-SNN）。該算法中，為保障AK-SNN所選擇的近鄰樣本與目標(biāo)樣本之間的相似度，將相似度與SNN算法相結(jié)合的方法以提高獲取近鄰樣本的可靠程度，并根據(jù)目標(biāo)樣本的局部密度實(shí)現(xiàn)SNN的K值自適應(yīng)調(diào)節(jié)以增強(qiáng)算法的預(yù)測(cè)能力。

2.1 相似度計(jì)算

余弦相似度（Cosine similarity）作為樣本相似度的衡量指標(biāo)，通過(guò)計(jì)算兩個(gè)樣本向量夾角的余弦值評(píng)估兩個(gè)樣本之間的相似性，其計(jì)算公式如下：

2.2局部密度

局部密度（Local density），表示局部范圍內(nèi)樣本分布的密集程度[11]。目標(biāo)樣本具有越高的局部密度，則說(shuō)明在固定的截?cái)喾秶鷥?nèi)，具有更多的樣本。對(duì)于目標(biāo)樣本Xo，其局部密度計(jì)算方法如公式（3）和（4）。

公式中，Dcutoff代表截?cái)嗑嚯x，D（Xo， XT）表示目標(biāo)樣本Xo與樣本XT之間的絕對(duì)距離，并通過(guò)公式（1）計(jì)算獲得，N表示數(shù)據(jù)集D中的樣本個(gè)數(shù)。

在SNN算法預(yù)測(cè)過(guò)程中，當(dāng)近鄰數(shù)K的大小憑經(jīng)驗(yàn)確定后，目標(biāo)樣本不同的局部密度會(huì)導(dǎo)致所獲取的殼近鄰樣本質(zhì)量的差異。當(dāng)目標(biāo)樣本的局部密度較高時(shí)，這使得周?chē)慕彉颖据^多，大大增加非同類(lèi)樣本的選中概率，因此，K值應(yīng)適當(dāng)減小以提高選中樣本的可靠程度。相反，當(dāng)局部密度較低時(shí)，為防止因殼近鄰集為空集而導(dǎo)致的SNN算法失效，K值應(yīng)適當(dāng)增加。本文中，為保障SNN算法在不同密度下實(shí)現(xiàn)自適應(yīng)的調(diào)節(jié)K的大小，設(shè)定了不同密度下的K值調(diào)節(jié)標(biāo)準(zhǔn)。在調(diào)節(jié)標(biāo)準(zhǔn)中，將數(shù)據(jù)集的全局平均密度作為K值調(diào)節(jié)的參考依據(jù)，當(dāng)目標(biāo)樣本的局部密度處于設(shè)定的密度區(qū)間時(shí)，K值進(jìn)行加減2或4的操作，以防止K出現(xiàn)偶數(shù)，影響SNN的預(yù)測(cè)。K值調(diào)節(jié)標(biāo)準(zhǔn)如表1。

3 實(shí)驗(yàn)

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

3.1 實(shí)驗(yàn)結(jié)果

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

從圖2展示的實(shí)驗(yàn)結(jié)果中可以分析得出，在10次獨(dú)立實(shí)驗(yàn)中，三種算法在準(zhǔn)確度、度上均有所浮動(dòng)。其中KNN算法在預(yù)測(cè)準(zhǔn)確度上最低，產(chǎn)生了較為明顯的上下浮動(dòng)。由于SNN克服了KNN算法在最近鄰樣本選擇上的偏好問(wèn)題，使得SNN算法相比較于KNN具有較高準(zhǔn)確度，并且具有較小的上下浮動(dòng)。AK-SNN算法在實(shí)驗(yàn)中取得了高于對(duì)比算法的預(yù)測(cè)精度，具有較小的上下浮動(dòng)。相比于SNN算法和KNN算法，AK-SNN算法利用相似度保障了樣本之間的相似性，并通過(guò)目標(biāo)樣本的局部密度，實(shí)現(xiàn)對(duì)K值的自適應(yīng)調(diào)節(jié)，使得算法具有較高的預(yù)測(cè)準(zhǔn)確度和較強(qiáng)的魯棒性。

分別計(jì)算不同數(shù)據(jù)集在不同算法下10次獨(dú)立重復(fù)實(shí)驗(yàn)獲得預(yù)測(cè)結(jié)果的平均準(zhǔn)確度，結(jié)果如表3所示。

從表3中可以了解到，AK-SNN算法在4種不同那個(gè)的數(shù)據(jù)集上分別取得了0.8406，0.8979，0.8578和0.9373的平均預(yù)測(cè)準(zhǔn)確度，并且算法在4種數(shù)據(jù)集上均取得了優(yōu)于KNN和SNN算法的預(yù)測(cè)平均準(zhǔn)確度。

4 結(jié)論

鑒于近鄰數(shù)K對(duì)SNN算法預(yù)測(cè)準(zhǔn)確度的直接影響，為提高算法整體分類(lèi)性能，提出一種基于局部密度和相似度的自適應(yīng)SNN算法。一方面，利用目標(biāo)樣本的局部密度，并根據(jù)設(shè)定的調(diào)節(jié)策略實(shí)現(xiàn)對(duì)K值的自適應(yīng)調(diào)節(jié);另一方面，利用相似度，確保了所選近鄰樣本與目標(biāo)樣本之間的相似性。實(shí)驗(yàn)結(jié)果顯示，AK-SNN算法，在不同數(shù)據(jù)集和不同特征個(gè)數(shù)的條件下，具有較高的預(yù)測(cè)精度。此外，相比較于SNN和KNN算法，該算法具有良好的魯棒性。

參考文獻(xiàn)：

[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] 李詩(shī)語(yǔ)，王峰，曹彬，等.基于KNN算法的手寫(xiě)數(shù)字識(shí)別[J].電腦知識(shí)與技術(shù)，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] 周靖，劉晉勝.基于特征熵相關(guān)度差異的KNN算法[J].計(jì)算機(jī)工程，2011，37（17）：146-148.

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

[6] 張兵，蒙祖強(qiáng)，沈亮亮，等.基于局部密度和純度的自適應(yīng)k近鄰算法[J].廣西科學(xué)院學(xué)報(bào)，2017，33（1）：19-24.

[7] 茹強(qiáng)喜，劉永.一種提高K近鄰分類(lèi)的新方法[J].電腦知識(shí)與技術(shù)，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] 黎雋男，呂佳.基于近鄰密度和半監(jiān)督KNN的集成自訓(xùn)練方法[J].計(jì)算機(jī)工程與應(yīng)用，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.

【通聯(lián)編輯：唐一東】