聚类方法(Clustering) 周源20101206

聚类方法（Clustering）周源2010.12.06什么是聚类•聚类（Clustering）就是将数据分组成为多个类（Cluster）。在同一个类内对象之间具有较高的相似度，不同类之间的对象差别较大。聚类分析•对于一个数据，人们既可以对变量（指标）进行分类(相当于对数据中的列分类)，也可以对观测值（事件，样品）来分类（相当于对数据中的行分类）。•比如学生成绩数据就可以对学生按照理科或文科成绩（或者综合考虑各科成绩）分类，•当然，并不一定事先假定有多少类，完全可以按照数据本身的规律来分类。聚类的应用领域•经济领域：–帮助市场分析人员从客户数据库中发现不同的客户群，并且用购买模式来刻画不同的客户群的特征。–谁喜欢打国际长途，在什么时间，打到那里？–对住宅区进行聚类，确定自动提款机ATM的安放位置–股票市场板块分析，找出最具活力的板块龙头股–企业信用等级分类–……•生物学领域–推导植物和动物的分类；–对基因分类，获得对种群的认识•数据挖掘领域–作为其他数学算法的预处理步骤，获得数据分布状况，集中对特定的类做进一步的研究有贡献的研究领域•数据挖掘–聚类可伸缩性、各种各种复杂形状类的识别，高维聚类等•统计学–主要集中在基于距离的聚类分析，发现球状类•机器学习–无指导学习（聚类不依赖预先定义的类，不等同于分类）•空间数据技术•生物学•市场营销学聚类分析原理介绍•聚类分析中“类”的特征：–聚类所说的类不是事先给定的，而是根据数据的相似性和距离来划分–聚类的数目和结构都没有事先假定•聚类方法的目的是寻找数据中：–潜在的自然分组结构astructureof“natural”grouping–感兴趣的关系relationship聚类分析原理介绍•什么是自然分组结构Naturalgrouping?•我们看看以下的例子：•有16张牌•如何将他们分为一组一组的牌呢？AKQJ聚类分析原理介绍•分成四组•每组里花色相同•组与组之间花色相异AKQJ花色相同的牌为一副Individualsuits聚类分析原理介绍•分成四组•符号相同的牌为一组AKQJ符号相同的的牌Likefacecards聚类分析原理介绍•分成两组•颜色相同的牌为一组AKQJ颜色相同的配对Blackandredsuits聚类分析原理介绍本章要介绍的分类的方法称为聚类分析（clusteranalysis）。对变量的聚类称为R型聚类，而对观测值聚类称为Q型聚类。这两种聚类在数学上是对称的(两个状态具有同等价值和相同的权重，例如性别的两个状态：男和女)，没有什么不同。相似性Similar的度量（统计学角度）•距离Q型聚类–主要用于对样本分类–常用的距离有（只适用于具有间隔尺度变量的聚类）：•明考夫斯基距离（包括：绝对距离、欧式距离、切比雪夫距离）•兰氏距离•马氏距离•斜交空间距离•此不详述，有兴趣可参考《应用多元分析》（第二版）王学民•相似系数R型聚类–用于对变量分类，可以用变量之间的相似系数的变形如1－rij定义距离–这里不详细介绍这种聚类度量方法聚类分析原理介绍变量按测量尺度（MeasurementLevel）分类•间隔（Interval）尺度变量–连续变量，如长度、重量、速度、温度等•有序（Ordinal）尺度变量–等级变量，不可加，但可比，如一等、二等、三等奖学金•名义（Nominal）尺度变量–类别变量，不可加也不可比，如性别、职业等聚类分析原理介绍•当对象是同时被各种类型的变量描述时，怎样描述对象之间的相异度呢？•一种可取的办法是把所有变量一起处理，将不同类型的变量组合在单个相异矩阵中，把所有有意义的变量转换到【0，1】的区间上，只进行一次聚类分析。详见参考书主要聚类算法的分类•划分方法（partitioningmethod）•层次的方法（也称系统聚类法）（hierarchicalmethod）•基于密度的方法（density-basedmethod）•基于网格的方法（grid-basedmethod）•基于模型的聚类方法（model-basedmethod）•聚类高维数据•基于约束的聚类分析•离群点分析其中，前两种算法是利用统计学定义的距离进行度量划分方法•1典型的划分方法：k均值和k中心点•2大型数据库的划分方法：从k中心点到CLARANS•思想：–随机选择k个对象，每个对象初始地代表一个类的平均值或中心，对剩余每个对象，根据其到类中心的距离，被划分到最近的类；然后重新计算每个类的平均值。不断重复这个过程，直到所有的样本都不能再分配为止。划分方法•特点：–k事先定好–创建一个初始划分，再采用迭代的重定位技术–不必确定距离矩阵–比系统聚类法运算量要小，适用于处理庞大的样本数据–适用于发现球状类•缺陷：–不同的初始值，结果可能不同–有些k均值算法的结果与数据输入顺序有关，如在线k均值算法–用爬山式技术（hill-climbing）来寻找最优解，容易陷入局部极小值划分方法•K-均值首先，随机地选择k个对象，每个对象代表一个簇的初始均值或中心。对剩余的每个对象，根据其与各个簇均值的距离，将它指派到最相似的簇。然后计算每个簇的新均值。这个过程不断重复，直到准则函数收敛。•EM(Expectation-Maximization,期望最大化)算法与K均值算法将每个对象指派到一个簇相反。在EM算法中，每个对象按照权重指派到每个簇，其中权重表示对象的隶属概率。换句话说，在簇之间没有严格的边界。因此，新的均值基于加权的度量值来计算。划分方法•K-均值–硬聚类–计算每个类的中心•EM算法特点：1.我们从初始迭代直到收敛2.是局部最优3.K均值是用EM算法求解高斯混合分布的特例K-均值•将n个向量分到k个类别中去•选择k个初始中心•计算两项距离•计算均值K-均值算法层次方法•1凝聚和分裂层次类聚•2BIRCH：利用层次方法的平衡迭代规约和聚类•3ROCK：分类属性的层次聚类算法•4Chameleon：利用动态建模的层次聚类算法层次的方法（也称系统聚类法）（hierarchicalmethod）•定义：对给定的数据进行层次的分解：•分类：凝聚的（agglomerative）方法（自底向上）（案例介绍）思想：一开始将每个对象作为单独的一组，然后根据同类相近，异类相异的原则，合并对象，直到所有的组合并成一个，或达到一个终止条件为止。–每一项自成一类–迭代，将最近的两类合为一类分裂的方法（divisive）（自顶向下）思想：一开始将所有的对象置于一类，在迭代的每一步中，一个类不断地分为更小的类，直到每个对象在单独的一个类中，或达到一个终止条件。–将所有项看作一类–找出最不相似的项分裂出去成为两类层次的方法（也称系统聚类法）（hierarchicalmethod）•特点：–类的个数不需事先定好–需确定距离矩阵–运算量要大，适用于处理小样本数据层次的方法缺陷：一旦一个步骤（合并或分裂）完成，就不能被撤销或修正，因此产生了改进的层次聚类方法，如BRICH,BURE,ROCK,Chameleon。详见参考书广泛采用的类间距离：•最小距离法（singlelinkagemethod）–极小异常值在实际中不多出现，避免极大值的影响广泛采用的类间距离：•最大距离法（completelinkagemethod）–可能被极大值扭曲，删除这些值之后再聚类广泛采用的类间距离：•类平均距离法（averagelinkagemethod）类间所有样本点的平均距离–该法利用了所有样本的信息，被认为是较好的系统聚类法广泛采用的类间距离：•重心法（centroidhierarchicalmethod）–类的重心之间的距离–对异常值不敏感，结果更稳定类的相似度度量•我们可以知道两个项之间的相似度，但是聚类要求知道类与类之间的相似度•三种方法：–单连接方法–全连接方法–组平均方法类的相似度度量-单连接方法：使用最小距离d(Ci,Cj)衡量簇间距离，有时称它为最近邻聚类算法。当最近的簇之间的距离超过某个任意的阀值时聚类过程就会终止。如果我们把数据点看作图的节点，图中的边构成簇内节点间的路径，由于连接簇的边总是从一个簇通向另一个簇，结果图将形成一颗树，使用最小距离度量的凝聚层次聚类算法也称为最小生成树算法。–全连接方法:使用最大距离d(Ci,Cj)度量簇间距离时，有时称为最远邻聚类算法。当最近的簇之间的最大距离超过某个任意的阀值时聚类过程就会终止，则称其为全连接算法。通过把数据点看作图中的节点，用边来连接节点，我们可以把每个簇看成是一个完全图，也就是说，簇中所有的节点都有边来连接。–组平均方法：最小和最大度量代表了簇间距离度量的两个极端。它们趋向对离群点或噪声数据过分敏感。使用均值距离或平均距离是对最小和最大距离之间的一种折中方法，而且可以克服离群点敏感性问题。基于密度的方法•1DBSCAN：一种基于高密度连通•2OPTICS：通过点排序识别聚类结构•3DENCLUE：通过密度分布函数的聚类•思想：–只要临近区域的密度超过一定的阀值，就继续聚类•特点：–可以过滤噪声和孤立点outlier，发现任意形状的类基于网格的方法•1STING：统计信息网格•2WaveCluster：利用小波变换聚类•把样本空间量化为有限数目的单元，形成一个网络结构，聚类操作都在这个网格结构（即量化空间）上进行。•优点：处理速度很快，其处理时间通常独立于数据对象的数目，仅依赖于量化空间中每一维的单元书目。基于模型的聚类方法•1期望最大化方法•2概念聚类•3神经网络方法•为每个类假定一个模型，寻找数据对给定模型的最佳拟合。聚类高维数据•1CLIQUE：维增长子空间聚类方法•2PROCLUS：维归约子空间聚类方法•3基于频繁模式的聚类方法很多应用需要对包含大量特征项或者维数的对象进行分析。例如，文本文档可能包含成千上万个词条作为特征项，DNA微阵列数据可以在数以百计的条件下提供关于数以千计的基因表达水平信息。基于约束的聚类分析•1含有障碍物的对象聚类•2用户约束的聚类分析•3半监督聚类分析是一种结合用户指定或面向应用的约束进行聚类的方法。约束表达了用户的期望，或者是描述了期望的聚类结果所具有的性质，并且提供与聚类过程通信的有效手段。可以指定各种各样的约束，或者由用户指定，或者作为应用需求来指定。离群点分析•1基于统计分布的离群点分析•2基于距离的离群点检测•3基于密度的局部离群点检测•4基于偏差的离群点检测Thankyou!