当前课程知识点:机器学习概论 >  第八章 支持向量机(II)和无监督学习 >  8.6 层次聚类 >  层次聚类

返回《机器学习概论》慕课在线视频课程列表

层次聚类在线视频

下一节:K-means聚类和K-medoids聚类

返回《机器学习概论》慕课在线视频列表

层次聚类课程教案、知识点、字幕

好 介绍完这些非常基本的东西之后

我们来了解我们今天会尝试给大家介绍三种不同的

并且是非常经典的 都是很经典聚类的算法

第一个是层次聚类的方法 层次聚类我们如图所示

事实上它往往很多常见的情况 绝大多数都是可以呈现出

一个树的结构 在这个树的结构下 每一个中间上一层的这个节点

都包括它下面的所有的子节点的类 然后兄弟节点它们相对而言

都属于同一个副节点 它们都会有一些共同的

都是属于上一层的这个节点 所以其实这种层次聚类事实上

是一种很有效的办法 让我们发现数据之间不同粒度之间的关系

这个粒度指的是 就是颗粒的粒 不同粒度之间的

数据之间的结构关系 给大家看一个示意图 这个是层次聚类

层次聚类有两种不同的做法 一种是 自底向上的

我们把它叫做聚合式的就是Agglomerative clustering 它的意思是说

15clustering
00:01:36,050 --> 00:01:42,500
我们原来每个点自己是一类 然后我们把最相近的合并起来

然后再接下来变成了一个簇 变成了一个cluster

然后接下来我们再把最相近的点或者cluster再聚到一起来

又继续往上聚 直到我们最后生成了两个类 因为再往上

就意味它们都属于同一类了 所以这个是自底向上的层次

的聚集式的凝聚类的聚类

还有一种方法是top-down它自上而下的划分式的这种Divisive的这种方法

我们一开始是一大类 我先切一刀把它切成两类

然后每一类里面分别再分成两类 分成两类等等

一直到最底下你觉得可以停止就OK了

相对而言层次划分复杂度更高一点 你怎么找到哪一刀更合适

这个会比较复杂 而更多的我们会使用这种层次

聚类自己向上的层次聚类的办法 层次聚类的办法

我们简单说一下算法其实是非常简单的 使得最初起始条件

每个数据点它自己就是一类 然后接下来我们就对当前的

这种聚类的cluster来说 我们要找到最近的那两个类

就找到两个cluster 这两个cluster之间的距离是最相似的

它们最近 也可以认为它们是最近的 然后把这两类合并成一个类

然后再继续持续下去 直到你最后只剩下一个类了

就全都合并成一个大类就OK了 其实这个时候就会涉及到问题

点和点之间的距离 我们的相似度我们是知道的

我们刚才已经讨论过很多 那么类和类之间的相似度怎么计算呢

有很多种不同的办法 一种办法非常简单

我们把它叫做single linkage 就看一个点

看我们这两类之间的距离最小的那一个点 就是minimum

那个相似度 我们就把它作为这两个类之间的相似度

这个是第一个 然后如果两个类合并之后

就是Ci和Cj假如说他们已经合并了

我们要求它和Ck另外的一个类 就两个小类合并成一类之后

它和另外一个类的距离 我们相似度

我们就会看它分别合并之前的每一个类 跟另外的那个类的相似度

哪个小 就用哪个 假设我们原来的这个情况下

这两个类被聚到了一起 那么聚完了这个新的这个类

和第三个类它们的相似度 就等于这两个类之间的相似度

和这两个类 这是两个类 它里面还有点的

这两个类之间相似度和这两个类之间的相似度哪个更小

就取哪个 作为这个新的类和另外一个类之间的相似度

我们把这种做法叫做single linkage 还有叫Complete linkage

Complete linkage是说我们假如Ci和Cj之间的相似度

是等于它们之间相似度的最大值 如果像这种合并之后的类

和这个类 事实上也是去找单独的每一个类

合并前每一个类和第三个类之间的相似度

它们的哪一个最大就作为这个相似度

当然存在第三种linkage方法 就叫做Average linkage

就是平均linkage 那Average大家最好理解的了

两个类之间的相似度就等于这两个类之间所有点

两两之间相似度的平均值 如果是合并之后的类

