論文の概要: Exact Recovery of Clusters in Finite Metric Spaces Using Oracle Queries
- arxiv url: http://arxiv.org/abs/2102.00504v1
- Date: Sun, 31 Jan 2021 18:00:29 GMT
- ステータス: 処理完了
- システム内更新日: 2021-02-02 16:07:51.790103
- Title: Exact Recovery of Clusters in Finite Metric Spaces Using Oracle Queries
- Title（参考訳）: Oracle Queries を用いた有限メートル空間におけるクラスタの厳密な回復
- Authors: Marco Bressan, Nicol\`o Cesa-Bianchi, Silvio Lattanzi, Andrea Paudice
- Abstract要約: オラクルクエリを用いたクラスタ依存の正確な問題について検討する。
任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意
- 参考スコア（独自算出の注目度）: 22.672233769934845
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We investigate the problem of exact cluster recovery using oracle queries.
Previous results show that clusters in Euclidean spaces that are convex and
separated with a margin can be reconstructed exactly using only $O(\log n)$
same-cluster queries, where $n$ is the number of input points. In this work, we
study this problem in the more challenging non-convex setting. We introduce a
structural characterization of clusters, called $(\beta,\gamma)$-convexity,
that can be applied to any finite set of points equipped with a metric (or even
a semimetric, as the triangle inequality is not needed). Using
$(\beta,\gamma)$-convexity, we can translate natural density properties of
clusters (which include, for instance, clusters that are strongly non-convex in
$R^d$) into a graph-theoretic notion of convexity. By exploiting this convexity
notion, we design a deterministic algorithm that recovers
$(\beta,\gamma)$-convex clusters using $O(k^2 \log n + k^2
(\frac{6}{\beta\gamma})^{dens(X)})$ same-cluster queries, where $k$ is the
number of clusters and $dens(X)$ is the density dimension of the semimetric. We
show that an exponential dependence on the density dimension is necessary, and
we also show that, if we are allowed to make $O(k^2 + k \log n)$ additional
queries to a "cluster separation" oracle, then we can recover clusters that
have different and arbitrary scales, even when the scale of each cluster is
unknown.
- Abstract（参考訳）: oracleクエリを用いて正確なクラスタリカバリの問題を調査する。
以前の結果は、円周で凸かつ分離されたユークリッド空間のクラスタは、$o(\log n)$の同クラスタクエリのみを使用して正確に再構築できることを示している。
本研究では,より困難な非凸環境においてこの問題を研究する。
我々は、計量(あるいは三角不等式を必要としないような半計量)を備えた任意の有限個の点の集合に適用可能な、$(\beta,\gamma)$-凸性と呼ばれるクラスターの構造的特徴付けを導入する。
$(\beta,\gamma)$-凸性を用いることで、(例えば、$R^d$で強く非凸なクラスタを含む)クラスタの自然な密度特性を凸性のグラフ理論の概念に変換することができる。
この凸性の概念を利用して、$O(k^2 \log n + k^2 (\frac{6}{\beta\gamma})^{dens(X)})$ same-cluster query(k$はクラスタ数、$dens(X)$はセミメトリックの密度次元)を用いて、$(\beta,\gamma)$-convexクラスタを復元する決定論的アルゴリズムを設計する。
密度次元への指数関数的依存が必要であることを示し、また、もし「クラスター分離」オラクルに$o(k^2 + k \log n)$の追加クエリを許可すれば、各クラスタのスケールが未知であっても、異なるスケールと任意のスケールのクラスタを復元できることを示した。
関連論文リスト
- A Unified Framework for Gradient-based Clustering of Distributed Data [51.904327888475606]
我々は,ユーザのネットワーク上で動作する分散クラスタリングアルゴリズムのファミリーを開発する。
DGC-$mathcalF_rho$は、K$-meansやHuber Losといった一般的なクラスタリング損失に特化している。
DGC-$mathcalF_rho$のコンセンサス固定点は、全データ上の勾配クラスタリングの固定点と等価であることを示す。
論文 参考訳（メタデータ） (2024-02-02T10:44:42Z) - Do you know what q-means? [50.045011844765185]
クラスタリングは、大規模なデータセットを分析する上で最も重要なツールの1つである。
クラスタリングのための"$q$-means"アルゴリズムの改良版を提案する。
また、$Obig(frack2varepsilon2(sqrtkd + log(Nd))big で実行される $varepsilon に対する "dequantized" アルゴリズムも提示する。
論文 参考訳（メタデータ） (2023-08-18T17:52:12Z) - Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model [79.46465138631592]
観測されたラベルを用いてクラスタを復元する効率的なアルゴリズムを考案する。
本稿では,期待値と高い確率でこれらの下位境界との性能を一致させる最初のアルゴリズムであるIACを提案する。
論文 参考訳（メタデータ） (2023-06-18T08:46:06Z) - Near-Optimal Explainable $k$-Means for All Dimensions [13.673697350508965]
k$-meansのコストは最大$k1 - 2/dmathrmpoly(dlog k)$である。
改良された$k1 - 2/dmathrmpolylog(k)$で、$k,dge 2$から$k$のポリ対数係数までのすべての選択に最適であることを示す。
論文 参考訳（メタデータ） (2021-06-29T16:59:03Z) - On Margin-Based Cluster Recovery with Oracle Queries [22.672233769934845]
1組の$n$ポイントのオラクルと"これらの2つのポイントは同じクラスタ内にあるのか?
本稿では,任意の凸クラスタを正確な時間で復元するアルゴリズムを提案する。
一般の擬計量空間では、クラスターが凸でない場合や、形状の概念が存在しない場合、$O(log n)$クエリ境界を達成し、確実に最適に近いアルゴリズムを与える。
論文 参考訳（メタデータ） (2021-06-09T08:48:23Z) - Fuzzy Clustering with Similarity Queries [56.96625809888241]
ファジィ(fuzzy, soft objective)は、よく知られた$k$-means問題の一般化である。
クエリを少なくすることで、問題の解決が容易になる。
論文 参考訳（メタデータ） (2021-06-04T02:32:26Z) - Sum-of-norms clustering does not separate nearby balls [49.1574468325115]
我々は,データセットを一般的な測度に置き換えた,和和クラスタリングの連続的なバージョンを示す。
我々は,離散データポイントの場合においても,新たなクラスタリングの局所的特徴を記述し,証明する。
論文 参考訳（メタデータ） (2021-04-28T13:35:17Z) - K-expectiles clustering [0.0]
本稿では,期待値に基づく分割クラスタリングアルゴリズムを提案する。
固定$tau$クラスタリングと適応$tau$クラスタリングの2つのスキームを提案します。
論文 参考訳（メタデータ） (2021-03-16T21:14:56Z) - 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) - Explainable $k$-Means and $k$-Medians Clustering [25.513261099927163]
我々は、小さな決定木を使ってデータセットをクラスタに分割し、クラスタを直接的な方法で特徴付けることを検討する。
一般的なトップダウン決定木アルゴリズムが任意のコストでクラスタリングに繋がる可能性があることを示す。
我々は、$k$の葉を持つ木を用いて説明可能なクラスタを生成する効率的なアルゴリズムを設計する。
論文 参考訳（メタデータ） (2020-02-28T04:21:53Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。