基于劃分的聚類在交通規劃小區中的應用

劉彥斌，智 偉，溫熙華，劉云鵬，程元暉，方志遠

（中電海康集團研究院，浙江 杭州 310012）

基于劃分的聚類在交通規劃小區中的應用

劉彥斌，智 偉，溫熙華，劉云鵬，程元暉，方志遠

（中電海康集團研究院，浙江 杭州 310012）

城市交通系統龐大而復雜，為保證交通管理的靈活性及魯棒性，必須劃分交通小區分而治之。針對現有的基于劃分的聚類算法應用于交通規劃小區存在的問題，文章基于交通特性定義了聚類有效性指標，進而設計了將模糊C均值聚類與K均值聚類相結合的交通小區劃分算法。以吳江區為例，結合17萬余條出租GPS數據，搭建GIS平臺劃分交通小區，驗證了算法的有效性，進而可視化地分析了小區之間的交通OD，為城市交通運營、規劃部門決策提供重要參考和依據。

交通小區；K均值聚類；模糊C均值聚類；聚類有效性指標；交通OD

0 引 言

城市交通系統是一個非線性、強耦合、離散、并具有隨機特性的復雜大系統[1]，很難直接對其建模分析。在這種情況下，交通小區應運而生，采用分而治之的思想：將復雜交通網絡解耦為若干個交通子區，分別對每個子區進行誘導和控制，從而實現對整個交通的協調優化。這種內部具有一定交通關聯度和交通相似度的交通子區就被定義為交通小區[2]。根據決策的層級不同，交通小區可分為面向交通控制的交通小區、面向交通誘導的交通小區以及面向交通規劃的交通小區。交通小區的誕生一方面保證了交通管理的靈活性，可因地制宜地根據小區間的不同交通特性制定差異性的管理策略；同時也保證了整個交通系統魯棒性，避免了單一控制中心癱瘓可能引發的災難性損失。因此，交通小區劃分在降低系統復雜性、提高交通管理效率方面具有重要的意義。

然而，現有的對交通小區的研究多停留在應用層面，缺乏對于交通小區劃分理論的深入研究。目前交通小區的劃分帶有很大的主觀性，往往根據行政單元或路網物理特性劃分，而忽略了內在交通特征的影響。本文關注面向交通規劃的交通小區，依據交通特征的空間分布特性，采用基于劃分的聚類方法進行交通小區的自動劃分，進而可視化地展現了小區間的OD，方便城市交通運營、規劃部門宏觀地了解居民出行分布狀況，為公共交通線路規劃、站點設置提供重要參考和依據。

1 基于劃分的聚類方法介紹

聚類是機器學習中一種重要的非監督學習方法，其目的是將數據集中的樣本劃分為若干個通常不相交的子集，每個子集稱為一個“簇”，每個“簇”可能對應一個潛在的概念。而基于劃分的聚類又是聚類方法中的重要分支[3]，其核心思想是定義代價函數來描述劃分的進程，通過不斷的試錯，調整樣本劃分，將使得代價函數最小的劃分作為最終的聚類結果。在劃分中我們希望簇內樣本比較相似，而簇間樣本差異較大，代價函數則是定量表述這一目標的工具，不失一般性的，給出如下所示的代價函數：

其中：n為數據集樣本個數；c為指定劃分的簇個數；xj表示第j個數據樣本；ci表示第i個簇的中心；d（ ci, xj）表示第j個數據樣本到第i個簇中心的“距離”，有閔可夫斯基距離、馬氏距離及切比雪夫距離等；J表示代價函數，是c個簇的代價函數之和；Ji表示第i個簇的代價函數，其物理含義是數據集所有對象與第i個簇中心的加權距離；uij表示樣本j歸屬于簇i的隸屬度，自然的有：

至此，基于劃分的聚類已抽象為一個帶有約束條件的最優化問題了。然而，樣本到簇中心“距離”的定義通常很復雜，式（1）屬非凸優化問題，很難直接求得全局最優。因此，我們通常采用啟發式算法，如最大期望算法（Exception Maximization Algorithm）、梯度下降法（Gradient Descent）等，來求得局部最優解。

