前言

在美團商家數據中心（MDC），有超過100w的已校準審核的POI數據（我們一般將商家標示為POI，POI基礎信息包括：門店名稱、品類、電話、地址、坐標等）。如何使用這些已校準的POI數據，挖掘出有價值的信息，本文進行了一些嘗試：利用機器學習方法，自動標注缺失品類的POI數據。例如，門店名稱為“好再來牛肉拉面館”的POI將自動標注“小吃”品類。

機器學習解決問題的一般過程：

本文將按照：1）特征表示；2）特征選擇；3）基于Naive Bayes分類模型；4）分類預測，四個部分順序展開。

特征表示

我們需要先將實際問題轉換成計算機可識別的形式。對于POI而言，反應出POI品類的一個重要特征是POI門店名稱，那么問題轉換成了根據POI門店名稱判別POI品類。POI名稱字段屬于文本特征，傳統(tǒng)的文本表示方法是基于向量空間模型(VSM模型)[1]：

空間向量模型需要一個“字典”，這個字典可以在樣本中產生，也可以從外部導入。上圖中的字典就是[好, 賓館, 海底, 拉面, 冰雪, ....... ，館]。我們對已校準的POI，先利用Lucene的中文分詞工具SmartCn[2]對POI名稱做預分詞處理，提取特征詞，作為原始粗糙字典集合。

有了字典后便可以量化地表示出某個文本。先定義一個與字典長度相同的向量，向量中的每個位置對應字典中的相應位置的單詞。然后遍歷這個文本，對應文本中的出現(xiàn)某個單詞，在向量中的對應位置，填入“某個值”（即特征詞的權重，包括BOOL權重，詞頻權重，TFIDF權重）?？紤]到一般的POI名稱都屬于短文本，本文采用BOOL權重。

在產生粗糙字典集合時，我們還統(tǒng)計了校準POI中，每個品類(type_id)，以及特征詞(term)在品類(type_id)出現(xiàn)的次數(文檔頻率)。分別寫入到表category_frequency和term_category_frequency，表的部分結果如下:

category_frequency表：

term_category_frequency表：

分別記：

這些統(tǒng)計量，將在后續(xù)的計算中發(fā)揮它們的作用。

特征選擇

現(xiàn)在，我們得到了一個“預輸入字典”：包括了所有已校準POI名稱字段的特征詞，這些特征詞比如：“88”、“11”， “3”、“auyi”、“中心”、“中國”、“酒店”、“自助餐”、“拉面”等。直觀感覺，“88”、“11”， “3”、“auyi”、“中國”這些詞對判斷品類并沒有多大幫助，但“酒店”、“自助餐”、“拉面”對判斷一個POI的品類卻可能起到非常重要作用。

那么問題來了，如何挑選出有利于模型預測的特征呢？這就涉及到了特征選擇。特征選擇方法可以分成基于領域知識的規(guī)則方法和基于統(tǒng)計學習方法。本文使用統(tǒng)計機器學習方法，輔助規(guī)則方法的特征選擇算法，挑選有利于判斷POI品類的特征詞。

基于統(tǒng)計學習的特征選擇算法

基于統(tǒng)計學習的特征選擇算法，大體可以分成兩種：

1.基于相關性度量(信息論相關)

2.特征空間表示(典型的如PCA)

文本特征經常采用的基于信息增益方法(IG)特征選擇方法[3]。某個特征的信息增益是指，已知該特征條件下，整個系統(tǒng)的信息量的前后變化。如果前后信息量變化越大，那么可以認為該特征起到的作用也就越大。
那么，如何定義信息量呢？一般采用熵的概念來衡量一個系統(tǒng)的信息量：

當我們已知該特征時，從數學的角度來說就是已知了該特征的分布，系統(tǒng)的信息量可以由條件熵來描述：

該特征的信息增益定義為：

信息增益得分衡量了該特征的重要性。假設我們有四個樣本，樣本的特征詞包括“火鍋”、“米粉”、“館”，我們采用信息增益判斷不同特征對于決策影響:

整個系統(tǒng)的最原始信息熵為：

分別計算每個特征的條件熵：

利用整個系統(tǒng)的信息熵減去條件熵，得到每個特征的信息增益得分排名(“火鍋”(1) > “米粉”(0.31) > “館”(0)) ，按照得分由高到低挑選需要的特征詞。

本文采用IG特征選擇方法，選擇得分排名靠前的N個特征詞（Top 30%）。我們抽取排名前20的特征詞：[酒店, 賓館, 火鍋, 攝影, 眼鏡, 美容, 咖啡, ktv, 造型, 汽車, 餐廳, 蛋糕, 兒童, 美發(fā), 商務, 旅行社, 婚紗, 會所, 影城, 烤肉]。這些特征詞明顯與品類屬性相關聯(lián)具有較強相關性，我們將其稱之為品類詞。

基于領域知識的特征選擇方法

基于規(guī)則的特征選擇算法，利用領域知識選擇特征。目前很少單獨使用基于規(guī)則的特征選擇算法，往往結合統(tǒng)計學習的特征選擇算法，輔助挑選特征。

本文需要解決的是POI名稱字段短文本的自動分類問題，POI名稱字段一般符合這樣的規(guī)則，POI名稱 = 名稱核心詞 + 品類詞。名稱核心詞對于實際的品類預測作用不大，有時反而出現(xiàn)”過度學習“起到負面作用。例如”好利來牛肉拉面館“， ”好利來“是它的名稱核心詞，在用學習算法時學到的很有可能是一個”蛋糕“品類（”好利來“和”蛋糕“品類的關聯(lián)性非常強，得到錯誤的預測結論）。

