分类： 算法

在高德吃喝玩乐！LBS信息的AI技术应用

还是先插个招聘信息： 急招推荐，搜索，语音算法，数据挖掘，工程人才，阿里P5~P9，欢迎推荐和自荐，微信扫码关注以下二维码了解详细信息

以下才是正文。。。。

从毕业步入职场到现在10年多的时间，就一直在搞两个技术领域：搜推广信息分发以及LBS。

搜推广不用说，近十年一直都是热门的领域，另一个是LBS的技术，可以说也是深入到我们生活的方方面面。过去既做LBS的信息分发，也做底层的实时路况，ETA以及RP算路，甚至更底层的地图匹配（或者叫抓路，绑路，map matching），目前，更多在做人地关系大数据，以及基于LBS的搜推广。相当于将两个领域结合到了一起。

更详细的LBS相关内容可参见：
GITC演讲-滴滴路况感知AI及应用
[LBS]地图Map-Matching流行算法及应用
[LBS]工业界ETA应用及滴滴WDR技术

《在高德如何吃喝玩乐！LBS信息分发的AI技术应用》就是团队的工作在高德技术开放日进行的介绍，感兴趣的同学可以在抖音，B站等平台观看交流。 具体B站的链接视频，参见‘阅读原文’

对于地图平台，无论是高德地图还是百度地图，腾讯地图，现阶段心智最强的功能还是出行。而在整个出行的用户交互过程当中，用户首先需要进行定位，确定自己所在的位置，然后进行POI的搜索，确定要去的目的地，之后就是怎么去的问题？包括路线规划导航ETA等相关技术。

随着地图平台的定位由出行工具逐渐转成吃喝玩乐相关的LBS本地生活平台，信息分发的范畴也在扩展：从原有的POI搜索，展到了交易的分发以及广告的分发。

同时，这个过程当中需要有非常多的内容的理解，包括文本，语音以及视频内容的建设。具体参见：ID+图像特征联合训练CTR模型

同时，分发的手段也有更多的扩展，由原来的搜索，扩展到推荐以及语音的更多的交互方式。包括搜前，搜中，搜后，语音主动提示等多种交互方式，和用户进行信息的交互。（完整的工业级搜索+推荐 用户交互机制实现参见：关键词推荐工具中的用户引导机制）

同时，分发的形态，也由原来的单纯的POI list，扩展到视频，聚合榜单的更加丰富的模式。

对应的工作也包括最底层的数据建设，上层的引擎平台的建设，通用算法策略的建设，以及业务的定制。都是非常复杂的过程。

在这个过程当中，也会用到非常多机器学习相关的算法模型，当然，我们要时刻意识到，机器学习模型只是整个业务逻辑很小的一部分，虽然它起着无可替代的重要作用。

LBS的搜推广和传统的信息分发最大的区别，就是他会有很强的空间，时间的划分属性。

在LBS场景，每一个区域，或者每一个POI，都可以看成他是一个个的局域网，这些局域网之间其实是没有非常强的关系的，例如一个云南的用户，可能从来也不会去一个天津的饭馆吃饭，因为地域天然将这两个要素隔离开。 这和淘宝的信息分发是有本质的区别的，在淘宝上，一个云南的用户和一个天津的用户可能都会买同样一个商家的，同样一个商品，而且几乎代价是没有区别的。

因为地域，或者距离的差别，就会导致LBS的信息分发和传统的信息分发有本质的区别，这样就衍生出非常多的LBS信息分发独特的技术。

例如POI的别名挖掘，如何挖掘同一个地点的不同的别名。 以及反过来如何挖掘不同地点，有相同名称的POI，都是特有的结合LBS空间挖掘的技术。

同时，我们会依赖于用户的搜索，点击导航路线规划以及位置信息，去使用定制的序列模型挖掘用户的行为序列信息，去做更准确的用户个性化定向。

在地图场景，需要主动给用户展示信息的入口/场景非常多，而且不同的入口有不同的产品形态和定位，如果对每一个入口都定制一个推荐模型，那维护的成本是非常高的；同时，不同入口的信息无法共享，所以我们也是用了多任务的模型，对不同入口的推荐算法进行统一的建模。（具体ctr预估参见：推荐系统，变现系统CTR&CVR预估算法演进－模型）

