pei’s blog

情報系の大学を出たSE1年生。主にプログラミング(機械学習寄り)の話題を書いていきます。

Pythonでドキュメントの重み付け(Okapi BM25)

今回はOkapi BM25での文書の重み付けを実装します。

目次



Okapi BM25とは

 TF-IDFに似た文書の重み付けの方法です。wikipedia(英語)
    以下の式で表されます。

 score(D, Q) = \sum_{q_i\in Q}^i IDF(q_i) \left( \frac{TF(q_i, D) \cdot (k_1 + 1)}{TF(q_i, D)+k_q \cdot (1 - b + b \cdot \frac{|D|}{avgdl})} + \delta \right)

    Dはドキュメント、Qは検索したい単語の集合、 q_iはQ中の単語、|D|はドキュメント長、avgdlは全ドキュメントの平均単語数です。

    TFはD中の q_iの出現数、IDFはInverse Document Frequencyの略で、多くのドキュメントに出現している単語は値が小さくなるような関数です。IDF( q_i) は \log{\frac{D}{d_w}}で表されます。ここでのDはドキュメントの総数、 d_wはwがいくつのドキュメントに出現したかを表します。

    また、b, k1,  \deltaは定数で、b=0.75, k1=1.2〜2.0,  \delta=1.0が最良みたいです。 \deltaがあるものはBM25+で、ないものはBM25と呼ぶようです。+のほうは改良版だそうです。ちなみに私が試した中で最良の結果だったのはb=0.75, k1=1.6,  \delta=1.0でした。

    TF-IDFと違うところはD/avgdlの箇所から分かるように、ドキュメントが短い時は重みが大きくなり、長ければちいさくなるということです。つまり、長いドキュメントに出現する単語より、短いドキュメントに出現する単語を重要視する感じです。







実装

計算の流れはこんな感じです。カッコ内は実際にその処理をするメソッド名です。
  1. IDFの計算(fit)
  2. TFの計算(transform)
  3. 重み付け(transform)
 文書をベクトル化したものは大抵疎なベクトルなので、値のあるインデックスと値のみを保管しないとパフォーマンスが非常に悪くなります。最後にscipy.sparse.lil_matrixで疎行列に変換します。 fitやtransformなどsklearnのVectorizerライクな関数名にしました。fitでベクトル化するオブジェクトのセットアップ、つまりIDFの計算、transformで実際に変換します。実際はクラスを実装したのですが、長くなるので一部だけ載せてます。全てのコードはこちら

import numpy as np
from scipy import sparse as sp
import math

def fit(self, documents, extract_words_func):
  """IDFの設定
  documentsはドキュメントのリスト、 
  extract_words_funcはドキュメントを単語リスト分割する関数"""
  self.average_words_len = 0  # 1つのドキュメントの平均の単語数を記録
  for document in documents:
    searched_dict = {}
    word_ls = extract_words_func(document)  # ドキュメントを単語リストに分割
    self.average_words_len += len(word_ls)
    for word in word_ls:
      # このドキュメント内で始めて出た単語
      if not searched_dict.get(word):
        searched_dict[word] = True
        # 他のドキュメントですでに出た単語
        if self.word_index_dict.get(word):
          self.idf[self.word_index_dict[word]] += 1.0
        # 初めて出現する単語
        else:
          self.feature_names.append(word)
          self.word_index_dict[word] = self.counter
          self.counter += 1  # 単語数を記録
          self.idf = np.append(self.idf, [1.0])

  documents_len = len(documents)
  self.idf = np.log2(documents_len / self.idf)
  self.average_words_len = self.average_words_len / documents_len


def transform(self, documents, extract_words_func, K1, B, delta):
  """ドキュメントをConvine Weigthで重み付け
  documentsはドキュメントのリスト
  extract_words_funcはドキュメントを単語リスト分割する関数
  K1, B, deltaは定数
  返すのはscipy.sparse.lil_matrixオブジェクト
  """
  len_ls = []  # 1つのドキュメントに出現した単語数
  word_index_ls, word_weight_ls = [], []  # 単語のインデックス, 単語の出現数
  for doc in documents:
    word_weight_dict = {}  # 値のあるインデックス: 値
    word_ls = extract_words_func(doc)
    # Term Frequency
    for word in word_ls:
      if self.word_index_dict.get(word):
        if word_weight_dict.get(self.word_index_dict[word]):
          word_weight_dict[self.word_index_dict[word]] += 1.0
        else:
          word_weight_dict[self.word_index_dict[word]] = 1.0

    # 重み付け
    dist, word_len = 0, len(word_ls)
    for ind in word_weight_dict.keys():
      word_weight_dict[ind] = self.idf[ind] * \
        (delta + (word_weight_dict[ind] * (K1+1.0)) /\
        (word_weight_dict[ind] + K1 * (1.0 - B + B*(word_len / self.average_words_len))))
      dist += word_weight_dict[ind] ** 2
    # 正規化
    dist = math.sqrt(dist)
    for ind in word_weight_dict.keys():
      word_weight_dict[ind] /= dist

    len_ls.append(len(word_weight_dict))
    word_index_ls.extend(word_weight_dict.keys())
    word_weight_ls.extend(word_weight_dict.values())

  # sp.lil_matrixで疎行列オブジェクト生成
  it = 0
  result = sp.lil_matrix((len(documents), self.counter))
  for i in range(len(len_ls)):
    for _ in range(len_ls[i]):
      result[i, word_index_ls[it]] = word_weight_ls[it]
      it += 1
  return result



導入してみた

    重み付けをOkapi BM25+にして全結合ニューラルネットワークを学習させて2値分類器を作成したところ、TFIDFより性能がよかったです(98%->98.5%くらいに向上)。やはり文書の長さによって単語の重要度は変化するようです。