隱馬爾可夫模型在信息工程質(zhì)量監(jiān)理中的應(yīng)用*

高 麗，劉宏志

（北京工商大學(xué) 計(jì)算機(jī)與信息工程學(xué)院，北京 100048）

目前，用于信息工程監(jiān)理[1]質(zhì)量控制的方法主要有基于模糊理論、基于因素神經(jīng)網(wǎng)絡(luò)、基于灰色系統(tǒng)理論[2]和基于模糊因素神經(jīng)網(wǎng)絡(luò)等；軟件質(zhì)量的度量模型主要有Boehm模型、McCall模型和ISO/IEC9126模型[3]等。這些方法和模型都能較好地適應(yīng)于靜態(tài)問(wèn)題的解決，但監(jiān)理人員只有針對(duì)信息工程監(jiān)理各個(gè)階段實(shí)施全過(guò)程的動(dòng)態(tài)監(jiān)理，才能使影響信息系統(tǒng)質(zhì)量的要素在開(kāi)發(fā)過(guò)程中處于受控狀態(tài)。隱馬爾可夫模型HMM(Hidden Markov Model)是一種雙重隨機(jī)過(guò)程，能夠解決隨機(jī)不確定問(wèn)題，在很多方面已有廣泛應(yīng)用[4]，具有理論研究透徹、算法成熟、效率高、效果好、易于訓(xùn)練等特點(diǎn)，作為一種有效的概率工具，已成為信息抽取領(lǐng)域中一個(gè)新的研究方向[5]。本文通過(guò)對(duì)信息工程質(zhì)量監(jiān)理過(guò)程特點(diǎn)的分析，將隱馬爾可夫模型映射到質(zhì)量監(jiān)理中，利用前向算法估計(jì)出在該模型下觀測(cè)事件序列發(fā)生的概率，從而在一定程度上有助于對(duì)軟件質(zhì)量進(jìn)行定量控制。

1 模型的建立

1.1 特征提取

隱馬爾可夫模型由兩個(gè)部分組成[6]：一個(gè)是隱蔽的（不可觀測(cè)的）、具有有限狀態(tài)的馬爾可夫鏈[7]，另一個(gè)是與馬爾可夫鏈的每一狀態(tài)相關(guān)聯(lián)的觀察事件的隨機(jī)過(guò)程（可觀測(cè)的）。

將隱馬爾可夫模型映射到信息工程監(jiān)理質(zhì)量評(píng)估模型上，即一個(gè)軟件的質(zhì)量狀態(tài)是無(wú)法直接觀察到的，但是可以通過(guò)分析與這個(gè)軟件相關(guān)的質(zhì)量度量要素，估算該軟件的質(zhì)量狀態(tài)，從而進(jìn)一步得到其量化的評(píng)判值。信息化工程監(jiān)理國(guó)標(biāo)中的信息化工程監(jiān)理規(guī)范技術(shù)參考模型[8]將信息工程質(zhì)量監(jiān)理分為工程招標(biāo)、工程設(shè)計(jì)、工程實(shí)施和工程驗(yàn)收四個(gè)階段。各個(gè)階段的軟件質(zhì)量狀態(tài)構(gòu)成一個(gè)馬爾可夫鏈，度量要素序列是一個(gè)隨機(jī)過(guò)程，每一個(gè)度量要素會(huì)對(duì)軟件的質(zhì)量狀態(tài)的轉(zhuǎn)移帶來(lái)一定影響，這樣，度量要素序列和軟件的質(zhì)量狀態(tài)之間就構(gòu)成了一個(gè)隱馬爾可夫模型。通過(guò)觀察信息工程監(jiān)理全過(guò)程各個(gè)階段的度量要素，每個(gè)階段都可以得到一個(gè)隨機(jī)的度量要素序列，這樣就可以計(jì)算軟件的質(zhì)量狀態(tài)和評(píng)判值。

