2.13 聚类K-means、层次与DBSCAN

1.先承认一件事：聚类手里没有标准答案

说起来，前面那些章节我们讨论的不管是分类还是回归，样本都自带标签，模型照着标签学就行。聚类这一章换了个局面。它属于无监督学习，手里压根没有标签，要靠样本彼此之间的相似性自己分堆。打个比方，有监督学习像老师拿着答案批改作业，聚类更像一群同学自己凑到一起，志趣相投的几个人自然就围成一圈。

聚类要做的事情，是在没有标准答案的前提下，把相似的样本归到同一簇，把不那么相似的样本分到不同簇。前面讲分类评估时我们反复用过的ROC、AUC、混淆矩阵，都建立在有真实标签可以对照的前提下。聚类手里没有标签，连准不准这件事都难以直接衡量，只能转而看簇内是否紧凑、簇间是否分开。这里有个朴素的前提：样本可以表示成一组特征，相似与否由特征之间的距离来体现。我们最常用的距离是欧氏距离，两个样本 $x_i$ 和 $x_j$ 之间的欧氏距离记作 $d(x_i, x_j)$，其中 $x_i$ 表示第 $i$ 个样本的特征向量，$x_j$ 表示第 $j$ 个样本的特征向量，$d$ 是衡量这两个向量差多少的函数，算的是把每一维的差值平方、求和、再开根号。这个 $d$ 在整篇文章里都指欧氏距离，下面不再改含义。

聚类听起来随意，其实用处极大。一家电商平台有几千万用户，没人给每个用户写好标签，可用户的浏览时长、加购次数、客单价这些特征是有的，聚类一跑，就能自动把用户分成几大群体，做精准营销的时候不至于一刀切。这一节我们先讲最经典的K-means，再讲层次聚类和DBSCAN，最后回到应用场景。

2.K-means：反复分堆再求中心

K-means大概是所有聚类算法里最入门、也最常用的一款，思路直白得让人有点意外。我们先定一个整数 $K$，$K$ 表示我们要把数据分成几簇，比如 $K=3$ 就是想分成3堆。算法一开始，会从数据里随机挑 $K$ 个样本当作初始的中心点，把这些中心记作 $\mu_1, \mu_2, \ldots, \mu_K$，其中 $\mu_k$ 表示第 $k$ 个簇的中心（$\mu$ 是希腊字母mu，在这里专门用来代表簇心，整篇都是这个意思，$k$ 是簇的编号）。

接下来算法反复做两步。

第一步是分配。对每一个样本 $x_i$，分别算它到 $K$ 个中心 $\mu_1, \mu_2, \ldots, \mu_K$ 的距离，看哪个中心离它最近，就把它划给那个中心所在的簇。第二步是更新。对每一个簇，把它名下所有样本的特征取平均，得到一个新的中心点，用来替换原来的 $\mu_k$。这两步交替进行，直到中心点几乎不再变动，或者每个样本所属的簇不再发生变化，我们就说算法收敛了。

K-means实际在最小化一个目标函数，叫簇内平方和（within-cluster sum of squares），记作 $J$：

$$J = \sum_{k=1}^{K} \sum_{x_i \in C_k} d(x_i, \mu_k)^2$$

其中 $C_k$ 表示第 $k$ 个簇里所有样本组成的集合，$\sum$ 是求和符号，外层 $\sum_{k=1}^{K}$ 表示把 $K$ 个簇逐一加起来，内层 $\sum_{x_i \in C_k}$ 表示对该簇里每一个样本 $x_i$ 求和，$d(x_i, \mu_k)$ 是样本 $x_i$ 到它所在簇中心 $\mu_k$ 的欧氏距离。整个 $J$ 就是所有样本到各自簇心距离的平方再求和。K-means反复做分配和更新，本质就是想让这个 $J$ 尽量小，让每个簇内部的样本都尽量靠拢自己的中心。

带数字的小例子

讲公式总归有点空，我们不妨走一个带数字的小例子。假设平面上有6个点，坐标分别是 $A(1,1)$、$B(1,2)$、$C(2,1)$、$D(8,8)$、$E(8,9)$、$F(9,8)$，肉眼一看就是左下角3个挤一堆、右上角3个挤一堆。我们令 $K=2$，随机挑两个点当初始中心，假设挑到了 $A(1,1)$ 和 $D(8,8)$。

先做分配。$B(1,2)$ 离 $A(1,1)$ 的距离是 $\sqrt{(1-1)^2+(2-1)^2}=1$，离 $D(8,8)$ 的距离是 $\sqrt{(1-8)^2+(2-8)^2}=\sqrt{49+36}=\sqrt{85}\approx9.22$，离 $A$ 近，划给第一簇。同理 $C(2,1)$ 离 $A$ 是 $1$，离 $D$ 大约 $9.22$，也划给第一簇。$E(8,9)$ 和 $F(9,8)$ 离 $D$ 都很近，划给第二簇。于是第一簇是 $\{A,B,C\}$，第二簇是 $\{D,E,F\}$。

