📑

キーフレーズ抽出の諸アルゴリズム

2023/08/24に公開

自然言語処理

NLP

idea

はじめに

日本語のテキストから「どんな単語がよく出ているのか」を分析するため、現在キーフレーズの抽出方法について学習中。本記事で学習内容を整理したい。

キーフレーズ抽出とは

簡単に説明すると、文章を解析し、その文章の特徴を表す重要なフレーズを抽出する技術のこと。なぜキーワードではなくキーフレーズなのかを説明すると、文章中に「大統領選挙」のような言葉がある場合に、「大統領」と「選挙」という別々の単語としてでなく、1つの名詞句として抽出したいからである。
キーフレーズ抽出の手法には、統計ベース、グラフベース、機械学習ベースの3つがある。ここではグラフベースの手法について整理する。グラフベースの手法は、文章をグラフ構造で表現し各ノード(=文や単語)の関係性を元に要約を作成する手法である。

アルゴリズム

PageRank

グラフベースのキーフレーズの抽出手法の根幹をなすアルゴリズム。
GoogleがWebページの重要度を測る指標として用いられたもので、0~10の値を取る。PageRankの値が大きいほど検索エンジンからの評価が高いことを意味する。
PageRankの値は「被リンクの数と質」で計測される。つまり、

沢山のページからリンクされているページは価値が高い
価値が高いページからリンクされているページは価値が高い

ということである。
以下のような遷移図の場合、

PageRankの計算式は以下となる。

PR(A) : ページ A の PageRank。
C(Ti) : ページ Ti から出ていくリンク数。
Ti : ページ A にリンクを張っているページ。総数 n
d : ダンピングファクタ。0 ≦ d ≦ 1 の値を取る

∑の中身を見ると、

TextRank

PageRankを文章に応用したもの。
PageRank、TextRankそれぞれのグラフ構造は以下である。

アルゴリズム	ノード	エッジ
PageRank	ページ	リンク
TextRank	単語	関連度、類似度

単語の部分は、グラフを肥大化させないよう品詞を選択する。一般的には「名詞＋形容詞」で絞り込むことが多い。
TextRankではPageRankと異なり無向グラフとなる。これは、単語の関連度や類似度に方向性は無いからである。

SingleRank

TextRankの拡張。
下の式で、PageRankで出力リンク数 C(Ti)で割っていた部分が重み M~j,iに置き換わった以外は大体同じであるところが見て取れる。
TextRankと異なるのは、エッジを共起回数で重みづけしていること、フレーズ候補のスコアが単語のスコアの合計値であること。

WordScore(vi) : 単語 vi のスコア。
|V| : キーフレーズを抽出する文書の語彙数。
M~ : |V| x |V| の重み行列。M~i,jの値は単語iと単語jの共起回数を M~ の各行を合計1になるよう正規化したもの。
μ : ダンピングファクタ。0 ≦ μ ≦ 1 の値を取る。

単語のスコアを計算後、グラフに追加した単語（名詞＋形容詞等）の連続をフレーズ候補とし、フレーズ内単語のスコアを合計したスコアをそのフレーズ候補のスコアとする。そして高スコアのフレーズ候補をキーフレーズとして抽出する。

PositionRank

SingleRankの拡張で、学術論文からキーフレーズを抽出することを目的とする方法。
学術論文において、文章の先頭に出現する単語の方がキーフレーズになりやすいという情報をもとに抽出している。
無向グラフ形成の手順やフレーズ候補のスコア算出はSingleRankと同じで、以下のようにスコアを計算する。

S : 単語スコアの列ベクトル。次元数は文書中の単語を品詞で絞り込んだ後の語彙数 |V|。
M~ : |V| x |V| の重み行列。SingleRank の M~と同じ。
p~ : エッジを無視してテレポートする際の飛び先の重みを保持した列ベクトル。次元数は |V|。
α : ダンピングファクタ。0 ≦ α ≦ 1 の値を取る。

