交通小區(qū)的兩維圖論聚類

馮樹(shù)民，馬棟才

（哈爾濱工業(yè)大學(xué)交通科學(xué)與工程學(xué)院，150090哈爾濱）

交通小區(qū)的兩維圖論聚類

馮樹(shù)民，馬棟才

（哈爾濱工業(yè)大學(xué)交通科學(xué)與工程學(xué)院，150090哈爾濱）

為使得交通小區(qū)合并生成交通中區(qū)的過(guò)程更加合理，同時(shí)考慮交通小區(qū)之間的相似性和位置關(guān)系，將兩維圖論聚類法應(yīng)用于交通小區(qū)的合并.給定交通小區(qū)相鄰滿足的條件，并用鄰接矩陣表示交通小區(qū)之間的位置關(guān)系，構(gòu)造無(wú)向加權(quán)圖并求解最小支撐樹(shù)，根據(jù)最小支撐樹(shù)選取閾值進(jìn)行交通小區(qū)合并，最后用F檢驗(yàn)法確定理論上的最優(yōu)合并結(jié)果作為小區(qū)合并結(jié)果選取的參考.實(shí)例分析結(jié)果表明：聚類數(shù)隨閾值的增大而減少，而且合并過(guò)程中只有相似且相鄰的交通小區(qū)被合并，并采用F檢驗(yàn)法確定了唯一的最優(yōu)合并參考方案，劃分結(jié)果合理可行.

交通工程；交通小區(qū)合并；兩維圖論聚類法；交通小區(qū)；位置關(guān)系

在城市交通規(guī)劃中需要將規(guī)劃區(qū)域劃分為若干個(gè)交通區(qū)，根據(jù)不同的研究層次交通區(qū)可分為交通小區(qū)、交通中區(qū)和交通大區(qū)，其中交通小區(qū)是規(guī)劃研究中的最小區(qū)域單元.交通小區(qū)劃分應(yīng)遵循劃分原則并滿足交通需求預(yù)測(cè)的精度，同時(shí)應(yīng)盡量減少交通調(diào)查與數(shù)據(jù)分析的工作量.而交通小區(qū)合并是交通小區(qū)劃分的逆向過(guò)程，合并可生成用于交通需求預(yù)測(cè)等實(shí)際研究問(wèn)題的交通中區(qū)［1］.由此可見(jiàn)，交通小區(qū)的合并有著重要的實(shí)際意義，與交通小區(qū)的劃分同等重要.

對(duì)于交通小區(qū)的劃分，文獻(xiàn)［2］應(yīng)用空間句法理論中的深度值進(jìn)行交通小區(qū)劃分，得到了滿意的結(jié)果；文獻(xiàn)［3］在分析空間聚類分析算法的基礎(chǔ)上，建模并設(shè)計(jì)了交通小區(qū)劃分的流程和算法，實(shí)現(xiàn)了小區(qū)的自動(dòng)劃分；文獻(xiàn)［4］分析了出行距離的概率密度和概率分布，提出了基于出行距離的交通小區(qū)劃分方法；文獻(xiàn)［5］克服了傳統(tǒng)靜態(tài)交通小區(qū)劃分的缺點(diǎn)，提出了基于博弈論的動(dòng)態(tài)劃分法；文獻(xiàn)［6］引入圖的矩陣，提出了基于圖的譜理論的劃分法；文獻(xiàn)［7］利用移動(dòng)計(jì)費(fèi)數(shù)據(jù)進(jìn)行交通小區(qū)劃分，該方法具有覆蓋率高、成本低的優(yōu)點(diǎn).對(duì)于交通小區(qū)的合并，一般的做法是有經(jīng)驗(yàn)的規(guī)劃人員結(jié)合研究區(qū)域的實(shí)際情況，在交通規(guī)劃軟件TransCAD中將一些性質(zhì)相似的小區(qū)人為地合并.此外，由于交通小區(qū)的合并類似于聚類過(guò)程，也可通過(guò)聚類技術(shù)實(shí)現(xiàn)交通小區(qū)合并，文獻(xiàn)［8-11］應(yīng)用模糊聚類法，根據(jù)反映交通小區(qū)特性的土地利用指標(biāo)或經(jīng)濟(jì)指標(biāo)，將相似的小區(qū)合并.

