「テキストアナリティクスの基礎と実践」をpythonで読む5 テキストのクラスタリング #Python

この内容は金明哲さんの「テキストアナリティクスの基礎と実践」のRでの実装をpythonで書き換えながら読んでいくものです。
提供されているデータは、すでに形態素解析されてある程度集計されたデータとなります。

説明が不十分であること、参考書通りの解析ができているわけではないことはご了承ください。
詳しくは本を読んでいただければと思います。

前回

トピック分析

5. テキストのクラスタリング

5.1 類似度

語句ベクトルの似ている度合いを測る指標としては、類似度と距離がある。
類似度は、値が大きいほど似ていることを示すのに対し、距離は非類似度とも呼ばれ、値が小さいほど似ていることを示す。
定量的データ$\boldsymbol{x}=(x_1,x_2,\cdots,x_i,\cdots,x_n)$、$\boldsymbol{y}=(y_1,y_2,\cdots,y_i,\cdots,y_n)$のピアソンの積率相関係数は次の式で定義される

$$
r_{xy}=\frac{\sum_{i=1}^n(x_i-\bar{x})(y_i-\bar{y})}{\sqrt{\sum_{i=1}^n(x_i-\bar{x})^2}\sqrt{\sum_{i=1}^n(y_i-\bar{y})^2}}
$$

類似度の指標としては、次に式で表されるコサイン類似度も多く用いられる。
これはピアソンの相関係数の各変数の平均がゼロである場合である。

$$
\cos{r_{xy}}=\frac{\sum_{i=1}^n(x_i)(y_i)}{\sqrt{\sum_{i=1}^n(x_i)^2}\sqrt{\sum_{i=1}^n(y_i)^2}}
$$

5.2 距離

相関係数や関連度指標などの類似度$r$は、次のように距離として変換して用いることができる。

$$
d(\boldsymbol{x}, \boldsymbol{y})=f(r)
$$

例えば、コサイン類似度は、ベクトル$\boldsymbol{x},\boldsymbol{y}$を単位1に正規化すると、ユークリッド距離の2乗$d(\boldsymbol{x},\boldsymbol{y})^2$との間に次の関係が成り立つ。

$$
d(\boldsymbol{x},\boldsymbol{y})^2=2(1-\cos{r_{xy}})
$$

距離の狭義の基本性質を次に示す。

$d(\boldsymbol{x},\boldsymbol{x})=0$
$d(\boldsymbol{x},\boldsymbol{y})\geq0\ (非負性)$
$d(\boldsymbol{x},\boldsymbol{y})=d(\boldsymbol{y},\boldsymbol{x})\ (対称性)$
$d(\boldsymbol{x},\boldsymbol{y})\leq d(\boldsymbol{x},\boldsymbol{z})+d(\boldsymbol{z},\boldsymbol{y})\ (三角不等式)$

量的データの距離

量的データのベクトル$\boldsymbol{x},\boldsymbol{y}$のユークリッド距離は次のように定義されている。

$$
\begin{align}
d_{Euclidean}(\boldsymbol{x},\boldsymbol{y})&=\sqrt{(x_1-y_1)^2+(x_2-y_2)^2+\cdots+(x_i-y_i)^2+\cdots+(x_m-y_m)^2}\
&=\biggl\{\sum_{i=1}^n(x_i-y_i)^2 \biggr\}^{1\ /\ 2}
\end{align}
$$

ユークリッド距離を一般化した次の距離をミンコフスキー距離と呼ぶ。

$$
d_{Minkowski}(\boldsymbol{x},\boldsymbol{y})^q=\sum_{i=1}^n(x_i-y_i)^q
$$

ユークリッド距離を標準化した距離としてマハラノビス距離がある。
マハラノビス距離を2つのベクトル間の距離に適用させたのが標準化ユークリッド距離である。

$$
d_{SE}(\boldsymbol{x},\boldsymbol{y})^2=\sum_{i=1}^n\frac{(x_i-y_i)^2}{\sigma_i^2}
$$

