一種基于密度的聚類(lèi)的算法

將物理或抽象對(duì)象的集合分成由類(lèi)似的對(duì)象組成的多個(gè)類(lèi)的過(guò)程被稱(chēng)為聚類(lèi)。由聚類(lèi)所生成的簇是一組數(shù)據(jù)對(duì)象的集合，這些對(duì)象與同一個(gè)簇中的對(duì)象彼此相似，與其他簇中的對(duì)象相異目前，它已成為數(shù)據(jù)挖掘研究領(lǐng)域中一個(gè)非?；钴S的研究方向。聚類(lèi)分析技術(shù)在模式識(shí)別、數(shù)據(jù)分析、圖像處理和市場(chǎng)研究等許多領(lǐng)域得到了廣泛的應(yīng)用。

　　許多算法被設(shè)計(jì)用來(lái)聚類(lèi)數(shù)值類(lèi)型的數(shù)據(jù)。但是，應(yīng)用可能要求聚類(lèi)其他類(lèi)型的數(shù)據(jù)，如二元類(lèi)型（binary），分類(lèi)/標(biāo)稱(chēng)類(lèi)型（categorical/nominal），序數(shù)型（ordinal）數(shù)據(jù)，或者這些數(shù)據(jù)類(lèi)型的混合。 其主要思想是：只要臨近區(qū)域的密度（對(duì)象或數(shù)據(jù)點(diǎn)的數(shù)目）超過(guò)某個(gè)閾值就繼續(xù)聚類(lèi)。樣的方法可以用來(lái)過(guò)濾噪聲和孤立點(diǎn)數(shù)據(jù)，發(fā)現(xiàn)任意形狀的類(lèi)。

　　DBSCAN算法利用類(lèi)的高密度連通性可以快速發(fā)現(xiàn)任意形狀的類(lèi)，但是當(dāng)處理的數(shù)據(jù)量較大時(shí)，一般的聚類(lèi)算法不能滿(mǎn)足在線(xiàn)聚類(lèi)這一特點(diǎn)，計(jì)算復(fù)雜度高，速度慢。

　　1 DBSCAN算法

　　DBSCAN（Density-Based Spatial Clustering of Applacations with Noise）是一個(gè)比較有代表性的基于密度的聚類(lèi)算法。與劃分和層次聚類(lèi)方法不同，它將簇定義為密度相連的點(diǎn)的最大集合，能夠把具有足夠高密度的區(qū)域劃分為簇，并可在噪聲的空間數(shù)據(jù)庫(kù)中發(fā)現(xiàn)任意形狀的聚類(lèi)。DBSCAN算法具有足夠高密度的區(qū)域劃分為一類(lèi)，并可以在帶有噪聲的空間數(shù)據(jù)庫(kù)中發(fā)現(xiàn)任意形狀的聚類(lèi)

　　DBSCAN算法提出了一些新的定義：

　　DBSCAN算法是基于密度的聚類(lèi)算法，它將類(lèi)看作是數(shù)據(jù)空間中被低密度區(qū)域分割開(kāi)的高密度對(duì)象區(qū)域。在該算法中，發(fā)現(xiàn)一個(gè)聚類(lèi)的過(guò)程是基于這樣的事實(shí)：一個(gè)聚類(lèi)能夠被其中的任意一個(gè)核心對(duì)象所確定。其基本思想是：考察數(shù)據(jù)庫(kù)D中的某一個(gè)點(diǎn)P，若P是核心點(diǎn)，則通過(guò)區(qū)域查詢(xún)得到該點(diǎn)的鄰域，鄰域中的點(diǎn)和P同屬于一個(gè)類(lèi)，這些點(diǎn)將作為下一輪的考察對(duì)象，并通過(guò)不斷地對(duì)種子點(diǎn)進(jìn)行區(qū)域查詢(xún)來(lái)擴(kuò)展它們所在的類(lèi)，直至找到一個(gè)完整的類(lèi)。

　　2 M-DBSCAN算法

　　2.1 在線(xiàn)聚類(lèi)

　　由于處理數(shù)據(jù)量較大，一次性處理完畢不但運(yùn)算量大，復(fù)雜度高，而且對(duì)存儲(chǔ)空間的需求量大，因此本文提出一種在線(xiàn)式聚類(lèi)算法，可以動(dòng)態(tài)增加聚類(lèi)數(shù)目。

　　算法的原理是：隨著輸入樣本數(shù)據(jù)的不斷增加，實(shí)時(shí)動(dòng)態(tài)地增加聚類(lèi)個(gè)數(shù)或調(diào)整聚類(lèi)中心及聚類(lèi)半徑，在形成的任意一個(gè)聚類(lèi)中，聚類(lèi)中心與屬于此聚類(lèi)的樣本點(diǎn)的相似度都不小于一個(gè)閾值dthr，dthr的選取將直接影響到聚類(lèi)數(shù)目。

　　將在線(xiàn)式聚類(lèi)算法引入后，算法的描述如下：

　　（1）積累一小段時(shí)間內(nèi)的數(shù)據(jù)，進(jìn)行歸一化壓縮，進(jìn)行相似度計(jì)算，得到相似度矩陣；

　?。?）通過(guò)對(duì)相似度矩陣進(jìn)行比較分析，找出鄰域密度最大的數(shù)據(jù)點(diǎn)作為第一個(gè)初始類(lèi)的中心c1；

　?。?）對(duì)尚未加入此類(lèi)的數(shù)據(jù)點(diǎn)xi，比較與類(lèi)中心的距離是否大于給定閾值dthr，若是，則加入此類(lèi)，否則創(chuàng)建一個(gè)新類(lèi)cj；

　　（4）處理完這一小段數(shù)據(jù)后，對(duì)新到來(lái)的一個(gè)數(shù)據(jù)點(diǎn)進(jìn)行與（3）相同的做法，確定其類(lèi)別；

　?。?）直到?jīng)]有數(shù)據(jù)到來(lái)為止，輸出聚類(lèi)結(jié)果。