DEIM Forum 2023 2b-2-3

大規模軌跡クラスタリングの類似度演算回数均一化による MapReduce モ
デルの分散処理効率化
鳥越貴智†† トヨタ自動車株式会社 〒 100-0004 東京都千代田区大手町 1-6-1 大手町ビル 6F
E-mail: †takatomo torigoe@mail.toyota.co.jp
あらまし

人や車などの移動体について大規模な軌跡データが蓄積されるなか，類似軌跡を高速に集約する手法が求められている．中心ベースの軌跡クラスタリングを用いれば軌跡数 n に対する計算量は O(n) となるものの，実用的な分析需要としては，軌跡数が増大しても実行時間を比例させない処理方法の開発が喫緊の課題である．本研究では軌跡クラスタリングについて，MapReduce モデルに基づく分散データフローに加え，その中で支配的な類似度算出タ
スク群に対して待ち合わせ時間の少ない分散処理を行うため，演算回数を均一化した CDTW 近似計算法を提案する．
人流軌跡の実データを用いて，軌跡数の増大に応じた計算資源を割り当て実行時間を抑えることで，その並列性が先
行実装より高いことを示した．
キーワード

空間・時空間・時系列データ処理，並列・分散処理, 可視化・データ分類・クラスタリング, 効率性・ス

ケーラビリティ, 軌跡の類似度
タリングについて実行時間を低減する計算手法を提案する．本

1 序論

GPS センサーが付いた IoT 端末の普及により，人や車などの移動データを広範囲に渡って収集できるようになった．移動
データの社会的な活用例として，リアルタイムな人口分布の推計 [1]，COVID-19 の影響による訪問施設カテゴリー変化分
析 [2]，被災状況把握のための通行実績道路マップ [3] などが挙げられる．これらの例では人流や交通流を地域・施設・道路といった単位で集計しているが，より各人・各車の移動について
時系列で着目したい場合は，どこから出発して・どこを通り・
どこへ向かったのか，その一連の軌跡を捉えることが望ましい．

研究の貢献は次の 2 点に要約できる．1 点目は，軌跡クラスタ
リングについて MapReduce モデルに基づく分散データフローを示したことである．2 点目は，その分散データフローにおいて待ち合わせ時間を少なくするため，演算回数が均一な軌跡類
似度の近似計算を示したことである．そして最大 357 万の人
流軌跡を用いた実験によって，軌跡数が増大しても応じた計算
資源を割り当てることで，実行時間の増加を抑えられたことを示す．

2 先行研究しかし全く同一の経路を通る軌跡は一般的に稀であるから，適本研究は，軌跡クラスタリング手法の (k, l)-clustering，分散切な粒度で捉えるためには類似した軌跡を集約するクラスタリ

計算モデルの MapReduce モデル，軌跡類似度の CDTW に関

ング手法が求められる．

連するため各々の先行研究について紹介する．

軌跡クラスタリング結果の活用先としては，たとえば観光地

なお本研究では軌跡を，計測点を線分で繋いだ折れ線として周遊経路の分析や推薦，幹線道路開通による交通流変化の分析定義する．すなわち d 次元の軌跡 P は，Rd の点列 (p1 , . . . , pl )や検知，などが想定される．また移動データはプライバシー性として捉えられる．隣接点間の距離の総和を軌跡長と呼び，点が高いため個別の軌跡は充分な保護を要するが，軌跡クラスタ

列の要素数を軌跡サイズと呼ぶ．軌跡 P について，媒介変数表

リングにより時系列性を保った統計処理を行えることも利点で示する場合は P (t) として表記する．ここで媒介変数 t は区間ある．
なお移動データは年々増加しており，2021 年の日本においては携帯電話契約数が 2 億台 [4]，コネクティッドカーの新車販売台数が推定 370 万台 [5] といった規模である．そのため大規模に蓄積された移動データの分析結果を素早く社会に活用するた
めには，入力データが増大しても実行時間をなるべく抑えられるような計算手法が求められる．とくに分析の基礎的な前処理[0, 1] を渡り，P (t) は始点 p1 から終点 pl まで軌跡上を等速に動くものとする．

2. 1 (k, l)-clustering
汎用的なクラスタリング手法として，階層的クラスタリング
や密度ベースクラスタリングがよく知られている．軌跡のような時系列データについても，それぞれの手法を基にしたものがとして全数処理の需要が高い軌跡クラスタリングについては，

