牛客笔试题之顺丰机器学习真题

昨天做了一套顺丰人工智能和机器学习的真题，下面是对其中一些知识点的总结。

Java中的String

解析：

链表

链表的特性，使其在某些操作上比数组更加高效。

1. 增删不必挪动元素。当进行插入和删除操作时，链表操作的时间复杂度仅为O(1)。
2. 无需实现估计空间。链表在内存中不是连续存储的，所以可以充分利用内存中碎片空间。

UDP与TCP

死锁

产生必要条件：

1. 互斥
2. 请求与保持
3. 循环等待
4. 非剥夺

OSI七层模型

OSI（Open System Interconnect），即开放式系统互联。 一般都叫OSI参考模型，是ISO（国际标准化组织）组织在1985年研究的网络互连模型。它定义了网络互连的七层框架：
物理层、数据链路层、网络层、传输层、会话层、表示层、应用层

TCP/IP五层协议和OSI的七层协议对应关系如下，在每一层都工作着不同的设备：

在每一层实现的协议也各不同，即每一层的服务也不同：

数据库索引

1. 通过创建唯一性索引，可以保证数据库表中每一行数据的唯一性
2. 当用户查询索引字段时，索引可以快速地执行检索操作，借助索引，在执行查询的时候不需要扫描整个表就可以快速地找到所需要的数据。
3. 创建索引和维护索引要耗费时间、空间,当对表中的数据进行增加、删除和修改的时候,会降低数据的维护速度

Numpy

解析：

import numpy as np
''' numpy.repeat(a, repeats, axis=None) 将a重复b次 >>> x = np.array([[1,2],[3,4]]) >>> np.repeat(x, 2) array([1, 1, 2, 2, 3, 3, 4, 4]) >>> np.repeat(x, 3, axis=1) array([[1, 1, 1, 2, 2, 2], [3, 3, 3, 4, 4, 4]]) >>> np.repeat(x, [1, 2], axis=0) array([[1, 2], [3, 4], [3, 4]]) '''
a = np.repeat(np.arange(5).reshape([1,-1]),10,axis = 0)+10.0
b = np.random.randint(5, size= a.shape) # 生成[0,5)随机矩阵，大小和矩阵a相同
c = np.argmin(a*b, axis=1) #矩阵a和b乘积，返回每行最小值位置
b = np.zeros(a.shape) #与矩阵a相同大小的全零矩阵
print("b变之前：",str(b))
print("c的值：",str(c))
b[np.arange(b.shape[0]), c] = 1 #将b中每一行的c位置处赋值为1
print("b变之后：",str(b))
print(b.shape)

输出结果：

b变之前： [[0. 0. 0. 0. 0.]
 [0. 0. 0. 0. 0.]
 [0. 0. 0. 0. 0.]
 [0. 0. 0. 0. 0.]
 [0. 0. 0. 0. 0.]
 [0. 0. 0. 0. 0.]
 [0. 0. 0. 0. 0.]
 [0. 0. 0. 0. 0.]
 [0. 0. 0. 0. 0.]
 [0. 0. 0. 0. 0.]]
c的值： [0 3 4 3 1 3 4 2 2 0]
b变之后： [[1. 0. 0. 0. 0.]
 [0. 0. 0. 1. 0.]
 [0. 0. 0. 0. 1.]
 [0. 0. 0. 1. 0.]
 [0. 1. 0. 0. 0.]
 [0. 0. 0. 1. 0.]
 [0. 0. 0. 0. 1.]
 [0. 0. 1. 0. 0.]
 [0. 0. 1. 0. 0.]
 [1. 0. 0. 0. 0.]]
(10, 5)

RF GBDT XgBoost

RF、GBDT、XgBoost 三者都是集成学习中的方法，其中RF属于Bagging方法，GBDT和XgBoost属于Boosting方法。过段时间会专门写一篇有关Bagging和Boosting介绍的博文。

1. RF（Random Forest）

随机森林主要运用到的方法是bagging，采用Bootstrap的随机有放回的抽样，抽样出N份数据集，训练出N个决策树。然后根据N个决策树输出的结果决定最终结果（离散型的输出：取最多的类别，连续型的输出：取平均数）。

优势：

• 容易理解和解释
• 不需要太多的数据预处理工作
• 隐含地创造了多个联合特征，并能够解决非线性问题
• 随机森林模型不容易过拟合
• 自带out-of-bag (oob)错误评估功能
• 并行化容易实现

劣势：

• 不适合小样本，只适合大样本
• 精度较低
• 适合决策边界是矩形的，不适合对角线型的

2. GBDT

通过采用加法模型（即基函数的线性组合），以及不断减小训练过程产生的残差来达到将数据分类或者回归的算法。通过多轮迭代,每轮迭代产生一个弱分类器，每个分类器在上一轮分类器的残差基础上进行训练。对弱分类器的要求一般是足够简单，并且是低方差和高偏差的。一般选择cart tree且树的深度不会很深。

优势：

• 精度高
• 能处理非线性数据
• 能处理多特征类型
• 适合低维稠密数据
• 模型可解释性好
• 不需要做特征的归一化，可以自动选择特征
• 能适应多种损失函数

劣势：

• 不太适合并发执行
• 计算复杂度高
• 不适用高维稀疏特征

3. XgBoost

简单来说XgBoost是GBDT的一种高效实现，主要具有以下几个优势：

• 显式的把树模型复杂度作为正则项加到优化目标中。
• 实现了分裂点寻找近似算法。
• 可以并行执行

RF和GBDT的比较:

相同点：

• 都是由多棵树组成
• 最终的结果都是由多棵树一起决定

不同点：

• 组成RF的树可以是分类树，也可以是回归树；而GBDT只由回归树组成
• 组成RF的树可以并行生成；而GBDT只能是串行生成
• 对于最终的输出结果而言，RF采用多数投票等；而GBDT则是将所有结果累加起来，或者加权累加起来
• RF对异常值不敏感，GBDT对异常值非常敏感
• RF对训练集一视同仁，GBDT是基于权值的弱分类器的集成
• RF是通过减少模型方差(variance)提高性能，GBDT是通过减少模型偏差(bias)提高性能

Boosting和Bagging的差别

过拟合的模型，通常variance比较大，这时应该用bagging对其进行修正。
欠拟合的模型，通常bias比较大，这时应该可以用boosting进行修正。使用boosting时， 每一个模型可以简单一些。

1. bagging中的模型是强模型，偏差低，方差高。目标是降低方差(variance)。在bagging中，每个模型的bias和variance近似相同，但是互相相关性不太高，因此一般不能降低bias，而一定程度上能降低variance。典型的bagging是random forest (RF)。

2. boosting中每个模型是弱模型，偏差高，方差低。目标是通过平均降低偏差(bias)。boosting的基本思想就是用贪心法最小化损失函数，显然能降低偏差，但是通常模型的相关性很强，因此不能显著降低variance。典型的Boosting是Adaboost，另外一个常用的并行Boosting算法是GBDT（gradient boosting decision tree）。这一类算法通常不容易出现过拟合。