基于IDWPSO-K-means聚類的網約車需求量時變特征分析

付文華，白 竹，張 蕾，王世鐸

（沈陽建筑大學 交通與測繪工程學院，遼寧 沈陽 110168）

0 引言

近年來，網約車行業發展較快，相比于傳統出租車，網約車服務更方便、快捷，但同樣存在供需不均衡問題。對網約車需求聚類可以觸發供給方的前瞻性調度行為，選擇恰當的聚類算法提取和深入挖掘網約車訂單數據的特征，將隱藏的時間需求分布交互性特征顯性表達出來，有助于平衡供需關系，合理調度區域運力資源，更好地為乘客服務。

針對網約車需求，國內外學者多從數據挖掘角度研究其特征。張政等以網約車數據集為依據，提出了基于主題模型的出行需求識別方法，可較好地識別不同時間窗口下區域出行需求特征[1]。龍雪琴等以成都市網約車訂單為基礎，分析了工作日與非工作日網約車上下客的空間分布，證實網約車上下客熱點具有明顯的區域分布特性，且下客熱點更為集中[2]。周夢杰等基于訂單數據將居民出行的時間序列分解為空間模態和時間系數兩部分，以挖掘乘客的出行特征[3]。Tang 等基于GPS 軌跡數據對出租車OD 點進行聚類分析，可有效識別出行熱點區域[4]。He 通過網約車運營數據識別網約車的時空變化特征，證實網約車需求在不同時段內具有較強的規律性[5]。況東鈺基于網約車數據對網約車需求進行時序分析，并識別了不同日期屬性下需求量的變化規律[6]。

針對網約車時空聚類算法，現有研究多集中于聚類算法改進上。黎新華等提出一種將改進動態時間彎曲距離作為凝聚層次聚類相似性度量的聚類方法，相對于歐氏距離凝聚層次聚類而言，該算法能更好地識別網約車的時間需求變化特征[7]。林基艷等采用基于密度的聚類算法（Density-Based Spatial Clustering of Applications with Noise,DBSCAN）挖掘車輛行駛軌跡數據[8]，但該算法的參數選擇對軌跡影響較大。基于此，孫立山等引入K-距離曲線對該算法進行改進并挖掘載客熱點，提高了聚類精度[9]。Chen 等以網約車訂單的初始經緯度作為特征值進行K-均值聚類，并以此進行區域劃分[10]。崔宇超等采用K-均值（K-means）聚類方法對兩類網約車訂單數據進行聚類分析，發現兩類乘客的出行需求呈相似特征[11]。但K-means 的聚類中心是隨機選擇的，易選到孤立點或選擇的初始聚類中心距離較小，且K值較難確定，易導致聚類結果不穩定。Jian 等針對K-means 算法的缺陷進行改進，發現改進算法在出租車熱需求方面具有更好的聚類效果[12]。除上述網約車聚類領域外，K-means 算法亦廣泛應用在公交客流預測[13]、交通流時間序列預測[14]等其他交通預測領域中。

綜上，現有網約車數據挖掘研究多集中在空間聚類領域，對網約車需求進行時間聚類分析的文獻較少，且以往研究僅對一種數據模式的網約車需求變化特征進行分析，并未對不同數據模式的需求量變化規律的相似性和差異性進行挖掘。在聚類方法領域，研究重點主要集中在算法改進上，其中K-means 算法因其良好的聚類性能已被廣泛應用，但該算法的聚類中心是隨機選取的，且K值較難確定，易導致聚類結果不穩定。因此，本文將通過改進粒子群算法優化K-means 的初始聚類中心，并從時段特征和日特征兩個角度對網約車需求數據進行聚類分析，以挖掘不同數據模式下網約車需求的變化規律，為網約車運營調度提供參考依據。

1 網約車需求分布特征

獲取蓋亞數據開放計劃[15]中海口市2017 年5月22 日—6 月4 日共兩周的網約車訂單數據，分析網約車需求在一周內的分布特征，如圖1所示。選取2017 年5 月22 日—5 月28 日一周的網約車數據，并將24h以10min為間隔，均勻劃分為144個時間序列，分析工作日和非工作日的網約車需求分布特征，如圖2 所示。由于多數樣本的需求變化特征具有高度相似性，因此隨機選取兩周的樣本數據，以分析網約車需求整體分布特征。

