《机器学习之聚类分析.ppt》由会员分享，可在线阅读，更多相关《机器学习之聚类分析.ppt（48页珍藏版）》请在三一办公上搜索。
1、聚类分析,Clustering Analysis,主讲人：吕朝晖西北大学智能信息处理实验室,目录,什么是聚类距离度量方法几种常见的聚类方法练习,概述,监督学习（supervised learning）无监督学习（unsupervised learning）半监督学习（Semi-Supervised Learning）,概述,从给定的训练数据集中学习出一个函数（模型参数），当新的数据到来时，可以根据这个函数预测结果监督学习就是最常见的分类问题监督学习的目标往往是让计算机去学习我们已经创建好的分类模型最典型的算法是KNN和SVM,监督学习（supervised learning）,输入数据没有标记
2、，也没有确定的结果样本数据类别未知，需要根据样本间的相似性对样本集进行聚类非监督学习目标不是告诉计算机怎么做，而是让计算机自己去学习怎样做,非监督学习（unsupervised learning）,无监督学习的方法分为两大类：基于概率密度函数估计的直接方法基于样本间相似性度量的简介聚类方法：设法定出不同类别的核心或初始内核，然后依据样本与核心之间的相似性度量将样本聚集成不同的类别,非监督学习（unsupervised learning）,“物以聚类，人以群分”所谓聚类，就是将相似的事物聚集在一 起，而将不相似的事物划分到不同的类别的过程，是数据分析之中十分重要的一种手段。,什么是聚类？,在图像
3、分析中，人们希望将图像分割成具有类似性质的区域在文本处理中，人们希望发现具有相同主题的文本子集在顾客行为分析中，人们希望发现消费方式类似的顾客群，以便制订有针对性的客户管理方式和提高营销效率这些情况都可以在适当的条件下归为聚类分析,什么是聚类？,聚类就是将数据集中的样本划分为若干个通常不相交的子集，每个子集成为一个“簇”（Cluster）。,聚类分析（Clustering Analysis）,聚类的相似性度量,1.欧氏距离(Euclidean Distance)欧氏距离是最易于理解的一种距离计算方法，源自欧氏空间中两点间的距离公式。两个n维向量a(x11,x12,x1n)与 b(x21,x22
4、,x2n)间的欧氏距离：,聚类的相似性度量,2.曼哈顿距离(Manhattan Distance)想象你在曼哈顿要从一个十字路口开车到另外一个十字路口，驾驶距离是两点间的直线距离吗？显然不是，除非你能穿越大楼。实际驾驶距离就是这个“曼哈顿距离”，也称为城市街区距离(City Block distance)。,两个n维向量a(x11,x12,x1n)与 b(x21,x22,x2n)间的曼哈顿距离,聚类的相似性度量,3.切比雪夫距离(Chebyshev Distance)国际象棋中国王走一步能够移动到相邻的8个方格中的任意一个。那么国王从格子(x1,y1)走到格子(x2,y2)最少需要多少步？你会
5、发现最少步数总是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。,要考虑所选择的距离公式在实际应用中有明确
6、的意义。如欧氏距离就有非常明确的空间距离概念。马氏距离有消除量纲影响的作用。,距离选择的原则,层次聚类,凝聚方法（自底向上）：一开始将每个对象作为单独的一组，然后根据同类相近，异类相异的原则，合并对象，直到所有的组合并成一个，或达到一个终止条件为止。分裂方法（自顶向下）：一开始将所有的对象置于一类，在迭代的每一步中，一个类不断地分为更小的类，直到每个对象在单独的一个类中，或达到一个终止条件。,层次聚类,特点：类的个数不需事先定好需确定距离矩阵运算量要大，适用于处理小样本数据,层次聚类最短距离法,两个类中距离最近的两个样本的距离作为这两个集合的距离,将类Gp与Gq合并为Gr，则Gr与任意一类Gk
7、间的距离为：,层次聚类最短距离法,最短距离法进行聚类分析的步骤如下：（1）定义样品之间距离，计算样品的两两距离，得一距离阵记为D(0)，开始每个样品自成一类，显然这时Dij=dij。（2）找出距离最小元素，设为Dpq，则将Gp和Gq合并成一个新类，记为Gr，即Gr=Gp，Gq。（3）计算新类与其它类的距离。（4）重复（2）、（3）两步，直到所有元素。并成一类为止。如果某一步距离最小的元素不止一个，则对应这些最小元素的类可以同时合并。,层次聚类最短距离法,层次聚类最大距离法,最大距离法（complete linkage method）,层次聚类最大距离法,将类Gp与Gq合并为Gr，则Gr与任意一
8、类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）中最小的元素是D12D56
9、1，于是将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提出的基本思
10、想是将每一个样本分配给最近中心（均值）的类中，具体的算法至少包括以下四个步骤：(1)从n个数据对象随机选取k个对象作为初始簇中心。(2)计算每个簇的平均值，并用该平均值代表相应的簇。(3)计算每个对象与这些中心对象的距离，并根据最小距离重新对相应对象进行划分。(4)转步骤(2)，重新计算每个(自变化)簇的平均值。这个过程不断重复直到某个准则函数不再明显变化或者聚类的对象不再变化为止。,K均值聚类（K-means),K均值聚类（K-means),【例】假定我们对A、B、C、D四个样品分别测量两个变量和得到结果见表。试将以上的样品聚成两类。,K均值聚类（K-means),第一步：按要求取K=2，为
11、了实施均值法聚类，我们将这些样品随意分成两类，比如（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、
12、C、D）。更新中心坐标如下表所示。,K均值聚类（K-means),第三步：再次检查每个样品，以决定是否需要重新分类。计算各样品到各中心的距离平方，结果见下表。到现在为止，每个样品都已经分配给距离中心最近的类，因此聚类过程到此结束。最终得到K=2的聚类结果是A独自成一类，B、C、D聚成一类。,K-means聚类的应用：图像分割：SLIC算法文本分析,K均值聚类（K-means),基于密度的聚类,主要有DBSCAN，OPTICS法思想：只要临近区域的密度超过一定的阈值，就继续聚类特点：可以过滤噪声和孤立点outlier，发现任意形状的类,DBSCAN是基于一组邻域来描述样本集的紧密程度的，参数(,
13、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密度直达。注意反之不一定成立，除非且x
14、i也是核心对象。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
15、然后检查某个对象-邻域中的对象数，如果对象数大于MinPts，该对象就是核心对象，就构建以该对象为核心的新簇 然后，反复寻找从这些核心对象出发在-邻域内的对象，这个寻找过程可能会合并一些簇。直到没有新的对象可以添加到任何簇中为止,密度聚类DBSCAN,密度聚类DBSCAN,第一步，在数据集中选择一点1，以它为圆心的，以1为半径的圆内包含2个点（小于4），因此它不是核心点，选择下一个点。第二步，在数据集中选择一点2，以它为圆心的，以1为半径的圆内包含2个点（小于4），因此它不是核心点，选择下一个点。第三步，在数据集中选择一点3，以它为圆心的，以1为半径的园内包含3个点（小于4），因此它不是核心点
16、，选择下一个点。,密度聚类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，
17、7，8，11，选择下一个点。,第八步，在数据集中选择一点8，已经在簇2中了，选择下一点。第九步，在数据集中选择一点9，已经在簇1中了，选择下一点。第十步，在数据集中选择一点10，已经在簇1中了，选择下一点。第十一步，在数据集中选择一点11，已经在簇2中了，选择下一点。第十二步，在数据集中选择一点12，已经在簇1中了，结束。,密度聚类DBSCAN,密度聚类DBSCAN,常用的外部指标Jaccard系数：主要判断隶属于相同类的个数。该个数越多，说明聚类效果越好。常用的内部聚类perplexity值：perplexity值（困惑度）主要计算特征的概率。通常用于LDA,HDP等模型上，值越小越好。距离计算：类内的样本距离越小越好，类间的距离越大越好。,评价指标,K均值聚类DBSCAN层次聚类（欧式距离，最短距离法）实现并说明其优势和劣势。,作业练习,
