Chapter 1 - Ep.2: K-NEAREST NEIGHBOUR (kNN)

K-NEAREST NEIGHBOUR (k-NN)

    

1/ INTRO

    Chào mọi người, hôm nay chúng ta sẽ cùng nhau tìm hiểu về một trong những thuật toán Machine Learning đơn giản nhất dựa trên kỹ thuật Supervised Learning (học có giám sát), đó là k-Nearest Neighbour (k-NN).

    Ví dụ nha, đến kì thi TOEIC ở trường, bạn vừa thi được 400 điểm và đang không biết đậu hay rớt. Ra về bạn lên dữ liệu của trung tâm tiếng Anh tra cứu kết quả của các anh chị khóa trước, thấy như sau:

              ...

                Nguyễn Văn A: 380 - đậu

                Nguyễn Văn B: 410 - đậu

                Nguyễn Văn C: 340 - rớt

                Nguyễn Văn D: 405 - đậu

                Nguyễn Văn E: 395 - đậu

                Nguyễn Văn F: 320 - rớt

                  ...

    Do đó bạn có thể mạnh dạn dự đoán mức điểm tròn 400 của bạn sẽ đậu - dựa trên số liệu bạn vừa tra cứu, k-NN cũng hoạt động như thế đấy, nó sẽ lưu trữ tất cả dữ liệu có sẵn và phân loại một điểm dữ liệu mới dựa trên sự tương đồng.

    Thuật toán k-NN có thể được sử dụng cho Hồi quy cũng như Phân loại nhưng chủ yếu nó được sử dụng cho các bài toán Phân loại.

    K-NN là một thuật toán phi tham số, có nghĩa là nó không đưa ra bất kỳ giả định nào về dữ liệu cơ bản.

    Nó còn được gọi là thuật toán lười học vì nó không học từ tập huấn luyện ngay lập tức, thay vào đó ở giai đoạn huấn luyện nó chỉ lưu trữ tập dữ liệu và khi nó nhận được dữ liệu mới, sau đó nó sẽ phân loại dữ liệu đó thành một loại gần giống với dữ liệu mới.

2/ HOẠT ĐỘNG

Bước 1: Chọn số K (số lượng điểm "hàng xóm" muốn xét)

Bước 2: Tính khoảng cách Euclide từ điểm dữ liệu mới đến các điểm trong bộ data 

              Khoảng cách Euclide: square[(x2 - x1)**2 + (y2 - y1)**2)]

Bước 3: Lấy K điểm "hàng xóm" gần nhất theo khoảng cách Euclide được tính toán

Bước 4: Trong số K điểm lân cận này, hãy đếm số điểm dữ liệu trong mỗi loại

Bước 5: Gán các điểm dữ liệu mới cho nhóm số lượng hàng xóm là nhiều hơn

 

   Trong bài toán phân loại đậu-rớt thi Anh văn ở trên, giả sử chọn số điểm "hàng xóm" K = 6

    Có 2 điểm thuộc lớp RỚT, 4 điểm thuộc lớp ĐẬU. So, new data point của chúng ta sẽ thuộc lớp ĐẬU.

LÀM THẾ NÀO ĐỂ BIẾT ĐƯỢC NÊN CHỌN K BẰNG BAO NHIÊU ?

    Thực ra, không có cách cụ thể nào để xác định giá trị tốt nhất cho K, vì vậy chúng ta cần thử một số giá trị để tìm ra giá trị tốt nhất trong số đó. 

+ Giá trị ưu tiên nhất cho K là 5.

+ Giá trị rất thấp của K chẳng hạn như K = 1 hoặc K = 2, có thể bị nhiễu và dẫn đến ảnh hưởng của các giá trị ngoại lệ trong mô hình.

+ Giá trị lớn đối với K là tốt, nhưng nó có thể gặp một số khó khăn.

Vì vậy, hãy thử với nhiều K khác nhau để chọn ra đươc một K đủ lớn cho mô hình của bạn.

3/ ƯU, NHƯỢC ĐIỂM CỦA THUẬT TOÁN K-NN

- Ưu điểm: 

            + Nó là đơn giản để thực hiện

            + Nó mạnh mẽ với dữ liệu đào tạo nhiễu

            + Nó có thể hiệu quả hơn nếu dữ liệu đào tạo lớn

- Nhược điểm:

            + Cần xác định giá trị của K có thể hơi phức tạp một lúc nào đó

            + Chi phí tính toán cao vì tính toán khoảng cách giữa các điểm dữ liệu cho tất cả các mẫu huấn luyện

4/ CODE

import numpy as np

from sklearn.neighbors import KNeighborsClassifier

modelKNN = KNeighborsClassifier(n_neighbors=6)

modelKNN.fit(features_train_array, labels_train_array)

accuracy = modelKNN.score(features_test_array, labels_test_array)

print("* Accuracy is", round(accuracy3 * 100, 2), "%")

# feature là số điểm trong bộ data của bạn

# label là nhãn của feature tương ứng trong bộ data

    Chúng ta nên thử với nhiều giá trị K khác nhau và rút ra sự lựa chọn một giá trị K thích hợp nhất.

import matplotlib.pyplot as plt

# Giả sử mình đã tính toán được các giá trị accuracy1-2-3-4-5-6 tường ứng với K = 1-3-5-7-9-11 rồi nha

plt.plot([1,3,5,7,9,11],[accuracy1*100, accuracy2*100, accuracy3*100, accuracy4*100, accuracy5*100, 

                                                                                    accuracy6*100], "go--")

plt.xlabel("n_neighbors parameter values")

plt.ylabel("model's Accuracy")

plt.title("MODEL RESULTS PERFORMANCE")

plt.show()

    

    Đối với bài toán mà đầu vào là ảnh, feature là các chỉ số màu của từng pixel ảnh (tốt nhất nên

được xử lí cân bằng Histogram) và ảnh sau đó phải được reshape về dạng mảng 2D (để nguyên là mảng 3D),

label thì là nhãn của nội dung từng hình (ví dụ hình chó, hình mèo, ...)

____________________________________________________________________

Mình xin kết thúc bài viết về k-Nearest Neighbour (k-NN) ở đây. 

 

Hy vọng bài viết này của mình có thể giúp người đọc tiếp cận dễ dàng hơn với thuật toán k-NN.

 

Mọi người không hiểu chỗ nào hay có đóng góp gì cứ bình luận ở dưới  mình sẽ giải đáp hoặc cùng nhau học tập nha. 

 

Cảm ơn mọi người rất nhiều...!  💚💙💛