编辑

8.1 基本概念

8.1.1 什么是聚类？

在无监督学习中，需要发现数据中分组聚集的结构，并根据数据中样本与样本之间的距离或相似度，将样本划分为若干组/类/簇（cluster）

划分的原则：类内样本距离小，类间样本距离大

一、聚类的类型

聚类的结果是产生一组聚类的集合

  • 基于划分的聚类（无嵌套）：每个样本仅属于一个簇

  • 基于层次的聚类（嵌套）：树形的聚类结构，簇之间存在嵌套

聚类中的簇集合还有一些其它的区别，包括：

  • 独占和非独占：非独占的簇中，样本可以属于多个簇

  • 模糊和非模糊

    • 模糊的簇表现为∑p=1\sum p=1，而非模糊的簇中概率非0即1

    • 概率聚类有相似的特性

  • 部分和完备：在非完备的场景中，只聚类部分数据

  • 异质和同质：簇的大小、形状和密度是否有很大差别

二、簇的类型

1、基于中心的簇

簇内的点和其“中心”较为相近（或相似），和其他簇的“中心”较远，这样的一组样本形成的簇

簇中心的表示：

  • 质心：簇内所有点的平均

  • 中值点：簇内最有代表性的点

2、基于连续性和基于密度的簇

  • 连续性：相比其他任何簇的点，每个点都至少和所属簇的某一个点更近

  • 密度：簇是由高密度的区域形成的，簇之间是一些低密度的区域

3、基于概念的簇

同一个簇共享某种性质，这个性质是从整个集合推导出来的

这种簇通常较难分辨，因为它一般不是基于中心/密度的

三、聚类分析的三要素

  • 如何定义样本点之间的远近

    • 距离函数

  • 如何评价聚类得到的簇的质量

    • 评价函数

  • 如何获得聚类的簇

    • 怎样表示簇

    • 怎样设计划分和优化算法

    • 算法何时停止

8.1.2 数据预处理

假设有n个样本，每一个有d个特征，则可以表示为一个n行d列的特征矩阵。对于这样的样本特征矩阵，有一些常见的数据预处理步骤：

一、标准化（StandardScaler）

将输入特征的均值变为0，方差变为1

对于每一个维度的特征，有：

xi‘=xi−μσμ=1N∑i=0Nxiσ=1N−1(∑i=1Nxi−μ)2\begin{align} &x_i^`=\frac{x_i-\mu}{\sigma} \nonumber\\ \\ &\mu = \frac1N\sum_{i=0}^Nx_i\\ \\ &\sigma = \sqrt{\frac1{N-1}\left(\sum_{i=1}^Nx_i-\mu\right)^2} \end{align}

二、区间缩放（Min-Max Scaling）

将特征的取值范围缩放到[0,1][0,1]​区间

有时也会缩放到[−1,1][-1,1]

  • 对非常小的标准偏差的特征鲁棒性更强

  • 能够在系数数据中保留零条目

三、归一化（Normalization）

对于样本的不同特征，将它们缩放同样的单位向量

即将样本的模的长度变为单位1：

xi‘=xi∥xi∥2=xi∑d=1Dxid2\begin{align} \boldsymbol x_i^` &= \frac{\boldsymbol x_i}{\Vert\boldsymbol x_i\Vert_2} \nonumber\\ \\ &= \frac{\boldsymbol x_i}{\sqrt{\sum\limits_{d=1}^D x_{id}^2}} \end{align}

在求欧氏距离和文本特征时常用到

8.1.3 距离度量函数

一个距离度量函数应当满足的特征：

  • 非负性：dist(xi,xj)≥0dist(\boldsymbol x_i,\boldsymbol x_j)\geq 0

  • 不可分的同一性：dist(xi,xj)=0 if xi=xjdist(\boldsymbol x_i,\boldsymbol x_j) = 0\ if\ \boldsymbol x_i=\boldsymbol x_j

  • 对称性：dist(xi,xj)=dist(xj,xi)dist(\boldsymbol x_i,\boldsymbol x_j) = dist(\boldsymbol x_j,\boldsymbol x_i)

  • 三角不等式：dist(xi,xj)≤dist(xi,xk)+dist(xk,xj)dist(\boldsymbol x_i,\boldsymbol x_j) \leq dist(\boldsymbol x_i,\boldsymbol x_k) + dist(\boldsymbol x_k,\boldsymbol x_j)

