Tất tần tật về thuật toán K-Nearest Neighbors (KNN) trong Học máy

Danh mục nội dung

1. Thuật toán KNN là gì?

K-Nearest Neighbors (KNN) là một thuật toán học có giám sát (supervised learning) và phi tham số (non-parametric), sử dụng độ gần (proximity) giữa các điểm dữ liệu để phân loại hoặc dự đoán giá trị. Đây là một trong những thuật toán đơn giản và phổ biến nhất được dùng cho cả phân loại (classification) và hồi quy (regression) trong học máy hiện nay. Tuy nhiên thuật toán này thường được dùng nhiều hơn cho phân loại với giả định rằng những điểm dữ liệu có đặc điểm tương tự sẽ nằm gần nhau.

Khi cần phân loại một điểm dữ liệu mới, thuật toán sẽ tìm K điểm gần nhất (nearest neighbors) trong tập dữ liệu huấn luyện và xác định nhãn dựa trên nhãn xuất hiện nhiều nhất trong số các điểm này. Về mặt kỹ thuật, đây thực chất là bỏ phiếu theo số đông, bởi với nhiều nhóm dữ liệu, nhãn có số phiếu cao nhất sẽ được chọn mà không cần đạt quá 50%. Chính nhờ sự trực quan, dễ triển khai và không yêu cầu xây dựng mô hình phức tạp, KNN trở thành lựa chọn phổ biến cho nhiều ứng dụng thực tế, dù vẫn tồn tại hạn chế như tốc độ xử lý chậm với dữ liệu lớn và dễ bị ảnh hưởng bởi dữ liệu nhiễu nếu không được xử lý cẩn thận.

Trong bài toán hồi quy, thuật toán KNN sử dụng nguyên lý tương tự như với bài toán phân loại, nhưng thay vì “bỏ phiếu” để chọn nhãn, thuật toán sẽ lấy giá trị trung bình của K điểm gần nhất (nearest neighbors) để đưa ra dự đoán. Điểm khác biệt chính ở đây là phân loại được dùng cho các giá trị rời rạc, trong khi hồi quy áp dụng với các giá trị liên tục. Tuy nhiên, trước khi có thể phân loại hoặc dự đoán, cần xác định cách đo khoảng cách giữa các điểm dữ liệu. Khoảng cách Euclid (Euclidean distance) là phương pháp được sử dụng phổ biến nhất.

Cũng cần lưu ý rằng KNN thuộc nhóm mô hình “học lười biếng”, nghĩa là thuật toán chỉ lưu trữ dữ liệu huấn luyện mà không thật sự trải qua một giai đoạn huấn luyện. Điều này đồng nghĩa với việc toàn bộ quá trình tính toán chỉ diễn ra khi cần phân loại hoặc dự đoán. Do phụ thuộc nhiều vào bộ nhớ để lưu trữ dữ liệu huấn luyện, KNN còn được gọi là phương pháp học dựa trên mẫu (instance-based learning) hoặc học dựa trên bộ nhớ (memory-based learning).

Evelyn Fix và Joseph Hodges được ghi nhận là những người những người đặt nền móng cho mô hình KNN trong một bài báo năm 1951, sau đó Thomas Cover đã mở rộng khái niệm này trong nghiên cứu “Nearest Neighbor Pattern Classification.” Dù không còn phổ biến như trước, KNN vẫn là một trong những thuật toán vỡ lòng đối với dân khoa học dữ liệu nhờ tính đơn giản và độ chính xác của nó. Tuy nhiên, khi kích thước tập dữ liệu tăng lên, KNN trở nên kém hiệu quả, làm giảm hiệu suất tổng thể của mô hình. Hiện nay, KNN thường được ứng dụng trong các hệ thống gợi ý đơn giản, nhận dạng mẫu, khai thác dữ liệu, dự đoán thị trường tài chính, phát hiện xâm nhập và nhiều lĩnh vực khác.

2. Cách tính KNN: Sử dụng thước đo khoảng cách

Mục tiêu của KNN là xác định K điểm gần nhất với một điểm dữ liệu cần dự đoán để từ đó gán nhãn hoặc đưa ra giá trị dự đoán cho điểm đó. Để làm được điều này, KNN yêu cầu xác định được thước đo khoảng cách – trong đó Euclidean distance là phương pháp được sử dụng phổ biến nhất

2.1. Xác định thước đo khoảng cách

Để xác định những điểm dữ liệu nào gần nhất với một điểm truy vấn (query point), cần tính khoảng cách giữa điểm truy vấn và các điểm dữ liệu còn lại. Các thước đo khoảng cách này giúp tạo ra ranh giới quyết định để phân chia các điểm truy vấn thành những vùng khác nhau và thường được thể hiện bằng biểu đồ Voronoi.

Có nhiều cách để đo khoảng cách, nhưng trong phạm vi bài viết này, chúng ta sẽ tập trung vào phương pháp phổ biến nhất:

Khoảng cách Euclid (p = 2): Đây là thước đo được sử dụng nhiều nhất, áp dụng cho các vectơ có giá trị thực. Công thức này đo đường thẳng giữa điểm truy vấn và các điểm dữ liệu khác.

Khoảng cách Manhattan (p = 1): Đây cũng là một thước đo khoảng cách phổ biến, tính tổng giá trị tuyệt đối của sự chênh lệch giữa các tọa độ của hai điểm. Phương pháp này còn được gọi là khoảng cách taxi hoặc khoảng cách ô phố vì thường được hình dung trên một lưới đường phố, giống như cách bạn di chuyển từ địa chỉ này đến địa chỉ khác theo các con đường trong thành phố.

