作者马东什么@知乎（已授权）

来源丨https://zhuanlan.zhihu.com/p/391954665

极市平台编辑

最近参加社会招聘，面试基本上是问项目，然后问项目算法，所以这里或根据实际面试过程总结，因为项目涉及不同的领域，所以统一整理以免忘记，当然，主营业务仍在machine learning因此，传统的机器学习算法主要是时间序列预测，nlp,Graph这些涉及的部分只会总结相关知识点，所以不会系统总结。没有必要，也很麻烦.

之前整理的材料主要是19年10月之前。这一次，几乎所有19年后可以找到的面经都扩大了范围，包括cv,推荐、语音等面经知识点，同时增加了三本面经书的内容github对于一些热门项目，大部分问题都是重复的。去重之后，其实大概就是百道题了。.

无监督相关(聚类、异常检测等):

问：熟悉哪些距离度量的方法？写一下距离计算公式？

1.连续数据距离计算：

闵可夫斯基离家：

当p=1时，就是曼哈顿距离；

当p=2.欧氏距离；

当p→∞切比雪夫距离。

余弦距离：

当向量模长归一化为1时，余弦距离和欧式距离可以相互转换。余弦距离不是

2.距离计算：

杰卡尔德距离：A，B集合交集/A,B集合的并集

汉明距离：在相应位置表示两个等长字符串不同字符的数量

关于距离计算，我遇到了一个单独的研究，因为它也是一个非常大的内容。上述距离计算公式是基于样本-样本 之间的简单距离计算，当引入核方法映射时，会有一些相应的更复杂的距离计算方法，此外，迁移学习样本组，即不同数据集之间的分布距离计算也是一个大内容，面试不应该问太复杂，这里暂时不深入。

问:你知道哪些常见的聚类算法？你对聚类了解多少？

https://zhuanlan.zhihu.com/p/394909171

简单回答，基于划分，基于密度，基于网格，层次聚类，此外，聚类和其他领域也有许多交叉领域，如半监督聚类、深度聚类、集成聚类等等；

问：kmeans原理是什么？

kmeans是一种基于划分的聚类，中心思想很简单，类内距离尽可能小，类间距尽可能大，算法过程如下：

1.初始化k作为最初的质感k个簇中心点，k人工设置的超参数；

2.所有样本点n分别计算和k这里的距离也是人工定义的，可以是不同的距离计算方法，每个样本点和k个质心中最近的质心分为一类簇；

3.重新计算质心的方法是聚合计算簇，kmeans采用简单平均的方法进行聚合计算，也可采用中位数等方法进行计算；

4.重复上述过程，直到达到预定的迭代次数或纹理不再发生明显变化

问：kmeans什么是损失函数？

其中，K是聚类数，p是样本，是第k聚类中心点。SSE样本聚合程度越小，越高。

问：kmeans如何选择初始点？选择不同初始点的策略有哪些缺陷？如何解决？

1.随机初始化：随机选择k样本点作为初始纹理，缺点是，如果选择的纹理距离非常接近同一簇，迭代结果可能相对较差，因为最终迭代的纹理点会落在簇之间，

最理想的状态是k质感恰到好处k由于随机初始化的随机性，可以多次考虑随机初始化，选择聚合结果最好的一次(这里涉及聚类评价方法)；

2.初始化的随机划分：如果所有样本点随机给出一个簇，则所有样本点最终将有k一个编号，然后进行组平均，即对同一组样本进行平均初始纹理。与随机初始化相比，初始纹理将更好，但仍有随机初始化的缺陷，只是缓解；

3.kmeans

kmeans 是一种启发性的初始化策略:

Kmeans 聚类算法原理与实现：https://zhuanlan.zhihu.com/p/152286357

①从数据集中随机(均匀分布)中选择样本点作为第一个初始聚类中心；

②然后计算每个样本与现有聚类中心之间的计算最短距离，使用表示；然后计算每个样本点被选为下一个聚类中心的概率，最后选择最大概率值对应的样本点作为下一个簇中心；

事实上，选择最短距离最大的样本点作为下一个初始化聚类中心点

③重复第②直到选择聚类中心；

kmeans 是一种没有严格理论证明的启发性初始化策略sklearn中kmeans的默认的初始化策略；

