百科问答小站 logo   百科问答小站
问题

用于数据挖掘的聚类算法有哪些，各有何优势？

回答
在数据挖掘的广阔天地里，聚类算法扮演着至关重要的角色，它就像一位勤勉的分析师，能够从杂乱无章的数据中找出隐藏的模式和结构，将相似的数据点归为一类。掌握这些算法，我们就能更深入地理解数据背后的故事。

下面我将详细介绍几种常用的聚类算法，并探讨它们各自的优势，力求用最清晰易懂的方式呈现给大家。

1. KMeans 聚类 (KMeans Clustering)

核心思想： KMeans 是一种迭代的划分聚类方法。它将数据集划分为 K 个预设的簇，使得每个数据点都属于离其最近的簇中心（质心）。

工作流程：

1. 初始化质心： 随机选择 K 个数据点作为初始的簇中心，或者通过其他方法（如 KMeans++）选择更优的初始质心。
2. 分配数据点： 计算每个数据点到所有簇中心的距离，并将数据点分配给距离最近的那个簇中心。
3. 更新质心： 对于每个簇，重新计算其所有数据点的平均值作为新的簇中心。
4. 重复迭代： 重复步骤 2 和 3，直到簇的分配不再发生变化，或者达到预设的最大迭代次数。

优势：

简单易懂，易于实现： KMeans 的算法原理非常直观，代码实现相对容易。
计算效率高： 在处理大规模数据集时，KMeans 的计算速度通常比其他一些算法快，尤其是在簇的数量 K 较小的情况下。它的时间复杂度大致为 O(nkdi)，其中 n 是数据点数量，k 是簇数量，d 是特征维度，i 是迭代次数。
结果可解释性强： 每个簇都有一个明确的中心点，这使得我们可以很容易地理解每个簇的代表性特征。
适用于凸形簇： 当数据中的簇是凸形、大小相似且密度均匀时，KMeans 的表现通常很好。

局限性：

需要预设簇数量 K： 提前知道数据中有多少个簇是一个挑战，需要通过一些方法（如肘部法则、轮廓系数等）来确定最优的 K 值。
对异常值敏感： 异常值会显著影响簇中心的计算，从而导致聚类结果的偏差。
容易陷入局部最优： 初始质心的选择对最终结果有很大影响，不同的初始值可能导致不同的聚类结果。
不适用于非球形或不规则形状的簇： KMeans 倾向于生成球形的簇，对于包含复杂形状（如香蕉状、环状）的数据集效果不佳。
不同尺度的特征可能影响结果： 如果特征的尺度差异很大，需要进行特征缩放。

2. DBSCAN 聚类 (DensityBased Spatial Clustering of Applications with Noise)

核心思想： DBSCAN 是一种基于密度的聚类算法。它将数据点密度较高的区域视为簇，将密度较低的区域视为噪声点。它不需要预先指定簇的数量，而是通过两个参数来定义“密度”：`epsilon` (ε) 和 `min_samples`。

工作流程：

1. 定义核心点 (Core Point)： 如果一个数据点在以它为圆心、半径为 ε 的圆域内，至少包含 `min_samples` 个数据点（包括它本身），那么它就被称为核心点。
2. 定义边界点 (Border Point)： 如果一个数据点不在任何核心点的 ε 邻域内，但它在某个核心点的 ε 邻域内，那么它就是边界点。
3. 定义噪声点 (Noise Point)： 既不是核心点也不是边界点的数据点被视为噪声点。
4. 形成簇： 从一个未访问的核心点开始，将其标记为一个新簇。然后，找到该核心点所有可达的（ε 邻域内的核心点或边界点）数据点，将它们也加入到这个簇中。这个过程会递归地进行，直到无法再找到可达的数据点为止。
5. 重复过程： 继续寻找未访问的核心点，重复上述过程，直到所有数据点都被访问。

优势：

无需预设簇数量： 这是 DBSCAN 最大的优点之一，它能够自动发现簇的数量。
能发现任意形状的簇： DBSCAN 对簇的形状没有限制，能够有效地发现任意形状的簇。
对噪声不敏感： 它能够识别并隔离噪声点，使得聚类结果更加鲁棒。
概念直观： 基于密度的概念容易理解，对于数据密集区域的划分有较强的直观性。

局限性：

