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

機(jī)器學(xué)習(xí)解決問題的一般過程：

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

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

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

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

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

category_frequency表：

term_category_frequency表：

分別記：

    A(i,j) = 特征詞term(i) 在品類為type_id(j)出現(xiàn)的次數(shù)count
    T(j) = 品類為type_id(j)在樣本集出現(xiàn)的次數(shù)   
    N = 已校準(zhǔn)POI數(shù)據(jù)集的數(shù)量
這些統(tǒng)計(jì)量，將在后續(xù)的計(jì)算中發(fā)揮它們的作用。

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

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

基于統(tǒng)計(jì)學(xué)習(xí)的特征選擇算法
基于統(tǒng)計(jì)學(xué)習(xí)的特征選擇算法，大體可以分成兩種：
1.基于相關(guān)性度量(信息論相關(guān))
2.特征空間表示(典型的如PCA)

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

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

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

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

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

分別計(jì)算每個(gè)特征的條件熵：

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

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

基于領(lǐng)域知識的特征選擇方法
基于規(guī)則的特征選擇算法，利用領(lǐng)域知識選擇特征。目前很少單獨(dú)使用基于規(guī)則的特征選擇算法，往往結(jié)合統(tǒng)計(jì)學(xué)習(xí)的特征選擇算法，輔助挑選特征。

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

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

#分類模型

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

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

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

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

其中1(condition)為條件函數(shù)，該函數(shù)表示當(dāng)條件成立是等于1，不成立時(shí)等于0；|V|則表示字典的長度。
多項(xiàng)事件模型
已知類別的條件下，多項(xiàng)事件模型假設(shè)樣本的產(chǎn)生過程：對文本中第k個(gè)位置的單詞，從字典中選擇一個(gè)單詞，每個(gè)位置k產(chǎn)生單詞對應(yīng)于一次多項(xiàng)事件。樣本X=(w1,w2...ws)的類概率密度：

采用向量空間模型表示樣本時(shí)，上式轉(zhuǎn)成：

其中N(ti,X) 表示特征詞i在樣本X出現(xiàn)的次數(shù)。
##參數(shù)估計(jì)
好啦，一大堆無聊公式的折磨后，我們終于要見到勝利的曙光：模型參數(shù)預(yù)估。一般的方法有最大似然估計(jì)、最大后驗(yàn)概率估計(jì)等。本文使用的是多項(xiàng)伯努利模型，我們直接給出多項(xiàng)伯努利模型參數(shù)估計(jì)結(jié)論：

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

接下來的coding的可能需要關(guān)注的兩個(gè)點(diǎn)：

參數(shù)平滑
在計(jì)算類概率密度p(X | Cj)時(shí)，如果在類Cj下沒有出現(xiàn)特征ti ，p(ti | Cj)=0，類概率密度連乘也將會等于0，額，對于一個(gè)樣本如果在某條件下某個(gè)特征沒有出現(xiàn)，便認(rèn)為她產(chǎn)生的可能等于零，這樣的結(jié)論實(shí)在是過武斷，解決方法是加1平滑:

其中，|C|表示樣本的類別數(shù)據(jù)。
小數(shù)溢出
在計(jì)算類概率密度時(shí)多個(gè)條件概率（小數(shù)）連乘，會存在著超過計(jì)算機(jī)能夠表示的最小數(shù)可能，為避免小數(shù)溢出問題，一般將類概率密度計(jì)算轉(zhuǎn)成成對數(shù)累和的形式。

另外，如果在計(jì)算p(ti | Cj)時(shí)過小，取對數(shù)后將會得到一個(gè)負(fù)無窮的值，需要對p(ti | Cj)截?cái)嗵幚恚盒∮谀硞€(gè)閾值（如1E-6）時(shí)，采用該閾值替代。
算法預(yù)測
本節(jié)將結(jié)合前面三節(jié)內(nèi)容，給出算法具體的計(jì)算預(yù)測過程。為簡化問題，我們假設(shè)字典為：[拉面，七天，牛肉，館]，并且只有火鍋和快餐兩個(gè)品類，兩類樣本的數(shù)量均為8個(gè)。以“好 利 來 牛肉 拉面 館為例”：

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

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

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

#總結(jié)

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