聚类算法

聚类算法是机器学习中涉及对数据进行分组的一种算法。在给定的数据集中，我们可以通过聚类算法将其分成一些不同的组。在理论上，相同的组的数据之间有相同的属性和特征，不同组数据之间的属性或者特征相差就会比较大。

K-means聚类算法

算法思想

K-means算法的思想比较简单，假设我们要把数据分成K个类

1. 随机选取k个点，作为聚类中心；
2. 计算每个点分别到k个聚类中心的聚类，然后将该点分到最近的聚类中心，这样就形成了k个簇
3. 再重新计算每个簇的质心（均值）
4. 重复以上2~4步，直到质心的位置不再发生变化或者达到设定的迭代次数

代价函数

要是k-means最后的分类结果最好，也就是要是K-均值最小化，是要最小化所有的数据点与其所关联的聚类中心点之间的距离之和，因此我们可以设计K-均值的代价函数
$$J(c^{(1)},......,c^{(m)},{\mu }_1,......,{\mu }_k)=\frac{1}{m}\sum _{i=1}^m||x^{(i)}-{\mu }_{c^{(i)}}|{|}^2$$
其中${\mu }_{c^{(i)}}$代表与$x^{(i)}$最近的聚类中心点。我们的优化目标就是要找出是的代价函数最小的$c^{(1)},......,c^{(m)}$和${\mu }_1,......,{\mu }_k$

优点

• 应用广泛，速度快，鲁棒性强
• 对于未知特性的数据集都可以先用K-means试试

缺点

• 对于离群点和孤立点敏感
• k值选择
• 初始聚类中心的选择
• 只能发现球状簇

改进

• LOF检测离群点通过去除离群点后在聚类，减少离群点和孤立点对于聚类效果的影响
• 一开始给定一个适合的数值给k，通过一次k-means算法得到一次聚类中心。对于得到的聚类中心，根据得到的k个聚类的距离情况，合并距离最近的类，因此聚类中心数减小，当将其用于下次聚类时，相应的聚类数目也减小，最终得到合适数目的聚类数。可以通过一个评判值E来确定聚类数得到一个合适的位置停下来，而不继续合并聚类中心。重复上述循环，直至评判函数收敛为止，最终得到较优聚类数的聚类结果。
• 首先随机选择一个点作为第一个初始类簇中心点，然后选择距离该点最远的那个点作为第二个初始类簇中心点，然后在选择距离前两个点的最近距离最大的点作为第三个初始类簇的中心点，以此类推，直至选出k个初始类簇中心点

Mean-Shift

Mean-shift聚类是一个基于滑窗的算法，尝试找到数据点密集的区域。它是一个基于质心的算法，也就是说它的目标是通过更新中心点候选者定位每个组或类的中心点，将中心点候选者更新为滑窗内点的均值。这些候选滑窗之后会在后处理阶段被过滤，来减少邻近的重复点，最后形成了中心点的集合和它们对应的组

算法流程

1. 在未被标记的数据点中随机选择一个点作为起始中心点center；
2. 找出以center为中心半径为radius的区域中出现的所有数据点，认为这些点同属于一个聚类C。同时在该聚类中记录数据点出现的次数加1。
3. 以center为中心点，计算从center开始到集合M中每个元素的向量，将这些向量相加，得到向量shift。
4. center = center + shift。即center沿着shift的方向移动，移动距离是||shift||。
5. 重复步骤2、3、4，直到shift的很小（就是迭代到收敛），记住此时的center。注意，这个迭代过程中遇到的点都应该归类到簇C。
6. 如果收敛时当前簇C的center与其它已经存在的簇C2中心的距离小于阈值，那么把C2和C合并，数据点出现次数也对应合并。否则，把C作为新的聚类。
7. 重复1、2、3、4、5直到所有的点都被标记为已访问。
8. 分类：根据每个类，对每个点的访问频率，取访问频率最大的那个类，作为当前点集的所属类。

应用

1. 图像平滑：图像最大质量吓得像素压缩
2. 图像分割：跟图像平滑类似的应用，但最终是将可以平滑的图像进行分离以达到前后景或固定物理分割的目的
3. 目标跟踪：例如针对监控视频中某个任务的动态跟踪
4. 常规聚类，如用户聚类等

