解析滴滴算法大赛---拟合算法
解析滴滴算法大赛---拟合算法
滴滴算法大赛到底需要什么样子的答案？ 我一开始的想法是建立一个模型，通过天气，POI，交通拥堵的参数来推导出订单数和GAP数。
但是通过现有的数据发现，这个模型很难建立。
其实看一下题目，这是一个预测题：
给定每个区域在时间片tj,tj-1…的各项数据，预测gapi,j+1, ∀di∈D。
测试数据是根据前半个小时的数据，获得后半个小时的GAP数 如果不是想研究机器学习的话，其实也没有必要（或者没有可能）建立一个完整的模型。 我们只需要知道，数据的发展趋势，例如这个时间点是 N ，按照经验，后一个时间点的趋势是上升还是下降，幅度大约多少即可。
订单
哪些因素左右订单
前几天一直在寻找那些因素制约着订单数。
9点整和18点整 全区域订单分析图 订单的总量在不同日期，表现出极大的不同。但是，接单量和司机数有关系，司机数则是比较稳定的，9点的司机数大约是5000人，18点为4500人。（前三个数据是 01-01 到 01-03 节假日 ，01-09 ，01-10，01-16，01-17 分别是节假日，所以早晨的需求比较少 ）
通过分析，我们应该可以整理出一张司机数和时间段的对应函数。（节假日和非节假日区分开来）
如果我们按照节假日和非节假日去看分时接单量
- 节假日的早高峰和平日的早高峰项目，相差巨大。
- 节假日和非节假日，其他时段接单量，基本持平。
- 每天的8：30分，17：30分 是两个最高值。
- 根据这个统计数据，我们大概知道了每天的接单情况。可以预测未来的某个时间片的接单量。当然，如果我们能够计算出Gap比率（GAP数/总订单数[GAP+接单数]），Gap数也是可以预测出来的。很遗憾，Gap比率的数据统计如下：（每天订单量起伏比较大，接单数较为固定，GAP比率则变化很大） 日期别9：00和18：00GAP比率
预测订单趋势
上面说了，日期别的订单差异量很大，但是我们是否可以考察一下，每个时段的订单变化率是否有规律可循呢？
例如在 100个时间片上订单时 N，则101个时间片上，根据统计一般会增加 1.5%的话，则可以预测101个时间片上的订单时 1.05 * N; 当然如果就这么计算的话，可能会接近于正确答案，但是完全没有使用POI，天气，交通等数据，基本上是不可能获奖的。。。
不过，我们可以先来试试看，是不是可以找到规律呢。从图表上看，我们应该可以统计出，每个时间点上数据的变化率。
周三的变化：
从第一个周三到第二个周三的变化
从第一个周三到第二个周三的变化率 订单变化率：（这个时间片 - 上个时间片）/ 上个时间片
这样的话，我们大概可以对于各个时间片之间订单的变化率做一个统计平均表。 假设时间片 N 的订单数位 Order ，下一个时间片N+1的订单数为 NextOrder，则 变化率 K = （NextOrder - Order） / Order。 我们可以计算出全区域的每个时间片的变化率，也可以算出单个区域的每个时间片的变化率。
每个区域的订单比例
有些区域订单多，有些区域订单少，这个比例是否会随着时间变化而变化呢？ 放心，基本上每个区域的订单比率很固定的。
如何解决问题
题目里面告诉了我们所需测试Gap的时间片的前三个时间片的数据。结合变化率的概念，其实我们可以计算出待预测的时间片的订单量。 还有一个问题是接单量怎么考虑，我的想法是将这三个已知时间片的接单量的平均值作为新的接单量。
（有一种情况，例如一个时间片里 有50个订单，但是有1个GAP，这个时候其实不能认为接单量只有49，而应该认为这个区域的基本上是公供需平衡的。1个GAP有可能是偶然因素。所以我这里认为5个GAP以下都是供需正常的。）
- 第N+1个时间片的GAP = 第N + 1个时间片的订单数 - 第N + 1个时间片的接单能力。
- 第N + 1个时间片的订单数 = 第N 个时间片的订单数 * （订单变化率+ 1）
- 第N + 1个时间片的接单能力 = 第 N ，N-1， N-2 个时间片的接单能力的平均值。
最后公式是：
- 第N+1个时间片的GAP = 第N 个时间片的订单数 * （订单变化率+ 1） - 第 N ，N-1， N-2 个时间片的接单能力的平均值
这种方法计算出来的结果可能接近于答案，也可能远离答案。但是完全没有体现出机器学习的作用，所以本人觉得肯定是有问题的。这里只是给出一种解决方案。接下来，开始思考正统的解决方案。
其实算法大赛需要预测的时间片也是很有趣的，请看以下图片 红色的是GAP走势，蓝色的是需要预测的时间片。这些时间片有一些位置比较特殊。GAP走势定性分析比较容易。（定量比较难）
拟合算法
Gap的预测，是建立在一个拟合函数上的。也有一些机器学习的味道。
总的Gap函数 = 函数(时间,地区)
- TimeID ： 时间片编号
- DistricID：地区编号
- Traffic：交通流量
- Weather：天气
- POI：设施数
http://lbsyun.baidu.com/index.php?title=lbscloud/poitags
注意：每家公司的POI分类都是不同的，这里只是将百度POI做个例子，滴滴打车的POI和百度的POI定义好像是不同的。
交通流量和时间有关，一个地方的拥堵程度和时间有关系 不同的地区，各种设施配置不同。 天气和时间有关。
Gap函数 = 函数(交通拥挤度函数(时间，地区编号)，POI函数(地区编号)，天气函数(时间))
这里可以认为，一个地方的打车人数，交通越堵，则打车的GAP越大。天气不好，打车的人则越多，GAP也越大。设施越多的地方，打车的需求也越多，GAP可能也越大。但是这一切都只是可能性。 （题外话，其实真实的情况也要考虑节假日的问题，在节假日的时候，GAP可能会变大。当然这是一个人文的考量了）
zhihu网友的算法
利益不相关，不是参赛选手，不是滴滴工作人员，纯粹觉得题目好玩。 我的分析： 这个题目的目标是预测，预测的核心是发掘信息，信息才是消除不确定性的唯一途径。信息存在于乘客与司机的几种行为模式，以及POI的不同功能类型。 乘客的行为基本上有三类模式，周期性的（每天上下班、每周去上补习班）、集中偶发性的（音乐会）和随机性的（各类杂事）。司机的行为模式包括出车、收车、找活、趴活、午休。POI类型也可以分为周期性的（工作单位）、集中偶发性（电影院、体育馆、演播大厅）、随机性的（医院、车站），当然每个POI的功能类型不是绝对的。 GAP是用车需求和供给的差，那么分别为需求和供给建立模型。 简单说，一个完整的打车需求包括出发地、目的地、时间。首先任意两个POI之间都存在一条线路，每条线路的人流量可以按照乘客的行为模式进行分解，这样也就包含了时间因素。这样最终就可以算出从每个POI出发的人数。由于数据只有方格的总数，这看起来是一个隐马尔科夫链。至于天气则基本可以看成线路人流量的一个系数。 司机接单在全天大多数时间里都是找活的状态，也就是附近有单就抢，那么某个方格某个时间片司机接单数应该是空车数量*一个系数，空车数量=上一个时间片到达的乘客数+其他司机漫无目的找活出入方格的净值+趴活司机数（找活、趴活数应该和poi类型有关，这得问问老司机拉活的窍门），系数就是抢单成功率。 非专业人士，以上只是粗浅的想了一下，还有很多细节没有考虑，抛砖引玉，达人莫笑！非专业人士，以上只是粗浅的想了一下，还有很多细节没有考虑，抛砖引玉，达人莫笑！
算法
交通拥堵
交通拥堵函数： 这里的交通拥堵函数是使用4个等级表示的。
- LV1 20条路 权重8
- LV2 10条路 权重4
- LV3 15条路 权重2
- LV4 05条路 权重1 那么拥堵指数怎么计算呢？这里应该是对每个拥堵哟一个权重，等级越高，权重越大。 拥挤度 = SUM(权重 * 数量）
在上文中 滴滴算法大赛算法解决过程 - 数据分析 提过了通过统计分析可以得知，LV1的路大约占2/3强，估计LV4，LV3的路是变化的关键。
我们尝试使用最小二分法拟合 LV4和 订单总量 从图中可以看到，大部分的点在一个 Y = AX+ B 的直线函数中。 （未去噪点） A:4.67355309006603 B:18.931303546517
(去除2倍平均值（1555.875）以上的噪点) A:1.08888907683687 B:192.700547917395
（这里使用的是2016-01-01 #51 的数据） A:5.9674717077966 B:-364.491343067091
（这里使用的是2016-01-07 #51 的数据）
我们现在看一下，其实即使是同一个区域，不同的日期，其拟合函数还是相差十分巨大的。 在TEST数据集中，其实Traffic的数据，每天只有3组，每组10个连续片段，用拟合的方法是无法预测出缺失的Traffic数据的。
那么，我们来看一下，同一区域，同一时间段，Level3 + Level4的情况如何。这样的话，整体数据相对比较稳定
.NET 代码技巧
多线程处理数据
List是线程不安全的，这里使用ConcurrentBag
多线程并行代码