而且在地图场景，我们使用了丰富的LBS数据，却对用户的时间，空间，行为进行预测，例如，用户接下来会去的地点，区域和城市，并且取得了显著的效果。

这个领域的工作非常多，也非常有意思，而且LBS本地生活是非常重要，非常有前途的一个领域，也是目前各个大公司重兵投入的兵家必争之地。如果大家感兴趣，请联系我进行高德岗位的内推。

如何使用机器学习解决实际问题-以关键词相关性模型为例

本文以百度关键词搜索推荐工具字面相关性模型为基础，介绍一个机器学习任务的具体设计实现。包括目标的设定，训练数据准备，特征选择及筛选， 以及模型的训练及优化。该模型可扩展到语意相关性模型，搜索引擎相关性及LTR学习任务的设计实现。该模型的设计调研实现，也可以很容易移植解决其他包括语义相关性的问题

目标设定：提升关键词搜索相关性

作为一个搜索+推荐产品，百度关键词搜索推荐系统的产品形态是向凤巢用户推荐适合他业务的关键词。例如一个卖鲜花的广告主，他想在百度上做关键词搜索推广时，需要提交和他业务相关的关键词，而且提交的关键词需要业务相关，例如他需要提交和卖鲜花业务相关的关键词。例如鲜花快递，鲜花速递等。此时他可以在百度关键词搜索推荐系统中进行搜索查询，选择适合他的关键词。

百度关键词搜索推荐系统query搜索

这是一个典型的搜索问题，具体的从输入query，到触发，到排序等会涉及到很多因素，例如如何查倒排，如果处理地域因素等；要提升搜索的质量，我们首先需要保证输入的query和推荐出来的推荐词的相关性，此处我们要解决的主要问题， 就是如何快速，准确地判断两个关键词（输入query和推荐词）的相关性，需要特别注明的是，我们主要的目标是让用户觉得该产品结果很靠谱， 所以该处我们仅考虑字面相关性，更多的语意扩展该模型并未考虑。

注：该模型的调研实验实现方式， 可以很容易平移到语义相关性。例如加入更多语意特征，例如plsa的bm25特征和word2vec的相似度特征（或者和扩展的相关性校验，例如将待推荐词扩展为baidu搜索结果的摘要扩展）提高语义特征的贡献。

相关性也是所有搜索问题的基石，只不过在不同的系统中使用方式不一样， 在一般的搜索中，相关性占有较大权重， 排序基本就以相关性为依据； 在商业系统中，相关性则经常作为搜索展现的门槛用于控制商业推广结果的质量（如果仅考虑CTR， 用户搜索鲜花快递时，给用户展现艳照门的结果，CTR会更高，但相关性较差）。  当然，判断相关性我们可以简单使用某一种方法进行直接判定，例如直接进行两个关键词的TF-IDF计算，或是进行两个关键词的BM25。但这样的方式效果都不太理想，想要达到更好的效果，就需要使用更多特征，而更多特征很自然地，需要使用模型组合这些特征，达到最终的预期效果。

图：相关性在关键词系统中的位置

此处将会使用机器学习的方法解决该问题。本文以下内容会从数据准备， 特征选择， 模型选择， 模

型调优等步骤介绍百度关键词搜索推荐系统如何解决该问题

数据，特征，模型

说到使用机器学习解决问题，我们经常提到的优化思路就是3方面的优化： 数据，特征，模型。首先找到充足的，准确的label数据（该出仅考虑有监督学习任务，例如相关性，或是LTR），之后提取贡献较大的特征作为input space，以label作为output /ground true label，之后优化模型（Hypothesis) ）。下面会分别从这3方面对整个优化过程进行阐述

准备训练数据

训练数据的获取一般有几种方式：

  1. 人工标注： 优点是质量较高，噪音较少；缺点是标注结果和标注者本身的认识相关，例如在搜索引擎中，判定苹果和手机的相关性，对于年轻人，一般都认为相关；但对于比较多的老人，可能认为不相关；另外一个缺点就是人工获取标注的成本较高
  2. 从日志中进行挖掘：优点是数据量相对更大，获取成本较低（编写几个hadoop脚本对日志进行统计）；缺点是噪音较多，例如搜索引擎中的恶意抓取访问导致的噪音数据