多く提案されている [6]．これらは一般的にクラスタリングの前

有用な計算手法の開発が喫緊の課題である．

処理として，軌跡数 n について n 行 n 列の類似度行列を求め以上の背景のもと，本研究では大規模な軌跡データのクラスる必要があり，その計算量は時間・空間ともに O(n2 ) となる．

軌跡の表現としては道路 ID のような記号の列を扱うものと緯2. 3 CDTW

度経度のような点の列を扱うものに大きく分けられるが，点列軌跡クラスタリングにおいて用いられる軌跡の類似度のうについては計算量に優れた手法として (k, l)-clustering [7] があち，軌跡を点列として扱うものとしては DTW (Dynamic Timeる．これは，点のクラスタリング手法として代表的な k-means

Warping) やフレシェ距離がよく知られている．どちらも軌跡

における中心点の代わりに，中心軌跡を用いる軌跡クラスタリ間の適切なマッチングを取るものであり，DTW はマッチング

ング手法である. 類似度についてはクラスタごとに求める中心点同士の類似度の和として求められ，フレシェ距離は最大値と軌跡と入力軌跡の間で測るため，計算量を O(kn) で抑えるこ

して求められる．そのためフレシェ距離の方が外れ値に鋭敏なとができる．ここで k はクラスタ数，すなわち中心軌跡の数で指標となる．

ある．

GPS センサーはビルの谷間など衛星通信環境の悪いとこ(k, l)-clustering は，コスト関数の最小化問題として定式化でろでは測位誤差が大きくなるため DTW の方が望ましいものきる．軌跡の集合 P = {P1 , . . . , Pn } が与えられた時，次式のの，DTW は離散的なマッチングを取るため測位のサンプリようなコスト関数の定義により，(k, l)-center と (k, l)-median

ング間隔による影響が大きい．そこで DTW のマッチングをという 2 種類の問題を設定できる．

連続化して，和を積分とした CDTW (Continuous Dynamic

Time Warping) が移動軌跡の類似度としては適切と考えられ
costcenter (P, C) =costmedian (P, C) =

max

min

i∈{1,...,n} j∈{1,...,k}
n
∑
i=1

min
j∈{1,...,k}similarity(Pi , Cj )similarity(Pi , Cj ) / n

る．CDTW はその積分の重みの付け方に様々な亜種 [15] があり，文献によっては平均フレシェ距離や積分フレシェ距離と呼ばれることもある．
本研究では，軌跡 P (t) と軌跡 Q(t) の類似度として CDTW

ここで l は中心軌跡のサイズ，similarity(·, ·) は 2 軌跡間のを次式で定義する．

類似度である．最小化の変数である C = {C1 , . . . , Ck } は k 個∫1の中心軌跡を表しており，それぞれサイズ l の軌跡である．このコスト関数を式変形すると，CDTW(P, Q) = infσcostcenter (P, C) =costmedian (P, C) =()()
s P (t), Q(σ(t))
L(P ) + L(Q)σ̇(t) dt
L(P ) + L(Q)ここで s(·, ·) は 2 点間の類似度，L(·) は軌跡長を表す．このmaxi∈{1,...,n}n∑similarity(Pi , Cbi )式は 2 つの軌跡長の比で重み付けした特殊な経路積分である．
そして σ(t) は軌跡の表示パラメータを変換するマッチング関

similarity(Pi , Cbi ) / n

i=1

where

0

bi = argmin similarity(Pi , Cj )j∈{1,...,k}数であり，積分値の下限を取る σ(t) を得る問題として CDTW
は捉えられる．

CDTW の (1 + ϵ) 近 似 解 を 得 る た め に ，計 算 量 が
4 4中心軌跡 C = {C1 , . . . , Ck } と，入力軌跡の所属クラスタ番O( ζϵ2l log ζl) のアルゴリズムが提案されている [16]．ここϵ

号 {b1 , . . . , bn } を求める最小化問題として捉えられる．よって

で ζ は 2 軌跡の任意の区間長の最大比であり，l は 2 軌跡のサ

k-means と同様に，中心軌跡を求めるステップと所属クラスタ

イズである．より実用的なアルゴリズムとして，双方向ダイクを求めるステップを交互に繰り返す EM アルゴリズムによってストラ法によるヒューリスティクス [10] が提案されている．

