基于改進隱馬爾科夫模型的魯棒用戶行為識別

何敏 彭嵐倩 劉宏立 胡久松

摘 要：提出了一種基于改進隱馬爾科夫模型的用戶行為識別方法.采用遺傳算法用于優化隱馬爾科夫模型的初始參數，將混沌算子代替遺傳算法中高斯變異算子，以避免傳統遺傳算法在收斂過程中的停滯和早熟問題，并有效解決傳統隱馬爾科夫模型中Baum-Welch算法對初始參數敏感的問題.此外，采用UCI中ADLs數據對用戶行為進行識別，實驗結果表明該方法具有很高的識別率和可靠性.

關鍵詞：隱馬爾科夫模型；遺傳算法；Baum-Welch算法；用戶行為識別

中圖分類號：TP391 文獻標志碼：A

Abstract：An improved Hidden Markov Models （HMM） was proposed to recognize the user's behavior. In order to improve the learning efficiency of Baum-Welch algorithm in HMM， and to solve the problem of initial sensitivity， the improved GA s used to optimize the initial parameters of HMM， in which the Chaos operator is utilized to avoid the problem of stagnation and premature convergence of the traditional GA in the convergence process. Finally， the experiment results based on ADLs data in UCI show the algorithm's availability and reliability for user's behavior recognition.

Key words：Hidden Markov Models； Genetic algorithm； Baum-Welch algorithm； users behavior recognition

隨著機器學習算法和人工智能的進步，智能家居領域在中國興起了浪潮.利用室內布置的智能家居傳感器，以無線傳感技術采集并記錄用戶在日常生活中的行為數據，因相似數據中隱含了用戶的某種行為模式，通過記錄的數據對用戶生活習慣建模就可以實現用戶行為識別[1-2].用戶行為識別技術在運動識別、健康監測、跌倒監測等多個領域得到了研究和應用[3-7]，如文獻[3]中介紹了一種基于智能手機傳感器的用戶行為識別系統；文獻[4]介紹了使用可穿戴式設備的慣性傳感器來識別人類活動的系統；文獻[5]中將用戶日常行為識別技術應用到用戶健康監測；文獻[6]對記錄的活動序列進行分析，分析結果應用到慣性導航領域；文獻[7]基于智能移動設備對用戶行為記錄的數據實現了用戶行為跟蹤；文獻[8]利用極速學習機ELM分類器對移動用戶行為進行識別，提出一種位置無關的多模型移動用戶行為識別方法；文獻[9]結合L（2，1）范數稀疏特征選擇和超法向量提出了一種新的深度圖像序列行為識別方法，并利用線性分類器Liblinear進行分類；文獻[10]針對目前行為識別通用模型對步行、上樓、下樓等易混淆行為識別準確率較低的情況，提出了一種基于小波分解及決策樹分類器的行為識別通用模型；文獻[11]對近年來提出的基于不同深度學習框架的人體行為識別新進展進行了逐一介紹和總結分析.

用戶行為識別技術的關鍵是找到能精確體現人體行為邏輯順序的關系模型，但可直接觀測到的傳感器狀態與隱藏用戶行為狀態之間不具有一一對應的關系.隱馬爾科夫模型HMM（Hidden Markov Model）具有雙隨機過程的特性[12]，能夠很好地描述兩種狀態的隱含關系；再者，HMM具有完善的數學模型和理論基礎，能很好地分析時序事件，且已在協議異常檢測、手寫識別、股票預測和DNA序列識別、動作識別[12-14]等方面大量應用.

本文采用HMM對用戶日常行為進行建模.HMM模型的矩陣參數辨識是用戶行為識別的重點，傳統的Baum-Welch算法任意選取初始參數來重估，能夠使迭代向著正確的方向發展，且收斂速度快，但是由于Baum-Welch迭代算法是根據梯度下降的方式進行局部優化，致使參數在迭代估計的過程中易陷入局部最優而影響最終值[15-18].為解決上述問題，本文將遺傳算法引入到HMM的Baum-Welch算法的訓練當中，利用遺傳算法全局尋優的優點，有效避免了Baum-Welch算法對初值的敏感.

1 相關理論及算法介紹

1.1 隱馬爾科夫模型HMM

HMM模型包含兩個隨機過程，即觀測狀態和隱藏狀態，并利用參數表示隨機過程的統計特性.HMM描述的是概率統計下的狀態轉移模型，應用馬爾科夫假設對連續時刻之間的相關性建模，依賴于以下兩個獨立條件.

HMM模型需要解決三個問題，即模型原始矩陣參數值設定、可觀測狀態序列概率及最可能出現的隱藏狀態序列[17].