其实就等于这两个类之间的相似度乘以它的系数

就是Ci这个类的大小 就是加权的合并

就两个类之间的相似度和另外的这两个类之间的相似度

它们的加权合并 要看哪个点多 哪个起到的影响就多一点

这三种cluster之间similarity的计算方法 都很常用 而且在不同情况下哪个效果更好 不一定

所以这个需要在我们通过学习的过程中 在training过程中学习出来

搞清楚这些问题之后 给大家讨论一下 比如说是聚类问题

有一些意大利的城市 我们假设是用欧氏距离

然后用Single linkage 就是两个之间的距离越小

那么我们就可以把它合并起来 我们原来这有很多个意大利的城市

你这个城市之间的距离的一个相似度的矩阵

接下来我们会看在这些里面 最小的是这个 MI米兰和Torino

是叫什么来着(都灵) 和Torino 然后这两个之间它们距离很近

于是我们就把它合并成一个新的类 合并成新的类之后

这个类合并出来的 就是MI/TO这个类和其他所有类之间的距离

就用这个最小距离来去代替了 在新的上面

我们会发现它跟219的这个 就是和NA这个最近

所以我们就把这两个NA和RM 就是罗马和NA最近

我们把这两个聚到一起了 再接下来它们合并之后

我们再去更新这个 基于最小距离来去替代

作为这个类和其他类之间的距离的代表

然后又会发现新的比较近的 我们就把这三个聚到一起了

然后再接下来又把它们聚到一起 然后又形成了我们这样一个

聚类的办法 这是它不同的城市 这是其中hierarchical

然后你就可以看到经过把聚的过程记录下来就是我们最后

Hierarchical Agglomerative聚类的结果

所以你可以说我如果想要距离最近的 在这砍一刀

你可以是1、2、3、4、5、6 6个城市 你如果在这砍一刀

你就可以到5个类 如果在这砍一刀 你可以得到三个类

那如果在这来一层那就是两个类 所以说层次聚类

它可以在不同的粒度上面 在不同的详略的情况下

来给我们给出不同聚类的结果 这个聚类的方法被提出来很多年了

而且其实也很简单 看起来不是那么复杂

尤其是我们大家刚经过SVM那个算法洗礼之后

会觉得这个太简单了 就计算一下距离

甚至对比一下最大、最小就行了 但是它很有用

我们给大家一个例子 这个是在2014年

就几年之前发表在《science》上的一篇paper

所以大家可以看到在很多研究领域 这样的算法仍然很有用

而且是在最前沿的工作里面是仍然能够起到帮助的

这个是一个《science》上的一篇paper的实验 当然它是生物科学上的一个实验

他们当时是在癫痫病人的脑中插了很多电极

每一列就是一个电极 然后横坐标 每一行是一个发音

就是英文音标的发音 比如说这有什么D、W、R

就是音标上面的发音/d/等等这样的发音

然后他们会发现对于不同的电极 他对不同的发音

是有不一样的敏感性的 所以他得到了这样的一个热力学的图

然后其中颜色深的就表示这个电极对这样的语速的发音

会更敏感 颜色浅就说明这个电极就他不敏感

然后他们就做了两个聚类 第一个记录是在这个力度上

去看哪些电极他们呈现的很接近 你就会看到这是一块

然后这是另外一块层次聚类 中间这是一块 然后这右边是三块

相关的层次聚类的结果 所以这个就会发现原来

有一批他们的电极就插在不同位置的电极 他们是有类似的

相似的对语音信号的响应 横着也可以

会发现原来这几个因素的发音它们很像

他们至少在物理刺激的电极上 这几个因素的发音

他们是有共同点的 然后还有这些是有共同点

这个就不是从语言学 而是从脑科学的这个角度

从生物的这个角度去看哪些发音是比较接近的

跟我们的脑电是有相关的 所以这个是很好的利用

层次聚类的方法能够很好起到帮助的研究的问题

那么这种层次聚类的办法 我们来讨论一下它的优点很明显

你可以很灵活 你可以指定不同 你最后使用的时候

可以使用不同的粒度就可以得到不同的结果

而且你处理不同similarity的时候 还是很方便的

所以可以对任何的atrribute type 就是属性的类型实数的、binary的

