最近在重温决策树。
也深感决策树算法的优势
下面是一篇它在个性化推荐方面的文章：
==========================
图灵测试大家都很熟悉，通过问答形式来区分人和机器。小时候也做过假托《镜花缘》的逻辑题，需要你通过提问区分两个怪蜀黍谁来自“真话国”谁来自“假话国”。回到现实中，绝大多数推荐系统都无法回避冷启动问题——面对素不相识的用户，需要尽快把握其好恶给出尽量靠谱推荐。这时候通过问问题套瓷观察对方的反应，就是很常见和有效的做法（跟社交场合一样）。考虑到对象是形形色色千差万别的人，如何提出恰当给力的问题，就很值得研究和琢磨了。本文就来讲讲利用决策树的做法，源自论文《Adaptive Bootstrapping of Recommender Systems Using Decision Trees》。
背景
先说点题外话。几周前推荐系统论坛举办的相当成功。（这里感谢组织者的辛苦工作，以及淘宝同学的给力赞助。论坛官方已经放出材料和视频，几位同学的参会总结也相当给力，本文最后将一并给出链接。）就我个人来讲，Koren博士的talk给我印象最为深刻。首先，极大的改造了我对netflix竞赛的看法。之前个人过于孤陋，觉得类似offline prediction竞赛，基于确定的数据集和目标函数，解决的不过是一个纯数学/算法问题：参赛者不用关心领域知识和用户需求（充其量看看数据的统计分布），不断的调整堆砌模型就ok了，离真正的推荐应用差之甚远。听了一圈发现，这些参赛者对于数据集其实有相当深刻的理解和思考，比如bias和temporal dynamics、用户不同反馈的理解，都很精彩且有启发性。这与实际构建推荐系统在很大程度上是契合的，首先要找到产品需求和数据中的规律，然后再加以利用。
其次，talk内容的针对性很强，不是一些形而上的抽象总结的或偏general的介绍，很多点跟实际应用的联系非常紧密。比如提到的bootstrapping a recommender，正是自己最近在琢磨的一个问题。最近构建的应用新用户比例过半，迫切需要解决对用户的judgement和profiling。由于工作没有深入到这里，之前只有一个大致的想法：人工或者机器找出一些区分度和接受度都较强的item，混合后提供给用户，通过用户的使用反馈逐渐确定其偏好；整个过程即可以是显式的用户引导（比如初始选择喜欢的item），也可以隐式的直接推荐。
结果Koren直接介绍了他们最近在这方面的工作，即《Adaptive Bootstrapping of Recommender System Using Decision Trees》这篇发表在WSDM2011的paper，提出用决策树的方法进行自适应的用户引导和判断。上周花时间找来读了一遍，写的相当清晰也很有意思。这里记下来备忘，如能帮同学们节约些时间更善。
设定
应用场景很明确，就是一个initial interview的过程，依次给出一些item要求用户进行显式的反馈，以此来构建对用户偏好的基本了解。暂不考虑如何挑选，先来看看候选集合中的种子（即提出的问题）需要满足什么样的条件。作者认为，至少需要考虑以下几个因素：- 流行度（popularity）。需要尽量给出流行或用户熟悉的item，更容易让对方接受并做出选择；
- 区分度（contenttion）。同样很好理解，好恶一边倒的item出现在候选序列中，不能提供多少信息量；
- 覆盖度（coverage）。这里更多指item的泛化能力。如果这个item只能关联上非常少的其他item，后续真正可做的事情也会非常有限；
以上只是针对单个item，更理想的情况是考虑item间的关联和序列关系，充分利用之前答案的信息来调整后续的对话，打出一套组合拳。
应用于推荐引导的决策树
将决策树应用于推荐引导，是一个很好理解且自然的过程。从根节点开始，向用户提问，每个节点对应一个特定问题（item/电影）；依据用户的不同反馈，进入相应的子节点；不断迭代上述过程，直到到达叶子节点或满足其他退出条件。用户的profilling过程，就是一条从根节点到叶子节点的访问路径。先看看论文中给出的一棵生成树。论文的工作都是基于Netflix数据集。如图可见，用户有三种回答，喜欢（like）、不喜欢（dislike）和不知道（unknown）；rmse值是对落到该节点所有用户预测评分的均方误差，马上会讲到。基本的构树过程比较简单：
- 将所有的用户评分数据映射到<like, dislike, unknown>三维空间上。Netflix评分为1-5星，这里将1-3星映射为dislike ，4-5映射为like，未评分则对应unknown；
- 从根结点开始，选择最佳的分割item，自顶向下建树；
- 终止条件，同时考虑以下三种：
- 设定树的最大深度；
- 设定最佳分割item的误差阈值；
- 设定当前节点的最少评分数量；
来看看对分割item的评价。整个决策树的优化目标是使得RMSE最小，这里为使树均衡和方便计算，在每个结点使用了和方差。
- 对于给定用户集合t，我们都可以计算评分的和方差
- 任选一个item i，可以计算针对该item的平方误差，R(i)是所有对item i评分的用户集合，是集合用户对item i的平均打分；
- 和方差，即将该用户集合t所有评分item的平方误差相加；
- 对于给定用户集合t，任选一个item i作为分割，都会将用户分成三组：评分喜欢、评分不喜欢、未评分，分别记为tL(i)、tH(i)、tU(i)。这样可以计算出三个集合的和方差之和。
- 决策树的每个结点对应一个用户集合，即其父结点的一个特定划分。对于根结点，这个集合就是全体用户；
- 为每个结点寻找最佳的分割item，就是找到一个item i使得三个集合和方差之和最小：
具体实现中，还有如下的一些考虑：
- 在计算评分误差时，考虑user bias；
- 通过将item的损失误差转化为其被选择的概率，支持一定程度上的随机树的生成；
- 针对性的性能优化
- tU(i)集合的用户数目是占大多数，通过公式变化转化为对结点全体用户t和tL(i)、tL(i)的运算；
- 通过数据结构设计，将集合划分实现为对某item对应user数组的排序操作，由于是评分只有三个值，计算复杂度为O(n)；
文中给出了构树的伪代码：
建树完成。当用户通过一系列选择到达某结点时，就可以使用该结点用户集合的平均评分来进行预测对各item的喜好，甚至可以基于预测评分得到一个ranked-list提供最简陋的推荐。文中作者也做了相关的讨论：- 首先需要考虑对于某个item该结点下用户评分数目过少的情况，这样很容易出现过拟和。因此引入层次平滑（hierarchical smoothing），将父结点对于该item的评分也纳入来考虑，实现的相当精巧；
- 直接基于预测值排序的推荐可能过于保守，作者建议比较该结点的预测值跟全体用户的平均值，倾向取差值较大的item；
评估
最终的评估还是RMSE，计算测试集上，决策树判定节点的预测得分与用户实际打分的差异。作者对比了HELF和Entropy0（综合popularity和熵）、Var（利用item方差）等方法，如图所见，决策树的方法使用少数几个item的效果要优于其他方法使用20、30个item的结果。 同时还比较了训练集中用户评分数据的多少对效果的影响，基本上符合常识数据越多越靠谱。评估部分相对讲的较少，有点意犹未尽。多棵决策树
作者认为可以考虑使用多棵决策树：- 互为补充，防止用户对给出的item无感。通过数据分析可知，对于unknown分支上的用户，预测准确率低；
- 用户界面考虑，更喜欢同一页面下评分多个item（这个地方存疑，不过一次多评几个也没啥坏处）；
- 决策树属于“weak learners”，使用多棵提升准确率；
多棵树的生成参见前述的随机生成，如何合并多棵树的结果，也是很有意思。一般使用均值、线性加权的做法，不是很适用——尤其是考虑对于不同用户不同树的贡献很可能是不同的。作者着重考虑了两类因素：
- 命中的结点深度。假设反馈越多，判定应该越准；
- 反馈类型，like、dislike、unknown分别考虑。假设置信度like > dislike >> unknown；
最后作者进行了验证，证明混合多棵树还是能有一定的效果提升。
一些感想
- 整个思路和实现都并不复杂，简单是种大美。不需要额外的标注、不需要进行用户/item聚类，对于数据充足、缺乏较强领域知识和强悍pm的应用完全可以快速尝试；
- 对于数据不充足的应用，类似的做法局限性较大。之前也跟几位同学讨论过，或许可以考虑把挖掘目标从领域内的兴趣描述（喜欢什么类型的音乐、电影），转移到对用户通用属性（如性别、年龄段）的挖掘上，带入先验知识再来做处理;
附：推荐系统高峰论坛的其他链接
- 官方资料：
- wangyuantao《2011推荐系统高峰论坛——参后感》（需fanQiang）：
- wentrue《2011推荐系统峰会及全民娱乐》：
- chen_lst《2011推荐系统论坛游记：爱的反义词不是恨》：