再做更新。第一簇的新中心是这三个点的坐标平均，横坐标 $(1+1+2)/3\approx1.33$，纵坐标 $(1+2+1)/3\approx1.33$，所以新的 $\mu_1\approx(1.33,1.33)$。第二簇的新中心同理，$\mu_2\approx(8.33,8.33)$。

再回到分配这一步，分簇结果没有发生变化，算法就收敛了，我们这个手算的小例子到此为止。真实数据里通常要多跑几轮，道理却完全一样。

K怎么选：肘部法

K-means有一个绕不开的问题，就是 $K$ 到底定多少。预先知道答案的事毕竟少。一个常用的法子叫肘部法（elbow method）。做法是把 $J$ 当作 $K$ 的函数，让 $K$ 从小到大取值，比如 $1$ 到 $10$，分别跑一遍K-means，画出 $J$ 随 $K$ 变化的曲线。$K$ 越大，$J$ 一定越小，极端情况 $K$ 等于样本数时 $J=0$，每个样本自成一簇。我们关心的是曲线从陡降变平缓的那个拐点，那个位置就像胳膊的肘部，再往上加 $K$ 收益已经不大，肘部对应的 $K$ 通常就是个不错的选择。比方说 $K$ 从1到3时 $J$ 掉得厉害，从3到4开始变缓，那 $K=3$ 大概就合适。

我有个朋友小张在做电商运营，第一次跑K-means给用户分群，肘部法看下来明明 $K=4$ 最合适，他偏偏为了显得细致，硬上 $K=10$，结果分出来的群体细碎到没法各自写文案，最后还是老老实实回到 $K=4$。可见 $K$ 不是越大越好，分到能讲故事的程度就够。

K-means的脾气和短板

K-means用起来省心，可短板也得说清楚，否则真到了大厂面试那一关，被追问一下就容易卡壳。

第一，$K$ 要预先指定，模型自己不会告诉你分几堆合适。第二，对初始中心敏感。同样一批数据，初始中心挑得不一样，最后的结果可能差很多，因为算法只能找到局部最优。工程上常见的改良是K-means++，它在挑初始中心的时候会刻意让它们彼此离得远一些，比起纯随机要稳得多。第三，K-means默认每个簇是球形的（在欧氏距离下接近一个球），而且大小别差太多。要是数据里的簇是长条形、月牙形、同心套圈形，K-means往往分得很不好。第四，它怕异常值，因为中心是取均值，一个跑偏很远的样本能把整个中心拽歪。

3.层次聚类：不用先定簇数，结果是一棵树

层次聚类走的是另一条路。它最大的好处是不用提前说定几个簇，结果可以画成一棵树状图（dendrogram），$K$ 取多少由你看完树之后再决定。

层次聚类有两种走法。一种叫凝聚的（agglomerative），自底向上，一开始把每个样本都当作独立的一簇，然后反复合并距离最近的两簇，直到全部合到一起。另一种叫分裂的（divisive），自顶向下，一开始所有样本同属一大簇，然后不断拆分。凝聚的做法用得更多，我们就说它。

凝聚层次聚类的关键，是两簇之间的距离怎么算。常用的有三种。第一种叫单连接（single linkage），取两簇之间最近那一对样本的距离。第二种叫全连接（complete linkage），取两簇之间最远那一对样本的距离。第三种叫平均连接（average linkage），把两簇所有样本两两之间的距离取平均。三者的脾气不同：单连接容易把长条状的簇串成一条链，全连接偏好紧凑的球形簇，平均连接比较折中。

层次聚类的结果用dendrogram来看最直观。横坐标是样本（或者已经合并的子簇），纵坐标是合并发生时的距离。每一次合并，就在两条支路汇合的高度上画一条横线。我们想分几个簇，就在合适的高度横着切一刀，刀下面的支路数就是簇数。比如想在距离为 $2.0$ 的地方切，刀口下面有3条支路，那就分成3簇。这种事后才定簇数的灵活，是层次聚类最讨人喜欢的地方。

层次聚类也有短板。最实际的一条是计算开销大，两两样本之间的距离矩阵就得占不少内存，样本量上一两千就要算挺久，跟K-means那种几万样本也能轻松跑的效率不在一个量级。所以大数据集上它常作为辅助探查手段，正式分堆还是交给K-means或者下面要讲的DBSCAN。

4.DBSCAN：按密度找簇，能认出噪声

K-means和层次聚类都依赖距离这个老物件，DBSCAN换了个角度，它按密度来分堆。说穿了，DBSCAN想找的是特征空间里那些样本特别密集的区域，稠密的地方连起来就是一簇，稀稀拉拉孤零零的样本则当作噪声丢掉。

DBSCAN有两个核心参数。一个是邻域半径 $\epsilon$（$\epsilon$ 是希腊字母epsilon，在这里专指邻域半径），另一个是最小点数 $m$（业内也叫minPts，表示一个核心点邻域里至少要落多少个样本）。对任意一个样本 $p$，我们看以 $p$ 为圆心、$\epsilon$ 为半径的圆，落在这个圆里的样本数就是 $p$ 的邻域密度。

