聚类

  1. 在无监督学习(unsupervised learning)中,训练样本的标记信息是未知的。

  2. 无监督学习的目标:通过对无标记训练样本的学习来揭露数据的内在性质以及规律。

  3. 一个经典的无监督学习任务:寻找数据的最佳表达(representation)。常见的有:

    • 低维表达:试图将数据(位于高维空间)中的信息尽可能压缩在一个较低维空间中。
    • 稀疏表达:将数据嵌入到大多数项为零的一个表达中。该策略通常需要进行维度扩张。
    • 独立表达:使数据的各个特征相互独立。
  4. 无监督学习应用最广的是聚类(clustering)

    • 给定数据集 ,聚类试图将数据集中的样本划分为 个不相交的子集 ,每个子集称为一个簇cluster。其中:
    • 通过这样的划分,每个簇可能对应于一个潜在的概念。这些概念对于聚类算法而言,事先可能是未知的。
    • 聚类过程仅仅能自动形成簇结构,簇所对应的概念语义需要由使用者来提供。
  5. 通常用 表示样本 的簇标记cluster label,即 。于是数据集 的聚类结果可以用包含 个元素的簇标记向量 来表示。

  6. 聚类的作用:

    • 可以作为一个单独的过程,用于寻找数据内在的分布结构。
    • 也可以作为其他学习任务的前驱过程。如对数据先进行聚类,然后对每个簇单独训练模型。
  7. 聚类问题本身是病态的。即:没有某个标准来衡量聚类的效果。

    • 可以简单的度量聚类的性质,如每个聚类的元素到该类中心点的平均距离。

      但是实际上不知道这个平均距离对应于真实世界的物理意义。

    • 可能很多不同的聚类都很好地对应了现实世界的某些属性,它们都是合理的。

      如:在图片识别中包含的图片有:红色卡车、红色汽车、灰色卡车、灰色汽车。可以聚类成:红色一类、灰色一类;也可以聚类成:卡车一类、汽车一类。

      解决该问题的一个做法是:利用深度学习来进行分布式表达,可以对每个车辆赋予两个属性:一个表示颜色、一个表示型号。

一、性能度量

  1. 聚类的性能度量也称作聚类的有效性指标validity index

  2. 直观上看,希望同一簇的样本尽可能彼此相似,不同簇的样本之间尽可能不同。即:簇内相似度intra-cluster similarity高,且簇间相似度inter-cluster similarity低。

  3. 聚类的性能度量分两类:

    • 聚类结果与某个参考模型reference model进行比较,称作外部指标external index
    • 直接考察聚类结果而不利用任何参考模型,称作内部指标internal index

1.1 外部指标

  1. 对于数据集 ,假定通过聚类给出的簇划分为 。参考模型给出的簇划分为 ,其中 不一定相等 。

    分别表示 的簇标记向量。定义:

    其中 表示集合的元素的个数。各集合的意义为:

    • :包含了同时隶属于 的样本对。
    • :包含了隶属于 ,但是不隶属于 的样本对。
    • :包含了不隶属于 , 但是隶属于 的样本对。
    • :包含了既不隶属于 , 又不隶属于 的样本对。

    由于每个样本对 仅能出现在一个集合中,因此有

  2. 下述性能度量的结果都在 [0,1]之间。这些值越大,说明聚类的性能越好。

1.1.1 Jaccard系数

  1. Jaccard系数Jaccard Coefficient:JC

    它刻画了:所有的同类的样本对(要么在 中属于同类,要么在 中属于同类)中,同时隶属于 的样本对的比例。

1.1.2 FM指数

  1. FM指数Fowlkes and Mallows Index:FMI

    它刻画的是:

    • 中同类的样本对中,同时隶属于 的样本对的比例为
    • 中同类的样本对中,同时隶属于 的样本对的比例为
    • FMI就是 的几何平均。

1.1.3 Rand指数

  1. Rand指数Rand Index:RI

    它刻画的是:

    • 同时隶属于 的同类样本对(这种样本对属于同一个簇的概率最大)与既不隶属于 、 又不隶属于 的非同类样本对(这种样本对不是同一个簇的概率最大)之和,占所有样本对的比例。
    • 这个比例其实就是聚类的可靠程度的度量。

