研究生课程：机器学习-第6章 聚类分析

《机器学习》课程笔记：第6章 聚类分析

第6章 聚类分析

概述

聚类是无监督机器学习问题

• 目标：感知样本间的相似度，进行类别归纳
• 聚类研究的重要应用：1. 潜在类别预测，2. 数据压缩
• 既可以作为一个单独过程，用于寻找数据内在的分布结构，也可以作为分类、稀疏表示等其他学习任务的前驱过程。

影响聚类结果的因素：

1. 属性选择导致不同结果
2. 相似性度量是判断样本间、类别间的相似的标准
3. 聚类规则是样本聚集条件，例如，近邻、损失函数

相似性度量

样本-样本：（向量相似性）

样本-集合：

1. 集合为离散点集

到集合最远点距离：

到集合最近点距离：

到集合平均点距离：

2. 集合为连续区域

集合为平面：

集合为圆：

集合-集合：（类间距离）

集合间最远点距离：

集合间最近点距离：

集合间所有点平均距离：

集合表征点间距离（如平均值）：

集合内样本间距离（类内距离）：

性能度量

聚类性能的外部指标指通过已知类簇划分，对聚类结果进行评价；判别同类别样本对标签一致与否，避免相同类簇划分，不同标签名称导致的不一致。

Jaccard系数、FM系数和Rand系数

聚类性能的内部指标：没有已知的类簇划分进行参考，通过聚类具有的类内相似和类间相异的特点进行评价。

DB指数：，越小越好

Dunn指数：，越大越好

序贯方法

基本思想：逐一比较单个样本与类簇的相似性，有相似类则归类，无相似类则建立新类。

优点：一种简单的，快速算法

相似性的关键度量：类别相似性：样本—类簇（样本—集合）。

缺点：所有样本过滤一遍后才知道类别总数，而先出现的样本不能找到（后出现的）合适类别

改进算法：采用两个阶段，类别确定、分类。

两阶段序贯方法：

缺点：以上两种方法依赖于阈值

改进方法：弱化阈值作用，采用两个阈值，形成灰色带。

双阈值序贯方法

三种算法缺点：

1. 当类别一旦产生，不可变，尽管后来类簇增加，类别很相近也无法合并。
2. 敏感于样本顺序，样本类别未必是最合适的。

增强算法

增强处理1：对类别集合进行合并操作

增强处理2：对样本类别重置

层次聚类

基本思想：

聚类嵌套定义：和是样本集上的两种聚类划分，如果中所有的类簇都是中类簇的子集，则称嵌套在内，记作

层次聚类策略：类簇之间（依据相似性）不断合并、或不断的分化, 直到满足聚类停止条件。

自底向上/归并算法：

第次迭代：计算所有两个类簇的相似性，归并最相似的两个类簇，更新类别划分

缺点：没有归并的类簇间相似性，被重复计算

基于矩阵的归并算法

利用矩阵记录类簇间的相似性

• 删除对应合并的两行和列
• 增加一行和列： 新类簇与其他类簇的相似度

优点：不必重新计算“没有合并的类簇间”的相似性

分化算法：过程与归并相反

第次迭代：在所有类簇的所有划分中，计算所有两个类簇相似性，选择最不相似的类簇集合划分，更新类别划分

缺点：没有划分的类簇间相似性，被重复计算

如何确定聚类个数？

K均值聚类

Kmeans：将样本分给最近的类心，然后重新调整类心；通过多次迭代，逐步进行类别划分。

最优准则：最小化误差平方和，， 是第个类簇的样本。

一般方法：最近类心原则，批量划分后修正类心

改进方法：单个划分最优原则，单个划分后修正类心