File Clustering.h

namespace faiss

实现具有多种变体的 k-means 聚类。

此源代码根据 LICENSE 文件中的 MIT 许可证获得许可，该文件位于此源代码树的根目录中。

IDSelector 旨在定义要处理的向量子集（用于删除或作为搜索的子集）

PQ4 SIMD 打包和累积函数

基本内核使用 bbs = nb * 2 * 16 向量累积 nq 查询向量，并为此生成一个输出矩阵。对于 nq * nb <= 4 来说，这很有趣，否则寄存器溢出会变得太大。

这些函数的实现分布在 3 个 cpp 文件中，以减少并行编译时间。模板被显式实例化。

此文件包含用于计算距离的内核的回调。

在整个库中，向量以 float * 指针的形式提供。当在一批中一起处理（添加/搜索）多个向量时，大多数算法可以得到优化。在这种情况下，它们作为矩阵传入。当大小为 d 的 n 个向量作为 float * x 提供时，向量 i 的分量 j 为

x[ i * d + j ]

其中 0 <= i < n 且 0 <= j < d。换句话说，矩阵始终是紧凑的。指定矩阵的大小时，我们将其称为 n*d 矩阵，这意味着行优先存储。

I/O 函数可以读/写到文件名、文件句柄或抽象介质的对象。

读取函数返回的对象应使用 delete 释放。这些对象中的所有引用都归该对象所有。

反向列表的定义 + 一些实现该接口的常见类。

由于 IVF（反向文件）索引对于大规模用例非常有用，因此我们将与它们相关的一些函数组合到这个小库中。大多数函数都适用于 IndexIVF 和嵌入在 IndexPreTransform 中的 IndexIVF。

此文件中实现了 L2 和内积之外的额外指标

实现了一些神经网络层，主要为了支持 QINCo

定义了一些对象，这些对象将转换应用于一组向量。这些通常是预处理步骤。

函数

float kmeans_clustering(size_t d, size_t n, size_t k, const float *x, float *centroids)

简化的接口

参数:

d – 数据的维度
n – 训练向量的数量
k – 输出质心的数量
x – 训练集（大小 n * d）
centroids – 输出质心（大小 k * d）

返回值:

最终量化误差

struct ClusteringParameters

#include <Clustering.h>

聚类参数类。可以传递给 Clustering 对象的构造函数。

由 faiss::Clustering, faiss::ProgressiveDimClusteringParameters 继承

公共成员

int niter = 25: 聚类迭代次数

int nredo = 1: 多次重复聚类，并保留目标值最好的聚类结果

bool verbose = false

bool spherical = false: 是否在每次迭代后对质心进行归一化（对内积聚类有用）

bool int_centroids = false: 每次迭代后是否将质心坐标四舍五入为整数？

bool update_index = false: 每次迭代后是否重新训练索引？

bool frozen_centroids = false: 使用提供的质心子集作为输入，并且在迭代期间不更改它们

int min_points_per_centroid = 39: 如果每个质心提供的训练向量少于此数量，则写入警告。请注意，每个质心少于 1 个点会引发异常。

int max_points_per_centroid = 256: 限制数据集大小，否则训练集将被二次采样

int seed = 1234: 随机数生成器的种子。负值导致使用 std::high_resolution_clock 播种内部 rng。

size_t decode_block_size = 32768: 当训练集被编码时，编解码器解码器的批量大小

bool check_input_data_for_NaNs = true: 是否检查输入数据中是否存在 NaN

bool use_faster_subsampling = false: 是否使用基于 splitmix64 的随机数生成器进行二次采样，该生成器速度更快，但可能会选择重复的点。

struct ClusteringIterationStats

公共成员

float obj: 目标值（索引报告的距离之和）

double time: 迭代的秒数

double time_search: 仅用于搜索的秒数

double imbalance_factor: 迭代的不平衡因子

int nsplit: 簇分裂的数量

struct Clustering : public faiss::ClusteringParameters 

#include <Clustering.h>

基于分配的 K-means 聚类 - 质心更新迭代

聚类基于 Index 对象，该对象将训练点分配给质心。因此，在每次迭代中，质心都会添加到索引中。

在输出时，质心表设置为质心的最新版本，并且它们也添加到索引中。如果质心表在输入时不是空的，则也用于初始化。

由 faiss::Clustering1D 子类化

公共函数

Clustering(int d, int k)

Clustering(int d, int k, const ClusteringParameters &cp)

virtual void train(idx_t n, const float *x, faiss::Index &index, const float *x_weights = nullptr)

运行 k-means 训练

参数:

x – 训练向量，大小为 n * d
index – 用于分配的索引
x_weights – 与每个向量关联的权重：NULL 或大小为 n

