1、第8章 聚类分析数据挖掘原理与数据挖掘原理与SPSS Clementine应用宝典应用宝典 元昌安元昌安 主编主编 邓松李文敬刘海涛编著邓松李文敬刘海涛编著 电子工业出版社电子工业出版社第8章 聚类分析由NordriDesign提供第8章 聚类分析主要内容聚类分析原理聚类分析常用算法分类划分聚类方法层次聚类方法基于密度的聚类方法基于网格的聚类方法基于模型的聚类方法高维数据的聚类方法模糊聚类FCM应用实例分析第8章 聚类分析8.1.1聚类分析介绍聚类就是按照事物的某些属性，把事物聚集成类，使类间的相似性尽可能小，类内相似性尽可能大。数据挖掘对聚类的典型要求如下： 可伸缩性 处理不同类型属性的能力
2、 发现任意形状的聚类 用于决定输入参数的领域知识最小化 处理噪声数据的能力第8章 聚类分析8.1.2聚类分析中的数据类型数据矩阵：用m个变量（也称为属性）来表现n个对象 相异度矩阵：存储n个对象两两之间的近似度，通常用一个维的矩阵表示 111212122212mmnnnmxxxxxxxxx02,103,13,20,1,20dddd nd n 第8章 聚类分析8.1.3 区间标度变量 计算均值绝对偏差 计算标准化的度量值 欧几里德距离 曼哈顿距离 明考斯基距离 第8章 聚类分析8.1.4 二元变量 简单匹配系数 Jaccard系数 Rao系数 第8章 聚类分析8.1.5 分类型、序数型变量 分类
3、变量 序数型变量 第8章 聚类分析8.1.6 向量对象 夹角余弦 相关系数 第8章 聚类分析8.2 聚类分析常用算法分类 划分方法划分方法 层次方法层次方法 基于密度的方法基于密度的方法 基于网格的方法基于网格的方法 基于模型的方法基于模型的方法 高维数据的聚类方法高维数据的聚类方法 模糊聚类模糊聚类FCM第8章 聚类分析8.3 划分聚类方法 k-meansk-means算法是基于质心的算法。k-means算法以k为参数，把n个对象分为k个簇，以使簇内具有较高的相似度，而簇间的相似度最低。相似度的计算根据一个簇中对象的平均值（被看作簇的重心）来进行。Step1 任意选择任意选择k个对象作为初始
4、的簇中心；个对象作为初始的簇中心；Step2 repeat；Step3 根据与每个中心的距离，将每个对象赋给最近的簇；根据与每个中心的距离，将每个对象赋给最近的簇；Step4 重新计算每个簇的平均值；重新计算每个簇的平均值；Step5 until 不再发生变化。不再发生变化。第8章 聚类分析8.3 划分聚类方法 k-medoids不采用簇中对象的平均值作为参照点，可以选用簇中位置最中心的对象，即medoid。这样划分方法仍然是基于最小化所有对象与其参照点之间的相异度之和的原则来执行的。Step1 随机选择随机选择k个对象作为初始的代表对象；个对象作为初始的代表对象；Step2 repeat；S
5、tep3 指派每个剩余的对象给离它最近的代表对象所代表的簇；指派每个剩余的对象给离它最近的代表对象所代表的簇；Step4 随意地选择一个非代表对象；随意地选择一个非代表对象；Step5 计算用代替的总代价计算用代替的总代价S；Step6 如果，则用替换，形成新的如果，则用替换，形成新的k个代表对象的集合；个代表对象的集合；Step7 until 不发生变化。不发生变化。第8章 聚类分析8.4 层次聚类方法 8.4.1凝聚的和分裂的层次聚类 8.4.2 BIRCH：平衡迭代归约和聚类 8.4.3 ROCK：分类属性层次聚类算法 8.4.4 CURE：使用代表点聚类方法 8.4.5 Chamele
6、on：动态建模层次聚类第8章 聚类分析8.4.1 凝聚的和分裂的层次聚类凝聚的方法 首先将每个对象作为单独的一个原子簇 然后相继地合并相近的对象或原子簇 直到所有的原子簇合并为一个（层次的最上层），或者达到一个终止条件分裂的方法 首先将所有的对象置于一个簇中 在迭代的每一步中，一个簇被分裂为更小的簇， 直到最终每个对象在单独的一个簇中，或者达到一个终止条件第8章 聚类分析8.4.1 凝聚的和分裂的层次聚类第8章 聚类分析8.4.2 BIRCH：平衡迭代归约和聚类 BIRCH通过聚类特征（Clustering Feature，CF）对簇的信息进行汇总描述，然后对簇进行聚类。 BIRCH算法的主要
7、目标是使I/0时间尽可能小， 原因在于大型数据集通常不能完全装入内存中。BIRCH算法通过把聚类分为多个阶段来达到此目的 首先通过构建CF-树对原数据集进行预聚类 在前面预聚类的基础上进行聚类第8章 聚类分析8.4.2 BIRCH：平衡迭代归约和聚类 CF树的结构 第8章 聚类分析8.4.2 BIRCH：平衡迭代归约和聚类 BIRCH共包含四个阶段：预聚类阶段：扫描整个数据库，构建初始聚类特征树，该树保存在内存中，用简洁的汇总信息或者叶子节点中的子聚类来代表数据点的密集区域。（可选阶段）重新扫描叶子节点项，来构建一个更小的CF-树。采用别的聚类算法，对CF-tree的叶子节点进行聚类。（可选阶
8、段）把前一个阶段中找到的聚类的质心，用作种子来创建最终的聚类。其它数据点根据到这些种子所代表聚类的远近来重新分配到各个聚类中。第8章 聚类分析8.4.3 ROCK：分类属性层次聚类算法 分类属性的层次聚类算法针对具有分类属性的数据使用了链接的概念。对于聚类包含布尔或分类属性的数据，传统聚类算法使用距离函数。实验表明对分类数据聚类时，这些距离度量不能产生高质量的簇。大多数聚类算法在进行聚类时只估计点与点之间的相似度；也就是说，在每一步中那些最相似的点合并到一个簇中。这种局部方法很容易导致错误。第8章 聚类分析8.4.3 ROCK：分类属性层次聚类算法 ROCK算法采用一种比较全局的观点，通过考虑
9、成对点的邻域情况进行聚类。如果两个相似的点同时具有相似的邻域，那么这两个点可能属于同一个簇而合并。 ROCK算法使用一个相似度阈值和共享邻域的概念从一个给定的数据相似度矩阵中首先构建一个稀疏图。在这个稀疏图上执行凝聚层次聚类。使用一个优度度量评价聚类。采用随机抽样处理大规模的数据集。ROCK算法在最坏情况下的时间复杂度为 ，其中和分别是近邻数目的最大值和平均值，是对象的个数。 22logmaO nnm mnn第8章 聚类分析8.4.4 CURE：使用代表点聚类方法CURE选择了位于基于质心和基于代表对象方法之间的中间策略。不用单个质心或对象来代表一个簇而是选择数据空间中固定数目的具有代表性的点
10、。一个簇的代表点通过如下方式产生：首先选择簇中分散的对象然后根据一个特定的分数或收缩因子向簇中心收缩或移动它们在算法的每一步，有最近距离的代表点对（每个点来自于一个不同的簇）的两个簇被合并CURE解决了偏好球形和相似大小的问题，在处理孤立点上也更加健壮。第8章 聚类分析8.4.4 CURE：使用代表点聚类方法CURE步骤如下：源数据对象中抽取一个随机样本S；将样本S分割为一组划分；对每个划分局部地聚类；通过随机取样剔除孤立点。如果一个簇增长的太慢，就去掉它；对局部的簇进行聚类。落在每个新形成的簇中的代表点根据用户定义的一个收缩因子收缩或向簇中心移动。这些点代表了簇的形状；用相应的簇标签来标记数
11、据。第8章 聚类分析8.4.4 CURE：使用代表点聚类方法CURE算法特点：算法特点：CURE算法可以适应非球形的几何形状算法可以适应非球形的几何形状算法对孤立点的处理更加健壮算法对孤立点的处理更加健壮而且能够识别非球形和大小变化较大的簇；而且能够识别非球形和大小变化较大的簇；CURE算法的复杂性为。算法的复杂性为。CURE从源数据对象中抽取一个随机样本从源数据对象中抽取一个随机样本S，基，基于对此样本的划分进行聚类，如果抽取的样本发于对此样本的划分进行聚类，如果抽取的样本发生倾斜，则会严重影响聚类结果生倾斜，则会严重影响聚类结果 第8章 聚类分析8.4.5 Chameleon：动态建模层次
12、聚类 Chameleon算法的思想是：算法的思想是：首先通过一个图划分算法将数据对象聚类为大量相对首先通过一个图划分算法将数据对象聚类为大量相对较小的子聚类，较小的子聚类，然后用一个凝聚的层次聚类算法通过反复地合并子类然后用一个凝聚的层次聚类算法通过反复地合并子类来找到真正的结果簇。来找到真正的结果簇。Chameleon既考虑了互连性，又考虑了簇间的既考虑了互连性，又考虑了簇间的近似度，特别是簇内部的特征，来确定最相似的近似度，特别是簇内部的特征，来确定最相似的子簇。子簇。它不依赖于一个静态的，用户提供的模型，能够自动它不依赖于一个静态的，用户提供的模型，能够自动地适应被合并的簇的内部特征。地
13、适应被合并的簇的内部特征。 第8章 聚类分析8.4.5 Chameleon：动态建模层次聚类 与与CURE和和DBSCAN相比：相比：Chameleon在发现高质量的任意形状的聚类方面有在发现高质量的任意形状的聚类方面有更强的能力更强的能力但是在最坏的情况下，高维数据的处理代价可能对但是在最坏的情况下，高维数据的处理代价可能对n个对象需要个对象需要 的时间的时间 2O(n )第8章 聚类分析8.4.5 Chameleon：动态建模层次聚类 与与CURE和和DBSCAN相比：相比：Chameleon在发现高质量的任意形状的聚类方面有在发现高质量的任意形状的聚类方面有更强的能力更强的能力但是在最坏
14、的情况下，高维数据的处理代价可能对但是在最坏的情况下，高维数据的处理代价可能对n个对象需要个对象需要 的时间的时间 2O(n )第8章 聚类分析8.5 基于密度的聚类方法 8.5.1 DBSCAN：高密度连通区域聚类 8.5.2 OPTICS：点排序识别聚类结构 8.5.3 DENCLUE：密度分布函数的聚类第8章 聚类分析8.5.1 DBSCAN：高密度连通区域聚类一个给定对象周围半径一个给定对象周围半径 内的区域称为该对象的内的区域称为该对象的 邻域邻域DBSCAN算法通过检查数据库中每个点的算法通过检查数据库中每个点的-邻邻域来寻找聚类。域来寻找聚类。如果一个点如果一个点p的的-邻域包含
15、多于邻域包含多于MinPts个点，则创建个点，则创建一个以一个以p作为核心对象的新簇。作为核心对象的新簇。然后，然后，DBSCAN算法迭代地寻找从这些核心对象直算法迭代地寻找从这些核心对象直接密度可达的对象，这个过程可能涉及一些密度可达接密度可达的对象，这个过程可能涉及一些密度可达簇的合并。当没有新的点可以被添加到任何簇时，该簇的合并。当没有新的点可以被添加到任何簇时，该过程结束。过程结束。第8章 聚类分析8.5.1 DBSCAN：高密度连通区域聚类DBSCAN算法步骤：Step1 读取读取D中任意一个未分类的对象中任意一个未分类的对象p；Step2 检索出与检索出与p的距离不大于的距离不大于
16、Eps的所有对象的所有对象 ； Step3 如果如果 （即（即p为非核心对象），则将为非核心对象），则将p标记为标记为噪声，并执行噪声，并执行Step1；Step4 否则（即否则（即p为核心对象），给为核心对象），给 中的所有对象打中的所有对象打上一个新的类标签上一个新的类标签newid，然后将这些对象压入堆栈的，然后将这些对象压入堆栈的Seeds中；中；Step5 让让CurrentObject = Seeds.top；然后检索属于；然后检索属于 的所有对象；如果的所有对象；如果 ，则剔除已经打上标，则剔除已经打上标记的对象，将余下的未分类对象打上类标签记的对象，将余下的未分类对象打上类标签
17、newid，然，然后压入堆栈；后压入堆栈；Step6 Seeds.pop，判断，判断Seeds是否为空，是，则执行是否为空，是，则执行Step1 ，否则执行，否则执行Step5。Neps(p)Neps(p)MinPtsNeps(p)Neps(CurrentObject)Neps(CurrentObject) MinPts第8章 聚类分析8.5.1 DBSCAN：高密度连通区域聚类DBSCAN算法不仅可以发现任意形状的聚类，算法不仅可以发现任意形状的聚类，对数据输入顺序不敏感，并且具有处理异常数据对数据输入顺序不敏感，并且具有处理异常数据（噪声）的能力。（噪声）的能力。DBSCAN算法对用户定义
18、的参数是敏感的，而算法对用户定义的参数是敏感的，而参数的恰当选择是需要有相关经验的参数的恰当选择是需要有相关经验的第8章 聚类分析8.5.2 OPTICS：点排序识别聚类结构对于真实的，高维的数据集合而言，参数的设置对于真实的，高维的数据集合而言，参数的设置通常是依靠经验，难以确定。通常是依靠经验，难以确定。绝大多数算法对参数值是非常敏感的：设置的细绝大多数算法对参数值是非常敏感的：设置的细微不同可能导致差别很大的聚类结果。微不同可能导致差别很大的聚类结果。OPTICS算法通过对象排序识别聚类结构。算法通过对象排序识别聚类结构。OPTICS没有显式地产生一个数据集合簇，它为自动没有显式地产生一
19、个数据集合簇，它为自动和交互的聚类分析计算一个簇排序。和交互的聚类分析计算一个簇排序。这个次序代表了数据的基于密度的聚类结构。这个次序代表了数据的基于密度的聚类结构。第8章 聚类分析8.5.3 DENCLUE：密度分布函数的聚类 DENCLUE是对是对k-means聚类算法的一个推广：聚类算法的一个推广：DENCLUE算法得到的是全局最优划分。算法得到的是全局最优划分。DENCLUE主要基于：主要基于：每个数据点的影响可以用一个数学函数来形式化地模每个数据点的影响可以用一个数学函数来形式化地模拟，它描述了一个数据点在邻域内的影响，被称为影拟，它描述了一个数据点在邻域内的影响，被称为影响函数；响
20、函数；数据空间的整体密度可以被模型化为所有数据点的影数据空间的整体密度可以被模型化为所有数据点的影响函数的总和；响函数的总和；然后聚类可以通过确定密度吸引点来得到，这里的密然后聚类可以通过确定密度吸引点来得到，这里的密度吸引点是全局密度函数的局部最大。度吸引点是全局密度函数的局部最大。第8章 聚类分析8.5.3 DENCLUE：密度分布函数的聚类 DENCLUE算法步骤：算法步骤：Step1 对数据点占据的空间推导密度函数；对数据点占据的空间推导密度函数；Step2 识别局部最大点；识别局部最大点；Step3 通过沿密度增长最大的方向移动，将每个通过沿密度增长最大的方向移动，将每个点关联到一个
21、密度吸引点；点关联到一个密度吸引点；Step4 定义与特定的密度吸引点相关联的点构成定义与特定的密度吸引点相关联的点构成的簇；的簇；Step5 丢弃密度吸引点的密度小于用户指定阈值丢弃密度吸引点的密度小于用户指定阈值的簇；的簇；Step6 合并通过密度大于或等于合并通过密度大于或等于的点路径连接的点路径连接的簇。的簇。第8章 聚类分析8.6 基于网格的聚类方法基于网格的聚类方法 8.6.1 STING：统计信息网格聚类8.6.2 WaveCluster：利用小波变换聚类第8章 聚类分析8.6.1 STING：统计信息网格聚类STING是一种基于网格的多分辨率聚类技术，是一种基于网格的多分辨率聚
22、类技术，它将空间区域划分为矩形单元。它将空间区域划分为矩形单元。针对不同级别的分辨率，通常存在多个级别的矩形单针对不同级别的分辨率，通常存在多个级别的矩形单元，元，这些单元形成了一个层次结构：高层的每个单元被划这些单元形成了一个层次结构：高层的每个单元被划分为多个低一层的单元。分为多个低一层的单元。关于每个网格单元属性的统计信息（例如平均值、最关于每个网格单元属性的统计信息（例如平均值、最大值和最小值）被预先计算和存储。这些统计信息用大值和最小值）被预先计算和存储。这些统计信息用于回答查询。于回答查询。第8章 聚类分析8.6.1 STING：统计信息网格聚类优点如下：优点如下：计算是独立于查询
23、的；计算是独立于查询的；有利于并行处理和增量更新；有利于并行处理和增量更新；效率很高。效率很高。STING算法扫描数据库一次来计算单元的统计信息，算法扫描数据库一次来计算单元的统计信息，因此产生聚类的时间复杂度是，其中因此产生聚类的时间复杂度是，其中n是对象的数目。是对象的数目。在层次结构建立后，查询处理时间是，这里在层次结构建立后，查询处理时间是，这里g是最低是最低层网格单元的数目，通常远小于层网格单元的数目，通常远小于n。第8章 聚类分析8.6.1 STING：统计信息网格聚类缺点如下：缺点如下：如果粒度比较细，处理的代价会显著增加；但是，如果粒度比较细，处理的代价会显著增加；但是，如果网
24、格结构最低层的粒度太粗，将会降低聚类如果网格结构最低层的粒度太粗，将会降低聚类分析的质量；分析的质量；在构建一个父亲单元时没有考虑孩子单元和其相在构建一个父亲单元时没有考虑孩子单元和其相邻单元之间的关系，因此，结果簇的形状是邻单元之间的关系，因此，结果簇的形状是isothetic，即所有的聚类边界或者是水平的，即所有的聚类边界或者是水平的，或者是竖直的，没有对角的边界。或者是竖直的，没有对角的边界。尽管该技术有快速的处理速度，但可能降低簇的质量尽管该技术有快速的处理速度，但可能降低簇的质量和精确性。和精确性。第8章 聚类分析8.6.2 WaveCluster：利用小波变换聚类WaveClust
25、er是一种多分辨率的聚类算法，是一种多分辨率的聚类算法，首先通过在数据空间上加一个多维网格结构来汇总数首先通过在数据空间上加一个多维网格结构来汇总数据，据，然后采用一种小波变换来变换原特征空间，在变换后然后采用一种小波变换来变换原特征空间，在变换后的空间中找到密集区域。的空间中找到密集区域。在该方法中，每个网格单元汇总了一组映射到该在该方法中，每个网格单元汇总了一组映射到该单元中的点的信息。这种汇总信息适合于在内存单元中的点的信息。这种汇总信息适合于在内存中进行多分辨率小波变换和随后的聚类分析使用。中进行多分辨率小波变换和随后的聚类分析使用。第8章 聚类分析8.6.2 WaveCluster：
26、利用小波变换聚类强调点密集的区域，而忽视在密集区域外的较弱强调点密集的区域，而忽视在密集区域外的较弱的信息。的信息。在原始特征空间中的密集区域成为了附近点的吸引点，在原始特征空间中的密集区域成为了附近点的吸引点， 距离较远的点成为抑制点。距离较远的点成为抑制点。能够自动地排除孤立点。能够自动地排除孤立点。有助于发现不同精度的聚类。有助于发现不同精度的聚类。聚类速度很快。聚类速度很快。可以并行化。可以并行化。第8章 聚类分析8.6.2 WaveCluster：利用小波变换聚类强调点密集的区域，而忽视在密集区域外的较弱强调点密集的区域，而忽视在密集区域外的较弱的信息。的信息。在原始特征空间中的密集
27、区域成为了附近点的吸引点，在原始特征空间中的密集区域成为了附近点的吸引点， 距离较远的点成为抑制点。距离较远的点成为抑制点。能够自动地排除孤立点。能够自动地排除孤立点。有助于发现不同精度的聚类。有助于发现不同精度的聚类。聚类速度很快。聚类速度很快。可以并行化。可以并行化。第8章 聚类分析8.7 基于模型的聚类方法基于模型的聚类方法 8.7.1 统计学方法COBWEB8.7.2 神经网络方法SOMs第8章 聚类分析8.7.1 统计学方法COBWEB COBWEB算法将对象增量地加入到分类树中。 COBWEB算法沿着一条适当的路径向下，修改计数，寻找可以分类该对象的最好节点。 COBWEB算法也计
28、算为给定对象创建一个新的节点所产生的分类效用。 它与基于现存节点的计算相比较。根据产生最高分类效用的划分，对象被置于一个已存在的类，或者为它创建一个新类。COBWEB算法可以自动修正划分中类的数目。 它不需要用户提供这样的输入参数。第8章 聚类分析8.7.1 统计学方法COBWEB CORWEB算法的优点在于： 它不需要用户输入参数来确定分类的个数，它可以自动修正划分中类的数目。缺点是： 首先，它基于这样一个假设：在每个属性上的概率分布是彼此独立的。由于属性间经常是相关的，这个假设并不总是成立。 此外，聚类的概率分布表示使得更新和存储类相当昂贵。因为时间和空间复杂度不只依赖于属性的数目，而且取
29、决于每个属性的值的数目，所以当属性有大量的取值时情况尤其严重。第8章 聚类分析8.7.2 神经网络方法SOMs算法步骤： Step1 随机选取一组输入层神经元到输出层神经元之间的权值；Step2 选取输出神经元j 的邻接神经元集合（如图8-6）。是初始时刻为0的神经元集合形状，则为t 时刻的形状；Step3 输入一个新样本X；Step4 计算欧式距离，即输入样本与每个输入神经元j之间的距离；Step5 修正输出神经元及其邻近神经元的权值；Step6 重复Step3- Step5的学习过程。第8章 聚类分析8.8 高维数据聚类方法高维数据聚类方法 8.8.1 CLIQUE：维增长子空间聚类方法
30、8.8.2 PROCLUS：维归约子空间聚类方法 第8章 聚类分析8.8.1 CLIQUE：维增长子空间聚类方法 算法步骤： Step1 找出对应于每个属性的一维空间中的所有稠密区域；Step2 ；Step3 repeat；Step4 由稠密的维单元产生所有的候选稠密维单元；Step5删除点数少于的单元；Step6；Step7 until 不存在候选稠密维单元；Step8 通过取所有邻接的、高密度的单元并发现簇；Step9 使用一小组描述簇中单元的属性值阈的不等式概括每一个簇。第8章 聚类分析8.8.1 CLIQUE：维增长子空间聚类方法 缺点：CLIQUE 算法容易破坏密集区域的边缘，降低最
31、终结果的准确性。不能自动去除数据集中的孤立点，增加了计算复杂性。可能会剪掉一些密集单元，对最终的聚类结果质量造成影响。算法的多步骤都采用近似算法，聚类结果的精确性可能因此降低。第8章 聚类分析8.9 模糊聚类模糊聚类FCMFCM步骤： Step1 用值在0，1间的随机数初始化隶属矩阵U，使其满足式（8-1）中的约束条件 Step2 用式（8-4）计算c个聚类中心。 Step3 根据式（8-2）计算价值函数。如果它小于某个确定的阈值，或它相对上次价值函数值的改变量小于某个阈值，则算法停止。 Step4 用（8-5）计算新的U矩阵。返回Step2。第8章 聚类分析8.10 应用实例分析应用实例分析例8-2二元变量之间的相异度使用实例 例8-3 k-means算法使用实例例8-4 ROCK使用实例同时使用点相似度和邻域链接信息 例8-5 划分聚类与层次聚类联合使用实例 例8-6 模糊聚类应用 谢谢
