決策圖聚類算法的研究及應用.pdf

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

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

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

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

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