一種GMMHMM隱狀態(tài)與高斯混合成份初始化算法

張軍超 蔣強榮

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

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

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年開始保持超高年回報率被業(yè)界譽為最高效的對沖基金，通過獨特的數(shù)學模型，捕捉市場機會進行量化投資，而隱馬爾科夫模型是主要工具之一[1]?？梢钥吹?，HMM在各個領域都有應用，具有廣泛影響。常用的HMM模型可以根據(jù)觀測狀態(tài)分為兩個類別：連續(xù)型和離散型。例如，連續(xù)型的GaussianHMM、GMMHMM，離散觀測狀態(tài)的有MultinomialHMM。

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

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

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

1 關鍵算法理論

1.1 HMM算法

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

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

1.2 K-means理論

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

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

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

K-means基本步驟：

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

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

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

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

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

1.3 GMM理論

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

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

2 性能評價標準

2.1 準確率

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

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

2.2 純度

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

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

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

2.3 OEHS準則

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

首先設定一個數(shù)值范圍，假設最優(yōu)值在該范圍內(nèi)，依次遍歷每個取值，計算每個取值的OEHS值，最后找到最小的OEHS值即為最優(yōu)值。

3 KGO算法參數(shù)設定

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

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

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

KGO具體算法：

（1）以K-means聚類算法得到K個數(shù)據(jù)簇。

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

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

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

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

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

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

4 實驗結果

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

5 結語

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

參考文獻：

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

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

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

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

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

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

[7] 王慧勇. 基于神經(jīng)網(wǎng)絡的多方言口音漢語語音識別系統(tǒng)研究[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] 張素潔， 趙懷慈. 最優(yōu)聚類個數(shù)和初始聚類中心點選取算法研究[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]. 智能系統(tǒng)學報，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] 段江嬌. 基于模型的時間序列數(shù)據(jù)挖掘[D]. 上海：復旦大學， 2008.

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

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

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

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

（責任編輯：何 麗）