注册    登录
关注
Py学习  »  机器学习算法

【机器学习】8个常见聚类算法解释！

机器学习初学者 • 2 年前 • 277 次点击  

公众号：尤而小屋
作者：Peter
编辑：Peter

本文主要介绍8个常见聚类算法和基本原理：

  • K-Means聚类
  • 层次聚类
  • DBSCAN聚类
  • 均值漂移聚类
  • 谱聚类
  • 模糊聚类Fuzzy Clustering
  • 密度峰值聚类Density Peaks Clustering
  • 结合GMM和EM的聚类

一、K-Means聚类

原理

K-Means聚类算法的原理如下：

  1. 初始化：随机选择k个中心点，作为初始的聚类中心。
  2. 计算距离：计算每个样本到k个中心点的距离，将各样本划分到距离最近的中心点所在的簇。
  3. 重新计算中心：为各簇所有点的均值，重新计算各簇的中心。
  4. 迭代：不断迭代2、3步骤，直到各簇不再发生变化或者达到预设的迭代次数。

优缺点

1、K-Means聚类算法的优点包括：

  • 原理简单，实现容易，收敛速度快。
  • 聚类效果较优，能够将簇紧凑，使得簇内相似度高。
  • 算法的可解释度较强。
  • 只需调整k值，即可得到不同数量的聚类结果。

2、K-Means聚类算法也存在以下缺点：

  • K值的选取不好把握，通常需要通过实验和可视化方法来确定合适的K值。
  • 对于初值的选择敏感，不同的初值会导致不同的聚类结果。为了克服这个问题，可以采用k-means++算法来选择初始中心点。
  • 对于非凸形状的簇、大小和密度不同的簇，K-Means算法容易受到离群点的影响，导致聚类效果不佳。这时可以考虑使用基于密度的聚类算法，如DBSCAN算法。
  • 只能收敛到局部最小值，而不能找到全局最小值。因此，在应用K-Means算法时，需要多次运行，并选择效果最好的结果。

代码

import numpy as np  
import matplotlib.pyplot as plt  
  
def kmeans(X, k, max_iterations=100):  
    """  
    K-Means聚类算法实现  
    :param X: 数据集  
    :param k: 聚类数  
    :param max_iterations: 最大迭代次数  
    :return: 聚类结果  
    """  
    centroids = X[np.random.choice(X.shape[0], k, replace=False)]  # 随机初始化聚类中心  
    for i in range(max_iterations):  
        # 计算每个样本到聚类中心的距离  
        distances = np.sqrt(((X - centroids[:, np.newaxis])**2).sum(axis=2))  
        # 根据距离将样本划分到距离最近的聚类中心所在的簇  
        labels = np.argmin(distances, axis=0)  
        # 重新计算各簇的中心  
        new_centroids = np.array([X[labels == j].mean(axis=0) for j in range(k)])  



    
        # 判断是否收敛  
        if np.allclose(centroids, new_centroids):  
            break  
        centroids = new_centroids  
    return labels, centroids  
  
# 测试  
X = np.random.rand(100, 2)  
labels, centroids = kmeans(X, k=4)  
plt.scatter(X[:, 0], X[:, 1], c=labels)  
plt.scatter(centroids[:, 0], centroids[:, 1], marker='x', s=200, linewidths=3, color='r')  
plt.show()

二、层次聚类

原理

层级聚类（Hierarchical Clustering）是一种基于树形结构的聚类算法，通过将数据点逐步合并成簇，最终形成一棵树形的聚类结构。层级聚类算法可以分为两种：自底向上聚类（Agglomerative Clustering）和自上向下聚类（Divisive Clustering）

1、自底向上聚类的原理：

  • 将每个数据点看作是一个单独的簇
  • 计算每对簇之间的距离，选择距离最近的两个簇
  • 将距离最近的两个簇合并成一个新的簇
  • 重复步骤2和3，直到所有数据点都被合并成一个簇

