2019-11-21 18:04:23 sdu_hao 阅读数 49

目录

 

1. 导读

2. 朴素贝叶斯法的学习与分类

3. 朴素贝叶斯法的参数估计

4. 朴素贝叶斯法的参数估计推导

5. 小结


1. 导读

朴素贝叶斯(naive Bayes)法是基于贝叶斯定理与特征条件独立假设的分类方法。对于给定的训练集,首先基于特征条件独立假设学习输入输出的联合概率分布;然后基于此模型,对给定的输入x,利用贝叶斯定理求出后验概率最大的输出y。

统计学习方法的第一章曾对统计学习方法进行了分类,根据模型形式的不同,可以分为决策函数和条件概率分布。在决策函数中,给定一个输入X,通过一个决策函数f,得到预测值Y,即Y=f(X)。在条件概率分布中,给定一个输入X,得到输出Y的条件概率分布P(Y|X),通过这个分布对Y进行决策,如果Y是分类变量,那么就选取概率最大时对应的分类。

统计学习方法可以分为生成模型和判别模型:

1)生成模型:

2)判别模型(有两种形式):

 上述三个分类模型的比较:

                                     Y = f(X) \Rightarrow P(Y|X) \Rightarrow P(Y|X) = \frac{P(X,Y)}{P(X)}

1)Y=f(X)决策函数形式,它不考虑X和Y的随机性;Y的条件概率分布P(Y|X),只考虑了Y的随机性,给定X时,Y有一个概率分布;第三种形式,同时考虑了X,Y的随机性,不仅有Y的条件概率分布,也有X的边际分布以及X和Y的联合分布。所以从左到右,考虑的随机性是越来越多的。

2)之前第二章中我们学习的感知机模型属于决策函数形式。我们现在学习的朴素贝叶斯法,该模型直接从第一种形式到第三种形式,里面用到了重要的贝叶斯公式。

 

2. 朴素贝叶斯法的学习与分类

  • 基本表示

设输入空间\chi \subseteq R^n是n维向量的集合,输出空间为类别标记集合Y =\{c_1,...,c_K\}.输入实例特征向量x \in \chi,输出类别标记y \in Y.

X是定义在输入空间\chi上的随机向量(每个特征/分量是一个随机变量),Y是定义在输出空间Y上的随机变量。P(X,Y)是X和Y的联合(概率)分布。

训练集:T= \{(x_1,y_1),...,(x_N,y_N)\}由联合分布P(X,Y)独立同分布产生。

  • 训练:

朴素贝叶斯法通过训练数据集学习联合概率分布P(X,Y).具体的学习以下先验概率分布和条件概率分布。

先验概率分布:P(Y=c_k),k=1,2,...,K.

条件概率分布:P(X=x|Y=c_k) = P(X^{(1)}=x^{(1)},...,X^{(n)}=x^{(n)}|Y=c_k),k=1,...,K

从而学习到联合概率分布P(X,Y).

但是条件概率分布P(X=x|Y=c_k)有指数级数量的参数(需要计算的概率是指数级的),我们设特征x^{(j)}S_j个取值,j=1,...,n,Y的取值有K个,那么参数有K \prod_{j=1}^{n}S_j个,其估计实际上是不可行的。

条件独立性假设:

朴素贝叶斯法对条件概率分布作了条件独立性假设。因为这是一个较强的假设,所以朴素之名由此而来。具体地,条件独立性假设(简化)是:

朴素贝叶斯法实际上学到生成数据的机制,属于生成模型。条件独立性假设等于用于分类的特征在类确定的条件下都是条件独立的。这一假设使朴素贝叶斯法变得简单,参数量减少,但有时会牺牲一定的分类准确率。

  • 预测

在进行分类时,对于给定的输入x,通过学习到的模型(先验概率分布,条件概率分布)计算后验概率分布P(Y=c_k|X=x),把后验概率最大的类作为x的类别输出。后验概率根据贝叶斯定理计算:

