計算機実験

ヒープを用いた階層的クラスタリングアルゴリズムの有効性を確かめるために、簡単 な計算機実験を行った。

対象間の距離を乱数を用いて発生し、その距離に基づいて、階層的なクラスタリング を行った。統合のための評価には、平均距離を用いた。

比較実験として、単純に、各階層で評価値最小のクラスター対を探す方法と、各クラ スターに対して最小の評価値を持つクラスターをあらかじめ記憶しておくことによっ て高速化した手法に対して実行時間を測定した。各クラスターに対して最小の評価値 を持つクラスターを記憶することによって、最小の評価値をもつクラスター対の探索 の手間は、$O(N)$ となるが、クラスター対の統合によって各クラスターに対して最 小の評価値を持つクラスターが変る場合には、評価値最小のクラスターを見つけるた めに、さらに、$O(N)$の手間が必要となり、結局、この方法でも、最悪の場合には、 $O(N^3)$ の手間が必要である。

表3.1にデータ数と計算時間の関係を示す。表3.1の (a)は本稿で提案したアルゴリズムを用いた場合の計算時間であり、(b)は各階層で単 純に最小の評価値を持つクラスター対を探索する場合の計算時間であり、(c)は各ク ラスターに対して最小の評価値を持つクラスターを記憶しておく方法を用いた場合の 計算時間である。ヒープを用いることにより、かなり高速化されていることが分かる。

表 3.1: データ数と計算時間の関係

	100	200	300	400	500	600	700	800	900	1000
(a)	0.0	0.2	0.5	1.0	1.7	2.3	3.2	4.2	5.2	6.5
(b)	1.1	8.0	27.2	64.4	125.7	216.8	*	*	*	*
(c)	0.3	1.1	2.7	4.9	7.8	11.3	15.5	20.6	26.4	32.1