決策圖聚類算法的研究及應(yīng)用.pdf

1、隨著時代發(fā)展，特別是近幾年進(jìn)入數(shù)據(jù)爆炸的時代，數(shù)據(jù)挖掘領(lǐng)域的重要性越發(fā)凸顯。而一些經(jīng)典的算法及其改進(jìn)已經(jīng)無法滿足日益增長的對數(shù)據(jù)處理的要求了。聚類，作為數(shù)據(jù)挖掘中一個重要的領(lǐng)域，對于更加優(yōu)秀的聚類算法的需求也是日益迫切。在新時代，對聚類算法的時空間效率以及聚類效果當(dāng)然要求更高，但是新時代對其的要求并不止于此，一個優(yōu)秀的聚類算法除此之外還應(yīng)該具有以下性質(zhì):可擴(kuò)展性和可伸縮性;識別任意形狀的類簇的能力;自動確定類簇數(shù)的能力;輸入?yún)?shù)足夠少;

2、輸入?yún)?shù)敏感性足夠低;具有對離群點(diǎn)的識別能力;對輸入數(shù)據(jù)的兼容性;可約束性等。
　　決策圖(Decision Graph)聚類算法，可簡稱DG算法，根據(jù)作者論文標(biāo)題首字母縮寫又可叫CFSFDP算法。于2014年6月在Science雜志上一經(jīng)刊載出來就受到了廣泛的討論。該算法幾乎完全具備以上性質(zhì)，比如它不需要事先指定聚類數(shù)量;需提前設(shè)定的參數(shù)很少，只有一個，且敏感度較低;可以非常簡單地確定離群點(diǎn);整體算法復(fù)雜度比一般的K-means

3、算法的復(fù)雜度更低;可以得到非球形的聚類結(jié)果，可以很好地識別異形數(shù)據(jù)分布。除此之外DG算法還具有其他非常優(yōu)秀的性質(zhì)，能夠僅以待聚類點(diǎn)之間的距離矩陣作為輸入數(shù)據(jù)，而并不需要將點(diǎn)映射到向量空間中;算法穩(wěn)定，只要輸入的數(shù)據(jù)源是同樣的，那么得到的聚類結(jié)果也是同樣的等。而最重要的是，DG算法在選取聚類中心的算法思想上另辟蹊徑，非常簡潔巧妙。對于該算法，有對其選取聚類中心的巧妙方法大加贊揚(yáng)的;也有對該算法的如選取聚類中心需要人工參與等問題進(jìn)行質(zhì)疑的。

4、筆者對此是持肯定態(tài)度的，畢竟該算法優(yōu)秀之處有目共睹，不足之處也并不是硬傷，經(jīng)過廣泛的優(yōu)化改進(jìn)之后，其未必不能成為聚類領(lǐng)域的又一經(jīng)典算法。文本也是在對該算法的問題發(fā)現(xiàn)以及解決改進(jìn)方面提供了一份貢獻(xiàn)。
　　本文的主要內(nèi)容就是針對筆者發(fā)現(xiàn)的一個該算法設(shè)計上的問題:密度沖突問題。該問題主要是出在計算決策圖算法的重要參數(shù)δ時，對需要考慮的基于另外一個重要參數(shù)ρ的判斷條件存在漏洞。于是本文之后舉出該問題會導(dǎo)致的錯誤聚類結(jié)果，然后就該問題設(shè)計了

5、兩種分別基于δ和基于ρ的改進(jìn)方案。然后在設(shè)計、實(shí)現(xiàn)了這兩種改進(jìn)算法后，用對比性實(shí)驗(yàn)驗(yàn)證了原算法的出現(xiàn)的錯誤以及改進(jìn)算法的解決效果，以及用驗(yàn)證性實(shí)驗(yàn)驗(yàn)證了改進(jìn)決策圖算法最主要的兩大特點(diǎn):可以是被異形類簇、可以不依賴于數(shù)據(jù)點(diǎn)之間的空間分布而只以數(shù)據(jù)點(diǎn)之間的距離矩陣作為輸入數(shù)據(jù)。最后針對決策圖算法選擇聚類中心的另辟蹊徑的巧妙算法的應(yīng)用，選擇將其實(shí)現(xiàn)于簡單經(jīng)典的K-means算法上。設(shè)計并實(shí)現(xiàn)了新算法DG-means之后，設(shè)計對比實(shí)驗(yàn)驗(yàn)證了新算