チケットの見える化にチャレンジしてみる(2-7: 準備編 BM25の実装)
こんにちは！株式会社スマレジ 開発部のmasaです。
投稿が空いてしまい申し訳ないです。うっかり先週の投稿を忘れてしまってました。。。汗
さて、今回はBM25の実装です・
BM25とは
BM25は一言で言うと「ある文書Qから見て、ある文書Dがどれくらい類似しているか」を表すスコアになります。 この時の文書Qを「クエリ」、文書Dを「ドキュメント」と言ったりします。
イメージとしては、クエリは検索エンジンに入れる文字列で、ドキュメントはネット上にある検索対象の記事が近いです。
このイメージのように、BM25は検索のアルゴリズムとしてよく使われるのですが、ここでは二つの文書がどれくらい類似しているかを比較することに用いてみます。
イメージとしては、redmineの各チケットをクエリとして、全チケットをドキュメントとして総当たりでスコアを出していけば、あるチケットから見た類似度が数値としてわかるようになります。
これを全チケットで実施すれば、任意の二つのチケットの類似度を図ることができます。
BM25の定義式
Wikipediaより。
Wikiの引用で大丈夫か不安になる人もいそうですが、先日案内した参考文献のうち「情報検索の基礎」にも同様の数式があります。
IDF(qi)は見た通り、qiというワードのIDFで、f(qi, D)は文書DにおけるqiのTFになります。|D|は文書Dの単語数ですavgdlは今回の場合であれば比較したいredmineチケット群の平均単語数です。（単純に二つの文書だけで比較したい場合は二つの文書の単語数の平均値でOKです）- b, k1はパラメータです。算出結果を調整するためにこの数字を変えていきます。デフォルトではb = 0.75, k1 は1.2~2.0の間の数を用いられます。今回はk1 = 1.6で計算しています。
BM25の最大のポイントは単に単語出現数と逆頻度をかけるTF-IDFと異なり、文書長をavgdlで正規化し、その上でTFをパラメータで調整してから、IDFとの積の総和として文書の類似度を算出しているところにあります。要するに、全体集合として比較対象の二つ以外にも文書が存在していて、その中でこの二つがどれくらい類似しているのかを算出できるわけです。
通常、Webの検索で使用される際は全体集合が検索対象全体となるため、非常に膨大ですが、このテーマのようにredmineのような有限の文書集合では非常にこの性質がよく働きます。
実装
from janome.tokenizer import Tokenizer from janome.analyzer import Analyzer from janome.charfilter import * from janome.tokenfilter import * import json import requests import math import itertools class Tf: word = "" documentNumber = 0 score = 0.0 def getScore(self, word, documentNumber): if word == self.word and documentNumber == self.documentNumber: return self.score else: return 0.0 class Idf: word = "" score = 0.0 def getScore(self, word): if word == self.word: return self.score else: return 0.0 def getDescriptionOfRedmineIssueByIssueId(id): """ redmineのチケットをID指定で取得して、説明を返す。 :param id: int :return: Bool|string 取得成功なら文字列、失敗ならFalse """ headers = {'X-Redmine-API-Key': "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX"} response = requests.get("http:/redmineのdomain/issues/" + str(id) + ".json", headers=headers) statusCode = response.status_code if statusCode >= 400: return "" text = response.text if len(text) < 1: return "" resJson = json.loads(text) if "issue" not in resJson: return "" issue = resJson["issue"] sentence = issue["description"] if sentence is None: sentence = "" return sentence def culcBM25(targetDocumentNumber, queryDocumentNumber, vectors): bm25score = 0.0 for queryWord in vectors[queryDocumentNumber]: currentTfScore = 0.0 currentIdfScore = 0.0 for idf in idfScores: currentIdfScore = idf.getScore(queryWord) if currentIdfScore != 0.0: break for tf in tfScores: currentTfScore = tf.getScore(queryWord, targetDocumentNumber) if currentTfScore != 0.0: break denominator = currentTfScore + k1 + (1 - b + b * targetDocumentLength / averageLength) molecule = currentTfScore * (k1 + 1) bm25score += currentIdfScore * molecule / denominator return bm25score # 辞書定義 char_filters = [UnicodeNormalizeCharFilter(), RegexReplaceCharFilter('<("[^"]*"|\'[^\']*\'|[^\'">])*>', u'')] tokenizer = Tokenizer() token_filters = [CompoundNounFilter(), POSKeepFilter(['名詞']), LowerCaseFilter(), TokenCountFilter()] analyzeInfo = Analyzer(char_filters=char_filters, tokenizer=tokenizer, token_filters=token_filters) sentences = [] for i in range(72): if i == 0: continue sentences.append(getDescriptionOfRedmineIssueByIssueId(i)) # redmineチケットの説明を取得(ID指定) sentence_v1 = getDescriptionOfRedmineIssueByIssueId(70) sentence_v2 = getDescriptionOfRedmineIssueByIssueId(70) # ベクトル化 vectors = [] wkVector = [] for wkSentence in sentences: if len(wkSentence) < 1: vectors.append([]) continue wkVector = [] for result in analyzeInfo.analyze(wkSentence): wkVector.append(result[0]) vectors.append(wkVector) # 全文書の単語一覧 wordList = set(list(itertools.chain.from_iterable(vectors))) # TF及IDFの計算 tfScores = [] idfScores = [] for targetWord in wordList: idfScore = 0 for index, tmpVector in enumerate(vectors): wkTfScore = 0 if targetWord in tmpVector: idfScore += 1 for currentWord in tmpVector: if targetWord == currentWord: wkTfScore += 1 if len(tmpVector) < 1: score = 0 else: score = wkTfScore / len(tmpVector) tf = Tf() tf.word = targetWord tf.documentNumber = index tf.score = score tfScores.append(tf) idf = Idf() idf.word = targetWord idf.score = math.log((len(vectors) - idfScore + 0.5) / idfScore + 0.5) idfScores.append(idf) # パラメータ設定 b = 0.75 k1 = 1.6 # 平均文書長の計算 totalLength = 0 for tmpVector in vectors: totalLength = totalLength + len(tmpVector) averageLength = totalLength / len(vectors) # BM25の計算 targetDocumentLength = len(vectors[targetDocumentNumber]) bm25ScoreList = [[0] * len(vectors) for i in range(len(vectors))] for targetDocumentNumber in range(1, len(vectors) - 1): for queryDocumentNumber in range(1, len(vectors) - 1): bm25ScoreList[targetDocumentNumber][queryDocumentNumber] = culcBM25(targetDocumentNumber, queryDocumentNumber, vectors) if bm25ScoreList[targetDocumentNumber][queryDocumentNumber] > 0: print("" + str(queryDocumentNumber) + " -> " + str(targetDocumentNumber) + " = " + str(bm25ScoreList[targetDocumentNumber][queryDocumentNumber]))
前半のベクトル作成部分は特に変わりはないです。 TF,IDFの計算はエンティティクラスを作成して、結果をオブジェクトの配列として管理するように変更しています。
BM25の計算部分については、見ての通り、culcBM25で計算実行し、それをとってきたredmine全体で実施しています。
もしこれを使用する場合は、予めチケットの中身を取ってきてDBやテキストファイルとして持っておくか、検索条件を絞るようにした方が良いです。
総当たりの計算に時間がかかるのもそうですが、apiで都度とってくると、redmineのサーバ側に非常に負荷がかかるので・・・。
これで、計算ロジック部分の解説はおしまいです。 計算結果の評価などもしたいのですが、流石に会社のredmineの結果を張るわけにもいかず。。。 肌感になり申し訳ないですが、これを試してみたところ、ある程度の精度で順位付けはしてくれます。 性質の異なる複数のプロダクトを抱えているSaaSであれば、全部ごちゃ混ぜにしたとしても同じプロダクトのチケットは上位にランク付けされますし、機能で絞っても同様です。
例えば、BM25用にある機能の重要ワードを記載した意味のないチケットを作成して、それの類似度を定期的に調べておくと、 ある瞬間から高スコアのチケットばかりになったりすれば、何か不具合が起きているかもしれません。 （学生時代はこういう調査に使う文書をアンカー（錨）と言ったりしました）
これで類似度まではでてくるようになったので、次はこれを見える化することを考えていきます。
