一種GMMHMM隱狀態與高斯混合成份初始化算法

張軍超 蔣強榮

摘 要：為了解決傳統隱馬爾可夫模型應用通常將隱狀態數和混合成份數看作一致的弊端，更客觀地描述問題，使模型研究適合現實的數據分布，參數設定更為精準，從而使算法效果達到最優，提出一種基于高斯混合分布、聚類思想和OEHS準則的適應數據分布且自動確定參數的算法。因隱馬爾可夫學習算法由EM算法實現，但EM是局部最優算法，嚴重依賴初始值，從跳出局部最優的角度出發，對兩個參數進行初始設定。與傳統的隨機初始化方法進行比較，實驗結果表明，該算法能得到更好的結果。

關鍵詞：隱馬爾可夫模型;GMM混合成份;隱狀態;自適應

DOI：10. 11907/rjdk. 181494

中圖分類號：TP312文獻標識碼：A文章編號：1672-7800（2019）001-0081-05

Abstract：In order to solve the problem that in traditional application of hidden Markov model， the number of hidden states and the number of mixed components are usually regarded as the same， and to describe the problem more objectively so that the model research can be very suitable for the actual data distribution， and the parameters are set more accurately to make the algorithm achieve the best results， an algorithm based on Gaussian mixture distribution， clustering idea and OEHS criterion is proposed. At the same time， the hidden Markov learning algorithm is implemented by EM algorithm， but EM is a local optimal algorithm， which depends heavily on the initial value. From the point of jumping out of local optimum， so that the initial setting of the two parameters is conducted， which can adapt to the data distribution and automatically determine the parameters. Compared with the traditional random initialization method， the experimental results show that the proposed algorithm can get better results.

0 引言

20世紀60年代，鮑姆提出了隱馬爾科夫模型（Hidden Markov Model，HMM），在語音識別領域使用，被廣大科研人員熟知。文藝復興科技公司是國際著名投資機構，因從1989年開始保持超高年回報率被業界譽為最高效的對沖基金，通過獨特的數學模型，捕捉市場機會進行量化投資，而隱馬爾科夫模型是主要工具之一[1]?？梢钥吹剑琀MM在各個領域都有應用，具有廣泛影響。常用的HMM模型可以根據觀測狀態分為兩個類別：連續型和離散型。例如，連續型的GaussianHMM、GMMHMM，離散觀測狀態的有MultinomialHMM。

離散型模型使用較為基礎，有幾個重要的參數需要設置，例如：“startprob_”表示隱狀態的初始分布概率，“transmat_”表示不同狀態間的轉移概率，“emissionprob_”表示觀測值的發射概率矩陣。許博等[2]為了實時、準確地識別多種P2P應用流，提出采用離散型HMM的P2P 流識別技術，能減少模型建立時間，提高識別未知流的實時性和準確性，并能較好地適應網絡環境變化。陳世文[3]針對微觀的具體攻擊特征檢測問題，提出一種基于多特征并行隱馬爾科夫模型，用HMM隱狀態序列與特征觀測序列的對應關系，將攻擊引起的多維特征異常變化轉化為離散型隨機變量，實驗結果表明，基于MFP-HMM（Multi-Feature Parallel Hidden Markov Model）的方法優于標準HMM等機器學習方法。

對于連續型觀測狀態的HMM模型，GaussianHMM是其主要實現，該模型假設觀測數據按照高斯函數分布，存在與離散HMM相同的幾個重要參數：Startprob、transmat和emissionprob，含義也一致，但是emissionprob成份不是以概率矩陣分布形式存在，而各個隱狀態對應的觀測值分布以單個高斯函數擬合實現概率密度函數。吳漫君[4]以隱狀態為股價未來走勢、觀察值為股價指標，對相同數據進行分析，連續隱馬爾科夫模型的實證結果優于離散模型。柳姣姣等[5]提出了一種基于時空密度聚類的連續型馬爾科夫模型對時空序列進行預測的方法，針對如何有效預測不同尺度分布的時空序列問題，采用該模型對藥品冷藏庫中的時空序列溫度數據進行分析預測，結果顯示與其它預測模型比較，該方法更準確有效。

