KNN (k nearest neighbors): chọn K bằng cross validation
Bài 5/11 · Chương 5
Phân loại: logistic regression, KNN, SVM, Naive Bayes
- 8 phút
- Cơ bản
- Python 3.14
- Cập nhật
Trong bài này · 11
KNN (k nearest neighbors, k hàng xóm gần nhất) đoán nhãn của một dòng mới bằng cách tìm K dòng train gần nó nhất theo khoảng cách, rồi lấy tỉ lệ nhãn của K dòng đó làm xác suất. Trong scikit-learn, KNeighborsClassifier(n_neighbors=K) làm việc này cho bài toán phân loại, KNeighborsRegressor lấy trung bình cho bài toán hồi quy, và K tốt nhất được chọn bằng cross-validation.
Cần biết trước: cross-validation, pipeline và overfitting và underfitting.
KNN là gì: đo khoảng cách rồi đếm phiếu
Với KNN, bước fit() gần như không tính gì: model giữ lại bảng train để tra về sau. Mọi phép tính dồn vào lúc đoán, gồm hai việc:
Trong đó:
là dòng mới, là một dòng train, cả hai có feature;
là khoảng cách Euclid, đường chim bay giữa hai điểm;
là tập K dòng train có nhỏ nhất, là nhãn 0/1 của chúng;
là tỉ lệ nhãn
1trong K hàng xóm, chính làpredict_proba().
Bảy hội viên giả định, mỗi người có số lần đăng nhập trong 30 ngày, số đơn trong 90 ngày và nhãn bỏ gói. Hai cột cùng cỡ số nên đo khoảng cách thẳng được. Một hội viên mới có 4 lần đăng nhập và 2 đơn:
import math
hoi_vien = [(2, 1, 1), (3, 1, 1), (9, 6, 0), (7, 7, 0), (5, 5, 0),
(1, 4, 1), (6, 2, 0)]
moi = (4, 2)
cach = []
for dang_nhap, don, bo_goi in hoi_vien:
d = math.dist(moi, (dang_nhap, don))
cach.append((round(d, 2), bo_goi))
cach.sort()
print(cach)
for k in [1, 3, 7]:
phieu = [nhan for _, nhan in cach[:k]]
print("K =", k, "->", round(sum(phieu) / k, 3))KẾT QUẢ
[(1.41, 1), (2.0, 0), (2.24, 1), (3.16, 0), (3.61, 1), (5.83, 0), (6.4, 0)]
K = 1 -> 1.0
K = 3 -> 0.667
K = 7 -> 0.429Hàng xóm gần nhất cách 1,41 và đã bỏ gói, nên K = 1 cho xác suất 1,0. Ba người gần nhất có hai người bỏ gói: 0,667. Hỏi cả bảy người thì câu trả lời chỉ còn là tỉ lệ chung của bảng, 3/7. Đổi moi = (4, 2) thành moi = (8, 6) rồi chạy lại: dòng K = 3 in 0.0, vì ba người gần nhất đều ở lại.
KNeighborsClassifier làm đúng phép tính đó
Cùng bảy dòng, viết bằng NumPy rồi so với scikit-learn. np.argsort trả vị trí theo thứ tự khoảng cách tăng dần; kneighbors() của model trả vị trí của các hàng xóm nó chọn:
import numpy as np
from sklearn.neighbors import KNeighborsClassifier
X = np.array([[2, 1], [3, 1], [9, 6], [7, 7], [5, 5], [1, 4],
[6, 2]])
y = np.array([1, 1, 0, 0, 0, 1, 0])
moi = np.array([4, 2])
khoang_cach = np.sqrt(((X - moi) ** 2).sum(axis=1))
ba_gan = np.argsort(khoang_cach)[:3]
print(ba_gan, y[ba_gan].mean().round(3))
knn = KNeighborsClassifier(n_neighbors=3).fit(X, y)
print(knn.predict_proba([moi]).round(3), knn.predict([moi]))
print(knn.kneighbors([moi])[1])KẾT QUẢ
[1 6 0] 0.667
[[0.333 0.667]] [1]
[[1 6 0]]Cùng ba hàng xóm, cùng xác suất 0,667. predict() báo 1 vì lớp 1 có nhiều phiếu hơn. Với K lẻ và hai lớp, số phiếu không bao giờ hòa. Mặc định n_neighbors=5; các khoảng cách khác ngoài Euclid nằm ở bài toán khoảng cách.
KNeighborsRegressor dùng cùng cách tìm hàng xóm, nhưng trả trung bình nhãn số của K hàng xóm. Đoán chi tiêu 90 ngày (nghìn đồng) theo số đơn, hỏi 50 hội viên gần nhất:
import pandas as pd
from sklearn.neighbors import KNeighborsRegressor
hv = pd.read_csv("hoi_vien.csv")
X = hv[["so_don_90_ngay"]]
knn = KNeighborsRegressor(n_neighbors=50)
knn.fit(X, hv["chi_tieu_90_ngay_nghin"])
moi = pd.DataFrame({"so_don_90_ngay": [1, 4, 10]})
print(knn.predict(moi).round(0))KẾT QUẢ
[ 314. 1163. 2783.]K nhỏ thì nhiễu, K lớn thì mờ
K = 1 nghe theo đúng một người, nên một hàng xóm có nhãn ngẫu nhiên là đủ đổi câu trả lời: ranh giới giữa hai lớp lởm chởm, đó là overfitting. K rất lớn hỏi gần cả bảng, nên mọi khách nhận xác suất gần tỉ lệ chung và model không còn phân biệt được ai: underfitting. K tốt nằm giữa, và nơi nó nằm tùy dữ liệu.
Chọn K bằng cross-validation
Ví dụ dùng mẫu 600 hội viên và 3 fold, vì KNN đoán chậm khi bảng lớn: mỗi lần đoán phải đo tới mọi dòng train. Scaler đặt trong pipeline để mỗi fold tự chuẩn hóa bằng số liệu của riêng phần train trong fold. Với mỗi K, cross_val_score cho ROC-AUC trung bình của 3 fold:
import matplotlib.pyplot as plt
import pandas as pd
from sklearn.model_selection import cross_val_score
from sklearn.neighbors import KNeighborsClassifier
from sklearn.pipeline import make_pipeline
from sklearn.preprocessing import StandardScaler
hv = pd.read_csv("hoi_vien.csv").sample(600, random_state=0)
X, y = hv.loc[:, "tu_dong_gia_han":"ti_le_dung_ma_giam"], hv.roi_bo
cac_k, auc = [5, 25, 75, 200, 350], []
for k in cac_k:
knn = make_pipeline(StandardScaler(), KNeighborsClassifier(k))
auc.append(cross_val_score(knn, X, y, cv=3, scoring="roc_auc").mean())
plt.semilogx(cac_k, auc, marker="o")
plt.xlabel("K (thang log)"); plt.ylabel("ROC-AUC trung bình 3 fold")
plt.show()ROC-AUC tăng nhanh từ 0,694 ở K = 5, đi gần ngang quanh 0,76 từ K = 25 tới K = 75, đạt đỉnh 0,779 ở K = 200 rồi giảm ở K = 350. Đỉnh đó là của mẫu này. Lặp lại với 200 mẫu 600 hội viên khác: K = 200 cao nhất ở 100 mẫu, K = 75 ở 77 mẫu, K = 350 ở 15 mẫu, và trung bình của K = 75 với K = 200 chỉ cách nhau 0,002. Vậy đừng nhớ một con số K cho "bảng hội viên": để cross-validation chọn trên chính dữ liệu bạn có. Trên dữ liệu thật, chia riêng tập test trước, chọn K bằng cross-validation trên phần train, fit lại pipeline với K đó trên cả phần train, rồi mới chấm một lần trên tập test để báo cáo. Muốn so nhiều K và nhiều tham số một lúc, GridSearchCV làm vòng lặp này thay bạn.
Kiểm tra nhanh
Sau
import math,round(math.dist((4, 2), (7, 6)), 2)cho kết quả gì?7.05.025.0
KNeighborsClassifier(n_neighbors=5)có ba hàng xóm nhãn1và hai hàng xóm nhãn0.predict_proba()trả gì cho lớp1?- 0,6
- 1,0
- 0,5
Những câu nào đúng về KNN trong scikit-learn?
- Phần tính toán dồn vào lúc đoán;
fit()gần như chỉ giữ lại bảng train KNeighborsRegressortrả trung bình nhãn của K hàng xóm- KNN học một hệ số cho mỗi cột như logistic regression
- K càng lớn thì model càng khớp chi tiết của bảng train
- Phần tính toán dồn vào lúc đoán;
Vì sao KNN với K = 1 có accuracy 1,0 trên bảng train?
- Vì K = 1 là K tốt nhất
- Vì mỗi dòng train là hàng xóm gần nhất của chính nó
- Vì scaler làm mọi khoảng cách bằng 0
Bài tập
Tự tính xác suất của KNN
X_tr là mảng NumPy hai chiều các dòng train (mỗi dòng một khách, mỗi cột một feature), y_tr là mảng nhãn 0/1 cùng số dòng, diem là mảng một chiều của khách mới, k là số hàng xóm (1 ≤ k ≤ số dòng). Viết thân hàm ti_le_hang_xom(X_tr, y_tr, diem, k) tìm k dòng train có khoảng cách Euclid tới diem nhỏ nhất và trả tỉ lệ nhãn 1 trong k dòng đó. Không dùng KNeighborsClassifier, KNeighborsRegressor hay NearestNeighbors của scikit-learn. Các bảng chấm không có hai khoảng cách bằng nhau. Hàm không sửa mảng của nơi gọi.
Trả về: tỉ lệ nhãn 1, một float.
Ví dụ: với bảy hội viên ở đầu bài, diem = np.array([4, 2]) và k = 3, kết quả là 0.666….
import numpy as np
def ti_le_hang_xom(X_tr, y_tr, diem, k):
pass # Viết thân hàm thay cho dòng nàyTóm tắt
KNN đo khoảng cách từ dòng mới tới mọi dòng train, lấy K dòng gần nhất và trả tỉ lệ nhãn của chúng.
KNeighborsClassifier(n_neighbors=K)cho phân loại,KNeighborsRegressorlấy trung bình cho hồi quy; phần tính toán nằm ở lúc đoán.K nhỏ thì nhiễu và overfit, K lớn thì kéo mọi khách về tỉ lệ chung.
Chọn K bằng cross-validation, với scaler trong pipeline; đừng chấm KNN trên bảng train.
Câu hỏi thường gặp
Thuật toán KNN có cần scale dữ liệu không?
Cần. Khoảng cách cộng thẳng hiệu của từng cột, nên cột tính bằng nghìn đồng sẽ lấn át cột chỉ từ 0 đến 1. Đặt StandardScaler trong pipeline; bài kế tiếp so các loại scaler khác nhau trên KNN.
Vì sao KNN đoán chậm khi bảng lớn?
Mỗi lần đoán, KNN phải đo khoảng cách tới mọi dòng train, nên thời gian tăng theo số dòng train nhân số dòng cần đoán. scikit-learn dùng cấu trúc cây để bớt phép đo khi số cột ít, nhưng với nhiều cột lợi thế này giảm dần.
K nên chẵn hay lẻ?
Với hai lớp, K lẻ tránh được hòa phiếu ở predict(). Khi hòa, scikit-learn chọn lớp có nhãn nhỏ hơn, nên K lẻ cho kết quả dễ giải thích hơn. Xác suất từ predict_proba() thì không bị ảnh hưởng.
Chủ đề
Dữ liệu của bài
- Tải xuống
hoi_vien.csv
CSV · 207.25 KB
Bài này có hữu ích?
Hỏi đáp
Tham vấn chuyên môn
Nhà sáng lập AIDev và VietPlatform · Thạc sĩ AI MSE
- Tốt nghiệp thủ khoa xuất sắc Thạc sĩ AI MSE.
- Đồng sáng lập, CTO E-University, SVOnline: số hóa 10+ đại học, 40.000+ sinh viên.
- Xây hệ thống AI cho doanh nghiệp tại VietPlatform.