一段階の二重グラフカット: 標準化された構文とスケーラブルなサブスペースクラスタリングへの適用

科学分野:

• 機械学習
• グラフ理論
• データマイニング

背景:

• ビパルタイトグラフは,サブスペースとスペクトルクラスタリングで大きなデータセットに有効です.
• 制約されたラプラシアンランク (CLR) のような既存の方法は,コンポーネント分布を無視しているため,不均衡なクラスタを生成することができます.
• 標準化されたカット (Ncut) は一般的なグラフでは成功しますが,線形的な複雑性を持つ二重グラフでは1段階の標準化されたカットが欠けています.

研究 の 目的:

• 標準化された制約を持つ新しい一段階バイパートイトグラフカット (OBCut) 基準を開発する.
• バランスのとれた,明確に定義されたクラスターを達成するための既存の方法の限界に対処する.
• 線形時間複雑性を持つスケーラブルなサブスペースクラスタリングアプローチを提案する.

主な方法:

• ノーマライズされた制約を持つ新しい一段階バイパートイトグラフカット (OBCut) 基準を特徴づけた.
• 理論的には OBCut が トレース最大化問題と等しいことを証明した.
• 拡張可能なサブスペースクラスタリングアプローチを開発し,アダプティブアンカーラーニング,バイパートイトグラフラーニング,および1段階の標準化されたバイパートイトグラフパーティションを統一されたオブジェクト関数に統合しました.
• 線形時間計算のための代替最適化アルゴリズムを設計した.

主要な成果:

• 提案されたOBCut基準は,バイパートイトグラフの接続されたコンポーネントを効果的に制限します.
• 統一されたオブジェクト関数と交替最適化アルゴリズムは,同時適応アンカー学習,二重グラフ学習,および正常化されたパーティショニングを実現します.
• 様々なデータセットでの実験結果は,提案されたアプローチの有効性とスケーラビリティを証明しています.
• この方法は線形時間の複雑性を達成します.

結論:

• 新しい OBCut 基準は,クラスタリングにおける標準化された二重グラフ分割のための堅牢な解決策を提供します.
• 統合されたサブスペースクラスタリングアプローチは,大規模データセットに有効でスケーラブルな方法を提供します.
• 線形時間の複雑さにより,このアプローチは現実世界のアプリケーションに適しています.