CS231n课程讲义翻译：图像分类

Xtr, Ytr, Xte, Yte = load_CIFAR10('data/cifar10/') # a magic function we provide
# flatten out all images to be one-dimensional
Xtr_rows = Xtr.reshape(Xtr.shape[0], 32 * 32 * 3) # Xtr_rows becomes 50000 x 3072
Xte_rows = Xte.reshape(Xte.shape[0], 32 * 32 * 3) # Xte_rows becomes 10000 x 3072

nn = NearestNeighbor() # create a Nearest Neighbor classifier class
nn.train(Xtr_rows, Ytr) # train the classifier on the training images and labels
Yte_predict = nn.predict(Xte_rows) # predict labels on the test images
# and now print the classification accuracy, which is the average number
# of examples that are correctly predicted (i.e. label matches)
print 'accuracy: %f' % ( np.mean(Yte_predict == Yte) )  # python2.x

import numpy as np

class NearestNeighbor(object):
	def __init__(self):
		pass

	def train(self, X, y):
    	""" 
    	这个地方的训练其实就是把所有的已有图片读取进来 -_-||
    	"""
    	""" X is N x D where each row is an example. Y is 1-dimension of size N """
    	# the nearest neighbor classifier simply remembers all the training data
    	self.Xtr = X
    	self.ytr = y

	def predict(self, X):
 		""" 
    	所谓的预测过程其实就是扫描所有训练集中的图片，计算距离，取最小的距离对应图片的类目
    	"""
    	""" X is N x D where each row is an example we wish to predict label for """
    	num_test = X.shape[0]
        # 这里要保证维度一致！
    	# lets make sure that the output type matches the input type
    	Ypred = np.zeros(num_test, dtype = self.ytr.dtype) # 一维元素都是0的array

        # 把训练集扫一遍 -_-||
		# loop over all test rows
    	for i in xrange(num_test):  
            # 注意这里的xrange仅适用于python2.x，range适用于python3.x
      		# find the nearest training image to the i'th test image
      		# using the L1 distance (sum of absolute value differences)
      		# 对训练集中每一张图片都与指定的一张测试图片，在对应元素位置上做差，
            # 然后分别以每张图片为单位求和。
      		distances = np.sum(np.abs(self.Xtr - X[i,:]), axis = 1)	# 一个5000元素的list
      		# 取最小distance图片的下标：
      		min_index = np.argmin(distances) # get the index with smallest distance
      		Ypred[i] = self.ytr[min_index] # predict the label of the nearest example

    	return Ypred

distances = np.sqrt(np.sum(np.square(self.Xtr - X[i,:]), axis = 1))

# 假定已经有Xtr_rows, Ytr, Xte_rows, Yte了，其中Xtr_rows为50000*3072 矩阵
# assume we have Xtr_rows, Ytr, Xte_rows, Yte as before
# recall Xtr_rows is 50,000 x 3072 matrix
Xval_rows = Xtr_rows[:1000, :] # take first 1000 for validation 构建前1000个图为交叉验证集
Yval = Ytr[:1000]
Xtr_rows = Xtr_rows[1000:, :] # keep last 49,000 for train 保留其余49000个图为训练集
Ytr = Ytr[1000:]

# 设置一些k值，用于试验
# find hyperparameters that work best on the validation set
validation_accuracies = []
for k in [1, 3, 5, 10, 20, 50, 100]:

    # 初始化对象
    # use a particular value of k and evaluation on validation data
    nn = NearestNeighbor()
	nn.train(Xtr_rows, Ytr)
    # 修改一下predict函数，接受 k 作为参数
  	# here we assume a modified NearestNeighbor class that can take a k as input
  	Yval_predict = nn.predict(Xval_rows, k = k)
  	acc = np.mean(Yval_predict == Yval)
  	print 'accuracy: %f' % (acc,)

    # 输出结果
  	# keep track of what works on the validation set
  	validation_accuracies.append((k, acc)) # 元组形式append在列表里

