실습1. KNN

Image Classification의 방법 중 K-Nearest-Neighbor에 대해 실습을 진행하였습니다.
KNN 관련 포스팅

모듈 Import 및 Data Load

import numpy as np
import random
import matplotlib.pyplot as plt
from keras.datasets import cifar10

#cifar10 데이터셋의 train data와 test data를 불러오기
(X_train, y_train), (X_test, y_test) = cifar10.load_data()
#train data와 test data의 class값을 1차원으로 변경
y_train = y_train.reshape(-1, )
y_test = y_test.reshape(-1, )

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)

실행 결과

Data Visualizing

#각 plot의 크기는 10x10으로 설정
plt.rcParams['figure.figsize'] = (10.0, 10.0) 
#디스플레이와 이미지 해상도 차이를 무시하고 정사각형으로 시각화
plt.rcParams['image.interpolation'] = 'nearest'
plt.rcParams['image.cmap'] = 'gray'
#cifar10의 class이름
classes = ['plane', 'car', 'bird', 'cat', 'deer', 'dog', 'frog', 'horse', 'ship', 'truck']
#cifar10의 class 개수
num_classes = len(classes)
#각 class 당 출력할 이미지의 개수
samples_per_class = 7

#y: class의 인덱스
#cls: class의 각 이름
for y, cls in enumerate(classes):
    #train data의 class값 중 같은 class를 가지는 data의 인덱스들을 저장
    idxs = np.flatnonzero(y_train == y)
    #idx와 7 사이의 수에서 랜덤하게 숫자를 정해서 idx에 다시 저장
    idxs = np.random.choice(idxs, samples_per_class, replace=False)
    
    #i: idxs의 인덱스
    #idx: idxs 중 인덱스의 위치
    for i, idx in enumerate(idxs):
        #plt 상에서 해당 data가 위치할 인덱스(column 인덱스)
        plt_idx = i * num_classes + y + 1
        #세로 7, 가로 10 사이즈 plot 내에 plt_idx 위치에 subplot 생성
        plt.subplot(samples_per_class, num_classes, plt_idx)
        #train data의 인덱스에 존재하는 이미지를 uint8 형식으로 출력
        plt.imshow(X_train[idx].astype('uint8'))
        #plt의 좌표축은 무시
        plt.axis('off')
        #첫 줄일때, class 이름을 출력
        if i == 0:
            plt.title(cls)
#plt 출력
plt.show()

실행결과

Data Preprocessing

#train data와 class를 1~5000개까지만 취함
num_training = 5000
mask = list(range(5000))
X_train = X_train[mask]
y_train = y_train[mask]
#test data도 마찬가지
num_test = 500
mask = list(range(500))
X_test = X_test[mask]
y_test = y_test[mask]

#train data와 test data를 열 기준으로 reshape
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)

실행결과

KNN 함수 구현

#KNN 객체 생성
class KNearestNeighbor():
    #L2 Distance를 기준으로 판독하는 KNN

    def train(self, X, y):
        #int32 형식으로 train data와 그 class를 저장
        self.X_train = np.int32(X)
        self.y_train = y

    def predict(self, X, k=1, num_loops=0):
        #num_loops: L2 Distance를 구할 때 for문의 사용 개수
        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: test data
        #self.X_train: train data
        num_test = X.shape[0]
        num_train = self.X_train.shape[0]
        dists = np.zeros((num_test, num_train))
        
        # for문 2번 사용
        #dist: (test data - train data)^2에 루트 씌운 L2 Distance 연산
        for i in range(num_test):
            for j in range(num_train):
                dists[i, j] = np.sqrt(np.sum(np.square(X[i] - self.X_train[j], dtype=np.int32)))
                
        return dists

    def compute_distances_one_loop(self, X):
        #X: test data
        #self.X_train: train data
        num_test = X.shape[0]
        num_train = self.X_train.shape[0]
        dists = np.zeros((num_test, num_train))
        
        # for문 1번 사용
        #dist: (test data - train data)^2에 루트 씌운 L2 Distance 연산
        for i in range(num_test):
            dists[i, :] = np.sqrt(np.sum(np.square(self.X_train - X[i], dtype=np.int32), axis=1))
            
        return dists

    def compute_distances_no_loops(self, X):
        #X: test data
        #self.X_train: train data
        num_test = X.shape[0]
        num_train = self.X_train.shape[0]
        dists = np.zeros((num_test, num_train))
        
        # for문을 사용하지 않음
        #dist: (test data - train data)^2에 루트 씌운 L2 Distance 연산
        dists = np.sqrt(np.sum(np.square(X, dtype=np.int32), axis=1, keepdims=True) \
                        + np.sum(np.square(self.X_train, dtype=np.int32), axis=1) \
                        - 2 * np.dot(X, self.X_train.T))
        

        return dists

    def predict_labels(self, dists, k=1):
        #dist의 행 길이만큼 num_test와 class predict array 생성
        num_test = dists.shape[0]
        y_pred = np.zeros(num_test)
        
        
        for i in range(num_test): 
            
            closest_y = [] 
            #dist[i]를 정렬하고 정렬된 인덱스를 ndarray로 반환
            np.argsort(dists[i]) < k
            #정렬된 인덱스의 train data class를 closest_y에 저장
            closest_y = self.y_train[np.argsort(dists[i]) < k]
            # closest_y에서 가장 빈도가 큰 class을 y_pred[i]에 담는다.
            y_pred[i] = np.bincount(closest_y).argmax()

        return y_pred

