1. 问题

人类有个很有趣的现象，一群人在一起，过一段时间就会自发的形成一个个的小团体。好像我们很擅长寻找和自己气质接近的同类。其实不只是人类，数据也有类似情况，这就是聚类(Clustering)的意义所在。

今天我们就一起来了解下聚类中最简单的一个算法，k 均值法(k means)。

2. 分析

乍一看，k means 和之前我们提到过得 K-nearest Neighbors 很像。其实这是完全不同的两种算法。K-nearest Neighbors 是用临近的数据推测新数据的属性，而 k means 则是在一堆没有属性的数据里面，把它们分成几个簇(Cluster)。

咱用穿衣服举个例子。Alice 正在和 Amy 逛街，有位大妈和她俩打招呼，原来大妈想给自己女儿买条裙子，但女儿又恰好不在，瞅着 Alice 和 Amy 的身材和女儿差不多，就让 Alice 帮试一下好看看效果。这就是 K-nearest Neighbors，用和女儿类似的 Alice ，来推测裙子是不是适合女儿。

Bob 是一家衬衫工厂老板，正在琢磨生产计划。按照惯例，他把人群分为了S码、M码和L码三个类别。但总有人发邮件抱怨，买M码的偏小，买L码的偏大。于是他决定做个市场调查，看能不能把分类再细化一下，比如分成S码、M码、ML码和L码四个类。这就是K means，把没有特定属性的人群，按照某种特征划分成不同的簇。

k means的实现，用的是使其平均距离最小化。我们定义畸变函数(Distortion function)为

$J = \frac{1}{m}\sum_{i=1}^m\parallel x^{(i)} - \mu_{c^{(i)}}\parallel ^2$

目的便是通过改变形心(Centroid)的改变，使得畸变函数最小化。

上面公式中

$x^{(i)}$ ：第 i 个数据；
$\mu_{c^{(i)}}$ ：第i 个数据对应的形心；

这么讲有点抽象。坊间对 k means 有一个更形象的解释，叫牧师布道

有四个牧师去郊区布道，一开始牧师们随意选了几个布道点，并且把这几个布道点的情况公告给了郊区所有的村民，于是每个村民到离自己家最近的布道点去听课。
听课之后，大家觉得距离太远了，于是每个牧师统计了一下自己的课上所有的村民的地址，搬到了所有地址的中心地带，并且在海报上更新了自己的布道点的位置。
牧师每一次移动不可能离所有人都更近，有的人发现A牧师移动以后自己还不如去B牧师处听课更近，于是每个村民又去了离自己最近的布道点……
就这样，牧师每个礼拜更新自己的位置，村民根据自己的情况选择布道点，最终稳定了下来。

这样，村民最后也就被分成了4个簇。

k means方法中，k 是一个关键参数。选择 k 通常可以从以下几个角度出发。

一个是从数据出发。比如通过观察碎石图(scree plot)

image

很显然，k 选择2或者3都可以。

有时候数据本身未必能像上图所示有很明显的结果，比如下面这张图

image

这时候，更多的就需要我们从业务本身出发来思考。

以 Bob 的衬衫厂为例，Bob 更多需要考虑的，可能是如果选择 k = 4，需要新投入多少设备？能有多少收益？这些是单纯的机器学习没法提供给我们的。

所以说，生活本身最重要。

3. 实现

我们用一组二维数据做个测试。之所以用二维，主要是为了方便打印。高维数据也可以用 K means 方法做聚类。

import numpy as np
from sklearn.cluster import KMeans
import matplotlib.pyplot as plt

X = np.loadtxt('X.txt', delimiter=' ')
kmeans = KMeans(n_clusters=3, random_state=0).fit(X)
plt.scatter(X[:, 0], X[:, 1], c=kmeans.labels_)

测试结果

image

完美分类，YOHOO~

4. 总结

今天我们大致介绍了k means的原理及实现。同性成簇，感觉是万物规律。所以到底为了联盟，还是为了部落，需要好好想清楚。

相关代码均已上传到 Github(https://github.com/jetorz/Data2Science)，欢迎标记 Star。

5. 交流

独学而无友则孤陋寡闻。现有「数据与统计科学」微信交流群，内有数据行业资深从业人员、海外博士、硕士等，欢迎对数据科学、数据分析、机器学习、人工智能有兴趣的朋友加入，一起学习讨论。

大家可以扫描下面二维码，添加荔姐微信邀请加入，暗号：机器学习加群。

image

6. 扩展

6.1. 延伸阅读

6.2. 参考文献

G. James, D. Witten, T. Hastie R. Tibshirani, An introduction to statistical learning: with applications in R. New York: Springer, 2013.
T. Hastie, R. Tibshirani, J. H. Friedman, The elements of statistical learning: data mining, inference, and prediction, 2nd ed. New York, NY: Springer, 2009.
W. Härdle, L. Simar, Applied multivariate statistical analysis, 3rd ed. Heidelberg ; New York: Springer, 2012.
周志华, 机器学习 = Machine learning. 北京: 清华大学出版社, 2016.

image