2、自上向下聚类的原理：

  • 将所有数据点看作是一个单独的簇
  • 将簇划分为两个子簇，使得子簇内部的相似度最高
  • 重复步骤2，直到每个子簇只包含一个数据点

优缺点

1、层级聚类的优点包括：

  • 可以生成一个树形结构的聚类结果，可以用于可视化数据集的聚类情况。
  • 可以在不同层次的聚类结果中进行选择，根据需要选择适当的聚类结果。
  • 对于数据集的大小和维度具有一定的适应性，可以处理不同规模和复杂度的数据集。

2、层级聚类也存在以下缺点：

  • 聚类结果的可解释性较弱，难以解释数据点之间的相似度。
  • 算法的收敛速度较慢，特别是对于高维数据集来说，可能需要大量的计算时间。
  • 算法的性能受到距离计算的影响较大，不同的距离计算方法可能会对聚类结果产生不同的影响。
  • 对于数据集的初始状态敏感，不同的初始状态可能会导致不同的聚类结果。

代码

import numpy as np  
from scipy.cluster.hierarchy import linkage, dendrogram  
  
# 生成数据集  
X = np.random.rand(10, 2)  
  
# 计算聚类距离矩阵  
Z = linkage(X, method='ward')  
  
# 绘制聚类树状图  
dendrogram(Z)  
  
# 显示图形  
plt.show()

三、DBSCAN聚类

原理

DBSCAN（Density-Based Spatial Clustering of Applications with Noise）是一种基于密度的聚类算法，用于将高维数据分组为密度相连的、具有相似特征的多个数据簇。其原理如下：

  1. 选择参数：DBSCAN算法需要两个关键参数，即ε（eps）和 MinPts。其中，ε用于定义邻域的大小，MinPts是指在邻域内至少应该有的数据点数目。
  2. 构建邻域：对于每个数据点，以其为圆心，半径为ε的圆形区域内，如果有MinPts个或以上的数据点，则将这些数据点标记为核心点。
  3. 扩展邻域：从每个核心点开始，将其邻域内的所有数据点加入同一个簇。然后，遍历每个数据点，如果其邻域内包含其他未被访问过的数据点，则将该数据点标记为核心点，并重复步骤2。
  4. 合并簇：如果两个簇之间距离小于ε，则将它们合并为一个簇。
  5. 标记噪声点：未被任何簇包含的数据点被标记为噪声点。

优缺点

主要优点：

  • 能够有效处理具有复杂形状的簇，能够识别出离群点。
  • 不需要事先确定簇的数量，可以自动识别出各个簇。
  • 对数据量不敏感，可以处理大规模数据集。
  • 算法的可解释性强，结果易于理解。

主要缺点：

  • 需要选择合适的参数，特别是ε的值，不同的数据集可能需要不同的参数值。
  • 对于高维数据，可能会出现“维数灾难”，使得算法的性能下降。
  • 对于分布不均匀的数据集，可能会出现一些簇被漏掉或者噪声点被误分类为簇内数据点的情况。
  • 对于边界模糊的数据集，可能会出现一些簇被错误地分割成多个簇。

代码

from sklearn.cluster import DBSCAN  
from sklearn.datasets import make_blobs  
import matplotlib.pyplot as plt  
  
# 生成一个随机数据集  
X, y = make_blobs(n_samples=1000, centers=8, random_state=42)  
  
# 创建DBSCAN聚类器  
dbscan = DBSCAN(eps=0.5, min_samples=5)  
  
# 进行聚类  
labels = dbscan.fit_predict(X)  
  
# 可视化聚类结果  
plt.scatter(X[:, 0], X[:, 1], c=labels, cmap='rainbow')  
plt.show()

四、均值漂移聚类

原理

均值漂移聚类（Mean Shift Clustering）是一种基于密度的聚类算法，用于将高维数据分组为密度相连的、具有相似特征的多个数据簇。其原理如下：

