Help us understand the problem. What is going on with this article?

機械学習ナイーブベイズ分類器のアルゴリズムを理解したのでメモ。そしてPythonで書いてみた。

More than 1 year has passed since last update.

概要

ナイーブベイズ分類器(ベイジアンフィルター)のアルゴリズムを具体的な数値を使って説明します。また、Pythonで実装してみました。自分の勉強メモのつもりで書いたのですが、他の方の役にも立てたら嬉しいです。

ナイーブベイズ分類器って?

あるデータ(文章)をどのカテゴリーに属するのかを判定させる、機械学習の教師あり学習の手法の一つです。
スパムメールフィルターやWEBニュース記事のカテゴライズによく使われています。

難易度

ベイズの定理を利用した単純な手法で、難易度は低です。
なるべく数式を使わないで説明してみました。

ナイーブベイズ分類器の計算

対象文章がどのカテゴリーに分類されるかを決めるための計算ロジックを、具体的な数値を使って説明します。

学習データが以下である場合、対象文章がどのカテゴリーに分類されるか計算します。

学習データ

  • サッカー  [ ボール | スポーツ | ワールドカップ | ボール ]
  • 野球    [ ボール | スポーツ | グローブ | バット ]
  • テニス   [ ボール | ラケット | コート ]
  • サッカー  [ ボール | スポーツ ]

※[ ]内はつながっている1つの文書だと仮定。

対象文書
「ボールスポーツ」

1. カテゴリー出現率の計算 P(C)

学習データの各カテゴリーの文書数を、総文書数で割った値を「カテゴリー出現率 P(C)」とします。

サッカー 野球 テニス
カテゴリー出現確率 $\frac{2}{4}$   $\frac{1}{4}$  $\frac{1}{4}$ 

2. カテゴリー内の文書出現率の計算 P(D|C)

学習データ内の各カテゴリーの単語数を数えます。
重複は排除せず、サッカーは合計とします。

サッカー 野球 テニス
単語数 $6$   $4$  $3$ 

「ボール」と「スポーツ」の各カテゴリーごとの出現回数を数え、上記で数えた各カテゴリーの単語数で割ります。これを「カテゴリー内の単語出現率 P(Wn|C)」とします。

サッカー 野球 テニス
ボール $\frac{3}{6}$   $\frac{1}{4}$  $\frac{1}{3}$ 
スポーツ $\frac{2}{6}$   $\frac{1}{4}$  $\frac{0}{3}$ 

計算した「ボールの値」と「スポーツの値」を掛け合わせた値を「カテゴリー内の文書出現率 P(D|C)」とします。

サッカー 野球 テニス
カテゴリー内の文書出現率 $\frac{6}{36}$ $\frac{1}{16}$ $\frac{0}{9}$

3. 文章内のカテゴリー出現率の計算 P(C|D)

上記の1. と2. で出した「カテゴリー出現率 P(C)」と「カテゴリー内の文書出現率 P(D|C)」を掛け合わせたものが文書に対する各カテゴリーへ属する確率(文章内のカテゴリー出現率 P(C|D))です。

この値が最も高いものが対象文書のカテゴリーと分類します。

サッカー 野球 テニス
文章内のカテゴリー出現率 $\frac{2}{4} \times \frac{6}{36} $ $\frac{1}{4} \times \frac{1}{16} $  $\frac{1}{4} \times \frac{0}{9} $ 
計算結果 $\frac{1}{12}$ $\frac{1}{64}$  $\frac{0}{36}$ 

結果、「ボールスポーツ」は「サッカー」へ分類されました!!

(あくまで例題なので、全部ボールスポーツであることはスルーで)

4. ゼロ頻度問題

この例では、テニスの確率が $0$ になりました。「スポーツ」という単語が「テニス」の学習データになかったからです。

学習データには存在しない新ワードがあった場合、カテゴリーの確率が$0$になってしまいます。
これを「ゼロ頻度問題」といいます。

これを解決するために、加算スムージングという方法をとって、再計算します。

加算スムージングで再計算

2.の「カテゴリー内の単語出現率 P(Wn|C)」計算部分に、下記の太字部分の処理を加えるだけです。

「ボール」と「スポーツ」の各カテゴリーごとの出現回数を数えて1加え、上記で数えた各カテゴリーの単語数に学習データ全単語数を加えた値で割ります。

学習データ全単語数は重複排除するので、8個です。

「カテゴリー内の単語出現率 P(Wn|C)」を再度表にまとめました。