SingleRankと異なるのはp~の部分。これはテレポート先の遷移確率で、PositionRankではこの遷移確率がノードによって異なる。つまり最初に述べたように、文章の先頭に近い位置で出現する単語の方が遷移確率が高くなり、スコアも大きくなる。

TopicRank

トピックをノードにする手法。
トピックとはなんぞや？を簡単に説明すると、抽出したフレーズ候補を似た者同士でクラスタリングし、そのフレーズ候補集団一つ一つをトピックとする。
クラスタリングのアルゴリズムとしてはHAC（Hierarchical Agglomerative Clusterring）を用いいて階層的に大きなクラスタにしていく。細かいクラスタリング方法の説明は省略する。

トピックの準備ができたら、ノードをトピック、エッジの重みをトピック間の意味的関係性として完全無向グラフを形成する。
トピックの意味的関係性とはなんぞや？を説明すると、「二つのトピックに属する全フレーズ候補の全出現位置のレシプロカル距離（出現位置の差分の絶対値の逆数）の総和」である。
式は以下。

ti, tj : トピック
ci, cj : トピック中のフレーズ候補
pos(ci) : フレーズ候補 ci の全出現位置

わかりやすく言うと、「トピックが二つあり、各トピックに属するフレーズ候補が近い位置で出現する場合、その二つのトピックの関係性は強い（＝重みが大きくなる）」という理解で良い。
グラフを形成したら、あとはこれまで同様PageRankでトピックの重要度を評価する。そして、重要度の高いトピックから代表フレーズを抽出する。洗濯方法は以下の3つがあるが、最良は1つ目であったよう。

文章の先頭に最も近いフレーズ候補
出現回数が最も多いフレーズ候補
トピックを構成するクラスタの重心となるフレーズ候補

TopicRankを用いるメリットとしては、意味合いが重複するキーフレーズが候補としてあがるのを回避できることである。単語をノードとする手法では「乳児用液体ミルク」と「液体ミルク」のような同じ意味合いのフレーズが複数抽出されてしまうが、TopicRankではこの課題を解決できる。

MultipartiteRank

TopicRank を改良したもの。
TopicRankでは、同じトピックに属するフレーズ候補は同じ重要度であるため、代表フレーズをヒューリスティック（経験則や先入観による判断）に抽出されていた。
MultipartiteRankではこの課題を解決する。
フレーズ候補の形成とトピック分類するところまではTopicRankと同じで、グラフの形成方法が異なる。TpicRankではトピックをノードとして完全無向グラフを形成したが、MultipartiteRankではフレーズ候補をノードとした完全有向グラフを形成する。その後、同一トピック内のノード間接続を切る。エッジの重みはTopicRankのdist(ci, cj)を用いる。

また MultipartieRankは各トピック毎で最初に出現したフレーズ候補を以下の要領で優遇する。
各トピック毎に文書中で最初に出現したフレーズ候補cj（③）への全ての入力エッジの重みをcjと同一トピックの他のフレーズ候補ck（④、⑤）とcjへの入力元フレーズ候補ci（①）間の重みの総和およびciの最初の出現位置に基づいて加算する。

cj : 各トピックの最初に出現したフレーズ候補
τ(cj) : cj と同一トピックに属するフレーズ候補集合
ci : cj から入力を受けるフレーズ候補（※全フレーズ候補集合から τ(cj) を除いた数存在する）
pi : フレーズ候補 ci の最初の出現位置
𝛼 : ハイパーパラメータ

つまり、各トピックの文書中で最初に出現したフレーズ候補は、自身が属するトピックとの関連性が強く文書先頭に近い位置に出現する他のトピックのフレーズ候補から、より多くの優遇を受けることになる。

ここまでくれば、あとはPageRankの計算と同様。

おわりに

以下の参考記事をベースに整理した。

参考記事:
はじめての自然言語処理 pke によるキーフレーズ抽出
 Keyphrase Extractionまとめ - Graph base 編-