近似解を得ることができる．
このような方針のもと，(k, l)-center について実用的なアルゴリズム [8] と実装 [9] が提案されている．(k, l)-median についても同様に実用的なアルゴリズム [10] とマルチスレッドで並列処理できる実装 [11] が提案されている．

2. 2 MapReduce モデル

3 提案手法3. 1 (k, l)-clustering の MapReduce モデルに基づく分散
データフロー(k, l)-clustering の EM ア ル ゴ リ ズ ム は ，(k, l)-center と(k, l)-median の先行実装 [9] [11] を抽象化すると，擬似コード 1

ビッグデータ処理のため広く用いられている分散計算モデルのとおり書くことができる．ここで初期クラスタリングのアルとして MapReduce モデル [12] がある．これは分散データを並ゴリズムとして Gonzalez 法 [17] を用いており，matching(·, ·)列処理する Map フェーズ，再配置する Shuﬄe フェーズ，集約

は軌跡の類似度 similarity(·, ·) と関連したマッチング関数でする Reduce フェーズに分けて計算するモデルである．

ある．

点のクラスタリングにおいては k-means の亜種 k-means|| [13]このデータフローを MapReduce モデルに基づいて分散化しが，MapReduce モデルの実行エンジン Apache Spark の MLlib

たものを図 1 のとおり提案する．まず初めに入力軌跡を n 行のにて実装 [14] されており，そのスケーラビリティが実証されてデータとして読みこみ，これに対して Px ← simplify(Px , m) のいる．そのため k-means と同様の EM アルゴリズムが適用でような入力軌跡を長さ m に簡約する Map 処理を行う．MapRe-

きる中心ベースの軌跡クラスタリングについても，MapReduce

duce モデルは，Shuﬄe フェーズにて計算ノード間で通信を行モデルによってスケールすることが期待できる．

いデータを再配置して，次の Shuﬄe フェーズまでは各計算ノー

擬似コード 1 (k, l)-clustering の EM アルゴリズム [9] [11]Input: 入力軌跡 P1 , . . . , Pn ∈ P
Input: クラスタ数 k, 中心軌跡サイズ l, ループ回数 iter
Output: 中心軌跡 C1 , . . . , Ck where ∀j |Cj | = l
Output: 所属クラスタ番号 b1 , . . . , bn ∈ {1, . . . , k}
▷ 1. 初期クラスタリング▷ 1a. 乱択した入力軌跡を簡約した中心軌跡を作成
x ← sample({1, . . . , n})
C1 ← simplify(Px , l)
▷ 1b. 最初のクラスタに所属を更新
for i ← 1 to n dobi ← 1sMin i ← similarity(Pi , C1 )for j ← 2 to k do
▷ 1c. 最も類似していない入力軌跡を簡約した中心軌跡を追加
x ← argmaxi sMin i
Cj ← simplify(Px , l)
▷ 1d. より類似している中心軌跡のクラスタに所属を更新
for i ← 1 to n dosi,j ← similarity(Pi , Cj )if si,j < sMin i thenbi ← jsMin i ← si,jloop iter times▷ 2. 中心軌跡の更新
for i ← 1 to n do
▷ 2a. 所属クラスタの中心軌跡から類似マッチング点を算出
Mi ← matching(Pi , Cj )for j ← 1 to k dofor o ← 1 to l do
▷ 2b. 類似マッチング点を集めて中心点を算出
mSet j,o ← ϕ
for i ← 1 to n do
if bi = j thenmSet j,o ← mSet j,o ∪ {mi,o }
cj,o ← center(mSet j,o )▷ 2c. 中心点を並べて中心軌跡を更新
Cj ← (cj,1 , . . . , cj,l )

図 1 (k, l)-clustering の分散データフロー▷ 3. 所属クラスタの更新
for i ← 1 to n do
for j ← 1 to k do

サイズに強く依存するため，中心軌跡サイズを l に固定すると共に入力軌跡サイズを m に固定する．なお，この簡約済み入力▷ 3a. 全中心軌跡との類似度を算出

軌跡データは以降繰り返し参照することになるためキャッシュ

si,j ← similarity(Pi , Cj )する．

▷ 3b. 最も類似している中心軌跡のクラスタに所属を更新
bi ← argminj si,j

ステップ「1. 初期クラスタリング」では，中心軌跡の作成および追加を Reduce 処理として行う．この新しい中心軌跡デー
タは 1 行と微量なため Broadcast して，入力軌跡データの分散ドで独立して並列実行するため，計算負荷に偏りがあるほど待配置はそのままに Join することで効率的に，入力軌跡と中心

