論文の概要: Faster Deterministic Approximation Algorithms for Correlation Clustering
and Cluster Deletion
- arxiv url: http://arxiv.org/abs/2111.10699v1
- Date: Sat, 20 Nov 2021 22:47:19 GMT
- ステータス: 処理完了
- システム内更新日: 2021-11-23 17:28:40.344036
- Title: Faster Deterministic Approximation Algorithms for Correlation Clustering
and Cluster Deletion
- Title（参考訳）: 相関クラスタリングとクラスタ削除のための高速決定論的近似アルゴリズム
- Authors: Nate Veldt
- Abstract要約: 相関クラスタリングは、ペアの類似性と相似性スコアに基づいてデータセットをパーティショニングするフレームワークである。
本稿では, 相関クラスタリング問題とエッジラベリング問題との新たな関係性を示す。
我々は,決定論的定数係数近似の保証を有する相関クラスタリングのための新しい近似アルゴリズムを開発し,標準線形プログラミング緩和を回避する。
- 参考スコア（独自算出の注目度）: 5.584060970507507
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Correlation clustering is a framework for partitioning datasets based on
pairwise similarity and dissimilarity scores, and has been used for diverse
applications in bioinformatics, social network analysis, and computer vision.
Although many approximation algorithms have been designed for this problem, the
best theoretical results rely on obtaining lower bounds via expensive linear
programming relaxations. In this paper we prove new relationships between
correlation clustering problems and edge labeling problems related to the
principle of strong triadic closure. We use these connections to develop new
approximation algorithms for correlation clustering that have deterministic
constant factor approximation guarantees and avoid the canonical linear
programming relaxation. Our approach also extends to a variant of correlation
clustering called cluster deletion, that strictly prohibits placing negative
edges inside clusters. Our results include 4-approximation algorithms for
cluster deletion and correlation clustering, based on simplified linear
programs with far fewer constraints than the canonical relaxations. More
importantly, we develop faster techniques that are purely combinatorial, based
on computing maximal matchings in certain auxiliary graphs and hypergraphs.
This leads to a combinatorial 6-approximation for complete unweighted
correlation clustering, which is the best deterministic result for any method
that does not rely on linear programming. We also present the first
combinatorial constant factor approximation for cluster deletion.
- Abstract（参考訳）: 相関クラスタリングは、ペアワイズ類似性と異種性スコアに基づくデータセットのパーティショニングのためのフレームワークであり、バイオインフォマティクス、ソーシャルネットワーク分析、コンピュータビジョンにおける多様な応用に使われている。
多くの近似アルゴリズムがこの問題のために設計されているが、最も理論的な結果は高価な線形プログラミング緩和による下界の獲得に依存している。
本稿では, 相関クラスタリング問題と強三進的閉包の原理に関連するエッジラベリング問題との新たな関係性を示す。
我々はこれらの接続を用いて、決定論的定数係数近似を保証する相関クラスタリングの新しい近似アルゴリズムを開発し、標準線形プログラミング緩和を回避する。
当社のアプローチは,クラスタ内に負のエッジを置くことを厳格に禁止する,クラスタ削除という,相関クラスタの変種にも拡張しています。
その結果,正規緩和よりも制約がはるかに少ない単純な線形プログラムに基づいて,クラスタ欠失と相関クラスタリングのための4近似アルゴリズムが得られた。
さらに重要なことは、ある種の補助グラフやハイパーグラフにおける最大マッチングの計算に基づいて、純粋に組合せ可能な高速な手法を開発することである。
これは完全な非重み付き相関クラスタリングの組合せ 6-近似につながり、線形プログラミングに依存しない任意のメソッドに対して最も決定論的結果となる。
また、クラスタ削除のための最初の組合せ定数係数近似も提示する。
関連論文リスト
- A Semidefinite Programming-Based Branch-and-Cut Algorithm for Biclustering [0.0]
本稿では,二クラスタリング問題に対する分枝切断アルゴリズムを提案する。
提案アルゴリズムは汎用的な解法よりも20倍大きな解法を解くことができることを示す。
論文 参考訳（メタデータ） (2024-03-17T21:43:19Z) - MeanCut: A Greedy-Optimized Graph Clustering via Path-based Similarity
and Degree Descent Criterion [0.6906005491572401]
スペクトルクラスタリングは、優れたパフォーマンス、簡単な実装、強力な適応性のために人気があり、魅力的です。
我々は,MeanCutを目的関数として提案し,非破壊グラフ分割の次数降下順で厳密に最適化する。
本アルゴリズムの有効性は,実世界のベンチマークによる検証と顔認識の適用によって実証される。
論文 参考訳（メタデータ） (2023-12-07T06:19:39Z) - Near-Optimal Correlation Clustering with Privacy [37.94795032297396]
相関クラスタリングは教師なし学習における中心的な問題である。
本稿では,相関クラスタリング問題と証明可能なプライバシ保証のための,シンプルで効率的なアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-03-02T22:30:19Z) - Skew-Symmetric Adjacency Matrices for Clustering Directed Graphs [5.301300942803395]
カットベースの有向グラフ(グラフ)クラスタリングは、しばしばクラスタ内あるいはクラスタ間の疎結合を見つけることに焦点を当てる。
フローベースのクラスタリングでは、クラスタ間のエッジは一方向を向く傾向にあり、マイグレーションデータ、フードウェブ、トレーディングデータに見出されている。
論文 参考訳（メタデータ） (2022-03-02T20:07:04Z) - 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) - Shift of Pairwise Similarities for Data Clustering [3.3178024597495903]
正規化項がクラスタの2乗サイズの和である場合を考察し、ペアの類似性の適応正規化に一般化する。
これは、ペアの類似性を(適切に)シフトさせ、それらのうちのいくつかを負にする可能性がある。
そこで我々は,新しいクラスタリング問題を解くために,高速な理論的収束率を持つ効率的な局所探索最適化アルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-10-25T16:55:07Z) - Clustering Ensemble Meets Low-rank Tensor Approximation [50.21581880045667]
本稿では,複数のクラスタリングを組み合わせ,個々のクラスタリングよりも優れたパフォーマンスを実現するクラスタリングアンサンブルの問題について検討する。
本稿では,この問題をグローバルな視点から解くために,新しい低ランクテンソル近似法を提案する。
7つのベンチマークデータセットを用いた実験の結果,提案手法は12の最先端手法と比較して,クラスタリング性能のブレークスルーを達成した。
論文 参考訳（メタデータ） (2020-12-16T13:01:37Z) - Local Graph Clustering with Network Lasso [90.66817876491052]
局所グラフクラスタリングのためのネットワークLasso法の統計的および計算的性質について検討する。
nLassoによって提供されるクラスタは、クラスタ境界とシードノードの間のネットワークフローを通じて、エレガントに特徴付けられる。
論文 参考訳（メタデータ） (2020-04-25T17:52:05Z) - Fair Correlation Clustering [92.15492066925977]
相関クラスタリングの近似アルゴリズムは,いくつかの重要なフェアネス制約の下で得られる。
相関クラスタリングに対する公平な解は、最先端の(不公平な)アルゴリズムと比較して、コストを抑えながら得られることを示す。
論文 参考訳（メタデータ） (2020-02-06T14:28:21Z) - Clustering Binary Data by Application of Combinatorial Optimization
Heuristics [52.77024349608834]
本稿では,2値データのクラスタリング手法について検討し,まず,クラスタのコンパクトさを計測するアグリゲーション基準を定義した。
近隣地域と人口動態最適化メタヒューリスティックスを用いた5つの新しいオリジナル手法が導入された。
準モンテカルロ実験によって生成された16のデータテーブルから、L1の相似性と階層的クラスタリング、k-means(メドイドやPAM)の1つのアグリゲーションの比較を行う。
論文 参考訳（メタデータ） (2020-01-06T23:33:31Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。