[發明專利]基于移動終端GPS定位數據計算個人通勤時間的方法

有效

• 申請號: 201810191353.2
• 申請日: 2018-03-08
• 公開（公告）號: CN108596202B
• 公開（公告）日: 2020-04-03
• 發明（設計）人: 周悅芝;藍翔;張迪
• 申請（專利權）人: 清華大學
• 主分類號: G06K9/62
• 分類號: G06K9/62;G06Q50/26;G01S19/14
• 代理公司: 北京清亦華知識產權代理事務所(普通合伙) 11201
• 代理人: 廖元秋

1.一種基于移動終端GPS定位數據計算個人通勤時間的方法，其特征在于，該方法包括以下步驟：

(1)計算通勤軌跡；

采集一時間段內的任一用戶的定位數據，并使用固定時間窗口的GPS定位數據對用戶某一時刻的定位坐標進行校準，通過聚類算法分別得到用戶家庭位置c_h和公司位置c_w，并對采集到的用戶坐標按時間進行排序，篩選出用戶在家和公司間通勤中產生的記錄點，得到用戶每日的通勤軌跡；

(2)初始化通勤軌跡聚類集合；

定義任意通勤軌跡聚類如下：<trajectory_m,trajectories>，其中trajectories是屬于這個通勤軌跡聚類的所有通勤軌跡集合:trajectories＝{T}，T表示該通勤軌跡聚類包含的用戶的所有通勤軌跡，trajectory_m是該通勤軌跡聚類中所有通勤軌跡合并之后的產生的聚合通勤軌跡：trajectory_m＝<P,D>，其中P是通勤軌跡定位數組，表示用戶所在的位置，D是相鄰兩點間的耗時數組，表示用戶在相鄰兩點移動所花費的時間；

對用戶的每一天的通勤軌跡T_i，按時間順序排列軌跡上的記錄點，每個記錄點包括：用戶標識uid、經度坐標lng、緯度坐標lat和時間戳time；取出軌跡T_i中記錄點包含的經緯度坐標放入對應的通勤軌跡定位數組P_i，并計算出該軌跡中相鄰兩點間的耗時數組D_i，用P_i和D_i作為T_i的初始的聚合通勤軌跡，得到初始化通勤軌跡聚類C_i:C_i＝<<P_i,D_i>,{T_i}>，所有的初始化通勤軌跡聚類C_i組成初始化通勤軌跡聚類集合clusters；

通勤軌跡T_i相鄰兩點耗時數組D_i計算方法如下：

D_i[j]＝T_i[j+1].time–T_i[j].time

其中D_i[j]表示相鄰兩點耗時數組D_i中第j個元素的值，T_i[j]和T_i[j+1]分別表示通勤軌跡T_i上第j和第j+1個記錄點；

(3)對clusters中所包含的通勤軌跡聚類的個數進行判定：如果clusters中所包含的通勤軌跡聚類的個數小于等于1，則聚類過程結束，轉入步驟(8)；否則，進入步驟(4)；

(4)計算clusters中任意兩個通勤軌跡聚類之間的距離，選取其中距離最小的兩個通勤軌跡聚類記為C_a和C_b，記其距離為D_ab并判定：如果D_ab大于最大距離閾值d_max，則聚類結束，轉入步驟(8)，否則進入步驟(5)；

其中，兩個通勤軌跡聚類間的距離為兩個通勤軌跡聚類所對應的聚合通勤軌跡的合并距離；令L(X)表示通勤軌跡X的長度，M表示通勤軌跡A，B合并之后的軌跡，定義兩個通勤軌跡A和B之間的合并距離D_M為：D_M(A,B)＝L(M)/max(L(A),L(B))；

(5)在空間上合并距離最小的兩個通勤軌跡聚類對應的聚合通勤軌跡；

對于從步驟(4)得到的距離最小的兩個通勤軌跡聚類C_a和C_b，取出其分別對應的聚合通勤軌跡T_a和T_b，將聚合通勤軌跡T_a和T_b定位數據的經度和緯度提取出來得到定位數組P_a和P_b；首先將用戶家庭位置c_h,定位數組P_a中的定位數據，以及公司位置c_w插入聚合后的通勤軌跡的定位數組P_m中，然后將P_b的點逐步插入到P_m中去，每次插入都選擇使軌跡長度的增量變化最小的位置，并且每次插入的位置，只會發生在上一次插入的點之后；具體步驟如下：

(5.1)用P_a，用戶家庭位置c_h以及用戶公司位置c_w初始化合并之后的通勤軌跡定位數組P_m；初始化P_m為空集合，將c_h插入P_m中，將軌跡P_a中的的所有記錄點按時間先后順序插入到P_m中，然后將用戶公司位置c_w插入P_m中；

(5.2)用pos表示上次將P_b中的記錄點插入P_m后在P_m中的位置，初始化pos為0；

(5.3)對P_b中的每一個記錄點r_b，計算其在P_m中pos之后的位置i插入所引起的P_m的總長度增量delta＝distance(P_m[i],r_b)+distance(r_b,P_m[i+1])–distance(P_m[i],P_m[i+1])，找到使delta最小的位置i_min，將r_b在i_min的位置插入P_m，并用i_min更新pos；其中distance函數用于計算兩個點之間的地理距離；

