基于改进的K-means算法初始化方法研究

马 健

(亳州职业技术学院 信息工程系,安徽 亳州 236800)

随着大数据时代的来临，人们在信息处理工作中面临着大量的信息.信息过多很难从大量的数据中快速的找到有价值的信息，为了解决这一现象，信息处理和分析工具便成为各种领域不可缺少的工具.信息处理技术受到人们的关注，通过大数据挖掘技术能够将数量庞大的信息转化为更有价值的数据，在数据挖掘技术中包含关联规则、预测、时间序列、聚类分析等.

聚类分析方法通过计算数据间的相似性或其他评估准则将大量数据加以区分开来，使得被区分开的数据形成许多的聚类，而所有聚类都具备有相同聚类内的数据拥有较高的相似性，而不同聚类间的数据则产生较大差别的特性[1].聚类分析方法就是为了解决大数据中复杂数据，并将数据划分多个类型数据进行归类整理，同一种类型的数据相似度非常高，不同类型的数据差异较大.由于聚类分析具备重要的功能，因此被广泛应用于许多领域中，例如人工智能、图形识别、统计方法、压缩技术、机器学习、与市场研究等.随着信息技术不断发展，大数据处理方法越来越被人们所应有，而聚类分析方法主要分为：划分式聚类分析方法、阶层式聚类分析方法、密度聚类分析方法与网格聚类分析方法的四种方法[2].

划分式聚类分析方法是最常用的聚类分析方法，而K-means 算法中最经常使用的聚类分析算法中具有代表性的算法[3].K-means 算法具备高效率、概念简单等优点.通过聚类分析获得数据的相似度，但同时存在一定的不足之处，例如K-means算法采用的随机选取初始聚类中心的方式，使得整体效率稳健性不足并且可能导致收敛至较差结果的可能性.本研究针对K-means算法不足之处进行分析研究，提出一个改进的K-means算法的初始化方法来解决该问题[4].

1 K-means算法与改进的K-means算法

通过对选取的初始聚类中心进行研究，可以得知聚类中心的选取影响着K-means算法执行的效率，提出一个新的聚类分析IKM方法.

1.1 K-means算法

K-means算法是比较常用的一种聚类方法，在多个领域都有应用，并具备以下的优点：概念较为简单、对于较大的数据集合也能够有很好的效率、有较高的可扩充性.但是K-means有一定的缺陷，不能对聚类的结果重复操作，显示不了非凸集的数据[5-6].

1.1.1 初始聚类中心的选取

1.1.2 聚类数目的选取

K-means算法在执行之前，首先来确定输入的聚类数目，也就是参数K.虽然对于使用者而言，聚类数目已经是非常容易理解的参数[8].然而，对于不具备相关领域知识的使用者而言，将难以适当地决定K值，而且错误的选择K值直接影响聚类结果的正确性.

1.1.3 K-means 算法执行步骤

算法执行步骤如图1所示.

1.1.4 K-means算法的时间复杂度

假设输入的数据共有n个，且数据的维度为d，K-means算法执行的一个循环的时间复杂度主要由3部分组成[9].首先执行K-means算法中的第2和第3步骤，这个部分的时间复杂度为O(nkd).其次，执行K-means算法中的步骤4，将这个部分时间复杂度为O(nd).最后，通过计算得到失真值，用来判断聚类是否停止，将此部分的时间复杂度为O(nd).

当前认可程度较高的公开病毒序列数据源系统（Gen-Bank、EMBL、DDBJ）都提供免费的数据资源存储、管理和分发的服务，其数据涵盖了动物、植物、微生物（病毒、细菌、真菌等）等。这里的数据源包含来自不同数据源系统的异构数据。按照数据结构和格式的不同也可以将数据源分为平面文件、关系数据库、XML文件等。

1.2 IKM算法

本研究根据先前对于K-means算法问题的探讨，提出改善的IKM算法.IKM 算法分为2个阶段进行：①用以选取初始聚类中心、决定聚类数目、识别复杂的数据；②根据阶段一的结果执行原始K-means算法，下面对IKM算法进行说明[10].

1.2.1 IKM算法的步骤

IKM算法的执行过程如图2所示.

1.2.2 IKM算法的时间复杂度

假设输入的数据共有n个，且各数据的维度为d，网格总数为g，所判断的聚类数目为k.则IKM算法的时间复杂度分析如下：

1) 计算每个数据到聚类中心的距离并分配数据与距离最近的聚类，时间复杂度为O(nkd).

2) 计算各聚类的平均值重新设置新的聚类中心，时间复杂度为O(nd).

3) 判断失真值是否收敛，如果收敛将停止聚类分析，时间复杂度为O(nd).

通过上面的分析，可以得知数据集趋近于无限大时，则 IKM 算法整体的时间复杂度为O(n).

2 模拟实验与结果分析

2.1 实验数据准备

为了能够确切地了解 IKM 与 K-means的差异，实验采用数据集(如表1所示).每一种数据集分别具备不同的聚类数目、聚类大小、聚类重迭情况、以及复杂的数据.另外为了解数据数量与数据维度对IKM与K-means的影响，产生维度1至16的数据.

2.2 实验过程及结果

