双十一憋在寝室炼丹

在这次作业中，我们将尝试提取基本的图像特征并使用提取的特征进行图像分类。

你需要在TODO模块的 """你的代码""" 中填写相应的代码。

你也可以添加任意数量的 cell 来辅助你完成实验。

1
2
3
4
5
6
7
8
9
10
11
import random
import numpy as np
import matplotlib.pyplot as plt
from past.builtins import xrange
%matplotlib inline
plt.rcParams['figure.figsize'] = (15., 12.) # 设置默认大小
plt.rcParams['image.interpolation'] = 'nearest'
plt.rcParams['image.cmap'] = 'gray'

%load_ext autoreload
%autoreload 2
The autoreload extension is already loaded. To reload it, use:
  %reload_ext autoreload

数据加载

理解该数据集的类型以及访问方式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# 读取提供的cifar10-mini数据集，
data = np.load('cifar10-mini.npz')

X_train= data['X_train']
X_val= data['X_val']
X_test= data['X_test']
y_train= data['y_train']
y_val= data['y_val']
y_test= data['y_test']

# 打印数据shape
print(X_train.shape)
print(X_val.shape)
print(X_test.shape)
(5000, 32, 32, 3)
(500, 32, 32, 3)
(500, 32, 32, 3)

提取图像特征

方向梯度直方图 HOG (Histogram of Oriented Gridients)特征检测算法，最早是由法国研究员Dalal等在CVPR-2005上提出来的，一种解决人体目标检测的图像描述子，是一种用于表征图像局部梯度方向和梯度强度分布特性的描述符。其主要思想是：在边缘具体位置未知的情况下，边缘方向的分布也可以很好的表示图像中物体的外形轮廓，但会忽略掉颜色信息。特征维度是144维

颜色直方图 (color histogram)特征则是提取图像的颜色信息并忽略掉纹理信息。因此同时使用这两种特征的分类效果会好于仅使用单一特征，【加分项】你可以尝试进行对比实验验证这一假设

hog_feature 和 color_histogram_hsv 两个函数都是接收一张图像然后返回这张图像的特征向量。你可以使用这两个函数中的一个提取所有图像的特征并将其存入 X_train_feats, X_val_feats, X_test_feats 这三个变量中（他们分别代表训练集、验证集和测试集的特征）。

如果你遇到了错误 ImportError: No module named past.builtins，可以在终端中执行 pip install future

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
from features import *

################################################################################
# TODO:                                                                        #
# 你需要使用 hog_feature, color_histogram_hsv 两个函数完成特征的提取           #
# 你可以在 features.py 中查看这两个函数的代码                                  #
################################################################################
"""你的代码"""

feature_fns = [hog_feature, lambda img: hog_feature(img)]
# feature_fns = [hog_feature, lambda img: color_histogram_hsv(img)]

X_train_feats = extract_features(X_train, feature_fns, verbose=True)
X_val_feats = extract_features(X_val, feature_fns)
X_test_feats = extract_features(X_test, feature_fns)

################################################################################
#                                 END OF YOUR CODE                             #
################################################################################

    
# 预处理: 减去均值
mean_feat = np.mean(X_train_feats, axis=0, keepdims=True)
X_train_feats -= mean_feat

mean_feat = np.mean(X_val_feats, axis=0, keepdims=True)
X_val_feats -= mean_feat

mean_feat = np.mean(X_test_feats, axis=0, keepdims=True)
X_test_feats -= mean_feat

# 预处理: 除以标准差，这能保证所有的值在 0～1 之间
std_feat = np.std(X_train_feats, axis=0, keepdims=True)
X_train_feats /= std_feat

std_feat = np.std(X_val_feats, axis=0, keepdims=True)
X_val_feats /= std_feat

std_feat = np.std(X_test_feats, axis=0, keepdims=True)
X_test_feats /= std_feat

# 预处理: 增加一个偏置值，在 K-NN 中，该步操作并无必要，但增加偏置值对其他分类器如 SVM 等有帮助。
X_train_feats = np.hstack([X_train_feats, np.ones((X_train_feats.shape[0], 1))])
X_val_feats = np.hstack([X_val_feats, np.ones((X_val_feats.shape[0], 1))])
X_test_feats = np.hstack([X_test_feats, np.ones((X_test_feats.shape[0], 1))])
Done extracting features for 1000 / 5000 images
Done extracting features for 2000 / 5000 images
Done extracting features for 3000 / 5000 images
Done extracting features for 4000 / 5000 images

使用 k-NN 算法对图像进行分类

使用上面提取的特征执行 k-NN 算法对图像分类，在这里，【加分项】你也可以实验对比使用 HOG特征、颜色直方图特征与使用图像原始特征（像素）哪个好。或者尝试特征拼接。

