Cài đặt thuật giải Nearest Neighbor với Python

Bài này sẽ giúp các bạn chạy thử thuật giải Nearest Neighbor bằng ngôn ngữ Python. Dataset được sử dụng trong bài này là CIFAR-10, một bộ dữ liệu khá nổi tiếng cho bài toán nhận dạng hình ảnh. Nói sơ qua về dataset này, CIFAR-10 chứa 60000 bức ảnh màu có kích thước 32*32, tổng số nhãn dán là 10 nhãn. Bộ dataset được chia làm 2 phần: training set (50000 ảnh) và testing set (10000 ảnh). Những bạn nào chưa nắm được các khái niệm như training set hay testing set thì xin mời quay về đây để đọc. Để tải bộ dataset này cho ví dụ ngày hôm nay, bạn vào đây.

Trước hết, bạn phải năm được Nearest Neighbor Classifier là gì đã nhá. Và code của bài này mình cũng đã upload lên đây. Bạn có thể tải về để chạy thử. Ok, bây chừ chúng ta sẽ bắt tay vào code. Đầu tiên chúng ta sẽ import các thư viện cần thiết vào:

import numpy as np
from cs231n.data_utils import load_CIFAR10

Lưu ý cho là, hàm load_CIFAR10 là hàm dùng để load dataset CIFAR10 vào python. Hàm này được cung cấp bởi cs231n, giúp các bạn dễ dàng hơn trong quá trình lập trình. Bước tiếp đến là chúng ta sẽ load dataset vào:

Xtr, Ytr, Xte, Yte = load_CIFAR10(link to dataset folder)

Như chúng ta đã biết, máy tính hiểu một bức hình màu thực chất là 3 ma trận RGB. Với trường hợp dataset này, mỗi bức hình màu sẽ là 1 ma trận: 32*32*3. Để dễ dàng cho việc tính khoảng cách, ta sẽ chuyển ma trận trên về thành ma trận 1 chiều với 3072 phần tử.

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

Bây giờ ta sẽ bắt đầu code hàm NearestNeighbor:

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

  def train(self, X, y):
    """ X, Y là input và output của tập train. Trong đó, X có kích thước 50000*3072, Y là mảng 1 chiều có kích thước 50000 """
    self.Xtr = X
    self.ytr = y

  def predict(self, X):
    """ X là input của tập test. Trong đó, X có kích thước 10000*3072 """
    num_test = X.shape[0]
    # khoi tạo tập kết quả dự đoán
    Ypred = np.zeros(num_test, dtype = self.ytr.dtype)

    # lặp qua tất cả những bức ảnh trong tập test
    for i in xrange(num_test):
      print i # hiển thị vòng lặp đang thực hiện
      # tính khoảng cách của bức ảnh hiện tại so với tất cả những bức ảnh trong tập train
      distances = np.sum(np.abs(self.Xtr - X[i,:]), axis = 1)
      # tìm vị trí của bức ảnh trong tập train gần với bức ảnh test nhất
      min_index = np.argmin(distances) 
      # lấy giá trị output tương ứng gán vào tập kết quả dự đoán
      Ypred[i] = self.ytr[min_index] 
    return Ypred

num_test là kích thước của tập test, trong trường hợp này là 10000. Nhìn vào dòng code ta có thể thấy, quá trình tính toán khoảng cách đã được numpy hỗ trợ rất tốt, ta có thể dễ dàng code chỉ trong 1 dòng. Và cũng nhắc thêm, khoảng cách trong đoạn code trên là khoảng cách Mahattan nhá. Việc tiếp theo ta cần làm là gọi tất cả các hàm ta đã code ra cho nó chạy thôi.

nn = NearestNeighbor()
nn.train(Xtr_rows, Ytr)
Yte_predict = nn.predict(Xte_rows)

Cuối cùng là tính toán tỉ lệ chính xác của thuật toán Nearest Neighbor classifier trên tập dataset này.

print 'accuracy: %f' % ( np.mean(Yte_predict == Yte) )

Nếu như chạy đúng, kết quả chính xác đưa ra sẽ là : 38,6%. OK, thấy được con số này, ai nói Nearest Neighbor là thuật toán vớ vẩn thì bước ra đây. Rõ ràng kết quả này quá cao nếu so với việc bạn cho máy tính random. Tỉ lệ đoán trúng dựa vào random chỉ là 10% (vì ta có đến 10 nhãn trong tập dataset này). Nếu bạn muốn cài đặt NN với độ đo Euclidean thì hãy thay dòng code này vào để tính khoảng cách:

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

Kết quả dự đoán với độ đo Euclidean là 35.4%, thấp hơn độ đo Mahattan. Vậy đấy, thế là bạn đã cài đặt thành công thuật toán Nearest Neighbor Classifier trên ngôn ngữ Python. Xin cung hỉ cung hỉ vì bạn vừa làm được cái điều mà ai học lập trình cũng làm đc -_-. Qua quá trình chạy trên, chắc hẳn bạn cũng thấy quá trình lặp để đưa kết quả dự đoán rất chậm. Cũng đúng thôi, vì mỗi lần đưa ra được kết quả, máy tính phải tính khoảng cách giữa 1 bức ảnh tới 50000 bức ảnh, đây cũng chính là nhược điểm rất lớn của thuật toán này.