次模函數(shù)展開定義的度量距離學(xué)習(xí)算法.pdf

1、度量距離學(xué)習(xí)是機器學(xué)習(xí)的一個重要的分支。不同于其他對數(shù)據(jù)直接進(jìn)行分類或聚類處理的機器學(xué)習(xí)算法，度量距離學(xué)習(xí)是對度量的優(yōu)化和選擇。而在機器學(xué)習(xí)領(lǐng)域及大部分相關(guān)的算法中，對現(xiàn)實對象的相似度或距離的準(zhǔn)確定義決定著算法的最終效果。K-中值聚類、K-最鄰近算法分類和支持向量機等核函數(shù)算法，它們都強烈地需求一個對距離或度量的準(zhǔn)確描述。
　　本文研究內(nèi)容如下：
　　(1)度量距離學(xué)習(xí)算法的通用模型。本文研究了現(xiàn)今國內(nèi)外常見的距離度量算法，

2、比如大余量最近鄰居算法，信息論距離度量學(xué)習(xí)算法和最小方差學(xué)習(xí)算法等，可以發(fā)現(xiàn)其中大部分算法基于類似馬氏距離的模型。它們大多是學(xué)習(xí)優(yōu)化對歐式距離的映射矩陣G；
　　(2)描述任意數(shù)量維度交集數(shù)據(jù)特征的方法。因為現(xiàn)行的經(jīng)典度量距離學(xué)習(xí)算法大多是學(xué)習(xí)優(yōu)化對歐式距離的映射矩陣G，矩陣的結(jié)構(gòu)導(dǎo)致無法對三維及三維維度的交集上數(shù)據(jù)的特征進(jìn)行描述。為了解決這一缺陷，本文引入了集函數(shù)這一概念來描述任意維度的交集。集函數(shù)即為輸入為集合，輸出一般為數(shù)值

3、的函數(shù)，通常用來衡量輸入集合的質(zhì)量、或價值、或消耗等。本文將對象的任意維度的交集作為集函數(shù)的輸入，將對象的相似相關(guān)權(quán)值作為輸出，并嘗試將這一集函數(shù)定義為度量進(jìn)行學(xué)習(xí)。為了便于對集函數(shù)的學(xué)習(xí)和優(yōu)化，本文著重于一類特殊的集函數(shù)——次模函數(shù)。
　　(3)次模函數(shù)及其展開分析。次模性是一個有著大量理論成果和實踐意義的集函數(shù)特性。因為次模函數(shù)這一集函數(shù)體現(xiàn)出的邊際遞減效應(yīng)表現(xiàn)類似與凹函數(shù)，又與凸函數(shù)性質(zhì)有所關(guān)聯(lián)，所以我們嘗試對次模函數(shù)進(jìn)行學(xué)

4、習(xí)，并根據(jù)集函數(shù)的兩種常見的展開——洛瓦斯展開和多線性展開進(jìn)行了分析。利用集函數(shù)的洛瓦斯展開即為集函數(shù)的下確界這一性質(zhì)，可以通過最小化洛瓦斯展開來最小化集函數(shù)，并根據(jù)其特性定義了基于洛瓦斯展開的洛瓦斯展開范數(shù)。范數(shù)任意冪次的差均為度量，因此便可以定義洛瓦斯度量。而多重線性展開雖然本文并未成功利用其特性定義多重線性展開范數(shù)，但是在受限條件下，可以利用多重線性展開的交叉凸性質(zhì)令其符合度量的定義條件，我們將其定義為多重線性展開差異度函數(shù)。

5、r>　　(4)基于次模函數(shù)定義的度量。提出并證明了一種基于次模函數(shù)的洛瓦斯展開定義的范數(shù)，以及根據(jù)這一范數(shù)獲得的基于次模函數(shù)的洛瓦斯展開度量。闡述了范數(shù)的三個條件并依次證明了在基于次模函數(shù)的條件下，次模函數(shù)的下確界洛瓦斯展開可以定義為一個范數(shù)。本文選擇使用相對距離限定和ridge正則化因子構(gòu)建了針對提出度量的損失函數(shù)，并將這一損失函數(shù)轉(zhuǎn)化為線性規(guī)劃問題和二次規(guī)劃的問題。
　　(5)次模展開度量學(xué)習(xí)算法實現(xiàn)與實驗。運用Python工

6、具包進(jìn)行了學(xué)習(xí)和優(yōu)化，在多種不同的實例數(shù)據(jù)集上，測試應(yīng)用了該度量的K-最鄰近算法的交叉檢驗分?jǐn)?shù)作為測量其表現(xiàn)的標(biāo)準(zhǔn)。并與常見的距離——歐式距離和曼哈頓距離及常見的度量學(xué)習(xí)算法——信息論距離度量學(xué)習(xí)算法和最小方差學(xué)習(xí)算法進(jìn)行了比較。
　　實驗結(jié)果展示了基于洛瓦斯展開范數(shù)和多線性差異函數(shù)的距離度量學(xué)習(xí)算法的表現(xiàn)，本文分析闡述了所提出的距離度量學(xué)習(xí)算法能夠更為有效地挖掘數(shù)據(jù)多個維度特征間關(guān)系和聯(lián)合表達(dá)的信息的優(yōu)點，和計算復(fù)雜度過大、依賴