在相关性模型中，一开始我们使用百度关键词搜索推荐系统的人工反馈数据作为label对模型进行训练，分别提取1.5W query-推荐词pair作为正负例进行特征提取，模型训练。

 

如图所示，在交互上，当用户喜欢该关键词时，就会点击‘大拇指’表示该结果符合用户需求（正反馈，该query-推荐词 pair可作为正例）；如用户认为该关键词不符合需求，就会点击‘垃圾桶’，将该关键词扔入回收站（负反馈，该query-推荐词 pair 可作为负例）

在实验中，我们发现正例没有问题， 不过负例中会存在较多这样的情形： query-推荐词是相关的， 但该用户不做该业务，所以被定义为负例，所以负例个性化较强。所以后来我们让产品经理同学又对负例子进行筛选，重新标注1.5W负例，进行后续特征提取， 模型训练。

之后我们将正负例打散后（直接使用python random.shuffle）分成10份，进行cross-validation

模型训练前，先定标准和样本

注： 训练样本的挑选完全决定了我们的问题目标，所以在一开始就需要准确选择，如果可能，所有的case都最好人工来搞，或者至少需要人工review。 确定没有问题后，再开展后续工作。特别是相关性类似的问题，比较主观，例如PM和RD在该问题的判断上就可能存在一定差异。

确定完训练样本， 评估标准，之后再小布快跑， 优化模型。

特征提取

一般特征的选择及处理会极大地影响学习任务的效果，而进行特征选择的时候，一般是先增加特征，并实验效果。 对于相关性模型， 我们可以先将传统的信息检索的特征加上，这些特征一般分为以下几类：

  1. query/候选词的一般结构特征： 例如query/候选词长度，term数等
  2. query-候选词的相关性度量：例如TF-IDF, bm25, LMIR及多重变种， plsa相似度度量，word2vec语意向量相似度等； 很多时候，关键词自身信息较少，还可以使用关键词在搜索引擎上的摘要扩展进行相似度度量
  3. 关键词自身在信息检索维度的重要性度量，例如关键词idf, 从语言模型方面的重要度等

在一开始的时候，我们可以先将能够想到，构造出来的特征均加入特征向量进行实验，而且每加一类特征，都可以看下该类特征对整体目标的提升程度。以便对该特征的贡献度有一个直观的感受。

以下数据可以简单看出随着特征的增加，效果的提升，其中的特征仅加不减（模型使用random forest   进行二分类）：

等到特征加得差不多，模型准确性已经提升不多的时候， 可以考虑砍特征，有一种比较简单粗暴有效的砍特征的方法，就是使用树模型，就是直接砍掉特征贡献程度及特征重要性较低的特征，例如直砍掉特征贡献度为0的特征，对相关性模型的准确性几乎没有影响

特征贡献度

当增加特征已经很难提升效果， 考虑到为了防止过拟合，同时考虑到模型online预测，需要对特征进行挑选。在使用树模型时，可以直接使用数节点特征贡献度和节点使用次数，判断是否需要去除该特征，以下为使用树模型进行选择特征的例子：

对于特征贡献度和分裂特征使用次数为0的特征，在调研时，直接去除对模型效果几乎没有影响，而且能提升预测的效率。

在选择特征的时候， 有一些经验值得分享：

  1. bm25特征及term weight特征对分类任务有极大贡献
  2. 一些单独的比值类特征并没有太大贡献，例如query，推荐词共同term与query term数，推荐词term数的比值，这些特征并没有太大贡献，但是这些特征与query，推荐词的term数结合到一起，贡献就非常多；所以有些特征需要联合在一起，才有较大作用。
  3. 特征选择需要和目标一致：例如word2vec是非常高大上，且非常靠谱的技术，但用在字面相关性，对目标并没有太大贡献（如果目标是语意相关，那么类似于PLSA,word2vec将会有很大贡献）
  4. 有些特征就就是用来解决特殊case的，虽然贡献不大，但需要保留（当然也可以直接设置为强规则与模型配合），例如query与推荐词拼音一致

模型选择

经典模型