圖2 網約車需求時段分布

由圖1 可看出，網約車需求與星期屬性有較大關系。網約車需求在一周的變化趨勢為：周一至周三（5月22日—5月24日、5月29日—5月31日）網約車需求量較平穩，變化不明顯；周四至周六（5 月25 日—5 月27 日、6 月1 日—6 月3 日）需求開始增加；周日開始下降。在一周中，非工作日的網約車需求顯著高于工作日；在工作日中，周二（5 月23 日、5 月30 日）需求量較低，周四和周五（5 月25 日—5 月26 日和6 月1 日—6月2日）的需求量較高。在非工作日中，周六（5月27日、6月3日）的需求量略高于周日（5月28日、6月4日）的需求量。

由圖2 可看出，工作日與非工作日的網約車需求時間分布存在較大差異，其中，工作日的時間序列分布具有較高相似性，且網約車需求變化幅度較大。工作日網約車需求一天內有4 個峰值，分別出現在早高峰時段8：20—8：30、午高峰時段11：50—12：00 和14：20—14：30、晚高峰時段17：20—18：00；非工作日網約車需求一天內有2 個峰值：一個較小的峰值和一個較大的峰值，這2 個峰值分別出現在18: 10 左右和21：30左右。

因此，如何識別不同數據模式下網約車需求時間序列變化的相似性與差異性，對挖掘網約車時間需求特征具有重要意義。

2 IDWPSO-K-means算法

K-means 是一種無監督聚類，可根據樣本點的特征劃分數據集，使得樣本的多維分量在同組內相似，而在不同組之間相異，因此可以較好地識別不同時段和日期內網約車需求量時間序列變化的相似性和差異性。但由于K-means 聚類中心是隨機選擇的，易選到孤立點或選擇的初始聚類中心距離較小，因此本文采用粒子群優化（Particle Swarm Optimization,PSO）算法優化K-means 的初始聚類中心。考慮到傳統的PSO 算法存在早熟收斂等缺陷，不少學者對其進行了改進。其中，胡堂清等提出的動態調整慣性權重的改進粒子群算法（Hybrid Particle Swarm Optimization with Dynamic Adjustment of Inertial Weigh,IDWPSO）[16]，改進策略相對簡單、收斂速度更快，具有較好的尋優性能。因此，本文采用該算法優化K-means的初始聚類中心。

2.1 K-means算法

MacQueen 于1967 年提出了K-means 聚類算法，用于處理數據挖掘中聚類相關問題[17]，其可將含有n個樣本的集合x={x1,x2,…,xn}，劃分成k個類簇ω1,ω2,…,ωk。算法的聚類步驟如下：

（1）確定需要生成的簇數k：從樣本中抽取k個樣本點作為k個原始聚類簇中心c1,c2,…,ck，即將x={x1,x2,…,xn}劃分為k個類簇：ω1,ω2,…,ωk，其中

（2）計算非簇中心點xi與簇中心ci間的歐氏距離d[18]；

（3）根據歐氏距離矩陣，分配非初始簇中心樣本點至距離最近的簇中心樣本點所在的類；

（4）根據式（2）計算各類簇內樣本的均值，并將該值作為新聚類中心[18]；

式（2）中：mi是簇i的中心；Ci是簇i的樣本數目。

（5）重復步驟（2）～步驟（4），直至各類簇的樣本點不再變化，迭代結束。此時輸出的結果即為K-means聚類的最終結果。

2.2 IDWPSO算法

IDWPSO 主要在慣性權重和更新粒子位置兩方面進行改進，具體如下。

（1）改進慣性權重

慣性權重ω通過指數函數控制，當迭代次數增加時，非線性減小，利用Matlab 中的betarnd 函數生成符合貝塔分布的隨機數，以增強算法后期的全局搜索能力，其表達式為[16]：