KNN — Công thức tính khoảng cách Manhattan

Khoảng cách Minkowski: Đây là một dạng tổng quát của cả khoảng cách Euclid và khoảng cách Manhattan. Tham số p trong công thức của Minkowski cho phép tạo ra nhiều thước đo khoảng cách khác nhau. Cụ thể, khi p = 2, công thức trở thành khoảng cách Euclid; còn khi p = 1, nó là khoảng cách Manhattan.

KNN — Công thức tính khoảng cách Minkowski

Khoảng cách Hamming: Đây là kỹ thuật thường được sử dụng với kiểu dữ liệu Boolean hoặc chuỗi ký tự, nhằm xác định vị trí mà các phần tử của hai vectơ không khớp nhau. Vì vậy, nó còn được gọi là chỉ số chồng chéo. Công thức tính khoảng cách Hamming khá đơn giản: đếm số vị trí mà hai vectơ khác nhau.

Ví dụ: Nếu bạn có hai chuỗi ký tự như sau, thì khoảng cách Hamming sẽ bằng 2, vì chỉ có hai ký tự khác nhau giữa hai chuỗi

2.2. Xác định giá trị K trong KNN

Giá trị K trong thuật toán KNN xác định số lượng điểm dữ liệu lân cận gần nhất được xem xét để quyết định phân loại cho một điểm dữ liệu truy vấn. Ví dụ, nếu K = 1, điểm dữ liệu mới sẽ được gán vào cùng lớp với điểm dữ liệu lân cận gần nhất của nó.

Việc chọn giá trị K là một quá trình cần sự cân bằng. Các giá trị K nhỏ có thể dẫn đến phương sai cao (high variance) nhưng độ chệch thấp (low bias), trong khi các giá trị lớn có thể làm tăng độ chệch (high bias) nhưng giảm phương sai (low variance). Lựa chọn này cũng phụ thuộc nhiều vào đặc điểm dữ liệu: nếu dữ liệu có nhiều nhiễu hoặc ngoại lệ, các giá trị K lớn thường cho kết quả tốt hơn. Nhìn chung, nên chọn K là số lẻ để tránh trường hợp hòa phiếu khi phân loại, và kỹ thuật cross-validation có thể giúp bạn tìm ra giá trị K tối ưu cho tập dữ liệu của mình.

3. Ứng dụng của KNN trong Học máy

Tiền xử lý dữ liệu: KNN được dùng để ước lượng các giá trị bị thiếu trong tập dữ liệu bằng một quy trình được gọi là bù dữ liệu thiếu.
Hệ thống gợi ý: Dựa trên dữ liệu hành vi người dùng, KNN có thể gợi ý nội dung hoặc sản phẩm bằng cách nhóm những người dùng có hành vi tương tự và đề xuất dựa trên xu hướng của nhóm đó. Tuy nhiên, với những hệ thống cần xử lý dữ liệu khổng lồ, phương pháp này có thể gặp khó khăn về hiệu suất.
Tài chính: KNN được sử dụng để đánh giá rủi ro tín dụng, dự báo thị trường chứng khoán, tỷ giá hối đoái hay thậm chí phát hiện rửa tiền. Nhờ khả năng học từ dữ liệu lịch sử, thuật toán này giúp đưa ra những dự đoán hỗ trợ ra quyết định trong lĩnh vực tài chính.
Y tế: Trong y tế, KNN được dùng để dự đoán nguy cơ bệnh, chẳng hạn như đánh giá khả năng mắc bệnh tim hoặc ung thư tuyến tiền liệt, bằng cách phân tích dữ liệu về biểu hiện gen hoặc các chỉ số y tế liên quan.
Nhận dạng mẫu: KNN hỗ trợ phân loại văn bản và chữ số viết tay, ví dụ như các con số trên biểu mẫu hoặc phong bì thư.

4. Ưu điểm của KNN

Dễ triển khai: Với cấu trúc đơn giản nhưng vẫn đảm bảo độ chính xác cao, KNN thường là một trong những thuật toán đầu tiên mà người học khoa học dữ liệu tiếp xúc.
Dễ thích nghi: Khi có thêm dữ liệu huấn luyện mới, KNN có thể tự điều chỉnh và cập nhật kết quả mà không cần huấn luyện lại mô hình (vì toàn bộ dữ liệu đều được lưu trữ trong bộ nhớ).
Ít siêu tham số: KNN chỉ cần xác định giá trị K và thước đo khoảng cách, ít hơn nhiều so với hầu hết các thuật toán học máy khác.

5. Nhược điểm của KNN

Khó mở rộng: KNN phải lưu toàn bộ dữ liệu huấn luyện và tính toán mỗi khi dự đoán, gây tiêu tốn tài nguyên và thời gian khi xử lý khối lượng dữ liệu lớn.
Lời nguyền chiều không gian: KNN kém hiệu quả với dữ liệu có nhiều đặc trưng. Khi số đặc trưng vượt mức tối ưu, tỷ lệ lỗi phân loại tăng lên, đặc biệt khi kích thước mẫu nhỏ.
Dễ gặp hiện tượng quá khớp (overfitting): KNN dễ gặp hiện tượng quá khớp, nhất là với giá trị K nhỏ. Dùng giá trị K lớn có thể giảm rủi ro này nhưng nếu quá lớn lại có thể gây nên hiện tượng chưa khớp (underfitting). Các kỹ thuật như chọn lọc đặc trưng và giảm chiều dữ liệu thường được áp dụng để khắc phục.

Nguồn: IBM