学术论文网:本站代理期刊可作为职称及学位评审依据 ;并代写(职称、本科、硕士、博士)论文,代写代发论文一条龙服务;保证原创,保密服务
中国学术期刊征稿平台
EI会议发表,稳妥操作,速度快,审稿专家直接推荐,包发表。每月有少量稿件可推荐!有意向联系客服咨询。
论文代写:十年专业服务品质,全部由期刊编辑、硕士、博士撰写;保证原创、版权归您;保证通过、否则全额退款。
论文发表:与百家优秀期刊合作,代理审核组稿,论文发表涵盖所有专业领域,全部正刊,保证出刊,否则全额退款。
联系我们:TEL:027-61277098 13277951105业务QQ :319935043代写代发论文咨询、论文定制、文献翻译、开题报告、课题申请 319935042代写代发论文咨询 Email:lw001web@qq.com
公告:因业务发展需要,诚招优秀写手合作,要求硕士以上学历,不限专业,另诚征优秀期刊代理合作,具体详谈。QQ:319935043
热门关键字: 代写毕业论文  代写论文  论文发表  代发论文

k 均值算法初始聚类中心选取方法的研究

Tag:
k 均值算法初始聚类中心选取方法的研究 郑丹* 作者简介:郑丹,(1980-),男,实验师,数据挖掘. E-mail: zhd@xznu.edu.cn (中国矿业大学计算机学院,江苏 徐州 221116) 5 摘要:对k 均值算法进行研究,针对k 均值算法在初始聚类中心选取及聚类结果受噪声影响 大的缺点,提出改进的k 均值初始聚类算法。改进之处是寻找初始聚类中心的方法,把距离 与密度结合,密度指标提高聚类的准确率;存储对象间的距离,避免重复计算距离,提高算 法效率。 关键词:数据挖掘;聚类分析;K-Means;距离;密度 10 中图分类号:TP311 Searching Method of K-Means Initial Clustering Centers Zheng Dan (School of Computer Science and Technology,China University of Mining and Technology, 15 JiangSu XuZhou 221116) Abstract: Researches k-means algorithm and improves its shortcomings. A new method is proposed to optimize searching of initial clustering centers. The method is to combine distances of any two objects and area density. Saving distance values is to avoid calculating distance values between objects repeatedly. Using density is to increase accuracy rate of clustering. 20 Keywords:data mining; clustering analysis; K-Means; distance; density 0 引言 基于划分与基于密度是聚类中的两种重要聚类分析方法[1]。“划分”方法简单、高效, 在处理大数据集的任务时具有较强的可伸缩性。最著名的基于划分的算法是k 均值算法。 25 k 均值算法是早期的数据挖掘算法,它是基于划分方法的聚类。由McQueen 在1967 年 提出。k 均值算法过程相对简单,执行速度快,已经应用在很多领域中。k 均值算法需要输 入参数k,k 是希望得到的聚类个数,表示把数据集划分成k 个簇或类。由于算法简单,所 以执行效率高。但是,初始聚类中心的选取是任意的,由使用者决定,往往使聚类结果陷入 局部最优。 30 前人对k 均值算法进行过改进,如基于遗传算法的改进k 均值算法,实现遗传算法的整 体与k 均值算法局部两方面的结合[2];基于数据集的对象抽样分布的k 均值初始聚类中心确 定算法等[3]。 1 k 均值算法的步骤 k 均值算法的主要步骤如下: 35 (1)在数据集中随机选取k 个对象代表,作为k 个聚类的中心; (2)计算每个剩余对象到各个聚类中心的欧几里得距离,将它们分到最近的聚类中; (3)重新计算每个聚类的平均值,更新簇的聚类中心; (4)重复步骤(2)到(3),直到聚类均值不再改变或准则函数收敛。 准则函数一般为平方差函数,即 Σ Σ − = ∈ = k i pC e i J p Mi 1 2 40 Je 是数据集中所有对象的平方误差的总和,Je 越大则对象与聚类中心的距离越大,簇 内的相似性越低;反之Je 越小说明簇内的相似性越高;p 是簇内任意一个对象;Mi 是聚类 Ci 的聚类中心。k 均值算法要求已知聚类数k,并且人为指定聚类初始中心。这样节省时间, 对于数据集较大时应当优先选择k 均值算法。 45 但是,k 均值算法存在缺点,即初始聚类中心是人为指定的,具有随意性。这种随意性 或不确定性导致聚类结果趋向局部最优解;噪声影响执行效率,甚至得不到有效的聚类结果。 k 均值算法聚类分析的步骤如下: (1)预处理数据集。 (2)确定聚类数目k。 50 (3)指定初始聚类中心。 (3)求解聚类结果。 (4)描述、解释聚类结果。 2 对k 均值算法的改进与检验 2.1 对k 均值算法改进 55 k 均值算法的初始聚类中心随机指定,随机的初始化聚类中心不能完整体现数据对象在 数据集中的分布情况。前人曾研究用相距最远的k 个对象作为初始聚类中心[4]。但是,相距 最远的k 个对象虽然具有一定的代表性,但是这样的k 个对象很可能包含噪声点。如果初始 聚类中心取到噪声点,那么一般不能获得有意义的聚类结果。所以在选取初始聚类中心时, 不仅要考虑距离最远的k 个对象,还要避免选择到噪声点。 60 数据集内部的对象分布往往不均匀,即高低密度区域共存的情况十分常见。数据对象的 密度完整反映了数据的分布情况。通常在一个数据集里,高密度区域的数据对象被低密度区 域的对象所分割,一般情况下,处于低密度区域的数据对象通常被认为是噪声点[5]。为了避 免噪声数据的干扰,取相距最远的k 个处于高密度区域的点作为初始聚类中心。 如果初始聚类中心都处于数据集的高密度区域,那么就能完整代表数据的分布情况,从 65 而消除传统的k 均值算法对初始聚类中心的依赖,提高k 均值聚类的准确性。 要选取高密度区域的对象作为初始聚类中心,必须计算对象之间的距离。距离被看做对 象相似性度量的标准。多维属性对象间的距离计算需要消耗大量时间,特别对于高维属性的 对象而言,距离的计算势必消耗更多的时间。 此外,选取高密度区域的初始聚类中心进行k 均值聚类时,仍然需要计算对象之间的距 70 离。这里的距离和选取高密度区域的初始聚类中心时距离是相同的。多次重复计算将极大增 加运行时间,降低聚类效率。 因此,本文提出一种改进的k 均值算法——基于距离和密度选取初始聚类中心的k 均值 算法,简称DSk-means(Distance and denSity based k-means)算法。 DSk-means 算法的主要工作是对初始聚类中心选取方法进行改进与优化。设置二维数组 75 存储对象之间的距离,一方面为初始聚类中心选取提供密度大小的衡量标准,另一方面,为 下一步的k 均值聚类直接提供距离值。本文的实验部分对DSk-means 算法、传统的k 均值 算法、Sk-means(不存储对象距离的DSk-menas)算法用C#代码实现并进行比对。实验结 果表明,改进后的DSk-means 算法在执行效率、聚类结果的准确率上具有显著优势。 2.2 相关参数的定义 80 定义1:ε - 邻域。对于给定的对象p,以p 为中心、ε 为半径的区域称为对象p 的ε - 邻 域。 定义2:核心对象。对于给定的正整数MinPts,如果对象p 的ε-邻域内至少包含MinPts 个对象,则称对象p 为核心对象。 2.3 算法的一般描述 85 输入:聚类数目k、对象的属性数attr、邻域半径ε 、邻域包含的最少对象数目MinPts; 输出:满足聚类生成条件或准则函数收敛要求的k 个聚类。 算法步骤: (1)计算所有对象间的距离d(i, j) 并存入二维数组d[i,j]。 (2)逐一计算每个对象的ε -邻域内的对象个数,如果对象个数不少于MinPts,则将该 对象加入到高密度区域D' 90 中。 (3)从高密度数据集D' 中找出ε -邻域内对象个数最多的数据对象c1,即该对象具有 最高密度,将其加入初始聚类中心集合Cluster。 (4)对 ‘ D 中的所有对象,查询它们到c1 的距离,找出距离c1 最远的数据对象c2,接 着将c2 加入初始聚类中心集合Cluster,并把该对象从集合D' 中删除。 (5)从集合D' 95 中找出与c1、c2 的距离之和最大,即距离c1 和c2 对象最远的对象c3, 接着将c3 加入初始聚类中心集合Cluster,并把该对象从集合D' 中删除。 (6)继续从集合D' 中找出与初始聚类中心集合cluster 中所有的对象的距离之和最大的 对象,即距离初始聚类中心集合最远的对象,直至找到第k 个初始聚类中心。 7)以得到的k 个初始聚类中心为出发点,再使用k 均值算法进行聚类,采用聚类中心 100 不变作为聚类结束条件,得到最终聚类结果。 2.4 算法的流程图 DSk-means 算法的流程图如图1 所示。 105 图1 改进k 均值算法流程图 Fig. 1 Flowchart of Improved k-means Algorithm 对DSk-means 算法的实验与分析 为验证改进的的效果,用实验的方法进行实际测试。实验环境为Intel 2.2GHz 双核处理 110 器、4G 物理内存,程序代码采用C#语言编写。 实验测试的数据集来源于UCI Machine Learning Repository[6]。1987 年,UC Irvine 的 David Aha 等人创建UCI Machine Learning Repository 数据库,专门为研究机器学习算法提供 数据集。因为UCI 数据集包含明确的类别标识,所以能够将聚类结果进行逐个对象地精确 比较。本文选取Glass Identification、Iris 和Blood Transfusion Service Center 3 个数据集。3 开始 计算并保存对象两两之间的距离 计算对象ε-邻域内的对象数Pts Y Pts ≥MinPts N 所有对象计算完毕 对象i 存入D’ N Y 比较并找出D’中Pts 最大的对象C1 对象C1 加入集合Cluster 从D’中删除C1 Cluster 元素数达到k N 在D’中查找与Cluster 的所有元素距离最大对象Ci 对象Ci加入Cluster Cluster 内k 个元素作为初始聚类中心进行k 均值聚类 结束 115 个数据集参数如表1 所示。 表1 数据集参数 Tab. 1 Dataset Parameters 数据集 对象总数 属性数 Glass Identification 214 10 Iris 150 4 Blood Transfusion Service Center 748 4 120 实验的关键程序请见本文的附录部分。 实验过程如下: (1)对3 个数据集分别进行传统的k 均值聚类。 1)Glass Identification 的k 均值聚类过程如下: ①选择Glass Identification 数据集。 125 ②数据预处理。因为Glass Identification 对象的第一个属性ID 代表记录号,对聚类没有 实际意义,所以在数据清理时首先去掉ID 属性。 ③对剩下的9 个属性进行数据变换。 ④对整个数据集实施k 均值聚类。程序从glass.txt 文件中读取数据集,并以数组的存储 结构保存数据集;定义时间变量保存聚类过程的起始时间与终止时间,用以计算聚类消耗的 130 时间;定义计数器变量记录聚类的迭代次数;运行结果输出到文件中。 ⑤统计并分析结果。聚类结果result.txt 的内容包含聚类后的数据集、行标、迭代次数与 消耗时间。本实验结果为迭代9 次,聚类共消耗10 毫秒。类3 陷入局部最优,聚类的正确 率为52.34%。 同样的聚类过程对Iris 和Blood Transfusion Service Center 数据集进行聚类。 135 2)对数据集Iris 实施传统的k 均值聚类结果。 Iris 数据集上的运行结果为迭代次数11,聚类共消耗2 毫秒,准确率为83.43%。 3)对数据集Blood Transfusion Service Center 实施传统的k 均值聚类结果。 Blood Transfusion Service Center 数据集上的运行结果为迭代6 次,聚类共消耗64 毫秒, 准确率为76.74。 140 (2)对3 个数据集分别进行DSk-means 聚类。 根据实验经验,DSk-means 算法对数据集Glass Identifications 和Iris 指定邻域半径ε为 1,最小数目MinPts 为50;对于blood 数据集,指定ε为40,MinPts 为300。 1)Glass Identification 的DSk-means 聚类结果。 Glass Identification 的DSk-means 数据集上的运行结果为迭代次数13,聚类共消耗19 145 毫秒,准确率为53.32%。 2)Iris 的DSk-means 聚类结果。 Glass Identification 的DSk-means 数据集上的运行结果为迭代次数4,聚类共消耗6 毫秒, 准确率为89.12%。 3)Blood Transfusion Service Center 的DSk-means 聚类结果。 150 Glass Identification 的DSk-means 数据集上的运行结果为迭代次数6,聚类共消耗101 毫秒,准确率为84.60%。 由于Sk-means 算法和DSk-means 算法得到的初始聚类中心是相同的,所以二者都只进 行一次实验,得到的最高、最低和平均聚类准确率以及最大、最小和平均准则函数Je 也是 相同的。传统的K 均值算法进行10 次实验,Sk-means 算法和DSk-means 算法进行1 次实 155 验,实验结果如表2、3、4 所示。 表2 3 种算法聚类准确率比较 Tab. 2 Compare of Clustering Accuracy of the 3 Algorithms 准确率% 算法 数据集 最高 最低 平均 Glass Identification 71.33 52.34 68.99 K 均值 Blood TIrraisn sfusion 88.55 83.43 86.03 Service Center 78.55 74.15 76.74 Glass Identification 53.32 53.32 53.32 Sk-means Iris 89.12 89.12 89.12 算法 Blood Transfusion Service Center 84.60 84.60 84.60 Glass Identification 53.32 53.32 53.32 DSk-means Iris 89.12 89.12 89.12 算法 Blood Transfusion Service Center 84.60 84.60 84.60 160 表3 3 种算法迭代次数比较 Tab. 3 Compare of Iterative Times of the 3 Algorithms 迭代次数 算法 数据集 最高 最低 平均 Glass Identification 15 7 9 K 均值 Blood TIrraisn sfusion 15 11 12 Service Center 12 5 6 Glass Identification 13 13 13 Sk-means Iris 4 4 4 算法 Blood Transfusion Service Center 6 6 6 Glass Identification 13 13 13 DSk-means Iris 4 4 4 算法 Blood Transfusion Service Center 6 6 6 表4 3 种算法执行时间比较 Tab. 4 Compare of Execution Time of the 3 Algorithms 时间(毫秒) 算法 数据集 最高 最低 平均 Glass Identification 17 8 10 K 均值 Blood TIrraisn sfusion 5 2 3 Service Center 130 53 64 Glass Identification 25 25 25 Sk-means Iris 8 8 8 算法 Blood Transfusion Service Center 121 121 121 Glass Identification 19 19 19 DSk-means Iris 6 6 6 算法 Blood Transfusion Service Center 101 101 101 165 从表2 可以看出,DSk-means 算法对Iris 和Blood Transfusion Service Center 数据集的聚 类精度达到了传统k均值算法的最高聚类精度,而且迭代次数接近传统k均值算法的最小值, 这说明对Iris 和Blood Transfusion Service Center 数据集的聚类更准确。对Glass Identification 数据集的DSk-means 聚类准确率低于传统k 均值算法的平均聚类准确率,但是迭代次数没 170 有超过传统算法的最大值,这说明改进后的算法对于Glass Identification 数据集也有一定的 聚类效果。但是,在极端情况下,如密度大小差别巨大的数据集,显然能够较好地进行聚类。 从表4 可以看出,DSk-means 算法比传统的k 均值算法需要更多时间,分别是传统算法 执行时间的1.9 倍、2 倍、1.6 倍。但是,Sk-means 算法执行时间分别是DSk-means 算法的 1.3 倍、1.3 倍、1.2 倍。多出的时间用在对象间距离的重复计算上。对于较小数据量的数据 175 集,延长的执行时间是可以接受的。本文很好得保存了对象间的距离,在初始聚类中心选择 和k 均值聚类过程中直接查询数组元素值,有效减少了重复计算对象间距离的时间。特别是 在数据集包含海量数据的情况下,DSk-means 算法时间将比Sk-means 算法时间显著减少。 因此,本DSk-means 能够有效提高基于密度的k 均值算法的执行效率。 3 结论 180 本文对k 均值算法进行改进。存储对象的距离,避免了重复计算,节约系统执行时间; 反映对象分布的密度指标应用到查找初始聚类中心的过程中,使初始聚类中心具有代表性, 提高了聚类的准确性。但是,本文的算法需要靠经验指定参数ε和MinPts。今后的应当对 这两个参数的确定方法以对聚类结果的影响进行深入研究。