聚类分析简介原理与应用.ppt

按一下以編輯母片標題樣式,按一下以編輯母片,第二層,第三層,第四層,第五層,*,聚类分析,陈龙震,聚类分析,聚类分析的简介,Q型聚类统计量,距离,R型聚类统计量,相似系数,系统聚类,动态聚类,k均值聚类,其他,聚类分析的定义,聚类分析是研究如何研究对象,(,样品或变量,),按照多个方面的,特征,进行综合,分类,的一种多元统计方法，它是根据物以类聚的原理将相似的样品,(,或变量)归为一类。,聚类和分类有什么区别？,无监督学习,与分类判别不同，进行聚类前并不知道将要划分成几个组和什么样的组，也不知道根据哪些空间区分规则来定义组,商业,聚类分析被用来发现不同的客户群，并且通过购买模式刻画不同的客户群的特征。聚类分析是细分市场的有效工具，同时也可用于研究消费者行为，寻找新的潜在市场、选择实验的市场，并作为多元分析的预处理。,聚类分析,主要应用,聚类分析,主要应用,生物,聚类分析被用来动植物分类和对基因进行分类，获取对种群固有结构的认识,Q型聚类统计量与R型聚类统计量,设有容量为n的样本观测数据,观测矩阵为：,样本,变量,Q型聚类,R型聚类,变量之间的聚类即R型聚类分析，常用相似系数来测度变量之间的亲疏程度。,样品之间的聚类即Q型聚类分析，常用距离来测度样品之间的亲疏程度。,Q型聚类统计量,距离,明氏距离测度,明考夫斯基,(,Minkowski,),距离,设 和,是第i和 j 个样品的观测值则二者之间的距离为：,当,时，绝对值距离,当,时，欧氏距离,当,时，切比雪夫距离,记,切比雪夫距离证明,Q型聚类统计量,距离,国际象棋棋盘上二个位置间的切比雪夫距离是指王要从一个位子移至另一个位子需要走的步数。由于王可以往斜前或斜后方向移动一格，因此可以较有效率的到达目的的格子。上图是棋盘上所有位置距,f6,位置的切比雪夫距离。,Q型聚类统计量,距离,明氏距离两个缺点：,明氏距离的值与各指标的量纲有关,明氏距离的定义没有考虑各个变量之间的相关性和重要性。,明氏距离是把各个变量都同等看待，将两个样品在各个变量上的离差简单地进行了综合。,兰氏距离,马氏距离,Q型聚类统计量,距离,这是印度著名统计学家马哈拉诺比斯,(P,C,Mahalanobis),所定义的一种距离，其计算公式为：,分别表示第,i,个样品和第,j,样品的,p,指标观测值所组成的列向量，即样本数据矩阵中第,i,个和第,j,个行向量的转置，,表示观测变量之间的协方差短阵。在实践应用中，若总体协方差矩阵,未知，则可用样本协方差矩阵作为估计代替计算。,R,型聚类统计量,相似系数,相似系数,设 和,是第 和 个样品的观测值，则二者之间的相似,测度为,:,R,型聚类统计量,夹角余弦,夹角余弦,夹角余弦时从向量集合的角度所定义的一种测度变量之间亲疏程度的相似系数。设在,n,维空间的向量,问题,马（欧）氏距离和余弦相似度的区别,问题,适用于何种不同的数据分析模型,欧氏距离能够体现,个体数值特征的绝对差异,，所以更多的用于需要从维度的数值大小中体现差异的分析，如使用用户行为指标分析用户价值的相似度或差异,余弦相似度更多的是从方向上区分差异，而对绝对的数值不敏感，更多的用于使用用户对内容评分来区分用户兴趣的相似度和差异，同时,修正,了用户间可能存在的,度量标准不统一,的问题（因为余弦相似度对绝对数值不敏感）,商品1,商品2,用户1,3,3,用户2,5,5,问题,Q型与R型聚类区别？,Q型聚类：当聚类把所有的观测记录（cases）进行分类时，它把性质相似的观测分在同一个类，性质差异较大的观测分在不同的类。,R型聚类：当聚类把变量variables）作为分类对象时。这种聚类用在变量数目比较多、且相关性比较强的情形，目的是将性质相近的变量聚类为同一个类，并从中找出代表变量，从而减少变量个数以达到降维的效果。,系统聚类,凝,聚的：从点作为个体簇开始，每一步合并两个最接近的簇。这需要定义簇的临近性(类间距离)的概念。,分裂的：从包含所有点的某个簇开始，每一步分裂一个簇，直到剩下单点簇。在这种情况下，我们需要确定我每一步分裂那个簇，以及如何分裂。,系统聚类,方法,最短距离法,设两个类 ，分别含有n1和n2个样本点,系统聚类,方法,若某步聚类将,和,合并为新类,即,新类 与其他类,间的距离递推公式为,系统聚类,方法,最长距离法设两个类 ，分别含有n1和n2个样本点,系统聚类,方法,若某步聚类将,和,合并为新类,即,新类 与其他类,间的距离递推公式为,系统聚类,方法,重心法,重心距离：两类中心分别为 ，则,系统聚类,方法,类平均法,递推公式：,推导：,系统聚类,方法,离差平方和,设将,n,个样品分成,k,类,G,1,，,G,2,，,，,G,k,，用,X,it,表示,G,t,中的第,I,个样品，,n,t,表示,G,t,中样品的个数，是,G,t,的重心，则,G,t,的样品离差平方和为,系统聚类,方法,递推公式,上述的各种类间距离定义的递推公式可以统一成如下公式,系统聚类,书：175页例子,系统聚类,类的个数确定,给定阈值：,通过观测聚类图，给出一个合适的阈值T。要求类与类之间的距离不要超过T值。例如我们给定T=0.3，当聚类时，类间的距离已经超过了0.3，则聚类结束。,系统聚类,半偏相关,半偏相关统计量,其中,T,是数据的总离差平方和，是组内离差平方和。,比较大，说明分,G,个类时类内的离差平方和比较小，也就是说分,G,类是合适的。但是，分类越多，每个类的类内的离差平方和就越小，也就越大；所以我们只能取合适的,G,，使得,足够大，而,G,本身很小,，随着,G,的增加，的增幅不大。比如，假定分,4,类时，,=0.8,；,下一次合并分3类时,下降了许多，,=0.32,，则分,4,类是合适的。,系统聚类,半偏相关系统聚类,伪F统计量,伪F统计量,伪,F,统计量用于评价聚为,G,类的效果。如果聚类的效果好，类间的离差平方和相对于类内的离差平方和大，所以应该取伪,F,统计量较大而类数较小的聚类水平。,其中T是数据的总离差平方和，是类内离差平方和,系统聚类,伪F统计量,伪 统计量的定义为,其中 和 分别是的类内离差平方和，,是将K和L合并为第,M,类的离差平方和,=-,为合并导致的类内离差平方和的,增量,。用它,评价合并第,K,和,L,类的效果，伪 统计量大说,明不应该合并这两类，应该取合并前的水平。,系统聚类,伪 统计量,系统聚类,CCC统计量,立方聚类准则,其中,，v是方差稳定化变换，一般取值为,一般由,维空间的均匀分布得到。一般选择,后的第一个局部极大值点对应的分类数。,系统聚类,CCC统计量,系统聚类法的基本性质,在聚类分析过程中，并类距离分别为,l,k,（,k=1,，,2,，,3,，,）若满足 ，则称该聚类方法具有单调性。除了重心法和中间距离法之外，其他的系统聚类法均满足单调性的条件。,单调性,系统聚类法的基本性质,空间的浓缩和扩张,设有两种系统聚类法,A,和,B,，他们在第,i,步的距离矩阵分别为,A,i,和,B,i,（,I=1,，,2,，,3,），若,A,i,B,i,，则称第一种方法,A,比第二种方法,B,使空间扩张，或第二种方法比第一种方法浓缩。,D（短）D（平），D（重）D（平）；,D（长）,D（平）；,方法的比较,类平均法适中,系统聚类局限,样品一旦划到某个类以后就不变了，这要求分类方法比较 准确,样品数n很大时，系统聚类法的计算很庞大，从而使其不方便应用,动态聚类,解决的问题是：,假如有个样本点，要把它们分为类，使得每一类内的元素都是聚合的，并且类与类之间还能很好地区别开。动态聚类使用于大型数据。,动态聚类步骤,动态聚类,凝聚点选择,凭经验选择，如果对问题已经有一定的了解，可将所有的的样品大致分类，在每类选择一个有代表性的样品作为聚类点,将所有的样品随机地分成k类，计算每一类的均值，将这些均值作为凝聚点,采用最大最小原则，假设样品最终分为k类，先选择所有样品中相距最远的两个样品为凝聚点，即选择,，使,.,选择第三个凝聚点,与前面两个聚类点的距离最小者等于所有其余的样品与,的最小距离中最大的。,动态聚类,k,均值聚类,动态聚类,k,均值聚类不足,凝聚点选择不当,动态聚类,k,均值聚类不足,不同的簇,动态聚类,k,均值聚类不足,离群点,其他,基于划分聚类算法（partition clustering),k-means,：,是一种典型的划分聚类算法，它用一个聚类的中心来代表一个簇，即在迭代过程中选择的聚点不一定是聚类中的一个点，该算法只能处理数值型数据,k-modes,：,K-Means,算法的扩展，采用简单匹配方法来度量分类型数据的相似度,k-prototypes,：,结合了,K-Means,和,K-Modes,两种算法，能够处理混合型数据,k-medoids,：,在迭代过程中选择簇中的某点作为聚点，,PAM,是典型的,k-medoids,算法,CLARA,：,CLARA,算法在,PAM,的基础上采用了抽样技术，能够处理大规模数据,CLARANS,：,CLARANS,算法融合了,PAM,和,CLARA,两者的优点，是第一个用于空间数据库的聚类算法,Focused CLARAN,：,采用了空间索引技术提高了,CLARANS,算法的效率,PCM,：,模糊集合理论引入聚类分析中并提出了,PCM,模糊聚类算法,其他,基于密度聚类算法：,DBSCANDBSCAN,算法是一种典型的基于密度的聚类算法，该算法采用空间索引技术来搜索对象的邻域，引入了,“,核心对象,”,和,“,密度可达,”,等概念，从核心对象出发，把所有密度可达的对象组成一个簇,GDBSCAN,：,算法通过泛化,DBSCAN,算法中邻域的概念，以适应空间对象的特点,DBLASD,：,OPTICS,：,OPTICS,算法结合了聚类的自动性和交互性，先生成聚类的次序，可以对不同的聚类设置不同的参数，来得到用户满意的结果,FDC,：,FDC,算法通过构造,k-d tree,把整个数据空间划分成若干个矩形空间，当空间维数较少时可以大大提高,DBSCAN,的效率,其他,基于层次聚类算法：,CURE,：,采用抽样技术先对数据集,D,随机抽取样本，再采用分区技术对样本进行分区，然后对每个分区局部聚类，最后对局部聚类进行全局聚类,ROCK,：,也采用了随机抽样技术，该算法在计算两个对象的相似度时，同时考虑了周围对象的影响,CHEMALOEN,（变色龙算法）：,首先由数据集构造成一个,K-,最近邻图,Gk,再通过一个图的划分算法将图,Gk,划分成大量的子图,每个子图代表一个初始子簇,最后用一个凝聚的层次聚类算法反复合并子簇，找到真正的结果簇,SBAC,：,SBAC,算法则在计算对象间相似度时，考虑了属性特征对于体现对象本质的重要程度，对于更能体现对象本质的属性赋予较高的权值,BIRCH,：,BIRCH,算法利用树结构对数据集进行处理，叶结点存储一个聚类，用中心和半径表示，顺序处理每一个对象，并把它划分到距离最近的结点，该算法也可以作为其他聚类算法的预处理过程,BUBBLE,：,BUBBLE,算法则把,BIRCH,算法的中心和半径概念推广到普通的距离空间,BUBBLE-FM,：,BUBBLE-FM,算法通过减少距离的计算次数，提高了,BUBBLE,算法的效率,其他,STING,：,利用网格单元保存数据统计信息，从而实现多分辨率的聚类,WaveCluster,：,在聚类分析中引入了小波变换的原理，主要应用于信号处理领域。（备注：小波算法在信号处理，图形图像，加密解密等领域有重要应用，是一种比较高深和牛逼的东西）,CLIQUE,：,是一种结合了网格和密度的聚类算法,OPTIGRID,：,基于网格的聚类算法：,基于统计学的聚类算法,：,COBWeb,：,COBWeb,是一个通用的概念聚类方法，它用分类树的形式表现层次聚类,CLASSIT,：,AutoClass,：,是以概率混合模型为基础，利用属性的概率分布来描述聚类，该方法能够处理混合型的数据，但要求各属性相互独立,R软件与聚类分析,在,R,软件中，,dist(),函数给出了各种距离的计算结果，其使用格式是,其中,x,是样本构成的数据矩阵（样本按行输入）或数据框。,Method,表示计算距离的方法，缺省值为,Euclide,距离,距离,-enclidean,-maximum,-manhattan,-canberra,-minkowski,例题一,例题二,对305名女中学生测量八个体型指标，相应的相关矩阵如下表所示，将相关系数看成相似系数，,用最长距离法做系统分析，,定义距离为:d=1-r,例题三,K-均值方法（kmeans()函数）对例一给出的31个省、市、自治区的消费水平进行聚类分析。,参考文献,1 吴密霞,刘春玲.多元统计分析M.北京：科学出版社,2014,:1,6,8-187,.,2,李素兰.数据分析与R软件M.北京：科学出版社,2013,:1,57-172.,3,Pang-Ning Tan,Micheal Steibach,Vipin Kumar,范明,范宏建等译.数据挖掘导论M.北京：人民邮电出版社,2007,:,305,-,326.,4,聚类分析：刘荣海 董佳伟,宿柯 陆昕辰,孔玲钰 卢丹丹 董萌,