一.bagging 和 boosting
在介绍adaboost之前有必要先介绍一下，bagging和boosting算法。
bagging，即可以称之为自举汇聚算法也可以称之为基于数据随机重抽样算法。它的原理就是从原始数据集中，随机抽样出S个和原数据集大小相等的新数据集。因为是随机的抽样因此就要可能有某些部分是重复的，而有些在原始数据集中有的数据在新的数据集中没有。然后利用这S个新数据集，采用同一个分类算法，进行训练就可以得到S个不同的分类器，而后根据这S个分类器得到的结果进行major vote，即可知新的数据的分类。
boosting和bagging类似，但是它更关注上一个分类器分错的数据，并且在投票的时候分类器的权重是不一样的，其值取决于其分类器在上一轮迭代中的成功度。
二.adaboost算法的基本介绍
adaboost算法是基于错误来提升分类的性能。adaboost算法的基本原理是使用弱分类器和多实例来构建强分类器。
adaboost算法的优点是：泛化错误率低，容易编码， 可以应用在大部分的分类器上， 无参数调整
adaboost算法的缺点是：对离群点敏感
adaboost算法适用的数据是：标称型和数值型
adaboost算法的过程。首先用训练集，采用某一个分类算法进行训练，并且初始化每个数据的初始权重相等且和为1， 即可得到一个弱分类器。然后计算出它的错误率，
e = 分错样本权重之和
根据e值计算出该弱分类器的vote权重alpha
alpha = 1/2 * len((1-e)/e)
然后根据得到的alpha值给训练集中每个数据更新权重，总的原则是分对的样本的权重小，分错的样本权重大。常用的方法是：
正确分类样本：Di(t+1) = Di(t)*e^(-alpha)/sum(D)
未正确分类样本： Di(t+1) = Di(t)*e^(alpha)/sum(D)
其中的t表示已经计算出了t个弱分类器
不断的重复以上的过程，直到错误率为0或者弱分类器的个数达到了预设值
三.代码实现
我们采用的弱分类器算法是单层决策树模型。它是决策树的最简单版本，也就是只有一个节点，换句话说就是只根据单个特征进行分类。
首先创建一个简单的数据集：
# create a simple train datadef createsimtra(): datamat = matrix([[1.0, 2.1], [2.0, 1.1], [1.3, 1.0], [1.0, 1.0], [2.0, 1.0]]) classlable = [1.0, 1.0, -1.0, -1.0, 1.0] return datamat, classlable
然后利用利用第i个特征和相应的阈值等对数据进行分类
def stumpclassify(datamat, i, threshold, leri): rearr = ones((shape(datamat)[0], 1)) if leri == 'left': rearr[datamat[:, i] <= threshold] = -1.0 elif leri == 'right': rearr[datamat[:, i] > threshold] = -1.0 return rearr
选择出错误率最小的单层决策树模型
def stump(dataarr, lablearr, d): datamat = mat(dataarr) classlable = mat(lablearr).T minerror = Inf numstep = 10.0 m, n = shape(datamat) beststump = {} bestclasslable = mat(zeros((m, 1))) for i in range(n): rangemin = datamat[:, i].min() rangemax = datamat[:, i].max() stepsize = (rangemax-rangemin)/numstep for j in range(-1, int(numstep)+1): for k in ['left', 'right']: threshold = rangemin + float(j) * stepsize predict = stumpclassify(datamat, i, threshold, k) err = mat(ones((m, 1))) err[predict == classlable] = 0 weighterror = d.T * err if weighterror < minerror: minerror = weighterror beststump['din'] = i beststump['thresh'] = threshold beststump['inqual'] = k bestclasslable = predict.copy() return beststump, bestclasslable, minerror 经典adaboost算法
def adaboost(dataset, datalable, numint): m = shape(dataset)[0] d = mat(ones((m, 1))/m) aggclassest = mat(zeros((m, 1))) weakclass = [] for i in range(numint): beststump, bestclasslable, minerror = stump(datamat, classlable, d) alpha = float(0.5 * log((1 - minerror)/max(minerror, e**(-16)))) beststump['alpha'] = alpha weakclass.append(beststump) expn = multiply(-1*alpha * mat(classlable).T, bestclasslable) d = multiply(d, exp(expn)) d /= d.sum() aggclassest += alpha * bestclasslable aggerror = multiply(sign(aggclassest) != mat(classlable).T, ones((m, 1))) errrate = aggerror.sum()/m if errrate == 0.0: break return weakclass
利用adaboost算法进行分类
def adaclassify(datatoclass, classifyarr): dataclassmat = mat(datatoclass) m = shape(dataclassmat)[0] aggest = mat(zeros((m, 1))) for i in range(len(classifyarr)): classest = stumpclassify(dataclassmat, classifyarr[i]['din'], classifyarr[i]['thresh'], classifyarr[i]['inqual']) aggest += classifyarr[i]['alpha'] * classest print aggest return sign(aggest)
不是一般性，以下是获得数据的函数
def loaddata(filename): length = len(open(filename).readline().split('\t')) fr = open(filename) dataset = [] lableset = [] for line in fr.readlines(): curline = [] currenline = line.strip().split('\t') for j in range(length - 1): curline.append(float(currenline[j])) dataset.append(curline) lableset.append(float(currenline[-1])) return dataset,lableset