Data Clustering:A Review 5.2 Partitional Algorithms （分割手法） 5.2.1 Squared Error Algorithm （二乗エラー手法）紺野憲一 5.2 分割手法分割手法は樹形図の代わりにデータの塊を得る。 y C ・樹形図の作成コストが大きい巨大なデータに対して有効 D ・希望の出力クラスタの数の選択問題を伴う A B ｘ 5.2.1 二乗エラー手法分割手法の中でも直感的にわかりやすく使いやすい。分離がはっきりしているクラスタに対しうまくいく傾向がある。 Kクラスターを含むパターンセット  に分割されるクラスタリング  の二乗エラーは K nj e (  , ）＝  X 2 j1 i 1 ( j) i  cj X i( j ) は j 番目のクラスに含まれるi 番目のパターン c j は j 番目のクラスのセントロイド（中心） 2 k-means手法最も単純な二乗エラーを用いる手法最初にランダムに代表点を設定しクラスタとする、それとパターンの類似度でクラスタにパターンを収束条件を満たすまで併合していく手法。パターン数が n の場合計算量は O (n) ※初期条件が正しく選ばれないと正しい結果にならない初期条件問題 y y C D B B A C D A F E F E ｘ初期クラスタを｛A｝、｛C｝、｛F｝とした場合クラスタリングは成功する。ｘ初期クラスタを｛A｝、｛B｝、｛F｝とした場合クラスタリングは成功しない。二乗エラークラスタリング手法（１）初期のクラスタを選択（２）クラスタの重心とに最も近いパターンをそのクラスタに併合し新しいクラスタのセントロイドを計算する。これを繰り返す。（３）ステップ2を繰り返した物に対し、独自の手法を用いて分離、結合を行う。 y E D y D F B E C A C ｘ F B A E D F B A y C ｘｘｋ－meansクラスタリング手法（１）ランダム、もしくはハイパーボリュームからランダムに適当なクラスタk 個選びそれ自信をクラスタのセントロイドと考える。（２）各パターンを最もクラスタのセントロイドと近いクラスタへと併合する。（３）併合したクラスタのメンバを用いてクラスタのセントロイドを再計算する。（４）収束基準に当てはまらない場合は（２）に戻る。典型的な収束基準・パターンが別のクラスタに移動しない。・二乗エラーの最小値が減少しない。 y E B セントロイド A セントロイド F C D ｘｋ－meansクラスタリング手法（１）ランダム、もしくはハイパーボリュームからランダムに適当なクラスタk を選びそのクラスタのセントロイドをkとして考える。（２）各パターンを最もクラスタのセントロイドと近いクラスタへと併合する。（３）併合したクラスタのメンバを用いてクラスタのセントロイドを再計算する。（４）収束基準に当てはまらない場合は（２）に戻る。典型的な収束基準・パターンが別のクラスタに移動しない。 y E ・二乗エラーの最小値が減少しない。 B A F C D ｘｋ－means改良手法 k-meansのヴァリエーションとして様々な手法が考案されている。・初期の分割を適正にするための手法・全く別の手法を導入する・クラスタの分割と併合を可能にする手法閾値を設定しクラスタの分散がその値より大きい場合分割する。また２クラスタ間のセントロイド距離がが閾値よりも小さい場合併合する。 ISO-DATAアルゴリズム y y B C D B A C D A F E F ｘクラスタの併合、分割が可能。 E ｘ