ngram演算法java

A. 自然語言處理中的N-Gram模型詳解

N-Gram（有時也稱為N元模型）是 自然語言 處理中一個非常重要的概念，通常在NLP中，人們基於一定的語料庫，可以利用N-Gram來預計或者評估一個句子是否合理。另外一方面，N-Gram的另外一個作用是用來評估兩個字元串之間的差異程度。這是模糊匹配中常用的一種手段。本文將從此開始，進而向讀者展示N-Gram在自然語言處理中的各種powerful的應用。
基於N-Gram模型定義的字元串距離
利用N-Gram模型評估語句是否合理
使用N-Gram模型時的數據平滑演算法

歡迎關注白馬負金羈的博客 http://blog.csdn.net/mafujinji ，為保證公式、圖表得以正確顯示，強烈建議你從該地址上查看原版博文。本博客 主要關注方向 包括：數字圖像處理、 演算法 設計與分析、 數據結構 、 機器學習 、數據挖掘、統計分析方法、自然語言處理。
基於N-Gram模型定義的字元串距離
在自然語言處理時，最常用也最基礎的一個操作是就是「模式匹配」，或者稱為「字元串查找」。而模式匹配（字元串查找）又分為 精確匹配 和 模糊匹配 兩種。

所謂精確匹配，大家應該並不陌生，比如我們要統計一篇文章中關鍵詞 「 information 」 出現的次數，這時所使用的方法就是精確的模式匹配。這方面的演算法也比較多，而且應該是計算機相關專業必修的基礎課中都會涉及到的內容，例如KMP演算法、BM演算法和BMH演算法等等。
另外一種匹配就是所謂的模糊匹配，它的應用也隨處可見。例如，一般的文字處理軟體（例如，Microsoft Word等）都會提供拼寫檢查功能。當你輸入一個錯誤的單詞，例如 「 informtaion 」 時，系統會提示你是否要輸入的詞其實是 「 information 」 。將一個可能錯拼單詞映射到一個推薦的正確拼寫上所採用的技術就是模糊匹配。
模糊匹配的關鍵在於如何衡量兩個長得很像的單詞（或字元串）之間的「差異」。這種差異通常又稱為「距離」。這方面的具體演算法有很多，例如基於編輯距離的概念，人們設計出了 Smith-Waterman 演算法和Needleman-Wunsch 演算法，其中後者還是歷史上最早的應用動態規劃思想設計的演算法之一。現在Smith-Waterman 演算法和Needleman-Wunsch 演算法在生物信息學領域也有重要應用，研究人員常常用它們來計算兩個DNA序列片段之間的「差異」（或稱「距離」）。甚至於在LeetCode上也有一道 「No.72 Edit Distance」 ，其本質就是在考察上述兩種演算法的實現。可見相關問題離我們並不遙遠。
N-Gram在模糊匹配中的應用
事實上，筆者在新出版的 《演算法之美——隱匿在數據結構背後的原理》 一書中已經詳細介紹了包括Needleman-Wunsch演算法、Smith-Waterman演算法、N-Gram演算法、Soundex演算法、Phonix演算法等在內的多種距離定義演算法（或模糊匹配演算法）。而今天為了引出N-Gram模型在NLP中的其他應用，我們首先來介紹一下如何利用N-Gram來定義字元串之間的距離。
我們除了可以定義兩個字元串之間的編輯距離（通常利用Needleman-Wunsch演算法或Smith-Waterman演算法）之外，還可以定義它們之間的N-Gram距離。N-Gram（有時也稱為N元模型）是自然語言處理中一個非常重要的概念。假設有一個字元串 s
，那麼該字元串的N-Gram就表示按長度 N 切分原詞得到的詞段，也就是 s
中所有長度為 N 的子字元串。設想如果有兩個字元串，然後分別求它們的N-Gram，那麼就可以從它們的共有子串的數量這個角度去定義兩個字元串間的N-Gram距離。但是僅僅是簡單地對共有子串進行計數顯然也存在不足，這種方案顯然忽略了兩個字元串長度差異可能導致的問題。比如字元串 girl 和 girlfriend，二者所擁有的公共子串數量顯然與 girl 和其自身所擁有的公共子串數量相等，但是我們並不能據此認為 girl 和girlfriend 是兩個等同的匹配。
為了解決該問題，有學者便提出以非重復的N-Gram分詞為基礎來定義 N-Gram距離這一概念，可以用下面的公式來表述：
|GN(s)|+|GN(t)|−2×|GN(s)∩GN(t)|

此處，|GN(s)|
是字元串 s
的 N-Gram集合，N 值一般取2或者3。以 N = 2 為例對字元串Gorbachev和Gorbechyov進行分段，可得如下結果（我們用下畫線標出了其中的公共子串）。

有興趣的讀者可以在引用相關JAR包之後在Eclipse中執行上述java程序，你會發現，和我們預期的一樣，字元串Gorbachev和Gorbechyov所得之距離評分較高（=0.7），說明二者很接近；而girl和girlfriend所得之距離評分並不高（=0.3999），說明二者並不很接近。
利用N-Gram模型評估語句是否合理
從現在開始，我們所討論的N-Gram模型跟前面講過N-Gram模型從外在來看已經大不相同，但是請注意它們內在的聯系（或者說本質上它們仍然是統一的概念）。
為了引入N-Gram的這個應用，我們從幾個例子開始。首先，從統計的角度來看，自然語言中的一個句子 s
可以由任何詞串構成，不過概率 P(s)
有大有小。例如：
s1
= 我剛吃過晚飯
s2
= 剛我過晚飯吃

