KNN - một giải thuật "siu" cơ bản trong Học máy

Xin chào các bạn, lại là mình đây, để nối tiếp series ở bài trước, ngày hôm nay mình sẽ giới thiệu đến các bạn một giải thuật siêu cơ bản trong Học máy, cụ thể hơn là trong Học có giám sát đó chính là KNN. Có thể đây là lần đầu tiên bạn tiếp xúc với lĩnh vực nãy, để tiện cho việc theo dõi cũng như dễ hiểu hơn, mình sẽ giải thích những khái niệm được sử dụng trong bài ở phần I, tiếp theo phần II là phần thuật toán. Nếu các bạn đã biết, mời các bạn bỏ qua phần này để đến với phần II. Let’s go thôi nào các bạn êiiii

I. Một số khái niệm được sử dụng trong bài

1. Observation

Observation (sự quan sát) là input (data point) của bài toán. Thường được kí hiệu là một vector gồm n thành phần, mỗi thành phần được gọi là một feature (đặc trưng) của input, vector đó được goi là feature vector :

Ví dụ: Để xác định hôm nay trời có mưa hay không, bạn sẽ quan sát các yếu tố về thời tiết như “nhiệt độ, độ ẩm, gió, mây”. mỗi thành phần được xem là một feature, tập hợp tất cả các feature được gọi là observation của dữ liệu.

2.Label

Label chính là nhãn của observation được đề cập ở trên. Được ký hiệu là y. Mỗi observation sẽ có một nhãn tương ứng. Ví dụ như với x = [23 độ C, 95%, gió cấp 3, nhiều mây] thì khả năng nhãn của observation này là Mưa. Nhãn của dữ liệu có thể ở dạng binary hoặc có thể là ổ dạng số thực.

3. Model

Trong phạm vi này, bạn có thể hiểu rằng nó chính là một hàm số f(x) để ánh xạ các giá trị của observation sang giá trị khác. Kết quả của giá trị này là label cần tìm của mô observation. Model được huấn luyện bằng cách cho model “học” những đặc trưng của dữ liệu.

Hình 1: Tổng quan cách huấn luyện model

4. Độ đo

Mục đích ta đánh giá mô hình Machine Learning nhằm giúp cho team nhận thức được rằng chuyện gì đang xảy ra với mô hình của mình, từ đó xác định được ta nên làm gì tiếp theo. Và để tiến hành đo đạc độ hiệu quả của mô hình, chúng ta cần xây dựng các phương pháp độ đo để đánh giá. Một số độ đo thông dụng được sử dụng trong phân lớp như :

Accuracy (độ chính xác): Cách đánh giá này đơn giản tính tỉ lệ giữa số điểm được dự đoán đúng và tổng số điểm trong tập dữ liệu kiểm thử
Precision: Được định nghĩa là tỉ lệ số điểm true positive trong số những điểm được phân loại là positive (TP + FP).
Recall: Được định nghĩa là tỉ lệ số điểm true positive trong số những điểm thực sự là positive (TP + FN).

Hình 2: Cách tính Precision và Recall

….

Ngoài ra còn rất nhiều độ đo để đánh giá một hệ thống phân lớp, các bạn có thể tham khảo thêm tại đây.

II. KNN – một thuật toán siêu cơ bản trong học giám sát

Trước khi bước vào giải thích KNN là gì, chúng ta cùng xét qua một ví dụ vui như sau:

Như các bạn đã biết, đối với học sinh, sinh viên chúng ta, việc hỏi bài trong lúc kiểm tra là một thông lệ không thể nào thiếu được. Trong một tiết kiểm tra nọ, vì lý do đề khó hay không có đủ kiến thức mà bạn Thạch có một câu không biết làm, tuy nhiên xung quanh bạn ấy có 4 bạn làm ra kết quả rồi. Mặc dù giám thị rất khắc khe nhưng bằng cách nào đó bạn Thạch đã hỏi được đáp án của 4 bạn đó, và 3 đã trong 4 bạn cho kết quả là 1, và một bạn cho kết quả là 2. Vì niềm tin là càng nhiều bạn làm ra kết quả giống nhau thì khả năng kết quả đó là đúng nên bạn Thạch quyết định kết quả cho bài làm của mình là 1.