实验操作的参数设定说明如下：K-means聚类数目(K)是根据人工数据的原始设定来决定.IKM 的各维度区间划分数量(u=dg)设定为u=[d100]且2≤u≤10.判定核心网格与复杂的网格所采用的标准偏差则都设定为1.实验操作IKM与K-means所得的结果将以图表方式呈现，其中包括了聚类数目、循环次数、失真值、复杂的数据、以及各个聚类的数据量与聚类中心等重要信息，并附上可视化的聚类结果图示以利判断结果的正确性.表1即为不同数据维度下的实验数据.

表1 IKM与K-means的不同数据维度下的实验数据

2.2.1 效率分析比较

本实验对于效率的评估标准为聚类分析方法的循环次数与执行时间比率(IKM/K-means).实验操作则针对两项变数探讨IKM与K-means的效率，两项变数分别是：数据的数量与数据维度.

1) 数据的数量分析比较. 理论上而言，当数据数量n趋近于无限大时，IKM与K-means的时间复杂度都为O(n).而就实际操作而言，本实验自表1中整理出2种方法的循环次数以及执行时间比率随数据量上升后的折线图3与图4所示.

从图3显示出 K-means 所需的循环次数随着数据的数量增加而有上升的趋势.由此可知，随着数据的数量的上升，K-means 整体的效率将受到过多的循环次数影响.纵使循环次数的上升有其限度，在数据的数量庞大的情况下将严重影响效率.反观 IKM 的循环次数则维持在少数几次，完全不受数据的数量影响.

除了循环次数外，由图4可以观察到 IKM 对于 K-means的执行时间比率，随着数据数量增加呈现出下降的趋势.因此，更加证实数据数量对于 K-means效率的影响胜过 IKM.综合上述观察，本实验推论 IKM 虽然因为较长的初始化时间而导致在数据数量较少时整体效率较差.然而随着数据量增加，IKM 的整体效率将逐渐赶上甚至超越 K-means.

2)维度比较. 为了解数据维度对于 IKM 与 K-means 效率的影响，本实验由表 1 中整理出两种方法的循环次数以及执行时间比率随数据维度上升后的折线图5 与图6所示.

为了避免数据数量对 K-means 算法造成太大影响，故本次实验操作都采用较小的数据集合(1 000 个数据)，因此2种方法的循环次数都不多.由图 3 能够观察到 IKM 与 K-means 的循环次数皆不太受数据维度的影响，但是 IKM 演算法的循环次数依然少于 K-means.

2.2.2 正确性

本实验对于正确性的评估标准为聚类结果的误判率与失真值.其中误判率的计算方式为分群前后同一聚类内数据点数差的总和取绝对值后除以总数据的数量，公式如下：

(1)

其中ER为误判率；Ai与Bi为K个聚类分群前后的数据的数量；N为总数据量.而失真值的计算方式为各聚类内数据至该聚类中心的距离的和，公式如下

(2)

其中E为失真值，il与wj分别为K个聚类内的数据与聚类中心.实验操作则针对两项变数探讨IKM 与K-means的正确性，变数分别是：聚类大小、重迭情况.

1)聚类大小.当聚类大小相同时，IKM与K-means都能完整地找出正确的聚类；然而当聚类大小相异时，两种方法都发生误判的情况，同时失真值大幅度增加.对于IKM算法同样继承了K-means的问题，但在误判率与失真值方面优于K-means算法.

2)重叠分析.当聚类无重迭情况时，IKM与K-means都完整地找出正确的聚类；而当聚类具备轻微重迭情况时，则IKM与K-means都开始出现误判的情况，但是观察数据可以发现此时 IKM的误判率与失真值稍低于K-means；然而当聚类具备严重重迭情况时，可以发现IKM 的误判率远高于K-means，并且失真值较K-means高出许多.造成此种结果的因素，与 IKM所判断的聚类数目与数据设定的聚类数目不同有关的误判率以K=2为计算基础.

3)复杂数据分析.无论是否有复杂数据，IKM与K-means的误判率与失真值都相同，并且两种方法都无法辨别出复杂数据.如果根据原先设定的复杂网格判断条件，则IKM算法并不具备辨别复杂数据的能力，如表2所示.

表2 IKM于不同复杂网格判断条件下的实验数据

当复杂网格的判断条件改变后，IKM便能够顺利辨别出复杂数据.除此之外，不同判断条件辨别复杂数据的能力也是有所差别.表2的实验数据显示出当复杂网格判断条件为平均值减0.15个标准偏差时，能够获得最低的误判率，并且所辨别出的复杂数据数量是最接近原始数据设定.所以本研究调整负责网格的判断条件为平均值减0.15个标准偏差.

3 结语

K-means算法是数据挖掘等信息处理应用在进行聚类计算时的常用工具之一，与其他分群方法相较，它具有简单与高效率等优点，但也存在一些可能改善强化的空间.本研究针对 K-means算法的缺点与不足之处提出一个新方法：Improved K-means算法(简称为IKM算法)用以协助改善K-means演算法初始聚类中心的适当选取；同时并且具备无须使用者输入参数以及识别复杂的数据的能力.IKM算法针对第一阶段的初始聚类中心选取方法进行改善，IKM 算法引用密度基础方法的概念，同时运用网格的方式，以达成自动决定聚类数目与识别复杂的数据目的，选出有利于K-means算法快速收敛至最后结果的初始群中心，并且提升整体的效率.