经典聚类算法及在互联网的应用

此处并不会列举每一种聚类(Clustering)算法,因为学术界Clustering算法如果真要细分,还真有很多变种。此处只会介绍几种在我近几年互联网工作生涯中实际碰到的具体问题, 以及如何使用Clustering算法解决这些问题。

一般来说,我们可以将Clustering认为是将出现的数据进行Data Segmentation,也就是经常说的哲理: 物以类聚。 从机器学习的观点来看, Clustering算是Unsupervised Learning,或者叫做Learning by Observation,根据观察到的情况进行Clustering。 因为形成簇的数据都被聚到一起,所以Clustering 方法也可以用来发现噪音或是异常点。

Clustering 算法大致可以分为以下几类(参见Data Mining Concepts and Techniques):

  1. Partitioning Methods:这是一类经典的,最简单的聚类方式,就是直接按照类内的点距离最近,类间距离足够远的原则进行数据Clustering。该类方法比较经典的方法有K-Means 和K-Medoids。下文中会以广告分段问题来具体介绍K-Means的实现(K-Medoids类似)
  2. Hierachical Methods:层次Clustering算法,又大致分为bottom-up和top-down两种思路,bottom-up为自底向上,逐渐合并离得比较近的类以形成更大的类,top-down为一种divisive的思路,逐渐对离得比较远的类进行分裂。下文中会以如何合并搜索引擎中的同意,近义词词形成簇的的方式具体介绍bottom-up hierachical methods。
  3. Density-based Methods:以上两种方法基本上都是在高维空间中将数据聚成球形的多个类的方法,却不能处理非球形的聚类,Density-based Methods就是解决非球形数据的聚类方法。
  4. Model-based Methods:对数据进行建模,之后使用观察到的数据预估模型参数,比较经典的使用EM方法,先假设数据服从某种分布(例如k个高斯分布),并且这k个高斯分布由一系列隐随机变量决定。之后在E步预估这些隐随机变量,而在M步固定这些隐随机变量后,使用最大似然估计迭代得到最优参数。

文章以下内容将介绍3种聚类方法解决3个问题:

  1. 使用K-Means方法对广告受众网民进行Data Segmentation。
  2. 使用Bottom Up Hierachical Clustering方法对搜索引擎query进行聚类以进行流量推荐。
  3. 使用EM方式寻找数据中的隐藏主体。

 使用K-Means方法对广告受众网民进行Data Segmentation

K-Means是一种球形的聚类,在二维空间中,类别会被聚成以圆心为中心的圆,三维空间中则会被聚成以球心为中心的球状簇(当然,这与选择的相似度度量有关,例如使用cosine计算归一化后的两个向量长度,就会变成计算二向量的夹角)

在K-Means算法运行前,有两个因素比较重要: 数据预处理和距离度量方法。具体距离度量参见博文相似度度量 ,数据预处理则包括数据归一化, 去除噪音等操作。

因为K-Means算法本身较为简单,此处直接给出Andrew Ng机器学习公开课教案中的伪代码:

k-means

其中uj为第j个簇的中心点,ci为第i条数据的簇类别。基本步骤就是遍历数据,每一轮迭代,先计算当前数据与哪个类中心最近,该条数据属于距离最近的簇,之后根据新计算出来的每条数据的类别,更新类中心。下图给出在指定数据上给出2个类的4轮迭代情况:

k-means-4-iteration

使用distortion function度量分类的好坏情况, distortion 越小越好,当然,一般distortion大小需要和类别 k 的数量间进行权衡。

distortion_function

应用: 虽然k-means堪称最简单的算法,但之前在实习时,在前东家还是用了一把,应用场景是使用MSN用户的注册信息(年龄,喜好,性别),以及MSN用户在 msn.com上经常访问的导航类别,搜索关键词等数据,使用决策树选出区分度较大的特征构成特征向量,使用L1-Norm进行归一化后,对特征向量进行Clustering。之后按Clustering向广告主售卖这些用户的pv。 该模式的优势是具有一定的兴趣定向作用。

 

右侧即为MSN展示广告。当然,该方法已经是2007年所使用的方法,现在相信MS已经使用更精准的方法了 。

该过程中尝试较多的是如何选择合适的类别数量k值,以及如何初始化初始类中心。当时迫于项目进度,k值最后根据经验并进行了粗略的搜索选择,初始类中心则使用在相同k值得情况下进行多次随机初始化Clustering

使用Bottom Up Hierachical Clustering方法对搜索引擎query进行聚类以进行流量推荐

例如在搜索引擎中, 很多网民的query意图的比较类似的,对这些query进行聚类,一方面可以使用类内部的词进行关键词推荐; 另一方面, 如果聚类过程实现自动化, 则也有助于新话题的发现;同时还有助于减少存储空间等。

例如:

训龙记国语  训龙记2 寻龙记  训龙记博克岛的骑手  驯龙记电影

骂人大全    骂人不带脏字的顺口溜    骂人带脏字越毒越好  骂人脏字的狠话

要设计层次聚类,就需要考虑一下几个因素及环节:

  1. 使用何种聚类算法: top-down 还是bottom-up 还是其他
  2. clusting的合并策略
  3. 使用哪些特征
  4. 如何度量距离
  5. 使用何种评估标准对效果进行评估

确定以上5个因素后,聚类算法也就确定了。

层次聚类

聚类算法:考虑到实现的复杂度, 一开始我们就确定使用bottom-up的方式作为聚类策略;后续也就没有尝试top-down的方式。

clusting的合并策略:

一般有两类合并策略: 选取最相近的两个clustering进行合并;求连通分量。 因为寻找相近cluster的方式, 时间复杂度会达到O(n^2), 所以最后决定使用连通分量。

特征: 我们使用字面特征及query在session中的共现特征; 例如, 对字面进行切词后的term(做适当过滤降维:idf太小则过滤)

距离函数, 尝试过cosine和jaccard后, 最终使用jaccard作为距离度量。

也可关注微博: weibo.com

或是直接访问: http://semocean.com

PageRank的经济学效用解释

