自动化时代的机械工，记KDD2009的获胜者报告-数据挖掘算法研究

自动化时代的机械工，记KDD2009的获胜者报告

正如我常说的，美丽而智能的产品或技术后面，通常隐藏着无数的脏活累活机械活。强如google那样智能直至个性化的技术产品，在那风光无限的PageRank后面，也有大量的人工标注、数据过滤、参数调节，以及与天斗与人斗的anti-spammer工作。

上周重读KDD2009竞赛的获奖者报告，发现其中也不乏这样的情感。

先大致介绍一下KDD2009竞赛的情况。KDD大会是每年数据挖掘与机器学习界的盛会，每次都牛人牛文云集。而每年伴随着大会的到来都会有一次算法竞赛，研究对象通常是某业界公司赞助的一批真实数据，研究问题也就是这些公司在实践中所关心的核心问题。

这里要说的KDD2009竞赛的数据是来自于法国Orange电信公司的客户特征描述数据。其中50000个带标签的训练数据，50000个无标签的测试数据。均有15000个特征变量。参赛者要根据这批数据训练三个分类模型，分别对客户的忠诚度、消费欲和增值服务倾向性作出二元判别。模型评判标准是ROC曲线的覆盖面积（AUC，参看上一篇文章）。竞赛的流程这里略去不讲，有兴趣的可以参看后面的参考文献，反正最后澳大利亚的墨尔本大学拿了两个奖项中的一个。其实现方法说不上多美，只是循规蹈矩地特征选择+有针对性的特征变换+现成的机器学习方法。这也说明在解决现实问题中不一定要刻意追求方法上的创新，对数据的分析理解后的预处理+成熟可用的机器学习模型即可解决大部分的工程问题。

1、特征选择
电信公司提供的特征变量有15000个，但大部分都与最终的分类任务没什么关系，无论出于计算效率还是降低数据噪声的目的，事前做一番特征筛选都是有必要的。

在剔除掉近20%的明显无用的特征后（缺失值过多或取值一样的特征），作者对剩下的特征集中的类别型变量与连续型变量都采用了同样的方法来计算特征的有效性。首先要把连续变量分桶，按每1%的间隔分成一百个离散的桶，这样就可以把连续变量与类别型变量一视同仁地处理了。接下来用单一的一个特征变量去预测目标变量（计算某特征取值或特征桶内正样本的比例，作为这个取值或这个桶对正样本的预测概率），并且可以计算出这个简单分类器的AUC值。根据每个特征的AUC值作一个排序，得到如图1所示的变量AUC值分布图。然后作者根据分布曲线的变化取了前2000个特征，作为后续处理的候选。

图1 忠诚度模型的特征AUC排序

2、类别型特征的变换
类别特征有时会存在着取值过多的情况，比如5万个样本中某个特征就有超过1万个不同的取值，必然注定了某些特征取值只覆盖了极少数的样本，如果要模型勉强地去拟合这些特殊的情况，必定会导致过拟合的出现。所以有必要对这些取值过多的变量作合并。

作者最初想到的方法是对于那些覆盖样本过多的特征取值，根据它们决定的正样本的数量多还是负样本的数量多而合并为两类，以求达到跟目标输出的最大相关。但这种合并方法在应用到测试集中时非常糟糕，很显然这导致了过拟合的出现。

于是作者接下来用了一种很蛮不讲理的方法，规则为，如果特征的不同取值数超过25个：

• 保留那些覆盖样本量超过1000的取值
• 把那些覆盖样本量在500-999之间的那些取值合并为一个新值
• 把那些覆盖样本量在250-499之间的那些取值合并为一个新值
• 把那些覆盖样本量在1-249之间的那些取值合并为一个新值

好像作者的意思是说，我只要把取值的数量减少就好了，天知道这样的合并有没有什么特别的含义，反正这么做了之后效果确实好了。

3、分类模型的选择
数据预处理完毕之后，作者没有再造一个分类器的轮子，而是选择了时下流行的boosting+决策树的分类器融合方法，甚至连实现都没有做，直接用了R的gbm包。好吧，这就是我为什么会找到这篇文章的原因。gbm包根据Friedman对boosting思想在统计优化角度的解释（参考文献[2]），做了成熟的实现，在我的PackageRank里面的分值为1.69（排位259）。因为这不是参赛作者的工作，所以报告中没有详细介绍，只是说了一下最后训练的参数。

这个分类器的好处在于可以处理缺失值、连续值、类别数据；它不会受极端数据及非规则连续变量分布的影响；它可以把特征间的相互影响也model进去；还可以处理非线性依赖关系。

根据这个分类器，作者算出了竞赛所需的三个模型，如图2所示。可以看到的是，最后三个模型所使用的特征数量只是在200个左右。Class Weight是为了应对正负样本的不平衡，为了增加正样本在boostrap中被抽中的概率而人为地提高权重。剩下的依次是学习率、树的数量（迭代次数）、每颗树的深度。

图2 模型参数

最后，作者不无自豪地告诉我们，他们所有的计算都是在一台2G的windows笔记本上完成的，计算工具是R+SAS。似乎也在揶揄拿了另一个奖项的IBM Research：我们可不需要大集群的计算哦。

你刚才看到的是一个很接近于现实问题的求解过程，漂亮么，我觉得一点都不漂亮，甚至是很枯燥，它没有通常paper中所描述的那么理想与完美，你需要对自己的数据有很深入的了解，如果更比这里深一层，你了解这个样本及特征所代表的现实意义的话，你也许还会用上这个领域的先验知识来指导你的处理。所以，通常的实际问题解决路径是：机械化的又艺术化的工作加上优雅的模型=问题的解决。

参考文献

[1] Predicting customer behaviour: The University of Melbourne’s KDD Cup report

[2] Additive logistic regression: a statistical view of boosting

关于作者