Ckmeans

use ckmeans::ckmeans;

let input = vec![
    1.0, 12.0, 13.0, 14.0, 15.0, 16.0, 2.0,
    2.0, 3.0, 5.0, 7.0, 1.0, 2.0, 5.0, 7.0,
    1.0, 5.0, 82.0, 1.0, 1.3, 1.1, 78.0,
];
let expected = vec![
    vec![
        1.0, 1.0, 1.0, 1.0, 1.1, 1.3, 2.0, 2.0,
        2.0, 3.0, 5.0, 5.0, 5.0, 7.0, 7.0,
    ],
    vec![12.0, 13.0, 14.0, 15.0, 16.0],
    vec![78.0, 82.0],
];
let result = ckmeans(&input, 3).unwrap();
assert_eq!(result, expected);

Ckmeans聚类是对一维（单变量）启发式聚类方法如Jenks的改进。该算法由Haizhou Wang和Mingzhou Song（2011年）开发，作为将数值数据聚类到具有最小组内平方和偏差的组的动态规划方法。

最小化组内差异——Wang和Song称之为withinss或组内平方和——意味着组在内部是最优同质的，数据被分割成代表性的组。这在可视化中非常有用，其中人们可能希望用离散的颜色或样式组来表示连续变量。此函数可以提供强调数据之间差异的组。

作为一个动态方法，该算法基于两个矩阵，这些矩阵存储平方偏差和回溯索引的增量计算值。

与原始实现不同，此实现不包含任何自动确定最佳聚类数量的代码：此信息需要明确提供。然而，它确实提供了roundbreaks方法来帮助标记。

FFI

提供了与C兼容的FFI实现，以及主要平台的库。请参阅头文件和examples文件夹中的基本C示例。已验证FFI函数不会泄漏内存（请参阅示例中的注释）。

WASM

WASM模块也可用，提供对ckmeans和roundbreaks的访问。使用wasm-bindgen和适当的目标生成模块，或使用NPM软件包。

实现

这是一个David Schnurr的软件包https://github.com/schnerd/ckmeans的移植（包括文档），并纳入了Bill Mill的Python + Numpy实现的一些改进，请参阅https://github.com/llimllib/ckmeans。

性能

在M2 Pro上，生成7个类别

1. 110k在0到250之间均匀分布的i32值：~12毫秒
2. 110k具有均值为3.0和标准差为1.0的正态分布f64值：38毫秒

复杂性

$O(kn)$。其他方法，如Hilferink的CalcNaturalBreaks或k-means具有可比的复杂性，但不保证最优性。在实践中，它们需要许多轮次才能接近最优结果，所以实际上它们较慢。

注意

王和宋（2011）在其介绍中声明该算法以$O(k^2n)$运行。然而，他们已经更新了他们的动态规划算法（请参阅2016年8月的笔记这里），将复杂性降低到线性时间。上述现有实现已经使用这种方法，并在此重现。

可能的改进

性能

"矩阵"是嵌套向量，因此没有最佳内存布局。此外，我们没有尝试利用如果使用例如ndarray可能可用的任何快速线性代数库。

测试

也许一些基于属性的测试。

参考文献

1. 王，H.，&宋，M.（2011）。Ckmeans.1d.dp：通过动态规划在一维中实现最优k-means聚类。R杂志，3(2)，29。
2. https://observablehq.com/@visionscarto/natural-breaks