【Python】MinHashとMeCabを使って文章の類似度を計算する

# はじめに

最近 Python で自然言語処理を扱うことになり、現在勉強中です。

自然言語処理では、「この文章はどれだけ似ているか？」という判定が求められる場面があります。特に日本語では語順や助詞の影響が強いため、うまく処理するためにはちょっとした工夫が必要です。

この記事では、MinHashとMeCabを組み合わせて、日本語の類似度を比較する方法を紹介します。

類似度ですが、今回は「意味」より「形式的な一致」に着目します。

# MinHash とは？

MinHashは、大量の文書やテキストを比較する際に、「どれだけ重なっているか（Jaccard類似度）」を計算できるアルゴリズムです。以下のように集合 $A,\ B$ の共通部分の要素数を和集合の要素数で割ります。

$$
J(A,\ B) = \displaystyle \frac{|A\cap B|}{|A\cup B|}
$$

すべての語を比較する代わりに、代表的なハッシュ値を使って効率化します。

本記事では以下のライブラリを使用します。

https://pypi.org/project/datasketch/

https://ekzhu.com/datasketch/minhash.html

# 日本語に対応させるための工夫

MinHashでは n-gram と呼ばれる文章を n 文字の長さに分割する手法を使用し、分割した文字列をハッシュオブジェクトに変換します。しかし、この方法は助詞や語順に弱いため MeCab での分かち書きを使用することにしました。類似度を計算するうえで句読点はノイズとなると考え、MeCab での分かち書き結果から除去しました。

- MeCab インストール方法

```bash
pip install mecab-python3
```

- MeCab での分かち書き

```py
import MeCab
import ipadic

mecab = MeCab.Tagger(ipadic.MECAB_ARGS)

def tokenize(text: str) -> List[str]:
    """MeCabで分かち書きし、記号を除外した単語リストを返す"""
    node = mecab.parseToNode(text)
    tokens = []
    while node:
        surface = node.surface
        feature = node.feature.split(',')
        if surface and feature[0] != '記号':  # 品詞が「記号」でないものだけを使う
            tokens.append(surface)
        node = node.next
    return tokens
```

# Jaccard類似度を計算する

- datasketch インストール方法

```bash
pip install datasketch
```

以下のように分かち書き結果を MinHash オブジェクトに変換し、類似度を計算します。

```py
from datasketch import MinHash

def minhash_signature(tokens: List, num_perm: int=128) -> MinHash:
    """トークン（文字列）の配列をMinHashオブジェクトに変換"""
    m = MinHash(num_perm=num_perm)
    for token in tokens:
        m.update(token.encode('utf-8'))
    return m

# ハッシュオブジェクトを生成
sig_1 = minhash_signature(tokens_1)
sig_2 = minhash_signature(tokens_2)

# Jaccord類似度を計算
similarity = sig_1.jaccard(sig_2)
print(f'類似度: {similarity:.6f}')
```

# 結果

## 検証1

同じ文章を比較します。

- 比較する文章

```py
# 入力テキスト
text_1 = '朝起きてコーヒーを淹れ、窓を開けると、涼しい風が部屋に入り込んできた。鳥のさえずりが心地よく響いていた。'
text_2 = '朝起きてコーヒーを淹れ、窓を開けると、涼しい風が部屋に入り込んできた。鳥のさえずりが心地よく響いていた。'
```

- 結果

```
類似度: 1.000000
処理時間: 0.026646秒
```

## 検証2

少し文章を変えてみます。

- 比較する文章

```py
# 入力テキスト
text_1 = '朝起きてコーヒーを淹れ、窓を開けると、涼しい風が部屋に入り込んできた。鳥のさえずりが心地よく響いていた。'
text_2 = '朝起きてミルクを温め、窓を開けると、涼しい風が部屋に入り込んできた。鳥たちのさえずりが心地よく響いていた。'
```

- 結果

```
類似度: 0.804688
処理時間: 0.032637秒
```

## 検証3

最後にまったく異なる文章を比較します。

- 比較する文章

```py
# 入力テキスト
text_1 = '朝起きてコーヒーを淹れ、窓を開けると、涼しい風が部屋に入り込んできた。鳥のさえずりが心地よく響いていた。'
text_2 = 'ビルの谷間をすり抜けるクラクションと人のざわめき。人波が流れ、都会の喧騒が絶え間なく続いていた。'
```

- 結果

```
類似度: 0.156250
処理時間: 0.035281秒
```

# 気になったこと

- 最初の実行では、1/100秒台、2回目以降の実行では 1/1000 秒台となるのはなぜか

# 検証に用いたコード

```py
from datasketch import MinHash
import time
import MeCab
import ipadic
from typing import List

start = time.perf_counter()

mecab = MeCab.Tagger(ipadic.MECAB_ARGS)

def tokenize(text: str) -> List[str]:
    """MeCabで分かち書きし、記号を除外した単語リストを返す"""
    node = mecab.parseToNode(text)
    tokens = []
    while node:
        surface = node.surface
        feature = node.feature.split(',')
        if surface and feature[0] != '記号':  # 品詞が「記号」でないものだけを使う
            tokens.append(surface)
        node = node.next
    return tokens

def minhash_signature(tokens: List, num_perm: int=128) -> MinHash:
    """トークン（文字列）の配列をMinHashオブジェクトに変換"""
    m = MinHash(num_perm=num_perm)
    for token in tokens:
        m.update(token.encode('utf-8'))
    return m

# 入力テキスト
text_1 = '朝起きてコーヒーを淹れ、窓を開けると、涼しい風が部屋に入り込んできた。鳥のさえずりが心地よく響いていた。'
text_2 = '朝起きてミルクを温め、窓を開けると、涼しい風が部屋に入り込んできた。鳥たちのさえずりが心地よく響いていた。'

# 分かち書き（単語リスト）
tokens_1 = tokenize(text_1)
tokens_2 = tokenize(text_2)

print(f'tokens_1: {tokens_1}')
print(f'tokens_2: {tokens_2}')

# ハッシュオブジェクトを生成
sig_1 = minhash_signature(tokens_1)
sig_2 = minhash_signature(tokens_2)

# Jaccard類似度を計算
similarity = sig_1.jaccard(sig_2)
print(f'類似度: {similarity:.6f}')

end = time.perf_counter()
print(f'処理時間: {end - start:.6f}秒')
```

# 参考

https://atmarkit.itmedia.co.jp/ait/articles/2408/28/news025.html

https://taku910.github.io/mecab/

https://ekzhu.com/datasketch/minhash.html