新词发现 基于python的理论与实现

2019.5.25 - 5.29 前言如何成词成词标准之一 —— 内部凝固程度成词标准之二：自由运用程度结论 代码块思想切词构建字典树节点字典树构建字典树，生成根节点rootTrieNode.add方法，向根节点中添加子节点TrieNode.search_right方法，统计右频次，返回*右信息熵* 集合。TrieNode.search_left方法，统计左熵， 并返回*左信息熵* 集合TrieNode.search_bi方法,计算新词内部凝固程度 GitHub地址 结语

2019.5.25 - 5.29

前言

生活中，有很多年度流行词，这些年度流行词依靠人为的判断很容易就能辨别，但是人的精力毕竟是有限的，利用python代码发现新词，不仅可以发现新词，只要语料库够大，甚至还可以找到年度网络流行语。

如何成词

成词标准之一 —— 内部凝固程度

我们可以想象一篇文本就是很长的一个字符串，我们需要在文本中找到新词，就是把一个很长的字符串分解成若干短的字符串，判断这个字符串出现次数的多少，出现的次数多并且没有在我们现有的词库中出现，我们就可把这个词想象成是一个新词。在对现有文本分析的时候发现， “图书馆” 出现了116次， “学校的” 出现了312次，然而我们却更倾向于把“图书馆”当作一个词，因为直觉上“图书”和“馆”凝固程度更好。 为了证明机器也可以和人脑一样进行这样判断，我们可以计算一下，在整整1295万的分词数据中，“图书”一共出现了1523次，出现的概率为0.0001176062，“馆”一共出现了3512次，出现的概率为0.0002711969，假设这两词毫无关系，那么两者组合在一起的概率就是P（预测1） = 0.00011760620.0002711969，约为3.1894e-8，但是“图书馆”出现的概率为8.9575e-6，是预测的280倍，。“的”字出现了13.58万次，概率为0.0104864865，“学校”出现的次数为3184次，概率为0.0002458687，得出 P（预测2） = 2.5786e-6，“学校的”出现的概率为2.4092e-5，是预测值的9.3倍。计算结果表明，“图书馆”应该是一个更让人信服的搭配，而“学校的”则更像是“学校”和“的”这两个成分偶然拼到一起的。 当然，作为一个刚开始没有任何语料库的抽词程序，我们并不知道“图书馆”是“图书”加“馆”拼接而来的，还是“图”加“书馆”拼接而来的，或许我们用“图”加“书馆”拼接而算的的概率可能会更大。因此，为了算出一个字符串的凝固程度，我们需要枚举这个字符串是由哪两部分组合而来的。令p(x)为文本片段x在整个语料中出现的概率，那么我们定义“图书馆”的凝固程度就是p(图书馆)与p(图)·p(书馆)的比值和p(图书馆)与p(图书)·p(馆)的比值中的较小值。

成词标准之二：自由运用程度

光看字符串内部的凝合程度还不够，我们还需要从整体来看它在外部的表现。考虑“杯子”和“辈子”这两个字符串。我们可以说“买杯子”、“拿杯子”、“好杯子”、“这杯子”、“玻璃杯子”等，在“杯子”前面加各种字；但“辈子”的用法却比较固定，除了“几辈子”、“这辈子”、“上辈子”、“下辈子”，基本上 “辈子”前面不能加别的字了。“辈子”这个文本片段左边可以出现的字太有限，以至于视觉上我们可能会认为，“辈子”并不单独成词，真正成词的其实是“几辈子”、“这辈子”之类的整体。可见，文本片段的自由运用程度也是判断它是否成词的重要标准。如果一个文本片段能够算作一个词的话，它应该能够灵活地出现在各种不同的文本片段中，具有非常丰富的左邻字集合和右邻字集合。 　信息熵是一个很神奇的概念，意外越大，越不可能发生，概率就越小，信息量也就越大，也就是信息越多。比如说“太阳从东边升起”，实现概率100%，说了和没说差不多，信息量就是0。  信息量= log2(1/概率)=log2(概率^-1)=-log2(概率)，log2是以2为底的对数。  举个例子：一个骰子6面有五面为1,一面为5，投掷一次，出现为1，你或许不那么吃惊，它带给你的信息量为 log2(6/5) = 0.2630。但如果出现5，它所带给你的信息量就为log2(6/1) = 2.5849，但你只有1/6的概率得到这个结果。因而平均情况下你可以得到 50.2630 + 12.5849 = 3.8999的信息量。再考虑一个最极端的情况：如果一颗骰子的六个面都是1，投掷它不会给你带来任何信息，它的信息熵为-log2(1)=0。什么时候 信息熵会更大呢？换句话说，发生了怎样的事件之后，你最想问一下它的结果如何？直觉上看，当然就是那些结果最不确定的事件。  考虑下面一段话：“吃葡萄不吐葡萄皮儿，不吃葡萄倒吐葡萄皮儿”，“葡萄”一次一共出现了4次，其中左邻字集合为{“吃”，“吐”，“吃”，“吐”}，右邻字集合为{“不”，“皮”，“倒”，“皮”}，根据公式，“葡萄”一词的左邻字的信息熵为 2log2(2) + 2log2(2) = 4.000，右邻字的信息熵为 log2(4) + 2*log2(2) + log2(4) = 6.000，可见葡萄的右邻字更丰富一些。事实上，只要合适，葡萄的右邻字可以为任意字。所以不妨定义一个字符串的自由运用程度为它的左、右信息熵的较小值。

