K-means

K-means 是最常见的一种聚类分析算法。直觉上来讲，它的步骤非常简单：

1. 随机选择K个聚类中心
2. 将每个数据点分类至离其最近的聚类中心
3. 根据第2步的分类，重新计算每一个分类的中心
4. 用第3步中的分类中心重新为所有数据点分类
5. 重复3，4两步直至收敛

在R中，K-means聚类算法的函数原型为kmeans(x, centers)（第5行），其中参数x的类型是matrix或data frame，代表一个数值型的数据集（如数据集不是数值型，则应选择一种合适的编码方法）；而参数centers则是无符号整型，是K-means中的K值，也即聚类的个数。

一般来说，我们可以通过比较聚类内部和聚类之间的相似程度，来作为衡量聚类效果的方法，从统计的角度来说也叫做方差分析。下面的wssplot函数比较了不同K值下的组内方差，这样我们就用画图的办法来确定最优的K值。

wssplot <- function(data, nc=15, seed=1234) {
    wss <- (nrow(data)-1) * sum(apply(data,2,var))
    for (i in 2:nc) {
        set.seed(seed)
        wss[i] <- sum(kmeans(data, centers=i)$withinss)}
        plot(1:nc, wss, type="b", xlab="Number of clusters", ylab="Within Group Variance")
}

因为K-means算法对聚类中心的初始值有一定敏感度，通过set.seed()确定随机数种子（这里设为1234），我们可以得到一致的聚类结果。

下面我们通过一个例子来学习如何在R中进行K-means聚类分析。

我们这里使用的意大利红酒数据集可以在UCI 机器学习数据库下载。在R里也可以通过rattle包来直接调取数据集。

data(wine, package="rattle")

head(wine)

	Type	Alcohol	Malic	Ash	Alcalinity	Magnesium	Phenols	Flavanoids	Nonflavanoids	Proanthocyanins	Color	Hue	Dilution	Proline
1	1	14.23	1.71	2.43	15.6	127	2.8	3.06	0.28	2.29	5.64	1.04	3.92	1065
2	1	13.2	1.78	2.14	11.2	100	2.65	2.76	0.26	1.28	4.38	1.05	3.4	1050
3	1	13.16	2.36	2.67	18.6	101	2.8	3.24	0.3	2.81	5.68	1.03	3.17	1185
4	1	14.37	1.95	2.5	16.8	113	3.85	3.49	0.24	2.18	7.8	0.86	3.45	1480
5	1	13.24	2.59	2.87	21	118	2.8	2.69	0.39	1.82	4.32	1.04	2.93	735
6	1	14.2	1.76	2.45	15.2	112	3.27	3.39	0.34	1.97	6.75	1.05	2.85	1450

这个数据集里包含了对每个红酒样本13种不同化学成分的测量结果，共计有178个样本。

为了保证可靠的方差分析，我们先用scale函数对样本特征的取值范围进行归一化。

df <- scale(wine[-1])

下面的图表现了不同K值下组内方差的结果。$x$轴代表聚类个数，$y$轴代表平均组内方差。我们可以看到，当聚类数目越大的时候，每组的组内方差就越小。

wssplot(df)

但显然K值并不是越大越好。K值越大，聚类结果的信息量越低。在这个数据集中，我们从上图可以看到，大概在K=3之前，组内方差下降比较明显，K=3之后组内方差下降放缓。看起来K=3是一个比较好的选择。

我们将K=3时的聚类结果保存在fit.km变量中。

fit.km <- kmeans(df, 3, nstart=25)

每一类的样本个数：

fit.km$size

1. 51
2. 65
3. 62

每一类的聚类中心：

round(fit.km$centers, 2)

	Alcohol	Malic	Ash	Alcalinity	Magnesium	Phenols	Flavanoids	Nonflavanoids	Proanthocyanins	Color	Hue	Dilution	Proline
1	0.16	0.87	0.19	0.52	-0.08	-0.98	-1.21	0.72	-0.78	0.94	-1.16	-1.29	-0.41
2	-0.92	-0.39	-0.49	0.17	-0.49	-0.08	0.02	-0.03	0.06	-0.9	0.46	0.27	-0.75
3	0.83	-0.3	0.36	-0.61	0.58	0.88	0.98	-0.56	0.58	0.17	0.47	0.78	1.12

注意我们在聚类之前，对特征进行了归一化，所以上表中是归一化之后的特征取值。下表则是在原范围内的取值：

round(aggregate(wine[-1], by=list(cluster=fit.km$cluster), mean), 2)

	cluster	Alcohol	Malic	Ash	Alcalinity	Magnesium	Phenols	Flavanoids	Nonflavanoids	Proanthocyanins	Color	Hue	Dilution	Proline
1	1	13.13	3.31	2.42	21.24	98.67	1.68	0.82	0.45	1.15	7.23	0.69	1.7	619.06
2	2	12.25	1.9	2.23	20.06	92.74	2.25	2.05	0.36	1.62	2.97	1.06	2.8	510.17
3	3	13.68	2	2.47	17.46	107.97	2.85	3	0.29	1.92	5.45	1.07	3.16	1100.23

聚类分析属于机器学习中的无监督学习，所以一般来说较难评估其效果。幸运的是，在原数据集中附带了样本的分类信息，也正好是3类，我们可以用混淆矩阵来评估聚类结果：

table(wine$Type, fit.km$cluster)

   
     1  2  3
  1  0  0 59
  2  3 65  3
  3 48  0  0

可以看到聚类结果较好，分别只有3个第2类的样本被错误归类到了第1类和第3类之中。