針對(duì)非均勻數(shù)據(jù)集自適應(yīng)聚類算法的研究論文
摘 要：傳統(tǒng)DBSCAN算法需要輸入兩個(gè)特定的參數(shù)（minPts和Eps），這對(duì)于沒(méi)有經(jīng)驗(yàn)的使用者是很困難的。同時(shí)，如果在多密度的數(shù)據(jù)集中使用全局的Eps參數(shù)，也會(huì)對(duì)聚類結(jié)果的質(zhì)量造成大的影響。所以，針對(duì)以上兩個(gè)問(wèn)題，結(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），并且其無(wú)法處理多密度的數(shù)據(jù)集。針對(duì)這兩個(gè)問(wèn)題，筆者提出一種基于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算法。
1 傳統(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ù)超過(guò)給定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密度連接的。
2 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矩陣中每一列的β； 通過(guò)β和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é)果。
3 實(shí)驗(yàn)結(jié)果
為了分析和觀察實(shí)驗(yàn)結(jié)果，我們使用了來(lái)自UCI的兩組不同的數(shù)據(jù)集。實(shí)驗(yàn)在Matlab V7。1軟件下實(shí)現(xiàn)進(jìn)行。使用Rand—Index來(lái)比較三種聚類算法的效果。 表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è)算法
4 結(jié) 語(yǔ)
本文針對(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
【針對(duì)非均勻數(shù)據(jù)集自適應(yīng)聚類算法的研究論文】相關(guān)文章：
淺析禮服的自適應(yīng)定制研究論文05-27
近場(chǎng)聲源定位算法研究論文06-18
基于屬性重要度約簡(jiǎn)算法在數(shù)據(jù)挖掘中的應(yīng)用研究論文10-30
大數(shù)據(jù)環(huán)境下的數(shù)據(jù)安全研究論文10-30
關(guān)于淺析非均勻分布冗余DRAM 的修復(fù)方法的論文05-28
CCD測(cè)量系統(tǒng)中基于自適應(yīng)相關(guān)算法的動(dòng)態(tài)目標(biāo)跟蹤的論文06-16