KNN (K-Hàng xóm gần nhất) là gì?

K-Láng giềng gần nhất (KNN) là gì?

K-Nearest Neighbors là một kỹ thuật và thuật toán học máy có thể được sử dụng cho cả nhiệm vụ hồi quy và phân loại. K-Những người hàng xóm gần nhất kiểm tra nhãn của một số điểm dữ liệu đã chọn xung quanh một điểm dữ liệu mục tiêu, để đưa ra dự đoán về lớp mà điểm dữ liệu đó rơi vào. K-Nearest Neighbors (KNN) là một thuật toán đơn giản nhưng rất mạnh về mặt khái niệm và vì những lý do đó, đây là một trong những thuật toán máy học phổ biến nhất. Hãy đi sâu vào thuật toán KNN và xem chính xác nó hoạt động như thế nào. Hiểu rõ về cách KNN hoạt động sẽ cho phép bạn đánh giá các trường hợp sử dụng tốt nhất và tồi tệ nhất đối với KNN.

Tổng quan về K-Láng giềng gần nhất (KNN)

Ảnh: Antti Ajanki AnAj qua Wikimedia Commons, CC BY SA 3.0 (https://commons.wikimedia.org/wiki/File:KnnClassification.svg)

Hãy hình dung tập dữ liệu trên mặt phẳng 2D. Hình dung một loạt các điểm dữ liệu trên biểu đồ, trải dọc theo biểu đồ theo cụm nhỏ. KNN kiểm tra sự phân bố của các điểm dữ liệu và tùy thuộc vào các đối số được cung cấp cho mô hình, nó sẽ phân tách các điểm dữ liệu thành các nhóm. Các nhóm này sau đó được gán một nhãn. Giả định chính mà mô hình KNN đưa ra là các điểm/trường hợp dữ liệu tồn tại gần nhau sẽ rất giống nhau, trong khi nếu một điểm dữ liệu cách xa nhóm khác thì điểm dữ liệu đó sẽ khác với các điểm dữ liệu đó.

Mô hình KNN tính toán độ tương tự bằng cách sử dụng khoảng cách giữa hai điểm trên biểu đồ. Khoảng cách giữa các điểm càng lớn thì chúng càng ít giống nhau. Có nhiều cách tính khoảng cách giữa các điểm, nhưng thước đo khoảng cách phổ biến nhất chỉ là khoảng cách Euclide (khoảng cách giữa hai điểm trên một đường thẳng).

KNN là một thuật toán học có giám sát, nghĩa là các ví dụ trong tập dữ liệu phải được gán nhãn cho chúng/các lớp của chúng phải được biết đến. Có hai điều quan trọng khác cần biết về KNN. Đầu tiên, KNN là một thuật toán phi tham số. Điều này có nghĩa là không có giả định nào về tập dữ liệu được đưa ra khi mô hình được sử dụng. Thay vào đó, mô hình được xây dựng hoàn toàn từ dữ liệu được cung cấp. Thứ hai, không có sự phân chia tập dữ liệu thành tập huấn luyện và tập kiểm tra khi sử dụng KNN. KNN không khái quát hóa giữa tập huấn luyện và tập kiểm tra, vì vậy tất cả dữ liệu huấn luyện cũng được sử dụng khi mô hình được yêu cầu đưa ra dự đoán.

Cách một thuật toán KNN hoạt động

Thuật toán KNN trải qua ba giai đoạn chính khi nó được thực hiện:

1. Đặt K thành số hàng xóm đã chọn.
2. Tính toán khoảng cách giữa một ví dụ được cung cấp/thử nghiệm và các ví dụ về tập dữ liệu.
3. Sắp xếp các khoảng cách được tính toán.
4. Lấy nhãn của K mục hàng đầu.
5. Trả về một dự đoán về ví dụ thử nghiệm.

Trong bước đầu tiên, K được người dùng chọn và nó cho thuật toán biết có bao nhiêu hàng xóm (bao nhiêu điểm dữ liệu xung quanh) nên được xem xét khi đưa ra phán đoán về nhóm mà ví dụ đích thuộc về. Trong bước thứ hai, lưu ý rằng mô hình sẽ kiểm tra khoảng cách giữa ví dụ mục tiêu và mọi ví dụ trong tập dữ liệu. Các khoảng cách sau đó được thêm vào một danh sách và được sắp xếp. Sau đó, danh sách đã sắp xếp được kiểm tra và các nhãn cho K phần tử trên cùng được trả về. Nói cách khác, nếu K được đặt thành 5, mô hình sẽ kiểm tra nhãn của 5 điểm dữ liệu gần nhất trên cùng với điểm dữ liệu đích. Khi hiển thị dự đoán về điểm dữ liệu đích, điều quan trọng là tác vụ đó là một hồi quy or phân loại nhiệm vụ. Đối với tác vụ hồi quy, giá trị trung bình của K nhãn trên cùng được sử dụng, trong khi chế độ của K nhãn trên cùng được sử dụng trong trường hợp phân loại.

Các phép toán chính xác được sử dụng để thực hiện KNN khác nhau tùy thuộc vào chỉ số khoảng cách đã chọn. Nếu muốn tìm hiểu thêm về cách tính toán các chỉ số, bạn có thể đọc về một số chỉ số khoảng cách phổ biến nhất, chẳng hạn như Euclide, Manhattanvà chồn.

Tại sao giá trị của K lại quan trọng

Hạn chế chính khi sử dụng KNN là có thể chọn giá trị K không chính xác (số lượng hàng xóm không chính xác được xem xét). Nếu điều này xảy ra, các dự đoán được trả về có thể bị sai lệch đáng kể. Điều rất quan trọng là, khi sử dụng thuật toán KNN, giá trị thích hợp cho K được chọn. Bạn muốn chọn một giá trị cho K để tối đa hóa khả năng đưa ra dự đoán của mô hình trên dữ liệu không nhìn thấy đồng thời giảm số lượng lỗi mà mô hình mắc phải.

Ảnh: Agor153 qua Wikimedia Commons, CC BY SA 3.0 (https://en.wikipedia.org/wiki/File:Map1NN.png)

Các giá trị thấp hơn của K có nghĩa là các dự đoán do KNN đưa ra kém ổn định và đáng tin cậy hơn. Để có được trực giác về lý do tại sao lại như vậy, hãy xem xét trường hợp chúng ta có 7 người hàng xóm xung quanh một điểm dữ liệu mục tiêu. Giả sử rằng mô hình KNN đang hoạt động với giá trị K là 2 (chúng tôi đang yêu cầu mô hình xem xét hai lân cận gần nhất để đưa ra dự đoán). Nếu phần lớn các hàng xóm (năm trên bảy) thuộc lớp Xanh, nhưng hai hàng xóm gần nhất tình cờ là Màu đỏ, thì mô hình sẽ dự đoán rằng ví dụ truy vấn là Màu đỏ. Bất chấp dự đoán của mô hình, trong trường hợp như vậy, Blue sẽ là dự đoán tốt hơn.

Nếu đây là trường hợp, tại sao không chỉ chọn giá trị K cao nhất có thể? Điều này là do việc yêu cầu mô hình xem xét quá nhiều hàng xóm cũng sẽ làm giảm độ chính xác. Khi bán kính mà mô hình KNN xem xét tăng lên, cuối cùng nó sẽ bắt đầu xem xét các điểm dữ liệu gần các nhóm khác hơn là điểm dữ liệu mục tiêu và việc phân loại sai sẽ bắt đầu xảy ra. Ví dụ: ngay cả khi điểm được chọn ban đầu nằm trong một trong các vùng màu đỏ ở trên, nếu K được đặt quá cao, mô hình sẽ tiếp cận các vùng khác để xem xét các điểm. Khi sử dụng mô hình KNN, các giá trị khác nhau của K được thử để xem giá trị nào mang lại cho mô hình hiệu suất tốt nhất.

Ưu và nhược điểm của KNN

Hãy xem xét một số ưu và nhược điểm của mô hình KNN.

Ưu điểm:

KNN có thể được sử dụng cho cả nhiệm vụ hồi quy và phân loại, không giống như một số thuật toán học có giám sát khác.

KNN có độ chính xác cao và sử dụng đơn giản. Thật dễ dàng để giải thích, hiểu và thực hiện.

KNN không đưa ra bất kỳ giả định nào về dữ liệu, nghĩa là nó có thể được sử dụng cho nhiều vấn đề khác nhau.

Nhược điểm:

KNN lưu trữ hầu hết hoặc tất cả dữ liệu, điều đó có nghĩa là mô hình yêu cầu nhiều bộ nhớ và tốn kém về mặt tính toán. Các tập dữ liệu lớn cũng có thể khiến các dự đoán mất nhiều thời gian.

KNN tỏ ra rất nhạy cảm với quy mô của tập dữ liệu và nó có thể bị loại bỏ bởi các tính năng không liên quan khá dễ dàng so với các mô hình khác.

Tóm tắt K-Láng giềng gần nhất (KNN)

K-Nearest Neighbors là một trong những thuật toán học máy đơn giản nhất. Mặc dù KNN đơn giản như thế nào, nhưng về mặt khái niệm, nó cũng là một thuật toán mạnh mang lại độ chính xác khá cao cho hầu hết các vấn đề. Khi bạn sử dụng KNN, hãy đảm bảo thử nghiệm với các giá trị khác nhau của K để tìm số mang lại độ chính xác cao nhất.