論文の概要: A cutting plane algorithm for globally solving low dimensional k-means clustering problems

• arxiv url: http://arxiv.org/abs/2402.13595v1
• Date: Wed, 21 Feb 2024 07:55:33 GMT
• ステータス: 処理完了
• システム内更新日: 2024-02-22 16:33:06.989356
• Title: A cutting plane algorithm for globally solving low dimensional k-means clustering problems
• Title（参考訳）: 低次元k平均クラスタリング問題をグローバルに解くための切削面アルゴリズム
• Authors: Martin Ryner, Jan Kronqvist, Johan Karlsson
• Abstract要約: 我々は、低次元データを持つインスタンスのk-means問題を考え、これを構造的凹面割り当て問題として定式化する。 これにより、低次元構造を利用して、妥当な時間で大域的最適性に問題を解くことができる。 本論文は,グローバル最適化理論の手法を組み合わせて手順を高速化し,数値的な結果を提供する。
• 参考スコア（独自算出の注目度）: 4.5594982923247995
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Clustering is one of the most fundamental tools in data science and machine learning, and k-means clustering is one of the most common such methods. There is a variety of approximate algorithms for the k-means problem, but computing the globally optimal solution is in general NP-hard. In this paper we consider the k-means problem for instances with low dimensional data and formulate it as a structured concave assignment problem. This allows us to exploit the low dimensional structure and solve the problem to global optimality within reasonable time for large data sets with several clusters. The method builds on iteratively solving a small concave problem and a large linear programming problem. This gives a sequence of feasible solutions along with bounds which we show converges to zero optimality gap. The paper combines methods from global optimization theory to accelerate the procedure, and we provide numerical results on their performance.
• Abstract（参考訳）: クラスタリングはデータサイエンスと機械学習の最も基本的なツールの1つであり、k平均クラスタリングはそのような方法の最も一般的な1つである。 k-平均問題には様々な近似アルゴリズムが存在するが、グローバル最適解の計算は一般にnp-hardである。 本稿では,低次元データを持つ場合のk-means問題について考察し,構造化凹代入問題として定式化する。 これにより、複数のクラスタを持つ大規模データセットに対して、低次元構造を利用し、妥当な時間内にグローバルな最適性への問題を解くことができる。 本手法は,小さな凹面問題と大規模な線形プログラミング問題を反復的に解くことに基づく。 これにより、ゼロ最適性ギャップに収束することを示す境界とともに、実現可能な解の列が与えられる。 本論文は,グローバル最適化理論の手法を組み合わせて手順を高速化し,その性能に関する数値的な結果を提供する。

関連論文リスト

• From Large to Small Datasets: Size Generalization for Clustering Algorithm Selection [12.993073967843292]
  我々は,未知の地下構造クラスタリングを用いて,半教師付き環境で問題を研究する。 本稿では,クラスタリングアルゴリズムの精度向上のためのサイズ一般化の概念を提案する。 データセット全体においてどのアルゴリズムが最適かを特定するために、データの5%をサブサンプルとして使用しています。
  論文  参考訳（メタデータ） (2024-02-22T06:53:35Z)
• A Novel Normalized-Cut Solver with Nearest Neighbor Hierarchical Initialization [107.07093621337084]
  正規化カット(N-Cut)は、スペクトルクラスタリングの有名なモデルである。 1)正規化ラプラシア行列の連続スペクトル埋め込みを計算する; 2)$K$-meansまたはスペクトル回転による離散化。 有名な座標降下法に基づく新しいN-Cut解法を提案する。
  論文  参考訳（メタデータ） (2023-11-26T07:11:58Z)
• Linear time Evidence Accumulation Clustering with KMeans [0.0]
  この研究は、平均的なリンククラスタリングの振る舞いを模倣するトリックを記述する。 分割の密度を効率よく計算する方法を見つけ、二次的な複雑さから線形的な複雑さへのコストを削減した。 k平均結果は、計算コストを低く保ちながら、NMIの観点からは、最先端の技術に匹敵する。
  論文  参考訳（メタデータ） (2023-11-15T14:12:59Z)
• Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
  凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。 多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。 そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
  論文  参考訳（メタデータ） (2023-07-17T20:11:56Z)
• Approximating a RUM from Distributions on k-Slates [88.32814292632675]
  与えられた分布を平均で最もよく近似するRUMを求める一般化時間アルゴリズムを求める。 我々の理論的結果は、実世界のデータセットに効果的でスケール可能なものを得るという、実践的な結果も得られます。
  論文  参考訳（メタデータ） (2023-05-22T17:43:34Z)
• Rethinking k-means from manifold learning perspective [122.38667613245151]
  平均推定なしで直接データのクラスタを検出する新しいクラスタリングアルゴリズムを提案する。 具体的には,バタワースフィルタを用いてデータ点間の距離行列を構成する。 異なる視点に埋め込まれた相補的な情報をうまく活用するために、テンソルのSchatten p-norm正規化を利用する。
  論文  参考訳（メタデータ） (2023-05-12T03:01:41Z)
• Randomized Greedy Algorithms and Composable Coreset for k-Center Clustering with Outliers [11.546734084378683]
  外れ値の存在は計算の複雑さを著しく増大させる。 我々のアイデアは、通常の$k$-centerクラスタリング問題を解決するために開発されたgreedy法にインスパイアされている。
  論文  参考訳（メタデータ） (2023-01-07T09:26:01Z)
• On the Global Solution of Soft k-Means [159.23423824953412]
  本稿では,ソフトk-平均問題の解法を全世界で提案する。 ミニマルボリュームソフトkMeans (MVSkM) と呼ばれる新しいモデルを提案する。
  論文  参考訳（メタデータ） (2022-12-07T12:06:55Z)
• 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)
• Differentially Private Clustering: Tight Approximation Ratios [57.89473217052714]
  基本的なクラスタリング問題に対して,効率的な微分プライベートアルゴリズムを提案する。 この結果から,SampleとAggregateのプライバシーフレームワークのアルゴリズムの改善が示唆された。 1-Clusterアルゴリズムで使用されるツールの1つは、ClosestPairのより高速な量子アルゴリズムを適度な次元で得るために利用できる。
  論文  参考訳（メタデータ） (2020-08-18T16:22:06Z)
• An Efficient Smoothing Proximal Gradient Algorithm for Convex Clustering [2.5182813818441945]
  最近導入された凸クラスタリング手法は、凸最適化問題としてクラスタリングを定式化している。 最先端の凸クラスタリングアルゴリズムは大規模な計算とメモリ空間を必要とする。 本稿では,凸クラスタリングのための非常に効率的なスムーズな勾配法 (Sproga) を提案する。
  論文  参考訳（メタデータ） (2020-06-22T20:02:59Z)

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

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