第5章 神经网络

  • 5.3 对于图 5.7 中的 ,试推导出 BP 算法中的更新公式 (5.13)。

按照链式法则:

其中,

所以,

  • 5.5 试编程实现标准 BP 算法和累积 BP 算法,在西瓜数据集 3.0 上分别用这两个算法训练一个单隐层网络,并进行比较。

预测算法

将阈值合并入权值,隐层输出的计算方式为:

输出层的计算方式为:

训练算法

import pandas as pd
import numpy as np


# Model
class SingleHiddenBP:

    input_number = 0
    hidden_number = 0
    output_number = 0
    w = v = np.array([])
    learning_rate = 0
    learning_round = 0
    batch_learning = False

    def __init__(self, input_number, hidden_number, output_number,
                 learning_rate=1, learning_round=100, batch_learning=False):
        self.input_number = input_number
        self.hidden_number = hidden_number
        self.output_number = output_number
        self.w = np.random.rand(hidden_number+1, output_number)
        self.v = np.random.rand(input_number+1, hidden_number)
        self.learning_rate = learning_rate
        self.learning_round = learning_round
        self.batch_learning = batch_learning

    def fit(self, X, Y):
        for time in range(0, self.learning_round):
            batch_delta_w = batch_delta_v = 0
            for i in range(0, len(X)):
                x, b, temp_y = self.__predict__(X[i])
                # Training hidden layer
                g = temp_y*(1-temp_y)*(Y[i]-temp_y)
                delta_w = np.outer(b, g) * self.learning_rate
                if self.batch_learning:
                    batch_delta_w += delta_w
                else:
                    self.w += delta_w
                # Training hidden layer
                e = b*(1-b)*np.matmul(self.w, g)
                e = e[:-1]
                delta_v = np.outer(x, e) * self.learning_rate
                if self.batch_learning:
                    batch_delta_v += delta_v
                else:
                    self.v += delta_v
            if self.batch_learning:
                self.w += batch_delta_w
                self.v += batch_delta_v

    def predict(self, x):
        return self.__predict__(x)[2]

    def __predict__(self, x):
        # Input layer
        x = np.append(x, [1])
        # Hidden layer
        b = self.__sigmoid__(np.matmul(x, self.v))
        b = np.append(b, [1])
        # Output layer
        y = self.__sigmoid__(np.matmul(b, self.w))
        return x, b, y

    @staticmethod
    def __sigmoid__(x):
        return 1/(1+np.exp(-x))

# Read data
data = pd.read_csv('data3.0.csv')
X = np.array(data[['色泽', '根蒂', '敲声', '纹理', '脐部', '触感', '密度', '含糖率']])
y = np.array(data['好瓜'])

# Convert discrete value to integer
mapper = [
{'浅白': 0, '青绿': 1, '乌黑': 2},
{'硬挺': 0, '稍蜷': 1, '蜷缩': 2},
{'清脆': 0, '浊响': 1, '沉闷': 2},
{'清晰': 0, '稍糊': 1, '模糊': 2},
{'平坦': 0, '稍凹': 1, '凹陷': 2},
{'软粘': 0, '硬滑': 1}]
X = X.transpose()
for i in range(0, len(mapper)):
    X[i] = [mapper[i][val] for val in X[i]]
X = X.transpose()
X = X.astype(dtype=float)
y = (y == '是')

no_better = tied = batch_better = 0
for r in range(0, 100):
    # Training
    model = SingleHiddenBP(8, 8, 1)
    model_batch = SingleHiddenBP(8, 8, 1, batch_learning=True)
    model.fit(X, y)
    model_batch.fit(X, y)
    # Test
    acc = acc_batch = 0
    for i in range(0, len(X)):
        acc += (model.predict(X[i])>0.5)[0] == y[i]
        acc_batch += (model_batch.predict(X[i]) > 0.5)[0] == y[i]
    if acc > acc_batch:
        no_better += 1
    elif acc < acc_batch:
        batch_better += 1
    else:
        tied += 1

# Report
print("(%d:%d:%d)" % (no_better, tied, batch_better))

在学习率为1,学习轮数为100的情况下,对标准BP和累积BP各训练100次,累积BP优于标准BP。

(15:34:51)
  • 5.7 根据式 (5.18) 和(5.19),试构造一个能解决异或问题的单层 RBF 神经网络。

异或问题的函数表为:

+1 +1 -1
+1 -1 +1
-1 +1 +1
-1 -1 -1

