1. 相似性度量
两个向量A和B的相似性度量 \begin{align} A &= (a_1,a_2,a_3,…,a_n) \\ B &= (b_1,b_2,b_3,…,b_n) \end{align} 相似度用符号S表示，S越大表示A和B越相似
2. 哈希函数
2.1 定义
假设二进制编码长度为位，那么需要个哈希函数 每个哈希函数代表一个超球，当样本与球心的相似系数大于等于球半径时，哈希函数的结果为，否则为 设第个哈希函数代表的超球的球心为，半径为，有哈希函数 \begin{align} h_i(x)= \left\{ \begin{aligned} & 0 & S(p_i, x) < r_i \\ & 1 & S(p_i, x) \geq r_i \end{aligned} \right. \end{align}
对于每个数据点，使用这C个哈希函数能得到长度为C的二进制编码
2.2 编码长度
假设用户有N个数据点，要计算每个点的K个邻近点 那么希望一个桶里平均有3K个，应该有个桶 \begin{align} C = \lfloor log_2\frac{N}{3K} \rfloor \end{align}
2.3 球心与半径
2.3.1 求解主流程
定义
\begin{align} o_i &= | \{ x|h_i(x)=1\}| \\ o_{i,j} &= | \{ x|h_i(x)=1,h_j(x)=1\}| \end{align}
理想的超球应满足
- 均匀划分数据，，即
- 球之间两两独立，，即
由于随机子集可以近似完整数据集的分布，因此随机选取数据子集
这里取 ，1e4为人为设定的参数
接下来以这个子集为优化目标，得到C个哈希函数
算法步骤
- 在子集中随机选取C个点，作为C个超球的球心
- 调整C个超球的半径，使得在子集满足条件『均匀划分数据』
- 迭代
3.1. 调整C个超球的球心使得在子集逼近条件『两两独立』
3.2. 调整C个超球的半径，使得在子集满足条件『均匀划分数据』
2.3.2 调整半径——均匀划分数据
固定球心，求球半径，显然为与子集中所有点相似度的中位数
并行设计：
- 使用M个map计算每个数据点与C个球心的相似度
- Reduce，得到C个中位数作为半径
2.3.3 调整球心——两两独立
很直观的做法
- 当时，两球应受到一个斥力
- 当时，两球应受到一个引力
定义球i受到的来自球j的力
\begin{align} f_{i\leftarrow j}=\frac{1}{2}\frac{o_{i,j}-m/4}{m/4}(p_i-p_j) \end{align}
显然
\begin{align} f_{j\leftarrow i}=-f_{i\leftarrow j} \end{align}
并行设计：
- 使用m个map，每个map处理一条数据，每条数据计算C个哈希函数，取其中哈希值为1的哈希函数ID两两配对，作为map的输出流
- reduce操作，得到任意两个哈希函数i和j对应的
- 使用个map，得到任意两个超球之间的力
- reduce，得到每个超球受到的合力，并更新球心
3. 查询
- 将query转为二进制编码
- 用二进制编码对应的桶中的数据更新堆中的top K
- 如果堆大小等于K，则结束，否则进入下一步
- 按照球面海明距离从小到大遍历桶，直到堆的大小等于K
x和y为两个二进制串，其球面海明距离为: \begin{align} d=\frac{(x异或y)中的1的数量}{(x\&y)中的1的数量} \end{align}
4. 杂谈
在实际工业环境中，数据通常是稀疏的，因此这个KNN方案作用有限，也只有在大公司内会有用了。