![点击分享此内容可以赚币 分享](/master/images/share_but.png)
一种服务于K-means的初始中心选取方法_李秋云.pdf
《一种服务于K-means的初始中心选取方法_李秋云.pdf》由会员分享,可在线阅读,更多相关《一种服务于K-means的初始中心选取方法_李秋云.pdf(5页珍藏版)》请在咨信网上搜索。
1、www.ChinaAET.comComputer Technology and Its Applications计算机技术与应用一种服务于 K-means 的初始中心选取方法李秋云1,刘燕武2(1.中国运载火箭技术研究院 北京宇航系统工程研究所,北京 100076;2.中国电子信息产业集团有限公司,广东 深圳 518000)摘 要:聚类是数据挖掘领域最重要的技术之一,K-means 是其中使用频率最高的举足轻重的聚类算法。然而,K-means 算法表现严重依赖于初始中心,选取多少个初始中心以及选择哪些数据点作为初始中心对 K-means 算法十分重要。基于此,提出一种初始中心选取方法 DPCC
2、(Density Peak Clustering Centers)。DPCC 方法基于密度和距离生成一个选取决策图,将数据集中所有的密度峰值点凸显出来。这些密度峰值点即为 DPCC 方法为 K-means 算法提供的初始中心。实验表明,DPCC 方法不仅可为 K-means 提供初始中心数量,还能有效提高 K-means 算法的准确度,并缩减 K-means 算法的执行时间。关键词:聚类;初始中心;决策图中图分类号:TP3-0 文献标志码:A DOI:10.16157/j.issn.0258-7998.223066中文引用格式:李秋云,刘燕武.一种服务于 K-means 的初始中心选取方法J.
3、电子技术应用,2023,49(3):134-138.英文引用格式:Li Qiuyun,Liu Yanwu.An initial centers selection method serving K-meansJ.Application of Electronic Technique,2023,49(3):134-138.An initial centers selection method serving K-meansLi Qiuyun1,Liu Yanwu2(1.Beijing Institute of Astronautical Systems Engineering,China Aca
4、demy of Launch Vehicle Technology,Beijing 100076,China;2.China Electronics Corporation,Shenzhen 518000,China)Abstract:Clustering is one of the most important data mining technologies,and K-means is the most famous and commonly used clustering algorithm.However,the performance of K-means depends heav
5、ily on the initial centers.It is very important for K-means to select how many initial centers and which data points to choose as the initial centers.Therefore,an initial centers selection method called DPCC(density peak clustering centers)is proposed.DPCC generates a selection decision graph based
6、on density and distance,so as to highlight all density peak points in dataset.These density peak points are the initial centers provided by DPCC for K-means.Experiments show that DPCC not only provides decision support for the number of initial centers,but also improves the accuracy of K-means and r
7、educes the running time of K-means.Key words:clustering;initial centers;decision graph0 引言聚类是一种无监督分析方法,其目的是识别出数据集中的所有数据簇,并将每个簇中的数据点看作一类。在众多聚类算法中,K-means1是使用频率最高的举足轻重的算法之一。K-means 算法从数据集中选取 k 个数据点作为初始聚类中心,按照距离最近原则,将其他数据点分配给这 k 个初始中心得到初始簇,再将处于初始簇中心的数据点作为新的聚类中心。重复上述过程,直到聚类中心不再改变为止。K-means 算法的原理相对简单,这也是
8、其受到广泛追捧的原因。然而,该算法也存在着明显缺陷:(1)分析之前,需要明确 k 值。在 K-means 算法中,k值就是簇的数量。若 k 被设置为 10,那么 K-means 算法将识别出 10 个数据簇。但聚类是一种无监督分析任务,在聚类之前无法得知数据集存在多少簇。显然,K-means 算法的机理与聚类初衷是相矛盾的。在真实分析场景中,常常会出现 k 值多于或少于真实簇数的情况,影响聚类准确度。(2)初始中心易聚团。K-means 算法随机将 k 个数据点确定为初始聚类中心,易造成多个聚类中心出现在134Computer Technology and Its Applications计算
9、机技术与应用电子技术应用 2023年 第49卷 第3期同一簇内,导致该簇被分解为多类。(3)迭代次数无法控制。K-means 算法需要经过多次迭代直至聚类中心不再改变为止。通常情况下,聚类中心最终会迭代到密度稠密区。也就是说,初始中心越远离密度核心,K-means 算法的迭代次数越多,运行时间越长。又因初始中心是随机选取的,致使 K-means 算法的运行时间无法控制。针对上述问题,本文提出一种名为 DPCC(Density Peak Clustering Centers)的方法,为 K-means 算法提供初始中心。DPCC 运用于 K-means 算法之前,通过计算数据点密度以及与高密度数
10、据点间最近距离生成决策图,以凸显数据集中所有的密度峰值点。这些密度峰值点即可作为 K-means 算法的初始中心。结合 DPCC 方法后,K-means 算法有 3 大优势:(1)提供 k 值依据。决策图可以凸显出簇的数量。实验显示,该数量与真实簇的数量保持一致。(2)初始中心相互远离。决策图凸显的密度峰值点不会出现聚团。实验显示,峰值点作为初始中心可大幅提升 K-means 算法的准确度。(3)缩减迭代次数。由于密度峰值点本身就在密度核心区,使 K-means 算法的迭代次数可以控制在 12 次内,算法运行时间大幅缩减。1 相关技术近几年,聚类相关研究快速发展。自聚类任务出现以来,迄今为止已
11、有上千种聚类算法被相继提出。这些算法可分为多个分支,如基于中心、基于密度、基于网络和基于层次。基于中心的聚类算法不直接识别簇,而是首先识别聚类中心。这类算法认为聚类中心是待分析数据集中最具代表的点,可以代表数据集中剩余的数据点。在识别出所有聚类中心后,这类算法会根据相应的分配原则将其他数据点分配到各个聚类中心所代表的簇中,以得到聚类结果。这类算法的聚类过程通常较为简单,但缺点也十分明显,即需要事先指定簇的数量。本文关注的K-means 是最经典的中心聚类算法,常见的基于中心聚类算法还有 BK-means2、PQK-means3等。基于密度的聚类算法通常根据数据点密度差异识别簇,这类算法在准确度
12、上常比基于中心的聚类算法更高,但调参较为复杂,不适用于真实且复杂的分析场景。一般情况下,簇核心密度远高于簇边界数据点。基于此,密度聚类算法认定被低密度数据点包围的高密度区域为一个簇。DBSCAN4是最著名的密度聚类算法。该算法将高密度数据点定义为核心点,将核心点邻域内数据点间的关系定义为直接密度可达,该可达关系具有传递性。被直接密度可达传递连接的数据点则称之为密度可达。它将具有密度可达关系的数据点识别为一类,并将与其核心点具有非密度可关系的离散点识别为异常。常见基于密度的聚类算法还有OPTICS5、DENCLUE6、FIDC7等。基于网络的聚类算法近几年逐渐兴起。这类算法通常将神经网络与聚类原
13、理相结合,在训练网络的过程中逐渐实现聚类损失最小化。由于神经网络具有较好的特征学习能力,这类算法在图像数据集上具有较好表现。但是这类算法对计算硬件要求较高,且缺乏可解释性。MIXAE8算法是一个极具代表性的网络聚类算法。该算法镶嵌了 k 个卷积自编码网络,k 为簇的数量。通过不断训练该网络,k 个网络的参数逐渐出现差异化。该算法认为待分析数据集中每个簇中的数据点特征不同,它们之间的差异可以表现在卷积自编码网络的参数上,因此将偏向同一网络参数的数据点认定为一个簇。常 见 基 于 网 络 的 聚 类 算 法 还 有 DLNC9、DSCN10、DGMM11、AGCN12、DeepCluster13等
14、。基于层次的聚类算法同样不直接聚类,而是以嵌套的形式递归得到聚类结果。AGNES14是最经典的层次聚类算法,它将每个数据点看作一个簇得到初始层结果,通过寻找最近的 2 个簇进行合并得到第 2 层结果。再按照上述方法不断合并,直到所有数据点被合并为 1个簇。最终,AGNES 的聚类过程被保存在一个层次结构中,该结构的切面即可作为聚类结果。尽管这类算法实现简单,但选择哪个结果层尚未有一个可以满足所有数据集的合理依据,在真实场景中实操性较差。常见基于 层 次 的 聚 类 算 法 还 有 HDBSCAN15、FINCH16、BIRCH17等。2 原理本文借鉴 DPC18算法,提出了 DPCC 方法来解
15、决 K-means 算法的缺陷。DPCC 的核心思想是识别出待分析数 据 集 中 的 密 度 峰 值 点,然 后 将 密 度 峰 值 点 作 为 K-means 算法的初始聚类中心。众所周知,密度峰值点在局部区域内一定拥有最大密度。因此,密度峰值点有两个特征,一是密度较大,二是与其他大密度点距离较远。为了让计算机理解该特征,需要构建两个指标去量化它们。这两个指标分别为数据点密度以及与更高密度数据点的最近距离。其中,数据点i密度i被定义为:i=j(dij-dc)(1)式中,如果x i dij(2)定义了这两个指标后,计算机即可将那些i和i值135Computer Technology and I
16、ts Applications计算机技术与应用www.ChinaAET.com明显大于其他数据点的数据点认定为密度峰值点。但怎么才是“明显大”呢?又或者说,超过什么阈值,i和i才能称之为“大”呢?一个有效的途径是将所有数据点根据各自的i和i值置于一个横坐标为、纵坐标为的图中,该图被称为决策图。在决策图中,密度峰值点与普通点表现出明显差异。由于密度峰值点的i和i值都较大,它们一定会出现在决策图的右上角区域。而普通数据点的i或i值较小,它们只能出现在坐标轴附近。基于此,就可以轻易识别出所有的密度峰值点。3 实验本节将通过实验展示 DPCC 方法的优势,并将原始K-means 与结合 DPCC 方法
17、的 K-means 进行了比较。3.1 k 值确定效果正如上文所述,K-means 算法的一个主要弊端是在聚类之前需要确定簇的数量(即 k 值),而本文提出的DPCC 可协助 K-means 获得正确的簇数。在真实世界中,数据集是多样的,为全方位展示 DPCC 的有效性,本文在不同类型数据集上测试 DPCC 方法。3.1.1 高斯数据集高斯数据集在真实世界数据集中屡见不鲜,因此有必要验证 DPCC 方法是否可以准确识别出高斯数据集中簇的数量。本文在一组常见的高斯数据集上测试了DPCC 方 法。这 组 数 据19由 3 个 数 据 集 组 成,分 别 为A1、A2、A3。从 A1 到 A3,簇的
18、数量越来越多。图 1 展示了这 3 个数据集的原始分布(第 1 行)以及 DPCC 的决策图(第 2 行)。其中,原始分布图中横、纵坐标分别为数据的第一、二维属性值;决策图中横、纵坐标分别为和值(下同)。实验结果显示,DPCC 决策图中右上角凸显的数据点数量与簇的数量完全一致。因此,DPCC方法对高斯数据集具有鲁棒性。3.1.2 形状数据集相比于高斯数据集,形状数据集较难识别。由于形状簇中数据点分布复杂,K-means 算法易在一个形状簇中识别出多个聚类中心,而在多个相互靠近的簇中只识别出一个聚类中心。因此,验证 DPCC 方法对形状数据集的鲁棒性对 K-means 算法极为重要。本文选择了
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 一种 服务 means 初始 中心 选取 方法 李秋云
![提示](https://www.zixin.com.cn/images/bang_tan.gif)
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。