集成学习,艾达boost算法笔记

集成学习是机械学习中一个格外重庆大学且热门的分支,是用三个弱分类器构成3个强分类器,其农学思想是“四个臭皮匠赛过诸葛孔明”。1般的弱分类器能够由决策树,神经网络,贝叶斯分类器,K-近邻等组成。已经有大家理论上说明了合并学习的思索是能够增进分类器的性质的,比如说计算上的因由,总括上的来由以及代表上的来由。集成学习中最首要的二个算法为:boosting,bagging,stacking。当中boosting的弱分类器形成是如出1辙种机器学习算法,只是其数据抽取时的权值在不断更新,每趟都以增强前一回分错了的数据集的权值,最终得到T个弱分类器,且分类器的权值也跟当中间结果的多寡有关。Bagging算法也是用的同一种弱分类器,其数量的源于是用bootstrap算法得到的。Stacking算法分为贰层,第3层是用区别的算法形成T个弱分类器,同时发出五个与原数据集大小相同的新数据集,利用那个新数据集和三个新算法构成第3层的分类器。集成学习有效的前提:1.各样弱分类器的错误率不能够凌驾0.5。二.弱分类器之间的品质要有较大的差别,不然集成作用不是很好。集成学习依照基本分类器之间的涉嫌足以分为异态集成学习和同态集成学习。异态集成学习是指弱分类器之间作者差别,而同态集成学习是指弱分类器之间自作者一样只是参数分歧。怎么样形成分化的基本分类器呢?首要从以下伍个方面取得。

背后的研商:对于一个繁杂的职务,讲八个我们的判断进行适宜的归咎得出的判定,要比内部任何3个学者单独的论断好。(八个臭皮匠赛过诸葛孔明)

  1. 主导分类器本人的品种,即其构成算法差别。
  2. 对数码举办处理不一致,比如说boosting,bagging,stacking,
    cross-validation,hold-out test.等。
  3. 对输入特征进行拍卖和挑选
  4. 对输出结果进行处理,比如说有的学者提议的纠错码
  5. 引入自由扰动
再可能率近似正确学习的框架中:
  • 强可学习:存在三个多项式的学习算法,并且它的正确率很高
  • 弱可学习:存在一个多项式的求学算法,它的正确率比自由估计好
  • 强可学习和弱可学习等价

骨干分类器之间的组合格局,一般有大约投票,贝叶斯投票,基于D-S证据反驳的组成,基于差异的性状子集的结缘。基础学习品质的分析方法首要有bias-variance分析法。近日有的壹般性实验结论:Boosting方法的合并分类器效果鲜明优于bagging,可是在1些数据集boosting算法的成效还比不上单个分类器的;使用随机化的人工神经互连网初步权值来进展集成的秘诀往往能够获取和bagging同样好的效益;Boosting算法一定水平上依赖而数据集,而bagging对数据集的借助没有那么强烈;Boosting算法不仅能够减弱差错还可以减少方差,但bagging算法智能收缩方差,对不是的滑坡职能相当小。

找到弱可学习的主意相比较易于,最著名的正是 Adaboost算法。

以下先对总括学习方式上的相关内容开展求证。

对此提示算法处理分类难点:

  • 每1轮怎么着改变多少的权值大概可能率分布
  • 如何将弱分类器组合成一个强分类器

boostting类算法

Adaboost的老路是:一. 教练的时候拉长弱分类器错误分类样本的权值,那样能够更进一步珍贵没有科学分类的多少;二. 使用加权多数核定的法子,加大分类错误率小的弱分类器的权值,使其再决定中起较大的效果。

Boosting方法是1种用来增强弱分类算法准确度的诀窍,那种办法通过结构一个人作品展望函数种类,然后以一定的措施将她们组合成3个猜想函数。他是一种框架算法,首假如由此对样本集的操作获得样本子集,然后用弱分类算法在样本子集上锻练生成1密密麻麻的基分类器。他得以用来抓牢别的弱分类算法的识别率,也便是将别的的弱分类算法作为基分类算法放于Boosting
框架中,通过Boosting框架对教练样本集的操作,得到不相同的磨炼样本子集,用该样本子集去磨炼生成基分类器;每得到二个样本集就用该基分类算法在该样本集上发生1个基分类器,这样在给定锻炼轮数
n 后,就可爆发 n 个基分类器,然后Boosting框架算法将这n个基分类器进行加权融合,产生1个终极的结果分类器,在那n个基分类器中,各种单个的分类器的识别率不自然很高,但她俩齐声后的结果有很高的识别率,那样便提升了该弱分类算法的识别率。在发生单个的基分类器时可用相同的归类算法,也可用不相同的分类算法,这几个算法一般是不安静的弱分类算法,如神经网络(BP)
,决策树(C四.5)等。

算法流程

图片 1

image.png

图片 2

image.png

图片 3

image.png

1、AdaBoost算法

AdaBoost 算法的解释:AdaBoost算法的模子是加法模型、损失函数为指数函数、学习算法为提升分步算法时的二类分类学习格局。


AdaBoost算法的骨干思维

  1. 多轮流培练习,多个分类器

  2. 每轮流培练习扩充错误分类样本的权值,降低正确分类样本的权值

  3. 跌落错误率高的分类器的权值,扩展正确率高的分类器的权值

提拔树算法—以分类树大概回归树为大旨分类器的晋级措施,其被认为是总结学习中质量最棒的不二等秘书籍之一。 [加法模型(基函数的线性组合) + 前向分布算法]

