第一篇：針對(duì)非均勻數(shù)據(jù)集自適應(yīng)聚類算法的研究論文

摘 要：傳統(tǒng)DBSCAN算法需要輸入兩個(gè)特定的參數(shù)（minPts和Eps），這對(duì)于沒有經(jīng)驗(yàn)的使用者是很困難的。同時(shí)，如果在多密度的數(shù)據(jù)集中使用全局的Eps參數(shù)，也會(huì)對(duì)聚類結(jié)果的質(zhì)量造成大的影響。所以，針對(duì)以上兩個(gè)問題，結(jié)合密度層次分層和聚類效果指數(shù)CEI的思想提出一種改進(jìn)的DBSCAN算法。實(shí)驗(yàn)結(jié)果表明，改進(jìn)的DBSCAN算法要優(yōu)于傳統(tǒng)的DBSCAN算法。

關(guān)鍵詞：DBSCAN；多密度；自適應(yīng)；密度層次劃分

數(shù)據(jù)挖掘是關(guān)于數(shù)據(jù)分析的技術(shù)，它能夠從大量的數(shù)據(jù)中提取隱藏和有意義的關(guān)系和模式。聚類分析作為一種重要的數(shù)據(jù)分析方法，主要用于將數(shù)據(jù)集中的對(duì)象分成多個(gè)類或者簇，使得同一個(gè)類和簇中的對(duì)象之間有較高的相似度，而不同對(duì)象之間的差別很大。DBSCAN作為經(jīng)典的基于密度的聚類算法，它能夠在包含有噪聲和邊界點(diǎn)的數(shù)據(jù)集中發(fā)現(xiàn)任意形狀的簇。但是DBSCAN算法需要輸入兩個(gè)特定的參數(shù)（minPts和Eps），并且其無法處理多密度的數(shù)據(jù)集。針對(duì)這兩個(gè)問題，筆者提出一種基于DBSCAN—DLP算法的針對(duì)非均勻數(shù)據(jù)集的自適應(yīng)聚類算法SADBSCSAN—DLP（A Self—Adaptive Density—Based Spatial Clustering of Application with Noise based on Density Levels Partitioning）。實(shí)驗(yàn)結(jié)果表明，該算法在對(duì)參數(shù)敏感性和在多密度環(huán)境下聚類的準(zhǔn)確性兩方面要優(yōu)于傳統(tǒng)的DBSCAN算法。傳統(tǒng)DBSCAN算法

DBSCAN算法作為一種經(jīng)典的基于中心的密度聚類算法，DBSCAN算法的定義如下：

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

定義2：（核心點(diǎn)、邊界點(diǎn)，噪音點(diǎn)）對(duì)于數(shù)據(jù)對(duì)象q，且，如果以q為中心，以為半徑，若內(nèi)的點(diǎn)數(shù)超過給定MinPts，則稱q為核心點(diǎn)，若q不是核心點(diǎn)，但在某個(gè)核心點(diǎn)的鄰域內(nèi)，則稱為邊界點(diǎn)，其余為噪聲點(diǎn)和離群點(diǎn)。

定義3：（直接密度可達(dá)），如果q屬于r的Eps—鄰域，且r是核心對(duì)象，則稱q從r直接密度可達(dá)。

定義4：（密度可達(dá)）密度存在對(duì)象鏈，若所有的對(duì)象從對(duì)象關(guān)于Eps和MinPts直接密度可達(dá)，則稱q從p關(guān)于Eps和MinPts密度可達(dá)。

定義5：（密度連接）給定對(duì)象r，若p和q都是從r出發(fā)，關(guān)于Eps和MinPts密度可達(dá)的，則稱p和q是關(guān)于Eps和MinPts密度連接的。

定義6：（聚類）對(duì)象集D的非空集合C是一個(gè)關(guān)于MinPts和Eps的聚類，當(dāng)且僅當(dāng)滿足下面條件： 最大性：：若，且q是從p關(guān)于Eps和MinPts密度可達(dá)的，那么； 連通性：：p與q是關(guān)于Eps和MinPts密度連接的。SADBSCAN—DLP算法

SADBSCSAN—DLP算法的思想：為了能直觀的描述改進(jìn)算法，我們構(gòu)造了帶有三個(gè)不同密度層次的樣本數(shù)據(jù)集，如圖2（a）。并計(jì)算出其對(duì)應(yīng)的KNN矩陣，對(duì)KNN矩陣中的某一列進(jìn)行曲線擬合得到distk圖，如圖2（b），再計(jì)算每一列的密度變化率DenVar，然后可以得到每一列的密度變化率的一個(gè)序列DenVarList，然后再以DenVarList序列的下標(biāo)作為橫坐標(biāo)，對(duì)應(yīng)的DenVar值作為縱坐標(biāo)，繪出DenVar圖，如圖2（c）。根據(jù)DenVarList序列的統(tǒng)計(jì)特性，β的定義如下： 改進(jìn)算法的具體步驟如下： 根據(jù)閾值β定義計(jì)算出KNN矩陣中每一列的β； 通過β和KNN中每一列的DenVarList序列對(duì)每一列進(jìn)行密度層次分層； 根據(jù)分層結(jié)果計(jì)算出KNN中能使CEI到達(dá)最大值所對(duì)應(yīng)的第k列，將k作為minPts； 根據(jù)分層結(jié)果，計(jì)算出每一層的Epsi，Epsi的計(jì)算方法如下： 在不同的DLSi上進(jìn)行聚類，最后合并聚類結(jié)果。

實(shí)驗(yàn)結(jié)果

為了分析和觀察實(shí)驗(yàn)結(jié)果，我們使用了來自UCI的兩組不同的數(shù)據(jù)集。實(shí)驗(yàn)在Matlab V7。1軟件下實(shí)現(xiàn)進(jìn)行。使用Rand—Index來比較三種聚類算法的效果。表1 結(jié)果比較 數(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給出了三個(gè)算法的實(shí)驗(yàn)對(duì)比結(jié)果?？梢钥闯觯跀?shù)據(jù)集Iris中使用所改進(jìn)的算法的準(zhǔn)確度要高于其它兩個(gè)算法結(jié) 語

本文針對(duì)DBSCAN算法和DBSCAN—DLP算法的不足提出了改進(jìn)。實(shí)驗(yàn)結(jié)果表明改進(jìn)的算法SADBSCAN—DLP算法有效減少了傳統(tǒng)DBSCAN聚類算法對(duì)參數(shù)的敏感度，對(duì)聚類效果有很大的提升。

參考文獻(xiàn) [1]Xutao Li，Yunming Ye，Mar