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

1、第8章模糊聚类8.1概述聚类是人类一项最基本的认识活动，如“物以类聚，人以群分”。所谓聚类就是 按照事物的某些属性，把事物聚集成类，使类间的相似性尽量小，类内的相似性尽 量大。其数学描述为设给定数据集合V Vi |i 1,2, ,n，其中Vi为数据对象，根据数据对象间的相似程度将数据集合分成k组Cj | j 1,2,k，并满足:Cj VCi C jk1Ci则该过程称为聚类,Ci,(i1,2,n)称为簇。聚类的基本方法经常是定义两个对象之间的距离，也可采用不依赖于距离的方 法：首先定义一个优化目标，再优化得到某个局部最小值聚类与分类区别：聚类是一个无监督的学习过程，属观察学习；而分类是有监督 的

2、学习过程，属示例学习。它们的 根本区别在于，分类时需要事先知道分类所依据数值属性和符的属性值，而聚类是要找到这个分类的属性值。一般属性值有两类: 号属性。关于数值属性聚类方法很多，而对符号属性聚类方法较少，常是将其转化 为数值后再处理。聚类分析目前已广泛应用于诸多领域， 包括模式识别、数据分析、图像处理、自 动控制以及市场研究等。通过聚类，人们能够识别密集的和稀疏的区域，因而发现 全局的分布模式，以及数据属性之间的有趣的相互关系。8.2聚类方法的分类聚类分析方法很多，通常是针对数据库中的记录，根据一定的分类规则，合理地划分记录集合，确定每个记录所在类别(如，k-平均算法、k-中心点算法、基于凝

3、聚的层次聚类和基于分裂的层次聚类等)。一般来说，对于相同的数据集，若采用不 同的聚类方法，可能有不同的划分结果。(1) 按聚类的标准分，有统计聚类方法和概念聚类方法统计聚类方法：基于相似性测量。包括系统聚类法、分解法、加入法、 动态聚类法、有序样品聚类、重叠聚类和模糊聚类等。这种聚类方法是 一种基于全局比较的聚类，它需要考察所有个体才能决定类的划分。因 此，它要求所有的数据必须预先给定，而不能动态增加新的数据对象。概念聚类方法：基于对象具有的概念。这里的距离不再是统计方法中的 几何距离，而是根据概念的描述来确定的。典型的概念聚类或形成方法 有：COBWEB、OLOC和基于列联表的方法。(2)

4、按聚类的对象分，有数值聚类方法和符号值聚类方法数据聚类方法：所分析的数据的属性为数值数据，因此可对所处理的数 据直接比较大小;符号值聚类方法：所分析的数据的属性为符号数据，因此对所处理的数 据不能直接比较大小。(3) 按聚类尺寸分，有基于距离聚类、基于密度聚类和基于连续的聚类基于距离的聚类：根据数据之间的距离进行聚类。这种算法对于噪声数 据和孤立点数据比较敏感;基于密度的聚类：该方法认为簇是具有相同密度的连通区域。 因此，密 度聚类需要扫描整个数据集，将数据空间划分为不同的小方格，并使用 小方格的并来近似表示簇。该方法有可能不够精确，但该方法对于噪声 数据和孤立点不敏感。该方法也可利用空间索引

5、结构，通过计算超球区 内的密度进行聚类，但该方法因为要维护复杂的索引结构， 故对于海量 数据存在效率问题;基于连续的聚类：将聚类对象映射为图模型或超图模型， 然后根据边或 者超边寻找连通的结点集合。8.3常用的聚类算法聚类问题本质上是一个优化问题，即通过一种迭代运算使得系统的目标函数达 到一个极小值。该目标函数为划分的评价函数。通常采用 距离作为划分的评价标准, 对数值属性主要采用欧氏距离，而对符号属性则通常采用 Hamming 距离。基于划分的聚类算法通过优化一个评价函数把数据集划分为k个部分。当采用聚类内的距离的平方作为评价函数时，聚类内的所有点向聚类中心汇集，因此采用基 于距离的划分评价

6、函数方法得到的聚类是球形的。一般，不同的评价函数会优先选 择不同的聚类结构。(1)k-平均方法k-平均法是一种常用的基于划分的聚类方法。它根据最终分类的个数k随机地选取k个初始聚类中心，不断地迭代，直至达到目标函数的最小值，即得到最终的聚 类结果为止。其中，目标函数通常采用平方误差准则，即kE|P mi I2i 1 p Ci这里，P为聚类对象；mi为类Ci的各聚类对象(样本)的平均值。即PP Cimi |Ci 1该方法在每一次迭代中，要计算每一个点和各聚类中心的距离， 并将距离最近的聚类作为该点所属的类。所以k-平均法的算法复杂度为0(knt)，其中，k-聚类数;n-结点数；t-迭代次数。k-