1- 选择参数：均值漂移聚类算法需要选择一个关键参数，即带宽（bandwidth）。带宽用于控制均值漂移算法的搜索半径，即决定哪些数据点被认为是相似的。

  1. 初始化簇：从数据集中随机选择一个数据点作为初始簇中心。

  2. 计算均值漂移向量：对于每个数据点，计算其与当前簇中心的均值漂移向量。均值漂移向量的计算方法是，对于每个数据点，将其与当前簇中心之间的距离除以带宽，得到一个权重，然后将权重乘以该数据点，最后将这些权重加起来得到均值漂移向量。

  3. 漂移簇中心：根据计算出的均值漂移向量，将当前簇中心向所有数据点的均值漂移向量的和的方向漂移一定距离。这个距离可以根据数据集的大小和复杂度进行调整。

  4. 检查终止条件：如果簇中心移动的距离小于一个预定义的阈值，则认为算法已经收敛，终止迭代。

  5. 重复步骤3到步骤5，直到所有数据点都被分配到一个簇中。

优缺点

主要优点：

  • 适用于非凸形状的簇：均值漂移聚类算法对于非凸形状的簇具有较好的聚类效果，可以识别出具有复杂形状的簇。
  • 适用于任意维数：均值漂移聚类算法适用于任意维数的数据集，可以处理高维数据。
  • 对数据量不敏感：均值漂移聚类算法可以处理大规模数据集，并且时间复杂度与数据集大小的关系不大。
  • 可解释性强：均值漂移聚类算法的结果易于理解，可以用于数据分析和可视化。

主要缺点：

  • 选择合适的带宽参数比较困难：均值漂移聚类算法对于带宽的选择比较敏感，不同的带宽值可能会导致不同的聚类结果。
  • 无法发现具有不同密度的簇：均值漂移聚类算法只能发现具有相似密度的簇，对于具有不同密度的簇可能无法正确识别。
  • 无法事先确定簇的数量：均值漂移聚类算法无法事先确定簇的数量，需要手动选择或调整。
  • 对噪声和离群点较敏感：均值漂移聚类算法对于噪声和离群点的处理能力较弱，可能会将一些噪声或离群点视为异常点而进行特殊处理。

代码

from sklearn.cluster import MeanShift  
from sklearn.datasets import make_blobs  
import matplotlib.pyplot as plt  
  
# 生成一个随机数据集  
X, y = make_blobs(n_samples=1000, centers=8, random_state=42)  
  
# 创建MeanShift聚类器  
meanshift = MeanShift(bandwidth=0.5)  
  
# 进行聚类  
labels = meanshift.fit_predict(X)  
  
# 可视化聚类结果  
plt.scatter(X[:, 0], X[:, 1], c=labels, cmap='rainbow')  
plt.show()

五、谱聚类

原理

谱聚类（Spectral Clustering）是一种基于图论的聚类方法，通过将数据点映射到低维空间，然后在低维空间中进行聚类。其原理如下：

  • 构建相似度矩阵：首先，通过计算数据点之间的相似度或距离，构建一个相似度矩阵。相似度矩阵可以通过不同的方法来计算，比如欧几里得距离、余弦相似度等。
  • 构造拉普拉斯矩阵：将相似度矩阵转化为拉普拉斯矩阵。拉普拉斯矩阵是一个对称的、半正定的矩阵，其非零特征值对应于数据点的低维表示，也就是谱聚类的核心。
  • 计算特征值和特征向量：通过求解拉普拉斯矩阵的特征值和特征向量，将数据点从原始空间映射到低维空间。
  • 进行聚类：在低维空间中，通过传统的聚类方法（如K-Means）对数据进行聚类。

优缺点

