基于自然鄰居的無參化實(shí)例約簡(jiǎn)研究.pdf

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

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

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

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

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

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

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

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