作业帮算法卷笔试

发表于 更新于 分类于

博主问题笔记

不包含博主经历所有题目只记录典型问题（估计也差不多全部了，因为博主菜…..）

问题1：交叉熵公式

解答：交叉熵公式如下：

这里公式定义，x、y都是表示概率分布。其中x是正确的概率分布，而y是我们预测出来的概率分布，这个公式算出来的结果，表示y与正确答案x之间的错误程度（即：y错得有多离谱），结果值越小，表示y越准确，与x越接近。

问题2：随机森林与GDBT的异同

解答：

理论知识

随机森林

随机森林是一个用随机方式建立的，包括多个决策树的集成分类器。其输出的类别由各个树投票而定（如果是回归树则取平均）。假设样本总数为n，每个样本的特征数为a。则随机森林生成过程如下：

  1. 从原始样本中采用有放回抽样的方法选取n个样本;
  2. 对n个样本选取a个特征中的随机k个，用建立决策树的方法获得最佳分割点；
  3. 重复m次，获取m个决策树；
  4. 对输入样例进行预测时，每个子树都产生一个结果，采用多数投票机制输出。

随机森林的随机性主要体现在两个方面：

  1. 数据集的随机选取：从原始的数据集中采取有放回的抽样(bagging)，构造子数据集，子数据集的数据量是和原始数据集相同的。不同子数据集的元素可以重复，同一个子数据集中的元素也可以重复。
  2. 待选特征的随机选取：与数据集的随机选取类似，随机森林中的子树的每一个分裂过程并未用到所有的待选特征，而是从所有的待选特征中随机选取一定的特征，之后再在随机选取的特征中选择最优的特征。

随机森林的优点：

  • 实现简单，训练速度快，泛化能力强，可以并行实现，因为训练时树与树之间是相互独立的；
  • 相比单一决策树，能学习到特征之间的相互影响，且不容易过拟合；
  • 能够处理高维数据（即特征很多），并且不用做特征选择，因为特征子集是随机选取的；
  • 对于不平衡的数据集，可以平衡误差；
  • 相比SVM，不是很怕特征缺失，因为待选特征也是随机选取；
  • 训练完成后可以给出哪些特征比较重要。

随机森林的缺点：

  • 在噪声过大的分类和回归问题还是容易过拟合；
  • 相比于单一决策树，它的随机性让我们难以对模型进行解释。

GBDT

GBDT （Gradient Boost Decision Tree）是以决策树为学习器迭代算法，注意GDBT里的决策树都是回归树而不是分类树。Boost是“提升”的意思，一般Boosting算法都是一个迭代的过程，每一次新的训练都是为了改进上一次的结果。

GBDT的核心就在于：每一棵树学的是之前所有树结果和的残差，这个残差就是一个加预测值后能得真实值的累加量。比如A的真实年龄是18岁，但第一棵树的预测年龄是12岁，差了6岁，即残差为6岁。那么在第二棵树里我们把A的年龄设为6岁去学习，如果第二棵树真的能把A分到6岁的叶子节点，那累加两棵树的结论就是A的真实年龄；如果第二棵树的结论是5岁，则A仍然存在1岁的残差，第三棵树里A的年龄就变成1岁，继续学习。
GBDT优点是适用面广，离散或连续的数据都可以处理，几乎可用于所有回归问题（线性/非线性），亦可用于二分类问题（设定阈值，大于阈值为正例，反之为负例）。缺点是由于弱分类器的串行依赖，导致难以并行训练数据。

随机森林和GBDT的区别

  1. 随机森林采用的bagging思想，而GBDT采用的boosting思想。这两种方法都是Bootstrap思想的应用，Bootstrap是一种有放回的抽样方法思想。虽然都是有放回的抽样，但二者的区别在于：Bagging采用有放回均匀取样，而boosting根据错误率来取样（Boosting 初始化时对每一个训练样例赋相等的权重$\frac{1}{n}$，然后用该算法对训练集训练t轮，每次训练后，对训练失败的样本赋以较大的权重），因此Boosting的分类京都要优于Bagging。Bagging的训练集的选择是随机的，各训练集之间相互独立，弱分类器可并行，而boosting的训练集的选择与前一轮的学习结果有关，是串行的。
  2. 组成随机森林的树可以是分类树，也可以是回归树；而GBDT只能由回归树组成。
  3. 组成随机森林的树可以并行生成；而GBDT只能是串行生成。
  4. 对于最终的输出结果而言，随机森林采用多数投票等；而GBDT则是将所有结果累加起来，或者加权累加起来。
  5. 随机森林对异常值不敏感；GDBT对异常值非常敏感。
  6. 随机森林对训练集一视同仁；GBDT是基于权值的弱分类器的集成。
  7. 随机森林是通过减少模型方差提高性能，GBDT是通过减少模型偏差提高性能。

参考资料：机器学习：随机森林和GDBT的区别

问题3：对后验概率估计的思考

解答：对于很多条件概率问题，可以等价于$P(B) =\frac{P(AB)}{P(A)}$求后验概率问题。

问题4：针对归一化问题的数据线性排序思考

解答：基数排序是一种针对该问题很好的解决方式，往往因为其平均复杂度为$O(d(r+n))$被忽略其线性。

问题5：带有容错的最长公共子串如何实现（动态规划问题）

解答： 暂时还没想到。

问题6：剑指Offer原题，螺旋遍历

解答：主要找规律找出循环条件：$columns \gt startX * 2$并且$rows \gt startY*2$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
# -*- coding:utf-8 -*-
class Solution:
    # matrix类型为二维列表，需要返回列表
    def printMatrix(self, matrix):
        # write code here
        if matrix is None:
            return
        res = []
        start = 0
        column = len(matrix[0])
        row = len(matrix)
        while column > 2*start and row > start*2:
            self.PrintMatrixIncicle(matrix,column,row,start,res)
            start += 1
        return res
    def PrintMatrixIncicle(self,matrix,column,row,start,res):
        endX = column-1-start
        endY = row-1-start
        i = start
        while i <= endX:
            number = matrix[start][i]
            self.printNumber(number,res)
            i += 1
        if start < endY:
            i = start+1
            while i <= endY:
                number= matrix[i][endX]
                self.printNumber(number,res)
                i += 1
        if start < endX and start < endY:
            i = endX-1
            while i >= start:
                number = matrix[endY][i]
                self.printNumber(number,res)
                i -= 1
        if  start < endX and start < endY-1:
            i = endY-1
            while i >= start+1:
                number = matrix[i][start]
                self.printNumber(number,res)
                i -= 1
    def printNumber(self,number,res):
        res.append(number)