論文の概要: Breathing K-Means
- arxiv url: http://arxiv.org/abs/2006.15666v3
- Date: Sun, 10 Oct 2021 21:16:06 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-16 02:16:04.369431
- Title: Breathing K-Means
- Title(参考訳): K‐Means
- Authors: Bernd Fritzke (individual researcher)
- Abstract要約: k-means++はk-means問題の近似解を見つけるためのデファクト標準である。
本稿では,Scikit-learn の k-means++ w.r.t において,解の質と実行速度を平均的に上回る呼吸 k-means アルゴリズムを提案する。
- 参考スコア(独自算出の注目度): 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The k-means++ algorithm is the de-facto standard for finding approximate
solutions to the k-means problem. A widely used implementation is provided by
the scikit-learn Python package for machine learning. We propose the breathing
k-means algorithm, which on average significantly outperforms scikit-learn's
k-means++ w.r.t. both solution quality and execution speed. The initialization
step in the new method is done by k-means++ but without the usual (and costly)
repetitions (ten in scikit-learn). The core of the new method is a sequence of
"breathing cycles," each consisting of a "breathe in" step where the number of
centroids is increased by m and a "breathe out" step where m centroids are
removed. Each step is ended by a run of Lloyd's algorithm. The parameter m is
decreased until zero, at which point the algorithm terminates. With the default
(m = 5), breathing k-means dominates scikit-learn's k-means++. This is
demonstrated via experiments on various data sets, including all those from the
original k-means++ publication. By setting m to smaller or larger values, one
can optionally produce faster or better solutions, respectively. For larger
values of m, e.g., m = 20, breathing k-means likely is the new SOTA for the
k-means problem.
- Abstract(参考訳): k-means++アルゴリズムは、k-means問題の近似解を見つけるためのデファクト標準である。
広く使われている実装は、scikit-learn python package for machine learningによって提供されている。
本稿では,Scikit-learn の k-means++ w.r.t において,解の質と実行速度を平均的に上回る呼吸 k-means アルゴリズムを提案する。
新しいメソッドの初期化ステップはk-means++によって行われるが、通常の(そしてコストのかかる)反復は行わない。
新しい方法の核心は「呼吸サイクル」のシーケンスであり、それぞれが「呼吸イン」ステップで、m個のセントロイドの数を増加させ、m個のセントロイドを除去した「呼吸アウト」ステップからなる。
各ステップはロイドのアルゴリズムの実行によって終了する。
パラメータ m は 0 まで減少し、その時点でアルゴリズムは終了する。
デフォルト (m = 5) では、呼吸k-meansが scikit-learn の k-means++ を支配している。
これは、k-means++のオリジナルの出版物を含む、さまざまなデータセットに関する実験を通じて実証される。
m を小さい値または大きい値に設定することで、それぞれより高速またはより良い解を生成することができる。
m のより大きな値、例えば m = 20 の場合、k 平均の呼吸は k 平均問題の新しい SOTA である可能性が高い。
関連論文リスト
- Do you know what q-means? [50.045011844765185]
クラスタリングは、大規模なデータセットを分析する上で最も重要なツールの1つである。
クラスタリングのための"$q$-means"アルゴリズムの改良版を提案する。
また、$Obig(frack2varepsilon2(sqrtkd + log(Nd))big で実行される $varepsilon に対する "dequantized" アルゴリズムも提示する。
論文 参考訳(メタデータ) (2023-08-18T17:52:12Z) - Rethinking k-means from manifold learning perspective [122.38667613245151]
平均推定なしで直接データのクラスタを検出する新しいクラスタリングアルゴリズムを提案する。
具体的には,バタワースフィルタを用いてデータ点間の距離行列を構成する。
異なる視点に埋め込まれた相補的な情報をうまく活用するために、テンソルのSchatten p-norm正規化を利用する。
論文 参考訳(メタデータ) (2023-05-12T03:01:41Z) - Using MM principles to deal with incomplete data in K-means clustering [0.0]
K平均クラスタリングアルゴリズムは、単純なアルゴリズムと高速収束のために広く利用されている。
主に、データの対称性を復元するためにMMの原理を適用し、K平均がうまく動作するようにします。
論文 参考訳(メタデータ) (2022-12-23T14:50:57Z) - Global $k$-means$++$: an effective relaxation of the global $k$-means
clustering algorithm [0.20305676256390928]
k$-meansアルゴリズムは、その単純さ、有効性、スピードから、一般的なクラスタリング手法である。
本稿では,高品質クラスタリングソリューションを効果的に取得する手段として,emphglobal $k$-meanstexttt++クラスタリングアルゴリズムを提案する。
論文 参考訳(メタデータ) (2022-11-22T13:42:53Z) - Hessian Averaging in Stochastic Newton Methods Achieves Superlinear
Convergence [69.65563161962245]
ニュートン法を用いて,滑らかで強凸な目的関数を考える。
最適段階において局所収束に遷移する普遍重み付き平均化スキームが存在することを示す。
論文 参考訳(メタデータ) (2022-04-20T07:14:21Z) - 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) - A Momentum-Assisted Single-Timescale Stochastic Approximation Algorithm
for Bilevel Optimization [112.59170319105971]
問題に対処するための新しいアルゴリズム - Momentum- Single-timescale Approximation (MSTSA) を提案する。
MSTSAでは、低いレベルのサブプロブレムに対する不正確な解決策のため、反復でエラーを制御することができます。
論文 参考訳(メタデータ) (2021-02-15T07:10:33Z) - k-sums: another side of k-means [34.317086730703124]
本稿では, 数十年前からあるクラスタリング手法k-meansについて再検討する。
k平均の元々の歪み最小化モデルは、純粋な最小化法によって対処される。
クラスタ内の対距離を最小化する新たなターゲット関数を示す。
論文 参考訳(メタデータ) (2020-05-19T14:36:12Z) - Ball k-means [53.89505717006118]
Ball k-meansアルゴリズムは、ポイントセントロイド距離計算の削減に集中して、クラスタを記述するためにボールを使用する。
高速、余分なパラメータなし、単純設計のボールk平均アルゴリズムは、素早いk平均アルゴリズムを全面的に置き換える。
論文 参考訳(メタデータ) (2020-05-02T10:39:26Z) - k-means++: few more steps yield constant approximation [3.7468898363447654]
Arthur and Vassilvitskii (SODA 2007) の k-means++ アルゴリズムは k-means クラスタリング問題を解くための最先端のアルゴリズムである。
最近、Lattanzi と Sohler (ICML) は k-means++ を O(k log k) 局所探索ステップで拡張し、k-means クラスタリング問題に一定の近似(期待)をもたらすことを提案した。
論文 参考訳(メタデータ) (2020-02-18T18:28:25Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。