加速大数据聚类Ｋ－ｍｅａｎｓ算法的改进韩　岩１，２，李　晓１（１．中国科学院新疆理化技术研究所，新疆乌鲁木齐８３００１１；２．中国科学院大学计算机与控制学院，北京１０００４９）摘　要：为有效处理大规模数据聚类的问题，提出一种先抽样再用最大最小距离进行Ｋ－ｍｅａｎｓ并行化聚类的方法。基于抽样的方法避免了聚类陷入局部解中，基于最大最小距离法使得初始聚类中心趋于最优化。大量实验结果表明，无论是在单机环境还是集群环境下，该方法受初始聚类中心的影响降低，提高了聚类的准确性，减少了聚类的迭代次数，降低了聚类的时间。关键词：Ｋ－均值算法；随机抽样；最大最小距离法；映射归约；并行化中图法分类号：ＴＰ３１１　文献标识号：Ａ 　文章编号：１０００－７０２４ （２０１５）０５－１３１７－０４ｄｏｉ：１０．１６２０８／ｊ．ｉｓｓｎ１０００－７０２４．２０１５．０５．０３９收稿日期：２０１４－０５－０８；修订日期：２０１４－０７－０９基金项目：中国科学院西部之光人才培养计划基金项目（ＲＣＰＴ２０１２０５）作者简介：韩岩（１９８８ ），男，河南商丘人，硕士，研究方向为数据挖掘、物联网、海量数据处理与分析；李晓（１９５７ ），男，新疆乌鲁木齐人，硕士，研究员，博士生导师，研究方向为多语种信息处理、信息系统研究与开发。Ｅ－ｍａｉｌ：８２５３５８４４５＠ｑｑ．ｃｏｍＩｍｐｒｏｖｅｄ　ａｃｃｅｌｅｒａｔｉｎｇ　ｌａｒｇｅ　ｄａｔａ　Ｋ－ｍｅａｎｓ　ｃｌｕｓｔｅｒｉｎｇ　ａｌｇｏｒｉｔｈｍＨＡＮ　Ｙａｎ１，２，ＬＩ　Ｘｉａｏ１（１．Ｘｉｎｊｉａｎｇ　Ｔｅｃｈｎｉｃａｌ　Ｉｎｓｔｉｔｕｔｅ　ｏｆ　Ｐｈｙｓｉｃｓ　ａｎｄ　Ｃｈｅｍｉｓｔｒｙ，Ｃｈｉｎｅｓｅ　Ａｃａｄｅｍｙ　ｏｆ　Ｓｃｉｅｎｃｅｓ，Ｕｒｕｍｑｉ　８３００１１，Ｃｈｉｎａ；２．Ｓｃｈｏｏｌ　ｏｆ　Ｃｏｍｐｕｔｅｒ　ａｎｄ　Ｃｏｎｔｒｏｌ　Ｅｎｇｉｎｅｅｒｉｎｇ，Ｕｎｉｖｅｒｓｉｔｙ　ｏｆ　Ｃｈｉｎｅｓｅ　Ａｃａｄｅｍｙ　ｏｆ　Ｓｃｉｅｎｃｅｓ，Ｂｅｉｊｉｎｇ　１０００４９，Ｃｈｉｎａ）Ａｂｓｔｒａｃｔ：Ｔｏ　ｄｅａｌ　ｗｉｔｈ　ｌａｒｇｅ－ｓｃａｌｅ　ｄａｔａ　ｃｌｕｓｔｅｒｉｎｇ　ｐｒｏｂｌｅｍｓ，ａ　ｓｐｅｅｄｉｎｇ　Ｋ－ｍｅａｎｓ　ｐａｒａｌｌｅｌ　ｃｌｕｓｔｅｒｉｎｇ　ｍｅｔｈｏｄ　ｗａｓ　ｐｒｅｓｅｎｔｅｄ　ｗｈｉｃｈｒａｎｄｏｍｌｙ　ｓａｍｐｌｅｄ　ｆｉｒｓｔ　ａｎｄ　ｔｈｅｎ　ｕｓｅｄ　ｍａｘ－ｍｉｎ　ｄｉｓｔａｎｃｅ　ｍｅａｎｓ　ｔｏ　ｃａｒｒｙ　ｏｕｔ　Ｋ－ｍｅａｎｓ　ｐａｒａｌｌｅｌ　ｃｌｕｓｔｅｒｉｎｇ．Ｓａｍｐｌｉｎｇ　ｂａｓｅｄ　ｍｅｔｈｏｄａｖｏｉｄｓ　ｔｈｅ　ｐｒｏｂｌｅｍ　ｏｆ　ｃｌｕｓｔｅｒｉｎｇ　ｉｎ　ｌｏｃａｌ　ｓｏｌｕｔｉｏｎｓ　ａｎｄ　ｍａｘ－ｍｉｎ　ｄｉｓｔａｎｃｅ　ｂａｓｅｄ　ｍｅｔｈｏｄ　ｍａｋｅｓ　ｔｈｅ　ｉｎｉｔｉａｌ　ｃｌｕｓｔｅｒｉｎｇ　ｃｅｎｔｅｒｓ　ｔｅｎｄ　ｔｏｂｅ　ｏｐｔｉｍｕｍ．Ｒｅｓｕｌｔｓ　ｏｆ　ａ　ｌａｒｇｅ　ｎｕｍｂｅｒ　ｏｆ　ｅｘｐｅｒｉｍｅｎｔｓ　ｓｈｏｗ　ｔｈａｔ　ｔｈｅ　ｐｒｏｐｏｓｅｄ　ｍｅｔｈｏｄ　ｉｓ　ａｆｆｅｃｔｅｄ　ｌｅｓｓ　ｂｙ　ｔｈｅ　ｉｎｉｔｉａｌ　ｃｌｕｓｔｅｒｉｎｇｃｅｎｔｅｒ　ａｎｄ　ｉｍｐｒｏｖｅｓ　ｔｈｅ　ｐｒｅｃｉｓｉｏｎ　ｏｆ　ｃｌｕｓｔｅｒｉｎｇ　ｉｎ　ｂｏｔｈ　ｓｔａｎｄ－ａｌｏｎｅ　ｅｎｖｉｒｏｎｍｅｎｔ　ａｎｄ　ｃｌｕｓｔｅｒ　ｅｎｖｉｒｏｎｍｅｎｔ．Ｉｔ　ａｌｓｏ　ｒｅｄｕｃｅｓ　ｔｈｅ　ｎｕｍｂｅｒ　ｏｆ　ｉｔｅｒａｔｉｏｎｓ　ｏｆ　ｃｌｕｓｔｅｒｉｎｇ　ａｎｄ　ｔｈｅ　ｃｌｕｓｔｅｒｉｎｇ　ｔｉｍｅ．Ｋｅｙ　ｗｏｒｄｓ：Ｋ－ｍｅａｎｓ　ａｌｇｏｒｉｔｈｍ；ｒａｎｄｏｍ　ｓａｍｐｌｉｎｇ；ｍａｘ－ｍｉｎ　ｄｉｓｔａｎｃｅ　ｍｅｔｈｏｄ；ＭａｐＲｅｄｕｃｅ；ｐａｒａｌｌｅｌｉｚａｔｉｏｎ０　引　言聚类分析是数据挖掘领域中的一个重要分支，研究者针对各个领域提出了不同的改进聚类算法：划分聚类、层次聚类、基于密度的聚类、基于网格的聚类、基于模型的聚类等算法［１－３］。尤其Ｋ－ｍｅａｎｓ算法使用最为广泛，但Ｋｍｅａｎｓ算法对初始的ｋ个中心依赖性很大，初始中心选择不当，容易造成局部最优解，增加迭代次数，降低执行效率。由于数据规模越来越大，而传统的聚类算法在处理大规模数据时无论从系统资源还是从实时性效率的角度，都不能提供很好的解决方案［４］。为解决上述问题，本文提出一种先抽样再用最大最小距离方法计算聚类中心的聚类分析方法。１　相关概念（１）Ｋ－ｍｅａｎｓ算法思想：以空间中ｋ个点为中心进行聚类，对最靠近他们的对象归类。通过迭代的方法，逐次更新各聚类中心的值，直至得到聚类中心收敛为止［１］。（２）最大最小距离法：具体详细内容参见文献［１１］。（３）欧氏距离（简称距离）Ｅｕｃｌｉｄｅａｎ［２］Ｄ ＝ Ｘ－Ｃ ＝２Σ ｎｉ＝１（Ｘｉ－Ｃｉ） 槡２ （１）（４）加权聚类准则函数。聚类准则函数［２］：Ｍｊ ＝ １ＮｊΣＸ∈ＳｊＸ，其中Ｎｊ ＝｜Ｓｊ｜ （２）　计算机工程与设计２０１５年Ｊｃ ＝Σｋｊ＝１ΣＸ∈ＳｊＸ－Ｍｊ２ （３）由于是对大数据进行聚类，防止孤立点对Ｊｃ值的影响，采用加权聚类准则函数Ｊｃ ＝ Σｋｊ＝１ΣＸ∈ＳｊＸ－Ｍｊ（ ２／ｎ）１２（４）式中：Ｘ———样本类别，Ｍｊ———样本均值，ｎ———所有样本数目。（５）ＭａｐＲｅｄｕｃｅ编程模型的基本思路：将大数据集分解成千上百个小数据集，每个小数据集分别由集群中的１个节点并行执行Ｍａｐ计算任务并生成中间结果，然后这些中间结果多节点并行执行Ｒｅｄｕｃｅ计算任务，形成最终结果。ＭａｐＲｅｄｕｃｅ执行过程如图１所示。图１　ＭａｐＲｅｄｕｃｅ执行过程２　改进的Ｋ－ｍｅａｎｓ算法２．１　改进算法思想Ｋ－ｍｅａｎｓ算法属于划分聚类算法之一，它有算法简单，速度快等优点；它也有对初始聚类中心依赖较大、对异常偏离数据敏感、只适合处理数值的数据等缺点。下文将针对优化初始聚类中心和并行化提出解决办法。改进算法的思路如下：设数据集Ｘ＝ ｛ｘ１，ｘ２．．．ｘｎ｝，且ｘｉ∈Ｏｄ 其中ｎ为样本个数，ｄ为样本维度，ｋ为聚类个数，ｍ为迭代次数。传统Ｋ－ｍｅａｎｓ算法如下［７］：（１）适当选择ｋ个类的初始中心；（２）在第ｍ次迭代中，对任意一个样本，求其到ｋ个中心的距离，将该样本归到距离最短的中心所在的类；（３）利用均值等方法更新该类的中心值；（４）对于所有的ｋ个聚类中心，如果利用式（２）、式（３）的迭代法更新后，值保持不变，则迭代结束，否则继续迭代。本文算法是首先结合随机抽样方法从样本集Ｘ中抽取一个规模较小的工作集Ｘ′，设｜Ｘ′｜＝｜Ｘ｜／ｓ，其中ｓ为抽样因子，一般取值在５～１００之间（即抽样数据是原始数据１％～２０％），取值视原始数据量而定。然后，用最大最小距离法计算抽样数据的聚类中心Ｃ１，再以Ｃ１作为据的聚类中心Ｃ，由于Ｋ－ｍｅａｎｓ之间的计算相互独立的，所以，可以使用ＭａｐＲｅｄｕｃｅ框架实现计算的并行化，提高计算的效率。然后再计算新的聚类中心Ｃ′与Ｃ距离是否小于设定的阀值Ｙ，如果小于执行结束，返回新的聚类中心与聚类结果。否则用新的聚类中心Ｃ′重新聚类，直到两个聚类中心距离小于设定阀值为止。通过个流程可以分析出整个程序的时间复杂度为：Ｏ（ｎｋ （１／ｓ＋ｔ）／ （Ｍ＊Ｎ））其中ｎ是样本集的个数，ｋ是聚类个数，ｔ是全局数据的迭代次数，Ｍ 是执行作业的Ｍａｐ个数，Ｎ是集群中执行该任务的结点数。２．２　改进算法的执行流程２．２．１　改进算法主要有个两个主要的步骤（１）确定初始化聚类的中心。（２）实现海量数据的Ｋ－ｍｅａｎｓ算法并行化计算。２．２．２　执行流程设数据集为Ｘ＝ ｛ｘ１，ｘ２，…，ｘｎ｝，其中ｘｉ∈Ｏｄ，抽样因子为ｓ，聚类个数为ｋ，阀值参数为Ｙ。（１）从数据集Ｘ中随机抽取ｎ／ｓ个样本数据构成抽样样本Ｘ′＝ ｛ｘ′１，ｘ′２．．．ｘ′ｍ｝；得到｜Ｘ′｜＝｜Ｘ｜／ｓ。（２）用最大最小距离方法计算抽样数据Ｘ′的ｋ个聚类中心：１）先从抽样数据Ｘ′随机选择一个样本ｘ′ｉ，作为抽样数据聚类中心Ｃ１第１个中心点ｃ１；２）用Ｘ中样本集计算出与ｃ１欧氏距离式（１）最远的点ｘ′ｊ，作为第２个中心点ｃ２；３）用Ｘ中样本集计算出与Ｃ１中样本集之间的欧氏距离：ｄｉ１＝ ｘ′ｉ－ｃ１ 　ｉ＝１，２…ｎ；ｄｉ２＝ ｘ′ｉ－ｃ２ 　ｉ＝１，２…ｎ；在所有模式中选择｛ｍｉｎ（ｄｉ１，ｄｉ２）ｉ＝１，２…ｎ；｝中最大的作为第３个中心点ｃ３；即ｍｉｎ（ｄｊ１，ｄｊ２）＝ｍａｘ ｛ｍｉｎ（ｄｉ１，ｄｉ２）ｉ＝１，２…ｎ；｝ｊ＝１，２…ｎ；则ｃ３＝ｘ′ｊ；４）如果现有聚类中心的个数ｒ（ｒ＜ｋ），得到了Ｃ１＝｛ｘ′１，ｘ′２…ｘ′ｒ｝，即确定第ｒ＋１个中心点：ｍｉｎ（ｄｊ１，ｄｊ２…ｄｊｒ）＝ｍａｘ ｛ｍｉｎ （ｄｉ１，ｄｉ２…ｄｉｒ）ｉ＝１，２…ｎ；｝ｊ＝１，２…ｎ；则ｃｒ＋１＝ｘ′ｊ；５）重复４），直到获得ｋ个聚类中心，即Ｃ１＝ ｛ｘ′１，ｘ′２…ｘ′ｋ｝（３）用Ｃ１作为全局数据的初始聚类中心Ｃ＝ ｛ｘ１，ｘ２…ｘｋ｝，使用ＭａｐＲｅｄｕｃｅ框架实现Ｋ－ｍｅａｎｓ算法的并行运算并求出新的聚类中心Ｃ′。（４）计算出新的聚类中心Ｃ′与Ｃ的距离是否小于阀值Ｙ，如果小于Ｙ，则返回聚类中心Ｃ及聚类结果；否则用Ｃ′作为新的聚类中心重新聚类，直到新的聚类中心与上一次聚类中心之间的距离小于Ｙ时，聚类结束，返回聚类的中心与聚类结果。·１３１８·第３６卷　第５期　　韩岩，李晓：加速大数据聚类Ｋ－ｍｅａｎｓ算法的改进　３　实验与结果分析３．１　实验环境硬件：２．５ＧＨＺ的双核ＣＰＵ，硬盘５００Ｇ。软件：操作系统ＣｅｎｔＯＳ５，ｈａｄｏｏｐ１．０．４，Ｅｃｌｉｐｓｅ４．２，单机伪分布式与集群完全分布式环境。３．２　实验结果与分析实验说明：方法都是基于ＭａｐＲｅｄｕｃｅ的并行运算，普通Ｋ－ｍｅａｎｓ方法（Ｓ）：代表随机选择ｋ个聚类中心后用Ｋｍｅａｎｓ方法；最大最小距离的Ｋ－ｍｅａｎｓ （ＭＭ）：最大最小距离法计算出ｋ个聚类中心后再用Ｋ－ｍｅａｎｓ方法；抽样加最大最小距离的Ｋ－ｍｅａｎｓ（ＭＭＳ）：①先采用最大最小距离方法计算出抽样数据ｋ个初聚类中心Ｃ；②使用聚类中心Ｃ作为全局数据的初始聚类中心；③ 再使用并行化的Ｋｍｅａｎｓ方法计算出聚类的结果。记录数为ｎ，聚类个数为ｋ，终止条件为Ｙ，方法为Ｍ，加权准则函数为Ｊｃ，迭代次数ｔ，执行时间Ｔ。以下的结果是运行５次的平均结果。３．２．１　实验１：验证改进的Ｋ－ｍｅａｎｓ算法可行性首先才用人工标注的２０条测试数据进行测试，数据分布如图２所示。图２　标注数据分布实验１运行结果见表１。表１　不同方法不同聚类个数聚类结果ｋ／Ｙ　Ｍ　Ｊｃ　ｔ　Ｔ／ｓ４／１０－２Ｓ　５．５１０４　３．０　２２．１１ＭＭ　３．３４８７　２．０　１５．４９ＭＭＳ　３．３４８７　２．０　１５．２０５／１０－２Ｓ　３．４５２９　２．４　１５．０３ＭＭ　１．６２２８　２．０　１４．９３ＭＭＳ　１．６２２８　２．４　１５．０６６／１０－２Ｓ　１．５５９８　２．０　１５．０１ＭＭ　１．０７６２　２．０　１４．９５ＭＭＳ　１．０７６２　２．０　１５．０５从表１与图３的结果中得出使用最大最小距离法Ｋｍｅａｎｓ聚类取得了相同优化的解，而且在５次实验中保持了稳定性，且性能明显优于随机选择聚类中心的Ｋ－ｍｅａｎｓ，但于海量数据的聚类用最大最小距离方法来计算聚类中心很浪费时间的，甚至造成内存不足，所以提出了这种折中的方法用抽样数据中心代替全局数据初始聚类中心的聚类方法。图３　不同聚类个数与Ｊｃ趋势３．２．２　实验２：验证改进的Ｋ－ｍｅａｎｓ算法有效性实验说明：用随机产生的记录数来验证方法的有效性，记录数ｎ （单位：万）分别是１、１０、１００，环境：单机伪分布条件下，方法同上，聚类为１００时结果见表２。表２　单机下聚类结果ｎ　Ｙ　Ｍ　Ｊｃ　ｔ　Ｔ／ｓ１　１０－２Ｓ　０．４１９２　６．０　４３．８１ＭＭ　０．４０９１　５．０　９５．６６ＭＭＳ　０．４１０４　４．０　４３．３７１０　１０－２Ｓ　０．４２５２　８．０　１０８．３４ＭＭ　０．４１７５　３．０　４７４．８２ＭＭＳ　０．４２１２　３．０　４４．９５１００　１０－２Ｓ　０．４２３８　７．４　１１９５．１２ＭＭ 时间过长ＭＭＳ　０．４１９２　３．２　６３３．７０３．２．３　实验３：验证改进算法可以并行执行在虚拟机下４台均是装有ＣｅｎｔＯＳ５操作系统，内存５１２Ｍ，硬盘１００Ｇ，２．５Ｇｈｚ双核ＣＰＵ，其中一台是ｍａｓｔｅｒ，三台是Ｓｌａｖｅ。数据：使用实验２中数据。聚类为１００时在集群的运行结果见表３。表３　集群下运行结果ｎ　Ｙ　Ｍ　Ｊｃ　ｔ　Ｔ／ｓ１　１０－２Ｓ　０．４１９２　６．０　５７．１９ＭＭ　０．４１２１　３．０　５８．０６ＭＭＳ　０．４００１　３．０　２６．３３１０　１０－２Ｓ　０．４２５２　８．０　９１．３６ＭＭ　０．４１６３　３．０　４０２．４５ＭＭＳ　０．４２１２　３．０　４０．４６１００　１０－２Ｓ　０．４２４８　７．０　１０４９．４０ＭＭ　０．４２４１　５．０　４１５１．６４ＭＭＳ　０．４１５５　４．２　６０３．４０通过表２得出以下结论：当数据量较小时，最大最小距离法Ｊｃ的值最小且执行时间最短；随着数据量的增加，最大最小距离法计算聚类中心时间增加导致计算时间过长；·１３１９·　计算机工程与设计２０１５年继续增加数据量时，这种方法将不在适合聚类运算。大数据量时，这种改进的方法执行时间大大减少了且加权准则函数值也降低了，提高聚类的质量。表３与表２对比，在同样的条件下，执行的时间明显是降低的，但并没成比例的降低。原因如下：①实验３中４台虚拟机总内存和实验２中１台虚拟机内存是相同的；②实验中随机数据和抽样数据导致迭代次数不一样，但在平均执行一次的时间，集群运行效率要比单机时效率要高。这也说明了同样条件下，并行化操作提高了运行效率。尤其是在执行时间上提高了２～３倍。４　结束语本文主要通过Ｈａｄｏｏｐ平台上的ＭａｐＲｅｄｕｃｅ框架实现Ｋ－ｍｅａｎｓ算法并行化的聚类操作。实验结果表明：这种改进的方法选取了较优的初始聚类中心，降低了对初始聚类中心的依赖性，提高了聚类的质量及运行效率，加速了聚类的收敛速度。特别是在集群环境下，数据量较大时，完全随机分布的数据有明显的效果。下一步工作主要在于抽样数据质量与优化上再进行改进；集群优化与负载均衡等。参考文献：［１］ＺＨＯＵ　Ａｉｗｕ，ＣＵＩ　Ｄａｎｄａｎ，ＰＡＮ　Ｙｏｎｇ．Ａｎ　ｏｐｔｉｍｉｚａｔｉｏｎ　ｉｎｉｔｉａｌ　ｃｌｕｓｔｅｒｉｎｇ　ｃｅｎｔｅｒ　ｏｆ　Ｋ－ｍｅａｎｓ　ｃｌｕｓｔｅｒｉｎｇ　ａｌｇｏｒｉｔｈｍ ［Ｊ］．Ｍｉｃｒｏｃｏｍｐｕｔｅｒ　＆Ｉｔｓ　Ａｐｐｌｉｃａｔｉｏｎｓ，２０１１，３０ （１３）：１－３ （ｉｎ　Ｃｈｉｎｅｓｅ）．［周爱武，崔丹丹，潘勇．一种优化初始聚类中心的Ｋｍｅａｎｓ聚类算法［Ｊ］．微型机与应用，２０１１，３０ （１３）：１－３．］［２］ＷＡＮＧ　Ｊｉａ，ＪＩＡＮＧ　Ｍｉｎｇｆｕ，ＬＩ　Ｙｏｕｇｕｏ．Ａ　ｃｌｕｓｔｅｒ　ａｎａｌｙｓｉｓｍｅｔｈｏｄ　ｂａｓｅｄ　ｏｎ　ｉｍｐｒｏｖｅｄ　Ｋ－ｍｅａｎｓ　ａｌｇｏｒｉｔｈｍ ［Ｊ］．ＡｇｒｉｃｕｌｔｕｒｅＮｅｔｗｏｒｋ　Ｉｎｆｏｒｍａｔｉｏｎ，２００９，１０：１２０－１２２ （ｉｎ　Ｃｈｉｎｅｓｅ）． ［汪嘉，姜明富，李友国．一种基于改进的Ｋ－Ｍｅａｎｓ算法的聚类分析方法［Ｊ］．农业网络信息，２００９，１０：１２０－１２２．］［３］ＨＵＡＮＧ　Ｔａｏ，ＬＩＵ　Ｓｈｅｎｇｈｕｉ，ＴＡＮ　Ｙａｎｎａ．Ｒｅｓｅａｒｃｈ　ｏｆ　ｃｌｕｓｔｅｒｉｎｇ　ａｌｇｏｒｉｔｈｍ　ｂａｓｅｄ　ｏｎ　Ｋ－ｍｅａｎｓ［Ｊ］．Ｃｏｍｐｕｔｅｒ　Ｔｅｃｈｎｏｌｏｇｙａｎｄ　Ｄｅｖｅｌｏｐｍｅｎｔ，２０１１，２１ （７）：５４－５７ （ｉｎ　Ｃｈｉｎｅｓｅ）． ［黄韬，刘胜辉，谭艳娜．基于Ｋ－ｍｅａｎｓ聚类算法的研究［Ｊ］．计算机技术与发展，２０１１，２１ （７）：５４－５７．］［４］ＱＩＡＮ　Ｙａｎｊｉａｎｇ．Ｒｅｓｅａｒｃｈ　ａｎｄ　ｒｅａｌｉｚａｔｉｏｎ　ｏｆ　ｌａｒｇｅ－ｓｃａｌｅ　ｄａｔａｃｌｕｓｔｅｒｉｎｇ　ｔｅｃｈｎｉｑｕｅｓ ［Ｄ］．Ｃｈｅｎｇｄｕ：Ｃｈｅｎｇｄｕ　Ｕｎｉｖｅｒｓｉｔｙ，２００９ （ｉｎ　Ｃｈｉｎｅｓｅ）． ［钱彦江．大规模数据聚类技术研究与实现［Ｄ］．成都：电子科技大学，２００９．］［５］ＷＡＮＧ　Ｘｉｕｈｕａ．Ａ　ｐａｒａｌｌｅｌ　ｓｐｅｅｄｉｎｇ　Ｋ－ｍｅａｎｓ　ｃｌｕｓｔｅｒｉｎｇ　ｍｅｔｈｏｄ［Ｊ］．Ｃｏｍｐｕｔｅｒ　Ｋｎｏｗｌｅｄｇｅ　ａｎｄ　Ｔｅｃｈｎｏｌｏｇｙ，２０１３，９ （１８）：４２９９－４３０２ （ｉｎ　Ｃｈｉｎｅｓｅ）．［王秀华．一种并行的加速Ｋ－均值聚类方法［Ｊ］．电脑知识与技术，２０１３，９ （１８）：４２９９－４３０２．］［６］Ｓｒｉｒａｍａ　ＳＮ，Ｊａｋｏｖｉｔｓ　Ｐ，Ｖａｉｎｉｋｋｏ　Ｅ．Ａｄａｐｔｉｎｇ　ｓｃｉｅｎｔｉｆｉｃ　ｃｏｍｐｕｔｉｎｇ　ｐｒｏｂｌｅｍｓ　ｔｏ　ｃｌｏｕｄｓ　ｕｓｉｎｇ　ＭａｐＲｅｄｕｃｅ ［Ｊ］．Ｆｕｔｕｒｅ　Ｇｅｎｅｒａｔｉｏｎｓ　Ｃｏｍｐｕｔｅｒ　Ｓｙｓｔｅｍｓ，２０１２，３９ （１１）：１８４－１９２ （ｉｎＣｈｉｎｅｓｅ）． ［Ｓｒｉｒａｍａ　ＳＮ，Ｊａｋｏｖｉｔｓ　Ｐ，Ｖａｉｎｉｋｋｏ　Ｅ．使用ＭａｐＲｅｄｕｃｅ解决云端的科学计算问题［Ｊ］．下一代计算机系统，２０１２，３９ （１１）：１８４－１９２．］［７］ＨＡＮ　Ｊｉａｗｅｉ，ｋａｍｂｅｒ．Ｄａｔａ　ｍｉｎｉｎｇ：Ｃｏｎｃｅｐｔｓ　ａｎｄ　ｔｅｃｈｎｉｑｕｅｓ［Ｍ］．Ｂｅｉｊｉｎｇ：Ｍｅｃｈａｎｉｃａｌ　Ｉｎｄｕｓｔｒｙ　Ｐｒｅｓｓ，２００８：２８８－３７５ （ｉｎＣｈｉｎｅｓｅ）．［韩家炜，坎伯．数据挖掘概念与技术［Ｍ］．北京：机械工业出版社，２００８：２８８－３７５．］［８］ＴＩＡＮ　Ｓｈｅｎｐｉｎｇ， ＷＵ　Ｗｅｎｌｉａｎｇ． Ａｌｇｏｒｉｔｈｍ　ｏｆ　ａｕｔｏｍａｔｉｃｇａｉｎｅｄ　ｐａｒａｍｅｔｅｒ　ｖａｌｕｅ　ｋ　ｂａｓｅｄ　ｏｎ　ｄｙｎａｍｉｃ　Ｋ－ｍｅａｎｓ［Ｊ］．Ｃｏｍｐｕｔｅｒ　Ｅｎｇｉｎｅｅｒｉｎｇ　ａｎｄ　Ｄｅｓｉｇｎ，２０１１，３２ （１）：２７４－２７６ （ｉｎ　Ｃｈｉｎｅｓｅ）．［田森平，吴文亮．自动获取Ｋ－ｍｅａｎｓ聚类参数ｋ值的算法［Ｊ］．计算机工程与设计，２０１１，３２ （１）：２７４－２７６．］［９］ＺＨＯＵ　Ａｉｗｕ，ＹＵ　Ｙａｆｅｉ．Ｔｈｅ　ｒｅｓｅａｒｃｈ　ａｂｏｕｔ　ｃｌｕｓｔｅｒｉｎｇ　ａｌｇｏｒｉｔｈｍ　ｏｆ　Ｋ－ｍｅａｎｓ ［Ｊ］．Ｃｏｍｐｕｔｅｒ　Ｔｅｃｈｎｏｌｏｇｙ　ａｎｄ　Ｄｅｖｅｌｏｐｍｅｎｔ，２０１１，２１ （２）：６２－６５ （ｉｎ　Ｃｈｉｎｅｓｅ）． ［周爱武，于亚飞．Ｋ－ｍｅａｎｓ聚类算法的研究［Ｊ］．计算机技术与发展，２０１１，２１ （２）：６２－６５．］［１０］ＷＡＮＧ　Ｘｉｕｈｕａ．Ａ　ｓｐｅｅｄｉｎｇ　Ｋ－ｍｅａｎｓ　ｃｌｕｓｔｅｒｉｎｇ　ｍｅｔｈｏｄ　ｂａｓｅｄｏｎ　ｓａｍｐｌｉｎｇ ［Ｊ］．Ｃｏｍｐｕｔｅｒ　ａｎｄ　Ｍｏｄｅｒｎｉｚａｔｉｏｎ，２０１３ （１２）：２７－２９ （ｉｎ　Ｃｈｉｎｅｓｅ）．［王秀华．基于随机抽样的加速Ｋ－均值聚类方法［Ｊ］．计算机与现代化，２０１３ （１２）：２７－２９．］［１１］ＺＨＯＵ　Ｊｕａｎ，ＸＩＯＮＧ　Ｚｈｏｎｇｙａｎｇ，ＺＨＡＮＧ　Ｙｕｆａｎｇ．Ｍｕｌｔｉｓｅｅｄ　ｃｌｕｓｔｅｒｉｎｇ　ａｌｇｏｒｉｔｈｍ　ｂａｓｅｄ　ｏｎ　ｍａｘ－ｍｉｎ　ｄｉｓｔａｎｃｅ　ｍｅａｎｓ［Ｊ］．Ｃｏｍｐｕｔｅｒ　Ａｐｐｌｉｃａｔｉｏｎｓ，２００６，２６ （６）：１４２５－１４２７ （ｉｎＣｈｉｎｅｓｅ）．［周涓，熊忠阳，张玉芳，等．基于最大最小距离法的多中心聚类算法［Ｊ］．计算机应用，２００６，２６ （６）：１４２５－１４２７．］·１３２０·