1、谱聚类的优点包括：

  • 适用于非凸形状的簇：谱聚类算法对于非凸形状的簇具有较好的聚类效果，可以识别出具有复杂形状的簇。
  • 适用于任意维数：谱聚类算法适用于任意维数的数据集，可以处理高维数据。
  • 对数据量不敏感：谱聚类算法可以处理大规模数据集，并且时间复杂度与数据集大小的关系不大。
  • 可解释性强：谱聚类算法的结果易于理解，可以用于数据分析和可视化。
  • 自动确定簇的数量：谱聚类算法可以通过特征值的数量来确定簇的数量，而不需要手动调整。

2、然而，谱聚类算法也存在以下缺点：

  • 对噪声和离群点较敏感：谱聚类算法对于噪声和离群点的处理能力较弱，可能会将一些噪声或离群点视为异常点而进行特殊处理。
  • 需要选择合适的相似度矩阵计算方法：谱聚类算法对于相似度矩阵的选择比较敏感，不同的相似度矩阵计算方法可能会导致不同的聚类结果。
  • 计算复杂度高：谱聚类算法需要计算相似度矩阵和拉普拉斯矩阵的特征值和特征向量，计算复杂度较高，不适用于大规模数据集。

代码

from sklearn.cluster import SpectralClustering  
from sklearn.datasets import make_blobs  
import matplotlib.pyplot as plt  
  
# 生成一个随机数据集  
X, y = make_blobs(n_samples=1000, centers=8, random_state=42)  
  
# 创建谱聚类器  
spectral = SpectralClustering(n_clusters=8, affinity='nearest_neighbors'


    
, assign_labels='kmeans')  
  
# 进行聚类  
labels = spectral.fit_predict(X)  
  
# 可视化聚类结果  
plt.scatter(X[:, 0], X[:, 1], c=labels, cmap='rainbow')  
plt.show()

六、模糊聚类Fuzzy Clustering

模糊聚类（Fuzzy Clustering）是一种基于模糊逻辑的聚类方法，它允许每个数据点在多个簇中具有不同的隶属度。其原理如下：

  1. 初始化：首先，需要初始化每个数据点的隶属度矩阵，通常将每个数据点都初始化为单独的一簇，即每个数据点的隶属度都为1，其他簇的隶属度都为0。
  2. 计算相似度：然后，需要计算每个数据点之间的相似度，通常使用欧几里得距离、曼哈顿距离等计算方法。
  3. 更新隶属度：根据相似度矩阵，可以计算每个数据点对每个簇的隶属度，即更新隶属度矩阵。
  4. 停止条件：模糊聚类的过程会一直进行，直到满足停止条件为止。通常，可以设置一个迭代次数或者设定一个阈值来控制停止条件。
  5. 聚类：最后，根据隶属度矩阵，可以将数据点分配到不同的簇中，完成模糊聚类的过程。

优缺点

1-主要优点

  • 对噪声和异常值的不敏感：模糊聚类算法对于噪声和异常值的处理能力较强，可以更好地识别出异常值。
  • 可以发现数据点间的模糊关系：模糊聚类算法可以发现数据点之间的模糊关系，即一个数据点可能同时属于多个簇。
  • 适用于任意维数：模糊聚类算法适用于任意维数的数据集，可以处理高维数据。
  • 算法可解释性强：模糊聚类算法的结果易于理解，可以用于数据分析和可视化。

2-主要缺点

  • 参数选择困难：模糊聚类算法需要选择许多参数，如相似度计算方法、停止条件、初始隶属度矩阵等，这些参数的选择对于聚类结果的影响较大，需要谨慎选择。
  • 计算复杂度高：模糊聚类算法需要计算相似度矩阵和更新隶属度矩阵，计算复杂度较高，不适用于大规模数据集。
  • 不适合发现具有不同密度的簇：由于模糊聚类算法是基于整个数据集的相似度来更新隶属度矩阵的，因此它不适合发现具有不同密度的簇。

代码

from sklearn.cluster import AgglomerativeClustering  
from sklearn.datasets import make_blobs  
import matplotlib.pyplot as plt  
  
# 生成一个随机数据集  
X, y = make_blobs(n_samples=1000, centers=8, random_state=42)  
  
