論文の概要: A Graph-Partitioning Based Continuous Optimization Approach to Semi-supervised Clustering Problems

• arxiv url: http://arxiv.org/abs/2503.04447v1
• Date: Thu, 06 Mar 2025 14:02:28 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-03-07 15:57:42.065192
• Title: A Graph-Partitioning Based Continuous Optimization Approach to Semi-supervised Clustering Problems
• Title（参考訳）: グラフ分割に基づく半教師付きクラスタリング問題に対する連続最適化手法
• Authors: Wei Liu, Xin Liu, Michael K. Ng, Zaikun Zhang,
• Abstract要約: 我々は、半教師付きクラスタリングタスクを、与えられたデータセットに関連付けられたグラフ上のパーティショニング問題とみなす。 このモデルを効率的に解くためにブロック座標降下アルゴリズムを提案する。 穏やかな仮定の下で、理論的には必須リンク制約を満たすクラスタを構築することができる。
• 参考スコア（独自算出の注目度）: 24.208152437317768
• License:
• Abstract: Semi-supervised clustering is a basic problem in various applications. Most existing methods require knowledge of the ideal cluster number, which is often difficult to obtain in practice. Besides, satisfying the must-link constraints is another major challenge for these methods. In this work, we view the semi-supervised clustering task as a partitioning problem on a graph associated with the given dataset, where the similarity matrix includes a scaling parameter to reflect the must-link constraints. Utilizing a relaxation technique, we formulate the graph partitioning problem into a continuous optimization model that does not require the exact cluster number, but only an overestimate of it. We then propose a block coordinate descent algorithm to efficiently solve this model, and establish its convergence result. Based on the obtained solution, we can construct the clusters that theoretically meet the must-link constraints under mild assumptions. Furthermore, we verify the effectiveness and efficiency of our proposed method through comprehensive numerical experiments.
• Abstract（参考訳）: 半教師付きクラスタリングは、様々なアプリケーションにおいて基本的な問題である。 既存の方法の多くは理想的なクラスタ番号の知識を必要とするが、実際は入手が難しいことが多い。 さらに、必須リンク制約を満たすことが、これらの方法のもう一つの大きな課題である。 本研究では,半教師付きクラスタリングタスクを与えられたデータセットに関連付けられたグラフ上の分割問題とみなし,類似度行列は必須リンク制約を反映するスケーリングパラメータを含む。 緩和手法を用いることで、グラフ分割問題を、正確なクラスタ数を必要としないが、過大評価のみを必要とする連続最適化モデルに定式化する。 そこで我々は,このモデルを効率的に解き,収束結果を確立するブロック座標降下アルゴリズムを提案する。 得られた解に基づいて、穏やかな仮定の下で理論的に必須リンク制約を満たすクラスタを構築することができる。 さらに,提案手法の有効性と有効性について,包括的数値実験により検証した。

関連論文リスト

• Counterfactual Explanations for k-means and Gaussian Clustering [1.8561812622368767]
  本稿では、妥当性と実現可能性の制約を含むモデルベースのクラスタリングに対する反事実の一般的な定義について述べる。 提案手法は, 現実性, 対象クラスタ, 動作可能な, 不変な特徴を示す2値マスク, クラスタ境界からどの程度の距離を指定すべきかを示す可視性係数を入力として行う。
  論文  参考訳（メタデータ） (2025-01-17T14:56:20Z)
• A Semidefinite Programming-Based Branch-and-Cut Algorithm for Biclustering [0.0]
  本稿では,二クラスタリング問題に対する分枝切断アルゴリズムを提案する。 提案アルゴリズムは汎用的な解法よりも20倍大きな解法を解くことができることを示す。
  論文  参考訳（メタデータ） (2024-03-17T21:43:19Z)