綜上，有關(guān)交通小區(qū)合并的研究相對(duì)較少且方法單一.其中人為地合并交通小區(qū)的做法主觀因素強(qiáng)、沒(méi)有統(tǒng)一標(biāo)準(zhǔn)，不同人的劃分結(jié)果也不盡相同；而基于模糊聚類分析的交通小區(qū)合并雖然克服了人為合并的缺點(diǎn)，使得合并過(guò)程更加科學(xué)，但模糊聚類法只能根據(jù)交通小區(qū)之間的相似性聚類（合并），而無(wú)法識(shí)別交通小區(qū)之間的位置關(guān)系（空間鄰接性），其應(yīng)用也存在著一定的不足：在聚類的過(guò)程中會(huì)將一些不相鄰的交通小區(qū)合并，這樣的結(jié)果在實(shí)際應(yīng)用中顯然不合理，如文獻(xiàn)［4］中在結(jié)果選取時(shí)還得人為地將不相鄰的小區(qū)分開(kāi).因此，同時(shí)考慮位置關(guān)系與相似性的交通小區(qū)合并值得重點(diǎn)研究.

1 交通小區(qū)位置關(guān)系分析

在交通小區(qū)合并生成交通中區(qū)的過(guò)程中不僅要考慮小區(qū)之間的相似性，還要考慮其位置關(guān)系.因此，需要對(duì)交通小區(qū)之間的位置關(guān)系進(jìn)行必要的分析.交通小區(qū)之間的位置關(guān)系只有相鄰與不相鄰兩種.為明確交通小區(qū)之間的位置關(guān)系，給定交通小區(qū)相鄰必須滿足以下條件.

1）在初始交通小區(qū)劃分圖上，交通小區(qū)i與j在空間位置上相鄰.

2）交通小區(qū)i與j之間的分界線不是河川、鐵路等天然屏障，而是人為劃定的交通小區(qū)分界線.如果小區(qū)之間的分界線是天然屏障，即使空間位置上相鄰也不算相鄰.

3）只有同時(shí)滿足以上兩個(gè)條件的兩個(gè)交通小區(qū)才算相鄰.

為方便編程求解，根據(jù)交通小區(qū)劃分方案及相鄰條件，用對(duì)稱的鄰接矩陣L= lij[ ]n×n表示小區(qū)i與j之間的位置關(guān)系，L中的鄰接元素為

2 兩維圖論聚類法

2.1 兩維圖論聚類法的原理及優(yōu)勢(shì)

圖論聚類法是由 Zahn提出的，又稱為最大（小）支撐樹(shù)聚類算法.一般的圖論聚類算法中，無(wú)向加權(quán)圖中對(duì)象 i與 j之間的連接邊 eij的權(quán)值w（eij）定義為對(duì)象之間的相似程度，而相似程度可用歐氏距離或相似系數(shù)描述.歐氏距離越小（相似系數(shù)越大）表示對(duì)象之間相似程度越高，反之則越不相似.如果采用歐氏距離作為無(wú)向圖連接邊的權(quán)值，則構(gòu)造無(wú)向加權(quán)圖并求解最小支撐樹(shù)，移去最小支撐樹(shù)中大于閾值的邊形成森林，森林中連通的對(duì)象合并為一類.如果采用相似系數(shù)作為無(wú)向圖連接邊的權(quán)值，則構(gòu)造無(wú)向加權(quán)圖并求解最大支撐樹(shù)，移去最大支撐樹(shù)中小于閾值的邊形成森林，森林中連通的對(duì)象合并為一類［12］.

在傳統(tǒng)圖論聚類算法的基礎(chǔ)上，同時(shí)考慮聚類對(duì)象之間的相似性與空間鄰接性形成兩維圖論聚類算法.與一般的圖論聚類算法相比，兩維圖論聚類算法的主要區(qū)別在于無(wú)向加權(quán)圖的構(gòu)造：只有相鄰的對(duì)象才連接，而一般圖論聚類法不考慮聚類對(duì)象的空間鄰接性.此時(shí)，基于聚類對(duì)象空間鄰接性及其相似性的無(wú)向加權(quán)圖也是一個(gè)加權(quán)連通圖［13］.因此，兩維圖論聚類法在涉及位置關(guān)系的聚類問(wèn)題中明顯優(yōu)于一般聚類方法.如根據(jù)圖1中4個(gè)交通小區(qū)之間的位置關(guān)系，可構(gòu)造如圖2所示的無(wú)向加權(quán)圖.

