机器学习之聚类分析.pptx

R聚类分析 Clustering Analysis 主讲人：吕朝晖 西北大学智能信息处理实验室 目录 什么是聚类 距离度量方法 几种常见的聚类方法 练习 概述 监督学习（supervised learning） 无监督学习（unsupervised learning） 半监督学习（Semi-Supervised Learning） 概述 从给定的训练数据集中学习出一个函数（模型参数）， 当新的数据到来时，可以根据这个函数预测结果 监督学习就是最常见的分类问题 监督学习的目标往往是让计算机去学习我们已经创建好 的分类模型 最典型的算法是KNN和SVM 监督学习（supervised learning） 输入数据没有标记，也没有确定的结果 样本数据类别未知，需要根据样本间的相似性对样本集 进行聚类 非监督学习目标不是告诉计算机怎么做，而是让计算机 自己去学习怎样做 非监督学习（unsupervised learning ） 无监督学习的方法分为两大类： 基于概率密度函数估计的直接方法 基于样本间相似性度量的简介聚类方法：设法定出不同 类别的核心或初始内核，然后依据样本与核心之间的相 似性度量将样本聚集成不同的类别 非监督学习（unsupervised learning ） “物以聚类，人以群分” 所谓聚类，就是将相似的事物聚集在一 起，而将不相似 的事物划分到不同的类别的过程，是数据分析之中十分 重要的一种手段。 什么是聚类？ 在图像分析中，人们希望将图像分割成具有类似性质的 区域 在文本处理中，人们希望发现具有相同主题的文本子集 在顾客行为分析中，人们希望发现消费方式类似的顾客 群，以便制订有针对性的客户管理方式和提高营销效率 这些情况都可以在适当的条件下归为聚类分析 什么是聚类？ 聚类就是将数据集中的样本划分为若干个通常不相交的 子集，每个子集成为一个“簇”（Cluster）。 聚类分析（Clustering Analysis） 聚类的相似性度量 1. 欧氏距离(Euclidean Distance) 欧氏距离是最易于理解的一种距离计算方法，源自欧 氏空间中两点间的距离公式。 两个n维向量a(x11,x12,x1n)与 b(x21,x22,x2n)间的欧氏距离： 聚类的相似性度量 2. 曼哈顿距离(Manhattan Distance) 想象你在曼哈顿要从一个十字路口开车到另外一个十 字路口，驾驶距离是两点间的直线距离吗？显然不是，除 非你能穿越大楼。实际驾驶距离就是这个“曼哈顿距离” ，也称为城市街区距离(City Block distance)。 两个n维向量a(x11,x12,x1n)与 b(x21,x22,x2n)间的 曼哈顿距离 聚类的相似性度量 3. 切比雪夫距离 ( Chebyshev Distance ) 国际象棋中国王走一步能够移动到相邻的8个方格中的任 意一个。那么国王从格子(x1,y1)走到格子(x2,y2)最少需要多 少步？你会发现最少步数总是max( | x2-x1 | , | y2-y1 | ) 步 。有一种类似的一种距离度量方法叫切比雪夫距离。 两个n维向量a(x11,x12,x1n)与 b(x21,x22,x2n)间的切比雪 夫距离 聚类的相似性度量 4. 马氏距离(Mahalanobis Distance) 有M个样本向量X1Xm，协方差矩阵记为S，均值记为向量 ，则其中样本向量X到u的马氏距离表示为： 5. 汉明距离(Hamming Distance) 两个等长字符串s1与s2之间的汉明距离定义为将其中一 个变为另外一个所需要作的最小替换次数。例如字符串 “1111”与“1001”之间的汉明距离为2。 要考虑所选择的距离公式在实际应用中有明确的意义。 如欧氏距离就有非常明确的空间距离概念。马氏距离有 消除量纲影响的作用。 距离选择的原则 层次聚类 凝聚方法（自底向上）：一开始将每个对象作为单独的一组，然后 根据同类相近，异类相异的原则，合并对象，直到所有的组合并成 一个，或达到一个终止条件为止。 分裂方法（自顶向下）：一开始将所有的对象置于一类，在迭代的 每一步中，一个类不断地分为更小的类，直到每个对象在单独的一 个类中，或达到一个终止条件。 层次聚类 特点： 类的个数不需事先定好 需确定距离矩阵 运算量要大，适用于处理小样本数据 层次聚类最短距离法 两个类中距离最近的两个样本的距离作为这两个集合的距离 将类Gp与Gq合并为Gr，则Gr与任意一类Gk间的距离为： 层次聚类最短距离法 最短距离法进行聚类分析的步骤如下： （1）定义样品之间距离，计算样品的两两距离，得一距离阵记为 D(0) ，开始每个样品自成一类，显然这时Dij =dij。 （2）找出距离最小元素，设为Dpq，则将Gp和Gq合并成一个新 类，记为Gr，即Gr = Gp，Gq。 （3）计算新类与其它类的距离。 （4）重复（2）、（3）两步，直到所有元素。并成一类为止。如 果某一步距离最小的元素不止一个，则对应这些最小元素的类可以 同时合并。 层次聚类最短距离法 层次聚类最大距离法 最大距离法（complete linkage method） 层次聚类最大距离法 将类Gp与Gq合并为Gr，则Gr与任意一类Gk间的距离为 ： 层次聚类中间距离法 中间距离法 最短、最长距离定义表示都是极端情况，我们定义类间距离可 以既不采用两类之间最近的距离也不采用两类之间最远的距离，而是采 用介于两者之间的距离，称为中间距离法。 中间距离将类Gp与Gq类合并为类Gr，则任意的类Gk和Gr的距离 公式为 ( 14 0) 设DkqDkp，如果采用最短距离法，则Dkr = Dkp，如果采用最长距离 法，则Dkr = Dkq。 层次聚类 【例】设有六个样品，每个只测量一个指标，分别是1，2，5，7，9，10 ，试用最短距离法将它们分类。 （1）样品采用绝对值距离，计算样品间的距离阵D（0） ，见表 层次聚类 （2）D（0）中最小的元素是D12D561，于是将G1和G2合并成G7， G5和G6合并成G8，并利用式计算新类与其它类的距离D(1) ，见下表 ： 层次聚类 （3）在D（1）中最小值是D34D482，由于G4与G3合并，又与G8 合并，因此G3、G4、G8合并成一个新类G9，其与其它类的距离D（2 ） ，见下表： 层次聚类 （4）最后将G7和G9合并成G10，这时所有的六个样品聚为一类，其过程 终止。 上述聚类的可视化过程见下图所示，横坐标的刻度表示并类的距离。这 里我们应该注意，聚类的个数要以实际情况所定： 原型聚类 （K-means、高斯混合聚类） 密度聚类（DBSCAN） 层次聚类 聚类算法 K均值法是麦奎因（MacQueen）1967提出的基本思想是将每 一个样本分配给最近中心（均值）的类中，具体的算法至少包括以 下四个步骤： (1)从n个数据对象随机选取k个对象作为初始簇中心。 (2)计算每个簇的平均值，并用该平均值代表相应的簇。 (3)计算每个对象与这些中心对象的距离，并根据最小距离重新对 相应对象进行划分。 (4)转步骤(2)，重新计算每个(自变化)簇的平均值。这个过程不 断重复直到某个准则函数不再明显变化或者聚类的对象不再变化为 止。 K均值聚类（K-means) K均值聚类（K-means) 【例】假定我们对A、B、C、D四个样品分别测量两个变量 和得到结果见表。 试将以上的样品聚成两类。 K均值聚类（K-means) 第一步：按要求取K=2，为了实施均值法聚类，我们将这 些样品随意分成两类，比如（A、B）和（C、D），然后 计算这两个聚类的中心坐标，见下表所示。 中心坐标是通过原始数据计算得来的，比如（A、 B）类的 ， K均值聚类（K-means) 第二步：计算某个样本到各类中心的欧氏平方距离，然后将该样品分 配给最近的一类。对于样品有变动的类，重新计算它们的中心坐标， 为下一步聚类做准备。先计算A到两个类的平方距离： 由于A到（A、B）的距离小于到（C、D）的距离，因此A不用重新 分配。计算B到两类的平方距离： K均值聚类（K-means) 由于B到（A、B）的距离大于到（C、D）的距离，因此 B要分配给（C、D）类，得到新的聚类是（A）和（B、C、 D）。更新中心坐标如下表所示。 K均值聚类（K-means) 第三步：再次检查每个样品，以决定是否需要重新分类。 计算各样品到各中心的距离平方，结果见下表。 到现在为止，每个样品都已经分配给距离中心最近的类， 因此聚类过程到此结束。最终得到K=2的聚类结果是A独自 成一类，B、C、D聚成一类。 K-means聚类的应用： 图像分割：SLIC算法 文本分析 K均值聚类（K-means) 基于密度的聚类 主要有DBSCAN，OPTICS法 思想：只要临近区域的密度超过一定的阈值，就继续聚类 特点：可以过滤噪声和孤立点outlier，发现任意形状的类 DBSCAN是基于一组邻域来描述样本集的紧密程度的，参数(, MinPts) 用来描述邻域的样本分布紧密程度。描述某一样本的邻域距离阈值， MinPts描述某一样本的距离为的邻域中样本个数的阈值。 假设我的样本集是D=(x1,x2,.,xm)则DBSCAN具体： 1） -邻域：对于xjD，其-邻域包含样本集D中与xj的距离不大于的子 样本集，即N(xj)=xiD|distance(xi,xj) 2) 核心对象：对于任一样本xjD，如果其-邻域对应的N(xj)至少包含 MinPts个样本，即如果|N(xj)|MinPts，则xj是核心对象。 密度聚类DBSCAN 3）密度直达：如果xi位于xj的-邻域中，且xj是核心对象，则称xi由xj 密度直达。注意反之不一定成立， 除非且xi也是核心对象。 4）密度可达：对于xi和xj,如果存在样本序列p1,p2,.,pT满足 p1=xi,pT=xj且pt+1由pt密度直达，则称xj由xi密度可达。密度可达满足传 递性。此时序列中的传递样本p1,p2,.,pT1均为核心对象，因为只有 核心对象才能使其他样本密度直达。 5）密度相连：对于xi和xj,如果存在核心对象样本xk，使xi和xj均由xk密 度可达，则称xi和xj密度相连。 密度聚类DBSCAN 密度聚类DBSCAN MinPts=5 由密度可达关系导出的最大密度相连的样本集合，即为我们最终聚类的 一个类别，或者说一个簇。 首先给定聚类对象的半径-邻域和-邻域中最小包含的对象数MinPts 然后检查某个对象-邻域中的对象数，如果对象数大于MinPts，该对象 就是核心对象，就构建以该对象为核心的新簇 然后，反复寻找从这些核心对象出发在-邻域内的对象，这个寻找过程 可能会合并一些簇。直到没有新的对象可以添加到任何簇中为止 密度聚类DBSCAN 密度聚类DBSCAN 第一步，在数据集中选择一点1，以它为圆心的，以1为半径的圆内包 含2个点（小于4），因此它不是核心点，选择下一个点。 第二步，在数据集中选择一点2，以它为圆心的，以1为半径的圆内包 含2个点（小于4），因此它不是核心点，选择下一个点。 第三步，在数据集中选择一点3，以它为圆心的，以1为半径的园内包 含3个点（小于4），因此它不是核心点，选择下一个点。 密度聚类DBSCAN 密度聚类DBSCAN 第四步，在数据集中选择一点4，由于在以它为圆心的，以1为半径的 圆内包含5个点，因此它是核心点，寻找从它出发可达的点（直接可 达4个，间接可达3个），聚出的新类1，3，4，5，9，10，12，选 择下一个点。 密度聚类DBSCAN 第五步，在数据集中选择一点5，已在簇1中，选择下一个点。 第六步，在数据集中选择一点6，在以它为圆心的，以1为半径的圆 内包含3个点，因此它不是核心点，选择下一个点。 密度聚类DBSCAN 第七步，在数据集中选择一点7，以它为圆心，以1为半径的圆内包 含5个点，因此它是核心点，寻找从它出发可达的点，聚出的新类2 ，6，7，8，11，选择下一个点。 第八步，在数据集中选择一点8，已经在簇2中了，选择下一点。 第九步，在数据集中选择一点9，已经在簇1中了，选择下一点。 第十步，在数据集中选择一点10，已经在簇1中了，选择下一点。 第十一步，在数据集中选择一点11，已