圖上的隨機游走學習.pdf

1、傳統(tǒng)的處理機器學習和數(shù)據(jù)挖掘問題的方法都需要很強的前提假設或者大量的先驗知識，所以當現(xiàn)實問題與前提假設不一致時或者先驗知識不足夠時就會導致傳統(tǒng)方法性能的降低。近年來大量的令傳統(tǒng)方法無能為力的學習問題不斷涌現(xiàn)出來，而隨機過程中的隨機游走(Random Walk)就是處理這類棘手問題的一種有效方法。 隨機游走在計算機學科的信息檢索領域已經得到了成功的應用，現(xiàn)在正被越來越多地應用到機器學習和數(shù)據(jù)挖掘等領域。在此背景下，我們提出圖上的隨

2、機游走學習，創(chuàng)造性地將隨機游走作為一項基本技術，用于改善傳統(tǒng)的有監(jiān)督學習，半監(jiān)督學習和無監(jiān)督學習中的困難問題，本論文的具體貢獻如下。 (1)隨機游走分類器模型?；趫D上的隨機游走理論，我們提出了隨機游走基礎分類器模型、互補的隨機游走分類器模型、組合隨機游走分類器模型，詳細地分析了這些模型下的最優(yōu)分類器的設置和性能，給出了各種模型對應的有效分類器實現(xiàn)方法，從理論上證明了我們提出的組合方法可以大大提升基礎分類器的性能。 (2

3、)多層隨機游走框架。在簡單隨機游走理論的啟發(fā)下，我們提出一個統(tǒng)一的半監(jiān)督學習框架——多層隨機游走，通過構建各種組件級的隨機游走模型，可以產生一系列對應的多分類標簽傳播算法。多層隨機游走框架不僅囊括了目前為止的絕大多數(shù)標簽傳播算法，而且還能產生更多新的高效的組件傳播算法，這些結果被我們從正則化的角度得到進一步的證實。另外針對有標簽數(shù)據(jù)不平衡分布情況，我們提出了一種簡單的平衡策略，可用于改進任何標簽傳播算法的分類性能。實驗結果證明多層隨機游

4、走框架下的組件傳播算法和平衡策略都是非常有效的。 (3)隨機游走的細胞自動機聚類。借鑒隨機游走的思想，受螞蟻分巢居住行為的啟發(fā),使用細胞自動機的形式提出了螞蟻睡眠模型(ASM)。在此模型上設計一個螞蟻隨機游走聚類算法(RWAC)，該算法用人工螞蟻代表一個數(shù)據(jù)對象，讓整個螞蟻群體在隨機游走中動態(tài)地、自適應地、自組織地形成多個獨立的子群體，使不同類別的螞蟻之間相互分離，而同類的螞蟻之間高度緊密地排列，從而達到對數(shù)據(jù)聚類的目的。在螞蟻