Cài đặt K-Nearest Neigbor với Python

Hi mọi người, hôm nay mình sẽ cài đặt thử thuật giải KNN với Python. Cũng như ở bài trước, chúng ta đã thử cài đặt NN với Python, mặc dù thuật toán cùi bắp nhưng vẫn có kết quả dự đoán khá ngon (38.6%). Lần này, để áp dụng KNN giải bài toán classification trên CIFAR-10 xem như thế nào. Để tìm hyperparameter K trong thuật toán này, mình sẽ xài chiến lược Cross Validation để tìm. Nhưng vì mình lười chạy thử vì đòi hỏi tài nguyên + thời gian + những suy tư trăn trở, mình mạn phép được lấy kết quả từ CS231n. Theo đó, K=7 là tối ưu dựa trên Cross Validation. Ok, vậy đã có K=7. Quá đơn giản mà không tốn nhiều công sức, chúng ta sẽ bước vào code. Sử dụng code của bài trước, ta đổi lại hàm tìm phần tử gần nhất.

def predict(self, X):   
    Ypred = np.zeros(num_test, dtype = self.ytr.dtype)    
    for i in xrange(num_test):
      print i     
      distances = np.sum(np.abs(self.Xtr - X[i,:]), axis = 1)
      k=7
      min_indexes = np.argpartition(distances, k)[:k] # vị trí k ảnh gần nhất
      yget = self.ytr[min_indexes] # yget chứa nhãn của k ảnh gần nhất
      c = Counter(yget).most_common(1) # lấy ra nhãn xuất hiện nhiều nhất trong yget
      Ypred[i] = c[0][0] # gán giá trị nhãn đó cho kết quả
    return Ypred

Lưu ý là, để chạy được hàm Counter, các bạn phải thêm thư viện vào bằng dòng code sau đây:

from collections import Counter

Sau khi để máy chạy một hồi, kết quả bạn thu được sẽ là: 37,65%. What the fuck????? Có gì đó sai sai ở đây, KNN dự đoán thua NN??? Đó là cảm giác của mình sau khi chạy xong code ở trên. Sau một hồi xem xét, thì hóa ra lỗi là ở đoạn code sau:

c = Counter(yget).most_common(1)
Ypred[i] = c[0][0]

Oái ăm là vầy, nếu như tất cả các nhãn trong yget xuất hiện phổ biến ngang nhau, thì đoạn code trên sẽ trả về nhãn có giá trị nhỏ nhất.

Như các bạn thấy, bức hình gần nhất có nhãn là "2". Nhưng đoạn code trên lại trả về nhãn "1", có thể vì nó sort hay sao đó để tìm mình cũng ko rõ, dẫn đến sai kết quả. Vì lí do này, mình có bổ sung thêm 1 số dòng code để giải.

def predict(self, X,k):
    num_test = X.shape[0]
    Ypred = np.zeros(num_test, dtype = self.ytr.dtype)
    for i in xrange(num_test):
      print i
      distances = np.sum(np.abs(self.Xtr - X[i,:]), axis = 1)      
      min_indexes = np.argpartition(distances, k)[:k] 
      yget = self.ytr[min_indexes]
      c = Counter(yget).most_common(k)
      result = c[0][0]
      if c[0][1]==1:
        k = 1
        min_indexes = np.argpartition(distances, k)[:k]
        yget = self.ytr[min_indexes]
        c = Counter(yget).most_common(k)
        result = c[0][0]
      else:
        i = 0
        while i<len(c)-1 and c[i][1]==c[i+1][1]:
          i = i+1
        if i!=0:            
          result = c[0][0]
          k2 = 1
          ind2 = np.argpartition(distances, k2)[:k2]
          yget2 = self.ytr[ind2]
          c2 = Counter(yget2).most_common(1)
          for y in range(0,i):
            if c[i][0]==c2[0][0]:
              result = c[i][0]
      Ypred[i] = result 
    return Ypred

Nhìn thì có vẻ rối, nhưng cơ bản đoạn code trên giải quyết những trường hợp sau:

Và sau khi dành thời gian để chạy thử code, kết quả ra là 38,26%. Vẫn thấp hơn NN các bạn ạ :'( Cuộc đời đúng là không biết lúc nào mới được giải thoát. Sau bao lần cài đặt và chạy thử, kết cục vẫn là một con số cùi bắp. Nhưng lý do tại sao KNN lại thấp hơn NN, mình nghĩ có 3 khả năng xảy ra ở đây: Khả năng 1: Quá trình chạy Cross Validation của CS231n đã sai. Khả năng này thì xác xuất xảy ra là 0.001%. Vì đây là bài giảng của Stanford, khó mà sai được. Khả năng 2: Code của mình sai :'( Khả năng này cũng khó xảy ra lắm. chắc tầm 20%. Khả năng 3: K=7 không tối ưu bằng K=1 trên tập test. Đây cũng là điều dễ hiểu, vì Cross Validation được thử nghiệm trên tập train chia nhỏ. Nên việc thử nghiệm trên tập test ko giống cũng có thể xảy ra. Khả năng này tầm 30-40%. Ok, mặc dù quá trình cài đặt và chạy thử không ra gì. Nhưng chúng ta ít nhất cũng đã thực hiện hóa được thuật toán KNN trên CIFAR-10. Một thành tích đáng được nhà nước và các đoàn thể tặng huân chưa. Một lần nữa, xin được vỗ tay cho thành công ngày hôm nay. Code bài này mình cũng đã up lên đây, bạn có thể lên để tải về chạy thử.