基于高斯混合模型的最大期望聚類算法研究

何慶， 易娜， 汪新勇， 江立斌

(中國移動通信集團廣東公司，廣州 510623)

0 引言

隨著信息技術應用領域的不斷拓展，人們掌握的數(shù)據(jù)日益增加，如何存儲和分析海量數(shù)據(jù)，成為學術研究的關鍵課題。海量數(shù)據(jù)中隱患帶有巨大價值的共識，但由于大數(shù)據(jù)冗余的問題，其價值密度比較低，很難準確發(fā)現(xiàn)其中有價值的信息[1、2]。聚類分析算法是一種在無人監(jiān)督情況下，進行數(shù)據(jù)挖掘和機器學習的方法，是進行大數(shù)據(jù)處理的重要方式。然而，聚類算法需要制定聚類個數(shù)，以串行方式運行，不適合海量數(shù)據(jù)處理。因此，本文選擇最大期望聚類算法，其通過高斯混合模型為用戶選擇合理的聚類個數(shù)， 無需憑借經驗指定。

1 聚類算法

聚類算法影響因素較多，如，判別標準、算法實現(xiàn)。在大數(shù)據(jù)處理中，聚類算法要滿足以下要求。1.可伸縮性；2.多樣性；3.發(fā)現(xiàn)任意形式簇；4.聚類高維數(shù)據(jù)處理。其中，數(shù)據(jù)集包括大量屬性，例如，文檔聚類中的關鍵詞。聚類算法適合于低維度數(shù)據(jù)分析，不適合2-3維數(shù)據(jù)分析[3、4]。最大期望聚類算法是基于模型的聚類算法[5、6]，假設樣本數(shù)據(jù)分布符合高斯混合模型，算法目的就是確定高斯部件中的參數(shù)，對給定數(shù)據(jù)進行充分擬合，得出模糊聚類。每個樣本以不同概率符合每個高斯分析，概率值由以上各個參數(shù)計算值求得。最大期望聚類算法的基礎是混合高斯模型，該模型被定義為N個高斯密度函數(shù)的線性組合，如式(1)。

(1)

(2)

最大似然估計是參數(shù)估計的主要方法，其通過似然函數(shù)獲得最大值的參數(shù)估計。高斯混合密度函數(shù)中所有參數(shù)標記為θ，那么似然函數(shù)為式(3)[7、8]：

(3)

其中θ為所參數(shù)集合，P(x|θ)為最大似然函數(shù)，N為自然數(shù)。

2 最大期望聚類算法的優(yōu)化

為了讓最大期望聚類算法的適用范圍更廣，需要對其進行優(yōu)化。首先，對公式3取對數(shù)，求出其最大值，計算公式如式(4)。

(4)

由于有和的對數(shù)，求導結果比較復雜，所以不能采用一般的計算方法，即求偏導并令導數(shù)為零的計算方法。最大期望聚類算法可以優(yōu)化為某混合高斯分布，其共有K個分布，而且對應每一個觀察到的X。如果同時知道其屬于K中哪個分布[9、10]，就可以求出其中的參數(shù)。然而，由于不知道每個X屬于哪個分布，就是說Z是觀察不到的數(shù)值，則Z是隱患變量，如式(5)。

(5)

由于Z是觀察不到的數(shù)值，所以最大期望聚類算法需要對Z的分布進行假設。依據(jù)式(5)進行參數(shù)估計，求出式(5)的最大期望值，其計算式，如式(6)。

(6)

通過上述計算以后，式(6)進行拉格朗日乘法計算，可得到式(7)。

(7)

其中，P(k|xi,θ(i-1))可以由以下式求得式(8)。

(8)

期望最大算法的整體流程是重復執(zhí)行以下2步驟，直至數(shù)據(jù)收斂：

(1)依據(jù)參數(shù)初始值，或上次迭代所得結果數(shù)值，進行似然函數(shù)計算，如式(9)。

(9)

其中的條件分布P(Z|X,θold)的期望為式(10)。

Q(θ，θold)=Ez[logP(X,Z|θ)|X,θold]

(10)

(2)對似然函數(shù)進行最大化處理，以此獲得新的參數(shù)值，用θnew對θold進行更新，實現(xiàn)Q(θ，θold)最大化。

3 大數(shù)據(jù)處理平臺下最大期望聚類算法實現(xiàn)分析

