adaboost算法

输入：训练数据集 $T = \{(x_1,y_1),(x_2,y_2),\ldots,(x_N,y_N), with \ x_i \in R^1, y_i \in \{-1,+1\}\}$
输出：最终分类器 $G_{final}(x)$

初始化样本的权值分布$ D = (w_{11}, \ldots, w_{1i}, \ldots, w_{1N}), w_{1i} = {1 \over N}, i=1, 2, \ldots, N, N $表示样本个数;
计算候选的切分点序列 $ S=(S_1, S_2, \ldots, S_{N-1}) $，默认是取特征的相邻两个值的平均值;
采用树桩作为基本的弱分类器，从$S$中选择使得在训练数据集上分类误差率最小的切分点建立基本分类器$G_j(x):x \rightarrow \{-1, 1\}$,同时记录其分类误差率$e_j$;
计算基本分类器$G_j(x)$的权重系数$ \alpha = {1 \over 2} log ({{1 - e_j} \over e_j})$ ;
更新训练样本的权值分布: $ w_{2i} = { w_{1i} \over Z } exp(-\alpha y_i G_j(x_i)) $,其中$Z$是一个归一化因子;
构建最终分类器$G_{final}(x) = sign (\sum{\alpha G_j(x)})$
判断是否满足精度要求或者达到最大迭代次数。如果是，则返回第3步;否则，输出最终分类器$G_{final}(x)$

算法实现

样本初始化

如果训练样本的类标签是大致均匀的话，则一般采用算法中默认的初始化方法；但类别不平衡时，需要不同的初始化方法。例如：$A,B,C$类样本数量分别为1000,200,100,则可以采用如下方法：
$$ sample \ weight = \left\{ \begin{array}{rcl} A \ class & {{1 \over 3} \times {1 \over 1000} }\\ B \ class & {{1 \over 3} \times {1 \over 200} }\\ C \ class & {{1 \over 3} \times {1 \over 100} } \end{array} \right. $$

候选的切分点序列

这里只考虑数值型特征的切分点选择，特征的值从小到大排序后将相邻值的平均值作为候选切分点；

基本弱分类器的构建

对于每一个切分点，对应大于该切分点取正类和小于该切分点取正类存在相应的两种弱分类器，在R实现的时候通过“UP”和“DOWN”两个字符串来区分它们。后面从存储空间上考虑，用Python实现时只用了一个逻辑位来区分这两种情况；

最佳基本分类器的选择

在R语言实现的版本中，每个切分点的两种弱分类器的误分类率都存储在向量(vector)中，该向量的前后半部分分别存储两个弱分类器的error rate，通过最小误分类率所在的位置来判断应该选择哪种弱分类器。
在Python的版本中，因为考虑到其实同一个切分点对应的两个弱分类器的误分类率之和必为1，因此只记录其中一个分类器的误分类率，那么如何选择最佳切分点以及正确的那个弱分类器呢？
假设某个切分点对应的两个弱分类器的误差率分别为$x,1-x$，则$|x - (1-x)| = |2x-1|$最大值对应的切分点是最佳切分点，而该最佳切分点上正确的弱分类器则通过与$1 \over 2$比较来确定；

代码链接

具体的python和R代码放在我的github，代码的注释比较详细，欢迎大家提出建议！