顯然，對於中文而言 s1
是一個通順而有意義的句子，而s2
則不是，所以對於中文來說，P(s1)>P(s2)
。但不同語言來說，這兩個概率值的大小可能會反轉。
其次，另外一個例子是，如果我們給出了某個句子的一個節選，我們其實可以能夠猜測後續的詞應該是什麼，例如
the large green __ . Possible answer may be 「mountain」 or 「tree」 ?
Kate swallowed the large green __ . Possible answer may be 「pill」 or 「broccoli」 ?

顯然，如果我們知道這個句子片段更多前面的內容的情況下，我們會得到一個更加准確的答案。這就告訴我們，前面的（歷史）信息越多，對後面未知信息的約束就越強。
如果我們有一個由 m
個片語成的序列（或者說一個句子），我們希望算得概率 P(w1,w2,⋯,wm)
，根據鏈式規則，可得
P(w1,w2,⋯,wm)=P(w1)P(w2|w1)P(w3|w1,w2)⋯P(wm|w1,⋯,wm−1)

這個概率顯然並不好算，不妨利用馬爾科夫鏈的假設，即當前這個詞僅僅跟前面幾個有限的詞相關，因此也就不必追溯到最開始的那個詞，這樣便可以大幅縮減上訴算式的長度。即P(wi|w1,⋯,wi−1)=P(wi|wi−n+1,⋯,wi−1)

特別地，對於 n
取得較小值的情況當 n=1
, 一個一元模型（unigram model)即為P(w1,w2,⋯,wm)=∏i=1mP(wi)

當 n=2
, 一個二元模型（bigram model)即為P(w1,w2,⋯,wm)=∏i=1mP(wi|wi−1)

當 n=3
, 一個三元模型（trigram model)即為P(w1,w2,⋯,wm)=∏i=1mP(wi|wi−2wi−1)

接下來的思路就比較明確了，可以利用最大似然法來求出一組參數，使得訓練樣本的概率取得最大值。
對於unigram model而言，其中c(w1,..,wn)
表示 n-gram w1,..,wn
在訓練語料中出現的次數，M
是語料庫中的總字數（例如對於 yes no no no yes 而言，M=5
）P(wi)=C(wi)M

對於bigram model而言，P(wi|wi−1)=C(wi−1wi)C(wi−1)

對於n
-gram model而言，P(wi|wi−n−1,⋯,wi−1)=C(wi−n−1,⋯,wi)C(wi−n−1,⋯,wi−1)

來看一個具體的例子，假設我們現在有一個語料庫如下，其中<s1><s2>
是句首標記，</s2></s1>
是句尾標記：
<s1><s2>yesnonononoyes</s2></s1><s1><s2>nononoyesyesyesno</s2></s1>

下面我們的任務是來評估如下這個句子的概率：<s1><s2>yesnonoyes</s2></s1>

我們來演示利用trigram模型來計算概率的結果P(yes|<s1><s2>)=12,P(no|<s2>yes)=1P(no|yesno)=12,P(yes|nono)=25P(</s2>|noyes)=12,P(</s1>|yes</s2>)=1

所以我們要求的概率就等於：12×1×12×25×12×1=0.05

再舉一個來自文獻[1]的例子，假設現在有一個語料庫，我們統計了下面一些詞出現的數量

下面這個概率作為其他一些已知條件給出：P(i|<s>)=0.25P(english|want)=0.0011P(food|english)=0.5P(</s>|food)=0.68

，則可以算得P(s1)=P(i|<s>)P(want|i)P(english|want)P(food|english)P(</s>|food)=0.25×0.33×0.0011×0.5×0.68=0.000031

使用N-Gram模型時的數據平滑演算法
有研究人員用150萬詞的訓練語料來訓練 trigram 模型，然後用同樣來源的 測試 語料來做驗證，結果發現23%的 trigram 沒有在訓練語料中出現過。這其實就意味著上一節我們所計算的那些概率有空為 0，這就導致了數據稀疏的可能性，我們的表3中也確實有些為0的情況。對語言而言，由於數據稀疏的存在，極大似然法不是一種很好的參數估計辦法。
這時的解決辦法，我們稱之為「平滑技術」（Smoothing）或者 「減值」 （Discounting）。其主要策略是把在訓練樣本中出現過的事件的概率適當減小，然後把減小得到的概率密度分配給訓練語料中沒有出現過的事件。實際中平滑演算法有很多種，例如：▸ Laplacian (add-one) smoothing▸ Add-k smoothing▸ Jelinek-Mercer interpolation▸ Katz backoff▸ Absolute discounting▸ Kneser-Ney
對於這些演算法的詳細介紹，我們將在後續的文章中結合一些實例再來進行討論。
A Final Word
如果你能從前面那些繁冗、復雜的概念和公式中挺過來，恭喜你，你對N-Gram模型已經有所認識了。盡管，我們還沒來得及探討平滑演算法（但它即將出現在我的下一篇博文里，如果你覺得還未過癮的話），但是其實你已經掌握了一個相對powerful的工具。你可以能會問，在實踐中N-Gram模型有哪些具體應用，作為本文的結束，主頁君便在此補充幾個你曾見過的或者曾經好奇它是如何實現的例子。
Eg.1 搜索引擎 （Google或者Bai）、或者輸入法的猜想或者提示。你在用網路時，輸入一個或幾個詞，搜索框通常會以下拉菜單的形式給出幾個像下圖一樣的備選，這些備選其實是在猜想你想要搜索的那個詞串。再者，當你用輸入法輸入一個漢字的時候，輸入法通常可以聯系出一個完整的詞，例如我輸入一個「劉」字，通常輸入法會提示我是否要輸入的是「劉備」。通過上面的介紹，你應該能夠很敏銳的發覺，這其實是以N-Gram模型為基礎來實現的，如果你能有這種覺悟或者想法，那我不得不恭喜你，都學會搶答了！

