#数据挖掘基础：聚类分析与 K-Means 算法详解

聚类是数据挖掘中的基本任务。聚类是将大量数据集中具有“相似”特征的数据点划分为统一类别，并最终生成多个类的方法。

聚类分析的基本思想是“物以类聚、人以群分”。大量的数据集中必然存在相似的数据点，基于这个假设，我们就可以将数据区分出来，并发现每个数据集（分类）的特征。

#聚类与分类的核心区别

与聚类概念类似的另一个概念是“分类”，实际上二者经常被混用，但它们在根本上是不同的：

• 学习方式不同：聚类是一种非监督式学习算法，而分类是监督式学习算法。
• 对源数据集要求不同：聚类不要求源数据集有标签，但分类需要标签用来做学习。
• 应用场景不同：聚类一般应用于做数据探索性分析，而分类更多地用于预测性分析。
• 解读结果不同：聚类算法的结果是将不同的数据集按照各自的典型特征分成不同类别，不同人对聚类的结果解读可能不同；而分类的结果却是一个固定值，不存在不同解读的情况。

聚类是一类成熟且经典的数据挖掘和机器学习算法。按照不同的维度划分，有很多经典的算法，如 K 均值（K-Means）、两步聚类、Kohonen 等，Python 甚至提供了 9 种聚类算法。本文将重点介绍最经典的 K-Means 算法。

#如何衡量数据之间的“相似度”？

聚类首先面临的一个问题是：如何衡量不同数据之间的“相似度”？大多数“相似度”都是基于距离计算的，距离计算主要可以分为以下两类：

#基于几何距离的“相似度”

为了方便计算，假设平面上两点 a(x1, y1) 与 b(x2, y2)：

• 欧式距离：a 和 b 平方和的开方（结果越大，相似度越高）。

  

• 曼哈顿距离：每个维度的距离之和（结果越大，相似度越高）。

  

• 切比雪夫距离：每个维度上距离的最大值（结果越大，相似度越高）。

  

#基于非几何距离的“相似度”

• 余弦距离：即两个向量的夹角。

  

  夹角余弦取值范围为 [-1, 1]。夹角余弦越大表示两个向量的夹角越小，越小表示两向量的夹角越大。当两个向量的方向重合时取最大值 1，方向完全相反时取最小值 -1。

• 汉明距离：两个等长字符串 s1 与 s2 之间的汉明距离，定义为将其中一个变为另外一个所需要作的最小替换次数。例如字符串“1111”与“1001”之间的汉明距离为 2。

• 杰卡德相似系数 (Jaccard similarity coefficient)：

  

• 相关系数 (Correlation coefficient)：

  

  相关系数是衡量随机变量 X 与 Y 相关程度的一种方法，取值范围是 [-1, 1]。绝对值越大，表明 X 与 Y 相关度越高。当 X 与 Y 线性相关时，相关系数取值为 1（正线性相关）或 -1（负线性相关）。

注：除了上述常用方法外，还可能包括马氏距离、闵可夫斯基距离、标准欧氏距离等。

#数据标准化：消除度量量级的差异

回到本文的主题 K-Means 算法。通过上述算法计算数据相似度（大多数选择欧氏距离）时，我们会发现：不同维度间由于度量单位的差异，计算的结果值会产生很大差异。

例如，假设 A 和 B 两个点分别具有两个维度：订单金额和转化率。订单金额的取值范围可能是 0 到无穷大，而转化率的取值为 0 到 1。因此，计算结果会由于订单金额的取值范围而“片面”夸大了这一维度的计算比重。

所以大多数情况下，如果存在这种度量量级的差异，我们会选择数据标准化，使不同维度落到相同的数据区间内然后再进行计算。

补充说明：何时不需要标准化？ 大多数情况下需要标准化，但这并不意味着所有场景都必须如此：

1. 原有的数据维度之间的量级差异不大，没有必要标准化。
2. 标准化后的结果在解读时会出现难以还原的问题。例如原本均值为 180，标准化后可能是 0.31，这个数据很难还原，只能进行相对其他维度的解读。

#经典算法：K-Means 深度解析

#K-Means 的计算步骤

1. 为每个聚类确定一个初始聚类中心，这样就有 K 个初始聚类中心。
2. 将样本集中的样本按照最小距离原则分配到最邻近聚类。
3. 使用每个聚类中的样本均值作为新的聚类中心。
4. 重复步骤 2 和 3，直到聚类中心不再变化。
5. 结束，得到 K 个聚类。

#K-Means 的优势

• 它是解决聚类问题的一种经典算法，简单、快速而且可以用于多种数据类型。
• 对处理大数据集，该算法是相对可伸缩和高效率的。
• 算法复杂度为 O(n*k*t)（其中 n 是所有对象的数目，k 是簇的数目，t 是迭代的次数）。通常 k << n 且 t << n。
• 算法尝试找出使平方误差函数值最小的 k 个划分。当结果簇是密集的，而簇与簇之间区别明显时，它的效果较好。

