論文の概要: On Approximability of Clustering Problems Without Candidate Centers
- arxiv url: http://arxiv.org/abs/2010.00087v2
- Date: Fri, 2 Oct 2020 17:35:55 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-13 00:38:12.879149
- Title: On Approximability of Clustering Problems Without Candidate Centers
- Title（参考訳）: 候補中心を持たないクラスタリング問題の近似可能性について
- Authors: Vincent Cohen-Addad, Karthik C. S., and Euiwoong Lee
- Abstract要約: k-平均の目的は、計量空間におけるクラスタリングタスクをモデル化するための最も広く使われるコスト関数である。
本稿では,これらの目的のために文献で知られている近似係数の硬さを大幅に改善する。
その結果、連続的な設定におけるクラスタリング問題と離散的な設定におけるクラスタリング問題の違いについて、新しい、おそらく反直感的な光を当てた。
- 参考スコア（独自算出の注目度）: 17.24716331811351
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The k-means objective is arguably the most widely-used cost function for
modeling clustering tasks in a metric space. In practice and historically,
k-means is thought of in a continuous setting, namely where the centers can be
located anywhere in the metric space. For example, the popular Lloyd's
heuristic locates a center at the mean of each cluster.
Despite persistent efforts on understanding the approximability of k-means,
and other classic clustering problems such as k-median and k-minsum, our
knowledge of the hardness of approximation factors of these problems remains
quite poor. In this paper, we significantly improve upon the hardness of
approximation factors known in the literature for these objectives. We show
that if the input lies in a general metric space, it is NP-hard to approximate:
$\bullet$ Continuous k-median to a factor of $2-o(1)$; this improves upon the
previous inapproximability factor of 1.36 shown by Guha and Khuller (J.
Algorithms '99).
$\bullet$ Continuous k-means to a factor of $4- o(1)$; this improves upon the
previous inapproximability factor of 2.10 shown by Guha and Khuller (J.
Algorithms '99).
$\bullet$ k-minsum to a factor of $1.415$; this improves upon the
APX-hardness shown by Guruswami and Indyk (SODA '03).
Our results shed new and perhaps counter-intuitive light on the differences
between clustering problems in the continuous setting versus the discrete
setting (where the candidate centers are given as part of the input).
- Abstract（参考訳）: k-means の目的は、メトリック空間におけるクラスタリングタスクのモデリングに最も広く使われているコスト関数である。
実践的かつ歴史的に、k-平均は連続的な設定、すなわち、中心が計量空間のどこにでも配置できる場所で考えられている。
例えば、人気のあるロイドのヒューリスティックは、各クラスタの平均に中心を配置する。
k-means の近似可能性や k-median や k-minsum のような古典的なクラスタリング問題を理解する努力は絶え間ないが、これらの問題の近似因子の難しさに関する我々の知識は依然として極めて乏しいままである。
本稿では,これらの目的のために文献で知られている近似因子の硬さを著しく改善する。
入力が一般計量空間にある場合、NP-ハードで近似できることが示される:$\bullet$ Continuous k-median to a factor of $2-o(1)$; これは、Guha と Khuller (J. Algorithms '99) が示した 1.36 の前の不近似係数を改善する。
$\bullet$ 4- o(1)$ の連続 k-平均は、Guha と Khuller (J. Algorithms '99) が示した2.10 の非近似係数により改善される。
$\bullet$ k-minsum to a factor of $1.415$, this improves on the APX-hardness shown by Guruswami and Indyk (SODA '03)。
その結果、連続設定におけるクラスタリング問題と離散設定(入力の一部として候補センターが与えられる)の違いについて、新しくて直観に反する光が得られた。
関連論文リスト
- Fair Clustering for Data Summarization: Improved Approximation Algorithms and Complexity Insights [16.120911591795295]
一部のアプリケーションでは、すべてのデータポイントをセンターとして選択できるが、一般的な設定では、施設またはサプライヤーと呼ばれる一連のポイントからセンターを選択する必要がある。
そこで本研究では,複数のグループから構成されるデータに対して,各グループから最小限のセンタを選択する必要がある,公平な$k$-supplier問題としてモデル化された公平なデータ要約に焦点を当てる。
論文 参考訳（メタデータ） (2024-10-16T18:00:19Z) - Self-Supervised Graph Embedding Clustering [70.36328717683297]
K-means 1-step dimensionality reduction clustering method は,クラスタリングタスクにおける次元性の呪いに対処する上で,いくつかの進歩をもたらした。
本稿では,K-meansに多様体学習を統合する統一フレームワークを提案する。
論文 参考訳（メタデータ） (2024-09-24T08:59:51Z) - ABCDE: Application-Based Cluster Diff Evals [49.1574468325115]
それは実用性を目指しており、アイテムはアプリケーション固有の重要な値を持つことができ、クラスタリングがどちらが優れているかを判断するときに人間の判断を使うのは粗悪であり、アイテムの任意のスライスのためのメトリクスを報告できる。
クラスタリング品質の差分を測定するアプローチは、高価な地平を前もって構築し、それに関して各クラスタリングを評価する代わりに、ABCDEはクラスタリング間の実際の差分に基づいて、判定のための質問をサンプリングする。
論文 参考訳（メタデータ） (2024-07-31T08:29:35Z) - Rethinking k-means from manifold learning perspective [122.38667613245151]
平均推定なしで直接データのクラスタを検出する新しいクラスタリングアルゴリズムを提案する。
具体的には,バタワースフィルタを用いてデータ点間の距離行列を構成する。
異なる視点に埋め込まれた相補的な情報をうまく活用するために、テンソルのSchatten p-norm正規化を利用する。
論文 参考訳（メタデータ） (2023-05-12T03:01:41Z) - Lattice-Based Methods Surpass Sum-of-Squares in Clustering [98.46302040220395]
クラスタリングは教師なし学習における基本的なプリミティブである。
最近の研究は、低次手法のクラスに対する低い境界を確立している。
意外なことに、この特定のクラスタリングモデルのtextitdoesは、統計的-計算的ギャップを示さない。
論文 参考訳（メタデータ） (2021-12-07T18:50:17Z) - Johnson Coverage Hypothesis: Inapproximability of k-means and k-median
in L_p metrics [16.953720670216093]
K-medianとk-meansはクラスタリングアルゴリズムの最も一般的な2つの目的である。
これらの目的のために文献で知られている近似係数の硬さを著しく改善する。
論文 参考訳（メタデータ） (2021-11-21T22:42:42Z) - Uniform Concentration Bounds toward a Unified Framework for Robust
Clustering [21.789311405437573]
センターベースのクラスタリングの最近の進歩は、ロイドの有名な$k$-meansアルゴリズムの欠点によって改善され続けている。
様々な手法は、ローカル・ミニマ(英語版)の貧弱さ、異常値に対する感度、ユークリッドの対応に適さないデータに対処しようとする。
本稿では,一般的な相似性尺度に基づく中心クラスタリングのための密結合型ロバストフレームワークを提案する。
論文 参考訳（メタデータ） (2021-10-27T03:43:44Z) - Fuzzy Clustering with Similarity Queries [56.96625809888241]
ファジィ(fuzzy, soft objective)は、よく知られた$k$-means問題の一般化である。
クエリを少なくすることで、問題の解決が容易になる。
論文 参考訳（メタデータ） (2021-06-04T02:32:26Z) - Socially Fair k-Means Clustering [3.3409719900340256]
我々は、異なるグループに対して公平なコストを提供するクラスタセンターを選択するための、公平なk平均目標とアルゴリズムを提案する。
このアルゴリズムであるFair-Lloydは、ロイドのk平均に対する修正であり、その単純さ、効率、安定性を継承している。
論文 参考訳（メタデータ） (2020-06-17T18:05:17Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。