共计 14708 个字符，预计需要花费 37 分钟才能阅读完成。
AdaBoost 是集成学习中的一个常见的算法，它模拟“群体智慧”的原理：将独自体现不佳的模型组合起来能够造成一个弱小的模型。
麻省理工学院 (MIT) 2021 年发表的一项钻研[Diz21] 形容了人们如何辨认假新闻。如果没有背景常识或事实的核查，人们往往很难辨认假新闻。然而依据不同人的教训，通常能够给出一个对于新闻虚实水平的个人见解，这通常比随机猜想要好。如果咱们想晓得一个题目是形容了假相还是假新闻只需随机询问 100 集体。如果超过 50 人说是假新闻，咱们就把它归类为假新闻。
将多个弱学习者的预测组合起来，就造成了一个强学习者，它可能精确地分辨真伪，通过集成学习，咱们模拟了这个概念
Boosting 是最风行的集成学习技术之一。通过建设了一组所谓的弱学习器，即性能略好于随机猜想的模型。将单个弱学习器的输入组合为加权和，代表分类器的最终输入。AdaBoost 是 Adaptive Boosting 的缩写。自适应 Adaptive 是因为一个接一个的建设模型，前一个模型的性能会影响后一个模型的建设过程。
在学习过程中，AdaBoost 算法还会为每个弱学习器调配一个权重，并非每个弱学习器对集成模型的预测都有雷同的影响。这种计算整体模型预测的过程称为软投票，相似的如果每个弱学习器的后果权重相等，咱们称之为说硬投票。
与 Bagging（随机森林）不同，在 Bagging 中，训练的是一组互相独立的独自模型。各个模型彼此不同，因为它们是应用训练数据集的不同随机子集进行训练。随机森林就是基于这个原理，一组独自的决策树造成了集成模型的预测。
而 Boosting 的训练是间断的，单个模型的模型构建过程一个接一个地进行，模型预测的准确性会影响后续模型的训练过程。本文将逐渐解释 AdaBoost 算法到底是如何做到这一点的。这些模型由弱学习器、深度为 1 的简略决策树（即所谓的“decision stumps”，咱们将其翻译为决策树桩）示意，本文将。
为了更不便得逐渐解释 AdaBoost 算法背地的概念，咱们抉择了一个常见的并且简略得数据集：成年人支出的数据集（“Adult”dataset）。
这个数据集也被称为“人口普查支出”数据集，是一个用于二元分类工作得数据集。该数据集蕴含形容生存在美国的人们的数据，包含性别、年龄、婚姻状况和教育等属性。指标变量辨别低于和高于每年 50,000 美元的支出。
为了阐明 AdaBoost 算法的工作原理，我简化了数据集，并且只应用了其中的一小部分。在本文的最初提供代码的下载。
首先载入数据集
import pandas as pd
df=pd.read_csv("<https://archive.ics.uci.edu/ml/machine-learning-databases/adult/adult.data>",
names= ["age",
"workclass",
"fnlwgt",
"education",
"education-num",
"marital-status",
"occupation",
"relationship",
"race",
"sex",
"capital-gain",
"capital-loss",
"hours-per-week",
"native-country",
"income"],
index_col=False)为了具体解释算法是如何工作的，咱们这里只应用 3 个简略的二进制特色：
- 性别：男（是或否）
- 每周工作工夫：>40 小时（是或否）
- 年龄:>50（是或否）
importnumpyasnp
# define input parameter
df['male'] =df['sex'].apply(lambdax : 'Yes'ifx.lstrip() =="Male"else"No")
df['>40 hours'] =np.where(df['hours-per-week']>40, 'Yes', 'No')
df['>50 years'] =np.where(df['age']>50, 'Yes', 'No')
# target
df['>50k income'] =df['income'].apply(lambdax : 'Yes'ifx.lstrip() =='>50K'else"No")
# define dataset
df_simpl=df[['male', '>40 hours','>50 years','>50k income']]
df_simpl=df_simpl.head(10)
df_simpl上面我就用这个简略的数据集来解释 AdaBoost 算法的工作原理。
1、构建第一个弱学习者：找到性能最好的“树桩”
第一步，咱们须要寻找一个弱学习者，它能够对咱们的指标（>50k 支出）进行简略得规定判断，并且要比随机猜想要好。
AdaBoost 能够与多种机器学习算法联合应用。个别状况下咱们会抉择决策树作为弱学习者，这是 AdaBoost 算法最风行的形式：
决策树在所谓的节点处逐渐拆分整个数据集。树中的第一个节点称为根节点，所有节点都在决策节点之后。不再对数据集进行拆分的节点称为终端节点或叶节点。
为了构建出最佳性能的第一个决策树桩。咱们构建可能确定数据集中最有可能辨别支出高于和低于 50k 的决策树模型。
咱们从一个随机抉择的特色开始; 这里的示例特色是“男性”。这个属性只能辨别一个人是不是男人。根节点将整个数据集宰割为一个子集，其中只有男性和所有其余类型的实例。
如果一个子集 (例如 D_1) 蕴含 k 个不同的类，那么一条记录属于类 i 的概率能够形容为 p_i。在上面的图片中，我形容了如何计算左侧末节的基尼不纯度。
咱们演示的简略数据集只蕴含 10 个实例：6 个为男性，4 个为女性。如果咱们察看 6 个“男性”数据样本的子集 D_1，会发现 6 个样本中有 4 个的支出是 50k 或以下，只有 2 个记录支出在 5 万以上。子集 D_1 的随机样本显示支出高于 50k 的概率是 2 / 6 或 1 /3，样本显示支出低于 50k 的概率是 4 / 6 或 2 /3。因而叶子 1(子集 D_1)的基尼系数不纯度为 0.444。
如果咱们对叶子 2 做同样的操作，咱们失去不纯度为 0.375。
因为咱们要比拟根节点“男性”、“>40 小时”和“>50 年”的树桩的性能 / 基尼指数，咱们首先计算根节点“男性”的加权 不纯度作为加权单个叶子的总和。
上面的 Python 代码片段中实现了基尼系数的计算，它只是简略地遍历数据帧的所有列，并执行下面形容的基尼系数计算:
defcalc_weighted_gini_index(attribute, df):
'''
Args:
df: the trainings dataset stored in a data frame
attribute: the chosen attribute for the root node of the tree
Return:
Gini_attribute: the gini index for the chosen attribute
'''d_node=df[[attribute,'>50k income']]
# number of records in the dataset (=10, for the simple example)
n=len(d_node)
# number of values "Yes" and "No" for the target variable ">50k income" in the root node
n_1=len(d_node[d_node[attribute] =='Yes'])
n_2=len(d_node[d_node[attribute] =='No'])
# count "Yes" and "No" values for the target variable ">50k income" in each leafe
# left leafe, D_1
n_1_yes=len(d_node[(d_node[attribute] =='Yes') & (d_node[">50k income"] =='Yes')])
n_1_no=len(d_node[(d_node[attribute] =='Yes') & (d_node[">50k income"] =='No')])
# right leafe, D_2
n_2_yes=len(d_node[(d_node[attribute] =='No') & (d_node[">50k income"] =='Yes')])
n_2_no=len(d_node[(d_node[attribute] =='No') & (d_node[">50k income"] =='No')])
# Gini index of the left leafe
Gini_1=1-(n_1_yes/(n_1_yes+n_1_no)) **2-(n_1_no/(n_1_yes+n_1_no)) **2
# Gini index of the right leafe
Gini_2=1-(n_2_yes/(n_2_yes+n_2_no)) **2-(n_2_no/(n_2_yes+n_2_no)) **2
# weighted Gini index for the selected feature (=attribute) as root node
Gini_attribute= (n_1/n) *Gini_1+ (n_2/n) *Gini_2
Gini_attribute=round(Gini_attribute, 3)
print(f'Gini_{attribute} = {Gini_attribute}')
returnGini_attribute
deffind_attribute_that_shows_the_smallest_gini_index(df):
'''
Args:
df: the trainings dataset stored in a data frame
Return:
selected_root_node_attribute: the attribute/feature that showed the lowest gini index
'''
# calculate gini index for each attribute in the dataset and store them in a list
attributes= []
gini_indexes= []
forattributeindf.columns[:-1]:
# calculate gini index for attribute as root note using the defined function "calc_weighted_gini_index"
gini_index=calc_weighted_gini_index(attribute, df)
attributes.append(attribute)
gini_indexes.append(gini_index)
# create a data frame using the just calculated gini index for each feature/attribute of the dataset
print("Calculated Gini indexes for each attribute of the data set:")
d_calculated_indexes= {'attribute':attributes,'gini_index':gini_indexes}
d_indexes_df=pd.DataFrame(d_calculated_indexes)
display(d_indexes_df)
# Find the attribute for the first stump, the attribute where the Gini index is lowest the thus the Gini gain is highest")
selected_root_node_attribute=d_indexes_df.min()["attribute"]
print(f"Attribute for the root node of the stump: {selected_root_node_attribute}")
returnselected_root_node_attribute
################################################################################################################
# to build the first stump we are using the orginial dataset as the train dataset
# the defined functions identify the features with the highest Gini gain
################################################################################################################
df_step_1=df_simpl
selected_root_node_attribute=find_attribute_that_shows_the_smallest_gini_index(df_step_1)咱们的指标是最小化叶子的基尼不纯度，从而最大化基尼增益，基尼增益是通过两个宰割子集的加权不纯度与整个数据集的不纯度之差来计算的。
通过计算咱们发现工作工夫特色为“>40 小时”的基尼增益最高，所以咱们应用它建设了第一个“树桩”。
AdaBoost 当初会按程序构建“树桩”，然而 AdaBoost 的个性（也是一个问题）是：第一个“树桩”的谬误会影响下一个“树桩”的建模过程。谬误分类的实例在下一棵树中的权重更大，单个“树桩”的后果在集成模型中的加权水平取决于误差有多高。
2、计算“树桩”的误差
在上图中曾经绘制了正确和谬误分类实例的数量：在预测指标变量时，构建的第一个“树桩”只有一个谬误（数据集中只有一个实例是每周工作工夫超过 40 小时但年收入低于 5 万）。数据集中的所有其余实例曾经用这个简略的决策“树桩”正确分类。
为了计算误差值须要为数据集的每条记录引入权重。在第一个“树桩”造成之前，每个实例的权重 w 为 w=1/n，其中 n 对应于数据集的总数据大小，所有权重的总和为 1。
决策树桩产生的误差被简略地计算为“树桩”谬误分类指标变量的所有样本权重的总和。这里谬误分类只有一个，所以第一次运行的误差为 1/10。
上面的函数“calculate_error_for_chosen_stump”用抉择的特色作为根节点（selected_root_node_attribute）计算加权误差。
importhelper_functions
defcalculate_error_for_chosen_stump(df, selected_root_node_attribute):
'''
Attributes:
df: trainings data set
selected_root_node_attribute: name of the column used for the root node of the stump
Return:
df_extended: df extended by the calculated weights and error
error: calculated error for the stump - sum of the weights of all samples that were misclassified by the decision stub
'''
# add column for the sample weight, for the first step its simply defined as 1/n, so the sum of all weights is 1
df["sample_weight"] =1/len(df)
df[selected_root_node_attribute]
df[">50k income"]
# in binary classification, we have two ways to build the tree.
# (1) That attribute and target value show the same value or
# (2) attribute and target value show the opposite value
# we choose the one which shows less errors
# stump_1_incorrect_v1 and stump_1_incorrect_v2 shows the prediction result of the two stumps
df["stump_1_incorrect_v1"] =np.where(((df[selected_root_node_attribute] =="Yes") & (df[">50k income"] =="Yes")) |
((df[selected_root_node_attribute] =="No") & (df[">50k income"] =="No")),0,1)
df["stump_1_incorrect_v2"] =np.where(((df[selected_root_node_attribute] =="Yes") & (df[">50k income"] =="No")) |
((df[selected_root_node_attribute] =="No") & (df[">50k income"] =="Yes")),0,1)
# select the stump with fewer samples misclassified
ifsum(df['stump_1_incorrect_v1']) <=sum(df["stump_1_incorrect_v2"]):
df["chosen_stump_incorrect"] =df['stump_1_incorrect_v1']
else:
df["chosen_stump_incorrect"] =df['stump_1_incorrect_v2']
# drop the columns for the two versions of the tree
df=df.drop(['stump_1_incorrect_v1', 'stump_1_incorrect_v2'], axis=1)
# calculate the error by multiplying sample weight and the column chosen_stump_incorrect
df["error"] =df["sample_weight"] *df["chosen_stump_incorrect"]
error=sum(df["error"])
# data frame extended by the weights, errors, etc.
df_extended=df
# display extended dataset
display(df_extended[[selected_root_node_attribute,">50k income","sample_weight", "chosen_stump_incorrect", "error"]])
# plot calculated weights in a stacked bar-plot
helper_functions.plot_weights(df_extended)
print(f'Error of the stump [{selected_root_node_attribute}] = {error}')
returndf_extended, error
# call function to calculate the weighted error for the selected stump
df_extended_1, error=calculate_error_for_chosen_stump(df_step_1, selected_root_node_attribute)3、计算“树桩”的权重，也就是“发言权”
集成模型的后果是所有“树桩”预测的加权和。所以上面咱们要确认刚刚构建的树的预测对于最终集成模型的重要性。或者换句话说，权重 alpha 有多高。
咱们计算 alpha 的数量如下：
上图左侧显示了 alpha 与“树桩”加权误差之间的关系。对于小谬误，alpha 量很大。对于较大的谬误，alpha 甚至能够取负值。对于第一个树桩的误差为 0.1，所以最初计算的发言权重约为 1.1。
importmatplotlib.pyplotasplt
fromdatetimeimportdatetime
# calculate the amount of say using the weighted error rate of the weak classifier
alpha=1/2*np.log((1-error)/error)
print(f'Amount of say / Alpha = {round(alpha,3)}')
helper_functions.plot_alpha(alpha, error)4、调整样本权重
因为咱们在建模第二个“树桩“时要思考第一个的后果，所以咱们依据第一个的误差来调整样本权值。第一个预测谬误的数据集的记录应该在构建下一个树桩的过程中施展更大的作用，所以首先调整各个样本的权重。
新权重用 alpha 计算如下:
左图显示了正确分类样本的比例，左边的图表显示了谬误分类样本的比例，对新的样本权值进行归一化解决
上面代码计算和绘制新的权重比例:
importmath
defplot_scale_of_weights(alpha, current_sample_weight, incorrect):
alpha_list= []
new_weights= []
ifincorrect==1:
# adjust the sample weights for instances which were misclassified
new_weight=current_sample_weight*math.exp(alpha)
# calculate x and y for plot of the scaling function and new sample weight
foralpha_ninnp.linspace(0, alpha*1.5, num=100):
scale=current_sample_weight*math.exp(alpha_n)
alpha_list.append(alpha_n)
new_weights.append(scale)
else:
# adjust the sample weights for instances which were classified correct
new_weight=current_sample_weight*math.exp(-alpha)
# calculate x and y for plot of the scaling function and new sample weight
foralpha_ninnp.linspace(0, alpha*1.5, num=100):
scale=current_sample_weight*math.exp(-alpha_n)
alpha_list.append(alpha_n)
new_weights.append(scale)
######################################################################################################
# plot scaling of the sample weight
######################################################################################################
# change font size for matplotlib graph
font= {'family': 'arial',
'weight': 'normal',
'size': 15}
plt.rc('font', **font)
plt.plot(alpha_list, new_weights, color='black')
plt.plot(np.linspace(alpha, alpha, num=100), new_weights, color='red')
plt.plot(np.linspace(0, alpha*1.5, num=100), np.linspace(new_weight, new_weight, num=100), color='red')
plt.xlabel('Alpha / Amount of say')
plt.title(f'New_weight (alpha = {round(alpha, 3)}, current_weight = {round(current_sample_weight, 3)}) = {round(new_weight, 3)}')
# define plot name and save the figure
# datetime object containing current date and time
now=datetime.now()
# use timestamp for file name
# dd/mm/YY H:M:S
dt_string=now.strftime("%d_%m_%Y_%H_%M_%S")
plt.savefig(r'.\\plots\\sample_weights_'+dt_string+'.svg')
plt.show()
returnnew_weight
new_weight=plot_scale_of_weights(alpha, current_sample_weight=0.1, incorrect=1)应用下面定义的函数来更新样本权重:
defupdate_sample_weights(df_extended_1):
# calculate the new weights for the misclassified samples
defcalc_new_sample_weight(x, alpha):
new_weight=plot_scale_of_weights(alpha, x["sample_weight"], x["chosen_stump_incorrect"])
returnnew_weight
df_extended_1["new_sample_weight"] =df_extended_1.apply(lambdax: calc_new_sample_weight(x, alpha), axis=1)
# define new extended data frame
df_extended_2=df_extended_1[["male", ">40 hours", ">50 years", ">50k income", "new_sample_weight"]]
df_extended_2=df_extended_2.rename(columns={"new_sample_weight": "sample_weight"}, errors="raise")
# normalize weights
df_extended_2["sample_weight"] =df_extended_2["sample_weight"] *1/df_extended_2["sample_weight"].sum()
df_extended_2["sample_weight"].sum()
returndf_extended_2
df_extended_2=update_sample_weights(df_extended_1)5、第二次运行: 造成一个新的自举数据集
第二次运行还是简略地为每个属性建设一个”树桩 ” 并抉择加权误差最小的，然而这不是一个好方法，所以咱们应用样本权重来生成一个新的数据集，其中权重更大的样本会被认为在统计上更常见。我应用样本权重将范畴 0 - 1 分成若干个 bins。
在上面图片中看到被形容为“cum_sum_low”-“cum_sum_upper”的 bins 的范畴。
而后抉择一个介于 0 和 1 之间的随机数，并查找该数字所属的范畴的 bin，并将样本增加到新数据集中。反复这个过程 N 次，直到我有一个与原始数据集一大小的新数据集。
因为权重更大的样本在 0 到 1 的范畴内会有更大的概率呈现，因而权重更大的样本通常在新数据集中呈现不止一次。在下图中能够看到：第一个谬误分类的样本权重更大（此处权重为 0.5），最终在新数据集中呈现的频率更高。
应用新数据集，咱们持续反复第一步的工作：
- 计算所有特色的基尼系数，抉择特色作为第二个“树桩”的根节点
- 建造第二个树桩
- 将加权误差计算为误分类样本的样本权重之和
####################################################################################
# define bins to select new instances
####################################################################################
importrandom
df_extended_2["cum_sum_upper"] =df_extended_2["sample_weight"].cumsum()
df_extended_2["cum_sum_low"] = [0] +df_extended_2["cum_sum_upper"][0:9].to_list()
####################################################################################
# create new dataset
####################################################################################
new_data_set= []
foriinrange(0,len(df_extended_2),1):
random_number=random.randint(0, 100)*0.01
ifi==0:
picked_instance=df_extended_2[(df_extended_2["cum_sum_low"]<random_number) & (df_extended_2["cum_sum_upper"]>random_number)]
new_data_set=picked_instance
else:
picked_instance=df_extended_2[(df_extended_2["cum_sum_low"]<random_number) & (df_extended_2["cum_sum_upper"]>random_number)]
new_data_set=pd.concat([new_data_set, picked_instance], ignore_index=True)
new_data_set找到第二个 ”” 树桩 ”” 的根节点：
df_step_2=new_data_set[["male", ">50 years", ">50k income"]]
selected_root_node_attribute_2=find_attribute_that_shows_the_smallest_gini_index(df_step_2)6、反复这个过程，直到达到终止条件
算法会反复咱们下面形容的 1 - 5 步，直到达到某个终止条件，例如直到所有特色都被用作根节点一次。所有的步骤总结如下：
- 找到最大化基尼收益的弱学习器 h_t(x)（或者最小化谬误分类实例的误差）
- 将弱学习器的加权误差计算为谬误分类样本的样本权重之和。
- 将分类器增加到集成模型中。模型的后果是对各个弱学习器后果的总结。应用下面确定的“发言权重”/ 加权错误率（alpha）对弱学习者进行加权。
- 更新发言权重：在加权和误差的帮忙下，将 alpha 计算为刚刚造成的弱学习器的“发言权重”。
- 应用这个 alpha 来从新调整样本权重。
- 新的样本权重被归一化，使权重之和为 1
- 应用新的权重，通过在 0 和 1 之间抉择一个随机数 N 次来生成一个新的数据集，而后将数据样本增加到示意该数据集的新数据集中。
- 通过新数据集训练新的弱学习器（与步骤 1 雷同）
7、将弱学习器组合成一个集成模型
到目前为止，咱们只差一个将弱学习器进行组合的过程没有阐明了，这个过程很简略，就是对每个“树桩”进行预测。
对于这个简略的例子，一个 30 岁的人每周工作 42 小时，第一个预测的后果是支出高于 50k，第二个后果是支出低于 50k。
咱们将支出超过 5 万的后果和支出低于 5 万的后果的权重相加。
而后比拟权重的总和。在咱们的例子中，第一个 ” 树桩 ” 的权重占主导地位，因而集成模型的预测是支出 >50k，代码如下：
alpha_step_1=alpha
print(f"Amount of say for the first stump: {round(alpha_step_1,3)}")
alpha_step_2=alpha_step_2
print(f"Amount of say for the second stump: {round(alpha_step_2,3)}")
##########################################################################################
# Make a prediction:
# Suppose a person lives in the U.S., is 30 years old, and works about 42 hours per week.
##########################################################################################
# the first stump uses the hours worked per week (>40 hours) as the root node
# if the regular working hours per week is above 40 hours, the stump would say that the person earns more than 50 k
# otherwise, the income would be classified as below 50 k
F_1=1
# the second stump uses the age (>50 years) as root node
# if you are over 50 years old, you are more likely to have an income of more than 50 k
# in this case, our second weak learner would classifier the target variable (>50 k income) as a 'Yes' or 1
# otherwise as a 'No' or 0
F_2=0
# calculate the result of the ensemble model
F_over_50_k=alpha_step_1*1+alpha_step_2*0
F_below_50_k=alpha_step_1*0+alpha_step_2*1
ifF_over_50_k>F_below_50_k:
print("The person has an income of more than 50 k")
else:
print("The person has an income below 50 k") 总结
Boosting 办法在近年来的多项数据比赛中都获得了优异的问题，但其背地的概念却并不简单。通过应用简略易懂的步骤构建简略并且可解释的模型，而后将简略模型的组合成弱小的学习器。
本文代码：
https://avoid.overfit.cn/post/d99544b82525450fb95110a79bc807ca
作者：Dominik Polzer