聚类算法课件.ppt

1、实验十十一 聚类算法主要内容1、聚类和聚类分析2、数据类型3、相似度量方法4、聚类方法的分类5、划分聚类的方法6、层次聚类方法7、基于空间索引的聚类方法8、聚类的应用案例1 聚类和聚类分析概述 1.1 聚类的起源1.2 聚类举例1.3 聚类的定义和相关概念1.1 聚类的起源人们认识世界的一种方法是将认识的对象按照一定的特征进行划分同一类事物之间有着相似的属性划分种类的方式包含分类和聚类1.2 分类举例1.2 聚类举例(一)对10位应聘者做智能检验。3项指标X，Y和Z分别表示数学推理能力，空间想象能力和语言理解能力。其得分如下，选择合适的统计方法对应聘者进行分类。应聘者12345678910X2

2、8181121262016142422Y29232223292322232927Z281816222622222424241.2 聚类举例(二)例如当我们对企业的经济效益进行评价时，建立了一个由多个指标组成的指标体系，由于信息的重叠，一些指标之间存在很强的相关性，所以需要将相似的指标聚为一类，从而达到简化指标体系的目的。1.3 聚类的定义及相关概念1.聚类的定义无监督的知识发现把物理或抽象对象的集合分成相似的对象类的过程成为聚类。2.相关概念簇:数据对象的集合距离:数据对象间的距离好的聚类：簇内部对象的距离小，而簇之间的距离大假如要分两个簇，如何分?00.20.40.60.811.21.41.

3、61.8200.20.40.60.811.21.41.61.82(0.1 0.1)(0.2 0.2)(1.8 1.8)(1.9 1.9)2 数据类型2.1 数据类型的分类2.2 数值型数据的标准化2.1 数据类型的分类从数据聚类的角度看，数据可以分为分类型和数值型分类型：名义型、等级型和布尔型名义型：属性值之间没有顺序，属性值的加减没有意义等级型：属性值之间有大小顺序，但不知道一个值比另一个值究竟大多少布尔型：分类型的特例，只有两个属性值数值型属性：属性值的加减、排序等均有意义2.2 数值型属性的标准化1 为什么要标准化数值型属性的量纲和单位不同，必须把不同的度量单位统一成相同的度量单位00.

4、20.40.60.811.21.41.61.820200400600800100012001400160018002000单 位：千 克单位：克00.20.40.60.811.21.41.61.820200400600800100012001400160018002000单 位：千 克单位：米2 标准化的常用方法Z-score标准化：均值为0，方差为1减去均值，除以绝对方差标准化值域，将值域映射到0,1除以均值：令均值为1除以最大值：令最大值为1前提：所有数值均为正值1()ijijjjxxxs11njijjisxxn3 注意：注意：不要为了标准化而标准化当我们需要比较的两个（或多个）序列是同一

5、量纲下的，则不必标准化标准化是按照属性进行标准化对哪些数列进行标准化作业：数列标准化(按小组交)设计一个excel表，实现数列标准化3 相似度量方法对象间的相似性计算是聚类的核心，有两种主要的方法：距离和相似度。00.20.40.60.811.21.41.61.8200.20.40.60.811.21.41.61.82(0.1 0.1)(0.2 0.2)(1.8 1.8)(1.9 1.9)3.1 距离1 距离的要求 0ijijdxx,0iji jx x d,iji jj ix x dd,ijki ji kk jx xx ddd2 常见的距离曼哈顿距离：欧式距离：切比雪夫距离：,1mi jikj

6、kkdxx2 0.5,1()mi jikjkkdxx,maxi jikjkdxx例子:分析上海股市和深圳股市的距离2.2 相似系数1.相似系数的要求0ijijrxx,0,1iji jx x r,iji jj ix x rr2 相似度的度量方式数量积法相关系数法111mijikjkkijrx xijM1,ijijijrx xij例子:分析上海股市和深圳股市的相似系数简单匹配法累积匹配的属性个数，匹配属性所占的比例作为相似系数大家利用匹配算法计算一下样本3和4、8和11的相似系数匹配系数针对二值型匹配系数=121234()/()waw dwaw dw bw c大家利用匹配系数计算上证指数和深证成指

7、的相似性补充4 聚类方法的分类4.1 平凡聚类和不平凡聚类4.2 覆盖聚类和非覆盖聚类4.3 层次聚类和非层次聚类4.4 数值型聚类、分类型聚类和混合型聚类4.5 从聚类的方法进行分类4.1 平凡聚类和不平凡聚类一组数据D有N个对象，分成M个簇平凡聚类：整个聚类只有一个簇或者每个对象单独成为一个簇非平凡聚类：其它的情况4.2 覆盖聚类和非覆盖聚类覆盖聚类：每个对象至少属于一个簇，则为覆盖聚类否则为非覆盖聚类4.3 层次聚类和非层次聚类如果存在两个聚类，其中一个聚类是另一个聚类的子集，则称为层次聚类，否则为非层次聚类4.4 数值型聚类、分类型聚类和混合型聚类根据属性的类型进行划分只包含数值属性的