1.1.4 ARI指数

  1. 使用RI有个问题:对于随机聚类,RI指数不保证接近0(可能还很大)。

    ARI指数就通过利用随机聚类来解决这个问题。

  2. 定义一致性矩阵为:

    其中:

    • 为属于簇 的样本的数量, 为属于簇 的样本的数量。
    • 为同时属于簇 和簇 的样本的数量。

    则根据定义有: ,其中 表示组合数。数字2 是因为需要提取两个样本组成样本对。

  3. 定义ARI指数Adjusted Rand Index:

    其中:

    • :表示同时隶属于 的样本对。

    • :表示最大的样本对。

      即:无论如何聚类,同时隶属于 的样本对不会超过该数值。

    • :表示在随机划分的情况下,同时隶属于 的样本对的期望。

      • 随机挑选一对样本,一共有 种情形。
      • 这对样本隶属于 中的同一个簇,一共有 种可能。
      • 这对样本隶属于 中的同一个簇,一共有 种可能。
      • 这对样本隶属于 中的同一个簇、且属于 中的同一个簇,一共有 种可能。
      • 则在随机划分的情况下,同时隶属于 的样本对的期望(平均样本对)为:

1.2 内部指标

  1. 对于数据集 ,假定通过聚类给出的簇划分为

    定义:

    其中: 表示两点 之间的距离; 表示簇 的中心点, 表示簇 的中心点, 表示簇 的中心点之间的距离。

    上述定义的意义为:

    • : 簇 中每对样本之间的平均距离。
    • :簇 中距离最远的两个点的距离。
    • :簇 之间最近的距离。
    • :簇 中心点之间的距离。

1.2.1 DB指数

  1. DB指数Davies-Bouldin Index:DBI

    其物理意义为:

    • 给定两个簇,每个簇样本距离均值之和比上两个簇的中心点之间的距离作为度量。

      该度量越小越好。

    • 给定一个簇 ,遍历其它的簇,寻找该度量的最大值。

    • 对所有的簇,取其最大度量的均值。

  2. 显然 越小越好。

    • 如果每个簇样本距离均值越小(即簇内样本距离都很近),则 越小。
    • 如果簇间中心点的距离越大(即簇间样本距离相互都很远),则 越小。

1.2.2 Dunn指数

  1. Dunn指数Dunn Index:DI

    其物理意义为:任意两个簇之间最近的距离的最小值,除以任意一个簇内距离最远的两个点的距离的最大值。

  2. 显然 越大越好。

    • 如果任意两个簇之间最近的距离的最小值越大(即簇间样本距离相互都很远),则 越大。
    • 如果任意一个簇内距离最远的两个点的距离的最大值越小(即簇内样本距离都很近),则 越大。

1.3 距离度量

  1. 距离函数 常用的有以下距离:

    • 闵可夫斯基距离Minkowski distance

      给定样本 ,则闵可夫斯基距离定义为:

      • 时,闵可夫斯基距离就是欧式距离Euclidean distance

      • 时,闵可夫斯基距离就是曼哈顿距离Manhattan distance

    • VDM距离Value Difference Metric

      考虑非数值类属性(如属性取值为:中国,印度,美国,英国),令 表示 的样本数; 表示 且位于簇 中的样本的数量。则在属性 上的两个取值 之间的 VDM距离为:

      该距离刻画的是:属性取值在各簇上的频率分布之间的差异。

  2. 当样本的属性为数值属性与非数值属性混合时,可以将闵可夫斯基距离与 VDM 距离混合使用。

    假设属性 为数值属性, 属性 为非数值属性。则:

  3. 当样本空间中不同属性的重要性不同时,可以采用加权距离。

    以加权闵可夫斯基距离为例:

  4. 这里的距离函数都是事先定义好的。在有些实际任务中,有必要基于数据样本来确定合适的距离函数。这可以通过距离度量学习distance metric learning来实现。

  5. 这里的距离度量满足三角不等式:

    在某些任务中,根据数据的特点可能需要放松这一性质。如:美人鱼距离很近,美人鱼距离很近,但是的距离很远。这样的距离称作非度量距离non-metric distance

二、原型聚类

  1. 原型聚类prototype-based clustering假设聚类结构能通过一组原型刻画。

    常用的原型聚类有:

    • k均值算法k-means
    • 学习向量量化算法Learning Vector Quantization:LVQ
    • 高斯混合聚类Mixture-of-Gaussian

2.1 k-means 算法

