Bỏ qua đến nội dung chính
Mục lục

Khoảng cách Euclid, Manhattan và vì sao scale đổi hàng xóm

AIDev Team · duyệt: Nguyễn Việt Chung

Bài 4/8 · Chương 12

Toán vừa đủ cho Machine Learning

  • 8 phút
  • Trung cấp
  • Python 3.14
  • Cập nhật

Khoảng cách Euclid giữa hai hội viên được tính như sau: lấy hiệu ở mỗi cột, bình phương, cộng lại rồi lấy căn. Khoảng cách Manhattan thì cộng thẳng trị tuyệt đối các hiệu đó. KNN dựa trọn vào con số này để chọn hàng xóm, nên một cột tính bằng phút có thể lấn át mọi cột khác khi bảng chưa được scale.

Cần biết trước: KNN và StandardScaler.

Công thức và tính tay cho hai hội viên

Mỗi hội viên Sóc Vàng là một điểm có hai tọa độ: số lần mở app trong tuần và số phút dùng app trong tuần. Hội viên P mở app 14 lần, dùng 250 phút. Hội viên Q mở 9 lần, dùng 262 phút. Khoảng cách Euclid giữa hai điểm u và v là:

d(u,v)=∑j=1m(uj−vj)2d(u, v) = \sqrt{\sum_{j=1}^{m} (u_j - v_j)^2}

Trong đó:

  • u, v (p, q): hai hội viên, mỗi người là một mảng m số.

  • m (len(p)): số cột, ở đây là 2.

  • u với chỉ số j (p[j]): giá trị cột thứ j của hội viên thứ nhất.

  • d (np.linalg.norm(p - q)): khoảng cách Euclid.

Khoảng cách Manhattan bỏ bình phương và căn: cộng thẳng trị tuyệt đối các chênh lệch.

Bước

Việc

Kết quả

1

Chênh lệch từng cột

14 − 9 = 5; 250 − 262 = −12

2

Bình phương

25; 144

3

Euclid: √(25 + 144)

√169 = 13

4

Manhattan: 5 + 12

17

python
import numpy as np

p = np.array([14, 250])
q = np.array([9, 262])
print("Euclid:", np.linalg.norm(p - q))
print("Manhattan:", np.abs(p - q).sum())
print("ord=1:", np.linalg.norm(p - q, ord=1))

KẾT QUẢ

Euclid: 13.0
Manhattan: 17
ord=1: 17.0

np.linalg.norm(v) tính độ dài Euclid của vector v. Thêm ord=1 thì nó tính tổng trị tuyệt đối, tức Manhattan. Manhattan không nhỏ hơn Euclid: hai số bằng nhau chỉ khi hai điểm khác nhau ở nhiều nhất một cột. Đổi q = np.array([9, 262]) thành q = np.array([14, 262]) rồi chạy lại: ba dòng in 12.0, 12 và 12.0.

Khoảng cách tới cả bảng bằng broadcasting

KNN cần khoảng cách từ một hội viên mới tới từng dòng của bảng. X - moi trừ điểm mới khỏi mọi dòng nhờ broadcasting, rồi axis=1 bảo norm tính độ dài theo từng dòng:

python
import numpy as np

X = np.array([[6, 310], [19, 360], [4, 90],
              [25, 120], [12, 540], [22, 380]])
moi = np.array([20, 300])
d = np.linalg.norm(X - moi, axis=1)
print((X - moi).shape)
print(d.round(1))
print("thứ tự gần tới xa:", np.argsort(d))

KẾT QUẢ

(6, 2)
[ 17.2  60.  210.6 180.1 240.1  80. ]
thứ tự gần tới xa: [0 1 5 3 2 4]

np.argsort(d) cho chỉ số dòng xếp theo khoảng cách tăng dần, như bài argsort. Hội viên mới mở app 20 lần, dùng 300 phút. Hàng xóm gần nhất là dòng 0, người chỉ mở app 6 lần nhưng dùng 310 phút. Dòng 1 mở 19 lần, dùng 360 phút, giống hơn hẳn về nhịp mở app, lại đứng thứ hai vì chênh 60 phút.

Vì sao scale đổi hàng xóm gần nhất

Ở dòng 1, chênh lệch hai cột là 1 lần mở và 60 phút, bình phương ra 1 và 3.600. Ở dòng 0 là 14 lần mở và 10 phút, bình phương ra 196 và 100. Cột phút dao động hàng trăm, cột lần mở chỉ vài chục, nên phút gần như một mình quyết định thứ tự. Phép thử rõ nhất: giữ nguyên sáu người, chỉ ghi cột thời gian bằng giờ thay cho phút:

python
import numpy as np

X = np.array([[6, 310], [19, 360], [4, 90],
              [25, 120], [12, 540], [22, 380]])
moi = np.array([20, 300])
doi_gio = np.array([1, 1 / 60])
d_gio = np.linalg.norm(X * doi_gio - moi * doi_gio, axis=1)
print(d_gio.round(2))
print("thứ tự gần tới xa:", np.argsort(d_gio))

KẾT QUẢ

[14.    1.41 16.38  5.83  8.94  2.4 ]
thứ tự gần tới xa: [1 5 3 4 0 2]

Không ai đổi thói quen, chỉ đơn vị đổi, vậy mà dòng 1 lên đầu và dòng 0 tụt xuống thứ năm. Khi chưa scale, hàng xóm gần nhất phụ thuộc vào một lựa chọn tùy ý của người ghi dữ liệu. StandardScaler trừ mỗi cột cho trung bình của nó rồi chia cho độ lệch chuẩn của chính cột đó, nên đơn vị bị triệt tiêu. Khối dưới chạy cùng phép đo cho bảng ghi bằng phút và bảng ghi bằng giờ:

python
import numpy as np
from sklearn.preprocessing import StandardScaler

X = np.array([[6, 310], [19, 360], [4, 90],
              [25, 120], [12, 540], [22, 380]])
moi = np.array([[20, 300]])
print("độ lệch chuẩn:", X.std(axis=0, ddof=0).round(1))
for ten, he_so in [("phút", 1), ("giờ", 1 / 60)]:
    X_dv, moi_dv = X * [1, he_so], moi * [1, he_so]
    scaler = StandardScaler().fit(X_dv)
    d = np.linalg.norm(scaler.transform(X_dv) - scaler.transform(moi_dv), axis=1)
    print(ten, d.round(2), np.argsort(d))

KẾT QUẢ

độ lệch chuẩn: [  7.9 155. ]
phút [1.77 0.41 2.43 1.32 1.85 0.57] [1 5 3 0 4 2]
giờ [1.77 0.41 2.43 1.32 1.85 0.57] [1 5 3 0 4 2]

Hai dòng in trùng nhau từng số. Độ lệch chuẩn của cột phút gần gấp 20 lần cột lần mở. Sau khi chia, 14 lần mở chênh lệch ở dòng 0 thành gần 1,8 lần độ lệch chuẩn, còn 10 phút chỉ còn khoảng 0,06. Dòng 1 đứng đầu, dòng 0 xuống thứ tư. Điểm mới đi qua cùng scaler đã học từ sáu dòng của bảng.

Với KNN một hàng xóm, đổi hàng xóm là đổi dự đoán. Ba hội viên đầu bảng hủy gói (1), ba hội viên còn lại ở lại (0):

python
import numpy as np
from sklearn.neighbors import KNeighborsClassifier
from sklearn.pipeline import make_pipeline
from sklearn.preprocessing import StandardScaler

X = np.array([[6, 310], [19, 360], [4, 90],
              [25, 120], [12, 540], [22, 380]])
huy = np.array([1, 0, 1, 0, 1, 0])
moi = np.array([[20, 300]])
tho = KNeighborsClassifier(n_neighbors=1).fit(X, huy)
knn = KNeighborsClassifier(n_neighbors=1)
co_scale = make_pipeline(StandardScaler(), knn).fit(X, huy)
print("chưa scale:", tho.predict(moi))
print("hàng xóm:", tho.kneighbors(moi)[1])
print("có scale:", co_scale.predict(moi))

KẾT QUẢ

chưa scale: [1]
hàng xóm: [[0]]
có scale: [0]

Nhãn ở đây tự đặt cho dễ theo dõi. Điều cần nhớ là cơ chế: kneighbors() cho thấy model chưa scale chọn dòng 0, nên đoán hủy.