import random
import numpy as np
from cs231n.data_utils import load_CIFAR10
import matplotlib.pyplot as plt

from __future__ import print_function

# This is a bit of magic to make matplotlib figures appear inline in the notebook
# rather than in a new window.
#这里有一个小技巧可以让matplotlib画的图出现在notebook页面上，而不是新建一个画图窗口
%matplotlib inline
# set default size of plots 设置默认的绘图窗口大小
plt.rcParams['figure.figsize'] = (10.0, 8.0) 
plt.rcParams['image.interpolation'] = 'nearest' # 差值方式
plt.rcParams['image.cmap'] = 'gray' # 灰度空间

# Some more magic so that the notebook will reload external python modules;
# see http://stackoverflow.com/questions/1907993/autoreload-of-modules-in-ipython
#另一个小技巧，下面的语句会让notebook自动加载最新版本的外部python模块
#详情见 http://stackoverflow.com/questions/1907993/autoreload-of-modules-in-ipython
%load_ext autoreload
%autoreload 2

import autoreload
?autoreload

# Load the raw CIFAR-10 data.
# 这里加载数据源的方法在data_utils.py中，会将data_batch_!到5的数据作为训练集，test_batch作为测试集
cifar10_dir = 'cs231n/datasets/cifar-10-batches-py'
X_train, y_train, X_test, y_test = load_CIFAR10(cifar10_dir)

# As a sanity check, we print out the size o f the training and test data.
# 检查一下数据，打印训练集及其标签和测试集及其标签的大小 
print('Training data shape: ', X_train.shape)
print('Training labels shape: ', y_train.shape)
print('Test data shape: ', X_test.shape)
print('Test labels shape: ', y_test.shape)
# 返回值是：
# Training data shape:  (50000, 32, 32, 3)
# Training labels shape:  (50000,)
# Test data shape:  (10000, 32, 32, 3)
# Test labels shape:  (10000,)

# Visualize some examples from the dataset.
# We show a few examples of training images from each class.
# 这里我们将训练集中每一个类别的样本随机挑出几个进行展示
classes = ['plane', 'car', 'bird', 'cat', 'deer', 'dog', 'frog', 'horse', 'ship', 'truck']
num_classes = len(classes)  # 类别数目
samples_per_class = 7    # 每个类别采样个数
# 对列表的元素位置和元素进行循环：
for y, cls in enumerate(classes):  # 这里对应生成的是 (y, cls) = (0, plane), (1, car), (2, bird), ..., (9, truck)
    # 在循环每一个类别时，挑出测试集y中该类别图片的索引位置（index）：
    idxs = np.flatnonzero(y_train == y)   
    # np.flatnonzero函数：返回扁平化后矩阵中非零元素(或真值)的位置索引（index）
    # 随机从idxs中选取num_classes个数的内容，并将选取结果生成新的array中返回
    idxs = np.random.choice(idxs, samples_per_class, replace=False)
    for i, idx in enumerate(idxs):  # 同上，i表示循环idx的序列号，idx是idxs的元素之一
        plt_idx = i * num_classes + y + 1  # 在子图中所占位置的计算，竖着一列一列画的。
        plt.subplot(samples_per_class, num_classes, plt_idx)  # 说明要画的子图的编号
        plt.imshow(X_train[idx].astype('uint8'))  # show出image
        plt.axis('off')
        if i == 0:
            plt.title(cls)   # 每当画第一行图像时，写上标题，也就是类别名
plt.show()

# REF：http://www.cnblogs.com/lijiajun/p/5479523.html

# Subsample the data for more efficient code execution in this exercise
# 为了更高效地运行我们的代码，这里取出一个子集进行后面的练习（取训练集前50000个，测试集前500个）
num_training = 5000
mask = list(range(num_training))
X_train = X_train[mask]
y_train = y_train[mask]

