Source: https://dev-docs.yueshu.com.cn/v5.3.2/analytic/algorithms/jaccard/ Documentation version: v5.3.2 # Jaccard 相似度 本文介绍 Jaccard 相似度算法，并演示如何用 GQL 实现该算法。 ## 算法介绍 Jaccard 相似度算法是一种用于衡量两个集合相似系数的指标。Jaccard 相似系数，又称为雅卡尔指数，能够量度有限样本集合的相似度。其定义为两个集合交集大小与并集大小之间的比例，计算公式如下： \[J(A, B) = \frac{|A \cap B|}{|A \cup B|}\] 其中： - \(J(A, B)\)：集合 A 和集合 B 之间的 Jaccard 相似系数。 - \(|A \cap B|\)：集合 A 和集合 B 的交集的大小。 - \(|A \cup B|\)：集合 A 和集合 B 的并集的大小。 Jaccard 相似系数的取值范围为 0 到 1。0 表示没有相似性（没有共同元素），1 表示完全相似（集合相同）。 有关 Jaccard 相似度算法的更多信息，请参见[雅卡尔指数](https://zh.wikipedia.org/wiki/%E9%9B%85%E5%8D%A1%E5%B0%94%E6%8C%87%E6%95%B0)。 ## 数据模型 为了用 GQL 实现 Jaccard 相似度算法，将基于以下数据模型来创建图类型： - 实体分别由类型为`User`和`Movie`的点表示。 - 两种类型的实体之间的关联关系（即用户与电影之间的喜爱关系）由类型为`Likes`的边表示。 在该数据模型中，每个实体（比如用户）都关联着另一类实体的一个集合（比如用户喜欢的电影集合）。为了衡量同类型两个实体之间的相似性，使用了 Jaccard 相似度算法。该算法通过将他们各自关联集合的交集大小除以并集大小来计算 Jaccard 相似系数。该数值反映了实体之间的关联重叠程度。 有关图类型的完整定义，请参见[准备图数据](https://dev-docs.yueshu.com.cn/v5.3.2/analytic/algorithms/jaccard/#1_prepare_graph_data)。 ## 过程实现[]() 为了计算 2 个集合的 Jaccard 相似系数，将创建两类[过程](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/procedures/create/)来实现 Jaccard 相似度算法。 所创建的过程分别为单源 Jaccard 相似度过程和批量输出 Jaccard 相似度过程。有关这些过程的完整定义，请参见[创建过程](https://dev-docs.yueshu.com.cn/v5.3.2/analytic/algorithms/jaccard/#2_create_a_procedure)。下文将介绍过程的关键组成部分及其工作原理。 单源 Jaccard 相似度过程批量输出 Jaccard 相似度过程 过程接收以下输入参数： - `u_id`： 源实体 ID（此处即指定用户的 ID），用于计算与目标实体（其他用户）之间的 Jaccard 相似系数。 此外，在过程内部定义了以下变量： | 变量 | 类型 | 说明 | `source_edges` | 全局 [SumAgg 聚合值变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/agg/sum_agg/) | 源实体与另一类实体之间的连接总数。此过程中即源用户喜欢的电影数量。 | `target_edges` | 点绑定 [SumAgg 聚合值变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/agg/sum_agg/) | 目标实体与另一类实体之间的连接总数。此过程中即目标用户喜欢的电影数量。 | `intersection` | 点绑定 [SumAgg 聚合值变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/agg/sum_agg/) | 源实体和目标实体共同连接的另一类实体的交集大小。此过程中即源用户和目标用户共同喜欢的电影数量。 | `topk_similarity` | 全局 [TopKAgg 聚合值变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/agg/topk_agg/) | 用于存储相似度最高的前 k 个实体及其相应 ID。 | `v_set` | [活动集变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/active-set-variable/) | 与源实体连接的另一类实体的集合。此过程中即所有源用户喜欢的电影的集合。 | `result_file` | [文件变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/file-variable/) | 保存最终结果的文件，包括目标实体 ID 及对应 Jaccard 相似系数。 以下步骤概述了该过程的逻辑： 1. 遍历所有`Likes`边，统计每个实体与另一类实体之间的连接总数（即为每个实体计算`target_edges`）。 2. 根据输入参数`u_id`选择源实体，并计算其与另一类实体之间的连接总数（即`source_edges`）。 3. 收集与源实体相连的所有另一类实体（如所有源用户喜欢的电影），并存入集合`v_set`。 4. 对于每个目标实体，计算`source_edges`、`target_edges`和`intersection`。 5. 通过`source_edges`、`target_edges`和`intersection`计算 Jaccard 相似系数。 6. 将相似度最高的前 k 个目标实体 ID 及其对应的 Jaccard 相似系数存入`topk_similarity`。 7. 处理完所有目标实体后，使用文件变量`result_file`导出最终的相似度结果。 过程接收以下输入参数： - `batch_num`：计算任务的批次数。 - `min_intersection`：源实体与目标实体之间的最小交集数量，只有满足该条件的实体对才会计算相似度。 此外，在过程内部定义了以下变量： | 变量 | 类型 | 说明 | `batch` | [原始值变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/value-variable/) | 当前正在处理的批次编号。 | `source_edges` | 全局 [MapAgg 聚合值变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/agg/map_agg/) | 用于存储每个源实体及其连接对象数量的映射。此过程中指每个用户喜欢的电影数量。 | `source` | [活动集变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/active-set-variable/) | 当前批次的源实体集合。 | `neighbor` | [活动集变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/active-set-variable/) | 与源实体集合相连的另一类实体集合。此过程中指所有用户喜欢的电影形成的集合。 | `out_edges` | 点绑定 [SumAgg 聚合值变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/agg/sum_agg/) | 每个实体的连接对象的总数。此过程中指每个用户喜欢的电影数量。 | `intersection_map` | 点绑定 [MapAgg 聚合值变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/agg/map_agg/) | 源实体 ID 到与目标实体交集数量的映射。 | `topk_similarity` | 点绑定 [TopKAgg 聚合值变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/agg/topk_agg/) | 用于存储每个目标实体对应的相似度最高的前 k 个源实体及其 ID。 | `result_file` | [文件变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/file-variable/) | 保存最终结果的文件，包括源实体 ID、目标实体 ID 及对应 Jaccard 相似系数。 以下步骤概述了该过程的逻辑： 1. 对每个批次，选取一组源实体作为本批次的计算对象。 2. 对于当前批次中的源实体： 1. 计算`source_edges`，即每个源实体连接的另一类实体总数。 2. 收集所有与源实体连接的另一类实体，存入集合`neighbor`。 3. 在`neighbor`中，构建`intersection_map`，记录每个目标实体与源实体的交集数量。 3. 对于每个目标实体（即与`neighbor`集合中至少一个源实体有连接的实体），执行以下步骤： 1. 将`intersection_map`从连接实体传播到目标实体，统计每个目标实体与各源实体的共享连接数量。 2. 对每一对源实体-目标实体，计算`source_edges`、`target_edges`和`intersection`。 3. 若`intersection`大于等于`min_intersection`且并集不为零，则计算 Jaccard 相似系数。 4. 将每个目标实体对应的相似度最高的前 k 个源实体与其 ID 及对应的 Jaccard 相似系数存入`topk_similarity`。 4. 批次内所有实体处理完成后，通过变量`result_file`导出最终相似度结果。 ## 操作步骤 在悦数图管理的控制台中，按顺序执行以下代码块。首次使用时，先按[准备算法示例数据](https://dev-docs.yueshu.com.cn/v5.3.2/analytic/algorithms/prepare-data/)确认操作位置和目录挂载。 ### 1. 准备图数据[]() 1. 创建与数据模型匹配的图类型： ```` ''' CREATE GRAPH TYPE IF NOT EXISTS jaccard_graph_type AS { NODE User (LABEL User {id INT PRIMARY KEY, name STRING}), NODE Movie (LABEL Movie {id INT PRIMARY KEY, title STRING}), EDGE Likes (User)-[LABEL Likes {MULTIEDGE KEY ()}]->(Movie) } ''' ```` 2. 下载以下 CSV 文件，保留文件名，保存到部署目录下的`examples/algorithms/jaccard/`： - [jaccard_node_user.csv](https://dev-docs.yueshu.com.cn/v5.3.2/analytic/algorithms/files/jaccard/jaccard_node_user.csv)：`User`点数据。 - [jaccard_node_movie.csv](https://dev-docs.yueshu.com.cn/v5.3.2/analytic/algorithms/files/jaccard/jaccard_node_movie.csv)：`Movie`点数据。 - [jaccard_edge.csv](https://dev-docs.yueshu.com.cn/v5.3.2/analytic/algorithms/files/jaccard/jaccard_edge.csv)：边数据。 查看 CSV 内容 jaccard_node_user.csv ```` u_id,u_name 1,Alice 2,Bob 3,Charlie 4,David 5,Eve ```` jaccard_node_movie.csv ```` m_id,m_title 1,The Shawshank Redemption 2,The Dark Knight 3,12 Angry Men 4,The Lord of the Rings: The Return of the King 5,Schindler's List ```` jaccard_edge.csv ```` u_id,m_id 1,1 1,2 2,2 2,3 3,2 3,3 3,4 4,3 4,4 5,5 ```` 3. 基于图类型创建一个临时图，并将数据文件加载到临时图中。 ```` CREATE TEMPORARY GRAPH IF NOT EXISTS #jaccard_graph TYPED jaccard_graph_type ```` ```` ''' USE #jaccard_graph IMPORT INTO GRAPH { NODE (u@User {id: u_id, name: u_name}) FROM DATAFILE { PATH: "file:///examples/algorithms/jaccard/jaccard_node_user.csv", FORMAT: "CSV", DELIMITER: ',' }, NODE (m@Movie {id: m_id, title: m_title}) FROM DATAFILE { PATH: "file:///examples/algorithms/jaccard/jaccard_node_movie.csv", FORMAT: "CSV", DELIMITER: ',' }, EDGE (id: u_id)-[e@Likes {}]->(id: m_id) FROM DATAFILE { PATH: "file:///examples/algorithms/jaccard/jaccard_edge.csv", FORMAT: "CSV", DELIMITER: ',' } } ''' ```` 导入成功后，在控制台执行以下查询核对点数： ```` ''' USE #jaccard_graph MATCH (n) RETURN count(n) AS node_count ''' ```` `node_count`应为`10`。点数不符时，先按[文件问题排查](https://dev-docs.yueshu.com.cn/v5.3.2/analytic/algorithms/prepare-data/#troubleshooting)检查文件和导入结果。 ### 2. 创建过程[]() 以下将创建两种实现 Jaccard 相似度算法的过程：单源 Jaccard 相似度过程和批量输出 Jaccard 相似度过程。关于过程实现的更多信息，请参见[过程实现](https://dev-docs.yueshu.com.cn/v5.3.2/analytic/algorithms/jaccard/#_3)。 这两种过程均基于实体之间的连接关系，将每个实体的所有连接对象视为一个集合，并通过聚合技术统计集合的规模以及集合间交集和并集的规模，从而计算实体之间的 Jaccard 相似度。 这两种过程的主要区别在于它们处理实体的方式： - 单源 Jaccard 相似度过程：针对指定实体，计算其连接对象集合与所有其他实体的连接对象集合之间的相似度。该过程适用于需要找到与某个特定实体相似的其他同类型实体的场景。 - 批量输出 Jaccard 相似度过程：该过程以批次方式处理多个源实体，计算每个实体的连接集合与其他实体的连接集合之间的相似度，使其在处理大型数据集时更加高效。它结合了批处理、高级聚合映射、基于阈值的过滤以及资源管理策略，从而能够高效处理大规模数据。因此，该过程适用于对整个数据集进行全面的相似度分析。 单源 Jaccard 相似度过程批量输出 Jaccard 相似度过程 ```` ''' CREATE OR REPLACE PROCEDURE jaccard_ss(u_id INT64) RETURNS () AS { VALUE source_edges SumAgg = 0 VALUE topk_similarity TopKAgg<5, similarity DOUBLE DESC, id INT DESC> NODE VALUE target_edges SumAgg = 0 NODE VALUE intersection SumAgg = 0 VALUE v_set ACTIVE_SET FILE result_file {id INT64, similarity DOUBLE} = DATAFILE { PATH: "file:///examples/algorithms/jaccard/output/single_source", FORMAT: "CSV" } MATCH (u:User)-[e:Likes]->(m:Movie) PER PATH { SET u.@target_edges += 1 } MATCH (u:User)-[:Likes]->(m:Movie) WHERE u.id = u_id PER NODE (u){ SET @source_edges += u.@target_edges } FINALLY { SET v_set = m } MATCH(m:Movie)<-[:Likes]-(t:User) WHERE t.id <> u_id AND m IN v_set PER PATH { SET t.@intersection += 1 } PER NODE (t){ VALUE union_size = t.@target_edges + @source_edges - t.@intersection if union_size <> 0 THEN { VALUE similarity = ROUND(CAST(t.@intersection as DOUBLE) / union_size, 5) SET @topk_similarity += RECORD{similarity:similarity,id:t.id} EXPORT t.id, similarity INTO result_file } } } ''' ```` ```` ''' CREATE OR REPLACE PROCEDURE jaccard_batch(num_of_batch INT64, min_intersection INT64) RETURNS () AS { VALUE batch INT32 = 0 VALUE source_edges MapAgg> VALUE source ACTIVE_SET VALUE neighbor ACTIVE_SET NODE VALUE out_edges SumAgg = 0 NODE VALUE intersection_map MapAgg> NODE VALUE topk_similarity TopKAgg<2, similarity DOUBLE DESC, target_id INT DESC> FILE result_file {source INT64, target INT64, similarity DOUBLE} = DATAFILE { PATH: "file:///examples/algorithms/jaccard/output/batch", FORMAT: "CSV" } // 统计每个实体所连接的另一类型实体的数量（即每个用户喜欢的电影集合大小） MATCH (s:User)-[e:Likes]->(t:Movie) PER PATH { SET s.@out_edges += 1 } // 进行批次循环，并为每个批次选择源实体（源用户） WHILE batch < num_of_batch THEN { LOG_INFO("batch: ", batch) MATCH (s:User) WHERE (element_id(s) % num_of_batch = batch) PER NODE (s){ SET @source_edges += TUPLE(element_id(s), s.@out_edges) } FINALLY { SET source = s } // 对每个源实体（源用户），收集其连接的另一类型实体的集合（即喜欢的电影集合） MATCH (s:User)-[:Likes]->(t:Movie) WHERE s IN source PER PATH { SET t.@intersection_map += TUPLE(element_id(s), 1) } FINALLY { SET neighbor = t } // 从每个另一类型实体（电影）向每个目标实体（目标用户）传播交集映射 MATCH (t:Movie)<-[:Likes]-(target:User) WHERE t IN neighbor PER PATH { SET target.@intersection_map += t.@intersection_map } // 对每个目标实体，统计其与每个源实体共同连接的另一类实体的交集（即共同喜欢的电影集合交集大小），计算 Jaccard 相似系数 PER NODE (target) { VALUE iter = 0 VALUE `map` = target.@intersection_map WHILE iter < length(`map`) THEN { VALUE item = `map`[iter] VALUE source_node_id = item._0 VALUE intersection = item._1 if element_id(target) <> source_node_id AND intersection >= min_intersection THEN { VALUE union_size = target.@out_edges + @source_edges.get(source_node_id) - intersection if (union_size <> 0) THEN { VALUE similarity = CAST(intersection AS DOUBLE) / union_size SET NODE(source_node_id).@topk_similarity += RECORD{similarity:similarity, target_id:target.id} } } SET iter = iter+1 } // 清理临时数据 SET target.@intersection_map.clear() } PER NODE (t) { SET t.@intersection_map.clear() } // 导出本批次每个源实体的相似度结果 MATCH (s:User) WHERE s IN source PER NODE (s) { VALUE topk = s.@topk_similarity VALUE j = 0 WHILE j < length(topk) THEN { VALUE item = topk[j] VALUE target_id = item.target_id VALUE similarity = item.similarity EXPORT s.id, target_id, similarity INTO result_file SET j = j + 1 } SET s.@topk_similarity.clear() } SET @source_edges.clear() SET batch = batch + 1 } } ''' ```` ### 3. 调用过程 调用对应过程来计算 2 个集合的 Jaccard 相似系数。 以下示例中，单源 Jaccard 相似度过程将用户 ID 设置为`2`；而批量输出 Jaccard 相似度过程将批次数设置为`2`，最小交集设置为`0`。 单源 Jaccard 相似度过程批量输出 Jaccard 相似度过程 ```` USE #jaccard_graph CALL jaccard_ss(2) FINISH ```` 此调用将结果写入 CSV，控制台不返回结果表。 在宿主机的部署目录下，打开`examples/algorithms/jaccard/output/single_source/`中的 CSV 文件。示例内容如下： ```` "id","similarity" 1,0.33333 3,0.66667 4,0.33333 ```` `id`表示目标实体（用户）ID，`similarity`表示与源实体（用户 ID 为`2`）的 Jaccard 相似系数。 ```` USE #jaccard_graph CALL jaccard_batch(2,0) FINISH ```` 此调用将结果写入 CSV，控制台不返回结果表。 返回： ```` Log: 2025-10-27T09:50:38.747142 INFO - batch: 0 2025-10-27T09:50:38.764850 INFO - batch: 1 ```` 在宿主机的部署目录下，打开`examples/algorithms/jaccard/output/batch/`中的 CSV 文件。示例内容如下： ```` "source","target","similarity" 2,3,0.6666666666666666 4,3,0.6666666666666666 2,4,0.3333333333333333 4,2,0.3333333333333333 1,2,0.3333333333333333 3,4,0.6666666666666666 1,3,0.25 3,2,0.6666666666666666 ```` `source`表示源实体（用户）ID，`target`表示目标实体（用户）ID，`similarity`则指的是两者之间的 Jaccard 相似系数。 将结果写入图中 如果需要将 Jaccard 结果持久化到图，请参见 [EXPORT](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/in-out/export/)，并根据 Jaccard 的输出结构进行适配： - 对单源过程，可先将`(source_id, target_id, similarity)`写入表变量再落盘。 - 对批量过程，可直接使用现有输出字段`source`、`target`、`similarity`作为写回载荷。 - 若写入远程图，使用`table_split(...)`分批，并通过`nebula_exec`执行批量`USE + INSERT`。 目标图类型需与落盘字段一致，例如将相似度作为`User`到`User`边属性，或作为结果点属性存储。