带入条件独立性假设:

所以朴素贝叶斯分类器可以表示为(找到一个类别ck使得上式/后验概率最大):

注意到,上式分母对于所有的c_k都是一样的(与类别c_k无关,相当于一个归一化因子,求整体的最大值等价于求分子的最大值),所以:

  • 小结

  • 后验概率最大化的含义

朴素贝叶斯法将实例分到后验概率最大的类中。这就等价于期望风险最小化。

证明:

 

3. 朴素贝叶斯法的参数估计

在朴素贝叶斯法中,学习意味着估计P(Y=c_k),P(X^{(j)}=x^{(j)}|Y=c_k).有极大似然估计和贝叶斯估计两种方法。

  • 极大似然估计

先验概率P(Y=c_k),k=1,2,...,K的极大似然估计为:

也就是训练数据集中类别为c_k的样本数除以总样本数。

设第j个特征x^{(j)}可能的取值集合为{a_{j1},...,a_{jS_j}},条件概率P(X^{(j)}=a_{jl}|Y=c_k)的极大似然估计为:

也就是训练数据集中类别为c_k的样本的第j个特征取值为a_{jl}的样本数除以类别为c_k的样本数。其中x_i^{(j)}表示第i个样本的第j个特征,a_{jl}表示第j个特征的第l个可能取值。

例题:

  • 贝叶斯估计

极大似然估计可能会出现要估计的概率值(参数)为0的情况,比如当训练样本比较少时,可能某些类的样本不存在,即\sum_{i=1}^{N} I(y_i = c_k) = 0,条件概率的极大似然估计中分母此时会出现为0的情况。这会影响到后验概率的计算结果,使得分类产生偏差。

可以使用贝叶斯估计解决这一问题。也就是进行平滑操作,可以把他的思想理解为“劫富济贫”,不会出现0概率的情况,对于数据集中没有出现的情况也会分配一个小概率,相应地对大概率(出现次数比较多)进行一定的削弱,以保证概率和为1.

条件概率的贝叶斯估计为:

其中\lambda \geq 0.等价于在随机变量各个取值的频数上赋予一个正数\lambda > 0.\lambda = 0时就是极大似然估计。通常取\lambda = 1,称为拉普拉斯平滑。

说明上式是一个概率分布。

先验概率的贝叶斯估计为:

例题:

按照拉普拉斯平滑计算概率,即\lambda = 1.

  • 朴素贝叶斯算法

输入:训练数据集T = \{(x_1,y_1),...,(x_N,y_N)\},其中x_i = (x_i^{(1)},...,x_i^{(n)})^T,x_i^{(j)}表示第i个样本的第j个特征,x_i^{(j)} \in \{a_{j1},...,a_{jS_j}\}表示第i个样本的第j个特征的取值集合(离散),a_{jl}第j个特征可能取的第l个值j=1,...,n;l = 1,...,S_j.y_i \in \{c_1,...,c_K\}.实例特征向量x。

输出:实例x的类别

1)计算先验概率和条件概率(参数估计):

其中j=1,..,n; l = 1,...,S_j;k = 1,...,K;\lambda \geq 0.

2)对于给定的实例x = (x^{(1)},...,x^{(n)})^T,计算:

3)确定实例x的类别:

4. 朴素贝叶斯法的参数估计推导

在本节中对Y分布的估计,以及Y条件下X分布的估计,用到了极大似然估计和贝叶斯估计。这里通过对Y的分布的估计来推导一下极大似然估计和贝叶斯估计得到的结果。

  • 问题描述

随机变量Y的分布是离散的,可能取值为c_1,...,c_K,Y属于多项分布(对于每一个类别,Y的取值都有一个对应的概率\theta_i),\sum_i \theta_i = 1

比如掷硬币,Y出现的结果有两种,正面和反面,正面出现的概率为\theta_1,反面为\theta_2\theta_1 + \theta_2 = 1。如果只有两个结果,Y是二项分布,如果有K个结果,叫做多项分布。

