28 tháng 12 năm 2017 - Máy tính
k-d tree (tạm dịch là cây không gian đa chiều) thường được sử dụng để phân chia không gian và tìm kiếm láng giềng gần nhất. Đây là một trường hợp đặc biệt của cây phân chia không gian nhị phân. Thông thường, đối với tập dữ liệu có số chiều k và số điểm dữ liệu là N, k-d tree phù hợp trong trường hợp N ≫ 2^k.
1) Nguyên lý thuật toán k-d tree
k-d tree là một cây nhị phân mà mỗi nút đại diện cho một điểm dữ liệu có k chiều. Mỗi nút trên cây biểu diễn một siêu phẳng mặt cắt, mặt này vuông góc với trục tọa độ của chiều đang được chọn làm tiêu chí phân chia và chia không gian thành hai phần: một phần nằm trong cành trái và một phần nằm trong cành phải. Nếu chiều phân chia hiện tại là d, thì tất cả các điểm con ở phía trái sẽ có giá trị tọa độ nhỏ hơn giá trị của nút hiện tại trên chiều d, và tất cả các điểm con ở phía phải sẽ có giá trị tọa độ lớn hơn hoặc bằng.
Định nghĩa này áp dụng cho mọi nút con của cây.
1.1) Xây dựng cây Một k-d tree cân bằng là khi khoảng cách từ tất cả các nút lá đến gốc gần như bằng nhau. Tuy nhiên, một k-d tree cân bằng chưa chắc đã là tối ưu cho các ứng dụng như tìm kiếm láng giềng gần nhất 99win club hay phân chia không gian.
Quá trình xây dựng thông thường của k-d tree bao gồm việc tuần tự lấy từng chiều của điểm dữ liệu làm chiều phân chia, chọn giá trị trung vị trên chiều đó làm mặt cắt siêu phẳng, sau đó phân phối các điểm bên trái trung vị vào cành trái và các điểm bên phải trung vị vào cành phải. Quá trình i99bet này được lặp lại đệ quy cho đến khi tất cả các điểm dữ liệu đã được gắn vào cây.
a) Tối ưu hóa lựa chọn chiều phân chia Trước khi bắt đầu xây dựng, ta so sánh sự phân bố của các điểm dữ liệu trên các chiều khác nhau. Khi phương sai của tọa độ trên một chiều càng lớn, sự phân tán của các điểm trên chiều đó càng rộng; ngược lại, nếu phương sai nhỏ, các điểm sẽ tập trung hơn. Việc bắt đầu phân chia từ chiều có phương sai lớn sẽ mang lại kết quả phân chia tốt và giúp cây cân bằng hơn.
b) Tối ưu hóa lựa chọn trung vị Cách thứ nhất, trước khi chạy thuật toán, ta sắp xếp tất cả các điểm dữ liệu theo từng chiều và lưu trữ kết quả. Trong quá trình chọn trung vị sau này, chúng ta không cần phải sắp xếp lại các tập con, điều này cải thiện hiệu suất đáng kể.
Cách thứ hai, ngẫu nhiên chọn một số lượng cố định các điểm từ tập dữ liệu gốc, sau đó sắp xếp chúng và chọn trung vị từ tập mẫu này làm mặt cắt siêu phẳng. Cách tiếp cận này đã được chứng minh là mang lại hiệu suất cao và đảm bảo tính cân bằng tốt.
Bài viết này sử dụng phương pháp xây dựng thông thường, ví dụ về tập điểm (x,y) trên mặt phẳng hai chiều như sau: (2,3), (5,4), (9,6), (4,7), (8,1), (7,2).
a) Khi xây dựng nút gốc, chiều phân chia hiện tại là x. Tập điểm được sắp xếp theo chiều x tăng dần: (2,3), (4,7), (5,4), (7,2), (8,1), (9,6). Giá trị trung vị là (7,2) (chú ý rằng giá trị trung vị trong toán học là (5+7)/2=6, nhưng do yêu cầu của thuật toán, giá trị trung vị được chọn là phần tử tại chỉ mục len(points)//2 = 3, tức points[3] = (7,2)).
b) Các điểm (2,3), (4,7), (5,4) được gắn vào cành trái của nút (7,2), và các điểm (8,1), (9,6) được gắn vào cành phải.
c) Khi xây dựng cành trái của nút (7,2), tập điểm (2,3), (4,7), (5,4) có chiều phân chia là y. Giá trị trung vị là (5,4), nên (2,3) được gắn vào cành trái và (4,7) được gắn vào cành phải.
d) Khi xây dựng cành phải của nút (7,2), tập điểm (8,1), (9,6) cũng có chiều phân chia là y. Giá trị trung vị là (9,6), vì vậy (8,1) được gắn vào cành trái. Đến đây, quá trình xây dựng k-d tree hoàn tất.
Từ hình ảnh trên, ta thấy rằng việc xây dựng một k-d tree chính là quá trình chia nhỏ dần một mặt phẳng hai chiều.
Chúng ta cũng có thể xem xét ví dụ ba chiều từ Wikipedia:
- Đầu tiên, mặt phẳng đứng màu đỏ chia không gian thành hai phần.
- Sau đó, mỗi phần này được chia thêm bởi mặt phẳng ngang màu xanh lá cây.
- Cuối cùng, mỗi phần con được chia tiếp bởi mặt phẳng đứng màu xanh dương, tạo ra tổng cộng tám phần con, tương ứng với các nút lá.
Dưới đây là mã nguồn xây dựng k-d tree:
def kd_tree(points, depth):
if len(points) == 0:
return None
cutting_dim = depth % len(points[0])
medium_index = len(points) // 2
points.sort(key=itemgetter(cutting_dim))
node = Node(points[medium_index])
node.left = kd_tree(points[:medium_index], depth + 1)
node.right = kd_tree(points[medium_index + 1:], depth + 1)
return node
1.2) Tìm kiếm điểm có giá trị tọa độ nhỏ nhất trên chiều d
a) Nếu chiều phân chia của nút hiện tại là d, do tất cả các nút con bên phải đều có giá trị tọa độ trên chiều d lớn hơn hoặc bằng nút hiện tại, ta có thể bỏ qua cành phải và chỉ cần tìm kiếm trên cành trái. Nếu không có cành trái, nút hiện tại chính là điểm có giá trị nhỏ nhất.
b) Nếu chiều phân chia của nút hiện tại không phải là d, ta cần tìm kiếm đệ quy trên cả cành trái lẫn cành phải.
Mã nguồn tìm kiếm điểm có giá trị nhỏ nhất trên chiều d:
def findmin(n, depth, cutting_dim, min_point):
if min_point is None:
min_point = n.location
if n is None:
return min_point
current_cutting_dim = depth % len(min_point)
if n.location[cutting_dim] < min_point[cutting_dim]:
min_point = n.location
if cutting_dim == current_cutting_dim:
return findmin(n.left, depth + 1, cutting_dim, min_point)
else:
leftmin = findmin(n.left, depth + 1, cutting_dim, min_point)
rightmin = findmin(n.right, depth + 1, cutting_dim, min_point)
if leftmin[cutting_dim] > rightmin[cutting_dim]:
return rightmin
else:
return leftmin
1.3) Thêm nút mới Bắt đầu từ nút gốc, nếu giá trị tọa độ của điểm cần thêm trên chiều phân chia hiện tại nhỏ hơn giá trị của nút hiện tại, ta thêm vào cành trái; nếu lớn hơn hoặc bằng, ta thêm vào cành phải. Quá trình này được thực hiện đệ quy cho đến khi đạt tới nút lá.
Mã nguồn thêm nút mới:
def insert(n, point, depth):
if n is None:
return Node(point)
cutting_dim = depth % len(point)
if point[cutting_dim] < n.location[cutting_dim]:
if n.left is None:
n.left = Node(point)
else:
insert(n.left, point, depth + 1)
else:
if n.right is None:
n.right = Node(point)
else:
insert(n.right, point, depth + 1)
Việc thêm nhiều nút có thể gây mất cân bằng cây. Khi mức độ mất cân bằng vượt quá một ngưỡng nhất định, cần tái cân bằng cây.
1.4) Xóa nút Phương pháp đơn giản nhất là thu thập tất cả các nút con của nút cần xóa thành một tập hợp mới, sau đó xây dựng lại cây từ tập hợp này. Phương pháp này có hiệu suất thấp, vì vậy ta sẽ xem xét phương pháp tối ưu hơn.
Giả sử nút cần xóa T có chiều phân chia là x. Ta sẽ xét từng trường hợp cụ thể:
a) Không có cành con: Nút này là nút lá, có thể xóa trực tiếp.
b) Có cành phải: Tìm điểm có giá trị nhỏ nhất trên chiều x trong cành phải của T, thay thế T bằng điểm này và tiếp tục xóa điểm vừa thay thế.
c) Không có cành phải nhưng có cành trái: Tìm điểm có giá trị nhỏ nhất trên chiều x trong cành trái của T, thay thế T bằng điểm này, và đặt cành phải của điểm thay thế là toàn bộ cành trái cũ của T. Sau đó tiếp tục xóa điểm vừa thay thế.
Mã nguồn xóa nút:
def delete(n, point, depth):
cutting_dim = depth % len(point)
if n.location == point:
if n.right is not None:
n.location = findmin(n.right, depth + 1, cutting_dim, None)
delete(n.right, n.location, depth + 1)
elif n.left is not None:
n.location = findmin(n.left, depth + 1)
delete(n.left, n.location, depth + 1)
n.right = n.left
n.left = None
else:
n = None
else:
if point[cutting_dim] < n.location[cutting_dim]:
delete(n.left, point, depth + 1)
else:
delete(n.right, point, depth + 1)
2) Tìm kiếm láng giềng gần nhất
Cho một điểm p, quá trình tìm kiếm điểm trong tập dữ liệu gần p nhất được gọi là tìm kiếm láng giềng gần nhất.
Ví dụ, khi tìm kiếm láng giềng gần nhất của điểm (3,5) trên k-d tree đã xây dựng, bài viết sẽ phân tích quá trình này dựa trên hình ảnh minh họa:
a) Bắt đầu từ nút gốc (7,2), giả sử láng giềng gần nhất hiện tại là (7,2). Sử dụng duyệt sâu trước để khám phá cây, vẽ một đường tròn tâm (3,5) và bán kính bằng khoảng cách từ (3,5) đến (7,2). Ta nhận thấy vùng bên phải của (8,1) không giao với đường tròn, do đó toàn bộ cành phải của (8,1) có thể bị bỏ qua.
b) Di chuyển đến nút gốc của cành trái (5,4), cập nhật láng giềng gần nhất thành (5,4). Vẽ một đường tròn mới với bán kính bằng khoảng cách từ (3,5) đến (5,4). Ta thấy vùng bên phải của (7,2) không giao với đường tròn, nên toàn bộ cành phải của (7,2) được đánh dấu là đã bỏ qua.
c) Sau khi duyệt hết các nút lá, ta thấy không có điểm nào gần hơn (5,4). Do đó, láng giềng gần nhất của (3,5) là (5,4).
Mã nguồn tìm kiếm láng giềng gần nhất:
3) Phân tích độ phức tạp
| Hoạt động | Độ phức tạp trung bình | Độ phức tạp xấu nhất |
|---|---|---|
| Thêm nút | O(log n) | O(n) |
| Xóa nút | O(log n) | O(n) |
| Tìm kiếm láng giềng gần nhất | O(log n) | O(n) |
4) Sử dụng scikit-learn scikit-learn là một thư viện machine learning hữu ích, cung cấp triển khai của KDTree. Dưới đây là một ví dụ minh họa cách xây dựng k-d tree trên không gian hai chiều, thực hiện tìm kiếm k-láng giềng gần nhất và tìm kiếm trong phạm vi bán kính chỉ định.
#!/usr/bin/python
# -*- coding: UTF-8 -*-
import numpy as np
from matplotlib import pyplot as plt
from matplotlib.patches import Circle
from sklearn.neighbors import KDTree
np.random.seed(0)
points = np.random.random((100, 2))
tree = KDTree(points)
point = points[0]
# Tìm kiếm k-láng giềng gần nhất
dists, indices = tree.query([point], k=3)
print(dists, indices)
# Tìm kiếm trong phạm vi bán kính
indices = tree.query_radius([point], r=0.2)
print(indices)
fig = plt.figure()
ax = fig.add_subplot(111, aspect='equal')
ax.add_patch(Circle(point, 0.2, color='r', fill=False))
X, Y = [p[0] for p in points], [p[1] for p in points]
plt.scatter(X, Y)
plt.scatter([point[0]], [point[1]], c='r')
plt.show()