基于图的索引建立方法、基于图的索引和推荐方法及装置与流程

1.本发明涉及技术领域，特别涉及一种基于图的索引建立方法、基于图的索引和推荐方法及装置。


背景技术：

2.随着互联网技术的发展，可用信息的迅速增长对现代推荐系统提出了巨大的挑战。近年来，推荐系统受到了广泛的关注，并提出了许多适用于召回和排序阶段的方法，使得它在电子商务、新闻和短视频等各个领域得到了广泛应用。尽管取得了显著的成就，但当面对大规模语料库时，召回阶段无法承受顺序扫描整个语料库带来的高计算成本和延迟。
3.为了应对信息过载，现代推荐系统通常采用“漏斗”结构的多阶段架构，参照图1所示，主要包括召回阶段和排序阶段。召回阶段通常采用向量检索的方式，负责从一个非常大的语料库中快速检索出数百万个物品，排序阶段主要根据用户更细致的偏好和特征对召回阶段检索到的物品进行更准确和个性化的排序。


技术实现要素：

4.本发明的发明人发现，现代推荐系统多阶段的“漏斗”结构，至少存在下述问题：多阶段推荐链路冗长而复杂，当面对大规模语料库时，召回阶段无法承受顺序扫描整个语料库带来的高计算成本和延迟，若想构建一个完整成熟的工业推荐系统需要消耗大量的计算资源和昂贵的训练成本。
5.鉴于上述问题，提出了本发明以便提供一种克服上述问题或者至少部分地解决上述问题的一种基于图的索引建立方法、基于图的索引和推荐方法及装置。
6.第一方面，本发明实施例提供一种基于图的索引的建立方法，包括：
7.随机选取用户节点或者物品节点并插入图中；
8.若选取用户节点，则从物品节点集合中选择与所述用户节点关联度最高的预设数量的物品节点并插入所述图中；
9.若选取物品节点，则从用户节点集合中选择与所述物品节点关联度最高的预设数量的用户节点并插入所述图中；
10.将所选取的用户节点与所述用户节点关联度最高的预设数量的物品节点中的部分或者全部进行连接，以及将所选取的物品节点与所述物品节点关联度最高的预设数量的用户节点中的部分或者全部进行连接；
11.重复上述步骤，直至所有的用户节点和物品节点都已插入所述图中且建立连接；
12.与所述用户节点关联度最高的预设数量的物品节点，以及与所述物品节点关联度最高的预设数量的用户节点是基于预先训练好的打分模型输出的用户和物品之间的关联度分值确定出的。
13.在一个实施例中，将所选取的用户节点与所述用户节点关联度最高的预设数量的物品节点中的部分进行连接，包括：
14.定义候选集和邻居集；
15.针对与所述用户节点关联度最高的预设数量的物品节点中的每个物品节点，判断所述物品节点是否在邻居集中，若否，则将其加入至候选集中，并将所述物品节点的邻居的邻居添加至所述邻居集中，并在所述用户节点与所述候选集合中的各物品节点之间分别添加边，且所述边由用户节点指向各物品节点，直至所述候选集合中的物品节点的数量大于预设的数量阈值。
16.在一个实施例中，将所选取的物品节点与所述物品节点关联度最高的预设数量的用户节点中的部分进行连接，包括：
17.定义候选集和邻居集；
18.针对与所述物品节点关联度最高的预设数量的用户节点中的每个用户节点，判断所述用户节点是否在邻居集中，若否，则将其加入至候选集中，并将所述用户节点的邻居的邻居添加至所述邻居集中，并在所述物品节点与所述候选集合中的各用户节点之间分别添加边，且所述边由物品节点指向用户节点，直至所述候选集合中的用户节点的数量大于预设的数量阈值。
19.在一个实施例中，从物品节点集合中选择与所述用户节点关联度最高的预设数量的物品节点，包括：
20.从物品集合中随机选择一个物品节点，将所述物品节点放入预设的候选集合中；
21.重复执行下述步骤直至候选集合中的物品节点不再发生变化：
22.从所述候选集合中，选择与所述用户节点关联度分值最高的物品节点，确定所述分值最高的物品节点的邻居的邻居；从所述邻居的邻居中，选择尚未添加至所述候选集合中的物品节点，添加至候选集合中，根据所述候选集合中各物品节点与所述用户节点之间的关联度分值的大小，对候选集合中的各物品节点进行排序，保留关联度分值从最大值开始的预设数量的物品节点，更新所述候选集合；
23.上述物品节点与用户节点的关联度分值，通过预设的打分模型得到。
24.在一个实施例中，从用户节点集合中选择出与所述物品节点关联度最高的预设数量的用户节点，包括：
25.从用户集合中随机选择一个用户节点，将所述用户节点放入预设的候选集合中；
26.重复执行下述步骤直至候选集合中的用户节点不再发生变化：
27.从所述候选集合中，选择与所述物品节点关联度分值最高的用户节点，确定所述分值最高的用户节点的邻居的邻居；从所述邻居的邻居中，选择尚未添加至所述候选集合中的用户节点，添加至候选集合中，根据所述候选集合中各用户节点与所述物品节点之间的关联度分值的大小，对候选集合中的各用户节点进行排序，保留关联度分值从最大值开始的预设数量的用户节点，更新所述候选集合；
28.上述用户节点与物品节点的关联度分值，通过预设的打分模型得到。
29.在一个实施例中，所述打分模型通过神经网络模型训练得到。
30.第二方面，本发明实施例提供一种物品推荐的方法，包括：
31.响应于用户的请求，通过预先建立的基于图的索引，利用预先训练得到的打分模型输出的所述用户对应的用户节点与所述基于图的索引中物品节点之间的关联度分值，在所述基于图的索引中查找与所述用户关联度最高的预设数量的物品；
32.按照关联度的大小，对所述物品进行排序，根据排序的结果，向用户返回推荐的物品信息；
33.所述基于图的索引是通过如前述的基于图的索引的建立方法得到的。
34.在一个实施例中，根据所述用户的信息，通过预先建立的基于图的索引，利用预先训练得到的打分模型输出的所述用户对应的用户节点与所述基于图的索引中物品节点之间的关联度分值，在预先建立的基于图的索引中查找与所述用户关联度最高的预设数量的物品，包括：
35.从所述基于图的索引中随机选择一个物品节点，将所述物品节点放入预设的候选集合中；
36.重复执行下述步骤直至候选集合中的物品节点不再发生变化：
37.从所述候选集合中，选择与所述用户节点关联度分值最高的物品节点，确定所述分值最高的物品节点的邻居的邻居，将所述邻居的邻居放入所述候选集合中；
38.将所述候选集合中所有物品节点与用户节点关联度分值按照大小进行排序，保留从最大关联度分值开始的预设数量的物品，更新所述候选集合；
39.上述用户节点与物品节点的关联度分值，通过所述预设的打分模型得到。
40.第三方面，本发明实施例提供一种用户与物品关联度分值打分模型的训练方法，包括：
41.获取用户特征、用户历史行为序列特征、推荐的目标物品的信息，未曝光给用户的物品的负样本；
42.将所述用户特征、所述用户历史行为序列特征、所述推荐的目标物品的信息和所述负样本数据作为训练数据，对预设的神经网络模型进行训练，得到所述打分模型。
43.在一个实施例中，获取所述用户历史行为序列特征，包括：获取为用户推荐所述目标物品之前，所述用户对物品已发生的至少一个行为的特征；
44.获取所述推荐的目标物品的信息，包括：获取推荐的目标物品自身的信息和用户是否点击的信息；
45.获取所述未曝光给用户的物品的负样本，包括：采用对未曝光给所述用户的物品进行随机采样得到所述负样本。
46.在一个实施例中，所述打分模型训练过程中的损失函数为第一目标损失函数乘以第一权重以及第二目标损失函数乘以第二权重的和值；
47.所述第一目标损失函数的训练目标为已曝光物品的预测分数大于未曝光物品的预测分数；
48.所述第二目标损失函数的训练目标为用户已点击的曝光物品的预测分数大于用户未点击的曝光物品的预测分数。
49.第四方面，本发明实施例提供一种用户与物品关联度分值的确定方法，包括：
50.获取用户的用户特征、用户历史行为序列特征以及待推荐的物品的信息；
51.将所述用户特征、用户历史行为序列特征以及待推荐的物品的信息，输入至预先训练好的打分模型中，获取所述打分模型输出的所述用户与物品关联度分值；
52.所述打分模型是采用如前述的用户与物品关联度分值打分模型的训练方法得到。
53.第五方面，本发明实施例提供一种基于图的索引，包括：相连的多个用户节点和物
品节点；其中：
54.所述用户节点与自身关联度最高的预设数量的物品节点全部或部分连接；
55.所述物品节点与自身关联度最高的预设数量的用户节点全部或部分连接；
56.与所述用户节点关联度最高的预设数量的物品节点，以及与所述物品节点关联度最高的预设数量的用户节点是基于预先训练好的打分模型输出的用户和物品之间的关联度分值确定出的。
57.在一个实施例中，所述基于图的索引采用二分有向图的结构。
58.第六方面，本发明实施例提供一种推荐系统，包括：如前述的基于图的索引和用户与物品关联度分值打分模型；
59.所述推荐系统，用于通过所述图的索引和所述打分模型，经过单一的检索阶段，输出与用户关联度最高的预设数量的物品的信息；
60.所述基于图的索引中采用所述用户与物品关联度分值打分模型输出的用户与物品之间的关联度分值衡量用户与物品之间的关联度。
61.第七方面，本发明实施例提供计算设备，包括：存储器、处理器及存储于存储器上并可在处理器上运行的计算机程序，所述处理器执行所述程序时实现如前述的基于图的索引的建立方法，或者实现如前述的物品推荐的方法，或者实现如前述的用户与物品关联度分值打分模型的训练方法，或者实现如前述的用户与物品关联度分值的确定方法。
62.第八方面，本发明实施例计算机可读存储介质，所述计算机可读存储介质存储有计算机程序，所述计算机程序被处理器执行时实现如前述的基于图的索引的建立方法，或者实现如前述的物品推荐的方法，或者实现如前述的用户与物品关联度分值打分模型的训练方法，或者实现如前述的用户与物品关联度分值的确定方法。
63.本发明实施例提供的上述技术方案的有益效果至少包括：
64.本发明实施例简化了传统推荐系统的召回阶段和排序阶段，并将它们整合为一个单阶段推荐系统，打破了传统推荐系统多阶段“漏斗”结构的限制。在该推荐系统中，推荐的步骤包含一个阶段，即检索过程，检索过程涉及用于输出用户和物品之间关联度分值的打分模型和基于图的索引，打分模型可以更好地建模用户和物品之间的复杂关系，另外，基于图的索引将打分模型输出的用户和物品之间关联度分值来很好地衡量用户和物品之间的距离，通过一个阶段就可以直接从数百万项物品中检索出最终的前k个推荐物品列表，从而降低了推荐系统的复杂度，节约了大量的计算资源和训练成本，并且实现了更高的搜索效率和推荐准确率，进而保证了推荐系统的推荐效果。
65.本发明实施例提供的基于图的索引，采用二分有向图的结构，基于打分模型输出的用户与物品之间的关联度分值作为距离函数来很好地衡量用户和物品之间的距离，保证了检索结果的准确性；
66.并且，该基于图的索引还提供了高效的剪枝机制，即在保证检索精度的前提下，压缩用户节点连接的物品节点的数量，以及压缩物品节点连接的用户节点的数量，较好地实现了检索效率和检索结果准确性的平衡。另外，本发明还提供了用户节点和物品节点的边缩减机制，保证了用户连接的物品的多样性，以及物品连接的用户的多样性，进一步提高推荐效果。
67.本发明实施例提供的打分模型，利用用户特征、用户历史行为特征和物品相关特
征作为训练数据训练得到，可以很好地学习到用户、用户对物品的历史行为、用户对当前推荐的物品的反应之间的潜在关系，从而更好地评价用户与物品之间的关联程度。另外，上述打分模型，将同时满足召回目标和排序目标为整体训练目标，使得输出的结果中top-k物品与其他物品的关联度分值有较大的区分度，还使得top-k物品的关联度分值大小是有序的。
68.本发明的其它特征和优点将在随后的说明书中阐述，并且，部分地从说明书中变得显而易见，或者通过实施本发明而了解。本发明的目的和其他优点可通过在所写的说明书、权利要求书、以及附图中所特别指出的结构来实现和获得。
69.下面通过附图和实施例，对本发明的技术方案做进一步的详细描述。
附图说明
70.附图用来提供对本发明的进一步理解，并且构成说明书的一部分，与本发明的实施例一起用于解释本发明，并不构成对本发明的限制。在附图中：
71.图1为传统推荐系统多阶段架构；
72.图2为本发明实施例中基于图的索引的建立方法的流程图；
73.图3为本发明实施例中用户与物品关联度分值打分模型的训练方法的流程图；
74.图4为本发明实施例中基于图的索引的二分有向图结构的示例图；
75.图5a-5b为本发明实施例中边缩减的机制的对比示意图；
76.图6为本发明实施例中单阶段推荐系统的整体结构示意图；
77.图7为本发明实施例中ssr-nn模型的架构示意图；
78.图8为本发明实施例中物品推荐的方法的流程图；
79.图9为本发明实施例中物品推荐方法的又一流程图。
具体实施方式
80.下面将参照附图更详细地描述本公开的示例性实施例。虽然附图中显示了本公开的示例性实施例，然而应当理解，可以以各种形式实现本公开而不应被这里阐述的实施例所限制。相反，提供这些实施例是为了能够更透彻地理解本公开，并且能够将本公开的范围完整的传达给本领域的技术人员。
81.本发明的发明人发现，为了解决现代推荐系统多阶段的“漏斗”结构存在的多阶段推荐链路冗长而复杂，需要消耗大量的计算资源和昂贵的训练成本的问题，对于召回阶段，基于嵌入的检索(ebr，embedding-based retrieval)由于其简单和高效而被应用于推荐系统。然而，ebr不能很好地建模用户-物品偏好的复杂结构，导致难以有效地衡量用户和物品之间的相似度，可能会导致检索准确度的损失。在“漏斗”结构排序阶段，同样有很多关于排序模型的研究。早期的排序模型是通过手动特征交叉完成的，这种方法耗时，且依赖于业务经验，并且，往往会忽略了前序的召回阶段可能带来的精度损失，早期的错误将在后续过程中不断放大，导致排序模型的效果受到召回阶段检索结果的限制，从而影响最终的推荐效果。
82.因此，如何基于神经网络模型设计出高效的检索索引，并提高推荐准确度，是一个值得思考的问题。
83.为了更好地解决推荐系统中存在的问题，提高推荐系统的效率并降低训练开销，
本发明的发明人简化了传统推荐系统的召回阶段和排序阶段，并将它们整合为一个单阶段推荐系统(ssr，single shot recommendation)，打破了传统推荐系统多阶段“漏斗”结构的限制。在该推荐系统中，推荐的步骤包含一个阶段，即检索过程，检索过程涉及用于输出用户和物品之间关联度分值的打分模型和基于图的索引，打分模型可以更好地建模用户和物品之间的复杂关系，另外，基于图的索引将打分模型输出的用户和物品之间关联度分值来很好地衡量用户和物品之间的距离，通过一个阶段就可以直接从数百万项物品中检索出最终的前k个推荐物品列表，从而降低了推荐系统的复杂度，节约了大量的计算资源和训练成本，并且实现了更高的搜索效率和推荐准确率，进而保证了推荐系统的推荐效果。
84.在本发明实施例中，“物品”包括各种推荐场景下的推荐对象，包括但不限于各种有形的物品比如商品等，还包括各种无具体形态的推荐对象例如广告、软件产品、所需的信息或者数据等。对于“用户”而言，同样可以宽泛理解为任何需要推荐服务的自然人、机构或者企业等等，在此对具体的类别并不做限定。
85.为了更好地说明本发明的发明构思，下面以具体实施例来分别说明基于图的索引的建立方法、基于图的索引、物品推荐的方法，用户与物品关联度分值打分模型的训练方法、用户与物品关联度分值的确定方法(即打分模型的使用方法)。
86.本发明实施例提供的基于图的索引的建立方法，参照图2所示，包括：
87.s21、随机选取用户节点或者物品节点并插入图中；
88.若选取的是用户节点，则执行下述步骤s22；若选取的是物品节点，则执行下述步骤s23；
89.s22、从物品节点集合中选择与所述用户节点关联度最高的预设数量的物品节点并插入所述图中；
90.s23、从用户节点集合中选择与所述物品节点关联度最高的预设数量的用户节点并插入所述图中；
91.s24、将所选取的用户节点与所述用户节点关联度最高的预设数量的物品节点中的部分或者全部进行连接；
92.s25、将所选取的物品节点与所述物品节点关联度最高的预设数量的用户节点中的部分或者全部进行连接；
93.s26、重复上述步骤，直至所有的用户节点和物品节点都已插入所述图中且建立连接。
94.上述方法中，与所述用户节点关联度最高的预设数量的物品节点，以及与物品节点关联度最高的预设数量的用户节点是基于预先训练好的打分模型输出的用户和物品之间的关联度分值确定出的。
95.上述打分模型，可以采用任意神经网络函数训练得到，线性或非线性、度量或非度量、凸或非凸、对称或非对称都可以。
96.在一个推荐系统中，假设i和u分别表示物品语料库和用户集合，目标是为每个用户u∈u从一个大规模的物品语料库i中检索出一个前k个相关物品的列表ru。数学上可表示为：
97.98.其中f(u,i)是打分模型的打分函数，用于给出用户u和物品i之间的距离或者相似度分数。上述这个过程被称为top-k搜索。
99.上述基于图的索引的建立方法所建立的索引将打分模型输出的用户和物品之间关联度分值来很好地衡量用户和物品之间的距离，使得通过一个阶段就可以直接从数百万项物品中检索出最终的前k个推荐物品的列表，从而降低了推荐系统的整体复杂度，节约了大量的计算资源和训练成本，并且实现了更高的搜索效率和推荐准确率，进而保证了推荐系统的推荐效果。
100.进一步地，上述基于图的索引例如可采用二分有向图的结构来实现。二分图又称为二部图，是图论中的一种特殊模型。设g＝(v,e)是一个无向图，如果顶点v可分割为两个互不相交的子集(a,b)，并且图中的每条边(i，j)所关联的两个顶点i和j分别属于这两个不同的顶点集(i in a,j in b)，则称图g为一个二分图。二分有向图是指有顶点之间的连接边是有方向的，在本发明实施例中，基于图的索引中，用户节点与用户节点关联度最高的预设数量的物品节点的部分或者全部进行连接时，其所连接的边是由用户节点指向物品节点的；反过来，基于图的索引中，物品节点与物品节点关联度最高的预设数量的用户节点的部分或者全部连接时，其所连接的边是由物品节点指向用户节点的。
101.在一个实施例中，上述打分模型可以通过本发明实施例提供的用户与物品关联度分值打分模型的训练方法训练得到。用户与物品关联度分值打分模型的训练方法，参照图3所示，包括下述步骤：
102.s31、获取用户特征、用户历史行为序列特征、推荐的目标物品的信息，未曝光给用户的物品的负样本；
103.s32、将用户特征、用户历史行为序列特征、推荐的目标物品的信息和负样本数据作为训练数据，对预设的神经网络模型进行训练，得到所述打分模型。
104.进一步地，获取用户特征，即获取用户自身属性相关的特征，比如用户id，用户性别、年龄、消费层次、购物深度(浅层用户、中度用户、深度用户)、所在城市的消费层级等等，以上仅为示例。上述特征可以采用脱敏后的数据得到。
105.获取用户历史行为序列特征，获取用户推荐目标物品之前，用户对物品已发生的至少一个行为的特征。例如，在推荐系统的一个推荐想购买的商品的场景下，用户对推荐的目标物品进行操作前，还会对物品(不限于是什么物品)产生例如浏览、加入购物车、收藏、点击、购买等等一系列的表示对该物品感兴趣的行为。这些用户历史行为序列特征，可能会对后续用户对目标物品的预设的行为比如点击行为形成影响，因此也成为模型训练数据的一部分。
106.进一步地，获取推荐的目标物品的信息，包括：获取推荐的目标物品自身的信息和用户是否点击的信息；
107.用户是否点击的信息可以采用对应的标签，比如点击则标签为1，未点击标签则为0；例如目标物品为物品1-物品9，则目标物品的信息包括：物品1,点击(1)；物品2，未点击(0)；物品3，点击(1)
……
等等此类的信息。
108.进一步地，采用对未曝光给所述用户的物品进行随机采样得到负样本，用户历史行为序列特征中的物品、推荐给用户的目标物品为已曝光给用户的物品，从总的物品集合中排除这些物品中随机采样就可以得到负样本。
109.打分模型训练过程为有监督的学习的过程，具体过程例如如下：
110.1、准备训练数据：打分模型需要大量的数据来进行训练。将前述用户特征、用户历史行为序列特征、推荐的目标物品的信息，未曝光给用户的物品的负样本的数据进行预处理后输入模型。
111.2、初始化神经网络的权重和偏置：基于预先设置的参数对神经网络的权重和偏置进行初始化。
112.3、前向传播计算预测结果：将输入数据输入预设的神经网络，按照网络结构进行前向传播，计算出神经网络的预测结果。
113.4、计算损失函数：将神经网络预测的结果与目标结果进行比较，按照上述设计的损失函数计算出神经网络的损失函数。
114.5、反向传播更新权重和偏置：根据损失函数，使用反向传播算法来更新神经网络的权重和偏置，使得神经网络的预测结果更加接近目标结果。
115.6、重复训练：不断地重复前面的步骤，直到神经网络的预测结果收敛或达到预定的训练次数或误差率。
116.7、测试验证：使用独立的测试集对训练好的神经网络模型进行验证，评估模型的预测准确率和泛化能力。
117.将用户特征和物品特征作为输入，任何神经网络结构都可以设计为打分模型。对于本发明实施例，不仅可以从整个物品库中选择用户感兴趣的top-k物品集(召回目标)，还需要区分用户对top-k物品集中不同物品的兴趣程度(排序目标)。因此，模型可以同时优化召回和排序目标。
118.为了优化召回和排序目标，打分模型训练过程中的损失函数为第一目标损失函数乘以第一权重以及第二目标损失函数乘以第二权重的和值；
119.第一目标损失函数的训练目标为已曝光物品的预测分数大于未曝光物品的预测分数；
120.第二目标损失函数的训练目标为用户已点击的曝光物品的预测分数大于用户未点击的曝光物品的预测分数。
121.就损失函数而言，有两个问题需要解决：(1)区分与用户关联度最高的前k个物品和其他物品，以及(2)使与用户关联度最高的前k个物品的分数有序。给定物品语料库，原始样本可以被分类为曝光样本(已曝光给用户的物品)和未曝光样本(未曝光给用户的物品)。具体而言，曝光样本中又包括已点击的曝光样本和未点击的曝光样本。首先，为了解决第一个问题，即如何更好地区分曝光样本和未曝光样本，将其建模为一个召回任务。期望对于曝光样本的预测分数大于未曝光样本。采用随机负样本采样，基于采样softmax交叉熵损失函数训练模型。此外，还采用加权机制，在训练期间增强随机选择的负样本的权重。具体优化目标如下：
[0122][0123]
其中，ε和分别指代曝光样本和未曝光样本的集合。u表示用户，i表示物品。p(u,i)代表打分模型对(u,i)的预测分数。此外，wu是负采样的权重。
[0124]
其次，为了使前k个物品的分数有序，将其建模为曝光空间中的常见排序任务。期
望模型能正确区分已点击的曝光样本和未点击的曝光样本。前者的预测分数应大于后者，将损失视为基于二元交叉熵损失函数，并且具体优化目标如下：
[0125][0126]
ε指代包括(u,i)对在内的所有曝光样本的集合。y
ui
是用户u与物品i交互的真实标签(当且仅当观察到点击样本(u,i)时，y
ui
＝1)，而p
ui
是模型预测用户u点击物品i的概率。因此，通过整合前面提到的所有目标，打分模型需要优化的总目标如下：
[0127][0128]
其中，λa和λo表示权衡不同损失项重要性的权衡参数。
[0129]
通过上述训练过程，可得到打分模型，对于打分模型来说，本发明实施例还提供了一种用户与物品关联度分值的确定方法，也就是该模型的使用方法，该方法包括下述步骤：
[0130]
获取用户的用户特征、用户历史行为序列特征以及待推荐的物品的信息；
[0131]
将用户特征、用户历史行为序列特征以及待推荐的物品的信息，输入至预先训练好的打分模型中，获取打分模型输出的所述用户与物品关联度分值。
[0132]
使用打分模型进行关联度分值的预测时，输入的用户和物品的相关信息，可以是一个用户与多个物品的相关信息，也可由是一个物品与多个用户的相关信息，还可以是多个用户与多个物品的相关信息，本发明实施例对此不做限定。
[0133]
在一个实施例中，基于图的索引的二分有向图的例子可参照图4所示，图4中有两种类型的节点——用户和物品，图中的边连接这两种节点，并且边是有方向的。每个用户会连接她/他最喜欢的m个物品，每个物品会连接到与它最相关的n个用户。
[0134]
因为通过检索基于图的索引来获得用户关联度最高的物品(代表用户最喜欢的前m个物品)，是根据基于图结构的特点，在图上进行游走和搜索，按照节点之间的距离或相关性，检索出与查询节点最相关的k个节点。为了提高检索效率，则需要在保证检索精度的前提下，压缩用户节点连接的用户节点的数量，以及压缩物品节点连接的用户节点的数量，即需要从所选取的用户节点与用户关联度最高的预设数量的物品节点中选择部分进行连接，例如，从k个物品节点中再找出代表用户最喜欢的前m个物品节点。不论是搜索物品还是搜索用户，都可以采用相似的贪心搜索算法。对于物品搜索，将返回用户节点的候选集；而对于用户搜索，将返回物品节点的候选集。
[0135]
基于图的索引是通过迭代的方式构建的，在一个实施例中，前述步骤s24中将所选取的用户节点与用户节点关联度最高的预设数量的物品节点中的部分进行连接，可通过下述流程实现：
[0136]
定义候选集和邻居集；
[0137]
针对与用户节点关联度最高的预设数量的物品节点中的每个物品节点，判断物品节点是否在邻居集中，若否，则将其加入至候选集中，并将物品节点的邻居的邻居添加至邻居集中，并在用户节点与候选集合中的各物品节点之间分别添加边，且添加的边由用户节点指向各物品节点，直至候选集合中的物品节点的数量大于预设的数量阈值。
[0138]
例如与用户节点关联度最高的预设数量的物品节点的数量为k个，定义一个空的候选集，一个空的邻居集；
[0139]
对于k个与用户节点关联度最高的物品节点中的每个物品节点，如果物品节点不在邻居集中，则将其加入到候选集中，并将物品节点的邻居的邻居添加到邻居集中，并在图中从物品节点到用户节点添加一条边，此时，判断候选集的物品节点的数量是否达到预设的最大节点数量m，若未达到，则重复执行前述步骤，直至候选集内物品节点的数量达到m。
[0140]
类似地，上述步骤s25中，将所选取的物品节点与物品节点关联度最高的预设数量的用户节点中的部分进行连接，可通过下述流程实现：
[0141]
定义候选集和邻居集；
[0142]
针对与物品节点关联度最高的预设数量的用户节点中的每个用户节点，判断用户节点是否在邻居集中，若否，则将其加入至候选集中，并将用户节点的邻居的邻居添加至邻居集中，并在物品节点与候选集合中的各用户节点之间分别添加边，且添加的该边由物品节点指向用户节点，直至候选集合中的用户节点的数量大于预设的数量阈值。
[0143]
例如与物品节点关联度最高的预设数量的用户节点的数量为k个，首先定义一个空的候选集，一个空的邻居集；
[0144]
针对k个与物品节点关联度最高的用户节点中的每个用户节点，如果用户节点不在邻居集中，则将其加入到候选集中，并将用户节点的邻居的邻居添加至邻居集中，并在图中从用户节点到物品节点添加一条边，此时，判断候选集的用户节点的数量是否达到预设的最大节点数量m，若未达到，则重复执行前述步骤，直至候选集内物品节点的数量达到m。
[0145]
无论索引基于什么结构，大规模检索系统总是需要在效率和效果之间进行权衡。为了提高检索效率，基于图的近邻搜索方法可采用精心设计的边缩减方法来限制节点的度数，以减小检索过程中的计算量，提升检索效率并保证推荐准确率。
[0146]
参照图5a所示，假设要插入一个用户节点(user 3)，并且假设每个用户节点最多有2个边(即m＝2)。首先利用物品邻居搜索函数来获取前4个候选物品(即图5a中的item1,2,3和4)。图5a显示了没有边缩减的情况。由于相似的物品会有相似的分数，这种方法会连接太多相似的候选物品节点。
[0147]
为了增加连接的多样性，本发明实施例提出了一种边缩减的机制(即上述步骤s24和s25的具体实施方式)，例如如图5b所示的例子，首先连接前1个候选物品(即物品节点item1)。对于其他候选物品，将检查它们是否可以通过已选定的候选物品在两次跳跃内到达(即邻居的邻居)。例如，候选物品2可以通过用户1从物品1到达。因此，候选物品2不会被选择(即被放入邻居集中)，而连接候选物品3(即被放入至候选集中)，因为它不能通过先前连接的物品节点(物品1)在两次跳跃内到达。插入用户节点的边缩减机制与插入物品节点类似，在此不再赘述。
[0148]
进一步地，上述k个与用户节点关联度最高的物品节点，例如可通过预设的用户邻居搜索函数搜索得到。
[0149]
该用户邻居搜索函数的实现过程如下：
[0150]
从物品集合中随机选择一个物品节点，将所述物品节点放入预设的候选集合中；
[0151]
重复执行下述步骤直至候选集合中的物品节点不再发生变化：
[0152]
从候选集合中，选择与用户节点关联度分值最高的物品节点，确定所述分值最高的物品节点的邻居的邻居；从邻居的邻居中，选择尚未添加至所述候选集合中的物品节点，添加至候选集合中，根据所述候选集合中各物品节点与所述用户节点之间的关联度分值的
大小，对候选集合中的各物品节点进行排序，保留关联度分值从最大值开始的预设数量的物品节点，更新所述候选集合；
[0153]
上述物品节点与用户节点的关联度分值，通过预设的打分模型得到。
[0154]
经过上述过程，实现找到与给定用户节点最相关的k个物品节点。
[0155]
进一步地，上述k个与物品节点关联度最高的用户节点，例如可通过预设的物品邻居搜索函数搜索得到。
[0156]
物品邻居搜索函数的实现过程如下：
[0157]
从用户集合中随机选择一个用户节点，将所述用户节点放入预设的候选集合中；
[0158]
重复执行下述步骤直至候选集合中的用户节点不再发生变化：
[0159]
从所述候选集合中，选择与所述物品节点关联度分值最高的用户节点，确定所述分值最高的用户节点的邻居的邻居；从所述邻居的邻居中，选择尚未添加至所述候选集合中的用户节点，添加至候选集合中，根据所述候选集合中各用户节点与所述物品节点之间的关联度分值的大小，对候选集合中的各用户节点进行排序，保留关联度分值从最大值开始的预设数量的用户节点，更新所述候选集合；
[0160]
上述用户节点与物品节点的关联度分值，通过预设的打分模型得到。
[0161]
经过上述过程，实现找到与给定物品节点最相关的k个用户节点。
[0162]
为了说明本发明实施例提供的上述单阶段推荐系统的结构，以一个具体的实例进行说明：
[0163]
如图6所示，ssr只包括一个阶段，神经网络模型(ssr-nn)和基于图的索引(ssr-index)，可以直接从数百万项物品中检索出最终的前k个推荐物品列表。ssr-nn是一种基于多目标联合优化的神经网络模型，可以更好地建模用户和物品之间的复杂关系。ssr-index是一种适用于大规模检索的二分图索引结构，采用ssr-nn作为距离函数来很好地衡量用户和物品之间的距离。
[0164]
参照图7所示，ssr-nn模型中，其训练时，包括用户特征(user feature)、用户历史行为序列(user behavior sequences)、目标物品(target item)和负样本(negative items),其中，用户行为序列特征与target item间采用了target attention的方式进行交互，以获取与目标target最相关的行为特征。
[0165]
target item和负样本的item特征，与用户序列特征计算target attention。
[0166]
target attention的结构，例如可基于经典的din模型结构实现。
[0167]
上述特征经过concat函数合并后，再经由多层dnn可得到最终的关联度分值。
[0168]
该打分模型的损失函数可参见前述损失函数的说明。训练数据可来源已有的物品展示广告点击率估计数据集，该数据集可通过对购物网站随机抽样广告点击日志生成。
[0169]
对于ssr-index的构建过程，可以在下述算法1中找到。
[0170]
基于图的索引是迭代构建的。图被初始化为空图，并且交替插入物品和用户节点。第一个节点将被插入作为孤立节点，因为它找不到任何邻居。稍后，对于后续的节点，它们将通过搜索算法至少找到一个邻居。物品搜索和用户搜索有两个分别的贪心搜索算法，如下述算法2和算法3所示。对于物品搜索，将返回用户的候选集，而对于用户搜索，将返回物品的候选集。两个算法大部分相同，除了入口点的选择和调用打分模型f(u,i)的方式。
[0171][0172][0173]
上述searchforitem(pi,g,k,f)的定义如下：
[0174][0175]
上述searchforuser(pu,g,k,f)的定义如下：
[0176]
[0177][0178]
基于相同的发明构思，本发明实施例还提供了一种物品推荐的方法，参照图8所示，包括下述步骤：
[0179]
s81、响应于用户的请求，通过预先建立的基于图的索引，利用预先训练得到的打分模型输出的所述用户对应的用户节点与所述基于图的索引中物品节点之间的关联度分值，在所述基于图的索引中查找与所述用户关联度最高的预设数量的物品；
[0180]
s82、按照关联度的大小，对所述物品进行排序，根据排序的结果，向用户返回推荐的物品信息；
[0181]
上述基于图的索引是通过如前述的基于图的索引的建立方法得到的。
[0182]
上述用户的请求，例如可以是访问网站的请求，访问推荐系统的请求，一切触发推荐系统工作的请求皆可，本发明实施例并不限定。
[0183]
进一步地，上述步骤s81中，根据所述用户的信息，通过预先建立的基于图的索引，
利用预先训练得到的打分模型输出的所述用户对应的用户节点与所述基于图的索引中物品节点之间的关联度分值，在预先建立的基于图的索引中查找与所述用户关联度最高的预设数量的物品，具体可通过下述方式实现：
[0184]
从所述基于图的索引中随机选择一个物品节点，将所述物品节点放入预设的候选集合中；
[0185]
重复执行下述步骤直至候选集合中的物品节点不再发生变化：
[0186]
从所述候选集合中，选择与所述用户节点关联度分值最高的物品节点，确定所述分值最高的物品节点的邻居的邻居，将所述邻居的邻居放入所述候选集合中；
[0187]
将所述候选集合中所有物品节点与用户节点关联度分值按照大小进行排序，保留从最大关联度分值开始的预设数量的物品，更新所述候选集合；
[0188]
上述用户节点与物品节点的关联度分值，通过所述预设的打分模型得到。
[0189]
上述步骤s82中，可根据关联分值从大到小的排序结果，按顺序向用户推送相关物品的数据，比如商品的广告，或者其他形式的推荐信息等等。
[0190]
本发明实施例提供的物品推荐的方法的流程可参照图9所示，从图9可以看出，用户发起请求后，由单阶段推荐系统的一步检索过程即可获得与用户关联度最高的top-k的物品。
[0191]
本发明实施例还提供一种基于图的索引，包括：彼此相连的多个用户节点和物品节点；其中：
[0192]
所述用户节点与自身关联度最高的预设数量的物品节点全部或部分连接；
[0193]
所述物品节点与自身关联度最高的预设数量的用户节点全部或部分连接；
[0194]
与所述用户节点关联度最高的预设数量的物品节点，以及与所述物品节点关联度最高的预设数量的用户节点是基于预先训练好的打分模型输出的用户和物品之间的关联度分值确定出的。
[0195]
进一步地，上述基于图的索引采用二分有向图的结构。
[0196]
本发明实施例还提供了一种推荐系统，包括：如前述的基于图的索引和用户与物品关联度分值打分模型；
[0197]
推荐系统，用于通过所述图的索引和所述打分模型，经过单一的检索阶段，输出与用户关联度最高的预设数量的物品的信息；
[0198]
所述基于图的索引中采用所述用户与物品关联度分值打分模型输出的用户与物品之间的关联度分值衡量用户与物品之间的关联度。
[0199]
一个推荐系统的架构的示例可参照前述图6所示。
[0200]
本发明实施例还提供了一种计算设备，包括：存储器、处理器及存储于存储器上并可在处理器上运行的计算机程序，所述处理器执行所述程序时实现如前述的基于图的索引的建立方法，或者实现如前述的物品推荐的方法，或者实现如前述的用户与物品关联度分值打分模型的训练方法，或者实现如前述的用户与物品关联度分值的确定方法。
[0201]
本发明实施例还提供了一种计算机可读存储介质，所述计算机可读存储介质存储有计算机程序，所述计算机程序被处理器执行时实现如前述的基于图的索引的建立方法，或者实现如前述的物品推荐的方法，或者实现如前述的用户与物品关联度分值打分模型的训练方法，或者实现如前述的用户与物品关联度分值的确定方法。
[0202]
本技术所涉及的用户信息(包括但不限于用户设备信息、用户个人信息等)和数据(包括但不限于用于分析的数据、存储的数据、展示的数据等)，均为经用户授权或者经过各方充分授权的信息和数据，并且相关数据的收集、使用和处理需要遵守相关国家和地区的相关法律法规和标准，并提供有相应的操作入口，供用户选择授权或者拒绝。
[0203]
本领域内的技术人员应明白，本发明的实施例可提供为方法、系统、或计算机程序产品。因此，本发明可采用完全硬件实施例、完全软件实施例、或结合软件和硬件方面的实施例的形式。而且，本发明可采用在一个或多个其中包含有计算机可用程序代码的计算机可用存储介质(包括但不限于磁盘存储器和光学存储器等)上实施的计算机程序产品的形式。
[0204]
本发明是参照根据本发明实施例的方法、设备(系统)、和计算机程序产品的流程图和/或方框图来描述的。应理解可由计算机程序指令实现流程图和/或方框图中的每一流程和/或方框、以及流程图和/或方框图中的流程和/或方框的结合。可提供这些计算机程序指令到通用计算机、专用计算机、嵌入式处理机或其他可编程数据处理设备的处理器以产生一个机器，使得通过计算机或其他可编程数据处理设备的处理器执行的指令产生用于实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能的装置。
[0205]
这些计算机程序指令也可存储在能引导计算机或其他可编程数据处理设备以特定方式工作的计算机可读存储器中，使得存储在该计算机可读存储器中的指令产生包括指令装置的制造品，该指令装置实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能。
[0206]
这些计算机程序指令也可装载到计算机或其他可编程数据处理设备上，使得在计算机或其他可编程设备上执行一系列操作步骤以产生计算机实现的处理，从而在计算机或其他可编程设备上执行的指令提供用于实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能的步骤。
[0207]
显然，本领域的技术人员可以对本发明进行各种改动和变型而不脱离本发明的精神和范围。这样，倘若本发明的这些修改和变型属于本发明权利要求及其等同技术的范围之内，则本发明也意图包含这些改动和变型在内。

技术特征：
1.一种基于图的索引的建立方法，其特征在于，包括：随机选取用户节点或者物品节点并插入图中；若选取用户节点，则从物品节点集合中选择与所述用户节点关联度最高的预设数量的物品节点并插入所述图中；若选取物品节点，则从用户节点集合中选择与所述物品节点关联度最高的预设数量的用户节点并插入所述图中；将所选取的用户节点与所述用户节点关联度最高的预设数量的物品节点中的部分或者全部进行连接，以及将所选取的物品节点与所述物品节点关联度最高的预设数量的用户节点中的部分或者全部进行连接；重复上述步骤，直至所有的用户节点和物品节点都已插入所述图中且建立连接；与所述用户节点关联度最高的预设数量的物品节点，以及与所述物品节点关联度最高的预设数量的用户节点是基于预先训练好的打分模型输出的用户和物品之间的关联度分值确定出的。2.如权利要求1所述的方法，其特征在于，将所选取的用户节点与所述用户节点关联度最高的预设数量的物品节点中的部分进行连接，包括：定义候选集和邻居集；针对与所述用户节点关联度最高的预设数量的物品节点中的每个物品节点，判断所述物品节点是否在邻居集中，若否，则将其加入至候选集中，并将所述物品节点的邻居的邻居添加至所述邻居集中，并在所述用户节点与所述候选集合中的各物品节点之间分别添加边，且所述边由用户节点指向各物品节点，直至所述候选集合中的物品节点的数量大于预设的数量阈值。3.如权利要求1所述的方法，其特征在于，将所选取的物品节点与所述物品节点关联度最高的预设数量的用户节点中的部分进行连接，包括：定义候选集和邻居集；针对与所述物品节点关联度最高的预设数量的用户节点中的每个用户节点，判断所述用户节点是否在邻居集中，若否，则将其加入至候选集中，并将所述用户节点的邻居的邻居添加至所述邻居集中，并在所述物品节点与所述候选集合中的各用户节点之间分别添加边，且所述边由物品节点指向用户节点，直至所述候选集合中的用户节点的数量大于预设的数量阈值。4.如权利要求1所述的方法，其特征在于，从物品节点集合中选择与所述用户节点关联度最高的预设数量的物品节点，包括：从物品集合中随机选择一个物品节点，将所述物品节点放入预设的候选集合中；重复执行下述步骤直至候选集合中的物品节点不再发生变化：从所述候选集合中，选择与所述用户节点关联度分值最高的物品节点，确定所述分值最高的物品节点的邻居的邻居；从所述邻居的邻居中，选择尚未添加至所述候选集合中的物品节点，添加至候选集合中，根据所述候选集合中各物品节点与所述用户节点之间的关联度分值的大小，对候选集合中的各物品节点进行排序，保留关联度分值从最大值开始的预设数量的物品节点，更新所述候选集合；上述物品节点与用户节点的关联度分值，通过预设的打分模型得到。
5.如权利要求1所述的方法，其特征在于，从用户节点集合中选择出与所述物品节点关联度最高的预设数量的用户节点，包括：从用户集合中随机选择一个用户节点，将所述用户节点放入预设的候选集合中；重复执行下述步骤直至候选集合中的用户节点不再发生变化：从所述候选集合中，选择与所述物品节点关联度分值最高的用户节点，确定所述分值最高的用户节点的邻居的邻居；从所述邻居的邻居中，选择尚未添加至所述候选集合中的用户节点，添加至候选集合中，根据所述候选集合中各用户节点与所述物品节点之间的关联度分值的大小，对候选集合中的各用户节点进行排序，保留关联度分值从最大值开始的预设数量的用户节点，更新所述候选集合；上述用户节点与物品节点的关联度分值，通过预设的打分模型得到。6.如权利要求1-5任一项所述的方法，其特征在于，所述打分模型通过神经网络模型训练得到。7.一种物品推荐的方法，其特征在于，包括：响应于用户的请求，通过预先建立的基于图的索引，利用预先训练得到的打分模型输出的所述用户对应的用户节点与所述基于图的索引中物品节点之间的关联度分值，在所述基于图的索引中查找与所述用户关联度最高的预设数量的物品；按照关联度的大小，对所述物品进行排序，根据排序的结果，向用户返回推荐的物品信息；所述基于图的索引是通过如权利要求1-6任一项所述的基于图的索引的建立方法得到的。8.如权利要求7所述的方法，其特征在于，根据所述用户的信息，通过预先建立的基于图的索引，利用预先训练得到的打分模型输出的所述用户对应的用户节点与所述基于图的索引中物品节点之间的关联度分值，在预先建立的基于图的索引中查找与所述用户关联度最高的预设数量的物品，包括：从所述基于图的索引中随机选择一个物品节点，将所述物品节点放入预设的候选集合中；重复执行下述步骤直至候选集合中的物品节点不再发生变化：从所述候选集合中，选择与所述用户节点关联度分值最高的物品节点，确定所述分值最高的物品节点的邻居的邻居，将所述邻居的邻居放入所述候选集合中；将所述候选集合中所有物品节点与用户节点关联度分值按照大小进行排序，保留从最大关联度分值开始的预设数量的物品，更新所述候选集合；上述用户节点与物品节点的关联度分值，通过所述预设的打分模型得到。9.一种用户与物品关联度分值打分模型的训练方法，其特征在于，包括：获取用户特征、用户历史行为序列特征、推荐的目标物品的信息，未曝光给用户的物品的负样本；将所述用户特征、所述用户历史行为序列特征、所述推荐的目标物品的信息和所述负样本数据作为训练数据，对预设的神经网络模型进行训练，得到所述打分模型。10.如权利要求9所述的训练方法，其特征在于，获取所述用户历史行为序列特征，包括：获取为用户推荐所述目标物品之前，所述用户对物品已发生的至少一个行为的特征；
获取所述推荐的目标物品的信息，包括：获取推荐的目标物品自身的信息和用户是否点击的信息；获取所述未曝光给用户的物品的负样本，包括：采用对未曝光给所述用户的物品进行随机采样得到所述负样本。11.如权利要求9所述的训练方法，其特征在于，所述打分模型训练过程中的损失函数为第一目标损失函数乘以第一权重以及第二目标损失函数乘以第二权重的和值；所述第一目标损失函数的训练目标为已曝光物品的预测分数大于未曝光物品的预测分数；所述第二目标损失函数的训练目标为用户已点击的曝光物品的预测分数大于用户未点击的曝光物品的预测分数。12.一种用户与物品关联度分值的确定方法，其特征在于，包括：获取用户的用户特征、用户历史行为序列特征以及待推荐的物品的信息；将所述用户特征、用户历史行为序列特征以及待推荐的物品的信息，输入至预先训练好的打分模型中，获取所述打分模型输出的所述用户与物品关联度分值；所述打分模型是采用如权利要求9-11任一项所述的用户与物品关联度分值打分模型的训练方法得到。13.一种基于图的索引，其特征在于，包括：相连的多个用户节点和物品节点；其中：所述用户节点与自身关联度最高的预设数量的物品节点全部或部分连接；所述物品节点与自身关联度最高的预设数量的用户节点全部或部分连接；与所述用户节点关联度最高的预设数量的物品节点，以及与所述物品节点关联度最高的预设数量的用户节点是基于预先训练好的打分模型输出的用户和物品之间的关联度分值确定出的。14.如权利要求13所述的基于图的索引，其特征在于，所述基于图的索引采用二分有向图的结构。15.一种推荐系统，其特征在于，包括：如权利要求13所述的基于图的索引和用户与物品关联度分值打分模型；所述推荐系统，用于通过所述图的索引和所述打分模型，经过单一的检索阶段，输出与用户关联度最高的预设数量的物品的信息；所述基于图的索引中采用所述用户与物品关联度分值打分模型输出的用户与物品之间的关联度分值衡量用户与物品之间的关联度。16.一种计算设备，其特征在于，包括：存储器、处理器及存储于存储器上并可在处理器上运行的计算机程序，所述处理器执行所述程序时实现如权利要求1-6任一项所述的基于图的索引的建立方法，或者实现如权利要求7-8任一项所述的物品推荐的方法，或者实现如权利要求9-11任一项所述的用户与物品关联度分值打分模型的训练方法，或者实现如权利要求12所述的用户与物品关联度分值的确定方法。17.一种计算机可读存储介质，其特征在于，所述计算机可读存储介质存储有计算机程序，所述计算机程序被处理器执行时实现如权利要求1-6任一项所述的基于图的索引的建立方法，或者实现如权利要求7-8任一项所述的物品推荐的方法，或者实现如权利要求9-11任一项所述的用户与物品关联度分值打分模型的训练方法，或者实现如权利要求12所述的
用户与物品关联度分值的确定方法。

技术总结
本发明公开了一种基于图的索引建立方法、基于图的索引和推荐方法及装置。所述推荐系统，包括：基于图的索引和用户与物品关联度分值打分模型；所述推荐系统用于通过图的索引和打分模型，经过单一的检索阶段，输出与用户关联度最高的预设数量的物品的信息；所述基于图的索引中采用所述用户与物品关联度分值打分模型输出的用户与物品之间的关联度分值衡量用户与物品之间的关联度。本发明打破了传统推荐系统多阶段“漏斗”结构的限制，为一个单阶段推荐系统，通过一个阶段就可以从数百万项物品中检索出最终的前K个推荐物品，降低了推荐系统的复杂度，节约了大量的计算资源和训练成本，实现了更高的搜索效率和推荐准确率，保证了推荐系统的推荐效果。了推荐系统的推荐效果。了推荐系统的推荐效果。


技术研发人员：张晓雯 金弘晟 钟灵 施兴
受保护的技术使用者：阿里巴巴（中国）有限公司
技术研发日：2023.03.31
技术公布日：2023/7/25