通透!十大聚类算法全总结!!

2023-11-28 16:39:51 浏览数 (1)

核心点:详细总结十大聚类算法!!

哈喽,我是Johngo~

精神满满的周一,大家好!今儿咱们整体上聊聊关于聚类算法的细节。

聚类算法在初学者,工作岗位,都是很常见的算法之一。

聚类算法的重要性不言而喻,今天拿出最常见的 10 种聚类算法和大家聊聊~

  1. K-means:这是最常见的聚类算法之一,用于将数据分成预定义数量的簇。
  2. 层次聚类:通过构建数据点之间的层次结构来进行聚类,可以是自底向上的凝聚方法或自顶向下的分裂方法。
  3. DBSCAN:一种基于密度的聚类算法,能够识别任意形状的簇,同时对噪声和离群点具有较好的鲁棒性。
  4. 谱聚类:使用数据的相似性矩阵来进行聚类,特别适用于复杂形状的数据集。
  5. 高斯混合模型:是一种基于概率模型的聚类方法,适用于估计子群体的分布。
  6. 模糊C-means:与K-means相似,但允许一个数据点属于多个簇,每个簇都有一定的隶属度或概率。
  7. K-medoids:与K-means类似,但使用数据点(medoids)而不是均值作为簇的中心。
  8. Mean Shift:通过迭代地更新候选簇中心点来寻找数据点密度最高的区域。
  9. OPTICS:一种基于密度的聚类算法,类似于DBSCAN,但对不同密度的数据集表现更好。
  10. BIRCH:专为大型数据集设计的一种层次聚类方法。

这些聚类算法各有优缺点,适用于不同类型的数据和不同的应用场景。选择合适的聚类算法通常取决于具体的需求、数据的特性和计算资源。

老规矩大家伙如果觉得近期文章还不错!欢迎大家点个赞、转个发,让更多的朋友看到。

更多的细节,下面将简介、核心公式原理、以及Python代码完完整整的实现出来。

咱们一起学习下~~

1. K-mean

K-means 是一种广泛使用的聚类算法,它的目标是将数据点分组到 K 个簇中,以使簇内的点尽可能相似,而簇间的点尽可能不同。它的核心思想是通过迭代优化簇中心的位置,以最小化簇内的平方误差总和。

算法步骤

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

目标函数

K-means 试图最小化簇内误差平方和,其公式为:

J = sum_{i=1}^{k} sum_{x in S_i} ||x - mu_i||^2

其中,

mu_i

是簇

S_i

的中心,

x

是簇

S_i

内的点,

||x - mu_i||

是点

x

到簇中心

mu_i

的欧几里得距离。

Python 实现

接下来,使用 Python 的 sklearn 库来实现 K-means 算法。

首先,生成一些随机数据进行演示,然后应用 K-means 算法,并展示结果。

代码语言:javascript复制
import numpy as np
import matplotlib.pyplot as plt
from sklearn.cluster import KMeans
from sklearn.datasets import make_blobs

# 生成模拟数据
np.random.seed(0)
X, y = make_blobs(n_samples=300, centers=4, cluster_std=0.60, random_state=0)

# 应用K-means算法
kmeans = KMeans(n_clusters=4)
kmeans.fit(X)
y_kmeans = kmeans.predict(X)

# 绘制数据点和聚类中心
plt.scatter(X[:, 0], X[:, 1], c=y_kmeans, s=50, cmap='viridis')
centers = kmeans.cluster_centers_
plt.scatter(centers[:, 0], centers[:, 1], c='red', s=200, alpha=0.5)
plt.title("K-means Clustering")
plt.xlabel("Feature 1")
plt.ylabel("Feature 2")
plt.show()

上图展示了使用 K-means 算法对模拟数据进行聚类的结果。图中的彩色点表示数据点,它们根据所属的簇被着色。红色的大点表示每个簇的中心。

在这个示例中,我们设定了四个簇(n_clusters=4),K-means 算法成功地将数据点分配到了这四个簇中,并计算出了每个簇的中心。

