李士果 盧建云 鄧劍勛

摘 要：在實際應用中，近鄰技術具有簡單、快速、高效的特點，受到研究人員的青睞。近來自然最近鄰被提出并應用到離群檢測和聚類中，鑒于自然最近鄰消除了參數k設置的特點，本文將自然最近鄰的概念應用到逆k最近鄰、互k最近鄰、共享k最近鄰中，提出了自然逆最近鄰、自然互最近鄰和自然共享最近鄰。并將提出的3種算法在離群點檢測中進行了實驗對比分析。實驗結果表明自然逆最近鄰和自然互最近鄰能夠有效發(fā)現局部和全局離群點。

關鍵詞：近鄰技術;離群點檢測;自然最近鄰;數據挖掘

文章編號：2095-2163（2019）04-0040-06 中圖分類號：TP391 文獻標志碼：A

0 引 言

近鄰技術是數據挖掘和機器學習的重要技術之一，被廣泛地應用到分類、聚類、異常檢測、協(xié)同過濾、圖像處理等研究領域。在實際應用中，近鄰技術具有簡單、快速、高效的特點，一直以來受到研究人員的重視。目前存在的近鄰技術有k最近鄰、互k最近鄰、逆k最近鄰、共享最近鄰、自然最近鄰。這些近鄰技術各有特點，自提出以來都得到了廣泛的應用。近來自然最近鄰被應用到離群檢測和聚類中，并取得了比較好的效果。鑒于自然最近鄰能夠消除參數k設置，本文將自然最近鄰這一特點應用到其它近鄰中，提出了自然逆最近鄰、自然互最近鄰、自然共享最近鄰的概念，并給出了相應的算法描述。在離群檢測應用中，對提出的自然逆最近鄰、自然互最近鄰、自然共享最近鄰算法進行了實驗對比分析，實驗結果表明自然逆最近鄰和自然互最近鄰能夠有效發(fā)現局部和全局離群點。

本文的主要貢獻如下：

（1）結合自然最近鄰消除參數k設置的特點，提出了無參的自然逆最近鄰、自然互最近鄰、自然共享最近鄰的概念，并給出了相應的算法描述;

（2）在離群檢測應用中，對提出的算法進行了實驗對比分析，實驗結果表明自然逆最近鄰和自然互最近鄰能夠有效地檢測局部和全局離群點。

1 相關研究

最近鄰概念直觀、簡單，認為一個對象與離其最近的對象具有相同的特點，最初被應用于基于示例的學習方法中。從概率的角度出發(fā)，可以通過多個對象投票的方式來確定被分類模式的標簽，則引入了k最近鄰的概念。k最近鄰有非常廣泛的用途，例如模式分類、機器學習、數據挖掘等領域[1]。在模式分類中，k最近鄰作為分類器對待識別模式進行分類，考慮每個近鄰的貢獻不同，出現了基于權重的kNN[2]分類方法。在圖像分割中，kNN與貝葉斯網絡結合，出現了貝葉斯kNN圖像分割算法[3]，還有kNN作為啟發(fā)的區(qū)域迭代的圖像分割算法[4]。在數據挖掘中，k最近鄰與距離結合衡量數據集中對象的密度，被用來進行離群點檢測。對于聚類應用，k個最近鄰能夠形成子圖，通過相似度度量函數，不斷合并相似的子圖，直到滿足需要得到的子圖數目，從而實現聚類。互k最近鄰比k最近鄰要嚴格，加入了一個限制條件，即要求2個對象p和q出現在對方的k最近鄰域，則p和q為互k最近鄰。通常，構建的互k最近鄰圖更加緊密，常被應用到去噪、分類中[5]。共享k最近鄰進一步考慮了對象p和q鄰域共有的近鄰數目，采用量化的方法來度量兩個對象的相似程度，常被應用到離群檢測、聚類中[6]。逆k最近鄰與k最近鄰具有相反的概念，是考慮一個對象對其周圍對象的影響，被應用于決策支持、資源定位與營銷等研究領域[7]。目前，對逆k最近鄰的研究主要集中在如何高效地進行搜索[8]。

