Hàng xóm gần nhất Postgresql k (KNN) trên khối nhiều chiều

Question

Tôi có khối lập phương có 8 kích thước. Tôi muốn làm người hàng xóm gần nhất. Tôi hoàn toàn mới với postgresql. Tôi đọc 9.1 hỗ trợ đối sánh lân cận gần nhất trên đa chiều. Tôi thực sự đánh giá cao nếu ai đó có thể đưa ra một ví dụ hoàn chỉnh:

1. Làm thế nào để tạo một bảng với khối 8D?

2. mẫu Chèn

3. Lookup - phù hợp chính xác

4. Lookup - hàng xóm gần nhất phù hợp với

mẫu dữ liệu:

Để đơn giản vì lợi ích, chúng ta có thể giả định rằng tất cả các giá trị dao động từ 0-100.

Point1: (1,1,1,1, 1,1,1,1)

Point2: (2,2,2,2, 2,2,2,2)

Tra cứu giá trị: (1,1,1,1, 1,1,1,2)

Điều này phải khớp với Point1 và không phải Point2.

Refs:

What's_new_in_PostgreSQL_9.1

https://en.wikipedia.org/wiki/K-d_tree#Nearest_neighbour_search

Answer 1

PostgreSQL hỗ trợ khoảng cách điều hành <-> và như tôi hiểu nó, điều này có thể được sử dụng cho phân tích văn bản (với module pg_trgrm) và geometry kiểu dữ liệu.

Tôi không biết cách bạn có thể sử dụng nó với nhiều hơn 1 thứ nguyên. Có lẽ bạn sẽ phải xác định chức năng khoảng cách của riêng bạn hoặc bằng cách nào đó chuyển đổi dữ liệu của bạn thành một cột với loại văn bản hoặc hình học.Ví dụ nếu bạn có bảng với 8 cột (khối 8 chiều):

c1 c2 c3 c4 c5 c6 c7 c8 
1 0 1 0 1 0 1 2 

Bạn có thể chuyển nó sang:

c1 c2 c3 c4 c5 c6 c7 c8 
a b a b a b a c 

Và sau đó đến bảng với một cột:

c1 
abababac 

Sau đó, bạn có thể sử dụng (sau khi tạo gistindex):

SELECT c1, c1 <-> 'ababab' 
FROM test_trgm 
ORDER BY c1 <-> 'ababab'; 

Ví dụ

Tạo dữ liệu mẫu

-- Create some temporary data 
-- ! Note that table are created in tmp schema (change sql to your scheme) and deleted if exists ! 
drop table if exists tmp.test_data; 

-- Random integer matrix 100*8 
create table tmp.test_data as (
    select 
     trunc(random()*100)::int as input_variable_1, 
     trunc(random()*100)::int as input_variable_2, 
     trunc(random()*100)::int as input_variable_3, 
     trunc(random()*100)::int as input_variable_4, 
     trunc(random()*100)::int as input_variable_5, 
     trunc(random()*100)::int as input_variable_6, 
     trunc(random()*100)::int as input_variable_7, 
     trunc(random()*100)::int as input_variable_8 
    from 
     generate_series(1,100,1) 
); 

Chuyển đổi dữ liệu đầu vào văn bản

drop table if exists tmp.test_data_trans; 

create table tmp.test_data_trans as (
select 
    input_variable_1 || ';' || 
    input_variable_2 || ';' || 
    input_variable_3 || ';' || 
    input_variable_4 || ';' || 
    input_variable_5 || ';' || 
    input_variable_6 || ';' || 
    input_variable_7 || ';' || 
    input_variable_8 as trans_variable 
from 
    tmp.test_data 
); 

này sẽ cung cấp cho bạn một biến trans_variable nơi tất cả các 8 thứ nguyên được lưu trữ:

trans_variable 
40;88;68;29;19;54;40;90 
80;49;56;57;42;36;50;68 
29;13;63;33;0;18;52;77 
44;68;18;81;28;24;20;89 
80;62;20;49;4;87;54;18 
35;37;32;25;8;13;42;54 
8;58;3;42;37;1;41;49 
70;1;28;18;47;78;8;17 

.210

Thay vì || điều hành bạn cũng có thể sử dụng cú pháp sau (ngắn hơn, nhưng khó hiểu hơn):

select 
    array_to_string(string_to_array(t.*::text,''),'') as trans_variable 
from 
    tmp.test_data t 

Thêm index

create index test_data_gist_index on tmp.test_data_trans using gist(trans_variable); 

Kiểm tra khoảng cách Lưu ý: Tôi đã chọn một dòng từ bảng - 52;42;18;50;68;29;8;55 - và sử dụng giá trị hơi thay đổi (42;42;18;52;98;29;8;55) để kiểm tra khoảng cách. Tất nhiên, bạn sẽ có các giá trị hoàn toàn khác nhau trong dữ liệu thử nghiệm của bạn, bởi vì nó là ma trận RANDOM.

select 
    *, 
    trans_variable <-> '42;42;18;52;98;29;8;55' as distance, 
    similarity(trans_variable, '42;42;18;52;98;29;8;55') as similarity, 
from 
    tmp.test_data_trans 
order by 
    trans_variable <-> '52;42;18;50;68;29;8;55'; 

Bạn có thể sử dụng toán tử khoảng cách < -> hoặc chức năng tương tự. Khoảng cách = 1 - Tương tự

Answer 2

Một "patch that introduces kNN search for cubes with euclidean, taxicab and chebyshev distances" gần đây đã được cung cấp trên danh sách pgsql-hacker. Nó có thể làm việc cho mục đích của bạn, nếu bạn có thể tùy chỉnh xây dựng PostgreSQL của bạn.

Lưu ý rằng loại cube, một phần mở rộng PostgreSQL, có thể được sử dụng để biểu thị các điểm hoặc hình khối trong không gian thứ n. (Giá trị của n có thể lên tới 100 theo mặc định, nhiều hơn nếu giới hạn trong số cubedata.h được nâng lên.) Vì vậy, bản vá này nên trong số những thứ khác cho phép tìm kiếm điểm/tìm kiếm lân cận gần nhất đa điểm/vector/lập chỉ mục.

(Không có bản vá này, loại cube không có nhà điều hành khoảng cách <-> và chức năng hỗ trợ (# 8) bị thiếu trong số OPERATOR CLASS gist_cube_ops cần thiết để cung cấp khả năng tạo chỉ mục liên quan đến khoảng cách các giá trị này.)

Tôi chưa thử bản vá và lưu ý rằng một trong các câu trả lời trong danh sách thảo luận cho thấy hiện tại nó có thể phá vỡ một số thử nghiệm hồi quy.