Vấn đề sau xuất hiện dưới dạng một bài tập trong khóa học Coursera Algorithm-I của Giáo sư. Robert Sedgewick từ Đại học Princeton vài năm trước [và cũng trong khóa học cos226 được cung cấp tại Princeton]. Định nghĩa vấn đề và mô tả được lấy từ trang web khóa học và bài giảng. Nhiệm vụ ban đầu được thực hiện bằng java, trong bài viết này cả cách triển khai java và cách triển khai python tương ứng cũng sẽ được mô tả
- Sử dụng cây 2d để hỗ trợ
- tìm kiếm phạm vi hiệu quả [tìm tất cả các điểm có trong hình chữ nhật truy vấn]
- tìm kiếm lân cận gần nhất [tìm một điểm gần nhất với một điểm truy vấn]
Cây 2d có nhiều ứng dụng, từ phân loại các vật thể thiên văn đến hoạt hình máy tính đến tăng tốc mạng thần kinh đến khai thác dữ liệu đến truy xuất hình ảnh. Hình bên dưới mô tả vấn đề
triển khai cây 2d. Cây 2d là dạng khái quát hóa của BST thành khóa hai chiều. Ý tưởng là xây dựng một BST với các điểm trong các nút, sử dụng tọa độ x– và y của các điểm làm khóa theo trình tự xen kẽ nghiêm ngặt, bắt đầu bằng tọa độ x, như thể hiện trong hình tiếp theo
- Tìm kiếm và chèn. Thuật toán tìm kiếm và chèn tương tự như thuật toán dành cho BST, nhưng ở gốc, chúng tôi sử dụng tọa độ x [nếu điểm được chèn có tọa độ x nhỏ hơn điểm ở gốc, hãy chuyển sang trái; nếu không, hãy chuyển sang phải]
- Ưu điểm chính của cây 2d so với BST là nó hỗ trợ triển khai hiệu quả tìm kiếm phạm vi và tìm kiếm lân cận gần nhất. Mỗi nút tương ứng với một hình chữ nhật được căn chỉnh theo trục, bao quanh tất cả các điểm trong cây con của nó. Căn tương ứng với toàn bộ mặt phẳng [[−∞, −∞], [+∞, +∞ ]];
- phạm vi tìm kiếm. Để tìm tất cả các điểm có trong một hình chữ nhật truy vấn nhất định, hãy bắt đầu từ gốc và tìm kiếm đệ quy các điểm trong cả hai cây con bằng cách sử dụng quy tắc cắt tỉa sau. nếu hình chữ nhật truy vấn không cắt hình chữ nhật tương ứng với một nút, thì không cần khám phá nút đó [hoặc các cây con của nó]. Nghĩa là, chỉ tìm kiếm một cây con nếu nó có thể chứa một điểm nằm trong hình chữ nhật truy vấn
- Tìm kiếm hàng xóm gần nhất. Để tìm điểm gần nhất với điểm truy vấn nhất định, hãy bắt đầu từ gốc và tìm kiếm đệ quy trong cả hai cây con bằng cách sử dụng quy tắc cắt tỉa sau. nếu điểm gần nhất được phát hiện cho đến nay gần hơn khoảng cách giữa điểm truy vấn và hình chữ nhật tương ứng với một nút, thì không cần khám phá nút đó [hoặc các cây con của nó]. Nghĩa là, chỉ tìm kiếm một nút nếu nó có thể chứa một điểm gần hơn điểm tốt nhất được tìm thấy cho đến nay. Hiệu quả của quy tắc cắt xén phụ thuộc vào việc nhanh chóng tìm ra một điểm gần đó. Để thực hiện việc này, hãy tổ chức phương pháp đệ quy sao cho khi có hai cây con có thể đi xuống, trước tiên, bạn chọn cây con nằm ở cùng phía của đường phân tách làm điểm truy vấn;
- k-tìm kiếm hàng xóm gần nhất. Phương thức này trả về k điểm gần điểm truy vấn nhất [theo bất kỳ thứ tự nào]; . Nó phải làm điều này một cách hiệu quả, tôi. e. sử dụng kỹ thuật từ tìm kiếm hàng xóm gần nhất trên cây kd, không phải từ lực lượng vũ phu
- BoidTrình mô phỏng. Sau khi Tìm kiếm k-láng giềng gần nhất, chúng ta có thể mô phỏng các boid. làm thế nào một đàn chim bay cùng nhau và một con diều hâu. Kìa sự hùng vĩ đổ xô của họ. Các hình dưới đây cho thấy lý thuyết sẽ được sử dụng, được lấy từ các slide bài giảng của cùng một khóa học
Kết quả
Các số liệu và hoạt ảnh sau đây cho thấy cách cây 2 chiều được phát triển với phân vùng không gian đệ quy đối với một số tập dữ liệu mẫu
- Bộ dữ liệu Circle 10
- Bộ dữ liệu Circle 100
Hình dưới đây cho thấy kết quả của thuật toán tìm kiếm phạm vi trên cùng một tập dữ liệu sau khi cây 2d được phát triển. Các điểm màu vàng là các điểm được thuật toán tìm thấy bên trong hình chữ nhật truy vấn được hiển thị
Hoạt ảnh tiếp theo hiển thị thuật toán tìm kiếm hàng xóm gần nhất cho một điểm truy vấn nhất định [điểm trắng cố định có viền đen. điểm [0. 3, 0. 9]] và cách các nhánh được duyệt qua và các điểm [nút] được truy cập trong cây 2 chiều cho đến khi tìm thấy hàng xóm gần nhất
Hình ảnh động tiếp theo cho biết cách duyệt cây kd cho tìm kiếm lân cận gần nhất cho một điểm truy vấn khác [0. 04, 0. 7]
Các số liệu tiếp theo cho thấy kết quả của tìm kiếm k-láng giềng gần nhất, bằng cách mở rộng thuật toán trước đó với các giá trị khác nhau của k [tương ứng là 15, 10, 5]
Thời gian chạy của các thuật toán với một vài bộ dữ liệu trong Python
Như có thể thấy từ hình tiếp theo, độ phức tạp về thời gian của việc xây dựng cây 2 chiều [chèn], tìm kiếm hàng xóm gần nhất và truy vấn k hàng xóm gần nhất không chỉ phụ thuộc vào kích thước của tập dữ liệu mà còn phụ thuộc vào hình học của tập dữ liệu
Các ứng dụng
mô phỏng Boids đổ xô
Trình giả lập bầy đàn boids được triển khai với cây 2 chiều và 2 hình ảnh động sau [java và trăn tương ứng] cho thấy cách đàn chim bay cùng nhau, những con màu đen/trắng là những con boids và màu đỏ là diều hâu săn mồi
Triển khai Trình phân loại kNN với cây kd từ đầu
giai đoạn đào tạo
Xây dựng cây 2d từ tập dữ liệu huấn luyện 2D được gắn nhãn [các điểm được đánh dấu màu đỏ hoặc xanh dương đại diện cho 2 nhãn lớp khác nhau]
Giai đoạn thử nghiệm
- Đối với điểm truy vấn [điểm kiểm tra mới với nhãn lớp không xác định] chạy k-tìm kiếm hàng xóm gần nhất trên cây 2d với điểm truy vấn [với giá trị cố định là k, e. g. , 3]
- Lấy biểu quyết đa số về nhãn lớp của k-láng giềng gần nhất [với nhãn lớp đã biết] thu được bằng cách truy vấn cây 2d. Gắn nhãn điểm truy vấn bằng nhãn lớp mà đa số các điểm truy vấn có
- Lặp lại cho các giá trị khác nhau của k
Các số liệu sau đây cho thấy cách sử dụng cây kd được tạo để phân loại bộ dữ liệu 2D [được tạo ngẫu nhiên] và ranh giới quyết định được học với k=3, 5 và 10 tương ứng