AmosTian

0%

8. 聚类分析

发表于 更新于 分类于 >
本文字数 1.9k字 | 阅读时长 ≈ 2 分钟

聚类分析是一种无监督学习方法，通过学习没有分类标记的训练样本分析数据本身的结构来发现数据的内在模式

[TOC]

数据之间的相似性通常用距离度量，类内差异应尽可能小，类间差异应尽可能大

根据形成距离类的方式不同，聚类算法可以分为：层次聚类、原型聚类、分布聚类、密度聚类

聚类分析的重要应用是对用户进行分组与归类

聚类分析概念

目标

学习没有分类标记的训练样本，以解释数据的内在性质和规律

  • 要将数据集划分为若干互不相交的子集，每个子集中的元素在某种度量下都与本子集内的元素有高度相似性，不同子集相关性较低

这种方法划分出的子集就是 聚类（簇）

  • 分类——先确定类别再划分数据
  • 聚类——先划分数据再确定类别

核心问题

  1. 如何判定哪些样本属于同一类
  2. 怎么让同一类的样本聚在一起

分类标准

解决 哪些样本属于同一类 的问题需要 对数据相似性进行度量

  • 同类样本间差距尽可能小
  • 异类样本间差距尽可能大

引入 距离测度：通过计算样本之间的距离判定它们是否属于同一类

  • 样本有 $M$ 个特征，则在 $M$ 维空间中计算不同点之间的距离

距离

  • 非负性：$\ge 0$
  • 同一性：任意点与其自身之间的距离为0
  • 对称性：交换点顺序不改变距离
  • 直递性：满足三角不等式

闵可夫斯基距离

当 $p=2$ 时，闵可夫斯基距离变为 欧氏距离

聚类算法设计

根据应用场景的差别，不同算法在组成聚类的概念以及有效找到聚类的方法上也会有所区别。

针对某种模型设计的算法可能在其他模型的数据集上表现的很差

层次聚类

基于连接的聚类：样本应当与附近而非远离的样本具有更强的相关性

即 同一类样本间的距离应该是同一水平 ，因而聚类的特性可以用聚类内部样本之间的距离尺度来刻画

聚类的划分是在不同的距离水平上完成的，划分过程就可以用 树状图 来表示——层次聚类

  • 自顶向下的拆分策略

  • 自底向上的会聚策略

    数据集的每个样本被视为一个初始聚类，算法每执行一次，就将最近的两个初始聚类合并，直至合并后的数目达到预设为止

    根据距离度量方式，分为：

    • 单链接算法：利用最小距离，由不同聚类中相距最近的样本决定
    • 全链接算法：利用最大距离，由两个不同聚类中相聚最远的样本决定
    • 均链接算法：利用平均距离，由两个不同聚类中的所有样本共同决定

会聚策略计算复杂度很高，拆分策略更加复杂

原型聚类

基于质心的聚类：核心思想是每个聚类可以用一个质心表示。

原型聚类将给定的数据集分裂为若干聚类，每个聚类都用一个中心向量来刻画，然后通过反复迭代来调整聚类中心和聚类成员，直到每个聚类不再变化

K均值

K-means ：典型的原型聚类算法，将聚类问题转化为最优化问题

先找到 $k$ 个聚类中心，并将所有样本分配给最近的聚类中心，分配原则是让所有样本到其聚类中心的欧式距离（平方距离）最小

  1. 从数据集中随机选取 $k$ 个样本作为 $k$ 个聚类各自的中心
  2. 对其余样本分别计算其到这 $k$ 个中心的距离，并将样本划分到离他最近的中心对应的聚类中
  3. 当所有样本的聚类归属确定后，再计算每个聚类中所有样本的算数平均数，作为聚类的新中心，并将所有样本按照 $k$ 新得中心重新聚类，直至聚类结果不再变化为为止

这个优化问题无法求精确解，只能搜索近似解

采用贪心策略，通过迭代优化来近似求解最小平方和

K均值分析：

  • 大多数k均值算法需要预先指定聚类的数目 $k$
  • $k$ 均值算法倾向于划分出相似大小的聚类，这会降低聚类边界的精确性
分布聚类

基于概率模型的聚类，核心思想是假定隐藏的类别是数据空间上的一个分布

在分布聚类中，每个聚类都是最可能属于同一分布的对象的集合。每个聚类中的样本由聚类总体中随机抽取的独立同分布样本组成

  • 缺点：无法确定隐含的概率模型是否真的存在，因而常导致过拟合发生

将样本看做观察值，将潜在的类别看做隐藏变量，那么就可以认为数据集是由不同的聚类产生——在此前提下，基于概率模型的聚类分析的任务是推导出最可能产生已有数据集的 $k$ 个聚类，并度量这 $k$ 个聚类产生已有数据集的似然概率——实质上是参数估计，估计出聚类参数，使似然函数最大化

EM

期望极大算法（Expectation Maximization algorithm），用于含因变量的概率模型中，在这种模型下对参数做出极大似然估计

E-step（期望）：将待估计分布的参数值随机初始化后，利用初始参数来估计样本所属的类别

S-step（最大化）：利用估计结果求取当似然函数取得极大值时，对应参数值的取值

两个步骤不断迭代，直至收敛

密度聚类

核心思想是样本分布的密度能够决定聚类结构

每个样本集中分布的区域都可以看作一个聚类，聚类之间由分散的噪声点区分。密度聚类算法根据样本密度考察样本间的可连接性，再基于可连接样本不断扩展聚类以获得最终结果。

利用噪声的基于密度的空间聚类(Density-Based Spatial Clustering of Applications with Noise)

DBSCAN，通过将距离在某一个阈值之内的点连接起来形成聚类，但连接的对象只限于满足密度标准的点——邻域内的点

  • $\varepsilon-邻域$ 这一概念给出的对邻域的限制，密度的可连接性则通过密度直达关系、密度可达关系、密度相连关系等一系列标准定义，根据这些概念形成的聚类就是由密度可达关系导出的最大密度相连样本集合
-------------本文结束-------------