針對非均勻數(shù)據(jù)集自適應聚類算法的研究論文
摘 要：傳統(tǒng)DBSCAN算法需要輸入兩個特定的參數(shù)（minPts和Eps），這對于沒有經驗的使用者是很困難的。同時，如果在多密度的數(shù)據(jù)集中使用全局的Eps參數(shù)，也會對聚類結果的質量造成大的影響。所以，針對以上兩個問題，結合密度層次分層和聚類效果指數(shù)CEI的思想提出一種改進的DBSCAN算法。實驗結果表明，改進的DBSCAN算法要優(yōu)于傳統(tǒng)的DBSCAN算法。
關鍵詞：DBSCAN；多密度；自適應；密度層次劃分
數(shù)據(jù)挖掘是關于數(shù)據(jù)分析的技術，它能夠從大量的數(shù)據(jù)中提取隱藏和有意義的關系和模式。聚類分析作為一種重要的數(shù)據(jù)分析方法，主要用于將數(shù)據(jù)集中的`對象分成多個類或者簇，使得同一個類和簇中的對象之間有較高的相似度，而不同對象之間的差別很大。DBSCAN作為經典的基于密度的聚類算法，它能夠在包含有噪聲和邊界點的數(shù)據(jù)集中發(fā)現(xiàn)任意形狀的簇。但是DBSCAN算法需要輸入兩個特定的參數(shù)（minPts和Eps），并且其無法處理多密度的數(shù)據(jù)集。針對這兩個問題，筆者提出一種基于DBSCAN—DLP算法的針對非均勻數(shù)據(jù)集的自適應聚類算法SADBSCSAN—DLP（A Self—Adaptive Density—Based Spatial Clustering of Application with Noise based on Density Levels Partitioning）。實驗結果表明，該算法在對參數(shù)敏感性和在多密度環(huán)境下聚類的準確性兩方面要優(yōu)于傳統(tǒng)的DBSCAN算法。
1 傳統(tǒng)DBSCAN算法
DBSCAN算法作為一種經典的基于中心的密度聚類算法，DBSCAN算法的定義如下：
定義1：（Eps—鄰域）給定某個對象q，q的鄰域 定義為以p為核心，以Eps為半徑的d維超球體的區(qū)域，公式表示為： 其中，d為空間R的維度。dist（q，p）表示對象q和p之間的直線距離。
定義2：（核心點、邊界點，噪音點）對于數(shù)據(jù)對象q，且，如果以q為中心， 以為半徑，若內的點數(shù)超過給定MinPts，則稱q為核心點，若q不是核心點，但在某個核心點的鄰域內，則稱為邊界點，其余為噪聲點和離群點。
定義3：（直接密度可達），如果q屬于r的Eps—鄰域，且r是核心對象，則稱q從r直接密度可達。
定義4：（密度可達）密度存在對象鏈，，若所有的對象從對象關于Eps和MinPts直接密度可達，則稱q從p關于Eps和MinPts密度可達。
定義5：（密度連接）給定對象r，若p和q都是從r出發(fā)，關于Eps和MinPts密度可達的，則稱p和q是關于Eps和MinPts密度連接的。
定義6：（聚類）對象集D的非空集合C是一個關于MinPts和Eps的聚類，當且僅當滿足下面條件： 最大性：：若，且q是從p關于Eps和MinPts密度可達的，那么； 連通性：：p與q是關于Eps和MinPts密度連接的。
2 SADBSCAN—DLP算法
SADBSCSAN—DLP算法的思想：為了能直觀的描述改進算法，我們構造了帶有三個不同密度層次的樣本數(shù)據(jù)集，如圖2（a）。并計算出其對應的KNN矩陣，對KNN矩陣中的某一列進行曲線擬合得到distk圖，如圖2（b），再計算每一列的密度變化率DenVar，然后可以得到每一列的密度變化率的一個序列DenVarList，然后再以DenVarList序列的下標作為橫坐標，對應的DenVar值作為縱坐標，繪出DenVar圖，如圖2（c）。 根據(jù)DenVarList序列的統(tǒng)計特性，β的定義如下： 改進算法的具體步驟如下： 根據(jù)閾值β定義計算出KNN矩陣中每一列的β； 通過β和KNN中每一列的DenVarList序列對每一列進行密度層次分層； 根據(jù)分層結果計算出KNN中能使CEI到達最大值所對應的第k列，將k作為minPts； 根據(jù)分層結果，計算出每一層的Epsi，Epsi的計算方法如下： 在不同的DLSi上進行聚類，最后合并聚類結果。
3 實驗結果
為了分析和觀察實驗結果，我們使用了來自UCI的兩組不同的數(shù)據(jù)集。實驗在Matlab V7。1軟件下實現(xiàn)進行。使用Rand—Index來比較三種聚類算法的效果。 表1 結果比較 數(shù)據(jù)集 算法參數(shù) 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給出了三個算法的實驗對比結果。可以看出，在數(shù)據(jù)集Iris中使用所改進的算法的準確度要高于其它兩個算法
4 結 語
本文針對DBSCAN算法和DBSCAN—DLP算法的不足提出了改進。實驗結果表明改進的算法SADBSCAN—DLP算法有效減少了傳統(tǒng)DBSCAN聚類算法對參數(shù)的敏感度，對聚類效果有很大的提升。
參考文獻 [1]Xutao Li， Yunming Ye， Mar
【針對非均勻數(shù)據(jù)集自適應聚類算法的研究論文】相關文章：
關于描述CRP模型中的聚類算法的論文06-16
計數(shù)查找算法研究精選論文04-05
淺析禮服的自適應定制研究論文05-27
近場聲源定位算法研究論文06-18
基于屬性重要度約簡算法在數(shù)據(jù)挖掘中的應用研究論文10-30
大數(shù)據(jù)環(huán)境下的數(shù)據(jù)安全研究論文10-30