论文研究-改进的K-means聚类k值选择算法.pdf

所需积分/C币:48 2019-09-06 15:33:27 1.96MB .PDF
收藏 收藏 1
举报

空间聚类算法中,聚类的效果在很大程度上受制于最佳[k]值的选择。典型的[K]-均值算法中,聚类数[k]需要事先确定,但在实际情况中[k]的取值很难确定。针对手肘法在确定[k]值的过程中存在的“肘点”位置不明确问题,基于指数函数性质、权重调节、偏执项和手肘法基本思想,提出了一种改进的[k]值选择算法ET-SSE算法。通过多个UCI数据集和[K]-means聚类算法对该算法进行实验,结果表明,使用该[k]值选择算法相比于手肘法能更加快速且准确地确定[k]值。
王建仁,等:改进的 K-mcans聚类k值选择算法 2019,55(8) 32对总误差平方和的改进 将公式(4)(5)进行组合,可得政进后的 ET-SSE值 传统的手肘法是以簇内误差平方和SE)加和后如下 所得的总误差平方和(SSE)为核心指标的。然而,这种 求和的方式存在一种问题。以k=2为例,则会有以下 E 两种特殊情况:情况1SF1=-130,S52=130),情况2化简后可得: (SSE1-10,SSE2-250),一般来说,会认为第一种情况 ET-SSE=D+M 会更好一些,但是通过总误差平方和计算可得最终结果其中,D为改进的误差平方和,M为偏执项。 (SE-260相同。造成这种情况产生的原因主要是加3.3对簇内误差平方和的改进 和的方式使得某些分类效果较差的簇计算所得的簇内在实际的操作过程中可能会存在这样一种情况:即 误差平方和被聚类效某较好的的内误差平方和中簇C中簇内对象到簇中心c的K式离相对较远 和了。 这种现象在实际聚类数大于的取值时尤为明显,此时 为解决这一间题,对总误差平和公式进行了改进,计算所得的簇内误差平方和将较大,由于指数函数 引入了指数函数e。∈为指数函数,总体图像位于x对的止值变化非常敏感,且△x变化所对应的函数值 轴方单调递增;作为基本初等函数之一的指数函变化非常剧烈,使得在实际操作过程中产生的函数值可 数还具有个非常重要的性质,即对指数x的正数值能过大甚至可能会出现“指数爆炸”现象,非但不会提 的变化非常敏感21,如图2 高最终的k值预测精度,反而会影响二维直角坐标系中 对聚类效果变化(折线的变化情况)的观察,故本文引入 p 权重0对计算所得的簇内误差平方和进行放缩调节,将 Y=lbx 放缩后的误差平方和作为指数函数自变量,如图3。 r=sint 50Y=arcsin 20000 Y 0 Y-expi.x) 15000 10152.02.53.03.54.04.55.0 0000 图2c与不同函数的趋势对比 5000 通过图2能够清晰地发现,指数函数e对x的正值 变化优于其他函数。因此,将e应用于总体误差平方 和加和公式,能够进一步提高聚类效果欠佳的簇在加和 图3权重0调节前后e图像对比 公式中所占的比重,具体公式如下 通过权重0的调节,可得最终k值选择算法公式 如下 (4) 在实际的掉作过程中发现,当前公式计算结果在折 C 线图的实际展示过程中,值确定的精度虽优于SSF,式中,h为人为设置的聚类数,c为簇C的中心,6为 但是效果并没有预期的明显。为进一步提高聚类误差权重负责调节簇内误差平方和数值的大小,p为簇C 较大簇所计算出的簇内误差平方和的比重,进一步引入 屮的样本对象。 ET-SSE计算过程示意图如图4 偏执项调节变量。其依据上文中所提到的指数函数e 的性质,从k个簇挑选出簇内误差平方和最大的数值4 ET-SSE算法实现 (聚类效果最差的簇的混乱程度)作为指数函数自变量, python作为一种动态编程语言,具有简洁、类厍丰 重就越大在实测过程中表瑰更优值选择精度进一富等优势,为机器学提供了丰富的数据类型和诸如 步提高。偏执项具体公式如下: tplotlib 点使得在基于 python编程时可直接调用标准厍和第三 m∑|p M=e (5)方库中已有的内容来大大减少重复工作。在phon 式中,p为簇C中的对象,∑|=c为簇内误差平 框架下,本文将 ET-SSE算法分解为若干子模块(任务), 具体流程如图5。 方和,max表示的是在计算所得的k个簇内误差平方和41读入原始数据 中挑选出数值最大的 该阶段的主要任务是将存储在变量文件内的结构 302019,55(8) Computer Engineering and4 pplications计算机工程与应用 Estimated number of clusters: 4 Estimated number of clusters: 4 : ,· 2-10 图4(a) ET-SSE欧式距离计算 图4(b) ET-SSE计算簇内误差平方和 Estimated number of clusters: 4 Estimated number of clusters 4 M=SSEI Sxx-D+M 2 4 图4(c)总误差平方和和偏执项计算 图4(d) ET-SSE值计算 k=k+1 K- means迭代过程 ETSE算法计算过程 读入数据 对k取 生成新 计算SEr存‖绘制二维直输出最 初值 中心点于矩阵当中}·角坐标系「佳k值 图5EI-SSE算法流程 化数据读入,并进行一些预处理,将读入的数据转换成 C datasnp. delete( data, index, 0) 程序能够识别的aray,并随机选择一个初始聚类中心 return data. o datas. c datas (=1),将簇中心和剩余其他对象所包含的属性及其属42 K-means迭代过程 性值返回。具体稈序伪代码如下所示。该模块主要使 ET-SSE算法的输入就是在K- means迭代过程输出 用 numpy和 pandas类库 结果的基仳之上进行计算的。 findcenters函数 Input:待聚类数据集合data、聚类数k、最大迭代次数 Input:源数据集(csv文件)、聚类数k max iters Output:源数据ata、簇中心 o datas和剩余其他对象 Output:添加了标签的数据对象集合 cluster Ship er Ship=[ c data m,n=datashape o datas=[]#将 o datas初始化为空列表 for 1 in range(m):#循环遍历原始数据集的每一 c datas-#将 C datas仞始化为存储剩余数据对象 对象 data=pd, read csy(“数据集名称,csv") for j in range(k):#计算每个对象与簇中心 m,n= data. shape#获取读入数据的行和列 的距离 indx=在[0,m中随机选择一个数作簇中心对应的下标 更新当前对象到所有簇中心的最小距离 for j in range( len(o datas ) 王建仁,等:改进的 K-mcans聚类k值选择算法 2019,55(8) 31 更新簇中心 数据集包含90个数据对象,每个数据对象包含7个属 for L in range(max iters) 性,共2类,分别对应19、71个数据对象。选择传统的 不断对聚类结果进行送代,直至最优,并将聚类“手肘法”与本文基于“手肘法”提出的改进算法 ET-SSE 结果输出 算法,将其分别应用于具有不同标签数量、不同样本量 return cluster Ship 的 datar2、Irs、Wine和 Immunotherapy数据集,测试改 43 ET-SSE算法计算过程 进算法的实际运行效果是否优于SSF;并将该改进算法 该过程为整个算法的核心部分,算法的其体流程与常用的“事后”判断k值是否最优的算法SE和轮廓 如下。 系数法就算法的运行时间、k值选择的准确率两个方面 Input:k的最小取值 num min,k的最大取值 nuim max,源 数据集data 进行对比测试,以说明本文提出的改进算法的有效性。 Oulput:k和SEr对应的二维平面直角坐标系 表1实验样本 da, o datas, C datas-)数据读取雨数 findcenterso 数据集名称样本量属性数类别数类别/样本 result=np zeros(k、21)#创建一个k行两列的数组,存 3[50,50,50] 储对应的k和SF值 Datar 2 I 17 52,65] or I In range(k):#对k从小到人进行遍历 178 3 [59,71,48] clusterShip=K means( data, i, max iters=50) Immunotherapy 「19,711 resulti,O]存储k值 5.2实验环境 计算k值对应的sE 实验的硬件条件为个人笔记本电脑 Thinkpad E480 resul[i,1]存储对应的S 台,内部配置有8 GB RAM内存, Intel core i7 for i in range(k) 8550UCPU@1.80GHz2.00GHz核心处理器,128GB 遍历二维数组 result 通过 matplotlib)绘制二维直角坐标系和k、SFr 态硬盘和512GB磁盘, Intel UHD Graphics620 对应的折线图 和 Radeon rx50双显卡;软件条件主要包含:Win pIt show() dows10家庭版64位操作系统, spss modeler18.0, print最佳k值 ChArm, python3.6解释器, anaconda的 python第三 方厍等。本文所涉及的算法均为 python实现 5实验与分析 5.3实验结果与分析 51实验描述 为了说明改进的k值选择算法EI-SSE的实际运行 为进一步验证本文改进的k值选择算法 ET-SSE算效果,本文采用data2 Iris wine和 Immunotherapy数 法的有效性,本文选取UCI数据集中Iris、 datar2(mdex=据集进行对比实验,k的取值范围设定为[l,8]。从表 00451)、wine和 iMmunotherapy数据集作为实验数据集。表2和图6中通过比较程序运行听产生的计算结果,能 如表1,Iris数据集合包含150个数据对象,仟一对够很容易发现,传统的“手肘法”在四个UCI数据集中预 象包含4个属性,包含3种不同的类别标签,每个标签对测的最佳k值均为一个范围域(离散型),对于大部分预 应50个样本对象8; datar2数据集合包含117个数据对测结果,实际的最佳k值包含在此范围内,一小部分k 象,仟一对象包含9个属性,包含2种不同标签,分别对值预测出现严重偏差,k值的确定过程存在很大的误 应52、65个数据对象;wine数据集包含对象178个,3类差;而 ET-SSE算法预测的最佳k值均为个固定的数, 別标签分別对应5971和48个样本对象; mmunotherapy与实际的数据集的聚类数完全相同,精度较高。本文算 表2SSE、 ET-SSE在 datar2、Iris、Wine及 Immunotherapy数据集上的计算数据 Datar Iris winc Immunotherapy SSE ET-SSE SSE ET-SSE ETSSE SSE ET-SSE 13930037.191054293243680.829931.3517592296.3817648191.871703280.935412846.87 11070382.97 329159.17155032173.151496489502324859.641680988.46 74969.75 10777203.26 1780.53129.50 863576266707 77.8l167207996 74926.85 10516851.23 178L.1960.1 6.04221614296 510606151.59 968.2052.75 6934859390.48 34.431628929,44 1171.3 10577575.53 656914964 7.8 1968250.13 7981009066.94 134.10 398078.80 87.23 8.74457195134 25.05000317.62 134.95 7494311.16 77.6834.50 9.574396082.06 25.2198902943 122.47 预测值 13,4 14,5,6 32 2019,55(8) Computer Engineering and4 pplications计算机工程与应用 表3SSE、EI-SSE及轮廓系数在不同标签数、不同样本数的数据集上的对比 Datar Iris Wi Immunotherapy 时间预测值预测 算法运行 运行 孤识运行 预测 准确率%时间 预测值 准确率/%时间 预测值 准确率%时间预测值预测 准确率 SSE0.128693[2-7 250.123708[2,4 500.1326440[3,4 50.00.132605 ET-SSE0.3645612 1000.12311713 1000.1467934110000.13284912 l00 轮廓系数0.1376462,3,4]00.141607[2,S] 50.1526450[2.3,733.30.119682[2,3,5,7 1.2 iriS-ET-SSE 0.8 0.6 0.4 ET-SSEI ET-SSE k 图6(a) datar2数据集上的运算数据折线对比图 图6(b)Iis数据集上的运算数据折线对比图 wine-SSE Immunotherapy-SSE 1.50 winc-FT-SSE Immunothcrapy-FT-SSE 125 ① 0.50 图6(c)Winc数据集上的运算数据折线对比图图6(d) Immunotherapy数据集上的运算数据折线对比图 dataR2-Silhouette Silhouette Wine- Silhouette Immunotherapy-Silhouette 0.66 0.58 c O 0.54 10.55 0.60 0.58 三0.45 0.56 0.48 0.35 0.5 k 图7轮廓系数法在不同数据集上运算数据折线对比图 法确定的k值史加接近实际的聚类数,预测效果史佳,廓系数法的运行时间随之増大,而改进的算法在大多数 能有效解决传统“手肘法”在应用过程中“肘点”不明昴情况(样木量较大)下的运行时间低于轮廓系数法。就 的问题 算法的预测精确度来说,与传统的“于肘法”相比k值预 从表2和图7中可知,传统的“手肘法”和改进后的测准确率更高且预测结果稳定,与轮廓系数法相比改进 EI-SSE算法的运行时间相当,在保持了原有算法较低的k值选择算法的运行时间短,时间复杂度小。本文提 时间复杂度的基础上进一步提高了精度;轮廓系数法是出的改进的k值选择算法FT-SSE从实际的测试结果中 种通过计算分离度与内聚性来选择最佳值的一种k可以看出在运行时间基木不变的情况下,在 dataR2、 值选择算法,该算法虽精度较SSE高,但其需要计算距Iis、wine和 Immunotherapy数据集上的预测准确率均 离矩阵,当数据量非常庞大时,运行时间将会非常长。为100%,可见改进算法的有效性。这主要是因为,改进 通过实验实测发现,随着测试数据集数据量的增大,轮算法针对传统手肘法存在的“肘点”不明显问题针对性 王建仁,等:改进的 K-mcans聚类k值选择算法 2019,55(8) 33 地引入了c、偏执项和调节杈重θ,有效地斛决加和过5]白树仁东龙自适应K值的粒子群聚类算法[计算机 程中误差的相互中和,提高了误差较大簇所占的比重。工程与网用2017,53161:11610 对比实验表明,木文针对“手肘法”现存在的“肘点”阿鲍黎明,黄刚.基于多叉树确定K值的动态K- means聚 不明确问题提出的基于指数函数性质、权重调节、偏执 类算法计算机技术与发展,2017,27(6):41-45 项和于肘法基本思想的k值选择算法在实际的数据集]李琪,张欣,张平康等基于密度峰值优化的camy 测试当中能够有效解决传统手时法在选择过程中 Kmeans并行算法小通信技术,2018(2) 肘点”不眀确的问题,且运行时间与传统∵于肘法”相 [8]王学贺.一种基于改进微粒群和轮廓系数的划分聚类方法[J] 云南民族大学学报(自然科学版),2016,25(4):367-371 当时间复杂度较小。同时,在与轮螂系数法的对比过(91成老占艳红一种基于最大最小距离和SE的自适应 程中发现,精度要高丁轮犀系数法,且算法的实际运行 聚类算法[南京邮电大学学报(自然科学版),2015,35 时间小于轮廓系数法的运行时间。综上所述,改进的k 2):102-107 值选择算法S的准确率更高时间复杂度较低,说m@年建新,王柏人,曲等,基改进欧式距离的硬件木马 明」算法的有效性 检测[]计算机工程,2017,43(6):92-96 [l Zhang Meirong, Zhao Kai Multilinear singular integrals 6结束语 on variable exponent Herz- Hardy spaces[J] Applied Mathe K- means算法是一种应用十分广泛的算法,但是聚 matics,2017,30(1):98-104 类数k是人为确定的,在实际的聚类过程中很难选取到12蒋业萍贺超,秦惠增基本初等函数的高精度快速计算 最佳k值,进而影响到聚类的效果。在众多的基于SSF 的加速算法数学的实践与认识,2017,47(13):238-24 的k值选择算法中,均是在SS基础上提出的,并未对 [13 Chen Zhifei, Ma Wanwangying, Lin Wei, et al. A study 算法本身进行改进。本文基于指数函数性质、权重调 on the changes of dynamic feature code when fixing 节、偏执项和手肘法基本思想针对传统的手肘法屮“肘 bugs: towards the benefits and costs of Python dynamic 点”不明确问题进行改进优化,实验表明该算法能有效 leatures[J].Science China(Information Sciences), 2018 6l(1):169-186 解决“肘点”不明确问题,且性能良好。但还需进一步研 [14]姜安印,冯龙飞.基于 Python的长文本比较研究——以 究:在实际的操作过程中需要对θ进行调整,如何确定 《管子》与《国富论》经济思想比较为例叮.图书与情报 最佳的权重将是下一步需要研究的内容。 08(2):67-73 [15]王丽,邹丽雪,刘细文.基于LDA主题模型的文献关联分 参考文献: 析及可视化研究[数据分析与知识发现,2018,2(3) []贾瑞玉,李玉功.类簇数目和初始中心点自确定的K 98-106. means算法[计算机工程与应用,2018,54(7):152-158 [16]初蓓,李占山张梦林,等.基」森林优化特征选择算法的 [2]张淑芬,董岩岩.陈学斌基于云计算平台 Hadoop的IKM 改进研究门软件学报,2018(9):2547-2558 聚类算法设计研究[J应用科学学报,2018,36(3):524534.[17张文元,谈国新,朱相舟.停留点空问聚类在景区热点分 「3]蒋丽,薛蓍良.优化初始聚类中心及确定K值的K- mcans 析中的应用[小计算机T程与应用,2018,54(4):263-270 算法J计算机与数字工程,2018,46(1):21-24 「18]谢娟英,高红超,谢维信.K近邻优化的密度峰值快速搜索 [4]周本金,陶以政,纪斌,等最小化误差平方和k- means初 聚类算法[J中国科学:信息科学,2016,46(2):258-280 始聚类中心优化方法[计算机工程与应用,2018,54(15):[19]殷亚博,杨文忠,杨慧婷,等.基于搜索改进的KNN文本 48-52. 分类算法[J计算机工程与设计,2018(9):2923-2928

...展开详情
试读 7P 论文研究-改进的K-means聚类k值选择算法.pdf
立即下载 低至0.43元/次 身份认证VIP会员低至7折
    抢沙发
    一个资源只可评论一次,评论内容不能少于5个字
    img
    • 至尊王者

      成功上传501个资源即可获取

    关注 私信 TA的资源

    上传资源赚积分,得勋章
    最新推荐
    论文研究-改进的K-means聚类k值选择算法.pdf 48积分/C币 立即下载
    1/7
    论文研究-改进的K-means聚类k值选择算法.pdf第1页
    论文研究-改进的K-means聚类k值选择算法.pdf第2页
    论文研究-改进的K-means聚类k值选择算法.pdf第3页

    试读已结束,剩余4页未读...

    48积分/C币 立即下载 >