$\sigma_i^2$は変数$i$の分散である。
他には、市街距離、あるいはマンハッタン距離がある。

$$
\begin{align}
d_{Man}(\boldsymbol{x},\boldsymbol{y})&=|x_1-y_1|+|x_2-y_2|+\cdots+|x_i-y_i|+\cdots+|x_m-y_m|\
&=\sum_{i=1}^n|x_i-y_i|
\end{align}
$$

マンハッタン距離を次のように拡張した距離をキャンベラ距離と呼ぶ。

$$
d_{Can}(\boldsymbol{x},\boldsymbol{y})=\sum_{i=1}^n\frac{|x_i-y_i|}{|x_i+y_i|}
$$

相対頻度の非類似度

カウントしたデータを相対頻度に変換したデータにおいては、特に次元が高いときは非類似度の方が有効である。

$$
Schi(\boldsymbol{x},\boldsymbol{y})=\sqrt{2\sum_{i=1}^n\frac{(x_i-y_i)^2}{x_i+y_i}}\
JSD(\boldsymbol{x},\boldsymbol{y})=\frac{1}{2}\sum_{i=1}^n\biggl(x_i\log{\frac{2x_i}{x_i+y_i}}+y_i\log{\frac{2y_i}{x_i+y_i}} \biggr)
$$

確率分布間の差異を測る指標として **カルバック-ライブラー・ダイバージェンス(KLD)**があり、

$$
KLD(\boldsymbol{x}||\boldsymbol{y})=\sum_{i=1}^nx_i\log{\frac{x_i}{y_i}}
$$

これを対象化したジェンセン-シャノン・ダイバージェンス(JSD)がある。

$$
JSD=KLD(\boldsymbol{x}||\boldsymbol{y})+KLD(\boldsymbol{y}||\boldsymbol{x})
$$

JSDはさらに次のように拡張された。

$$
JSD=\frac{1}{2}\biggl\{KLD\biggl(\boldsymbol{x}||\frac{\boldsymbol{x}+\boldsymbol{y}}{2}\biggr)+KLD\biggl(\boldsymbol{y}||\frac{\boldsymbol{x}+\boldsymbol{y}}{2}\biggr) \biggr\}
$$

JSDについて平方根を取ったものをRJSDと記す。

$$
RJSD=\sqrt{\frac{1}{2}\biggl\{KLD\biggl(\boldsymbol{x}||\frac{\boldsymbol{x}+\boldsymbol{y}}{2}\biggr)+KLD\biggl(\boldsymbol{y}||\frac{\boldsymbol{x}+\boldsymbol{y}}{2}\biggr) \biggr\}}
$$

5.3 階層的クラスタリング

階層的クラスタリングとは、個体間の類似度あるいは非類似度(距離)に基づいて、似ている順に集めてクラスター作っていく方法である。
ラベルが付いている部分を葉と呼び、葉と葉の距離(葉から上に延びている線が連結するところまでの高さ)が短いほど似ている。

階層的クラスタリングのプロセス

距離(あるいは類似度)を求める方法を選択し、距離を計算する。
クラスタリング方法(最近隣法や最遠隣法など)を選択し、クラスタリングの順位を決める
樹形図を作成する
結果について検討を行う

階層的クラスタリングの例

データから距離の行列を求め、距離の行列からクラスタリングを行う。クラスタリングはクラスター間の距離に基づいて行う。
クラスター間の距離行列をコーフェン行列と呼ぶ。樹形図はコーフェン行列に基づいて作成する。
コーフェン行列を作成する方法はいくつかある。

import pandas as pd

d1 = pd.read_csv('sakubun259f.csv', encoding='shift-jis', index_col=0)
d1

階層的クラスターの樹形図を示す。
距離がユークリッド距離で、クラスタリングの方法がウォード法であるものと、
距離がRJSD非類似度で、クラスタリングの方法がウォード法であるものを示す。

