当前位置：首页 > news >正文

机器学习自学笔记——聚类

news 文章来源：https://blog.csdn.net/m0_61787307/article/details/129507293 2025/1/11 7:02:14

聚类的基本概念

聚类，顾名思义，就是将一个数据集中各个样本点聚集成不同的“类”。每个类中的样本点都有某些相似的特征。比如图书馆中，会把成百上千的书分成不同的类别：科普书、漫画书、科幻书等等，方便人们查找。每一种类别的书都有相似之处：比如科普书类别中的书基本上都是普及一些科学知识，这就是他们的相似之处。而聚类可以理解为“将一堆图书分为不同的类别的过程”。

这里不得不说明一下“聚类”和“分类”的区别：

聚类是刚创立一个图书馆，通过各种渠道获得了一堆图书，事先我不知道可以分为哪些类，但是随着分类的进行，逐渐被分为不同的类。这是一种无监督学习。
分类是现在有一堆图书，要将其按类别放入图书馆的书架上，这些类别都是事先确定的，比如科普类、文学类、历史类等等，按类别放入即可。这是一种监督学习。

数据的聚类方法有很多，如下图：

请添加图片描述

本文之后会主要介绍k-means(k均值聚类)和层次聚类算法中的聚合聚类。

上面这些聚类算法有一些共同步骤：

数据准备：对数据进行特征标准化和降维处理。就像将事先准备好的一本本图书一本本堆叠规整放好
特征选择/提取：从最初的特征中选择最有效的特征，进行转换形成新的突出特征，并将其存储在向量中。就像将图书中十分破烂或者不良的剔除，并存储在专门存储图书的地方
进行聚类：基于某种距离函数进行相似度度量，并形成聚簇。就像按照某种规律（书名出现相同的字）将图书之间归类（都出现百科归一类、都出现秋天归一类······）
结果评估：对聚类的分类结果进行评估，判断聚类进行的优劣。就像将图书聚类完之后，抽取图书并翻看内容来判断其类别是否正确

相似度度量

在上面的聚类算法的步骤中，“进行聚类”这一步骤中出现了“相似度度量”，这也是聚类算法中最重要的点。比如像我用图书的例子进行类比时，在“进行聚类”这一步说得就十分不清楚，因为我没法找到一个合适的标准去衡量图书之间的相似程度。

在聚类算法中，我们会通过计算“距离”去衡量相似度。当我们将特征数字化之后，特征之间是否相似也就是特征数字之间是否大小接近。需要注意的是，这里的“距离”是广义距离，并不仅仅是我们通常理解的 $d_1-d_2$ 这种距离。下面我们来看几种比较常见的距离：

1、闵可夫斯基距离

① 欧式距离

欧式距离就是我们最常见的距离度量方法，就是两点之间的最短距离。

假设两个点的坐标分别为 $x_1(x_{11}，x_{12}，x_{13}，···，x_{1n})$ ， $x_2(x_{21}，x_{22}，x_{23}，···，x_{2n})$ ，（我们也称 $x_{11}，x_{12}，x_{13}，···，x_{1n}$ 为 $x_1$ 的特征）则这两个点的欧式距离为：
$L(x1,x2)=∑i=1n(x1i−x2i)2L(x_1,x_2)=\sqrt{\sum_{i=1}^n{(x_{1i}-x_{2i})^2}}$
② 曼哈顿距离

假设两个点的坐标分别为 $x_1(x_{11}，x_{12}，x_{13}，···，x_{1n})$ ， $x_2(x_{21}，x_{22}，x_{23}，···，x_{2n})$ ，则这两个点的曼哈顿距离为：
$L(x1,x2)=∑i=1n∣x1i−x2i∣L(x_1,x_2)=\sum_{i=1}^n|x_{1i}-x_{2i}|$
③ 切比雪夫距离

假设两个点的坐标分别为 $x_1(x_{11}，x_{12}，x_{13}，···，x_{1n})$ ， $x_2(x_{21}，x_{22}，x_{23}，···，x_{2n})$ ，则这两个点的切比雪夫距离为：
$L(x1,x2)=(∑i=1n∣x1i−x2i∣p)1pL(x_1,x_2)=(\sum_{i=1}^n|x_{1i}-x_{2i}|^p)^{\frac{1}{p}}$
其中p趋于正无穷。

