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))ここで,変数
IDFはInverted Document Frequencyの略語であるように,単語の文書頻度を表す値なので,計算方法は以下のようになります.
idf = Math.log( 全文書数 / 単語tの出現する文書数 )そこで,これらを踏まえてRubyでTF・IDFを計算してみることにします.
今回のエントリでやっていないこと
- DRYできれいなコードを作る
- 単語の単数系・複数形・過去形などの同一視
- 日本語対応
このエントリを読んだ凄腕rubyistの人が、自分のブログ上で 素敵なコードに修正したものを公開してくれる予定… とかだったらいいなぁ。
rubyneko - Rubyとsqlite3でTF-IDFを計算してみよう
私は凄腕rubyistではないですが,情報検索を研究としてやってる人なので,経験上最適(であろう)データベースのテーブル構成を使ったTF・IDFを計算してみたいと思います.
材料
- Ruby-1.8.6
- rubygems-0.9.4
- ActiveRecord-1.15.3
- Hpricot-0.5.140
- net-yjws-0.0.20070619
- sqlite-3.3.6
- sqlite3-ruby-1.2.1
テーブル作成
データーベス設計は,文書を入れる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
)さらに,テーブル間の関係として
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単語抽出
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
endimport_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
endTF・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



氏久です。
この部分、完全に勘違いしていました。 お恥ずかしい…
指摘ありがとうございます!
ujihisaさん
コメントありがとうございます.
IDFそのものが,ちょっと直感的に分かりにくいので勘違いはよくあります.私も長らく分かってなかったですし.