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

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

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

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

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

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

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

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

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

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

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