Kiểm tra nhanh

  1. Sau import numpy as np, print(np.linalg.norm(np.array([2, 9]) - np.array([8, 1]))) in ra gì?

    • 10.0
    • 14.0
    • 100.0
  2. Trong bảng sáu hội viên chưa scale, vì sao dòng 0 (6 lần mở, 310 phút) là hàng xóm gần nhất của hội viên 20 lần mở, 300 phút?

    • Cột phút có thang lớn nên quyết định khoảng cách: dòng 0 chỉ lệch 10 phút, dòng 1 lệch 60 phút
    • Cột số đơn có trọng số lớn hơn trong khoảng cách Euclid
    • Euclid chỉ nhìn cột cuối của bảng
  3. Những câu nào đúng về khoảng cách Euclid và Manhattan?

    • Manhattan không bao giờ nhỏ hơn Euclid
    • np.linalg.norm(v, ord=1) cho khoảng cách Manhattan khi v là hiệu hai điểm
    • Chuẩn hóa cột không đổi thứ tự hàng xóm
    • Hai điểm khác nhau ở hai cột thì Euclid bằng Manhattan
  4. Trong khung bẫy, vì sao np.argsort(d) in [0]?

    • Vì dòng 0 thật sự là hàng xóm gần nhất
    • Vì thiếu axis=1, d chỉ còn một số cho cả bảng
    • Vì argsort() chỉ trả phần tử nhỏ nhất
Đúng hết lần đầu +15 XP

Bài tập

Tìm hàng xóm gần nhất, có và không chuẩn hóa

X là mảng hai chiều, mỗi dòng một hội viên. diem là mảng một chiều, cùng số cột với X. chuan_hoa là True hay False.

Viết thân hàm gan_nhat(X, diem, chuan_hoa). Khi chuan_hoa là True, trừ trung bình rồi chia cho độ lệch chuẩn của từng cột của X (ddof=0), áp cho cả X lẫn diem. Sau đó tính khoảng cách Euclid từ diem tới từng dòng. Không dùng KNeighborsClassifier, KNeighborsRegressor hay NearestNeighbors.

Hàm không sửa X, diem của nơi gọi.

Trả về: chỉ số dòng gần nhất, một int.

Ví dụ: với bảng sáu hội viên và diem là np.array([20, 300]), hàm trả về 0 khi chuan_hoa=False và 1 khi chuan_hoa=True.

python
import numpy as np

def gan_nhat(X, diem, chuan_hoa):
    pass  # Viết thân hàm thay cho dòng này

Tóm tắt

  • Euclid: bình phương hiệu từng cột, cộng, lấy căn. Manhattan: cộng trị tuyệt đối các hiệu.

  • np.linalg.norm(v) cho Euclid, thêm ord=1 cho Manhattan.

  • Khoảng cách tới cả bảng: np.linalg.norm(X - moi, axis=1), rồi np.argsort() để xếp hàng xóm.

  • Cột có thang đo lớn lấn át khoảng cách: chưa scale thì chỉ đổi phút sang giờ cũng đổi hàng xóm.

  • Chuẩn hóa theo số liệu của bảng triệt tiêu đơn vị, đổi thứ tự hàng xóm, và có thể đổi dự đoán của KNN.

  • Quên axis=1 thì norm trả một số cho cả bảng mà không báo lỗi.

Câu hỏi thường gặp

Công thức khoảng cách Euclid giữa hai điểm là gì?

Lấy chênh lệch ở từng cột, bình phương, cộng lại rồi lấy căn bậc hai. Với hai cột, đó chính là định lý Pythago. Trong NumPy, np.linalg.norm(a - b) tính đúng công thức đó cho bất kỳ số cột nào.

Khi nào dùng khoảng cách Manhattan thay cho Euclid?

Manhattan ít bị một chênh lệch rất lớn ở một cột chi phối hơn, vì không bình phương. KNeighborsClassifier(metric="manhattan") dùng nó. Nên thử cả hai bằng cross validation, vì không cách nào thắng trên mọi bảng.

Có cần scale dữ liệu cho mọi model dùng khoảng cách?

Có, với KNN, K-means, SVM kernel RBF: mọi model đo khoảng cách giữa các dòng đều bị cột thang đo lớn lấn át. Đặt scaler trong pipeline để nó chỉ học từ tập train. Bài chọn scaler so StandardScaler với MinMaxScaler và RobustScaler.

Cây quyết định có bị ảnh hưởng bởi scale không?

Không. Cây chia theo ngưỡng trên từng cột một, nên nhân cả cột với một số dương chỉ dời ngưỡng theo, thứ tự các dòng không đổi. Đó là lý do decision tree và random forest không cần StandardScaler.

Chủ đề

khoảng cách euclid

Bài này có hữu ích?

Hỏi đáp

Đang tải câu hỏi…

Tham vấn chuyên môn

Nguyễn Việt Chung

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.
Biên soạn: AIDev Team · Rà soát · Quy trình biên tập