葫芦书第五章——非监督学习

作者: 单调不减 | 来源:发表于2019-08-12 14:52 被阅读0次

葫芦书第五章——非监督学习
第十三章聚类（Clustering）
吴恩达机器学习笔记-非监督学习
监督学习和非监督学习
11.25 统计学习方法
监督学习——学习笔记
监督&非监督
机器学习分类
Introduction of Machine Learning
监督学习，非监督学习

在实际工作中，我们经常会遇到这样一类问题：给机器输入大量的特征数据，并期望机器通过学习找到数据中存在的某种共性特征或者结构，亦或是数据之间存在的某种关联。例如，视频网站根据用户的观看行为对用户进行分组从而建立不同的推荐策略，或是寻找视频播般是否流畅与用户是否退订之间的关系等。这类问题被称作“非监督学习”问题，它并不是像监督学习那样希望预测某种输出结果。相比监督学习，非监督学习的输入数据没有标签信息，需要通过算法模型来挖掘数据内在的结构和模式。非监督学习主要包含两大类学习方法：数据聚类和特征变量关联。其中，聚类算法往往是通过多次迭代来找到数据的最优分割，而特征变量关联则是利用各种相关性分析方法采找到变量之间的关系。

1、K均值聚类

聚类是在事先并不知道任何样本类别标签的情况下，通过数据之间的内在关系把样本划分为若干类别，使得同类别样本之间的相似度高，不同类别之间的样本相似度低。

