劉彥斌，智 偉，溫熙華，劉云鵬，程元暉，方志遠(yuǎn)

（中電?？导瘓F(tuán)研究院，浙江 杭州 310012）

基于劃分的聚類在交通規(guī)劃小區(qū)中的應(yīng)用

劉彥斌，智 偉，溫熙華，劉云鵬，程元暉，方志遠(yuǎn)

（中電海康集團(tuán)研究院，浙江 杭州 310012）

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

交通小區(qū)；K均值聚類；模糊C均值聚類；聚類有效性指標(biāo)；交通OD

0 引 言

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

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

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

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

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

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

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

2 交通小區(qū)劃分

交通小區(qū)是具有一定交通關(guān)聯(lián)度和交通相似度的節(jié)點(diǎn)或連線的集合，同一小區(qū)內(nèi)的交通狀態(tài)應(yīng)比較相近，而不同小區(qū)間的交通狀態(tài)則應(yīng)相差較大。居民出行的起訖點(diǎn)（Original&Destination points，OD）恰恰是交通小區(qū)作用下的外在表現(xiàn)，因而可以根據(jù)起訖點(diǎn)的集聚特性進(jìn)行聚類操作，挖掘OD數(shù)據(jù)背后隱藏的交通小區(qū)分布規(guī)律。

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

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

可見，無論軟聚類還是硬聚類都無法完全滿足劃分交通小區(qū)的需求?；诖耍疚脑O(shè)計(jì)了將K-means與FCM相結(jié)合的改進(jìn)算法。其基本思想是先利用FCM做初步劃分，以此形成K-means的初始化參數(shù)，進(jìn)而再由K-means做進(jìn)一步精細(xì)劃分。

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

2.1 基于FCM的交通小區(qū)劃分

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

同時，F(xiàn)CM需要滿足式（2）所示的約束條件。為求解這個約束條件下的最優(yōu)化問題，本文引入拉格朗日函數(shù)：

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

至此，可以得到利用FCM進(jìn)行交通小區(qū)劃分的處理流程：

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

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

步驟三：利用式（3）計(jì)算代價(jià)函數(shù)。如果代價(jià)函數(shù)相較于上一次運(yùn)算的結(jié)果改變不大（差別小于給定閾值），則轉(zhuǎn)至步驟五，否則進(jìn)行步驟四。

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

步驟五：利用起訖點(diǎn)的隸屬度矩陣U判定其所屬的交通小區(qū)，結(jié)束算法。判定原則是：如果起訖點(diǎn)屬于某交通小區(qū)的隸屬度達(dá)到最大，則判定其屬于該小區(qū)。

利用FCM劃分交通小區(qū)，指定不同的交通小區(qū)個數(shù)，得到的結(jié)果如圖1所示：

圖1 吳江出租起訖點(diǎn)在不同交通小區(qū)個數(shù)下的FCM聚類結(jié)果

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

2.2 基于K-means的交通小區(qū)劃分

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

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

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

至此，可以得到利用K-means進(jìn)行交通小區(qū)劃分的處理流程：

步驟一：隨機(jī)初始化c個交通小區(qū)的中心。

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

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

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

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

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

圖2 吳江出租起訖點(diǎn)在不同交通小區(qū)個數(shù)下的K-means聚類結(jié)果

圖3 吳江出租起訖點(diǎn)在不同初始交通小區(qū)中心下的K-means聚類結(jié)果

2.3 FCM與K-means相結(jié)合的交通小區(qū)劃分

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

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

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

我們希望劃分的交通小區(qū)具有這樣的特性：在同一小區(qū)內(nèi)，交通特性應(yīng)有很強(qiáng)的相似性，即Rinner要??；同時，不同小區(qū)間的交通特性應(yīng)有足夠的差異性，即Router要大，因此“劃分系數(shù)”S越小，表征所對應(yīng)的劃分結(jié)果越優(yōu)秀。

根據(jù)交通小區(qū)劃分的相關(guān)文獻(xiàn)[6]、結(jié)合小區(qū)劃分的經(jīng)驗(yàn)常識，給定吳江區(qū)交通小區(qū)個數(shù)的待選范圍 2,1[ ] 0，利用FCM在不同的交通小區(qū)個數(shù)條件下進(jìn)行聚類，并利用“劃分系數(shù)”評價(jià)各聚類結(jié)果，得到圖4。

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

表1 FCM初步規(guī)劃6個交通小區(qū)中心位置

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

圖4 FCM聚類劃分系數(shù)隨交通小區(qū)個數(shù)變化圖

圖5 以FCM得到的小區(qū)中心初始化K-means聚類結(jié)果

將上述改進(jìn)算法與傳統(tǒng)的FCM及K-means進(jìn)行有效性對比，得到表2。由于傳統(tǒng)K-means聚類結(jié)果依隨機(jī)初始值的不同而變化，導(dǎo)致劃分系數(shù)相應(yīng)的波動，表中是多次聚類后的平均劃分系數(shù)。

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

可以看出，改進(jìn)算法對應(yīng)的劃分系數(shù)最小，意味著該劃分得到的交通小區(qū)內(nèi)具有相似的交通屬性，同時不同小區(qū)之間的交通差異性也相對明顯，因而是相對較優(yōu)的算法。

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

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

3 實(shí)例分析

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

圖6 根據(jù)起訖點(diǎn)周圍的道路屬性生成交通小區(qū)邊界

圖7 吳江交通小區(qū)劃分

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

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

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

表3 交通小區(qū)間OD矩陣

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

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

圖8 交通小區(qū)間OD弦圖

4 結(jié)束語

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

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

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

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

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

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

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

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

[6] 郭嶠楓.淺析交通小區(qū)劃分問題[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年工業(yè)轉(zhuǎn)型升級（中國制造2025）項(xiàng)目，項(xiàng)目編號：0714-EMTC02-5737/5。

劉彥斌（1986-），男，湖南株洲人，中電海康集團(tuán)研究院，車聯(lián)網(wǎng)技術(shù)總監(jiān)，碩士，研究方向：交通大數(shù)據(jù)、交通運(yùn)輸管理、交通流建模與仿真、交通系統(tǒng)分析。