報告論文

近傍グラフによるOD交通量データの視覚表現

近傍グラフは，データ間の類似度や近接性を解析し，そのデータ構造を視覚化する手法として注目され，多くの分野で活用されている．しかし，地域の近接性を記録するデータの一つであるOD交通量データを用
いて近傍グラフを構築し，そこから明らかになる地域構造を視覚表現しようとする試みは，
これまでのところ見られない．本報告は近傍グラフに着目し，主要な発着地域の組み合わせの抽出を行い，その結果を視覚表現する新たな手法を提案する．最後に，全国幹線旅客純流動調査データを用いた分析を通して，提案手法の適用可能性を検証する．
キーワード

清水英範

近傍グラフ，OD交通量データ，視覚化，地域構造

工博 東京大学大学院工学系研究科教授

SHIMIZU, Eihan

井上

亮

博
（工）東北大学大学院情報科学研究科准教授

INOUE, Ryo

1──はじめに近傍グラフとは，距離空間上の点集合について，点間距

では抽出結果を地図上に表現する方法について検討を行い，4章で全国幹線旅客純流動調査データを用いた提案手法の適用結果を示す．

離を用いて近傍点の組み合わせを抽出し，点集合の空間
分布特性を表現するグラフである．
近年，近傍グラフは，物理的な距離空間上の点集合に限らず，データの属性に基づいて定義された特徴空間上2──近傍グラフによる主要OD交通量データの抽出の点集合に対して適用された例も数多く見られる．例え・本章では，代表的な近傍グラフである最小全域木 4）–6）ば，高次元の細胞特性データを利用した細胞の階層性抽・ガブリエルグラフ 8）を応用した，主要相対近傍グラフ 7）

出 1）や，遺伝子機能解析データのクラスタリング 2），高次元

OD交通量データの抽出について検討する．

データのデータベースに対する索引付け 3）など様々な分

まず，近傍グラフの応用に際し，OD交通量の多寡に基析へ応用されており，
データ間の類似度や近接性の解析，

づいて地域間の近接性を定義する．ここでは，地域ij間

データ構造の視覚表現に広く活用されている．しかし，地の近接性指標pij を，両方向のOD交通量の和tij＋tji の逆域（ゾーン）
間の近接性を記録するデータの一つであるOD（tij＋tji）
で設定することを考えよう．交通量が大数pij＝1/

交通量データを用いて近傍グラフを構築し，そこから明らきい地域間ほど小さい近接性指標値を取り，近傍にあるかになる地域構造を視覚表現する試みは，筆者らの知ると見なされる．この近接性指標が与えられた点集合に対限り存在しない．

して近傍グラフ作成を適用すると，交通量の多い地域間

本稿では近傍グラフに着目し，これを用いたOD交通量

を結ぶ辺を抽出することが可能であると期待される．

データの視覚表現について報告する．なお本報告では，

しかし，
このOD交通量データから定義される地域間近

地図上に地域を表す点を配置し，主要なOD交通量デー

接性指標は，
一般に距離の公理を満たさない．前述のよタをその発着地域を表す2点を直線の辺で結んで示す単うに，近傍グラフは，距離空間上に配置された点に対し純な表現を考える．一般にOD交通量データは非対称だて近傍点の組み合わせを抽出する方法であり，これまでが，表現する地域の組み合わせを近傍グラフを用いて抽の適用では，点間の関係は距離で与えられたデータを出する際は，双方向の交通量の合計を用いて評価する．

扱っている．また，通常，ユークリッド空間上で近傍を定義

非対称性を表現する場合は，主な移動方向を辺に矢印するガブリエルグラフを，他の一般的な距離空間へ拡張を付加して表し，また，交通量の多寡を表す場合は，辺のする研究 9）も行われているものの，距離の公理を満たさ

太さや色で対応する．

ない近接性指標に対し近傍グラフ作成を行う例は，筆者

この視覚表現の実現に向けて，2章では近傍グラフを用いた主要OD交通量データの抽出方法について，3章

報告論文

らの知る限りでは存在しない．
そこで，最小全域木・相対近傍グラフ・ガブリエルグラ