サッカー 野球 テニス
ボール $\frac{(3 + 1)}{(6 + 8)}$  $\frac{(1 + 1)}{(4 + 8)}$  $\frac{(1 + 1)}{(3 + 8)}$ 
スポーツ $\frac{(2 + 1)}{(6 + 8)}$   $\frac{(1 + 1)}{(4 + 8)}$  $\frac{(0 + 1)}{(3 + 8)}$ 

分数を計算します。

サッカー 野球 テニス
ボール $\frac{4}{14}$  $\frac{2}{12}$  $\frac{2}{11}$ 
スポーツ $\frac{3}{14}$  $\frac{2}{12}$  $\frac{1}{11}$ 

こうすると、「スポーツ」という単語が「テニス」の学習データになくても、確率が0にはならないことがわかります。

そして、続きをそのまま計算します。

1.で計算した「カテゴリー出現率 P(C)」はそのままです。
「カテゴリー内の文書出現率 P(D|C)」は上記で分数計算した「ボール」と「スポーツ」の値を掛け合わせたものです。

サッカー 野球 テニス
カテゴリー出現確率 $\frac{2}{4}$   $\frac{1}{4}$  $\frac{1}{4}$ 
カテゴリー内の文書出現率 $\frac{12}{196}$ $\frac{4}{144}$  $\frac{2}{121}$ 
文章内のカテゴリー出現率 $\frac{2}{4}$ × $\frac{12}{196}$ $\frac{1}{4}$ × $\frac{4}{144}$ $\frac{1}{4}$× $\frac{2}{121}$ 
計算結果 $\frac{3}{98}$ $\frac{1}{144}$  $\frac{1}{242}$ 

結果はテニスの確率が$0$にならずに、サッカーと分類されました!!

しかし、加算スムージングは「カテゴリー出現率 P(C)」の値の影響が大きくなり、精度が悪くなるように思います。ここをよく考慮して学習データをセットする必要がありますね。

5. アンダーフロー対策

例題はわかりやすくするために、単語数やデータセットを少なくしましたが、実際はもっと沢山の単語を取り扱います。そのため、計算結果の分母が非常に大きな数になり、アンダーフローを起こす可能性が高いです。

その回避策が、対数で比較する方法です。

$0.001$ は $\frac{1}{10}$ × $\frac{1}{10}$ × $\frac{1}{10}$ とも表すことができ、$10$の$-3$乗といい、-3が$0.001$の対数です。(底は$10$)
$0.0001$ は $\frac{1}{10}$ × $\frac{1}{10}$ × $\frac{1}{10}$ × $\frac{1}{10}$ とも表すことができ、$10$の$-4$乗といい、-4が$0.001$の対数です。(底は$10$)

$X$, $Y$, $Z$ の大小関係は、$X$の対数, $Y$の対数, $Z$の対数 の大小関係と同じです。(底が同じで1より大きい場合)
対数は元の値より大きくなります。(値が1より小さくて、底が1より大きい場合)

また、値の掛け算の大小は対数の足し算の大小と同じになります。
2 × 2 × 2  : 対数 3
2 × 2 × 2 × 2 : 対数 3 + 1

話は例題に戻り、
「カテゴリー内の文書出現率 P(D|C)」を「ボール」と「スポーツ」の「カテゴリー内の単語出現率 P(Wn|C)」の対数の足し算として算出し、「カテゴリー出現確率 P(C)」の対数と足し算してあげます。

サッカー 野球 テニス
カテゴリー出現確率 $\log {\frac{2}{4}}$   $\log {\frac{1}{4}}$  $\log {\frac{1}{ 4}}$ 
カテゴリー内の単語出現率(ボール) $\log {\frac{4}{14}}$  $\log {\frac{2}{12}}$   $\log {\frac{2}{11}}$
カテゴリー内の単語出現率(スポーツ) $\log {\frac{3}{14}}$  $\log {\frac{2}{12}}$  $\log {\frac{1}{11}}$ 
文章内のカテゴリー出現率 $\log {\frac{2}{4}} + \log {\frac{4}{14}} + \log {\frac{3}{14}}$ $\log {\frac{1}{4}} + \log {\frac{2}{12}} + \log {\frac{2}{12}}$  $\log {\frac{1}{ 4}} + \log {\frac{2}{11}} + \log {\frac{1}{11}}$ 

これでナイーブベイズ分類器の完成です!!

※logの表記方法はこちらを見てください
http://kenyu.red/archives/3132.html

Pythonで書いてみた

以下のサイトを参考に実際にpythonで書いてみました。
http://yaju3d.hatenablog.jp/entry/2016/10/31/222307

