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

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

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

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