どんなもの？

類似軌道の算出アプローチであるtrajGATの提案．先行研究と比較しSOTA

先行研究と比べてどこがすごい?

長期のシーケンスに対しての類似軌道が劇的に低下していた．trajGATにより長期記憶に対応

技術や手法のキモはどこ？

GATベースのグラフ方法の導入．グリッドベースの軌跡の埋め込みにPR quadtreeを導入し，Node2vecでベクトル化

どうやって有効だと検証した？

XianとPortoの軌道データで実験

議論はある？

やはりスポーツの様なマルチトラジェクトリーへの対応は議論がされてない．

次に読むべき論文は？

• Deep representation learning for trajectory similarity computation.
• A generic seed-guided neural metric learning approach.

読書時間

2h

TrajGAT：軌跡類似度計算のためのグラフベースの長期依存性モデリングアプローチ

ABSTRACT 軌跡の類似性を計算することは、クラスタリング、予測、異常検知など、様々な空間-時間アプリケーションにとって重要かつ基本的なタスクである。従来の類似性メトリクス（DTWやHausdorffなど）は、計算量が2次関数的であるため、大規模データには適用できない。この問題を解決するために、類似度計算の複雑さを軽減しながらメトリクス空間を近似する、多くの軌跡表現学習技術が提案されている。しかし、これらの技術はRNNバックエンドに基づいて設計されているため、長い軌跡では深刻な性能低下を引き起こす。本論文では、階層的な空間構造を明示的にモデル化し、長い軌跡の類似性計算の性能を向上させる、新しいグラフベースの手法、すなわち、TrajGATを提案します。TrajGATは、グラフ構築と軌跡エンコードという2つの主要なモジュールから構成される。グラフ構築では、まず空間全体の階層構造を構築するためにPR quadtreeを採用し、次に元のレコードとquadtreeのリーフノードに基づいて、各軌跡のグラフを構築する。軌跡のエンコードについては、Transformerのselfattentionをグラフattentionに置き換え、生成されたグラフの軌跡を表現するエンコーダを設計しています。

1 はじめに 軌跡の類似性計算は、時空間データ解析において不可欠なタスクである。DTW[33]、Hausdorff[2]、ERP[6]などの古典的な類似尺度は、軌跡の本質的な類似性を定量化するために提示されており、軌跡のクラスタリング[31]、位置予測[17、29]、異常検知[15、18、40]などで応用することができる。一方、これらの尺度の2次的な複雑さは、大規模な軌跡解析への適用を制限し、軌跡の類似性を計算するための事実上のボトルネックとなっている。

この問題に対処するため、Hausdorff [8]のローカライズハッシュ（LSH）やDTW [20]のラッピングウィンドウの制約など、近似類似性尺度の様々な戦略が提案されてきた。しかし、これらの手法は、ある特定の尺度に対して設計されており、他の尺度には適用できない。近年、軌跡の類似性計算には、Deep Representation Learning（DRL）法[12, 14, 16, 25, 30, 35, 36]がうまく適用されている。DRL法は、軌跡をベクトルで表現し、ベクトルのメトリクス空間を学習することで、類似度を近似する手法である。従来の近似手法と比較すると、DRL手法は様々な類似メトリクスに対して高速かつ一般的である。しかしながら、既存のDRL法をtop-K類似性検索で評価したところ、長い軌跡ではその性能が劇的に低下することがわかった。図1 (a) に示すように、NeuTraj や Traj2SimVec などの最先端手法のヒット率トップ10は、長い軌道で少なくとも40%低下していることがわかります。同様の結果は、他の距離メトリクスでも観察されます。この問題を解決することは、DRLに基づく類似性計算にとって不可欠である。

図1：TrajGATの動機。長い軌跡で性能が低下する理由を(b)に示す。 Taは長い軌跡、Tbは短い軌跡である。 赤の実線は、RNNが捉えたアライメントを示す。

現在のDRL手法は、長期的な依存関係をモデル化することができないため、長い軌跡で性能が低下してしまう。一方、類似性指標の定義によれば、2つの軌道の類似性は、通常、いくつかのレコードの整列によって支配されている。 図1 (b)に示すように、長い軌跡と短い軌跡の間の整列は、異なる領域にまたがっています。 現在の手法では、リカレントニューラルネットワーク（RNN）を用いて、類似性の関係を維持したまま軌跡をエンコードしています。これらのRNNモデルは、最適化にBPTT（backpropagation through time）を用いており、最新の観測記録の短期的な依存性しか捉えることができず、長いシーケンスに拡張することは困難である[37]。その結果、既存のモデルでは、長い軌跡のアライメント情報を捉えることができない。一方、DRL法は等しい大きさのグリッドの共有表現を学習することで空間情報をモデル化するため[16, 28]、シーケンスモデリングにおいて離れた場所にあるレコードの接続が弱くなる。また、レコードは空間的に不均一に分布している。グリッドセルによっては、その表現を学習するのに十分なデータがないため、長い軌跡での性能がさらに悪化する。したがって、類似度を計算するためには、長い軌跡の長期的な依存関係を捉えることが重要かつ不可欠である。