Vol.16 No.3 2013 Autumn 運輸政策研究023

フに関して，ユークリッド空間上の点集合に対する作成手配置に依存して定められる．なお，全域木の定義から，抽法を示した上で，上記の近接性指標が与えられた点集合

出される辺の数は頂点数−1となる．

に対して近傍グラフ作成手法を適用した際に得られるグ

さて，最小全域木作成手法を，OD交通量に基づく地域

ラフの特徴を確認し，主要OD交通量データの抽出に対間の近接性指標が与えられた点集合に対して適用する

する近傍グラフの適用可能性を検討する．

と，近接性指標の定義，および，プリム法のアルゴリズム
より，OD交通量の総和が最大となる全域木が得られることが分かる．このグラフでは，それぞれの地域から交通

2.1 最小全域木

全域木とは，グラフの全点と一部の辺からなる連結か量が最も大きい地域への辺が必ず抽出されるため，地域

つ閉路のないグラフであり，最小全域木とは，全域木の中間の結びつきを表現できる．しかし，各地域からの交通

で辺長の和が最小のグラフである．図─1の関東地方の量最大の辺だけでは全域木が構成できない場合，複数の県庁所在地配置に対して最小全域木を作成すると，図─2

木を接続するため，OD交通量データ全体を見たときにはが得られる．

決して重要とは言えない地域の組み合わせが抽出される

この作成手法は多く提案されており，貪欲法の一種で可能性があることには注意を要する．

あるプリム法 4）やクラスカル法 5）が有名である 6）．ここで，以下にプリム法のアルゴリズムを示す．

2.2 相対近傍グラフ（a）点集合Vと辺集合Eを空集合とする．

相対近傍グラフ 7）とは，任意i・jの組合せについて，点i（b）
任意の点uを選択し，Vに追加する．

とjを中心に点ij間の距離dij を半径とした円を描き，両円（c）Vに全点が含まれるまで「V内の点uとV外の点vを結の重複領域に他点が存在しない場合に点i・jが近傍にあぶ距離が最小の頂点の組合せ（u，v）
を選び，
その頂

ると定義し，辺ijを辺集合Eに加えたグラフである．相対点u，vを結ぶ辺をEに追加し，vをVに追加する」操作

近傍グラフ作成の辺ijの抽出条件（図─3（a）
）
は，式
（1）
で

を繰り返す．

表される．

（d）
Vが全点を含む時，
グラフ（V，E）
が最小全域木となる．

（1）

プリム法で最小全域木が作成できることから明らかな

相対近傍グラフでは，最小全域木の場合とは異なり，点i，jように，各点に繋がる最短辺長の辺は必ず抽出される．しの近隣の局所的な点配置だけから，辺ijが抽出されるか

かし，各点に繋がる2番目以降に短い辺が選ばれるか否否かを判断することができる．

かは，その点近傍の配置だけでは定められず，全体の点

なお，距離空間上では，相対近傍グラフは最小全域木（b）は，図─1のを包含することが知られている 10）．図─3

宇都宮

点配置に対する相対近傍グラフ作成結果を表し，図中の前橋

水戸

青色の辺は最小全域木（図─2）に対して追加された辺を示す．
さて，相対近傍グラフの辺抽出条件
（式
（1）
）
を近接性指
標に適用すると式（2）が得られる．

さいたま

（2）

東京
千葉
横浜

■図―1

ここで近接性指標をOD交通量データで表現すると式（3）が得られる．
（3）

点配置の例（関東地方 県庁所在地）

kij（a）近傍の定義■図―2024

最小全域木 作成例

運輸政策研究Vol.16 No.3 2013 Autumn■図―3（b）作成例

相対近傍グラフ

報告論文

式
（3）
より，相対近傍グラフ作成で辺ijが抽出される場合，ることになるため，
より多くの辺が抽出される．このように

地域ij間の交通量よりも，地域i，jの双方に対して交通量

式（5）は，乗数パラメータ α の設定によって，抽出辺の数をが多い地域kが存在しないことを意味する．すなわち，相自在に調整することができる辺抽出となる．この式（5）に対近傍グラフを援用してOD交通量データを抽出する場

