Thuật Toán K-Nearest Neighbors (KNN) Siêu Cơ Bản

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:

  1. Ví dụ đơn thuần nhất
  2. Ý tưởng của KNN
  3. Thực hành với ví dụ thực tế

Ok khởi đầu thôi nào .

1. Ví dụ đơn thuầ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 xử lý 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 tài 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 hiệu 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 tất cả chúng ta hoàn toàn có thể phân loại tài liệu 1 chiều ( 1 feature ) bằng cách làm khá đơn thuần. Và những bạn có nhận thấy rằng tài liệu mình khảo sát càng nhiều, càng rộng thì Dự kiến đưa ra càng đúng chuẩn ( Giả sử lớp bạn không có ai loại khá ngoài bạn thì mặc dầu bạn lấy bao nhiêu người gần điểm bạn nhất củng sẽ ra tác dụng sai ). Okey mình sẽ tiếp tới phần tiếp theo để cùng khám phá tổng quát ý tưởng sáng tạo 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ụ tất cả chúng ta có tài liệu là tuổi, khoản vay và năng lực vở nợ như hình :

Dữ liệu cần phân loại của tất cả chúng ta là { age : 48, loan : 142000 }. Đây dữ liệu 2 chiều và tất cả chúng ta cần Dự kiến người này thuộc rủi ro tiềm ẩn vở nợ hay không. Chúng ta sẽ dùng một cách khá phổ cập để tính khoảng cách là Euclidean. Ví dụ ở hàng tiên phong khoảng cách sẽ được tính :

Thực hiện tương tự như, 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 tài 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 Open nhiều hơn nên tất cả chúng ta sẽ đưa ra Dự kiến người này có năng lực vở nợ .
Vì đây là dử liệu 2 chiều nên tất cả chúng ta củng hoàn toàn có thể màn biểu diễn tài 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 tiễn

Chúng ta sẽ thực hành thực tế ngay với DataSet là thuộc tính của những loài hoa. Các bạn hoàn toà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 tiên phong là chỉ số, 4 cột giữa là những thông số kỹ thuật của mỗi thuộc tính và cột sau cuối là tên của loài hoa đó .

Yêu cầu của tất cả chúng ta là qua những tài liệu đã cho, mình hoàn toàn có thể Dự kiến tên của loài hoa dựa vào những thông số kỹ thuật tựa như. Ok triển khai code thôi .
Đầu tiên mình sẽ import một số ít module thiết yếu nhé :

import csv
import numpy as np
import math

Mình sẽ đi qua từng hàm để mọi người tiện theo dõi
Đầu tiên tất cả chúng ta sẽ đọc tài 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, testSet

Mình sẽ dùng module csv để định dạng tài liệu đọc vào, sau đó chuyển qua ma trận bằng numpy để thuận tiện 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 tiên phong ( thứ tự ), sau đó tất cả chúng ta sẽ sử dụng phương pháp shuffle của numpy.random để trộn tài liệu. Lí do là để sau khi trộn tất cả chúng ta sẽ lấy 50 hàng cuối để làm dữ liệu test .
Tiếp theo tất cả chúng ta sẽ thiết kế 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 lý giải nhiều, nó sẽ triển khai việc đo lường và thống kê tài liệu 2 điểm truyền vào bằng công thức Euclidean. Đơn giản là duyệt qua toàn bộ những 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, sau cuối là trả về căn bậc 2 của tổng đó. ( Nếu bạn thấy khó hiểu hoàn toàn có thể xem lại công thức ở trên )
Tiếp theo là hàm tìm k điểm tài 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 toàn bộ những 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 bắt đầu. Kết quả của vòng lặp này là một list những dictionary gồm tên nhãn ( tên loài hoa ) và khoản cách đến điểm đó. Tiếp theo tất cả 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ì tác dụng tất cả chúng ta chỉ cần biết tên k loài hoa nên tất cả chúng ta sẽ thêm 1 vòng lặp để tạo một list những nhãn có cùng thứ tự. Cuối cùng là trả về k điểm tài liệu đàu tiên của list ( nhỏ nhất )
Và hàm ở đầu cuối là tìm loài hoa Open 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 ans

Chúng ta có list labels là tập hợp những nhãn, sau đó duyệt qua những nhãn đó để tìm nhãn Open nhiều nhất .
Ok. Cuối cùng tất cả chúng ta sẽ duyệt qua những 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à hiệu 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-virginica

Các bạn hoàn toàn có thể thấy hiệu quả tương đối đúng mực. Và để tính độ đúng mực, mình hoàn toàn 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ả độ đúng chuẩn sẽ ~ 0.9

Kết luận:

Trong bài này tất cả chúng ta đã cùng khám phá 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 những bạn thuận tiện tiếp cận với thuật toán KNN hơn. Nếu có quan điểm góp ý gì mọi người hoàn toàn có thể comment bên dưới nhé. Cảm ơn mọi người đã đọc bài

FullCode: gitHub

ĐÁNH GIÁ post
Bài viết liên quan

Tư vấn miễn phí (24/7) 094 179 2255