统计方法ch5-聚类1

首先我们要来了解一下聚类思想。以类识物是人类认识世界的一种重要方式，但是人类自身是没有办法处理眼睛所捕获的大量信息的，因此我们通常会对个体的特征进行归纳，并将相似的个体归并为一类，一次来达到信息的整体性认识。比如说我们看到头上有”王”字的动物会将其归类与老虎，其实捕捉的是老虎脸上的特征。

那么聚类分析有什么作用呢？

• 识别从属特定总体的个体

比如说，研究消费者行为从而将市场进行细分，对消费者精准投放广告或者商品推荐

• 识别异常个体

比如说，检测用户的上网行为从而判断其行为是否正常，对政府企业等重要数据库进行保护以防止黑客攻击

在这一章中，我们主要来解决一下几个问题：

1. 如何定义个体之间的相似性
2. 如何确定类别的数目
3. 如何选取个体的特征
4. 如何评价聚类方法的结果

基本概念

基本定义

我们知道在一些场合下，获取足够多数量的负样本其实是比较困难的。而聚类研究的就是那些无标签的数据集。因此，聚类分析是无监督学习中最为常用且重要的方法之一。数据集可以写成矩阵形式如下：

我们可以将每一行看做是一个样本，第 i 个样本$\boldsymbol{xi} = (x{i1},x{i2},\cdots,x{ip})’$ 可以看做是p维空间中的一个点。那么，按行进行聚类的话，我们可以将相似的个体聚成一类，由此在数据集$\boldsymbol X $​中进行集群发现。

我们可以将每一列看做是一个特征，第j个特征$x^*{j} = (x{1j},x{2j}\cdots,x{nj})’$ 可以看做是n维空间中的一点​，如果按列进行聚类，可以将相似的变量聚成一类，从而对数据集$X$ 进行降维

在这一章我们主要来了解集群发现，也就是按行聚类

距离的意义

点间距离

连续变量的点间距离

欧氏距离

说起距离，最容易想到的就是欧氏距离了，即对两个样本$\boldsymbol{xk}=(x{k1},\cdots,x{kp})’$ 和 $\boldsymbol{x_l}=(x{l1},\cdots,x_{lp})’$​ 的欧氏距离为：

$$||x_k-x_l||_2 = \sqrt{\sum_{j=1}^p(x_{kj}-x_{lj})^2}$$

我们如果要计算p维空间的两个点之间的距离，相当于求矩阵中第k行和第l行的距离，那么我们要对每个对应的点求平方和在进行开方。

在二维空间中，如下图所示

欧式距离度量的是欧几里得空间中的直线距离

平方欧氏距离

$$||x_k-x_l||_2^2 = \sum_{j=1}^p(x_{kj}-x_{lj})^2$$

闵式距离

闵式距离是包含欧氏距离的

$$(\sum_{j=1}^p(x_{kj}-x_{lj})^q)^{\frac{1}{q}}$$

当q=2的时候，闵式距离和欧氏距离是等价的

还有一写特殊的闵式距离——绝对距离和最大距离

曼哈顿距离(绝对距离)

当q取1的时候，闵式距离变成了曼哈顿距离又称为绝对距离

$$||\boldsymbol{x_k}-\boldsymbol{x_l}||_1 = \sum_{i=1}^p|x_{kj}-x_{lj}|$$

切比雪夫距离(最大距离)

当q取无穷大的时候，闵式距离变成了最大距离

$$||\boldsymbol{x_k}-\boldsymbol{x_l}||_\infty = \max_{j}|x_{kj}-x_{lj}|$$

用来度量所有维度中差异最大的那个维度

兰氏距离

$$\sum_{j=1}^p \frac{|x_{kj}-x_{lj}|}{|x_{kj}|+|x_{lj}|}$$

兰氏距离可以看做是加权的曼哈顿距离，它对接近于零的值的变化非常敏感，且对量纲不敏感。而曼哈顿距离对量纲是很敏感的。

因此若$|x_{kj}|$ 非常接近于0的话，兰氏距离会非常大

马氏距离

马氏距离又称为是广义欧氏距离

