引言
在2000年和2004年的美国总统大选中，候选人的得票数比较接近或者说非常接近。任一候选适人得到的普选票数的最大百分比为50.7％，而最小百分比为47.9％。如果1％的选民将手中的选票投向另外的候选人，那么选举结果就会截然不同。实际上，如果妥善加以引导与吸引，少部分选民就会转换立场。尽管这类选举者占的比例较低但当候选人的选票接近时，这些人的立场无疑会对选举结果产生非常大的影响。如何找出这类选民，以及如何在有限的预算下采取措施来吸引他们？答案就是聚类（ Clustering）。
接下来介绍如何通过聚类实现上述目标。首先，收集用户的信息，可以同时收集用户满意或不满意的信息，这是因为任何对用户重要的内容都可能影响用户的投票结果。然后，将这些信息输入到某个聚类算法中。接着，对聚类结果中的每一个簇（最好选择最大簇），精心构造能够吸引该簇选民的消息。最后，开展竞选活动并观察上述做法是否有效。
K – 均值聚类算法简介
聚类是一种无监督的学习，它将相似的对象归到同一个簇中。它有点像全自动分类。聚类方法几乎可以应用于所有对象，簇内的对象越相似，聚类的效果越好。本文介绍一种称为K均值（k – means）聚类的算法。之所以称之为K-值是因为它可以发现k个不同的簇，且每个簇的中心采用簇中所含值的均值计算而成。下面会逐步介绍该算法的更多细节。
在介绍K – 均值算法之前，先讨论一下簇识别（ cluster identificatio）簇识别给出聚类结果的含义。假定有一些数据，现在将相似数据归到一起，簇识别会告诉我们这些簇到底都是些什么。聚类与分类的最大不同在于，分类的目标事先已知，而聚类则不一样。因为其产生的结果与分类相同，而只是类别没有预先定义聚类有时也被称为无监督分类（unsupervised classification ）。聚类分析试图将相似对象归入同一簇，将不相似对象归到不同簇。相似这一概念取决于所选择的相似度计算方法。
算法特点
- 优点：容易实现。
- 候选缺点：可能收敛到局部最小值，在大规模数据集上收敛较慢。
- 适用数据类型：数值型数据。
算法核心思想
K – 均值是发现给定数据集的k个簇的算法。簇个数k是用户给定的，每一个簇通过其质心，即簇中所有点的中心来描述。
K均值算法的工作流程是这样的。首先，随机确定k个初始点作为质心。然后将数据集中的每个点分配到一个簇中，具体来讲，为每个点找距其最近的质心，并将其分配给该质心所对应的簇。这一步完成之后，每个簇的质心更新为该簇所有点的平均值。
上述过程的伪代码表示如下：
创建k个点作为起始质心（经常是随机选择）
当任意一个点的簇分配结果发生改变时
对数据集中的每个数据点
对每个质心
计算质心与数据点之间的距离
将数据点分配到距其最近的簇
对每一个簇，计算簇中所有点的均值并将均值作为质心K均值聚类的一般流程
- 收集数据：使用任意方法。
- 准备数据：需要数值型数据来计算距离，也可以将标称型数据映射为二值型数据再用于距离计算。
- 分析数据：使用任意方法。
- 训练算法：不适用于无监督学习，即无监督学习没有训练过程。
- 测试算法：应用聚类算法、观察结果可以使用量化的误差指标如误差平方和来评价算法的结果。
- 使用算法：可以用于所希望的任何应用。通常情况下，簇质心可以代表整个簇的数据来做出决策。
算法具体实现
上面提到“最近”质心的说法，意味着需要进行某种距离计算。读者可以使用所喜欢的任意距离度量方法。数据集上K均值算法的性能会受到所选距离计算方法的影响。下面给出K-均值算法的代码实现 kMeans。首先创建一个名为py的文件，然后将下面程序清单中的代码添加到文件中。
# 加载数据
def loadDataSet(fileName):
dataMat = []
fr = open(fileName)
for line in fr.readlines():
curLine = line.strip(). split("\t")
fltLine = map(float,curLine)
dataMat.append(fltLine)
return dataMat
# 计算欧氏距离
def distEclud(vecA, vecB):
return np.sqrt(np.sum(np.power(vecA - vecB, 2)))
# 随机初始化K个质心(质心满足数据边界之内)
def randCent(dataSet, k):
n = np.shape(dataSet)[1]
centroids = np.mat(np.zeros((k, n)))
for j in range(n):
minJ = np.min(dataSet[:, j])
rangeJ = float(max(dataSet[:, j])-minJ)
centroids[:, j] = minJ+rangeJ*np.random.rand(k, 1)
return centroids
上述代码中包含几个K-均值算法中要用到的辅助函数。第一个函数 loadDataSet()为加载数据函数，它将文本文件导入到一个列表中文本文件每一行为tab分隔的浮点数每一个列表会被添加到 dataMat中，最后返回 dataMat该返回值是一个包含许多其他列表的列表。这种格式可以很容易将很多值封装到矩阵中。
下一个函数 distEclud()计算两个向量的欧式距离。这是本文使用的距离函数，也可以使用其他距离函数。
最后一个函数是 randCent()，该函数为给定数据集构建一个包含k个随机质心的集合。随机质心必须要在整个数据集的边界之内，这可以通过找到数据集每一维的最小和最大值来完成。然后生成0到1.0之间的随机数并通过取值范围和最小值，以便确保随机点在数据的边界之内。
所有支持函数正常运行之后，就可以准备实现完整的K均值算法了。该算法会创建k个质心，然后将每个点分配到最近的质心，再重新计算质心。这个过程重复数次，直到数据点的簇分配结不再改变为止。
# Kmeans聚类算法
def kMeans(dataSet, k, distMeas=distEclud, createCent=randCent):
m = np.shape(dataSet)[0]
clusterAssment = np.mat(np.zeros((m, 2)))
centroids = createCent(dataSet, k)
clusterChanged = True
while clusterChanged:
clusterChanged = False
for i in range(m):
minDist = np.inf
minIndex = -1
for j in range(k):
distJI = distMeas(centroids[j, :], dataSet[i, :])
if distJI < minDist:
minDist = distJI
minIndex = j
if clusterAssment[i, 0] != minIndex:
clusterChanged = True
clusterAssment[i, :] = minIndex, minDist**2
# print(centroids)
for cent in range(k):
ptsInClust = dataSet[np.nonzero
(clusterAssment[:, 0].A == cent)[0]]
if len(ptsInClust) != 0:
centroids[cent, :] = np.mean(ptsInClust, axis=0)
return centroids, clusterAssment
上述清单给出了均值算法。 kMeans()函数接受4个输入参数。只有数据集及簇的数目是必选参数，而用来计算距离和创建初始质心的函数都是可选的。 kMeans()函数一开始确定数据集中数据点的总数，然后创建一个矩阵来存储每个点的簇分配结果。簇分配结果矩阵 clusterAssment包含两列：一列记录簇索引值，第二列存储误差。这里的误差是指当前点到簇质心的距离，后会使用该误差来评价聚类的效果。
按照上述方式（即计算质心 – 分配 – 重新计算）反复迭代直到所有数据点的簇分配结果不再改变为止。程序中可以创建一个标志变量 clusterChanged，如果该值为True，则继续迭代。上述迭代使用 while循环来实现。接下来遍历所有数据找到距离每个点最近的质心，这可以通过对每个点遍历所有质心并计算点到每个质心的距离来完成。计算距离是使用 distMeas参数给出的距离函数，默认距离函数是 distEclud()。如果任一点的簇分配结果发生改变，则更新 clusterChanged标志。
最后，遍历所有质心并更新它们的取值。具体实现步骤如下：首先通过数组过滤来获得给定簇的所有点；然后计算所有点的均值，选项axis＝0表示沿矩阵的列方向进行均值计算；最后，程序返回所有的类质心与点分配结果。