R语言大数据分析与挖掘 课件 第十章 聚类算法

第10章聚类算法内容要点1、了解聚类算法的相关理论。2、掌握R语言K均值聚类算法建模的方法。3、掌握R语言凝聚式层次聚类算法建模的方法。聚类算法概述K均值聚类算法凝聚式层次聚类算法123聚类算法概述聚类分析（ClusterAnalysis）指将物理或抽象对象的集合分组为由类似的对象组成的多个类的分析过程。聚类结果一般分为4～6类。聚类分析的目的在于将相似的事物归类，同一类中的个体有较大的相似性，不同类的个体差异性很大。两个个体间（或变量间）的对应程度或联系紧密程度可以用两种方式来测量。（1）采用描述个体对（变量对）之间的接近程度的指标，

例如，“距离”越小的个体（变量）越具有相似性。（2）采用表示相似程度的指标，例如，“相关系数”越大的个体（变量）越具有相似性。聚类算法概述聚类算法的类型（1）层次聚类与划分聚类：若允许簇具有子簇，则我们得到一个层次聚类。层次聚类是嵌套簇的集族，组织成一棵树。划分聚类简单地将数据对象划分成不重叠的子集（簇），使得每个数据对象恰在一个子集中。（2）互斥聚类、重叠聚类与模糊聚类：互斥聚类指每个对象都指派到单个簇。重叠聚类或模糊聚类用来反映一个对象同时属于多个组的事实。在模糊聚类中，每个数据对象以一个0和1之间的隶属权值属于每个簇。每个对象与各个簇的隶属权值之和往往是1。（3）完全聚类与部分聚类：完全聚类将每个对象指派到一个簇中。部分聚类中，某些对象可能不属于任何组，如一些噪声对象。聚类算法概述聚类算法评估的特点不同聚类算法的目标函数相差比较大，没有统一的评价标准。聚类不像分类有一个最优化目标和学习过程，聚类只是一个统计方法，把相似和不相似的数据分开。在很多实际问题中，聚类仅仅是其中的一步，聚类的目的只是观察其是否对最终结果产生好的影响。在数据质量高的情况下，一个好的聚类结果表明了数据中相对稳定的某种模式或者分布，这种现象不会因为个别数据点的变化而改变，并且能够尽可能将数据分开。12K均值聚类算法K均值聚类算法（K-MeansClusteringAlgorithm）是一种迭代求解的聚类分析算法，其步骤是，预将数据分为K组，则随机选取K个对象作为初始的聚类中心，然后计算每个对划分方法概述划分方法是首先创建K个划分，K为要创建的划分个数；然后利用一个循环定位技术将对象从一个划分移到另一个划分来帮助改善划分质量。典型的划分方法包括K-Means、K-Medoids、CLARA、CLARANS、FCM。K均值聚类算法的优缺点1．优点（1）速度快。（2）计算简便。2．缺点（1）必须提前知道数据有多少类/组。（2）K-Medians是K-Means的一种变体，是用数据集的中位数而不是均值来计算数据的中心点。（3）K-Medians计算中位数时需要对数据集中的数据进行排序，速度相对于K-Means较慢。K均值聚类算法K均值聚类算法的流程K均值聚类算法，是聚类算法中最为基础但也最为重要的算法。其算法流程如下。（1）选取数据空间中的K个对象并将其作为初始中心，每个对象代表一个聚类中心；（2）对于样本中的数据对象，根据它们与这些聚类中心的欧氏距离，以距离最近为准则，将它们分到距离它们最近的聚类中心（最相似）所对应的类；（3）更新聚类中心，将每个类别中所有对象所对应的均值作为该类别的聚类中心，计算目标函数的值；（4）判断聚类中心和目标函数的值是否发生改变，若不变，则输出结果，若改变，则返回步骤（2）。K均值聚类算法K均值聚类分析案例以R语言基础包自带的鸢尾花（iris）数据进行K均值聚类分析，代码如下：K均值聚类算法K均值聚类分析案例以R语言基础包自带的鸢尾花（iris）数据进行K均值聚类分析，输出结果为：K均值聚类算法K均值聚类分析案例kmeans模型将数据分成了3类，每类的数量分别为38、62、50，Clustermeans表示的是3个类别中4个变量的均值。将分类的结果进行可视化，代码如下：结果如图10-1所示。凝聚式层次聚类算法层次聚类就是通过对数据集按照某种方法进行层次分解，直到满足某种条件为止。按照分类原理的不同，可以分为凝聚和分裂两种方法。由下向上对小的类别进行聚合，是凝聚式层次聚类；一层一层地进行聚类，由上向下把大的类别（Cluster）分割，就是分裂式层次聚类。凝聚式层次聚类概述凝聚式层次聚类是一种自底向上的策略，首先将每个对象都作为一个簇，然后合并这些原子簇为越来越大的簇，直到所有的对象都在一个簇中，或者某个终止条件被满足，绝大多数层次聚类方法都属于这一类，它们只是在簇间相似度的定义上有所不同，簇间相似度也就是邻近准则。凝聚式层次聚类算法1．邻近准则对于凝聚式层次聚类，指定簇的邻近准则是非常重要的一个环节，有三种最常用的准则，分别是MAX、MIN和AVERAGE，如图10-2所示。（1）单链（Single-link）：不同簇的两个最近的点之间的邻近度，即MIN；（2）全链（Complete-link）：不同簇中两个最远的点之间的邻近度，即MAX；（3）组平均（Average-link）：不同簇的所有点对邻近度的平均值（平均长度），即AVERAGE。凝聚式层次聚类算法2．主要问题1）缺乏全局目标函数这种方法产生的聚类算法避开了解决困难的组合优化问题。2）如何处理待合并簇的相对大小这个问题值适用于涉及求和的簇临近性方案，如质心，Ward方法和组平均。有两种方法：加权方法，平等地对待所有簇；非加权方法考虑每个簇的点数。换言之，平等地对待不同大小的簇表示赋予不同簇中的点不同的权值，而考虑簇的大小则赋予不同簇中的点相同的权值。3）合并决策是最终的凝聚式层次聚类算法趋向于做出好的局部决策，然而，一旦做出合并两个簇的决策，以后就不能撤销了。这种方法阻碍了局部最优标准、编程全局最优标准。一些试图克服这个问题限制的技术如下。（1）修补层次聚类：移动树的分支以改善全局目标函数。（2）划分聚类技术（如K均值）来创建许多小簇，然后从这些小簇出发进行层次聚类。凝聚式层次聚类算法3．算法优缺点（1）优点：通常，使用这类算法是因为基本应用需要层次结构，如创建一种分类方法。这些算法能够产生较高质量的聚类。（2）缺点：这类算法的计算量和存储需求代价昂贵。另外，对于噪声、高位数据，也可能造成问题。可先使用其他技术（如K均值）进行部分聚类，这两个问题都会在一定程度上得到解决。凝聚式层次聚类算法凝聚式层次聚类算法流程凝聚式层次聚类算法是一个迭代的过程，算法流程如下。（1）每次选最近的两个簇合并，将这两个合并后的簇称为合并簇。（2）若采用MAX准则，选择其他簇与合并簇中离得最远的两个点之间的距离作为簇之间的邻近度。若采用MIN准则，取其他簇与合并簇中离得最近的两个点之间的距离作为簇之间的邻近度。若采用组平均准则，取其他簇与合并簇所有点之间距离的平均值作为簇之间的邻近度。（3）重复步骤（1）和步骤（2），合并至只剩下一个簇。1凝聚式层次聚类算法凝聚式层次聚类算法流程（续）在这个算法中，需注意以下几点。（1）邻近度矩阵。邻近度有许多种定义方式，如欧氏距离，曼哈顿距离，马氏距离，余弦相似度，Jaccard系数，Bregman散度等。种类丰富，样品奇多，根据不同的需求来选择最适合的邻近度，计算得到相应的邻近度矩阵。（2）簇与簇之间邻近度的定义。每个簇中的点数不一定相等，如何计算两个不同簇之间的邻近度呢？常用的有三种方法：单链（MIN准则），全链（MAX准则），组平均技术。算法流程示例如下。（1）图10-3是一个有5个点的二维坐标系。（2）表10-1为这5个点的欧式距离矩阵。凝聚式层次聚类算法凝聚式层次聚类算法流程（续）（3）根据算法流程，先找出距离最近的两个簇P3、P4。合并P3、P4为{P3,P4}，根据MIN原则更新矩阵：MIN.distance({P3,P4},P1)=1.32;MIN.distance({P3,P4},P2)=1.56;MIN.distance({P3,P4},P5)=0.70。表10-2为欧式距离更新矩阵。凝聚式层次聚类算法凝聚式层次聚类算法流程（续）（4）接着继续找出距离最近的两个簇：{P3,P4}、P5。合并{P3,P4}、P5为{P3,P4,P5}，根据MIN原则继续更新矩阵：MIN.distance(P1,{P3,P4,P5})=1.32;MIN.distance(P2,{P3,P4,P5})=1.56。表10-3为欧式距离更新矩阵。凝聚式层次聚类算法凝聚式层次聚类算法流程（续）继续找出距离最近的两个簇P1、P2。合并P1、P2为{P1,P2}，根据MIN原则继续更新矩阵：MIN.distance({P1,P2},{P3,P4,P5})=1.32。表10-4为欧式距离更新矩阵。凝聚式层次聚类算法凝聚式层次聚类算法流程（续）（5）最终合并剩下的这两个簇即可获得最终结果，如图10-4所示。MAX组平均算法流程与M