图片 4

image.png

AdaBoost算法

给定几个贰类分类的陶冶数据集

图片 5

内部,各种样本点由实例与标记组成。实例图片 6,标记图片 7图片 8是实例空间,图片 9是标志集合。艾达Boost利用以下算法,从陶冶多少中学习一层层弱分类器或大旨分类器,并将那个弱分类器线性组合成为贰个强分类器。

AdaBoost算法

输入:练习数据集图片 10:弱学习算法;

出口:最后分类器图片 11

(1)开首化锻炼多少的权值分布

图片 12

每一个w的下标由两片段构成,前叁个数表示近来迭代次数,与D的下标保持1致,后一个数表示第多少个权值,与地方保持壹致。开始情状下,种种权值都以均等的。

(2)对图片 13(那里的M原作未做表明,其实是象征演习的迭代次数,是由用户钦命的。每轮迭代发出三个分类器,最后就有M个分类器):

(a)使用具有权值分布的磨练多少集学习,得到基本分类器

图片 14

 

(b)计算图片 15在训练多少集上的归类基值误差率

图片 16

分拣基值误差率那个名字大概发生误解,那里其实是个加权和。

(c)计算图片 17的系数

图片 18

那里的对数是自然对数。图片 19表示图片 20在结尾分类器中的重要性。由式图片 21可知,当图片 22时,图片 23,并且图片 24随着图片 25的滑坡而增大,所以分类相对误差率越小的为主分类器在终极分类器中的作用越大。

为什么一定要用那几个姿势呢?那与前向分步算法的推理有关,在后边的章节会介绍。

(d)更新兵练习练数据集的权值分布

图片 26

y唯有正负1三种取值,所以上式能够编写:

图片 27

这里,图片 28是规范化因子

图片 29

它使图片 30成为四个概率分布。

想来,被基本分类器误分类样本的权值得以扩张,而被科学分类样本的权值却足以裁减。两相相比较,误分类样本的权值被放大图片 31倍。由此,误分类样本在下一轮学习中起更大的成效。不改变所给的练习多少,而不止变更陶冶多少权值的遍布,使得磨炼多少在大旨分类器的上学中起差别的功力,那是AdaBoost的三个特色。

(叁)构建大旨分类器的线性组合

图片 32

获得最后分类器

图片 33

以决策树为基函数的升级措施称为升高树(boosting tree). 对分类难题决策树是贰叉树,对于回归难题决策树是二叉回归树。

AdaBoost算法的解释

AdaBoost算法还有另二个表达,即能够认为AdaBoost算法是模型为加法模型、损失函数为指数函数、学习算法为前向分步算法时的2类分类学习情势。

为何还要学习前向分步算法呢?直接给本身AdaBoost的代码不就好了吗?因为唯有知道了前向分步算法,才能知道AdaBoost为何能跟决策树组合起来。

算法简介

前向分步算法

设想加法模型(additive model)

图片 34

其中,图片 35为基函数,图片 36为基函数的参数,图片 37为基函数的周密。分明,图片 38是三个加法模型。

在给定磨炼多少及损失函数的规范下,学习加法模型图片 39变成经验风险相当小化即损失函数相当的小化难点:

图片 40

经常那是1个复杂的优化难题。前向分步算法(forward stage wise
algorithm)求解这一优化难点的想法是:因为学习的是加法模型,若是能够在此以前向后,每一步只学习三个基函数及其周密,稳步逼近优化指标函数式图片 41(L应该是loss的缩写,表示三个损失函数,输入正确答案yi和模型预测值,输出损失值),那么就能够简化优化的复杂度。具体地,每步只需优化如下损失函数:

图片 42

也正是说,原来有M个分类器,未来只在意优化3个。

给定磨练数据集图片 43。损失函数图片 44和基函数的聚合图片 45,学习加法模型图片 46的前向分步算法如下:

算法(前向分步算法)

输入:磨炼数据集图片 47,损失函数图片 48,基函数集图片 49;

出口:加法模型图片 50

(1)初始化图片 51

(2)对图片 52

(a)十分的小化损失函数

图片 53

取得参数图片 54

 (b)更新

图片 55

(3)获得加法模型

图片 56

诸如此类,前向分步算法将同时求解从m=一到M全数参数图片 57的优化难点简化为逐次求解各种图片 58的优化难题。

先是明确开端提高书f0(x)=0, 第m步模型为:

图片 59

image.png

图片 60

image.png

图片 61

image.png


前向分步算法与AdaBoost

由前向分步算法能够推导出AdaBoost,用定理叙述这一关系。

定理 AdaBoost算法是前向分歩加法算法的特例。那时,模型是由大旨分类器组成的加法模型,损失函数是指数函数。

表明 前向分步算文学习的是加法模型,当基函数为骨干分类器时,该加法模型等价于AdaBoost的末了分类器

由主旨分类器图片 62随同周全图片 63结缘,m=1,二,…,M。前向分步算法逐一学习基函数,那1进程与AdaBoost算法逐1学习为主分类器的进程一样。下面申明前向分步算法的损失函数是指数损失函数(exponential
loss function)

图片 64

时,其深造的有血有肉操作等价于AdaBoost算理学习的具体操作。

只要经过m-一轮迭代前向分步算法已经获得图片 65:

图片 66