最近提出的自然最近鄰概念具有自適應的特點，不需要顯示地指定參數k的值，而是通過迭代計算得到給定數據集的自適應k值。自然最近鄰被應用到高維數據結構學習、離群檢測、分類、聚類等場景[9]。自然最近鄰在形成的過程中，帶有密度信息和離群信息，能夠被應用到局部密度估計和離群檢測[10]。

2 近鄰技術

本節(jié)中，給出了互k最近鄰、逆k最近鄰、共享k最近鄰和自然最近鄰的定義，并對各種近鄰的特點進行了分析。

2.1 互k最近鄰

在k最近鄰的基礎上，增加一個限制條件，即2個對象要互為k最近鄰，這就是互k最近鄰的思想。2個對象互為k最近鄰，恰恰反應了2個對象之間的緊密程度。相對于k最近鄰反映的是單邊關系，而互k最近鄰描述的是一種雙邊關系。

2.2 逆k最近鄰

求解k最近鄰時，一個對象總是返回k個最近鄰，每個對象擁有最近鄰的數目是不變的。在實際應用中，對于密度度量，處于稀疏空間的對象并不總是有k個最近鄰。逆k最近鄰是與k最近鄰具有相反含義的一種最近鄰概念。k最近鄰反應的是查詢對象離某個被查詢對象最近，而逆k最近鄰描述的是被查詢對象對數據集中其它查詢對象的影響，被查詢對象能夠影響的對象數目可能有一個、多個或者是沒有。

2.3 共享k最近鄰

互k最近鄰描述了2個對象之間的相近或緊密程度。這種度量關系比較簡單，只有緊密、不緊密，或者相近、不相近這樣的二元關系。共享k最近鄰突破了這種二元關系，采用一種可以量化的度量方法，即衡量2個對象共有最近鄰的數目，這種量化度量方式很好地表達了相對程度。

2.4 自然最近鄰

在k近鄰技術中，參數k是需要設置的，對于不同的應用場景，參數k的設置也不盡相同，往往通過經驗分析得到合適的參數值。為了減輕參數k對最近鄰計算結果的影響，鄒咸林等人提出了自然最近鄰概念[9]。求解自然最近鄰時，不需要指定參數k或者鄰域半徑ε，其是一種無尺度的最近鄰概念。求解自然最近鄰的核心思想是設置計算的終止條件，整個計算過程是對給定數據集的一個自適應過程，當迭代計算收斂時，得到數據集中每個對象的自然最近鄰。自然最近鄰數目是一種量化的度量方法，能夠反映數據集疏密分布情況。求解自然最近鄰的方式可以有多種，表現為迭代計算的終止條件不同。

3 自然最近鄰在其它近鄰中的應用

本節(jié)中，給出了自然逆最近鄰、自然互最近鄰和自然共享最近鄰的定義和算法描述。自然最近鄰概念的要點是“數據集中最離群的數據對象都至少有一條路徑到達”，這個特點使得每個對象具有不固定尺度的近鄰數目，也減輕了參數k對最終近鄰數目的影響。

3.1 自然最近鄰定義

在定義7中，自然共享最近鄰不是指2個對象p和q共有的近鄰對象，而是指p和q的一種關系，如果p和q共有的近鄰數目大于等于m，則p和q是一種自然共享最近鄰的關系。下面給出定義5到定義7的算法實現描述。

3.2 自然最近鄰算法描述

算法1 自然逆最近鄰算法（NRNN）

輸入：數據集D包含n個對象

輸出：D中每個對象的自然逆最近鄰數目

算法描述如下：

初始化變量r=1，向量nrnn（i）=0，0

while r

for each p in D

計算p的第r最近鄰q;

nrnn（q）=nrnn（q）+1;

if all（nrnn（i）≠0）

r = 0;

else

r=r+1

end

在算法1中，第5行給出了算法的終止條件，即數據集D中的每個對象都至少有一個逆最近鄰。在實際應用中，對于包含一些相對離群對象的數據集，算法的收斂性變的很差。因此，在算法的具體實現中，加入了另外一個終止條件，即在迭代過程中數據集中沒有逆最近鄰的數據對象的數目連續(xù)兩次沒有變化，則算法停止。該終止條件對算法的本質并沒有影響，因為算法的目的是統(tǒng)計數據集中對象的逆最近鄰數目，逆最近鄰數目反映了數據對象的密度分布信息。算法提前終止說明數據集中的一些對象處于相對稀疏的區(qū)域，這對數據集整體的密度分布并沒有影響。在下面2個算法的具體實現中，也加入了類似的終止條件。

