发表于 | 分类于

List Theme

本篇博客主要是对LeetCode上关于链表题目的总结。对于链表类的题目主要包括以下几类：

  • 链表的查找
  • 链表节点的逆序
  • 链表节点的删除
  • 不同链表间的操作
  • 链表中的环问题

根据以上专题，下面列出了LeetCode中链表题目的分类

链表中节点的逆序

链表中节点的重新连接

链表节点的删除

不同链表间的操作

链表中的环问题

以上问题的具体解法和思路和看博客.

链表中的其他问题

发表于 | 分类于

Swap List Node

题目描述：

给定链表的头节点，交换链表中两两链表节点。

例子：

具体描述可以看LeetCode24

解题思路：

解题的思路很直接，我们直接交换节点即可。主要需要注意的是：我们需要用到虚拟头节点的技巧便于处理链表头部；改变链表指向的时候需要注意顺序；到达链表尾部的判断。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if (!head) return head;
        //空节点直接返回
        ListNode* dummy = new ListNode(-1);
        dummy->next = head;
        //定义虚拟头结点指向链表头部
        ListNode* first = dummy;
        ListNode* second = first->next;
        ListNode* third = second->next;
        //定义三个节点的初始位置
        while(second && third){
            ListNode* next = third->next;
            //保存下一个节点
            third->next = second;
            //第二个节点指向改变
            second->next = next;
            //第一个节点指向改变
            first->next = third;
            // 重连交换后节点
            first = second;
            second = next;
            third = !second ? NULL : second->next;
            //节点往下移动用于遍历
        }
        return dummy->next;
    }
};

发表于 | 分类于

Valid IP Address

题目描述：

给定一个字符串；判断其是否是有效的IPV4或者IPV6的字符串。其中字符串不包含空格和特殊字符。

例子：

具体的例子和描述可以参考LeetCode_468

解题思路：

本题中首先主要的难点在于如何分割字符串；利用C++的stringstream函数和getline函数可以将字符串按照指定的方式进行分割；然后就是边界条件的判断，主要包括：

  • 每个分割子串长度判断，IPV4不超过3，IPV6长度不超过4
  • 当前的子串个数判断，IPV4个数为4，IPV6个数为6
  • IPV4中的首字母为0的判断
  • 子串为空的判断，IPV4和IPV6长度均不能为空
  • 子串中各个字符的判断，IPV4中只能是数字类型，IPV6的字母是16进制范围
  • 字符串结尾的判断，字符串的结尾不能是”:”和”.”

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    string validIPAddress(string IP) {
        stringstream is(IP);
        string tmp = "";
        int count = 0;
        if (IP.find(':') == string::npos){
            while(getline(is, tmp, '.')){
                count++;
                if (tmp.empty() || tmp.size() > 3 || (tmp.size() > 1 && tmp[0] == '0') || count > 4) return "Neither";
                for (char c : tmp){
                    if (c < '0' || c > '9')
                        return "Neither";
                }
                int val = stoi(tmp);
                if (val < 0 || val > 255) return "Neither";
            }
            return (IP.back() != '.' && count == 4) ? "IPv4" : "Neither";
        }else{
            while(getline(is, tmp, ':')){
                count++;
                if (tmp.empty() || tmp.size() > 4 || count > 8) return "Neither";
                for (char c : tmp){
                    if (!(c <= '9' && c >= '0') && !(c <= 'f' && c >= 'a') && !(c <= 'F' && c >= 'A'))
                        return "Neither";
                }
            }
            return (count == 8 && IP.back() != ':') ? "IPv6" : "Neither";
        }
        
    }
};

发表于 | 分类于

SVM In MNIST

算法原理简述：