可以考虑在空间中放置四个点,通过就算样本取值点到四个点的距离来获得结果:

  • 5.8 从网上下载或自己编程实现 SOM 网络,并观察其在西瓜数据集 3.0a 上产生的结果。

这里使用的SOM实现是sompy。

import matplotlib.pylab as plt
%matplotlib inline
import pandas as pd
import numpy as np
import sompy
# Read data
data = pd.read_csv('data3.0a.csv')
X = np.array(data[['密度','含糖率']])
y = np.array(data['好瓜']) == '是'

绘制图形观察样本的分布,其中绿色表示好瓜,红色表示不好瓜。

# Plot data
fig = plt.figure()
for i in range(0, len(X)):
    if y[i]:
        plt.plot(X[i,0],X[i,1],'og')
    else:
        plt.plot(X[i,0],X[i,1],'or')
fig.set_size_inches(5,5)

png

对SOM进行训练:

# Training
som = sompy.SOMFactory.build(X, [10, 10])
som.train()

我们按照映射结果对样本进行聚类:

v = sompy.mapview.View2DPacked(50, 50, 'test',text_size=8)  
cl = som.cluster(n_clusters=2)
v.show(som, what='cluster')

png

第6章 支持向量机

直接使用LIBSVM比较麻烦,可以使用scikit-learn中的SVM。

  • 6.1 试证明样本空间中任意点到超平面(w, b)的距离为式(6.2)。

超平面的法向量是,我们在超平面上随便找一个点,然后可以得到超平面上一点到的线段的向量,将这条线段投影到法向量上就可以得到到超平面的距离:

  • 6.2 试使用LIBSVM,在西瓜数据集3.0a上分别用线性核和高斯核训练一个SVM,并比较其支持向量的差别。

默认的参数下,训练得到的SVM的准确率是非常低的,为了提交准确率,需要增大C来提高损失函数的比重。当SVM到达最大的准确率时,其支持向量如下:

import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
from sklearn import svm, datasets
# Read data
data = pd.read_csv('data3.0.csv')
X = np.array(data[['密度', '含糖率']])
y = np.array(data['好瓜']) == '是'

使用线性核训练SVM:

linear_model = svm.SVC(kernel='linear', C=100)
linear_model.fit(X, y)
print('准确率:', np.sum(linear_model.predict(X) == y) / len(X))
print('支持向量:', linear_model.support_)
准确率: 0.823529411765
支持向量: [ 8  9 11 12 13 14 16  2  3  4  5  6  7]

使用高斯核训练SVM:

gaussian_model = svm.SVC(kernel='rbf', C=10000)
gaussian_model.fit(X, y)
print('准确率:', np.sum(gaussian_model.predict(X) == y) / len(X))
print('支持向量:', gaussian_model.support_)
准确率: 1.0
支持向量: [11 13 14  1  5  6]
  • 6.3 选择两个UCI数据集,分别用线性核和高斯核训练一个 SVM,并与BP神经网络和C4.5决策树进行实验比较。

测试数据:Iris Data SetWine Data Set

测试程序:watermelon-book-6-3.ipynb

测试结果:

  Iris Wine
线性核SVM 1.0 0.98
高斯核SVM 1.0 0.42
BP神经网络 0.98 0.40
C4.5决策树 0.98 0.91
  • 6.7 试给出式(6.52)的完整KKT条件。
  • 6.8 以西瓜数据集3.0a的“密度”为输入,“含糖率”为输出,试使用LIBSVM训练一个 SVR。
import numpy as np
import pandas as pd
from sklearn import svm

# Read data
data = pd.read_csv('data3.0.csv')
x = np.array(data['密度']).reshape([-1,1])
y = np.array(data['含糖率'])

# Training
model = svm.SVR(kernel='linear')
model.fit(x, y)
  • 6.9 试使用核技巧推广对率回归,产生“核对率回归”。

为了讨论方便,我们将合并入

在对率回归中引入映射得到

按照表示定理

对率回归的似然对数函数就可以表示为

对似然函数可以采用梯度下降法求解,似然函数的梯度函数为

实验程序的测试结果如下:

png

png

png

图中绿色越深表示是好瓜的可能性越大,红色表示不是好瓜的可能性,其中线性核的性能甚至不如普通的对率回归。由于自己对于优化技术不够了解,暂时无法分析出原因。

第7章 贝叶斯分类器

  • 7.1 试使用极大似然法估算西瓜数据集 3.0 中前 3 个属性的类条件概率。

条件概率的估计公式为:

计算程序:

import pandas as pd
import numpy as np

# Read data
data = pd.read_csv('data3.0.csv')
X = np.array([data['色泽'], data['根蒂'], data['敲声']])
y = np.array(data['好瓜'])

