论文研究-基于k-means聚类算法的研究 .pdf

发布时间：2022-05-29 发布人：admin 分类：说明书资料大小：0.27M 资料格式：pdf 举报版权申诉

weixin_39840588-11560123-4744302543416035017.pdf-第1页.png

第1页 / 共7页

weixin_39840588-11560123-4744302543416035017.pdf-第2页.png

第2页 / 共7页

weixin_39840588-11560123-4744302543416035017.pdf-第3页.png

第3页 / 共7页

weixin_39840588-11560123-4744302543416035017.pdf-第4页.png

第4页 / 共7页

weixin_39840588-11560123-4744302543416035017.pdf-第5页.png

第5页 / 共7页

weixin_39840588-11560123-4744302543416035017.pdf-第6页.png

第6页 / 共7页

weixin_39840588-11560123-4744302543416035017.pdf-第7页.png

第7页 / 共7页

文本预览

2. Department of Software Harbin university of science and technology, Harbin 150080; 3. Department of Computer Science and Technology Harbin engineering university, Harbin 150080; Harbin 150001) 中国科技论文在线 http://www.paper.edu.cn 基于 k-means 聚类算法的研究# 黄韬1，刘胜辉2，谭艳娜3* （1. 哈尔滨理工大学计算机科学与技术学院，哈尔滨 150080； 2. 哈尔滨理工大学软件学院，哈尔滨 150080； 3. 哈尔滨工程大学计算机科学与技术学院，哈尔滨 150001）摘要：本文首先分析研究聚类分析方法，对多种聚类分析算法进行分析比较，讨论各自的优点和不足，同时针对原 k-means 算法的聚类结果受随机选取初始聚类中心的影响较大的缺点，提出一种改进算法。通过将对数据集的多次采样，选取最终较优的初始聚类中心，使得改进后的算法受初始聚类中心选择的影响度大大降低；同时，在选取初始聚类中心后，对初值进行数据标准化处理，使聚类效果进一步提高。通过 UCI 数据集上的数据对新算法 Hk-means 进行检测，结果显示 Hk-means 算法比原始的 k-means 算法在聚类效果上有显著的提高，并对相关领域有借鉴意义。关键词：数据挖掘；聚类算法；k-means 算法中图分类号：TP311 Research of clustering algorithm based on K-means (1. Department of Computer Science and Technology Harbin university of science and technology, Huang Tao1, Liu Shenghui2, Tan Yanna3 Abstract: Firstly, the paper analyzes and research the method of cluster analysis, analyzes and compares many kinds of algorithms of cluster analysis, discusses their respective strengths and weaknesses. At the same time, according to the weaknesses of the cluster result of original k-means algorithm is significant influence by selecting the initial cluster centers randomly, a modified algorithm is proposed. Through taking sample many times to data set, choose final superior cluster center, bring down the impact of initial cluster centers to improved algorithm greatly.Simultaneously, the initial data is standadized once the initial cluster center is selected, makes cluster effect improved furthermore. Detecting new algorithm Hk-means through the date of UCI data set, the result shows that Hk-means algorithm is more prominent improved than initial k-means algorithm in cluster effect, and it's useful for conference to relative field. Keywords:Data mining; clustering algorithm; k-means algorithm 0 引言数据挖掘(Data Mining)是一种数据分析处理技术，一般采取排出专家因素而通过自动的方式来发现数据仓库、大型数据库或其他大量信息中新的、不可预见的或隐藏的有价值的知识。挖掘的方法可以是数学的，也可以是非数学的；可以是归纳的，也可以是演绎的。发现的知识可以被用于信息管理、查询优化、决策支持和过程控制等,还可以用于数据自身的维护，因此数据挖掘技术是当前多个领域研究的热点。聚类分析是数据挖掘领域中的一个重要分支，它既可以作为数据挖掘中其他分析算法的一个预处理步骤，也可以作为一个单独的工具发现数据库中数据分布的一些深入的信息。聚类算法大致分为划分方法、层次方法、基于密度方法、基于网格方法和基于模型方法。一般情况下，为了使聚类效果更佳，经常将划分方法作为其他聚类方法的预处理步骤，所以划分基金项目：哈尔滨市后备带头人基金项目(2004AFXXJ039) 作者简介：黄韬，（1982-），男，硕士，企业智能计算. E-mail: huangtao_world@126.com - 1 -