4.其它聚类算法的初始化策略：

使用其他聚类算法计算k个质心点作为kmeans初始质感，我挺傻的，好像有亿点麻烦。

4.kmeans是特征还是样本？如何计算特征的距离？

一般来说，样本聚类，如果特征聚类处理简单，原始输入.T ，即转移。其目的与相关系数相似，如果两个特征高度相关，如收入和资产水平，两个特征之间的距离相对较小，但一般不可行，因为转移后，维度往往很高，如100万样本有100万维度，计算不现实，高维数据距离测量无效，最好直接计算相关系数；

5.为什么欧式距离的测量在高维空间中逐渐失效？

《When Is “Nearest Neighbor” Meaningful?》

维度d高维空间中任何两个样本点的最大距离和最小距离趋于相等，距离度量失效；

问.聚类数量如何确定？K(如果不知道有多少种聚类，有什么方法？

选择某种方式，就像评估分类或回归一样metric或某些metrics下最好的k，例如sse（其实就是kmeans损失函数)、轮廓系数、兰德指数、互信息等；

如果聚类本身服务于监督任务(如聚类产生)features用于下游任务)，可直接根据下游任务metrics更好的评估；

问：k-means如何调优

1.初始化策略调参；

2.k大小参考，手工方法，肘法为代表；

3.处理数据归一化和异常样本；

问：介绍肘法（gap statistic计算很麻烦，这里就不写了)？

肘法没什么特别的。纵轴是聚类效果的评价指标。根据具体问题，如果存在聚类作为单独的任务，则使用它sse或轮廓系数等非监督系数metric作为纵坐标，然后找到metric最好并且k最小结果对应k最终选择；

手肘法其实也很容易做成自动化，我们计算metric可以计算变化的斜率。k=n和k=n 1之间的斜率，当 斜率n和斜率n-1，斜率n 1和斜率n，斜率n 2和斜率n 1的差值小于固定阈值时即可停止，代码实现的思路与早停基本一致；

问：k-means如何解决缺点？

1.对异常样本非常敏感，簇心会因为异常样本被拉得很远

注意，这里的异常样本只是指在某些特征维度上取值特别大或特别小的样本，是异常检测中定义的异常样本的子集，因为欧洲距离的计算不考虑不同变量之间的差异联合分布，默认所有特征是相互独立的，所以kmeans中会对结果产生影响的异常样本特指简单的异常样本，即某些特征维度存在异常值的样本，这类异常样本通过简单的统计就可以得到；

解决方法即做好预处理，将异常样本剔除或修正；

2.k值需要事先指定，有时候难以确定；

解决方法即针对k调参；

3.只能拟合球形簇，对于流形簇等不规则的簇或是存在簇重叠问题的复杂情况等，效果较差

解决方法，换算法；

4.无法处理离散特征，缺失特征，

5.无法保证全局最优

解决方法：矮子里面挑高个，跑多次，取不同的局部最优里最优的

问：dbscan和optics是怎么解决这些缺点的？

dbscan和optics是基于密度的聚类

1.kmeans对异常样本很敏感，簇心会因为异常样本被拉得很远

dbscan和optics定义了密度的计算方式，不涉及到任何的平均这种鲁棒性较差的计算方式，对异常样本不敏感，还能检测异常样本呢；

2.k值需要事先指定，有时候难以确定；

dbscan和optics不需要指定簇的数量；算法迭代过程中自然而然产生最优的k个聚类簇；

3.只能拟合球形簇，对于流形簇等不规则的簇或是存在簇重叠问题的复杂情况等，效果较差

基于密度的聚类可以拟合任意形状的簇，这也归功于密度的计算方式，基于密度的聚类本身不对聚类簇的形状有任何的假设；

4.无法处理离散特征，缺失特征：缺失特征要插补，离散特征可以换离散特征的距离度量方法，基于密度的聚类算法可以灵活搭配各种不同的distance的度量方式；

5.无法保证全局最优：未解决

问：讲一下dbscan和optics的大致思路？

dbscan：单个超球体，病毒式扩散；

optics：两个嵌套的超球体一大一小，先映射为直方图，然后从直方图上生成聚类结果

