首页 ›存档› 技术 › 查看内容

【模型算法】解析滴滴算法大赛---GBDT进行数据预测

2018-3-30 13:00 |来自: 互联网 325 0

摘要: GBDT 网友说可以使用GBDT的方法来进行数据预测。所以，我们先来聊聊GBDT算法的一些基础知识。熵凡是说到算法，人工智能，机器学习的文章，多半一定要说到熵这个概念的。什么是熵？百度一下：熵（entropy）指的 ...

GBDT

网友说可以使用GBDT的方法来进行数据预测。所以，我们先来聊聊GBDT算法的一些基础知识。

熵

凡是说到算法，人工智能，机器学习的文章，多半一定要说到熵这个概念的。什么是熵？

百度一下：

熵（entropy）指的是体系的混乱的程度，它在控制论、概率论、数论、天体物理、生命科学等领域都有重要应用，在不同的学科中也有引申出的更为具体的定义，是各领域十分重要的参量。熵由鲁道夫克劳修斯（Rudolf Clausius）提出，并应用在热力学中。后来在，克劳德艾尔伍德香农（Claude Elwood Shannon）第一次将熵的概念引入到信息论中来。

一个体系越是单调，则熵越低，反之亦然。

这里我们引用数据挖掘大神的文章来接单说一下熵。

如果有一个字符串，里面包含了4种字符，每种出现的概率都是P= 1/4。

　　P(X=A) = 1/4

　　P(X=B) = 1/4

　　P(X=C) = 1/4

　　P(X=D) = 1/4

这样的字符串可能是：BAACBADCDADDDA。传送这样的字符串，每一个字符需要用几个bit？

答案是2个bit

A = 00, B = 01, C = 10, D =11

如果有一个字符串，里面包含了4种字符，但是每个字符串出现的概率不同

　　P(X=A) = 1/2

　　P(X=B) = 1/4

　　P(X=C) = 1/8

　　P(X=D) = 1/8

传送这样的字符串，每一个字符平均需要用几个bit？注意这里说平均。

答案是1.75个bit

A = 0, B = 10, C = 110, D =111

(如果使用等概率的方法， A = 00, B = 01, C = 10, D =11，则无法节省编码量，还是2个bit)

这里巧妙的做到了，出现概率高的字符，使用的bit位少，同时做到了编码上的问题。

（AB =〉010 和 C 110，D 111 不重复。AA =〉00 和 B 10 不重复等）

有如果有一个字符串，里面3种字符串，每种出现概率都是 1/3呢？

最简单的编码方式是 A = 00, B = 01, C = 10, 这样是2个bit，但是如果好好计算一下，可以做到1.6个bit。

A=10，B= 11，C = 0（理论上是1.58496 个bit）

有如果有一个字符串，里面N种字符串，每种出现概率是 PN呢？

如果有一个字符串，里面包含了4种字符，每种出现的概率都是P= 1/4 = 0.25。

　log(0.25,2) = - 2

　H(X) = - (1/4)log(0.25,2) - (1/4)log(0.25,2) - (1/4)log(0.25,2) - (1/4)log(0.25,2) = 2;

如果要表示下图的H（X）和H（Y）呢？

这个很容易计算

H（X）= 1.5

P（Math） = 1/2 P（History）= 1/4 P（CS）= 1/4

log(0.25,2) = - 2 log(0.5,2) = - 1

H(X) = - (1/2)log(0.5,2) - (1/4)log(0.25,2) - (1/4) * log(0.25,2) = 0.5 0.5 0.5 = 1.5;

H（Y）= 1

P（Yes） = 1/2 P（No） = 1/2

H(Y) = - (1/2)log(0.5,2) - (1/2)log(0.5,2) = 0.5 0.5 = 1;

如果说，我们的计算范围只是 X = Math 的数据。那么这个时候 H（Y | X = Math) 是多少呢？是多少呢？答案是1。（一共4条记录，但是Y有两种可能性）
如果说，我们的计算范围只是 X = Histroy 的数据。那么这个时候 H（Y| X = Histroy)是多少呢？答案也是 0 。（一共2条记录，但是Y只是一种可能性）
如果说，我们的计算范围只是 X = CS 的数据。那么这个时候 H（Y| X = CS)是多少呢？答案也是 0 。（一共2条记录，但是Y只是一种可能性）

H（Y | X ): 条件熵 Conditional Entropy

现在我们考虑一个问题，如果我们需要将Y传输出去。当然，如果直接传输的话， H（Y）= 1。

如果我们在传输的时候，双方都知道X的值，则需要熵定义为H（Y | X )。

例如：大家都知道X=History，则 Y 必然是 NO， H（Y ) = 0 ， Histroy的可能性是1/4 ，需要的传输量是 0（CS同理）

大家都知道X=Math，则 Y 可能是 Yes或者No，H（Y ) = 1 ，Math的可能性是1/2 ，需要的平均传输率是 1/21 = 0.5

Math的概率 P（Math） = 1/2 ； History的概率 P（Histroy）= 1/4； History的概率 P（CS）= 1/4；

则我们定义H（Y | X ) = H（Y | X = Math)P（Math） H（Y| X = Histroy)P（Histroy） H（Y| X = CS)P（CS） = 0.5

Information Gain 信息增益和 Relative Information Gain

从上文可知，比起直接传输Y，条件熵则更加划算了。这些划算的部分，我们称为信息增益IG。

IG(Y|X) = H(Y) - H(Y | X)

上面的例子，IG(Y|X) = H(Y) - H(Y | X) = 1 - 0.5 = 0.5

RIG= IG(Y|X) / H(Y) = 0.5 / 1 = 0.5 (节省的部分占了50%)