中国科技论文在线 http://www.paper.edu.cn 方法的好坏直接的影响了结合聚类算法的效果。k-means 算法是划分方法中应用最广泛的一种方案，所以改进 k-means 算法，不但改善了划分方法本身的性能，还对结合的聚类方法提供了良好的接口。由于 k-means 算法选取初始聚类质心是随机的，导致聚类结果不稳定。为了提高聚类结果的稳定性，我们在传统的聚类方法上结合聚类融合思想，提出一种新的 Hk-means 聚类方法，进行多次采样，选取最终较优的初始聚类中心，使得改进后的算法受初始聚类中心选择的影响度大大降低，提高聚类结果的稳定性。 1 相关工作聚类算法是一种非监督机器学习算法，其实质就是对我们事先不了解的数据集进行分组，使得同一组内的数据尽可能相似而不同组内的数据尽可能不同，其目的是揭示数据分布的真实情况。聚类分析在统计数据分析、模式识别、图像处理、生物学以及市场营销等领域也有着广泛的应用前景。目前的聚类算法大致上主要被分为五类[1]：划分方法、层次方法、基于密度方法、基于网格方法和基于模型方法。 1.1 划分聚类算法划分聚类算法过程[2]：给定一个 n 个对象或元组的数据库,一个划分方法构建数据的 k 个划分,每个划分表示一个聚簇, 并且 k < n 。也就是说, 它将数据划分为 k 个组,同时满足如下的要求: (І) 每个组至少包含一个对象; (П) 每一个对象必须属于且只属于一个组。其思想是给定一个 n 个对象的数据库，通过迭代重定位策略优化特定的目标函数，尝试确定数据集的 k 个划分，每个划分表示一个聚簇（k<= n）。要求簇间的对象尽可能相近或相关，不同的簇间的对象尽可能不同。划分聚类算法实质上通过迭代重定位策略优化特定的目标函数，尝试确定数据集的一个划分[3]。它具有挖掘算法简单、速度快等优点，适用于中小规模的数据集中发现球状簇，但不能发现形状任意和大小差别很大的类簇、只能保证收敛到局部最优最优，聚类结果受初始聚类质心的影响，且对噪音点敏感。典型的代表算法 k-means 算法。 1.2 层次聚类算法层次方法对给定的数据集合进行层次的分级，称为树聚类算法。它使用数据的联接规则，透过一种层次架构方式，反复将数据进行分裂或聚合，以形成一个层次序列的聚类问题解。根据分解形成的过程，层次聚类可以分为凝聚的和分裂。凝聚的方法,也称为自底向上方法, 首先将每个对象作为单独的一个组，然后相继地合并相近的对象、组，直到所有的组合合并为一个，或者达到一个中止条件。分裂的方法，也称为自顶向下的方法,首先将所有的对象置于一个簇中。在迭代的每一步中，一个簇被分裂为更小的簇，直到最终每个对象在单独的一个簇中，或者达到一个终止条件。一种纯粹的层次聚类方法的缺点在于一旦合并或是分裂执行，就不能修正，也就是说，如果某个合并或是分裂效果在后来证明是不好的选择，该方法无法退回或是更正。层次聚合算法的计算复杂性为 O(n2)，适合于小型数据集的分类。 1.3 基于密度的聚类算法基于密度的聚类方法是将数据对象之间的距离和某一给定范围内数据对象个数这两个参数结合起来，得到“密度”的概念，然后根据密度的稠密程度判定数据对象的聚集情况。即将簇看作是数据空间中被低密度区域分割开的稠密数据区域。它能从含有噪声的空间数据库 - 2 -