google大名鼎鼎的pagerank算法大家都耳熟能详,基本的思路就是: 网页的重要性由指向该网页的链接,及指向网页的重要性决定。
那从经济学的角度, 背后隐藏的深层含义是什么呢?  说简单点,就是‘具有流动性的市场对商品价值的客观定价’。
我们先举一个简单而又经典的例子: 假设在原始社会中, 没有货币的概念, 所有的交换均为物物交换。 且生产社会中只有三个生产者:  农夫(使用F表示), 生产衣服的人(使用C表示)和生产工具的人(使用M表示)。 三个生产者生产出来的物品, 除一部分留己自用外, 其余均用于与其余二人进行交换。 交换关系如下:
图1: 三生产者的交换比例关系
F M C
F 1/2 1/3 1/2
M 1/4 1/3 1/4
C 1/4 1/3 1/4
图2:三生产者的交换关系邻接关系
以农民为例,除1/2生产的农作为自行享用外,剩余1/4与工具制造人换取他制造的1/3的工具,用剩下的1/4与衣服制造人交换他生产的1/2的衣服。 则根据列昂惕夫生产投入产出理论, 在自由市场下,交换的比例也即反映出该产品的内在价值。 以上图为例,假设:
一份农产品的内在价值为x1,一份生产出的工具内在价值为x2,一份衣服的为x3,则获得方程如下:
1/2 * x1 + 1/3 * x2 +  1/2 * x3 = x1
1/4 * x1 + 1/3 * x2 + 1/4 * x3 = x2
1/4 * x1 + 1/3 * x2 + 1/4 * x3 = x3
即可用解线性方程组的方法解除各内在价值。 该方程组背后的思想是: 任一物品的价值由自由市场中其他商品对其的认可程度决定。  后续会讲到, PageRank中迭代求稳定特征向量的过程, 其实就相当于是在自由市场中, 货物经过长时间流通后所反映出来的市场价值认可程度。
上述例子是在知道了邻接矩阵(转移关系)的情况下直接求解内在价值的过程。 如果我们对每种物品进行初始定价, 则能够计算在该转移矩阵的作用下,物品的价格在市场的作用下逐渐趋向于内在价格。
又例如:
教科书中一个非常经典的例子,是小镇上已婚女性和单身女性每年的数量问题:某小镇上,每年30%的已婚女性离婚,20%的单身女性结婚,镇上有8000已婚女2000单身女,假设小镇上女性总量为常数,分别求一年,二年后的女性数量?
求解方式为构建已婚,单身女性的转移矩阵A=[[0.7, 0.2],[0.3, 0.8]]   (此处使用python第三方库 numpy方式表示matrix)   x=[8000, 2000]为当前已婚,单身女的数量向量。 则一年后小镇上已婚,单身女性的数量向量x1 = A*x  两年后为 x2 = A* x1 = A*A * x    ;  如将x 写为已婚,单身女性的比例, 则该过程为Markov Process(Markov Process为随机过程)
PageRank
PR其实就是随机过程在网页ranking过程中的应用,该算法假设网页都是有价值的, 且价值是可以传递的,同时价值传递时也会衰减。 价值大的节点传递给指向的网页的价值也比较大。该算法中的思想其实是个人类学的问题: 和权威的人关系紧密的人, 一般也较有权威; 也经常说: 你的收入和你关系最近的5个人类似  啥的说法都比较类似。
PR的计算方式如下:
其中PR(n)为节点n的PR值,它由指向n的节点q集合的PR值及系数w决定, 1/|V| 为随机跳转概率避免闭环
所有节点的PR值计算方式如上, 其中C即为转移矩阵。
实际应用中, 一般是制定PR的迭代次数作为停止条件。
而PR值其实就可以直接看作是一种价值转移直到稳定状态。
参考文献:
  1. 经济学原理
  2. The PageRank Citation Ranking: Bringing Order to the Web
也可关注微博: weibo.com/dustinsea
或是直接访问: http://semocean.com

google youtube 电影推荐算法

在面试实习生的时候,我有个习惯,就是面试快结束的时候,会像聊天一样和面试的学生聊一下他们对某个技术方向的看法。很多时候不是期望他们能提供什么灵感,也不期望能聊出太多结果,更多的是想通过这些沟通,看一下现在学生对这些问题的看法达到什么程度,而且这些沟通很能反映一个面试者的个性。 比如有些人对问题比较坚持, 或者叫做偏执,或者叫做执着,都能够反映出来。
前几天面试的时候到了最后环节的时候,忘了是说什么问题了,面试的实习生提到一般工业界使用的推荐算法都是比较简单的,不会去尝试复杂的算法。 我问他为什么,他说觉得工业界不会投入太多人力; 后来我告诉他还需要考虑处理的数据量和可维护性等因素。 当然他说的这个现象的确比较普遍: 工业界一般都倾向于使简单粗暴有效的算法,只有这些方法都搞不定时,才会尝试更复杂的潜在算法。
两个例子: 一个是 youtube 使用的电影推荐算法(参见论文: The Youtube Video Recommendation System);另一个例子就是Baidu关键词推荐系统中使用的级联二步图;  应该说Baidu关键词推荐系统中的级联二步图的思路是借鉴于youtube电影推荐算法并应用在关键词推荐的场景中。 下边就简单介绍下youtube Video推荐算法。
算法的思想其实比较简单:使用关联规则找到有关联的电影,计算权值后进行ranking推荐。其中的新意在于,这种关联关系能够进行多次传递,逐渐扩大和种子电影相关的电影集合(当然关系传递得越远,一般关联程度也会相应减弱)
具体的推荐过程可以分为3步:
建立video间的关系
建立video间关系的方式比较简单,使用关联规则中的共现方式即可。此处youtube使用的是24小时内session的co-visitation。具体为:
使用 r(vi, vj) = cij/f(vi,vj) 表示video i和video的关联程度, 其中 r为两个video/item的相关系数, ci为i,j共同出现次数, f 为 vi, vj归一化后的分母总量(最简单的方式就是ci * cj),这样就能找到相关的两个vedio
产生特定用户的video候选
该过程在经典信息检索中可以被理解为触发逻辑,及找到待推荐video/item的候选(触发逻辑在推荐系统中所处的位置及重要性参见另外一篇blog: 传统推荐引擎系统架构)
定义S为特定用户的种子video集合, 例如在youtube推荐系统中可以选择用户最新观看(或者最新完整观看的video),之后的问题就是怎么找到和种子词相关的video进行推荐。我们将其分为以下3步:
  1. 定义Cn(S)为和种子集合S相关联的,通过n步扩展后的推荐候选集合。 例如 C1(S) = 所有Ri的并, 其中Ri是与S中的vi相关联的v(寻找相关联v的过程参见上述:产生特定用户的video候选)。 相当于找到所有与S中种子vi想关联的v的并集;该做法的缺点是可能范围比较小且太相似。
  2. 使用Cn(S)进行触发, 即得到C(n-1)(S)后,再找到与C(n-1)(S)中每一个vi相关联的v,之后去除种子词S,我们称Cn(S)为对S的n步扩展。
  3. 同时在C(n)(S)中保留着每一个v被找到的原因, 便于后续ranking及给出explanation。
