聚类分析算法学习报告课件

1、聚类分析算法 学习汇报第1页，共31页。聚类分析概述宁夏大学数学与计算机学院 1、什么是聚类？ 聚类（clustering）是将物理或抽象对象的集合分组成为多个类或簇（cluster）的过程，使得在同一个簇中的对象之间具有较高的相似度，而不同簇中的对象差别较大。 2、与分类的不同 它要划分的类是未知的。即聚类是一种无指导学习，它不依赖预先定义的类和带类标号的训练实例。 第2页，共31页。聚类分析的应用 聚类分析已经广泛的用在许多应用中，包括模式识别、数据分析、图像处理以及市场研究。典型的应用： （1）商业：帮助市场分析人员从客户基本库中发现不同的客户群，并且用不同的购买模式描述不同客户群的特征

2、。 （2）生物学：推导植物或动物的分类，活的对种群固有结构的认识。 （3）WEB文档分类 （4）其他：地球观测数据库中相似地区的确定各类保险投保人的分组，一个城市中不同类型、价值、地理位置房子的分组等。 （5）作为其他数据挖掘算法的预处理：即先进行聚类，然后再进行分类等其他数据挖掘宁夏大学数学与计算机学院第3页，共31页。聚类分析的要求宁夏大学数学与计算机学院可伸缩性处理不同类型属性的能力发现任意形状的聚类 用于决定输入参数的领域知识最小化 处理噪声数据的能力 对于输入记录的顺序不敏感高维性基于约束的聚类可解释性和可用性第4页，共31页。聚类分析中的数据类型宁夏大学数学与计算机学院 聚类分析中

3、数据类型用于度量对象间的相异度，常用的数据类型:区间标度变量二元变量标称型、序数型和比例标度型变量混合类型变量第5页，共31页。区间标度变量 宁夏大学数学与计算机学院 1、 区间标度变量是一个粗略线性标度的连续度量。典型的例子包括重量和高度，经度和纬度坐标，以及大气温度。2、选择不同的度量单位（如“米”与英尺、“千克”与“磅”等）将直接影响聚类分析的结果。 3、为了避免聚类分析对度量单位的依赖性，数据需要进行标准化。 4、怎样将一个变量的数据标准化呢？为了实现度量值的标准化，一种方法是将原来的度量值转换为无单位的值。 第6页，共31页。度量值的标准化 宁夏大学数学与计算机学院 （1）计算平均的

4、绝对偏差（mean absolute deviation）:其中： （2）计算标准化的度量值，或（z-score）: 第7页，共31页。对象间的相异度计算欧几里德距离：曼哈坦距离：明考斯基距离： 宁夏大学数学与计算机学院第8页，共31页。聚类分析中的数据类型宁夏大学数学与计算机学院 聚类分析中数据类型用于度量对象间的相异度，常用的数据类型:区间标度变量二元变量标称型、序数型和比例标度型变量混合类型变量第9页，共31页。二元变量宁夏大学数学与计算机学院 一个二元变量只有两个状态：0或者1，0表示该变量为空，1表示该变量存在。 如果假设所有的二元变量有相同的权重，则得到一个两行两列的可能性表。在下

5、面这个表中，a是对于对象i和j值都为1的变量的数目，b是对于对象I值为1而对象j的值为0的变量数目，s是对于对象c值为0而在对于对象j值为1的变量数目，d是对于对象i和j的值都为0的变量的数目。变量的总数是p，p=a+b+c+d。 Object jObject i第10页，共31页。 基于对称二元变量的相似度称为恒定的相似度，即当一些或者全部二元变量编码改变时，计算结果不会发生变化。 如果二元变量的两个状态的输出不是同样重要，则该二元变量是不对称的。基于这样变量的相似度被称为非恒定的相似度。 二元变量相似度的计算宁夏大学数学与计算机学院第11页，共31页。聚类分析中的数据类型宁夏大学数学与计算