算法中的主要证明在此处不做赘述；主要是介绍代码和与之对应的算法原理。首先，我们是从所有的alpha中调整了其顺序，先遍历那些符合0<alpha<c的数据；然后根据偏离kkt条件的程度，选择出alpha1和alpha2;然后我们根据选择出的alpha1和alpha2计算出alpha1的上下界；计算在未约束的情况下alpha1的最优值；根据和上下界的关系确定新的alpha1值；根据alpha1值确定alpha2值；接下来我们根据新的alpha1和alpha2更新对应的b值和对应的E函数值；至此一轮的迭代结束。
算法中的主要思路是我们有原始问题；但是原始问题相对难以求解，所以选择对偶问题来突破。得到对偶问题的解我们就可以逆向求解得到原始问题的解。对偶问题涉及到多个变量的二次规划问题；所以我们选择每次选择两个变量来不断逼近最优解。选择变量的方式就是找到最不符合KKT条件的第一个变量；然后根据第一个变量找到|E1 - E2|最大的那个第二个变量即可。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @File  : SVM.py
# @Author: mfzhu
# @Date  : 2017/5/10
# @Desc  :
import time
import numpy as np
from sklearn.model_selection import train_test_split
from sklearn.metrics import accuracy_score
import seaborn as sns
import matplotlib.pyplot as plt
def binary(data, threshold):
    """
    :param data: 需要二值化的数据
    :param threshold: 二值化的阈值
    :return: 二值化后的数据
    """
    index_1 = np.array(data > threshold)
    index_2 = np.array(data <= threshold)
    data[index_1] = 1
    data[index_2] = 0
    return data