よって抽出される辺は，相対近傍グラフの抽出辺を包含合，相対的に交通量の多い強い地域ijの組み合わせが抽することは容易に確認できる．
なお，距離空間上の点集合に対して式（5）を適用する

出されることになる．
また，ユークリッド空間上の点集合の場合と同様，近接場合には，距離の公理よりα≦1では全ての辺が選択さ性指標に基づく相対近傍グラフの辺抽出結果も，最小全れてしまう．しかし，距離の公理が成り立たない近接性指域木の結果を包含することが確認できる．

標に対して適用する場合は α＜1と設定しても全ての辺が選ばれるとは限らない．
ここで式（5）を基に，OD交通量データを用いて，式（3）2.3 ガブリエルグラフ

ガブリエルグラフ 8）は，任意の点i・jの組合せについて，
辺ijを直径とする円が空円である場合に点i・jが近傍にの相対近傍グラフによる抽出辺を包含する結果を得る式
を記述すると，式（6）と表すことができる．

あると定義し，辺ijを辺集合Eに加えたグラフである．空（6）円条件（図─4（a））
は，ユークリッド空間上では式（4）
と表

ただし，式
（6）
による近傍の定義は，最小全域木や相対近すことができる．

傍グラフによる近傍の定義に比べて不明快であるため，（4）

相対近傍グラフと同様に，ガブリエルグラフも，局所的抽出されたOD交通量データの意味解釈には限界があることに注意が必要である．

な点配置だけから，各辺が抽出されるか否かが判断される．また，ユークリッド空間上の点配置に対して作成され

2.4 まとめたガブリエルグラフが相対近傍グラフを包含することは，

以上のように，OD交通量を用いて定義した地域間の

式（1）
（4）
の比較から明らかである．図─4（b）は，図─3

近接性指標に対して近傍グラフ作成を応用することによの点配置に対するガブリエルグラフ作成結果を表し，
青り，主要なOD交通量データを抽出することができること

色の辺は，相対近傍グラフ（図─3（b））に加えて抽出されが確認された．
また，ユークリッド空間上の点集合に対する近傍グラフている辺を示す．
さて，ガブリエルグラフの辺抽出条件
（式
（4）
）
を近接性

の包含関係は，近接性指標に対する近傍グラフ作成でも指標に適用することを考えよう．ユークリッド空間上にお同様に成立することが確認できる．最小全域木・相対近ける辺抽出の場合，空円条件を意味する距離の2乗値を傍グラフ・ガブリエルグラフが包含関係にあることを利用

用いて辺を抽出するか否かを判断することになるが，近接すると，近傍グラフ作成の応用により，OD交通量データ性指標を用いた辺抽出の場合は，近接性指標の2乗値はを段階的に抽出することが可能である．また，ガブリエル

意味を有していない．そこで，近接性指標の2乗値にはこグラフへの乗数パラメータの導入によって，相対近傍グラ

だわらず，
より柔軟に点の近傍関係を定義することを検討

フによる抽出辺に対して，追加する抽出辺の数を細かく（5）を用いた辺抽出をし，乗数パラメータα を導入した式

設定することも可能である．

提案する．

ただし，
いずれの近傍グラフ作成手法を基にした手法
（5）

式
（5）
では，α を小さくすると近傍の判断条件を緩和すでも，抽出される辺の意味解釈は難しい場合があることには注意が必要である．

3──抽出結果の視覚表現
本章では，近傍グラフ作成手法によって抽出された主ki

要OD交通量データの視覚表現について検討する．
まず，地域を代表する点を，例えば地域の地理的重心

j位置などの地理的位置関係に基づき2次元平面上に配置し，抽出されたOD交通量データを表現するような点を（a）近傍の定義
■図―4

報告論文

ガブリエルグラフ（b）作成例

結ぶ直線の辺を引くことを考える．しかし，
この単純な辺の配置ルールでは，図上の点や辺が近接して配置され，Vol.16 No.3 2013 Autumn 運輸政策研究025

表現されている地域構造の把握が難しい図が得られると仮定した時の，点と辺の両端点の間の距離と方位角（図─可能性があることが容易に推察される．そのため，図上7の二重線）
を計算し更新する．なお，問題箇所以外につの点配置を調整して点の辺への近接を緩和し，可読性をいては，現配置の点間距離・方位角を設定する．