• Revisiting Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model [69.15976031704687]
  IAC (Instance-Adaptive Clustering, インスタンス適応クラスタリング) を提案する。 IACは$ MathcalO(n, textpolylog(n) $の計算複雑性を維持しており、大規模問題に対してスケーラブルで実用的なものである。
  論文  参考訳（メタデータ） (2023-06-18T08:46:06Z)
• One-step Bipartite Graph Cut: A Normalized Formulation and Its Application to Scalable Subspace Clustering [56.81492360414741]
  両部グラフの1ステップ正規化カットを、特に線形時間複雑性で実施する方法を示す。 本稿では、まず、正規化制約付き一段階二分グラフカット基準を特徴付けるとともに、そのトレース問題に対する等価性を理論的に証明する。 このカット基準を、適応アンカー学習、二部グラフ学習、一段階正規化二部グラフ分割を同時にモデル化するスケーラブルなサブスペースクラスタリングアプローチに拡張する。
  論文  参考訳（メタデータ） (2023-05-12T11:27:20Z)
• Unified Multi-View Orthonormal Non-Negative Graph Based Clustering Framework [74.25493157757943]
  我々は,非負の特徴特性を活用し,多視点情報を統合された共同学習フレームワークに組み込む,新しいクラスタリングモデルを定式化する。 また、深層機能に基づいたクラスタリングデータに対するマルチモデル非負グラフベースのアプローチを初めて検討する。
  論文  参考訳（メタデータ） (2022-11-03T08:18:27Z)
• Late Fusion Multi-view Clustering via Global and Local Alignment Maximization [61.89218392703043]
  マルチビュークラスタリング(MVC)は、異なるビューからの補完情報を最適に統合し、クラスタリング性能を改善する。 既存のアプローチの多くは、クラスタリングに最適な類似性行列を学ぶために、複数の事前定義された類似性を直接融合する。 これらの問題に対処するために、アライメントを通してレイトフュージョンMVCを提案する。
  論文  参考訳（メタデータ） (2022-08-02T01:49:31Z)
• Lattice-Based Methods Surpass Sum-of-Squares in Clustering [98.46302040220395]
  クラスタリングは教師なし学習における基本的なプリミティブである。 最近の研究は、低次手法のクラスに対する低い境界を確立している。 意外なことに、この特定のクラスタリングモデルのtextitdoesは、統計的-計算的ギャップを示さない。
  論文  参考訳（メタデータ） (2021-12-07T18:50:17Z)
• An Exact Algorithm for Semi-supervised Minimum Sum-of-Squares Clustering [0.5801044612920815]
  半教師付きMSSCのための分岐結合アルゴリズムを提案する。 背景知識はペアワイズ・マスタリンクと結びつかない制約として組み込まれている。 提案したグローバル最適化アルゴリズムは,実世界のインスタンスを最大800個のデータポイントまで効率的に解決する。
  論文  参考訳（メタデータ） (2021-11-30T17:08:53Z)
• Clustering to the Fewest Clusters Under Intra-Cluster Dissimilarity Constraints [0.0]
  均等なクラスタリングは、密度も期待されるクラスの数にも依存せず、相似性の閾値にも依存します。 このクラスタリング問題に対する様々な実践的ソリューション間のトレードオフを特定するために,適切なクラスタリングアルゴリズムをレビューし,評価する。
  論文  参考訳（メタデータ） (2021-09-28T12:02:18Z)
• Mixed Membership Graph Clustering via Systematic Edge Query [22.77704627076251]
  この研究は、ほとんど不完全なグラフのクラスタリングノードを考慮する。 問題設定の下では、エッジに関する少数のクエリしか作成できないが、グラフ全体はオブザーバブルではない。 この問題は,限定アノテーションを用いた大規模データクラスタリング,限定された調査リソースによるコミュニティ検出,グラフトポロジ推論などに適用できる。
  論文  参考訳（メタデータ） (2020-11-25T19:19:05Z)
• Scalable Hierarchical Agglomerative Clustering [65.66407726145619]
  既存のスケーラブルな階層的クラスタリング手法は、スピードの質を犠牲にする。 我々は、品質を犠牲にせず、数十億のデータポイントまでスケールする、スケーラブルで集約的な階層的クラスタリング法を提案する。
  論文  参考訳（メタデータ） (2020-10-22T15:58:35Z)

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

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