著者

長井 歩

出版者

一般社団法人情報処理学会

雑誌

情報処理学会研究報告アルゴリズム(AL) (ISSN:09196072)

巻号頁・発行日

vol.2007, no.119, pp.73-80, 2007-11-30

---

多種多様なアルゴリズムのひしめくクラスタリング・アルゴリズムの中でも,近年注目されているものにNormalized Cutsがある.Norma』ized Cuts の最大の特徴は,固有値分解を行うなど行列計算を多用する点にある.基本的には,Normalized Cuts は分割クラスタ数を固定した上で,独自の評価基準のもとでクラスタ分割を得るという手法である.クラスタ数を固定するため,クラスタ数を変えることに対する柔軟性には乏しい.また Normalized Cuts は行列計算を行う際に粗行列化することによって計算量をO(n1.5) に減らしてるが,粗行列化できない場合にはO(n2.5) にまで増大してしまう.(nはデータ数である.)本論文で提案する階層型アルゴリズムは Normalized Cuts のこれらの問題点を解消できるいったん実行してしまえば,様々なクラスタ数の解を得ることが容易である.また,計算量は常にO(n2)である.アルゴリズムの基本的な骨格は古典的な階層型手法に似ている.しかし Normalized Cuts の評価基準を用いているために,両者の長所を併せ持つ.すなわち,Normalized Cuts のように任意の形状のクラスタを得られ,かつWard法のように樹形図を得ることができる.The characteristic mark of Normalized Cuts is that it relies on a linear algebraic approach including spectral decomposition. Basically, it obtains a partition by fixing the number K; of clusters. Therefore, it is not so easy to obtain partitions of various k, besides re-calculating. Moreover, when we cannot use sparse matrix, computational complexity jumps up to O(n2.5). We propose an hierarchical algorithm which can resolve these problems. It is easy to obtain partitions of various k after running the program. Its computational complexity is O(n2).