云环境下K-means算法的并行化研究

胡珊

（广州工商学院 广东省广州市 510850）

K-means算法在工业和科学领域有着广泛的应用。在现代社会发展的背景下，一些新兴领域的出现和发展都需要依靠计算机系统和算法来实现。数字化技术带动了大数据、云计算等技术手段的出现和发展。其中，云计算为以数据挖掘为主要目的的算法程序优化提供了技术支持。对云环境下的K-means算法并行化进行分析，能够为K-means算法的优化和创新提供一定的建议。

1 K-means算法

1.1 K-means算法的简介

在信息技术和数字化技术得到不断发展的背景下，社会生产过程中产生的大量数据给各个行业和领域的发展带来了一定的难度，各项工作的开展都需要建立在数据挖掘的基础上，才能够应对这些海量的信息。算法程序是现阶段承担数据挖掘功能和作用的主要工具，将算法程序应用到计算机系统当中，能够有效满足数据挖掘和整理飞机的需要，对发挥数据在现代社会发展下的价值具有重要的作用[1]。K-means算法是算法程序中一种最为经典和常见的聚类算法，该算法在实际的应用中，能够将所有的数据对象按照不同的特征划分为不同的类别或簇，处在同一类别的数据能够呈现出高度的相似性。在将这些数据进行聚类分析之后，能够依据数据在不同类别中的分布情况，找到所有数据对象的分布模式和不同数据属性之间的相互关系。因而从本质上来说，K-means算法是一种能够对数据对象进行划分的方法。在现代社会科学技术水平不断提高的背景下，K-means算法的执行效率也在不断提高，能够满足许多大规模的数据对象的聚类分析和处理要求。

1.2 K-means算法的并行原理

从K-means算法的角度出发，基于数据分析和处理的相关要求，该算法程序在实际运行中主要包括数据并行和控制并行两种具体的并行策略和算法。数据并行与控制并行的算法都需要以实现数据挖掘和分析为主要目标，而在K-means算法的实际应用中，发现数据并行相比于控制并行拥有更多的优势。数据变形主要是指在将数据对象划分为多个数据子集之后，对每一个数据子集执行相同的操作，而控制并行则需要直接让数据对象执行不同的操作和指令[2]。在这个过程中，数据病情的算法能够符合串行算法的运行要求，同时也能够呈现出良好的可伸缩性，因而既能够满足串行算法的并行分析需求，也能够被应用到大规模数据集的处理当中。

以数据并行的算法为主，K-means算法在实际运行中，用k来代表数据对象被划分的聚类个数，在依据数据挖掘和分析处理的相关要求确定好需要划分的k值以后，基于k值随机选择初始对象数据点，并将这些数据点作为初始的聚类中心。在对各个数据对象与聚类中心之间的距离进行计算之后，依据距离的计算结果，将各个数据对象分配到与其距离最近的类中。然后需要重新对各个聚类的中心进行计算，并将计算的结果与之前计算的结果进行对比分析[3]。如果两次计算的聚类中心距离没有发生变化，就证明对这一部分的数据对象调整过程已经结束。而如果两次计算结果不同，则证明聚类准则函数没有收敛，需要将数据对象重新返回到分配类的环节，并重复后续的步骤，直到对比结果没有发生变化，证明整个算法过程成功。

在传统的K-means算法原理基础上，基于当前大数据集对算法运行的相关要求，充分发挥数据并行算法的应用优势，可以有效解决遗忘K-means算法应用中存在的一些问题。以数据并行来改进K-means算法，主要可以通过分布式聚类算法的方式来实现。该算法在实际的运行中，一般需要设置p个站点，在从这些站点中选择一个主站点之后，其余的站点均为从站点[4]。在主站点随机产生K个聚类中心之后，各个从站点能够依据自身接收到的信息，确认从站点自身所在的数据对象总数，在将其传送到主站点之后，由主站点来进行全局聚簇中心的计算。

由于该算法也是在K-means算法的基础上进行改进和优化的，因而无论是算法的实际运行流程还是特点，都与K-means算法有着较大的相似性。结合K-means算法的运行流程来看，该算法在依据各个步骤运行的过程中，能够满足动态的聚类算法分析需要，因而该算法在实际运行中还能够体现出迭代过程的特点[5]。如果在整个迭代过程中的所有数据对象都能够被重新分类，那么就不会再发生聚类中心的改变和调整。而在改进的算法当中，这一迭代过程稳定的主要标志是全局聚簇中心的稳定。与传统的K-means算法不同的是，改进后的算法不需要在整个算法程序的运行过程中传送大量的数据对象，一般只需要对聚簇中心涉及到的数据对象总数进行传送，就能够满足对各类数据对象进行传送的要求[6]。在这个过程中，算法运行不需要消耗较高的通信量，因而能够有效提高算法程序的实际运行效率。

