成對約束傳遞方法及其在約束聚類問題中的應(yīng)用研究.pdf

1、在機器學(xué)習(xí)、模式識別和數(shù)據(jù)挖掘等領(lǐng)域的研究中，聚類分析是一類極為重要的數(shù)據(jù)分析方法。聚類分析方法在圖像分析、生物信息學(xué)、web數(shù)據(jù)分析、社交網(wǎng)絡(luò)分析、天文學(xué)等諸多領(lǐng)域有著廣泛的應(yīng)用。利用聚類分析方法，人們對來自于這些領(lǐng)域的大規(guī)模應(yīng)用數(shù)據(jù)有了更深刻的理解，同時聚類分析的結(jié)果也是對大規(guī)模數(shù)據(jù)做進(jìn)一步處理的基礎(chǔ)。研究更為有效的數(shù)據(jù)聚類分析方法具有極為重要的現(xiàn)實意義。
　　但是，應(yīng)當(dāng)注意到傳統(tǒng)的數(shù)據(jù)聚類分析本身是一個病態(tài)的問題，這主要是因

2、為聚類分析是一類完全無監(jiān)督的學(xué)習(xí)方法。為了進(jìn)一步改進(jìn)聚類分析的性能，人們希望能夠在數(shù)據(jù)聚類分析中引入一些監(jiān)督信息來指導(dǎo)聚類過程。數(shù)據(jù)點之間存在的成對約束關(guān)系就是這樣的一類監(jiān)督信息，它包括了兩種成對約束關(guān)系，分別是必然連接（must-link）關(guān)系，用來表示數(shù)據(jù)集中的兩個數(shù)據(jù)點必然屬于同一類別，和必然不連接（cannot-link）關(guān)系，用來表示數(shù)據(jù)集中的兩個數(shù)據(jù)點必然屬于不同類別?？紤]了成對約束關(guān)系的聚類分析被稱為是基于成對約束的約束聚

3、類問題。
　　在基于成對約束的約束聚類問題中，通?？色@得的數(shù)據(jù)點之間的成對約束關(guān)系是非常有限的。成對約束關(guān)系傳遞問題是指對可獲得的初始有限的成對約束關(guān)系在數(shù)據(jù)集上進(jìn)行傳遞，通過成對約束傳遞可獲得大量可靠的數(shù)據(jù)點之間的成對約束信息，利用這樣大量的成對約束信息就可以顯著地提高約束聚類的性能。由于初始可獲得的成對約束關(guān)系非常有限，所以成對約束關(guān)系傳遞問題具有半監(jiān)督學(xué)習(xí)的結(jié)構(gòu)，可以利用大量的無監(jiān)督信息的數(shù)據(jù)幫助完成約束傳遞任務(wù)。人們已經(jīng)提

4、出了一些解決成對約束關(guān)系傳遞問題的算法，但是現(xiàn)有的算法具有一定的局限性。例如數(shù)據(jù)點之間存在的成對約束關(guān)系具有對稱的形式，但是目前的成對約束關(guān)系傳遞算法并沒有考慮到這種成對約束關(guān)系的對稱性；再者，成對約束關(guān)系傳遞過程需要首先計算數(shù)據(jù)點之間的一個相似圖，目前的相似圖構(gòu)造算法中并沒有考慮到將成對約束關(guān)系作為一種先驗信息引入到相似圖的構(gòu)造過程中；此外，已提出的成對約束關(guān)系傳遞算法主要集中在處理單模態(tài)數(shù)據(jù)上，但是在現(xiàn)實世界中存在著大量的多模態(tài)數(shù)據(jù)

5、，如何能夠充分利用多模態(tài)數(shù)據(jù)各個模態(tài)之間的關(guān)系來完成成對約束關(guān)系傳遞任務(wù)也是一個非常重要的研究問題。
　　針對現(xiàn)有約束傳遞算法存在的問題，本論文對成對約束關(guān)系傳遞算法及其在約束聚類中的應(yīng)用做了深入研究，主要工作和創(chuàng)新點包括以下幾個方面：
　?。?）首先從成對約束關(guān)系所具有的對稱性特征出發(fā)，研究具有對稱結(jié)構(gòu)的約束傳遞問題，提出了一個對稱圖正則的成對約束關(guān)系傳遞算法（symmetric graph regularized pai

