第 24 卷 第 5 期 2007 年 5 月 计 算 机 应 用 研 究 Application Research of Computers Vol. 24, No. 5 May 2007 基 于 聚 类 分 析 的 K-m eans 算 法 研 究 及 应 用 * ( 1. 山东 师范 大学 信 息科 学与 工程学 院, 山东 济南 250014; 2. 山东 师范 大学 管 理学 院, 山 东 济南 250014) 张建萍 1, 刘希玉 2 摘 要: 通 过对 聚类 分析 及其 算法 的论 述, 从多 个方 面对 这 些算 法 性 能 进 行 比 较, 同 时 以 儿 童 生长 发 育 时 期 的 数据 为例 通过 聚类分 析的 软件 和改 进的 K-means 算法 来进 一步 阐述 聚类 分析在 数据 挖掘 中的 实践 应用 。 关键 词: 数 据挖 掘; 聚类 分析 ; 数据 库; 聚类 算法 中图 分类 号: TP311 文 章编 号: 1001- 3695( 2007) 05- 0166- 03 文 献标 志码: A Application in Cluster’s Analysis Is Analyzed in Children Development Period ( 1. College of Information Science & Engineering, Shandong Normal University, Jinan Shandong 250014, China; 2. College of Management, Shandong Normal University, Jinan Shandong 250014, China) ZHANG Jian-ping1, LIU Xi-yu2 Abstract: This paper passed cluster’s analysis and its algorithm correctly, compared these algorithm performances from a lot of respects, and explained that cluster analysis excavates the practice application of in datum further to come through software and improved K-means algorithm, cluster of analysis at the same time practise application. Key words: data mining; cluster analysis; database; cluster algorithm 随着计算机硬件和软件技术的飞速发展, 尤其是数据库技 术的普及, 人们面临着日 益扩张 的数据 海洋, 原来的 数据分 析 工具已无法有效地为决策者提供决策支持所需要的相关知识, 从而形成一种 独特 的现象 “丰富 的数 据, 贫乏 的知 识”。数 据 挖掘 [ 1] 又 称 为 数 据 库 中 知 识 发 现 ( Knowledge Discovery from Database, KDD) , 它是一 个从 大 量数 据中 抽 取 挖掘 出 未 知的、 有价值的模式或规律等知 识的复 杂过程。目 的是在 大量的 数 据中发现人们感兴趣的知识。 常用的数据挖掘技术包 括关联 分析、异类分 析、分 类与 预 测、聚类分析以及演化分析等。由于数据库中收集了大量的数 据, 聚类分析已经成为数据挖掘领域的重要技术之一。 1 问题的提出 随着社会的发展和人们生活水平 的提高, 优育 观念 [ 2, 3] 逐 渐渗透到每个家 庭, 小 儿的 生长 发 育越 来越 引 起家 长们 的 重 视。中国每隔几年都要进行全国儿童营养调查, 然而用手工计 算的方法在大量的数据中分析出其中的特点和规律, 显然是不 现实的, 也是不可行 的。 为了有 效地解 决这个 问题, 数据挖 掘 技术———聚类分析发挥了巨大的作用。 在数据挖掘领域, 聚类算法经常遇到一些问题如聚类初始 点的选择 [ 4] 、模糊因子的确定 [ 5] 等, 大部 分均已 得到解 决。现 在的研究工作主要集中在为大 型的数 据库有 效聚类 分析寻 找 适当的方法、聚类算法对复杂分布数据和类别性数据聚类的有 效性以及高维数据聚类技 术等方 面。本文通 过对聚 类分析 算 法的分析并重点从聚类 分析的 软件工 具和 改进 的 K-means 算 法两个方面来论证聚类分析在儿童生长发育时期中的应用。 2 聚类算法分析 聚类 [ 6] 分 析是 直接比 较各 事物 之间 的性 质, 将性 质相 近 的归为一类, 将性质差别较大的归入不同的类。在医学实践中 也经常需要做分类工作, 如 根据病 人的一 系列症 状、体征和 生 化检查的结果, 判断病人所 患疾病 的类型; 或 对一系 列检查 方 法及其结果, 将之划分成 某几种 方法适 合用于 甲类病 的检查, 另几种方法适合用于乙类病的检查, 等等。聚类分析被广泛研 究了许多年。基于聚类分析的 工具已 经被加 入到许 多统计 分 析软件包或系统中, 如 S-Plus、SPSS, 以及 SAS。 大体上, 聚类算法 [ 7] 可以划分为如下几类: ( 1) 划分方法。给定一个包含 n 个 对象或 数据行, 划分 方 法将数据集划分为 k 个子集( 划分) 。其中每 个子集 均代表 一 个聚类( k≤n ) 。代表算法为 K-means 算法、K-medoids 算法 和 CLARANS 算法。 ( 2) 层次方法。该方法就是通过分解所 给定的数据对象集 来创建一个层次。它 存在的缺陷 就是在进行 ( 组 ) 分解或 合并 之后无法回溯。将循环再定位与层次方法结合起来使用常常是 有效的, 如 BIRCH 和 CURE, 就是基于这种组合方法设计的。 ( 3) 基于密度 的方法。只 要临近区域 的密度( 对象或 数据 点的数目) 超过某个阈值, 就继续聚类。DBSCAN 是一个有代表 性的基于密度的方法。它根据一个密度阈值来控制簇的增长。 ( 4) 基于网格的 方法。基 于网 格方 法将 对 象空 间划 分 为 有限数目的单元以形成网 格结构。其 主要优 点是它 的处理 速 度很快, 其处理时间独立于 数据对 象的数 目, 只与量 化空间 中 每一维的单元数目有 关。 STING 就是一 个典型 的基于 网格 的 收 稿日期 : 2006- 04- 12; 修 返日期 : 2006- 05- 15 基金 项目 : 国家 自然 科学 基金 资助 项目 ( 6037405 ) ; “泰山 学者 ”建设 工程 专项 经费 资 助项目 ; 山 东省 自然科 学基 金重大 项目( Z2004 G02) ; 山东省 中青 年科学 家奖 励基金 资助项 目( 03BS003) 作 者简介 : 张建萍 ( 1979- ) , 女, 山东 滨州人 , 硕士研 究生, 主 要研究 方向 为遗传 算法、数 据挖掘 ; 刘 希 玉( 1964 - ) , 男 , 山东 济 南人 , 教授 , 博导 , 主要研 究方向 为信 息管理 、管理信 息系统 ( MIS) . 