在第m轮迭代得到图片 67图片 68

图片 69

指标是使前向分步算法获得的图片 70使图片 71在磨练多少集T上的指数损失极小,即

图片 72

上式能够象征为

图片 73

其中,图片 74(指数中的加法能够拿出去做乘法)。因为图片 75既不重视α也不依赖于G,所以与最小化无关。但图片 76依赖于图片 77,随着每壹轮迭代而产生变更。

现证使式图片 78落得最小的图片 79不畏AdaBoost算法所收获的图片 80

求解式图片 81可分两步:

首先,求图片 82。对任意a>0,使式图片 83最小的图片 84由下式获得:

图片 85

其中,图片 86

此分类器图片 87即为艾达Boost算法的为主分类器图片 88,因为它是使第m轮加权锻炼多少分类测量误差率最小的主干分类器。

之后,求图片 89图片 90

图片 91

其一转换很简单,当y和G1致时,指数为负,反之为正,第三个等号也是使用那个原理,只可是换到了用提醒变量I表述。

将已求得的图片 92代入式图片 93,对α求导并使导数为0,即得到使式图片 94最小的a。

图片 95

其中,图片 96是分类固有误差率:

 

这里的图片 97与AdaBoost算法第2(c)步的图片 98完全一致。

终极来看每一轮样本权值的革新。由

图片 99

以及图片 100,可得

图片 101

那与AdaBoost算法第2(d)步的样本权值的翻新,只相差规范化因子,因此等价。

梯度提高算法

提升树

晋级树是以分类树或回归树为骨干分类器的晋升措施。升高树被认为是计算学习中性能最佳的方法之1。升高措施其实运用加法模型(即基函数的线性组合)与前向分步算法。以决策树为基函数的提拔措施称为提高树(boosting
tree)。对分类难点决策树是二叉分类树,对回归难点决策树是二叉回归树。在原版的书文例题中来看的主干分类器,能够用作是由一个根结点直接连接四个叶结点的粗略决策树,即所谓的仲裁树桩(decision
stump)。进步树模型可以代表为决策树的加法模型:

图片 102

其中,图片 103表示决策树;图片 104为决策树的参数;M为树的个数。

Freidman建议了梯度升高算法(Gradient Boosting), 其关键是采取损失函数的负梯度再当前模型的值作为回归难点升高树算法中的残差的近似值,拟合二个回归树。

图片 105

image.png


晋升树算法

升级树算法选取前向分步算法。首先鲜明初步升高树/e(x)=0,第m歩的模子是

图片 106

其中,图片 107为当前模型,通过经历危害十分的小化鲜明下一棵决策树的参数图片 108

图片 109

出于树的线性组合能够很好地拟合陶冶多少,即使数据中的输入与输出之间的涉及很复杂也是这么,所以进步树是二个髙功用的学习算法。

不等难题有差不离的升迁树学习算法,其重庆大学不一致在于运用的损失函数分裂。包罗用平方抽样误差损失函数的回归难题,用指数损失函数的归类难点,以及用壹般损失函数的貌似决策难点。

对于二类分类难点,提高树算法只需将艾达Boost算法中的基本分类器限制为2类分类树即可,能够说那时的升迁树算法是AdaBoost算法的尤其情况,接下去通过《机器学习实战》中的代码学习其利用。

未完待续…

进步树的Python实现

AdaBoost+决策树=进步树,来探望实际用Python怎么落实。

from numpy import *

def loadSimpData():
    datMat = matrix([[ 1. ,  2.1],
        [ 2. ,  1.1],
        [ 1.3,  1. ],
        [ 1. ,  1. ],
        [ 2. ,  1. ]])
    classLabels = [1.0, 1.0, -1.0, -1.0, 1.0]
    return datMat,classLabels

def loadDataSet(fileName):      #general function to parse tab -delimited floats
    numFeat = len(open(fileName).readline().split('\t')) #get number of fields 
    dataMat = []; labelMat = []
    fr = open(fileName)
    for line in fr.readlines():
        lineArr =[]
        curLine = line.strip().split('\t')
        for i in range(numFeat-1):
            lineArr.append(float(curLine[i]))
        dataMat.append(lineArr)
        labelMat.append(float(curLine[-1]))
    return dataMat,labelMat

def stumpClassify(dataMatrix,dimen,threshVal,threshIneq):#just classify the data
    retArray = ones((shape(dataMatrix)[0],1))
    if threshIneq == 'lt':
        retArray[dataMatrix[:,dimen] <= threshVal] = -1.0
    else:
        retArray[dataMatrix[:,dimen] > threshVal] = -1.0
    return retArray


def buildStump(dataArr,classLabels,D):
    dataMatrix = mat(dataArr); labelMat = mat(classLabels).T
    m,n = shape(dataMatrix)
    numSteps = 10.0; bestStump = {}; bestClasEst = mat(zeros((m,1)))
    minError = inf #init error sum, to +infinity
    for i in range(n):#loop over all dimensions
        rangeMin = dataMatrix[:,i].min(); rangeMax = dataMatrix[:,i].max();
        stepSize = (rangeMax-rangeMin)/numSteps
        for j in range(-1,int(numSteps)+1):#loop over all range in current dimension
            for inequal in ['lt', 'gt']: #go over less than and greater than
                threshVal = (rangeMin + float(j) * stepSize)
                predictedVals = stumpClassify(dataMatrix,i,threshVal,inequal)#call stump classify with i, j, lessThan
                errArr = mat(ones((m,1)))
                errArr[predictedVals == labelMat] = 0
                weightedError = D.T*errArr  #calc total error multiplied by D
                #print "split: dim %d, thresh %.2f, thresh ineqal: %s, the weighted error is %.3f" % (i, threshVal, inequal, weightedError)
                if weightedError < minError:
                    minError = weightedError
                    bestClasEst = predictedVals.copy()
                    bestStump['dim'] = i
                    bestStump['thresh'] = threshVal
                    bestStump['ineq'] = inequal
    return bestStump,minError,bestClasEst


def adaBoostTrainDS(dataArr,classLabels,numIt=40):
    weakClassArr = []
    m = shape(dataArr)[0]
    D = mat(ones((m,1))/m)   #init D to all equal
    aggClassEst = mat(zeros((m,1)))
    for i in range(numIt):
        bestStump,error,classEst = buildStump(dataArr,classLabels,D)#build Stump
        #print "D:",D.T
        alpha = float(0.5*log((1.0-error)/max(error,1e-16)))#calc alpha, throw in max(error,eps) to account for error=0
        bestStump['alpha'] = alpha  
        weakClassArr.append(bestStump)                  #store Stump Params in Array
        #print "classEst: ",classEst.T
        expon = multiply(-1*alpha*mat(classLabels).T,classEst) #exponent for D calc, getting messy
        D = multiply(D,exp(expon))                              #Calc New D for next iteration
        D = D/D.sum()
        #calc training error of all classifiers, if this is 0 quit for loop early (use break)
        aggClassEst += alpha*classEst
        #print "aggClassEst: ",aggClassEst.T
        aggErrors = multiply(sign(aggClassEst) != mat(classLabels).T,ones((m,1)))
        errorRate = aggErrors.sum()/m
        print "total error: ",errorRate
        if errorRate == 0.0: break
    return weakClassArr,aggClassEst

def adaClassify(datToClass,classifierArr):
    dataMatrix = mat(datToClass)#do stuff similar to last aggClassEst in adaBoostTrainDS
    m = shape(dataMatrix)[0]
    aggClassEst = mat(zeros((m,1)))
    for i in range(len(classifierArr)):
        classEst = stumpClassify(dataMatrix,classifierArr[i]['dim'],\
                                 classifierArr[i]['thresh'],\
                                 classifierArr[i]['ineq'])#call stump classify
        aggClassEst += classifierArr[i]['alpha']*classEst
        print aggClassEst
    return sign(aggClassEst)

def plotROC(predStrengths, classLabels):
    import matplotlib.pyplot as plt
    cur = (1.0,1.0) #cursor
    ySum = 0.0 #variable to calculate AUC
    numPosClas = sum(array(classLabels)==1.0)
    yStep = 1/float(numPosClas); xStep = 1/float(len(classLabels)-numPosClas)
    sortedIndicies = predStrengths.argsort()#get sorted index, it's reverse
    fig = plt.figure()
    fig.clf()
    ax = plt.subplot(111)
    #loop through all the values, drawing a line segment at each point
    for index in sortedIndicies.tolist()[0]:
        if classLabels[index] == 1.0:
            delX = 0; delY = yStep;
        else:
            delX = xStep; delY = 0;
            ySum += cur[1]
        #draw line from cur to (cur[0]-delX,cur[1]-delY)
        ax.plot([cur[0],cur[0]-delX],[cur[1],cur[1]-delY], c='b')
        cur = (cur[0]-delX,cur[1]-delY)
    ax.plot([0,1],[0,1],'b--')
    plt.xlabel('False positive rate'); plt.ylabel('True positive rate')
    plt.title('ROC curve for AdaBoost horse colic detection system')
    ax.axis([0,1,0,1])
    plt.show()
    print "the Area Under the Curve is: ",ySum*xStep

贰、梯度进步gradient boosting

梯度进步是对AdaBoost的延长,它不再须求相对误差函数是指数固有误差函数,而或然是随意一种标称误差函数(因为那边是用梯度下跌法来最棒化抽样误差函数,所以那里要求抽样误差函数是坦荡的)。

图片 110

在那一个框架结构下,大家就能够利用不一样的只要和模型,来缓解分类恐怕回归的题材。

梯度提高利用于回归难题

梯度进步利用于回归难题时,测量误差函数选中均方标称误差函数。

图片 111

接着,我们对那么些舍入误差函数中变量s在sn处进行一阶Taylor展开的类似,我们发现要最小化的骨子里是∑h(xn)·2(sn-yn),要让该表明式最小,需求h(xn)(sn-yn)的样子相反:

图片 112

 须要解最好化难点,须要h(xn)(sn-yn)的可行性相反,而h(xn)的尺寸其实不是大家提到的题材,因为步长难点是由参数η决定的。要是将h(xn)强制限制为一要么有个别常数的话,那么就获得了一个有规则的最好化难题,增加了求解的难度。比不上咱们将查办项h(xn)的平方放进最棒化式子中(意思是,即便h(xn)越大,大家就越不指望那样)。大家得以将平格局子变换一下,得到关于(h(xn)-(yn-sn))^2的姿势,所以大家渴求一个带惩罚项的近乎函数梯度的难题,就等效于求xn和余数(residual)yn-sn的回归难题。

图片 113

鲜明步长η

图片 114

