机器学习算法:AdaBoost

举报
技术火炬手 发表于 2018/08/29 09:41:14 2018/08/29
【摘要】 AdaBoost算法(Adaptive Boost)的核心思想是:如果一个弱分类器的分类效果不好,那么就构建多个弱分类器,综合考虑它们的分类结果和权重来决定最终的分类结果。很多人认为AdaBoost是监督学习中最强大的两种算法之一(另一个是支持向量机SVM)。AdaBoost的训练过程如下:为每个训练样本初始化相同的权重;针对训练样本及权重,找到一个弱分类器;计算出这个弱分类器的错误率ε与权...

AdaBoost算法(Adaptive Boost)的核心思想是:如果一个弱分类器的分类效果不好,那么就构建多个弱分类器,综合考虑它们的分类结果和权重来决定最终的分类结果。很多人认为AdaBoost是监督学习中最强大的两种算法之一(另一个是支持向量机SVM)。

AdaBoost的训练过程如下:

  1. 为每个训练样本初始化相同的权重;

  2. 针对训练样本及权重,找到一个弱分类器;

  3. 计算出这个弱分类器的错误率ε与权重α

  4. 对正确分类的样本,降低其权重,对错误分类的样本,提升其权重;

  5. 返回2不断迭代,直至弱分类器数量足够;

其中错误率ε定义为分错的样本数除以总样本数。权重α定义为:

wKioL1Ra2T6C1zzVAAAVvb2J73M988.jpg


权重提升与降低的公式如下:

wKioL1Ra2WGjZrI_AABIehALMaw618.jpg

对未知样本分类时,用每个弱分类器进行分类,将结果乘以这个分类器的权重α,累加到一起得到一个猜测值,根据其正负决定最终输出1还是-1。注意AdaBoost只能解决二分类问题,如果多于2个分类,需要做一定变通。

在AdaBoost中,广泛使用单层决策树(Decision Stump)作为弱分类器。之前研究ID3算法的决策树时,样本特征是离散型数据,这回研究连续型数据,因此之前的方法就不可用了,需要基于边界比较来确定分类。另外需要注意要同时考虑权重D来决定最佳切分方式。基本思路如下:

foreach(每一个维度){
    在此维度最大最小值之间切出N个边界    foreach(每一个边界)
    {
        针对"<="与">"两种情况        {
            获取此条件下的分类结果(满足记为1,不满足记为-1)            foreach(每一个结果)
            {
                if(猜测错误)
                    累加加权错误率            }
            保留最小加权错误率的切分方式        }
    }}

由于只在一个维度上切分一次,可以想像单层决策树的错误率应该相当高,是典型的弱分类器。但是综合考虑它们的结果及权重,最终的分类错误率可以做到大大低于单个单层决策树。上完整C#版AdaBoost的实现代码:

首先是DataVector,之前Label一直是字符串,这回要出现1和-1了,因此改造一下,使Label的类型可定义:

using System;namespace MachineLearning{
    /// <summary>
    /// 数据向量
    /// </summary>
    /// <typeparam name="TData">特征类型</typeparam>
    /// <typeparam name="TLabel">标签数据</typeparam>
    public class DataVector<TData, TLabel>
    {
        /// <summary>
        /// N维数据
        /// </summary>
        public TData[] Data { get; private set; }
        /// <summary>
        /// 分类标签
        /// </summary>
        public TLabel Label { get; set; }
        /// <summary>
        /// 构造
        /// </summary>
        /// <param name="dimension">数据维度</param>
        public DataVector(int dimension)
        {
            Data = new TData[dimension];
        }
        /// <summary>
        /// 维度数量
        /// </summary>
        public int Dimension        {
            get { return this.Data.Length; }
        }
    }}

然后是一个存储单层决策树的结构:

using System;using System.Collections.Generic;namespace MachineLearning{
    /// <summary>
    /// 单层决策树
    /// </summary>
    public class DecisionStump    {
        /// <summary>
        /// 分类器权重
        /// </summary>
        public double Alpha { get; set; }
        /// <summary>
        /// 加权错误率
        /// </summary>
        public double Error { get; set; }
        /// <summary>
        /// 在哪个维度上切分
        /// </summary>
        public int Dimension { get; set; }
        /// <summary>
        /// 切分边界
        /// </summary>
        public double Boundary { get; set; }
        /// <summary>
        /// 是否按大于来切分
        /// </summary>
        public bool GreaterThan { get; set; }
        /// <summary>
        /// 此分类器在训练数据集上的分类结果
        /// </summary>
        public List<int> Results { get; set; }
    }}

最后是AdaBoost:

using System;using System.Collections.Generic;using System.Linq;namespace MachineLearning{
    /// <summary>
    /// AdaBoost(基于单层决策树)
    /// </summary>
    public class AdaBoost    {
        /// <summary>
        /// 弱分类器列表
        /// </summary>
        private List<DecisionStump> m_WeakClassifiers;
        
        /// <summary>
        /// 训练
        /// </summary>
        /// <param name="trainingSet">训练数据集</param>
        /// <param name="iterateCount">迭代次数,即弱分类器数量</param>
        public void Train(List<DataVector<double, int>> trainingSet, int iterateCount = 50)
        {
            m_WeakClassifiers = new List<DecisionStump>();
            
            var D = new List<double>();
            var gue***esults = new List<double>();
            for(int i = 0;i < trainingSet.Count;++i)
            {
                //权重初始化为1/n
                D.Add(1.0 / trainingSet.Count);
                //猜测结果初始化为0,后面累加要用
                gue***esults.Add(0.0);
            }
            
            //迭代指定次数
            for(int i = 0;i < iterateCount;++i)
            {
                //在当前权重下生成一棵错误率最低的单层决策树
                var stump = CreateDecisionStump(trainingSet, D);
                
                //计算Alpha(注意stump.Error有可能为0,要防止除0错误)
                stump.Alpha = 0.5 * Math.Log((1 - stump.Error) / Math.Max(stump.Error, 1e-16));
                
                //保存这个决策树到弱分类器
                m_WeakClassifiers.Add(stump);
                
                //根据猜测结果,重新计算下一轮的权重向量D(暂时未除以Sum(D),下一步再处理)
                for(int j = 0;j < trainingSet.Count;++j)
                {
                    if(stump.Results[j] == trainingSet[j].Label)
                        D[j] = D[j] * Math.Exp(-1.0 * stump.Alpha);
                    else
                        D[j] = D[j] * Math.Exp(stump.Alpha);
                }
                
                //保证Sum(D)==1
                double sum = D.Sum();
                for(int j = 0;j < trainingSet.Count;++j)
                {
                    D[j] = D[j] / sum;
                    gue***esults[j] += stump.Alpha * stump.Results[j];
                }
                
                //计算总错误率
                int errors = 0;
                for(int j = 0;j < trainingSet.Count;++j)
                {
                    if(Math.Sign(gue***esults[j]) != trainingSet[j].Label)
                        ++errors;
                }
                
                //如果没有错误,可以提前退出循环,但一般很难达到
                if(errors == 0)
                    break;
            }
        }
        
        /// <summary>
        /// 分类
        /// </summary>
        /// <param name="vector">待测数据</param>
        /// <returns>分类结果,1或-1</returns>
        public int Classify(DataVector<double, int> vector)
        {
            double result = 0.0;
            var dataSet = new List<DataVector<double, int>>();
            dataSet.Add(vector);
            
            //用每一个弱分类器的结果乘以相应的alpha,累加得到最终的猜测结果
            foreach(var c in m_WeakClassifiers)
            {
                var stumpResults = ClassifyByDecisionStump(dataSet, c.Dimension, c.Boundary, c.GreaterThan);
                result += stumpResults[0] * c.Alpha;
            }
            
            //根据正负决定输出1还是-1
            return Math.Sign(result);
        }
        
        /// <summary>
        /// 根据单层决策树进行一次分类
        /// </summary>
        /// <param name="dataSet">数据集</param>
        /// <param name="dimension">在哪个维度上分类</param>
        /// <param name="boundary">分类边界</param>
        /// <param name="greaterThan">是否按大于来划分数据</param>
        /// <returns>结果</returns>
        private List<int> ClassifyByDecisionStump(List<DataVector<double, int>> dataSet, int dimension, double boundary, bool greaterThan)
        {
            var result = new List<int>();
            foreach(var item in dataSet)
            {
                if(greaterThan)
                    result.Add(item.Data[dimension] > boundary ? 1 : -1);
                else
                    result.Add(item.Data[dimension] <= boundary ? 1 : -1);
            }
            
            return result;
        }
        
        /// <summary>
        /// 构建一个单层决策树
        /// </summary>
        /// <param name="dataSet">数据集</param>
        /// <param name="D">权重</param>
        /// <returns>此权重下的最佳单层决策树</returns>
        private DecisionStump CreateDecisionStump(List<DataVector<double, int>> dataSet, List<double> D)
        {
            var stump = new DecisionStump();
            double minError = double.PositiveInfinity;
            
            //遍历每一个维度
            for(int i = 0;i < dataSet[0].Dimension;++i)
            {
                //找此维度的最大最小值
                double maxValue = double.NegativeInfinity;
                double minValue = double.PositiveInfinity;
                
                foreach(var item in dataSet)
                {
                    if(item.Data[i] > maxValue)
                        maxValue = item.Data[i];
                    if(item.Data[i] < minValue)
                        minValue = item.Data[i];
                }
                
                //做10次切分,计算步长
                double stepSize = (maxValue - minValue) / 10.0;
                for(int j = 0;j < 10;++j)
                {
                    //边界
                    double boundary = minValue + stepSize * j;
                    
                    //分别计算边界两边的情况
                    for(int k = 0;k < 2;++k)
                    {
                        var results = ClassifyByDecisionStump(dataSet, i, boundary, k == 0);
                        
                        //计算错误,注意是加权的错误
                        double weightError = 0.0;
                        for(int idx = 0;idx < results.Count;++idx)
                        {
                            if(results[idx] != dataSet[idx].Label)
                                weightError += D[idx];
                        }
                        
                        //保留最小错误的分类器
                        if(weightError < minError)
                        {
                            minError = weightError;
                            stump.Error = Math.Min(weightError, 1.0);        //此分类器的错误比例
                            stump.Boundary = boundary;                       //分类边界
                            stump.Dimension = i;                             //在哪个维度上分类
                            stump.GreaterThan = false;                       //大于还是小于
                            stump.Results = results;                         //用此分类器得出的结果
                        }
                    }
                }
            }
            
            return stump;
        }
    }}

最后上测试,还是使用上次的breast-cancer-wisconsin.txt做测试,顺便也和kNN对比一下。上测试代码:

public void TestAdaBoost(){
    var trainingSet = new List<DataVector<double, int>>();
    var testSet = new List<DataVector<double, int>>();
    
    //读取数据
    var file = new StreamReader(@"breast-cancer-wisconsin.txt", Encoding.Default);
    for(int i = 0;i < 699;++i)
    {
        string line = file.ReadLine();
        var parts = line.Split(',');
        
        var p = new DataVector<double, int>(9);
        for(int j = 0;j < p.Dimension;++j)
        {
            if(parts[j + 1] == "?")
                parts[j + 1] = "0";
            p.Data[j] = Convert.ToDouble(parts[j + 1]);
        }
        p.Label = Convert.ToInt32(parts[10]) == 2 ? 1 : -1;
        
        //和上次一样,600个做训练,99个做测试
        if(i < 600)
            trainingSet.Add(p);
        else
            testSet.Add(p);
    }
    file.Close();
    
    //检验
    var boost = new AdaBoost();
    boost.Train(trainingSet);               //默认50次迭代
    int error = 0;
    foreach(var p in testSet)
    {
        var label = boost.Classify(p);
        if(label != p.Label)
            error++;
    }
    
    Console.WriteLine("Error = {0}/{1}, {2}%", error, testSet.Count, (error * 100.0 / testSet.Count));}

最终结果是99个测试样本猜错1个,错误率1.01%,相当不错。

在Train方法中计算了错误率,可以把它同时也输出出来,另外改变不同的迭代次数,可以对比一下训练错误率与测试错误率:

弱分类器数量(迭代次数)训练错误率测试错误率
54.8%4.0%
104.7%2.0%
503.0%1.0%
1002.5%2.0%
2002.0%2.0%
5000.8%2.0%
10000.0%2.0%


可以看到,随着弱分类器越来越多,AdaBoost的训练错误率不断下降,最终收敛到0,但测试错误率在下降到最低点后又有所上升。


本文转自BoyTNT博客51CTO博客,如需转载,请自行联系原作者。

原文链接


【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。