或者是序关系或者是没有序关系的这种描述类的都可以

但是它的缺点 缺点是什么时候停止 除非去把它全聚完了

否则应该停在哪一层就停止 这个标准很模糊 而且不太好比

还有计算起来其实挺复杂的 因为在有的选择下面

比如说average 你得计算任何两点之间的距离 然后再求一个average

机器学习概论课程列表:

第一章 绪论

-1.1 课程介绍

--课程介绍(1)

--课程介绍(2)

-1.2 机器学习的背景

--机器学习的背景

-1.3 什么是机器学习

--什么是机器学习

-1.4 机器学习系统设计

--机器学习系统设计(1)

--机器学习系统设计(2)

-第一章作业

-第一章课件

第二章 决策树学习(I)

-2.1 决策树的基本概念

--决策树的基本概念

-2.2 决策树的实例和发展历史

--决策树的实例和发展历史

-2.3 经典决策树算法ID3

--经典决策树算法ID3(1)

--经典决策树算法ID3(2)

--经典决策树算法ID3(3)

-2.4 过拟合和前剪枝

--过拟合和前剪枝

-第二章作业

-第二章课件

第三章 决策树学习(II)和贝叶斯学习

-3.1 下午茶时间:勒索软件

--下午茶时间:勒索软件

-3.2 后剪枝

--后剪枝

-3.3 决策树的改进和归纳学习假设

--决策树的改进和归纳学习假设

-3.4 贝叶斯学习的背景

--贝叶斯学习的背景

-3.5 极大似然假设、朴素贝叶斯和最小描述长度

--极大似然假设、朴素贝叶斯和最小描述长度

-第三章作业

-第三章课件

第四章 马尔可夫模型和隐马尔可夫模型

-4.1 下午茶时间:微博的垃圾检测

--下午茶时间:微博的垃圾检测

-4.2 马尔可夫模型

--马尔可夫模型

-4.3 隐马尔可夫模型

--隐马尔可夫模型

-4.4 评估问题

--评估问题(1)

--评估问题(2)

-4.5 解码问题

--解码问题

-4.6 隐马尔可夫模型的应用

--隐马尔可夫模型的应用

-第四章课件

-第四章作业

第五章 假设检验

-5.1 下午茶时间:图灵奖

--下午茶时间:图灵奖(1)

--下午茶时间:图灵奖(2)

-5.2 假设评估

--假设评估(1)

--假设评估(2)

--假设评估(3)

-5.3 置信度和置信区间

--置信度和置信区间(1)

--置信度和置信区间(2)

--置信度和置信区间(3)

-5.4 有限数据下的比较

--有限数据下的比较

-第五章课件

-第五章作业

第六章 基于实例的学习

-6.1 下午茶时间:黑洞照片

--下午茶时间:黑洞照片

-6.2 基于实例的学习的基本概念

--基于实例的学习的基本概念

-6.3 最近邻算法

--最近邻算法

-6.4 K邻近算法

--K近邻算法

-6.5 KD树

--KD树

-6.6 距离加权的K近邻算法

--距离加权的K近邻算法

-第六章课件

-第六章考试

第七章 支持向量机(I)

-7.1 支持向量机的背景

--支持向量机的背景

-7.2 线性支持向量机

--线性支持向量机(1)

--线性支持向量机(2)

--线性支持向量机(3)

--线性支持向量机(4)

--线性支持向量机(5)

-第七章课件

-第七章作业

第八章 支持向量机(II)和无监督学习

-8.1 核函数支持向量机

--核函数支持向量机:向量空间

--核函数支持向量机:核函数(1)

--核函数支持向量机:核函数(2)

-8.4 支持向量机总结

--支持向量机总结

-8.5 无监督学习简介

--无监督学习简介(1)

--无监督学习简介(2)

-8.6 层次聚类

--层次聚类

-8.7 K-means聚类和K-medoids聚类

--K-means聚类和K-medoids聚类

-第八章课件

-第八章作业

层次聚类笔记与讨论

也许你还感兴趣的课程:

© 柠檬大学-慕课导航 课程版权归原始院校所有,
本网站仅通过互联网进行慕课课程索引,不提供在线课程学习和视频,请同学们点击报名到课程提供网站进行学习。