dbscan和optics：https://zhuanlan.zhihu.com/p/395088759

问：kmeans是否一定可以收敛，为什么？kmeans为什么无法保证全局最优？

收敛性证明就算了吧。。.这也太超纲了。.。

kmeans的损失函数是一个非凸函数，所以无法保证全局最优；

from K Means为什么不能收敛到全局最优点？-SofaSofa：http://sofasofa.io/forum_main_post.php?postid=1002942

kmeans的损失函数，需要记忆一下

这里μk是第k个簇的质心，

为了方便描述，假设x是2维的，取k=1，则我们令：

uk是待求解变量，画出：z=

的函数图像：

可以看到，优化目标z存在(1,1),(-1,1)两个最优解，所以kmeans的损失函数不是一个凸函数而是一个非凸函数，难以保证收敛到全局最优。

问：为什么在一些场景中要使用余弦相似度而不是欧氏距离？

如果A，B两个向量e 的模场均为1，则欧式距离和余弦距离之间满足：

总体来说，欧氏距离体现数值上的绝对差异，而余弦距离体现方向上的相对差异。例如，统计两部剧的用户观看行为，用户A的观看向量为(0,1)，用户B为 (1,0)；此时二者的余弦距离很大，而欧氏距离很小；我们分析两个用户对于不同视频的偏好，更关注相对差异，显然应当使用余弦距离。而当我们分析用户活跃度，以登陆次数(单位：次)和平均观看时长(单位：分钟)作为特征时，余弦距离会认为(1,10)、(10,100)两个用户距离很近；但显然这两个用户活跃度是有着极大差异的。

因此，我们关注向量数值绝对差异，应当使用欧氏距离，如果关心的是向量方向上的相对差异，则应当使用余弦距离。

问：余弦距离是否是一个严格定义的距离? （一个度量标准要满足什么要求才能算是距离）

该题主要考察面试者对距离的定义的理解，以及简单的反证和推导。首先看 距离的定义：在一个集合中，如果每一对元素均可唯一确定一个实数，使得三条距离公理（正定性，对称性，三角不等式）成立，则该实数可称为这对元素之间的距离。

余弦距离满足正定性和对称性，但是不满足三角不等式，因此它并不是严格定义的距离。

问：K-means 中我想聚成100类 结果发现只能聚成98类，为什么？

迭代的过程中出现空簇，原因在于k太大，实际的簇数量小于k；

初始化策略不会导致空簇的问题，因为即使最简单的随机初始化也是从原始的样本点里选择部分样本作为质心，如果初始质心中存在异常样本，则最终聚类的结果，这个异常点会自成一个簇而不会出现空簇的问题；

https://datascience.stackexchange.com/questions/44897/k-means-clustering-what-to-do-if-a-cluster-has-0-elements

空簇对应的中心点和任意一个样本点的距离都不是该样本点距离其它质心点的距离的最小值。

问：kmeans，GMM，EM之间有什么关系？

kmeans是基于划分的聚类算法，GMM是基于模型的聚类算法，EM是估计GMM的参数使用的优化算法；

1. kmeans可以看作是GMM的一种特例，于协方差为单位矩阵，故kmeans聚类的形状是球形的，而GMM是椭球型的；

2. kmeans使用hard EM求解，GMM使用soft EM求解（kmeans感觉还是从直观上的计算过程上理解比较舒服，通过hard em也是一个解释就是了）;

关于上述的原因，在下一个问题里说明

问：高斯混合模型的核心思想是什么？（GMM和多元高斯有什么区别？，多元高斯函数的期望是什么）

GMM就是多个相关多元高斯分布的加权求和；

理解GMM之前，先回归基本概念：

1.一元高斯分布：

现在我们将高斯分布扩展到多维空间，简单说就是有x1，x2，x3。。。xn等多个维度。当我们假设多维空间的每一个空间之间完全独立，则独立的n元高斯分布为：

可以看到，是非常类似的，根号2pi部分取n次方，方差用协方差矩阵代替，代数的乘法转化为矩阵乘法；多元高斯分布的期望就是观测样本的（样本向量-所有特征向量的均值构成的均值向量）进行和自身的向量乘计算；

协方差矩阵：

