拟合

概论

Gap的预测，是建立在一个拟合函数上的。也有一些机器学习的味道。

总的Gap函数 = 函数(时间,地区)

• TimeID ： 时间片编号
• DistricID：地区编号
• Traffic：交通流量
• Weather：天气
• POI：设施数

百度地图POI说明
注意：每家公司的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

(去除1500以上的噪点)
A:1.08888907683687
B:192.700547917395

（这里使用的是2016-01-01 #51 的数据）

1.  
   #region 最小二乘法拟合
2.  
   ///<summary>
3.  
   ///用最小二乘法拟合二元多次曲线
4.  
   ///例如y=ax+b
5.  
   ///其中MultiLine将返回a，b两个参数。
6.  
   ///a对应MultiLine[1]
7.  
   ///b对应MultiLine[0]
8.  
   ///</summary>
9.  
   ///<param name="arrX">已知点的x坐标集合</param>
10.  
    ///<param name="arrY">已知点的y坐标集合</param>
11.  
    ///<param name="length">已知点的个数</param>
12.  
    ///<param name="dimension">方程的最高次数</param>
13.  
    public static double [] MultiLine( double [] arrX, double [] arrY, int length, int dimension) //二元多次线性方程拟合曲线
14.  
    {
15.  
    int n = dimension + 1; //dimension次方程需要求 dimension+1个 系数
16.  
    double[,] Guass = new double[n, n + 1]; //高斯矩阵 例如：y=a0+a1*x+a2*x*x
17.  
    for ( int i = 0; i < n; i++)
18.  
    {
19.  
    int j;
20.  
    for (j = 0; j < n; j++)
21.  
    {
22.  
    Guass[i, j] = SumArr(arrX, j + i, length);
23.  
    }
24.  
    Guass[i, j] = SumArr(arrX, i, arrY, 1, length);
25.  
    }
26.  
    return ComputGauss(Guass, n);
27.  
    }
28.  
     
29.  
    private static double SumArr(double[] arr, int n, int length) //求数组的元素的n次方的和
30.  
    {
31.  
    double s = 0;
32.  
    for ( int i = 0; i < length; i++)
33.  
    {
34.  
    if (arr[i] != 0 || n != 0)
35.  
    s = s + Math.Pow(arr[i], n);
36.  
    else
37.  
    s = s + 1;
38.  
    }
39.  
    return s;
40.  
    }
41.  
     
42.  
    private static double SumArr(double[] arr1, int n1, double[] arr2, int n2, int length)
43.  
    {
44.  
    double s = 0;
45.  
    for ( int i = 0; i < length; i++)
46.  
    {
47.  
    if ((arr1[i] != 0 || n1 != 0) && (arr2[i] != 0 || n2 != 0))
48.  
    s = s + Math.Pow(arr1[i], n1) * Math.Pow(arr2[i], n2);
49.  
    else
50.  
    s = s + 1;
51.  
    }
52.  
    return s;
53.  
    }
54.  
     
55.  
    private static double [] ComputGauss( double [,] Guass, int n)
56.  
    {
57.  
    int i, j;
58.  
    int k, m;
59.  
    double temp;
60.  
    double max;
61.  
    double s;
62.  
    double[] x = new double[n];
63.  
     
64.  
    for (i = 0; i < n; i++) x[i] = 0.0; //初始化
65.  
    for (j = 0; j < n; j++)
66.  
    {
67.  
    max = 0;
68.  
    k = j;
69.  
    for (i = j; i < n; i++)
70.  
    {
71.  
    if (Math.Abs(Guass[i, j]) > max)
72.  
    {
73.  
    max = Guass[i, j];
74.  
    k = i;
75.  
    }
76.  
    }
77.  
    if (k != j)
78.  
    {
79.  
    for (m = j; m < n + 1; m++)
80.  
    {
81.  
    temp = Guass[j, m];
82.  
    Guass[j, m] = Guass[k, m];
83.  
    Guass[k, m] = temp;
84.  
    }
85.  
    }
86.  
    if ( 0 == max)
87.  
    {
88.  
    // "此线性方程为奇异线性方程"
89.  
    return x;
90.  
    }
91.  
    for (i = j + 1; i < n; i++)
92.  
    {
93.  
    s = Guass[i, j];
94.  
    for (m = j; m < n + 1; m++)
95.  
    {
96.  
    Guass[i, m] = Guass[i, m] - Guass[j, m] * s / (Guass[j, j]);
97.  
     
98.  
    }
99.  
    }
100.  
     }
101.  
     //结束for (j=0;j<n;j++)
102.  
      
103.  
     for (i = n - 1; i >= 0; i--)
104.  
     {
105.  
     s = 0;
106.  
     for (j = i + 1; j < n; j++)
107.  
     {
108.  
     s = s + Guass[i, j] * x[j];
109.  
     }
110.  
      
111.  
     x[i] = (Guass[i, n] - s) / Guass[i, i];
112.  
      
113.  
     }
114.  
      
115.  
     return x;
116.  
     } //返回值是函数的系数
117.  
     #endregion

任务

• 研究同一时间片，同一地区，按照日期变化，数据的变化。观察天气对数据变化的影响
• 研究同一时间片，不同地区，POI的数量对数据变化的影响
• 研究每个区域的需求量，可能每个区域的需求量基准数值都是差不多的。

文章来源: wenyusuran.blog.csdn.net，作者：文宇肃然，版权归原作者所有，如需转载，请联系作者。

原文链接：wenyusuran.blog.csdn.net/article/details/80844460