論文の概要: Fair Correlation Clustering
- arxiv url: http://arxiv.org/abs/2002.03508v1
- Date: Mon, 10 Feb 2020 02:59:17 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-02 07:11:27.587244
- Title: Fair Correlation Clustering
- Title（参考訳）: 公正な相関クラスタリング
- Authors: Saba Ahmadi, Sainyam Galhotra, Barna Saha, Roy Schwartz
- Abstract要約: 本稿では,各ノードが色を持つ相関クラスタリング問題に対して,公平性制約の2つのバリエーションを検討する。
本研究では,実世界のデータセットに対する実験的な評価により,公平なクラスタを生成するアルゴリズムの有効性を示す。
- 参考スコア（独自算出の注目度）: 18.00619071013106
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In this paper we study the problem of correlation clustering under fairness
constraints. In the classic correlation clustering problem, we are given a
complete graph where each edge is labeled positive or negative. The goal is to
obtain a clustering of the vertices that minimizes disagreements -- the number
of negative edges trapped inside a cluster plus positive edges between
different clusters.
We consider two variations of fairness constraint for the problem of
correlation clustering where each node has a color, and the goal is to form
clusters that do not over-represent vertices of any color.
The first variant aims to generate clusters with minimum disagreements, where
the distribution of a feature (e.g. gender) in each cluster is same as the
global distribution. For the case of two colors when the desired ratio of the
number of colors in each cluster is $1:p$, we get
$\mathcal{O}(p^2)$-approximation algorithm. Our algorithm could be extended to
the case of multiple colors. We prove this problem is NP-hard.
The second variant considers relative upper and lower bounds on the number of
nodes of any color in a cluster. The goal is to avoid violating upper and lower
bounds corresponding to each color in each cluster while minimizing the total
number of disagreements. Along with our theoretical results, we show the
effectiveness of our algorithm to generate fair clusters by empirical
evaluation on real world data sets.
- Abstract（参考訳）: 本稿では,正当性制約下での相関クラスタリングの問題について検討する。
古典的な相関クラスタリング問題では、各辺が正または負のラベル付けされた完全グラフが与えられる。
目的は、クラスタ内に閉じ込められた負のエッジの数と異なるクラスタ間の正のエッジを最小化する、頂点のクラスタリングを得ることだ。
各ノードが色を持つ相関クラスタリングの問題に対して,フェアネス制約の2つのバリエーションを考察し,任意の色の頂点を過剰に表現しないクラスタを形成することを目標とした。
最初の変種は、各クラスタにおける特徴(例えば性別)の分布がグローバルな分布と同じである最小の不一致でクラスタを生成することを目的としている。
2色の場合、各クラスタ内の色数の所望の比率が1:p$の場合、$\mathcal{o}(p^2)$近似アルゴリズムが得られる。
アルゴリズムは複数の色に拡張できる。
我々はこの問題がNPハードであることを証明する。
第2の変種は、クラスタ内の任意の色のノード数に対する相対的な上限と下限を考える。
目的は、クラスタ内の各色に対応する上下境界の違反を回避し、不一致の総数を最小限に抑えることである。
本研究では,実世界のデータセットに対する経験的評価により,公平なクラスタを生成するアルゴリズムの有効性を示す。
関連論文リスト
- Learning Uniform Clusters on Hypersphere for Deep Graph-level Clustering [25.350054742471816]
我々はUDGC(Uniform Deep Graph Clustering)と呼ばれる新しいディープグラフレベルのクラスタリング手法を提案する。
UDGCはインスタンスを異なるクラスタに均等に割り当て、次にこれらのクラスタをユニットハイパースフィア上に分散させ、より均一なクラスタレベルの分散と、より小さなクラスタ崩壊につながる。
8つのよく知られたデータセットに関する実証研究は、UDGCが最先端のモデルを大幅に上回っていることを示している。
論文 参考訳（メタデータ） (2023-11-23T12:08:20Z) - Reinforcement Graph Clustering with Unknown Cluster Number [91.4861135742095]
本稿では,Reinforcement Graph Clusteringと呼ばれる新しいディープグラフクラスタリング手法を提案する。
提案手法では,クラスタ数決定と教師なし表現学習を統一的なフレームワークに統合する。
フィードバック動作を行うために、クラスタリング指向の報酬関数を提案し、同一クラスタの凝集を高め、異なるクラスタを分離する。
論文 参考訳（メタデータ） (2023-08-13T18:12:28Z) - Dink-Net: Neural Clustering on Large Graphs [59.10189693120368]
ディープグラフクラスタリング法 (Dink-Net) は, 拡張と縮小という概念を用いて提案される。
ノードを識別することにより、拡張によって劣化しても、表現は自己教師された方法で学習される。
クラスタリング分布は、提案したクラスタ拡張損失とクラスタ縮小損失を最小化することにより最適化される。
ランナアップと比較して、Dink-Net 9.62%は1100万ノードと16億エッジを持つogbn-papers100MデータセットでNMIの改善を実現している。
論文 参考訳（メタデータ） (2023-05-28T15:33:24Z) - ClusterFuG: Clustering Fully connected Graphs by Multicut [20.254912065749956]
密マルチカットでは、クラスタリングの目的はノード特徴ベクトルの内部積として分解形式で与えられる。
我々は、密集した環境でのマルチカットのための古典的欲求アルゴリズムの書き直し方法と、より効率とソリューションの品質を高めるためにそれらをどう修正するかを示す。
論文 参考訳（メタデータ） (2023-01-28T11:10:50Z) - Anomaly Clustering: Grouping Images into Coherent Clusters of Anomaly
Types [60.45942774425782]
我々は異常クラスタリングを導入し、その目標はデータを異常型の一貫性のあるクラスタにまとめることである。
これは異常検出とは違い、その目標は異常を通常のデータから分割することである。
パッチベースの事前訓練されたディープ埋め込みとオフザシェルフクラスタリング手法を用いた,単純で効果的なクラスタリングフレームワークを提案する。
論文 参考訳（メタデータ） (2021-12-21T23:11:33Z) - Lattice-Based Methods Surpass Sum-of-Squares in Clustering [98.46302040220395]
クラスタリングは教師なし学習における基本的なプリミティブである。
最近の研究は、低次手法のクラスに対する低い境界を確立している。
意外なことに、この特定のクラスタリングモデルのtextitdoesは、統計的-計算的ギャップを示さない。
論文 参考訳（メタデータ） (2021-12-07T18:50:17Z) - Self-supervised Contrastive Attributed Graph Clustering [110.52694943592974]
我々は,自己教師型コントラストグラフクラスタリング(SCAGC)という,新たな属性グラフクラスタリングネットワークを提案する。
SCAGCでは,不正確なクラスタリングラベルを活用することで,ノード表現学習のための自己教師付きコントラスト損失を設計する。
OOSノードでは、SCAGCはクラスタリングラベルを直接計算できる。
論文 参考訳（メタデータ） (2021-10-15T03:25:28Z) - 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) - Spectral Clustering with Smooth Tiny Clusters [14.483043753721256]
本稿では,データのスムーズさを初めて考慮した新しいクラスタリングアルゴリズムを提案する。
私たちのキーとなるアイデアは、スムーズなグラフを構成する小さなクラスタをクラスタ化することです。
本稿では,マルチスケールな状況に着目するが,データのスムーズさの考え方はどのクラスタリングアルゴリズムにも確実に拡張できる。
論文 参考訳（メタデータ） (2020-09-10T05:21:20Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。