聚类分析（超全超详细版）
共 6729字，需浏览 14分钟
·
2024-06-23 10:05
点击上方“小白学视觉”，选择加"星标"或“置顶”
重磅干货，第一时间送达
聚类分析的概念
聚类分析是根据在数据中发现的描述对象及其关系的信息，将数据对象分组。目的是，组内的对象相互之间是相似的（相关的），而不同组中的对象是不同的（不相关的）。组内相似性越大，组间差距越大，说明聚类效果越好。
也就是说， 聚类的目标是得到较高的簇内相似度和较低的簇间相似度，使得簇间的距离尽可能大，簇内样本与簇中心的距离尽可能小
聚类得到的簇可以用聚类中心、簇大小、簇密度和簇描述等来表示
聚类中心是一个簇中所有样本点的均值(质心)
簇大小表示簇中所含样本的数量
簇密度表示簇中样本点的紧密程度
簇描述是簇中样本的业务特征
聚类的过程
数据准备：包括特征标准化和降维；
特征选择：从最初的特征中选择最有效的特征,并将其存储于向量中；
特征提取：通过对所选择的特征进行转换形成新的突出特征；
聚类(或分组)：首先选择合适特征类型的某种距离函数(或构造新的距离函数)进行接近程度的度量，而后执行聚类或分组；
聚类结果评估：是指对聚类结果进行评估，评估主要有3种：外部有效性评估、内部有效性评估和相关性测试评估。
良好聚类算法的特征
良好的可伸缩性
处理不同类型数据的能力
处理噪声数据的能力
对样本顺序的不敏感性
约束条件下的表现
易解释性和易用性
聚类分析的要求
不同的聚类算法有不同的应用背景，有的适合于大数据集，可以发现任意形状的聚簇；有的算法思想简单，适用于小数据集。总的来说，数据挖掘中针对聚类的典型要求包括：
（1）可伸缩性：当数据量从几百上升到几百万时，聚类结果的准确度能一致。
（2）处理不同类型属性的能力：许多算法针对的数值类型的数据。但是，实际应用场景中，会遇到二元类型数据，分类/标称类型数据，序数型数据。
（3）发现任意形状的类簇：许多聚类算法基于距离（欧式距离或曼哈顿距离）来量化对象之间的相似度。基于这种方式，我们往往只能发现相似尺寸和密度的球状类簇或者凸型类簇。但是，实际中类簇的形状可能是任意的。
（4）初始化参数的需求最小化：很多算法需要用户提供一定个数的初始参数，比如期望的类簇个数，类簇初始中心点的设定。聚类的结果对这些参数十分敏感，调参数需要大量的人力负担，也非常影响聚类结果的准确性。
（5）处理噪声数据的能力：噪声数据通常可以理解为影响聚类结果的干扰数据，包含孤立点，错误数据等，一些算法对这些噪声数据非常敏感，会导致低质量的聚类。
（6）增量聚类和对输入次序的不敏感：一些算法不能将新加入的数据快速插入到已有的聚类结果中，还有一些算法针对不同次序的数据输入，产生的聚类结果差异很大。
（7）高维性：有些算法只能处理2到3维的低纬度数据，而处理高维数据的能力很弱，高维空间中的数据分布十分稀疏，且高度倾斜。
（8）可解释性和可用性：我们希望得到的聚类结果都能用特定的语义、知识进行解释，和实际的应用场景相联系。
几种常用的聚类算法从可伸缩性、适合的数据类型、高维性（处理高维数据的能力）、异常数据的抗干扰度、聚类形状和算法效率6个方面进行了综合性能评价
聚类分析的度量
外部指标
聚类的分类
基于划分的聚类(k‐均值算法、k‐medoids算法、k‐prototype算法)
基于层次的聚类
基于密度的聚类(DBSCAN算法、OPTICS算法、DENCLUE算法)
基于网格的聚类
基于模型的聚类(模糊聚类、Kohonen神经网络聚类)
基于划分的聚类
基于划分的方法是简单、常用的一种聚类方法，它通过将对象划分为互斥的簇进行聚类， 每个对象属于且仅属于一个簇；划分结果旨在使簇之间的相似性低，簇内部的相似度高；基于划分的方法常用算法有k均值、k‐medoids、k‐prototype等
K-means聚类
k‐均值聚类是基于划分的聚类算法，计算样本点与类簇质心的距离，与类簇质心相近的样本点划分为同一类簇。k‐均值通过样本间的距离来衡量它们之间的相似度，两个样本距离越远，则相似度越低，否则相似度越高
优缺点及拓展：
k‐均值算法原理简单，容易实现，且运行效率比较高（优点）
k‐均值算法聚类结果容易解释，适用于高维数据的聚类（优点）
k‐均值算法采用贪心策略，导致容易局部收敛，在大规模数据集上求解较慢（缺点）
k‐均值算法对离群点和噪声点非常敏感，少量的离群点和噪声点可能对算法求平均值产生极大影响，从而影响聚类结果（缺点）
k‐均值算法中初始聚类中心的选取也对算法结果影响很大，不同的初始中心可能会导致不同的聚类结果。对此，研究人员提出k‐均值++算法，其思想是使初始的聚类中心之间的相互距离尽可能远
K-means++聚类
代码1（鸢尾花的三个特征聚类）
使用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（可以是任何数目）个周围邻居来对未标记的观察进行分类。它也被称为懒惰学习法，因为它涉及最小的模型训练。因此，它不用训练数据对未看见的数据集进行泛化
不得不说，K-means和PAM算法都不可避免有一个弱点，就是计算量上都是随着初始数据量的增大而几何增长的，它适用于小型数据集，那么有什么算法是可以用于大规模的数据集呢？接下来我们将了解CLARA算法以及他衍生出来的算法
CLARA算法
CLARA（Clustering LARge Applications）是应用于大规模数据的聚类，它弥补了k-mediod / PAM算法只能应用于小规模数据的缺陷。
当面对一个大样本量时，CLARA首先通过运用类似于randomforest的随机抽样的方法，每次随机选取样本量中的一小部分进行PAM聚类，然后将剩余样本按照最小中心距离进行归类。在各次重复抽样聚类的结果中，选取误差最小，即中心点代换代价最小的结果作为最终结果。核心是,先对大规模数据进行多次采样,每次采样样本进行k-mediod聚类,然后将多次采样的样本聚类中心进行比较,选出最优的聚类中心.
基于层次的聚类
层次聚类的应用广泛程度仅次于基于划分的聚类，核心思想是通过对数据集按照层次，把数据划分到不同层的簇，从而形成一个树形的聚类结构。层次聚类算法可以揭示数据的分层结构，在树形结构上不同层次进行划分，可以得到不同粒度的聚类结果。按照层次聚类的过程分为自底向上的聚合聚类和自顶向下的分裂聚类。聚合聚类以AGNES、BIRCH、ROCK等算法为代表，分裂聚类以DIANA算法为代表。
自底向上的聚合聚类将每个样本看作一个簇，初始状态下簇的数目等于样本的数目，然后然后根据一定的算法规则，例如把簇间距离最小的相似簇合并成越来越大的簇，直到满足算法的终止条件。
自顶向下的分裂聚类先将所有样本看作属于同一个簇，然后逐渐分裂成更小的簇，直到满足算法终止条件为止。
目前大多数是自底向上的聚合聚类，自顶向下的分裂聚类比较少
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”时则使用均连接方法。
基于密度的聚类
为了解决这一缺陷，基于密度聚类算法利用密度思想，将样本中的高密度区域(即样本点分布稠密的区域)划分为簇，将簇看作是样本空间中被稀疏区域(噪声)分隔开的稠密区域。
这一算法的主要目的是过滤样本空间中的稀疏区域，获取稠密区域作为簇基于密度的聚类算法是根据密度而不是距离来计算样本相似度，所以基于密度的聚类算法能够用于挖掘任意形状的簇，并且能够有效过滤掉噪声样本对于聚类结果的影响。
常见的基于密度的聚类算法有DBSCAN、OPTICS和DENCLUE等。其中，OPTICS 对DBSCAN算法进行了改进，降低了对输入参数的敏感程度。DENCLUE算法综合了基于划分、基于层次的方法
DBSCAN 算法
DBSCAN（Density-Based Spatial Clustering of Applications with Noise，具有噪声的基于密度的聚类方法）是一种基于密度的空间聚类算法。该算法将具有足够密度的区域划分为簇，并在具有噪声的空间数据库中发现任意形状的簇，它将簇定义为密度相连的点的最大集合。
看了赵卫东老师和嵩天老师关于这部分的介绍，我可以说，不是很容易懂，不过，下面这两个网站可以让我们看懂很DBSCAN 算法：首先先看第一个，看了之后再看下面这个配套动画讲解DBSCAN算法的国外网站，你会发现看我下面写的东西原来也不是那么难理解了
下载1：OpenCV-Contrib扩展模块中文版教程
在「小白学视觉」公众号后台回复：扩展模块中文教程，即可下载全网第一份OpenCV扩展模块教程中文版，涵盖扩展模块安装、SFM算法、立体视觉、目标跟踪、生物视觉、超分辨率处理等二十多章内容。
下载2：Python视觉实战项目52讲 在「小白学视觉」公众号后台回复：Python视觉实战项目，即可下载包括图像分割、口罩检测、车道线检测、车辆计数、添加眼线、车牌识别、字符识别、情绪检测、文本内容提取、面部识别等31个视觉实战项目，助力快速学校计算机视觉。
下载3：OpenCV实战项目20讲 在「小白学视觉」公众号后台回复：OpenCV实战项目20讲，即可下载含有20个基于OpenCV实现20个实战项目，实现OpenCV学习进阶。
交流群
欢迎加入公众号读者群一起和同行交流，目前有SLAM、三维视觉、传感器、自动驾驶、计算摄影、检测、分割、识别、医学影像、GAN、算法竞赛等微信群（以后会逐渐细分），请扫描下面微信号加群，备注：”昵称+学校/公司+研究方向“，例如：”张三 + 上海交大 + 视觉SLAM“。请按照格式备注，否则不予通过。添加成功后会根据研究方向邀请进入相关微信群。请勿在群内发送广告，否则会请出群，谢谢理解~