2.1.1 k-means

  1. 给定样本集 , 假设一个划分为

    定义该划分的平方误差为:

    其中 是簇 的均值向量。

    • 刻画了簇类样本围绕簇均值向量的紧密程度,其值越小,则簇内样本相似度越高。
    • k-means 算法的优化目标为:最小化 。即:
  2. k-means 的优化目标需要考察 的所有可能的划分,这是一个NP难的问题。实际上k-means 采用贪心策略,通过迭代优化来近似求解。

    • 首先假设一组均值向量。

    • 然后根据假设的均值向量给出了 的一个划分。

    • 再根据这个划分来计算真实的均值向量:

      • 如果真实的均值向量等于假设的均值向量,则说明假设正确。根据假设均值向量给出的 的一个划分确实是原问题的解。
      • 如果真实的均值向量不等于假设的均值向量,则可以将真实的均值向量作为新的假设均值向量,继续迭代求解。
  3. 这里的一个关键就是:给定一组假设的均值向量,如何计算出 的一个簇划分?

    k均值算法的策略是:样本离哪个簇的均值向量最近,则该样本就划归到那个簇。

  4. k-means 算法:

    • 输入:

      • 样本集
      • 聚类簇数
    • 输出:簇划分

    • 算法步骤:

      • 中随机选择 个样本作为初始均值向量

      • 重复迭代直到算法收敛,迭代过程:

        • 初始化阶段:取

        • 划分阶段:令

          • 计算 的簇标记:

            即:将 离哪个簇的均值向量最近,则该样本就标记为那个簇。

          • 然后将样本 划入相应的簇:

        • 重计算阶段:计算

        • 终止条件判断:

          • 如果对所有的 ,都有 ,则算法收敛,终止迭代。
          • 否则重赋值
  5. k-means 优点:

    • 计算复杂度低,为 ,其中 为迭代次数。

      通常 要远远小于 ,此时复杂度相当于

    • 思想简单,容易实现。

  6. k-means 缺点:

    • 需要首先确定聚类的数量

    • 分类结果严重依赖于分类中心的初始化。

      通常进行多次k-means,然后选择最优的那次作为最终聚类结果。

    • 结果不一定是全局最优的,只能保证局部最优。

    • 对噪声敏感。因为簇的中心是取平均,因此聚类簇很远地方的噪音会导致簇的中心点偏移。

    • 无法解决不规则形状的聚类。

    • 无法处理离散特征,如:国籍、性别 等。

  1. k-means 性质:

    • k-means 实际上假设数据是呈现球形分布,实际任务中很少有这种情况。

      与之相比,GMM 使用更加一般的数据表示,即高斯分布。

    • k-means 假设各个簇的先验概率相同,但是各个簇的数据量可能不均匀。

    • k-means 使用欧式距离来衡量样本与各个簇的相似度。这种距离实际上假设数据的各个维度对于相似度的作用是相同的。

    • k-means 中,各个样本点只属于与其相似度最高的那个簇,这实际上是 分簇。

    • k-means 算法的迭代过程实际上等价于EM 算法。具体参考EM 算法章节。

2.1.2 k-means++

  1. k-means++ 属于 k-means 的变种,它主要解决k-means 严重依赖于分类中心初始化的问题。

  2. k-means++ 选择初始均值向量时,尽量安排这些初始均值向量之间的距离尽可能的远。

  3. k-means++ 算法:

    • 输入:

      • 样本集
      • 聚类簇数
    • 输出:簇划分

    • 算法步骤:

      • 中随机选择1个样本作为初始均值向量组

      • 迭代,直到初始均值向量组有 个向量。

        假设初始均值向量组为 。迭代过程如下:

        • 对每个样本 ,分别计算其距 的距离。这些距离的最小值记做
        • 对样本 ,其设置为初始均值向量的概率正比于 。即:离所有的初始均值向量越远,则越可能被选中为下一个初始均值向量。
        • 以概率分布 (未归一化的)随机挑选一个样本作为下一个初始均值向量
      • 一旦挑选出初始均值向量组 ,剩下的迭代步骤与k-means 相同。

2.1.3 k-modes

  1. k-modes 属于 k-means 的变种,它主要解决k-means 无法处理离散特征的问题。

  2. k-modesk-means 有两个不同点(假设所有特征都是离散特征):

    • 距离函数不同。在k-modes 算法中,距离函数为:

      其中 为示性函数。

      上式的意义为:样本之间的距离等于它们之间不同属性值的个数。

    • 簇中心的更新规则不同。在k-modes 算法中,簇中心每个属性的取值为:簇内该属性出现频率最大的那个值。

      其中 的取值空间为所有样本在第 个属性上的取值。

2.1.4 k-medoids

  1. k-medoids 属于 k-means 的变种,它主要解决k-means 对噪声敏感的问题。

  2. k-medoids 算法:

    • 输入:

      • 样本集
      • 聚类簇数
    • 输出:簇划分

    • 算法步骤:

      • 中随机选择 个样本作为初始均值向量

      • 重复迭代直到算法收敛,迭代过程:

        • 初始化阶段:取

          遍历每个样本 ,计算它的簇标记: