维特比算法改进在python实现例子

维特比算法改进即yon实现简介用以下例子进行说明1.题目2.已知情况3.计算过程代码实现
简介
本文实现了维特比算法中选择前k个最优的路径算法。通常的维特比算法会算出到每一个节点的最优路径，计算复杂度比较高，本文选择前k个节点的最优路径进行计算到该节点的最优路径，计算次全局最优解。
优点为：相比于一般的维特比算法，可以降低算法的运算复杂度与空间复杂度。使用者可以自行调节k值，来达到自己所要求的解的最优状况。
用以下例子进行说明
1.题目
假设有这样一个问题，远在另一个城市上大学的小明每天通过邮件向你汇报他今天做的事情是什么，这些事情可能是这四项之一：打球、访友、听歌、读书。那么在这种场景下，如何推测小明所在城市的天气情况。假设小明活动有如下规律：在晴天更可能打球，在阴天更可能访友，在雨天更可能的读书，在观测概率矩阵中显示为概率值大小。已知小明这三天的活动分别为：打球，听歌，读书。求小明所在城市这三天的天气状况。
2.已知情况
隐含的天气状况={晴天，多云，雨天}
可观察的活动={打球，访友，听歌，读书}
起始的天气状况的概率分布={0.63，0.17，0.20}
天气状况的转移概率分布为：
竖向—>横向
晴天
多云
雨天
晴天
0.5
0.375
0.125
多云
0.25
0.125
0.625
雨天
0.25
0.375
0.375
在不同天气下，小明不种活动的概率矩阵为：
天气
打球
访友
听歌
读书
晴天
0.6
0.2
0.15
0.05
多云
0.25
0.25
0.25
0.25
雨天
0.05
0.10
0.35
0.5
3.计算过程
(1)计算第一天的概率
P1(晴天)=P(打球|晴天)*P(晴天|初始)=0.6*0.63=0.378
P1(多云)=P(打球|多云)*P(多云|初始)=0.25*0.17=0.045
P1(雨天)=P(打球|雨天)*P(雨天|初始)=0.05*0.20=0.010
则P1(晴天)>P1(多云)>P1(雨天)=0.378>0.045>0.010
与一般的维特比算法不同，我们在该阶段对数据进行删减，选择概率前k个状态(这里选择2)作为下一个状态转移的开始状态。即考虑下一个状态时，只考虑前一天为晴天和多云的状况。
(2)计算第二天的概率
P21(晴天)=P(听歌|晴天)*P(晴天|晴天)*P(晴天)=0.15*0.5*0.378=0.02835
P22(晴天)=P(听歌|晴天)*P(晴天|多云)*P(多云)=0.15*0.25*0.045=0.00169
则P2(晴天)=max{P21(晴天),P22(晴天)}=0.02835
P21(多云)=P(听歌|多云)*P(多云|晴天)*P(晴天)=0.25*0.375*0.378=0.03543
P22(多云)=P(听歌|多云)*P(多云|多云)*P(多云)=0.25*0.125*0.045=0.00141
则P2(多云)=max{P21(多云),P22(多云)}=0.03543
P21(雨天)=P(听歌|雨天)*P(雨天|晴天)*P(晴天)=0.35*0.125*0.378=0.01654
P22(雨天)=P(听歌|雨天)*P(雨天|多云)*P(多云)=0.35*0.625*0.045=0.00984
则P2(雨天)=max{P21(雨天),P22(雨天)}=0.01654
则P2(多云)>P2(晴天)>P2(雨天)=0.03543>0.02835>0.01654
我们继续选择前k(2)个状态，即多云，晴天作为下一天的起始转移状态。
(3)计算第三天的概率
P31(晴天)=P(读书|晴天)*P(晴天|晴天)*P(晴天)=0.05*0.5*0.02835=0.000708
P32(晴天)=P(读书|晴天)*P(晴天|多云)*P(多云)=0.05*0.25*0.03543=0.004428
则P3(晴天)=max{P31(晴天),P32(晴天)}=0.004428
P31(多云)=P(读书|多云)*P(多云|晴天)*P(晴天)=0.25*0.375*0.02835=0.002658
P32(多云)=P(读书|多云)*P(多云|多云)*P(多云)=0.25*0.125*0.03543=0.001107
则P3(多云)=max{P31(多云),P32(多云)}=0.002658
P31(雨天)=P(读书|雨天)*P(雨天|晴天)*P(晴天)=0.5*0.125*0.02835=0.001772
P32(雨天)=P(读书|雨天)*P(雨天|多云)*P(多云)=0.5*0.625*0.03543=0.011072
则P3(雨天)=max{P31(雨天),P32(雨天)}=0.011072
则P3(雨天)>P3(晴天)>P3(多云)=0.011072>0.004428>0.002658
综上所述，最后的判断小明所在城市这三天天气为：晴天—>多云—>雨天
代码实现
imortnumyasn
defviterbi(ainsition_robabity,emission_robabity,i,obs_seq,k):
#转换为矩阵进行运算
ainsition_robabity=n.array(ainsition_robabity)
emission_robabity=n.array(emission_robabity)
i=n.array(i)
#最后返回一个Row*Col的矩阵结果，第1行表示影藏状态，第2行表示概率
Row=2
Col=len(obs_seq)
#定义要返回的矩阵
f=n.zeros((Row,Col))
#定义基于前一状态k个最优计算该状态的概率
st=n.zeros(n.array(ainsition_robabity).shae[0])
#定义该状态的最优前k概率及位置，第一行为位置，第二行为概率
tm=n.zeros((2,k))
#定义选择k个最优的转移矩阵
new_ainsition_robabity=n.zeros((k,ainsition_robabity.shae[1]))
#初始状态
st=i*emission_robabity[:,obs_seq[0]]
#将初始状态下前k个最优按概率从大到小排序
tm[0,:]=st.argsort()[::-1][0:k]
foriinrange(0,k):
tm[1,i]=st[int(tm[0,i])]
f[:,0]=tm[:,0]fortinrange(1,Col):
st=[]
#重新设置该状态下的new_ainsition_robabity
foriinrange(k):
new_ainsition_robabity[i,:]=ainsition_robabity[int(tm[0,i]),:]#由于ainsition_robabity中元素为浮点型，
#需要转换为整型表示位置。
#计算在前k个转态下，不同状态的概率
forninrange(ainsition_robabity.shae[1]):
st_x=tm[1,:]*new_ainsition_robabity[:,n]
#获取最大概率
st.aend(n.max(st_x))
st=n.array(st)*emission_robabity[:,obs_seq[t]]
#将前k个最优按概率从大到小排序
tm[0,:]=n.array(st).argsort()[::-1][0:k]
foriinrange(0,k):
tm[1,i]=st[int(tm[0,i])]
f[:,t]=tm[:,0]
turnf
if__name__=='__main__':
#隐藏状态
invisible=['Sunny','Cloud','Rainy']
#初始状态
i=[0.63,0.17,0.20]
#转移矩阵
ainsion_robity=[[0.5,0.375,0.125],[0.25,0.125,0.625],[0.25,0.375,0.375]]
#发射矩阵
emission_robity=[[0.6,0.2,0.15,0.05],[0.25,0.25,0.25,0.25],[0.05,0.10,0.35,0.5]]
#最后显示状态
obs_seq=[0,2,3]
#设置k值
k=3
#最后返回一个Row*Col的矩阵结果
F=viterbi(ainsion_robity,emission_robity,i,obs_seq,k)
rint(F)
程序输出的结果为：
[[0.1.2.]
[0.3780.03543750.01107422]]
0表示晴天，1表示多云，2表示雨天，与所算的结果一致。
参考自：
htts:blog.csdn.netzhangduan8785rticledetails80443650
htts:blog.csdn.netLuzichangrticledetails91365752