ち時間が増え非効率となる．そのため軌跡クラスタリングで頻軌跡の類似度を測り所属クラスタを更新する Map 処理を行う

出する類似度計算や類似マッチングの計算量は均一にすることことができる．この Broadcast Join の 2 回目以降は，計算グが望ましい．詳しくは次節にて述べるが，この計算量は両軌跡

ラフの系統である lineage を切るために一度外部出力したのち再読み込みすることが推奨される．なぜなら Apache Spark な擬似コード 2 CDTW の動的計画法
Input: 入力軌跡 P, Q
Output: CDTW resultfor i ← 1 to length(P ) dofor j ← 1 to length(Q) do
if i = 1 and j = 1 thenMA1,1 ← ((p1 , q1 ))else if j = 1 thenMAi,1 ← append(MAi−1,1 , (pi , q1 ))
図2else if i = 1 thenp3 と [q4, q5] の内点までのマッチングを参照して，p4 と [q4, q5]

qq ← argminq∈[qj−1 , qj ] s(p1 , q)の内点までのマッチングを探索する場合

MA1,j ← append(MB 1,j−1 , (p1 , qq))else
qq ← argminq∈[MAi−1,j,i+j−1,2 , qj ] s(pi , q)pairsA ← append(MAi−1,j , (pi , qq))
qq ← argminq∈[qj−1 , qj ] s(pi , q)pairsB ← append(MB i,j−1 , (pi , qq))
if ﬁxedCDTW(pairsA) < ﬁxedCDTW(pairsB ) thenMAi,j ← pairsA
else
MAi,j ← pairsB
if i = 1 and j = 1 thenMB 1,1 ← ((p1 , q1 ))図 3 [p3, p4] の内点と q4 までのマッチングを参照して，p4 と [q4, q5]の内点までのマッチングを探索する場合

else if i = 1 thenMB 1,j ← append(MB 1,j−1 , (p1 , qj ))else if j = 1 then

どの実行エンジンは，出力を求められてから lineage を辿って

pp ← argminp∈[pi−1 , pi ] s(p, q1 )実行計画を立てるものの，繰り返し処理の中で複数回参照されMAi,1 ← append(MAi−1,1 , (pp, q1 ))るサブグラフが展開されてしまうと計算グラフが指数爆発して

else

しまい，ボトルネックになってしまうからである．なお，このpp ← argminp∈[MB i,j−1,i+j−1,1 , pi ] s(p, qj )入力軌跡は次の繰り返しで 2 回使うためキャッシュする．

pairsA ← append(MB i,j−1 , (pp, qj ))pp ← argminp∈[pi−1 , pi ] s(p, qj )ステップ「2. 中心軌跡の更新」では，入力軌跡に Join 済み

pairsB ← append(MAi−1,j , (pp, qj ))である所属クラスタの中心軌跡との類似マッチングを Map 処

if ﬁxedCDTW(pairsA) < ﬁxedCDTW(pairsB ) then

理として行う．それから所属クラスタ番号と中心軌跡を成す点

MB i,j ← pairsA

列のインデックスによる kl 個の複合キーによって Shuﬄe して，

else

それぞれの中心点を算出する Reduce 処理を行う．さらに所属

MB i,j ← pairsB

クラスタ番号のみをキーに Shuﬄe して，中心点をインデック
スによってソートして新しい中心軌跡として更新する Reducei ← length(P )処理を行う．この新しい中心軌跡データは k 行であり一般的にj ← length(Q)n よりも充分に小さいため Broadcast して，入力軌跡データのpairsA ← append(MAi,j , (pi , qj ))分散配置はそのままに Cross Join することで効率的に，全入

pairsB ← append(MB i,j , (pi , qj ))力軌跡と全中心軌跡の組み合わせデータを作ることができる．

if ﬁxedCDTW(pairsA) < ﬁxedCDTW(pairsB ) thenステップ「3. 所属クラスタの更新」では，全入力軌跡と全中
心軌跡の類似度を算出する Map 処理を行う．それから所属ク

result ← ﬁxedCDTW(pairsA)
else
result ← ﬁxedCDTW(pairsB )ラスタ番号のみをキーに Shuﬄe して，最も類似している中心
軌跡のクラスタに所属を更新する Reduce 処理を行う．
以上のステップ「2. 中心軌跡の更新」とステップ「3. 所属ク
ラスタの更新」を iter 回繰り返すことで，(k, l)-clustering の近似解を得る．

