クラスタリング手法のクラスタリング

  • 31
    いいね
  • 2
    コメント

はじめに

クラスタリングについて調べてみると,割りと無責任に scikit-learn がーとか機械学習がーとか語っているページがとても多かったので,

  • なぜ,クラスタリングを行うのかとその注意点
  • クラスタリングにはどのような分類があるのか
  • それぞれの手法の長所と短所,なぜその手法を使うのか
  • 具体的なライブラリの選択

という観点からまとめてみました.

プログラマかつ数学弱者なので,深く込み入った数学的な沼については語ることが出来ません.

また,具体的なライブラリとして,Python の Scipy や scikit-learn を用います.

基本的に引用が多い記事なので,下記の参考ページを一読していただきたいです.また,引用元の著者さんで,引用を外していただきたい場合はご連絡ください.すぐに対応します.

クラスタリングを行う理由と注意点

クラスタリングとは

そもそも機械学習の手法は大きく分けて,教師ありと教師なしに分けられる.

  • 教師あり学習:人間が与えた正解を元に,観測データから予測する規則を生成.(例:おそ松さんの判定とか.先にそれぞれの正解を学ばせている.)
  • 教師なし学習:観測データだけを対象に分析を行う.(例:大量のデータを入れて,分類させるなど.)

クラスタリング (clustering) は,クラスター分析( cluster analysis) やデータ・クラスタリング (data clustering) とも呼ばれ,代表的な教師なし学習手法である.

データの集合をクラスタという部分集合に分けることであり,内的結合 (internal cohesion) と外的分離 (external isolation) の性質を持つ.

上図は,参考ページ [3] クラスタリングに関する講演・講義資料 におけるスライド 3 より引用. (2017/7/7 閲覧)

そもそも,教師なし学習の手法であるため,分類の基準が決まっておらず,分類のための外敵基準や評価が与えられていない場合に行う.つまり,分類してみてから,どうしてそのように分類されたかを分析する必要がある.そのため,これが最適と呼べるようなクラスター分析が存在するわけではないということを留意しなければならない.

クラスタリングの注意点

神蔦先生より,

最も重要な点は,クラスタリングは探索的 (exploratory) なデータ解析手法であって,分割は必ず何らかの主観や視点に基づいているということです.よって,クラスタリングした結果は,データの要約などの知見を得るために用い,客観的な証拠として用いてはなりません.

また,

クラスタリングの結果は,その利用目的などに応じて,妥当性を常に検証する必要があります.
得られたクラスタは絶対的・客観的なものではなく,あくまで一つのある視点から見た結果であることに留意.

に全て集約されている.

クラスタリングの結果,グループ分けされた結果を解釈して,他者でも納得できるような意味を与えることが,クラスタリングの価値を大きく左右する重要なプロセスであるとも言える.

また,クラスタリングはあくまで分類のみであるため,分類された対象ごとに相関分析や回帰分析を行うことで,成立している法則性・相関関係・因果関係を考察しなければならない.

クラスタリングの分類