最开始我们尝试了最大熵，SVM和adaboost模型， 考虑到online使用的效率，最终我们选择了adaboost模型作为线上使用的模型，虽然效果不是最好的，但使用简单的weak learner构建的模型的确比较快（参见博文：《adaboost》），并且使用adaboost进行上线并取得较好效果：上线后不仅召回增加，准确性上90%的case相关性高于等于原有结果（采用非模型的版本）

评估结果分布图（2到-2分别代表扩召回结果相关性高于、略高于、等于、略低于、低于线上策略）

集成树模型

现在特别喜欢使用树模型，因为使用的时候，连特征归一化都省了： 如果使用SVM类似的模型，还需要对特征进行归一化等处理， 但使用树模型，直接将特征向量及label扔给模型， 模型自己会根据信息增益，或是基尼系数等标准选择最合适的拆分点进行树节点的拆分（具体的拆分标准可参见博文：《使用impurity选择树模型拆分节点》），开源的树模型，例如大名鼎鼎的Quinlan的C4.5或是C5.0都在调研时都可以拿来试试作为特征选择的依据。

特别是集成树模型的出现，更是极大地提升了树模型效果。所以现在的项目中，我比较喜欢在增加特征的时候就使用集成树模型进行效果实验。 具体树模型使用参见《集成树类模型及其在搜索推荐系统中的应用》

集成树模型配置选择

此处的配置选择和传统的模型参数稍有区别，该出的树模型配置主要指集成树模型中树的数量，每棵树的特征选择因子和样本使用因子等。在项目中，考虑到准确率和速度，最终确定的参数是树的数量是20， 特征选择因子和样本选择因子均为0.65（每棵树随机选择0.65的样本和特征进行训练）

具体产品效果可参见www2.baidu.com中百度关键词搜索推荐系统的排序结果：

如何个性化

首要需要考虑的是我们的数据样本，是否本身就是包含个性化的case（此处的答案是否定的）； 假设我们的标注case是个性化的，也就是case中本身就包含了个性化结果时，在模型训练流程上其实并没有太大区别， 主要的区别就在于我们选取哪些能够区分这些个性化的特征， 例如百度凤巢中账户（单元）的plsa模型产出的pzd向量与query的相似度等

登录www2.baidu.com->关键词工具->搜索query->查看结果 即可。

更多内容也可参见： http://semocean.com

关键词推荐工具中的用户引导机制之三：相关搜索query技术

在上一篇《关键词推荐工具中的用户引导机制之二：suggestion架构》中， 我们提到， 在用户在搜索引擎，或是关键词推荐工具中输入搜索query片段的过程中， 我们可以提供suggestion来对用户搜索进行引导。 我们可以认为此时用户的搜索意图是不全面的。 而当用户已经输入完整query后， 用户的搜索用途已经在某种程度上明确了， 此时我们就可以使用相关搜索， 扩展出与用户输入搜索意图一致/类似的高质量query， 引导用户进行搜索， 让用户更快地获取信息， 得到所求。本文会具体介绍相关搜索类似的关键词推荐系统的策略架构，以及业界常用的相关搜索挖掘算法。
说简单一点， 相关搜索query， 其实也是一个关键词推荐。 和adwords中关键词工具， 或是百度关键词工具不同的地方， 是相关搜索对质量要求非常高，而给出的结果一般比较少， 即高准确， 低召回。
图： 百度相关搜索
图： Google相关搜索
以上分别为Baidu和Google的相关搜索结果， 不知道大家是否发现，Baidu相关搜索结果多样性强一些，同时商业价值也强一些（本文不介绍商业价值机制，后文介绍的优化目标中加入商业价值因素即可）
相关搜索策略架构
因为相关搜索就是一个典型的特定场景的关键词推荐系统， 所以相关搜索从策略架构上，会包含完整的关键词推荐的逻辑。 包括候选词源触发(query retrival)、 相关性过滤(filtering)、排序模型排序(ranking)，　以及根据规则进行调整（marketing rule）。 其中每个阶段都可以根据最终的优化目标（或者多目标）设计相应架构。
图：关键词推荐策略架构中的主要处理逻辑，包括query retrival, filtering, ranking, marketing rule几大逻辑
各组件功能
  1. 候选词源触发(query retrival)：其主要功能是通过各种offline数据挖掘，得到query（或是成份）之间的关系， 获取到候选的待推荐query，供后续逻辑进行处理。
  2. 相关性过滤（filtering）：根据应用场景，对不满足query之间相关性的候选词进行过滤，以减轻后续逻辑的性能负担。 相关性过滤的方法可参见《分类模型在关键词推荐系统中的应用》
  3. 排序(ranking)：根据应用场景的优化目标，对候选词进行排序。 例如， 如果要提升用户体验，那就直接将高相关性的候选词排在前边（衡量标准可参见《使用NDCG评估关键词推荐系统的相关性》），如果同时需要考虑商业变现， 那么可以考虑将能够获取到较多广告点击量的query排到比较靠前的位置
  4. 业务规则（marketing rule）： 例如， ‘黄赌毒’结果必须过滤，或者带有某些特定字眼的关键词必须提到比较靠前的位置。。。。 这些规则更多是人为确定的（例如PM确定）