式（3）中：t為當前迭代次數；tmax是最大迭代次數；ωmax,ωmin分別為慣性權重的初值和終值；σ為慣性調整因子，取0.1；B(p,q)為貝塔函數。等號右側第1 項與第2 項通過指數函數改變，算法前期慣性權重較大，隨著迭代次數增加非線性遞減。第3 項利用貝塔分布對ω的整體取值分布進行調整。

（2）粒子位置更新

引入差分進化操作更新粒子位置，以避免迭代后期種群多樣性下降。其具體步驟為：初始化、變異、交叉和選擇，通過變異與交叉操作更新粒子位置。位置更新計算式[16]為：

該算法的具體步驟如下：

①初始化種群參數；

②計算各粒子的適應度值；

③比較粒子個體適應度與群體最優值，選擇更優者作為群體最優值；

④按式（3）計算慣性權重ω，并更新粒子速度；

⑤若rand ＜CR，采用交叉算子更新粒子位置，否則用PSO算法進行更新；

⑥當達到終止條件時，輸出最優解，否則轉至步驟②。

2.3 IDWPSO-K-means算法

據此，本文通過IDWPSO 算法優化K-means初始聚類中心的步驟如下。

（1）種群初始化，主要包含以下初始設置。

①設定粒子位置的最小值向量Zmin和最大值向量Zmax（其中Zmin和Zmax是依據所有樣本點的各維分量的最小值和最大值所構成的向量而定），并設定粒子速度最大值Vmax。

②將數據集x中的n個樣本點在k個簇中隨機分配，按K-means 算法，根據式（2）計算k簇內的樣本均值，將這k個均值作為聚類中心并以此構成一個粒子，不斷重復該過程，直至生成m個粒子。設這m個粒子為，其中為粒子i的位置，是第i個粒子的第j個聚類中心（i=1,2,…,m;j=1,2,…,k）。

③原始m個粒子的適應度函數fitness[19]為：

式（5）中：fitness(Xi)為第i個粒子的適應度函數，其值越小，聚類質量越好。

④將粒子i的最優適應度Pbestfitness(i)的初值設為fitness(Xi(0))，最優位置Pxbesti的初值設為，i=1,2,…,m。

⑤將所有粒子中Pbestfitness(i)的最小者賦值在全局最優適應度Gbestfitness(i)上，將下標記為I，此時該粒子的對應位置PxbestI為全局最優位置Gxbest。

（2）生成下一代粒子群，根據式（6）～式（7）更新粒子i(i=1,2,…,m)的速度與位置，速度值在[-Vmax,Vmax]內，當rand ＜CR時，粒子位置更新算法采用式（4）中的交叉算子法，否則采用式（7）標準粒子群進行位置更新。

式（6）～式（7）中：ω為改進慣性權重，其計算方法如式（3）所示，可以權衡局部和全局最優能力；r1和r2為獨立的隨機變量，取值在(0,1)區間；c1和c2為加速系數，用來控制迭代步長，一般取值2.0[20]。

（5）找到所有粒子中最優適應度Pbestfitness(i)最小的值，作為全局最優適應度Gbestfitness(i)的值，并將該粒子的最優位置賦為全局最優位置Gxbest。

（6）若全局最優位置Gxbest在多次迭代后仍未變化，則退出迭代，轉到（9）；否則繼續運算。

（7）按式（8）降低慣性權重ω值[20]，式中參數含義同前。

（8）重復步驟（2）～步驟（7），直至迭代終止，轉到步驟（9）。

（9）將粒子群全局最優位置Gxbest作為Kmeans 的聚類中心進行聚類，即重復執行以下幾個步驟。

①將數據集x中樣本點分配到離k個聚類中心Gxbest1,Gxbest2,…,Gxbestk最近的簇。

②重新計算k個簇中心。

③重復以上兩步，直到k個簇中心無變化，或樣本點未被重新分配，則迭代結束，轉到步驟（10）。

（10）輸出k個聚類中心，以及x的劃分。

由于K-means 算法的難點在于事先確定類數k，因此本文預先設置多個k值，選取戴維森堡丁指數（Davies Bouldin Index,DBI）和標準偏差指數（Standard Deviation Based Index,STDI）[21]檢驗各k值下的聚類有效性，計算公式見式（9）和式（10），從而確定本文算法的聚類數目。

