gap統計量とS_Dbw
1 はじめに
クラスタ数評価指標である gap統計量, S_Dbw についてまとめる.
2 設定
データセット(行列) \(:{\boldsymbol X}\)
\begin{align*} {\boldsymbol X} = \begin{bmatrix} x_{11} & \cdots & x_{1p} \\ \vdots & \ddots & \vdots \\ x_{N1} & \cdots & x_{Np} \end{bmatrix} = \begin{bmatrix} {\boldsymbol x}_{1}^{T}\\ \vdots \\ {\boldsymbol x}_{N}^{T} \end{bmatrix} \in {\mathbb R}^{N \times p} \end{align*}
- データ点 \(: \{{\boldsymbol x}_{l}\}_{l=1}^{N}\), データ点数 \(:N\), 特徴数 \(:p\)
- \(\{{\boldsymbol x}_{l}\}_{l=1}^{N}\) の中心点 \(:\displaystyle \bar{\boldsymbol x} = \frac{1}{N} \sum_{i=1}^{N} {\boldsymbol x}_{i}\quad(\bar{\boldsymbol x}=[\bar{x}_{1}\cdots \bar{x}_{p}]^{T})\)
- データ点 \(: \{{\boldsymbol x}_{l}\}_{l=1}^{N}\), データ点数 \(:N\), 特徴数 \(:p\)
- クラスタ数の候補 \( k \in \{1,\cdots K\}\)
- \({\boldsymbol X}\) のクラスタリング結果
- \(k\) 個のクラスタ(添字集合) \(: \{ C_{l} \}_{l=1}^{k}\)
- \(C_{l}\) 中に含まれるデータ点数 \(: n_{l} = \mbox{card}(C_{l})\)
- \(C_{l}\) の中心点 \(: \displaystyle {\boldsymbol v}_{l} = \dfrac{1}{n_{l}} \sum_{i \in C_{l}} {\boldsymbol x}_{i}\quad({\boldsymbol v}_{l} = [ v_{l1} \cdots v_{lp} ]^{T})\)
- \(k\) 個のクラスタ(添字集合) \(: \{ C_{l} \}_{l=1}^{k}\)
3 gap統計量
3.1 概念
(参考: tibshirani2001estimating)
- 解析対象のデータセット
- データ点が散乱し, まとまりを持たない架空のデータセット
両者をそれぞれクラスタリングして得られたクラスタの"コンパクト性"を比較する.
クラスタ分割数候補のうち, 比較結果に最も大きな差異(gap)が見られたクラスタ数を最適な分割数と判断する.
3.2 特徴
- データセットの最適クラスタ分割数が \(1\) であるときも有効に判別することが可能
(最適クラスタ分割数が \(1 \cdots\) データセット中のデータ点が散乱しまとまりを持たない状況)
3.3 定義
"コンパクト性" の指標
\begin{align*} W_{k} := \sum_{l=1}^{k} \dfrac{1}{2n_{l}} \left( \sum_{\substack{i,i' \in C_{l} \\ i \neq i'}} \| {\boldsymbol x}_{i} - {\boldsymbol x}_{i'} \|_{\ell_{2}}^{2} \right) \end{align*}
\(B\) 個の架空データセット \( \{{\boldsymbol X}^{(b)}\}_{b=1}^{B}\)
\begin{align*} {\boldsymbol X}^{(b)} &:= \begin{bmatrix} x^{(b)}_{11} & \cdots & x_{1p}^{(b)} \\ \vdots & \ddots & \vdots \\ x_{N1}^{(b)} & \cdots & x_{Np}^{(b)} \end{bmatrix} = \begin{bmatrix} {\boldsymbol x}_{1}^{(b)~T}\\ \vdots \\ {\boldsymbol x}_{N}^{(b)~T} \end{bmatrix} \in {\mathbb R}^{N \times p} \\ & x_{ij}^{(b)} \sim \mbox{Uniform}(\min_{i} x_{ij}, \max_{i} x_{ij}) \end{align*}
gap統計量
\begin{align*}\displaystyle\mbox{Gap}(k) &:= \underbrace{\dfrac{1}{B} \sum_{b=1}^{B} \log(W_{k}^{(b)})}_{{=:m}} - \log(W_{k}) \\ \displaystyle \mbox{sd}_{k}&:= \sqrt{\dfrac{1}{B}\sum_{b=1}^{B} \{\log(W_{k}^{(b)}) - m \}} \end{align*}
最適なクラスタ分割数 \(\hat{k}\)
\begin{align*} \hat{k} := \mbox{smallest}~k ~~ \mbox{such}~\mbox{that}~\mbox{Gap}(k) \geq \mbox{Gap}(k+1) - \sqrt{1 + 1/B}~\mbox{sd}_{k+1} \end{align*}
4 S_Dbw
4.1 概念
(参考: halkidi2001clustering)
解析対象のデータセットをクラスタリングして得られたクラスタの"コンパクト性"と"分離性"
をそれぞれ定量的に評価し, 上記2つの評価値を足し合わせる.
クラスタ分割数候補のうち, 評価値を足し合わせた結果が最も小さいクラスタ数を最適な分割数と判断する.
4.2 特徴
- 計算量 \(: O(N)~\) ( \(k,p \ll N\) のとき)
- 比較的に評価性能が良い (参照: liu2010understanding )
4.3 定義
"コンパクト性" の指標
\begin{align*} \mbox{Scat}(k) := \dfrac{1}{k}\sum_{l=1}^{k}\dfrac{\| Var(C_l) \|_{\ell_{2}}}{\| Var({\boldsymbol X}) \|_{\ell_{2}}} \end{align*} \begin{align*} \left( Var(C_l) := \dfrac{1}{n_{l}} \begin{bmatrix} \sum_{i \in C_{l}}(x_{i1}-v_{l1})^{2} \\ \vdots \\ \sum_{i \in C_{l}}(x_{ip}-v_{lp})^{2} \end{bmatrix},~Var({\boldsymbol X}) := \dfrac{1}{n_{l}} \begin{bmatrix} \sum_{i=1}^{N}(x_{i1}-\bar{x}_{1})^{2} \\ \vdots \\ \sum_{i=1}^{N}(x_{ip}-\bar{x}_{p})^{2} \end{bmatrix} \right)\end{align*}
"分離性" の指標
\begin{align*} \mbox{Dens_bw}(k) := \dfrac{1}{k(k-1)} \sum_{l=1}^{k}\left(\sum_{\substack{l'=1 \\ l \neq l'}}^{k}\dfrac{ \overbrace{\sum_{i \in C_{l} \cup C_{l'}} f({\boldsymbol x}_{i},\frac{{\boldsymbol v}_{l} + {\boldsymbol v}_{l'}}{2})}^{\tiny{{\boldsymbol v}_{l}\mbox{と}{\boldsymbol v}_{l'}\mbox{の中点付近に存在するデータ点の個数}}}}{\max\{ \sum_{i \in C_{l}}f({\boldsymbol x}_{i},{\boldsymbol v}_{l}),\sum_{i \in C_{l'}}f({\boldsymbol x}_{i},{\boldsymbol v}_{l'}) \}} \right) \end{align*} \begin{align*} \left( f({\boldsymbol x},{\boldsymbol v}) = \left\{ \begin{array}{ll} 0 & \mbox{if}~\| {\boldsymbol x} - {\boldsymbol v} \|_{\ell_2} > stdev \\ 1 & \mbox{otherwise} \end{array} \right. ,~stdev := \frac{1}{k} \sqrt{\sum_{l=1}^{k}\| Var(C_l) \|_{\ell_2}} \right) \end{align*}
S_Dbw
\begin{align*} \mbox{S_Dbw}(k) := \mbox{Scat}(k) + \mbox{Dens_bw}(k) \end{align*}
最適なクラスタ分割数 \(\hat{k}\)
\begin{align*} \hat{k} := \mathop{\rm argmin}\limits_{k} \mbox{S_Dbw}(k) \end{align*}
5 まとめ
- クラスタの持つ性質のうち,
- クラスタ内のデータ点同士の距離が近い性質("コンパクト性")に着目したのがgap統計量
- "コンパクト性"に加え, あるクラスタと他のクラスタが離れている性質("分離性")に着目したのがS_Dbw
- クラスタ内のデータ点同士の距離が近い性質("コンパクト性")に着目したのがgap統計量
- gap統計量はデータセットにクラスタが存在するかどうかの判別に強みを持ち,
S_Dbwはクラスタ存在時に, 最適クラスタ数を精度良く効率的に決定する上で強みを持つ.
( \(\ast\) クラスタの概念が曖昧なため, 何をもってクラスタが存在するか, 最適クラスタ数とするかについては解析者の主観が伴う)
参考文献
- [tibshirani2001estimating] R. Tibshirani, G. Walther & T. Hastie, Estimating the number of clusters in a data set via the gap statistic, Journal of the Royal Statistical Society: Series B (Statistical Methodology), Vol. 63, No. 2, pp. 411-423, 2001.
- [halkidi2001clustering] M. Halkidi & M. Vazirgiannis, Clustering validity assessment: Finding the optimal partitioning of a data set, pp. 187-194, In Proceedings IEEE International Conference on Data Mining, 2001.
- [liu2010understanding] Y. Liu, Z. Li, H. Xiong, X. Gao & J. Wu, Understanding of internal clustering validation measures, pp. 911-916, In 2010 IEEE International Conference on Data Mining (ICDM), 2010.
