(5.1)--第五章聚类大数据机器学习.pdf

《(5.1)--第五章聚类大数据机器学习.pdf》由会员分享，可在线阅读，更多相关《(5.1)--第五章聚类大数据机器学习.pdf（30页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、大数据机器学习第五讲：聚类目录1.聚类任务描述2.性能度量3.原型聚类 K均值算法 学习向量算法4.密度聚类5.层次聚类聚类任务 无监督学习unsupervised learning 标记未知 揭示数据的内在性质和规律 应用最广的无监督学习：聚类聚类任务 聚类的形式化描述：样本集：每个样本：划分为k个不相交的簇：簇标记：聚类的结果可用包含m个元素的簇标记向量表示 聚类的重要性：其它学习任务的前驱过程；性能度量 什么样的聚类结果比较好呢？“簇内相似度”（intra-cluster similarity)高“簇间相似度”(inter-cluster similarity)低 性能度量“外部指标”(

2、external index)：计数法“内部指标”(internal index)：距离法性能度量“外部指标”(external index);计数 四类点对：a+b+c+d=m(m-1)/2，m为数据集的样例数性能度量“外部指标”(external index);计数 四类点对：a+b+c+d=m(m-1)/2，m为数据集的样例数 三个指标：Jaccard系数：FM指数Rand指数性能度量“内部指标”(internal index)：距离法性能度量“内部指标”(internal index)：距离法DB指标 DBI：Dunn指标 DI：距离计算 距离度量需满足的基本性质：非负性 同一性 对称

3、性 直递性性能度量 闵可夫斯基距离 P=2时，欧氏距离 P=1时，曼哈顿距离橙子（黄色，130g，8cm直径），如何计算距离？性能度量 有序属性 ordinal attribute Minkowski距离可计算 无序属性 non-ordinal attribute VDM（value difference metric）VDM mu,a表示在属性u上取值为a的样本数 mu,a,i表示在第i个样本簇中在属性u上取值为a的样本数 k为样本簇数，则属性u上两个离散值 a 与 b之间的 VDM 距离为性能度量 针对刚才混合属性的例子：橙子（黄色，130g，8cm直径）假设nc个有序属性、n-nc个无序

4、属性，则 样本间MinkoVDM距离为：加权距离：聚类算法 原型聚类 K均值算法 学习向量算法 高斯混合聚类（将在EM算法中详细介绍）密度聚类 层次聚类原型聚类 原型聚类prototype-based clustering 此类算法假设聚类结构能通过一组原型刻画；算法先对原型进行初始化，然后对原型进行迭代更新求解。原型聚类 K均值算法 给定样本集D=x1,x2xm;聚类得到的簇划分C=C1,C2Ck 最小化平方误差：为簇i的均值向量；E值越小则簇内样本相似度越高；问题：最小化E，实际需要样本集 D 所有可能的簇划分，NP难问题；贪心策略的迭代优化方法求解；K均值算法 输入：样本集D=x1,x2

5、xm；聚类簇数k 过程：1 从D 中随机选择k个样本作为初始均值向量i 2:repeat3：令 Ci=4：for j=1,2,，m do5:计算样本xj与各均值向量 i的距离6:根据距离最近的均值向量确定xj的簇标记j7：将样本xj划入相应的簇：Cj；8：end for9：for i=1,2,.,k do10:计算新均值向量：i11：end for12：until 当前均值向量均未更新 输出：簇划分C=(C1,C2Ck)K均值算法学习向量量化 学习向量量化（Learning Vector Quantization，LVQ）和k均值聚类的不同 每个样例有类别标签；输出不是簇的划分，是每个类别的原

6、型向量；每个类别的原型向量不是简单的均值向量，考虑了附近非同类样例的影响；学习向量量化 输入:样本集D=(x1,y1),(x2,y2),(xm,ym)；原型向量个数q,各原型向量预设的类别标记t1tq;学习率;过程：1:初始化一组原型向量p1,p2.pq;2:repeat3：从样本集随机选取样本(xj,yj)4：计算样本xj与Pi的距离5:找出与xj距离最近的原型向量pi*6:7:8:9:将原型向量 Pi*更新为p10:until 满足停止条件输出一组原型向量p1,p2.pq学习向量量化密度聚类 基于密度的聚类（density-based clustering）特点：假设聚类结构通过样本分布的

7、紧密程度确定,通常情形下,算法从样本密度的角度来考察样本之间的可连接性,并基于可连接样本不断扩展聚类簇以获得最终的聚类结果;密度聚类 基于一组“邻域”(neighborhood)参数(,MinPts):样本分布的紧密程度,概念:给定数据集D=x1,x2,xm,-邻域:包含样本集 D 中与xj的距离不大于的样本,即：核心对象(core object):若xj的-邻域至少包含 MinPts 个样本；密度直达:若xj位于的xi的-邻域中，且xi是核心对象，则称xj由xi密度直达；密度相连:对xi与xj,若存在xk使得与xi与xj均由xk密度可达,则称xi与xj密度相连；密度聚类密度聚类 密度聚类方法

8、：将“簇”定义为，由密度可达关系导出的最大的密度相连样本集合。例子：核心对象集：随机选取一个核心对象作为种子，找出由它密度可达的所有样本，这就构成了第一个聚类簇；如x8，作为种子：将C1中包含的核心对象从中去除，再从 中随机抽取一个核心对象做种子构成第二个聚类簇，上述过程不断重复，直到 为空；密度聚类层次聚类 层次聚类(hierarchical clustering)试图在不同层次对数据集进行划分,从而形成树形的聚类结构。AGNES方法 自底向上聚合策略的层次聚类算法；先将数据集中的每个样本看作一个初始聚类簇；然后在算法运行的每一步中找出距离最近的两个聚类簇进行合并；该过程不断重复，直至达到预设的聚类簇个数。层次聚类 给定聚类簇Ci与Cj，计算距离的方式：层次聚类Q&A？