第十章 聚类分析

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第十章 聚类分析,聚类分析含义,将物理或抽象对象的集合分组成为由类似的对象组成的多个类的过程称为,聚类,，由聚类所组成的簇是一组对象的集合，这些对象与同一簇中的对象彼此相似，与其它簇中的对象相异。,与分类不同，它要划分的类是未知的。,什么是好的聚类分析？,一个好的聚类分析方法会产生高质量的聚类,高类内相似度,低类间相似度,作为统计学的一个分支，聚类分析的研究主要是基于距离的聚类；一个高质量的聚类分析结果，将取决于所使用的聚类方法,聚类方法的所使用的相似性度量和方法的实施,方法发现隐藏模式的能力,数据类型及转换,1,、数据矩阵：用,p,个变量（也称为度量或属性）来表现,n,个对象，例如用年龄、身高、性别等属性来表现对象“人”。构成一个,n*p,的,矩阵。,2,、相异度矩阵：存储,n,个对象两两之间的近似程度性，表现形式是一个,n*n,的,矩阵。这里,d(i,j,),是对象,i,和对象,j,之间,相异性,的量化表示,相异度计算,许多聚类算法都是以相异度矩阵为基础，如果数据是用数据矩阵形式表示，则往往要将其先转化为相异度矩阵。,相异度,d(i,j,),的具体计算会因所使用的数据类型不同而不同，常用的数据类型包括：,区间标度变量,二元变量,标称型、序数型和比例标度型变量,混合类型的变量,数据类型及转换,3,、区间标度度量,一个粗略线性标度的连续度量。（如重量，温度等）,为什么这么做,?,选用的度量单位会直接影响聚类结果。例如千克改位克。一般，所用的单位越小，变量的值域就越大，对聚类的影响也越大。为了避免数据对度量单位的依赖，数据应当标准化。,实现度量值的标准化：将原来的度量值转换为无单位的值。,变换方法,1,）计算平均的绝对偏差,S,f,2,）计算标准化度量值，或,z-score:,对象的相似度计算方法,（,1,）欧几里德距离,（,2,）曼哈坦距离,（,3,）明斯基距离,（,1,）二元变量,变量的取值只有两个状态，如性别，表示是否吸烟，医疗检查正常还是不正常等。,i,和,j,是两个变量：,q,是两个变量中都为,1,的个数,t,是两个变量中都为,0,的个数,s,是,i,变量中为,0,，,j,中为1,的个数,r,是,i,变量中为,1,，,j,中为0,的个数,p=,q+r+s+t,二元变量权重相同,(,对称的，如性别）,即：分子为两者相异的总数，分母为二元变量总数,其它类型变量的相异度计算,二元变量权重不同,(,非对称的）,例如，一个疾病化验结果正常和不正常，对一个群体，正常者总是大多数，我们用,1,表现几率小的情况，,0,表示另一种情况。,评价系数，,Jaccard,系数,即：两个相异的数量作为分子，相异的数量加两个为,1,的数量作为分母。（同对称二元变量相比，两个同为,0,的数量不出现在分母中）,其它类型变量的相异度计算,示例,假定一个病人记录表如下：,姓名,发烧,咳嗽,检查,1,检查,2,检查,3,检查,4,张明,是,否,不正常,正常,正常,正常,王枚,是,否,不正常,正常,不正常,正常,李力,是,是,正常,正常,正常,正常,.,.,.,.,.,.,.,假定一个病人记录表如下：,姓名,发烧,咳嗽,检查,1,检查,2,检查,3,检查,4,张明,是,否,不正常,正常,正常,正常,王枚,是,否,不正常,正常,不正常,正常,李力,是,是,正常,正常,正常,正常,.,.,.,.,.,.,.,示例,假定一个病人记录表如下：,姓名,发烧,咳嗽,检查,1,检查,2,检查,3,检查,4,张明,是,否,不正常,正常,正常,正常,王枚,是,否,不正常,正常,不正常,正常,李力,是,是,正常,正常,正常,正常,.,.,.,.,.,.,.,从左边的计算知道：,（,1,）李力和王枚不大可能有相同疾病，因为相异很高；,（,2,）张明和王枚最可能得相同的疾病,示例,其它类型变量的相异度计算,（,2,）枚举变量,可以有若干个不同取值，比如反映产品颜色的,color,可以 是,红、黄、绿、兰、粉红,假设一个枚举变量的状态数目是,M,。这些状态可以映射到字母、符号或一组整数,(1,2,M),。,p,是全部变量的数目,m,是匹配的数目。,其它类型变量的相异度计算,（,3,）序数型变量,是枚举但有序，比如,金牌、银牌、铜牌,区间标度度量值划成了区间，比如年龄分成了年龄段,10,岁以下，,11.20,21.30,.,等。,一个序数型变量的值可以映射为,秩,。例如一个变量,f,可以有,M,f,个状态，可以映射到一个有序排列1，2，,M,f,。,如何处理序数型变量？,假设,f,是用于描述,n,个对象的一组序数型变量之一，关于,f,的相异度计算包括如下步骤：,1,）第,i,个对象的,f,值为,x,if,，,变量,f,有,M,f,个有序的状态，对应于序列1，,M,f,。,用对应的秩,r,if,代替,x,if,，,r,if,1,，,.,，,M,f,2,）,既然每个序数型变量可以有不同数目的状态，经常必须将每个变量的值映射到0.0，1.0上，以便每个变量都有相同的权重。可以通过用,z,if,代替,r,if,来实现,3),相异度的计算可以采用前面的任意一种距离度量方法,（,4,）比例标度型,非线性的取正的数据，如指数型数据。,对数变换，对象,i,的,f,变量的值,x,if,被变换成,y,if,，,y,if,=,log(x,if,),将,x,if,看成序数型数据,其它类型变量的相异度计算,6,、混合类型的变量,真实数据库的元组的变量往往是混合的。处理方法为：,（,1,）将变量按类型分组，对每种类型的变量进行单独的聚类分析。如果这些分析得到的结果是兼容的，则该方法是可行的。实际应用中，这种情况比较少见。,（,2,）将所有变量一起处理，只进行一次聚类。,将不同类型的变量组合在单个相异度矩阵中，把所有有意义的变量转换到共同的值域区间,0.0,，,1.0,上。,假设数据集包含,p,个不同类型的变量，对象,i,和,j,之间的相异度,d(i,，,j),定义为：,6,、混合类型的变量,其中，如果,x,if,或,x,jf,缺，或者,x,if,=,x,jf,=0,，,且变量,f,是不对称的二元变量，则指示项 =0；否则等于1。变量,f,对,i,和,j,之间相异的计算方式与其具体类型相关：,如果,f,是二元变量或枚举变量：如果,x,if,=,x,jf,否则为1。,如果,f,是区间标度变量：,如果,f,是虚数型或者比例标度型变量：计算秩,r,if,，在变换,z,if,类间距离,距离函数都是关于两个样本的距离刻画，然而在聚类应用中，最基本的方法是计算类间的距离。,设有两个类,C,a,和,C,b,，它们分别有,m,和,h,个元素，它们的中心分别为,a,和,b,。设元素,x C,a,，,y,C,b,，这两个元素间的距离通常通过类间距离来刻画，记为,D(C,a,C,b,),。,类间距离的度量主要有：,最短距离法：定义两个类中最靠近的两个元素间的距离为类间距离。,最长距离法：定义两个类中最远的两个元素间的距离为类间距离。,中心法：定义两类的两个中心间的距离为类间距离。,类平均法：它计算两个类中任意两个元素间的距离，并且综合他们为类间距离：,离差平方和。,中心法,中心法涉及到类的中心的概念。假如,C,i,是一个聚类，,x,是,C,i,内的一个数据点，那么类中心定义如下：,其中,n,i,是第,i,个聚类中的点数。因此，两个类,C,a,和,C,b,的类间距离为：,其中,a,和,b,是类,C,a,和,C,b,的中心点，,d,是某种形式的距离公式。,离差平方和,离差平方和用到了类直径的概念：,类的直径反映了类中各元素间的差异，可定义为类中各元素至类中心的欧氏距离之和，其量纲为距离的平方：,根据上式得到两类,C,a,和,C,b,的直径分别为,a,和,b,，类,C,a,+b,=C,a,C,b,的直径为,a+b,，则可定义类间距离的平方为：,三、划分方法,划分方法,:,给定一个有,n,个对象的数据集，划分聚类技术将构造数据,k,个划分，每一个划分就代表一个簇，,k,n,。也就是说，它将数据划分为,k,个簇，而且这,k,个划分满足下列条件：,每一个簇至少包含一个对象。,每一个对象属于且仅属于一个簇。,对于给定的,k,，算法首先给出一个初始的划分方法，以后通过反复迭代的方法改变划分，使得每一次改进之后的划分方案都较前一次更好。,给定一个,k,，要构造出,k,个簇，并满足采用的划分准则：,k-,平均,:,由簇的中心来代表簇；,k-,中心点,:,每个簇由簇中的某个数据对象来代表。,聚类设计的评价函数,一种直接方法就是观察聚类的类内差异（,Within cluster variation,）和类间差异,(Between cluster variation,）。,类内差异：衡量聚类的紧凑性，类内差异可以用特定的距离函数来定义，例如，,类间差异：衡量不同聚类之间的距离，类间差异定义为聚类中心间的距离，例如，,聚类的总体质量可被定义为,w(c,),和,b(c,),的一个单调组合，比如,w(c,),/,b(c,),。,k,-means,算法,k,-means,算法，也被称为,k,-,平均或,k,-,均值，是一种得到最广泛使用的聚类算法。相似度的计算根据一个簇中对象的平均值来进行。,输入：簇的数目,k,和包含,n,个对象的数据库。,输出：,k,个簇，使平方误差准则最小。,（,1)assign initial value for means;/*,任意选择,k,个对象作为初始的簇中心；*,/,(2)REPEAT,(3),FOR,j,=1 to,n,DO assign each,xj,to the,closest,clusters;,(4)FOR,i,=1 to,k,DO /*,更新簇平均值*,/,(5)Compute /*,计算准则函数,E,*/,(6)UNTIL,E,不再明显地发生变化。,k,-means,算法,算法首先随机地选择,k,个对象，每个对象初始地代表了一个簇的平均值或中心。对剩余的每个对象根据其与各个簇中心的距离，将它赋给最近的簇。然后重新计算每个簇的平均值。这个过程不断重复，直到准则函数收敛。,准则函数试图使生成的结果簇尽可能地紧凑和独立。,k,-means,例子,样本数据,序号 属性,1,属性,2,1 1 1,2 2 1,3 1 2,4 2 2,5 4 3,6 5 3,7 4 4,8 5 4,迭代次数平均值平均值产生的新簇新平均值新平均值,（簇,1,）（簇,2,）（簇,1,）（簇,2,）,1,（,1,，,1,）（,1,，,2,）,1,，,2,，,3,，,4,，,5,，,6,，,7,，,8,（,1.5,，,1,）（,3.5,，,3,）,2,（,1.5,，,1,）（,3.5,，,3,）,1,，,2,，,3,，,4,，,5,，,6,，,7,，,8,（,1.5,，,1.5,）（,4.5,，,3.5,）,3,（,1.5,，,1.5,）（,4.5,，,3.5,）,1,，,2,，,3,，,4,，,5,，,6,，,7,，,8,（,1.5,，,1.5,）（,4.5,，,3.5,）,根据所给的数据通过对其实施,k,-means,(,设,n,=8,，,k,=2),，其主要执行执行步骤：,第一次迭代：假定随机选择的两个对象，如序号,1,和序号,3,当作初始点，分别找到离两点最近的对象，并产生两个簇,1,，,2,和,3,，,4,，,5,，,6,，,7,，,8,。,对于产生的簇分别计算平均值，得到平均值点。,对于,1,，,2,，平均值点为（,1.5,，,1,）（这里的平均值是简单的相加出,2,）；,对于,3,，,4,，,5,，,6,，,7,，,8,，平均值点为（,3.5,，,3,）。,第二次迭代：通过平均值调整对象的所在的簇，重新聚类，即将所有点按离平均值点（,1.5,，,1,）、（,3.5,，,1,）最近的原则重新分配。得到两个新的簇：,1,，,2,，,3,，,4,