机器学习算法——聚类任务

发布于：2025-03-11 ⋅ 阅读:(19) ⋅ 点赞:(0)

目录
1、K-Means
2、K-medoids
3、K-medians
4、层次聚类
5、DBSCAN
6、OPTICS
7、谱聚类 Spectral Clustering
8、高斯混合模型 GMM
9、模糊C-means FCM
10、Mean Shift
11、BIRCH
12、Affinity Propagation
13、对比总结
14、完整代码

1、K-Means

       目标:将数据点分组到K个簇中，使簇内的点尽可能相似，而簇间的点尽可能不同。
       核心思想:通过迭代优化簇中心的位置，以最小化簇内的平方误差总和。

算法步骤:
       1.初始化：随机选择K个数据点作为初始簇中心。
       2.分配：将每个数据点分配给最近的簇中心。
       3.更新：重新计算每个簇的中心（即簇内所有点的均值）。
       4.迭代：重复步骤2和3直到簇中心不再发生变化或达到预设的迭代次数。

       优点：算法简单高效，广泛应用于各种场景，特别是在需要快速、初步的数据分组时。
       缺点：对初始簇中心的选择敏感，可能会陷入局部最优，且假设簇是凸形的，对于复杂形状的数据可能不适用。

# 1. K-Means
kmeans = KMeans(n_clusters=4, random_state=0) # n_clusters指定簇的数量
kmeans_labels = kmeans.fit_predict(X)

2、K-medoids

       K-medoids聚类算法作为K-Means算法的一个变体，与K-means算法相似，旨在提高聚类的稳健性和对异常值的容忍度。与K-Means不同，K-Medoids选择数据集中的实际点作为簇中心（称为Medoid），而不是计算簇内所有点的均值。这使得K-Medoids在处理具有噪声和离群点的数据集时表现更好。

算法步骤：
       1.初始化：随机选择k个数据点作为初始的簇中心。
       2.分配：将每个数据点分配给最近的簇中心。
       3.更新：计算每个簇的新中心。与K-means不同，这里选择簇内最能代表其他点的数据点作为中心。
       4.重复：重复分配和更新步骤，直到簇中心不再变化或达到预设的迭代次数。

# 2. K-Medoids (需 scikit-learn-extra)
kmedoids = KMedoids(n_clusters=4, random_state=0) # n_clusters指定簇的数量
kmedoids_labels = kmedoids.fit_predict(X)

3、K-medians

       K-medians聚类是一种聚类算法，类似于K-means，但使用中位数来确定簇的中心，而不是平均值。这种方法在处理数据中存在离群值或异常值时比较有用，因为中位数对离群值不敏感。K-medians的步骤与K-means类似，但在每次迭代中，它使用中位数来更新簇的中心。

算法步骤：
       1.初始化：随机选择K个数据点作为初始的簇中心。
       2.分配：将每个数据点分配到距离其最近的簇中心所代表的簇。
       3.更新中心：对于每个簇，使用该簇中所有数据点的中位数来更新簇中心。
       4.重复迭代：重复执行分配和更新中心的步骤，直到簇中心不再发生显著变化或达到预定的迭代次数。

       优点：对于含有离群值的数据集更加鲁棒，因为中位数受到离群值的影响较小。在处理非球形簇时表现较好，相对于K-means更加灵活。

# 3. K-Medians (自定义实现)
# 使用曼哈顿距离的 K-Medians 近似
kmedians = KMeans(n_clusters=4, init='k-medians', algorithm='elkan', random_state=0)
# n_clusters指定簇的数量、init='k-medians'使用中位数初始化中心点、algorithm='elkan'使用Elkan算法加速计算
kmedians_labels = kmedians.fit_predict(pairwise_distances(X, metric='manhattan'))

4、层次聚类Hierarchical methods

       通过构建数据点之间的层次结构来进行聚类。层次聚类不需要预先指定簇的数量，并且结果可以表示为树状图（称为树状图或层次树），提供了数据点之间关系的丰富视图。

