Activity pattern similarity:
a multidimensional sequencealignment method
Chang-Hyeon Joh, Theo Arentze,Frank Hofman, Harry Timmermans

東京大学大学院羽藤研究室
M1 松村草也

2008/10/30

研究の背景アクティビティパターンの類似性
活動目的 / 活動地点 / 開始時刻 / 終了時刻 /継続時間 / 交通手段 といった指標による判
断

研究目的
類似性指標はアクティビティパターンの基礎分析において重要な役割を持つ
アクティビティモデルの精度検証においても同様.

問題設定
ソースパターンs = s[ s1 ,..., sk ,..., sK ]'sk = sk [ sk 0 ,..., ski ,..., skm ]

出勤
会社
自動車
単独

営業
営業先
徒歩
2人

帰宅
自宅
自動車
単独

買物
ｺﾝﾋﾞﾆ
自転車
単独

出勤
会社
電車
単独

食事
ﾌｧﾐﾚｽ
バス
2人

営業
営業先
電車
単独

帰宅
自宅
電車
単独

ターゲットパターンg = g[g1 ,...g k ,...,g K ]g k = g k [ g k 0 ,..., g kj ,..., g kn ]k:attributeの数
i:ソースパターンのステップ数
j:ターゲットパターンのステップ数

atrribute：活動属性．
活動目的 / 活動場所 / 交通手段 / 同行者など

i=0,..., m; j=0,..., n; k=1,..., K ; ski ∈ Ak , g ki ∈ Ak

SAM（Sequence Alignment Method）

4つの操作：（）内はスコアDeletion:削除（１）Insertion:挿入（１）Substitution:置換（２）Identity:確認（０）異なる２つの活動属性シークエンスを等しい形にする，スコア合計が最小の操作セットを求める．

操作例にかかる操作コストは？

s[ACB]→n u ll

ABCn u ll

ACBAACBABACBABCACB

A

CB

ACB

ABCB

ABCCBC

BAB

ABB

ABCB

Bn u llAAB

ABCs[ABC]

右方向：挿入下方向：削除右下方向：確認or置換

統合手法の提案
問題点
複数のattributesを考慮したモデルへの拡張．
従来手法では単純に重ね合わせ（UDSAM）→個々のattributeについてsequenceの類似性のoperation costを計算し，足し合わせると，attribute間の相互作用を考慮できない．
「Segment」の提案
β：attributeの重み
ｗ：個々のoperationのcost

操作コストの定義：

C = max(β1 , β 2 ) × wd
( β1 + β 2 ) × wd − max(β1 , β 2 ) × wd = min( β1 , β 2 ) × wd

複数のOperationをSegmentとしてまとめて考える．

１次元オペレーションセット
(Uni-dimensional operation set)
1.
2.
3.

operationの内容
operationの位置
operationが適用されたattributeによって操作を記述する．

Ok ,l = { p | p = d (i, k ) ∨ i ( j , k ) ∨ s (i, j , k )}deletion

insertion

substitutiond(i,k):skのi番目の要素を削除
i ∈ {1,..., m},i( j,k):gkのj番目の要素をskのj番目の要素へ挿入
s(i,j,k):gkのj番目の要素とskのi番目の要素を置換．

j ∈ {1,..., n}, 1 ≤ k ≤ K

ex.左図の操作セット

O2,1 = {i(1,2), i(3,2), d(2,2), d(3,2), i(5,2)}
O2, 2 = {i(1,2), i(2,2), d(3,2), d(3,2), i(5,2)}→異なる経路がl通りある．
OT-MDSAM:
Optimum Trajectories-based MultiDimensional Sequence Alignment Method多次元オペレーションセット
KT = ∏ Tk
k =1

T:attributeごとの最小操作量経路の組み合わせ数．
最小操作量を満たす経路が複数存在する時，それらの集合を多次元オペレーションセットと呼ぶ．

O = { p | p = d (i, k ) ∨ i( j , k ) ∨ s(i, j , k )}tたとえば，右のような例を考える．
３つのattribute．

O1t,l ' = {d (2,1), i(4,1), s(5,6,1)},O2t ,l = {d (3,2), i(4,2), s(5,5,2)},O3t ,l " = {d (2,3), i(4,3), s(5,5,3)}

O t = {d(2,{1,3}), d(3,{2}), i(4,{1,2,3}), s(5,5,{2,3}), s (5,6, {1})},

多次元類似性
attributeの組み合わせごとにコストを計算した合計．

C = ∑ cptp∈Otwd β kmax if p = d (i, k )where c p = wi β kmax if p = i( j , k )maxw
βif p = s(i, j , k ) s k
多次元類似性指標を以下のように定義する．

C = min[C ,..., C ,..., C ]
t*

1t

T

計算実行例

活動目的
Tk=１

活動場所
Tk=１

交通手段
Tk=５

同行者
Tk=１

計算実行例

計算実行例

手法の有効性検証
OT-MDSAMとUDSAMの比較
従来型の単純加算手法に比べて，提案手法を用いることで活動属性間の相互作用について，より有効な知見が得られていることを示す．

提案手法の計算可能性
データ構造を縮約したことによる計算速度の向上について検証を行う.

検証データ概要
Rotterdam
アクティビティダイアリーデータ（97年オランダ，2都市）
連続した2日間についてアンケート
2974パターン中の71パターン，(71*71-71)/2=2485ペアを対象とした．
活動属性は活動目的，活動場所，交通手段の3種類．
活動目的：25種類＋自宅
活動場所：32施設
交通手段：４種類（車，徒歩，自転車，助手席の）Hendrik-Ido-Ambacht
Zwijndrecht

類似性検証結果

2485ペアを対象に類似性コストを2つの方法で計算し，結果を比較．
提案手法が算出した平均コストが従来手法に比べて14.63ポイント低下．
OT-MDSAMのプライマリ活動属性の重みを3以上の値に設定すると，UDSAMの結果との相関係数がほぼ１となる（左図）．同時にUDSAMの結果に対する平均コストの「減少率」が下がる（右図）．

活動属性間比較

検証では，活動目的は行き先よりも交通手段のほうが相関関係にある，という結果が得られている.
交通手段と移動先の関係のほうが，移動先と活動内容に比べ，固定されているといえる.

計算速度に関する検証

従来手法に比べ，格段に計算速度が上がっている.
Segmentを用いることによるデータの縮約の効果が現れているといえる.

まとめ
シーケンシャル情報，活動属性間の相互依存性について説明を与える指標として，活動パターン間の類似性を提案した．
特に，多次元での活動パターン比較を可能にした．複数要素をSegmentとしてまとめることを提案した．