相关搜索query策略
数据
总的来说，搜索引擎要挖掘相关搜索结果，有以下几类数据可用：
  1. 网民搜索session数据（后续简称session数据）： 就是网民在搜索引擎搜索框中连续输入的多个query。 这里有一个假定， 就是同一个session中的query都是有关系的（更进一步， 同一个session中离得近的query更相关； 在多个session中都出现的连续搜索更相关），该数据可以表示为多个query的序列
  2. 搜索点击数据： 即网民输入某个query后，在搜索引擎上点击的url，该数据可以简单表示为的pair
  3. 网页内容信息： url对应的网页内容
相关搜索的算法， 总的来说都是围绕上述数据， 其中 1，2类数据我们可以认为是网名的行为数据，而3可以认为是内容数据。 一般而言， 很多算法直接使用1，2类行为数据即能取得较好效果。 也有一些算法会结合网页内容信息提升效果。
候选词源触发方式
以下是几种典型的用于相关搜索的算法：
Beeferman, Doug and Berger, Adam. 2000. Agglomerative Clustering of a Search Engine Query Log. Proceedings of the 6th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2000, 407-416.
使用Agglomerative Clustering方法， 首先使用query点击数据，对query和URL进行聚类， 取得相近query(具体算法介绍参见《搜索引擎点击日志聚类实现相关搜索》)；得到query聚类后，在新query到来时，可以先判断网民query与哪个/些聚类最相近，然后该聚类下的词，都作为待推荐的关键词后续，进行后续排序过滤。 该方式优点是完全使用网民查询点击的行为数据，而没有使用到网民的内容， 或是query的内容； 此类思路和协同过滤类似。
图： query-点击关系
图： Agglomerative Clustering Init
图： Agglomerative Clustering Iterative
Wen, Ji-Rong, Nie, Jian-Yun and Zhang, Hong-Jiang. 2002. Query Clustering Using User Logs. ACM Transactions on Information Systems. January 2002, Vol. 20(1), pp. 59-81.
该方式不仅使用了query-点击数据对query进行了聚类，同时还是用了query内容等信息。 也就是说， 网民行为和内容， 作为相似度度量的最终标准。
图： 结合查询行为及内容相似度度量
BM Fonseca, PB Golgher  2003 Using association rules to discover search engines related queries Web Congress, 2003  - ieeexplore.ieee.org
该方法中直接使用2项关联规则进行related-query的挖掘， 满足提前设定的支持度， 置信度阈值后后， 就作为推荐结果候选
Z Zhang, O Nasraoui   2006 Mining search engine query logs for query recommendation - Proceedings of the 15th international conference …, 2006 - dl.acm.org
该方法， 也是直接使用session数据对相关搜索结果进行挖掘总的思路也是根据session中共现概率较高的关键词作为高相关的query pair。 其中的一个创新， 是计算session之间的距离的时候， 使用了衰减方式。
论文中认为： session 中的pair， 离得越远， 相似度就越低， 例如， 假设session中每一步的相似度是d(d属于(0, 1))， 则两步的相似度为 d^2， 使用该方式进行衰减， 两步的相似度为  d + d^2  而不是2d  (当然， 实际中也可以选择， 两步的相似度， 就是d^2， 而不是d^2 + d)
图：session中随着间隔的增加，权重衰减
R Baeza-Yates, C Hurtado, M Mendoza 2005 Query recommendation using query logs in search engines Current Trends in Database 2005 - Springer
以该文为代表的方式， 还同时使用了搜索query和点击URL对应页面中的term之间的关系， 使用点击URL对应页面中出现的term作为query的表示，同事考虑了query的受欢迎程度作为相似度度量。 不过该方法因为挖掘代价较大，所以并未做该类实验， 毕竟， 简单也是一种美： ）
其中q为代表特定query的向量， Pop(q,u)为搜索query q后点击URL u的PV， Tf(ti,u)为在在u对应的网页中， ti出现的词频。
排序过滤
产生了大量候选词后，一般会使用相关性模型直接过滤高度不相关候选词（参见《分类模型在关键词推荐系统中的应用》），之后进行排序。 排序时，一般按照优化目标进行排序。例如，假设我们一方面要考虑相关性（使用Q表示），同时要考虑商业变现收入（使用R表示）， 则我们可以将优化目标表示为：
T=Q^(t) * R^(1-t)， 其中t属于[0，1]，通过调整t来控制在相关性和商业变现收入之间的权衡，该方式也可扩展为更多目标优化场景。
当然，对于现实中的相关搜索， 可以融合多种策略算法的数据以提高最终质量。
更多内容请参考：
Beeferman, Doug and Berger, Adam. 2000. Agglomerative Clustering of a Search Engine Query Log. Proceedings of the 6th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2000, 407-416.
Wen, Ji-Rong, Nie, Jian-Yun and Zhang, Hong-Jiang. 2002. Query Clustering Using User Logs. ACM Transactions on Information Systems. January 2002, Vol. 20(1), pp. 59-81.
BM Fonseca, PB Golgher  2003 Using association rules to discover search engines related queries Web Congress, 2003  - ieeexplore.ieee.org
R Baeza-Yates, C Hurtado, M Mendoza 2005 Query recommendation using query logs in search engines Current Trends in Database 2005 - Springer
也可关注我的微博：  weibo.com/dustinsea
或是直接访问： http://semocean.com

