論文の概要: On Margin-Based Cluster Recovery with Oracle Queries
- arxiv url: http://arxiv.org/abs/2106.04913v1
- Date: Wed, 9 Jun 2021 08:48:23 GMT
- ステータス: 処理完了
- システム内更新日: 2021-06-10 15:22:51.461847
- Title: On Margin-Based Cluster Recovery with Oracle Queries
- Title（参考訳）: oracleクエリによるマージンベースのクラスタリカバリについて
- Authors: Marco Bressan, Nicol\`o Cesa-Bianchi, Silvio Lattanzi, Andrea Paudice
- Abstract要約: 1組の$n$ポイントのオラクルと"これらの2つのポイントは同じクラスタ内にあるのか?
本稿では,任意の凸クラスタを正確な時間で復元するアルゴリズムを提案する。
一般の擬計量空間では、クラスターが凸でない場合や、形状の概念が存在しない場合、$O(log n)$クエリ境界を達成し、確実に最適に近いアルゴリズムを与える。
- 参考スコア（独自算出の注目度）: 22.672233769934845
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study an active cluster recovery problem where, given a set of $n$ points
and an oracle answering queries like "are these two points in the same
cluster?", the task is to recover exactly all clusters using as few queries as
possible. We begin by introducing a simple but general notion of margin between
clusters that captures, as special cases, the margins used in previous work,
the classic SVM margin, and standard notions of stability for center-based
clusterings. Then, under our margin assumptions we design algorithms that, in a
variety of settings, recover all clusters exactly using only $O(\log n)$
queries. For the Euclidean case, $\mathbb{R}^m$, we give an algorithm that
recovers arbitrary convex clusters, in polynomial time, and with a number of
queries that is lower than the best existing algorithm by $\Theta(m^m)$
factors. For general pseudometric spaces, where clusters might not be convex or
might not have any notion of shape, we give an algorithm that achieves the
$O(\log n)$ query bound, and is provably near-optimal as a function of the
packing number of the space. Finally, for clusterings realized by binary
concept classes, we give a combinatorial characterization of recoverability
with $O(\log n)$ queries, and we show that, for many concept classes in
Euclidean spaces, this characterization is equivalent to our margin condition.
Our results show a deep connection between cluster margins and active cluster
recoverability.
- Abstract（参考訳）: 私たちは、n$ポイントのセットとoracleが“これら2つのポイントは同じクラスタ内にあるか?
タスクは、可能な限り少数のクエリを使用して、正確にすべてのクラスタをリカバリすることです。
まず、特に、以前の研究で使われたマージン、古典的なSVMマージン、センターベースのクラスタリングの安定性の標準概念をキャプチャするクラスタ間のマージンの単純だが一般的な概念を導入する。
そして、マージンの仮定の下で、さまざまな設定で、$O(\log n)$クエリのみを使用して、すべてのクラスタを正確に回復するアルゴリズムを設計します。
ユークリッドの場合、$\mathbb{r}^m$ は任意の凸クラスタを多項式時間で回復するアルゴリズムであり、既存のアルゴリズムの最も低いクエリを$\theta(m^m)$ factor で与える。
一般の擬距離空間では、クラスターが凸でない場合や、形状の概念が存在しない場合、$O(\log n)$クエリバウンドを達成し、空間のパッキング数の関数として証明可能な準最適であるアルゴリズムを与える。
最後に、二項概念クラスによって実現されたクラスタリングに対して、$O(\log n)$クエリによる回復可能性の組合せ的特徴付けを行い、ユークリッド空間における多くの概念クラスに対して、この特徴付けが我々のマージン条件に等しいことを示す。
その結果,クラスタマージンとアクティブクラスタリカバリ可能性との深い関係が示された。
関連論文リスト
- ABCDE: Application-Based Cluster Diff Evals [49.1574468325115]
それは実用性を目指しており、アイテムはアプリケーション固有の重要な値を持つことができ、クラスタリングがどちらが優れているかを判断するときに人間の判断を使うのは粗悪であり、アイテムの任意のスライスのためのメトリクスを報告できる。
クラスタリング品質の差分を測定するアプローチは、高価な地平を前もって構築し、それに関して各クラスタリングを評価する代わりに、ABCDEはクラスタリング間の実際の差分に基づいて、判定のための質問をサンプリングする。
論文 参考訳（メタデータ） (2024-07-31T08:29:35Z) - Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model [79.46465138631592]
観測されたラベルを用いてクラスタを復元する効率的なアルゴリズムを考案する。
本稿では,期待値と高い確率でこれらの下位境界との性能を一致させる最初のアルゴリズムであるIACを提案する。
論文 参考訳（メタデータ） (2023-06-18T08:46:06Z) - Recovering Unbalanced Communities in the Stochastic Block Model With
Application to Clustering with a Faulty Oracle [9.578056676899203]
オラクルブロックモデル(英: Oracle block model、SBM)は、ネットワークにおけるグラフクラスタリングやコミュニティ検出を研究するための基礎モデルである。
我々は,SBMのコミュニティを様々な大きさのコミュニティで復元する,シンプルなSVDベースのアルゴリズムを提供する。
論文 参考訳（メタデータ） (2022-02-17T08:51:19Z) - Lattice-Based Methods Surpass Sum-of-Squares in Clustering [98.46302040220395]
クラスタリングは教師なし学習における基本的なプリミティブである。
最近の研究は、低次手法のクラスに対する低い境界を確立している。
意外なことに、この特定のクラスタリングモデルのtextitdoesは、統計的-計算的ギャップを示さない。
論文 参考訳（メタデータ） (2021-12-07T18:50:17Z) - Fuzzy Clustering with Similarity Queries [56.96625809888241]
ファジィ(fuzzy, soft objective)は、よく知られた$k$-means問題の一般化である。
クエリを少なくすることで、問題の解決が容易になる。
論文 参考訳（メタデータ） (2021-06-04T02:32:26Z) - K-expectiles clustering [0.0]
本稿では,期待値に基づく分割クラスタリングアルゴリズムを提案する。
固定$tau$クラスタリングと適応$tau$クラスタリングの2つのスキームを提案します。
論文 参考訳（メタデータ） (2021-03-16T21:14:56Z) - Exact Recovery of Clusters in Finite Metric Spaces Using Oracle Queries [22.672233769934845]
オラクルクエリを用いたクラスタ依存の正確な問題について検討する。
任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意
論文 参考訳（メタデータ） (2021-01-31T18:00:29Z) - Scalable Hierarchical Agglomerative Clustering [65.66407726145619]
既存のスケーラブルな階層的クラスタリング手法は、スピードの質を犠牲にする。
我々は、品質を犠牲にせず、数十億のデータポイントまでスケールする、スケーラブルで集約的な階層的クラスタリング法を提案する。
論文 参考訳（メタデータ） (2020-10-22T15:58:35Z) - Exact Recovery of Mangled Clusters with Same-Cluster Queries [20.03712152278538]
半教師付きアクティブクラスタリングフレームワークにおけるクラスタリカバリ問題について検討する。
我々は、$n$ポイントを$k$クラスタに分割するアルゴリズムを設計し、$O(k3 ln k ln n)$oracleクエリと$tildeO(kn + k3)$でクラスタを非分類エラーで復元する。
論文 参考訳（メタデータ） (2020-06-08T15:27:58Z) - Computationally efficient sparse clustering [67.95910835079825]
我々はPCAに基づく新しいクラスタリングアルゴリズムの有限サンプル解析を行う。
ここでは,ミニマックス最適誤クラスタ化率を,体制$|theta infty$で達成することを示す。
論文 参考訳（メタデータ） (2020-05-21T17:51:30Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。