K-nearest neighbors là thuật toán học máy có giám sát, đơn giản và dễ triển khai. Thường được dùng trong các bài toán phân loại và hồi quy. Trong bài viết hôm nay, mình và các bạn sẽ cùng tìm hiểu và đi qua một ví dụ đơn giản để hiểu rõ hơn về KNN nhé. Chúng ta sẽ đi qua các phần:
- Ví dụ đơn giản nhất
- Ý tưởng của KNN
- Thực hành với ví dụ thực tế
Ok bắt đầu thôi nào.
1. Ví dụ đơn giản nhất
Bài toán đặt ra: Bạn có điểm của một môn học nhưng bạn không biết thuộc loại nào [Giỏi, khá, trung bình, yếu]. Giả sử bạn không biết bất kì quy tắc nào để phân loại cả.
Có một cách giải quyết là bạn phải đi khảo sát những người xung quanh. Để biết điểm của mình thuộc loại nào thì bạn phải đi hỏi những đứa có điểm gần số điểm mình nhất. Giả sử trong lớp 50 đứa, mình khảo sát 5 đứa gần điểm mình nhất và được dữ liệu như sau:
Điểm của tôi: 7
Điểm của bạn tôi:
- 7.1 => Khá
- 7.2 => Khá
- 6.7 => Khá
- 6.6 => Khá
- 6.4 => Trung bình
Qua kết quả trên thì mình sẽ mạnh dạng đoán là mình loại khá đúng không nào? Với cách này chúng ta có thể phân loại dữ liệu 1 chiều [1 feature] bằng cách làm khá đơn giản. Và các bạn có nhận thấy rằng dữ liệu mình khảo sát càng nhiều, càng rộng thì dự đoán đưa ra càng chính xác [Giả sử lớp bạn không có ai loại khá ngoài bạn thì cho dù bạn lấy bao nhiêu người gần điểm bạn nhất củng sẽ ra kết quả sai]. Okey mình sẽ tiếp tới phần tiếp theo để cùng tìm hiểu tổng quát ý tưởng của thuật toán KNN là gì nhé?
2. Ý tưởng của KNN
Thuật toán KNN cho rằng những dữ liệu tương tự nhau sẽ tồn tại gần nhau trong một không gian, từ đó công việc của chúng ta là sẽ tìm k điểm gần với dữ liệu cần kiểm tra nhất. Việc tìm khoảng cách giữa 2 điểm củng có nhiều công thức có thể sử dụng, tùy trường hợp mà chúng ta lựa chọn cho phù hợp. Đây là 3 cách cơ bản để tính khoảng cách 2 điểm dữ liệu x, y có k thuộc tính:
Ví dụ chúng ta có dữ liệu là tuổi, khoản vay và khả năng vở nợ như hình:
Dữ liệu cần phân loại của chúng ta là {age: 48, loan: 142000}. Đây dữ liệu 2 chiều và chúng ta cần dự đoán người này thuộc nguy cơ vở nợ hay không. Chúng ta sẽ dùng một cách khá phổ biến để tính khoảng cách là Euclidean. Ví dụ ở hàng đầu tiên khoảng cách sẽ được tính:
Thực hiện tương tự, ta sẽ tính được khoảng cách ở cột Distance, từ đó chọn ra k = 3 khoảng cách nhỏ nhất [gần với dữ liệu vào nhất]. Với 3 khoảng cách này chúng ra nhận được 3 label là [Yes, No, Yes]. Trong 3 label này Yes xuất hiện nhiều hơn nên chúng ta sẽ đưa ra dự đoán người này có khả năng vở nợ.
Vì đây là dử liệu 2 chiều nên chúng ta củng có thể biểu diễn dữ liệu trong hệ tọa độ như hình:
Trên hệ tọa độ này chúng ta thể dễ dàng nhận thấy cách chúng ta chọn k điểm gần nhất. Nhưng với dữ liệu lớn, nhiều chiều thì việc biểu diễn dữ liệu trên một không gian là không hề dễ dàng.
3. Thực hành với ví dụ thực tế
Chúng ta sẽ thực hành ngay với DataSet là thuộc tính của các loài hoa. Các bạn có thể tải về tại đây IrisData
Dữ liệu vào là một file csv có 6 cột với cột đầu tiên là chỉ số, 4 cột giữa là các thông số của mỗi thuộc tính và cột cuối cùng là tên của loài hoa đó.
Yêu cầu của chúng ta là qua các dữ liệu đã cho, mình có thể dự đoán tên của loài hoa dựa vào các thông số tương tự. Ok tiến hành code thôi.
Đầu tiên mình sẽ import một số module cần thiết nhé:
import csv
import numpy as np
import mathMình sẽ đi qua từng hàm để mọi người tiện theo dõi
Đầu tiên chúng ta sẽ đọc dữ liệu vào từ file csv:
def loadData[path]:
f = open[path, "r"]
data = csv.reader[f] #csv format
data = np.array[list[data]]# covert to matrix
data = np.delete[data, 0, 0]# delete header
data = np.delete[data, 0, 1] # delete index
np.random.shuffle[data] # shuffle data
f.close[]
trainSet = data[:100] #training data from 1->100
testSet = data[100:]# the others is testing data
return trainSet, testSetMình sẽ dùng module csv để định dạng dữ liệu đọc vào, sau đó chuyển qua ma trận bằng numpy để dễ dàng xử lí
Một số thao tác tiền xử lí gồm: Xóa đi hàng đầu tiên chứa tiêu đề, xóa đi cột đầu tiên [thứ tự], sau đó chúng ta sẽ sử dụng phương thức shuffle của numpy.random để trộn dữ liệu. Lí do là để sau khi trộn chúng ta sẽ lấy 50 hàng cuối để làm dữ liệu test.
Tiếp theo chúng ta sẽ xây dựng hàm tính khoản cách:
def calcDistancs[pointA, pointB, numOfFeature=4]:
tmp = 0
for i in range[numOfFeature]:
tmp += [float[pointA[i]] - float[pointB[i]]] ** 2
return math.sqrt[tmp]Chắc hàm này mình không cần giải thích nhiều, nó sẽ thực hiện việc tính toán dữ liệu 2 điểm truyền vào bằng công thức Euclidean. Đơn giản là duyệt qua tất cả các thuộc tính tương ứng mỗi điểm, tính tổng của hiệu bình phương mỗi thuộc tính, cuối cùng là trả về căn bậc 2 của tổng đó. [Nếu bạn thấy khó hiểu có thể xem lại công thức ở trên]
Tiếp theo là hàm tìm k điểm dữ liệu gần nhất:
def kNearestNeighbor[trainSet, point, k]:
distances = []
for item in trainSet:
distances.append[{
"label": item[-1],
"value": calcDistancs[item, point]
}]
distances.sort[key=lambda x: x["value"]]
labels = [item["label"] for item in distances]
return labels[:k]Hàm này sẽ duyệt qua tất cả các giá trị trong trainSet, tính khoảng cách giữa điểm truyền vào với những điểm trong tập dữ liệu ban đầu. Kết quả của vòng lặp này là một list các dictionary gồm tên nhãn [tên loài hoa] và khoản cách đến điểm đó. Tiếp theo chúng ta sẽ sắp xếp tăng dần list này với giá trị so sánh là khoảng cách. Vì kết quả chúng ta chỉ cần biết tên k loài hoa nên chúng ta sẽ thêm 1 vòng lặp để tạo một list các nhãn có cùng thứ tự. Cuối cùng là trả về k điểm dữ liệu đàu tiên của list [nhỏ nhất]
Và hàm cuối cùng là tìm loài hoa xuất hiện nhiều nhất trong k loài tìm được:
def findMostOccur[arr]:
labels = set[arr] # set label
ans = ""
maxOccur = 0
for label in labels:
num = arr.count[label]
if num > maxOccur:
maxOccur = num
ans = label
return ansChúng ta có list labels là tập hợp các nhãn, sau đó duyệt qua các nhãn đó để tìm nhãn xuất hiện nhiều nhất.
Ok. Cuối cùng chúng ta sẽ duyệt qua các giá trị trong bộ giữ liệu test để kiểu tra:
if __name__ == "__main__":
trainSet, testSet = loadData["./Iris.csv"]
for item in testSet:
knn = kNearestNeighbor[trainSet, item, 5]
answer = findMostOccur[knn]
print["label: {} -> predicted: {}".format[item[-1], answer]]Và đây là kết quả:
label: Iris-versicolor -> predicted: Iris-versicolor
label: Iris-versicolor -> predicted: Iris-versicolor
label: Iris-virginica -> predicted: Iris-virginica
label: Iris-versicolor -> predicted: Iris-versicolor
label: Iris-setosa -> predicted: Iris-setosa
label: Iris-virginica -> predicted: Iris-virginica
label: Iris-versicolor -> predicted: Iris-virginica
label: Iris-setosa -> predicted: Iris-setosa
label: Iris-setosa -> predicted: Iris-setosa
...
label: Iris-versicolor -> predicted: Iris-virginica
label: Iris-setosa -> predicted: Iris-setosa
label: Iris-virginica -> predicted: Iris-virginica
label: Iris-setosa -> predicted: Iris-setosa
label: Iris-virginica -> predicted: Iris-virginica
label: Iris-setosa -> predicted: Iris-setosa
label: Iris-virginica -> predicted: Iris-virginicaCác bạn có thể thấy kết quả tương đối chính xác. Và để tính độ chính xác, mình có thể thêm 1 biến để tính như thế này:
if __name__ == "__main__":
trainSet, testSet = loadData["./Iris.csv"]
numOfRightAnwser = 0
for item in testSet:
knn = kNearestNeighbor[trainSet, item, 5]
answer = findMostOccur[knn]
numOfRightAnwser += item[-1] == answer
print["label: {} -> predicted: {}".format[item[-1], answer]]
print["Accuracy", numOfRightAnwser/len[testSet]]Kết quả độ chính xác sẽ ~0.9
Kết luận:
Trong bài này chúng ta đã cùng tìm hiểu qua về thuật toán KNN ở mức cơ bản nhất. Hi vọng qua ví dụ của mình sẽ giúp các bạn dễ dàng tiếp cận với thuật toán KNN hơn. Nếu có ý kiến góp ý gì mọi người có thể comment bên dưới nhé. Cảm ơn mọi người đã đọc bài