L2 Distance 계산 및 시각화

classifier = KNearestNeighbor()
#train data로 train을 실행
classifier.train(X_train, y_train)
#test data과 train data 간의 L2 Distance 계산
dists = classifier.compute_distances_two_loops(X_test)

#500개의 test data와 5000개의 train data 간 L2 Distance가 저장되어 있는 dist
print(dists.shape)

# dist을 시각화한다. 각각의 행은 테스트 샘플로서, 훈련 샘플과의 거리를 나타낸다.
plt.imshow(dists, interpolation='none')
#백색에 가까울수록 L2 Distacne가 멀고, Class가 다름
plt.show()

실행결과

Prediction

#k = 1로 predict 실행
y_test_pred = classifier.predict_labels(dists, k=1)

#class를 맞춘 test data의 개수 
num_correct = np.sum(y_test_pred == y_test)
#정확도
accuracy = num_correct / num_test
print('Got %d / %d correct => accuracy: %f' % (num_correct, num_test, accuracy))

실행결과

#k = 10로 predict 실행
y_test_pred = classifier.predict_labels(dists, k=10)

#class를 맞춘 test data의 개수 
num_correct = np.sum(y_test_pred == y_test)
#정확도
accuracy = num_correct / num_test
print('Got %d / %d correct => accuracy: %f' % (num_correct, num_test, accuracy))

실행결과

Cross-Validation

#train data를 나눌 개수
num_folds = 5
#선택할 수 있는 k
k_choices = [1, 3, 5, 8, 10, 12, 15, 20, 50, 100]
#folder 개수 따라 data split
X_train_folds = np.array_split(X_train, num_folds)
y_train_folds = np.array_split(y_train, num_folds)

# k 값이 key이고, floder 별 accuracy가 들어있는 리스트가 value인 딕셔너리.
k_to_accuracies = {}

for k in k_choices:
    accuracies = []
    for i in range(num_folds):
        #해당 folder에 대해 train, label 설정
        train_set = np.concatenate(X_train_folds[:i] + X_train_folds[i+1:])
        lebel_set = np.concatenate(y_train_folds[:i] + y_train_folds[i+1:])
        #classifier training
        classifier.train(train_set, lebel_set)
        #k를 바꿔가며 predict
        pred = classifier.predict(X_train_folds[i], k=k)
        #정답률 확인
        acc = np.sum(pred == y_train_folds[i]) / pred.size
        accuracies.append(acc)
        
    #정확도 저장하는 딕셔너리에 key(k)와 value(accuracy)를 저장
    k_to_accuracies[k] = accuracies

#출력
for k in sorted(k_to_accuracies):
    print('k = %d, accuracy = %f' % (k, np.mean(k_to_accuracies[k])))

실행결과

Accuracy 시각화

#각 k별 정확도를 산점도로 표현
for k in k_choices:
    accuracies = k_to_accuracies[k]
    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('Cross-validation on k')
plt.xlabel('k')
plt.ylabel('Cross-validation accuracy')
plt.xticks(k_choices)
plt.show()

실행결과

최적 Parameter로 재예측

#평균 정확도가 가장 높은 50을 k값으로 설정
best_k = 50

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

#최고 정확도를 출력
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))

실행결과

최적의 K값으로 Predict하였으나, 정확도가 10% 밖에 나오지 않았다.

Train Data와 Test Data 사이의 L2 Distance를 기준으로 K개의 인접 Data들을 참조하여 Class를 판정하는 KNN은 Image Classification에 적합하지 않다고 볼 수 있다.