通过这篇文章我们主要回答以下几个问题：
1. LSH解决问题的背景，即以图片相似性搜索为例，如何解决在海量数据中进行相似性查找？
2. 图像相似性查找的连带问题：相似性度量，特征提取；
3. LSH的数学分析，即局部敏感HASH函数的数学原理，通过与、或构造提升查找的查全率与查准率
4. LSH具体实现，对着代码一步一步学习算法的具体实现
一、问题背景介绍
LSH即Locality Sensitive hash，用来解决在海量数据中进行相似性查找的问题，以图片搜索为例，见下图，用户向百度图搜提交待搜索图片，百度图搜将相似的图片返回展示。
要实现这样一个应用，需要考虑以下几个问题：
1. 提取用户提交的图片特征，即将提交图片转换成一个特征向量；
2. 预先将所有收集到的图片进行特征提取；
3. 把步骤1中提取的特征与步骤2中的特征集合，进行比对，并记录比对的相似性值；
4. 对相似值由大到小排序，返回相似度最高的作为检索结果。
问题1，2是一个图片特征提取的问题，与LSH无关。LSH主要解决问题3与问题4，在海量特征集中找到相似特征。以下简述问题1，2，详细讲解问题3，4。
二、图像的特征提取
图像的特征提取属于个图像学研究领域，有很多经典的图像算法，分别从图像颜色，角度，形态不同角度进行图像的特征描述，包括最近流行的深度学习方法也可以做类似的事情。这里介绍一种比较容易理解的2种方法，一种是传统的颜色直方图，一种是自编码器。
1. 颜色直方图就是将RGB图像中出现的颜色进行统计，将一张图像描述中一个256维度的特征向量，如下图所示：
2. 自编码器的思想是通过神经网络进行特征提取，提取出针对学习样本的通用特征降维方法，用训练得到的统一方法对待测图像进行降维处理，得到一个特征向量。
如图所示，神经网络的2端通过相同的数据限制，学习到中间的隐藏层权重，通过使用降维再升维的方法，使隐藏层输出最大限度的保存图像的主要特征，以使还原后的图像与原图像误差达到最小。
自编码器完成训练后，使用输入层到隐藏层的权重向量进行特征提取，将图像数据作为输入层输入，将隐藏层输出作为图像特征，以此作为图像的特征。
三、特征的相似性比较
相似是一个形容词，对于一对图像使用不同的评价标准可能得到不同相似度量值。比如对于不同的业务场景，如相貌识别、形态识别、背景识别所采用相似度量方法可能完全是不同的。
同样从数学的角度进行特征的相似性比较也有不同的方法，如果把特征向量看成空间的一个点，那么可以把度量2个向量的相似性看做度量多维空间中的2个点的距离，这些度量方法包括：
欧式距离
Jaccard距离
余弦距离
曼哈顿距离
闵可夫斯基距离
作为一个距离的度量函数d，必须满足以下一些性质
• d(x,y)>=0,距离非负性
• d(x,y)=0当切仅当x=y,只有点到自身的距离为0，其他距离都大于0
• d(x,y)=d(y,x),距离对称性
• d(x,y)<=d(x,z)+d(z,y),满足三角不等式
当完成了第1，第2步以后，即能提取图像的特征，又找到了方法可以度量图像特征的相似后，剩下的事情就是要预先将图像库的所有图像一一提取特征，在搜索时用同样的特征提取方法对待测图像提取特征，然后将待搜特征循环与图像库中的图像特征集合比较，找到相似度最高的。
四、局部敏感hash
由于图像库的特征通常数量很大，循环比较的时间复杂度过高，无法满足应用的响应需要。因此，必须要使用类似的索引技术来降低搜索的复杂性，多维索引有一种叫KD树的技术可以做类似的事情，但是对于图像搜索的场景另外一种LSH的技术更有用。
回顾问题的背景，现在已经预先将图像库中的图像都转换成了特征并组成特征集合（所有特征的维度都是相同的）：
[[20,….,………….61],
…,
[[31,….,………….55]]
同时也用相同的特征提取算法提取了用户提交图像的特征，如：
[1,2,3,4,5,6,….,60]
现在的问题是从第一个特征集中找到与用户图像特征相似度最高的一些特征。
用一个p稳定分布（p-stable distribution）定义如下：
• 定义：对于一个实数集R上的分布D，如果存在P>=0，对任何n个实数v1,…,vn和n个满足D分布的变量X1,…,Xn，随机变量ΣiviXi（向量点乘，一个整数）和(Σi|vi|p)1/pX（p(阶)范数，一个整数）有相同的分布，其中X是服从D分布的一个随机变量，则称D为 一个p-稳定分布。比如p=1是柯西分布，p=2时是高斯分布。
这里面有几个基本问题必须要进行背景了解，向量点乘、范数、正态分布、同分布。
向量点乘：2个向量相同维度相乘，再相加。
范数：是具有“长度”概念的函数。向量的0范数，向量中非零元素的个数。向量的1范数，为绝对值之和。向量的2范数，就是通常意义上的模。
正态分布：这个太长见了，不多解释。
同分布：2个数列同分布，意味着呈线性关系的两个数列，可以理解为同比例缩放。
用通俗的语言进行解析上述定义就是：
取满足正态分布的一个数列，与某个特征向量做向量点乘，得到一个数值，这个数值与这个特征向量本身的2阶范数（即向量每一维的元素绝对值的平方和再开方，代表向量的长度，也是一个数值），有同分布的性质。
假设有两个图像特征X1,X2，用这两个特征分别与同一个正态分布的数列做向量点乘，所得到的2个数值在一维上的距离与X1,X2在多维上的欧氏距离是同分布的。
设正态分布数值为D，待计算的两个图像特征为X1,X2，则有：
|X1.D-X2.D| = (X1 – X2).D 同分布于 (X1 – X2) 的2阶范数(即长度)。
(X1 – X2)是向量相减，得到一个新的向量，代表两个特征的距离向量。
用图像库中N个图像的N个特征分别与同一个正态分布的数列做向量点乘，得到的N个特征在一维上的点，我们用在一维上的点之间的距离度量多维空间的距离，当然这种相近是概率意义下的相近。为了简化计算，把一维上的线划分成段；为了提高算法的稳定性，向量点乘后增加一个随机的噪音。于是得到了一个新的哈希函数：
a是p稳定生成的随机数列
b是(0,r)里的随机数, noise/随机噪音
r为直线上分段的段长
V待计算特征向量，即图像提取出来的特征
像这样一类hash函数称之为局部敏感hash函数，下面给出局部敏感hash函数的定义：
将这样的一族hash函数 H={h:S→U} 称为是(d1,d2,p1,p2)敏感的，如果对于任意H中的函数h，满足以下2个条件：
– 如果d(O1,O2)<d1，那么Pr[h(O1)=h(O2)]≥p1
– 如果d(O1,O2)>d2，那么Pr[h(O1)=h(O2)]≤p2
其中，O1,O2∈S，表示两个具有多维属性的数据对象，d(O1,O2)为2个对象的相异程度，也就是相似度。
通俗的讲就是：
• N个值足够相似时
– 映射为同一hash值的概率足够大；
• N个值不足够相似时
– 映射为同一hash值的概率足够小
可以用下图来表示：
局部敏感HASH函数必要要满足如下条件：
[1] 进行相似性搜索时，在概率上可以保证返回值的相似性
[2] 函数族中的各函数，返回值在概率上相互独立，概率独立可以带来以下好处
a) 统计独立，满足叠加多个函数，提高查准率
b) 通过组合能够避免伪正例、伪反例
[3] 搜索效率
a) hash比对比线性查询快
五、概率相似度度量与调节（与构造与或构造）
既然是在概率意义下相似性度量，必然会存在着相近样本被hash到不同的hash值情况，同时也必然会存在不相近的样本被hash到相同的hash值情况，前一种称为伪反例，向一种称为伪正例。
伪正例通过与构造解决，即通过多个hash函数，计算同一个特征的多个hash值，只有当多个hash函数均相同时，才认为特征相似。这有效避免了不相似的特征被判定为相似特征的情况。
伪反例通过或构造解决，即通过多个hash函数，计算同一个特征的多个hash值，只有多个hash函数有一个hash值相同时，即认为特征相似。这有效避免了相似的特征被判定为不相似特征的情况。
结合与构造与或构造2种方案，可以生成r*b个函数，每r个hash函数带表一组与构造，每b组hash函数族代表一组或构造，当满足一个或构造后特征判定为相似。设一组特征hash的相似概率为s，则通过hash函数与/或构造后的相似概率为：
1-（1-s^r）^b
在这个概率函数中，s与hash函数的精度相关，属于不可调节参数。当r越大时，相似概率越小，当b越大时，相似概率越大。r与b作为LSH的超参数可以根据实际情况进行相应的调节。
六、代码分析
下面的LIRE上找到一份LSH的代码实现，这份代码实现清晰明了，比网上大多数开源出来的代码要更容易理解。
1 /*
2 * This file is part of the LIRE project: http://www.semanticmetadata.net/lire
3 * LIRE is free software; you can redistribute it and/or modify
4 * it under the terms of the GNU General Public License as published by
5 * the Free Software Foundation; either version 2 of the License, or
6 * (at your option) any later version.
7 *
8 * LIRE is distributed in the hope that it will be useful,
9 * but WITHOUT ANY WARRANTY; without even the implied warranty of
10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11 * GNU General Public License for more details.
12 *
13 * You should have received a copy of the GNU General Public License
14 * along with LIRE; if not, write to the Free Software
15 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
16 *
17 * We kindly ask you to refer the any or one of the following publications in
18 * any publication mentioning or employing Lire:
19 *
20 * Lux Mathias, Savvas A. Chatzichristofis. Lire: Lucene Image Retrieval 鈥�
21 * An Extensible Java CBIR Library. In proceedings of the 16th ACM International
22 * Conference on Multimedia, pp. 1085-1088, Vancouver, Canada, 2008
23 * URL: http://doi.acm.org/10.1145/1459359.1459577
24 *
25 * Lux Mathias. Content Based Image Retrieval with LIRE. In proceedings of the
26 * 19th ACM International Conference on Multimedia, pp. 735-738, Scottsdale,
27 * Arizona, USA, 2011
28 * URL: http://dl.acm.org/citation.cfm?id=2072432
29 *
30 * Mathias Lux, Oge Marques. Visual Information Retrieval using Java and LIRE
31 * Morgan & Claypool, 2013
32 * URL: http://www.morganclaypool.com/doi/abs/10.2200/S00468ED1V01Y201301ICR025
33 *
34 * Copyright statement:
35 * ====================
36 * (c) 2002-2013 by Mathias Lux (mathias@juggle.at)
37 * http://www.semanticmetadata.net/lire, http://www.lire-project.net
38 *
39 * Updated: 02.06.13 10:27
40 */ 41 42 package net.semanticmetadata.lire.indexing.hashing;
43 44 import java.io.*;
45 import java.util.zip.GZIPInputStream;
46 import java.util.zip.GZIPOutputStream;
47 48 /**
49 * <p>Each feature vector v with dimension d gets k hashes from a hash bundle h(v) = (h^1(v), h^2(v), 
, h^k(v)) with
50 * h^i(v) = (a^i*v + b^i)/w (rounded down), with a^i from R^d and b^i in [0,w) <br/>
51 * If m of the k hashes match, then we assume that the feature vectors belong to similar images. Note that m*k has to be bigger than d!<br/>
52 * If a^i is drawn from a normal (Gaussian) distribution LSH approximates L2. </p>
53 * <p/>
54 * Note that this is just to be used with bounded (normalized) descriptors.
55 *
56 * @author Mathias Lux, mathias@juggle.at
57 * Created: 04.06.12, 13:42
58 */ 59 public class LocalitySensitiveHashing {
60 private static String name = "lshHashFunctions.obj";
61 // 一组正态分布数列，长250，比实际用到的长一些
62 private static int dimensions = 250;
// max d
63 // 50组正态分布数列（供与/或构造共同使用）
64 public static int numFunctionBundles = 50;
// k
65 // 一维线段的长度，公式中的r
66 public static double binLength = 10;
// w
67 68 private static double[][] hashA =
null;
69 70 71 72 // a
73 private static double[] hashB =
null;
// b
74 private static double dilation = 1d;
// defines how "stretched out" the hash values are.
75 76 /**
77 * Writes a new file to disk to be read for hashing with LSH.
78 *
79 * @throws java.io.IOException
80 */ 81 // 产生hash函数，并存储到磁盘上
82 public static void generateHashFunctions()
throws IOException {
83 File hashFile =
new File(name);
84 System.out.println(hashFile.getAbsolutePath());
85 if (!hashFile.exists()) {
86 ObjectOutputStream oos =
new ObjectOutputStream(
new GZIPOutputStream(
new FileOutputStream(hashFile)));
87 oos.writeInt(dimensions);
88 oos.writeInt(numFunctionBundles);
89 // 产生点乘结果相加的随机数噪声
90 for (
int c = 0; c < numFunctionBundles; c++) {
91 oos.writeFloat((
float) (Math.random() * binLength));
92 }
93 // 产生 numFunctionBundles 组正态分布数列，每组dimensions个数字
94 for (
int c = 0; c < numFunctionBundles; c++) {
95 for (
int j = 0; j < dimensions; j++) {
96 oos.writeFloat((
float) (drawNumber() * dilation));
97 }
98 }
99 oos.close();
100 }
else {
101 System.err.println("Hashes could not be written: " + name + " already exists");
102 }
103 }
104 105 // 指定路径名版本
106 public static void generateHashFunctions(String name)
throws IOException {
107 File hashFile =
new File(name);
108 if (!hashFile.exists()) {
109 ObjectOutputStream oos =
new ObjectOutputStream(
new GZIPOutputStream(
new FileOutputStream(hashFile)));
110 oos.writeInt(dimensions);
111 oos.writeInt(numFunctionBundles);
112 for (
int c = 0; c < numFunctionBundles; c++) {
113 oos.writeFloat((
float) (Math.random() * binLength));
114 }
115 for (
int c = 0; c < numFunctionBundles; c++) {
116 for (
int j = 0; j < dimensions; j++) {
117 oos.writeFloat((
float) (drawNumber() * dilation));
118 }
119 }
120 oos.close();
121 }
else {
122 System.err.println("Hashes could not be written: " + name + " already exists");
123 }
124 }
125 126 /**
127 * Reads a file from disk and sets the hash functions.
128 *
129 * @return
130 * @throws IOException
131 * @see LocalitySensitiveHashing#generateHashFunctions()
132 */133 public static double[][] readHashFunctions()
throws IOException {
134 return readHashFunctions(
new FileInputStream(name));
135 }
136 137 // 读取存储在磁盘上LSH hash函数值，计算图像特征时反复使用同一套LSH函数
138 public static double[][] readHashFunctions(InputStream in)
throws IOException {
139 ObjectInputStream ois =
new ObjectInputStream(
new GZIPInputStream(in));
140 dimensions = ois.readInt();
141 numFunctionBundles = ois.readInt();
142 double[] tmpB =
new double[numFunctionBundles];
143 for (
int k = 0; k < numFunctionBundles; k++) {
144 tmpB[k] = ois.readFloat();
145 }
146 LocalitySensitiveHashing.hashB = tmpB;
147 double[][] hashFunctions =
new double[numFunctionBundles][dimensions];
148 for (
int i = 0; i < hashFunctions.length; i++) {
149 double[] functionBundle = hashFunctions[i];
150 for (
int j = 0; j < functionBundle.length; j++) {
151 functionBundle[j] = ois.readFloat();
152 }
153 }
154 LocalitySensitiveHashing.hashA = hashFunctions;
155 return hashFunctions;
156 }
157 158 /**
159 * Generates the hashes from the given hash bundles.
160 *
161 * @param histogram
162 * @return
163 */164 // 计算一个特征的numFunctionBundles组hash特征
165 public static int[] generateHashes(
double[] histogram) {
166 double product;
167 int[] result =
new int[numFunctionBundles];
168 for (
int k = 0; k < numFunctionBundles; k++) {
169 product = 0;
170 // 1. 向量点乘
171 for (
int i = 0; i < histogram.length; i++) {
172 product += histogram[i] * hashA[k][i];
173 }
174 // 2. 加上随机噪音，除一维线段长度
175 result[k] = (
int) Math.floor((product + hashB[k]
/*加上随机噪音*/) / binLength
/*除一维线段长度*/);
176 }
177 return result;
178 }
179 180 181 /**
182 * Returns a random number distributed with standard normal distribution based on the Box-Muller method.
183 *
184 * @return
185 */186 // Box-Muller算法，产生正态分布数
187 private static double drawNumber() {
188 double u, v, s;
189 do {
190 u = Math.random() * 2 - 1;
191 v = Math.random() * 2 - 1;
192 s = u * u + v * v;
193 }
while (s == 0 || s >= 1);
194 return u * Math.sqrt(-2d * Math.log(s) / s);
195 // return Math.sqrt(-2d * Math.log(Math.random())) * Math.cos(2d * Math.PI * Math.random());
196 }
197 198 public static void main(String[] args) {
199 try {
200 generateHashFunctions();
201 }
catch (IOException e) {
202 e.printStackTrace();
203 }
204 }
205 206 207 }
208
七、总结
本文描述了LSH的适用场景、算法原理与算法分析，并配合源代码帮助读者理解算法原理，了解算法的实现要点。
程序员长期养成了从代码反向学习知识的习惯，但是到了人工智能时代这种学习方式受到了很大的挑战，在一些复杂的数学背景知识面前，先了解背景知识是深入掌握的前提。
参考文献：
Website:
[1] http://people.csail.mit.edu/indyk/ （LSH原作者）
[2] http://www.mit.edu/~andoni/LSH/ (E2LSH)
Paper:
[1] Approximate nearest neighbor: towards removing the curse of dimensionality
[2] Similarity search in high dimensions via hashing
[3] Locality-sensitive hashing scheme based on p-stable distributions
[4] MultiProbe LSH Efficient Indexing for HighDimensional Similarity Search
[5] Near-Optimal Hashing Algorithms for Approximate Nearest Neighbor in High Dimensions
Tutorial:
[1] Locality-Sensitive Hashing for Finding Nearest Neighbors
[2] Approximate Proximity Problems in High Dimensions via Locality-Sensitive Hashing
[3] Similarity Search in High Dimensions
Book:
[1] Mining of Massive Datasets
[2] Nearest Neighbor Methods in Learning and Vision: Theory and Practice
Cdoe:
[1] http://sourceforge.net/projects/lshkit/?source=directory
[2] http://tarsos.0110.be/releases/TarsosLSH/TarsosLSH-0.5/TarsosLSH-0.5-Readme.html
[3] http://www.cse.ohio-state.edu/~kulis/klsh/klsh.htm
[4] http://code.google.com/p/likelike/
[5] https://github.com/yahoo/Optimal-LSH
[6] OpenCV LSH（分别位于legacy module和flann module中）
posted on 2018-02-24 13:10
胡满超 阅读(8777)
评论(0) 编辑 收藏 引用 所属分类:
算法 、
搜索引擎