針對非均勻資料集自適應聚類演算法的研究論文

　　摘要：傳統DBSCAN演算法需要輸入兩個特定的引數（minPts和Eps），這對於沒有經驗的使用者是很困難的。同時，如果在多密度的資料集中使用全域性的Eps引數，也會對聚類結果的質量造成大的影響。所以，針對以上兩個問題，結合密度層次分層和聚類效果指數CEI的思想提出一種改進的DBSCAN演算法。實驗結果表明，改進的DBSCAN演算法要優於傳統的DBSCAN演算法。

　　關鍵詞：DBSCAN；多密度；自適應；密度層次劃分

　　資料探勘是關於資料分析的技術，它能夠從大量的資料中提取隱藏和有意義的關係和模式。聚類分析作為一種重要的資料分析方法，主要用於將資料集中的`物件分成多個類或者簇，使得同一個類和簇中的物件之間有較高的相似度，而不同物件之間的差別很大。DBSCAN作為經典的基於密度的聚類演算法，它能夠在包含有噪聲和邊界點的資料集中發現任意形狀的簇。但是DBSCAN演算法需要輸入兩個特定的引數（minPts和Eps），並且其無法處理多密度的資料集。針對這兩個問題，筆者提出一種基於DBSCAN—DLP演算法的針對非均勻資料集的自適應聚類演算法SADBSCSAN—DLP（A Self—Adaptive Density—Based Spatial Clustering of Application with Noise based on Density Levels Partitioning）。實驗結果表明，該演算法在對引數敏感性和在多密度環境下聚類的準確性兩方面要優於傳統的DBSCAN演算法。

　　1 傳統DBSCAN演算法

　　DBSCAN演算法作為一種經典的基於中心的密度聚類演算法，DBSCAN演算法的定義如下：

　　定義1：（Eps—鄰域）給定某個物件q，q的鄰域定義為以p為核心，以Eps為半徑的d維超球體的區域，公式表示為：其中，d為空間R的維度。dist（q，p）表示物件q和p之間的直線距離。

　　定義2：（核心點、邊界點，噪音點）對於資料物件q，且，如果以q為中心，以為半徑，若內的點數超過給定MinPts，則稱q為核心點，若q不是核心點，但在某個核心點的鄰域內，則稱為邊界點，其餘為噪聲點和離群點。

　　定義3：（直接密度可達），如果q屬於r的Eps—鄰域，且r是核心物件，則稱q從r直接密度可達。

　　定義4：（密度可達）密度存在物件鏈，，若所有的物件從物件關於Eps和MinPts直接密度可達，則稱q從p關於Eps和MinPts密度可達。

　　定義5：（密度連線）給定物件r，若p和q都是從r出發，關於Eps和MinPts密度可達的，則稱p和q是關於Eps和MinPts密度連線的。

　　定義6：（聚類）物件集D的非空集合C是一個關於MinPts和Eps的聚類，當且僅當滿足下麵條件：最大性：：若，且q是從p關於Eps和MinPts密度可達的，那麼；連通性：：p與q是關於Eps和MinPts密度連線的。

　　2 SADBSCAN—DLP演算法

　　SADBSCSAN—DLP演算法的思想：為了能直觀的描述改進演算法，我們構造了帶有三個不同密度層次的樣本資料集，如圖2（a）。並計算出其對應的KNN矩陣，對KNN矩陣中的某一列進行曲線擬合得到distk圖，如圖2（b），再計算每一列的密度變化率DenVar，然後可以得到每一列的密度變化率的一個序列DenVarList，然後再以DenVarList序列的下標作為橫座標，對應的DenVar值作為縱座標，繪出DenVar圖，如圖2（c）。根據DenVarList序列的統計特性，β的定義如下：改進演算法的具體步驟如下：根據閾值β定義計算出KNN矩陣中每一列的β；透過β和KNN中每一列的DenVarList序列對每一列進行密度層次分層；根據分層結果計算出KNN中能使CEI到達最大值所對應的第k列，將k作為minPts；根據分層結果，計算出每一層的Epsi，Epsi的計算方法如下：在不同的DLSi上進行聚類，最後合併聚類結果。

　　 3 實驗結果

　　為了分析和觀察實驗結果，我們使用了來自UCI的兩組不同的資料集。實驗在Matlab V7。1軟體下實現進行。使用Rand—Index來比較三種聚類演算法的效果。表1 結果比較資料集演算法引數 Rand—Index Iris （Cluster = 3， Attribute = 4） DBSCAN （minPts = 4， Eps = 0.3194） 69.1% DBSCAN—DLP （k = 4， ω=0.5） 84.1% SADBSCAN—DLP （ω= 0.5） 88.03% Wine （Cluster = 2， Attribute = 13） DBSCAN （minPts = 4， Eps = 0.3194） 73.1% DBSCAN—DLP （k = 4，ω= 1） 72.3% SADBSCAN—DLP （ω= 0.5） 72.1% 表1給出了三個演算法的實驗對比結果。可以看出，在資料集Iris中使用所改進的演算法的準確度要高於其它兩個演算法

　　4 結語

　　本文針對DBSCAN演算法和DBSCAN—DLP演算法的不足提出了改進。實驗結果表明改進的演算法SADBSCAN—DLP演算法有效減少了傳統DBSCAN聚類演算法對引數的敏感度，對聚類效果有很大的提升。

　　參考文獻 [1]Xutao Li， Yunming Ye， Mar