Kempe Swap K-Means：半教師ありクラスタリングのためのスケーラブルな準最適解

arXiv cs.LG / 2026/3/31

💬 オピニオンIdeas & Deep AnalysisModels & Research

共有:

要点

本論文は、剛なmust-link（同一クラスタ必須）およびcannot-link（異なるクラスタ必須）といった制約をサポートする、セントロイドベースのヒューリスティックであるKempe Swap K-Meansを提案する。
2段階の反復アプローチを用いる：まずKempe鎖（ケンペ・チェーン）によるスワップで割当てを洗練する工程を行い、その後、現在の割当てに基づいて最適なセントロイドを計算するセントロイド更新工程を実施する。
探索の幅を広げ、局所最適解に陥るリスクを低減するために、セントロイド更新フェーズ中に制御された摂動を追加し、よりグローバルな探索を可能にする。
大規模データセットでの実験により、本アルゴリズムは計算効率とスケーラビリティを保ちつつ、準最適な分割を達成することが示されている。
報告された結果では、Kempe Swap K-Meansがクラスタリング精度および実行時間／効率の両面で、既存の最先端ベンチマークを上回ることが示されている。

Abstract

本論文は、剛体のmust-link（ML）制約およびcannot-link（CL）制約のもとでの制約付きクラスタリングに対する、新しいセントロイドベースのヒューリスティックアルゴリズム「Kempe Swap K-Means」を提案する。アルゴリズムは二段階の反復プロセスを用いる。すなわち、制約付き解の探索空間においてKempe鎖のスワップを利用して現在のクラスタリングを洗練する割当てステップと、最適なクラスタセントロイドを計算するセントロイド更新ステップである。大域的探索能力を高め、局所最適に陥ることを避けるために、本フレームワークでは更新フェーズ中に制御された摂動を組み込む。実験的評価により、提案手法が高い計算効率とスケーラビリティを維持しつつ、ほぼ最適な分割を達成することが示される。結果は、Kempe Swap K-Meansが、大規模データセットにおけるクラスタリング精度とアルゴリズム効率の双方において、最先端のベンチマークを一貫して上回ることを示している。