决策边界

发表于 更新于 分类于
本文字数： 8.3k 阅读时长 ≈ 15 分钟

在分类问题上经常会遇到一个名词 - 决策边界。对它有一些了解但是没有很多的认识，同时很难直观去理解高维数据分类问题的决策边界

理清决策边界的概念，同时可视化决策边界

什么是决策边界

对于二分类问题，如果在向量空间中存在一个能够分类数据集的超曲面（hypersurface），使得同一类的数据点在超曲面的同一边，称该超曲面为决策边界（decision boundary）或决策曲面（decision surface）

什么是超平面

超平面是维度比向量空间维度小1的线性子空间，比如3维向量空间的超平面是2维，2维向量空间的超平面是1维

超平面的另一种解释是它的自由度比向量空间维度小1，比如在3维向量空间的2维超平面上，给定（x,y,z）中的任意两点就能确定剩余一点的值

超平面的数学形式如下：

对于二维空间，超平面就是一条直线：\(ax + by + c=0\)

对于三维空间，超平面就是一个平面：\(ax + by + cz + d = 0\)

推广到\(n\)维空间：\(ax + by + cz + ... + x = 0\)

简写成：\(wX + b = 0\)

线性 vs. 非线性

如果决策边界是一个超平面（hyperplane），那么称该分类问题为线性可分的，分类器是线性分类器（linear classifier），反之称之为非线性分类器（nonlinear classifier）

常用线性和非线性分类器

线性分类器

  • 对于线性SVM分类器而言，其前向操作就是一个线性映射，所以它是线性分类器
  • 对于逻辑回归分类器而言，其前向操作是线性映射+sigmoid函数，其是否线性判定比较复杂，参考logistic回归属于线性模型还是非线性模型？，就我个人观察，虽然sigmoid操作增加了非线性因素，但通常以\(p=0.5\)作为分类面进行分类，也就是说，线性映射结果就决定了分类结果，那么可以看成是线性分类器
  • 对于softmax分类器而言，其是逻辑回归对于多分类问题的推广，参考Softmax classifier，同样可看成是线性分类器

非线性分类器

  • 对于神经网络而言，如果没有隐藏层，那么就是一个线性分类器；如果有多个隐藏层就是非线性分类器
  • 对于KNN分类器而言，其分类标准基于训练数据和测试数据的像素差异，不存在分类超平面，所以是非线性分类器

决策边界可视化

可视化决策边界能够有助于算法的理解和改进，实现方式可分为两类：

  1. 单线决策边界：使用一条数据线分隔不同类区域

  2. 基于轮廓的决策边界：利用不同颜色的轮廓包围数据点区域

单线决策边界

这种方式适用于线性分类器，以逻辑回归分类器为例，其类实现地址：lr_classifier.py

数据集scores.csv包含100名学生在2次考试中获得的分数和标签，下载链接

  • https://github.com/navoneel1092283/logistic_regression.git
  • https://download.csdn.net/download/u012005313/11384178
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
# -*- coding: utf-8 -*-

# @Time    : 19-7-18 下午8:51
# @Author  : zj

import numpy as np
from sklearn.model_selection import train_test_split
import pandas as pd
import matplotlib.pyplot as plt
from lr_classifier import LogisticClassifier


def load_scores(data_path, shuffle=True, tsize=0.8):
    df = pd.read_csv(data_path, header=None, sep=',')
    values = np.array(df.values)
    x = values[:, :2]
    y = values[:, 2]

    x_train, x_test, y_train, y_test = train_test_split(x, y, shuffle=shuffle, train_size=tsize)

    return x_train, x_test, y_train, y_test


if __name__ == '__main__':
    scores_path = '/home/zj/data/scores.csv'
    x_train, x_test, y_train, y_test = load_scores(scores_path)

    # 零中心 + 单位方差
    mu = np.mean(x_train, axis=0)
    var = np.var(x_train, axis=0)
    eps = 1e-5
    x_train = (x_train - mu) / np.sqrt(var + eps)
    x_test = (x_test - mu) / np.sqrt(var + eps)

    # 训练分类器
    classifier = LogisticClassifier()
    classifier.train(x_train, y_train, num_iters=5000, batch_size=120, verbose=True)

    # 编辑网络，预测结果
    x_min, x_max = min(x_test[:, 0]) - 0.5, max(x_test[:, 0]) + 0.5
    y_min, y_max = min(x_test[:, 1]) - 0.5, max(x_test[:, 1]) + 0.5
    xx, yy = np.meshgrid(np.arange(x_min, x_max, 0.01), np.arange(y_min, y_max, 0.01))
    x_grid = np.vstack((xx.reshape(-1), yy.reshape(-1))).T
    # 预测结果
    y_pred = classifier.predict(x_grid).reshape(xx.shape)
    # 绘制等高轮廓
    plt.contourf(xx, yy, y_pred, cmap=plt.cm.cool_r)
    # 绘制测试点
    indexs_0 = np.argwhere(y_test == 0).squeeze()
    indexs_1 = np.argwhere(y_test == 1).squeeze()
    plt.scatter(x_test[indexs_0, 0], x_test[indexs_0, 1], c='r', marker='<')
    plt.scatter(x_test[indexs_1, 0], x_test[indexs_1, 1], c='g', marker='8')
    plt.show()

