本项目是根据论文[1] Manuel Fritz, Michael Behringer, Holger Schwarz. LOG-Means: Efficiently Estimating the Number of Clusters in Large Datasets. PVLDB, 13(11): 2118-2131, 2020. DOI: https://doi.org/10.14778/3407790.3407813, 基于C++复现的LOG-Means算法项目。
LOG-Means算法是一种新型、简化的、高效、对大数据集和大搜索空间具有强鲁棒性的簇数目估计方法。它采用了二分搜索策略和递归细化策略，分别在大范围和小范围内进行簇数目估计，从而高效估计数据中的簇的个数。
- Log-Means算法[1]
- 定义键值数据结构K和M, K存储k的已评估值和相应的SSE，M存储k的已评估值与k和左侧邻值之间相应的SSE Ratio
- 当klow和khigh相差大于1（不直接相邻）时，进行迭代
- 分别对klow和khigh进行KMeans聚类，聚类结果{k, SSE}存储在K中
- 定义kmid，对kmid进行KMeans聚类，聚类结果{kmid, SSE}存储在K中
- 分别计算kmid与klow、khigh的SSE Ratio，存储在M中
- 从M中获取最大的SSE Ratio对应的k值，作为下一次迭代的khigh值
- 从K中获取khigh的相邻值，作为下一次迭代的klow值
- 检索klow、khigh对应的SSE作为下一轮迭代的SSEHigh和SSELow
- k-means||初始化[2]
- 随机选择一个中心点
- 计算满足概率条件的多个候选中心点C（可能大于k个）
- 迭代r次，
r=logn(这里设定r=2，Apache Sparch MLLib中的默认值) - 根据probability，每次迭代取样O(k)个样本
- 最后得到大约O(kr)个样本
- 迭代r次，
- 如果C中的点个数小于k，则继续迭代，直到C中的点个数等于k，然后返回
- 如果C中的点个数大于k，则进行下一步
- 给C中所有点赋予权重值，这个权重值表示距离x点最近的点的个数。
- 使用带有权重的K-Means++算法从C中筛选出k个中心点
-
k-means++初始化
- 随机选择一个中心点
- 计算每个点到中心点的距离，选择最远的点作为下一个中心点
- 重复上述过程，直到选出k个中心点
-
random初始化
- 随机选择k个点作为中心点
-
Elbow算法[3]
- 对于给定的数据集，分别计算k=1,2,...,kmax的KMeans聚类结果
- 计算每个k对应的SSE
- 画出k-SSE曲线，选择拐点对应的k值作为簇数目估计值
- C++编译器（支持C++17或更高版本）
- 第三方库：Eigen3
- 构建项目
./configure
- 运行项目
// 默认运行模式，对Avila数据集在[0.5c, 2c]范围内进行簇数目估计
./cluster
// 运行帮助
./cluster --help
// 对所有数据集进行簇数目估计
./cluster -a
// 对指定数据集进行簇数目估计，可以不指定，默认为Avila数据集
./cluster -d <dataset>
// 指定大范围搜索模式，将搜索空间设置为[2, 10c]，默认为[2, 2c]
./cluster -d <dataset> -s
./cluster -a -s
// 指定elbow模式，将使用Elbow算法进行簇数目估计，如果不指定-e则运行LogMeans
./cluster -e
// 指定质心初始化模式，default(kmeans||)，random，kmeans++，如果不指定-i则使用kmeans||
./cluster -i <initMode>
本项目将使用一系列测试用例对每个模块进行单元测试，以确保它们的正确性和有效性。测试用例应涵盖正常情况、边缘情况和异常情况。此外，我们还将使用一些具有不同特征和规模的真实数据集进行集成测试，以评估算法的性能和准确性。
每个数据集的规模为：
- Avila 包含了 10,430 个数据点，每个点有 10 个维度，总计 12 个类
- DSDD 包含了 58,509 个数据点，每个点有 48 个维度，总计 11 个类
- MNIST 包含了 60,000 个数据点，每个点有 784 个维度，总计 10 个类
- KDD 包含了 4,898,431 个数据点，每个点有 34 个维度，总计 23 个类
- KITSUNE 包含了 20,253,460 个数据点，每个点有 115 个维度，总计 8 个类
- KITSUNE10 包含了 1,868,224 个数据点，每个点有 115 个维度，总计 8 个类
-
$\delta_k=\frac{k-c}{c}*100%$ (k是预估类数, c是真实类数) - Runtime(s)
This project is licensed under the Apache 2.0 License. See the LICENSE file for more information.
[1] Manuel Fritz, Michael Behringer, Holger Schwarz. LOG-Means: Efficiently Estimating the Number of Clusters in Large Datasets. PVLDB, 13(11): 2118-2131, 2020. DOI: https://doi.org/10.14778/3407790.3407813
[2] B. Bahmani, B. Moseley, A. Vattani, R. Kumar, andS. Vassilvitskii. Scalable K-Means++. PVLDB,5(7):622–633, 2012.
[3] R. L. Thorndike. Who belongs in the family? Psychometrika, 18(4):267–276, 12 1953.