机器学习中的聚类

Clustering in Machine Learning - GeeksforGeeks

在现实世界中，并非我们处理的每个数据都有目标变量。这种类型的数据不能使用监督学习算法进行分析。我们需要无监督算法的帮助。在无监督学习中最流行的分析类型之一是聚类分析。当目标是对数据集中的相似数据点进行分组，那么我们会使用聚类分析。在真实情况下，我们可以使用聚类分析客户群体以定向广告，或者在医学成像中找到未定义的新感染区域和更多的用例，他们会在这篇文章中被我们讨论。

什么是聚类

给予他们的相似性对于数据点彼此之间进行分组，他叫做聚类或者聚类分析。这个方法定义在无监督学习之下，他意图从未标记的数据点中获得洞察力，也就是，不像进度学习我们没有目标目标变量。

聚类目的是在异质数据集中形成同质数据点的组。他基于欧氏距离，余弦相似度，曼哈顿距离等评估相似性。然后分组高相似度得分到一起。

例如，在下面给出的图片，我们可以清楚的看到他们有3圆形簇是基于距离而形成的。

现在簇的形状不一定要是圆形的。这个形状可以是任意的。有许多很好的算法可以很好的检测形状簇。

例如，下面给出的图片我们可以看到簇不是由环形组成的。

簇的类型

广泛的说，有俩钟类型的聚类他们可以用来分类相似的数据点：

硬聚类：这个类型的聚类每个数据点每个数据点要么完全属于一个簇要么不属于一个簇。例如让我们假设4个数据点我们有俩个簇，将点加入这俩个簇。所以每个数据点要么属于一个簇要么都不属于。

软簇：在这个类型的簇中，作为分派每个数据点到簇中的替代，对该点是否为该簇的可能性进行评估。例如，让我们假设有四个点要分类到俩个簇中。所以我们将评估数据点属于这俩个簇的概率.这个概率是通过计算所有的点得到的。

聚类的用途

在我们开始不同类型的聚类算法之前，我们将浏览聚类算法的用例。聚类算法主要被使用在：

• 市场细分：公司使用簇已分类他们的顾客使用定向广告吸引更多的观众。
• 市场篮分类：商场经营者分析他们的销售弄清楚，哪些商品主要是由顾客一起购买的。例如在美国，尿布和啤酒通常是由父亲一起购买的
• 社交网络分析：社交媒体网站使用你的数据以确定你浏览的行为和提供目标交友推荐或者内容推荐。
• 医学成像：医生使用簇找到诊断图像如x光中的感染的区域
• 异常探测：在实时数据流中找到异常值或者，预测欺诈交易，我们可以用聚类来识别它们。
• 简化大数据集的处理工作：簇完成后每个簇都有一个簇ID。现在你可以将特性集的整个特性集约简为它的簇ID。当簇可以用简单的簇ID表示复杂的情况时，它是有效的。 使用简单的原则，簇数据可以使复杂的数据变得更简单。

还有更多关于聚类算法的用例，但是也有一些主要和常见的用力。接下来我们将讨论聚类算法将怎么样帮助我们执行上述任务。

聚类算法的类型

表面上聚类算法帮助我们分析非结构性数据。 绘制最短距离，数据点的密度是一些元素，他们影响了数据的组成。聚类是确定如何关联对象的过程，基于一种叫做相似性度量的度量。相似的度量更容易在更小的特征集中定位。随着特征数量的增加创建相似的度量变得越来越困难。根据数据挖掘中使用的聚类算法类型，几个技术被用来分类数据集中的数据。在这部分描述了聚类技术，多种类型的聚类有：

中心点聚类（基于模型的方法 ）

分割方法是更容易的聚类方法。他们根据数据点的接近程度对它们进行分组。这些算法的相似性度量是欧几里得距离，曼哈顿距离，闵可夫斯基距离。数据集被划分成预定义数量的簇，每个簇是向量的一个引用。当对向量值进行比较，数据数据变量无差异就加入聚类。

