K-means算法的初始值选取问题的研究_姚蒙.pdf
《K-means算法的初始值选取问题的研究_姚蒙.pdf》由会员分享,可在线阅读,更多相关《K-means算法的初始值选取问题的研究_姚蒙.pdf(5页珍藏版)》请在咨信网上搜索。
1、第 39 卷 第 7 期 福 建 电 脑 Vol.39 No.7 2023 年 7 月 Journal of Fujian Computer Jul.2023 姚蒙,男,1988年生,主要研究领域为算法、数据结构、数据挖掘等。E-mail:。何鹏程,男,1991年生,主要研究领域为算法、数据挖掘。E-mail:。K-means 算法的初始值选取问题的研究 姚蒙1 何鹏程2 1(信阳职业技术学院网络信息管理中心 河南 信阳 464100)2(信阳职业技术学院数学与信息工程学院 河南 信阳 464100)摘 要 随着数据爆发式的增长,数据挖掘算法的使用更加频繁,因此选取合适的数据挖掘算法进行数据分
2、析是非常有必要的。本文对确定 K-means 算法初始值的问题,提出了一种数据预处理的优化方案。通过对目标数据集进行 Canopy 算法处理,并对 Canopy 算法执行后的分组进行降噪、合并,以最终的分组个数作为 K-means 算法的分组 K 值,并以各分组的重心作为初始聚类重心,从而确定 K-means 算法的初始值。对比实验的结果显示,优化后的 K-means 算法具有更好的聚类效果。关键词 数据挖掘;K-means 算法;Canopy 算法;聚类中心 中图法分类号 TP301.6 DOI:10.16707/ki.fjpc.2023.07.011 Research on Initial
3、 Value Selection of K-means Algorithm YAO Meng1,HE Pengcheng2 1(Network information Management Center,Xinyang Vocational and Technical College,Xinyang,China,464000)2(Department of Mathematics and Information Engineering,Xinyang Vocational and Technical College,Xinyang,China,464000)Abstract As a fast
4、-moving consumer product,cigar products are also limited by tobacco monopoly laws and mainly sold offline,which makes it difficult for consumers to obtain data and cannot meet the demand for cigar consumption insights.The available cigar consumption data mainly includes search data that generate dem
5、and for cigars and evaluation data after cigar consumption.This paper aims to build a cigar Data dictionary with insight into cigar consumption demand.The visualization results indicate that the search data for Great Wall cigars increased by 5%in 2022,providing insight into the growth in consumer de
6、mand for Great Wall cigars.The associated term Cigar Express Network has emerged,revealing the emergence of a new model for cigar purchase.After marketing personnel conducted promotional training for retail customers,the local delivery model increased by 37.6%year-on-year.Keywords Data Mining;K-mean
7、s Algorithm;Canopy Algorithm;Cluster Center 1 引言 聚类算法是用“物以类聚”的思想1,把性质相同或相近的数据划分到同一个分组,把性质差异较大的数据划分到不同的分组。K-means 算法是基于划分的一种迭代聚类算法2。该算法优点如下:(1)收敛速度快。这一特征在处理组别之间差距较大的凸面数据时体现得尤为明显。不同组别相似度低,组内数据相似度高,则在迭代计算时,速度会很快,聚类也会达到很好的效果3。(2)算法复杂度为 O=N*K*t,是线性关系。其中,N 是数据集总数据个数,K 即为分组个数,t是算法直到收敛总的迭代次数。在处理大数据集时的可伸缩性比较
8、强4。因算法复杂度低,执行效率较高,很适用于海量数据集的聚类处理。K-means 算法虽优点突出,但同时也存在着如下缺点:58 姚蒙等:K-means 算法的初始值选取问题的研究 第 7 期(1)K 值确定存在困难。K-means 算法在执行时,分组数量 K 的值需要提前指定,目标数据集的不同会导致难以预先指定K 值。K 值的选取必须根据数据集本身的数据特征和实验期望通过处理所得到的分组数来共同决定。因此,K 值的选取存在困难,在处理数据集前很难确定该数据集最合适的分组数5。(2)初始聚类中心不易确定。算法的执行需要指定初始的聚类中心。K-means 算法的执行步骤就是根据初始中心分组,通过不
9、断的迭代,最终得到收敛结果。初始聚类中心的选取如同 K 值的选取一样,选取不同的聚类中心会导致聚类结果的不同6。因为 K-means 算法选取误差的平方和 SSE 作为度量聚类质量的目标函数,如式(1)所示:SSE=dist(Ci,x)2xiCiKi=1 (1)其中,dist 表示两个点的欧氏距离,Ci为 K 个分组中的任意一个,xi为 Ci分组中的数据。因该函数存在多个极小值,如果初始聚类中心选取不当,会使算法执行后的最终结果在某一极小值上,而并非全局最优解,导致聚类结果与实际偏差较大。(3)易受噪声点和孤立点的影响。在数据采集过程中,虽然会有一定程度的鉴别和筛选,但当数据集的规模到达一定程
10、度后,最终获取的结果难免会体现在数据收集过程中的过失。例如,出现错误的一些数据在进行聚类时会成为“噪声点”;一些数据虽未出错但与其他剩余数据差别较大,并存在于数据集中时,则在聚类中会成为“孤立点”。由于 K-means 算法的特性,所有数据都会在迭代计算中,导致分组的聚类中心有可能会因噪声点、孤立点的数据而使其偏离实际值,无法得到很好的聚类效果7。鉴于以上问题,本文提出了数据预处理的方法,以优化 K-means 算法的执行效果。通过数据预处理,确定K-means算法的初值K和初始聚类中心,使得 K-means 算法的执行结果更具参考意义。2 K-means 算法初值选取方法 当前存在的数据预处
11、理方法较多,如选取低复杂度算法优先进行一次运算。本文基于这种方案,选取 Canopy 算法作为 K-means 算法的初始步骤8。整个数据预处理的过程分为三步:(1)执行 Canopy算法。(2)数据集“降噪”。(3)合并剩余分组并检验阈值的选取。2.1 获取Canopy初始分组 当 Canopy 算法执行后,会生成多个 canopies(即 canopy 分组)。以图 1 为例,简要分析 Canopy处理后的结果,图 1 中出现了从 A 到 F 共 6 个分组。每个分组的中心为圆心,虚线部分小圆半径 D1,实线部分大圆半径为 D2。假设任意一点与圆心的距离为 dis,当 disD1 时,称该
12、点与当前分组为强关联点;当 D1disD2 时,该点与当前分组为弱关联点。图 1 Canopy 结果 2.2 数据集“降噪”通过图 1 的执行结果可以看出,Canopy 算法执行后会给出若干个分组(即 canopies)及每个分组的数据中心。若以 canopies 的数量作为 K-means 算法的K值,以各个canopies的数据中心作为K-means算法的初始聚类中心,Canopy 算法的执行结果可以直接作为 K-means 算法的初始值。这种做法在一定程度上减少了 K-means 算法初值选取的随机性,提高了 K-means 算法的处理精度。但为了使 K-means算法的精度更高,获得一
13、个更好的分组结果,就必须对 canopies 进行进一步处理。首先需要进行整个数据集的降噪。如图 1 中的分组 E,该分组中只包含了 1 个数据点,且距离该数据点 D2 范围内并不存在弱关联点。综合上述对数据集的分析,该点可作为两种对象分别进行处理:(1)将其作为噪声点,直接从数据集中删除。(2)将其作为孤立点,专门列出分组,在进行 K-means 算法时将其挑出,避免其干扰分组效果。对于是噪声点还是孤立点的判断,需要溯源到数据采集环节,根据实际情况加以2023 年 福 建 电 脑 59 判断。但不管是当作噪声点还是孤立点来处理,均为“降噪”过程。2.3 合并分组 将分组 E 降噪处理后,再观
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- means 算法 初始值 选取 问题 研究 姚蒙
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。