向上させる必要がある．

次に，この新たな点間距離・方位角情報をカルトグラム

点や辺の接続関係を読み取りやすい配置を求める問作成手法に入力し，点・辺の再配置を行う．カルトグラム

題に関しては，
これまでに多くの検討がなされており11），12），

作成手法は，入力されたすべての点間距離・方位角情報

点と点
（図─5）
や点と辺
（図─6）
の近接を緩和する配置をの再現を目指すが，多くの場合，入力された情報を完全に得る手法が提案されている 13）．これらの既往研究では，達成する配置を得ることはできない．そのため，すべてのWebのリンク構造 11），12）など地理的位置と関連がない情近接問題を解消することは必ずしもできないが，再配置前

報の表現を目指しており，
一般に，点配置は自由に定めらに比べると点・辺の近接は緩和することができる．また，れることを前提としている．

局所的な対応と異なり，提案解法ではすべての点・辺のしかし，OD交通量データは，発地・着地という地理的な位置に関連付けられた地理空間情報である．地理空間情報を表現する図を閲覧する時，読図者は通常，地域

配置が同時に更新されるため，新たな点・辺の近接が生じる可能性は小さい．
その後，新たに得られた配置に対して，近接判定の閾の地理的配置を念頭に置き，図上の点と地域の対応関係を確認する．そのため，図上の点配置が地域の地理的地
域配置と大きく異なると，図の可読性は大きく損なわれる．
そのため，地理的配置を保持した点配置の決定がOD交通量データの視覚表現には極めて重要となる．
本稿では，近傍グラフによる主要OD交通量データの抽出結果を，地理的配置に従って点と辺の初期配置を定めた上で，点と辺の近接を緩和する方法を検討する．なお，
点と点の近接については，各地域の代表点の初期配置に関する設定で解決することができるため，本稿では検討■図―5

点と点の近接の緩和■図―6

点と辺の近接の緩和の対象とはしない．
点と辺の近接を局所的に緩和する方法は様々考え得るだろう．しかし，ある特定の点・辺間の近接を緩和するために，例えば，点を辺から離す方向に移動させると，点の移動先で，他の辺との新たな近接問題を引き起こす可能性が存在する．そのため，局所的対応の繰り返しで点・辺の近接問題全体を改善することは難しい．そこで，所与の点間距離・方位角を可能な限り再現する点配置を同時に求めることができるカルトグラム作成手法 14）を用いた
点・辺近接問題の解法を提案する．
提案解法の手順は以下の通りである．
まず，点・辺近接判定の閾値を設定し，入力された点・辺配置に近接問題が存在するか否かを検索する．なお，
点・辺の近接の緩和を目指して配置を一度に大幅に変更

distance（v，e）<dthreshold

すると，他の点や辺の配置に悪影響を与える可能性がある．そこで近接判定の閾値には，最初は微小な値を設定

辺e

し，点間の最短距離を上限に徐々に増加させながら，以下の点・辺の再配置手順を繰り返し実行する．
もし，設定した閾値に対して，点・辺の近接問題の存在

頂点vが確認されたら，問題箇所の点と辺の両端点に関して，点間距離・方位角を更新する（図─7）．点・辺間距離を閾値まで離すように点を移動（図─7の黒点から白点）
させた
026

運輸政策研究Vol.16 No.3 2013 Autumn■図―7

点と辺の近接緩和に向けた辺長と方位角の更新

報告論文

値を増加させて同様の操作を繰り返す．閾値が増加する

4──全国幹線旅客純流動調査データへの適用と考慮すべき点・辺の組み合わせが増加し，再配置を行っても点・辺が密集する場所では問題が改善しない可

平成25年3月に公開された，
平成22年度実施・第5回全能性がある．そこで，閾値の上限まで再配置計算を繰り

国幹線旅客純流動調査の平日・休日を合計した年間，全返すものの，計算過程において得られた点・辺間の最小旅行目的・全代表交通機関の都道府県間幹線旅客純流距離が最大となる配置を出力する．

