4.5.4.1 消息故障分析算法
应用隐马尔可夫模型首先能够判断给定的观察序列σ的消息执行序列中是否存在异常的消息，即消息集中没有包含的消息或消息转移矩阵中概率小于ε的消息转移序列，如果存在异常消息就寻找一个与该观察序列最匹配的消息来代替异常消息，然后获得一个与观察序列最匹配的正常消息序列。这里的ε表示一个极小概率值。如果描述规约及历史数据中不包含噪声，那么ε=0；如果描述规约及历史数据中包含噪声，那么设定εi=1/2nzi。这里nzi表示消息转移矩阵MM的第i行元素mpi·中概率不为0的元素个数。
在算法4.3中，max（matrix（·））表示矩阵matrix中满足条件的所有元素中概率值最大的元素。算法4.3按观察序列中从前向后的顺序依次诊断，首先判断观察序列中前一个消息转移到下一个消息在消息转移矩阵的概率是否小于ε，如果小于ε则认为所转移到的消息发生异常；如果消息异常，则找出满足由行为σ（i）.b输出的消息且从消息MS（i-1）出发的转移序列中转移概率最大的消息，用于替换相应的异常消息；如果未找到这样的消息，那么进一步放宽匹配条件，找到从消息MS（i-1）出发的转移序列中转移概率最大的消息用于替换相应的异常消息。最后，当遍历完观察序列中的所有消息后，得到一个最匹配的正确转移序列MS和消息诊断解集合DS_m。时间复杂度中，T表示在消息观察序列σ中行为及其输出消息的个数，n表示行为转移矩阵BM中行为的个数，k表示消息转移矩阵MM中消息的个数。
算法4.3 Corr MS（SHM，σ）
输入：服务模型SH M，观察序列σ。
输出：消息序列MS，消息诊断解集合DS_m。
4.5.4.2 行为故障分析算法
在获得与观察序列相匹配的正确消息序列MS之后，再应用Viterbi算法找出与MS最匹配的行为序列BS，然后再通过比较BS和观察序列σ找出它们之间的差异，并将σ中与BS同一位置但行为与其不同的行为放入行为诊断解集合DS_b中。
在算法4.4中，π（i）表示行为i的初始概率，如果行为i是开始行为，那么π（i）=1，否则π（i）=0；max1≤k≤n（·）表示给定集合·中的最大值；argmax1≤k≤n（·）表示给定集合·中有最大值的元素。算法4.4首先根据给定的正确消息序列MS计算每个行为作为开始行为的概率，再依次计算与消息序列MS中相应位置消息相匹配的行为执行序列的概率，选取具有最大概率值的行为作为与该位置消息相匹配的行为，并将行为序号放入φ中，然后根据整个正确行为序列带有最大概率的最后一个执行行为从后向前推出与MS最匹配的行为序列BM，最后比较BM与给定观察序列σ，如果σ中的第i个行为与BM中的第i个行为不同，那么认为σ中的第i个行为是故障行为，并将其放入行为诊断解集合DS_b中。时间复杂度中，T表示在消息观察序列σ中行为及其输出消息的个数，n表示行为转移矩阵BM中行为的个数。
算法4.4 CorrBS（SHM，σ，MS）
输入：服务模型SHM，观察序列σ，正确消息序列MS。(www.xing528.com)
输出：行为诊断解集合DS_b。
通过算法4.3和算法4.4，不仅能够诊断出发生故障的行为以及错误的输出，而且可以根据消息诊断解集合和行为诊断解集合分析出故障发生原因，即数据语义故障或行为逻辑故障。
4.5.4.3 算法有效性证明
定理4.3 给定一个隐马尔可夫服务模型SHM=（B，M，π，BM，MM，OM）和一个待诊断的观察序列σ={o1，o2，…，oT}，可知消息诊断解集合DS_m是σ中所有异常消息集合。
证明：假设所有异常消息转移的概率都远远小于SH M中所有正常转移概率，这里假设每个消息异常转移的概率都小于给定的极小值ε。如果一个消息转移概率mp＜ε，那么mp∈DS_m，并且遍历了σ中的每一个消息转移，那么对于∀mp∈σ∧mp＜ε，mp∈DS_m；如果一个消息转移mp′≥ε，且SH M表示所有正常转移概率，那么mp′是一个正常的消息转移。由此可以证明，消息诊断解集合DS_m是σ中所有异常消息的集合。
定理4.4 给定一个隐马尔可夫服务模型SHM=（B，M，π，BM，MM，OM）和一个待诊断的观察序列σ={o1，o2，…，oT}，可知消息序列MS是一个正确消息序列。
证明：假设mt∈MS∧mt∈DS_m，根据定理4.1可知，mt是一个异常消息。假设mt′是mt在MS中的前一个消息，由于mt是一个异常消息，因此MM（mt′，mt）＜ε。根据算法4.4可知，（mt′，mt）∉MS，假设mt∈MS∧mt∈DS_m不成立。所以，消息序列MS是一个正确消息序列。
定理4.5 给定一个隐马尔可夫服务模型SHM=（B，M，π，BM，MM，OM），一个待诊断的观察序列σ={o1，o2，…，oT}和一个正确消息序列MS，可知DS_b是行为诊断解集合。
证明：假设根据MS应用Viterbi算法求得的BS是一个与MS最匹配的行为序列。根据Viterbi算法可知，BS是通过MS生成的具有最大转移概率的行为序列，BS中的行为转移都包含在正常行为转移当中，即BS⊂BM，所以BS是一个与MS最匹配的正确行为序列。如果σ（i）≠BS（i），那么σ（i）必然发生了异常，不符合正常的行为转移规律。根据算法4.4可知，σ（i）∈DS_b，由此可以得出DS_b是行为诊断解集合。
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