class svm(object):
    def __init__(self, data_in, label_in, penalty_coefficient, epsilon):
        self.data = data_in
        # 初始化训练数据
        self.label = label_in
        # 初始化标签数据
        self.epsilon = epsilon
        # 确定阈值
        self.penalty_coefficient = penalty_coefficient
        # 确定惩罚系数
        self.row = data_in.shape[0]
        # 数据行数
        self.column = data_in.shape[1]
        # 数据维数
        self.alpha = np.zeros([1, self.row], float)[0]
        # 初始化待训练系数
        self.b = 0.0
        # 初始化偏移量
        self.E = [self.e_func(i) for i in range(self.row)]
        # 计算每个样本的E函数值
        self.iteration = 5000
        # 确定迭代次数
    def g_func(self, index):
        # 计算第index个数据的G函数值
        res = self.b
        for i in range(self.row):
            res += self.alpha[i] * self.label[i] * np.dot(self.data[index], self.data[i])
        return res
    def e_func(self, index):
        # 计算第index个数据的E函数值
        return self.g_func(index) - self.label[index]
    def satisfy_KKT(self, index):
        # 判断第index个样本是否符合KKT条件
        judgeNum = self.g_func(index) * self.label[index]
        if abs(self.alpha[index]) < self.epsilon:
            return judgeNum > 1 or judgeNum == 1
        elif abs(self.alpha[index] - self.penalty_coefficient) < self.epsilon:
            return judgeNum < 1 or judgeNum == 1
        else:
            return abs(judgeNum - 1) < self.epsilon
    # def is_stop(self):
    #     # 确定是否当前符合所有样本符合KKT条件
    #     for index in range(self.row):
    #         if not self.satisfy_KKT(index):
    #             return False
    #     return True
    # def kernel(self):
    #
    #     if self.kernel == "liner":
    #         pass
    #     if self.kernel == "poly":
    #         return np.sum(np.dot(x1, x2))**3
    def select_alpha1_alpha2(self):
        # 选择出两个待迭代的系数
        index_list = [i for i in range(self.row)]
        front_list = list(filter(lambda i: 0 < self.alpha[i] < self.penalty_coefficient, index_list))
        back_list = list(set(index_list) - set(front_list))
        index = front_list
        index.extend(back_list)
        # 此处主要是重新调整了索引的顺序，先遍历的部分是满足(0, C)的索引
        for i in index:
            if self.satisfy_KKT(i):
                continue
            E_1 = self.E[i]
            max_difference = [0, 0]
            # 保存的是另外一个索引和其E函数值和第一个索引的E函数值的绝对值差
            for j in index_list:
                if j == i:
                    continue
                E_2 = self.E[j]
                if abs(E_1 - E_2) > max_difference[0]:
                    max_difference[0] = abs(E_1 - E_2)
                    max_difference[1] = j
            # 找到E函数值差最大的两个索引并返回
            return i, max_difference[1]
    def K_fun(self, index1, index2):
        # 计算两个样本之间的k函数值
        return np.dot(self.data[index1], self.data[index2])
    def train(self):
        # 训练函数
        for time in range(self.iteration):
            index1, index2 = self.select_alpha1_alpha2()
            # 选择出两个待训练的索引
            if self.label[index1] == self.label[index2]:
                # 如果两个索引对应的标签同号的情况
                # 确定alpha2的上下界
                lowBound = max(0, self.alpha[index1] + self.alpha[index2] - self.penalty_coefficient)
                highBound = min(self.penalty_coefficient, self.alpha[index1] + self.alpha[index2])
            else:
                # 异号的情况
                # 确定alpha2的上下界
                lowBound = max(0, self.alpha[index2] - self.alpha[index1])
                highBound = min(self.penalty_coefficient, self.penalty_coefficient +
                                self.alpha[index2] - self.alpha[index1])
            eta = self.K_fun(index1, index1) + self.K_fun(index2, index2) - 2 * self.K_fun(index1, index2)
            # 计算eta值
            alpha1_old = self.alpha[index1]
            alpha2_old = self.alpha[index2]
            # 记录下alpha1和alpha2的原始值
            alpha2_unc = self.alpha[index2] + self.label[index2] * (self.E[index1] - self.E[index2]) / eta
            # 计算未约束的情况下的alpha2的结果
            if alpha2_unc > highBound:
                alpha2_new = highBound
            elif alpha2_unc < lowBound:
                alpha2_new = lowBound
            else:
                alpha2_new = alpha2_unc
            # 判断未约束值与上下界的关系并更新alpha2的值
            alpha1_new = alpha1_old + (self.label[index1] * self.label[index2]
                                       * (alpha2_old - alpha2_new))
            # 更新alpha1的值
            b_new = 0
            b1_new = -self.E[index1] - self.label[index1] * self.K_fun(index1, index1) * (
                alpha1_new - alpha1_old) - self.label[index2] * self.K_fun(
                index2, index1) * (alpha2_new - alpha2_old) + self.b
            b2_new = -self.E[index2] - self.label[index2] * self.K_fun(index2, index2) * (
                alpha2_new - alpha2_old) - self.label[index1] * self.K_fun(
                index1, index2) * (alpha1_new - alpha1_old) + self.b
            # 更新alpha1和alpha2对应的b值
            if 0 < alpha1_new < self.penalty_coefficient:
                b_new = b1_new
            elif 0 < alpha2_new < self.penalty_coefficient:
                b_new = b2_new
            else:
                b_new = (b1_new + b2_new) / 2
            self.b = b_new
            # 更新b值
            self.alpha[index1] = alpha1_new
            self.alpha[index2] = alpha2_new
            # 更新alpha值
            self.E[index1] = self.e_func(index1)
            self.E[index2] = self.e_func(index2)
            # 更新E值
    def _predict_(self, feature):
        # 预测输入向量的标签
        result = self.b
        for i in range(self.row):
            result += self.alpha[i] * self.label[i] * np.dot(self.data[i], feature)
        if result > 0:
            return 1
        else:
            return -1
    def predict(self, features):
        # 预测多个输入的标签
        result = []
        for i in range(len(features)):
            result.append(self._predict_(features[i]))
        return result
if __name__ == '__main__':
    time1 = time.time()
    print("start reading the data:")
    raw_path = r'F:\work and learn\ML\dataset\MNIST\train.csv'
    raw_data = np.loadtxt(raw_path, delimiter=',', skiprows=1)
    # 读入原始数据
    label = raw_data[:, 0]
    data = raw_data[:, 1:]
    # 区分标签数据和原始数据
    data = binary(data, 100)
    label[label != 1] = -1
    # 进行二值化和对标签二值化（这边做的是二分类）
    train_data, test_data, train_label, test_label = train_test_split(data, label, test_size=0.33, random_state=23323)
    time2 = time.time()
    print("read data cost:", time2 - time1, " seconds", '\n')
    # 将训练数据切分成三块用于训练和测试
    print("start training the model:")
    clf = svm(train_data, train_label, 1000, 0.001)
    clf.train()
    time3 = time.time()
    print("training cost:", time3 - time2, ' seconds', '\n')
    print("start predicting:")
    # 定义svm类然后训练
    test_predict = clf.predict(test_data)
    print(test_predict)
    score = accuracy_score(test_label, test_predict)
    time4 = time.time()
    print("predicting cost:", time4 - time3, ' seconds', '\n')
    # 利用训练到的模型预测测试集的标签
    print("the accuracy_score is:", score)