类型：
       自下向上：凝聚型，从每个点作为单独的簇开始，逐渐合并最近的簇。
       自上向下：分裂型，从所有数据作为一个簇开始，逐步分裂为更小的簇。

算法步骤（以凝聚型为例）：
       1.开始时，将每个数据点视为一个单独的簇。
       2.找到最相似（距离最近）的两个簇并将它们合并。
       3.重复步骤2，直到所有数据点都合并到一个簇中或达到预定的簇数量。

       距离公式：簇之间的相似性通常用距离来衡量，常用的距离度量有：最短距离，最长距离、平均距离（Average）、中间距离方法。比如最短距离法，将类与类的距离定义为类与类之间样本的最短距离。
在这里插入图片描述

       图中每个点代表一个数据样本。水平线表示簇的合并，其长度代表合并簇之间的距离或不相似度。树状图的垂直轴代表距离或不相似度，可以用来判断簇之间的距离。
       通过树状图，可以观察数据的层次聚类结构，并根据需要选择适当的截断点来确定簇的数量。
       优点：特别适用于那些簇的数量不明确或数据具有自然层次结构的场景。
       缺点：与K-means等算法相比，它不需要预先指定簇的数量，但计算复杂度通常更高。

# 4. 层次聚类
agg = AgglomerativeClustering(n_clusters=4, linkage='ward')
# linkage='ward'使用Ward方法（最小化簇内方差）进行合并
agg_labels = agg.fit_predict(X)

5、DBSCAN

       一种基于密度的聚类算法，通过在数据空间中找到高密度区域，将这些区域作为簇，同时把孤立点（密度低的点）归为噪声。特别适用于具有噪声的数据集和能够发现任意形状簇的情况。它不需要事先指定簇的数量，能有效处理异常点。

基本思想：
       在某个点的邻域半径内，如果有足够多的点（超过一个阈值），就认为这个区域是一个高密度区域，可以扩展成一个簇。
       一个簇通过密度相连的点进行扩展。
       无法归属于任何簇的点被认为是噪声点。

算法步骤：
       1.初始化：从数据集中任意选择一个点p，判断它是否为核心点（即ε邻域内是否包含至少minPts阈值个点）。
       2.扩展簇：如果p是核心点，则开始一个新簇，将p及其邻域中的点加入簇中，并不断对新的核心点的邻域进行扩展。
       3.处理噪声点：如果一个点既不在任何簇中，也不满足成为核心点的条件，则将其标记为噪声点。
       4.重复处理：继续检查所有未访问的点，直到所有点都被访问为止。
在这里插入图片描述

       优点：不需要事先指定簇的数量，可以识别任意形状的簇，并且对噪声数据具有良好的鲁棒性。
       缺点：选择合适的邻域大小和最小点数对于获得好的聚类结果至关重要。

# 5. DBSCAN
dbscan = DBSCAN(eps=0.3, min_samples=10) # eps邻域半径、min_samples核心点的最小样本数
dbscan_labels = dbscan.fit_predict(X)

6、OPTICS

       DBCSAN算法中需要输入两个参数：ϵ和MinPts，选择不同的参数会导致最终聚类的结果千差万别，因此DBCSAN对于输入参数过于敏感。OPTICS算法是从DBSCAN算法中优化而来，解决DBSCAN中参数（邻域半径）依赖问题。与DBSCAN算法类似，但在处理可变密度的数据集时更为有效。其核心思想是通过分析数据点的密度-可达性来识别聚类结构。
       核心思想：基于密度的聚类，但不直接生成聚类，而是生成一个数据点的密度可达性图。这个图可以用来识别数据集中的不同密度区域，从而确定聚类的边界。OPTICS算法通过计算每个数据点的可达距离和核心距离，来构建这个密度可达性图。

       核心点：在给定的半径（邻域半径）内的样本点的数量大于等于给定的最小点数。
       核心距离：对于给定点，其核心距离是使其成为核心对象的最小半径。
       可达距离：是一个对象到一个核心对象的最小距离。

