最全常见算法工程师面试题目整理(二)

接着上回写的《最全常见算法工程师面试题目整理(一)》,继续填接下来的坑。

11boost算法的思路是什么样的？讲一下你对adaboost 和 gbdt的了解？

答案：

boost的核心思想不同于bagging，它在基于样本预测结果对照与真实值得差距，进行修正，再预测再修正，逐步靠近正确值。

我对adaboost和gbdt了解的也不算很全面：大概的梳理如下：

不足： 1、adaboost存在异常点敏感的问题； 2、gbdt一定程度上优化了adaboost异常点敏感的问题，但是存在难以并行的缺点；

3、两者的目标都是优化bias，必然导致训练出来的数据var的不稳定。

亮点： 1.发现非线性的特征关系，网格化的切分feature 2.拟合的效果相较于其他分类器更加精准，且训练参数较少

Adaboost:

adaboost初始数据权重都是1/M，然后通过训练每一个弱分类器Classifier使得在每一次y_pred误差最小，得到每一个弱Classifier的权重方法对：（αi，yi）然后提高错分了的数据的权重，降低正确分类的数据权重，循环训练，最后组合最后若干次的训练弱Classifier对，得到强分类器。

其中，αi由误差决定：

该弱分类器分类错误率em越大，则该若分类器作用越小。

剖析了原理之后，我们发现，这样做对异常点非常敏感，异常点非常容易错分，会影响后续若干个弱分类器。

gbdt:

gbdt的核心在于下面这个公式：

L（y，y_pred）：预测值与实际值间的误差 F(x):前若干个弱分类器的组合。

关键的在于当前预测结果=对前若干个弱分类器+当前弱分类器修正，所以对前若干个分类器组合求偏导的方向进行梯度处理，保证L（x）出来的值最小。

这边结果在于你选取什么样的误差函数：

Loss即为损失函数，Derivative即为导数。

除此之外，在每一步弱分类器构建的同时，它还考虑了正则化： Ω=入T+μ*linalg.norm(f(xi))

T为子叶节点数目，同时也对预测结果得分的值进行了l1或者l2压缩，避免过拟合。

我个人更喜欢用xgboost，在求解速度上，对异常值处理上面都要比gbdt要快，而且基于R、python版本都有package。

12听说你做过用户关系，你用的什么方法？社群算法有了解，讲讲什么叫做Modularity Q？

答案一、我用的是Jaccard相关。

比如，用户1一共收过150个红包，发了100个红包，其中20个被用户2抢过。 用户2一共收过100个红包，发了50个红包，其中30个被用户1抢过。

similarity(user1=>user2)=(30+20)/(150+100) similarity(user2=>user1)=(30+20)/(50+100) similarity(user2=>user1)=(30+20+30+20)/(150+100+50+100)

答案2、社区算法主要是用来衡量用户关系网中，不同用户、链接、信息之间的相似程度。

本来这边我准备讲pagerank的，结果被打断了，说需要讲内部结构相关的，其实我觉得PageRank这边来描述更加合适。不过，无所谓，我这边谈的是一个很基本的叫做：Kernighan-Lin算法（后面简称了KL算法）

KL算法中，先随机切分原数据集群，得到不同社区集，随机交换不同社区集内的不同点，观察优化值得变化程度是否为正向，循环即可。

共需执行次数：循环次数x集群A内点的个数x集群B内点的个数

感觉这边答的不行，被嫌弃了，有知道的大神可以自行去研究一下相关的社区算法，我这边只了解PageRank和LK。

答案3、Q-modularity：

这个简单，E：关系点连接线之间的个数，I：关系点连接线两端都在社群内的数量，O：关系点连接线有至少一端在社群外的连接线的数量。

这个指标是用来衡量社群划分的稳定性的，讲真我也没用过，只是在周志华的算法的书上看过。

13如果让你设计一套推荐算法，请说出你的思路？

讲真，这个点，我起码说了有25分种，对面的面试管也很耐心的听完了，并且还给予了很多点的反馈，个人觉得非常受到尊重，我下面细节梳理一下。

首先，我个人非常赞同阿里现在的推荐算法这边的设计思路： 推荐＝人＋场景＋物 其中， 人＝新用户＋老用户＋综合特征＋... 场景＝属性偏好＋周期属性＋黏度偏好＋... 物＝相关性＋物品价值＋特殊属性＋... 接下来，我简单的剖析三个最常见也最重要的问题：

冷启动

很多人有一种错觉，只要业务上线时间长了就不存在所谓的冷启动问题，实则不是，新用户是持续进入的、流失用户也是在增长的、很多盲目用户（没有有价值行为）等等都可以归纳为冷启动问题，这类问题的核心在于你可用的数据很少，甚至没有，我这边采取的是热门推荐的方法。

然而在热门推荐的算法中，我这边推荐一些方法：

威尔逊区间法：综合考虑总的行为用户中，支持率与支持总数的平衡 hacker new排序：综合考虑时间对支持率的影响 pagerank排序：考虑用户流向下的页面权重排序 梯度效率排序：考虑商品增速下的支持率的影响 ...