在基于劃分的聚類算法中，樣本j歸屬于簇i的隸屬度uij是一個很重要的參數，根據其設置的不同，基于劃分的聚類可分為硬聚類及軟聚類兩大派系。在硬聚類中隸屬度uij的取值非0即1，也就是說每個樣本被硬性地劃分到唯一一個簇中，具備“非此即彼”的特性，因而產生的簇不會發生重疊。在軟聚類中隸屬度uij可取0到1間的任意實數，也就是說樣本以不同的概率被劃分到各個簇中，這種“模糊”劃分的特性就導致了產生的簇可能會發生重疊。

2 交通小區劃分

交通小區是具有一定交通關聯度和交通相似度的節點或連線的集合，同一小區內的交通狀態應比較相近，而不同小區間的交通狀態則應相差較大。居民出行的起訖點（Original&Destination points，OD）恰恰是交通小區作用下的外在表現，因而可以根據起訖點的集聚特性進行聚類操作，挖掘OD數據背后隱藏的交通小區分布規律。

常用的K均值聚類（K-means）屬于硬聚類，這種硬性地簇劃分是符合對于交通小區劃分的需求的[4]，然而K-means算法在實際應用中存在兩大問題：一是聚類個數無法事先確定，也就是說待規劃交通小區個數的選取具有盲目性；二是K-means算法嚴重依賴初始聚類中心的選取，不同的初始化參數直接導致聚類結果的不同，而事實上是無法提前獲知交通小區的中心的。兩方面的原因導致了以K-means為代表的硬聚類在交通小區劃分中的局限性。

常用的模糊C均值聚類（FCM）屬于軟聚類，這種軟性的劃分雖運行速度較快，且不需要額外的初始化參數[5]，但同樣需事先指定小區個數，而且分類結果具有二義性，其產生的重疊的聚類結果不符合規劃交通小區的需求，這也限制了以FCM為代表的軟聚類在交通小區劃分領域的應用。

可見，無論軟聚類還是硬聚類都無法完全滿足劃分交通小區的需求。基于此，本文設計了將K-means與FCM相結合的改進算法。其基本思想是先利用FCM做初步劃分，以此形成K-means的初始化參數，進而再由K-means做進一步精細劃分。

本文采用的數據源為吳江2017.3.1～2017.3.7為期一周的出租車GPS數據，共177 927條記錄。剔除異常記錄，包括經緯度為空或為0、行程終點時間早于起點時間等明顯異常的記錄后，剩余153 035條有效數據，對應306 070個起訖點。之所以選擇出租GPS數據作為數據源，一方面是因為，作為非通勤性出行的工具，出租車本身就代表性地反應了區民多樣的出行需求；另一方面，利用出租的GPS數據可自動化地獲取大量的OD，節省人工調查成本的同時保證了數據精度。

2.1 基于FCM的交通小區劃分

FCM引入模糊聚類指數m來控制算法的柔性，本文中取定為2。將第j個數據樣本到第i個簇中心的“距離”簡記為dij，將隸屬度 uij（c×n）記為隸屬度矩陣U，則式（1）轉化為：

同時，FCM需要滿足式（2）所示的約束條件。為求解這個約束條件下的最優化問題，本文引入拉格朗日函數：

其中：λj是n個約束條件的拉格朗日乘子。對上式所有參量求導，得到代價函數J取極小值的必要條件：

至此，可以得到利用FCM進行交通小區劃分的處理流程：

步驟一：在式（2）的約束條件下隨機初始化起訖點的隸屬度矩陣U。

步驟二：利用式（5）求解c個交通小區的中心。

步驟三：利用式（3）計算代價函數。如果代價函數相較于上一次運算的結果改變不大（差別小于給定閾值），則轉至步驟五，否則進行步驟四。

步驟四：利用式（6）計算起訖點的隸屬度矩陣U，其中dij取為歐式距離，結合步驟二中得到的交通小區中心位置容易求得。之后，返回步驟二。

步驟五：利用起訖點的隸屬度矩陣U判定其所屬的交通小區，結束算法。判定原則是：如果起訖點屬于某交通小區的隸屬度達到最大，則判定其屬于該小區。

利用FCM劃分交通小區，指定不同的交通小區個數，得到的結果如圖1所示：

圖1 吳江出租起訖點在不同交通小區個數下的FCM聚類結果

