基于结构系数的K-means初始聚类中心选择算法.pdf
《基于结构系数的K-means初始聚类中心选择算法.pdf》由会员分享,可在线阅读,更多相关《基于结构系数的K-means初始聚类中心选择算法.pdf(5页珍藏版)》请在咨信网上搜索。
1、2023 年第 5 期计算机与数字工程收稿日期:2022年11月7日,修回日期:2022年12月10日基金项目:广东省大学生创新创业项目“基于图像变换与压缩算法的荔枝损伤研究”(编号:S202010564034);华南农业大学微达安产业学院项目资助。作者简介:李汉波,男,研究方向:机器学习与数据挖掘。魏福义,男,硕士,教授,研究方向:组合矩阵论和人工智能。张嘉龙,男,研究方向:人工智能。刘志伟,男,研究方向:人工智能。黄杰,男,研究方向:统计应用。方月宜,女,研究方向:应用数学。1引言聚类分析是数据挖掘中的一个重要研究领域。聚类算法是衡量数据相似性的典型算法,它以“物以类聚”的思想,在文档分析
2、、图像压缩1、特征提取、图像分割等领域得到广泛的应用。MacQueen于1967年首次提出K-means算法,它基于样本间相似度对数据进行划分,具有聚类效果好和收敛速度快等特点,属硬聚类算法2。传统K-means算法随机选取初始聚类中心会导致聚类结果不稳定3。为了削弱初始聚类中心选取的随机性对聚类结果不稳定的影响,研究确定初始聚类中心的有效方法具有重要意义。一个好的聚类算法具备各类中包含的样本点彼此相似,并且聚类中心在空间分布上尽量分散4的特征,这样才能更好地让每一类体现不同于其他类的特性。确定聚类中心和数据分类问题一直是大数据研究的热点内容512。文献 13 运用了相异度的概念,通过构造相异
3、度矩阵,选取K个与其他样本相异度较低且聚类个数最多的样本作为初始总第 403期2023 年第 5期计算机与数字工程Computer&Digital EngineeringVol.51No.5基于结构系数的 K-means 初始聚类中心选择算法李汉波魏福义张嘉龙刘志伟黄杰方月宜(华南农业大学数学与信息学院广州510642)摘要传统的K-means算法选取初始聚类中心时的不确定性会导致聚类结果不稳定。论文提出了基于相异度的邻域及其结构系数的概念,从最小的结构系数开始,按照其递增顺序寻找初始聚类中心;随后采用依次缩小邻域的技巧逐步探索,直到找到K个初始聚类中心。该方法同时得到li(i=0,1,2,q
4、)个初始聚类中心及其对应的数据分类结果。实验证明,对比于以往的算法,新算法具有更高的分类准确率以及更少的迭代次数。关键词K-means聚类;相异度;初始聚类中心;结构系数中图分类号TP31DOI:10.3969/j.issn.1672-9722.2023.05.003Algorithm for Selecting K-means Initial Clustering CentersBased on the Structure CoefficientLI HanboWEI FuyiZHANG JialongLIU ZhiweiHUANG JieFANG Yueyi(College of Math
5、ematics and Information,South China Agricultural University,Guangzhou510642)AbstractThe uncertainty in selecting initial clustering centers usually leads to unstable clustering results of the traditionalK-means method.This paper proposes a new concept of neighborhood and structure coefficients based
6、 on dissimilarity.This algorithm looks for the initial clustering centers in order of ascending structure coefficients,starting from the neighborhood with thesmallest coefficient.The above procedure is repeated with the neighborhood reduced until the K initial clustering centers are found.By the pro
7、posed algorithm,it can finally obtain li(i=0,1,2,q)initial clustering centers and the corresponding data classificationresults.Experiments show that this algorithm achieves higher classification accuracy and needs less number of iterations than the existing algorithms.Key WordsK-means clustering,dis
8、similarity,initial cluster centers,structure coefficientsClass NumberTP31993第 51 卷聚类中心,该算法削弱了传统算法对初始聚类中心的敏感性,在传统算法的基础上具有更高的分类准确率。文献 14 在文献 13 的基础上增加了一个判断,当最大相异度参数不唯一时,提出了一种合理选取最大相异度参数值的解决方案,改进算法与文献 13 的算法在准确率和迭代次数方面有所优化。而文献 15 提出了一种基于最大距离中位数及误差平方和(SSE)的自适应改进算法,通过SSE变化趋势决定终止聚类或继续簇的分裂。本文算法基于文献 13 的相异度
9、概念,定义一个可变邻域参数,从最小结构系数开始,按结构系数递增的顺序寻找初始聚类中心,直到找到 K 个初始聚类中心。本文实验表明:采用新方法构造的算法相比文献 13、文献 14 以及文献 15 具有更高的准确率和更少的迭代次数。2改进的选取初始聚类中心算法首先给出基于相异度的四个新概念,在此基础上推导改进的K-means选取初始聚类中心的新方法,最后得到基于结构系数的新算法。2.1基本概念设待聚类样本数据:X=x1x2x3xn,其中xi=xi1xi2xi3xim,n为数据集中的样本数,m为样本属性的个数。采用三个步骤计算样本间相异度并构造相异度矩阵13:1)计算不同样本的第 s 个属性的相异度
10、:r(s)ij=|xis-xjsmaxxrs-minxrs,ij12n,其 中r(s)ij表示样本xi与xj之间第s个属性的相异度,xrs为第s个属性的所有取值;2)计算不同样本的相异度:rij=s=1mr(s)ij,其中rij表示样本xi与xj之间的相异度;3)构造相异度矩阵:R=0r12r13 r1nr210r22 r2nr31r320 r3nrn1rn2rn30记Ri=ri1ri2rii-1rii+1rin,其 中 i=1,2,n。定义1 对于样本xi和邻域参数,从Ri中任意取-1个元素求和,和最小的值称为样本xi的邻域的结构系数,记为D(,xi)。定义 2 设-rijR,若j=1-1-
11、rij和最小,则-rij对应的样本xj(j=12-1)和xi组成的集合称为样本xi的邻域,记为U(,xi);U(,xi)中的样本称为邻域的内点。在参数确定的条件下,样本xi对应于结构系数D(,xi)和邻域U(,xi)。定义3 对于样本集X=x1x2x3xn,集合D(x1)D(x2)D(xn)称为对应参数的结构系数集合,记为M()。定义4 数min1inD(xi)称为对应参数的最小结构系数,记为D()。由定义2和定义4可知,最小结构系数D()对应含有个样本最密集的邻域。对于样本集X,若要选取K个聚类中心,则nK,其中nK表示数nK取下整。2.2算法思想本文从=nK出发,计算并确定D()及其对应的
12、邻域U(,xi),逐步寻找初始聚类中心。遴选K个初始聚类中心的方法:1)首先采用三个步骤构造出相异度矩阵,以及计算邻域的结构系数集合M();2)计算M()的最小结构系数D(),其对应的样本不妨设为xi,将样本xi作为第一个初始聚类中心,同时标记其邻域U(,xi)的内点,并将其结构系数都设置为,记新的结构系数集合为M1();3)选取M1()中最小结构系数D(),其对应的样本不妨设为xj,将样本xj作为候选点。若邻域U(,xj)的内点均没有被标记,则选取xj作为下一个初始聚类中心,并标记其所有内点,同时将内点的结构系数设置为。否则,将D(,xj)设为,随后选取M1()中最小的元素对应的样本作为候选
13、点;4)反复进行以上判断直至所有样本的结构系数都为,此时得到的初始聚类中心个数记为l0;5)若l0K,则选择前K个候选点为初始聚类中心;若l0K,则清空初始聚类中心和内点标记;6)缩小邻域参数,循环以上方法,直到选出K个初始聚类中心。根据以上分析,得到算法的流程图如图 1 所示。按照上述算法流程,设参数=nK缩小 q 次李汉波等:基于结构系数的K-means初始聚类中心选择算法9942023 年第 5 期计算机与数字工程后,即=nK-q时,得到K个初始聚类中心,与其对应的K个邻域表示对数据集X的K个分类结果。设分别取nKnK-1nK-inK-lq时,得到的初始聚类中心个数依次为l0l1liK,
14、按照新算法,同时得到li=(i=01q)个初始聚类中心和相应数据聚类结果。图 1算法流程图3实验结果与分析以常用的五个UCI数据集为实验数据,将本文算法与文献 5、文献 6 和文献 7 的算法进行对比实验,验证新算法的有效性。3.1实验数据集UCI数据集作为标准数据集,经常用于测试机器学习算法的性能,为了验证以上算法选取初始聚类中心的有效性,本文采用UCI数据集中的Diabetes数据集、Iris数据集、Harbeman数据集、Wine数据集和Seed数据集作为实验数据集,数据集详细信息如表1所示。表 1实验数据集描述信息数据集DiabetesIrisHabermanWineSeed样本数量7
15、68150306178210属性维度843137分类数23233每类样本数268,50050,50,50225,8159,71,4870,70,70由 于 Diabetes 数 据 集、Haberman 数 据 集 和Wine数据集各维度属性取值范围差异较大,先对这三个数据集进行零-均值规范化,以便消除属性差异对聚类性能的影响。对于每一维度属性,有如下计算公式:x*i=xi-xii其中,-xi为样本数据第i维属性的均值,i为样本数据第i维属性的标准差。3.2聚类效果评价指标衡量聚类算法性能的评价指标有许多种,本文选用准确度和迭代次数作为判定聚类算法性能优劣的指标。设数据要求分为K类,则准确度的
16、计算公式14如下:MP=i=1Kin其中n为样本总量,i表示被正确划分为第i类的样本数量,MP值越接近1,表示聚类效果越好。对于数据集要求分为K类,在保证准确度前提下,迭代次数越少越好。3.3实验结果和分析表2表6分别是文献 13、14、15 算法和本文算法在5个UCI数据集上的对比实验。表2Diabetes数据集的实验结果文献 13 算法文献 14 算法本文算法准确率/%66.3268.4571.35迭代次数979在 Diabetes 数据集中,使用本文算法改进的K-means算法的准确率最高,为71.35%。虽然在迭995第 51 卷代次数方面略微高于文献 14 算法,但与文献 13算法持
17、平。由此可见,本文算法对于Diabetes数据集聚类性能具有改良效果。表3Iris数据集的实验结果文献 13 算法文献 14 算法文献 15 算法本文算法准确率/%89.3389.3389.3389.33迭代次数4274对 于 Iris 数 据 集,本 文 算 法 的 准 确 率 为89.33%,准确率效果与文献 13、14、15 的算法持平。在迭代次数方面,本文算法与文献 13 算法性能相同,相比文献 15 迭代次数减少3次,但略逊于文献 14 算法。表4Haberman数据集的实验结果文献 13 算法文献 14 算法本文算法准确率/%74.5175.4974.84迭代次数865在Haber
- 配套讲稿:
如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。