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

【1】当数据缺失时怎么处理，除了直接舍去还有什么方法。如何使用聚类算法去填补缺失值。

答：

• 对于缺失值较多的特征处理：我们直接将该特征弃掉，否则可能反倒会带入较大的noist，对结果造成不良影响。
• 对于缺失值较少的特征处理：
  （1）把缺失值用一个数值，例如0表示；
  （2）均值，中值，分位数、众数，随机数，上下数据填充，插值法；
  （3）用算法拟合进行填充；
  

对于如何使用聚类算法去填补缺失值，我想到的是用KNN方法去预测，也就是 KNeighborsRegressor 把非缺失值当作特征，把缺失值当作label，然后通过KNN算法去预测。也就是上面图片中的KNN插值。

【2】kmeans聚类算法的实现流程

k-means有三个基本步骤：

• （1）在选择初始化质心，最基本的方法就是从数据集$X$X中选择$k$k个样本。在初始化后，k-means就由剩下两步循环完成。
• （2）通过计算将本样本分到其最近的质心。
• （3）通过取分配给每个质心的所有样本的均值来创建新的质心。计算新旧质心之间的差值，重复上面两步（2）（3），直到差值小于阈值。

【3】kmeans的初始化方法有哪些

• k-means++¹:
  设$D(x)$D(x)为数据集中的一点到我们已经选定的最近的中心点的最断距离。然后进行下面的计算：
  1a:从数据集$X$X中均匀随机选取一个中心点$c_1$c1​
  1b.选择新的中心点$c_i$ci​,但是选择的$x$x的概率为$\frac{D(x)^2}{\sum_{x\in X D(x)^2}}$∑x∈XD(x)2​D(x)2​
  1c.重复1b的步骤，直到选出$k$k个中心点。
• random:随机的从数据集中选出$k$k个点选出数据。
• 自己定义的中心点，但是narray的大小要一致，为（n_clusters, n_features）.

【4】如果kmeans的初始点是随机选取的，怎么知道哪种聚类结果是好的？比如重复了100次，哪一次聚类是最优的

我们要去定义一个评价的标准，在kmeans中我们定义这样一个标准
$\sum_{i = 0}^n min_{\mu_j \in C}(||x_i -\mu_j||^2)$i=0∑n​minμj​∈C​(∣∣xi​−μj​∣∣2)
在每次重复的时候我们都去计算这个值，然后存储起来最后就可以得到哪次是最优的。

【5】kmeans中的距离是怎么定义的，kmeans计算距离的权重怎么分配，如果是欧氏距离，那么性别（0（表未知）、1和2）和年龄（20、30和40）的这种怎么处理

（1）距离定义为$||x_i - \mu_j||^2$∣∣xi​−μj​∣∣2，其中，$x_i$xi​是样本点，$\mu_j$μj​是中心点。
（2）权重均匀，或者基于距离的
（3）首先年龄进行归一化处理，然后对性别进行热编码，然后使用kmeans算法。

【6】kmeans的收敛问题

kmeans一定收敛：

【7】别的聚类算法

AP聚类算法，Mean Shift等

【8】聚类的相似度计算方法（余弦相似度，欧氏距离）

• 余弦相似度²：通过测量两个向量的夹角的余弦值来度量它们之间的相似性。0角度的余弦值是1，而其它任何角度的余弦值都不大于1，并且其最小值为-1，从而两个向量之间的角度的余弦值确定两个向量是否大致指向相同的方向。两个向量有相同的指向时，余弦相似度的值为1；两个向量夹角为90°时，余弦相似度的值为0；两个向量指向完全相反的方向时，余弦相似度的值为-1。这结果是与向量的长度无关的，仅仅与向量的指向方向相关。余弦相似度通常用于正空间，因此给出的值为0到1之间。另外外，它通常用于文本挖掘中的文件比较。此外，在数据挖掘领域中，会用到它来度量集群内部的凝聚力。
  两个向量之间的余弦值可用通过使用欧几里得点积公式求出：
  $a ·b = ||a|| ·||b||·cos \theta$a⋅b=∣∣a∣∣⋅∣∣b∣∣⋅cosθ
  给定两个属性向量，$A$A和$B$B，其余弦相似性$\theta$θ为：
  $similarity = cos(\theta) = \frac{A ·B}{||A||·||B||} = \frac{\sum_{i = 1}^nA_i*B_i}{\sqrt{\sum_{i=1}^n(A_i)^2} * \sqrt{\sum_{i =1}^n(B_i)^2}}$similarity=cos(θ)=∣∣A∣∣⋅∣∣B∣∣A⋅B​=∑i=1n​(Ai​)2​∗∑i=1n​(Bi​)2​∑i=1n​Ai​∗Bi​​

• 欧式距离³：
  $similary = distance(A, B) = \sqrt{||A-B||^2} = \sqrt{\sum_{i = 1}^n||A_i - B_i||^2}$similary=distance(A,B)=∣∣A−B∣∣2​=i=1∑n​∣∣Ai​−Bi​∣∣2​

---

1. 1: The Advantages of Careful Seeding http://ilpubs.stanford.edu:8090/778/1/2006-13.pdf ↩︎

2. 2: 余弦相似性:https://en.wikipedia.org/wiki/Cosine_similarity ↩︎

3. 3: 欧式距离:https://en.wikipedia.org/wiki/Euclidean_distance ↩︎