优点

1. 算法计算量不大，在目标区域已知的情况下完全可以做到实时跟踪；
2. 采用核函数直方图模型，对边缘遮挡、目标旋转、变形和背景运动不敏感。

缺点

1. 缺乏必要的模板更新；
2. 跟踪过程中由于窗口宽度大小保持不变，当目标尺度有所变化时，跟踪就会失败；
3. 当目标速度较快时，跟踪效果不好；
4. 直方图特征在目标颜色特征描述方面略显匮乏，缺少空间信息；

由于其计算速度快，对目标变形和遮挡有一定的鲁棒性，所以，在目标跟踪领域,meanShift算法目前依然受到大家的重视。但考虑到其缺点，在工程实际中也可以对其作出一些改进和调整；例如：
5. 引入一定的目标位置变化的预测机制，从而更进一步减少meanShift跟踪的搜索时间，降低计算量；
6. 可以采用一定的方式来增加用于目标匹配的“特征”；
7. 将传统meanShift算法中的核函数固定带宽改为动态变化的带宽；
8. 采用一定的方式对整体模板进行学习和更新；

基于密度的带噪声的空间聚类的应用 DBSCAN

基于距离的聚类算法的聚类结果是球状的簇，当数据集中的聚类结果是非球状结构时，基于距离的聚类算法的聚类效果并不好。与基于距离的聚类算法不同的是，基于密度的聚类算法可以发现任意形状的聚类。在基于密度的聚类算法中，通过在数据集中寻找被低密度区域分离的高密度区域，将分离出的高密度区域作为一个独立的类别。

算法原理

1. 首选任意选取一个点，然后找到到这个点距离小于等于 eps 的所有的点。如果距起始点的距离在 eps 之内的数据点个数小于 min_samples，那么这个点被标记为噪声。如果距离在 eps 之内的数据点个数大于 min_samples，则这个点被标记为核心样本，并被分配一个新的簇标签。
2. 然后访问该点的所有邻居（在距离 eps 以内）。如果它们还没有被分配一个簇，那么就将刚刚创建的新的簇标签分配给它们。如果它们是核心样本，那么就依次访问其邻居，以此类推。簇逐渐增大，直到在簇的 eps 距离内没有更多的核心样本为止。
3. 选取另一个尚未被访问过的点，并重复相同的过程。

DBSCAN的参数选择

• eps 设置得非常小，则意味着没有点是核心样本，可能会导致所有点被标记为噪声
  eps 设置得非常大，可能会导致所有点形成单个簇。
• 虽然不需要显示设置簇的个数，但设置 eps 可以隐式地控制找到 eps 的个数。
• 使用 StandarScaler 或 MinMaxScaler 对数据进行缩放，有时更容易找到 eps 的较好取值。因为使用缩放技术将确保所有特征具有相似的范围。

优点

• 不需要用户先验地设置簇的个数，可以划分具有复杂形状的簇，还可以找出不属于任何簇的点。
• 可以对任意形状的稠密数据集进行聚类，相对的，K-Means之类的聚类算法一般只适用于凸数据集。
• 可以在聚类的同时发现异常点，对数据集中的异常点不敏感。
• DBSCAN 比凝聚聚类和 k 均值稍慢，但仍可以扩展到相对较大的数据集。

缺点

• 需要设置eps当数据量增大时，要求较大的内存支持I/O消耗也很大；
• 当空间聚类的密度不均匀、聚类间距差相差很大时，聚类质量较差，因为这种情况下参数MinPts和Eps选取困难。
• 算法聚类效果依赖与距离公式选取，实际应用中常用欧式距离，对于高维数据，存在“维数灾难”。

基于高斯混合模型(GMM)的期望最大化（EM）聚类