中国科技论文在线 http://www.paper.edu.cn 中发现任意形状的聚类，但需要直接面对整个样本集进行操作，测试每个对象是否是核心对象，并对每个核心对象搜索其直接密度可达的对象。而由于密度连通关系的传递性[4]，往往使得绝大多数的样本点聚集到非常少的几个类簇中(通常是一类)。在没有空间索引辅助下，算法复杂度为 O（n2）。 1.4 基于网格的聚类算法基于网格的聚类算法使用一种多分辨率的网格数据结构，把对象空间量化为有限数目的单元，形成了一个网格结构。这种方法的主要优点是处理速度很快。但在构建父亲单元的时候往往没有考虑子女单元及其相邻单元的之间的关系，降低了聚类结果的质量和精确性。 1.5 基于模型的聚类算法基于模型的方法为每个簇假定了一个模型，寻找数据对象和给定模型的最佳拟合。一个基于模型的算法可能通过构建反映数据对象空间分布的密度函数来定位聚类，或基于标准的统计数字自动决定聚类的数目，而产生健壮的聚类方法。典型代表有 EM 算法、概念聚类、神经网络。EM 算法比较易于实现并且算法简单，但是不能达到全局最优；概念聚类在机器学习中有着广泛的应用，但是对于大型数据集聚类没有良好的伸缩性。 2 Hk-means 聚类算法 k-means 算法是划分聚类算法的典型代表之一，它具有算法简单，速度快等优点，经常作为其他算法的预处理步骤，所以它的精度直接或间接的影响着聚类结果的质量。由于原始的 k-means 算法对初始质心的选取敏感，导致结果质量不稳定。下文将针对这个问题，提出解决办法。 2.1 k-means 算法 k-means 算法是划分聚类算法的典型代表，实质上该算法基于簇中对象的平均值。为了达到全局最优，基于划分的聚类会要求穷举所有可能的划分。算法的处理过程如下：算法的输入：簇的数目 k 和数据库中的对象。算法的输出：使得平方误差准则最小的 k 个簇。方法如下：（1）从整个样本 n 中，任意选择 k 个对象作为初始的簇的中心 mi ( i=1,2,…k )；（2）利用公式 1，计算数据集中的每个 p 到 k 个簇中心的距离 d ( p , mi ) （3）找到每个对象 p 的最小的 d ( p , mi )，将 p 归入到与 mi 相同的簇中。（4）遍历完所有对象之后，利用公式 2 重新计算 mi 的值，作为新的簇中心。（5）重新将整个数据集中的对象赋给最类似的簇。这个过程反复进行直至平方误差准则最小。 d i j ( , ) ( = 2 ) ... + + ( x in − x 2 ) jn x i 1 − x 2 ) + ( x i 2 j 1 − x j 2 公式 1：其中 i =（xi1, xi2,…, xin）和 j=（ji1, ji2,…,jin）是两个 n 维数据对象。公式 2: m k x i N ∑ i 1 == N 其中的 mk 代表第 k 个簇的簇中心，N 代表第 k 个簇中数据对象的个数。 - 3 -

