Ruby de TF・IDF

書いた人: noriaki 2007,09月08日(土) 23:00

ujihisaさんのブログで見かけたRubyとsqlite3でTF-IDFを計算してみようというエントリが,先日のエントリでご紹介したTF・IDFをRubyで計算してしまおうということで興味深かったので反応してみます.

ujihisaさんのTF・IDF実装では,適当な量のWebページ群に出現する単語をSqliteデータベースに放り込んで,IDFを自力で計算しています.私のようにYahoo! Web検索サービスに任せるなんて手抜きはしてません.

しかし,IDFの計算方法をたぶんちょっと勘違いされているようです.ujihisaさんのIDF計算方法の抜粋はこんな感じです.

idf = Math.log10(all_words_in_all_page / (wc ? wc.count + count : count))

ここで,変数all_words_in_all_pageにはデータベースに登録した全Webページの全出現単語の出現頻度の合計が入っています. この計算では,ある単語tのIDFを求めるために,all_words_in_all_pagetの出現頻度の合計で割っています.

IDFはInverted Document Frequencyの略語であるように,単語の文書頻度を表す値なので,計算方法は以下のようになります.

idf = Math.log( 全文書数 / 単語tの出現する文書数 )

そこで,これらを踏まえてRubyでTF・IDFを計算してみることにします.

今回のエントリでやっていないこと

  • DRYできれいなコードを作る
  • 単語の単数系・複数形・過去形などの同一視
  • 日本語対応

このエントリを読んだ凄腕rubyistの人が、自分のブログ上で 素敵なコードに修正したものを公開してくれる予定… とかだったらいいなぁ。

rubyneko - Rubyとsqlite3でTF-IDFを計算してみよう

私は凄腕rubyistではないですが,情報検索を研究としてやってる人なので,経験上最適(であろう)データベースのテーブル構成を使ったTF・IDFを計算してみたいと思います.

材料

テーブル作成

データーベス設計は,文書を入れるdocuments,単語を入れるwords,単語がどの文書に何回出現したのかを入れるshowupsの3つのテーブルを用意します.ER図は以下のようになります(クリックすると拡大します).

これらのテーブルを作成するコードinit_tables.rbは以下のとおりです.

init_tables.rb

require 'connect'

ActiveRecord::Schema.define do |s|
  s.verbose = false
  create_table 'documents', :force => true do |t|
    t.column :title, :string
    t.column :uri, :string, :limit => 1024
    t.column :body, :text
  end
  add_index :documents, :uri

  create_table 'words', :force => true do |t|
    t.column :name, :string
    t.column :df, :integer, :default => 0
  end
  add_index :words, :name

  create_table 'showups', :force => true do |t|
    t.column :document_id, :integer
    t.column :word_id, :integer
    t.column :tf, :integer, :default => 0
  end
  add_index :showups, :document_id
  add_index :showups, :word_id
end

ちなみに,requireしているconnect.rbはデータベースへの接続をDRY化するために別ファイルに分けたものです.

connect.rb

require 'rubygems'
require 'active_record'

ActiveRecord::Base.establish_connection(
  :adapter => 'sqlite3',
  :database => 'tfidf.db',
  :timeout => 5000
  )

さらに,テーブル間の関係としてhas_many :throughを利用します.これはTF・IDFを計算する際に,文書に出現する単語数や単語ごとの出現文書数など複数テーブルをまたいだ計算を簡単に扱うためです.ActiveRecordのモデルを宣言しているtables.rbを以下に示します.

tables.rb

class Document < ActiveRecord::Base
  has_many :showups, :dependent => :destroy
  has_many :words, :through => :showups
end

class Word < ActiveRecord::Base
  has_many :showups, :dependent => :destroy
  has_many :documents, :through => :showups
end

class Showup < ActiveRecord::Base
  belongs_to :document
  belongs_to :word, :counter_cache => 'df'
end

:counter_cache => 'df'を指定すると,単語の出現文書数をActiveRecordが自動でカウントしてくれるようになります.また,他の要素の意味は くまくまーのサイトが詳しいです.または,くまくまーのなかの人である舞波さんの書かれたRuby on Rails入門 - 優しいRailsの育て方がこの辺りのことを含め,Rails本としていつも参考にしています.

単語抽出

IDFを計算するためにデータベースに文書を登録し,その文書に含まれている単語と出現頻度を抽出します.

今回は日本語のページを想定しているので,形態素解析を行う必要があります. MeCabをインストールしてやってもよかったのですが,先日のエントリで利用したYahoo! 形態素解析Webサービスが非常に便利だったので,今回もそれをma.rbというライブラリにして利用しています.

import_docs.rb

$KCODE = 'u'
require 'connect'
load 'tables.rb'

require 'ma'
ma = POS::Tagger.new

Dir.glob('docs/**/*').each do |filename|
  next unless FileTest.file?(filename)
  print "importing '#{filename}' ... "
  $stdout.flush
  if Document.find_by_uri(filename)
    puts "skip."
    next
  end
  fr = File.open(filename) do |f|
    doc = ma.prepare(f)
    document = Document.create(
      :uri => filename,
      :title => doc[:title],
      :body => doc[:body]
      )
    if doc[:body].blank?
      puts "skip."
      break
    end
    begin
      words = ma.parse(doc[:body])
    rescue Timeout::Error
      puts "Timeout::Error."
      break
    end
    words.each do |word|
      w = Word.find_or_create_by_name(word.surface)
      begin
        Showup.create(
          :document => document,
          :word => w,
          :tf => word.count
          )
      rescue
        next
      end
    end
  end
  puts "done." if fr
end