算法步骤：
       1.初始化：为每个数据点计算核心距离，即在给定的邻域半径内，包含至少指定数量的邻点的最小距离。如果数据点的邻域内没有足够的点，那么该点的核心距离被设为无穷大。
       2.构建排序：选择一个未处理的数据点作为起始点，计算其邻域内所有点的可达距离，并将这些点按可达距离排序。然后，从排序列表中选择下一个未处理的点，重复此过程，直到所有点都被处理。
       3.生成聚类：基于密度可达性图，可以使用不同的方法来生成聚类。一种常见的方法是选择一个阈值，将所有可达距离小于该阈值的点视为一个聚类。另一种方法是使用可视化工具，如聚类层次图，来手动识别聚类边界。

# 6. OPTICS
optics = OPTICS(min_samples=10, xi=0.05) # min_samples核心点的最小样本数、xi控制簇的最小密度
optics_labels = optics.fit_predict(X)

7、谱聚类 Spectral Clustering

       一种基于图论的聚类方法（谱指的是矩阵的特征值），适用于发现复杂形状的簇和非球形簇。与传统的聚类算法（如K-means）不同，谱聚类依赖于数据的相似性矩阵，并利用数据的谱（即特征向量）来进行降维，进而在低维空间中应用如K-means的聚类方法。
       主要思想：主要思想是把所有的数据看做空间中的点，这些点之间可以用边连接起来。距离较远的两个点之间的边权重值较低，而距离较近的两个点之间的边权重值较高，通过对所有数据点组成的图进行切图，让切图后不同的子图间边权重和尽可能的低，而子图内的边权重和尽可能的高，从而达到聚类的目的。

算法步骤：
       1.构建相似性矩阵：基于数据点之间的距离或相似度。
       2.计算图的拉普拉斯矩阵：常用的是归一化拉普拉斯矩阵。
       3.计算拉普拉斯矩阵的特征向量和特征值。
       4.基于前k个特征向量的新特征空间，应用传统聚类算法（如K-means）。

       优点：能够发现任意形状的簇，特别适用于传统聚类算法（如K-means）难以处理的数据集。只需要数据之间的相似度矩阵，对于处理稀疏数据的聚类很有效。使用了降维，在处理高维数据聚类时的复杂度比传统聚类算法好。
       缺点：计算复杂度高，特别是在处理大型数据集时。如果最终聚类的维度非常高，则由于降维的幅度不够，谱聚类的运行速度和最后的聚类效果均不好。聚类效果依赖于相似矩阵，不同的相似矩阵得到的最终聚类效果可能很不同。

# 7. 谱聚类
spectral = SpectralClustering(n_clusters=4, affinity='nearest_neighbors', random_state=0)

# affinity='nearest_neighbors'使用最近邻方法构建相似度矩阵。
spectral_labels = spectral.fit_predict(X)

8、高斯混合模型GMM

       一种基于概率模型的聚类算法，用于表示由多个高斯分布（正态分布）组成的复杂数据分布。假设数据集中的每一个样本都由若干个高斯分布中的一个生成，且每个高斯分布对应一个潜在的簇（cluster）。GMM通过估计这些高斯分布的参数（包括均值、协方差矩阵和混合权重）来描述整体数据分布。与K-means等硬聚类算法不同，GMM属于软聚类算法，它为每个数据点提供了属于各个簇的概率。
       算法思想：假设样本数据服从混合高斯分布，根据样本数据集推出混合高斯分布的各个参数，以及各个样本最可能属于哪个高斯分布，这样，GMM的K（K值往往由用户提供）个成分对应于聚类任务中的K个簇，每个样本划到最可能的高斯分布所对应的簇中。如何根据样本数据求出混合高斯分布的各个参数是关键所在

算法步骤：
       1.初始化：随机选择K个高斯分布的参数。
       2.期望步骤（E-step）：根据当前参数，计算每个数据点属于每个簇的概率。
       3.最大化步骤（M-step）：更新每个高斯分布的参数以最大化数据的似然。
       4.迭代：重复E-step和M-step直到收敛。
在这里插入图片描述

# 8. 高斯混合模型 (GMM)
gmm = GaussianMixture(n_components=4, random_state=0)
gmm_labels = gmm.fit(X).predict(X)

