論文の概要: Strong bounds for large-scale Minimum Sum-of-Squares Clustering

• arxiv url: http://arxiv.org/abs/2502.08397v1
• Date: Wed, 12 Feb 2025 13:40:00 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-13 13:44:47.904011
• Title: Strong bounds for large-scale Minimum Sum-of-Squares Clustering
• Title（参考訳）: 大規模最小二乗クラスタリングのための強境界
• Authors: Anna Livia Croella, Veronica Piccialli, Antonio M. Sudoso,
• Abstract要約: Minimum Sum-of-Squares Clustering (MSSC)は、最も広く使われているクラスタリング手法の1つである。 MSSCは、データポイントとそれに対応するクラスタセントロイド間の合計2乗ユークリッド距離を最小化することを目的としている。 最適性ギャップによるMSSCソリューションの検証手法を提案する。
• 参考スコア（独自算出の注目度）: 0.9831489366502302
• License:
• Abstract: Clustering is a fundamental technique in data analysis and machine learning, used to group similar data points together. Among various clustering methods, the Minimum Sum-of-Squares Clustering (MSSC) is one of the most widely used. MSSC aims to minimize the total squared Euclidean distance between data points and their corresponding cluster centroids. Due to the unsupervised nature of clustering, achieving global optimality is crucial, yet computationally challenging. The complexity of finding the global solution increases exponentially with the number of data points, making exact methods impractical for large-scale datasets. Even obtaining strong lower bounds on the optimal MSSC objective value is computationally prohibitive, making it difficult to assess the quality of heuristic solutions. We address this challenge by introducing a novel method to validate heuristic MSSC solutions through optimality gaps. Our approach employs a divide-and-conquer strategy, decomposing the problem into smaller instances that can be handled by an exact solver. The decomposition is guided by an auxiliary optimization problem, the "anticlustering problem", for which we design an efficient heuristic. Computational experiments demonstrate the effectiveness of the method for large-scale instances, achieving optimality gaps below 3% in most cases while maintaining reasonable computational times. These results highlight the practicality of our approach in assessing feasible clustering solutions for large datasets, bridging a critical gap in MSSC evaluation.
• Abstract（参考訳）: クラスタリングは、類似のデータポイントをまとめるのに使用される、データ分析と機械学習の基本的なテクニックである。 クラスタリング手法としては,MSSC (Minimum Sum-of-Squares Clustering) がある。 MSSCは、データポイントとそれに対応するクラスタセントロイド間の合計2乗ユークリッド距離を最小化することを目的としている。 クラスタリングの教師なしの性質のため、グローバルな最適性を達成することは重要であるが、計算的に困難である。 グローバルソリューションを見つける複雑さは、データポイントの数とともに指数関数的に増加し、大規模なデータセットでは正確なメソッドが実用的でない。 最適MSSC目標値の強い下限さえも計算的に禁止されており、ヒューリスティックな解の質を評価することは困難である。 最適性ギャップを通じてヒューリスティックMSSCソリューションを検証する新しい手法を導入することで、この問題に対処する。 提案手法では分割・対数戦略を用いて,問題をより小さなインスタンスに分解し,正確な解法で処理する。 この分解は、効率的なヒューリスティックを設計する補助最適化問題である「反クラスタリング問題」によって導かれる。 計算実験は、大規模インスタンスに対する手法の有効性を実証し、計算時間を維持しながら、ほとんどのケースにおいて3%未満の最適性ギャップを達成している。 これらの結果は,MSSC評価において重要なギャップを埋めるとともに,大規模データセットに対する実現可能なクラスタリングソリューションの評価において,我々のアプローチの実用性を強調した。

関連論文リスト

• Self-Supervised Graph Embedding Clustering [70.36328717683297]
  K-means 1-step dimensionality reduction clustering method は,クラスタリングタスクにおける次元性の呪いに対処する上で,いくつかの進歩をもたらした。 本稿では,K-meansに多様体学習を統合する統一フレームワークを提案する。
  論文  参考訳（メタデータ） (2024-09-24T08:59:51Z)
• A cutting plane algorithm for globally solving low dimensional k-means clustering problems [4.5594982923247995]
  我々は、低次元データを持つインスタンスのk-means問題を考え、これを構造的凹面割り当て問題として定式化する。 これにより、低次元構造を利用して、妥当な時間で大域的最適性に問題を解くことができる。 本論文は,グローバル最適化理論の手法を組み合わせて手順を高速化し,数値的な結果を提供する。
  論文  参考訳（メタデータ） (2024-02-21T07:55:33Z)
