前言在美团商户数据中心(MDC)中,有超过100万条经过校准和审核的POI数据(我们一般将商户标记为POI,POI基本信息包括:店名、品类、电话、地址、坐标等)。如何利用这些标定后的POI数据挖掘出有价值的信息,本文做了一些尝试:利用机器学习的方法对缺失类别的POI数据进行自动标注。例如,店名“好在来牛肉拉面馆”的POI会自动标注“小吃”类目。机器学习解决问题的一般过程:本文将遵循:1)特征表示;2)特征选择;3)基于朴素贝叶斯分类模型;4)分类预测,四个部分依次展开。特征表明我们需要先将实际问题转化为计算机可识别的形式。对于POI,反映了POI品类的一个重要特征是POI店的名称,因此问题转化为根据POI店名识别POI品类。POI名称字段是一个文本要素。传统的文本表示方法是基于向量空间模型(VSM模型)[1]:空间向量模型需要一个“字典”,可以在样本中生成,也可以从外部导入。上图中的字典是【好、酒店、海底、拉面、冰雪、……、大厅】。对于标定后的POI,我们首先使用Lucene的中文分词工具SmartCn[2]对POI名称进行预分词,提取特征词,作为原始粗字典集。有了字典,文本就可以量化。首先定义一个与字典长度相同的向量,向量中的每个位置对应字典中对应位置的单词。然后遍历文本,对应文本中的某个词,在vector中对应位置填入“某个值”(即特征词的权重,包括BOOL权重、词频权重、TFIDF权重).考虑到一般的POI名称都是短文本,本文使用BOOL权重。在生成粗略词典集时,我们还统计了每个类别(type_id)和类别(type_id)中的特征词(term)在校准POI中的出现次数(文档频率)。分别写入表category_frequency和term_category_frequency,表的部分结果如下:特征选择现在,我们有一个“预打字词典”:包括标定后的POI名称字段的所有特征词,如:“88”、“11”、“3”、“auyi”、“center”、“China”、“Hotel”、“Buffet”、“Ramen”等。直观上,“88”、“11”、“3”、“auyi”、“China”这些词对于判断类别帮助不大,但“酒店”、“自助餐”和“拉面”虽然有助于判断一个POI的类别,但可能非常重要。那么问题来了,如何选择有利于模型预测的特征呢?这就涉及到特征选择。特征选择方法可以分为基于领域知识的基于规则的方法和基于统计学习的方法。本文采用统计机器学习方法和辅助规则法的特征选择算法,选取有利于判断POI类别的特征词。基于统计学习的特征选择算法基于统计学习的特征选择算法大致可以分为两种:1.基于相关性度量(信息论相关)2.特征空间表示(典型的如PCA)文本特征往往是基于信息增益方法(IG)的特征选择方法[3]。某个特征的信息增益是指在该特征已知的情况下,整个系统的信息量的变化。如果前后信息量的变化更大,那么可以认为该特征的作用更大。那么,如何定义信息量呢?一般用熵的概念来衡量一个系统中的信息量:当我们知道了特征,从数学的角度就知道了该特征的分布,系统中的信息量可以描述为条件熵:信息增益定义为:信息增益分数衡量特征的重要性。假设我们有四个样本,样本的特征词包括“火锅”、“米粉”和“餐厅”。我们使用信息增益来判断不同特征对决策的影响:米粉(A)火锅(B)餐厅(C)类别110火锅011火锅100零食101零食整个系统最原始的信息熵是:分别计算每个特征的条件熵:用整个系统的信息熵减去条件熵得到每个特征的信息增益得分排名(《火锅》(1)>“米线”(0.31)>“关”(0)),根据评分从高到低选??择需要的特征词。本文采用IG特征选择的方法,选取前N个特征词(Top30%)。我们抽取前20个特征词:【酒店、酒店、火锅、摄影、眼镜、美容、咖啡、ktv、造型、汽车、餐厅、蛋糕、儿童、美发、商务、旅行社、婚纱、俱乐部、电影院,烧烤]。这些特征词与类别属性有明显关联,具有很强的相关性,我们称之为类别词。基于领域知识的特征选择方法基于规则的特征选择算法使用领域知识来选择特征。目前,基于规则的特征选择算法很少单独使用,往往与统计学习特征选择算法相结合,辅助特征选择。本文需要解决POI名称字段短文本的自动分类问题。POI名称字段一般符合这样的规则,POI名称=名称核心词+类别词。名称的核心词对实际类别预测影响不大,有时“过度学习”会产生负面影响。比如“好利来牛肉拉面餐厅”,“好莱坞”是它名字的核心词,很可能是使用学习算法学习到的“蛋糕”类别(“好莱坞”和“蛋糕”类别非常接近相关,得到错误的预测)。本文利用这个规则在选择特征的时候做了一个技巧:使用特征选择得到的特征词(多为类别词),对POI名称字段进行切分,舍弃前面的部分(主要是名称的核心词),保留休息。根据目前的评估结果来看,这个trick可以提高5%左右的准确率,但缺点是会降低算法的覆盖率。分类模型建模完成特征表示和特征选择后,下一步就是训练分类模型。机器学习分类模型可以分为两种类型:1)生成模型;2)判别模型。可以简单认为,两者的区别在于生成模型直接对样本的联合概率分布进行建模:生成模型的难点在于如何估计类概率密度分布p(x|y)。本文采用的朴素贝叶斯模型,其“朴素”简化了类概率密度函数,假设条件独立:根据p(x|y)的建模形式不同,朴素贝叶斯模型主要分为:变量伯努利模型(multipleBernoullimodel)和Multinomialeventmodel(多事件模型)[4]。一次伯努利事件相当于一次抛硬币事件(0、1两种可能),多次事件相当于一次骰子(1到6种可能)。我们结合传统的文本分类来解释这两类模型:在多个伯努利模型已知类别的情况下,多项式伯努利对应的样本生成过程:遍历字典中的每个单词(t1,t2..t|V|),判断该词是否出现在样本中。每次遍历都是一次伯努利实验,|V|traversals:其中1(condition)是一个条件函数,意思是当条件为真时,等于1,不为真时,等于0;|V|表示字典的长度。在多事件模型已知类别的情况下,多事件模型假设样本的生成过程:对于文本中第k个位置的词,从字典中选择一个词,每个位置k产生一个词对应一个多重事件。样本的类概率密度X=(w1,w2...ws):当用向量空间模型表示样本时,上式转化为:其中N(ti,X)表示特征出现的次数单词i出现在样本X中。参数估计完成。在一堆无聊的公式之后,我们终于要看到胜利的曙光了:模型参数估计。一般的方法有最大似然估计,最大后验概率估计等。本文使用的是多项式伯努利模型,我们直接给出多项式伯努利模型参数估计结论:还记得特征表示部分的term_category_frequency和category_frequency这两个表吗?这个时候,就该发挥它的作用了!我们只需要查询这两个表就可以完成参数估计。是不是很开心?虽然过程有点曲折,但是结果还是很美好的~具体参数的含义可以参考特征表示部分。在接下来的编码中可能需要注意的两点:参数平滑在计算类别概率密度p(X|Cj)时,如果特征ti没有出现在类别Cj下,则p(ti|Cj)=0,类概率密度的乘积也会等于0,呃,对于一个样本来说,如果某个特征在某个条件下没有出现,就认为它可能等于0。这样的结论太武断了,解决方法是加1平滑:其中,|C|表示样本的类别数据。在计算类概率密度时,多个条件概率(小数)相乘可能会超过计算机所能表示的最小数。为避免小数溢出问题,类概率密度计算一般转为对数累加。形式。另外,如果p(ti|Cj)的计算量过小,取对数后会得到一个负无穷大的值,需要截断p(ti|Cj):当小于某个阈值时(比如1E-6),改用这个阈值。算法预测本节将结合前面三节的内容给出算法的具体计算和预测过程。为了简化问题,我们假设字典是:[拉面,七日,牛肉,餐厅],并且只有火锅和快餐两个类别,两个类别的样本数都是8。以“好利来牛肉拉面馆”为例:对测试样本进行中文词切分,判断“牛肉”属于类别词,舍弃类别词“牛肉”前面的部分,提取特征词集的样本得到:[牛肉拉面馆]根据字典,建立向量空间模型:x=[1,0,1,1]使用朴素贝叶斯模型分类预测,我们给出两种类型的term_category_frequency统计火锅和快餐的样本:特征词\类别火锅(C1)快餐(C2)拉面05齐天20牛肉42餐厅21样本属于快餐的概率比属于火锅的概率,预测样本属于快餐的置信度明显高于火锅的概率。算法随机选取2000条未标定的POI数据进行评价。该算法有两个评价指标:覆盖率和准确率。覆盖率是指算法能够预测的样本数量占整个测试样本集的比例。由于部分POI名称在采用特征选择后由于不包含特征词集而无法预测,因此算法评估的覆盖率为84%。算法的准确率是指可预测的正确样本占整个测试样本集的比例,算法评估的准确率为91%。总结机器学习解决问题最关键的一步就是识别问题:这种问题能不能用机器学习算法来解决?还有其他更简单的方法吗?简单的比如字符串匹配,使用正则化可以轻松解决,但是机器学习的方法很麻烦,得不偿失。如果可以使用机器学习算法,如何表示这个机器学习问题,如何提取特征?以及什么样的机器模型可以分类(分类、聚类、回归?)确定问题后,可以尝试一些开源的机器学习工具来验证算法的有效性。如果有必要,自己实现一些机器算法,或者学习一些开源的机器学习算法。