動データを用いて，提案手法の適用可能性を確認する．

図─8に本章で提案する解法のフローチャートを示す．

なお，集計単位の基本は都道府県だが，
首都圏
（東京・

この手順を経ると，グラフ上の点と辺の近接した配置を緩

神奈川・千葉・埼玉）
・中京圏（愛知・岐阜・三重）・近畿圏

和し，表現されている地域構造の把握が容易なグラフを（大阪・京都・兵庫・奈良）
はそれぞれ一地域に集約され，作成することが可能になる．

北海道は道北・道東・道央・道南の四地域に分割されて次章では，提案したOD交通量データ視覚化手法の適用可能性を検証する．

いる．結果として，総地域数は42となり，全地域間を繋ぐ
完全グラフを作成すると辺数は861となる．

点集合V（点v の座標xv，yv），
辺集合E（辺e の端点ev1，ev2），#_iterationを入力

点の座標，辺の端点，および，繰り返し計算回数を入力

edge_length（E，V ）→Elength
edge_bearing（E，V ）→Ebearing

辺の端点と点の座標を用いて，全辺の辺長・方位角を計算
初期配置上の点・辺間の最短距離を記録，点間の最短距離を点・辺近接問題検出の閾値の最大値に設定

min_distance（E，V ）→max_dmin
min_vertex_distance（V ）→dmax_threshold
1→i

繰り返し計算のカウンタを初期化
繰り返し計算で使用する
近接検出の閾値を設定

dmax_threshold×i / #_iteration→dthreshold
v=Vfirst，Vlast，1
e=Efirst，Elast，1

distance（e，v）<dthresholdNO

点・辺近接問題を検索

YES問題が検出されたら，点と辺の端点を結ぶ辺の長さと方位角を調整

edge（ev1，v），edge（ev2，v）に関してElength，Ebearingを更新

ev

カルトグラム作成手法にElength・Ebearingを入力しV（点v の座標xv，yv）を更新

min_distance（E，V ）>max_dminカルトグラム作成手法を用いて全ての点の座標を同時に更新

NO

点座標の更新によって近接問題が緩和されたことを確認

YES
V→Vbest

i＋1→i
NO

YES

報告論文

繰り返し計算のカウンタを更新

i>#_iteration

Vbest出力■図―8近接問題が緩和されれば
点座標を出力用データに記録

繰り返し計算の中で，点・辺間の最短距離が最大となった時の点配置を出力

抽出結果の視覚表現に関するフローチャート

Vol.16 No.3 2013 Autumn 運輸政策研究

027

道央

道央

宮城県
宮城県

近畿圏

首都圏

近畿圏
首都圏

福岡県

福岡県

中京圏

中京圏

沖縄県

沖縄県

（a）地理的配置■図―9（b）点と辺の近接緩和

最小全域木

道央
道央

宮城県
宮城県

近畿圏

近畿圏

首都圏
福岡県

首都圏
福岡県

中京圏

中京圏
沖縄県
沖縄県
（a）地理的配置■図―10（b）点と辺の近接緩和

相対近傍グラフ図─9は最小全域木，図─10は相対近傍グラフ，図─11■表―1

各近傍グラフによるOD交通量データ表現
最小

相対近傍

ガブリエルグラフ

全域木

グラフ

α＝2

表現辺数

41辺

45辺

48辺

59辺

表現交通量

65.1％

68.8％

69.4％

78.7％

は α＝2と設定したガブリエルグラフ，図─12は α＝1と設定したガブリエルグラフの結果を示す．各図の（a）は，県庁所在地など地域の代表点を地理的座標に従い配置しα＝1て，近傍グラフによって抽出された辺を描いたグラフ，（b）は，点・辺の近接を緩和するよう点配置を改め，抽出された辺を描いたグラフである．辺の矢印は，総発生・集中割合を，表─1に示す．
以下に，それぞれの視覚表現結果に関する考察を記す．

交通量の小さい地域から大きい地域に向けて描いている．なお，沖縄を表す点は図右下に配置している．図上での表現辺数と，全OD交通量に対する表現OD交通量の028

