論文の概要: Learning-Augmented Hierarchical Clustering

• arxiv url: http://arxiv.org/abs/2506.05495v1
• Date: Thu, 05 Jun 2025 18:22:40 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-09 17:28:43.192004
• Title: Learning-Augmented Hierarchical Clustering
• Title（参考訳）: 学習強化階層クラスタリング
• Authors: Vladimir Braverman, Jon C. Ergun, Chen Wang, Samson Zhou,
• Abstract要約: 自然のオラクルから補助情報を得た階層的クラスタリングの問題を考察する。 分割オラクルは、アルゴリズムが標準のHCアプローチより優れていることを示す。 我々のアプローチはサブ線形設定にまで拡張され、保証を改善した新しいストリーミングとPRAMアルゴリズムが示されます。
• 参考スコア（独自算出の注目度）: 29.438861266606573
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Hierarchical clustering (HC) is an important data analysis technique in which the goal is to recursively partition a dataset into a tree-like structure while grouping together similar data points at each level of granularity. Unfortunately, for many of the proposed HC objectives, there exist strong barriers to approximation algorithms with the hardness of approximation. Thus, we consider the problem of hierarchical clustering given auxiliary information from natural oracles. Specifically, we focus on a *splitting oracle* which, when provided with a triplet of vertices $(u,v,w)$, answers (possibly erroneously) the pairs of vertices whose lowest common ancestor includes all three vertices in an optimal tree, i.e., identifying which vertex ``splits away'' from the others. Using such an oracle, we obtain the following results: - A polynomial-time algorithm that outputs a hierarchical clustering tree with $O(1)$-approximation to the Dasgupta objective (Dasgupta [STOC'16]). - A near-linear time algorithm that outputs a hierarchical clustering tree with $(1-o(1))$-approximation to the Moseley-Wang objective (Moseley and Wang [NeurIPS'17]). Under the plausible Small Set Expansion Hypothesis, no polynomial-time algorithm can achieve any constant approximation for Dasgupta's objective or $(1-C)$-approximation for the Moseley-Wang objective for some constant $C>0$. As such, our results demonstrate that the splitting oracle enables algorithms to outperform standard HC approaches and overcome hardness constraints. Furthermore, our approaches extend to sublinear settings, in which we show new streaming and PRAM algorithms for HC with improved guarantees.
• Abstract（参考訳）: 階層的クラスタリング(HC)は、データセットを木のような構造に再帰的に分割し、類似のデータポイントを粒度ごとにグループ化する、重要なデータ分析手法である。 残念なことに、提案されている多くのHC目標に対して、近似の難しさを伴う近似アルゴリズムには強い障壁が存在する。 そこで本研究では,自然のオラクルから補助情報を得る階層的クラスタリングの問題点を考察する。 具体的には、*splitting oracle* に焦点をあてる。これは、頂点のトリプルトが与えられたときに、最も共通の祖先が最適木にある3つの頂点すべてを含む頂点のペア、すなわち、頂点の ``splits away' を他の木から識別する(誤って)答えである。 このようなオラクルを用いて、Dasgupta の目的(Dasgupta [STOC'16])に対して$O(1)$-approximation の階層的クラスタリング木を出力する多項式時間アルゴリズムを得る。 -Moseley-Wang目標(Moseley and Wang [NeurIPS'17])に対して(1-o(1))$-approximationの階層的クラスタリングツリーを出力するニア線形時間アルゴリズム。 可算小集合展開仮説の下では、ある定数$C>0$のモーゼリー=ワングの目的に対してダスグプタの目的に対して定数近似や(1-C)$-近似を達成できない多項式時間アルゴリズムは存在しない。 その結果, 分割オラクルは, アルゴリズムが標準HC手法より優れ, 硬度制約を克服できることを示した。 さらに、我々のアプローチはサブ線形設定にまで拡張され、保証を改善したHCのための新しいストリーミングおよびPRAMアルゴリズムが示される。

関連論文リスト

• Accelerating k-Means Clustering with Cover Trees [0.30693357740321775]
  表木指数に基づく新しいk-meansアルゴリズムを提案し, オーバーヘッドが比較的低く, 性能も良好である。 木集約と境界に基づくフィルタリングの利点を組み合わせたハイブリッドアルゴリズムを得る。
  論文  参考訳（メタデータ） (2024-10-19T14:02:42Z)
• Revisiting Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model [69.15976031704687]
  IAC (Instance-Adaptive Clustering, インスタンス適応クラスタリング) を提案する。 IACは$ MathcalO(n, textpolylog(n) $の計算複雑性を維持しており、大規模問題に対してスケーラブルで実用的なものである。
  論文  参考訳（メタデータ） (2023-06-18T08:46:06Z)
• 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)
• An objective function for order preserving hierarchical clustering [0.0]
  確率的部分順序の類似性に基づく階層的クラスタリングの理論と目的関数を提案する。 具体的には、元 $x le y$ が部分順序で与えられ、それぞれのクラスタ $[x]$ と $[y]$ が与えられたとき、その理論はクラスタ上で $[x]le'[y]$ となるような順序関係 $le'$ が得られる。
  論文  参考訳（メタデータ） (2021-09-09T13:35:01Z)
• An Information-theoretic Perspective of Hierarchical Clustering [30.896561720088954]
  階層クラスタリングのコスト関数はDasgupta citedasgupta 2016 Costによって導入された。 本稿では,階層的クラスタリングをインセンフィス理論の観点から検討し,新たな目的関数を定式化する。
  論文  参考訳（メタデータ） (2021-08-13T03:03:56Z)
• Solving correlation clustering with QAOA and a Rydberg qudit system: a full-stack approach [94.37521840642141]
  量子近似最適化アルゴリズム(QAOA)とクォーディットを用いた相関クラスタリング問題について検討する。 具体的には、中性原子量子コンピュータを検討し、相関クラスタリングのためのフルスタックアプローチを提案する。 ゲート数によって定量化されるように、quditの実装はqubitエンコーディングよりも優れていることを示す。
  論文  参考訳（メタデータ） (2021-06-22T11:07:38Z)
• Fuzzy Clustering with Similarity Queries [56.96625809888241]
  ファジィ(fuzzy, soft objective)は、よく知られた$k$-means問題の一般化である。 クエリを少なくすることで、問題の解決が容易になる。
  論文  参考訳（メタデータ） (2021-06-04T02:32:26Z)
• Exact and Approximate Hierarchical Clustering Using A* [51.187990314731344]
  クラスタリングのA*探索に基づく新しいアプローチを紹介します。 A*と新しいエンフォレリスデータ構造を組み合わせることで、禁止的に大きな検索空間を克服します。 実験により,本手法は粒子物理利用事例や他のクラスタリングベンチマークにおいて,ベースラインよりもかなり高品質な結果が得られることを示した。
  論文  参考訳（メタデータ） (2021-04-14T18:15:27Z)
• Explainable $k$-Means and $k$-Medians Clustering [25.513261099927163]
  我々は、小さな決定木を使ってデータセットをクラスタに分割し、クラスタを直接的な方法で特徴付けることを検討する。 一般的なトップダウン決定木アルゴリズムが任意のコストでクラスタリングに繋がる可能性があることを示す。 我々は、$k$の葉を持つ木を用いて説明可能なクラスタを生成する効率的なアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2020-02-28T04:21:53Z)

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

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