机器学习：集成算法 - bagging、boosting、adaboost
不同的分类算法各有优缺点，可以将不同的分类器组合起来
这种组合被称为集成方法（ensemble method）或者元算法（meta-algorithm）
使用集成方法有多种形式
?○?可以是不同算法的集成
?○?可以是同一算法在不同设置下的集成
?○?可以是数据集不同部分分配给不同分类器之后的集成
bagging （Bootstrap aggregating，引导聚集算法，又称装袋算法）
- 随机采样：在一个有 m 个样本的数据集中，每次采集一个样本，然后将该样本放回，共采集 m 个样本形成新的数据集，这样原始数据集中有些样本会被重复采集，有些样本则不会被采集，形成的新的数据集和原数据集大小相等，理论上 m 足够大的情况下平均会有约 36% 的样本不会被采集
- 重复 S 次得到 S 个新数据集
- 将某个学习算法分别作用于每个数据集就得到了 S 个分类器
- 对新数据进行分类时，应用这 S 个分类器进行分类，选择分类器投票结果中最多的类别作为最后的分类结果
随机森林（random forest, RF）
和普通的 bagging 差不多，在其基础上做了一点改进
?○?使用 S 个 CART 决策树作为弱学习器
?○?假设样本特征数为 a，则每次生成 CART 树都是随机选择 a 中的 k 个特征
boosting（提升算法）
- 与 bagging 类似，不同的是 bagging 的各个分类器是独立训练出来的，而 boosting 的每个分类器是根据已训练出的分类器的性能来进行训练
- boosting 是通过集中关注被已有分类器错分的那些数据来获得新的分类器
- boosting 分类的结果是基于所有分类器的加权求和，而 bagging 中的分类器权重是相等的
- boosting 公式
??
??\(\large f(x)= \sum_{i=1}^{n}(a_{i}f_{i}(x))\)
?? - boosting 是串行过程，不好并行化，这是它的一个缺点
- boosting 有多种算法比如 adaboost、GBDT、xgboost
adaboost（adaptive boosting - 自适应 boosting）
adaboost 可以应用于任意分类器，只要将该分类器改造成能够处理加权数据即可
其运行过程如下
- 对每个样本赋予一个权重，这些权重构成向量 D，一开始 D 初始化成相等值： \(\Large \frac{1}{样本数}\)
- 先在训练数据上训练出一个弱分类器 \(\large f(x)\) 并按照样本权值 D 计算该分类器的错误率
??\(\large e = \sum D_{i}\)????其中 \(\large i\) 为分类错误的数据 - 每个分类器也有一个权重值，该值基于每个弱分类器的错误率进行计算的，公式为
??\(\large \alpha = \frac{1}{2} ln(\frac{1-e}{e})\) - 这里要有 \(\large e<0.5\) 以保证 \(\large \alpha>0\)，分类器也不应该出现错误大于一半的情况，否则应忽略
- 然后在同一数据集上再次训练弱分类器，这次会调整每个样本的权重，上一次分对的样本的权重将会降低，分错的样本的权重将会提高，同时基于上个分类器权值 \(\small \alpha\) 计算
??正确分类则
????\(\Large D_{i-new} = \frac{D_{i-old}\ e^{(-\alpha)}}{\sum_{j=1}^{n}D_{j-old}\ e^{(-\alpha)}}\)
?
??错误分类则
????\(\Large D_{i-new} =\frac{D_{i-old}\ e^{(\alpha)}}{\sum_{j=1}^{n}D_{j-old}\ e^{(\alpha)}}\)
??
??将分类结果标记为 1 和 -1，这样统一写为
?
????\(\Large D_{i-new} = \frac{D_{i-old}\ e^{(-\alpha y_{i}f(x_{i}))}}{\sum_{j=1}^{n}D_{j-old}\ e^{(-\alpha y_{j}f(x_{j})))}}\) - 累加分类结果为
??\(\Large y = sign(\sum_{i=1}^{n}(\alpha_{i}f_{i}(x)))\) - 不断迭代直到总错误率为 0 或者弱分类器的数目达到用户的指定值为止
??\(\Large 总错误率 = \frac{累加分类结果错误数}{总样本数}\)
adaboost 代码
# coding=utf-8
import numpy as np
def stumpClassify(dataMatrix, dimen, threshVal, threshIneq):
"""
单层决策树 (decision stump，也称决策树桩)
它仅基于单个特征来做决策，由于只有一次分裂过程，实际上就是一个树桩
单层决策树的分类能力比较弱，是一种弱分类器，通过 adaboost 使用多个单层决策树可以构建强分类器
dataMatrix - 要分类的数据集 (n, m) 矩阵
dimen - 用于分类的特征
threshVal - 判断分类的阀值
threshIneq - 操作符 ('lt', 'gt') 决定是特征值大于阀值返回分类 -1，还是小于阀值返回分类 -1
"""
# 初始化分类矩阵，默认为分类 1
retArray = np.ones((np.shape(dataMatrix)[0], 1))
if threshIneq == 'lt':
# 当 dataMatrix[x, dimen] <= threshVal 时，将 retArray[x] 改为 -1
retArray[dataMatrix[:, dimen] <= threshVal] = -1.0
else:
retArray[dataMatrix[:, dimen] > threshVal] = -1.0
return retArray
def buildStump(dataArr, classLabels, D):
"""
按照样本权值，寻找最佳的单层决策树，即寻找最佳的分类特征和分类阀值，以及操作符
dataArr - 样本数据
classLabels - 标签数据
D - 样本权值
"""
# 初始化矩阵并获取矩阵大小
dataMatrix = np.mat(dataArr)
labelMat = np.mat(classLabels).T
n, m = np.shape(dataMatrix)
# 阀值数
# 将特征值从最大值到最小值之间，取 10 个间隔分出 11 个阀值，在这些阀值中选取最佳值
numSteps = 10.0
# 用于存储最佳决策树的配置，包括（特征，阀值，操作符）
bestStump = {}
# 用于保存最佳决策树的分类结果
bestClasEst = np.mat(np.zeros((n, 1)))
# 用于保存最佳决策树的错误率
minError = np.inf
# 遍历每一个特征
for i in range(m):
# 取该特征的最大最小值以及步长
rangeMin = dataMatrix[:, i].min()
rangeMax = dataMatrix[:, i].max()
stepSize = (rangeMax - rangeMin)/numSteps
# 遍历所有阀值
for j in range(0, int(numSteps) + 1):
# 遍历操作符
for inequal in ['lt', 'gt']:
# 取阀值
threshVal = (rangeMin + float(j) * stepSize)
# 以 (特征，阀值，操作符) 作为决策树，对所有数据分类
predictedVals = stumpClassify(dataMatrix, i, threshVal, inequal)
# 评估分类结果，正确分类为 1，错误分类为 0
errArr = np.mat(np.ones((n, 1)))
errArr[predictedVals == labelMat] = 0
# 计算错误率, D 的初始值是 1/(样本总数)
weightedError = D.T*errArr
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):
"""
基于单层决策树的 adaboost 训练
dataArr - 样本数据
classLabels - 样本标签
numIt - 最大迭代次数
"""
# 用于保存决策树列表
# 每次迭代会产生一个决策树, 直到达到最大迭代次数, 或是最终错误率为 0
weakClassArr = []
# 样本数
n = np.shape(dataArr)[0]
# 初始化样本权值 D，每个数据的权重为 1/(样本数)
D = np.mat(np.ones((n, 1))/n)
# 保存累加分类结果
aggClassEst = np.mat(np.zeros((n, 1)))
for i in range(numIt):
# 按样本和权值寻找最佳决策树
# 返回决策树配置(特征，阀值，操作符), 错误率, 分类结果
bestStump, error, classEst = buildStump(dataArr, classLabels, D)
# 计算决策树权值 alpha = 0.5 * ln((1-err)/err)
# 1e-16 是防止 err 为 0 的情况, ln(1/1e-16) 的结果为 36.8
# 这里没处理 err > 0.5 导致 alpha < 0 的情况, 照理说也不应该出现这种情况
alpha = float(0.5 * np.log((1.0 - error)/max(error, 1e-16)))
# 将决策树权值加入到决策树配置
bestStump['alpha'] = alpha
# 将决策树配置加入决策树列表
weakClassArr.append(bestStump)
# 计算新的样本权值
# D(i_new) = (D(i_old) * exp(-alpha * yi * f(xi))) / SUM_j_1_n (D(j_old) * exp(-alpha * yj * f(xj)))
expon = np.multiply(-1 * alpha * np.mat(classLabels).T, classEst)
D = np.multiply(D, np.exp(expon))
D = D/D.sum()
# 该决策树的分类结果, 按权值算入累加分类结果
aggClassEst += alpha*classEst
# 计算累加分类结果的错误率, 如果错误率为 0 则退出迭代
aggErrors = np.multiply(np.sign(aggClassEst) != np.mat(classLabels).T, np.ones((n, 1)))
errorRate = aggErrors.sum()/n
if errorRate == 0.0:
break
# 返回决策树配置列表, 累加分类结果
return weakClassArr, aggClassEst
def adaClassify(datToClass, classifierArr):
"""
使用决策树列表进行分类
weakClassArr - 要分类的数据
classifierArr - 决策树配置列表
"""
dataMatrix = np.mat(datToClass)
n = np.shape(dataMatrix)[0]
aggClassEst = np.mat(np.zeros((n, 1)))
# 遍历决策树
for i in range(len(classifierArr)):
# 分类
classEst = stumpClassify(dataMatrix,
classifierArr[i]['dim'],
classifierArr[i]['thresh'],
classifierArr[i]['ineq'])
# 按权值累加分类结果
aggClassEst += classifierArr[i]['alpha']*classEst
# sign 函数：大于 0 返回 1，小于 0 返回 -1，等于 0 返回 0
return np.sign(aggClassEst)
????
???? 相关推荐
Pokemogo 2020-11-16
lwnylslwnyls 2020-11-06
Micusd 2020-11-19
人工智能 2020-11-19
81510295 2020-11-17
jaybeat 2020-11-17
flyfor0 2020-11-16
lgblove 2020-11-16
Pokemogo 2020-11-16
clong 2020-11-13
lizhengjava 2020-11-13
ohbxiaoxin 2020-11-13
Icevivian 2020-11-13
EchoYY 2020-11-12
CSDN人工智能头条 2020-11-11
mogigo00 2020-11-11
jaybeat 2020-11-10
白飞飞Alan 2020-11-11
lemonade 2020-11-10