運輸政策研究Vol.16 No.3 2013 Autumn（図─9）4.1 最小全域木

最小全域木は，完全グラフの辺数861に対し5％弱の

報告論文

道央

道央

宮城県

宮城県

近畿圏

近畿圏

首都圏

首都圏
福岡県

福岡県
中京圏

中京圏

沖縄県
沖縄県
（b）点と辺の近接緩和（a）地理的配置
■図―11

（α＝2）
ガブリエルグラフ

道央

道央

宮城県

宮城県

近畿圏

近畿圏

首都圏

首都圏
福岡県

福岡県

中京圏

中京圏
沖縄県

沖縄県

（a）地理的配置■図―12（b）点と辺の近接緩和（α＝1）
ガブリエルグラフ

41辺で全体の65.1％の交通量を表現する．都道府県間
幹線旅客純流動データについては，最小全域木は主要
OD交通量データを表現できているといえる．

置されると，読図が困難になる可能性がある．
そこで，点・辺の近接を緩和した図─9（b）を確認する．
首都・近畿圏を結ぶ辺や，
首都圏・道央を結ぶ辺に着目

首都・中京・近畿圏を表す3点に着目すると，地理的配すると明らかなように，点・辺の近接が解消し，誤った読図

置上に辺を描いた図─9（a）
では，
首都・近畿圏を結ぶ辺の可能性を軽減させる表現がなされている．近接緩和をに近接して中京圏の点が位置しているため，中京圏が首行ったグラフでも，点配置は大きく変化せず地理的な配

都圏と近畿圏のいずれと辺で繋がれているかが明らかで置を保っているため，グラフ上の点と地域との対応関係がはない．同様に，
首都圏と道央を結ぶ辺に近接して青森，

分かりやすく表現されていることが確認できる．

福島，栃木の各点が位置し，いずれの地域間が接続され最小全域木では，首都・中京圏間は接続されず，中京圏ているかが明確ではない．このように点と辺が近接して配は首都圏よりも近畿圏との間の交通量が大きいことが示

報告論文

Vol.16 No.3 2013 Autumn 運輸政策研究029

されている．なお，最小全域木はOD交通量上位の辺かに基づく辺の抽出基準は意味解釈が難しいため，新たにら抽出するものの閉路を避けるため，OD交通量の大き抽出された辺のOD交通量が持つ特徴を明らかにするこさが第8位の茨城・栃木間や第12位の中京圏・静岡間をとは容易ではない．しかし，抽出される辺の数を自在に増抽出せず，第68位の岡山・香川間や第72位の首都圏・沖やすことができるガブリエルグラフを活用した視覚表現

縄間を抽出して，全点を接続するグラフを構成している．

を通して，最小全域木や相対近傍グラフでは表現できな
いOD交通量データが示す地域の関係性を示すことがで（図─10）
4.2 相対近傍グラフ

きると筆者らは考えている．例えば，図─12では，遠距離

相対近傍グラフは，最小全域木で示された辺に加えて，にも関わらず，道央・青森・宮城・中京圏・近畿圏・愛媛・

図─10上に青色で示した中京圏・静岡，首都圏・福岡，中福岡と首都圏とを結ぶ辺が引かれ，これらの地域が首都京圏・富山，近畿圏・鳥取の4辺を抽出し，交通量の68.8％

圏に対して比較的強い結びつきを持っていることが示さを表している．地理的配置上に辺を描いた図─10（a）
でれている．一方で，新潟からは隣接県との間に全く辺がは，例えば，
首都圏・福岡間を結ぶ辺の近傍に中京圏，近引かれておらず，近隣地域との交流が活発ではないこと

畿圏，香川が位置するため接続関係が読み取りにくいが，が表現されている．

点・辺近接を緩和した図─10（b）
では，点配置が改められ

本報告で提案したガブリエルグラフを拡張した辺の抽た結果，誤解を生みにくい図となることが確認できる．

出は，試行錯誤的に抽出辺数を変えながら視覚表現を

ここで，新たに抽出された辺の中で，最もOD交通量の行うことによって，OD交通量データに潜む地域の関係性

小さい中京圏・富山を結ぶ辺に着目する．相対近傍グラを発見できる道具となると考えている．

