ciwei020621的个人博客分享 http://blog.sciencenet.cn/u/ciwei020621

博文

[转载]boost实现

已有 2525 次阅读 2012-6-18 13:26 |个人分类:算法实现|系统分类:科研笔记|关键词:boost| boost |文章来源:转载

boost算法(草稿)(2011-12-16 21:53:54)
主要内容来自ijcai 1999, "A brief introduction to Boosting".

这篇论文介绍的是AdaBoost,一种简洁有效的算法。它的算法过程可以写成如下步骤:
1.输入是一群样本,形式如(x_1, y_1), (x_2, y_2),..., (x_i, y_i), ..., (x_m, y_m)。这里,x_i是多维的向量,y_i或者是-1,或者是1。当然,x_i可以是数值型的,也可以是字符型的,后话。

2. 初始化D_1(i) = 1/m。对每个样本都对应一个权重D,D_1(i),就表示第i个样本,在第1论训练里的权重。在第一轮训练的时候,权重设成相同的均值。

3. 假设训练进行T次,那么,对每次训练,设为t,按照如下步骤:
    3.1 根据D_t,训练弱分类器。
    3.2 根据3.1的弱分类器,会得到h_t: x->{-1, 1},此时,该分类器对训练样本的分类错误是
          e_t = 1/m*k 其中,k是使得h_t(x_i)!=y_i的样本的权重D的总和。
    3.3 a_t = 0.5*ln((1-e_t)/e_t)
    3.4 更新D:
        3.4.1 D_(t+1)(i) = D_t(i)/Z_t*e^(-a_t) if h_t(x_i) == y_i, D_(t+1)(i) = D_t(i)/Z_t*e^(a_t) if h_t(x_i) != y_i

4. 输出
    H(x) = sign(sum(a_t*h_t(x)))

所谓弱分类器,就是分类的准确性超过50%的分类器,所谓弱,就说即使50.1%都行。AdaBoost算法很简洁,但可以将一大堆弱分类器组合起来,成为强分类器,也就是准确性很高的分类器。

这篇论文也说了AdaBoost的诸多好处,还有一些理论结论。我实现了一个简单的AdaBoost,作为参考,代码没有作足够的优化,只是为了说明AdaBoost算法。

代码是Python2.6的,在Ubuntu 10.04下调试通过,效果符合预期。

#!/usr/bin/env python
# -*- coding: utf-8 -*-

from random import randint
from math import sin, cos, log, exp

import os
import pickle

#存放数据集的文件
fname = "data.pkl"

#产生数据集的参数
maxint = 20
n_train = int(maxint*0.8)
n_test = int(maxint*0.2)

#属性的定义域分割
n_patt = 100

pi = 3.1415926

#adaboost训练次数
T = 200

#每个属性的最大值和最小值
max_v = []
min_v = []

#一个很简单的决策树
class DecTree(object):
    def __init__(self):
        self.thr = 0
        self.idx_attr = 0
    
    def do(self, ele):
        if ele[self.idx_attr] > self.thr:
            return 1
        else:
            return -1

"""
生成数据集:
随机生成两个分布在不同半径上的圆弧数据。每组数据,一部分作测试集,一部分作训练集。
大半径圆弧对应正类。小半径圆弧对应负类。
然后,将数据存入pickle文件备用。
"""
def get_data_set():
    #随机产生maxint个角度
    ang1 = []
    for i in range(maxint):
        ang1.append(randint(0, 100))
    #print "ang = ", ang

    #产生第1个圆的数据
    c1_data = []
    r1 = 10
    for i in range(maxint):        
        c1_data.append([r1*cos(ang1[i]*2*pi/360), r1*sin(ang1[i]*2*pi/360)])

    #随机产生maxint个角度
    ang2 = []
    for i in range(maxint):
        ang2.append(randint(80, 180))
    #产生第2个圆的数据
    c2_data = []
    r2 = 8
    for i in range(maxint):
        c2_data.append([r2*cos(ang2[i]*2*pi/360), r2*sin(ang2[i]*2*pi/360)])

    #产生第1个圆的训练集和测试集
    c1_train_x = []
    c1_train_y = []
    for i in range(n_train):
        c1_train_x.append(c1_data[i])
        c1_train_y.append(1)

    c1_test_x = []
    c1_test_y = []

    for i in range(n_train, maxint):
        c1_test_x.append(c1_data[i])
        c1_test_y.append(1)
    
    #产生第2个圆的训练集和测试集
    c2_train_x = []
    c2_train_y = []
    for i in range(n_train):
        c2_train_x.append(c2_data[i])
        c2_train_y.append(-1)

    c2_test_x = []

    c2_test_y = []
    for i in range(n_train, maxint):
        c2_test_x.append(c2_data[i])
        c2_test_y.append(-1)

    f1 = file(fname, 'wb')
    pickle.dump(c1_train_x, f1, True)
    pickle.dump(c1_train_y, f1, True)
    pickle.dump(c1_test_x, f1, True)
    pickle.dump(c1_test_y, f1, True)

    pickle.dump(c2_train_x, f1, True)
    pickle.dump(c2_train_y, f1, True)
    pickle.dump(c2_test_x, f1, True)
    pickle.dump(c2_test_y, f1, True)
    f1.close()

