多维立方体上的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）

回答

相关问题