咱俩现在规定了gt,接着我们要规定步长η,那里我们得以将标称误差函数写成余数(yn-sn)的花样,那是1个单变量的线性回归难点,当中输入是用gt转换后的多少,输出是余数(residual)。

图片 115

梯度升高决策树

笔者们就能够获得梯度提高决策树的算法流程:

图片 116

 总计如下:

1、在每一遍迭代进程,化解2个回归难题,那里能够用CACRUISERT算法来解{xn,
(yn-sn)}的回归难题;

二、然后,用gt做转换,做二个{gt(xn), yn-sn}的单变量线性回归难题;

叁、更新分数sn;

4、经过T轮迭代,得到G(x)。

以此GBDT算法能够作为是AdaBoost-DTree的回归难题版本。

代码如下:

/**
 * 梯度提升回归树    简单实现*/
public class Gbdt {
    static List<Sample> mSamples;
    static List<Double> mTrainTarget;
    static List<Double> mTrainCurTarget;
    static List<Cart> mCarts;
    /**
     * 加载数据   回归树
     * @param path
     * @param regex
     * @throws Exception
     */
    public  void loadData(String path,String regex) throws Exception{
        mSamples = new ArrayList<Sample>();
        mTrainTarget = new ArrayList<Double>();
        mTrainCurTarget = new ArrayList<Double>();
        BufferedReader reader = new BufferedReader(new FileReader(path));
        String line = null;
        String splits[] = null;
        Sample sample = null;
        while(null != (line=reader.readLine())){
            splits = line.split(regex);
            sample = new Sample();
            sample.label = Double.valueOf(splits[0]);
            mTrainTarget.add(sample.label);
            mTrainCurTarget.add(0.0);
            sample.feature = new ArrayList<Double>(splits.length-1);
            for(int i=0;i<splits.length-1;i++){
                sample.feature.add(new Double(splits[i+1]));
            }

            mSamples.add(sample);
        }
        reader.close();
    }
    /**
     * 更新训练集目标
     * @author Administrator
     *
     */
    static class Update implements Runnable{
        int from;
        int to;
        Cart cart;
        public Update(int from,int to,Cart cart){
            this.from = from;
            this.to = to;
            this.cart = cart;
        }
        @Override
        public void run() {
            // TODO Auto-generated method stub
            Sample sample = null;
            for(int i=from;i<to;i++){
                sample = mSamples.get(i);
                mTrainCurTarget.set(i, mTrainCurTarget.get(i)+cart.classify(sample));
                sample.label = mTrainTarget.get(i)-mTrainCurTarget.get(i);
            }
        }

    }
    public void updateTarget(Cart cart) throws InterruptedException{
        /*Sample sample = null;
        for(int i=0;i<mSamples.size();i++){
            sample = mSamples.get(i);
            mTrainCurTarget.set(i, mTrainCurTarget.get(i)+cart.classify(sample));
            sample.label = mTrainTarget.get(i)-mTrainCurTarget.get(i);
        }*/
        Update update = null;
        int num = 10;
        Thread ths[] = new Thread[num];
        int size = mSamples.size();

        for(int i=0;i<num;i++){
            update = new Update(i*size/num,(i+1)*size/num,cart);
            ths[i] = new Thread(update);
            ths[i].start();
        }
        for(int i=0;i<num;i++){
            ths[i].join();
        }
    }
    public void train(int iters) throws InterruptedException{
        mCarts = new ArrayList<Cart>(iters);
        Random ran = new Random();
        ran.setSeed(100);
        for(int iter=0;iter<iters;iter++){
            System.out.println("start iter "+iter+"  time:"+System.currentTimeMillis()/1000);
            Cart cart = new Cart();
            cart.mFeatureRate = 0.8;
            cart.mMaxDepth = 5;
            cart.mMinLeaf = 1;
            cart.mRandom = ran;
            cart.setData(mSamples);
            cart.train();
            mCarts.add(cart);
            updateTarget(cart);
            System.out.println("end iter "+iter+"  time:"+System.currentTimeMillis()/1000);
        }
    }
    public double classify(Sample sample){
        double ret = 0;
        for(Cart cart:mCarts){
            ret += cart.classify(sample);
        }
        return ret;
    }
    /**
     * @param args
     * @throws Exception 
     */
    public static void main(String[] args) throws Exception {
        // TODO Auto-generated method stub
        System.out.println(System.currentTimeMillis());
        Gbdt gbdt = new Gbdt();
        gbdt.loadData("F:/2016-contest/20161001/train_data_1.csv", ",");
        gbdt.train(100);
        List<Sample> samples = Cart.loadTestData("F:/2016-contest/20161001/valid_data_1.csv", true, ",");
        double sum = 0;
        for(Sample s:samples){
            double val = gbdt.classify(s);
            sum += (val-s.label)*(val-s.label);
            System.out.println(val+"  "+s.label);
        }
        System.out.println(sum/samples.size()+"  "+sum);
        System.out.println(System.currentTimeMillis());
    }

}

bagging类算法

boosting算法在每一轮学习中,模型具有相似性的表征,而bagging则是在每一轮之间,模型尽大概分歧,展现并行的特征,boosting显示串行的特征。bagging特点:对m个样本数量,采集出T个含n个样本的采访数据集,每1个采访数据集用于陶冶多个模型,再将相继模型进行整合,整合时,常采用简便易行投票、简单平均、置信度相比等政策。bagging的持筹握算复杂度较高,算法较便捷。同时,bagging专注下跌方差,boosting专注下降偏差。