フでは全体の5％強の辺しか抽出されないにも関わらず，
OD交通量第62位の同辺が抽出されている．相対近傍グ

4.4 まとめラフの辺抽出は，
中京圏・富山間の交通量以上に，中京圏

全国幹線旅客純流動調査データへの適用を通して，近と富山の双方に対して交通量が多い地域が存在しない

傍グラフ作成を応用した主要辺抽出によって，図上で表ことを示しており，相対的に中京圏・富山間の交通量が多現するOD交通量データを段階的に抽出することが可能

い事実を把握することができる．

であること，
また，カルトグラム作成手法を応用した点・辺

なお，最小全域木では，例えば，中京圏・静岡を結ぶ辺
は，「閉路を作らない」という全域木の制約のため，
より関近接の緩和によって，可読性の高い作図が可能であることが示された．

係が強い首都圏・近畿圏を結ぶ辺の影響で抽出されなかった．閉路を作らない最小全域木は，地域の階層的な関係を明示的に表現できる利点を持つ反面，局所的に5──おわりには強い関係を有する地域間を結ぶ辺を表現できないと

本報告では，近傍グラフによるOD交通量データの視いう欠点がある．相対近傍グラフの抽出辺上に，最小全覚表現について検討を行った．交通量の多い主要な地

域木の抽出辺を描き，最小全域木の欠点を補った表現を域の組み合わせを近傍グラフで抽出した上で，その抽出行うことも有効であろう．

結果を，地域の地理的位置関係を考慮しつつ，点と辺の近接を回避するように配置する方法を提案した．その後，（図─11・12）
4.3 ガブリエルグラフ

全国幹線旅客純流動調査データを用いて提案手法によ

乗数パラメータ α に関して α＝2と設定したガブリエル

る視覚表現を試み，OD交通量データが持つ地域間の関グラフでは，相対近傍グラフで示された辺に加えて，図─

係性に関する情報を縮約して2次元平面に展開し，
可読

11上に青色で示した道北・道東，
首都圏・愛媛，大分・宮性の高い視覚表現が可能であることを確認した．

崎の3辺を抽出し，交通量の69.4％を表現している．まデータの視覚表現を行う主目的の一つは，データの中た，α＝1と設定したガブリエルグラフは，図─11に加えに潜む，気づきにくい事象を抽出し，新たな知識を生み出て図─12 上に青色で示した 11 辺を抽出し，交通量のす分析へと繋げることにある．本報告では，様々な近傍

78.7％を表現している．ガブリエルグラフでは，相対近傍の定義に基づきOD交通量データを抽出した結果，必ずグラフに比べて数多くの辺が抽出されているが，点・辺のしも主要な地域の組み合わせとは言えない辺が数多く表

近接を緩和した結果（図─11（b）
・図─12（b））
では点の配現された．残念ながら筆者らの力不足により，抽出され置が調整され，容易に読図できる配置になっていることた地域間の関係性について有効な意味解釈を行うにはが確認できる．

至っておらず，知識発見の道具としての提案手法の魅力を

前述のように，ガブリエルグラフを拡張した近傍の定義
030

運輸政策研究Vol.16 No.3 2013 Autumn

伝えられる事例を示すには至っていない．しかし，筆者ら

報告論文

は，提案手法がOD交通量データに潜む地域の関連性を抽出・発見する道具としての利用可能性を有していると考

参考文献
1）Qiu, P., Simonds, E. F., Bendall, S. C., Gibbs, K. D. Jr., Bruggner, R. V.,
Linderman, M. D., Sachs, K., Nolan, G. P., and Plevritis, S. K.
［ 2011］，

えている．今後，パーソントリップデータなどより大規模な

Extracting a cellular hierarchy from high-dimensional cytometry data with

OD交通量データ，あるいは，情報・通信など交通以外の

SPADE ，Nature Biotechnology, Vol. 29, pp. 886-891.

ODデータへの適用を通して，提案手法の知識発見の道
具としての有用性を確認していきたいと考えている．
なお，本報告では，地域間の両方向のOD交通量の和

