[机器学习]第九章聚类

作者: 两全丶 | 来源:发表于2018-09-17 22:57 被阅读0次

《机器学习》西瓜书学习笔记（六）
3.1.1.9 聚类
第一章回归，分类 & 聚类
9.machine_learning_clusting_and_
机器学习-聚类
机器学习----聚类
聚类算法
[机器学习]第九章聚类
技术积累
K均值聚类及代码实现

9.1 聚类任务

常见的无监督学习任务

密度估计
异常检测
聚类

聚类任务将数据集划分为若干个不相交的子集，为每一个样本标上一个簇标记(表示这个样本属于哪个簇)，于是得到一个簇标记向量

9.2 性能度量

在开始一项机器学习任务之前，首先必须要定义好性能度量指标，以便量化的评估模型的好坏。

聚类性能度量的基本想法

“物以类聚”，相同簇内的样本应该尽可能的相似；“人以群分”，不同簇内的样本应该经可能的不同。需要定义距离来度量相似性。

两类度量指标

外部指标通过和一个参考模型比较（即和一个专家进行比较）
内部指标不借助任何参考模型

外部指标

假定通过聚类给出的簇划分为 $C = \{C_1...C_K\}$ , 参考模型给出的簇划分为 $C^* = \{C_1^*...C_K^*\}$ , 令 $\lambda$ 与 $\lambda^*$ 分别表示聚类给出的簇标记向量以及参考模型给出的簇标记向量, 定义如下量

其中 $a$ 表示在中属于同一个簇的且在中也属于同一个簇的点对的集合，其他依次类推。显然我们希望 $a$ 和 $b$ 越大越好。

由于一个点对只能出现在一个集合中，共有个点对，所以 $a + b + c + d = \frac{m(m - 1) }{2}$

Jaccard系数

显然当 $a$ 和 $b$ 越大时，该系数越大，直观的表达了聚类性能度量的基本想法

$JC = \frac{a}{a + b + c} = \frac{a}{S - b}$
FM系数

$FMI = \sqrt{\frac{a}{a + b}\frac{a}{a +c}}$
Rand指数

$RI = \frac{2(a + d)}{m(m - 1)}$

内部指标

簇内样本间平均距离

描述簇内的聚合程度

簇内样本间最大距离

描述簇内的聚合程度

簇间样本最小距离

描述两簇之间的距离

两簇间样本中心距离

描述两簇簇之间的距离

DB指数

显然任意两簇样本内平均距离越小，样本中心越远越好，所以DB指数越小越好
Dunn指数

显然任意两簇，簇内最远距离越小，簇间最小距离越大越好，所以该指数越大越好

9.4 原型聚类

此类算法假设聚类结构能够通过一组原型刻画，在聚类任务中较为通用。一般先对原型进行初始化，然后再对原型进行迭代更新求解

9.4.1 k均值算法

给定样本,k均值算法针对聚类所得簇划分最小化平方误差,

$E = \sum^k_{i = 1}\sum_{x \in C_i}||x - \mu_i||^2_2$

E值越小，簇内样本相似程度越高，求解该最优划分为NP难问题，k均值算法采用贪心策略通过迭代优化来近似求解

算法流程

image

可设定最大迭代次数，或的最小更新幅度阈值来防止迭代过久

9.4.2 学习向量量化(Learning Vector Quantization)

LVQ假设数据样本带有类别标记，利用这些监督信息来辅助聚类

算法流程

image

初始化原型向量可如下操作，对第个簇，从类别标记相同的样本中随机选取一个作为原型向量
LVQ根据样本与原型向量的距离来划分簇，因此学得一组原型向量后，就得到了样本空间上的一组划分，称为"Voronoi"划分
学习率越大，每次原型向量更新的幅度就越大
若将簇所对应的划分区域中的样本全用原型向量表示，则可实现数据的有损压缩，称为“向量量化”

9.4.3 高斯混合聚类

k均值和LVQ通过原型向量来刻画聚类结构，而高斯混合聚类通过概率模型来表达聚类原型

高斯分布

由 $n$ 维均值向量和 $n \times n$ 的协方差矩阵决定

高斯混合分布

数据分布由k个高斯成分混合而成，每个高斯分布都有一个混合系数 $\alpha_i$ ,且 $\sum_{i=1}^{k}\alpha_i = 1$ ，则为样本在生成过程中，选择第个高斯分布的概率 $P(z_j = i)$ 对应与 $\alpha_i$

聚类

训练集，令 $z_j \in \{1,2....k\}$ 表示生成样本的高斯混合成分, 设后验概率为 $p_M(z_j = i | x_j)$ , 简记为 $\gamma_{ji}$ 由贝叶斯定义得的后验分布为

image

高斯混合聚类把样本D划分为k个簇（对应k个混合成分），每个样本的簇标记如下确定，选取簇标记后验概率最大的一个做为样本的簇标记,