圖1 交通小區(qū)劃分圖

圖2 小區(qū)加權(quán)無(wú)向圖

2.2 聚類指標(biāo)及處理

影響交通小區(qū)劃分的重要因素是用地性質(zhì)的差異，例如居民區(qū)早晚高峰由于工作、上學(xué)等出行活動(dòng)將會(huì)有較大的出行量，商業(yè)區(qū)具有很強(qiáng)的交通吸引力［14］，居民區(qū)與商業(yè)區(qū)呈現(xiàn)出的交通特性取決于用地性質(zhì).因此，交通小區(qū)合并時(shí)以用地性質(zhì)作為關(guān)鍵指標(biāo)，保證被合并的交通小區(qū)在用地性質(zhì)方面有較強(qiáng)的相似性，即交通特點(diǎn)相似.用地性質(zhì)可分為居住用地、道路交通用地、工業(yè)用地、生態(tài)用地、倉(cāng)儲(chǔ)用地、商業(yè)服務(wù)設(shè)施用地、公共管理與服務(wù)用地、公用設(shè)施用地；其次，由于交通小區(qū)劃分的重要目的就是將交通的產(chǎn)生、吸引與一定區(qū)域的社會(huì)經(jīng)濟(jì)指標(biāo)聯(lián)系起來(lái)分析其相關(guān)規(guī)律［8］，因此選取交通小區(qū)的經(jīng)濟(jì)指標(biāo)GDP反映其經(jīng)濟(jì)情況；最后考慮各個(gè)交通小區(qū)的人口數(shù)量.于是，各個(gè)交通小區(qū)的用地性質(zhì)、經(jīng)濟(jì)指標(biāo)、人口數(shù)量組成了交通小區(qū)的聚類指標(biāo)體系.

n個(gè)交通小區(qū)組成樣本集合X= {x1，x2…，xn}，如果交通小區(qū)i有m個(gè)反映其特性的指標(biāo)，則表示為 xi= {xi1，xi2，…，xim，}，i=1，2，…，n，n個(gè)交通小區(qū)構(gòu)成原始數(shù)據(jù)矩陣 xij[ ]n×m.由于不同特性具有不同的量綱，需要對(duì)原始數(shù)據(jù)進(jìn)行標(biāo)準(zhǔn)化處理來(lái)消除量綱的影響，一般采用標(biāo)準(zhǔn)差標(biāo)準(zhǔn)化.為了將標(biāo)準(zhǔn)化后的數(shù)據(jù)壓縮在［0，1］，再進(jìn)行極值標(biāo)準(zhǔn)化，即

2.3 連接邊的權(quán)值

交通小區(qū)合并過(guò)程中需要構(gòu)造基于位置關(guān)系的無(wú)向加權(quán)圖，連接邊的權(quán)值用相似系數(shù)或歐氏距離表示.小區(qū)i與j之間的歐氏距離和相似系數(shù)分別為

其中，歐氏距離一般適用于二維或三維空間的對(duì)象間相似性的度量［15］，歐氏距離和相似系數(shù)之間還可以相互轉(zhuǎn)換［16］，即

2.4 合并結(jié)果的確定

應(yīng)用兩維圖論聚類法選擇不同閾值進(jìn)行交通小區(qū)合并，最終采用F檢驗(yàn)法［16］確定最佳閾值.由原始數(shù)據(jù)矩陣可得所有聚類對(duì)象的中心為

假設(shè)聚類數(shù)為s，第j類含有nj個(gè)對(duì)象，則第j類樣本的聚類中心為

于是可構(gòu)造F統(tǒng)計(jì)量為

F統(tǒng)計(jì)量服從自由度為s-1、n-s的F分布，式（10）中分子表示不同類之間的距離，分母表示同一類樣本之間的距離.在一定的顯著水平α下，通過(guò)顯著性檢驗(yàn)且F值越大，說(shuō)明不同類對(duì)象之間的差異越大、同類對(duì)象之間的差異越小，即聚類效果越好.