算法2 自然互最近鄰算法（NMNN）

輸入：數據集D包含n個對象

輸出：D中每個對象的自然互最近鄰數目

算法描述如下：

初始化變量r=1，向量nmnn（i）=0，0

while r

for each p in D

計算p的第r最近鄰q;

end

for each p，q in D

if ismember（p，rNN（q）） and ismember（q，rNN（p））

nmnn（p）=nmnn（p）+1

nmnn（q）=nmnn（q）+1

if all（nmnn（i）≠0）

r = 0;

else

r = r + 1;

end

end

在算法2中，第7行的if條件中函數ismember（p，rNN（q））表示對象p是對象q的r最近鄰，函數ismember（q，rNN（p））表示q是p的r最近鄰，當這2個條件同時成立，p和q為互最近鄰。第10行是算法的終止條件，即數據集中的每個對象都至少有一個互最近鄰。

算法3 自然共享最近鄰算法（NSNN）

輸入：數據集D包含n個對象

輸出：D中每個對象的自然共享最近鄰數目

初始化變量r=m，向量nsnn（i）=0，0

while r

for each p in D

計算p的第r最近鄰q;

end

for each p，q in D

snn=intersect（rNN（p），rNN（q））

if length（snn）>m

nsnn（p）=nmnn（p）+1

nsnn（q）=nmnn（q）+1

if all（nsnn（i）≠0）

r = 0;

else

r = r + 1;

end

end

在算法3中，第7行函數intersect（rNN（p），rNN（q））為計算對象p和對象q的共享最近鄰數目，第8行判斷該數目是否大于閾值m，如果成立，p和q為自然共享最近鄰。第11行是算法的終止條件，即數據集中每個對象至少有另外一個對象與其的共享最近鄰數目是大于等于m的。

4 實驗與結果

本節(jié)將上述提出的3種自然最近鄰算法在離群檢測應用中進行了實驗對比分析。

4.1 實驗數據集

本次實驗采用了2個人工合成數據集DS1和DS2，分布包含6個、11個離群點。實驗數據集的具體信息見表1。

4.2 評價指標

采用精確率（Precision）、召回率（Recall）和F-Measure對3種算法的實驗結果進行評價，3種評價指標的解釋如下：

精確率=（表示模型預測為所有正樣本數量中真正為正樣本的比例）;

召回率=（表示模型準確預測為正樣本的數量占所有正樣本數量的比例）;

F-Measure =（a2+1）（精確率*召回率）a2（精確率+召回率）

當a=1時，F1 = 2*（精確率*召回率）/（精確率+召回率）。

4.3 實驗和結果

通過2個實驗對3種自然最近鄰算法NRNN、NMNN和NSNN進行對比分析。第一個實驗分析3種自然最近鄰數目在DS1和DS2數據集上的統(tǒng)計分布情況，如圖1和圖2所示。統(tǒng)計3種自然最近鄰數目分布的目的，是通過分布反映數據集中對象所在區(qū)域的疏密情況。通常情況下，擁有很多自然最近鄰的對象處于數據集中比較密集的區(qū)域，具有很少自然最近鄰的對象位于數據集中相對稀疏的區(qū)域，這與利用密度進行離群檢測的方法吻合，通常離群點是位于數據集中相對稀疏的區(qū)域。

圖1顯示了NRNN、NMNN和NSNN在DS1數據集上的統(tǒng)計分布。由此可以看出，當r值為5時，NRNN算法收斂，此時DS1中不是每個數據對象都至少有一個自然逆最近鄰。算法收斂是因為在連續(xù)2次迭代的過程中，沒有自然逆最近鄰的對象數目沒有變化。同理，在r值為6時，NMNN算法收斂。NSNN算法設置的共享最近鄰數目閾值為9，當r值為14時，DS1中每個對象都至少有一個自然共享最近鄰。