Y的分布为:

  • 极大似然估计

  • 贝叶斯估计

 

 

5. 小结

1)朴素贝叶斯是典型的生成学习方法。生成方法由训练数据学习联合概率分布P(X,Y),然后求得后验概率分布P(Y|X).具体来说通过训练数据学习条件概率分布P(X|Y)和先验概率分布P(Y),得到联合概率分布:

概率(参数)估计可以用极大似然估计或贝叶斯估计。

2)朴素贝叶斯法的基本假设是条件独立性:

这是一个较强的假设。由于这一假设,模型包含的条件概率数量(参数数量)大大减少,朴素贝叶斯法的学习与预测大为简化。因而朴素贝叶斯法高效且易于实现。缺点是分类的性能不一定很高。

3)朴素贝叶斯法利用贝叶斯定理与学到的联合概率模型进行分类预测:

把输入x分到后验概率最大的类y:

后验概率最大等价于0-1损失函数时的期望风险最小化。

 

2019-11-21 22:19:32 sdu_hao 阅读数 32

 

1. 用极大似然估计法推出朴素贝叶斯法中的概率估计公式:

 

2. 用贝叶斯估计法推出朴素贝叶斯法中的概率估计公式:

 

3. 贝叶斯估计求解过程

4. 自编程实现朴素贝叶斯算法,对上述表格中的训练数据进行分类。

"""
朴素贝叶斯算法的实现
2019/4/12
"""
import numpy as np
import pandas as pd


class NaiveBayes():
    def __init__(self, lambda_):
        self.lambda_ = lambda_  # 贝叶斯系数 取0时,即为极大似然估计 非0时为贝叶斯估计
        self.y_types_count = None  # y的(类型:数量)
        self.y_types_proba = None  # y的(类型:概率)
        self.x_types_proba = dict()  # (xi 的编号,xi的取值,y的类型):概率

    def fit(self, X_train, y_train):
        self.y_types = np.unique(y_train)  # y的所有取值类型
        X = pd.DataFrame(X_train)  # 转化成pandas DataFrame数据格式,下同
        y = pd.DataFrame(y_train)
        # y的(类型:数量)统计
        self.y_types_count = y[0].value_counts()
        # y的(类型:概率)计算
        self.y_types_proba = (self.y_types_count + self.lambda_) / (y.shape[0] + len(self.y_types) * self.lambda_)

        # (xi 的编号,xi的取值,y的类型):概率的计算
        for idx in X.columns:  # 遍历xi
            for j in self.y_types:  # 选取每一个y的类型
                p_x_y = X[(y == j).values][idx].value_counts()  # 选择所有y==j为真的数据点的第idx个特征的值,并对这些值进行(类型:数量)统计
                for i in p_x_y.index:  # 计算(xi 的编号,xi的取值,y的类型):概率
                    self.x_types_proba[(idx, i, j)] = (p_x_y[i] + self.lambda_) / (
                            self.y_types_count[j] + p_x_y.shape[0] * self.lambda_)

    def predict(self, X_new):
        res = []
        for y in self.y_types:  # 遍历y的可能取值
            p_y = self.y_types_proba[y]  # 计算y的先验概率P(Y=ck)
            p_xy = 1
            for idx, x in enumerate(X_new):
                p_xy *= self.x_types_proba[(idx, x, y)]  # 计算P(X=(x1,x2...xd)/Y=ck)
            res.append(p_y * p_xy)
        for i in range(len(self.y_types)):
            print("[{}]对应概率:{:.2%}".format(self.y_types[i], res[i]))
        # 返回最大后验概率对应的y值
        return self.y_types[np.argmax(res)]