Tuy chỉ là một ví dụ vui nhưng đó chính là ý tưởng của thuật toán KNN. KNN (K-Nearest Neighbors) là một thuật toán đơn giản nhất trong nhóm thuật toán Học có giám sát. Ý tưởng của thuật toán này đó là tìm output của một dữ liệu mới dựa trên output của K điểm gần nhất xung quanh nó. KNN được ứng dụng nhiều trong khai phá dữ liệu và học máy. Trong thực tế, việc đo khoảng cách giữa các điểm dữ liệu, chúng ta có thể sử dụng rất nhiều độ đo, tiêu biểu như là Mahatan, Ơ-clit, cosine,…

Hình 3: Minh họa thuật toán KNN

Ví dụ như hình trên, để gán nhãn cho điểm dữ liệu màu cam, ta xét K = 5 điểm gần nhất xung quanh nó. Nhận thấy trong 5 điểm đó, có 3 điểm mang dữ liệu âm và 2 điểm mang dữ liệu dương. Như vậy ta sẽ gán nhãn cho điểm màu cam sẽ là mang giá trị âm.

Thuật toán của KNN có thể được mô tả như sau:

Thuật toán:

Xác định tham số K số làng giềng gần nhất
Tính khoảng cách của đối tượng cần phân lớp tới tất cả các đối tượng có trong tập train
Lấy top K cho giá trị nhỏ nhất (hoặc lớn nhất)
Trong top K giá trị vừa lấy, ta thống kê số lượng của mỗi lớp, chọn phân lớp cho số lượng lớn nhất

Một câu hỏi đặt ra đó là có phải cứ chọn K càng lớn thì càng tốt, thì câu trả lời đó là còn tùy thuộc vào dữ liệu đó như thế nào. Không phải lúc nào K càng lớn thì cho kết quả tốt và ngược lại. Việc lựa chọn tham số K của mô hình sẽ tiến hành thông qua thực nghiệm nhiều lần để chọn ra kết quả tốt nhất.

Với các bước như trên, chúng ta nhận thấy rằng thuật toán của KNN rất đơn giản, dễ thực hiện, dễ cài đặt. Việc dữ đoán kết quả thật là dễ dàng, độ phức tạp của thuật toán nhỏ. Bên cạnh đó sẽ tồn tại nhiều nhược điểm như:

Ý tưởng của thuật toán này là nó không học một điều gì từ tập dữ liệu học (nên KNN được xếp vào loại lazy learning), mọi tính toán được thực hiện khi nó cần dự đoán nhãn của dữ liệu mới.Nếu tập train của chúng ta có kích thước rất lớn, thì việc duyệt qua tất cả các điểm dữ liệu để tính toán là rất mất thời gian, đặt biệt là trong thời kỳ hiện nay thì dữ liệu thu thập được rất lớn
KNN rất nhạy cảm với dữ liệu nhiễu, đặc biệt là khi ta chọn K nhỏ. Việc này sẽ dẫn đễn kết quả không tốt.

Thực hành

Trong bài viết này, mình sẽ hướng dẫn các bạn xây dựng bộ phân lớp cho bộ dữ liệu Titanic bằng việc sử dụng kỹ thuật KNN. Bài viết này sẽ hướng dẫn các bạn thực hiện coding trên cả 2 level đó là tự thực hiện lại bằng thuật toán và sử dụng hàm có sẵn trong pyhton. Còn chần chừ gì nữa, xoắn tay áo lên làm ngay nào !!!

Trước tiên, chúng ta tìm hiểu sơ qua bộ dữ liệu mà ta đang dùng.

Hình 4: Thông tin cơ bản về bộ Titanic dataset

Nhiệm vụ của bài toán bây giờ là sẽ tiến hành phân loại “sự sống” dựa trên các thuộc tính mà dataset cung cấp. Chúng ta sẽ tiến hành thực hiện coding bằng ngôn ngữ python trên Google Colab – một dịch vụ miễn phí của Google nhằm hỗ trợ nghiên cứu và học tập về AI. Colaboratory cung cấp môi trường Code như Jupyter Notebook và có thể sử dụng GPU và TPU miễn phí. Để tiến hành tạo một notebook trên Colab bạn có thể tham khảo tại đây

Bước 1. Kết nối Colab với Google Drive

from google.colab import drive
drive.mount('/content/drive')

Bước 2. Tiến hành download bộ dữ liệu Titanic. Bạn đọc có thể dowload tại link này. sau đó các bạn giải nén, đổi đuôi .data cùa file Dataset.data thành đuôi .csv

Bước 3. Import một số thư viện cần thiết

import pandas as pd
import numpy as np
from sklearn.model_selection import train_test_split
from sklearn.preprocessing import LabelEncoder

Bước 4. Tiền xử lý dữ liệu

