數據挖掘：基于機器學習方法的POI品類推薦算法

作者：hong 2015-07-28 15:41:06

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

前言

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

機器學習模型

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

特征表示

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

向量空間模型

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

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

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

category_frequency表：

category_frequency

term_category_frequency表：

category_frequency

分別記：

這些統計量，將在后續的計算中發揮它們的作用。

特征選擇

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

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

基于統計學習的特征選擇算法

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

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

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

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

$H(Y)=-\sum_{i=1}^{n}p\left ( y_{i}\right )\log p\left ( y_{i} \right )$

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

$H\left ( Y|X \right )=\sum _{x}p\left ( x \right )H\left ( Y|X=x \right )=-\sum _{x}\sum _{y}p\left ( x,y \right )\log p\left ( y|x \right )$

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

$IG(X)=H(Y)-H(Y|X)$

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

米粉(A)	火鍋(B)	館(C)	品類
1	1	0	火鍋
0	1	1	火鍋
1	0	0	小吃
1	0	1	小吃

整個系統的最原始信息熵為：

$H\left ( Y \right )=-\sum _{i=1}^{2}p\left ( y_{i} \right )\log p\left ( y_{i} \right )=-2*\frac{1}{2}*\log \frac{1}{2} = 1$

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

$H\left ( C|A \right )=-\sum_{i=1}^{2}\sum_{j=1}^{2}p\left ( x,y \right )\log p\left ( y|x \right )=0-0- \frac{1}{2}\log \frac{2}{3} -\frac{1}{4}\log \frac{1}{3} =0.69$

$H(Y|B)=0-0-0-0=0$

$H(Y|C)=-4*\frac{1}{4}*\log \frac{1}{2}=1$

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

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

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

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

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

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

分類模型

建模

完成了特征表示、特征選擇后，下一步就是訓練分類模型了。機器學習分類模型可以分成兩種：1）生成式模型；2）判別式模型。可以簡單認為，兩者區別生成式模型直接對樣本的聯合概率分布進行建模：

$p\left ( y|x \right )=\frac{p\left ( y \right )p\left ( x|y \right )}{p\left ( x \right )} \sim p\left ( x|y \right )$

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

$p(X|y)=p\left (x_{1},x_{2}...x_{n}|y \right )=p(x_{1}|y)p(x_{2}|y,x_{1})...p(x_{n}|y,x_{1},x_{2}...x_{n-1}) =p(x_{1}|y)p(x_{2}|y)...p(x_{n}|y)$

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

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

$p(X|C_{j})=\prod_{i=1}^{|V|}=1(t_{i}\in X)p(t_{i}|C_{j}) + 1(t_{i}\notin X)(1-p(t_{i}|C_{j}))$
其中1(condition)為條件函數，該函數表示當條件成立是等于1，不成立時等于0；|V|則表示字典的長度。

多項事件模型

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

$p(X|C_{j})=p(w_{1},w_{2},w_{3}...w_{s}|C_{j})=\prod_{i=1}^{s}p(w_{i}|C_{j})$

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

$p(X|C_{j})=\prod_{i=1}^{|V|}p(t_{i}|C_{j})^{N(t_{i},X)}$

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

參數估計

好啦，一大堆無聊公式的折磨后，我們終于要見到勝利的曙光：模型參數預估。一般的方法有***似然估計、***后驗概率估計等。本文使用的是多項伯努利模型，我們直接給出多項伯努利模型參數估計結論：
$\Theta _{j}=p(y=C_{j})=\frac{\sum_{k=1}^{N}1(y_{k}=C_{j})}{\sum_{k=1}^{N}\sum_{j=1}^{C}1(y_{k}=C_{j})}=\frac{T\left ( j \right )}{N}$

$\Theta _{i|j}=p\left ( t_{i}|C_{j} \right )=\frac{\sum_{k=1}^{N}1(y_{k}=C_{j}1(t_{i}\in C_{j}))}{\sum_{k=1}^{N}1(y_{k}=C_{j})}=\frac{A(i,j)}{N}$

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

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

參數平滑
在計算類概率密度p(X | Cj)時，如果在類Cj下沒有出現特征ti ，p(ti | Cj)=0，類概率密度連乘也將會等于0，額，對于一個樣本如果在某條件下某個特征沒有出現，便認為她產生的可能等于零，這樣的結論實在是過武斷，解決方法是加1平滑:
$\Theta _{i|j}=p\left ( t_{i}|C_{j} \right )=\frac{1+\sum_{k=1}^{N}1(y_{k}=C_{j}1(t_{i}\in C_{j}))}{|C|+\sum_{k=1}^{N}1(y_{k}=C_{j})}=\frac{1+A(i,j)}{|C|+N}$
其中，|C|表示樣本的類別數據。
小數溢出
在計算類概率密度時多個條件概率（小數）連乘，會存在著超過計算機能夠表示的最小數可能，為避免小數溢出問題，一般將類概率密度計算轉成成對數累和的形式。
$\log p(X|C_{j})=\log p(t_{1},t_{2},t_{3}...t_{|V|}|C_{j})=\sum_{i=1}^{|V|}\log p\left ( t_{i}|C_{j} \right )$
另外，如果在計算p(ti | Cj)時過小，取對數后將會得到一個負無窮的值，需要對p(ti | Cj)截斷處理：小于某個閾值（如1E-6）時，采用該閾值替代。

算法預測

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

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

特征詞\品類	火鍋(C1)	快餐(C2)
拉面	0	5
七天	2	0
牛肉	4	2
館	2	1

$p(C_{1})p(X|C_{1})=\frac{8}{8 + 8}\frac{0 + 1}{8 + 2}(1-\frac{2 + 1}{8 + 2})\frac{4+1}{8+2}\frac{2+1}{8+2}=0.005$

$p(C_{2})p(X|C_{2})=\frac{8}{8+8}\frac{5+1}{8+2}(1-\frac{0+1}{8+2})\frac{2+1}{8+2}\frac{1+1}{8+2}=0.02$

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

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

總結

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

責任編輯：李英杰來源：美團技術部

機器學習算法數據挖掘