Question

聚类分析中最广泛使用的算法为K-Means聚类分析算法。K-Means算法属于聚类分析中分类方法里较为经典的一种，由于该算法的效率高，所以在对大规模数据进行聚类时被广泛应用。目前，许多算法均围绕着该算法进行扩展和改进。在实际应用中，K-Means算法在商业上常用于客户价值分析。如识别客户价值应用的最广泛的RFM模型便是通过K-Means算法进行分类，最终得到不同特征的客户群。

1.算法原理

K-Means算法通过将样本划分为k个方差齐次的类来实现数据聚类。该算法需要指定划分的类的个数。它处理大数据的效果比较好，已经被广泛用于实际应用。

K-Means算法将数据集N中的n个样本划分成k个不相交的类，将这k个类用字母C表示，n个样本用字母X表示，每一个类都具有相应的中心u_i 。K-Means算法是一个迭代优化算法，最终使得下面的均方误差最小：

迭代算法具体描述如下：

1）适当选取k个类的初始中心。

2）在第k次的迭代中，对每一个样本x_j ，求其到每个中心u_i 的距离，将该样本归到距离最近的类中。

3）对于每个类c_i ，通过均值计算出其中心u_i 。

4）如果通过2）3）的迭代更新每个中心u_i 后，与更新前的值相差微小，则迭代终止，否则重复2）3）继续迭代。

K-Means算法的优点是简洁和快速，设t步算法结束，时间复杂度为O（nkt），一般有k<<n和t<<n，适合大规模的数据挖掘。但使用K-Means算法需要预先设定聚类数量k，而这个信息一般我们难以获取。

2.Python实现

K-Means的算法原理很简单，我建议读者自己动手实现K-Means算法（见上机实验1）。这里我们选择scikit-learn中的K-Means算法进行聚类实验。我们先看看代码清单8-1和K-Means算法的效果（见图8-1）：

代码清单8-1 K-Means实验

# -*- coding:utf-8 -*-
# K-Means实验
import numpy as np
import matplotlib.pyplot as plt
from sklearn.cluster import KMeans
from sklearn.datasets import make_blobs
plt.figure(figsize=(12, 12))
# 选取样本数量
n_samples = 1500
# 选取随机因子
random_state = 170
# 获取数据集
X, y = make_blobs(n_samples=n_samples, random_state=random_state)
# 聚类数量不正确时的效果
y_pred = KMeans(n_clusters=2, random_state=random_state).fit_predict(X)
plt.subplot(221)
plt.scatter(X[y_pred==0][:, 0], X[y_pred==0][:, 1], marker='x',color='b')
plt.scatter(X[y_pred==1][:, 0], X[y_pred==1][:, 1], marker='+',color='r')
plt.title("Incorrect Number of Blobs")
# 聚类数量正确时的效果
y_pred = KMeans(n_clusters=3, random_state=random_state).fit_predict(X)
plt.subplot(222)
plt.scatter(X[y_pred==0][:, 0], X[y_pred==0][:, 1], marker='x',color='b')
plt.scatter(X[y_pred==1][:, 0], X[y_pred==1][:, 1], marker='+',color='r')
plt.scatter(X[y_pred==2][:, 0], X[y_pred==2][:, 1], marker='1',color='m')
plt.title("Correct Number of Blobs")
# 类间的方差存在差异的效果
X_varied, y_varied = make_blobs(n_samples=n_samples,
                                    cluster_std=[1.0, 2.5, 0.5],
                                    random_state=random_state)
y_pred = KMeans(n_clusters=3, random_state=random_state).fit_predict(X_varied)
plt.subplot(223)
plt.scatter(X_varied[y_pred==0][:, 0], X_varied[y_pred==0][:, 1], marker= 'x',color='b')
plt.scatter(X_varied[y_pred==1][:, 0], X_varied[y_pred==1][:, 1], marker= '+',color='r')
plt.scatter(X_varied[y_pred==2][:, 0], X_varied[y_pred==2][:, 1], marker= '1',color='m')
plt.title("Unequal Variance")
# 类的规模差异较大的效果
X_filtered = np.vstack((X[y == 0][:500], X[y == 1][:100], X[y == 2][:10]))
y_pred = KMeans(n_clusters=3, random_state=random_state).fit_predict(X_filtered)
plt.subplot(224)
plt.scatter(X_filtered[y_pred==0][:, 0], X_filtered[y_pred==0][:, 1], marker= 'x',color='b')
plt.scatter(X_filtered[y_pred==1][:, 0], X_filtered[y_pred==1][:, 1], marker= '+',color='r')
plt.scatter(X_filtered[y_pred==2][:, 0], X_filtered[y_pred==2][:, 1], marker= '1',color='m')
plt.title("Unevenly Sized Blobs")
plt.show()

*代码详见：示例程序/code/8-1.py

图8-1 K-Means实验效果

我们实验采取的数据集是Scikit-learn中的make_blods^[1] 。使用Scikit-learn中K-Means算法的程序语句很简单，主要语句是：

# 设置分类器
clf  =  sklearn.cluster.Kmeans(n_cluster=8,random_state=None,…
)
# random_state参数是随机因子，使得初始中心是随机选取的
# 训练分类器并对样本的标签进行预测
y_pred = clf.fit_predict(X)

函数还有其他输入参数上面没有列出，读者可参考官方的函数介绍^[2] 。

样本X的格式可以是二维列表或NumPy数组，每行代表一个样本，每列代表一个特征，上面例子的样本数据是二维的，即每个样本都有两个特征。输出的y_pred是每个样本的预测分类。分析图8-1的效果，聚类数量的选取尤为重要，选取错误的聚类数量时将使得聚类效果不理想。K-Means算法处理类间方差差异大和类的规模差异大的样本时，都有很好的表现，可见K-Means算法具有一定的抗干扰能力。

[1] http://scikit-learn.org/stable/modules/generated/sklearn.datasets.make_blobs.html#sklearn.datasets.make_blobs

[2] http://scikit-learn.org/stable/modules/generated/sklearn.cluster.KMeans.html#sklearn.cluster.KMeans