Upgrade to Pro — share decks privately, control downloads, hide ads and more …

論文読み会 SIG-SPATIAL'20 | (k,l)-Medians Clustering...

cocomoff
April 23, 2021

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

論文読み会のための資料

cocomoff

April 23, 2021
Tweet

More Decks by cocomoff

Other Decks in Research

Transcript

  1. 距離指標 | DTW DTW (Dynamic Time Warping) (summed measure) 離散時間pair-wise

    でコスト計算 pair-wise matrix を左下から右上へつないだものが解 ( 対応付け) ( 離散) warping path と呼ぶ (monotone curve from LB to UR) 2/18
  2. 距離指標 | 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
  3. 距離指標 | CDTW を利用する目的 (2/3) CDTW はDTW と異なりクラスタ中心として表現が望ましい クラスタ中心は -means

    でいう重心のことで,重心trajectory を求める と,DTW よりもうまく平均的なtrajectory とみなすことができると主張 5/18 k
  4. 距離指標 | CDTW を利用する目的 (3/3) CDTW はFrechet と比較して外れ値に強い Frechet は最大値に引きずられが,CDTW

    はDTW っぽい性質を引き継ぐ (summed measure) ため,外れ値に強いと主張 6/18
  5. 距離指標 | 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] ∑
  6. 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
  7. 参考: Frechet 距離の計算 ( イメージ図) Frechet 距離/CDTW に関する計算はFree-space を利用 |

    距離 以下の箇所 Free-space を考えている = 頂点以外に対応する ( 連続 ) 直感的には白色の領域の連結性は格子上だけで判定できる 曲線の部分同士のペア毎に計算し,DTW のようにたどる monotone path が見つけられたら,Frechet 距離が 以下 10/18 ϵ t ϵ
  8. 論文での実装 ( おそらくMaheshwari et al. の応用) コスト が乗っているとき,コスト最小になるmonotone path として2

    パタ ーンのパスがある (Maheshwari et al. 2018) 双方向ダイクストラで計算するらしい ( 詳細不明) 11/18 h
  9. クラスタリング ( その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
  10. クラスタリング ( その2) DBA (DTW Barycenter Averaging), CDBA (CDTW ...)

    k-means して,クラスタ内の平均trajectory を使って計算し直し,コ ストが下がればクラスタ中心を置き換える FSA (Free Space Averaging) これはFrechet の教祖Buchin の手法 点をサンプルしてきてFrechet 距離を使って計算する既存手法 ( 謎) 13/18