带有噪声的分层密度空间聚类应用 ("HDBSCAN")

纯 Rust 实现的 HDBSCAN 聚类算法。对浮点数类型进行泛型处理。

HDBSCAN 是一种强大的聚类算法，可以有效地在现实世界数据中找到簇。HDBSCAN 的主要优势是：

1. 它不像许多聚类算法那样假设所有数据点都属于一个簇。也就是说，数据集可以包含“噪声”点。这对于模拟现实世界数据非常重要，因为现实世界数据本质上是有噪声的；
2. 它允许簇具有不同的密度，与使用静态密度阈值的普通 DBSCAN 算法不同。获胜的簇是在所有密度下都持续最久的那一个。这对于模拟现实世界数据也非常重要；
3. 它不假设必须有多少个簇，与 KMeans 聚类不同。该算法将只选择在所有密度下都最持久的簇。

此实现得益于 Python scikit-learn 中此算法的实现，没有它，此算法将无法实现。下面的“HDBSCAN 如何工作”文章对于更好地理解此算法非常有价值。

当前状态

HDBSCAN 有几种可能的变体。值得注意的是，使用最近邻算法来计算点与其第 K 个邻居的距离。这是计算向量空间中点密度的一个关键输入。目前，此实现仅支持 K-d Tree 最近邻算法来完成此任务。虽然 K-d Tree 对于大多数用例来说是最好的候选者，但我希望在将来支持其他最近邻算法，以使此实现更具灵活性（如 scikit-learn Python 实现）。

此外，该实现使用Prim算法来寻找点的最小生成树。Prim算法在密集向量上表现最佳，因此大多数情况下都会使用。然而，Kruskal算法也是另一种可能性，在稀疏向量上可能表现更好。

使用方法

使用默认超参数

use std::collections::HashSet;
use hdbscan::Hdbscan;

let data: Vec<Vec<f32>> = vec![
    vec![1.5, 2.2],
    vec![1.0, 1.1],
    vec![1.2, 1.4],
    vec![0.8, 1.0],
    vec![1.1, 1.0],
    vec![3.7, 4.0],
    vec![3.9, 3.9],
    vec![3.6, 4.1],
    vec![3.8, 3.9],
    vec![4.0, 4.1],
    vec![10.0, 10.0],
];
let clusterer = Hdbscan::default(&data);
let labels = clusterer.cluster().unwrap();
//First five points form one cluster
assert_eq!(1, labels[..5].iter().collect::<HashSet<_>>().len());
// Next five points are a second cluster
assert_eq!(1, labels[5..10].iter().collect::<HashSet<_>>().len());
// The final point is noise
assert_eq!(-1, labels[10]);

使用自定义超参数

use std::collections::HashSet;
use hdbscan::{DistanceMetric, Hdbscan, HdbscanHyperParams, NnAlgorithm};

let data: Vec<Vec<f32>> = vec![
    vec![1.3, 1.1],
    vec![1.3, 1.2],
    vec![1.2, 1.2],
    vec![1.0, 1.1],
    vec![0.9, 1.0],
    vec![0.9, 1.0],
    vec![3.7, 4.0],
];
let hyper_params = HdbscanHyperParams::builder()
    .min_cluster_size(3)
    .min_samples(2)
    .dist_metric(DistanceMetric::Manhattan)
    .nn_algorithm(NnAlgorithm::BruteForce)
    .build();
let clusterer = Hdbscan::new(&data, hyper_params);
let labels = clusterer.cluster().unwrap();
// First three points form one cluster
assert_eq!(1, labels[..3].iter().collect::<HashSet<_>>().len());
// Next three points are a second cluster
assert_eq!(1, labels[3..6].iter().collect::<HashSet<_>>().len());
// The final point is noise
assert_eq!(-1, labels[6]);

计算簇中心

use hdbscan::{Center, Hdbscan};

let data: Vec<Vec<f32>> = vec![
        vec![1.5, 2.2],
        vec![1.0, 1.1],
        vec![1.2, 1.4],
        vec![0.8, 1.0],
        vec![1.1, 1.0],
        vec![3.7, 4.0],
        vec![3.9, 3.9],
        vec![3.6, 4.1],
        vec![3.8, 3.9],
        vec![4.0, 4.1],
        vec![10.0, 10.0],
];
let clusterer = Hdbscan::default(&data);
let labels = clusterer.cluster().unwrap();
let centroids = clusterer.calc_centers(Center::Centroid, &labels).unwrap();
assert_eq!(2, centroids.len());
assert!(centroids.contains(&vec![3.8, 4.0]) && centroids.contains(&vec![1.12, 1.34]));

许可协议

双许可，以兼容Rust项目。

根据您的选择，许可协议为Apache License，版本2.0 https://apache.ac.cn/licenses/LICENSE-2.0 或MIT许可 http://opensource.org/licenses/MIT。此文件不得根据除上述条款外的任何条款进行复制、修改或分发。