协方差矩阵是一个nXn的矩阵，n代表了多元的大小，对于协方差矩阵中的每一个元素，计算公式如下：

具体展开来看就是：

协方差矩阵和相关系数的关系：

可以看到，相关系数的计算过程中，已经对变量做了均值方差的标准化处理了，所以对两个特征计算相关系数不需要考虑量纲大小的问题；

现实世界中，不同的特征（多个特征=多元）很难完全独立，因此我们也会使用非独立的多元高斯分布，公式写作：

402 Payment Required

可以看到，公式层面上，独立多元高斯分布和非独立（相关）多元高斯分布的形式是一样的，只不过协方差矩阵不同：

独立多元高斯分布除对角线之外其它元素的值均为0，相关多元高斯分布则其它元素的值为特征之间的协方差的计算结果；

高斯混合模型：

高斯混合模型GMM是多元高斯分布之上的概念，他认为现实世界的数据是由多个不同参数的相关多元高斯模型以不同的权重累积求和构成的（单元，独立多元高斯模型可以看作相关多元高斯模型的特例）；

其中：

是第个子模型的相关多元高斯分布，是观测数据属于第个子模型的概率；因此对于GMM而言，其参数，即每个子模型的均值向量、协方差矩阵以及在GMM中该子模型的权重；

对于相关多元高斯混合模型，其参数仅包含均值向量和协方差矩阵，可以直接通过极大似然法写出极大似然函数，然后通过求导进行参数估计，具体的通过极大似然法可以直接推导出均值向量和协方差矩阵关于输入向量X的计算公式，带入数据集X可以直接求解；

而GMM的极大似然函数较为复杂：

由于存在（观测数据属于第个子模型的概率）这个隐变量，无法直接求导得到参数的估计结果，因此通过EM算法来进行迭代式的求解；

问：GMM是如何迭代计算的？为什么kmeans，GMM，EM满足上面描述的方式？（EM算法数学原理）

首先需要了解em算法，em算法和梯度下降法一样，都可以用来优化极大似然函数，当极大似然函数中存在隐变量时，EM算法是一种常用的优化算法；

EM算法是一种迭代优化策略，由于它的计算方法中每一次迭代都分两步，其中一个为期望步（E步），另一个为极大步（M步），所以EM算法被称为EM算法（Expectation-Maximization Algorithm）

jensen不等式：

如果f是凸函数，X是随机变量，那么：。当且仅当X是常量时，该式取等号。其中，E(X)表示X的数学期望。Jensen不等式应用于凹函数时，不等号方向反向。当且仅当x是常量时，该不等式取等号。

如上图，实线f表示凸函数，X是随机变量，有0.5的概率是a，有0.5的概率是b。X的期望值就是a和b的中值，从图中可以看到成立。

问：GMM的损失函数？增大数据量是否会更好？

问：层次聚类原理

问：为什么选择孤立森林？介绍一下iforest？

优点：基于集成异常检测的思路，鲁棒性强；不涉及距离和密度计算，计算速度很快；每棵树独立生成可并行或分布式；

iforest的算法流程：

（1）底层是极限随机树，随机选择一个特征，随机选择部分样本（bagging），每次分裂随机选择一个分裂节点，最大深度是 log2（bagging的样本数量）

（2）整合所有极限随机树的结果，使用score function打分：

h(x) 为 样本x 在每棵树的高度（其实就是x在这棵树上分裂了几次），对样本x在所有树上的分裂次数进行平均得到分子项目，c(Ψ) 为给定样本数 Ψ 时路径长度的平均值，用来对样本 x 的路径长度 h(x) 进行标准化处理。

（3）score function的计算结果在0~1之间，

如果异常得分接近 1，那么一定是异常点；

如果异常得分远小于 0.5，那么一定不是异常点；

如果异常得分所有点的得分都在 0.5 左右，那么样本中很可能不存在异常点。

详细的可见：

isolation forest：https://zhuanlan.zhihu.com/p/181378482

isolation forest的score function公式到底是个啥？：https://zhuanlan.zhihu.com/p/181650438

追问：为什么高度为log2（bagging的样本数量）？为什么每次随机仅选择一小部分的样本（默认是min(bagging的样本数量，256)）？