しかしながら、軌跡の類似性計算のために長期的な依存関係をモデル化することは、容易ではありません。長いシーケンスをモデル化するための既存の研究は、RNNベースの方法[4、22]、メモリネットワークベースの方法[5、11]、Transformerベースの方法[7、26、39]という3つのグループに分類することができる。しかし、そのどれもが我々のタスクでは使用できない。RNNベースの手法では、最適化において補助的な損失が採用され、モデルの学習が困難になるだけでなく、メトリクス近似のパフォーマンスが最適でなくなる。メモリネットワークベースの手法は、メモリ構造のヒューリスティックな設計に依存しており、通常、逐次的な関係を捉えることができない。Transformerは、 self-attention operationsを積み重ねることで、長期的な依存関係を捉えることに優れていることを実証している。selfattention の効率を向上させるためのアルゴリズム [32, 39] がいくつか提案されているが、それらは空間情報を利用できないため、軌跡の類似性計算に直接利用することはできない。

本論文では、軌跡類似度計算のために、長期的な依存関係を捉える新しい手法、すなわち、TrajGATを提案する。TrajGATは階層的な空間構造を軌跡エンコードに統合し、長い軌跡における領域間の関係を明示的にモデル化するだけでなく、TransformerのselfattentionによるGPUメモリ需要を制約する。具体的には、TrajGATはまずPR quadtree[21]を用いて階層構造を構築する。すべての4分木の葉のグリッドの位置記録はバランスされており、グリッド表現の等価な学習を保証する。四分木をベースに、元レコードとその関連グリッドの間の余分なエッジを巻き込んで、すべての軌跡のグラフを構築する。そして、グラフアテンション(GAT)に基づくTransformerを設計し、軌跡グラフを埋め込みベクトルに符号化する。GAT-basedTransformerは、GPUのメモリコストを削減するために、すべてのペアレコードのAttentionを計算する代わりに、軌跡グラフのエッジに沿った情報のみを集約しています。最後に、埋め込みベクトルをメトリクス学習フレームワークに供給し、類似性メトリクスを近似的に求める。本論文の主な貢献は以下のように要約される：

• 長い軌跡の類似性計算における性能低下問題を解決するための新しい方法を提案する。我々の知る限り、TrajGATはGPS軌跡モデリングのための、長期依存性を捉えた初の深層学習手法である。
• 我々は、階層的な空間構造を明示的に統合し、軌跡をグラフに変換するGATベースのTransformerを設計し、軌跡エンコードに用いる。GPUのメモリ使用量を削減しながら、領域横断的な関係をモデル化することができる。
• 2つの公開軌跡データセットを用いた広範な実験により、TrajGATは長い軌跡の類似性計算性能を向上させるだけでなく、混合軌跡においても最先端の手法を凌駕することができる。

2 関連する研究成果

本節では、TrajGATに関連する既存の研究を、(1)軌跡の類似性計算、(2)長尺シーケンスモデル、(3)グラフ変換の3つの観点から概観する。

軌跡の類似性計算

既存の軌跡類似度計算手法は、非学習ベースの手法と学習ベースの手法の2つに大別される。非学習ベースの手法[1, 3, 8, 20]の多くは、各軌跡を空間曲線として捉え、計算を簡略化するために計算幾何学を用いている。これらの手法は、主に手作業で作られた発見的なルールに依存しており、その結果、パフォーマンスが低下する可能性がある。さらに、これらの手法は特定の距離のために設計されているため、他の類似メトリクスに適応することは困難である。近年、AI[27]の発展に伴い、軌跡の時空間特性をベクトルに埋め込み、類似度を計算する学習ベースの手法[12, 16, 25, 30, 35, 36]が多数提案されている。しかし、これらの手法は、シーケンスのモデリングにRNNを用い、パラメータの最適化にBPTTを利用する。これらの方法は短い軌跡のデータセットでは良好な性能を発揮するが、長い軌跡のデータセットでは性能低下に悩まされる。

長いシーケンスのモデリング。 長期依存性をモデル化するために、既存の作品は3つのグループ、すなわちRNNベースの方法、メモリネットワークベースの方法、Transformerベースの方法に分類することができる。Trinhら[22]は、教師なし損失を追加することで、RNNの長期依存性を捕らえる能力を向上させた。Francoisら[4]は、長期的な依存関係の原理的な推定手順を提案し、長いシーケンスのモデリングのためにEvolutiveRNNsを設計した。これらのRNNベースの手法は、最適化のための外部目標も関与しているため、モデルの学習が難しく、最適でない性能につながる。メモリネットワークに基づく手法[5, 11]は、メモリテンソルを共有することで長期的な依存関係をモデル化します。しかし、メモリテンソルの構造は手作業による設計に基づくものであり、拡張することはできない。近年、長配列のモデリングのために、Transformerベースのアプローチ[26, 39]が多く提案されている。しかし、これらのモデルのGPUメモリコストは、シーケンス長の増加とともに二次関数的に拡大するため、その利用は制限される。さらに，既存のすべてのロングシーケンスモデリングモデルは，軌跡の類似性計算のために重要な空間情報を捕らえることができない．

グラフ変換器。 多くの研究[13, 34, 38]では、グラフニューラルネットワークとTransformerを組み合わせて、シーケンスの構造情報を捉えることが検討されている。しかし、これらの方法はいずれもグラフのモデリングを必要とし、軌跡データから得ることは容易ではない。文章などのシーケンシャルなデータに対してグラフを構築する研究がある[32]。しかし、これらの手法は、時空間特性の特殊性から、軌跡をモデル化することができない。

3 前提となるもの 3.1 問題の定義

