優先聚類和高斯混合模型樹相融合的遞增聚類研究

資和周

摘 要： 傳統聚類算法實現大數據集聚類時，耗費大量的時間和內存，無法適應大數據流的動態性，聚類穩定性較差。因此，提出基于優先聚類和高斯混合模型樹的遞增聚類方法。采用優先聚類算法對大數據集進行優先聚類，獲取典型數據集，降低大數據集的數據復雜度，采用高斯混合模型樹的遞增聚類算法，將典型數據集中的數據插入到高斯混合模型樹內，塑造數據集的高斯混合模型樹，樹的葉子節點和非葉子節點分別同單高斯數據分布和高斯混合模型分布對應，基于插入結果對高斯混合模型樹實施調整，檢測插入到模型樹內的數據是否需要刪除，并完成數據的刪除操作，采用廣度優先方法獲取最佳的樹節點作為最終的聚類結果。實驗結果表明該算法取得了很好的效果，具有較高的可擴展性和穩定性。

關鍵詞： 大數據； 聚類分析； 高斯混合模型； 仿真實驗

中圖分類號： TN911.1?34； TP391.4 文獻標識碼： A 文章編號： 1004?373X（2017）19?0177?05

Research on incremental clustering integrating priority clustering

with Gaussian mixture model tree

ZI Hezhou

（School of Finance and Trade Management， Yunnan College of Business Management， Kunming 650106， China）

Abstract： The traditional clustering algorithms consume a large amount of time and memory for large dataset clustering， can′t adapt to the dynamic performance of big data flow， and have poor clustering stability. Therefore， an incremental clustering method based on partial?priority clustering and Gaussian mixture model tree is put forward. The partial?priority clustering algorithm is used to perform the priority clustering for large dataset， acquire the typical dataset， and reduce the data complexity of large dataset. And then the incremental clustering algorithm based on Gaussian mixture model tree is used to insert the data in typical dataset into a Gaussian mixture model tree to construct the Gaussian mixture model tree of the dataset. The leaf nodes and none?leaf nodes of the tree are matched with single Gaussian data distribution and Gaussian mixture model distribution respectively. According the insertion results， the Gaussian mixture model tree is adjusted， the data inserted into the model should be deleted whether or not is detected， and data deletion is accomplished. The breadth?first method is adopted to get the best tree node as the final clustering result. The experimental results indicate that the proposed incremental clustering algorithm has perfect clustering effect， strong expansibility， and high stability.

Keywords： big data； clustering analysis； Gaussian mixture model； simulation experiment

0 引 言

隨著計算機和數據分析計算的高速發展，信息在人們的生產和生活中具有重要的作用，并且當前互聯網中數據量呈現爆炸式增長，人們需要通過聚類技術從大數據環境中采集有價值的信息。聚類技術在生物學、數據挖掘、信息檢索等領域具有較高的應用價值。大數據環境下的聚類技術，成為相關人員分析的重點[1]。當前大數據集的聚類算法主要是靜態聚類算法，其對總體數據集進行檢索，耗費大量的時間和內存，并且無法適應大數據流的動態性，聚類穩定性較差[2]。因此，本文提出基于優先聚類和高斯混合模型樹的遞增聚類方法。

1 基于優先聚類和高斯混合模型樹的遞增聚類

方法

1.1 優先聚類算法

優先聚類算法的示意圖如圖1所示。

優先聚類算法從某個大數據集內任意采集樣本[A，]若分析[A]是典型樣本，則獲取典型點，否則繼續進行分析，直至獲取典型樣本。隨機從[A]內采集一個點當成原始點，設置半徑[r]以及密度閾值Minpts。若以該原始點為中心，半徑為[r]的圓內存在的數據量比Minpts大，則該樣本是典型樣本。采用[C1=xi∈pxiP]運算典型樣本的中心，將[C1]看成是典型點。以[C1]為中心實施聚類，運算[C1]同數據集內各對象間的距離：

[d（xi，xj）=xi-xj=k=1p（xik-xjk）2] （1）

若[C1]同某對象[xi]間的聚類比數值[r]低，則將該對象劃分到該類內，否則分析后續對象，直至完成數據集內全部數據的分析。

設置原始空集是[T1，]并向其融入典型點[C1，]若運算[T1]內全部點同[C1]間的距離比閾值[r]低，則將該對象[xi]融入[T1，]最終獲取第一個類[T1。]將該類中的數據從原始數據集內過濾掉，確保[T1]中的數據不再進行后續的分類，降低數據的復雜度。循環進行形成第一類的過程，直到剩余數據不再符合規范，形成相關的類是[T1，T2，…，Tk]。這些類中存在著大部分數據，并且各類中存在一個典型點[Ck（k=1，2，…，k）]。因為剩余數據是不符合規范的點，則將這些數據平均劃分成[k]類，再將其分配到前期產生的[k]個[T1，T2，…，Tk]類內，獲取的典型數據集是[T′1，T′2，…，T′k （i=1，2，…，k）]。

