Pythonで英文類似記事検索アルゴリズム : TF-IDF, Cosine類似度

# 概要

急にリコメンドに興味を持ちまして、ニュースの類似記事検索アルゴリズムを試してみました。
アルゴリズムは、自然言語分野ではよく使われている**TF-IDF**と**Cosine類似度**を用いました。

# TF-IDFとは
文章をベクトル化するアルゴリズムの一つです。

- TF : Term Frequency。単語の出現頻度。
- IDF : Inverse Document Frequency。直訳すると「逆文書頻度」。  
珍しい文字が入ると値が大きくなる為、単語の「希少性」を表しているとも言えます。

各文章の単語を抜き出し、全ての単語に対してTF(その文章が保持する単語数)とIDF(希少性)を掛け合わせたベクトルを作成します。このベクトルを用いることで、文章を用いた情報検索やクラスタリングが可能になります。

詳しくは[こちらの記事](http://ailaby.com/tfidf/)などが分かりやすいです。

# Cosine類似度とは
2つのベクトルがどれくらい同じ向きを向いているのかを算出する指標（計算式）です。
TF-IDFでベクトル化した文書に対してこの指標を用いることで、類似した文章（同じ向きを向いているベクトル）を見つけることができます。

数式は以下の通り。
$$
similarity = cos\theta = \frac{A \cdot B}{||A|| ||B||}
$$

詳しくは[こちらの記事](https://qiita.com/tetsutaroendo/items/61942d25ae2a017831f2)などが分かりやすいです。


# データセット
今回も、いつものようにデータ解析コンペサイト[Kaggle](https://www.kaggle.com/)のデータを用います。
https://www.kaggle.com/uciml/news-aggregator-dataset/data
- データ内容：英語ニュース記事
- データ件数：422,937件
- 収集期間：2014/3/10から8/10

# 実装
numpy, pandas, Scikit-learnを用いることで、簡単に実装できます。
ソースコードは[こちら(Github)](https://github.com/yampy/machine-learning/blob/master/recommendation/news-recommendation-en.py)を参照下さい。

## インポート

今回、ライブラリはScikit-learnの*TfidfVectorizer*、*cosine_similarity*を使用します。

```python
import numpy
import pandas
from sklearn.feature_extraction.text import TfidfVectorizer
from sklearn.metrics.pairwise import cosine_similarity
```

## データ読み込み & 定数 
```python
DATASET_FILE_PATH = "./datasets/uci-news-aggregator.csv"
RESULT_FILE_PATH = "./output/similarity_calc_result.csv"

dataset = pandas.read_csv(DATASET_FILE_PATH)
dataset = dataset[0:10000] # データ量が多いので必要に応じて省略

confidence = 0.6 # 類似度が0.6以上の記事のみ表示
```

## TF-IDF(TfidfVectorizer)による文書のベクトル化
```python
input_dataset = numpy.array(dataset["TITLE"])
tf_idf_vectorizer = TfidfVectorizer(analyzer="word", ngram_range=(1, 3), min_df=1, stop_words="english")
tf_idf_vector = tf_idf_vectorizer.fit_transform(input_dataset)

```


## Cosine類似度（cosine_similarity）の算出
```python

# calculate similaritis

similarities_calc_result = []

# TD_IDF vector Iterration
for item_index, item in enumerate(tf_idf_vector):
    # calculate cosine similarities
    similarities = cosine_similarity(item, tf_idf_vector)
    
    # sort in ascending order
    similarities_index =similarities.argsort()[0][-2:-12:-1]
    
    # cocine similarities Iteration
    for sim_index in similarities_index:
        similarity = similarities[0][sim_index]

        # if similarity is higher than confidence, save it to result object
        if similarity > confidence and  similarity < 1:
            similarities_calc_result.append([int(item_index), int(dataset["ID"][sim_index]), similarity])
    # show progress
    # print("progress:", item_index/len(dataset.index))
    
# save result as csv format
result = pandas.DataFrame(similarities_calc_result, columns=["Source_ID", "Similar_ID", "Similarity"])
result.to_csv(RESULT_FILE_PATH, index=False)
```

# 任意の記事に対し、類似の高いニュースを表示

```python
print("please input which news_id you like...")
input_id = int(input())
sim_id = 0

print("you selected below news:")
print(dataset.loc[[input_id], ["TITLE"]])
print("######################################")
print("Below are similar news:")
for result_index, sim_id in enumerate(result.ix[result["Source_ID"] == input_id]["Similar_ID"]):
    print(sim_id, ":", dataset.loc[sim_id]["TITLE"])

if (len(result.ix[result["Source_ID"] == input_id]["Similar_ID"]) == 0):
    print("Nothing to show.")
```

## 実行結果

"ECB" という文字列が含まれている似たニュースがちゃんと拾われています。


```
you selected below news:
                                                TITLE
27  ECB to reveal bad loan hurdles for euro zone b...
######################################
Below are similar news:
32 : ECB requires tougher call on bad loan definition
31 : ECB to reveal bad loan hurdles for euro zone bank test - sources
```

# 感想
アルゴリズム自体はライブラリがあるので、データの扱いに一番時間がかかりました。
iPython Notebookなどでデータを確認しながらやるのがおすすめです。

次は、MeCabなどの構文解析ソフトを使って日本語の記事でも試していきたいと思います。

# 参考
- [(未解決)大規模疎行列のコサイン類似度](http://studylog.hateblo.jp/entry/2015/05/24/033333)
- [Scipyの疎行列を使った文書間コサイン類似度の計算](http://hamukazu.com/2016/07/01/cosine-similarity-using-scipy-sparse/)