検索エンジンのMore-Like-Thisクエリとグラフアルゴリズムによる類似記事集約

本記事は Grouping Similar Articles with Search Engine More-Like-This Queries and Graph Algorithms の翻訳記事です。以前の記事である More Like This Query を活用した類似記事集約 入門 から、より踏み込んだ内容になっています。

はじめに

ストックマークでは、毎日数千のメディアから数万件のニュース記事を収集しています。そのときに、異なるメディアから類似した内容の記事がクロールされることもあります。その一方で、これらの内容の重複した記事をそのままユーザに表示してしまうと、ユーザの情報収集体験を損ねてしまう可能性があります。そのため、ストックマークのプロダクトであるAnewsので記事推薦や、Astrategyでの事業活動比較などのニュース分析サービスにおいて、より良いユーザー体験を提供するためには、類似記事を検出して集約するのが重要です。

全く同じ内容の記事を集約するのは比較的簡単です。難しいのは、同じ内容の記事ですが、表現のやや異なる記事も集約する必要がある点です。類似記事の多くは、同じ文章を複製しているのではなく、同じ記事を別の著者が書いたという形になっています。

ストックマークでは、文書の類似性を見つけるために検索エンジンを利用しています。また、類似した記事をグループ化するためにグラフアルゴリズムを利用しています。以降で、詳細は説明していきましょう。

類似性グラフの構築

記事を集約する前に、類似性グラフを最初に構築します。グラフの各ノードは記事を表しており、2つのノードが類似していると判断された場合、2つのノード間にエッジが存在しています。類似性定義のためのメトリックによって、グラフは有向もしくは無向になります。今回の場合は有向グラフになります。

記事が固定次元のベクトルで表現できれば、doc2vec や S-BERT を利用して、ベクトル距離を計算して記事の類似性を計算できます。今回のプロジェクトでは、これとは異なる方法を利用しています。すなわち、記事の類似性取得に全文検索エンジンを利用しています。実際に、全文検索エンジンを利用したアプローチの方が、高精度で柔軟な検索が可能であることがわかりました。

ストックマークでは、ニュース記事のインデクシングに Elasticsearch を活用しています。Elasticsearch は、Apache Lucene の上に構築された全文検索エンジンです。Luceneでの類似性スコアリングはこちらに詳細があります。

インデックスされた各記事に対して、More Like This (以降、MLT) クエリを実行し、その類似記事を取得します。類似度判定には閾値を設定します。Luceneでの類似度スコアは記事の長さによって異なるため、絶対値で閾値を設定するのではなく、0から1の間の相対値でスコアを計算します。MLTクエリの実行で、最初のマッチした記事は、同一記事であるため、スコアは1になります。残りの記事は類似度に応じて相対値でスコアリングされます。

類似度の計算には、記事文書の title と body フィールドを利用しています。検索結果からノイズを減らすために、次のフィルタリングを加えています。

• 同じメディアからのニュースは無視する
• 5日以上間隔をあけて発表されたニュースは無視する（あるニュースの記事が5日後に再生されることはレアであるため）

類似記事が取得できたら、類似度グラフの構築が可能になります。もし記事 B が記事 A の類似結果リストにあれば、 A から B へのエッジを書きます。なお、MLTのスコアリングは対称ではないため、 B が A に似ているからといって、 A が B に似ているとは限らない点に注意してください。

グラフの構成要素の抽出

次に、上で作成した類似グラフ上で類似記事を見つけます。そのために、次のステップとして、2つの異なるアルゴリズムを利用しています。グラフの強連結成分およびコミュニティをそれぞれ検出し、それらの成分が交差した部分を類似記事と判定します。

有向グラフは、各頂点のペアの間に少なくとも1本の経路が存在する場合、”強連結している” と言われます。グラフの強連結成分は、そのグラフの極大かつ強連結な部分グラフです。今回のサンプルデータセットでは、図1に示すように、類似性グラフの強連結成分を色分けして確認できます。非常に大きな成分が数個、小さな成分が多数存在します。最も大きな成分は、記事の4%以上を占めます。これは、主に同じフォーマットで書かれた市場レポートの記事が含まれているためです。

図2では、強連結成分と、それと交差する3つのコミュニティを表示しています。グラフのコミュニティ検出アルゴリズムは、グラフ内の密に結合された頂点をグループ化します。これは、ストックマークの場合には、強連結成分からノイズとなる記事を取り除くのに有効です。コミュニティ検出には、SCDアルゴリズムを使用しています。SCDアルゴリズムは貪欲なアルゴリズムであり、最初に密に結合しているノードをクラスタリングします。その後、最初のクラスタの精度を高めていきます。詳しくは論文と実装を参照ください。

理論的には、強連結成分の検出を行わずに、コミュニティ検出のみの適用も可能です。コミュニティ検出は非常に強力ですが、SCDアルゴリズムが有向グラフを無向として扱うため、コミュニティ検出アルゴリズムのみを用いた場合、類似記事の誤検出が増えることを確認しています。強結合成分とコミュニティの検出の両アルゴリズムを併用することで、どちらか一方のみを用いるよりも良好な結果が得られる点が確認できています。

バッチ計算

ストックマークでは、毎日動作させているクローリングのバッチ処理があります。このバッチ処理の都度に、すべての記事の類似度グラフを再構築するのは、計算量的に不可能です。そこで、インクリメンタルなアプローチを採用します。つまり、新たに追加された記事ノードから到達可能な既存ノードの記事のみを更新するのです。また、5日以上前に追加された記事は、更新時に無視しています。

まとめ

本記事では、全文検索エンジンを活用して類似しているニュース記事を検出する方法について説明しました。図3は、Astrategy の検索画面の例です。あるニュース記事と、類似と検出された他の記事の一覧を表示しています。

また、ストックマークのデータベースでは、40%の記事で類似記事を検出しています。類似記事グループの平均の大きさは 3 でした。

本記事は、ストックマークの研究開発チームとエンジニアリングチームの協同の成果です。原文執筆者は、R&Dチームのメンバーとして主にアルゴリズムの部分を説明しました。（実際には、Elasticsearchサーバのセットアップや、クエリのスケーリングなどの作業もありましたが、本記事では割愛しています。）