Faiss 基础构建块

Faiss 的核心是几个高效实现的基础算法，包括：k-means 聚类（K均值）、PCA（主成分分析）、PQ（乘积量化）编码与解码。

聚类（Clustering）​

Faiss 提供了高效的 K-means 聚类实现。要对存储在二维张量 x 中的一组向量进行聚类，可以这样操作：

ncentroids = 1024  # 聚类中心数量
niter = 20         # 迭代次数
verbose = True     # 是否打印详细日志
d = x.shape[1]     # 向量维度
kmeans = faiss.Kmeans(d, ncentroids, niter=niter, verbose=verbose)
kmeans.train(x)

聚类训练后得到的**质心（centroid）**存储在 kmeans.centroids 中。

聚类目标函数的值（对于 K-means 是总的平方误差）在每次迭代的结果会保存在 kmeans.obj，更详细的统计信息放在 kmeans.iteration_stats。

若希望在 GPU 上运行，只需在 Kmeans 构造函数中加入 gpu=True，会自动使用所有可用的 GPU。

其它配置选项​

Kmeans 对象主要是 C++ Clustering 对象的一个封装。你可以通过构造函数设置以下参数：

• nredo：聚类训练多次，保留表现最好的质心（按目标函数挑选）
• verbose：是否显示更详细的日志
• spherical：是否执行球形 K-means（每次迭代都将质心做 L2 归一化）
• int_centroids：将质心参数四舍五入为整数
• update_index：每次迭代后都重新训练索引吗？
• min_points_per_centroid / max_points_per_centroid：如果低于这个数会有警告；高于则对训练集进行子采样
• seed：设置随机数生成器的种子

向量归属（Assignment）​

聚类完成后，想知道输入向量 x 各自最接近的质心，可以这样操作：

D, I = kmeans.index.search(x, 1)

这里，I 返回每个输入向量最近的质心编号；D 则是对应的 L2 距离的平方。

找到离质心最近的若干原始点​

如果你想查找给定质心在原始数据中最近的 15 个点：

index = faiss.IndexFlatL2(d)
index.add(x)
D, I = index.search(kmeans.centroids, 15)

此时，I 的形状为 (质心数, 15)，每行是距离对应质心最近的 15 个原始样本的下标。

在 GPU 上进行聚类​

你可以通过 gpu=True（全部 GPU）或如 gpu=3（3 块 GPU）等方式，在多 GPU 上进行 K-means 聚类。只需在 Kmeans 构造函数中配置即可。

计算主成分分析（PCA）​

假设我们想把 40 维的向量降到 10 维，可以这样操作：

# 随机训练样本
mt = np.random.rand(1000, 40).astype('float32')
mat = faiss.PCAMatrix(40, 10)
mat.train(mt)
assert mat.is_trained
tr = mat.apply(mt)
# 可以打印 tr 的每一列平方和，观察主成分的能量逐步减少
print((tr ** 2).sum(0))

量化器（Quantizers）​

量化器对象继承自 Quantizer，通常有以下常用方法（详见 impl/Quantizer.h）：

• train：在训练样本（二位矩阵）上训练量化器
• compute_codes 和 decode：分别是编码器和解码器。编码通常是有损的，会为每个输入向量生成一个 uint8(无符号8位) 类型的代码矩阵。
• get_DistanceComputer：返回一个 DistanceComputer 对象（见下文）。

量化器对象的状态即为训练产生的码本（codebook）或归一化系数。其 code_size 字段表示每个向量编码后占用的字节数。

量化器的类型​

Faiss 支持的量化器主要有：

• ScalarQuantizer：对每个向量分量（维度）进行独立线性范围的量化
• ProductQuantizer：对子向量做矢量量化（将原始向量分为子块分开量化）
• AdditiveQuantizer：将向量编码为一组码本条目的和。详见Additive Quantizers。
  • ResidualQuantizer、LocalSearchQuantizer、ProductAdditiveQuantizer 等属于加法量化器的子类，不同训练方式。

每种量化器都有其对应的索引类型，用于存储量化后向量的集合。

除 ScalarQuantizer 外，所有量化索引还存在 FastScan 版本（快速扫描），详情参考Fast accumulation of PQ and AQ codes。

距离计算器（Distance computers）​

部分量化器提供了 DistanceComputer 对象。它主要用于在已编码的情况下，高效计算给定向量与大量压缩后代码之间的距离。这样通常可以通过预计算查找表大幅提升距离计算速度。

DistanceComputer 提供：

• set_query：设置当前要比对的原始（未编码）向量
• distance_to_code：给定编码计算实际距离

示例：PQ 编码 / 解码​

ProductQuantizer（乘积量化器）可以对向量进行编码和解码：

d = 32  # 向量维度
cs = 4  # 每个向量编码长度（单位：字节）

# 训练集
nt = 10000
xt = np.random.rand(nt, d).astype('float32')

# 待编码数据（也可以与训练集相同）
n = 20000
x = np.random.rand(n, d).astype('float32')

pq = faiss.ProductQuantizer(d, cs, 8)
pq.train(xt)

# 编码
codes = pq.compute_codes(x)

# 解码为原始数据的近似还原
x2 = pq.decode(codes)

# 计算重构误差
avg_relative_error = ((x - x2)**2).sum() / (x ** 2).sum()

标量量化（Scalar Quantizer）用法类似：

d = 32  # 向量维度

# 训练集
nt = 10000
xt = np.random.rand(nt, d).astype('float32')

# 待编码数据（可以和训练集相同）
n = 20000
x = np.random.rand(n, d).astype('float32')

# QT_8bit 为每一维分配8比特；也可用 QT_4bit
sq = faiss.ScalarQuantizer(d, faiss.ScalarQuantizer.QT_8bit)
sq.train(xt)

# 编码
codes = sq.compute_codes(x)

# 解码
x2 = sq.decode(codes)

# 计算重构误差
avg_relative_error = ((x - x2)**2).sum() / (x ** 2).sum()

如需了解更多每个方法的参数和详细说明，请查阅 Faiss 官方文档和示例链接。