一、闵可夫斯基（Minkowski）距离

dist(xi,xj)=(∑d=1D∣xid−xjd∣p)1pdist(\boldsymbol x_i,\boldsymbol x_j)=\left(\sum_{d=1}^D\vert x_{id}-x_{jd}\vert^p\right)^\frac1p

当p=2p=2时，为欧氏距离：

dist(xi,xj)=∑d=1D(xid−xjd)2dist(\boldsymbol x_i,\boldsymbol x_j)=\sqrt{\sum_{d=1}^D( x_{id}-x_{jd})^2}

当p=1p=1时，为曼哈顿距离：

dist(xi,xj)=∑d=1D∣xid−xjd∣dist(\boldsymbol x_i,\boldsymbol x_j)=\sum_{d=1}^D\vert x_{id}-x_{jd}\vert

  • 对样本特征的旋转和平移变换不敏感

  • 对样本特征的数值尺度敏感

  • 当特征值尺度不一致时，需要进行标准化操作

二、余弦相似度

将两个变量看作高维空间的两个向量，通过夹角余弦评估其相似度：

cos⁡(θ)=a⋅b∥a∥×∥b∥=(x1,y1)⋅(x2,y2)x12+y12×x22+y22=x1x2+y1y2x12+y12×x22+y22\begin{align} \cos(\theta) &= \frac{a\cdot b}{\Vert a\Vert\times\Vert b\Vert} \nonumber \\ \\ &= \frac{(x_1,y_1)\cdot(x_2,y_2)}{\sqrt{x_1^2+y_1^2}\times\sqrt{x_2^2+y_2^2}}\\ \\ &= \frac{x_1x_2+y_1y_2}{\sqrt{x_1^2+y_1^2}\times\sqrt{x_2^2+y_2^2}} \end{align}

进而有：

cos⁡(θ)=∑i=1n(xi×yi)∑i=1nxi2×∑i=1nyi2\cos(\theta)=\frac{\sum\limits_{i=1}^n(x_i\times y_i)}{\sqrt{\sum\limits_{i=1}^nx_i^2}\times\sqrt{\sum\limits_{i=1}^ny_i^2}}

三、相关系数

定义变量xi,xj\boldsymbol x_i,\boldsymbol x_j的相关系数为：

r(xi,xj)=cov(xi,xj)σxiσxj=E[(xi−μi)(xi−μj)]σxiσxj=∑k=1D(xik−μik)(xjk−μjk)∑k=1D(xik−μik)2∑j=1D(xjk−μjk)2\begin{align} r(\boldsymbol x_i,\boldsymbol x_j) &= \frac{cov(\boldsymbol x_i,\boldsymbol x_j)}{\sigma_{x_i}\sigma_{x_j}}\nonumber \\ \\ &=\frac{\mathbb{E}\left[\left(\boldsymbol{x}_i-\boldsymbol{\mu}_i\right)\left(\boldsymbol{x}_i-\boldsymbol{\mu}_j\right)\right]}{\sigma_{\boldsymbol{x}_i} \sigma_{\boldsymbol{x}_j}}\\ \\ &=\frac{\sum\limits_{k=1}^D(x_{ik-\mu_{ik}})(x_{jk}-\mu_{jk})}{\sqrt{\sum\limits_{k=1}^D(x_{ik}-\mu_{ik})^2\sum\limits_{j=1}^D(x_{jk}-\mu_{jk})^2}} \end{align}

当对数据做中心化后，相关系数等于余弦相似度

8.1.4 聚类性能评价指标

绘图代码

上一页附 第七章作业下一页8.2 经典聚类算法

最后更新于

这有帮助吗？