Machine Learning in Action Chapter07 Improving classification with the AdaBoost meta-algorithm

Machine Learning in Action Chapter07 Improving classification with the AdaBoost meta-algorithm

元算法(meta-algorithm):当做重要决定时,大家可能都会考虑吸取多个专家而不只是一个人的意见。

元算法是对其他算法进行组合的一种方式。

所有分类器都会遇到的一个通用问题:非均衡分类问题。

基于数据集多重抽样的分类器

集成方法(ensemble method)或元算法(meta-algorithm):将不同的分类器组合起来。

集成方法有很多种,可以是同一算法在不同设置下的集成,还可以是数据集不同部分分配个不同分类器之后的集成。

AdaBoost:

  • 优点:泛化错误率低,易编码,可以应用在大部分分类器上,无参数调整
  • 缺点:对离群点敏感
  • 使用数据类型:数值型和标称型数据

bagging: 基于数据随机重抽样的分类器构建方法

自举汇聚法(bootstrap aggregating),也称为 bagging 方法,是在从原始数据集选择 S 次后得到 S 个新数据集的一种技术。

在 S 个数据集建好之后,将某个学习算法分别作用域每个数据集就得到了 S 个分类器。当我们要对新数据进行分类时,就可以应用这 S 个分类器进行分类。与此同时,选择分类器投票结果中最多的类别作为后的分类结果。

boosting

bagging 中不同的分类器是通过串行训练而获得的,每个新分类器都根据已训练出的分类器的性能来进行训练。boosting 是通过集中关注被已有分类器错分的那些数据来获得新的分类器。

boosting 分类的结果是基于所有分类器的加权求和结果的,权重是对应分类器在上一轮迭代中的成功度;bagging 中的分类器权重是相等的。

AdaBoost 的一般流程:

1
2
3
4
5
(1) 收集数据:可以使用任意方法。 
(2) 准备数据:依赖于所使用的弱分类器类型,本章使用的是单层决策树,这种分类器可 以处理任何数据类型。当然也可以使用任意分类器作为弱分类器,第2章到第6章中的 任一分类器都可以充当弱分类器。作为弱分类器,简单分类器的效果更好。
(3) 分析数据:可以使用任意方法。
(4) 训练算法:AdaBoost的大部分时间都用在训练上,分类器将多次在同一数据集上训练弱分类器。 (5) 测试算法:计算分类的错误率。
(6) 使用算法:同SVM一样,AdaBoost预测两个类别中的一个。如果想把它应用到多个类别的场合,那么就要像多类SVM中的做法一样对AdaBoost进行修改

训练算法:基于错误提升分类器的性能

AdaBoost 是 adaptive boosting (自适应 boosting)的缩写,其运行过程如下:

  • 训练数据中的每个样本被赋予一个权重,构成向量 D,一开始初始化为相等值
  • 首先在训练数据上训练出一个弱分类器并计算该分类器每个样本的错误率
  • 然后在同一数据集上再次训练弱分类器。重新调整每个样本的权重。第一次分对样本的权重将会降低,而第一次分错的样本的权重将会提高。

AdaBoost 为每个分类器都分配了一个权重值 alpha:

错误率 ε 的定义为:

\[\epsilon=\frac{未正确分类的样本数目}{所有样本数目}\]

alpha 的计算公式:

\[\alpha = \frac12 ln(\frac{1-\epsilon}{\epsilon})\]

AdaBoost 的工作流程:

计算出 alpha 值后,可以对权重向量 D 进行更新,使得那些正确分类的样本的权重降低而错分样本的权重升高:

如果某个样本被正确分类:则该样本的权重更新为:

\[D^{t+!}_i=\frac{D^{(t)}_ie^{-\alpha}}{Sum(D)}\]

如果某个样本被错分:则该样本的权重更新为:

\[D^{t+!}_i=\frac{D^{(t)}_ie^{\alpha}}{Sum(D)}\]

在计算出 D 之后,AdaBoost 又开始进入下一轮迭代。AdaBoost 算法会不断地重复训练和调整权重的过程,直到训练错误率为 0 或者弱分类器的数目达到用户的指定值为止。