方法很多，但是核心的一点是热门推荐是冷启动及实时推荐必不可少的一环，优化好实时推荐的算法是占到一个好的推荐算法的30%以上的权重的，切忌0推荐。

不同种算法产生的推荐内容互不冲突

这个是苏宁易购的首页推荐位，1、2、3分别是三个推荐位，我们在做算法的时候常常会特别注意，不能用太多相关性比较高的变量，会产生共线性，但在推荐内容上，“58同城”的算法推荐团队之前有一份研究证明，同一个页面上由不同算法产出的推荐结果不存在相互影响。

所以，我非常赞同不同的算法产出不同的结果同时展示，因为我们不知道对目标用户是概率模型、距离模型、线性模型等不同模型中哪个产出的结果更加合适。

关于常用的推荐算法，我之前梳理过，这边也不再多加重复，需要仔细研究的可看我上面的图，或者看我之前的文章：《深度学习下的电商商品推荐》（http://www.jianshu.com/p/00a28141521f）、《偏RSVD及扩展的矩阵分解方法》（http://www.jianshu.com/p/a3e633e396a0）等等。

你的对象是用户，不是冰冷的数字

我在苏宁呆的时间不长，但是我有个感觉，身边算法工程师很容易把自己陷入数字陷阱，近乎疯狂去用各种算法去拟合当前的用户数据，以求得得到高的ctr或者转化率。

不同的推荐场景需要使用不同的用户行为。举例假设存在经典的关系：买了炸鸡和番茄酱的用户，接下来的一周有35%的用户会来买汽水。所以，很多工程师会选择只要买了炸鸡和番茄酱的用户，就弹窗汽水，因为就35%的百分比而言，是非常高的支持度了。其实只要有用户画像的支持就会发现，这35%的用户中，80%的都是年龄在青少年，如果在推送之前做一个简单的逻辑判断只针对所有青少年进行推送汽水的话，35%轻而易举的上升到了70%，这是任何算都无法比拟的。

最上方的橙黄色的横条中，橙色代表原始的目标用户，黄色代表非目标用户，假设我们知道黑色方框所框选的用户的转化率达到最小置信度的时候，我们可以通过特征映射、非线性分解、用户画像刻画等不同方法得到左右完全不同的新的用户分布，在同样的用户框选占比下，效果也是完全不同的。

真实推荐中，比如针对用户冬装推荐，我不仅仅以用户近期的搜索、浏览、购买商品等行为判断用户的偏好，我也根据他夏天的购买风格款式、他的年龄、生理性别、浏览性别等综合判断他可能会买什么。推荐算法才不会是冷漠的。

至于想要了解具体实现算法及创新的一些想法可以看上方的脑图，但是我觉得那并不是最重要。

14什么是P、NP、NP-Hard、NP-Complete问题？

P：很快可以得出解的问题 NP：一定有解，但可很快速验证答案的问题

后面两个我没答出来，网上搜了下，分享下： NP-Hard：比所有的NP问题都难的问题 NP-Complete：满足两点：

1、是NP-Hard的问题

2、是NP问题

个人不喜欢这种问题。

15常见的防止过拟合的方法是什么？为什么l1、l2正则会防止过拟合？

当被问了第一个问题的时候，我愣了下，因为我觉得挺简单的，为什么要问这个，我感觉接下来有坑。

我回答的是：

先甩出了下面的图解释了一波欠拟合、正常、过拟合：

然后举了几个例子：

• 针对error递归的问题，l1，l2正则化
• 扩充数据量，使得数据更加符合真实分布
• bagging等算法技巧

当问到为什么的时候，我觉得自己回答的不好，有点蛋疼：

我说的是，l1以：

l2以：

l1中函数与约束点偏向相切于四个端点，端点处压缩了某个特征＝0；l2中函数与约束点偏向相切于圆，会造成某些特征值压缩的接近于0；

根据奥卡姆剃刀原理，当两个假说具有完全相同的解释力和预测力时，我们以那个较为简单的假说作为讨论依据，而通常过拟合的模型的特征维度过高过多，所以一定程度可以缓解过拟合。

面试管以一种奇怪的眼神看着我，然后表示他其实想让我通过先验概率解释，不过我这样说仿佛也有道理。我回来之后就研究了一下，比如l2，大致如下：

首先，我们确定两点：

l2，其实就给了系数w一个期望是0，协方差矩阵是 1/alpha的先验分布。l1对应的是Laplace先验。

我们相当于是给模型参数w设置一个协方差为1/alpha 的零均值高斯分布先验。

根据贝叶斯定律：

这一步我没看懂，我计算了半天也没由最大似然估计算出下面这个式子，有会的朋友可以私信我一下。

有了上面的式子就很简单了，alpha在0-正无穷之间，如果a接近0的话，左侧及为正常的MSE也就是没有做任何的惩罚。如果alpha越大的话，说明预测值越接近真实值的同时，协方差也控制的很小，模型越平稳，Var也越小，所以整体的模型更加有效，避免了过拟合导致训练数据拟合效果很差的问题。

到这里，我觉得常见的算法题目都讲完了，很多简单的知识点我没有提，上面这些算是比较经典的，我没答出来的，希望对大家有所帮助，最后谢谢大家的阅读。