# 创建模糊聚类器  
fuzzy_clustering = AgglomerativeClustering(n_clusters=8, linkage='complete', affinity='euclidean')  
  
# 进行聚类  
labels = fuzzy_clustering.fit_predict(X)  
  
# 可视化聚类结果  
plt.scatter(X[:, 0], X[:, 1], c=labels, cmap='rainbow')  
plt.show()

七、密度峰值聚类Density Peaks Clustering

密度峰值聚类（DPC）是一种基于密度的聚类方法，其原理是基于以下两个假设：

  1. 簇中心的局部密度大于围绕它的点的局部密度；
  2. 不同簇中心间的距离较远。

DPC算法的主要思路是通过搜索数据空间中的密度峰值来确定类簇的中心，然后将周围的点归为相应的簇。具体来说，DPC算法主要包括以下步骤：

(1)计算每个数据点在数据空间中的局部密度，可以使用基于最近邻的方法来计算；

(2)搜索密度峰值，将所有密度大于周围点密度的点标记为可能的簇中心；

(3)对于每个可能的簇中心，计算其与周围点的距离，如果距离小于某个阈值，则将它们归为同一簇；

(4)迭代更新每个簇的中心，直到簇中心不再变化或达到最大迭代次数。

参考文献：https://blog.csdn.net/weixin_45317919/article/details/121472851

优缺点

1、主要优点

  • 无需预先指定簇数，可以自动确定簇数；
  • 可以发现任意形状的簇，对噪声和异常点具有较强的鲁棒性；
  • 算法简单直观，易于实现。

2、主要缺点

DPC算法也存在一些缺点：

  • 算法的时间复杂度较高，对海量数据聚类时，需要消耗较长时间；
  • 阈值的设置对聚类结果影响较大，需要人工调整；
  • 对于高维数据和大规模数据集，可能会出现“维数灾难”和“数据稀疏性”问题。

代码

import numpy as np

def distance(x1, x2):
    # 计算两个样本点之间的欧氏距离
    return np.sqrt(np.sum((x1 - x2) ** 2))

