Hatena::ブログ(Diary)

ダウンロードたけし(寅年)の日記 このページをアンテナに追加 RSSフィード Twitter

2011-03-01

非同期で全文検索エンジンgroongaを叩く AnyEvent::Groonga 書いたよ

要するにAnyEventでgroongaを使いたかったのでperlモジュール書きました。んでもって久々にCPANにアップしましたよ、という告白です。

AnyEvent::Groonga - Groonga client for AnyEvent

http://search.cpan.org/~miki/AnyEvent-Groonga/

非同期でガンガン全文検索エンジンを叩きたいな、ということでAnyEvent::Groonga。

なおYappo さんが取り組まれているCライブラリperlバインディングスとは異なり、AE::Groongaはgroongaディストリビューションに同梱されてるオリジナルの「groongaサーバ」を対象としています。

このgroongaの組み込みサーバは、じつはhttpとgqtp(groonga独自プロトコルらしい)両方をしゃべれます。また普通にローカルのDBとしての問い合わせもできます。

んで、このgqtpプロトコルとローカルDB問い合わせについては、どちらの場合にもクライアント側にgroongaがインストールされている必要があります。

ですがhttpであればクライアント側にはgroongaは必要ありません。なのでgroongaサーバ以外のマシンからは普通にhttp経由で呼び出すのがお手軽なユースケースかと思われます。


使い方

使い方はこう。

use AnyEvent::Groonga;

my $groonga = AnyEvent::Groonga->new(
    protocol => 'http',
    host       => 'localhost',
    port       => '10041',
);

# blocking interface
my $result = $groonga->call(
    select => {
        table                  => "Site",
        query                 => 'title:@test',
        output_columns => [qw(_id _score title)],
        sortby                => '_score',
    }
)->recv;

print $result->dump;

$any_event_cv = $groonga->call( groongaコマンド => 引数リファンレンス ) という形になります。

AnyEventのcondvarがかえってくるので、そのままrecvすればブロッキング風になります。

ノンブロッキングにする場合はcall backを指定してください。

# non-blocking interface
$groonga->call(
    table_create => {
        name => "Test",
        ....
    }
)->cb(
    sub { 
        $result = $_[0]->recv;
    }
);

なお$resultとして取得したオブジェクトですが、AnyEvent::Groonga::Resultというクラスのインスタンスになっています。

例外としてselectコマンドの時だけAnyEvent::Groonga::Result::Selectというさらに深いネームスペースのオブジェクトを返すようにしています。

selectの時だけ$result->hit_numとか$result->itemsなどのメソッドが使えてちょっと便利、にしたつもりなんですが、どうかな。。自分でももっと使い込んでみないとわからんな。ここら辺の設計はだいぶ甘いかも。

なおgroongaのコマンドは全部で20種類以上あり、一応その全部に対してAnyEvent経由でコマンドを投げられるはずなんですが、まだ検証はたりてません。

元のDSLが少々むずかしくて、とくにJSONパラメータでのクオーテーションのエスケープとか、文字コードまわりとか、泥臭い変換処理を伴うため、まだまだ不十分。バグとか不具合などあったら教えてください。

なおgroongaコマンドの詳細についてはgroongaのオフィシャルサイトのドキュメントを参照して下さい。

AnyEvent::Groongaの使い方は、まだあんまりドキュメント書けてないのでテストコードでも見ながらがんばってみてください。


sennaとgroongaについて

全文検索エンジンと言えばsenna、ということで今まで頑にsenna(正確にはtritonn)だけを愛し続けてきたのですが、やっぱり書き込みが多くなってくるとMyISAMのテーブルロックが頻発し、全体のパフォーマンスが低下するし。。。そろそろお別れかしら、と思い始めていました。

というわけで、そろそろgroonga!

  • なんといっても「参照ロックフリー」だゼ
  • mysqlやpostgresに依存しない独自のストレージ持ってるゼ
  • カラム志向のちょっと頑固なKVSだゼ

もうgroongaがまぶしすぎて困ります。

実際に書き込み処理をループで大量にまわしつつ、同じディスクを読んでいるgroongaサーバにselectを並列して投げてみましたが、ほとんどパフォーマンスは劣化しません。参照ロックフリーってすごくいいかも〜。

mysqlのgroongaストレージエンジンも既にリリースはされていますが、

