数据挖掘-第10章--聚类分析：基本概念和方法.pptVIP

数据挖掘与商务智能范勤勤物流研究中心

第十章聚类分析1聚类分析2划分方法3层次方法4基于密度的方法

聚类分析

聚类分析:基本概念簇：每个子集是一个簇簇中的对象彼此相似与其他簇中的对象不相似典型应用作为一个独立的工具观察数据分布的情况，观察每个簇的特点，集中对特定的某些簇做进一步分析作为其他算法（如分类等）的一个预处理步骤，这些算法再在生成的簇上进行处理聚类分析是一个把数据对象划分成子集的过程，由聚类分析产生的簇的集合称作一个聚类聚类被称为无监督学习，因为没有提供类标号信息4

聚类分析:应用示例Marketing在商业上，聚类能帮助市场分析人员从客户基本库中发现不同的客户群Biology在生物学上，聚类能用于推导植物和动物的分类，对基因进行分类，获得对种群中固有结构的认识Landuse在地球观测数据库中相似地区的确定5

数据挖掘对聚类的典型要求可伸缩性：在大数据集合样本上进行聚类会导致有偏的结果处理不同属性类型的能力：如图、序列、图像等发现任意形状的簇：许多聚类算法基于欧式或曼哈顿距离，球状簇对于确定输入参数的领域知识的要求：对参数设定十分敏感处理噪声数据的能力：对数据敏感，可能导致低质量的聚类结果增量聚类（新数据）和对输入次序不敏感：不能将新数据合并到已有的聚类结构中，对于输入数据的顺序是敏感的聚类高维数据的能力：高维数据有可能是非常稀疏和高度倾斜基于约束的聚类：现实中有很多约束条件可解释性和可用性6

可以用于比较聚类方法的诸方面划分准则分层或不分层相似性度量虽然基于距离的方法常常可以利用最优化技术，但是基于密度或基于连通性的方法常常可以发现任意形状的簇簇的分离性作为簇的主题可能不是互斥的聚类空间子空间聚类发现揭示对象相似性的簇和子空间7

基本聚类方法概述划分方法(Partitioningapproach)基本思想：给定一个n个样本的数据库，划分方法将数据划分为k个划分（k=n），每个划分表示一个簇，同时满足：（1）每个簇至少包含一个样本；（2）每个样本必须属于且仅属于一个层次方法(Hierarchicalapproach)创建给定数据对象集的层次分解8基于密度的方法对给定簇中的每个数据点，在给定半径的领域中必须至少包含最少数目的点

9基本聚类方法概述方法一般特点划分方法发现球形互斥的簇基于距离可以用均值或中心点等代表簇中心对中小规模数据集有效层次方法聚类是一个层次分解（即多层）不能纠正错误的合并或划分可以集成其他技术，如微聚类或考虑对象“连接”基于密度的方法可以发现任意形状的簇簇是对象空间中被低密度区域分隔的稠密区域簇密度：每个点的“邻域”内必须具有最少个数的点可能过滤离群点

划分方法

划分方法给定一个n个对象或元组的数据库，一个划分方法构建数据的k个划分，每个划分表示一个簇，并且k=n。每个组至少包含一个对象每个对象属于且仅属于一个组簇的表示k-平均算法（由簇的平均值来代表整个簇）k中心点算法（由处于簇的中心区域的某个值代表整个簇）划分准则同一个聚类中的对象尽可能的接近或相关，不同聚类中的对象尽可能的远离或不同11

K-均值:一种基于形心的技术假设数据集D包含n个欧式空间中的对象，划分把D中的对象分配到k个簇中。簇Ci的质量可以用簇内变差度量，它是Ci中所有对象和形心ci之间的误差的平方和，定义为12

K-均值:一种基于形心的技术算法K-均值。用于划分的k–均值算法，其中每个簇的中心都用簇中所有对象的均值来表示方法从D中任意选择k个对象作为初始簇中心Repeat根据簇中对象的均值，将每个对象分配到最相似的簇更新簇均值，即重新计算每个簇中对象的均值Until不再发生变化输入k：簇的数目D：包含n个对象的数据集13

K-均值:例子-步骤114k1k2k3XY随机选择3个簇中心

K-均值:例子-步骤215k1k2k3XY分配每个点到最近的簇中心

K-均值:例子-步骤316XY移动每个簇中心到每个簇的平均位置k1k2k2k1k3k3

K-均值:例子-步骤417XY把对象重新分布到离簇中心最近的簇中k1k2k3

K-均值:例子-步骤4…18XYA:threepointswithanimationk1k3k2

K-均值:例子-步骤4b19XY重新计算簇的均值k1k3k2

K-均值:例子-步骤520XY把簇的中心移到簇的均值k2k1k3

K-均值:缺点21是局部最优,不是全局最优要求用户必须事先给出要生成的簇的数目,选择初始划分的最佳方向、更新分区和停止准则不适合发现大小很不相同的簇或具有凹状的簇算法只有在簇的平均值被定义的情况下才能使用,这不适合涉及有类属性的数据对噪音和异常点非常敏感孤立点（极大值）的存在,会大幅度扭曲数据的分布

K-中心点:一种基于代表对象的