上述分析的優先聚類算法采用隨機大數據集樣本，獲取典型樣本以及典型點，將典型樣本的均值當成典型點實現聚類，可提高“召集”數據量，確保原數據集最大程度的縮小。獲取首個類后，從原始數據集中將其過濾掉，可大大降低原始數據集的復雜度。

1.2 高斯混合模型樹的遞增聚類算法

采用1.1節分析的優先聚類算法對大數據集進行優先聚類，獲取典型數據集，大大降低了大數據集的數據復雜度，為后續的數據遞增聚類過程提供可靠的基礎。進而采用高斯混合模型樹的遞增聚類算法實現大數據集的高精度聚類。該算法將優先聚類算法獲取的典型數據集中的數據插入到當前的高斯混合模型樹中，基于插入結果對高斯混合模型樹實施調整，檢測插入到模型樹內的數據是否需要刪除，并完成數據的刪除操作，獲取最終的聚類結果。

1.2.1 高斯混合模型樹的構建

結合高斯混合模型與樹型的框架構成高斯混合模型樹。數據聚類、子聚類以及整個數據集間的聯系可通過高斯混合模型樹呈現。由下至上組建高斯混合模型樹的方法與遞增聚類的流程一致。葉子節點與單一高斯成分相對應，構成了高斯混合模型樹中數據散布程度最密集的區域，高位節點處于數據散布稀疏區域，全部數據集的高斯混合模型分散度與根節點的分散度一致，構成高斯混合模型樹中數據分散度最高的區域。數據集中的各聚類簇頭同一個高斯混合模型對應，高斯混合模型描述了數據的分散狀態[3]。多個高斯混合模型構成了高斯混合模型樹。塑造高斯混合模型樹的流程與數據集匹配高斯混合模型的流程相同，葉子節點處于數據最密集的區域，樹的層數與數據分散度成反比。

高斯混合模型樹示意圖如圖2所示，其中[G1～G3]表示葉子節點，分別與單一高斯成分相對應，GMM1～ GMM3表示非葉子節點，與高斯混合模型相對應。由圖2可知，GMM1作為[G1，G2]的父親節點，其數據分散狀態受[G1，G2]的數據分散狀態制約。非葉子節點連接著單一高斯成分與高斯混合模型，即非葉子節點的構成可以是單一高斯成分也可以是高斯混合模型。高斯模型GMM1與GMM2組成根節點GMM3。

1.2.2 數據插入

數據插入是塑造數據集的高斯混合模型樹的關鍵。將優先聚類算法獲取的典型數據集中的各個新數據點插入到高斯混合模型樹的葉子層，獲取高斯混合模型樹。這個新數據既可能形成新的葉子節點，也可能被安插到已有的葉子節點中。基于對上文的分析，葉子節點反映出高斯混合模型樹中單高斯分布最密集的區域，使獲取的新數據能夠被精確地安插到適合的葉子節點上，需要求出新數據點與全部單高斯成分的平均值的歐式距離，其中與歐式距離最小值對應的則是待檢索的葉子節點。閾值[Tinsert]的使用可保障葉子層單高斯成分的密集度[4]，當最小的歐式距離大于該閾值時，會有新的葉子節點誕生，與該葉子節點相應的單高斯成分的方差是一個較小的起始值，數據點即是平均值；當最小的歐式距離小于該閾值時，與最小歐式距離相應的葉子節點會接收新的數據點。如果葉子節點密集度變大，會降低新插入的節點與全部葉子節點歐式距離的運算速度，因此，可由高到低即從根節點開始，依據類條件概率密度的方法確定相似度最高的葉子節點。詳細過程為：

（1） 先獲取新數據，再對不同的高斯混合模型樹已有的葉子節點量采用不同的數據安插方式，比較已存在的高斯混合模型樹葉子節點量與設定的閾值，如果已存在的高斯混合模型樹葉子節點量不大于閾值，那么接受過程（2）的方式；如果已存在的高斯混合模型樹葉子節點量大于閾值時，那么接受過程（3）的方式。

（2） 求出過程（1）獲取的新數據與全部單高斯成分的平均值的歐氏距離，并將其中最小的歐氏距離以及與之相應的葉子節點做好標記[5]；當最小的歐氏距離小于等于設定的閾值時，此歐氏距離值由相應的葉子節點保管；當最小的歐氏距離大于設定的閾值時，此歐氏距離值由形成的新葉子節點保管。

