機器學習中的Optimal Transport及相關問題：（三）文字聚類
這篇文章我打算回顧一下我2017年在ACL發表的關於文字聚類的文章，並分享一下重現部分實驗結果的程式碼和使用方法。
這是我博士工作的一個自然延續。我在2015年前後一直在研究Wasserstein barycenter（WBC）的高效能運算方法，簡單來說，WBC是用來刻畫測度空間上分佈中心的一個自然定義，類比歐式空間上向量的平均。但是和歐式空間的上向量做平均不同，離散分佈（可以理解為點雲）的中心並不是顯然的，WBC的定義使得它沒有封閉的計算表示式，必須要通過優化得到。如果能快速計算WBC，就為KMeans形式的聚類方法提供了有效支援，而我ACL的工作用一句話來概括就是
將文字(text)看作詞向量空間上的分佈，利用WBC來表示分佈中心(means)，從而實現Kmeans的一個演算法。
換句話說對一個文字資料集，只需要給演算法提供一個預訓練好的詞向量模型，將文字對映到詞向量空間上的分佈，就可以做對文字做Kmeans聚類了。ACL文章的一個主要發現是這麼直觀簡潔的做法效果卻非常好。
廢話不多說，我們先把跑一個簡單的實驗。
環境配置
- 先配置一個新的python2.7虛擬環境，在這個環境下安裝一些包
$ pip install numpy scipy sklearn cvxopt gensim==0.12.1 nltk
2. 再裝一下MPI和OpenBLAS
$ sudo apt install mpi-default-dev libopenblas-dev
3. 下載解壓Mosek 7.1 到${HOME}目錄，並ofollow,noindex">申請免費的academic license 。將郵件收到的lic檔案放到${HOME}/mosek目錄下。
預處理文字
下載用來預處理文字的指令碼
$ git clone https://github.com/bobye/acl2017_document_clustering.git $ cd acl2017_document_clustering $ wget http://infolab.stanford.edu/~wangz/project/linguistics/ACL17/acl2017dataset.zip $ unzip acl2017dataset.zip
再下載一個預訓練好的詞向量模型，可以用比較經典的glove，Google-word2vec，或者我幾年前隨手訓練的一個： https:// psu.box.com/s/bah111zno k5xs6cdztddfwdc9msq33g1
把詞向量模型放到同一個目錄下（acl2017_document_clustering），然後跑一下預處理的指令碼，獲得兩個預處理好的資料檔案，第一個d2s結尾，第二個d2s.vocab0結尾。
$ python export_d2s.py raw categories: 54 document count: 1983 average words: 22 (1983, 4863) $ ls story_cluster.d2s* story_cluster.d2sstory_cluster.d2s.vocab0
第一個文字檔案的格式大概是這樣的：
400 24 0.1488716753303587 0.24316779995271623 0.2314516109605463 0.19002949575269293 0.1313640700443559 0.2609550908453762 0.1658936459471341 0.19002949575269293 0.2509378080991073 0.22270067398052742 0.2750736579046661 0.2609550908453762 0.16299024238964863 0.1985648241749686 0.1807775332823086 0.11838726661190102 0.2314516109605463 0.1488716753303587 0.20989625045864707 0.21903195014715737 0.23681924103981736 0.1488716753303587 0.18854754142869967 0.1716418335937983 4523 4342 4296 4275 4211 3907 3807 3768 3727 2949 2859 2652 2509 2232 1786 1651 1621 949 933 673 581 556 497 249 400 15 0.2631001122049208 0.3451717336122755 0.24740288965452167 0.23907641419163206 0.2045446855924344 0.21613236550073492 0.2713602243848376 0.37423216840429857 0.12508312416492076 0.17598118532807402 0.3266498670500045 0.2002741218543161 0.25597535923852455 0.31302548445807793 0.1846561806351315 4299 4296 3807 3175 2589 2106 1947 1597 1531 770 673 275 249 190 171 ...
第一個行表示詞向量維度（冗餘資訊），第二行表示文字的單詞個數（24），第三行是一個長度為24的權重向量，表示每個詞的權重（tfidf），第四行表示24個詞token在詞典（vocab0）中的index（從1開始，0保留作未知單詞）；然後開始下一個文字，依次類推。
執行d2_kmeans獲得聚類結果
編譯d2_kmeans軟體包
$ git clone --recursive https://github.com/bobye/d2_kmeans.git $ cd d2_kmeans $ cp make.inc.Ubuntu make.inc $ make $ make test
如果test都可以正確運行了，說明你的mosek安裝是完整的。
d2_kmeans 支援MPI，我的電腦有8個核，所以我需要先把資料拆分成8段：
$ ./d2 -i ../acl2017_document_clustering/story_cluster.d2s -n 2000 -d 400 -s 22 --types 7 --prepare_batc hes 8 Task: 0-th phase is of D2_WORD_EMBED rank 0 warning: only read 1983 d2! IO time: 0.694081 write 1983 indices to ../acl2017_document_clustering/story_cluster.d2s.ind batch_size: 248 write 248 objects to ../acl2017_document_clustering/story_cluster.d2s.0 write 248 objects to ../acl2017_document_clustering/story_cluster.d2s.1 write 248 objects to ../acl2017_document_clustering/story_cluster.d2s.2 write 248 objects to ../acl2017_document_clustering/story_cluster.d2s.3 write 248 objects to ../acl2017_document_clustering/story_cluster.d2s.4 write 248 objects to ../acl2017_document_clustering/story_cluster.d2s.5 write 248 objects to ../acl2017_document_clustering/story_cluster.d2s.6 write 247 objects to ../acl2017_document_clustering/story_cluster.d2s.7 [Finish!]
資料原來有1983個文字，被平均分成8段後，每段有不超過248個文字。這裡的幾個引數的含義是：
- n：一個略大於等於1983的數字，用於pre-allocation
- d：詞向量的維度
- s：通常可以選擇在[1, average-word-count-per-document]區間
- types：d2_kmeans支援多種格式的分佈輸入，7表示詞向量輸入。
接下來就可以跑並行8核跑d2_kmeans了：這裡我隨便選了k=50
$ mpirun -n 8 ./d2 -i ../acl2017_document_clustering/story_cluster.d2s -n 248 -d 400 -s 22 --clusters 50 --types 7 -------------------------------------------------------------------------- Task: 0-th phase is of D2_WORD_EMBED rank 7 warning: only read 247 d2! IO time: 1.205412 ------------------------------------------------------------------------- Accelerated Discrete Distribution Clustering under Wasserstein Distance version preview, build #1, timestamp 2015/9/16 15:40:24 written by Jianbo Ye, 2014 - 2015 ------------------------------------------------------------------------- Initializing centroids ... [done] Round 0 ... Re-labeling all instances ... 1983 objects change their labels 99148 distance pairs computed seconds: 4.967810 Update centroids ... phase 0: label counts:109 13 8 67 1 33 58 13 5 5 41 7 25 113 196 15 7 5 14 170 54 103 4 17 9 80 18 3 7 14 10 14 8 18 78 37 239 118 39 2 7 31 24 1 4 4 5 42 17 71 iterobjprimresdualresseconds ---------------------------------------------------------------- 208.1005640.0711320.0709600.272611 407.8423650.0663370.0644840.534532 607.5926330.0618720.0577380.794823 807.4378520.0566860.0514751.083981 1007.3361190.0509660.0461601.357285 Round 1 ... ... Round 22 ... Re-labeling all instances ... 3 objects change their labels 14726 distance pairs computed seconds: 74.710868 Update centroids ... phase 0: label counts:114 14 12 58 1 29 61 15 65 9 82 12 23 94 108 25 39 8 28 65 41 103 5 23 8 100 72 3 18 13 13 17 10 21 139 39 59 110 51 3 11 42 11 1 6 4 6 104 46 42 iterobjprimresdualresseconds ---------------------------------------------------------------- 206.2556420.0341120.0015940.289595 406.2869900.0238230.0010900.619123 606.3089340.0178550.0009590.930083 806.3227510.0141110.0009051.266073 1006.3315490.0117460.0008911.575809 Round 23 ... Re-labeling all instances ... 1 objects change their labels 14049 distance pairs computed seconds: 77.219085 Terminate! Iteration time: 77.219172 0 labels change.mean cost 6.333734time 82.229855 s [done] 114 14 12 58 1 28 61 15 65 9 82 12 23 94 109 25 39 8 28 65 41 103 5 23 8 100 72 3 18 13 13 17 10 21 139 39 59 110 51 3 11 42 11 1 6 4 6 104 46 42 Write centroids to ../acl2017_document_clustering/story_cluster.d2s_261544_c.d2 Write data partitioned labels to ../acl2017_document_clustering/story_cluster.d2s_261544.label Write serial data labels to ../acl2017_document_clustering/story_cluster.d2s_261544.label_o [Finish!]
評估聚類結果
跑出結果後回到acl2017_document_clustering目錄，就可以看一下具體的數字了（文章中方法和baseline的具體數字都是通過grid search超參得到的）：
$ python export_d2s.py 2>/tmp/null Method: D2 Clustering Vocabulary Embedding: word2vec_400_10_10.bin number of clusters: 50 [ 114712264513121737202210181612 1341312 1427251225321214 154765432241514203739 2317211019111410 381292610935893292412] [114141258128611565982122394 10925398 286541 1035238 100723181313171021 13939 59 1105131142111646 1044642] Homogeneity: 0.584 Completeness: 0.573 V-measure: 0.579 Normalized Mutual Information: 0.579 Adjusted Mutual Information: 0.501 Adjusted Rand Index: 0.217
小結
我們回顧了d2_kmeans在文字聚類上的應用。這個演算法相比傳統的topic modeling和low-rank approximation的方法比效果更好，但計算量要大幾個數量級，所以並行幾乎是處理大規模資料必須的選項。
參考文獻
Ye, Jianbo, et al. "Determining Gains Acquired from Word Embedding Quantitatively Using Discrete Distribution Clustering."Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers) . Vol. 1. 2017.
Ye, Jianbo, et al. "Fast discrete distribution clustering using Wasserstein barycenter with sparse support."IEEE Transactions on Signal Processing 65.9 (2017): 2317-2332.