論文の概要: Query-Efficient Correlation Clustering
- arxiv url: http://arxiv.org/abs/2002.11557v1
- Date: Wed, 26 Feb 2020 15:18:20 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-28 15:44:09.480885
- Title: Query-Efficient Correlation Clustering
- Title（参考訳）: クエリ効率の良い相関クラスタリング
- Authors: David Garc\'ia-Soriano, Konstantin Kutzkov, Francesco Bonchi,
Charalampos Tsourakakis
- Abstract要約: 相関クラスタリングはクラスタリングの最も自然な定式化であることは間違いない。
相関クラスタリングの主な欠点は、入力として$Theta(n2)$ペアの類似性を必要とすることである。
我々は,最大3cdot OPT + O(fracn3Q)$の相違点が期待される解が得られる相関クラスタリングアルゴリズムを考案した。
- 参考スコア（独自算出の注目度）: 13.085439249887713
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Correlation clustering is arguably the most natural formulation of
clustering. Given n objects and a pairwise similarity measure, the goal is to
cluster the objects so that, to the best possible extent, similar objects are
put in the same cluster and dissimilar objects are put in different clusters.
A main drawback of correlation clustering is that it requires as input the
$\Theta(n^2)$ pairwise similarities. This is often infeasible to compute or
even just to store. In this paper we study \emph{query-efficient} algorithms
for correlation clustering. Specifically, we devise a correlation clustering
algorithm that, given a budget of $Q$ queries, attains a solution whose
expected number of disagreements is at most $3\cdot OPT + O(\frac{n^3}{Q})$,
where $OPT$ is the optimal cost for the instance. Its running time is $O(Q)$,
and can be easily made non-adaptive (meaning it can specify all its queries at
the outset and make them in parallel) with the same guarantees. Up to constant
factors, our algorithm yields a provably optimal trade-off between the number
of queries $Q$ and the worst-case error attained, even for adaptive algorithms.
Finally, we perform an experimental study of our proposed method on both
synthetic and real data, showing the scalability and the accuracy of our
algorithm.
- Abstract（参考訳）: 相関クラスタリングは、おそらく最も自然なクラスタリングの定式化である。
n個のオブジェクトとペアの類似度の測定値が与えられた場合、目的はオブジェクトをクラスタ化し、可能な限り、類似したオブジェクトを同じクラスタに配置し、異なるオブジェクトを異なるクラスタに配置することである。
相関クラスタリングの主な欠点は、入力として$\theta(n^2)$ の類似性が必要であることである。
これはしばしば計算や保存だけでは不可能である。
本稿では相関クラスタリングのためのemph{query- efficient}アルゴリズムについて検討する。
具体的には,$Q$クエリの予算が与えられた場合,最大で$3\cdot OPT + O(\frac{n^3}{Q})$で,$OPT$がインスタンスの最適コストとなるような相関クラスタリングアルゴリズムを考案する。
実行時間は$o(q)$であり、同じ保証で、容易に非適応にすることができる(つまり、開始時にすべてのクエリを指定でき、並列にすることができる)。
このアルゴリズムは, 適応アルゴリズムにおいても, クエリ数$Q$と, 最悪のエラー発生率との間に, 確実に最適なトレードオフをもたらす。
最後に,提案手法である合成データと実データの両方について実験を行い,アルゴリズムのスケーラビリティと精度を示す。
関連論文リスト
- Do you know what q-means? [50.045011844765185]
クラスタリングは、大規模なデータセットを分析する上で最も重要なツールの1つである。
クラスタリングのための"$q$-means"アルゴリズムの改良版を提案する。
また、$Obig(frack2varepsilon2(sqrtkd + log(Nd))big で実行される $varepsilon に対する "dequantized" アルゴリズムも提示する。
論文 参考訳（メタデータ） (2023-08-18T17:52:12Z) - Are Easy Data Easy (for K-Means) [0.0]
本稿では、$k$-meansアルゴリズムの様々なブランドによって、適切に分離されたクラスタを復元する能力について検討する。
シード選択時に繰り返しサブサンプリングによって$k$-means++のバリエーションが提案される。
論文 参考訳（メタデータ） (2023-08-02T09:40:19Z) - Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model [79.46465138631592]
観測されたラベルを用いてクラスタを復元する効率的なアルゴリズムを考案する。
本稿では,期待値と高い確率でこれらの下位境界との性能を一致させる最初のアルゴリズムであるIACを提案する。
論文 参考訳（メタデータ） (2023-06-18T08:46:06Z) - Improved Learning-augmented Algorithms for k-means and k-medians
Clustering [8.04779839951237]
学習強化設定におけるクラスタリングの問題について考察し、そこでは、$d$次元ユークリッド空間のデータセットが与えられる。
本稿では,クラスタリングコストを改良したセンターを生成する決定論的$k$-meansアルゴリズムを提案する。
我々のアルゴリズムは、予測があまり正確でないときでも機能する。つまり、我々の限界は$alpha$を$/2$に保ち、以前の研究で$alpha$よりも1/7$に改善する。
論文 参考訳（メタデータ） (2022-10-31T03:00:11Z) - How to Query An Oracle? Efficient Strategies to Label Data [59.89900843097016]
機械学習におけるデータセットのラベル付けに専門家の託宣を照会する際の基本的な問題について考察する。
本稿では,サンプルをラベル付けするために,ラウンド・バイ・ラウンドでランダム化されたバッチアルゴリズムを提案し,クエリレートが$O(fracNk2)$であることを示す。
さらに,適応型グリージークエリ方式を提案し,三重項クエリを用いたサンプルあたり平均$approx 0.2N$クエリを実現する。
論文 参考訳（メタデータ） (2021-10-05T20:15:35Z) - 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) - 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。