概述
在数学中,欧几里得空间中两点之间的欧几里得距离(Euclidean Distance,也称为欧氏距离)是两点之间的直线长度。在图中,指定节点的N个数值属性(特征)来表示节点在N维欧几里得空间中的位置。
基本概念
欧几里得距离
在二维空间中,两个点A(x1, y1)和B(x2, y2)之间的欧几里得距离公式为:
在三维空间中,两个点A(x1, y1, z1)和B(x2, y2, z2)之间的欧几里得距离公式为:
推广到N维空间,欧几里得距离公式为:
其中,xi1表示第一个点的第i维坐标,xi2表示第二个点的第i维坐标。
欧几里得距离的取值范围是0到+∞,数值越小,两个节点越相似。
标准化欧几里得距离
标准化欧几里得距离将欧几里得距离的取值范围缩放到0至1;越接近1,两个节点越相似。
嬴图采用的标准化欧几里得距离计算公式为:
特殊说明
- 两个节点的欧几里得距离理论上不依赖它们之间的连通性。
示例图集
创建示例图集:
// 在空图集中逐行运行以下语句
create().node_schema("product")
create().node_property(@product, "price", int32).node_property(@product, "weight", int32).node_property(@product, "width", int32).node_property(@product, "height", int32)
insert().into(@product).nodes([{_id:"product1", price:50, weight:160, width:20, height:152}, {_id:"product2", price:42, weight:90, width:30, height:90}, {_id:"product3", price:24, weight:50, width:55, height:70}, {_id:"product4", price:38, weight:20, width:32, height:66}])
创建HDC图集
将当前图集全部加载到HDC服务器hdc-server-1
上,并命名为 hdc_sim_prop
:
CALL hdc.graph.create("hdc-server-1", "hdc_sim_prop", {
nodes: {"*": ["*"]},
edges: {"*": ["*"]},
direction: "undirected",
load_id: true,
update: "static",
query: "query",
default: false
})
hdc.graph.create("hdc_sim_prop", {
nodes: {"*": ["*"]},
edges: {"*": ["*"]},
direction: "undirected",
load_id: true,
update: "static",
query: "query",
default: false
}).to("hdc-server-1")
参数
算法名:similarity
参数名 |
类型 |
规范 |
默认值 |
可选 |
描述 |
---|---|---|---|---|---|
ids |
[]_id |
/ | / | 否 | 通过_id 指定参与计算的第一组点;若未设置则计算所有点 |
uuids |
[]_uuid |
/ | / | 否 | 通过_uuid 指定参与计算的第一组点;若未设置则计算所有点 |
ids2 |
[]_id |
/ | / | 是 | 通过_id 指定参与计算的第二组点;若未设置则计算所有点 |
uuids2 |
[]_uuid |
/ | / | 是 | 通过_uuid 指定参与计算的第二组点;若未设置则计算所有点 |
type |
String | euclideanDistance , euclidean |
cosine |
否 | 指定待计算的相似度类型;计算欧几里得距离时,设置为euclideanDistance ;计算标准化欧几里得距离时,设置为euclidean |
node_schema_property |
[]"<@schema.?><property> " |
/ | / | 否 | 构成向量的数值类型点属性;所有指定的属性必须属于同一个标签(schema) |
return_id_uuid |
String | uuid , id , both |
uuid |
是 | 在结果中使用_uuid 、_id 或同时使用两者来表示点 |
order |
String | asc , desc |
/ | 是 | 根据similarity 分值对结果排序 |
limit |
Integer | ≥-1 | -1 |
是 | 限制返回的结果数;-1 返回所有结果 |
top_limit |
Integer | ≥-1 | -1 |
是 | 在选拔模式下,限制ids /uuids 中每个节点返回的结果数;-1 返回所有相似度大于0的结果。配对模式下,该参数无效 |
该算法包含两种计算模式:
- 配对:同时配置
ids
/uuids
和ids2
/uuids2
时,ids
/uuids
中的每个节点与ids2
/uuids2
中的每个节点配对(自配对除外),并逐对计算相似度。 - 选拔:若仅配置了
ids
/uuids
,则逐对计算其中各节点与图中所有其他节点间的相似度,返回所有或指定个数的相似度大于0的结果,并按相似度降序排列。
文件回写
配对模式下计算相似度:
CALL algo.similarity.write("hdc_sim_prop", {
params: {
return_id_uuid: "id",
ids: "product1",
ids2: ["product2", "product3", "product4"],
node_schema_property: ["price", "weight", "width", "height"],
type: "euclideanDistance"
},
return_params: {
file: {
filename: "euclideanDistance"
}
}
})
algo(similarity).params({
project: "hdc_sim_prop",
return_id_uuid: "id",
ids: "product1",
ids2: ["product2", "product3", "product4"],
node_schema_property: ["price", "weight", "width", "height"],
type: "euclideanDistance"
}).write({
file: {
filename: "euclideanDistance"
}
})
结果:
_id1,_id2,similarity
product1,product2,94.3822
product1,product3,143.962
product1,product4,165.179
完整返回
CALL algo.similarity("hdc_sim_prop", {
params: {
return_id_uuid: "id",
ids: ["product1","product2"],
ids2: ["product2","product3","product4"],
node_schema_property: ["price", "weight", "width", "height"],
type: "euclideanDistance"
},
return_params: {}
}) YIELD distance
RETURN distance
exec{
algo(similarity).params({
return_id_uuid: "id",
ids: ["product1","product2"],
ids2: ["product2","product3","product4"],
node_schema_property: ["price", "weight", "width", "height"],
type: "euclideanDistance"
}) as distance
return distance
} on hdc_sim_prop
结果:
_id1 | _id2 | similarity |
---|---|---|
product1 | product2 | 94.382202 |
product1 | product3 | 143.961807 |
product1 | product4 | 165.178696 |
product2 | product3 | 54.304695 |
product2 | product4 | 74.135010 |
流式返回
CALL algo.similarity("hdc_sim_prop", {
params: {
return_id_uuid: "id",
ids: ["product1", "product3"],
node_schema_property: ["price", "weight", "width", "height"],
type: "euclideanDistance",
top_limit: 1
},
return_params: {
stream: {}
}
}) YIELD top
RETURN top
exec{
algo(similarity).params({
return_id_uuid: "id",
ids: ["product1", "product3"],
node_schema_property: ["price", "weight", "width", "height"],
type: "euclideanDistance",
top_limit: 1
}).stream() as top
return top
} on hdc_sim_prop
结果:
_id1 | _id2 | similarity |
---|---|---|
product1 | product4 | 165.178696 |
product3 | product1 | 143.961807 |