数据挖掘导论--第8章-聚类-2017-v3

第8章聚类分析:基本概念和算法8.1概述8.1.1什么是聚类分析8.1.3不同的簇类型补充聚类算法的分类8.2K-均值聚类算法8.2.1基本K均值算法基本K均值算法存在的问题8.3凝聚层次聚类8.3.1基本的凝聚层次聚类算法8.3.2如何计算簇之间的邻近性8.3.4层次聚类的主要问题8.4DBSCAN8.1概述8.1概述8.1.1什么是聚类分析8.1.3不同的簇类型补充聚类算法的分类8.2K-均值聚类算法8.2.1基本K均值算法基本K均值算法存在的问题8.3凝聚层次聚类8.3.1基本的凝聚层次聚类算法8.3.2如何计算簇之间的邻近性8.3.4层次聚类的主要问题8.4DBSCAN什么是聚类分析聚类分析仅根据在数据中发现的描述对象及其关系的信息，将数据对象分组。其目标是，组内的对象之间是相似的（相关的），而不同的组中的对象是不同的（不相关的）。组内的相似性（同质性）越大，组间差别越大，聚类就越好。Inter-clusterdistancesaremaximizedIntra-clusterdistancesareminimized聚类分析的应用旨在理解生物学：分类、现类似功能的基因组信息检索：将搜索结果分成若干簇气候：分析极地和海洋大气压力模式医学和心理学：识别不同类型的抑郁症商业：将顾客划分成若干组旨在实用汇总数据压缩数据发现最近邻ClusteringprecipitationinAustralia簇（Cluster）的定义是不精确的Howmanyclusters?FourClustersTwoClustersSixClusters8.1概述8.1.1什么是聚类分析8.1.3不同的簇类型补充聚类算法的分类8.2K-均值聚类算法8.2.1基本K均值算法基本K均值算法存在的问题8.3凝聚层次聚类8.3.1基本的凝聚层次聚类算法8.3.2如何计算簇之间的邻近性8.3.4层次聚类的主要问题8.4DBSCAN不同的簇类型Well-separatedclusters（明显分离的簇）Center-basedclusters（基于中心的簇）Contiguousclusters（基于邻近的簇）Density-basedclusters（基于密度的簇）PropertyorConceptual（概念簇）明显分离的簇:簇是对象的集合，不同组中的任意两点之间的距离都大于组内任意两点之间的距离。基于原型的簇（基于中心的簇）簇是对象的集合，其中每个对象到定义该簇的原型的距离比到其他簇的原型的距离更近（或更加相似）。对于具有连续属性的数据，簇的原型通常是质心，即簇中所有点的平均值。当质心没有意义是，原型通常是中心点，即簇中最有代表性的点。这种簇倾向于呈球状。基于图的（基于邻近的簇）：如果数据用图表示，其中节点是对象，而边代表对象之间的联系，则簇可以定义为连通分支，即互相连通但不与组外对象连通的对象组。基于图的簇一个重要例子就是基于临近的簇，其中两个对象是相连的，仅当他们的距离在指定的范围之内。也就是说，每个对象到该簇某个对象的距离比不同簇中的任意点的距离更近。基于密度的：簇是对象的稠密区域，被低密度的区域环绕。当簇不规则或互相盘绕，并且有噪声和离群点时，常常使用基于密度的簇定义。不同的簇类型8.1概述8.1.1什么是聚类分析8.1.3不同的簇类型补充聚类算法的分类8.2K-均值聚类算法8.2.1基本K均值算法基本K均值算法存在的问题8.3凝聚层次聚类8.3.1基本的凝聚层次聚类算法8.3.2如何计算簇之间的邻近性8.3.4层次聚类的主要问题8.4DBSCAN聚类算法的分类大体上，主要的聚类算法可以划分为如下几类：划分方法层次方法基于密度的方法基于网格的方法聚类算法的分类1.划分方法（partitionmethod）给定一个有N个元组或者记录的数据集，划分方法将构造K个分组，每一个分组就代表一个聚类，KN。而且这K分组满足下列条件：1）每一个分组至少包含一个数据记录；2）每一个数据记录隶属于且仅属于一个分组；对于给定的K，算法首先给出一个初始的分组方法，以后通过反复迭代的方法改变分组，使得每一次改进之后分组方案都较前一次好，所谓的“好”的标准就是同一分组的记录越相似越好，而不同分组中的记录则越相异越好。最著名与最常用的划分方法是k-均值方法和k-中心点方法。聚类算法的分类2.基于层次的方法（hierarchicalmethod）一个层次的聚类方法是将数据对象组成一棵聚类的树。根据层次分解是自底向上还是自顶向下形成，层次的聚类方法可以进一步分为聚合式层次聚类（agglomerative）和分裂式层次聚类（divisive）。聚合式的层次聚类，其层次过程的方向是自底向上的。将样本集合中的每个对象作为一个初始簇，然后将最近的两个簇合并，组成新的簇，再将这个新簇与剩余的簇中最近的合并，这种合并过程需要反复进行，直到所有的对象最终被聚到一个簇中。分裂式的层次聚类，其层次过程的方向是自顶向下的，最初先将有关对象放到一个簇中，然后将这个簇分裂，分裂的原则是使两个子簇之间的聚类尽可能的远，分裂的过程也反复进行，直到某个终止条件被满足时结束。不论是合并还是分解的过程，都会产生树状结构，树的叶子节点对应各个独立的对象，顶点对应一个包含了所有对象的簇。常见的层次聚类算法有：BIRCH算法、CURE算法、ROCK算法等。聚类算法的分类3.基于密度的方法（density-basedmethod）基于密度的方法与其他方法的一个最根本的区别是：它不是基于各种各样的距离，而是基于密度的，它将簇看做是数据空间中被低密度区域分割开的高密度对象区域，这种方法的优势是善于发现空间数据库中任意形状的聚类。基于密度的聚类根据空间密度的差别，把具有相似密度的点作为聚类。由于密度是一个局部概念，这类算法又称为局部聚类（LocalClustering）。一般情况下，基于密度的聚类只扫描一次数据库，故又称为是单次扫描聚类（SingleScanClustering）。基于密度的聚类方法主要：DBSCAN算法、DENCLUE算法。聚类算法的分类4.基于网格的方法（density-basedmethod）基于网格的方法采用一个多分辨率的网格数据结构。它将数据空间量化，并将其划分为有限数目的网格单元，所有的聚类操作都在网格上进行。该算法的优势在于处理速度快，处理时间与数据对象的数目无关。基于网格的聚类方法有STING算法和CLIQUE算法等。8.2K-均值聚类算法K-meansClusteringK-meansClusteringK均值是基于原型的、划分的聚类技术。典型的基于原型的、划分的聚类算法：K均值、K中心点。K均值用质心定义原型，其中质心是一组点的均值。K均值聚类用于n维连续空间中的对象。它试图发现用户指定个数（K）的簇（由质心代表）。K中心点使用中心点定义原型，其中中心点是一组点中最有代表性的点。K中心点聚类可以用于广泛的数据，因为它只需要对象之间的邻近性度量。尽管质心几乎从来不对应实际的数据点，但是根据定义，中心点必须是一个实际的数据点。8.1概述8.1.1什么是聚类分析8.1.3不同的簇类型补充聚类算法的分类8.2K-均值聚类算法8.2.1基本K均值算法基本K均值算法存在的问题8.3凝聚层次聚类8.3.1基本的凝聚层次聚类算法8.3.2如何计算簇之间的邻近性8.3.4层次聚类的主要问题8.4DBSCAN基本K均值算法K均值的算法步骤：首先选择K个初始质心，其中K是用户指定的参数，即所期望的簇的个数。每个点指派到最近的质心，而指派到一个质心的点集为一个簇。然后，根据指派到簇的点，更新每个簇的质心。重复指派和更新步骤，直到簇不发生变化，或等价的，直到质心不发生变化。算法流程如下：K-meansClustering:Example-2-1.5-1-0.500.511.5200.511.522.53xyIteration1-2-1.5-1-0.500.511.5200.511.522.53xyIteration2-2-1.5-1-0.500.511.5200.511.522.53xyIteration3-2-1.5-1-0.500.511.5200.511.522.53xyIteration4-2-1.5-1-0.500.511.5200.511.522.53xyIteration5-2-1.5-1-0.500.511.5200.511.522.53xyIteration6K-meansClustering:Example-2-1.5-1-0.500.511.5200.511.522.53xyIteration1-2-1.5-1-0.500.511.5200.511.522.53xyIteration2-2-1.5-1-0.500.511.5200.511.522.53xyIteration3-2-1.5-1-0.500.511.5200.511.522.53xyIteration4-2-1.5-1-0.500.511.5200.511.522.53xyIteration5-2-1.5-1-0.500.511.5200.511.522.53xyIteration6K-均值聚类的距离度量与目标函数虑邻近度量为欧几里得距离的数据,度量聚类质量最常用的是误差的平方和(SumofSquaredError,SSE)对于每个点,其误差是到最近质心的距离为了得到SSE,我们对每个点的误差求平方和x是簇Ci的点,ci是簇Ci的代表点可以证明ci对应于簇的质心(均值)给定两个聚类,我们可以选择具有最小SSE的聚类KiCxiixcdistSSE12),(x1iiCimcx其它距离度量K-means也可以用于非欧氏空间数据例,文档数据通常,文档用余弦相似性度量距离是相异性度量,而余弦是相似性度量质心仍然用均值最近的质心是最相似的质心目标:最大化簇中文档与簇的质心的相似性总凝聚度（totalcohesion）1x(,)iKiiCTotalcohesioncosinexc其它距离度量K均值：邻近度、质心和目标函数的常见选择邻近度函数质心目标函数曼哈顿距离（L1）中位数最小化对象到其簇质心的L1距离和平方欧几里得距离均值最小化对象到其簇质心的L2距离的平方和余弦均值最大化对象与其簇质心的余弦相似度和Bregman散度均值最小化对象到其簇质心的Bregman散度和8.1概述8.1.1什么是聚类分析8.1.3不同的簇类型补充聚类算法的分类8.2K-均值聚类算法8.2.1基本K均值算法基本K均值算法存在的问题8.3凝聚层次聚类8.3.1基本的凝聚层次聚类算法8.3.2如何计算簇之间的邻近性8.3.4层次聚类的主要问题8.4DBSCAN基本K均值算法存在的问题不同的初始质心将收敛得到不同的目标函数，可能只能达到局部最优解。随机选取初始质心，拙劣的初始质心，可能导致很糟糕的聚类结果。可能产生空簇容易受到离群点的影响不能处理非球形簇、不同尺寸和不同密度的簇。不同的初始质心导致不同的SSE-2-1.5-1-0.500.511.5200.511.522.53xy-2-1.5-1-0.500.511.5200.511.522.53xySub-optimalClustering-2-1.5-1-0.500.511.5200.511.522.53xyOptimalClusteringOriginalPoints基本K均值算法存在的问题拙劣的初始质心-2-1.5-1-0.500.511.5200.511.522.53xyIteration1-2-1.5-1-0.500.511.5200.511.522.53xyIteration2-2-1.5-1-0.500.511.5200.511.522.53xyIteration3-2-1.5-1-0.500.511.5200.5