AI 101
KNN (K-Nearest Neighbors) là gì?
KNN (K-Nearest Neighbors) là gì?
K-Nearest Neighbors là một kỹ thuật học máy và thuật toán có thể được sử dụng cho cả nhiệm vụ hồi quy và phân loại. K-Nearest Neighbors kiểm tra các nhãn của một số điểm dữ liệu được 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 thuộc về. K-Nearest Neighbors (KNN) là một thuật toán đơn giản về mặt khái niệm nhưng rất mạnh mẽ, và vì những lý do đó, nó là một trong những thuật toán học máy phổ biến nhất. Hãy cùng tìm hiểu về thuật toán KNN và xem nó hoạt động như thế nào. Việc hiểu rõ cách KNN hoạt động sẽ giúp bạn đánh giá cao các trường hợp sử dụng tốt nhất và tồi tệ nhất cho KNN.
Tổng quan về K-Nearest Neighbors (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 một tập dữ liệu trên một mặt phẳng 2D. Hãy tưởng tượng một loạt điểm dữ liệu trên một đồ thị, phân bố trên đồ thị thành các 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 tham số được đưa vào mô hình, 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 dữ liệu/đối tượng tồn tại gần nhau là rất tương tự, trong khi nếu một điểm dữ liệu cách xa một nhóm khác thì nó không tương tự với các điểm dữ liệu đó.
Mô hình KNN tính toán sự tương tự bằng cách sử dụng khoảng cách giữa hai điểm trên một đồ thị. Khoảng cách giữa các điểm càng lớn, sự tương tự càng thấp. Có nhiều cách để tính toán khoảng cách giữa các điểm, nhưng metric khoảng cách phổ biến nhất là khoảng cách Euclid (khoảng cách giữa hai điểm trong một đường thẳng).
KNN là một thuật toán học máy có giám sát, có nghĩa là các ví dụ trong tập dữ liệu phải có nhãn được gán cho chúng/lớp của chúng phải được biết. 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 không tham số. Điều này có nghĩa là không có giả định nào về tập dữ liệu được thực hiện 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 đưa ra bất kỳ sự khái quát nào 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.
Thuật toán KNN hoạt động như thế nào
Thuật toán KNN đi qua ba giai đoạn chính khi nó được thực hiện:
- Đặt K là số lượng hàng xóm được chọn.
- Tính toán khoảng cách giữa một ví dụ/test được cung cấp và các ví dụ trong tập dữ liệu.
- Sắp xếp các khoảng cách đã tính toán.
- Lấy các nhãn của các mục nhập hàng đầu K.
- Trả về một dự đoán về ví dụ kiểm tra.
Trong bước đầu tiên, K được chọn bởi người dùng và nó thông báo cho thuật toán số lượng hàng xóm (số lượng điểm dữ liệu xung quanh) cần được xem xét khi đưa ra phán quyết về nhóm mà ví dụ mục tiêu thuộc về. Trong bước thứ hai, lưu ý rằng mô hình 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à sắp xếp. Sau đó, danh sách được sắp xếp và các nhãn của các mục nhập hàng đầu K được trả về. Nói cách khác, nếu K được đặt là 5, mô hình sẽ kiểm tra các nhãn của 5 điểm dữ liệu gần nhất với điểm dữ liệu mục tiêu. Khi đưa ra dự đoán về điểm dữ liệu mục tiêu, nó quan trọng nếu nhiệm vụ là hồi quy hoặc phân loại. Đối với nhiệm vụ hồi quy, trung bình của các nhãn hàng đầu K được sử dụng, trong khi chế độ của các nhãn hàng đầu K được sử dụng trong trường hợp phân loại.
Các hoạt động toán học chính xác được sử dụng để thực hiện KNN khác nhau tùy thuộc vào metric khoảng cách được chọn. Nếu bạn muốn tìm hiểu thêm về cách các metric được tính toán, bạn có thể đọc về một số metric khoảng cách phổ biến nhất, chẳng hạn như Euclid, Manhattan và Minkowski.
Tại sao giá trị của K lại quan trọng
Giới hạn chính khi sử dụng KNN là việc chọn giá trị K không phù hợp (số lượng hàng xóm không chính xác cần được xem xét) có thể được chọn. Nếu điều này xảy ra, các dự đoán được trả về có thể không chính xác. Điều quan trọng là, khi sử dụng thuật toán KNN, giá trị phù hợp cho K phải được chọn. Bạn muốn chọn một giá trị cho K mà tối đa hóa khả năng của mô hình trong việc đưa ra dự đoán trên dữ liệu không nhìn thấy trong khi giảm số lượng lỗi nó tạo ra.
Ảnh: Agor153 qua Wikimedia Commons, CC BY SA 3.0 (https://en.wikipedia.org/wiki/File:Map1NN.png)
Giá trị K thấp hơn có nghĩa là dự đoán được đưa ra bởi KNN ít ổn định và tin cậy hơn. Để có được trực giác về lý do tại sao điều này xảy ra, hãy xem xét một trường hợp chúng ta có 7 hàng xóm xung quanh một điểm dữ liệu mục tiêu. Giả sử mô hình KNN đang làm việc với giá trị K là 2 (chúng tôi yêu cầu nó xem xét hai hàng xóm gần nhất để đưa ra dự đoán). Nếu đa số hàng xóm (5 trong 7) thuộc về lớp Xanh, nhưng hai hàng xóm gần nhất chỉ happens to là Đỏ, mô hình sẽ dự đoán rằng ví dụ kiểm tra là Đỏ. Mặc dù mô hình đưa ra dự đoán, trong một kịch bản như vậy, Xanh sẽ là một dự đoán tốt hơn.
Nếu đó là trường hợp, tại sao không chọn giá trị K cao nhất có thể? Điều này là vì việc yêu cầu mô hình xem xét quá nhiều hàng xóm cũng sẽ giảm độ chính xác. Khi bán kính mà mô hình KNN xem xét tăng lên, 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à sự 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 khu vực đỏ trên, nếu K được đặt quá cao, mô hình sẽ mở rộng để xem xét các điểm trong các khu vực khác. Khi đưa ra dự đoán về điểm dữ liệu mục tiêu, điều quan trọng là nhiệm vụ là hồi quy hoặc phân loại. Đối với nhiệm vụ hồi quy, trung bình của các nhãn hàng đầu K được sử dụng, trong khi chế độ của các nhãn hàng đầu K được sử dụng trong trường hợp phân loại.
Các giá trị K khác nhau được thử nghiệm để xem giá trị nào mang lại hiệu suất tốt nhất cho mô hình.
Ưu và nhược điểm của KNN
Hãy cùng 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 máy có giám sát khác.
KNN rất chính xác và đơn giản để sử dụng. Nó dễ dàng giải thích, hiểu và triển khai.
KNN không đưa ra bất kỳ giả định nào về dữ liệu, có 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, có nghĩa là mô hình yêu cầu nhiều bộ nhớ và tính toán tốn kém. Các tập dữ liệu lớn cũng có thể gây ra dự đoán mất nhiều thời gian.
KNN chứng minh rất nhạy cảm với quy mô của tập dữ liệu và nó có thể bị ảnh hưởng 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ổng kết về K-Nearest Neighbors (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 về mặt khái niệm, nó cũng là một thuật toán mạnh mẽ mang lại độ chính xác khá cao trên 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ị K khác nhau để tìm giá trị mang lại độ chính xác cao nhất.
