精华内容
下载资源
问答
  • 2022-03-23 17:45:24

    并行算法的一般设计方法
    串行算法的直接并行化
    算法设计方法描述
    方法描述
    发掘和利用现有串行算法中的并行性,直接将串行算法改造为并行算法。
    评注
    由串行算法直接并行化的方法是并行算法设计的最常用方法之一
    不是所有的串行算法都可以直接并行化的
    一个好的串行算法并不能并行化为一个好的并行算法
    许多数值串行算法可以并行化为有效的数值并行算法
    例:快排序算法的并行化
    算法:PRAM-CRCW上的快排序二叉树构造算法

    输入:序列(A1,…,An)和n个处理器

    输出:供排序用的一颗二叉排序数

    从问题描述开始设计并行算法
    方法描述
    从问题本身描述出发,不考虑相应的串行算法,设计一个全新的并行算法。
    评注
    挖掘问题的固有特性与并行的关系
    设计全新的并行算法是一个挑战性和创造性的工作
    利用串的周期性的PRAM-CRCW算法是一个很好的范例

    借用已有的算法求解新问题
    方法描述
    找出求解问题和某个已解决问题之间的联系
    改造或利用已知算法应用到求解问题上
    评注
    这是一项创造性的工作
    使用矩阵乘法算法求解所有点对间最短路径是一个很好的范例
    利用矩阵乘法求所有点对间最短路径
    计算原理

    参考:
    https://www.cnblogs.com/zhangzefei/p/9973332.html
    https://wenku.baidu.com/view/3dbe9248640e52ea551810a6f524ccbff021ca05.html

    更多相关内容
  • 串行算法并行化处理的数学模型与算法描述
  • 点相对于多边形位置检测是计算机图形学中的一个底层而基本的问题,目前的算法较多,但这些算法要么复杂,要么不稳定,都或多或少存在一些问题。为改进算法,首先从分析直线...实验证明,串行算法是一个稳定的最优算法。
  • 点相对于多边形位置检测是计算机图形学中的一个底层而基本的问题,目前的算法较多,但这些算法要么复杂,要么不稳定,都或多或少存在一些问题。为改进算法,首先从分析直线的正负...实验证明,串行算法是一个稳定的最优算法。
  • 事件重叠下的频繁串行情节发现算法,卓鹏,肖波,在事件序列的数据挖掘中, 一个重要的步骤就是发现频繁情节。 一旦发现频繁情节就能导出描述该序列行为的情节规则。H. Mannila等人提��
  •   本次实验分别使用串行算法、Cache优化算法、SSE编程和分片策略算法实现了矩阵乘法运算,实验采用同一个样本,即矩阵大小为512个元素,元素值为由时间生成的随机数,每个算法对此样本运行十次,并记录每次运行...

    1 问题描述

      本次实验分别使用串行算法、Cache优化算法、SSE编程和分片策略算法实现了矩阵乘法运算,实验采用同一个样本,即矩阵大小为512个元素,元素值为由时间生成的随机数,每个算法对此样本运行十次,并记录每次运行时间和十次运算的平均运行时间。实验环境:计算机apple macbook pro2015、系统macOS High Sierra10.13.5、编辑器vscode&C/C++ Extension、gcc编译。

    2 算法设计与实现

      首先在矩阵样本设计方面,考虑大越大规模的数据越能体现不同算法在运行上的差距,因而将矩阵大小设置为512个元素,并且为了减少元素数据对实验的影响,采取了随机数赋值的方法。

     srand((unsigned)time(NULL));
     float a[maxN][maxN];
     float b[maxN][maxN];
     for(int i = 0; i < n; i++)
     {
       for(int j=0; j < n; j++){
         a[i][j] = rand();
         b[i][j] = rand();
       }
     }
    

    ​ 其次考虑每个算法的具体实现:

    2.1 串行算法

    ​ 由于矩阵乘法规则为乘积AB的第i个分量等于矩阵A的第i个行向量与列向量B的对应分量乘积之和,因而对矩阵A的每一行的元素,矩阵B的每一列的元素都要与之相乘并相加,所以需要先遍历矩阵A一行中的元素的同时遍历矩阵B一列中的元素,再遍历矩阵B中的每一列,再遍历矩阵A中的每一行,三层遍历嵌套,时间复杂度O(n) = n^3,用clock_t记录时间。

    ​ 具体代码如下:

    double mul(int n,float a[][maxN],float b[][maxN],float c[][maxN]){ //串行算法 O(n) = n^3
        double time;
        clock_t start,end;
        start = clock();
    
        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < n; j++)
            {
                c[i][j]= 0.0;
                for(int k = 0; k < n; k++){
                    c[i][j] += a[i][k] * b[k][j];
                }
            }
        }
    
        end = clock();
        time = (double)(end-start);
        cout<<"串行算法耗时: "<<(time/CLOCKS_PER_SEC)<<"s"<<endl;
        return time/CLOCKS_PER_SEC;
    }
    
    2.2 Cache优化

    ​ 由于寄存器从内存中取值时,需要从内存中寻址,上述串行算法b[k][j]需要先对矩阵B的行进行遍历,又因为在c++中,二维数组相邻的元素地址相近,因而先对行进行遍历造成了地址跳跃,需要更长的寻址时间。将矩阵B转置,就能够实现对连续的地址进行读写操作,节省大量寻址时间。算法时间复杂度O(n) = n^3。

    ​ 具体代码如下:

    double trans_mul(int n, float a[][maxN], float b[][maxN], float c[][maxN]){ // Cache优化 O(n) = n^3
        double time;
        clock_t start,end;
        start = clock();
    
        for (int i = 0; i < n; ++i) 
            for (int j = 0; j < i; ++j) 
                swap(b[i][j], b[j][i]); 
        for (int i = 0; i < n; ++i) {  
            for (int j = 0; j < n; ++j) { 
                c[i][j] = 0.0;
                for (int k = 0; k < n; ++k) { 
                    c[i][j] += a[i][k] * b[j][k];
                    }
                }
        } // transposition
        for (int i = 0; i < n; ++i) 
            for (int j = 0; j < i; ++j) 
                swap(b[i][j], b[j][i]);
    
        end = clock();
        time = (double)(end-start);
        cout<<"Cache优化耗时: "<<(time/CLOCKS_PER_SEC)<<"s"<<endl;
        return time/CLOCKS_PER_SEC;
    }
    
    2.3 SSE版本

    ​ 基于SIMD编程,将多个元素同时进行寄存器加载和存储器存值等操作能够提高并行效率。使用SSE指令能够实现该功能。时间复杂度为O(n) = (n^3)/4,同样对矩阵B进行转置。

    ​ 具体代码如下:

    double sse_mul(int n, float a[][maxN], float b[][maxN], float c[][maxN]){ //SSE版本 O(n) = (n^3)/4
        double time;
        clock_t start,end;
        start = clock();
    
        __m128 t1, t2, sum;  //__m128 == float
        for (int i = 0; i < n; ++i) 
            for (int j = 0; j < i; ++j) 
                swap(b[i][j], b[j][i]); 
        for (int i = 0; i < n; ++i){ 
            for (int j = 0; j < n; ++j){ 
                c[i][j] = 0.0;
                sum = _mm_setzero_ps();  //Initialize
                for (int k = n - 4; k >= 0; k -= 4){ // sum every 4 elements 
                    t1 = _mm_loadu_ps(a[i] + k); 
                    t2 = _mm_loadu_ps(b[j] + k); 
                    t1 = _mm_mul_ps(t1, t2);
                    sum = _mm_add_ps(sum, t1);
                }
                sum = _mm_hadd_ps(sum, sum); 
                sum = _mm_hadd_ps(sum, sum); 
                _mm_store_ss(c[i] + j, sum);
                for (int k = (n % 4) - 1; k >= 0; --k){ // handle the last n%4elements
                    c[i][j] += a[i][k] * b[j][k];
                }
            }
        } 
        for (int i = 0; i < n; ++i) 
            for (int j = 0; j < i; ++j) 
                swap(b[i][j], b[j][i]);
    
        end = clock();
        time = (double)(end-start);
        cout<<"SSE版本耗时: "<<(time/CLOCKS_PER_SEC)<<"s"<<endl;
        return time/CLOCKS_PER_SEC;
    }
    

    ​ 其中_mm_loadu_ps为同时加载四个单精度浮点数值的指令,因而循环每次跳跃四个元素,再将四个元素的乘积相加。对于矩阵n不能被4整除的情况,对剩余元素做类似Cache优化算法的操作。

    2.4 分片策略

    ​ 先针对cpu线程数设置分片数,将矩阵分为多个小矩阵,对每个小矩阵进行SSE指令计算。时间复杂度为O(n) = n^3,同样对矩阵B进行转置。

    ​ 具体代码如下:

    double sse_tile(int n, float a[][maxN], float b[][maxN], float c[][maxN]){ //分片策略  O(n) = n^3
        double time;
        clock_t start,end;
        start = clock();
    
        __m128 t1, t2, sum;
        float t;
        for (int i = 0; i < n; ++i) 
            for (int j = 0; j < i; ++j) 
                swap(b[i][j], b[j][i]); 
        for (int r = 0; r < n / T; ++r) 
            for (int q = 0; q < n / T; ++q) { 
                for (int i = 0; i < T; ++i) 
                    for (int j = 0; j < T; ++j) 
                        c[r * T + i][q * T +j] = 0.0;
                for (int p = 0; p < n / T; ++p) { 
                    for (int i = 0; i < T; ++i) 
                        for (int j = 0; j < T; ++j) { 
                            sum = _mm_setzero_ps();
                            for (int k = 0; k < T; k += 4){ //sum every 4th elements
                                t1 = _mm_loadu_ps(a[r * T + i] + p * T + k); 
                                t2 = _mm_loadu_ps(b[q * T + j] + p * T + k);
                                t1 = _mm_mul_ps(t1, t2); 
                                sum = _mm_add_ps(sum, t1);
                            }
                            sum = _mm_hadd_ps(sum, sum); 
                            sum = _mm_hadd_ps(sum, sum); 
                            _mm_store_ss(&t, sum);
                            c[r * T + i][q * T + j] += t;
                        }
                }
            } 
        for (int i = 0; i < n; ++i) 
            for (int j = 0; j < i; ++j) 
                swap(b[i][j], b[j][i]);
    
        end = clock();
        time = (double)(end-start);
        cout<<"分片策略耗时: "<<(time/CLOCKS_PER_SEC)<<"s"<<endl;
        return time/CLOCKS_PER_SEC;
    }
    

    3 实验结果及结果分析

    ​ 每个算法的十次运行时间结果如下:

    第1次运行结果:
    串行算法耗时: 0.753588s
    Cache优化耗时: 0.453238s
    SSE版本耗时: 0.230628s
    分片策略耗时: 0.279179s
    
    第2次运行结果:
    串行算法耗时: 0.77117s
    Cache优化耗时: 0.465396s
    SSE版本耗时: 0.239504s
    分片策略耗时: 0.293299s
    
    第3次运行结果:
    串行算法耗时: 0.746869s
    Cache优化耗时: 0.451797s
    SSE版本耗时: 0.228981s
    分片策略耗时: 0.282906s
    
    第4次运行结果:
    串行算法耗时: 0.696163s
    Cache优化耗时: 0.453274s
    SSE版本耗时: 0.233736s
    分片策略耗时: 0.277309s
    
    第5次运行结果:
    串行算法耗时: 0.878417s
    Cache优化耗时: 0.490044s
    SSE版本耗时: 0.271495s
    分片策略耗时: 0.378412s
    
    第6次运行结果:
    串行算法耗时: 1.08664s
    Cache优化耗时: 0.491328s
    SSE版本耗时: 0.243387s
    分片策略耗时: 0.291609s
    
    第7次运行结果:
    串行算法耗时: 0.777393s
    Cache优化耗时: 0.470352s
    SSE版本耗时: 0.233467s
    分片策略耗时: 0.285942s
    
    第8次运行结果:
    串行算法耗时: 0.689719s
    Cache优化耗时: 0.450596s
    SSE版本耗时: 0.224129s
    分片策略耗时: 0.284757s
    
    第9次运行结果:
    串行算法耗时: 0.692528s
    Cache优化耗时: 0.450607s
    SSE版本耗时: 0.229762s
    分片策略耗时: 0.282219s
    
    第10次运行结果:
    串行算法耗时: 0.708097s
    Cache优化耗时: 0.45446s
    SSE版本耗时: 0.223255s
    分片策略耗时: 0.28649s
    
    平均耗时:
    串行算法耗时:0.780058s
    Cache优化耗时:0.463109s
    SSE版本耗时:0.235834s
    分片策略耗时:0.294212s
    

    ​ 图表展示如下:

    算法12345
    串行算法(s)0.750.770.750.690.88
    Cache优化(s)0.450.470.450.450.49
    SSE版本(s)0.230.240.230.230.27
    分片策略(s)0.280.290.280.280.38
    算法678910
    串行算法(s)1.090.770.690.690.71
    Cache优化(s)0.490.470.450.450.45
    SSE版本(s)0.240.230.220.230.22
    分片策略(s)0.290.290.280.280.29

    在这里插入图片描述

    ​ 从图中可以明显看出,耗时最多的算法时串行算法,也是最原始的算法,Cache优化对串行算法有很明显的优化效果,时间减短大约40% ,但用时仍比SSE编程要长,SSE版本算法运行时间最短,采用分片策略后时间反而有点增长。

    ​ 由于串行算法没做任何优化,因而运行时间最长。Cache优化算法对串行算法的取址时间进行了压缩。而想要更短的运行时间就需要用到SIMD编程。分片策略比SSE版本用时较长的原因大概是分片数量不理想,并行成本消耗过高。

    4 源码

    ​ 本次实验代码如下:

    #include<iostream>
    #include<stdlib.h>
    #include <pmmintrin.h>
    #include <stdio.h>
    #include <algorithm>
    #include<cmath>
    
    using namespace std;
    
    const int maxN = 512;
    const int T = 64; // tile size
    
    double mul(int n,float a[][maxN],float b[][maxN],float c[][maxN]);
    double trans_mul(int n, float a[][maxN], float b[][maxN], float c[][maxN]);
    double sse_mul(int n, float a[][maxN], float b[][maxN], float c[][maxN]);
    double sse_tile(int n, float a[][maxN], float b[][maxN], float c[][maxN]);
    
    int main(){
        int n = 512;
        srand((unsigned)time(NULL));
        float a[maxN][maxN];
        float b[maxN][maxN];
        float c[maxN][maxN];
        double mul_sum = 0;
        double trans_mul_sum = 0;
        double sse_mul_sum = 0;
        double sse_tile_sum = 0;
        for(int i = 0; i < n; i++)
        {
            for(int j=0; j < n; j++){
                a[i][j] = rand();
                b[i][j] = rand();
            }
        }
        for(int i=0;i<10;i++){
            cout<<"第"<<i+1<<"次运行结果:"<<endl;
            mul_sum += mul(n,a,b,c);
            trans_mul_sum += trans_mul(n,a,b,c);
            sse_mul_sum += sse_mul(n,a,b,c);
            sse_tile_sum += sse_tile(n,a,b,c);
            cout<<endl;
        }
        cout<<"平均耗时:"<<endl;
        cout<<"串行算法耗时:"<<mul_sum/10<<"s"<<endl;
        cout<<"Cache优化耗时:"<<trans_mul_sum/10<<"s"<<endl;
        cout<<"SSE版本耗时:"<<sse_mul_sum/10<<"s"<<endl;
        cout<<"分片策略耗时:"<<sse_tile_sum/10<<"s"<<endl;
    }
    
    double mul(int n,float a[][maxN],float b[][maxN],float c[][maxN]){ //串行算法 O(n) = n^3
        double time;
        clock_t start,end;
        start = clock();
    
        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < n; j++)
            {
                c[i][j]= 0.0;
                for(int k = 0; k < n; k++){
                    c[i][j] += a[i][k] * b[k][j];
                }
            }
        }
    
        end = clock();
        time = (double)(end-start);
        cout<<"串行算法耗时: "<<(time/CLOCKS_PER_SEC)<<"s"<<endl;
        return time/CLOCKS_PER_SEC;
    }
    
    double trans_mul(int n, float a[][maxN], float b[][maxN], float c[][maxN]){ // Cache优化 O(n) = n^3
        double time;
        clock_t start,end;
        start = clock();
    
        for (int i = 0; i < n; ++i) 
            for (int j = 0; j < i; ++j) 
                swap(b[i][j], b[j][i]); 
        for (int i = 0; i < n; ++i) {  
            for (int j = 0; j < n; ++j) { 
                c[i][j] = 0.0;
                for (int k = 0; k < n; ++k) { 
                    c[i][j] += a[i][k] * b[j][k];
                    }
                }
        } // transposition
        for (int i = 0; i < n; ++i) 
            for (int j = 0; j < i; ++j) 
                swap(b[i][j], b[j][i]);
    
        end = clock();
        time = (double)(end-start);
        cout<<"Cache优化耗时: "<<(time/CLOCKS_PER_SEC)<<"s"<<endl;
        return time/CLOCKS_PER_SEC;
    }
    
    double sse_mul(int n, float a[][maxN], float b[][maxN], float c[][maxN]){ //SSE版本 O(n) = (n^3)/4
        double time;
        clock_t start,end;
        start = clock();
    
        __m128 t1, t2, sum;  //__m128 == float
        for (int i = 0; i < n; ++i) 
            for (int j = 0; j < i; ++j) 
                swap(b[i][j], b[j][i]); 
        for (int i = 0; i < n; ++i){ 
            for (int j = 0; j < n; ++j){ 
                c[i][j] = 0.0;
                sum = _mm_setzero_ps();  //Initialize
                for (int k = n - 4; k >= 0; k -= 4){ // sum every 4 elements 
                    t1 = _mm_loadu_ps(a[i] + k); 
                    t2 = _mm_loadu_ps(b[j] + k); 
                    t1 = _mm_mul_ps(t1, t2);
                    sum = _mm_add_ps(sum, t1);
                }
                sum = _mm_hadd_ps(sum, sum); 
                sum = _mm_hadd_ps(sum, sum); 
                _mm_store_ss(c[i] + j, sum);
                for (int k = (n % 4) - 1; k >= 0; --k){ // handle the last n%4elements
                    c[i][j] += a[i][k] * b[j][k];
                }
            }
        } 
        for (int i = 0; i < n; ++i) 
            for (int j = 0; j < i; ++j) 
                swap(b[i][j], b[j][i]);
    
        end = clock();
        time = (double)(end-start);
        cout<<"SSE版本耗时: "<<(time/CLOCKS_PER_SEC)<<"s"<<endl;
        return time/CLOCKS_PER_SEC;
    }
    
    double sse_tile(int n, float a[][maxN], float b[][maxN], float c[][maxN]){ //分片策略  O(n) = n^3
        double time;
        clock_t start,end;
        start = clock();
    
        __m128 t1, t2, sum;
        float t;
        for (int i = 0; i < n; ++i) 
            for (int j = 0; j < i; ++j) 
                swap(b[i][j], b[j][i]); 
        for (int r = 0; r < n / T; ++r) 
            for (int q = 0; q < n / T; ++q) { 
                for (int i = 0; i < T; ++i) 
                    for (int j = 0; j < T; ++j) 
                        c[r * T + i][q * T +j] = 0.0;
                for (int p = 0; p < n / T; ++p) { 
                    for (int i = 0; i < T; ++i) 
                        for (int j = 0; j < T; ++j) { 
                            sum = _mm_setzero_ps();
                            for (int k = 0; k < T; k += 4){ //sum every 4th elements
                                t1 = _mm_loadu_ps(a[r * T + i] + p * T + k); 
                                t2 = _mm_loadu_ps(b[q * T + j] + p * T + k);
                                t1 = _mm_mul_ps(t1, t2); 
                                sum = _mm_add_ps(sum, t1);
                            }
                            sum = _mm_hadd_ps(sum, sum); 
                            sum = _mm_hadd_ps(sum, sum); 
                            _mm_store_ss(&t, sum);
                            c[r * T + i][q * T + j] += t;
                        }
                }
            } 
        for (int i = 0; i < n; ++i) 
            for (int j = 0; j < i; ++j) 
                swap(b[i][j], b[j][i]);
    
        end = clock();
        time = (double)(end-start);
        cout<<"分片策略耗时: "<<(time/CLOCKS_PER_SEC)<<"s"<<endl;
        return time/CLOCKS_PER_SEC;
    }
    
    展开全文
  • 关于CRC校验码的详尽分析和描述,对串行和并行的原理进行了阐述,然后利用Quartus软件绘制出电路原理图,有设计的总结以及详细的仿真过程。
  • 描述 CellLists.jl是一种解决固定半径近邻问题的算法。 也就是说,它找到彼此之间在固定距离内的所有成对的点。 另外,我写了一篇文章“ ,它更深入地探讨了其背后的单元格列表算法和理论。 安装 当前,该软件包尚未...
  • AdaBoost基本原理与算法描述

    万次阅读 多人点赞 2018-08-21 19:59:33
    最近在看集成学习方法,前面已经对XGBoost的原理与简单实践做了介绍,这次对AdaBoost算法做个学习笔记,来巩固自己所学的知识,同时也希望对需要帮助的人有所帮助。 关于集成学习主要有两大分支,一种是bagging方法...

    一. 前言

    最近在看集成学习方法,前面已经对XGBoost的原理简单实践做了介绍,这次对AdaBoost算法做个学习笔记,来巩固自己所学的知识,同时也希望对需要帮助的人有所帮助。

    关于集成学习主要有两大分支,一种是bagging方法,一种是boosting方法。

    bagging方法的弱学习器之间没有依赖关系,各个学习器可以并行生成,最终通过某种策略进行集成得到强学习器(比如回归问题用所有弱学习器输出值的平均值作为预测值;分类问题使用投票法,即少数服从多数的方法来得到最终的预测值;也可以使用学习法,即每个弱学习器的输出值作为训练数据来重新学习一个学习器,而该学习器的输出值作为最终的预测值,代表方法有stacking方法,感兴趣的同学可以自己去了解一下)。bagging方法采用自助采样法,即在总样本中随机的选取m个样本点作为样本m1,然后放回,继续随机选取m个样本点作为样本m2,如此循环下去直到选取的样本个数达到预设定值n,对这n个样本进行学习,生成n个弱学习器。随机森林算法就是bagging方法的代表算法。

    boosting方法的若学习器之间有强的依赖关系,各个弱学习器之间串行生成。它的工作机制是初始给每个样本赋予一个权重值(初始权重值一般是1/m,m表示有m个样本),然后训练第一个弱学习器,根据该弱学习器的学习误差率来更新权重值,使得该学习器中的误差率高的训练样本点(所有的训练样本点)的权重值变高,权重值高的训练样本点在后面的弱学习器中会得到更多的重视,以此方法来依次学习各个弱学习器,直到弱学习器的数量达到预先指定的值为止,最后通过某种策略将这些弱学习器进行整合,得到最终的强学习器。boosting方法的代表算法有AdaBoost和boosting tree算法,而AdaBoost算法就是本文接下来要介绍的算法。

    在介绍AdaBoost之前,要先搞清楚boosting系列算法主要解决的一些问题,如下:

    • 弱学习器的权重系数\alpha如何计算?
    • 样本点的权重系数w如何更新?
    • 学习的误差率e如何计算?
    • 最后使用的结合策略是什么?

    下面我们就来看看AdaBoost是如何解决以上问题的。

    二. AdaBoost基本原理介绍

    2.1 AdaBoost分类问题

    以二分类为例,假设给定一个二类分类的训练数据集\chi = \left \{ (x_{1}, y_{1}), (x_{2}, y_{2}),...,(x_{n}, y_{n})\right \},其中x_{i}表示样本点,y_{i}表示样本对应的类别,其可取值为{-1,1}。AdaBoost算法利用如下的算法,从训练数据中串行的学习一系列的弱学习器,并将这些弱学习器线性组合为一个强学习器。AdaBoost算法描述如下:

    输入:训练数据集\chi = \left \{ (x_{1}, y_{1}), (x_{2}, y_{2}),...,(x_{n}, y_{n})\right \}

    输出:最终的强分类器G(x)

    (1) 初始化训练数据的权重分布值:(D_{m} 表示第m个弱学习器的样本点的权值)

                   D_{1}=(w_{11},...,w_{1i},...,w_{1N}),       w_{1i}=1/N,     i=1,2,...,N

    (2) 对M个弱学习器,m=1,2,...,M:

    (a)使用具有权值分布D{_{m}}的训练数据集进行学习,得到基本分类器 G{_{m}}(x) ,其输出值为{-1,1};

    (b)计算弱分类器G{_{m}}(x)在训练数据集上的分类误差率e{_{m}},其值越小的基分类器在最终分类器中的作用越大。

                            

                            其中,I(G{_{m}}(x{_{i}})\neq y{_{i}})取值为0或1,取0表示分类正确,取1表示分类错误。

    (c)计算弱分类器G{_{m}}(x)的权重系数\alpha {_{m}}:(这里的对数是自然对数)

                   \alpha {_{m}}=\frac{1}{2}ln{\frac{1-e{_{m}}}{e{_{m}}}}

    一般情况下e{_{m}}的取值应该小于0.5,因为若不进行学习随机分类的话,由于是二分类错误率等于0.5,当进行学习的时候,错误率应该略低于0.5。当e{_{m}}减小的时候\alpha {_{m}}的值增大,而我们希望得到的是分类误差率越小的弱分类器的权值越大,对最终的预测产生的影响也就越大,所以将弱分类器的权值设为该方程式从直观上来说是合理地,具体的证明\alpha {_{m}}为上式请继续往下读。

    (d)更新训练数据集的样本权值分布:

                            

    对于二分类,弱分类器G{_{m}}(x)的输出值取值为{-1,1},y{_{i}}的取值为{-1,1},所以对于正确的分类 y{_{i}}G{_{m}}(x)>0,对于错误的分类y{_{i}}G{_{m}}(x)<0,由于样本权重值在[0,1]之间,当分类正确时w{_{m+1,i}}取值较小,而分类错误时w{_{m+1,i}}取值较大,而我们希望得到的是权重值高的训练样本点在后面的弱学习器中会得到更多的重视,所以该上式从直观上感觉也是合理地,具体怎样合理,请往下读。

                      其中,Z{_{m}}是规范化因子,主要作用是将W{_{mi}}的值规范到0-1之间,使得\sum_{i=1}^{N}{W{_{mi}}} = 1

                           

    (3) 上面我们介绍了弱学习器的权重系数α如何计算,样本的权重系数W如何更新,学习的误差率e如何计算,接下来是最后一个问题,各个弱学习器采用何种结合策略了,AdaBoost对于分类问题的结合策略是加权平均法。如下,利用加权平均法构建基本分类器的线性组合:

                   f(x)=\sum_{m=1}^{M}{\alpha {_{m}}G{_{m}}(x)}

         得到最终的分类器:

                  G(x)=sign(f(x))=sign(\sum_{m=1}^{M}\alpha {_{m}}G{_{m}}(x))

    以上就是对于AdaBoost分类问题的介绍,接下来是对AdaBoost的回归问题的介绍。

    2.2 AdaBoost回归问题

    AdaBoost回归问题有许多变种,这里我们以AdaBoost R2算法为准。

    (1)我们先看看回归问题的误差率问题,对于第m个弱学习器,计算他在训练集上的最大误差:

                           E{_{m}}=max|y{_{i}}-G{_{m}}(x{_{i}})|    i=1,2,...,N

    然后计算每个样本的相对误差:(计算相对误差的目的是将误差规范化到[0,1]之间)

                          e{_{mi}}=\frac{|y{_{i}}-G{_{m}}(x{_{i}})|}{E{_{m}}}  ,  显然 0\leq e{_{mi}}\leq 1

    这里是误差损失为线性时的情况,如果我们用平方误差,则e{_{mi}}=\frac{|y{_{i}}-G{_{m}}(x{_{i}})|}{E{_{m}}^2}^2,如果我们用指数误差,则e{_{mi}}=1-exp(\frac{-y{_{i}}+G{_{m}}(x{_{i}})}{E{_{m}}})

    最终得到第k个弱学习器的误差率为:

                        e{_{m}}=\sum_{i=1}^{N}{w{_{mi}}e{_{mi}}},表示每个样本点的加权误差的总和即为该弱学习器的误差。

    (2)我们再来看看弱学习器的权重系数α,如下公式:

                       \alpha {_{m}}=\frac{e{_{m}}}{1-e{_{m}}}

    (3)对于如何更新回归问题的样本权重,第k+1个弱学习器的样本权重系数为:

                      w{_{m+i,i}}=\frac{w{_{mi}}}{Z{_{m}}}\alpha {_{m}}^{1-e{_{mi}}}

    其中Z{_{k}}是规范化因子:Z{_{m}}=\sum_{i=1}^{N}{w{_{mi}}\alpha {_{m}}^{1-e{_{mi}}}}

    (4)最后是结合策略,和分类问题不同,回归问题的结合策略采用的是对加权弱学习器取中位数的方法,最终的强回归器为:

                      G(x)=\sum_{m=1}^{M}{g(x)ln\frac{1}{\alpha {_{m}}}},其中g(x)是所有\alpha {_{m}}G{_{m}}(x)的中位数(m=1,2,...,M)。

    这就是AdaBoost回归问题的算法介绍,还有一个问题没有解决,就是在分类问题中我们的弱学习器的权重系数\alpha {_{m}}是如何通过计算严格的推导出来的。

    2.3 AdaBoost前向分步算法

    在上两节中,我们介绍了AdaBoost的分类与回归问题,但是在分类问题中还有一个没有解决的就是弱学习器的权重系数\alpha {_{m}}=\frac{1}{2}ln{\frac{1-e{_{m}}}{e{_{m}}}}是如何通过公式推导出来的。这里主要用到的就是前向分步算法,接下来我们就介绍该算法。

    从另一个角度讲,AdaBoost算法是模型为加法模型,损失函数为指数函数,学习算法为前向分步算法时的分类问题。其中,加法模型表示我们的最终得到的强分类器是若干个弱分类器加权平均得到的,如下:

            f(x)=\sum_{m=1}^{M}{\alpha {_{m}}G{_{m}}(x)}

    损失函数是指数函数,如下:

           L(y,f(x))=exp(-yf(x))

    学习算法为前向分步算法,下面就来介绍AdaBoost是如何利用前向分布算法进行学习的:

    (1)假设进过m-1轮迭代前向分布算法已经得到f{_{m-1}}(x)

              f{_{m-1}}=f{_{m-2}}(x)+\alpha {_{m-1}}G{_{m-1}}(x)

                        =\alpha {_{1}}G{_{1}}(x)+...+\alpha {_{m-1}}G{_{m-1}}(x)

    在第m轮的迭代得到\alpha {_{m}}G{_{m}}(x)f{_{m}}(x).

              f{_{m}}(x)=f{_{m-1}}(x)+\alpha {_{m}}G{_{m}}(x)

    目标是使前向分布算法得到的\alpha {_{m}}G{_{m}}(x)使f{_{m}}(x)在训练数据集T上的指数损失最小,即

             (\alpha {_{m}},G{_{m}}(x))=arg \underset{\alpha ,G}{min}\sum_{i=1}^{N}exp(-y{_{i}}(f{_{m-1}}(x{_{i}})+\alpha G(x{_{i}})))

                                   =arg\underset{\alpha ,G}{min}\sum_{i=1}^{N}\bar{w}{_{mi}}exp(-y{_{i}}\alpha G(x{_{i}}))          {\color{Red} (1)}

    上式即为我们利用前向分步学习算法得到的损失函数。其中,\bar{w}{_{mi}}=exp(-y{_{i}}f{_{m-1}}(x{_{i}}))。因为\bar{w}{_{mi}}既不依赖\alpha也不依赖于G,所以在第m轮迭代中与最小化无关。但\bar{w}{_{mi}}依赖于f{_{m-1}}(x),随着每一轮的迭代而发生变化。

    上式达到最小时所取的\alpha ^{_{*}}{_{m}}G ^{_{*}}{_{m}}(x)就是AdaBoost算法所得到的\alpha {_{m}}G{_{m}}(x)

    (2)首先求分类器G ^{_{*}}{_{m}}(x)

    我们知道,对于二分类的分类器G(x)的输出值为-1和1,y{_{i}}\neq G{_{m}}(x{_{i}})表示预测错误,y{_{i}}= G{_{m}}(x{_{i}})表示正确,每个样本点都有一个权重值,所以对于一个弱分类器的输出则为:G{_{m}}(x)=\sum_{i=1}^{N}\bar{w}{_{mi}}I(y{_{i}}\neq G{_{m}}(X{_{i}})),我们的目标是使损失最小化,所以我们的具有损失最小化的第m个弱分类器即为:

    G^{_{*}}{_{m}}(x)=arg \underset{G}{min}\sum_{i=1}^{N}\bar{w}{_{mi}}I(y{_{i}}\neq G(x{_{i}}))   其中,\bar{w}{_{mi}}=exp(-y{_{i}}f{_{m-1}}(x{_{i}}))

    为什么用I(y{_{i}}\neq G(x{_{i}}))表示一个弱分类器的输出呢?因为我们的AdaBoost并没有限制弱学习器的种类,所以它的实际表达式要根据使用的弱学习器类型来定。

    此分类器即为Adaboost算法的基本分类器G{_{m}}(x),因为它是使第m轮加权训练数据分类误差率最小的基本分类器。

    (3)然后就是来求\alpha ^{_{*}}{_{m}}

    G ^{_{*}}{_{m}}(x)代入损失函数(1)式中,得:

          \alpha {_{m}}=\sum_{i=1}^{N}\bar{w}{_{mi}}exp(-y{_{i}}\alpha{_{m}} G^{_{*}}{_{m}}(x{_{i}}))

    我们的目标是最小化上式,求出对应的\alpha ^{_{*}}{_{m}}

                  \sum_{i=1}^{N}\bar{w}{_{mi}}exp(-y{_{i}}\alpha{_{m}} G^{_{*}}{_{m}}(x{_{i}}))

             =\sum_{y{_{i}}=G{_{m}}(x{_{i}})}\bar{w{_{mi}}}e^{_{-\alpha }}+\sum_{y{_{i}}\neq G{_{m}}(x{_{i}})}\bar{w{_{mi}}}e^{_{\alpha }}

            =e^{_{-\alpha }}\sum_{y{_{i}}=G{_{m}}(x{_{i}})}\bar{w}{_{mi}}+e^{_{\alpha }}\sum_{y{_{i}}\neq G{_{m}}(x{_{i}})}\bar{w}{_{mi}}

            =e^{_{-\alpha }}(\sum_{i=1}^{N}\bar{w}{_{mi}}-\sum_{y{_{i}}\neq G{_{m}}(x{_{i}})}\bar{w}{_{mi}})+e^{_{\alpha }}\sum_{y{_{i}}\neq G{_{m}}(x{_{i}})}\bar{w}{_{mi}}

            =(e^{_{\alpha }}-e^{_{-\alpha }})\sum_{y{_{i}}\neq G{_{m}}(x{_{i}})}\bar{w}{_{mi}}+e^{_{-\alpha }}\sum_{i=1}^{N}\bar{w}{_{mi}}

            =(e^{_{\alpha }}-e^{_{-\alpha }})\sum_{i=1}^{N}\bar{w}{_{mi}}I(y{_{i}}\neq G{_{m}}(x{_{i}}))+e^{_{-\alpha }}\sum_{i=1}^{N}\bar{w}{_{mi}}        {\color{Red} (2)}

    由于,e{_{m}}=\frac{\sum_{i=1}^{N}\bar{w}{_{mi}}I(y{_{i}}\neq G{_{m}}(x{_{i}}))}{\sum_{i=1}^{N}\bar{w}{_{mi}}}

    注意:这里我们的样本点权重系数\bar{w}{_{mi}}并没有进行规范化,所以\sum_{i=1}^{m}\bar{w}{_{mi}}\neq 1

    (2)式为:   (e^{_{\alpha }}-e^{_{-\alpha }})e{_{m}}\sum_{i=1}^{N}\bar{w}{_{mi}}+e^{_{-\alpha }}\sum_{i=1}^{N}\bar{w}{_{mi}}

    则我们的目标是求:

             \alpha {_{m}}=arg\underset{\alpha }{min}(e^{_{\alpha }}-e^{_{-\alpha }})e{_{m}}\sum_{i=1}^{N}\bar{w}{_{mi}}+e^{_{-\alpha }}\sum_{i=1}^{N}\bar{w}{_{mi}}

    上式求\alpha偏导,并令偏导等于0,得:

           (e^{_{\alpha }}+e^{_{-\alpha }})e{_{m}}\sum_{i=1}^{N}\bar{w}{_{mi}}-e^{_{-\alpha }}\sum_{i=1}^{N}\bar{w}{_{mi}}=0,进而得到:

           (e^{_{\alpha }}+e^{_{-\alpha }})e{_{m}}-e^{_{-\alpha }}=0,求得:\alpha ^{_{*}}{_{m}}=\frac{1}{2}ln\frac{1-e{_{m}}}{e{_{m}}},其中e{_{m}}为误差率:

           e{_{m}}=\frac{\sum_{i=1}^{N}\bar{w}{_{mi}}I(y{_{i}}\neq G{_{m}}(x{_{i}}))}{\sum_{i=1}^{N}\bar{w}{_{mi}}}=\sum_{i=1}^{N}w{_{mi}}I(y{_{i}}\neq G(x{_{i}}))

    (4)最后看样本权重的更新。

    利用前面所讲的f{_{m}}(x)=f{_{m-1}}(x)+\alpha {_{m}}G{_{m}}(x),以及权值 \bar{w}{_{mi}}=exp(-y{_{i}}f{_{m-1}}(x))

    可以得到如下式子:

           \bar{w}{_{m+1,i}}=\bar{w}{_{mi}}exp(-y{_{i}}\alpha {_{m}}G{_{m}}(x{_{i}}))

    这样就得到了我们前面所讲的样本权重更新公式。

    2.4 AdoBoost算法的正则化

    为了防止过拟合,AdaBoost算法中也会加入正则化项,这个正则化项我们称之为步长也就是学习率。定义为v,对于前面的弱学习器的迭代有:

                     f{_{m}}(x)=f{_{m-1}}(x)+\alpha {_{m}}G{_{m}}(x)

    加入正则化项,就变成如下:

                    f{_{m}}(x)=f{_{m-1}}(x)+v\alpha {_{m}}G{_{m}}(x)

    v的取值范围为(0,1]。对于同样的训练集学习效果,较小的v意味着我们需要更多的弱学习器的迭代次数。通常我们用学习率和迭代最大次数一起来决定算法的拟合效果。

    到这里,我们的AdaBoost算法介绍完毕。

    三. AdaBoost算法流程描述

    3.1 AdaBoost分类问题的算法流程描述

    关于AdaBoost的分类问题,sklearn中采用的是SAMME和SAMME.R算法,SAMME.R算法是SAMME算法的变种。sklearn中默认采用SAMME.R,原因是SAMME.R算法比SAMME算法收敛速度更快,用更少的提升迭代次数实现了更低的测试误差。接下来我们先介绍AdaBoost的分类算法流程,可以将二元分类算法视为多元分类算法的一个特例。

    3.1.1 SAMME算法流程描述:

    输入:样本集T=\left \{ (x{_{1}},y{_{1}}),(x{_{2}},y{_{2}}),...,(x{_{N}},y{_{N}}) \right \},输出为\left \{ -1,1 \right \},弱分类器的迭代次数为M,样本点的个数为N。

    输出:最终的强分类器G(x)

    (1)初始化样本点的权重为:

                       D_{1}=(w_{11},...,w_{1i},...,w_{1N}),       w_{1i}=1/N,     i=1,2,...,N

    (2)对于m=1,2,..,M

           (a)使用带有权重的样本来训练一个弱学习器G{_{m}}(x);

           (b)计算弱分类器G{_{m}}(x)的分类误差率:

                        

           (c)计算弱分类器的系数:

                          \alpha {_{m}}=\frac{1}{2}ln{\frac{1-e{_{m}}}{e{_{m}}}}+ln(K-1)

             其中,K表示K元分类,可以看出当K=2时,ln(K-1)=0,余下的\alpha {_{m}}与我们二元分类算法所描述的弱分类器系数一致。

           (d)更新样本的权重分布:

                     

    (3)构建最终的强分类器:

                         G(x)=sign(f(x))=sign(\sum_{m=1}^{M}\alpha {_{m}}G{_{m}}(x))

    3.1.2 SAMME.R算法流程描述:

    输入:样本集T=\left \{ (x{_{1}},y{_{1}}),(x{_{2}},y{_{2}}),...,(x{_{N}},y{_{N}}) \right \},输出为\left \{ -1,1 \right \},弱分类器的迭代次数为M,样本点的个数为N。

    输出:最终的强分类器G(x)

    (1)初始化样本点的权重为:

                       D_{1}=(w_{11},...,w_{1i},...,w_{1N}),       w_{1i}=1/N,     i=1,2,...,N

    (2)对于m=1,2,..,M

           (a)使用带有权重的样本来训练一个弱学习器G{_{m}}(x);

           (b)获得带有权重分类的概率评估:

                      P{_{mk}}(x{_{i}})=Prob{_{w}}(c=k|x{_{i}})

                   其中P{_{mk}}(x{_{i}})表示第m个弱学习器将样本x{_{i}}分为第k类的概率。k=1,2,...,K,K表示分类的类别个数。

           (c) 使用加权概率推导出加法模型的更新,然后将其应用于数据:

                       h{_{mk}}(x)=(K-1)(logP{_{mk}}(x)-\frac{1}{K}\sum_{\bar{k}=1}^{K}logP{_{m\bar{k}}}(x))k=1,2,...,K

           (d)更新样本点权重系数:

                      w{_{m+1,i}}=w{_{mi}}exp(-\frac{K-1}{K}y{_{i}}logP{_{m}}(x{_{i}}))

           (e)标准化样本点权重w;

    (3)构建最终的强分类器:

                       G(x)=sign(arg\underset{K}{max}\sum_{m=1}^{M}h{_{mk}}(x)),表示使\sum_{m=1}^{M}h{_{mk}}(x))最大的类别即为我们所预测的类别。

    3.2 AdaBoost回归问题的算法流程描述

    在sklearn中,回归使用的算法为 AdaBoost.R2算法,具体的流程描述如下:

    输入:样本集T=\left \{ (x{_{1}},y{_{1}}),(x{_{2}},y{_{2}}),...,(x{_{N}},y{_{N}}) \right \},输出为\left \{ -1,1 \right \},弱分类器的迭代次数为M,样本点的个数为N。

    输出:最终的强分类器G(x)

    (1)初始化样本点的权重为:

                       D_{1}=(w_{11},...,w_{1i},...,w_{1N}),       w_{1i}=1/N,     i=1,2,...,N

    (2)对于m=1,2,..,M

    (a)使用具有权重D{_{m}}的样本集来训练数据,得到弱学习器G{_{m}}(x)

    (b)计算训练集上的最大误差

                 E{_{k}}=max|y{_{i}}-G{_{m}}(x{_{i}})|i=1,2,...,N

    (c)计算每个样本点的相对误差:

             如果是线性误差:则e{_{mi}}=\frac{|y{_{i}}-G{_{m}}(x{_{i}})|}{E{_{m}}}

             如果是平方误差,则e{_{mi}}=\frac{(y{_{i}}-G{_{m}}(x{_{i}}))^2}{E{_{m}}^2}

             如果是指数误差,则e{_{mi}}=1-exp(\frac{-|y{_{i}}-G{_{m}}(x{_{i}})|}{E{_{m}}})

    (d)计算回归误差率:

            e{_{m}}=\sum_{i=1}^{N}w{_{mi}}e{_{mi}}

    (c)计算弱学习器的系数:

            \alpha {_{m}}=\frac{e{_{m}}}{1-e{_{m}}}

    (d)更新样本集的权重分布:

            w{_{m+1,i}}=\frac{w{_{mi}}}{Z{_{m}}}\alpha {_{m}}^{1-e{_{mi}}},其中Z{_{m}}是规范化因子,Z{_{m}}=\sum_{i=1}^{N}w{_{mi}}\alpha {_{m}}^{1-e{_{mi}}}

    (3)构建最终的强学习器:

                       G(x)=\sum_{m=1}^{M}{g(x)ln\frac{1}{\alpha {_{m}}}},其中g(x)是所有\alpha {_{m}}G{_{m}}(x)的中位数(m=1,2,...,M)。

    四. AdaBoost算法的优缺点

    4.1 优点

    (1)不容易发生过拟合;

    (2)由于AdaBoost并没有限制弱学习器的种类,所以可以使用不同的学习算法来构建弱分类器;

    (3)AdaBoost具有很高的精度;

    (4)相对于bagging算法和Random Forest算法,AdaBoost充分考虑的每个分类器的权重;

    (5)AdaBoost的参数少,实际应用中不需要调节太多的参数。

    4.2 缺点

    (1)AdaBoost迭代次数也就是弱分类器数目不太好设定,可以使用交叉验证来进行确定。

    (2)数据不平衡导致分类精度下降。

    (3)训练比较耗时,每次重新选择当前分类器最好切分点。

    (4)对异常样本敏感,异常样本在迭代中可能会获得较高的权重,影响最终的强学习器的预测准确性。

    五. 参考文献/博文

    (1)李航,《统计学习方法》 第八章

    (2)Multi-class AdaBoost 论文

    (3)Boosting for Regression Transfer AdaBoost回归论文

    (4)https://www.cnblogs.com/pinard/p/6133937.html

    展开全文
  • 个体学习器间存在强依赖关系、必须串行生成的序列化方法 代表是Boosting族算法。 Boosting族中最著名的代表是AdaBoost。 个体学习器间不存在强依赖关系、必须同时生成的并行化化方法 代表是Bagging和随机森林 ...

    1 集成学习方法包含两类:

    1. 个体学习器间存在强依赖关系、必须串行生成的序列化方法
      代表是Boosting族算法。
      Boosting族中最著名的代表是AdaBoost。
    2. 个体学习器间不存在强依赖关系、必须同时生成的并行化化方法
      代表是Bagging和随机森林

    2 串行方法

    Boosting(提升)族算法是串行算法的代表,其思想
    从训练集训练出一个基学习器,根据这个基学习器的表现对训练样本分布进行调整,然后用调整后的训练集训练出下一个基学习器,如此重复进行,直至基学习器数目达到事先指定的值T,最终将这T个基学习器进行加权结合。

    下图是《机器学习-周志华》中的解释:
    《机器学习-周志华》
    Boosting算法有几个问题没有详细说明:

    1. 如何计算学习误差率e?
    2. 如何得到弱学习器权重系数αα?
    3. 如何更新样本权重D?
    4. 使用何种结合策略?

    只要是boosting族的算法,都要解决这4个问题。接下来看Adaboost是如何解决的。

    2.1 AdaBoost

    AdaBoost(Adaptive Boost 自适应提升)是一种Boosting算法。
    AdaBoost算法有多种推导方式,此处采用基于“加性模型”,即基学习器的线性组合
    在这里插入图片描述

    2.1.1 算法描述

    算法描述如下图,其中yi={-1,+1},f是真实函数。
    在这里插入图片描述

    2.1.2 公式推导

    假设我们的训练集样本是:
    在这里插入图片描述
    训练集在第k个弱学习器的输出权重为(其中wki是第k个学习器中,第i个样本对应的权重)——对应过程1
    在这里插入图片描述
     分类问题的误差率很好理解和计算。由于多元分类是二元分类的推广,这里假设我们是二元分类问题,输出为{-1,1},则第k个弱分类器Gk(x)在训练集上的加权误差率为——对应过程4
    在这里插入图片描述
    接着我们看弱学习器权重系数,对于二元分类问题,第k个弱分类器Gk(x)的权重系数为——对应过程6
    在这里插入图片描述
    为什么这样计算弱学习器权重系数?从上式可以看出,如果分类误差率ekek越大,则对应的弱分类器权重系数αkαk越小。也就是说,误差率小的弱分类器权重系数越大。具体为什么采用这个权重系数公式,我们在讲Adaboost的损失函数优化时再讲。

    第三个问题,更新更新样本权重D。假设第k个弱分类器的样本集权重系数为D(k)=(wk1,wk2,…wkm),则对应的第k+1个弱分类器的样本集权重系数为——对应过程7
    在这里插入图片描述
    最后一个问题是集合策略。Adaboost分类采用的是加权表决法,最终的强分类器为——对应输出
    在这里插入图片描述
    标准AdaBoost只适用于二分类任务,对于多分类、回归等任务需要使用AdaBoost的变体算法。

    AdaBoost用于二分类、多分类、回归等任务的情况,可以参考文章:集成学习之Adaboost算法原理小结-博客园。这篇文章对AdaBoost的公式推导非常明晰、易理解。

    3 并行方法

    3.1 Bagging

    Bagging(Bootstrap Aggreating 自助聚集)是并行式集成算法的最著名代表。

    3.1.1 Bagging的思想

    基于自助采样法(bootstrap sampling),采样出T个采样集,然后基于每个采样集训练出一个基学习器,再将这些基学习器进行结合。

    自助采样法(bootstrap sampling)——有放回采样:
    在这里插入图片描述
    对基学习器的预测输出进行结合时,通常:

    • 分类任务,使用简单投票法。若两个类票数一样,则最简单的随机选择一个,也可进一步考察学习器投票的置信度。
    • 回归任务,使用简单平均法。

    Bagging的算法描述:
    在这里插入图片描述
    在这里插入图片描述

    3.1.2 Bagging、AdaBoost的不同

    • 标准AdaBoost只适用于二分类任务,处理多分类或回归任务时,须对AdaBoost进行修改。
    • Bagging能不加修改地用于多分类、回归等任务。

    参考文献:
    Bagging与随机森林算法原理小结-博客园

    3.2 随机森林

    随机森林(Random Forest)是Bagging的一个扩展变体。
    为了提升泛化性能,随机森林采取了两种措施:

    • 使用CART决策树作为基学习器
    • 在决策树的构建过程中引入随机属性
      在使用决策树的基础上,RF对决策树的构建做了改进。
      普通的决策树,会在当前结点的属性集合(假设有d个属性)中选择一个最优属性,然后划分出左、右子树。
      而在RF中,对基决策树的每个结点,先从该结点的属性集合中随机选择一个包含k个属性的子集,然后再从这个子集中选择一个最优属性用于划分。
      如果k=d,则此时RF的CART决策树和普通的CART决策树没有区别。k越小,则模型越健壮,当然此时对于训练集的拟合程度会变差。也就是说k越小,模型的方差会减小,但是偏差会增大。在实际案例中,一般会通过交叉验证调参获取一个合适的k的值。一般情况下,推荐k=log2d。

    4 结合策略

    基学习器结合带来的好处:

    • 统计方面
      学习任务的假设空间可能很大,可能有多个假设的性能相同,使用单学习器可能因误选导致泛化性能不佳。
    • 计算方面
      学习算法容易陷入局部极小,多次运行后结合,可降低陷入局部极小的风险。
    • 表示方面
      学习任务的真实假设可能不在当前学习算法所考虑的假设空间中,结合多个学习器,能够扩大假设空间

    4.1 平均法

    对数值型输出,常用结合策略是平均法,包含简单平均法、加权平均法。加权平均法中,权重是个体学习器的权重。

    4.2 投票法

    对分类任务,常用结合策略是投票法,包含绝对多数投票法,相对多数投票法、加权投票法。

    1. 绝对多数投票法:得票超过半数的标记。
    2. 相对多数投票法:得票最多的标记。
    3. 加权投票法:权重是个体学习器的权重。

    4.3 学习法

    训练数据很多时,更强大的结合策略是“学习法”。
    学习法思想:将基学习器(初级学习器)的预测结果,通过另一个学习器(次级学习器)进行结合。

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    5 GBDT

    梯度提升树(Gradient Boosting Decison Tree, 以下简称GBDT)是Boosting家族中另一个重要的算法。
    请前往查看另一篇文章:

    展开全文
  • 详解归并排序算法

    千次阅读 2020-04-27 14:10:54
    基本思想 归并排序的基本思想是: 先将序列一次次分成子序列,直到子序列长度为1; 再将已有序的子序列合并,得到完全有序的序列。 可以看出归并排序运用了 ** 分而治之的思想** 。 例子 输入数组 [ 2, 5, 3 , 10,-...
  • 研究了Turbo码的并行译码算法,将Turbo码译码和图论结合起来,利用Bayesian网络图模型描述了Turbo码的译码过程,基于模型使用Pearl的信息传播算法,建立了Turbo码的并行译码算法。并对所讨论的并行译码算法进行了模拟,...
  • 该代码被设计为易于更改和移植:您的输入源(文件、串行通信等)、 输入格式(有符号或无符号整数、浮点数、双精度等)、采样频率、算法微调、 等等。 .c 文件有据可查,注释中解释了每一个有意义的行或代码块, ...
  • 1、熟悉快速排序的串行算法 2、熟悉快速排序的并行算法 3、实现快速排序的并行算法 3.2 实验环境及软件 单台或联网的多台PC机,Linux操作系统,MPI系统。 3.3实验内容 1、快速排序的基本思想 2、单处理机上快速...
  • 为解决AprioriTid算法对大数据执行效率不高的问题,根据Hadoop平台的MapReduce模型,分析了AprioriTid算法的并行化方法,给出了并行化的主要步骤和Map、Reduce函数的描述。与串行的AprioriTid算法相比,并行算法利用...
  • 在介绍CRC校验原理和传统CRC32串行比特算法的基础上,由串行比特型算法推导出一种CRC32并行算法。并结合SATAⅡ协议的要求,完成了SATAⅡ主控制器设计中CRC生成与校验模块的设计。最后通过在ISE平台上编写Verilog硬件...
  • 这是Liu等人描述的HPSOM算法的有效实现。 该实现可以在以下环境中运行: 串行体系结构(通过具有make buildserial的batch-som分支) 共享内存体系结构(通过batch-som分支将OpenMP与OMP_NUM_THREADS环境变量一起...
  • 贪心算法(文字描述解释)

    千次阅读 2020-02-20 13:13:27
    贪心算法 ​ 贪心算法(又称贪婪算法,greedy algorithm)是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的是在某种意义上的局部最优解,而不能算是全局最优解...
  • 快速排序(QuickSort)算法介绍

    万次阅读 多人点赞 2017-09-20 09:47:38
    算法简介快速排序(Quicksort)是对冒泡排序的一种改进算法。由C. A. R. Hoare在1960年提出。该算法使用广泛、效率很高,是最重要的排序算法之一。该算法的实现基本可分为以下几步:
  • 文章目录前言1、智能优化算法:黑寡妇算法(蛛)1.1算法原理1.1.1 初始化种群1.1.2 蜘蛛运动1.1.3 信息素1.2 算法流程1.3 参考文献2、智能优化算法:灰狼优化算法(母狼)2.1 算法原理2.1.1 包围猎物2.1.2
  • 串行算法 串行算法描述是:找出集中点x坐标值的最小值和最大值的两个极限点pmin和pmax,显然此二值极点位于土包边界上。用直线连接pmin和pmax,则点集中的点部分位于上方部分位于下方,显然点集的最小凸包右这两...
  • unsigned char cal_table_high_first(unsigned char value) { unsigned char i ; unsigned char checksum = value ; for (i=8;i>0;--i) { if (check_sum & 0x80) { check_sum = (check_sum<... }
  • Boosting[8](串行)是两种常见的集成学习方法,这 两者的区别在于集成的方式是并行还是串行。随机森林 算法(Random Forests)[9]是Bagging集成方法里最具有代表性的一个算法,这也是本文重点总结的算法。 随机森林是...
  • 算法基础-算法分析

    千次阅读 多人点赞 2022-01-20 17:23:44
    算法是对特定问题求解步骤的一种描述,是执行的有限序列,其中每个指令都表示一个或多个操作。 如果想要从一个数组中查找指定的数字key并返回位置,只需要从第一个位置开始遍历整个数组,直到找到给定的key并返回...
  • 目录冒泡排序算法一、问题描述二、问题分析三、代码实现四、运行结果五、算法解析六、BUG记录 一、问题描述        将一个数组中的数字进行排序处理,并返回一个排好序的新数组...
  • 同样一个算法,用硬件实现和使用软件实现的区别很大,在实现难度和效率上都天差地别。 算法硬件实现和软件实现的区别? CPU一般分为两种,一种是专用CPU,另一种是通用CPU,电脑上的CPU就是一种通用CPU,它是基于...
  • 根据高光谱图像的特点,描述了该算法的设计原理,阐述了PPI的主要云分解过程,并分析了串行和并行算法的时间复杂度。 实验结果表明,在云上并行实施PPI算法可以有效地处理大高光谱数据并加速算法。 :copyright:2016...
  • 但难以进行算法描述、设计和分析。 5、BSP模型中参数的意义P19 BSP模型以三个参数描述分布式存储的多计算模型。三个参数: 处理机(P) 处理机之间的点对点通信的选路器(g) 执行以时间间隔L为周期的路障同步器(L...
  • 该方法先去除噪声, 提取振动信号的相关信息, 再进行SFF以得到具有准确描述能力的特征向量, 最后采用概率神经网络(PNN)算法进行学习和分类。利用不同单一振动信号和风雨天气干扰下的不同振动信号对该方法进行验证。...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 46,931
精华内容 18,772
关键字:

串行算法的描述