概述
在数学中,欧几里得空间中两点之间的欧几里得距离(Euclidean Distance,也称为欧氏距离)是两点之间的直线长度。在图中,指定节点的N个数值属性(特征)来表示节点在N维欧几里得空间中的位置。
基本概念
欧几里得距离
在二维空间中,两个点A(x1, y1)和B(x2, y2)之间的欧几里得距离公式为:
![](https://img.ultipa.cn/2022-08-09-15-15-45-d2.jpg)
在三维空间中,两个点A(x1, y1, z1)和B(x2, y2, z2)之间的欧几里得距离公式为:
![](https://img.ultipa.cn/2022-08-09-15-15-47-d3.jpg)
推广到N维空间,欧几里得距离公式为:
![](https://img.ultipa.cn/2022-08-09-15-15-49-dn.jpg)
其中,xi1表示第一个点的第i维坐标,xi2表示第二个点的第i维坐标。
欧几里得距离的取值范围是0到+∞,数值越小,两个节点越相似。
标准化欧几里得距离
标准化欧几里得距离将欧几里得距离的取值范围缩放到0至1;越接近1,两个节点越相似。
嬴图采用的标准化欧几里得距离计算公式为:
![](https://img.ultipa.cn/2022-08-09-15-23-53-dnorm.jpg)
特殊说明
- 两个节点的欧几里得距离理论上不依赖它们之间的连通性。
语法
- 命令:
algo(similarity)
- 参数:
名称 |
类型 |
规范 |
默认 |
可选 |
描述 |
---|---|---|---|---|---|
ids / uuids | []_id / []_uuid |
/ | / | 否 | 待计算的第一组节点的ID/UUID |
ids2 / uuids2 | []_id / []_uuid |
/ | / | 是 | 待计算的第二组节点的ID/UUID |
type | string | euclideanDistance , euclidean |
cosine |
否 | 相似度衡量指标;euclideanDistance 计算欧几里得距离,euclidean 计算标准化欧几里得距离 |
node_schema_property | []@<schema>?.<property> |
数值类型,需LTE | / | 否 | 指定至少两个点属性来表示节点,所有属性必须属于同一个Schema |
limit | int | ≥-1 | -1 |
是 | 返回的结果条数,-1 返回所有结果 |
top_limit | int | ≥-1 | -1 |
是 | 在选拔模式下,限制ids /uuids 中每个节点返回的最大结果条数,-1 返回所有相似度大于0的结果;在配对模式下,此参数无效 |
本算法有两种计算模式:
- 配对:同时配置
ids
/uuids
和ids2
/uuids2
时,将ids
/uuids
中的每个节点分别与ids2
/uuids2
中的每个节点配对(忽略相同节点),逐对计算相似度。 - 选拔:仅配置
ids
/uuids
时,对于其中的每个节点,计算其与图中其他所有节点的相似度,返回所有或限定个数的与其相似度大于0的结果,并按相似度降序排列。
示例
示例图包含4个产品(忽略边),每个产品包含price、weight、width和height属性:
![](https://img.ultipa.cn/draw/draw_5cb4504e589a45b7b1d33d7b784e4b77.jpg?v='1662111270178')
文件回写
配置项 | 回写内容 |
---|---|
filename | node1 ,node2 ,similarity |
algo(similarity).params({
uuids: [1],
uuids2: [2,3,4],
node_schema_property: ['price', 'weight', 'width', 'height'],
type: 'euclideanDistance'
}).write({
file:{
filename: 'ed'
}
})
结果:文件ed
product1,product2,94.3822
product1,product3,143.962
product1,product4,165.179
algo(similarity).params({
uuids: [1,2,3,4],
node_schema_property: ['price', 'weight', 'width', 'height'],
type: 'euclidean'
}).write({
file:{
filename: 'ed_list'
}
})
结果:文件ed_list
product1,product2,0.010484
product1,product3,0.006898
product1,product4,0.006018
product2,product3,0.018082
product2,product4,0.013309
product2,product1,0.010484
product3,product4,0.024091
product3,product2,0.018082
product3,product1,0.006898
product4,product3,0.024091
product4,product2,0.013309
product4,product1,0.006018
直接返回
别名序号 |
类型 |
描述 |
列名 |
---|---|---|---|
0 | []perNodePair | 各点对及相似度 | node1 , node2 , similarity |
algo(similarity).params({
uuids: [1,2],
uuids2: [2,3,4],
node_schema_property: ['price', 'weight', 'width', 'height'],
type: 'euclideanDistance'
}) as distance
return distance
结果:distance
node1 | node2 | similarity |
---|---|---|
1 | 2 | 94.3822017119753 |
1 | 3 | 143.96180048888 |
1 | 4 | 165.178691119648 |
2 | 3 | 54.3046959295419 |
2 | 4 | 74.1350119714025 |
algo(similarity).params({
uuids: [1,2],
type: 'euclidean',
node_schema_property: ['price', 'weight', 'width', 'height'],
top_limit: 1
}) as top
return top
结果:top
node1 | node2 | similarity |
---|---|---|
1 | 2 | 0.0104841362649574 |
2 | 3 | 0.0180816471945529 |
流式返回
别名序号 |
类型 |
描述 |
列名 |
---|---|---|---|
0 | []perNodePair | 各点对及相似度 | node1 , node2 , similarity |
algo(similarity).params({
uuids: [3],
uuids2: [1,2,4],
node_schema_property: ['@product.price', '@product.weight', '@product.width'],
type: 'euclidean'
}).stream() as distance
where distance.similarity > 0.01
return distance
结果:distance
node1 | node2 | similarity |
---|---|---|
3 | 2 | 0.0194221437384056 |
3 | 4 | 0.024206458584663 |
algo(similarity).params({
uuids: [1,3],
node_schema_property: ['price', 'weight', 'width', 'height'],
type: 'euclideanDistance',
top_limit: 1
}).stream() as top
return top
结果:top
node1 | node2 | similarity |
---|---|---|
1 | 4 | 165.178691119648 |
3 | 1 | 143.96180048888 |