这里你需要补全KNearestNeighbor类中的部分关键函数的代码，包括compute_distances_one_loop,compute_distances_two_loop,compute_distances_no_loop

你可能需要认真阅读玩下面两篇文章后才能完成这部分作业：

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
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
class KNearestNeighbor(object):
    """ 使用L2距离的kNN分类器 """
    def __init__(self):
        pass
    
    def train(self, X, y):
        """ 
        训练分类器 
        
        输入：
        - X: 一个形状为(num_train, D)的numpy数组，包含训练数据。
        - y: 一个形状为(num_train,)的numpy数组，包含训练标签，其中 y[i]是X[i]的标签。
        """
        self.X_train = X
        self.y_train = y
    
    def predict(self, X, k=1, num_loops=0):
        """
        使用该分类器预测测试数据的标签。
        
        输入：
        - X: 一个形状为(num_test, D)的numpy数组，包含测试数据。
        - k: 为预测标签投票的近邻的数量。
        - num_loops: 决定使用哪种方法来计算训练点和测试点之间的距离。训练点和测试点之间的距离。
        
        输出：
        - y: 一个形状为(num_test,)的numpy数组，包含测试数据的预测标签。测试数据的预测标签，其中y[i]是测试点X[i]的预测标签。
        """
        if num_loops == 0:
            dists = self.compute_distances_no_loops(X)
        elif num_loops == 1:
            dists = self.compute_distances_one_loop(X)
        elif num_loops == 2:
            dists = self.compute_distances_two_loops(X)
        else:
            raise ValueError('Invalid value %d for num_loops' % num_loops)

        return self.predict_labels(dists, k=k)

    def compute_distances_two_loops(self, X):
        """
        计算X中每个测试点和self.X_train中每个训练点之间的距离。
        需要使用一个嵌套循环。

        输入:
        - X：一个形状为(num_test, D)的numpy数组，包含测试数据。

        输出:
        - dists: 一个形状为(num_test, num_train)的numpy数组，其中dists[i, j] 是第i个测试点和第j个训练点之间的欧几里得距离。
        """
        num_test = X.shape[0]
        num_train = self.X_train.shape[0]
        dists = np.zeros((num_test, num_train))
        for i in xrange(num_test):
            for j in xrange(num_train):
                #####################################################################
                # TODO:                                                             #
                # 计算第i个测试点和第j个训练点之间的l2距离，并将结果存入dists[i, j]中
                #####################################################################
                """你的代码"""
                
                dists[i, j] = np.linalg.norm(X[i] - self.X_train[j])

                #####################################################################
                #                       END OF YOUR CODE                            #
                #####################################################################
        return dists

    def compute_distances_one_loop(self, X):
        """
        计算X中每个测试点和self.X_train中每个训练点之间的距离。
        只需在测试数据上进行一次循环。

        输入/输出。与compute_distances_two_loops相同
        """
        num_test = X.shape[0]
        num_train = self.X_train.shape[0]
        dists = np.zeros((num_test, num_train))
        for i in xrange(num_test):
            #######################################################################
            # TODO:                                                               #
            # 计算第i个测试点和所有训练点之间的l2距离，并将结果存入dists[i, :]中。#
            #######################################################################
            """你的代码"""
            
            dists[i] = np.linalg.norm(X[i]-self.X_train, axis=1)

            #######################################################################
            #                         END OF YOUR CODE                            #
            #######################################################################
        return dists

    def compute_distances_no_loops(self, X):
        """
        计算X中每个测试点和self.X_train中每个训练点之间的距离，不使用显式循环。

        输入/输出。与compute_distances_two_loops相同
        """
        num_test = X.shape[0]
        num_train = self.X_train.shape[0]
        dists = np.zeros((num_test, num_train)) 
        ##########################################################################
        # TODO:                                                                  #
        # 计算所有测试点和所有训练点之间的l2距离，不使用任何显式循环             #
        # 并将结果存储在dists中                                                  #
        ##########################################################################
        """你的代码"""

        x2 = np.sum(X**2, axis=1).reshape((num_test, 1))
        y2 = np.sum(self.X_train**2, axis=1).reshape((1, num_train))
        xy = -2 * np.matmul(X, self.X_train.T)
        dists = np.sqrt(x2 + xy + y2)

        ##########################################################################
        #                         END OF YOUR CODE                               #
        ##########################################################################
        return dists

    def predict_labels(self, dists, k=1):
        """
        给出一个测试点和训练点之间距离的矩阵。为每个测试点预测一个标签。

        输入:
        - dists: 一个形状为(num_test, num_train)的numpy数组，
        其中dists[i, j] ... 表示第i个测试点和第j个训练点之间的距离。

        输出:
        - y: 一个形状为(num_test,)的numpy数组，包含测试数据的预测标签。
        其中y[i]是测试点X[i]的预测标签。 
        """
        num_test = dists.shape[0]
        y_pred = np.zeros(num_test)
        for i in xrange(num_test):
            # 一个长度为k的列表，存储第i个测试点的k个最近的邻居的标签。
            closest_y = []

            # 使用距离矩阵找到第1个测试点的k个最近的邻居，并使用self.y_train来找到这些邻居的标签。#
            # 将这些标签存储在closest_y中。                                               #
            k_nearest_idxs = np.argsort(dists[i, :])[:k]
            closest_y = self.y_train[k_nearest_idxs]
            
            # 找到标签列表closest_y中最常见的标签，将这个标签存入y_pred[i]。                                                  #
            y_pred[i] = np.argmax(np.bincount(closest_y))

        return y_pred
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
# 实例化
classifier = KNearestNeighbor()
# 训练KNN分类器
classifier.train(X_train_feats, y_train)

