Rust 中的 FasterPAM 算法实现的 k-Medoids 聚类

此 Rust 包实现了通过直接优化 (Medoid) Silhouette 的聚类方法，使用 PAM 和聚类算法的变体。它可以与任意的不相似度一起使用，因为它需要一个不相似度矩阵作为输入。

此软件包已在 JOSS 中介绍

Erich Schubert 和 Lars Lenssen
Rust 和 Python 中的快速 k-Medoids 聚类
开源软件杂志 7(75)，4183
https://doi.org/10.21105/joss.04183 (开放获取)

有关实现的算法 FasterPAM 的更多详细信息，请参阅

Erich Schubert，Peter J. Rousseeuw
快速和贪婪的 k-Medoids 聚类
PAM、CLARA 和 CLARANS 算法的 O(k) 运行时间改进
信息系统 (101)，2021，101804
https://doi.org/10.1016/j.is.2021.101804 (开放获取)

一个更早的（较慢的，现已过时）版本已发表为

Erich Schubert，Peter J. Rousseeuw
快速 k-Medoids 聚类：改进 PAM、CLARA 和 CLARANS 算法
在第 12 届相似性搜索与应用国际会议上发表
https://doi.org/10.1007/978-3-030-32047-8_16
预印本：https://arxiv.org/abs/1810.05691

这是一个将原始 Java 代码从 ELKI 移植到 Rust 的版本。

有关具有自动聚类数量选择的 medoid Silhouette 聚类（FasterMSC、DynMSC）的更多详细信息，请参阅

Lars Lenssen，Erich Schubert
具有自动聚类数量选择的 medoid Silhouette 聚类
信息系统 (120)，2024，102290
https://doi.org/10.1016/j.is.2023.102290
预印本：https://arxiv.org/abs/2309.03751

基本的 FasterMSC 方法首先发表为

Lars Lenssen，Erich Schubert
通过直接优化 Medoid Silhouette 进行聚类
在第 15 届相似性搜索与应用国际会议上发表
https://doi.org/10.1007/978-3-031-17849-8_15

如果您在科学工作中使用了此代码，请引用上述论文。谢谢。

示例

let dissim = ndarray::arr2(&[[0,1,2,3],[1,0,4,5],[2,4,0,6],[3,5,6,0]]);
let mut meds = kmedoids::random_initialization(4, 2, &mut rand::thread_rng());
let (loss, assingment, n_iter, n_swap): (f64, _, _, _) = kmedoids::fasterpam(&dissim, &mut meds, 100);
println!("Loss is: {}", loss);

注意

• 您需要指定loss的“输出”数据类型——选择一个具有足够精度的有符号类型。例如，对于无符号距离，使用u32，可能最好使用i64来计算损失。
• 输入距离类型需要可以通过Into转换为输出数据类型。

实现算法

• FasterPAM（Schubert 和 Rousseeuw，2020，2021）
• FasterPAM带有集成的附加洗牌步骤
• 并行化FasterPAM带有集成的附加洗牌步骤
• FastPAM1（Schubert 和 Rousseeuw，2019，2021）
• PAM（Kaufman 和 Rousseeuw，1987）带有BUILD和SWAP
• 交替优化（k-means风格算法）
• 轮廓指数用于评估（Rousseeuw，1987）
• FasterMSC（Lenssen 和 Schubert，2022）
• FastMSC（Lenssen 和 Schubert，2022）
• DynMSC（Lenssen 和 Schubert，2023）
• PAMSIL（Van der Laan 和 Pollard，2003）
• PAMMEDSIL（Van der Laan 和 Pollard，2003）

请注意，k-means风格的算法对于k-medoids往往找到较差的解。

如果您打算在相同的数据上多次重启k-medoids（以找到更好的解），FasterPAM的附加洗牌步骤是有益的。当您拥有超过5000个实例时，并行实现通常更快。

Rust依赖项

• num-traits用于支持不同的数值类型
• ndarray用于数组（可选）
• rand用于随机初始化（可选）
• rayon用于并行化（可选）

为rust-kmedoids做出贡献

欢迎第三方贡献。请使用pull requests提交补丁。

报告问题

请在存储库的问题跟踪器中报告错误，作为issue。

支持请求

如果您需要帮助，请在该存储库的问题跟踪器中提交issue。

许可证：GPL-3或更高版本

本程序是自由软件：您可以在自由软件基金会发布的GNU通用公共许可证条款下重新分发和/或修改它，许可证版本为3，或者（根据您的选择）许可证的任何更高版本。

本程序以希望它将是有用的方式分发，但没有任何保证；甚至没有对适销性或针对特定目的的适用性的暗示保证。有关详细信息，请参阅GNU通用公共许可证。

您应该已经收到一份GNU通用公共许可证副本。如果没有，请参阅https://www.gnu.org/licenses/。