對關(guān)聯(lián)聚類的擴(kuò)展及其應(yīng)用的研究.pdf

1、數(shù)據(jù)時(shí)代下智能化是各種設(shè)備和應(yīng)用發(fā)展的一大趨勢，各種數(shù)據(jù)挖掘技術(shù)正被用于實(shí)現(xiàn)這一目標(biāo)。雖然數(shù)據(jù)時(shí)代的前景十分美好，但是也充滿著各種挑戰(zhàn)。首先，數(shù)據(jù)搜集和存儲的代價(jià)越來越小，而人們處理數(shù)據(jù)的速度卻遠(yuǎn)不及數(shù)據(jù)增長的速度。其次，獲取的數(shù)據(jù)存在包括噪聲、無結(jié)構(gòu)性、信息缺省等多方面的質(zhì)量問題，這為數(shù)據(jù)分析帶來了不少困難?，F(xiàn)實(shí)中獲取的數(shù)據(jù)大部分為無監(jiān)督類型的，快速高效的無監(jiān)督學(xué)習(xí)方法不僅能夠適當(dāng)緩解數(shù)據(jù)處理壓力，而且能夠根據(jù)其所發(fā)現(xiàn)的價(jià)值幫助后續(xù)的

2、數(shù)據(jù)收集工作。
　　聚類分析是無監(jiān)督學(xué)習(xí)的重要內(nèi)容，有著久遠(yuǎn)的發(fā)展歷史。相比起其他聚類方法，關(guān)聯(lián)聚類能夠不需預(yù)定義而自動(dòng)選擇合適的簇類數(shù)目進(jìn)行聚類，這種特性使其更加適用于真實(shí)數(shù)據(jù)場景。然而關(guān)聯(lián)聚類因其求解十分困難，多年來一直未能得到廣泛應(yīng)用。鑒于此，本文針對關(guān)聯(lián)聚類問題進(jìn)行了如下研究:
　　(1)分別對關(guān)聯(lián)聚類、最小k-割問題和二次半分配問題的數(shù)學(xué)優(yōu)化形式進(jìn)行了重構(gòu)，一方面闡述了三者之間的相互關(guān)系和求解難度，另一方面以此說明

3、利用現(xiàn)有的解決類似問題的松弛技術(shù)很難有所突破，應(yīng)尋求其他方法。
　　(2)通過對關(guān)聯(lián)聚類求解難點(diǎn)的分析，引入聚類指示矩陣和聚類分配這兩個(gè)新的變量，對原問題進(jìn)行重新形式化，松弛掉問題的非關(guān)鍵約束，提出了一種單次迭代時(shí)間復(fù)雜度為O(|V|+|E|)的基于偽期望最大的迭代算法——Pseudo-EM。此外，本文討論了一種啟發(fā)式的聚類指示矩陣的初始化方法和數(shù)據(jù)的稀疏性問題，并利用實(shí)驗(yàn)驗(yàn)證了算法的有效性。
　　(3)本文最后探索了關(guān)聯(lián)聚