直观上来看，m个特征，我们用m个极限随机树分别进行完全分裂，分裂到叶子节点的样本特征值完全相同，得到n个样本在m个极限随机树上的分裂次数，即得到n个样本在m个特征上的分裂次数，然后取平均就可以满足我们的预测目标了。本质上通过分裂次数代替聚类或密度的计算，分裂越少，则样本在这个特征上的异常程度越高，然后综合考虑样本在多个特征上的异常程度；

但是这么做的问题有：

1.计算复杂度太高了，树的完全分裂的时间复杂度为O(n)，上述做法的总的时间复杂度为O(mn);

2.本质上做的是基于集成学习的无监督学习，鲁棒性强，但是单纯用1个极限随机树分裂1个特征，随机因素影响太大，重新训练的结果差异可能会很大。解决的方法是每个特征用多个极限随机树来拟合，则计算复杂度进一步扩大为O(mnk)，k为树的数量；

3.无监督的核心缺陷，无法自动特征选择，所有特征的重要性一视同仁，则如果存在大量无用特征或者噪声特征，会严重影响计算结果；

iforest针对上述问题做了改进：

1.针对问题1，树的最大深度限制为log2（bagging的样本数量），之所以对树的高度做限制，是因为我们只关心路径长度较短的点，它们更可能是异常点，而并不关心那些路径很长的正常点。之所以使用log2的底数，是为了和score function的公式对应起来，为了计算score fuction上的便利性：

2-log2(2)=1/2,2log2(2)=2（指数和log计算公式）

总结一下， log2（bagging的样本数量）和服务于score function的设计的，计算上提供了便利性，；

2.仍旧是针对问题1，树每次使用的样本默认为 min(采样的样本数，256)，这么做主要避免了太大数量的样本上分裂次数过多计算复杂度高的问题，然后通过集成提高整个模型的鲁棒性。（精度和效率之间的一种折衷，根据论文和实际的应用结果，效果还ok）；

3.针对问题2，仍旧是精度和效率上的折衷，k个极限随机树通过采样，最终一共使用k个特征，每一轮随机选择一个特征生成一棵树；

4.针对问题1和2的不精确分裂的问题（实质上也没有办法做精确分裂），tree分裂上的不精确在实践中可以被认为提高了算法的鲁棒性，类似于lgb直方图；

5.针对问题3，特征的随机采样某些情况下缓解了无效特征的问题（大部分特征有效少部分特征无效的情况），但是本质上没有解决（大部分特征无效，少部分特征有效的情况），最终的特征工程还是要基于业务经验来进行；

追问：iforest的score function，为什么这么设计？

一步一步拆解来看：

1.指数函数形式的设计

我们希望iforest输出的结果能够在一个有限的范围内，例如像auc的取值范围为0.5~1一般，有界的评估指标便于比较（高度必然为正数，因此分子部分可以保证为负数，2**-x必然是大于0小于1的）；

2.分子的设计：

h(x)部分，并不是简单的直接计算样本在tree上的分裂次数，观察上述公式，其中e表示的才是样本在tree上的分裂次数，后面额外多了一项c(T.size)的修正项，T.size表示的样本所在叶子节点中所有样本的数量。

c(n)表示样本数量为n的情况下，生成随机二叉树的期望高度：

3.分母部分的设计：

分母部分使用的仍旧是上述的C(n)的公式，只不过分母部分的n指的是每一棵极限随机树使用的全部样本数量，即bagging得到的样本数量，默认是256个样本。这里的分母也是作为修正项存在的。

追问：为什么这里要引入分子和分母部分的修正项？

1.分子部分的修正项：

主要目的在于将样本落在的叶子节点中的样本数量大小这一因素考虑进来，假设某个样本A落入了叶子节点1，叶子节点1中有5个样本；某个样本B落入了叶子节点2，叶子节点2中有5000个样本，并且假设A和B的树的深度e都是3，则如果我们不引入修正项c(T.size)，计算结果是完全相同的。但实际上很明显，A的异常程度是要高于B的，因为B所在的叶子节点的样本数量很大，其实是可以继续分裂很多次，然而考虑到性能的问题，我们对树的高度做了限制，因此会引发这样的误差。

