[發明專利]一種基于密度核心的最小生成樹聚類算法及系統

在審

• 申請號: 202011110208.0
• 申請日: 2020-10-16
• 公開（公告）號: CN112364887A
• 公開（公告）日: 2021-02-12
• 發明（設計）人: 高強;高琴琴;熊忠陽;張玉芳
• 申請（專利權）人: 重慶大學
• 主分類號: G06K9/62
• 分類號: G06K9/62;G06F16/2458
• 代理公司: 重慶雙馬智翔專利代理事務所(普通合伙) 50241
• 代理人: 顧曉玲

本發明提出了一種基于密度核心的最小生成樹聚類算法及系統。該算法為：構建一顆KD樹；采用自然鄰居法獲取數據點的逆近鄰信息和自然特征值，統計每個數據點的逆近鄰數目；將逆近鄰數目不小于自然特征值的數據點作為核心點，這些核心點組成密度核心點集合；根據密度核心集合建立最小生成樹，得到最小生成樹中各個邊的權值的集合；根據最小生成樹中各個邊的權值的集合計算切邊閾值，并根據該值切除最小生成樹中連接不同簇的邊，得到各個子簇最小生成子樹；根據得到的子簇最小生成子樹聚類密度核心；將非密度核心點分配到距離其最近的密度核心的簇中，完成聚類。該算法能夠較好的保留簇的大致形狀和結構，使得算法能夠適應具有復雜形狀的數據集。

技術領域

本發明涉及計算機領域，具體涉及一種基于密度核心的最小生成樹聚類算法及系統。

背景技術

近些年來，數據信息呈現爆炸式增長趨勢，形成了龐大且復雜的海量數據。這些有價值的數據若不借助自動分析手段是非人工所能剖析理解的。要想從龐大并且復雜的數據中及時的提取出有效的信息，就需要有效的數據分析工具，數據挖掘技術順勢而生。

數據挖掘可以分為以下三個步驟：預處理、數據分析和知識評價。在從數據源獲得原始數據后，利用數據清洗、數據轉換、特征選擇和特征抽取等數據預處理方法進行預處理，然后選取數據分析算法對處理過的數據進行分析從而得到其中有用的數據信息。知識評價是指將數據挖掘得到的知識，利用不同的評估函數進行評估，最后使用圖表或者可視化等技術讓人們能夠易于理解，幫助人們更好的從中獲取信息。

數據挖掘主要包括關聯規則分析、分類、聚類和離群點檢測等技術。針對用戶不同的需求，采用不同的策略方法進行數據挖掘。關聯規則分析是通過分析數據找出事物之間存在的必然聯系，發掘出有價值的信息；分類屬于一種有監督的學習，其使用一群已知類別屬性的樣本，訓練一種模型使其能夠對未知類別的樣本進行分類；聚類分析屬于無監督學習，其訓練樣本的分類信息是未知的，算法需要根據數據對象彼此之間的相似性和簇之間相異性，將數據集劃分為多個子簇，使得同簇內對象彼此相似，不同簇之間彼此相異。離群點檢測是從數據集中識別出那些不同于正常分布的數據點的過程。

聚類算法屬于無監督學習算法，無監督學習是指從沒有標注的數據中識別模式的特征，有監督學習則是需要大量的帶有正確的標注的數據集作為訓練集。然而在實際生活中，數據集往往缺乏先驗知識沒有被標注，對這些大量且復雜的數據進行標注又將耗費大量的人力物力或者是難以被標注。聚類分析正是為了解決這種重要的問題應運而生的方法，因此在數據挖掘和數據分析領域有著極其重要的作用。

聚類分析算法在實際生產生活中有著廣泛的需求，各種聚類算法也是各有千秋。根據聚類分析方法的思想的不同，經典的聚類算法有以下劃分：基于劃分的聚類算法、基于層次的聚類算法、基于密度的聚類算法和基于網格的聚類算法。

隨著數據分析領域的需求不斷提高，對于聚類算法的適應性要求也在不斷的提高，亟需高質量的算法解決實際問題。但是許多經典算法并不具備普適性，大多數的算法都有特定適應的數據集，沒有一種算法能夠滿足所有的數據集，同時應用場景的多變性，大數據的復雜性，不斷要求新的聚類算法能夠適應數據分布多樣、聚類數目不確定、特征維度大等問題，如何有效的處理這些復雜的數據給聚類算法帶來了新的挑戰。因此，研究適用于多密度層次和復雜形狀的聚類分析算法有著重要的意義。

近年來，基于中心代表點和基于密度代表點的聚類算法成為聚類算法中的研究熱點。K-Means算法和密度峰聚類算法都是典型的基于代表點的算法，尤其是密度峰聚類算法以其獨特的算法思想備受關注。密度峰聚類算法假設數據集中每個簇中都存在一個密度最大點，而且不同簇中的密度最大點相距較遠，然后通過數據對象的密度和數據對象之間的距離構造決策圖，從決策圖中選取密度代表點作為聚類的初始中心，最后將剩余點分配至代表點所在的簇。密度峰聚類算法能夠有效的對數據集進行聚類，但是其需要手動的選取聚類中心，不能處理具有復雜形狀的數據集，以及時間復雜度高等缺點。

發明內容