聚类分析算法学习报告.ppt

《聚类分析算法学习报告.ppt》由会员分享，可在线阅读，更多相关《聚类分析算法学习报告.ppt（31页珍藏版）》请在三一办公上搜索。

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

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

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

4、）:,对象间的相异度计算,欧几里德距离：曼哈坦距离：明考斯基距离：,宁夏大学数学与计算机学院,聚类分析中的数据类型,宁夏大学数学与计算机学院,聚类分析中数据类型用于度量对象间的相异度，常用的数据类型:区间标度变量二元变量标称型、序数型和比例标度型变量混合类型变量,二元变量,宁夏大学数学与计算机学院,一个二元变量只有两个状态：0或者1，0表示该变量为空，1表示该变量存在。如果假设所有的二元变量有相同的权重，则得到一个两行两列的可能性表。在下面这个表中，a是对于对象i和j值都为1的变量的数目，b是对于对象I值为1而对象j的值为0的变量数目，s是对于对象c值为0而在对于对象j值为1的变量数目，d是对

5、于对象i和j的值都为0的变量的数目。变量的总数是p，p=a+b+c+d。,Object j,Object i,基于对称二元变量的相似度称为恒定的相似度，即当一些或者全部二元变量编码改变时，计算结果不会发生变化。如果二元变量的两个状态的输出不是同样重要，则该二元变量是不对称的。基于这样变量的相似度被称为非恒定的相似度。,二元变量相似度的计算,宁夏大学数学与计算机学院,聚类分析中的数据类型,宁夏大学数学与计算机学院,聚类分析中数据类型用于度量对象间的相异度，常用的数据类型:区间标度变量二元变量标称型、序数型和比例标度型变量混合类型变量,1、标称型变量 标称变量（nominal）是二元变量的推广，它

6、可以具有多于两个的状态值。例如，map-color是一个标称变量，它可能有五个状态：红色，黄色，绿色，粉红色和蓝色。两个对象和j之间的相异度可以用两种方法来计算：（1）简单匹配方法 M是匹配的数目，P是全部变量的数目（2）使用二元变量 为每一个状态创建一个新的二元变量，可以用非对称的二元变量来编码标称变量。,标称型变量,宁夏大学数学与计算机学院,一个离散的序数（ordinal）型变量类似于标称变量，除了序数型变量的个状态是以有意义的序列排序的。在计算对象的相异度时，序数型变量的处理与区间标度变量非常类似。（1）将xif 用它对应的秩代替。（2）将每个变量的值域映射到0.0，1.0上，使得每个变

7、量都有相同的权重。这通过用zif来替代rif来实现。（3）用前面所述的区间标度变量的任一种距离计算方法来计算。,序数型变量,宁夏大学数学与计算机学院,用比例标度型变量描述对象之间相异度有以下三种方法：（1）采用与处理区间标度变量相同的方法。（2）对比例标度型变量进行对数变换，如：yif=log(xif)然后再对变换得到的值按区间标度的值处理。（3）将其作为连续的序数型数据，将其秩作为区间标度的值来对待。,比例标度型变量,宁夏大学数学与计算机学院,聚类分析中的数据类型,宁夏大学数学与计算机学院,聚类分析中数据类型用于度量对象间的相异度，常用的数据类型:区间标度变量二元变量标称型、序数型和比例标度

8、型变量混合类型变量,在许多现实的数据库中，对象是被混合类型的变量描述的。一般来说，一个数据库可能包含上面列出的全部六种变量类型。用以下的公式计算i和j的相异度：其中，p为对象中的变量个数（1）如果xif或xjf缺失（即对象i或对象j没有变量f的值），或者xif=xjf=0，且变量f是不对称的二元变量，则指示项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并将其作为区