交通小區(qū)合并生成中區(qū)的過(guò)程中，在最小（最大）支撐樹(shù)的基礎(chǔ)上選取閾值進(jìn)行合并，計(jì)算合理分類結(jié)果對(duì)應(yīng)的F值并進(jìn)行顯著性檢驗(yàn)，然后結(jié)合規(guī)劃層次的需求選取F值最大的合并結(jié)果.

2.5 交通小區(qū)合并的流程

基于以上分析，給出應(yīng)用兩維圖論聚類法進(jìn)行交通小區(qū)合并的流程，如圖3所示.

圖3 交通小區(qū)合并流程

其中，在根據(jù)交通小區(qū)劃分圖求鄰接矩陣時(shí)，為避免面積較大的交通小區(qū)直接合并形成過(guò)大的交通中區(qū)，可結(jié)合交通小區(qū)劃分情況，將面積較大的小區(qū)之間的鄰接元素lij賦值為0，使得面積較小，相鄰且相似的交通小區(qū)先被合并，從而得到大小適宜的交通中區(qū).

3 實(shí)例分析

以東莞市南城區(qū)為例進(jìn)行實(shí)例分析，介紹兩維圖論法在交通小區(qū)合并中的具體應(yīng)用.初始交通小區(qū)劃分圖如圖4所示.

圖4 初始交通小區(qū)劃分圖

圖4中的數(shù)字代表14個(gè)分區(qū)，各個(gè)小區(qū)的聚類指標(biāo)如表1所示.P為小區(qū)人口數(shù)；GDP為小區(qū)的生產(chǎn)總值，億元；R為居住用地面積，hm2；S為道路交通用地面積，hm2；G為生態(tài)用地面積，hm2；M為工業(yè)用地面積，hm2；W為物流倉(cāng)儲(chǔ)用地面積，hm2；B為商業(yè)服務(wù)設(shè)施用地面積，hm2；A為公共管理與公共服務(wù)用地面積，hm2；U為公用設(shè)施用地面積，hm2.數(shù)據(jù)來(lái)源于東莞市軌道交通相關(guān)項(xiàng)目.

從表1及圖4中可以看出，交通小區(qū)7、8、10、12、13的面積明顯大于其他交通小區(qū)，為避免這5個(gè)小區(qū)兩兩直接合并形成過(guò)大的交通中區(qū)，可令這5個(gè)小區(qū)兩兩之間的鄰接元素為0，然后根據(jù)式（1）及圖4得鄰接矩陣L.表1中各項(xiàng)指標(biāo)單位不統(tǒng)一，首先進(jìn)行標(biāo)準(zhǔn)差標(biāo)準(zhǔn)化，然后采用式（2）將數(shù)據(jù)壓縮到［0，1］.由于聚類指標(biāo)數(shù)大于3，因此選擇用相似系數(shù)式（4）描述小區(qū)之間的相似性.為了便于利用MATLAB中求解最小支撐樹(shù)的graphminspantree函數(shù)編程實(shí)現(xiàn)交通小區(qū)的合并，采用式（5）將相似系數(shù)轉(zhuǎn)化為距離，得到權(quán)值矩陣W（對(duì)稱矩陣）如下，最小支撐樹(shù)如圖5所示.

?

圖5 最小支撐樹(shù)

MATLAB編程獲得最小支撐樹(shù)中所有互不相同的權(quán)值，將這些權(quán)值作為閾值并對(duì)其排序如下：0.001、0.003、0.004、0.005、0.009、0.595、0.636、0.639、0.647.當(dāng)選擇閾值為0.001時(shí)，移去最小支撐樹(shù)（見(jiàn)圖5）中權(quán)值大于0.001的邊形成森林，如圖6所示.

由圖6可知，交通小區(qū)3、4、5連通，交通小區(qū)8、9連通，根據(jù)兩維圖論聚類原理，交通小區(qū)3、4、5被合并，交通小區(qū)8、9被合并，分別形成集合｛3，4，5｝、｛8，9｝，每個(gè)集合代表一個(gè)新區(qū).選擇其余的閾值進(jìn)行交通小區(qū)合并，結(jié)果如表2所示.

圖6 森林

