多維立方體上的Postgresql k最近鄰居（KNN）

我有一個有8個維度的立方體。我想做最近的鄰居匹配。我對postgresql完全陌生。我讀了9.1支持多維度上的最近鄰居匹配。我真的很感激，如果有人可以舉一個完整的例子：多維立方體上的Postgresql k最近鄰居（KNN）

如何使用8D立方體創建表？
樣品插入
查詢 - 精確匹配
查詢 - 近鄰匹配

樣本數據：

爲了簡單起見，我們可以假設，所有的取值範圍爲0-100。

POINT1：（1,1,1,1，1,1,1,1）

POINT2：（2,2,2,2，2,2,2,2）

查找值：（1,1,1,1,1,1,1,2）

這應該匹配Point1而不是Point2。

參考文獻：

What's_new_in_PostgreSQL_9.1

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

來源

2013-05-21 MD Luffy

你能解釋一下你有什麼數據，也許提供一些小樣本？我認爲8D立方體只是一個有8列（尺寸）的桌子。 –

我編輯了問題以包含示例數據。是的，8D立方體可以使用8個不同的數字列表示。 –

我已將完整的示例添加到我的原始答案中。 –

PostgreSQL支持距離操作者<->和我理解，這可被用於分析文本（帶有pg_trgrm模塊）和geometry數據類型。

我不知道如何在超過1維的情況下使用它。也許你將不得不定義你自己的距離函數或以某種方式將你的數據轉換成一個文本或幾何類型的列。例如，如果您有8列（8維立方體）表：有一列

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

然後到表：

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

你可以將其轉換爲

c1 
abababac

然後你可以使用（在創建gistindex後）：

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

個

例

創建採樣數據

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

變換輸入數據爲文本

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

這會給你一個可變trans_variable其中所有的8個維度存儲：

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

而不是||運營商還可以使用下面的語法（更短，更神祕的）：

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

添加索引

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

測試距離注：我從選定一行表 - 52;42;18;50;68;29;8;55 - 並使用稍微更改的值（42;42;18;52;98;29;8;55）來測試距離。當然，你的測試數據中會有完全不同的值，因爲它是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';

您可以使用距離運算符< - >或相似函數。距離= 1 - 相似度

來源

2013-05-22 07:10:47

謝謝twn08。我嘗試創建索引時遇到了此錯誤：使用gist（trans_variable）在tmp.test_data_trans上創建索引test_data_gist_index; 錯誤：數據類型文本沒有用於訪問方法「要點」的缺省操作符類 SQL狀態：42704 提示：您必須爲索引指定操作符類或爲該數據類型定義默認操作符類。 –

也許'btree_gist'丟失？類似的問題[在這個問題]（http://dba.stackexchange.com/questions/37351/postgresql-exclude-using-error-data-type-integer-has-no-default-operator-class） –

我didn'看到您在分號加入的列中定義條目之間的距離度量。 <->運算符是否使用解碼點的字符串距離或幾何距離？ – Andrew

最近提供了一個「patch that introduces kNN search for cubes with euclidean, taxicab and chebyshev distances」pgsql-hackers列表。如果您可以自定義您的PostgreSQL版本，它可能適合您的目的。

請注意，cube類型（PostgreSQL擴展）可用於表示n維中的點或多維數據集。（默認情況下，n的值可以上升到100，如果在cubedata.h中出現限制，那麼n的值可以更多。）因此，此補丁應該能夠使用索引輔助的多維點/向量/立方體最近鄰居搜索。

（如果沒有這個補丁，該cube類型不具有<->距離運算符和支持功能（＃8）是從一個需要給要點做出的距離相關指數的能力OPERATOR CLASS gist_cube_ops失蹤這些數值。）

我還沒試過補丁，並且注意，這個列表的一個答覆表明，它可能會打破目前一些迴歸測試。

來源

2013-10-02 03:34:38 gojomo

多維立方體上的Postgresql k最近鄰居（KNN）

回答

相關問題