軟件質(zhì)量目標(biāo)控制按照分層法分解為人、軟件元、開(kāi)發(fā)方法、設(shè)備及材料和工程環(huán)境五個(gè)度量要素，軟件質(zhì)量狀態(tài)依據(jù)各度量要素分為優(yōu)、良、中、差四個(gè)決斷因子，如果再定義出它們之間的概率轉(zhuǎn)換關(guān)系，就會(huì)得到由這兩組狀態(tài)構(gòu)成的隱馬爾可夫模型（如圖1所示）。

圖1 隱馬爾可夫模型

根據(jù)該HMM模型，可以在沒(méi)有直接觀測(cè)軟件質(zhì)量的情況下根據(jù)度量要素的分布來(lái)推測(cè)軟件質(zhì)量的變化情況。

1.2 參數(shù)設(shè)定

一個(gè)HMM可以由五個(gè)元素構(gòu)成，將HMM定義為：λ=(S，V，π，Trans，Obs)[9]。實(shí)際上當(dāng) Trans、Obs確定后也意味著 S、V 已 指定， 所 以 可 簡(jiǎn) 寫(xiě) 為：λ=(π，Trans，Obs)。

首先定義監(jiān)理軟件的質(zhì)量狀態(tài)為 S={A，B，C，D}，也就是將軟件質(zhì)量分為 A、B、C、D四個(gè)等級(jí)。s1=A，表示質(zhì)量狀態(tài)處于優(yōu)；s2=B，表示質(zhì)量狀態(tài)處于良；s3=C，表示質(zhì)量狀態(tài)處于中；s4=D，表示質(zhì)量狀態(tài)處于差。設(shè)在信息工程質(zhì)量監(jiān)理階段t軟件質(zhì)量所處的狀態(tài)為qt，qt∈S，1≤t≤4，已知信息工程質(zhì)量監(jiān)理由四個(gè)階段組成。

如果能較為準(zhǔn)確地計(jì)算軟件質(zhì)量處于何種狀態(tài)，則可以定量分析軟件的質(zhì)量情況。軟件質(zhì)量狀態(tài)之間的轉(zhuǎn)移見(jiàn)圖 2。

圖2 Markov鏈

由圖1可以直觀看出，度量軟件質(zhì)量的要素有5個(gè)，用 V={P，U，M，F(xiàn)，E}表示，ν1=P(People)，表示度量要素人的因素；ν2=U(Units)，表示度量要素軟件元質(zhì)量；ν3=M(Methods)，表示度量要素開(kāi)發(fā)方法；ν4=F(Facilities)，表示度量要素設(shè)備及材料；ν5=E(Environment)，表示度量要素工程環(huán)境。設(shè)質(zhì)量度量要素觀測(cè)序列為O={o1，o2，o3，o4}，其中 ot∈V。

設(shè)軟件質(zhì)量情況在信息工程監(jiān)理開(kāi)始階段狀態(tài)為π，它是一個(gè)向量，表示在信息工程監(jiān)理工程招標(biāo)階段軟件質(zhì)量處于各個(gè)狀態(tài)的概率，π={π1，π2，π3，π4}，πi=P(q1=si)，1≤i≤4。對(duì)于工程招標(biāo)階段，可以根據(jù)信息工程監(jiān)理協(xié)同工作平臺(tái)下的模糊因素神經(jīng)網(wǎng)絡(luò)質(zhì)量評(píng)估方法得到一個(gè)默認(rèn)值，之后的每一階段，通過(guò)Trans和Obs可以計(jì)算出當(dāng)前軟件質(zhì)量處于各種狀態(tài)的概率st=(r1，…，r4)，將此概率作為下一階段的初始狀態(tài)。在t階段，狀態(tài)分布表示為 rt={rt(i)}，1≤i≤4，狀態(tài)的分布概率公式為：rt(i)=P(qt=si|λ)。再引入一個(gè)代價(jià)向量 C[10]，代表軟件在每個(gè)狀態(tài)的質(zhì)量值，則可以將軟件狀態(tài)的定性分析轉(zhuǎn)化為定量分析。