1.2 基于GA的HMM模型優化算法

在HMM訓練過程中，Baum-Welch算法對隨機選定的初始矩陣參數會產生較大的差異，使結果陷入局部最優，影響建模準確性.由Holland教授提出遺傳算法把自然界中“優勝劣汰，適者生存”的思想引入參數優化算法中，并通過選擇、交叉和變異對個體進行選擇，保留適應度值好的個體，淘汰適應度值差的個體，反復循環，就得到了進化得好的種群[18-19].本文結合遺傳算法全局搜索的優點[20-21]，將經過遺傳算法優化后的結果當作HMM的矩陣初始參數，從而解決Baum-Welch訓練算法對初始參數隨機選擇造成的敏感問題.但使用傳統的遺傳算子，又會容易被進化過程當中產生的“超級個體”困住，無法使其余染色體得到同樣的進化，丟失了優秀的染色體，使得進化停滯.針對這一問題，本文對最易產生超級個體的變異算子進行改進，采用混沌算子進行變異操作，以普遍提高進化結果的質量.算法詳細步驟如下：

1）染色體編碼

為保證遺傳算法在產生新個體的同時能滿足這一條件，需要對每一代新個體的參數進行歸一化處理，把HMM三個矩陣的各個參數作為染色體的各個基因，圖1給出了兩個隱藏含狀態時的編碼示意圖.

2）適應度函數

適應度函數的選擇是評選個體的重要參數，由于求解的問題不同，表達式也會有不同，聯系HMM的學習算法特性，對于給定的觀測狀態序列，找到使條件概率P（O|L）最大的HMM參數，基于此特性，把log（P（O|L））作為適應度函數[15]，從而保證結果的最優化.

3）選擇算子

選擇操作通過對適應度函數的評估，使適應度好、生命力強的個體遺傳到下一代，選擇算子（通常為基于適應度的函數）是對整個種群執行優勝劣汰的操作，是為了避免有用遺傳信息在群體進化過程中被遺失，提高全局收斂性和計算效率.本文采用輪盤賭法選擇算子，挑選出適應度高的個體.

4）交叉算子

在自然界中，兩個染色體通過交換彼此之間的信息，從而完成種群繁衍更新，提升算法的全局搜索能力.傳統的一點交叉，會丟失許多優秀基因，致使個體多樣性減少.由于存在上述問題，本文選用算術交叉算子，算術交叉是指兩個染色體的基因通過選擇系數進行組合，從而產生新后代，算術交叉過程如下：

5）改進變異算子

變異有助于新個體的產生.普通的變異一般采用基于高斯分布的隨機數字進化，由于高斯函數的分布通常有長而扁平的尾巴，遠離中心軸距離較遠的個體變異概率較低，相較之下混沌算子的變異概率在橫坐標0附近對應的縱坐標的概率是最高，具備了高斯分布的特性，且在遠離中心點的地方也有較高的概率，產生的后代跟父代差異更大，基于上述考慮，本文采用文獻[18]中提到的混沌映射算子用于變異操作，得到映射模型：

2 基于改進HMM模型的用戶行為識別

由于人體行為產生的信號時序性較強，且隱馬爾科夫模型的輸入數據通常是一維數據.因此，在用于用戶行為識別時，將門磁等傳感器采集的數據通過預處理轉換為一維向量進行訓練.圖2中列出了傳感器和用戶行為關系的HMM模型.

本文采用前述的基于改進HMM模型方法對用戶日常行為識別，具體流程圖如圖3所示.

首先對訓練數據進行預處理，將訓練數據集中的時刻統一劃分為26個時段，使數據集構成的數據長度一致，對數據存儲提供了方便.預處理之后將訓練數據作為觀測數據，在HMM訓練過程中，把經過遺傳算法優化后的結果當作HMM的矩陣初始參數，引入Baum-Welch算法中學習，得到重估后的概率矩陣參數，基于概率矩陣參數構建模型庫.將待識別的測試數據采用前向算法，計算HMM模型庫中log（P（O|L））的值，從各個HMM對應的前向概率對數值中選取最大的值所對應的HMM模型作為該測試數據對應的模型.利用前向概率找到了合適的模型，最后用Viterbi算法解碼，動態尋找最佳路徑，得到觀測數據對應的隱狀態，即用戶行為.

3 實驗結果及分析

