第8章聚类分析.

第8章聚类分析数据挖掘原理与SPSSClementine应用宝典元昌安主编邓松李文敬刘海涛编著电子工业出版社第8章聚类分析由NordriDesign提供章聚类分析主要内容•聚类分析原理•聚类分析常用算法分类•划分聚类方法•层次聚类方法•基于密度的聚类方法•基于网格的聚类方法•基于模型的聚类方法•高维数据的聚类方法•模糊聚类FCM•应用实例分析第8章聚类分析8.1.1聚类分析介绍•聚类就是按照事物的某些属性，把事物聚集成类，使类间的相似性尽可能小，类内相似性尽可能大。•数据挖掘对聚类的典型要求如下：–可伸缩性–处理不同类型属性的能力–发现任意形状的聚类–用于决定输入参数的领域知识最小化–处理噪声数据的能力第8章聚类分析8.1.2聚类分析中的数据类型•数据矩阵：用m个变量（也称为属性）来表现n个对象•相异度矩阵：存储n个对象两两之间的近似度，通常用一个维的矩阵表示111212122212mmnnnmxxxxxxxxx02,103,13,20,1,20ddddndn第8章聚类分析8.1.3区间标度变量•计算均值绝对偏差•计算标准化的度量值–欧几里德距离–曼哈顿距离–明考斯基距离第8章聚类分析8.1.4二元变量•简单匹配系数•Jaccard系数•Rao系数第8章聚类分析8.1.5分类型、序数型变量•分类变量•序数型变量第8章聚类分析8.1.6向量对象•夹角余弦•相关系数第8章聚类分析8.2聚类分析常用算法分类•划分方法•层次方法•基于密度的方法•基于网格的方法•基于模型的方法•高维数据的聚类方法•模糊聚类FCM第8章聚类分析8.3划分聚类方法•k-meansk-means算法是基于质心的算法。k-means算法以k为参数，把n个对象分为k个簇，以使簇内具有较高的相似度，而簇间的相似度最低。相似度的计算根据一个簇中对象的平均值（被看作簇的重心）来进行。Step1任意选择k个对象作为初始的簇中心；Step2repeat；Step3根据与每个中心的距离，将每个对象赋给最近的簇；Step4重新计算每个簇的平均值；Step5until不再发生变化。第8章聚类分析8.3划分聚类方法•k-medoids不采用簇中对象的平均值作为参照点，可以选用簇中位置最中心的对象，即medoid。这样划分方法仍然是基于最小化所有对象与其参照点之间的相异度之和的原则来执行的。Step1随机选择k个对象作为初始的代表对象；Step2repeat；Step3指派每个剩余的对象给离它最近的代表对象所代表的簇；Step4随意地选择一个非代表对象；Step5计算用代替的总代价S；Step6如果，则用替换，形成新的k个代表对象的集合；Step7until不发生变化。第8章聚类分析8.4层次聚类方法•8.4.1凝聚的和分裂的层次聚类•8.4.2BIRCH：平衡迭代归约和聚类•8.4.3ROCK：分类属性层次聚类算法•8.4.4CURE：使用代表点聚类方法•8.4.5Chameleon：动态建模层次聚类第8章聚类分析8.4.1凝聚的和分裂的层次聚类•凝聚的方法–首先将每个对象作为单独的一个原子簇–然后相继地合并相近的对象或原子簇–直到所有的原子簇合并为一个（层次的最上层），或者达到一个终止条件•分裂的方法–首先将所有的对象置于一个簇中–在迭代的每一步中，一个簇被分裂为更小的簇，–直到最终每个对象在单独的一个簇中，或者达到一个终止条件第8章聚类分析8.4.1凝聚的和分裂的层次聚类abcdfabdefcdefabcdef初始步骤1步骤2步骤3步骤4凝聚的ede步骤4步骤3步骤2步骤1初始分裂的第8章聚类分析8.4.2BIRCH：平衡迭代归约和聚类•BIRCH通过聚类特征（ClusteringFeature，CF）对簇的信息进行汇总描述，然后对簇进行聚类。•BIRCH算法的主要目标是使I/0时间尽可能小，–原因在于大型数据集通常不能完全装入内存中。BIRCH算法通过把聚类分为多个阶段来达到此目的–首先通过构建CF-树对原数据集进行预聚类–在前面预聚类的基础上进行聚类第8章聚类分析8.4.2BIRCH：平衡迭代归约和聚类1CF……2CFnCF11CF……12CF1kCF根层第一层…………………………CF树的结构第8章聚类分析8.4.2BIRCH：平衡迭代归约和聚类BIRCH共包含四个阶段：•预聚类阶段：扫描整个数据库，构建初始聚类特征树，该树保存在内存中，用简洁的汇总信息或者叶子节点中的子聚类来代表数据点的密集区域。•（可选阶段）重新扫描叶子节点项，来构建一个更小的CF-树。•采用别的聚类算法，对CF-tree的叶子节点进行聚类。•（可选阶段）把前一个阶段中找到的聚类的质心，用作种子来创建最终的聚类。其它数据点根据到这些种子所代表聚类的远近来重新分配到各个聚类中。第8章聚类分析8.4.3ROCK：分类属性层次聚类算法•分类属性的层次聚类算法针对具有分类属性的数据使用了链接的概念。–对于聚类包含布尔或分类属性的数据，传统聚类算法使用距离函数。–实验表明对分类数据聚类时，这些距离度量不能产生高质量的簇。–大多数聚类算法在进行聚类时只估计点与点之间的相似度；也就是说，在每一步中那些最相似的点合并到一个簇中。这种局部方法很容易导致错误。第8章聚类分析8.4.3ROCK：分类属性层次聚类算法•ROCK算法采用一种比较全局的观点，通过考虑成对点的邻域情况进行聚类。如果两个相似的点同时具有相似的邻域，那么这两个点可能属于同一个簇而合并。–ROCK算法使用一个相似度阈值和共享邻域的概念从一个给定的数据相似度矩阵中首先构建一个稀疏图。–在这个稀疏图上执行凝聚层次聚类。使用一个优度度量评价聚类。采用随机抽样处理大规模的数据集。–ROCK算法在最坏情况下的时间复杂度为，其中和分别是近邻数目的最大值和平均值，是对象的个数。22logmaOnnmmnn第8章聚类分析8.4.4CURE：使用代表点聚类方法•CURE选择了位于基于质心和基于代表对象方法之间的中间策略。–不用单个质心或对象来代表一个簇–而是选择数据空间中固定数目的具有代表性的点。•一个簇的代表点通过如下方式产生：–首先选择簇中分散的对象–然后根据一个特定的分数或收缩因子向簇中心收缩或移动它们–在算法的每一步，有最近距离的代表点对（每个点来自于一个不同的簇）的两个簇被合并•CURE解决了偏好球形和相似大小的问题，在处理孤立点上也更加健壮。第8章聚类分析8.4.4CURE：使用代表点聚类方法CURE步骤如下：•源数据对象中抽取一个随机样本S；•将样本S分割为一组划分；•对每个划分局部地聚类；•通过随机取样剔除孤立点。如果一个簇增长的太慢，就去掉它；•对局部的簇进行聚类。落在每个新形成的簇中的代表点根据用户定义的一个收缩因子α收缩或向簇中心移动。这些点代表了簇的形状；•用相应的簇标签来标记数据。第8章聚类分析8.4.4CURE：使用代表点聚类方法•CURE算法特点：–CURE算法可以适应非球形的几何形状–算法对孤立点的处理更加健壮–而且能够识别非球形和大小变化较大的簇；–CURE算法的复杂性为。•CURE从源数据对象中抽取一个随机样本S，基于对此样本的划分进行聚类，如果抽取的样本发生倾斜，则会严重影响聚类结果第8章聚类分析8.4.5Chameleon：动态建模层次聚类•Chameleon算法的思想是：–首先通过一个图划分算法将数据对象聚类为大量相对较小的子聚类，–然后用一个凝聚的层次聚类算法通过反复地合并子类来找到真正的结果簇。•Chameleon既考虑了互连性，又考虑了簇间的近似度，特别是簇内部的特征，来确定最相似的子簇。–它不依赖于一个静态的，用户提供的模型，能够自动地适应被合并的簇的内部特征。第8章聚类分析8.4.5Chameleon：动态建模层次聚类•与CURE和DBSCAN相比：–Chameleon在发现高质量的任意形状的聚类方面有更强的能力–但是在最坏的情况下，高维数据的处理代价可能对n个对象需要的时间2O(n)第8章聚类分析8.4.5Chameleon：动态建模层次聚类•与CURE和DBSCAN相比：–Chameleon在发现高质量的任意形状的聚类方面有更强的能力–但是在最坏的情况下，高维数据的处理代价可能对n个对象需要的时间2O(n)第8章聚类分析8.5基于密度的聚类方法•8.5.1DBSCAN：高密度连通区域聚类•8.5.2OPTICS：点排序识别聚类结构•8.5.3DENCLUE：密度分布函数的聚类第8章聚类分析8.5.1DBSCAN：高密度连通区域聚类•一个给定对象周围半径内的区域称为该对象的–邻域•DBSCAN算法通过检查数据库中每个点的ε-邻域来寻找聚类。–如果一个点p的ε-邻域包含多于MinPts个点，则创建一个以p作为核心对象的新簇。–然后，DBSCAN算法迭代地寻找从这些核心对象直接密度可达的对象，这个过程可能涉及一些密度可达簇的合并。当没有新的点可以被添加到任何簇时，该过程结束。第8章聚类分析8.5.1DBSCAN：高密度连通区域聚类DBSCAN算法步骤：•Step1读取D中任意一个未分类的对象p；•Step2检索出与p的距离不大于Eps的所有对象；•Step3如果（即p为非核心对象），则将p标记为噪声，并执行Step1；•Step4否则（即p为核心对象），给中的所有对象打上一个新的类标签newid，然后将这些对象压入堆栈的Seeds中；•Step5让CurrentObject=Seeds.top；然后检索属于的所有对象；如果，则剔除已经打上标记的对象，将余下的未分类对象打上类标签newid，然后压入堆栈；•Step6Seeds.pop，判断Seeds是否为空，是，则执行Step1，否则执行Step5。Neps(p)Neps(p)MinPtsNeps(p)Neps(CurrentObject)Neps(CurrentObject)MinPts第8章聚类分析8.5.1DBSCAN：高密度连通区域聚类•DBSCAN算法不仅可以发现任意形状的聚类，对数据输入顺序不敏感，并且具有处理异常数据（噪声）的能力。•DBSCAN算法对用户定义的参数是敏感的，而参数的恰当选择是需要有相关经验的第8章聚类分析8.5.2OPTICS：点排序识别聚类结构•对于真实的，高维的数据集合而言，参数的设置通常是依靠经验，难以确定。•绝大多数算法对参数值是非常敏感的：设置的细微不同可能导致差别很大的聚类结果。•OPTICS算法通过对象排序识别聚类结构。–OPTICS没有显式地产生一个数据集合簇，它为自动和交互的聚类分析计算一个簇排序。–这个次序代表了数据的基于密度的聚类结构。第8章聚类分析8.5.3DENCLUE：密度分布函数的聚类•DENCLUE是对k-means聚类算法的一个推广：–DENCLUE算法得到的是全局最优划分。•DENCLUE主要基于：–每个数据点的影响可以用一个数学函数来形式化地模拟，它描述了一个数据点在邻域内的影响，被称为影响函数；–数据空间的整体密度可以被模型化为所有数据点的影响函数的总和；–然后聚类可以通过确定密度吸引点来得到，这里的密度吸引点是全局密度函数的局部最大。第8章聚类分析8.5.3DENCLUE：密度分布函数的聚类DENCLUE算法步骤：•Step1对数据点占据的空间推导密度函数；•Step2识别局部最大点；•Step3通过沿密度增长最大的方向移动，将每个点关联到一个密度吸引点；•Step4定义与特定的密度吸引点相关联的点构成的簇；•Step5丢弃密度吸引点的密度小于用户指定阈值ξ的簇；•Step6合并通过密度大于或等于ξ的点路径连接的簇。第8章聚类分析8.6基于网格的聚类方法•8.6.1STING：统计信息网格聚类•8.6.2WaveCluster：利用小波变换聚类第8章聚类分析8.6.1STING：统计信息网格聚类•STING是一种基于网格的多分辨率聚类技术，它将空间区