修改密码

请输入密码
请输入密码 请输入8-64长度密码 和 email 地址不相同 至少包括数字、大写字母、小写字母、半角符号中的 3 个
请输入密码
提交

修改昵称

当前昵称:
提交

搜索
v4.0
    v4.0

    欧几里得距离

    概述

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

    基本概念

    向量

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

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

    欧几里得距离

    在二维空间中,欧几里得距离公式为:

    在三维空间中,欧几里得距离公式为:

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

    其中,xi1 表示第一个点的第 i 维坐标,xi2 表示第二个点的第 i 维坐标。

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

    标准化欧几里得距离

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

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

    特殊处理

    孤点、不连通图

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

    自环边

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

    有向边

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

    命令和参数配置

    • 命令:algo(similarity)
    • params() 参数配置项如下:
    名称
    类型
    默认值
    规范
    描述
    ids 或 uuids []_id 或 []_uuid / 必填 指定计算的第一组节点 ID / UUID
    ids2 或 uuids2 []_id 或 []_uuid / 选填 指定计算的第二组节点 ID / UUID
    type string cosine jaccard 或
    overlap 或
    cosine 或
    pearson 或
    euclideanDistance 或
    euclidean
    相似度度量标准:
    jaccard:杰卡德相似度
    overlap:重叠相似度
    cosine:余弦相似度
    pearson:皮尔森相关系数
    euclideanDistance:欧几里得距离
    euclidean:标准化欧几里得距离
    node_schema_property []@<schema>?.<property> / 数值类的点属性;需 LTE;是否携带 schema 均可 type 为 cosine / pearson / euclideanDistance / euclidean 时,必须指定的构成向量的至少两个点属性,无该属性的点不参与计算;type 为 jaccard / overlap 时,此参数无效
    limit int -1 >=-1 返回的结果条数,-1 表示返回所有结果
    top_limit int -1 >=-1 仅选拔模式可用,每个选拔结果 top_list 的长度,-1 表示返回完整结果

    计算模式

    本算法有两种计算模式:

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

    示例

    示例图

    示例图包含 4 个产品 product1、product2、product3 和 product4(UUID 依次为 1、2、3、4;忽略边),产品包含 price、weight、width 和 height 属性:

    任务回写

    1. 文件回写

    计算模式 配置项 各列数据
    配对模式 filename node1,node2,similarity
    选拔模式 filename node,top_list

    示例:通过属性 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. 统计回写

    算法无统计值。

    直接返回

    计算模式
    别名序号
    类型 描述 列名
    配对模式 0 []perNodePair 各点对及相似度 node1, node2, similarity
    选拔模式 0 []perNode 各点及其选拔结果 node, top_list

    示例:通过属性 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
    

    结果:

    node1 node2 similarity
    1 4 165.178691119648
    1 3 143.96180048888
    1 2 94.3822017119753

    示例:通过属性 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
    

    结果:

    node top_list
    1 2:0.010484,
    2 3:0.018082,

    流式返回

    计算模式
    别名序号
    类型 描述 列名
    配对模式 0 []perNodePair 各点对及相似度 node1, node2, similarity
    选拔模式 0 []perNode 各点及其选拔结果 node, top_list

    示例:通过属性 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
    

    结果:

    node1 node2 similarity
    3 2 0.0180816471945529
    3 4 0.0240910110982062

    示例:通过属性 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
    

    结果:

    node top_list
    1 4:165.178691,
    3 1:143.961800,

    实时统计

    算法无统计值。

    请完成以下信息后可下载此书
    *
    公司名称不能为空
    *
    公司邮箱必须填写
    *
    你的名字必须填写
    *
    你的电话必须填写
    *
    你的电话必须填写