論文の概要: Four Algorithms for Correlation Clustering: A Survey
- arxiv url: http://arxiv.org/abs/2208.12636v1
- Date: Wed, 24 Aug 2022 22:05:24 GMT
- ステータス: 処理完了
- システム内更新日: 2022-08-29 13:36:22.971320
- Title: Four Algorithms for Correlation Clustering: A Survey
- Title（参考訳）: 相関クラスタリングのための4つのアルゴリズム:調査
- Authors: Jafar Jafarov
- Abstract要約: 相関クラスタリング問題は、一対の類似性情報を持つオブジェクトの集合に基づいている。
私たちの目標は、これらのオブジェクトを、可能な限りこの情報にマッチするクラスタに分割することにあります。
目標は、不一致の重みを最小化するクラスタリングを作ることです。
- 参考スコア（独自算出の注目度）: 3.42658286826597
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In the Correlation Clustering problem, we are given a set of objects with
pairwise similarity information. Our aim is to partition these objects into
clusters that match this information as closely as possible. More specifically,
the pairwise information is given as a weighted graph $G$ with its edges
labelled as ``similar" or ``dissimilar" by a binary classifier. The goal is to
produce a clustering that minimizes the weight of ``disagreements": the sum of
the weights of similar edges across clusters and dissimilar edges within
clusters. In this exposition we focus on the case when $G$ is complete and
unweighted. We explore four approximation algorithms for the Correlation
Clustering problem under this assumption. In particular, we describe the
following algorithms: (i) the $17429-$approximation algorithm by Bansal, Blum,
and Chawla, (ii) the $4-$approximation algorithm by Charikar, Guruswami, and
Wirth (iii) the $3-$approximation algorithm by Ailon, Charikar, and Newman (iv)
the $2.06-$approximation algorithm by Chawla, Makarychev, Schramm, and
Yaroslavtsev.
- Abstract（参考訳）: 相関クラスタリング問題では、一対の類似性情報を持つオブジェクトの集合が与えられる。
私たちの目標は、これらのオブジェクトを、可能な限りこの情報にマッチするクラスタに分割することにあります。
より具体的には、対情報は重み付きグラフ $G$ として与えられ、その辺は二進分類器によって ``similar' または ``dissimilar' とラベル付けられている。
目標は、クラスタ間の類似したエッジの重みとクラスタ内の異なるエッジの重みの和である`disagreements'の重みを最小化するクラスタリングを作ることだ。
この表現では、$g$ が完備かつ非重み付けである場合に焦点を当てます。
この仮定の下で相関クラスタリング問題に対する4つの近似アルゴリズムについて検討する。
特に,以下のアルゴリズムについて述べる。
(i)Bansal,Blum,Chawlaによる17429-$approximationアルゴリズム
(ii)charikar,guruswami,wirthによる4ドル近似アルゴリズム
(iii) Ailon, Charikar, Newmanによる3-$approximationアルゴリズム
(iv) Chawla, Makarychev, Schramm, Yaroslavtsevによる2.06-$approximationアルゴリズム。
関連論文リスト
- Multilayer Correlation Clustering [12.492037397168579]
相関クラスタリング(Bansal et al., FOCS '02)の新たな一般化である多層相関クラスタリングを確立する。
本稿では、共通集合である$V$に対して相関クラスタリング(層と呼ばれる)の一連の入力を与えられる。
目的は、不一致ベクトルの$ell_p$-norm(pgeq 1$)を最小化する$V$のクラスタリングを見つけることである。
論文 参考訳（メタデータ） (2024-04-25T15:25:30Z) - A Scalable Algorithm for Individually Fair K-means Clustering [77.93955971520549]
Jung et al. と Mahabadi et al が導入した個別フェア (p$, $k$) クラスタリング問題に対するスケーラブルなアルゴリズムを提案する。
クラスタリングは、各$xin P$に対して$delta(x)$ of $x$の範囲内で中心となる場合、個別にフェアと呼ばれる。
我々は,従来よりもアルゴリズムがはるかに高速であるだけでなく,低コストのソリューションを生み出すことを実証的に示す。
論文 参考訳（メタデータ） (2024-02-09T19:01:48Z) - 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) - 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) - Correlation Clustering with Asymmetric Classification Errors [12.277755088736864]
すべての"類似"エッジ$e$は重みを持つ $mathbfw_ein[alpha mathbfw]$と、すべての"類似"エッジ$e$は重みを持つ $mathbfw_egeq alpha mathbfw。
論文 参考訳（メタデータ） (2021-08-11T12:30:52Z) - Solving correlation clustering with QAOA and a Rydberg qudit system: a
full-stack approach [94.37521840642141]
量子近似最適化アルゴリズム(QAOA)とクォーディットを用いた相関クラスタリング問題について検討する。
具体的には、中性原子量子コンピュータを検討し、相関クラスタリングのためのフルスタックアプローチを提案する。
ゲート数によって定量化されるように、quditの実装はqubitエンコーディングよりも優れていることを示す。
論文 参考訳（メタデータ） (2021-06-22T11:07:38Z) - Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean
Estimation [58.24280149662003]
本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。
我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
論文 参考訳（メタデータ） (2021-06-16T03:34:14Z) - Fuzzy Clustering with Similarity Queries [56.96625809888241]
ファジィ(fuzzy, soft objective)は、よく知られた$k$-means問題の一般化である。
クエリを少なくすることで、問題の解決が容易になる。
論文 参考訳（メタデータ） (2021-06-04T02:32:26Z) - Explainable $k$-Means and $k$-Medians Clustering [25.513261099927163]
我々は、小さな決定木を使ってデータセットをクラスタに分割し、クラスタを直接的な方法で特徴付けることを検討する。
一般的なトップダウン決定木アルゴリズムが任意のコストでクラスタリングに繋がる可能性があることを示す。
我々は、$k$の葉を持つ木を用いて説明可能なクラスタを生成する効率的なアルゴリズムを設計する。
論文 参考訳（メタデータ） (2020-02-28T04:21:53Z) - Query-Efficient Correlation Clustering [13.085439249887713]
相関クラスタリングはクラスタリングの最も自然な定式化であることは間違いない。
相関クラスタリングの主な欠点は、入力として$Theta(n2)$ペアの類似性を必要とすることである。
我々は,最大3cdot OPT + O(fracn3Q)$の相違点が期待される解が得られる相関クラスタリングアルゴリズムを考案した。
論文 参考訳（メタデータ） (2020-02-26T15:18:20Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。