2 云环境下K-means算法的并行化分析

数字化技术和信息技术的发展，使得大数据、云计算等先进的技术被应用到对各种数据的挖掘和分析处理当中。其中，以云计算技术作为技术基础的云环境的出现和应用，能够发挥处理和开发大量数据的功能作用，以更大的储存空间来满足大量数据信息的储存和处理分析要求。而云环境相比于以往的数据处理系统光和平台，还能够以更低的成本来提高数据处理和分析的效率，因而能够呈现出更为显著的性能优势[7]。K-means算法的并行化是当前该算法程序发展的主要方向和趋势。在云环境下对K-means算法的并行化进行分析，主要可以从以下几个方面来入手：

2.1 基于云环境的K-means算法设计

在云环境下，针对K-means算法并行化分析的过程中，首先要对算法进行设计，此为分析过程的关键。具体而言，云环境主要是基于云计算逐渐产生并发展起来的，云计算作为现代社会一种先进的商业计算模型，是满足云环境下数据分析和处理需求的主要依据。在云环境下对K-means算法进行设计，最主要的就是明确云计算的结构组成和运行程序。当前云环境中应用的云计算平台以Hadoop平台最为常见，Hadoop平台由Map Reduce计算模型以及HDFS两部分组成。其中，Map Reduce计算模型是该平台能够在运行中体现出分布式特点的主要依据，作为一种典型的分布式编程模型，该计算模型在实际的应用中具有更高的效率，能够满足对海量数据信息进行处理和分析的要求。在云计算平台的主要运行框架下，该计算模型主要能够借助Map函数和Reduce函数来确定对运行参数的输出位置以及输入位置。同时，在云计算平台的框架中，该计算模型还可以让用户自行设置函数，以便能够对每一组数据进行处理。而HDFS则主要是一种借助M/S结构运行的框架。在实际对数据信息进行分析的过程中，由于每一个数据集群都是由数据节点和管理节点组成的，而每一个具体的节点又分别属于独立的PC端，因而在实际的应用过程中，HDFS本身与文件系统之间能够呈现出较为明显的相似性特征，不仅能够用于创建文件目录，还能够实现对格列文件的复制、查看等基本的操作。而在其实际的运用过程中，也可以发现HDFS实现的所有功能都是围绕着数据节点的管理展开的。依据数据节点的管理要求。HDFS不仅能够对某一组加工的数据结构进行维护，还能够以类似于文件系统的功能来实现对每一个数据文件在处理过程中的信息的及时记录。对此，相关人员在利用这一算法时，需要针对上述问题加以重视。

在明确云计算平台的主要构成和基本功能之后，就可以将云计算平台与K-means算法融合起来。结合K-means算法的主要运行流程，对K-means聚类算法的设计，需要能够重点从算法程序中数据信息发送到较近距离的聚簇这一环节入手，将K-means算法在实际应用中的迭代过程与云计算平台中的Map以及Reduce结合起来。以此为原理，发现在云环境下的K-means算法设计，主要由以下几个方面组成：

（1）对于K-means算法的设计需要重视Map函数在算法运行程序中的应用。基于Map函数在云计算平台中的重要作用，对Map函数的设计，需要能够从函数输入键值的角度入手，将函数输入数据文件的起始点偏移量与字符串联系起来。具体来说，首先需要在字符串中队输入的坐标值数进行解析。在得到相应的解析结果之后，计算得出字符串与中心点之间的距离，并找出中心点聚簇的下标，在将键值输出之后，就能够得到相应的函数计算结果。而针对以往K-means算法在运行中消耗的通信量问题，可以将Map函数与Combine操作结合起来，将得到的函数结果和操作结果结合起来，尽可能地减少在实际算法运行过程中消耗的通信量。

（2）对于Combine函数的设计，需要在得到Map函数结果的基础上，在字符串联表中对坐标指数进行解析，依据解析的结果来将坐标值数相加，并依据字符串联表来记录依据解析结果产生的样本总数。在函数计算和程序运行之后，还会产生相应的键值。这些键值一般就是距离聚簇最近的下标。而字符串联表中则能够呈现出整个函数计算过程中产生的坐标值数。

