「机器学习算法的数学解析与Python实现」K-means聚类算法

本章讲解无监督学习中最为经典的问题——聚类问题。

用投票表决实现“物以类聚”

标注数据不足始终是监督学习的一大问题,因此业界逐渐开始探索将监督学习和无监督学习结合在一起,首先通过聚类等无监督学习的算法处理数据,通过各种假设和结合聚类结果来给数据打标签,然后再把这些数据喂入监督学习算法进行建模训练,使得未经人工标注的数据,也能够起到提高监督学习模型预测准确度的效果。这种集两家之长的方法称为半监督学习

K-means聚类算法重点关注:

  • 聚类问题
  • 质心
  • 多数表决

聚类问题的关键在于满足什么样条件的“物”才会作为同一类聚在一起,所以基本原则就是找相似。所谓的分类就是找相同点,相同点多了就是同一类,不同点多了就不是同一类。

样本数据集通过聚类算法最终会聚成一个个“类”,这些类就称簇(Cluster)。聚类问题就是把一个个样本数据点汇聚成一个个簇,核心思想就是“合并同类项”。

问题一:应该会聚成多少个簇?

对于分类问题,有多少个类是已知条件,但对于聚类问题,有多少个簇是未知条件。而选择不同的簇个数,可能会产生不同的聚类结果。

「机器学习算法的数学解析与Python实现」K-means聚类算法

决定多少个簇无法有两种思路:

  1. 预先设定有多少个簇;
  2. 在聚类的过程中形成。

不同的聚类算法采取了不同的思路,主要分为:

  • 划分法
  • 层次法
  • 密度法
  • 网格法

划分法是最简单的聚类算法,预先假设待聚类的数据能够划分为K个簇,在这个假设基础上再采取各种手段完成聚类,K-means就采用了这种方法。

问题二:怎样量化相似?

可以参考KNN,使用“距离”作为度量工具。

问题三:如何进行多数表决?

在监督学习的KNN算法中,待分类点可以根据其邻居的类别来进行多数表决,而K-means最大的问题就在于每个样本点都是类别未知的。

为了解决这个问题,K-means算法创造了K个中心点,称为质心

K-means聚类的算法原理

基本思路

K-means的聚类过程,可以看成是不断寻找簇的质心的过程,这个过程从随机设定K个质心开始,直到找到K个真正质心为止。

K-means聚类的大概步骤:

  1. 随机设定K个质心,对于其他数据点来说,距离哪个质心近就归为哪个簇,因此可以形成K个簇。
  2. 对于第一步聚成的K个簇,重新计算质心,K-means使用簇内所有样本点的均值作为新质心的坐标值。
  3. 根据新的质心,重新划分K个簇,以此类推,直至质心不再变化,完成聚类。

数学解析

1.找质心过程的本质

让簇内样本点到达各自质心的距离的总和最小,能够满足这个“最小”的K个质心,就是我们要找的质心。

2.距离的度量

欧几里得距离的数学表达式如下:

\[d_2(x,y) = \sqrt{\sum_{i=1}^n (x_i -y_i)^2} \]

假设第 \(j\) 个簇内有 \(n\) 个数据点,根据上式,该簇的所有样本点到质心 \(\mu_j\) 的距离总和为:

\[\sum_{i=0}^n \|x_i-\mu_j\|^2 \]

为什么表达式这样写?符号啥意思??

我们的最终目标是使得集合 \(C\) 内的每个簇内的样本点到质心的距离总和最小:

\[\sum_{i=0}^n \min_{\mu_j \in C} \|x_i-\mu_j\|^2 \]

具体步骤

K-means聚类算法信息表

「机器学习算法的数学解析与Python实现」K-means聚类算法

K-means具体步骤如下:

graph TD A(随机选取K个质心) --> B[计算样本点到质心的距离] B --> C[分簇: 样本点距离哪个质心最近, 就划分为哪个簇] C --> D[重选质心: 计算簇内的所有样本点的均值作为新的质心] D --> E{质心是否改变} E --是--> B E --否--> F(结束)

在Python中使用K-means聚类算法

在sklearn中,聚类算法都在cluster类库下,本文介绍的K-means算法可以通过KMeans类调用,K可通过参数n_clusters设置。

使用方法如下:

import matplotlib.pyplot as plt
# 从sklearn中导入K-means聚类算法
from sklearn.cluster import KMeans
# 导入聚类数据生成工具
from sklearn.datasets import make_blobs

# 生成聚类测试数据
n_samples = 1500  # 样本点个数
X, y = make_blobs(n_samples=n_samples)

# 聚类,k=3
y_pred = KMeans(n_clusters=3).fit_predict(X)

# 用点状图显示聚类效果
plt.scatter(X[:, 0], X[:, 1], c=y_pred)

聚类结果效果图:

「机器学习算法的数学解析与Python实现」K-means聚类算法

使用make_blobs生成的X默认为两个特征维度:

array([[ 5.94517357,  6.30431031],
       [-2.41766292, -6.46417324],
       [ 2.6726998 ,  7.1979758 ],
       ...,
       [-2.30785925, -7.36744246],
       [ 6.20006451,  6.16699149],
       [ 5.2868925 ,  7.10342902]])

而y实际上是样本点的标签,所以生成的其实是有标签的样本点。

array([2, 0, 2, ..., 0, 2, 2])

K-means聚类算法的使用场景

K-means算法原理简单,运算简单。最明显的问题是需要先验地设置“K”,同时由于需要求均值,所以要求数据集的维度属性类型应该是数值类型。

K-means聚类算法特点

「机器学习算法的数学解析与Python实现」K-means聚类算法

上一篇:k-means分群


下一篇:2021-09-18