代码运行结果：

从运行结果可以知道，训练的时间较长，且预测的正确率较低。通过与sklearn的包的内置函数比较，正确率和训练时间等方面都较差于sklearn的svm。
img

发表于 | 分类于

Rotate List

题目描述：

给定一个链表的头节点和一个整数k，其中整数k表示从尾部向左k个节点进行旋转。要求返回旋转后的链表头结点。

例子：

具体描述见LeetCode61。

解题思路：

主要是通过将链表连接成环状，然后通过和链表长度的比较找到目标节点断开链表。主要注意的是：在链表中有时候可以通过连接成环来处理问题；问题中k可以大于链表长度的情况的处理，通过求余即可。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if (!head) return head;
        // 空节点直接返回
        int length = 1;
        ListNode* cur = head;
        while(cur->next){
            cur = cur->next;
            length++;
        }
        // 计算出链表的长度
        cur->next = head;
        // 将链表连接成环状
        if (k %= length){
        // 当k大于链表的长度的时候
            for (auto i = 0; i < length - k; i++)
                cur = cur->next;
                //找到需要断开的位置
        }
        ListNode* newhead = cur->next;
        cur->next = NULL;
        //断开并且修改尾部节点指向
        return newhead;
        
        
    }
};

发表于 | 分类于

Permutation In String

题目描述：

给定两个字符串str1和str2，要求判断str2中是否包含着str1的任意排列。

例子：

具体描述可以看LeetCode567

解题思路：

这题主要的难点是克服全排列这个问题。对于字符串的全排列我们知道，同一个字符串的所有全排列得到的哈希表是一致的；利用这个为突破口，我们首先记录下str1的哈希表，然后在str2中构建一个和str1一样大的窗口，通过不断移动窗口和判断窗口中的哈希表是否和str1的哈希表一致即可判断其是否包含了str1的排列。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        if (s1.size() > s2.size())
            return false;
        // 当str1的长度大于str2的时候肯定不符合条件
        vector<int> v1(26, 0);
        vector<int> v2(26, 0);
        // 用数组来作为哈希表的构建
        for (int i = 0; i < s1.size(); i++){
            v1[s1[i] - 'a']++;
        }
        //生成str1的哈希表
        for (int j = 0; j < s1.size(); j++){
            v2[s2[j] - 'a']++;
        }
        //生成str2前和str1长度一致的哈希表
        if (v1 == v2) return true;
        # 如果相同则返回存在
        for (int i = s1.size(); i < s2.size(); i++){
            v2[s2[i] - 'a']++;
            //增加新位置的哈希
            v2[s2[i - s1.size()] - 'a']--;
            // 减小被移动位置的哈希
            if (v1 == v2)
                return true;
        }
        return false;  
    }
};

发表于 | 分类于

Reverse Whole List

题目描述：

给定链表的头结点，将其全部逆序后返回新链表的头结点。

例子：

具体的描述可以看LeetCode206。

解题思路：

链表中的基本题；主要的难点在于要保存下一个节点用于下次遍历；另外我们用pre=NULL这个操作可以少定义一个变量。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (!head) return head;
        ListNode* pre = NULL;
        ListNode* cur = head;
        while(cur){
            ListNode* next = cur->next;
            # 保存下一个节点
            cur->next = pre;
            # 重新指向指针，此处pre定义为NULL，一举两得
            pre = cur;
            cur = next;
            # 更改pre和cur继续遍历
        }
        return pre;        
    }
};

发表于 | 分类于

HMM_Baum_Welch

算法原理简述：

