# Inferring the Root Cause in Road Traffic Anomalies > [!abstract] 概要 > 道路交通データに現れる異常の根本原因を推定する、新しい 2 段階のマイニングと最適化の枠組みを提案する。道路交通を、主要道路で区切った都市の領域から成るネットワーク上の時間依存フローとしてモデル化する。第 1 段階では、過去の交通プロファイルからの逸脱に基づいてリンク異常を特定する。しかしリンク異常だけでは、何がそれを異常にしたかはほとんど分からない。そこで第 2 段階では生成的なアプローチをとり、ネットワーク上のフローを起点終点(OD)行列で表す。OD 行列は、起点と終点の間の潜在フローと、リンク上の観測可能フローを物理的に結びつける。重要な着眼は、観測ベクトルとして全リンク交通量を使う代わりに、リンク異常ベクトルだけを使う点である。L1 逆問題を解くことで、リンク異常を生んだ経路(起点終点対)を推定する。ほぼ 8 億点に及ぶ非常に大規模な GPS データでの実験により、リンク異常の出現を明確に説明できる経路を発見できることを示す。観測可能な異常を生成的に説明するために最適化技法を用いる点は、我々の知る限り完全に新しい。 ## 論文情報 - 著者: [[Sanjay Chawla]](シドニー大学)、[[Yu Zheng]]([[Microsoft Research Asia]])、[[Jiafeng Hu]](中国科学院ソフトウェア研究所)。 - 掲載: ICDM 2012(IEEE International Conference on Data Mining)。PDF 内に出版年の記載はなく、出版年は依頼側の指定に従った。 - データ: 北京のタクシー GPS 軌跡。 ## 概要 道路の交通量異常を検知するだけでは、それがなぜ起きたかは分からない。本論文は、異常検知の後段に「異常を説明する経路の推定」を置く。主要道路で区切った領域を節点、十分なタクシー流のある領域間を有向リンクとし、リンク・経路行列 A で観測リンク量 b と経路量 x を Ax = b で結ぶ。b にはリンク異常ベクトルだけを入れ、L1 最小化でスパースな x を得る。北京の実データで、桜祭りの増加と、マラソンの交通規制による減少を、外部の出来事の情報なしで経路として説明した。 ## 問題設定 - 履歴に出来事の記述は無く、マイニングした異常を組み合わせて原因の出来事を推す体系的な方法が無い。 - 道路網は有向グラフ N = (V, L)。V は主要道路で区切った領域、L は領域間の有向リンクである。北京は 580 領域に分割した。 - 領域単位で扱う理由は 2 つある。領域には業務地区・商業地区・住宅地などの意味的まとまりがあり、住宅地から商業地区への異常な増加が休日の指標になる。領域は GPS の誤差を平均化でき、グラフも小さくできる。 - リンク・経路行列 A は、リンク i が経路 j 上にあれば 1、なければ 0 の二値行列である。経路数 n はリンク数 m より遙かに多く、Ax = b は劣決定で解が無数にある。 ![[wiki/sources/_attachments/2012__ICDM__Inferring-the-Root-Cause-in-Road-Traffic-Anomalies/fig02-region-link-route-example.png]] *Figure 2: 領域・リンク・経路・リンク経路行列の例。* ## 提案手法 全体の例を図 1 に示す。赤い太線が PCA で見つけたリンク異常、緑の破線が L1 最適化で推定した原因経路である。マラソンのために天安門広場周辺が迂回され、本来の最速経路(点線)を避けた交通が破線の経路に集中した。 ![[wiki/sources/_attachments/2012__ICDM__Inferring-the-Root-Cause-in-Road-Traffic-Anomalies/fig01-beijing-marathon-root-cause.png]] *Figure 1: Beijing marathon の例(異常リンクと原因経路)。* **第 1 段階: PCA によるリンク異常検知。** - リンク × 時間区間のリンク時間行列 L から、平均を引いた行列 L~ を作る。C = L~ᵀL~(t × t)の固有分解で固有対を降順に並べ、上位 r 本を正常部分空間 Pn、残りを異常部分空間 Pa とする。各リンクを Pa へ射影し、射影の大きさ ‖x − xa‖ が閾値 θ を超えるリンクを異常候補とする。 - 時間区間でなくリンクの異常を探すので、共分散行列に LLᵀ でなく LᵀL を使う。 - 弱点は、正常と異常の部分空間の分割が恣意的で、結果がその選択に敏感なことである。上位 k 本で分散の約 95% を捉える慣習に従う。 - 5 × 5 の例では、固有値が [1.9, 0.67, 0.02, 0.01, 0] × 10³、異常部分空間での 2 乗偏差が [0.4, 0.06, 0.5, 1.47, 0.49] × 10³ となり、リンク l4 が異常と正しく特定された。 **第 2 段階: L1 最小化による経路推定。** - 交通工学ではこの問題を観測可能性問題、ネットワーク計測ではネットワークトモグラフィと呼ぶ。均衡状態で Ax = b が成り立つと仮定し、A は 0/1 行列、x は経路量ベクトル、b はリンク量ベクトルである。 - スパース解を得るには L0 ノルムが自然だが、凸な L1 ノルムに置き換えても、条件次第でスパースな解が得られる。2 本の制約が平行(線形従属)でないことが、L1 解のスパース性の条件である。 - 図 3 は 2 変数の例で、線形計画に直した L1 問題の超平面 x1 + x2 = t が制約に最初に触れる点が、L0 解 (0, b1/a1) と一致する様子を示す。 ![[wiki/sources/_attachments/2012__ICDM__Inferring-the-Root-Cause-in-Road-Traffic-Anomalies/fig03-l1-l0-lp-geometry.png]] *Figure 3: L1 解と L0 解が一致する条件。* - 図 2 の A(5 × 6)で l2 と l4 が異常なら b = [0, 1, 0, 1, 0]ᵀ で、cvx による L1 解は x = (0, 1, 0, 0, 0, 0)、すなわち経路 p2: r2 → r3 → r4 だけが選ばれる。L2 解は x = (0, 0.75, 0.25, 0.25, −0.25, 0) と多数の非ゼロを含み、解釈が難しい。 - 実装は Matlab の cvx(L1 と L2)と、Basis Pursuit に近い貪欲版 L1(L1-greedy)の 3 種を比べる。 ## 新規性 - 観測可能な異常を生成的に説明するために最適化技法を使う点を、著者らは完全に新しいとする。 - 既存のネットワーク異常検知(Lakhina らの PCA、Zhang らのネットワークアノモグラフィ)は、異常な時間区間を見つけ、その起点終点対を推す。本論文は出来事の種類も分からない状態から出発する。 - 交通工学の観測可能性問題では、スパースな経路ベクトルを L1 で推定する使い方が知られていないと述べる。 - 交通渋滞の検知(Dong と Pentland、Ong ら)とは、渋滞に限らない増減を扱う点と、道路面でなく領域間を扱う点で異なる。 ## 実験設定 - データ: 13,597 台のタクシーの 3 か月(2011 年 3・5・8 月)の GPS 軌跡。総距離は 4 億 km 超、GPS 点は約 7 億 9 千万、平均サンプリング間隔は 70.4 秒。重量センサで客の乗車を判定し、実車の 8,202,012 トリップを抽出した(北京市交通局の報告で路上交通の 15% 超)。 - 道路網: 節点 121,771、辺 162,246。主要道路で 580 領域に分割した。 - 時間区間は 15 分で、過去 w 時間の軌跡で 15 分ごとに手法を実行する(図 4)。w は 1〜8 時間で変える。 - 実行環境は Windows Server 2008 の 64 ビット、2.66 GHz CPU、16 GB メモリ。行列の構築は C#、PCA は Matlab 標準、L1 は cvx。 - 5 トリップ未満のリンクは、雑音や地図照合の不完全さによるとして除く。 - 評価は、北京市交通局が報告した実際の出来事による事例研究と、半合成実験の 2 種類。 ![[wiki/sources/_attachments/2012__ICDM__Inferring-the-Root-Cause-in-Road-Traffic-Anomalies/fig04-sliding-window.png]] *Figure 4: スライディング窓と行列の更新時間。* ![[wiki/sources/_attachments/2012__ICDM__Inferring-the-Root-Cause-in-Road-Traffic-Anomalies/fig05-trajectory-link-maps.png]] *Figure 5: 軌跡データとリンクの分布(北京)。* ![[wiki/sources/_attachments/2012__ICDM__Inferring-the-Root-Cause-in-Road-Traffic-Anomalies/fig06-traffic-links-time-of-day.png]] *Figure 6: 時間帯ごとの交通量とリンク数の変化。* ## 実験結果 **効率。** 表 II に各段の平均時間を示す。行列を作った後の更新は速く、多くの場合 10 秒以内で異常を検知でき、8 時間窓でも 15 秒以内である。窓幅を延ばしても計算時間は少ししか増えない。 ![[wiki/sources/_attachments/2012__ICDM__Inferring-the-Root-Cause-in-Road-Traffic-Anomalies/fig13-table2-running-time.png]] *Table 2: 行列構築・PCA・L1 最適化の実行時間。* 図 7 で 3 種の解法を比べると、平均実行時間は cvx-L2 が最速で、L1-greedy は窓が小さいとき cvx-L1 より速く、窓が大きくなると cvx-L1 が有利になる。窓幅により L1 の実装を選べる。 ![[wiki/sources/_attachments/2012__ICDM__Inferring-the-Root-Cause-in-Road-Traffic-Anomalies/fig07-l1-implementation-efficiency.png]] *Figure 7: L1 実装の効率。* **閾値の設定。** 図 8 は異常部分空間での平均からの距離の分布で、窓幅と時間帯によらず、90% のリンクが標準偏差 1 倍以内、98% が 3 倍以内に入る。この分布に基づき、標準偏差の 3 倍を超えるリンクを異常とした。 ![[wiki/sources/_attachments/2012__ICDM__Inferring-the-Root-Cause-in-Road-Traffic-Anomalies/fig08-anomalous-subspace-deviation.png]] *Figure 8: 異常部分空間での偏差の分布。* **解のスパース性。** 表 III のとおり、窓幅が大きいほど異常リンクも経路も増える。L2 解は経路が数百に及ぶ(w = 8 で 693)のに対し、cvx-L1 は 10〜97 経路の妥当な数を返す。 ![[wiki/sources/_attachments/2012__ICDM__Inferring-the-Root-Cause-in-Road-Traffic-Anomalies/fig14-table3-anomalous-links-paths.png]] *Table 3: 検出した異常リンクと経路の数。* **事例研究。** - 2011 年 4 月 2 日 9〜11 時(桜祭り初の週末で、清明節のため出勤日に振り替えられた土曜)。領域 r3(玉淵潭公園)へ向かう増加により、リンク L1・L2・L3 が異常となった。L2 の交通の 21.4% が r1 から、14.3% が r2 から来ており、L3 の原因交通の 61% は r3 に由来する。r1・r2・r4 が歴史名所を含む領域であることから、桜祭りへの来訪者による異常と読み取れた。 - 2011 年 4 月 17 日 9 時 30 分(北京マラソン)。天安門広場発のマラソンの交通規制(赤い領域)で、r1 と r3、r2 と r3、r1 と r5 の最速経路が遮られた。リンク L1 の交通が減少して異常となり、規制前の 15 分間に r1 から r5 へ走った 4 台は規制後に 0 台となった。原因は異常が生じた領域の中でなく規制域にあり、経路の推定なしには結論しにくい。 ![[wiki/sources/_attachments/2012__ICDM__Inferring-the-Root-Cause-in-Road-Traffic-Anomalies/fig09-sakura-and-marathon-cases.png]] *Figure 9: 桜祭り(増加型)とマラソン(減少型)の異常事例。* **半合成実験。** 実データの窓からリンク・経路行列を作り、正常リンク(L5)を手で除いてその交通を別経路(r3 → r4 → r6)へ回す(図 10)。除去リンクの交通量ごとに、200 の時間帯から選んだ 3 リンクで 600 回の試験をし、各段の適合率と再現率を測る。 ![[wiki/sources/_attachments/2012__ICDM__Inferring-the-Root-Cause-in-Road-Traffic-Anomalies/fig10-semisynthetic-setup.png]] *Figure 10: 半合成実験の設定。* - 第 1 段階(図 11)は、除去リンクの交通量が大きいほど検知精度が上がる。窓幅 2 時間は 1 時間より精度が高く、4 時間にしても改善しない。長い窓ほど正確だが、長すぎると雑音を招く。 ![[wiki/sources/_attachments/2012__ICDM__Inferring-the-Root-Cause-in-Road-Traffic-Anomalies/fig11-step1-precision-recall.png]] *Figure 11: 第 1 段階の有効性。* - 第 2 段階(図 12)は、cvx-L1 が適合率・再現率とも cvx-L2 を上回る。L1 は交通量の変化にあまり敏感でない。図 12 の読み取りでは、L1 は約 0.8〜0.95、L2 は約 0.4〜0.6 の水準にある。 ![[wiki/sources/_attachments/2012__ICDM__Inferring-the-Root-Cause-in-Road-Traffic-Anomalies/fig12-step2-precision-recall.png]] *Figure 12: 第 2 段階の有効性。* ## 考察 - 先行研究との関係: 交通の数理モデル(Beckmann らの Wardrop 均衡と大域最適化の等価性)は順問題で、データはモデルの較正に使われる。データマイニングが解くのは逆問題で、データから均衡を乱す出来事を推す。 - 領域単位のモデル化が、計算量の削減と原因推定の双方に効くと述べる。 - L1 解が経路数の爆発を抑え、経路の解釈を容易にする。 ## 強み / 弱点・課題 - 強み - 検知と原因説明を 1 つの枠組みでつなぎ、出来事の情報なしに実イベントを経路として説明できた。 - スライディング窓の更新で、8 時間窓でも 15 秒以内に動作する。 - 増加型の異常と減少型の異常の両方を扱える。 - 弱点・課題 - PCA の正常部分空間の次元と閾値 θ の選択が恣意的で、結果が敏感になる(本論文自身が認める)。 - 均衡状態で Ax = b が成り立つという理想化を置く。実際は起点終点と各リンクの流れに時間差がある。 - 事例研究は 2 件で、地上真値は市交通局の報告に依存する。適合率と再現率は半合成実験でしか測っていない。 - スパース性が原因の真の集合と一致する保証は示さず、L1 解のスパース性は制約が線形従属でないことを条件とする。 - 論文内の数値に食い違いがある。要旨は約 8 億点、実験は約 7 億 9 千万点で、結論は「3 万台超のタクシー」と書くが、実験は 13,597 台である。 ## 関連 - 概念: [[異常検知]] / [[根本原因分析]] / [[主成分分析]] - エンティティ: [[Sanjay Chawla]] / [[Yu Zheng]] / [[Jiafeng Hu]] / [[Microsoft Research Asia]] / [[University of Sydney]] ## 出典 - [[.raw/papers/2012__ICDM__Inferring-the-Root-Cause-in-Road-Traffic-Anomalies.pdf]]