num_test = 500
mask = list(range(num_test))
X_test = X_test[mask]
y_test = y_test[mask]

# Reshape the image data into rows
# 将图像数据转置成二维的
X_train = np.reshape(X_train, (X_train.shape[0], -1))  
X_test = np.reshape(X_test, (X_test.shape[0], -1))
# 这里的-1表示，X_train.shape[0]作为新array的行数后，剩余可自动推断出的列数。
print(X_train.shape, X_test.shape)
# 打印结果：
# (5000, 3072) (500, 3072)

from cs231n.classifiers import KNearestNeighbor

# Create a kNN classifier instance. 
# Remember that training a kNN classifier is a noop: 
# the Classifier simply remembers the data and does no further processing 
classifier = KNearestNeighbor()
classifier.train(X_train, y_train)

# Open cs231n/classifiers/k_nearest_neighbor.py and implement
# compute_distances_two_loops.
# 打开cs231n/classifiers/k_nearest_neighbor.py，补全compute_distances_two_loops方法

# Test your implementation:
# 测试一下
dists = classifier.compute_distances_two_loops(X_test)
print(dists.shape)
# 打印结果：
# (500, 5000)	其dists[i,j]表示的是第i个测试图片与第j个训练图片之间的L2距离

# We can visualize the distance matrix: each row is a single test example and
# its distances to training examples
# 我们可以将距离矩阵进行可视化：其中每一行表示一个测试样本与所有训练样本的距离
plt.imshow(dists, interpolation='none')
plt.show()

# Now implement the function predict_labels and run the code below:
# We use k = 1 (which is Nearest Neighbor).
# 实现predict_labels方法，然后运行下列代码
# 这里我们将k设置为1

y_test_pred = classifier.predict_labels(dists, k=1)

# Compute and print the fraction of correctly predicted examples
# 计算并打印准确率
num_correct = np.sum(y_test_pred == y_test)
accuracy = float(num_correct) / num_test
print('Got %d / %d correct => accuracy: %f' % (num_correct, num_test, accuracy))
# 打印结果：
# Got 137 / 500 correct => accuracy: 0.274000

y_test_pred = classifier.predict_labels(dists, k=5)
num_correct = np.sum(y_test_pred == y_test)
accuracy = float(num_correct) / num_test
print('Got %d / %d correct => accuracy: %f' % (num_correct, num_test, accuracy))
# 打印结果：
# Got 139 / 500 correct => accuracy: 0.278000

# Now lets speed up distance matrix computation by using partial vectorization
# with one loop. Implement the function compute_distances_one_loop and run the
# code below:
# 现在我们将距离计算的效率提升一下，使用单层循环结构的计算方法。实现
# compute_distances_one_loop方法，并运行下列代码

dists_one = classifier.compute_distances_one_loop(X_test)

# To ensure that our vectorized implementation is correct, we make sure that it
# agrees with the naive implementation. There are many ways to decide whether
# two matrices are similar; one of the simplest is the Frobenius norm. In case
# you haven't seen it before, the Frobenius norm of two matrices is the square
# root of the squared sum of differences of all elements; in other words, reshape
# the matrices into vectors and compute the Euclidean distance between them.
# 为了保证矢量化的代码运行正确，我们将运行结果与前面的方法的结果进行对比。对比两个
# 矩阵是否相等的方法有很多，比较简单的一种是使用Frobenius范数。Frobenius范数表示的
# 是两个矩阵所有元素的插值的平方和的根。或者说是将两个矩阵reshape成矢量后，它们之
# 间的欧氏距离
difference = np.linalg.norm(dists - dists_one, ord='fro')
print('Difference was: %f' % (difference, ))
if difference < 0.001:
    print('Good! The distance matrices are the same')
else:
    print('Uh-oh! The distance matrices are different')
    
# 打印结果：
# Difference was: 0.000000
# Good! The distance matrices are the same

