文書クラスタリング徹底比較 (keras + scikit learn + gensim + α)

4月から新卒エンジニアになりますFooQooと申します．
Twitterのデータ分析に興味がありますので，お仕事の話などありましたら[@FooQoo56](https://twitter.com/FooQoo56)にご連絡いただければ幸いです．

大学院でTwitterハッシュタグのクラスタリングの研究をしていたことから，文書クラスタリングの手法について興味があったため，実験してみました．

# データセット
実験で使用するデータセットはkerasに組み込まれている[ロイターのニュースワイヤー](https://keras.io/ja/datasets/#_5)です．
こちらは，**46のトピックにラベル付けされた，11,228個のロイターのニュースワイヤーのデータセット**となっております．

こちらをtrainおよびtestデータのcsvファイルにしておきます．

```get_reuters.py
from keras.datasets import reuters

(x_train, y_train), (x_test, y_test) = reuters.load_data(path="reuters.npz",
                                                         num_words=None,
                                                         skip_top=0,
                                                         maxlen=None,
                                                         test_split=0.2,
                                                         seed=113,
                                                         start_char=1,
                                                         oov_char=2,
                                                         index_from=0)

i2w = {w_id: w for w, w_id in reuters.get_word_index(path="reuters_word_index.npz").items()}
 
train_docs = []
test_docs = []

for i in range(x_train.shape[0]):
    train_docs.append(' '.join([i2w[w_id] for w_id in x_train[i]]))

for i in range(x_test.shape[0]):
    test_docs.append(' '.join([i2w[w_id] for w_id in x_test[i]]))
    
with open('train.csv', mode='w') as f:
    for i in range(x_train.shape[0]):
        f.write('{0}, {1}\n'.format(train_docs[i], y_train[i]))

with open('test.csv', mode='w') as f:
    for i in range(x_test.shape[0]):
        f.write('{0}, {1}\n'.format(test_docs[i], y_test[i]))
```

# 比較手法
今回の実験では**文書のベクトル化**と**クラスタリング**の手法に分けて比較しました．

## 文書のベクトル化
### TF-IDF
文書をクラスタリングするためには，各文書をベクトルで表現する必要があります．
この手法では文書のベクトルの要素をTF-IDFの重みとします．
(計算方法の詳細は[scikit learnの解説ページ](https://scikit-learn.org/stable/modules/feature_extraction.html#tfidf-term-weighting)を参照ください)

### word2vec
`king - man + woman = queen`でおなじみのword2vecによる単語ベクトルを用いて文書をベクトル化します．
ただしword2vecは単語をベクトルに表現するだけなので，これをそのまま文書のベクトルとするには工夫が必要です．
本記事では[ClaraLabs](https://claralabs.com/)のLaska氏による[Simple datetime disambiguation](https://medium.com/@jaska_at_clara/simple-datetime-disambiguation-fd2374ce664a)を参考に文書のベクトルを計算しました．

Laska氏は単語ベクトルをSPPMIと呼ばれる単語共起行列を拡張したものとし，文書の単語ベクトルにidfによって重み付けした値の総和をcontext vectorとして計算しています．

![Steps for mapping a set of context words to a context vector.](https://cdn-images-1.medium.com/max/800/0*cpeLOZvkZdo2eWyI.)

本実験では，contextを文書とし，word vectorsをSPPMIではなくword2vecとしました．
各文書のベクトルは100次元とし，L2ノルムによって正規化を行なっています．

## クラスタリング
以下の手法を候補とします．

1. k-means 
2. Gaussian Mixture Model (GMM)
3. Spherical k-means (spk-means)
4. Mixture of von-Mises Fisher distribution (movMF)

3および4について解説すると，これらの手法はクラスタ重心が球面状に分布することを仮定したモデルです．
**spk-means**はパラメータとしてクラスタ重心を持つことに対して，**movMF**はクラスタ重心に加えてクラスタ要素の集中度の分布も考慮しています．
このような対応関係は，**k-means**と**GMM**の関係性と類似しています．

[k-mean](https://scikit-learn.org/stable/modules/generated/sklearn.cluster.KMeans.html)および[GMM](https://scikit-learn.org/stable/modules/generated/sklearn.mixture.BayesianGaussianMixture.html)はscikit learn，spk-meansとmovMFは[ClaraLabsのパッケージ](https://github.com/jasonlaska/spherecluster)を利用しました．

また，各手法ではパラメータの探索を行い，最も汎化している設定で実験を行いました．

# 評価尺度
## V-Measure
2007年のEMNLPにて[Rosenbergら](http://www.aclweb.org/anthology/D07-1043)によって提案された評価手法で，条件付きエントロピーがベースとなっています．
この手法では，**homogeneity**と**completeness**を定義し，この性質を数値化します．
以下に[scikit learnの解説の抜粋](https://scikit-learn.org/stable/modules/clustering.html#homogeneity-completeness-and-v-measure)を和訳したものを掲載します．

- homogeneity: 各クラスタは単一クラスの要素のみ含む
- completeness: 与えられたクラスのすべての要素は同じクラスタに割り当てられる

V-Measureは，値の範囲が0から1で，高ければ高いほど上記の性質が良いとみなします．

# 実験結果
実験では各手法で5回のクラスタリングを行い，クラスタ内分散の最も低いモデル同士で評価値の比較を行いました．
評価値は，テストデータにクラスタを予測した結果と真のクラスを元に計算しています．

|  | k-means | GMM | spk-means | movMF |
|:-:|:-:|:-:|:-:|:-:|
|TF-IDF| 0.425 | - | 0.416 | 0.445 |
|word2vec| 0.468 | 0.495 |  0.465 | 0.459 |

GMMは，TF-IDFベクトルの次元数が15,837次元と大きくなりすぎたため，マシンのメモリが足らず結果が得られませんでした．

TF-IDFとword2vecを比較した場合，各クラスタリング手法において，word2vecがそれぞれ高い結果となりました．
クラスタリング手法間を比較した場合，TF-IDFではmovMFが，word2vecではGMMが高い結果となりました．

以下考察です．

TF-IDFよりword2vecの方が総じて性能が良かったため，文書をベクトル化する場合，word2vecを採用した方が良いと考えられます．
一方で，word2vecの学習ではそれなりの時間を有するため，速度を意識する場合はTF-IDFの方がよいのでは？と考えれます．
しかし，TF-IDFベクトルは次元数が大きくなるため，クラスタリングに時間が掛かってしまいます．
よって，時間的なコストはさして変わらないのではないかと考えられます．

全ての結果の中から最も性能のよい手法は，word2vecを用いて計算した文書のベクトルに対してGMMを適用したケースでした．

また，word2vecにおいて，L2正規化を使用せず，実験を行ったところ性能が落ちたので，上記のクラスタリングにおいては文書のベクトル表現にL2正規化した方がよいと考えられます．
(L2正規化を使用しない場合では，文書におけるidf重みの総和が1になるように制限をかけ，文書内の文字数でベクトルの各要素をdivideする)

また，k-meansが他手法と比較して健闘しているので，学習時間のコストも考えるとk-meansは高速なので，とりあえずk-meansを使うのは悪くないように思います．

# まとめ
本記事では，文書クラスタリングの手法を**文書のベクトル化**および**クラスタリング**の観点から比較を行いました．
今回紹介した手法が文書クラスタリングの全てではなく，doc2vecやLDAまたはそのほかの分散表現を用いた手法も考えられます．

上記と同様の実験で，性能が向上するほかの手法がありましたらコメントいただけると幸いです．

# 追記
word2vecの実験における文書のベクトル表現の実装が間違っていたので，修正し再度計算し直しました．(2019/3/21)
ハイパーパラメータの探索を行い，最も汎化している設定において，各手法のテストデータに対する評価値を計算しました．(2019/3/22)