6、rwise constraint propagation，SRCP）。在對稱圖正則框架下，指出了成對約束關(guān)系傳遞等價于求解一個李雅普諾夫矩陣方程。此外，還將成對約束關(guān)系傳遞過程建模為一個動態(tài)的對稱信息擴散過程，證明了這樣的一個對稱信息擴散過程具有時間不變的擴散結(jié)果，并且指出了時不變的擴散結(jié)果同樣等價于求解相同的李雅普諾夫矩陣方程。本論文的研究將對稱形式的成對約束傳遞同在控制論研究中被廣泛采用的李雅普諾夫矩陣方程聯(lián)系起來，具有重要的理論價

7、值。實驗結(jié)果表明對稱圖正則約束傳遞算法在約束聚類任務(wù)中可以獲得很好的聚類性能。
　?。?）建立在半監(jiān)督學(xué)習(xí)框架下的成對約束關(guān)系傳遞算法需要首先計算一個定義在數(shù)據(jù)集上的相似圖，用來反映數(shù)據(jù)點之間的相似程度。本論文提出一種相似度學(xué)習(xí)算法，提出的算法同時考慮了最小化局部重構(gòu)誤差和最小化局部約束誤差，提出的相似度學(xué)習(xí)問題可以被建模為一個二次優(yōu)化問題。進(jìn)一步將學(xué)習(xí)到的數(shù)據(jù)相似度用于成對約束關(guān)系傳遞任務(wù)，基本思想是使相似度高的兩個數(shù)據(jù)點彼此之

8、間應(yīng)該具有相同的關(guān)于其它數(shù)據(jù)點的成對約束關(guān)系配置。實驗結(jié)果表明將學(xué)習(xí)到的數(shù)據(jù)相似度應(yīng)用到成對約束關(guān)系傳遞問題可以有效地提高算法的性能。
　?。?）針對多模態(tài)數(shù)據(jù)集上的成對約束傳遞問題，本論文首先提出了一種基于多圖隨機行走的多模態(tài)成對約束關(guān)系傳遞算法。該算法首先在多模態(tài)數(shù)據(jù)集的每一個數(shù)據(jù)模態(tài)上建立了相似圖，然后在每一個模態(tài)相似圖上定義了隨機行走過程，并利用多個圖上的隨機行走過程將多個相似圖連接起來，形成多圖結(jié)構(gòu)，進(jìn)而在多圖上利用多圖

9、標(biāo)記傳遞技術(shù)解決了多模態(tài)數(shù)據(jù)集上的成對約束關(guān)系傳遞問題。進(jìn)一步提出了一種方法可以自動地學(xué)習(xí)多圖組合過程中各個數(shù)據(jù)模態(tài)的權(quán)重。多模態(tài)的成對約束關(guān)系傳遞問題可以通過求解一個無約束的二次規(guī)劃問題來計算，并且所提出的模型具有解析解的形式。實驗結(jié)果表明，提出的多模態(tài)成對約束關(guān)系傳遞算法可以有效地利用多個數(shù)據(jù)模態(tài)上的信息，獲得比單模態(tài)算法要好得多的性能。
　?。?）針對多模態(tài)數(shù)據(jù)約束傳遞問題，進(jìn)一步提出了一個模態(tài)一致性的框架，并將該框架用于解

10、決多模態(tài)成對約束關(guān)系傳遞問題。所提出的模態(tài)一致性框架利用了一個模態(tài)一致性的正則項將各個數(shù)據(jù)模態(tài)上約束傳遞結(jié)果統(tǒng)一起來，希望各個數(shù)據(jù)模態(tài)上的傳遞結(jié)果能夠彼此一致。為了有效地求解模態(tài)一致性框架，采用了一種可分離的模態(tài)一致性正則項，多模態(tài)成對約束傳遞問題可以通過一種簡單的交替優(yōu)化的方式求解。交替優(yōu)化過程包括了在每一個數(shù)據(jù)模態(tài)上的獨立成對約束傳遞過程和各個模態(tài)之間的一致傳遞過程。利用所提出的模態(tài)一致性框架，兩個單模態(tài)成對約束傳遞算法可以直接轉(zhuǎn)化