基于C-K-N-Cluster 的居民出行時空特征分析

戴兵，田博，高心雨，嚴(yán)李強

（西藏大學(xué) 信息科學(xué)技術(shù)學(xué)院，拉薩 850000）

0 引言

地理數(shù)據(jù)以及高精度定位技術(shù)的發(fā)展，使得大量移動對象的移動、位置信息能夠以軌跡數(shù)據(jù)的形式被收集下來，通過分析大量居民軌跡數(shù)據(jù)集為確定城市熱點區(qū)域及提取出行時空特征信息提供了新的重要研究思路。區(qū)別于公交車、地鐵等軌道交通出行載體，出租車是城市中提供給居民便捷和個性化的出行服務(wù)，對出租車行駛過程中產(chǎn)生的軌跡數(shù)據(jù)進行合理挖掘則可以揭示居民出行特征，讓城市規(guī)劃更加合理。

隨著多樣的應(yīng)用場景和數(shù)據(jù)規(guī)模不斷提高，很多經(jīng)典聚類分析方法的不足難以適應(yīng)大數(shù)據(jù)背景下的智能應(yīng)用分析。伴隨著計算機發(fā)展，基于軌跡數(shù)據(jù)的信息挖掘研究不斷豐富更新。程靜等人［1］利用北京市出租車GPS 數(shù)據(jù)，結(jié)合時間序列距離度量和K-means 聚類，研究了乘客出行的時空分布特征。劉旭等人［2］將Canopy 結(jié)合到聚類算法中用于確定簇類值，并應(yīng)用到武漢市公交車站的預(yù)測分析中。Rahman 等人［3］首次提出了智能學(xué)習(xí)G-A-KClustering 遺傳聚類算法，來解決聚類算法中突出的初始化種子點等問題。

傳統(tǒng)K-means 算法在處理小規(guī)模數(shù)據(jù)集上，相較其他聚類算法因其高效的模型結(jié)構(gòu)和良好的聚類效果被廣泛應(yīng)用，而隨著復(fù)雜大規(guī)模數(shù)據(jù)集的應(yīng)用場景加入，其算法主要的弊端逐漸暴露：

（1）初始化中的簇類數(shù)僅憑主觀因素確定。直接決定最后的輸出極有可能達(dá)不到理想的結(jié)果。

（2）不良初始種子點的選擇會隨著算法迭代對結(jié)果產(chǎn)生嚴(yán)重的影響。如何消除K-means 算法在處理大規(guī)模數(shù)據(jù)集上的弊端并有效保留其算法優(yōu)勢是目前研究的重點。

遺傳智能算法具有良好的尋找最優(yōu)解能力，為解決傳統(tǒng)K-means 算法弊端提供了重要的研究思路?；诖?，本文提出一種新的改進型智能遺傳CK-N-Cluster 聚類算法，有效解決種子點數(shù)選擇弊端與病態(tài)初始化等問題，并以杭州市大量出租車GPS 軌跡點為實驗數(shù)據(jù)，實現(xiàn)最佳簇類中心的輸出和城市熱點區(qū)域的挖掘研究，最后通過數(shù)據(jù)分析和可視化方法，研究杭州市城市出租車運行特征，對不同區(qū)域的居民出行規(guī)律展開分析，為城市交通管理和居民出行提供決策服務(wù)。

1 基礎(chǔ)理論

1.1 遺傳算法簡介

遺傳算法（Genetic Algorithm，GA）是當(dāng)前應(yīng)用領(lǐng)域最廣泛、影響最深遠(yuǎn)的優(yōu)化算法之一。通過特定遺傳算子指標(biāo)從父代染色體（解）中篩選出部分優(yōu)秀的子代染色體（更優(yōu)秀的解），重復(fù)迭代，直至達(dá)到最大進化代數(shù)或結(jié)果滿足收斂條件，收斂到的最終個體可能代表著問題的最優(yōu)解或次要解。基本的遺傳算法包含5 個基本步驟：解的編碼；種群初始化；適應(yīng)度函數(shù)選擇；遺傳操作算子；設(shè)定遺傳參數(shù)［4］。

1.2 K-Means 算法描述

聚類（Cluster）是一種常用的無監(jiān)督學(xué)習(xí)，其在機器學(xué)習(xí)、數(shù)據(jù)挖掘等統(tǒng)計應(yīng)用中備受關(guān)注與重視。經(jīng)典K-means 算法由于高效快速的顯著特點已經(jīng)成為聚類算法中使用廣泛的算法之一［5］。常用歐氏距離作為相似性的評價指標(biāo)，計算數(shù)據(jù)集中每一個數(shù)據(jù)點xi與每個質(zhì)心cj在m維空間中的歐式距離d表示為［6］：