GMM和k-means很想，k-means的结果是每个数据点被assign到其中一个cluster，而GMM是学习出数据点被addign到每个cluster的概率
GMM常用于聚类，通过选择成分最大化后验概率来完成聚类。高斯混合模型也是用迭代算法计算，最终收敛到局部最优。高斯混合模型在各类尺寸不同、聚类间有相关关系的时候可能比k-means聚类更合适。
从几何上讲，单高斯模型分布在二维空间应该更接近于椭圆，在三维空间上近似于椭球。遗憾的是在很多分类问题中，属于同一类别的样本点并不满足“椭圆”分布的特性。这就引入了高斯混合模型。
观整个高斯模型，他主要是由方差和均值两个参数决定，,对均值和方差的学习,采取不同的学习机制,将直接影响到模型的稳定性、精确性和收敛性。
每个 GMM 由 K 个 Gaussian 分布组成，每个 Gaussian 称为一个“Component”，这些 Component 线性加成在一起就组成了 GMM 的概率密度函数：
$$p(x)=\sum _{k=1}^{K}p(k)p(x|k)=\sum _{k=1}^K{\pi }_{k}N(x|{\mu }_k,{\Sigma }_k)$$
根据上面的式子，如果我们要从 GMM 的分布中随机地取一个点的话，实际上可以分为两步：首先随机地在这 K 个 Component 之中选一个，每个 Component 被选中的概率实际上就是它的系数 ${\pi }_k$，选中了 Component 之后，再单独地考虑从这个 Component 的分布中选取一个点就可以了──这里已经回到了普通的 Gaussian 分布，转化为了已知的问题。
那么如何用 GMM 来做 clustering 呢？其实很简单，现在我们有了数据，假定它们是由 GMM 生成出来的，那么我们只要根据数据推出 GMM 的概率分布来就可以了，然后 GMM 的 K 个 Component 实际上就对应了 K 个 cluster 了。根据数据来推算概率密度通常被称作 density estimation ，特别地，当我们在已知（或假定）了概率密度函数的形式，而要估计其中的参数的过程被称作“参数估计”。
现在假设我们有 N 个数据点，并假设它们服从某个分布（记作 p(x) ），现在要确定里面的一些参数的值，例如，在 GMM 中，我们就需要确定 ${\pi }_k$、${\mu }_k$ 和${\Sigma }_k$ 这些参数。 我们的想法是，找到这样一组参数，它所确定的概率分布生成这些给定的数据点的概率最大，而这个概率实际上就等于 ${\prod }_{i=1}^{N}p(x_i)$，我们把这个乘积称作似然函数 (Likelihood Function)。通常单个点的概率都很小，许多很小的数字相乘起来在计算机里很容易造成浮点数下溢，因此我们通常会对其取对数，把乘积变成加和 ${\sum }_{i=1}^N\log p(x_i)$，得到 log-likelihood function 。接下来我们只要将这个函数最大化（通常的做法是求导并令导数等于零，然后解方程），亦即找到这样一组参数值，它让似然函数取得最大值，我们就认为这是最合适的参数，这样就完成了参数估计的过程。
　　下面让我们来看一看 GMM 的 log-likelihood function ：
$\sum _{i=1}^N\log \left\{\sum _{k=1}^K{\pi }_k\mathcal{N}(x_i|{\mu }_k,{\Sigma }_k)\right\}$
　　在最大似然估计里面，由于我们的目的是把乘积的形式分解为求和的形式，即在等式的左右两边加上一个log函数，转化为log后，还有log(a+b)的形式，因此，要进一步求解。
由于在对数函数里面又有加和，我们没法直接用求导解方程的办法直接求得最大值。为了解决这个问题，我们采取之前从 GMM 中随机选点的办法：分成两步，实际上也就类似于 K-means 的两步。

EM实现

1. 假设模型参数已知，求概率。估计数据由每个 Component 生成的概率（并不是每个 Component 被选中的概率）：对于每个数据 $x_i$来说，它由第 k 个 Component 生成的概率为$\gamma (i,k)=\frac{{\pi }_k\mathcal{N}(x_i|{\mu }_k,{\Sigma }_k)}{{\sum }_{j=1}^K{\pi }_j\mathcal{N}(x_i|{\mu }_j,{\Sigma }_j)}$
   由于式子里的 ${\mu }_k$ 和 ${\Sigma }_k$ 也是需要我们估计的值，我们采用迭代法，在计算 $\gamma (i,k)$ 的时候我们假定 ${\mu }_k$和 ${\Sigma }_k$ 均已知，我们将取上一次迭代所得的值（或者初始值）。