实现步骤如下：

  1. 加载数据
  2. 训练逻辑回归分类器
  3. 编辑网格，预测结果
  4. 绘制轮廓图以及散点图

基于轮廓的决策边界

两类数据决策边界

从上面可知，使用单线决策边界无法实现非线性数据分类，下面使用神经网络分类器实现基于轮廓的决策边界。参考上述实现，替换分类器为神经网络分类器即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
# -*- coding: utf-8 -*-

# @Time    : 19-7-18 下午9:22
# @Author  : zj


import numpy as np
from sklearn.model_selection import train_test_split
import pandas as pd
import matplotlib.pyplot as plt
from nn_classifier import NN
import warnings

warnings.filterwarnings('ignore')


def load_scores(data_path, shuffle=True, tsize=0.8):
    ...
    ...

def draw_decision_boundary(classifier, x, y):
    # 编辑网络，预测结果
    x_min, x_max = min(x[:, 0]) - 0.5, max(x[:, 0]) + 0.5
    y_min, y_max = min(x[:, 1]) - 0.5, max(x[:, 1]) + 0.5
    xx, yy = np.meshgrid(np.arange(x_min, x_max, 0.01), np.arange(y_min, y_max, 0.01))
    x_grid = np.vstack((xx.reshape(-1), yy.reshape(-1))).T
    # 预测结果
    y_pred = classifier.predict(x_grid).reshape(xx.shape)
    # 绘制等高轮廓
    plt.contourf(xx, yy, y_pred, cmap=plt.cm.cool_r)
    # 绘制测试点
    indexs_0 = np.argwhere(y == 0).squeeze()
    indexs_1 = np.argwhere(y == 1).squeeze()
    plt.scatter(x[indexs_0, 0], x[indexs_0, 1], c='r', marker='<')
    plt.scatter(x[indexs_1, 0], x[indexs_1, 1], c='g', marker='8')
    plt.show()


if __name__ == '__main__':
    scores_path = '/home/zj/data/scores.csv'
    x_train, x_test, y_train, y_test = load_scores(scores_path)

    # 零中心 + 单位方差
    mu = np.mean(x_train, axis=0)
    var = np.var(x_train, axis=0)
    eps = 1e-8
    x_train = (x_train - mu) / np.sqrt(var + eps)
    x_test = (x_test - mu) / np.sqrt(var + eps)

    # 训练分类器
    classifier = NN([100], input_dim=2, num_classes=2, learning_rate=5e-2, reg=1e-3)
    classifier.train(x_train, y_train, num_iters=20000, batch_size=256, verbose=True)

    draw_decision_boundary(classifier, x_test, y_test)

多类数据决策边界

cs231n中提供了一个神经网络测试：Putting it together: Minimal Neural Network Case Study，里面实现了3类数据集的分类，并绘制了决策面

数据集是自定义得到的3类数据，每类个数为100，维度为2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def load_data():
    N = 100  # number of points per class
    D = 2  # dimensionality
    K = 3  # number of classes
    X = np.zeros((N * K, D))  # data matrix (each row = single example)
    y = np.zeros(N * K, dtype='uint8')  # class labels
    for j in range(K):
        ix = range(N * j, N * (j + 1))
        r = np.linspace(0.0, 1, N)  # radius
        t = np.linspace(j * 4, (j + 1) * 4, N) + np.random.randn(N) * 0.2  # theta
        X[ix] = np.c_[r * np.sin(t), r * np.cos(t)]
        y[ix] = j
    # lets visualize the data:
    plt.scatter(X[:, 0], X[:, 1], c=y, s=40, cmap=plt.cm.Spectral)
    plt.show()

    np.random.seed(100)
    np.random.shuffle(X)
    np.random.seed(100)
    np.random.shuffle(y)

    return X, y

使用softmax分类器实现结果：

使用2层神经网络（隐藏层神经元个数为100），学习率为1e-0，正则化强度为1e-3，共训练10000轮

多维数据决策边界

