論文の概要: An algorithm for clustering with confidence-based must-link and cannot-link constraints

• arxiv url: http://arxiv.org/abs/2212.14437v3
• Date: Fri, 18 Oct 2024 12:20:54 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-10-21 14:22:20.827919
• Title: An algorithm for clustering with confidence-based must-link and cannot-link constraints
• Title（参考訳）: 信頼度に基づくマスタリンクと不能リンク制約を用いたクラスタリングアルゴリズム
• Authors: Philipp Baumann, Dorit S. Hochbaum,
• Abstract要約: 我々はPCCCアルゴリズム(Pairwise-Confidence-Constraints-Clustering)を導入する。 PCCCアルゴリズムは、オブジェクトのペアに提供された情報を考慮しながら、反復的にオブジェクトをクラスタに割り当てる。 既存のアルゴリズムとは異なり、我々のアルゴリズムは最大6万のオブジェクト、100のクラスタ、数百万のnot-link制約を持つ大規模インスタンスにスケールする。
• 参考スコア（独自算出の注目度）: 0.0
• License:
• Abstract: We study here the 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 (Pairwise-Confidence-Constraints-Clustering) algorithm, which iteratively assigns objects to clusters while accounting for the information provided on the pairs of objects. Our algorithm uses integer programming for the assignment of objects which allows to 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. We developed an enhanced multi-start approach and a model-size reduction technique for the integer program that contributes to the effectiveness and the efficiency of the algorithm. 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 or all soft constraints both in terms of runtime and various metrics of solution quality. The code of the PCCC algorithm is publicly available on GitHub.
• Abstract（参考訳）: ここでは、オブジェクトのペアが同じか異なるクラスタにあるかという情報が得られる半教師付き$k$-clustering問題について研究する。 この情報は確実性を持つか、あるいはある程度の信頼を持って利用できる。 そこで我々は,PCCC (Pairwise-Confidence-Constraints-Clustering) アルゴリズムを導入する。 我々のアルゴリズムは、オブジェクトの割り当てに整数プログラミングを使用し、満足することが保証される厳密な制約や、ペナルティに反する可能性のあるソフトな制約として関係を含ませることができる。 この柔軟性は、全ての対の制約がハードと見なされるか、あるいは全てソフトと見なされるような最先端のアルゴリズムと、我々のアルゴリズムを区別する。 我々は,アルゴリズムの有効性と効率性に寄与する改良されたマルチスタート手法と,整数プログラムのモデルサイズ削減手法を開発した。 既存のアルゴリズムとは異なり、我々のアルゴリズムは最大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)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。