R语言-聚类分析.ppt

聚类的基本步骤,什么是类：粗略地讲，相似样品（或指标）的集合成为类。聚类的两个基本步骤邻近度度量的选择：检验每一对观测值（对象）取值的相似性。一个相似性（邻近度）的度量定义为对象间的“接近”程度。越接近越同质。组别构建算法的选择：根据邻近度的度量，被分配到各组的对象间的差别变大，而被分配到同一组的观测值应尽可能接近。,关于聚类：聚类应用领域,仓储管理：对不同类的商品在入库过程中进行聚类储存营销:发现客户集群并进行直销和重组天文:发现相似恒星群以及星系群地震研究:观测到的地震震源应聚集在大陆断层带基因分析:发现具有相似表达式的基因群,关于聚类：探索性的分析方法,作为一种探索性技术，Everitt(1993)评价到：“聚类方法基本上是用于产生一些假设而不是检验假设”。有多少作聚类分析的人就有多少聚类方法。,聚类的分类：划分聚类方法层次聚类方法密度聚类方法网格聚类方法模型聚类方法,在基于划分的聚类中，任务就是将数据划分成K个不相交的点集，使每个子集中的点尽可能同质。基于划分的方法，其代表算法有k-means算法、K-medoids等,划分聚类方法,k-means算法,k-means算法基本步骤从n个数据对象任意选择k个对象作为初始聚类中心；根据每个聚类对象的均值(中心对象)，计算每个对象与这些中心对象的距离；并根据最小距离重新对相应对象进行划分；重新计算每个(有变化)聚类的均值(中心对象)；计算标准测度函数，当满足一定条件，如函数收敛时，则算法终止；如果条件不满足则回到步骤2。,k-means优缺点,主要优点：是解决聚类问题的一种经典算法，简单、快速。对处理大数据集，该算法是相对可伸缩和高效率的。当结果簇是密集的，它的效果较好。主要缺点在簇的中心（平均值）被定义的情况下才能使用。必须事先给出k（要生成的簇的数目），而且对初值敏感，对于不同的初始值，可能会导致不同结果。不适合于发现非凸面形状的簇或者大小差别很大的簇。而且，它对于“躁声”和孤立点数据是敏感的。,层次聚类方法,层次聚类方法对给定的数据集进行层次的分解，直到某种条件满足为止。具体又可分为：凝聚的层次聚类：一种自底向上的策略，首先将每个对象作为一个簇，然后合并这些原子簇为越来越大的簇，直到某个终结条件被满足。分裂的层次聚类：采用自顶向下的策略，它首先将所有对象置于一个簇中，然后逐渐细分为越来越小的簇，直到达到了某个终结条件。层次凝聚的代表是AGNES算法。层次分裂的代表是DIANA算法。,层次聚类优缺点,层次聚类方法是不可逆的，也就是说，当通过凝聚式的方法将两组合并后，无法通过分裂式的办法再将其分离到之前的状态，反之亦然。另外，层次聚类过程中调查者必须决定聚类在什么时候停止，以得到某个数量的分类。在不必要的情况下应该小心使用层次聚类方法。,1、距离的定义,距离的定义有很多，但是必须遵循一定的规则。假设表示样本之间的距离，则一般要求它满足如下条件：（1）对一切i,j都大于等于0（2）等于0当且仅当i=j（3）对一切i和j可以互换（4）如果距离的定义仅满足前三条，则称此距离为广义距离。常用的距离有，明氏距离，兰氏距离，马氏距离，斜交空间距离，列名变量的相似性度量。,2、常用的距离,明氏距离,特别地，当k1时，即为绝对值距离,(1)明氏距离,设原始数据为,明氏距离,当k2时，即为欧氏距离,当k时，即为切比雪夫距离,欧氏距离,切比雪夫距离,例：,明考夫斯基距离有以下两个缺点：,明氏距离的数值与指标的量纲有关。当各变量的测量值相差悬殊时，常发生“大数吃小数”的现象，为消除量纲的影响，通常先将每个变量进行标准化。明氏距离的定义没有考虑各个变量之间相关性的影响。,(2)标准化的欧氏距离,设原始数据为,(3)马氏距离马氏距离是由印度著名统计学家马哈拉诺比斯(Mahalanobis)所定义的一种距离，其计算公式为：,=,马氏距离又称为广义欧氏距离。马氏距离考虑了观测变量之间的相关性。如果假定各变量之间相互独立，即观测变量的协方差矩阵是对角矩阵，此时马氏距离就是标准化的欧氏距离。马氏距离不受指标量纲及指标间相关性的影响,系统聚类法,系统聚类法的基本思想先将n个样品各自看成一类，然后规定样品之间的“距离”和类与类之间的距离。选择距离最近的两类合并成一个新类，计算新类和其它类（各当前类）的距离，再将距离最近的两类合并。这样，每次合并减少一类，直至所有的样品都归成一类为止。,系统聚类法的基本步骤：1.计算n个样品两两间的距离，记作D=。2.构造n个类，每个类只包含一个样品。3.合并距离最近的两类为一新类。4.计算新类与各当前类的距离。5.重复步骤3、4，合并距离最近的两类为新类，直到所有的类并为一类为止。6.画聚类谱系图。7.决定类的个数和类。,最短距离法最长距离法中间距离法重心法类平均法离差平方和法（Ward法）,系统聚类方法：,上述6种方法归类的基本步骤一致，只是类与类之间的距离有不同的定义。,定义类p与q之间的距离为两类最近样品的距离，即,一、最短距离法,设类p与q合并成一个新类，记为k，则k与任一类r的距离是,例最短距离法,设抽取5个样品，每个样品观察2个指标，：您每月大约喝多少瓶啤酒，：您对“饮酒是人生的快乐”这句话的看法如何？观察数据如下，对这5个样品分类。,2.合并距离最小的两类为新类，按顺序定为第类。,3、计算新类与各当前类的距离，,得距离矩阵如下：,为最小，=,4、重复步骤2、3，合并距离最近的两类为新类，直到所有的类并为一类为止。,6、按聚类的过程画聚类谱系图,4,5,并类距离,3,1,2,7、决定类的个数与类。,观察此图，我们可以把5个样品分为3类，,二、最长距离法,定义类p与q之间的距离为两类最远样品的距离，即,三、中间距离法,定义类与类之间的距离既不采用两类之间最近的距离，也不采用两类之间最远的距离，而是采用介于两者之间的距离，故称为中间距离法。,四、重心法（Centroid),五、类平均法（Average),定义两类之间的距离平方为这两类元素两两之间距离平方的平均,六、差平方和法（Ward法）,反映样品之间的差异程度,设变量X的n个样品观察值为：,n个样品的离差平方和为：,直观上容易想到把两群样品聚为一大群，大群的离差平方和将超过原来两个群的离差平方和之和。,如果将p和q并类得到新类k，则类k的离差平方和为,把增加的量记为,定义类p和q之间的距离为：,动态聚类法-K均值法,系统聚类法是一种比较成功的聚类方法。然而当样本点数量十分庞大时，则是一件非常繁重的工作，且聚类的计算速度也比较慢。比如在市场抽样调查中，有4万人就其对衣着的偏好作了回答，希望能迅速将他们分为几类。这时，采用系统聚类法就很困难，而动态聚类法就会显得方便，适用。动态聚类适用于对大型数据的聚类。,动态聚类法,基本思想：选取若干个样品作为凝聚点，计算每个样品和凝聚点的距离，进行初始分类，然后根据初始分类计算其重心，再进行第二次分类，一直到所有样品不再调整为止。,选择凝聚点,分类,修改分类,分类是否合理,分类结束,Yes,No,用一个简单的例子来说明动态聚类法的工作过程。例如我们要把图中的点分成两类。快速聚类的步骤：1、随机选取两个点和作为凝聚点。2、对于任何点，分别计算3、若，则将划为第一类，否则划给第二类。于是得图（）的两个类。,4、分别计算两个类的重心，则得和，以其为新的凝聚点，对空间中的点进行重新分类，得到新分类。,c,(b)任取两个凝聚点,（a）空间的群点,(e)第二次分类,动态聚类法,优点：计算量小，方法简便，可以根据经验，先作主观分类。缺点：结果受选择凝聚点好坏的影响，分类结果不稳定。,选择凝聚点和确定初始分类,凝聚点就是一批有代表性的点，是欲形成类的中心。凝聚点的选择直接决定初始分类，对分类结果也有很大的影响，由于凝聚点的不同选择，其最终分类结果也将出现不同。故选择时要慎重通常选择凝聚点的方法有：(1)人为选择，当人们对所欲分类的问题有一定了解时，根据经验，预先确定分类个数和初始分类，并从每一类中选择一个有代表性的样品作为凝聚点。(2)重心法将数据人为地分为A类，计算每一类的重心，将重心作为凝聚点。,第一、选择凝聚点第二、初始分类对于取定的凝聚点，视每个凝聚点为一类，将每个样品根据定义的距离向最近的凝聚点归类。第三、修改分类得到初始分类，计算各类的重心，以这些重心作为新的凝聚点，重新进行分类，重复步骤2，3，直到分类的结果与上一步的分类结果相同，表明分类已经合理为止。,动态聚类法的基本步骤：,划分聚类方法层次聚类方法密度聚类方法：基于密度的聚类方法以数据集在空间分布上的稠密程度为依据进行聚类，无需预先设定簇的数量，因此特别适合对于未知内容的数据集进行聚类。网格聚类方法模型聚类方法,密度聚类方法,基于密度方法的聚类,密度聚类方法的指导思想是，只要一个区域中的点的密度大于某个域值，就把它加到与之相近的聚类中去。对于簇中每个对象，在给定的半径的邻域中至少要包含最小数数目（MinPts）个对象。这类算法能克服基于距离的算法只能发现“类圆形”的聚类的缺点，可发现任意形状的聚类，且对噪声数据不敏感。代表算法有：DBSCAN、OPTICS、DENCLUE算法等。,基于密度方法的聚类-DBSCAN,DBSCAN（Density-BasedSpatialClusteringofApplicationswithNoise）一个比较有代表性的基于密度的聚类算法。与层次聚类方法不同，它将簇定义为密度相连的点的最大集合，能够把具有足够高密度的区域划分为簇，并可在有“噪声”的空间数据库中发现任意形状的聚类。,传统基于中心的密度定义为：数据集中特定点的密度通过该点半径之内的点计数(包括本身)来估计。显然，密度依赖于半径。,传统的密度定义：基于中心的方法,基于密度方法的聚类-DBSCAN所用到的基本术语,定义对象的-邻域：给定对象在半径内的区域。定义核心对象：如果一个对象的-邻域至少包含最小数目MinPts个对象，则称该对象为核心对象。例下图中，=1cm，MinPts=5，q是一个核心对象。定义直接密度可达：给定一个对象集合D，如果p是在q的-邻域内，而q是一个核心对象，我们说对象p从对象q出发是直接密度可达的。例在下图中，=1cm，MinPts=5，q是一个核心对象，对象p1从对象q出发是直接密度可达的。,基于密度方法的聚类-DBSCAN所用到的基本术语,密度可达,定义密度可达的：如果存在一个对象链p1，p2，pn，p1=q，pn=p，对piD，（1=i=n），pi+1是从pi关于和MitPts直接密度可达的，则对象p是从对象q关于和MinPts密度可达的。例在下图中，=1cm，MinPts=5，q是一个核心对象，p1是从q关于和MitPts直接密度可达，p是从p1关于和MitPts直接密度可达，则对象p从对象q关于和MinPts密度可达的,基于密度方法的聚类-DBSCAN所用到的基本术语,图密度相连,图噪声,定义噪声:一个基于密度的簇是基于密度可达性的最大的密度相连对象的集合。不包含在任何簇中的对象被认为是“噪声”。边界点：边界点不是核心点，但落在某个核心点的邻域内。噪声就是那些既不是边界点也不是核心点的对象,定义密度相连的：如果对象集合D中存在一个对象o，使得对象p和q是从o关于和MinPts密度可达的，那么对象p和q是关于和Mi