参数选择对结果影响较大： ε 和 `min_samples` 的选择直接影响聚类结果，找到最优参数需要一些经验和尝试。
处理密度不均匀的数据集困难： 对于密度差异较大的数据集，DBSCAN 可能难以找到一个统一的参数集来正确聚类。
在高维空间中表现不佳： 在高维空间中，距离的概念变得模糊（“维度灾难”），ε 邻域可能会包含大量数据点，导致聚类效果下降。
计算复杂度较高： 对于大规模数据集，尤其是需要频繁计算邻域时，DBSCAN 的计算复杂度可能高于 KMeans。

3. Hierarchical Clustering (层次聚类)

核心思想： 层次聚类不预设簇的数量，而是构建一个簇的层次结构。这种结构通常以树状图（Dendrogram）的形式表示。层次聚类可以分为两种主要类型：

凝聚型 (Agglomerative)： 自底向上。开始时，每个数据点都是一个独立的簇。然后，逐步将最相似的两个簇合并，直到所有数据点都属于同一个簇。
分裂型 (Divisive)： 自顶向下。开始时，所有数据点都属于一个大簇。然后，逐步将簇分裂成更小的簇，直到每个数据点都成为一个独立的簇。

工作流程（以凝聚型为例）：

1. 初始化： 将每个数据点看作一个独立的簇。
2. 迭代合并： 计算所有簇对之间的距离（可以使用不同的链接准则，如单链接、全链接、平均链接等）。选择距离最近的两个簇进行合并。
3. 重复： 重复步骤 2，直到所有数据点形成一个单独的簇。

优势：

无需预设簇数量： 通过观察树状图，可以根据需要选择合适的聚类层级，从而确定簇的数量。
提供簇的层次结构： 树状图提供了数据的层级关系，有助于理解数据之间的嵌套关系。
适用于不同形状的簇（取决于链接准则）： 例如，单链接（Minimum Linkage）可以发现非球形或长条形的簇。
概念清晰，结果可交互性强： 可以通过剪切树状图的不同高度来获得不同数量的簇。

局限性：

计算复杂度高： 凝聚型层次聚类的基本操作是计算簇对的距离并合并，时间复杂度通常为 O(n^2 log n) 或 O(n^3)，对大规模数据集不太友好。
一旦合并，无法撤销： 凝聚型层次聚类一旦合并了两个簇，就不能再将它们分开了，这可能导致不理想的聚类结果。
对噪声敏感（尤其是单链接）： 单链接对噪声敏感，容易将两个不相关的点连接起来。
难以选择合适的链接准则和距离度量： 不同的链接准则和距离度量会产生不同的结果，需要根据具体数据和问题进行选择。

4. KMedoids 聚类 (KMedoids Clustering)

核心思想： KMedoids 与 KMeans 非常相似，但它不是选择簇的均值作为簇中心，而是选择数据集中实际存在的点作为簇中心（称为“中心点”或“Medoid”）。

工作流程：

1. 初始化： 随机选择 K 个数据点作为初始的中心点。
2. 分配数据点： 计算每个数据点到所有中心点的距离，并将数据点分配给距离最近的那个中心点。
3. 更新中心点： 对于每个簇，计算该簇内所有点到该簇所有其他点的“代价”之和（即到其他点的总距离）。然后，选择代价最小的点作为新的中心点。
4. 重复迭代： 重复步骤 2 和 3，直到簇的分配不再发生变化。

优势：

对异常值更鲁棒： 由于中心点必须是实际数据点，KMedoids 不会像 KMeans 那样被异常值拉扯得太远。
结果可解释性强： 簇中心是实际存在的数据点，更易于理解其代表性。
适用于各种形状的簇： 和 KMeans 一样，它也适合凸形簇，但由于其鲁棒性，在有异常值的情况下可能表现更好。

局限性：

计算复杂度比 KMeans 高： 寻找最优中心点的过程需要计算所有数据点到所有数据点的距离，以及每个簇内数据点到簇内其他点的总距离，效率不如 KMeans。
同样需要预设簇数量 K： 与 KMeans 相同，需要提前指定簇的数量。
对初始中心点敏感： 同样存在陷入局部最优的问题。

5. Mean Shift 聚类

核心思想： Mean Shift 是一种无参数的聚类算法，它基于“密度梯度”的思想。它会迭代地将数据点移动到密度更高的区域，直到收敛于一个局部密度最大值点，这些局部密度最大值点最终形成簇的中心。

工作流程：