Baum_Welch算法是在给定观测序列而不知道状态序列的情况下，如何估计HMM模型中的A,B,PI参数的算法。因为存在隐遍历状态序列所以我们可以利用EM算法来对参数进行估计。EM算法此处不再赘述，其中算法的迭代过程主要用到了先前博客中提到的前向函数(alpha_func)和后向函数(beta_func)以及根据这两个函数所计算得到gamma_func以及kesi_func；具体的参数迭代过程和公式可以参考李航老师的书籍的隐马尔科夫模型一章。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @File  : HMM_Baum_Welch.py
# @Author: mfzhu
# @Date  : 2017/5/5
# @Desc  :
import numpy as np
import copy
class HMM_Baum_Welch(object):
    def __init__(self, input_data, num_state, num_observation):
        self.time_length = len(input_data)
        # 记录时线的长度
        self.num_state = num_state
        # 记录状态变量的个数
        self.num_observation = num_observation
        # 记录观测变量的个数
        self.data = input_data
        # 记录当前输入观测向量的数据
        self.iteration = 5
        # 迭代次数
        # self.state2state = np.ones([self.num_state, self.num_state]) / self.num_state
        # self.state2observation = np.ones([self.num_state, self.num_observation]) / self.num_observation
        # self.pi = np.ones([1, self.num_state])[0] / self.num_state
        # 以上注释部分为原始代码，为了测试代码正确性利用李航老师书上数据进行测试
        self.state2state = np.array([[0.5, 0.2, 0.3], [0.3, 0.5, 0.2], [0.2, 0.3, 0.5]])
        self.state2observation = np.array([[0.5, 0.5], [0.4, 0.6], [0.7, 0.3]])
        self.pi = np.array([0.2, 0.4, 0.4])
        # 测试数据
    def alpha_func(self, time, sequence):
        # 计算时间为time，当前观测为sequence的前向权重向量
        alpha = self.pi * self.state2observation[:, sequence[0]]
        for i in range(1, time):
            nextAlpha = []
            for j in range(self.num_state):
                perState = alpha * self.state2state[:, j]
                nextAlpha.append(np.sum(perState) * self.state2observation[j, sequence[i]])
            alpha = copy.deepcopy(nextAlpha)
        return np.array(alpha)
    def beta_func(self, time, sequence):
        # 计算时间为time，当前观测为sequence的后向权重向量
        beta = np.ones([1, self.num_state])[0]
        for i in range(len(sequence), time, -1):
            prebeta = []
            if i == 1:
                beta = beta * self.pi * self.state2observation[:, sequence[0]]
                break
            for j in range(self.num_state):
                prebeta.append(np.sum(self.state2state[j, :] * self.state2observation[:, sequence[i - 1]] * beta))
            beta = copy.deepcopy(prebeta)
        return np.array(beta)
    def gamma_func(self, time, sequence):
        # 计算时间为time时的各个状态的对应概率向量gamma
        alpha = self.alpha_func(time, sequence)
        beta = self.beta_func(time, sequence)
        return (alpha * beta) / np.sum(alpha * beta)
    def kesi_func(self, time, sequence):
        # 计算时间为time, 状态为i,时间为time+1,状态为j的kesi函数
        # 取各个状态的可能最后生成一个矩阵kesi
        alpha = self.alpha_func(time, sequence)
        beta = self.beta_func(time + 1, sequence)
        kesi = np.zeros([self.num_state, self.num_state])
        demo = 0
        for i in range(self.num_state):
            for j in range(self.num_state):
                demo += alpha[i] * self.state2state[i, j] \
                        * self.state2observation[j, sequence[time]] * beta[j]
        for i in range(self.num_state):
            for j in range(self.num_state):
                kesi[i, j] = alpha[i] * self.state2state[i, j] * \
                             self.state2observation[j, sequence[time]] * beta[j]
        kesi /= demo
        return kesi
    def train(self):
        # 根据以上函数和输入数据进行训练模型得到模型的参数
        for i in range(self.iteration):
            # 迭代次数的循环
            new_pi = self.gamma_func(1, self.data)
            # 关于新的初始概率的计算
            new_state2state = np.zeros([self.num_state, self.num_state])
            # 定义新的概率转移矩阵
            demo = np.zeros([1, self.num_state])[0]
            # 计算矩阵中所用的分母
            numer = np.zeros([self.num_state, self.num_state])
            # 计算矩阵中所用到的分子
            for t in range(1, self.time_length):
                demo += self.gamma_func(t, self.data)
            # 计算分母
            for t in range(1, self.time_length):
                numer += self.kesi_func(t, self.data)
            # 计算分子
            for i in range(self.num_state):
                for j in range(self.num_state):
                    new_state2state[i][j] = numer[i, j] / np.sum(demo[i])
            # 计算状态转移矩阵的各个概率
            new_state2observation = np.zeros([self.num_state, self.num_observation])
            # 初始化状态和观测值的转移概率
            demo = np.zeros([1, self.num_state])[0]
            # 初始化计算分母所用的向量
            for t in range(1, self.time_length + 1):
                demo += self.gamma_func(t, self.data)
            # 计算分母
            for k in range(self.num_observation):
                # k对应观测序列的可能进行循环
                numer = np.zeros([1, self.num_state])[0]
                # 每个k对应一个分子向量
                for t in range(1, self.time_length + 1):
                    # 在所有的状态序列中找到时间下和k观测相同的进行计算
                    if k == self.data[t - 1]:
                        numer += self.gamma_func(t, self.data)
                    # 相同的情况计算分子
                new_state2observation[:, k] = numer / demo
                # 对应每个k更新矩阵
            self.pi = new_pi
            self.state2state = new_state2state
            self.state2observation = new_state2observation
            # 分布更新状态转移矩阵，观测转移矩阵，初始状态向量
        return self.state2state, self.state2observation, self.pi
