第10章描述建模聚类

2019/12/201五邑大学计算机学院何国辉数据仓库与数据挖掘DataWarehouseandDataMining2019/12/202数据仓库与数据挖掘DataWarehouseandDataMining第十章描述建模：聚类2019/12/203描述建模的目的是对数据进行概括，以看到数据的特征。描述建模的方法有很多，如：聚类分析、密度估计、因素分析等。本章主要讨论聚类分析。10.0基本概念2019/12/204根据学习过程是否有指导，基于数据挖掘的学习方法可以分为两大类：有指导的学习：指存在一部分已知的知识，能对模型的构造起到指导作用。学习的目的是构造最优的模型，使它与已知知识之间的误差最小。无指导的学习：在构造模型的过程中，没有利用已知的知识，模型完全从数据中抽取。分类是一种典型的有指导的学习方法。10.1聚类分析简介2019/12/205聚类属于无指导学习方法。它在没有训练样本的情况下，依靠数据自身的相似性把数据集划分成多个有意义的子集（一个子集称为一个组或一个族（簇））。方法：将数据集分组，使其具有最大的组内相似性和最小的组间相似性。10.1聚类分析简介（续）2019/12/20610.1.1对象间的相似性对象间的相似性是聚类分析的核心。不同类型的对象，其相似性的定义方式是不同的。对象的属性可分为：区间标度型二元型分类型序数型比例型2019/12/2071.区间标度型变量区间标度型变量的典型代表：温度、湿度等。这一类型变量通常有一个可以被均匀分割的取值区间。在进行聚类分析前，该类变量需要先进行规格化，以消除因度量单位不同而带来聚类结果不一致的影响。2019/12/2081.区间标度型变量（续）对于给定变量f，假设它在n个对象上的取值分别为x1f，x2f，...，xnf，则一种常用的规格化方法是求标准偏差：其中：是平均绝对偏差，而是算术平均。smxzffififnififfmxsn11niiffxmn112019/12/2091.区间标度型变量（续）基于区间标度型变量的相似性通常用距离来描述。距离越大，相似性越小。反之，距离越小，相似性越大。令D={x1，x2，...，xm}为m维空间中的一组对象，，d（i，j）是xi和xj的距离，则采用欧几里得距离公式为：Dxxji、)||...|||(|),(2222211mmjxixjxixjxixjid2019/12/20101.区间标度型变量（续）采用曼哈坦距离公式为：|jmximx|...|j2xi2x||j1xi1x(|j)d(i,2019/12/20111.区间标度型变量（续）上述两种距离函数都满足如下性质：非负数，d（i，j）必须是一个非负数；d（i，j）=0，说明某个对象到自己的距离为0；对称性，d（i，j）=d（j，i）；d（i，j）≦d（i，h）+d（h，j），即该距离函数满足三角不等式。2019/12/20121.区间标度型变量（续）上述两种距离函数是明可夫斯基距离公式的特殊形式：考虑到不同变量具有不同的重要性，则可以对不同的变量制定不同的权重，即：qqjmimqjiqjixxxxxxjid/12211)|||||(|),(…qqjmimpqjiqjixxwxxwxxwjid/1222111)||||||(),(2019/12/20132.二元型变量二元型变量只能取两个值。如：性别只能取“男”或“女”，等等。对于对称的二元型变量，通常采用的距离计算公式为：d(i，j)=（b+c）/（a+b+c+d）对于非对称的二元型变量，采用的距离计算公式为：d(i，j)=（b+c）/（a+b+c）2019/12/20142.二元型变量（续）其中：对象j10对象i1ab0cd2019/12/20153.分类型变量分类型变量是二元型变量的扩展，它可以取多个值，例如：世界上的七大洲、4大洋，我国的56个民族中的“洲”、“洋”和“民族”。通常采用的距离公式为：d(i，j)=（p-m）/p其中，p表示分类型变量的总数，而m表示相匹配的变量个数。2019/12/20163.分类型变量（续）举例：给出6个6维分类的样本:X1={A，B，A，B，C，B}X2={A，A，A，B，A，B}X3={B，B，A，B，A，B}X4={B，A，B，A，C，A}X5={A，C，B，A，B，B}X6={A，C，B，A，B，B}求样本两两之间的距离？2019/12/20174.序数型变量序数型变量的域由多个有先后次序的状态值构成，如：排名{冠军、亚军、季军}、职称{助教、讲师、副教授、教授}等。序数型变量的相似性计算方法和区间标度型变量的相似性计算方法类似。措施：先进行规格化，将变量的值映射到[0.0,1.0]之间。2019/12/20184.序数型变量（续）假设第i个对象在第f个变量上的取值为rif，规格化的方法为：其中，Mf指的是该序数型变量所能取的所有值的个数。格式化后，就可以采用欧几里得等距离公式计算任意两个对象之间的距离。11Mrzfifif2019/12/20195.比例型变量比例型变量主要用来描述数据的指数型变化，如细菌数目的增长等。对于比例型变量，通常采用先将其转换成区间标度型变量（通过对数变换），然后再采用和区间标度型变量相同的方式计算相似度。2019/12/20206.混合型变量混合型变量是指同一个对象是由多种类型的变量来同时描述。采用的距离计算公式为：其中：p表示对象所具有的变量的总数，是一个系数（当xif或xjf的值缺失，或者当f是非对称二元型变量，且xif=xjf=0时，取值为0；其它情况下取值为1），是根据变量f的类型计算出来的。pffijpfffijjidjid11,,fijfjid,2019/12/202110.1.2其它相似性度量除了用上面提到的距离来度量对象间的相似性之外，还有很多其它的相似性度量方法。如：相似系数等。夹角余弦法相关系数法（略）2019/12/2022一个好的聚类方法是能生成高质量的族或组。所谓高质量是指：在同一族中的对象相似性很高，而不同族之间的对象相似性很低。迄今为止，人们研究了很多种有效的聚类方法：基于划分的方法基于密度的方法基于层次的方法基于模型的方法......10.2聚类方法概述2019/12/2023一个好的聚类算法的标准：能够处理各种数据类型能够处理各种形状的数据分布不需要太多的输入参数能够处理噪音数据与数据的输入顺序无关具有可解释性和可使用性具有可扩展性10.2聚类方法概述（续）2019/12/202410.2.1基于划分的聚类给定一个参数k，基于划分的聚类方法是将数据库D中的n个对象分成k个族C1，C2，...，Ck，并且使得某个评分函数在此划分下达到最优。划分方法满足两个条件：每个分组至少包含一个对象。每个对象必须属于且仅属于某一个分组。目前已经提出的基于划分的聚类方法主要有：k-Means（k-平均算法）k-Medoids（PAM）（k-中心点算法）...2019/12/20251.k-Means方法k-Means方法是MacQueen在1967年提出的。主要思想：给定一个数据库D和一个参数k（k≦n），k-Means方法将D中的n个对象分成k个族，并使得如下评分函数在此划分下取值最小。2019/12/20261.k-Means方法（续）几个有关概念：假设给定的n维空间上的n个样本集被以某种方式分区为K个类{C1，C2，…，Ck}。每个类Ck包含nk个样本，因此:类Ck的均值向量Mk，也称为重心。其中：每个类Ck包括nk个样本。Ki=1∑nk=Nnki=1Mk=(1/n)∑xik2019/12/20271.k-Means方法（续）Ck的方差是Ck中的每个样本及其重心的欧式距离的平方和，这个误差也叫类内误差：包含K个类的整个聚类空间的平方误差是类内误差的和：nki=1ek=∑(xik-Mk)22Kk=1Ek=∑ek22追求目标：总体平方误差在一个可接受的范围内。总体平方误差2019/12/20281.k-Means方法（续）算法描述：（1）首先将所有对象随机分配到k个非空的簇中。（2）计算每个簇的平均值，并用该平均值代表相应的簇。（3）根据每个对象与各个簇中心的距离，分配给最近的簇。（4）然后转第二步，重新计算每个簇的平均值。这个过程不断重复直到满足某个准则函数才停止。2019/12/20291.k-Means方法（续）举例：有关样本：5个点{x1，x2，x3，x4，x5}，假定要求的类的数量为2，对其进行分类。其中样本数据为：x1=(0，2)x2=(0，0)x3=(1.5，0)x4=(5，0)x5=(5，2)首先随意分成两类，然后进行迭代2019/12/20301.k-Means方法（续）过程：1）随机划分两个类：C1={x1,x2,x4}，C2={x3,x5}2）计算两个类的重心：M1={（0+0+5)/3，（2+0+0）/3}={1.66,0.66}M2={（1.5+5)/2，（0+2）/2}={3.25,1.00}2019/12/20311.k-Means方法（续）3）求内类方差：e12=[(0-1.66)2+(2-0.66)2]+[(0-1.66)2+(0-0.66)2]+[(5-1.66)2+(0-0.66)2]=19.36e22=[(1.5-3.25)2+(0-1)2]+[(5-3.25)2+(2-1)2]=8.12求总体平方误差：E=e12+e22=19.36+8.12=27.482019/12/20321.k-Means方法（续）4)根据距离重心M1、M2的最小距离，再分配所有的样本：d(M1,x1)=(1.662+1.342)1/2=2.14d(M2,x1)=3.4则x1∈C1d(M1,x2)=d(M2,x2)=则x2∈…d(M1,x3)=d(M2,x3)=则x3∈…d(M1,x4)=d(M2,x4)=则x4∈…d(M1,x5)=d(M2,x5)=则x5∈C12019/12/20331.k-Means方法（续）5）得到新类C1和C2，并计算新的重心M1、M26）计算新的类内方差和总体平方误差：7）如果总体平方误差在规定范围，结束，否则再次迭代，直到满足要求。2019/12/20341.k-Means方法（续）k-Means方法的优点：对于处理大数据量具有可扩充性和高效率。算法的复杂度是O（tkn），其中n是对象的个数，k是Cluster的个数，t是循环的次数，通常k，tn。可以实现局部最优化。2019/12/20351.k-Means方法（续）k-Means方法的缺点：族的个数k必须事先确定。在有些应用中，事先确定族的个数非常困难。无法找出具有特殊形状的族。必须给出k的初始中心点，如果初始中心点选择不好，最后形成的聚类结果明显很差。求中心点时，需要计算算术平均。无法适应具有分类属性的数据。2019/12/20361.k-Means方法（续）k-Means方法的变种k-Modes方法k-Prototypes算法......2019/12/20372.k-Medoids方法k-Medoids方法是在k-Means方法的而基础上提出的。主要思想是：为每个族找到一个具有代表性的对象，该对象被称为Medoid，是最靠近该族中心点的对象。剩余的对象根据其与代表对象的距离分配给最近的一个簇。然后反复用非代表对象代替代表对象，以提高聚类的质量。一旦k个Medoids确定下来，则每个对象就属于距它最近的Medoid所属族。2019/12/20382.k-Medoids方法（续）k-Medoids方法的主要优点：可以很好地处理噪音数据。这种算法对于脏数据和异常数据不敏