聚类分析简介原理与应用

聚类分析陈龙震聚类分析聚类分析的简介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用户133用户255问题Q型与R型聚类区别？Q型聚类：当聚类把所有的观测记录（cases）进行分类时，它把性质相似的观测分在同一个类，性质差异较大的观测分在不同的类。R型聚类：当聚类把变量（variables）作为分类对象时。这种聚类用在变量数目比较多、且相关性比较强的情形，目的是将性质相近的变量聚类为同一个类，并从中找出代表变量，从而减少变量个数以达到降维的效果。系统聚类凝聚的：从点作为个体簇开始，每一步合并两个最接近的簇。这需要定义簇的临近性(类间距离)的概念。分裂的：从包含所有点的某个簇开始，每一步分裂一个簇，直到剩下单点簇。在这种情况下，我们需要确定我每一步分裂那个簇，以及如何分裂。系统聚类——方法最短距离法设两个类，分别含有n1和n2个样本点系统聚类——方法若某步聚类将

和

合并为新类,即,新类与其他类

间的距离递推公式为

系统聚类——方法最长距离法设两个类，分别含有n1和n2个样本点系统聚类——方法若某步聚类将

和

合并为新类,即,新类与其他类

间的距离递推公式为

系统聚类——方法重心法重心距离：两类中心分别为，则系统聚类——方法类平均法递推公式：推导：系统聚类——方法离差平方和设将n个样品分成k类G1，G2，…，Gk，用Xit表示Gt中的第I个样品，nt表示Gt中样品的个数，是Gt的重心，则Gt的样品离差平方和为系统聚类——方法递推公式上述的各种类间距离定义的递推公式可以统一成如下公式系统聚类书：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统计量系统聚类法的基本性质

在聚类分析过程中，并类距离分别为lk（k=1，2，3，…

）若满足，则称该聚类方法具有单调性。除了重心法和中间距离法之外，其他的系统聚类法均满足单调性的条件。单调性系统聚类法的基本性质空间的浓缩和扩张设有两种系统聚类法A和B，他们在第i步的距离矩阵分别为Ai和Bi（I=1，2，3…），若Ai>Bi，则称第一种方法A比第二种方法B使空间扩张，或第二种方法比第一种方法浓缩。

D（短）D（平），D（重）D（平）；D（长）

D（平）；方法的比较类平均法适中系统聚类局限样品一旦划到某个类以后就不变了，这要求分类方法比较准确样品数n很大时，系统聚类法的计算很庞大，从而使其不方便应用动态聚类解决的问题是：假如有个样本点，要把它们分为类，使得每一类内的元素都是聚合的，并且类与类之间还能很好地区别开。动态聚类使用于大型数据。动态聚类步骤动态聚类——凝聚点选择凭经验选择，如果对问题已经有一定的了解，可将所有的的样品大致分类，在每类选择一个有代表性的样品作为聚类点将所有的样品随机地分成k类，计算每一类的均值，将这些均值作为凝聚点采用最大最小原则，假设样品最终分为k类，先选择所有样品中相距最远的两个样品为凝聚点，即选择

，使.选择第三个凝聚点

与前面两个聚类点的距离最小者等于所有其余的样品与

的最小距离中最大的。动态聚类——k均值聚类动态聚类——k均值聚类不足凝聚点选择不当动态聚类——k均值聚类不足不同的簇动态聚类——k均值聚类不足离群点其他基于划分聚类算法（partitionclustering)k-means：是一种典型的划分聚类算法，它用一个聚类的中心来代表一个簇，即在迭代过程中选择的聚点不一定是聚类中的一个点，该算法只能处理数值型数据k-modes：K-Means算法的扩展，采用简单匹配方法来度量分类型数据的相似度k-prototypes：结合了K-Means和K-Modes两种算法，能够处理混合型数据k-medoids：在迭代过程中选择簇中的某点作为聚点，PAM是典型的k-medoids算法CLARA：CLARA算法在PAM的基础上采用了抽样技术，能够处理大规模数据CLARANS：CLARANS算法融合了PAM和CLARA两者的优点，是第一个用于空间数据库的聚类算法FocusedCLARAN：采用了空间索引技术提高了CLARANS算法的效率PCM：模糊集合理论引入聚类分析中并提出了PCM模糊聚类算法其他基于密度聚类算法：DBSCAN：DBSCAN算法是一种典型的基于密度的聚类算法，该算法采用空间索引技术来搜索对象的邻域，引入了“核心对象”和“密度可达”等概念，从核心对象出发，把所有密度可达的对象组成一个簇GDBSCAN：算法通过泛化DBSCAN算法中邻域的概念，以适应空间对象的特点DBLASD：OPTICS：OPTICS算法结合了聚类的自动性和交互性，先生成聚类的次序，可以对不同的聚类设置不同的参数，来得到用户满意的结果FDC：FDC算法通过构造k-dtree把整个数据空间划分成若干个矩形空间，当空间维数较少时可以大大提高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是样本构