机器学习算法之决策树

什么是决策树

决策树(Decision Tree)是一种简单但是广泛使用的分类器。通过训练数据构建决策树,可以高效的对未知的数据进行分类。决策数有两大优点:1)决策树模型可以读性好,具有描述性,有助于人工分析;2)效率高,决策树只需要一次构建,反复使用,每一次预测的最大计算次数不超过决策树的深度。

继续阅读机器学习算法之决策树

剖析IForest:用于金融风控中的反欺诈算法

 

iForest用于挖掘异常数据,如网络安全中的攻击检测和流量异常分析。我们主要使用它在风控场景中做欺诈行为挖掘,算法对内存要求很低,且处理速度很快,其时间复杂度也是线性的。可以很好的处理高维数据和大数据,并且也可以作为在线异常检测。
继续阅读剖析IForest:用于金融风控中的反欺诈算法

20150806@Tencent 数学建模分享

来这个team之后被安排到做数据挖掘,最近也在折腾推荐系统,不是简单的做个算法,更多的其实对我的挑战是学习hadoop,编写mapreduce。

因为之前参加过两次数学建模竞赛,空隙中做了一次关于数学建模的分享,自己其实也有很多不足的地方,不过接触更多工程后,理解更深刻,更能体会掌握一些数学模型后对解决实际问题时找到突破口是非常有帮助的。

下面是我本次分享的ppt:

http://chingzhu.com/share/20150806@tencent.pptx

主要有对数学模型的一个概览;

了解一次建模过程;

对目前常见的推荐系统方法的一个介绍;

对item cf的一个实现;

对latent factor算法的一个介绍;

以及比较好用的降维方法(pca)的介绍。

优化算法之遗传算法及其matlab实现

一.进化论知识 

作为遗传算法生物背景的介绍,下面内容了解即可:

  种群(Population)生物的进化以群体的形式进行,这样的一个群体称为种群。

  个体:组成种群的单个生物。

  基因 ( Gene ) 一个遗传因子。 

  染色体 ( Chromosome ) :包含一组的基因。

  生存竞争,适者生存:对环境适应度高的、牛B的个体参与繁殖的机会比较多,后代就会越来越多。适应度低的个体参与繁殖的机会比较少,后代就会越来越少。

  遗传与变异:新个体会遗传父母双方各一部分的基因,同时有一定的概率发生基因变异。

简单说来就是:繁殖过程,会发生基因交叉( Crossover ) ,基因突变 ( Mutation ) ,适应度( Fitness )低的个体会被逐步淘汰,而适应度高的个体会越来越多。那么经过N代的自然选择后,保存下来的个体都是适应度很高的,其中很可能包含史上产生的适应度最高的那个个体。

二.遗传算法思想 

借鉴生物进化论,遗传算法将要解决的问题模拟成一个生物进化的过程,通过复制、交叉、突变等操作产生下一代的解,并逐步淘汰掉适应度函数值低的解,增加适应度函数值高的解。这样进化N代后就很有可能会进化出适应度函数值很高的个体。

举个例子,使用遗传算法解决“0-1背包问题”的思路:0-1背包的解可以编码为一串0-1字符串(0:不取,1:取) ;首先,随机产生M个0-1字符串,然后评价这些0-1字符串作为0-1背包问题的解的优劣;然后,随机选择一些字符串通过交叉、突变等操作产生下一代的M个字符串,而且较优的解被选中的概率要比较高。这样经过G代的进化后就可能会产生出0-1背包问题的一个“近似最优解”。

  编码:需要将问题的解编码成字符串的形式才能使用遗传算法。最简单的一种编码方式是二进制编码,即将问题的解编码成二进制位数组的形式。例如,问题的解是整数,那么可以将其编码成二进制位数组的形式。将0-1字符串作为0-1背包问题的解就属于二进制编码。假设x1,x2同为0~7的整数。那么其可以编码为3位2进制,即110111可等同于x1,x2=[6,7]。我们需要在编程的时候编写编解码程序。

遗传算法有3个最基本的操作:选择,交叉,变异。

  选择:选择一些染色体来产生下一代。一种常用的选择策略是 “比例选择”,也就是个体被选中的概率与其适应度函数值成正比。假设群体的个体总数是M,那么那么一个体Xi被选中的概率为f(Xi)/( f(X1) + f(X2) + …….. + f(Xn) ) 。比例选择实现算法就是所谓的“轮盘赌算法”( Roulette Wheel Selection ) ,轮盘赌算法的一个简单的实现如下:(matlab)

function RWS(p)

