人工智能

聚类分析——无监督

什么是聚类分析：

问题：给你一堆样本，如何通过样本间可能存在的联系将这些样本分为不同的类别？
这些样本没有原本正确的类别，这种我们称为无监督（无标记的样本），希望寻找样本中存在的自然的聚类。

001

而对于原本就有标记的聚类行为我们称为分类，希望能够将混在一起的不同样本区分开来，这些样本的某写特征可能很相似，但是因为是不同标记，因此我们需要分开这些样本，这里与聚类的行为完全不同！

002

对于一个详细的实物，我们如何使用计算机对他们进行处理，这就要求我们对实物的本体或者特征抽象为一个个特征向量，通过特征向量的距离来表征相似性！所以，如何抽象出特征向量决定了聚类的准确性。

003

上面的例子就体现出了特征的选取在聚类中起到至关重要的作用！

特征相似性的测度和聚类准则

最常见的，我们使用欧氏距离表征两个特征向量之间的距离：

$$
d(x, y) = \sqrt{(x - y)^T (x - y)} = \sqrt{\sum_{i=1}^n (x_i - y_i)^2}
$$

注意，这里的计算需要在同一个量纲下。

004

在第一种情况下，你会发现学生身高对欧氏距离的影响在体重面前完全不值一提，就算此时身高相差1m对于两个学生对应特征向量之间的欧氏距离影响也微乎其微；而第二种，两种特征对欧氏距离都有较大的影响因子（用于表征该特征对欧氏距离的影响力）。

对于上面的这个问题，推出了马氏距离归一化样本特征之间的相关性：

$$
d(x, y) = \sqrt{(x - y)^T S^{-1} (x - y)}
$$

欧式距离中，完全是特征向量中对应分量相乘，再相加得到，如果某一项的值非常大，那么其值就会掩盖值小的一项所起到的作用，这是欧式距离的不足；当采用马氏距离，就可以屏蔽这一点，因为相关性强的一个分量，对应于协方差矩阵C中对角线上的那一项的值就会大一些。再将这一项取倒数，减小该影响。

通过上面的描述你也可以发现，马氏距离对特征向量中每一个分量都做了归一化，并且由于协方差的量纲与原始分量相同，所以马氏距离的结果与原始数据的量纲无关。

005

左图是欧氏距离，右图是马氏距离。左图中，A, B到均值的距离相同，因此都在同一个圆上，忽略了数据的分布（量纲）的不同；右图中，通过协方差矩阵调整了$X_{1}, X_{2}$从而使得虽然A, B之间的马氏距离不同但是更符合数据的分布。

006

上图中更是反映出，欧氏距离的等高线是以原点为中心的圆分布，右边的马氏距离等高线与数据的分布相似。

除了上述两种相似性的测量方式，还有：

角度相似性函数

007

用于表征两个特征向量之间的夹角大小，这样表述相似性有两个好处：

  1. 当特征空间进行尺度变换，如放大缩小时，夹角保持不变；
  2. 当坐标系旋转，或者坐标变换，如仿射变换，双线性变换，平方变换、双平方变换时，夹角不变；

Tanimoto测度：

008

其中x和z的分量用二值来表示，0表示不具有某种特征，1表示具有某种特征。这样就可以表示为所有特征中共有的特征占比了。
表示出两个特征向量之间的相似度后，我们需要定义一个聚类准则函数，使聚类问题变成一个最优化问题，比如说误差平方和：

$$
J = \sum_{j=1}^{c} \sum_{x \in S} |x - m_j|^2
$$

$m_{j}$是定义的质心，使聚类后的同类之间到质心的距离和最小，质心通过平均求得。

分级聚类

009

0010

类间距离准则：

  1. 最近邻域：
    两个不同的类别之间最近的两个样本之间的距离代表两个类别之间的距离；
  2. 最远邻域：
    两个不同的类别之间最远的两个样本之间的距离代表两个类别之间的距离；
  3. 平均邻域：
    两个类别的质心间的距离表示两个类别之间的距离

0011

以最近邻域为例（右上），先初始化所有样本各为一个聚类，然后计算不同类之间的距离，将距离最近的两个类进行合并，之后重新计算类之间的距离，合并后的类计算距离时取类内样本最小距离；按照如此继续聚类合并直到只剩下需求的类别数量；

通过上面的聚类结果可视化能发现，由于样本中存在一个噪声，即距离较远的样本，无论如何计算最近距离该样本都会被判定为一个类，而相距较近的不同类反而被误判为同类。

0012

举个例子🤓 ：

0013

答案见P43。

K均值聚类法

0014

一个比较明显跟分级聚类不同的地方是，类间的距离不是取样本间距离作为判断依据，而是取样本的均值定义为类别重心，求样本到重心的距离来判断该样本属于哪个类别；

问题:

  • 如果k值的选取不正确，那么聚类错误；
  • 高度依赖于初始值选取；
  • 更适用“球形”分布的数据，难处理非球形聚类；

0015

如果一开始的中心取在上下两端则会出现右图的分类情况，因此Kmeans聚类对初始值的选择较敏感；

尝试下面题目：

0016

基于密度峰值的聚类方式

由于Kmeans只适合球状分布，因此针对非球状分布推出了密度峰值聚类；

0017

0018

局部密度定义为$\rho_i = \sum_j \chi(d_{ij} - d_c)$，其中$d_{ij}$表示数据对之间的距离，$d_{c}$为距离阈值，如果距离小于阈值则$\rho_{i}$加一，这样可以计算出局部的密度；

0019

0020

试着解决以下问题吧🤓

0021