9005a8a1ed74878d8dd8f2b7f3e6f781.gif

向AI转型的程序员都关注了这个号👇👇👇

聚类分析的概念

聚类分析是根据在数据中发现的描述对象及其关系的信息,将数据对象分组。目的是,组内的对象相互之间是相似的(相关的),而不同组中的对象是不同的(不相关的)。组内相似性越大,组间差距越大,说明聚类效果越好。

也就是说, 聚类的目标是得到较高的簇内相似度和较低的簇间相似度,使得簇间的距离尽可能大,簇内样本与簇中心的距离尽可能小

聚类得到的簇可以用聚类中心、簇大小、簇密度和簇描述等来表示

  • 聚类中心是一个簇中所有样本点的均值(质心)

  • 簇大小表示簇中所含样本的数量

  • 簇密度表示簇中样本点的紧密程度

  • 簇描述是簇中样本的业务特征

聚类的过程

  • 数据准备:包括特征标准化和降维;

  • 特征选择:从最初的特征中选择最有效的特征,并将其存储于向量中;

  • 特征提取:通过对所选择的特征进行转换形成新的突出特征;

  • 聚类(或分组):首先选择合适特征类型的某种距离函数(或构造新的距离函数)进行接近程度的度量,而后执行聚类或分组;

  • 聚类结果评估:是指对聚类结果进行评估,评估主要有3种:外部有效性评估、内部有效性评估和相关性测试评估。

良好聚类算法的特征

  • 良好的可伸缩性

  • 处理不同类型数据的能力

  • 处理噪声数据的能力

  • 对样本顺序的不敏感性

  • 约束条件下的表现

  • 易解释性和易用性

聚类分析的要求

不同的聚类算法有不同的应用背景,有的适合于大数据集,可以发现任意形状的聚簇;有的算法思想简单,适用于小数据集。总的来说,数据挖掘中针对聚类的典型要求包括:

(1)可伸缩性:当数据量从几百上升到几百万时,聚类结果的准确度能一致。

(2)处理不同类型属性的能力:许多算法针对的数值类型的数据。但是,实际应用场景中,会遇到二元类型数据,分类/标称类型数据,序数型数据。

(3)发现任意形状的类簇:许多聚类算法基于距离(欧式距离或曼哈顿距离)来量化对象之间的相似度。基于这种方式,我们往往只能发现相似尺寸和密度的球状类簇或者凸型类簇。但是,实际中类簇的形状可能是任意的。

(4)初始化参数的需求最小化:很多算法需要用户提供一定个数的初始参数,比如期望的类簇个数,类簇初始中心点的设定。聚类的结果对这些参数十分敏感,调参数需要大量的人力负担,也非常影响聚类结果的准确性。

(5)处理噪声数据的能力:噪声数据通常可以理解为影响聚类结果的干扰数据,包含孤立点,错误数据等,一些算法对这些噪声数据非常敏感,会导致低质量的聚类。

(6)增量聚类和对输入次序的不敏感:一些算法不能将新加入的数据快速插入到已有的聚类结果中,还有一些算法针对不同次序的数据输入,产生的聚类结果差异很大。

(7)高维性:有些算法只能处理2到3维的低纬度数据,而处理高维数据的能力很弱,高维空间中的数据分布十分稀疏,且高度倾斜。

(8)可解释性和可用性:我们希望得到的聚类结果都能用特定的语义、知识进行解释,和实际的应用场景相联系。

几种常用的聚类算法从可伸缩性、适合的数据类型、高维性(处理高维数据的能力)、异常数据的抗干扰度、聚类形状和算法效率6个方面进行了综合性能评价

28334bed08369a16ee14694b623c07f8.png


聚类分析的度量

聚类分析的度量指标用于对聚类结果进行评判,分为内部指标外部指标两大类

  • 外部指标指用事先指定的聚类模型作为参考来评判聚类结果的好坏

  • 内部指标是指不借助任何外部参考,只用参与聚类的样本评判聚类结果好坏

外部指标

953cc49cc9570a7f70a2568cc6bfa3d2.png

c3b6f6798424dfe10b64119a4da048ba.png

b899a826eba802111b14192cfd94c222.png

56bcb4898dfa5aa2d31db77dc947b4d9.png

9f741ec1309adefa845e2dc12050e4bd.png

聚类的分类

  • 基于划分的聚类(k‐均值算法、k‐medoids算法、k‐prototype算法)

  • 基于层次的聚类

  • 基于密度的聚类(DBSCAN算法、OPTICS算法、DENCLUE算法)

  • 基于网格的聚类

  • 基于模型的聚类(模糊聚类、Kohonen神经网络聚类)

基于划分的聚类