Eg.2 某某作家或者語料庫風格的文本自動生成。這是一個相當有趣的話題。來看下面這段話（該例子取材自文獻【1】）：
「You are uniformly charming!」 cried he, with a smile of associating and now and then I bowed and they perceived a chaise and four to wish for.

你應該還沒有感覺到它有什麼異樣吧。但事實上這並不是由人類寫出的句子，而是計算機根據Jane Austen的語料庫利用trigram模型自動生成的文段。（Jane Austen是英國著名女作家，代表作有《傲慢與偏見》等）
再來看兩個例子，你是否能看出它們是按照哪位文豪（或者語料庫）的風格生成的嗎？
This shall forbid it should be branded, if renown made it empty.
They also point to ninety nine point six billion dollars from two hundred four oh three percent of the rates of interest stores as Mexico and Brazil on market conditions.

答案是第一個是莎士比亞，第二個是華爾街日報。最後一個問題留給讀者思考，你覺得上面兩個文段所運用的n-gram模型中，n應該等於多少？
推薦閱讀和參考文獻：
[1] Speech and Language Processing. Daniel Jurafsky & James H. Martin, 3rd. Chapter 4[2] 本文中的一些例子和描述來自 北京大學 常寶寶 以及 The University of Melbourne 「Web Search and Text Analysis」 課程的幻燈片素材

B. java word分詞器怎樣安裝在java中

word分詞是一個Java實現的分布式的中文分片語件，提供了多種基於詞典的分詞演算法，並利用ngram模型來消除歧義。

如果需要安裝word分詞器可以參考下面的步驟：

1、確保電腦上已經安裝了JDK軟體和Eclispe工具，沒有安裝的可以到對應的官網下載安裝：

JDK官網：http://www.oracle.com/technetwork/java/javase/downloads/index.html

Eclipse官網：http://www.eclipse.org

2、下載word分詞器的相關jar包：

打開word分詞器的官方github主頁：https://github.com/ysc/word

導入成功之後就可以在自己的項目中使用word分詞器了。

C. java中文分片語件word怎麼使用

參考如下
1、快速體驗
運行項目根目錄下的腳本demo-word.bat可以快速體驗分詞效果
用法: command [text] [input] [output]
命令command的可選值為：demo、text、file
demo
text 楊尚川是APDPlat應用級產品開發平台的作者
file d:/text.txt d:/word.txt
exit

2、對文本進行分詞
移除停用詞：List<Word> words = WordSegmenter.seg("楊尚川是APDPlat應用級產品開發平台的作者");
保留停用詞：List<Word> words = WordSegmenter.segWithStopWords("楊尚川是APDPlat應用級產品開發平台的作者");
System.out.println(words);

輸出：
移除停用詞：[楊尚川, apdplat, 應用級, 產品, 開發平台, 作者]
保留停用詞：[楊尚川, 是, apdplat, 應用級, 產品, 開發平台, 的, 作者]

3、對文件進行分詞
String input = "d:/text.txt";
String output = "d:/word.txt";
移除停用詞：WordSegmenter.seg(new File(input), new File(output));
保留停用詞：WordSegmenter.segWithStopWords(new File(input), new File(output));

4、自定義配置文件
默認配置文件為類路徑下的word.conf，打包在word-x.x.jar中
自定義配置文件為類路徑下的word.local.conf，需要用戶自己提供
如果自定義配置和默認配置相同，自定義配置會覆蓋默認配置
配置文件編碼為UTF-8

5、自定義用戶詞庫
自定義用戶詞庫為一個或多個文件夾或文件，可以使用絕對路徑或相對路徑
用戶詞庫由多個詞典文件組成，文件編碼為UTF-8
詞典文件的格式為文本文件，一行代表一個詞
可以通過系統屬性或配置文件的方式來指定路徑，多個路徑之間用逗號分隔開
類路徑下的詞典文件，需要在相對路徑前加入前綴classpath:

指定方式有三種：
指定方式一，編程指定（高優先順序）：
WordConfTools.set("dic.path", "classpath:dic.txt，d:/custom_dic");
DictionaryFactory.reload();//更改詞典路徑之後，重新載入詞典
指定方式二，Java虛擬機啟動參數（中優先順序）：
java -Ddic.path=classpath:dic.txt，d:/custom_dic
指定方式三，配置文件指定（低優先順序）：
使用類路徑下的文件word.local.conf來指定配置信息
dic.path=classpath:dic.txt，d:/custom_dic

如未指定，則默認使用類路徑下的dic.txt詞典文件

