論文の概要: A Sublinear-Time Spectral Clustering Oracle with Improved Preprocessing Time

• arxiv url: http://arxiv.org/abs/2310.17878v2
• Date: Fri, 29 Dec 2023 08:32:43 GMT
• ステータス: 処理完了
• システム内更新日: 2024-01-03 01:09:54.380908
• Title: A Sublinear-Time Spectral Clustering Oracle with Improved Preprocessing Time
• Title（参考訳）: プリプロセッシング時間を改善するサブリニア時間スペクトルクラスタリングオラクル
• Authors: Ranran Shen, Pan Peng
• Abstract要約: 本稿では,クラスタ性が強いグラフに対して,サブ線形時間スペクトルクラスタリングオラクルを設計する問題に対処する。 アルゴリズムは仮定を緩和するが、誤分類比はわずかに高い。 私たちのクラスタリングオラクルは、いくつかのランダムなエッジ削除に対して堅牢です。
• 参考スコア（独自算出の注目度）: 6.961946145048321
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We address the problem of designing a sublinear-time spectral clustering oracle for graphs that exhibit strong clusterability. Such graphs contain $k$ latent clusters, each characterized by a large inner conductance (at least $\varphi$) and a small outer conductance (at most $\varepsilon$). Our aim is to preprocess the graph to enable clustering membership queries, with the key requirement that both preprocessing and query answering should be performed in sublinear time, and the resulting partition should be consistent with a $k$-partition that is close to the ground-truth clustering. Previous oracles have relied on either a $\textrm{poly}(k)\log n$ gap between inner and outer conductances or exponential (in $k/\varepsilon$) preprocessing time. Our algorithm relaxes these assumptions, albeit at the cost of a slightly higher misclassification ratio. We also show that our clustering oracle is robust against a few random edge deletions. To validate our theoretical bounds, we conducted experiments on synthetic networks.
• Abstract（参考訳）: 本稿では,クラスタ性が強いグラフに対して,サブ線形時間スペクトルクラスタリングオラクルを設計する問題に対処する。 これらのグラフは、それぞれ大きな内部伝導(少なくとも$\varphi$)と小さな外部伝導(ほとんどの$\varepsilon$)によって特徴づけられる、潜伏クラスター$k$を含む。 我々の目的は、グラフを前処理してクラスタリングメンバシップクエリを有効にすることであり、前処理とクエリ応答の両方をサブライン時間で実行し、その結果のパーティションは、地上のクラスタリングに近い$k$-partitionと整合性を持つべきである。 以前のオラクルは、内部コンダクタンスと外部コンダクタンスの間の$\textrm{poly}(k)\log n$ギャップか($k/\varepsilon$)前処理時間に依存していた。 我々のアルゴリズムは、少し高い分類率のコストで、これらの仮定を緩和する。 また、クラスタリングオラクルはいくつかのランダムなエッジ削除に対して堅牢であることを示す。 理論境界を検証するために,合成ネットワーク実験を行った。

関連論文リスト

• Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model [79.46465138631592]
  観測されたラベルを用いてクラスタを復元する効率的なアルゴリズムを考案する。 本稿では,期待値と高い確率でこれらの下位境界との性能を一致させる最初のアルゴリズムであるIACを提案する。
  論文  参考訳（メタデータ） (2023-06-18T08:46:06Z)
• Approximating a RUM from Distributions on k-Slates [88.32814292632675]
  与えられた分布を平均で最もよく近似するRUMを求める一般化時間アルゴリズムを求める。 我々の理論的結果は、実世界のデータセットに効果的でスケール可能なものを得るという、実践的な結果も得られます。
  論文  参考訳（メタデータ） (2023-05-22T17:43:34Z)
• Optimal Clustering with Bandit Feedback [57.672609011609886]
  本稿では,バンディットフィードバックを用いたオンラインクラスタリングの問題点について考察する。 これは、NPハード重み付きクラスタリング問題をサブルーチンとして解決する必要性を回避するための、シーケンシャルなテストのための新しい停止規則を含む。 合成および実世界のデータセットの広範なシミュレーションを通して、BOCの性能は下界と一致し、非適応的ベースラインアルゴリズムよりも大幅に優れることを示す。
  論文  参考訳（メタデータ） (2022-02-09T06:05:05Z)
• Lattice-Based Methods Surpass Sum-of-Squares in Clustering [98.46302040220395]
  クラスタリングは教師なし学習における基本的なプリミティブである。 最近の研究は、低次手法のクラスに対する低い境界を確立している。 意外なことに、この特定のクラスタリングモデルのtextitdoesは、統計的-計算的ギャップを示さない。
  論文  参考訳（メタデータ） (2021-12-07T18:50:17Z)
• Towards a Query-Optimal and Time-Efficient Algorithm for Clustering with a Faulty Oracle [7.449644976563424]
  本稿では,クラスタリングを不良オラクルで研究するためのエレガントな理論的モデルを提案する。 一般の場合の$k$クラスタに対して、クエリ最適で時間効率のアルゴリズムを得られるかどうかというオープンな疑問として残された。 情報理論の回復が可能であれば,全ての定数$k$に対して,ほぼ最適なクエリ複雑性(最大$O(log2 n)$)を持つ時間効率アルゴリズムを提供する。
  論文  参考訳（メタデータ） (2021-06-18T22:20:12Z)
• 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)
• 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)
• Query-Efficient Correlation Clustering [13.085439249887713]
  相関クラスタリングはクラスタリングの最も自然な定式化であることは間違いない。 相関クラスタリングの主な欠点は、入力として$Theta(n2)$ペアの類似性を必要とすることである。 我々は,最大3cdot OPT + O(fracn3Q)$の相違点が期待される解が得られる相関クラスタリングアルゴリズムを考案した。
  論文  参考訳（メタデータ） (2020-02-26T15:18:20Z)

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

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