當(dāng)有一組n個樣本的數(shù)據(jù)集X，將其分成k個獨立的簇C＝（C1，C2，…，Ck）時，聚類過程可描述為每個簇內(nèi)的平方誤差E不斷降低并趨向最小的過程，平方誤差定義為：

其中，x∈Ci為樣本均值，ui是簇類Ci的質(zhì)心。

2 結(jié)合Canopy-K-Means++的小生境遺傳C-K-N-Cluster算法

本文以杭州市大量出租車GPS 軌跡數(shù)據(jù)為基礎(chǔ)，用密度代替?zhèn)鹘y(tǒng)分類閾值的思想改進Canopy，結(jié)合K-means++算法實現(xiàn)初始化種子點，達(dá)到消除種子點數(shù)選擇與病態(tài)初始化限制的目的，為避免智能學(xué)習(xí)過程易陷入局部最優(yōu)的弊端，通過共享小生境提高遺傳算法操作中的優(yōu)化能力，與K-Means 結(jié)合實現(xiàn)最優(yōu)染色體（聚類中心）的輸出和城市熱點區(qū)域的挖掘研究。

2.1 算法結(jié)構(gòu)設(shè)計

本文通過改進Canopy-K-Means++的初始化種群生成方法、以準(zhǔn)則函數(shù)的倒數(shù)作為適應(yīng)度函數(shù)、遺傳算子的自適應(yīng)設(shè)計、小生境劃分種群等改進方法完成聚類算法的改進優(yōu)化，以消除局部最優(yōu)、病態(tài)初始化、難確定k值等傳統(tǒng)算法弊端。整體的算法設(shè)計步驟如圖1 所示。

圖1 改進算法流程圖Fig.1 Flow chart of the improved algorithm

2.2 染色體編碼及種群初始化

若GPS 數(shù)據(jù)集有n個數(shù)據(jù)點，每個數(shù)據(jù)點都有m個字段特征，假設(shè)種群中有NI條染色體（種群規(guī)模為NI），每條染色體上的基因數(shù)（聚類中心數(shù)）為K1＝｛k1，k2，…，kK1｝。將m個字段屬性綜合起來進行編碼，則該種群可以描述為：

其中，NI為種群規(guī)模；pop表示種群；CHR1、CHR2、…、CHRNI是種群中的各條染色體；K1表示CHR1染色體含有的初始化聚類中心數(shù)量。

同時，在實際操作過程中，需要對該數(shù)據(jù)集通過式（4）進行歸一化處理，使數(shù)據(jù)的范圍值都轉(zhuǎn)換控制在［0，1］范圍內(nèi)：

種群初始化過程中，初始聚類中心點的選擇對最后的聚類效果影響頗大，傳統(tǒng)K-Means 算法的隨機生成與改進后的K-Means++距離分散初始點生成方法較為常見，但前者結(jié)果的最優(yōu)值有著不穩(wěn)定性，后者并不適用于數(shù)量多而富含信息量少的冗余數(shù)據(jù)集［7］。Canopy 算法是一種結(jié)構(gòu)簡單、使用距離測度的聚類數(shù)生成方法，已廣泛出現(xiàn)在各類聚類應(yīng)用中［8］。本文利用密度概念對Canopy 算法進行改進并與K-Means++算法結(jié)合完成種群初始化［9］：

（1）設(shè)置一組密度，用于生成不同基因數(shù)目（種子點數(shù)量）的種群：

Den＝［d1，d2，…，dNI］＝［0.000 1，0.000 5，0.001，0.002，0.003，0.004，0.005，0.006，0.007，0.008，0.009，0.1，…］。

（2）基于以上NI個不同半徑生成NI條不等長的染色體：簡化Canopy，將2 個閾值T1與T2 簡化為一個閾值集合Den。

（3）向列表List中放入向量化的數(shù)據(jù)集，從List中隨機選取一點P1作為第一個Canopy。

（4）從List中隨機選取的點Pi開始快速計算點Pi與所有已有Canopy 之間的距離半徑，如果點Pi與某個Canopy 距離在T以內(nèi)，則將點Pi加入到這個Canopy，同時點Pi從List中刪除。