void train_encoded(idx_t nx, const uint8_t *x_in, const Index *codec, Index &index, const float *weights = nullptr)

使用编码向量运行

除了 train() 的参数之外，还接受一个 codec 作为参数来解码输入向量。

参数:: codec – 用于解码向量的 codec（nullptr = 向量实际上是浮点数）

void post_process_centroids(): 在每次质心更新后对质心进行后处理。包括可选的 L2 归一化和最近整数舍入

inline virtual ~Clustering()

公共成员

size_t d: 向量的维度

size_t k: 质心的数量

std::vector<float> centroids: 质心（k * d）。如果在训练的输入中设置了质心，它们将用作初始化

std::vector<ClusteringIterationStats> iteration_stats: 聚类的每次迭代的统计信息

int niter = 25: 聚类迭代次数

int nredo = 1: 多次重复聚类，并保留目标值最好的聚类结果

bool verbose = false

bool spherical = false: 是否在每次迭代后对质心进行归一化（对内积聚类有用）

bool int_centroids = false: 每次迭代后是否将质心坐标四舍五入为整数？

bool update_index = false: 每次迭代后是否重新训练索引？

bool frozen_centroids = false: 使用提供的质心子集作为输入，并且在迭代期间不更改它们

int min_points_per_centroid = 39: 如果每个质心提供的训练向量少于此数量，则写入警告。请注意，每个质心少于 1 个点会引发异常。

int max_points_per_centroid = 256: 限制数据集大小，否则训练集将被二次采样

int seed = 1234: 随机数生成器的种子。负值导致使用 std::high_resolution_clock 播种内部 rng。

size_t decode_block_size = 32768: 当训练集被编码时，编解码器解码器的批量大小

bool check_input_data_for_NaNs = true: 是否检查输入数据中是否存在 NaN

bool use_faster_subsampling = false: 是否使用基于 splitmix64 的随机数生成器进行二次采样，该生成器速度更快，但可能会选择重复的点。

struct Clustering1D : public faiss::Clustering 

#include <Clustering.h>

精确的 1D 聚类算法

因为它不使用索引，所以它不重载 train() 函数

公共函数

explicit Clustering1D(int k)

Clustering1D(int k, const ClusteringParameters &cp)

void train_exact(idx_t n, const float *x)

inline virtual ~Clustering1D()

virtual void train(idx_t n, const float *x, faiss::Index &index, const float *x_weights = nullptr)

运行 k-means 训练

参数:

x – 训练向量，大小为 n * d
index – 用于分配的索引
x_weights – 与每个向量关联的权重：NULL 或大小为 n

void train_encoded(idx_t nx, const uint8_t *x_in, const Index *codec, Index &index, const float *weights = nullptr)

使用编码向量运行

除了 train() 的参数之外，还接受一个 codec 作为参数来解码输入向量。

参数:: codec – 用于解码向量的 codec（nullptr = 向量实际上是浮点数）

void post_process_centroids(): 在每次质心更新后对质心进行后处理。包括可选的 L2 归一化和最近整数舍入

公共成员

size_t d: 向量的维度

size_t k: 质心的数量

std::vector<float> centroids: 质心（k * d）。如果在训练的输入中设置了质心，它们将用作初始化

std::vector<ClusteringIterationStats> iteration_stats: 聚类的每次迭代的统计信息

int niter = 25 : 聚类迭代次数

int nredo = 1 : 多次重复聚类，并保留目标值最好的聚类结果

bool verbose = false 

bool spherical = false : 是否在每次迭代后对质心进行归一化（对内积聚类有用）

bool int_centroids = false : 每次迭代后是否将质心坐标四舍五入为整数？

bool update_index = false : 每次迭代后是否重新训练索引？

bool frozen_centroids = false : 使用提供的质心子集作为输入，并且在迭代期间不更改它们

int min_points_per_centroid = 39 : 如果每个质心提供的训练向量少于此数量，则写入警告。请注意，每个质心少于 1 个点会引发异常。

int max_points_per_centroid = 256 : 限制数据集大小，否则训练集将被二次采样

int seed = 1234 : 随机数生成器的种子。负值导致使用 std::high_resolution_clock 播种内部 rng。

size_t decode_block_size = 32768 : 当训练集被编码时，编解码器解码器的批量大小

bool check_input_data_for_NaNs = true : 是否检查输入数据中是否存在 NaN

bool use_faster_subsampling = false : 是否使用基于 splitmix64 的随机数生成器进行二次采样，该生成器速度更快，但可能会选择重复的点。

struct ProgressiveDimClusteringParameters : public faiss::ClusteringParameters 