(5.4)重復步驟(5.3)直到P_b中的所有點均插入到P_m中；

(5.5)從P_m中移除用戶家庭位置c_h以及公司位置c_w，返回P_m作為合并之后的通勤軌跡的定位數組，進入步驟(6)；

(6)在時間上合并距離最小的兩個通勤軌跡聚類對應的聚合通勤軌跡；

利用步驟(4)得到的距離最小的兩個通勤軌跡聚類C_a和C_b，取出其對應的聚合通勤軌跡T_a和T_b，并分別計算T_a和T_b對應的相鄰兩點耗時數組D_a和D_b；首先基于P_a和P_b中的記錄點在P_m中的位置，依照通勤軌跡點間距離，將其對應的耗時數組D_a和D_b按距離進行加權，從而得到按距離加權分配的時間數組D_a'以及D_b'；D_a'和D_b'分別表示依照用戶在T_a和T_b中的速率，在P_m中相鄰兩點移動的時間；在求得耗時數組D_a'和D_b'之后，將D_a'和D_b'合并，得到合并之后通勤軌跡對應的相鄰兩點間的耗時數組D_m；具體步驟如下：

(6.1)初始化D_a'為大小是定位數組P_m大小-1，值為0的數組；

(6.2)對D_a中的每個時間t，找到其對應的起點r_start和終點r_end，并在P_m中找到r_start和r_end對應的位置index_start和index_end；計算P_m中index_start和index_end之間的所有相鄰定位點之間的距離總和，記為d，將在D_a中r_start和r_end間的時間依距離加權分到D_a'中，形式化為：

D_a'[i]＝distance(P_m[i],P_m[i+1])/d×t，其中i≥index_start且i<index_end；

返回D_a'作為通勤軌跡T_a按照在合并之后軌跡的定位數組P_m中點與點間的距離加權分配得到的耗時數組；

(6.3)初始化D_b'為大小是定位數組P_m大小-1，值為0的數組；

(6.4)對D_b中的每個時間t，找到其對應的起點r_start和終點r_end，并在P_m中找到r_start和r_end對應的位置index_start和index_end；計算P_m中index_start和index_end之間的所有相鄰定位點之間的距離總和，記為d，將在D_b中r_start和r_end間的時間依距離加權分到D_b'中，形式化為：

D_b'[i]＝distance(P_m[i],P_m[i+1])/d×t，其中i≥index_start且i<index_end；

返回D_b'作為通勤軌跡T_b按照在合并之后軌跡的定位數組P_m中點與點間的距離加權分配得到的耗時數組；

(6.5)遍歷D_a'和D_b'，如果D_a'和D_b'的對應位置均非0，則取兩者對應耗時的均值，否則取D_a'和D_b'中非零的值作為P_m中對應兩點間的耗時，形式化為：

返回D_m作為合并之后通勤軌跡對應的相鄰兩點間的耗時數組；

(7)合并距離最小的兩個通勤軌跡聚類；

用<P_m,D_m>作為初始化通勤軌跡聚類C_m，并將C_a和C_b里的通勤軌跡加入到C_m中，將C_m插入到clusters中，并從clusters刪除C_a以及C_b，然后重新返回步驟(3)；

(8)計算每條通勤軌跡對應的通勤時間；

對用戶每一天的通勤軌跡，找到其所在的通勤軌跡聚類，并將該通勤軌跡聚類包含的聚合通勤軌跡作為用戶當日通勤軌跡所對應的參考軌跡，具體步驟如下：

(8.1)計算每日通勤的平均速度；

從步驟(1)得到的所有通勤軌跡中任意選取某一日的通勤軌跡，令p_start表示用戶當日通勤軌跡上的第一點，該點標志著用戶離開了家，已經開始通勤；令p_end表示用戶當日通勤軌跡上的最后一點，該點表示用戶即將到達公司；令t_start和t_end分別表示p_start和p_end對應的時刻；在該通勤軌跡的參考軌跡中找到用戶p_start和p_end兩點，用p_start和p_end將參考軌跡分成三段，在p_start之前的記為trajectory_start，在p_start和p_end之間的記為trajectory_mid，在p_end之后的記為trajectory_end；計算trajectory_mid的總長度l_mid，則用戶當日的通勤的平均速度為v_avg＝l_mid/(t_end-t_start)；

(8.2)計算每日通勤開始時間和結束時間；

對于步驟(8.1)選取的通勤軌跡，令d_home,l_home分別表示用戶從家出發到通勤軌跡第一個點的耗時和長度，d_comp,l_comp分別表示用戶從通勤軌跡最后一點到公司的耗時和長度，則d_home＝l_home/v_avg，d_comp＝l_comp/v_avg；由參考軌跡的耗時數組得到trajectory_start和trajectory_end對應的時間d_start和d_end，計算用戶當日通勤開始時刻t_leave，通勤結束時刻t_arrive：

t_leave＝t_start–d_start–d_home

t_arrive＝t_end+d_end+d_comp

(8.3)計算用戶每日通勤時間d_commute；

由步驟(8.2)得到的通勤開始時間t_leave，以及通勤結束時間t_arrive，計算用戶當日通勤時間為：

d_commute＝t_arrive–t_leave。