設(shè)Trans為軟件質(zhì)量狀態(tài)轉(zhuǎn)換矩陣，即質(zhì)量狀態(tài)之間轉(zhuǎn)換的概率組成的矩陣，包含4行4列，aij表示在 t階段質(zhì)量狀態(tài)為si，那么到 t+1階段質(zhì)量狀態(tài)為 sj的概率，即 aij=P(qt+1=sj|qt=si)，1≤i，j≤4。

定義Obs為當(dāng)軟件處于某一個(gè)特定質(zhì)量狀態(tài)時(shí)觀測(cè)到某種度量要素的概率矩陣，bj（k）表示在階段 t，軟件質(zhì)量處于 sj狀態(tài)觀測(cè)到度量要素 νk的概率，1≤k≤5，1≤j≤4。

2 基于前向算法的模型應(yīng)用

根據(jù)得到的觀察序列 O={o1，o2，o3，o4}和模型 λ=(π，Trans，Obs)可以計(jì)算出在該模型下觀察事件序列發(fā)生的概率 P(O|λ)。P(O|λ)評(píng)價(jià)了給定模型 λ 與給定觀測(cè)序列匹配的程度。

對(duì)隱馬爾可夫模型而言，狀態(tài)轉(zhuǎn)換序列是隱藏的，一個(gè)觀測(cè)序列可能由任何一種狀態(tài)轉(zhuǎn)換序列產(chǎn)生。因此要計(jì)算一個(gè)觀測(cè)序列的概率值，就必須考慮所有可能的狀態(tài)轉(zhuǎn)換序列。

窮舉搜索的時(shí)間復(fù)雜度是2TNT，前向算法的時(shí)間復(fù)雜度是2N2T，其中T指的是觀察序列長(zhǎng)度，N指的是隱藏狀態(tài)數(shù)目。對(duì)于信息工程監(jiān)理質(zhì)量控制，N=4，T=4，如果利用窮舉搜索算法，復(fù)雜度相對(duì)會(huì)比較大，可以采用前向算法來(lái)降低復(fù)雜度。

定義前向變量[11]：

表示在模型 λ下，t時(shí)刻觀測(cè)事件是ot、狀態(tài)是si的概率。則在t+1時(shí)刻：

則前向算法為：

初始：

遞歸：

終止：

給定這種算法，對(duì)于已知的一個(gè)度量要素觀察序列，可以直接用來(lái)確定在一些隱馬爾可夫模型中哪一個(gè)最好地描述了它，即先用前向算法評(píng)估某一個(gè)給定的λ，然后通過(guò)多次調(diào)整參數(shù)λ來(lái)提高評(píng)估的概率，進(jìn)而通過(guò)實(shí)時(shí)調(diào)整信息工程監(jiān)理中的質(zhì)量的度量要素的比例來(lái)達(dá)到提高軟件質(zhì)量控制的目的。

3 仿真實(shí)驗(yàn)

實(shí)驗(yàn)數(shù)據(jù)來(lái)源于信息工程監(jiān)理協(xié)同工作平臺(tái)（IPSS）下的數(shù)據(jù)庫(kù)。實(shí)驗(yàn)環(huán)境為Eclipse和Java開(kāi)源工具包jahmm-0.6.1。文中使用狀態(tài)數(shù)為N=4，觀測(cè)值數(shù)為M=5的隱馬爾可夫模型進(jìn)行檢驗(yàn)。

在信息工程監(jiān)理中，每個(gè)階段軟件所處的質(zhì)量狀態(tài)與前一階段所處的質(zhì)量狀態(tài)有關(guān)，即前一階段的質(zhì)量狀態(tài)會(huì)影響下一階段質(zhì)量狀態(tài)出現(xiàn)的概率。

初始質(zhì)量狀態(tài)概率分布：π=(0.3，0.3，0.2，0.2)

四個(gè)質(zhì)量狀態(tài)兩兩之間轉(zhuǎn)化的概率如表1所示。

表1 狀態(tài)轉(zhuǎn)移概率矩陣

軟件質(zhì)量處于某個(gè)狀態(tài)時(shí)，度量要素所占的比例有一定的規(guī)律性。度量要素觀測(cè)值概率分布如表2。

