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

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

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

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

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

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