另外還有一種重要的連續型HMM模型即GMMHMM，不同于GaussianHMM，對emissionprob的實現是由幾個不同高斯函數混合而成的，用來擬合發射概率函數。較前兩者，GMMHMM更符合現實情況，對真實問題的解釋更強，同時也更復雜。王慎波等[6]針對傳統混合高斯模型（GMM）對運動目標檢測方法計算量大、時間復雜度高的缺點，提出一種利用塊模型的混合高斯模型運動目標檢測方法，該算法平均耗時減少了46.16%，存儲空間減少不低于54.15%。王慧勇[7]基于GMM-HMM系統模型更好地解決了多口音問題中模型不匹配以及特定口音數據稀疏導致的建模難題，進而提高了識別率。在此基礎上，結合目前廣州、重慶地區數據，實驗表明：本文改進系統所帶來的相對CER下降分別為23.03%和21.21%，性能提升效果相當明顯。

1 關鍵算法理論

1.1 HMM算法

隱馬爾可夫模型（HMM）是統計模型，是在探究一個馬爾可夫過程與背后隱藏狀態關系過程中建立的模型，用來描述一個含有隱含未知參數的馬爾可夫過程[8]。HMM常用來從可觀測序列中確定該序列隱含的參數，然后利用參數進一步研究分析[9-10]。

HMM根據使用背景不同分為離散型和連續型，典型的離散型是隱狀態和觀測值概率一一對應，而連續型HMM的隱狀態和觀測值概率通過隱狀態的概率分布得到。隱馬爾科夫模型通過三元組表示[（π，A，B）]，完整表示為[（N，M，π，A，B）]。其中：N為隱狀態數，M為一個隱狀態對應的觀測值數，[π]指隱狀態的初始概率分布。

1.2 K-means理論

K-means算法對于不同初始值，可能會導致不同結果。解決方法是多設置一些不同初值，對比最后的運算結果，一直到結果趨于穩定結束。但是，很多時候事先并不知道給定數據集應該分成多少個類別才最合適。

K-means算法理論是對給定一個包含N個元素的數據集，且將其分為K個數據簇?；具^程是通過給定幾個不同的數據簇中心，通過不斷將數據歸屬簇且重新計算簇中心，盡可能達到簇間距最大而簇內距離最小的狀態。

具體K-means算法[11]：對于給定的具有N個元素的數據集[X={x1，x2，？，xN}，xi={xi1，xi2，？，xim}]表示一個數據項，m代表一個數據項維度。

K-means基本步驟：

（1）初始化。首先需要指定K參數的值，隨機給定K個不同點作為初始K個簇的中心點。

（2）計算數據歸屬。遍歷數據集X，同時計算每個數據項到K個簇中心的距離，并將其歸屬到距離最小的簇中，得到K個簇。

（3）更新簇中心。對K個簇的中心重新計算，通過新簇的數據求得平均值作為新的中心。

（4）重復步驟（2）、步驟（3）。當每個簇的中心不再變化時結束算法。

近年來有一些學者使用K-means聚類方法設定隱狀態數目[12]，但是K-means聚類算法對初始值太敏感，不同初始值會得到不同結果，而且需要事先設定k值。本文僅將K-means算法作為算法初始化參數的設置方法，可以粗略分類作為GMM的混合成份，同時減少候選成份，避免每個數據單獨作為成份，大大減少了程序運行時間。

1.3 GMM理論

高斯混合模型在單高斯密度分布函數基礎上發展而來，因GMM具有單高斯分布無法比擬的先天優勢，可以用GMM描述訓練數據樣本的概率分布，對一些連續型概率分布問題具有很好的適用性，因此可以與HMM聯合使用，克服HMM在解決連續性問題上的弊端，用GMM擬合HMM的發射概率，形成GMM-HMM算法[13]。描述為連續性觀測值的概率分布使用混合高斯函數近似擬合。

一般機器學習參數求解步驟是先求得優化目標函數，然后對函數求導，使函數取到最優值，再令模型參數為此時的對應參數，但是對混合高斯的目標函數應用此法求解困難，不好求偏導。而EM算法也是一種求解最優值的優秀算法，可以使用EM求解GMM問題 [14]：首先，初始化GMM各參數;其次，基于該參數求得估計參數，使估計函數求到最大值，不斷迭代這個過程，直到收斂。具體如下：

2 性能評價標準

2.1 準確率

目前機器學習領域使用的聚類性能評價指標有很多種[15]。本文采用準確率、純度作為聚類實驗工具，分析評價算法聚類性能。準確率公式如下：