2. 根据概率值和最大似然估计找到参数。估计每个 Component 的参数：现在我们假设上一步中得到的 $\gamma (i,k)$ 就是正确的“数据$x_i$ 由 Component k 生成的概率”，亦可以当做该 Component 在生成这个数据上所做的贡献，或者说，我们可以看作 $x_i$ 这个值其中有 $\gamma (i,k)x_i$ 这部分是由 Component k所生成的。集中考虑所有的数据点，现在实际上可以看作 Component 生成了 $\gamma (1,k)x_1,\dots ,\gamma (N,k)x_N$ 这些点。由于每个 Component 都是一个标准的 Gaussian 分布，可以很容易分布求出最大似然所对应的参数值：$\begin{array}{rl}{\mu }_k& =\frac{1}{N_k}\sum _{i=1}^N\gamma (i,k)x_i\\ {\Sigma }_k& =\frac{1}{N_k}\sum _{i=1}^N\gamma (i,k)(x_i-{\mu }_k)(x_i-{\mu }_k{)}^T\end{array}$
   其中 $N_k={\sum }_{i=1}^N\gamma (i,k)$ ，并且 ${\pi }_k$ 也顺理成章地可以估计为 $N_k/N$ 。
3. 重复迭代前面两步，直到似然函数的值收敛为止。

k-means和GMM的区别与联系

相同点

• 两者都是迭代算法，并且迭代策略大致相同：算法开始对需要计算的参数赋初值，然后交替执行两个步骤。第一个步骤是对数据的估计，k-means是估计每个点所属簇，GMM是计算隐含变量的期望。第二个步骤是用第一步的估计值重新计算参数值，更新目标参数。其中k-means是计算簇心位置；GMM是计算各个高斯分布的中心位置和协方差矩阵。
  不同点
• k-means是计算簇心位置，GMM是计算各个高斯分布的参数。
• k-means是计算当前簇中所有元素的位置的均值，GMM是通过计算似然函数的最大值实现分布参数的求解的。

原理分析

混合高斯模型基于多变量正态分布。通过使用EM算法来拟合数据，它基于各观测量计算各成分密度的后验概率

凝聚层次聚类

凝聚法分层聚类中有一堆方法可以用来算两点（pair）之间的距离：欧式，欧式平方，manhattan等，还有一堆方法可以算类（cluster）与类之间的距离，什么single-linkage、complete-linkage、还有这个ward linkage。（即最短最长平均，离差平方和）

算法

首先假定每个样本都是一个独立的聚类,输入的是一个距离矩阵，知道每两个点之间的距离。然后初始化是每个点做为一个cluster，假设总共N组，此时每个组内的ESS都是0
$ESS={\sum }_{i=1}^n{x}_i^2-\frac{1}{n}({\sum }_{i=1}^n{x}_i{)}^2$
如果统计出来的聚类数大于期望的聚类数，则从每个样本出发寻找离自己最近的另一个样本，与之聚集，形成更大的聚类。枚举所有二项cluster【N个cluster是N*(N-1)/2个二项集】，计算合并这两个cluster后的总ESS值。将总ESS值增长最小的那两个cluster合并。重复这个步骤直到聚类数等于期望的聚类数。

特点

1. 聚类数k必须事先已知。借助某些评估指标，优选最好的聚类数。
2. 没有聚类中心的概念，因此只能在训练集中划分聚类，但不能对训练集以外的未知样本确定其聚类归属。不能预测。
3. 在确定被凝聚的样本时，除了以距离作为条件以外，还可以根据连续性来确定被聚集的样本。

参考

• https://blog.csdn.net/Dhane/article/details/86661208
• https://baijiahao.baidu.com/s?id=1625408992304959354&wfr=spider&for=pc
• https://www.cnblogs.com/hxsyl/p/5559043.html
• http://blog.sciencenet.cn/blog-2827057-1145924.html

关于作者

知乎

最后

以上就是现代钢笔为你收集整理的五种聚类算法思想总结聚类算法参考关于作者的全部内容，希望文章能够帮你解决五种聚类算法思想总结聚类算法参考关于作者所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。