張軍超 蔣強(qiáng)榮

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

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

DOI：10. 11907/rjdk. 181494

中圖分類號：TP312文獻(xiàn)標(biāo)識碼：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世紀(jì)60年代，鮑姆提出了隱馬爾科夫模型（Hidden Markov Model，HMM），在語音識別領(lǐng)域使用，被廣大科研人員熟知。文藝復(fù)興科技公司是國際著名投資機(jī)構(gòu)，因從1989年開始保持超高年回報(bào)率被業(yè)界譽(yù)為最高效的對沖基金，通過獨(dú)特的數(shù)學(xué)模型，捕捉市場機(jī)會進(jìn)行量化投資，而隱馬爾科夫模型是主要工具之一[1]?？梢钥吹剑琀MM在各個(gè)領(lǐng)域都有應(yīng)用，具有廣泛影響。常用的HMM模型可以根據(jù)觀測狀態(tài)分為兩個(gè)類別：連續(xù)型和離散型。例如，連續(xù)型的GaussianHMM、GMMHMM，離散觀測狀態(tài)的有MultinomialHMM。

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

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

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

1 關(guān)鍵算法理論

1.1 HMM算法

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

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

1.2 K-means理論

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

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

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

K-means基本步驟：

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

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

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

（4）重復(fù)步驟（2）、步驟（3）。當(dāng)每個(gè)簇的中心不再變化時(shí)結(jié)束算法。

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

1.3 GMM理論

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

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

2 性能評價(jià)標(biāo)準(zhǔn)

2.1 準(zhǔn)確率

目前機(jī)器學(xué)習(xí)領(lǐng)域使用的聚類性能評價(jià)指標(biāo)有很多種[15]。本文采用準(zhǔn)確率、純度作為聚類實(shí)驗(yàn)工具，分析評價(jià)算法聚類性能。準(zhǔn)確率公式如下：

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

2.2 純度

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

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

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

2.3 OEHS準(zhǔn)則

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

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

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

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

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

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

KGO具體算法：

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

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

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

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

（5）重新計(jì)算本成份的mu、cov，同時(shí)更新M矩陣。

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

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

4 實(shí)驗(yàn)結(jié)果

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

5 結(jié)語

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

參考文獻(xiàn)：

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

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

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

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

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

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

[7] 王慧勇. 基于神經(jīng)網(wǎng)絡(luò)的多方言口音漢語語音識別系統(tǒng)研究[D]. 深圳：中國科學(xué)院深圳先進(jìn)技術(shù)研究院，2014.

[8] 杜世平.? 隱馬爾可夫模型的原理及其應(yīng)用[D]. 成都：四川大學(xué)， 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)聚類個(gè)數(shù)和初始聚類中心點(diǎn)選取算法研究[J]. 計(jì)算機(jī)應(yīng)用研究，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] 馮柳偉，常冬霞，鄧勇，等. 最近最遠(yuǎn)得分的聚類性能評價(jià)指標(biāo)[J]. 智能系統(tǒng)學(xué)報(bào)，2017，12（1）：67-74.

[16] 譚穎. 文本挖掘中的聚類算法研究[D]. 長春：吉林大學(xué)， 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í)間序列數(shù)據(jù)挖掘[D]. 上海：復(fù)旦大學(xué)， 2008.

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

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

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

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

（責(zé)任編輯：何 麗）