rand(‘state’,sum(clock);

% assume that p(i) has been initialized

r = rand(1,1);

psum = 0;

for i = 1:length(p)

    psum = psum + p(i);

    if psum>=r,

        chose = i;

        return;

    end

end

初始化一个 p = [ 0.1 0.3 0.4 0.2];

>> RWS(p)

ans = 3

交叉(Crossover):2条染色体交换部分基因,来构造下一代的2条新的染色体。例如:

交叉前:

00000|011100000000|10000

11100|000001111110|00101

交叉后:

00000|000001111110|10000

11100|011100000000|00101

染色体交叉是以一定的概率发生的,这个概率记为Pc 。

 

变异(Mutation):在繁殖过程,新产生的染色体中的基因会以一定的概率出错,称为变异。变异发生的概率记为Pm 。例如:

变异前:

000001110000000010000

变异后:

000001110000100010000

 

适应度函数 ( Fitness Function ):用于评价某个染色体的适应度,用f(x)表示。有时需要区分染色体的适应度函数与问题的目标函数。例如:0-1背包问题的目标函数是所取得物品价值,但将物品价值作为染色体的适应度函数可能并不一定适合。适应度函数与目标函数是正相关的,可对目标函数作一些变形来得到适应度函数。

为了更好的理解先看一段伪代码吧。

基本遗传算法伪代码

/*
* Pc:交叉发生的概率
* Pm:变异发生的概率
* M:种群规模
* G:终止进化的代数
* Tf:进化产生的任何一个个体的适应度函数超过Tf,则可以终止进化过程
*/
初始化Pm,Pc,M,G,Tf等参数。随机产生第一代种群Pop

do
{
计算种群Pop中每一个体的适应度F(i)。
初始化空种群newPop
do
{
根据适应度以比例选择算法从种群Pop中选出2个个体   //选择
if ( random ( 0 , 1 ) < Pc )
{
对2个个体按交叉概率Pc执行交叉操作   //交叉
}
if ( random ( 0 , 1 ) < Pm )
{
对2个个体按变异概率Pm执行变异操作  //变异
}
将2个新个体加入种群newPop中
} until ( M个子代被创建 )
用newPop取代Pop     //适应度函数的判断或繁殖代数超过一定后终止循环
}until ( 任何染色体得分超过Tf, 或繁殖代数超过G )

三.基本遗传算法优化 

下面的方法可优化遗传算法的性能。

  精英主义(Elitist Strategy)选择:是基本遗传算法的一种优化。为了防止进化过程中产生的最优解被交叉和变异所破坏,可以将每一代中的最优解原封不动的复制到下一代中。

  插入操作:可在3个基本操作的基础上增加一个插入操作。插入操作将染色体中的某个随机的片段移位到另一个随机的位置。

 

 

三.飞机巡航路线遗传算法优化的matlab实现 

飞机巡航数据

function gasim()
disp(‘模拟退火求巡航路径’);
data=xlsread(‘飞机巡航数据.xlsx’,’sheet1′,’C4:J28′);
x=data(:,1:2:8);x=x(:);
y=data(:,2:2:8);y=y(:);
sj=[x y];
d1=[70,40];
sj0=[d1;sj;d1];
%距离矩阵d
sj=sj0*pi/180;
d=zeros(102);
for i=1:101
for j=i+1:102
temp=cos(sj(i,1)-sj(j,1))*cos(sj(i,2))*cos(sj(j,2))+sin(sj(i,2))*sin(sj(j,2));
d(i,j)=6370*acos(temp);
end
end
d=d+d’;L=102;w=50;dai=100; %w指的是种群的大小
%通过改良圈算法选取优良父代A
for k=1:w
c=randperm(100);
c1=[1,c+1,102];
flag=1;
while flag>0
flag=0;
for m=1:L-3
for n=m+2:L-1
if d(c1(m),c1(n))+d(c1(m+1),c1(n+1))<d(c1(m),c1(m+1))+d(c1(n),c1(n+1)) %交换两个节点的顺序
flag=1;
c1(m+1:n)=c1(n:-1:m+1);
end
end
end
end
J(k,c1)=1:102; %矩阵J的第k行的第c1列的值依次为1:102 %J就是取出来的50个优良的父代
end
J=J/102;
J(:,1)=0;
J(:,102)=1;
rand(‘state’,sum(clock));
%遗传算法实现过程
pby = 0.01; %变异概率
A=J;
for k=1:dai
B=A;
c=randperm(w); %打乱顺序, 产生配对
%交配产生子代B
for i=1:2:w
F1=2+floor(100*rand(1)); %随机选择交换开始的位置
F2=2+floor(100*rand(1)); %随机选择交换结束的位置
if(F1>F2),
tempf = F1;
F1 = F2;
F2 = tempf;
end
%交换相邻染色体的基因
temp=B(c(i),F1:F2);
B(c(i),F1:F2)=B(c(i+1),F1:F2);
B(c(i+1),F1:F2)=temp;
end
%变异产生子代C
by=find(rand(1,w)<pby); % 比pby小的都发生变异
if length(by)==0 % 如果没有变异的, 就随机产生一个
by=floor(w*rand(1))+1;
end
C=A(by,:); % 提取出变异的
L3=length(by);
for j=1:L3 % 交换片段
bw=2+floor(100*rand(1,3)); %产生3个节点, 便于交换两个片段的位置
bw=sort(bw);
C(j,:)=C(j,[1:bw(1)-1,bw(2)+1:bw(3),bw(1):bw(2),bw(3)+1:102]);
end

%将ABC组合起来
G=[A;B;C]; % A父代 B子代 C变异的后代
TL=size(G,1); %TL是G的行数
%在父代和子代中选择优良品种作为新的父代,保证留下最优解
[dd,IX]=sort(G,2);%dd是行升序重排后的结果,IX是索引值
temp(1:TL)=0; %初始化temp
for j=1:TL
for i=1:101
temp(j)=temp(j)+d(IX(j,i),IX(j,i+1)); %求出G中每一种排列的路径和
end
end
[DZ,IZ]=sort(temp);
A=G(IZ(1:w),:); %拿出前五十个排列作为优秀父代进行再次重排
end
path=IX(IZ(1),:) %输出最优解
long=DZ(1)
v=xlsread(‘飞机巡航数据.xlsx’,’sheet1′,’A2′); %得到巡航速度
time=long/v(1,1) %输出所花时间
xx=sj0(path,1);yy=sj0(path,2);
plot(xx,yy,’-o’)

最后得到的图和上一篇里用模拟退火算法得到的差不多,可以自行运行,这里就不贴图了

优化算法之模拟退火算法及matlab示例

一、原理

模拟退火是一种贪心算法,但是它的搜索过程引入了随机因素。模拟退火算法以一定的概率来接受一个比当前解要差的解,因此有可能会跳出这个局部的最优解,达到全局的最优解。以图1为例,模拟退火算法在搜索到局部最优解A后,会以一定的概率接受到E的移动。也许经过几次这样的不是局部最优的移动后会到达D点,于是就跳出了局部最大值A。

模拟退火算法描述:

若J( Y(i+1) )>= J( Y(i) )  (即移动后得到更优解),则总是接受该移动

若J( Y(i+1) )< J( Y(i) )  (即移动后的解比当前解要差),则以一定的概率接受移动,而且这个概率随着时间推移逐渐降低(逐渐降低才能趋向稳定)

这里的“一定的概率”的计算参考了金属冶炼的退火过程,这也是模拟退火算法名称的由来。

根据热力学的原理,在温度为T时,出现能量差为dE的降温的概率为P(dE),表示为:

    P(dE) = exp( dE/(kT) )

其中k是一个常数,exp表示自然指数,且dE<0。这条公式说白了就是:温度越高,出现一次能量差为dE的降温的概率就越大;温度越低,则出现降温的概率就越小。又由于dE总是小于0(否则就不叫退火了),因此dE/kT < 0 ,所以P(dE)的函数取值范围是(0,1) 。

随着温度T的降低,P(dE)会逐渐降低。

我们将一次向较差解的移动看做一次温度跳变过程,我们以概率P(dE)来接受这样的移动。

二、示例

(i). 旅行商问题

旅行商问题 ( TSP , Traveling Salesman Problem ) :有N个城市,要求从其中某个问题出发,唯一遍历所有城市,再回到出发的城市,求最短的路线。

旅行商问题属于所谓的NP完全问题,精确的解决TSP只能通过穷举所有的路径组合,其时间复杂度是O(N!) 。

使用模拟退火算法可以比较快的求出TSP的一条近似最优路径。(使用遗传算法也是可以的,我将在下一篇文章中介绍)模拟退火解决TSP的思路:

1. 产生一条新的遍历路径P(i+1),计算路径P(i+1)的长度L( P(i+1) )

2. 若L(P(i+1)) < L(P(i)),则接受P(i+1)为新的路径,否则以模拟退火的那个概率接受P(i+1) ,然后降温

3. 重复步骤1,2直到满足退出条件

产生新的遍历路径的方法有很多,下面列举其中3种:

1. 随机选择2个节点,交换路径中的这2个节点的顺序。

2. 随机选择2个节点,将路径中这2个节点间的节点顺序逆转。

3. 随机选择3个节点m,n,k,然后将节点m与n间的节点移位到节点k后面。

(ii).飞机巡航问题及其matlab实现

我方有一个基地,经度和纬度为(70,40)。假设我方飞机的速度为1000公里/小时。
我方派一架飞机从基地出发,侦察完敌方所有目标,再返回原来的基地。在敌方每一目
标点的侦察时间不计,求该架飞机所花费的时间(假设我方飞机巡航时间可以充分长)。
这是一个旅行商问题。我们依次给基地编号为1,敌方目标依次编号为2,3,…,
101,最后我方基地再重复编号为102(这样便于程序中计算)。

飞机巡航数据

function mySim()
disp(‘模拟退火求巡航路径’);
data=xlsread(‘飞机巡航数据.xlsx’,’sheet1′,’C4:J28′);
x=data(:,1:2:8);x=x(:)
y=data(:,2:2:8);y=y(:);
si=[x y]; d1=[70,40];
si=[d1;si;d1]; %构成一个环
sj=si;
sj=sj*pi/180; %经纬度化为弧度制
d=zeros(102); %距离矩阵d
for i=1:101
for j=i+1:102 %右上三角矩阵
temp=cos(sj(i,1)-sj(j,1))*cos(sj(i,2))*cos(sj(j,2))+ …
sin(sj(i,2))*sin(sj(j,2));
d(i,j)=6370*acos(temp);
end
end
d=d+d’; %生成距离矩阵
S0=[]; %用于存放最优路径
Sum=inf; %用于存放最优解
rand(‘state’,sum(clock)); %设随机种子,因为计算机产生的都是伪随机数,
%所以我们采用rand(‘state’,sum(clock))来重新设定随机数产生的时间
for j=1:1000
S=[1 1+randperm(100),102]; %randperm(n)用于随机生成1到n的一个排列
temp=0;
for i=1:101
temp=temp+d(S(i),S(i+1)); %求得一个所有的距离和
end
if temp<Sum %更新最小和
S0=S;Sum=temp;
end
end
% 随机解产生完毕
e=0.1^30;L=20000;at=0.999;T=1; %设定温度阈值,最大步长,温度衰减系数,初始温度

%退火过程
for k=1:L
%产生新解
c=2+floor(100*rand(1,2)); %floor向下取整,rand(m,n)生成m*n阶(0,1)随机矩阵
c=sort(c); %顺序排列
c1=c(1);c2=c(2);
%计算代价函数值, 即上述方法中的第一种, 随机选择2个节点,交换路径中的这2个节点的顺序。
df=d(S0(c1-1),S0(c2))+d(S0(c1),S0(c2+1))-d(S0(c1-1),S0(c1))-d(S0(c2),S0(c2+1));
%接受准则
if df<0 %说明更换节点顺序后的方法更好
S0=[S0(1:c1-1),S0(c2:-1:c1),S0(c2+1:102)];
Sum=Sum+df;
elseif exp(-df/T)>rand(1) %否则以退火概率接受当前解
S0=[S0(1:c1-1),S0(c2:-1:c1),S0(c2+1:102)];
Sum=Sum+df;
end
T=T*at; %更新温度
if T<e %如果已经几乎冷却,则停止(0℃)
break;
end
end
% 输出巡航路径及路径长度
S0,Sum
%巡航时间
v=xlsread(‘飞机巡航数据.xlsx’,’sheet1′,’A2′); %得到巡航速度
time=Sum/v(1,1)
%画出路径图
r=size(sj,1);
for i=1:r-1;
plot(si(S0(i),1),si(S0(i),2),si(S0(i+1),1),si(S0(i+1),2),’*’);
text(si(S0(i),1)-0.5,si(S0(i),2)+0.5,num2str(S0(i)));
if i~=101,
text(si(S0(i+1),1)-0.5,si(S0(i+1),2)+0.5,num2str(S0(i+1)));
end
line([si(S0(i),1) si(S0(i+1),1)],[si(S0(i),2) si(S0(i+1),2)]);
title(‘飞机巡航路线(By un1q.me)’);
hold on
end

最后,可以得到以下所示图形及结果:

Sum =

4.5107e+04
time =

45.1073

untitled

基于民意的排序算法(四)

这将是阮先生博客中所提及的排序算法序列的终结篇,下一次写排序算法,应该会跟一些锅内的互联网公司的产品有关。

之前的那些排序方法,都和过去一段时间内的热门排序有关,这个系列的最后两篇,并没有考虑时间的因素,比较适合应用在一些不需要特别在意时效性的产品的排序。 比如对一些国内外经典名著的热门排序,它可以是一个长时期占据榜单的排序。

威尔逊区间

一种常见的错误算法是:

得分 = 赞成票 – 反对票

引一个阮先生提的例子,假定有两个项目,项目A是 60 张赞成票,40张反对票,项目B是 550 张赞成票,450张反对票。请问,谁应该排在前面?按照上面的公式,B会排在前面,因为它的得分(550 – 450 = 100)高于A(60 – 40 = 20)。但是实际上,B的好评率只有 55%(550 / 1000),而A为 60%(60 / 100),所以正确的结果应该是A排在前面。

另一种常见的错误算法是

得分 = 赞成票 / 总票数

如果”总票数”很大,这种算法其实是对的。问题出在如果”总票数”很少,这时就会出错。假定A有 2 张赞成票、0张反对票,B有 100 张赞成票、1张反对票。这种算法会使得A排在B前面。这显然错误。

那么,正确的算法是什么呢?

我们先做如下设定:

(1)每个用户的投票都是独立事件。

(2)用户只有两个选择,要么投赞成票,要么投反对票。

(3)如果投票总人数为n,其中赞成票为k,那么赞成票的比例p就等于k/n。

熟悉统计学的同学应该已经看出来这里的p服从二项分布(binomial distribution)。

我们的思路是,p越大,就代表这个项目的好评比例越高,越应该排在前面。但是,p的可信性,取决于有多少人投票,如果样本太小,p就不可信。好在我们已经知道,p服从”两项分布”,因此我们可以计算出p的置信区间。所谓”置信区间”,就是说,以某个概率而言,p会落在的那个区间。比如,某个产品的好评率是 80%,但是这个值不一定可信。根据统计学,我们只能说,有 95% 的把握可以断定,好评率在 75% 到 85% 之间,即置信区间是[75%, 85%]。

那么如何设计一个好的排序算法的步骤就显而易见了。

1. 计算每个item的”好评率”(即赞成票的比例)。

2. 计算每个”好评率”的置信区间(假设以 95% 的概率)。

3. 根据置信区间的下限值,进行排名。这个值越大,排名就越高。

这样做的原理是,置信区间的宽窄与样本的数量有关。

这里先补充一下置信区间的概念(可能有朋友学过已经忘了)

置信区间是指由样本统计量所构造的总体参数的估计区间。在统计学中,一个概率样本的置信区间(Confidence interval)是对这个样本的某个总体参数的区间估计。置信区间展现的是这个参数的真实值有一定概率落在测量结果的周围的程度。置信区间给出的是被测量参数的测量值的可信程度,即前面所要求的“一定概率”。这个概率被称为置信水平。举例来说,如果在一次大选中某人的支持率为55%,而置信水平0.95上的置信区间是(50%,60%),那么他的真实支持率有百分之九十五的机率落在百分之五十和百分之六十之间,因此他的真实支持率不足一半的可能性小于百分之2.5。 如例子中一样,置信水平一般用百分比表示,因此置信水平0.95上的置信空间也可以表达为:95%置信区间。置信区间的两端被称为置信极限。对一个给定情形的估计来说,置信水平越高,所对应的置信区间就会越大。

样本量对置信区间的影响:在置信水平固定的情况下,样本量越多,置信区间越窄。

计算步骤

第一步:求一个样本的均值
第二步:计算出抽样误差。
人们经过实践,通常认为调查:
100个样本的抽样误差为±10%;
500个样本的抽样误差为±5%;
1,200个样本时的抽样误差为±3%;
第三步:用第一步求出的“样本均值”加、减第二步计算的“抽样误差”,得出置信区间的两个端点。这样就可以得到其下限值了。

二项分布的置信区间有多种计算公式,以上是”正态区间”(Normal approximation interval),教科书里几乎都是这种方法。但是,它只适用于样本较多的情况(np > 5 且 n (1 − p) > 5),对于小样本,它的准确性很差。

1927年,美国数学家 Edwin Bidwell Wilson 提出了一个修正公式,被称为”威尔逊区间”,很好地解决了小样本的准确性问题。

它的下限值为

5-300x108

可以看到,当n的值足够大时,这个下限值会趋向p^。如果n非常小(投票人很少),这个下限值会大大小于p^。实际上,起到了降低”赞成票比例”的作用,使得该项目的得分变小、排名下降。

Bayes平均

“威尔逊区间”,它解决了投票人数过少、导致结果不可信的问题。

如果只有 2 个人投票,”威尔逊区间”的下限值会将赞成票的比例大幅拉低。这样做固然保证了排名的可信性,但也带来了另一个问题:排行榜前列总是那些票数最多的项目,新项目或者冷门的项目,很难有出头机会,排名可能会长期靠后。

而一部好莱坞大片有 10000 个观众投票,一部小成本的文艺片只有 100 个观众投票。这两者的投票结果,怎么比较?如果使用”威尔逊区间”,后者的得分将被大幅拉低,这样处理是否公平,能不能反映它们真正的质量?

一个合理的思路是,如果要比较两部电影的好坏,至少应该请同样多的观众观看和评分。既然文艺片的观众人数偏少,那么应该设法为它增加一些观众。

以IMDB 为例,它是世界最大的电影数据库,观众可以对每部电影投票,最低为 1 分,最高为 10 分。

在排名页面的底部,IMDB 给出了它的计算方法。

22

其中,

  • WR, 加权得分(weighted rating)。
  • R,该电影的用户投票的平均得分(Rating)。
  • v,该电影的投票人数(votes)。
  • m,排名前 250 名的电影的最低投票数(现在为 3000)。
  • C, 所有电影的平均得分(现在为6.9)。

不难看出,IMDB 为每部电影增加了 3000 张选票,并且这些选票的评分都为6.9。这样做的原因是,假设所有电影都至少有 3000 张选票,那么就都具备了进入前 250 名的评选条件;然后假设这 3000 张选票的评分是所有电影的平均得分(即假设这部电影具有平均水准);最后,用现有的观众投票进行修正,长期来看,v/(v+m)这部分的权重将越来越大,得分将慢慢接近真实情况。

这样做拉近了不同电影之间投票人数的差异,使得投票人数较少的电影也有可能排名前列。

把这个公式写成一个更一般的形式:

33

其中,

  • C,投票人数扩展的规模,是一个自行设定的常数,与整个网站的总体用户人数有关,可以等于每个项目的平均投票数。
  • n,该项目的现有投票人数。
  • x,该项目的每张选票的值。
  • m,总体平均分,即整个网站所有选票的算术平均值

这种算法被称为”贝叶斯平均”(Bayesian average)。因为某种程度上,它借鉴了”贝叶斯推断”(Bayesian inference)的思想:既然不知道投票结果,那就先估计一个值,然后不断用新的信息修正,使得它越来越接近正确的值。(比如一开始,这部电影没有人投票,那么它默认的就是其他电影的平均得分,当它票数得到很多之后,假设到了一定程度,我们可以忽略分子的左边那项,忽略分母中的c,那么就接近它的真实得分了(实际是一个算数平均值,得到评分的总和/总票数))

因此,这种方法可以给一些投票人数较少的项目,以相对公平的排名。

“贝叶斯平均”也有缺点,主要问题是它假设用户的投票是正态分布。比如,电影A有 10 个观众评分,5个为五星,5个为一星;电影B也有 10 个观众评分,都给了三星。这两部电影的平均得分(无论是算术平均,还是贝叶斯平均)都是三星,但是电影A可能比电影B更值得看。

阮一峰先生提到解决这个问题的思路是,假定每个用户的投票都是独立事件,每次投票只有n个选项可以选择,那么这就服从”多项分布”(Multinomial distribution),就可以结合贝叶斯定理,计算该分布的期望值。由于这涉及复杂的统计学知识,这里就不深入了,感兴趣的朋友可以继续阅读 William Morgan 的How to rank products based on user input(后期我会再写一个读后的笔记)

基于民意的排序算法(三)

今天会更新阮先生博文中提到的剩下4篇算法,一口气看完了,正好来整理下笔记,再谈谈自己的理解。也会在之后学习更多的排序算法。

阮先生提到的几篇算法中基本都是从现实生活中的应用中提取出来的,具有实用性,这点让我感触很深。在我看来,这些算法通俗易懂,是绝对不会出现在那些“高大上”的paper中的,但它们确实是realistic的。

Stack Overflow

这是一个知名的程序员问答平台。它对一个问题的排名就不只是考虑了对问题投赞成票和反对票的次数以及时间的因素,还考虑了当问题被回答后,对回答点赞以及反对的因素。

排名算法的作用是,找出某段时间内的热点问题,即哪些问题最被关注、得到了最多的讨论。

其创始人曾在前几年公布了它的排序算法:

stack flow

现在让我们来大致分析以下这个式子所涉及的因子影响score的机制:

首先,我们看看分子项。

Qviews是这个问题的浏览次数,跟reddit像的是,此部分的影响呈对数上升。

然后是Qanswers*Qscore,这个是反应的是一个问题的分值与其回答数和得分值呈正比,获得相同数量评论的问题,如果这个问题本身的分值更高的(根据问题得到的点赞和反对数,即Qscore = 支持数-反对数),显然排名更高。而没有得到回答的问题,即使点赞数量很高,这一项分值也是无效的。

Ascores指得是回答的得分情况,这也就意味着,好的回答能为这个问题加分,而差的则相反。

然后,看看分母项,主要是跟距离问题发布的时间和距离最后一次回答问题的时间有关系。这就意味着,随着时间的增长,这个问题的分值就会逐渐减小。

stackflow的排序方法跟问题的浏览量以及回答的个数、问题的得分、回答的得分呈正比,而与问题的发布时间及回答时间的距离呈反比

 

牛顿冷却定律

比起之前的三篇中提及的三种算法,这里更偏重一般的数学问题。

其实排名也可以看作一个热度冷却的过程。

(1)任一时刻,网站中所有的文章,都有一个”当前温度”,温度最高的文章就排在第一位。

(2)如果一个用户对某篇文章投了赞成票,该文章的温度就上升一度。

(3)随着时间流逝,所有文章的温度都逐渐”冷却”。

这样假设的意义,在于我们可以照搬物理学的冷却定律,使用现成的公式,建立”温度”与”时间”之间的函数关系,轻松构建一个”指数式衰减”(Exponential decay)的过程。

伟大的物理学家牛顿,早在 17 世纪就提出了温度冷却的数学公式,被后人称作”牛顿冷却定律”(Newton’s Law of Cooling)。

“牛顿冷却定律”非常简单,用一句话就可以概况:

物体的冷却速度,与其当前温度与室温之间的温差成正比。可以写为下式

1

 

其中,T (t)是温度(T)的时间(t)函数。微积分知识告诉我们,温度变化(冷却)的速率就是温度函数的导数T'(t)。

通过改写方式,积分后(推导过程可以参照阮一峰先生的博文),对室温置0后,可以得到下式(可以想象成,一个物体在被加热后的冷却过程,经过一个很长的时间,会回到室温。而我们对文章评分的要求可以是让其在长时间后分值变为0,即室温为0)

2

 

上面这个方程,就是我们想要的最终结果:

本时刻的温度 = 上一时刻的温度 x exp (-(冷却系数) x 间隔的小时数)

将这个公式理解为排序的算法,既是:

本时刻的得分 = 上一时刻的得分 x exp (-(冷却系数) x 间隔的小时数)

其中,”冷却系数”是一个你自己决定的值。如果假定一篇新文章的初始分数是 100 分,24小时之后”冷却”为 1 分,那么可以计算得到”冷却系数”约等于0.192。如果你想放慢”热文排名”的更新率,”冷却系数”就取一个较小的值,否则就取一个较大的值。(源于阮先生博客)

 

 

基于民意的排序算法(二)

上一篇文章中谈到了对hacker news ranking algorithm的理解。

这篇将介绍Reddit排名算法如何工作。

Reddit是用 Python 编写的开源系统,整站代码可以自由获得(代码在这里)。他们的排序算法使用Pyrex(一种用来编写Python C扩展的语言)实现。之所以用 Pyrex 是出于效率的考虑,下面贴一个由一个谈到reddit算法的博主重写成纯Python的,这样更易于阅读。

热度排名(默认新闻排名算法)是这样实现的:

# Rewritten code from /r2/r2/lib/db/_sorts.pyx

 

from datetime import datetime, timedelta

from math import log

 

epoch = datetime(1970, 1, 1)

 

def epoch_seconds(date):

“””Returns the number of seconds from the epoch to date.”””

td = date – epoch

return td.days * 86400 + td.seconds + (float(td.microseconds) / 1000000)

 

def score(ups, downs):

return ups – downs

 

def hot(ups, downs, date):

“””The hot formula. Should match the equivalent function in postgres.”””

s = score(ups, downs)

order = log(max(abs(s), 1), 10)

sign = 1 if s > 0 else -1 if s < 0 else 0

seconds = epoch_seconds(date) – 1134028003

return round(order + sign * seconds / 45000, 7)

以下是从seomoz摘来的对算法的数学描述:

reddit

 

提交时间的影响

新闻排名中的提交时间可作如下考虑:

  • 提交时间对排名有很大的影响,新提交的新闻排在前面
  • 评分不会随着时间的推移而下降,但新的新闻会得到比旧新闻更高的分数。这种方法和Hacker News不同,Hacker News的评分会随着时间的推移而下降。

 

对数标度
Reddit的热度排名使用对数函数,前面的投票比后面的投票有更高的权重。大概像这样:

前10个“顶”和接下来100个“顶”拥有一样的权重,而这100个“顶”又和接下来1000个“顶”有相同的权重,依此类推……

“踩”的影响
Reddit是有“踩”的几个网站之一。正如代码中所描述的,一条新闻的“评分”定义为: “顶数” – “踩数”
所以,有争议(“顶”和”踩“数目相当)的新闻,得到的评分比“顶”数占优势的新闻较低。

 

 

总结

Amir总结了一下Reddit的算法:
 Submission time(提交时间)是一个非常重要的参数,玩聚SR和RT就都是参照Reddit重视文章或热门消息的发布时间的。
 前10票的得分,和接下来的100票,是一样的。这样,得了10票的文章,就可能和得了50票的文章得分相似。
 争议性话题(得了很多反对票的)得分会很低。
(Amir还讲了Reddit的comment ranking,有兴趣可以自己去看看)

与上一篇中提到的hacker news ranking比较

Hacker News的算法能够让老文章消失得更快,比如24小时之前的文章,基本就不会在榜单上存留。

Reddit的算法则能够让众望所归的那些优秀文章能够停留相当长时间,然后随着时间流逝,一点一点地被新的、好的文章挤下去。

Reddit的算法还有一个好处就是,当投票数变化了,才需要去重新计算一次文章的Rank,不用管时间的流逝。

基于民意的排序算法(一)

第二次训练结束了。

闲来无事,也学学、谈谈算法。顺序参考了阮一峰先生的博客,同时也希望能像他一样,有空的时候就多学习学习,谈谈自己的感悟。

如阮先生说的,最直觉、最简单的算法,莫过于按照单位时间内用户的投票数进行排名。得票最多的项目,自然就排在第一位。

比如旧版的delicious有一个热门书签,就采取依据最近60分钟的用户点击量来显示排名。听上去十分简单,但是却有一些弊端,比如前一个小时和后一个小时的榜单有很大不同,有一些时间长远但是经常被点击的page会在排行榜上久久不能下去,这样子有失实效性。

今天先介绍下hacker news ranking algorithm.

根据维基百科相关词条,Hacker News是一家关于计算机黑客和创业公司的社会化新闻网站,与其它社会化新闻网站不同的是, Hacker News 没有踩或反对一条提交新闻的选项;只可以赞成或是完全不投票。简而言之,Hacker News 允许提交任何可以被理解为“任何满足人们求知欲”的新闻。

How it works

(= gravity* 1.8 timebase* 120 front-threshold* 1
     nourl-factor* .4 lightweight-factor* .17 gag-factor* .1)
  (def frontpage-rank (s (o scorefn realscore) (o gravity gravity*))
    (* (/ (let base (- (scorefn s) 1)
            (if (> base 0) (expt base .8) base))
          (expt (/ (+ (item-age s) timebase*) 60) gravity))
       (if (no (in s!type 'story 'poll))  .8
           (blank s!url)                  nourl-factor*
           (mem 'bury s!keys)             .001
                                          (* (contro-factor s)
                                             (if (mem 'gag s!keys)
                                                  gag-factor*
                                                 (lightweight s)
                                            lightweight-factor*
                                                  1)))))
上述代码是hacker news给出的一段核心算法的代码。

文章的得分是基于他们提交以来,获得的赞成投票数,同时通过下列公示计算出得分。上图是hacker news给出的一段核心算法的代码。

7cc829d3gw1eb6vqk21zyg207s01dgld

其中,

votes表示帖子的得票数,减去1是为了忽略发帖人的投票。

age表示距离发帖的时间(单位为小时),加上2是为了防止最新的帖子导致分母过小(之所以选择2,可能是因为从原始文章出现在其他网站,到转贴至Hacker News,平均需要两个小时)。

由于在这个公式中时间的指数比投票的指数更大,因此,一篇文章的得分最终会降到0分。所以,没有一篇文章会长期在首页出现。这个指数称为重力因子。

penalties是一种罚分机制,主要是对一些内容违规的帖子进行处罚,这样它的分值会随着时间的流逝下降得比其他的帖子快。

罚分的影响

采用得分计算公式,可以计算罚分的影响。如果一篇文章被罚了0.4分,那么这篇文章获得的每一个赞成投票,被算成0.3票。或者,这篇文章会以比正常下降速度快66%的速度在排名中下滑。0.1分的罚分,相当于每一个赞成投票,被算为0.05票,或者是,文章以3.6倍下滑速度在排名中下降。因此,0.4分的罚分影响很大,而0.1分的罚分可以认为是相当严厉的。

现在,知道了算法的构成,就可以调整参数的值,以便适用于自己的应用程序。