修改密码

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

修改昵称

当前昵称:
提交

搜索
v4.0
    v4.0

    杰卡德相似度

    概述

    杰卡德相似度(Jaccard Similarity)也称杰卡德指数(Jaccard Index),由 Paul Jaccard 于 1901 年提出,是一种基于网络半结构信息定义的节点相似性指标。它用两个集合交集的大小除以并集的大小,以此来表示两个集合的相似程度。在图上,杰卡德相似度是用节点表示集合,用节点的邻居表示集合中的元素,计算两个节点的共同邻居在所有邻居中的数量占比。

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

    杰卡德相似度的取值范围是 [0,1],数值越大越相似。

    基本概念

    集合

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

    由所有既属于集合 A 又属于集合 B 的元素构成的集合称作 A 和 B 的交集,记作A⋂B;由所有属于集合 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,c,d,e,f,g}

    杰卡德相似度

    已知集合 A 和 B,它们之间的杰卡德相似度可表示为:

    根据此定义,可计算前面例子中集合 A 与 B 的杰卡德相似度:2 / 7 = 0.2857

    邻居

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

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

    上图中,红、绿节点的共同邻居数为 2,邻居数总和为 6,这两个节点的杰卡德相似度为 2 / 6 = 0.3333

    特殊处理

    孤点、不连通图

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

    属于不同连通分量的两个点,它们的杰卡德相似度必然为 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;是否携带 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 位用户 userA、userB、userC 和 userD(UUID 依次为 1、2、3、4)对各项体育运动的喜爱情况:

    任务回写

    1. 文件回写

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

    示例:计算 userC 与 userA、userB、userD 两两之间的杰卡德相似度,将算法结果回写至文件

    algo(similarity).params({
      ids: "userC",
      ids2: ["userA", "userB", "userD"],
      type: "jaccard"
    }).write({
      file:{ 
        filename: "sc"
      }
    })
    

    结果:文件 sc

    userC,userA,0.25
    userC,userB,0.5
    userC,userD,0
    

    示例:计算用户 UUID = 1,2,3,4 各自与其他所有节点的杰卡德相似度,将算法结果回写至文件

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

    结果:文件 list

    userA,userC:0.250000;userB:0.200000;userD:0.166667;
    userB,userC:0.500000;userD:0.250000;userA:0.200000;
    userC,userB:0.500000;userA:0.250000;
    userD,userB:0.250000;userA:0.166667;
    

    2. 属性回写

    算法不支持属性回写。

    3. 统计回写

    算法无统计值。

    直接返回

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

    示例:计算用户 UUID = 1 与用户 UUID = 2,3,4 两两之间的杰卡德相似度,并按照相似性大小降序排列结果

    algo(similarity).params({ 
      uuids: [1], 
      uuids2: [2,3,4],
      type: "jaccard"
    }) as jacc
    return jacc 
    order by jacc.similarity desc
    

    结果:

    node1 node2 similarity
    1 3 0.25
    1 2 0.2
    1 4 0.166666666666667

    示例:分别选拔图中与节点 UUID = 1,2 间杰卡德相似度最高的节点

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

    结果:

    node top_list
    1 3:0.250000,
    2 3:0.500000,

    流式返回

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

    示例:计算用户 UUID = 3 与用户 UUID = 1,2,4 两两之间的杰卡德相似度,仅返回相似度大于 0 的结果

    algo(similarity).params({ 
      uuids: [3], 
      uuids2: [1,2,4],
      type: "jaccard"
    }).stream() as jacc
    where jacc.similarity > 0
    return jacc
    

    结果:

    node1 node2 similarity
    3 1 0.25
    3 2 0.5

    示例:选拔图中与节点 UUID = 1 杰卡德相似度最高的两个节点

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

    结果:

    node top_list
    1 3:0.250000,2:0.200000,

    实时统计

    算法无统计值。

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