[發明專利]一種基于密度峰值的高效層次聚類方法

在審

• 申請號: 201510957655.2
• 申請日: 2015-12-18
• 公開（公告）號: CN105631465A
• 公開（公告）日: 2016-06-01
• 發明（設計）人: 王國胤;徐計;鄧偉輝;尚明生;張學睿
• 申請（專利權）人: 中國科學院重慶綠色智能技術研究院
• 主分類號: G06K9/62
• 分類號: G06K9/62
• 代理公司: 北京同恒源知識產權代理有限公司 11275
• 代理人: 廖曦

技術領域

本發明屬于數據處理技術領域，涉及一種基于密度峰值的高效層次聚類方法。

背景技術

現實世界中隨時隨地發生著數據采集和數據生成。理解這些數據，揭示它們背后 的模式和趨勢是數據挖掘、機器學習和智能信息處理的主要任務。聚類是一種用于數據分 析和解釋的通用技術和算法框架，它依照對象之間的相似性把數據組織成“簇”(或者 “類”)。

根據聚類結果的結構區分，聚類可以分為扁平聚類(又稱劃分聚類)和層次聚類。 扁平聚類得到的結果是一種對原數據集的劃分，它只有一個層次。扁平聚類概念簡單，運行 高效，但存在一定的不足。其一，有些時候，聚類返回的結果包含很多類(例如>20類)，根據 Miller的“7±2”準則，人們其實不能將注意力很好地分配到9個以上的對象上，因此需要構 建成層次結構，將相似性較大的幾個類進一步合并成一個上層的類從而形成高層的聚類結 果。其二，很多情況下，數據集中蘊含的概念本身就具有層次性，單一層次的扁平聚類就不 能反應這一客觀實際。為此，針對上述情況，有必要將扁平聚類改造成為層次聚類，以便在 一次運行后，得到多層上的聚類結果。層次聚類比扁平聚類含有更豐富的信息。一般地，層 次聚類根據構建層次的順序(或者方向)，可以分為拆分層次聚類(自頂向下)和聚合層次聚 類(自底向上)。

現有的層次聚類方法主要有兩點局限：一是某些算法對數據集形狀敏感，不能很 好的解決非球形數據的聚類問題；二是某些算法效率較低，除了獲得單層聚類，還需要花費 至少O(m²)的代價來構建多個聚類層次。而在當前大數據的分析中，針對數據的多樣性 (variety)和高速性(velocity)，魯棒性和效率恰恰是數據分析需要重點考慮的指標。

2014年6月，Rodriguez和Laio在《Science》雜志上發表了一種基于密度峰值的聚 類方法(以下簡稱其為DPClus)，它通過定義兩個參數“局部密度”和“到更高密度最近鄰的 距離”來挑選出中心點，然后再將其他所有點按照一個向量NNeigh(NNeigh[i]＝j表示第i 個對象要劃分到與j相同的類中)的指示，在O(n)的時間復雜度上把其余點指派到相應的聚 類。DPClus具有思想簡單，效率高，準確性高，對數據形狀魯棒等優點。但是它有兩點不足： 一是它屬于扁平聚類，只返回一層聚類結果；二是它需要人工圈定中心點，這樣雖然可以融 入人類直覺，但是也帶來了不便，特別是當很多數據子集需要迭代地調用DPClus的情況下， 交互式地選取中心顯然是不允許的；而且，人工選取中心點，甚至會產生不合理的中心點選 取結果。

發明內容

有鑒于此，本發明的目的在于提供一種基于密度峰值的高效層次聚類方法，該方 法可以自動選取聚類中心，確定聚類層次數，并計算各個聚類層次的置信度。

為達到上述目的，本發明提供如下技術方案：

一種基于密度峰值的高效層次聚類方法，包括以下步驟：步驟一：自動選取全體中 心點并確定不同的層次上包含哪些中心；步驟二：根據各層次中心點，進行層次聚類，完成 全部層次聚類結果的表示和輸出，包括該層聚類的共識度指標。

進一步，步驟一中，通過計算機程序分析降序排列的γ參數曲線，模擬人工選取中 心點的行為，并定義一個共識度來刻畫哪些中心點可能誘導一個合理的聚類層次。

進一步，所述γ參數定義為：γ_i＝ρ_i×δ_i，1≤i≤N，它刻畫了一個數據點能夠被選 為中心的可能性，其取值在區間[0,+∞)；

用SortedGamma[N]存儲降序排列的γ參數值，SortedGammaInd[N]存儲與γ參數 值降序排列對應的數據點的序號(或ID)；從后往前觀察降序排列的γ參數曲線，整個數據 集中絕大多數非中心點的γ參數取值都很小，接近于零；然后到中心點的地方，γ參數值會 突然增大，并且在全體的中心點集合內，各個中心點的γ參數取值也會出現明顯的“臺階”； 用類似于從整體中區分出中心點的方法，用判斷增長比例的方式識別出中心點中的“臺 階”，每個“臺階”就對應了層次聚類中的一個層次。

進一步，在步驟二中，基于密度峰值的聚類(DPClus)的中間結果NNeigh,可以構建 一棵樹，該樹中每個節點(根節點除外)所屬的中心點與其父節點所屬的中心相同；每個非 根節點都由其父節點“引領”加入到父節點所屬的簇。