当前位置：首页 > news >正文

聚类算法(K-means、DBSCAN)

news 来源：原创 2025/7/24 4:47:00

聚类算法

K-means 算法

算法原理

K-means 是一种基于类内距离最小化的划分式聚类算法，其核心思想是通过迭代优化将数据划分为 K 个簇。目标函数为最小化平方误差（SSE）：
$\sum_{i=1}^{K} \sum_{x \in C_i} ||x - \mu_i||^2$
其中 $\mu_i$ 是第 $i$ 个簇的质心。

算法步骤

初始化：
- 随机选择 K 个初始质心（或使用 k-means++ 优化初始化）
迭代优化：
- 分配阶段：将每个样本分配到距离最近的质心所属簇
  $C_i = \{ x : ||x - \mu_i||^2 \leq ||x - \mu_j||^2, \forall j \}$
- 更新阶段：重新计算每个簇的质心
  $\mu_i = \frac{1}{|C_i|} \sum_{x \in C_i} x$
终止条件：
- 质心位置不再变化（收敛）
- 达到最大迭代次数
- SSE 变化量小于阈值

特点

时间复杂度： $O (n * K * I * d)$ ，n 为样本数，I 为迭代次数
需预先指定 K 值
对初始质心敏感，可能收敛到局部最优

DBSCAN 算法

算法原理

DBSCAN（Density-Based Spatial Clustering of Applications with Noise）是一种基于密度可达性的聚类算法，由Ester等人在1996年提出，其核心思想是通过数据点的局部密度分布识别聚类结构，并有效处理噪声。算法中的关键概念包括：

核心点：以某点为中心、半径ε邻域内的点数≥MinPts的点，是簇形成的基础。
边界点：位于核心点的ε邻域内，但自身邻域内点数＜MinPts的点。
噪声点：既非核心点也非边界点的孤立点。
密度可达性：若点A通过一系列核心点间接可达点B，则称A与B密度可达。
密度连通性：若存在核心点O，使得点A和B均密度可达于O，则A与B密度连通。

算法步骤

初始化参数：设置邻域半径ε和最小密度阈值MinPts。
遍历未访问点：随机选择一个未访问点，计算其ε邻域内的点数：
- 若点数＜MinPts：标记为噪声点（可能后续被重新归类为边界点）。
- 若点数≥MinPts：标记为核心点，创建新簇，递归合并所有密度可达点。
扩展聚类：通过核心点的邻域不断吸收边界点和可达核心点，直至无法扩展。
重复处理：遍历所有未访问点，直至数据集处理完毕。

特性

时间复杂度：O(n log n)（使用空间索引时）
可发现任意形状的簇
自动识别噪声点
对参数敏感

聚类评估指标

1. 轮廓系数 (Silhouette Coefficient)

综合衡量样本的簇内紧密度和簇间分离度：
$\frac{b(i) - a(i)}{\max\{a(i), b(i)\}}$

$a (i)$ ：样本 i 到同簇其他点的平均距离
$b (i)$ ：样本 i 到最近其他簇的平均距离
取值范围：[-1, 1]，值越大聚类质量越高

2. Calinski-Harabasz 指数

通过方差比评估聚类质量：
$\frac{tr(B_k)/(K-1)}{tr(W_k)/(n-K)}$

$B_k$ ：簇间协方差矩阵
$W_k$ ：簇内协方差矩阵
值越大表示簇间差异越大，簇内越紧密

K-means 的 K 值选择方法详解

肘部法则 (Elbow Method)

计算不同 K 值对应的 SSE：

sse = []
for k in range(1, 11):kmeans = KMeans(n_clusters=k)kmeans.fit(data)sse.append(kmeans.inertia_)

聚类算法

K-means 算法

算法原理

算法步骤

特点

DBSCAN 算法

算法原理

算法步骤

特性

聚类评估指标

1. 轮廓系数 (Silhouette Coefficient)

2. Calinski-Harabasz 指数

K-means 的 K 值选择方法详解

肘部法则 (Elbow Method)

相关文章：