聚类

发表于 | 分类于 ，

聚类任务

  • 在无监督学习中（unsupervised learning）中，训练样本的标记信息是未知的，目标是通过对无标记的训练样本的学习来揭示数据的内在性质及规律，为进一步的数据分析提供基础。此类学习任务中研究最多、应用最广的是“聚类”（clustering）
  • 聚类试图将数据集中的样本划分为若干通常是不相交的子集，每个子集称为一个“簇”（cluster）。
  • 聚类既能作为一个单独的过程，用于找寻数据内的分布结构，也可作为分类等其他学习任务的前驱过程。

性能度量

  • 聚类性能度量亦称聚类“有效性指标”（validity index）
    • 与监督学习中的性能度量作用相似。对聚类结果，我们需通过某种性能度量来评估其好坏；
    • 另一方面，若明确了最终将要使用的性能度量，则可直接将其作为聚类过程的优化目标，从而更好地得到符合要求的聚类结果。
      聚类是将样本集D划分为若干不相交的子集，即样本簇。直观上看，我们希望“物以类聚”，即同一簇的样本尽可能彼此相似，不同簇的样本尽可能不同。换言之，聚类结果的“簇内相似度”（intra-cluster similarity）高且“簇间相似度”（inter-cluster similarity）低。
  • 聚类性能度量大致有两类：
    • “外部指标”（external index）
      将聚类结果与某个“参考模型”（reference model）进行比较；
      • 常用的聚类性能度量外部指标有：
        • Jaccard系数（Jaccard Coefficient，简称 JC）
        • FM指数（Fowlkes and Mallows Index，简称FMI）
        • Rand指数（Rand Index，简称RI）
    • “内部指标”（internal index）
      直接考察聚类结果而不利用任何参考模型
      • 常用的聚类性能度量内部指标有
        • DB指数（Davies-Bouldin Index，简称DBI）
        • Dunn指数（Dunn Index，简称DI）

距离计算

  • 给定样本$x_i=（x_{i1}，x_{i2}；…；x_{in}），与x_j=（x_{j1}；x_{j2}；…；x_{jn}）$
  • 最常用的是”闵可夫斯基距离“（Minkowski distance）
  • p=2时，闵可夫斯基距离即欧氏距离（Euclidean distance）
  • p=1时，闵可夫斯基距离即曼哈顿距离（Manhattan distance）

原型聚类

原型聚类亦称”基于原型的聚类“（prototype-based clustering），此类算法假设聚类结构能通过一组原型刻画，在现实聚类任务中极为常用。

  • 通常情形下，算法先对原型进行初始化，然后对原型进行迭代更新求解。采用不同的原型表示、不同的求解方式，将产生不同的算法
    • 我的理解就是直接通过先假设几个样本就为几类簇，然后再迭代更新
  • k均值算法
    给定样本集$D={x_1，x_2，…，x_m}$，”k均值“（k-means）算法针对聚类所得簇划分$C={C_1，C_2，…，C_k}$最小化平方误差
    • 直观来看，上面式子在一定程度上刻画了簇内样本围绕簇均值向量的紧密程度，E值越小则簇内样本相似度越高
      • 其中$\mu_i$，是簇$C_i$的均值向量

  • 学习向量量化
    与k均值算法类似，“学习向量量化”（Learning Vector Quantization，简称LVQ）也是试图找到一组原型向量来刻画聚类结构，但与一般的聚类算法不同的是，LVQ假设数据样本带有类别标记，学习过程用样本的这些监督信息来辅助聚类

    • 和KMeans的区别：
      • LVQ数据样本带有标签
      • 初始化方式不同，LVQ是初始化一组向量，KMeans初始化几个簇点
      • 迭代方式不同，LVQ是循环找到每个样本点和向量簇最近的向量，然后根据该样本点的类别是否和该向量表示的类别是否相同，另该向量靠近或更远离该点

  • 高斯混合聚类
    与k均值、LVQ用原型向量来刻画聚类结构不同，高斯混合（Mixture-of-Gaussian）聚类采用概率模型来表达聚类原型

密度聚类

密度聚类亦称“基于密度的聚类”（density-based clustering），此类算法假设聚类结构能通过样本分布的紧密程度确定。通常情况下，密度聚类算法从样本密度的角度来考察样本之间的可连接性，并基于可连接样本不断扩展聚类簇以获得最终的聚类结果。

  • DBSCAN是一种著名的密度聚类算法

层次聚类

层次聚类（hierarchical clustering）试图在不同层次对数据集进行划分，从而形成树形的聚类结构。数据集的划分可采用“自底向上”的聚合策略，也可采用“自顶向下”的分拆策略。

  • AGNES 是一种采用自底 向上聚合策略的层次聚类算法.它先将数据集中 的每个样本看作一个初始聚类簇，然后在算法运行的每一步中找 出距离最近的两个粟类簇进行合并，该过程不断重复，直至达到预设的聚类簇个数
  • Louvain算法