本章内容
- k均值聚类算法
- 对聚类得到的簇进行后处理
- 二分k均值聚类算法
- 对地理位置进行聚类
在2000年和2004年的美国总统大选中，候选人的得票数比较接近或者说非常接近。任一候选人得到的普选票数的最大百分比为50.7%，而最小百分比为47.9%。如果1%的选民将手中的选票投向另外的候选人，那么选举结果就会截然不同。实际上，如果妥善加以引导与吸引，少部分选民就会转换立场。尽管这类选举者占的比例较低，但当候选人的选票接近时，这些人的立场无疑会对选举结果产生非常大的影响1。如何找出这类选民，以及如何在有限的预算下采取措施来吸引他们？答案就是聚类（Clustering）。
1. 对于微目标策略如何成功用于2004年的美国总统大选的细节，请参见 Fournier、Sosnik与Dowd合著的Applebee’s America（Simon & Schuster, 2006）一书。
接下来介绍如何通过聚类实现上述目标。首先，收集用户的信息，可以同时收集用户满意或不满意的信息，这是因为任何对用户重要的内容都可能影响用户的投票结果。然后，将这些信息输入到某个聚类算法中。接着，对聚类结果中的每一个簇（最好选择最大簇），精心构造能够吸引该簇选民的消息。最后，开展竞选活动并观察上述做法是否有效。
聚类是一种无监督的学习，它将相似的对象归到同一个簇中。它有点像全自动分类2。聚类方法几乎可以应用于所有对象，簇内的对象越相似，聚类的效果越好。本章要学习一种称为k-均值（K-mean）聚类的算法。之所以称之为k均值是因为它可以发现k个不同的簇，且每个簇的中心采用簇中所含值的均值计算而成。下面会逐步介绍该算法的更多细节。
2. 这里的自动意思是连类别体系都是自动构建的。——译者注
在介绍k均值算法之前，先讨论一下簇识别（cluster identification）。簇识别给出聚类结果的含义。假定有一些数据，现在将相似数据归到一起，簇识别会告诉我们这些簇到底都是些什么。聚类与分类的最大不同在于，分类的目标事先已知，而聚类则不一样。因为其产生的结果与分类相同，而只是类别没有预先定义，聚类有时也被称为无监督分类（unsupervised classification）。
聚类分析试图将相似对象归入同一簇，将不相似对象归到不同簇。相似这一概念取决于所选择的相似度计算方法。前面章节已经介绍了不同的相似度计算方法，后续章节它们会继续出现。到底使用哪种相似度计算方法取决于具体应用。
下面会构建k均值方法并观察其实际效果。接下来还会讨论简单k均值算法中的一些缺陷。为了解决其中的一些缺陷，可以通过后处理来产生更好的簇。接着会给出一个更有效的称为二分k均值（bisecting k-means）的聚类算法。本章的最后会给出一个实例，该实例应用二分k均值算法来寻找同时造访多个夜生活热点地区的最佳停车位。