Giải thuật k láng giềng gần - kNN(k-Nearest Neighbors)

1. Giới thiệu về thuật toán kNN

Bài toán phân loại dữ liệu là một trong những bài toán thường gặp trong cuộc sống và kĩ thuật. có rất nhiều cách tiếp cận và giải thuật được đưa ra để giải quyết bài toán phân loại. Một trong số đó là thuật toán láng giềng gần kNN(k-Nearest Neighbors)

2. Đầu vào và đầu ra

Thuật toán có 2 đầu vào, một là tập các dữ liệu đã biết trước kiểu(loại) của từng dữ liệu(hay còn gọi là tập huấn luyện - training set), đầu vào thứ 2 là dữ liệu, chúng ta chưa biết kiểu(loại) dữ liệu đó. Đầu ra của thuật toán kNN là kiểu dữ liệu của đầu vào thứ 2.

3. Ví dụ áp dụng trong thực tế

Sau đây là một số ví dụ mẫu minh họa cách áp dụng thuật toán kNN trong thực tế.

Ví dụ 1:  giả sử bạn là một quản trị viên của một trang web, công việc hằng ngày của bạn là phân loại phim theo các thể loại(hài, hành động, tình cảm,...), vấn đề sẽ dễ dàng nếu số lượng phim của bạn là nhỏ, bạn có thể tự coi và dựa vào cảm nhận, quyết định xem phim đó thuộc thể loại nào :). Tuy nhiên vấn đề sẽ trở nên phức tạp, khi số lượng phim rất lớn, thì việc coi từng phim và cảm nhận là điều không tưởng, quá thiếu hiệu quả, lúc đó bạn sẽ bắt đầu nghĩ ngay tới việc sử dụng phần mềm giúp bạn tự động phân loại phim. Nói cách khác, việc phân loại phim chính là bài toán phân loại dữ liệu, và chúng ta có thể sử dụng thuật toán kNN trong trường hợp này.

Ví dụ 2: Bạn được yêu cầu viết một phần mềm, nhận vào một tệp ảnh và đưa ra kết quả đó là tệp ảnh đó miêu tả con số nào từ 0 đến 9. Việc chúng ta làm ở đây phát biểu theo một cách khác đó là xác định xem tệp ảnh đầu vào nằm ở trong kiểu nào? kiểu số 0 hay kiểu số 1 hay kiểu số 2,... hay kiểu số 9.

4. Tư tưởng và cách thức làm việc của giải thuật kNN

Bây giờ chúng ta sẽ đi vào chi tiết cách thức hoạt động của giải thuật kNN. Đầu tiên chúng ta phải chuẩn bị một tập huấn luyện(training set) mà tất cả các dữ liệu trong tập đó đều biết trước được thuộc loại nào. Người dùng sẽ đưa vào một dữ liệu chưa biết được thuộc loại nào. kNN sẽ so sánh dữ liệu đó với tất cả dữ liệu trọng tập huấn luyện và chọn ra k dữ liệu gần giống nhất. Trong k dữ liệu đó, kNN sẽ xem xét xem loại nào là loại chiếm đa số --> và sẽ đưa ra kết luận rằng tập dữ liệu cần xác định thuộc loại đó. Có vẻ cũng hơi khó hiểu nhỉ? Bây giờ chúng ta sẽ đi vào chi tiết một ví dụ, hi vọng là các bạn sau khi xem xong ví dụ, sẽ hiểu rõ hơn :)

Ví dụ này mình lấy trong cuốn "Machine learning in action" của Petter Harington.

Chúng ta sẽ đi phân loại xem một bộ phim thuộc thể loại phim hành động hay phim tình cảm. Việc phân loại phim sẽ được xác định bằng cách đếm số lượng cú đá hoặc số lượng nụ hôn trong phim. Ở đây, chúng ta đã một tập huấn luyện(training set), tập đó chứa một số phim đã biết số lượng cú đá, nụ hôn trong phim đó, và loại phim được cho trong bảng sau:

Tên phim	Số lượng cú đá	Số lượng nụ hôn	Loại phim
California Man	3	104	Tình cảm
He isn't really into dudes	2	100	Tình cảm
Beautiful Woman	1	81	Tình cảm
Kevin Longblade	101	10	Hành động
Robo Slayer 3000	99	5	Hành động
Amped II	98	2	Hành động
?	18	90	Chưa xác định

Chúng ta đã biết được số lượng cú đá, số lượng nụ hôn trong phim. Nhiệm vụ của chúng ta ở đây là xác định xem phim ? thuộc thể loại nào?

Đầu tiên chúng ta sẽ xác định xem sự giống nhau của phim ? với các phim khác như thế nào
Để làm được điều đó, chúng ta sẽ sử dụng euclidean distance.

Euclidean distance là việc chúng ta tìm khoảng cách giữa hai điểm trong không gian, ví dụ cho 2 điểm ${P_1(x_1, y_1)}$ và ${P_2(x_2, y_2)}$ thì Euclidean distance sẽ được tính theo công thức:
$$d = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}$$

Để áp dụng trong euclidean distance vào trong trường hợp này, chúng ta sẽ coi mỗi phim sẽ được biểu diễn bởi một điểm trong tọa độ Oxy với số lượng cú đá là tọa độ x và số lượng nụ hôn là tọa độ y. Điều đó có nghĩa là phim California Man sẽ được biểu diễn bởi điểm (3, 104); phim He isn't really into dudes sẽ được biểu diễn bởi điểm (2, 100), ..

Gọi d là euclidean distance

Thì:

• California Man:

$$d = \sqrt{(18-3)^2 + (90-104)^2} = 20.5$$   

• He isn’t really into dudes:

$$d = \sqrt{(18-2)^2 + (90-100)^2} = 18.7$$ 

• Beautiful Woman:

$$d = \sqrt{(18-1)^2 + (90-81)^2} = 19.2$$ 

• Kevin Longblade:

$$d = \sqrt{(18-101)^2 + (90-10)^2} = 115.3$$ 

• Robo Slayer 3000:

$$d = \sqrt{(18-99)^2 + (90-5)^2} = 117.4$$ 

• Amped II:

$$d = \sqrt{(18-98)^2 + (90-2)^2} = 118.9$$ 

Sau khi tính toán, chúng ta sẽ được bảng sau:

Tên phim	Euclidean distance
California Man	20.5
He isn’t really into dudes	18.7
Beautiful Woman	19.2
Kevin Longblade	115.3
Robo Slayer 3000	117.4
Amped II	118.9

Chúng ta đã có khoảng cách euclidean từ phim chưa biết loại tới từng phim trong tập huấn luyện, giờ chúng ta sẽ tìm ra k làng giềng gần nhất bằng cách sắp xếp các phim theo thứ tự euclidean distance từ nhỏ đến lớn. Giả sử k = 3 thì 3 làng giềng gần nhất, đó là các phim California Man, He isn't really into dudes và Beautiful Woman. thuật toán kNN sẽ lấy loại phim nào chiếm ưu thế trong các láng giếng gần nhất để làm loại phim cho phim cần được xác định loại. Vì 3 phim trên đều là thể loại Tình cảm ==> Phim cần xác định thuộc thể loại phim tình cảm.

5. Nhược điểm của giải thuật kNN

giải thuật kNN thích hợp cho việc phân loại dữ liệu chứ giải thuật này không có khả năng phân tích dữ liệu để tìm ra các thông tin có giá trị. Trong quá trình kNN hoạt động, nó phải tính toán "khoảng cách" từ dữ liệu cần xác định loại đến tất cả các dữ liệu trong tập huấn luyện (training set) ==> nếu tập huấn luyện quá lớn, điều đó sẽ làm cho thời gian chạy của chương trình sẽ rất lâu.