#K-Means 的局限性

• 既然基于均值计算，那么要求簇的平均值可以被定义和使用，此时字符串等非数值型数据则不适用。
• 第一步需要人为确定 K 值（要生成的簇的数目），对于不同的初始值 K，可能会导致不同结果。
• 应用数据集存在局限性，适用于球状或集中分布数据，不适用于特殊情况数据。如下面这种非球状的数据分布就无法正确分类：

  

• 它对于 “噪声”和孤立点数据是敏感的 ，少量的该类数据能够对平均值产生极大的影响。

#典型应用场景

• 图像压缩
• 大数据集的探索性分析 （例如：会员初步聚类）

#Python 实战：基于 scikit-learn 的 K-Means 演示

下面使用 Python 的机器学习库 scikit-learn 中的 KMeans 算法进行演示。

#代码实现与结果对比

本案例从 Python 自带数据集 iris 中调取数据进行聚类。其中有两个类别是通过 KMeans 算法获取的，为了便于比较效果，我们手动设置其中一个算法参数，使之表现“较差”，然后再与正常下的聚类模式以及原始真实数据集进行对比。

pythonCopy
1import numpy as np
2import matplotlib.pyplot as plt
3from mpl_toolkits.mplot3d import Axes3D
4from sklearn.cluster import KMeans
5from sklearn import datasets
6
7# 原始数据集
8np.random.seed(5)
9centers = [[1, 1], [-1, -1], [1, -1]]
10iris = datasets.load_iris()
11X = iris.data
12y = iris.target
13
14estimators = {
15    'k_means_iris_3': KMeans(n_clusters=3),
16    'k_means_iris_bad_init': KMeans(n_clusters=3, n_init=1, init='random')
17}
18
19# 输出两个模型的聚类结果
20fignum = 1
21for name, est in estimators.items():
22    fig = plt.figure(fignum, figsize=(4, 3))
23    plt.clf()
24    ax = Axes3D(fig, rect=[0, 0, .95, 1], elev=48, azim=134)
25    plt.cla()
26    plt.title(name)
27    est.fit(X)
28    labels = est.labels_
29    ax.scatter(X[:, 3], X[:, 0], X[:, 2], c=labels.astype(np.float))
30    ax.w_xaxis.set_ticklabels([])
31    ax.w_yaxis.set_ticklabels([])
32    ax.w_zaxis.set_ticklabels([])
33    ax.set_xlabel('Petal width')
34    ax.set_ylabel('Sepal length')
35    ax.set_zlabel('Petal length')
36    fignum = fignum + 1
37
38# 展示原始真实分类结果
39fig = plt.figure(fignum, figsize=(4, 3))
40plt.clf()
41ax = Axes3D(fig, rect=[0, 0, .95, 1], elev=48, azim=134)
42plt.cla()
43plt.title('ground truth')
44for name, label in [('Setosa', 0), ('Versicolour', 1), ('Virginica', 2)]:
45    ax.text3D(X[y == label, 3].mean(), 
46              X[y == label, 0].mean() + 1.5, 
47              X[y == label, 2].mean(), 
48              name,
49              horizontalalignment='center',
50              bbox=dict(alpha=.5, edgecolor='w', facecolor='w'))
51y = np.choose(y, [1, 2, 0]).astype(np.float)
52ax.scatter(X[:, 3], X[:, 0], X[:, 2], c=y)
53ax.w_xaxis.set_ticklabels([])
54ax.w_yaxis.set_ticklabels([])
55ax.w_zaxis.set_ticklabels([])
56ax.set_xlabel('Petal width')
57ax.set_ylabel('Sepal length')
58ax.set_zlabel('Petal length')
59
60plt.show()

上述代码运行结果如下：

由运行结果可知：左侧正常聚类下的结果与中间的真实分类类似，只有在交叉边界存在几个分类错误点；而右侧的算法，我们故意设置了随机指定质心以及只通过一次运算确定分类，导致分类结果在交叉边界处错误较多。

#KMeans 可配置的核心参数

pythonCopy
1class sklearn.cluster.KMeans(n_clusters=8, init='k-means++', n_init=10, max_iter=300, tol=0.0001, precompute_distances='auto', verbose=0, random_state=None, copy_x=True, n_jobs=1)  

#总结与业务落地建议

在实际业务中应用 K-Means 算法时，需要特别注意以下几点：

• 数据预处理必不可少：尤其是异常点的剔除和数据的标准化工作，直接决定了聚类的质量。
• 合理指定 K 值：可以通过对比不同 K 值下的数据聚类结果来寻找最优解。通常结果类别不能太多，否则就失去了聚类的意义。
• 关注样本量均衡：每一个类别的数据流量应大体均等，过少样本量的类别很难具备实际业务价值。
• 确保业务可解释性：聚类后的每个类别都应有其对应的特征值，不同类别之间的特征值差异越大，才越容易进行业务解读和区分。