中国科技论文在线 http://www.paper.edu.cn 平方误差准则试图使聚类结果尽可能地独立和紧凑，即簇内对象的相似度尽可能的高。定义如下： k E = ∑ ∑ i 1 = p C ∈ i | p m i − 2 | 其中 E 表示所有对象的平方误差的总和，p 代表空间中的对象，mi 代表簇 Ci 的平均值。 2.2 改进的 k-means 算法算法思想：为了降低初值对聚类结果的影响，提高 k-means 聚类结果的稳定性，本文将对样本集进行 h 次随机采样，再对各采样的样本集进行以 k’(k’≥ k)个质心的 k-means 运算，即得到 h 组在随机样本上的聚类结果，每组聚类结果包括 k’个类簇中心，共 h* k’个簇。文献[5]给出，如果采样过程是以非常随机的方式进行的，我们认为这些选取出来的样本足以代表整个样本集。所以通过分析采样样本集的数据分布情况就可以找到整个样本集全局较优的 k 个质心，从而使得聚类结果的稳定性提高。其中参数 h 为采样次数，实验表明 h=3~10 通常已经足够。参数 k’为各采样的样本集上质心数目，k’>>k。原始的 k-means 算法，在 k 的选取上可以被认为是随机爬山算法，对于具有大量局部极高点和 k 个全局最高点的数据集，k-means 算法很可能陷入局部极高点。然而类别数目 k 的增大类似于开辟更多的爬山路径，如果 k’>>k 个路径，则到达全局最高点的可能性自然会增大。但同时随着 k’的增大，计算的代价也会增大。在文献[6]中研究了 k 近邻分类算法中参数 k 的设置，给出一个法则 k= n3/8。文献[7]推荐 k’值的选取满足如下约束：k’= min(a[n／|umin| ] , n5/8)，其中，umin 是需要关注的最小类簇，a 值一般小于等于 10。需要说明的是，在满足上述约束条件时，k’的取值对于聚类结果不敏感。处理流程如图 1 所示。图 1 输出 h* k’个簇流程图然后再对这 h×k’个聚类中心采取以下方法：先找到密度最大的质心，将其放入集合 S - 4 -

中国科技论文在线 http://www.paper.edu.cn 中，再计算其他质心与 S 集合中所有对象距离之和最大的质心，也将其放入到 S 中，直到选出 k 个聚类中心为止即集合 S 中有 k 个元素。再以这 k 个质心作为 k-means 原始中心，进行 k-means 运算，处理流程如图 2 所示。图 2 输出较优 k 个初始质心流程图 2.3 算法的复杂度分析 Hk-means 算法中，h 次预聚类时间复杂度为 O( h tk’dnsum )，其中, nsum 为随机样本的大小，t 为迭代次数，d 为特征属性数，通常 k’，t << nsum。再计算 h k’ 的密度，找到最大的簇，及最优的 k 个质心，时间复杂度为 O( (h k’ )2) ，则 Hk-means 的时间负复杂度为 O( t(hk’)2dn ),其中 n 为数据集的大小。大型数据集聚类时，Hk-means 算法比层次聚类算法快得多。 3 Hk-means 算法的应用 3.1 Hk-means 聚类算法的流程 Hk-means 算法的描述如下：输入：数据集 D、数据分类数目 k，采样次数 h; 输出：k 个簇。方法：（1） For h=1 对数据集 D 进行随机的采样，得到采样数据集 D’；（2）利用 FindCenter(D’，k’)，获取 k’个初始聚类中心{C1,C2,…,C3}; - 5 -