基于划分的方法是简单、常用的一种聚类方法,它通过将对象划分为互斥的簇进行聚类, 每个对象属于且仅属于一个簇;划分结果旨在使簇之间的相似性低,簇内部的相似度高;基于划分的方法常用算法有k均值、k‐medoids、k‐prototype等

K-means聚类

k‐均值聚类是基于划分的聚类算法,计算样本点与类簇质心的距离,与类簇质心相近的样本点划分为同一类簇。k‐均值通过样本间的距离来衡量它们之间的相似度,两个样本距离越远,则相似度越低,否则相似度越高

d8d0c7acfe429d24e70caa3956c29dcd.png

优缺点及拓展:

  • k‐均值算法原理简单,容易实现,且运行效率比较高(优点)

  • k‐均值算法聚类结果容易解释,适用于高维数据的聚类(优点)

  • k‐均值算法采用贪心策略,导致容易局部收敛,在大规模数据集上求解较慢(缺点)

  • k‐均值算法对离群点和噪声点非常敏感,少量的离群点和噪声点可能对算法求平均值产生极大影响,从而影响聚类结果(缺点)

  • k‐均值算法中初始聚类中心的选取也对算法结果影响很大,不同的初始中心可能会导致不同的聚类结果。对此,研究人员提出k‐均值++算法,其思想是使初始的聚类中心之间的相互距离尽可能远

K-means++聚类

5e14efe48df09cf1915a6e5015a4eeea.png

k‐均值++算法的优缺点

  • 优点:
    提高了局部最优点的质量
    收敛更快

  • 缺点:
    相比随机选择中心点计算较大

sklearn.cluster.KMeans函数默认使用k-means++算法(init=‘k-means++’):

aead3b74f4c723fed42a2fda68f91161.png

代码1(鸢尾花的三个特征聚类)

e72f3bb1d310c3223eb5dac9e77bd443.png5f94f116767d56038c5fe4d672cd21a9.png

7b161014e0872ef2870952bede8fe685.png

使用k‐均值聚类的注意事项:

  • 模型的输入数据为数值型数据(如果是离散变量,需要作哑变量处理

  • 需要将原始数据作标准化处理(防止不同量纲对聚类产生影响)

对k值的选取,主要有以下几种:

  • 与层次聚类算法结合,先通过层次聚类算法得出大致的聚类数目,并且获得一个初始聚类结果,然后再通过k‐均值算法改进聚类结果

  • 基于系统演化的方法,将数据集视为伪热力学系统,在分裂和合并过程中,将系统演化到稳定平衡状态从而确定k值

拓展:KNN和K-means的不同

写到这里,让我想起了k-近邻算法(KNN),那么他们之间存在着哪些异同点?

KNN

首先,KNN是什么?

KNN是通过测量不同特征值之间的距离进行分类。它的思路是:如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别,则该样本也属于这个类别,其中K通常是不大于20的整数。KNN算法中,所选择的邻居都是已经正确分类的对象。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。

在KNN中,通过计算对象间距离来作为各个对象之间的非相似性指标,避免了对象之间的匹配问题,在这里距离一般使用欧氏距离或曼哈顿距离。

如右图,绿色圆要被决定赋予哪个类,是红色三角形还是蓝色四方形?

如果K=3,由于红色三角形所占比例为2/3,绿色圆将被赋予红色三角形那个类,

如果K=5,由于蓝色四方形比例为3/5,因此绿色圆被赋予蓝色四方形类。

由此也说明了KNN算法的结果很大程度取决于K的选择。

KNN算法:在训练集中数据和标签已知的情况下,输入测试数据,将测试数据的特征与训练集中对应的特征进行相互比较,找到训练集中与之最为相似的前K个数据,则该测试数据对应的类别就是K个数据中出现次数最多的那个分类,其算法的描述为:

1)计算测试数据与各个训练数据之间的距离;

2)按照距离的递增关系进行排序;

3)选取距离最小的K个点;

4)确定前K个点所在类别的出现频率;

5)返回前K个点中出现频率最高的类别作为测试数据的预测分类。

KNN和K-means的区别

K-means算法把一个数据集分割成簇,使得形成的簇是同构的,每个簇里的点相互靠近。该算法试图维持这些簇之间有足够的可分离性。由于无监督的性质,这些簇没有任何标签。

KNN算法尝试基于其k(可以是任何数目)个周围邻居来对未标记的观察进行分类。它也被称为懒惰学习法,因为它涉及最小的模型训练。因此,它不用训练数据对未看见的数据集进行泛化

6b6da5fb33034cc76933d5663d865b85.png

94684846cf54cf4e0493c4c18d68d2da.png

f2d211afa31ab56b1aae2ba32daa1e9d.png

不得不说,K-means和PAM算法都不可避免有一个弱点,就是计算量上都是随着初始数据量的增大而几何增长的,它适用于小型数据集,那么有什么算法是可以用于大规模的数据集呢?接下来我们将了解CLARA算法以及他衍生出来的算法

