對關聯(lián)聚類的擴展及其應用的研究.pdf

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

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

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