（3） 以根節點作為開端，基于類條件概率密度的方法確定相似度最高的葉子節點，類條件概率密度的公式為：

[Co=argmaxkPXCk] （2）

用[k]描述目前數據集相應的聚類量，用[P，X]分別描述條件概率以及數據，用[Ck，][Co]分別描述第[k]個聚類以及符合公式的類。過程（2）中新數據安插到已有的葉子節點時，要對新葉子節點中高斯成分的參數進行更改，更改平均值以及方差的公式為：

[μn+1=μn+1n+1xn+1-μn] （3）

[σn+1=n-1nσn+1n+1xn+1-μnxn+1-μnT] （4）

1.2.3 數據刪除

本文研究的遞增聚類算法對當前高斯混合模型樹中的數據點可以進行刪除操作。對數據進行刪除與插入數據都是以葉子層節點作為開端。當該葉子節點上僅存在一個數據點時，刪除這個數據點也就意味著刪除該葉子節點[6]。當該葉子節點上存在多個數據點時，可采用以下公式對葉子節點相應的高斯成分參數進行更改：

[μn+1=nn-1μn-1m-1xn] （5）

[Σn+1=n-1n-2Σn-n-1n?（n-2）xn-μn+1xn-μn+1T] （6）

對式（3）～式（6）的推算過程如下：

針對數據集[D1=x1，…，xm-1，xm，]平均值、方差為：

[μm=1mj=1mxj] （7）

[Σm=1m-1j=1mxj-μmxj-μmT] （8）

新數據點被安插至原數據集，進而得到新的數據集：

[D2=x1，…，xm-1，xm，xm+1] （9）

新的高斯成分的平均值為：

[μm+1=1m+1j=1m+1xj=1m+1j=1m+1xj+1m+1xm+1=mm+11mj=1mxj+1m+1xm+1=mm+1μm+1m+1xm+1] （10）

進而得到高斯成分的新方差，被安插的新數據點相應的平均值以及方差為：

[μm+1=mm+1（xj-m）+m+1m+1μm] （11）

[Σm+1=m-1mΣm+1m+1xm+1-μmxm+1-μmT] （12）

對一個數據點進行刪除操作后的數據集為：[D3=x1，x2，…，xm-1] （13）

更改后的平均值以及方差為：

[μm-1=m-xm-1j=1m-1xj] （14）

[Σm-1=1m-2j=1m-1xj-μm-1xj-μm-1T] （15）

同理可得，對一個數據點進行刪除操作后的高斯成分得到的新均值以及方差為：

[μm-1=mm-1μm-1m-1xm] （16）

[Σm-1=m-1m-2Σm-m-1mm-2xm-μm-1xm-μm-1T] （17）

1.2.4 高斯混合模型樹的更新

高斯混合模型樹的更新流程包括對相應父節點參數進行更新以及確認父節點是否具備裂變條件。對相應父節點參數進行更新的具體過程是：對數據進行安插或刪除操作后，利用全部和數據安插節點來自于同一父節點的節點，對安插節點的父節點進行參數更新[7]，其中，主要參數是與父節點相應的高斯混合模型的平均值、方差以及權重等。確認父節點是否具備裂變條件的具體過程是：求出父節點中子節點的連通圖數量，體現出父節點的連通度，同時也體現出高斯混合模型樹與數據粘稠度[8]。兩個高斯混合模型樹間的距離可通過兩個節點間的距離描述。若連通程度GQFD比閾值[Tdivide]高，則說明節點擁有較小的連通度，將該父節點分割成多個同其處于同層的新節點；否則當GQFD比閾值[Tdivide]低時，保持該父節點穩定不變。循環運行上述兩個過程，直至根節點，完成高斯混合模型樹的更新。

1.2.5 聚類結果的確定

本文基于類內距離和類間聚類兩個指標，獲取高質量的聚類結果。類內聚類越小，類間聚類越大，說明聚類效果越優。高斯混合模型樹的非葉子節點描述了模型的數據分布情況[9]，高斯分布是最小的數據單元。基于高斯混合模型的相似度聚類公式，運算類內聚類和類間聚類公式為：

[IC=i=1M1≤p≤q≤kiGQFDGpi，Gqi] （18）

[IS=1≤i≤j≤MGQFDCi，Cj] （19）

式中：設置[C1，C2，…，CM]是[M]個聚類族，各聚類族表示一個高斯混合模型；[Gji]表示第[i]個聚類族內的第[j]個高斯成分；第[i]個聚類族相關的高斯數量為[Ki]。通過聚類質量CQ能夠衡量聚類算法的聚類性能，表達式為：

[CQ=ICIS] （20）