# Calculate condition probability
p = {}
for i in range(0, len(X)):
    values = np.unique(X[i])
    for value in values:
        print("p(%s|是) = %s" % (value, np.sum(np.logical_and(X[i] == value, y == '是')) / np.sum(y == '是')))
        print("p(%s|否) = %s" % (value, np.sum(np.logical_and(X[i] == value, y == '否')) / np.sum(y == '否')))

计算结果:

p(乌黑|是) = 0.5
p(乌黑|否) = 0.222222222222
p(浅白|是) = 0.125
p(浅白|否) = 0.444444444444
p(青绿|是) = 0.375
p(青绿|否) = 0.333333333333
p(硬挺|是) = 0.0
p(硬挺|否) = 0.222222222222
p(稍蜷|是) = 0.375
p(稍蜷|否) = 0.444444444444
p(蜷缩|是) = 0.625
p(蜷缩|否) = 0.333333333333
p(沉闷|是) = 0.25
p(沉闷|否) = 0.333333333333
p(浊响|是) = 0.75
p(浊响|否) = 0.444444444444
p(清脆|是) = 0.0
p(清脆|否) = 0.222222222222
  • 7.3 试编程实现拉普拉斯修正的朴素贝叶斯分类器,并以西瓜数据集 3.0 为训练集,对 P.151 “测 1” 样本进行判别。

学习过程需要首先计算类先验概率:

对于离散属性,属性类条件概率计算方法为:

对于连续属性,属性条件概率计算方法为:

朴素贝叶斯的生成模型为:

import pandas as pd
import numpy as np
import scipy.stats


# Naive bayes
class NaiveBayes:
    p_class = {}
    p_attr = []
    tags = []

    def fit(self, X, y):
        assert len(X) > 0
        # Calculate class probabilities
        self.tags = np.unique(y)
        for tag in self.tags:
            self.p_class[tag] = (np.sum(y == tag) + 1) / (len(y) + len(self.tags))
        # Calculate attribute conditional probabilities
        attributes = np.transpose(X)
        for attr in attributes:
            if type(attr[0]) is str:
                self.p_attr.append(self.__discrete_attr_prob__(attr, y))
            elif type(attr[0]) is float:
                self.p_attr.append(self.__continuous_attr_prob__(attr, y))

    def predict(self, x):
        sum = 0
        prob = np.array([])
        for tag in self.tags:
            p = self.p_class[tag]
            for i in range(0, len(x)):
                if self.p_attr[i]['type'] == 'discrete':
                    p *= self.p_attr[i][(x[i], tag)]
                elif self.p_attr[i]['type'] == 'continuous':
                    p *= scipy.stats.norm(self.p_attr[i][('mean', tag)], self.p_attr[i][('sd', tag)]).pdf(x[i])
            prob = np.append(prob, p)
            sum += p
        prob /= sum
        ans = {}
        for i in range(0, len(self.tags)):
            ans[self.tags[i]] = prob[i]
        return ans

    @staticmethod
    def __discrete_attr_prob__(x, y):
        attr = {'type': 'discrete'}
        values = np.unique(x)
        for val in values:
            for tag in np.unique(y):
                attr[(val, tag)] = (np.sum(np.logical_and(x == val, y == tag)) + 1) / (np.sum(y == tag) + len(values))
        return attr

    @staticmethod
    def __continuous_attr_prob__(x, y):
        attr = {'type': 'continuous'}
        for tag in np.unique(y):
            sub = x[np.where(y == tag)]
            attr[('mean', tag)] = np.mean(sub)
            attr[('sd', tag)] = np.sqrt(np.var(sub))
        return attr


# Read data
data = pd.read_csv('data3.0.csv')
X = np.array(data[['色泽', '根蒂', '敲声', '纹理', '脐部', '触感', '密度', '含糖率']])
y = np.array(data['好瓜'])

# Training
model = NaiveBayes()
model.fit(X, y)
print(model.predict(['青绿', '蜷缩', '浊响', '清晰', '凹陷', '硬滑', 0.697, 0.460]))

得到结果:

{'否': 0.0022497679464180179, '是': 0.99775023205358193}
  • 7.6 试编程实现 AODE 分类器,并以西瓜数据集 3.0 为训练集,对 p.151的“测 1” 样本进行判别。

AODE分类器的生成模型为:

AODE分类器中先验概率的计算方法为:

AODE分类器只支持离散变量,然而西瓜数据集 3.0 中存在着连续变量,可以使用MDLP离散化将连续值转换为离散值。

