はじパタ ~クラスタリング~


はじめてのパターン認識の読書メモです。

はじパタ クラスタリング

 

概要

教師データなしで、入力データ間の類似度あるいは非類似度でグループ分けを行うクラスタリングについて書かれている。

 

類似度と非類似度

データとクラス間の類似度を図る基本的な尺度が距離である

ミンコフスキーの距離

$$d(x_{i}, x_{j}) = (\sum_{k=1}^{d}\mid{x_{ik}} – {x_{jk}}\mid^{a})^{\frac{1}{b}}$$

aの値が大きくなるほど、特徴間の差に大きな重みを与えることができる。
逆にbの値が大きくなるほど、特徴間の重みを小さくすることができる。
このabの値により、様々な距離を設定することができる。

例:
a = 1, b = 1の場合 → 市街地距離
a = 2, b = 2の場合 → ユークリッド距離
a = 2, b = 1の場合 → ユークリッド距離の2乗
a, b = ∞の場合 → チェビシェフ距離

この他にも、キャンベラ尺度や方向余弦などもある。

 

非階層型クラスタリング(K-平均法)

K-平均法

1. N個のデータをランダムにK個のクラスタに振り分ける
2. それぞれのクラスタの平均ベクトルを求める
3. k個のクラスタのそれぞれの重心が新しい平均になる
4. 再度k個クラスタに分ける

k個のクラスタは、すべての観測値を最も近い平均に関連付けることによって作成されます。ここでの区画は、手段によって生成されたボロノイ図を表します。

Image from Gyazo
下記リンクより引用
https://en.wikipedia.org/wiki/K-means_clustering

問題点

この方法は、初期値に大きく依存してしまう。
なので、初期値を何回か変更して、実行する必要がある。

 

階層型クラスタリング(融合法)

階層型クラスタリング(融合法)

N個のデータを一つのクラスタに統合する手法。
そしてこの統合されていく過程は、樹形図で表現することができる。

「はじめてのパターン認識」では、下記のように書かれている。

【融合法 手順】
1. n = N
2. n * nの距離行列を作る
3. もっとも距離が近い2つのデータやクラスタをまとめて、一つのクラスタにする
4. n = n -1
5. n > 1であれば 2 に、n = 1であれば終了

そして、クラスタ間の類似度の定義によって、様々な手法が存在する。
今回は、階層法の中で最も精度が高いウォード法をまとめる。

ウォード法

クラスタAとBの距離をそれらが融合されたときのクラスタ内変動分を定義し、距離の小さなクラスタから融合していく方法である。

$$D(A,B)=\sum_{x\in{A,B}}d(x, \mu_{A})^{2} – (\sum_{x\in{A}}d(x, \mu_{A})^{2} + \sum_{x\in{B}}d(x, \mu_{B})^{2}) = S_{A,B} – (S_{A} + S_{B})$$

これを使用することで、樹形図の下の位置でもクラスを形成することができる。

 

確率モデルによるクラスタリング

クラスタを確率的にどこに属するかを決めるクラスタリングのこと。

混合分布

複数の分布を混ぜた分布

Q関数

隠れ変数の期待値を事後確率で置き換えた関数のこと。

EMアルゴリズム

分布のパラメータ推定に用いられる解法のこと。
確率モデルのパラメータの最尤推定値を求める手法のこと。

【手順】
E(Expectation)
 → 隠れ変数の事後確率を求める(Q関数)
 → 推定したモデルによって、各データのクラスタを推定
M(Maximization)
 → Q関数を最大にするパラメータを求める
 → 確率モデルの推定

 

参考にした記事

パッケージユーザーのための機械学習(7):K-meansクラスタリング

パッケージユーザーのための機械学習(6):階層的クラスタリング

数式を使わずイメージで理解するEMアルゴリズム

はじめてのパターン認識輪読会 10章後半

EMアルゴリズム徹底解説