Scipyの疎行列を使った文書間コサイン類似度の計算

私のブログが引用されているこんな記事
(未解決)大規模疎行列のコサイン類似度 – studylog/北の雲
を見つけたので乗っかってみる。しかも、未解決って書いてあるし。

文書群データが疎行列\(A\)で与えられているとする。ここで、各行が文書を、各列が語を表しているとする。ここで文書間のコサイン類似度を総当りで計算したいものとして、その方法を示す。

\(A\)の各行をベクトルと見てL2ノルムで正規化したものを\(\tilde{A}\)とすると、コサイン類似度を示す行列は
\[ \tilde{A} \tilde{A}^T \]
で計算できる。

では\(\tilde{A}\)をどう計算するかだが、ブロードキャスティングを使ってインプレイスで求めるのがいいかと思う。以下にサンプルコードを示す。

from scipy.sparse import lil_matrix
import numpy as np

a = lil_matrix((4, 5))
a[0,2]=2; a[0,4]=6; a[1,0]=4; a[1,1]=9; a[1,2]=5
a[1,4]=4; a[2,0]=2; a[2,3]=4; a[3,0]=9; a[3,1]=4

norms = np.sqrt(a.multiply(a).sum(axis=1))
for i in range(a.shape[0]):
    a[i, :] /= norms[i]

sims = a.dot(a.T)
print(sims.toarray())

ここで、4行目～6行目では適当な疎行列を用意している。8行目～10行目では各行をインプレイスで正規化している。12行目のsimsにはコサイン類似度を表す行列が入る。

注意すべきなのは、結果として出てくるsimsは型として疎行列になるのだが、かなり密になると思われるので、文書数が多いときは全ペアについてコサイン類似度計算しようというのはそもそも計算量的にもメモリ量的にも現実的ではない。実際上記リンク先に具体的な問題のサイズが書かれているが、そのくらいの大きさだとまともに動かないだろう。kNNなどを使って近いところだけを求めるのが現実的だと思うが、scipy.sparse.NearestNeighborsではコサイン類似度の指定がうまく動かないようだ（ドキュメントには書かれているのだが）。

そこで、正規化してからL2ノルムでkNNすればよい。なぜなら各ベクトルのL2ノルムが1であるという前提の元、L2ノルムとコサイン類似度には次のような関係がある。
\begin{align}
\lVert x-y \rVert_2^2 &= \lVert x \rVert_2^2 + \lVert y \rVert_2^2 – 2 x\cdot y\\
&=2- 2\mathrm{cossim}(x,y)
\end{align}

つまりL2ノルムでの昇順ソートはコサイン類似度の降順ソートと一致する。

Pythonを使った機械学習について、詳しくはここらへんをどうぞ：