修改密码

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

修改昵称

当前昵称:
提交

申请证书

证书详情

Please complete this required field.

  • Ultipa Graph V4

Standalone

Please complete this required field.

Please complete this required field.

服务器的MAC地址

Please complete this required field.

Please complete this required field.

取消
申请
ID
产品
状态
核数
申请天数
审批时间
过期时间
MAC地址
申请理由
审核信息
关闭
基础信息
  • 用户昵称:
  • 手机号:
  • 公司名称:
  • 公司邮箱:
  • 地区:
  • 语言:
修改密码
申请证书

当前未申请证书.

申请证书
Certificate Issued at Valid until Serial No. File
Serial No. Valid until File

Not having one? Apply now! >>>

ProductName CreateTime ID Price File
ProductName CreateTime ID Price File

No Invoice

搜索
    中文

      杰卡德相似度

      概述

      杰卡德相似度(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,

      实时统计

      算法无统计值。

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