结论

在实际运用中你会发现，字符串的凝固程度和自由程度，两种判断标准缺一不可。只看凝固程度的话，程序会找出“巧克”、“俄罗”、“颜六色”、“柴可夫”等实际上是“半个词”的字符串片段；只看自由程度的话，程序则会把“吃了一 顿”、“看了一遍”、“睡了一晚”、“去了一趟”中的“了一”提取出来，因为它的左右邻字都太丰富了。

代码块

思想

首先，分词之后，构建字典树，然后，根据计算，得出内部凝固程度和自由运用程度，最后根据内部凝固程度和自由运用程度，算出得分，当得分超过阈值时得到新词。

切词

import jieba def loadDate(fileName, stopwords): # 加载数据集 data = [] with open(fileName, 'r', encoding='utf-8') as f: lines = f.readlines() for line in lines: line = line.strip() line = [x for x in jieba.cut(line, cut_all=False) if x not in stopwords] data.append(line) # 按照行进行切分句子，得到一个数组 # [[行，切词], [], []] # print(data) #[['台湾', '中', '时', '电子报', '26', '日', '报道', '称', '蔡', '英文', '今日', '一早', '会见', '世卫', '行 动', '团', '她', '称', '台湾', '虽然', '无法', '参加', 'WHA', '世界卫生', '大会', '但', '还是', '要', '有', '贡献', '于是', '她', '表示', '要', '捐', '100', '万美元', '给', 'WHO', '对抗', '埃', '博拉', '病毒'], #['对于', '台湾', '为何', '不能', '蔡', '英文', '又', '一次', '惯性', '甩锅', '宣称', '中国', '对', '台湾', ' 外交', '打压', '已', '无所不用其极'], #['不过', '环环', '想', '提醒', '一句', '此次', '大会', '上', '确实', '有', '多个', '台湾', '友邦', '受', '台当局', '邀请', '向', '大会', '提案', '邀请', '台湾', '作为', '观察员', '参加', 'WHA', '然而', '结果', '是', '立即', '被', '大会', '否决'], #[]] return data

loadDate接收文件名和停用词文件名

构建字典树

节点

直接看代码，后面具体解释用法

class Node: """ 建立字典树的节点 """ def __init__(self, char): self.char = char#存放节点字符串 self.word_finish = False#记录到当前节点时候可生成一个词 self.count = 0#计数 self.child = {}#存放孩子节点 {"char":Node} self.isback = False#判断是否是左邻接字

字典树

构建字典树，生成根节点root

class TrieNode: """ 建立前缀树，并且包含统计词频，计算左右熵，计算互信息的方法 """ def __init__(self, node, data=None, PMI_limit=20): """ 初始函数，data为外部词频数据集 :param node: :param data: 建立初始字典树 """ self.root = Node(node)#构建字典树的根节点 self.PMI_limit = PMI_limit#这里的PMI_limit就是设置的初始阈值，可根据需要自行调整 """ 这里的data，可不传，这里只是我需要用到已有的数据， 所以构建root节点之后我还需要将我原有的数据导入进去 """ if not data: return node = self.root for key, values in data.items(): new_node = Node(key) new_node.count = int(values) new_node.word_finish = True node.child[key]=new_node

TrieNode.add方法，向根节点中添加子节点