协同过滤中item-based与user-based选择依据

协同过滤是大家熟知的推荐算法。 总的来说协同过滤又可以分为以下两大类：
  1. Neighborhood-based：计算相似item 或user后进行推荐
  2. Model-based： 直接训练模型预测Rating
在Neighborhoold-based算法中，又细分为user-based CF(Collaborative Filtering)和item-based CF。合适选择使用userd-based CF，什么时候item-based CF更适用就会是一个需要权衡的问题。一般而言，可以以下几个标准进行选择：
  1. Accuracy：一般而言，少数置信的邻居的推荐要比很多的没有太多区分性的邻居更加准确，所以一般我们会选择数量较少的因素(item or user)作为based的算法。 例如， amazon中的商品的种类很多，但远没有注册的用户多，所以该场景使用item-based CF比较合适； 反过来，在百度关键词推荐系统中，商业客户(user)量级是100W左右，而待推荐的关键词(item)是10亿量级，此时使用user-based会是更明智的选择。
  2. Efficiency
  3. Stability：一般情况下倾向于使用变动频率和变动量较少的因素作为based的因素， 例如item变动较少， 则选择item-based， 否则选择user-based
  4. Justifablity（说服力）：推荐系统中，推荐理由越白盒，用户越容易理解就越有说服力。所以从这方面考虑，item-based CF会更有说服力，例如显示‘因为你浏览了三星 Galaxy，所以给你推荐了HTC One’的理由会比‘和你相似的用户也喜欢XXX’更有说服力，因为推荐系统是不披露哪些用户和我详细，怎么证明和我相似的，而且这种说法显得比较含糊。
  5. Serendipity：多样性就是user-based的一大优势，和自己相似的用户，总能发现一些自己还没发现的新东西。 如果追求多样性， userd-based会是不错的选择。
当然上述原则都不是绝对的，而且在真实工业界推荐系统中， 两种方法一般都是混合着使用。例如百度关键词推荐系统中，就会分别使用item-based和user-based方法找到待推荐关键词候选后，再统一使用model进行后续ranking。
参考文献：
  1. RSs Handbook
  2. Evaluating Collaborative Filtering Recommender Systems, Jonathan L.Herlocker