（3）对于Reduce函数的设计，需要利用Reduce函数来将Combine函数中由于数据传输而产生的中间结果进行解析，并将解析的结果与对应的Reduce函数值进行累加，将得到的累加数值除去总的样本数量，所得到的结果就是算法程序运行过程中产生的新中心点坐标。在这个过程中，Reduce函数的运行不仅能够满足新的中心点坐标点定位，同时也能够为HDFS中的文件更新提供技术支持，让K-means算法能够在云环境下满足迭代过程的运行需要，直到完成所有的数据信息分类。

2.2 算法的复杂度分析

结合K-means算法的应用情况来看，该算法所依据的聚类分析原理，主要是一种能够将整个数据集按照不同的标准划分为多个子集的过程。而依据这种聚类算法，可以让处于同一类子集中的数据呈现出高度的相似性，让处于不同类子集中的数据呈现出不相似的特点。能够对一个总的数据集进行聚类划分并判断是否相似，主要是由数据对象本身具有的描述属性取值来决定的。K-means算法所依据的数据对象描述属性取值，主要是各个聚类间的距离大小来决定的。

基于聚类分析的原理，从算法复杂度的角度来看，K-means算法的复杂度主要能够体现在时间复杂度和通信复杂度两个方面。对于聚类算法的复杂度进行计算，通常需要以每一个聚类分析后得到的数据点与相应中心矢量之间的距离作为依据。在K-means算法的运行过程中，从一个站点向另一个站点传输数据，一般需要事先对算法程度重复步骤过程中体现的复杂度进行分析。从时间复杂度的角度来看，在将时间复杂度设置为一个数据项的实际通行时间之后，在并行执行的情况下，通过模拟一次数据传送的过程，确定整个算法流程中每一步的复杂度。用公式可以表示为：

Ttime=Tstart+KTdata

在该式中，Ttime代表时间复杂度，Tstart代表建立数据连接所需要的时间，K为算法确定的聚簇个数，Tdata代表数据项。

对于K-means算法的通信复杂度的计算，与时间复杂度的计算基本相同，在列举K-means算法的时间复杂度和通信复杂度的计算流程之后，将两种复杂度的计算方法整合起来，就可以得到一个关于K-means算法的复杂度表达式：

Ttime=TKTdata，Tcomm=TKTdist

其中，Tcomm代表通信复杂度，Tdist代表单一数据点距离的时间，两式中的T均为K-means算法的循环次数。

2.3 实验分析

K-means算法作为一种经典的算法程序，能够有效满足数据挖掘和聚类分析的需要。基于K-means算法在实际应用中存在的缺陷和不足，提出了针对K-means算法程序运行的改进方法。在对改进方法的实验进行分析的过程中，考虑到K-means算法本身在操作运行中需要以随机初始化中心点为前提条件，因而在实验中的数据计算时，一般需要设置10次以上的重复执行次数，在让每一组数据的实验结果取平均值的前提下，保证实验结果的准确性。

在实验的过程中，一方面需要基于K-means聚类算法的实际应用流程和要求，以提升算法本身的加速比性能为主要目标，在实验中将数据集规模作为主要的变量，并在得到结果后将结果与传统K-means算法下的函数计算结果进行对比分析。在具体的实验过程中，以二维数据作为实验的主要数据来源。

在将这些数据都上传到K-means算法之后，让k取不同的值带入到云计算平台中的DataNode中，依据数据分配情况来创建全局文件，并选取号全局文件的中心点。在算法程序的整个运行过程中，算法程序中的每个节点都可以通过读取全局文件的方式来获得迭代过程产生的信息，并计算从节点的数据点到迭代过程信息之间的距离，进而得到迭代后的数据。

2.4 K-means算法的优缺点

结合K-means算法的实际应用情况来看，在聚类算法的分析原理基础上，算法程序在实际运行中能够尽可能的尝试找出更符合总数据集的详细划分k的方法。当被划分的各个聚簇之间能够呈现出明显的不相似特征情况下，就能够呈现出更为明显的聚类分析效果。而在对K-means算法以及改进算法的应用情况进行分析之后可以发现，K-means聚类算法在实际的应用中，能够以更为简便的程序和算法方式，满足大的数据集聚类分析和处理的需要。而由于K-means算法中的数据控制算法能够体现出明显的可伸缩性特点，且该算法在时间复杂度的表现上能够呈现出明显的线性特征，因而相对来说更适合对大规模的数据集进行聚类分析和处理。

