クラスタリングについてのとても浅い理解

クラスタリングのお勉強をしている

クラスタリングとは

Wikipediaを読んで適当にまとめた: Clustering a.k.a. cluster analysis is a set of methods to classify similar objects into several groups. The similarity is usually defined by distance function or some probability function(how?). Using clustering is a manual and exploratory task that includes the choice for an algorithm, a distance function, number of expected clusters, etc.

アルゴリズムの種類

• 階層的クラスタリング: 樹形図をつくる
  • 距離関数と点同士の接続基準を決める必要あり
  • single-linkage clustering
  • complete-linkage clustering
  • UPGMA(Unweighted Pair Group Method with Arithmetic Mean)
  • WPGMA(Weighted Pair Group Method with Arithmetic Mean)
  • O(n³)とかO(2ⁿ)とかで遅いらしい
    • SLINK, CLINKというO(n²)のものもある
• Centroid-based clustering
  • k-means, k-means++, fuzzy c-means
    • 概念的にはボロノイ図、k-NN、Lloyd's algorithm(wikipediaには連続な空間を入力とする、とあるが、k-meansを実施するためのアルゴリズムとして記載されている例がscikit-learnも含めて見られるのだが)と近い
• Distribution-based clustering
  • 生成モデルを利用する
  • stanとか使う感じのやつかな?
  • EMアルゴリズムもここ?
  • 最近時々見かけるtSNEは?
• Density-based clustering
  • 密度の高い領域をクラスターとして分離し、密度が低いところはノイズや境界として扱う
  • DBSCAN, OPTICS
  • Mean-shift

Evaluation

• 既にラベルの付いたデータがあるならそれを使えばいい
• そうでないなら評価指標を使う(以下のものはラベルありデータ用も含まれる)
  • purity: 得られたクラスタそれぞれで最大多数派の数を数えて、足し合わせたものを全部のデータ数で割ったもの
  • Rand mesure: 全体のうち正しく分類できたものの割合
  • F-mesure: precision, recall
    • 時々見かけるやつはこれか
    • precisionはあるクラスに入れたもののうち正しく分類できていたものの割合、recallはあるクラスに分類されるべきもののうち正しく分類できたいた者の割合
  • Jaccard index: あるクラスに正しく分類できたもの、出来なかったもの、間違えてあるクラスに分類してしまったもののうち正しく分類できたものの割合(F-measureにかなり似ている)
  • Dice index: Jaccard indexの分母をいじってある
  • Fowlkes-Mallows index: precisionとrecallの積のsqrt
  • mutual information: KLダイバージェンスを利用して定義されているらしい
    • scikit-learn見るとMI-based measures require the knowledge of the ground truth classesとある
  • confusion matrix: 色々の定義を行列の成分に詰め込んだやつ
• と山ほど基準がある

実装のAPI

アルゴリズムの差し替えを頻繁にすると思われるので拾い物を使う時もAPIだけはメジャーどころに合わせるラッパーを書いたほうが良いだろう

• scikit-learn

model = KMeans(parameters...)
model.fit(X)

• r

> kmeans
kmeans <- function (x, centers, iter.max = 10L, nstart = 1L, algorithm = c("Hartigan-Wong",
    "Lloyd", "Forgy", "MacQueen"), trace = FALSE)
fit <- kmeans(data, parameters)
fit$cluster

教科書

以下はEoSLの14章の一部の見出しの名前と感想

• 14.3 クラスタ分析
  • 14.3.1 類似度行列
    • 非類似度は距離のことのようで、距離行列を入力にするアルゴリズムがある
  • 14.3.2 属性に基づく非類似度
    • 色々の種類の実験結果で得られた非類似度をかき集めて各人ごとの非類似度として使う感じか
    • 非類似度の定義は量的変数だったり順序変数だったり、場合によっていろいろ定義される
  • 14.3.3 オブジェクト間非類似度
    • 非類似の和を取る前に重みを付ける
  • 14.3.4 クラスタリングアルゴリズム
    • 組み合わせアルゴリズム、混合モデル、最頻値探索に分類している
  • 14.3.5 組み合わせアルゴリズム
    • kmeansを含む一群の分類方法
  • 14.3.6 K平均クラスタリング
  • 14.3.7 ソフトなK平均クラスタリングとしての混合ガウス分布
  • 14.3.8 例: ヒト腫瘍マイクロアレイデータ
  • 14.3.9 ベクトル量子化
    • ここでいうベクトルは実際の用途で言うと、画像のピクセルに入っているRGBとかのことらしい
    • 量子化は連続データから離散データにすること
    • クラスタリングしたラベルを使うのかな
    • 離散化は圧縮に使えるらしい。逆に圧縮手法はものによっては離散化、クラスタリングに使えそう。
  • 14.3.10 Kメドイドクラスタリング
    • kmeansの亜種っぽい
    • クラスタの代表点の計算のステップだけが2乗ユークリッド空間を仮定しているのでそこだけ置き換える
    • 代表点はあるクラスタに属する点の中で、他の点までの距離の総和が小さくなるように選ぶらしい
    • このアルゴリズムは距離行列に相当するものがあれば動くぞ
  • 14.3.11 実用上の問題
    • クラスタ数の設定方法について
      • クラスタ内の点同士の距離の合計を小さくするようなKを選ぶ?
        • この基準だとすべての点を別のクラスタに入れるのが最強になってしまう
        • この合計の減少スピードが落ちた所を最適なクラス多数だと思えばいい
        • ギャップ統計量というものがあるらしい
    • 14.3.12 階層的クラスタリング
      • 凝集型、分割型
      • 二分木
      • デンドログラム
      • cophrenic correlation coefficientというものでうまく樹形図が書けているか評価
        • グループ間非類似度を使う
      • 凝集型には群平均、完全連結、単連結の3種類のグループ間非類似度が使用されることが多い
• 14.4 自己組織化マップ(self-organizing map)
  • 2次元座標系への写像が得られるのでconstarined topological mapとも呼ばれる。
  • https://qiita.com/tohru-iwasaki/items/e51864269767ccc07254