Hãy tưởng tượng rằng nếu như một đứa trẻ ở trong một môi trường giáo dục tốt thì khả năng cao sẽ đào tạo ra một công dân giỏi, và ngược lại. Trong Học máy cũng vậy, để thực hiện train một mô hình thì việc xử lý dữ liệu trước khi đưa vào mô hình là rất quan trọng.Một mô hình có thực sự tốt hay không phụ thuộc rất nhiều vào việc chúng ta xử lý dữ liệu như thế nào. Trước tiên ta phải trực quan hóa dữ liệu để có cái nhìn tổng quát về dữ liệu:

# dùng thư viện pandas đọc dữ liệu từ file Dataset.csv
df = pd.read_csv("Dataset.csv")
df.head()

Kết quả:

Dựa vào kết quả trả về, ta thấy rằng mỗi điểm dữ liệu có 3 thuộc tính, kèm theo nhãn.Tất cả thông tin của dữ liệu đều được lưu dưới dạng chuỗi, thế nên ta sẽ tiến hành xử lý để đưa về dạng số:

# Thuộc tính thứ nhất
social = []

# Thuộc tính thứ 2
age = []

# Thuộc tính thứ 3
sex = []

# Nhãn 
labels = []
for infor in df[:][0]:
    temp = infor.split() # Tách các thuộc  tính bởi dấu phẩy
    social.append(temp[0]) # Lấy thuộc tính thứ nhất
    age.append(temp[1]) # Lấy thuộc tính thứ 2
    sex.append(temp[2]) # Lấy thuộc tính thứ 3
    labels.append(temp[3]) # Lấy nhãn

Sau bước này, ta đã tách các thuộc tính và nhãn của dữ liệu thành các vector riêng biệt. Nhiệm vụ bây giờ là tiến hành mã hóa dữ liệu về dạng số. Đến đây, một suy nghĩ đơn giản đó là chúng ta sẽ tiến hành ánh xạ từ chữ sang số bằng một quy ước nào đó. Ví dụ như trong thuộc tính sex, ta sẽ tiến hành gán male = 0, female = 1, những thuộc tính khác cũng tương tự như vậy. Thế nhưng các bạn để ý rằng “female” và “male” rõ ràng là không phụ thuộc lẫn nhau nghĩa là chúng hoàn toàn có thể xảy ra một cách độc lập. Nếu như chúng ta đánh trọng số cho male = 0 và female = 1 thì rõ ràng là đang thiên vị cho thuộc tính famale. Như vậy, câu hỏi đặt ra là có cách nào mã hóa chúng sang dạng số mà giá trị trọng số của mỗi thuộc tính vẫn giữ được sự công bằng ? Câu trả lời là có !! Chúng ta sẽ sử dụng kĩ thuật one-hot encoding để tiến hành mà hóa, các bạn có thể đọc thêm tại link này. Với kỹ thuật này chúng ta sẽ xem những thuộc tính con của mỗi thuộc mà ta đang xét sẽ là một thuộc tính của dữ liệu. Để hình dung, chúng ta có thể lấy ví dụ sau: Thay vì mỗi điểm hiện tại của chúng ta có 3 thuộc tính, trong đó thuộc tính sex có 2 thuộc tính con đó là male và female. Bây giờ ta sẽ thay thuộc tính sex bởi hai thuộc tính con của nó: Ban đầu (social,age,sex) sẽ được thay bằng (social,age,male,female). Đến đây, thay vì quy ước male = 0 và female = 1, ta sẽ quy ước giá trị của thuộc tính đó sẽ là một nếu như điểm dữ liệu đang xét chứa thuộc tính đó, và sẽ bằng 0 nếu thuộc tính đó không xuất hiện trong điểm dữ liệu mà ta đang xét.

Ví dụ:
một người có giới tính nam sẽ được biểu diễn là [0,1]
một người có giới tính nam sẽ được biểu diễn là [1,0]
Thay vì biểu diễn như trước đây là nam:0 và nữ:1

Như vậy với one-hot encoding chúng ta sẽ tăng thêm số lượng đặc trưng của điểm dữ liệu đồng thời giúp loại bỏ sự thiên vị trong việc ánh xạ từ một giá trị là phi số sang giá trị số. Tương tự cho các thuộc tính còn lại. Hàm “one_hot_vector” sẽ thực hiện công việc này:

def one_hot_vector(num_class,vector):
    # Đánh index cho thuộc tính của vector
    # Ví dụ ["a","b","c"] --> [0,1,2]
    vector = LabelEncoder().fit_transform(vector)
    target = np.array([vector]).reshape(-1)
    # one-hot
    oh = np.eye(num_class)[target]
    return oh