N個の軌跡を含む軌跡データベースTと軌跡類似度尺度f (-, -)を考える。各軌跡T∈Tは、移動する物体の軌跡を記録した場所の集合である。一般性を失うことなく、ここでは2次元の軌跡を考える。各軌跡T = [X1, ...,Xt, ...]はタプルの列であり、Xt (latt ,lont )はオブジェクトのt番目の位置である。任意の2つの軌跡Ti ,Tj∈T に対して、f (Ti ,Tj) はTi とTj の間の類似性を測定する。ここで、f (-, -) は、DTW、Hausdorff、Fréchet距離、または他の軌跡の類似性尺度である可能性がある。

我々の課題は、類似関数f (-, -)の下でTからの軌跡のアドホックなペアの類似性を計算することである。しかし、一般的な類似性尺度では、一対の軌跡の類似性を計算するのに2次関数的な時間的複雑さが発生する。既存のDRLベースの手法[16, 30, 35]は、長い軌跡の場合、深刻な性能低下に悩まされています。したがって、研究課題は、長短両方の軌跡における差分｜f (Ti ,Tj ) - д (Ti ,Tj )｜を最小化しながら、д (Ti ,Tj )を効率的に計算するような近似類似性関数д (-, -)をいかにして学ぶか、である。

3.2 TrajGATの概要 図2に示すように、TrajGATは、グラフベースのメトリクス学習フレームワークである。階層構造モデリング、グラフベースの軌跡エンコード、メトリクス学習に基づく最適化の3つの主要モジュールから構成される。Tの軌跡がある領域Aに分布していると仮定して、TrajGATは以下のように軌跡の類似性を計算する：

• まず、Point-Region(PR)四分木を用いて、Aを階層的に分割し、Hとする。このような情報を軌跡エンコードに組み込むために、まずHに対して事前学習を行い、階層的な情報を保持するグリッドセルの埋め込みを学習する。
• グラフベースの軌跡エンコードでは、TrajGATはHの木構造を利用して、各軌跡TをグラフT дに変換する。T дをエンコードし、GPUのメモリ使用量を削減するために、我々はグラフベースのTransformer層を提案し、階層構造だけでなく順序関係もモデル化して軌跡エンコーディングを生成する。
• 最適化のために、軌跡ペアの類似性を適合させるためにランキングロスを利用し、教師情報を学習しやすくするために正規化アプローチを提案する。

4 メソッド 本節では、TrajGATの詳細を導入するための説明を行う。TrajGATは、階層構造モデリング、グラフベースの軌跡エンコード、メトリクス学習に基づく最適化の3つの主要モジュールから構成されている。そして、各モジュールの構造をそれぞれ定義する。

4.1 階層構造モデリング 図2に示すように、まずTの軌跡を利用して、階層的な空間構造を表す四分木Hを構築する。そして、Hの中のグリッドセルの埋め込みを事前に学習する。以下、この2つの手順について説明する：

4.1.1 階層構造構築。 TrajGATは、階層的な空間情報をモデル化するためにPR quadtree[21]を採用している。図3に示すように、領域を4つの等しい象限、副象限に再帰的に分解するものである。ある領域A内のTについて、PR quadtreeを用いて以下のように階層構造を構築する：

1. まず、すべての軌跡から位置記録を抽出し、重複する位置のジオ座標が等しい位置集合を構築する。
2. 経験的な閾値δを用いて、どのリーフノードもδ以上の位置を持たないまで、再帰的に領域を分解し、子ノードとしてサブリージョンを生成する。
3. 最後に、葉ノードの位置リストを省略し、Aの階層的分割のみを階層構造として採用する。これをHと表記する。

図示のように、図3は、δ＝2での玩具の階層構築プロセスを提供する。全領域を3層、13グリッドセルに重複なく分解している。HはAの増加に伴って変化するが、類似性計算のための適切な構造は安定している傾向があると主張する。これは、Hが部分的なデータで構成でき、他の新しい軌跡に対しても一般化されることを示すものである。このことは、付録A.3の実験によって証明する。したがって、TrajGATの以下のモジュールは、Hに基づいて設計されている。

4.1.2 H.のセルエンベッディングの学習 軌跡エンコードのために階層的な情報を統合するために、Hに対して事前学習を行い、グリッドセルMHの埋め込みを得る。HにはK個のグリッドセルが存在すると仮定し、Hをグラフとして扱い、その上でNode2Vecを行う。具体的には、Hからパスのセットをサンプリングし、多様な近傍を探索しながらネットワーク近傍を保存する尤度を最大化することで、グリッドセルの埋め込みベクトルを学習する。サンプリングされたクロスレイヤーパスを用いて、学習された埋め込み行列MH∈dh×Nhは、Hの階層的な情報を捉える（dhはグリッドセルの埋め込みの次元）。その後、MHを利用して軌跡エンコードを強化する。

4.2 グラフベースの軌跡エンコード 軌跡エンコードでは、まず T の各軌跡に対してグラフを作成し、軌跡グラフの埋め込みを生成する GAT-based Transformer を提案する。

4.2.1 軌跡グラフの構築。 軌跡 T が与えられたとき，H のグリッドセルを考慮してグラフ T д = (N, E) を構成する．ここで，N はノード集合，E は辺集合である．図4に示すように、T дは元のレコードだけでなく、Hの階層的な情報も含んでいる。ここでは、グラフ構造とノードの特徴の構築についてそれぞれ説明する。

