LionKing数据科学专栏

购买普通会员高级会员可以解锁网站精华内容且享受VIP服务的优惠

想要查看更多数据科学相关的内容请关注我们的微信公众号知乎专栏

聚类分析(cluster analysis)

聚类分析介绍

聚类分析的目标是将数据进行分组,使得类似的数据在同一个聚类(cluster)中。

如上图中的二维数据,我们可以将数据分为红、绿、蓝三个聚类/组,使得每个聚类的数据尽可能的接近,而不同聚类的数据距离较远。

聚类分析没有明确的目标,不同的算法对数据采取不同的建模方式。聚类算法主要有以下类别:

如果每个数据必须恰好包含在一个聚类中,则算法为硬聚类(hard clustering)算法;否则为软聚类(soft clustering)算法。

聚类算法在科学发现和商业分析中均有应用,以下为其部分应用:

本文介绍最常用的k-means算法。

k-means算法原理

k-means将数据分为$k$个聚类/组,其中每个聚类有一个聚类中心(centroid),而每个数据被分为距离最近的聚类中心所在的聚类。

k-means假定数据的每一个特征都是连续型特征,即$x_1, \ldots, x_n \in \mathbb{R}^{p}$。

我们希望寻找$k$个聚类中心$\mu_1, \ldots, \mu_k \in \mathbb{R}^{p}$,并且将每个数据$x_i$归类为$\mu_{g_i}, g_i \in \{1, \ldots, k\}$所在的类,使得组内方差(within-cluster sum of squares)最小化:

$$\sum_{i=1}^{n}\|x_i - \mu_{g_i}\|_2^2$$

上图中,我们将$x_1, \ldots, x_7$分为了聚类中心$\mu_1$所在的聚类,$x_8, \ldots, x_{11}$分为了聚类中心$\mu_2$所在的聚类,$x_{12}, x_{13}, x_{14}$分为了聚类中心$\mu_3$所在的聚类。

算法

最常用的初始化方法为均匀地随机选取$k$个原始数据作为聚类中心,更好的初始化方法为K-means++算法的初始化步骤。其大致思路是每次尽可能地选取距离已有聚类中心最远的数据作为新的聚类中心。

k-means算法的结果不能保证是全局最优解,且全局最优解的计算复杂度很高。因此实际中往往进行若干次随机初始化,对每一个初始化分别进行上述迭代,并选取组内方差最小的结果作为最终输出。

下面的动画来自维基百科

可以看到,最初我们选择了三个聚类中心,在接下来的每次迭代中,我们将数据划分到最近的聚类中心所在的聚类中,并将聚类中心更新为所有该聚类的数据的几何重心(centroid)。

$k$的选择

类似于主成分分析中$k$的选择,一般来说$k$越大时,组内方差越小,但是过于大的$k$会造成信息的丢失。

为了选择合适的$k$,可以将数据可视化并且进行人工判断。但是这种方式只有在数据的维数$p$较小时有效。

更常见的方法是对于不同的$k$运行k-means算法,将每个$k$得到的组内方差画出一个折线图,选取一个$k_0$,使得随着$k$超过$k_0$,组内方差的降低不再显著。

由于该方法很像是在折线图中寻找肘部,这种方法称为肘点图法(Elbow method),除了对于k-means算法,也可以用于其他的聚类算法。

此外,也可以依据Silhouette分值,选择该分值较高的$k$。详细解释可以参考sklearn官方文档

Python实现

我们首先看一个二维平面上数据的聚类的例子。

import numpy as np
from sklearn import cluster
from matplotlib import pyplot as plt
from matplotlib import cm

# 生成数据
np.random.seed(10)
k_true = 5
R = 5.0
n = 1000
centers_x = [R * np.cos(np.pi * 2.0 / k_true * i) for i in range(k_true)]
centers_y = [R * np.sin(np.pi * 2.0 / k_true * i) for i in range(k_true)]
X = np.zeros((n, 2))
for i in range(n):
    centroid_id = np.random.randint(k_true)
    X[i][0] = centers_x[centroid_id] + np.random.normal()
    X[i][1] = centers_y[centroid_id] + np.random.normal()

# 创建运行k-means算法对象
kmeans_fitter = cluster.KMeans(n_clusters=k_true, random_state=0)
# 运行k-means算法
kmeans_fitter.fit(X)
# 得到每个数据所在的组
kmeans_grp = kmeans_fitter.labels_
# 得到每个聚类的中心
kmeans_centroids = kmeans_fitter.cluster_centers_

colors = cm.rainbow(np.linspace(0, 1, k_true))
plt.close()
plt.scatter(X[:, 0], X[:, 1], s=1, color=colors[kmeans_grp])
plt.scatter(kmeans_centroids[:, 0], kmeans_centroids[:, 1], color='black', marker='X')
plt.savefig('k-means-data.png')


ks = np.arange(1, 10)
var = []
for k in ks:
    fitter = cluster.KMeans(n_clusters=k, random_state=0)
    fitter.fit(X)
    # 得到组内方差
    var.append(fitter.inertia_)

plt.close()
plt.plot(ks, var, '.-')
plt.xlabel('k')
plt.ylabel('within-cluster sum of squares')
plt.savefig('k-means-elbow.png')
        

聚类结果见下图,每个颜色代表一个聚类,X代表各个聚类中心。

肘点图如下,可以看到在$k$超过5时,组内方差的降低非常小。

我们再来看一个用k-means算法进行图像分割的例子。我们的思路是将图片的每个像素点看作三维空间中的点,其中三个坐标分别为像素的RGB值。

对像素点进行聚类后,我们可以认为每个聚类代表了图像的一个部分。例如$k = 2$对应了计算机视觉领域的前景检测(foreground detection),可以将图像分为前景(foreground)和后景(background)两部分。

from sklearn import cluster
from matplotlib import pyplot as plt
from matplotlib import image

# 读取图片
img = image.imread('k-means-test.png')
# 将图片转换为像素的向量
orig_shape = img.shape
img = img.reshape((-1, 3))
plt.close()
plt.axis('off')
plt.imshow(img.reshape(orig_shape))
plt.savefig('orig.png')

for k in range(2, 10):
  # 创建运行k-means算法对象
  kmeans_fitter = cluster.KMeans(n_clusters=k)
  # 运行k-means算法
  kmeans_fitter.fit(img)
  # 得到每个像素所在的组
  kmeans_grp = kmeans_fitter.labels_
  # 得到每个聚类的中心
  kmeans_centroids = kmeans_fitter.cluster_centers_
  # 将每个像素替换为聚类中心
  result = kmeans_centroids[kmeans_grp]
  # 显示图片
  plt.close()
  plt.axis('off')
  plt.imshow(result.reshape(orig_shape))
  plt.savefig('transformed-%s.png' % (k, ))
	

原图如下:

将像素分为2类结果如下:

将像素分为4类结果如下:

将像素分为6类结果如下:

将像素分为8类结果如下:

可以看到将数据分为8类时,已经保留了图片的很多信息。因此,也可以使用k-means算法对数据进行压缩。

常见面试问题

Q:简述k-means算法的原理。

Q:k-means算法中的$k$应如何选择?

Q:k-means算法有哪些缺点?

更多机器学习相关问题见本网站论坛机器学习理论版面机器学习实践版面

更多面试问题见面试真题汇总

想要查看更多数据科学相关的内容请关注我们的微信公众号知乎专栏