基于单层决策树构建弱分类器

单层决策树见第二章。

首先建立简单的数据集:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import numpy as np


def load_sim_data():
"""
测试数据,
:return: data_arr feature对应的数据集
label_arr feature对应的分类标签
"""
data_mat = np.matrix([[1.0, 2.1],
[2.0, 1.1],
[1.3, 1.0],
[1.0, 1.0],
[2.0, 1.0]])
class_labels = [1.0, 1.0, -1.0, -1.0, 1.0]
return data_mat, class_labels

数据可视化如下:

我们很难找出一条与坐标轴平行的直线来将所有的圆形点和方形点分开,这显然是不可能的。

单层决策树生成函数:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
def stump_classify(data_mat, dimen, thresh_val, thresh_ineq):
"""
(将数据集,按照feature列的value进行 二分法切分比较来赋值分类)
:param data_mat: Matrix数据集
:param dimen: 特征的哪一个列
:param thresh_val: 特征列要比较的值
:param thresh_ineq:
:return: np.array
"""
ret_array = np.ones((np.shape(data_mat)[0], 1))
# data_mat[:, dimen] 表示数据集中第dimen列的所有值
# thresh_ineq == 'lt'表示修改左边的值,gt表示修改右边的值
# (这里其实我建议理解为转换左右边,就是一棵树的左右孩子,可能有点问题。。。待考证)
if thresh_ineq == 'lt':
ret_array[data_mat[:, dimen] <= thresh_val] = -1.0
else:
ret_array[data_mat[:, dimen] > thresh_val] = -1.0
return ret_array

def build_stump(data_arr, class_labels, D):
"""
得到决策树的模型 (这个比较重要,需要看懂)
:param data_arr: 特征标签集合
:param class_labels: 分类标签集合
:param D: 最初的特征权重值
:return: bestStump 最优的分类器模型
min_error 错误率
best_class_est 训练后的结果集
"""
data_mat = np.mat(data_arr)
label_mat = np.mat(class_labels).T

m, n = np.shape(data_mat)
num_steps = 10.0
best_stump = {}
best_class_est = np.mat(np.zeros((m, 1)))
# 无穷大
min_err = np.inf
for i in range(n):
range_min = data_mat[:, i].min()
range_max = data_mat[:, i].max()
step_size = (range_max - range_min) / num_steps
for j in range(-1, int(num_steps) + 1):
for inequal in ['lt', 'gt']:
thresh_val = (range_min + float(j) * step_size)
predicted_vals = stump_classify(data_mat, i, thresh_val, inequal)
err_arr = np.mat(np.ones((m, 1)))
err_arr[predicted_vals == label_mat] = 0
# 这里是矩阵乘法
weighted_err = D.T * err_arr
'''
dim 表示 feature列
thresh_val 表示树的分界值
inequal 表示计算树左右颠倒的错误率的情况
weighted_error 表示整体结果的错误率
best_class_est 预测的最优结果 (与class_labels对应)
'''
# print('split: dim {}, thresh {}, thresh inequal: {}, the weighted err is {}'.format(
# i, thresh_val, inequal, weighted_err
# ))
if weighted_err < min_err:
min_err = weighted_err
best_class_est = predicted_vals.copy()
best_stump['dim'] = i
best_stump['thresh'] = thresh_val
best_stump['ineq'] = inequal
# best_stump 表示分类器的结果,在第几个列上,用大于/小于比较,阈值是多少 (单个弱分类器)
return best_stump, min_err, best_class_est

