名寄せ（EntityResolution）のサブタスクとして，大量の表記集合のうち確実に同一エンティティを指さない表記ペアを比較対象から除外するEntityBlockingが広く研究されている[1]．本研究はQ-gramsBlockingに着目し，Zipf則[2]と分布仮説[3]を考慮したシンプルなアルゴリズムを構築することで，高速かつ高精度な名寄せが実現できることを確認した．また，同アルゴリズムを文書集合に対して適用することで，高速かつ高精度なテキストクラスタリングが実現できることを確認した．

名寄せ（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）のみを変更することでクラスタの粒度を調整できる．