机器学习-AdaBoost元算法
一、基本原理
元算法是指将不同的分类器组合起来，这种组合结果被称为元算法或集成方法。它可以是不同算法的集成，也可以是同一算法在不同设置下的集成，还可以是数据集的不同部分分配给不同分类器后的集成。
AdaBoost是adaptive boosting（自适应boosting）的缩写，是boosting方法最流行的一个版本。boosting是一种与自举汇聚法很类似的技术，通过集中关注被已有分类器错分的那些数据来获得新的分类器，boosting算法中分类的权重并不相等，每个权重代表的是其对应分类器在上一轮迭代中的成功度。
考虑到二分类情况下，弱分类器的错误率会高于50%，而强分类器的错误率将会低很多，那能否使用弱分类器和多个实例来构建一个强分类器呢？AdaBoost算法为这个问题提供了新的思路。
AdaBoost算法运行过程如下：训练数据中的每个样本，并赋予其一个权重，这些权重构成了向量D，一开始这些权重都初始化成相等值。首先在训练数据上训练出一个弱分类器并计算该分类器的错误率，然后在同一数据集上再次训练弱分类器。在分类器的第二次训练中，将会重新调整每个样本的权重，其中第一次分对的样本的权重将会降低，而第一次分错的样本的权重将会提高。为了从所有弱分类器中得到最终的分类结果，AdaBoost为每个分类器都分配了一个权重值alpha，这些alpha值是基于每个弱分类器的错误率进行计算的。
错误率 e = 未正确分类的样本数目/所有样本数目
alpha = (1/2)ln((1-e)/e)
二、算法流程：
将最小错误率minError设为正无穷
对数据集中的每一个特征（第一层循环）：
对每个步长（第二层循环）：
对每个不等号（第三层循环）：
建立一棵单层决策树并利用加权数据集对它进行测试
如果错误率低于minError，则将当前单层决策树设为最佳单层决策树
返回最佳单层决策树
三、算法的特点
优点：泛化错误率低、易编码，可以应用在大部分分类器上，无参数调整。
缺点：对离群点敏感。
适用数据范围：数值型和标称型。
四、Python 代码实现
1、创建初始训练集
#############################################
#功能：训练集
#输入变量：无
#输出变量：data_mat, class_labels 数据集，类标签
##############################################
def load_simple_data():
data_mat = mat([[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
2、构建单层决策生成树
#############################################
#功能：通过阈值比较对数据进行分类
#输入变量：data_matrix, dimen, thresh_val, thresh_ineq
# 数据集，位数，阈值
#输出变量：ret_array 分类后的数据
##############################################
def stump_classify(data_matrix, dimen, thresh_val, thresh_ineq):
ret_array = ones((shape(data_matrix)[0], 1))
if thresh_ineq == 'lt':
ret_array[data_matrix[:, dimen] <= thresh_val] = -1.0
else:
ret_array[data_matrix[:, dimen] > thresh_val] = -1.0
return ret_array
def build_stump(data_arr, class_labels, d):
data_matrix = mat(data_arr)
label_matrix = mat(class_labels).T
m, n = shape(data_matrix)
num_steps = 10.0
best_stump = {}
best_class_est = mat(zeros((m, 1)))
min_error = inf
for i in xrange(n):
# 计算一列中的最小值与最大值
range_min = min(data_matrix[:, i])
range_max = max(data_matrix[:, i])
step_size = (range_max - range_min)/num_steps
for j in xrange(-1, int(num_steps)+1):
for inequal in ['lt', 'gt']:
thresh_val = range_min + float(j)*step_size
predicted_vals = stump_classify(data_matrix, i, thresh_val, inequal)
print 'predicted_vals=', predicted_vals
error_arr = mat(ones((m, 1)))
error_arr[predicted_vals == label_matrix] = 0
print 'error_arr=', error_arr
weighted_error = d.T * error_arr
print "split: dim %d, thresh_val %.2f, thresh_ineq %s, weighted_error %.3f" %\
(i, thresh_val, inequal, weighted_error)
if weighted_error < min_error:
min_error = weighted_error
best_class_est = predicted_vals
best_stump['dimen'] = i
best_stump['thresh'] = thresh_val
best_stump['ineq'] = inequal
print 'best_stump=', best_stump
return best_stump, min_error, best_class_est
代码测试：
def main():
data_mat, class_labels = load_simple_data()
print data_mat, class_labels
d = mat(ones((5, 1))/5) # 权重向量
print 'd=', d
build_stump(data_mat, class_labels, d)
if __name__ == '__main__':
main()