import pandas as pd
import numpy as np
from mdlp.discretization import MDLP


class AODE:
    tags = []
    num_tags = 0
    num_features = 0
    prob_joint = []
    prob_cond = []

    def fit(self, X, y):
        # Update meta data of model
        self.tags = np.unique(y)
        self.num_tags = len(self.tags)
        features = np.transpose(X)
        self.num_features = len(features)
        # Calculate joint probability
        self.prob_joint = np.empty([self.num_tags, self.num_features], dtype=dict)
        for c in range(0, self.num_tags):
            for i in range(0, self.num_features):
                self.prob_joint[c][i] = self.__prob_joint__(X, y, self.tags[c], i, self.num_tags)
        # Calculate conditional probability
        self.prob_cond = np.empty([self.num_tags, self.num_features, self.num_features], dtype=dict)
        for c in range(0, self.num_tags):
            for i in range(0, self.num_features):
                for j in range(0, self.num_features):
                    self.prob_cond[c][i][j] = self.__prob_conditional__(X, y, self.tags[c], i, j)

    def predict(self, x):
        ans = {}
        prob = []
        for c in range(0, self.num_tags):
            p = 0
            for i in range(0, self.num_features):
                temp = self.prob_joint[c][i][x[i]]
                for j in range(0, self.num_features):
                    temp *= self.prob_cond[c][i][j][(x[i], x[j])]
                p += temp
            prob = np.append(prob, p)
        sum = np.sum(prob)
        for i in range(0, len(prob)):
            ans[self.tags[i]] = prob[i] / sum
        return ans

    @staticmethod
    def __prob_joint__(X, y, tag, i, n):
        prob = {}
        values = np.unique(X[:, i])
        for val in values:
            prob[str(val)] = (np.sum(np.logical_and(X[:,i] == val, y == tag)) + 1) / (len(X) + n * len(values))
        return prob

    @staticmethod
    def __prob_conditional__(X, y, tag, i, j):
        prob = {}
        values_i = np.unique(X[:, i])
        values_j = np.unique(X[:, j])
        for vi in values_i:
            for vj in values_j:
                a = np.sum(np.logical_and(np.logical_and(X[:, i] == vi, X[:, j] == vj), y == tag)) + 1
                b = np.sum(np.logical_and(X[:, i] == vi, y == tag)) + len(values_j)
                prob[(str(vi), str(vj))] = a / b
        return prob


# Read data
data = pd.read_csv('data3.0.csv')
X = np.array(data[['色泽', '根蒂', '敲声', '纹理', '脐部', '触感']])
y = np.array(data['好瓜'])

# MDLP discretization
transformer = MDLP(min_depth=1)
X_desc = transformer.fit_transform(np.asarray(data[['密度', '含糖率']]), np.asarray(y == '是', dtype=int))
X = np.append(X.T, X_desc.T).reshape([8, -1]).T

# Training
model = AODE()
model.fit(X, y)

# Predict
x_predict = np.array(['青绿', '蜷缩', '浊响', '清晰', '凹陷', '硬滑'])
x_predict = np.append(x_predict, transformer.transform(np.array([[0.697, 0.460]])))
print(model.predict(x_predict))

得到结果:

{'否': 0.015102815096227133, '是': 0.98489718490377287}
  • 7.7 给定 d 个二值属性的二分类任务,假设对于任何先验概率项的估算至少需 30 个样例,则在朴素贝叶斯分类器式 (7.15) 中估算先验概率项P(c) 需 302 = 60 个样例。试估计在 AODE 式 (7.23) 中估算先验概率项 所需的样例数(分别考虑最好和最坏情形)。

最好情形

个样例。其中60个一类样例和60个二类样例,对于每一类样例集合,每一个属性上,两种取值的样例数目各为30。

最坏情形

个样例。令每个属性取值为,假设对于每一个样本的所有属性,只有一项属性的取值为a,其他均为b,这就是最坏情形。

  • 7.8 考虑图 7.3,试证明:在同父结构中,若 的取值未知,则 不成立;在顺序结构中,,但 不成立。

在同父结构中

的取值未知

不成立。

在顺序结构中

因此,和同父结构类似 不成立。

第8章 集成学习

  • 8.1 假设抛硬币正面朝上的概率为p,反面朝上的概率为1-p。令H(n)代表抛n次硬币所得正面朝上的次数,则最多k次正面朝上的概率为

​ 对,有Hoeffding不等式 ​ 试推导出式(8.3)。

如果基分类器的错误率

那么满足

