Nearest neighbor và region search trên k-d tree

Truy vấn nâng cao trên cây k-d: xóa nút, lân cận gần nhất bằng cắt tỉa siêu cầu, tìm kiếm vùng và bảng tổng kết mọi phương thức.

KhóThuật toán ~60 phút

Ôn lại trước khi học

Ký hiệu Big-O và các lớp tăng trưởng

Giới thiệu

Bài này học xóa nút và tìm lân cận trên k-d tree. Bạn dùng nó để tìm điểm gần nhất và điểm trong vùng.

Kiến thức cần nhớ

Xóa nút

Xóa lá thì gỡ thẳng là xong.
Xóa nút trong phải tìm vật thay thế giữ đúng chiều chia.
Vật thay thế có thể nằm sâu ở nhánh bất kỳ.
Ví dụ đời thường: như rút 1 quản lý giữa, phải tìm người hợp đúng chuyên môn thay vào.

Lân cận gần nhất

Đi xuống như tìm điểm để có ứng viên tốt ngay.
Khi quay lui, kiểm tra quả cầu quanh điểm hỏi có cắt mặt chia không.
Không cắt thì cắt cả nhánh bên kia cho nhanh.
Ví dụ đời thường: như tìm quán gần nhất, xa hơn quán đã thấy thì bỏ cả khu đó.

# Ý tưởng cắt tỉa lân cận
# best = ứng viên tốt nhất hiện tại
# nếu khoảng_cách(tới mặt chia) > best: bỏ cả nhánh bên kia

Tìm kiếm vùng

Cho hình chữ nhật, trả về mọi điểm nằm trong.
Mỗi nút nhớ hộp bao của cây con mình.
Hộp nằm gọn trong truy vấn thì lấy cả cây con.
Hộp rời hẳn truy vấn thì cắt cả cây con.

Độ phức tạp và giới hạn

Trung bình logarit nhờ cắt tỉa tốt.
Xấu nhất tuyến tính khi quả cầu nuốt cả cây.
Chiều càng cao càng khó cắt nhánh.
Dữ liệu động ghi nhiều thì nên tái xây định kỳ.

Ví dụ

Input: hỏi lân cận của điểm đã có trong cây. Output: chính nó, khoảng cách 0.
Giải thích: không điểm nào gần hơn chính mình.
Input: vùng bao toàn bộ dữ liệu. Output: trả về đúng n điểm.
Giải thích: mọi hộp đều giao nên phải thăm hết.

💻 Bài tập

Ngôn ngữ: C++. Dùng tiếp KDTree<K> ngày 45. Nộp vào day-069/.

Bài 1: Nearest neighbor và k-NN

Hàm	Yêu cầu
`Point nearest(const Point &q) const`	Đi xuống trước, quay lui, cắt nhánh khi $(q[axis] - p[axis])^2 \ge best^2$
`std::vector<Point> kNearest(const Point &q, int k) const`	Max-heap cỡ `k`, cắt nhánh theo khoảng cách lớn nhất trong heap
`int lastVisited`	Số nút đã thăm ở truy vấn gần nhất

7 điểm ngày 45, q=(9,2)       -> nearest (8,1)
kNearest((5,5), 3)            -> (6,5), (5,4), (4,7)   (sắp theo khoảng cách)
k > n                         -> trả hết n điểm

Kiểm tra với 10.000 truy vấn ngẫu nhiên: kết quả khớp quét tuyến tính.

bool remove(const Point &p): nút lá gỡ thẳng. Nút trong chia theo trục a: tìm điểm có tọa độ a nhỏ nhất trong cây con phải, chép lên, xóa đệ quy điểm đó. Nếu không có cây con phải, tìm min trong cây con trái rồi chuyển cây con trái thành cây con phải.

Xóa gốc của cây 7 điểm -> checkInvariant = true, còn 6 điểm
Xóa 50% trong 10^4 điểm ngẫu nhiên -> checkInvariant = true, nearest vẫn khớp quét tuyến tính

Bài 3: Lời nguyền số chiều (nâng cao)

Với K = 2, 4, 8, 16, 32, dựng cây từ $10^5$ điểm ngẫu nhiên đều. Chạy 1000 truy vấn nearest.

K     avg_visited    tỉ_lệ_thăm (/n)    tốc_độ_so_với_quét
2     ...
32    ...

Vẽ avg_visited theo K. Viết 3 câu giải thích vì sao ở chiều cao k-d tree gần như phải thăm hết cây.

✅ Tiêu chí hoàn thành

nearest và kNearest khớp quét tuyến tính trên 10.000 truy vấn.
remove giữ bất biến sau 5000 lần xóa.
Bảng Bài 3 có số thật và hình vẽ.
Giải thích được điều kiện cắt nhánh bằng hình vẽ tay.

❓ Câu hỏi ôn tập

Xóa nút trong k-d tree khó ở đâu?
Cắt tỉa lân cận dựa vào gì?
Tìm kiếm vùng cắt nhánh thế nào?
Khi nào k-d tree suy biến thành duyệt hết?

🌕 Bạn đã hoàn thành ngày 69. Làm hết bài tập phía trên rồi sang ngày tiếp theo.

Ngày 68

Kết hợp Iterator và Composite duyệt cây đệ quy

Ngày 70

Bài toán nearest neighbor và R-tree indexing