この記事は Nikkei Advent Calendar 2022 の 24 日目の記事です。

はじめに

メリークリスマス 🎅

デジタル事業情報サービスユニットで検索エンジニアをしている日當（@hinatades）と申します。

本記事では、報道記事の時事性を加味したクラスタリング手法を、検索サービスへ導入することを目的として開発したのでご紹介します。

弊社ではこの開発テーマを長らく実現に向けて取り組んできましたが、今月やっと日経リスク&コンプライアンスにて初めてサービスインできました。

これまでの課題感

私の所属している情報サービスユニットでは、200 社以上の企業様とコンテンツを提携しており、それらを各サービスからお客様に提供しています。

例えば日経リスク&コンプライアンス(以下日経 RC)では、50 社以上の報道記事を検索することで取引先のリスクやコンプライアンスのチェックが可能です。

ところで、通常あるニュースは各社がそれぞれ同じ報道をするので、ユーザーがこの報道について日経 RC 上で検索をすると、以下のように同じ内容の記事が報道会社ごとに数多くヒットして並んでしまいます。

各社ごとの報道に興味があるユーザーに対してはこの見せ方で問題ないのですが、報道会社に関係なく事実確認にだけ興味があるユーザーに対しては、この見せ方は冗長です。

そこで、以下のようにサービス上で類似記事をまとめ込んで表示できると、ユーザーは記事を一つ一つ確認する必要が無くなり、より効率的な確認が可能になります。

類似記事の定義としては、記事の内容が似ていることはもちろん、時事性の高い報道記事なので記事の公開日も類似判定に使えるとより精度が上がります。

どう作ったのか

改めて要件を整理すると

• サービス上で記事内容が類似していて、かつ公開日が近い記事をクラスタリングしたい

です。

弊社の各サービスは共通の検索基盤の API を作って記事を取り出しています。そこでこの API 上に、記事の分散表現と公開日を使って記事をクラスタリングして返却する機能を作ることにしました。

以下が処理の全体像です。

クラスタリングにはグラフベースのアルゴリズムを日経イノベーション・ラボの安井さんに考案してもらいました。

全体の流れは大きく

1. 記事の分散表現を検索エンジンに格納
2. 検索エンジンから取得した記事で k 近傍グラフ構築
3. グラフから公開日が n 以上のエッジを削除
4. ラベルプロパゲーションでグラフからコミュニティ検出

です。各処理についてそれぞれ解説します。

1.記事の分散表現を検索エンジンに格納

弊社の記事データは、記者や自動タグ付け処理によりキーフレーズがメタ情報として付与されています。 今回はこのキーフレーズを記事の分散表現を作るために用いました。

それぞれのキーフレーズを spaCy のja_core_news_lgモデルを使って 300 次元のベクトルに変換後、SWEM (Simple Word-Embedding-based Methods)で一つのベクトルにします。

分散表現の計算は重いので、この処理を API 化し、記事を検索エンジンに格納する前に呼び出して事前にメタ情報として付与しました。

弊社では検索エンジンとして Elasticsearch を広く活用しています。 Elasticsearch にはDense vector field typeというベクトル用のフィールド型があるので利用しました。

PUT my-index
{
  "mappings": {
    "properties": {
      "my_vector": {
         "type": "dense_vector",
         "dims": 300
      }
    }
  }
}

2. 検索エンジンから取得した記事で k 近傍グラフ構築

Elasticsearch から取得した記事に対して k 近傍グラフを構築します。

k 近傍グラフは各ノードから距離の近い k 個のノードに対してエッジを生やすことで構築できます。

グラフ構築にはscikit-learnとNetworkXを使いました。

import networkx as nx
from sklearn.neighbors import kneighbors_graph

csr = kneighbors_graph(vectors, n_neighbors=K) # vectorsは分散表現(リスト)のリスト
G = nx.from_scipy_sparse_matrix(csr)
G = nx.relabel_nodes(G, ids)  # 各ノードに記事IDを付与

3. 公開日が n 以上のエッジを削除

Elasticsearch からは記事の公開日も一緒に取得し、先程構築したグラフから公開日が n 以上離れたノード間のエッジを取り除きます。

pruned_edges = [
    (vi, vj)
    for vi, vj in G.edges()
    if abs((articles[vi]["publish_datetime"] - articles[vj]["publish_datetime"]).days) >= N
]
G.remove_edges_from(pruned_edges)

4. ラベルプロパゲーションでグラフからコミュニティ検出

得られたグラフに対してコミュニティを定義し、各コミュニティを 1 クラスタとします。 コミュニティ検出にはラベルプロパゲーション¹を使いました。

ラベルプロパゲーションはグラフ内のコミュニティを決定するためのアルゴリズムです。 このアルゴリズムは、隣接しているノード同士は同じコミュニティに属する、という直感に基づく仮定がベースになっていて、グラフに対してイテレーションを回すことで結果が収束し、コミュニティ(ラベル)が決定されます。 各イテレーションでは、各ノードのラベルを、隣接するラベルの中で最も多いラベルで上書きする処理を行います。 このアルゴリズムは、事前ラベルを持たないグラフでも動作するし、一部のノードに正解ラベルをつけておくとそれを考慮することもできます。

今回構築したグラフは事前ラベルが無いグラフであり、NetworkX の label_propagation_communities を使ってコミュニティ検出を行いました。

from networkx.algorithms.community import label_propagation_communities

community = {i: nodes for i, nodes in enumerate(label_propagation_communities(G))}
nx.set_node_attributes(G, community, name="community")

2, 3 ,4 でグラフは以下のようなイメージで遷移します。

性能について

上記のクラスタリングのパフォーマンスを記事数ごとに計測しました。 1000 件の記事を 140[ms]ほどでクラスタリングできます。

¹ のタイトルにもあるように Near linear time なアルゴリズムであることがわかります。

まとめ

記事を分散表現と公開日を使ってクラスタリングする手法をご紹介しました。 今回紹介した方法は、公開日に限らず分散表現に加えて何らかのメタ情報を持ったデータであれば応用が可能です。 特に何かしらの検索機能があるサービスでは、検索結果をまとめ込んで表示したいというニーズは少なからずあると思うので、参考にしていただけたら嬉しいです。

日経 RC は法人向けサービスなので、気軽に触っていただける環境を提供できない事が心苦しいですが、今後この仕組みを日経 COMPASSなどの個人向けサービスでも展開予定です。

乞うご期待ください！