6、自定義停用詞詞庫
使用方式和自定義用戶詞庫類似，配置項為：
stopwords.path=classpath:stopwords.txt，d:/custom_stopwords_dic

7、自動檢測詞庫變化
可以自動檢測自定義用戶詞庫和自定義停用詞詞庫的變化
包含類路徑下的文件和文件夾、非類路徑下的絕對路徑和相對路徑
如：
classpath:dic.txt，classpath:custom_dic_dir,
d:/dic_more.txt，d:/DIC_DIR，D:/DIC2_DIR，my_dic_dir，my_dic_file.txt

classpath:stopwords.txt，classpath:custom_stopwords_dic_dir，
d:/stopwords_more.txt，d:/STOPWORDS_DIR，d:/STOPWORDS2_DIR，stopwords_dir，remove.txt

8、顯式指定分詞演算法
對文本進行分詞時，可顯式指定特定的分詞演算法，如：
WordSegmenter.seg("APDPlat應用級產品開發平台", SegmentationAlgorithm.BidirectionalMaximumMatching);

SegmentationAlgorithm的可選類型為：
正向最大匹配演算法：MaximumMatching
逆向最大匹配演算法：ReverseMaximumMatching
正向最小匹配演算法：MinimumMatching
逆向最小匹配演算法：ReverseMinimumMatching
雙向最大匹配演算法：BidirectionalMaximumMatching
雙向最小匹配演算法：BidirectionalMinimumMatching
雙向最大最小匹配演算法：
全切分演算法：FullSegmentation
最少分詞演算法：MinimalWordCount
最大Ngram分值演算法：MaxNgramScore

9、分詞效果評估
運行項目根目錄下的腳本evaluation.bat可以對分詞效果進行評估
評估採用的測試文本有253 3709行，共2837 4490個字元
評估結果位於target/evaluation目錄下：
corpus-text.txt為分好詞的人工標注文本，詞之間以空格分隔
test-text.txt為測試文本，是把corpus-text.txt以標點符號分隔為多行的結果
standard-text.txt為測試文本對應的人工標注文本，作為分詞是否正確的標准
result-text-***.txt，***為各種分詞演算法名稱，這是word分詞結果
perfect-result-***.txt，***為各種分詞演算法名稱，這是分詞結果和人工標注標准完全一致的文本
wrong-result-***.txt，***為各種分詞演算法名稱，這是分詞結果和人工標注標准不一致的文本

D. 自然語言處理（NLP）的基礎難點：分詞演算法

自然語言處理（NLP，Natural Language Processing）是人工智慧領域中的一個重要方向，主要研究人與計算機之間用自然語言進行有效通信的各種理論和方法。自然語言處理的底層任務由易到難大致可以分為詞法分析、句法分析和語義分析。分詞是詞法分析（還包括詞性標注和命名實體識別）中最基本的任務，也是眾多NLP演算法中必不可少的第一步，其切分准確與否往往與整體結果息息相關。

金融領域分詞的難點

分詞既簡單又復雜。簡單是因為分詞的演算法研究已經很成熟了，大部分的演算法（如HMM分詞、CRF分詞）准確率都可以達到95%以上；復雜則是因為剩下的5%很難有突破，主要可以歸結於三點：

▲粒度，即切分時的最小單位，不同應用對粒度的要求不一樣，比如「融資融券」可以是一個詞也可以是兩個詞

▲歧義，比如「恆生」一詞，既可指恆生公司，又可指恆生指數

▲未登錄詞，即未出現在演算法使用的詞典中的詞，比如不常見的專業金融術語，以及各種上市公司的名稱

在金融領域中，分詞也具有上述三個難點，並且在未登錄詞方面的難點更為突出，這是因為金融類詞彙本來就多，再加上一些專有名詞不僅有全稱還有簡稱，這就進一步增大了難度。

在實際應用中，以上難點時常會造成分詞效果欠佳，進而影響之後的任務。尤其是在一些金融業務中，有許多需要與用戶交互的場景，某些用戶會用口語化的詞彙描述業務，如果分詞錯誤會影響用戶意圖的解析，這對分詞的准確性提出了更高的要求。因此在進行NLP上層應用開發時，需要對分詞演算法有一定的了解，從而在效果優化時有能力對分詞器進行調整。接下來，我們介紹幾種常用的分詞演算法及其應用在金融中的優劣。

幾種常見的分詞演算法

分詞演算法根據其核心思想主要分為兩種：

第一種是基於字典的分詞，先把句子按照字典切分成詞，再尋找詞的最佳組合方式，包括最大匹配分詞演算法、最短路徑分詞演算法、基於N-Gram model的分詞演算法等；

第二種是基於字的分詞，即由字構詞，先把句子分成一個個字，再將字組合成詞，尋找最優的切分策略，同時也可以轉化成序列標注問題，包括生成式模型分詞演算法、判別式模型分詞演算法、神經網路分詞演算法等。

最大匹配分詞尋找最優組合的方式是將匹配到的最長片語合在一起，主要的思路是先將詞典構造成一棵Trie樹（也稱為字典樹），Trie樹由詞的公共前綴構成節點，降低了存儲空間的同時可以提升查找效率。