if __name__ == '__main__':
    test_data = np.array([0, 1, 0])
    hmm_bm = HMM_Baum_Welch(test_data, 3, 2)
    s2s, s2o, pi = hmm_bm.train()
    print("the initial probality is:")
    print(pi)
    print("the state matrix is:")
    print(s2s)
    print("the observation matrix is:")
    print(s2o)

运行结果：

在程序中为了测试主要是利用了李航老师课本的原始数据来验证程序的正确性。在进行5轮的迭代后得到如下图的结果，通过和他人的博客结果进行比较可知程序结果的正确性。
img

发表于 | 分类于

HMM_Viterbi

算法原理简述：

本篇博客中主要介绍的是关于HMM算法中的维特比算法。该算法主要是给定A,B,PI参数和观测序列的情况下要求求出最有可能出现的状态序列。利用的思想还是动态规划的思想。
主要是定义了两个函数:

  • delta(t, i),表示在所有到t时刻的状态为i的状态序列中概率最大的那个状态序列。
  • psi(t, i)表示在到t时刻状态为i的所有状态序列中概率最大序列的t-1时刻的状态。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @File  : HMM_Viterbi.py
# @Author: mfzhu
# @Date  : 2017/5/7
# @Desc  :
import numpy as np
class HMM_Vtterbi(object):
    def __init__(self, state2state, state2observation, pi):
        self.state2state = state2state
        # 初始化状态转移矩阵
        self.state2observation = state2observation
        # 初始化观测转移矩阵
        self.pi = pi
        # 初始化初始状态概率向量
        self.num_state = len(state2state)
        # 确定模型中的状态数
    def predict(self, sequence):
        # 预测序列的可能状态
        res = []
        # 保存结果
        delta = self.pi * self.state2observation[:, sequence[0]]
        # 初始化delta函数向量
        psi = np.zeros([self.num_state, len(sequence)], int)
        # 初始化psi函数矩阵
        for t in range(1, len(sequence)):
            # 从时刻1开始迭代
            new_delta = []
            psi_col = []
            # 保存当前轮迭代的delta和psi
            for i in range(self.num_state):
                tmp = delta * self.state2state[:, i]
                index = tmp.argmax()
                # 找到最大值所对应的index
                psi_col.append(index)
                new_delta.append(tmp[index] * self.state2observation[i, sequence[t]])
                # 更新当前轮的delta和psi
            psi[:, t] = psi_col
            delta = np.array(new_delta)
            # 保存结果
        last = delta.argmax()
        res.insert(0, last)
        # 回溯找到最大概率所对应的状态序列
        for t in range(len(sequence) - 1, 0, -1):
            res.insert(0, psi[last, t])
            last = int(psi[last, t])
        return res
