まえがき

補足

類似度

類似度という概念は，２つの集合の要素がまさにどれだけ似ているかを数量化したものであり，距離とは，要素同士の離れ具合，従って非類似度とちかい概念と考えてもよい．

２つのデータが似ている度合いを，類似度の大きさや距離の近さといった数値にしてあらわすことで，クラスタ分析や，k-近傍法，多次元尺度構成法(MDS)をはじめとするいろいろな分析を行うことが可能となる．

詳しくは、ここで見てください。

もうちょっと、コサイン類似度について

sim= x・y /(|x|*|y|)
x・y=ベクトルx,yの内積
  =(x1*y1 + x2*y2 + .. + xn*yn) 
|x|=ベクトルxの長さ（ノルム）= sqrt(x・x)
  =原点からベクトルxの終点までのユークリッド距離
  =sqrt((x1-0)**2 + (x2-0)**2 + .. + (xn-0)**2) = sqrt( (x-0) * t(x-0) )

逆索引（転置インデクス）

検索エンジンに見てください。

問題定義

W：文書データベース

M：単語の種類の数

Wi：文書データベースの第i文書

Xi：文書WiのBOW(bag of words)のベクトル

Q:クエリ（キーワードの集合）

ここでは、クエリに含まれる｜Q|個のキーワードのうち、ｋ個を含む文書を選び出せ。

簡潔データ構造

一般的には、転置インデクスを用いて解かれる。簡単な検索エンジンには、この手法を用いている。

ただ、大規模Wに対して、検索結果は｜W|と比べるとすごく小さい。その時、転置インデクスは効率的でない。

Summary Vectorを用いる方法

この手法では、各文書を葉とする二分木を構築する。検索を早くするため、各ノードｖにM次元のSummary vector　ｙｖを用意する。したがって、単語ｊが下流のすべての文書に含まれていないときのみ、yv[j]=0となる。クエリが与えらてると、探索木を深さ優先でたどることによって検索が行われる。Summary vector yvとクエリに含まれる単語集合の共通部分の大きさがｋより少なくなれば、その時点で探索を中止する。

その手法はわかりやすく、簡単で実装できるが、大幅に高速化できる。

部分逆索引を用いる方法

　手法１の高速性は、各ノードで、summary vectorの情報を参照できるところから来ている。同様のアルゴリズムは、各ノードに部分的な逆索引を保持することによっても達成できる。

　クエリの単語集合をQ=(q1, q2, …, qm)とする。ノードｖにおいて、対応する逆索引により、単語qjが下流のすべての文書に含まれているか否かがわかる。その時点で、枝刈りを行って、探索を中止する。

ランク辞書

ランク辞書は、長さｎのビット配列Sを対象としたデータ構造であり、ランククエリrank(S,i)をサポートする。ランククエリを受け取ると、ランク辞書はS[1,i]における文字「１」の個数を返す。（文字「１」がわかったら、文字「０」を簡単で計算できる）。

参考：セルクトクエリ[Raman 02] verbatim[Okanohara 07]

アルゴリズム：

ビット配列を長さl:=(logn)^2の大ブロックに分割して、各大ブロックの開始位置を配列RL[0,...,n/l]に保持する。大ブロックは、さらに長さs:=logn/2の小ブロックに分割される。各小ブロックの、大ブロックに相対的な開始位置は、配列RS[0,...,n/s]に保持する。小ブロックの中のランクは、インテルのCPUで利用できるpopcountという命令を使って計算する。s[i,i+j]における１の数を,popcount(i,j)と置くと、ランククエリは次のように処理される。

関連リンク

1. Wavelet Treeのオープンソース
2. Sketchsort (for cosine distance)
3. Sketchsort (for Euclidean distance)
4. Sketchsort (for Jaccard-Tanimoto distance) 　(使えそう。アイテムのデータに対するSketchsortだ。自然言語処理において、アイテムは単語と同等するだろう。)