為驗證上述方法的有效性，本文采用UCI數據集中ADLs[22]（Activities of Daily Living）數據作為對象進行實驗.數據集中記錄了兩組數據，分別是12種傳感器和10種用戶生活習慣，通過在門、沙發、床、櫥柜、冰箱和廁所沖水箱等地方放置相應的傳感器采集數據，數據集總共記錄了35天的生活數據，按比例5∶2分為訓練數據和測試數據.并且對結合改進GA的BW算法、結合傳統GA的BW算法[23]、經典BW算法[24]三者的標準方差進行比較，并計算識別率.從圖4仿真結果圖中可以看出結合改進GA的BW算法產生的結果明顯優于結合傳統GA的BW算法.

為了比較三種算法在訓練隱馬爾科夫模型參數的收斂性，采用標準誤差進行結果對比：

抽取一個樣本觀察在BW迭代過程中轉移概率矩陣得到的標準誤差如圖5所示.可以看出三種算法中，經典BW算法[24]的標準誤差接近0.24左右才收斂，傳統GA結合BW算法[23]的標準誤差接近0.2左右收斂，改進GA經過BW迭代后的標準誤差接近0.14時收斂，改進GA得到的初始值經過BW迭代后提高了全局搜索能力，避免了對初始值敏感這一問題.

圖6為改進后的遺傳算法跟傳統的遺傳算法[23]的適應度值的比較，（a）圖中給出的是改進GA的最佳適應度和平均適應度值，從圖中可以看出兩者之間趨向一致且最佳適應度值跟平均適應度值差距不大，染色體之間的適應度值均比較高，沒有進化的超級個體，實現了全局優化，而（b）圖中在第6代最佳適應度值出現了突增，且后面代數平均適應度值增長緩慢，說明該算法產生了超級個體，適應度值遠遠超過其他染色體，循環一直不能跳出該值，陷入了局部優化.綜合以上分析，改進的GA實現了全局優化，更加準確地訓練出HMM模型，提高了系統的質量，從而驗證了改進的遺傳算法的穩定性和有效性.

4 結 論

針對傳統HMM模型中Baum-Welch算法易受初始參數影響的問題，本文提出了一種基于改進HMM的魯棒用戶行為識別方法，將A，B，π三個矩陣的各個參數作為染色體的基因，對其進行全局搜索優化.為保證模型的穩定性，本文利用改進的遺傳算法，將混沌變異算子代替傳統高斯算子應用到遺傳算法中，用改進后的算法得到的結果作為BW算法的初始參數，隨后建立HMM模型庫，為用戶行為匹配提供了途徑，之后用Viterbi算法解出對應的用戶行為，最后用UCI數據集中的ADLs數據進行實驗，對經典BW、傳統GA+BW和改進GA+BW三種算法在迭代過程中矩陣參數的標準方差進行比較，并對算法的最佳適應度和平均適應度值進行對比，結果表明本文提出的方法在識別準確率、標準誤差上都要優于另外兩種算法，在適應度上也能看出彌補了傳統遺傳算法的缺點，從而驗證了算法的有效性和可靠性.

參考文獻

[1] LI M， LIN H. Design and implementation of smart home control systems based on wireless sensor networks and power line communications[J]. IEEE Transactions on Industrial Electronics， 2015，62（7）：4430-4442.

[2] ORDEZ F J， ENGLEBIENNE G， TOLEDO P D， et al. In-home activity recognition： Bayesian inference for hidden Markov models[J]. IEEE Pervasive Computing， 2014，13（3）：67-75.

[3] HOSEINI-TABATABAEI S A， GLUHAK A， TAFAZOLLI R. A survey on smart phone-based systems for opportunistic user context recognition[J]. ACM Computing Surveys（CSUR）， 2013，45（3）：1-33.

[4] BULLING A， BLANKE U， SCHIELE B. A tutorial on human activity recognition using body-worn inertial sensors[J]. ACM Computing Surveys（CSUR）， 2014，46（3）：57-76.

[5] CHIANG J H， YANG P C， TU H. Pattern analysis in daily physical activity data for personal health management[J]. Journal Pervasive and Mobile Computing， 2014，13（4）：13-25.

[6] ZHOU B， LI Q， MAO Q， et al. Activity sequence-based indoor pedestrian localization using smart phones[J]. IEEE Transactions on Human-Machine Systems， 2015，45（5）：562-574.

[7] MARTIN H， BERNARDOS A M， IGLESIAS J， et al. Activity logging using lightweight classification techniques in mobile devices[J]. Personal and Ubiquitous Computing， 2013，17（4）：675-695.

[8] 王忠民，韓帥，宋輝.一種位置無關的多模型移動用戶行為識別方法[J].計算機應用研究，2017，34（4）：1060-1062，1066.

WANG Z M， HAN S， SONG H. A location-independent multi-model mobile user behavior recognition method[J]. Application Research of Computers，2017，34（4）：1060-1062，1066.（In Chinese）