3. 2 演算回数が均一な CDTW の動的計画法
前節で述べたとおり MapReduce モデルは，Join を含む Shuf-ﬂe フェーズにて計算ノード間で通信を行いデータを再配置して，次の Shuﬄe フェーズまでは各計算ノードで独立して並列実行するため，計算負荷に偏りがあるほど待ち時間が増え非効率となる．そのため図 1 で頻出する類似度計算や類似マッチン

4. 2 実装グの計算量は均一にすることが望ましい．この前提において，

提案分散データフローは Apache Spark 3.3.0 を基盤として，先行研究の双方向ダイスクトラ法 [10] のような計算量に偏りがSpark MLlib の Estimator を継承したクラスとして Scala 言語

ありその予測も困難であるようなアルゴリズムは適していない．

にて実装した．提案 CDTW 計算とマッチングは Spark SQL 関

対して離散的な DTW は素朴な動的計画法で解ける代表的なア数として実装して，前述の Estimator 継承クラスの内部で呼びルゴリズムであり，長さ l の軌跡と長さ m の軌跡について支配出した．この SQL 関数は Apache Spark の表形式データ構造的である 2 点間の類似度の演算回数は lm 固定であることが保Dataset/DataFrame の内部を直接操作するものであり，UDF証される．

を用いた実装と比べてデータ変換のオーバーヘッドが少ない実

そこで CDTW でも動的計画法を用いた近似計算のアルゴリ装となっている．これらを利用して，本実験では (k, l)-median

ズムを，擬似コード 2 のとおり提案する．ここで入力軌跡 P ,Qの問題設定のなか各アルゴリズムについて，入力軌跡の簡約について，メモ行列を二つ用意する．一つ目の行列 MA は，p1

は配列インデックスのサンプリング，初期中心軌跡の簡約は折から pi までの部分軌跡，q1 から [qj−1 , qj ] の内点までの部分

れ線上の等距離サンプリング，中心点は重心，2 点間の類似度

軌跡，とのマッチングと CDTW をメモする行列である．二つは平方ユークリッド距離，として実装した．またパラメータは目の行列 MB は，p1 から [pi−1 , pi ] の内点までの部分軌跡，q1

k = 16，l = 32，m = 32，iter = 20 を設定した．入力についから qj までの部分軌跡，とのマッチングと CDTW をメモすては，データセットの CSV ファイル群の選択によって軌跡数る行列である．この二つのメモ行列を使って軌跡間のマッチン

n を変化させ，スケーラビリティを検証できるようにした．

グを貪欲に探索する．探索中のマッチングを所与のものとした

CDTW を ﬁxedCDTW(·) とする．

比較対象としては，(k, l)-median の先行実装 [11] を用いた．
この先行実装は C++言語によって開発されており，共有メモリ

動的計画法における漸化式のキーアイディアを図 2 と図 3 に型の並列ライブラリ OpenMP によって部分的にマルチスレッ

示す．p4 と [q4, q5] の内点までのマッチングを探索する場合，

ド化されている．ただしハードコーディングされている部分が

図 2 では p3 と [q4, q5] までのマッチングを M 1 から参照して，あるため，本比較実験では main 関数のみ差し替えた．パラメー

p4 から [q4′ , q5] の最も類似度の小さい点へのマッチングを追加

タは提案手法と同様に k = 16，l = 32，m = 32，iter = 20 をする．ここで q4′ は参照したマッチングにおける [q4, q5] の内点設定しているが，中心軌跡の更新時にコストが改善されない場である．図 3 では [p3, p4] の内点と q4 までのマッチングを M 2

合は iter 回ループせずに早期打ち切りする工夫が為されている．

から参照して，p4 から [q4, q5] の最も類似度の小さい点への各アルゴリズムも提案実装とできるかぎり同様のものを設定しマッチングを追加する．この二つのうち，より ﬁxedCDTW(·)ているが，CDTW 計算として双方向ダイスクトラ法を用いてが小さいものを p4 と [q4, q5] の内点までのマッチングを決定いること，初期中心軌跡の簡約として CDTW による貪欲法をする．

用いていることが異なる．なお CDTW 計算中に C++の例外

このようにして二つのメモ行列を使う動的計画法によって，が稀に発生することがあり，その場合はフレシェ距離にフォー

P の節点から Q の内点へのマッチング，Q の節点から P の内