9、间标度变量值对待,混合类型变量,宁夏大学数学与计算机学院,基于划分的方法基于层次的方法基于密度的方法基于网格的方法基于模型的方法,主要聚类分析方法,宁夏大学数学与计算机学院,划分方法（partitioning method）的基本思想是：给定一个n个对象或元组的数据库，一个划分方法构建数据的k个划分，每个划分表示一个聚簇，并且kn。也就是说，它将数据划分成为k个组，同时满足如下要求：每个组至少包括一个对象；每个对象必须属于且只属于一个组。基于划分的聚类会要求穷举所有可能的划分。实际上，绝大多数应用采用了以下两个比较流行的启发式方式：（1）k-平均算法。在该算法当中，每个簇用该簇中对象的平均值来

10、表示。（2）k-中心点算法。在该算法中每个簇用接近聚类中心的一个对象来表示。,基于划分的方法,宁夏大学数学与计算机学院,层次方法（hierarchical method）的基本思想是：对给定数据对象集合进行层次的分解。根据层次的分解如何形成，层次的方法可以分为凝聚的和分裂的。（1）凝聚的方法：又称为自底向上的方法，一开始将每个对象作为单独的一个组，然后根据一些规则相继地合并相近的对象或者组，将它们聚合成越来越大的类，直到所有的组合并为一个，或者达到一个预先设定的终止条件。,基于层次的方法,宁夏大学数学与计算机学院,（2）分裂的方法：又称为自顶向下的方法，是一个与凝聚的方式相反的过程。即开始时将

11、所有的对象置于一个簇中。在迭代的每一步中，一个簇被分裂为更小的簇，直到最终每个对象在单独的一个簇中，或者达到一个终止条件（例如：类的数目到了预定值，最近的两个类之间的最小距离大于设定值等）。,基于层次的方法,宁夏大学数学与计算机学院,绝大多数划分方法基于对象之间的距离进行聚类。这样的方法只能发现球状的簇，而在发现任意形状的簇上遇到了困难。随之提出了基于密度的聚类方法（density-based method）。基本思想是：只要临近区域的密度（对象或数据点的数目）超过某个值，就继续聚类。也就是说，对给定类中的每个数据点，在一个给定范围的区域中必须至少包含某个数目点。这样的方法可以用来过滤“噪声”

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

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

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

15、别明显时,它的效果较好。,k-means算法性能分析,宁夏大学数学与计算机学院,主要缺点在簇的平均值被定义的情况下才能使用，这对于处理符号属性的数据不适用。必须事先给出k（要生成的簇的数目），而且对初值敏感，对于不同的初始值，可能会导致不同结果。它对于“躁声”和孤立点数据是敏感的，少量的该类数据能够对平均值产生极大的影响。,k-means算法性能分析,宁夏大学数学与计算机学院,k-means算法对某类簇中所有的样本点维度求平均值，即获得该类簇质点的维度。当聚类的样本点中有“噪声”（离群点）时，在计算类簇质点的过程中会受到噪声异常维度的干扰，造成所得质点和实际质点位置偏差过大，从而使类簇发生“畸

16、变”。为了解决该问题，K中心点算法（K-medoids）提出了新的质点选取方式，而不是简单像k-means算法采用均值计算法。在K中心点算法中，每次迭代后的质点都是从聚类的样本点中选取，而选取的标准就是当该样本点成为新的质点后能提高类簇的聚类质量，使得类簇更紧凑。该算法使用绝对误差标准来定义一个类簇的紧凑程度。,K-中心点算法,宁夏大学数学与计算机学院,输入：结果簇的数目K，包含N个对象的数据库。输出：K个簇，使得所有对象与其最近中心点的相异度总和最小。方法：随机选择K个对象作为初始的中心点。REPEAT指派每个剩余的对象给离它最近的中心点所代表的簇。随机地选择一个非中心点对象Orandom；计算用Orandom代替Oj的总代价S；if S0,then Orandom代替Oj,形成新的K个中心点的集合；until不发生变化；,K-中心点算法,宁夏大学数学与计算机学院,