擬合 概論 Gap的預測，是建立在一個擬合函數上的。也有一些機器學習的味道。 總的Gap函數 = 函數(時間,地區) TimeID ： 時間片編號 DistricID：地區編號 Traffic：交通流量 Weather：天氣 POI：設施數 "百度地圖POI說明" 註意：每家公司的POI分類都是不同 ...
擬合
概論
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的路是變化的關鍵。
由於數據量非常龐大，所以這裡建議將中間的計算結果也放入資料庫中備用。
博客園不支持圖片放大功能，如果您想更好的查看圖片，也可以使用以下網址獲得更好的閱讀體驗:
http://codesnippet.info/Article/Index?ArticleId=00000041
我們嘗試使用最小二分法擬合 LV4和 訂單總量
從圖中可以看到，大部分的點在一個 Y = AX+ B 的直線函數中。
（未去噪點）
A:4.67355309006603
B:18.931303546517
(去除1500以上的噪點)
A:1.08888907683687
B:192.700547917395
（這裡使用的是2016-01-01 #51 的數據）
#region 最小二乘法擬合
///<summary>
///用最小二乘法擬合二元多次曲線
///例如y=ax+b
///其中MultiLine將返回a，b兩個參數。
///a對應MultiLine[1]
///b對應MultiLine[0]
///</summary>
///<param name="arrX">已知點的x坐標集合</param>
///<param name="arrY">已知點的y坐標集合</param>
///<param name="length">已知點的個數</param>
///<param name="dimension">方程的最高次數</param>
public static double[] MultiLine(double[] arrX, double[] arrY, int length, int dimension)//二元多次線性方程擬合曲線
{
int n = dimension + 1; //dimension次方程需要求 dimension+1個 繫數
double[,] Guass = new double[n, n + 1]; //高斯矩陣 例如：y=a0+a1*x+a2*x*x
for (int i = 0; i < n; i++)
{
int j;
for (j = 0; j < n; j++)
{
Guass[i, j] = SumArr(arrX, j + i, length);
}
Guass[i, j] = SumArr(arrX, i, arrY, 1, length);
}
return ComputGauss(Guass, n);
}
private static double SumArr(double[] arr, int n, int length) //求數組的元素的n次方的和
{
double s = 0;
for (int i = 0; i < length; i++)
{
if (arr[i] != 0 || n != 0)
s = s + Math.Pow(arr[i], n);
else
s = s + 1;
}
return s;
}
private static double SumArr(double[] arr1, int n1, double[] arr2, int n2, int length)
{
double s = 0;
for (int i = 0; i < length; i++)
{
if ((arr1[i] != 0 || n1 != 0) && (arr2[i] != 0 || n2 != 0))
s = s + Math.Pow(arr1[i], n1) * Math.Pow(arr2[i], n2);
else
s = s + 1;
}
return s;
}
private static double[] ComputGauss(double[,] Guass, int n)
{
int i, j;
int k, m;
double temp;
double max;
double s;
double[] x = new double[n];
for (i = 0; i < n; i++) x[i] = 0.0;//初始化
for (j = 0; j < n; j++)
{
max = 0;
k = j;
for (i = j; i < n; i++)
{
if (Math.Abs(Guass[i, j]) > max)
{
max = Guass[i, j];
k = i;
}
}
if (k != j)
{
for (m = j; m < n + 1; m++)
{
temp = Guass[j, m];
Guass[j, m] = Guass[k, m];
Guass[k, m] = temp;
}
}
if (0 == max)
{
// "此線性方程為奇異線性方程"
return x;
}
for (i = j + 1; i < n; i++)
{
s = Guass[i, j];
for (m = j; m < n + 1; m++)
{
Guass[i, m] = Guass[i, m] - Guass[j, m] * s / (Guass[j, j]);
}
}
}
//結束for (j=0;j<n;j++)
for (i = n - 1; i >= 0; i--)
{
s = 0;
for (j = i + 1; j < n; j++)
{
s = s + Guass[i, j] * x[j];
}
x[i] = (Guass[i, n] - s) / Guass[i, i];
}
return x;
}//返回值是函數的繫數
#endregion任務
- 研究同一時間片，同一地區，按照日期變化，數據的變化。觀察天氣對數據變化的影響
- 研究同一時間片，不同地區，POI的數量對數據變化的影響
- 研究每個區域的需求量，可能每個區域的需求量基準數值都是差不多的。