類內聚類越低，類間距離越高，說明數據的聚類質量效果越佳。塑造完高斯混合模型樹后，基于CQ指標分析聚類效果的優劣，采用廣度優先方法獲取最佳的樹節點作為最終的聚類結果。

2 實驗結果與分析

2.1 有效性分析

實驗采用本文遞增聚類方法對菌群功能代謝通路以及表達基因兩種類型大數據集進行聚類分析，檢測本文方法的有效性。實驗分析的菌群功能代謝KEGG數據庫是常用的功能注釋數據庫，其是一種生物代謝通路分析數據庫，其中包含了完備的代謝通路地圖以及注釋說明，其還具備KAAS等在線注釋分析平臺，基于用戶提交的菌群蛋白序列，能夠得到相應的KO注釋信息，進而分析不同菌群樣本的功能代謝。基于KEGG數據庫的注釋結果，采用本文聚類方法對注釋結果實施聚類分析，獲取菌群樣本的功能代謝通路聚類情況，如圖3所示，采用不同的顏色描述聚類結果。

采用本文方法實現芯片數據的聚類分析，采用的示例芯片數據來自于GEO數據庫內GSE11787的Affvmetrix芯片的CEL文件，其中包括6個CEL文件、3個正常對照組以及3個HPS刺激組，是免疫器官脾臟的表達數據。讀入原始數據后，采用AffvBatch目標將數據變換成ExpressionSet目標，為了提高差異表達基因的檢測統計精度，采用本文方法對數據對過濾后的數據集實施遞增聚類，聚類效果圖如圖4所示。

分析圖3和圖4的結果能夠看出，本文方法實現了菌群功能代謝通路聚類以及表達基因的聚類，說明本文方法進行大數據集的數據聚類是有效的，具有較高的應用價值。

2.2 可擴展性和穩定性分析

大數據集具有動態性，穩定性好的遞增算法能夠確保在數據規模、特征維數以及聚類簇數量提高的狀態下，將內存以及時間的消耗都控制在線性增長的維度，獲取更為穩定的聚類效果，該穩定性確保算法具有較高的可擴展性。實驗檢測本文遞增聚類方法同[k]均值聚類方法、EM聚類方法的可擴展性和穩定性結果，如圖5～圖7所示。其中的矩形圖和曲線圖分別用于描述不同方法的內存耗費和時間耗費情況。

對比分析圖5～圖7能夠看出，無論在何種情況下本文方法的時間消耗和內存消耗都比其他兩種算法低。同時隨著數據規模、特征維度以及聚類簇個數的逐漸提高，本文方法的時間消耗呈現線性增長趨勢，而其他兩種方法卻呈現指數增長趨勢，說明本文方法在時間消耗方面具有較高的穩定性和可擴展性。本文方法需要進行舊節點的刪除和新節點的生成操作，需要進行的操作較多，但是隨著高斯模型樹的增長，節點合并和刪除，節點數量逐漸降低，使得本文方法的內存消耗低于其他兩種算法。并且本文方法的內存消耗呈現線性增長，確保在內存消耗上本文方法具有較高的穩定性和可擴展性。

3 結 語

本文提出一種基于優先聚類和高斯混合模型樹的遞增聚類方法，先采用優先聚類算法對大數據集進行優先聚類，獲取典型數據集，然后在典型數據集的基礎上，采用高斯混合模型樹的遞增聚類算法獲取最佳的聚類結果。

參考文獻

[1] 盧志茂，馮進玫，范冬梅，等.面向大數據處理的劃分聚類新方法[J].系統工程與電子技術，2014，36（5）：1010?1015.

[2] 張曉，王紅.一種改進的基于大數據集的混合聚類算法[J].計算機工程與科學，2015，37（9）：1621?1626.

[3] 韓巖，李曉.加速大數據聚類K?means算法的改進[J].計算機工程與設計，2015，36（5）：1317?1320.

[4] 李斌，王勁松，黃瑋.一種大數據環境下的新聚類算法[J].計算機科學，2015，42（12）：247?250.

[5] 向堯，袁景凌，鐘珞，等.一種面向大數據集的粗粒度并行聚類算法研究[J].小型微型計算機系統，2014，35（10）：2370?2374.

[6] 馬蕾，楊洪雪，劉建平.大數據環境下用戶隱私數據存儲方法的研究[J].計算機仿真，2016，33（2）：465?468.

[7] 冷泳林，陳志奎，張清辰，等.不完整大數據的分布式聚類填充算法[J].計算機工程，2015，41（5）：19?25.

[8] 周潤物，李智勇，陳少淼，等.面向大數據處理的并行優化抽樣聚類K?means算法[J].計算機應用，2016，36（2）：311?315.

[9] 龍虎，張小梅.基于修正二階錐規劃模型的大數據聚類算法[J].科技通報，2016，32（8）：168?171.