Technically Impossible

Lets look at the weak link in your statement. Anything "Technically Impossible" basically means we haven't figured out how yet.

PYR103 week 8, 9 クラスター分析

特定テーマに限定したWikiを立ち上げる必要もなく、ブログの様に私見をまとめる必要もない、

  • 講義の予習ノート
  • 読書ノート
  • メモ

などの雑記帳Wikiから移行した投稿。

統計クラスの予習ノート。

用語

centroid 質量中心
重心
centroid method 重心法
CLA CLuster Analysis
Euclidean distance ユークリッド距離
gap statistic ギャップ統計量
K-means K平均法
AHC
Agglomerative Hierarchical Clustering
凝集型階層的クラスタリング
NHC
Non-hierarchical clustering
非階層的クラスタリング

クラスタ分析

impsbl.hatenablog.jp

クラスタ間の距離

ユークリッド距離
平均ユークリッド距離
標準化ユークリッド距離
マハラノビス距離
マンハッタン距離
市街地距離
チェビシェフ距離
ミンコフスキー距離

通常のユークリッド距離は式からわかるとおり、各データの性質の差の2乗和の平方根です。よって、簡単に言えばこの距離は、各性質の単位を無視しているということになります。例えば、長さの差3m(メートル)と気温の差3℃が同等の割合 で性質の差(クラスターの割り当て)に影響すると考える、ということです。それに対して、標準化ユークリッド距離はその逆で、標準化を行なうことでデータの持つ性質の差が性質ごとに開きがないように配慮しているわけです。

標準化ユークリッド距離は各性質の差を標準化していますが、標準化ユークリッド距離のほうがユークリッド距離よりも優れているということではありません。なぜなら、標準化するということは、性質ごとの影響力、重みをなくすということであり、本来影響力がある性質の差も、ほとんど影響のない性質の差も等しく扱うということになってしまうからです。

クラスター分析の手法①(概要) | データ分析基礎知識

クラスタリング手法

最短距離法 minimum
single-linkage clustering
異なるクラスタの内、最も近いデータ同士の距離を、クラスタ間の距離とする。
再長距離法 maximum
complete-linkage clustering
異なるクラスタの内、最も遠いデータ同士の距離を、クラスタ間の距離とする。
群平均法 UPGMA
Unweighted Pair-Group Method using Arithmetic Mean
異なるクラスタの全データ同士の距離の平均を、クラスタ間の距離とする。
McQuitty法 WPGMA
Weighted Pair-Group Method using Arithmetic Mean
異なるクラスタの全データ同士の距離の平均を、クラスタ間の距離とする。
重心法 UPGMC
Unweighted Pair-Group Method with Centroid
異なるクラスタの重心(データの平均)同士の距離を、クラスタ間の距離とする。
メディアン法 WPGMC
Weighted Pair Group Method with Centroid
異なるクラスタの重心(データの平均)同士の距離を、クラスタ間の距離とする。
ウォード法 Ward's method 異なるクラスタを一グループとし、グループ内平方和を最小にするようにクラスター間の距離を定義する。

LanceとWilliamsは、6つの方法を統一的に扱い式を示し、各方法の違いをパラメータ(αp, αq, β γ)の違いで決定できると示した。

  1. 最短距離法
  2. 再長距離法
  3. 重心法
  4. メディアン法
  5. 群平均法
  6. ウォード法

最適なクラスタ数を求める

エルボー法

発想

  • クラスタ分割数kが増えるほど、クラスター内変動は下がり続ける。
  • kが変化することによる、変動の変化量を調べる。
  • 変化量が少なくなる位置(プロット上の「肘」)のkを見つける。

クラスタ内変動=クラスタ内距離の平方和=クラスタ内誤差の平方和
距離(誤差)→クラスタ内のデータから、クラスタの重心までの距離

りんだろぐ rindalog: クラスター分析:クラスター数の決定法
【R言語】階層的クラスタリング結果の可視化及び客観的なクラスタ数の決定方法について - What a Wonderful World

ギャップ統計