if __name__ == '__main__':
    state2state = np.array([[0.5, 0.2, 0.3], [0.3, 0.5, 0.2], [0.2, 0.3, 0.5]])
    state2observation = np.array([[0.5, 0.5], [0.4, 0.6], [0.7, 0.3]])
    pi = np.array([0.2, 0.4, 0.4])
    sequence = [0, 1, 0]
    # 以上数据初始化模型
    v = HMM_Vtterbi(state2state, state2observation, pi)
    print(v.predict(sequence))
    # 训练模型并预测对应的状态序列

代码结果：

通过与李航老师书本上的例子进行比较可知，当前算法的运算结果是正确的。

img

发表于 | 分类于

HMM_Forward_Backward

算法原理简述：

本篇博客主要是介绍隐马尔科夫算法中在给定A,B,PI参数的情况下，计算观测序列出现概率的算法。主要包括了前向算法和后向算法。
其中前向算法主要是定义函数alpha(t, i),表示在t时刻，其处在状态i,且(t1,t2,…t)的观测序列为(o1, o2,…)的概率；而后通过递推式，利用动态规划的方法来计算即可。
后向算法是定义函数beta(t, i);表示在t时刻处在状态i,且(t+1, t+2,…T)的观测序列为(o(t+1), o(t+2),…o(T))的概率；也是通过递归公式和动态规划的思想来实现计算过程。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
# @File  : HMM_forward_backward.py
# @Author: mfzhu
# @Date  : 2017/5/4
# @Desc  :
import numpy as np
import copy
class HMM_forward(object):
    def __init__(self, state2state, state2observation, pi):
        self.state2state = state2state
        # 初始化状态转移矩阵
        self.state2observation = state2observation
        # 初始化观测转移矩阵
        self.pi = pi
        # 初始化初始状态概率向量
        self.num_state = len(state2state)
        # 确定模型中的状态数
    def alpha_func(self, time, sequence):
        alpha = pi * self.state2observation[:, sequence[0]]
        # 初始化time=1的alpha向量
        for i in range(1, time):
            nextAlpha = []
            # 保存下一轮迭代的alpha向量
            for j in range(self.num_state):
                perState = alpha * self.state2state[:, j]
                # 计算每种状态转移的值
                nextAlpha.append(np.sum(perState) * self.state2observation[j, sequence[i]])
                # 当前状态转移的结果保存
            alpha = copy.deepcopy(nextAlpha)
            # 更新alpha向量
        return np.array(alpha)
class HMM_backward(object):
    def __init__(self, state2state, state2observation, pi):
        self.state2state = state2state
        # 初始化状态转移矩阵
        self.state2observation = state2observation
        # 初始化观测转移矩阵
        self.pi = pi
        # 初始化初始状态概率向量
        self.num_state = len(state2state)
        # 确定模型中的状态数
    def beta_func(self, time, sequence):
        beta = np.ones([1, self.num_state])[0]
        # 初始化beta向量
        for i in range(len(sequence), time, -1):
            prebeta = []
            # 保存下一轮的beta向量
            if i == 1:
                beta = beta * pi * self.state2observation[:, sequence[0]]
                # 当time=1的时候和pi向量进行乘积
                break
            for j in range(self.num_state):
                prebeta.append(np.sum(self.state2state[j, :] * self.state2observation[:, sequence[i - 1]] * beta))
            beta = copy.deepcopy(prebeta)
            # 更新beta向量
        return np.array(beta)
if __name__ == '__main__':
    state2state = np.array([[0.5, 0.2, 0.3], [0.3, 0.5, 0.2], [0.2, 0.3, 0.5]])
    state2observation = np.array([[0.5, 0.5], [0.4, 0.6], [0.7, 0.3]])
    pi = np.array([0.2, 0.4, 0.4])
    sequence = [0, 1, 0]
    forward = HMM_forward(state2state, state2observation, pi)
    backward = HMM_backward(state2state, state2observation, pi)
    print("the alpha matrix:")
    print(forward.alpha_func(1, sequence))
    print(forward.alpha_func(2, sequence))
    print(forward.alpha_func(3, sequence))
    print("the beta matrix: ")
    print(backward.beta_func(1, sequence))
    print(backward.beta_func(2, sequence))
    print(backward.beta_func(3, sequence))

代码结果：

通过与李航老师书本的结果比较可以知道算法的正确性。

img