7、平均法是解决聚类问题的一种经典算法，是一种爬山式搜索算法。优点：算法简洁、快速。缺点：对初值敏感，且易陷入局部最优。(2)k-中心点方法与k平均法的算法过程相似。唯一不同之处就是聚类中心的计算和表达。k -中心点法是用类中最靠近中心的一个样本来代表该类。k-中心点法最初随机选择k个中心点，然后反复地试图找出更好的中心点。k-中心点法的核心是中心点的选择。 假设聚类C原先的中心点Oc_old，现拟改为可能引起各样本所属聚类的情Oc_new，则根据样本属于和其距离最近的聚类的原则,况发生调整。对于原先聚类 C中的任意样本Pi可能有两种情况:Pi和Oc_new的距离仍然小于和其他各聚类的中心点的距离

8、，因此Pi仍属于聚类聚类c ；Pi和其他某一聚类r的中心点的距离最短，则Pi将改属于聚类r ；假如Oc_new使得总的距离平方和下降，则Oc_new代替Ooid成为聚类C的新聚类中 心，反之，则说明Oc_new目前不适合作为聚类 C的新的聚类中心，重新试探其他的点。相比于k-平均法，k-中心点算法对于噪声数据和异常数据不敏感，但计算量比k-平均算法要大。（3 ）层次聚类层次的方法是对给定数据对象集合进行层次的分解。层次聚类的基本思想是：将模式样本按距离准则逐步聚类，直到满足分类要求为止。其聚类过程可表示为一个 二叉层次树，叶结点表示一个样本，中间结点表示将数据集分割为两个不同的类, 或一个类由

9、它的两个子类合并而成。在层次聚类方法中，一旦一个步骤（合并或分裂）完成，它就不能被撤消。这既是优点，不用担心组合数目的不同选择，计算代价会较小；同时又是缺点，不能更 正错误的决定。根据层次聚类的分解形成原理， 层次聚类的方法可以分为凝聚方法和分裂方法。a）凝聚方法也称为自底向上方法。一开始将每个对象作为单独的一个类， 然后相继地合并相 近的对象或组，将较小的数据对象子集合依据相似程度进行合并，这些小的数据对 象子集合逐渐合并成较大的数据对象子集合，直到所有的类合并为一个，或者达到 一个终止条件为止，从而构成一个类的层次。假设Ci和Cj是两个聚类，则两类间的最短距离定义为D (Ci ,C j)

10、min d Pi, pj其中，Pi Ci， Pj C j， d p i, Pj表示样本Pi和Pj间的距离。凝聚方法的算法描述为For i=1,2 ,n令Ci Pi；While存在一个以上的聚类 doIf D(Ci,Cj) thenCi Ci C j ;删除Cj；采用凝聚方法的典型聚类算法有:BIRCH、CURE、CHAMELON 等。b）分裂方法也称自顶向下方法。一开始将所有的对象置于一个类中，在迭代的每一步中,一个类被分裂为更小的类，直到每个对象在单独的一个类中，或者达到一个终止条件为止。通常情况下，凝聚方法优于分裂方法。DIANA是分裂方法的代表。8.4模糊聚类在客观世界中，存在着大量的界

11、限模糊并不分明的聚类问题,如区分“年青人”和“中年人”时就需要模糊的划分，由此诞生了模糊聚类。模糊聚类的开创性工作是由 Ruspini于1969年提出的,是基于Zadeh教授1965年提出的模糊集合论。之后，Bezdek和Dunn于1987年提出了 C-均值模糊聚类法。目前，有关模糊聚类的方法很多，并已应用于生物学、商业、经济、工程、信息科学、医药学等许多领域。常用的模糊聚类方法有：系统聚类法、传递闭包法以及与此等价的最大支撑树的Prim算法及Kruskal算法、动态直接聚类法，基于摄动的模糊聚类法FCMBP、模糊C-均值法、模糊ISODATA算法、人工神经网络模糊聚类法等。聚类算法分为分割和