結論として、groongaオリジナルサーバでも十分にパフォーマンスよさげなので、AnyEvent::Groongaは手っ取り早くgroongaの恩恵にあずかりたい、とう人におすすめです。

2011-02-16

perlでデーモン書く時は素直にMoose化しておくのもいいかもな

今更Mooseの話題かよ、と思われることでしょうが、自分は常に流行の3年遅れぐらいを全力で追いかけるタイプなので、自分にとっては今が旬。というわけで、Moose的なはなしを書きます。

突然ですが、現役バリバリのperl使いのみなさんに質問です。

POEやらAnyEventやらでちょっとしたアプリケーションサーバを書く場合、みなさんはどうやって「デーモン化」してますか?

自分はもう何回もこの手のものを書いてきたつもりですが、実は未だにベストな手法を編み出せてません。。。

App::DaemonDaemon::Genericあたりでなんとなく自分流な形を模索した時期もありましたが、結局どれも面倒くさくなって、最近では「もう nohup perl hoge_server.pl & でいいじゃん」みたいな。「止める時は pkill -f hoge_server でいいじゃん、文句アッカ」みたいな。そんなダメダメな運用を繰り返す今日この頃であります。

daemontoolsじゃないヤツで

そんな話をすると「最近はdaemontoolsがいいみたいよ」という流れになるわけですが、自分はどうもあの雰囲気になじめないんですよ。

「/serviceとか大胆な配置場所がちょっと鼻につくぜ」とか「みんながイイっていってるのは本当はイクないんだぜ。」とか訳の分からない理由をつけては新しいものの導入を拒否してしまいます。

新しいものを拒否するという現象はいよいよエンジニアとしての終わりが近いナ、と自分でも感じる今日この頃なんですが、流行の3年あとを追いかけるオールドタイプにとっては新しすぎるのは無理なんです。はい。

まぁ本当はただの食わず嫌いなんですが、とにかくdaemontoolsはちょっと矢田。できれば外部ツールにたよらずperlだけでシンプルに解決したいな、と。

そこで考えてみたんですが、MooseX::DaemonizeとMooseX::LogDispatch、あとMooseX::SimpleConfigをうまく組み合わせたものでデーモン化の下地をつくってやって、そこにアプリケーションサーバ本体を載せるような構成はどうだろうか、と。

構成イメージ

イメージはこんな感じです。

libの下にAppというネームスペースをつくってあげて、その中で「MooseXを組み合わせたデーモン化の下地」を書いておきます。そしてscript/my_server.plからはApp::MyServerを、App::MyServerからはMyserverを、という順に呼び出します。

