分词
自然语言处理是机器学习领域比较通用的方向，可以和推荐、图像相提并论啦，本系列的博客就就围绕自然语言处理介绍一些相关概念，可以给初学者提供一个学习的地方。
中文分词和英文分词有着极大的不同，英文会有空格进行分开，但是中文不仅没有相应的分隔符，甚至歧义也是常有的事情，就如下面这个例子。
南京市长江大桥
这句话使用不同的分词方法会得到截然不同的结果。
正向最大匹配法（Maximun Match）
正向最大匹配法一种比较常用的匹配算法，其基本思想如下。假定分词词典中的词最大长度的词长度是L,对于输入的语句，先从头截取前L个字符，进行匹配，如果有则匹配成功，如果失败就去掉前L个字符中的最后一个，然后重新匹配，直到匹配成功为止。
思路十分简单，但是问题也不少，我们来看看上文中的例子，如果我们的词典中有一个词是"南京市长"那么匹配结果就变成了
南京市长/江大桥
能明显，这样的结果不是我们想要的结果。
规则分词
逆向最大匹配（Reverse Maximum Match）
逆向最大匹配算法和上文讲到的正向最大匹配法基本类似，就是方向上可能有点不同，逆向最大匹配是从文本的末端进行匹配，如果匹配失败就去掉前面的一个字符重新匹配，你可能会问为什么会有这种算法呢，感觉和上面的算法差不多呢？
其实主要是因为汉语中的偏正序结果较多，所以逆向最大匹配算法准确率会更加高一些。
单纯使用正向最大匹配法的错误率是1691
逆向最大匹配的错误率是2451
双向最大匹配算法
这个算法是将正向最大匹配的到的分词结果和逆向最大匹配算法得到的结果进行比较，然后按照最大匹配原则，选取词数切分最少的作为结果。根据统计表明中文中有90%的是正正逆向切词结果正确且切分正确的，有大概9%的句子切分结果不一样但是其中一个是正确的，只有不到1%的是正逆向切分都是错误的。
正向：南京市/长江大桥
逆向：南京市/长江/大桥
最后:南京市/长江大桥
最后我们会选择切分次数较少的。
统计分词
随着我们的语料数据不断增大，我们当然不用靠想想来做一些事情，分词也是一样的，统计模型分词就出现啦。
HMM 分词算法
当处理一句话的时候，需要对这句话的每次字都给一个词位，所谓的词位，就是B(词首), M(词中), E(词尾), S(单独词)，所以逐个字的扫描。例如
南/B京/M市/E长/B江/M大/M桥/E
接下来我们来一个数学的表达讲解。
用λ表示一句话，λ=[λ0,λ1,λ2,λn],其中λi就是其中的一个字，O=[o0,o1,...,on]，我们就是要针对一句话的中的每个字给出{B,M,E,S}这样的标签。
P=maxP(o∣λ)=P(o0∣λ0)P(o1∣λ1)...P(on∣λn)(1.1)
也就是给每个字打上最大概率的标签。而以上这个公式是建立在两个假设的基础上的。
- 有限历史性假设: si 只由 si−1 决定
- 独立输出假设：第 i 时刻的接收信号 oi只由发送信号 λi 决定
P(o∣λ)=P(λ)P(λ∣o)P(o)(1.2)
这里是一个贝叶斯公式，对于P(λ),计算是一个常数，所以实际计算中就忽略啦。
P(λ∣o)=P(λ0∣o0)P(λ1∣o1)...P(λn∣on)(1.3)
P(o)=P(o1)P(o2∣o1)P(o3∣o1,o2)...P(on∣o1,,on−1)(1.4)
根据第二个假设
P(o)=P(o1)P(o2∣o1)P(o3∣o2)...P(on∣on−1)(1.5)
在HMM算法中，P(λk∣ok)称为发射概率，P(ok∣ok−1)称为转移概率。所以从训练数据中求的这两个概率，我们就能遇到新的语句的时候很快计算出P(λ∣o)的最大标签期望，从而做到正确的切词。
这里可能还是对算法的细节迷惑，那P(λk∣ok)和P(ok∣ok−1)在具体的算法中具体计算的是什么呢？
P(ok∣ok−1):
{
'E': {
'E': 0.0,
'S': 0.5310673430644739,
'B': 0.46893265693552616,
'M': 0.0
},
'S': {
'E': 0.0,
'S': 0.46460125869921165,
'B': 0.3503213832274479,
'M': 0.0
},
'B': {
'E': 0.8832824882681853,
'S': 0.0,
'B': 0.0,
'M': 0.1167175117318146
},
'M': {
'E': 0.7222256882859919,
'S': 0.0,
'B': 0.0,
'M': 0.2777743117140081
}
}
P(λk∣ok):
{
"E": {
"怀": 9.578461281410872e-05,
"茂": 3.456888282012946e-05,
"耀": 1.8724811527570125e-05,
"涉": 0.00011955071975294772
},
"M": {
"耀": 0.00016042923733723116,
"茂": 0.00019608017896772698,
"怀": 0.00011140919259529943,
"涉": 3.565094163049582e-05,
"谈": 0.0012388702216597296,
"伊": 0.00045009313808500967
},
"B": {
"怀": 0.00016492237845436763,
"挂": 0.00013467460598675437,
"耀": 7.922035646279668e-06,
"涉": 0.00013539479104550706,
"谈": 0.0011897457170594555,
"伊": 0.000820290781919322
},
"S": {
"耀": 7.205344875136343e-05,
"挂": 0.00012919928741623787,
"怀": 0.00010870132354731551,
"涉": 2.857291933243722e-05,
"谈": 0.00032672512106221693,
"伊": 0.00032796742190275766
}
}
训练数据大家可以下载
训练数据
# coding=utf-8
import sys
class HMM(object):
def __init__(self):
"""
方法：初始化参数
"""
import os
# 主要是用于存取算法中间结果，不用每次都训练模型
self.model_file = './data/hmm_model.pkl'
# 状态值集合
self.state_list = ['B', 'M', 'E', 'S']
# 参数加载,用于判断是否需要重新加载model_file
self.load_para = False
def try_load_model(self, trained):
"""
方法：用于加载已计算的中间结果，当需要重新训练时，需初始化清空结果
输入：trained ：是否已经训练好
"""
if trained:
import pickle
with open(self.model_file, 'rb') as f:
self.A_dic = pickle.load(f)
self.B_dic = pickle.load(f)
self.Pi_dic = pickle.load(f)
self.load_para = True
else:
# 状态转移概率（状态->状态的条件概率）
self.A_dic = {}
# 发射概率（状态->词语的条件概率）
self.B_dic = {}
# 状态的初始概率
self.Pi_dic = {}
self.load_para = False
def train(self, path):
"""
方法：计算转移概率、发射概率以及初始概率
输入：path：训练材料路径
"""
# 重置几个概率矩阵
self.try_load_model(False)
# 统计状态出现次数，求p(o)
Count_dic = {}
# 初始化参数
def init_parameters():
for state in self.state_list:
self.A_dic[state] = {s: 0.0 for s in self.state_list}
self.Pi_dic[state] = 0.0
self.B_dic[state] = {}
Count_dic[state] = 0
def makeLabel(text):
"""
方法：为训练材料每个词划BMES
输入：text：一个词
输出：out_text:划好的一个BMES列表
"""
out_text = []
if len(text) == 1:
out_text.append('S')
else:
out_text += ['B'] + ['M'] * (len(text) - 2) + ['E']
return out_text
init_parameters()
line_num = -1
# 观察者集合，主要是字以及标点等
words = set()
with open(path, mode="r") as f:
for line in f:
line = line.decode("utf-8")
line_num += 1
line = line.strip()
if not line:
continue
word_list = [i for i in line if i != ' ']
words |= set(word_list) # 更新字的集合
linelist = line.split()
line_state = []
for w in linelist:
line_state.extend(makeLabel(w))
assert len(word_list) == len(line_state)
for k, v in enumerate(line_state):
Count_dic[v] += 1
if k == 0:
self.Pi_dic[v] += 1 # 每个句子的第一个字的状态，用于计算初始状态概率
else:
self.A_dic[line_state[k - 1]][v] += 1 # 计算转移概率
self.B_dic[line_state[k]][word_list[k]] = \
self.B_dic[line_state[k]].get(
word_list[k], 0) + 1.0 # 计算发射概率
self.Pi_dic = {k: v * 1.0 / line_num for k, v in self.Pi_dic.items()}
self.A_dic = {k: {k1: v1 / Count_dic[k] for k1, v1 in v.items()}
for k, v in self.A_dic.items()}
# 加1平滑
self.B_dic = {k: {k1: (v1 + 1) / Count_dic[k] for k1, v1 in v.items()}
for k, v in self.B_dic.items()}
# 序列化
import pickle
with open(self.model_file, 'wb') as f:
pickle.dump(self.A_dic, f)
pickle.dump(self.B_dic, f)
pickle.dump(self.Pi_dic, f)
return self
def viterbi(self, text, states, start_p, trans_p, emit_p):
"""
方法：维特比算法，寻找最优路径，即最大可能的分词方案
输入：text：文本
states：状态集
start_p：第一个字的各状态的可能
trans_p：转移概率
emit_p：发射概率
输出：prob:概率
path:划分方案
"""
V = [{}] # 路径图
path = {}
for y in states: # 初始化第一个字的各状态的可能性
V[0][y] = start_p[y] * emit_p[y].get(text[0], 0)
path[y] = [y]
for t in range(1, len(text)): # 每一个字
V.append({})
newpath = {}
# 检验训练的发射概率矩阵中是否有该字
neverSeen = text[t] not in emit_p['S'].keys() and \
text[t] not in emit_p['M'].keys() and \
text[t] not in emit_p['E'].keys() and \
text[t] not in emit_p['B'].keys()
for y in states: # 每个字的每个状态的可能
emitP = emit_p[y].get(
text[t], 0) if not neverSeen else 1.0 # 设置未知字单独成词
# y0上一个字可能的状态，然后算出当前字最可能的状态，prob则是最大可能，state是上一个字的状态
(prob, state) = max(
[(V[t - 1][y0] * trans_p[y0].get(y, 0) *
emitP, y0)
for y0 in states if V[t - 1][y0] > 0])
V[t][y] = prob
newpath[y] = path[state] + [y] # 更新路径
path = newpath
if emit_p['M'].get(text[-1], 0) > emit_p['S'].get(text[-1], 0): # 最后一个字是词中的可能大于单独成词的可能
(prob, state) = max([(V[len(text) - 1][y], y) for y in ('E', 'M')])
else: # 否则就直接选最大可能的那条路
(prob, state) = max([(V[len(text) - 1][y], y) for y in states])
return (prob, path[state])
# 用维特比算法分词，并输出
def cut(self, text):
import os
if not self.load_para:
self.try_load_model(os.path.exists(self.model_file))
prob, pos_list = self.viterbi(
text, self.state_list, self.Pi_dic, self.A_dic, self.B_dic)
begin, next = 0, 0
for i, char in enumerate(text):
pos = pos_list[i]
if pos == 'B':
begin = i
elif pos == 'E':
yield text[begin: i + 1]
next = i + 1
elif pos == 'S':
yield char
next = i + 1
if next < len(text):
yield text[next:]
hmm = HMM()
# hmm.train('./data/trainCorpus.txt_utf8')
text = u'南京市长江大桥'
res = hmm.cut(text)
# print(text.decode("utf-8"))
for item in res:
print item.encode("utf-8")
# print(str(list(res)))
jieba
这里提到比较常用的jieba分词，除了jieba含有比较常用的词典以外，jieba对于未登录词也是使用了HMM算法进行分词。
jieba有三种分词模式
- 精确模式：将句子精确切开，适合用于文本分析
- 全模式：把句子所有成词的词语全部扫描出来，速度快，但是不能解决歧义
- 搜索引擎模式：在精确模式的基础上，对长词再次切分，提高召回，适合用于搜索引擎。
import jieba
sent = '南京市长江大桥'
# 全模式
seg_list = jieba.cut(sent, cut_all=True)
print('/'.join(seg_list))
# 精确模式，默认
seg_list = jieba.cut(sent, cut_all=False)
print('/'.join(seg_list))
# 搜索引擎模式
seg_list = jieba.cut_for_search(sent)
print('/'.join(seg_list))
结果如下：
南京/南京市/京市/市长/长江/长江大桥/大桥
南京市/长江大桥
南京/京市/南京市/长江/大桥/长江大桥
分词数据