6、机学院 聚类分析中数据类型用于度量对象间的相异度，常用的数据类型:区间标度变量二元变量标称型、序数型和比例标度型变量混合类型变量第12页，共31页。 1、标称型变量 标称变量（nominal）是二元变量的推广，它可以具有多于两个的状态值。例如，map-color是一个标称变量，它可能有五个状态：红色，黄色，绿色，粉红色和蓝色。两个对象和j之间的相异度可以用两种方法来计算： （1）简单匹配方法 M是匹配的数目，P是全部变量的数目 （2）使用二元变量 为每一个状态创建一个新的二元变量，可以用非对称的二元变量来编码标称变量。标称型变量宁夏大学数学与计算机学院第13页，共31页。 一个离散的序数（or

7、dinal）型变量类似于标称变量，除了序数型变量的个状态是以有意义的序列排序的。在计算对象的相异度时，序数型变量的处理与区间标度变量非常类似。（1）将xif 用它对应的秩代替。 （2）将每个变量的值域映射到0.0，1.0上，使得每个变量都有相同的权重。这通过用zif来替代rif来实现。 （3）用前面所述的区间标度变量的任一种距离计算方法来计算。序数型变量宁夏大学数学与计算机学院第14页，共31页。 用比例标度型变量描述对象之间相异度有以下三种方法： （1）采用与处理区间标度变量相同的方法。 （2）对比例标度型变量进行对数变换，如： yif = log(xif) 然后再对变换得到的值按区间标度的

8、值处理。 （3）将其作为连续的序数型数据，将其秩作为区间标度的值来对待。比例标度型变量宁夏大学数学与计算机学院第15页，共31页。聚类分析中的数据类型宁夏大学数学与计算机学院 聚类分析中数据类型用于度量对象间的相异度，常用的数据类型:区间标度变量二元变量标称型、序数型和比例标度型变量混合类型变量第16页，共31页。 在许多现实的数据库中，对象是被混合类型的变量描述的。一般来说，一个数据库可能包含上面列出的全部六种变量类型。用以下的公式计算i和j的相异度： 其中，p为对象中的变量个数 （1）如果xif或xjf缺失（即对象i或对象j没有变量f的值），或者xif = xjf =0，且变量f是不对称的

9、二元变量，则指示项ij(f)=0；否则ij(f)=1。 （2）f 是二元变量或标称变量: if xif = xjf dij(f) = 0, else dij(f) = 1 （3）f是区间标度变量：dij(f) = | xif-xjf |/maxhxhf-minhxhf （4）f 是序数型或比例标度型： 计算秩rif 计算zif并将其作为区间标度变量值对待混合类型变量宁夏大学数学与计算机学院第17页，共31页。基于划分的方法基于层次的方法基于密度的方法基于网格的方法基于模型的方法 主要聚类分析方法宁夏大学数学与计算机学院第18页，共31页。 划分方法（partitioning method）的基

10、本思想是：给定一个n个对象或元组的数据库，一个划分方法构建数据的k个划分，每个划分表示一个聚簇，并且kn。也就是说，它将数据划分成为k个组，同时满足如下要求： 每个组至少包括一个对象； 每个对象必须属于且只属于一个组。 基于划分的聚类会要求穷举所有可能的划分。实际上，绝大多数应用采用了以下两个比较流行的启发式方式： （1）k-平均算法。在该算法当中，每个簇用该簇中对象的平均值来表示。 （2）k-中心点算法。在该算法中每个簇用接近聚类中心的一个对象来表示。 基于划分的方法宁夏大学数学与计算机学院第19页，共31页。 层次方法（hierarchical method）的基本思想是：对给定数据对象集

11、合进行层次的分解。根据层次的分解如何形成，层次的方法可以分为凝聚的和分裂的。 （1）凝聚的方法：又称为自底向上的方法，一开始将每个对象作为单独的一个组，然后根据一些规则相继地合并相近的对象或者组，将它们聚合成越来越大的类，直到所有的组合并为一个，或者达到一个预先设定的终止条件。 基于层次的方法宁夏大学数学与计算机学院第20页，共31页。（2）分裂的方法：又称为自顶向下的方法，是一个与凝聚的方式相反的过程。即开始时将所有的对象置于一个簇中。在迭代的每一步中，一个簇被分裂为更小的簇，直到最终每个对象在单独的一个簇中，或者达到一个终止条件（例如：类的数目到了预定值，最近的两个类之间的最小距离大于设定