轻易森林:

随机森林是bagging思想的1种体现,现在差不多介绍一下。

自由森林,指的是选用多棵树对样本进行磨练并推测的一种分类器。该分类器最早由LeoBreiman和Adele
Cutler提议,并被注册成了商标。简而言之,随机森林正是由多棵CA卡宴T(Classification
And Regression
Tree)构成的。对于每棵树,它们选择的教练集是从总的操练集中有放回采集样品出来的,那意味着,总的练习集中的多少样本也许数次涌出在一棵树的磨练集中,也或许没有出现在一棵树的教练集中。在教练每棵树的节点时,使用的表征是从全部特征中遵守一定比例随机地无放回的抽取的,依据LeoBreiman的提议,如若总的特征数据为M,这些比例能够是sqrt(M),十二分之伍sqrt(M),贰sqrt(M)。

所以,随机森林的教练进程能够总计如下:

(1)给定磨练集S,测试集T,特征维数F。明确参数:使用到的CAPRADOT的数量t,每棵树的深度d,每一种节点使用到的特征数据f,终止条件:节点上至少样本数s,节点上最少的音讯增益m

对于第1-t棵树,i=1-t:

(二)从S中有放回的抽取大小和S壹样的陶冶集S(i),作为根节点的样书,从根节点最先磨练

(3)若是当前节点上达到终止条件,则设置当前节点为叶子节点,假设是分类难题,该叶子节点的预测输出为近年来节点样本集合中数据最多的那1类c(j),可能率p为c(j)占当前样本集的比重;若是是回归难点,预测输出为当下节点样本集各种样本值的平均值。然后继续陶冶别的节点。假设当前节点没有达标终止条件,则从F维特征中无放回的妄动选拔f维特征。利用这f维特征,寻找分类效果最佳的一维特征k及其阈值th,当前节点上样本第k维特征小于th的样本被划分到左节点,别的的被划分到右节点。继续陶冶别的节点。有关分类作用的评判标准在背后会讲。

(四)重复(二)(三)直到全体节点都练习过了大概被标记为叶子节点。

(5)重复(2),(三),(四)直到全部CAKoleosT都被磨练过。

使用随意森林的估量进程如下:

对于第1-t棵树,i=1-t:

(1)从当下树的根节点开首,依照当前节点的阈值th,判断是进入左节点(<th)依然进入右节点(>=th),直到抵达,有个别叶子节点,并出口预测值。

(贰)重复执行(一)直到全数t棵树都输出了预测值。若是是分类难点,则输出为有着树中预测可能率总和最大的那个类,即对种种c(j)的p实行累计;假使是回归难题,则输出为所有树的输出的平均值。

注:有关分类成效的评判标准,因为运用的是CA奥迪Q5T,因而使用的也是CA哈弗T的度量准则,和C3.0,C4.五都不雷同。

对于分类难题(将有些样本划分到某一类),也正是离散变量难点,CAOdysseyT使用Gini值作为评判标准。定义为Gini=壹-∑(P(i)*P(i)),P(i)为当前节点上数据汇总第i类样本的比例。例如:分为2类,当前节点上有916个样本,属于第3类的样本有七二十多个,属于第一类的样本有二16个,则Gini=一-0.7×07-0.3×0三=0.4二,能够观望,连串分布越平均,Gini值越大,类分布越不均匀,Gini值越小。在寻找最棒的归类特征和阈值时,评判标准为:argmax(Gini-GiniLeft-GiniRight),即寻找最棒的特征f和阈值th,使稳当前节点的Gini值减去左子节点的Gini和右子节点的Gini值最大。

对此回归难点,相对更为简明,直接行使argmax(Var-VarLeft-VarRight)作为评判标准,即当前节点练习集的方差Var减去减去左子节点的方差VarLeft和右子节点的方差VarRight值最大。

代码如下:

#ifndef _DECISION_TREE_H_
#define _DECISION_TREE_H_
#include <string>
#include <vector>
#include <set>
#include <ctime> 
#include <algorithm>
#include <cmath>

using namespace std;

//the data structure for a tuple
struct TupleData
{
  vector<int> A;
  char label;
};

  struct TNode
{
  int attrNum;    
  int attr;    
  char label;
};

struct decision_tree
{
  TNode node;
  vector<decision_tree*> childs;
};

  void init(char * trainname, char * testname);
  int readData(vector<TupleData> &data, const char* fileName);
  int stringtoint(string s);
  void sub_init();
  void calculate_ArrtNum();
  void calculate_attributes();
  void RandomSelectData(vector<TupleData> &data, vector<TupleData> &subdata);
  double Entropy(double p, double s);
  int creat_classifier(decision_tree *&p, const vector<TupleData> &samples, vector<int> &attributes);
  int BestGainArrt(const vector<TupleData> &samples, vector<int> &attributes);
  bool Allthesame(const vector<TupleData> &samples, char ch);
  char Majorityclass(const vector<TupleData> &samples);
  void RandomSelectAttr(vector<int> &data, vector<int> &subdata);
  char testClassifier(decision_tree *p, TupleData d);
  void testData();
  void freeClassifier(decision_tree *p);
  void freeArrtNum();
  void showResult();
  #endif //_DECISION_TREE_H_


#include <iostream>
#include <fstream>
#include <sstream>
#include "random_forest.h"