9、模糊C-means FCM

       Fuzzy C-Means在K-Means的基础上引入“隶属度”这一概念，让每个数据点同时对多个簇有不同程度的归属。FCM算法允许一个数据点属于多个聚类中心。与传统的K-means聚类算法不同，模糊C-means通过为每个数据点分配一个属于各个聚类中心的隶属度，来表示其属于不同聚类的程度。这种方法是软聚类方法的一种，特别适用于那些不清晰或重叠的数据集。

       硬聚类算法在分类时有一个硬性标准，根据该标准进行划分，分类结果非此即彼。
       软聚类算法更看重隶属度，隶属度在[0,1]之间，每个对象都有属于每个类的隶属度，并且所有隶属度之和为1，即更接近于哪一方，隶属度越高，其相似度越高。

算法步骤：
       1.初始化：选择聚类中心的数量C，并随机初始化每个数据点对每个聚类中心的隶属度。
       2.迭代：在每次迭代中，执行以下步骤：
       3.更新聚类中心，根据数据点对聚类中心的隶属度和数据点的位置。
       4.更新每个数据点对每个聚类中心的隶属度，基于数据点与聚类中心的距离。
       5.停止条件：当聚类中心的变化小于一个阈值或达到预设的迭代次数时，算法停止。

       在算法中维护一个隶属度矩阵U，其元素uij表示第i个数据点对第j个簇的归属度，且对同一个数据点，所有簇的隶属度之和为1。每次交替进行“更新隶属度”与“更新簇中心”，目标函数会不断下降，并在若干步后收敛。

# 9. 模糊C-means (FCM)
fcm = FCM(n_clusters=4)
fcm.fit(X)
fcm_labels = fcm.predict(X)

10、Mean Shift

       Mean Shift（均值漂移）是基于密度的非参数聚类算法，算法思想是假设不同簇类的数据集符合不同的概率密度分布，找到任一样本点密度增大的最快方向（最快方向的含义就是Mean Shift），样本密度高的区域对应于该分布的最大值，这些样本点最终会在局部密度最大值收敛，且收敛到相同局部最大值的点被认为是同一簇类的成员。

       窗口大小（又称带宽）：可以简单理解为一把尺子，决定我们在空间里“看多远”。如果这把尺子太短，可能只看得到自己身边少量的邻居；如果尺子太长，又可能把不相关的远处邻居也算进来。
       核函数：在这个窗口内，通常会让离中心近的点“权重大一些”，离中心远的点“权重小一些”。常用的一种方法是“高斯核”，它让距离越远的点对中心的影响越小。也有其他核函数，不同的核函数本质上都是用来衡量“邻居贡献”大小的。

算法步骤：
       1.选择初始点：把数据集中所有点都作为起始位置，或随机选几个起始点。
       2.划定核窗口：给定一个带宽（也称“窗口大小”），确定离当前点一定距离之内的所有邻居点。
       3.计算“加权平均”：对核窗口内的邻居进行加权平均。加权的方式往往使用距离衰减，也就是说，离中心近的邻居权重越大，离中心远的邻居权重越小。
       4.更新位置：将当前点移动到刚才算出来的“加权平均”位置，并将其作为新的中心点。
       5.持续迭代，直到收敛。

# 10. Mean Shift
ms = MeanShift(bandwidth=0.5) # bandwidth带宽参数，决定搜索窗口大小
ms_labels = ms.fit_predict(X)

11、BIRCH 利用层次方法的平衡迭代规约和聚类

       BIRCH是层次聚类和其他聚类算法结合的一套组合，适用于具有噪声的大规模数据集。
       核心思想：构建一个CF Tree（聚类特征树）的内存中的数据结构来压缩数据，该数据结构以一种方式保存数据，使得聚类可以高效地进行。

       算法原理：利用聚类特征树（CF Tree）来进行聚类，聚类特征树类似于平衡B+树，主要通过计算数据点间的相似度来创建一棵有层次的嵌套聚类树，它试图在不同层次对数据集进行划分，从而形成树形的聚类结构。只要构造好了CF-树，BIRCH算法也就完成了。