K-means 算法简单高效,广泛应用于各种场景,特别是在需要快速、初步的数据分组时。然而,它也有局限性,比如对初始簇中心的选择敏感,可能会陷入局部最优,且假设簇是凸形的,对于复杂形状的数据可能不适用。

2. 层次聚类

层次聚类是一种常用的聚类方法,它通过构建数据点之间的层次结构来进行聚类。层次聚类不需要预先指定簇的数量,并且结果可以表示为树状图(称为树状图或层次树),提供了数据点之间关系的丰富视图。

类型

  1. 凝聚型(Agglomerative):从每个点作为单独的簇开始,逐渐合并最近的簇。
  2. 分裂型(Divisive):从所有数据作为一个簇开始,逐步分裂为更小的簇。

算法步骤(以凝聚型为例)

  1. 开始时,将每个数据点视为一个单独的簇。
  2. 找到最相似(距离最近)的两个簇并将它们合并。
  3. 重复步骤 2,直到所有数据点都合并到一个簇中或达到预定的簇数量。

距离公式

层次聚类中,簇之间的相似性通常用距离来衡量,常用的距离度量有:

  • 单链接(Min):
d(S,T) = min { d(x,y) : x in S, y in T }
  • 完全链接(Max):
d(S,T) = max { d(x,y) : x in S, y in T }
  • 平均链接(Average): d(S,T) = frac1}{S| cdot |T| sum_{x in S} sum_{y in T} d(x,y)
  • Ward 方法:最小化合并簇后的方差增加量。

其中

S

T

是不同的簇,

d(x,y)

是簇内点

x

y

之间的距离。

Python 实现

接下来,使用 Python 的 scipy 库来实现层次聚类,并使用 matplotlib 库绘制树状图。我们将使用相同的模拟数据来展示层次聚类的结果。

代码语言:javascript复制
from scipy.cluster.hierarchy import dendrogram, linkage
from matplotlib import pyplot as plt

# 生成层次聚类的链接矩阵
Z = linkage(X, method='ward')

# 绘制树状图
plt.figure(figsize=(10, 5))
plt.title('Hierarchical Clustering Dendrogram')
plt.xlabel('Sample index')
plt.ylabel('Distance')
dendrogram(Z)
plt.show()

上图展示了层次聚类的树状图,也称为树状图。在这个图中:

  • 每个点代表一个数据样本。
  • 水平线表示簇的合并,其长度代表合并簇之间的距离或不相似度。
  • 树状图的垂直轴代表距离或不相似度,可以用来判断簇之间的距离。

通过这个树状图,我们可以观察数据的层次聚类结构,并根据需要选择适当的截断点来确定簇的数量。例如,通过在不同的高度水平切割树状图,可以得到不同数量的簇。

层次聚类特别适用于那些簇的数量不明确或数据具有自然层次结构的场景。与 K-means 等算法相比,它不需要预先指定簇的数量,但计算复杂度通常更高。

3. DBSCAN

DBSCAN(Density-Based Spatial Clustering of Applications with Noise)是一种基于密度的聚类算法,特别适用于具有噪声的数据集和能够发现任意形状簇的情况。它不需要事先指定簇的数量,能有效处理异常点。

核心概念

  • 核心点:在指定半径
epsilon

内有至少

text{minPts}

个其他点的点。

  • 边界点:在半径
epsilon

内少于

text{minPts}

个点,但属于核心点的邻域。

  • 噪声点:既不是核心点也不是边界点的点。

算法步骤

  1. 标记所有点为核心点、边界点或噪声点。
  2. 删除噪声点。
  3. 为剩余的核心点创建簇,如果一个核心点在另一个核心点的邻域内,则将它们放在同一个簇中。
  4. 将每个边界点分配给与之关联的核心点的簇。

DBSCAN 的参数

epsilon

:邻域的大小。

text{minPts}

:形成密集区域所需的最小点数。

Python 实现

下面,使用 Python 的 sklearn 库中的 DBSCAN 类来实现 DBSCAN 算法。

代码语言:javascript复制
from sklearn.cluster import DBSCAN
import numpy as np
import matplotlib.pyplot as plt

# 再次使用之前的模拟数据
X, _ = make_blobs(n_samples=300, centers=4, cluster_std=0.60, random_state=0)

# 应用DBSCAN算法
dbscan = DBSCAN(eps=0.5, min_samples=5)
clusters = dbscan.fit_predict(X)

# 绘制聚类结果
plt.scatter(X[:, 0], X[:, 1], c=clusters, cmap='viridis', marker='o', s=50)
plt.title("DBSCAN Clustering")
plt.xlabel("Feature 1")
plt.ylabel("Feature 2")
plt.show()

上图展示了使用 DBSCAN 算法对模拟数据进行的聚类结果。在这个图中,不同颜色的点表示不同的簇,而相同颜色的点属于同一个簇。

在 DBSCAN 算法中,我设置了邻域大小(eps=0.5)和最小点数(min_samples=5)。算法能够识别出密度不同的簇,并且有效地区分出噪声点(通常用特殊颜色或标记表示,但在此图中未显示)。

DBSCAN 的优势在于它不需要事先指定簇的数量,可以识别任意形状的簇,并且对噪声数据具有良好的鲁棒性。然而,选择合适的 epsmin_samples 参数对于获得好的聚类结果至关重要。

4. 谱聚类

谱聚类是一种基于图论的聚类方法,特别适用于发现复杂形状的簇和非球形簇。与传统的聚类算法(如K-means)不同,谱聚类依赖于数据的相似性矩阵,并利用数据的谱(即特征向量)来进行降维,进而在低维空间中应用如K-means的聚类方法。

算法步骤

  1. 构建相似性矩阵:基于数据点之间的距离或相似度。
  2. 计算图的拉普拉斯矩阵:常用的是归一化拉普拉斯矩阵。
  3. 计算拉普拉斯矩阵的特征向量和特征值
  4. 基于前
k

个特征向量的新特征空间,应用传统聚类算法(如K-means)

相关公式

  • 相似性矩阵
S

:若

s_{ij}

代表点

i

和点

j

的相似度,则

S = [s_{ij}]

  • 度矩阵
D

:对角矩阵,其对角元素

d_{ii}

是点

i

的度(即与点

i

相连的边的权重之和)。

  • 拉普拉斯矩阵
L

:定义为

L = D - S

Python 实现

下面,使用 Python 的 sklearn 库中的 SpectralClustering 类来实现谱聚类。

代码语言:javascript复制
from sklearn.cluster import SpectralClustering
import matplotlib.pyplot as plt
from sklearn.datasets import make_blobs

# 生成模拟数据
X, _ = make_blobs(n_samples=300, centers=4, cluster_std=0.60, random_state=0)

# 应用谱聚类算法
spectral_clustering = SpectralClustering(n_clusters=4, affinity='nearest_neighbors')
clusters = spectral_clustering.fit_predict(X)

# 绘制聚类结果
plt.scatter(X[:, 0], X[:, 1], c=clusters, cmap='viridis', marker='o', s=50)
plt.title("Spectral Clustering")
plt.xlabel("Feature 1")
plt.ylabel("Feature 2")
plt.show()

上图展示了使用谱聚类算法对模拟数据进行的聚类结果。在这个图中,不同颜色的点表示不同的簇,而相同颜色的点属于同一个簇。

在这个示例中,谱聚类被设置为将数据分成四个簇(n_clusters=4),并使用最近邻方法(affinity='nearest_neighbors')来构建相似性矩阵。然而,警告信息表明,生成的图可能不是完全连接的,这可能影响聚类结果。

谱聚类的一个关键优势是能够发现任意形状的簇,这使得它特别适用于那些传统聚类算法(如K-means)难以处理的数据集。不过,选择合适的相似性度量和参数对于获得好的聚类结果至关重要。此外,谱聚类的计算复杂度比一些其他聚类算法高,特别是在处理大型数据集时。

5. 高斯混合模型

高斯混合模型(GMM)是一种基于概率模型的聚类算法,它假设所有数据点都是从有限个高斯分布的混合生成的。与K-means等硬聚类算法不同,GMM 属于软聚类算法,它为每个数据点提供了属于各个簇的概率。

核心概念

  • 混合模型:假设数据是由
K

个高斯分布混合而成。

  • 高斯分布:每个分布由均值(mean)和协方差(covariance)决定。
  • 概率:每个数据点属于各个簇的概率。

算法步骤

  1. 初始化:随机选择
K

个高斯分布的参数。

  1. 期望步骤(E-step):根据当前参数,计算每个数据点属于每个簇的概率。
  2. 最大化步骤(M-step):更新每个高斯分布的参数以最大化数据的似然。
  3. 迭代:重复 E-step 和 M-step 直到收敛。

目标函数

GMM 试图最大化数据的似然,即:

L(theta) = sum_{i=1}^{N} log left( sum_{k=1}^{K} pi_k mathcal{N}(x_i | mu_k, Sigma_k) right)

其中,

N

是数据点的数量,

K

是簇的数量,

pi_k

是第

k

个高斯分布的混合权重,

mu_k

Sigma_k

分别是第

k

个高斯分布的均值和协方差,

mathcal{N}(x_i | mu_k, Sigma_k)

是第

k

个高斯分布在点

x_i

的概率密度函数。

Python 实现

接下来,我将使用 Python 的 sklearn 库中的 GaussianMixture 类来实现 GMM。

代码语言:javascript复制
from sklearn.mixture import GaussianMixture
import matplotlib.pyplot as plt
from sklearn.datasets import make_blobs

# 生成模拟数据
X, _ = make_blobs(n_samples=300, centers=4, cluster_std=0.60, random_state=0)

# 应用高斯混合模型聚类算法
gmm = GaussianMixture(n_components=4)
gmm.fit(X)
clusters = gmm.predict(X)

# 绘制聚类结果
plt.scatter(X[:, 0], X[:, 1], c=clusters, cmap='viridis', marker='o', s=50)
plt.title("Gaussian Mixture Model Clustering")
plt.xlabel("Feature 1")
plt.ylabel("Feature 2")
plt.show()

上图展示了使用高斯混合模型(GMM)对模拟数据进行的聚类结果。在这个图中,不同颜色的点表示不同的簇,而相同颜色的点属于同一个簇。

在这个示例中,GMM 被设置为将数据分成四个簇(n_components=4)。GMM 算法不仅为每个点分配了一个簇,而且还可以提供关于每个点属于各个簇的概率信息。

GMM 的优势在于它是一个基于概率的方法,提供了比 K-means 更丰富的信息,并且可以模拑非球形的簇。它通过期望最大化(EM)算法迭代地优化参数,以最大化数据的似然概率。不过,选择合适的簇数量和协方差类型对于获得好的聚类结果至关重要。此外,GMM 对于初始化参数比较敏感,可能会陷入局部最优。

6. 模糊C-means

模糊 C-means(FCM)算法允许一个数据点属于多个聚类中心。与传统的K-means聚类算法不同,模糊C-means通过为每个数据点分配一个属于各个聚类中心的隶属度,来表示其属于不同聚类的程度。这种方法特别适用于那些不清晰或重叠的数据集。

基本步骤

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

算法公式

  • 更新聚类中心:
v_i = frac{sum_{j=1}^n u_{ij}^m x_j}{sum_{j=1}^n u_{ij}^m}

其中

v_i

是第

i

个聚类中心,

x_j

是数据点,

u_{ij}

是数据点

j

对聚类中心

i

的隶属度,

m

是模糊化参数,通常设为2。

  • 更新隶属度:
u_{ij} = frac{1}{sum_{k=1}^C left( frac{| x_j - v_i |}{| x_j - v_k |} right)^{frac{2}{m-1}}}

Python代码

以下是使用Python实现模糊C-means算法的一个简单示例:

代码语言:javascript复制
import numpy as np
import matplotlib.pyplot as plt
from sklearn.datasets import make_blobs

# 生成模拟数据
X, _ = make_blobs(n_samples=300, centers=4, cluster_std=0.60, random_state=0)

# 模糊C-means算法实现
def fuzzy_c_means(X, C, m=2, error=0.005, maxiter=300):
    # 初始化隶属度矩阵
    n = X.shape[0]
    U = np.random.rand(n, C)
    U = U / np.sum(U, axis=1, keepdims=True)

    for iteration in range(maxiter):
        # 更新聚类中心
        centers = np.dot(U.T ** m, X) / np.sum(U.T ** m, axis=1, keepdims=True)

        # 更新隶属度
        distance = np.linalg.norm(X[:, np.newaxis] - centers, axis=2)
        U_new = 1.0 / np.sum((distance[:, :, np.newaxis] / distance[:, np.newaxis, :]) ** (2 / (m - 1)), axis=2)

        # 检查是否收敛
        if np.max(np.abs(U_new - U)) < error:
            break
        U = U_new

    return centers, U

# 使用模糊C-means算法
centers, U = fuzzy_c_means(X, C=4)

# 绘制结果
plt.scatter(X[:, 0], X[:, 1], alpha=0.5)
plt.scatter(centers[:, 0], centers[:, 1], c='red', marker='X')
plt.title('Fuzzy C-means Clustering')
plt.show()

这段代码首先生成一些模拟数据,然后使用模糊C-means算法进行聚类,并最后显示聚类结果。在实际应用中,可能需要根据具体的数据集调整参数,如聚类的数目、模糊

7. K-medoids

K-medoids 用于将数据集中的数据点分成多个簇。这种算法与著名的 K-means 算法相似,但主要区别在于 K-medoids 选择数据点中的实际点作为簇的中心,而 K-means 则使用簇内数据点的均值。

算法简介

  1. 初始化:随机选择
k

个数据点作为初始的簇中心。

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

算法公式

K-medoids 算法的目标是最小化簇内点到其簇中心的距离之和。对于给定的簇

C

,其中心

m

由以下公式确定:

m = text{argmin}_{x_i in C} sum_{x_j in C} d(x_i, x_j)

其中

d(x_i, x_j)

表示点

x_i

x_j

之间的距离。

Python 代码

随机生成一些数据点,然后应用一个简单的 K-medoids 算法来聚类这些点,并展示结果。

代码语言:javascript复制
import numpy as np
import matplotlib.pyplot as plt
from sklearn.metrics.pairwise import pairwise_distances
from sklearn.datasets import make_blobs

def simple_kmedoids(data, num_clusters, max_iter=100):
    # Randomly initialize medoids
    medoids = np.random.choice(len(data), num_clusters, replace=False)
    for _ in range(max_iter):
        # Compute distances between data points and medoids
        distances = pairwise_distances(data, data[medoids, :])
        # Assign each point to the closest medoid
        clusters = np.argmin(distances, axis=1)
        # Update medoids
        new_medoids = np.array([np.argmin(np.sum(distances[clusters == k, :], axis=0)) for k in range(num_clusters)])
        # Check for convergence
        if np.array_equal(medoids, new_medoids):
            break
        medoids = new_medoids
    return clusters, medoids

# Generating synthetic data
data, _ = make_blobs(n_samples=150, centers=3, n_features=2, random_state=42)

# Applying the simple K-medoids algorithm
num_clusters = 3
clusters, medoids = simple_kmedoids(data, num_clusters)

# Plotting the results
plt.figure(figsize=(10, 6))
plt.scatter(data[:, 0], data[:, 1], c=clusters, cmap='viridis', marker='o', label='Data points')
plt.scatter(data[medoids, 0], data[medoids, 1], c='red', marker='X', s=100, label='Medoids')
plt.title('Simple K-medoids Clustering')
plt.xlabel('Feature 1')
plt.ylabel('Feature 2')
plt.legend()
plt.grid(True)

# Saving the plot
plot_path_simple = 'simple_kmedoids_clustering.png'
plt.savefig(plot_path_simple)

plot_path_simple

我已经应用了一个简化版的 K-medoids 算法来进行聚类,并生成了一个可视化图像。在这个图中,不同颜色的点代表不同的簇,而红色的“X”标记表示每个簇的中心点(即medoids)。这个图形展示了如何将数据点根据它们与中心点的距离分配到不同的簇中。

8. Mean Shift

Mean Shift 算法是一种基于密度的非参数聚类算法。其核心思想是通过迭代过程寻找数据点密度的峰值。这个算法不需要预先指定簇的数量,它通过数据本身的分布特性来确定簇的数量。

算法概述

  1. 选择带宽(Bandwidth):带宽确定了搜索窗口的大小,对算法的结果有显著影响。
  2. 迭代过程:对每个数据点,计算其在带宽范围内邻近点的均值,然后将数据点移动到这个均值位置。
  3. 收敛:重复上述过程直到数据点的移动非常小或达到预定的迭代次数。

相关公式

假设

x_i

是数据点,核函数

K(x)

通常是一个高斯核,带宽为

h

,则 mean shift 向量为:

M(x) = frac{sum_{x_i in N(x)} K(x_i - x) cdot x_i}{sum_{x_i in N(x)} K(x_i - x)} - x

其中,

N(x)

是在

x

点周围带宽内的邻近点集合。

Python 实现

以下是 Mean Shift 算法的一个基本 Python 实现,使用了 scikit-learn 库:

代码语言:javascript复制
import numpy as np
import matplotlib.pyplot as plt
from sklearn.cluster import MeanShift
from sklearn.datasets import make_blobs

# 生成样本数据
centers = [[1, 1], [5, 5], [3, 10]]
X, _ = make_blobs(n_samples=300, centers=centers, cluster_std=0.7)

# 应用 Mean Shift 算法
ms = MeanShift()
ms.fit(X)
labels = ms.labels_
cluster_centers = ms.cluster_centers_

# 可视化结果
plt.scatter(X[:, 0], X[:, 1], c=labels, marker='o')
plt.scatter(cluster_centers[:, 0], cluster_centers[:, 1], c='red', marker='x')
plt.title('Mean Shift Clustering')
plt.show()

这段代码首先生成一些样本数据,然后应用 Mean Shift 算法对数据进行聚类,并将结果可视化。每个聚类的中心用红色的 'x' 标记。

9. OPTICS

OPTICS(Ordering Points To Identify the Clustering Structure)算法是一种用于数据聚类的算法,与DBSCAN算法类似,但在处理可变密度的数据集时更为有效。其核心思想是通过分析数据点的密度-可达性来识别聚类结构。

简单介绍

  • 核心概念:OPTICS算法主要关注两个概念,即核心距离和可达距离。
    • 核心距离:对于给定点,其核心距离是使其成为核心对象的最小半径。
    • 可达距离:是一个对象到一个核心对象的最小距离。
  • 算法流程:OPTICS算法首先根据核心距离和可达距离为数据点创建一个排序,然后基于这个排序来识别聚类。

相关公式

  1. 核心距离:对于点
p

,核心距离定义为

text{Core-Distance}_{text{MinPts}}(p) = min{ d(p, o) | o in text{Neighbors}_{text{MinPts}}(p) }

其中,

text{Neighbors}_{text{MinPts}}(p)

是点

p

的最近的

text{MinPts}

邻居。

  1. 可达距离:点
o

对于点

p

的可达距离定义为

text{Reachability-Distance}_{text{MinPts}}(o, p) = max{ text{Core-Distance}_{text{MinPts}}(p), d(p, o) }

Python代码

下面的Python代码示例使用sklearn库中的OPTICS类来实现OPTICS算法,并展示结果:

代码语言:javascript复制
from sklearn.cluster import OPTICS
import matplotlib.pyplot as plt
import numpy as np

# 示例数据
X = np.random.rand(100, 2)

# OPTICS模型
optics_model = OPTICS(min_samples=5, xi=0.05, min_cluster_size=0.1)
optics_model.fit(X)

# 可视化
space = np.arange(len(X))
reachability = optics_model.reachability_[optics_model.ordering_]
labels = optics_model.labels_[optics_model.ordering_]

plt.figure(figsize=(10, 7))
colors = ['g.', 'r.', 'b.', 'y.', 'c.']
for klass, color in zip(range(0, 5), colors):
    Xk = space[labels == klass]
    Rk = reachability[labels == klass]
    plt.plot(Xk, Rk, color, alpha=0.3)
plt.plot(space[labels == -1], reachability[labels == -1], 'k.', alpha=0.3)
plt.ylabel('Reachability (epsilon distance)')
plt.title('Reachability Plot')
plt.show()

在这个代码中,我们首先生成了一些随机数据点,然后使用OPTICS算法对其进行聚类,并使用matplotlib库来可视化结果。这个示例生成了一个可达性图,其中每个点的可达性距离都被绘制出来,以揭示数据中的聚类结构。

10. BIRCH

BIRCH(平衡迭代式规约和聚类使用层次方法)是一种用于大数据集的聚类算法,特别适用于具有噪声的大规模数据集。BIRCH算法的核心思想是通过构建一个名为CF Tree(聚类特征树)的内存中的数据结构来压缩数据,该数据结构以一种方式保存数据,使得聚类可以高效地进行。

关键概念

  1. 聚类特征(CF):一个CF是一个三元组,表示为
(N, LS, SS)

,其中:

N

是该聚类中点的数量。

LS

是该聚类中所有点的线性和(即所有点的坐标值的总和)。

SS

是该聚类中所有点的平方和。

  1. CF Tree:这是一个平衡树结构,用于存储聚类特征。它由内部节点和叶子节点组成。叶子节点包含聚类特征,而内部节点包含指向子节点的指针和这些子节点聚类特征的汇总。

算法步骤

  1. 构建CF Tree:读取数据点,更新CF Tree。如果新数据点可以合并到现有聚类中而不违反树的定义,则进行合并;否则,创建新的叶子节点。
  2. 凝聚步骤:可选步骤,用于进一步压缩CF Tree,通过删除距离较近的子聚类并重新平衡树。
  3. 全局聚类:使用其他聚类方法(如K-Means)对叶子节点中的聚类特征进行聚类。

相关公式

聚类特征(CF)的计算公式:

CF = (N, LS, SS)
  • 其中,
N

是点的数量,

LS = sum x_i

x_i

是点的坐标),

