⾃⼰实现knn，进⾏图⽚分类（python）
这是斯坦福课程的作业，根据⾥⾯assignment1内的提⽰，下载好实验所需要的数据集。
⽬录
前⾔：
1、knn的预处理步骤需要对数据进⾏Normalize，对于图像⽽⾔，可以理解为⼀个像素为⼀个feature。因为像素的分布
是homogeneous，且不存在widely different distributions，因此这⼉不需要data mormalization。
2、实际运⽤knn时需要对数据的预处理第⼆步是降维处理，因为knn是通过定义不同的distance metric来vote的，⽽distance⼀旦处于⾼维就是反直觉的，并且在数学上也是能解释为什么效果不好，具体参见section6。这⼉的实验只是为了学习knn，实际中从来不会⽤knn进⾏图⽚分类，原因见3
3、knn的优点在于简单、直观。但缺点 ⼀是 在训练上花费很少的时间（具体见下，训练只是缓存了训练集），但在预测上花费很多时间（有扩展的算法可以减少预测时间，以正确率作为代价，例如Approximate Nearest Neighbor (ANN) ，具体可参考），实际的需要与此相反。⼆是 knn在⾼维的数据上效果并不好。
4、可以先从⼀个很简单的例⼦开始：。
代码主体：
part1 数据的导⼊以及预处理
import random
import numpy as np
from cs231n.data_utils import load_CIFAR10
import matplotlib.pyplot as plt
from __future__ import print_function
"""
这⼀步只是进⾏配置
"""
# Run some setup code for this notebook.
# This is a bit of magic to make matplotlib figures appear inline in the notebook
# rather than in a new window.
%matplotlib inline
# Some more magic so that the notebook will reload external python modules;
# see stackoverflow/questions/1907993/autoreload-of-modules-in-ipython
%load_ext autoreload
%autoreload 2
# Load the raw CIFAR-10 data.
cifar10_dir = 'cs231n/datasets/cifar-10-batches-py'
# Cleaning up variables to prevent loading data multiple times (which may cause memory issue)
try:
del X_train, y_train
del X_test, y_test
print('Clear previously loaded data.')
except:
pass
pass
# cs231n.data_utils 中的load_CIFAR10 实现在后⾯
X_train, y_train, X_test, y_test = load_CIFAR10(cifar10_dir)
# As a sanity check, we print out the size of the training and test data.
# print('Training data shape: ', X_train.shape) >> Training data shape:  (50000, 32, 32, 3)
# print('Training labels shape: ', y_train.shape) >> Training labels shape:  (50000,)
# print('Test data shape: ', X_test.shape) >> Test data shape:  (10000, 32, 32, 3)
# print('Test labels shape: ', y_test.shape) >> Test labels shape:  (10000,)
# Subsample the data for more efficient code execution in this exercise
num_training = 5000
mask = range(num_training)
# 下⾯两种⽅式都可以实现筛选前5000⾏，注意，若数据是⾼维的，也可以实现
# 例如若数据是（10000，32，32，3），那么下⾯的代码运⾏后，维数变为（5000，32，32，3）#X_train = X_train[mask]
X_train = X_train[np.arange(num_training)]
y_train = y_train[mask]
#print(X_train.shape) >> (5000, 32, 32, 3)
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))
# print(X_train.shape, X_test.shape) >> (5000, 3072) (500, 3072)
part2 knn训练以及预测
from cs231n.classifiers import KNearestNeighbor
# the Classifier simply remembers the data and does no further processing
# 具体实现见后⾯
classifier = KNearestNeighbor()
# Test your implementation:
dists = classifierpute_distances_two_loops(X_test)
print(dists.shape)
# 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).
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))
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))
"""
接下来是⽤不同的⽅式计算dist，并进⾏⽐较，可以不看
"""
# 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:
dists_one = classifierpute_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.
#矩阵A的Frobenius范数（ord='fro')定义为矩阵A各项元素的绝对值平⽅的总和difference = (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')
# Now implement the fully vectorized version inside compute_distances_no_loops
# and run the code
dists_two = classifierpute_distances_no_loops(X_test)
# check that the distance matrix agrees with the one we computed before:
difference = (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')
# 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(classifierpute_distances_two_loops, X_test)
print('Two loop version took %f seconds' % two_loop_time)import pickle
one_loop_time = time_function(classifierpute_distances_one_loop, X_test)
print('One loop version took %f seconds' % one_loop_time)
no_loop_time = time_function(classifierpute_distances_no_loops, X_test)
print('No loop version took %f seconds' % no_loop_time)
# you should see significantly faster performance with the fully vectorized implementation 具体实现
对于评分矩阵⽽⾔，理论上是⼆重循环，但可以利⽤python函数的特性，将⼆重循环减少为⼀重，甚⾄是直接⼀次性完成。
3.1 数据导⼊
from __future__ import print_function
ves import cPickle as pickle
import numpy as np
import os
from scipy.misc import imread
import platform
def load_pickle(f):
version = platform.python_version_tuple()
if version[0] == '2':
return  pickle.load(f)
elif version[0] == '3':
return  pickle.load(f, encoding='latin1')
raise ValueError("invalid python version: {}".format(version))
def load_CIFAR_batch(filename):
""" load single batch of cifar """
with open(filename, 'rb') as f:
datadict = load_pickle(f)
X = datadict['data']
Y = datadict['labels']
X = X.reshape(10000, 3, 32, 32).transpose(0,2,3,1).astype("float")
Y = np.array(Y)
return X, Y
def load_CIFAR10(ROOT):
""" load all of cifar """
xs = []
ys = []
for b in range(1,6):
f = os.path.join(ROOT, 'data_batch_%d' % (b, ))
X, Y = load_CIFAR_batch(f)
xs.append(X)
ys.append(Y)
Xtr = np.concatenate(xs)
Ytr = np.concatenate(ys)
del X, Y
Xte, Yte = load_CIFAR_batch(os.path.join(ROOT, 'test_batch'))
return Xtr, Ytr, Xte, Yte
def get_CIFAR10_data(num_training=49000, num_validation=1000, num_test=1000,
subtract_mean=True):
"""
Load the CIFAR-10 dataset from disk and perform preprocessing to prepare
it for classifiers. These are the same steps as we used for the SVM, but
condensed to a single function.
"""
# Load the raw CIFAR-10 data
cifar10_dir = 'cs231n/datasets/cifar-10-batches-py'
X_train, y_train, X_test, y_test = load_CIFAR10(cifar10_dir)
# Subsample the data
mask = list(range(num_training, num_training + num_validation))
X_val = X_train[mask]
y_val = y_train[mask]
mask = list(range(num_training))
X_train = X_train[mask]
y_train = y_train[mask]
mask = list(range(num_test))
mask = list(range(num_test))
X_test = X_test[mask]
y_test = y_test[mask]
# Normalize the data: subtract the mean image
if subtract_mean:
mean_image = np.mean(X_train, axis=0)
X_train -= mean_image
X_val -= mean_image
X_test -= mean_image
# Transpose so that channels come first
X_train = anspose(0, 3, 1, 2).copy()
X_val = anspose(0, 3, 1, 2).copy()
X_test = anspose(0, 3, 1, 2).copy()
# Package data into a dictionary
return {
'X_train': X_train, 'y_train': y_train,
'X_val': X_val, 'y_val': y_val,
'X_test': X_test, 'y_test': y_test,
}
3.2 计算dist（三种实现，由易到难，原理相同）⼆重循环（最简单直观的实现）

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。