球哈希

球哈希：

球哈希不同与局部敏感哈希和密度敏感哈希基于随机超平面，球哈希时基于超球面的哈希技术。定义球哈希的函数族

,L为哈希编码的位数，其中每一个哈希函数事实上就是一个超球面，每个球哈希函数定义了一个球心和半径,每个超球面将空间划分为球内和球外两部分。哈希函数如下：其中d表示点与球心之间的欧式距离，点到球心的距离大于半径编码为0否则编码为1.

为了获得更高的准确性，每个哈希函数需要均衡划分原始空间，并且要保证哈希函数之间的独立性。因此构建哈希函数时需要遵守两个准则：

（1）.每个点被哈希函数编码为0或1的概率相等即：

（2）.哈希函数之间相互独立即，

球哈希独立性 ：

球哈希通过选择L个满足上述条件的超球面来形成哈希函数进行编码。

球哈希函数训练过程分为两个阶段：

第一阶段：

选择L个球心，初始球心的选择应该能大致反应数据集在空间中的分布情况，以减少后边的优化开销，球心选择后可以求出半径，半径一个简单计算方法是，计算每个点到球心的距离然后求和，接着求出平均值，用该平均值作为半径。

第二阶段优化球心和半径使哈希函数满足两个准则。

第一个阶段生成的哈希函数存在以下两个问题，两个球太近或者太远甚至重合。当两个球的位置靠的太近需要给一个斥力，否则给一个吸引里使满足独立性要求。

变量定义，其中m为数据集中点的个数：

表示第i个球中数据点个数

表示第j个球中数据点的个数

两个球的交集

第二阶段又分为两个过程，首先更新球心，然后再更新半径，不断重复这个过程，优化后最好的结果是，每个球都满足两个原则。有时候优化过程会导致过度拟合，为了防止过度拟合，需要定义误差范围，根据论文上的实验测试，误差值在左右效果很好。下面给出两个球之间的作用力。

求出一个球心到每个球心之间的作用力平均值：

计算出就是第i个球心需要移动的位置。每个球心都这样计算并且移动位置就更新了球心，然后再跟新半径。

可以把球哈希过程总结如下：

输入：cifar-10图片集的gist特征向量，容许的误差范围，哈希编码的位数L。

输出：哈希函数即L个球心和半径。

第一步：从数据集中随机选择L个数据点作为球心，最好能反应数据的大致分布情况。

第二步：计算出每个球的半径，满足每个球内部数据的个数和球外部的数据个数相等。

第三步：计算任意两个球之间的作用力。

第四步：更新球心位置

第五步：重复步骤二到四，知道满足