ルバックするように関数をラップした．入力については 1 日分

点へのマッチング，その l + m 個の最適な順番を貪欲に探索すのデータ (2012 年 10 月 14 日) に絞って，先行実験と同様に軌ることができる．このアルゴリズムは長さ l の軌跡と長さ m の跡ごとのファイル群に事前変換し，その読み込み数によって n軌跡について，2 点間の類似度の演算回数は 4lm で固定であるを変化させ，スケーラビリティを検証できるようにした．

ことが保証される．

4. 3 実 行 環 境

4 実

験

4. 1 データセット

実験環境は，Amazon Web Services の東京リージョンで構築した．提案実装については，Apache Spark のマネージドサービスである Amazon EMR 6.9.0 を利用した．Apache Spark

軌跡クラスタリングの対象として，実測によるオープンデー

クラスタを構成するインスタンスとしては，マスターノード

タのうち最大規模のものである Datasets from the ATC shop-に m6i.4xlarge (16vCPU， 64GiB memory)，コアノードに

ping center [18] を用いた．これは大阪市のショッピングセン

m6i.12xlarge (48vCPU， 192GiB memory) を採用し，コア

ターで延べ 92 日間に渡り 3D センサで計測された人物位置のノードの台数を変えることによりスケーラビリティを検証で追跡データセットであり，複数の CSV ファイルから構成されきるようにした．Apache Spark クラスタのパラメーターにる．本実験では 36 億レコードを日付ファイル名および人物 ID

ついては，公式ブログの推奨 [19] に従ってドライバーと各エフィールドの複合キーで集約したのち時刻フィールドで昇順にグゼキューターに割り当てる CPU 数やメモリ数を設定した．

ソートすることで 357 万軌跡を得た．また位置座標は X フィー

Apache Spark Web UI から確かめられる Total uptime を実行

ルドと Y フィールドのみを利用しており，2 次元軌跡として時間として計測し，Task Time を Total Time で割ることによ扱った．

りタスク CPU 使用率を求めた．
先行実装については，Amazon EC2 の Ubuntu 20.04.1 LTS
イメージを利用した．インスタンスとしては m6i.16xlarge図5

軌跡数に対する実行時間の評価

k = 16, l = 32, m = 32, iter = 20

図4

提案実装によるクラスタリング結果

k = 16, l = 32, m = 32, iter = 20, n = 3 578 281
図6(64vCPU， 256GiB memory) を採用し，Amazon EMR のマ

軌跡数に対するタスク CPU 使用率の評価

k = 16, l = 32, m = 32, iter = 20

スターノード 1 台とコアノード 1 台を合わせた vCPU 数とメモリ量が等しくなるようにした．time コマンドによって出力されを評価した結果を図 5，6，7 に示す．提案手法については，コる elapsed time を実行時間として計測し，user time を elapsed

アノード 1 台，4 台，16 台の Apache Spark クラスタにて，軌time で割ることでタスク CPU 使用率を求めた．

跡数 n = 17 558 (計 1 日)，n = 85 413 (計 3 日)，n = 340 946

4. 4 実 験 結 果(計 10 日)，n = 1 099 538 (計 31 日)，n = 3 578 281 (計 92 日)
および比較のため n = 124，n = 1028 でクラスタリングをそれ

まず提案実装の妥当性確認のため，コアノード 4 台の Apache

ぞれ実行した．ただし 1 コアノードかつ n = 3 578 281 の場合

Spark クラスタにより全軌跡 n = 3 578 281 をクラスタリング

のみ，実行中にエラーが発生し計測できなかった．メモリ不足にしたのち，クラスタごとに 100 軌跡をサンプリングしたものをよるものと推測される．先行実装については，軌跡数 n = 128

図 4 に示す．軌跡ごとに始点から終点へ，水色から紫色へのグから n = 16 384 まで 2 の累乗数および比較のため n = 17 558

ラデーションをかけて描画しており，始点・終点・経路の近し(計 1 日) でクラスタリングを実行した．

い軌跡群が同じクラスタにまとめられていることを確認できる．

図 5 の実行時間については，軌跡数に関わらず提案実装の方

次に軌跡数 n を変化させながら，実行時間・タスク並列度・クが短い結果となった．n = 17 557 で先行実装が 4.4 時間，計算

ラスタリングコストを計測することで，そのスケーラビリティ

資源が同じコアノード 1 台の提案実装が 5.2 分と 50 倍以上速