# Now implement the fully vectorized version inside compute_distances_no_loops
# and run the code
# 完成完全矢量化方式运行的compute_distances_no_loops方法，并运行下列代码
dists_two = classifier.compute_distances_no_loops(X_test)

# check that the distance matrix agrees with the one we computed before:
# 将结果与之前的计算结果进行对比
difference = np.linalg.norm(dists - dists_two, ord='fro')
print('Difference was: %f' % (difference, ))
if difference < 0.001:
    print('Good! The distance matrices are the same')
else:
    print('Uh-oh! The distance matrices are different')
        
# 打印结果：
# Difference was: 0.000000
# Good! The distance matrices are the same

# Let's compare how fast the implementations are
# 下面我们对比一下各方法的执行速度
def time_function(f, *args):
    """
    Call a function f with args and return the time (in seconds) that it took to execute.
    """
    import time
    tic = time.time()
    f(*args)
    toc = time.time()
    return toc - tic

two_loop_time = time_function(classifier.compute_distances_two_loops, X_test)
print('Two loop version took %f seconds' % two_loop_time)

one_loop_time = time_function(classifier.compute_distances_one_loop, X_test)
print('One loop version took %f seconds' % one_loop_time)

no_loop_time = time_function(classifier.compute_distances_no_loops, X_test)
print('No loop version took %f seconds' % no_loop_time)

# 打印结果：
# Two loop version took 57.122203 seconds
# One loop version took 71.512672 seconds
# No loop version took 0.510630 seconds

# you should see significantly faster performance with the fully vectorized implementation
# 你应该可以看到，完全矢量化的代码运行效率有明显的提高

num_folds = 5
k_choices = [1, 3, 5, 8, 10, 12, 15, 20, 50, 100]

X_train_folds = []
y_train_folds = []
################################################################################
# TODO:                                                                        #
# Split up the training data into folds. After splitting, X_train_folds and    #
# y_train_folds should each be lists of length num_folds, where                #
# y_train_folds[i] is the label vector for the points in X_train_folds[i].     #
# Hint: Look up the numpy array_split function.                                #
# 任务:                                                                        #
# 将训练数据切分成不同的折。切分之后,训练样本和对应的样本标签被包含在数组                 #
# X_train_folds和y_train_folds之中，数组长度是折数num_folds。其中                  #
# y_train_folds[i]是一个矢量，表示矢量X_train_folds[i]中所有样本的标签              #
# 提示: 可以尝试使用numpy的array_split方法。                                      #
################################################################################
X_train_folds = np.array_split(X_train, num_folds)	
y_train_folds = np.array_split(y_train, num_folds)
# 以num_folds的折数从前向后分割，最后不够num_folds数目的为最后一折
################################################################################
#                                 END OF YOUR CODE                             #
#                                 结束                                          #
################################################################################

# A dictionary holding the accuracies for different values of k that we find
# when running cross-validation. After running cross-validation,
# k_to_accuracies[k] should be a list of length num_folds giving the different
# accuracy values that we found when using that value of k.
# 我们将不同k值下的准确率保存在一个字典中。交叉验证之后，k_to_accuracies[k]保存了
# k值下，一个长度为折数的准确率矢量

k_to_accuracies = {}
for k in k_choices:
    k_to_accuracies.setdefault(k, [])
################################################################################
# TODO:                                                                        #
# Perform k-fold cross validation to find the best value of k. For each        #
# possible value of k, run the k-nearest-neighbor algorithm num_folds times,   #
# where in each case you use all but one of the folds as training data and the #
# last fold as a validation set. Store the accuracies for all fold and all     #
# values of k in the k_to_accuracies dictionary.                               #
# 任务:                                                                         #
# 通过k折的交叉验证找到最佳k值。对于每一个k值，执行kNN算法num_folds次，每一次            #
# 执行中，选择一折为训练集，最后一折为验证集。将不同k值在不同折上的运算结果保              #
# 存在k_to_accuracies字典中。                                                    #
################################################################################
for i in range(num_folds):
    classifier = KNearestNeighbor()
    X_train_ = np.vstack(X_train_folds[:i] + X_train_folds[i+1:])
    y_train_ = np.hstack(y_train_folds[:i] + y_train_folds[i+1:])
    classifier.train(X_train_, y_train_)
    for k in k_choices:
        y_pred_ = classifier.predict(X_train_folds[i], k=k)
        accuracy = np.mean(y_pred_ == y_train_folds[i])
        k_to_accuracies[k].append(accuracy)
