Postgresql k-najbliższego sąsiada (KNN) na wielowymiarowym kostce

Question

Mam kostkę, która ma 8 wymiarów. Chcę dopasować najbliższego sąsiada. Jestem całkowicie nowy w postgresql. Przeczytałem, że 9.1 obsługuje najbliższego sąsiada pasującego do wielodomen. Byłbym wdzięczny, gdyby ktoś mógł podać pełny przykład:

1. Jak stworzyć stół z kostką 8D?

2. Próbka Włóż

3. Lookup - Dokładne dopasowanie

4. Lookup - najbliższy sąsiad dopasowanie

przykładowe dane:

Dla uproszczenia możemy przyjąć, że cała wartości mieszczą się w zakresie od 0-100.

punkt 1: (1,1,1,1, 1,1,1,1)

punktem2 (2,2,2,2, 2,2,2,2)

Wartość wyszukiwania: (1,1,1,1, 1,1,1,2)

Powinno to być zgodne z Point1, a nie Point2.

Ref:

What's_new_in_PostgreSQL_9.1

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

Answer 1

PostgreSQL operatora odległość <-> i jak rozumieją, może być wykorzystywane do analizy tekstu (z modułem pg_trgrm) i geometry typu.

Nie wiem, jak można go używać z więcej niż 1 wymiarem. Może będziesz musiał zdefiniować własną funkcję odległości lub jakoś przekonwertować dane do jednej kolumny z tekstem lub typem geometrii.Na przykład, jeśli masz tabelę z 8 kolumn (kostka 8-wymiarowej):

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

można przekonwertować go do:

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

A potem do tabeli z jednej kolumny:

c1 
abababac 

Następnie można użyć (po utworzeniu gistindex):

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

Przykład

Tworzenie przykładowych danych

-- 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) 
); 

przekształcania danych wejściowych do tekstu

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 
); 

To daje jednej zmiennej trans_variable gdzie przechowywane są wszystkie 8 wymiary:

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 

Zamiast || operatora można również użyć następującej składni (krótsze, ale bardziej tajemnicze):

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

Dodaj indeks

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

odległość testowa Uwaga: Wybrałam jeden wiersz z tabela - 52;42;18;50;68;29;8;55 - i użyłem lekko zmienionej wartości (42;42;18;52;98;29;8;55), aby przetestować odległość. Oczywiście w twoich danych testowych będą zupełnie inne wartości, ponieważ jest to macierz 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'; 

Można użyć operatora odległość < -> lub funkcji similiarity. Odległość = 1 - Podobieństwo

Answer 2

"patch that introduces kNN search for cubes with euclidean, taxicab and chebyshev distances" był niedawno oferowany na liście pgsql-hackers. Może to działać w twoim celu, jeśli możesz dostosować kompilację PostgreSQL.

Należy pamiętać, że typ cube, rozszerzenie PostgreSQL, może służyć do reprezentowania punktów lub kostek w n-wymiarach. (Wartość n może domyślnie przekroczyć 100, więcej, jeśli podniesiony zostanie limit w cubedata.h). Tak więc ta poprawka powinna między innymi umożliwić wielowymiarowe wyszukiwanie punktu/wektora/kostki w indeksie z indeksem.

(bez tego plastra typu cube nie operatora odległość <-> i funkcję nośną (8) nie ma na OPERATOR CLASS gist_cube_ops, która jest potrzebna, aby dać GiST zdolność do indeksu związane z odległością od te wartości.)

Jeszcze nie wypróbowałem łaty i zauważ, że jedna z odpowiedzi na liście dyskusyjnej sugeruje, że obecnie może przerwać testy regresji.