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

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

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

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

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

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

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

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

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

在人人網(wǎng)用戶狀態(tài)中，“被子”一詞一共出現(xiàn)了956次丙者，“輩子”一詞一共出現(xiàn)了2330次复斥，⌒得剑“被子”的左鄰字用例非常豐富：用得最多的是“曬被子”目锭，它一共出現(xiàn)了162次；其次是“的被子”纷捞，出現(xiàn)了85次痢虹；接 下來分別是“條被子”、“在被子”主儡、“床被子”奖唯，分別出現(xiàn)了69次、64次和52次糜值；當然丰捷，還有“疊被子”、“蓋被子”寂汇、“加被子”瓢阴、“新被子”、“掀被 子”健无、“收被子”荣恐、“薄被子”、“踢被子”、“搶被子”等100多種不同的用法構(gòu)成的長尾叠穆。所有左鄰字的信息熵為3.67453少漆。但“輩子”的左鄰字就很 可憐了，2330個“輩子”中有1276個是“一輩子”硼被，有596個“這輩子”示损，有235個“下輩子”，有149個“上輩子”嚷硫，有32個“半輩子”检访，有 10個“八輩子”，有7個“幾輩子”仔掸，有6個“哪輩子”脆贵，以及“n輩子”、“兩輩子”等13種更罕見的用法起暮。所有左鄰字的信息熵僅為1.25963卖氨。因 而，“輩子”能否成詞负懦，明顯就有爭議

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

新詞發(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

接下來筆者用下方測試語料去進行新詞發(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)很多特殊詞語缆巧，比如“蔡英文”布持，“蔡英文”，“臺當局”等陕悬，說明新詞發(fā)現(xiàn)算法確實起作用了题暖。

結(jié)果

結(jié)語

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

參考

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