下面根據(jù)軟件質(zhì)量初始狀態(tài)、表1和表2的數(shù)據(jù)，估計(jì)狀態(tài)序列 O={P，U，M，F(xiàn)}出現(xiàn)的概率。假設(shè) P為工程招標(biāo)階段觀測(cè)到的主導(dǎo)要素，U為工程設(shè)計(jì)階段觀測(cè)到的主導(dǎo)要素，M為工程實(shí)施階段觀測(cè)到的主導(dǎo)要素，F(xiàn)為工程驗(yàn)收階段觀測(cè)到的主導(dǎo)要素。

在模型 λ下，在 t時(shí)刻觀測(cè)事件是 ot、狀態(tài)是 si的概率如表3所示，每個(gè)階段的四個(gè)概率對(duì)應(yīng)四個(gè)質(zhì)量狀態(tài)。

表2 觀測(cè)值概率矩陣

表3 在模型λ下，在t時(shí)刻觀測(cè)事件是 ot、狀態(tài)是 si的概率

P(O|λ)=0.00077526+0.00067653+0.00025347+0.00010482=0.00181008。則在該模型下?tīng)顟B(tài)序列 O={P，U，M，F(xiàn)}出現(xiàn)的概率為：0.00181008。

本文通過(guò)對(duì)隱馬爾可夫理論的分析，建立了用于質(zhì)量控制的隱馬爾可夫模型，并嘗試基于該模型對(duì)信息工程監(jiān)理進(jìn)行質(zhì)量控制。本文提出的隱馬爾可夫質(zhì)量控制模型只是用于控制信息工程監(jiān)理4個(gè)階段的5個(gè)基本要素，模型稍顯粗糙。如何基于隱馬爾可夫模型或其他擴(kuò)展模型與信息工程監(jiān)理質(zhì)量控制完全的整合，以及如何利用模型進(jìn)行質(zhì)量評(píng)估并對(duì)模型進(jìn)行訓(xùn)練還需要進(jìn)一步的探索研究。

[1]劉宏志，葛迺康.信息化工程監(jiān)理[M].北京：中國(guó)電力出版社，2009.

[2]劉宏志，楊建軍.基于灰色系統(tǒng)理論的軟件工程監(jiān)理研究[J].經(jīng)濟(jì)管理，2007，29(18).

[3]周建.關(guān)于軟件質(zhì)量的定量評(píng)估的研究[D].成都：電子科技大學(xué)，2007.

[4]胡可，張大力.一類(lèi)廣義隱馬爾可夫模型的建模與參數(shù)估計(jì)[J].中國(guó)科學(xué)院研究生院學(xué)報(bào)，2005，22(2)：210-217.

[5]洪流，張巍，肖明軍，等.一種改進(jìn)的基于 HMM的信息抽取模型[J].模式識(shí)別與人工智能，2004，17(3)：347-351.

[6]翟琳琳，陳儀香.隱馬爾可夫模型在智能學(xué)習(xí)系統(tǒng)中的應(yīng)用[J].計(jì)算機(jī)工程與應(yīng)用，2007，43(6)：178-180.

[7]Wojciech Pieczynski.PairwiseMarkovChains[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2003， 25(5)： 634-639.

[8]中國(guó)國(guó)家標(biāo)準(zhǔn)化管理委員會(huì).信息化工程監(jiān)理規(guī)范——第5部分：軟件工程監(jiān)理規(guī)范[S].中華人民共和國(guó)國(guó)家標(biāo)準(zhǔn)，GB/T 19668.5-2007，ICS.35.020，L01.

[9]LEE H K，KIM J H.An HMM-Based Threshold Model Approach for Gesture Recognition[J].IEEE Transactions on Pattern Analysis and Machine Intelligence， 1999， 21(10)：961-973.

[10]董靜.改進(jìn)的HMM網(wǎng)絡(luò)安全風(fēng)險(xiǎn)評(píng)估方法研究[D].武漢：華中科技大學(xué)，2008.

[11]彭子平，張嚴(yán)虎，潘露露.隱馬爾可夫模型原理及其重要應(yīng)用[J].計(jì)算機(jī)科學(xué)，2008，35(4).