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

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

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

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

　　1 DBSCAN算法

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

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

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

　　2 M-DBSCAN算法

　　2.1 在線聚類

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

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

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

　　（1）積累一小段時間內的數據，進行歸一化壓縮，進行相似度計算，得到相似度矩陣；

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

　　（3）對尚未加入此類的數據點xi，比較與類中心的距離是否大于給定閾值dthr，若是，則加入此類，否則創建一個新類cj；

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

　　（5）直到沒有數據到來為止，輸出聚類結果。