解析滴滴算法大赛---GBDT进行数据预测

按照前面文章的方法进行数据预测，完全不使用POI，天气，交通情况的数据，可以达到0.43的成绩。 不过如果想要获得更好的成绩，简单的预测方法显然无法满足要求了。

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/2 1 = 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%)

信息增益是什么，我们先从它的用处来了解它： 信息增益是特征选择中的一个重要指标，它定义为一个特征能够为分类系统带来多少信息，带来的信息越多，该特征越重要。

离散化

回到滴滴算法的问题，我们应该挑选哪些指标作为GBDT的参考呢？ 所有的这些指标在使用之前都进行一下离散化。

关于离散化的好处：数据处理：离散化好处多

http://blog.sina.com.cn/s/blog_652090850100ynds.html

例如，在滴滴算法大赛里面，天气中的PM值，交通拥堵状况都是一些具体的数值，这里用离散化后，才能放入决策树中。

GBDT实现（C#）

    /// <summary>    /// 回归分类树节点    /// </summary>    class TreeNode    {        /// <summary>        /// 节点属性名字        /// </summary>        public string attrName { set; get; }        /// <summary>        /// 节点索引标号        /// </summary>        public int nodeIndex { set; get; }        /// <summary>        /// 包含的叶子节点数        /// </summary>        public int leafNum { set; get; }        /// <summary>        /// 节点误差率        /// </summary>        public double alpha { set; get; }        /// <summary>        /// 父亲分类属性值        /// </summary>        public string parentAttrValue { set; get; }        /// <summary>        /// 孩子节点        /// </summary>        public TreeNode[] childAttrNode { set; get; }        /// <summary>        /// 数据记录索引        /// </summary>        public List<string> dataIndex { set; get; }    }

（隐）马尔可夫模型的思考

在滴滴算法问题中，你需要预测的是第4个时间片，前3个时间片的状态是已经知道的。 如果我们知道第一个时间片和第二个时间片的GAP是呈现上升或者持平或者下降的状态变化，记作 C1，第二和第三个时间片变化记作 C2。 是不是可以通过C1 ，C2 ，拟合出 C3呢？

社会工程学

在拟合的时候，不可避免的会考虑各种天气对于订单的影响，但是官方并没有给出天气的类型和天气描述之间的关系。 通过对于数据的分析，我们可以知道采样数据是来自上海市（感谢某位做天气研究的同学） 然后通过查阅历史资料，我们也可以初步获得所有天气类型值和天气描述的关系，这个是无法用程序和算法完成的，所以我认为这也是社会工程学的一部分。

        public static string GetWeatherType(int type)        {            string des = "未知";            switch (type)            {                case 1:                    des = "雾";                    break;                case 2:                    des = "晴";                    break;                case 3:                    des = "轻雾";                    break;                case 4:                    des = "降水";                    break;                case 6:                    //2016-01-22上海雨夹雪                    des = "雪";                    break;                case 8:                    des = "雷暴";                    break;                case 9:                    des = "霾";                    break;                default:                    des = "未知";                    break;            }            return des;        }

决策树（分类）

组委会是要求测算GAP值，是个定量问题。在这之前，我们看一下是否能够限定性分析一下GAP的高低呢？

从滴滴算法大赛的数据可以知道，数据的特征值大约有这些：

• 天气相关：天气类型，PM2.5(离散化处理)，温度(离散化处理)
• 交通状态：需要将原有数据重新计算为一个新的指标，例如将拥挤度进行加权平均。
• POI数据：挑选特征明显的分类

有一些特征需要自己去发现

• 工作日/休息日
• 特殊天气（极端最低气温）
• 时间段（根据组委会的题目，可以将9个待预测时间片，变化为9个时间段）

整理出来的表格大概像这个样子的（不完全，示例）

这个时候，我们到底先用哪个条件作为优先决策的依据呢？答案就是上文提到的信息增益。

Information Gain 信息增益 和 Relative Information Gain

• IG（GAP分类 | 天气类型） = H（GAP分类） - H（GAP分类 | 天气类型）
• IG（GAP分类 | 交通状态） = H（GAP分类） - H（GAP分类 | 交通状态）
• IG（GAP分类 | 工作日） = H（GAP分类） - H（GAP分类 | 工作日）

哪个数字最大就挑选哪个作为第一优先分类条件。 现在我们假设工作日是最高信息增益的，作为第一个决策条件 第一次分组之后就是这个样子了：

按照理论（大神的文章，以后会翻译的），工作日组的GAP分类都一致了，所以就无需决策了。 对于节假日组，根据交通状态进行再分类

交通状态再分类结果如下

这里无需天气类型就可以完成分类决策了。 （当然还有一种情况是所有特征都用完了，还是不能完全分类，这个时候可以使用多数表决的方式决定分类）

决策树（定量）

上面是一个定性的过程，下面我们来看一下，如果需要定量怎么处理呢？

• 根节点的输入是所有的值，输出是所有目标值得均值。 （输入和输出之间的差就是误差，这里往往不是计算简单的差，而是方差） 这里的平均值就是（ 893 + 375 + 542 + 437 + 753 ） / 5 = 600

第一次分类怎么处理呢？ 分裂的时候选取使得误差下降最多的分裂 如果我们选择工作日作为分裂条件

工作日的均值是：（893 + 753 ）/ 2 = 823

误差的方差是： 70 × 70 + 70 × 70 = 9800

节假日的均值是：（375 + 542 + 437 ）/ 3 = 451

误差的方差是： 76 × 76 + 91 × 91 + 14 × 14 = 14253

按照是否为工作日分裂之后的总误差是 9800 + 14253 = 24053

当然标准做法是计算所有的总误差，然后选取最小的总误差的特征作为分类特征 （如果在这里结束，则认为工作日的预测是823，节假日的预测是541当然这还没有完）

第一颗树： 工作日：+823 休息日：+451

第二颗树： 如果按照拥挤分类呢？ 注意这里我们使用的输入值是误差！！

首先计算均值：

• 轻度拥挤 ： -76
• 重度拥挤 ： -70
• 拥挤 ： +49

(这些数字的意思是，如果你认为工作日的预测是823，节假日的预测是541，两者都需要根据拥挤程度根据上述值进行修正)

第三颗树：

晴天：+ 31 雪：- 63

在交通状态为拥堵的时候，如果是晴天，修正 31，雪：修正 -63

预测一下

工作日 +823 拥挤：+49 拥挤 且 雪天：-63 预测：809

C#代码

回归分类树节点

    /// <summary>    /// 回归分类树节点    /// </summary>    class TreeNode    {        /// <summary>        /// 节点属性名字        /// </summary>        public string attrName { set; get; }        /// <summary>        /// 节点索引标号        /// </summary>        public int nodeIndex { set; get; }        /// <summary>        /// 包含的叶子节点数        /// </summary>        public int leafNum { set; get; }        /// <summary>        /// 节点误差率        /// </summary>        public double alpha { set; get; }        /// <summary>        /// 父亲分类属性值        /// </summary>        public string parentAttrValue { set; get; }        /// <summary>        /// 孩子节点        /// </summary>        public TreeNode[] childAttrNode { set; get; }        /// <summary>        /// 数据记录索引        /// </summary>        public List<string> dataIndex { set; get; }    }