图松弛优化聚类的快速近似提升方法

来源：计算机科学与探索杂志2018年第4期北京时间：

作者：谢磊，王士同

单位：江南大学 数字媒体学院，江苏 无锡 214122

摘要：基于图松弛优化为非近似迭代方法提供了有效的分析解决方案，且实现简单。然而，由于矩阵的逆在计算时需要多项式时间，则在运行速度方面不是很理想，当面对较大规模数据时此方法将变得不可行。提出了对基于图松弛优化聚类进行快速近似提升的两种方法：一个是基于k均值聚类，另一个是基于随机投影树。广泛实验表明，这些算法在运算速度方面表现较优，聚类精度变化非常小。具体来讲，该算法在运算大规模数据时精度优于k均值算法，并且在保证精度的情况下运行速度远快于基于图松弛优化聚类算法。值得注意的是，该算法可以使得单个机器在数分钟内对具有数百万样本的数据集进行聚类。

关键词：无监督学习,基于图松弛优化聚类,数据量化,高维数据,快速近似