5 結

論

本研究では軌跡クラスタリングについて，(k, l)-clusteringの MapReduce モデルに基づく分散データフローおよび，その中で支配的な類似度算出タスク群のため演算回数が均一な

CDTW の動的計画法を提案した．また人流軌跡の実データを用いて，軌跡数の増大に応じた計算資源を割り当て実行時間を抑えることで，その並列性が先行実装より高いことを示した．
そして 357 万軌跡という規模のクラスタリングも実用的に行えることを示した．
今後の展望としては，よりクラスタ数 k が大きい場合 k について逐次的な繰り返し処理となっている初期クラスタリングがボトルネックになることへの対処として，k-means|| [13] のような初期中心軌跡を一度に複数サンプリングするアイディアを取り入れ，より分散処理に適した軌跡クラスタリングの手法を
図7

軌跡数に対するクラスタリングコストの評価

k = 16, l = 32, m = 32, iter = 20

開発することが考えられる．またリアルタイムに収集される移動データについて，事前に学習したクラスタへの所属や中心軌跡との類似度を求めることで，オンライン異常検知に応用する

かった．そしてコアノード数を増やすことにより更に高速化でき，その度合いは軌跡数が増加してもあまり変わらない．実行時間が同等の結果を比べると，コアノード 1 台で n = 340 946
が 30 分，コアノード 4 台で n = 1 099 538 が 29 分，コアノー
ド 16 台で n = 3 578 281 が 35 分となり，おおむね軌跡数がことも期待できる．
な お 提 案 実 装 は Apache Spark 拡 張 ラ イ ブ ラ リ と し て

https://github.com/ToyotaInfoTech にて公開予定である．

6 謝

辞3 倍程度増えてもコアノード数を 4 倍程度増やせば実行時間

本研究の遂行にあたり，トヨタ自動車株式会社コネクティッ

を伸ばすことなくクラスタリングできたことが分かる．なおド先行開発部 InfoTech の吉岡顕主査，福島真太朗主幹，桑原n = 124，n = 1028 では，提案実装についてコアノード台数に

昌広主幹には熱心なご指導を頂きました．心から感謝いたしま

関わらず実行時間がほぼ一定となっている．これは扱うレコー

す．また，同室の園部竜也主任には日常的な議論において適切

ド数が少ないため，実際には Shuﬄe を行わずコアノード 1 台

な助言をいただきました．お礼申し上げます．

で処理するような実行計画が立てられたためと推測される．
図 6 のタスク CPU 使用率についても，軌跡数に関わらず提案実装の方が高い結果となった．先行実装の OpenMP は 64
スレッド認識しているため理想的な上限値は 6400%となるが，

n = 64 で 274%，n = 17 557 で 169%と，あまりインスタン
スのマルチコアを活かせていなかった．提案実装も n が少な
い内はあまり高くないものの n = 17 558 以降は軌跡数の増加に伴ってゆっくりと上限に達していく傾向が見てとれる．実験内の最大値としては，1 コアノード (計 64vCPU) で 3406%，

4 コアノード (計 208vCPU) で 10 775%，16 コアノード (計784vCPU) で 19 337%と，クラスタサイズに応じた高い並列性を実現している．
図 7 のクラスタリングコストについても，軌跡数に関わらず提案実装の方が低く抑えられ，安定性も良い結果となった．
ただし先行実装のコストは CDTW のフォールバックとしてフレシェ距離を設定した実行上の対応により，アルゴリズム本来の性能より悪くなっている可能性がある．また提案実装でコアノード数の増減によるクラスタリングコストへの影響はほぼ見られなかった．

文