from scipy.cluster.hierarchy import linkage, dendrogram
from scipy.spatial.distance import pdist
import matplotlib.pyplot as plt
import japanize_matplotlib
import numpy as np

#method_list = ("average", "centroid", "complete", "median", "single", "ward", "weighted")
#metric_lits = ('braycurtis', 'canberra', 'chebyshev', 'cityblock', 'correlation', 'cosine',
#               'euclidean', 'hamming', 'jaccard', 'jensenshannon')

d_array = np.array(d1.iloc[:,:-1])
d_array = d_array / np.sum(d_array, axis=1).reshape(-1,1)+1e-6

fig ,axes = plt.subplots(nrows=1, ncols=2, figsize=(16, 5))

result_eu = linkage(d_array, 
                  metric = "euclidean",
                  method = "ward"
                   );
dendrogram(result_eu, color_threshold=1.3, labels=d1.index, ax=axes[0]);
axes[0].set_title('ユークリッド距離');

result_jsd = linkage(pdist(d_array, metric = "jensenshannon"),
                  #metric = "euclidean",
                  method = "ward"
                   );
dendrogram(result_jsd, color_threshold=1.3, labels=d1.index, ax=axes[1]);
axes[1].set_title('RJSD非類似度');

階層的クラスタリングの諸方法

最近隣法
最遠隣法
群平均法
重心法
メディアン法
ウォード法

などがある。
どの方法を用いるべきかに関しては定説がない。
大きな差異は鎖効果であり、分類対象が1つずつ結合され、クラスターが形成される現象のことである。
ウォード法は、他の方法と比べ鎖効果が起こりにくい。

5.4 クラスターのヒートマップ

個体と変数の対応関係を考察するため、個体と変数との階層的クラスタリングを同時に行う方法としてバイクラスタリング法がある。
バイクラスタリングの結果の視覚化にはヒートマップが多用される。
バイクラスタリングのヒートマップを示す。

テキストのクラスターと語のクラスターがクロスになっているモザイクの部分が各クラスターの特徴となる。
これらの対応関係から、各クラスター内のテキストに共通する特徴を分析できる。

import seaborn as sns

row_linkage = linkage(pdist(d_array, metric = "jensenshannon"),
                      #metric = "euclidean",
                      method = "ward");

col_linkage = linkage(pdist(d_array.T, metric = "canberra"),
                      #metric = "euclidean",
                      method = "ward");

sns.clustermap(pd.DataFrame(d_array, index=d1.index, columns=d1.columns[:-1]),
               row_linkage=row_linkage,
               col_linkage=col_linkage,
               row_cluster=True,
               col_cluster=True,
               figsize=(10, 10),
               cmap='rainbow');

5.5 非階層的クラスタリング

大規模のデータセットのクラスタリングには、非階層的クラスタリング法が多用されている。
非階層的クラスタリングの代表的な方法としてk平均法(k-means)法がある。
基本的な考え方はクラスター$C_k$内の距離のような統計量$W(C_k)$を最小化することである。
式の中の$k$はクラスターの数である。

$$
\min{\biggl\{\sum_{k=1}^KW(C_k) \biggr\}}
$$

$W(C_k)$に関しては、クラスター$C_k$内において中心までの距離が多く用いられる。
中心としてはクラスター内の平均値、中央値などを用いる。
k平均法のアルゴリズムの概要を示す。

$k$個の仮の初期クラスター中心を適当に与える
すべてのデータと$k$個のクラスター中心との距離を求め、個々のデータをもっとも近いクラスターに分類する
新たに形成されたクラスターの中心を求める
ステップ2, 3を繰り返し、クラスターの中心がすべて前の結果と同じであれば終了し、そうでなければ2に戻る

from sklearn.cluster import KMeans

km = KMeans(n_clusters=3,
            init='random',
            tol=1e-4)
y_km = km.fit_predict(d_array)

