机器学习知识总结 —— 17.什么是聚类

什么是聚类

在前面的章节介绍了机器学习中的第一个分类算法SVM除此以外如果你有关注过机器学习或者数据挖掘方面的知识那么应该也听说过聚类。

作为机器学习中的一种重要算法聚类也是一种无监督学习方法它的目的是将数据分成若干组使得每组数据之间相似度尽量大不同组之间相似度尽量小。

聚类与SVM算法的区别是什么

由于同样是分类算法所以我们不得不好奇聚类和SVM的具体区别是什么以及面对怎样的问题时我们应该使用SVM什么时候可以考虑使用聚类算法。

一个比较粗浅的区别大致是这样的

聚类是一种 无监督学习 算法它可以将数据自动分组而不需要事先知道数据的标签。它通常用于对数据进行探索性分析发现数据中的隐藏模式。

SVM 是一种 监督学习算法它需要事先知道数据的标签。它的目的是找到一个超平面使得不同类别的数据尽可能地分开并且同一类别的数据尽可能地靠近。

当数据中存在明显的类别划分时我们应该优先考虑 SVM 算法。而当数据中存在隐藏的类别划分时我们应该优先考虑聚类。总之聚类是对数据进行探索性分析的工具SVM是在已知类别的情况下建立分类模型的工具。

聚类算法的重要知识点

在这一章节里我们将回顾一下关于聚类的重要知识点。我们要知道常见的聚类算法有哪些比如

K-means、层次聚类、密度聚类、基于模型的聚类等。

对于数据的分类依据或者说标准有哪些比如

距离度量、轮廓系数、Calinski-Harabasz指数等。

以及由于该算法是无监督学习所以为了得到一个较为理想的结果我们可能要事先以及事后做一些处理和评判比如

如何选择聚类的数量、如何评估聚类的质量、如何处理离群值等。

以及最后的可视化是采用二维图像还是三维数据如何显示给目标用户或人群。

现在我们来依次说明常见的聚类算法

常见聚类算法

K-Means聚类

K-Means是最常用的聚类算法之一它的基本思想是对于给定的数据集选择K个初始质心然后将所有数据分配到距离它最近的质心所属的簇。然后重新计算每个簇的质心重复这个过程直到簇的划分不再发生变化。

K-Means的目标函数为

$$J(c_1,c_2,\dots ,c_k)=\sum _{i=1}^k\sum _{x_j\in c_i}||x_j-{\mu }_i|{|}^2$$

其中 $c_i$ 是第 i 个簇${\mu }_i$ 是第 i 个簇的质心$x_j$ 是第 j 个样本。

K-Means聚类算法的工作原理是将数据集划分为K个簇。

算法的基本步骤如下

1. 随机选取K个初始质心也叫中心点。

2. 对于每个数据样本计算它与每个质心的距离并将其分配到距离最近的质心所属的簇。

3. 重新计算每个簇的质心。重复步骤2和3直到簇的划分不再发生变化。其中K是用户输入的聚类数量, 收敛条件可以是最大迭代次数, 或者簇的划分不再发生变化。

初始化质心可以使用随机选取K个点, 或者手动指定。距离度量可以使用欧几里得距离, 曼哈顿距离等。分配样本到簇的过程中, 可以使用 for 循环来遍历每个样本, 找出距离它最近的质心。

重新计算质心可以使用平均值来计算新的质心坐标。

层次聚类 (Hierarchical Clustering)

层次聚类算法通过不断合并或分裂簇来划分数据集最后形成一棵树状的层次结构。常用的层次聚类算法有凝聚层次聚类和分裂层次聚类。

凝聚层次聚类算法从单个样本开始不断将距离最近的两个簇合并直到形成最终的簇。而分裂层次聚类算法则是从所有样本构成的一个大簇开始不断将簇分裂直到形成最终的簇。

这种算法可以通过两种方式来实现

1. 分层聚类agglomerative方法从每一个数据点开始不断地将最相近的簇合并直到所有点都被分到一个簇里。

2. 递归分裂聚类divisive方法从所有数据点开始不断地将数据点分裂成越来越小的簇直到每一个簇只包含一个数据点。

层次聚类的优点是可以很直观地展示数据聚类的过程和结果并且能够处理大量数据。缺点是由于簇之间距离的定义可能不同导致不同的算法结果不同且计算量较大。

需要注意的是层次聚类会对数据点的顺序敏感并且不能处理不连续的簇。

DBSCAN聚类

DBSCAN (Density-Based Spatial Clustering of Applications with Noise) 是一种基于密度的聚类算法。它可以将数据点分为若干个簇并且不需要事先知道簇的个数。

主要思想是如果一个数据点周围有很多其他数据点那么它们应该属于同一个簇。而如果一个数据点周围没有很多其他数据点那么它们应该属于不同的簇。

DBSCAN 算法主要有两个参数半径 $ϵ$ 和最小样本数量 $minPts$。半径 $ϵ$ 指定了一个数据点周围的范围最小样本数量 $minPts$ 指定了在这个范围内最少需要有多少个数据点才能认为这个数据点是一个核心点。

DBSCAN 算法的流程如下:

1. 从每个数据点开始找到所有在半径 $ϵ$ 内的数据点如果找到的数据点的数量大于 $minPts$则这个数据点是一个核心点。

2. 对于每个核心点找到它周围所有的核心点并将它们划分到同一个簇中。

3. 对于每个非核心点如果它距离至少一个核心点不超过 $ϵ$那么它就划分到对应的簇中。

DBSCAN 的优点是能够发现任意形状的簇不需要事先知道簇的个数并且对于噪声数据也能很好的处理。缺点是参数 $ϵ$ 和 $minPts$ 比较难调整并且对于高维数据效果不佳。需要注意的是 DBSCAN 不能处理不连续的簇对于这种情况需要使用其他聚类算法如基于密度的聚类算法 HDBSCAN.

基于密度的HDBSCAN

HDBSCAN (Hierarchical Density-Based Spatial Clustering of Applications with Noise) 是一种基于密度的层次聚类算法是对DBSCAN算法的扩展。

在DBSCAN算法中聚类的结果是以密度为基础的但是它需要手动调整参数而且对于不同密度的簇难以处理。而HDBSCAN算法则通过计算簇的密度来确定簇的边界并且使用层次聚类方法来组合不同密度的簇。

基本算法流程如下

1. 从数据点中选取密度最大的点作为核心点。

2. 对于核心点所在的密度相连簇进行聚类得到若干个子簇。

3. 对于每个子簇判断是否符合簇的条件即密度是否足够大如果符合条件则继续聚类否则当前簇结束。

HDBSCAN算法的优点是不需要手动调整参数能够处理不同密度的簇并且能够识别噪声点。