计算机应用

作者：刘静姝, 王莉, 刘惊雷

单位：1. 太原理工大学 大数据学院, 山西 晋中 030600;2. 烟台大学 计算机与控制工程学院, 山东 烟台 264005

关键词：谱聚类,Nyström采样,收敛性分析,特征分解,乘法更新迭代

基金：国家自然科学基金资助项目（61872260）；山西省自然科学基金资助项目（201703D421013）。

为了解决样本数较大时，传统谱聚类算法执行特征分解消耗时间过大的问题，提出了一种无需特征分解的快速谱聚类算法，通过乘法更新迭代来降低时间开销。首先，利用Nyström方法进行随机采样，建立了采样矩阵和原始矩阵之间的关系；其次，基于乘法更新原理实现矩阵指示器矩阵的迭代更新；最后，在理论上对所设计算法进行了正确性和收敛性分析。在广泛使用的五个真实数据集和三个人工合成数据集上进行测试。实验结果表明，在真实数据集上，所提算法的标准互信息（NMI）平均值为0.45，与k-means聚类算法相比提高了12.50%；运行时间为61.73 s，与传统谱聚类算法相比减少了61.13%；而且表现性能优于层次聚类算法，验证了该算法的有效性。

来源：2020年第12期

《计算机应用》期刊编辑部

查看计算机应用杂志2020年第12期