聚类分析简介及K-means在python中的使用

发布于 2021-08-30  1692 次阅读


聚类分析简介

聚类分析(cluster analysis)是一种常用的无监督学习算法,它试图将一组不带标签的样本(或变量)根据彼此之间的相似度划分成若干个类,使得相似的样本归到一个小的分类单位中,不相似的样本归到一个大的分类单位中,直到所有样本都划分完毕。通过这样的划分,我们可以从类中获取一些有价值的信息。但需要注意的是,由于这些样本并不带有标签,因此,对于各个类的含义需要使用者结合业务知识进行解读和定义。

聚类分析既能作为一个单独的过程,用来寻找一组不带标签的数据的内在结构和规律,也可以作为其他分类算法的前期工作,例如,我们可以先用聚类算法对一批产品的消费者进行分类,并给予业务上的定义,再基于这个人为定义的类型训练有监督的分类模型,用来对新用户进行预测分类。

通常,聚类对样本进行分类,但也可以对变量(属性)进行分类。对样本的分类称为Q型聚类,对变量的分类称为R型聚类。在实际应用场景中,聚类分析常用来对目标用户群体分类,把目标群体分为几个特征鲜明的细分群体,从而可以在运营活动中对这些不同群体开展差异化的服务。另外,聚类分析也常用来发现异常和孤立点,比如,在电子商务网站的购物交易中,通过聚类发现异常的有欺诈风险的交易行为。

聚类算法的类型

基于划分的方法

基于划分的方法基本思路如下:假设我们有一堆样本要聚类,想要的聚类效果是类内的样本足够近,类间的样本足够远。那么,首先需要决定样本要聚成多少类,选择一批聚类中心点或给出一个初始的分类,让样本按某种原则向中心点靠拢,对聚类中心不断迭代,直到迭代稳定或分类结果合理为止。

代表算法:K-means,K-Modes,K-Prototypes,CLARA。

基于层次的方法

基于层次的聚类方法可以分为凝聚法(自下往上)和分裂法(自上往下)两种。在凝聚方法中,我们首先将n个样本看作n个类,然后将最接近的两个样本合并为一个新类,得到 (n-1) 个类,合并后重新计算新类和其他所有类的距离,再次合并最接近的两个类,重复这个过程直到所有样本都归为一个类,整个过程类似于一个自底部向上合并成一棵树的过程。

分裂方法与凝聚方法相反,是自顶部向下分裂成一棵树的过程,即首先将所有样本看成一个类,将其不断分解以使其变成越来越小但个数越来越多的小类,直到所有对象均独自构成一个类,或满足一定终止条件为止。

代表算法:BIRCH算法,CURE算法,CHAMELEON算法

基于密度的方法

由于层次聚类算法和划分聚类算法往往只能发现凸型的聚类簇,为了弥补这一缺陷,发现各种任意形状的聚类簇,研究者开发出了基于密度的聚类算法。这种算法认为,在整个样本空间点中,各目标类簇是由一群稠密样本点组成的,而这些稠密样本点被低密度区域(噪声)分割,算法的目的就是要过滤低密度区域,发现稠密样本点。基于密度的聚类算法可以发现任意形状的聚类,这对于带有噪声点的数据起着重要的作用。

代表算法:DEBSCAN算法,GDBSCAN算法,OPTICS算法

基于网格的方法

该类方法采用网格作为算法的数据结构,将空间中每个样本都对应到网格中,有效提高了对样本的处理速度,关键在于设置合适的网格大小,若网格过大,所包含的样本过多,就会严重影响聚类质量。

代表算法:STING算法,WaveCluster算法

基于模型的聚类方法

该类方法假设目标的样本集由概率分布决定,因此每个都对应一个数学模型,聚类的过程是将样本集与某个模型拟合的过程,常见的基于统计和基于神经网络的方法。

代表算法:自组织映射神经网络算法,贝叶斯聚类

样本相似性的度量

进行聚类分析之前,首先要衡量样本之间的相似性,有了这个度量,我们才能按照一定方法将相对相似的样本归到一个类内。常用的相似性度量方法可以分为两大类:距离度量和关联度量。

  • 距离度量:欧氏距离、曼哈顿距离、切比雪夫距离、夹角余弦距离等,详见文章K近邻。
  • 关联衡量:常见的有匹配系数和相似比。如果样本的属性都是以名义变量来表示时,则两个样本之间的相似性可以用匹配系数或相似比来衡量。

匹配系数

第i个样本与第j个样本的匹配系数定义为:

S_{ij} = \frac{a+b}{m}

其中,a是i和j共同具有的属性数目,b是i和j共同不具有的属性数目,m是属性总数。显然,匹配系数越大,两个样本越相似。

