PQ算法

PQ（productquantization）算法：乘积量化，这里的乘积为笛卡尔积；从字面理解包括了两个过程特征的分组量化过程和类别的笛卡尔积过程。它属于ANN(approximatenearest neighbor)算法。与它相关的算法有E2LSH（EuclideanLocality-SensitiveHashing）， KD-trees，K-means。

假设有一个数据集： 由n个D维向量组成（如：n行D列）

K-means：的做法就是给定类别数目K，对整个数据集进行聚类，目标函数是所有样本到类中心的距离和最小，迭代计算优化目标函数，得到K个类中心和每个样本所属的类别。

PQ算法：目标函数不变和K-means一样，是所有样本到类中心的距离和最小，迭代计算优化目标函数；但是它把原来的向量（n * D）空间分解为若干个低维向量空间的笛卡尔积，并对分解得到的低维向量空间分别做量化（quantization）。这样每个向量就能由多个低维空间的量化code组合表示。