在式（12）中，N代表實驗的數據集大小;TP代表本屬同一類別的數據項通過算法聚類仍劃分為同一種簇的數據數目;FN代表不同類別數據項通過算法聚類仍劃分為不同種簇的數據數目;Prec是準確率，代表在本數據集實驗結果中，正確劃分數據數目占到總數據數目的比例，該值越大說明實驗結果越好，算法性能越高。

2.2 純度

purity是另外一種常用的聚類評價指標，主要思想是統計正確聚類的數據數目占數據集的比例[16]。表示為：

其中，[Ω={ω1，ω2，？，ωk}]表示簇集;[ωk]表示第k個簇集;[C={c1，c2，？，cj}]是所有類集，[cj]指第j個類集;N是數據集大小。

Purity指標計算方便，值的范圍為0～1，越大表示聚類錯誤的數據項越少。但是這個指標不能很好地適用退化聚類情況，即如果所有數據項單個成簇，仍然可以得到Purity的值為1。

2.3 OEHS準則

參數生成算法的評價方法采用OEHS準則，利用交叉檢驗似然值作為最終隱狀態確定準則[17-18]。對于隱馬爾科夫模型來說，隱狀態N確定后，通過HMM計算序列隱狀態的似然值，再進行HMM 隱狀態標記。通過解碼數據序列，得到隱狀態數與序列似然值的關系，不同隱狀態會有不同效果，以交叉檢驗似然值的 OEHS標準評價。但是模型會隨著隱狀態數增加而越來越復雜，最穩定合適的HMM隱狀態數OEHS最小時的值。

首先設定一個數值范圍，假設最優值在該范圍內，依次遍歷每個取值，計算每個取值的OEHS值，最后找到最小的OEHS值即為最優值。

3 KGO算法參數設定

傳統觀念認為HMM的隱狀態數目在一定意義上也是一種數據分類結果，而數據分布是由若干種單高斯分布混合而成的，每一個高斯分布對應一個類別，因此可以用隱狀態數目作為混合高斯的成份數，兩者之間是一對一、相互轉化并保持一致性的。但是如此粗略劃分對認識問題本質進而解決問題都不是好方法。

傳統做法是使用K-means作為確定隱狀態數的方法[19]，該方法有嚴重弊端：其一，需要大量遍歷計算才能找到最優值，浪費了大量時間，效率很低;其二，需要事前指定取K值，過于主觀隨機，沒有尊重數據本身的特點[20]。本文提出的算法可以解決該問題：第一，具有自適應性的算法，實現了根據數據特點設定隱狀態數;第二，同時計算得出樣本數據混合高斯的成份數;第三，不用事先指定隱狀態數目，一次遍歷數據，減少運行計算時間，大大提高了效率。

為了得到更好的預測結果，且更好地符合客觀事實，分別對隱狀態數目和單一隱狀態對應數據混合高斯成份進行學習，結合多種算法，提出一種具有自主學習能力且對數據分布形狀友好的算法：KGO算法。流程如圖1所示。

KGO具體算法：

（1）以K-means聚類算法得到K個數據簇。

（2）計算K個數據簇的均值、協方差，分別作為初始K個GMM的參數：mu、cov。

（3）通過mu、cov計算GMM成份間的距離，得矩陣M。

（4）遍歷M矩陣，得到間距最小的兩個GMM成份，合并兩個數據簇。

（5）重新計算本成份的mu、cov，同時更新M矩陣。

（6）以本次合并GMM成份和上次合并GMM成份所得到的M矩陣最小值間差值最大者作為最優候選GMM0。標榜合并已經到達最優，各個GMM成份間距離最大。

（7）以OEHS為準則，選取不同GMM-HMM的隱狀態數，同時以GMM0為初始混合高斯成份。尋找最優隱狀態數目N和每個隱狀態對應的GMM。

4 實驗結果

本文實驗數據由兩部分構成：一部分選取UCI數據挖掘數據庫中的標準數據集4k2_far和Iris[21]，另外一部分來自隨機生成的不同維度數據集。各數據集詳細情況如表1所示，實驗仿真硬件環境：Intel 2.6GHz，內存8GB;操作系統：Microsoft Windows 10。

5 結語