発想

  • クラスタ分割数kが増えるほど、クラスター内変動は下がり続ける。
  • kが変化することによる、変動の変化量を調べる。
  • 観測データのクラスタ、一様分布データのクラスタ間の変動を比較し、ギャップGap(k)が最大となるkを見つける。
  1. 解析対象データと、データが散乱し、まとまりをもたない架空のデータ(一様分布のデータ、クラスタ数1のデータ)を用いる。
  2. 両者をクラスタリングし、クラスタのコンパクト性を比較する。
  3. 最大の比較結果(ギャップ)を得るクラスタ数を、最適なクラスタ数と見なす。

解析対象データと架空データの範囲は同じことに注意。

  • コンパクト性

一様分布から作成されたクラスタ内の距離の平均と元データのクラスタ内の距離の平均とを比べて、より密集しているクラスタ数を採用するという方法である。

Wk 観測データによるクラスタ内の変動
Wunif 一様分布データによるクラスタ内の変動
s Wunifの標準誤差



W = \sum_{k=1}^{K}\;\sum_{C(i)=k}\|X_{i}-\bar{X}_{k}\|_2^2\\

\begin{align}
Gap(k) &= \log\;\frac{W_{unif}}{W_k}\\
&= \log\;W_{unif}-\log\;W(k)
\end{align}\\

\hat{k}=min\{k\in {1,...,k_{max}\;:\;Gap(k) \geq Gap(k+1)-s(k+1)}

TEX

W = \sum_{k=1}^{K}\;\sum_{C(i)=k}\|X_{i}-\bar{X}_{k}\|_2^2\\

\begin{align}
Gap(k) &= \log\;\frac{W_{unif}}{W_k}\\
&= \log\;W_{unif}-\log\;W(k)
\end{align}\\

\hat{k}=min\{k\in {1,...,k_{max}\;:\;Gap(k) \geq Gap(k+1)-s(k+1)}

備忘録: gap統計量とS_Dbw
パターン認識02 k平均法ver2.0
R K-means法のクラスタ数を機械的に決定する方法 | トライフィールズ

シルエット分析
凝集度 クラスタ内の全データの距離の平均
乖離度 クラスタ同士の距離
シルエット・スコア 凝集度、乖離度のバランス

シルエット・スコア:±1の間の値を取る。

1 所属クラスタの中心に近い。~~隣接するクラスタから遠い。 クラスタリングの分離性能が良い。
0 クラスタ間の決定境界付近に存在する。 クラスタリングの分離性能が悪い。
-1   間違ったクラスタに所属している可能性がある。

あるクラスタをA、Aに最も近いクラスタをBとする。

ai クラスタAの凝集度~~クラスタA内の平均距離
bi クラスタAB間の意乖離度~~クラスタAB間の平均距離
si シルエット・スコア


x_i \in A\\
x_j \in A\, and\;i \neq j\\
x_m \in B\\
a_i = \sum_{j=1}^{N}\;\frac{\|x_{i}-x_{j}\|}{N}\\
b_i = \sum_{m=1}^{M}\;\frac{\|x_{i}-x_{m}\|}{M}\\
s_i = \frac{b_{i}-a_{i}}{max(a_i, b_i)}

TEX

x_i \in A\\
x_j \in A\, and\;i \neq j\\
x_m \in B\\
a_i = \sum_{j=1}^{N}\;\frac{\|x_{i}-x_{j}\|}{N}\\
b_i = \sum_{m=1}^{M}\;\frac{\|x_{i}-x_{m}\|}{M}\\
s_i = \frac{b_{i}-a_{i}}{max(a_i, b_i)}


クラスター数の決め方の1つシルエット分析 – S-Analysis
k-meansの最適なクラスター数を調べる方法 - Qiita
クラスタリングとレコメンデーション資料

R

dist 距離行列を求める。
factoextra::fviz_cluster クラスタのプロット。
factoextra::fviz_dend 樹形図の描画。
hclust 階層的クラスタ分析。
hcut 階層的クラスタと樹形図の計算。

Python

scipy.cluster.hierarchy

ward ウォード法による距離行列を求める。
dendrogram 樹形図の生成。

sklearn.cluster

AgglomerativeClustering 凝集型クラスタリング