def add(self, word): """ 添加节点，对于左熵计算时，这里采用了一个trick，用a->b<-c 来表示 cba 具体实现是利用 self.isback 来进行判断 :param word: :return: 增加节点 """ node = self.root # 正常加载 for count, char in enumerate(word): found_in_child = False # 在节点中找字符 if node.child.get(char)!=None: node = node.child.get(char) found_in_child = True else: new_node = Node(char) node.child[char]=new_node node = new_node # 判断是否是最后一个词 if count == len(word) - 1: node.count += 1#到此节点可构成新词,考虑到之前就已经构成，所以为count += 1 node.word_finish = True # 建立后缀表示 """ 寻找左邻接字 ["我","是","瓜皮"]转化为["是","瓜皮","我"],这样， 方便我们的寻找字符串“是瓜皮”的左邻接字“我”。 “是” --->“瓜皮” --->“我”。 建立分叉之后，设置“我”子节点的word_finish = True,isback = True,count += 1。 """ length = len(word) node = self.root if length == 3: word[0], word[1], word[2] = word[1], word[2], word[0] for count, char in enumerate(word): found_in_child = False # 在节点中找字符 if count != length - 1: if node.child.get(char)!=None: node = node.child.get(char) found_in_child = True else: if node.child.get(char)!=None and node.child.get(char).isback: node = node.child.get(char) found_in_child = True if not found_in_child: new_node = Node(char) node.child[char]=new_node node = new_node # 判断是否是最后一个节点 if count == len(word) - 1: node.count += 1 node.isback = True#左邻接字 node.word_finish = True

TrieNode.search_one方法，寻找一阶共现，并返回所有词概率和词总和

def search_one(self): """ 寻找一阶共现，并返回所有词概率 对于：["我"，"爱"，"你"，"我"，"是"，"你"，"哥哥"] result: {"我":0.2857142857142857，"你":0.2857142857142857,"爱":0.14285714285714285, "是":0.14285714285714285,"哥哥":0.14285714285714285} total: 7 :return: """ result = {} node = self.root if not node.child: return False, 0 total = 0 for child in node.child.values(): if child.word_finish == True: total += child.count for child in node.child.values(): if child.word_finish == True: result[child.char] = child.count / total return result, total

TrieNode.search_right方法，统计右频次，返回右信息熵 集合。

def search_right(self): """ 寻找右频次 统计右熵，并返回右熵 :return: """ result = {} node = self.root if not node.child: return False, 0 for child in node.child.values(): for cha in child.child.values(): total = 0 p = 0.0 for ch in cha.child.values(): if ch.word_finish == True and not ch.isback: total += ch.count for ch in cha.child.values(): if ch.word_finish == True and not ch.isback: p += (ch.count / total) * math.log(ch.count / total, 2) result[child.char + cha.char] = -p return result

TrieNode.search_left方法，统计左熵， 并返回左信息熵 集合

def search_left(self): """ 寻找左频次 统计左熵， 并返回左熵 :return: """ result = {} node = self.root if not node.child: return False, 0 for child in node.child.values(): for cha in child.child.values(): total = 0 p = 0.0 for ch in cha.child.values(): if ch.word_finish == True and ch.isback: total += ch.count for ch in cha.child.values(): if ch.word_finish == True and ch.isback: p += (ch.count / total) * math.log(ch.count / total, 2) result[child.char + cha.char] = -p return result

TrieNode.search_bi方法,计算新词内部凝固程度

def search_bi(self): """ 寻找二阶共现，并返回log2( P(X,Y) / (P(X) * P(Y))和词概率 :return: """ result = {} node = self.root if not node.child: return False, 0 total = 0 one_dict, total_one = self.search_one() for child in node.child.values(): for ch in child.child.values(): if ch.word_finish == True: total += ch.count for child in node.child.values(): for ch in child.child.values(): if ch.word_finish == True : PMI = math.log(max(ch.count, 1), 2) - math.log(total, 2) - math.log(one_dict[child.char], 2) - math.log( one_dict[ch.char], 2) # 这里做了PMI阈值约束 if PMI > self.PMI_limit: result[child.char + '_' + ch.char] = (PMI, ch.count / total) return result

TrieNode.wordFind方法,统计内部凝固程度，左右熵，计算新词得分，根据得分筛选新词

def wordFind(self, N): # 通过搜索得到内部凝固程度（互信息） bi = self.search_bi() # 通过搜索得到左右熵 left = self.search_left() right = self.search_right() result = {} for key, values in bi.items(): d = "".join(key.split('_')) # 计算公式 score = PMI + min(左熵， 右熵) result[key] = (values[0] + min(left[d], right[d])) * values[1] result = sorted(result.items(), key=lambda x: x[1], reverse=True) dict_list = [result[0][0]] add_word = {} new_word = "".join(dict_list[0].split('_')) # 获得概率 add_word[new_word] = result[0][1] # 取前N个 for d in result[1:N]: flag = True for tmp in dict_list: pre = tmp.split('_')[0] if d[0].split('_')[-1] == pre or "".join(tmp.split('_')) in "".join(d[0].split('_')): flag = False break if flag: new_word = "".join(d[0].split('_')) add_word[new_word] = d[1] dict_list.append(d[0]) return result, OrderedDict(sorted(add_word.items(),key = lambda t:t[1],reverse=True))

GitHub地址

戳我

结语

感谢F哥给我这次接触新词发现的机会，欢迎各位大佬提出意见、指出不足与错误。