经过前面对AdaBoost的总结，下面要基于Matlab实现AdaBoost-Stump进行二维平面数据点的分类的实验。
一. 实验原理
参看 http://blog.csdn.net/lg1259156776/article/details/46831191
<boosting：三个臭皮匠赛过诸葛亮，adaptive：逐步（级联）>
二. 实验方法
生成一个可以利用sine线进行分割的数据点样本，然后通过AdaBoost – decision stump对数据点进行学习，最后得出能够将数据点样本进行分类的分割线。如下图所示：
实际上就是将一堆（T个）decision stump进行vote，然后得到一个比较复杂的分界线，实际上就是对实现利用阶跃函数对正弦函数进行逼近的。
<1> 生成training data 和 testing data : GenerateTrainDataSet
随机生成0-2pi之间数作为x1，随机生成0-4之间的数作为x2，设定的最理想的x2 = sin(x1) + 2，通过判定point(x1,x2)在曲线的上下方来给定标记y，如果在上方则为1，如果在下方则为0。
% ========================================================================
% 功能：生成具有正弦分界线的training data set
%
function [TrainData, TestData] = GenerateTrainDataSet(nTrainSize, nTestSize)
TrainData = zeros(nTrainSize,3);
TestData = zeros(nTestSize,3);
figure;
hold on;
%生成training data
title('training data')
for m = 1 : nTrainSize;
TrainData(m,1) =2 * pi * rand(); % 1 对应x1
%TrainData(m,2) = sin(TrainData(m,1)) + rand() - 0.5; % 2 对应x2
TrainData(m,2) = 4 * rand();
if(TrainData(m,2) >= sin(TrainData(m,1)) + 2) % 3 对应y
TrainData(m,3) = 1;
plot(TrainData(m,1),TrainData(m,2),'*b','MarkerSize',10);
hold on;
else
TrainData(m,3) = 0;
plot(TrainData(m,1),TrainData(m,2),'or','MarkerSize',10);
hold on;
end;
end;
%生成testing data
figure;
hold on;
title('testing data')
for m = 1 : nTestSize;
TestData(m,1) =2 * pi * rand(); % 1 对应x1
%TrainData(m,2) = sin(TrainData(m,1)) + rand() - 0.5; % 2 对应x2
TestData(m,2) = 4 * rand();
if(TestData(m,2) >= sin(TestData(m,1)) + 2) % 3 对应y
TestData(m,3) = 1;
plot(TestData(m,1),TestData(m,2),'*b','MarkerSize',10);
hold on;
else
TestData(m,3) = 0;
plot(TestData(m,1),TestData(m,2),'or','MarkerSize',10);
hold on;
end;
end;
下图是生成的训练样本，N = 500
下图是生成的测试数据集，N = 100
<2> 设计演算法对training data进行学习
根据AdaBoost原理，对于learning algorithm A来讲，minimize Error时不用特别的费劲选择Error最小的，只要我们能够选出加权分类error < 0.5 的分类器g(k)就可以了。因此在设计decision stump ： Hypothesis h = s * sign(X(i) – theta)时，对于其中的三个参数(feature i, threshold theta, direction s）采用了随机均匀获得的方式，同时满足error比乱猜（丢硬币）要小就行。下面就是decision
stump的详细代码：
%=========================================================================%
% decision stump 模型
% 输入：（X，y, u) (re-weighted error : u)，(X,y) data set (supervised)
% u(i)标记X(i)的权重，或者是bootstrap中样本点采样次数的归一化结果
% 输出(feature i, threshold theta, direction s, error, label[n]):
% label[n]标记每个数据点分类是否犯错，犯错了标记为1，正确标记为0
% 构成Hypothesis h = s * sign(X(i) - theta)
% s为direction，s = +1表示xi>theta为输出标记为+1，s = -1 表示xi<theta输出+1
% i表示某个维度，decision stump通常只选择某一维度进行分割，类似水平线和竖直线
% theta代表分割阈值
% 下面秉持一种信念尝试一下：只要找到比随机猜要好的h就可以了
% 算法思路：随机选取 feature_i，direction s和threshold theta，计算加权误差
% 反复迭代直到error < 0.5 (比随机乱猜好一点，weak classifier)即可
%=========================================================================%
function [feature_i, theta, s , error, label] = decison_stump(X, y, u)
while(1)
if(rand()>0.5) feature_i = 1;else feature_i = 2; end; %随机选取feature i
if(rand()>0.5) s = 1;else s = -1; end; %随机选取direction s
theta = ( max(X(:,feature_i)) - min(X(:,feature_i)) ) * rand() + min(X(:,feature_i)); %随机选取direction s error = 0; for n = 1 : length(X(:,feature_i));
if(s == 1) % 大于为1，小于为0
label(n) = 1 - ( (X(n,feature_i) >= theta) == y(n) ); %犯错了标记为1，正确标记为0
error = error + u(n) * label(n);
else
label(n) = 1 - ( (X(n,feature_i) <= theta) == y(n) );
error = error + u(n) * label(n) ;
end; end; if( error < 0.5 )
break;
end;end
之后就是AdaBoost中重要的一环：更新bootstrap中的数据re-sample的权重u，当然是根据实验原理中的步骤进行，将分类错误的点的重采样权重提高，再次训练decision stump，因为这种更新方式一方面从data diversity上保证了g的多样性，另一方面，通过调整犯错的点的采样权重，使得g(k)在采样权重u(k+1)的样本data上的分类错误与随机乱猜一样，从而保证了g(k)与g(k+1)的不同，也是diversity的一种设计。下面是adaboost的详细代码：
%=========================================================================%
% adaboost，实现对u的调节，以及后续的vote（decision stump 的融合）
% 实际上是完成了bootstrap，对数据进行re-sample，得到放大错误分类数据的u
% 输入：u_0(u(k)), error(gk对应的分类误差), label(data是否分类错误的标签)
% 输出：u_1(u(k+1)), alpha(gk对应的融合权重)
% error = 0.5, 则delta = 1,alpha() = 0,随机猜测的g的权重为0
% error = 0，则delta = ∞,alpha() = ∞,有理由让完全分类对的g的权重为∞
%=========================================================================%
function [u_1, alpha] = my_adaboost(u_0, error, label)
N = length(label); %数据大小
delta = sqrt((1-error)/error);
for n = 1 : N
if(label(n) == 1) u_1(n) = u_0(n) * delta; else u_1(n) = u_0(n) / delta; end;
end;
alpha = log(delta);
最后就是设计实验进行训练和测试，具体的解释见代码注释：
%=========================================================================%
% 利用生成的training data和testing data对AdaBoosting decision stump进行学习
% 设置在同一数据集下的演示测试为tTimes: 训练的迭代次数自增100，初始为T = 100
% 观察在同一个数据集下不同迭代次数AdaBoost融合的G在test集上的分类正确率
% 流程：生成数据集，开启循环训练-测试，并输出分类效果%%
% 生成数据集并初始化参数
nTrainSize = 1000;
nTestSize = 100;
[TrainData, TestData] = GenerateTrainDataSet(nTrainSize, nTestSize);
tTimes = 10;
T = 0;
f = fopen('Testing Results.txt','w');
%%
% 开启tTimes次训练和测试
for times = 1 : tTimes;
T = T + 100;
u0 = 1/nTrainSize * ones(1, nTrainSize); % 初始化bootstrap采样权重为均匀分布
X = TrainData(:,1:2); % 提取输入X
y = TrainData(:,3); % 提取标签y
g_set = zeros(4, T); % 初始化g_set集合：存储decision stump的参数（feature_i,theta,s）,再存入一个error性能
label = zeros(1, nTrainSize); % data 分类错误标签
alpha = zeros(1, T); % g_set融合权重
%%
% 主循环迭代训练得到g_set，alpha
for n = 1 : T;
[g_set(1,n) g_set(2,n) g_set(3,n) g_set(4,n) label] = ...
decision_stump(X, y, u0);
[u_1, alpha(n)] = my_adaboost(u0, g_set(4,n), label);
u0 = u_1;
end;
%%
% 如何把这个g的融合边界绘制出来才是问题的关键所在
% 不如直接进行测试算了
% 直接利用训练得到的g_set和alpha对testing data进行测试，求出分类正确率 X = TestData(:,1:2);
y = TestData(:,3);
vote = zeros(1, nTestSize); % X = TrainData(:,1:2);
% y = TrainData(:,3);
% vote = zeros(1, nTrainSize); sucess_rate = 0;
%%
% vote , aggregation, adaboost
for m = 1 : T;
feature_i = g_set(1,m); theta = g_set(2,m); s = g_set(3,m);
for n = 1 : length(X(:,feature_i));
if(s == 1) % 大于为1，小于为0
label(n) = ( (X(n,feature_i) >= theta) ); % 犯错了标记为1，正确标记为0
else
label(n) = ( (X(n,feature_i) <= theta) );
end;
vote(n) = vote(n) + alpha(m) * label(n)/sum(alpha); % 利用归一化的alpha进行加权融合
%vote(n) = vote(n) + 1/T * label(n); % 利用无权重的融合效果经测试不好
if(m == T)
sucess_rate = sucess_rate + ((vote(n)>0.5) == y(n));
end;
end;
end;
fprintf('第%d次训练的g_set集大小为%d，测试数据分类成功率为%f\n',times,T,sucess_rate/nTestSize);
% display('测试数据分类成功率为：');
% display(sucess_rate/nTestSize);
end;
fclose(f);
三. 实验结果
adaboost_decision_stump_test
第1次训练的g_set集大小为100，测试数据分类成功率为0.870000
第2次训练的g_set集大小为200，测试数据分类成功率为0.870000
第3次训练的g_set集大小为300，测试数据分类成功率为0.930000
第4次训练的g_set集大小为400，测试数据分类成功率为0.940000
第5次训练的g_set集大小为500，测试数据分类成功率为0.940000
第6次训练的g_set集大小为600，测试数据分类成功率为0.960000
第7次训练的g_set集大小为700，测试数据分类成功率为0.890000
第8次训练的g_set集大小为800，测试数据分类成功率为0.970000
第9次训练的g_set集大小为900，测试数据分类成功率为0.950000
第10次训练的g_set集大小为1000，测试数据分类成功率为0.930000
四 分析与讨论
从实验结果中可以看出，虽然每一个decision stump单独工作进行分类的误差仅仅比随即乱猜要好一些，但是经过AdaBoost的设计，我们得到一系列的diversity的decision stump: g，通过aggregation将其融合，从而得到一个较强的分类器。（weak classifier -> strong classifier）从而实现了“三个臭皮匠赛过诸葛亮”的预言。
另外，值得进一步去完善的地方是：本次实验程序并没有将构造出来的分类器分割边界绘制出来，所以没能很形象的展示出利用AdaBoost + decision stump能够实现对复杂非线性函数的逼近、拟合的能力。而通过测试结果不难想象出分类边界的模样。
有兴趣的可以进一步编写函数把整个融合后的G的分割边界绘制出来，形成第一幅图进行演示的效果！
*************************************************随时记录，随时分享****************************************************
