自然鄰居思想概念及其在數(shù)據(jù)挖掘領(lǐng)域的應(yīng)用.pdf

1、近些年來，最近鄰居的概念與對應(yīng)的鄰居搜索算法在數(shù)據(jù)挖掘、圖像處理以及模式識別等多個(gè)領(lǐng)域中有著廣泛的應(yīng)用基礎(chǔ)并取得了許多令人滿意的結(jié)果。最近鄰居概念中近鄰關(guān)系的定義是最近鄰居思想的根本基礎(chǔ)，對該思想的各種方法起著決定性的作用。在眾多的近鄰關(guān)系中，最為廣泛應(yīng)用的無疑是 k-最近鄰居（KNN：k-Nearest Neighbor）和逆k最近鄰居（RkNN：Reverse k-Nearest Neighbor）。然而，無論是KNN還是RkNN，

2、最近鄰居的概念中始終縈繞著一個(gè)懸而未決的問題——如何選擇合適的鄰域大小。鄰域參數(shù)的最優(yōu)選擇并不固定，其取值通常依賴數(shù)據(jù)集自身的分布情況。比如在對數(shù)據(jù)集進(jìn)行分類操作時(shí)，較大的鄰域參數(shù)能夠減少噪聲點(diǎn)對分類結(jié)果的影響，但同時(shí)會模糊不同類之間的差異性。特別是當(dāng)數(shù)據(jù)集呈現(xiàn)流形分布時(shí)，過大的鄰域參數(shù)會造成短路的現(xiàn)象，對流形產(chǎn)生破壞。而與之相反，過小的鄰域參數(shù)會削弱數(shù)據(jù)間的鄰居關(guān)系，極端情況下則會將屬于同一個(gè)類的數(shù)據(jù)點(diǎn)分割到多個(gè)不同的區(qū)域中。

3、　　因此，在當(dāng)前基于最近鄰居思想的算法中，鄰域選擇問題成為了制約算法效率的重要部分。為了從根本上解決這個(gè)問題，本文提出了自然鄰居思想及其應(yīng)用。首先，論文提出了自然鄰居思想的基本概念。自然鄰居思想擺脫了鄰域參數(shù)選擇的難題，在自然鄰居的查找過程中自適應(yīng)的完成鄰居關(guān)系的構(gòu)建，同時(shí)獲得具有數(shù)據(jù)集特征信息的自然鄰居特征值和自然鄰居鄰域圖。
　　自然鄰居思想的主要特點(diǎn)為：
　　1)自然鄰居思想能根據(jù)不同數(shù)據(jù)集的局部特征創(chuàng)建對應(yīng)的自然鄰居

4、鄰域圖，其能夠直觀準(zhǔn)確地呈現(xiàn)數(shù)據(jù)分布規(guī)律，特別是流形數(shù)據(jù)和噪聲數(shù)據(jù)。
　　2)自然鄰居思想能夠?qū)Σ煌瑪?shù)據(jù)集自適應(yīng)得到自然鄰居特征值，而自然鄰居特征值能夠動態(tài)的反映不同數(shù)據(jù)集的分布狀態(tài)。
　　3)自然鄰居思想中每個(gè)數(shù)據(jù)點(diǎn)的鄰居數(shù)量是可變的，鄰居的多少反映了數(shù)據(jù)點(diǎn)與數(shù)據(jù)集的真實(shí)關(guān)系。
　　在自然鄰居思想的概念之上，論文提出了自然鄰居思想對傳統(tǒng)算法中鄰域參數(shù)選擇問題的解決辦法。自然鄰居思想中的自然鄰居特征值反映了數(shù)據(jù)集的分布

5、情況，因此其可以作為傳統(tǒng)最近鄰居思想中的鄰域參數(shù)k?；谠撍悸?，論文提出了自然鄰居特征值的快速計(jì)算算法，高效地計(jì)算自然鄰居特征值，進(jìn)而將其作為鄰域參數(shù)應(yīng)用于離群檢測、聚類分析等領(lǐng)域的多個(gè)算法中，并且取得了令人滿意的實(shí)驗(yàn)結(jié)果。
　　除了自然鄰居特征值之外，反映自然鄰居關(guān)系的自然鄰居鄰域圖也具有極強(qiáng)的研究價(jià)值。論文在最后提出了一種基于加權(quán)自然鄰居鄰域圖的數(shù)據(jù)挖掘算法，將自然鄰居查找過程中的查找深度作為自然鄰居鄰域圖中邊的權(quán)值構(gòu)造加權(quán)自