聚类算法

问题

K-Means 的原理是什么？和 DBSCAN 有什么区别？

答案

一、K-Means

算法步骤

优缺点

优点	缺点
简单快速 $O(nKt)$	需要预设 K
适合球形簇	对初始中心敏感
可扩展到大数据	不适合非凸形状

K 值选择

• 肘部法则：绘制 K 与 SSE（组内平方和）曲线，找拐点
• 轮廓系数：越接近 1 聚类效果越好

二、DBSCAN

基于密度的聚类，不需要预设簇数量：

概念	定义
ε (eps)	邻域半径
MinPts	核心点最少邻居数
核心点	ε 邻域内 ≥ MinPts 个邻居
边界点	不是核心点但在核心点邻域内
噪声点	既不是核心点也不是边界点

三、算法对比

对比维度	K-Means	DBSCAN	层次聚类
需要预设 K	✅	❌	可选
簇形状	球形	任意形状	任意形状
噪声处理	差	好（自动检测）	差
时间复杂度	$O(nKt)$	$O(n \log n)$	$O(n^2 \log n)$
大数据集	适合	中等	不适合

---

常见面试问题

Q1: K-Means 的初始化有什么改进方法？

答案：

• K-Means++：选择初始中心尽量远离彼此
  1. 随机选第 1 个中心
  2. 下一个中心选距已有中心最远的点（按概率）
  3. 重复直到选满 K 个
• sklearn 的 KMeans 默认使用 K-Means++

Q2: DBSCAN 的 eps 和 MinPts 如何选择？

答案：

• MinPts：通常设为 $2 \times \text{特征维度}$，最小为 3
• eps：用 K-距离图（对每个点计算第 K 近邻距离，排序绘图，找拐点）
• 这两个参数对结果影响很大，需要仔细调参

---

相关链接

• 无监督学习
• 降维算法