nakatani @ cybozu labs

データ

自然言語処理を試すには、とにもかくにもデータが必要。
学術的には Reuters-RCV1 とかとかとかとか使う方が正しいんでしょうけど。
突っ込みを入れてもらいやすいよう、できるだけ検証しやすい形でサンプルコード＆データを見せていきたいな、とか企んでいるので、Reuters-RCV1 とかだとちょっと尻が重い……。

というわけで Project Gutenberg から O.Henry の短編集を借りてくることにしました。
各短編がおおむね 3000 語前後、ほど良さげな長さで揃っていて、かつ全部持ってくれば 200 編以上とボリュームもそこそこというあたりが決め手。

え？　もっとカテゴリがはっきりしているデータの方がいいんじ ゃないかって？
うーんそうかも。でも、自分の興味のあるデータの方が楽しいですよね(笑)。ま、それにデータは入れ替えられますから。

Project Gutenberg はフォーマットがぐちゃぐちゃ。
Project Gutenberg のテキストデータから本文を抽出する を使ってまず本文部分を抽出しつつ、短編ごとに切り出し(もちろんこれもフォーマットバラバラ)、さらにラベルに使いたいのでタイトルも抽出(もち以下略)、ということをしなくちゃなりません……

以下がそのための Ruby コードです。

require 'rubygems'
require 'stemmer'