圖1中每個星號點都代表一個真實的出租起訖點（橫坐標為經度，縱坐標為緯度），利用FCM進行聚類，得到每個起訖點所屬的交通小區，以不同顏色標識。該算法運行速度較快，且不需要額外參數。但是算法也存在兩個問題，一是劃分結果依賴交通小區個數的選取，如圖1所示，從左至右依次給出了交通小區個數為4～6的劃分結果，而在現實情況下，小區的個數很難事先確定；二是劃分結果具有二義性，如上圖黑色點標識的樣本，由于在兩個小區間的隸屬度相等，算法判定其同時屬于2個交通小區。換言之，算法產生了重疊的交通小區，不滿足本文的應用場景。

2.2 基于K-means的交通小區劃分

K-means中隸屬度uij只能取0或1，為了加以區別定義二元指標rij∈ 0,｛1，｝表征樣本j是否隸屬于簇i，由式（2）不難得出：

式（1）中，樣本和簇中心的距離取為歐式距離，則式（1）特化為：

要在式（7）的約束條件下使得J最小，已被證明為NP難問題，采用最大期望算法，得到迭代公式：

至此，可以得到利用K-means進行交通小區劃分的處理流程：

步驟一：隨機初始化c個交通小區的中心。

步驟二：利用式（9）求解二元指標rij，其物理含義即根據樣本與各小區中心的距離判定其所屬的小區。

步驟三：利用式（8）計算代價函數。如果代價函數相較于上一次運算的結果改變不大（差別小于給定閾值），則終止算法，否則進行步驟四。

步驟四：利用式（10）更新交通小區中心。之后，返回步驟二。

利用K-means劃分交通小區，指定不同的交通小區個數、初始中心得到的結果如圖2、圖3所示。

該算法對所有起訖點做“非此即彼”的明確劃分，但是也存在兩個問題，一是劃分結果依賴交通小區個數的選取，如圖2所示，從左至右依次給出了交通小區個數為4～6的劃分結果，而在現實情況下，小區的個數很難事先確定；二是劃分結果額外依賴初始交通小區中心的選取，圖3給出了不同初始化參數下的聚類結果，差異較大，因此為了避免K-means收斂到不同的局部最優解，必須合理地給出交通小區中心的初始化算法。

圖2 吳江出租起訖點在不同交通小區個數下的K-means聚類結果

圖3 吳江出租起訖點在不同初始交通小區中心下的K-means聚類結果

2.3 FCM與K-means相結合的交通小區劃分

2.3.1 基于FCM確定交通小區的個數及中心。為了評價不同的聚類結果，首先要定義聚類有效性指標。常用有效性指標有：Calinski-Harabasz（CH）指標、Davies-Bouldin（DB）指標、以及Silhouette（S） 指標等，但上述指標的設計并未考慮交通特性，單純的基于樣本幾何結構的評價并不適用于本文的應用場景。因此，定義了“劃分系數”S作為有效性指標，綜合考慮了區內通行量，區內及區間通行距離等因素，如式（11）所示：

其中：dij表示樣本i到小區j中心的距離，nj為第j個交通小區內起訖點的個數，Rj為第j個交通小區的平均半徑，n為全部起訖點的個數，可以看出Rinner是對Rj按通行量的加權平均，用于描述小區內部起訖點的緊密度，表征小區內交通的相似性。

pij為小區i中心與小區j中心的距離，Router是全部小區中心兩兩距離之和，用于描述各小區間的分離度，表征小區間交通的差異性。

我們希望劃分的交通小區具有這樣的特性：在同一小區內，交通特性應有很強的相似性，即Rinner要小；同時，不同小區間的交通特性應有足夠的差異性，即Router要大，因此“劃分系數”S越小，表征所對應的劃分結果越優秀。

根據交通小區劃分的相關文獻[6]、結合小區劃分的經驗常識，給定吳江區交通小區個數的待選范圍 2,1[ ] 0，利用FCM在不同的交通小區個數條件下進行聚類，并利用“劃分系數”評價各聚類結果，得到圖4。

可以看出，在2個小區的情況下，劃分系數相對較大；隨著交通小區個數的增加，劃分系數迅速下降，當小區個數增至6時，劃分系數取到極小值，表征最優的劃分結果；繼續增加小區個數，劃分系數已不會明顯變化，甚至增大。因此，本文選定吳江區交通小區的劃分個數為6，此時FCM得到的6個交通小區中心如表1所示：

表1 FCM初步規劃6個交通小區中心位置

2.3.2 基于K-means精細劃分各個交通區。選定交通小區個數為6，并將FCM得到的6個交通小區中心位置作為K-means聚類的初始化參數，對吳江出租全部起訖點進行聚類，得到圖5。