1. 初始化： 随机选择一个数据点作为起点。
2. 计算均值偏移向量： 在以当前点为中心、半径为带宽 (bandwidth) 的窗口内，计算所有数据点的均值。然后，用这个均值减去当前点，得到均值偏移向量。
3. 更新位置： 将当前点沿着均值偏移向量的方向移动指定的步长（通常是窗口半径本身，或者一个较小的比例）。
4. 重复迭代： 重复步骤 2 和 3，直到数据点不再发生显著移动（收敛）。
5. 形成簇： 所有收敛到同一个局部密度最大值点的数据点被归为同一个簇。

优势：

无需预设簇数量： 能够自动发现簇的数量。
能够发现任意形状的簇： 和 DBSCAN 一样，它不限制簇的形状。
对异常值不敏感： 由于其基于密度的思想，异常值对结果的影响较小。
带宽参数的含义相对直观： 带宽可以看作是簇的“粒度”或“平滑度”。

局限性：

计算复杂度高： 尤其是在数据集较大且窗口半径较大时，计算量非常大。
带宽参数的选择至关重要： 带宽的选择直接影响聚类结果，需要仔细调整。
在高维空间中表现不佳： 和 DBSCAN 一样，在高维空间中距离的概念模糊，效果会打折扣。
结果可能包含重叠的簇： 如果两个高密度区域靠得很近，可能会被视为同一个簇，或者产生多个非常接近的中心点。

总结

| 算法名称 | 是否需要预设 K | 能否发现任意形状 | 对噪声敏感度 | 算法核心思想 | 主要优势 | 主要劣势 |
| : | : | : | : | : | : | : |
| KMeans | 是 | 否（球形） | 高 | 基于均值（质心）的划分 | 简单易懂，效率高，适用于球形簇 | 需要预设 K，对异常值和非球形簇敏感，易陷入局部最优 |
| DBSCAN | 否 | 是 | 低 | 基于密度（ε邻域和最小点数） | 无需预设 K，能发现任意形状，对噪声不敏感 | 参数选择难，处理密度不均和高维数据困难，计算复杂度高 |
| Hierarchical | 否 | 是（取决于链接） | 中（单链接高） | 构建簇的层次结构 | 无需预设 K，提供层次结构，结果可交互 | 计算复杂度高，一旦合并不可撤销，对参数选择敏感 |
| KMedoids | 是 | 否（球形） | 低 | 基于实际数据点（中心点）的划分 | 对异常值鲁棒性强，结果可解释性强 | 计算复杂度高于 KMeans，需要预设 K，对初始中心点敏感 |
| Mean Shift | 否 | 是 | 低 | 基于密度梯度 | 无需预设 K，能发现任意形状，对噪声不敏感 | 计算复杂度高，带宽参数选择难，在高维数据上表现不佳 |

选择哪种聚类算法，最终取决于你的数据特性、分析目标以及对算法优劣势的权衡。理解它们的内在机制，才能更有效地将它们应用于数据挖掘的实践中，从中挖掘出有价值的洞察。

网友意见

user avatar

如果真要做全面介绍的话，有可能是一部专著的篇幅。即使是做综述性的介绍，一篇三五十页的论文也可以写成了。所以我一直想怎么能从头到尾把这个问题logically串连起来。正好这段时间我在修改我做的交易策略里面关于聚类的部分，趁脑子热的时候顺手写下。

就我的理解而言，如果想全面的了解聚类算法并对其进行区别和比较的话，最好能把聚类的具体算法放到整个聚类分析的语境中理解。那我接下来主要谈谈我的理解，就不搬弄教科书里的概念了。

聚类分析其实思路很简单，粗略来看就是以下2个（或3个）环节。

1、相似性衡量（similarity measurement）

相似性衡量又可以细分为直接法和间接法（答主自己取的名字，求轻拍）：直接法是直接求取input data的相似性，间接法是求取data中提取出的features的相似性。但无论是求data还是feature的相似性，方法都是这么几种：

  • 距离。距离主要就是指Minkovski距离。这个名字虽然听起来陌生，但其算法就是Lp norm的算法，如果是L1 norm，那就是绝对值/曼哈顿距离（Manhattan distance）；如果是L2 norm，那就是著名的欧式距离（Euclidean distance）了，也是应用最广泛的；如果，supremum距离，好像也有叫切比雪夫距离的，但就很少有人用了。另外，还有Mahalanobis距离，目前来看主要应用于Gaussian Mixture Model（GMM），还有Lance&Williams距离等等，但几乎没见过求距离的时候会专门用这个的。
  • 相似系数。主要有夹角余弦和相关系数。相关系数的应用也非常广泛，其主要优势是它不受原线性变换的影响，而且可以轻松地转换为距离，但其运算速度要比距离法慢得多，当维数很高的时候。
  • 核函数K(x,y)。定义在上的二元函数，本质上也是反映x和y的距离。核函数的功能就是把数据从低维空间投影（project）到高维空间去。
  • DTW（dynamic time warping）。之所以把DTW单独拿出来，是因为它是一种非常特殊的距离算法，它可以计算两个不同长度的向量的距离，也可以对两对向量中不同时间段内的数据做匹配，比如你发现2015年上半年的上证指数走势和SP5002012年的走势非常相似。DTW主要用在时间序列的部分场合里，在这里就不做具体分析了。