经过上述3步,对于特定user的候选video就触发完毕了。 该触发步骤可以说是该论文中的值得借鉴的点。 组里之前一位工程架构策略都很牛的同学指导实习生实现了一个通用的级联二步图算法框架, 该算法框架能够将有关联的节点的关系进行传递:
例如对于关键词,我们可以使用topic 主题(由topic model产生)建立关键词之间的跳转关系, 或是关键词中的核心term(一般是归一化后的核心term)建立跳转关系。 而该框架更令人着迷的是, 二步图的左右两边可以不是同样的item, 例如左边节点是keyword而右边是user, 则可以使用topic 直接建立keyword与user的关系进行推荐。
 Ranking
youtube 的ranking策略主要考虑以下3个因素:
  1. video质量, 这个可以通过网名对video投票打分得到。这一项和用户及对应偏好, 仅和video自身质量有关,就类似于搜索中pagerank得到的page质量度一样
  2. user specificity: 在触发后,可以通过使用user profile和电影的一些质量, 或是内容属性进行排序。这一项反映的是用户对电影的偏好得分
  3. divercification:特别是类似video这种兴趣相关的内容, divercification的引入就显得非常重要了,否则推荐的video会逐渐收拢到可数的一两个品类,可以使用的方式是限制每一个category video的推荐数量,或者本文中限制每个seed video出的video的数量;相反, divercification在不同的场景下可能不同,百度关键词推荐中, 根据种子词直接检索得到的结果需要考虑与种子query的强相关性, 此时divercification的引入, 或者引入的程度需要比较慎重保守。
当然, ranking机制一般都会非常复杂, 论文中此处只是简单介绍; 例如在构造百度关键词推荐系统的过程中, 我们引入了提词率预估, 效用预估, 价值预估等模型对返回结果进行ranking。同时也需要结合user interaction的样式,算法出口(interface)等进行调整。 具体ranking机制会在后续blog中介绍。
效果上, 级联二步图的引入,能够找到非常多靠谱的结果(当然二步图边的建立是核心,选对了边的建立方式,才会有好效果),具体效果数据就不便透露了:)   反正是基本上能够覆盖全部凤巢用户,每个客户都能推出数量惊人的关键词(当然,需要使用字面, 语义等技术进行后续filtering and ranking)
更进一步, 级联二步图是图关系挖掘的一个简单有效的特例, 使用类似于pagerank等经典算法, 也能够很好地找出类似的关系进行推荐。
参考来源:
  1. Davidson J, Liebald B, Liu J, et al. The YouTube video recommendation system[C]//Proceedings of the fourth ACM conference on Recommender systems. ACM, 2010: 293-296.
  2. Google Adwords
  3. 百度关键词推荐工具 :http://support.baidu.com/product/fc/4.html?castk=e6f89hg77d37ada65d612
或者直接访问 http://semocean.com

Collaborative Filtering根据近邻推荐时需要考虑的3要素

在使用类似于item-based 或user-based collaborative filtering构建推荐策略时,会涉及以下3个因素:
  1. 训练数据的归一化: 工业界推荐系统,包括商业系统中user的数量非常庞大(例如facebook是10亿级别),而user都会有自己对推荐内容打分的独特习惯,例如有些人对推荐内容,都会一股脑地接收,或是给出较高的评价,而有些人则会打较低的分数;有些人总给一样的分数,有些人的评价则分布较为广泛。这就需要对训练数据进行归一化,规避user个性化对模型的影响。
  2. 寻找一种适合数据的相似度度量方法:信息检索中的经典问题。在推荐系统中,第一步就是需要找到待推荐的候选, 以及之后的众多过滤,基本都是在使用合适的相似度度量过滤不相关的item,保留较为相关的item。例如在百度关键词推荐系统,以及触发系统中,大部分的工作,都是围绕相似度度量展开的(当然会比较复杂,包含各种特定场景,特定优化目标的相关性模型,以及使用topic model进行语义相关性计算)
  3. 高效的neigibors查找算法: 正如1中提到,工业界中待推荐处理的user/item较多,所以不可能为每个neighbor的pair都计算相似度,所以一般会对待计算的neighbors进行剪枝,仅计算‘靠谱’的neighbors进行计算。