################################################################################
#                                 END OF YOUR CODE                             #
################################################################################

# Print out the computed accuracies
for k in sorted(k_to_accuracies):
    for accuracy in k_to_accuracies[k]:
        print('k = %d, accuracy = %f' % (k, accuracy))

# plot the raw observations
# 画个图会更直观一点
for k in k_choices:
    accuracies = k_to_accuracies[k]
    plt.scatter([k] * len(accuracies), accuracies)

# plot the trend line with error bars that correspond to standard deviation
# 画出在不同k值下，误差均值和标准差
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('Cross-validation on k')
plt.xlabel('k')
plt.ylabel('Cross-validation accuracy')
plt.show()

# Based on the cross-validation results above, choose the best value for k,   
# retrain the classifier using all the training data, and test it on the test
# data. You should be able to get above 28% accuracy on the test data.
# 根据上面交叉验证的结果，选择最优的k，然后在全量数据上进行试验，你将得到约28%的准确率
best_k = 6

classifier = KNearestNeighbor()
classifier.train(X_train, y_train)
y_test_pred = classifier.predict(X_test, k=best_k)

# Compute and display the accuracy
# 计算并展示准确率
num_correct = np.sum(y_test_pred == y_test)
accuracy = float(num_correct) / num_test
print('Got %d / %d correct => accuracy: %f' % (num_correct, num_test, accuracy))

# 打印结果：
# Got 141 / 500 correct => accuracy: 0.282000

#-*- coding:utf-8 -*-
import numpy as np
#from past.builtins import xrange

