李长明, 张红臣, 王 超, 李晓光, 陆 洋, 钱超越

(1. 长春光华学院 工程技术研发中心, 长春 130033; 2. 长春光华学院 电气信息学院, 长春 130033; 3. 长春理工大学 计算机科学技术学院, 长春 130022)

聚类分析是机器学习领域重要的无监督分类方法.k-means聚类算法具有思想简单、收敛性好、易实现等优点, 在矢量量化、图像压缩和空间数据挖掘等领域应用广泛.k-means算法通过不断运行数据分配与中心更新两个步骤优化目标函数值. 在分配步骤中,k-means算法将每个数据点分配给距离其最近的中心, 这需要计算所有数据与所有中心之间的距离, 计算复杂度较高. 针对该问题, 目前已提出了许多加速算法, 其中加速方式分为近似加速和精确加速两种. 在k-means近似加速领域, Wang等[1]使用多个随机投影树建立聚类封闭, 提高了k-means算法在分配步骤中的效率和准确性; Sculley[2]引入了一种小批量采样方法, 该方法可得到更好的收敛效果, 且在处理高维数据集时不会增加计算成本; Hu等[3]提出了一种从粗到细的搜索方法进行多级过滤, 测试数据中比标准k-means算法快约600倍； Fahim等[4]提出了一种距离排除准则, 在连续两次迭代中, 点到中心的距离小于上一次迭代的距离, 则可排除剩余的距离计算, 该准则适用于大型数据集提速; Tsai等[5]利用连续指定次数迭代中不变的划分数据进行加速; Ortegal等[6]通过计算中心的移动概率确定阀值, 排除了距离计算； Ortegal等[7]改进了该算法, 使用等距阈值改善其在大型数据集上的计算效率. 在k-means精确加速……