arXiv:2501.16113cs.LG2025-01被引 1
固定簇大小的k均值算法，实现均衡聚类并提升大规模数据处理能力。
Fixed-sized clusters $k$-Means
- 基于匈牙利算法解决簇内分配问题，确保各簇大小固定。
- 处理超过5000点的数据集，时间复杂度为O(n³)。
- 适合需要均衡聚类的场景，如公平性要求高的应用。
我们提出一种基于k均值的聚类算法，通过优化均方误差来实现给定簇大小的聚类。直接应用包括平衡聚类，即每个簇大小相等。在k均值的分配阶段，该算法使用匈牙利算法求解分配问题，使分配阶段的时间复杂度为O(n³)，从而支持对超过5000个点的数据集进行聚类。
原文摘要 · Abstract (English)
We present a $k$-means-based clustering algorithm, which optimizes the mean square error, for given cluster sizes. A straightforward application is balanced clustering, where the sizes of each cluster are equal. In the $k$-means assignment phase, the algorithm solves an assignment problem using the Hungarian algorithm. This makes the assignment phase time complexity $O(n^3)$. This enables clustering of datasets of size more than 5000 points.
聚类算法平衡聚类匈牙利算法
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。