相似比

第i个样本与第j个样本的相似比定义为:

{SR}_{ij} = \frac{a}{m-b}

其中,a是i和j共同具有的属性数目,m-b表示i或者j至少有一个样本拥有的属性数目。

K-Means聚类

K-Means聚类是最常用的一种聚类算法,他的思想很简单,对于给定的样本集和用户实现给定的k的个数,将数据集里所有的样本划分成K个簇,使得簇内的点尽量紧密地连在一起,簇间的距离尽量远。由于每个簇的中心点是该簇中所有点的均值计算而得,因此叫K-Means聚类。

算法过程

  1. 从所有样本中随机选择k个样本作为初始的聚类中心
  2. 计算每个样本到各个初始聚类中心的距离,将样本分配到距离最近的类中(通常使用欧氏距离)
  3. 将所有样本都分配完毕后,重新计算K个聚类的中心,新的聚类中心即是该簇所有点的平均值
  4. 重复步骤2~3
  5. 当聚类中心不再发生变化或者满足一定条件后,结束聚类

算法优缺点

  • 需要调节的参数只有聚类数目K
  • 对于大数据集,算法相对可伸缩和高效,计算的复杂度较低
  • K-Means聚类的结果很大程度上依赖于一开始随机选择的聚类中心,可能会导致最终而聚类结果只是局部最优。为了获得最理想的结果,通常需要多次运行K-Means算法,选择不同的随即初始聚类中心,观察结果。
  • K值需要事先指定,但一般很难选择,需要多次尝试(可以采用一些统计量来决定最佳的k值,如轮廓系数、戴维森堡丁指数等)
  • 对噪声点和异常值十分敏感
  • 只适用于数值类型的样本数据,不适用于名义类型的样本数据
from sklearn.cluster import KMeans
import matplotlib.pyplot as plt
import numpy as np

# 随机在平面三个区域构造样本集合
x1 = np.array([1,2,3,1,5,6,5,5,6,7,8,9,9])
x2 = np.array([1,3,2,2,8,6,7,6,7,1,2,1,3])
x = np.array(list(zip(x1, x2))).reshape(len(x1), 2)

# 样本集合可视化
plt.figure(figsize=(5,5))
plt.xlim([0, 10])
plt.ylim([0, 10])
plt.scatter(x1, x2)
plt.show()
kmeans_model = KMeans(n_clusters=3).fit(x)

colors = ['b', 'g', 'r']
markers = ['o', '^', '+']
for i, j in enumerate(kmeans_model.labels_):
    plt.plot(x1[i], x2[i], color=colors[j], marker=markers[j], ls='None')
plt.xlim([0,10])
plt.ylim([0,10])
plt.show()

扩展

K-Menas只能发现凸面形状的簇,如果簇的形状是非凸的,则效果很差。同时,其对噪声点敏感、只能处理数值型变量等缺陷也很明显。为了解决这些问题,K-Means还有很多变体。

K-Medoid聚类

K中心点(K-Medoid)算法可以解决K-Means中对噪声点敏感的问题。在K-Means中,我们对某类簇中所有样本点求平均值,作为该类簇的聚类中心,而当样本中有“噪点”(离群点)时,我们得到的聚类中心就会受到噪声的干扰,造成所得的聚类中心偏差过大,使得该类发生“畸变”。

为了解决这个问题,研究者们提出了新的质点选取方法。在K中心点算法中,每次迭代后的新聚类中心都是从该类的样本点中选取,选取的标准就是当该样本点成为新的聚类中心后能提高聚类质量,使得类簇更紧凑。该算法使用绝对误差来定义一个类簇的紧密程度。如果某样本成为中心点后,绝对误差能小于原中心点所造成的绝对误差,那么认为该样本点是可以取代原中心点的。即在一次迭代重计算类簇中心点时,我们选择绝对误差最小的那个样本点成为新的聚类中心。

K-Modes聚类

K-Modes算法可以看作K-Means算法在非数值属性样本上的扩展。它通过匹配系数度量样本之间的相关性,并且使用一个簇中每个属性出现频率最高的那个属性值作为该簇的代表属性值,以此为基础反复更新聚类中心,知道聚类结果稳定或达到一定条件。

K-Prototype聚类

K-Prototype算法通过结合K-Means和K-Modes,解决了具有混合属性的样本的聚类问题。度量样本之间相似性的方法是:数值属性采用K-Means方法得到P1,名义属性采用K-Modes方法得到P2,总距离 D=P_1+aP_2 ,其中a是用户设置的权重。如果分类属性不重要,则减少a,反之增加a。之后的迭代过程与K-Means类似。