表2 不同閾值下的合并結(jié)果

由于閾值為距離，表示的是交通小區(qū)之間的相似程度，被合并的小區(qū)之間的相似程度隨閾值的增大而減小.表2為F檢驗(yàn)結(jié)果，可見(jiàn)：隨著閾值的增大，聚類數(shù)減少，被合并的小區(qū)增加；當(dāng)閾值為0.647時(shí)，所有的小區(qū)被合并為一個(gè)；而且所有合并結(jié)果中均沒(méi)有出現(xiàn)不相鄰的交通小區(qū)合并的情況.當(dāng)閾值≥0.005時(shí)，合并形成的小區(qū)過(guò)大，因而在最佳合并結(jié)果確定時(shí)不予考慮.為確定最佳閾值，采用式（10）編程計(jì)算閾值對(duì)應(yīng)的F值，并給出α=0.05水平下的臨界值進(jìn)行顯著性檢驗(yàn)，結(jié)果見(jiàn)表3.

表3 F檢驗(yàn)結(jié)果

從表3中可以看出，F(xiàn)值均大于臨界值且0.001對(duì)應(yīng)的F值最大，因此最佳閾值為0.001，原來(lái)的14個(gè)交通小區(qū)合并為11個(gè).此外，從權(quán)值矩陣W中可以看出，小區(qū)12與13（7與8；10與12）相鄰且距離為0，表明這兩個(gè)小區(qū)極其相似，可看作一個(gè)小區(qū).但這兩個(gè)小區(qū)的面積均明顯大于其余小區(qū)，合并后再與其余小區(qū)合并將使得合并生成的中區(qū)面積過(guò)大.本案例中通過(guò)鄰接矩陣，有效限制了面積較大的交通小區(qū)直接合并，避免形成過(guò)大的交通中區(qū).

本案例如應(yīng)用文獻(xiàn)［1］采用的模糊聚類分析進(jìn)行交通小區(qū)合并，結(jié)果如表4所示.

由表4可知，當(dāng)閾值為0.999 575時(shí)，交通小區(qū)4、7、8、9、10、11、12、13被合并，而在初始交通小區(qū)劃分圖中（圖4）交通小區(qū)4與其他幾個(gè)小區(qū)均不相鄰.當(dāng)閾值分別為0.999 628、0.999 651、0.999 665、0.999 699、0.999 887、0.999 936時(shí)也出現(xiàn)類似的情況，這樣的合并結(jié)果顯然不合理，原因在于模糊聚類法沒(méi)有考慮交通小區(qū)之間的鄰接關(guān)系.由于兩維圖論聚類法是基于交通小區(qū)的空間鄰接性與相似性進(jìn)行合并，表2所示的合并結(jié)果中均不會(huì)出現(xiàn)不合理的合并結(jié)果.

表4 模糊聚類方法合并結(jié)果

4 結(jié) 論

1）在交通小區(qū)合并生成交通中區(qū)的過(guò)程中應(yīng)用兩維圖論聚類法，能夠有效克服現(xiàn)有方法無(wú)法識(shí)別交通小區(qū)位置關(guān)系的缺點(diǎn)，避免將不相鄰的小區(qū)合并，使得交通小區(qū)合并生成交通中區(qū)的過(guò)程更加科學(xué)，合并結(jié)果合理可行，為交通小區(qū)合并產(chǎn)生交通中區(qū)提供了理論依據(jù).

2）通過(guò)計(jì)算不同分類對(duì)應(yīng)的F值并進(jìn)行F檢驗(yàn)，可確定最大F值對(duì)應(yīng)的最優(yōu)合并結(jié)果，為最終小區(qū)合并結(jié)果的選取提供參考，克服人為選擇主觀因素強(qiáng)的缺點(diǎn)，將定量分析與定性分析的結(jié)果相結(jié)合，使得交通小區(qū)合并生成的交通中區(qū)更符合實(shí)際情況.

3）兩維圖論聚類法不僅適用于交通小區(qū)合并生成交通中區(qū)，還適用于交通中區(qū)合并生成交通大區(qū)的工作.

［1］宋亮.交通小區(qū)的理論分析和劃分方法研究［D］.西安：長(zhǎng)安大學(xué)，2011.