# 使用验证集调整 k 的值
k_choices = [1, 3, 5, 8, 10, 12, 15, 20, 50, 100]
k_to_accuracies = {} # 用来存储结果

##########################################################################################
# TODO:                                                                                  #
# 你需要从 k_choice 中找出最好的 k                                                       #
# 如果accuracy <= 0.1， 说明结果不对，随机猜的准确率是0.1，需要修改k_nearest_neighbor.py #
##########################################################################################

#遍历所有的k，在验证集上进行结果测试分类的准确性
for k in k_choices:
    """你的代码"""

    k_to_accuracies[k] = []

    num_folds = 5
    X_train_folds = np.array_split(X_train_feats, num_folds)
    y_train_folds = np.array_split(y_train, num_folds)  # 不均等分割

    accuracies = []
    for i in range(num_folds):
        X_train_cv = np.vstack(X_train_folds[0:i] + X_train_folds[i+1:])
        y_train_cv = np.hstack(y_train_folds[0:i] + y_train_folds[i+1:])
        X_valid_cv = X_train_folds[i]
        y_valid_cv = y_train_folds[i]
        
        classifier.train(X_train_cv, y_train_cv)
        dists = classifier.compute_distances_no_loops(X_valid_cv)
        y_valid_pred = classifier.predict_labels(dists, k)
        num_correct = np.sum(y_valid_pred == y_valid_cv)
        accuracy = float(num_correct) / y_valid_cv.shape[0]
        accuracies.append(accuracy)
        
    k_to_accuracies[k] = accuracies


for k in k_choices:
    accuracies = k_to_accuracies[k]
    print('k = %d, average accuracy = %f' % (k, np.average(accuracies)))
    plt.scatter([k] * len(accuracies), accuracies)

accuracies_mean = np.array([np.mean(v) for k,v in sorted(k_to_accuracies.items())])
accuracies_std = np.array([np.std(v) for k,v in sorted(k_to_accuracies.items())])
plt.errorbar(k_choices, accuracies_mean, yerr=accuracies_std)
plt.title('accuracy-k')
plt.xlabel('k')
plt.ylabel('accuracy')
plt.show()
    

##########################################################################################
#                                 END OF YOUR CODE                                       #
##########################################################################################

print(k_to_accuracies)
k = 1, average accuracy = 0.304400
k = 3, average accuracy = 0.297800
k = 5, average accuracy = 0.311400
k = 8, average accuracy = 0.317200
k = 10, average accuracy = 0.326200
k = 12, average accuracy = 0.321400
k = 15, average accuracy = 0.314200
k = 20, average accuracy = 0.316600
k = 50, average accuracy = 0.289600
k = 100, average accuracy = 0.265600

png

{1: [0.292, 0.29, 0.287, 0.325, 0.328], 3: [0.289, 0.296, 0.296, 0.29, 0.318], 5: [0.315, 0.297, 0.314, 0.3, 0.331], 8: [0.32, 0.308, 0.327, 0.303, 0.328], 10: [0.328, 0.309, 0.334, 0.319, 0.341], 12: [0.312, 0.315, 0.321, 0.332, 0.327], 15: [0.315, 0.304, 0.319, 0.32, 0.313], 20: [0.334, 0.312, 0.3, 0.326, 0.311], 50: [0.295, 0.282, 0.292, 0.298, 0.281], 100: [0.285, 0.276, 0.251, 0.27, 0.246]}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# 评估你的算法
##########################################################################################
# TODO:                                                                                  #
# 根据验证集的结果，选择合适的K值，并在测试集上测试结果                                  #
"""你的代码"""
best_k = 10  # 填你上面选出的 K 值 
##########################################################################################
#                                 END OF YOUR CODE                                       #
##########################################################################################

# 计算测试集上准确率
y_test_pred = classifier.predict(X_test_feats, k=best_k)
test_accuracy = np.mean(y_test == y_test_pred)
print(test_accuracy)
0.302

1