HMM算法python实现

基础介绍，后5项为基础5元素

Q = ['q0', 'q1', 'q2', 'q3']              # 状态集合 States，共 N 种状态

V = ['v0', 'v1']                          # 观测集合 Observations，共 M 种观测值

I = [ 'i{}'.format(i) for i in range(5) ] # 某个长度为 T 的状态序列，i_t 属于Q

O = [ 'o{}'.format(i) for i in range(5) ] # 状态序列对应的观测值序列，o_t 属于 V

A = [ a_ij ]                              # 转移概率 Transition Problity, a_ij = P( i_t+1 = q_j | i_t = q_i ) N*N

B = [ bj(o_t) ]                           # 发射概率 Emission Problity，b_ij = P( o_t = v_k |  i_t = q_j ) N*M

Pi = [ P_i ]                              # 初识状态概率 P_i = P( i_1 = q_i )

基础5元素对应初始化

# Q = ['盒1', '盒2', '盒3']

Q = ['盒1', '盒2']

V = [ '红' , '黑' ]

# A = [ [ 0.2  , 0.3 , 0.5 ] ,

#       [ 0    , 0.5 , 0.5 ] ,

#       [ 0.4  , 0.2 , 0.2 ]]

A = [ [ 0.5 , 0.5 ] ,

      [ 0.5 , 0.5 ]]

B = [ [ 0.3 , 0.7 ] ,

      [ 0.5 , 0.5 ] ]

Pi = [ 0.5 , 0.5 ]

def label_2_id(target):

    dt = { v:k for k,v in enumerate(V)}

    return [ dt[item] for item in target ]

# target = label_2_id( ['红','红','黑','红'] )

target = label_2_id( ['红','红'] )

BruteForce暴力算法，计算复杂度：

# 路径展示角度

def brute_force_algorithm( target = [] ,path = '' ,prob ='' , pre = -1):

    ret = []

    path_tmp = ''

    prob_tmp = ''

    for k,v in enumerate(Q):

        path_tmp =  '{}/{}'.format(path , v)

        if prob == '':

            prob_tmp = '{}/{},{}'.format(prob , Pi[k] , B[k][target[0]] )

        else:

            prob_tmp = '{}/{},{}'.format( prob , A[pre][k] , B[k][target[0]] )

        if len(target) > 1:

            tmp = brute_force_algorithm(target[1:] , path_tmp ,prob_tmp , pre = k )

            ret.extend( tmp )

        elif len(target) == 1:

            ret.append([path_tmp , prob_tmp])

    return ret

# 总概率展示角度

def brute_force_algorithm( target = [] ,path = '' ,prob = 0 , pre = -1):

    ret = 0

    for k,v in enumerate(Q):

        prob_tmp = prob

        path_tmp =  '{}/{}'.format(path , v)

        if pre == -1 :

            prob_tmp += Pi[k] * B[k][target[0]]  # joint 联合概率局部

        else:

            prob_tmp *= A[pre][k] * B[k][target[0]]

        if len(target) > 1:

            ret += brute_force_algorithm(target[1:] , path_tmp ,prob_tmp , pre = k )

        elif len(target) == 1:

            ret += prob_tmp

    return ret

Forward 前向算法，时间复杂度：

def forward_algorithm( target = [] ):

    prob = [ [ 0 for i in Q] for j in target ]

    for t ,o in enumerate(target):

        if t == 0 :

            for i in range( len(Q) ):

                prob[0][i] = Pi[i] * B[i][o]

        else:

            for id , q in enumerate(Q):

                for k,v in enumerate(prob[t-1]):

                    print(  v ,  A[k][id] , prob , prob[t][id] )

                    prob[t][id] += (v * A[k][id] * B[id][o]  )

    print(prob)

    return prob

Backend后向算法，计算复杂度：

def backend_algorithm( target = [] ):

    prob = [ [ 0.0 for i in Q] for j in target ]

    length = len(target)

    for t in range( length-1 , -1 , -1):

        if t == length-1 :

            for i in range( len(Q) ):   # 后向计算有点问题

                prob[t][i] = 1

        else:

            o = target[t+1]

            for id , q in enumerate(Q):

                if t == 0:

                    for k,v in enumerate(prob[t+1]):

                        prob[t][id] *= 1000

                        prob[t][id] += ( v * A[id][k] * B[k][o] ) * 1000

                        prob[t][id] /= 1000

                else:

                    for k,v in enumerate(prob[t+1]):

                        prob[t][id] += v * A[id][k] * B[k][o]

    for k,v in enumerate(prob[0]):

        prob[0][k] = v * Pi[k] * B[k][target[0]]

    return prob