クラスタリング手法をネストして分類すると,

  • 階層的 (hierarchical)
    • 凝集型 (agglomerative)
      • 単リンク法 (single linkage method) 別名:最短距離法
      • 完全リンク法 (complete linkage method) 別名:最長距離法
      • 群平均法 (group average method)
      • Ward 法 (Ward's method) 別名:最小分散法
      • セントロイド法 (centroid method) 別名:重心法
      • 重み付き平均法 (weighted average method)
      • メジアン法 (median method)
    • 分割型 (divisible)
      • データ集合全体が一つのクラスタの状態から,順次クラスタを分割して,クラスタの階層を生成する.
  • 非階層的 (non-hierarchical) 別名:分割最適化 (partitional optimization)
    • K-means 法 別名:K 平均法
      • 派生的手法:K-means++
    • その他沢山

に分けられる.

階層的手法は最も距離 (類似度) が近くて似ている組み合わせからまとめていくという方法である.最終的にはツリー状のデンドログラムを書くことができる.この距離 (metric) についても様々な定義が存在する.(後述する) また,クラスタ間における距離の定義も複数存在し,上で挙げた7つの手法に分類される.

非階層的手法は逆にいくつのクラスターに分けるかあらかじめ決め,決めたクラスター数になるようにまとめていく手法である.代表的な手法として,K-means 法があり,これは K 個のクラスターに means (平均) を用いてまとめていくという手法である.

階層的手法について

それぞれのクラスタ間の距離を決める定義 (method)

単リンク法,最短距離法

2つのクラスタのそれぞれの中から一つづつ点を選び距離を求め,その内で最も近い距離をクラスタ間の距離として用いる.

特徴として,

  • 実用上,外れ値に弱い
  • 細長いクラスタが出やすい
  • 分類感度が低く,連鎖しやすい

などが挙げられる.

完全リンク法,最長距離法

2つのクラスタのそれぞれの中から一つづつ点を選び距離を求め,その内で最も遠い距離をクラスタ間の距離として用いる.

特徴として,

  • 実用上,外れ値に弱い
  • クラスタの大きさが揃いやすい
  • 分類感度は高い

などが挙げられる.

群平均法

単一リンク法と完全リンク法の折衷案.2つのクラスタのそれぞれの中から一つづつ点を選び距離を求め,その平均をクラスタ間の距離として用いる.重みのない平均距離を用いる手法.

特徴として,

  • 単リンク法と完全リンク法の中間的なクラスタが得られる
  • 外れ値に強く,実用的に便利

などが挙げられる.

Ward 法,最小分散法

併合後のクラスタの分散と,併合前のクラスタの分散のそれぞれの和と差が最小となるクラスタ同士を併合していく.要約すると,内部の平方距離を用いているって感じ.

特徴として,

  • 実用上,外れ値に弱い
  • 最も明確なクラスターが出やすい
  • 一番代表的な手法

などが挙げられる.

セントロイド法,重心法

それぞれのクラスタの重心の間の距離の2乗をクラスタ間の距離として用いる.metric はユークリッド距離にのみ適している.

特徴として,

  • クラスタ間の距離が逆になりやすい
  • 単純なセントロイドになる場合がある

などが挙げられる.

重み付き平均法

u と v のクラスタ間の距離を決める際,u 以外の全てのクラスタと,v との距離の平均を用いる.要は,平均距離にそれ以外のクラスタを用いて重み付けを行っているって感じである.

これと,メジアン法は計算量が少ないという利点があったが,そもそも計算機の発達によりあまり使われなくなっている.

メジアン法

重心法の変形で,それぞれの重心にクラスタ内の個数に応じた重み付けを行っている.metric はユークリッド距離にのみ適している.

それぞれの距離の定義 (metric)

  • euclidean:ユークリッド距離
  • minkowski:ミンコフスキー距離
  • cityblock:マンハッタン距離
  • seuclidean:標準化されたユークリッド距離
  • sqeuclidean:乗ユークリッド距離
  • cosine:コサイン距離 (1からベクトルの余弦を引いたもの)
  • correlation:層間距離(1から標本相関を引いたもの)
  • hamming:異なる座標の比率を示すハミング距離
  • jaccard:1からジャカード係数を引いた値
  • chebychev:チェビシェフ距離(最大座標差)
  • canbella:キャンベラ距離
  • braycurtis:ブレイ・カーティス距離
  • mahalanobis:マハラノビス距離

等が存在する.基本的にユークリッド距離のみを使っていれば良いはず,,,

他にも,yule, matching, dice, kulsinski, rogerstanimoto, russellrao, sokalmichener, sokalsneath, wminkowski などが存在する.

どの手法を使うか

  1. サンプルでクラスタリングするか,変数でクラスタリングするか決める.
  2. 階層構造が必要なら階層的クラスタリング,データが大きい場合は非階層的クラスタリングである K-means 法を用いる.
  3. 分類に用いる距離 (類似度) の定義をどれを用いるか決める.
  4. それぞれの手法に応じた選択を行う.

階層構造が必要な場合,とりあえず method は ward 法か群平均法,metric は eucidian, cosine, correlation, chebychev, mahalanobis ぐらいから総当りでやってみる.結果が気に入らない場合は,method を単一リンク法や完全リンク法に変えて試してみると良い.

階層構造が必要ない場合,k-means 法の初期値問題を解決しようとした k-means++ 法を用いれば良い.k 個のクラスタに分けるため,k の値を変えつつ最も適当な k の値を決めると良い.

Python のライブラリについて

階層的手法

scipy.cluster.hierarchy を用いればよい.method は scipy.cluster.hierarchy.linkage,metric は scipy.spatial.distance.pdist あたりにまとまっている.

英語だがこのページが非常によくまとまっている.SciPy Hierarchical Clustering and Dendrogram Tutorial

scikit-learn を用いて,階層的手法のデンドログラムを書き方は見つけられなかった.

非階層的手法 (k-means 法)

Syipy,scikit-learn の両方のライブラリ,どちらを用いても可能である.

Scipy の場合は,scipy.cluster.vq が公式ドキュメントである.どちらかと言うと,scikit-learn を用いるのが主流みたいで,実際に行っている人はあまりいないようです.

scikit-learnの場合は,scikit-learn A demo of the mean-shift clustering algorithmscikit-learn でクラスタ分析 (K-means 法)k-meansの最適なクラスター数を調べる方法 あたりが参考になる.

最後に

それぞれのライブラリのコードについて書こうと考えてましたか,力尽きて最後リンク集になりました.いつか加筆したいです.

また,ご指摘等いただけるとありがたいです.

追記 (2017/07/07)

certeron さんのご指摘より,図の引用元の記述が不充分であることと,階層型の分類の不備があったため,明記・修正を行った.

参考ページ

  1. 機械学習 クラスタリングについて:先駆者.これを Python のライブラリに落とし込めないかと考えるところから始めた.
  2. クラスタリング(クラスター分析):神嶌先生の記事.とても参考になる.
  3. クラスタリングに関する講演・講義資料:神蔦先生の講義資料.これを読んでおけばいい感ある.
  4. 神嶌敏弘. "データマイニング分野のクラスタリング手法 (1)." 人工 知能学会誌 18.1 (2003).
  5. 代表的な機械学習手法一覧:機械学習手法の分類について.
  6. Scipy.org scipy.cluster.hierarchy.linkage:method について
  7. Scipy.org scipy.spatial.distance.pdist:metric について
  8. scikit-learn A demo of the mean-shift clustering algorithm