クラスタリングについて。。。 references: - 言語処理のための機械学習入門 クラスタリング: 似たデータ(単語)を同じグループにまとめること。 できあがったグループをクラスタと呼ぶ。 データD = {d1, d2, d3,...d|D|} 各事例 = x1, x2, x3, ... x|D| 学習: データDが与えられ、そこからモデルや処理手段を導くこと (Learning, Training) 学習データ:学習に用いるデータ クラスタリングはどういうカテゴリに分かれていくかを知らない。分類とは異なる。 語義推定(Word Sense Induction)によく使われる 凝集型クラスタリング(agglomerative clustering) 最も似ているモノ同士をくっつける ボトムアップクラスタリング 樹形図で表記(dendrogram)される。 アルゴリズム: 1. 各データを単一クラスタ(C={C1, C2, C3, ... C|D|})とする 2. 最類似クラスタペアmax sim(Ci, Cj)を選択する。 3. 新規クラスタCnew(Ci, Cj)とし、Ci, Cjは削除する。 4. kクラスタ数になるまで(2) - (3)を行う 上記の(2)の項目において、最類似を求めるに当たって二つそれないし一つのクラスタが複数ベクトルということもありえる。 その際においての計算方法として、例として以下の３つがある。 1. 単連結法 (single-link method) / aka 最短距離法 (nearest neighbor method) 2. 完全連結法 (complete-link method) / aka 最長距離法 (furthest neighbor method) 3. 重心法 (centroid method) どれがいいかは一長一短により問題による 凝集法の利点/欠点 利点: - 様々な形状のデータをクラスタリングできる. - データの入力順序に依存しない. - 実数値データ, 整数値データ, カテゴリデータなど, 異なる属性を同時に扱える. - 近傍データが同じクラスタに含まれる可能性が高い. - クラスタ数を決める必要がないため任意の数のクラスタを得ることができる. 欠点: - 孤立したデータである外れ値やノイズが含まれるデータを扱えない. - 最適なクラスタ数を自動的に決定できない. - データ数NについてN 2 〜N 3 に比例する計算量がかかる. - いったん統合したクラスタを後で分割できない. k-平均法(k-means) 適当に分けて、それからうまく分かれるように分けていく手法 アルゴリズム 1. データ群からk個データを選択し（セントロイド）, クラスタの中心(代表クラスタ)とする. 2. 全要素において、それぞれの代表クラスタとの距離(類似度)を計算し、最短クラスタに属させる. 3. クラスタの中心を計算し代表クラスタを再度求める 4. 全要素とk個の中心との距離を計算し, 最も距離の近い中心を含むクラスタに属させる. 5. クラスタ中心の位置がほぼ定まり, 収束判定条件を満たすまで（3）, （4）を繰り返す. 初期値により結果が変わる。 k-means法の利点 - データの入力順序に依存しない. - 次元数, データ数に対するスケーラビリティがある. - 特定のクラスタ数における各クラスタサイズを最小化する. - クラスタの境界が明確に決定する. k-means法の欠点 - 多様なクラスタ形状を扱えない. - 実数値データ, 整数値データ, カテゴリデータなど, 異なる属性を同時に扱えない. - 最適なクラスタ数の発見やクラスタ境界が非線形な問題の扱いが困難である. - 初期値に依存するため, 異なる初期設定により異なる結果となりうる. |
|
|