《《聚类分析读书报告》》由会员分享，可在线阅读，更多相关《《聚类分析读书报告》（17页珍藏版）》请在金锄头文库上搜索。
1、聚类分析读书报告王晨研数理15351152209008基本原理聚类问题实际上是将一组数据分成若干个组， 每个组里的对象具有很大的相 似性，不同的组之间存在尽量大的差异性。 在这些组之间寻找数据之间内在的联 系。这个过程实际上是一中在无监督状态下寻找最优划分的过程。聚类有效性的评价可以参考以下几个指标：聚类质量的度量、聚类算法与某种数据集适合的程 度、划分的最佳聚类数目。聚类分析的内容十分丰富，一般情况下按方法可以分 为以下几种：系统聚类法，调优法（动态聚类法），最优分割法（有序样品聚类法）, 模糊聚类法，图论聚类法，聚类预报法。按照分类对象的不同可以分为 R型和Q 型两大类，R型是对变量进行分
2、类，Q型是对样品进行分类。聚类分析就是用数学方法研究和处理给定对象的分类。 聚类问题是一个久远 的问题，是随着人类的产生和社会的发展而不断深化的一个问题。 人们要认知世 界、改变世界就要区分不同的事物并感知存在丁不同事物间的相似性。经典分类学是从单对象或有限的几个对象出发，单凭经验或专业知识对事物进行分类。这种分类具有的优点是界限非常活晰。但是，随着人们认识的加深， 发现这种分类常常不适用丁具有模糊性的分类问题。如把人按漂亮分为“漂亮的 人，“不漂亮的人”。这就产生了经典分类方法解决不了的问题一如何判定某个人 的类别。由此产生了模糊聚类分析，应用模糊聚类得到了对象届丁不同类别的不 确定性程度，
3、表达了样本类届的中介性，更能客观地反映现实世界。我们把应用 普通数学方法进行分类的聚类方法称为普通聚类分析，而把应用模糊数学方法进行分析的聚类分析称为模糊聚类分析。1.1三种类的定义：【定义一】设阈值T是给定的正数，若集合 G中任何两个元素的距离 由都 满足：dj T (i, j G),则称G对丁阈值T组成一个类。【定义二设阈值T是给定的正数，若集合G中每个i G都满足：1 dn Tlim , n 1 j g x其中，n是集合G中元素的个数，则称G对丁阈值T组成一个类。【定义三】设T和H (H T)是两个给定的正数，如果集合 G中两两元素距 离的平均满足：jGd L 4I G)，其中n是集合G
4、中元素的个数，则称G对丁阈值T , H组成一个类。1.2类的性质特征:设类G包含的样品为X(1), X,.,X(n),其中X(t)(t 1,2,., n)为m元总体的样本，可以从不同角度来刻画G :(D1 nG的重心(或称均值)：XG X(2)样本离差阵AG及样本协方差阵SG分别为:n 1Ag Xg气(3)类的直径：用Dg表示类G的直径，通常用以下来表示直径n Dg (X(t)XG)(X(t)Xg) tr(AG) t 1Dgmax di ,G i,j G i,j，距离与相似系数对样品进行分类，就需要研究它们之间的关系，现在用的较 多的是距离和相似系数。1.3距离把n个样品看成是m维空间中的n个
5、点，那么两个样品问的相似系数用di,j度量。一般要求:di,j0,对任意 i,j；当 di,j 0X(o乂;dij dji，对任意 i, j ;dij dik dkj ,对任意 i,j,k。1.3.1 明氏(Minkowski )距离dj(q)Xit t1 /q q(i, j1,2,.,n),1时的一阶明氏距离为dj(1)Xit t(i, j 1,2,.,n)即绝对距离2 时，dj(2)当趋丁 时，dj()Xitt1/22(i, j 1,2,., n),即欧氏距离max Xit t 1 t m(i, j 1,2,., n),即为切比雪夫距离。1.3.2 马氏(Mahalanobis)距离马氏距
6、离是1936年印度的马哈拉诺比斯提出的，具有很重要的作用。为指标的协方差阵,(ij)pp ,其中,ij1(XiXi)(X j ),(i,j 1,2,., p)Xi当-1存在时，则dj(M) (Xi)1(Xi)为马氏距离。样品X到总体G的马氏距离定义为d2(X,G) (X )1(X )，其中 为 总体的均值向量。1.3.3 兰氏(Canberra) 距离Xit t1 dij(L)-兰氏距离是由兰思和威廉姆斯所给定的一种距离。其计算公式为:、， i, j 1,2,.,nm i 1 (Xitxp1.3.4杰氏距离杰氏距离是由杰斐瑞和马突斯塔提出的。计算公式为：1dij(J)QXk 区)k 21.3.
7、5斜交空间距离由丁变量之间往往存在着不同的相关关系，正交空间的距离计算样本空间易 变性，可以采用斜交空间距离。1 P P12dij 2(Xih h)(Xik k)rhkP n 1 k 11.4相似系数为了将样品进行分类，研究样品之间的关系，采用相似系数的方法；性质接 近的样品，相似系数就越接近1或者-1,而无关系的样品的相关系数就越接近0.比较相似的样品归为一类，不相似的样品归届不同的类。设Cj1 Xi a (a 0为常数)；Cij 1 ,对任意i, j均成立；Cij Cji ,对任意i, j均成立。这里Cj的绝对值越接近1，表示Xi和越相似。反之，两者关系疏远。常用的相似系数有：火角余弦Cj
8、 (1) cos j当Xi和平行式，火角j0,Xi和正交时，火角j 90, Cj(1)相关系数nCj k1n(Xki k 1Cij (2) 1表示两个向量线性相关。指数相似系数Cj (3)非参数方法令 Xij nXkk,kn.Xikk,k相似系数定义为CjnXkiXkj k 1 1nn222XkiXkjk 1k 1Cj(1) 1,说明这两个向量完全相似；当0 ,说明这两个向量不相关(Xki Xi)(Xkj )n12一、2,一 、2Xi)(Xkj)k 13(*k Q2i m-1o4skem k 11, ,m中大丁 0勺个数1, ,m中小丁 0勺个数当非负时，有三种相似系数:Cij(5)mmin(
9、Xik,k) k 1 mmaX Xk,k) k 1m min(Xik,k)Cij(6)Cijk 11 m-(Xik k)2 k 1mmin(Xik,k) k 1m xikx jkk 1 Cij (8)联列系数1.5聚类分析的性质1.5.1单调性设Dk为系统聚类中第k次并类时的距离。如果D1 D2 D3,则称它具 有单调性。在聚类方法当中，可以证明的是只有重心法和中间距离法不具有单调 性。图2为一个等角三角形，两个腰长为1.1,底边是1,则第一次A , B并为 一类，并类的距离几=l,第二次并类的距离是C至AB中点的距离，它是AB边 的高，它等丁 J1.12-0.52 0.98 D2 D10所以
10、重心法不能够满足单调性。1.5.2空间的浓缩与扩张设两个同阶矩阵D(A)和D(B)。如果D(A)的每一个元素不小丁 D(B)相应元 素，则记为D(A) D(B)。特别的如果矩阵D的元素非负，则有D 0.如果D(A) 0 , D(B) 0 , D2(A)表示 将D(A)的每一个元素平方，则D(A) D(B) D2(A) D2(B)。 令 D(A, B) D2(A) D2(B), 则D A,B 0 D(A) D(B)若有两个系统聚类法A,B ,在第k步距离阵记为D(Ak)和 D(Bk) (k 0,1,2, ,n 1),若D(Ak,Bk) 0则称A比B使空间扩张或B比A使空 间浓缩。这种性质称为最长
11、距离法比最短距离法扩张；或最短距离法比最长距离法浓缩。基本方法聚类方法主要有划分聚类法、层次聚类法和密度聚类法、基丁网格的方法和 基丁模型的方法等。2.1层次聚类CURE算法层次聚类方法是一种目前应用较广的聚类技术， 是一种针对大型数据库的高 效的聚类算法，可为用户提供多种可选的聚类结果，可以随时完成聚类实施过程。 CURE, ROCK和CHAMELEON算法是聚合聚类中最具代表性的三个方法。Guha等人在1998年提出了 CURE算法。该方法选择数据空间中固定数目 的、具有代表性的一些点共同来表示相应的类，这样就可以识别具有复杂形状和 不同大小的聚类，找到更合适的孤立点。 ROCK算法是对C
12、URE的改进，适用 丁类别届性的数据。CHAMELEON算法是KaryPis等人丁 1999年提出来的，它在聚合聚类的过 程中利用了动态建模的技术。例如在“自底向上”方案中，初始时每一个数据纪 录都组成一个单独的组，在接下来的迭代中,它把那些相互邻近的组合并成一个 组，直到所有的记录组成一个分组或者某个条件满足为止。它是一种分裂的层次聚类。CURE采用了用多个点代表一个簇的方法，可以较好的处理以上问题。并且在处理大数据量的时候采用了随机取样，分区的方法，来提高其效率，使得其可以高效的处理大量数据。算法分为以下六步：(1) 从原始数据中抽取一个随机样本 S。(2) 将样本S分割为一组划分。(3)
13、 对每个划分局部的聚类。(4) 通过随机取样剔除孤立点。如果一个类增长太慢，就去掉它。(5) 对局部的类进行聚类。落在每个新形成的类中的代表点根据用户定义的一个收缩因子收缩或向类中心移动。这些点代表和捕捉到了类的形状。(6) 用相应的类标签来标记数据。CURE算法的思想主要体现在如下几个方面：(1) CURE算法采用的是聚结层次聚类。把每一个对象设立为一个类，随即根据相似点对它们进行合并。(2) CURE算法采用分割方法，先把样本分割为几块然后针对各个部分中的对象分别进行局部聚类，形成子类。再对子类进行聚类，形成新的类。2.2 BIRCH 方法BIRCH(Balanced Iterative
14、Reducing and clustering using Hierarchies)是专门针对大规模数据集提出的聚集型层次聚类算法，它综合了层次凝聚和迭代的重定位方法。首先用自底向上的层次算法，然后用迭代的重定位来改进结果。它的主要思想是：扫描数据库，建立一个初始存放丁内存中的聚类特征树，然后对聚类特征树的叶结点进行聚类。聚类特征的定义(CF): 一个聚类特征(CF)是一个三元组(N , LS, SS),其中N是簇中的点的数目，LS是N个点的线性和，SS是N个点的平方和。聚类特征树的定义(CF树):一颗CF树是一个带有分支因子B的平衡树,每一个内部结点对丁每一个子结点都包含一个 CF三元组。每个叶结点也代表-个簇，并且对丁其中每一个子簇都包含一个 CF条目。在叶结点中的子簇要有一个不超过给定阈值T的直径。合并假定：假定n(n 2)个簇Ci进
