論文の概要: Exact Acceleration of K-Means++ and K-Means$\|$
- arxiv url: http://arxiv.org/abs/2105.02936v1
- Date: Thu, 6 May 2021 20:22:55 GMT
- ステータス: 処理完了
- システム内更新日: 2021-05-10 12:30:28.542139
- Title: Exact Acceleration of K-Means++ and K-Means$\|$
- Title（参考訳）: K-Means++とK-Means$\|$の厳密な加速
- Authors: Edward Raff
- Abstract要約: K-Means++とK-Means$|$はK-meansの初期種を選択するデファクトツールとなっている。
我々は、K-Means++とK-Means$|$の最初のアクセラレーションを示すために、特殊三角不等式プルーニング戦略と動的優先度待ち行列を開発する。
- 参考スコア（独自算出の注目度）: 22.66983713481359
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: K-Means++ and its distributed variant K-Means$\|$ have become de facto tools
for selecting the initial seeds of K-means. While alternatives have been
developed, the effectiveness, ease of implementation, and theoretical grounding
of the K-means++ and $\|$ methods have made them difficult to "best" from a
holistic perspective. By considering the limited opportunities within seed
selection to perform pruning, we develop specialized triangle inequality
pruning strategies and a dynamic priority queue to show the first acceleration
of K-Means++ and K-Means$\|$ that is faster in run-time while being
algorithmicly equivalent. For both algorithms we are able to reduce distance
computations by over $500\times$. For K-means++ this results in up to a
17$\times$ speedup in run-time and a $551\times$ speedup for K-means$\|$. We
achieve this with simple, but carefully chosen, modifications to known
techniques which makes it easy to integrate our approach into existing
implementations of these algorithms.
- Abstract（参考訳）: K-Means++とその分散変種K-Means$\|$は、K-meansの初期種を選択するデファクトツールとなっている。
代替案が開発されているが、K-means++と$\|$メソッドの有効性、実装の容易性、理論的根拠は、全体論的観点からの「ベスト」を困難にしている。
種苗選択の限られた機会を考慮し,特殊な三角不等式刈り込み戦略と動的優先度キューを開発し,アルゴリズム的に等価なk-means++とk-means$\|$の最初の加速を示す。
どちらのアルゴリズムに対しても、距離計算を500\times$で削減できる。
K-means++の場合、これは実行時の17$\times$スピードアップとK-means$\|$の551$スピードアップとなる。
私たちは、このアプローチをこれらのアルゴリズムの既存の実装に容易に統合できるように、既知のテクニックをシンプルだが慎重に修正することで、これを達成します。
関連論文リスト
- Almost-linear Time Approximation Algorithm to Euclidean $k$-median and $k$-means [4.271492285528115]
Euclidean $k$-medianと$k$-meansの問題、クラスタリングのタスクをモデル化する標準的な2つの方法に注目します。
本稿では,定数係数近似を計算するためのほぼ線形時間アルゴリズムを提案することにより,この問題にほぼ答える。
論文 参考訳（メタデータ） (2024-07-15T20:04:06Z) - 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) - Private estimation algorithms for stochastic block models and mixture
models [63.07482515700984]
効率的なプライベート推定アルゴリズムを設計するための一般的なツール。
最初の効率的な$(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery。
論文 参考訳（メタデータ） (2023-01-11T09:12:28Z) - Scalable Differentially Private Clustering via Hierarchically Separated
Trees [82.69664595378869]
我々は,最大$O(d3/2log n)cdot OPT + O(k d2 log2 n / epsilon2)$,$epsilon$はプライバシ保証であることを示す。
最悪の場合の保証は、最先端のプライベートクラスタリング手法よりも悪いが、提案するアルゴリズムは実用的である。
論文 参考訳（メタデータ） (2022-06-17T09:24:41Z) - 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) - Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean
Estimation [58.24280149662003]
本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。
我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
論文 参考訳（メタデータ） (2021-06-16T03:34:14Z) - 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) - Differentially Private Clustering: Tight Approximation Ratios [57.89473217052714]
基本的なクラスタリング問題に対して,効率的な微分プライベートアルゴリズムを提案する。
この結果から,SampleとAggregateのプライバシーフレームワークのアルゴリズムの改善が示唆された。
1-Clusterアルゴリズムで使用されるツールの1つは、ClosestPairのより高速な量子アルゴリズムを適度な次元で得るために利用できる。
論文 参考訳（メタデータ） (2020-08-18T16:22:06Z) - Breathing K-Means: Superior K-Means Solutions through Dynamic K-Values [0.0]
我々は,広く知られているgreedy k-means++アルゴリズムによって得られる解を平均的に大幅に改善する呼吸k-meansアルゴリズムを提案する。
これらの改善は、局所的誤差と実用性尺度に基づいて、周期的にセントロイドの数を増加・減少させる、新しい呼吸技術によって達成される。
論文 参考訳（メタデータ） (2020-06-28T17:49:37Z) - Improving The Performance Of The K-means Algorithm [2.28438857884398]
私の論文では、クラスタリング結果の質を概ね保ちながら、IKMを高速化する2つのアルゴリズムを提案している。
最初のアルゴリズムはDivisive K-meansと呼ばれ、クラスタの分割プロセスを高速化することでIKMの速度を改善する。
2つ目のアルゴリズムはPar2PK-means(Par2PK-means)と呼ばれ、Two-Phase K-meansモデルを用いてIKMを並列化する。
論文 参考訳（メタデータ） (2020-05-10T15:09:44Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。