引入全局算法的小批量K-Means

王颖 吴观茂

摘 要：提出一种引入全局算法的小批量K-means.算法应用全局搜索算法，解决在大数据情况下运算耗时问题和传统K-means对初始中心点敏感的问题.实验结果表明，该方法在获得最佳结果的前提下可以节省大量的计算时间.

关键词：数据挖掘;全局搜索;K-means算法;小批量

[中图分类号]TP301.6 [文献标志码]A

Mini Batch K-Means with Global Algorithm

WANG Ying，WU Guanmao

（Department of Computer Science and Engineering，Anhui University of Scienceand Technology，Huainan  232001，China）

Abstract：A small batch K-means with global algorithm is proposed Global search algorithm is applied to solve the problem of time-consuming operation in the case of big data and the sensitivity of traditional K-means to the initial center point.The experimental results show that this method can save a lot of calculation time on the premise of obtaining the best results.

Key words：data mining;global search;K-means algorithm;mini batch

数据挖掘是透过数据表面发现掩藏的规律性.聚类算法是通过目标函数优化的数据集X={ x1，x2…xn }，C={c1，c2…cn}，目标函数就是最小化每个簇的平方误差之和（SSE），SSE=（C）=∑ki=1∑x∈cidis（x，mean（ci））2.N个对象划分为k个非空集合的方式可以由第二种斯特林数给出：φ（N，K）=1K！∑（-1）K-iKiiN，可以近似为KNK！.完全枚举出所有可能的聚类以确定全局最小SSE（C）在计算上显然是不可行的，所以诞生了很多方法求上述问题的近似解.K-means算法因为简单易行性被广泛应用，但因利用欧氏距离平方、异常点和噪声容易影响聚类结果，很容易陷入局部最小[1]，不同的初始中心点会产生不同的聚类结果，具有很大的不稳定性，为此研究人员提出了一系列初始化中心点的方法.Likas，Vlassis，Verbeek[2]提出一种通过全局搜索所有数据来动态添加聚类中心的方法，每个阶段添加一个新的聚类中心点，不依赖初始参数.Arthur， Vassilvitskii[3]提出一种基于简单概率播种技术的初始化过程，先选择一个数据点作为初始中心点，然后计算每个数据到该中心点的距离，从而计算每个其他数据点被选为下一个中心点的概率.Bahman[4]等人给出更简明的方案，每次不用遍历全部样本而只需遍历O（k）个样本，5次重复取样即可.MarcoCapó[5]等人提出了一种有效逼近K-means的聚类方法，通过分区，在数量较少的子集上递归的应用K-means的加权版本.Shyr-Shen[6]等人提出两种算法tri-level K-means和bi-layer K-means算法，类似多次分区运用K-means算法，解决K-means对初始点敏感问题.笔者提出一种更加准确和快速优化K-means的算法，在Mini Batch K-means的早期阶段引入全局算法，提高聚类效率，保证聚类的准确性.

1 改进Mini Batch K-means算法

Mini Batch K-means算法[14]使用小批量样本做传统的K-means，每次训练算法提取不同的数据子集，避免样本量太大时的计算难题，目标函数也能得到优化.算法步骤：第一步，从数据集中随机提取一些数据以形成小批量并将它们分配到最近的质心;第二步，重新计算每批小数据的质心，直到质心稳定或达到指定的迭代次数，停止计算.

改进Mini Batch K-means中最后將多组结果取平均值作为最终结果的方式，将每次的结果再次聚类.现在假设随机抽样J次，每次得到K个中心点，最后得到J*K个中心点，将这些J*K个中心点重新聚类的结果作为最终结果.本文让J=4，K=3，即随机取样4次，每次计算出3个中心点，最后将这12个中心点重新聚类成3个最终中心点.简单图示见图1.从图1能很直观的看出改进后的Mini Batch K-means与之前的区别，即使前期离群点会造成影响，最后再次聚类会将该影响降到最低.

参考文献

[1]蔡春华，赵杰，宋丽. 基于随机投影的隐私保护分布式聚类算法研究[J].牡丹江师范学院学报：自然科学版，2014（3）：1-3.

[2]A.Likas，N.A.Vlassis，J.J.Verbeek.The global K-means clustering algorithm[J].Pattern Recognit，2003，36（2）：451-461.

[3]D.Arthur，S.Vassilvitskii，K-means++：the advantages of careful seeding[C].Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms，New Orleans，Louisiana，USA，January 7-9，2007.

[4]Bahman Bahmani，Benjamin Mosesey，Andrea Vattani，Ravi Kumar，Sergei Vassilvitskii.Scalable K-means++[J].Proceedings of the SLDB Endowment，2012，2（5）：622-633.

[5]AritzPéreza，Jose A.Lozanoab.An efficient approximation to the K-means clustering for massive data[J].Knowledge-Based Systems，2017，2（1）：56-69.

[6]Shyr-Shen Yua，Shao-Wei Chua，Chuin-Mu Wangb，Yung-Kuan Chanc，Ting-Cheng Changd.Two improved K-means algorithms[J].Applied Soft Computing，2018，68（13）：744-755.

[7]A.Likas，N.A.Vlassis，J.J.Verbeek.The global K-means clustering algorithm[J].Pattern Recognit，2003，36（2） ：451-461.

編辑：琳莉

收稿日期：2019-12-10

基金项目：安徽省自然科学基金面上项目（1908085MF189）;安徽高校拔尖人才培育项目（gxbjZD15）

作者简介：王颖（1995-），女，安徽池州人.硕士，主要从事数据挖掘研究;吴观茂（1971-），男，安徽淮南人.教授，主要从事数据库和数据挖掘研究.