論文の概要: No-Substitution $k$-means Clustering with Low Center Complexity and
Memory
- arxiv url: http://arxiv.org/abs/2102.09101v1
- Date: Thu, 18 Feb 2021 01:20:03 GMT
- ステータス: 処理完了
- システム内更新日: 2021-02-19 15:33:00.596026
- Title: No-Substitution $k$-means Clustering with Low Center Complexity and
Memory
- Title（参考訳）: No-Substitution $k$-means Clustering with Low Center Complexity and Memory
- Authors: Robi Bhattacharjee and Jacob Imola
- Abstract要約: 中心複雑性を$Lower_36, k(X)$で有界なアルゴリズムを開発し、これは真の$O(1)$-近似であり、近似係数は$k$または$n$とは独立である。
このアルゴリズムは、$Lower_36, k(X)$で区切られた最初の既知のアルゴリズムであり、これは真の$O(1)$-近似であり、近似係数は$k$または$n$から独立している。
- 参考スコア（独自算出の注目度）: 5.837881923712394
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Clustering is a fundamental task in machine learning. Given a dataset $X =
\{x_1, \ldots x_n\}$, the goal of $k$-means clustering is to pick $k$ "centers"
from $X$ in a way that minimizes the sum of squared distances from each point
to its nearest center. We consider $k$-means clustering in the online, no
substitution setting, where one must decide whether to take $x_t$ as a center
immediately upon streaming it and cannot remove centers once taken.
The online, no substitution setting is challenging for clustering--one can
show that there exist datasets $X$ for which any $O(1)$-approximation $k$-means
algorithm must have center complexity $\Omega(n)$, meaning that it takes
$\Omega(n)$ centers in expectation. Bhattacharjee and Moshkovitz (2020) refined
this bound by defining a complexity measure called $Lower_{\alpha, k}(X)$, and
proving that any $\alpha$-approximation algorithm must have center complexity
$\Omega(Lower_{\alpha, k}(X))$. They then complemented their lower bound by
giving a $O(k^3)$-approximation algorithm with center complexity
$\tilde{O}(k^2Lower_{k^3, k}(X))$, thus showing that their parameter is a tight
measure of required center complexity. However, a major drawback of their
algorithm is its memory requirement, which is $O(n)$. This makes the algorithm
impractical for very large datasets.
In this work, we strictly improve upon their algorithm on all three fronts;
we develop a $36$-approximation algorithm with center complexity
$\tilde{O}(kLower_{36, k}(X))$ that uses only $O(k)$ additional memory. In
addition to having nearly optimal memory, this algorithm is the first known
algorithm with center complexity bounded by $Lower_{36, k}(X)$ that is a true
$O(1)$-approximation with its approximation factor being independent of $k$ or
$n$.
- Abstract（参考訳）: クラスタリングは機械学習の基本的なタスクです。
データセット $X = \{x_1, \ldots x_n\}$ を考えると、$k$-means クラスタリングの目標は、各点から最も近い中心までの平方距離の合計を最小化する方法で $X$ から $k$ "centers" を選択することである。
我々は、オンラインにおける$k$-meansクラスタリングを検討し、置換設定はせず、ストリーミングした直後に$x_t$をセンターとして取るかどうかを決めなければならない。
オンラインの代替設定はクラスタリングに困難ではない - 任意の$O(1)$-近似$k$-meansアルゴリズムが中心複雑度$\Omega(n)$を持つ必要があるデータセット$X$が存在することを示すことができる。
bhattacharjee と moshkovitz (2020) はこの境界を、$lower_{\alpha, k}(x)$と呼ばれる複雑性測度を定義し、任意の$\alpha$近似アルゴリズムが$\omega(lower_{\alpha, k}(x))$を持つことを証明することで洗練した。
すると彼らは、中心複雑性が $O(k^3)$-approximation アルゴリズムを $\tilde{O}(k^2Lower_{k^3, k}(X))$ で与え、それらのパラメータが要求中心複雑性の厳密な測度であることを示した。
しかし、アルゴリズムの主な欠点は、そのメモリ要件であり、これは$O(n)$です。
これにより、非常に大きなデータセットではアルゴリズムが非現実的になる。
本研究では,3つの領域のアルゴリズムを厳格に改良し,中心的複雑性が$\tilde{O}(kLower_{36, k}(X))$で,O(k)$追加メモリのみを使用する36$近似アルゴリズムを開発した。
ほぼ最適なメモリを持つのに加えて、このアルゴリズムは、中心複雑性を$lower_{36, k}(x)$で区切られた最初の既知のアルゴリズムであり、これは真の$o(1)$近似であり、近似係数は$k$または$n$とは独立である。
関連論文リスト
- A Scalable Algorithm for Individually Fair K-means Clustering [77.93955971520549]
Jung et al. と Mahabadi et al が導入した個別フェア (p$, $k$) クラスタリング問題に対するスケーラブルなアルゴリズムを提案する。
クラスタリングは、各$xin P$に対して$delta(x)$ of $x$の範囲内で中心となる場合、個別にフェアと呼ばれる。
我々は,従来よりもアルゴリズムがはるかに高速であるだけでなく,低コストのソリューションを生み出すことを実証的に示す。
論文 参考訳（メタデータ） (2024-02-09T19:01:48Z) - Sketching Algorithms for Sparse Dictionary Learning: PTAS and Turnstile
Streaming [48.18845814885398]
本研究は,スプリス辞書学習とユークリッド語$k$-meansクラスタリング問題に対するスケッチベースアプローチの適用性を高めるための新しい手法を開発した。
高速アルゴリズムでは、$k$-meansクラスタリング問題に対してPTASを設計するための新しいアプローチを得る。
ストリーミングアルゴリズムの分野では、辞書学習と$k$-meansクラスタリングのための新しい上限と下位境界を得る。
論文 参考訳（メタデータ） (2023-10-29T16:46:26Z) - Simple, Scalable and Effective Clustering via One-Dimensional
Projections [10.807367640692021]
クラスタリングは、教師なし機械学習における基本的な問題であり、データ分析に多くの応用がある。
任意の$k$に対して、期待時間$O(mathrmnnz(X) + nlog n)$で確実に動作する単純なランダム化クラスタリングアルゴリズムを導入する。
我々は,このアルゴリズムが$k$-means目的の任意の入力データセットに対して,近似比$smashwidetildeO(k4)$を達成することを証明した。
論文 参考訳（メタデータ） (2023-10-25T16:37:45Z) - Do you know what q-means? [50.045011844765185]
クラスタリングは、大規模なデータセットを分析する上で最も重要なツールの1つである。
クラスタリングのための"$q$-means"アルゴリズムの改良版を提案する。
また、$Obig(frack2varepsilon2(sqrtkd + log(Nd))big で実行される $varepsilon に対する "dequantized" アルゴリズムも提示する。
論文 参考訳（メタデータ） (2023-08-18T17:52:12Z) - Near-Optimal Bounds for Learning Gaussian Halfspaces with Random
Classification Noise [50.64137465792738]
この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。
我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
論文 参考訳（メタデータ） (2023-07-13T18:59:28Z) - Near-Optimal Quantum Coreset Construction Algorithms for Clustering [15.513270929560088]
我々は、$tildeO(sqrtnkd3/2)$クエリ複雑性を持つ$mathbbRd$で$k$-clusteringのコアセットを見つける量子アルゴリズムを与える。
私たちのコアセットは入力サイズを$n$から$mathrmpoly(kepsilon-1d)$に減らします。
論文 参考訳（メタデータ） (2023-06-05T12:22:46Z) - Learning a Latent Simplex in Input-Sparsity Time [58.30321592603066]
我々は、$AinmathbbRdtimes n$へのアクセスを考えると、潜入$k$-vertex simplex $KsubsetmathbbRdtimes n$を学習する問題を考える。
実行時間における$k$への依存は、トップ$k$特異値の質量が$a$であるという自然な仮定から不要であることを示す。
論文 参考訳（メタデータ） (2021-05-17T16:40:48Z) - No-substitution k-means Clustering with Adversarial Order [8.706058694927613]
任意の順序で到着するデータセットのクラスタリングの難しさを定量化する新しい複雑性尺度を提案する。
我々の新しいアルゴリズムは、$textpoly(klog(n))$centerのみを取り、$textpoly(k)$-approximationです。
論文 参考訳（メタデータ） (2020-12-28T22:35:44Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z) - Coreset-based Strategies for Robust Center-type Problems [0.6875312133832077]
我々は、効率的なシーケンシャル、MapReduce、ストリーミングアルゴリズムをもたらす2つの問題に対するコアセットベースの戦略を考案する。
パラメータ$k,zepsilon,D$の広い範囲で、$|V|$で実行時間線形のシーケンシャルアルゴリズムと、ラウンド/パスが少なく、実質的にサブ線形な局所/ワーキングメモリを持つMapReduce/ストリーミングアルゴリズムを得る。
論文 参考訳（メタデータ） (2020-02-18T10:04:08Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。