using namespace std;

vector<decision_tree*> alltrees;

vector<TupleData>    trainAll,
                    train,    
test;    

vector<int>     attributes;    

int trainAllNum=0;    
int testAllNum=0;    
int MaxAttr;    
int *ArrtNum;
unsigned int F;
int tree_num=100;
const int leafattrnum=-1;
int TP=0,
FN=0,
FP=0,
TN=0,
TestP=0,
TestN=0;

void init(char * trainname, char * testname)
{
trainAllNum=readData(trainAll, trainname);
testAllNum=readData(test, testname);
calculate_attributes();
double temp=(double)trainAllNum;
temp=log(temp)/log(2.0);
//     F=round(temp)+1;
F = (unsigned int)floor(temp+0.5)+1;
if(F>MaxAttr) F=MaxAttr;
//cout<<"f="<<F<<endl;
}

void sub_init()
{
RandomSelectData(trainAll, train);
calculate_ArrtNum();
}


int readData(vector<TupleData> &data, const char* fileName)
{
ifstream fin;
fin.open(fileName);
string line;

int datanum=0;

while(getline(fin,line))
{
TupleData d;
        istringstream stream(line);
        string str;
while(stream>>str)
{
if(str.find('+')==0)
{
d.label='+';
}
else if(str.find('-')==0)
{
 d.label='-';
}
else
{
int j=stringtoint(str);
d.A.push_back(j);
}
}

data.push_back(d);    
datanum++;
}

fin.close();
return datanum;
}

void RandomSelectData(vector<TupleData> &data, vector<TupleData> &subdata)
{
int index;
subdata.clear();
int d=0;
while (d < trainAllNum)
{
index = rand() % trainAllNum;
subdata.push_back(data.at(index));
d++;
}
}

void calculate_attributes()
{
TupleData d=trainAll.at(0);
MaxAttr=d.A.size();
attributes.clear();

for (int i = 0; i < MaxAttr; i++)
{
attributes.push_back(i);
}

ArrtNum=new int[MaxAttr];
}


int stringtoint(string s)
{
int sum=0;
for(int i=0; s[i]!='\0';i++)
{
int j=int(s[i])-48;
sum=sum*10+j;
}
return sum;
}

void calculate_ArrtNum()
{
for(int i=0; i<MaxAttr;i++) ArrtNum[i]=0;
for (vector<TupleData>::const_iterator it = train.begin(); it != train.end(); it++)    
{
int i=0;
for (vector<int>::const_iterator intt=(*it).A.begin(); intt!=(*it).A.end();intt++)
{
int valuemax=(*intt)+1;   //(*it).A.at(i)???
if(valuemax>ArrtNum[i]) ArrtNum[i]=valuemax;
i++;
}
}
}


double Entropy(double p, double s)
{
double n = s - p;
double result = 0;
if (n != 0)
result += - double(n) / s * log(double(n) / s) / log(2.0);
if (p != 0)
result += double(-p) / s * log(double(p) / s) / log(2.0);
return result;
}

int creat_classifier(decision_tree *&p, const vector<TupleData> &samples, vector<int> &attributes)
{
if (p == NULL)
p = new decision_tree();
if (Allthesame(samples, '+'))
{
p->node.label = '+';
p->node.attrNum = leafattrnum;
p->childs.clear();
return 1;
}
if (Allthesame(samples, '-'))
{
p->node.label = '-';
p->node.attrNum = leafattrnum;
p->childs.clear();
return 1;
}
if (attributes.size() == 0)
{
p->node.label = Majorityclass(samples);
p->node.attrNum = leafattrnum;
p->childs.clear();
return 1;
}
p->node.attrNum = BestGainArrt(samples, attributes);

p->node.label = ' ';

vector<int> newAttributes;
for (vector<int>::iterator it = attributes.begin(); it != attributes.end(); it++)
if ((*it) != p->node.attrNum)
newAttributes.push_back((*it));

int maxvalue=ArrtNum[p->node.attrNum];
vector<TupleData>* subSamples = new vector<TupleData>[maxvalue];
for (int i = 0; i < maxvalue; i++)
subSamples[i].clear();

for (vector<TupleData>::const_iterator it = samples.begin(); it != samples.end(); it++)
{
subSamples[(*it).A.at(p->node.attrNum)].push_back((*it));
}

decision_tree *child;
for (int i = 0; i < maxvalue; i++)
{
child = new decision_tree;
child->node.attr = i;
if (subSamples[i].size() == 0)
child->node.label = Majorityclass(samples);
else
creat_classifier(child, subSamples[i], newAttributes);
p->childs.push_back(child);
}
delete[] subSamples;
return 0;
}

