論文の概要: Rock the KASBA: Blazingly Fast and Accurate Time Series Clustering
- arxiv url: http://arxiv.org/abs/2411.17838v1
- Date: Tue, 26 Nov 2024 19:26:17 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-11-28 15:26:00.338312
- Title: Rock the KASBA: Blazingly Fast and Accurate Time Series Clustering
- Title（参考訳）: Rock the KASBA: 驚くほど高速で正確な時系列クラスタリング
- Authors: Christopher Holder, Anthony Bagnall,
- Abstract要約: 我々は、新しい時系列クラスタリング(TSCL)アルゴリズム、$k$-means (K)Accelerated (A) subgradient (S) Barycentre (B) Average (A)を提案する。
KASBAは、クラスタリングのすべての段階で、Move-Split-Merge (MSM) の弾性距離を使用し、ランダム化下降降下を適用してバリセント・セントロイドを見つけ、クラスタリングの各段階をリンクして収束を加速し、MSM距離の計量特性を利用して距離計算を行う、$k$-meansクラスタリングアルゴリズムである。
汎用的でスケーラブルなクラスタリングである。
- 参考スコア（独自算出の注目度）: 0.6215404942415159
- License:
- Abstract: Time series data has become increasingly prevalent across numerous domains, driving a growing demand for time series machine learning techniques. Among these, time series clustering (TSCL) stands out as one of the most popular machine learning tasks. TSCL serves as a powerful exploratory analysis tool and is also employed as a preprocessing step or subroutine for various tasks, including anomaly detection, segmentation, and classification. The most popular TSCL algorithms are either fast (in terms of run time) but perform poorly on benchmark problems, or perform well on benchmarks but scale poorly. We present a new TSCL algorithm, the $k$-means (K) accelerated (A) Stochastic subgradient (S) Barycentre (B) Average (A) (KASBA) clustering algorithm. KASBA is a $k$-means clustering algorithm that uses the Move-Split-Merge (MSM) elastic distance at all stages of clustering, applies a randomised stochastic subgradient gradient descent to find barycentre centroids, links each stage of clustering to accelerate convergence and exploits the metric property of MSM distance to avoid a large proportion of distance calculations. It is a versatile and scalable clusterer designed for real-world TSCL applications. It allows practitioners to balance run time and clustering performance. We demonstrate through extensive experimentation that KASBA produces significantly better clustering than the faster state of the art clusterers and is offers orders of magnitude improvement in run time over the most performant $k$-means alternatives.
- Abstract（参考訳）: 時系列データは、多くのドメインでますます普及し、時系列機械学習技術への需要が高まっている。
これらのうち、時系列クラスタリング(TSCL)は、最も人気のある機械学習タスクの1つである。
TSCLは強力な探索分析ツールとして機能し、異常検出、セグメンテーション、分類など様々なタスクのための前処理ステップやサブルーチンとしても使用される。
最も一般的なTSCLアルゴリズムは(実行時間の面では)高速だが、ベンチマーク問題では性能が良くないか、ベンチマークでは性能が良くない。
我々は,新しいTSCLアルゴリズム,$k$-means (K)Accelerated (A) Stochastic subgradient (S) Barycentre (B) Average (A) (KASBA) クラスタリングアルゴリズムを提案する。
KASBAは、クラスタリングのすべての段階で、モブ・スプリット・マージ(英語版)(MSM)の弾性距離を使い、ランダム化された確率的勾配勾配を適用して、バリセント・セントロイドを見つけ、クラスタリングの各段階をリンクして収束を加速し、MSM距離の計量特性を利用して距離計算を行う、$k$-meansクラスタリングアルゴリズムである。
現実世界のTSCLアプリケーション用に設計された汎用的でスケーラブルなクラスタである。
実行時間とクラスタリングのパフォーマンスのバランスをとることができる。
我々は、KASBAがより高速な最先端クラスタリングよりもはるかに優れたクラスタリングを実現し、最も高性能な$k$-meansの代替品よりも、実行時間を大幅に改善することを示した。
関連論文リスト
- Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model [79.46465138631592]
観測されたラベルを用いてクラスタを復元する効率的なアルゴリズムを考案する。
本稿では,期待値と高い確率でこれらの下位境界との性能を一致させる最初のアルゴリズムであるIACを提案する。
論文 参考訳（メタデータ） (2023-06-18T08:46:06Z) - Rethinking k-means from manifold learning perspective [122.38667613245151]
平均推定なしで直接データのクラスタを検出する新しいクラスタリングアルゴリズムを提案する。
具体的には,バタワースフィルタを用いてデータ点間の距離行列を構成する。
異なる視点に埋め込まれた相補的な情報をうまく活用するために、テンソルのSchatten p-norm正規化を利用する。
論文 参考訳（メタデータ） (2023-05-12T03:01:41Z) - An Exact Algorithm for Semi-supervised Minimum Sum-of-Squares Clustering [0.5801044612920815]
半教師付きMSSCのための分岐結合アルゴリズムを提案する。
背景知識はペアワイズ・マスタリンクと結びつかない制約として組み込まれている。
提案したグローバル最適化アルゴリズムは,実世界のインスタンスを最大800個のデータポイントまで効率的に解決する。
論文 参考訳（メタデータ） (2021-11-30T17:08:53Z) - Meta Clustering Learning for Large-scale Unsupervised Person
Re-identification [124.54749810371986]
メタクラスタリング学習(MCL)と呼ばれる「大規模タスクのための小さなデータ」パラダイムを提案する。
MCLは、第1フェーズのトレーニングのためにコンピューティングを節約するためにクラスタリングを介して、未ラベルデータのサブセットを擬似ラベル付けするのみである。
提案手法は計算コストを大幅に削減すると同時に,従来よりも優れた性能を実現している。
論文 参考訳（メタデータ） (2021-11-19T04:10:18Z) - K-Splits: Improved K-Means Clustering Algorithm to Automatically Detect
the Number of Clusters [0.12313056815753944]
本稿では,k-meansに基づく改良された階層型アルゴリズムであるk-splitsを紹介する。
提案手法の主な利点は,精度と速度である。
論文 参考訳（メタデータ） (2021-10-09T23:02:57Z) - SOMTimeS: Self Organizing Maps for Time Series Clustering and its
Application to Serious Illness Conversations [3.2689702143620147]
我々はSOMTimeS(TIMEシリーズの自己組織化マップ)と呼ばれるDTWに基づく新しいクラスタリング手法を提案する。
他のDTWベースのクラスタリングアルゴリズムよりも高速で、パフォーマンスも同等です。
我々は,大規模医療コホート研究の一環として収集した自然言語会話データにSOMtimeSを適用した。
論文 参考訳（メタデータ） (2021-08-26T00:18:25Z) - Robust Trimmed k-means [70.88503833248159]
本稿では,外乱点とクラスタポイントを同時に識別するRobust Trimmed k-means (RTKM)を提案する。
RTKMは他の方法と競合することを示す。
論文 参考訳（メタデータ） (2021-08-16T15:49:40Z) - Gradient Coding with Dynamic Clustering for Straggler-Tolerant
Distributed Learning [55.052517095437]
勾配降下(GD)は、複数の労働者にデータセットを分散することで学習タスクの並列化に広く用いられている。
分散同期gdにおけるイテレーション完了時間ごとの重要なパフォーマンスボトルネックは$straggling$ workersである。
コード化された分散技術は、最近ストラグラーを緩和し、労働者に冗長な計算を割り当てることでgdイテレーションを高速化するために導入された。
本稿では,従来のトラグリング動作に依存する可能性のあるコードの中から,冗長なデータを労働者に割り当てて選択する動的GC方式を提案する。
論文 参考訳（メタデータ） (2021-03-01T18:51:29Z) - Hierarchical Clustering using Auto-encoded Compact Representation for
Time-series Analysis [8.660029077292346]
本稿では,学習した時系列のコンパクト表現,オートエンコードコンパクトシーケンス(AECS),階層クラスタリングアプローチを組み合わせたクラスタの識別機構を提案する。
Sequence to Sequence(seq2seq)オートエンコーダと集約型階層クラスタリングに基づくRecurrent Neural Network(RNN)を利用するアルゴリズムです。
論文 参考訳（メタデータ） (2021-01-11T08:03:57Z) - (k, l)-Medians Clustering of Trajectories Using Continuous Dynamic Time
Warping [57.316437798033974]
本研究では,トラジェクトリの集中型クラスタリングの問題について考察する。
我々はDTWの連続バージョンを距離測定として使用することを提案し、これをCDTW(Continuous dynamic time warping)と呼ぶ。
一連の軌道から中心を計算し、その後反復的に改善する実践的な方法を示す。
論文 参考訳（メタデータ） (2020-12-01T13:17:27Z) - Spectral Clustering with Smooth Tiny Clusters [14.483043753721256]
本稿では,データのスムーズさを初めて考慮した新しいクラスタリングアルゴリズムを提案する。
私たちのキーとなるアイデアは、スムーズなグラフを構成する小さなクラスタをクラスタ化することです。
本稿では,マルチスケールな状況に着目するが,データのスムーズさの考え方はどのクラスタリングアルゴリズムにも確実に拡張できる。
論文 参考訳（メタデータ） (2020-09-10T05:21:20Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。