第3章 数据库挖掘-聚类分析

1聚类分析什么是聚类分析?聚类分析中的数据类型主要聚类分析方法分类划分方法（PartitioningMethods）分层方法基于密度的方法基于表格的方法基于模型（Model-Based）的聚类方法异常分析3什么是一个好的聚类方法?一个好的聚类方法要能产生高质量的聚类结果——簇，这些簇要具备以下两个特点：高的簇内相似性低的簇间相似性聚类结果的好坏取决于：该聚类方法采用的相似性评估方法以及该方法的具体实现；该方法是能发现某些还是所有的隐含模式；4可伸缩性能够处理不同类型的属性能发现任意形状的簇在决定输入参数的时候，尽量不需要特定的领域知识能够处理噪声和异常对输入数据对象的顺序不敏感能处理高维数据能产生一个好的、能满足用户指定约束的聚类结果结果是可解释的、可理解的和可用的聚类算法性能的方面要求5聚类分析什么是聚类分析?聚类分析中的数据类型主要聚类分析方法分类划分方法（PartitioningMethods）分层方法基于密度的方法基于表格的方法基于模型（Model-Based）的聚类方法异常分析总结6incomestudentcredit_ratingbuys_computerhighnofairnohighnoexcellentnohighnofairyesmediumnofairyeslowyesfairyeslowyesexcellentnolowyesexcellentyesmediumnofairnolowyesfairyesmediumyesfairyesmediumyesexcellentyesmediumnoexcellentyeshighyesfairyesmediumnoexcellentno7对于不同的聚类算法得到的簇的数目可能不一样生成的簇其对应的特征可能不一样8聚类算法的主要基础相异度计算相似度计算数据归一化或者标准化9聚类依据差异度/相似度矩阵:相似度通常用距离函数来表示；对不同类型的变量，距离函数的定义通常是不同的；根据实际的应用和数据的语义，在计算距离的时候，不同的变量有不同的权值相联系；很难定义“足够相似了”或者“足够好了”只能凭主观确定；10聚类依据通常使用距离来衡量两个对象之间的相异度。常用的距离度量方法有:明考斯基距离（Minkowskidistance）:其中i=(xi1,xi2,…,xip)和j=(xj1,xj2,…,xjp)是两个p维的数据对象,q是一个正整数。qqppqqjxixjxixjxixjid)||...|||(|),(221111聚类依据当q=1时,d称为曼哈坦距离（Manhattandistance）当q=2时,d就成为欧几里德距离:距离函数有如下特性：d(i,j)0d(i,i)=0d(i,j)=d(j,i)d(i,j)d(i,k)+d(k,j)可以根据每个变量的重要性赋予一个权重12聚类分析中的数据类型区间标度变量（Interval-scaledvariables）二元变量（Binaryvariables）标称型，序数型和比例型变量（Nominal,ordinal,andratiovariables）混合类型变量（Variablesofmixedtypes）13区间标度变量区间标度变量是一个粗略线性标度的连续度量，如重量、长度、温度等。选用的度量单位对聚类分析的效果影响很大。一般而言，度量单位越小，变量的取值范围就越大，对聚类效果的影响也就越大。(1.65,72),(1.60,71),(1.75,72)(165,0.072),(160,0.071),(175,0.072)14区间标度变量为了减小度量单位的选择对聚类效果的影响，需要对数据进行标准化，使原来的度量值变成无度量单位的值。15区间标度变量数据标准化计算绝对偏差的平均值:其中计算标准度量值(z-score)使用绝对偏差的平均值比使用标准偏差更健壮.)...211nffffxx(xnm|)|...|||(|121fnffffffmxmxmxnsffififsmxz16二元变量的可能性表表中每个对象有p个变量，且p=a+b+c+da表示对象i和对象j的值都为1的概率b表示对象i为1、对象j的值为0的概率c表示对象i为0、对象j的值为1的概率。d表示对象i和对象j的值都为0的概率二元变量pdbcadcdcbaba和和0101对象i对象j17二元变量对称的如果一个二元变量的两个状态是同等价值的，具有相同的权重。即可以任取其中一种状态编码为1或者0对于对称的二元变量，采用简单匹配系数来评价两个对象之间的相异度d(i,j)=(b+c)/(a+b+c+d)18二元变量非对称的如果变量的两个状态不是同样重要的，则称该变量是不对称的。根据惯例，将比较重要通常也是出现概率比较小的状态编码为1，将另一种状态编码为0。对于非对称的二元变量，采用Jaccard系数来评价两个对象之间的相异度d(i,j)=(b+c)/(a+b+c)19二元变量的相异度计算实例性别是一个对称的二元变量//不用于计算其它的都是非对称的二元变量将值Y和P编码为1,值N编码为0，根据Jaccard系数计算得：姓名性别发烧咳嗽测试-1测试-2测试-3测试-4Jack男YNPNNNMary女YNPNPNJim男YPNNNN75.021121),(67.011111),(33.010210),(maryjimdjimjackdmaryjackd20标称变量是二元变量的推广，它可以具有多于两个的状态，比如变量map_color可以有red,yellow,blue,green四种状态。有两种计算相异度的方法：方法1:简单匹配方法m是匹配的数目,p是全部变量的数目d(i,j)=(p-m)/p方法2:使用二元变量为每一个状态创建一个新的二元变量，可以用非对称的二元变量来编码标称变量。标称变量21一个序数型变量可以是离散的也可以是连续的离散的序数型变量类似于标称变量，除了它的M个状态是以有意义的序列排序的，比如职称连续的序数型变量类似于区间标度变量，但是它没有单位，值的相对顺序是必要的，而其实际大小并不重要。序数型变量22序数型变量相异度的计算与区间标度变量的计算方法相类似将xif用它对应的秩代替rif,rif{1,2,…,Mf}将每个变量的值域映射到[0.0，1.0]上，使得每个变量都有相同的权重。这通过用zif来替代rif来实现zif=(rif-1)/(Mf-1)用前面所述的区间标度变量的任一种距离计算方法来计算23比例标度型变量:总是取正的度量值，有一个非线性的标度，近似的遵循指数标度，比如AeBtorAe-Bt计算相异度的方法:采用与处理区间标度变量相同的方法—不是一个好的选择进行对数变换，对变换得到的值再采用与处理区间标度变量相同的方法yif=log(xif)比例标度型变量24一个数据库可能包含了所有这6种类型的变量处理过程较为复杂混合类型的变量28聚类分析什么是聚类分析?聚类分析中的数据类型主要聚类分析方法分类划分方法（PartitioningMethods）分层方法基于密度的方法基于表格的方法基于模型（Model-Based）的方法//神经网络29划分方法（partitioningmethod）划分方法的基本思想是:给定一个n个样本的数据库，划分方法将数据划分为k个划分（k=n），每个划分表示一个簇，同时满足：a.每个簇至少包含一个样本；b.每个样本必须属于且仅属于一个簇。30划分方法划分策略全局最优:尽可能的列举所有的划分；启发式方法:k-平均和k-中心点算法代表性算法k-平均(MacQueen’67):由簇的中心来代表簇；k-中心点或PAM(Partitionaroundmedoids):每个簇由簇中的某个数据对象来代表。31K-平均算法给定k，算法的处理流程如下:1.随机的把所有对象分配到k个非空的簇中；2.计算每个簇的平均值，并用该平均值代表相应的簇；3.将每个对象根据其与各个簇中心的距离，重新分配到与它最近的簇中；4.回到第二步，直到不再有新的分配发生。32K-平均算法(例)坐标表示5个点｛X1,X2,X3,X4,X5｝作为一个聚类分析的二维样本：X1＝（0,2），X2＝（0,0），X3＝（1.5,0），X4＝（5,0），X5＝（5,2）。假设要求的簇的数量k=2。33K-平均算法(例)第1步：由样本的随机分布形成两个簇：C1＝｛X1,X2,X4｝和C2＝｛X3,X5｝。这两个簇的质心M1和M2是：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｝；34K-平均算法(例)第2步：取距离其中一个质心（M1或M2）最小的距离分配所有样本，簇内样本的重新分布如下：d(M1,X1)=(1.662+1.342)1/2=2.14d(M2,X1)=3.40==X1∈C1；d(M1,X2)=1.79和d(M2,X2)=3.40==X2∈C1d(M1,X3)=0.83和d(M2,X3)=2.01==X3∈C1d(M1,X4)=3.41和d(M2,X4)=2.01==X4∈C2d(M1,X5)=3.60和d(M2,X5)=2.01==X5∈C2新簇C1＝｛X1,X2,X3｝和C2＝｛X4,X5｝35K-平均算法(例)第3步：计算新的质心：M1＝｛0.5，0.67｝；M2＝｛5.0，1.0｝。如果继续分析新中心和样本间的距离，样本将会全部分给同样的簇，不将重新分配，算法停止。36K-平均算法例子01234567891001234567891001234567891001234567891001234567891001234567891001234567891001234567891037优点相对高效的:算法复杂度O(tkn),其中n是数据对象的个数,k是簇的个数,t是迭代的次数，通常k,tn.算法通常终止于局部最优解；缺点只有当平均值有意义的情况下才能使用，对于类别字段不适用；必须事先给定要生成的簇的个数；对“噪声”和异常数据敏感；不能发现非凸面形状的数据。K-平均算法38K-平均算法的变种k-原型算法包括综合k-平均算法和k-模算法能同时处理类别字段和数值字段k-模算法(Huang’98)用模来替代平均值；用新的相异度计算方法来处理类别字段；用基于频率的方法来修改簇的模；39找出簇中位置最中心的对象，即中心点来代表簇PAM(PartitioningAroundMedoids,1987CLARA(Kaufmann&Rousseeuw,1990)CLARANS(Ng&Han,1994):RandomizedsamplingK-中心点算法40PAM(KaufmanandRousseeuw,1987）用真实的数据对象来代表簇随机选择k个对象作为初始的中心点，将每一个非中心点对象根据与中心点的距离分配给离它最近的中心点，产生k个簇Repeat对簇中每一个由非中心对象h和中心对象i,计算i被h替代的总代价TcihIfTcih0,i被h替换然后将每一个非中心点对象根据与中心点的距离分配给离它最近的中心点Until不发生变化。41可分为两类凝聚分裂层次聚类42凝聚的层次聚类采用自底向上策略首先将每个样本作为一个簇，然后合并这些原子簇形成越来越大的簇，减少簇的数目，直到所有的样本都在一个簇中，或某个终结条件被满足。层次聚类43分裂的层次聚类采用自顶向下策略首先将所有样本置于一个簇中，然后逐渐细分为越来越小的簇，来增加簇的数目，直到每个样本自成一个