グラフ構造の構築 このパートでは、ノードとエッジの構築プロセスを順次導入するためのものである。 T дのノードは、Tの原記録とHの関連するグリッドセルから、異なる階層、すなわちN＝Nr∪Nhから抽出される。 具体的には、Tの長さをLとすると、まず、すべてのレコードのノード、すなわち、Nr＝{n1, ...nL,}を構築する。各ノードniには、元のレコードの情報がすべて含まれている。Nrをレイヤ0ノードとして、前のレイヤノードに関連する階層グリッドセルが追加されていない場合は、再帰的に巻き込む。図4に示すように、レイヤー1ノードを構築するために、TrajGATはレイヤー0ノードをHのリーフグリッドセルに対する座標でグループ化する。同様に、レイヤー2ノードについては、TrajGATはHの最初の非リーフノードに従ってレイヤー1ノードをグループ化する。Hから抽出した全てのノードについて、Nh = {N 1 h , ..., N η h }として表し、ηは抽出レイヤーとN i hは各層のサブセットノードを示す。なお、ηは重要なハイパーパラメータであり、スペースの関係上、付録A.3でその効果を研究する。

T дのノードを構築した後、エッジEを構築する。第一は，異なる層のノードを接続する層間エッジEc である．HのリーフグリッドセルはAのパーティションであるため，すべてのレコードの関連セルを求め，NrからN 1 hまでのエッジを追加する．したがって，H の木構造から他のクロスレイヤーエッジが抽出される．GPUのメモリ効率を向上させ、TrajGATの計算コストを削減するために、Nhの内層エッジのみを構築する。各層N i hについて、ノードが下位層で接続されていない場合、ノード間に完全接続のエッジを追加する。なお、E のすべてのエッジは無向性であり、メッセージはノードを双方向に通過することが可能である。グラフを構築するプロセスを図4に示します。

ノードの特徴構築。 軌跡グラフ T д = (N, E) を同種グラフとみなし、Nr と Nh の両方のノードを等しく扱う。N のノード特徴は、座標特徴 f l 、領域特徴 f r 、階層構造特徴 f h の 3 つの側面から構成される。次に、その構築手順をそれぞれ説明する。

Nの各ノードは、領域Aにおける空間要素（位置または矩形領域）を表す。Nrのノードについては、その関連レコードの位置を直接、関連位置として利用する。Nhのノードについては、その中心位置を関連位置として選択する。なお、軌跡の位置はすべてGPS座標であるため、まずmin-max正規化関数で正規化し、多層パーセプトロン（MLP）を用いて非線形変換を行う。Xi = (lati , loni ) をノードni∈Nの関連位置と仮定すると、位置特徴は以下のように構成される：

さらに、領域の大きさをモデル化するために、領域特徴を採用する。niがNhのノードである場合、その関連するグリッドセルの幅wiと高さhiを抽出し、非線形変換を行い、領域特徴を得る。を得る。 NiがNrにある場合、デフォルト値wi = 0;hi = 0をその領域特徴量として設定する。この操作は次のように定式化される：

階層的特徴については、事前に学習されたHの埋め込み行列を直接利用する。Nrのノードについては、MHにすべてのオリジナルレコードの階層的特徴を表す特別なキーを一つ追加する。このように、異なる軌跡の空間的に近接したレコードは、同じ階層的特徴を共有することで接続される。

f h i = Embedding(MH , ni )

要約すると、特定のノードni∈Nに対して、3つの特徴量を連結し、ノード特徴量を得ることができる：

一般性を損なわない範囲で、f l i 、f r i 、f h i の次元を df に等しいと仮定する。ノード特徴 fi の次元は d = 3 × df である。

4.2.2 GATベースの軌跡エンコード。本節では、軌跡をエンコードするための核となるGATベースの軌跡エンコードを導入する。これは、グラフを入力とし、GPUのメモリコストが高いという問題を解決しながら、Transformerの主要なアイデアを踏襲している。図5に示すように、重要な洞察は、類似性計算のためにすべてのレコードが他のすべてのレコードに出席する必要がないことです。GATベースのTransformerは、構築された軌跡グラフと協調することで、レコードから離れた異なるグリッドセルに出席するレコードを可能にします。(1)軌跡の順序情報と位置情報の両方を保持するPosition Encoding、(2)グラフattention操作を利用して長い軌跡をモデル化するGAT-based Transformerである。以下、2つの設計について説明する。

Position Encoding. 軌跡グラフをエンコーダに入力する前に、まず、レコードの順序情報とノードのグラフ関係の両方を含む、Position Encodingを導入するためのものである。順次情報をモデル化するために、T д上の擬似レベルオーダートラバサルを設計する。まず、空のリストLを利用して、ノード列を保存し、T дのノードをレベル0からレベルηにそれぞれ追加する。レベル0（Nr）のノードについては、Tの元のシーケンスを採用し、関連するノードを順次Lに追加していく。η≧i＞0のレベル-iのノードについては、N h i-1 の接続ノードの出現順序に従って、繰り返しなくLに追加する。Lの構成は図4の通りである．

Lの連続したノードを用いて、Vaswaniら[23]が提案した正弦波値を位置情報のエンコードに採用する。この方法は、正弦波位置エンコーディングと呼ばれる絶対位置エンコーディングである。LがM個のノードを含むと仮定し、以下のように逐次位置埋め込みを構築する：

ここで、i = [1, ..., M]、j = [1, ...,d/2] とする。ノードni∈Nの逐次位置Encodingについては、λ s i∈R d/2 と表記する。T дのグラフ関係をモデル化するために、ラプラシアン位置エンコード[9]を採用し、相対距離情報をエンコードする。すなわち、近くのノードは類似の位置特徴を持ち、遠いノードは非類似の位置特徴を持っている。

