艺造记忆中的 k-means 算法

最近在准备面试，需要复习之前用过的算法，所以就趁机将一些算法改编成夸张荒诞的小故事，利于记忆。例如，k-means是一个有关城市规划的故事。

想象一个大城市突然停水。为了解决大家上厕所用水的问题，市政随机安置了 k 个可移动厕所。每天早上，人们先用手机搜索最近的可移动厕所，然后憋住屎尿飞奔过去。每天早上六点，人们集中在各自选定的移动公厕排队拉屎。

这时突然有人倡议：公厕的位置太不方便了，既然是可移动公厕，为什么我们不把它移到更好的地方去呢！（我们假设每个厕所都有这么一个聪明人。）大家一致认为这个提议不错，但是移动到哪里呢？为公平起见，移动到所有人住所的正中间（平均值），这样就不会有异议了。（也假设每个厕所都这样公平民主。）这个找“厕所 → 商讨 → 移动公厕”的过程每天上演，直到所有公厕的位置都满足了人们的需求。这就是最佳规划。

为了让故事更夸张，可以想象急着上厕所的人们憋得满脸通红，有憋不住的拉在裤子里，又不敢声张。也可以想象大家争论商讨的场景。想象那位倡议者聪明绝顶，随着他的头的转动，不断有人被晃得眯眼蹙眉。当然，少不了的还有厕所发出的臭味。切身实地地想象，调动所有感官，这样就能记住这个故事，多久也不会忘记了。从中解码出 k-means 算法是非常容易的。

虽然编这个故事只是为了方便记忆，但故事本身也很有启发意义。我们知道 k-means 算法最终将收敛到

$$ \underset{S}{\mathrm{argmin}} \sum_{i=1}^{k} \sum_{x \in S_i} \| x - \nu_i \|_2^2, $$

其中，$S_i$ 表示第 $i$ 个簇（cluster），$\mu_i$ 表示 $S_i$ 中点的均值。所以，这个故事反映出民主行为如何自发地产生最优方案，如何划分出自然社区，以最大化资源共享。