def local_density(x, X, delta):
    # 计算样本点x的局部密度
    distance_list = [distance(x, x_i) for x_i in X]
    return sum([1 for d in distance_list if d 
def min_distance(x, X):
    # 计算样本点x与其他样本点的最小距离
    distance_list = [distance(x, x_i) for x_i in X]
    return np.min(distance_list)

def find_density_peaks(X, delta, rho):
    n_samples = len(X)
    rhos = np.zeros(n_samples)
    deltas = np.zeros(n_samples)

    for i in range(n_samples):
        rhos[i] = local_density(X[i], X, delta)

    sorted_indices = np.argsort(-rhos)
    max_rho_index = sorted_indices[0]

    for i in range(n_samples):
        deltas[i] = min_distance(X[i], X)

    centers = [max_rho_index]
    center_deltas = [deltas[max_rho_index]]

    for i in range(1, n_samples):
        if rhos[sorted_indices[i]] > rho and deltas[sorted_indices[i]] > center_deltas[-1]:
            centers.append(sorted_indices[i])
            center_deltas.append(deltas[sorted_indices[i]])

    return centers

# 示例用法
X = np.array([[1, 2], [1.5, 2.5], [2, 1], [6, 5], [6.5, 4.5], [5.5, 5]])
delta = 1.0
rho = 2

centers = find_density_peaks(X, delta, rho)
print("聚类中心点的索引:", centers)

在上面的代码中，distance函数用于计算两个样本点之间的欧氏距离。local_density函数计算样本点x的局部密度，它遍历数据集中的每个样本点，并统计距离小于给定阈值delta的样本点个数。

min_distance函数计算样本点x与其他样本点的最小距离。find_density_peaks函数是主要的密度峰值聚类算法，它遍历数据集中的每个样本点，计算每个样本点的局部密度和最小距离，并根据给定的rho和delta阈值找到密度峰值点作为聚类中心。

在示例用法中，我们给定了一个简单的二维数据集X，并指定了delta和rho的阈值。通过调用find_density_peaks函数，我们可以获得聚类中心点的索引。输出结果将显示聚类中心点的索引值。

请注意，密度峰值聚类算法对于选择合适的delta和rho阈值非常敏感，因此在实际应用中可能需要进行调参和验证。

八、基于高斯混合模型GMM和最大值期望EM的聚类

GMM原理

高斯混合模型（Gaussian Mixture Model，简称GMM）是一种常用的聚类算法，它假设数据点服从高斯分布。

GMM聚类算法通过迭代来不断优化隶属度矩阵和聚类中心，以最小化数据点与高斯分布之间的误差。其迭代过程包括以下步骤：

  1. 初始化隶属度矩阵：对于每个数据点，将其初始分配给一个聚类，隶属度矩阵中的每个元素初始化为1/聚类数。
  2. 更新聚类中心：对于每个聚类，计算所有属于该聚类的数据点的均值，得到该聚类的新的聚类中心。
  3. 计算概率：对于每个数据点，计算它属于每个聚类的概率，方法是使用每个聚类的高斯分布概率密度函数计算。
  4. 更新隶属度矩阵：对于每个数据点，根据它属于每个聚类的概率，更新隶属度矩阵中的元素。具体方法是，将每个元素的值设为其对应的聚类的概率除以所有聚类的概率之和。
  5. 判断是否收敛：如果隶属度矩阵的变化小于一个预定义的阈值，则认为模型已经收敛。
  6. 通过迭代上述过程，GMM最终得到一个高斯混合分布来描述数据集的分布情况，并且能够将数据点分类到不同的聚类中。

EM算法

最大值期望（Expectation-Maximization，EM）算法是一种用于在概率模型中估计参数的迭代算法。该算法通常用于处理带有潜在变量的数据集，其中观测数据是部分可观测的。

EM算法的目标是通过迭代来最大化观测数据的对数似然函数，以估计模型参数。它通过以下两个步骤来实现：

  • E步骤（Expectation）：在这个步骤中，算法计算每个观测数据点属于每个聚类的概率。这通常通过计算每个观测数据点在每个聚类中心周围的概率密度函数来实现。这个步骤的目标是计算每个观测数据点属于每个聚类的概率分布。

  • M步骤（Maximization）：在这个步骤中，算法根据上一步中计算出的概率分布来更新模型参数。对于每个参数，算法计算将观测数据分配给每个聚类的概率与每个聚类中心位置的乘积，然后将这些乘积的加权平均用于更新参数值。这个步骤的目标是最大化观测数据的对数似然函数，以估计模型参数。

参考：https://zhuanlan.zhihu.com/p/568823491

代码

from sklearn.mixture import GaussianMixture  
import numpy as np  
  
# 生成随机数据  
np.random.seed(0)  
X = np.concatenate([np.random.normal(0, 1, int(0.3*100)),  
                    np.random.normal(5, 1, int(0.4*100)),  
                    np.random.normal(10, 1, int(0.3*100))])  
X = X.reshape(-1, 2)  
  
# 训练GMM模型  
gmm = GaussianMixture(n_components=3, max_iter=100)  
gmm.fit(X)  
labels = gmm.predict(X)  
  
# 可视化聚类结果  
plt.scatter(X[:, 0], X[:, 1], c=labels)  
plt.show()

最后

这些聚类方法各有特点和使用场景，需要根据具体的数据特点和需求选择合适的方法。同时，这些方法也可以结合使用或者与其他算法结合使用，以实现更好的聚类效果。



    

往期精彩


    
回顾




Python社区是高质量的Python/Django开发社区
本文地址：http://www.python88.com/topic/157691
Reply
 
277 次点击  
登录后回复
关于  
Py学习 - 专注于Python技术发展的社区(原Django社区)
沪ICP备11025650号