Data Clustering: A Review A.K. Jain, M.N. Murty, P.J. Flynn ～5.10 A Comparison of Technique～ 院生ゼミ ‘04年6月15日（火曜日） 谷津 哲平
Techniques 決定論的で確率論的な検索技術のほとんどが“二乗エラー手法”を使用する 階層型ほど多能でない 階層型 分割型 Artifical Neural Network (ANN) Genetic Algorithm(GA) Simulated Annealing(SA) Tabu Search(TS) 決定論的で確率論的な検索技術のほとんどが“二乗エラー手法”を使用する 階層型ほど多能でない
Evolutional approaches 進化的アプローチ 「大域的な探索技術」「一つ以上の解決策で探索する」 他のアプローチ 「局所的な探索技術」「一つの解決策で探索する」 ANN, GA, SA, TS は様々な学習，制御のパラメータの選択に敏感 （難しい） 分野依存の知識 理論上，明白な 領域情報（domain knowledge）を使用しないので， これらの4つの方法はウィークメソッド[Rich 1983]である 進化的アプローチの特徴 評価関数が不連続であっても最適解を見つけられる
Comparison 1 パフォーマンス Presented in Mishra and Raghavan [1994] Randomized branch-and-bound (RBA) を提案 SA, GA, TS, Hybrid Search (HS) 1989 との性能比較 ※ データセット200未満 結果 GA : 1次元データにおいて良い SA : 遅いので魅力的でない TS : 最も性能が良い RBA : HS : 高い次元において良い
Comparison 2 計算速度 Presented in Al-Sultan and Khan [1996] k-means, SA, TS, GA での実験 ※ データセット200未満 結果 GA, SA, TS は品質が同等で，k-means より良いが，実行時間は k-means が最も効率的 GA : 速い SA : 遅い（TSより時間がかかる） TS : 中 k-means : 最も速い
Comparison 3 品質 Presented in Babu et al. [1997] stochastic connectionist approach (SCA)を提案 SAと k-means との標準のデータセットに関する性能比較 結果 SCA が SA, k-means より品質（solution quality）が優れている 進化的アルゴリズムはデータサイズが1000以下で低い次元データのときに良い
Comparison 4 大きいデータセット Presented in Mao and Jain [1996] K-means, ANN, kohonen net は大きいデータセット， 他のアプローチは小さいデータセットで比較 結果 ANN, GA, TS, SA は学習,制御のパラメータを得ることが難しい 大きいデータセットでは時間がかかる k-means は局所的最適解に収束するが 他の手法を使うことで大きいデータセットにも使える
結論 実験に基づく研究で領域情報を併用すると 性能が向上することが明らかになった GA, SA, ANN, TS の領域情報を使うのは役立つ 実験に基づく研究で領域情報を併用すると 性能が向上することが明らかになった GA, SA, ANN, TS の領域情報を使うのは役立つ しかし，球型の領域を作る傾向があり制約になる可能性がある 実際,クラスタベースの文献検索では階層型が分割型より良いことが観測された[Rasmussen 1992]