完整 AdaBoost 算法的实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
def ada_boost_train_ds(data_arr, class_labels, num_it=40):
"""
adaBoost训练过程放大
:param data_arr: 特征标签集合
:param class_labels: 分类标签集合
:param num_it: 迭代次数
:return: weak_class_arr 弱分类器的集合
agg_class_est 预测的分类结果值
"""
weak_class_arr = []
m = np.shape(data_arr)[0]
# 初始化 D,设置每个特征的权重值,平均分为m份
D = np.mat(np.ones((m, 1)) / m)
agg_class_est = np.mat(np.zeros((m, 1)))
for i in range(num_it):
# 得到决策树的模型
best_stump, error, class_est = build_stump(data_arr, class_labels, D)
# print('D: {}'.format(D.T))
# alpha 目的主要是计算每一个分类器实例的权重(加和就是分类结果)
# 计算每个分类器的 alpha 权重值
alpha = float(0.5 * np.log((1.0 - error) / max(error, 1e-16)))
best_stump['alpha'] = alpha
# store Stump Params in Array
weak_class_arr.append(best_stump)
# print('class_est: {}'.format(class_est.T))
# 分类正确:乘积为1,不会影响结果,-1主要是下面求e的-alpha次方
# 分类错误:乘积为 -1,结果会受影响,所以也乘以 -1
expon = np.multiply(-1 * alpha * np.mat(class_labels).T, class_est)
# 判断正确的,就乘以-1,否则就乘以1, 为什么? 书上的公式。
# print('(-1取反)预测值 expon=', expon.T)
# 计算e的expon次方,然后计算得到一个综合的概率的值
# 结果发现: 判断错误的样本,D对于的样本权重值会变大。
# multiply是对应项相乘
D = np.multiply(D, np.exp(expon))
D = D / D.sum()
# 预测的分类结果值,在上一轮结果的基础上,进行加和操作
# print('叠加前的分类结果class_est: {}'.format(class_est.T))
agg_class_est += alpha * class_est
# print('叠加后的分类结果agg_class_est: {}'.format(agg_class_est.T))
# sign 判断正为1, 0为0, 负为-1,通过最终加和的权重值,判断符号。
# 结果为:错误的样本标签集合,因为是 !=,那么结果就是0 正, 1 负
agg_errors = np.multiply(np.sign(agg_class_est) != np.mat(class_labels).T,
np.ones((m, 1)))
error_rate = agg_errors.sum() / m
# print('total error: {}\n'.format(error_rate))
if error_rate == 0.0:
break
return weak_class_arr, agg_class_est

测试算法:基于 AdaBoost 的分类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def ada_classify(data_to_class, classifier_arr):
"""
通过刚刚上面那个函数得到的弱分类器的集合进行预测
:param data_to_class: 数据集
:param classifier_arr: 分类器列表
:return: 正负一,也就是表示分类的结果
"""
data_mat = np.mat(data_to_class)
m = np.shape(data_mat)[0]
agg_class_est = np.mat(np.zeros((m, 1)))
for i in range(len(classifier_arr)):
class_est = stump_classify(
data_mat, classifier_arr[i]['dim'],
classifier_arr[i]['thresh'],
classifier_arr[i]['ineq']
)
agg_class_est += classifier_arr[i]['alpha'] * class_est
print(agg_class_est)
return np.sign(agg_class_est)

示例:在一个难数据集上应用 AdaBoost

在第 4 章给出的马疝病上应用 AdaBoost 分类器。

开发流程:

1
2
3
4
5
6
收集数据:提供的文本文件
准备数据:确保类别标签是+1和-1,而非1和0
分析数据:统计分析
训练算法:在数据上,利用 adaBoostTrainDS() 函数训练出一系列的分类器
测试算法:我们拥有两个数据集。在不采用随机抽样的方法下,我们就会对 AdaBoost 和 Logistic 回归的结果进行完全对等的比较
使用算法:观察该例子上的错误率。不过,也可以构建一个 Web 网站,让驯马师输入马的症状然后预测马是否会死去

自适应数据加载函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def load_data_set(file_name):
"""
加载马的疝气病的数据
:param file_name: 文件名
:return: 必须要是np.array或者np.matrix不然后面没有,shape
"""
num_feat = len(open(file_name).readline().split('\t'))
data_arr = []
label_arr = []
fr = open(file_name)
for line in fr.readlines():
line_arr = []
cur_line = line.strip().split('\t')
for i in range(num_feat - 1):
line_arr.append(float(cur_line[i]))
data_arr.append(line_arr)
label_arr.append(float(cur_line[-1]))
return np.matrix(data_arr), label_arr

