Thuật toán k-lân cận gần nhất (k-NN) là một phương pháp đơn giản nhưng hiệu quả trong xử lý dữ liệu. Dưới đây là cách triển khai thuật toán này để tối ưu hóa hệ thống ghép nối người dùng trên nền tảng hẹn hò trực tuyến.
Triển khai thuật toán k-NN
def phan_loai(input_vector, tap_du_lieu, danh_sach_nhan, k):
so_mau = tap_du_lieu.shape[0]
ma_tran_khoang_cach = tile(input_vector, (so_mau, 1)) - tap_du_lieu
khoang_cach_binh_phuong = ma_tran_khoang_cach ** 2
tong_khoang_cach = khoang_cach_binh_phuong.sum(axis=1)
khoang_cach = sqrt(tong_khoang_cach)
chi_so_sap_xep = argsort(khoang_cach)
dem_nhan = {}
for i in range(k):
nhan_hien_tai = danh_sach_nhan[chi_so_sap_xep[i]]
dem_nhan[nhan_hien_tai] = dem_nhan.get(nhan_hien_tai, 0) + 1
danh_sach_nhan_sap_xep = sorted(dem_nhan.items(), key=lambda x: x[1], reverse=True)
return danh_sach_nhan_sap_xep[0][0]
Xử lý dữ liệu đầu vào
def doc_du_lieu(ten_tap_tin):
file = open(ten_tap_tin)
so_dong = len(file.readlines())
ma_tran_du_lieu = zeros((so_dong, 3))
danh_sach_nhan = []
file.seek(0)
for i in range(so_dong):
dong = file.readline().strip()
gia_tri = dong.split('\t')
ma_tran_du_lieu[i] = gia_tri[:3]
danh_sach_nhan.append(int(gia_tri[-1]))
return ma_tran_du_lieu, danh_sach_nhan
Chuẩn hóa dữ liệu
def chuan_hoa_du_lieu(tap_du_lieu):
gia_tri_min = tap_du_lieu.min(0)
gia_tri_max = tap_du_lieu.max(0)
khoang_cach = gia_tri_max - gia_tri_min
tap_du_lieu_chuan = (tap_du_lieu - tile(gia_tri_min, (tap_du_lieu.shape[0], 1))) / tile(khoang_cach, (tap_du_lieu.shape[0], 1))
return tap_du_lieu_chuan, khoang_cach, gia_tri_min
Kiểm tra độ chính xác
def kiem_tra_hoat_dong():
ti_le_kiem_tra = 0.5
du_lieu, nhan = doc_du_lieu('tap_du_lieu_thu_vien.txt')
du_lieu_chuan, _, _ = chuan_hoa_du_lieu(du_lieu)
so_mau = du_lieu_chuan.shape[0]
so_mau_kiem_tra = int(so_mau * ti_le_kiem_tra)
so_loi = 0
for i in range(so_mau_kiem_tra):
ket_qua = phan_loai(du_lieu_chuan[i],
du_lieu_chuan[so_mau_kiem_tra:],
nhan[so_mau_kiem_tra:], 3)
if ket_qua != nhan[i]:
so_loi += 1
print(f"Tỷ lệ lỗi: {so_loi/so_mau_kiem_tra:.2%}")
print(f"Số lỗi: {so_loi}")