優(yōu)先聚類和高斯混合模型樹相融合的遞增聚類研究

資和周

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

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

中圖分類號： 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 引 言

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

1 基于優(yōu)先聚類和高斯混合模型樹的遞增聚類

方法

1.1 優(yōu)先聚類算法

優(yōu)先聚類算法的示意圖如圖1所示。

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

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

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

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

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

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

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

1.2.1 高斯混合模型樹的構建

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

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

1.2.2 數(shù)據(jù)插入

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

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

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

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

[Co=argmaxkPXCk] （2）

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

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

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

1.2.3 數(shù)據(jù)刪除

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

[μ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）的推算過程如下：

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

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

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

新數(shù)據(jù)點被安插至原數(shù)據(jù)集，進而得到新的數(shù)據(jù)集：

[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）

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

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

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

對一個數(shù)據(jù)點進行刪除操作后的數(shù)據(jù)集為：[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）

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

[μ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 高斯混合模型樹的更新

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

1.2.5 聚類結果的確定

本文基于類內(nèi)距離和類間聚類兩個指標，獲取高質量的聚類結果。類內(nèi)聚類越小，類間聚類越大，說明聚類效果越優(yōu)。高斯混合模型樹的非葉子節(jié)點描述了模型的數(shù)據(jù)分布情況[9]，高斯分布是最小的數(shù)據(jù)單元?；诟咚够旌夏Ｐ偷南嗨贫染垲惞剑\算類內(nèi)聚類和類間聚類公式為：

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

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

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

[CQ=ICIS] （20）

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

2 實驗結果與分析

2.1 有效性分析

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

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

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

2.2 可擴展性和穩(wěn)定性分析

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

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

3 結 語

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

參考文獻

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

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

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

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

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

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

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

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

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