def main():
    X_train = np.array([
        [1, "S"],
        [1, "M"],
        [1, "M"],
        [1, "S"],
        [1, "S"],
        [2, "S"],
        [2, "M"],
        [2, "M"],
        [2, "L"],
        [2, "L"],
        [3, "L"],
        [3, "M"],
        [3, "M"],
        [3, "L"],
        [3, "L"]
    ])
    #标签
    y_train = np.array([-1, -1, 1, 1, -1, -1, -1, 1, 1, 1, 1, 1, 1, 1, -1])
    #创建朴素贝叶斯分类器对象
    clf = NaiveBayes(lambda_=0.2)
    #训练 计算先验概率和条件概率
    clf.fit(X_train, y_train)
    #预测样本
    X_new = np.array([2, "S"])
    #预测
    y_predict = clf.predict(X_new)
    print("{}被分类为:{}".format(X_new, y_predict))


if __name__ == "__main__":
    main()

 

5. 试分别调用 sklearn.naive_bayes 的 GaussianNB、BernoulliNB、MultinomialNB 模块,对上述表格中训练数据进行分类。

之前碰到的都是特征是离散变量情形,如果特征是连续变量,如身高(如果训练集身高有175,177,如果把他当作离散变量来做,会有问题,比如预测时出现身高=176.5就没办法做了),此时要使用高斯分布。

"""
朴素贝叶斯算法sklearn实现
2019/4/15
"""

import numpy as np
from sklearn.naive_bayes import GaussianNB, BernoulliNB, MultinomialNB
from sklearn import preprocessing  # 预处理


def main():
    X_train = np.array([
        [1, "S"],
        [1, "M"],
        [1, "M"],
        [1, "S"],
        [1, "S"],
        [2, "S"],
        [2, "M"],
        [2, "M"],
        [2, "L"],
        [2, "L"],
        [3, "L"],
        [3, "M"],
        [3, "M"],
        [3, "L"],
        [3, "L"]
    ])
    y_train = np.array([-1, -1, 1, 1, -1, -1, -1, 1, 1, 1, 1, 1, 1, 1, -1])
    #对于离散型特征,我们要进行预处理 使每一个样本在每个特征上的取值为0或1
    #比如第一个样本 的特征为1,S;其中第一个特征有三个取值 第二个特征也有三个取值
    #转换后的特征为 1 0 0 0 0 1 (分别对应 1 2 3 L M S)
    enc = preprocessing.OneHotEncoder(categories='auto')
    enc.fit(X_train)
    X_train = enc.transform(X_train).toarray()
    print(X_train)
    print("---------------")
    clf = MultinomialNB(alpha=0.0000001) #离散变量
    clf.fit(X_train, y_train)
    X_new = np.array([[2, "S"]]) #对预测样本也做相同的转换
    X_new = enc.transform(X_new).toarray() 
    y_predict = clf.predict(X_new)
    print("{}被分类为:{}".format(X_new, y_predict))
    print("---------------")
    print(clf.predict_proba(X_new))  #归一化概率


if __name__ == "__main__":
    main()

 

 

2019-03-02 16:16:45 qq_20095389 阅读数 66

1、思想
  • 最大化最小间隔
  • 拉格朗日乘子法求解
2、推导过程
3、拓展知识点
2019-07-10 16:21:50 Mr_W1997 阅读数 42

项目链接:https://github.com/Wchenguang/gglearn/blob/master/DecisionTree/李航机器学习讲解/DecisionTree.ipynb

'''
特征选择算法
'''

import numpy as np
import math
'''
熵的计算
'''
def entropy(y_values):
    e = 0
    unique_vals = np.unique(y_values)
    for val in unique_vals:
        p = np.sum(y_values == val)/len(y_values)
        e += (p * math.log(p, 2))
    return -1 * e

'''
条件熵的计算
'''
def entropy_condition(x_values, y_values):
    ey = entropy(y_values)
    ey_condition = 0
    xy = np.hstack((x_values, y_values))
    unique_x = np.unique(x_values)
    for x_val in unique_x:
        px = np.sum(x_values == x_val) / len(x_values)
        xy_condition_x = xy[np.where(xy[:, 0] == x_val)]
        ey_condition_x = entropy(xy_condition_x[:, 1])
        ey_condition += (px * ey_condition_x)
    return ey - ey_condition

