coreset

简介

这个包致力于在度量空间中对大量点数据执行聚类近似。
特别地，我们对数据不能完全加载到内存中，需要流式处理的情况感兴趣。

该方法依赖于获取问题中使用的度量的核心集。
一个 k-核心集是称为设施点的更少数量的点的采样摘要。这些点被选择来近似将原始数据集调度到 每个 k 点子集的成本。所以搜索 k-聚类时，点设施将是整个数据集聚类的良好近似。但是，选定的点现在具有附加到选定点上的 权重，因此我们使用加权点聚类方法来生成最终的聚类。

该包以库和子包 fromhnsw 中的特定二进制文件的形式提供。

实现算法的引用

1. 我们考虑了论文中描述的核心集构建

   • 离线和流式核心集构建的新框架。
     Braverman, Feldman, Lang, Statsman 2022 arxiv-v3

2. 核心集构建依赖于度量空间中的 [$\alpha$,$\beta$] 近似。对于这一步骤，我们使用了以下论文

   • 在良好聚类的数据上的流式 k-means。
     Braverman, Meyerson, Ostrovski, Roytman ACM-SIAM 2011 braverman-1 或 braverman-2

3. 在获得核心集之后，我们需要一个算法来提供加权数据点的 k-medoid 并检查近似核心集的质量。我们实现了以下简单算法（引用自 Friedman Hastie Tibshirani 2001 年的《统计学习的元素》第 14.3.10 节）并进行了以下修改

   • 使用类似 PAM-BUILD 的贪婪初始化
   • 考虑点的权重
   • 对中心点过于接近的簇对进行随机扰动。

结果

详细的成果在这里给出 。我们在核心集构建后运行简单的加权 kmean，并与在整个数据上运行 par_fastermap 得到的结果进行比较。

结论

即使是我们简化的加权Kmedoid实现，平均结果也低于通过par_fastermap获得的参考成本5%以下，并且根据Kmedoid的迭代次数，在2或3个标准差内保持在8%以内。

Kmedoid的迭代次数对速度有一定影响，25次迭代（要求10个簇）是一个很好的折衷方案。

速度快一个或两个数量级。.

使用方法

数据必须与实现MakeIter特质的结构相关联。

pub trait MakeIter {
    /// The identificator of a data
    type Item;
    /// how to get an iterator
    fn makeiter(&self) -> impl Iterator<Item = Self::Item>;
}

算法需要多次遍历数据，因此算法接受一个结构作为参数，在需要时提供数据迭代器。通常，该结构可以提供文件I/O以迭代数据，或者如果没有内存限制，只需包含一个数据Vec的引用并提供数据引用的迭代器。
mnist数据有一个示例（参看module utils::mnistiter）。

实现内部进行缓冲和并行化。最简洁的接口在clustercore模块中提供，但可以通过相应的模块单独访问coreset构建和bmor算法。
距离由crate anndists 提供。

Fromhnsw

工作空间子crate fromhnsw 提供了一个实现MakeIter的trait，用于在hnsw_rs crate的Hnsw结构中存储的数据上运行coreset算法。二进制hcore提供直接coreset或coreset+kmedoid计算，输出为csv文件格式。请参阅Readme。

构建

要编译整个crate（包括子crate fromhnsw），启用在hnsw数据上执行coreset计算，运行
cargo build --release --all --bin hcore

获取完整文档
cargo doc --no-deps --all

Simd

crate anndists通过2个功能simdeez_f在Intel上提供simd，或者stdsimd（可移植但需要rust nightly）。您可以在该crate的Cargo.toml中或使用cargo命令中的--features选择您想要的功能。

许可证

根据您的要求，许可以下任一项

• Apache License，版本2.0，LICENSE-APACHE 或 http://www.apache.org/licenses/LICENSE-2.0
• MIT许可证LICENSE-MIT 或 http://opensource.org/licenses/MIT

。