其实，上面三种计算方法可以进行一个统一，这就是这一部分的小标题——闵可夫斯基距离。欧氏距离是闵可夫斯基距离 $L(x1,x2)=(∑i=1n∣x1i−x2i∣p)1pL(x_1,x_2)=(\sum_{i=1}^n|x_{1i}-x_{2i}|^p)^{\frac{1}{p}}$ 中 $p = 2$ 的结果，曼哈顿距离是该式 $p = 1$ 的结果，而切比雪夫距离是 $p=+∞p=+\infin$ 的结果

2、马氏距离

马氏距离全称马哈拉诺比斯距离。样本不同的特征之间大小尺寸可能会不同，比如特征1两个数据为10000和20000，特征2两个数据为1和2。如果只考虑其距离，那么10000与12000之间相差的数字肯定要比1与2之间相差的数字要大，但这并不意味着前者的相似度一定要比后者更小，因为他们的尺寸不同难以比较，所以使用马氏距离可以避免这种问题：
$dij=[(xi−xj)TS−1(xi−xj)]12d_{ij}=[(x_i-x_j)^TS^{-1}(x_i-x_j)]^\frac{1}{2}$
其中 $x_i$ 是样本 $i$ 的特征矩阵， $x_j$ 是样本 $j$ 的特征矩阵， $S$ 是样本集合 $X$ 的协方差矩阵。

3、相关系数

相关系数的定义表达式为：
$rij=∑k=1m(xki−x‾i)(xkj−x‾j)[∑k=1m(xki−x‾i)2∑k=1m(xkj−x‾j)2]12r_{ij}=\frac{\sum_{k=1}^{m}(x_{ki}-\overline x_i)(x_{kj}-\overline x_j)}{[\sum_{k=1}^{m}(x_{ki}-\overline x_i)^2\sum_{k=1}^{m}(x_{kj}-\overline x_j)^2]^\frac12}$
相关系数越接近1，表示样本越相似；相关系数越接近0，表示样本越不相似。

4、夹角余弦

夹角余弦的定义表达式为：
$sij=∑k=1mxkixkj[∑k=1mxki2∑k=1mxkj2]12s_{ij}=\frac{\sum_{k=1}^{m}x_{ki}x_{kj}}{[\sum_{k=1}^{m}x_{ki}^2\sum_{k=1}^{m}x_{kj}^2]^\frac12}$
夹角余弦越接近1，表示样本越相似；夹角余弦越接近0，表示样本越不相似。

上面的这些距离是样本点之间的距离，在聚类算法中，我们还需要一种衡量类与类之间的距离方法，常见的有以下四种：

（1）最短距离/单链接(Single-link)：

定义两个类的样本之间的最短距离为两类之间的距离。

缺点：容易出现包含范围特别大的类，因为并没有对两个类的最大距离进行限制。

（2）最长距离/完全链接(Complete-link)：

定义两个类的样本之间的最长距离为两类之间的距离。

缺点：容易受到异常样本点的影响而造成不合理的聚类，因为异常样本点很容易干扰最长距离。

（3）中心距离(UPGMA)：

定义两个类的样本中心之间的距离为两类之间的距离。

（4）平均距离(WPGMA)：

定义两个类任意样本之间的距离的平均为两类之间的距离。

聚合聚类

聚合聚类是一种层次聚类算法，主要分为两种：聚合聚类和分类聚类。聚合聚类开始将每个样本各自分到一个类之中，之后再讲相距最近的两个类合并，最终生成一个类；而分裂聚类正好相反，先将所有样本分到一个类之中，再将样本中距离最远的分到两个新的类。这里只介绍聚合聚类。

算法步骤：

（1）计算样本两两之间的欧式距离，构造距离矩阵
（2）将每个样本都变成一个类： $G_1,G_2,···,G_n$
（3）定义**最短距离(Single-link)**为类间距离，找出距离最小的两个类归为一个新的类
（4）如果只剩下一个类，那么停止运算，否则继续重复(3)(4)

算法复杂度： $O(n^3m)$ ， $n$ 是样本个数， $m$ 是样本维数

K均值聚类

K均值聚类是已知要将原数据样本分成k个类，但是并不知道这k个类具体是什么。刚开始要随机选取k个点作为样本的初始中心点，这k个点各自属于一个类别。再通过比较距离大小将剩余的点分到这k个点对应的类别之中。