自然最近鄰居在高維數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)中的應(yīng)用.pdf

1、對(duì)大規(guī)模高維數(shù)據(jù)結(jié)構(gòu)的分析和研究一直是數(shù)據(jù)挖掘、機(jī)器學(xué)習(xí)和模式識(shí)別等領(lǐng)域中十分重要的研究課題之一，同時(shí)也是現(xiàn)代科學(xué)技術(shù)所必須面對(duì)的困難之一。高維數(shù)據(jù)的結(jié)構(gòu)特征主要包括聚類結(jié)構(gòu)和流形結(jié)構(gòu)，所用到的研究方法涉及到了多個(gè)數(shù)學(xué)分支，如多元分析、非線性泛函分析及統(tǒng)計(jì)等，尋找簡(jiǎn)單而有效的方法是人們一直追求的目標(biāo)。因此對(duì)高維數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)具有十分重要的價(jià)值。
　　 本文提出了一種新的最近鄰居概念，自然最近鄰居(Natural Nearest

2、Neighbor：3N)，它是一種無尺度(scale-free)的最近鄰居，其核心的思想是最離群的數(shù)據(jù)對(duì)象只有一個(gè)最近鄰居或者說具有最低的能量，而稠密的對(duì)象有較多的鄰居或較高的能量，而且，自然最近鄰居的計(jì)算過程可以自動(dòng)地實(shí)現(xiàn)，這是本文的主要貢獻(xiàn)和創(chuàng)新。由自然最近鄰居可以自動(dòng)地形成一種自適應(yīng)的數(shù)據(jù)最近鄰域圖或數(shù)據(jù)網(wǎng)絡(luò)，借助復(fù)雜網(wǎng)絡(luò)的概念，這也是一種無標(biāo)度(scale-free)的網(wǎng)絡(luò)，這種鄰域圖或網(wǎng)絡(luò)可以很好地表示數(shù)據(jù)對(duì)象之間的關(guān)聯(lián)關(guān)系，

3、能夠明顯地給出各個(gè)數(shù)據(jù)對(duì)象的密度信息。自然最近鄰居的形成機(jī)制，能夠有效地降低跨邊界尋找最近鄰居的風(fēng)險(xiǎn)，因而可保持具有聚類結(jié)構(gòu)的數(shù)據(jù)的凝聚狀態(tài)，自然地展示出聚類數(shù)據(jù)的基礎(chǔ)結(jié)構(gòu)(infrastructure)，為后續(xù)的聚類和流形結(jié)構(gòu)分析提供一個(gè)稀疏和無參數(shù)的基礎(chǔ)圖模型。將這種自適應(yīng)鄰域圖用于流形學(xué)習(xí)算法，如Isomap、LLE、HLLE、LTSA等，可得到相應(yīng)的無自由參數(shù)的自適應(yīng)流形學(xué)習(xí)算法，避免了傳統(tǒng)流形學(xué)習(xí)算法中關(guān)于鄰域參數(shù)的選擇問題，

4、原因在于由自然最近鄰居所形成的鄰域圖能很好地逼近低維嵌入的數(shù)據(jù)流形。這為機(jī)器學(xué)習(xí)領(lǐng)域中的兩大熱點(diǎn)問題之一的維數(shù)約簡(jiǎn)(Dimensionality Reduction)方法提供了一個(gè)新的視角。
　　 本文還研究了離群數(shù)據(jù)對(duì)象的特征子空間結(jié)構(gòu)與聚類特征子空間結(jié)構(gòu)之間的關(guān)系，還提供了一種從鄰居的角度來觀察離群對(duì)象的行為。
　　 本文的主要?jiǎng)?chuàng)新和貢獻(xiàn)包括如下幾個(gè)方面。
　　 (1)提出了自然最近鄰居(3N)的概念，并提供

5、了一個(gè)十分簡(jiǎn)單的計(jì)算方法。在標(biāo)準(zhǔn)分布(均勻分布、正態(tài)分布)及規(guī)則數(shù)據(jù)集上驗(yàn)證了這種鄰居概念的合理性。與k-最近鄰居和ε-最近鄰居相比含有更豐富的信息：如密度、離群信息以及結(jié)構(gòu)逼近等。從自然最近鄰居數(shù)目的分布(直方圖)可以觀察數(shù)據(jù)集的分布狀態(tài)，這種分布與數(shù)據(jù)集的高維特性無關(guān)。
　　 (2)將自適應(yīng)鄰域圖用于代表性的流形學(xué)習(xí)算法：如全局結(jié)構(gòu)流形學(xué)習(xí)算法Isomap和局部結(jié)構(gòu)流形學(xué)習(xí)算法LLE、HLLE及LTSA等算法，提出了無自由參

6、數(shù)的自適應(yīng)流形學(xué)習(xí)算法3N-Isomap、3N-LLE及3N-LTSA等，同時(shí)解決了近十年來流形學(xué)習(xí)算法中關(guān)于如何選擇自由參數(shù)的問題。使任何人都可使用這批算法來觀察自己領(lǐng)域范圍內(nèi)的數(shù)據(jù)，而不受困擾。在三個(gè)實(shí)際問題中應(yīng)用了3N-Isomap算法，并提出了自動(dòng)多流形學(xué)習(xí)算法、大規(guī)模流形學(xué)習(xí)算法(由一個(gè)通用的簡(jiǎn)單隨機(jī)采樣算法實(shí)現(xiàn))及同質(zhì)數(shù)據(jù)復(fù)雜性分析方法。
　　 (3)將自適應(yīng)鄰域圖用于譜圖聚類算法，如MNcut算法，提出了一個(gè)改進(jìn)的