2、聚类算法（clustering algorithm）

  • Hierarchical methods：该主要有两种路径：agglomerative和divisive，也可以理解为自下而上法（bottom-up）和自上而下法（top-down）。自下而上法就是一开始每个个体（object）都是一个类，然后根据linkage寻找同类，最后形成一个“类”。自上而下法就是反过来，一开始所有个体都属于一个“类”，然后根据linkage排除异己，最后每个个体都成为一个“类”。这两种路径本质上没有孰优孰劣之分，只是在实际应用的时候要根据数据特点以及你想要的“类”的个数，来考虑是自上而下更快还是自下而上更快。至于根据Linkage判断“类”的方法就是楼上所提到的最短距离法、最长距离法、中间距离法、类平均法等等（其中类平均法往往被认为是最常用也最好用的方法，一方面因为其良好的单调性，另一方面因为其空间扩张/浓缩的程度适中）。Hierarchical methods中比较新的算法有BIRCH（Balanced Iterative Reducing and Clustering Using Hierarchies）主要是在数据体量很大的时候使用，而且数据类型是numerical；ROCK（A Hierarchical Clustering Algorithm for Categorical Attributes）主要用在categorical的数据类型上；Chameleon（A Hierarchical Clustering Algorithm Using Dynamic Modeling）里用到的linkage是kNN（k-nearest-neighbor）算法，并以此构建一个graph，Chameleon的聚类效果被认为非常强大，比BIRCH好用，但运算复杂的发很高，O(n^2)。看个Chameleon的聚类效果图，其中一个颜色代表一类，可以看出来是可以处理非常复杂的形状的。
  • Partition-based methods：其原理简单来说就是，想象你有一堆散点需要聚类，想要的聚类效果就是“类内的点都足够近，类间的点都足够远”。首先你要确定这堆散点最后聚成几类，然后挑选几个点作为初始中心点，再然后依据预先定好的启发式算法（heuristic algorithms）给数据点做迭代重置（iterative relocation），直到最后到达“类内的点都足够近，类间的点都足够远”的目标效果。也正是根据所谓的“启发式算法”，形成了k-means算法及其变体包括k-medoids、k-modes、k-medians、kernel k-means等算法。k-means对初始值的设置很敏感，所以有了k-means++、intelligent k-means、genetic k-means；k-means对噪声和离群值非常敏感，所以有了k-medoids和k-medians；k-means只用于numerical类型数据，不适用于categorical类型数据，所以k-modes；k-means不能解决非凸（non-convex）数据，所以有了kernel k-means。另外，很多教程都告诉我们Partition-based methods聚类多适用于中等体量的数据集，但我们也不知道“中等”到底有多“中”，所以不妨理解成，数据集越大，越有可能陷入局部最小。下图显示的就是面对非凸，k-means和kernel k-means的不同效果。

  • Density-based methods：上面这张图你也看到了，k-means解决不了这种不规则形状的聚类。于是就有了Density-based methods来系统解决这个问题。该方法同时也对噪声数据的处理比较好。其原理简单说画圈儿，其中要定义两个参数，一个是圈儿的最大半径，一个是一个圈儿里最少应容纳几个点。最后在一个圈里的，就是一个类。DBSCAN（Density-Based Spatial Clustering of Applications with Noise）就是其中的典型，可惜参数设置也是个问题，对这两个参数的设置非常敏感。DBSCAN的扩展叫OPTICS（Ordering Points To Identify Clustering Structure）通过优先对高密度（high density）进行搜索，然后根据高密度的特点设置参数，改善了DBSCAN的不足。下图就是表现了DBSCAN对参数设置的敏感，你们可以感受下。

  • Grid-based methods：这类方法的原理就是将数据空间划分为网格单元，将数据对象集映射到网格单元中，并计算每个单元的密度。根据预设的阈值判断每个网格单元是否为高密度单元，由邻近的稠密单元组形成”类“。该类方法的优点就是执行效率高，因为其速度与数据对象的个数无关，而只依赖于数据空间中每个维上单元的个数。但缺点也是不少，比如对参数敏感、无法处理不规则分布的数据、维数灾难等。STING（STatistical INformation Grid）和CLIQUE（CLustering In QUEst）是该类方法中的代表性算法。下图是CLIQUE的一个例子：

  • Model-based methods：这一类方法主要是指基于概率模型的方法和基于神经网络模型的方法，尤其以基于概率模型的方法居多。这里的概率模型主要指概率生成模型（generative Model），同一”类“的数据属于同一种概率分布。这中方法的优点就是对”类“的划分不那么”坚硬“，而是以概率形式表现，每一类的特征也可以用参数来表达；但缺点就是执行效率不高，特别是分布数量很多并且数据量很少的时候。其中最典型、也最常用的方法就是高斯混合模型（GMM，Gaussian Mixture Models）。基于神经网络模型的方法主要就是指SOM（Self Organized Maps）了，也是我所知的唯一一个非监督学习的神经网络了。下图表现的就是GMM的一个demo，里面用到EM算法来做最大似然估计。



