tf-idfの実装

基本的にwikiを参照しているので、間違いがあったらご指摘いただけるとありがたいです。

tf-idfの説明ですが、wikipediaから引用すると、
> [tf-idf](https://ja.wikipedia.org/wiki/Tf-idf)は文章中に含まれる単語の重要度を評価する手法の1つであり、主に情報検索やトピック分析などの分野で用いられている。

と記載されています。文書中にどの単語が重要かを測定するために

* **TF** (Term Frequency )
* **IDF** (Inverse Document Frequenc)

を掛けることでその指標としています。デジタルライブラリの文章レコメンドシステムの83％がtf-idfを使用しているそうです[^1]。

ここでは、tf-idfの考え方と実際にコーディングをすることで理解を深めたいと思います。


## Term frequency (TF)

**Term fequency (単語の出現頻度)**は、文字通り文書中に単語がでてくる頻度です。*tf*だけでも重み付けにより複数の方法が提案されています。最も単純な選択はドキュメント中のタームのカウントです。文書(ドキュメント)、単語(ターム)をそれぞれ$d, t$とします。


###  **バイナリ**

ブール型の頻度「frequencies」です。文章中に単語が存在するなら1にそれ以外なら0です。

```math
\text{tf}(t, d) = \left\{
\begin{array}{ll}
1 & (\text{if} \hspace{4pt} t \in d ) \\
0 & (\text{otherwise})
\end{array}
\right.
```

###  **カウント (raw count)**

文章中に単語が存在したとき単純にカウントしていく方法です。

$$
\text{tf}(t, d) = f\_{t, d}
$$


###  **単語の出現頻度 (term frequency)**

これがいわゆる*tf*です。上記のカウントを文章中のカウントの総和で割り出現頻度を求める方法です。

$$
\text{tf}(t, d) = \frac{f\_{t, d}}{\text{number of words in d}} = \frac{f\_{t, d}}{\sum\_{t' \in d} f\_{t', d}}
$$


他の方法では以下のようなものが提案されています。

### **対数正規化 (log normalization)**
カウントベースのものに対数をとることで正規化しています。
$$
\text{tf}(t, d) = \log{(1 + f\_{t, d})}
$$


### **二重K正規化 (double normalization K)**

K = 0.5とした場合が使用されるようです。

$$
\text{tf}(t, d) = K + (1 - K) \cdot \frac{f\_{t,d}}{\max\\{f\_{t', d} :t' \in d\\} }
$$


## Inverse document frequency (IDF)
**inverse document frequency (逆文書頻度)**は、単語が与える情報がどれくらいを測る指標です。よく出てくるもの値は下がり、レアなものに値が大きくなるように重みづけされます。一般語フィルタとして働きます。数式だと次式になります。

$$
\text{idf}(t, D) = \log \frac{N}{|\\{ d \in D:t \in d\\}|}
$$

ここで、Nはコーパス中の文書数です。分母は**df (document frequency)**であり、文書全体の単語の出現頻度です（**tf**は文章中の出現頻度）。

### **IDF**
 
良く紹介されるものは次の式です。

$$
\text{idf}(t, D) = \log \frac{N}{df\_{t}}
$$


### **smooth IDF**

sklearnの`TfidfVectorizer()`ではデフォルトで`smooth_idf = True`と平滑化しており、

$$
\text{idf}(t, D) = \log \left(\frac{1 + N}{1+ df\_t} \right) + 1
$$

となっています。他の方法として以下のものも提案されています。

### **idf-max**

$$
\text{idf}(t, D) = \log \left(\frac{\max\_{t' \in d} df\_t'}{1+ df\_t}\right) 
$$


### **probabilistic idf**

$$
\text{idf}(t, D) = \log \frac{N - df\_t}{df\_t}
$$

があります。ドキュメントの頻度が小さいときはほとんどIDFの値は変わりませんが、頻度が大きくなるとIDFの値はsmooth IDF > IDF > proba. IDF の順になります。proba. IDFだとdf = 50からIDFの値は負になります。

## TF-IDF
上記の二つの指標を掛け合わせたものです。

$$
\text{tfidf} (t, d, D) = \text{tf} (t,d) \cdot \text{idf}(t, D)  
$$

複数の組み合わせがあります。`document term weight (dtw)`と`query term weight (qtw)`があります。

| 手法 |  dtw | qtw | 
|-----|-----------------------------------------|-----------------------------------------------------------------------|
|1| $f_{t, d} \cdot \log \frac{N}{df_t} $  |  $ \left(0.5 + 0.5 \cdot \frac{f\_{t,d}}{\max\\{f\_{t', d} :t' \in d\\} } \right) \cdot  \log \frac{N}{df\_t} $ |
|2|  $ 1 + \log f\_{t, d} $ | $ \log (1 + \frac{N}{df\_t})$    |
|3|  $ (1 + \log f\_{t, d}) \cdot \log \frac{N}{df\_t} $| $ (1 + \log f\_{t, d}) \cdot \log \frac{N}{df\_t} $ |


## コード
例文としてsklearnにある文章を用います。

```python
corpus = [
    'This is the first document.',
    'This document is the second document.',
    'And this is the third one.',
    'Is this the first document?'
]
```

### sklearnを使う場合
こちらは非常に簡単で3行でtfidfの計算ができます。

```python
from sklearn.feature_extraction.text import TfidfVectorizer

tfidf = TfidfVectorizer()
x = tfidf.fit_transform(corpus)
```

tfidfの結果をみるために、データフレームに変換します。

```python
import pandas as pd

df_tfidf = pd.DataFrame(x.toarray(), columns=tfidf.get_feature_names())
```

```python
print(df_tfidf)
        and  document     first  ...       the     third      this
0  0.000000  0.469791  0.580286  ...  0.384085  0.000000  0.384085
1  0.000000  0.687624  0.000000  ...  0.281089  0.000000  0.281089
2  0.511849  0.000000  0.000000  ...  0.267104  0.511849  0.267104
3  0.000000  0.469791  0.580286  ...  0.384085  0.000000  0.384085
```

このように、単語ごとに重要度が産出されます。tf-idfの値を用いて、文章中の類似度を見ることができます。よくcosine 類似度が使用されます。tf-idfを求める際、内部で正規化されているので、線形カーネル($x^Ty$)に通すのと同じになります。

```math
\text{cosine}(x,y) = \frac{x^Ty}{||x||||y||} = \frac{x_1y_1 + \cdots x_n y_n}{\sqrt{x_1^2 + \cdots x_n^2}\sqrt{y_1^2 + \cdots y_n^2}}
```


```python
from sklearn.metrics.pairwise import cosine_similarity

print(cosine_similarity(x))
>> 
array([[1.        , 0.64692568, 0.30777187, 1.        ],
       [0.64692568, 1.        , 0.22523955, 0.64692568],
       [0.30777187, 0.22523955, 1.        , 0.30777187],
       [1.        , 0.64692568, 0.30777187, 1.        ]])
```
行列の成分が文書同士の類似度でるので、対称行列になります。例えば(1, 1), (1, 2), (1, 3), (1,4)での類似度がそれぞれ$1, 0.64, 0.31, 1$となっています。文書1と4は疑問文にしただけなので同じとなっています。


### 自作した場合
sklearnのものと同じになるか試してみます。corpus内の単語の出現頻度を数えるために`CountVectorizer()`を用います。

```python
from sklearn.feature_extraction.text import CountVectorizer
from sklearn.preprocessing import normalize
import numpy as np

wc = CountVectorizer()
x = wc.fit_transform(corpus)
wcX = np.array(x.toarray())
```

```python
df_wcX = pd.DataFrame(wcX, columns=wc.get_feature_names())
print(df_wcX)
>>
   and  document  first  is  one  second  the  third  this
0    0         1      1   1    0       0    1      0     1
1    0         2      0   1    0       1    1      0     1
2    1         0      0   1    1       0    1      1     1
3    0         1      1   1    0       0    1      0     1
```
このままだと**tf**ではなく、raw countの$f_{t,d}$になります。


```python
smooth_idf = True
norm_idf = True

# term frequency:
N = wcX.shape[0]
tf = np.array([wcX[i, :] / np.sum(wcX, axis=1)[i] for i in range(N)])

# inverse documents frequency
df = np.count_nonzero(wcX, axis=0)
idf = np.log((1 + N) / (1 + df)) + 1  if smooth_idf else np.log( N / df )  

# normalize
tfidf = normalize(tf*idf) if norm_idf else tf*idf
tfidf = pd.DataFrame(tfidf, columns=wc.get_feature_names())
```
※ 正規化しないと同じ結果になりません。

```python
print(tfidf)
>>
        and  document     first  ...       the     third      this
0  0.000000  0.469791  0.580286  ...  0.384085  0.000000  0.384085
1  0.000000  0.687624  0.000000  ...  0.281089  0.000000  0.281089
2  0.511849  0.000000  0.000000  ...  0.267104  0.511849  0.267104
3  0.000000  0.469791  0.580286  ...  0.384085  0.000000  0.384085
```



### CountVectorizerも使わない場合
corpus内の単語を数える前処理部分も自分でやってみます。本来は`scipy.sparse.csr_matrix`を使って処理すべきです。CountVectorizerを実装してみます。

```python
import re
from collections import defaultdict

documents = [re.sub('[.|?]', '', i.lower()) for i in corpus]
documents = [doc.split(' ') for doc in documents]

vocab = defaultdict()
vocab.default_factory = vocab.__len__
for doc in documents:
    feature_counter = {}
    for feature in doc:
        feature_idx = vocab[feature]
        if feature_idx not in feature_counter:
            feature_counter[feature_idx] = 1
        else:
            feature_counter[feature_idx] += 1

sorted_feature = sorted(vocab.items())
for new_val, term in enumerate(sorted_feature):
    vocab[term] = new_val

X = np.zeros(shape=(len(corpus), len(sorted_feature)), dtype=int)
for idx, doc in enumerate(documents):
    for word in doc:
        if word in vocab.keys():
            X[idx, vocab[word]] += 1
```

これで`CountVectorizer()`と同じ結果になります。同じ単語がでてきたら、カウントするようにします。`defaultdict()`は非常に便利ですね。



## 最後に
**tf-idf**の計算だけならsklearnを用いれば非常に簡単に行えることがわかります。ただ、**tf**と**idf**の組み合わせは地味に難しそうなので気を付けていく必要があります。

また、例文が簡単すぎるので楽にできますが、実際にはデータ整形やノイズ除去など地味で面倒な前処理もあるので、そこが大変だと思います。さらに、テキストの前処理はnltkの`WordNetLemmatizer`がありこちらも必須です。


## 参考文献

*  [Wikipedia TF-idf](https://en.wikipedia.org/wiki/Tf%E2%80%93idf)
* [sklern TfidfVectirzer](https://scikit-learn.org/stable/modules/generated/sklearn.feature_extraction.text.TfidfVectorizer.html)
* [How to process textual data using TF-IDF in python](https://medium.freecodecamp.org/how-to-process-textual-data-using-tf-idf-in-python-cd2bbc0a94a3)


[^1]: Breitinger, Corinna; Gipp, Bela; Langer, Stefan (2015-07-26). "Research-paper recommender systems: a literature survey"