双向最大匹配和实体标注：你以为我只能分词？
source link: http://mp.weixin.qq.com/s?__biz=MjM5ODkzMzMwMQ%3D%3D&%3Bmid=2650412895&%3Bidx=5&%3Bsn=bb31cbe78a66b9d9a39b62e4bf3445cd
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
一 ：内容预告
前几天，我看了叉烧同学写的文章：
文章介绍了一种实体自动打标的方法： 实体词典+最大逆向匹配 。
啥叫实体打标呢？
举叉烧同学文章里的例子，有一句话：宫保鸡丁和红烧牛肉哪个好吃， 我们需要给句子中的两个实体 [宫保鸡丁, 红烧牛肉] 打上 Food 标签，非实体打上 O 标签。
做法是，首先准备一个实体词典，实体词典包含这两个实体在内的食物名，然后用这个词典和最大逆向匹配算法，给实体打标签。
打好标签的句子，可以直接作为实体提取的最终结果，也可以作为训练实体识别模型的样本。
用于构造样本时，打标签的结果如下：
""" 1：句子 """
宫保鸡丁和红烧牛肉哪个好吃
""" 2：标注结果 """
宫 B-Food
保 I-Food
鸡 I-Food
丁 I-Food
和 O
红 B-Food
烧 I-Food
牛 I-Food
肉 I-Food
哪 O
个 O
好 O
吃 O
我之前也做过实体自动打标签的活，不过用的方法是： 实体词典+jieba词性标注 。
jieba词性标注应该用到了双向最大匹配，所以其实我之前做的，就是掉包实现了以上打标的方法。
这次准备了一个医疗实体词典（带标签）和若干医疗文本，用python实现双向最大匹配算法，并结合实体词典进行实体自动打标，作为训练实体识别模型的样本。
同时也整理了 实体词典+jieba词性标注 进行实体自动打标的方法。
代码已上传github地址：
https://github.com/DengYangyong/medical_entity_recognize
本文主要关注以下四方面的内容：
-
双向最大匹配算法的思路
-
双向最大匹配算法的代码实现
-
实体词典+双向最大匹配算法做实体打标
-
实体词典+jieba词性标注做实体打标
二：双向最大匹配算法
前向最大匹配算法和后向最大匹配算法是基于规则（词典）的分词方法，二者按照一定的规则结合使用，就是双向最大匹配算法。
双向最大匹配算法不仅可以用于分词，也可以用于序列标注，速度快且准确率高，不会分出奇怪的词或实体，但也难以正确处理未登录词。
由于完全依赖词典，通用性不强，所以比较适用于处理具体领域的任务，比如医疗领域。
01
前向最大匹配算法
首先拿到一个词典，比如实体词典，每一行是一个实体和对应的标签：
""" 词典（包含：实体和标签） """
肾抗针,DRU
肾囊肿,DIS
肾区,REG
肾上腺皮质功能减退症,DIS
肾性高血压,DIS
肾性贫血,DIS
肾血管,ORG
肾脏,ORG
伴脓性渗出,NBP
生理反射存在,NBP
然后计算词典中实体的最大长度，作为截取句子片段的最大长度。
为什么叫最大匹配呢？
对句子进 行分词和标注的一个 原则是： 单个词（实体）的长度尽可能大。 所以会先按最大长度从句子中截取片段，去词典中匹配，匹配中了，就切分出来。
按最大长度匹配不中，那么最大长度减一，再去截取句子片段，去词典中匹配，直到匹配中，或者截取的长度减小至一。
为什么叫前向呢？
前向的意思是，从句子中截取片段是从左向右进行的。
更多的细节，来看一个例子。
患者的电子病历上写着：我最近双下肢疼痛，我该咋办。
句子中有个两个实体，出现在实体词典中：双下肢疼痛、疼痛。
句子的长度为14（包括标点符号），实体词典中的最大长度为10。
第一轮遍历未匹配中，把第一个字切分出来：[我]。
第二轮遍历未匹配中，把第二个字切分出来：[我，最]。
第四轮遍历，匹配中了[双下肢疼痛]，就把这个实体从句子中剔除，拿剩下的句子继续匹配。
最终的实体打标结果为：
可以看到，[疼痛] 这个实体没有被匹配出来，因为[双下肢疼痛]的粒度更大，表达的含义更明确，这也是最大匹配的意义。
前向最大匹配的python实现如下：
#coding:utf-8
import pandas as pd
class PsegMax:
def __init__(self, dict_path):
self.entity_dict, self.max_len = self.load_entity(dict_path)
def load_entity(self, dict_path):
"""
加载实体词典
"""
entity_list = []
max_len = 0
""" 实体词典: {'肾抗针': 'DRU', '肾囊肿': 'DIS', '肾区': 'REG', '肾上腺皮质功能减退症': 'DIS', ...} """
df = pd.read_csv(dict_path,header=None,names=["entity","tag"])
entity_dict = {entity.strip(): tag.strip() for entity,tag in df.values.tolist()}
""" 计算词典中实体的最大长度 """
df["len"] = df["entity"].apply(lambda x:len(x))
max_len = max(df["len"])
return entity_dict, max_len
def max_forward_seg(self, sent):
"""
前向最大匹配实体标注
"""
words_pos_seg = []
sent_len = len(sent)
while sent_len > 0:
""" 如果句子长度小于实体最大长度，则切分的最大长度为句子长度 """
max_len = min(sent_len,self.max_len)
""" 从左向右截取max_len个字符，去词典中匹配 """
sub_sent = sent[:max_len]
while max_len > 0:
""" 如果切分的词在实体词典中，那就是切出来的实体 """
if sub_sent in self.entity_dict:
tag = self.entity_dict[sub_sent]
words_pos_seg.append((sub_sent,tag))
break
elif max_len == 1:
""" 如果没有匹配上，那就把单个字切出来，标签为O """
tag = "O"
words_pos_seg.append((sub_sent,tag))
break
else:
""" 如果没有匹配上，又还没剩最后一个字，就去掉右边的字,继续循环 """
max_len -= 1
sub_sent = sub_sent[:max_len]
""" 把分出来的词（实体或单个字）去掉，继续切分剩下的句子 """
sent = sent[max_len:]
sent_len -= max_len
return words_pos_seg
02
后向最大匹配算法
后向的意思是，从句子中截取片段是从右往左进行的。
还是来看上面的那个例子。
第一轮遍历未匹配中，把最后一个字切分出来：[。]。
第二轮遍历未匹配中，把倒数第二个字切分出来：[办，。]。
直到第七轮遍历， 匹配中了[双下肢疼痛]，就把这个实体从句子中剔除，拿剩下的句子继续匹配。
最终的实体打标结果和前向最大匹配的结果一致。
这个例子没反映出前向最大匹配和后向最大匹配的差别，感觉在实体标注这一块，二者的结果差别不大。
有资料统计，在分词时，仅使用前向最大匹配的错误率为 1/169，而使用后向最大匹配的错误率为 1/245，可见使用后向最大匹配可以提高分词或标注的准确率。
后向最大匹配的python实现如下：
#coding:utf-8
import pandas as pd
class PsegMax:
def __init__(self, dict_path):
self.entity_dict, self.max_len = self.load_entity(dict_path)
def load_entity(self, dict_path):
"""
加载实体词典
"""
def max_forward_seg(self, sent):
"""
前向最大匹配实体标注
"""
def max_backward_seg(self, sent):
"""
后向最大匹配实体标注
"""
words_pos_seg = []
sent_len = len(sent)
while sent_len > 0:
""" 如果句子长度小于实体最大长度，则切分的最大长度为句子长度 """
max_len = min(sent_len,self.max_len)
""" 从右向左截取max_len个字符，去词典中匹配 """
sub_sent = sent[-max_len:]
while max_len > 0:
""" 如果切分的词在实体词典中，那就是切出来的实体 """
if sub_sent in self.entity_dict:
tag = self.entity_dict[sub_sent]
words_pos_seg.append((sub_sent,tag))
break
elif max_len == 1:
""" 如果没有匹配上，那就把单个字切出来，标签为O """
tag = "O"
words_pos_seg.append((sub_sent,tag))
break
else:
""" 如果没有匹配上，又还没剩最后一个字，就去掉右边的字,继续循环 """
max_len -= 1
sub_sent = sub_sent[-max_len:]
""" 把分出来的词（实体或单个字）去掉，继续切分剩下的句子 """
sent = sent[:-max_len]
sent_len -= max_len
""" 把切分的结果反转 """
return words_pos_seg[::-1]
03
双向最大匹配算法
双向最大匹配就是，将前向最大匹配的切分结果，和后向最大匹配的结果进行比较，按一定的规则选择其一作为最终的结果。
按照什么规则来选择呢？
（1）如果前向和后向切分结果的词数不同，则取词数较少的那个。
（2）如果词数相同 ：
-
切分结果相同，则返回任意一个；
-
切分结果不同，则返回单字较少的那个。
网上看到一个非常好的例子，前向和后向切分后，词数相同，结果不同，返回单字少的那个结果（例子中为后向最大匹配）。
双向最大匹配的python实现如下：
#coding:utf-8
import pandas as pd
class PsegMax:
def __init__(self, dict_path):
self.entity_dict, self.max_len = self.load_entity(dict_path)
def load_entity(self, dict_path):
def max_forward_seg(self, sent):
def max_backward_seg(self, sent):
def max_biward_seg(self, sent):
"""
双向最大匹配实体标注
"""
""" 1: 前向和后向的切分结果 """
words_psg_fw = self.max_forward_seg(sent)
words_psg_bw = self.max_backward_seg(sent)
""" 2: 前向和后向的词数 """
words_fw_size = len(words_psg_fw)
words_bw_size = len(words_psg_bw)
""" 3: 前向和后向的词数，则取词数较少的那个 """
if words_fw_size < words_bw_size: return words_psg_fw
if words_fw_size > words_bw_size: return words_psg_bw
""" 4: 结果相同，可返回任意一个 """
if words_psg_fw == words_psg_bw: return words_psg_fw
""" 5: 结果不同，返回单字较少的那个 """
fw_single = sum([1 for i in range(words_fw_size) if len(words_psg_fw[i][0])==1])
bw_single = sum([1 for i in range(words_fw_size) if len(words_psg_bw[i][0])==1])
if fw_single < bw_single: return words_psg_fw
else: return words_psg_bw
if __name__ == "__main__":
dict_path = "medical_ner_dict.csv"
text = "我最近双下肢疼痛，我该咋办。"
psg = PsegMax(dict_path)
words_psg = psg.max_biward_seg(text)
print(words_psg)
最终的实体打标结果为：
三：实体自动标注
接下来就两种方法来做实体自动打标，构造训练实体识别模型的样本。
一是用：实体词典+双向最大匹配，
二是用：实体词典+jieba词性标注。
01
jieba加载词典
医疗实体词典的格式如下，每一行是实体词和对应的标签：
肾抗针,DRU
肾囊肿,DIS
肾区,REG
肾上腺皮质功能减退症,DIS
肾性高血压,DIS
肾性贫血,DIS
肾血管,ORG
肾脏,ORG
伴脓性渗出,NBP
生理反射存在,NBP
未标注的电子病历内容如下：
首先导入必要的包，max_seg.py 就是上面写好的双向最大匹配算法。
#encoding=utf8
import os,jieba,csv,random,re
import jieba.posseg as psg
from max_seg import PsegMax
""" 医疗实体词典, 每一行类似：(视力减退,SYM) """
dict_path = "medical_ner_dict.csv"
psgMax = PsegMax(dict_path)
c_root = os.getcwd() + os.sep + "source_data" + os.sep
""" 实体类别 """
biaoji = set(['DIS', 'SYM', 'SGN', 'TES', 'DRU', 'SUR', 'PRE', 'PT', 'Dur', 'TP', 'REG', 'ORG', 'AT', 'PSB', 'DEG', 'FW','CL'])
""" 句子结尾符号，表示如果是句末，则换行 """
fuhao = set(['。','?','？','!','！'])
然后把医疗实体和标签加载到jieba中，同时为了保证由多个词组成的实体不被切开，我们为实体设置较高的权重。
def add_entity(dict_path):
"""
把实体字典加载到jieba里，
实体作为分词后的词，
实体标记作为词性
"""
dics = csv.reader(open(dict_path,'r',encoding='utf8'))
for row in dics:
if len(row)==2:
jieba.add_word(row[0].strip(),tag=row[1].strip())
""" 保证由多个词组成的实体词，不被切分开 """
jieba.suggest_freq(row[0].strip())
我们可以选择用jieba还是双向最大匹配来标注。
def sentence_seg(sentence,mode="jieba"):
"""
1: 实体词典+jieba词性标注。mode="jieba"
2: 实体词典+双向最大匹配。mode="max_seg"
"""
if mode == "jieba": return psg.cut(sentence)
if mode == "max_seg": return psgMax.max_biward_seg(sentence)
我们来看实体标注（词性标注）的效果：
sentence = "我最近双下肢疼痛。"
""" 1: 不加词典的jieba词性标注 """
[pair('我', 'r'), pair('最近', 'f'), pair('双下肢', 'n'), pair('疼痛', 'n'), pair('。', 'x')]
""" 2: 加词典的jieba词性标注 """
[pair('我', 'r'), pair('最近', 'f'), pair('双下肢疼痛', 'SYM'), pair('。', 'x')]
""" 3: 双向最大匹配的标注 """
[('我', 'O'), ('最', 'O'), ('近', 'O'), ('双下肢疼痛', 'SYM'), ('。', 'O')]
02
样本自动标注
这次一共有100篇电子病历，我们按7:2:1的比例划分为训练集、验证集和测试集。
def split_dataset():
"""
划分数据集，按照7:2:1的比例
"""
file_all = []
for file in os.listdir(c_root):
if "txtoriginal.txt" in file:
file_all.append(file)
random.seed(10)
random.shuffle(file_all)
num = len(file_all)
train_files = file_all[: int(num * 0.7)]
dev_files = file_all[int(num * 0.7):int(num * 0.9)]
test_files = file_all[int(num * 0.9):]
return train_files,dev_files,test_files
然后进行样本自动标注，采用的实体标注格式为BIO。
BIO格式就是说，对于实体词，第一个字标注为B，其他的字标注为I；对于非实体词，每个字都标注为O。
还有一个小细节是句与句之间要留空格。
例子如下：
我 O
最 O
近 O
双 B-SYM
下 I-SYM
肢 I-SYM
疼 I-SYM
痛 I-SYM
。 O
怎 O
么 O
办 O
？ O
我们把每个字的标注结果，作为一行，写入到文件中。
代码实现如下：
def auto_label(files, data_type, mode="jieba"):
"""
不是实体，则标记为O，
如果是句号等划分句子的符号，则再加换行符，
是实体，则标记为BI。
"""
writer = open("example.%s" % data_type,"w",encoding="utf8")
for file in files:
fp = open(c_root+file,'r',encoding='utf8')
for line in fp:
""" 按词性分词 """
words = sentence_seg(line,mode)
for word,pos in words:
word,pos = word.strip(), pos.strip()
if not (word and pos):
continue
""" 如果词性不是实体的标记，则打上O标记 """
if pos not in biaoji:
for char in word:
string = char + ' ' + 'O' + '\n'
""" 在句子的结尾换行 """
if char in fuhao:
string += '\n'
writer.write(string)
else:
""" 如果词性是实体的标记，则打上BI标记"""
begin = 0
for char in word:
if begin == 0:
begin += 1
string = char + ' ' + 'B-' + pos + '\n'
else:
string = char + ' ' + 'I-' + pos + '\n'
writer.write(string)
writer.close()
def main():
""" 1: 加载实体词和标记到jieba """
add_entity(dict_path)
""" 2: 划分数据集 """
trains, devs, tests = split_dataset()
""" 3: 自动标注样本 """
for files, data_type in zip([trains,devs,tests],["train","dev","test"]):
auto_label(files, data_type,mode="max_seg")
if __name__ == "__main__":
main()
标注好的样本的部分内容如下：
部 O
分 O
脱 O
痂 O
。 O
双 B-ORG
侧 I-ORG
瞳 I-ORG
孔 I-ORG
正 O
大 O
等 O
圆 O
哈哈，感觉很多人都是用医疗领域的数据来学习实体识别，是因为在其他领域做实体识别的效果不好吗？
五月份要认真整理一下实体识别的模型，不然就是个假NLPer。
祝大家五一节快乐啊！
推荐阅读
太赞了！Springer面向公众开放电子书籍，附65本数学、编程、机器学习、深度学习、数据挖掘、数据科学等书籍链接及打包下载
深度学习如何入门？这本“蒲公英书”再适合不过了！豆瓣评分9.5!【文末双彩蛋！】
斯坦福大学NLP组Python深度学习自然语言处理工具Stanza试用
数学之美中盛赞的 Michael Collins 教授，他的NLP课程要不要收藏？
From Word Embeddings To Document Distances 阅读笔记
模型压缩实践系列之——bert-of-theseus，一个非常亲民的bert压缩方法
可解释性论文阅读笔记1-Tree Regularization
关于AINLP
AINLP 是一个有趣有AI的自然语言处理社区，专注于 AI、NLP、机器学习、深度学习、推荐算法等相关技术的分享，主题包括文本摘要、智能问答、聊天机器人、机器翻译、自动生成、知识图谱、预训练模型、推荐系统、计算广告、招聘信息、求职经验分享等，欢迎关注！加技术交流群请添加AINLPer(id：ainlper)，备注工作/研究方向+加群目的。
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK