每日算法题：Day 20

Day 20, 机器学习知识点走起~

1

编程题

【剑指Offer】数组中只出现一次的数

一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

思路： 这一道题看似很简单，我们使用一个hashmap用来统计每个数出现的次数或者使用hashset，遍历的同时查找hashset，如果存在则删除，如果不存在就将数字存入hashset，最后hashset中只存在出现一次的两个数，但如果题目不让你是用辅助空间，即空间复杂度为O(1)，怎么办？

有人就想到了异或算法，异或是指二进制中，如果两位相同则为零，不同则为1。假如有一组数据[6, 5, 6, 7, 7]，我们设立初始值x=0，对这个数组进行累积的异或运算，最后等于5. 这就是一个异或运算的性质，不管两个相同的数字在那个位置，经过异或可以各自抵消！

因此题中的数组经过这个运算后最后得到的是两个数（只出现一次的）的异或值，那么怎么分开呢？ 其实思路也很简单，如果两个数不同的话，那么其二进制必定有一位数不同导致其异或位为1，加入是最后一位不同，那么我们可以从头遍历并判断每个数&1，那么就会将所有的数分成两个数组，而这两个单独的数也一定会被分开，这样就成了我们第一段我们说的只包含一个孤独的数的情况，然后遍历进行异或运算就可以得到这两个数组中的孤独的数！哈哈哈，思路很棒！

class Solution {
public:
    void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {
        int x = ;
        int len = data.size();
        for(int i=; i<len; ++i){
            x = x^data[i];
        }
        int t = x^(x-1) & x; //找1所在的最低位，这个比较简洁易懂
        *num1 = ;
        *num2 = ;
        for(int i=; i<len; ++i){
            if(data[i] & t){
                *num1 ^= data[i];
            }else{
                *num2 ^= data[i];
            }
        }
    }
};

【剑指Offer】和为S的连续正序列

小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good Luck!

思路： 我们可以使用双指针来进行表示一个连续正数序列的边界，然后根据等差数列的公式：sum = (begin+end)*N/2 ,当我们求得一个正数序列的和sum后，如果sum大于目标数值，我们让begin向右移动，如果小于目标数值，则让end向右移动，最终的最终，两个指针都会指到同一位置,即目标数值，从而退出循环！当等于目标时，我们将[begin, end]中的所有数存入数组中即可！

class Solution {
public:
    vector<vector<int> > FindContinuousSequence(int sum) {
        vector<vector<int>> res;
        vector<int> tmp;
        int pLow = , pHigh = ;
        while(pHigh > pLow){
            int sum_list = (pHigh + pLow)*(pHigh-pLow+)/;
            if(sum_list == sum){
                for(int i = pLow;i <= pHigh;i++){
                    tmp.push_back(i);
                }
                res.push_back(tmp);
                tmp.clear();   // 将tmp清空
                pLow++;
            }
            else if(sum_list < sum){
                pHigh++;
            }else{
                pLow++;
            }
        }
        return res;
    }
};

2

概念题

【机器学习】常见的ensemble方式都有什么？

Bagging: 使用训练集的不同子集来训练每一个base model，最后进行投票，投票时每个base model的权重是相同的！对于分类问题，使用投票法，而对于回归问题，直接计算全部模型的均值即可！比如随机森林算法

Boosting:迭代的训练base model, 每次根据上一次迭代预测错误的情况修改训练集中样本在分类器中的权重，提高错误分类的样本的权重！而在测试时，增加分类误差小的弱分类器的权重，使得其在整个模型表决时起到更大的作用！如AdaBoost算法

Stacking:简单来说，stacking算法就是将第一层模型的输出包括训练集和测试集，被第二层模型接受，并重新进行训练，主要两层的模型都可以是多个模型或者使用KFold训练成不同参数的单类模型！

Blending:用不相交的数据训练不同的 Base Model，将它们的输出取（加权）平均。实现简单，但对训练数据利用少了,可能会导致模型训练不充分。

【机器学习】Boosting算法和Stacking算法的区别

• 样本选择上： Bagging：训练集是在原始集中有放回选取的，从原始集中选出的各轮训练集之间是独立的。 Boosting：每一轮的训练集不变，只是训练集中每个样例在分类器中的权重发生变化。而权值是根据上一轮的分类结果进行调整。
• 样例权重： Bagging：使用均匀取样，每个样例的权重相等 Boosting：根据错误率不断调整样例的权值，错误率越大则权重越大。
• 预测函数： Bagging：所有预测函数的权重相等。 Boosting：每个弱分类器都有相应的权重，对于分类误差小的分类器会有更大的权重。
• 并行计算： Bagging：各个预测函数可以并行生成 Boosting：各个预测函数只能顺序生成，因为后一个模型参数需要前一轮模型的结果 源自：CSDN: 模型融合

【深度学习】stacking算法流程

1. 把训练集分为不交叉的五份。我们标记为 train1 到 train5。
2. 从 train1 开始作为预测集，使用 train2 到 train5 建模，然后预测 train1，并保留结果；然后，以 train2 作为预测集，使用 train1，train3 到 train5 建模，预测 train2，并保留结果；如此进行下去，直到把 train1 到 train5 各预测一遍；
3. 【test数据转换】在上述建立的五个模型过程中，每个模型分别对 test 数据集进行预测，并最终保留这五列结果，然后对这五列取平均，作为第一个基模型对 test 数据的一个 stacking 转换。
4. 【train数据转换】把预测的结果按照 train1 到 trian5 的位置对应填补上，得到对 train 整个数据集在第一个基模型的一个 stacking 转换。
5. 选择第二个基模型，重复以上 2-5 操作，再次得到 train 整个数据集在第二个基模型的一个 stacking 转换。
6. 以此类推。有几个基模型，就会对整个train 数据集生成几列新的特征表达。同样，也会对test 有几列新的特征表达。一般使用LR 作为第二层的模型进行建模预测！