論文の概要: Kempe Swap K-Means: A Scalable Near-Optimal Solution for Semi-Supervised Clustering

• arxiv url: http://arxiv.org/abs/2603.27417v1
• Date: Sat, 28 Mar 2026 21:33:06 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-03-31 23:18:44.948937
• Title: Kempe Swap K-Means: A Scalable Near-Optimal Solution for Semi-Supervised Clustering
• Title（参考訳）: Kempe Swap K-Means: 半スーパービジョンクラスタリングのためのスケーラブルなニア最適ソリューション
• Authors: Yuxuan Ren, Shijie Deng,
• Abstract要約: 本稿では,厳密なマスタリンク制約下での制約クラスタリングのために,Kempe Swap K-Meansと呼ばれるセントロイドに基づく新しいアルゴリズムを提案する。 このアルゴリズムは、大規模データセットのクラスタリング精度とアルゴリズム効率の両方において、最先端ベンチマークを一貫して上回る。
• 参考スコア（独自算出の注目度）: 5.478764356647438
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper presents a novel centroid-based heuristic algorithm, termed Kempe Swap K-Means, for constrained clustering under rigid must-link (ML) and cannot-link (CL) constraints. The algorithm employs a dual-phase iterative process: an assignment step that utilizes Kempe chain swaps to refine current clustering in the constrained solution space and a centroid update step that computes optimal cluster centroids. To enhance global search capabilities and avoid local optima, the framework incorporates controlled perturbations during the update phase. Empirical evaluations demonstrate that the proposed method achieves near-optimal partitions while maintaining high computational efficiency and scalability. The results indicate that Kempe Swap K-Means consistently outperforms state-of-the-art benchmarks in both clustering accuracy and algorithmic efficiency for large-scale datasets.
• Abstract（参考訳）: 本稿では,厳密なm must-link(ML)およびnot-link(CL)制約下での制約クラスタリングのための,Kempe Swap K-Meansと呼ばれる,セントロイドに基づく新しいヒューリスティックアルゴリズムを提案する。 このアルゴリズムは二相反復プロセスを用いており、ケンプ連鎖スワップを用いて制約された解空間における電流クラスタリングを洗練させる割り当てステップと、最適なクラスタセントロイドを計算するセントロイド更新ステップである。 グローバルな検索機能を強化し、ローカルな最適化を避けるため、このフレームワークは更新フェーズ中に制御された摂動を組み込む。 実験により,提案手法は高い計算効率とスケーラビリティを維持しつつ,ほぼ最適分割を実現することを示す。 その結果、Kempe Swap K-Meansは大規模データセットのクラスタリング精度とアルゴリズム効率の両方において、最先端のベンチマークを一貫して上回っていることが示唆された。

関連論文リスト

• Approximation Algorithm for Constrained $k$-Center Clustering: A Local Search Approach [10.257446766550862]
  本稿では,制約付きk中心クラスタリング問題について検討し,インスタンスレベルのNot-link (CL) と must-link (ML) の制約を背景知識として組み込む。 2 の近似比を最適に達成し,支配的集合問題への変換に基づく新しい局所探索フレームワークを提案する。
  論文  参考訳（メタデータ） (2026-01-17T02:39:41Z)
• CAS Condensed and Accelerated Silhouette: An Efficient Method for Determining the Optimal K in K-Means Clustering [0.0]
  本稿では,クラスタリングにおけるkの最適値を選択するための戦略を提案する。 複雑なデータ環境におけるクラスタリング精度と計算効率のバランスを達成することに焦点を当てている。 提案手法は,高次元データセット上での実行時間を最大99%高速化する。
  論文  参考訳（メタデータ） (2025-07-11T05:03:16Z)
• Accelerating Spectral Clustering under Fairness Constraints [56.865810822418744]
  本研究では,Fair SC問題を凸関数(DC)フレームワークの差内にキャストすることで,フェアスペクトルクラスタリング(Fair SC)のための新しい効率的な手法を提案する。 本研究では,各サブプロブレムを効率よく解き,計算効率が先行処理よりも高いことを示す。
  論文  参考訳（メタデータ） (2025-06-09T18:46:27Z)
• K*-Means: A Parameter-free Clustering Algorithm [55.20132267309382]
  k*-meansは、kや他のパラメータをセットする必要がない新しいクラスタリングアルゴリズムである。 最小記述長の原理を用いて、クラスタの分割とマージによって最適なクラスタ数k*を自動的に決定する。 k*-平均が収束することが保証されることを証明し、kが未知のシナリオにおいて既存のメソッドよりも著しく優れていることを実験的に証明する。
  論文  参考訳（メタデータ） (2025-05-17T08:41:07Z)
• Nearest Neighbour Equilibrium Clustering [6.635604919499181]
  新しく直感的に近づいた近傍のクラスタリングアルゴリズムでは、クラスタはそのサイズと凝集性のバランスをとる平衡条件によって定義される。 平衡条件の定式化は、各点のクラスタへのアライメントの強さの定量化を可能にし、これらのクラスタアライメントの強度は、提案されたアプローチを完全に自動化可能なモデル選択基準に自然に導かれる。
  論文  参考訳（メタデータ） (2025-03-27T12:16:54Z)
• Self-Supervised Graph Embedding Clustering [70.36328717683297]
  K-means 1-step dimensionality reduction clustering method は,クラスタリングタスクにおける次元性の呪いに対処する上で,いくつかの進歩をもたらした。 本稿では,K-meansに多様体学習を統合する統一フレームワークを提案する。
  論文  参考訳（メタデータ） (2024-09-24T08:59:51Z)
• Fuzzy K-Means Clustering without Cluster Centroids [21.256564324236333]
  ファジィK平均クラスタリングは教師なしデータ分析において重要な手法である。 本稿では,クラスタセントロイドへの依存を完全に排除する,ファジィテクストK-Meansクラスタリングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-04-07T12:25:03Z)
• Gradient Based Clustering [72.15857783681658]
  本稿では,クラスタリングの品質を計測するコスト関数の勾配を用いて,距離に基づくクラスタリングの一般的な手法を提案する。 アプローチは反復的な2段階の手順(クラスタ割り当てとクラスタセンターのアップデートの代替)であり、幅広い機能に適用できる。
  論文  参考訳（メタデータ） (2022-02-01T19:31:15Z)

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

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