在这里插入图片描述

算法步骤：
       1.构建CF Tree：扫描数据库，建立一棵存放于内存的 CF-Tree，它可以被看作数据的多层压缩，试图保留数据的内在聚类结构。如果新数据点可以合并到现有聚类中而不违反树的定义，则进行合并；否则，创建新的叶子节点。
       2.凝聚步骤：可选步骤，用于进一步压缩CF Tree，通过删除距离较近的子聚类并重新平衡树。
       3.全局聚类：使用其他聚类方法（如K-Means）对叶子节点中的聚类特征进行聚类。把稀疏的簇当作离群点删除，而把更稠密的簇合并为更大的簇。

# 11. BIRCH
birch = Birch(n_clusters=4)
birch_labels = birch.fit_predict(X)

12、Affinity Propagation

       Affinity Propagation（近邻传播算法）是一种基于消息传递的自适应聚类算法，突破传统聚类需要预设类别数的限制。其核心创新在于通过数据点间的吸引度（Responsibility）和归属度（Availability）迭代计算，自动识别最优聚类中心。
在这里插入图片描述

       基本思想：将全部数据点都当作潜在的聚类中心(exemplar)；然后数据点两两之间连线构成一个网络(相似度矩阵)，再通过网络中各条边的消息(responsibility和availability)传递计算出各样本的聚类中心。

概念：

Examplar 聚类中心
Similarity S(i,j) 相似度 一般使用负的欧式距离，S(i,j)越大，表示两个点距离越近，相似度也就越高
Preference 点i作为聚类中心的参考度(不能为0)，取值为S相似度对角线的值。此值越大，则为聚类中心的可能性就越大。如果没有被设置，则一般设置为S相似度值的中值。
Responsibility吸引度 点k适合作为数据点i的聚类中心的程度，记为r(i,k)。
Availability归属度 点i选择点k作为其聚类中心的适合程度，记为a(i,k)。
Damping factor阻尼系数 起收敛作用

算法步骤：
       1.计算相似度矩阵，对角线上的值预先是0，用算法（固定参数/相似度矩阵的中位值/最小值等）填充对角线的值。
       2.构造一个全0的归属度矩阵a。
       3.迭代更新：

  • 更新吸引度矩阵r：
    在这里插入图片描述

  • 更新归属度矩阵a：
    在这里插入图片描述
    在这里插入图片描述

  • 使用阻尼系数更新归属度a和吸引度r，以免在更新的过程中出现数值振荡：

在这里插入图片描述

       4.获取聚类中心：
在这里插入图片描述

# 12. Affinity Propagation
ap = AffinityPropagation(damping=0.7) # damping阻尼系数，控制收敛速度
ap_labels = ap.fit_predict(X)

13、对比总结

  • 大规模数据：优先选择K-Means或BIRCH。
  • 复杂形状簇：优先选择DBSCAN、OPTICS或谱聚类。
  • 存在噪声：优先选择K-medoids或DBSCAN。
  • 不确定簇数量：优先选择DBSCAN、谱聚类或Affinity Propagation。
  • 需要层次结构：优先选择层次聚类或BIRCH。
  • 数据点有相似性关系：优先选择谱聚类或Affinity Propagation。

14、完整代码

import numpy as np
from sklearn.datasets import make_blobs
from sklearn.preprocessing import StandardScaler
from sklearn.cluster import (
    KMeans, AgglomerativeClustering, DBSCAN, OPTICS,
    SpectralClustering, AffinityPropagation, MeanShift, Birch
)
from sklearn_extra.cluster import KMedoids
from sklearn.mixture import GaussianMixture
from fcmeans import FCM  # 需安装 fuzzy-c-means 库
from sklearn.metrics import pairwise_distances

from sklearn.metrics import silhouette_score, calinski_harabasz_score, davies_bouldin_score

# 生成模拟数据
X, y = make_blobs(n_samples=300, centers=4, cluster_std=0.6, random_state=0)
X = StandardScaler().fit_transform(X)  # 标准化数据


