論文の概要: (k, l)-Medians Clustering of Trajectories Using Continuous Dynamic Time
Warping
- arxiv url: http://arxiv.org/abs/2012.00464v1
- Date: Tue, 1 Dec 2020 13:17:27 GMT
- ステータス: 処理完了
- システム内更新日: 2021-05-30 19:31:08.417525
- Title: (k, l)-Medians Clustering of Trajectories Using Continuous Dynamic Time
Warping
- Title(参考訳): (k, l)-連続動的時間ワープを用いた軌道の中間子クラスタリング
- Authors: Milutin Brankovic, Kevin Buchin, Koen Klaren, Andr\'e Nusser,
Aleksandr Popov, Sampson Wong
- Abstract要約: 本研究では,トラジェクトリの集中型クラスタリングの問題について考察する。
我々はDTWの連続バージョンを距離測定として使用することを提案し、これをCDTW(Continuous dynamic time warping)と呼ぶ。
一連の軌道から中心を計算し、その後反復的に改善する実践的な方法を示す。
- 参考スコア(独自算出の注目度): 57.316437798033974
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Due to the massively increasing amount of available geospatial data and the
need to present it in an understandable way, clustering this data is more
important than ever. As clusters might contain a large number of objects,
having a representative for each cluster significantly facilitates
understanding a clustering. Clustering methods relying on such representatives
are called center-based. In this work we consider the problem of center-based
clustering of trajectories.
In this setting, the representative of a cluster is again a trajectory. To
obtain a compact representation of the clusters and to avoid overfitting, we
restrict the complexity of the representative trajectories by a parameter l.
This restriction, however, makes discrete distance measures like dynamic time
warping (DTW) less suited.
There is recent work on center-based clustering of trajectories with a
continuous distance measure, namely, the Fr\'echet distance. While the
Fr\'echet distance allows for restriction of the center complexity, it can also
be sensitive to outliers, whereas averaging-type distance measures, like DTW,
are less so. To obtain a trajectory clustering algorithm that allows
restricting center complexity and is more robust to outliers, we propose the
usage of a continuous version of DTW as distance measure, which we call
continuous dynamic time warping (CDTW). Our contribution is twofold:
1. To combat the lack of practical algorithms for CDTW, we develop an
approximation algorithm that computes it.
2. We develop the first clustering algorithm under this distance measure and
show a practical way to compute a center from a set of trajectories and
subsequently iteratively improve it.
To obtain insights into the results of clustering under CDTW on practical
data, we conduct extensive experiments.
- Abstract(参考訳): 利用可能な地理空間データの量が急増し、それを理解可能な方法で提示する必要があるため、このデータのクラスタリングはこれまで以上に重要である。
クラスタには多数のオブジェクトが含まれる可能性があるため、各クラスタに代表を持つことによって、クラスタの理解が大幅に容易になる。
このような代表に依存するクラスタリング手法をセンターベースと呼ぶ。
本研究では,軌跡中心クラスタリングの問題について考察する。
この設定では、クラスタの代表は再び軌跡となる。
クラスタのコンパクトな表現とオーバーフィッティングを避けるため,パラメータ l による代表軌道の複雑さを制限する。
近年,連続距離測度,すなわちfr\'echet距離を用いた軌道の中心的クラスタリングが研究されている。
fr\'echet距離は中心複雑性の制限を可能にするが、外れ値にも敏感であるが、dtwのような平均型距離測度はそうではない。
中心複雑性を制限し,アウトレーラに対して堅牢なトラジェクトリクラスタリングアルゴリズムを実現するために,DTWの連続バージョンを距離測定として使用することを提案し,これを連続動的時間ワープ(CDTW)と呼ぶ。
私たちの貢献は2つあります。
cdtwの実用的アルゴリズムの欠如に対処するために,計算を行う近似アルゴリズムを開発した。
2.
本研究では,この距離測定に基づく最初のクラスタリングアルゴリズムを開発し,一連の軌道から中心を計算し,反復的に改善する実用的な方法を示す。
実測データに基づくCDTWによるクラスタリングの結果の洞察を得るために,我々は広範な実験を行った。
関連論文リスト
- Self-Supervised Graph Embedding Clustering [70.36328717683297]
K-means 1-step dimensionality reduction clustering method は,クラスタリングタスクにおける次元性の呪いに対処する上で,いくつかの進歩をもたらした。
本稿では,K-meansに多様体学習を統合する統一フレームワークを提案する。
論文 参考訳(メタデータ) (2024-09-24T08:59:51Z) - Fuzzy K-Means Clustering without Cluster Centroids [21.256564324236333]
ファジィK平均クラスタリングは教師なしデータ分析において重要な手法である。
本稿では,クラスタセントロイドへの依存を完全に排除する,ファジィテクストK-Meansクラスタリングアルゴリズムを提案する。
論文 参考訳(メタデータ) (2024-04-07T12:25:03Z) - Towards a connection between the capacitated vehicle routing problem and the constrained centroid-based clustering [1.3927943269211591]
実用的なランタイムにおける車両ルーティングの効率的な解決は、デリバリ管理企業にとって重要な課題である。
本稿では,CVRPとCCBC(Constrainedid-Based Clustering)の理論的および実験的関係について検討する。
提案するフレームワークは,3つの段階から構成される。第1段階では,制約付きセントロイドベースのクラスタリングアルゴリズムが,ユーザの実現可能なクラスタを生成する。
論文 参考訳(メタデータ) (2024-03-20T22:24:36Z) - Distribution-Based Trajectory Clustering [14.781854651899705]
軌道クラスタリングは、軌道データの共通パターンの発見を可能にする。
距離測定には高い計算コストと低い忠実度という2つの課題がある。
我々は,最近の分散カーネル(IDK)を3つの課題に対処するための主要なツールとして利用することを提案する。
論文 参考訳(メタデータ) (2023-10-08T11:28:34Z) - Rethinking k-means from manifold learning perspective [122.38667613245151]
平均推定なしで直接データのクラスタを検出する新しいクラスタリングアルゴリズムを提案する。
具体的には,バタワースフィルタを用いてデータ点間の距離行列を構成する。
異なる視点に埋め込まれた相補的な情報をうまく活用するために、テンソルのSchatten p-norm正規化を利用する。
論文 参考訳(メタデータ) (2023-05-12T03:01:41Z) - Fast conformational clustering of extensive molecular dynamics
simulation data [19.444636864515726]
本稿では,長い軌道の高速なコンフォーメーションクラスタリングを実現するために,教師なしのデータ処理ワークフローを提案する。
我々は密度に基づく空間クラスタリングアルゴリズム(HDBSCAN)と2つの次元削減アルゴリズム(cc_analysisとEncodermap)を組み合わせる。
4つのテストシステムの助けを借りて、このクラスタリングワークフローの機能とパフォーマンスを説明します。
論文 参考訳(メタデータ) (2023-01-11T14:36:43Z) - Adaptively-weighted Integral Space for Fast Multiview Clustering [54.177846260063966]
線形複雑度に近い高速マルチビュークラスタリングのための適応重み付き積分空間(AIMC)を提案する。
特に、ビュー生成モデルは、潜在積分空間からのビュー観測を再構成するために設計されている。
いくつかの実世界のデータセットで実施された実験は、提案したAIMC法の優位性を確認した。
論文 参考訳(メタデータ) (2022-08-25T05:47:39Z) - ThetA -- fast and robust clustering via a distance parameter [3.0020405188885815]
クラスタリングは機械学習の根本的な問題であり、遠隔ベースのアプローチが数十年にわたってこの分野を支配してきた。
Theta-based Algorithms (ThetA) と呼ばれる新しい距離しきい値法を提案する。
論文 参考訳(メタデータ) (2021-02-13T23:16:33Z) - Scalable Hierarchical Agglomerative Clustering [65.66407726145619]
既存のスケーラブルな階層的クラスタリング手法は、スピードの質を犠牲にする。
我々は、品質を犠牲にせず、数十億のデータポイントまでスケールする、スケーラブルで集約的な階層的クラスタリング法を提案する。
論文 参考訳(メタデータ) (2020-10-22T15:58:35Z) - Ball k-means [53.89505717006118]
Ball k-meansアルゴリズムは、ポイントセントロイド距離計算の削減に集中して、クラスタを記述するためにボールを使用する。
高速、余分なパラメータなし、単純設計のボールk平均アルゴリズムは、素早いk平均アルゴリズムを全面的に置き換える。
論文 参考訳(メタデータ) (2020-05-02T10:39:26Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。