上で説明した値がどこに該当するのか、出来る限りコメントで記載してみました。
形態素解析にはjanomeを使用してます。

naivebayes.py
class NaiveBayes:

    # コンストラクタ
    def __init__(self):

        # 学習データの全単語の集合(加算スムージング用)
        self.vocabularies = set()

        # 学習データのカテゴリー毎の単語セット用
        self.word_count = {}

        # 学習データのカテゴリー毎の文書数セット用
        self.category_count = {}

    # 学習
    def train(self, document, category):

        # 学習文書を形態素解析
        ma = MorphologicalAnalysis()
        word_list = ma.get_word_list(document)

        for word in word_list:

            # カテゴリー内の単語出現回数をUP
            self.__word_count_up(word, category)

        # カテゴリーの文書数をUP
        self.__category_count_up(category)

    # 学習データのカテゴリー内の単語出現回数をUP
    def __word_count_up(self, word, category):

        # 新カテゴリーなら追加
        self.word_count.setdefault(category, {})

        # カテゴリー内で新単語なら追加
        self.word_count[category].setdefault(word, 0)

        # カテゴリー内の単語出現回数をUP
        self.word_count[category][word] += 1

        # 学習データの全単語集合に加える(重複排除)
        self.vocabularies.add(word)

    # 学習データのカテゴリーの文書数をUP
    def __category_count_up(self, category):

        # 新カテゴリーなら追加
        self.category_count.setdefault(category, 0)

        # カテゴリーの文書数をUP
        self.category_count[category] += 1

    # 分類
    def classifier(self, document):

        # もっとも近いカテゴリ
        best_category = None

        # 最小整数値を設定
        max_prob = -sys.maxsize

        # 対象文書を形態素解析
        ma = MorphologicalAnalysis()
        word_list = ma.get_word_list(document)

        # カテゴリ毎に文書内のカテゴリー出現率P(C|D)を求める
        for category in self.category_count.keys():

            # 文書内のカテゴリー出現率P(C|D)を求める
            prob = self.__score(word_list, category)

            if prob > max_prob:
                max_prob = prob
                best_category = category

        return best_category

    # 文書内のカテゴリー出現率P(C|D)を計算
    def __score(self, word_list, category):

        # カテゴリー出現率P(C)を取得 (アンダーフロー対策で対数をとり、加算)
        score = math.log(self.__prior_prob(category))

        # カテゴリー内の単語出現率を文書内のすべての単語で求める
        for word in word_list:

            # カテゴリー内の単語出現率P(Wn|C)を計算 (アンダーフロー対策で対数をとり、加算)
            score += math.log(self.__word_prob(word, category))

        return score

    # カテゴリー出現率P(C)を計算 
    def __prior_prob(self, category):

        # 学習データの対象カテゴリーの文書数 / 学習データの文書数合計
        return float(self.category_count[category] / sum(self.category_count.values()))

    # カテゴリー内の単語出現率P(Wn|C)を計算
    def __word_prob(self, word, category):

        # 単語のカテゴリー内出現回数 + 1 / カテゴリー内単語数 + 学習データの全単語数 (加算スムージング)
        prob = (self.__in_category(word, category) + 1.0) / (sum(self.word_count[category].values())
                                                             + len(self.vocabularies) * 1.0)
        return prob

    # 単語のカテゴリー内出現回数を返す
    def __in_category(self, word, category):

        if word in self.word_count[category]:
            # 単語のカテゴリー内出現回数
            return float(self.word_count[category][word])
        return 0.0

上記のクラスの学習と分類をViewから呼び出してあげました。

view.py
def matching(request):

    if request.method == 'POST':

        # 対象文書取得
        words = request.POST['words']

        nb = NaiveBayes()

        # 学習データセット
        nb.train('ボール スポーツ ワールドカップ ボール', 'サッカー')
        nb.train('ボール スポーツ グローブ バット', '野球')
        nb.train('ボール ラケット コート', 'テニス')
        nb.train('ボール スポーツ', 'サッカー')

        # 分類した結果を取得
        category = nb.classifier(words)

        dictionary = {'category': category}

        return render(request, 'matching.html', dictionary)

    elif request.method == 'GET':

        return render(request, 'matching.html')

おわり

機械学習は勉強を始めたばかりで、分からない事だらけです。
またPythonも始めて数日なので、書き方が変かもしれません。

上記の説明で誤りがありましたら、指摘いただけたら嬉しいです。

また、janomeだとカタカナ続きの単語を区切ってくれませんでした。
自分用メモのつもりでしたが、もしも誰かの役に立てたら嬉しいです:blush:

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away