训练数据归一化
最常用的训练数据归一化方法,非Mean-centering莫属,该方法的核心思想就是对于每一个user,找出其投票分值得中心,该用户其他的分值均会与该中心对比正负,即不关心投票分数的绝对值,而是看与均值的偏差: 如果投票分数为负数,说明是一个负向的打分,如果为正值,则说明正向。例如小明和小张都是用户,小明平均情况下对电影的打分是3分(例如满分是5,最低分是1),小张的打分均值是4,说明相比于小明,小张喜欢打高分,对于小张,一个电影如果打分为3就算是负向评价了,而同样的分值对于小明这样的分数是个中性的分数。
item-base CF中mean-centering计算方法如下:
user-based CF中mean-centering计算方法同理
设想这样一个场景: 小明和小张投票的均值均为3,小明投票时都投3分,而小张则各个分数的分布都有。如果小明和小张对于同一个电影都投了5分,此时小明和小张的投票体现出的信息是不同的: 小明平常都投3分而此时投了5分,这一票体现出的信息,比经常投5分的小张的一票体现出的信息要多(类似于TF-IDF中的IDF原理),而Mean-Centering则不能体现该特性。故我们引出另一种Normalization方法: Z-Score
Z-Score
核心思路是:如果一个用户投票的波动较大,则其投票的话语权要降低。具体计算公式与Mean-Centering相比,除以标准差即可。
极端的解释,就是经常投各种票的人, 其投票的权重会被降低;而投票分值一般不变,但突然改变以往习惯投票值得一票,体现出的信息较多。

在这插入另一篇文章中的思想: 就是经常投票给较多item的user的票的权值需要进行惩罚。例如在youtube推荐视频时,如果某个视频经常和很多视频一起被观看,则有可能不是因为他们相关,而是某个视频就是比较热,需要增加惩罚降低‘哈利波特’效应(具体思想可参见论文: the youtube video recommendation system),例如百度关键词推荐系统中就在级联二步图算法中对类似边的权值进行了惩罚(具体技术实现后续会有专门章节介绍)
Neighborhood 中的相似度度量方法参见前文,此处就不再复述。
至于高效的Neighbors计算方法,则可以在离线计算时设定固定Neighbors的具体N值(KNN中的N),之后在性能和效果之间权衡, 就像你知道的,很多时候,系统设计,就是在不停地在性能和效果之间做取舍达到平衡。
参考文献:
the youtube video recommendation system,James Davidson 等
RSs Handbooks
可关注微博:  weibo.com/dustinsea
也可直接访问:  http://semocean.com

adaboost

使用机器学习方法解决问题时,有较多模型可供选择。 一般的思路是先根据数据的特点,快速尝试某种模型,选定某种模型后, 再进行模型参数的选择(当然时间允许的话,可以对模型和参数进行双向选择)
因为不同的模型具有不同的特点, 所以有时也会将多个模型进行组合,以发挥‘三个臭皮匠顶一个诸葛亮的作用’, 这样的思路, 反应在模型中,主要有两种思路: Bagging和Boosting
Bagging
Bagging 可以看成是一种圆桌会议, 或是投票选举的形式,其中的思想是:‘群众的眼光是雪亮的’,可以训练多个模型,之后将这些模型进行加权组合,一般这类方法的效果,都会好于单个模型的效果。 在实践中, 在特征一定的情况下,大家总是使用Bagging的思想去提升效果。 例如kaggle上的问题解决,因为大家获得的数据都是一样的,特别是有些数据已经过预处理。
以下为Data Mining Concepts and Techniques 2nd 中的伪代码
基本的思路比较简单,就是:训练时,使用replacement的sampling方法, sampling一部分训练数据k次并训练k个模型;预测时,使用k个模型,如果为分类,则让k个模型均进行分类并选择出现次数最多的类(每个类出现的次数占比可以视为置信度);如为回归,则为各类器返回的结果的平均值。
在该处,Bagging算法可以认为每个分类器的权重都一样。
Boosting
在Bagging方法中,我们假设每个训练样本的权重都是一致的; 而Boosting算法则更加关注错分的样本,越是容易错分的样本,约要花更多精力去关注。对应到数据中,就是该数据对模型的权重越大,后续的模型就越要拼命将这些经常分错的样本分正确。 最后训练出来的模型也有不同权重,所以boosting更像是会整,级别高,权威的医师的话语权就重些。
以下为Data Mining Concepts and Techniques 2nd 中adaboost伪代码:
训练时:先初始化每个训练样本的权重相等为1/d  d为样本数量; 之后每次使用一部分训练样本去训练弱分类器,且只保留错误率小于0.5的弱分类器,对于分对的训练样本,将其权重 调整为 error(Mi)/(1-error(Mi)) ,其中error(Mi)为第i个弱分类器的错误率(降低正确分类的样本的权重,相当于增加分错样本的权重);
与测试:每个弱分类器均给出自己的预测结果,且弱分类器的权重为log(1-error(Mi))/error(Mi) ) 权重最高的类别,即为最终预测结果。
在adaboost中,  弱分类器的个数的设计可以有多种方式,例如最简单的就是使用一维特征的树作为弱分类器。
adaboost在一定弱分类器数量控制下,速度较快,且效果还不错。
我们在实际应用中使用adaboost对输入关键词和推荐候选关键词进行相关性判断。随着新的模型方法的出现, adaboost效果已经稍显逊色,我们在同一数据集下,实验了GBDT和adaboost,在保证召回基本不变的情况下,简单调参后的Random Forest准确率居然比adaboost高5个点以上,效果令人吃惊。。。。
Bagging和Boosting都可以视为比较传统的集成学习思路。 现在常用的Random Forest,GBDT,GBRank其实都是更加精细化,效果更好的方法。 后续会有更加详细的内容专门介绍。
参考内容:
Data Mining Concepts and Techniques 2nd
Soft Margin for Adaboost
也可关注我的微博: weibo.com/dustinsea
或是直接访问: http://semocean.com

分类模型在关键词推荐系统中的应用