最大匹配分詞將句子與Trie樹進行匹配，在匹配到根結點時由下一個字重新開始進行查找。比如正向（從左至右）匹配「他說的確實在理」，得出的結果為「他／說／的確／實在／理」。如果進行反向最大匹配，則為「他／說／的／確實／在理」。

這種方式雖然可以在O(n)時間對句子進行分詞，但是只單向匹配太過絕對，尤其是金融這種詞彙較豐富的場景，會出現例如「交易費/用」、「報價單/位」等情況，所以除非某些詞的優先順序很高，否則要盡量避免使用此演算法。

最短路徑分詞演算法首先將一句話中的所有詞匹配出來，構成詞圖（有向無環圖DAG），之後尋找從起始點到終點的最短路徑作為最佳組合方式，例：

我們認為圖中每個詞的權重都是相等的，因此每條邊的權重都為1。

在求解DAG圖的最短路徑問題時，總是要利用到一種性質：即兩點之間的最短路徑也包含了路徑上其他頂點間的最短路徑。比如S->A->B->E為S到E到最短路徑，那S->A->B一定是S到B到最短路徑，否則會存在一點C使得d(S->C->B)<d(S->A->B)，那S到E的最短路徑也會變為S->C->B->E，這就與假設矛盾了。利用上述的最優子結構性質，可以利用貪心演算法或動態規劃兩種求解演算法：

（1）基於Dijkstra演算法求解最短路徑，該演算法適用於所有帶權有向圖，求解源節點到其他所有節點的最短路徑，並可以求得全局最優解；

（2）N-最短路徑分詞演算法，該方法是對Dijkstra演算法的擴展，在每一步保存最短的N條路徑，並記錄這些路徑上當前節點的前驅，在最後求得最優解時回溯得到最短路徑。這種方法的准確率優於Dijkstra演算法，但在時間和空間復雜度上都更大。

相較於最大匹配分詞演算法，最短路徑分詞演算法更加靈活，可以更好地把詞典中的片語合起來，能更好地解決有歧義的場景。比如上述「他說的確實在理」這句話，用最短路徑演算法的計算結果為「他／說／的／確實／在理」，避免了正向最大匹配的錯誤。但是對於詞典中未存在的詞基本沒有識別能力，無法解決金融領域分詞中的「未登錄詞」難點。

N-Gram（又稱N元語法模型）是基於一個假設：第n個詞出現與前n-1個詞相關，而與其他任何詞不相關。在此種假設下，可以簡化詞的條件概率，進而求解整個句子出現的概率。

現實中，常用詞的出現頻率或者概率肯定比罕見詞要大。因此，可以將求解詞圖最短路徑的問題轉化為求解最大概率路徑的問題，即分詞結果為「最有可能的詞的組合「。

計算詞出現的概率，僅有詞典是不夠的，還需要充足的語料，所以分詞任務已經從單純的「演算法」上升到了「建模」，即利用統計學方法結合大數據挖掘，對「語言」（句子出現的概率）進行建模。

我們將基於N-gram模型所統計出的概率分布應用到詞圖中，可以得到詞的概率圖。對該詞圖用最短路徑分詞演算法求解最大概率的路徑，即可得到分詞結果。

相較於前兩種分詞演算法，基於N-Gram model的分詞演算法對詞頻進行了統計建模，在切分有歧義的時候力求得到全局最優值，比如在切分方案「證券/自營/業務」和「證券/自/營業/務」中，統計出「證券/自營/業務」出現的概率更大，因此結果有更高的准確率。但也依然無法解決金融場景中未登錄詞的問題。

生成式模型主要有隱馬爾可夫模型（HMM，Hidden Markov Model）、樸素貝葉斯分類等。HMM是常用的分詞模型，基於Python的jieba分詞器和基於Java的HanLP分詞器都使用了HMM。

HMM模型認為在解決序列標注問題時存在兩種序列，一種是觀測序列，即人們顯性觀察到的句子，另一種是隱狀態序列，即觀測序列的標簽。假設觀測序列為X，隱狀態序列是Y，則因果關系為Y->X。因此要得到標注結果Y，必須對X的概率、Y的概率、P(X|Y)進行計算，即建立P(X,Y)的概率分布模型。

HMM演算法可以在一定程度上解決未登錄詞的問題，但生成式模型的准確率往往沒有接下來要談到的判別式模型高。

判別式模型主要有感知機、支持向量機（SVM，Support Vector Machine）、條件隨機場（CRF，Conditional Random Field）、最大熵模型等，其中感知機模型和CRF模型是常用的分詞模型。

（1）平均感知機分詞演算法

感知機是一種簡單的二分類線性模型，通過構造超平面，將特徵空間（輸入空間）中的樣本分為正負兩類。通過組合，感知機也可以處理多分類問題。但由於每次迭代都會更新模型的所有權重，被誤分類的樣本會造成很大影響，因此採用平均的方法，在處理完一部分樣本後對更新的權重進行平均。

（2）CRF分詞演算法

CRF可以看作一個無向圖模型，假設給定的標注序列為Y，觀測序列為X，CRF對條件概率P(Y|X)進行定義，而不是對聯合概率建模。

平均感知機演算法雖然速度快，但仍不夠准確。適合一些對速度要求高、對准確性要求相對不那麼高的場景。CRF分詞演算法可以說是目前最常用的分詞、詞性標注和實體識別演算法，它對未登陸詞也有很好的識別能力，是目前在速度、准確率以及未登錄詞識別上綜合表現最突出的演算法，也是我們目前所採用的解決方案，但速度會比感知機慢一些。

