交通小區的兩維圖論聚類

馮樹民，馬棟才

（哈爾濱工業大學交通科學與工程學院，150090哈爾濱）

交通小區的兩維圖論聚類

馮樹民，馬棟才

（哈爾濱工業大學交通科學與工程學院，150090哈爾濱）

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

交通工程；交通小區合并；兩維圖論聚類法；交通小區；位置關系

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

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

綜上，有關交通小區合并的研究相對較少且方法單一.其中人為地合并交通小區的做法主觀因素強、沒有統一標準，不同人的劃分結果也不盡相同；而基于模糊聚類分析的交通小區合并雖然克服了人為合并的缺點，使得合并過程更加科學，但模糊聚類法只能根據交通小區之間的相似性聚類（合并），而無法識別交通小區之間的位置關系（空間鄰接性），其應用也存在著一定的不足：在聚類的過程中會將一些不相鄰的交通小區合并，這樣的結果在實際應用中顯然不合理，如文獻［4］中在結果選取時還得人為地將不相鄰的小區分開.因此，同時考慮位置關系與相似性的交通小區合并值得重點研究.

1 交通小區位置關系分析

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

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

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

3）只有同時滿足以上兩個條件的兩個交通小區才算相鄰.

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

2 兩維圖論聚類法

2.1 兩維圖論聚類法的原理及優勢

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

在傳統圖論聚類算法的基礎上，同時考慮聚類對象之間的相似性與空間鄰接性形成兩維圖論聚類算法.與一般的圖論聚類算法相比，兩維圖論聚類算法的主要區別在于無向加權圖的構造：只有相鄰的對象才連接，而一般圖論聚類法不考慮聚類對象的空間鄰接性.此時，基于聚類對象空間鄰接性及其相似性的無向加權圖也是一個加權連通圖［13］.因此，兩維圖論聚類法在涉及位置關系的聚類問題中明顯優于一般聚類方法.如根據圖1中4個交通小區之間的位置關系，可構造如圖2所示的無向加權圖.

圖1 交通小區劃分圖

圖2 小區加權無向圖

2.2 聚類指標及處理

影響交通小區劃分的重要因素是用地性質的差異，例如居民區早晚高峰由于工作、上學等出行活動將會有較大的出行量，商業區具有很強的交通吸引力［14］，居民區與商業區呈現出的交通特性取決于用地性質.因此，交通小區合并時以用地性質作為關鍵指標，保證被合并的交通小區在用地性質方面有較強的相似性，即交通特點相似.用地性質可分為居住用地、道路交通用地、工業用地、生態用地、倉儲用地、商業服務設施用地、公共管理與服務用地、公用設施用地；其次，由于交通小區劃分的重要目的就是將交通的產生、吸引與一定區域的社會經濟指標聯系起來分析其相關規律［8］，因此選取交通小區的經濟指標GDP反映其經濟情況；最后考慮各個交通小區的人口數量.于是，各個交通小區的用地性質、經濟指標、人口數量組成了交通小區的聚類指標體系.

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

2.3 連接邊的權值

交通小區合并過程中需要構造基于位置關系的無向加權圖，連接邊的權值用相似系數或歐氏距離表示.小區i與j之間的歐氏距離和相似系數分別為

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

2.4 合并結果的確定

應用兩維圖論聚類法選擇不同閾值進行交通小區合并，最終采用F檢驗法［16］確定最佳閾值.由原始數據矩陣可得所有聚類對象的中心為

假設聚類數為s，第j類含有nj個對象，則第j類樣本的聚類中心為

于是可構造F統計量為

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

交通小區合并生成中區的過程中，在最小（最大）支撐樹的基礎上選取閾值進行合并，計算合理分類結果對應的F值并進行顯著性檢驗，然后結合規劃層次的需求選取F值最大的合并結果.

2.5 交通小區合并的流程

基于以上分析，給出應用兩維圖論聚類法進行交通小區合并的流程，如圖3所示.

圖3 交通小區合并流程

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

3 實例分析

以東莞市南城區為例進行實例分析，介紹兩維圖論法在交通小區合并中的具體應用.初始交通小區劃分圖如圖4所示.

圖4 初始交通小區劃分圖

圖4中的數字代表14個分區，各個小區的聚類指標如表1所示.P為小區人口數；GDP為小區的生產總值，億元；R為居住用地面積，hm2；S為道路交通用地面積，hm2；G為生態用地面積，hm2；M為工業用地面積，hm2；W為物流倉儲用地面積，hm2；B為商業服務設施用地面積，hm2；A為公共管理與公共服務用地面積，hm2；U為公用設施用地面積，hm2.數據來源于東莞市軌道交通相關項目.

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

?

圖5 最小支撐樹

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

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

圖6 森林

表2 不同閾值下的合并結果

由于閾值為距離，表示的是交通小區之間的相似程度，被合并的小區之間的相似程度隨閾值的增大而減小.表2為F檢驗結果，可見：隨著閾值的增大，聚類數減少，被合并的小區增加；當閾值為0.647時，所有的小區被合并為一個；而且所有合并結果中均沒有出現不相鄰的交通小區合并的情況.當閾值≥0.005時，合并形成的小區過大，因而在最佳合并結果確定時不予考慮.為確定最佳閾值，采用式（10）編程計算閾值對應的F值，并給出α=0.05水平下的臨界值進行顯著性檢驗，結果見表3.

表3 F檢驗結果

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

本案例如應用文獻［1］采用的模糊聚類分析進行交通小區合并，結果如表4所示.

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

表4 模糊聚類方法合并結果

4 結 論

1）在交通小區合并生成交通中區的過程中應用兩維圖論聚類法，能夠有效克服現有方法無法識別交通小區位置關系的缺點，避免將不相鄰的小區合并，使得交通小區合并生成交通中區的過程更加科學，合并結果合理可行，為交通小區合并產生交通中區提供了理論依據.

2）通過計算不同分類對應的F值并進行F檢驗，可確定最大F值對應的最優合并結果，為最終小區合并結果的選取提供參考，克服人為選擇主觀因素強的缺點，將定量分析與定性分析的結果相結合，使得交通小區合并生成的交通中區更符合實際情況.

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

［1］宋亮.交通小區的理論分析和劃分方法研究［D］.西安：長安大學，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］李曉丹，楊曉光，陳華杰.城市道路網絡交通小區劃分方法研究［J］.計算機工程與應用，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］于慧杰.交通小區在交通規劃中若干技術問題的研究［D］.西安：西安電子科技大學，2008.

［9］楊波，劉海洲.基于聚類分析的交通小區劃分方法的改進［J］.交通與運輸：學術版，2007（1）：5-7.

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

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

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

［13］谷曉巖，李鳳英，張燕.兩維圖論聚類法在農業區劃中的應用：以山東省十七地市為例［J］.安徽農學通報：上半月刊，2009，15（3）：62-64.

［14］伍拾煤.密集城鎮群多層級軌道交通客流預測模型研究［D］.哈爾濱：哈爾濱工業大學，2014.

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

［16］王晟.模糊聚類算法的研究與實現［D］.南京：南京理工大學，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.

國家高技術研究發展計劃（2014AA110304）.

馮樹民（1973—），男，教授，博士生導師.

馬棟才，madongcai1990＠126.com.