AdaBoost算法（Adaptive Boost）的核心思想是：如果一个弱分类器的分类效果不好，那么就构建多个弱分类器，综合考虑它们的分类结果和权重来决定最终的分类结果。很多人认为AdaBoost是监督学习中最强大的两种算法之一（另一个是支持向量机SVM）。
AdaBoost的训练过程如下：
为每个训练样本初始化相同的权重；
针对训练样本及权重，找到一个弱分类器；
计算出这个弱分类器的错误率ε与权重α；
对正确分类的样本，降低其权重，对错误分类的样本，提升其权重；
返回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
{
///
/// 数据向量
///
///
///
public class DataVector
{
///
/// N维数据
///
public TData[] Data { get; private set; }
///
/// 分类标签
///
public TLabel Label { get; set; }
///
/// 构造
///
/// 数据维度
public DataVector(int dimension)
{
Data = new TData[dimension];
}
///
/// 维度数量
///
public int Dimension
{
get { return this.Data.Length; }
}
}
}
然后是一个存储单层决策树的结构：
using System;
using System.Collections.Generic;
namespace MachineLearning
{
///
/// 单层决策树
///
public class DecisionStump
{
///
/// 分类器权重
///
public double Alpha { get; set; }
///
/// 加权错误率
///
public double Error { get; set; }
///
/// 在哪个维度上切分
///
public int Dimension { get; set; }
///
/// 切分边界
///
public double Boundary { get; set; }
///
/// 是否按大于来切分
///
public bool GreaterThan { get; set; }
///
/// 此分类器在训练数据集上的分类结果
///
public List
}
}
最后是AdaBoost：
using System;
using System.Collections.Generic;
using System.Linq;
namespace MachineLearning
{
///
/// AdaBoost(基于单层决策树)
///
public class AdaBoost
{
///
/// 弱分类器列表
///
private List
///
/// 训练
///
/// 训练数据集
/// 迭代次数，即弱分类器数量
public void Train(List
{
m_WeakClassifiers = new List
var D = new List
var gue***esults = new List
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;
}
}
///
/// 分类
///
/// 待测数据
///
public int Classify(DataVector
{
double result = 0.0;
var dataSet = new List
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);
}
///
/// 根据单层决策树进行一次分类
///
/// 数据集
/// 在哪个维度上分类
/// 分类边界
/// 是否按大于来划分数据
///
private List
{
var result = new List
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;
}
///
/// 构建一个单层决策树
///
/// 数据集
/// 权重
///
private DecisionStump CreateDecisionStump(List
{
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
var testSet = new List
//读取数据
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
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方法中计算了错误率，可以把它同时也输出出来，另外改变不同的迭代次数，可以对比一下训练错误率与测试错误率：
可以看到，随着弱分类器越来越多，AdaBoost的训练错误率不断下降，最终收敛到0，但测试错误率在下降到最低点后又有所上升。