.
|-- lib
|   |-- App
|   |   `-- MyServer.pm
|   |-- MyServer
|   |   |-- Fuga.pm
|   |   `-- Hoge.pm
|   `-- MyServer.pm
`-- script
    `-- my_server.pl

つまりデーモン化の足回り的なコードはすべてApp::MyServerに閉じ込めてしまします。ここでMooseXをモリモリ使います。それ以外のサーバ本体のコードとはきれいに分離できるようにしています。

実はこのアイデア、牧さんが2年くらい前に書いていたHamakiを見て盗作させていただきました。ゴチです。

で、そのデーモン化の足回りとなるApp::Myserverのコードはこんな感じになります。

適当に書いているのでがちゃがちゃしてますが。

package App::MyServer
use Moose;
use MyServer;

with qw(MooseX::Daemonize MooseX::LogDispatch MooseX::SimpleConfig);

has '+configfile' => ( default => "/etc/daemon.yaml", );

has config => (
    is       => 'ro',
    isa      => 'HashRef',
    required => 1,
);

has log_dispatch_conf => (
    is       => 'ro',
    isa      => 'HashRef',
    lazy     => 1,
    required => 1,
    default  => sub {
        my $self = shift;
        if ( $self->foreground ) {
            {   class       => 'Log::Dispatch::Screen',
                min_level   => 'debug',
                stderr      => 1,
                DatePattern => 'yyyy-MM-dd',
                format      => '[%d] [%p] %m at %F line %L%n'
            };
        }
        else {
            {   class       => 'Log::Dispatch::FileRotate',
                min_level   => 'debug',
                filename    => '/tmp/app.log',
                mode        => 'append',
                DatePattern => 'yyyy-MM-dd',
                max         => 50,
                format      => '[%d] [%p] %m at %F line %L%n'
            };
        }
    },
);

has pidbase => (
    is      => 'rw',
    isa     => 'Str',
    default => "/tmp/",
);

after "start" => sub {
    my $self = shift;
    return unless $self->is_daemon();
    my $server = MyServer->new(
        config => $self->config,
        logger => $self->logger,
    );
    try {
        $server->start;
    }
    catch {
        warn "an error occuerd: $_";
    }
};

no Moose;

__PACKAGE__->meta->make_immutable;

1

ちなみにこっちが起動スクリプト


# my_server.pl

#!/usr/local/bin/perl -w
use strict;
use warnings;
use App::MyServer;

my $daemon = App::MyServer->new_with_options();

my ($command) = @{ $daemon->extra_argv };
$daemon->$command if $daemon->can($command);

warn( $daemon->status_message );
exit( $daemon->exit_code );

まず言えることとして、MooseX::Daemonizeのおかげでstart, stop, restartなどが使えるようになっています。

またMooseX::Daemonizeは内部でMooseX::Getoptを使ってるので、これだけで引数の処理を面倒みてくれるしMooseX::SimpleConfigとの食い合わせもよいようで、configファイルでの指定と引数での指定をミックスして使うことも可能になります。

# 起動イメージ
perl -Mblib script/my_server.pl --configfile ./config.yaml start

さらにさらに、MooseX::Daemonizeの機能で -f オプションをつけるとフォアグラウンド処理になるので、MooseX::LogDispatchもこれに連動するようにしてます。-f をつけて起動すると自動的にスクリーンに、そうでない時はapp.logというファイルにロギングする、とかね。気が利いてるでしょ。

あとは$configと$loggerをオブジェクトとしてそのままサーバ本体のコンストラクタに渡している点もこだわりポイントです。

こうすることで、サーバ本体側では$loggerや$configをそのまま使えばよい。

つまり今まで動かしていたようなサーバプログラムに最低限の改修をくわえるだけでこのウツワの上に載せることができるかなと。無理に全体をMoose化しなくてもよい、という状態にしたかったのです。

まとめ

自分は今までかたくなに「Mooseは嫌いだ」と言ってきました。自分とこの開発チームでのMoose導入もガッチリ阻止してきました。

なのでこのブログを読んでくれる仕事関係の方々は「はぁ?このおっさん今更なに言ってんのさ!」と思うことでしょう。


ごめんね。B型だから言うことがコロコロ変わるのさ。勘弁してつかあさい。




いや、正直いうと、今でも「何でもかんでもMooseを導入するのはよろしくない」と思ってます。

特に起動にかかる時間は間違いなく長くなるので、何度も呼び出すようなプログラムMooseを使わない方が良いと思います。

でもサーバスクリプトなんかは起動に少しくらい時間がかかってもたいして問題にならないし、部分的にMoose化するのは悪くないかなと。MooseXなRoleたちを上手につかってやると自分流の定番サーバスタイルができあがるかな、と思った次第です。

いま仕事でアプリケーションサーバを再構築しているものがあるので、まずそいつを上記のような構成にして試してみようかなと考えてます。


おわり。

2011-02-01

「みんなの検索」リリースしました

昨日、仕事で開発をすすめていた検索機能をリリースしたので、ちょっと紹介します。

gooウェブ検索」で、自分に似た検索をしている人たちの関心事が見える機能「みんなの検索」を提供開始

gooのweb検索で適当なキーワードで検索すると、結果表示面の一番したの方に「みんなが検索中」というボックスが表示されます。

f:id:download_takeshi:20110131111451j:image

これは何かというと、いま入力したキーワードと同じような意味や関心ごとを持って検索している人たちの検索キーワードストリームっぽく表示される、というモノです。

http://search.goo.ne.jp/option/topics/2011/

「みんなの検索」は、同じまたは類似した検索キーワードを入力して検索している他のユーザが、どんな検索キーワードを入力しているのかを表示する機能です。あなたに似た人たちが、たった今しらべているキーワードストリームが表示されます。

これまでの関連ワードやサジェスト機能とは異なり、「知りたかった」ものを見つけやすくするだけでなく、あなた自身も気づいていない「知りたい」欲求を刺激するキーワードを提供します。

コンセプトのようなもの

いままでの検索は、とにかく目的の情報に最短距離でスピーディーにたどり着くための道具でした。

それに対して、「みんなの検索」でねらっていることは「脱線」です。

例えば、町中をぶらぶら歩いているときって、周りの人の様子や景色が自然と目に入っていると思います。無意識のうちに。「あの子がきてる服かわいいな」とか「あ、こんな店できたんだ」とか。

それって人間という動物が、無意識のうちにさまざまな「気づき」を得るためにすごく高度な「情報探索」を行っている、ということだと思うんですよ。

その観点からすると、一般的な検索エンジンが提供している機能とは、いってみればその高度な人間さまに競走馬のマスクをつけさせて、「目的物しか見せない」「とにかくよそ見をせずに、速く検索結果にたどりきなさい」といっているようなモノかもしれません。

事実、調べたい情報や知りたいことが明確に定まっているときには「速さ」というのが最も価値が高くて、それが多くの人に支持されているわけですが、せっかくの高度な頭脳と尽きることのない知的欲求をもった「人間さま」に対して、情報を絞り込むだけのアプローチしか提供しない、というのは面白くない。というかもったいない。

なので「みんなの検索」では自分と近しい興味・関心ごとを持った人たちが何をしているのかを、心地よいノイズとして出していこう、と考えた訳です。

自分が調べたいと思ったことと、直接関係はないかもしれないけど、思わず「おっ」と思ってしまうような情報、もしくはその手がかりが、偶然にも目に留まるかもしれません。

脱線 = 探索行動の入り口として、検索そのものを楽しんでもらえたらいいなぁと思ってます。

技術的なはなし

えっと、あまり細かいことは書けません。

ですが、ざっくり言うと、裏側で直近数時間分の検索データを類似ユーザというくくりでインデキシングしておき、検索クエリーが投げられた瞬間にオンザフライでベクトル化して類似検索、みたいな流れです。

「類似ユーザ」ってどうやってくくってるのよ?とか

オンザフライでベクトル化ってどうすればできるのよ?

といった部分は秘密のアッコちゃんです。ナイショ。

大量のベクトルデータのインデキシングと類似検索の部分は、以前このブログで紹介したLuigi(ルイージ)を使ってます。

http://d.hatena.ne.jp/download_takeshi/20101121/1290364695

perlで高速な類似検索エンジンを構築できるようにしてみた

実験的なコードなんでCPANにあげてませんが、実戦で使いつつ、そのうち洗練してきたらアップしようかな。


というわけで、gooでの検索がちょっとだけ面白くなったのではないかと思いますので、ぜひ使ってみてください。

2011-01-04

ブロッキングする処理を外部プロセスに任せる - AnyEvent::Workerを使ってみた

AnyEventを使う場合に、どうしてもブロッキングしてしまうような処理があるとして、それを外部プロセスとして切り出しつつ、メインのイベントループの中に取り込みたいんだよな、と。

そんな時はAnyEvent::Workerがよさそうです。

AnyEvent::Worker - Manage blocking task in external process

http://search.cpan.org/~mons/AnyEvent-Worker/

POEで言うところのPOE::Component::Genericのようなものらしいです。使いこなせるようになるといろいろと便利!

use strict;
use warnings;
use AnyEvent;
use AnyEvent::Worker;

$|++;

print _timestamp(), "開始しまーす\n";

my $cv = AnyEvent->condvar;

print _timestamp(), "AnyEvent::Workerで外部プロセス化", "\n";
my $worker = AnyEvent::Worker->new( ['My::App'] );

print _timestamp(), "ブロッキングする処理を投げる", "\n";
$worker->do(
    blocking_task => 'a happy new year!',
    sub {
        my ( $worker, $return_message ) = @_;
        print _timestamp(), "外部プロセスからかえってきたよ", "\n";
        $cv->send($return_message);
    }
);

print _timestamp(),
    "その間にメインのイベントループでは他の処理ができるんだぜ", "\n";
sleep 2;
print _timestamp(), "メインループでもわざと2秒眠ってみたフリ", "\n";

my $rec = $cv->recv;
print _timestamp(), $rec, "\n";

sub _timestamp {
    my ( $sec, $min, $hour, $day, $month, $year ) = localtime(time);
    sprintf("%02d時%02d分%02d秒\t", $hour, $min, $sec);
}

#----------

package My::App;

sub new {
    my $class = shift;
    my $self = bless {@_}, $class;
    return $self;
}

sub blocking_task {
    my $self    = shift;
    my $message = shift;

    for ( 1 .. 5 ) {
        print "\t", _timestamp(), "外部プロセスでブロッキングしてしまう処理", "\n";
        sleep 1;
    }
    return $message;
}

sub _timestamp {
    my ( $sec, $min, $hour, $day, $month, $year ) = localtime(time);
    sprintf("%02d時%02d分%02d秒\t", $hour, $min, $sec);
}

これを実行するとこうなります。

インデントして書いてある行は外部プロセスで実行した処理です。

imac:Hacks miki$ perl any_event_worker.pl 
07時55分09秒	開始しまーす
07時55分09秒	AnyEvent::Workerで外部プロセス化
07時55分09秒	ブロッキングする処理を投げる
07時55分09秒	その間にメインのイベントループでは他の処理ができるんだぜ
	07時55分09秒	外部プロセスブロッキングしてしまう処理
	07時55分10秒	外部プロセスブロッキングしてしまう処理
07時55分11秒	メインループでもわざと2秒眠ってみたフリ
	07時55分11秒	外部プロセスブロッキングしてしまう処理
	07時55分12秒	外部プロセスブロッキングしてしまう処理
	07時55分13秒	外部プロセスブロッキングしてしまう処理
07時55分14秒	外部プロセスからかえってきたよ
07時55分14秒	a happy new year!

外部プロセスでは1秒スリープを5回まわしてます。

なので「ブロッキングする処理を投げる」から5秒経って「外部プロセスからかえってきたよ」が表示されてますね。

注目すべきはその5秒の間にメインのイベントループの中でも他の処理ができているという部分です。

これがAnyEvent::Workerの良いところですね。ふんづまる処理は外部プロセスに押し出してしまおう、という発想です。

あ、ちなみにメインのイベントループで2秒スリープしているのは演出のため、わざとです。

実際にはブロッキングするような処理をAnyEventの中で書いては意味ありませんので、そこんところヨロシク。

そして最後に「外部プロセスからかえってきたよ」「a happy new year!」ということで、

新年あけましておめでとうございます。今年もよろしくござ候ー。

2010-11-21

perlで高速な類似検索エンジンを構築できるようにしてみた

すみません。タイトルはやや釣り気味です。

類似検索エンジンというか、そのアイデア程度の話なんですが、以前から考えていた類似検索エンジン風のネタがあったので、ちょっとperlで書いてみたので、そいつを晒してみます。

Luigi   https://github.com/miki/Luigi

類似検索なのでLuigi。ルイージとか読みたい人はそう読んじゃっても良いです。(冷)


考え方と仕組み

類似文書の検索、となりますと一般的には超高次元での空間インデックスとかが必要になります。

昔からR-TreeやSR-Treeなど、いろいろと提案されていますが、より高次元になると「次元の呪い」によりパフォーマンスが出なくなる、なんて言われていますね。

そこで最近ではLSHに代表されるような、より高度な「近似」型のインデキシング手法が人気を集めているようです。

で、今回考えたLuigiも実は近似型のインデックスです。ただし文系脳で考えたのですごく簡単&イメージしやすいと思います。

(1)まず検索対象となるデータを用意します。文書ラベルに対してその文書の特徴語がスコア付きで並んでいるようなデータです。

$data = {
    文書label => {
        単語 => score, 単語 => score, 単語 => score, ...
    }, 
    文書label => {
        単語 => score, 単語 => score, 単語 => score, ...
    }, 
    文書label => {
        単語 => score, 単語 => score, 単語 => score, ...
    }, 
}

(2)上記のデータに対して、まず非階層型クラスタリング(K-Meansなど)を実施。

(3)各クラスタの重心点とそのベクトルをピックアップし、もう1度(1)のようなデータ構造を作る

(4)(3)で作った重心点のデータに対して改めてクラスタリングを実施し、(3)に戻る

最終的に処理すべきノードがなくなるまでこれを繰り返します。

すると各ノードが「意味」としてまとめられたバランスのとれた木構造ができあがります。

検索時には検索したいキーワードベクトル化した上で、このツリーのRootノードから投げてやります。

ノードでは自分の子ノードの重心ベクトルクエリベクトルの類似度(もしくは距離)を計算し、類似度が高かった子ノードが選ばれ、されにその子供(孫)ノードへとおりていきます。最後に葉(リーフ)にたどり着いたらオシマイ。

ちょっと調べてみたところopencvマニュアルサイトあたりで「Hierarchical K-Means Tree(階層型KMeansツリー)」なんて言葉も出てくるようなので、やってることは同じなのかもしれません。


実験結果

簡易な実験結果です。某QAサイトのデータを1万件ほど用意してインデックスを作りました。

それに対して「インフルエンザ」「不倫」「確定申告」「トヨタ自動車」と何の脈絡もなく、適当にキーワードを投げてみました。

データが1万件と少ないので、入力した言葉に大してのマッチ具合がちょっとぼんやりしてますが、それでも類似文書検索にはなっています。

なお各結果は左の数値が類似度、右の文字列がQAの文書ラベルです。

下部には[keyword expand elapsed]と[similarity search elapsed]という項目がありますが、これは経過秒数です。

keyword expand は入力されたキーワードをYahooAPIを叩いてオンザフライで特徴ベクトルに変換する処理です。なのでどうしても低速です。

similarity search の部分が実際にLuigiがインデックスツリーをたどって検索した処理の秒数となっています。

Input keyword: インフルエンザ

0.581558925433416 インフルエンザ感染経路について - 生物学 -

0.506834581525096 触れた物でインフルエンザ感染する可能性について - 病気 -

0.416235552701384 インフルエンザ 完治。 - ヘルスケア(健康管理) -

0.257363443533322 インフルエンザによる鶏の殺処分 - 自然環境問題 -

0.183202534089901 新型インフルエンザ感染者人数について - 病気 -

0.107096136233281 感染したのでしょうか。 - ウィルス対策 -

0.107073400034487 どんな症状でウイルスに汚染されたと判断できるのですか? - ウィルス対策 -

0.10196785878913 自覚症状なしで感染はある? - ウィルス対策 -

0.100320950732344 ウイルス感染予防 - ウィルス対策 -

----------------------------------------------------------------------------------------------------

[keyword expand elapsed ] 1.24062

[similarity search elapsed] 0.007747

----------------------------------------------------------------------------------------------------



Input keyword: 不倫

0.928112763412724 不倫のはじまり? - 恋愛相談 -

0.74892012063956 不倫をする女性を理解できるのか? - 夫婦・家族 -

0.723756525050272 都合のよい女? - 恋愛相談 -

0.640222414512117 不倫 慰謝料 - 夫婦・家族 -

0.581905311603478 既婚者の人と付き合ってます・・・ - 恋愛相談 -

0.519328972624065 はじめての携帯チェック(男性の方回答お願いします) - 恋愛相談 -

0.469573317060705 夫が悪い?妻が悪い? (不倫の事・・長文です) - 恋愛相談 -

0.437586348780523 既婚者ですが恋をしてしまいました・・・ - 恋愛相談 -

0.406506723588201 この男性の心理は? - 恋愛相談 -

0.40090569692471 感受性がない(人の心がわからない)人は病気なのか、性格なのでしょうか?... - 夫婦・家族 -

0.397803793924256 妻子もちの彼に私への愛情はあるの・・・? - 恋愛相談 -

0.36090868212552 図々しい職場の女性にギャフンと言わせたい。(長文です) - 恋愛相談 -

0.357805881567324 お金のためと言え、妻が他人とハメ撮り - 夫婦・家族 -

0.330370489228686 不倫の恋愛について - 恋愛相談 -

0.295080022135181 妻又は夫の不倫 - その他(ライフ) -

0.268932663691503 別れた不倫相手が妊娠した。 - 恋愛相談 -

0.260702721742602 子供の為に離婚しないという選択 - 恋愛相談 -

0.248174912998768 奥さんの思い込み・・・ - 法律 -

0.215141243969756 自分の浮気OKの女性へ質問 - 恋愛相談 -

0.205917241884543 離婚するための準備 - 夫婦・家族 -

0.202873460208085 潮時?? - 恋愛相談 -

0.143639484514496 10年前の彼氏がまた好きになってしまいました - 夫婦・家族 -

0.136331768702082 帰化 - 法律 -

0.123197055943046 離婚後も 同居したい 親や子供の学校にばれない様にする方法 - 夫婦・家族 -

0.117817802306074 遊び(浮気)相手に買いますか? - 恋愛相談 -

----------------------------------------------------------------------------------------------------

[keyword expand elapsed ] 0.676104

[similarity search elapsed] 0.011468

----------------------------------------------------------------------------------------------------

Input keyword: 確定申告

0.448847725667931 アフィリエイト報酬の確定申告 - 税金 -

0.331799631447844 税務署の届出について - 起業 -

0.301505276386864 扶養家族について - 税金 -

0.251311917852604 国民健康保険確定申告 - 健康保険 -

0.231278394261396 途中から加入した扶養控除は・・・? - 税金 -

0.21445531184007 消費税申告が1日遅れたら5%も加算されました - 税金 -

0.209033457089336 年金生活者の株取引での利益 - 税金 -

0.208093399571145 低い年収でも青色申告にするメリットってありますか? - 税金 -

0.201014863628649 年金と控除 - 年金 -

0.118114070134288 所得が38万円以下の場合、配偶者特別控除申告書に記載する必要は? - 税金 -

----------------------------------------------------------------------------------------------------

[keyword expand elapsed ] 0.509284

[similarity search elapsed] 0.006793

----------------------------------------------------------------------------------------------------


Input keyword: トヨタ自動車

0.33857076472299 初購入 - 国産車 -

0.290008657323579 トヨタイプサムに乗っている方と車高を落としている方へ  - 国産車 -

0.255260034426658 トヨタパッソを購入したいと思ってます - 国産車 -

0.180490218245698 トヨタでスライドドアのあるお勧めファミリーカーを教えて下さい。 - 国産車 -

0.173544528124501 トヨタの増産で・・・ - ニュース・時事問題 -

0.158633301729542 ミニバンランニングコスト - 国産車 -

0.123424426531673 車に詳しい方にお聞きします。 - 国産車 -

0.11085629266251 車の車種に詳しくなりたい! - その他(車) -

0.100809731019605 同車種でディーゼルからガソリン乗り換え。有利な売却は? - 国産車 -

----------------------------------------------------------------------------------------------------

[keyword expand elapsed ] 0.843112

[similarity search elapsed] 0.006991

----------------------------------------------------------------------------------------------------

実際に動かしてみるとLuigiによる類似文書検索部では0.006秒前後で答えを返しているのがわかります。

このサンプルでは1万件のデータを対象にしましたが、50万件程度に増やしてみても0.01〜0.04秒程度でした。


課題

課題はたくさんあります。

まずはLuigiという名前がダサイです。Tree::Hierarchical::KMeans だと長過ぎるので適当につけましたが、ベタベタ過ぎてなんだかちょっとハズカシイ。。。

あと実験コードなので、1つもテスト書いてないし、スクリプトの構成も書きなぐり風です。実験的なモノなので完成度はかなり低めです。

インデックスの更新もできません。今のところ更新するには作り直ししかないです。


いいところ

えっと、メモリに全部のせてるので速いです。perlで0.006秒とかってかなり速いと思います。C++で書き直したらさらにすごいかも。

あと精度がそこそこいい。

ベースとなるクラスタリングツール(Bayonを使わせてもらってます)が優秀だから、というのもありますが、実は独自に工夫しているポイントもあります。

今回のような「クラスタリング結果の積み上げ方式ツリー」に対して、単純にノードをただ辿るだけの検索を行うと、類似度の測定にあやまりが多くなります。

これは各ノードでの検索対象が「重心点」であり、各クラスタの分散具合などは考慮されていないので、結構な確率で誤ったノードへと導かれてしまいます。

しかもRootに近いところで間違うと全然違うクラスタへと導かれてしまうという致命的な罠が待っています。

そこでLuigiでは最も類似しているノード数個を並列してたどるような仕組みをとっています。

その中で生き残ったノードの子ノードたちに対しても、1つではなく複数の候補を持って辿るような考え方です。

試してみたところ、1つだけを対象にすると7〜8割前後の精度しか出ませんが、同時に2〜5個くらいを辿るようにするだけで、誤判断はほぼなくなるようです。



というわけで、興味のある人はgithubから落として使ってみてください。