Cùng tìm hiểu về thuật toán phân loại k-NN và các cách mở rộng, cải tiến phổ biến nhất
Trong bài trước, chúng ta đã làm quen với k-NN hồi quy và nguyên lý dự đoán dựa trên khoảng cách. Ở phần này, chúng ta sẽ tiếp tục với k-NN phân loại.
Dù nguyên lý chung không thay đổi, khi áp dụng cho bài toán phân loại, chúng ta có thể khai thác thêm nhiều biến thể như Radius Nearest Neighbors, Nearest Centroid, phân loại đa lớp, và các phương pháp xác suất dựa trên khoảng cách.
Vì vậy, trước khi bàn về các mô hình nâng cao, chúng ta sẽ cùng nhau thực hành thuật toán k-NN cơ bản trên Excel.
Bạn có thể mở [bảng tính Excel/Google Sheet này](https://docs.google.com/spreadsheets/d/1Y1AdACWxNG002UN12q2IAvyqbUB7y5qXmd7UNJ374k/edit?usp=sharing) để theo dõi các ví dụ minh họa.
12q2IAvyqbUB7y5qXmd7UNJ374k/edit?usp=sharing”>
Hình minh họa phân loại k-NN trên Excel do tác giả thực hiện
## Bộ dữ liệu sống sót trên tàu Titanic
Trong phần này, chúng ta sử dụng bộ dữ liệu nổi tiếng về các hành khách trên tàu Titanic, với mỗi dòng là thông tin về một người: hạng vé, giới tính, tuổi, giá vé, và mục tiêu là dự đoán liệu người đó có sống sót hay không.
Bộ dữ liệu Titanic survival – hình minh họa do tác giả thực hiện – giấy phép CC0: Public Domain
## Cách thức phân loại bằng k-NN
Thuật toán k-NN phân loại có nguyên lý rất giống với Sop k-NN hồi quy: đều đi tìm k quan sát gần nhất với điểm cần dự đoán, thông qua khoảng cách.
Ở bước chọn láng giềng gần nhất, chúng ta không sử dụng giá trị y – bất kể đó là số hay nhãn lớp.
Tuy nhiên, khi chuyển sang phân loại, đặc biệt là phân loại nhị phân hoặc đa lớp, cách xử lý kết quả và các đặc trưng đầu vào sẽ có những điểm khác biệt và thú vị.
Chúng ta sẽ bắt đầu với bài toán phân loại nhị phân, sau đó mở rộng sang phân loại nhiều lớp.
### Một đặc trưng liên tục và phân loại nhị phân
Ví dụ với một đặc trưng liên tục, bạn có thể thực hiện k-NN phân loại trên bộ dữ liệu này.
Thông thường, nhãn y sẽ nhận giá trị 0 hoặc 1 để đại diện hai lớp. Tuy nhiên, vì 0 và 1 cũng là số, nên về mặt tính toán, quy trình hoàn toàn giống như hồi quy.
Phân loại k-NN trên Excel – một đặc trưng liên tục – hình minh họa do tác giả thực hiện
Điều khác biệt nằm ở cách diễn giải: khi lấy trung bình các giá trị y của các láng giềng gần nhất, con số này phản ánh tỷ lệ (phần trăm) các láng giềng thuộc lớp 1 – tức là xác suất quan sát mới rơi vào lớp này.
Bạn có thể thử thay đổi giá trị của quan sát mới để kiểm tra và quan sát kết quả dự đoán.
Phân loại k-NN trên Excel – dự đoán cho một đặc trưng liên tục – hình minh họa do tác giả thực hiện
Để đảm bảo không xảy ra trường hợp tỷ lệ ngang bằng giữa hai lớp (ví dụ 50%), chúng ta thường chọn số lượng k là số lẻ để có thể dự đoán theo số đông.
Phân loại k-NN trên Excel – dự đoán cho một đặc trưng liên tục – hình minh họa do tác giả thực hiện
### Hai đặc trưng liên tục cho phân loại nhị phân
Khi có hai đặc trưng đầu vào, cách làm vẫn tương tự như hồi quy k-NN: tính khoảng cách trong không gian hai chiều để chọn k láng giềng gần nhất.
Phân loại k-NN trên Excel – hai đặc trưng liên tục – hình minh họa do tác giả thực hiện
### Một đặc trưng cho phân loại đa lớp
Nếu y có ba nhãn lớp, lúc này chúng ta không thể sử dụng trung bình số học để dự đoán nữa, vì bản chất các giá trị chỉ là ký hiệu xác định nhóm. Thay vào đó, ta sẽ đếm số lượng láng giềng thuộc từng nhóm và dự đoán lớp có tỷ lệ cao nhất.
Phân loại k-NN trên Excel – phân loại đa lớp – hình minh họa do tác giả thực hiện
## Từ k-NN đến Nearest Centroid
### Khi k quá lớn
Nếu tăng k lên cực đại, bằng với tổng số quan sát huấn luyện, kết quả của k-NN hồi quy là giá trị trung bình toàn bộ tập dữ liệu.
Tương tự với phân loại, nếu k bằng tổng số mẫu, mô hình sẽ dự đoán tỷ lệ xuất hiện của từng lớp trong toàn bộ dữ liệu – chỉ còn lại các tỷ lệ tổng quát, không còn khả năng phân biệt điểm mới.
### Tạo ra các centroid
Một bước mở rộng tự nhiên: thay vì dùng tất cả dữ liệu, với mỗi lớp, chúng ta tính trung bình các đặc trưng đầu vào (vector trung bình), gọi là tâm điểm (centroid) của lớp đó.
Khi cần dự đoán cho một điểm mới, chỉ việc đo khoảng cách từ điểm đó đến từng centroid của các lớp và chọn lớp có tâm điểm gần nhất.
Ví dụ, với bộ Titanic, bạn có thể tính tâm điểm cho hai lớp (sống sót và không sống sót) dựa trên tuổi hoặc cả tuổi và giá vé.
Phân loại k-NN trên Excel – Nearest Centroids – hình minh họa do tác giả thực hiện
Khi dùng nhiều đặc trưng liên tục, tâm điểm của mỗi lớp là vector trung bình của các đặc trưng đó.
Phân loại k-NN trên Excel – Nearest Centroids – hình minh họa do tác giả thực hiện
Một số lưu ý quan trọng với mô hình này:
Quy mô (scale) của các đặc trưng ảnh hưởng trực tiếp tới kết quả.
Khi tính tâm điểm, giá trị thiếu sẽ tự động được loại trừ, không gây khó khăn.
* So với k-NN truyền thống (cần lưu toàn bộ dữ liệu), phương pháp này chỉ cần lưu một vector cho mỗi lớp.
### Độ tuyến tính của mô hình
Điểm hạn chế lớn nhất của Nearest Centroid là tính tuyến tính: ranh giới giữa các lớp chỉ phụ thuộc vào vị trí hai tâm điểm, và luôn là một đường thẳng chia đôi không gian đặc trưng.
Ngược lại, k-NN truyền thống có thể tạo ra ranh giới phức tạp, uốn lượn tùy theo vị trí các điểm dữ liệu.
Phân loại k-NN trên Excel – tính tuyến tính của Nearest Centroids – hình minh họa do tác giả thực hiện
### Vì sao centroid không áp dụng cho hồi quy
Phương pháp tâm điểm chỉ áp dụng được với phân loại, vì khi đó tập dữ liệu chia thành các nhóm rõ ràng. Còn với hồi quy, biến mục tiêu y là liên tục, không có nhóm nào để tính tâm điểm riêng biệt. Nếu lấy trung bình toàn bộ y thì đó chỉ là ước lượng trung bình chung, không phân biệt từng vùng giá trị.
Vì vậy, phương pháp Nearest Centroid là một mở rộng tự nhiên cho phân loại, nhưng không áp dụng cho hồi quy.
## Một số cải tiến thống kê khác
Có thể mở rộng k-NN phân loại theo nhiều hướng khác nhau:
### Thống kê trung bình và phương sai
Ngoài trung bình, nếu bổ sung cả phương sai khi xác định tâm điểm cho từng lớp, ta có thể đo khoảng cách bằng khoảng cách Mahalanobis, giúp đánh giá xác suất thuộc về từng lớp dựa trên phân phối đặc trưng của lớp đó.
### Xử lý đặc trưng phân loại
Với các đặc trưng là nhãn (categorical), không thể tính trung bình hay phương sai. Khi đó, ta có thể đếm tỷ lệ xuất hiện từng giá trị của đặc trưng trong mỗi lớp, từ đó ước lượng khả năng quan sát mới thuộc về lớp nào.
Cách làm này cũng là nguyên lý của các mô hình như Categorical Naive Bayes – mỗi lớp được mô tả bằng phân phối tần suất trên từng giá trị của đặc trưng phân loại.
### Khoảng cách có trọng số
Một biến thể khác là gán trọng số cho các láng giềng: những điểm gần hơn sẽ đóng góp nhiều hơn vào dự đoán. Trong scikit-learn, tham số “weights” cho phép cấu hình điều này.
Ngoài ra, có thể chuyển từ việc chọn k láng giềng sang xác định tất cả các điểm nằm trong bán kính cố định quanh điểm mới – gọi là Radius Nearest Neighbors.
### Radius Nearest Neighbors
Một số đồ thị minh họa k-NN classifier thực chất đang dùng ý tưởng bán kính lân cận. Ưu điểm là kiểm soát chính xác vùng lân cận, đặc biệt hữu ích khi hiểu rõ ý nghĩa thực tế của khoảng cách (ví dụ khoảng cách địa lý).
Radius Nearest Neighbors classifier – hình minh họa do tác giả thực hiện
Điểm bất tiện là cần xác định trước bán kính hợp lý cho từng bài toán.
Ý tưởng này cũng có thể áp dụng cho hồi quy.
### Tổng kết các biến thể
Các điều chỉnh nhỏ trên tạo ra những mô hình k-NN khác nhau, mỗi mô hình đều hướng tới việc cải tiến định nghĩa khoảng cách hoặc cách lựa chọn vùng lân cận (k cố định, bán kính, trọng số…), nhằm phù hợp với tính chất dữ liệu thực tế.
Trong phạm vi bài viết này, chúng ta chỉ điểm qua các biến thể phổ biến. Các mô hình này sẽ được triển khai cụ thể trong những bài tiếp theo của tháng này.
Các biến thể và cải tiến của k-NN classifier – hình minh họa do tác giả thực hiện
## Kết luận
Qua bài viết, chúng ta đã tìm hiểu từ k-NN phân loại cơ bản đến các cách mở rộng như Nearest Centroid, Radius Nearest Neighbors, cũng như xử lý đặc trưng dạng phân loại.
Cốt lõi của thuật toán là: phân loại quan sát mới dựa trên mức độ giống với dữ liệu huấn luyện, bằng cách đo khoảng cách hoặc so sánh tần suất xuất hiện trong vùng lân cận.
Khi số lượng láng giềng tăng lên, mô hình dần thu gọn thành các thống kê tổng hợp, dẫn tới phương pháp Nearest Centroid.
Hiểu sâu các ý tưởng dựa trên khoảng cách và xác suất sẽ giúp bạn nhận ra rằng nhiều mô hình machine learning thực ra đều nhằm trả lời một câu hỏi đơn giản:
> Quan sát mới này giống lớp nào nhất?
Trong các bài tới, chúng ta sẽ tiếp tục khám phá các mô hình dựa trên mật độ, là những cách đo lường mức độ tương đồng tổng quát giữa quan sát mới và từng lớp trong dữ liệu.