ここで、Aは隣接行列、Dは次数行列、Λ,Uはそれぞれ固有値と固有ベクトルに相当する。また、λiはノードiのラプラシアン位置エンコーディングを示し、toppはΛの最小の非自明なp個をスライスする操作を示し、ノードniの位置の固有ベクトルを関連付ける。この固有ベクトルを完全連結層に供給することで、グラフの位置符号化（λ д i ∈ R d/2 とする）を得ることができる。

λsiとλдiの生成後、それらを連結して最終的な位置符号化ベクトルλiを得、それをノード特徴量と加算する。この結果は次のGAT-based Transformer Layerの入力とされる。

GATベースのTransformer Layer。 self-attention 操作のため、vanilla Transformer はすべてのペアワイズアテンションウェイトを計算する必要があり、GPU メモリ使用量が多いという問題に悩まされます。我々は、最大長1000の軌跡でおもちゃの実験を行った。24Gのメモリを搭載したNvidia 3090 GPUでは、vanilla transformerの最大バッチサイズは1であり、極めて非効率的です。一方、ほとんどの類似性測定は、Hausdorff、Fréchet、w-DTWのように、レコードペアの部分的なアラインメントで定義されていることがわかります。すべてのペアワイズアテンションを計算することは、軌跡の類似性計算において効率的でも必要でもない。そこで、iiを入力h 0 iとして、自己Attention層をグラフAttention層に置き換えて、軌跡埋め込みを得る。ある特定のノードni に対して、GAT-based Transformer層での演算は以下のように定義される：

ここで、Niはノードniの近傍、Qk, ℓ, K k, ℓ, V k, ℓ∈ R dk×d , Oℓ h∈ R d×d , k = 1～H は注意ヘッドの数を示す。数値的安定性のため、so f tmax内部の項の指数を取った後の出力は、（-5，5）の範囲に限定される。そして、Attention出力h ′ℓ+1 iは、残差接続とバッチ正規化モジュールを含むFeed Forward Network (FFN) に供給される。簡潔なため、Transformerと同じ操作の式は省略する。GATベースのTransformerのP層の後、我々はすべてのノードの隠れ表現、すなわち[h P 1 , ..., h P i , ..., h P M ]を得る。軌跡グラフT дの最終的な埋め込みを生成するために、ノードの埋め込みに平均読み出し関数を採用する。軌跡Tの埋め込みeは、e = PM i=1 h P i /Mとして計算される。グラフベースの軌跡エンコードの出力は、軌跡の類似性を測定するために使用することができる軌跡の埋め込みです。

4.3 最適化のためのメトリクス学習

TrajGATは、軌跡グラフの埋め込みに基づき、モデルパラメータを最適化するために、Deep Metric Learningのフレームワークを採用しています。T内の軌跡ペアのペアワイズ距離を含む距離行列Dが与えられたとき、我々は[28]を導入するための方法に従い、まずDを類似度行列Sに変換し、Sを教師情報として使用する、すなわち、Sij = exp(-θ Di,h ) max(exp(-θ D)) ここで、θは類似度の値分布を制御する調整可能なパラメータである。そして、T の軌跡は順次、モデル最適化のためのアンカー軌跡として採用される。

これまでの手法[28, 35]では、S の類似度をグランドトゥルースとして直接採用していた。しかし、Taの類似度のほとんどは小さな領域に集まる傾向があり、明確な教師情報を提供することができない。我々は損失を計算する前に、Taの類似性リストに対してガウス正規化を行う：

正規化後、Taの類似度分布は標準的なガウス分布になります。正規化後、Taの類似度分布は標準的なガウス分布に適合するため、TrajGATはより容易に教師情報を取得することができる。

Taの類似度に合うようにn個の軌跡がサンプリングされたと仮定すると、Taの損失を以下のように計算する。

ここで、д(Ti ,Tj ) = exp(-Euclidean(ei , ej ))は、2つの軌跡埋め込み間の類似度を計算し、rは、重み付け順位損失[28]によって計算されたサンプル重みです。最後に、Tの全体的な損失は、すべてのアンカー軌跡の損失の合計、すなわち、LT = P a ∈T Laである。TrajGATの全てのパラメータは、エンドツーエンドで更新することができる。バックプロパゲーションアルゴリズムでパラメータを更新し、最適化のためにアダムオプティマイザを採用する。

5 実証実験

本節では、TrajGATの性能を評価し、以下の問いに答える： - Q1: TrajGATの性能は、既存の軌跡類似性計算手法と比較してどのようなものであるか？- Q2: TrajGATは、軌跡埋め込みを生成するためのGPUメモリ使用量について、どの程度効率的か？- Q3: 提案する階層構造モデリングとグラフベースの軌跡エンコードはどのような機能を持つのか？

5.1 実験設定

以下、実験設定を簡単に導入するためのものである。詳細な実験設定は付録 A.2 に記載されている。

5.1.1 データ記述。TrajGATの性能を評価するために、2つの公開軌跡データセットを採用する。最初のデータセットは、DiDi Inc.が提供する西安のタクシー軌跡である。28]で提案されたデータ事前保有法の後、我々は西安データセットで525万の軌跡を、ポルトデータセットで0.6万以上の軌跡を得た。各データセットについて、異なる軌跡の長さに対するTrajGATの性能を検証するために、MixとLongと呼ばれる2つのサブデータセットを構築する。実験では、2つのデータセットのMixとLongの両方が10, 000の軌跡を含む。