（5）重復(fù)步驟（3），當(dāng)List中每個點都刪除完畢，輸出該Den值下的一條染色體長度（Canopy 數(shù)量）。

（6）重復(fù)執(zhí)行步驟（3）～（5）各NI次，使用K-Means++方法初始化種群作為每條染色體上的基因（聚類中心），直到成功生成NI條長度不同的染色體為止。

2.3 適應(yīng)度函數(shù)設(shè)計

考慮到聚類過程即是每個簇內(nèi)的平方誤差不斷降低并趨向最小的過程，將平均標(biāo)準(zhǔn)函數(shù)作為該過程的準(zhǔn)則函數(shù)：

其中，E表示數(shù)據(jù)集在不同中心點下的準(zhǔn)則函數(shù)，也稱聚類代價，E值越小，代表聚類效果越好，各簇內(nèi)相似度越高。為與遺傳算法結(jié)合，本文利用準(zhǔn)則函數(shù)的倒數(shù)作為適應(yīng)度函數(shù)：

2.4 遺傳操作

（1）基于相似度的基因交叉。由于種群中染色體長度不一致，無法與其他相關(guān)等長染色體一樣簡單地實現(xiàn)局部交叉操作［10］，本文利用基因重排技術(shù)［3］，根據(jù)余弦定理計算不同染色體中的相似性，將相似性高的作為交叉操作中的參考體［11］，具體操作步驟如下：

①迭代中及時存儲適應(yīng)度最好的染色體CHRbest。

②通過賭輪盤方法［12-13］從種群隨機挑選2 條染色體CHRi、CHRj，輪盤賭方法實現(xiàn)概率問題、即適應(yīng)值越大，選出的概率就越大，計算方法見式（7）：

③用余弦相似度計算CHRi、CHRj、CHRbest之間的相似度，對于長度不一致的染色體，通過將短的染色體后端自動補零來實現(xiàn)等長計算相似度操作。將最好和最差的分別作為基因交叉中的參考和目標(biāo)染色體，實現(xiàn)適應(yīng)值大的染色體基因?qū)m應(yīng)度差的染色體基因的替代。

④對選出的參考染色體和目標(biāo)染色體按照式（8）進行基因單點交叉操作［14］，即2 個父代染色體通過預(yù)設(shè)的交叉概率生成新的2 個子代染色體，保障種群的多樣性。需要注意的是，完成一次交叉操作后需要將父代染色體移除，以保證交叉后得到的新染色體對父代染色體的迭代更新。這里的式（8）可表示為：

（2）基于密度劃分小生境操作。本文引入密度參數(shù)劃分小生境，并通過預(yù)選擇機制完成后續(xù)操作，達(dá)到提高種群的多樣性和全局優(yōu)化水平的目的。具體步驟如下：

①預(yù)設(shè)一個合適的密度參數(shù)R，通過式（4）對預(yù)處理數(shù)據(jù)進行歸一化。

②處理后的數(shù)據(jù)按照R進行可達(dá)性計算（從一個頂點到另一個頂點的容易程度），記錄各分類數(shù)量。

③統(tǒng)計各分類內(nèi)部點的數(shù)量，把數(shù)量最多的類當(dāng)成一個小生境。

④重復(fù)步驟③，直到所有點都被選擇過，進行小生境劃分。

⑤對劃分的小生境執(zhí)行預(yù)選擇操作。

3 實驗數(shù)據(jù)與預(yù)處理方法

杭州市是中國沿海地區(qū)較為重要的交通樞紐和長江三角洲中心城市之一，人口規(guī)模約一千二百余萬。對其城市交通的熱點區(qū)域和城市出行特征展開研究分析具有必要性。本文采用杭州市2019 年9月24 日全市約一萬輛正常運營出租車一天的GPS定位數(shù)據(jù)為實驗數(shù)據(jù)集，基本覆蓋全天段杭州市出租車整體運營狀況，數(shù)據(jù)樣本集能夠很好地反映該時間段杭州市居民出行的實際情況。分布情況顯示，大部分市內(nèi)中心路網(wǎng)已被覆蓋。

本文選用數(shù)據(jù)集包含車輛編號、定位時間戳、經(jīng)度、緯度、瞬時速度、行駛方向、車輛狀態(tài)的屬性，數(shù)據(jù)描述見表1。

表1 軌跡數(shù)據(jù)集描述Tab.1 Description of track data set

3.1 預(yù)處理操作

