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

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

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

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

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

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

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

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