概述

欧几里得距离（Euclidean Distance）也称欧式距离，它以古希腊数学家欧几里得命名，是最常见的距离度量，用来衡量多维空间中两个点间的绝对距离，也就是两点之间最短的直线距离。在图上是用点的 N 个属性构成两个 N 维向量并计算欧几里得距离。

基本概念

向量

向量是高等数学的基本概念，低维空间中的向量是比较容易理解和表达的。下图分别展示了二维空间、三维空间中向量 A、B 和坐标轴之间的关系以及它们之间的夹角 θ：

对图中两点进行比较时，用指定的 N 个数值类属性构成两个 N 维向量。

欧几里得距离

在二维空间中，欧几里得距离公式为：

在三维空间中，欧几里得距离公式为：

推广到 n 维空间，欧几里得距离公式为：

其中，xi₁ 表示第一个点的第 i 维坐标，xi₂ 表示第二个点的第 i 维坐标。

欧几里得距离的取值范围是 [0,+∞]，数值越小越相似。

标准化欧几里得距离

标准化欧几里得距离是对欧几里得距离的一种改进方案，标准化欧几里得距离的取值范围是 [0,1]，数值越大越相似。

Ultipa 的标准化欧几里得距离计算公式为：

特殊处理

孤点、不连通图

计算两点的欧几里得距离理论上不依赖边，无论待计算的两个节点是否为孤点或是否处于同一个连通分量内，都不影响它们欧几里得距离的计算。

自环边

欧几里得距离的计算与边无关。

有向边

欧几里得距离的计算与边无关。

命令和参数配置

• 命令：algo(similarity)
• params() 参数配置项如下：

计算模式

本算法有两种计算模式：

1. 配对模式：配置有效的两组节点时，将第一组与第二组中的节点两两配对（笛卡尔乘积），逐对计算相似度
2. 选拔模式：仅配置（第）一组有效节点时，对于其中每一个节点，计算其与图中其他所有点的相似度，返回相似度大于 0 的结果并按相似度大小降序排列

示例

示例图

示例图包含 4 个产品 product1、product2、product3 和 product4（UUID 依次为 1、2、3、4；忽略边），产品包含 price、weight、width 和 height 属性：

任务回写

1. 文件回写

示例：通过属性 price、weight、width 和 height 计算产品 UUID = 1 与产品 UUID = 2,3,4 两两之间的欧几里得距离，将算法结果回写至文件

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

示例：通过属性 price、weight、width 和 height 计算产品 UUID = 1,2,3,4 各自与其他所有产品的标准化欧几里得距离，将算法结果回写至文件

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;product3:0.006898;product4:0.006018;
product2,product3:0.018082;product4:0.013309;product1:0.010484;
product3,product4:0.024091;product2:0.018082;product1:0.006898;
product4,product3:0.024091;product2:0.013309;product1:0.006018;

2. 属性回写

算法不支持属性回写。

3. 统计回写

算法无统计值。

直接返回

示例：通过属性 price、weight、width 和 height 计算产品 UUID = 1 与产品 UUID = 2,3,4 两两之间的欧几里得距离，并按照距离大小降序排列结果

algo(similarity).params({
  uuids: [1], 
  uuids2: [2,3,4],
  node_schema_property: [price,weight,width,height],
  type: "euclideanDistance"
}) as distance
return distance
order by distance.similarity desc

结果：

示例：通过属性 price、weight、width 和 height 分别选拔图中与产品 UUID = 1,2 间标准化欧几里得距离相似度最高的产品

algo(similarity).params({
  uuids: [1,2],
  type: "euclidean",
  node_schema_property: [price,weight,width,height],
  top_limit: 1
}) as top
return top

结果：

流式返回

示例：通过属性 price、weight、width 和 height 计算产品 UUID = 3 与产品 UUID = 1,2,4 两两之间的标准化欧几里得距离，仅返回相似度大于 0.01 的结果

algo(similarity).params({
  uuids: [3], 
  uuids2: [1,2,4],
  node_schema_property: [price,weight,width,height],
  type: "euclidean"
}).stream() as distance
where distance.similarity > 0.01
return distance

结果：

示例：通过属性 price、weight、width 和 height 分别选拔图中与产品 UUID = 1,3 间欧几里得距离最远的产品

algo(similarity).params({
  uuids: [1,3],
  node_schema_property: [price,weight,width,height],
  type: "euclideanDistance",
  top_limit: 1
}).stream() as top
return top

结果：

实时统计

算法无统计值。