本文對研究采用的原始出租車軌跡數(shù)據(jù)需要處理的異常數(shù)據(jù)，擬做闡釋分述如下：

（1）超出研究區(qū)范圍：本文以杭州市及其周邊為研究對象，經(jīng)緯度范圍為東經(jīng)120°00′至120°43′和北緯30°16′至30°50′。

（2）異常數(shù)據(jù)：主要為該時間段內(nèi)速度始終為零的數(shù)據(jù)、行駛過程中速度超過市區(qū)最大限速1.5倍的不合格數(shù)據(jù)。

（3）冗余數(shù)據(jù)的化簡：使用模型簡單、運算速度快的Douglas-Peucker 算法，以采樣軌跡點與前后相鄰采樣軌跡點間的平均距離和速度來識別篩選。

3.2 上下客源軌跡點篩選

根據(jù)出租車軌跡數(shù)據(jù)的車輛狀態(tài)字段，其值為“0”和“1”時，分別代表不同的車載狀態(tài)“空車”和“重車”，當(dāng)該字段的數(shù)值發(fā)生變化時，表示車輛載客狀態(tài)的改變，即該地點為一個上下客軌跡點。但實際數(shù)據(jù)中會存在上下兩個客源點位置與實際上下客點位置距離過大的異常數(shù)據(jù)，本文將7.50 km／h的時速設(shè)置為速度閾值：

（1）當(dāng)2 個相鄰軌跡點的行駛速度均小于該速度閾值時，則表示該2 個數(shù)據(jù)點位置與真正的上下客點距離誤差較小，可以視為有效的上下客軌跡點。

（2）對于車載狀態(tài)發(fā)生改變、但并不滿足該速度閾值條件的2 個軌跡點，則將軌跡點中速度較小的作為有效上下客點進行保留。

提取上下載客點坐標(biāo)數(shù)據(jù)步驟如圖2 所示。

圖2 上下客源有效點提取Fig.2 Effective point extraction of up and down passenger sources

4 實驗與數(shù)據(jù)可視化分析

4.1 城市時段熱點區(qū)域分析

通過對杭州市一天出租車軌跡數(shù)據(jù)研究城市出行熱點區(qū)域的劃分識別。文中利用軟件Matlab2020a 實現(xiàn)上述小生境C-K-N-Cluster 算法，設(shè)置種群規(guī)模sizepop＝100，初始種群密度半徑劃分Den＝［d1，d2，…，dNI］＝［0.000 1，0.000 2，0.000 3，0.000 4，0.000 5，0.001，0.002，0.003，0.004，0.005，0.006，0.007，…］共100個，代表初始化100 個不同長度大小的個體。設(shè)置交叉概率P（cross）＝0.6，變異概率P（mutation）＝0.01，小生境劃分密度R＝0.4，對預(yù)處理上下載客點數(shù)據(jù)進行導(dǎo)入，對具有代表性的3 個不同時間段數(shù)據(jù)分別繪制迭代適應(yīng)度變化曲線，其中2 條曲線分別反映了平均適應(yīng)度avgfitness和最佳適應(yīng)度bestfitnessd的值隨迭代次數(shù)的變化情況，為避免因次數(shù)過少導(dǎo)致的優(yōu)化不足以及次數(shù)過多所帶來的浪費計算時間，本文從曲線變化規(guī)律中設(shè)置迭代次數(shù)Margen＝150 次。3 個時間段載客迭代適應(yīng)度變化曲線如圖3 所示。

圖3 3 個時間段載客迭代適應(yīng)度變化曲線Fig.3 Change curve of passenger carrying iteration fitness during three time periods

基于改進Canopy 算法種群初始方法完成種群初始化，迭代結(jié)束自動計算出5 個時間段上下車簇類數(shù)，結(jié)果進行可視化顯示，如圖4 所示。

圖4 各時間段載／卸客簇類結(jié)果可視化Fig.4 Visualization of passenger load／unload cluster results in each time period

由結(jié)果可知，居民出行較為集中，而中午出行較分散，這也與居民正常出行特征相吻合。表2 統(tǒng)計了研究范圍內(nèi)幾個典型時段內(nèi)上下客熱點區(qū)域大致分布，這些聚類中心區(qū)域周邊大量分布著商業(yè)、交通、城市服務(wù)等居民需求地點。圍繞這些城市熱點展開的城市功能區(qū)規(guī)劃和出租車分布管理將極大地方便城市管理與居民出行需求。

