SPL实践：高维二值向量查找

A3：将每份数据转成长度为 512 的二值序列，形式如下：

A4：创建序表，name 字段是向量的标识，即文件名，data 是 512 维二值序列转成的由 8 个 long 型整数构成的序列，形式如下：

下面是第一行的 data 序列：

异或距离还有 1 个好处，相较于 cos 相似度，它只有位运算，没有除法运算，可以更快速地算出结果。

ANN算法通常分为两部分：

1. 聚类，即把数据按照某种规则分到不同的子集，使这些子集内的点距离较近，同时使两个子集内的点距离较远，通俗点说就是把扎堆的数据分成一组, 同时使各堆尽量远。

2. 查询，查询目标向量的最相似向量时，只要遍历距目标向量最近的部分子集即可，不必遍历全部数据，这样做有时可能会找不到最近的成员，但大概率能找到，这是权衡准确率和查找效率的结果。

我们决定自行研发聚类方法，大概过程如下：

尝试将数据拆分成N个子集，每个子集的成员数阈值是M。

1. 所有数据是集合X，随机选 1 个向量作为第一个基向量x₁，此时的集合也可以称作第一个子集X₁。

2. 从X₁中找到和基向量距离最远的向量，把它作为第二个子集X₂的基向量x₂。

3. 当有i个子集时，计算所有向量到每个基向量x_i的距离，距离哪个基向量最近就将该向量划分到哪个子集。

4. 第i+1 个子集X_i+1的基向量x_i+1是从已有的i个子集中找到成员数超过M且半径最大的子集中选择与其基向量最远的向量作为第i+1 个基向量x_i+1。（子集的半径定义为子集中所有成员到其基向量的最远距离）

5. 重复第 3、4 步，直到所有子集成员数都小于M或子集数达到N。

完成聚类后，目标向量x’的比对过程如下：

1. 计算x’与所有基向量x_i的距离，并按距离排序，取前K个最近子集。

2. 遍历K个子集的成员，计算他们与x’的距离，找到最近距离成员。

A6、A7：设置两个变量 X 和 G，分别存储每个向量的信息和聚类子集的信息。

A1：读入目标向量数据；

B21：全遍历最近距离成员。

变量 ath_data_num、ath_time、all_time、miss_hit 分别统计算法遍历数据量、算法耗时、全遍历耗时和算法最近距离不等于全遍历最近距离的次数。

A33-A36是上述统计量的平均值。

我们把算法找出的最近距离不等于全遍历计算出来最近距离的次数占全部目标向量数的比例（A36 的结果）叫做击不中率，作为算法有效性的考虑指标，显然击不中率越低说明这个算法有效性更高。

下面是 1 万个目标向量在聚类输出文件 "indexes_1.btx" 和 "indexes_m.btx" 上的统计结果：

数学分析表明，这个算法的理论复杂度和数据量的平方根成正比，数千万数据量的耗时不超过 100ms, 比如数据量扩大到 9000 万，相当于 90 万的 100 倍，算法耗时只扩大到原来的 10 倍，遍历 512 个子集时耗时在 20ms 左右，遍历 1024 个子集时耗时在 40ms 左右，而全遍历耗时会扩大 100 倍，需要 1800ms 左右。

有鉴于此，我们又设计了逐步聚类的方法，过程如下：

设子集成员数阈值为M

1. 第一个基向量是第一个向量，记为x_i，第一个子集记为X₁。

2. 遍历整个集合X，把X的成员加到最近的子集X_i中（距离相等时，随机加）。

3. 加到有X_i的成员数超过M时，对遍历过的数据拆分，使所有X_i成员数都小于等于M（拆分过程就是拆分式聚类过程）。

C21代码块：拆分式聚类过程。

查询过程和之前相同，这里不再赘述。

下面是同样数据逐步聚类的实验结果：

效果比拆分式聚类更好一些。

具体做法如下：

1. 按原来的比对方法找到每次随机聚类的最近距离成员；

2. 再从两个最近距离成员中选出距离更近的成员（相当于取两次结果的击不中成员的交集）。

B20代码块：两次次聚类结果的比对过程。

A3：统计各维度 1 的个数；

比对过程也差不多，有以下几点区别：

1. 目标向量要按敏感度排序后再转换成 long 型数据，同样取前p个 long 型数据；

2. 按原来的方式从前p个 long 型数据选出距离最近的topn个向量，因为只计算前p个 long 的距离，无法确定前p个 long 的最近距离成员一定是全维度最近距离成员，所以取前topn个向量，使其大概率包含全维度最近距离成员，结合交集方法，可以进一步增加这一概率；

3. 计算这topn个向量的全维度距离，找到最近距离成员;

4. 用交集方法降低击不中率。

B23代码块：比对过程;

维度排序减少了横向计算量，聚类也提速不少。

下面是 90 万数据综合采用逐步聚类、交集方法、维度排序的比对结果：