著者

酒井 智弥 井宮 淳

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会論文誌. D, 情報・システム (ISSN:18804535)

巻号頁・発行日

vol.93, no.8, pp.1256-1266, 2010-08-01

---

本論文では,スペクトラルクラスタリングの計算量を削減するランダム算法を提案する.スペクトラルクラスタリングは核関数法と固有値分解を利用して非線形多様体上のデータを分類できるが,類似度行列の作成と固有ベクトル計算のコストが高い.提案する算法はランダム射影とランダムサブサンプリングを利用し,データの次元数とサンプル数に起因する計算コストをそれぞれ低減する.計算時間はサンプル数に準線形,次元数に線形であり,Nystrom近似に基づく既存の高速算法より高速かつ安定である.特に,アピアランスベースの画像解析では少数の画素のランダムサンプリングによって計算時間が次元数に無関係となり得ることを考察する.また,この特長と提案算法を活かした応用として,画像分割と動画像のショット分割を示す.