本文使用該規(guī)則在挑選特征時做了一個trick：利用特征選擇得到的特征詞（絕大部分是品類詞），對POI名稱字段分詞，丟棄前面部分（主要是名稱核心詞），保留剩余部分。這種trick從目前的評測結果看有5%左右準確率提升，缺點是會降低了算法覆蓋度。

分類模型

建模

完成了特征表示、特征選擇后，下一步就是訓練分類模型了。機器學習分類模型可以分成兩種：1）生成式模型；2）判別式模型?？梢院唵握J為，兩者區(qū)別生成式模型直接對樣本的聯(lián)合概率分布進行建模：

生成式模型的難點在于如何去估計類概率密度分布p(x|y)。本文采用的樸素貝葉斯模型，其"Naive"在對類概率密度函數簡化上，它假設了條件獨立：

根據對p(x|y)不同建模形式，Naive Bayes模型主要分成：Muti-variate Bernoulli Model （多項伯努利模型）和Multinomial event model（多項事件模型）[4]。一次伯努利事件相當于一次投硬幣事件（0，1兩種可能），一次多項事件則相當于投色子（1到6多種可能）。我們結合傳統(tǒng)的文本分類解釋這兩類模型：

多項伯努利模型
已知類別的條件下，多項伯努利對應樣本生X成過程：遍歷字典中的每個單詞(t1,t2...t|V|)，判斷這個詞是否在樣本中出現(xiàn)。每次遍歷都是一次伯努利實驗，|V|次遍歷：

 其中1(condition)為條件函數，該函數表示當條件成立是等于1，不成立時等于0；|V|則表示字典的長度。

多項事件模型

已知類別的條件下，多項事件模型假設樣本的產生過程：對文本中第k個位置的單詞，從字典中選擇一個單詞，每個位置k產生單詞對應于一次多項事件。樣本X=(w1,w2...ws)的類概率密度：

采用向量空間模型表示樣本時，上式轉成：

其中N(ti,X) 表示特征詞i在樣本X出現(xiàn)的次數。

參數估計

好啦，一大堆無聊公式的折磨后，我們終于要見到勝利的曙光：模型參數預估。一般的方法有***似然估計、***后驗概率估計等。本文使用的是多項伯努利模型，我們直接給出多項伯努利模型參數估計結論：

還記得特征表示一節(jié)中統(tǒng)計的term_category_frequency和category_frequency兩張表嗎？此時，就要發(fā)揮它的作用了！我們，只需要查詢這兩張表，就可以完成參數的估計了，是不是很happy? 過程雖然有點曲折，但是結果是美好的~ 具體參數意義可以參見特征表示一節(jié)。

接下來的coding的可能需要關注的兩個點：

• 參數平滑
  在計算類概率密度p(X | Cj)時，如果在類Cj下沒有出現(xiàn)特征ti ，p(ti | Cj)=0，類概率密度連乘也將會等于0，額，對于一個樣本如果在某條件下某個特征沒有出現(xiàn)，便認為她產生的可能等于零，這樣的結論實在是過武斷，解決方法是加1平滑:
  
  其中，|C|表示樣本的類別數據。

• 小數溢出
  在計算類概率密度時多個條件概率（小數）連乘，會存在著超過計算機能夠表示的最小數可能，為避免小數溢出問題，一般將類概率密度計算轉成成對數累和的形式。
  
  另外，如果在計算p(ti | Cj)時過小，取對數后將會得到一個負無窮的值，需要對p(ti | Cj)截斷處理：小于某個閾值（如1E-6）時，采用該閾值替代。

算法預測

本節(jié)將結合前面三節(jié)內容，給出算法具體的計算預測過程。為簡化問題，我們假設字典為：[拉面，七天，牛肉，館]，并且只有火鍋和快餐兩個品類，兩類樣本的數量均為8個。以“好 利 來 牛肉 拉面 館為例”：

• 對測試樣本做中文分詞，判斷”牛肉“屬于品類詞，丟棄品類詞”牛肉“前面的部分，并提取樣本的特征詞集合得到：[牛肉 拉面 館]
• 根據字典，建立向量空間模型：x = [1, 0, 1, 1]
• 利用Naive Bayes模型分類預測，我們給出火鍋和快餐兩類樣本的term_category_frequency統(tǒng)計：

樣本屬于快餐的概率高于屬于火鍋概率4倍，預測樣本屬于快餐置信度明顯高于火鍋概率。

算法隨機抽取2000條未校準的POI數據進行評測，算法的評測指標有兩個：覆蓋度和準確率。覆蓋度是指算法可預測的樣本數量在整個測試樣本集中的比例。由于采用特征選擇后，一些POI名稱因不包含特征詞集合而無法預測，算法的評測的覆蓋度為84%。算法的準確率是指，可預測正確樣本在整個測試樣本集中的比例，算法評測的正確率為91%。

總結

• 機器學習解決問題最關鍵的一步是找準問題：這種問題能否用機器學習算法解決？是否存在其他更簡單的方法？簡單的如字符串匹配，利用正則就可以簡單解決，才機器學習方法反而很麻煩，得不償失。
• 如果能機器學習算法，如何去表示這個機器學習問題，如何抽取特征？又可能歸類哪類機器模式（分類、聚類、回歸？）
• 找準問題后，可以先嘗試一些開源的機器學習工具，驗證算法的有效性。如果有必要，自己實現(xiàn)一些機器算法，也可以借鑒一些開源機器學習算法實現(xiàn)。