Oleksii Trekhleb | Javascript algorithms (k-Nearest neighbors algorithm)

This is a series of books diving deep into the core mechanisms of the JavaScript language.

 · 2 phút đọc.

This is a series of books diving deep into the core mechanisms of the JavaScript language.

The k-nearest neighbors algorithm (k-NN) is a supervised Machine Learning algorithm. It’s a classification algorithm, determining the class of a sample vector using a sample data.

In k-NN classification, the output is a class membership. An object is classified by a plurality vote of its neighbors, with the object being assigned to the class most common among its k nearest neighbors (k is a positive integer, typically small). If k = 1, then the object is simply assigned to the class of that single nearest neighbor.

The idea is to calculate the similarity between two data points on the basis of a distance metric. Euclidean distance is used mostly for this task.

Euclidean distance between two points

Image source: Wikipedia

The algorithm is as follows:

  1. Check for errors like invalid data/labels.
  2. Calculate the euclidean distance of all the data points in training data with the classification point
  3. Sort the distances of points along with their classes in ascending order
  4. Take the initial K classes and find the mode to get the most similar class
  5. Report the most similar class

Here is a visualization of k-NN classification for better understanding:

KNN Visualization 1

Image source: Wikipedia

The test sample (green dot) should be classified either to blue squares or to red triangles. If k = 3 (solid line circle) it is assigned to the red triangles because there are 2 triangles and only 1 square inside the inner circle. If k = 5 (dashed line circle) it is assigned to the blue squares (3 squares vs. 2 triangles inside the outer circle).

Another k-NN classification example:

KNN Visualization 2

Image source: GeeksForGeeks

Here, as we can see, the classification of unknown points will be judged by their proximity to other points.

It is important to note that K is preferred to have odd values in order to break ties. Usually K is taken as 3 or 5.

nhavantuonglai

Share:
Quay lại.

Có thể bạn chưa đọc

Xem tất cả »

Đăng ký nhận bảng tin hàng tuần

Liên lạc trao đổi

Liên lạc thông qua Instagram

Thông qua Instagram, bạn có thể trao đổi trực tiếp và tức thời, cũng như cập nhật những thông tin mới nhất từ nhavantuonglai.

Tức thời

Bạn có thể gửi và nhận tin nhắn nhanh chóng, trực tiếp, giúp những vấn đề cá nhân của bạn được giải quyết tức thời và hiệu quả hơn.

Thân thiện

Vì tính chất là kênh liên lạc nhanh, nên bạn có thể bỏ qua những nghi thức giao tiếp thông thường, chỉ cần lịch sự và tôn trọng thì sẽ nhận được sự phản hồi đầy thân thiện, thoải mái từ tác giả.

Trao đổi trên email

Thông qua email cá nhân, bạn có thể trao đổi thỏa thuận hợp tác, kết nối chuyên sâu và mang tính chuyên nghiệp.

Tin cậy

Trong một số trường hợp, email được dùng như một tài liệu pháp lý, chính vì vậy mà bạn có thể an tâm và tin cậy khi trao đổi với tác giả thông qua email.

Chuyên nghiệp

Cấu trúc của email đặt tính chuyên nghiệp lên hàng đầu, nên những thông tin, nội dung được viết trong email từ tác giả sẽ luôn đảm bảo điều này ở mức cao nhất.