[發明專利]一種高斯混合模型樹及其遞增聚類方法

有效

• 申請號: 201410035056.0
• 申請日: 2014-01-24
• 公開（公告）號: CN103823843B
• 公開（公告）日: 2017-02-22
• 發明（設計）人: 劉峽壁;伍藝;萬玉釵
• 申請（專利權）人: 北京理工大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 暫無信息
• 代理人: 暫無信息

技術領域

本發明涉及一種遞增聚類結構——高斯混合模型樹，及其遞增聚類方法，屬于計算機應用技術中的聚類技術領域。

背景技術

隨著大數據時代的到來，數據在人們的生活和工作中起到越來越重要的作用。目前，在互聯網上已經存在海量的數據，并且其數量還在高速增長。例如，據Alexa統計，最出名的在線照片分享網站www.flickr.com，全球訪問量排名二十三，月均訪問量達六千萬，共上傳五十多億張照片。為了更好的將數據進行自動的分類，聚類技術受到了越來越多的關注。

目前，已有的聚類方法大多為靜態聚類方法，即每次執行聚類方法之前都需要掃描整個數據集，諸如K-均值方法，EM-MDL方法，DENCLUE方法，CLIQUE方法等。但是，在大數據時代，傳統的靜態聚類方法面臨著較大的技術瓶頸：第一，隨著數據量的不斷增大，數據占有的內存空間也隨之增加，當數據集本身占有的空間超過了計算機內存的空間時，數據集中的數據不能被預先存儲至計算機內存；第二，隨著數據增長的速度不斷提高，如果每次執行聚類方法都需要對整個數據集進行重新聚類，計算復雜度和時間復雜度都變得很難接受。

遞增式聚類方法可以較好的解決以上問題，但相關研究仍處于發展較為初級的階段。遞增式聚類方法可以分批次地將圖片讀取至內存，進行聚類，魯棒的遞增式聚類方法的聚類結果可以接近甚至優于傳統靜態聚類方法。

BIRCH是一種經典的遞增式聚類方法，并以樹型結構表示聚類過程和結果，每個節點表示數據的特征，包括數據的數量，數據的線性和，數據的平方和，但是BIRCH方法只能得到最小的數據單元；Littau和DanielBoley使用低內存的分解式矩陣來表示數據，并用這種矩陣來完成聚類；Duan在傳統Clique方法的基礎上提出了K-Clique方法，該方法主要基于深度優先的“搜索森林”數據更新技術；Ester等人改進了傳統的DBSCAN方法，使之具有遞增式聚類方法的優點，在數據插入和刪除時只影響它臨近的數據。

發明內容

本發明的目的是為了解決在大數據時代，隨著數據量和數據增長速度的增加，傳統聚類方法在計算復雜度和時間復雜度方面變得難以接受問題而提出了一種高斯混合模型樹及其遞增聚類方法。

本發明的目的是通過下述技術方案實現的。

一種高斯混合模型樹及其遞增聚類方法，包括兩部分：

（1）一種新的聚類結構——高斯混合模型樹（聚類樹），高斯混合模型樹的葉子節點對應著單個高斯成分，反映了該高斯混合模型樹中最稠密的數據分布，分布的稠密程度由單高斯成分的最大方差控制。數據稠密程度自下而上變得稀疏，樹的高層節點由低層的節點組合而成，即高斯成分的組合，高層節點對應更稀疏的數據分布，根節點對應著整個數據集的高斯分布，也是該高斯混合模型樹中最稀疏的數據分布。該高斯混合模型樹由上述的葉子節點和高層節點構成，反映了數據聚類、子聚類、整個數據集的關系；葉子節點對應單個高斯成分，節點對應高斯混合模型；樹的構建方式是自底向上的；

（2）在（1）的基礎上，提出基于高斯混合模型樹的遞增聚類方法；其中，遞增聚類方法包括數據插入、更新聚類樹、數據刪除和聚類結果確定。這四個技術環節的關系為：對于每一個新數據，都需要插入到現有的高斯混合模型樹，再根據插入的結果更新聚類樹；隨著新數據的插入，檢查已經插入到聚類樹的數據是否需要刪除，如果需要刪除，則刪除數據；當所有數據讀取完成之后，確定聚類結果。

技術環節1.數據插入：將每一個新數據插入至高斯混合模型樹的葉子層，有可能插入到現有的葉子節點，也有可能生成新的葉子節點；判斷是否生成新葉子節點的標準為：計算新插入的數據與葉子節點的均值的歐氏距離；

技術環節2.更新聚類樹：當新的數據被插入到最恰當的葉子節點后，當前的高斯混合模型樹的結構和參數會隨之更新，更新的節點包括插入新數據的葉子節點和與之相關的高層節點；聚類樹結構的變化主要體現在高層節點是否需要分裂，參數的變化包括葉子節點中單個高斯成分的參數、高層節點中高斯混合模型的參數；更新聚類樹結構時，通過計算高層節點對應的子節點的連通圖個數來判斷是否要分裂以及分裂的個數；