一種基于密度的聚類的算法

將物理或抽象對象的集合分成由類似的對象組成的多個類的過程被稱為聚類。由聚類所生成的簇是一組數(shù)據(jù)對象的集合，這些對象與同一個簇中的對象彼此相似，與其他簇中的對象相異目前，它已成為數(shù)據(jù)挖掘研究領域中一個非常活躍的研究方向。聚類分析技術在模式識別、數(shù)據(jù)分析、圖像處理和市場研究等許多領域得到了廣泛的應用。

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

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

　　1 DBSCAN算法

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

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

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

　　2 M-DBSCAN算法

　　2.1 在線聚類

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

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

　　將在線式聚類算法引入后，算法的描述如下：

　?。?）積累一小段時間內的數(shù)據(jù)，進行歸一化壓縮，進行相似度計算，得到相似度矩陣；

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

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

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

　　（5）直到?jīng)]有數(shù)據(jù)到來為止，輸出聚類結果。