[9] 宋相法，張延鋒，鄭逢斌.基于L（2，1）范數稀疏特征選擇和超法向量的深度圖像序列行為識別[J].計算機科學，2017，44（2）：306-308，323.

SONG X F， ZHANG Y F， ZHENG F B. Activity recognition from depth image sequences based on L（2，1） norm sparse feature selection and super normal vector[J]. Computer Science， 2017，44（2）：306-308，323.（In Chinese）

[10]賀炎，王斌，王忠民.小波分解在移動用戶行為識別中的應用[J].北京郵電大學學報，2016，39（4）：67-70.

HE Y， WANG B， WANG Z M. Application of wavelet decomposition in mobile user behavior recognition[J]. Journal of Beijing University of Posts and Telecom， 2016，39（4）：67-70.（In Chinese）

[11]朱煜，趙江坤，王逸寧，等.基于深度學習的人體行為識別算法綜述[J].自動化學報，2016，42（6）：848-857.

ZHU Y， ZHAO J K， WANG Y N， et al. Summarization of human behavior recognition algorithm based on deep learning[J]. Journal of Automation， 2016，42（6）：848-857.（In Chinese）

[12]王昌海，張建忠，徐敬東，等.基于HMM的動作識別結果可信度計算方法[J].通信學報，2016，37（5）：143-151.

WANG C H， ZHANG J Z， XU J D， et al. Identifying the confidence level of activity recognition via HMM[J]. Journal on Communications， 2016，37（5）：143-151.（In Chinese）

[13]HASSAN M R， NATH B. Stock market forecasting using Hidden Markov Model： a new approach[C]//International Conference on Intelligent Systems Design and Applications. 2005：192-196.

[14]溫加睿，劉麗娜，芮玲，等.基于自學習特征與HMM的人體動作識別[J].系統仿真學報，2015，27（8）：1782-1789，1795.

WEN J R， LIU L N， RUI L， et al. Human action recognition based on self-learning feature and HMM[J]. Journal of System Simulation， 2015，27（8）：1782-1789，1795.（In Chinese）

[15]ALEMDAR H， KASTEREN T L M V， NIESSEN M E， et al. A unified model for human behavior modeling using a hierarchy with a variable number of states[J]. International Conference on Pattern Recognition，2014，29（2）：3804-3809.

[16]PATTERSON D J， FOX D， KAUTZ H， et al. Fine-grained activity recognition by aggregating abstract object usage[C]//IEEE International symposium on Wearable Computers. 2005：44-51.

[17]CRANDALL A S， COOK D J. Using a Hidden Markov Model for resident identification[C]//Sixth International Conference on Intelligent Environments. IEEE Xplore， 2010：74-79.

[18]YANG L J， CHEN T L. Application of chaos in genetic algorithms[J]. Journal of Communications in Theoretical Physics， 2002，38（8）：168-172.

[19]HALALAI R， LEMNARU C， POTOLEA R. Distributed community detection in social networks with genetic algorithms [C]// IEEE International Conference on Intelligent Computer Communication and Processing. 2010：35-41.

[20]LIAO L， FOX D， KAUTZ H. Location-based activity recognition using relational Markov networks [C]// International Joint Conference on Artificial Intelligence. 2005：773-778.

[21]劉振軍，楊迪雄.面向工程全局優化的混沌優化算法研究進展[J].計算力學學報，2016，33（3）：269-286.

LIU Z J， YANG D X. Research advances of chaos optimization algorithms for engineering global optimization[J]. Journal of Computational Mechanics， 2016，33（3）：269-286.（In Chinese）

[22]ORDONEZ F J， De TOLEDO P， SANCHIS A. Activity recognition using hybrid generative/discriminative models on home environments using binary sensors [DB/OL]. Sensors. https：//archive.ics.uci.edu/ml/datasets/Activities+of+Daily+Living+（ADLs）+Recognition+Using+Binary+Sensors， 2013-13，5460-5477/2017-5.

[23]吳剛，邱煜晶，王國仁，等.基于隱爾可夫模型和遺傳算法的地圖匹配算法[J].東北大學學報（自然科學版），2017，38（4）：472-475.

WU G， QIU Y J， WANG G R， et al. Map matching algorithm based on Hidden Markov model and Gennetic algorithm[J]. Journal of Northeastern University（Natural Science）， 2017，38（4）：472-475.（In Chinese）

[24]BILMES J A. A gentle tutorial of the EM algorithm and its application to parameter estimation for Gaussian Mixture and Hidden Markov models[M]. U.C. Berkeley： International Computer Science Institute， 1998：120-126.