論文読み会 SIG-SPATIAL'20 | (k,l)-Medians Clustering of Trajectories Using Continuous Dynamic Time Warping

論文読み会のための資料

Transcript

1. @cocomoff 2021/4/23
2. 概要 CDTW (Continous DTW) という距離尺度を用いて，軌跡データのクラス タリングを達成した: 具体的な貢献は (1) CDTW を近似計算するアルゴリ ズムを提案した (2) CDTW を用いるクラスタリング計算を提案した 1/18
3. 目次 概要と問題・実験 詳細 DTW ，Frechet ，CDTW CDTW の計算 クラスタリング計算 実験その他
4. 距離指標 | DTW DTW (Dynamic Time Warping) (summed measure) 離散時間pair-wise でコスト計算 pair-wise matrix を左下から右上へつないだものが解 ( 対応付け) ( 離散) warping path と呼ぶ (monotone curve from LB to UR) 2/18
5. 距離指標 | Frechet distance, CTDW Frechet Distance (bottleneck measure) 直感的にはDTW でコストを和とする代わりにmax にしたもの 最大離れている箇所を最小にする連続空間の対応付けを求める 時刻 の曲線地点 が，曲線地点 に対応つく d ​ (P, Q) := F ​ ​ dist(P(t), Q(f(t))) f:[0,1]→[0,1] inf t∈[0,1] sup CDTW: イメージとしてはDTW とFrechet の良いとこ取り DTW で頂点( 離散インデックス ) 以外で対応付けしても良いもの 歴史的にはFrechet distance のsum/average として特徴付け ( 不明) 具体的な定義は後ほど 3/18 t P(t) Q(f(t)) t
6. 距離指標 | CDTW を利用する目的 (1/3) (1) クラスタ中心として良い (2) 外れ値に強くする CDTW はDTW と異なり頂点以外で対応付けして良い 4/18
7. 距離指標 | CDTW を利用する目的 (2/3) CDTW はDTW と異なりクラスタ中心として表現が望ましい クラスタ中心は -means でいう重心のことで，重心trajectory を求める と，DTW よりもうまく平均的なtrajectory とみなすことができると主張 5/18 k
8. 距離指標 | CDTW を利用する目的 (3/3) CDTW はFrechet と比較して外れ値に強い Frechet は最大値に引きずられが，CDTW はDTW っぽい性質を引き継ぐ (summed measure) ため，外れ値に強いと主張 6/18
9. 距離指標 | CDTW の定義 | 概要 Warping path を計算するとき，格子だけではなく間も全て計算する 連続 に対するwarping path 計算はFrechet でよく研究されている 7/18 t
10. 距離指標 | CDTW の定義 | 式 Trajectories 連続化した空間 空間の上にコストが乗っている: 連続的に と媒介変数表示した曲線上で積分する (DTW は ) ​ h(r)dr := ∫ π ​ h(π(t))∣∣π (t)∣∣dt ∫ 0 1 ′ コスト最小となるcontinuous warping path は δ ​ (P, Q) := CD p ​ ​ h(π(t))∣∣π (t)∣∣ ​ dt π min ∫ 0 1 ′ p 8/18 P = (p ​ , … , p ​ ), Q = 1 n (q ​ , … , q ​ ) 1 m P = [0, L(P) = n] × [0, L(Q) = m] h : P → R+ t ∈ [0, 1] ∑
11. 目次 概要と問題・実験 詳細 DTW ，Frechet ，CDTW CDTW の計算 クラスタリング計算 実験その他
12. CDTW の計算 曲線上の2 点 上のコスト定義は以下とする ( 理由は？) h((p, q)) := (p − a) + 2 (q − a) + 2 2λ(p − a)(q − a) + c ある格子 で計算する．積分+ 最小化はどうやって計算すればいい? 計算: セルの中身は無視して境界部分だけ判定すれば良い (Frechet) 既存手法の流れ [Maheshwari et al. 2018] 各セルでfree-space とコスト関数を確認して候補を出す 全部のセルを計算してから，continuous warping path を接続する 9/18 (p, q) ∈ P C
13. 参考: Frechet 距離の計算 ( イメージ図) Frechet 距離/CDTW に関する計算はFree-space を利用 | 距離 以下の箇所 Free-space を考えている = 頂点以外に対応する ( 連続 ) 直感的には白色の領域の連結性は格子上だけで判定できる 曲線の部分同士のペア毎に計算し，DTW のようにたどる monotone path が見つけられたら，Frechet 距離が 以下 10/18 ϵ t ϵ
14. 論文での実装 ( おそらくMaheshwari et al. の応用) コスト が乗っているとき，コスト最小になるmonotone path として2 パタ ーンのパスがある (Maheshwari et al. 2018) 双方向ダイクストラで計算するらしい ( 詳細不明) 11/18 h
15. 目次 概要と問題・実験 詳細 DTW ，Frechet ，CDTW CDTW の計算 クラスタリング計算 実験その他
16. クラスタリング ( その1) -medians clustering - 本のクラスタに分ける 距離計算する際に -simplification する (k-means の重心に相当する trajectory が必要で，ここの簡素化part のこと) Gonzalez algorithm を用いる ( 要するにk-means のgreedy) Trajectory simplification の併用 論文にはあまり書いてない 細かい部分を直したものを計算してクラスタ中心として用いる 2 つの手法が存在するので ( たぶん) ，利用する Greedy Imai-Iri ( 東大の今井研の昔の論文らしい) 12/18 (k, l) k l
17. クラスタリング ( その2) DBA (DTW Barycenter Averaging), CDBA (CDTW ...) k-means して，クラスタ内の平均trajectory を使って計算し直し，コ ストが下がればクラスタ中心を置き換える FSA (Free Space Averaging) これはFrechet の教祖Buchin の手法 点をサンプルしてきてFrechet 距離を使って計算する既存手法 ( 謎) 13/18
18. 目次 概要と問題・実験 詳細 DTW ，Frechet ，CDTW CDTW の計算 クラスタリング計算 実験その他
19. 実験 | simplification Simplification の例 14/18
20. 実験 | クラスタリング (quality) CDBA, Wedge が提案手法 (Wedge はk-means の中心更新の計算が異なる) 15/18
21. 実験 | クラスタリング ( 文字h, e) 16/18
22. 実験 | クラスタリング (pigeon) 17/18
23. 実験 | クラスタリング (movement) 18/18