［2］ XUE Y，DUAN Z Y.An accessibility oriented traffic analysis zone division method［C］／／2010 2nd International Asia Conference on Informatics in Control，Automation and Robotics.Wuhan：IEEE Computer Society，2010：516-519.

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

［4］WU S M，CHENG G Z，PEI Y L.Model of traffic zone division based on trip distance［J］.Applied Mechanics and Materials，2013，409-410：1184-1187.

［5］LIU H Q，YANG L C，ZHANG Y，et al.A dynamic traffic zone division scheme based on game theory［J］.Journal of Information and Computational Science，2013，10（10）：2961-2969.

［6］WU S M，PEI Y L，CHENG G Z.Method of traffic zone division based on spectral graph theory［J］.Computer Modelling and New Technologies，2014，18（2）：186-191.

［7］XING X X，HUANG H W，SONG G J，et al.Traffic zone division using mobile billing data［C］／／2014 11th International Conference on Fuzzy Systems and Knowledge Discovery.Xiamen：Institute of Electrical and Electronics Engineers Inc，2014：692-697.

［8］于慧杰.交通小區(qū)在交通規(guī)劃中若干技術(shù)問(wèn)題的研究［D］.西安：西安電子科技大學(xué)，2008.

［9］楊波，劉海洲.基于聚類分析的交通小區(qū)劃分方法的改進(jìn)［J］.交通與運(yùn)輸：學(xué)術(shù)版，2007（1）：5-7.

［10］桂小玲，靳文舟，胡郁蔥.模糊聚類分析方法及其在交通規(guī)劃中的應(yīng)用［J］.交通與計(jì)算機(jī)，2005，23（2）：80-83.

［11］劉乙霏.基于模糊聚類的交通小區(qū)劃分方法研究［J］.物流科技，2011（9）：25-28.

［12］高興波.模糊聚類分析及其應(yīng)用［M］.西安：西安電子科技大學(xué)出版社，2004，37-48.

［13］谷曉巖，李鳳英，張燕.兩維圖論聚類法在農(nóng)業(yè)區(qū)劃中的應(yīng)用：以山東省十七地市為例［J］.安徽農(nóng)學(xué)通報(bào)：上半月刊，2009，15（3）：62-64.

［14］伍拾煤.密集城鎮(zhèn)群多層級(jí)軌道交通客流預(yù)測(cè)模型研究［D］.哈爾濱：哈爾濱工業(yè)大學(xué)，2014.

［15］唐東明.聚類分析及其應(yīng)用研究［D］.成都：電子科技大學(xué)，2010.

［16］王晟.模糊聚類算法的研究與實(shí)現(xiàn)［D］.南京：南京理工大學(xué)，2006.

（編輯 魏希柱）

Two-dimensional graphic theory on clustering method of small traffic zones

FENG Shumin，MA Dongcai

（School of Transportation Science and Engineering，Harbin Institute of Technology，150090 Harbin，China）

In order to make the process of generating small traffic zones into middle traffic zones more reasonable and taking the similarity and the positional relation of small traffic zones into consideration，two-dimensional graphic theory-clustering method on the mergence of small traffic zone is applied.Given conditions that satisfied the adjacent small traffic zones，the positional relation of small traffic zones by the adjacent matrix is re-formulated.After the undirected weighted graph construction，the minimum spanning tree（MST）was solved.Choose the threshold according to the MST for the small traffic zones mergence.Finally the F-test is used to determine the optimal mergence in theory which is the reference of the selection of the small traffic zone mergence.The result of example analysis shows that the clustering number reduces along with the increase of the threshold value，and only the similar and adjacent small traffic zones can be merged during the mergence.In addition，the F-test is adopted to determine the exclusive optimal scheme of mergence for reference，which proved that the division result was feasible.

traffic engineering；small traffic zone mergence；two-dimensional graphic theory on clustering method；small traffic zone；positional relationship

U491

A

0367-6234（2015）09-0057-06

10.11918／j.issn.0367-6234.2015.09.011

2015-06-09.

國(guó)家高技術(shù)研究發(fā)展計(jì)劃（2014AA110304）.

馮樹(shù)民（1973—），男，教授，博士生導(dǎo)師.

馬棟才，madongcai1990＠126.com.