論文の概要: Small Is Not Dead: Distance-Aware Cluster Revival for e-means
- arxiv url: http://arxiv.org/abs/2611.18238v1
- Date: Fri, 13 Nov 2026 14:32:35 GMT
- ステータス: 情報取得中
- システム内更新日: 2026-11-16 19:22:56.934095
- Title: Small Is Not Dead: Distance-Aware Cluster Revival for e-means
- Title(参考訳): 小さめは死んでいない:e-meansの遠隔クラスターを復活させる
- Abstract要約: e-meansは、大きな埋め込みデータセットよりも桁違いに高速であるロイドのアルゴリズムの誤差に達する。
5つのミニバッチごとに、ランニングポイント数が平均の10分の1以下であるすべてのクラスタを削除し、その中心を再利用して大規模なクラスタを分割する。
埋め込みベンチマークでは、除去を決して防ぐことができないため、結果はFAISSと同一である。
- 参考スコア(独自算出の注目度): 0.913755431537592
- License:
- Abstract: e-means (Bessa et al., 2026) is a recent mini-batch k-means algorithm, now part of the FAISS library, that reaches the error of Lloyd's algorithm about an order of magnitude faster on large embedding datasets. Every five mini-batches, it removes every cluster whose running point count falls below a tenth of the average and reuses its centre to split a large cluster. In the authors' ablation, removing this mechanism, called dead-cluster revival, raises the error more than removing any other component added to the moving-average update. The rule, however, considers only cluster size: it cannot distinguish a cluster that is small because it is redundant from one that covers a rare, isolated group of points, and on data with such groups it repeatedly removes centres whose removal is costly. We add a second condition, based on the distance between centres: a small cluster is removed only if its centre is close to another centre, relative to a running estimate of the mean squared error. When a centre equals the mean of its points, this squared distance is an upper bound on the average increase in squared error, per point of the cluster, caused by removing the centre. The condition costs one nearest-centre search for the small clusters every five mini-batches and adds no measurable running time. On the e-means paper's embedding benchmarks, it never prevents a removal, so the results are identical to those of FAISS. On datasets with small isolated groups not used during development, it reduces the test error after two epochs by roughly 10% to 80% relative to count-based revival, and it preserves the advantage of k-means++ initialization; on the other evaluation datasets, it stays within about 1% of the better of revival enabled and disabled. We also report two failure modes that the analysis predicts. This is a CPU proof of concept; GPU implementations are left to future work.
- Abstract(参考訳): e-means (Bessa et al , 2026) は最近のミニバッチk-meansアルゴリズムで、現在はFAISSライブラリの一部となっている。
5つのミニバッチごとに、ランニングポイント数が平均の10分の1以下であるすべてのクラスタを削除し、その中心を再利用して大規模なクラスタを分割する。
著者のアブレーションでは、デッドクラスタリバイバルと呼ばれるこのメカニズムを削除することで、移動平均更新に追加される他のコンポーネントを削除するよりも、エラーを発生させる。
しかし、このルールはクラスタサイズのみを考慮しており、希少で孤立した点群をカバーするクラスタとは冗長であるため、小さいクラスタを区別することはできない。
中心間の距離に基づいて第2の条件を加える: 中心が他の中心に近い場合のみ、その平均二乗誤差のランニング推定に対して、小さなクラスタが除去される。
中心がその点の平均と等しいとき、この2乗距離は、中心を取り除くことによって引き起こされるクラスターの点あたりの平均的な2乗誤差の増加の上限である。
この条件は5つのミニバッチごとに1つの最寄りのクラスタを探索し、測定可能な実行時間を追加しない。
e-meansの論文の埋め込みベンチマークでは、除去を決して防ぐことができないため、結果はFAISSと同一である。
開発中に使われていない小さな独立したグループを持つデータセットでは、2つのエポック後のテストエラーを、カウントベースのリバイバルと比較して約10%から80%削減し、k-means++初期化の利点を保ちます。
また、分析が予測する2つの障害モードを報告します。
これはCPUの概念実証であり、GPUの実装は将来の作業に委ねられている。
関連論文リスト
- e-means: outperforming k-means (in one-tenth the epochs) [22.735518961851856]
ミニバッチ更新を伴うk平均の指数的移動平均最適化手法を提案する。
また、崩壊率とバッチサイズが最終的なパフォーマンスに与える影響について、スケーリング法則を定めています。
結果として得られたクラスタリングアルゴリズムは e-means と呼ばれ、ロイズk-means よりもはるかに高速で、損失の減少に収束する。
論文 参考訳(メタデータ) (2026-11-06T14:22:43Z) - MNAR-$k$-means: A $k$-means Clustering for Data Missing Not at Random with Magnitude-Decaying Probability [7.3226942109207895]
本稿では,命令値の大きさの制約に基づく新しい$k$-meansクラスタリング手法を提案する。
本研究では,提案手法のクラスタ中心から完全に観測されたデータの真のクラスタ中心まで,推定されたクラスタ中心の統計的一貫性を確立する。
論文 参考訳(メタデータ) (2026-06-30T07:31:22Z) - Self-Supervised Graph Embedding Clustering [70.36328717683297]
K-means 1-step dimensionality reduction clustering method は,クラスタリングタスクにおける次元性の呪いに対処する上で,いくつかの進歩をもたらした。
本稿では,K-meansに多様体学習を統合する統一フレームワークを提案する。
論文 参考訳(メタデータ) (2024-09-24T08:59:51Z) - A Unified Framework for Center-based Clustering of Distributed Data [46.86543102499174]
我々は、ユーザのネットワーク上で動作する分散センターベースのクラスタリングアルゴリズムのファミリーを開発する。
私たちのフレームワークは、$K$-meansやHuber Losといった一般的なクラスタリング損失を含む、スムーズな凸損失関数の幅広いクラスを可能にします。
ブレグマン損失の特別の場合、固定点がロイド点の集合に収束することを示す。
論文 参考訳(メタデータ) (2024-02-02T10:44:42Z) - Rethinking k-means from manifold learning perspective [122.38667613245151]
平均推定なしで直接データのクラスタを検出する新しいクラスタリングアルゴリズムを提案する。
具体的には,バタワースフィルタを用いてデータ点間の距離行列を構成する。
異なる視点に埋め込まれた相補的な情報をうまく活用するために、テンソルのSchatten p-norm正規化を利用する。
論文 参考訳(メタデータ) (2023-05-12T03:01:41Z) - An enhanced method of initial cluster center selection for K-means
algorithm [0.0]
K-meansアルゴリズムの初期クラスタ選択を改善するための新しい手法を提案する。
Convex Hullアルゴリズムは、最初の2つのセントロイドの計算を容易にし、残りの2つは、以前選択された中心からの距離に応じて選択される。
We obtained only 7.33%, 7.90%, and 0% clustering error in Iris, Letter, and Ruspini data。
論文 参考訳(メタデータ) (2022-10-18T00:58:50Z) - Sum-of-norms clustering does not separate nearby balls [49.1574468325115]
我々は,データセットを一般的な測度に置き換えた,和和クラスタリングの連続的なバージョンを示す。
我々は,離散データポイントの場合においても,新たなクラスタリングの局所的特徴を記述し,証明する。
論文 参考訳(メタデータ) (2021-04-28T13:35:17Z) - Computationally efficient sparse clustering [67.95910835079825]
我々はPCAに基づく新しいクラスタリングアルゴリズムの有限サンプル解析を行う。
ここでは,ミニマックス最適誤クラスタ化率を,体制$|theta infty$で達成することを示す。
論文 参考訳(メタデータ) (2020-05-21T17:51:30Z) - Ball k-means [53.89505717006118]
Ball k-meansアルゴリズムは、ポイントセントロイド距離計算の削減に集中して、クラスタを記述するためにボールを使用する。
高速、余分なパラメータなし、単純設計のボールk平均アルゴリズムは、素早いk平均アルゴリズムを全面的に置き換える。
論文 参考訳(メタデータ) (2020-05-02T10:39:26Z) - Structures of Spurious Local Minima in $k$-means [20.155509538529568]
我々は、$k$-means問題に対する急激な局所解の構造について検討する。
分離条件下では,この現象が唯一の局所的局所最小値であることを示す。
論文 参考訳(メタデータ) (2020-02-16T22:15:03Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。