針對非均勻數據集自適應聚類算法的研究論文

　　摘 要：傳統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

【針對非均勻數據集自適應聚類算法的研究論文】相關文章：

關于描述CRP模型中的聚類算法的論文06-16

計數查找算法研究精選論文04-05

淺析禮服的自適應定制研究論文05-27

近場聲源定位算法研究論文06-18

基于屬性重要度約簡算法在數據挖掘中的應用研究論文10-30

大數據環境下的數據安全研究論文10-30

關于淺析非均勻分布冗余DRAM 的修復方法的論文05-28

CCD測量系統中基于自適應相關算法的動態目標跟蹤的論文06-16

大數據營銷創新研究論文11-06