本文同時利用K-means和聚類思想，對數據集4k2-far、Iris、5、3、2進行聚類測試，利用準確率和純度作為評價標準，通過對不同情況數據集的仿真驗證，可以得到清晰的性能對比，本文聚類算法可以不指定聚類個數，自適應數據分布情況，自動聚類出數據簇?；诖诵滤惴ǖ难芯拷Y果，進一步應用于混合高斯—隱馬爾科夫模型，鑒于混合高斯-隱馬爾科夫模型適用性能比較依賴參數初始化，對初始化要求較高，為了更好地適應數據分布，該模型可以根據數據情況，初始化混合高斯—隱馬爾科夫模型的隱狀態數目以及每個隱狀態下混合高斯成份的參數。通過對股票數據的驗證測試，本文提出的聚類算法可以很好地在不知數據分布情況時自動適應學習數據分布，設定混合高斯-隱馬爾科夫模型的隱狀態數目以及每個隱狀態下混合高斯成份的參數，同時通過減少尋優時遍歷數據的次數，大大提高運行效率，對模型效果有重要影響，同時對進一步優化模型性能有重要指導意義。

參考文獻：

[1] 文芳. 股票量化策略：科學愛好者的游戲[J]. 新財富，2016（8）：60-64.

[2] 許博， 陳鳴， 魏祥麟. 基于隱馬爾科夫模型的P2P流識別技術[J]. 通信學報，2012，33（6）：55-63.

[3] 陳世文. 基于譜分析與統計機器學習的DDoS攻擊檢測技術研究[D]. 鄭州：解放軍信息工程大學，2013.

[4] 吳漫君. 基于隱馬爾科夫模型的股價走勢預測[D]. 廣州：華南理工大學，2011.

[5] 柳姣姣，禹素萍，吳波，等. 基于隱馬爾科夫模型的時空序列預測方法[J]. 微型機與應用，2016，35（1）：74-76.

[6] 王慎波，張為. 基于塊模型的混合高斯模型運動目標檢測方法[J]. 信息技術，2016（6）：151-156.

[7] 王慧勇. 基于神經網絡的多方言口音漢語語音識別系統研究[D]. 深圳：中國科學院深圳先進技術研究院，2014.

[8] 杜世平.? 隱馬爾可夫模型的原理及其應用[D]. 成都：四川大學， 2004.

[9] BAUM L E， PETRIE T， SOULES G， et al. A maximization technique occurring in the statistical analysis of probabilistic functions of Markov chains[J]. Annals of Mathematical Statistics，1970，41（1）：164-171.

[10] BAUM L E，PETRIE T. Statistical inference for probabilistic functions of finite state Markov chains[J].? Annals of Mathematical Statistics， 1966， 37（6）：1554-1563.

[11] 張素潔， 趙懷慈. 最優聚類個數和初始聚類中心點選取算法研究[J]. 計算機應用研究，2017，34（6）：1617-1620.

[12] HU L， ZANIBBI R. HMM-based recognition of online handwritten mathematical symbols using segmental K-means initialization and a modified pen-up/down feature[C]. Asian Conference on Computer Vision，2011：457-462.

[13] ZIMMERMANN M，GHAZI M M，EKENEL H K，et al. Visual speech recognition using PCA networks and LSTMs in a tandem GMM-HMM system[C]. Asian Conference on Computer Vision， 2016：264-276.

[14] VERBEEK J J， VLASSIS N， KR？SE B. Efficient greedy learning of Gaussian mixture models[J]. Neural Computation， 2014，15（2）：469-485.

[15] 馮柳偉，常冬霞，鄧勇，等. 最近最遠得分的聚類性能評價指標[J]. 智能系統學報，2017，12（1）：67-74.

[16] 譚穎. 文本挖掘中的聚類算法研究[D]. 長春：吉林大學， 2009.

[17] CELEUX G，DURAND J B. Selecting hidden Markov model state number with cross-validated likelihood[J]. Computational Statistics，2008，23（4）：541-564.

[18] 段江嬌. 基于模型的時間序列數據挖掘[D]. 上海：復旦大學， 2008.

[19] 吳靜，吳曉燕，滕江川，等. 基于連續隱馬爾可夫模型的仿真模型驗證[J]. 兵工學報，2012，32（3）：367-372.

[20] 馮波，郝文寧，陳剛，等. K-means算法初始聚類中心選擇的優化[J]. 計算機工程與應用，2013，49（14）：182-185.

[21] 謝慶華，張寧蓉，宋以勝，等. 聚類數據挖掘可視化模型方法與技術[J]. 解放軍理工大學學報：自然科學版， 2015（1）：7-15.

[22] 賈瑞玉，宋建林. 基于聚類中心優化的k-means最佳聚類數確定方法[J]. 微電子學與計算機，2016，33（5）：62-66.

（責任編輯：何 麗）