CLARA算法

CLARA(Clustering LARge Applications)是应用于大规模数据的聚类,它弥补了k-mediod / PAM算法只能应用于小规模数据的缺陷。

当面对一个大样本量时,CLARA首先通过运用类似于randomforest的随机抽样的方法,每次随机选取样本量中的一小部分进行PAM聚类,然后将剩余样本按照最小中心距离进行归类。在各次重复抽样聚类的结果中,选取误差最小,即中心点代换代价最小的结果作为最终结果。核心是,先对大规模数据进行多次采样,每次采样样本进行k-mediod聚类,然后将多次采样的样本聚类中心进行比较,选出最优的聚类中心.

bca7d11bd024e3ddd112c0f82a41cf6d.png

f1de28f2e39fff83a0fda7cacac218c6.png

9d475992505e2fa43e972a83ac38c6e4.png

47ef8808b6ed9e42c6e2f636c5153586.png

基于层次的聚类

层次聚类的应用广泛程度仅次于基于划分的聚类,核心思想是通过对数据集按照层次,把数据划分到不同层的簇,从而形成一个树形的聚类结构。层次聚类算法可以揭示数据的分层结构,在树形结构上不同层次进行划分,可以得到不同粒度的聚类结果。按照层次聚类的过程分为自底向上的聚合聚类和自顶向下的分裂聚类。聚合聚类以AGNES、BIRCH、ROCK等算法为代表,分裂聚类以DIANA算法为代表。

自底向上的聚合聚类将每个样本看作一个簇,初始状态下簇的数目等于样本的数目,然后然后根据一定的算法规则,例如把簇间距离最小的相似簇合并成越来越大的簇,直到满足算法的终止条件。

自顶向下的分裂聚类先将所有样本看作属于同一个簇,然后逐渐分裂成更小的簇,直到满足算法终止条件为止。

目前大多数是自底向上的聚合聚类,自顶向下的分裂聚类比较少

bb6f3a82c75c139eb4997fcaedc42a91.png

BIRCH(平衡迭代削减聚类法)

BIRCH(Balanced Iterative Reducingand Clustering Using Hierarchies利用层次方法的平衡迭代规约和聚类)主要是在数据量很大的时候使用,而且数据类型是numerical。首先利用树的结构对对象集进行划分,然后再利用其它聚类方法对这些聚类进行优化;

BIRCH算法的优缺点:

适合大规模数据集,线性效率

只适合分布呈凸形或者球形的数据集,需要给定聚类个数和簇直径的限制

CURE算法(使用代表点的聚类法)

CURE算法先把每个数据点看成一类,然后合并距离最近的类直至类个数为所要求的个数为止。但是和AGNES算法的区别是:取消了使用所有点或用中心点+距离来表示一个类,而是从每个类中抽取固定数量、分布较好的点作为此类的代表点,并将这些代表点乘以一个适当的收缩因子,使它们更加靠近类中心点。代表点的收缩特性可以调整模型可以匹配那些非球形的场景,而且收缩因子的使用可以减少噪音对聚类的影响。

CURE算法的优缺点:

能够处理非球形分布的应用场景

采用随机抽样和分区的方式可以提高算法的执行效率

ROCK

ROCK(A Hierarchical ClusteringAlgorithm for Categorical Attributes)主要用在categorical的数据类型上;Chameleon(A Hierarchical Clustering AlgorithmUsing Dynamic Modeling)里用到的linkage是kNN(k-nearest-neighbor)算法,并以此构建一个graph,Chameleon的聚类效果被认为非常强大,比BIRCH好用,但运算复杂度很高,O(n^2)。

代码

AgglomerativeClustering是scikit-learn提供的层级聚类算法模型。一般只需要设置参数linkage和n_clusters,

其中n_clusters是一个正整数,指定分类簇的数量;

linkage是一个字符串,用于指定链接算法 :当其值为“ward”时表示采用单链接方法,值为“complete”时表示采用全链接方法,若取值为“average”时则使用均连接方法。

f61504e2e08083faf43d4b0583875328.png2ef300a1533265dbf40cef94d452d53c.png

0b92b4f3c1c8296d9ff07b07f1dc7f61.png

0eb31b1e76efcc8a0589e324b2b5126b.png

基于密度的聚类

基于划分聚类和基于层次聚类的方法在聚类过程中根据距离来划分类簇,因此只能够用于挖掘球状簇。但往往现实中还会有各种形状,这时上面的两大类算法将不适用了。

20791d146d9a188f1d01cb22611f9157.png

为了解决这一缺陷,基于密度聚类算法利用密度思想,将样本中的高密度区域(即样本点分布稠密的区域)划分为簇,将簇看作是样本空间中被稀疏区域(噪声)分隔开的稠密区域。

