手写一个简单的提升算法AdaBoost

老肥码码码

发布于 2020-01-17 11:22:50

4260

发布于 2020-01-17 11:22:50

文章被收录于专栏：算法与数据之美算法与数据之美

提升方法是一种常用的统计学习方法，应用广泛并且有效。很多机器学习的库都对该方法进行了封装，调用它们也相对容易。而通过自己手写一个算法能让自己加深对算法的理解。

提升方法

提升方法的主要思想就是“三个臭皮匠顶一个诸葛亮”。对于一个复杂任务来说，将多个人的判断进行进行适当的综合所得出的判断，要比参与判断的任何一个人单独判断效果要好。
在PAC（概率近似正确(PAC, Probably approximately correct)）学习框架下，一个概念是强可学习的充分必要条件是这个概念是弱可学习的，对应于上述的综合判断和单独判断，是由Schapire证明的。
提升方法的两个问题

在每一轮如何改变训练数据的权值或概率分布
如何将弱分类器组合成一个强分类器

Adaboost的解决方案：

提高那些被前一轮弱分类器错误分类样本的权值，降低那些被正确分类的样本的权值
加权多数表决的方法，加大分类误差率小的弱分类器的权值，减小分类误差率大的弱分类器

AdaBoost算法

在上述算法中，步骤（1）假设训练数据集具有均匀的权值分布，即每个训练样本在基本分类器的学习中作用相同。

步骤（2）是AdaBoost反复学习弱分类器，先使用当前权值分布的训练数据集，学习一个弱分类器。再计算弱分类器再加权训练数据集的分类误差率，再计算弱分类器的系数α，然后更新训练数据的权值分布。

步骤（3）用线性组合f(x)实现了M个弱分类器的加权表决。

定义一个分类函数，该函数能够根据特征将数据进行分类，有两种分类方式。大于分类点的数值标记为1，小于分类点的数值标记为-1的是positive；

小于分类点的数值标记为1，大于分类点的数值标记为-1的是negative。返回在当前权值分布下的最优分类点以及分类方式等。里面很重要的一点，不改变所给训练数据而改变训练数据的权值分布。体现在计算分类误差率的部分。

def _classify(self,features,labels,weights):
        m=len(features)
        error=1.0           # 初始化误差率
        best_v=0.0          # 初始化分类结点
        # 单维特征
        feature_min=min(features)
        feature_max=max(features)
        # 需要的步骤数目
        n_step=(feature_max-feature_min+self.learning_rate)/self.learning_rate        
        direct,compare_array=None,None   # 初始化方式和结果数组
        for i in range(1,int(n_step)):
            v=feature_min+self.learning_rate*i
            if v not in features:
                # 计算在训练集上的分类误差率
                # 不改变所给的训练数据，但是不断改变数据权值分布
                compare_array_positive=np.array([1 if features[k]>v else -1 for k in range(m)])
                weight_error_positive=sum([weights[k] for k in range(m) if compare_array_positive[k]!=labels[k]])
                compare_array_negative=np.array([-1 if features[k]>v else 1 for k in range(m)])
                weight_error_negative=sum([weights[k] for k in range(m) if compare_array_negative[k]!=labels[k]])

                if weight_error_positive<=weight_error_negative:
                    weight_error=weight_error_positive
                    _compare_array=compare_array_positive
                    direct='positive'
                else:
                    weight_error=weight_error_negative
                    _compare_array=compare_array_negative
                    direct='negative'
                
                if weight_error<error:
                    error=weight_error
                    compare_array=_compare_array
                    best_v=v
        # print(best_v)
        return best_v,direct,error,compare_array

系数权值等的更新函数，严格按照算法的公式计算。

# 计算alpha
    def _alpha(self,error):
        return 0.5*np.log((1-error)/error)
    
    # 规范化因子
    def _Z(self,weights,a,clf):
        return sum([weights[i]*np.exp(-1*a*self.y[i]*clf[i]) for i in range(self.M)])
    
    # 权值更新
    def _w(self,a,clf,Z):
        for i in range(self.M):
            self.weights[i]=self.weights[i]*np.exp(-1*a*self.y[i]*clf[i])/Z

有了基本的弱分类器以及各种参数的更新方式，我们需要实现这些分类器的加权表决。可以在该分类器的组合已经正确完成对所有训练数据的分类时，停止训练。

def fit(self,X,y):
        self.init_args(X,y)
        
        for epoch in range(self.clf_num):
            best_v,final_direct,best_clf_error,clf_result=self._classify(self.X,self.y,self.weights)
            # 如果分类器已经完全分类，停止迭代
            if self.test()==1:
                break
            else:
                # 计算G(x)系数a
                a=self._alpha(best_clf_error)
                self.alpha.append(a)
                # 记录分类器
                self.clf_sets.append((best_v,final_direct))
                Z=self._Z(self.weights,a,clf_result)
                self._w(a,clf_result,Z)            
            print("已经训练完第{}个弱分类器，分类点为{}，分类方式为{},分类误差为{:.4f}，权重为{}"
                  .format(epoch+1,best_v,final_direct,best_clf_error,self.weights))

            
        print(self.clf_sets)
    
    def predict(self,feature):
        result=0.0
        for i in range(len(self.clf_sets)):
            clf_v,direct=self.clf_sets[i]
            result+=self.alpha[i]*self.G(feature,clf_v,direct)            
        return np.sign(result)

    def test(self):
        right_count = 0
        for i in range(len(self.X)):
            feature=self.X[i]
            if self.predict(feature)==self.y[i]:
                right_count += 1
        return right_count/len(self.X)

我们采用的数据集如下图所示：