基于自然鄰居的無參化實例約簡研究.pdf

1、實例約簡是基于實例的學習算法中的一個比較關鍵的任務?；趯嵗膶W習算法使用整個訓練集來構(gòu)造決策面，如果訓練集中包含過多的實例，就會造成算法在分類階段消耗大量的內(nèi)存空間和計算時間，甚至讓人無法忍受。實例約簡通過對訓練集進行約簡從而降低算法在分類階段的空間和時間消耗。k-最近鄰居分類是一種典型的基于實例的學習算法，因其直觀、簡單和易用性等特點，在機器學習、數(shù)據(jù)挖掘和模式識別等鄰域中獲得了廣泛的應用，當前已經(jīng)成為數(shù)據(jù)挖掘領域的十大算法之一。k

2、-最近鄰居的實例約簡方法主要可以分為：裁剪的方法、壓縮的方法和混合的方法。
　　裁剪的方法通過刪除數(shù)據(jù)集對分類有害的數(shù)據(jù)（噪聲）來提高算法的分類精度。壓縮的方法則認為決策邊界上的數(shù)據(jù)包含了分類中的關鍵的信息，而遠離決策邊界的數(shù)據(jù)則包含少量的或者不包含決策信息。所以經(jīng)典的壓縮最近鄰居算法試圖通過最近鄰居決策對訓練集進行約簡，通過刪除那些能夠被最近鄰居準則正確分類的數(shù)據(jù)，從而獲得一個和訓練集一致的子集來代替原始訓練集進行分類。而混合的

3、方法則綜合了上述兩種算法的特性，通常來說，裁剪算法被用來作為數(shù)據(jù)的噪聲過濾器，去除噪聲、平滑決策邊界，然后再使用壓縮的算法對數(shù)據(jù)集進行約簡。
　　雖然當前實例約簡算法已經(jīng)取得了大量的成果，但是其面臨三個主要的問題：參數(shù)依賴問題、噪聲敏感問題和約簡率低的問題。為了克服以上問題，本文將自然鄰居概念引入到實例約簡中。自然鄰居是一種新的鄰居形式，它是一種無尺度的鄰居概念。每個數(shù)據(jù)點的自然鄰居可以由自然鄰居搜索算法自動獲得。自然鄰居的提出解

4、決了最近鄰居的鄰域參數(shù)選擇問題，但是其結(jié)構(gòu)也適合于處理最近鄰居思想所面臨的實例約簡問題。本文對自然鄰居在實例約簡中的應用進行了研究，主要創(chuàng)新和貢獻包括以下幾個方面：
　?。?）提出一種自適應的裁剪自然鄰居算法 ENaN，解決基于裁剪的實例約簡算法的參數(shù)依賴和噪聲敏感等問題。該算法通過刪除那些不能被自身的自然鄰居正確分類的點，從而對噪聲數(shù)據(jù)進行裁剪。自然鄰居無尺度的特性，使得 ENaN算法不需要參數(shù)。自然鄰居個數(shù)不固定的特性，使得

5、ENaN算法可以降低因為噪聲數(shù)據(jù)的影響所導致的誤刪，從而具有抗噪能力。最具代表性的實例裁剪算法就是裁剪自然鄰居算法ENN，它通過刪除那些不能被它的k-最近鄰居正確分類的點，從而對數(shù)據(jù)集進行去噪，以提高算法的分類精度。但是，ENN算法計算復雜性高，需要設置參數(shù) k，而且還對噪聲點敏感。ENaN算法解決了 ENN所遇到的上述問題。此外，自然鄰居算法的離群點檢測能力，使得 ENaN能夠刪除掉數(shù)據(jù)集中的全局離群點。以上特性使得新提出的算法能夠非

6、常容易的使用到其它約簡算法中作為預處理算法(噪聲過濾器)，用以去除噪聲和平滑決策邊界。
　?。?）提出一種融合自然鄰居的混合實例約簡算法 IRNN，解決基于壓縮的實例約簡算法的參數(shù)依賴、噪聲敏感和壓縮率低的問題。該算法使用自然鄰居暗含的密度信息來搜索數(shù)據(jù)集核心點，使用約束最近鄰居鏈來查找邊界點?；趬嚎s的實例約簡算法認為處于決策邊界附近的點對分類精度的貢獻最大，而遠離決策邊界的點對分類精度的貢獻非常弱。因此，基于壓縮的實例約簡算法

7、通過保留決策邊界附近的點，而刪除遠離決策邊界的點，來對數(shù)據(jù)集進行壓縮。但是，通過大量的實驗發(fā)現(xiàn)，雖然邊界點含有的信息在決策中占主要地位，但是適當?shù)谋Ａ魞?nèi)部核心點可以極大的提高分類精度，特別是在數(shù)據(jù)集分布特別復雜的情況下。由于自然鄰居中隱含有密度信息，利用這些信息能夠?qū)?nèi)部核心點進行搜索。另外一方面，使用約束最近鄰居鏈對邊界點進行查找。最后，將核心點和邊界點融合起來，就構(gòu)成了最終的約簡集。該算法的優(yōu)點在于不需要參數(shù)，對噪聲不敏感。而且在極

8、大的提高算法的約簡率的同時能夠保證甚至提高精度。
　　（3）提出一種無參數(shù)的基于自然鄰域圖的實例約簡算法NNGIR，解決基于圖的實例約簡算法的約簡率低和參數(shù)依賴等問題。圖是一種常用的數(shù)據(jù)點之間關系表示的有效方式，被大量運用于聚類和流行學習中。當我們給一個圖的節(jié)點加上類別信息之后，圖結(jié)構(gòu)中就包含了我們所需要的決策信息。自然鄰居鄰域圖是一種自動生成的圖結(jié)構(gòu)，是一種擴展的最近鄰居鄰域圖。將帶標簽的自然鄰居鄰域圖應用到實例約簡中，定義了兩