pd.DataFrame({'文書':d1.index,'cluster':y_km}).T

5.6 クラスター数の決定方法

事前にクラスター数を決める必要がある。
数十種類の指標が提案されているが、計算結果は用いた方法により異なる。
対処法の1つとしては、複数の指標を用いた結果から、多数決をとることである。

5.7 t-SNE法

t-SNE法は、高次元のデータを低次元に縮約する方法である。
実証研究によると、t-SNE法は主成分分析などの従来の方法より、元のデータの再現性がよいことがわかった。

d2 = pd.read_csv('saku11.csv', encoding='shift-jis', index_col=0)
d2

t-SNE法で2次元に縮約した結果の散布図である。
複数のクラスタが識別できる。

from sklearn.manifold import TSNE

d_array = np.array(d2.iloc[:,:-10])
d_array = d_array / np.sum(d_array, axis=1).reshape(-1,1)

tsne = TSNE()
d_tsne = tsne.fit_transform(d_array)
d_tsne /= np.max(d_tsne)

colors = ['#476A2A', '#7851B8', '#BD3430', '#4A2D4E', '#875525',
         '#A83683', '#4E655E', '#853541', '#3A3120', '#535D8E']

plt.figure(figsize=(10,10))

[plt.text(d_tsne[i,0], d_tsne[i,1], d2.index[i], color=colors[i%10], ha='left', va='center') for i in np.arange(len(d2))]

plt.xlim([-1.2,1.2])
plt.ylim([-1.2,1.2])

t-SNEのアルゴリズム

SNE法は、正規分布の仮定のもとで、元データの2点の非対称確率と縮約後の低次元空間上の2点の非対称確率の差を最小にする確率である。
t-SNE法では正規分布ではなく、縮約したデータが自由度1のt分布に従うことを仮定している。

(1) 元のデータ$\boldsymbol{x}_i$と$\boldsymbol{x}_j$の条件付き確率を以下のように定義する。
式の中の$\sigma_i$は経験則か、$\boldsymbol{x}_i$の近隣分布のエントロピーを用いた複雑さ(perplexity)で決める。

p_{j|i}=\frac{\exp{(-|\boldsymbol{x}_i-\boldsymbol{x}_j|^2\ /\ 2\sigma_i^2)}}{\sum_{k\neq i}\exp{(-|\boldsymbol{x}_i-\boldsymbol{x}_k|^2/2\sigma_i^2)}},\ p_{i|j}=0\\
Perplexity=2^{H(p_i)},\ H(p_i)=-\sum_{j}p_{j|i}\log_2(p_{j|i})

t-SNE法では、対称性をとるため$\boldsymbol{x_j}$ から $p_{j|i}$を求め、$p_{ij}=\frac{p_{j|i}+p_{i|j}}{2n}$ で対称化する。

(2)縮約後のデータの$y_i$と$y_j$の条件付き確率は、SNEでは$\sigma^2=1/2$となる正規分布で$q_{ij}$を求めるが、
t-SNEでは縮約した低次元空間の確率分布を自由度1のt分布とし、次の式で求める。

$$
q_{ij}=\frac{(1+|y_i-y_j|^2)^{-1}}{\sum_{k\neq l(1+|y_i-y_j|^2)^{-1}}},\ q_{ij}=0
$$

(3)上記で求めた$p_{ij}$と$q_{ij}$のカルバック-ライブラー・ダイバージェンス$C$を最小化する
$$
C=KLD(P||Q)=\sum_i\sum_jp_{ij}\log{\biggl(\frac{p_{ij}}{q_{ij}} \biggr)}
$$

$C$の最小解は勾配降下法で求める。

$$
\frac{\partial C}{\partial y_i}=4\sum_{j\neq i}(p_{ij}-q_{ij})(y_i-y_j)(1+|y_i-y_j|^2)^{-1}
$$

「テキストアナリティクスの基礎と実践」をpythonで読む5 テキストのクラスタリング

前回