スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

MongoDBのMapReduceでTF-IDFによる日本語の全文検索を実装する(Part 1)

MongoDBのMapReduceでTF-IDFによる日本語の全文検索を実装する(Part 1)



https://github.com/exabugs/similarity_search

前提


  • MongoDB は v2.4.8 以上のこと。
    (mac の brew でインストールされる 2.4.6 だと MapReduce が不安定です。)
  • 形態素解析は行いません。事前にMeCab等で形態素解析して単語(名詞)を抜き出して下さい。


仕様


  • 以下のようなtweetsコレクションを対象とします。
    (対象となるコレクション名は 'master_name' という変数に入れてください。)
    > db.tweets.find();
    { "_id" : ObjectId("52afd7b550433450593e0100"),
    "content" : "到着後はお早めに召し上がり下さい",
    "tf" : { "v" : [
    { "k" : "到着", "v" : 0.333 },
    { "k" : "後", "v" : 0.333 },
    { "k" : "早め", "v" : 0.333 } ] }
    }

  • フィールド"tf.v"には名詞とその出現確率を入れておく。
    (出現確立 : 対象名詞出現回数 / 名詞総数)
  • バッチ・プログラムで以下を実施します。
    (1〜3全てMapReduceで処理しています。)
    1. IDF (Inverse Document Frequency)の辞書作成
    2. 各文書のTF-IDFを計算する
    3. 文書相互のコサイン類似度を計算する
      (ドキュメント総数がN なら、N(N-1)÷2 回のコサイン類似度を計算する。)

  • db[master_name+'_similarity']コレクションに結果が出力される。
    • フィールド a : 元となる文書のObjectId
    • フィールド b : 類似文書のObjectId
    • フィールド score : コサイン類似度 (0〜1)

  • MongoDBのMapReduceは、実行開始時点で値が確定しているものしか処理できない。
    Map中にコレクションを検索したりはできないので、実行開始時点で処理に必要なデータは全てscopeパラメータとして渡す。


バッチ・プログラム


Mongoシェルで実行します。

var master_name = 'tweets';

// ユーティリティ
var util = {
// 乗算
product : function (a, v) {
for (var i = 0; i < a.length; i++) {
if (v[a[i].k])
a[i].w = a[i].v * v[a[i].k];
else
a[i].w = a[i].v;
}
return a;
},
// ノルム
norm : function (a) {
var sum = 0;
for (var i = 0; i < a.length; i++) {
if (a[i].w) {
sum += a[i].w * a[i].w;
}
}
return Math.sqrt(sum);
},
// 内積
innerproduct : function (a, v) {
var sum = 0;
for (var i = 0; i < a.length; i++) {
var info = a[i];
if (v[info.k]) {
sum += info.w * v[info.k];
}
}
return sum;
},
// 辞書化
to_hash : function (a) {
var ret = {};
for (var i = 0; i < a.length; i++) {
if (a[i].w) {
ret[a[i].k] = a[i].w;
}
}
return ret;
}
}

// IDF Dictionary
db[master_name].mapReduce(
function () {
for (var i = 0; i < this.tf.v.length; i++)
emit(this.tf.v[i].k, 1);
},
function(key,values) {
return Array.sum(values);
},
{finalize: function(key, value) {return Math.log(N/value);}, scope: {N: db[master_name].count()}, out: master_name+'_idf'}
);

// TF-IDF
// (idf辞書をハッシュで渡す部分が不安。大きさやコリジョンによるパフォーマンス劣化等は大丈夫か。)
var dic = {};
db[master_name+'_idf'].find().sort({value:-1}).limit(100000).forEach( function (idf) {dic[idf._id] = idf.value} );
db[master_name].mapReduce(
function () {
var v = util.product(this.tf.v, dic);
emit(this._id, {v: v, l: util.norm(v)});
},
function(key,values) {
return values[0];
},
{scope: {util: util, dic: dic}, out: master_name+'_tfidf'}
);
db[master_name+'_tfidf'].find().forEach(function (tgt) {
db[master_name].update({_id: tgt._id},{$set: {tf: tgt.value}});
});
db[master_name+'_tfidf'].drop();

// コサイン類似度 (Cosine Similarity)
db[master_name+'_similarity'].drop();
var cursor = db[master_name].find();
while (cursor.hasNext()) {
var src = cursor.next();
src.tf.condition = util.to_hash(src.tf.v);
db[master_name].mapReduce(
function () {
var s = util.innerproduct(this.tf.v, src.tf.condition);
if (0 < s) emit(this._id, s / this.tf.l / src.tf.l);
},
function(key,values) {
return values[0];
},
{scope: {util: util, src: src}, query: {_id:{$gt:src._id}}, out: master_name+'_tmp'}
);
db[master_name+'_tmp'].find().forEach(
function (dst) {
db[master_name+'_similarity'].insert({a:dst._id, b:src._id, score:dst.value});
db[master_name+'_similarity'].insert({a:src._id, b:dst._id, score:dst.value});
}
);
}
db[master_name+'_tmp'].drop();


// 確認
db[master_name].find({},{_id:1, content:1, tf:1});
db[master_name+'_idf'].find();
db[master_name+'_similarity'].find();
スポンサーサイト

コメントの投稿

非公開コメント

検索フォーム
RSSリンクの表示
リンク
exabugsをフォローしましょう
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。