image

模型参数由EM算法求取

由表达式看，参数通过样本加权平均来估计，权重为每个样本属于该成分的后验概率

算法流程

image

9.5 密度聚类

密度聚类假设聚类结构能通过样本分布的紧密程度确定。

DBSCAN聚类

使用一组“邻域”参数来刻画样本分布的紧密程度,数据集 $D = \{x_1....x_m\}$

$\epsilon$ -邻域

对于样本 $x_j \in D$ , $N_\epsilon = \{x_i \in D | dist(x_i,x_j) \leq \epsilon\}$ , 即与样本之间的距离小于 $\epsilon$ 的样本的集合
核心对象

若 $x_j$ 的 $\epsilon$ -邻域内至少包含个 $MinPts$ 样本，则 $x_j$ 是一个核心对象
密度直达

若 $x_j$ 位于 $x_i$ 的 $\epsilon$ -邻域中，且 $x_i$ 是核心对象，则 $x_j$ 由 $x_i$ 密度直达
密度可达

若存在样本序列 $p_1....p_n$ , 其中 $p_1 = x_i, p_n = x_j$ ,且 $p_{i + 1}$ 由 $p_i$ 密度直达，则 $x_j$ 由 $x_i$ 密度可达

即存在一条路径使得可以到达的 $x_i$ 的 $\epsilon-$ 邻域内
密度相连

若 $x_i$ 与 $x_j$ 存在 $x_k$ , 使的 $x_i$ 与 $x_j$ 均由 $x_k$ 密度可达，则称 $x_i$ 与 $x_j$ 密度相连

簇的定义

DBSCAN将簇定义为

由密度可达关系导出的最大密度相连样本集合

连接性

簇内任意两个样本都是密度相连的
最大性

簇内样本不与簇外的任何一个样本密度相连

由上定义可看出，这里的簇与图论中的连通分量概念相似

若为核心对象，由密度可达的所有样本组成的集合为,则为满足连接性与最大性的簇

算法流程

image

9.6 层次聚类

层次聚类尝试在不同层次对数据集进行划分，从而形成树形的聚类结构

自底向上聚合数据集
自顶向下拆分数据集

AGNES聚类

采用自底向上聚合策略进行聚类，先将数据集中的每一个样本看作一个初始簇，不断合并距离最近的两个簇，直到达到预设的簇的个数。关键是距离的计算。

image

由最小距离计算时：AGNES算法被称为单链接
由最大距离计算时：AGNES算法被称为全链接
由平均距离计算时：AGNES算法被称为均链接

算法流程

image.png

《机器学习》西瓜书学习笔记（六）
上一篇笔记在这里：《机器学习》西瓜书学习笔记（五）第九章聚类 9.1 聚类任务无监督学习（unsupervi...
3.1.1.9 聚类
聚类原理《机器学习》周志华 9.1 聚类任务在“无监督学习”(unsupervised learning)中...
第一章回归，分类 & 聚类
•分类数据 •数据回归分析 •聚类数据 •如何构建机器学习问题虽然还有其他模型，但是回归，分类和聚类在机器学习问...
9.machine_learning_clusting_and_
机器学习聚类与降维机器学习中的聚类算法聚类是一种经典的无监督学习方法，无监督学习的目标是通过对无标记训练样本的...
机器学习-聚类
简介前面介绍的线性回归，SVM等模型都是基于数据有标签的监督学习方法，本文介绍的聚类方法是属于无标签的无监督学习...
机器学习----聚类
接着机器学习系列文章的脚印，今天介绍一下机器学习的无监督算法--聚类，内容主要包括以下几个部分：（1）常见的聚类...
聚类算法
#聚类算法标签（空格分隔）：机器学习聚类算法 --- ###聚类算法的原理无监督算法，相似的样本自动归...
[机器学习]第九章聚类
9.1 聚类任务常见的无监督学习任务密度估计异常检测聚类聚类任务将数据集划分为若干个不相交的子集，为每一...
技术积累
数学基础 MCMC 采样 MCMC 采样一、机器学习 1、无监督学习聚类 Kmeans 聚类降维 PCA 理...
K均值聚类及代码实现
KMeans聚类在聚类算法中，最出名的应该就是k均值聚类(KMeans)了，几乎所有的数据挖掘/机器学习书籍都会...

[机器学习]第九章聚类

9.1 聚类任务

9.2 性能度量

9.4 原型聚类

9.4.1 k均值算法

9.4.2 学习向量量化(Learning Vector Quantization)

9.4.3 高斯混合聚类

9.5 密度聚类

DBSCAN聚类

9.6 层次聚类

AGNES聚类

相关文章

《机器学习》西瓜书学习笔记（六）

3.1.1.9 聚类

第一章回归，分类 & 聚类

9.machine_learning_clusting_and_

机器学习-聚类

机器学习----聚类

聚类算法