基于互信息和左右熵的新词发现算法——python实现

作者: 王同学死磕技术 | 来源:发表于2019-05-11 10:28 被阅读12次

新词发现
新词发现
python3实现互信息和左右熵的新词发现
基于互信息和左右熵的新词发现算法——python实现
基于Hanlp实现短语提取
左右熵互信息实现新词发现
Pyhanlp自然语言处理中的新词识别
互信息和左右熵的新词发现
基于互信息和左右信息熵的短语提取
短语抽取模型

今天笔者来介绍一下新词发现算法，顾名思义，新词发现算法饿的目的就是帮助我们发现新词。我们如果采用现在的分词技术，有时候一下生僻词或者专有词汇经常会被分错，而改进措施就是可以用新词算法发现预料中的新词，之后将发现的新词放到分词算法的用户自定义字典中，会增加分词的准确率。

而对于如何发现语料中的新词呢，这里笔者需要引入两个概念。

点间互信息（Pointwise Mutual Information）——凝固程度

首先我们来看一下点间互信息的公式，
$\operatorname{PMI}(x, y)=\log _{2} \frac{p(x, y)}{p(x) p(y)}$

其中 $p(x, y)$ 表示两个词一起出现的概率，而 $p(x)$ 和 $p(y)$ 表示各词出现的概率。举个例子，比如一份预料中，“深度学习”出现了10词，“深度”出现了15次，学习出现了“20”次。由于语料库总词数是个定值，那么深度学习这个词在“深度”，“学习”上的的点间互信息就为 $\log _{2} \frac{10}{15*20}$ 。

上述公式告诉我们：点间互信息越大，说明这两个词经常出现在一起，意味着两个词的凝固程度越大，其组成一个新词的可能性也就越大。

左右熵（Information Entropy）——自由程度

左（右）熵的公式如下，说白了其实就是信息熵的公式：
$E_{left}(PreW)=-\sum_{\forall Pre \subseteq A} P(PreW) \log _{2} P(PreW )$

上述公式PreW我们需要拆开看，Pre是W词前缀的集合。大家都知道信息熵是反应不确定程度的一个量，而这里引入信息熵是为了干嘛呢？这里笔者引用参考文献中的一个例子来说明：

在人人网用户状态中，“被子”一词一共出现了956次，“辈子”一词一共出现了2330次，。“被子”的左邻字用例非常丰富：用得最多的是“晒被子”，它一共出现了162次；其次是“的被子”，出现了85次；接下来分别是“条被子”、“在被子”、“床被子”，分别出现了69次、64次和52次；当然，还有“叠被子”、“盖被子”、“加被子”、“新被子”、“掀被子”、“收被子”、“薄被子”、“踢被子”、“抢被子”等100多种不同的用法构成的长尾。所有左邻字的信息熵为3.67453。但“辈子”的左邻字就很可怜了，2330个“辈子”中有1276个是“一辈子”，有596个“这辈子”，有235个“下辈子”，有149个“上辈子”，有32个“半辈子”，有 10个“八辈子”，有7个“几辈子”，有6个“哪辈子”，以及“n辈子”、“两辈子”等13种更罕见的用法。所有左邻字的信息熵仅为1.25963。因而，“辈子”能否成词，明显就有争议

看完例子我们发现被子左边词有100多种不同情况，显然其不确定性明显更大，在生活中我们也的确会大概率的把“被子”当初一个词来用。所以我们大致可以得到：左右熵值越大，说明该词的周边词越丰富，意味着词的自由程度越大，其成为一个独立的词的可能性也就越大。

新词发现算法实战

这里新词发现算法的算法逻辑主要分为三个步骤：

将语料文本转换成一个字符串，然后一个生成n_ gram的词典，并统计个词的词频。
利用点间互信息从之前的n_gram 词典中筛选出备选的新词。
在通过左右熵从备选新词中筛选出最终输出的新词。

下方用python定义了一些计算互信息和左右熵的方法。

from collections import Counter
import numpy as np
import re 

def n_gram_words(text,n_gram):
    """
    To get n_gram word frequency dict
    input: str of the chinese sentence ，int of n_gram 
    output: word frequency dict
    
    """
    words = []
    for i in range(1,n_gram+1):
        words += [text[j:j+i] for j in range(len(text)-i+1)]
    words_freq = dict(Counter(words))    
    return words_freq      

def PMI_filter(word_freq_dic,min_p):
    """
    To get words witch  PMI  over the threshold
    input: word frequency dict , min threshold of PMI
    output: condinated word list
    
    """
    new_words = []
    for word in word_freq_dic:
        if len(word) == 1:
            pass
        else:
            p_x_y = min([word_freq_dic.get(word[:i])* word_freq_dic.get(word[i:]) for i in range(1,len(word))])
            mpi = p_x_y/word_freq_dic.get(word)
            if mpi > min_p:
                new_words.append(word)
    return new_words

def calculate_entropy(char_list):
    """
    To calculate entropy for  list  of char
    input: char list 
    output: entropy of the list  of char
    """
    char_freq_dic =  dict(Counter(char_list)) 
    entropy = (-1)*sum([ char_freq_dic.get(i)/len(char_list)*np.log2(char_freq_dic.get(i)/len(char_list)) for i in char_freq_dic])
    return entropy


def Entropy_left_right_filter(condinate_words,text,min_entropy):
    """
    To filter the final new words from the condinated word list by entropy threshold
    input:  condinated word list ,min threshold of Entropy of left or right
    output: final word list
    """
    final_words = []
    for word in condinate_words:
        try:
            left_right_char =re.findall('(.)%s(.)'%word,text)

            left_char = [i[0] for i in left_right_char] 
            left_entropy = calculate_entropy(left_char)

            right_char = [i[1] for i in left_right_char]
            right_entropy = calculate_entropy(right_char)

            if min(right_entropy,left_entropy)> min_entropy:
                final_words.append(word)
        except:
            pass
    return final_words

接下来笔者用下方测试语料去进行新词发现

测试语料

接下来运行下方代码：首先处理好语料后，然后设置好互信息的最小阈值min_p = 4 ,左右熵的最小阈值min_e = 2后，最后通过凝固程度和自由程度逐级筛选新词。

# read the data and preprocessing the data to a whole str
stop_word=['【','】',')','(','、','，','“','”','。','\n','《','》',' ','-','！','？','.','\'','[',']','：','/','.','"','\u3000','’','．',',','…','?']
with open("test.txt") as f:
    text = f.read()
for i in stop_word:
    text=text.replace(i,"")

# finding the new words 
min_p = 4
min_e = 2
n_gram = n_gram_words(text,min_p)
condinate = PMI_filter(n_gram ,min_e )
final = Entropy_left_right_filter(condinate,text,1)


print(final)

得到的新词，结果如下，其实还是发现很多特殊词语，比如“蔡英文”，“蔡英文”，“台当局”等，说明新词发现算法确实起作用了。