式（9）中：Sp和Sq為第p類和第q類內的元素與質心的標準差；Dpq為第p類和第q類質心間的歐氏距離；其他參數含義同前。式中括號內分子越小則類內元素相似度越大，分母越大則各聚類間相似度越小。因此，DBI值越小，聚類結果越有效。

式（10）中：cp是類p的質心；是所有樣本的質心；xμ是類p的第μ個樣本；np是類p的樣本數，k為類簇數。式中的分子表示各類之間的方差，分子越大，則各聚類間相似度越小；分母表示各類內的方差之和，分母越小，則類內元素相似度越大。因此，STDI值越大，聚類結果越有效。

3 實例分析

本文選取蓋亞數據開放計劃中海口市2017年5 月22 日（周一）至7 月21 日（周五）兩個月的網約車訂單數據進行分析，由于網約車需求變化特征不僅與一日內的時段有關，也與星期的變化有關，因此本文分別從時段和星期兩個不同角度對網約車訂單數據進行聚類分析，借助Matlab R2019a，基于IDWPSO-K-means 算法聚類分析網約車需求總量的時段特征和日特征。

3.1 基于時段特征的網約車需求聚類分析

本文將單個調查日按10min間隔共劃分為144個時間序列，調查日總計61d，因此本文聚類算法的數據處理對象共144（個/d）×61（d）=8784（個）。當聚類數目為2～10時，其DBI和STDI見表1。

表1 基于時段特征的IDWPSO-K-means聚類檢驗系數

由表1 可看出，當聚類數目為2 時，DBI=0.4167,STDI=3.1291，同時達到最優，因此基于時段特征合適的聚類數目為2，聚類結果如表2所示。

表2 基于時段特征的IDWPSO-K-means聚類結果

由表2可看出，IDWPSO-K-means算法將144個時段的需求量分為2 類，0：00—7：20 和23：20—23：50 均處于網約車需求較低的時段，7：30—23：10 網約車需求較高，與日常經驗相似，分類較為合理。

3.2 基于日特征的網約車需求聚類分析

基于日特征聚類的數據模式與基于時段特征聚類相反，是對144 個時段中每個時段61d 的需求量進行聚類，觀察同一時段每天需求量的變化情況。此處采用9：00—9：10的時段數據進行日特征聚類，聚類數目同樣取2～10時，DBI和STDI如表3所示。

表3 基于日特征的IDWPSO-K-means聚類檢驗系數

由表3 可看出，當聚類數目為4 時，DBI 和STDI同時達到最優，因此基于日特征合適的聚類數目為4。當k=4時，聚類結果如表4所示。

表4 基于日特征的IDWPSO-K-means聚類結果

由表4 可知，IDWPSO-K-means 算法能較好地區分需求量不同的日期，同一時段中大部分周一至周三的需求量聚為穩定的一類、周五至周六大致聚為穩定的一類，與日常經驗較為相似，工作日的出行需求略低于非工作日的出行需求，分類較為合理。個類別中將工作日和非工作日分為一類的原因是，個別工作日的網約車需求過高，與非工作日需求接近；或非工作日的需求量較低，與工作日的需求量接近，被看作異常的工作日或非工作日。

3.3 對比分析

為驗證本文算法聚類效果的有效性，選用聚類誤差平方和和迭代次數作為聚類評價指標，并與K-means 算法和PSO-K-means 算法進行對比。誤差平方和s的計算公式[18]為

式（11）中：xi為樣本點；ci為聚類中心；ωi為第i個樣本集合；k為類簇數。

3.3.1 基于時段特征聚類的對比分析

根據式（11）計算當聚類數目為2～10時，基于時段特征聚類的3 種算法的誤差平方和，結果如表5所示，迭代次數如表6所示。

表5 基于時段特征聚類的3種算法的誤差平方和

表6 基于時段特征聚類的3種算法的迭代次數

由表5 可看出，PSO-K-means 算法和IDWPSO-K-means 算法聚類結果的誤差平方和在任意聚類數目下，均小于K-means 算法。當k=2 時，IDWPSO-K-means 算法和PSO-K-means 算法得到了相同的聚類中心和聚類數目，因此，誤差平方和相等。僅當k=3 時，IDWPSO-K-means 誤差平方和略大于PSO-K-means 算法。當k=4～10 時，IDWPSO-K-means 算法的誤差平方和小于PSOK-means算法。

