論文の概要: Simple, Scalable and Effective Clustering via One-Dimensional
Projections
- arxiv url: http://arxiv.org/abs/2310.16752v1
- Date: Wed, 25 Oct 2023 16:37:45 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-26 13:41:27.010256
- Title: Simple, Scalable and Effective Clustering via One-Dimensional
Projections
- Title（参考訳）: 1次元投影によるシンプルでスケーラブルで効果的なクラスタリング
- Authors: Moses Charikar, Monika Henzinger, Lunjia Hu, Maxmilian V\"otsch, Erik
Waingarten
- Abstract要約: クラスタリングは、教師なし機械学習における基本的な問題であり、データ分析に多くの応用がある。
任意の$k$に対して、期待時間$O(mathrmnnz(X) + nlog n)$で確実に動作する単純なランダム化クラスタリングアルゴリズムを導入する。
我々は,このアルゴリズムが$k$-means目的の任意の入力データセットに対して,近似比$smashwidetildeO(k4)$を達成することを証明した。
- 参考スコア（独自算出の注目度）: 10.807367640692021
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: Clustering is a fundamental problem in unsupervised machine learning with
many applications in data analysis. Popular clustering algorithms such as
Lloyd's algorithm and $k$-means++ can take $\Omega(ndk)$ time when clustering
$n$ points in a $d$-dimensional space (represented by an $n\times d$ matrix
$X$) into $k$ clusters. In applications with moderate to large $k$, the
multiplicative $k$ factor can become very expensive. We introduce a simple
randomized clustering algorithm that provably runs in expected time
$O(\mathrm{nnz}(X) + n\log n)$ for arbitrary $k$. Here $\mathrm{nnz}(X)$ is the
total number of non-zero entries in the input dataset $X$, which is upper
bounded by $nd$ and can be significantly smaller for sparse datasets. We prove
that our algorithm achieves approximation ratio $\smash{\widetilde{O}(k^4)}$ on
any input dataset for the $k$-means objective. We also believe that our
theoretical analysis is of independent interest, as we show that the
approximation ratio of a $k$-means algorithm is approximately preserved under a
class of projections and that $k$-means++ seeding can be implemented in
expected $O(n \log n)$ time in one dimension. Finally, we show experimentally
that our clustering algorithm gives a new tradeoff between running time and
cluster quality compared to previous state-of-the-art methods for these tasks.
- Abstract（参考訳）: クラスタリングは教師なし機械学習の基本的な問題であり、データ分析には多くの応用がある。
Lloydのアルゴリズムや$k$-means++のような一般的なクラスタリングアルゴリズムは、$d$次元空間の$n$ポイント($n\times d$ matrix $X$)を$k$クラスタにクラスタするときに$\Omega(ndk)$時間を取ることができる。
中間から大きい$k$のアプリケーションでは、乗法的な$k$係数は非常に高価になる。
任意の$k$に対して、期待時間$O(\mathrm{nnz}(X) + n\log n)$で確実に動作する単純なランダム化クラスタリングアルゴリズムを導入する。
ここで$\mathrm{nnz}(x)$ は入力データセットの0でないエントリの総数である$x$ であり、これは$nd$で上限を上回っており、スパースデータセットではかなり小さい。
我々は,このアルゴリズムが$k$-means目的の任意の入力データセットに対して近似比$\smash{\widetilde{O}(k^4)}$を達成することを証明した。
我々はまた、我々の理論解析は、$k$-meansアルゴリズムの近似比が射影のクラスでほぼ保存されていること、そして$k$-means++のシードは期待される$O(n \log n)$時間で1次元で実装可能であることを示し、独立した関心を持つと考えている。
最後に,このクラスタリングアルゴリズムは,従来の最先端手法と比較して,実行時間とクラスタ品質のトレードオフを新たに与えていることを示す。
関連論文リスト
- 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) - Do you know what q-means? [50.045011844765185]
クラスタリングは、大規模なデータセットを分析する上で最も重要なツールの1つである。
クラスタリングのための"$q$-means"アルゴリズムの改良版を提案する。
また、$Obig(frack2varepsilon2(sqrtkd + log(Nd))big で実行される $varepsilon に対する "dequantized" アルゴリズムも提示する。
論文 参考訳（メタデータ） (2023-08-18T17:52:12Z) - Differentially Private Clustering in Data Streams [65.78882209673885]
オフラインのDPコアセットやクラスタリングアルゴリズムをブラックボックスとしてのみ必要とする,差分プライベートなストリーミングクラスタリングフレームワークを提案する。
我々のフレームワークはまた、連続的なリリース設定の下で微分プライベートであり、すなわち、全てのタイムスタンプにおけるアルゴリズムの出力の和は常に微分プライベートである。
論文 参考訳（メタデータ） (2023-07-14T16:11:22Z) - 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) - Improved Learning-augmented Algorithms for k-means and k-medians
Clustering [8.04779839951237]
学習強化設定におけるクラスタリングの問題について考察し、そこでは、$d$次元ユークリッド空間のデータセットが与えられる。
本稿では,クラスタリングコストを改良したセンターを生成する決定論的$k$-meansアルゴリズムを提案する。
我々のアルゴリズムは、予測があまり正確でないときでも機能する。つまり、我々の限界は$alpha$を$/2$に保ち、以前の研究で$alpha$よりも1/7$に改善する。
論文 参考訳（メタデータ） (2022-10-31T03:00:11Z) - Nearly-Tight and Oblivious Algorithms for Explainable Clustering [8.071379672971542]
Moshkovitz, Dasgupta, Rashtchian, Frost (ICML 2020) によって初めて定式化された設定における説明可能なクラスタリングの問題について検討する。
k$クラスタリングは、各内部ノードデータが1次元(機能)で閾値をカットした点を示す決定木によって与えられる場合、説明可能であると言われる。
我々は、$k$-mediansの目的に対して最適な(必ずしも説明できない)クラスタリングと比較して、少なくとも$O(log2 k)$の係数を失う説明可能なクラスタリングを出力するアルゴリズムを提供する。
論文 参考訳（メタデータ） (2021-06-30T15:49:41Z) - Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean
Estimation [58.24280149662003]
本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。
我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
論文 参考訳（メタデータ） (2021-06-16T03:34:14Z) - Fuzzy Clustering with Similarity Queries [56.96625809888241]
ファジィ(fuzzy, soft objective)は、よく知られた$k$-means問題の一般化である。
クエリを少なくすることで、問題の解決が容易になる。
論文 参考訳（メタデータ） (2021-06-04T02:32:26Z) - List-Decodable Mean Estimation in Nearly-PCA Time [50.79691056481693]
高次元におけるリストデコタブル平均推定の基本的な課題について検討する。
我々のアルゴリズムは、すべての$k = O(sqrtd) cup Omega(d)$に対して$widetildeO(ndk)$で実行されます。
我々のアルゴリズムの変種は、すべての$k$に対してランタイム$widetildeO(ndk)$を持ち、リカバリ保証の$O(sqrtlog k)$ Factorを犠牲にしている。
論文 参考訳（メタデータ） (2020-11-19T17:21:37Z) - Explainable $k$-Means and $k$-Medians Clustering [25.513261099927163]
我々は、小さな決定木を使ってデータセットをクラスタに分割し、クラスタを直接的な方法で特徴付けることを検討する。
一般的なトップダウン決定木アルゴリズムが任意のコストでクラスタリングに繋がる可能性があることを示す。
我々は、$k$の葉を持つ木を用いて説明可能なクラスタを生成する効率的なアルゴリズムを設計する。
論文 参考訳（メタデータ） (2020-02-28T04:21:53Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。