在NLP中，最常用的神經網路為循環神經網路（RNN，Recurrent Neural Network），它在處理變長輸入和序列輸入問題中有著巨大的優勢。LSTM（Long Short-Term Memory，長短期記憶網路）為RNN變種的一種，在一定程度上解決了RNN在訓練過程中梯度消失和梯度爆炸的問題。

目前對於序列標注任務，業內公認效果最好的模型是BiLSTM+CRF。相比於上述其它模型，雙向循環神經網路BiLSTM，可以更好地編碼當前字等上下文信息，並在最終增加CRF層，核心是用Viterbi演算法進行解碼，以得到全局最優解，避免B,S,E這種不可能的標記結果的出現，提高准確率。

神經網路分詞雖然能在准確率、未登錄詞識別上有更好的表現，但RNN無法並行計算，在速度上沒有優勢，所以該演算法通常在演算法研究、句子精確解析等對速度要求不高的場景下使用。

分詞作為NLP底層任務之一，既簡單又重要，很多時候上層演算法的錯誤都是由分詞結果導致的。因此，對於底層實現的演算法工程師，不僅需要深入理解分詞演算法，更需要懂得如何高效地實現和調試。

而對於上層應用的演算法工程師，在實際分詞時，需要根據業務場景有選擇地應用上述演算法，比如在搜索引擎對大規模網頁進行內容解析時，對分詞對速度要求大於精度，而在智能問答中由於句子較短，對分詞的精度要求大於速度。

E. ngram模型在哪些場景運動較多

首頁

博客

研修院

VIP

APP

問答

下載

社區

推薦頻道

活動

招聘

專題

打開CSDN APP
Copyright © 1999-2020, CSDN.NET, All Rights Reserved

風控模型特徵工程
打開APP

風控建模二、特徵工程---通用 原創
2022-09-17 11:46:33
1點贊

沐自禮

碼齡8年

關注
目錄

一、數據預處理

1.1 缺失值

1.2 異常值處理

1.3 樣本不均衡處理

二、特徵生成

2.1 特徵歸一化（or 標准化）

2.2 特徵放縮（統計信息+ 簡單加減乘除）

2.3 啞變數

2.3 分桶

2.4 日期類

2.5 組合特徵

2.6 文本型（風控場景中應用比較少，傳統nlp應用較多）

2.6.1 詞袋模型+Ngram

2.6.2 tf-idf

2.6.3 word2vev/fastext

2.7 embedding

2.8 特徵分解 （應用較少）

三、特徵篩選

3.1 移除低方差的特徵 (Removing features with low variance)

3.2. 單變數特徵選擇 (Univariate feature selection)

3.2.1 卡方(Chi2)檢驗

3.2.2 Pearson相關系數 (Pearson Correlation)

3.3 遞歸特徵消除 (Recursive Feature Elimination)

3.4 基於L1的特徵選擇 (L1-based feature selection)

3.5 xgboost, lightGBM

參考文獻

「特徵決定了模型的上限， 而演算法只是逼近這個上限」，由此可見特徵工程在風控建模中的重要程度。 特徵工程的本質是基於原始數據的信息提煉， 風控場景中的很多數據源， 單獨來看可能和風險表現關聯性並不強，但是加工成特徵後， 卻會與我們想要預測的目標產生緊密的聯系。

下面我們將從特徵預處理，特徵生成，特徵篩選三個模塊對特徵工程進行拆解。

一、數據預處理
1.1 缺失值
一般來說，未經處理的原始數據中通常會存在缺失值，因此在建模訓練之前需要處理好缺失值。

1）缺失數據佔比小於 20%。可以通過直接填充法，連續特徵一般取均值填充，離散特徵可以取眾數填充；可以模型預測法，通過隨機森林或者決策樹進行預測結果填充；也可以通過插值法填充。
2）缺失數據佔比大於 20% 小於 50%，這個時候可以把缺失值構建為新的特徵，增加一列離散特徵，即有缺失數據和無缺失數據。
3）缺失數據佔比大於 50%，因為信息量較少，模型可能會學到大量噪音建議直接刪除該特徵。

像 xgboost 模型自帶缺失值處理功能，可以不進行缺失值處理。

缺失值填充方法：
1). 如果是連續性，就使用平均值插補，如果是離散性，就使用眾數來插補。 當然也可以用特殊值、中位數等代替。 其中採用均值填充的缺點：大大降低數據的方差
2). 隨機插補法----從總體中隨機抽取某個樣本代替缺失樣本
3). 引入預測模型，可考慮輔助回歸，通過變數間的關系來預測缺失數據

下面代碼就是均值填充的兩種方案：

df_train['Age'].fillna(value=df_train['Age'].mean()).sample(10)

from sklearn.preprocessing import Imputer
imp = Imputer(missing_values='NaN', strategy='mean', axis=0)
df_train.loc[:,'Age'] = df_train['Age'].fillna(value=df_train['Age'].mean()).()
df_train.head(10)
1.2 異常值處理
異常值，即在數據集中存在不合理的值，又稱離群點、極值等。可以通過統計分析、箱線圖、聚類、3σ 原則、孤立森林等方法進行檢查。