这个算法的主要缺点是它要求建立簇的数量“k”，无论是直觉上还是系统上（使用肘部法则）在任何聚类机器学习系统开始分配数据点之前就完成指派。尽管如此，它还是一个受欢迎的聚类算法类型。K-means和K-medoids聚类就是这种聚类的一些例子。

基于密度的聚类（基于模型的方法）

基于密度的聚类，一个基于模型的聚类，根据数据点的密度来找到分组。与中心点聚类相反，中心点聚类需要预定义簇的数量对于初始点非常敏感，基于密度的聚类是根据簇的数量自动进行，并且不容易受到初始点的影响。它是很好的处理不同大小与形式的簇，使他们非常适合不规则的数据集或者有重叠簇的数据集。这个方法关注局部密度使他可以同时管理稠密和稀疏数据块，并且可以区分不同形态的簇。

相反，中心聚类例如k-means很难找到任意形状的簇。这是因为预制的簇数量限制并且对初始点的质心极度敏感。此外，中心点聚类倾向于产生球形或者凸簇，限制了他们去处理复杂或者不规则形状簇的能力。总之基于密度的聚类客服了这些中心点聚类的缺点，动态选择簇大小，对初始化更有弹性，成功的俘获了不同大小和不同形式的簇

基于连通性的簇（分层聚类）

一种将相关的数据点组合到分层簇的方法也叫做分层聚类。每个数据点在初始时都被纳入到单独簇。这些簇最会与随后会与其他相似簇结合，形成一个大簇他们包括了所有的数据点。

思考你如何根据物品的相似程度来排列他们。当时用了分类聚类，每个对象在树的底部作为自己的簇开始他们创建树形图，一个类树状结构。在算法审查过这些物体之间有多相似之后，更接近的簇在之后会被合并到更大的簇上。当每个对象都在树顶部的一个簇中时，合并程序将会结束。探查不同的粒度级别是关于分层聚类中有趣的事情之一。为了获得给定数量的簇，你可以选择在特定高度上切割树形图。在簇中的俩个对象越相似，他们就越接近。这相当于根据家族树对物品进行分类，其中最近亲是一起成群的，更宽的分支表示更普遍的联系。分层聚类有俩种方法：

1. 分割法聚类：它遵循自顶向下方法，这里我们视所有数据点为一个大簇的分类，然后将这些簇划分成最小的组。
2. 凝聚型聚类：它遵循自顶向上的方法，这里我们将所有的点视为个体簇的一部分，然后这些簇一起形成一个包含所有点的大簇。

基于分布的簇

使用基于分布的簇，数据点的生成和源头倾向于根据他们倾向，在数据中落入相同的概率分布（比如高斯，二项或者其他）。数据元素使用基于统计学概率的分布进行分组。包括数据对象他们在簇中有着高相似度。离簇中心点越远的数据被包含在簇中的可能性越小，每个簇都有自己的中心点。

基于密度和基于边界的方法的一个显著缺点是，某些算法需要预先指定簇，并且主要是对大部分算法的聚类形式的定义。至少选择一个调优或超参数，虽然这样做很简单，但是如果做错了会有意外的反应。基于分布的聚类有超越空间关系，且与基于中心聚类在灵活性准确性和聚类结构方面有明显的优势。关键问题是，为了避免过拟合，很多聚类方法只适用于模拟或者制造的数据，或者当大部分数据点中心确实属于预测分布时。最受欢迎的基于分布的算法是高斯混合模型。

不同的聚类算法

k均值聚类

K means Clustering - Introduction - GeeksforGeeks

介绍

k均值聚类，依据他们和中心点的距离，分配数据点到k个簇中的一个。它开首先在空间中随机分配簇的质心。然后每个数据点基于从中心点的距离分配到了一个点，在每个点分配完一个簇之后，这个过程进行迭代，直到都找到一个好的簇。在分析中我们假设簇的数量是预先给定的，我们必须把一个点放在组中。