8、数值型聚类只包含分类型属性的分类型聚类同时包含数值属性和分类型属性混合型聚类4.5 从聚类的方法进行聚类划分聚类层次聚类基于密度的聚类网格聚类5 划分聚类方法5.1 常见的划分聚类的方法5.2 K-means算法的一般过程5.3 例子5.1 常见的划分聚类的方法1 划分聚类的含义：对于一组数据集合D，给定聚类数目k和目标函数F，划分聚类算法把D划分成k个组，使得目标函数在此划分下达到最优。目标函数通常是：各个点到每个聚类中心的距离最短。2 常见的划分聚类的方法有K-meansK-medoids等等5.2 k-means算法5.2.1 聚类结果的表示形式每个聚类至少有一个样本每个样本至少属于一个

9、聚类5.2.2 K-means算法的过程(1)确定输入输出(2)具体处理流程(3)k-means算法的结束条件(4)(1)K-means算法的输入输出 输入：聚类个数k，以及包含n个数据对象的数据库。输出：满足方差最小标准的k个聚类。(2)(2)处理流程：处理流程：(1)(1)从从n n个数据对象任意选择个数据对象任意选择k k个对象作为初始聚个对象作为初始聚类中心。类中心。(2)(2)使用欧氏距离将剩余实例赋给距离它们最近使用欧氏距离将剩余实例赋给距离它们最近的簇中心的簇中心 (3)(3)使用每簇中的实例计算每个簇对象的均值使用每簇中的实例计算每个簇对象的均值(中中心对象心对象)，计算每个对

10、象与这些中心对象的距离，计算每个对象与这些中心对象的距离，并根据最小距离重新对相应对象进行分类。并根据最小距离重新对相应对象进行分类。(4)(4)重新计算每个重新计算每个(有变化有变化)聚类的均值聚类的均值(中心对中心对象象)，直至新平均值等于上次迭代的平均值，算法，直至新平均值等于上次迭代的平均值，算法结束。结束。假设空间数据对象假设空间数据对象分布如图分布如图(a)(a)所示，所示，设是设是k k3 3，也就是，也就是需要将数据集划分需要将数据集划分为为3 3份份(聚类聚类)。(3)K-means算法的结束条件：目标函数值不再下降两次迭代得到的聚点相同两次迭代得到的划分相同达到最大的迭代次

11、数（4）K-means算法的关键之处1.样本距离的确定2.样本中心点的确定对于数值型属性而言，对应属性求均值对于分类型属性而言，则复杂一些：选择频率最大的。思考：三者中心如何确定6 层次聚类法6.1 层次聚类的定义6.2 层次聚类的步骤6.3 聚类之间距离的定义6.1 层次聚类层次聚类方法是指递归地对对象进行合并和分裂，直到满足某一终止条件为止。6.2 层次聚类的过程(1)计算对象两两之间的距离；(2)构造n个单成员聚类C1,C2,Cn,每个聚类高度为0；(3)找到两个距离最近的聚类Ci和Cj，聚类的个数减1，以被合并的两个类之间的间距作为上层的高度(4)重复3直到满足终止条件6.3 聚类之间

12、距离的定义最大距离、最小距离、类平均距离、中心距离思考1分成两个聚类，大家计算各聚类之间的距离思考2:层次聚类结果练习利用最长距离法，写出层次聚类结果编号1 2 3 4 51234506024 034 5 07 1 5 5 07、基于空间索引的聚类方法7.1 几个重要概念：核心对象和边界对象核心对象：在给定半径r的领域中的对象个数大于密度阈值minNum，则该对象称为核心对象。边界对象：其它令r=5,minNum=3核心对象有哪些？非核心对象有哪些？编号1 2 3 4 51234506024 034 5 07 1 5 5 0直接密度可达、密度可达、密度联通直接密度可达：如果p是一个核心对象，q

13、属于p的领域，则称p直接密度可达q。问：这是能不能称q直接密度可达p？为什么？令p1=p,pk=q;其中pi直接密度可达pi+1，则称p密度可达q。问：p密度可达q是否意味着q密度可达p?为什么？如果存在o，使得o密度可达p，o也密度可达q，则称p与q是密度联通的。问1：若p密度联通q，那么q是否密度联通p问2：p密度联通q，是否意味着p密度可达q?若p密度可达q，是否意味着p密度联通q?问3：如果存在o，使得p密度可达o，q也密度可达o，能否称p与q是密度联通的？点1和点5有哪些关系？(密度可达、密度直接可达、密度联通)点2和点4有哪些关系？(密度可达、密度直接可达、密度联通)r=5,minNum=3编号1 2 3 4 51234506024 034 5 07 1 5 5 0基于密度的聚类步骤1.标记出核心对象Ci和边界对象Ni2.当ci和cj彼此密度可达，则ci和cj在同一个类中3.若ci密度可达Ni,则Ni所在类与ci相同，否则Ni单独归于一类思考：已知r=5,minNum=3，求下表的聚类结果编号1 2 3 4 51234506024 034 5 07 1 5 5 08 聚类的应用案例8.1 旅游上的应用情景：大家成立了一个旅行社，打算做一个调查问卷，针对学生进行宣传，发展学生旅游市场，请问你会怎么做？