如果数据集维度为多维，需要进一步降维才能进行决策边界可视化。有两种方式进行降维操作：

1.利用随机森林分类器等给特征进行重要性评分，得到2个最重要的特征，然后在散点图上绘制决策边界。 2.主成分分析(PCA)或线性判别分析(LDA)等降维技术可用于将N个特征嵌入到2个特征中，从而将N个特征的信息解释或减少为2个特征(n_components = 2)。然后再基于这两个特征在散点图上绘制决策边界。

使用Iris数据集进行测试，其包含3类数据，数据维度为4，参考：iris数据集

参考主成分分析，实现PCA降维操作，完整代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
# -*- coding: utf-8 -*-

# @Time    : 19-7-16 上午9:52
# @Author  : zj

import numpy as np
from sklearn import utils
from sklearn.model_selection import train_test_split
import pandas as pd
import matplotlib.pyplot as plt
import matplotlib as mpl
from nn_classifier import NN


def load_iris(iris_path, shuffle=True, tsize=0.8):
    """
    加载iris数据
    """
    data = pd.read_csv(iris_path, header=0, delimiter=',')

    if shuffle:
        data = utils.shuffle(data)

    species_dict = {
        'Iris-setosa': 0,
        'Iris-versicolor': 1,
        'Iris-virginica': 2
    }
    data['Species'] = data['Species'].map(species_dict)

    data_x = np.array(
        [data['SepalLengthCm'], data['SepalWidthCm'], data['PetalLengthCm'], data['PetalWidthCm']]).T
    data_y = np.array(data['Species'])

    x_train, x_test, y_train, y_test = train_test_split(data_x, data_y, train_size=tsize, test_size=(1 - tsize),
                                                        shuffle=False)

    return x_train, x_test, y_train, y_test


def pca(X, ratio=0.99, **kwargs):
    """
    pca降维
    :param X: 大小为NxM，其中M是个数，N是维度，每个字段已是零均值
    :param ratio: 表示投影均方误差和方差比值，默认为0.99,保持99%的方差
    :param kwargs: 字典参数，如果指定了k值，则直接计算
    :return: 降维后数据
    """
    N, M = X.shape[:2]
    C = X.dot(X.T) / M
    u, s, v = np.linalg.svd(C)

    k = 1
    if 'k' in kwargs:
        k = kwargs['k']
    else:
        while k < N:
            s_k = np.sum(s[:k])
            s_N = np.sum(s)
            if (s_k * 1.0 / s_N) >= ratio:
                break
            k += 1
    p = u.transpose()[:k]
    y = p.dot(X)

    return y, p


def draw_decision_boundary(classifier, x_test, y_test):
    # PCA降维
    y, p = pca(x_test, k=2)
    # 编辑网络，预测结果
    x_min, x_max = min(p[0]) - 0.05, max(p[0]) + 0.05
    y_min, y_max = p[1].min() - 0.05, p[1].max() + 0.05
    xx, yy = np.meshgrid(np.arange(x_min, x_max, 0.001), np.arange(y_min, y_max, 0.001))
    x_grid = np.vstack((xx.reshape(-1), yy.reshape(-1))).T.dot(y)
    y_pred = classifier.predict(x_grid).reshape(xx.shape)
    # 绘制等高轮廓
    plt.contourf(xx, yy, y_pred, cmap=mpl.cm.jet)
    # 绘制测试点
    indexs_0 = np.argwhere(y_test == 0).squeeze()
    indexs_1 = np.argwhere(y_test == 1).squeeze()
    indexs_2 = np.argwhere(y_test == 2).squeeze()
    plt.scatter(p[0, indexs_0], p[1, indexs_0], c='r', marker='<')
    plt.scatter(p[0, indexs_1], p[1, indexs_1], c='g', marker='8')
    plt.scatter(p[0, indexs_2], p[1, indexs_2], c='y', marker='*')
    plt.show()


if __name__ == '__main__':
    iris_path = '/home/zj/data/iris-species/Iris.csv'
    x_train, x_test, y_train, y_test = load_iris(iris_path)

    mu = np.mean(x_train, axis=0)
    var = np.var(x_train, axis=0)
    eps = 1e-8
    x_train = (x_train - mu) / np.sqrt(var + eps)
    x_test = (x_test - mu) / np.sqrt(var + eps)

    # 训练分类器
    classifier = NN([100, 60], input_dim=4, num_classes=3, learning_rate=1e-1, reg=1e-3)
    classifier.train(x_train, y_train, num_iters=30000, batch_size=200, verbose=True)

    draw_decision_boundary(classifier, x_test, y_test)

相关阅读