专栏首页AI小白入门【机器学习】层次聚类

【机器学习】层次聚类

本文介绍了层次聚类算法。首先抛出了聚类理论中两个关键问题:何为类,何为相似,同时介绍了聚类中常用两种评价指标:内部指标和外部指标。然后介绍了层次聚类算法:凝聚层次聚类和分裂层次聚类算法,两者皆以样本集作为类表示,常用欧式距离作为相似性度量,分层次聚类。最后介绍了层次聚类算法的特点,可视化,复杂度。

作者 | 文杰

编辑 | yuquanle

聚类理论

一般来说,聚类是在训练样本的标签信息不知的情况下,学习样本内在的性质和规律,将有限的集合划分成类。

根据“方以类聚,物以群分”的思想,类内对象尽可能的相似,类间对象尽可能不相似。因此,吾师言:聚类中两个关键的问题是:何为类?何为类内相似,类间不相似?以下所有的聚类模型皆从这两点出发。

由于缺少样本标签,我们很难定义类和相似性,比如下面的问题:

按照颜色聚类可以分类三类,按照形状聚类可以分类两类,关键问题在于如何定义类,定义相似性。所以吾师还言:聚类一般不是一个任务的最终目标,而是一个预处理的过程。

聚类的评价指标有两种:

  1. 内部指标,指导思想是类内紧致性和类间分离性,比如Xie-Beni指标,DB指标;
  2. 外部指标,假设数据集有标注,按有监督学习的评价指标进行评价。

可以看出,外部指标有很大的问题,那就是聚类学到的数据规律不一定是标签,这对聚类算法的评价是不可靠的,但是对于只看结果,不评价模型的好坏是可以的,当然拿聚类的结果与有监督学习的结果对比是“无赖”的。

层次聚类

层次聚类的类表示可以看作是基于样本的,表示属于第的样本集合,即作为第类的类表示。类相似性度量可以用“欧式距离”。

层次聚类分为两种,一种是自底向上的凝聚层次聚类,一种是自顶向下的分裂层次聚类。两者的区别在于前者一开始将每一个样本看作一类,通过不断的合并最相似的两个簇,直到类;后者一开始将所有样本看作一类,通过最小化损失(类紧致)分裂为类。

凝聚层次聚类

输入:样本数据,相似性度量函数,聚类簇数

输出:类样本

1)初始化每个样本为一个簇:

2)计算样本两两之间的距离:

3)通过相似性度量函数,找出最相似的两个簇进行合并:

最小距离:

最大距离:

平均距离:

4)直到簇数为,否则循环2)

分裂层次聚类

输入:样本数据,损失函数,聚类簇数

输出:类样本

1)初始化所有样本为一个簇:

2)计算样本两两之间的距离:

3)计算当前所有簇,的损失函数,选择损失最大的簇进行二分,计算该簇下两点间距离:

选择簇中最远的两个点作为类中心将簇进行二分;

4)直到簇数为,否则循环2)

值得注意的是分裂层次聚类在进行二分时,可以采用kmeans进行二分,这样时间复杂度就不再是.

层次聚类算法特点:

  • 可视化
  • 采用计算样本两两之间的距离,时间复杂度为
  • 凝聚和分裂的不可逆性

The End

本文分享自微信公众号 - AI小白入门(StudyForAI),作者:文杰

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-04-06

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【机器学习】谱聚类

    本文介绍了一种定义在图上聚类算法-谱聚类。首先介绍谱聚类其实是保持图上节点之间的相似性对节点进行向量表示。然后介绍了谱聚类的目标函数-最小化原始相似性矩阵与样本...

    yuquanle
  • 【机器学习】Kmeans

    本文介绍了K-means聚类算法。首先介绍了K-means算法是一种原型聚类算法,其类表示为类中心点,常用欧式距离作为相似性度量。然后由类内紧致准则给出了Kme...

    yuquanle
  • 【机器学习】密度聚类

    本文介绍了一种无参的密度聚类算法-DBSCAN。首先介绍了DBSCAN的类表示为一簇密度可达的样本点,相似性度量为密度可达。然后介绍了DBSCAN中几个基本定义...

    yuquanle
  • Must Know! 数据科学家们必须知道的 5 种聚类算法

    聚类是一种关于数据点分组的机器学习技术。给出一组数据点,我们可以使用聚类算法将每个数据点分类到特定的组中。理论上,同一组中的数据点应具有相似的属性或特征,而不同...

    AI研习社
  • OpenCV学习入门(三):kmeans原理及代码

    Kmeans是一种非监督的聚类方法,是最常用的聚类技术之一。kmeans尝试找到数据的自然类别,通过用户设定的类别个数K,它可以快速的找到“好的”类别中心,“好...

    用户1150922
  • 数据科学家必须了解的六大聚类算法:带你发现数据之美

    机器之心
  • factoextra包 聚类分析(2)

    聚类分析是一种数据贵呀技术,旨在揭露数据集中观测值的子集。它可以把大量的观测值归为若干个类。这里的类被定义为若干个观测值组成的群组,群组内观测值的相似度比群间的...

    用户1359560
  • 机器学习算法之聚类算法

    "If you set your goals ridiculously high and it's a failure, you will fail above...

    小闫同学啊
  • 人人都能读懂的无监督学习:什么是聚类和降维?

    可以说机器学习已经成为了改变时代的大事,一时间似乎人人都应该懂一点机器学习。但机器学习涉及到的数学知识和编程能力往往让没有相关经验的人望而却步。YupTechn...

    小莹莹
  • 独家 | 如何在BigQueryML中使用K-均值聚类来更好地理解和描述数据(附代码)

    本文教你如何在BigQueryML中使用K均值聚类对数据进行分组,进而更好地理解和描述。

    数据派THU

扫码关注云+社区

领取腾讯云代金券