論文の概要: Settling Time vs. Accuracy Tradeoffs for Clustering Big Data
- arxiv url: http://arxiv.org/abs/2404.01936v1
- Date: Tue, 2 Apr 2024 13:31:19 GMT
- ステータス: 処理完了
- システム内更新日: 2024-04-03 16:19:00.890579
- Title: Settling Time vs. Accuracy Tradeoffs for Clustering Big Data
- Title（参考訳）: ビッグデータクラスタリングにおける時間と精度のトレードオフ
- Authors: Andrew Draganov, David Saulpic, Chris Schwiegelshohn,
- Abstract要約: 大規模データセット上でのk-meansおよびk-medianクラスタリングの理論的および実用的な実行限界について検討する。
私たちのコードは公開されており、実験を再現するためのスクリプトがあります。
- 参考スコア（独自算出の注目度）: 7.932425355668529
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study the theoretical and practical runtime limits of k-means and k-median clustering on large datasets. Since effectively all clustering methods are slower than the time it takes to read the dataset, the fastest approach is to quickly compress the data and perform the clustering on the compressed representation. Unfortunately, there is no universal best choice for compressing the number of points - while random sampling runs in sublinear time and coresets provide theoretical guarantees, the former does not enforce accuracy while the latter is too slow as the numbers of points and clusters grow. Indeed, it has been conjectured that any sensitivity-based coreset construction requires super-linear time in the dataset size. We examine this relationship by first showing that there does exist an algorithm that obtains coresets via sensitivity sampling in effectively linear time - within log-factors of the time it takes to read the data. Any approach that significantly improves on this must then resort to practical heuristics, leading us to consider the spectrum of sampling strategies across both real and artificial datasets in the static and streaming settings. Through this, we show the conditions in which coresets are necessary for preserving cluster validity as well as the settings in which faster, cruder sampling strategies are sufficient. As a result, we provide a comprehensive theoretical and practical blueprint for effective clustering regardless of data size. Our code is publicly available and has scripts to recreate the experiments.
- Abstract（参考訳）: 大規模データセット上でのk-meansおよびk-medianクラスタリングの理論的および実用的な実行限界について検討する。
事実上、すべてのクラスタリングメソッドはデータセットを読むのに要する時間よりも遅いので、最も高速なアプローチは、データを素早く圧縮し、圧縮された表現上でクラスタリングを実行することである。
残念なことに、点数を圧縮するための普遍的な選択は存在しない - ランダムサンプリングはサブ線形時間で実行され、コアセットは理論的な保証を提供するが、前者は精度を強制しないが、後者は点数やクラスタの数が増えるにつれて遅すぎる。
実際、感度に基づくコアセットの構成はデータセットサイズにおいて超線形時間を必要とすると推測されている。
この関係は、データを読み取るのに要する時間をログファクター内で、効果的に線形時間で感度サンプリングによってコアセットを得るアルゴリズムがあることを最初に示すことで検証する。
これに関して大幅に改善されるアプローチは、実用的なヒューリスティックスに頼らなければならないため、静的およびストリーミング設定において、実データと人工データセットの両方にわたるサンプリング戦略のスペクトルを考える必要がある。
これにより,クラスタの有効性を維持するためにコアセットが必要な条件と,より高速で粗いサンプリング戦略が十分である設定を示す。
その結果,データサイズによらず,効果的なクラスタリングを行うための総合的な理論的,実践的な青写真が得られた。
私たちのコードは公開されており、実験を再現するためのスクリプトがあります。
関連論文リスト
- Squeezed Attention: Accelerating Long Context Length LLM Inference [64.11145320159126]
本稿では,入力プロンプトの大部分を固定したLLMアプリケーションを高速化する機構として,Squeezed Attentionを提案する。
K-meansクラスタリングをオフラインで使用して、セマンティックな類似性に基づいて、固定されたコンテキストのキーをグループ化し、各クラスタを単一のセントロイド値で表現します。
そして、固定された文脈から重要なキーのみを用いて正確な注意を計算し、帯域幅と計算コストを削減する。
論文 参考訳（メタデータ） (2024-11-14T18:54:19Z) - Large-scale Fully-Unsupervised Re-Identification [78.47108158030213]
大規模未ラベルデータから学ぶための2つの戦略を提案する。
第1の戦略は、近傍関係に違反することなく、それぞれのデータセットサイズを減らすために、局所的な近傍サンプリングを行う。
第2の戦略は、低時間上限の複雑さを持ち、メモリの複雑さを O(n2) から O(kn) に k n で還元する新しい再帰的手法を利用する。
論文 参考訳（メタデータ） (2023-07-26T16:19:19Z) - Rethinking k-means from manifold learning perspective [122.38667613245151]
平均推定なしで直接データのクラスタを検出する新しいクラスタリングアルゴリズムを提案する。
具体的には,バタワースフィルタを用いてデータ点間の距離行列を構成する。
異なる視点に埋め込まれた相補的な情報をうまく活用するために、テンソルのSchatten p-norm正規化を利用する。
論文 参考訳（メタデータ） (2023-05-12T03:01:41Z) - Hard Regularization to Prevent Deep Online Clustering Collapse without
Data Augmentation [65.268245109828]
オンラインディープクラスタリング(オンラインディープクラスタリング)とは、機能抽出ネットワークとクラスタリングモデルを組み合わせて、クラスタラベルを処理された各新しいデータポイントまたはバッチに割り当てることである。
オフラインメソッドよりも高速で汎用性が高いが、オンラインクラスタリングは、エンコーダがすべての入力を同じポイントにマッピングし、すべてを単一のクラスタに配置する、崩壊したソリューションに容易に到達することができる。
本稿では,データ拡張を必要としない手法を提案する。
論文 参考訳（メタデータ） (2023-03-29T08:23:26Z) - Cluster-and-Conquer: A Framework For Time-Series Forecasting [94.63501563413725]
本稿では,高次元時系列データを予測するための3段階フレームワークを提案する。
当社のフレームワークは非常に汎用的で,各ステップで時系列予測やクラスタリングが利用可能です。
単純な線形自己回帰モデルでインスタンス化されると、いくつかのベンチマークデータセットで最先端の結果が得られる。
論文 参考訳（メタデータ） (2021-10-26T20:41:19Z) - 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) - Very Compact Clusters with Structural Regularization via Similarity and
Connectivity [3.779514860341336]
本稿では,汎用データセットのためのエンドツーエンドのディープクラスタリングアルゴリズムであるVery Compact Clusters (VCC)を提案する。
提案手法は,最先端のクラスタリング手法よりも優れたクラスタリング性能を実現する。
論文 参考訳（メタデータ） (2021-06-09T23:22:03Z) - Spectral Clustering with Smooth Tiny Clusters [14.483043753721256]
本稿では,データのスムーズさを初めて考慮した新しいクラスタリングアルゴリズムを提案する。
私たちのキーとなるアイデアは、スムーズなグラフを構成する小さなクラスタをクラスタ化することです。
本稿では,マルチスケールな状況に着目するが,データのスムーズさの考え方はどのクラスタリングアルゴリズムにも確実に拡張できる。
論文 参考訳（メタデータ） (2020-09-10T05:21:20Z) - SDCOR: Scalable Density-based Clustering for Local Outlier Detection in
Massive-Scale Datasets [0.0]
本稿では,大規模データセットにおける局所外乱検出のためのバッチワイド密度に基づくクラスタリング手法を提案する。
実生活および合成データセットの評価は,提案手法の線形時間複雑性が低いことを示す。
論文 参考訳（メタデータ） (2020-06-13T11:07:37Z) - Computationally efficient sparse clustering [67.95910835079825]
我々はPCAに基づく新しいクラスタリングアルゴリズムの有限サンプル解析を行う。
ここでは,ミニマックス最適誤クラスタ化率を,体制$|theta infty$で達成することを示す。
論文 参考訳（メタデータ） (2020-05-21T17:51:30Z) - Simple and Scalable Sparse k-means Clustering via Feature Ranking [14.839931533868176]
直感的で実装が簡単で,最先端のアルゴリズムと競合する,スパースk平均クラスタリングのための新しいフレームワークを提案する。
本手法は,属性のサブセットのクラスタリングや部分的に観測されたデータ設定など,タスク固有のアルゴリズムに容易に一般化できる。
論文 参考訳（メタデータ） (2020-02-20T02:41:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。