表2 典型時段上下客軌跡點熱點區(qū)域統(tǒng)計Tab.2 Statistics of hot spot areas of boarding in typical time periods

4.2 城市客流量與運營分析

通過對所有上下載客點數(shù)據(jù)進行了時間劃分，以1 h 作為時間間隔，統(tǒng)計24 個時間段內(nèi)的出行量分布［12］，對一天中不同時段的客流量的變化特征進行分析，居民不同時域出行量分布如圖5 所示。

圖5 居民時域出行量分布圖Fig.5 Distribution of residents′ travel volume in time domain

定義早7：00 到10：00 和晚17：00 到19：00 為高峰時段，經(jīng)緯度數(shù)據(jù)通過逆解析完成區(qū)域劃分，并分別計算各區(qū)域高峰與平時時段的出租車空載率和載客率占比，選擇具有代表性的西湖區(qū)、江干區(qū)、下城區(qū)、拱墅區(qū)進行分析。分析結(jié)果如圖6 所示。由圖6 可以看到，4 個象限從綠色象限開始順時針分別代表“高峰空載”、“平時空載”、“高峰載客”、“平時載客”，數(shù)值代表此時段出租車運營所占百分比。

圖6 西湖、江干、下城、拱墅各區(qū)高峰與平時運營比例（左上順時針）Fig.6 Proportion of peak and normal operation in West Lake，Jianggan，Xiacheng and Gongshu districts（upper left clockwise）

該分布顯示出租車空載率在高峰時間段明顯小于載客率，符合實際情況且未拉開過大差距，反映出杭州市市區(qū)出租車服務(wù)數(shù)量并不短缺，能夠基本滿足高峰時間段居民的出行需求。但在非高峰時間段存在出租車空載率較高的問題，綜合反映出杭州市出租車數(shù)量方面較為飽和，同時江干區(qū)高峰時間段出租車需求最大，考慮該時段將周邊出租車調(diào)度進來服務(wù)將得到有效緩解。

4.3 出租車行駛軌跡與主要跨區(qū)流動分析

忽略天氣和節(jié)假日等其他因素影響，僅從單日的出租車軌跡數(shù)據(jù)分析，將行駛路程較遠(yuǎn)的出租車軌跡數(shù)據(jù)記錄標(biāo)記出來，具體如圖7 所示。

整理圖7 復(fù)雜的軌跡，進一步得到圖8。圖8代表各區(qū)之間的跨區(qū)出租車流動網(wǎng)絡(luò)，線條的粗細(xì)直觀展示了區(qū)間流動量的大小。圖8 中顯示西湖區(qū)、拱墅區(qū)、江干區(qū)之間的車輛流動量較大，西湖區(qū)、江干區(qū)、拱墅區(qū)和下城區(qū)是出租車最密集的區(qū)域。出租車跨區(qū)行駛的情況存在較大差異，西湖區(qū)到江干區(qū)，西湖區(qū)到下城區(qū)、拱墅區(qū)的數(shù)量較多。從數(shù)據(jù)中準(zhǔn)確地計算發(fā)現(xiàn)，23%的出租車集中在西湖區(qū)，江干區(qū)、下城區(qū)和拱墅區(qū)的出租車數(shù)量分別16%、13%、12%。

圖7 行駛軌跡Fig.7 Driving track of the Taxi

圖8 跨區(qū)流動網(wǎng)絡(luò)Fig.8 Cross-region network

5 結(jié)束語

本文利用杭州市一天內(nèi)的出租車載客軌跡數(shù)據(jù)挖掘城市的活動信息，用密度概念代替?zhèn)鹘y(tǒng)分類閾值的思想改進Canopy，提出基于結(jié)合Canopy-KMeans++的小生境遺傳策略聚類算法，達(dá)到消除種子點數(shù)選擇、病態(tài)初始化和局部最優(yōu)等弊端的目的，最后成功結(jié)合數(shù)據(jù)可視化完成挖掘載客熱點和城市出行時空特征信息。但仍需指出的是，由于實驗數(shù)據(jù)數(shù)量具有局限性，所分析的數(shù)據(jù)時間跨度僅為一天，難以保證實驗結(jié)果的普適性。此外，出租車數(shù)據(jù)是隨著時間動態(tài)變化的［15］，若引入在交通運輸系統(tǒng)中適用的動態(tài)聚類算法框架可以對其進行改進。故分析長期的載客熱點區(qū)域與居民通勤模型是下一步需解決的研究問題。