在一些例子中K没有清晰的定义，我们需要考虑好K的最优数量。K均值聚类性能好，数据被分离的也很好。当数据点有重合这个聚类方法就不在合适。K均值相比于其他的聚类技术很快。它在数据点之间提供了强大的连接。K均值聚类不能提供关于聚类质量的明确信息。不同的初始化簇中心可能会导致不同的结果。同样，K均值算法对噪音敏感。它可能停留在局部极小值。

k均值的目标是什么？

聚类的目标是划分群体或者数据点集合到一定数量的分组中。所以每个组中的数据点是可以与另一个其他组中的数据点进行比较的。本质上事务的分组是基于他们和另一个点的相似性与区别进行分组的。

k均值是如何工作的

我们有一组数据有特定的特征，和特征的值（类似向量）。任务是将这些羡慕分类成组。为了实现这个，我们使用k均值算法，一个无监督学习算法。K在算法的名字中代表的是簇或者我们项分类的组的数量。

（如果你把羡慕想象成n维空间中的点，这将会有帮助）。算法会将项目分类到k个组或者相似的簇中。使用欧氏距离计算他们的相似性。

算法的工作如下：

1. 首先，我们岁初始化K个点，叫做聚类的均值点
2. 我们分类每个项目到最接近的点，然后我们更新均值坐标，它是当前簇中被分类项目的平均值
3. 我们在给定的迭代次数和中重复该过程到结束，我们就由了我们的簇

上面提到的点也被叫做均值，是因为他们是项目分类中的均值点。为了初始化这个均值点，我们有很多选择。直觉方法是初始化数据集中随机项的均值。另一种方法是初始话数据集边界之间随机值的均值（如果对于特性x，项目有值[0,3],我们将初始化x的值为[0,3]的均值）

高斯混合模型

基本概念

协方差

它提供了关于变量间关系方向的信息，但并没有以一种易于解释的尺度提供这种关系的强弱信息。

俩个数据集的协方差公式为

$$ \mathrm{Cov}(X,Y)=\frac{\sum_{i=1}^n(X_i-\overline{X})(Y_i-\overline{Y})}{n-1} $$

其中$X_i,Y_i$是独立的相同点索引为i，$\overline X,\overline Y$分别是X和Y样本的均值，n是数据点的数量

协方差矩阵可以告诉你

• 如果协方差是正数，那么意味着当一个变量增加，另一个变量也会增加
• 如果协方差是负数，以为这当一个变量增加，另一个变量减小
• 如果协方差是0，变量之间没有线性关系
• 协方差等于零不能代表变量独立，变量独立协方差一定等于零

然而协方差的大小没有标准化，所以很难解释关系的强度。（数字的大小和关联强度无关）

协方差矩阵

协方差矩阵提供了一种方式来测量一组随机变量或向量变化程度。

给定随机变量集合Xn，协方差矩阵$\sum$是一个nxn的对称矩阵，其中每个元素$\sum_{ij}$是$X_i,X_j$之间的随机变量。

$X_i,X_j$俩个随机变量之间的协方差为

$$ \mathrm{Cov}(X_i,X_j)=E[(X_i-\mu_i)(X_j-\mu_j)] $$

其中E代表了期望值，$u_i,u_j$分别是$X_i,X_j$的平均值期望值。

期望值表示随机变量取值的长期平均值。

对于离散型随机变量X，其期望值E(X)定义为$E(X)=\sum x_ip(x_i)$,这里表示对所有可能的x进行求和

假设有一个离散型随机变量$X$,它可以取三个值：$x_1=1$,$x_2=2$,和$x_{3}=3$,并且它们的概率分别为$p(x_1)=0.2$,$p(x_2)=0.5$,以及$p(x_3)=0.3.$