'''
信息增益比:摒弃了选择取值多的特征为重要特征的缺点
'''
def entropy_condition_ratio(x_values, y_values):
    return entropy_condition(x_values, y_values) / entropy(x_values)

'''
基尼指数计算
'''
def gini(y_values):
    g = 0
    unique_vals = np.unique(y_values)
    for val in unique_vals:
        p = np.sum(y_values == val)/len(y_values)
        g += (p * p)
    return 1 - g

'''
按照x取值的基尼指数的计算
'''
def gini_condition(x_values, y_values):
    g_condition = {}
    xy = np.hstack((x_values, y_values))
    unique_x = np.unique(x_values)
    for x_val in unique_x:
        xy_condition_x = xy[np.where(xy[:, 0] == x_val)]
        xy_condition_notx = xy[np.where(xy[:, 0] != x_val)]
        g_condition[x_val] = len(xy_condition_x)/len(x_values) * gini(xy_condition_x[:, 1]) + len(xy_condition_notx)/len(x_values) * gini(xy_condition_notx[:, 1])
    return g_condition
import operator
class DTNode:
    '''
    决策树节点
    '''
    def __init__(self, x, y, default_label, split_val = None, cart_cols = []):
        self.children = []
        if(len(y) != 0):
            self.label = Counter(y.reshape(1, -1).tolist()[0]).most_common(1)[0][0]
        else:
            self.label = default_label
        self.next_split_index = None
        self.split_val = split_val
        self.x = x.copy()
        self.y = y.copy()
        self.xy = np.hstack([x, y])
        self.default_label = default_label
        self.cart_cols = cart_cols
    def get_x(self):
        return self.x
    def get_y(self):
        return self.y
    def get_xy(self):
        return self.xy
    def get_children(self):
        return self.children
    def get_label(self):
        return self.label
    def get_next_split_index(self):
        return self.next_split_index
    def get_split_val(self):
        return self.split_val
    def _get_real_cols_num(self, arr):
        if(arr.shape[0] == 0):
            return 0
        else:
            return arr.shape[1]
    def _get_x_and_xval(self, calculate_method, threshold):
        '''
        根据所选方法及阈值,计算信息增益(比),选择目标特征, 并计算目标特征取值种类
        '''
        res = {}
        for col_index in range(self._get_real_cols_num(self.x)):
            res[col_index] = calculate_method(self.x[:, col_index].reshape(-1, 1), self.y.reshape(-1, 1))
        if(operator.eq(res, {})):
            return None, None
        else:
            target = sorted(res, key=res.__getitem__, reverse=True)[0]
            if(res[target] < threshold):
                return None, None
            else:
                return target, np.unique(self.x[:, target])
    def _cart_get_x_and_feature(self, calculate_method, threshold, cols):
        '''
        根据所选方法及阈值,计算基尼指数以及均方差,返回最佳划分特征,以及最佳划分特征值
        '''
        res = {}
        for col_index in cols:
            res[col_index] = calculate_method(self.x[:, col_index].reshape(-1, 1), self.y.reshape(-1, 1))
            target = sorted(res[col_index], key=res[col_index].__getitem__)[0]
            res[col_index] = (target, res[col_index][target])
        if(operator.eq(res, {})):
            return None, None
        else:
            target = sorted(res, key = lambda k: res[k][1])[0]
            if(res[target][1] < threshold):
                return None, None
            else:
                return target, res[target][0]
        
    def _build_exit(self):
        if(len(np.unique(self.y)) == 1):
            self.label = np.unique(self.y)[0]
            return True
        elif(operator.eq(self.x.tolist(), [])):
            self.label = self.default_label
            return True
        else:
            return False
        
    def _cart_build_exit(self):
        if(operator.eq(self.x.tolist(), [])):
            self.label = self.default_label
            return True
        else:
            return False
        
    def build_children(self, method, threshold):
        '''
        检测退出条件
        '''
        if(self._build_exit()):
            return 
        '''
        构建子节点
        '''
        if(method == 'information gain'):
            x_index, x_val = self._get_x_and_xval(entropy_condition, threshold)
        else:
            #method == 'information gain ratio'
            x_index, x_val = self._get_x_and_xval(entropy_condition_ratio, threshold)
        '''
        无需分割
        label置为当前最多的label值
        ?
        '''
        if(x_index == None):
            #self.label = self.default_label
            return
        self.next_split_index = x_index
        for val in x_val:
            splited_xy = self.xy[self.xy[:, x_index] == val]
            splited_xy = np.delete(splited_xy, [x_index], axis = 1)
            self.children.append(DTNode(splited_xy[:, :-1], splited_xy[:, -1].reshape(-1, 1), self.default_label, val))
            
    def cart_build_children(self, method, threshold):
        '''
        检测退出条件
        '''
        if(self._cart_build_exit()):
            return 
        '''
        构建子节点
        '''
        if(method == 'gini'):
            x_index, x_val = self._cart_get_x_and_feature(gini_condition, threshold, self.cart_cols)
        if(x_index == None):
            return
        self.next_split_index = x_index
        splited_left_xy = self.xy[self.xy[:, x_index] == x_val]
        splited_right_xy = self.xy[self.xy[:, x_index] != x_val]
        next_cart_cols = self.cart_cols.copy()
        next_cart_cols.remove(x_index)
        self.children.append(DTNode(splited_left_xy[:, :-1], splited_left_xy[:, -1].reshape(-1, 1), 
                                    self.default_label, x_val, cart_cols = next_cart_cols))
        self.children.append(DTNode(splited_right_xy[:, :-1], splited_right_xy[:, -1].reshape(-1, 1), 
                                    self.default_label, x_val, cart_cols = next_cart_cols))