中国科技论文在线 http://www.paper.edu.cn （3）将 k’个样本点值分别赋给初始聚类中心 mi,1≤i≤k’; （4）利用公式 1，计算数据集 D’中的所有点 Pj( j =1,2,…,nsum),到 k’个簇中心的距离 d ( p , mi )；（5）找到对象 p 的最小的 d ( p , mi )，将 p 归入到与 mi 相同的簇中；（6）遍历完数据集 D’中的所有对象之后，利用公式 2 重新计算 mi 的值，作为新的簇中心；（7）重新将整个数据集中的对象赋给最类似的簇。这个过程反复进行直至平方误差准则最小，将 k’个簇进行标记存储；（8）再一次重新采样，反复执行步骤 2-7 的过程。直到 h 与用户输入的参数相符。（9）利用 FindDesity( h Ck)找到 k’簇中密度最大的簇 Ci，将其放入集合 S 中，作为用户定义的最初始 k 个簇类中心的第一个成员；（10）利用 DistanceMean(S),得到集合 S 中的各簇中心的均值mi，再利用 Distance(mi,mj), 找到不在集合 S 中其他簇类中心到 mi 的最大值，将其归入集合 S 中；（11）反复计算 9-10，直到 S 中的元素个数为 k; （12）将集合 S 中的 k 个质心作为聚类的初始质心，对整个数据集进行步骤 4-7；（13）输出满足均方误差函数值最小的 k 个簇。 3.2 算法在审计中的应用本节通过实验对 Hk-means 算法的有效性、及聚类质量进行分析。测试数据集，选取某省某市的单位实缴信息表，费款属期在 2007 年 1 月至 2007 年 6 月，总计 6 个月的数据为实验数据，数据条数共计 33096 条，对非数值属性值做了预处理，TestDB 为合成实验数据集。算法采用 JAVA 编写，在 Pentium(R)4．3.00GHz，1GB 内存，160GB 硬盘，JBulider9.0 环境下运行。数据挖掘算法几乎都包含或多或少的参数，这些预先给定的参数值在很大程度上决定了数据挖掘的结果。如果参数值不符合数据的分布特征，就很难获得好的聚类结果。而在实际应用中，合适的参数值的确不好确定，一般采用专家知识或进行多次试验的方法，来取得一个参数的最佳近似值。当 k 分别取 [4, 8，15，20，25]时，实验结果如下：表 1 K 值取不同值的结果 Hk-means k-means 93% 94% 99% 95% 92% 81% 86% 99% 81% 83% 效果算法准确率 K 取值 4 8 15 20 25 由表 1 可见 Hk-means 与 k-means 算法在 k 值等于 15 的情况下，可准确识别出绝大部分数据的类别。在其他 k 值情况下会出现一定差别，通过跟踪差别数据对象，发现造成差别主要原因是：k-means 算法随意的选择初始的聚类中心，使得聚类效果时好时坏，而 Hk-means 算法对初始质心的选择进行了分析、计算，使得一般下聚类效果都好于原始的聚类算法。 - 6 -

中国科技论文在线 4 结论 http://www.paper.edu.cn 本文通过将将聚类融合思想与 k-means 算法有机的结合，提出一种 Hk-means 算法，对数据集进行多次采样，选取最终较优的初始聚类中心，使得改进后的算法受初始聚类中心选择的影响度大大降低；同时，在选取初始聚类中心后，对初值进行数据标准化处理，使聚类效果进一步提高。理论分析和实验结果表明，算法是有效可行的。下一步，将对减小参数点的选取对聚类质量的影响以及算法在高维空间数据集的应用做进一步研究。 [参考文献] (References) [1] 孙吉贵，刘杰. 聚类算法研究[J]. 软件学报，2008，19(1)： 48～61. [2] Jiawei han. Data Mining Concepts and Techniques[M]. 机械工业出版社，2006. [3] 雷小峰，谢昆青. 一种基于 k-means 局部最优性的高效聚类算法[J]. 软件学报，2008，19(7)：1683～1692. [4] 周水庚，周傲英. 一种基于密度的快速聚类算法[J]. 计算机研究与发展，2000，37(11)：1287～1292. [5] 毕华梁，洪力，王珏. 重采样方法与机器学习[J]. 计算机学报，2009，32(5)：862～876. [6] Hand DJ, Vinciotti V． Choosing k for two-class nearest neighbor classifiers with unbalance classes[J]. Pattern Recognition Letter, 2003, 24(9): 1555～1562. [7] Cuha S, RastogiR, Shim K. CURE: An efficient clustering algorithm for large databases. In: Hass LM, Tiwary A, eds. Proc. of the ACM SIGMOD Int` l Conf. on Management of Data[M]. New York: ACM Press, 1998: 73～84． - 7 -

分享到：

赞收藏

资料库

论文研究-基于k-means聚类算法的研究 .pdf

相关推荐

开发技术

热门标签

最新资料