专栏首页算法与数据之美手写一个简单的提升算法AdaBoost

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

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

提升方法

  • 提升方法的主要思想就是“三个臭皮匠顶一个诸葛亮”。对于一个复杂任务来说,将多个人的判断进行进行适当的综合所得出的判断,要比参与判断的任何一个人单独判断效果要好。
  • 在PAC(概率近似正确(PAC, Probably approximately correct))学习框架下,一个概念是强可学习的充分必要条件是这个概念是弱可学习的,对应于上述的综合判断和单独判断,是由Schapire证明的。
  • 提升方法的两个问题
  1. 在每一轮如何改变训练数据的权值或概率分布
  2. 如何将弱分类器组合成一个强分类器
  • Adaboost的解决方案:
  1. 提高那些被前一轮弱分类器错误分类样本的权值,降低那些被正确分类的样本的权值
  2. 加权多数表决的方法,加大分类误差率小的弱分类器的权值,减小分类误差率大的弱分类器

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)

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

程序运行之后的结果:

利用三个弱分类器的组合,得到了最终的分类器,实现了对数据集的正确分类。

喜欢就点个赞吧❤

本文分享自微信公众号 - 算法与数据之美(algo_and_data),作者:斐波那契小李

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-07-23

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 用Python做一个久坐提醒小助手

    整体的构思类似于一个番茄时钟,提供一个倒计时功能并且在完成计时时发出警告。主要分为如下几个模块,一是时间选择模块,二是按钮模块,控制计时开始、暂停以及恢复,三是...

    老肥码码码
  • JS逆向之猪场某游

    下图是收藏榜总榜的部分商品,一看这金额???果然是有钱人玩的游戏啊,到底是什么样的属性能让其价值连城?鼠标放到装备图标上,我们可以看到装备的详细信息,那么如何抓...

    老肥码码码
  • 什么是AlexNet?

    对于CNN(卷积神经网络)最早可以追溯到1986年BP算法的提出,然后1989年LeCun将其用到多层神经网络中,直到1998年LeCun提出Le...

    老肥码码码
  • 移动端开发人员调试H5

    程序员不务正业
  • 反运算(简单的定制)[第十七章]

    关于反运算,这里要注意一点;对于a + b,b的__radd__(self,other),中other是a的对象,self才是b的对象

    天钧
  • 为你的好朋友添点评论

    想要为朋友来点评论就需要知道他的博客域名、appId、appKey和他所使用的机器是哪个地区的。

    Dreamy.TZK
  • IOS 自定义UITableViewCell 常用

    用户5760343
  • 深度强化学习之DQN实战

    今天我们会将我们上一篇文章讲解的DQN的理论进行实战,实战的背景目前仍然是探险者上天堂游戏,不过在下一次开始我们会使用OpenAI gym的环境库,玩任何我们想...

    CristianoC
  • ReactiveCocoa使用心得

    5.NSMutableArray 因为NSMutableArray不支持KVO,所以用另外一个方式处理:

    freesan44
  • PyQt5--TextDrag

    py3study

扫码关注云+社区

领取腾讯云代金券