本文以Hadoop平臺為實驗平臺進行分析，該平臺屬于高效的云計算基礎平臺，利用通用硬件構建功能強大，運行穩(wěn)定，操作簡單的分布式集群計算系統(tǒng)，完全滿足大數(shù)據(jù)分析的需要。Hadoop平臺自身的開源性，使其付出相對低廉的成本[11-12]，就可以輕松處理大規(guī)模的數(shù)據(jù)群。國內利用Hadoop構建底層大數(shù)據(jù)基礎框架平臺有百度、騰訊和阿里等互聯(lián)網(wǎng)公司，也有電信、移動和聯(lián)通等傳統(tǒng)通訊企業(yè)。MapReduce是一種新的海量數(shù)據(jù)處理方式，通過抽象出高層次的數(shù)學模型，編寫出能夠在成千上百臺計算機上運行的程序，將聚類分析變得更加簡單和準確。MapReduce引擎的擴展性趨于線性，如果數(shù)據(jù)處理量增加，只需要增加相應的計算機數(shù)量即可，而其他參數(shù)和運行時間不變。另外，MapReduce穩(wěn)定性非常高，雖然個別計算機出現(xiàn)故障，但是計算集群規(guī)模為數(shù)千Note，不影響整體運行效率。對應個別計算故障問題，MapReduce進行相應完善，利用高斯混亂模型，將整體數(shù)據(jù)分析任務，進行聚類分解，妥善解決數(shù)據(jù)任務分析失敗的問題，保證其不對所屬作用的正確執(zhí)行產生影響。下面就利用MapReduce處理方式中的最大期望聚類算方法，在Hadoop平臺中選擇樣本數(shù)據(jù)進行相應分析，以國家失業(yè)率(UR)和國內人均總產值(GDP)間的關系為案例，進行相應數(shù)據(jù)說明。其中，數(shù)據(jù)來源于Hadoop平臺中2016年世界主要國家失業(yè)率數(shù)據(jù)(單位：%)和國內人均總產值數(shù)據(jù)(單位：美元)[13-14]。由于部分國家2016年數(shù)據(jù)丟失，所以選擇131個國家和地區(qū)數(shù)據(jù)進行分析，如表1所示。

表1 2016年世界主要國家失業(yè)率數(shù)據(jù)和國內人均總產值數(shù)據(jù)

由于利用數(shù)學原理進行計算，其過程比較復雜，所以采用MapReduce數(shù)據(jù)分析方式中的R語言進行數(shù)分析。首先，選擇最優(yōu)的聚類數(shù)目和一組要選擇的混合模型，對每一模型采用基于高斯混合模型的分層聚類，計算出似然函數(shù)的最大值，得出最優(yōu)高斯分布。以初始聚類結果作為最初數(shù)值，對每一模型和從2到131的多個類數(shù)進行期望值最大化法進行參數(shù)估計，計算每一情況下的BIC(貝葉斯數(shù)值)，并選擇BIC數(shù)值最大的模型，完成R語言計算中的模型選擇和數(shù)據(jù)聚類[15、16]。

依據(jù)R語言計算結果，得出BIC數(shù)值為-901.458 41，最優(yōu)類別數(shù)為3類，并對各類分別含有184,210,3個樣本，高斯混合概率密度分別為：0.412 142 17,0.521 352 82,0.098 451 24，可以在R語言中作出二維和三維的聚類概率密度圖，如圖1、圖2所示。

圖1 基于高斯混合模型的最大期望聚類二維概率密度圖

通過圖1可以大致看出各類別的主要分布區(qū)域，以及概率密度最為集中區(qū)域分別是人均國內生產總值處于45 000美元和失業(yè)率處于6%以下，以及國內人均生產總值處于15 000美元，失業(yè)率處于6%-7%之間的國家或者區(qū)域。由此可知，國內人均生產總值越高，失業(yè)率就會相對較低，但是這一特征并不明顯，也會存在國內人均生產總值較高，失業(yè)率隨之增加的現(xiàn)象[17]。

圖2 基于高斯混合模型的最大期望聚類三維概率密度圖

從圖2中的三維概率密度圖可知，失業(yè)率與國內人均生產總值之間并無必然關系，所以圖2中顯示的結果：國內人均生產總值越高，失業(yè)率就會相對較低，這一特征并不成立。

4 總結

大數(shù)據(jù)的出現(xiàn)給教育、醫(yī)療和工業(yè)等行業(yè)帶來深入影響，其中的潛在價值非常巨大。大數(shù)據(jù)具有海量性、分散性[8]，實時性和低價值密度性的特征，需要利用數(shù)學分析方法進行數(shù)據(jù)挖掘，特征聚類，發(fā)現(xiàn)其中隱藏的價值。數(shù)據(jù)分析受到高斯混合模型的影響，可以對某一數(shù)據(jù)任務進行分類表示，并成功地應用到圖像處理、語音識別領域。然而，高斯混

