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

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

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

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

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

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

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

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

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

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

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