- 松弛化,无需四舍五入:聚类公式的整数性
该研究探讨了点云聚类问题的凸松弛的精确恢复条件,以 k-means 和 k-median 聚类为重点,并提供了理论分析和实验研究。
- 局部搜索算法的高效多起点策略
本文介绍一种基于多臂赌博和 Lipschitz 优化的多次启动策略,持续估计每个算法实例的潜在性能,并动态地向有可能收敛于最优解的实例分配资源,实验证明该方法在实践中表现良好,并且需要的目标函数评估次数只是理论上建议的平方增加的对数增加。
- 集群关闭的快速近似 $k$ 均值算法
本文提出了一种新的近似 k-means 算法,采用多个随机空间分区树将数据预先组装成相邻点的组,并使用邻域信息构造每个簇的闭合形式,从而在分配步骤中只需考虑少量簇的候选项,证明该方法在聚类质量和效率方面优于现有的近似 k-means 算法。
- NIPS基于矩的 $k$-means 及其衍生算法均匀偏差界
通过能够均匀控制偏差的机制,解决了拟合具有有界矩的分布的 k-means 成本与样本成本之间的差异,并考虑了一种软聚类变体的 k-means 成本,即受到所有协方差矩阵具有有界谱约束的高斯混合对数似然的约束,并为具有一定聚类结构的 k-me - 在一般拓扑上进行分布式 k-Means 和 k-Median 聚类
本文提出一种新的分布式 k-median 和 k-means 聚类算法,通过 coresets 的方法,构建全局 coreset,降低了通信复杂度,实验结果表明该算法优于其他 coreset-based 分布式聚类算法。
- 聚类中的硬聚类和软聚类方法的信息论分析
本文通过信息论分析研究了几种不同的分配方法,包括 “硬分配” 和 “软分配”,发现 K-means 和 EM 算法之间的系统差异。同时提出了一种后验分配方法,与 EM 的 “软分配” 相似,但具有截然不同的算法。
- K-Means 聚类算法高效初始化方法的比较研究
本研究探讨了 K-means 算法及其初始化方法在聚类方面的应用,比较了 8 种常用线性时间复杂度的初始化方法,并使用各种性能指标对各种数据集进行了测试和分析, 结论表明,当前通用的初始化方法表现不佳,并且有更好的替代方案。
- NIPS使用 K-Means 和 K-Flats 学习浸入式流形
本文研究了从随机样本中估计流形的问题,并分析了由 k 均值和 k - 平面诱导的分段常数和分段线性估计器的性能。还扩展了先前对 k 均值的结果,提供了 k - 均值重建流形的新结果,并为高阶逼近(k - 平面)证明了重建界限。
- 可扩展的 K-Means++
本研究展示了一种通过在并行计算中显著减少所需传递次数的方法,从而获得好的初始化的 K-means|| 初始化算法,并通过实验评估证明该算法在顺序和并行设置下均优于 K-means ++。