这一算法的主要目的是过滤样本空间中的稀疏区域,获取稠密区域作为簇基于密度的聚类算法是根据密度而不是距离来计算样本相似度,所以基于密度的聚类算法能够用于挖掘任意形状的簇,并且能够有效过滤掉噪声样本对于聚类结果的影响。

常见的基于密度的聚类算法有DBSCAN、OPTICS和DENCLUE等。其中,OPTICS 对DBSCAN算法进行了改进,降低了对输入参数的敏感程度。DENCLUE算法综合了基于划分、基于层次的方法

DBSCAN 算法

DBSCAN(Density-Based Spatial Clustering of Applications with Noise,具有噪声的基于密度的聚类方法)是一种基于密度的空间聚类算法。该算法将具有足够密度的区域划分为簇,并在具有噪声的空间数据库中发现任意形状的簇,它将簇定义为密度相连的点的最大集合。

看了赵卫东老师和嵩天老师关于这部分的介绍,我可以说,不是很容易懂,不过,下面这两个网站可以让我们看懂很DBSCAN 算法:首先先看第一个,看了之后再看下面这个配套动画讲解DBSCAN算法的国外网站,你会发现看我下面写的东西原来也不是那么难理解了

f7855d1a17ef4c82642cb21842b85857.png

d2aeb4ee627f5ddb6fae4922a4f1b11f.png

1d486d975077612392f9ca1d33e0c5cb.png

7c789b90be2af3aed71a6825ecc88f96.png

3ccb950acee47273846caea2b05897a4.png

060368f58dd6487f3ebb207e8fec6af1.png

    原文地址

https://blog.csdn.net/weixin_43584807/article/details/105539675


机器学习算法AI大数据技术
 搜索公众号添加: datanlp

长按图片,识别二维码
阅读过本文的人还看了以下文章:
TensorFlow 2.0深度学习案例实战

基于40万表格数据集TableBank,用MaskRCNN做表格检测

《基于深度学习的自然语言处理》中/英PDF

Deep Learning 中文版初版-周志华团队

【全套视频课】最全的目标检测算法系列讲解,通俗易懂!

《美团机器学习实践》_美团算法团队.pdf

《深度学习入门:基于Python的理论与实现》高清中文PDF+源码

《深度学习:基于Keras的Python实践》PDF和代码

特征提取与图像处理(第二版).pdf

python就业班学习视频,从入门到实战项目

2019最新《PyTorch自然语言处理》英、中文版PDF+源码
《21个项目玩转深度学习:基于TensorFlow的实践详解》完整版PDF+附书代码

《深度学习之pytorch》pdf+附书源码

PyTorch深度学习快速实战入门《pytorch-handbook》

【下载】豆瓣评分8.1,《机器学习实战:基于Scikit-Learn和TensorFlow》

《Python数据分析与挖掘实战》PDF+完整源码

汽车行业完整知识图谱项目实战视频(全23课)

李沐大神开源《动手学深度学习》,加州伯克利深度学习(2019春)教材

笔记、代码清晰易懂!李航《统计学习方法》最新资源全套!
《神经网络与深度学习》最新2018版中英PDF+源码

将机器学习模型部署为REST API
FashionAI服装属性标签图像识别Top1-5方案分享

重要开源!CNN-RNN-CTC 实现手写汉字识别

yolo3 检测出图像中的不规则汉字
同样是机器学习算法工程师,你的面试为什么过不了?

前海征信大数据算法:风险概率预测

【Keras】完整实现‘交通标志’分类、‘票据’分类两个项目,让你掌握深度学习图像分类

VGG16迁移学习,实现医学图像识别分类工程项目
特征工程(一)

特征工程(二) :文本数据的展开、过滤和分块

特征工程(三):特征缩放,从词袋到 TF-IDF

特征工程(四): 类别特征

特征工程(五): PCA 降维

特征工程(六): 非线性特征提取和模型堆叠

特征工程(七):图像特征提取和深度学习

如何利用全新的决策树集成级联结构gcForest做特征工程并打分?

Machine Learning Yearning 中文翻译稿
蚂蚁金服2018秋招-算法工程师(共四面)通过

全球AI挑战-场景分类的比赛源码(多模型融合)

斯坦福CS230官方指南:CNN、RNN及使用技巧速查(打印收藏)

python+flask搭建CNN在线识别手写中文网站
中科院Kaggle全球文本匹配竞赛华人第1名团队-深度学习与特征工程
不断更新资源
深度学习、机器学习、数据分析、python
 搜索公众号添加: datayx
Logo

为开发者提供学习成长、分享交流、生态实践、资源工具等服务,帮助开发者快速成长。

更多推荐