#训练样本的第i_att个属性上的决策树分类器
def train_weak_classifier_of_attr(train_x, train_y, D, i_att):
    func_name = "train_weak_classifier_of_attr"

    print ""
    print "func = ", func_name
    #决策树的阈值是让训练的误差最小
    min_e = None
    dt_res = None
    min_num_err = None
    for i in range(n_patt):
        #print "nn_patt = ", i
        dt = DecTree()
        dt.idx_attr = i_att
        dt.thr = min_v[i_att] + 1.0*i/n_patt*(max_v[i_att] - min_v[i_att])
        #print "dt.idx_attr = ", dt.idx_attr
        #print "dt.thr = ", dt.thr
        e = 0
        num_err = 0
        for ii in range(len(train_x)):
            if(dt.do(train_x[ii]) != train_y[ii]):
                e += D[ii]
                num_err += 1
        #print "e = ", e
        #print "num_err = ", num_err
        if None == dt_res:
            dt_res = dt
            min_e = e
            min_num_err = num_err
            #print "None == dt_res"
            #print "min_e = ", min_e
            #print "min_num_err = ", min_num_err
        else:            
            if e < min_e:
                min_e = e
                dt_res = dt
                min_num_err = num_err
                #print "e < min_e"
                #print "min_e = ", min_e
                #print "min_num_err = ", min_num_err                

    #防止数据无意义
    if min_e >= 1.0:
        min_e = 0.999
    if min_e <= 0.0:
        min_e = 0.001

    print "nfunc = ", func_name, " ok"
    print "dt_res = ", [dt_res.idx_attr, dt_res.thr], 
    print "min_e = ", min_e
    
    return dt_res, min_e, min_num_err

#根据D,训练分类器    
def train_weak_classifier_of_D(train_x, train_y, D):
    func_name = "train_weak_classifier_of_D"

    print ""
    print "func = ", func_name
    min_e = None
    dt_res = None
    min_num_err = None
    for i in range(len(train_x[0])):
        print "--------------"
        print "i = ", i
        dt, e, num_err = train_weak_classifier_of_attr(train_x, train_y, D, i)
        print "dt = [", dt.idx_attr, ", ", dt.thr, "]"
        print "e = ", e
        print "num_err = ", num_err
        
        if None == dt_res:
            dt_res = dt
            min_e = e
            min_num_err = num_err
        else:
            if e < min_e:
                min_e = e
                dt_res = dt
                min_num_err = num_err
    print "nfunc = ", func_name, " ok"
    print "dt_res = [", dt_res.idx_attr, ", ", dt_res.thr, "]"
    print "min_e = ", min_e
    print "min_num_err = ", min_num_err

    return dt_res, min_e, min_num_err

#根据训练好的分类器对测试集数据进行分类
def make_decision(dt_all, at_all, ele):
    s = 0
    for i in range(len(dt_all)):
        s += at_all[i]*dt_all[i].do(ele)
    if s > 0:
        return 1
    else:
        return -1