也可关注我的微博：  weibo.com/dustinsea
也可直接访问： 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

使用impurity选择树模型拆分节点

在近期的项目中经常会使用到连续值模型以提升模型效果。 例如在项目初期， 训练数据准备OK后，就会使用原有的LR模型初步训练model看实际的效果， 同时因为连续值模型， 特别是树类模型已经在其他项目中应用并取得较好的效果， 所以我们也会将离散特征进行变换处理后， 使用GBDT, RF看下实际效果。
虽然GBDT, RF都有现成的model训练环境，直接用就可以，在项目过程中还是顺便复习了一下与树类模型相关的impurity度量标准；就像侯捷在《STL源码剖析》中说的，开飞机的人不一定需要了解飞机的原理，但参观飞机制造厂也是一种乐趣。
常用的使用impurity选择树模型拆分节点的度量有以下几类，他们都来自于信息论：
  1. Information Gain
  2. Gain Ratio
  3. Gini Index
以上三种根据impurity进行拆分的度量方式各有优缺点， 一下具体介绍
Information Gain
首先要定义概念熵(entropy)可以理解为定义一个分布的信息量， 具体定义如下：
其中D为数据集合， pi为第i类在数据中出现的概率。之所以使用以2为底的对数， 是因为我们默认使用bit进行编码。而该处的info/entropy即描述分布不纯的程度。 而我们可以将树模型看成是对接点进行分裂， 之后根据拆分条件节点的建立使整棵树的叶子节点尽快达到较纯的状态。
假设现在有A,B,C作为拆分feature的候选，且假设我们选择使用featureA进行拆分， 则拆分后的信息为：
其中A为选择的feature，Dj为feature A的值为j的集合，而Information Gain，即表示在原分布上，确定待拆分的feature A 后， 所带来的信息增益（减少的信息量）， 拆分时使用贪心算法， 信息减少量越多越好。故：
每次拆分时，贪心地选择Gain最大的feature A进行拆分即可。
最经典的Decision Tree算法ID3中即使用Information Gain作为节点拆分的标准。ID3算法具体描述参见：http://link.springer.com/article/10.1023/A:1022643204877
Gain Ratio
Information Gain在节点拆分时是有倾向的， 倾向于拆分属性值较多的feature，一个极端的例子，假设feature是具体的ID值，即每条instance的ID值都唯一，则对该feature进行一次拆分后，则每个节点都达到纯的状态，Information Gain值最大。为了解决该问题，在ID3的升级版Decision Tree中引入另外的拆分标准，Gain Ratio。
定义：
因为某feature的属性值越多， SplitInfo就会越大，故可以使用SplitInfo在一定程度上消除Information Gain倾向于多属性feature的偏好。 具体Gain Ratio如下：
在此：属性值越多Gain越大，但SplitInfo也会越大，这样就中合了Information Gain带来的偏向。
P.S. 做策略算法中，类似的操作都是互通的，例如在推荐引擎中，用户打分可能偏好不一样，有些习惯打高分，有些习惯打低分，则我们可以使用打分的均值去中和这种偏差；而有些人打分分值比较集中，有些人则分布比较广泛，则我们可以使用z-score，即处于标准差去一定程度上消除这种分布。
Gini Index
Gini Index在CART（Classify and Regression Tree）中使用，定义：
其中D为数据集， pi为类Ci在D中出现的概率， 可以直接使用|Dci|/|D|预估。
假设我们在feature A上进行拆分， 并且是进行二分类拆分，拆分得到D1，D2数据集
则拆分后的Gini Index如上。
同样， 我们使用Gini稀疏的减少量选择拆分的feature。
这里需要注意，CART中仅进行二分拆分，如果A为多属性， 则需要转化为二分类拆分。
细心的同学可能会发现，除了gini和entropy的定义不一样外，其余的计算Gain的方式都是相似的
reference:
induction to decision tree,  J,R,Quinlan
Data Ming: Concepts and Techniques
 也可关注微博： weibo.com/dustinsea
或是直接访问： http://semocean.com