Distance Based Hashingによる多次元データのK近傍探索

元ネタは
Vassilis Athitsos, Michalis Potamias, Panagiotis Papapetrou, and George Kollios. Nearest Neighbor Retrieval Using Distance-Based Hashing. In ICDE, pp. 327–336. IEEE, 2008.

Locally Sensitive Hashing(LSH)

多次元データのK近傍探索を行う場合に使われるのがLocally Sensitive Hashingである．同じく多次元データの探索技術として木構造の一つであるKD木を使ったものなどもある．

$\mathbb{X}$ をオブジェクトの空間とし， $\mathbb{X}$ 上で定義される距離測度を $D$ とする．また， $h:\mathbb{X} \rightarrow \mathbb{Z}$ となるハッシュ関数族を $\mathcal{H}$ で表す．ただし， $\mathbb{Z}$ は整数全体の集合を意味する．いま， $r_1 < r_2,\; p_1 > p_2$ であるとき，全ての $X_1, X_2 \in \mathbb{X}$ に対して，
$D(X_1, X_2) < r_1 \Rightarrow Pr_{h \in \mathcal{H}} (h(X_1) = h(X_2)) \ge p_1$
$D(X_1, X_2) > r_2 \Rightarrow Pr_{h \in \mathcal{H}} (h(X_1) = h(X_2)) \le p_2$
となる実数 $r1, r2, p1, p2$ が存在する場合，
$\mathcal{H}$ は局所性を持つ（locally sensitiveである）と言う*1．

局所性を持つ関数族 $\mathcal{H}$ が与えられたとき，
Locally Sensitive Hashing（LSH）のインデクシングは以下のように行われる．

$k, l > 0$ となる2つの整数を選択する
$l$ 個のハッシュ関数 $g_1, g_2, \dots, g_l$ を作成する．ただし，それぞれのハッシュ関数は $\mathcal{H}$ からランダムに選ばれた $k$ 個の関数のリストである．すなわち， $g_i(X) = (h_{i1}, h_{i2}(X), \dots, h_{ik}(X))$ となる．
$l$ 個のハッシュテーブル $t_i$ に， $t_1(g_1(X)) \leftarrow X,\: t_2(g_2(X)) \leftarrow X,\: \dots,\: t_l(g_l(X)) \leftarrow X$ として値を保存する．ここで， $t_i(a) \leftarrow b$ は，ハッシュテーブル $t_i$ の $a$ 番目のエントリに値 $b$ を保存する事を意味している．データ同士の値が近い場合，一定確率で同じハッシュ値が生成されるため，K近傍探索が行えるようになる．

LSHではこの $l$ 個のハッシュテーブルをもとにしてK近傍探索を行う．ただし， $k$ と $l$ はデータの種類によって最適な値が異なってくる．直感的には $k$ が低くなるとハッシュ値が衝突する確率が大きくなり，検索しなければならないデータの取りこぼしが少なくなってしまうが，余分なデータのハッシュ値まで衝突してしまうため，計算のコストが増大する．逆に， $k$ を大きくしすぎると，衝突が発生しにくくなってしまい， $l$ の値を大きくとらないとならない．

Distance Based Hashing

一般的にLSHではデータの検出の正確性やコストなどを厳密なものにするため，データ空間に三角不等式が成り立つなど，一定の制約が必要となる．Distance Based Hashingではデータ同士の距離が測定可能こと以外には，例えばデータの空間がユークリッド空間である必要があるなどといった特別な制約がない．以下ではDistance Based Hashingのインデクシング方法を説明する．

$\mathbb{X}$ をオブジェクトの空間とし， $\mathbb{X}$ 上で定義される距離測度を $D$ とする．いま， $X_1, X_2 \in \mathbb{X}$ となるランダムな値 $X_1, X_2$ が与えられたとき，データ空間から1次元の実数空間 $\mathbb{R}$ への写像 $F^{X_1, X_2}: \mathbb{X} \rightarrow \mathbb{R}$ を以下のように定義する．
$F^{X_1, X_2} = \frac{D(X, X_1)^2 + D(X_1, X_2)^2 - D(X, X_2)^2}{2D(X_1, X_2)}$

次に， $t_1, t_2 \in \mathbb{R}$ となる，2つの実数 $t_1, t_2$ が与えられたとき，二値の値を返す関数 $F^{X_1, X_2}_{t_1, t_2}$ を以下のように定義する．
$F^{X_1, X_2}_{t_1, t_2} = \left\{ \begin{array}{rl} 1 & \mathrm{if} F^{X_1, X_2}(X) \in [t_1, t_2] \\ 0 & \mathrm{otherwise} \end{array}$

ここで， $F^{X_1, X_2}_{t_1, t_2}$ が0となる確率が，だいたい0.5になるような $t_1, t_2$ の組み合わせの集合 $\mathbb{V}(X_1, X_2)$ を考える．すなわち，
$\mathbb{V}(X_1, X_2) = \{(t_1, t_2) | \mathrm{Pr}_{X \in \mathbb{X}}(F^{X_1, X_2}_{t_1, t_2}(X)) \approx 0.5\}$
となる集合である．

DBHでは以下のハッシュ関数族 $\mathcal{H}_{\mathrm{DBH}}$ を用いて，インデクシングを行う．
$\mathcal{H}_{\mathrm{DBH}} = \{F^{X_1, X_2}_{t_1, t_2} | X_1, X_2 \in \mathbb{X},\: (t_1, t_2) \in \mathbb{V}(X_1, X_2)\}$

あとは，LSHと同様に， $l$ 個のハッシュ関数からハッシュテーブルのインデクス値を生成する．また，DBHでもLSHと同様に $g$ 個のハッシュテーブルを用いる．

*1:Aristides Gionis, Piotr Indyk, and Rajeev Motwani. Similarity Search in High Dimensions via Hashing. In VLDB ’99: Proceedings of the 25th International Conference on Very Large Data Bases, pp. 518–529, San Francisco, CA, USA, 1999. Morgan Kaufmann Publishers Inc.