今天筆者來介紹一下新詞發(fā)現(xiàn)算法，顧名思義，新詞發(fā)現(xiàn)算法餓的目的就是幫助我們發(fā)現(xiàn)新詞。我們?nèi)绻捎矛F(xiàn)在的分詞技術(shù)，有時候一下生僻詞或者專有詞匯經(jīng)常會被分錯，而改進(jìn)措施就是可以用新詞算法發(fā)現(xiàn)預(yù)料中的新詞，之后將發(fā)現(xiàn)的新詞放到分詞算法的用戶自定義字典中，會增加分詞的準(zhǔn)確率。

而對于如何發(fā)現(xiàn)語料中的新詞呢，這里筆者需要引入兩個概念。

點間互信息（Pointwise Mutual Information）——凝固程度

首先我們來看一下點間互信息的公式，

其中表示兩個詞一起出現(xiàn)的概率，而和表示各詞出現(xiàn)的概率。舉個例子，比如一份語料中，“深度學(xué)習(xí)”出現(xiàn)了10詞，“深度”出現(xiàn)了15次，學(xué)習(xí)出現(xiàn)了“20”次。由于語料庫總詞數(shù)是個定值，那么深度學(xué)習(xí)這個詞在“深度”，“學(xué)習(xí)”上的的點間互信息就為 。其中N指總詞數(shù)。

上述公式告訴我們：點間互信息越大，說明這兩個詞經(jīng)常出現(xiàn)在一起，意味著兩個詞的凝固程度越大，其組成一個新詞的可能性也就越大。

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

左（右）熵的公式如下，說白了其實就是信息熵的公式：

上述公式PreW我們需要拆開看，Pre是W詞前綴的集合。大家都知道信息熵是反應(yīng)不確定程度的一個量，而這里引入信息熵是為了干嘛呢？這里筆者引用參考文獻(xiàn)中的一個例子來說明：

在人人網(wǎng)用戶狀態(tài)中，“被子”一詞一共出現(xiàn)了956次，“輩子”一詞一共出現(xiàn)了2330次，?！氨蛔印钡淖筻徸钟美浅ＸS富：用得最多的是“曬被子”，它一共出現(xiàn)了162次；其次是“的被子”，出現(xiàn)了85次；接 下來分別是“條被子”、“在被子”、“床被子”，分別出現(xiàn)了69次、64次和52次；當(dāng)然，還有“疊被子”、“蓋被子”、“加被子”、“新被子”、“掀被 子”、“收被子”、“薄被子”、“踢被子”、“搶被子”等100多種不同的用法構(gòu)成的長尾。所有左鄰字的信息熵為3.67453。但“輩子”的左鄰字就很 可憐了，2330個“輩子”中有1276個是“一輩子”，有596個“這輩子”，有235個“下輩子”，有149個“上輩子”，有32個“半輩子”，有 10個“八輩子”，有7個“幾輩子”，有6個“哪輩子”，以及“n輩子”、“兩輩子”等13種更罕見的用法。所有左鄰字的信息熵僅為1.25963。因 而，“輩子”能否成詞，明顯就有爭議

看完例子我們發(fā)現(xiàn)被子左邊詞有100多種不同情況，顯然其不確定性明顯更大，在生活中我們也的確會大概率的把“被子”當(dāng)初一個詞來用。所以我們大致可以得到：左右熵值越大，說明該詞的周邊詞越豐富，意味著詞的自由程度越大，其成為一個獨立的詞的可能性也就越大。

新詞發(fā)現(xiàn)算法實戰(zhàn)

這里新詞發(fā)現(xiàn)算法的算法邏輯主要分為三個步驟：

• 將語料文本轉(zhuǎn)換成一個字符串，然后一個生成n_ gram的詞典，并統(tǒng)計個詞的詞頻。
• 利用點間互信息從之前的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

接下來筆者用下方測試語料去進(jìn)行新詞發(fā)現(xiàn)

測試語料

接下來運行下方代碼：首先處理好語料后，然后設(shè)置好互信息的最小閾值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)

得到的新詞，結(jié)果如下，其實還是發(fā)現(xiàn)很多特殊詞語，比如“蔡英文”，“蔡英文”，“臺當(dāng)局”等，說明新詞發(fā)現(xiàn)算法確實起作用了。

結(jié)果

結(jié)語

互信息和左右熵搭配效果果然不同凡響。當(dāng)然這里筆者只是實現(xiàn)了一個超級簡單版的新詞發(fā)現(xiàn)算法，其中有很多細(xì)節(jié)都有待優(yōu)化，比如可以引入字典樹加速算法，或者可以采取一些多輪搜索策略，讓算法找到的新詞更準(zhǔn)等等，大家對新詞發(fā)現(xiàn)算法有興趣的可以繼續(xù)深入學(xué)習(xí)并優(yōu)化。

參考

https://blog.csdn.net/Jemila/article/details/78027240
https://blog.csdn.net/u012879957/article/details/81239458
http://www.itdecent.cn/p/e9313fd692ef