クラスタリングにおけるスペクトル法の平均時の性能解析
スポンサーリンク
概要
- 論文の詳細を見る
グラフクラスタリングはテキストマイニングや画像認識など様々な分野で応用されている.この問題に対するアルゴリズムの性能を評価する指標として,最小コンダクタンス分割問題に対する近似比が重要である事がRavi Kannan等によって示された.本稿では,隣接行列の固有ベクトルを用いて,クラスタリングを行うスペクトル法を対象とし,最小コンダクタンス分割問題に対する平均時の性能を,クラスターを持つ様なランダムグラフG_<n,p,q>を用いて解析した.その結果,平均時には高い性能を持つという事がわかった.
- 社団法人電子情報通信学会の論文
- 2008-09-04