論文の概要: 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 である可能性が高い。
関連論文リスト
- Rethinking k-means from manifold learning perspective [122.38667613245151]
平均推定なしで直接データのクラスタを検出する新しいクラスタリングアルゴリズムを提案する。
具体的には,バタワースフィルタを用いてデータ点間の距離行列を構成する。
異なる視点に埋め込まれた相補的な情報をうまく活用するために、テンソルのSchatten p-norm正規化を利用する。
論文 参考訳（メタデータ） (2023-05-12T03:01:41Z) - CKmeans and FCKmeans : Two deterministic initialization procedures for
Kmeans algorithm using a modified crowding distance [0.0]
K平均クラスタリングのための2つの新しい決定論的手順を示す。
CKmeans と FCKmeans という名前の手順は、より混雑した点を初期セントロイドとして使用する。
複数のデータセットに関する実験的研究により、提案手法がクラスタリング精度においてKmeansとKmeans++より優れていることが示された。
論文 参考訳（メタデータ） (2023-04-19T21:46:02Z) - Efficient Approximate Kernel Based Spike Sequence Classification [56.2938724367661]
SVMのような機械学習モデルは、シーケンスのペア間の距離/相似性の定義を必要とする。
厳密な手法により分類性能は向上するが、計算コストが高い。
本稿では,その予測性能を向上させるために,近似カーネルの性能を改善する一連の方法を提案する。
論文 参考訳（メタデータ） (2022-09-11T22:44:19Z) - Careful Seeding for k-Medois Clustering with Incremental k-Means++ Initialization [17.4921582710817]
K-medoidsクラスタリングはk-meansクラスタリングの一般的な変種であり、パターン認識や機械学習で広く使用されている。
INCKMアルゴリズムと呼ばれる改良されたk-medoidsクラスタリングアルゴリズムが最近提案され、この欠点を克服した。
インクリメンタルk-means++ (INCKPP) アルゴリズムと呼ばれる新しいk-medoidsクラスタリングアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-07-06T02:25:35Z) - Robust Trimmed k-means [70.88503833248159]
本稿では,外乱点とクラスタポイントを同時に識別するRobust Trimmed k-means (RTKM)を提案する。
RTKMは他の方法と競合することを示す。
論文 参考訳（メタデータ） (2021-08-16T15:49:40Z) - Improved Guarantees for k-means++ and k-means++ Parallel [18.26254785549146]
k-means++とk-means++並列は、古典的なk-meansクラスタリング問題に対する一般的なアルゴリズムである。
我々は、k-means++とk-means++の並列化に対する近似とbi-criteria近似の改善を示す。
我々はk-means++と同じ近似保証を持つk-means++並列アルゴリズム(Exponential Race k-means++)を提案する。
論文 参考訳（メタデータ） (2020-10-27T17:46:00Z) - Differentially Private Clustering: Tight Approximation Ratios [57.89473217052714]
基本的なクラスタリング問題に対して,効率的な微分プライベートアルゴリズムを提案する。
この結果から,SampleとAggregateのプライバシーフレームワークのアルゴリズムの改善が示唆された。
1-Clusterアルゴリズムで使用されるツールの1つは、ClosestPairのより高速な量子アルゴリズムを適度な次元で得るために利用できる。
論文 参考訳（メタデータ） (2020-08-18T16:22:06Z) - SimpleMKKM: Simple Multiple Kernel K-means [49.500663154085586]
単純なマルチカーネルk-means(SimpleMKKM)と呼ばれる,単純で効果的なマルチカーネルクラスタリングアルゴリズムを提案する。
我々の基準は、カーネル係数とクラスタリング分割行列における難解な最小化最大化問題によって与えられる。
クラスタリング一般化誤差の観点から,SimpleMKKMの性能を理論的に解析する。
論文 参考訳（メタデータ） (2020-05-11T10:06:40Z) - 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。