K均值聚类（K-Means Clustering）是最基础和最常用的聚类算法。它的基本思想是通过迭代方式寻找K个簇(Cluster）的一种划分方案使得聚类结果对应的代价函数最小。

1.1、简述K均值算法的具体步骤。

我的回答：

K均值算法的步骤很简单，首先，在特征空间中任意选择K个点作为中心点，然后计算样本点到它们的距离，将各样本点划入与其距离最近的中心点形成K个簇，然后更新中心点为K个簇的均值点，并重复上述过程，直到各簇的样本点不发生变化为止。

参考答案：

K均值聚类的核心目标是将给定的数据集划分成K个簇，并给出每个数据对应的簇中心点。算法的具体步骤描述如下：

1）数据预处理，如归一化、离群点处理等。

2）随机选取K个簇中心，记为 $\{\mu_1^{(0)},\dots,\mu_k^{(0)}\}$ 。

3）定义代价函数 $J(c,\mu)=\min_\mu\min_c\sum_{i=1}^M ||x_i-\mu_{c_i}||^2$ 。

4）令 $t=0,1,\dots$ ，重复以下过程直到 $J$ 收敛：

对于每一个样本 $x_i$ ，将其分配到距离最近的簇：

$c_i^{(t)} \leftarrow \arg \min_k ||x_i-\mu_k^{(t)}||^2$

对于每一个类簇k，重新计算该类簇的中心：

$\mu_k^{(t+1)}\leftarrow \arg \min_{\mu} \sum_{i:c_i^{(t)}=k}||x_i-\mu||^2$

K均值算法在迭代时，假设当前 $J$ 没有达到最小值，那么首先固定簇中心 $\{\mu_k\}$ ，调整每个样例 $x_i$ 所属的类别 $c_i$ ，来让 $J$ 函数减少，然后固定 $\{c_i\}$ ，调整簇中心 $\{\mu_k\}$ 使 $J$ 减小。这两个过程交替循环， $J$ 单调递减；当 $J$ 递减到最小值时， $\{\mu_k\}$ 和 $\{c_i\}$ 也同时收敛。

1.2、K均值算法的优缺点是什么？如何对其进行调优？

我的回答：

1、K均值的优点是算法简单易操作，计算效率高。

2、K均值的缺点是算法对初始中心点的选取敏感，可能收敛到局部最优解。此外，K值的确定倚赖于经验，并不完全准确。

3、K均值算法的调优过程如问题一中所述。

参考回答：

K均值算法有一些缺点，例如受初值和离群点的影响，每次的结果不稳定、结果通常不是全局最优而是局部最优解、无法很好地解决数据簇分布差别比较大的情况（比如一类是另一类样本数量的100倍）、不太适用于离散分类等。

但是瑕不掩瑜， K均值聚类的优点也是很明显和突出的，主要体现在对于大数据集，K均值聚类算法相对是可伸缩和高效的，它的计算复杂度 $O(NKt)$ 接近于线性，其中 $N$ 是数据对象的数目， $K$ 是聚类的簇数， $t$ 是迭代的轮数。尽管算法经常以局部最优结束，但一般情况下达到的局部最优已经可以满足聚类的需求。

K均值算法的调优一般可以从以下几个角度出发：

1）数据归一化和离群点处理。

K均值聚类本质上是一种基于欧式距离度量的数据划分方法，均值和方差大的维度将对数据的聚类结果产生决定性的影响，所以未做归一化处理和统一单位的数据是无法直接参与运算相比较的。同时离群点或者少量的噪声数据就会对均值产生较大的影响，导致中心偏移，因此使用K均值聚类算法之前通常需要对数据做预处理。

2）合理选择K值。

K值的选择是K均值聚类最大的问题之一，这也是K均值聚类算法的主要缺点。实际上，我们希望能够找到一些可行的办法来弥补这一缺点，或者说找到K值的合理估计方法。但是，K值的选择一般基于经验和多次实验结果。例如采用手肘法，我们可以尝试不同的K值，并将不同K值所对应的损失函数画成折线，横轴为K的取值，纵轴为误差平方和所定义的损失函数，如图。

手肘法是一个经验方法，缺点就是不够自动化，因此研究员们又提出了一些更先进的方法，其中包括比较有名的Gap Statistic方法。

Gap Statistic方法的优点是，不再需要肉眼判断，而只需要找到最大的 Gap Statistic所对应的K即可，因此该方法也适用于批量化作业。在这里我们继续使用上面的损失函数，当分为K簇时，对应的损失函数记为 $D_k$ 。Gap Statistic定义为：

$Gap(K)=E(\log D_k)-\log D_k$

其中 $E(\log D_k)$ 是 $\log D_k$ 的期望，一般通过蒙特卡洛模拟产生。我们在样本所在的区域内按照均匀分布随机地产生和原始样本数一样多的随机样本，并对这个随机样本做K均值，得到一个 $D_k$ ，重复多次就可以计算出 $E(\log D_k)$ 的近似值。

$Gap(K)$ 可以视为随机样本的损失与实际样本的损失之差。试想实际样本对应的最佳簇数为K，那么实际样本的损失应该相对较小，随机样本损失与实际样本损失之差也相应地达到最大值，从而 $Gap(K)$ 取得最大值所对应的K值就是最佳的簇数。

3）采用核函数。

传统的欧式距离度量方式，使得K均值算法本质上假设了各个数据簇的数据具有一样的先验概率并呈现球形或者高维球形分布，这种分布在实际生活中并不常见。面对非凸的数据分布形状时，可能需要引入核函数来优化，这样的算法又称为核K均值算法，是核聚类方法的一种。核聚类方法的主要思想是通过一个非线性映射，将输入空间中的数据点映射到高位的特征空间中，并在新的特征空间中进行聚类。非线性映射增加了数据点线性可分的概率，从而在经典的聚类算法失效的情况下，通过引入核函数可以达到更为准确的聚类结果。

1.3、针对K均值算法的缺点，有哪些改进的模型？

我的回答：

触及知识盲区……

参考答案：

K均值算法的主要缺点如下：

1）需要入工预先确定初始K值，且该值和真实的数据分布未必吻合。

2）K均值只能收敛到局部最优，效果受到初始值影响很大。

3）易受到噪点的影响。

4）样本点只能被划分到单一的类中。

1、k-means++算法

K均值的改进算法中，对初始值选择的改进是很重要的一部分。而这类算法中，最具影响力的当属K-means++算法。

原始K均值算法最开始随机选取数据集中 $K$ 个点作为聚类中心，而K-means++按照如下的思想选取 $K$ 个聚类中心。假设已经选取了 $n$ 个初始聚类中心（ $0<n<K$ ），则在选取第 $n+1$ 个聚类中心时，距离当前 $n$ 个聚类中心远的点会有更高的概率被选为第 $n+1$ 个聚类中心。在选取第一个聚类中心（ $n=1$ ）时同样通过随机的方法。

当选择完初始点后，K-means++后续的执行和经典K均值算法相同，这也是对初始值选取进行改进的方法的共同点。

2、ISODATA算法

ISODATA的全称是迭代自组织数据分析法。在K均值算法中，聚类个数K的值需要预先人为地确定，并且在整个算法过程中无法更改。而当遇到高维度的海量数据集时，人们往往很难准确地估计出K的大小。ISODATA算法就是针对这个问题进行了改进，它的思想也很直观，当属于某个类别的样本数过少时把该类别去除，当属于某个类别的样本数过多、分散程度较大时把该类别分为两个子类别。ISODATA算法在K均值算法的基础之上增加了两个操作，一是分裂操作，对应着增加聚类中心数，二是合并操作，对应着减少聚类中心数。ISODATA算法是一个比较常见的算法，其缺点是需要指定的参数比较多，不仅仅需要一个参考的聚类数量K，还需要制定3个阈值。下面介绍ISODATA算法的各个输入参数。

1）预期的聚类中心数目 $K_0$ 。在ISODATA运行过程中聚类中心数可以变化。 $K_0$ 是一个用户指定的参考值，该算法的聚类中心数目变动范围也由其决定。具体地，最终输出的聚类中心数目常见范围是从 $K_0$ 的一半，到两倍 $K_0$ 。

2）每个类所要求的最少样本数目 $N_{min}$ 。如果分裂后会导致某个子类别所包含样本数目小于该阈值，就不会对该类别进行分裂操作。

3）最大方差 $\Sigma$ 。用于控制某个类别中样本的分散程度。当样本的分散程度超过这个阈值时，一旦分裂后满足1）2），进行分裂操作。

4）两个聚类中心之间所允许最小距离 $D_{min}$ 。如果两个类靠得非常近（即这两个类别对应聚类中心之间的距离非常小），小于该阈值时，则对这两个类进行合并操作。

1.4、证明K均值算法的收敛性。

我的回答：

与EM算法收敛性证明相同，见这里。

参考答案：

K均值聚类的迭代算法实际上是一种最大期望算法（Expectation Maximization algorithm），简称EM算法。

EM算法的证明在学习《统计学习方法》时已经做过记录，链接同上。

这里主要说明一下K均值算法和EM算法的联系。K均值算法等价于用EM算法求解以下含隐变量的最大似然问题：

$P\left(x, z | \mu_{1}, \mu_{2}, \ldots, \mu_{k}\right) \propto\left\{\begin{array}{c}{\exp \left(-\left\|x-\mu_{z}\right\|_{2}^{2}\right),\left\|x-\mu_{z}\right\|_{2}=\min _{k}\left\|x-\mu_{k}\right\|_{2}} \\ {0 \quad \quad\quad \quad \quad\quad\quad,\left\|x-\mu_{z}\right\|_{2}>\min _{k}\left\|x-\mu_{k}\right\|_{2}}\end{array}\right.$

其中 $z\in \{1,2,\dots,k \}$ 是模型的隐变量。直观地理解，就是当样本 $x$ 离第 $k$ 个簇的中心点的距离最近时，概率正比于 $\exp \left(-\left\|x-\mu_{z}\right\|_{2}^{2}\right)$ ，否则为0。

在E步骤，计算：

$Q_{i}\left(z^{(i)}\right)=P\left(z^{(i)} | x^{(i)}, \mu_{1}, \mu_{2}, \ldots, \mu_{k}\right) \propto\left\{\begin{array}{l}{1,\left\|x^{(i)}-\mu_{z^{(i)}}\right\|_{2}=\min _{k}\left\|x-\mu_{k}\right\|_{2}} \\ {0,\left\|x^{(i)}-\mu_{z^{(i)}}\right\|_{2}>\min _{k}\left\|x-\mu_{k}\right\|_{2}}\end{array}\right.$

这等同于在K均值算法中对于每一个点 $x^{(i)}$ 找到当前最近的簇 $z^{(i)}$ 。

在M步骤，找到最优的参数 $θ=\{\mu_1,\dots,\mu_k \}$ 使得似然函数最大：

$\theta=\underset{\theta}{\operatorname{argmax}} \sum_{i=1}^{m} \sum_{z^{(i)}} Q_{i}\left(z^{(i)}\right) \log \frac{P\left(x^{(i)}, z^{(i)} | \theta\right)}{Q_{i}\left(z^{(i)}\right)}$

经过推导可得：

$\sum_{i=1}^{m} \sum_{z^{(i)}} Q_{i}\left(z^{(i)}\right) \log \frac{P\left(x^{(i)}, z^{(i)} | \theta\right)}{Q_{i}\left(z^{(i)}\right)}=\text { const }-\sum_{i=1}^{m}\left\|x^{(i)}-\mu_{z^{(i)}}\right\|^{2}$

因此这一步等同于找到最优中心 $\mu_1,\dots,\mu_k$ ，使损失函数 $\sum_{i=1}^{m}\left\|x^{(i)}-\mu_{z^{(i)}}\right\|^{2}$ 达到最小，此时每个样本 $x^{(i)}$ 对应的簇 $z^{(i)}$ 已经确定，因此每个簇 $k$ 对应的最优中心点 $\mu_k$ 可以由该簇中所有点的平均计算得到，这与K均值算法中根据当前簇的分配更新聚类中心的步骤是等同的。

2、高斯混合模型

高斯混合模型（Gaussian Mixed Model,GMM）也是一种常见的聚类算法，与K均值算法类似，同样使用了EM算法进行迭代计算。高斯混合模型假设每个簇的数据都是符合高斯分布的，当前数据呈现的分布就是各个簇的高斯分布叠加在一起的结果。

理论上，高斯混合模型可以拟合出任意类型的分布。

2.1、高斯混合模型的核心思想是什么？它是如何迭代计算的？

我的回答：

1、高斯混合模型的核心思想就是将样本分布视作各个簇的高斯分布叠加在一起的结果。如此一来我们只需要使混合高斯分布生成当前样本的似然函数最大即可求得各高斯成分的参数。

2、如上所述，我们最终的优化目标是最大化一个似然函数，且该似然函数是非凸的和的对数的形式，因此要通过EM算法来求解。

参考答案：

1、高斯混合模型的核心思想是：假设数据可以看作从多个高斯分布中生成出来的。在该假设下，每个单独的分模型都是标准高斯模型，其均值 $\mu_i$ 和方差 $\Sigma_i$ 是待估计的参数。此外，每个分模型都还有一个参数 $\pi_i$ ，可以理解为权重或生成数据的概率。高斯混合模型的公式为：

$p(x)=\sum_{i=1}^K \pi_i N(x|\mu_i,\Sigma_i)$

高斯混合模型是一个生成式模型。可以这样理解数据的生成过程，设一个最简单的情况，即只高两个一维标准高斯分布的分模型 $N(0,1)$ 和 $N(5,1)$ ，其权重分别为 $0.7$ 和 $0.3$ 。那么，在生成第一个数据点时，先按照权重的比例随机选择一个分布，比如选择第一个高斯分布，接着从 $N(0,1)$ 中生成一个点，如 $0.5$ ，便是第一个数据点。在生成第二个数据点时，随机选择到第二个高斯分布 $N(5,1)$ ，生成了第二个点 $4.7$ 。如此循环执行，便生成出了所有数据点。

2、EM算法是在最大化目标函数时，先固定一个变量使整体函数变为凸优化函数，求导得到最值，然后利用最优参数更新被固定的变量，进入下一个循环。具体到高斯混合模型的求解，EM算法的迭代过程如下：

首先，初始随机选择各参数的值。然后，重复下述两步直到收敛。

1）E步骤。根据当前的参数，计算每个点由某个分模型生成的概率。

2）M步骤。使用E步骤估计出的概率，来改进每个分模型的均值，方差和权重。

也就是说，我们并不知道最佳的 $K$ 个高斯分布的各自 $3$ 个参数，也不知道每个数据点究竟是哪个高斯分布生成的。所以每次循环时，先固定当前的高斯分布不变，获得每个数据点由各个高斯分布生成的概率。然后固定该生成概率不变，根据数据点和生成概率获得一组更佳的高斯分布。循环往复，直到参数的不再变化，或者变化非常小时，便得到了比较合理的一组高斯分布。

3、自组织映射神经网络

自组织映射神经网络（Self-Organizing Map,SOM）是无监督学习中一类重要方法，可以用作聚类、高维可视化、数据压缩、特征提取等多种用途。在深度神经网络大为流行的今天，谈及自组织映射神经网络依然是一件非常有意义的事情，这主要是由于自组织映射神经网络融入了大量人脑神经元的信号处理机制，高着独特的结构特点。

3.1、自组织映射神经网络是如何工作的？它与K均值算法有何区别？

我的回答：

触及知识盲区了……

参考答案：

1、生物学研究表明，在人脑的感知通道上，神经元组织是有序排列的，同时，大脑皮层会对外界特定时空信息的输入在特定区域产生兴奋，而且类似的外界信息输入产生对应兴奋的大脑皮层区域也是连续映像的。例如，生物视网膜中有许多特定的细胞对特定的图形比较敏感，当视网膜中有若干个接收单元同时受特定模式剌激时，就使大脑皮层中的特定神经元开始兴奋，当输入模式接近时与之对应的兴奋神经元也接近。大脑皮层中神经元的这种响应特点不是先天安排好的，而是通过后天的学习自组织形成的。

在生物神经系统中，还存在着一种侧抑制现象，即一个神经细胞兴奋后，会对周围其他神经细胞产生抑制作用。这种抑制作用会使神经细胞之间出现竞争，其结果是某些获胜，而另一些则失败。表现形式是获胜神经细胞兴奋，失败神经细胞抑制。

自组织神经网络就是对上述生物神经系统功能的一种人工神经网络模拟。

自组织映射神经网络本质上是一个两层的神经网络，包含输入层和输出层（竞争层）。输入层模拟感知外界输入信息的视网膜，输出层模拟做出响应的大脑皮层。输出层中神经元的个数通常是聚类的个数，代表每一个需要聚成的类。训练时采用“竞争学习”的方式，每个输入的样例在输出层中找到一个和它最匹配的节点，称为激活节点。紧接着用随机梯度下降法更新激活节点的参数；同时，和激活节点临近的点也根据它们距离激活节点的远近而适当地更新参数。这种竞争可以通过神经元之间的横向抑制连接（负反馈路径）来实现。

自组织映射神经网络的输出层节点是有拓扑关系的。这个拓扑关系依据需求确定，如果想要一维的模型，那么隐藏节点可以是“ 一维线阵” ；如果想要二维的招扑关系，那么就形成一个“二维平面阵”，如图所示。

假设输入空间是 $D$ 维，输入模式为 $x=\{x_i,i=1,\dots,D\}$ ，输入单元 $i$ 和神经元 $j$ 之间在计算层的连接权重为 $w=\{w_{ij},i=1,\dots,D,j=1,\dots,N\}$ ，其中 $N$ 是神经元总数。自组织映射神经网络的学习过程可以归纳为以下几个子过程：

1）初始化。所有连接权重都用小的随机值进行初始化。

2）竞争。神经元计算每个输入模式各自的判别函数值，并宣布具有最小判别函数值的特定神经元为胜利者，其中每个神经元 $j$ 的判别函数为 $d_j(x)=\sum_{i=1}^D (x_i-w_{ij})^2$ 。

3）合作。获胜神经元 $I(x)$ 决定了兴奋神经元拓扑邻域的空间位置。确定激活结点 $I(x)$ 之后，我们也希望重新和它临近的节点。更新程度计算如下：

$T_{j,I(x)}(t)=\exp(-\frac{S_{j,I(x)}^2}{2\sigma(t)^2})$

其中 $s_{ij}$ 表示竞争层神经元 $i$ 和 $j$ 的距离， $\sigma(t)=\sigma_0 \exp(-\frac{t}{\tau_\sigma})$ 随时间衰减，简单地说，临近的节点距离越远，更新程度越小。

4）适应。适当调整相关兴奋神经元的连接权重，使得获胜的神经元对相似输入模式的后续应用的响应增强：

$\Delta w_{ij}=\eta(t)\cdot T_{j,I(x)}(t)\cdot (x_i-w_{ij})$

其中依赖于时间的学习率定义为 $\eta(t)=\eta_0 \exp(-\frac{t}{\tau_\eta})$ 。

5）迭代。继续回到步骤（2），直到特征映射趋于稳定。在迭代结束之后，每个样本所激活的神经元就是它对应的类别。

由其学习过程可以看出，每个学习权重更新的效果等同于将获胜的神经元及其邻近的权向量 $w$ 向输入向量 $x$ 移动，同时对该过程的迭代进行会使得网络的拓扑有序。

在自组织映射神经网络中，获胜的神经元将使得相关的各权重向更加有利于竞争的方向调整，即以获胜神经元为中心，对近邻的神经元表现出兴奋性侧反馈，而对远邻的神经元表现出抑制性侧反馈，近邻者相互激励，远邻者相互抑制。这种交互作用的方式以曲线可视化则类似“墨西哥帽”，如图所示：

总结来说，自组织映射神经网络所做的事情就是：对当前样本 $x$ 找到激活神经元，然后调整与激活神经元连接的权值使其与 $x$ 更加类似，然后距离这个激活神经元较近的神经元也会将连接权重向 $x$ 的方向调整（这样起到的效果实际上是使得距离近的神经元与各输入单元连接的权值相似），因此最终两个样本对应的激活神经元距离越远，意味着这两个样本对应的类别相差越大（或者说越不相似）。

2、自组织映射神经网络与K均值算法的区别如下：

1）K均值算法需要事先定下类的个数，也就是K的值。而自组织映射神经网络则不用。隐蘸层中的某些节点可以没有任何输入数据属于它，因此聚类结果的实际簇数可能会小于神经元的个数。而K均值算法受K值设定的影响要重大一些。

2）K均值算法为每个输入数据找到一个最相似的类后，只更新这个类的参数；自组织映射神经网络则会更新临近的节点。所以，K均值算法受noise data的影响比较大，而自组织映射神经网络的准确性可能会比K均值算法低（因为也更新了临近节点）。

3）相比较而言，自组织映射神经网络的可视化比较好，而且具有优雅的拓扑关系图。

3.2、怎样设计自组织映射神经网络并设定网络训练参数？

我的回答：

知识盲区……

参考答案：

1、设定输出层神经元的数量。

输出层神经元的数量和训练集样本的类别数相关。若不清楚类别数则尽可能地设定较多的节点数，以便较好地映射样本的拓扑结构，如果分类过细再酌情减少输出节点。这样可能会带来少量从未更新过权值的“死节点”，但一般可通过从新初始化权值解决。

2、设计输出层节点的排列。

输出层的节点排列成哪种形式取决于实际应用的需要，排列形式应尽量直观地反映出实际问题的物理意义。例如，对于一般的分类问题，一个输出节点能代表一个模式类，用一维线阵既结构简单又意义明确；对于颜色空间或者旅行路径类的问题，二维平面则比较直观。

3、初始化权值。

可以随机初始化，但尽量使权值的初始位置与输入样本的大概分布区域充分重合，避免出现大量的初始“死节点”。一种简单易行的方法是从训练集中随机抽取 $m$ 个输入样本作为初始权值。

4、设计拓扑领域。

拓扑领域的设计原则是使领域不断缩小，这样输出平面上相邻神经元对应的权向量之间既有区别又有相当的相似性，从而保证当获胜节点对某一类模式产生最大响应时，其领域节点也能产生较大响应。领域的形状可以是正方形、六边形或者菱形。优势领域的大小用领域的半径表示，通常凭借经验来选择。

5、设计学习率。

学习率是一个递减的函数，可以结合拓扑邻域的更新一起考虑，也可分开考虑。在训练开始时，学习率可以选取较大的值，之后以较快的速度下降，这样有利于很快地捕捉到输入向量的大致结构，然后学习率在较小的值上缓降至0值，这样可以精细地调整权值使之符合输入空间的样本分布结构。

4、聚类算法的评估

4.1、以聚类问题为例，假设没有外部标签数据，如何评估两个聚类算法的优劣？

我的回答：

在没有标签数据的情况下，我们可以设定一个带正则项的损失函数，比如各簇中样本到各簇中心点距离的平方和再加上正则项系数乘以簇的个数。

参考答案：

相比于监督学习，非监督学习通常没有标注数据，模型、算法的设计直接影响最终的输出和模型的性能。为了评估不同聚类算法的性能优劣，我们需要了解常见的数据簇的特点。

以中心定义的数据簇

这类数据集合倾向于球形分布，通常中心被定义为质心，即此数据簇中所有点的平均值。集合中的数据到中心的距离相比到其他簇中心的距离更近。

以密度定义的数据簇

这类数据集合呈现和周围数据簇明显不同的密度，或稠密或稀疏。当数据簇不规则或互相盘绕，并且有噪声和离群点时，常常使用基于密度的簇定义。

以连通定义的数据簇

这类数据集合中的数据点和数据点之间有连接关系，整个数据簇表现为图结构。该定义对不规则形状或者缠绕的数据簇有效。

以概念定义的数据簇

这类数据集合中的所有数据点具有某种共同性质。

聚类评估的任务是估计在数据集上进行聚类的可行性，以及聚类法产生结果的质量。这一过程又分为三个子任务。

1）估计聚类趋势

这一步骤是检测数据分布中是否存在非随机的簇结构。如果数据是基本随机的，那么聚类的结果也是毫无意义的。我们可以观察聚类误差是否随聚类类别数量的增加而单调变化，如果数据是基本随机的，即不存在非随机簇结构，那么聚类误差随聚类类别数量增加而变化的幅度应该较不显著，并且也找不到一个合适的K对应数据的真实簇数。

我们也可以应用霍普金斯统计量（Hopkins Statistic）来判断数据在空间上的随机性。首先，从所有样本中随机找 $n$ 个点，记为 $p_1,p_2,\dots,p_n$ ，对其中每个点 $p_i$ ，都在样本空间中找到一个距离最近的点并计算它们之间的距离 $x_i$ ，从而得到距离向量 $x_1,x_2,\dots,x_n$ ，然后在样本的可能取值范围内随机生成 $n$ 个点，记为 $q_1,q_2,\dots,q_n$ ，对其中每个点 $q_i$ ，都在样本空间中找到一个距离最近的点并计算它们之间的距离 $y_i$ ，从而得到距离向量 $y_1,y_2,\dots,y_n$ 。霍普金斯统计量 $H$ 表示为：

$H=\frac{\sum_{i=1}^n x_i}{\sum_{i=1}^n x_i+\sum_{i=1}^n y_i}$

如果样本接近随机分布，那么 $\sum_{i=1}^n x_i$ 和 $\sum_{i=1}^n y_i$ 的取值应该比较接近，即 $H$ 的值接近 $0.5$ ，如果聚类趋势明显，则随机生成的样本点距离应该远大于实际样本点的距离， $\sum_{i=1}^n x_i<<\sum_{i=1}^n y_i$ ， $H$ 的值接近于 $1$ 。

2）判定数据簇数

确定聚类趋势之后，我们需要找到与真实数据分布最为吻合的簇数，据此判定聚类结果的质量。数据簇数的判定方法有很多，例如手肘法和Gap Statistic方法。需要说明的是，用于评估的最佳数据簇数可能与程序输出的簇数是不同的。例如，有些聚类算法可以自动地确定数据的簇数，但可能与我们通过其他方法确定的最优数据簇数有所差别。

3）测定聚类质量

在无监督的情况下，我们可以通过考察簇的分离情况和簇的紧凑情况来评估聚类的效果。定义评估指标可以展现面试者实际解决和分析问题的能力。事实上测量指标可以有很多种，以下列出了几种常用的度量指标：

轮廓系数：给定一个点 $p$ ，该点的轮廓系数定义为：

$s(p)=\frac{b(p)-a(p)}{\max\{a(p),b(p)\}}$

其中 $a(p)$ 是点 $p$ 与同一簇其它点 $p^{'}$ 的平均距离， $b(p)$ 是点 $p$ 与另一个不同簇中的点之间的最小平均距离（如果有 $n$ 个其他簇则只计算和点 $p$ 最接近的一簇中的点与该点的平均距离）。

$a(p)$ 反映的是 $p$ 所属簇中数据的紧凑程度， $b(p)$ 反映的是该簇与其他临近簇的分离程度。显然， $b(p)$ 越大， $a(p)$ 越小，对应的聚类质量越好，因此我们将所有点对应的轮廓系数 $s(p)$ 求平均值来度量聚类结果的质量。

均方根标准偏差：用采衡量聚结果的同质性，即紧凑程度，定义为：

$R M S S T D=\left\{\frac{\sum_{i} \sum_{x \in C_{i}}\left\|x-c_{i}\right\|^{2}}{P \sum_{i}\left(n_{i}-1\right)}\right\}^{\frac{1}{2}}$

真中 $C_i$ 代表第 $i$ 个簇， $c_i$ 是该簇的中心， $n_i$ 为第 $i$ 个簇的样本数量， $P$ 为样本点对应的向量维数。可以看出，分母对点的维度 $P$ 做了惩罚，维度越高，则整体的平方距离度量值越大。RMSSTD可以看作是经过归一化的标准差。

R方（R-Square）：可以用来衡量聚类的差异度，定义为：

$R S=\frac{\sum_{x \in D}\|x-c\|^{2}-\sum_{i} \sum_{x \in C_{i}}\left\|x-c_{i}\right\|^{2}}{\sum_{x \in D}\|x-c\|^{2}}$

其中 $D$ 代表整个数据集， $c$ 代表数据集 $D$ 的中心点，从而 $\sum_{x \in D}\|x-c\|^{2}$ 代表将数据集 $D$ 看作单一簇时的平方误差和。 $\sum_{i} \sum_{x \in C_{i}}\left\|x-c_{i}\right\|^{2}$ 代表将数据集聚类之后的平方误差和，因此 $RS$ 表示聚类后和聚类前相比，对应的平方误差和指标的改进幅度。

葫芦书第五章——非监督学习
在实际工作中，我们经常会遇到这样一类问题：给机器输入大量的特征数据，并期望机器通过学习找到数据中存在的某种共性...
第十三章聚类（Clustering）
13.1 聚类简介聚类是一个非监督学习的算法，监督学习和非监督学习的介绍在第一章：监督学习VS非监督学习 - 简...
吴恩达机器学习笔记-非监督学习
聚类之前的课程中我们学习的都是监督学习相关的算法，现在来开始看非监督学习。非监督学习相对于监督非学习来看，其使用...
监督学习和非监督学习
机器学习分为监督学习、非监督学习和半监督学习（也可以叫强化学习）。在这里我们来区分一下监督学习和非监督学习的区别吧...
11.25 统计学习方法
1.2监督学习统计学习包括监督学习，非监督学习，半监督学习及强化学习。监督学习（supervised lear...
监督学习——学习笔记
前言统计学习包括监督学习、非监督学习、半监督学习及强化学习。监督学习 (supervised learning)...
监督&非监督
机器学习中涉及的学习方式主要有四种： 1.监督学习 2.非监督学习 3.强化学习 4.半监督学习区分：监督与非监...
机器学习分类
监督/非监督学习监督学习 K近邻算法线性回归逻辑回归支持向量机（SVM）决策树和随机森林神经网络非监督学习聚...
Introduction of Machine Learning
解释监督学习：有标签数据半监督学习：部分有标签非监督学习：无标签迁移学习：用非相关数据（含标签）来优化目标...
监督学习，非监督学习
机器学习的定义是：在没有明确设置的情况下，使计算机具有学习能力的领域。一个适当的学习问题定义如下：计算机程序从经...