因此有

  • 8.3 从网上下载或自己编程实现AdaBoost,以不剪枝决策树为基学习器,在西瓜数据集3.0a加上训练一个 AdaBoost集成,并与图8.4进行比。
import pandas as pd
import numpy as np
import matplotlib.pyplot as plt
from sklearn.tree import DecisionTreeRegressor
from sklearn.ensemble import AdaBoostRegressor
data = pd.read_csv('data3.0.csv')
y = np.array(data['好瓜']) == '是'
X = np.vstack([np.asarray(data['密度']), np.asarray(data['含糖率'])])
X = np.transpose(X)
model = AdaBoostRegressor(DecisionTreeRegressor())
model.fit(X, y);
for i in range(0, len(X)):
    if y[i]:
        plt.plot(X[i,0], X[i,1], 'go')
    else:
        plt.plot(X[i,0], X[i,1], 'ro')
test_x = np.arange(0.2, 0.8, 0.02)
test_y = np.arange(0.0, 0.5, 0.02)
test_data = np.transpose([np.tile(test_x, len(test_y)), np.repeat(test_y, len(test_x))])
test_out = model.predict(test_data)
for i in range(0, len(test_data)):
    if test_out[i]:
        plt.plot(test_data[i,0], test_data[i,1], 'gx', alpha=0.5)
    else:
        plt.plot(test_data[i,0], test_data[i,1], 'rx', alpha=0.5)
plt.xlabel('密度')
plt.ylabel('含糖率')
plt.show()

png

  • 8.5 试编程实现Bagging,以决策树桩为基学习器,在西瓜数据集3.0a加上训练一个Bagging集成并与图8.6进行比较。

如果我们需要T个基学习器,Bagging算法利用自助法获取T个数据集,然后使用这T个数据集训练出T个基学习器,然后将T个基学习器返回结果中出现最多的类作为最终的分类结果。

import matplotlib.pyplot as plt
import pandas as pd
import numpy as np
from bagging import Bagging
from decision_tree import DecisionTree
# Plot data and decision boundary
def plot(X, y, model):
    for i in range(0, len(X)):
        if y[i] == '是':
            plt.plot(X[i,0], X[i,1], 'go')
        elif y[i] == '否':
            plt.plot(X[i,0], X[i,1], 'ro')
    for i in range(0, model.num_base):
        tree = model.classifiers[i].tree
        index = tree['index']
        divider = tree['divider']
        minv = model.minvs[i]
        maxv = model.maxvs[i]
        if index == 0:
            plt.vlines(divider, minv[1], maxv[1], linestyles='dashed')
        elif index == 1:
            plt.hlines(divider, minv[0], maxv[0], linestyles='dashed')
    for x in np.arange(0.2, 0.8, 0.02):
        for y in np.arange(0.0, 0.5, 0.02):
            if model.predict([x, y]) == '是':
                plt.plot(x, y, 'go', alpha=0.2, markeredgewidth=0)
            elif model.predict([x, y]) == '否':
                plt.plot(x, y, 'ro', alpha=0.2, markeredgewidth=0)
    plt.xlabel('密度')
    plt.ylabel('含糖率')
    plt.title('%d个基学习器' % model.num_base)
    plt.show()
# Read data
data = pd.read_csv('data3.0.csv')
y = np.array(data['好瓜'])
X = np.vstack([np.asarray(data['密度']), np.asarray(data['含糖率'])])
X = np.transpose(X)

由于基学习器是决策树桩,因此单个基学习器的表现是非常差的。在学习器数量比较少的时候,集成分类器的表现也是不尽人意,可以从分类可视化图中看到,也就是11个学习器的表现可以接受。

# Training
model = Bagging(DecisionTree(max_depth=1), 3)
model.fit(X, y)
plot(X, y, model)

model = Bagging(DecisionTree(max_depth=1), 5)
model.fit(X, y)
plot(X, y, model)

model = Bagging(DecisionTree(max_depth=1), 11)
model.fit(X, y)
plot(X, y, model)

png

png

png

参考资料

  1. CS231n Convolutional Neural Networks for Visual Recognition
  2. 1.4. Support Vector Machines — scikit-learn 0.19.1 documentation
  3. A Guide to TF Layers: Building a Convolutional Neural Network
  4. Not So Naive Bayes: Aggregating One-Dependence Estimators

相关资源

  1. Bagging实现:bagging.py
  2. 决策树实现:decision_tree.py
  3. 单隐层BP神经网络实现:single_hidden_bp.py
  4. 西瓜数据集3.0:data3.0.csv