SS = sum x_i^2

Python代码

接下来,使用Python演示BIRCH算法的基本使用,并生成相关的图形。我们将使用scikit-learn库中的BIRCH实现。

代码语言:javascript复制
from sklearn.cluster import Birch
from sklearn.datasets import make_blobs
import matplotlib.pyplot as plt

# 生成模拟数据
X, _ = make_blobs(n_samples=1000, centers=4, cluster_std=0.5, random_state=0)

# 应用BIRCH算法
brc = Birch(n_clusters=4)
brc.fit(X)

# 预测聚类标签
labels = brc.predict(X)

# 绘制结果
plt.figure(figsize=(8, 6))
plt.scatter(X[:, 0], X[:, 1], c=labels, cmap='viridis', marker='o')
plt.title("BIRCH Clustering")
plt.xlabel("Feature 1")
plt.ylabel("Feature 2")
plt.colorbar(label='Cluster Label')
plt.show()

上图展示了使用BIRCH算法对模拟数据进行聚类的结果。在这个例子中,我们生成了1000个数据点,分布在4个中心点周围。使用BIRCH算法,我们能够有效地将这些点分成四个不同的聚类,如不同颜色所示。

在实际应用中,BIRCH算法特别适合于处理大规模数据集,并且当数据集中存在噪声时,它通常也能表现良好。通过调整算法参数,例如树的深度和分支因子,可以优化聚类的性能和准确性。

0 人点赞