献[1] 株 式 会 社 NTT ド コ モ. （ お 知 ら せ ）モ バ イ ル 空 間 統
計 の「 国 内 人 口 分 布 統 計（ リ ア ル タ イ ム 版 ） 」の 提 供 開
始. https://www.docomo.ne.jp/info/news_release/2019/12/03_00.html, December 2019. (visited on 01/10/2023).
[2] Google LLC.
感 染 症 対 策 の 専 門 家 を 支 援 。新 型 コ ロ
ナ ウ イ ル ス 感 染 症（covid-19）と 戦 う 上 で 役 立 つ デ ー タを.
https://japan.googleblog.com/2020/04/covid-19community-mobility-reports.html, April 2020. (visited on
01/10/2023).
[3] トヨタ自動車株式会社. トヨタ自動車、ビッグデータを活用した新しい情報サービスの提供を開始. https://global.toyota/jp/detail/1960877, May 2013. (visited on 01/10/2023).
[4] 総 務 省.
電 気 通 信 サ ー ビ ス の 契 約 数 及 び シェア に 関
す る 四 半 期 デ ー タ の 公 表（ 令 和 3 年 度 第 3 四 半 期（12 月 末 ） ）. https://www.soumu.go.jp/menu_news/snews/01kiban04_02000205.html, March 2022. (visited on
01/10/2023).
[5] 株式会社富士経済. コネクテッドカー (つながる車) の世界市場を調査―2035 年市場予測 (2020 年比)―. https://www.fujikeizai.co.jp/market/detail.html?cid=21122, December
2021. (visited on 01/10/2023).
[6] Dimitrios Kotsakos, Goce Trajcevski, Dimitrios Gunopulos,
and Charu C. Aggarwal. Time-series data clustering. In
Data Clustering: Algorithms and Applications, chapter 15,
pp. 357–380. CRC Press, August 2013.

[7] Anne Driemel, Amer Krivošija, and Christian Sohler. Clustering time series under the fréchet distance. In Proceedingsof the 2016 Annual ACM-SIAM Symposium on Discrete
Algorithms (SODA), Proceedings, pp. 766–785. Society for
Industrial and Applied Mathematics, December 2015.
[8] Kevin Buchin, Anne Driemel, Natasja van de L’Isle, andAndré Nusser. klcluster: Center-based clustering of trajectories. In Proceedings of the 27th ACM SIGSPATIALInternational Conference on Advances in Geographic Information Systems, SIGSPATIAL ’19, pp. 496–499, New York,NY, USA, November 2019. Association for Computing Machinery.
[9] Kevin Buchin, Anne Driemel, Natasja van de L’Isle, andAndré Nusser. Gitlab - klcluster sigspatial19. https://
gitlab.com/anusser/klcluster-sigspatial19/, December 2019. (visited on 01/10/2023).
[10] Milutin Brankovic, Kevin Buchin, Koen Klaren, André
Nusser, Aleksandr Popov, and Sampson Wong. (k, l)medians clustering of trajectories using continuous dynamic
time warping. In Proceedings of the 28th International Conference on Advances in Geographic Information Systems,
SIGSPATIAL ’20, pp. 99–110, New York, NY, USA, November 2020. Association for Computing Machinery.
[11] Milutin Brankovic, Kevin Buchin, Koen Klaren, André
Nusser, Aleksandr Popov, and Sampson Wong. Github mesoptier/trajectory-clustering at v1.0. https://github.
com/Mesoptier/trajectory-clustering/tree/v1.0, November 2020. (visited on 01/10/2023).
[12] Jeﬀrey Dean and Sanjay Ghemawat. MapReduce: simpliﬁed
data processing on large clusters. Commun. ACM, Vol. 51,
No. 1, pp. 107–113, January 2008.
[13] Bahman Bahmani, Benjamin Moseley, Andrea Vattani,
Ravi Kumar, and Sergei Vassilvitskii. Scalable K-Means++.
March 2012.
[14] Apache Software Foundation. Clustering - mllib - spark
1.5.0 documentation. https://spark.apache.org/docs/
1.5.0/mllib-clustering.html, May 2015. (visited on
01/10/2023).
[15] Maike Buchin. On the computability of the Frechet distance
between triangulated surfaces. PhD thesis, 2007.
[16] Anil Maheshwari, Jörg-Rüdiger Sack, and Christian Scheffer. Approximating the integral fréchet distance. Comput.
Geom., Vol. 70-71, pp. 13–30, February 2018.
[17] Teoﬁlo F. Gonzalez. Clustering to minimize the maximum
intercluster distance. Theor. Comput. Sci., Vol. 38, pp.
293–306, January 1985.
[18] Dražen Brščić, Takayuki Kanda, Tetsushi Ikeda, andTakahiro Miyashita. Person tracking in large public spaces
using 3-D range sensors. IEEE Transactions on HumanMachine Systems, Vol. 43, No. 6, pp. 522–534, November
2013.
[19] Karunanithi Shanmugam. Best practices for successfully
managing memory for apache spark applications on amazon
emr. https://aws.amazon.com/jp/blogs/big-data/bestpractices-for-successfully-managing-memory-for-apachespark-applications-on-amazon-emr/, April 2019. (visitedon 01/10/2023).