面向大規(guī)模數(shù)據(jù)的聚類算法研究及應用.pdf

1、聚類分析是一種重要的無監(jiān)督學習方法，作為數(shù)據(jù)分析的工具，其重要性在模式識別、圖像處理等各個領(lǐng)域都得到了廣泛的認可。聚類分析的目的是尋找隱藏在數(shù)據(jù)中的結(jié)構(gòu)，并按照某種相似性度量，盡可能地使具有相同性質(zhì)的數(shù)據(jù)歸于同一類。近年來，各類數(shù)據(jù)及其信息量以指數(shù)形式增長，面對大規(guī)模數(shù)據(jù)，由于受到時間、內(nèi)存、CPU等資源的限制，傳統(tǒng)的聚類算法處理能力不再“高效”，而普遍存在著單位時間內(nèi)處理量小、面對大規(guī)模數(shù)據(jù)時處理時間較長、難以達到預期效果等缺陷。如何

2、對大規(guī)模數(shù)據(jù)進行有效聚類，得到了廣大學者的關(guān)注，也已成為國際數(shù)據(jù)挖掘領(lǐng)域的重點。
　　針對現(xiàn)有聚類算法不能有效處理大規(guī)模數(shù)據(jù)的問題，本文分成二大部分開展了研究：第一部分，面向大規(guī)模復雜數(shù)據(jù)，結(jié)合并行計算及云計算技術(shù)，針對劃分聚類算法和譜聚類算法，設計了兩種并行聚類算法，分別是基于MapReduce的抽樣劃分聚類算法和云環(huán)境下高效并行譜聚類算法；第二部分，面向復雜網(wǎng)絡、生物基因、圖像分割等特定領(lǐng)域中的大規(guī)模數(shù)據(jù)，分別設計了聚類集成發(fā)

3、現(xiàn)復雜社區(qū)算法F-DC、加權(quán)半監(jiān)督聚類圖像分割算法WSSC和基因差異共表達雙聚類算法DCECluster。本文的主要研究成果如下：
　　(1)提出了一個基于抽樣劃分聚類算法的通用框架，并為其設計了MapReduce實現(xiàn)。具體而言，我們先采用改進的抽樣技術(shù)去處理大規(guī)模數(shù)據(jù)集的表示；而后提出了一種抽樣劃分聚類算法的通用框架，并通過實現(xiàn)k-means和k-medoids算法來驗證框架的有效性；此外，在此基礎(chǔ)上，我們使用MapReduce

4、編程模型實現(xiàn)了提出的框架。實驗顯示，針對大規(guī)模數(shù)據(jù)集，本文提出的方法是有效的。
　　(2)提出了高效的并行譜聚類算法。并行化譜聚類算法的策略是：改進了距離矩陣和相似度矩陣，引入kd樹技術(shù)，用于對相似度矩陣進行稀疏化處理；在計算特征向量時，把拉普拉斯矩陣存儲于Hadoop文件系統(tǒng)上，通過分布式Lanczos運算獲得特征向量；最后使用高效的并行k-means聚類對特征向量的轉(zhuǎn)置矩陣進行處理獲得聚類結(jié)果。通過對算法的每一步采用不同的并行

5、策略，使得整個算法在速度上獲得線性增長。實驗表明，隨著處理數(shù)據(jù)規(guī)模的擴大，聚類速度達到差不多線性的增長，提出的并行譜聚類算法適合海量數(shù)據(jù)挖掘。
　　(3)提出了高效的社區(qū)發(fā)現(xiàn)聚類集成算法F-DC。算法的具體做法是：先提出了時間演變網(wǎng)絡模型，并對每個聚類進行了統(tǒng)一描述；針對真實網(wǎng)絡隨時間進化演變特征，提出了基于聚類分割的網(wǎng)絡快照產(chǎn)生聚類成員的方法；考慮到每個聚類成員的聚類中心分布和實際分布的差異，提出了基于最大似然法集成聚類結(jié)果的方

6、法。通過大量實驗的評估，驗證了面向時間演變網(wǎng)絡社區(qū)發(fā)現(xiàn)的聚類集成算法有效性。
　　(4)提出了一種面向彩色圖像分割的加權(quán)半監(jiān)督聚類算法WSSC。算法首先提出了在傳統(tǒng)半監(jiān)督聚類算法中權(quán)重的概念并給出了計算公式。在此基礎(chǔ)上，通過優(yōu)化可能性矩陣獲得了類標簽。對于每一副圖像，都可以表示成一個d維隨機向量，每個像素點可由混合密度獨立獲取。利用WSSC算法，圖像分割結(jié)果可以通過混合組件類標簽獲得。通過在二組圖像數(shù)據(jù)上的一系列實驗結(jié)果證明，提出

7、的算法WSSC效率較高，特別是針對大規(guī)模彩色圖像優(yōu)勢明顯。
　　(5)提出了一種新的基于粗糙集的多值樣本屬性離散化方法，進而提出了一種基于基因差異共表達樣本權(quán)值圖和搜索剪枝策略的最大雙聚類挖掘算法DCECluster。算法首先把離散化的數(shù)據(jù)集構(gòu)建成基因差異樣本關(guān)系權(quán)值圖，有效去除了無關(guān)的基因，通過基因差異共表達關(guān)系，定義了新的差異支持度概念，最后使用有效的搜索策略和剪枝策略對產(chǎn)生的候選雙聚類進行剪枝。通過對4種不同差異共表達雙聚類