圖4 FCM聚類劃分系數隨交通小區個數變化圖

圖5 以FCM得到的小區中心初始化K-means聚類結果

將上述改進算法與傳統的FCM及K-means進行有效性對比，得到表2。由于傳統K-means聚類結果依隨機初始值的不同而變化，導致劃分系數相應的波動，表中是多次聚類后的平均劃分系數。

表2 不同聚類方法有效性對比

可以看出，改進算法對應的劃分系數最小，意味著該劃分得到的交通小區內具有相似的交通屬性，同時不同小區之間的交通差異性也相對明顯，因而是相對較優的算法。

2.3.3 搭建GIS平臺生成交通小區邊界。在聚類完成后，我們得到了所有起訖點所屬的小區（以不同顏色標識），進而需要解決小區邊界標定的問題。文獻[4]提出基于樣本與聚類中心的距離生成邊界的算法，但方法過于粗糙，存在漏劃區域，且默認所有小區都采用同樣邊數的多邊形，顯然不符合真實場景。

為保證劃分的合理性，如無漏劃、道路不被切割等，搭建GIS平臺，通過糾偏將出租起訖點定位到地圖上，以充分展示每個起訖點周圍的道路屬性，進而根據聚類結果精細劃分小區邊界。其劃分原則是：由城市路網生成小區邊界，且其內盡可能多的包含隸屬于該小區的起訖點。將不同小區的起訖點以不同顏色標識在地圖上，將地圖放大至道路級別，篩選不同顏色起訖點的分界路段作為交通小區邊界，如圖6所示。

3 實例分析

針對吳江2017.3.1～2017.3.7為期一周的出租車GPS數據，采用本文所述的FCM與K-means相結合的交通小區劃分算法，對全部起訖點做聚類分析，得到其隸屬的小區ID；進而利用java搭建GIS平臺，通過糾偏將全部訖點定位到地圖上，根據起訖點周圍的道路屬性精細生成交通小區邊界，得到圖7（僅保留吳江區域）：

圖6 根據起訖點周圍的道路屬性生成交通小區邊界

圖7 吳江交通小區劃分

劃分交通小區后，利用出租車OD數據即可宏觀分析城市居民出行分布狀況，了解交通需求的空間特性，計算交通小區間的OD矩陣，得到表3。

表3內容的第i行第j列的元素表示由小區i到小區j的出行量。例如，第3行第5列的元素為4 758，表示一周內由小區3出發，到小區5的出租乘客共有4 758位。為了更直觀地展示交通流量的空間流動特性，本文采用了弦圖，如圖8所示。

弦圖的各弧代表各個小區，弧的角度大小代表以該小區為起點的OD量，弧被分為6種顏色，體現6個小區的交通屬性。弦圖的各弦代表兩個小區之間的交通往來，如小區3、小區5間的弦，與小區3相連的一端代表小區3到小區5的OD量，與小區5相連的一端代表小區5到小區3的OD量，弦被分為36種寬度，一一對應于OD矩陣的每一個元素。因此，可以直觀地看出：小區5是出行量最大的交通小區，小區4次之、小區6再次；小區5、6之間，小區3、5之間以及小區2、4之間的通行量相對較大。以上基于出租OD數據的聚類結果結合吳江土地利用布局也不難解釋：吳江區委區政府所在地松林鎮隸屬小區6，蘇嘉杭高速、滬蘇浙高速、蘇州繞城高速穿境而過，屬交通樞紐；“絲綢重鎮”盛澤鎮坐落于小區4，很多國內外的商人需要來這里做交易；“中國特色商業街”永康路位于小區5，服裝店、首飾店、購物中心林立其中，產生巨大的交通吸引。

表3 交通小區間OD矩陣

因此，建議吳江區交管部門參考本文給出的交通小區劃分結果，分區進行差異性地交通誘導和控制。同一小區內的交通特性較為相似，因而可以將全區的交通信號整合到一個系統，以保證全區的整體控制效益；不同小區間的交通特性相差較大，因而可針對性的選擇定時式脫機操作或感應式聯機操作等不同的控制系統。這種分而治之的策略，保證交通管理靈活性的同時，避免了單一控制中心癱瘓可能引發的災難性損失。