圖2顯示了NRNN、NMNN和NSNN 3種算法在DS2數據集上的統(tǒng)計分布?？梢钥闯?，NRNN算法在r=6時收斂，收斂時，數據集中仍有幾個對象沒有自然逆最近鄰。當r取值為9時，NMNN算法收斂，此時數據集中的所有對象都至少有一個自然互最近鄰。對于NSNN算法，共享最近鄰數目閾值設置為9，當r值為15時，NSNN算法收斂，此時，數據集中仍有幾個對象沒有自然共享最近鄰。

離群點通常處于數據集中稀疏的區(qū)域，根據自然最近鄰數目在數據集上的分布，通過設置閾值找到擁有相對少的自然最近鄰數目的對象，從而實現離群檢測。實驗對比結果見表2和表3。

從表2可以看出， NRNN和NMNN能夠取得100%的精確率和召回率，NRNN在閾值小于2時，F1指標為100%，NMNN在閾值小于5時，F1指標為100%。通過整體對比，NRNN略優(yōu)于NMNN。NSNN在精確率、召回率和F1指標上的結果都相對比較低。

分析表3得出，NMNN在閾值小于17時，取得了100%的精確率和召回率，整體來看，NMNN略優(yōu)于NRNN。NSNN在閾值小于5時，取得了100%的精確率，但只有27.3%的召回率，說明挖掘出的離群點很少。NSNN閾值小于11時，取得了81.8%的召回率。

總體來看，NMNN和NRNN在離群檢測應用中取得了比較好的效果，NSNN在DS2數據集上可以實現離群檢測，但在DS1數據集上表現不太理想，這與數據集中數據分布的相對密度有關。NRNN傾向于發(fā)現處于稀疏區(qū)域和處于數據集外邊緣的對象，NMNN能夠發(fā)現位于稀疏區(qū)域和數據集內邊緣的對象，NSNN檢測出的數據對象相對比較集中。

5 結束語

本文從概念上對目前存在的近鄰技術進行了對比分析，對各種近鄰技術的特點進行了剖析。結合自然最近鄰概念，提出了自然逆最近鄰、自然互最近鄰和自然共享最近鄰3種算法，并給出了3種算法的定義和算法描述。對提出的算法在離群檢測應用中進行了實驗對比，實驗結果表明自然逆最近鄰和自然互最近鄰能夠有效地檢測出局部和全局離群點，自然共享最近鄰與數據集中數據的相對分布密度有關，檢測出的對象相對比較集中。

參考文獻

[1]毋雪雁， 王水花， 張煜東. K最近鄰算法理論與應用綜述[J]. 計算機工程與應用， 2017， 53（21）：1-7.

[2]黃文明， 莫陽. 基于文本加權KNN算法的中文垃圾短信過濾[J]. 計算機工程， 2017， 43（3）：193-199.

[3]張旭， 蔣建國， 洪日昌， 等. 基于樸素貝葉斯K近鄰的快速圖像分類算法[J]. 北京航空航天大學學報， 2015， 41（2）：302-310.

[4]管建， 亞娟， 王立功. K近鄰分類指導的區(qū)域迭代圖割算法研究[J]. 計算機應用與軟件，2018，35（11）：237- 244，265.

[5]盧偉勝， 郭躬德， 嚴宣輝， 等. SMwKnn：基于類別子空間距離加權的互k近鄰算法[J]. 計算機科學， 2014， 41（2）：166-169.

[6]蘇曉珂， 鄭遠攀， 萬仁霞. 基于共享最近鄰的離群檢測算法[J]. 計算機應用研究， 2012， 29（7）：2426-2428，2453.

[7]KORN F， MUTHUKRISHNAN S. Influence sets based on reverse nearest neighbor queries [J]. ACM SIGMOD Record， 2000， 29（2）：201-212.

[8]GAO Yunjun， LIU Qing， MIAO Xiaoye， et al. Reverse k -nearest neighbor search in the presence of obstacles[J]. Information Sciences， 2016， 330：274-292.

[9]鄒咸林. 自然最近鄰居在高維數據結構學習中的應用[D]. 重慶：重慶大學， 2011.

[10]朱慶生， 唐匯， 馮驥. 一種基于自然最近鄰的離群檢測算法[J]. 計算機科學， 2014， 41（3）：276-278， 305.