合模型在大數(shù)據(jù)特征分析方面仍然存在很多科學問題，所以本文圍繞大數(shù)據(jù)的本質，深入研究針對大數(shù)據(jù)分析的最大期望聚類算法。

本文首先介紹基于高斯混合模型的最大期望聚類算法的原理，對高斯混合模型進行操作簡化，然后選擇Hadoop平臺中的經濟類數(shù)據(jù)作為研究對象，并利用MapReduce處理技術中的R語言進行相應分析。在R語言中利用高斯混合模型得出最大期望聚類算法的概率密度，并用二維、三維可視化化圖進行表示，通過概率密度形象的表示，可以清楚地發(fā)現(xiàn)失業(yè)率與國內人均生產總值的集中區(qū)域。在二維可視化圖中發(fā)現(xiàn)的“國內人均生產總值越高，失業(yè)率就會相對較低”假設，經過三維可視化圖證明為不成立，說明基于高斯混合模型的最大期望聚類算法可以在大數(shù)據(jù)中發(fā)現(xiàn)有價值信息。本文將高斯混合模型應用于大數(shù)據(jù)分析，具有一定的創(chuàng)新價值，而且MapReduce中的R語言在處理高斯混合模型的數(shù)據(jù)聚類分析中，具有非常好的作用。

參考文獻

[1] 魯偉明，杜晨陽，魏寶剛，等.基于Map Reduce的分布式近鄰傳播聚類算法[J].計算機研究與發(fā)展.2012,49(8)：1762-1772.

[2] Bi-Ru Dai; I-Chang Lin. Efficient Map/Reduce-Based DBSCAN Algorithm with Optimized Data Partition [J].Cloud Computing, 2012,5(4)：59-66

[3] 翟周偉.Hadoop核心技術[M]北京：機械工業(yè)出版社，2015,9(1):2-3.

[4] 黃宜華.深入理解大數(shù)據(jù)：大數(shù)據(jù)處理與編程實踐[M]北京：機械工業(yè)出版社，2014，4(8):9-10.

[5] 孟小峰，慈樣.大數(shù)據(jù)管理:概念、技術與挑戰(zhàn)[J].計算機研究與發(fā)展，2013,2(1):7.

[6] 陳麗敏，楊靜，張健沛.一種加速迭代的大數(shù)據(jù)集譜聚類方法[J].計算機科學，2012,39(5)：172-176.

[7] 陳思慧.基于M1P和改進模糊K-Means算法的大數(shù)據(jù)聚類設計[J].計算機測量與控制，2014,22(4)：1270-1275.

[8] 高霞,李瑞俊.EM算法在不完全數(shù)據(jù)參數(shù)估計中的應用[J].集寧師范學院學報,2015,2(3):8-11.

[9] 毛海斌,張瀟笑.一種解決不平衡情感分類的EM改進算法[J].電子測試,2015,3(5):90.

[10] 浦慧忠.基于數(shù)據(jù)挖掘的一種聚類分析方法在PDM系統(tǒng)中的應用研究[J].計算機與數(shù)字工程，2016，4(11):7-10.

[11] 陳巖.電信運營商基于移動互聯(lián)網(wǎng)門戶的精細化營銷系統(tǒng)研究[J].電信工程技術與標準化，2017，4(2):8-11.

[12] 殷小紅,王君.流量精細化運營的網(wǎng)絡架構方案[J].通信管理與技術，2014，5(2):9-10

[13] 張卓筠,高功應,王磊.WLAN與LEPACN與EPC網(wǎng)絡融合架構研究[J].移動通信，2012,11(10):9-11.

[14] DHARMESTID,NUGROHOSS,et al. The antecedents of online customers at insfaction and customer loyalty. DELAROSAM，2012,8(9):8-11.

[15] 林濟鏗,劉露,張聞博,等.基于隨機模糊聚類的負荷建模與參數(shù)辨識[J].電力系統(tǒng)自動化，2013,9(14):9-12.

[16] 張粒子,王茜,舒雋.基于聚類最優(yōu)乘子向量的發(fā)輸電系統(tǒng)可靠性評估[J].電力系統(tǒng)自動化，2011,3(6):7-11.

[17] 王德青,劉曉葳,朱建平.基于自適應迭代更新的函數(shù)型數(shù)據(jù)聚類方法研究[J]. 統(tǒng)計研究，2015,4(4):7-9.

[18] MengXiaofeng.Big data management:concepts,techniques andchallenges[J].Journal of Computer Research and Development,2013,50(1)：146-169.