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

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

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

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

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

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

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