RengaBlock:Q-gramsBlockingを用いた高速名寄せ・高速テキストクラスタリングの実装

名寄せ（EntityResolution）は現実世界の同一エンティティを指し示す複数の表記同士をまとめ上げるタスクであり，データベース内のエントリの重複や表記ゆれの吸収に利用される．しかし，対象表記が푁件存在し，網羅的に全表記ペアを比較した場合，比較回数はO(푁2)となり，大規模データにスケールしない．その解決策として，比較する表記ペア数を削減するBlocking手法が様々に提案されている[1]．その一つにQ-gramsBlockingが存在する．Q-gramとは文字N-gramのことを指し，例えば「LINEヤフー」に含まれる푞=2のQ-gramは[‘LI’,‘IN’,‘NE’,‘Eヤ’,‘ヤフ’,‘フー’]となる．Q-gramsBlockingは同一Q-gramを一つ以上共有する表記ペアのみを比較対象とすることで，比較回数を削減する．しかし，あるQ-gram푘の出現数が푛푘だとすると，푘を共有する表記ペアの数はO(푛2푘)となる．Q-gramの出現数はべき乗則に従う[2]ため，高頻度Q-gramを考慮した場合の比較回数は依然として多いままである．一方で，考慮の対象とするQ-gramが高頻度であるほど，そのQ-gramの一致が判明したことによって得られる情報量は減少し，表記ペア同士が同一エンティティを指し示す確率は減少すると考えられる．そこで本研究では，低頻度Q-gramのみを考慮の対象としてQ-gramsBlockingを行う，ボトムアップ型の階層的クラスタリングアルゴリズムを提案する．提案手法は，クラスタ結合時に素性平均ベクトル同士を比較することで分布仮説[3]を自然に考慮する．提案アルゴリズムを適用しうる別のタスクとして，テキストクラスタリング，あるいはトピックモデリングが存在する．これらは文書集合内で同じトピックについて書かれた文書同士をまとめ上げるタスクであり，ユーザ生成コンテンツの分類や自動タグ付与に利用される．特にトピックモデリングはクラスタリング結果に加えて，各クラスタの中心となるトピックを抽出し出力する．我々の提案アルゴリズムはQ-gramを素性とし，エンティティ同士をまとめ上げるが，同アルゴリズムにおいて，文中の形態素等を素性とすれば，文同士を効率的にまとめ上げることができる．本研究におけるテキストクラスタリングでは，名詞・名詞句のみを素性とする1）．提案手法の極めて実用的な特徴として，以下の三つが挙げられる．(1)教師ラベルや事前学習済みモデルを必要とせず，ドメインに依存しない．(2)実行のたびに出力が変わらない決定的なアルゴリズムである．(3)必要となる二つのパラメータのうち一つ（coveragethreshold）をタスクごとに固定することで，ユーザは一つのパラメータ（similaritythreshold）のみを変更することでクラスタの粒度を調整できる．