論文の概要: Why does Greedy Search produce Optimal Clustering Outcomes? A Fixed-Core Assignment Theory

• arxiv url: http://arxiv.org/abs/2607.24237v2
• Date: Wed, 29 Jul 2026 16:47:30 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-07-30 14:21:10.712367
• Title: Why does Greedy Search produce Optimal Clustering Outcomes? A Fixed-Core Assignment Theory
• Title（参考訳）: なぜGreedy Searchは最適なクラスタリング結果を生成するのか?固定コア割り当て理論
• Authors: Kaifeng Zhang, Kai Ming Ting, Sanjay Chawla,
• Abstract要約: クラスタの形状が不規則な場合、クラスタのパフォーマンスは著しく悪化し、クラスタ毎に密度やサイズが変化する。 最近のクラスタ・アズ・ディストリビューション(CaD)クラスタリングは、これらの一般的なタイプのクラスタを発見することが示されている。 これは、欲求探索によるCaDクラスタリングが任意の形状、密度、大きさのクラスタを発見できる理由を説明する最初の分析である。
• 参考スコア（独自算出の注目度）: 12.631764566188407
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Many existing clustering methods are designed based on a set-oriented definition---a cluster is a set of similar points---relying a point-to-point similarity function to find similar points. This works well for compact clusters, but clustering performance can deteriorate badly when cluster shapes are irregular, and densities or sizes vary between clusters. Recent `Cluster-as-Distribution' (CaD) clustering has been shown to discover these generic types of clusters in practice by treating each cluster as a set of independent and identically distributed points generated from some unknown distribution via a greedy search, achieving a clustering objective equivalent to that of Spectral Clustering, but with better clustering outcomes without eigen-decomposition. However, a theoretical analysis of this phenomenon is still lacking. Our analyses are from two angles. First, we analyze the approximation error between the true and empirical distribution embeddings. Second, we show that the greedy search employed to achieve the CaD clustering objective can be mapped to a partition matroid---yielding greedy optimality. These yield a near-optimality guarantee for the CaD clustering objective, with regret controlled by the approximation error. This is the first analysis that explains why CaD clustering via greedy search can discover clusters of arbitrary shapes, densities and sizes (where all set-oriented clustering methods have failed to discover) when the estimated cluster embeddings faithfully approximate the underlying cluster distributions.
• Abstract（参考訳）: 多くの既存のクラスタリング手法は、セット指向の定義に基づいて設計されており、クラスタは類似した点の集合である。 これは、コンパクトクラスタではうまく機能するが、クラスタの形状が不規則な場合にはクラスタのパフォーマンスが悪化し、クラスタ間で密度やサイズが変化する。 近年の'Cluster-as-Distribution' (CaD) クラスタリングは,各クラスタを,スペクトルクラスタリングと同等のクラスタ化目標を達成するとともに,固有分解のないクラスタリング結果により,未知の分布から生成される独立および同一の分散点の集合として扱うことで,これらの一般的なクラスタのタイプを実際に発見することが示されている。 しかし、この現象に関する理論的分析はまだ不十分である。 私たちの分析は2つの角度から行われている。 まず,真の分布埋め込みと経験的分布埋め込みの近似誤差を解析する。 次に,CaDクラスタリングの目的を達成するために用いられる欲求探索を分割マトロイドにマッピングできることを示す。 これらはCaDクラスタリングの目的に対してほぼ最適に保証され、後悔は近似誤差によって制御される。 これは、推定されたクラスタの埋め込みが基礎となるクラスタ分布を忠実に近似した場合に、欲求探索によるCaDクラスタリングが任意の形状、密度、大きさのクラスタ(すべてのセット指向クラスタリングメソッドが発見できなかった)を発見できる理由を説明する最初の分析である。

関連論文リスト

• Guaranteed Recovery of Unambiguous Clusters [7.011239860967789]
  クラスタリングは、しばしば難しい問題である。なぜなら、それは、"正しい"クラスタリングがどうあるべきかに固有の曖昧さのためである。 本稿は,クラスタ内の2つの高密度領域が,K$clusteringの2つの真に異なるクラスタよりも,2つの異なるクラスタのように見えるほど分離可能な状況について定式化する。
  論文  参考訳（メタデータ） (2025-01-22T18:51:25Z)
• 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)
• Reinforcement Graph Clustering with Unknown Cluster Number [91.4861135742095]
  本稿では,Reinforcement Graph Clusteringと呼ばれる新しいディープグラフクラスタリング手法を提案する。 提案手法では,クラスタ数決定と教師なし表現学習を統一的なフレームワークに統合する。 フィードバック動作を行うために、クラスタリング指向の報酬関数を提案し、同一クラスタの凝集を高め、異なるクラスタを分離する。
  論文  参考訳（メタデータ） (2023-08-13T18:12:28Z)
• Revisiting Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model [85.51611950757643]
  IAC (Instance-Adaptive Clustering, インスタンス適応クラスタリング) を提案する。 IACは$ MathcalO(n, textpolylog(n) $の計算複雑性を維持しており、大規模問題に対してスケーラブルで実用的なものである。
  論文  参考訳（メタデータ） (2023-06-18T08:46:06Z)
• A Computational Theory and Semi-Supervised Algorithm for Clustering [0.0]
  クラスタリングは異常のないデータのグループ化の獲得である。 クラスタリング手法のカーネルは知覚異常検出アルゴリズムである。 半教師付きクラスタリングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-06-12T09:15:58Z)
• Self-supervised Contrastive Attributed Graph Clustering [110.52694943592974]
  我々は,自己教師型コントラストグラフクラスタリング(SCAGC)という,新たな属性グラフクラスタリングネットワークを提案する。 SCAGCでは,不正確なクラスタリングラベルを活用することで,ノード表現学習のための自己教師付きコントラスト損失を設計する。 OOSノードでは、SCAGCはクラスタリングラベルを直接計算できる。
  論文  参考訳（メタデータ） (2021-10-15T03:25:28Z)
• K-expectiles clustering [0.0]
  本稿では,期待値に基づく分割クラスタリングアルゴリズムを提案する。 固定$tau$クラスタリングと適応$tau$クラスタリングの2つのスキームを提案します。
  論文  参考訳（メタデータ） (2021-03-16T21:14:56Z)
• Scalable Hierarchical Agglomerative Clustering [65.66407726145619]
  既存のスケーラブルな階層的クラスタリング手法は、スピードの質を犠牲にする。 我々は、品質を犠牲にせず、数十億のデータポイントまでスケールする、スケーラブルで集約的な階層的クラスタリング法を提案する。
  論文  参考訳（メタデータ） (2020-10-22T15:58:35Z)

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

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