✓ 文件回写 ✕ 属性回写 ✓ 直接返回 ✓ 流式返回 ✕ 统计值
概述
杰卡德相似度(Jaccard Similarity)也称为杰卡德指数(Jaccard Index),由 Paul Jaccard 于 1901 年提出,用于度量两个集合数据的相似性。在图中,收集节点的邻居节点作为邻居集合,两个节点的邻居集合越相似,这两个节点就越相似。
杰卡德相似度的取值范围 0 到 1;1 意味着两个集合完全一样,0 意味着两个集合没有任何共同元素。
基本概念
杰卡德相似度
已知集合 A 和 B,它们之间的杰卡德相似度可表示为:
在下面的例子中,集合 A = {b,c,e,f,g},集合 B = {a,d,b,g},它们的交集 A⋂B = {b,g},并集 A⋃B = {a,b,c,d,e,f,g},因此它们之间的杰卡德相似度为 2 / 7 = 0.2857
。
邻居集合
在 Ultipa 的杰卡德相似度算法中,收集两个目标节点的邻居集合用于计算其相似度时需注意以下几点:
- 邻居集合中没有重复的节点;
- 忽略自环边;
- 忽略两个目标节点之间的边;
- 忽略边方向。
上图中,当计算节点 u 和节点 v 间的杰卡德相似度时,它们的邻居集合分别为 Nu = {a,b,c,d,e} 以及 Nv = {d,e,f},它们的杰卡德相似度为 2 / 6 = 0.3333
。
在实践中,为了计算基于共同邻居的相似性指标,就像杰卡德相似度,有时可能需要将一些点属性转换为点 Schema。例如,当考虑两个申请之间的相似性时,申请的电话号码、邮箱、设备 IP 等信息可能是存储为 @application 类型的点的属性的。如果要使用这些信息来度量相似性,则应将它们设计为节点加入图中。
语法
- 命令:
algo(similarity)
- 参数:
名称 |
类型 |
规范 |
默认 |
可选 |
描述 |
---|---|---|---|---|---|
ids / uuids | []_id / []_uuid |
/ | / | 否 | 待计算的第一组节点的 ID / UUID |
ids2 / uuids2 | []_id / []_uuid |
/ | / | 是 | 待计算的第二组节点的 ID / UUID |
type | string | jaccard |
cosine |
否 | 相似度衡量指标;计算杰卡德相似度时,保持此项为 jaccard |
limit | int | >=-1 | -1 |
是 | 返回的结果条数,-1 返回所有结果 |
top_limit | int | >=-1 | -1 |
是 | 在选拔模式下,限制 ids /uuids 中每个节点返回的最大结果条数,-1 返回所有相似度大于 0 的结果;在配对模式下,此参数无效 |
本算法有两种计算模式:
- 配对:同时配置
ids
/uuids
和ids2
/uuids2
时,将ids
/uuids
中的每个节点分别与ids2
/uuids2
中的每个节点配对(忽略相同节点),逐对计算相似度。 - 选拔:仅配置
ids
/uuids
时,对于其中的每个节点,计算其与图中其他所有节点的相似度,返回所有或限定个数的与其相似度大于 0 的结果,并按相似度降序排列。
示例
示例图如下:
文件回写
配置项 | 回写内容 |
---|---|
filename | node1 ,node2 ,similarity |
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
algo(similarity).params({
uuids: [1,2,3,4],
type: 'jaccard'
}).write({
file:{
filename: 'list'
}
})
结果:文件 list
userA,userC,0.25
userA,userB,0.2
userA,userD:0.166667
userB,userC:0.5
userB,userD,0.25
userB,userA,0.2
userC,userB,0.5
userC,userA,0.25
userD,userB:0.25
userD,userA:0.166667
直接返回
别名序号 |
类型 |
描述 |
列名 |
---|---|---|---|
0 | []perNodePair | 各点对及相似度 | node1 , node2 , similarity |
algo(similarity).params({
uuids: [1,2],
uuids2: [2,3,4],
type: 'jaccard'
}) as jacc
return jacc
结果:jacc
node1 | node2 | similarity |
---|---|---|
1 | 2 | 0.2 |
1 | 3 | 0.25 |
1 | 4 | 0.166666666666667 |
2 | 3 | 0.5 |
2 | 4 | 0.25 |
algo(similarity).params({
uuids: [1,2],
type: 'jaccard',
top_limit: 1
}) as top
return top
结果:top
node1 | node2 | similarity |
---|---|---|
1 | 3 | 0.25 |
2 | 3 | 0.5 |
流式返回
别名序号 |
类型 |
描述 |
列名 |
---|---|---|---|
0 | []perNodePair | 各点对及相似度 | node1 , node2 , similarity |
algo(similarity).params({
uuids: [3],
uuids2: [1,2,4],
type: 'jaccard'
}).stream() as jacc
where jacc.similarity > 0
return jacc
结果:jacc
node1 | node2 | similarity |
---|---|---|
3 | 1 | 0.25 |
3 | 2 | 0.5 |
algo(similarity).params({
uuids: [1],
type: 'jaccard',
top_limit: 2
}).stream() as top
return top
结果:top
node1 | node2 | similarity |
---|---|---|
1 | 3 | 0.25 |
1 | 2 | 0.2 |