面向復(fù)雜數(shù)據(jù)的聚類算法研究.pdf

1、近年來(lái)，數(shù)據(jù)量急劇增長(zhǎng)，數(shù)據(jù)源的種類日益增多，導(dǎo)致從復(fù)雜的數(shù)據(jù)中獲取有用的信息變得越來(lái)越困難。要想很好地利用這些數(shù)據(jù)，就必須理解這些復(fù)雜的數(shù)據(jù)，從中挖掘出其內(nèi)在的模式。聚類分析能根據(jù)數(shù)據(jù)間的相似性識(shí)別出數(shù)據(jù)集中的內(nèi)在模式。但很多聚類算法在劃分不同類型的數(shù)據(jù)集時(shí)，都會(huì)遇到精確性不高或者執(zhí)行效率較低等問(wèn)題，這就需要投入更多的精力去提高聚類算法的性能。本論文以更高效、更精確地對(duì)復(fù)雜數(shù)據(jù)進(jìn)行聚類為目的，針對(duì)三種不同類型的數(shù)據(jù)，集中在聚類研究的三

2、個(gè)方面，提出了四個(gè)聚類算法：EPC、MulSim、CLUB和SUM。EPC是一個(gè)根據(jù)污染特征將大氣污染抽樣數(shù)據(jù)進(jìn)行聚類的算法，它能提高CMB、PMF、UNMIX和PCA等源解析模型的精確性，并且和傳統(tǒng)算法算法相比更易于使用、更適合于聚類高維數(shù)據(jù)；MulSim和CLUB是挖掘數(shù)據(jù)集中包含的任意形狀、任意密度以及任意規(guī)模的簇的兩個(gè)聚類算法，其中，MulSim基于單點(diǎn)與多點(diǎn)相似的策略進(jìn)行聚類，CLUB通過(guò)識(shí)別簇的密度主干進(jìn)行聚類；SUM是對(duì)圖

3、數(shù)據(jù)中的頂點(diǎn)進(jìn)行聚類的算法，其基本原理是質(zhì)疑簇中的最大度頂點(diǎn)在聚類時(shí)對(duì)其他頂點(diǎn)的連接作用。
　?。?）EPC EPC在第一步對(duì)數(shù)據(jù)進(jìn)行預(yù)處理后，迭代進(jìn)行第二步，每次迭代選擇第一個(gè)未標(biāo)記的數(shù)據(jù)點(diǎn)作為一個(gè)簇中心點(diǎn)，然后根據(jù)本文提出的相似性函數(shù)和用戶給定的相似性閾值，把每個(gè)數(shù)據(jù)點(diǎn)分配到與它最相似的中心點(diǎn)所屬的簇，最后利用與k-Means相似的方法對(duì)簇進(jìn)行更新，形成最終的簇結(jié)構(gòu)。本文在實(shí)驗(yàn)部分通過(guò)人工數(shù)據(jù)集和真實(shí)數(shù)據(jù)集分別驗(yàn)證了EPC算法

4、的有效性。結(jié)果表明，EPC算法不但能根據(jù)污染特征的相似性對(duì)環(huán)境污染抽樣數(shù)據(jù)進(jìn)行聚類，而且還能同時(shí)檢測(cè)出其中的異常點(diǎn)。
　　（2）MulSim MulSim定義了一個(gè)能自動(dòng)適應(yīng)數(shù)據(jù)點(diǎn)密度變化的相似性函數(shù)，若一個(gè)數(shù)據(jù)點(diǎn)同時(shí)與另一個(gè)數(shù)據(jù)點(diǎn)以及該點(diǎn)的鄰居相似，就認(rèn)為這兩個(gè)數(shù)據(jù)點(diǎn)屬于同一個(gè)簇。實(shí)驗(yàn)結(jié)果顯示，在測(cè)試的任意密度數(shù)據(jù)集、統(tǒng)一密度數(shù)據(jù)集、簇內(nèi)包含多個(gè)中心點(diǎn)的數(shù)據(jù)集、包含螺旋形簇的數(shù)據(jù)集、包含球狀簇的數(shù)據(jù)集、包含任意形狀簇的數(shù)據(jù)集以及

5、多維數(shù)據(jù)集等各種類型的數(shù)據(jù)集上，MulSim的聚類質(zhì)量在多數(shù)情況下優(yōu)于六個(gè)對(duì)比算法。
　?。?）CLUB CLUB首先基于互k最近鄰方法發(fā)現(xiàn)初始簇，接著將初始簇作為算法第二步的輸入，基于k最近鄰方法識(shí)別出簇的密度主干。然后，通過(guò)把無(wú)標(biāo)簽的數(shù)據(jù)點(diǎn)分配給密度比它大的最近鄰所在的簇以形成最終簇結(jié)構(gòu)。最后，從簇的內(nèi)部檢測(cè)出異常點(diǎn)。實(shí)驗(yàn)部分在九個(gè)包含任意形狀、任意密度、任意規(guī)模簇的二維數(shù)據(jù)集以及七個(gè)廣泛使用的多維數(shù)據(jù)集上，通過(guò)與三個(gè)經(jīng)典算法

6、、三個(gè)新算法進(jìn)行比較，對(duì)CLUB的性能進(jìn)行了評(píng)價(jià)。而且，還將CLUB應(yīng)用于Olivetti Face數(shù)據(jù)集上，展示了其在人臉識(shí)別中的有效性。實(shí)驗(yàn)結(jié)果顯示，CLUB在大多數(shù)情況下優(yōu)于對(duì)比算法。
　?。?）SUM SUM利用相鄰頂點(diǎn)間的公共鄰居個(gè)數(shù)和較小度頂點(diǎn)的度定義了一個(gè)相似度函數(shù)。在將相似的頂點(diǎn)放置到同一個(gè)簇中之后，SUM質(zhì)疑簇中的最大度頂點(diǎn)對(duì)其他頂點(diǎn)的連接作用，斷開(kāi)簇中最大度頂點(diǎn)與其鄰居頂點(diǎn)的連線，將最大度頂點(diǎn)重新分配來(lái)獲得初始