首页 » 机器学习实战 » 机器学习实战全文在线阅读

《机器学习实战》第10章 利用K-均值聚类算法对未标注数据分组

关灯直达底部

本章内容

  • 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均值算法来寻找同时造访多个夜生活热点地区的最佳停车位。