12、分层两种。分割聚类算法通过优化目标函数，把数据集分割成若干部分，如模糊k-均值聚类法。分层聚类是由不同层次的分割聚类组成，层次之间的分割具有嵌套的关系，如传递闭包法和摄动的模糊聚类法FCMBP。1 ）聚类结果的表示通常的聚类是把含n个对象的集合划分成K个不相交的部分，称之为 聚类块。聚类的结果可表示为一个n K阶矩阵U （Uj）nK，其中1,Uij 0,聚类块j聚类块jKUij 1,j 11,2, ,n; j 1,2, K（说明每个元素属于且仅属于1个聚类）Uj 0,1模糊聚类的结果表示，就是将上面通常的聚类结果表示替换为使Uj 0,1,i 1,2,n；1,2,K2）模糊聚类的一般模型聚类问题

13、实质上是在一定的聚类准则下的优化问题， 只是不同的聚类方法其聚类 对象的属性值与目标函数不同。三维数据模糊聚类可以看作一个模糊聚类的一般模型。（对象、属性、情形）设三维数据由n个对象在T个时刻的P个属性的值构成。记为i1,2,n（即每时刻对应一张二维表）X(t)(x：a) a 1,2,t1,2,T聚类的目的，就是将 n个对象的集合O01,02,0n分成K个模糊聚类块C1 , C2 , CK。即 C1, C2 , C K 是 0o1,02 ,On上的模糊集合。这K个模糊集合的隶属函数即每个对象相对于聚类块的隶属度表示为KU(uij ) n K， u ij 0,u ij 1 ， i 1,2, nj

14、 1t时刻的聚类中心表示为1,2,T1,2,K1,2,Pt(t)Z (t) Vj)(V#)jat时刻的目标函数为K npJ(U,v)(Uj )t阳v；：)2(按列求方差)j 1 i 1a 1如果存在一个解(U,v)使得J(t 1,2,T)最小，则(U,v)就是最优解。但通常这种最优解不存在，所以，三维数据聚类是一个多目标优化问题。设是可行解(U,v)的 集合，那么加权和的单聚类准则为TJ(U,v)w J (U,v(t)t 18.5传递闭包法1)模糊相似系数的标定基于模糊相似关系的模糊聚类,首先是建立模糊相似矩阵，建立模糊相似矩阵的关键就是相似系数。相似系数反映了样本之间相对于某些属性的相似程度

15、。确定相 似系数的方法很多，可根据实际问题选择使用。设O X1 , X2 , ,Xn为被分类对象的全体，以(Xi1,Xi2, ,Xim)表示每一对象Xj的 特征数据。常用的方法有:1rj丄M 数量积法mXikXjkk 1 mM max(XikXjk)i j k 1j如果rj中出现负值，可采用如下方法调整:rijrii1'-j-，则 rj0,1；rijrj m .,iM m其中，m min rj，max rii。于是 rj0,1 夹角余弦法mXikXjkk 1mk 统计相关系数法m(Xik k 1mV (XikV k 1_ 1 m - 其中，XiXik， Xjm k 1Xi)(Xjk X

16、j)rij- m -2 2Xi) J(XjkXj)I k 11 mXjk om k 1最大最小法m(XikXjk)k 1rij (XikXjk)k 1算术平均最小法m2(XikXjk)k 1rijm(Xik Xjk)k 1几何平均最小法m(Xik Xjk)k 1rijmJXikX jkk 1绝对值指数法m|Xkrije k1xjk|指数相似系数法rijN，当出现负数时，用上面的方法调整2Xjk(XkXjk)2/si1绝对值倒数法rij1,Mm|Xik Xjk |k 1其中，M适当选取，使rj0,1且分开。绝对值减数法mrj 1 c|XikXjkk 1(11)(12)其中，c适当选取，使非参数法

