Quy nạp k láng giềng gần nhất (kNN)

Xử lý dữ liệu khuyết bằng Imputation trong R

Michal Oleszak

Machine Learning Engineer

Quy nạp k láng giềng gần nhất (kNN)

Một bảng có ba cột: A, B và C. Có một giá trị thiếu ở cột A.

Quy nạp k láng giềng gần nhất (kNN)

Một bảng có ba cột: A, B và C. Ba hàng không có giá trị thiếu được tô màu.

Với mỗi quan sát có giá trị thiếu:

Tìm k quan sát khác (donor, láng giềng) giống nhất với quan sát đó.

Quy nạp k láng giềng gần nhất (kNN)

Một bảng có ba cột: A, B và C. Ba hàng không có giá trị thiếu được tô màu. Giá trị thiếu trước đó ở A được thay bằng trung bình các số trong cùng cột ở các hàng được tô.

Với mỗi quan sát có giá trị thiếu:

Tìm k quan sát khác (donor, láng giềng) giống nhất với quan sát đó.
Thay giá trị thiếu bằng giá trị tổng hợp từ k donor (trung bình, trung vị, mode).

Thước đo khoảng cách

Khoảng cách giữa hai quan sát a và b:

Khoảng cách Euclid cho n biến số:

$\sqrt{\Sigma_{i=1}^{n} (a_i - b_i)^{2}}$

Khoảng cách Manhattan cho f biến factor:

$\Sigma_{i=1}^{f} |a_i - b_i|$

Khoảng cách Hamming cho c biến phân loại:

$\Sigma_{i=1}^{c} I(a_i \neq b_i)$

Một hệ trục tọa độ với hai điểm nối bằng một đoạn thẳng.

Một hệ trục tọa độ với hai điểm nối bằng hai đoạn vuông góc, như hai góc đối diện của hình chữ nhật.

Khoảng cách Gower

Một khung dữ liệu giả có ba loại biến, mỗi loại tô màu khác nhau: số, định tính (factor) và phân loại (categorical).

Khoảng cách Gower

Một khung dữ liệu giả có ba loại biến, mỗi loại tô màu khác nhau: số, định tính (factor) và phân loại (categorical). Mỗi loại biến có một mũi tên chỉ tới thước đo khoảng cách tương ứng: Euclid, Manhattan và Hamming. Ba thước đo này cùng trỏ tới một ellipse “khoảng cách Gower”, là sự kết hợp của cả ba.

Thực hành quy nạp kNN

library(VIM)
nhanes_imp <- kNN(nhanes, k = 5, variable = c("TotChol", "Pulse"))

head(nhanes_imp)

  Age Gender Weight Height Diabetes TotChol Pulse PhysActive TotChol_imp Pulse_imp
1  16   male   73.2  172.0    FALSE    3.00    76       TRUE       FALSE     FALSE
2  17   male   72.3  176.0    FALSE    2.61    74       TRUE       FALSE     FALSE
3  12   male   57.7  158.9    FALSE    4.27    80       TRUE       FALSE     FALSE
4  16   male   88.9  183.3    FALSE    3.62    58       TRUE       FALSE     FALSE
5  13 female   45.1  157.6    FALSE    2.66    92       TRUE       FALSE     FALSE
6  16 female   48.7  158.4    FALSE    4.32    58      FALSE       FALSE     FALSE

Gán trọng số cho donor

Trong số k láng giềng đã chọn cho một quan sát, có láng giềng giống hơn.
Khi tổng hợp giá trị, nên tăng trọng số cho láng giềng gần hơn.
Tổng hợp láng giềng bằng trung bình có trọng số, với trọng số là nghịch đảo khoảng cách tới từng láng giềng.
Chỉ áp dụng khi quy nạp biến số.

nhanes_imp <- nhanes %>% 
  kNN(variable = c("TotChol", "Pulse"),
      k = 5,
      numFun = weighted.mean,
      weightDist = TRUE)

Sắp xếp biến

Thuật toán kNN lặp qua các biến và quy nạp lần lượt.
Mỗi lần đều tính khoảng cách giữa các quan sát.
Nếu biến đầu có nhiều giá trị thiếu, thì khi tính khoảng cách cho biến thứ hai sẽ dựa trên nhiều giá trị đã quy nạp.
Nên sắp xếp biến tăng dần theo số lượng giá trị thiếu trước khi chạy kNN.

Thực hành sắp xếp biến

vars_by_NAs <- nhanes %>% 
  is.na() %>%
  colSums() %>%
  sort(decreasing = FALSE) %>% 
  names()

nhanes_imp <- nhanes %>% 
  select(vars_by_NAs) %>% 
  kNN(k = 5)

Hãy luyện tập quy nạp kNN!

Xử lý dữ liệu khuyết bằng Imputation trong R