def main():
    #如果数据文件不存在,生成数据集
    if(os.path.isfile(fname)):
        pass
    else:
        get_data_set()

    #读入数据集
    f1 = file(fname, 'rb')
    c1_train_x = pickle.load(f1)
    c1_train_y = pickle.load(f1)
    c1_test_x = pickle.load(f1)
    c1_test_y = pickle.load(f1)

    c2_train_x = pickle.load(f1)
    c2_train_y = pickle.load(f1)
    c2_test_x = pickle.load(f1)
    c2_test_y = pickle.load(f1)

    f1.close()

    #生成训练集
    train_x = []
    train_y = []
    for i in range(n_train):
        train_x.append(c1_train_x[i])
        train_y.append(c1_train_y[i])
        train_x.append(c2_train_x[i])
        train_y.append(c2_train_y[i])
    print "ntrain set:"
    for i in range(len(train_x)):
        print train_y[i], ":t", train_x[i]
    
    #找每组属性的最大值和最小值
    for i in range(len(train_x[0])):
        vb = train_x[0][i]
        vs = train_x[0][i]
        for j in range(len(train_x)):
            if train_x[j][i] > vb:
                vb = train_x[j][i]
            if train_x[j][i] < vs:
                vs = train_x[j][i]
        max_v.append(vb)
        min_v.append(vs)
    print "max_v = ", max_v
    print "min_v = ", min_v

    D_all = []
    dt_all = []
    at_all = []
    e_all = []
    min_num_err_all = []
    #第0次训练
    print "nn"
    print "No.0 Train"
    D = []
    for i in range(len(train_x)):
        D.append(1.0/len(train_x))
    D_all.append(D)
    print "D = ", D
    
    dt, e, num_err = train_weak_classifier_of_D(train_x, train_y, D)
    dt_all.append(dt)
    e_all.append(e)
    a_t = 0.5*log((1-e)/e)
    at_all.append(a_t)
    min_num_err_all.append(num_err)
    print "nNo.0 train ok"
    print "dt = ", [dt.idx_attr, dt.thr]
    print "e = ", e
    print "a_t = ", a_t

    #第1次到第T-1次训练
    for t in range(T):
        print "nnNo.%d train" %(t+1)
        D_new = []
        for i in range(len(D)):
            if(dt.do(train_x[i]) != train_y[i]):
                D_new.append(D[i]*exp(a_t))
            else:
                D_new.append(D[i]*exp(-1*a_t))
        print "D_new = ", D_new
        sD = sum(D_new)
        print "sD = ", sD
        for i in range(len(D_new)):
            D_new[i] = 1.0*D_new[i]/sD
        D = D_new
        D_all.append(D)
        print "D = ", D
        print "sum of D = ", sum(D)
        dt, e, num_err = train_weak_classifier_of_D(train_x, train_y, D)
        print "dt = ", [dt.idx_attr, dt.thr]
        print "e = ", e
        e_all.append(e)
        dt_all.append(dt)
        a_t = 0.5*log((1-e)/e)
        at_all.append(a_t)
        min_num_err_all.append(num_err)
        print "a_t = ", a_t

    #输出训练结果
    print "nn"
    print "result is:"
    for i in range(len(dt_all)):
        print "------------"
        print "i = ", i
        dt = dt_all[i]
        print "D = ", D_all[i]
        print "dt = ", [dt.idx_attr, dt.thr]  
        print "e = ", e_all[i]
        print "a_t = ", at_all[i]
        print "min_num_err = ", min_num_err_all[i]
            
    test_x = []
    test_y = []
    for i in range(n_test):
        test_x.append(c1_test_x[i])
        test_y.append(c1_test_y[i])
        test_x.append(c2_test_x[i])
        test_y.append(c2_test_y[i])
    print "ntest set:"
    for i in range(len(test_x)):
        print test_y[i], ":t", test_x[i]

    err  = 0
    for i in range(len(test_x)):
        if(make_decision(dt_all, at_all, test_x[i])!= test_y[i]):
            err += 1
    err_per = 1.0*err/len(test_x)
    print "err_per = %d%%" %(err_per*100)

if __name__ == "__main__":
    main()


http://blog.sciencenet.cn/blog-471807-583350.html

上一篇:考虑空间关系的SAR图像分类
下一篇:[转载]word与mathtype公式的问题(转载)

0

该博文允许注册用户评论 请点击登录 评论 (0 个评论)

数据加载中...

Archiver|手机版|科学网 ( 京ICP备14006957 )

GMT+8, 2019-9-23 22:13

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部