解析滴滴算法大赛---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个时间段)

整理出来的表格大概像这个样子的(不完全,示例)

天气类型

交通状态

工作日

GAP分类

拥挤

雷暴

轻度拥挤

拥挤

拥挤

重度拥挤

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

Information Gain 信息增益 和 Relative Information Gain

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

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

天气类型

交通状态

工作日

GAP分类

拥挤

重度拥挤

天气类型

交通状态

工作日

GAP分类

雷暴

轻度拥挤

节假日

拥挤

拥挤

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

天气类型

交通状态

工作日

GAP分类

雷暴

轻度拥挤

拥挤

拥挤

交通状态再分类结果如下

天气类型

交通状态

工作日

GAP分类

拥挤

拥挤

天气类型

交通状态

工作日

GAP分类

雷暴

轻度拥挤

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

决策树(定量)

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

天气类型

交通状态

工作日

GAP数

拥挤

893

雷暴

轻度拥挤

375

拥挤

542

拥挤

437

重度拥挤

753

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

天气类型

交通状态

工作日

GAP数

误差

拥挤

893

293

雷暴

轻度拥挤

375

225

拥挤

542

58

拥挤

437

167

重度拥挤

753

153

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

工作日的均值是:(893 + 753 )/ 2 = 823

天气类型

交通状态

工作日

GAP数

误差

拥挤

893

+70

重度拥挤

753

-70

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

节假日的均值是:(375 + 542 + 437 )/ 3 = 451

天气类型

交通状态

工作日

GAP数

误差

雷暴

轻度拥挤

375

-76

拥挤

542

+91

拥挤

437

-14

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

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

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

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

天气类型

交通状态

工作日

GAP数

误差

拥挤

893

+70

重度拥挤

753

-70

雷暴

轻度拥挤

375

-76

拥挤

542

+91

拥挤

437

-14

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

天气类型

交通状态

工作日误差

拥挤

+70

拥挤

+91

拥挤

-14

雷暴

轻度拥挤

-76

重度拥挤

-70

首先计算均值:

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

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

天气类型

交通状态

工作日误差

交通状态误差

拥挤

+70

+21

拥挤

+91

+ 42

拥挤

-14

- 63

雷暴

轻度拥挤

-76

0

重度拥挤

-70

0

第三颗树:

天气类型

交通状态:拥挤

+21

+ 42

- 63

晴天:+ 31 雪:- 63

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

预测一下

天气类型

交通状态

工作日

GAP数

拥挤

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

天气类型

交通状态

工作日

GAP数

拥挤

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; }    }

原文发布于微信公众号 - 大数据挖掘DT数据分析(datadw)

原文发表时间:2017-02-19

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏CVer

[计算机视觉] 入门学习资料

本文将介绍计算机视觉相关的经典书籍,顶级期刊/会议,在线学习课程,常用开源库和安利小工具等。 简介 计算机视觉(Computer Vision) 计算机视觉是...

1.2K18
来自专栏人工智能头条

干货 | “后 Word Embedding 的”热点会在哪里?

2392
来自专栏机器人网

无人机用陀螺仪的数据处理

1 陀螺仪数据校准 1.1 原理 一款飞控上的传感器是需要进行校准的,比如这里讲的陀螺仪。目前大多数的陀螺校准其实就是去掉零点偏移量,采集一定的数据,求平均,...

6716
来自专栏AI科技大本营的专栏

AI 技术讲座精选:数学不好,也可以学习人工智能(四)——图解张量

【AI100 导读】本文是《数学不好,也可以学习人工智能》系列的第四篇文章,主要内容围绕 Tensors(张量)展开。 ? 现在的你是否已经下载好 Tensor...

4846
来自专栏C/C++基础

动态规划与数学方程法解决楼层扔鸡蛋问题

两个软硬程度一样的鸡蛋,它们有可能都在一楼就摔碎,也可能从一百层楼摔下来没事。有座100层的建筑,用这两个鸡蛋确定哪一层是鸡蛋可以安全落下的最高位置,可以摔碎两...

1183
来自专栏大数据文摘

拓扑学——探寻大数据的内在模式

2175
来自专栏ATYUN订阅号

IBM与哈佛合作开发工具解决AI翻译中的黑箱问题

近年来,由于深度学习和神经网络的进步,机器翻译得到了极大的进步。然而,神经网络的问题在于人们不知道它们内部发生了什么,这意味着很难解决它们的错误。

801
来自专栏机器之心

机器之心「GMIS 2017」嘉宾揭秘:LSTM之父Jürgen Schmidhuber

2017 全球机器智能峰会(GMIS 2017),让我们近距离接触「LSTM 之父」Jürgen Schmidhuber。 2017 全球机器智能峰会(GMIS...

3118
来自专栏CDA数据分析师

测试:你是否具备企业的数据挖掘能力?

1.某超市研究销售纪录数据后发现,买啤酒的人很大概率也会购买尿布,这种属于数据挖掘的哪类问题? A. 关联规则发现 B. 聚类 C. 分类 D. 自然语言处理 ...

2376
来自专栏大数据挖掘DT机器学习

一个贯穿图像处理与数据挖掘的永恒问题

作者: 左飞 著有《算法之美——隐匿在数据结构背后的原理(C++版)》 原文 http://blog.csdn.net/baimafujinji/articl...

2443

扫码关注云+社区

领取腾讯云代金券