一 提升方法是什么?
首先介绍两个概念 强可学习,弱可学习
在概率近似正确学习的框架中 , 一个概念(一个类) ,如果存在一个多项式的学习算法 能够学习它,并且正确率很高,那么就称这个概念是强可学习的;
一个概念,如果存在 一个多项式的学习算法能够学习它,学习的正确率仅比随机猜测略好,那么就称这个概念是弱可学习的。
但是事实上已经有学者证明 一个概念是强可学习的充分必要条件是这个概念 是弱可学习的,即二者是等价的。
显而易见,我们学习一个仅仅比随机猜测正确率高的模型是很容易的,但是学习一个正确率很高的模型却是很困难的。如果我们已经学习出一个弱学习模型,根据我们之前的介绍,我们必然可以学习出一个强学习模型。
提升方法要解决的问题就是如何将一个弱学习的模型提升为一个强学习的模型。 它的具体做法是从弱学习算法出发,反复学习,得到一系列弱分类器,然后组合这些弱分类器,构成一个强分类器,这也就是我们的一句古话,三个臭皮匠顶个诸葛亮所表达的含义 。大多数的提升方法是根据改变训练数据的概率分布(训练数据的权值分布),针对不同的训练数据分布调用弱学习算法学习一系列弱分类器。
下面介绍一个具体的提升方法
二 AdaBoost算法
在我们前面的介绍中,大家可能会有一些疑惑,改变训练数据的概率分布是什么东东? 还有多个弱分类器组合成一个强分类器, what? 怎么组合?一头雾水…
我现在这里简单的介绍一下,让大家有那么一点头绪,之后再看下面的就会恍然大悟。
AdaBoost初始时,会给所有的训练样本一样的权值,假如我们的训练集中有N个训练样本,所有训练样本的权值就都是1/N , 之后每迭代完一轮,训练好一个弱分类器后都会重新更新这些样本的权值,提高那些被前一轮弱分类器错误分类样本的权值,而降低那些被正确分类样本的权值。这样可以使下一轮弱分类器重点关注被上一轮弱分类器错误分类的样本。
至于组合弱分类器,是给每一个弱分类器G(x)一个权值 a 之后让所有弱分类器和它们的权值的乘积做一个加和运算,得到我们的强分类器。权值是根据弱分类器的误差值来分配的,误差越大的弱分类器,它的权值越小,这就使得在构建强分类器时,误差大的弱分类器起的作用比较小,误差小的弱分类器起的作用比较大。
简单回答了以上两个问题,我们正式来认识一下AdaBoost这个厉害的朋友吧 !
AdaBoost算法流程
输入: 训练集 T={(x1,y1),(x2,y2),…,(xN,yN)}
![](https://img.laitimes.com/img/_0nNw4CM6IyYiwiM6ICdiwiIyVGduV2YfNWawNyZuBnLxcDNwMDN0EjMwETMxAjMwIzLc52YucWbp5GZzNmLn9Gbi1yZtl2Lc9CX6MHc0RHaiojIsJye.png)
AdaBoost算法在初始时会给每一个样本一个权值
1 初始权值为 1/N
2 M是设定的一个迭代轮次 每迭代一轮都会生成一个弱分类器, 我们需要迭代 第2步–第5步 M 次 若完成迭代 则继续往下进行 6
基于当前训练数据以及其权值分布Dm 进行训练,得到分类器Gm(x) m=1,2,…,M
3 计算Gm(x) 在训练数据集上的分类误差率
Gm(X) 在加权的训练数据集上的分类误差率是被 Gm(X) 误分类样本的权值之和
4 计算Gm(x) 的系数
5 进行权值更新
其中 Zm 称作规范化因子
更新训练数据的权值分布的公式可以写成这样
两式相比较可知 被误分类样本的权值被放大了
倍
误分类样本在下一轮学习中起更大的作用
6 构建基本分类器的线性组合
得到最终分类器
下面给大家讲解一个例子
我们根据这个例子看AdaBoost算法到底怎么进行的
样本序号 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
---|---|---|---|---|---|---|---|---|---|---|
样本点 X | (1,5) | (2,2) | (3,1) | (4,6) | (6,8) | (6,5) | (7,9) | (8,7) | (9,8) | (10,2) |
类别Y | 1 | 1 | -1 | -1 | 1 | -1 | 1 | 1 | -1 | -1 |
三 Python实现Adaboost
代码实现基于以上讲解
class Gx:
def __init__(self,feature,split,coef,left,right):
#一个分布 这个分布是以哪个feature 作为划分的 划分点 split是 这个分布的系数是coef
self.feature=feature
self.split= split
self.coef=coef
self.left_class =left#小于切分点的类
self.right_class = right #大于切分点的类
class Adaboost:
def __init__(self,Train,Test,M):
self.Train = Train
self.Test = Test
self.w=[1/(self.Train.shape[0])]* self.Train.shape[0] #赋初值,权重的初值是 1/ 训练样本的个数
self.feature_num = self.Train.shape[1] - 1 # 求特征个数 因为训练数据的最后一列是标签 所以特征数等于维度数减一
self.label = self.Train.shape[1] - 1 # 标签所在列
self.Gx = []
self.M = M # 迭代次数
self.split=self.cal_split()
def cal_split(self):
# 因为数据的特征都是连续值 计算每一个特征的切分点
split={}
for i in range(self.feature_num):
split[i]=[] #将某一个特征的所有切分点放到一个列表中
d = self.Train[np.argsort(self.Train[:, i])] # 以这个特征的大小来进行排序
for j in range(d.shape[0]-1):
sp=(d[j][i]+d[j+1][i])/2
if sp not in split[i]: #可能有的切分点是重复的 这一步去重
split[i].append(sp)
return split
def cal_class(self,data):
#返回数据中正类和负类的占比
positive =0
negative =0
for i in range(data.shape[0]):
if data[i][self.label]==1:
positive+=1
else:
negative+=1
return positive/data.shape[0] , negative/data.shape[0]
def cal_error(self,feature,split,left,right):
#计算按某个分布的误差
error=0
for i in range(self.Train.shape[0]):
if (self.Train[i][feature] <= split and self.Train[i][self.label]!=left) or (self.Train[i][feature] > split and self.Train[i][self.label]!=right):
error+=self.w[i]
return error
def cal_Gx(self): #求误差最小的分布
min_error=sys.maxsize #最小误差 李航书上的 em
min_Gx=None #最小误差对应的分布
min_a=0
for i in range(self.feature_num): #遍历每一个特征
for j in self.split[i]: #遍历切分点
left = self.Train[(self.Train[:, i] <= j),: ]
right = self.Train[(self.Train[:, i] > j),: ]
p1,n1=self.cal_class(left)
p2,n2=self.cal_class(right)
if p1>p2:
left_class=1
right_class=-1
else:
left_class = -1
right_class = 1
error=self.cal_error(i,j,left_class,right_class)
a = 1/2*math.log((1-error)/error)
if error < min_error:
min_error=error
min_Gx=Gx(i,j,a,left_class,right_class)
min_a = a
self.Gx.append(min_Gx)
return min_a,min_Gx
def cal_Zm(self,a,Gx):
#计算规范化因子Zm
Zm=0
for i in range(self.Train.shape[0]):
y=self.Train[i][self.label]
feature=Gx.feature
split=Gx.split
if self.Train[i][feature]<=split:
g=Gx.left_class
else:
g=Gx.right_class
Zm+= self.w[i]*math.exp(-a*y*g)
return Zm
def update_w(self,Zm,a,Gx):
# 更新权值w
for i in range(self.Train.shape[0]):
y = self.Train[i][self.label]
feature = Gx.feature
split = Gx.split
if self.Train[i][feature] <= split:
g = Gx.left_class
else:
g = Gx.right_class
self.w[i]=self.w[i] * math.exp(-a * y * g) / Zm
def cal_fx(self,X):
#计算 f(x)
fx=0
for gx in self.Gx:
feature = gx.feature
split = gx.split
left=gx.left_class
right=gx.right_class
a=gx.coef
if X[feature]<=split:
g = left
else:
g=right
fx +=a*g
return fx
def sign_fx(self,fx):
# 计算 sign(f(x))
if fx>0:
return 1
elif fx<0:
return -1
else:
return 0
def fit(self):
for i in range(self.M):
print(i)
min_a, min_Gx=self.cal_Gx()
Zm=self.cal_Zm(min_a,min_Gx)
self.update_w(Zm,min_a,min_Gx)
print(self.predict())
def predict(self):
right=0
for i in range(self.Test.shape[0]):
y=self.sign_fx(self.cal_fx(self.Test[i]))
if y==self.Test[i][self.label]:
right+=1
return right / self.Test.shape[0]
调用代码
数据基于sklearn的datasets中的breast_cancer数据集
breast_cancer=datasets.load_breast_cancer()
data1=breast_cancer.data
data2=breast_cancer.target
data2.resize([data2.shape[0],1])
for i in range(data2.shape[0]):
if data2[i][0]==0:
data2[i][0] =-1
data=np.concatenate((data1,data2), axis=1)
train_size = int(len(data) * 0.7)#划分训练集与测试集
train = np.array(data[:train_size])
# print(X_train.shape)
test=np.array(data[train_size:])
model=Adaboost(train,test,100)
model.fit()
print(model.predict())