Python3.3で実装したナイーブベイズ分類器を利用して、文章と文字列中の語の共起頻度から、類似度を計算する


**この投稿は[現実逃避アドベントカレンダー2013](http://katryo.hatenablog.com/entry/2013/12/19/001823)の3日目の記事です。**

## 今回の内容を3行でまとめる
- 前回作った分類器を利用した類似度計算器を作った
- カテゴリと入力文字列の類似度を計算できるようにした
- コサイン類似度とシンプソン係数を使った類似度が計算できる

Githubにコードをまとめて上げた。 https://github.com/katryo/bing_search_naive_bayes_sim

## [前回](http://qiita.com/katryo/items/62291ba328de9d12bd30)までのあらすじ

- Bing APIを利用してWeb検索を行い
- クエリをカテゴリ名として、分類器に学習させ
- 入力した文字列がどのカテゴリに入るか分類させる

こういうシステムを作った。

## 今回追加した機能

- 入力した文字列と各カテゴリに入れた文書との類似度計算

### さらに詳しく
- ベクトル（数学ガールっぽくヴェクタと呼ぶほうが好き）のコサイン類似度の計算
- 2つの集合のシンプソン係数による類似度計算

の2種類の類似度計算機能を追加した。

## 理論
### 2種類の類似度計算方法
#### コサイン類似度
2つのベクトルのコサインを計算し、コサインの値を類似度とする。ベクトルの次元数は2でも3でも100でもよい（具体例を後述）。ただし次元数が増えると当然計算コストが高くなるので次元数を減らせる工夫（tfidfで頻出すぎる語はカウントしない、とか）ができるならしたほうがいい。ちなみに今回は工夫していない。

#### シンプソン係数
コサイン類似度とは異なり、ベクトルではなく2つの「語の集合(= Bag of words) 」を比べ、共通して持っている語の数で類似度を計算する。頻度は関係ない。

コードを見てもらえばわかるが、1カテゴリ（あるいは1入力文字列中）に100回同じ単語が出現しても1回だけ出現しても、同じように計算する（だから頻度は関係ない！）。同じ単語が繰り返し登場しても、スコアを高くしたりはしない。

### ナイーブベイズの生起確率と類似度
#### 生起確率
ナイーブベイズである語（たとえば「診察」）があるカテゴリ（たとえば「花粉症」）に入る確率を計算するとする。

[第一回](http://qiita.com/katryo/items/6a2266ffafb7efa9a46c)でも説明したが、その確率はかなり小さくなる。普通のやり方だと0.01より小さくなる。

さらに、今回、分類における入力は語ではなく文章だ。MeCabで形態素解析をしてBag of wordsにして、語の集合として計算しているわけだから、さらに確率は低くなる。

ナイーブベイズにおいて「花粉症になったらまず耳鼻咽喉科の医院に診察してもらうといいですよ」という文が「花粉症」カテゴリに入る確率は、0.0000……1くらいだと思っていい。

だが他のカテゴリ（「骨折」や「胃もたれ」など）に入る確率よりずっと高い。相対的にだが、群を抜いて高い。だから、「花粉症になったらまず耳鼻咽喉科の医院に診察してもらうといいですよ」が「花粉症」カテゴリに入るのがいちばん尤もらしい。つまり尤度が高い。

#### 類似度
類似度は生起確率とはまったく別の考えである。語の集合同士の類似度をどう定義し、どう計算するかは手法によって異なる。

詳しくは[しょとうさんのブログ記事](http://sucrose.hatenablog.com/entry/2012/11/30/132803)や[データ分析・マイニングの世界 by SASというWikiページ](http://wikiwiki.jp/cattail/?%CE%E0%BB%F7%C5%D9%A4%C8%B5%F7%CE%A5)や[類似性尺度のまとめ論文](http://ci.nii.ac.jp/naid/110006440287)あたりを読むとよいと思う。

今回はコサイン類似度とSimpson係数を使った類似度計算を行ったが、Jaccard係数やDice係数を使ったり、類似度計算には様々な手法がある。用途と計算量で使い分けよう。

## コード
1. 類似度計算器
2. 作ったシステムに組み込んで類似度を計算

作ったコードは2つに分けられる。

### 1. 類似度計算器
まず以下のようなSimCalculatorクラスを作った。

```python:sim_calculator.py
import math


class SimCalculator():
    def _absolute(self, vector):
        # ベクトルvの長さつまり絶対値を返す
        squared_distance = sum([vector[word] ** 2 for word in vector])
        distance = math.sqrt(squared_distance)
        return distance

    def sim_cos(self, v1, v2):
        numerator = 0
        # v1とv2で共通するkeyがあったとき、その値の積を加算していく。2つのベクトルの内積になる。
        for word in v1:
            if word in v2:
                numerator += v1[word] * v2[word]
        
        denominator = self._absolute(v1) * self._absolute(v2)

        if denominator == 0:
            return 0
        return numerator / denominator

    def sim_simpson(self, v1, v2):
        intersection = 0
        # v1とv2で共通するkeyの数を数えている
        for word in v2:
            if word in v1:
                intersection += 1
        denominator = min(len(v1), len(v2))

        # v1かv2の中身が0だったとき
        if denominator == 0:
            return 0
        return intersection / denominator

if __name__ == '__main__':
    sc = SimCalculator()
    print('コサイン類似度は' + str(sc.sim_cos({'ライフハック': 1, '骨折': 2}, {'ライフハック': 2, '仕事': 1, '趣味': 1})))
    print('シンプソン係数で計算した類似度は' + str(sc.sim_simpson({'ライフハック': 1, '骨折': 2}, {'ライフハック': 2, '仕事': 1, '趣味': 1})))

```

実行するとこんな結果になる。

```
コサイン類似度は0.3651483716701107
シンプソン係数で計算した類似度は0.5
```

コサイン類似度を計算しているsim_cosメソッドの中で使っている_absoluteメソッドは、ベクトルの長さ（絶対値、大きさ）を計算している。ここでいうベクトルは、「ライフハック」や「骨折」のような単語によって表現されている。たとえば上記のコードの

```
{‘ライフハック': 1, '骨折': 2}
```

は2次元ベクトルである。

参考 http://www.rd.mmtr.or.jp/~bunryu/pithagokakutyou.shtml

### 2. 作ったシステムに組み込んで類似度を計算
1で作った類似度計算器を、[前回作ったナイーブベイズ分類器](http://qiita.com/katryo/items/62291ba328de9d12bd30)に組み込む。

つまり標準入力した文字列とカテゴリ（に入れた学習データのBag of words）との類似度を計算する機能を追加する。

ちなみにナイーブベイズによる分類は行わず、NaiveBayesオブジェクトが学習した結果を利用しているに過ぎない。

以下のコードを実行すると、分類と類似度計算を同時に行えるターミナルツールになる。

```python:calc_similarity.py
from sim_calculator import SimCalculator
from naive_bayes import NaiveBayes
import constants
import pickle
import sys
import pdb
from collections import OrderedDict


if __name__ == '__main__':
    sc = SimCalculator()
    with open(constants.NB_PKL_FILENAME, 'rb') as f:
        nb_classifier = pickle.load(f)

    # 標準入力した文字列を、trainとword_countを使って {'input': {'スギ花粉': 4, '薬':3}}という形式に整形するためNBオブジェクトにした
    # 分類器としては使わないので本当は別のクラスを作ってやるべきだがめんどい
    nb_input = NaiveBayes()

    for query in sys.stdin:
        nb_input.word_count = {}  # 二回目以降のinputのための初期化
        nb_input.train(query, 'input')  # 標準入力で入れた文字列を'input'カテゴリとして学習
        results = OrderedDict()
        for category in nb_classifier.word_count:
            # sim_cosのかわりにsim_simpsonも使える
            sim_cos = sc.sim_cos(nb_input.word_count['input'], nb_classifier.word_count[category])
            results[category] = sim_cos

        for result in results:
            print('カテゴリー「%s」との類似度は %f です' % (result, results[result]))

        # http://cointoss.hatenablog.com/entry/2013/10/16/123129 の通りやってもmaxのkey取れない(´・ω・`)
        best_score_before = 0.0
        best_category = ''
        for i, category in enumerate(results):
            if results[category] > best_score_before:
                best_category = category
                best_score_before = results[category]
        try:
            print('類似度の最も高いカテゴリーは「%s」で類似度は %f です' % (best_category, results[best_category]))
        except KeyError:  # inputが空白のとき
            continue
``` 

これを実行して、適当な文字列を入れよう。

```
少しでも花粉症を楽に乗りきるためには、しっかり花粉症対策を行うことが大切。そのための自分でできる花粉症の基本的な対策や花粉症日記、間違った花粉症対策などをご紹介します。
```

[適当なページ](http://www.kyowa-kirin.co.jp/kahun/measure/)から取ってきた文字列を入れた結果がこちらだ。

```
カテゴリー「胃もたれ」との類似度は 0.362058 です
カテゴリー「虫歯」との類似度は 0.381352 です
カテゴリー「花粉症対策」との類似度は 0.646641 です
カテゴリー「鬱」との類似度は 0.250696 です
カテゴリー「機械」との類似度は 0.300861 です
カテゴリー「骨折」との類似度は 0.238733 です
カテゴリー「肩こり」との類似度は 0.326560 です
カテゴリー「書類」との類似度は 0.333795 です
類似度の最も高いカテゴリーは「花粉症対策」で類似度は 0.646641 です
```

うん、それらしい結果になった。

[ここ](http://matome.naver.jp/odai/2137329123912824901)から取ってきた文章を入れる。

```
10代20代の頃は、焼肉と言えばカルビ、とんかつはロース、ラーメンはとんこつで替え玉当たり前。大好きだったけど、少しずつ疎遠になってきた
```

いかにも胃もたれしそうな文章だ。これを入力すると。

```
カテゴリー「胃もたれ」との類似度は 0.398943 です
カテゴリー「虫歯」との類似度は 0.425513 です
カテゴリー「花粉症対策」との類似度は 0.457718 です
カテゴリー「鬱」との類似度は 0.300388 です
カテゴリー「機械」との類似度は 0.340718 です
カテゴリー「骨折」との類似度は 0.256197 です
カテゴリー「肩こり」との類似度は 0.339602 です
カテゴリー「書類」との類似度は 0.322423 です
類似度の最も高いカテゴリーは「花粉症対策」で類似度は 0.457718 です
```

あれ……「胃もたれ」にならない……？

最後に[こちら](http://www.ha-channel-88.com/musiba/)から取ってきた虫歯の文章の類似度を計算する。

```
虫歯の原因や治療法、予防法、子供(乳歯)のむし歯、治療費などについて詳しく解説。虫歯の画像(写真)や、初期虫歯の治療についても
```
どうなる？

```
カテゴリー「胃もたれ」との類似度は 0.404070 です
カテゴリー「虫歯」との類似度は 0.445692 です
カテゴリー「花粉症対策」との類似度は 0.427097 です
カテゴリー「鬱」との類似度は 0.306610 です
カテゴリー「機械」との類似度は 0.381016 です
カテゴリー「骨折」との類似度は 0.241813 です
カテゴリー「肩こり」との類似度は 0.346461 です
カテゴリー「書類」との類似度は 0.394373 です
類似度の最も高いカテゴリーは「虫歯」で類似度は 0.445692 です
```

よかった。

胃もたれらしい文章が花粉症対策と判断されたのは、ノイズが多かったためと考えられる。

「を」や「は」のような語はどんなカテゴリーにも出現する。これらは人間からすればカテゴリー分類に非有用だが、上記の手法では単純に出現したすべての語の頻度をもとに類似度を計算しているため、類似度計算に使ってしまっている。

tf-idfを使うなどして、頻度の多い語の重みを下げ、頻度の少ない語の重みを高めることで、性能を高められるかもしれない。

#### 補足
コメントにも書いたが、標準入力をNaiveBayesオブジェクトであるnb_inputに入れている。trainメソッドとword_countメソッドを使うためだが、本来こいつはNaiveBayes分類器ではないので、別にクラスを作って、NaiveBayesのほうもそのクラスを継承させるようにしたほうがしっかりした設計になる。

ちなみに最後の結果出力のあたりで「dictの中からvalue最大値のやつのkeyとvalueを取得する」ということをしようとして、かっこいい書き方を調べた。[この記事](http://cointoss.hatenablog.com/entry/2013/10/16/123129)がまさしく求めることを書いているが、うまくいかなかった。Python3になって仕様が変わったのが原因だと思う。

あと、機械学習を実際に使うときは[scikit-learn](http://scikit-learn.org/stable/)のようなライブラリを使うと高速かつバグなしにできてよいと思う。今回の記事のように自分で実装するのはあくまで勉強のためであり、実用の際は遠慮なく品質が保たれたライブラリを使うべき。

## Github
Githubにコードを上げた。 https://github.com/katryo/bing_search_naive_bayes_sim

## 参考
ショ糖さんの個人ブログ http://sucrose.hatenablog.com/entry/2012/11/30/132803

## 次回予告
次こそtf-idfを実装して性能向上を目指す。類似度の計算方法を変えて、Dice係数やJaccard係数を使ったものにしても面白そう。

と思ったけどscikit-learnでtf-idf計算することにした。

[続きはこちら](http://qiita.com/katryo/items/f86971afcb65ce1e7d40)