from collections import Counter
class DecisionTree:
    '''
    决策树
    '''
    def __init__(self, method, threshold):
        self.x = None
        self.y = None
        self.root = None
        self.threshold = threshold
        self.default_label = None
        self.method = method
        if(method == 'ID3'):
            self.feature_selection_method = "information gain"
        elif(method == 'cart clf'):
            self.feature_selection_method = "gini"
        else:
            #method == 'C4.5'
            self.feature_selection_method = "information gain ratio"
    def fit(self, x, y):
        self.x = x
        self.y = y
        '''
        筛选默认label,即训练集中频率最高的label
        '''
        self.default_label = Counter(self.y.reshape(1, -1).tolist()[0]).most_common(1)[0][0]
        '''
        宽度遍历建立决策树
        '''
        self.root = DTNode(x, y, self.default_label, cart_cols = list(range(self.x.shape[1])))
        queue = [self.root]
        while(len(queue) > 0):
            node = queue.pop(0)
            if('information' in self.feature_selection_method):
                node.build_children(self.feature_selection_method, self.threshold)
            else:
                node.cart_build_children(self.feature_selection_method, self.threshold)
            queue += node.get_children()
    def show(self):
        '''
        展示各个节点的信息
        '''
        queue = [self.root]
        while(len(queue) > 0):
            node = queue.pop(0)
            print('==============')
            print('node label:', node.get_label())
            print('node split_val', node.get_split_val())
            print('node next_split_index:', node.get_next_split_index())
            print('xy:')
            print(node.get_xy())
            queue += node.get_children()
xy = np.array([[0,0,0,0,0,1,1,1,1,1,2,2,2,2,2], [0,0,1,1,0,0,0,1,0,0,0,0,1,1,0], [0,0,0,1,0,0,0,1,1,1,1,1,0,0,0], 
            [0,1,1,0,0,0,1,1,2,2,2,1,1,2,0], [0,0,1,1,0,0,0,1,1,1,1,1,1,1,0]]).T
