修改密码

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

修改昵称

当前昵称:
提交
搜索
v4.0
    v4.0

    重叠相似度

    概述

    重叠相似度(Overlap Similarity)是杰卡德相似度的一种延申,也叫 Szymkiewicz–Simpson 系数。它用两个集合的交集大小除以两个集合中较小的集合的大小,以此来表示两个集合的相似程度。

    集合中的元素通常代表应用场景中实体的一系列属性,例如计算两个信贷申请之间的相似度时,这些元素就是申请表中填写的手机号、邮箱、设备IP、公司名称等。在一般的图应用中,这类信息通常会存储为节点的属性,但是在执行本算法时,这些信息需要设计为节点并入图。

    重叠相似度的取值范围是 [0,1],数值越大越相似。

    基本概念

    集合

    集合由多个元素构成;集合中的元素是无序的、互不相同的;集合 A 中元素的数量就是集合 A 的大小,记作|A|

    由所有既属于集合 A 又属于集合 B 的元素构成的集合称作 A 和 B 的交集,记作A⋂B

    上图中,集合 A 为{b,c,e,f,g},集合 B 为{a,b,d,g},交集 A⋂B 为{b,g}

    重叠相似度

    已知集合 A 和 B,它们之间的重叠相似度可以表示为:

    根据此定义,可计算出前面例子中集合 A 与 B 的重叠相似度:2 / 4 = 0.5

    邻居

    用图中节点 x 的邻居集合 Kx 表示集合 A,节点 y 的邻居集合 Ky 表示集合 B。需要注意的是,KxKy 均既不包含重复值,也不包含 xy。因此,在图上按边查找邻居时需要排除以下干扰:

    • xy 与邻居之间的多条边
    • xy 的自环边
    • xy 之间的边

    上图中,红色节点的邻居数为 3(排除绿色节点),绿色节点的邻居数为 5(排除红色节点),红、绿节点的共同邻居数为 2,这两个节点的重叠相似度为 2 / 3 = 0.6667

    特殊处理

    孤点、不连通图

    在实际应用中很少出现有计算价值的孤点(空集),有孤点则交集为空,重叠相似度为 0。

    属于不同连通分量的两个点,它们的重叠相似度必然为 0。

    自环边

    节点的自环边不会增加节点的邻居数。

    有向边

    对于有向边,本算法会忽略边的方向,按照无向边进行计算。

    结果和统计值

    下图展示 4 位用户 userA、userB、userC 和 userD(UUID 依次为 1、2、3、4)对各项体育运动的喜爱情况:

    算法结果 1:计算每位用户与其他用户间的重叠相似度,返回 nodetop_list 两列;对于每个点,top_list 是与节点的相似度大于 0 的各点的 UUID 及相似度(按相似度降序排列)

    node top_list
    1 3:1.000000, 2:0.500000, 4:0.333333
    2 3:1.000000, 4:0.500000, 1:0.500000
    3 1:1.000000, 2:1.000000
    4 2:0.500000, 1:0.333333

    算法结果 2:分别计算 userC 与其他每位用户间的重叠相似度,返回 node1node2similarity 三列

    node1 node2 similarity
    3 1 1
    3 2 1
    3 4 0

    算法统计值:

    命令和参数配置

    • 命令: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 type 为 cosine 或 pearson 或 euclideanDistance 或 euclidean 时,必须指定构成向量的两个或更多个点属性,带不带 schema 均可,无该属性的点不参与计算;type 为 jaccard 或 overlap 时,不支持此参数
    limit int -1 >=-1 需要返回的结果条数,-1 或忽略表示返回所有结果
    top_limit int -1 -1 或 >=0 仅忽略 ids2 和 uuids2 时可用,每个点的选拔结果 top_list 的长度,-1 或忽略表示返回完整的 top_list

    本算法有两种计算模式:

    1. 选拔模式

    • 不配置 ids2 和 uuids2 或其值为空时,为 ids/uuids 中的每一个点选出与其相似度大于 0 的所有点(按相似度降序排列)。
    • 配置项 limit 限制返回的 ids/uuids 点的数量。

    2. 配对模式

    • 配置有效的 ids2/uuids2 时,将 uuids/ids 与 uuids2/ids2 中的点两两配对(笛卡尔乘积),逐对计算相似度。
    • 配置项 limit 限制返回的点对数量。

    示例:计算集合 UUID = 1,2 与集合 UUID = 3,4 任意两点间的重叠相似度

    algo(similarity).params({ 
      uuids: [1,2], 
      uuids2: [3,4],
      type: "overlap"
    }) as similarity
    return similarity
    

    示例:对于集合 UUID = 1,2,3 中的每个点,计算与该点重叠相似度最高的点

    algo(similarity).params({ 
      uuids: [1,2,3], 
      type: "overlap",
      top_limit: 1
    }) as nodes
    return nodes
    

    算法执行

    任务回写

    1. 文件回写

    配置项 各列数据
    filename node,top_listnode1,node2,similarity

    示例:计算 UUID = 3 的点与其他每个点间的重叠相似度,将算法结果回写至名为 s3 的文件

    algo(similarity).params({
      uuids: 3,
      uuids2: [1,2,4],
      type: "overlap"
    }).write({
      file:{ 
        filename: "s3"
      }
    })
    

    2. 属性回写

    算法不支持属性回写。

    3. 统计回写

    算法无统计值。

    直接返回

    别名序号
    类型
    描述 列名
    0 []perNode 或 []perNodePair 各点及其选拔结果或各点对及相似度 node, top_listnode1, node2, similarity

    示例:计算每个点与其他点间的重叠相似度,将算法结果定义为别名 similarity 返回

    algo(similarity).params({
      uuids: [1,2,3,4],
      type: "overlap"
    }) as similarity
    return similarity
    

    流式返回

    别名序号
    类型
    描述 列名
    0 []perNode 或 []perNodePair 各点及其选拔结果或各点对及其相似度 node, top_listnode1, node2, similarity

    示例:计算每个点与其他点间的重叠相似度,保留相似度最大的点,将算法结果定义为别名 similarity 并返回

    algo(similarity).params({
      uuids: [1,2,3,4],
      type: "overlap",
      top_limit: 1 
    }).stream() as similarity
    return similarity
    

    实时统计

    算法无统计值。

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