模型融合的投票算法 2011-09-08

使用单一模型的风险是很大的。首先单一模型可能只考虑数据集的一方面,不能概括所有影响事务的因素,比如时间序列模型更适合平稳或增长平稳的数据,对明显波动且有周期规律的数据采取其他模型可能更合理。其次,某些模型对数据集的是有依赖性的,比如时间序列模型对波峰波谷非常敏感,有时候为准确性不得不采用短期数据,很有可能造成过拟合。在数据挖掘竞赛(比如KDDcup以及Netflix大赛)中,名次较高的参赛队都采用了多种模型,并用一种合并算法将最终模型合并。尤其Netflix大赛中获得冠军的团队就是最后时刻由原2,3名团队合并而成的,最终他们提交的模型中融合了100多种算法。模型融合不仅能进一步提高模型的整体效果,而且能有效防止过拟合现象。在测试集数据较少的情况下,或者目的是在于预测的场合,利用模型融合防止过拟合尤为重要。下面简述几种可用于模型融合的投票算法:

简单投票算法:假设我们目的是给出集合B(包含5个元素)排位的次序。比如两个结果给出排位次序为: 1,3,4,2,5 2,4,1,5,3 则可以将这两个结果看成是两个用户对集合B的评价,其中分值越小表明用户对其倾向性越高。投票算法的思想是少数服从多数,即只有当多数人都同意某个人的排位时,这个排位才是稳定的。对于上述结果,投票结果为: 1+2, 3+4, 4+1, 2+5, 5+3 票数最小的排位将越靠前。投票后的次序为: 1,4,2,3,5 另外对于两个投票结果的用户,也可以通过计算方差进行排序:方差越小则排位靠前。但是简单投票算法并没有考虑对投票人进行权值分配。

Scaled 投票算法:所谓Scaled投票算法是仿照一等奖1人(奖励10000元),二等奖2人(奖励5000元),三等奖10人(奖励1000元)……而设计,这样我们可以给靠前的排序与靠后的排序不同的排序序号。例如,在一个序列中排名靠前的排序可以得到比较高的奖励。 可以设计一个函数使得 y=f(x),其中,x是候选用户B在某个序列中的排序,y是我们给它的排序序号(奖励)。最简单的情况下f(x)是个线性函数,如y=x,即简单投票算法。同时f(x)可以是非线性函数,如y=x^2,或者y=x^(1/2),或者阶梯函数y=(int)ln(x), y=e^(int)ln(x)。

Bootstrap投票算法:所谓Bootstrap投票算法是指为了增加结果的随机性而使用的一种抽样策略。例如,在有10个候选推荐结果的情况下,我们随机从这10个候选结果中抽取N次,用这N次结果做投票,从而增加最终结果的随机性。N可以取任意一个正整数,但N越大,结果的随机性就会越小,最终也将收敛于最简单的投票算法。

后两种算法实际上是在不同层次上对简单投票算法的探索:可以认为Scaled投票算法是对每个候选推荐结果的学习和修正,而Bootstrap投票算法是对投票策略的学习和修正。



Powered by Jekyll on GitHub | ©2016 Meroa | Last modified: 2018-03-22