5.1.2 実験プロトコル TrajGATの性能を評価するために、Top-K軌跡類似性検索（セクション5.2）と軌跡クラスタリング（セクション5.3）という2つのタスクについて実験を行い、TrajGATの性能を多くの学習ベースの類似性計算手法と比較する。また、TrajGATの効率を測るために、GPUのメモリコストを比較し、セクション5.4でその結果を報告する。アブレーション研究の結果は、セクション5.5で詳述する。さらに、付録A.3で主要なパラメータの感度もテストしている。

5.1.3 比較したベースライン 我々はTrajGATをNT-No-SAM [28], traj2vec [30], t2vec [16], NeuTraj [28], Traj2SimVec [35] and transformer [23] など6つの代表作と比較している。これらの手法の詳細は付録 A.2.3 に明記する。

5.2 性能 Top-K Trajectory Similarity Searchの性能 質問Q1に答えるため、XianとPortoの両データセットにおいて、TrajGATの性能をベースラインと比較し、表1に実験結果を示す。Mixデータセットの結果から、以下のことが確認された：(1) TrajGATはほぼ全てのメトリクスでベースラインを大幅に上回る。PortoデータセットのHausdorff距離を例にとると、TrajGATは最強のベースラインNeuTrajと比較して、HR@10で約2倍の性能向上（34.99%から65.69%）を達成している。TrajGATは同じ教師情報を利用しているにもかかわらず、このような向上が見られるのは驚くべきことである。(2) TrajGATの優位性は、両類似性尺度においても明らかである。DTWとHausdorffの両方で最高の性能を達成しており、これはTrajGATが異なる軌跡の類似性メトリクスに対して一般的であることを示しています。(3) 比較した全ての手法は、類似性関数を近似するためにDeep Neural Networkを採用しているが、TrajGATは最高の性能を得るために2つの利点がある。第一に、階層構造を明示的にモデル化することで、TrajGATは空間全体の位置密度分布を把握することができる。第二に、軌跡エンコードにRNNを用いる代わりに、TrajGATは逐次情報をモデル化するためにGATベースのTransformerを採用しており、長期的な依存関係をモデル化するだけでなく、異なる層からの空間情報を集約することができます。

Longデータセットでの結果によると、以下のことがわかります： (1) TrajGATは、すべてのベースラインと比較して、圧倒的な優位性を獲得した。西安とポルトの両データセットにおいて、TrajGATの性能は他の方法より少なくとも2倍以上高い。例えば、TrajGATはPortoデータセットのHausdorffのHR@10を18.03%から53.44%に向上させています。この結果は、TrajGATが類似性計算に有用な軌跡の長期依存性を捉えることができることを示しています。(2) 比較した手法の中で、Traj2SimVecの性能は他より優れている。これは、Traj2SimVecがモデル学習の教師情報としてサブ軌跡の類似性を用いており、異なる領域にまたがる長い軌跡の階層的関係を暗黙のうちに捉えているためである。(3) TrajGATの結果をMixとLongで比較すると、Longデータセットでの性能はMixデータセットでの性能に劣ることがわかる。この現象は、長い軌跡の類似性を近似することが、混合軌跡の類似性を近似するよりも困難であることを示している。

5.3 軌跡のクラスタリングの性能 TrajGATのペアワイズ類似度計算の有効性を検証し、より良いQ1に答えるために、Portoデータセットで軌跡クラスタリングの実験を行う。クラスタリングアルゴリズムはDBSCANで、2つの重要なパラメータ、すなわち、1つのクラスタのサンプルペア内の最小サンプルmと最大距離ϵがある。 図6に示すように、様々なϵの下で正確な類似性（グランドトゥルース）と埋め込みベースの類似性のクラスタ数を比較しています。他の学習型類似度計算手法の結果と比較して、TrajGATのクラスタ数の差は比較的小さく（図6（a）右）、TrajGATが生成する埋め込みのメトリクス空間が、他のベースラインよりも正確なメトリクスに近似していることを示しています。図6 (b)から、NeuTrajとTraj2SimVecの性能は、ほとんど全てのクラスタ結果で低いことがわかる。これは、既存の学習ベースの手法が、長い軌跡のメトリクス空間をほとんど近似できないことを証明するものである。全体として、TrajGATはLongデータセットでより良い性能を達成しており、これはTrajGATが捉える長期依存性が長い軌道の類似性を計算するのに不可欠であることを証明している。

さらに、異なるクラスタ結果における軌跡の一貫性を測定するために、埋め込みベースの方法について4つのクラスタリングメトリクスを計算した。図7と図8に示すように、TrajGATはすべてのクラスタにおいてNeuTrajとTraj2SimVecの両方を大きく上回っている。MixデータセットのHomoдeneityを例にとると、TrajGATはほとんどのケースで0.8以上を達成し、比較した手法の性能は0.5程度であることがわかる。同様の現象は、他の3つのクラスタリングメトリクスでも観察されます。この結果は、TrajGATがメトリクス空間を近似する上で優れていることをさらに示しています。図7と図8の結果を比較すると、TrajGATと他のベースラインの性能差は、Longの方がMixよりも高いことが観察され、これはクラスタ数と一致する。また、ベースラインのクラスタリングメトリクスはLongデータセットでは低く、比較した手法が長い軌跡に対して意味のある埋め込みをほとんど学習できていないことがわかります。TrajGATは長期的な依存関係をモデル化することでこの問題を解決し、大幅な性能向上を実現しています。

