基于聚类分析的K-means算法研究及应用

　　摘要：通过对聚类分析及其算法的论述，从多个方面对这些算法性能进行比较，同时以儿童生长发育时期的数据为例通过聚类分析的软件和改进的K－means算法来进一步阐述聚类分析在数据挖掘中的实践应用。?
　　关键词：数据挖掘；聚类分析；数据库；聚类算法 ?
　　
　　随着机硬件和软件技术的飞速，尤其是数据库技术的普及，人们面临着日益扩张的数据海洋，原来的数据分析工具已无法有效地为决策者提供决策支持所需要的相关知识，从而形成一种独特的现象“丰富的数据，贫乏的知识”。数据挖掘[1]又称为数据库中知识发现（Knowledge Discovery from Database，KDD），它是一个从大量数据中抽取挖掘出未知的、有价值的模式或等知识的复杂过程。目的是在大量的数据中发现人们感兴趣的知识。?
　　常用的数据挖掘技术包括关联分析、异类分析、分类与预测、聚类分析以及演化分析等。由于数据库中收集了大量的数据，聚类分析已经成为数据挖掘领域的重要技术之一。?
　　
　　1问题的提出?
　　
　　随着社会的发展和人们生活水平的提高，优育观念[2，3]逐渐渗透到每个家庭，小儿的生长发育越来越引起家长们的重视。每隔几年都要进行全国儿童营养调查，然而用手工计算的方法在大量的数据中分析出其中的特点和规律，显然是不现实的，也是不可行的。为了有效地解决这个问题，数据挖掘技术——聚类分析发挥了巨大的作用。?
　　在数据挖掘领域，聚类算法经常遇到一些问题如聚类初始点的选择[4]、模糊因子的确定[5]等，大部分均已得到解决。现在的研究工作主要集中在为大型的数据库有效聚类分析寻找适当的方法、聚类算法对复杂分布数据和类别性数据聚类的有效性以及高维数据聚类技术等方面。本文通过对聚类分析算法的分析并重点从聚类分析的软件工具和改进的K－means算法两个方面来论证聚类分析在儿童生长发育时期中的应用。?
　　
　　2聚类算法分析?
　　
　　聚类[6]分析是直接比较各事物之间的性质，将性质相近的归为一类，将性质差别较大的归入不同的类。在医学实践中也经常需要做分类工作，如根据病人的一系列症状、体征和生化检查的结果，判断病人所患疾病的类型；或对一系列检查方法及其结果，将之划分成某几种方法适合用于甲类病的检查，另几种方法适合用于乙类病的检查，等等。聚类分析被广泛研究了许多年。基于聚类分析的工具已经被加入到许多统计分析软件包或系统中，如S－Plus、SPSS,以及SAS。?
　　大体上，聚类算法[7]可以划分为如下几类：?
　　
　　（2）层次方法。该方法就是通过分解所给定的数据对象集来创建一个层次。它存在的缺陷就是在进行（组）分解或合并之后无法回溯。将循环再定位与层次方法结合起来使用常常是有效的，如BIRCH和CURE，就是基于这种组合方法设计的。?
　　（3）基于密度的方法。只要临近区域的密度（对象或数据点的数目）超过某个阈值，就继续聚类。DBSCAN是一个有代表性的基于密度的方法。它根据一个密度阈值来控制簇的增长。?
　　（4）基于网格的方法。基于网格方法将对象空间划分为有限数目的单元以形成网格结构。其主要优点是它的处理速度很快，其处理时间独立于数据对象的数目，只与量化空间中每一维的单元数目有关。STING 就是一个典型的基于网格的方法。?
　　（5）基于模型的方法。该方法就是为每个聚类假设一个模型，然后再去发现符合相应模型的数据对象。它根据标准统计方法并考虑到噪声或异常数据，可以自动确定聚类个数；因而它可以产生很鲁棒的聚类方法。?
　　数据挖掘在不同领域对聚类算法提出了各自特殊的要求,表1可以给聚类算法的研究和应用提供[7]。?
　　
　　3儿童生长发育的分析?
　　
　　聚类分析在数据挖掘中的应用主要有以下三个方面：?
　　（1）聚类分析能作为一个独立的工具来获得数据的分布情况，观察每个簇的特点，集中对特定的某些簇作进一步的分析。如：①聚类分析软件 v1.2。此软件主要用于血型、蛋白质多态、品种聚类等方面的统计分析，可自动进行杂合度、多态信息含量、遗传距离以及聚类的计算，并可自动画出聚类图。②SPSS统计软件。SPSS软件是一种专业的统计分析软件，用于数据的各种分析，从而最终为企、事业的决策服务。其中采用聚类分析是理想的多变量统计技术，主要有分层聚类法和迭代聚类法。?
　　本文通过一组儿童生长发育的数据运用SPSS工具进行分析，如表2所示。?
　　
　　运用SPSS工具调用K－means Cluster过程可完成由用户指定类别数的大样本资料的逐步聚类分析。逐步聚类分析就是先把被聚对象进行初始分类，然后逐步调整，得到最终分类。?
　　为研究儿童生长发育的分期，笔者对1 253名1月~7岁儿童进行了抽样调查，分别对儿童的身高（cm）、体重（kg）、胸围（cm）和坐高（cm）进行了测量。资料作如下整理：先把1月~7岁划成19个月份段，分月份算出各指标的平均值，将第1月的各指标平均值与出生时的各指标平均值比较，求出月平均增长率（%），然后第2月起的各月份指标平均值均与前一月比较，求出月平均增长率（%）（表2）。将儿童生长发育时期分为四期，所以聚类的类别数为4，从而确定四个儿童生长发育期的起止区间。?
　　①激活数据管理窗口，定义变量名。虽然月份分组不做分析变量，但为了更直观地了解聚类结果，也将之输入数据库。?
　　②进行统计分析，在聚类方法上选择Iterate and classify指定初始类别中心点，按K－means算法作迭代分类。对聚类结果进行方差分析。　　结果解释：首先系统根据用户的指定，按四类聚合确定初始聚类的各变量中心点，未经K－means算法迭代，其类别间距离并非最优；经迭代运算后类别间各变量中心值得到修正。?
　　③对聚类结果的类别间距离进行方差分析。方差分析表明，类别间距离差异的概率值均小于0.001，即聚类效果好。这样，原有19类（即原有的19个月份分组）聚合成四类，第一类含原有1类，第二类含原有1类，第三类含原有2类，第四类含原有15类。具体结果系统以变量名qcl_1存于原始数据库中。?
　　 在原始数据库（图1）中，可清楚地看到聚类结果；参照专业知识，将儿童生长发育分期定为：?
　　 第一期，出生后至满月，增长率最高；?
　　 第二期，第2个月起至第3个月，增长率次之；?
　　 第三期，第3个月起至第8个月，增长率减缓；?
　　 第四期，第8个月后，增长率显著减缓。?
　　图1逐步聚类分析的分类结果?
　　（2）运用聚类分析软件可以很方便地对数据进行分析，利用分析的结果，在孩子生长发育时期合理安排好饮食，促进儿童健康快乐成长。同时，聚类分析可以作为其他算法（如特征和分类等）的预处理步骤，这些算法再在生成的簇上进行处理。本文以改进的K－means算法[9]为例来说明儿童生长发育时期的特征。算法描述如下：?
　　算法：K－means。划分的K－means算法基于簇中对象的平均值。?
　　输入：簇的数目?k?=4和输入?n?=19的表2的数据。?
　　输出：四个簇，使平方误差准则最小。?
　　方法：?
　　①任意选择四个对象作为初始簇的中心；?
　　②repeat；?
　　③根据簇中对象的平均值，将每个对象（重新）赋给最类似的簇；?
　　
本文原文
　　④更新簇的平均值，即每个簇中对象的平均值；?
　　⑤until 不再发生变化。?
　　在本算法中要用到以下几个定义：?
　　
　　（3）聚类分析也可以进行孤立点的分析。经常存在一些数据对象，它们不符合数据的一般模型，这些数据对象被称为孤立点。孤立点的分析有着广泛的应用[12，13]，如欺诈检测即探询不寻常的信用卡使用或电信服务；此外，它在市场分析中可用于确定极低或极高收入的客户的消费行为、或者在医疗分析中用于发现对多种方式的不寻常的反应。?
　　
　　4结束语?
　　
　　本文通过改进的K－means算法和聚类分析工具SPSS来对儿童生长发育期进行分析。?
　　在科技的今天，随着信息化产业的不断发展，大量的数据迫切需要强有力的数据分析工具的出现，从而导致了数据挖掘的蓬勃发展，而聚类分析已经成为数据挖掘领域一个非常活跃的研究课题。用户当然希望聚类的结果是可解释的、可理解的和可应用的。如何选择聚类方法和正确地使用聚类算法也是很重要的，而目前所使用的聚类算法均存在某方面的缺陷，也没有统一的标准，因此如何使聚类算法成为像SQL语言那样统一、标准的语言，还有待于计算机工作者的努力。?
　　
　　：?
　　［1］朱明.数据挖掘[M].合肥：技术大学出版社，2002：5－6.?
　　[2]卫生部关于八省（自治区）婴幼儿营养健康状况调查报告[R].北京：新华出版社，2005:1－3.?
　　[3]杭燕.幼儿园体育课程模式的探索（上）[J]. 学前文荟,2000（6）:10－12.?
　　[4]GONZALEZ T.Clustering to minimize and maximum intercluster distance[J].Theoretical Computer Science,1985,38（2－3）:293－306.?
　　[5]PAL N R,BEZDEK J C.On cluster validity for the fuzzy c－means model[J].IEEE Transactions on Fuzzy Systems,1995,3(3):370－379.?
　　[6]邵峰晶,于忠清.数据挖掘的原理与算法[M].北京：中国水利水电出版社,2003.?
　　[7]HAN Jiawei,KAMBER M.Data mining concepts and techniques[M].范明,孟小峰,等译.北京： 机械出版社.?
　　[8]马庆国.管理统计[M].北京：科学出版社,2002:3－120.?
　　[9]WISHART D.K－means clustering with outlier detection:the 25th Annual Conference of the German Classification Society[C].Munich:?University of Munich,2001:14－16.?
　　[10]左子叶,朱扬勇.基于数据挖掘聚类技术的信用评分评级[J].计算机应用与软件,2004,21(4):1－3，101.?
　　[11]何彬彬,方涛，郭达志.基于不确定性的空间聚类[J].计算机科学,2004,31(11):196－198.?
　　[12]钱锋,徐麟文.知识发现中的聚类分析及其应用[J].杭州师范学院学报:科学版,2001(2):34－37.?
　　[13]许向东,张全寿.数据仓库与数据挖掘的应用[J].计算机系统应用,1998(4):20－24.