[發明專利]一種基于拉普拉斯中心性的峰值聚類方法

在審

• 申請號: 201710292849.4
• 申請日: 2017-04-28
• 公開（公告）號: CN107194415A
• 公開（公告）日: 2017-09-22
• 發明（設計）人: 楊旭華;陳果;朱欽鵬
• 申請（專利權）人: 浙江工業大學
• 主分類號: G06K9/62
• 分類號: G06K9/62
• 代理公司: 杭州斯可睿專利事務所有限公司33241
• 代理人: 王利強

技術領域

本發明涉及到機器學習領域，特別是指一種基于拉普拉斯中心性的峰值聚類方法。

背景技術

機器學習是人工智能領域中十分活躍的一個重要分支,其研究目標主要是讓計算機模擬或實現人類的學習行為，以獲取新的知識或技能。聚類方法屬于機器學習中的無監督學習算法，可以提取數據內在的隱含結構，將具有相似性屬性的數據點聚成一個類簇，類簇內部的數據點具有較大的相似性，而不同類簇的數據點相似性比較低。聚類方法在計算機和其他學科的許多領域具有廣泛的應用價值。

研究者們在聚類算法上已經做出了很多有益的工作，比如基于劃分的聚類算法：K-means是基于一個優化的目標函數通過反復迭代，降低目標函數的差異值，當目標函數逐漸收斂，劃分完成K個類簇，算法缺點是要先驗地指定類簇數目K或類簇中心，聚類的魯棒性不高；基于密度聚類算法：DBSCAN算法是基于密度的空間聚類算法，該算法采用空間索引技術來搜索對象的鄰域，引入了“核心對象”和“密度可達”等概念，從核心對象出發，把所有密度可達的對象組成一個類簇。算法優點是聚類速度快且能夠有效處理噪聲點和發現任意形狀的空間類簇，缺點是仍然是需要預先指定參數，算法的魯棒性不好。一種新的基于Delta-Density的聚類算法(DDC)最近在Science發表，算法的核心思想是巧妙地提出和利用了密度和一個基于距離的新指標δ去快速地發現高密度節點峰值。具有高密度和高δ值的節點被確信為類簇中心。然后，再把除去類簇中心的節點逐步地分配到已經確信的類簇中心，直至完成類簇的劃分，實驗結果表明其具有良好的聚類效果。DDC算法的缺點是需要事先給定一個經驗參數截斷距離，該參數對聚類性能影響巨大但沒有一個有效地估計其合適數值的方法等；基于層次的聚類算法:BIRCH算法利用樹結構對數據集進行處理，葉結點存儲一個聚類，用中心和半徑表示，順序處理每一個對象，并把它劃分到距離最近的結點，該算法也可以作為其他聚類算法的預處理過程。算法缺點是對輸入數據的先后順序敏感，魯棒性不高；基于網格的聚類算法：CLIQUE算法是一種結合了網格和密度的聚類算法,利用自頂向上方法求出各個子空間的聚類單元；算法缺點是空間和時間效率都較低，需要輸入的參數具有不確定性。當然還有很多其他的聚類算法，像基于自組織神經網絡和基于統計方法的聚類算法等。

發明內容

為了克服已有聚類方法精確度不高、需要提前設定參數等不足之處，本發明提出一種聚類精確度高、無需提前設定參數的基于拉普拉斯中心性的峰值聚類方法。

本發明解決其技術問題所采用的技術方案是：

一種基于拉普拉斯中心性的峰值聚類方法，包括以下步驟：

步驟一：建立數據集模型D＝{v_i}，i＝1…n，其中v_i為數據集D中的任意數據點，數據點v_i和v_j之間的距離值為d_ij；

步驟二：將待分類數據集D轉化成為一個加權完全圖模型G，G中的一個節點表示數據集中的一個數據點，其中任意兩個節點之間邊的權值就是相應兩個數據點之間的距離，獲取加權完全圖G的權值矩陣：

其中w_i,j為節點v_i與v_j之間的邊權值；

步驟三：根據權值矩陣W(G)計算表示每個節點到其它所有節點的權重的和所組成的對角矩陣：

其中，是節點v_i的和其他所有節點之間的邊權值之和；

步驟四：計算加權完全圖G的拉普拉斯矩陣：

L(G)＝X(G)-W(G)；

步驟五：計算加權完全圖G的拉普拉斯能量值：

步驟六：計算加權完全圖G中任意節點v_i的拉普拉斯中心性c_i：

其中,E_L(G_i)為去掉節點v_i后的拉普拉斯能量值；

步驟七：對加權完全圖G中任意節點v_i，將該節點的c_i值和其他節點的Laplacian中心性數值作比較，得到所有拉普拉斯中心性比c_i高的節點集合，并計算節點v_i與該集合中每個節點的距離的最小值δ_i；