Data Clustering: A Review

Presentation on theme: "Data Clustering: A Review"— Presentation transcript:

1 Data Clustering: A Review
A.K. Jain, M.N. Murty, P.J. Flynn ～5.10 A Comparison of Technique～ 院生ゼミ ‘04年6月15日（火曜日） 谷津 哲平

2 Techniques 決定論的で確率論的な検索技術のほとんどが“二乗エラー手法”を使用する 階層型ほど多能でない 階層型 分割型
Artifical Neural Network (ANN) Genetic Algorithm(GA) Simulated Annealing(SA) Tabu Search(TS) 　決定論的で確率論的な検索技術のほとんどが“二乗エラー手法”を使用する 階層型ほど多能でない

3 Evolutional approaches
進化的アプローチ 「大域的な探索技術」「一つ以上の解決策で探索する」 他のアプローチ 「局所的な探索技術」「一つの解決策で探索する」 ANN, GA, SA, TS は様々な学習，制御のパラメータの選択に敏感 （難しい） 分野依存の知識 　理論上，明白な 領域情報（domain knowledge）を使用しないので， これらの4つの方法はウィークメソッド[Rich 1983]である 進化的アプローチの特徴 評価関数が不連続であっても最適解を見つけられる

4 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 :　高い次元において良い

5 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 :　最も速い

6 Comparison 3 品質 Presented in Babu et al. [1997]
　stochastic connectionist approach (SCA)を提案 SAと k-means との標準のデータセットに関する性能比較 結果 SCA が SA, k-means より品質（solution quality）が優れている 　進化的アルゴリズムはデータサイズが1000以下で低い次元データのときに良い

7 Comparison 4 大きいデータセット Presented in Mao and Jain [1996]
K-means, ANN, kohonen net　は大きいデータセット， 他のアプローチは小さいデータセットで比較 結果 ANN, GA, TS, SA は学習,制御のパラメータを得ることが難しい 大きいデータセットでは時間がかかる k-means は局所的最適解に収束するが 他の手法を使うことで大きいデータセットにも使える

8 結論 実験に基づく研究で領域情報を併用すると 性能が向上することが明らかになった GA, SA, ANN, TS の領域情報を使うのは役立つ
　実験に基づく研究で領域情報を併用すると 性能が向上することが明らかになった 　GA, SA, ANN, TS の領域情報を使うのは役立つ 　しかし，球型の領域を作る傾向があり制約になる可能性がある 　実際,クラスタベースの文献検索では階層型が分割型より良いことが観測された[Rasmussen 1992]