疎行列に対応したコサイン類似度行列計算の説明

コサイン類似度行列の計算では、比較データ数の二乗に比例してメモリや計算時間のリソースが必要になる。これとは逆に、大規模の問題ではデータの次元数も増え、データにゼロ要素が多くなるケースが多い。このような場合、疎行列に対応した類似度行列計算を行うことで計算時間が短縮できる。疎行列の度合いにもよるが、計算時間が1/100から1/1000になるケースもある。

類似度行列計算においてリソースを消費する部分は、メモリ：データ行列（m×n）、結果行列（m×m）、計算量：n×m×m/2のオーダーである。
本計算においては、まずデータ行列を非零要素のみ指定して与え、その部分のみ計算^※する。さらに結果もあらかじめ指定した類似度として有意な値以上のものだけ保存することでリソース消費を抑えている。なお、C言語で組めば10万行×10万次元レベルのものまでPC上・オンメモリで計算が可能になる。
^※ C++をはじめ、Java、PHP、Perlなど多くの言語系ではハッシュ構造をサポートしている。それを用いてデータを保存し、キーが一致する部分だけ計算することで時間を短縮できる。また疎の度合いが高い場合、より単純な線形リスト構造を用いた方がコンパイラ上での最適化・ベクトル化が的確に行われ計算コストをさらに抑えることができる。