手順3 : 文のクラスタリング

2.1節の手順3では，$X$-means法[4][5]というクラスタリング手法を用いて文をクラスタリングする． $X$-means法は，図2.2のようにK=2での$K$-means法による分割を繰り返し，ベイズ情報量$BIC$によって分割を停止するかを判定することで，クラスタ数を自動で決定するクラスタリング手法である．分割前のベイズ情報量$BIC$，分割後のベイズ情報量$BIC'$に対し，$BIC \leq BIC'$ならば分割を停止する． $p$変量正規分布を

$$f(\theta_i;x)=(2\pi)^{-p/2}\vert V_i\vert^{-1/2}\exp\left[\frac{1}{2}(x-\mu_i)^tV_i^{-1}(x-\mu_i)\right]$$

と仮定すると，$BIC$は以下のように定義される．ここで $\hat{\theta_i}=[\hat{\mu_i},\hat{V_i}]$は，$p$変量正規分布の最尤推定値とし， $\mu_i$は$p$次の平均値ベクトル，$V_i$は$p \times p$の分散共分散行列である．$q$はパラメータ空間の次元数で，$V_i$の共分散を無視すれば$q=2p$であり，無視しなければ$q=p(p+3)/2$である．$L$は尤度関数で$L(=\Pi f()$である．

$$BIC=-2\log(L\hat{\theta_i};x_i \in C_i) + q\log{n_i}$$

また，分割後の$BIC'$は以下のように定義される．ここで $\hat{\theta_i'}=[\hat{\theta_i^1},\hat{\theta_i^2}]$は，分割後の2つの各クラスタにおける$p$変量正規分布の最尤推定値とする．共分散を無視すると，各$p$に対し平均と分散の2つのパラメータが存在するので， $q'=2 \times 2p = 4p$であり，無視しなければ$q'=2q=p(p+3)$である．

$$BIC'=-2\log(L\hat{\theta_i'};x_i \in C_i) + q'\log{n_i}$$

図: $X$-means法のイメージ