12、值等）。基于层次的方法宁夏大学数学与计算机学院第21页，共31页。 绝大多数划分方法基于对象之间的距离进行聚类。这样的方法只能发现球状的簇，而在发现任意形状的簇上遇到了困难。随之提出了基于密度的聚类方法（density-based method）。 基本思想是：只要临近区域的密度（对象或数据点的数目）超过某个值，就继续聚类。也就是说，对给定类中的每个数据点，在一个给定范围的区域中必须至少包含某个数目点。这样的方法可以用来过滤“噪声”孤立点数据，发现任意形状的簇。基于密度的方法宁夏大学数学与计算机学院第22页，共31页。 基于网格的方法（grid-based method）的基本思想是：对象空间

13、量化为有限数目的单元，形成了一个网格结构。所有的聚类操作都在这个网格结构上进行。这种方法的主要优点是它的处理速度较快，其处理时间独立于数据对象的数目，只与量化空间中每一维单元数目有关。基于网格的方法宁夏大学数学与计算机学院第23页，共31页。 基本思想是：为每个簇假定了一个模型，寻找数据对给定模型的最佳拟合。一个基于模型的算法可能通过构建反映数据点空间分布的密度函数来定位聚类。它也是基于标准的统计数字自动决定聚类的数目，考虑“噪声”数据或孤立点，从而产生健壮的聚类方法。基于模型的方法宁夏大学数学与计算机学院第24页，共31页。 k-means算法，也被称为k-平均或k-均值，是一种得到最广泛使

14、用的聚类算法。 它是将各个聚类子集内的所有数据样本的均值作为该聚类的代表点，算法的主要思想是通过迭代过程把数据集划分为不同的类别，使得评价聚类性能的准则函数达到最优，从而使生成的每个聚类内紧凑，类间独立。 k-means算法宁夏大学数学与计算机学院第25页，共31页。（1）选定某种距离作为数据样本间的相似性度量 例如欧式距离：（2）选择评价聚类性能的准则函数 误差平方和准则函数为：（3）相似度的计算根据一个簇中对象的平均值来进行。k-means算法三个要点宁夏大学数学与计算机学院第26页，共31页。输入：簇的数目k和包含n个对象的数据库。输出：k个簇，使平方误差准则最小。 算法步骤： 1.为每

15、个聚类确定一个初始聚类中心，这样就有K 个初始聚类中心。 2.将样本集中的样本按照最小距离原则分配到最邻近聚类 3.使用每个聚类中的样本均值作为新的聚类中心。4.重复步骤2.3步直到聚类中心不再变化。5.结束，得到K个聚类 k-means算法流程宁夏大学数学与计算机学院第27页，共31页。主要优点：是解决聚类问题的一种经典算法，简单、快速。对处理大数据集，该算法是相对可伸缩和高效率的。因为它的复杂度是0 (n k t ) , 其中, n 是所有对象的数目, k 是簇的数目, t 是迭代的次数。通常k n 且t n 。当结果簇是密集的，而簇与簇之间区别明显时, 它的效果较好。k-means算法性

16、能分析宁夏大学数学与计算机学院第28页，共31页。主要缺点在簇的平均值被定义的情况下才能使用，这对于处理符号属性的数据不适用。必须事先给出k（要生成的簇的数目），而且对初值敏感，对于不同的初始值，可能会导致不同结果。 它对于“躁声”和孤立点数据是敏感的，少量的该类数据能够对平均值产生极大的影响。k-means算法性能分析宁夏大学数学与计算机学院第29页，共31页。 k-means算法对某类簇中所有的样本点维度求平均值，即获得该类簇质点的维度。当聚类的样本点中有“噪声”（离群点）时，在计算类簇质点的过程中会受到噪声异常维度的干扰，造成所得质点和实际质点位置偏差过大，从而使类簇发生“畸变”。 为了解决该问题，K中心点算法（K-medoids）提出了新的质点选取方式，而不是简单像k-means算法采用均值计算法。在K中心点算法中，每次迭代后的质点都是从聚类的样本点中选取，而选取的标准就是当该样本点成为新的质点后能提高类簇的聚类质量，使得类簇更紧凑。该算法使用绝对误差标准来定