K均值文献阅读报告.doc_第1页
K均值文献阅读报告.doc_第2页
K均值文献阅读报告.doc_第3页
K均值文献阅读报告.doc_第4页
K均值文献阅读报告.doc_第5页
已阅读5页,还剩12页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

模式识别文献阅读报告及心得体会 学生姓名: 刘凯 班 学 号: 075114 20111001740 08 指导老师: 马丽 在过去的三个星期里,我读了5篇文献,分类算法有两大类,一是聚类算法,二是有监督的分类算法。我比较喜欢前者,因为我觉得聚类算法更适合于对很多未知数据集进行数据信息的挖掘,有一种“自动化”处理的意味。作为最经典的算法K均值算法,就是本文所要讨论的东西。我读的这些文献中,所有算法都是针对传统K均值算法进行优化后的的结果。5篇文献都来源于中国知网,我把它们进行排序分类,前两篇主要讨论传统k均值算法易陷入局部最优值的改进,后三篇都是对初始类心的优化算法,我发现文献之间是有联系的,为此,针对同一个问题的改进,后一篇的文章基本上都优于前一篇。 第一篇:基于遗传算法的K均值聚类分析1.摘要:传统的k均值算法对初始聚类中心敏感,聚类结果随不同的初始输入而波动,容易陷入局部最优值。于是本文讲k均值算法的局部寻优能力与遗传算法的全局寻优能力相结合,在自适应交叉概率和变异概率的遗传算法中引入k均值操作,以克服传统k均值算法的局部性和对初始类心的敏感性。2.算法核心思想:遗传算法是一种模拟生物在自然环境中的遗传和进化过程而形成的自适应全局优化搜索算法。其最优解的搜索过程模仿了生物的进化过程,使用遗传操作数作用于群体进行遗传操作,进而得到新一代群体。本质上是一种求解问题的高效并行全局搜索算法。它能在搜索过程中自动获取和积累有关搜索空间的知识,并自适应地控制搜索过程。作者想在种群进化中引入k均值操作,同时为了避免早熟现象,在种群中采用自适应方法动态调节交叉概率和变异概率,使其能随适应度自动改变。3.数据实验与分析:文章中实验数据主要来源于 /pub/machine-learning-databases/,数据分为iris、glass、wine.其中iris有4个属性,glass有9个属性,wine有13个属性。实验的种群大小为30,最大迭代次数100,重复20次。结果如下:从实验中可以看出,传统k均值算法不一定每次都能达到最优解,而基于遗传的k均值算法每次都可以;而且后者平均迭代次数也较少。4.总结:这种算法克服了传统的k均值算法对初始类心敏感的问题,并且可以得到最优解。5.我的评价:从实验结果来看,该算法确实达到了预期目标,但是美中不足的是作者给出的实验数据集的数据量太少了,种群大小才30,那么对于大批量数据结论是否还成立呢?从这个意义上讲,该算法优越性还不能完全证实。6.文献信息:文章编号:1000-3428(2008)20-0200-03文献标识码:A中图分类号:TP301作者:赖玉霞,刘建平,杨国兴。 第二篇:基于粒子群的K均值算法1.摘要:粒子群优化算法(PSO)是一种源于对鸟类捕食行为的研究而发明的进化技术,同上一篇遗传算法相比,PSO不但具有全局寻优能力,通过参数调整,PSO还具有较强的局部寻优能力,并且PSO算法更为简单,适合于计算机编程处理。作者发现,在大多数情况下,本算法比遗传算法更快收敛于最优解,而且可以避免完全随机寻优的退化现象。2.算法核心思想:粒子群算法由美国人Kemedy和Eberhar提出,粒子通过不断调整自己的位置X来搜索新解,每个粒子都能记住自己搜索到的最好解Pid,以及整个粒子群经历过的最好位置Pgd,每个粒子都有一个速度V且Vid是粒子在第d维上的速度,其余参数类推。具体算法可描述为:初始化粒子群,随机设定各粒子初始位置X和速度V;然后计算各粒子适应度值,将该粒子适应度值与Pid、Pgd的适应度值作比较,以最优值更新Pid、Pgd;由上述公式调整粒子速度和位置;直到达到条件或最大迭代次数。3. 数据实验与分析:作者取了400个二维点,比较了三种算法(基于遗传的k均值,传统k均值和粒子k均值算法),取样规模均为20,迭代30次。结果如下:分析知,传统k均值算法对初始类心敏感且易陷入局部最小值,遗传算法优于传统算法,但是样本数量大时也会陷入最小值,而粒子群算法具有较强的全局寻优能力,而且每次都能收敛到最优点。4.总结:理论与实践表明,基于粒子群的k均值算法能克服传统算法存在的问题,全局寻优秀能力优于基于遗传的k均值算法,具有较快的收敛速度。5.我的评价:此算法效果很好,但是有一大缺陷,那就是数据计算量太大,正如作者所言,每个粒子的速度V有k*d维,位置X也是k*d维,更新起来计算量是很大的。6.文献信息:文章编号:1000-6788(2005)06-0054-05文献标识码:A中图分类号:TP301.6作者:上海交大管理学院 刘靖明,韩丽川,侯立文。第三篇:初始聚类中心优化K均值算法1.摘要:传统的k均值算法对初始类心敏感,聚类结果随不同的初始输入而波动。作者提出的这种基于密度选取初始类心的算法就是为了解决上述问题。该算法试图寻找尽可能体现数据实际分布的初始类心。2. 算法核心思想:一般在一个数据空间中,高密度的数据对象被低密度的数据对象区域所分割,通常认为处于低密度区域的点为噪声,为了避免初始类心取到噪声点,该算法选取相距最远的k个处于高密度区的点作为初始类心。具体算法思路有点类似于用最小最大距离法选取初始类心过程,如图:原理很简单,但是值得注意的是作者对密度值定义:通过计算任一点到周围点的距离,设定一个常数C,取前C个距离最近的点划分为一个区域,其最大距离作为密度值S。显然,按照这种定义,S越小密度越大。3. 数据实验与分析:作者选用UCI数据库的Iris、balance scale、New-thyroid、Haberman和Wine五组数据。结果如下:4. 从实验结果可以看出,对于前4组数据,改进后的算法的准确率均高于传统k均值算法,但是第5组数据结果出现了反差。作者的解释是,Wine共有178个数据,分3类,每个数据有14个属性,应用决策树分析发现Alcohol(属性1)、Flavanoids(属性8)和Color-intensity(属性11)最为重要,单三者的值很小,波动的范围也很小。而对分类贡献不大的Proline(属性13)的取值范围为2781680,因此在计算距离过程中Proline起到了绝对作用,使得相距很远的点不能很好地代表数据实际分布。4.总结:只要数据的各个属性可以很好地对分类做出贡献(即重要属性在数值上占主导地位),该算法在很多情况下可以消除传统k均值算法对初始类心的敏感性。5.我的评价:此算法缺陷是当数据的次要属性值明显大于重要属性值时,聚类效果并不好。6.文献信息:文章编号:1000-3428(2007)(03)-0065-02文献标识码:A中图分类号:TP39作者:袁方,周志勇,宋鑫。 第四篇:基于初始类心优的K均值算法1.摘要:本算法同上一篇算法出发点相同,也是基于密度的初始聚类中心选取方法,所不同之处是作者在该算法中特别添加了对孤立点的特殊处理,减少了运算迭代次数。2.算法核心思想:先介绍作者定义的密度:对于任意一点,设置每个参数R作为其半径,然后统计距离该点距离在R范围内的所有点数作为密度值Di,显然,Di越大则越密集。设置一个密度闸值D,据此将所有数据分为两类,密度大的放到数据集Z中,密度小的当作孤立点放到数据集S中。取Z中密度最大的点作为第一个类心z1,再设置合适的距离值d,在Z求所有点到z1的距离,挑选距离值大于d且密度最大的点作为z2.类似于上一篇文献中的方式可以获得剩余的k-2个初始类心(注意每求一个类心时要兼顾该点到已确定的所有类心的距离和最高密度要求)。进而对Z中所有点进行k均值操作,迭代结束后把S中的孤立点进行归类即可。3.数据实验与分析:作者进行了三组实验,随机生成三组二维数据,分别含200个、1200个和1600个,且孤立点占10%15%。用“.”“。”“+”表示不同的类别。实验一:图2a、2b分别表示不同的初始类心、迭代5次的传统k均值分类结果,图2c表示该算法迭代2次的结果如下:实验二:图3a、3b分别表示不同的初始类心、迭代8次的传统k均值分类结果,图3c表示该算法迭代2次的结果如下:实验三:图4a、4b分别表示不同的初始类心、迭代14次的传统k均值分类结果,图4c表示该算法迭代5次的结果如下: 从实验结果看出,不同的初始类心使传统k均值算法聚类结果不同,而作者提出的算法用更少的迭代次数和时间却得到了较好的聚类效果,且结果是唯一的。4.总结:此算法对孤立点采取最后处理的方式,同时初始类心是基于密度而优化选取的,成功解决了传统k均值算法对初始类心和孤立点敏感度双重问题。5.我的评价:该算法中孤立点不参与迭代循环,所以特别适合于处理噪声大量存在的数据集,和上一篇文献相比,此算法更为先进。但是,正如作者所言此算法设置了很多参数,引入了太多的主观分析。6.文献信息:文章编号:1007-130X(2010)10-0105-03文献标识码:A中图分类号:TP18作者:王赛芳,戴芳,王万斌,张晓宇。第五篇:基于样本空间分布密度的初始聚类中心优化K均值算法1. 摘要:本文算法也是初始类心优化问题,利用数据集样本的空间分布信息定义数据对象的密度,并根据整个数据集的空间信息定义了书记对象的领域,在此基础上选择密集区且相距较远的数据对象作为初始类心,以提高k均值算法的准确性和收敛速度。2. 算法核心思想:此算法充分利用样本空间信息,根据数据集中的数据自然分布状况,定义样本的密度和邻域,密度越小说明该数据对象周围样本分布密集。为此首先选出密度最小的数据对象,以该数据对象为中心,将整个数据集划分为不同的环形区域,即邻域。选出数据对象最多的前k个邻域,再从这k个邻域中选择周围数据最密集的数据对象作为初始类心。这样一来所选的类心不仅处于密集区,而且各类心之间距离较远,只要适当调节邻域的半径就可以最合适的初始聚类中心。3. 数据实验与分析:作者做了两个实验,一个是基于UCI数据集,另一个是随机生成的人工模拟数据集,我将重点讨论后者。试验中随机生成分别含0.5%、10%、15%、20%、25%、30%、35%、40%不同比例噪声的人工模拟数据集对算法进行测试(数据包分为三类,每类含有120个二维样本,均符合正态分布)。结果如下: 可以看出,基于样本空间分布密度的初始类心优化k均值算法收敛时对应的准则函数值很小,因而有良好的聚类效果,不仅准确性高,而且对噪声数据有很强的抗干扰能力。4.总结:基于样本空间分布密度的初始类心优化k均值算法有良好的聚类效果,有效解决了初始类心优化选择问题。5.我的评价:事实上这种算法比上面两篇关于同一问题(优化初始类心)的算法更为优异,本质在于设置的参数少,更具有客观性。但此算法付出了时间上的牺牲,可以从时间表中看出,相对传统k均值算法而言,运行时间更长。6.文献信息:文章编号:1001-3695(2012)03-0888-05文献标识码:A中图分类号:TP301.6 作者:谢娟英,郭文娟,谢维信,高新波。六、本门课程心得体会平心而论,马老师教学认真,对

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论