以下内容均基于百度关键词推荐系统进行讨论
本文内容主要集中在使用机器学习方法判断两个短文本的相关性为基础构建商业关键词推荐系统。 为方便读者理解, 会先介绍该技术的具体应用背景及场景。
广告主在百度或google上进行广告投放时, 需要选择关键词, 以向搜索引擎表述自己想要覆盖的有商业价值的网民搜索流量。 在选择关键词后, 还需要设定具体的关键词匹配模式, 以告诉搜索引擎选择的关键词以何种方式去匹配网民的搜索。 举个例子: 网民在百度上搜索 ‘鲜花快送’, 假设商家A是卖花的, 搞鲜花速递业务的, 则A可以在百度凤巢系统中选择‘鲜花快送’这个关键词,同时设定匹配模式为精确匹配(即网民搜索和A在凤巢系统中选择的关键词完全一致时才出A的广告, 更多细节参见:http://yingxiao.baidu.com/), 假设B在凤巢中未选择‘鲜花快递’, 但选择了‘鲜花速递’, 假设B选择了广泛匹配(语义近似即匹配,具体参见http://yingxiao.baidu.com/), 则B的广告也会被触发(具体是否会展现, 还和出价, 质量度等诸多因素有关)
此时会面临一个问题: 广告主在凤巢系统中选择关键词时, 仅凭自己去想, 很难完全想到所有符合自己需求的关键词(网民的搜索query千奇百怪), 故需要提供工具, 帮助凤巢客户快速找到和自己推广意图一致或相近的关键词,即: 关键词推荐工具。
从交互上来看,可以将关键词工具看成一个搜索引擎,凤巢客户输入一个种子词(种子query),返回一个和种子query意图相近的推荐词list。
当然作为推荐系统, 其中还会包括属性披露, 推荐理由, 关键词行业分类, 关键词自动分组等支持, 这些内容会在接下来的其他博文进行介绍。
整个推荐流程大致如下
整个推荐流程, 大致分为5步:
  1. 基础日志,数据清洗即预处理
  2. 候选词触发: 根据输入种子query触发得到系统性能支持的最大关键词候选(供后续流程进行筛选过滤及排序),当然为保证性能, 该过程中会保留触发关键词的各种基础属性,例如PV, 行业, 主题等; 一般业界的检索,推荐系统会有较多触发逻辑逻辑,故触发出的关键词会比较多
  3. 相关性过滤:因为触发出的推荐关键词较多,故需要判断推荐关键词与种子query的相关性;既要保证召回,又需要保证准确性。
  4. ranking
  5. 使用业务,商业规则对最终结果进行排序调整及过滤(最经典的, 黄赌毒必须过滤删除)
对于相关性过滤,很早以前我们也是使用规则进行过滤,但随着规则数量的急剧增加,一方面导致系统架构性能下降,另外一方面也使系统策略越难约维护,故最终决定使用机器学习方法进行相关性过滤。
涉及到机器学习方法解决问题, 就会涉及到3方面的问题: 用哪些数据,准备哪些数据,如何处理数据? 使用哪些特征? 选用何种model ?
数据
一般来说,如果数据选择有问题, 那基本可以说后边无论再做多少努力, 这些努力都会付诸东流, 公司里这样的机器学习相关的项目也不少见: 几个人全情投入几个月或是1年多,效果总提不上去,回过头来发现数据就有问题,哭都没有眼泪。
所以一开始我们选择数据就比较慎重,还好关键词推荐工具隐性和显性反馈数据都还算比较丰富(推荐系统中都需要有这些信息, 将整个数据流形成完整的迭代闭环): 我们可以认为用户输入一个query并选择了这个query返回的某个候选推荐词的pair,就是一个正例(即模型是判断是否相关,相关为正例,不相关为),而输入一个query后,用户将返回的某个词放入垃圾箱(关键词工具交互上支持该操作),则query及被放入垃圾箱的关键词组成的pair,即为负例。
获得数据后, 很快就发现一个问题: 客户操作得到的正例, 就是毫无疑问的正例;但用户的负反馈(用户使用种子query搜索得到返回结果后,被扔入垃圾箱的的case)很多时候并不一定和query不相关, 甚至是很相关,只是因为用户个性化的原因导致客户认为这个case 不适合自己。
比如: 一个客户主要卖各种花茶, 像菊花茶, 桂花茶等,但他不卖茉莉花茶,此时如果用户输入花茶, 从相关性来说, 推荐‘菊花茶’,‘茉莉花茶’, ‘桂花茶’其实都是OK的,但用户将‘茉莉花茶’放入垃圾箱,因为他不卖该产品。其实并不能说明花茶和茉莉花茶不相关。
为了消除因个性化带来的负例不准的情况,我们人工标注了1.5W非个性化的负例。 并进行随机sampling, 使正负例数量基本相当。
最终使用1/10数据作为测试样本,9/10作为训练样本。
特征
数据准备就绪后,下一步就是如何选择合适的特征了。 因为整个关键词推荐系统所能触发的关键词各式各样, 各种类型千奇百怪, 所以如果直接使用各种地位特征(例如字面,或是ID类)的话,会导致特征空间较大而数据比较稀疏,导致完成分类基本上变成不可能完成的任务; 所以我们不能直接使用字面, ID作为特征进行分类,而是要使用更加泛化,高维的特征。
在特征选择过程中,我们也充分贯彻了站在巨人的肩膀上远眺的方式,充分利用手头的资源,例如短串核心判断,同意变化扩展等基础工具进行特征设计。更详细的特征此处不便于列出,仅列出两个有代表性的特征供大家参考。
  1. 推荐词与种子query经过切词后的相同term的长度之和与种子query经过切词后的term的长度之和的比值;类型为double类型。
  2. 推荐词基本切词后切词顺序包含 query, 特征值为1,默认值为0;类型为double类型。
  3. 推荐词,种子query的topic向量相似度。
  4. 。。。。更多高维特征。。。。。
利用多个类似的高维特征,就能很好地覆盖推荐词与种子query; 当然特征的设计会直接影响关键词推荐中相关性的定义,例如如果字面(重合)相关特征较多, 则推荐主要表现为字面相关,如特征主要为语义特征, 则推荐结果反映为语义相关。如果特征中有用户的历史行为信息特征(例如用户已经选择的关键词),则可以认为相关性模型就已经实现了个性化处理。
 模型
很多项目因为周期比较赶, 所以小步快跑的起步阶段并没有太多时间去做模型和参数的双向搜索,所以综合效率和时间的代价,选择了部分模型及在经验参数下的效果,进行模型的初选。
最终综合考虑性能,准确性和召回诸多因素下,选择了adaboost,在adaboost ratio 和 弱分类器数量上进行了参数实验。 准确性/召回 效果如下:
具体adaboost算法参见: adaboost介绍
WLRatio 300 500 1000 1500
0 0.87/0.89 0.87/0.91 0.87/0.9 0.86/0.91
-0.1 0.81/0.95 0.79/0.96 0.8/0.96 0.8/0.97
-0.2 0.74/0.98 0.73/0.98 0.73/0.98 0.73/0.98
-0.3 0.66/0.99 0.64/1 0.65/1 0.64/1
评估
以上内容均属于线下模型优化部分,所有的指标均可以线下获得, 但最终需要用线上的效果说话, 最后说服力的, 还是线上A/B Test, 因为是后台策略的升级, 故这样的实验在成熟的A/B test框架下比较容易做; 线上实验的最终效果也比较符合预期, 保证准确性的情况下召回大为提升(此处就不贴具体数值)
后文:后来将adaboost直接替换为Random Forest,在未改变模型的基础上效果立刻提升非常多,可见模型选择也较为重要。
参考文献:
百度凤巢关键词工具: www2.baidu.com
Data.Mining.Concepts.and.Techniques.2nd.Ed
也可关注微博: weibo.com
或是直接访问: http://semocean.com

经典聚类算法及在互联网的应用

此处并不会列举每一种聚类(Clustering)算法,因为学术界Clustering算法如果真要细分,还真有很多变种。此处只会介绍几种在我近几年互联网工作生涯中实际碰到的具体问题, 以及如何使用Clustering算法解决这些问题。
一般来说,我们可以将Clustering认为是将出现的数据进行Data Segmentation,也就是经常说的哲理: 物以类聚。 从机器学习的观点来看, Clustering算是Unsupervised Learning,或者叫做Learning by Observation,根据观察到的情况进行Clustering。 因为形成簇的数据都被聚到一起,所以Clustering 方法也可以用来发现噪音或是异常点。
Clustering 算法大致可以分为以下几类(参见Data Mining Concepts and Techniques):
  1. Partitioning Methods:这是一类经典的,最简单的聚类方式,就是直接按照类内的点距离最近,类间距离足够远的原则进行数据Clustering。该类方法比较经典的方法有K-Means 和K-Medoids。下文中会以广告分段问题来具体介绍K-Means的实现(K-Medoids类似)
  2. Hierachical Methods:层次Clustering算法,又大致分为bottom-up和top-down两种思路,bottom-up为自底向上,逐渐合并离得比较近的类以形成更大的类,top-down为一种divisive的思路,逐渐对离得比较远的类进行分裂。下文中会以如何合并搜索引擎中的同意,近义词词形成簇的的方式具体介绍bottom-up hierachical methods。
  3. Density-based Methods:以上两种方法基本上都是在高维空间中将数据聚成球形的多个类的方法,却不能处理非球形的聚类,Density-based Methods就是解决非球形数据的聚类方法。
  4. Model-based Methods:对数据进行建模,之后使用观察到的数据预估模型参数,比较经典的使用EM方法,先假设数据服从某种分布(例如k个高斯分布),并且这k个高斯分布由一系列隐随机变量决定。之后在E步预估这些隐随机变量,而在M步固定这些隐随机变量后,使用最大似然估计迭代得到最优参数。
文章以下内容将介绍3种聚类方法解决3个问题:
  1. 使用K-Means方法对广告受众网民进行Data Segmentation。
  2. 使用Bottom Up Hierachical Clustering方法对搜索引擎query进行聚类以进行流量推荐。
  3. 使用EM方式寻找数据中的隐藏主体。
 使用K-Means方法对广告受众网民进行Data Segmentation
K-Means是一种球形的聚类,在二维空间中,类别会被聚成以圆心为中心的圆,三维空间中则会被聚成以球心为中心的球状簇(当然,这与选择的相似度度量有关,例如使用cosine计算归一化后的两个向量长度,就会变成计算二向量的夹角)
在K-Means算法运行前,有两个因素比较重要: 数据预处理和距离度量方法。具体距离度量参见博文相似度度量 ,数据预处理则包括数据归一化, 去除噪音等操作。
因为K-Means算法本身较为简单,此处直接给出Andrew Ng机器学习公开课教案中的伪代码:
其中uj为第j个簇的中心点,ci为第i条数据的簇类别。基本步骤就是遍历数据,每一轮迭代,先计算当前数据与哪个类中心最近,该条数据属于距离最近的簇,之后根据新计算出来的每条数据的类别,更新类中心。下图给出在指定数据上给出2个类的4轮迭代情况:
使用distortion function度量分类的好坏情况, distortion 越小越好,当然,一般distortion大小需要和类别 k 的数量间进行权衡。
应用: 虽然k-means堪称最简单的算法,但之前在实习时,在前东家还是用了一把,应用场景是使用MSN用户的注册信息(年龄,喜好,性别),以及MSN用户在 msn.com上经常访问的导航类别,搜索关键词等数据,使用决策树选出区分度较大的特征构成特征向量,使用L1-Norm进行归一化后,对特征向量进行Clustering。之后按Clustering向广告主售卖这些用户的pv。 该模式的优势是具有一定的兴趣定向作用。
右侧即为MSN展示广告。当然,该方法已经是2007年所使用的方法,现在相信MS已经使用更精准的方法了 。
该过程中尝试较多的是如何选择合适的类别数量k值,以及如何初始化初始类中心。当时迫于项目进度,k值最后根据经验并进行了粗略的搜索选择,初始类中心则使用在相同k值得情况下进行多次随机初始化Clustering
使用Bottom Up Hierachical Clustering方法对搜索引擎query进行聚类以进行流量推荐
例如在搜索引擎中, 很多网民的query意图的比较类似的,对这些query进行聚类,一方面可以使用类内部的词进行关键词推荐; 另一方面, 如果聚类过程实现自动化, 则也有助于新话题的发现;同时还有助于减少存储空间等。
例如:
训龙记国语  训龙记2 寻龙记  训龙记博克岛的骑手  驯龙记电影
骂人大全    骂人不带脏字的顺口溜    骂人带脏字越毒越好  骂人脏字的狠话
要设计层次聚类,就需要考虑一下几个因素及环节:
  1. 使用何种聚类算法: top-down 还是bottom-up 还是其他
  2. clusting的合并策略
  3. 使用哪些特征
  4. 如何度量距离
  5. 使用何种评估标准对效果进行评估
确定以上5个因素后,聚类算法也就确定了。
聚类算法:考虑到实现的复杂度, 一开始我们就确定使用bottom-up的方式作为聚类策略;后续也就没有尝试top-down的方式。
clusting的合并策略:
一般有两类合并策略: 选取最相近的两个clustering进行合并;求连通分量。 因为寻找相近cluster的方式, 时间复杂度会达到O(n^2), 所以最后决定使用连通分量。
特征: 我们使用字面特征及query在session中的共现特征; 例如, 对字面进行切词后的term(做适当过滤降维:idf太小则过滤)
距离函数, 尝试过cosine和jaccard后, 最终使用jaccard作为距离度量。
 也可关注微博: weibo.com
或是直接访问: http://semocean.com

使用NDCG评估关键词推荐系统的相关性

对于传统推荐策略, 我们在验证其效果的时候, 一般会采用以下流程验证其实验效果:
  1. offline 的评测: 思路基本和传统机器学习的思路类似, 例如在推荐算法中我们直接使用AUC,F2等评估模型效果一样, 线下使用测试数据就能知道算法的初步效果。
  2. 用户调研实验: 该方式需要人的参与, 例如招一批人, 不告诉他们新老算法的界面或是使用的算法, 然后看用户的行为, 之后使用他们的最终交互, 或是选择判定算法/交互方案的优略。
  3. 线上实验: 最真实的尝尽, 例如小流量进行A/B test
具体关于评测后续会用专门的文章介绍,此处略去。 此处仅考虑一种特定的评估:关键词推荐系统的相关性评估。
因为baidu 关键词推荐系统是关键词的推荐,所以在很大程度上, 该推荐系统和传统的IR系统有着非常紧密的联系, 评估标准也较为相像。
对于一次推荐,用户进入百度关键词推荐系统交互界面: 关键词推荐系统会主动向用户push推荐的关键词,同时用户可以输入种子query进行查询:
如果将种子query看成是搜索引擎上的query,返回的关键词看成doc, 则问题就转换为搜索引擎的结果评估问题, 一种常用的方式为:NDCG(Normalized Discount Cummulative Gain)
CG
要介绍NDCG,我们首先介绍CG(Cummulative Gain), 其思想比较简单, 就是将相关性的分值累加后, 作为某个query/ 请求结果的分值。
reli 为处于位置i的推荐结果与query的相关性, p代表我们要考察前p个结果。
DCG
CG的一个缺点是CG没有考虑结果处于不同位置对结果的影响,例如我们总是希望相关性高的结果应排在前面,相关性低的结果排在靠前的位置会严重影响用户体验, 所以需要在CG的基础上引入位置影响因素,即DCG(Discounted Cummulative Gain)
即相同的相关性rel,排在对整次检索结果的正向影响,相较于放在后边更大。
NDCG
DCG仍然有其局限之处,即不同的query之间,很难进行横向的评估。例如, 我们评估百度关键词推荐系统, 或是搜索引擎的时候,都不可能仅使用一个query及相应结果进行评估, 一般都是是使用一批query及结果进行评估。 不同的query的评估分数就需要进行归一化。 也即NDCG。
例如我们定义:
其中DCG的定义如上, IDCG为特定query返回的最好结果, 即假设返回结果按照相关性排序, 最相关的结果放在最前面, 此序列的DCG为IDCG。因DCG的值介于 (0,IDCG],故NDCG的值介于(0,1]
具体操作方式
在具体操作中, 可以事先确定query和结果的相关系分级, 例如可以使用 0,1分别表示相关或不相关, 或是这是0~5分别表示严重不相关到非常相关。 相当于确定了rel值的范围。
之后对于每一个query的返回结果给定rel值,然后使用DCG的计算公式计计算出返回结果的DCG值。
使用根据sort后的rel值得序列计算IDCG值, 即可计算NDCG
参考文献:
百度关键词系统评估
 可关注微博: weibo.com/dustinsea
也可直接访问: http://semocean.com

选择推荐算法时需要考虑得因素

推荐系统涉及到前端交互设计,后台算法选取优化, 所以在设计推荐系统时,不能单纯使用accuracy对推荐效果进行衡量,需要根据推荐系统的具体应用场景,使用对象,解决的问题使用多指标对其进行衡量。而且很多时候这些指标都是一个上涨其他跌,需要彼此间做权衡(例如在设计百度关键词推荐引擎时,就需要在关键词的召回和准确性之间进行权衡,同时要考虑用户操作的便利性,推荐关键词的多样性等)。 下边就对这些指标进行介绍:
User Preference
用户是否喜欢该RS(Recommender System)的设计。最简单的方法就是让用户选择, 实验那种算法/交互设计用户更喜欢, 然后被投票较多的一种胜出。
中间会涉及几个问题:
  1. A算法和B算法比,假设A算法胜出了, 而投票给A的人相对于B只是稍微喜欢A一点点。 但投票给B的人却非常不喜欢A,则这种情况下,有可能最终仍然需要选择B。
  2. 每一票的权重,也可能是不同的,例如在百度关键词推荐系统中,消费较高,买词较多的客户相对于新客户更专业,他们的选择一般更科学,说以权重需要高一些。
 Prediction Accuracy
很多推荐算法都是基于数据挖掘或是机器学习, 所以很多时候, 也会使用数据挖掘和机器学习的accuracy衡量标准。我们可以简单粗暴地默认accuracy越高, 推荐算法的效果越好。
NOTE: 下文中所有的推荐系统衡量标准具体公式参见本站:推荐系统中的相似度度量
推荐算法中可以将accuracy的衡量标准分为3类:
  1. Rating Prediction
  2. Usage Prediction
  3. Accuracy of Ranking Items
Rating Prediction
例如在Netflix,douban中预测user对某个item(电影or音乐)的打分,为了评估算法预测的效果及偏差,可以使用RMSE(Root Mean Squared Error)或MAE(Mean Absolute Error)进行评估。数值越大表示偏差越大。
Usage Prediction
例如在百度关键词推荐引擎中, 更多需要考虑的是推荐出候选关键词后, 客户是否采纳该关键词(use),此时就不适合使用RMSE或是MAE进行衡量了。该场景下使用经典的Precision/Recall方式衡量更为合适,即一方面需要考虑推荐结果是否合适,另外一方面也需要考虑是否所有适合该客户该场景的结果都被推荐出来。
Precision=tp/(tp+fp)
recall=tp/(tp+fn)
更多时候可以直接使用AUC进行衡量刻画
Ranking Measures
例如在百度关键词推荐系统中,推荐出来的结果是关键词的list,排在前边的结果用户更容易看到,用户选择的代价也就更小,所以需要尽可能将更相关的结果往前排。此时就需要使用Ranking的标准衡量推荐结果list的结果。
此时一般使用NDCG(Normalized Discount Cummulative Gain)对该序列进行衡量,具体使用方式参见:使用NDCG评估关键词推荐系统的相关性
Coverage
即推荐的覆盖率, 最简单的方法就是评估推荐系统推荐的item占item全集的比例,同时评估推荐系统能够推荐给总用户的比例。 例如电商有100W种商品,推荐系统能够覆盖80W, 则可以简单地认为该推荐系统的Coverage为80%;又如网站用户为100W,推荐系统能够覆盖50W用户,则可以简单定义用户覆盖面为50%
该方式的缺点显而易见: item有重要和不重要,热门和长尾的区分,例如,在国外,哈利波特深受大家喜欢,该书/音像制品的关注度非常高,该商品被购买的概率较大,所以推荐一个哈利波特后被购买的概率, 可能是推荐一个冷门商品的N倍(例如推荐一个了冷门的‘舵机’),所以在计算Coverage的时候,需要考虑item的冷热程度。
例如在百度关键词推荐系统中,我们可以简单地考虑推荐系统所能覆盖的关键词数量的比例,但其实考虑推荐关键词所能覆盖的pv的比例,更合理。 或者在专门推荐长尾流量的出口使用关键词数量覆盖比例。
推荐用户所能覆盖的比例也是一个需要慎重考虑得问题: 一般情况下,有些客户是不适宜覆盖的,例如新用户的profile还没有建立的时候,过早地对其进行推荐,虽然覆盖率上去了, 却不能保证正确性。 所以经常需要在准确性和覆盖率上做权衡(例如不同的应用场景可以选用不同的覆盖率,准确性标准, 或是在交互上进行提示,告诉用户:仅供参考)
Confidence
推荐的置信度,很多时候,使用模型方法时,都可以产生一个置信度, 我们甚至可以根据置信度, 选择推荐样式, 或是是否展现结果给用户。 例如,当系统产生一个置信度较低的结果时,可以选择不进行推荐。
Trust
即:能否博取用户的信任。需要从心理学的角度去进行设计,例如推荐时可以掺杂一些确信的用户喜欢的item,或是推荐的时候写明推荐的理由(这点非常重要,就是‘给一个理由先’, 给了理由,说服力立马倍增)
但Trust很难定量衡量, 更多是进行调研得到调研分析结果。
Novelty
什么是Novelty?所谓Novelty,就是需要推荐新的东西,用户已经关注,已经购买的东西,再推荐就没有多少价值了。 举个例子,我经常上amazon.cn买东西,但之前经常发现一个问题: 我要买一口炒锅, 浏览了很多炒锅相关的item,之后下单买了口爱仕达的炒锅, 回头再上amazon的时候,他竟然仍然向我推荐各种品牌的炒锅。 这就是Novelty做的不好。
Serendipity
就是要推荐一些有惊喜的东西,例如我经常看某一个演员的电影,推荐系统给我推荐一部该演员演的我没看过的电影,算是Novelty; 如果给我推荐一部不是该演员演的但是风格和这些电影类似的电影,就属于Serendipity。
一个比较特别的的例子:
“假设一名用户喜欢周星驰的电影,然后我们给他推荐了一部叫做《临歧》的电影(该电影是1983年刘德华、周星驰、梁朝伟合作演出的,很少有人知道这部有周星驰出演的电影),而该用户不知道这部电影,那么可以说这个推荐具有新颖性。但是,这个推荐并没有惊喜度,因为该用户一旦了解了这个电影的演员,就不会觉得特别奇怪。但如果我们给用户推荐张艺谋导演的《红高粱》,假设这名用户没有看过这部电影,那么他看完这部电影后可能会觉得很奇怪,因为这部电影和他的兴趣一点关系也没有,但如果用户看完电影后觉得这部电影很不错,那么就可以说这个推荐是让用户惊喜的。这个例子的原始版本来自于Guy Shani的论文”
简单地说,就是让用户感觉到‘毫无理由地’喜欢
以上例子内容来自于项亮同学所著《推荐系统实践》
Diversity
最经典的例子, 在百度上搜索关键词‘苹果’,如果我们认为用户大概率是要搜手机相关的内容就不出水果的搜索结果, 那就是一个diversity较低的例子; 又如旅游推荐时,如果都是推荐一个地方的同类旅游景点时,也是diversity的一个反例,当然diversity很多时候需要和precision做trade-off
Utility
即推荐系统的效用。效用可以从两个角度考虑: 推荐系统对用户的效用及推荐系统对网站(owner)的效用,从两个角度来看,可能会得到不同的结果。 以百度关键词推荐系统为例,从用户的角度看,我们需要推荐和用户推广意图相关的关键词, 且这些关键词能够带来最高的ROI;而从百度的角度看,推荐的关键词应该带来最大的消费(至少短期的衡量标准是这样,长期考虑还是需要提升用户的ROI),针对不同的效用就需要建立不同的模型。
例如从公司的utility考虑,需要建立题词率模型(最大化推荐结果的采用率模型)及点击率模型; 从用户的角度,需要建立模型最大化ROI。 一般系统都是综合考虑这些效用决定最终结果。
 也可关注微博: weibo.com/dustinsea
或是直接访问: http://semocean.com