論文の概要: PCCC: The Pairwise-Confidence-Constraints-Clustering Algorithm
- arxiv url: http://arxiv.org/abs/2212.14437v1
- Date: Thu, 29 Dec 2022 19:21:33 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-02 17:06:02.953799
- Title: PCCC: The Pairwise-Confidence-Constraints-Clustering Algorithm
- Title（参考訳）: PCCC: Pairwise-Confidence-Constraints-Clusteringアルゴリズム
- Authors: Philipp Baumann and Dorit S. Hochbaum
- Abstract要約: そこで我々は,PCCCアルゴリズムを導入し,オブジェクトのペアに提供される情報を考慮しながら,反復的にオブジェクトをクラスタに割り当てる。
我々のアルゴリズムは、満足することが保証される厳格な制約や、違反される可能性のあるソフトな制約として関係を組み込むことができる。
既存のアルゴリズムとは異なり、我々のアルゴリズムは最大6万のオブジェクト、100のクラスタ、数百万のnot-link制約を持つ大規模インスタンスにスケールする。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We consider a semi-supervised $k$-clustering problem where information is
available on whether pairs of objects are in the same or in different clusters.
This information is either available with certainty or with a limited level of
confidence. We introduce the PCCC algorithm, which iteratively assigns objects
to clusters while accounting for the information provided on the pairs of
objects. Our algorithm can include relationships as hard constraints that are
guaranteed to be satisfied or as soft constraints that can be violated subject
to a penalty. This flexibility distinguishes our algorithm from the
state-of-the-art in which all pairwise constraints are either considered hard,
or all are considered soft. Unlike existing algorithms, our algorithm scales to
large-scale instances with up to 60,000 objects, 100 clusters, and millions of
cannot-link constraints (which are the most challenging constraints to
incorporate). We compare the PCCC algorithm with state-of-the-art approaches in
an extensive computational study. Even though the PCCC algorithm is more
general than the state-of-the-art approaches in its applicability, it
outperforms the state-of-the-art approaches on instances with all hard
constraints or all soft constraints both in terms of running time and various
metrics of solution quality. The source code of the PCCC algorithm is publicly
available on GitHub.
- Abstract（参考訳）: 我々は、オブジェクトのペアが同じか異なるクラスタにあるかという情報が得られる半教師付き$k$-clustering問題を考える。
この情報は確実性を持つか、あるいはある程度の信頼を持って利用できる。
提案手法は,オブジェクト対に提供された情報を考慮しつつ,反復的にオブジェクトをクラスタに割り当てるpcccアルゴリズムを導入する。
我々のアルゴリズムは、満足することが保証される厳格な制約や、ペナルティに違反する可能性のあるソフトな制約として関係を組み込むことができる。
この柔軟性は、すべてのペアワイズ制約がハードと見なされるか、あるいはすべてソフトと見なされる状態とアルゴリズムを区別します。
既存のアルゴリズムとは異なり、アルゴリズムは最大6万のオブジェクト、100のクラスタ、数百万のnot-link制約(組み込むのが最も難しい制約)を持つ大規模インスタンスにスケールする。
我々は,PCCCアルゴリズムと最先端の手法との比較を行った。
PCCCアルゴリズムはその適用性における最先端のアプローチよりも一般的なものであるが、実行時間とソリューション品質の様々な指標の両方において、すべての厳しい制約または全てのソフトな制約を持つインスタンスに対して最先端のアプローチより優れている。
PCCCアルゴリズムのソースコードはGitHubで公開されている。
関連論文リスト
- Near-Optimal Algorithms for Constrained k-Center Clustering with Instance-level Background Knowledge [12.808663917871888]
我々は、広く採用されている$k$-centerクラスタリングに基づいて、その入力背景知識を must-link (ML) および cannot-link (CL) 制約セットとしてモデル化する。
制約付き$k$-centerの最初の効率的な近似アルゴリズムに到達します。
論文 参考訳（メタデータ） (2024-01-23T07:16:32Z) - 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) - Consistent Multiclass Algorithms for Complex Metrics and Constraints [38.6998359999636]
この設定には、マルチクラスG平均やマイクロF1測定など、多くの一般的なパフォーマンス指標が含まれている。
このような複雑な設計目標のための一貫したアルゴリズムのための一般的なフレームワークを提供する。
様々なクラス分類タスクと公正制約のある問題の実験により、我々のアルゴリズムは最先端のベースラインと良好に比較できることを示した。
論文 参考訳（メタデータ） (2022-10-18T09:09:29Z) - An Exact Algorithm for Semi-supervised Minimum Sum-of-Squares Clustering [0.5801044612920815]
半教師付きMSSCのための分岐結合アルゴリズムを提案する。
背景知識はペアワイズ・マスタリンクと結びつかない制約として組み込まれている。
提案したグローバル最適化アルゴリズムは,実世界のインスタンスを最大800個のデータポイントまで効率的に解決する。
論文 参考訳（メタデータ） (2021-11-30T17:08:53Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-07T08:00:02Z) - A black-box adversarial attack for poisoning clustering [78.19784577498031]
本稿では,クラスタリングアルゴリズムのロバスト性をテストするために,ブラックボックス対逆攻撃法を提案する。
我々の攻撃は、SVM、ランダムフォレスト、ニューラルネットワークなどの教師付きアルゴリズムに対しても転送可能であることを示す。
論文 参考訳（メタデータ） (2020-09-09T18:19:31Z) - Differentially Private Clustering: Tight Approximation Ratios [57.89473217052714]
基本的なクラスタリング問題に対して,効率的な微分プライベートアルゴリズムを提案する。
この結果から,SampleとAggregateのプライバシーフレームワークのアルゴリズムの改善が示唆された。
1-Clusterアルゴリズムで使用されるツールの1つは、ClosestPairのより高速な量子アルゴリズムを適度な次元で得るために利用できる。
論文 参考訳（メタデータ） (2020-08-18T16:22:06Z) - An Integer Linear Programming Framework for Mining Constraints from Data [81.60135973848125]
データから制約をマイニングするための一般的なフレームワークを提案する。
特に、構造化された出力予測の推論を整数線形プログラミング(ILP)問題とみなす。
提案手法は,9×9のスドクパズルの解法を学習し,基礎となるルールを提供することなく,例からツリー問題を最小限に分散させることが可能であることを示す。
論文 参考訳（メタデータ） (2020-06-18T20:09:53Z) - Beyond Worst-Case Analysis in Stochastic Approximation: Moment
Estimation Improves Instance Complexity [58.70807593332932]
近似問題に対する勾配に基づく手法のオラクル複雑性について検討する。
最悪のケースの複雑さではなく、インスタンス依存の複雑さに焦点を当てます。
提案アルゴリズムとその解析はモーメント推定の成功を理論的に正当化する。
論文 参考訳（メタデータ） (2020-06-08T09:25:47Z) - A semi-supervised sparse K-Means algorithm [3.04585143845864]
クラスタリングに必要な機能のサブグループを検出するために、教師なしスパースクラスタリング手法を用いることができる。
半教師付き手法では、ラベル付きデータを使用して制約を作成し、クラスタリングソリューションを強化することができる。
提案アルゴリズムは,他の半教師付きアルゴリズムの高性能性を保ち,また,情報的特徴から情報的特徴を識別する能力も保持していることを示す。
論文 参考訳（メタデータ） (2020-03-16T02:05:23Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。