17、令Xiknijnijrijrij0,1且分开。XikXi，XjkXiiXji,Xi2Xj2,XiiXji,Xi2Xj2,1nij nij尹b贴近度法Xjk Xj,XimXjm中的正数个数,XimXjm中的负数个数如果把Xi,Xj的特征归一化，使Xik ,Xjk 0,1 (k 1,2, m)，则Xi,Xj的相似程度取为其贴近度。距离贴近度为rj1 c(d(Xi ,Xj)a其中，c,a为适当选择参数值;1 Xjk |ppd(Xi,Xj)为模糊集各种距离，可以取闵可夫斯基距离:md(Xi,Xj)(|Xikk 1(13)专家打分法请若干专家直接对Xi，Xj的相似程度打分，取其平均值作为rj。上述方法均

18、可建立 模糊相似矩阵R (rij)nn，由于它满足对称性和自反性，不满 足传递性。所以还需建立一个 Fuzzy等价阵，根据模糊等价阵才能聚类。2)传递闭包法模糊相似矩阵R的传递闭包是指包含R的最小模糊等价矩阵。利用平方法可以 求得模糊相似矩阵的传递闭包，其理论依据为定理：设R为n阶模糊相似矩阵，则存在一个最小自然数k(k n)，使得传递闭Rk。包t(R) Rk，且对一切大于k的自然数I，恒有R'该定理说明，从模糊相似矩阵 R出发，利用平方法依次计算 R2,R基本概念：主元、双重主元、单重主元、填充替换、合并变换、清洗变换、分解集、连通元、连接元。定义1:设R (rij)n n为模糊相似

19、矩阵，R的第i行非主对角线上的元素可写为ri1, ri2, ri,i 1, ri,i 1,环我们称式(1)中的最大元或重复出现的几个极大元中的最左侧的元素称为R的第i行主元。, ,R2i当第一次出现Rk Rk Rk时，Rk就是传递闭包t(R)。计算方法为，设模糊相似矩阵R(rij )n n，S(Sj )n n，则RS (t j ) n n，其中ntij k 1（rik定义2 :如果R (rij)n n为模糊相似矩阵，rj为第i行第j列的主元，则称为Rj）计算量是nn3 log 2 n。的双重主元。在R的主元中，非双重主元的主元称为 R的单重主元。定义3 :给定若干个两两不交的集合S1 , S2

20、 , Sp若存在集合Tt1,t2及式（2）中唯一集合Sk，使得Sk T ，则用Sk T代替Sk。称这种变换为T对式（2）进行填充变换。，S|T对式若存在集合T ti,t2及式（2）中两个集合Sk和Si，使得SkT 则用Sk S1代替Sk，并将S1从式（2）中删除，得到新集合列的过程，称为（2）进行合并变换。若i Sk, jSl，则在R中去掉rij的过程，称为对R进行清理变换。定义4 :假设R的各个双重主元的足码集合为S1, S2 , Sp若R的各个双重主元的足码集对式（3）进行填充变换而得新的足码集，称为行标分解集。算法8.1连接元算法找出R的各个双重主元与单重主元，并写出 R的行标分解集;H

21、1,H2, ,Hp如果i,j Hk（k 1,2, p），且rij不是R的双重主元与单重主元，我们称 之为R的连通元。找出R的所有连通元;在R的除去主元与连通元的元素中，取一个最大的元 rij，称为R的连接 元，如果有几个可任取一个。如果已选取到 P 1个连接元，则算法停止;否则转步骤下一步;用连接元rij对已有足码集进行合并变换，并对R进行清理变换，而后转步骤。定义5 : R的双重主元、单重主元、连接元统称为R的基元。算法8.2动态直接聚类法 建立模糊相似矩阵; 求R的基元; 画出动态聚类图，或以集合方式写出各水平下的聚类结果。4)最大树法最大树法是我国学者吴望名提出的,它有两种算法:Prim

22、 法和Kruskal法。总体步骤为建立模糊相似矩阵;画出最大树;聚类算法1 : Prim法设待分类对象的集合简记为1,2,3,4,51，给定的模糊相似矩阵为10.1R 0.80.50.310.10.20.410.30.110.6 1(1) 先取对象1,在对象2,3,4,5中,找出与1相关系数最大的，这里0.8 = R (1,3)，画出下图:10.83在2,4,5中，找出与对象1的最大系数0.5=R(1,4);找出与对象3最大的相关系数 0.3=R(3,4)，因为0.5>0.3，取对象4,得下图：40.510.83，再在2,5中找出与1 ,3,4最大的相关系数，0.6=R(4,5)，得下图