# 1. K-Means
kmeans = KMeans(n_clusters=4, random_state=0) # n_clusters指定簇的数量
kmeans_labels = kmeans.fit_predict(X)

# 2. K-Medoids (需 scikit-learn-extra)
kmedoids = KMedoids(n_clusters=4, random_state=0) # n_clusters指定簇的数量
kmedoids_labels = kmedoids.fit_predict(X)

# 3. K-Medians (自定义实现)
# 使用曼哈顿距离的 K-Medians 近似
kmedians = KMeans(n_clusters=4, init='k-medians', algorithm='elkan', random_state=0)
# n_clusters指定簇的数量、init='k-medians'使用中位数初始化中心点、algorithm='elkan'使用Elkan算法加速计算
kmedians_labels = kmedians.fit_predict(pairwise_distances(X, metric='manhattan'))

# 4. 层次聚类
agg = AgglomerativeClustering(n_clusters=4, linkage='ward')
# linkage='ward'使用Ward方法（最小化簇内方差）进行合并
agg_labels = agg.fit_predict(X)

# 5. DBSCAN
dbscan = DBSCAN(eps=0.3, min_samples=10) # eps邻域半径、min_samples核心点的最小样本数
dbscan_labels = dbscan.fit_predict(X)

# 6. OPTICS
optics = OPTICS(min_samples=10, xi=0.05) # min_samples核心点的最小样本数、xi控制簇的最小密度
optics_labels = optics.fit_predict(X)

# 7. 谱聚类
spectral = SpectralClustering(n_clusters=4, affinity='nearest_neighbors', random_state=0)
# affinity='nearest_neighbors'使用最近邻方法构建相似度矩阵。
spectral_labels = spectral.fit_predict(X)

# 8. 高斯混合模型 (GMM)
gmm = GaussianMixture(n_components=4, random_state=0)
gmm_labels = gmm.fit(X).predict(X)

# 9. 模糊C-means (FCM)
fcm = FCM(n_clusters=4)
fcm.fit(X)
fcm_labels = fcm.predict(X)

# 10. Mean Shift
ms = MeanShift(bandwidth=0.5) # bandwidth带宽参数，决定搜索窗口大小
ms_labels = ms.fit_predict(X)

# 11. BIRCH
birch = Birch(n_clusters=4)
birch_labels = birch.fit_predict(X)

# 12. Affinity Propagation
ap = AffinityPropagation(damping=0.7) # damping阻尼系数，控制收敛速度
ap_labels = ap.fit_predict(X)

# 定义评估函数
def evaluate_clustering(X, labels, algorithm_name):
    if len(np.unique(labels)) > 1:  # 至少需要两个簇才能计算
        silhouette = silhouette_score(X, labels)
        calinski = calinski_harabasz_score(X, labels)
        davies = davies_bouldin_score(X, labels)
        print(f"{algorithm_name} 评估结果:")
        print(f"  - 轮廓系数: {silhouette:.3f}")
        print(f"  - Calinski-Harabasz 指数: {calinski:.3f}")
        print(f"  - Davies-Bouldin 指数: {davies:.3f}")
    else:
        print(f"{algorithm_name} 无法评估（仅一个簇）。")

# 评估所有聚类结果
evaluate_clustering(X, kmeans_labels, "K-Means")
evaluate_clustering(X, kmedoids_labels, "K-Medoids")
evaluate_clustering(X, kmedians_labels, "K-Medians")
evaluate_clustering(X, agg_labels, "层次聚类")
evaluate_clustering(X, dbscan_labels, "DBSCAN")
evaluate_clustering(X, optics_labels, "OPTICS")
evaluate_clustering(X, spectral_labels, "谱聚类")
evaluate_clustering(X, gmm_labels, "高斯混合模型")
evaluate_clustering(X, fcm_labels, "模糊C-means")
evaluate_clustering(X, ms_labels, "Mean Shift")
evaluate_clustering(X, birch_labels, "BIRCH")
evaluate_clustering(X, ap_labels, "Affinity Propagation")

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布