数据挖掘与学习知识发现(8模糊聚类)

,.第8章 模糊聚类8.1概述聚类是人类一项最基本的认识活动，如“物以类聚，人以群分”。所谓聚类就是感谢阅读按照事物的某些属性，把事物聚集成类，使类间的相似性尽量小，类内的相似性尽感谢阅读量大。其数学描述为设给定数据集合V{v|i1,2,,n}，其中v为数据对象，根据数据对象间的相谢谢阅读i i似程度将数据集合分成k组{C|j1,2,,k}，并满足：jCVjCCijkCVi1i则该过程称为聚类，C,(i1,2,,n)称为簇。精品文档放心下载i聚类的基本方法经常是定义两个对象之间的距离，也可采用不依赖于距离的方精品文档放心下载法：首先定义一个优化目标，再优化得到某个局部最小值。谢谢阅读聚类与分类区别：聚类是一个无监督的学习过程，属观察学习；而分类是有监督精品文档放心下载的学习过程，属示例学习。它们的根本区别在于，分类时需要事先知道分类所依据感谢阅读的属性值，而聚类是要找到这个分类的属性值。一般属性值有两类：数值属性和符精品文档放心下载号属性。关于数值属性聚类方法很多，而对符号属性聚类方法较少，常是将其转化精品文档放心下载为数值后再处理。聚类分析目前已广泛应用于诸多领域，包括模式识别、数据分析、图像处理、自谢谢阅读动控制以及市场研究等。通过聚类，人们能够识别密集的和稀疏的区域，因而发现感谢阅读,.全局的分布模式，以及数据属性之间的有趣的相互关系。8.2聚类方法的分类聚类分析方法很多，通常是针对数据库中的记录，根据一定的分类规则，合理地感谢阅读划分记录集合，确定每个记录所在类别（如，k-平均算法、k-中心点算法、基于凝感谢阅读聚的层次聚类和基于分裂的层次聚类等）。一般来说，对于相同的数据集，若采用不精品文档放心下载同的聚类方法，可能有不同的划分结果。（1）按聚类的标准分，有统计聚类方法和概念聚类方法统计聚类方法：基于相似性测量。包括系统聚类法、分解法、加入法、动态聚类法、有序样品聚类、重叠聚类和模糊聚类等。这种聚类方法是一种基于全局比较的聚类，它需要考察所有个体才能决定类的划分。因此，它要求所有的数据必须预先给定，而不能动态增加新的数据对象。感谢阅读概念聚类方法：基于对象具有的概念。这里的距离不再是统计方法中的几何距离，而是根据概念的描述来确定的。典型的概念聚类或形成方法有：COBWEB、OLOC和基于列联表的方法。精品文档放心下载（2）按聚类的对象分，有数值聚类方法和符号值聚类方法感谢阅读数据聚类方法：所分析的数据的属性为数值数据，因此可对所处理的数据直接比较大小；感谢阅读符号值聚类方法：所分析的数据的属性为符号数据，因此对所处理的数据不能直接比较大小。精品文档放心下载（3）按聚类尺寸分，有基于距离聚类、基于密度聚类和基于连续的聚类精品文档放心下载基于距离的聚类：根据数据之间的距离进行聚类。这种算法对于噪声数据和孤立点数据比较敏感；精品文档放心下载,.基于密度的聚类：该方法认为簇是具有相同密度的连通区域。因此，密度聚类需要扫描整个数据集，将数据空间划分为不同的小方格，并使用小方格的并来近似表示簇。该方法有可能不够精确，但该方法对于噪声数据和孤立点不敏感。该方法也可利用空间索引结构，通过计算超球区内的密度进行聚类，但该方法因为要维护复杂的索引结构，故对于海量数据存在效率问题；谢谢阅读基于连续的聚类：将聚类对象映射为图模型或超图模型，然后根据边或者超边寻找连通的结点集合。谢谢阅读8.3常用的聚类算法聚类问题本质上是一个优化问题，即通过一种迭代运算使得系统的目标函数达感谢阅读到一个极小值。该目标函数为划分的评价函数。通常采用距离作为划分的评价标准，谢谢阅读对数值属性主要采用欧氏距离，而对符号属性则通常采用Hamming距离。精品文档放心下载基于划分的聚类算法通过优化一个评价函数把数据集划分为k个部分。当采用聚谢谢阅读类内的距离的平方作为评价函数时，聚类内的所有点向聚类中心汇集，因此采用基精品文档放心下载于距离的划分评价函数方法得到的聚类是球形的。一般，不同的评价函数会优先选谢谢阅读择不同的聚类结构。（1）k-平均方法-平均法是一种常用的基于划分的聚类方法。它根据最终分类的个数k随机地选取k个初始聚类中心，不断地迭代，直至达到目标函数的最小值，即得到最终的聚感谢阅读类结果为止。其中，目标函数通常采用平方误差准则，即Ek|pmi|2i1pCi这里，p为聚类对象；mi为类Ci的各聚类对象（样本）的平均值。即精品文档放心下载,.ppCii|Ci|该方法在每一次迭代中，要计算每一个点和各聚类中心的距离，并将距离最近的感谢阅读聚类作为该点所属的类。所以k-平均法的算法复杂度为O(knt)，其中，k--聚类数；精品文档放心下载n--结点数；t--迭代次数。---平均法是解决聚类问题的一种经典算法，是一种爬山式搜索算法。优点：算法简洁、快速。谢谢阅读缺点：对初值敏感，且易陷入局部最优。（2）k-中心点方法k平均法的算法过程相似。唯一不同之处就是聚类中心的计算和表达。k-中心点法是用类中最靠近中心的一个样本来代表该类。k-中心点法最初随机选择k个感谢阅读中心点，然后反复地试图找出更好的中心点。-中心点法的核心是中心点的选择。假设聚类C原先的中心点Oc_old，现拟改为精品文档放心下载Oc_new，则根据样本属于和其距离最近的聚类的原则，可能引起各样本所属聚类的情况发生调整。对于原先聚类C中的任意样本pi可能有两种情况：感谢阅读pi和Oc_new的距离仍然小于和其他各聚类的中心点的距离，因此pi仍属于聚类聚类c；感谢阅读pi和其他某一聚类r的中心点的距离最短，则pi将改属于聚类r；谢谢阅读假如Oc_new使得总的距离平方和下降，则Oc_new代替Oc_old成为聚类C的新聚类中精品文档放心下载心，反之，则说明Oc_new目前不适合作为聚类C的新的聚类中心，重新试探其他的点。谢谢阅读相比于k-平均法，k-中心点算法对于噪声数据和异常数据不敏感，但计算量比精品文档放心下载-平均算法要大。,.（3）层次聚类层次的方法是对给定数据对象集合进行层次的分解。层次聚类的基本思想是：将谢谢阅读模式样本按距离准则逐步聚类，直到满足分类要求为止。其聚类过程可表示为一个精品文档放心下载二叉层次树，叶结点表示一个样本，中间结点表示将数据集分割为两个不同的类，感谢阅读或一个类由它的两个子类合并而成。在层次聚类方法中，一旦一个步骤（合并或分裂）完成，它就不能被撤消。这既谢谢阅读是优点，不用担心组合数目的不同选择，计算代价会较小；同时又是缺点，不能更感谢阅读正错误的决定。根据层次聚类的分解形成原理，层次聚类的方法可以分为凝聚方法和分裂方法。谢谢阅读凝聚方法也称为自底向上方法。一开始将每个对象作为单独的一个类，然后相继地合并相近的对象或组，将较小的数据对象子集合依据相似程度进行合并，这些小的数据对象子集合逐渐合并成较大的数据对象子集合，直到所有的类合并为一个，或者达到一个终止条件为止，从而构成一个类的层次。感谢阅读假设C和C是两个聚类，则两类间的最短距离定义为ijD(C,C)min{d}ijp,pji其中，pC，pC，d表示样本p和p间的距离。凝聚方法的算法描述为iijjp,pjijiFori=1,2…,n令C{p}；iiWhile存在一个以上的聚类doIf D(Ci,Cj) thenCiCiCj;删除Cj;,.End;采用凝聚方法的典型聚类算法有：BIRCH、CURE、CHAMELON等。谢谢阅读分裂方法也称自顶向下方法。一开始将所有的对象置于一个类中，在迭代的每一步中，一个类被分裂为更小的类，直到每个对象在单独的一个类中，或者达到一个终止条件为止。通常情况下，凝聚方法优于分裂方法。DIANA是分裂方法的代表。精品文档放心下载8.4模糊聚类在客观世界中，存在着大量的界限模糊并不分明的聚类问题，如区分“年青人”和“中年人”时就需要模糊的划分，由此诞生了模糊聚类。精品文档放心下载模糊聚类的开创性工作是由Ruspini于1969年提出的，是基于Zadeh教授1965年提出的模糊集合论。之后，Bezdek和Dunn于1987年提出了C-均值模糊聚类法。目前，有关模糊聚类的方法很多，并已应用于生物学、商业、经济、工程、信息科学、医药学等许多领域。谢谢阅读常用的模糊聚类方法有：系统聚类法、传递闭包法以及与此等价的最大支撑树的Prim算法及Kruskal算法、动态直接聚类法，基于摄动的模糊聚类法FCMBP、模谢谢阅读C-均值法、模糊ISODATA算法、人工神经网络模糊聚类法等。谢谢阅读聚类算法分为分割和分层两种。分割聚类算法通过优化目标函数，把数据集分割谢谢阅读成若干部分，如模糊k-均值聚类法。分层聚类是由不同层次的分割聚类组成，层次谢谢阅读之间的分割具有嵌套的关系，如传递闭包法和摄动的模糊聚类法FCMBP。谢谢阅读1）聚类结果的表示通常的聚类是把含n个对象的集合划分成K个不相交的部分，称之为聚类块。感谢阅读,.聚类的结果可表示为一个nK阶矩阵U(u)，其中ijnK1,i聚类块jui聚类块jij0,K1,i1,2,,n;j1,2,K（说明每个元素属于且仅属于1个聚类）uij1{0,1}ij模糊聚类的结果表示，就是将上面通常的聚类结果表示替换为使感谢阅读u [0,1], i1,2,,n;j1,2,,K谢谢阅读ij2）模糊聚类的一般模型聚类问题实质上是在一定的聚类准则下的优化问题，只是不同的聚类方法其聚类谢谢阅读对象的属性值与目标函数不同。三维数据模糊聚类可以看作一个模糊聚类的一般模型。（对象、属性、情形）感谢阅读设三维数据由n个对象在T个时刻的p个属性的值构成。记为感谢阅读1,2,,n（即每时刻对应一张二维表）X(t)(xt)a1,2,,pia1,2,,Tt聚类的目的，就是将n个对象的集合O{o,o,,o}分成K个模糊聚类块12nC,C,,C。即C,C,,C是O{o,o,,o}上的模糊集合。这K个模糊集合12K12K12n的隶属函数即每个对象相对于聚类块的隶属度表示为U(u)，u0,K1，i1,2,,nnKuijijijj1时刻的聚类中心表示为v(t)(v(t)j ja

1,2,,T)j1,2,,Ka1,2,,p时刻的目标函数为,.J(t)(U,v(t))(u)t(x(t)v(t))2（按列求方差）Knpj1i1ija1iaja如果存在一个解(U,v)使得J(t)(t1,2,,T)最小，则(U,v)就是最优解。但通常这种感谢阅读最优解不存在，所以，三维数据聚类是一个多目标优化问题。设是可行解(U,v)的谢谢阅读集合，那么加权和的单聚类准则为J(U,v)Tw(t)J(t)(U,v(t))谢谢阅读18.5传递闭包法1）模糊相似系数的标定基于模糊相似关系的模糊聚类，首先是建立模糊相似矩阵，建立模糊相似矩阵的感谢阅读关键就是相似系数。相似系数反映了样本之间相对于某些属性的相似程度。确定相精品文档放心下载似系数的方法很多，可根据实际问题选择使用。设O{x,x,,x}为被分类对象的全体，以(x,x,,x)表示每一对象x的12ni1i2imi特征数据。常用的方法有：①数量积法1ijr1mijijxxMikjkk1mx)Mmax(xijikjkk1如果r中出现负值，可采用如下方法调整：ij法1：令r'r1ij，则r'[0,1]；ij2ij法2：令r'rm,ijijijMm其中，mminr，Mmaxr。于是r'[0,1]ijijijijij②夹角余弦法,.xxmrk1ikjk，当出现负数时，用上面的方法调整ijx2x2mmikjkk1k1③统计相关系数法m__(xx)(xx)rikijkjk1ijm_m_(xx)2(xx)2ikijkjk1k1其中，x_m，x_m。1x1ximikjmjkk1k1④最大最小法mx)(xikjkrk1ijmx)(xikjk1算术平均最小法mx)2(xrikjkk1ijmx)(xikjk1几何平均最小法m(x x)rk1ikjkxxijmikjk1绝对值指数法mre|xx|ikjkij⑧指数相似系数法1mij

me(xikxjk)2/sk21,.⑨绝对值倒数法1,ijM,ijrijm|xikxjk|k1其中，M适当选取，使r [0,1]且分开。ij⑩绝对值减数法mx|r1c|xijikjk1其中，c适当选取，使r [0,1]且分开。ij⑾非参数法令x'xx_，x'xx_ikikijkjkjn{x'x',x'x',,x'x'}中的正数个数iji1j1i2j2imjmn{x'x',x'x',,x'x'}中的负数个数iji1j1i2j2imjmr1(1nijnij)ij2nnijij⑿贴近度法如果把x,x的特征归一化，使x,x[0,1](k1,2,,m)，则x,x的相似ijikjkij程度取为其贴近度。距离贴近度为1c(d(x,x))aij i j其中，c,a为适当选择参数值；d(x,x)为模糊集各种距离，可以取闵可夫斯基距离：谢谢阅读ijm1d(x,x)(|xx|p)pijikjk1当p=1时为海明距离，p=2时为欧氏距离。,.⒀专家打分法请若干专家直接对x,x的相似程度打分，取其平均值作为r。感谢阅读i j ij上述方法均可建立模糊相似矩阵R(r) ，由于它满足对称性和自反性，不满谢谢阅读ij nn足传递性。所以还需建立一个Fuzzy等价阵，根据模糊等价阵才能聚类。谢谢阅读2）传递闭包法模糊相似矩阵R的传递闭包是指包含R的最小模糊等价矩阵。利用平方法可以求得模糊相似矩阵的传递闭包，其理论依据为精品文档放心下载定理：设R为n阶模糊相似矩阵，则存在一个最小自然数k(kn)，使得传递闭谢谢阅读t(R)Rk，且对一切大于k的自然数l，恒有RlRk。感谢阅读该定理说明，从模糊相似矩阵R出发，利用平方法依次计算R2,R4,,R2i，感谢阅读当第一次出现RkRkRk时，Rk就是传递闭包t(R)。计算方法为，设模糊相似矩阵R(r)，S(s)，则RS(t)，其中ijnnijnnijnntns)(rijk1ikkj计算量是n3～n3log n。23）动态直接聚类法基本概念：主元、双重主元、单重主元、填充替换、合并变换、清洗变换、分解精品文档放心下载集、连通元、连接元。定义1：设R(r) 为模糊相似矩阵，R的第i行非主对角线上的元素可写为感谢阅读ij nnr,r,,r,r,,r（1）i1i2i,i1i,i1in我们称式（1）中的最大元或重复出现的几个极大元中的最左侧的元素称为R的第i行感谢阅读主元。定义2：如果R(r) 为模糊相似矩阵，r为第i行第j列的主元，则称r为R谢谢阅读ij nn ij ij,.的双重主元。在R的主元中，非双重主元的主元称为R的单重主元。感谢阅读定义3：给定若干个两两不交的集合S,S,,S（2）12p若存在集合T{t,t}及式（2）中唯一集合S，使得ST，则用ST代替S。12kkkk称这种变换为T对式（2）进行填充变换。若存在集合T{t,t}及式（2）中两个集合S和S，使得ST，ST，12klkl则用SS代替S，并将S从式（2）中删除，得到新集合列的过程，称为T对式klkl（2）进行合并变换。若iS,jS，则在R中去掉r的过程，称为对R进行清理变换。klij定义4：假设R的各个双重主元的足码集合为S,S,,S（3）12p若R的各个双重主元的足码集对式（3）进行填充变换而得新的足码集，称为R的感谢阅读行标分解集。算法8.1 连接元算法①找出R的各个双重主元与单重主元，并写出R的行标分解集；谢谢阅读,H,,H1 2 p②如果i,jH(k1,2,,p)，且r不是R的双重主元与单重主元，我们称kij之为R的连通元。找出R的所有连通元；③在R的除去主元与连通元的元素中，取一个最大的元r，称为R的连接感谢阅读ij元，如果有几个可任取一个。如果已选取到p1个连接元，则算法停止；谢谢阅读否则转步骤下一步；④用连接元r对已有足码集进行合并变换，并对R进行清理变换，而后转步谢谢阅读ij,.骤③。定义5：R的双重主元、单重主元、连接元统称为R的基元。谢谢阅读算法8.2动态直接聚类法①建立模糊相似矩阵；②求R的基元；③画出动态聚类图，或以集合方式写出各水平下的聚类结果。谢谢阅读4）最大树法最大树法是我国学者吴望名提出的，它有两种算法：Prim法和Kruskal法。总感谢阅读体步骤为建立模糊相似矩阵；画出最大树；聚类算法1：Prim法设待分类对象的集合简记为｛１，２，３，４，５｝，给定的模糊相似矩阵为感谢阅读10.11R0.80.110.50.20.310.40.10.60.31（１） 先取对象１，在对象２，３，４，５中，找出与１相关系数最大感谢阅读的，这里0.8＝Ｒ(1,3)，画出下图：130.8在２，４，５中，找出与对象１的最大系数０.5=R(1,4)；找出与谢谢阅读对象３最大的相关系数0.3=R(3,4)，因为0.5>0.3，取对象４，精品文档放心下载得下图：40.510.83，再在２，５中找出与１，３，４最大谢谢阅读,.的相关系数，0.6=R(4,5)，得下图50.640.510.83感谢阅读最后找出２与１，３，４，５之间最大的相关系数０.4=R(2,5)，精品文档放心下载得最大树为20.450.640.510.83谢谢阅读（２） 取[0,1]，砍断连接权重小于的枝，就可得到一个不连通的图，感谢阅读而各连通分支就构成了水平上的分类。如，若取[0,0.4]，则只得一类｛１，２，３，４，５｝；精品文档放心下载若取(0.4,0.5]，则得两类｛２｝，｛１，３，４，５｝；感谢阅读若取(0.5,0.6]，则得三类｛２｝，｛４，５｝，｛１，３｝；精品文档放心下载若取(0.6,0.8]，则得四类｛２｝，｛５｝，｛４｝，｛１，３｝；谢谢阅读若取(0.8,1]，则得五类｛１｝，｛２｝，｛３｝，｛４｝，｛５｝谢谢阅读算法２：Ｋruskal法（１）先在Ｒ的非主对角线中找到最大元0.8=R(1,3)，得下图：感谢阅读30.81再找次最大元0.6=R(4,5)，0.５=R(１,４)，得下图：精品文档放心下载30.810.540.65感谢阅读最后得到0.４=R(２,５)，至此所有顶点都被连到，且不含圈，从谢谢阅读而得到最大树。30.810.540.650.42精品文档放心下载（２）以下算法同算法１中的步骤注：用上述两种方法得到的最大树可能不同，但可以证明其分类结果相同。用Ｐrim感谢阅读法至多需要进行3n3次运算，用Ｋruskal法至多需要进行n3～n3logn次运算。22,.传递闭包法和动态直接聚类法，以及最大树法的分类结果相同的。但动态直接聚感谢阅读类法计算量比较小。8.6系统聚类法是目前国内外使用最多的一种方法。其基本思想是：先将n个样本各自看成一类，然后规定样本之间的距离和类与精品文档放心下载类之间的距离。开始时，各个样本自成一类，类与类之间的距离与样本之间的距离谢谢阅读是相等的。选择距离最近的一对合并为一个新类。计算新类与其他类的距离，再将精品文档放心下载距离最近的两类合并，这样每次减少一类，直至所有的样品都归为一类为止。谢谢阅读类与类之间的距离定义多种多样，最常用的有8种之多，包括最短距离、最长谢谢阅读距离、中间距离、重心距离、类平均距离、可变类平均法、可变法、离差平方和法。谢谢阅读以上8种系统聚类法的并类原则和步骤是完全相同的，所不同的是类与类之间谢谢阅读的距离有不同的定义，从而得到不同的递推公式。Wishart在1969年把它们的递推精品文档放心下载公式统一了起来。为简单起见，这里只给出最短距离的步骤。感谢阅读1.最短距离法用d表示样本i与j的距离，C,C,表示类，定义类与类之间的距离为两类最谢谢阅读ij12近样品的距离，用D表示C与C之间的距离，则pqpqDmindpqijiCp,jCq用最小距离法聚类的算法步骤如下：①规定样本之间的距离，计算样本两两距离的对称阵，记为D，开始每个样(0)品自成一类，因此，DD；pqqp②选择D的最小元素，设为D，将C与C合并为一类，记为C{CC}；(0)pqpqrpq③计算新类与其他类之间的距离,.Dmindmin{mind,mind}min{D,D}rkijijijpkqkiC,jCkiC,jCkiC,jCkrpq将D中p,q行p,q列合并为一个新行新列。新行新列对应C，所得到的矩(0)r阵记为D；(1)④对D 重复上面对D的两步，得到D，如此下去直到所有元素聚为一类。精品文档放心下载(1) (0) (2)如果某一步中的最小元素不止一个，则对应之些最小元素的类同时合并。谢谢阅读最长距离法Dmaxdpqij3.中间距离法iCp,jCqD21D21D21D2kr2kp2kq4pq中间距离法的推广形式：D21D21D2D2,10kr2kp2kqpq44.重心距离法dpq _ _xpxq其距离推广公式为：D2npD2nqD2npnqD2krnkpnkqnnpqrrrr其中，类Cp与Cq的样本个数为np,nq。将Cp与Cq合并为Cr，则样本个数为n nnr p q类平均距离法D21d2pqnnqiC,jCijpqp其递推公式为D2npD2nqD2krnkpnkqrr可变类平均法,.D2np(1)D2nq(1)D22,1krnkpnkqDpq7.可变法rrD21[D2D2]2,12Dkrkpkqpq8.离差平方和法设将n个样品分成k类C,C,,C，用x表示C中的样品，n表示C中样12kitttt品的个数，x_是C的重心，则在C中的样品的整个类内距离差平方和是tttS(xx)'(xx)Skn__ktittitttWart提出如下算法：t1i1t1先将n个样品各自成一类；然后每次缩小一类，每缩小一类距离差平方和都要增加选择使S增加最小的两类合并，直到所有的样品归为一类为止。把两类合并所得的距离差平方和看成平方距离，则以下递推公式：谢谢阅读D2nnpD2nnqD2nD2kkkkrnnkpnnkqnnpprkrkrkWishart在1969年提出了系统聚类的统一公式为：精品文档放心下载D2D2D2D2|D2D2|,1感谢阅读kr p kp q kq pq kp kq其中，系统 , ,,对于不同方法有不同的取值。精品文档放心下载p q8.7C-均值聚类法C-均值聚类是一种简便实用的无监督学习算法，此种方法能够用于已知类数的谢谢阅读数据聚类和分类。其基本步骤如下：①选取聚类块数k；②从训练集中任意取定k个向量c,c,,c作为聚类中心；精品文档放心下载1 2 k,.③将每个样本向量x[x,x,,x]T，按下列欧氏距离归入中心为c类ll1l2lni中：||xc||min||xc||liljj④重新调整聚类中心c。令c[c,c,,c]'，其中c由下式计算得出：iii