使用上述函数

1
2
3
4
5
6
7
8
9
10
11
12
13
data_mat, class_labels = load_data_set('horseColicTraining2.txt')

weak_class_arr, agg_class_est = ada_boost_train_ds(data_mat, class_labels, 40)

data_arr_test, label_arr_test = load_data_set("horseColicTest2.txt")
m = np.shape(data_arr_test)[0]
predicting10 = ada_classify(data_arr_test, weak_class_arr)
err_arr = np.mat(np.ones((m, 1)))
# 测试:计算总样本数,错误样本数,错误率
print(m,
err_arr[predicting10 != np.mat(label_arr_test).T].sum(),
err_arr[predicting10 != np.mat(label_arr_test).T].sum() / m
)

在弱分类器数目为 50 的时候,达到了较高的性能。之后为过拟合。

非均衡分类问题

在分类器训练时,正例数目和反例数目不相等(相差很大)。或者发生在正负例分类错误的成本不同的时候。

其他分类性能度量指标:正确率、召回率及 ROC 曲线

  • 正确率(Precision):TP/(TP+FP)
  • 召回率(Recall):TP/(TP+FN)
  • ROC 曲线: 最佳的分类器应该尽可能地处于左上角

  • 横轴:FP/(FP+TN),假阳率
  • 纵轴:TP/(TP+FN),真阳率

  • AUC:曲线下面积,分类器的平均性能值,完美分类器的 AUC 为 1,随机猜测为 0.5

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
def plot_roc(pred_strengths, class_labels):
"""
(打印ROC曲线,并计算AUC的面积大小)
:param pred_strengths: 最终预测结果的权重值
:param class_labels: 原始数据的分类结果集
:return:
"""
import matplotlib.pyplot as plt
# variable to calculate AUC
y_sum = 0.0
# 对正样本的进行求和
num_pos_class = np.sum(np.array(class_labels) == 1.0)
# 正样本的概率
y_step = 1 / float(num_pos_class)
# 负样本的概率
x_step = 1 / float(len(class_labels) - num_pos_class)
# np.argsort函数返回的是数组值从小到大的索引值
# get sorted index, it's reverse
sorted_indicies = pred_strengths.argsort()
# 测试结果是否是从小到大排列
# 可以选择打印看一下
# 开始创建模版对象
fig = plt.figure()
fig.clf()
ax = plt.subplot(111)
# cursor光标值
cur = (1.0, 1.0)
# loop through all the values, drawing a line segment at each point
for index in sorted_indicies.tolist()[0]:
if class_labels[index] == 1.0:
del_x = 0
del_y = y_step
else:
del_x = x_step
del_y = 0
y_sum += cur[1]
# draw line from cur to (cur[0]-delX, cur[1]-delY)
# 画点连线 (x1, x2, y1, y2)
# print cur[0], cur[0]-delX, cur[1], cur[1]-delY
ax.plot([cur[0], cur[0] - del_x], [cur[1], cur[1] - del_y], c='b')
cur = (cur[0] - del_x, cur[1] - del_y)
# 画对角的虚线线
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')
# 设置画图的范围区间 (x1, x2, y1, y2)
ax.axis([0, 1, 0, 1])
plt.show()
'''
参考说明:http://blog.csdn.net/wenyusuran/article/details/39056013
为了计算 AUC ,我们需要对多个小矩形的面积进行累加。
这些小矩形的宽度是x_step,因此可以先对所有矩形的高度进行累加,最后再乘以x_step得到其总面积。
所有高度的和(y_sum)随着x轴的每次移动而渐次增加。
'''
print("the Area Under the Curve is: ", y_sum * x_step)

基于代价函数的分类器决策控制

将混肴矩阵的代价 0,1 改为权重,这样正确分类得到的收益也就不一样。这样,就可以选择分类代价最小的分类器。

处理非均衡问题的数据抽样方法

对分类器的训练数据进行改造,即欠抽样和过抽样。

欠抽样意味着复制样例,过抽样意味着删除样例。

Comments

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×