根据期望值的定义，我们有：$$E(X)=\sum x_ip(x_i)=x_1p(x_1)+x_2p(x_2)+x_3p(x_3)$$
将给定的值代入上述公式：$$E(X)=1\cdot0.2+2\cdot0.5+3\cdot0.3=0.2+1+0.9=2.1$$
因此，随机变量$X$的期望值$E(X)$为 2.1。

对于连续形随机变量期望值可以定义为$E(X)=\int xf(x)dx$

其中f(x)是随机变量的概率密度函数

性质：

• 对称性：协方差矩阵永远是对称的，意味着$\sum_{ij}=\sum_{ji}$
• 非负：协方差举证是正半定的。
• 对角元素：对角元素$\sum_{ii}$是单个随机变量$X_i$的方差

例如二元分布中的变量X和Y，协方差矩阵$\sum$将会是

$$ \boldsymbol{\Sigma}=\begin{bmatrix}\mathrm{Var}(X)&\mathrm{Cov}(X,Y)\\\mathrm{Cov}(Y,X)&\mathrm{Var}(Y)\end{bmatrix} $$

使用：

协方差矩阵被广泛的用于各种领域，比如信号处理，模式识别和机器学习。

混合高斯分布

正态分布&高斯分布

在现实中，很多数据集可以通过高斯分布进行建模（单变量或者多变量）。所以这个假设是很自然和直观的，一个簇可以来自不同的高斯分布。换句话说，他试图建模数据集变为多个不同的高斯分布。这是这个模型的核心思想。一个维度的高斯分布概率密度函数如下

$$ G(X|\mu,\sigma)=\frac{1}{\sigma\sqrt{2\pi}}e^{-\frac{(x-\mu)^2}{2\sigma^2}} $$

其中的$\mu$和$\sigma^2$分别代表均值和分布方差。对于多元（假设是d个随机变量）高斯分布，概率函数为

$$ G(X|\mu,\Sigma)=\frac{1}{\sqrt{(2\pi)|\boldsymbol{\Sigma}|}}\exp\left(-\frac{1}{2}(X-\mu)^T\boldsymbol{\Sigma}^{-1}(X-\mu)\right) $$

这里的$\mu$是d维向量，表示了分布的均值，$\sum$是dxd协方差矩阵。

高斯混合模型

假设有k个簇（为了简单起见这里假设簇的数量是已知的，它是K）所以$\mu,\sum$也估计每个k。如果它只有一个分布，那么就可以用极大似然法来进行估计。但是这里有K个这样的簇，概率密度被定义为所有k个分布的密度的线性函数，即

$$ p(X)=\sum_{k=1}^K\pi_kG(X|\mu_k,\Sigma_k) $$

其中$\pi_k$是第k个分布的混合系数。用最大对数似然估计参数计算$\mathrm{p}(\mathrm{X}|\mu,\Sigma, \pi).$

$$ \begin{aligned} \ln p(X|\mu,\Sigma,\pi)& =\sum_{i=1}^Np(X_i) \\ &=\sum_{i=1}^{N}\ln\sum_{k=1}^{K}\pi_{k}G(X_{i}|\mu_{k},\Sigma_{k}) \end{aligned} $$

现在我们定义了随机变量$\gamma_{k}(X)$使得$\gamma_{k}(X){=}\mathrm{p}(\mathrm{k}|\mathrm{X}).$

根据贝叶斯理论

$$ \begin{aligned} \gamma_{k}(X)& =\frac{p(X|k)p(k)}{\sum_{k=1}^{K}p(k)p(X|k)} &=\frac{p(X|k)\pi_{k}}{\sum_{k=1}^{K}\pi_{k}p(X|k)} \end{aligned} $$

现在为了最大化对数似然函数，$p(X|\mu,\Sigma,\pi)$相对于$\mu\sum\pi$的倒数应该为0，将$p(X|\mu,\Sigma,\pi)$相对于$\mu$的倒数设为0，重新排列这些项