docs = Array.new
terms = Hash.new
ARGV.each do |path|
  # ファイルを開いて本文を取得
  file = path.dup
  file = $1 if path =~ /\/([^\/]+)$/
  text = if path =~ /\.zip$/i
    file.sub!(/\.zip$/i, ".txt")
    `unzip -cq #{path} "*.txt"`
  else
    open(path){|f| f.read}
  end
  text = extract_gutenberg_body(text)

  # 短編ごとに分割
  list = text.split(/^[IVX]+\s*\.?$/)[1..-1]
  list = text.split(/^\n{4}$/) if list.size<=1
  list.each do |x|
    next unless x =~ /^(.+)$/
    title = $1

    words = x.scan(/[A-Za-z]+(?:'t)?/)
    next if words.size < 1000

    words.each do |word|
      word = word.downcase.stem # 単語の原形(簡易版)
      terms[word] ||= Hash.new(0)
      terms[word][docs.size] += 1
    end
    docs << {:title=>title, :n_words=>words.size}
  end
end

open('corpus', 'w'){|f| Marshal.dump({:docs => docs, :terms => terms}, f) }

extract_gutenberg_body() は Project Gutenberg のテキストデータから本文を抽出する の抽出コードを呼び出すものです（上記サンプルコードでは省略）。
これに The Four Million by O. Henry などからダウンロードした zip アーカイブされた ascii ファイルを渡すと、各短編の抽出と使用語の解析が行われて corpus という marshal ファイルに出力されます(全ての Gutenberg ドキュメントに対応するわけではもちろんありません……)。

$ ./extract_corpus.rb 2776.zip 2777.zip ...

使用語については原形に戻してます。精度が良くなることを期待するのと(必ずしも上がるわけではないのですが)、計算時間を減らすため。
サンプルコードでは stemmer モジュールを使って簡便に済ませてしまってます。
手元のコードでは、ちょっとでも精度を上げようと、ここに書いてあるやり方で Linguistics モジュールも組み合わせつつ、さらに手作り辞書とかごにょごにょしてます。
Pathtraq のカテゴリ分類での経験からすると、ここの精度が最終的に結構効いてくるんだろうなあ、という予感はします……まあ今のところは技術検証なのでシビアにやる必要はないですけど。

データの準備は本題ではないので、このへんで。
データだけでこんなに面倒じゃあ、検証とか無理無理……と思われると嬉しくないので、ここで作った corpus ファイルをさっくり公開します。

O.Henry の短編 109 データのダウンロード

これを利用するには以下のように書けばＯＫ。

data = open('corpus'){|f| Marshal.load(f) }
docs = data[:docs]
terms = data[:terms]

#docs = [{:title=>"THE GIFT OF THE MAGI", :n_words=>2105}, ...]
#terms = {"cat"=>{49=>2, 22=>1, 55=>2, 39=>1, 50=>1, ..}, ...}

docs には短編のタイトルとその語数が格納されています。
terms は Hash 形式の inverted index になっていて、キーの term に対して、ドキュメントID とそのドキュメントにおけるその term の出現回数(= term frequency) の Hash を返します(ドキュメントID は docs におけるインデックス)。
term には原形の語幹が入っています。
この形式のデータがあれば、いきなりいろいろ遊べますよね！

simple HAC の実装

IIR Ch 17.1 の simple, naive, but inefficient な hiererachical agglomerative clustering(HAC) を実装してみましょう。

# tf-idf を計算(一番オーソドックスな式)
def calc_tdidf(tf, df, n_docs)
  tf * Math.log(n_docs / df)
end

# similarity(ドキュメントの類似度、内積) を計算
def calc_sim(v1, v2)
  sim = 0
  v1.each_with_index {|x, i| sim += x * v2[i] }
  sim
end

# similarity(ドキュメントの類似度) を計算
class Similarity
  def initialize
    @memo = Hash.new # ドキュメント名に対して結果をキャッシュ
  end
  def calc(d1, d2)
    key = [d1[:title], d2[:title]]
    @memo[key] || @memo[key.reverse] || (@memo[key] = calc_sim(d1[:vector], d2[:vector]))
  end
  def include?(pair, title) # ペアに含まれていれば片割れを返す
    return pair[0] if pair[1] == title
    return pair[1] if pair[0] == title
  end
  # ２つのクラスタをマージ(inefficient なのはこいつのせい)
  def merge(d1, d2)
    @memo.each do |key, value|
      if (title2 = include?(key, d1[:title])) && title2 != d2[:title]
        value2 = @memo[[title2, d2[:title]]] || @memo[[d2[:title], title2]]
        @memo[key] = value2 if value2 > value
      end
    end
  end
end

# corpus を読み込み
data = open(ARGV[0] || 'corpus'){|f| Marshal.load(f) }
docs = data[:docs]
terms = data[:terms]

# 軸
#axes = terms.keys # all terms
axes = terms.keys.select{|t| n=terms[t].size; n>1 && n<docs.size } # 2～n_docs-1

# 各ドキュメントの特徴ベクトルを計算
docs.each_with_index do |doc, doc_id|
  l2 = 0
  v = axes.map do |term|
    rev_index = terms[term]
    docfreq = rev_index.size
    termfreq = rev_index[doc_id]
    x = calc_tdidf(termfreq, docfreq, docs.size)
    l2 += x * x
    x
  end
  l = Math.sqrt(l2)
  doc[:vector] = v.map{|x| x / l} # 単位ベクトルに
end

# HAC algorism(ここが本体)
sim = Similarity.new
clusters = []
while docs.size > 1
  maxsim = 0
  maxsim_pair = nil
  docs.each do |d1|
    docs.each do |d2|
      break if d1==d2
      s = sim.calc(d1, d2)
      if maxsim < s
        maxsim = s
        maxsim_pair = [d1, d2]
      end
    end
  end

  clusters << [maxsim_pair[0][:title], maxsim_pair[1][:title], maxsim]
  docs.delete(maxsim_pair[1])
  sim.merge maxsim_pair[0], maxsim_pair[1]
end

# dendrogram を出力
tree = Tree.new(clusters)
puts tree

IIR に掲載されている pseudo code では 13行しかないんですけどね(苦笑)。
しかもこれでも dendrogram を出力するための Tree クラスはアルゴリズムに直接関係ない＆でかいので省略してあるんですよ……（後掲してあるのでご安心を）。

細かい説明は後にして、まずは実行。
以下のような dendrogram が得られます(テキストだから枝分かれの表現が貧弱ですが)。

------------------------- THE BRIEF DEBUT OF TILDY
||||||||| ||    |    +--- AN ADJUSTMENT OF NATURE
||||||||| ||    +-------- A COSMOPOLITE IN A CAFE
||||||||| |+------------- FROM THE CABBY'S SEAT
||||||||| |  +----------- THE GREEN DOOR
||||||||| |      +------- SPRINGTIME A LA CARTE
||||||||| +-------------- THE FURNISHED ROOM
|||||||||   | |   | +---- BETWEEN ROUNDS
|||||||||   | |   |    +- TOBIN'S PALM
|||||||||   | |   +------ AN UNFINISHED STORY
|||||||||   | +---------- THE SKYLIGHT ROOM
|||||||||   +------------ LOST ON DRESS PARADE
||||||||+---------------- MAN ABOUT TOWN
|||||||+----------------- MEMOIRS OF A YELLOW DOG
||||||+------------------ THE CALIPH, CUPID AND THE CLOCK
||||||         +--------- THE COP AND THE ANTHEM
|||||+------------------- MAMMON AND THE ARCHER
||||+-------------------- BY COURIER
|||+--------------------- AFTER TWENTY YEARS
|||      |            +-- THE COMING-OUT OF MAGGIE
|||      +--------------- A SERVICE OF LOVE
||+---------------------- SISTERS OF THE GOLDEN CIRCLE
||                 +----- THE GIFT OF THE MAGI
|+----------------------- THE LOVE-PHILTRE OF IKEY SCHOENSTEIN
+------------------------ THE ROMANCE OF A BUSY BROKER

109 ドキュメントだとダイアグラムが大きすぎるので、短編集 The Four Million に含まれる 25 編のクラスタリング結果です。
本当は閾値も出したいんだけど、それは宿題ということで(Graphviz で書けるかなぁ？)。

この結果を見ても、コーパスの性質を知らないと「？？？」でしょうけれど（だからもっとわかりやすいデータをって！）。
それでもクラスタリングとしては到底満足できない結果であることはわかります。
例えば左から３列目までの枝分かれを見ることで、全体を４つのクラスタに分けることが出来ますが、「１個、１個、２個、２１個」というクラスタリングになってしまいます。本当に１個しか含まれないクラスタが存在すべきデータならともかく(１つだけイタリア語とかｗ)、そうでないならこの割り方は不自然です。
このように枝分かれが階段状になってしまうことを「チェイニング効果」というそうですが、それが起きてしまっているわけですね。

ここで実装した simple unefficient な HAC ではチェイニング効果が発生しやすいことはわかっていたんですが(だから inefficient!)、それが確認できた、ということですね。
17.2 以降の efficient な HAC ではそれが抑えられるはずなので、次回はそちらに挑戦します。

コードについて

簡単に。

ドキュメントの特徴ベクトルは、基準となる terms をあらかじめ選んでおき、term ごとの tf-idf を計算、それを並べたものになります(後のために単位ベクトル化しておく)。
ドキュメント間の類似度 (similarity) は、その特徴ベクトルの内積(=単位ベクトルなので、２つのベクトルのなす角の余弦)と定義します。0 から 1 の間の値となり、大きいほど類似度が高いと見なすことが出来ます。
このあたりは IIR の Chapter 6 に書いてあります。

特徴ベクトルは (terms の個数)次元の vector space の元となるわけですが、109 ドキュメントでの使用語数は 13000 くらいあるので 13000 次元の vector space ！
……なんて考えただけでもうんざりするので(しかもテスト用の小さいコーパスに過ぎないのに!)、サンプルコードでは恣意的に減らして document frequency が１だったり、ドキュメント数と一致(=全ドキュメントに出現)というものについては除外してみました。それでもまだ 8000 あるんですが。
正しくは Chapter 13 の feature selection などを駆使するべきなのでしょうが、そこは後回し。

あとは基本的に IIR の pseudo code に従って。
ただ、対称な similarity を２回計算するのを嫌って、結果のキャッシュとかしてます。

次回は上で書いたとおり、このコードを efficient HAC に発展させたいです。
おっとそうそう。dendrogram 出力クラスも載せておきます。だらっと書いたので長いです(汗)。

class Tree
  def initialize(clusters)
    @tree = Hash.new
    clusters.each do |d1, d2, s|
      branch d1, d2
    end

    @lines = Array.new
    @index = Hash.new
    gen_lines @tree.values[0]
    clusters.each do |d1, d2, s|
      connect d1, d2
    end
  end

  def get_tree(d)
    if @tree.key?(d)
      @tree.delete(d)
    else
      d
    end
  end
  def branch(d1, d2)
    @tree[d1] = [get_tree(d1), get_tree(d2)]
  end

  def gen_lines(branch)
    if branch.instance_of?(Array)
      gen_lines branch[0]
      gen_lines branch[1]
    else
      @lines << "- " + branch
      @index[branch] = @lines.size - 1
    end
  end

  def connect(d1, d2)
    i1 = @index[d1]
    i2 = @index[d2]
    i1, i2 = i2, i1 if i2 < i1
    @lines.each_with_index do |line, i|
      if i==i1
        @lines[i] = "-" + line
      elsif i==i2
        @lines[i] = "+" + line
      elsif i>i1 && i<i2
        @lines[i] = "|" + line
      elsif line =~ /^-/
        @lines[i] = "-" + line
      else
        @lines[i] = " " + line
      end
    end
  end
  def to_s
    @lines.join("\n")
  end
end