Mã hóa các thuộc tính (bằng cách gọi hàm one_hot_vecote vừa tạo ở trên) và labels. Input của chúng ta là toàn bộ các thuộc tính, vì vậy chúng ta cần phải merge các thuộc tính lại với nhau.

# one - hot
social = one_hot_vector(4,social)
age = one_hot_vector(2,age)
sex = one_hot_vector(2,sex)

# Mã hóa label về dạng Binary
labels = LabelEncoder().fit_transform(labels)
# Merge các feature lại với nhau
X = np.concatenate((social.T,age.T,sex.T)).T

Sau đó tiến hành chia dữ liệu train và dữ liệu test, trong bài này mình chia train-test theo tỷ lệ là 8:2 bằng hàm train_test_split

X_train,X_test,y_train,y_test = train_test_split(X,labels, random_state=42, shuffle=True,test_size=0.2)

Tén, ten!!. Đến đây coi như chúng ta đã xong công đoạn tiền xử lý dữ liệu. Giai đoạn cuối cùng của chúng ta là tiến hành cài đặt thuật toán và test kết quả thôi nào.

Bước 5. Cài đặt thuật toán

Đối với bạn nào muốn code lại từ đầu theo thuật toán của KNN, chúng ta có thể tham khảo cách cài đặt của hàm KNN như sau:

def KNN(X_train,X_test,y_train,k):
    num_test = X_test.shape[0] # số lượng dữ liệu test
    num_train = X_train.shape[0] # số lượng dữ liệu train
    # y_pred là một ma trận, mỗi hàng tương ứng là khoảng cách của một điểm dữ liệu trong tập test đối với tất cả các điểm dữ liệu trong tập train
    y_pred = np.zeros((num_test,num_train))
    # duyệt qua mỗi điểm trong tập test
    for i in range(num_test):
    # tương ứng một điểm trong tập test sẽ duyêt qua hết bộ train
        for j in range(num_train):
    # tính khoảng cách tới tập train 
            y_pred[i,j] = np.sqrt(np.sum(np.power(X_test[i,:]-X_train[j,:],2)))  
    results = []
    # sắp xếp theo chiều tăng dần khoảng cách
    for i in range(len(y_pred)):
        zipped = zip(y_pred[i,:],y_train)
        res = sorted(zipped,key = lambda x:x[0]) 
        results_topk = res[:k]
    # Đếm số lượng của mỗi class
        classes = {}
        for _,j in results_topk:
            j = int(j)
            if j not in classes:
                classes[j] = 1
            else:
                classes[j] = classes[j] + 1 
        # trả về class có số lượng nhiều nhất
        results.append(max(classes,key = classes.get))
    return np.array(results)

Trong bài toán này, chúng ta sẽ sử dụng độ đo accuracy.Ta sẽ dự đoán kết quả với K = 3, các bạn có thể thử với nhiều tham số K để chọn ra K cho phù hợp:

def Accuracy(y_test,y_pred):
    dem = 0
    for i in range(len(y_test)):
        if y_test[i] == y_pred[i]:
            dem += 1
    return dem/len(y_test)*100

# gọi hàm KNN
results = KNN(X_train,X_test,y_train,3)

# in accuracy
print(Accuracy(result,y_test))

# Kết quả xấp xỉ 78.2312925170068

Đối với các bạn không cần quan tâm đến chi tiết của thuật toán, chỉ quan tâm đến ý tưởng của mô hình thì rất may mắn là thư viện sklearn có hộ trợ sẵn cho ta hàm train model luôn. Code thực hiện tương đối ngắn, các bạn có thể tham khảo dưới đây

from sklearn.neighbors import KNeighborsClassifier
neigh = KNeighborsClassifier(n_neighbors=3)
# train
neigh.fit(X_train, y_train)

# predict
results = neigh.predict(X_test)
# accuracy

print(Accuracy(y_test,results))

Test trên một mẫu bất kì

Lời kết: Trên đây là tổng quan về mô hình KNN đi kèm là hướng dẫn thực hiện coding thuật toán mà mình muốn giới thiệu đến các bạn Mình hy vọng thông qua bài viết này các bạn có thể hình dung một các rõ ràng hơn về giải thuật này. Trong bài viết tiếp theo, chúng ta sẽ đi vào tìm hiểu về một giải thuật phân lớp tiếp theo trong Supervised Learning đó là Naive Bayes và Decision Tree, hi vọng mọi người theo dõi. Mọi đóng góp của các bác chính là động lực để mình hoàn thiện và phát triển bài viết tốt hơn.