另外，基于交通小區的交通特性分析還可為交通運營部門合理規劃公交、公共自行車站點以及出租候客泊位提供依據，同時也可對交通規劃部門進行公共交通線路規劃、站點設置等提供參考。以吳江區為例，針對小區4、小區5這樣出行流量較大的區域，可考慮增加公共自行車、出租車的分配比重以減緩出行壓力，達到供需的動態平衡；針對小區5、6之間，小區3、5之間存在大流量區間通行的狀況，可考慮規劃相應的公交專線，以滿足居民在不同小區間的出行需求。

圖8 交通小區間OD弦圖

4 結束語

交通小區劃分是區域交通誘導控制以及城市規劃的基礎，是解析復雜城市交通網絡的有利工具。居民出行的起訖點是交通小區作用下的外在表現，因而可以根據起訖點的集聚特性進行聚類，挖掘OD數據背后隱藏的交通小區分布規律。本文重點研究了基于劃分的聚類方法，以K均值聚類為代表的硬聚類嚴重依賴初始聚類中心的選取，而以模糊C均值聚類為代表的軟聚類可能產生重疊的交通小區，均不能完全契合劃分交通小區的需求。

因此，本文設計了將模糊C均值聚類與K均值聚類相結合的交通小區劃分算法。首先，指定交通小區個數的范圍，對全部起訖點在不同小區個數的條件下進行模糊聚類，得到一系列聚類結果；然后，綜合考慮區內通行量、區內及區間通行距離等因素，定義聚類有效性指標“劃分系數”，對每個聚類結果評價其有效性，并選擇有效性最高的聚類數作為最佳小區劃分個數；最后，利用最佳聚類數、最佳模糊聚類中心初始化K-means算法，使其迅速收斂，克服了傳統K-means算法需要人工定義交通小區個數以及小區中心初始值的盲目性。

以吳江區為例，結合17萬余條出租GPS數據，搭建GIS平臺，并利用上述算法劃分交通小區。對比分析表明，所設計算法的劃分系數為0.0048，明顯優于傳統的模糊C均值聚類及K均值聚類算法，從而驗證了算法的有效性。在此基礎上，可視化地分析了所劃分的交通小區間的OD，可為城市交通運營、規劃部門決策提供重要參考和依據。

[1] Richardson I E.Video Codec Design:Developing Image and Video Compression Systems[S].John Wiley&Sons Inc,2002.

[2] 李曉丹，楊曉光，陳華杰.城市道路網絡交通小區劃分方法研究[J].計算機工程與應用，2009,45(5):19-22.

[3] 包穎.基于劃分的聚類算法研究與應用[D].大連：大連理工大學（碩士學位論文），2008.

[4] 呂玉強，秦勇，賈利民,等.基于出租車GPS數據聚類分析的交通小區動態劃分方法研究[J].物流技術，2010,29(9):86-88.

[5] 劉乙霏.基于模糊聚類的交通小區劃分方法研究[J].物流科技，2011,34(9):25-28.

[6] 郭嶠楓.淺析交通小區劃分問題[J].黑龍江科技信息，2010(28):270.

Application of Partition-based Clustering to Traffic Zone Planning

LIU Yanbin,ZHI Wei,WEN Xihua,LIU Yunpeng,CHENG Yuanhui,FANG Zhiyuan

(CETHIK Group Corporation Research Institute,Hangzhou 310012,China)

Nowadays,urban transport system is becoming ever more complex.In order to ensure the flexibility and robustness of traffic management,traffic zone must be divided so that it can be ruled separately.This article addresses problems on the application of partition-based clustering to traffic zone planning.The clustering validity index based on traffic characteristics is firstly defined,and then the algorithm for traffic zone division,combining fuzzy C-means cluster and K-means cluster,is proposed. Taking Wujiang district as an example,based on more than 170 000 GPS data of taxis,GIS platform is constructed to divide traffic zone,which verifies the effectiveness of the proposed algorithm.Finally,the traffic OD matrix between traffic zones is analyzed visually,as the outcome the important reference and basis for urban transportation operation and planning department could be obtained.

traffic zone;K-means cluster;FCM cluster;clustering validity index;traffic OD

F570

A

1002-3100(2017)08-0072-06

2017-06-05

工信部2016年工業轉型升級（中國制造2025）項目，項目編號：0714-EMTC02-5737/5。

劉彥斌（1986-），男，湖南株洲人，中電海康集團研究院，車聯網技術總監，碩士，研究方向：交通大數據、交通運輸管理、交通流建模與仿真、交通系統分析。