k均值聚类算法中初始点与时间复杂度的改进研究

《k均值聚类算法中初始点与时间复杂度的改进研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、分类号：密级：UDC：编号：学位论文K均值聚类算法中初始点与时间复杂度的改进研究谭有倩指导教师姓名：刘国丽教授河北工业大学申请学位级别：硕士学科、专业名称：计算机应用技术论文提交日期：2012年11月论文答辩日期：2012年12月学位授予单位：河北工业大学答辩委员会主席：评阅人：2012年11月DissertationSubmittedtoHebeiUniversityofTechnologyforTheMasterDegreeofComputerAppliedTechnologyTHEIMPROVEDRESEARCHO

2、FK-MEANSCLUSTERINGALGORITHMININITIALVALUESANDTIMECOMPLEXITYByTanYouqianSupervisor:Prof.LiuGuoliNovember2012原创性声明本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行研究工作所取得的成果。除文中已经注明引用的内容外，本学位论文的研究成果不包含任何他人创作的、已公开发表或者没有公开发表的作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集体，均已在文中以明确方式标明。本学位论文原创性声明的法律责任由本人承

3、担。学位论文作者签名：日期：关于学位论文版权使用授权的说明本人完全了解河北工业大学关于收集、保存、使用学位论文的规定。同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版本；学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有关部门或者机构送交论文的复印件和电子版；在不以赢利为目的的前提下，学校可以适当复制论文的部分或全部内容用于学术活动。(保密的学位论文在解密后适用本授权说明)学位论文作者签

4、名：日期：导师签名：日期：河北工业大学硕士学位论文K均值聚类算法中初始点与时间复杂度的改进研究摘要数据挖掘是在海量的数据中挖掘出潜在的、有价值的信息，这些信息给人们提供帮助。聚类分析是数据挖掘中一个重要的应用。它以“物以类聚，人以群分”的思想，根据对象之间的相似度将相似度大的对象划分到同一类，不同类之间的对象相似度低。由于简单、快速的优点，K均值聚类算法成为聚类分析中最频繁使用的算法之一。本文针对K均值聚类算法对初始点依赖性及时间复杂度高的特点两方面进行深入研究，为了改善K均值聚类算法对初始点的依赖性，提出了基于迭代密度

5、的K均值算法(简称IDKM)，通过不断修改密度阀值，获得较多的聚类中心，并将聚类中心合并，直到达到规定数目的聚类中心，将IDKM算法应用于IRIS数据集进行聚类分析，证明改进算法改善了K均值聚类算法对初始点的依赖性；针对K均值聚类算法时间复杂度高的特点，本文提出基于三角不等式与移除边界的K均值聚类算法(简称TRBKM)，在利用三角不等式减少冗余计算的基础上，移除一部分点，减少距离计算量，分别将K均值聚类算法、基于三角不等式的K均值聚类算法、TRBKM聚类算法应用于IRIS、Cloud、Abalone数据集，通过分析实验数

6、据证明TRBKM聚类算法的优越性；最后将IDKM和TRBKM算法应用于学生成绩数据集进行分析，最终聚类结果分析指导学生的学习，实现了K均值聚类算法在数据挖掘中的应用。关键词：数据挖掘，聚类分析，K均值，初始点，时间复杂度iK均值聚类算法中初始点与时间复杂度的改进研究THEIMPROVEDRESEARCHOFK-MEANSCLUSTERINGALGORITHMININITIALVALUESANDTIMECOMPLEXITYABSTRACTDataminingdigsthehiddenandvaluableinformati

7、on,whichprovidespeopleeffectivehelp.Clusteringanalysisisanimportantapplicationindatamining.Themainideaofclusteralgorithmistoapplythatthingsofakindcometogether,peopleofamindfallintothesamegroup.Clusteringanalysiscanpartitionandclassifydataobjectsaccordingtosimilar

8、itybetweenobjects,itmakesahighersimilarityamongdatainthesameclusterandalowersimilarityindifferentclusters.Duetoitssimplicityandeffectiveness,k-meansclusteringa