2）波平光洋・名嘉村盛和・岡崎威生・Suharnan, S.
［2006］， 複数の最小木を考慮した確率的進化計算による遺伝子データ・クラスタリング ，「情報処理学会研究報告 バイオ情報学」，第64号，pp.59-64.
3）
吉田哲也・Hacid, H.
［2007］， 高次元データへのアクセス回数を削減する近傍
グラフ更新手法 ，Proceedings of Data Engineering Workshop，A1-9．

から近接性を定義し，近傍グラフ作成手法を用いた表現

4）Prim, R. C.
［1957］， Shortest connection networks and some generaliza-を試みたが，
もちろん他の近接性の定義に基づく表現も可

5）Kruskal, J. B.
［1956］， On the shortest spanning subtree of a graph and the

能である．地域間の結びつきの強さを表す指標として，

traveling salesman problem ，Proceedings of the American Mathematical

例えば，地域iからjへの交通量が，地域iの発生交通量に占める割合を用いて，地域間の近接性を定義することも可能である．様々な近接性の定義に基づく視覚表現を試すことにより，新たな地域間の関係性を発見できる可能性を有している．本報告で試行した近接性の定義以外に，

tions ，Bell System Technical Journal, Vol. 36, pp. 1389-1401.

Society, Vol. 7, No. 1, pp. 48-50.
6）Granam, R. L. and Hell, P.［ 1985］， On the history of the minimum
spanning tree problem ，Annals of the History of Computing, Vol. 7, No. 1,
pp. 43-57.
7）Toussaint, G. T.
［1980］， The relative neighbourhood graph of a finite
planar set ，Pattern Recognition, Vol. 12, No. 4, pp. 261-268.
8）Gabriel, K. R. and Sokal, R. R.
［1969］， A new statistical approach to geographic variation analysis ，Systematic Zoology, Vol. 18, No. 3, pp. 259-278.

視覚表現を行う上で有効な定義があるかどうかについて

9）Maignan, L. and Gruau, F.
［2011］， Gabriel graphs in arbitrary metric spaceも検討が必要である．合わせて今後の課題としたい．

and their cellular automation for many grids ，ACM Transactions on
Autonomous and Adaptive Systems, Vol. 6, No. 2, Article 12.
，『なわばりの数理モデル−ボロノイ図からの数理
10）例えば，杉原厚吉［2009］

謝辞：本報告の内容は，清水が運輸政策研究所の客員研

工学入門−』，共立出版．

究員として行った研究成果の一部である．研究助成，
なら11）例えば，中野眞一・西関隆夫［1999］，グラフの自動描画 ，「電子情報通信学

びに，研究報告会の折などに，関係の皆様から頂戴した

12）例えば，三木和男［2009］，ネットワークの可視化技術−大規模ネットワークと貴重なご助言に対し，深く感謝致します．

会誌」，第82巻，第2号，pp. 175-180．
動的ネットワークへの挑戦− ，「電子情報通信学会誌」，第92巻，第2号，pp.
112-117．
， 力学モデルを用いた階層型グラフデータ画面配13）
土井淳・伊藤貴之［2004］
置手法の改良手法とウェブサイト視覚化への応用 ，「芸術科学会論文誌」，第3巻，第4号，pp. 250-263．
14）清水英範・井上亮［2004］， 時間地図作成問題の汎用解法 ，「土木学会論文集」，765/IV-64号，pp. 105-114．
（原稿受付

2013年6月10日）

Visualization of Origin-Destination Trip Matrices through Applications of Neighborhood GraphBy Eihan SHIMIZU and Ryo INOUE
Since neighborhood graphs are noteworthy tools that analyze the similarity and proximity between data items and visualize
the structure of data, they are utilized in many research fields. However, they have not been used in the analysis andvisualization of origin-destination trip matrices, which record the proximity and hierarchy of regions. This report focuses onneighborhood graphs; it proposes to extract the major origin-destination pairs from data and visualize the extracted results.
The applicability of proposed method is confirmed using the inter-prefectural passenger trip data in Japan.
Key Words : neighborhood graph, origin-destination trip matrix, visualization, regional structure

報告論文

Vol.16 No.3 2013 Autumn 運輸政策研究031