机器学习期末复习——第九章

一、重点知识点回顾

1. 原型聚类

原型聚类（Prototype-based Clustering）假设聚类结构能够通过一组原型来刻画。通常情况下，算法先对原型进行初始化，然后对原型进行迭代更新求解。

（1）$k$均值聚类

给定样本集$D=\left\{ \boldsymbol{x}_1,\boldsymbol{x}_2,...,\boldsymbol{x}_{\boldsymbol{m}} \right\}$，$k$均值算法针对聚类所得簇划分$\mathcal{C}=\left\{ C_1,C_2,...,C_k \right\}$最小化平方误差:

$$E=\sum_{i=1}^k{\sum_{\boldsymbol{x}\in C_i}{\lVert \boldsymbol{x}-\boldsymbol{\mu }_i \rVert _{2}^{2}}}$$

其中$\boldsymbol{\mu }_i=\frac{1}{\left| C_i \right|}\sum_{\boldsymbol{x}\in C_i}{\boldsymbol{x}}$是簇$C_i$的均值向量。

（2）学习向量量化

一般聚类算法都是无监督学习，然而学习向量量化算法是监督学习算法。

（3）高斯混合聚类

高斯混合聚类采用概率模型来表达聚类原型。

2. 密度聚类

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

密度聚类和原型聚类的区别可如下图所示：

（1）DBSCAN

DBSCAN是一种著名的密度聚类算法，它基于一组“邻域”参数来刻画样本分布的紧密程度。给定数据集$D=\left\{ \boldsymbol{x}_1,\boldsymbol{x}_2,...,\boldsymbol{x}_{\boldsymbol{m}} \right\}$，定义以下几个概念：

• 核心对象：直观理解的话就是我们的样本考察对象，如图9.8中的$\boldsymbol{x}_1$；
• $\epsilon$-邻域：见图9.8中的虚线；
• 密度直达：若$\boldsymbol{x}_j$位于$\boldsymbol{x}_i$的$\epsilon$-邻域当中，且$\boldsymbol{x}_i$是核心对象，则称$\boldsymbol{x}_j$由$\boldsymbol{x}_i$密度直达；
• 密度可达：对$\boldsymbol{x}_i$与$\boldsymbol{x}_j$，若存在样本序列$\boldsymbol{p}_1,\boldsymbol{p}_2,...,\boldsymbol{p}_n,$，其中$\boldsymbol{p}_1=\boldsymbol{x}_i$，$\boldsymbol{p}_n=\boldsymbol{x}_j$，且$\boldsymbol{p}_{i+1}$由$\boldsymbol{p}_i$密度直达，则称$\boldsymbol{x}_j$由$\boldsymbol{x}_i$密度可达；
• 密度相连：对$\boldsymbol{x}_i$与$\boldsymbol{x}_j$，若存在$\boldsymbol{x}_k$使得$\boldsymbol{x}_i$与$\boldsymbol{x}_j$均由$\boldsymbol{x}_k$密度可达，则称$\boldsymbol{x}_i$与$\boldsymbol{x}_j$密度相连。

基于上述概念，DBSCAN将簇定义为：由密度可达关系导出的最大的密度相连的样本集合。其训练流程如下图所示：

3. 层次聚类

层次聚类（Hierarchical Clustering）试图在不同层次上对数据集进行划分，从而形成树形的聚类结构。

（1）AGNES算法

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

二、重点题目回顾