但从实际应用K-means算法的经验来看，该算法在应用中也存在着一定的问题，仍需要对该算法进行不断的优化和改进，才能够更好的为当前社会发展过程中的各类大规模数据集进行分析处理。具体来说，K-means算法在应用中，主要存在着以下几个方面的问题：

（1）K-means算法程序的运行需要以确定的聚类k值作为依据，但聚类k值通常需要由用户在应用算法之间来指定。而用户应用K-means算法的目的就是对数据集进行聚类分析，在用户本身并不了解需要将整体的数据集划分为多少k值得情况下，就会因为k值得难以估计而影响到算法程序的整体运行情况。

（2）在K-means算法运行的过程中，对于初始聚类中心的选取本身具有较大的随机性，而由于初始聚类中心的确定对整个算法程序的正常运行也具有决定性的作用，在初始聚类中心的位置确定不明确的情况下，整个算法在运行中很容易陷入到局部最小解的困境当中，进而影响到算法分析结果的准确性和科学性。同时，由于K-means算法程序在实际运行中需要依据误差平方和准则函数来进行数据集的聚类分析，受到这类非凸函数多个局部极小值的影响，也会给在算法中寻找全局最优解造成一定的难度。

（3）K-means算法在实际的运行过程中，很容易在聚簇质心计算过程中，将其以聚类中心的形式进行计算，使得聚类中心在运行和计算的过程中逐渐原理数据密集区。在这个过程中，随着聚类中心和数据密集区之间距离的不断增加，在产生噪声和受到孤立点数据的影响下，最终的聚类分析结果很容易与实际不符。在现阶段对K-means算法的改进和优化过程中，通常可以应用参考点和密度的调整来满足参考点数据的分析和处理需要。

（4）K-means算法在实际的应用过程中，还会因为受到时间复杂度的影响而产生较大的算法开销。具体来说，由于K-means算法本身处于不断的调整和优化当中，每当算法优化之后，初始中心就需要通过计算来重新调整。在这个过程中，如果算法程序涉及到的数据量较大，很容易提高算法程序在实际运行中消耗的成本。对于这种问题，在对K-means算法进行优化的过程中，通常需要从算法本身所具有的时间复杂度入手，对算法的时间复杂度加以改进的方式，不断提高算法本身的应用范围和算法本身的收敛速度，让K-means算法能够被应用到更多的行业和领域发展当中。

（5）结合K-means算法的应用原理来看，尽管K-means算法在实际应用中能够将总的数据集划分为多个不相似的聚簇，但该算法中应用的聚类算法通常需要以欧式距离和误差平方作为算法运行和判断的依据，只能够在对数据进行聚类分析的过程中发现一些数据分布较为均匀的球状聚簇，难以发现数据集中的形状不规则的、任意的聚簇，这样就会很容易影响到算法聚类分析的最终结果。因而在对K-means算法进行优化和改进的过程中，也需要能够针对非球状聚簇的特点和分布情况，对这些非球状聚簇的伸长方向进行聚类分析，从而更好的满足对数据集进行聚类分析的需要。

2.5 K-means算法的未来发展趋势

在现代社会的发展过程中，云环境作为一种更为先进的数据挖掘和处理平台，在各个行业和领域的发展中得到了越来越广泛的应用。将云环境与算法程序的运行结合起来，能够充分发挥二者在数据挖掘和分析处理过程中的优势，满足各个行业和领域生产发展的需要。结合以上的分析可以发现，当前应用的K-means算法仍存在一定的缺陷和不足，在云环境越来越得到人们重视的背景下，K-means算法也需要能够借助云环境中的云计算平台应用优势，在改进算法程序自身运行过程中存在的缺陷基础上，推动K-means聚类算法以并行化的方式，逐渐朝着算法网络化和现代化的方向发展，以此来更好的满足各种大规模数据集的分析要求，让各种数据信息能够在各个行业和领域的发展中积极发挥自身的作用和价值。基于这方面的要求，K-means算法在未来的发展中，需要能够将改进和优化的重点放到探讨聚类算法禀性化的规律上，以便能够不断提升K-means算法的应用效果。

3 结论

综上所述，在云环境下，K-means算法虽然仍然是最为常见的一种算法程序，但在应用中也存在着一定的不足。考虑到现代社会各个行业和领域的现代化、数字化发展需求，K-means算法的优化和创新也需要能够符合时代的发展趋势。作为一种经典的聚类算法，K-means算法能够有效满足数据挖掘的基本需求。在未来的发展中，K-means算法也需要朝着更加网络化和服务化的方向发展。