int BestGainArrt(const vector<TupleData> &samples, vector<int> &attributes)
{
int attr, 
bestAttr = 0,
p = 0,
s = (int)samples.size();

for (vector<TupleData>::const_iterator it = samples.begin(); it != samples.end(); it++)
{
if ((*it).label == '+')
p++;
}

double infoD;
double bestResult = 0;
infoD=Entropy(p, s);

vector<int> m_attributes;
RandomSelectAttr(attributes, m_attributes);

for (vector<int>::iterator it = m_attributes.begin(); it != m_attributes.end(); it++)
{
attr = (*it);
double result = infoD;

int maxvalue=ArrtNum[attr];
int* subN = new int[maxvalue];
int* subP = new int[maxvalue];
int* sub = new int[maxvalue];
for (int i = 0; i < maxvalue; i++)
{
subN[i] = 0;
subP[i] = 0;
sub[i]=0;
}
for (vector<TupleData>::const_iterator jt = samples.begin(); jt != samples.end(); jt++)
{
if ((*jt).label == '+')
subP[(*jt).A.at(attr)] ++;
else
subN[(*jt).A.at(attr)] ++;
sub[(*jt).A.at(attr)]++;
}

double SplitInfo=0;
for(int i=0; i<maxvalue; i++)
{
double partsplitinfo;
partsplitinfo=-double(sub[i])/s*log(double(sub[i])/s)/log(2.0);
SplitInfo=SplitInfo+partsplitinfo;
}

double infoattr=0;
for (int i = 0; i < maxvalue; i++)
{
double partentropy;
partentropy=Entropy(subP[i], subP[i] + subN[i]);
infoattr=infoattr+((double)(subP[i] + subN[i])/(double)(s))*partentropy;
}
result=result-infoattr;
result=result/SplitInfo;

if (result > bestResult)
{
bestResult = result;
bestAttr = attr;
}
delete[] subN;
delete[] subP;
delete[] sub;
}

if (bestResult == 0)
{
bestAttr=attributes.at(0);
}
return bestAttr;
}

void RandomSelectAttr(vector<int> &data, vector<int> &subdata)
{
int index;
unsigned int dataNum=data.size();
subdata.clear();
if(dataNum<=F)
{
for (vector<int>::iterator it = data.begin(); it != data.end(); it++)
{
int attr = (*it);
subdata.push_back(attr);
}
}
else
{
set<int> AttrSet;
AttrSet.clear();
while (AttrSet.size() < F)
{
index = rand() % dataNum;
if (AttrSet.count(index) == 0)
{
AttrSet.insert(index);
subdata.push_back(data.at(index));
}
}
}
}

bool Allthesame(const vector<TupleData> &samples, char ch)
{
for (vector<TupleData>::const_iterator it = samples.begin(); it != samples.end(); it++)
if ((*it).label != ch)
return false;
return true;
}

char Majorityclass(const vector<TupleData> &samples)
{
int p = 0, n = 0;
for (vector<TupleData>::const_iterator it = samples.begin(); it != samples.end(); it++)
if ((*it).label == '+')
p++;
else
n++;
if (p >= n)
return '+';
else
return '-';
}

char testClassifier(decision_tree *p, TupleData d)
{
if (p->node.label != ' ')
return p->node.label;
int attrNum = p->node.attrNum;
if (d.A.at(attrNum) < 0)
return ' ';
return testClassifier(p->childs.at(d.A.at(attrNum)), d);
}

void testData()
{
for (vector<TupleData>::iterator it = test.begin(); it != test.end(); it++)
{
if((*it).label=='+') TestP++;
else TestN++;

int p=0, n=0;
for(int i=0;i<tree_num;i++)
{
if(testClassifier(alltrees.at(i), (*it))=='+')  p++;
else n++;
}

if(p>n)
{
if((*it).label=='+') TP++;
else FP++;
}
else
{
if((*it).label=='+') FN++;
else TN++;
}
}
}


void freeClassifier(decision_tree *p)
{
if (p == NULL)
return;
for (vector<decision_tree*>::iterator it = p->childs.begin(); it != p->childs.end(); it++)
{
freeClassifier(*it);
}
delete p;
}

void freeArrtNum()
{
delete[] ArrtNum;
}

void showResult()
{
cout<<"Train size:    "<< trainAllNum<<endl;
cout<<"Test size:    "<<testAllNum<<endl;    
cout << "True positive:    " << TP << endl;
cout << "False negative:    "<< FN<<endl;
cout << "False positive:    "<<FP<<endl;
cout << "True negative:    "<<TN<<endl;

//     cout << TP << endl;
//     cout << FN<<endl;
//     cout <<FP<<endl;
//     cout <<TN<<endl;
}

int main(int argc, char **argv)
{
char * trainfile=argv[1];
char * testfile=argv[2];

//cout<<"input the F and tree_num"<<endl;
//cin>>F>>tree_num;

srand((unsigned)time(NULL)); 

init(trainfile, testfile);

for(int i=0; i<tree_num; i++)
{
sub_init();
decision_tree * root=NULL;
creat_classifier(root, train, attributes);
alltrees.push_back(root);
}

testData();

for (vector<decision_tree *>::const_iterator it = alltrees.begin(); it != alltrees.end(); it++)
{
freeClassifier((*it));
}

freeArrtNum();

showResult();
return 0;
}

相关博客,可参考如下列表:

http://www.hankcs.com/ml/adaboost.html

http://www.csdn.net/article/2015-09-07/2825629

http://www.csdn.net/article/2015-03-02/2824069

http://www.cnblogs.com/tornadomeet/archive/2012/03/21/2409421.html

http://www.jianshu.com/p/819a21e1e8ef

http://blog.csdn.net/dream_angel_z/article/details/48085889

http://www.tuicool.com/articles/mMb22un

http://www.cnblogs.com/hrlnw/p/3850459.html

http://www.cnblogs.com/emanlee/p/4851555.html

http://blog.csdn.net/nieson2012/article/details/51279332

http://www.cnblogs.com/maybe2030/p/4585705.html

http://blog.csdn.net/jlei_apple/article/details/8168856

相关文章