[聚类算法综述.docxVIP

聚类算法综述姓名：谢天娇学校：北京邮电大学学院: 计算机学院2014 年 5 月 30 日摘要聚类算法又称群集分析，常用于将大量数据按照一定规则分为不同类别，其与分类算法的差异在于，聚类算法可在非监督模式下处理数据，不需要人为输入数据标签。聚类算法发展至今约有六十余年，其非监督的特性在如今的大数据时代显示出更大的优势，而与之相应很多学者也致力于研究针对海量数据且精确度更高，语义更明确的聚类算法。笔者在文中从算法分类的角度简述不同种类聚类算法的基础和发展现状。然后就当前使用范围较广的层次法，划分法，密度法，谱聚类各选出一个较为代表性的算法简要分析其算法结构和性能。最后，笔者给出一种谱聚类的matlab实现实例及实验结果。正文一、引言聚类分析最早起源于分类学，初时人们依靠经验一类事件的集合分为若干子集。随着科技的发展，人们将数学工具引入分类学，聚类算法便被细化归入数值分类学领域。后来，信息技术快速发展，新数据的出现呈井喷趋势，其结构的复杂性和内容的多元化尤为聚类提出了新的要求，于是多元分析技术被引入数值分析学，形成了聚类分析学。聚类分析，在英文中是Cluster analysis，又译为群集分析。其作用，简单而言即是非监督式的将大量数据以相似度为基础形成集合。非监督式，即是聚类分析与分类和回归分析的区别所在，聚类不需要人为的输入标签，尽管某些聚类算法需要设定初始划分方法或者根据输入参数确定聚类集合个数，但在分析过程中，算法无须人为输入分类标准。因此，聚类分析在很多时候用于大型数据库的分类预处理，当然聚类分析也常作为独立分析数据的工具。而不同的关于相似度的判断，就形成了不同的聚类算法。聚类算法的分类有很多，从时间上可以分为传统聚类算法和现代聚类算法；从子集元素可以分为软聚类和硬聚类；从对初始状态的处理可以分为结构性聚类和分散性聚类，基于其他标准亦有其他的分类方法，在本文第二节将会给出详细介绍和分析。聚类分析具有广泛的应用领域。对于网络流量的监控和数据挖掘，可以实现舆情分析，获知前所未有的又出现的热点事件。在商业上，市场消费数据的聚类，可以使企业相关人员获知新的消费趋势和市场需求。而在城市规划领域，对于地形地貌或者人口分布的聚类，可以帮助市政规划人员更好的进行城市分区和建设。不同的应用领域，需要聚类的数据差异很大，对于聚类结果也有不同的要求，选择合适的聚类算法才能得到最满意的聚类结果。二、聚类算法分类及国内外发展现状根据中国知网的有哪些信誉好的足球投注网站结果显示，可搜到的最早关于聚类的外国文献出版于1957年，中文文献则是1975年方开泰教授发表于期刊《数学的实践与认识》上的《聚类分析》系列文章。聚类分析的实现步骤大致为特征选择，计算相似度，选择聚类算法，验证判定结果。每一步中选择不同的方法，便是区分聚类算法的原则之一。目前的聚类算法有很多种，考虑到数据类型，相似度计算公式以计算法结构，各种算法已有很多交集。本文中，笔者参考网络文献《聚类算法综述》中该作者的分类方法，将聚类算法按其发展进程大致分为传统聚类算法和现代聚类算法，在此基础上在按其技术细节细分。1. 传统聚类算法传统聚类算法多数属于硬聚类，每个元素只能属于一个集合，在元素特征模糊时聚类结果将受到影响。此外，一些传统聚类算法需要输入子集数量的初始值，这使得在处理大数据时聚类效果不佳。但传统聚类是现代聚类发展的理论基础和实践先驱，因此对于传统聚类的介绍和理解具有重要意义。(1) 层次法层次法的指导思想是对给定待聚类数据集合进行层次化分解。此算法又称为数据类算法，此算法根据一定的链接规则将数据以层次架构分裂或聚合，最终形成聚类结果。从算法的选择上看，层次聚类分为自顶而下的分裂聚类和自下而上的聚合聚类。分裂聚类初始将所有待聚类项看成同一类，然后找出其中与该类中其他项最不相似的类分裂出去形成两类。如此反复执行直到所有项自成一类。聚合聚类初始将所有待聚类项都视为独立的一类，通过联接规则，包括单链接、全连接、类间平均连接，以及采用欧氏距离作为相似度计算的算法，将相似度最高的两个类合并成一个类。如此反复执行直到所有项并入同一个类。BIRCH算法是层次算法中的典型代表算法，其核心是CF（Cluster Feature）和CF树。CF是一个存储了聚类信息的三元组，其中包含了N（待聚类项个数），（N个数据点的线性和），SS（N个数据点的平方和）。和SS分别反映了聚类的质心和聚类的直径大小。CF树有两个参数：分支因子和阈值T。分支因子包括非叶节点CF条目的最大个数和叶节点CF条目的最大个数。这里叶节点看作聚合而成的一个簇。阈值T限定了所有条目的最大半径或直径。BIRCH算法主要有四个阶段。第一阶段扫描待聚类的所有数据项，根据初始阈值T初始化一颗CF树。第二阶段采用聚合思路，通过增加阈值T重建CF树，使其聚合度