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