修正项的引入可以很好的解决这个问题 ，C(n)代表了给定n个叶子节点，所能生成的随机二叉树的平均高度，显然，叶子节点数量越多，则平均高度越大，则score function的计算结果越小，从而巧妙地缓解了上述存在的问题；

2.分母部分的修正项：

主要目的在于将每个tree所训练的bagging的样本数大小这一因素考虑进来，假设bagging的样本大小为64和256，则根据iforest的设计，max_depth分别为5和8，显然，bagging的样本数量越大则树可以生成的树的深度大概率越深，因此在分母部分引入给定bagging样本数量下，所能生成的随机二叉树的平均高度，显然，bagging样本数越多，平均高度越大，则score function计算的结果越大。

问：KNN算法是否存在损失函数？

无，knn是一种懒惰学习（lazy learning）的算法，对应的有eager learning：

lazy learning：

1. 只存储数据集而不从中学习，不需要模型训练

2. 收到测试数据后开始根据存储数据集对数据进行分类或回归；

eager learning：

1.从收集到的数据中学习，需要模型训练；

2.受到测试数据后直接完成分类或回归

不均衡学习:

问：数据不均衡如何解决，抽样得到的分类准确率如何转换为原准确率？

将采样后的预测的类别按照采样比例进行相应的增大或减少，例如对类别A下采样了50%，则预测结果中类别A的预测数量为m，令m=m/0.5=2m，然后计算分类准确率；

这种处理方式是不准确的，合理的方式应该是直接对原始数据进行评估指标的计算；

问：解决难样本问题的方法（hard sample problem），ohem与focal loss的相同点和不同点

问：如果把不平衡的训练集（正负样本1：3）通过降采样平衡后，那么对于平衡后的AUC值和预测概率值有怎样的变化？

roc曲线对类别数量的变化不敏感，因此auc的计算结果整体不会发生明显变化；

通过下采样平衡后，变相增大了正样本数量，分类决策边界远离正样本，预测概率整体变大；

问：class_weight的思想是什么？

class_weight对应的简单加权法是代价敏感学习最简单的一种方法，思想就是小类样本加权，使其在loss中比重变大；

问：不均衡学习原理？

目前主流的不均衡学习主要是关于分类问题的不均衡。所谓不均衡分类，指的是样本不同类别的数量差异越来越大的情况下，模型越来越偏向于预测大类样本的现象，因此，模型分类性能越来越差。

单纯从样本不均衡的角度出发（不考虑分布变化，小样本学习，分类问题的困难程度等其它问题），不均衡的类别对模型造成影响的原因：

1.目标函数优化的方法，使用梯度下降法优化目标函数的模型对于不均衡问题更敏感；而tree模型纯粹基于贪心策略进行分裂的方法则对此并不敏感；

2.目标函数的使用，hinge loss和交叉熵对于不均衡的敏感度不同；

不均衡是一个现象，是分类模型效果差的潜在原因之一；

问：了解哪些不均衡学习的处理方法？讲讲smote算法的原理？为什么平常很少使用smote这类基于样本生成的方法？

问：过采样（上采样）和生成样本的区别？

上采样不一定是生成样本，例如简单的repeat式的上采样，通过repeat不涉及样本生成的过程，但生成样本一定是一种上采样；

模型的loss function，metrics和optimizers

无监督metrics：

问：如何评价聚类结果的好坏（知道哪些聚类的评估指标）？轮廓系数有没有用过

sse很简单

轮廓系数：

轮廓系数是为每个样本定义的，由两个分数组成：

• a：样本与同一cluster中所有其他点之间的平均距离。

• b：样本与_下一个最近cluster_中的所有其他点之间的平均距离。

对于单个样本而言，轮廓系数的计算公式如下：

对于模型评估而言，取所有样本的轮廓系数的均值作为模型聚类效果的评估指标；

其它评估方式可见：

https://scikit-learn.org/stable/modules/clustering.html#clustering-performance-evaluation

有监督metrics：

问：准确率的局限性是什么？

1.不同分类阈值下准确率会发生变化，评估起来比较麻烦；

2.对样本不均衡问题特别敏感，例如当负样本占99%时，分类器把所有样本都预测为负样本也可以获得99%的准确率；