由表6 可看出，IDWPSO-K-means 算法和PSO-K-means 算法在聚類數目為8 時，迭代次數略高于K-means 算法；在聚類數目為6 時，IDWPSO-K-means 算法迭代次數略高于PSO-K-means算法，但低于K-means 算法；當聚類數目為2～5、7、9～10 時，IDWPSO-K-means 算法均有最小的迭代次數。

3.3.2 基于日特征聚類的對比分析

比較基于日特征聚類的3 種算法聚類結果的誤差平方和及迭代次數，如表7和表8所示。

表7 基于日特征聚類的3種算法的誤差平方和

表8 基于日特征聚類的3種算法的迭代次數

由表7 可看出，PSO-K-means 算法和IDWPSO-K-means 算法的誤差平方和均小于K-means算法。當k=8～10時，IDWPSO-K-means 算法的誤差平方和略大于PSO-K-means 算法；當k=2～7時，IDWPSO-K-means 算法誤差平方和小于PSO-K-means算法。

由表8 可看出，IDWPSO-K-means 算法按日特征聚類時，當聚類數目為9 時，其迭代次數略高于PSO-K-means 算法，但當聚類數目為2～8 和10 時，IDWPSO-K-means 算法的迭代次數低于或等于PSO-K-means算法。

由此可看出，無論是基于時段特征還是日特征對網約車需求進行聚類，本文提出的IDWPSOK-means 算法的聚類效果均最優，驗證了本文算法的有效性。

3.4 基于聚類結果的對策建議

基于時段特征考慮，IDWPSO-K-means 算法將144 個時間序列聚為2 類，較好地識別出了不同時段內網約車需求的規律性；聚類結果較好區分了網約車需求量的時間變化階段，網約車運營商可基于此優化資源配置，實現運力的合理調度。當網約車需求量處于高峰時段時，運營商需增加車輛供給，以滿足乘客的出行需求；當處于需求量低峰階段時，運營商可適當降低車輛供給，以壓縮成本支出，避免運力浪費，實現供需均衡。

基于日特征考慮，IDWPSO-K-means 算法將不同日期的需求量聚為4 類，其中，同一時段內大部分周一至周三被聚為穩定的一類（標簽1），周五至周六被聚為穩定的一類（標簽3），周日被聚為一類（標簽4）。相同類別的網約車需求變化趨勢具有較高相似性，網約車運行商可依據不同類別下的交通需求，合理規劃網約車運營調度方案，實現合理的資源配置。針對個別星期屬性在多類標簽出現的情況，將其歸為異常類別，如周四均勻出現在標簽1與標簽2中、周五出現在多類標簽中等，運營商需探查網約車需求量在該日突變的主要原因，確定是由于調度決策失誤、供需不均衡等內在因素造成，還是由于天氣、大型活動等外在因素導致，以提升對異常需求量的處理水平。

4 結語

本文首先對網約車訂單數據進行了預處理，分析了網約車需求量的時段和日分布特征。然后針對K-means 算法的不足，提出了一種動態調整慣性權重的粒子群優化（IDWPSO-K-means）聚類算法來優化K-means 的初始聚類中心。最后基于該算法考慮兩種不同的數據模式（時段特征和日特征）對海口市的網約車需求數據進行聚類分析。結果表明，基于時段特征的網約車需求量聚為2 類，基于日特征的網約車需求量聚為4 類，相同類別的網約車需求變化趨勢具有較高的相似性。與K-means 算法和PSO-K-means 算法相比，IDWPSO-K-means 算法的誤差平方和和迭代次數2 個指標的值均更優，能更好地識別出需求量時變特征，為網約車實時調度和規劃提供依據。但本文僅針對網約車時間序列進行了聚類研究，尚未對城市傳統出租車需求展開研究，未來可綜合挖掘不同時段和日期內網約車與傳統出租車的需求變化規律，有助于更好地提升城市運輸服務水平。