转自:http://blog.csdn.net/orlandowww/article/details/52706135
隐马尔科夫模型(HMM)
模型介绍
HMM模型是由一个“五元组”组成:
- StatusSet: 状态值集合
- ObservedSet: 观察值集合
- TransProbMatrix: 转移概率矩阵
- EmitProbMatrix: 发射概率矩阵
- InitStatus: 初始状态分布
参数介绍
- StatusSet,状态值集合为(B, M, E, S): {B:begin, M:middle, E:end, S:single}。分别代表每个状态代表的是该字在词语中的位置,B代表该字是词语中的起始字,M代表是词语中的中间字,E代表是词语中的结束字,S则代表是单字成词。
- ObservedSet,观察值集合就是所有汉字,甚至包括标点符号所组成的集合。
- TransProbMatrix,状态转移概率矩阵的含义就是从状态X转移到状态Y的概率,是一个4×4的矩阵,即{B,E,M,S}×{B,E,M,S}。
- EmitProbMatrix,发射概率矩阵的每个元素都是一个条件概率,代表P(Observed[i]|Status[j])
- InitStatus,初始状态概率分布表示句子的第一个字属于{B,E,M,S}这四种状态的概率。
Viterbi算法的核心思想就是动态规划实现最短路径,按照Michael Collins教的,核心思想是:
Define a dynamic programming table π(k,u,v),
π(k,u,v) = maximum probability of a tag sequence ending in tags u,v at position k.
For any k ∈ {1…n}: π(k,u,v) = max ( π(k-1,w,u) × q(v|w,u) × e(xk|v) )
完整的Viterbi算法网上有很多资料可以查看,本文主要关注代码的实现。
实验 代码1:模型训练
生成三个文件:
- prob_start.py 为初始状态概率
- prob_trans.py 为状态转移概率
- prob_emit.py 为发射概率
# -*- coding: utf-8 -*-# 二元隐马尔科夫模型(Bigram HMMs)
# 'trainCorpus.txt_utf8'为人民日报已经人工分词的预料,29万多条句子import sys#state_M = 4
#word_N = 0
A_dic = {}
B_dic = {}
Count_dic = {}
Pi_dic = {}
word_set = set()
state_list = ['B','M','E','S']
line_num = -1INPUT_DATA = "https://www.it610.com/article/trainCorpus.txt_utf8"
PROB_START = "trainHMM\prob_start.py"#初始状态概率
PROB_EMIT = "trainHMM\prob_emit.py"#发射概率
PROB_TRANS = "trainHMM\prob_trans.py"#转移概率def init():#初始化字典
#global state_M
#global word_N
for state in state_list:
A_dic[state] = {}
for state1 in state_list:
A_dic[state][state1] = 0.0
for state in state_list:
Pi_dic[state] = 0.0
B_dic[state] = {}
Count_dic[state] = 0def getList(input_str):#输入词语,输出状态
outpout_str = []
if len(input_str) == 1:
outpout_str.append('S')
elif len(input_str) == 2:
outpout_str = ['B','E']
else:
M_num = len(input_str) -2
M_list = ['M'] * M_num
outpout_str.append('B')
outpout_str.extend(M_list)#把M_list中的'M'分别添加进去
outpout_str.append('E')
return outpout_strdef Output():#输出模型的三个参数:初始概率+转移概率+发射概率
start_fp = file(PROB_START,'w')
emit_fp = file(PROB_EMIT,'w')
trans_fp = file(PROB_TRANS,'w')
print "len(word_set) = %s " % (len(word_set))for key in Pi_dic:#状态的初始概率
Pi_dic[key] = Pi_dic[key] * 1.0 / line_num
print >>start_fp,Pi_dicfor key in A_dic:#状态转移概率
for key1 in A_dic[key]:
A_dic[key][key1] = A_dic[key][key1] / Count_dic[key]
print >>trans_fp,A_dicfor key in B_dic:#发射概率(状态->词语的条件概率)
for word in B_dic[key]:
B_dic[key][word] = B_dic[key][word] / Count_dic[key]
print >>emit_fp,B_dicstart_fp.close()
emit_fp.close()
trans_fp.close()def main():ifp = file(INPUT_DATA)
init()
global word_set#初始是set()
global line_num#初始是-1
for line in ifp:
line_num += 1
if line_num % 10000 == 0:
print line_numline = line.strip()
if not line:continue
line = line.decode("utf-8","ignore")#设置为ignore,会忽略非法字符word_list = []
for i in range(len(line)):
if line[i] == " ":continue
word_list.append(line[i])
word_set = word_set | set(word_list)#训练预料库中所有字的集合lineArr = line.split(" ")
line_state = []
for item in lineArr:
line_state.extend(getList(item))#一句话对应一行连续的状态
if len(word_list) != len(line_state):
print >> sys.stderr,"[line_num = %d][line = %s]" % (line_num, line.endoce("utf-8",'ignore'))
else:
for i in range(len(line_state)):
if i == 0:
Pi_dic[line_state[0]] += 1#Pi_dic记录句子第一个字的状态,用于计算初始状态概率
Count_dic[line_state[0]] += 1#记录每一个状态的出现次数
else:
A_dic[line_state[i-1]][line_state[i]] += 1#用于计算转移概率
Count_dic[line_state[i]] += 1
if not B_dic[line_state[i]].has_key(word_list[i]):
B_dic[line_state[i]][word_list[i]] = 0.0
else:
B_dic[line_state[i]][word_list[i]] += 1#用于计算发射概率
Output()
ifp.close()if __name__ == "__main__":
main()
- 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
- 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
# -*- coding: utf-8 -*-def load_model(f_name):
ifp = file(f_name, 'rb')
return eval(ifp.read())#eval参数是一个字符串, 可以把这个字符串当成表达式来求值,prob_start = load_model("trainHMM\prob_start.py")
prob_trans = load_model("trainHMM\prob_trans.py")
prob_emit = load_model("trainHMM\prob_emit.py")def viterbi(obs, states, start_p, trans_p, emit_p):#维特比算法(一种递归算法)
V = [{}]
path = {}
for y in states:#初始值
V[0][y] = start_p[y] * emit_p[y].get(obs[0],0)#在位置0,以y状态为末尾的状态序列的最大概率
path[y] = [y]
for t in range(1,len(obs)):
V.append({})
newpath = {}
for y in states:#从y0 -> y状态的递归
(prob, state) = max([(V[t-1][y0] * trans_p[y0].get(y,0) * emit_p[y].get(obs[t],0) ,y0) for y0 in states if V[t-1][y0]>0])
V[t][y] =prob
newpath[y] = path[state] + [y]
path = newpath#记录状态序列
(prob, state) = max([(V[len(obs) - 1][y], y) for y in states])#在最后一个位置,以y状态为末尾的状态序列的最大概率
return (prob, path[state])#返回概率和状态序列def cut(sentence):
prob, pos_list =viterbi(sentence,('B','M','E','S'), prob_start, prob_trans, prob_emit)
return (prob,pos_list)if __name__ == "__main__":
test_str = u"新华网驻东京采访人员报道"
prob,pos_list = cut(test_str)
print test_str
print pos_list
- 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
- 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
新华网驻东京采访人员报道
['B', 'M', 'E', 'S', 'B', 'E', 'B', 'E', 'B', 'E']
- 1
- 2
- 1
- 2
转自:http://blog.csdn.net/orlandowww/article/details/52693225
正向最大匹配算法(FMM)
正向最大匹配算法(FMM)是一种基于词典的分词方法,思想很简单就是从左向右扫描寻找词的最大匹配,比如词典中同时含有“钓鱼”和“钓鱼岛”,那“钓鱼岛属于中国”就会被分词成“钓鱼岛/属于/中国”
过程
- 限定词的最大长度(例如5)
- 从最大的长度开始在词库中进行匹配,直到匹配成功
- 更新起点的位置继续上一步骤直到全部完成
# -*- coding: utf-8 -*-
# 中文正向最大匹配(FMM)分词import sys
reload(sys)#动态重新加载sys模块
sys.setdefaultencoding('utf8')word_dict = ['新华网', '东京', '采访人员', '吴谷丰', '日本共同社', '28', '报道']test_str = '新华网东京电采访人员吴谷丰据日本共同社28日报道'# 获取分词
def getSeg(text):
if not text:
return ''if len(text) == 1:
return textif text in word_dict:
return text
else:
small = len(text) - 1
text = text[0:small]
return getSeg(text)def main():
global test_str
test_str = test_str.decode('utf8').strip()
max_len = 5# 正向最大匹配分词测试,最大长度5
result_str = ''# 保存要输出的分词结果
result_len = 0
print 'input :', test_str
while test_str:tmp_str = test_str[0:max_len]
seg_str = getSeg(tmp_str)
seg_len = len(seg_str)
result_len = result_len + seg_lenif seg_str.strip():
result_str = result_str + seg_str + ' / '
test_str = test_str[seg_len:]print 'output :', result_strif __name__ == '__main__':
main()
- 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
- 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
input : 新华网东京电采访人员吴谷丰据日本共同社28日报道
output : 新华网 / 东京 / 电 / 采访人员 / 吴谷丰 / 据 / 日本共同社 / 28 / 日 / 报道 /
- 1
- 2
- 1
- 2
word_dict = [line.strip() for line in open('dict.txt')]
正向最大匹配算法(FMM) 正向最大匹配算法(FMM)是一种基于词典的分词方法,思想很简单就是从左向右扫描寻找词的最大匹配,比如词典中同时含有“钓鱼”和“钓鱼岛”,那“钓鱼岛属于中国”就会被分词成“钓鱼岛/属于/中国”
过程
- 限定词的最大长度(例如5)
- 从最大的长度开始在词库中进行匹配,直到匹配成功
- 更新起点的位置继续上一步骤直到全部完成
# -*- coding: utf-8 -*-
# 中文正向最大匹配(FMM)分词import sys
reload(sys)#动态重新加载sys模块
sys.setdefaultencoding('utf8')word_dict = ['新华网', '东京', '采访人员', '吴谷丰', '日本共同社', '28', '报道']test_str = '新华网东京电采访人员吴谷丰据日本共同社28日报道'# 获取分词
def getSeg(text):
if not text:
return ''if len(text) == 1:
return textif text in word_dict:
return text
else:
small = len(text) - 1
text = text[0:small]
return getSeg(text)def main():
global test_str
test_str = test_str.decode('utf8').strip()
max_len = 5# 正向最大匹配分词测试,最大长度5
result_str = ''# 保存要输出的分词结果
result_len = 0
print 'input :', test_str
while test_str:tmp_str = test_str[0:max_len]
seg_str = getSeg(tmp_str)
seg_len = len(seg_str)
result_len = result_len + seg_lenif seg_str.strip():
result_str = result_str + seg_str + ' / '
test_str = test_str[seg_len:]print 'output :', result_strif __name__ == '__main__':
main()
- 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
- 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
input : 新华网东京电采访人员吴谷丰据日本共同社28日报道
output : 新华网 / 东京 / 电 / 采访人员 / 吴谷丰 / 据 / 日本共同社 / 28 / 日 / 报道 /
- 1
- 2
- 1
- 2
word_dict = [line.strip() for line in open('dict.txt')]
推荐阅读
- paddle|动手从头实现LSTM
- 人工智能|干货!人体姿态估计与运动预测
- 推荐系统论文进阶|CTR预估 论文精读(十一)--Deep Interest Evolution Network(DIEN)
- Python专栏|数据分析的常规流程
- 分析COMP122 The Caesar Cipher
- 读书笔记|《白话大数据和机器学习》学习笔记1
- Pytorch学习|sklearn-SVM 模型保存、交叉验证与网格搜索
- 技术|为参加2021年蓝桥杯Java软件开发大学B组细心整理常见基础知识、搜索和常用算法解析例题(持续更新...)
- C语言学习(bit)|16.C语言进阶——深度剖析数据在内存中的存储
- Python机器学习基础与进阶|Python机器学习--集成学习算法--XGBoost算法