• Mostly Beneficial Clustering: Aggregating Data for Operational Decision Making [3.9825334703672812]
  本稿では,クラスタ構造を利用したShrunken-SAA手法を提案する。 問題の数が増えるにつれて、問題間で与えられたクラスタ構造を活用することで、さらなるメリットが得られます。 提案手法は, 軽度条件下での一般的なコスト関数に拡張することができる。
  論文  参考訳（メタデータ） (2023-11-29T02:53:32Z)
• On the Global Solution of Soft k-Means [159.23423824953412]
  本稿では,ソフトk-平均問題の解法を全世界で提案する。 ミニマルボリュームソフトkMeans (MVSkM) と呼ばれる新しいモデルを提案する。
  論文  参考訳（メタデータ） (2022-12-07T12:06:55Z)
• A One-shot Framework for Distributed Clustered Learning in Heterogeneous Environments [54.172993875654015]
  異種環境における分散学習のためのコミュニケーション効率化手法のファミリーを提案する。 ユーザによるローカル計算に基づくワンショットアプローチと、サーバにおけるクラスタリングベースのアグリゲーションステップは、強力な学習保証を提供する。 厳密な凸問題に対しては,ユーザ毎のデータ点数がしきい値を超える限り,提案手法はサンプルサイズの観点から順序最適平均二乗誤差率を達成する。
  論文  参考訳（メタデータ） (2022-09-22T09:04:10Z)
• How to Use K-means for Big Data Clustering? [2.1165011830664677]
  K-meansはEuclidean Minimum Sum-of-Squares Clustering (MSSC)モデルの下で最もシンプルで広く使われているアルゴリズムである。 ビッグデータクラスタリングにK-means++アルゴリズムとK-means++アルゴリズムを用いる並列方式を提案する。
  論文  参考訳（メタデータ） (2022-04-14T08:18:01Z)
• A sampling-based approach for efficient clustering in large datasets [0.8952229340927184]
  本稿では,多数のクラスタを持つ高次元データに対して,簡便かつ効率的なクラスタリング手法を提案する。 私たちのコントリビューションは、データポイントとクラスタの完全な比較を必要としないため、k-meansよりもはるかに効率的です。
  論文  参考訳（メタデータ） (2021-12-29T19:15:20Z)
• Differentially-Private Clustering of Easy Instances [67.04951703461657]
  異なるプライベートクラスタリングでは、個々のデータポイントに関する情報を公開せずに、$k$のクラスタセンターを特定することが目標だ。 我々は、データが"簡単"である場合にユーティリティを提供する実装可能な差分プライベートクラスタリングアルゴリズムを提供する。 我々は、非プライベートクラスタリングアルゴリズムを簡単なインスタンスに適用し、結果をプライベートに組み合わせることのできるフレームワークを提案する。
  論文  参考訳（メタデータ） (2021-12-29T08:13:56Z)
• An Exact Algorithm for Semi-supervised Minimum Sum-of-Squares Clustering [0.5801044612920815]
  半教師付きMSSCのための分岐結合アルゴリズムを提案する。 背景知識はペアワイズ・マスタリンクと結びつかない制約として組み込まれている。 提案したグローバル最適化アルゴリズムは,実世界のインスタンスを最大800個のデータポイントまで効率的に解決する。
  論文  参考訳（メタデータ） (2021-11-30T17:08:53Z)
• Meta Clustering Learning for Large-scale Unsupervised Person Re-identification [124.54749810371986]
  メタクラスタリング学習(MCL)と呼ばれる「大規模タスクのための小さなデータ」パラダイムを提案する。 MCLは、第1フェーズのトレーニングのためにコンピューティングを節約するためにクラスタリングを介して、未ラベルデータのサブセットを擬似ラベル付けするのみである。 提案手法は計算コストを大幅に削減すると同時に,従来よりも優れた性能を実現している。
  論文  参考訳（メタデータ） (2021-11-19T04:10:18Z)
• Learnable Subspace Clustering [76.2352740039615]
  本研究では,大規模サブスペースクラスタリング問題を効率的に解くために,学習可能なサブスペースクラスタリングパラダイムを開発する。 鍵となる考え方は、高次元部分空間を下層の低次元部分空間に分割するパラメトリック関数を学ぶことである。 我々の知る限り、本論文は、サブスペースクラスタリング手法の中で、数百万のデータポイントを効率的にクラスタ化する最初の試みである。
  論文  参考訳（メタデータ） (2020-04-09T12:53:28Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。