class KNearestNeighbor(object):
    """ a kNN classifier with L2 distance """
	""" 使用L2距离的kNN分类器 """

	def __init__(self):
		pass
	
    def train(self, X, y):
    """
    Train the classifier. For k-nearest neighbors this is just 
    memorizing the training data.

    Inputs:
    - X: A numpy array of shape (num_train, D) containing the training data
      consisting of num_train samples each of dimension D.
    - y: A numpy array of shape (N,) containing the training labels, where
         y[i] is the label for X[i].
    
    训练分类器。对于KNN分类器来说，训练就是将训练数据保存

    输入：
    -X: 训练数据集，一个(训练样本数量，维度)大小的numpy数组
    -y: 训练样本标签，一个(训练样本数量，1)大小的numpy数组，其中y[i]表示样本X[i]的类别标签
    """
    	self.X_train = X
    	self.y_train = y
    
	def predict(self, X, k=1, num_loops=0):
    """
    Predict labels for test data using this classifier.

    Inputs:
    - X: A numpy array of shape (num_test, D) containing test data consisting
         of num_test samples each of dimension D.
    - k: The number of nearest neighbors that vote for the predicted labels.
    - num_loops: Determines which implementation to use to compute distances
      between training points and testing points.

    Returns:
    - y: A numpy array of shape (num_test,) containing predicted labels for the
      test data, where y[i] is the predicted label for the test point X[i].

    该方法对输入数据进行类别预测

    输入：
    - X: 测试数据集，一个(测试样本数量，维度)大小的numpy数组
    - k: 最近邻数量
    - num_loops: 计算测试样本和训练样本距离的方法

    返回：
    - y: 类别预测结果，一个(测试样本数量，1)大小的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):
    """
    Compute the distance between each test point in X and each training point
    in self.X_train using a nested loop over both the training data and the 
    test data.

    Inputs:
    - X: A numpy array of shape (num_test, D) containing test data.

    Returns:
    - dists: A numpy array of shape (num_test, num_train) where dists[i, j]
      is the Euclidean distance between the ith test point and the jth training
      point.

    通过一个两层的嵌套循环，遍历测试样本点，并求其到全部训练样本点的距离

    输入:
    - X: 测试数据集，一个(测试样本数量, 维度)大小的numpy数组

    返回:
    - dists: 一个(测试样本数量, 训练样本数量) 大小的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 range(num_test):
      		for j in range(num_train):
        		#####################################################################
		        # TODO:                                                             #
		        # Compute the l2 distance between the ith test point and the jth    #
		        # training point, and store the result in dists[i, j]. You should   #
		        # not use a loop over dimension.                                    #
		        # 任务:                                                             #
		        # 计算第i个测试点到第j个训练样本点的L2距离，并保存到dists[i, j]中，         #
		        # 注意不要在维度上使用for循环                                           #
		        #####################################################################
	        	dists[i, j] = np.sqrt(np.sum(np.square(self.X_train[j,:] - X[i,:])))
                # 这里的np.square()是对其中每个元素平方操作
		        #####################################################################
		        #                       END OF YOUR CODE                            #
		        #                       任务结束                                     #
		        #####################################################################
    	return dists

	def compute_distances_one_loop(self, X):
    """
    Compute the distance between each test point in X and each training point
    in self.X_train using a single loop over the test data.

    Input / Output: Same as compute_distances_two_loops

    通过一个单层的嵌套循环，遍历测试样本点，并求其到全部训练样本点的距离
    输入/输出：和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 range(num_test):
      		#######################################################################
      		# TODO:                                                               #
      		# Compute the l2 distance between the ith test point and all training #
      		# points, and store the result in dists[i, :].                        #
      		# 任务:                                                               #
      		# 计算第i个测试样本点到所有训练样本点的L2距离，并保存到dists[i, :]中          #
      		#######################################################################
			dists[i,:] = np.sqrt(np.sum(np.square(self.X_train - X[i,:]),axis = 1))
      		#######################################################################
      		#                         END OF YOUR CODE                            #
      		#                         任务结束                                     #
      		#######################################################################
	return dists

	def compute_distances_no_loops(self, X):
    """
    Compute the distance between each test point in X and each training point
    in self.X_train using no explicit loops.

    Input / Output: Same as compute_distances_two_loops

    不通过循环方式，遍历测试样本点，并求其到全部训练样本点的距离
    输入/输出：和compute_distances_two_loops方法相同
    """
    	num_test = X.shape[0]
    	num_train = self.X_train.shape[0]
    	dists = np.zeros((num_test, num_train)) 
    	#########################################################################
    	# TODO:                                                                 #
    	# Compute the l2 distance between all test points and all training      #
    	# points without using any explicit loops, and store the result in      #
    	# dists.                                                                #
    	#                                                                       #
    	# You should implement this function using only basic array operations; #
    	# in particular you should not use functions from scipy.                #
    	#                                                                       #
    	# HINT: Try to formulate the l2 distance using matrix multiplication    #
    	#       and two broadcast sums.                                         #
    	# 任务:                                                                 #
    	# 计算测试样本点和训练样本点之间的L2距离，并且不使用for循环，最后将结果           #
    	# 保存到dists中                                                          #
    	#                                                                       #
    	# 请使用基本的数组操作完成该方法；另外，不要使用scipy中的方法                    #
    	#                                                                       #
    	# 提示: 可以使用矩阵乘法和两次广播加法                                        #
    	#########################################################################
		# 这里对完全平方公式做了展开，以方便我们实现矢量化，(a-b)^2=a^2+b^2-2ab
        dists = np.sqrt(-2*np.dot(X, self.X_train.T) # 一个500*5000的矩阵
                        + np.sum(np.square(self.X_train), axis=1) # 一个1*5000的矩阵
                        + np.transpose([np.sum(np.square(X), axis=1)]))	# 一个500*1的矩阵
        # 留意self.X_train的shape是(5000,3072),X的shape是(500,3072)
        # np.dot()是矩阵乘法, np.sqrt()和np.square()都是对矩阵每个元素的操作
        # np.sum(array_like, axis=1)是对矩阵每行分别求和，即每个图片像素求和
        # 注意：后两个矩阵的加法可以张成一个500*5000的矩阵！
    	#########################################################################
    	#                         END OF YOUR CODE                              #
    	#                         任务结束                                       #
    	#########################################################################
	return dists

	def predict_labels(self, dists, k=1):
    """
    Given a matrix of distances between test points and training points,
    predict a label for each test point.

    Inputs:
    - dists: A numpy array of shape (num_test, num_train) where dists[i, j]
      gives the distance betwen the ith test point and the jth training point.

    Returns:
    - y: A numpy array of shape (num_test,) containing predicted labels for the
      test data, where y[i] is the predicted label for the test point X[i].

    通过距离矩阵，预测每一个测试样本的类别
    
    输入：
    - dists: 一个(测试样本数量，训练样本数量)大小的numpy数组，其中dists[i, j]表示
      第i个测试样本到第j个训练样本的距离

    返回：
    - y: 一个(测试样本数量，)大小的numpy数组，其中y[i]表示测试样本X[i]的预测结果
    """
		num_test = dists.shape[0]
    	y_pred = np.zeros(num_test)
    	for i in range(num_test):
      		# A list of length k storing the labels of the k nearest neighbors to
      		# the ith test point.
      		# 一个长度为k的list数组，其中保存着第i个测试样本的k个最近邻的类别标签
      		closest_y = []
      		#########################################################################
      		# TODO:                                                                 #
      		# Use the distance matrix to find the k nearest neighbors of the ith    #
      		# testing point, and use self.y_train to find the labels of these       #
      		# neighbors. Store these labels in closest_y.                           #
      		# Hint: Look up the function numpy.argsort.                             #
      		# 任务:                                                                 #
      		# 通过距离矩阵找到第i个测试样本的k个最近邻,然后在self.y_train中找到这些         #
      		# 最近邻对应的类别标签，并将这些类别标签保存到closest_y中。                    #
      		# 提示: 可以尝试使用numpy.argsort方法                                      #
      		#########################################################################
      		# 在dists距离矩阵中，第i个测试图片(第i行)下的列(训练图片)，按值从小到大排列，
            # 取出前k个的索引(原列数，亦训练集的索引)，最后根据该索引在测试集中切片出相应的标签值
            closest_y = self.y_train[np.argsort(dists[i])[:k]]
            # np.argsort()函数返回的是数组值从小到大的索引值
      		#########################################################################
      		# TODO:                                                                 #
      		# Now that you have found the labels of the k nearest neighbors, you    #
      		# need to find the most common label in the list closest_y of labels.   #
      		# Store this label in y_pred[i]. Break ties by choosing the smaller     #
      		# label.                                                                #
      		# 任务:                                                                 #
      		# 现在你已经找到了k个最近邻对应的标签, 下面就需要找到其中最普遍的那个             #
      		# 类别标签，然后保存到y_pred[i]中。如果有票数相同的类别，则选择编号小            #
      		# 的类别                                                                #
      		#########################################################################
      		y_pred[i] = np.argmax(np.bincount(closest_y))
            # np.bincount()是凡是与索引值相同的值，计数+1，计数结果返回为新的索引值里的计数值
            # np.argmax() 返回的是数值最大的索引值，在这个例子中即是标签
      		#########################################################################
      		#                           END OF YOUR CODE                            # 
      		#########################################################################

	return y_pred