聚類分析是數(shù)據(jù)挖掘中的一項(xiàng)重要技術(shù),已被用來探索實(shí)際應(yīng)用中各種數(shù)據(jù)的潛在類結(jié)構(gòu)。由于數(shù)據(jù)的復(fù)雜性,聚類結(jié)果并不一定能滿足用戶期望。半監(jiān)督聚類利用少量的先驗(yàn)信息指導(dǎo)聚類過程,使得聚類結(jié)果盡可能的滿足用戶期望。本文以如何利用和傳播先驗(yàn)信息為主題,針對標(biāo)簽傳播算法和成對約束的擴(kuò)充算法進(jìn)行了系統(tǒng)的研究,主要研究內(nèi)容如下:（1）本文對標(biāo)簽傳播算法進(jìn)行了擴(kuò)展,提出了基于成對約束的標(biāo)簽傳播算法。在該算法中,我們將先驗(yàn)信息保存到成對關(guān)系矩陣中,并且通過計(jì)算成對關(guān)系與聚類結(jié)果之間的差異來代替劃分矩陣之間的差異。同時(shí),我們通過構(gòu)建一種新的最優(yōu)化模型,將標(biāo)簽傳播算法的最優(yōu)化問題轉(zhuǎn)化為譜聚類問題,并通過特征值分解方法得到最優(yōu)解。該算法不僅可以解決標(biāo)簽傳播過程中存在的非對齊問題,同時(shí)還可以處理成對約束先驗(yàn)信息。最后,將該算法與8種半監(jiān)督聚類算法在11個(gè)基準(zhǔn)數(shù)據(jù)集上進(jìn)行了比較。實(shí)驗(yàn)結(jié)果表明,所提出的算法相比其他算法更有效。（2）成對約束的數(shù)量是影響半監(jiān)督聚類結(jié)果有效性的重要因素。然而,在現(xiàn)實(shí)應(yīng)用中,成對約束的獲取需要耗費(fèi)大量的成本。因此,本文提出了一種基于安全性的成對約束擴(kuò)充方法。該算法通過統(tǒng)計(jì)傳遞閉包中最大局部... 

【文章來源】：山西大學(xué)山西省

【文章頁數(shù)】：65 頁

【學(xué)位級別】：碩士

【部分圖文】：

類標(biāo)簽和簇標(biāo)簽之間存在的非對齊現(xiàn)象

基于標(biāo)簽傳播的半監(jiān)督聚類算法研究8根據(jù)以上，和的定義，我們可以按照先驗(yàn)信息類型的不同來定義成對關(guān)系矩陣，如下所示：={,先驗(yàn)信息為正標(biāo)簽,11(),先驗(yàn)信息為負(fù)標(biāo)簽,,先驗(yàn)信息為成對約束,(2-9)其中和11()分別是和的成對關(guān)系表示，表示數(shù)據(jù)集的聚類數(shù)量。由于僅根據(jù)兩個(gè)數(shù)據(jù)對象的負(fù)標(biāo)簽無法判斷兩個(gè)數(shù)據(jù)對象是否屬于同一類。因此，我們使用11來反映兩個(gè)數(shù)據(jù)對象屬于同一類的概率。根據(jù)成對關(guān)系矩陣的定義，我們重新定義了標(biāo)簽傳播算法的代價(jià)函數(shù)′()如下所示：′()=‖‖2,(2-10)其中是的成對關(guān)系表示，′()表示預(yù)先給定的成對關(guān)系和聚類得到的成對關(guān)系之間存在的差異。新的代價(jià)函數(shù)可以解決預(yù)先給定的類標(biāo)簽和聚類得到的簇標(biāo)簽之間存在的非對齊問題。延續(xù)圖2.1中的示例，在圖2.2中我們展示了新代價(jià)函數(shù)′()的優(yōu)勢。由圖2.2可知，完全等價(jià)于。因此使用成對關(guān)系矩陣可以克服非對齊問題。圖2.2將劃分矩陣轉(zhuǎn)化為成對關(guān)系矩陣的過程此外，我們修改了標(biāo)簽傳播算法的最優(yōu)化問題，如下所示：

第二章基于成對約束的標(biāo)簽傳播算法13聚類性能的影響。在分析中，我們考慮了三種情況，即正標(biāo)簽，成對約束，正負(fù)標(biāo)簽分別作為先驗(yàn)信息時(shí)算法的聚類性能。我們將約束的數(shù)量固定為25%，其中對應(yīng)數(shù)據(jù)集中數(shù)據(jù)對象的數(shù)量。我們以0.1為步長在[0,1]區(qū)間內(nèi)測試了不同值所對應(yīng)提出算法的聚類結(jié)果。根據(jù)這些圖可以發(fā)現(xiàn)，參數(shù)對不同數(shù)據(jù)集的影響是不同的。這表明很難為每個(gè)數(shù)據(jù)集選擇合適的來執(zhí)行所提出的算法。為了進(jìn)一步分析參數(shù)的影響，我們在圖2.4和圖2.6中展示了每個(gè)值對算法在所有測試的數(shù)據(jù)集上得到的平均評價(jià)指標(biāo)。根據(jù)平均線我們可以發(fā)現(xiàn)當(dāng)在某種程度上增加時(shí)，所提出算法的平均聚類性能相對穩(wěn)定。(a)正標(biāo)簽為先驗(yàn)信息(b)成對約束為先驗(yàn)信息(c)正負(fù)標(biāo)簽為先驗(yàn)信息圖2.3參數(shù)對NLPPC算法NMI值的影響(a)正標(biāo)簽為先驗(yàn)信息(b)成對約束為先驗(yàn)信息(c)正負(fù)標(biāo)簽為先驗(yàn)信息圖2.4參數(shù)在所有數(shù)據(jù)集上對NLPPC算法NMI平均值的影響(a)正標(biāo)簽為先驗(yàn)信息(b)成對約束為先驗(yàn)信息(c)正負(fù)標(biāo)簽為先驗(yàn)信息圖2.5參數(shù)對NLPPC算法ARI值的影響

【參考文獻(xiàn)】：
期刊論文
[1]密度敏感的半監(jiān)督譜聚類[J]. 王玲,薄列峰,焦李成.  軟件學(xué)報(bào). 2007(10)



本文編號：3512067