被 faiss::ProgressiveDimClustering 继承

公共函数

ProgressiveDimClusteringParameters() 

公共成员

int progressive_dim_steps : 增量步数

bool apply_pca : 对输入应用 PCA

int niter = 25 : 聚类迭代次数

int nredo = 1 : 多次重复聚类，并保留目标值最好的聚类结果

bool verbose = false

bool spherical = false: 是否在每次迭代后对质心进行归一化（对内积聚类有用）

球形聚类：bool spherical = false: 每次迭代后是否将质心坐标四舍五入为整数？

bool int_centroids = false: 每次迭代后是否重新训练索引？

整数质心：bool int_centroids = false: 使用提供的质心子集作为输入，并且在迭代期间不更改它们

bool update_index = false: 如果每个质心提供的训练向量少于此数量，则写入警告。请注意，每个质心少于 1 个点会引发异常。

更新索引：bool update_index = false: 限制数据集大小，否则训练集将被二次采样

bool frozen_centroids = false: 随机数生成器的种子。负值导致使用 std::high_resolution_clock 播种内部 rng。

冻结质心：bool frozen_centroids = false: 当训练集被编码时，编解码器解码器的批量大小

int min_points_per_centroid = 39: 是否检查输入数据中是否存在 NaN

每个质心的最小点数：int min_points_per_centroid = 39: 是否使用基于 splitmix64 的随机数生成器进行二次采样，该生成器速度更快，但可能会选择重复的点。

int max_points_per_centroid = 256

#include <Clustering.h>

每个质心的最大点数：int max_points_per_centroid = 256

int seed = 1234

公共函数

随机数种子：int seed = 1234: size_t decode_block_size = 32768

解码块大小：size_t decode_block_size = 32768

bool check_input_data_for_NaNs = true

#include <Clustering.h>

检查输入数据中的NaN值：bool check_input_data_for_NaNs = true

bool use_faster_subsampling = false

使用更快的子采样：bool use_faster_subsampling = false

struct ProgressiveDimIndexFactory

ProgressiveDimIndexFactory 结构体

调用时生成适合聚类的索引

公共函数

被 faiss::gpu::GpuProgressiveDimIndexFactory 继承

virtual Index *operator()(int dim)

训练函数：使用给定的数据和索引工厂训练渐进维度聚类。

析构函数：渐进维度聚类的析构函数。

公共成员

维度：输入向量的维度。: 向量的维度

聚类数量：要创建的聚类中心的数量。: 质心的数量

聚类中心：存储聚类中心坐标的向量。: 聚类中心 (k * d)

迭代统计：存储每次迭代的统计信息的向量。: 聚类的每次迭代的统计信息

渐进维度步长：在渐进维度聚类中，每次增加的维度数量。: 增量步数

应用PCA：是否在聚类前应用主成分分析 (PCA)。: 对输入应用 PCA

迭代次数：聚类算法的最大迭代次数，默认为 25。: 聚类迭代次数

重做次数：聚类过程重复的次数，选择最佳结果，默认为 1。: 多次重复聚类，并保留目标值最好的聚类结果

详细模式：是否启用详细输出，默认为 false。

球面聚类：是否进行球面聚类（将聚类中心归一化），默认为 false。: 是否在每次迭代后对质心进行归一化（对内积聚类有用）

整数聚类中心：是否将聚类中心转换为整数，默认为 false。: 每次迭代后是否将质心坐标四舍五入为整数？

更新索引：是否在聚类后更新索引，默认为 false。: 每次迭代后是否重新训练索引？

冻结聚类中心：是否在训练后冻结聚类中心，默认为 false。: 使用提供的质心子集作为输入，并且在迭代期间不更改它们

每个聚类中心的最小点数：每个聚类中心至少需要的点数，默认为 39。: 如果每个质心提供的训练向量少于此数量，则写入警告。请注意，每个质心少于 1 个点会引发异常。

每个聚类中心的最大点数：每个聚类中心允许的最大点数，默认为 256。: 限制数据集大小，否则训练集将被二次采样

随机种子：用于初始化的随机种子，默认为 1234。: 随机数生成器的种子。负值导致使用 std::high_resolution_clock 播种内部 rng。

解码块大小：解码时的块大小，默认为 32768。: 当训练集被编码时，编解码器解码器的批量大小

检查输入数据是否存在 NaN：是否检查输入数据是否存在 NaN 值，默认为 true。: 是否检查输入数据中是否存在 NaN

bool use_faster_subsampling = false: 是否使用基于 splitmix64 的随机数生成器进行二次采样，该生成器速度更快，但可能会选择重复的点。