Thuật toán KNN - Tìm những người hàng xóm gần nhất
Giới thiệu
Thuật toán K-láng giềng gần nhất (KNN) là một loại thuật toán ML có giám sát có thể được sử dụng cho cả phân loại cũng như các bài toán dự đoán hồi quy. Tuy nhiên, nó chủ yếu được sử dụng để phân loại các vấn đề dự đoán trong công nghiệp. Hai thuộc tính sau sẽ xác định tốt KNN:
Lazy learning algorithm - KNN là một thuật toán lười học vì nó không có giai đoạn huấn luyện chuyên biệt và sử dụng tất cả dữ liệu để huấn luyện trong khi phân loại.
Non-parametric learning algorithm - KNN cũng là một thuật toán học phi tham số vì nó không giả định bất cứ điều gì về dữ liệu bên dưới.
Hoạt động của thuật toán KNN
Thuật toán K-láng giềng gần nhất (KNN) sử dụng 'tính năng tương tự' để dự đoán giá trị của các điểm dữ liệu mới, điều này có nghĩa là điểm dữ liệu mới sẽ được chỉ định một giá trị dựa trên mức độ phù hợp chặt chẽ của nó với các điểm trong tập huấn luyện. Chúng tôi có thể hiểu cách hoạt động của nó với sự trợ giúp của các bước sau:
Step 1- Để thực hiện bất kỳ thuật toán nào, chúng ta cần tập dữ liệu. Vì vậy trong bước đầu tiên của KNN, chúng ta phải tải dữ liệu huấn luyện cũng như kiểm tra.
Step 2- Tiếp theo, chúng ta cần chọn giá trị của K tức là các điểm dữ liệu gần nhất. K có thể là bất kỳ số nguyên nào.
Step 3 - Đối với mỗi điểm trong dữ liệu kiểm tra, hãy làm như sau:
3.1- Tính toán khoảng cách giữa dữ liệu kiểm tra và mỗi hàng dữ liệu đào tạo với sự trợ giúp của bất kỳ phương pháp nào cụ thể là: Khoảng cách Euclidean, Manhattan hoặc Hamming. Phương pháp thông dụng nhất để tính khoảng cách là Euclidean.
3.2 - Bây giờ, dựa trên giá trị khoảng cách, hãy sắp xếp chúng theo thứ tự tăng dần.
3.3 - Tiếp theo, nó sẽ chọn K hàng trên cùng từ mảng đã sắp xếp.
3.4 - Bây giờ, nó sẽ chỉ định một lớp cho điểm kiểm tra dựa trên lớp thường xuyên nhất của các hàng này.
Step 4 - Kết thúc
Thí dụ
Sau đây là một ví dụ để hiểu khái niệm K và hoạt động của thuật toán KNN:
Giả sử chúng ta có một tập dữ liệu có thể được vẽ như sau:
Bây giờ, chúng ta cần phân loại điểm dữ liệu mới với chấm đen (tại điểm 60,60) thành lớp màu xanh lam hoặc màu đỏ. Chúng tôi giả sử K = 3 tức là nó sẽ tìm thấy ba điểm dữ liệu gần nhất. Nó được hiển thị trong sơ đồ tiếp theo -
Chúng ta có thể thấy trong biểu đồ trên ba láng giềng gần nhất của điểm dữ liệu với chấm đen. Trong số ba người đó, hai trong số chúng nằm trong lớp Đỏ do đó chấm đen cũng sẽ được gán trong lớp đỏ.
Triển khai bằng Python
Như chúng ta đã biết, thuật toán K-láng giềng gần nhất (KNN) có thể được sử dụng cho cả phân loại cũng như hồi quy. Sau đây là các công thức trong Python để sử dụng KNN làm bộ phân loại cũng như bộ hồi quy:
KNN làm Bộ phân loại
Đầu tiên, hãy bắt đầu với việc nhập các gói python cần thiết -
import numpy as np
import matplotlib.pyplot as plt
import pandas as pdTiếp theo, tải xuống tập dữ liệu mống mắt từ liên kết web của nó như sau:
path = "https://archive.ics.uci.edu/ml/machine-learning-databases/iris/iris.data"Tiếp theo, chúng ta cần gán tên cột cho tập dữ liệu như sau:
headernames = ['sepal-length', 'sepal-width', 'petal-length', 'petal-width', 'Class']Bây giờ, chúng ta cần đọc tập dữ liệu thành khung dữ liệu gấu trúc như sau:
dataset = pd.read_csv(path, names=headernames)
dataset.head()| SI. Không. | lá đài dài | chiều rộng đài hoa | chiều dài cánh hoa | chiều rộng cánh hoa | Lớp học |
|---|---|---|---|---|---|
| 0 | 5.1 | 3.5 | 1,4 | 0,2 | Iris-setosa |
| 1 | 4,9 | 3.0 | 1,4 | 0,2 | Iris-setosa |
| 2 | 4,7 | 3.2 | 1,3 | 0,2 | Iris-setosa |
| 3 | 4,6 | 3.1 | 1,5 | 0,2 | Iris-setosa |
| 4 | 5.0 | 3.6 | 1,4 | 0,2 | Iris-setosa |
Quá trình tiền xử lý dữ liệu sẽ được thực hiện với sự trợ giúp của các dòng tập lệnh sau:
X = dataset.iloc[:, :-1].values
y = dataset.iloc[:, 4].valuesTiếp theo, chúng tôi sẽ chia dữ liệu thành phân chia huấn luyện và thử nghiệm. Đoạn mã sau sẽ chia tập dữ liệu thành 60% dữ liệu đào tạo và 40% dữ liệu kiểm tra -
from sklearn.model_selection import train_test_split
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.40)Tiếp theo, việc chia tỷ lệ dữ liệu sẽ được thực hiện như sau:
from sklearn.preprocessing import StandardScaler
scaler = StandardScaler()
scaler.fit(X_train)
X_train = scaler.transform(X_train)
X_test = scaler.transform(X_test)Tiếp theo, đào tạo mô hình với sự trợ giúp của lớp KNeighborsClassifier của sklearn như sau:
from sklearn.neighbors import KNeighborsClassifier
classifier = KNeighborsClassifier(n_neighbors=8)
classifier.fit(X_train, y_train)Cuối cùng, chúng ta cần phải dự đoán. Nó có thể được thực hiện với sự trợ giúp của tập lệnh sau:
y_pred = classifier.predict(X_test)Tiếp theo, in kết quả như sau:
from sklearn.metrics import classification_report, confusion_matrix, accuracy_score
result = confusion_matrix(y_test, y_pred)
print("Confusion Matrix:")
print(result)
result1 = classification_report(y_test, y_pred)
print("Classification Report:",)
print (result1)
result2 = accuracy_score(y_test,y_pred)
print("Accuracy:",result2)Đầu ra
Confusion Matrix:
[[21 0 0]
[ 0 16 0]
[ 0 7 16]]
Classification Report:
precision recall f1-score support
Iris-setosa 1.00 1.00 1.00 21
Iris-versicolor 0.70 1.00 0.82 16
Iris-virginica 1.00 0.70 0.82 23
micro avg 0.88 0.88 0.88 60
macro avg 0.90 0.90 0.88 60
weighted avg 0.92 0.88 0.88 60
Accuracy: 0.8833333333333333KNN làm Regressor
Đầu tiên, hãy bắt đầu với việc nhập các gói Python cần thiết -
import numpy as np
import pandas as pdTiếp theo, tải xuống tập dữ liệu mống mắt từ liên kết web của nó như sau:
path = "https://archive.ics.uci.edu/ml/machine-learning-databases/iris/iris.data"Tiếp theo, chúng ta cần gán tên cột cho tập dữ liệu như sau:
headernames = ['sepal-length', 'sepal-width', 'petal-length', 'petal-width', 'Class']Bây giờ, chúng ta cần đọc tập dữ liệu thành khung dữ liệu gấu trúc như sau:
data = pd.read_csv(url, names=headernames)
array = data.values
X = array[:,:2]
Y = array[:,2]
data.shape
output:(150, 5)Tiếp theo, nhập KNeighborsRegressor từ sklearn để phù hợp với mô hình -
from sklearn.neighbors import KNeighborsRegressor
knnr = KNeighborsRegressor(n_neighbors=10)
knnr.fit(X, y)Cuối cùng, chúng ta có thể tìm thấy MSE như sau:
print ("The MSE is:",format(np.power(y-knnr.predict(X),2).mean()))Đầu ra
The MSE is: 0.12226666666666669Ưu và nhược điểm của KNN
Ưu điểm
Nó là một thuật toán rất đơn giản để hiểu và giải thích.
Nó rất hữu ích cho dữ liệu phi tuyến vì không có giả định về dữ liệu trong thuật toán này.
Nó là một thuật toán linh hoạt vì chúng ta có thể sử dụng nó để phân loại cũng như hồi quy.
Nó có độ chính xác tương đối cao nhưng có nhiều mô hình học có giám sát tốt hơn KNN.
Nhược điểm
Về mặt tính toán, nó là một thuật toán hơi tốn kém vì nó lưu trữ tất cả các dữ liệu huấn luyện.
Yêu cầu bộ nhớ lưu trữ cao so với các thuật toán học có giám sát khác.
Dự đoán chậm trong trường hợp N lớn.
Nó rất nhạy cảm với quy mô dữ liệu cũng như các tính năng không liên quan.
Các ứng dụng của KNN
Sau đây là một số lĩnh vực mà KNN có thể được áp dụng thành công -
Hệ thống ngân hàng
KNN có thể được sử dụng trong hệ thống ngân hàng để dự đoán thời tiết một cá nhân có phù hợp để phê duyệt khoản vay không? Cá nhân đó có các đặc điểm giống với cá nhân mặc định không?
Tính toán xếp hạng tín dụng
Các thuật toán KNN có thể được sử dụng để tìm xếp hạng tín dụng của một cá nhân bằng cách so sánh với những người có đặc điểm tương tự.
Chính trị
Với sự trợ giúp của các thuật toán KNN, chúng tôi có thể phân loại cử tri tiềm năng thành nhiều lớp khác nhau như “Sẽ bỏ phiếu”, “Sẽ không bỏ phiếu”, “Sẽ bỏ phiếu cho Đảng 'Đại hội',“ Sẽ bỏ phiếu cho Đảng 'BJP'.
Các lĩnh vực khác mà thuật toán KNN có thể được sử dụng là Nhận dạng giọng nói, Phát hiện chữ viết tay, Nhận dạng hình ảnh và Nhận dạng video.