文書をクラスタリングする

by

人間、生きてるといろんな情報と出会い、それらをクラスタリングしたくなるのがこの世の常である。機械学習ライブラリは一から自分で実装するよりはすでに実績のあるものを利用するのが良いだろう。まずは Mahout を使ってみる。

テキストコーパスの取得

まずはテキストコーパスを用意する。実験なので無難に青空文庫とかでもいいのだけど、いますぐ分析したい文書があるならそれを使えば良い。君は日頃収集しているソーシャルネットワークの情報を使ってもいいし、運営しているサービスに寄せられたユーザーの声を利用してもいい。

ちなみにいい話判定器に格納されたいい話を使うなんてのも一興である。

形態素解析

我々は日本人である。日本語文書は英語のように単語どうしが空白で区切られていない。そこで形態素解析エンジンを利用する必要があるし、ここではいわゆる分かち書きをする。

シェルスクリプトでの単純な例。

1
2
3
4
for file in `find -type f -name "*.txt"`
do
  mecab -O wakati -o $file.wakati.txt $file
done

MeCab は Ruby 等の各種言語のバインディングなどもあるのでそれらを利用したり MapReduce でやってもいい。

シーケンスとベクトルの生成

分かち書きをしたファイルを HDFS にアップロードし、シーケンスとベクトルを生成する。

1
2
3
4
5
6
7
8
9
10
11
hadoop fs -put corpus_examples corpus_examples
mahout seqdirectory -i corpus_examples -o corpus_seq
mahout seq2sparse -i corpus_seq -o corpus_sparse -a org.apache.lucene.analysis.WhitespaceAnalyzer

# 中身のチェック
hadoop fs -lsr corpus_seq
hadoop fs -lsr corpus_sparse

# 頻出語句のチェック
mahout seqdumper -s corpus_sparse/wordcount/part-r-00000 -o wordcount
sort -nrk4 -t: wordcount | head

これで Mahout を使う準備はできた。

キャノピークラスタリング

単純に K 平均法でクラスタリングしてもいいけどクラスタの数を事前に見積もれないよね、ということで TF-IDF で単語ごとの重み付けをしたベクトルを利用しキャノピー重心を求める。

1
mahout canopy -i corpus_sparse/tfidf-vectors -o corpus_canopy -t1 0.4 -t2 0.6 -dm org.apache.mahout.common.distance.CosineDistanceMeasure -ow

次にキャノピー重心を利用して K 平均法クラスタリング。

1
2
3
mahout kmeans -i corpus_sparse/tfidf-vectors -c corpus_canopy/clusters-0/part-r-00000 -o corpus_kmeans --maxIter 10 -cl -ow
# クラスタのダンプを取得し内容を精査
mahout clusterdump -d corpus_sparse/dictionary.file-0 -dt sequencefile -s corpus_kmeans/clusters-1 -p corpus_kmeans/clusterdPoints -o dump

あとは dump の中身を見たりクラスタ間及びクラスタ内部点間の距離を計測したりしてクラスタリングの質を向上すれば良い。コサイン距離以外の類似性指標を使っても良い。こういうのはライブラリが自動でやってくれるわけではないので自力でひたすら数字とにらめっこするしかなさそうですね。

Ruby でクラスタリングする

Mahout は環境を用意したり使うまでの事前準備が意外とだるい。そこでもっとカジュアルに Ruby でやってみる。

Ruby の世界には以前にも書いた通り AI4R や K-Means 、それに拙作の kmeans といったライブラリがある。

上記のうち K-Means というのが高速かつ便利で、内部的に Distance Measures ライブラリを呼んでいる。類似性指標としてコサイン距離やユークリッド距離など自由に指定することができる。ちなみに拙作の kmeans では集合間の距離をピアソン相関係数で求めている。

公式の例にしたがってベンチマークを取ってみる。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
require 'rubygems'
require 'benchmark'
require 'k_means'
require 'ai4r'

# 1000 records with 50 dimensions
data = Array.new(1000) {Array.new(50) {rand(10)}}
ai4r_data = Ai4r::Data::DataSet.new(:data_items=> data)

# Clustering can happen in magical ways
# so lets do it over multiple times
n = 5

Benchmark.bm do |x|
  x.report('euclidean') do
    n.times { KMeans.new(data, :distance_measure => :euclidean_distance) }
  end
  x.report('cosine') do
    n.times { KMeans.new(data, :distance_measure => :cosine_similarity) }
  end
  x.report('j_index') do
    n.times { KMeans.new(data, :distance_measure => :jaccard_index) }
  end
  x.report('j_distance') do
    n.times { KMeans.new(data, :distance_measure => :jaccard_distance) }
  end
  x.report('b_j_index') do
    n.times { KMeans.new(data, :distance_measure => :binary_jaccard_index) }
  end
  x.report('b_j_distance') do
    n.times { KMeans.new(data, :distance_measure => :binary_jaccard_distance) }
  end
  x.report('tanimoto') do
    n.times { KMeans.new(data, :distance_measure => :tanimoto_coefficient) }
  end
  x.report("Ai4R") do
    n.times do
      b = Ai4r::Clusterers::KMeans.new
      b.build(ai4r_data, 4)
    end
  end
end

で、こればベンチマーク結果。類似度は何を使ってもいいけどウーム AI4R 遅すぎだろという感じですね。

1
2
3
4
5
6
7
8
9
               user     system      total        real
euclidean     13.250000   0.090000  13.340000 ( 15.467818)
cosine         4.780000   0.040000   4.820000 (  5.913864)
j_index        7.940000   0.080000   8.020000 (  9.106817)
j_distance     8.400000   0.080000   8.480000 (  9.889458)
b_j_index      8.040000   0.050000   8.090000 (  9.884315)
b_j_distance   5.030000   0.060000   5.090000 (  5.860338)
tanimoto       4.630000   0.020000   4.650000 (  5.422322)
Ai4R         121.700000   1.140000 122.840000 (159.453762)

まとまっていないけど以上です。