第 5 期 方法。 ( 5) 基于模型 的方法。该 方法 就是 为每 个 聚类 假设 一 个 模型, 然后再去发现符合相应模型的数据对象。它根据标准统 计方法并考虑到噪声或异常 数据, 可以 自动确 定聚类 个数; 因 而它可以产生很鲁棒的聚类方法。 数据挖掘在不同领域对聚类算法提出了各自特殊的要求, 表 1 可以给聚类算法的研究和应用提供参考 [ 7] 。 表 1 聚类 算法比 较 算 法 可 伸 缩 性 发 现 聚 类 的 形 状 噪 声 的 敏 感 性 数 据 输 入 顺 序 的 敏 感 性 高 维 性 效 率 CLAR ANS CURE BIR CH STING DBSCAN COBWEB FCM 好 较 差 较 差 好 较 好 较 好 好 凸 形 或 球 形 不 敏 感 非 常 敏 感 一 般 较 低 任 意 形 状 不 敏 感 敏 感 凸 形 或 球 形 一 般 不 太 敏 感 任 意 形 状 不 敏 感 不 敏 感 任 意 形 状 不 敏 感 任 意 形 状 任 意 形 状 一 般 敏 感 敏 感 敏 感 不 敏 感 好 好 好 较 高 高 高 一 般 一 般 好 好 较 低 较 高 3 儿童生长发育的分析 聚类分析在数据挖掘中的应用主要有以下三个方面: ( 1) 聚类分析能 作为 一个独 立的 工具 来获 得数 据的 分 布 情况, 观察每个簇的特点, 集中 对特定 的某些 簇作进 一步的 分 析。如: ①聚类分析软件 v1. 2。此软件主 要用于血型、蛋白 质 多态、品种聚类等方面的统计分析, 可自动进行杂合度、多态信 息含量、遗传距离以 及聚类 的计算, 并可 自动画 出聚类 图。② SPSS 统计软件。SPSS 软件 是一种 专业的 统计分 析软件, 用 于 数据的各种分析, 从 而最终 为企、事业的 科学决 策服务。其 中 采用聚类分析是理想的多变量统计技术, 主要有分层聚类法和 迭代聚类法。 本文通过一组儿童生长发育的数据运用 SPSS 工具进行分 析, 如表 2 所示。 表 2 儿 童生 长发育 时期 的数据 月 份 数 月 平 均 增 长 率 ( % ) 月 份 数 月 平 均 增 长 率 ( % ) 身 高 体 重 胸 围 坐 高 11. 03 50. 30 11. 81 11. 27 5 . 47 3 . 58 2 . 01 2 . 13 2 . 06 1 . 63 1 . 17 1 . 03 0 . 69 19. 30 9 . 85 4 . 17 5 . 65 1 . 74 2 . 04 1 . 60 2 . 34 1 . 33 5 . 20 3 . 14 1 . 47 1 . 04 0 . 17 1 . 04 0 . 89 0 . 53 0 . 48 7 . 18 2 . 11 1 . 58 2 . 11 1 . 57 1 . 46 0 . 76 0 . 89 0 . 58 1 2 3 4 6 8 10 12 15 18 身 高 0 . 77 0 . 59 0 . 65 0 . 51 0 . 73 0 . 53 0 . 36 0 . 52 0 . 34 体 重 1 . 41 1 . 25 1 . 19 0 . 93 1 . 13 0 . 82 0 . 52 1 . 03 0 . 49 胸 围 0 . 52 0 . 30 0 . 49 0 . 16 0 . 35 0 . 16 0 . 19 0 . 30 0 . 18 坐 高 0 . 42 0 . 14 0 . 38 0 . 25 0 . 55 0 . 34 0 . 21 0 . 55 0 . 16 24 30 36 42 48 54 60 66 72 运用 SPSS 工具调用 K-means Cluster 过程可完成 由用户指 定类别数的大样本资料的逐步聚类分析。逐步聚类分析就是先 把被聚对象进行初始分类, 然后逐步调整, 得到最终分类。 为研究儿童生长发 育的分期, 笔者对 1 253 名 1 月 ～7 岁 儿童进行了抽样调查, 分别 对儿童 的身高 ( cm) 、体 重( kg) 、胸 围( cm) 和坐高( cm) 进行了 测量。资料作如 下整理: 先把 1 月 ～7 岁划成 19 个月份 段, 分 月份算 出各指 标的平 均值, 将 第 1 月的各指标平均值与出生时的各指标平均值比较, 求出月平均 增长率( % ) , 然后第 2 月起的 各月 份指 标平 均 值均 与前 一 月 比较, 求出月平均增 长率 ( % ) ( 表 2) 。 将儿 童 生长 发育 时 期 分为四期, 所以聚类 的类 别数 为 4, 从而 确定 四个 儿童 生长 发 育期的起止区间。 张建 萍等 : 基 于聚 类分 析的 K-means 算法研 究及 应用 ·761· ①激活数据管理窗口, 定义变量名。虽然月份分组不做分 析变量, 但为了更直观地了解聚类结果, 也将之输入数据库。 ②进行统计分析, 在聚类方法上选择 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 不再发生变化。 在本算法中要用到以下几个定义: 定义 1 DSS[ 10] ( Distance Square Sum) 是指数 据库中所 有 p∈ Ci |p-mi |2。 其 中, p 对象的平方 误 差的 总和, 即 Ep = 是空间中的点, 表示 给定 的 数据 对 象; mi 是簇 ci 的 平均 值 ( p  k i = 1 

·861· 和 mi 都是多维的) 。 2 =  kδijk dijk 计 算 机 应 用 研 究 2007 年 定义 2 数 据 对 象 i 与 j 的 相 异 度 为 dij 2 /  2 是第 k 个值距离的平方, 对每个变 量根据 其 重要性赋予一个权重, 运用加权的欧几里得距离 [ 11] 可以计算: kδijk。其中, dijk dijk 2 = W1 |Xi1 - Xj1 |2 + W2 |Xi2 - X j2 |2 + … + Wp |Xip - Xjp |2 其中, i = ( Xi1, Xi2 , …, Xip) 、j = ( Xj1, Xj2 , …, Xjp) 是 两个 p 维 的 数据对象。δijk是值为 0 ～1 的权重, 它决定第 k 个值的重要性。 DSS 是判别 K-means 聚类 结果的 重要指 标。 通过 k, 试 图找 到 使 DSS 函数值最小的划分, 一般实际可 达到局 部最优, 即算 法 最终要使 DSS 最小化, 采 用这 种方 法是 试图 使 生成 的结 果 簇 尽可能紧凑和独立。基于 K-means 算法 同样 可得 到图 1 所 示 的结果。 ( 3) 聚类分析 也可以 进行 孤立 点的 分 析。 经常 存在 一 些 数据对象, 它们不符合数 据的一 般模型, 这些 数据对 象被称 为 孤立点。孤立点的 分析 有着广 泛 的应 用 [ 12, 13] , 如欺 诈检 测 即 探询不寻常的信用卡使用或 电信服 务; 此外, 它在市 场分析 中 可用于确定极低或极高收入的客户的消费行为、或者在医疗分 析中用于发现对多种治疗方式的不寻常的反应。 4 结束语 本文通过改进的 K-means 算法和聚类分析工具 SPSS 来对 儿童生长发育期进行分析。 在科技发展的今天, 随 着信息 化产业 的不断 发展, 大量 的 数据迫切需要强有力的数据分析工具的出现, 从而导致了数据 挖掘的蓬勃发展, 而聚类分析已经成为数据挖掘领域一个非常 活跃的研究课题。用户当然希望聚类的结果是可解释的、可理 解的和可应用的。如何选择聚 类方法 和正确 地使用 聚类算 法 也是很重要的, 而目 前 所使 用的 聚 类算 法均 存 在某 方面 的 缺 ( 上 接第 162 页) ⑤各种功能资源配置信 息。插件描 述文件 plu- gin. xml 集中描述了插 件的基 本信息 ( 如插件 的名 字、类 型、实 现类的类名、组合和依赖关系等) 。 二级代理 广告 一级代理 广告 浏览 浏览 订阅 通知 广告 发布 浏览 浏览 通知 订阅 浏览 客户端 1 客户端 2 图9ACT 蛳PS 发布订阅通信流程 客户端 3 客户端 4 5 结束语 ACT-PS 解决了可配置和可扩展发布订阅通信的一些 初步 问题, 并在实际数据交换 系统中 进行了 配置和 扩展实 现, 为 一 般的发布订阅中间件系统 的建立 提供了 参考。目前 可配置 发 布订阅系统的研究仍然是一个新的领域, 后续的工作是进一步 深入研究设计模型之间的语义 冲突和 发布订 阅系统 安全控 制 问题。 参考文献: [ 1] UGOLA G, NITTO E D, FUGGETTA A. The JEDI event-based infra- structure and its application to the development of the OPSS WFMS 陷, 也没有统一的标准, 因此如何 使聚类算法 成为像 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 dis- tance[ J] . Theoretical Computer Science, 1985, 38 ( 2- 3 ) : 293- [ 5] 306. 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 An- nual 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 . [ J] . IEEE Transaction on Software Engineering, 2001, 27( 9 ) : 827- 850 . [ 3] [ 2] EUGSTER P T, FELLER P, GUERRAOUI R. The many faces of pub- lish/ subscribe[ J] . ACM Computing Surveys, 2003, 35( 2) : 114-131. SOUZA C R B, BASAVESWARA S D, REDMILES D F. Using event notification servers to support application awareness: International Conference on Software Engineering and Applications[ C] . New York: IEEE press, 2002: 521- 526. [ 4] FITZPATRICK G, KAPLAN S, MANSFIELD T. Supporting public a- vailability and accessibility with elvin: experiences and reflections[ J] . Computer Supported Cooperative Work,2002, 11( 3) : 447-474. IBM Corporation. Gryphon: publish/ subscribe over public networks [ R] . Yorktown: IBM TJ Watson Research Center, 2001. [ 5 ] [ 6] CARZANIGA A, ROSENBLUM D S, WOLF A L. Design and evalua- tion of a wide-area event notification service[ J] . ACM Transactions on Computer Systems, 2001 , 19( 3 ) : 332- 383. [ 7] BARRETT D J, CLARKE L A, TARR P L, et al. A framework for e- vent-based software integration[ J] . ACM Transactions on Software Engineering and M ethodology, 1996, 5( 4) : 378 -421. [ 8] CARZANIGA A, ROSENBLUM D S, WOLF A L. Design and evalua- tion of a wide-area event notification service[ J] . ACM Transaction on Computer Systems, 2001, 19( 3) : 332 -383. [ 9] CARZANIGA A, ROSENBLUM D S, WOLF A L. Challenges for dis- tributed event services: scalability vs. expressiveness: proc. of EDD ’99 [ C] . New York: IEEE Press, 1999: 72- 77.