$$\sqrt{(\boldsymbol{x_k}-\boldsymbol{x_l})'\Sigma^{-1}(\boldsymbol{x_k}-\boldsymbol{x_l})}$$

其中Σ是多维随机变量的协方差矩阵，当$\Sigma = \boldsymbol I_p$ ，即$\Sigma$​​为单位阵的时候，说明各个维度独立同分布，因此马氏距离等于欧氏距离

马氏距离实际意义

那么马氏距离就能干什么？它比欧氏距离好在哪里？举几个栗子

欧式距离近就一定相似？

先举个比较常用的例子，身高和体重，这两个变量拥有不同的单位标准，也就是有不同的scale。比如身高用毫米计算，而体重用千克计算，显然差10mm的身高与差10kg的体重是完全不同的。但在普通的欧氏距离中，这将会算作相同的差距。

归一化后欧氏距离近就一定相似？

当然我们可以先做归一化来消除这种维度间scale不同的问题，但是样本分布也会影响分类

举个一维的栗子，现在有两个类别，统一单位，第一个类别均值为0，方差为0.1，第二个类别均值为5，方差为5。那么一个值为2的点属于第一类的概率大还是第二类的概率大？距离上说应该是第一类，但是直觉上显然是第二类，因为第一类不太可能到达2这个位置。

所以，在一个方差较小的维度下很小的差别就有可能成为离群点。就像下图一样，A与B相对于原点的距离是相同的。但是由于样本总体沿着横轴分布，所以B点更有可能是这个样本中的点，而A则更有可能是离群点。

算上维度的方差就够了？

还有一个问题——如果维度间不独立同分布，样本点一定与欧氏距离近的样本点同类的概率更大吗？

可以看到样本基本服从f(x) = x的线性分布，A与B相对于原点的距离依旧相等，显然A更像是一个离群点

即使数据已经经过了标准化，也不会改变AB与原点间距离大小的相互关系。所以要本质上解决这个问题，就要针对主成分分析中的主成分来进行标准化。

马氏距离的几何意义

上面搞懂了，马氏距离就好理解了，只需要将变量按照主成分进行旋转，让维度间相互独立，然后进行标准化，让维度同分布就OK了

由主成分分析可知，由于主成分就是特征向量方向，每个方向的方差就是对应的特征值，所以只需要按照特征向量的方向旋转，然后缩放特征向量倍就可以了，可以得到以下的结果：

离群点就被成功分离，这时候的欧式距离就是马氏距离。

现在我们可以来推导一下马氏距离：

首先要对数据点进行旋转，旋转至主成分使得维度间线性无关，假设新的坐标为：

$$F = (F_1,F_2\cdots,F_m) = U^TX\\ \mu_F = (\mu_1,\mu_2,\cdots,\mu_m)\\ (F- \mu_F)= U^T (X-\mu_X)$$ $$(F-\mu_F)(F-\mu_F)^T = \begin{bmatrix}\lambda_1\\&\lambda_2\\&&\cdots\\&&&\lambda_m\end{bmatrix}\\ =U^T(X-\mu_X)(X-\mu_X)^TU\\ =U^T\Sigma_XU$$

马氏距离是旋转变换缩放后的欧氏距离没所以马氏距离的计算公式可以写为：

$$D^2_M = (\frac{f_1-\mu_{F_1}}{\sqrt{\lambda_1}})^2+\cdots+(\frac{f_2-\mu_{F_2}}{\sqrt{\lambda_2}})^2\\=(f_1-\mu_{F_1},f_2-\mu_{F_2},\cdots,f_M-\mu_{F_M})\begin{bmatrix}\frac{1}{\lambda_1}\\&\frac{1}{\lambda_2}\\&&\cdots\\&&&\frac{1}{\lambda_m}\end{bmatrix}\begin{pmatrix}f_1-\mu_{F_1}\\f_2-\mu_{F_2}\\\cdots\\f_m-\mu_{F_m} \end{pmatrix}\\ =(f-\mu_F)^T(U^T\Sigma_X U^{-1})(f-\mu_F)\\ =(x-\mu_X)^TUU^T\Sigma_X^{-1}UU^T(x-\mu_X)\\ =(x-\mu_X)^T\Sigma_X^{-1}(x-\mu_X)$$

皮尔逊线性相关系数

余弦相似度

余弦相似度的定义为：

$$\cos\theta = \frac{\sum_{j=1}^p x_{kj}x_{lj}}{\sqrt{\sum_{j=1}^px_{kj}^2\sum_{j=1}^px^2_{lj}}}$$

余弦距离是由两个向量之间夹脚的余弦公式得到的

$$\cos\theta = \frac{\boldsymbol{a'b}}{\boldsymbol{|a||b|}}$$

当余弦为1时，说明两个向量完全相似，此时距离为0

余弦相关距离=1-$\cos\theta$

肯德尔秩相关系数

现在我们来介绍秩相关系数，我们用秩来代替原来的数值，是因为我们要规避一些极端数值带来的影响

肯德尔相关系数，又称肯德尔秩相关系数，它是一种秩相关系数，不过，它的目标对象是有序的类别变量，比如名次、年龄段、肥胖等级(重度肥胖，中度肥胖、轻度肥胖、不肥胖)等。它可以度量两个有序变量之间单调关系强弱。肯德尔相关系数使用了“成对“这一概念来决定相关系数的强弱。

成对可以分为协同对(Concordant)和不协同对(Discordant)。协同对是指两个变量取值的相对关系一致，可以理解为$X_2-X_1$与$Y_2-Y_1$有相同的符号；分歧对则是指它们的相对关系不一致，$X_2-X_1$与$Y_2-Y_1$有着相反的符号。

肯德尔秩的相关系数是基于观测值中两个特征同时增加或者同时减少的个数从而计算相关系数

• 协同对:$(x{kj}-x{kj’})(x{lj}-x{lj’})>0$
• 不协同对：$(x{kj}-x{kj’})(x{lj}-x{lj’})<0$

那么，肯德尔相关系数的定义如下：

$$\text{Kendall}~\tau = \frac{n_c-n_d}{p(p-1)/2}$$

其中，$n_c$​表示协同对的个数，而$n_d$​表示不协同对的个数，$p(p-1)/2$ 代表总对数。

如果两个属性排名是相同的，系数为1 ，两个属性正相关。

如果两个属性排名完全相反，系数为-1 ，两个属性负相关。

我们来举一个例子：

肯德尔相关距离=1-Kendall $\tau $

斯皮尔曼秩相关系数

斯皮尔曼秩相关系数类似于皮尔逊相关系数，只不过将原始数据$x{kj}$​ 用其秩$r{kj}$​ 来代替

将$\boldsymbol x{k}$ 的各个分量$x{k1}\cdots, x{k2},\cdots,x{kp}$ 按从小到大排序，计算每一个分量所对应的秩，记为$r{k1},r{k2},\cdots,r_{kp}$

$$\text{Spearman} ~~\rho = \frac{\sum_{j=1}^p(r_{kj}-\overline r_{kj})(r_{lj}-\overline r_{lj})}{\sqrt{\sum_{j=1}^p(r_{kj}-\overline r_{kj})^2\sum_{j=1}^p(r_{lj}-\overline r_{lj}})^2}$$

通过化简我们可以得到更精简的式子：

$$\rho = 1-\frac{6\sum d_i^2}{n(n^2-1)}$$

我们用具体的例子来解释计算过程：

原始位置	原始X	排序后	秩次X’	原始Y	排序后	秩次Y’	秩次差$d_i$的平方
1	11	490	5	2	75	6	1
2	490	43	1	75	44	1	0
3	14	30	4	3	42	5	1
4	43	14	2	44	7	2	0
5	30	11	3	7	3	4	1
6	3	3	6	42	2	3	9

代入公式，得到：$\rho = 1-\frac{6(1+1+1+9)}{6(36-1 )} = 0.657$

斯皮尔曼相关距离 = 1-Spearman $\rho$​​

混合变量的点间距离

刚才定义的点间距离都是在连续场合定义的，那么如果我们的数据既有连续场合又有离散场合该怎么办？我们需要用统一的量纲去度量才能保证距离是靠谱的。

我们可以令$sj = s_j(x{kj}-x_{lj})$ 为第k个观测值和第l个观测值在第j个特征或变量之间的相似性。通过$s_j$​ 来定义点与点之间的距离$d_j$, 即 $s_j = 1-d_j$​​​

定性变量

比如说，我们考虑性别是否为男性、产品的颜色是否为黑色等，这些特征$x{kj}$和$x{lj}$ 均为定性变量。两者相等即为1，否则即为0；那么我们可以定义相似性为：

$$s_j = s_j(x_{kj},x_{lj}) = \begin{cases}1&x_{kj}=x_{lj}\\0&x_{kj}\neq x_{lj} \end{cases}$$

定量变量

比如考虑年龄、产品的价格等，这些特征$x{kj}$ 和$x{lj}$ 均为定量变量，那么我们可以定义相似性为：

$$s_j = s_j(x_{kj},x_{lj}) = 1-\frac{|x_{kj}-x_{lj}|}{R_j}$$

其中，$Rj$ 表示第j个特征的极差，即$R_j = \max_ix{ij}-\minix{ij}$​ ，也就是进行一个归一化后的绝对距离

定序变量

比如考虑文化程度、空气质量指数级别等，这些特征$x{kj}$和$x{lj}$​ 均为定序变量。那么我们要对$x{1j},x{2j},\cdots,x{nj}$ 从小到大进行排序，并分别计算其秩，记为$r{1j},r{2j},\cdots,r{nj}$​ 。

通常我们定义相似性为：

$$s_j = s_j(x_{kj},x_{lj}) = 1-\frac{|r_{kj}-r_{lj}|}{\max_k r_{kj}-\min_k r_{kj}}$$

相似度

上面说的都是观测点之间的相似性，现在我们来定义两个观测$\boldsymbol{x}_k,\boldsymbol{x}_l$ 之间的相似度：

$$s_j(\boldsymbol x_{k}-\boldsymbol x_{l}) = \frac{\sum_{j=1}^ps_j(x_{kj},x_{lj})\delta(x_{kj},x_{lj})w_j}{\sum_{j=1}^p\delta(x_{kj},x_{lj})w_j}$$

其中$\delta(x{kj},x{lj})$ 表示观测值中是否存在确是观测，即

$$\delta(x_{kj},x_{lj}) = \begin{cases}0,&\text{如果}x_{kj}\text{或}x_{lj}\text{存在缺失观测}\\1,&\text{其他} \end{cases}$$

$w_j$ 表示权重，一般取值为1，但是如果事先知道第j个特征尤其重要，可以增加相应的权重。

类间距离

由一个点组成的类是最基本的类，如果每一类都由一个点组成，那么点间距离就是类间距离。

那么，如果某一类上包含不止一个点，就要定义类间距离，也称关联准则。

sinple linkage

将两个类中距离最短的两个点之间的距离定为类间距离，称 sinple linkage, 如下图所示：

complete linkage

将两个类中剧里最长的两个点之间的距离定义为类间距离，称为complete linkage

centroid linkage

将两个类中所有的点的重心距离定义为类间距离，称为 centroid linkage

关联准则

为了同一副好，我们将点也看做是类，因此把点(类)k与l之间的距离用$d(k,l)$ 表示。如果点(或者类)k与l聚合成一个类，记为$k\cup l$ ，对于任何其他的一个点(或者类)i，那么类($k \cup l$)与点或类i之间的距离记为$d(k\cup l,i)$

Lance-Williams 公式为：

$$d(k\cup l,i) = \alpha_k d(k,i)+\alpha_ld(l,i)+\beta d(k,l)+\gamma ~|d(k,i)-d(l,i)|$$

其中，$\alpha_k,\alpha_l,\beta,\gamma$​

如果我们使用single-linkage,三个参数分别是0.5，0.5，0.5，我们来推一下：

$$d(k\cup l,i) = \frac{1}{2} d(k,i)+\frac{1}{2}d(l,i)-\frac{1}{2}|d(k,i)-d(l,i)|\\ =\frac{1}{2}|d(k,i)+d(l,i)|-\frac{1}{2}|d(k,i)-d(l,i)|$$

如果$d(k,i)>d(l,i)$,原式等于 $d(l,i)$;

如果$d(k,i)<d(l,i)$，原式等于 $d(k,i)$

符合 single-linkage的定义

层次聚类

在博客：https://jasonxqh.github.io/2020/10/25/Hierarchical-Clustering/ 中介绍过层次聚类，现在我们从数学方面来看一下

层次聚类一般有两种不同的形式，自下而上和自上而下

自下而上：每个样本各自分到一个类中，之后将类间距离最近的两类关联，并建立一个新的类，反复此过程直到所有的样本聚合至一个类中；
自上而下：将所有样本归到一个类中，之后将在类中相距最远的样本记为两个新的类，基于这两个类，将未进行聚类的点逐一比较其与两个新的类的距离，这样所有样本划分成了两类，在每一个类中重复此过程直到每个样本点各自分到一个类中；

一般来说都会选择自下而上方法，自上而下会比较麻烦。

我们给一个例题：假设有4个点，距离矩阵为：

找到欧式距离最近的两个类，是A和B，距离为1，把他们聚成一类。然后我们要计算$d(A\cup B,C),d(A\cup B,D)$

我们不妨采用simple linkage，那么$A\cup B$​到C 的距离是A到C的距离与B到C距离的最小值, 即3；那么$A\cup B$​​​到D 的距离是A到D的距离与B到D距离的最小值,即2

因此，重新得到的距离矩阵为：

接着我们找出距离最近的两个类，A,B和D，把他们聚成一类

$A,B\cup D$ 到C的距离是A,B到C的距离与D到C的距离的最小值，即3，因此我们再次更新距离矩阵如下：

最后可以将A,B,C,D 聚成一类

K-Means 聚类

K-Means我在博客https://jasonxqh.github.io/2020/10/22/K-Means%E8%81%9A%E7%B1%BB/ 有所介绍。 现在我们从数学角度再来学习一下。

K-Means 是最简单的无监督学习方法之一，且计算速度快，因此也被称为快速聚类

相较于层次聚类，K均值聚类实现确定聚类数目，这里假定聚类的数目为K(K<n)

那么对于给定n个样本集 $X= (\boldsymbol x_1,\cdots,\boldsymbol x_n)’$ ，K-Means 的目标就是将n个样本划分到K个不同的类中，这K个类$C_1,C_2,\cdots,C_k$ 形成了样本集X的划分，即：

$$C_k\cap C_l = \empty,\bigcup_{k=1}^K C_k = X$$

输出的划分 $\mathcal C = {C_1,C_2,\cdots,C_k}$ 可以对应一个聚类结果

目标与思想

我们的目标是，希望能找到一个最优化分$\mathcal C^*$​​ ，使得类内距离足够小而类间距离足够大。这和聚类的思想是一致的，即相似的放在同一簇中，不相似的放在不同簇当中。一般来说，我们使用平方欧氏距离来表示点与点之间的距离 ，即：

$$d_{kl} = d(k,l)=||\boldsymbol x_k-\boldsymbol x_l||_2^2= \sum_{j=1}^p(x_{kj}-x_{lj})^2$$

由此，我们可以定义一个合理的损失函数, 如下：

$$W(\mathcal C) = \sum_{k=1}^{n_k}\sum_{i\in C_k}||\boldsymbol x_i-\boldsymbol m_k||^2$$

• $\boldsymbol m_k$ 表示第k类的均值或中心
• 这里$n_k$​是第k类中样本的个数

而K均值聚类实际上就是解决一个最优化问题：

$$\mathcal C^* = \arg\min_C W(\mathcal C)$$

这是一个NP-Hard问题，可以用迭代法求解。

步骤

通常采用迭代法来求解区 均值聚类的问题，每次迭代包括两个步骤：

• 确定K个类的中心$\boldsymbol m_k$，将样本逐一分配到其最近的中心所对应的类中，得到一个聚类结果；
• 更新每个类的样本均值，作为类的更新后的中心；重复此过程，直到收敛为止。

注意事项：

• 收敛条件，通常可以设置为：聚类结果不变；
• 复杂度是$O(pnK)$，其中p表示特征个数，n 表示样本个数，K是聚类数目；
• 如果各个类的数据集非凸，基于非凸性质，我们可以构造出一个数据集，存在一个点在两个类之间横跳，导致K均值聚类算法难以收敛；未解决这个问题，我们可以放宽收敛的条件

高斯混合模型(GM)

参考： https://blog.csdn.net/lin_limin/article/details/81048411

概述

高斯混合模型在聚类的分类里面属于基于模型的聚类方法。这和Kmeans和Hierarchical 聚类的底层思想是不同的。

高斯混合模型的核心在于：分布的假定。 假定第i个样本$\boldsymbol xi$​ 来自于第k类正态分布$N_p(\boldsymbol\mu k,\Sigma_k)$​

• $\boldsymbol\mu_k$ 表示均值向量
• $\Sigma_k$ 表示协方差矩阵

那么，$\boldsymbol x_i$ 的密度函数为：

$$f(x_i) = (2\pi)^{-p/2}\abs{\Sigma_k}^{-1/2}\exp\bigg\{-\frac{1}{2}(x_i-\boldsymbol \mu_k)'\Sigma_k^{-1}(x_i-\boldsymbol \mu_k) \bigg\}$$

• K表示聚类数目，可以看做是一个超参数，需要我们事先确定。
• n表示样本量

由来

那么，如果我们能够确定第 i 个样本是来自于第k 个高斯分布总体时，我们可以构造变量：

$$\delta_{ik} = \begin{cases}1,\text{当第i个样本}x_i\text{属于第k个总体}\\0,\text{当第i个样本}x_i\text{不属于第k个总体}\\ \end{cases}$$

这就说明，某一个样本是可能属于某一类的，而且仅属于某一类。

因此，$\deltai = (\delta{i1},\delta{i2},\cdots,\delta{iK})’$ 满足

• 独立同分布的随机向量

• 这个K维向量某一维是1，其余都是0。这就相当于我掷了一个K面的骰子。某一维朝上的记为1，其余都记为0。因此，这个随机变量是服从多维分布 的。因为我只掷了一次骰子，因此第一个变量是1，由于不同”面”出现的概率是不一定的，我们令其为$\pi_1,\cdots,\pi_K$。最终我们给出随机变量是服从多维分布 $M(1,\pi_1,\pi_2,\cdots,\pi_K)$的。

• $\pik=P(\delta{ik}=1)$且满足：

  $$0<\pi_k<1,\sum_{i=1}^K \pi_k = 1$$

根据上面的推论，我们给出 $\delta{i}=(\delta{i1},\delta{i2},\cdots,\delta{iK})’$ 的概率密度函数：

$$f(\delta_i) = \prod_{k=1}^K (\pi_k)^{\delta_{ik}},i=1,2\cdots,n$$

那么，当我们对一个$x_i$ ，给定了$\delta_i$ 的密度函数之后(样本真的落在第k类上的时候)，可以给出$x_i$的密度函数。

$$f(x_i|\delta_i) = \prod_{k=1}^K\Bigg( (2\pi)^{-p/2}|\Sigma_k|^{-1/2}\exp\bigg\{-\frac{1}{2}(x_i-\boldsymbol \mu_k)'\sum_k^{-1}(x_i-\boldsymbol \mu_k) \bigg\} \Bigg)^{\delta_{ik}}$$

因为$\delta_i$中只有一项是等于1的，其余都等于0。其实就相当于样本属于第k类的密度函数乘以 K-1 个 1。因此这个式子拆开来就是等于上面我给出的$x_i$的密度函数，只不过这个式子更加 General一点

那么，对于样本 ${x_i,\delta_i},i=1,2\cdots,n$，我们可以给出其联合密度函数

$$\begin{align} & \prod_{i=1}^n f(x_i,\delta_i)\\ =&\prod_{i=1}^n f(\delta_i)\cdot f(x_i|\delta_i)\\ =&\prod_{i=1}^n\bigg(\pi_k(2\pi)^{-p/2}|\Sigma_k|^{-1/2}\exp\bigg\{-\frac{1}{2}(x_i-\boldsymbol \mu_k)'\Sigma_k^{-1}(x_i-\boldsymbol \mu_k) \bigg\}\bigg)^{\delta_{ik}} \end{align}$$

对于上面这个密度函数，其实就是未知参数 $\theta = (\pi_1,\cdots,\pi_K,\boldsymbol\mu_1,\cdots,\boldsymbol\mu_K,\Sigma_1,\cdots,\Sigma_K)$ 的似然函数。理论上，基于这个似然函数，我们可以来估计参数$\theta$

但是，在实际中，我们仅能观测到样本${x_i}$ ，$i=1,2\cdots,n$, 是没有办法去观测$\delta_i$ 的。因此，我们没有办法直接估计未知参数$\theta$。因此我们可以对联合密度函数求关于 $x_i$ 的边际分布。

$$f(x_i) = \sum_{k=1}^K \pi_k(2\pi)^{-p/2}|\Sigma_k|^{-1/2}\exp\bigg\{-\frac{1}{2}(x_i-\boldsymbol \mu_k)'\Sigma_k^{-1}(x_i-\boldsymbol \mu_k) \bigg\}$$

这个密度函数是由K 个正态分布的密度函数加权组合而成的，常被称为是高斯混合模型。其中,$p(x|\deltai)$ 就是第k个高斯模型的概率密度函数，可以看成选定第k 个模型后，该模型产生x的概率；$p(\delta_i)=\pi_k$ 是第k个高斯模型的权重，称其为第k个模型的先验概率，满足 $\sum{k=1}^K \pi_k$ = 1

所以，混合高斯模型并不是什么新奇的东西，它的本质就是融合几个单高斯模型，来使得模型更加复杂，从而产生更复杂的样本。理论上，如果某个混合高斯模型融合的高斯模型个数足够多，它们之间的权重设定得足够合理，这个混合模型可以拟合任意分布的样本。

EM算法

由于只观测到$xi$ 去估计参数$\theta$ 是很难估的，因此我们需要用EM算法。将$\delta{ik}$作为潜变量。

对于未知参数$\theta$的对数似然函数为：

$$\begin{align} \ln L(\mu,\Sigma,\pi) &= \sum_{i=1}^n\ln\sum_{k=1}^K\pi_k N(x_i|\mu_k,\Sigma_k)\\ &\propto -\frac{1}{2}\sum_{i=1}^n\sum_{k=1}^K\delta_{ik}\big((x_i-\boldsymbol \mu_k)'\Sigma_k^{-1}(x_i-\boldsymbol \mu_k)+\ln|\Sigma_k|\big)+\sum_{i=1}^n\sum_{k=1}^K\delta_{ik}\ln(\pi_k)\\ &=Q_0(\mu,\Sigma,\pi) \end{align}$$

E 步

在E步，我们需要将潜变量 $\delta{ik}$的期望$\pi{ik}^*$ 带入$Q_0(\boldsymbol \theta )$, 即

$$Q(\theta) = -\frac{1}{2}\sum_{i=1}^n\sum_{k=1}^K\pi^*_{ik}\big((x_i-\boldsymbol \mu_k)'\Sigma_k^{-1}(x_i-\boldsymbol \mu_k)+\ln|\Sigma_k|\big)+\sum_{i=1}^n\sum_{k=1}^K\pi^*_{ik}\ln(\pi_k)\\ =Q_1(\theta)+Q_2(\theta)$$

前面这部分只和 $\mu,\Sigma$ 有关，后面只和 $\pi_k$ 有关

$\delta{ik}$ 的期望$\pi{ik}^*$ 为：

$$\pi^*_{ik} = E(\delta_{ik}|x_i) = P(\delta_{ik}=1|x_i)=\frac{\pi_k\phi(x_i;\boldsymbol \mu_k,\sum_k)}{\sum_{k=1}^K\pi_k\phi(x_i;\boldsymbol\mu_k,\sum_k)}$$

其中：

$$\phi(\boldsymbol x_i,\boldsymbol \mu_k,\Sigma_k) = (2\pi)^{-p/2}\abs{\Sigma_k}^{-1/2}\exp\bigg\{-\frac{1}{2}(x_i-\boldsymbol \mu_k)'\Sigma_k^{-1}(x_i-\boldsymbol \mu_k) \bigg\}$$

① Q函数描述的其实就是在给定$\boldsymbol \theta$ 参数下，先对样本 X 做一个最有可能的划分（每个样本来源于各个类的可能性，即对$\delta_i$ 做估计 $E$ ，再描述能够产生这组样本的可能性（Q函数）)

② 有了对于 $\delta_i$ 的估计之后，Q函数只和样本有关（传统意义上的似然函数亦如此，完全数据的似然函数还与 $\gamma$有关），而不再含有隐变量，从而使得最大化Q函数成为可能；

③ 最大化Q函数的过程实则就是使得能够产生这组样本的可能性最大，与最大化似然函数的思路如出一辙。

M步

求$Q(\theta)$ 的最大值，而确定未知参数的估计

我们发现：

• $Q1(\theta)$ 仅与未知参数 ${\boldsymbol \mu_k,\Sigma_k}^{K}{k=1}$ 有关
• $Q2(\theta)$ 仅与未知参数 ${\pi_k}^K{k=1}$ 有关

于是，我们可以分别确定最大值点。

Q1

$$Q_1(\boldsymbol\theta) =-\frac{1}{2}\sum_{i=1}^n\sum_{k=1}^K\pi^*_{ik}\big((x_i-\boldsymbol \mu_k)'\Sigma_k^{-1}(x_i-\boldsymbol \mu_k)+\ln|\Sigma_k|\big)$$

在这里，由于$\Sigma_k$ 是一个矩阵，我们来复习一下对正定对称矩阵的求导

• 假定 $X$ 是一个正定对称矩阵

  • 非线性的形式：

    $$\frac{\partial \ln \det (X)}{\partial X} = X^{-1}$$

  • 关于逆矩阵的求导：

    $$\frac{\partial \tr(AX^{-1}B)}{\partial X} = -(X^{-1}BAX^{-1})'$$

现在，对于$Q_1(\theta)$ ,我们要分别对$\boldsymbol \mu_k$ 和 $\Sigma_k$ 求导，并使得导函数为0

$$\begin{align} &\frac{\partial Q_1(\boldsymbol \theta)}{\partial\boldsymbol\mu_k} = -\frac{1}{2}\sum_{i=1}^n\pi_{ik}^*\Sigma_{k}^{-1}(\boldsymbol x_i-\boldsymbol \mu_k)=0 \\~\\ &\frac{\partial Q_1(\boldsymbol \theta)}{\partial \Sigma_k} = \sum_{i=1}^n\pi_{ik}^*(\Sigma_k^{-1}(\boldsymbol x_i-\boldsymbol \mu_k)(\boldsymbol x_i-\boldsymbol \mu_k)'\Sigma_{k}^{-1}+\Sigma_k^{-1})=0 \end{align}$$

由此解得：

$$\begin{align} &\boldsymbol \mu_k^{i+1} = \frac{\sum_{i=1}^n\pi_{ik}^*\boldsymbol x_i} {\sum_{i=1}^n\pi_{ik}^*}\\~\\ &\Sigma^{i+1}_k = \frac{\sum_{i=1}^n\pi_{ik}^*(\boldsymbol x_i-\boldsymbol \mu_k)(\boldsymbol x_i-\boldsymbol \mu_k)'}{\sum_{i=1}^n \pi_{ik}^*} \end{align}$$

$\mu_k^{i+1},\sum_k^{i+1}$ 分别表示第$(i+1)$次迭代下第k个类的均值、协方差矩阵

Q2

$$Q_2(\boldsymbol \theta) = \sum_{i=1}^n\sum_{k=1}^K\pi^*_{ik}\ln(\pi_k)\\$$

对于$Q_1(\theta)$ ,我们要分别对$\pi_k$ 求导，并使得导函数为0

注意了，在求$Q_2(\boldsymbol \theta)$ 的最大值时，注意这里是对$\pi_k$ 有限制条件的，即：

$$\sum_{i=1}^K \pi_k = 1, 0<\pi_k<1,k=1,2\cdots ,K$$

因此，我们需要采用拉格朗日乘子法，令

$$Q_2^*(\boldsymbol \theta) = \sum_{i=1}^n\sum_{k=1}^K\pi_{ik}^*\ln(\pi_k)-\lambda(\sum_{k=1}^K\pi_k-1)$$

对 $Q_2^*(\boldsymbol \theta) $ 关于 $\pi_k$ 求导，并使得导函数为0，即：

$$\frac{\partial Q_2^*(\boldsymbol \theta)}{\partial \pi_{k}} = \sum_{i=1}^n\frac{\pi_{ik}^*}{\pi_k}-\lambda = 0$$

由此解得：

$$\pi_{k} = \frac{1}{n}\sum_{i=1}^n\pi_{ik}^*$$

小结

EM算法的核心思想是：通过迭代的过程来找到一组最优的参数 $ (\mu^,\Sigma^,\pi^*)$，使得这组参数表示的模型最有可能产生现有的采样数据。每次迭代的过程就是参数矫正的过程。

现假设初始化一组参数 $\mu^0,\Sigma^0,\pi^0$。在这组参数下，2类二维高斯分布如图11绿色椭圆所示。现在开始用EM算法

• E-step 开始对样本数据进行划分（对$\delta_i$ 进行估计）。蓝色的样本大多都被划分给第1类模型，橘黄色的样本大多都被划分给第2类模型。但是第1类模型还有优化空间：第1类模型还不能使得蓝色样本出现的联合概率达到最大。第2类模型也是如此。

• M-step便优化了2类模型的参数，得到新的参数，$\mu^1,\Sigma^1,\pi^1$ .使得优化后2类高斯分布如图11红色椭圆所示。

  • 第1类模型主要优化的是模型均值$\mu$（即椭圆的中心）
  • 第2类模型主要优化的是模型协方差矩阵$\Sigma$（即椭圆的长轴、短轴和长短轴的方向）
• 然后重复进行E-step和M-step，直到参数$(\mu,\Sigma,\pi)$收敛 　　

最后谈谈混合高斯模型的参数$\pi$。

• 混合高斯模型的参数$\mu,\Sigma$ 比较好理解，用于描述各个高斯分布的形状，对于它们的调整也比较直观：使得本高斯分布能够更好地接纳被划分到这类分布的样本。

• 而为什么要有参数$\pi$ ? 它描述的是各个高斯分布所占的比重，如果不加“歧视”的话（样本来源于各个高斯分布的可能性一致），则有 $\pi_k=1/K$ 。而如果对于某一类高斯分布（即为i）有侧重的话，则相应的 $\pi_i$ 较大，体现在图中就是被分配给各个类的样本数占样本总数的比例。如果一轮优化后，某一类高斯分布又接纳了更多样本，则其 $\pi$ 变大，反之变小（所以图11从绿色椭圆调整为红色椭圆实际上两个类所对应的权重也被优化了）。

  • 而从本质上来看参数 $\pi$，则是为了混合高斯模型能有更好的曲面拟合能力。当参数 $\pi$ 退化为 某一类高斯分布的权重远远大于其他类高斯分布的时候，混合高斯模型就退化成了单高斯模型！

最后，给出混合高斯分布参数估计的逻辑流程。

DBScan

参考博客https://www.cnblogs.com/pinard/p/6208966.html

DBSCAN(Density-Based Spatial Clustering of Applications with Noise，具有噪声的基于密度的聚类方法)是一种很典型的密度聚类算法，和K-Means，BIRCH这些一般只适用于凸样本集的聚类相比，DBSCAN既可以适用于凸样本集，也可以适用于非凸样本集。下面我们就对DBSCAN算法的原理做一个总结。

DBSCAN是一种基于密度的聚类算法，这类密度聚类算法一般假定类别可以通过样本分布的紧密程度决定。同一类别的样本，他们之间的紧密相连的，也就是说，在该类别任意样本周围不远处一定有同类别的样本存在。

通过将紧密相连的样本划为一类，这样就得到了一个聚类类别。通过将所有各组紧密相连的样本划为各个不同的类别，则我们就得到了最终的所有聚类类别结果。

概述

我们给定数据集 $X = (\boldsymbol {x_1,x_2,\cdots,x_n})’$

对于每一个样本 $\boldsymbol xi = (x{i1},x{i2},\cdots,x{ip})’$ 可以看做 $R^p$ 空间中的一个点。

我们假定第k 个点$\boldsymbol x_k$ 和第l个点 $\boldsymbol x_l$ 之间的距离为 $d(k,l)$

基本概念

DBSCAN是基于一组邻域来描述样本集的紧密程度的，参数(ϵ, MinPts)用来描述邻域的样本分布紧密程度。其中，ϵ 描述了某一样本的邻域距离阈 ，MinPts 描述了某一样本的距离为ϵ的邻域中样本个数的阈值 。由此，我们给出DBSCAN的一些基本概念如下：

1. $\epsilon$-邻域：对于$xj\in X$ 其 ϵ-邻域包含样本集D中与$x_j$ 的距离不大于 𝜖 的子样本集， 即 $N\epsilon(xj) = {x_i\in D|d(i,j) \leq\epsilon}$ 。称其为点 $x_j$ 的 $\epsilon$-邻域, 并将这个子样本集的个数记为 $|N\epsilon(x_j)|$

2) 核心对象：对于任一样本 $xj\in D$，如果其 $\epsilon$-邻域对应的 $Nϵ(x_j)$ 至少包含MinPts个样本，即如果$|N\in(x_j)|≥MinPts$，则 $x_j$是核心对象。　

1. 密度直达：如果 $x_i$ 位于 $x_j$ 的ϵ-邻域中，且$x_j$是核心对象，则称$x_i$ 由 $x_j$ 密度直达。注意反之不一定成立，即此时不能说$x_j$由$x_i$ 密度直达, 除非 $x_i$ 也是核心对象。

2. 密度可达：对于 $xi$ 和 $x_j$ , 如果存在样本样本序列 $p_1,p_2,\cdots,p_T$ ,满足$p_1 = x_i,p_T=x_j$ , 且$p{t+1}$由$pt$密度直达，则称$x_j$由 $x_i$密度可达。也就是说，密度可达满足传递性。此时序列中的传递样本$p_1,p_2,\cdots,p{T−1}$ 均为核心对象，因为只有核心对象才能使其他样本密度直达。注意密度可达也不满足对称性，这个可以由密度直达的不对称性得出。

3. 密度相连：对于 $x_i$ 和 $x_j$,如果存在核心对象样本$x_k$，使$x_i$和$x_j$均由$x_k$ 密度可达，则称$x_i$和$x_j$密度相连。注意密度相连关系是满足对称性的。

从下图可以很容易看出理解上述定义，图中MinPts=5，红色的点都是核心对象，因为其ϵ-邻域至少有5个样本。黑色的样本是非核心对象。

• 所有核心对象密度直达的样本在以红色核心对象为中心的超球体内，如果不在超球体内，则不能密度直达。
• 图中用绿色箭头连起来的核心对象组成了密度可达的样本序列。在这些密度可达的样本序列的 ϵ-邻域内
• 所有的样本相互都是密度相连的。

聚类思想

DBSCAN的聚类定义很简单：由密度可达关系导出的最大密度相连的样本集合，即为我们最终聚类的一个类别，或者说一个簇。

这个DBSCAN的簇里面可以有一个或者多个核心对象。如果只有一个核心对象，则簇里其他的非核心对象样本都在这个核心对象的ϵ-邻域里；如果有多个核心对象，则簇里的任意一个核心对象的ϵ-邻域中一定有一个其他的核心对象，否则这两个核心对象无法密度可达。这些核心对象的ϵ-邻域里所有的样本的集合组成的一个DBSCAN聚类簇。

那么怎么才能找到这样的簇样本集合呢？DBSCAN使用的方法很简单，它任意选择一个没有类别的核心对象作为种子，然后找到所有这个核心对象能够密度可达的样本集合，即为一个聚类簇。接着继续选择另一个没有类别的核心对象去寻找密度可达的样本集合，这样就得到另一个聚类簇。一直运行到所有核心对象都有类别为止。

基本上这就是DBSCAN算法的主要内容了，是不是很简单？但是我们还是有三个问题没有考虑。

• 第一个是一些异常样本点或者说少量游离于簇外的样本点，这些点不在任何一个核心对象在周围，在DBSCAN中，我们一般将这些样本点标记为噪音点。

+　第二个是距离的度量问题，即如何计算某样本和核心对象样本的距离。在DBSCAN中，一般采用最近邻思想，采用某一种距离度量来衡量样本距离，比如欧式距离。这和KNN分类算法的最近邻思想完全相同。对应少量的样本，寻找最近邻可以直接去计算所有样本的距离，如果样本量较大，则一般采用KD树或者球树来快速的搜索最近邻。如果大家对于最近邻的思想，距离度量，KD树和球树不熟悉，建议参考 K近邻法(KNN)原理小结。

• 第三种问题比较特殊，某些样本可能到两个核心对象的距离都小于 ϵ，但是这两个核心对象由于不是密度直达，又不属于同一个聚类簇，那么如果界定这个样本的类别呢？一般来说，此时DBSCAN采用先来后到，先进行聚类的类别簇会标记这个样本为它的类别。也就是说DBSCAN的算法不是完全稳定的算法。

算法

下面我们对DBSCAN聚类算法的流程做一个总结。

输入：样本集 $D= (x_1,x_2,\cdots,x_m)$，邻域参数 (ϵ,MinPts), 样本距离度量方式

输出：簇划分C.　

1. 初始化核心对象集合$\Omega = \emptyset$, 初始化聚类簇数 $k=0$，初始化未访问样本集合 $ \Gamma = D$, 簇划分$C = \emptyset$
2. 对于 $j=1,2\cdots,m$, 按下面步骤，找出所有核心对象
   • 通过距离度量方式，找到样本 $xj$ 的 ϵ-邻域 样本集 $N\epsilon(x_j)$
   • 如果子样本集样本个数满足 $|N_\epsilon(x_j)|\geq MinPts$ , 就将样本$x_j$ 加入核心对象的样本集合中去：$\Omega = \Omega \cup{x_j}$
3. 如果核心对象集合 $\Omega = \emptyset $，则算法结束，否则转入步骤4.
4. 在核心对象集合$\Omega$中，随机选择一个核心对象$o$，初始化当前簇核心对象队列 $\Omega_{cur}={o}$, 初始化类别序号$k=k+1$，初始化当前簇样本集合 $C_k={o}$, 更新未访问样本集合 $\Gamma=\Gamma−{o}$
5. 如果当前簇核心对象队列 $\Omega_{cur}=\emptyset$，则当前聚类簇 $C_k$ 生成完毕, 更新簇划分$C={C_1,C_2\cdots,C_k}$, 更新核心对象集合$\Omega = \Omega- C_k$， 转入步骤3。否则更新核心对象集合 $\Omega=\Omega−C_k$。
6. 在当前簇核心对象队列 $\Omega{cur}$ 中取出一个核心对象 $o’$,通过邻域距离阈值 ϵ找出所有的 ϵ-邻域子样本集$N\epsilon(o’)$，令$\Delta=Nc(o’)\cap \Gamma $, 更新当前簇样本集合$C_k = C_k\cup\Delta$, 更新未访问样本集合$\Gamma=\Gamma−\Delta$, 更新$\Omega{cur} = \Omega_{cur}\cup(\Delta\cap\Omega)-o’$，转入步骤5.
7. 如果 $x_i\in D$ 但是 $x_i\notin C_k,k=1,2\cdots,K$ ，那么我们称点 $x_i$ 为噪声

输出结果为： 簇划分 $C = {C_1,C_2\cdots,C_m}$

我们用一个可视化的例子来展现DBSCAN的聚类效果：这里由于点很多，采取的是在图片上等距离得取几个点，判断这几个点中是否存在核心对象，然后从选中的核心对象开始聚类。我们发现DBSCAN可以对非凸数据集(圆环)进行聚类，而Kmeans是达不到这种效果的。

小结

和传统的K-Means算法相比，DBSCAN最大的不同就是不需要输入类别数k，当然它最大的优势是可以发现任意形状的聚类簇，而不是像K-Means，一般仅仅使用于凸的样本集聚类。同时它在聚类的同时还可以找出异常点，这点和BIRCH算法类似。

用通俗的话来说：我联系的到的人，都是我的朋友，我联系不到的，反正不属于我这类。如果有人被孤立了，他就是噪声

那么我们什么时候需要用DBSCAN来聚类呢？一般来说，如果数据集是稠密的，并且数据集不是凸的，那么用DBSCAN会比K-Means聚类效果好很多；如果数据集不是稠密的，则不推荐用DBSCAN来聚类，因为如果$\epsilon$设置的不好的话，很可能都是噪声。

下面对DBSCAN算法的优缺点做一个总结。

DBSCAN的主要优点有：

1. 可以对任意形状的稠密数据集进行聚类，相对的，K-Means之类的聚类算法一般只适用于凸数据集。
2. 可以在聚类的同时发现异常点，对数据集中的异常点不敏感。
3. 聚类结果没有偏倚，相对的，K-Means之类的聚类算法初始值对聚类结果有很大影响。

DBSCAN的主要缺点有：

1. 如果样本集的密度不均匀、聚类间距差相差很大时，聚类质量较差，这时用DBSCAN聚类一般不适合。
2. 如果样本集较大时，聚类收敛时间较长，此时可以对搜索最近邻时建立的KD树或者球树进行规模限制来改进。
3. 调参相对于传统的K-Means之类的聚类算法稍复杂，主要需要对距离阈值 ϵ，邻域样本数阈值MinPts联合调参，不同的参数组合对最后的聚类效果有较大影响。

聚类方法的评价

聚类有效性是评价聚类结果的方式，主要分为外部聚类的有效性和内布聚类的有效性。它们的区别就在于：对于这个数据集，我们知不知道它的标签，如果知道，相当于借助了“外部”信息，就是外部聚类的有效性。反之就是内部聚类的有效性

外部聚类的有效性

对于n个测试样本(数据集) $x_i(i=1,2\cdots,n)$

• 假定分类结果为 $\mathcal C = {C_1,C_2\cdots,C_K}$ 并满足：

  $$C_k\cap C_l = \emptyset\\ \bigcup_{k=1}^KC_i = X$$
  • K 为聚类的数目

• 假设 “真实的” 标签划分 $\mathcal P = {P1,P_2\cdots,P{K’}}$ 并满足：

  $$P_k\cap P_l = \emptyset\\ \bigcup_{k=1}^KP_i = X$$
  • K’ 为真实分类数目

因此，我们可以给出可能性矩阵的定义：

我们可以计算：

$$p_{ij} = \frac{n_{ij}}{n},p_i = \frac{n_{i\cdot}}{n},p_j = \frac{n_{\cdot j}}{n}$$

常用指标

对 K 均值聚类算法而言，熵和纯度是两种最常用的外部度量

熵

$$E = -\sum_i p_i\bigg(\sum_j\frac{p_{ij}}{p_i}\ln\frac{p_{ij}}{p_i} \bigg)$$

纯度

$$P = \sum_i p_i(\max_j\frac{p_{ij}}{p_i})$$

内部聚类的有效性

聚类一般是没有标签的，所以外部聚类有效性指标有很大的局限性。因此现在来讲讲内部聚类的有效性。

内部聚类有效性要看两个准则：

紧密度(Compactness)

紧密度是在同一类内不同个体之间紧密关联的度量

• 方差可以体现数据的紧密度；低方差表明紧密度好。
• 很多紧密度的定义是依赖于距离的，如：最大或平均两两距离，基于中心的最大或平均距离等。

区分度(Seperation)

区分度是不同类别区间程度的度量。

• 例如，两个类中心的距离，或者是最短距离，通常作为区分度的度量
• 密度(density) 也会用于度量区分度。

指标

均方标准差

$$RMSSTD = \bigg(\frac{\sum_{k=1}^K \sum_{i\in C_k}||\boldsymbol x_i-\boldsymbol m_k||^2 }{p\sum_{k=1}^K(n_{k}-1)} \bigg)^{1/2}$$

用语言来表述，分子是：每个个体减去每个组的均值；分母中，p代表维度，右边是总的样本的个数。

RMSSTD 越小，就代表紧密度越好

R平方 (RS)

$$RS = 1-\frac{\sum_{k=1}^K\sum_{i\in C_k}||\boldsymbol x_i-\boldsymbol m_k||^2}{\sum_{i=1}^n||\boldsymbol x_i-\boldsymbol {\overline x}||^2}$$

这个方法是从回归中迁移过来的，分子是 SSE，即组内个体减去组均值的平方和。分母是SST 即所有样本减去整体样本的平方和

选超参

因为很多聚类算法都需要我们手动选择超参，那么有什么通用的方法吗？

轮廓法

第一种是轮廓法，是一种直观的、且用于验证聚类结果的方法。

基本思想就是：同类相似，异类不同。

在轮廓法中，需要定义一个重要的概念——轮廓值。 轮廓值是一个-1到1之间的值，需要通过计算获得。

一般认为，轮廓值较高表示该样本被很好得聚到其所属的类，而不和其他类相似。

如果大部分的样本具有较高的轮廓值，那么聚类的结果是恰当的；如果存在许多样本具有较低的轮廓值，甚至是负值，那么聚类的个数可能不合适

具体方法

计算 a(i)

对于某个聚类结果 $\mathcal C = {C_1,C_2\cdots,C_K}$ ：

那么，对于第 i 个样本，假定其属于第k 类，$n_k$ 表示第k 类中的样本量，令$a(i)$ 表示第i个样本与 第k类的 其他样本的 平均距离。即：

$$a(i) = \frac{1}{n_k-1} \sum_{j\in \mathcal C_k,j\neq i}\text{dist}(i,j)$$

我们注意到 $a(i)$ 表示第i 个样本与其同属一类的样本的平均不相似度，如果该类只有第i个样本本身，那么$a(i)$ 为0

计算b(i)

在计算 b(i) 之前，我们要对第i个样本和另一个样本量为 $n{k’}$ 的类 $\mathcal C{k’}$ ，令$d(i,\mathcal C_{k’})$为第i个样本与第 $k’$ 个类的所有样本的平均不相似度

$$d(i,\mathcal C_{k'}) = \frac{1}{n_{k'}}\sum_{j\in \mathcal C_{k'}}\text{dist}(i,j)$$

然后我们可以定义 $b(i)$，令

$$b(i) = \min_{k'\neq k} d(i,\mathcal C_k')$$

用来表示第i 个样本和不属于同一类的最近距离

计算轮廓值 s(i)

对于第 i 个样本，我们定义轮廓值 $s(i)$ 为：

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

对于所有n个样本，可以计算平均轮廓值，用于度量聚类数目 K 是否合适

由此，以最大的平均轮廓值对应的K 作为最优聚类数目，这种方法被称为是轮廓法

CH指数

CH 指数是与方差分析中的 F 检验统计量是相似的。

假定我们对 n 个样本进行聚类，对于某个聚类结果 $\mathcal C = {C_1,C_2\cdots,C_K}$ ：我们分别考虑类间的平方和$B(K)$ 和 类内的平方和 $W(K)$

那么，CH指数可以定义为：

$$CH(K) = \frac{B(K)/K-1}{W(K)/(n-K)}$$

其中，

$$\begin{align} &W(K) = \sum_{k=1}^K \sum_{i\in \mathcal C_k}||\boldsymbol x_i-\boldsymbol{\overline x_k}||^2\\ &\overline x_k = \frac{1}{n_k}\sum_{i\in\mathcal C_k}\boldsymbol x_i\\ \end{align}$$ $$\begin{align} &B(K) = \sum_{k=1}^K\sum_{i\in\mathcal C_k} ||\overline {\boldsymbol x_i}-\boldsymbol {\overline{\overline x}}_k ||^2\\ &\overline{\overline {\boldsymbol x}} = \frac{1}{K} \sum_{k=1}^K \overline {\boldsymbol x}_k \end{align}$$

基于方差分解公式，在给定样本时，$B(K)$ 与 $W(K)$ 的和是一个定值

如果 $B(K)$ 越大，则 $W(K)$ 越小，那么满足对聚类的基本思想：类内差异小，类间差异大

我们可以通过最大化 CH指数来得到最优的聚类数目K