import_docs.rbを実行すると,docs/以下の全ファイルをHTMLファイルと仮定して,テキストの部分だけをHpricotで抽出した,Yahoo! 形態素解析で単語抽出を行ってデータベースへ格納します.

ちなみに,このときのYahoo! 形態素解析を利用するためのライブラリma.rbは以下のようになっています.(長い・・ POSTリクエストを送る部分だけでもnet/yjwsの作者さんに送ろうかな)

ma.rb

require 'net/http'
Net::HTTP.version_1_2
require 'kconv'
require 'hpricot'
require 'net/yjws'

class Net::YJWS::MAService
  def execute
    uri = BASE_URI.dup
    uri.query = to_query
    uniq_result = nil
    Net::HTTP.start(uri.host) do |http|
      response = http.post(uri.path, uri.query)
      src = response.body
      xml = REXML::Document.new(src)
      REXML::XPath.match(xml, "/ResultSet/uniq_result").each {|r|
        uniq_result = Result.new
        uniq_result.total_count = REXML::XPath.first(r, "total_count").text.to_i
        uniq_result.word_list = []
        REXML::XPath.match(r, "word_list/word").each {|w|
          word = Word.new
          if surface = REXML::XPath.first(w, "surface")
            word.surface = surface.text
          end
          if count = REXML::XPath.first(w, "count")
            word.count = count.text.to_i
          end
          uniq_result.word_list << word
        }
      } # uniq_result
    end
    { :uniq_result=> uniq_result }
  end
end

module POS
  class Tagger
    def initialize
      @yjws = Net::YJWS::MAService.new
      @yjws.appid = 'morphological_analysis'
      @yjws.results = 'uniq'
      @yjws.uniq_response = 'surface'
      @yjws.filter = 9
    end

    def prepare(file)
      doc = Hpricot(file.read.toutf8)
      title = doc.at(:title).inner_text rescue "untitled"
      begin
        body = doc.at(:body)
        (body/:script).remove
        (body/:style).remove
        text = doc.inner_text
        text = text.strip.tr_s(" \t\n\r\f\v", ' ')
      rescue
        text = ""
      end
      {:title => title, :body => text}
    end

    def parse(text)
      @yjws.sentence = text
      @yjws.execute[:uniq_result].word_list
    end
  end
end

TF・IDFを求める

以上を実行した上で,ようやくTF・IDFを求めることができます.適当なWebページのURLやファイルのURLを以下のように指定してtfidf.rbを実行すると出現単語のTF・IDFが一覧で出力されます.

$ ruby tfidf.rb http://blog.fulltext-search.biz/articles/2007/09/08/tf-idf-by-ruby
end:    75.6907302844764
IDF:    64.1173309637195
rb:     43.6308134484654
単語:   55.7947666917104
require:        48.355464466149
text:   37.8133716553367
エントリ:       11.716287108625
計算:   52.0953314080221
body:   36.3180471866489
count:  52.9535795200876
出現:   48.0879982227897
文書:   44.0806650375572
Ruby:   3.96415272588246
do:     27.0805020110221
uri:    19.2789164355263
TF:     36.0659986670922
(以下省略)

ちなみにこれを行ったときは,IDFのもとになるWebページ群として,このブログの全ページと,そこからリンクされているページをHyper Estraierのクローラで取得しました.それらのページには,技術的な用語が比較的多く出現するため,技術的な単語のIDFが低くなっています. RubyのTF・IDF値が低い辺り悲しくなりますね.文書群をもっと増やせばいい感じの値に収束するんじゃないでしょうか.

それぞれのテーブルのデータ数はこんな感じです.

[noriaki@www tfidf]$ sqlite3 tfidf.db
SQLite version 3.3.6
Enter ".help" for instructions
sqlite> SELECT COUNT(*) FROM showups;
29010
sqlite> SELECT COUNT(*) FROM words;
6308
sqlite> SELECT COUNT(*) FROM documents;
165

以下にtfidf.rbの中身を示します.# 実はこのコードが一番短かったり.

tfidf.rb

require 'connect'
load 'tables.rb'

require 'ma'
ma = POS::Tagger.new

require 'open-uri'

n = Document.count

open(ARGV.shift) do |io|
  result = ma.prepare(io)
  ma.parse(result[:body]).each do |word|
    next unless w = Word.find_by_name(word.surface)
    idf = Math.log(n / w.df.to_f)
    puts "#{word.surface}:\t#{word.count * idf}"
  end
end

参考ページ

rubyneko - Rubyとsqlite3でTF-IDFを計算してみよう
http://ujihisa.nowa.jp/entry/b6b2da3b36
Hpricot, a fast and delightful HTML parser
http://code.whytheluckystiff.net/hpricot/
SQL Designer
http://ondras.zarovi.cz/sql/demo/(ER図作成に利用しました)
ヽ( ・∀・)ノくまくまー(2006-01-27) - habtm と has_many :through (ActiveRecord)
http://wota.jp/ac/?date=20060127#p01

このエントリをdel.icio.usにブックマークしているユーザ数このエントリをdel.icio.usに追加する
このエントリをはてなブックマークしているユーザ数このエントリをはてなブックマークに追加する
 | Tags ,

コメント

  1. ujihisa said 約1分 later:

    氏久です。

    idf = Math.log( 全文書数 / 単語tの出現する文書数 )

    この部分、完全に勘違いしていました。 お恥ずかしい…

    指摘ありがとうございます!

  2. noriaki said 約12分 later:

    ujihisaさん

    コメントありがとうございます.

    IDFそのものが,ちょっと直感的に分かりにくいので勘違いはよくあります.私も長らく分かってなかったですし.

このエントリはアーカイブされています。
コメントする場合は、お手数ですが「このページのURL」を記載した上で、新しいエントリにお願いします。