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

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

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

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

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

考え方と仕組み

類似文書の検索、となりますと一般的には超高次元での空間インデックスとかが必要になります。
昔からR-TreeやSR-Treeなど、いろいろと提案されていますが、より高次元になると「次元の呪い」によりパフォーマンスが出なくなる、なんて言われていますね。
そこで最近ではLSHに代表されるような、より高度な「近似」型のインデキシング手法が人気を集めているようです。

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

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

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

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

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

（４）（３）で作った重心点のデータに対して改めてクラスタリングを実施し、（３）に戻る

最終的に処理すべきノードがなくなるまでこれを繰り返します。
すると各ノードが「意味」としてまとめられたバランスのとれた木構造ができあがります。

検索時には検索したいキーワードをベクトル化した上で、このツリーのRootノードから投げてやります。
各ノードでは自分の子ノードの重心ベクトルとクエリーベクトルの類似度（もしくは距離）を計算し、類似度が高かった子ノードが選ばれ、されにその子供（孫）ノードへとおりていきます。最後に葉（リーフ）にたどり着いたらオシマイ。

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

実験結果

簡易な実験結果です。某QAサイトのデータを１万件ほど用意してインデックスを作りました。
それに対して「インフルエンザ」「不倫」「確定申告」「トヨタ自動車」と何の脈絡もなく、適当にキーワードを投げてみました。

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

なお各結果は左の数値が類似度、右の文字列が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 消費税申告が１日遅れたら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秒前後で答えを返しているのがわかります。

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

課題

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

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

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

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

いいところ

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

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

今回のような「クラスタリング結果の積み上げ方式ツリー」に対して、単純にノードをただ辿るだけの検索を行うと、類似度の測定にあやまりが多くなります。
これは各ノードでの検索対象が「重心点」であり、各クラスタの分散具合などは考慮されていないので、結構な確率で誤ったノードへと導かれてしまいます。
しかもRootに近いところで間違うと全然違うクラスタへと導かれてしまうという致命的な罠が待っています。

そこでLuigiでは最も類似しているノード数個を並列してたどるような仕組みをとっています。
その中で生き残ったノードの子ノードたちに対しても、１つではなく複数の候補を持って辿るような考え方です。

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

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