3、数据简化（data reduction），这个环节optional。其实第二部分提到的有些算法就是对数据做了简化，才得以具备处理大规模数据的能力，比如BIRCH。但其实你可以任意组合，所以理论上把数据简化的方法和上面提到的十几种聚类算法结合使用，可以有上百个算法了。

  • 变换（Data Transformation）：离散傅里叶变换（Discrete Fourier Transformation）可以提取数据的频域（frequency domain）信息，离散小波变换（Discrete Wavelet Transformation）除了频域之外，还可以提取到时域（temporal domain）信息。
  • 降维（Dimensionality Reduction）：在降维的方法中，PCA（Principle Component Analysis）和SVD（Singular Value Decomposition）作为线性方法，受到最广泛的应用。还有像MDS（Multi-Dimensional Scaling）什么的，不过只是作为PCA的一个扩展，给我的感觉是中看不中用。这几个方法局限肯定是无法处理非线性特征明显的数据。处理非线性降维的算法主要是流形学习（Manifold Learning），这又是一大块内容，里面集中常见的算法包括ISOMAP、LLE（Locally Linear Embedding）、MVU（Maximum variance unfolding）、Laplacian eigenmaps、Hessian eigenmaps、Kernel PCA、Probabilistic PCA等等。流形学习还是挺有趣的，而且一直在发展。关于降维在聚类中的应用，最著名的应该就是 @宋超 在评论里提到的谱聚类（Spectral Clustering），就是先用Laplacian eigenmaps对数据降维（简单地说，就是先将数据转换成邻接矩阵或相似性矩阵，再转换成Laplacian矩阵，再对Laplacian矩阵进行特征分解，把最小的K个特征向量排列在一起），然后再使用k-means完成聚类。谱聚类是个很好的方法，效果通常比k-means好，计算复杂度还低，这都要归功于降维的作用。
  • 抽样（Sampling）：最常用的就是随机抽样（Random Sampling）咯，如果你的数据集特别大，随机抽样就越能显示出它的低复杂性所带来的好处。比如CLARA（Clustering LARge Applications）就是因为k-medoids应对不了大规模的数据集，所以采用sampling的方法。至于更加fancy的抽样方法我还真不了解，我就不在这里好为人师而误人子弟了。

PS：以上所有图示均来自于UIUC的韩家炜教授的slides，版权归韩家炜教授所有；

PSS：如果对某个算法感兴趣，还请直接读论文、读教材、写代码；

PSSS：以上三个环节，可以各选择其中一个方法加以组合，放心地试验，放心地玩吧，就像把不同的溶液都往一个烧瓶里倒，这里很安全，不会爆炸的。

类似的话题

本站所有内容均为互联网搜索引擎提供的公开搜索信息，本站不存储任何数据与内容，任何内容与数据均与本站无关，如有需要请联系相关搜索引擎包括但不限于百度，google,bing,sogou 等

© 2025 tinynews.org All Rights Reserved. 百科问答小站 版权所有

服务条款
联系我们
关于我们
隐私政策
友情链接
知乎
百度问答
搜狐
新浪