23、50.640510.83最后找出2与1,3,4,5之间最大的相关系数0.4=R(2,5),得最大树为20.450640.510.83(2) 取0,1,砍断连接权重小于 的枝，就可得到一个不连通的图,而各连通分支就构成了 水平上的分类。如，若取0,0.4，则只得一类1,2,3,4,5若取(040.5，贝U得两类2 , 1,3,4,5若取(0.5,0.6，则得二类2 , 4,若取(0.6,0.8，则得四类2 , 5若取(0.8,1，贝U得五类1 , 2,算法2 : K ruskal法，得下图:得下图:(1)先在R的非主对角线中找到最大元0.8=R(1,3)30.81再找次最大元 0.6=R(4,5

24、) , 0. 5 =R( 1 ,4 ),传递闭包法和动态直接聚类法，以及最大树法的分类结果相同的。但动态直接聚 类法计算量比较小。8.6系统聚类法是目前国内外使用最多的一种方法。其基本思想是：先将n个样本各自看成一类，然后规定样本之间的距离和类与 类之间的距离。开始时，各个样本自成一类，类与类之间的距离与样本之间的距离 是相等的。选择距离最近的一对合并为一个新类。计算新类与其他类的距离，再将 距离最近的两类合并，这样每次减少一类，直至所有的样品都归为一类为止。类与类之间的距离定义多种多样，最常用的有8种之多，包括最短距离、最长距离、中间距离、重心距离、类平均距离、可变类平均法、可变法、离差平方

25、和法。以上8种系统聚类法的并类原则和步骤是完全相同的，所不同的是类与类之间 的距离有不同的定义，从而得到不同的递推公式。Wishart在1969年把它们的递推 公式统一了起来。为简单起见，这里只给出最短距离的步骤。1.最短距离法用dj表示样本i与j的距离，Ci,C2,表示类，定义类与类之间的距离为两类最 近样品的距离，用Dpq表示Cp与Cq之间的距离，则Dpq mndij用最小距离法聚类的算法步骤如下:规定样本之间的距离，计算样本两两距离的对称阵，记为 D(0)，开始每个样 品自成一类，因此，Dpq Dqp ；选择D(0)的最小元素，设为Dpq，将Cp与Cq合并为一类，记为CrCp Cq； 计

26、算新类与其他类之间的距离Drk min dij min.巴讥 dij'min dij minD卩“将D（0）中p,q行p,q列合并为一个新行新列。新行新列对应 Cr，所得到的矩 阵记为D（i）； 对D（i）重复上面对D（o）的两步，得到D（2），如此下去直到所有元素聚为一类。如果某一步中的最小元素不止一个,则对应之些最小元素的类同时合并。2.最长距离法D pqmaxdij3.中间距离法lDk2p中间距离法的推广形式：DkrlDkqPpq44.重心距离法DkrDkqDiq,D pqd _ _Xp Xq其距离推广公式为:5.DkrnrC C其中，类 p与q的样本个数为类平均距离法nrnp

27、nqDPqniD2Dkqnrn p , nqnp nqnr nrCCCp与q合并为Cr，则样本个数为。将DPqdi2npnq i Cp，j Cq其递推公式为Dkr3Sp nrriD2Ukq nr6.可变类平均法17.可变法Dkrnpr2丄(1 )Dkp nrn q22(1 )DkqDpq,nrDkr一 DkpDkq D2pq，8.离差平方和法设将n个样品分成k 类 C1 , C2,Ck，用Xit表示Ct中的样品，nt表示Ct中样品的个数，Xt是Ct的重心，则在Ct中的样品的整个类内距离差平方和是k nt_S(XitXt)'(Xit Xt)t 1 i 1kStt 1Wart提出如下算法:

28、先将n个样品各自成一类;然后每次缩小一类，每缩小一类距离差平方和都要增加选择使S增加最小的两类合并，直到所有的样品归为一类为止。把两类合并所得的距离差平方和看成平方距离，则以下递推公式:Wishart 在 1969,2nknp,2 nknq,2D kr D kp D kqnrnknrn年提出了系统聚类的统一公式为：k2kD 2 D ppnr nk其中，系统2 2 2 2DkrpDkp qDkq Dpq对于不同方法有不同的取值。I DipDkq |,8.7 C-均值聚类法C-均值聚类是一种简便实用的无监督学习算法，此种方法能够用于已知类数的数据聚类和分类。其基本步骤如下:选取聚类块数k ； 从训练集中任意取定k个向量C1,C2, ,Ck作为聚类中心; 将每个样本向量xlxl1 ,xl2, xln T，按下列欧氏距离归入中心为Ci类中:l|Xl Ci|min HX cj| 重新调整聚类中心Ci。令CiCi1,Ci2, ,Cin'，其中Cim由下式计算得出:xlimNi为第i个聚类块中的向量数X|Cluster iCim-N-如果步骤中的聚类中心（Ci,i 1,2, ,k ）不再变化就终止，否则转步骤;上述方法是一种迭代算法，可以采用下面的目标函数进行迭代:nJ|Xk Ci |2k 1 xk Ci其中，Ci是中心为Ci的聚类块。上述算法过程中，每调整一个样本的类别，各类