重み付きデータのNormalized Cuts

長井 歩  

誌名
電子情報通信学会論文誌 D   Vol.J90-D   No.9   pp.2483-2494
発行日: 2007/09/01
Online ISSN: 1881-0225
DOI: 
Print ISSN: 1880-4535
論文種別: 論文
専門分野: データマイニング
キーワード: 
クラスタリング,  Normalized Cuts,  固有値分解,  画像の領域分割,  

本文: PDF(1.1MB)>>
論文を購入




あらまし: 
クラスタリングの一手法にspectral clusteringと呼ばれる手法がある.この手法は,固有値分解を行うなど線形代数的アプローチを採用している点が特徴的である.spectral clusteringの代表的な手法にNormalized Cutsがある.従来のNormalized Cutsは,重み付きデータを直接は扱えない.「重み」とはデータの重複度のことであり,直感的には同じデータを複数含む場合の出現回数のことである.従来のNormalized Cutsは,すべてのデータの重みが同じであることが前提となる.そこで我々はNormalized Cutsの枠組みの中で重み付きデータを扱える方法を提案する.それは重みの分だけ複製したデータを入力として,従来のNormalized Cutsを適用した場合と同一の結果が得られることを保証できる.しかも,計算量を大幅に減らすことができる.重み付きデータのデータ数を nd,重みの分だけ複製して得られる総データ数を n とすると,固有値分解の計算量は (nd/n)1.5 に抑えられる.提案法の従来法に対する修正は,二つのデータ間の類似度関数の定義を変更するだけという,わずかな修正で実現可能であることも示す.提案法を用いた実験として,2種類の実験結果を示す.従来のNormalized Cutsでこれらの実験を行うには限界があるが,提案法の導入により,扱える問題のサイズを広げることができる.