DBSCAN把样本分成三类。第一类叫核心点，样本 $p$ 的 $\epsilon$ 邻域里样本数大于等于 $m$，说明它身处稠密区。第二类叫边界点，$p$ 自己的邻域不够密，可它落在某个核心点的邻域里，算是搭了便车被划进簇里。第三类叫噪声点，既不是核心点也不是边界点，游离在所有簇之外，算法会把它单独标出来。

簇是怎么长出来的呢，从一个核心点出发，把它邻域里所有的核心点都拉进来，再从这些新拉进来的核心点继续扩展，这么一路连下去，连成一片的样本就构成一簇。这个过程有点像一场靠口碑扩散的读书会，一个人带动身边几个朋友来，这几个朋友又各自带来自己的圈子，最后连成一片热闹的会场。而那些身边一个熟人都凑不齐、又没人愿意带他的，自然就成了看热闹的局外人，被划成噪声。

DBSCAN最大的长处，是能找出任意形状的簇，月牙形、同心圆、长条蜿蜒，它都能应对，这一点K-means是远远不及的。它还能自动把噪声挑出来，不用我们额外处理。可它也有自己的脾气。$\epsilon$ 和 $m$ 怎么定得费点心思，定大了所有点合成一簇，定小了每个点都是噪声。一种经验做法是画一张k-距离图（k-distance plot），把每个点到它第 $m$ 近邻居的距离从小到大排好画出来，曲线陡升的地方常常就是合适的 $\epsilon$。另外，DBSCAN在密度差异大的数据上表现一般，如果一份数据里既有很密的簇又有较稀的簇，它往往照顾不过来。

5.回到地面：客户分群与文章主题

讲到这，三种算法的脾气大概清楚了，我们再落到两个实际场景上看看。

第一个场景是客户分群做精准营销。一家做电商的公司，手里有每个用户的最近一次下单距今天数、月均下单次数、累计消费金额（业内合称RFM的三个维度，其中R是Recency最近一次消费距今、F是Frequency下单频次、M是Monetary累计消费金额）。做营销的同学先把这三个特征标准化，再用K-means跑一遍，令 $K=4$，往往会得到诸如高价值且活跃、低价值但稳定、高价值但有流失风险、低价值且沉默这么几个群体。对不同群体，发券力度、推送频次、文案风格都该不一样。一刀切地全员满减，往往把利润白白让给本来就会下单的人，效果很不划算。如果用户分布里有奇怪的弯月形状（某两类用户在特征上高度非线性），K-means可能就力不从心，这时不妨换DBSCAN试试，或者先做特征工程把分布拉顺。

第二个场景是文章按主题聚类。新闻门户每天进稿成千上万篇，编辑想快速看看今天都有哪些主题在热。常见做法是把每篇文章表示成向量（用TF-IDF或者更现代的文本embedding都行），再跑一遍聚类。层次聚类在这种探索性场景里格外顺手，dendrogram一张开，编辑能直接看出哪几篇讲的是同一件事，哪些是孤立的小众话题，分多细全凭手感切一刀。如果稿子里混了大量零散的水文，DBSCAN还能顺手把它们标成噪声，省去人工剔除的功夫。

我之前看过一本讲市场细分的书，里面有一句话记得很牢，大意是说真正的洞察，在于分完之后每一类能不能讲出一个具体的故事，至于把人分成几类，反倒只是手段。聚类算法只是工具，最后落地的，还是我们对每一群人的理解。

练习

Q1. K-means 反复做的两步是什么？它在最小化哪个目标函数？

第一步分配：每个样本划给离它最近的中心所在的簇。第二步更新：把每个簇里所有样本取平均得到新中心。两步交替直到中心不再变。它在最小化簇内平方和 $J=\sum_{k=1}^{K}\sum_{x_i\in C_k} d(x_i,\mu_k)^2$，也就是所有样本到各自簇心距离的平方和。

Q2. 用 K-means 时 $K$ 怎么定？肘部法的思路是什么？

因为聚类没有标签，$K$ 没有标准答案。肘部法让 $K$ 从小到大取值，分别跑一遍画出 $J$ 随 $K$ 变化的曲线，$K$ 越大 $J$ 越小（极端 $K=$样本数时 $J=0$）。我们找曲线从陡降变平缓的那个拐点（像胳膊的肘部），再往上加 $K$ 收益已经不大，拐点对应的 $K$ 通常就合适。

Q3. K-means、层次聚类、DBSCAN 各自最擅长什么形状的簇，分别有什么短板？

K-means 假设簇是球形且大小接近，怕长条形、月牙形数据，也怕异常值（均值会被拽歪），还要预先定 $K$。层次聚类不用先定簇数，结果是一棵 dendrogram 事后切刀，但计算开销大、样本上千就慢。DBSCAN 按密度找簇，能识别任意形状还能自动挑出噪声点，但 $\epsilon$、minPts 不好定，密度差异大的数据照顾不过来。