算法思想

Adaboost是一种集成学习(Ensemble)思想的算法。在之前，没有一种方法可以使得弱分类器有效的变为强分类器，后面集成学习的出现解决了这一问题，可以使得弱分类器变为强分类器。集成学习主要可以分为两个方法：Sequential Method和Parallel Method，其中Sequential Method中最为基础的代表便是Adaboost。该算法的核心思想如下图。

Adaboost相比于原始决策树具有以下优势：

1. Adaboost是一种精度非常高的分类器；

2. 可以与各种方法构建子分类器，Adaboost算法提供一种计算框架；

3. 弱分类器的构造方法比较简单；

4. 算法易于理解，不用做特征筛选；

5. 不易发生过拟合；

6. 易于编码（和奥卡姆剃刀有悖）。

Adaboost算法伪代码如下：

writage过期了，所以word转公式特别麻烦QAQ。。就直接用图片啦，不知道有一天图床崩了会引起什么反应

后面我又用latex输了

balabala 不想贴了，不过这里补一个报告pdf

我们这里讲解Adaboost是如何解决上一节这4个问题的。

假设我们的训练集样本是

$$
T={(x,y1),(x2,y2),…(xm,ym)}
$$
训练集的在第k个弱学习器的输出权重为
$$
D(k)=(wk1,wk2,…wkm);w1i=1m;i=1,2…m
$$
Adaboost的误差率和其他分类误差率相似，由于多元分类是二元分类的推广，在这里假设是二元分类问题，输出为{-1，1}，则第k个弱分类器Learner k的加权误差率为：
$$
e_k = P(G_k(x_i) \neq y_i) = \sum\limits_{i=1}^{m}w_{ki}I(G_k(x_i) \neq y_i)
$$
Adaboost的第k个分类器的权重系数为：
$$
\alpha_k = \frac{1}{2}log\frac{1-e_k}{e_k}
$$
从误差率公式和权重系数公式可以看出分离误差率越大,ak越小。假设第k个弱分类器的样本集权重系数为
$$
D(k) = (w_{k1}, w_{k2}, …w_{km})
$$
需要得到第k+1个权重系数，对应第k+1个权重系数为：
$$
w_{k+1,i} = \frac{w_{ki}}{Z_K}exp(-\alpha_ky_iG_k(x_i))
$$
上式的规范化因子的计算的计算如下：
$$
Z_k = \sum\limits_{i=1}^{m}w_{ki}exp(-\alpha_ky_iG_k(x_i))
$$
如图中所示，多个弱学习器还需要一个集合函数将他们合成一个，Adaboost采用的是加权表示法，最终的强分类器为：
$$
f(x) = sign(\sum\limits_{k=1}^{K}\alpha_kG_k(x))
$$
分类Adaboost的弱学习器权重系数公式和样本权重更新公式的确定，和从Adaboost的损失函数有关，Adaboost是模型为加法模型，学习算法为前向分步学习算法，损失函数为指数函数的分类问题。加法模型是指最终的强分类器是若干个弱分类器加权平均而得到的，前向分步学习算法是通过一轮轮的弱学习器学习，利用前一个强学习器的结果和当前弱学习器来更新当前的强学习器的模型。第k-1轮的强学习器为：
$$
f_{k-1}(x) = \sum\limits_{i=1}^{k-1}\alpha_iG_{i}(x)
$$
而第k轮的强学习器为：
$$
f_{k}(x) = \sum\limits_{i=1}^{k}\alpha_iG_{i}(x)
$$
上两式一比较可以得到
$$
f_{k}(x) = f_{k-1}(x) + \alpha_kG_k(x)
$$
可见强学习器的确是通过前向分步学习算法一步步而得到的。

代码

class MyAdaBoost(BaseEstimator,ClassifierMixin):
   
    def __init__(self,weak_clf=None,n_estimator=50):
        self._clfs=[] # 弱分类器的列表
        self._clf_weight=[] # 权重列表
        self._weak_clf=weak_clf # 弱学习器选择
        self._n_estimator=n_estimator # 最大基学习器数量
        
    def get_para_ts(self, deep = False):  
        return{  
            "weak_clf": self._weak_clf,  
            "n_estimator": self._n_estimator,  
        }  

    def clear(self):  
        self._clfs.clear()  
        self._clf_weight.clear()
  
        
    def fit(self, X, y):
        self.clear()

        n=len(X)
        # 计算第一个权重
        # 此后的权重通过计算迭代的得到，见权重计算公式
        avg_weight=np.ones(n) / n
      
        # 基学习器的最大数量self.n_estimator为迭代次数       
        for i in range(self._n_estimator):
            
            # 使用弱分类器的fit方法训练弱分类器
            self._weak_clf=self._weak_clf.fit(X, y,sample_weight=np.array(avg_weight))
            
            # 调用弱分类器的predict方法进行预测
            y_pred=self._weak_clf.predict(X)
            
            # 计算加权错误率e_k
            # 公式如上文e_k的计算，这里考虑到数值的稳定性
            eps = 1e-12  
            e_k = min(max((y_pred != y).dot(avg_weight[:, None])[0], eps), 1 - eps)
            
            # 计算该弱分类器的权重a_t
            # 在公式中反映为 1/2*log{(1-e_k)/e_k}
            a_t=0.5 * np.log((1 - e_k) / (e_k))  
            
            # 更新样本权重
            #通过第k+1个权重公式得到
            avg_weight *= np.exp(-a_t * y* y_pred)
            avg_weight /= np.sum(avg_weight)
            
            # 记录分类器和权重
            self._clf_weight.append(a_t)
            self._clfs.append(deepcopy(self._weak_clf))
        return self
            
    def predict(self,x):
        result=np.zeros(len(x))
        
        # 集合函数
        # 按权重求和
        for clf, a_t in zip(self._clfs, self._clf_weight):
            result += a_t * clf.predict(x) 
        # 将结果化为1 0 -1
        result-=0.5
        prediction = np.sign(result)
        prediction[prediction == -1] = 0
        return prediction

# 检测Adaboost的树深从8-12的代码
from sklearn.tree import DecisionTreeClassifier
from sklearn.model_selection import cross_val_predict
from sklearn.metrics import *
for i in range(8,13):
    clf=DecisionTreeClassifier(max_depth=i)# 最大深度
    AdaBoostClf=MyAdaBoost(weak_clf=clf)
    AdaBoostClf.fit(dota2x,dota2y)
    prediction1=AdaBoostClf.predict(dota2x)
    from sklearn.metrics import mean_absolute_error
    from sklearn.metrics import mean_squared_error
    print(i,":",mean_absolute_error(dota2y,prediction1),mean_squared_error(dota2y,prediction1))