第6章 无监督学习ppt课件.pptx
《第6章 无监督学习ppt课件.pptx》由会员分享,可在线阅读,更多相关《第6章 无监督学习ppt课件.pptx(61页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、章 节 目 录6.1 6.1 聚类概述聚类概述6.2 K-means6.2 K-means算法算法6.3 DBSCAN6.3 DBSCAN算法算法6.4 EM6.4 EM算法算法6.5 6.5 关联分析关联分析6.6 6.6 竞争网络竞争网络6.7 6.7 无监督学习应用概述无监督学习应用概述 6.8 6.8 案例分析案例分析什么是无监督学习?什么是无监督学习? 前面的机器学习算法,都使用了由一系列标记好的目标数据组成的训练集。但现实生活中,我们往往很难得到标记好的数据,或进行人工类别标注的成本太高。很自然地,我们希望计算机能代我们完成这些工作,或至少提供一些帮助。 因此,这种没有标注的训练数
2、据集,需要根据样本间的统计规律对样本集进行分析,我们称为无监督学习。 什么是无监督学习?什么是无监督学习? 无监督学习的数据集和有监督学习的不同,没任何标签,也就是没有“正确的输出结果”,在此过程中没有指导者,只有计算机自己学习。 无监督学习的常见任务包括聚类等。 聚类概述聚类概述 聚类就是一种典型的无监督学习。 聚类又称为点群分析,聚类的目标是在一个对象(模式、数据点)的集合中发现其自然分组。 定义:给定n个对象的某种表示,根据某种相似度度量,发现K个簇,使得簇内对象的相似度高,簇间对象的相似度低 。聚类类别聚类类别 聚类算法种类繁多,具体的算法选取取决于数据类型、聚类的应用和目的。常用的聚
3、类算法大致可分成如下几类: 基于划分的聚类算法 基于密度的聚类算法 基于模型的聚类算法 基于层次的聚类算法 基于网格的聚类算法 聚类类别聚类类别 基于划分的聚类算法。按照某种目标将数据集划分成若干个组,划分的结果使目标函数值最大化(或最小化)。代表算法有K-means算法、K-medoids算法以及CLARANS算法等。 基于密度的聚类算法。只要在临近区域的密度(对象或数据点的数目)超过某个阈值,就把它加到与之相近的聚类。代表算法有DBSCAN算法、OPTICS算法及DENCLUE算法等。聚类类别聚类类别 基于模型的聚类算法。假定了一个模型,寻找数据对给定模型的最佳拟合。代表算法有基于统计学模
4、型的EM算法和COBWEB算法,以及基于神经网络模型的竞争网络。 基于层次的聚类算法。对给定数据集进行层次的分解,形成一颗以簇为结点的树。代表算法有BIRCH算法、CURE算法、ROCK算法及Chameleon算法等。 基于网格的聚类算法。将对象空间划分为有限个单元以构成网格结构,然后利用网格结构完成聚类。代表算法有STING算法、WaveCluster算法等。背景背景 K-means算法是由Steinhaus于1955年、Lloyd于1957年、Ball和Hall于1965年、Mcqueen于1967年分别在各自的不同的科学研究领域独立提出来。 自被提出以来,这一算法在许多学科领域内得到了大
5、量的研究和应用,具体的如数据压缩、数据分类、密度估计等诸多方面。由于其算法思想简洁易懂,而且对于很多聚类问题都可以花费较小的计算代价而得到不错的聚类结果,K-means算法成为无监督聚类算法中较为常用的算法之一。准则函数准则函数 算法描述算法描述 K-means算法的目标:找到最小化SSE的聚类结果。 迭代过程 (1)分配过程。在分配过程中,每个数据样本都要被分配到与它距离最近的簇质心所属的簇中; (2)更新过程。在更新过程中,簇质心需要被重新计算,采用分配到这一簇中的所有数据样本的平均值对簇质心进行更新。算法流程算法流程算法:K-means算法。用于划分的K-means算法,每个簇的质心用簇
6、中所有对象的均值来表示。输入:簇的数目k和包含n个对象的数据集。输出:k个簇,使平方误差(SSE)最小。方法:随机地选择k个对象,每个对象代表一个簇的初始均值或质心。对剩余的每个对象,根据它与簇均值(质心)的距离,将其指派到最相似的簇。计算每个簇的新均值(质心)。回到步骤2),循环,直到簇的均值(质心)不再发生变化。工作过程工作过程 图(a),表示初始数据集,假设k=2; 图(b),我们随机选择两个簇质心,即图中红蓝质心,然后分别求所有样本到两质心距离,并标记每个样本类别为和该样本距离最小的质心类别; 图(c),经计算样本和红蓝质心的距离,我们得到所有样本的第一轮迭代的类别。此时对当前标记为红
7、蓝点分别求其新的质心; 图(d),新的红色质心和蓝色质心的位置发生变动; 图(e)和图(f)重复了我们在图(c)和图(d)的过程,即将所有点的类别标记为距离最近的质心的类别并求新的质心。 K K值选择值选择 当k小于真实聚类数时,由于k的增大会大幅增加每个簇的聚合程度,故SSE下降幅度会很大; 当k到达真实聚类数时,再增加k所得到的聚合程度回报会迅速变小,所以SSE的下降幅度会骤减,然后随着k值的继续增大而趋于平缓; 也就是说SSE和k的关系图是一个手肘的形状,而这个肘部对应的k值就是数据的真实聚类数。目前常使用参考SSE的“手肘法”。 “手肘法”核心思想:随着聚类数k的增大,样本划分会更加精
8、细,每个簇的聚合程度会逐渐提高,那么SSE自然会逐渐变小。初始质心选择初始质心选择初始化的聚类质心距离要尽可能地远。 首先,随机选择一个点作为第一个初始类簇质心 然后,选择距离该点最远的那个点作为第二个初始类簇质心 接着,再选择距离前两个点的距离最远的点作为第三个初始类簇的质心 以此类推,直至选出K个初始类簇质心。 K-meansK-means算法总结算法总结 当结果簇是密集的,而簇之间的区别明显时,它的效果较好。 对于处理大数据集,该算法是相对可伸缩的和高效的,因为它的算法复杂度是O(nkt),其中n是数据个数,k是簇的个数,t是迭代的次数,通常,kn,且tn。 算法通常终止于局部最优解。
9、只有当簇均值有定义的情况下才能使用,这可能不适用于某些应用,例如涉及有分类属性的数据。 必须事先给定要生成的簇的数目k。 对噪声和孤立点数据敏感,少量的该类数据能够对平均值产生极大的影响。 不适合发现非凸形状的簇,或者大小差别很大的簇。背景背景 DBSCAN(Density Based Spatial Clustering of Application with Noise,具有噪声的基于密度的空间聚类应用)由Ester、Kriegel、Sande和Xu于1996年提出,是一种基于高密度连接区域的密度聚类算法。 该算法将具有足够高密度的区域划分成簇,并可以在带有“噪声”的空间数据库中发现任意形
10、状的聚类,它定义簇为密度相连的点的最大集合。基本概念基本概念基本概念基本概念连接性和最大性连接性和最大性概念解释概念解释 由上图可看出m,p,o,r 都是核心对象,因为他们的内都只是包含3个对象。对象q是从m直接密度可达的。对象m从p直接密度可达的。对象q是从p(间接)密度可达的,因为q从m直接密度可达,m从p直接密度可达。r和s是从o密度可达的,而o是从r密度可达的,所有o,r和s都是密度相连的。 算法流程算法流程算法:DBSCAN算法。基于高密度连接区域的密度聚类算法。 DBSCANDBSCAN算法总结算法总结 聚类速度快且能够有效处理噪声点和发现任意形状的空间聚类。聚类速度快且能够有效处
11、理噪声点和发现任意形状的空间聚类。 与与K-means比较起来,不需要输入要划分的聚类个数。比较起来,不需要输入要划分的聚类个数。 聚类簇的形状没有偏倚。聚类簇的形状没有偏倚。 可以在需要时输入过滤噪声的参数。可以在需要时输入过滤噪声的参数。 当数据量增大时,要求较大的内存支持当数据量增大时,要求较大的内存支持I/O消耗也很大。消耗也很大。 当空间聚类的密度不均匀、聚类间距差相差很大时,聚类质量较当空间聚类的密度不均匀、聚类间距差相差很大时,聚类质量较差,因为这种情况下参数差,因为这种情况下参数、MinPts选取困难。选取困难。 算法聚类效果依赖于距离公式选取,实际应用中常用欧式距离,算法聚类
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第6章 无监督学习ppt课件 监督 学习 ppt 课件
限制150内