聚类分析 (2).ppt

聚类分析 主讲人 尹婷婷 目录 聚类分析背景和定义 聚类的依据 常见的聚类方法 1 1聚类产生的背景 聚类分析起源于分类学 在考古的分类学中人们主要依靠经验和专业知识来实现分类 随着生产技术和科学的发展 人类的认识不断加深 分类越来越细 要求也越来越高 有时光凭经验和专业知识是不能进行确切分类的 往往需要定性和定量分析结合起来去分类 于是数学工具逐渐被引进分类学中 形成了数值分类学 后来随着多元分析的引进 聚类分析又逐渐从数值分类学中分离出来而形成一个相对独立的分支 在社会经济领域中存在着大量分类问题 比如 对我国30个省市自治区独立核算工业企业经济效益进行分析 一般不是逐个省市自治区去分析 而较好的做法是选取能反映企业经济效益的代表性指标 如百元固定资产实现利税 资金利税率 产值利税率 百元销售收入实现利润 全员劳动生产率等等 根据这些指标对30个省市自治区进行分类 然后根据分类结果对企业经济效益进行综合评价 就易于得出科学的分析 又比如若对某些大城市的物价指数进行考察 而物价指数很多 有农用生产物价指数 服务项目物价指数 食品消费物价指数 建材零售价指数等等 由于要考察的物价指数很多 通常先对这些物价指数进行分类 总之 需要分类的问题很多 因此聚类分析这个数学工具越来越受到人们的重视 它在数学的领域中都得到了广泛的应用 1 2聚类分析的定义 聚类分析又称为群分析或分类分析等分析 是一种重要的分类方法 它是根据事物自身的特征 通过已建立的统计模型对事物进行多元分析方法的一种统计分析 其目的在于将相似的事物进行归类 这些类不是事先给定的 而是需要通过聚类分析来给以确定类型 分类一般是对样品分类或者对变量分类 对样品进行分类称为Q型聚类分析 对变量进行分类称为R型聚类分析 2 聚类的依据 为了将样品 或变量 进行分类 就需要研究样品之间关系 目前用的最多的方法有两个 一种方法是用相似系数 性质越接近的样品 它们的相似系数的绝对值越接近于1 而彼此无关的样品 它们的相似系数的绝对值越接近于0 比较相似的样品归为一类 不怎么相似的样品归为不同的类 另一种方法是将一个样品看做P维空间的一个点 并在空间定义距离 距离越近的点归为一类 距离较远的点归为不同的类 对样品进行聚类分析 通常采用距离测量样品之间的相似程度 目前最常用的距离是明氏距离 对变量进行进行聚类分析 一般采用夹角余弦或相关系数 样品相似性的度量 设有n个样品 每个样品有个指标的测试数据 用矩阵表示为 称为样品观测值矩阵 用表示与之间的距离 p表示p维空间 n表示样品个数 则有 明氏距离 闵可夫斯基距离 明氏距离的表现公式为 这里的p表示p维空间 q表示自然数 根据q的取值不同又可以分为 1 绝对值距离 q 1 2 欧氏距离 q 2 欧氏距离是聚类分析中最常用的距离 3 切比雪夫距离 q 变量相似性的度量 多元数据中的变量表现为向量形式 在几何上可用有向线段表示 在对多元数据进行分析时 相对于数据的大小 我们更多的对变量的变化趋势或方向感兴趣 因此变量之间的相似性可以从它们的方向趋同性或相关性进行考察 从而得到夹角余弦法和相关系数两种度量方法 1 夹角余弦 与看做p维空间中的两个向量 这两个向量间的夹角余弦可用下式进行计算 例如在二维空间中 对 这两个变量有 2 相关系数 相关系数经常用来度量变量之间的相似性 变量 的相关系数定义为 无论是夹角余弦还是相关系数 他们的绝对值都小于等于1 作为变量近似值得工具 我们把它们统计为当 1时 说明两个变量完全相似 当近似于1时 说明两变量非常密切 当 0时 说明两变量完全不一样 当近似于0时 说明两变量差别很大 这样 我们把比较相似的变量聚为一类 把不太相似的变量归到不同的类中 3 聚类分析的方法 常见的聚类方法有 有序样品聚类法 系统聚类法 K均值法 模糊聚类法和动态聚类法等等 不同的聚类方法可以将样品或变量分成不同的类别 根据分类要求的不同 选择不同的分类方法 1 有序样品聚类法 许多实际问题中有序事物按一定次序排列的 这样的事物称为有序事物 如儿童的增重数按年龄排序 历史的研究按时间的先后排序 地质勘探取样资料按地层的深浅排序等 对有序事物分类时不能打乱原先事物的次序 例如 为了了解儿童的生长发育规律 今随机抽样统计了男孩从出生到11岁平均增长的重量数据表如下 试问 男孩发育可分为几个阶段 记与年龄对应的儿童增重数的11个数据 表示儿童的增重数 例如表示8岁儿童的平均年增重为2 千克 如果要把增重数分成保持次序的3个组 这时可以有种选择 例如 就是一种可选择的分类方法 一个好的分类方法就是应该使处于同一类事物之间的差别尽可能地小 而使类与类之间的差别尽可能地大 为了表示类内部事物与事物的差别 我们借用统计中全距 直径 的计算方法 以 这个分类为例来说明计算类内差别的方法 其中第一类对应的数据为9 3 1 8 1 9 最大值为9 3 最小值为1 8 这一类的差异我们用全距9 3 1 8 7 5第二类中最大值为2 0 最小值为1 3 则2 0 1 3 0 7第三类中的最大值为2 3 最小值为1 9 则2 3 1 9 0 4为衡量上述分类方法的优劣 我们计算此种分类方法中的三个类内的平均差异 即规定该分类方法的优劣指标K为 对于另一种分类方法 1 2 3 4 5 6 7 8 9 10 11 其第一类的类内差异为7 6 第二类的类内差异为0 2 第三类的类内差异为0 9 该分类方法的优劣指标K为2 9 相比之下 此分类方法不如前一种分类方法好 试问 分三类最好的分类方法应怎么分 把11个有序数据分成3类共有45种方法 计算每类分法的优劣指标并加以比较 可以得到最好的 分三类 方法为 1 2 3 4 5 6 7 8 9 10 11 此分类方法的优劣指标K是0 3 以同样的方法分析 可知把这11个数据分成两类的最好分类方法是这时的优劣指标K为0 5 那么这11个数据分成几类为宜呢 为此 我们分别找到把11个数据分成1类 2类 11类的最好的分类法 计算出各最好分类方法的优劣指标 列表如下 由表可看到 如果把1至11岁的数据只分成一类时 K 8 优劣指标值太大 而对n大于4时的K值相差不多 而当n 3或n 4时 K值已降为0 30和0 20 而n 5及其以上时 K相差太小 而类分得太多无意义 因此分成3类或4类为宜 我们也许可以对分成三类的情况予以如下实际解释 儿童从1岁到11岁可分为三个阶段 1岁的儿童睡得多吃得多 处于体重增加最快的阶段 2岁至7岁的儿童处于入学前或刚入学的阶段 体重增加有所减缓 8岁至11岁后生活规律化 开始进入发育期 体重稳定增加 2 系统聚类法 3 1系统聚类的基本思想系统聚类的基本思想是 距离相近的样品 或变量 先聚成类 距离相远的后聚成类 过程一直进行下去 每个样品 或变量 总能聚到合适的类中 系统聚类过程是 假设总共有n个样品 或变量 第一步 将每个样品 或变量 独自聚成一类 共有n类 第二步 根据所确定的样品 或变量 距离 公式 把距离较近的两个样品 或变量 聚合成一类 其他的样品 或变量 仍各自聚为一类 共聚成n 1类 第三步 将 距离 最近的两个类进一步聚成一类 共聚成n 2类 以上步骤一直进行下去 最后将所有的样品 或变量 聚成一类 为了直观地反映以上的系统聚类过程 可以把整个分类系统地画成一张谱系图 所以有时系统聚类也称为谱系分析 在进行系统聚类之前 我们首先要定义类与类之间的距离 由类间距离定义的不同产生了不同的系统聚类法 系统聚类法中常用的距离有最短距离法 最长距离法 中间距离法 重心法等等 每种距离法的归类步骤是一致的 主要差异是类间距离的计算方法不同 我们以最短距离为例进行说明 用表示第i个事物与第j个事物之间的距离 设表示类 用表示类与类之间的距离 最短距离法 定义 即中任一事物与任一事物距离的最小值 最短距离法进行聚类分析的步骤如下 1 定义样品之间的距离 计算样品的两两距离 得一距离阵 开始时每个样品自成一类 2 找出距离最小元素 设为 则将与合并成一个新类 记为 3 将与其他类再进行求出最短距离 再进行合并 4 重复上述步骤 直到所有元素并成一类为止 例1 设有6个样品 每个只测量一个指标 分别为1 2 5 7 9 10 试用最短距离法将他们分类 1 样品采用绝对值距离 计算样品间的距离阵 如下表 2 上述矩阵中最小的元素是D12 D56 于是将G1 G2合并成G7 将G5 G6合并成G8 可知G7 1 2 G8 9 10 于是得到新的距离阵 在上述距离阵中最小值是D34 D48 2 于是G3与G4合并 再与G8合并 成一个新类G9 5 7 9 10 将其再与其他类进行计算 得新的距离阵 4 最后将G7 G9合并成G10 这时所有的六种样品聚为一类 过程终止 例2对某地21个古墓挖掘后 记录每个古墓陪葬的瓷器用具数和陶桶数 分别记为和要求按这两个指标对古墓进行分类 数据列表如下 此处和均可以看作平面直角坐标系中点的两个坐标 每个古墓可以用该坐标平面上的一个点来表示 得图2 6 1 我们采用通常平面上点的距离作为对应的古墓与古墓间的差别 第一 从图和表都可看出 两个古墓的最小距离是1 其中下面几组古墓之间的距离都是1 1号与2号 5号与6号 11号与5号 8号与9号 12号与13号 17号与18号 17号与19号 把距离为1的点合成一类 就得到新的类 把这些新类用实线圈圈起来 分别记为G1 G2 G3 G4 G5 第二 以两个类元素中的最短距离作为两个类的类间的距离 可计算得目前两个类问的最短距离为 此处4号墓与G2中的11号墓距离为 同样 10号墓与G3的距离为 20号墓与G5的距离都是 把距离不大于收的类归为一类 则得到新类 如图2 6 3中实线所圈的集合 第三 仍以两个类中的最短距离作为两类之间的距离 则现在两个类间的最小距离为2 将类的距离小于2的类合并成新类 在图2 6 3中新的类用虚线围成 现在 除去16 21这两点外 所有的点全在这4个类中 第四 再重复上述的过程 我们最终可以把这21个样本归为一类 但是在进行分类的过程中 如果是要求对样本进行分类 在第三步时就可以终止了 这样将16号和21号单独归为一类 就可以分为6类 3 K均值法 系统聚类需要计算出不同样品之间的距离 当样本容量较大时 计算量也比较 需要占据非常大的计算机内存空间 这给应用带来一定的困难 K均值法是一种快速的分类法 采用该方法得到的结果比较简单 基本思想是 将每一个样品分配给最近中心 均值 的类中 具体的算法包括以下步骤 1 将所有样品分成K个初始类 计算每一个类的中心坐标 2 通过欧几里得距离将某个样品划入离中心最近的类中 并对获得样品与失去样品的类 重新计算中心坐标 3 重复步骤 2 直到所有的样品都不能再分配时为止 例3 假定我们对A B C D四个样品分别测量两个变量和 得到结果如下 试将以下样品聚成两类 第一步 我们将这些项目先随意分成两个聚类 比如说 AB 和 CD 然后计算这两个聚类的中心 均值 的坐标第二步 计算某个样品到各类中心的欧几里得距离 然后将该样品分配到最近的一类 先计算A到两个类的平方距离 d2 A AB 5 2 2 3 2 2 10d2 A CD 5 1 2 3 2 2 61由于A到 A B 的距离小于到 C D 因此不用重新分配 再计算B到两个类的平方距离 d2 B AB 1 2 2 1 2 2 10d2 B CD 1 1 2 1 2 2 9由于B到 A B 的距离大于到 C D 因此B要分配给CD 于是得到一个新的聚类 A 和 B