$$ \mu_k=\frac{\sum_{n=1}^N\gamma_k(x_n)x_n}{\sum_{n=1}^N\gamma_k(x_n)} $$

同样的对$\sum,\pi$分别求导，可以得到以下表达式

$$ \Sigma_k=\frac{\sum_{n=1}^N\gamma_k(x_n)(x_n-\mu_k)(x_n-\mu_k)^T}{\sum n=1^N\gamma_k(x_n)} $$

和

$$ \pi_k=\frac{1}{N}\sum_{n=1}^N\gamma_k(x_n) $$

因此，可以清楚地看到，参数不能以封闭形式估计。这就是期望最大化(EM)算法的好处所在。

DBSCAN聚类（基于密度）

基本上，所有的聚类算法使用了相同的方法：即首先计算相似值，然后使用它来聚类数据点成组或者批。这里我们将重点关注：基于密度的带噪声空间聚类方法(Density-based spatial clustering of applications with noise DBSCAN)

簇在数据空间中是高密度的区域，被密度较低区域进行分割。DBSCAN算法是基于一种中观的对于簇和噪声的概念。关键思想是对于簇中的每个点，在给定的半径的邻域会包含最少数的点。

分割法（K均值，PAM聚类）和局域密度的聚类工作方式是找到球状簇或凸簇。换句话说，他们只适合紧凑的分离良好的簇，此外，他们会被噪声和数据中的异常严重的影响。

现实中的数据可能存在不规范支出，就像

1. 簇的形状可以随性所欲，如下图
2. 数据可能包含了噪声

上图展示了一个包含了非凸相撞的聚类和异常值的数据集。给定这样的数据k均值算法很能难找出不同形状的簇。

DBSCAN算法所需要的参数

epc

k距离图是通过连接定点从原始图中（可能是无向图）导出的一种图，它正好差了k步或者相隔“跳数”（hops）的距离。换句话说，俩个顶点，在k距离图中是临近的（用边连接），当且仅当它们在基图中的距离恰好为k

理论上给定样例，无向图 G=(V,E), 其中的V是定点的集合，E是边的集合，k距离图$G_k$有相同的顶点集合V，但是它的边集$E_k$由顶点对(u,v)构成，以至于最短的路径u和v在G中正好有k条边。

它定义了数据点周围的领域，即如果俩个点之间的距离小于或者等于eps，那么他们将被视为邻居。如果eps值选择的小那么大部分数据将被视为离群点(outlier)。如果选择了很大的数据，那么簇将合并大多数的数据点到一个相同的簇当中。一个方法可以找到eps值，那就是k距离图（k-distance graph.）

MinPts

eps半径内的最小邻居数。数据集越大要选择的MinPts也越大。一般情况下，最小的MinPts可以从数据集D中导出为MinPts>=D+1.MinPts的最小值必须至少为3。

在这个算法中我们有三种类型的数据点

1. 核心点：如果有超过MinPts数量的点在eps之内，那么这个点被称为核心点
2. 边界点：一个点在eps中只有小于MinPts的点，但是仍在核心点的邻域内。
3. 噪声或者离群点：一个点没有核心点或者边界点

DBSCAN 算法的步骤

1. 找到所有在 eps 范围内的邻近点，并识别那些拥有超过 MinPts 个邻近点的核心点或已访问点。
2. 对于每个核心点如果他不存在已分配簇，创建新的簇
3. 递归寻找所有的稠密连接点，将它们分配到核心点相同的簇中
   如果存在点c它在领域内有足够数量的点并且点A和点b都在eps距离内，则成点A和点B是密度联通的。这是一个连接过程。所以如果b是c的邻居，c是d的邻居，d是e的邻居，e是a的邻居，这也就意味着b是a的邻居
4. 遍历数据集中剩下的未访问点。这些点不属于任何簇是噪声