一般的處理方法如下：
1）直接刪除含有異常值的樣本。
2）視為缺失值。利用缺失值處理的方法進行處理。
3）最近值修正。可以用相近的觀測值修正該異常值。
4）不處理。可以直接在具有異常值的數據集上進行數據建模。

大部分建模時，通過畫圖的方式進行看一下即可。

提供的方法：

統計分析，看四分位數，看數據分布。

箱線圖：使用畫圖工具比如seaborn庫 調用boxplot，distplot看一下。

聚類：使用sklearn中的聚類函數。

3σ: 需要自己同統計，類似看四分位數。

1.3 樣本不均衡處理
推薦包：imbalance learn (https://imbalanced-learn.org/stable/references/index.html)

後面章節會對樣本不均衡做詳細的介紹，暫時可以先簡單了解一下。一般應用場景中，常用樣本不均衡的是解決方案為1,2。

樣本不均衡現象是指正樣本數目與負樣本數目比列相差很大。處理方法如下：
1）下采樣/欠采樣(under sampling)：從多數類中隨機抽取樣本從而減少多數類別樣本數據，使數據達到平衡的方式。比如本來樣本正負例的比例是 10:1，可以對正樣本進行下采樣構建 10 個正負樣本比例為 1:1 的模型，回歸結果取平均值，分類結果進行投票。

2）上采樣/過采樣(Over Sampling)：和欠采樣採用同樣的原理，通過抽樣來增加少數樣本的數目，從而達到數據平衡的目的。同樣比如本來樣本正負例的比例是 10:1，可以對負樣本進行上采樣構建正負樣本比例為 1:1 的模型。

3）Smote 演算法：Smote 演算法屬於上采樣的一種，通過人工合成的方法來生成少類別的樣本。方法也很簡單，對於某一個缺少樣本的類別，它會隨機找出幾個該類別的樣本，再找出最靠近這些樣本的若干個該類別樣本，組成一個候選合成集合，然後在這個集合中不停的選擇距離較近的兩個樣本，在這兩個樣本之間，比如中點，構造一個新的該類別樣本。舉個例子，比如該類別的候選合成集合有兩個樣本(x1,y),(x2,y)(x1,y),(x2,y)，那麼Smote采樣後，可以得到一個新的訓練樣本(x1+x22,y)(x1+x22,y)，通過這種方法，我們可以得到不改變訓練集分布的新樣本，讓訓練集中各個類別的樣本數趨於平衡。

4）Focal loss ：主要解決分類樣本不平衡問題，通過修改交叉熵損失函數，通過增加類別權重 α 和樣本難度權重調因子(molating factor)(1−pt)γ(1−pt)γ，來減緩上述問題。

5）設置損失函數的權重：使得少數類別數據判斷錯誤的損失大於多數類別數據判斷錯誤的損失，即當我們的少數類別數據預測錯誤的時候，會產生一個比較大的損失值，從而導致模型參數往讓少數類別數據預測准確的方向偏。

二、特徵生成
2.1 特徵歸一化（or 標准化）
應用於數值類特徵。

歸一化（標准化），就是要把你需要處理的數據經過處理後（通過某種演算法）限制在你需要的一定范圍內。其目的一是把不同量綱的東西放在同一量綱下，保正程序運行時收斂加快，大部分模型歸一化後收斂速度會加快。但像樹模型不受特徵歸一化影響，所以不需要特徵歸一化。
歸一化處理：最大最小值歸一化或者叫 0-1 歸一化，取值范圍在 [0,1] 處理，max 為樣本最大值， min 為樣本最小值。
標准化處理：這里只介紹一種經常使用的 z-score 標准化，經過處理後的數據均值為 0，標准差為 1，符合標準的正態分布。其中 mean 為平均值，б 為標准差。

# 幅度縮放，最大最小值縮放到[0,1]區間內
from sklearn.preprocessing import MinMaxScaler
mm_scaler = MinMaxScaler()
fare_trans = mm_scaler.fit_transform(df_train[['Fare']])

# 幅度縮放，將每一列的數據標准化為正態分布的
from sklearn.preprocessing import StandardScaler
std_scaler = StandardScaler()
fare_std_trans = std_scaler.fit_transform(df_train[['Fare']])

#中位數或者四分位數去中心化數據，對異常值不敏感
from sklearn.preprocessing import robust_scale
fare_robust_trans = robust_scale(df_train[['Fare','Age']])

#將同一行數據規范化,前面的同一變為1以內也可以達到這樣的效果
from sklearn.preprocessing import Normalizer
normalizer = Normalizer()
fare_normal_trans = normalizer.fit_transform(df_train[['Age','Fare']])
fare_normal_trans
2.2 特徵放縮（統計信息+ 簡單加減乘除）
應用於數值類特徵，可以引入log非線性進行放縮。

import numpy as np
log_age = df_train['Age'].apply(lambda x:np.log(x))
df_train.loc[:,'log_age'] = log_age

# 最大最小值
max_age = df_train['Age'].max()
min_age = df_train["Age"].min()

# 分位數,極值處理，我們最粗暴的方法就是將前後1%的值抹去
age_quarter_01 = df_train['Age'].quantile(0.01)
print(age_quarter_01)
age_quarter_99 = df_train['Age'].quantile(0.99)
print(age_quarter_99)
df_train.loc[:,'family_size'] = df_train['SibSp']+df_train['Parch']+1
df_train.head() df_train.loc[:,'tmp'] = df_train['Age']*df_train['Pclass'] + 4*df_train['family_size']
df_train.head()
2.3 啞變數
啞變數用於類別，一般如性別，分為男女兩列。

embarked_oht = pd.get_mmies(df_train[['Embarked']])
embarked_oht.head()
2.3 分桶
應用於數值。

可以等頻分桶，也可以自行指定區間分桶。非線性變化。

# 等頻切分
df_train.loc[:,'fare_qcut'] = pd.qcut(df_train['Fare'], 10)
df_train.head()

df_train = df_train.sort_values('Fare')

alist = list(set(df_train['fare_qcut']))
badrate = {}
for x in alist:
a = df_train[df_train.fare_qcut == x]
bad = a[a.label == 1]['label'].count()
good = a[a.label == 0]['label'

F. n-gram語言模型

在自然語言處理中的一個基本問題： 如何計算一段文本序列在某種語言下出現的概率？ 之所為稱其為一個基本問題，是因為它在很多NLP任務中都扮演著重要的角色。例如，"我經常會去圖書館____"，預測該句後面的詞。我們會通過已有的語料或上下文，來統計預測這句話可以填某個詞的概率。將概率最大的作為預測結果返回。再比如機器翻譯中，『I like Tom so much.』 ===>{『我』，『喜歡』，『湯姆』，『非常』} 將這個集合里的字詞排列組合成句子，然後用語言模型去計算形成句子的概率大小。概率越大，說明翻譯越順暢，越好，就作為最終的答案返回。

統計語言模型給出了這一類問題的一個基本解決框架。對於一段文本序列

它的概率可以表示為：

即將序列的聯合概率轉化為一系列條件概率的乘積。問題變成了如何去預測這些給定previous words下的條件概率：

由於其巨大的參數空間，這樣一個原始的模型在實際中並沒有什麼用。我們更多的是採用其簡化版本—— Ngram模型 ：

常見的如bigram模型（N=2）和trigram模型（N=3）。事實上，由於模型復雜度和預測精度的限制，我們很少會考慮N>3的模型。

我們可以用最大似然法去求解Ngram模型的參數——等價於去統計每個Ngram的條件詞頻。

為了避免統計中出現的零概率問題，針對於Ngram模型有很多處理的小技巧。

n-gram語言模型的思想，可以追溯到資訊理論大師香農的研究工作，他提出一個問題： 給定一串字母，如「for ex」，下一個最大可能性出現的字母是什麼？ 從訓練語料數據中，我們可以通過極大似然估計的方法，得到N個概率分布：是a的概率是0.4，是b的概率是0.0001，是c的概率是…，當然， 別忘記約束條件：所有的N個概率分布的總和為1.

n-gram模型概率公式推導。根據條件概率和乘法公式：

得到 

拿一個應用來講，假設T是由詞序列A1,A2,A3,…An組成的，那麼P(T)=P(A1A2A3…An)=P(A1)P(A2|A1)P(A3|A1A2)…P(An|A1A2…An-1) 

如果直接這么計算，是有很大困難的，需要引入馬爾科夫假設，即：一個item的出現概率，只與其前m個items有關 ，當m=0時，就是unigram，m=1時，是bigram模型。

因此，P(T)可以求得，例如，當利用bigram模型時，P(T)=P(A1)P(A2|A1)P(A3|A2)…P(An|An-1) 

而P(An|An-1)條件概率可以通過極大似然估計求得，等於Count(An-1,An)/Count(An-1)。

·著名的 google books Ngram Viewer ，它的n-gram數據格式是這樣的：

代表了一個 1-gram的數據片段 ，第一行的意思是，「circumvallate」這個單詞在1978年出現335次，存在91本書中。這些元數據，除了頻率335次是必須的，其他的元數據（例如，還有詞性等）可以根據應用需求來定。下面是一個 5-gram數據片段 ：

當然，也可以是其他形式，例如， HanLP 的n-gram模型是bigram：

每一行代表，兩個相鄰單詞共同出現時的頻率（相對於背後的語料庫）。

· 文化研究 ·分詞演算法 ·語音識別 ·輸入法 ·機器翻譯

文化研究：n-gram模型看起來比較枯燥和冰冷，但實際上，google books ngram項目，催生了一門新學科( Culturomics )的成立，通過數字化的文本，來研究人類行為和文化趨勢。可查看知乎上的 詳細介紹 ，。《可視化未來》這本書也有詳細介紹。還有TED上的視頻 《what_we_learned_from_5_million_books》 ，十分精彩。

輸入法：大家每天都在使用的東西，請看：輸入「tashiyanjiushengwude」，可能的輸出有：

究竟哪個是輸入者最想表達的意思，這背後的技術就要用到n-gram語言模型了。item就是每一個拼音對應的可能的字。還記得智能ABC嗎？ 據說 是運用n-gram的鼻祖了。 不過搜狗輸入法後來居上，它採用更先進的 雲計算技術 (n-gram模型的數據量可是相當之大，後面會說到) 。

做概率統計的都知道，語料庫的規模越大，做出的n-gram對統計語言模型才更有用。n-gram，無論是存儲還是檢索，對技術都是極大的挑戰。 

主要參考文章：

【1】 N-Gram語言模型   原文更精彩