dt = DecisionTree(method = 'cart clf', threshold = 0.01)
dt.fit(xy[:, :-1], xy[:, -1].reshape(-1, 1))
dt.show()
xy = np.array([[0,0,0,0,0,1,1,1,1,1,2,2,2,2,2], [0,0,1,1,0,0,0,1,0,0,0,0,1,1,0], [0,0,0,1,0,0,0,1,1,1,1,1,0,0,0], 
           [0,1,1,0,0,0,1,1,2,2,2,1,1,2,0], [0,0,1,1,0,0,0,1,1,1,1,1,1,1,0]]).T
dt = DecisionTree(method = 'ID3', threshold = 0.1)
dt.fit(xy[:, :-1], xy[:, -1].reshape(-1, 1))
dt.show()
2019-07-25 11:34:58 Mr_W1997 阅读数 27

AdaBoost梯度提升算法

项目链接:https://github.com/Wchenguang/gglearn/blob/master/AdaBoost/李航机器学习讲解/AdaBoost.ipynb

算法步骤与原理

  1. 训练 mm 个弱学习分类器,分类器有相同的接口
    Gm(x):X{x1,x2&ThinSpace;} G_{m}(x) : \mathcal{X} \rightarrow\{x_{1},x_{2} \dots\}

  2. 假设数据有均匀的权值分布,即每个样本在分类器中作用相同,$ n $个实例的权重为
    D1=(w11,&ThinSpace;,w1i,&ThinSpace;,w1N),w1i=1N,i=1,2,&ThinSpace;,N D_{1}=\left(w_{11}, \cdots, w_{1 i}, \cdots, w_{1 N}\right), \quad w_{1 i}=\frac{1}{N}, \quad i=1,2, \cdots, N
    对于mm个分类器而言,有$ m \times n $个权重

  3. 进入迭代循环,在每一次循环中进行如下操作

    3.1 计算mm个分类器在加权数据集上的分类错误率
    em=P(Gm(xi)yi)=Cn(xi)yiwmi e_{m}=P\left(G_{m}\left(x_{i}\right) \neq y_{i}\right)=\sum_{C_{n}\left(x_{i}\right) \neq y_{i}} w_{m i}
    3.2 计算每个分类器的权重alphamalpha_{m},该权重表明,每个单独分类器在最终分类器中的重要程度
    αm=12log1emem \alpha_{m}=\frac{1}{2} \log \frac{1-e_{m}}{e_{m}}

    • 由上式可知,随着分类器的误差率的减小,其权重值越大

    3.3 更新数据集的权重分布

    Dm+1=(wm+1,1,&ThinSpace;,wm+1,i,&ThinSpace;,wm+1,N)wm+1,i=wmiZmexp(αm(yi==Gm(xi))),i=1,2,&ThinSpace;,N \begin{array}{c}{D_{m+1}=\left(w_{m+1,1}, \cdots, w_{m+1, i}, \cdots, w_{m+1, N}\right)} \\ {w_{m+1, i}=\frac{w_{m i}}{Z_{m}} \exp \left(-\alpha_{m} (y_{i}== G_{m}\left(x_{i})\right)\right), \quad i=1,2, \cdots, N}\end{array}
    Zm=i=1Nwmiexp(αmyiGm(xi)) Z_{m}=\sum_{i=1}^{N} w_{m i} \exp \left(-\alpha_{m} y_{i} G_{m}\left(x_{i}\right)\right)

    • 由上式可知
      wm+1,i={wmiZmeαm,Gm(xi)=yiwmiZmeαm,Gm(xi)yi w_{m+1, i}=\left\{\begin{array}{ll}{\frac{w_{m i}}{Z_{m}} \mathrm{e}^{-\alpha_{m}},} &amp; {G_{m}\left(x_{i}\right)=y_{i}} \\ {\frac{w_{m i}}{Z_{m}} \mathrm{e}^{\alpha_{m}},} &amp; {G_{m}\left(x_{i}\right) \neq y_{i}}\end{array}\right.
      预测错误的实例,权重提升。预测正确的实例,权重下降。
import numpy as np

class testClf:
    def __init__(self, thresold):
        self.thresold = thresold
        self.x = None
        self.y = None
    def fit(self, x, y):
        self.x = x
        self.y = y
        return self
    def predict(self, x):
        y = x.copy()
        less_index = np.where(y[:, 0] < self.thresold)
        greater_index = np.where(y[:, 0] > self.thresold)
        y[less_index] = 1
        y[greater_index] = -1
        return y
    def fit_predict(self, x, y):
        return self.fit(x, y).predict(x)
        
'''
test_x = np.arange(10).reshape(-1, 1)
test_y = np.array([1,1,1,-1,-1,-1,1,1,1,-1]).reshape(-1, 1)
tc = testClf(2.5)
print(tc.fit_predict(test_x, test_y))
'''
import numpy as np
import matplotlib.pyplot as plt

class AdaBoost:
    def __init__(self, clf_list, iteration_times):
        '''
        分类器需要有相同的fit,predict接口用于训练及预测
        '''
        self.clf_list = clf_list
        self.iteration_times = iteration_times
        self.x_weight_matrix = None
        self.clf_weight = None
    def _em(self, y_predict, y, x_weight):
        y_predict_flag = (y_predict != y).astype(int)
        return np.multiply(y_predict_flag, x_weight).sum()
    def _am(self, em):
        return np.log((1- em) / em) * 0.5
    def _update_x_weight(self, y_predict, y, am, x_weight):
        y_predict_flag = (y_predict == y).astype(int)
        y_predict_flag[np.where(y_predict_flag[:, 0] == 0)] = -1
        zm_array = np.multiply(np.exp(y_predict_flag * am * -1),
                                    x_weight)
        zm_array = zm_array / zm_array.sum()
        return zm_array
    def _fit_once(self, x, y, x_weight, clf_weight):
        for index in range(len(self.clf_list)):
            clf = self.clf_list[index]
            y_predict = clf.fit_predict(x, y)
            em = self._em(y_predict, y, x_weight)
            am = self._am(em)
            x_weight = self._update_x_weight(y_predict, y, am, x_weight)
            clf_weight[index] = am
            print('em', em, 'am', am)
            print('更新后权重')
            print(x_weight)
    def fit(self, x, y):
        m = len(self.clf_list)
        n = x.shape[0]
        if(0 == n or 0 == m):
            return
        self.x_weight = np.full((n, 1), 1/n)
        self.clf_weight = np.full((m, 1), 1/m)
        for i in range(self.iteration_times):
            self._fit_once(x, y, self.x_weight, self.clf_weight)
    def transform(self, x):
        if(self.clf_list == None or 0 == len(self.clf_list)):
            return None
        res = self.clf_weight[0] * self.clf_list[0].predict(x)
        for index in range(1, len(self.clf_list)):
            res += (self.clf_weight[index] * 
                            self.clf_list[index].predict(x))
        return res
test_x = np.arange(10).reshape(-1, 1)
test_y = np.array([1,1,1,-1,-1,-1,1,1,1,-1]).reshape(-1, 1)
adaboost = AdaBoost([testClf(2.5), testClf(8.5), testClf(5.5), ], 1)
adaboost.fit(test_x, test_y)
predict = adaboost.transform(test_x)
predict[np.where(predict[:, 0] < 0)] = -1
predict[np.where(predict[:, 0] >= 0)] = 1
print('predict')
print(predict)
print('truth')
print(test_y)
  • 与书中P140-P41结果相符
  • 书中分类器G3计算应为错误
没有更多推荐了,返回首页