5.4 効率実験 Q2に答えるために、GPUメモリ使用量に関するTrajGATの効率性をテストします。バッチサイズの変更に伴うTrajGATのGPUメモリ使用量を評価します。TrajGATをTransformerやNeuTrajと比較し、モデル推論で割り当てられたGPUメモリを表記する。結果は図9に示す通りである．図示されているように、TrajGATのGPUメモリ使用量は、2つのベースラインに比べてはるかに少ない。TrajGATとTransformerを比較すると、Transformerはバッチサイズ>100でメモリ不足の問題が発生するのに対し、TrajGATはGPUメモリ（500MiB）を約20％しか使用しないことがわかります。これは、TrajGATが、元の軌跡を軌跡グラフに変換し、グラフattentionでモデル化することにより、GPUメモリの使用量を大幅に削減することを証明しています。TrajGATとNeuTrajを比較すると、NeuTrajのメモリ使用量は常に高く、90%以上であることがわかります。これは、NeuTrajが空間相関をモデル化するために空間記憶テンソルを採用しており、その記憶には大量のメモリが必要であるためである。

5.5 アブレーション結果 Q3に答えるため、TrajGATと3つのアブレーション（TrajGAT-tree, TrajGAT-graph, TrajGAT-trans）を比較します。これらのアブレーションのアーキテクチャは以下の通りである： - TrajGAT-graphは、空間分割としてquadtreeのリーフノードを採用し、グリッドのモデルとしてTransformerを利用する。- TrajGAT-treeは、空間領域を等しい大きさのグリッドで分割し、2層の軌跡グラフをモデル化するためにGATベースのTransformerを採用しています。グリッドサイズは50m×50mを採用する。- TrajGAT-transは軌跡グラフを構築し、軌跡の埋め込みを生成するためにグラフアテンションネットワーク[24]を採用している。実験はPortoデータセットで行われ、結果は表3に示す通りである。その結果、(1)階層的な空間構造を明示的に統合することで、top-k類似検索の性能向上が顕著であり（すなわち、DTW下のLongでTransformer 10.17% → TrajGAT-graph 40.91% ）、長期依存性モデリングの有効性を証明する。(2) TrajGAT-treeとTransformerの結果を比較すると、グラフ構築手順により、MixとLongの両方で類似度計算に有用な情報を抽出し、軌跡の長期依存性をモデル化できることがわかる。例えば、MixにおけるHausdorffのHR@10は25.28%から60.95%に向上している。(3) TrajGAT-transとTrajGATの結果から、GATベースのTransformerは、軌跡の類似性計算において、グラフアテンションネットワークよりも有効であると結論付けられる。(4) TrajGATは全てのアブレーションと比較して最高の性能を達成し、提案技術の有効性が証明された。

6 結論（CONCLUSION 本論文では、現在のDRLベースの手法において、長い軌跡と短い軌跡の間に性能差があることを初めて観察した。我々はこの問題を、長期的な依存関係をモデル化していないことに起因すると考えている。この問題を解決するために、グラフベースの手法であるTrajGATを提案する。これは、PR-quadtreeによって構築された空間領域の階層構造を明示的にモデル化し、quadtreeのグリッドセルに基づいて軌跡グラフを構築するものである。また、GATベースのTransformerを設計することで、GPUのメモリ使用量を削減しつつ、軌跡の空間情報とシーケンシャル情報の両方を取り込むことができる。2つの公開データセットを用いた広範な実験により、TrajGATは長い軌跡において大幅な性能向上を達成し、すべての比較ベースラインを凌駕することが示されました。

A APPENDIX A.

1 TrajGATの複雑性解析 TrajGATの計算には、階層構造の構築と軌跡エンコードの2つの部分がある。それぞれについて複雑性を解析する。TrajGATはPR quadtreeを用いてAの階層構造を再帰的に構築する．したがって，Hを構築する複雑さは，通常loд(Nall )である(NallはT中のロケーションレコードの数)quadtreeの深さに比例する．階層構造の時間的複雑さはO(Nall - loд(Nall ))である．この構築は、準備手順として扱うことができる。新しい軌跡を準備するとき、階層構造は共有される。したがって、類似度計算の効率はこの追加的な手順によって影響を受けることはない。

軌跡エンコードでは、まず、各軌跡を、あらかじめ構築されたHに基づいて軌跡グラフT дに変換する。4.2.1節で導入するためのη層の階層情報が軌跡グラフの構築に関与している。この手順の時間的複雑さはO(η -L)であり、ここでLは軌跡の長さである。T дを入力として、TrajGATはGAT-based Transformerを用いて軌跡の表現を得ることができる。各GAT-based Transformer層の計算コストはL - NEであり、NEはT дのエッジの数であり、通常はloд(L)に比例する。したがって、軌跡エンコードの全体的な複雑さは、O(η - L + L - loд(L)) である。

A.2 実験の設定

A.2.1 データ記述。TrajGATの性能を評価するために、2つの公開軌跡データセットを採用する。最初のデータセットは西安のタクシー軌跡[？]で、2007年から2010年までの人の移動の軌跡17,621件が含まれている。2つ目のデータセットPorto[19]には、2013年から2014年までの170万件以上のタクシーの軌跡が含まれています。このデータセットでは，[28]のデータ選択手順に従って，都市の中心部の軌跡を選択し，10レコード以下の軌跡を削除している．処理後、西安データセットでは7641件、ポルトデータセットでは600,000件以上の軌跡を得ることができました。

