医学大数据分析 课件 第9章 聚类方法

医学大数据分析聚类方法高等教育出版社CONTENTS目录1聚类的概念2聚类与分类的区别3划分方法4层次聚类4聚类算法评估1聚类的概念什么是聚类？

什么是聚类？聚类分析是将物理的或者抽象的数据集合划分为多个类别的过程，聚类之后的每个类别中任意两个数据样本之间具有较高的相似度，而不同类别的数据样本之间具有较低的相似度。每一类称为一个簇。物以类聚，人以群分聚类和分类的区别有监督学习学习器通过对大量有标记的训练集进行学习，从而建立模型用于预测未见示例的标记，例如神经网络和决策树无监督学习无训练样本，仅根据测试样本的在特征空间分布情况来进行标记/聚簇有监督学习无监督学习分类图示训练数据待分类数据聚类图示聚类中没有任何指导信息，完全按照数据的分布进行类别划分2划分方法距离度量

距离度量

3划分方法划分方法给定n个数据对象的数据集D，以及要生成的簇数k，划分算法把数据分成k(k≦n)个分区，其中每个分区代表一个簇。使得在同一个簇中对象是“相似的”，而不同簇中的对象是“相异的”。也就是说，它将数据划分为k个组，同时满足如下的要求：每个组至少包含一个对象；每个对象必须属于且只属于一个组，同时某些模糊划分技术中第二个要求可以放宽。划分方法主要包含以下两种：K-均值算法K-中心点算法k均值聚类给定k，算法的处理流程如下:Step1：从D中任意选择k个对象作为初始簇中心；Step2：将每个对象根据其与各个簇中心的距离，重新分配到与它最近的簇中；Step3：计算每个簇的平均值，并用该平均值代表相应的簇；Step4：回到第2步，直到不再有新的分配发生。k均值聚类(a)

(b)(c)(d)k均值聚类优点相对高效的：算法复杂度O(tkn)，其中n是数据对象的个数，k是簇的个数，t是迭代的次数，通常k,t<<n当簇是密集的，簇与簇之间区别明显时,它的效果较好。缺点只有当平均值有意义的情况下才能使用，对于类别字段不适用；必须事先给定要生成的簇的个数k；对“噪声”和异常数据敏感；不能发现非球形的簇，难以达到全局最优k均值聚类缺陷(a)聚类-预期结果(b)原始数据(c)结果较差聚类k-中心点聚类k-均值算法对离群点非常敏感。因为拥有极端值的对象将在很大程度上影响数据的分布。k-中心点:用中心点（位于簇最中心位置的对象）而不是簇中对象的平均值作为参考点。k-中心点聚类算法实现的过程：设置聚类簇数k，从数据集中随机选择k个数据点作为初始簇中心。计算其余数据点到聚类簇中心的距离，并将其分配到距离最近的簇中。随机选择一个非簇中心代替最开始的初始中心，并进行重新分配剩余的数据。计算代替后的总代价，如果该总代价小于代替之前的总代价，则用该非簇中心对象代替原来的簇中心，否则不替换。重复执行步骤3-4，直到没有簇中心发生变化或达到迭代次数，算法停止并输出聚类簇中心坐标。k-中心点聚类-优缺点k-中心点聚类的主要优点：该算法原理简单，容易实现。该算法伸缩性好，能够处理中小型数据集。该算法对于读入数据的顺序不敏感，数据输入顺序不影响聚类结果。该算法对离群点或“噪声”数据不敏感。k-中心点聚类-优缺点

4层次聚类层次聚类把数据分成不同层，将数据对象组成层次结构或簇的“树”，有利于数据汇总和可视化。层次聚类使用距离作为衡量标准，不需要输入聚类的个数k，但需要设置终止条件。层次聚类-步骤(1)把n个对象作为n个聚类(2)找出距离最近的两个聚类合并(3)重复(2)直至n个对象归于一类(或几类)BCAFDEG层次聚类-距离最小距离(SINGLE)：最大距离(COMPLETE):距离均值(MEAN)：平均距离(AVERAGE)：层次聚类-距离(a)最小距离

(b)最大距离(c)平均距离

(d)均值距离当算法使用最小距离衡量簇间距离时，称为最近邻聚类算法。此外，如果当最近的簇之间的距离超过某个任意的阈值时聚类过程就会终止，则称其为单连接算法。当一个算法使用最大距离度量簇间距离时，称为最远邻聚类算法。如果当最近簇之间的最大距离超过某个任意的阈值时聚类过程就会终止，则称其为全连接算法。距离度量先将五个样本都分别看成是一个簇，最靠近的两个簇是3和4，因为他们具有最小的簇间距离D(3,4)=5.0第一步：合并簇3和4，得到新的簇集合1,2,(3,4),5x1x2110522020330104301555101234510.00218.00.00320.614.10.00422.411.25.000.0057.0718.025.025.50.00最小距离层次聚类实例第二步：更新距离矩阵：D(1,(3,4))=min(D(1,3),D(1,4))=min(20.6,22.4)=20.6D(2,(3,4))=min(D(2,3),D(2,4))=min(14.1,11.2)=11.2D(5,(3,4))=min(D(3,5),D(4,5))=min(25.0,25.5)=25.0125(34)10.00218.00.0057.0718.00.00(34)20.611.225.00.002(34)(15)20.00(34)11.20.00(15)18.020.60.00(15)(234)(15)0.00(234)18.00.00最小距离层次聚类实例最小距离层次聚类实例最小和最大度量代表了簇间距离度量的两个极端。它们趋向对离散点或噪声数据过分敏感。使用均值距离和平均距离是对最小和最大距离之间的一种折中方法，而且可以克服离群点敏感性问题。尽管均值距离计算简单，但是平均距离也有它的优势，因为它既能处理数值数据又能处理分类数据。各种距离优缺点层次聚类方法尽管简单，但经常会遇到合并或分裂点选择的困难。这样的决定是非常关键的，因为一旦一组对象合并或者分裂，下一步的处理将对新生成的簇进行。(不能撤销先前步骤所做的工作)不具有很好的可伸缩性，因为合并和分裂的决定需要检查和估算大量的对象或簇，时间复杂度为O(n2)层次聚类缺点5聚类算法评估36聚类算法评估主要包括：确定数据集中的簇数测定聚类质量算法评估37

算法评估—确定簇数38外