論文の概要: Learning-Augmented $k$-means Clustering

• arxiv url: http://arxiv.org/abs/2110.14094v1
• Date: Wed, 27 Oct 2021 00:11:49 GMT
• ステータス: 処理完了
• システム内更新日: 2021-10-29 06:26:56.009114
• Title: Learning-Augmented $k$-means Clustering
• Title（参考訳）: 学習によるk$-meansクラスタリング
• Authors: Jon Ergun, Zhili Feng, Sandeep Silwal, David P. Woodruff, Samson Zhou
• Abstract要約: 予測器を付加した$k$-means問題を考えると、任意の点で、そのクラスタラベルを、何らかの、おそらくは逆のエラーまで、ほぼ最適なクラスタリングで返します。 精度の高い予測器に従えば、高いクラスタリングコストがもたらされるが、予測器の精度とともに性能が向上するアルゴリズムを提案する。 我々は、実際のデータセット上でアルゴリズムを評価し、クラスタリングの品質を大幅に改善したことを示す。
• 参考スコア（独自算出の注目度）: 44.06375788674942
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: $k$-means clustering is a well-studied problem due to its wide applicability. Unfortunately, there exist strong theoretical limits on the performance of any algorithm for the $k$-means problem on worst-case inputs. To overcome this barrier, we consider a scenario where "advice" is provided to help perform clustering. Specifically, we consider the $k$-means problem augmented with a predictor that, given any point, returns its cluster label in an approximately optimal clustering up to some, possibly adversarial, error. We present an algorithm whose performance improves along with the accuracy of the predictor, even though na\"{i}vely following the accurate predictor can still lead to a high clustering cost. Thus if the predictor is sufficiently accurate, we can retrieve a close to optimal clustering with nearly optimal runtime, breaking known computational barriers for algorithms that do not have access to such advice. We evaluate our algorithms on real datasets and show significant improvements in the quality of clustering.
• Abstract（参考訳）: k$-meansクラスタリングは広く適用可能なため、よく研究されている問題である。 残念なことに、最悪の入力に対する$k$-means問題に対するアルゴリズムの性能には強い理論的制限がある。 この障壁を克服するために、クラスタリングの実行を支援する"アドバイス"を提供するシナリオを検討します。 特に、k$-means問題は、任意の時点において、そのクラスタラベルをほぼ最適のクラスタリングで返却する(おそらくは逆)という予測子によって拡張されている。 高精度予測器に追従したna\"{i}velyがクラスタリングコストを上昇させる可能性があるが,予測器の精度とともに性能が向上するアルゴリズムを提案する。 したがって、予測器が十分正確であれば、ほぼ最適な実行時間で、そのようなアドバイスにアクセスできないアルゴリズムの既知の計算障壁を破り、最適なクラスタリングを得られる。 アルゴリズムを実際のデータセット上で評価し,クラスタリングのクオリティが大幅に向上したことを示す。

関連論文リスト

• Near-Optimal Algorithms for Constrained k-Center Clustering with Instance-level Background Knowledge [12.808663917871888]
  我々は、広く採用されている$k$-centerクラスタリングに基づいて、その入力背景知識を must-link (ML) および cannot-link (CL) 制約セットとしてモデル化する。 制約付き$k$-centerの最初の効率的な近似アルゴリズムに到達します。
  論文  参考訳（メタデータ） (2024-01-23T07:16:32Z)
• Rethinking k-means from manifold learning perspective [122.38667613245151]
  平均推定なしで直接データのクラスタを検出する新しいクラスタリングアルゴリズムを提案する。 具体的には,バタワースフィルタを用いてデータ点間の距離行列を構成する。 異なる視点に埋め込まれた相補的な情報をうまく活用するために、テンソルのSchatten p-norm正規化を利用する。
  論文  参考訳（メタデータ） (2023-05-12T03:01:41Z)
• Scalable Clustering: Large Scale Unsupervised Learning of Gaussian Mixture Models with Outliers [5.478764356647437]
  本稿では,損失最小化に基づくロバストなクラスタリングアルゴリズムを提案する。 これはアルゴリズムが高い確率で高い精度を得るという理論的保証を提供する。 実世界の大規模データセットの実験では、アルゴリズムの有効性が示されている。
  論文  参考訳（メタデータ） (2023-02-28T14:39:18Z)
• Differentially-Private Hierarchical Clustering with Provable Approximation Guarantees [79.59010418610625]
  階層クラスタリングのための微分プライベート近似アルゴリズムについて検討する。 例えば、$epsilon$-DPアルゴリズムは入力データセットに対して$O(|V|2/epsilon)$-additiveエラーを示さなければならない。 本稿では,ブロックを正確に復元する1+o(1)$近似アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-01-31T19:14:30Z)
• Sketch-and-solve approaches to k-means clustering by semidefinite programming [14.930208990741132]
  我々は,k-meansクラスタリングのPeng-Wei半定緩和を高速化するためのスケッチ・アンド・ソルジ手法を提案する。 データが適切に分離された場合、k平均の最適なクラスタリングを特定する。 そうでなければ、我々のアプローチは最適k-平均値に高信頼な下界を与える。
  論文  参考訳（メタデータ） (2022-11-28T19:51:30Z)
• Fuzzy Clustering with Similarity Queries [56.96625809888241]
  ファジィ(fuzzy, soft objective)は、よく知られた$k$-means問題の一般化である。 クエリを少なくすることで、問題の解決が容易になる。
  論文  参考訳（メタデータ） (2021-06-04T02:32:26Z)
• Clustering of Big Data with Mixed Features [3.3504365823045044]
  我々は混合型の大規模データのための新しいクラスタリングアルゴリズムを開発した。 このアルゴリズムは、比較的低い密度値の外れ値とクラスターを検出することができる。 本研究では,本アルゴリズムが実際に有効であることを示す実験結果を示す。
  論文  参考訳（メタデータ） (2020-11-11T19:54:38Z)
• Differentially Private Clustering: Tight Approximation Ratios [57.89473217052714]
  基本的なクラスタリング問題に対して,効率的な微分プライベートアルゴリズムを提案する。 この結果から,SampleとAggregateのプライバシーフレームワークのアルゴリズムの改善が示唆された。 1-Clusterアルゴリズムで使用されるツールの1つは、ClosestPairのより高速な量子アルゴリズムを適度な次元で得るために利用できる。
  論文  参考訳（メタデータ） (2020-08-18T16:22:06Z)
• Computationally efficient sparse clustering [67.95910835079825]
  我々はPCAに基づく新しいクラスタリングアルゴリズムの有限サンプル解析を行う。 ここでは,ミニマックス最適誤クラスタ化率を,体制$|theta infty$で達成することを示す。
  論文  参考訳（メタデータ） (2020-05-21T17:51:30Z)
• Explainable $k$-Means and $k$-Medians Clustering [25.513261099927163]
  我々は、小さな決定木を使ってデータセットをクラスタに分割し、クラスタを直接的な方法で特徴付けることを検討する。 一般的なトップダウン決定木アルゴリズムが任意のコストでクラスタリングに繋がる可能性があることを示す。 我々は、$k$の葉を持つ木を用いて説明可能なクラスタを生成する効率的なアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2020-02-28T04:21:53Z)

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

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