軌跡の長さが異なる場合のTrajGATの性能を検証するために、各データセットに対してMixとLongの2つのサブデータセットを構築した。200レコードを超える軌跡をロング軌跡と呼び、Longに割り当てる。この設定により、Portoデータセットでは30,031個の長い軌跡が、Xianデータセットでは85個の長い軌跡が得られた。対距離の計算コストが高いため、2つのデータセットについてすべての対距離を計算することは困難である。性能評価のために、元のデータセットから軌跡のサブセットをランダムにサンプリングする。実験では、2つのデータセットのMixとLongの両方に10,000の軌跡が含まれている。ペアワイズ距離行列は、モデル学習を教師するために事前に計算される。

A.2.2 実験プロトコル TrajGATの性能を評価するために、Top-K軌跡類似性検索と軌跡クラスタリングという2つのタスクを採用し、多くの学習ベースの類似性計算手法とTrajGATの性能を比較する。また、TrajGATの効率性を検証するために、GPUのメモリコストも比較する。以下、実験プロトコルを詳細に説明する。

Top-K軌跡類似度検索 XianとPortoの両データセットでTop-k類似性探索問題を研究し、DTW（Dynamic Time Warping）とHausdorff距離という2つの距離尺度でTrajGATを評価した。Hausdorff距離はメトリクスであるため、対称的であり、三角形の不等式を満たしている。そのため、メトリクスを直接近似するようにモデルを学習します。DTWはメトリクスではありません。距離行列にそのtransformer行列を加えて対称にし、非メトリックな類似性尺度に対するTrajGATの性能を調べる。 この問題のグランドトゥルースは、事前に計算された正確な類似性、すなわちHausdorff距離とDTW距離に基づく正確なトップk結果である。異なる長さ範囲の軌跡に対するモデルの能力を検証するために、TrajGATと全ての比較された方法の性能をMixとLongの両方のデータセットで評価する。さらに、20%の軌跡を訓練セット、10%の軌跡を検証セット、70%の軌跡をテストセットとしてランダムに選択する。

トップk類似性探索実験における性能評価には、3種類のメトリクスを採用した： HR@10、HR@50、R10@50である。HR@kはtop-kヒット率を表し、生成されたtop-k結果とグランドトゥルースとの重なり率を意味する。R10@50はトップ10グランドトゥルースのトップ50リコール率を表し、異なる手法で作成されたトップ50リストによって、トップ10グランドトゥルースの軌跡がどれだけ回収されたかを評価するものである。トップk軌跡類似検索の性能比較は、セクション5.2に示す。

軌跡のクラスタリング ペアワイズ類似度計算におけるTrajGATの性能を評価するため、Portoデータセットで軌跡クラスタリング実験を行い、正確な類似度と埋め込みベースの類似度のクラスタの違いを比較する。クラスタリングアルゴリズムとしては、空間データで広く使われている密度ベースのクラスタリングアルゴリズムであるDBSCAN[10]を利用し、様々なパラメータ設定においてクラスタリング結果を得ることができる。具体的には、クラスタの最小軌跡数を固定し、ϵを増加させて、正確な類似度と学習された埋め込みの両方について異なるクラスタを生成する。クラスタリング結果は、クラスタ数、均質性、完全性、V-measure、Adjusted Random Indexという5つのクラスタリングメトリクスで評価される。軌跡のクラスタリング結果は5.3節に示す。

効率化を図る。 セクション4.4で示したように、軌跡の類似度の計算は軌跡の埋め込みを生成した後、一定である。したがって、軌跡埋め込みに対する推論コストは、TrajGATの効率を表すために使用することができる。実験では、TrajGATのGPUメモリ使用量を既存の学習型類似性計算手法と比較し、効率性を検証する。実験結果はセクション5.4で分析する。

A.2.3 比較されたベースライン。 TrajGATをNT-No-SAM[28]、traj2vec [30]、t2vec [16]、NeuTraj [28]、 Traj2SimVec [35], Transformer [23] などの代表作6つと比較します。これらの手法の主な考え方を以下に列挙する： - NT-No-SAM[28]は，リカレントニューラルネットワークを用いて順序関係を捉え，出力のHidden Stateを軌跡の埋め込みとみなしている．- traj2vec[30]は、軌跡の移動挙動と再構成損失により軌跡の特徴を表現する。この手法は、軌跡のクラスタリング用に設計されている。また、膨大な修正を加えることなく、類似度計算にも適応できる。

t2vec[16]はseq2seqベースのモデルであり、サンプリングレートの変動やノイズの多いサンプルポイントに対処するための新しい埋込み技術を採用している。- NeuTraj[28]は，空間Attention記憶モジュールと距離重み付けランキングロスを組み合わせたメトリクス学習アプローチで，軌跡の類似性を計算するためにシードガイドニューラルネットワークを採用している．

• Traj2SimVec[35]は、サブ軌跡から距離情報を抽出する戦略を設計し、異なる距離メトリクスに基づいて軌跡点間の一致関係を制限する。
• Transformer[23]は神経言語処理のために提案されたが、シーケンシャルデータのモデル化にも適応できる。この研究に触発され、我々は軌跡エンコード法を設計する。公開されているコード[16, 28, 30]を持つ手法については、その実装を直接利用する。それ以外の手法については、関連する論文の設定に従い、自力で実装する。