机器学习面试题——聚类算法

提示：互联网大厂经常考的传统机器学习算法

文章目录

机器学习面试题——聚类算法
@[TOC](文章目录)

题目
k-means介绍一下，K-means的过程
k-means优缺点
k-means的簇（k簇）怎么选，K-means如何选取K值
k-means如何调优，kmeans聚类如何选择初始点？
知道哪些聚类模型，聚类算法知道哪些
kmeans聚类，聚的是特征还是样本？特征的距离如何计算？
Kmeans算法和EM算法的关系
写Kmeans代码
总结

题目

机器学习面试题汇总与解析——聚类

k-means介绍一下
k-means优缺点
k-means的簇怎么选
k-means如何调优
知道哪些聚类模型
K-means的过程
K-means如何选取K值
kmeans聚类如何选择初始点
kmeans聚类，聚的是特征还是样本？特征的距离如何计算？
聚类算法知道哪些
Kmeans算法和EM算法的关系
写Kmeans代码

k-means介绍一下，K-means的过程

K-Means算法的思想很简单：
（1）事先确定常数K，即最终的聚类类别数
（2）首先随机选定每个类的初始点为质心，并通过计算每一个样本x与质心之间的相似度(这里为欧式距离)，将样本点归到最相似的类中（最近的类）
（3）接着，更新每个类的质心(即为类中心)
（4）重复（1）–（3）这样的过程，直到质心不再改变，最终就确定了每个样本所属的类别以及每个类的质心。
在这里插入图片描述

由于每次都要计算所有的样本与每一个质心之间的相似度，
故在大规模的数据集上，K-Means算法的收敛速度比较慢。

k-means优缺点

优点：原理简单，实现容易
缺点：收敛较慢 =算法时间复杂度比较高 O(nkt)、不能发现非凸形状的簇、需要事先确定超参数K、对噪声和离群点敏感、结果不一定是全局最优，只能保证局部最优

k-means的簇（k簇）怎么选，K-means如何选取K值

**手肘法：**当误差手肘处拐变，然后不咋巨变，那拐点就是k
比如下图k=3，手肘处的k
在这里插入图片描述

k-means如何调优，kmeans聚类如何选择初始点？

（0）初始点随机分布
（1）数据归一化和离群点的处理：
上面也说了k-means是根据欧式距离来度量数据的划分，**均值和方差大的数据会对结果有致命的影响。**同时，少量的噪声也会对均值产生较大的影响，导致中心偏移。所以在聚类前一定要对数据做处理。
（2）**选择合适的k值：**k-means++方法，在一开始确定簇时，让所有簇中心坐标两两距离最远。

知道哪些聚类模型，聚类算法知道哪些

聚类方法其实有很多，但k-means是最简单、最常考的一种。
（1）K-Means聚类（上面1说过了）
（2）均值漂移聚类
（3）具噪声基于密度的空间聚类算法
（4）高斯混合模型的期望最大化聚类
（5）凝聚层次聚类

（2）均值漂移聚类

Mean-Shift聚类是基于滑动窗口的算法，试图找到数据点的密集区域。
这是一种基于质心的算法，意味着其目标是定位每个簇的中心点，
通过将滑动窗口的均值点作为候选点来迭代更新中心点。
在后处理阶段将消除近似重复的窗口，最终形成一组中心点及其相应的簇。
——与K-means聚类相比，Mean-Shift的最大优势就是可以自动发现簇的数量而不需要人工选择。
簇的中心向最大密度点聚合的事实也是非常令人满意的，因为它可被非常直观地理解并很自然地契合数据驱动。
在这里插入图片描述

（3）具噪声基于密度的空间聚类算法

DBSCAN（Density-Based Spatial Clustering of Applications with Noise）是一种基于密度的聚类算法，类似于Mean-Shift，但具有一些显著的优点。
在这里插入图片描述

（4）高斯混合模型的期望最大化聚类

K-Means的主要缺点之一是其简单地使用了平均值作为簇的中心。
高斯混合模型（GMMs）相比于K-Means来说有更多的灵活性。
对于GMMs，我们假设数据点是服从高斯分布的（对于用均值进行聚类，这一假设是个相对较弱的限制）。
这样，我们有两个参数来描述簇的形状：均值和标准差！
以二维为例，这意味着簇可以采用任何类型的椭圆形（因为我们在x和y方向都有标准偏差）。因此，每个簇都有一个高斯分布。
在这里插入图片描述

（5）凝聚层次聚类
分层聚类算法实际上分为两类：自上而下或自下而上。
自下而上算法首先将每个数据点视为单个簇，然后不断合并（或聚合）成对的簇，直到所有簇合并成一个包含所有数据点的簇。因此自下而上的层次聚类被称为分层凝聚聚类或HAC。该簇的层次结构被表示为树（或树状图）。树的根是包含所有样本的唯一的簇，叶是仅有一个样本的簇。在进入算法步骤之前，请查看下面的图解。
在这里插入图片描述
分层聚类不要求我们指定聚类的数量，因为我们在构建一棵树，我们甚至可以选择哪个数量的簇看起来最好。
另外，该算法对距离度量的选择不敏感，它们的效果都趋于相同，而对其他聚类算法而言，距离度量的选择则是至关重要的。