gameofdimension.github.io

View the Project on GitHub

simhash 原理

simhash 算法一般用来计算两个文本的相似度。


设想两个文本被表示成两个向量,向量中元素的值表示一个特征的权重,比如某个词的出现频数。

\[v_i=(w^{(i)}_1, w^{(i)}_2 .. w^{(i)}_D)\]

\[v_j=(w^{(j)}_1, w^{(j)}_2 .. w^{(j)}_D)\]

对于两个向量,如何估计其相似度?一种方法是计算余弦相似度。实际应用中,两两计算余弦相似度的开销可能过高,尤其是特征特别多的情况下。如果我们能将特征向量转换成较短的签名,可能可以提高计算效率。

对于 \(D\) 维随机向量 \(u\) ,\(v_i \cdot u\) 与 \(v_j \cdot u\) 符号相反的概率正比于 \(v_i, v_j\) 的夹角大小。

选定 \(n\) 个随机向量 \(u_{1..n}\) ,以下两个向量

\[(sgn(v_i \cdot u_1), sgn(v_i \cdot u_2) .. sgn(v_i \cdot u_n))^T\]

\[(sgn(v_j \cdot u_1), sgn(v_j \cdot u_2) .. sgn(v_j \cdot u_n))^T\]

的海明距离正比于 \(v_i, v_j\) 的夹角大小。

海明距离在计算机中计算效率非常高,如果同时适当控制 \(n\) 的大小,我们可以得到一种更高效估计文本相似度的方法。


simhash 将每个特征 hash 到一个大整数(比如 64 bit),得到 \(D\) 个大整数:

\[(hash(f_1), hash(f_2)..hash(f_D))\]

将每个大整数比特位的 \(0\) 换成 \(-1\) ,并表示成向量形式,上述向量可写成矩阵:

\(\left( \begin{array}{ccc} b^{(1)}_1 & b^{(2)}_1 & .. & b^{(D)}_1 \\ b^{(1)}_2 & b^{(2)}_2 & .. & b^{(D)}_2 \\ \vdots & \vdots & \vdots & \vdots \\ b^{(1)}_{64} & b^{(2)}_{64} & .. & b^{(D)}_{64} \end{array} \right)\)

根据 hash 函数的性质,其中的每一行可看成一个随机向量。

simhash 算法中将文档各特征的权重向量与该矩阵行向量做点乘并取符号,得到的 64 位向量作为该文档的 simhash ,文档之间的相似度用海明距离来度量。

可以看到这种做法原理上与上面取定随机向量的方法是一致的,唯一的区别在于并不是取定 64 个随机向量,而是通过对特征做 hash 的方法得到 64 个向量,这样得到的向量依然具有随机性质。