客户交互网络挖掘电子商务查询关系

,,This paper is published under the Creative Commons Attribution 4.0 International(CC BY 4.0) license. Authors reserve their rights to disseminate the work on theirpersonal and corporate Web sites with the appropriate attribution.WWW 2018, April 23–27, 2018, Lyon, France© 2018 IW3C2 (International World Wide Web Conference Committee), publishedunder Creative Commons CC BY 4.0 License.ACM ISBN 978-1-4503-5639-8/18/04.https://doi.org/10.1145/3178876.318617418050使用客户交互网络挖掘电子商务查询关系0� 弗吉尼亚理工学院计算机科学系 ◦ WalmartLabs � {bijaya, badityap}@cs.vt.edu ,  ◦ parikshit@neulogic.ai ,{wzhang1, Mohit.Sharma}@walmartlabs.com0摘要0客户交互网络（CINs）是表示和挖掘客户与电子商务搜索引擎交互的自然框架。客户交互始于根据初始产品意图制定的查询的提交，然后是一系列的产品参与和查询改写操作。与产品的互动（例如点击）表明其与客户的产品意图相关。对新查询的改写表明对当前结果的不满，或者客户的产品意图的演变。在会话内部和会话之间分析这些交互，使我们能够发现各种查询-查询和查询-产品之间的关系。在这项工作中，我们首先研究了使用Walmart.com的产品搜索日志开发的CINs的属性。我们观察到，CINs表现出的属性使得纯粹基于结构信息挖掘查询之间的意图关系成为可能。我们展示了如何利用这些关系来进行a）基于意图的查询聚类，b）显著提高性能较差的查询的搜索质量，以及c）识别对其他查询性能影响最大的最有影响力（也称为“关键”）查询。0关键词0客户交互网络，查询关系挖掘，电子商务0ACM参考格式：Bijaya Adhikari � , † , Parikshit Sondhi ◦ , † , Wenke Zhang ◦, Mohit Sharma ◦ , B. Aditya Prakash � . 2018.使用客户交互网络挖掘电子商务查询关系. 在WWW 2018:2018年网络会议上，2018年4月23日至27日，法国里昂。ACM，纽约，美国，10页。https://doi.org/10.1145/3178876.318617401 引言0搜索引擎日志是客户与搜索引擎交互的宝贵资源。日志中的每个搜索会话都以根据初始意图制定的查询的提交开始，然后是一系列的结果参与和查询改写操作。与结果的互动（例如点击）0† 第二作者在WalmartLabs工作时完成了这项工作，第一作者是那里的一个暑期实习生。0信号其与客户意图的相关性。对新查询的改写表明对当前结果的不满，或者意图的演变。因此，我们非常关注从搜索日志中挖掘有意义的信息，并将其用于改进系统的各个方面。在网络搜索领域，这反映在几个先前的工作中[1, 4, 14,22]，这些工作提出了新颖的搜索日志表示，制定了各种日志挖掘任务，并评估了挖掘信息在提供可衡量的系统改进方面的效用。常用的基于图的表示方法包括点击图[23]、覆盖图[1]、查询流图[6]、术语图[35]等。常见的挖掘任务包括识别查询-查询对之间的关系（例如同义词、泛化、特化等）以及查询-URL对之间的相关关系。然后，挖掘到的信息被用于相关查询推荐、搜索质量改进（通过相关URL检索）等应用。然而，在电子商务搜索的背景下，相关文献较少。已经有一些关于分析电子商务搜索日志以研究客户和产品之间关系的工作[13,27]。然而，据我们所知，目前还没有关于各种查询-查询和查询-项目图表示的属性和效用的正式研究。与网络搜索相比，电子商务领域具有几个独特的特点，这使得这样的研究变得有趣。0（1）精确意图：由于电子商务搜索是一种实体搜索，与Web搜索相比，查询意图更加精确。在电子商务中，意图通常可以用查询所期望的一组明确定义的产品属性-值对来表示。（2）狭窄的搜索任务：搜索的目标也是狭窄的，即购买特定的产品，这使得会话连贯。还存在明确的任务完成信号，即将物品添加到购物车或购买物品。（3）类别层次结构：电子商务目录中的产品通常组织成一个明确定义的类别层次结构，这可以作为意图挖掘任务的有用的基准。0这些特征使我们能够定义更好的度量标准，围绕各种图挖掘任务进行大规模评估，而无需使用人工输入。对Web搜索领域的先前论文的回顾表明，这是一个重要的问题，因为评估通常是手动的，因此规模较小。由于这些差异，我们使用“客户互动网络（CINs）”这个术语作为一个总称，用来指代使用电子商务搜索日志构建的各种图，以区别于它们的Web搜索对应物。0Track: Industry WWW 2018, 2018年4月23日至27日，法国里昂18060（a）会话日志（b）查询重构网络（c）物品点击网络0图1：网络创建过程。四个不同会话日志的快照。日志中的每个条目包括查询、物品、参与时间等数据。（b）查询重构网络和（c）从会话日志构建的物品点击网络。0本文中，我们提出了对使用电子商务搜索日志构建的各种图的属性进行形式化研究，重点关注它们在挖掘查询-查询和查询-产品关系方面的实用性。我们提出的基于图挖掘的技术为我们提供了一种补充的方法来发现查询和产品之间的关系，而不直接使用它们的文本内容，使我们的技术与语言无关。我们首先研究使用Walmart.com的产品搜索日志开发的真实世界客户互动网络的属性。我们观察到，与其他真实世界网络（如WWW、社交网络等）相比，CINs表现出显著不同的属性，使得纯粹基于结构信息挖掘查询之间的意图关系成为可能。然后，我们利用CINs进行三种不同的查询关系挖掘任务。我们的主要贡献是：0•实证研究：我们研究了四种不同CINs的结构特性，分别是查询重构网络、物品点击网络、组合点击网络和覆盖网络。•图论问题形式化：我们将基于意图的查询聚类和关键查询挖掘问题形式化为正式的查询聚类和关键查询问题。•算法：我们提出了经过精心设计的高效HubQ-Expansion和Critical-Queries算法来解决查询聚类和关键查询问题。0由于篇幅有限，我们省略了一些引理的证明。02 相关工作0网络分析。[10,16]是最早研究大规模网络宏观结构的学者之一。最近，Zhang等人[39]研究了专业网络的结构，Shen等人[34]对电子商务市场网络进行了实证研究，Zlatic等人[41]研究了维基百科页面之间的超链接网络。社区检测是网络设置中一个研究得较多的问题[20,31]，包括二分网络[3]和异构网络[26]。与我们的工作相关的其他重要任务包括发现网络中的有影响力的节点[9, 24]和测量节点中心性[8,33]。查询图。Beeferman和Berger引入了点击图[4]来对相似查询和URL进行聚类。随后的几项工作0利用点击图在其他应用程序[12, 18,19]中进行了应用，如查询建议、文档搜索、相关反馈和URL注释。Baeza-Yates [1]提出了各种查询关系图的变体，包括覆盖图。Boldi等人[6,7]研究了查询流图，并将其用于相关查询建议。这些与我们的查询重构网络（第3.1节）相似，只是它们还使用查询内容来确定查询-查询边缘的存在。查询关系挖掘。已经采用了许多技术来挖掘查询之间的关系。查询聚类已被用于将相似的查询分组[2, 4,37]。其他一些工作基于关联规则[17]和建模用户[40]。03 数据和应用程序 3.1 我们的网络0在这项工作中，我们使用了从Walmart.com收集的一年期间的会话级客户交互数据。收集的数据包括查询字符串、点击的项目、交互时间等信息。我们从中创建了四个CIN，即查询重构、项目点击、复合点击和覆盖网络（见图1）。查询重构网络。查询重构网络是一个有向加权网络G(Q，E，W)，其中每个节点q∈Q是一个查询字符串。如果查询字符串q2是会话中查询字符串q1的连续重构，则存在一条有向边(q1，q2)。边(q1，q2)的权重w(q1，q2)∈R+表示q1倾向于被重构为q2的频率。为了过滤掉噪声和不重要的数据，我们定义了一些约束条件。只有当查询q1的支持大于δ1且从q1到q2的重构比例大于δ2百分比时，才将边(q1，q2)添加到网络G(Q，E，W)中。对于我们的实验，δ1和δ1都在[0，20]1的范围内。请注意，过滤掉噪声节点和边缘不会影响我们算法的性能，因为我们只关心重要的重构关系。在清除不重要的边缘和节点之后，我们最终的查询重构网络有211万个节点和214万个边缘。项目点击网络。项目点击网络是一个二分加权网络B(Q，I，E，W)，其中Q是查询分区，I是项目分区。查询节点q∈Q是一个查询字符串。一个项目节点01 由于保密问题，阈值的确切值没有公开。0Track: Industry WWW 2018，2018年4月23日至27日，法国里昂18070i  ∈  I是一个项目id。如果客户在给定查询q之后点击项目i，则存在一条边(q，i)∈E。边(q1，q2)的权重w(q1，q2)∈R+表示i倾向于在查询q中被点击的频率。与查询重构网络类似，我们过滤掉不重要的边缘。我们的最终项目点击网络有540万个节点和1840万个边缘。复合点击网络。复合点击网络是一个标准的点击网络，包括查询到查询和查询到项目的边缘。我们通过叠加查询重构网络和项目点击网络创建复合点击网络。结果网络有630万个节点和2050万个边缘。覆盖网络。从我们的项目点击网络中，我们推断出查询到查询的覆盖网络。在覆盖网络中，如果两个查询在项目点击网络中共享一个项目邻居，则它们之间有一条边。查询到项目点击关系是查询意图的明确指示。因此，从点击关系推断出的覆盖网络中的边缘自然地表示两个查询节点之间的相似意图。这些网络往往非常密集。因此，我们对边缘权重施加了额外的阈值。结果图有78.5万个节点和7100万个边缘。03.2 应用0由于我们的CIN捕捉了客户交互数据的各个方面，因此可以用于各种应用，如查询聚类、改进没有参与数据的查询的性能等。可以基于查询内容设计这些应用的方法，但我们在这里的目标是利用网络结构来解决这些问题。与基于内容的方法相比，利用图结构的方法具有语言无关性。因此，我们的方法可以轻松地用于任何使用的电子商务搜索系统，而不管它使用的语言是什么。此外，我们的方法与基于语言/内容的方法是互补的。将这两种方法结合起来是一个有趣的未来工作。在这项工作中，我们专注于利用CIN解决三个不同的应用。应用的描述如下。基于意图的查询聚类：在电子商务搜索中，识别查询意图对返回相关商品至关重要。查询的意图是将查询映射到产品的属性-值对。最终，它被表示为一组产品。产品推荐：在任何电子商务搜索系统中，经常遇到没有客户参与数据的查询。在这个应用中，我们利用查询关系为性能较差的查询推荐产品。关键查询：关键查询是对其他查询性能影响最大的查询。在这个应用中，我们试图利用查询重构网络的结构来识别最关键的查询。我们在后面的章节中对关键查询的概念进行了形式化。在接下来的章节中，我们首先描述了我们的CIN的各种结构特性。然后讨论如何利用它们进行各种应用。04 描述我们的网络0众所周知，大多数真实网络，如WWW、社交网络、互联网、买卖网络等[10,16,34]，都具有特定的结构特性。在本节中，我们研究了我们的CIN的结构特性，并展示了它们与其他网络的不同之处。这些差异对我们的应用有重大影响。04.1 度分布0许多真实网络的特性是无标度的，即入度和出度遵循幂律分布[10,16]。在无标度网络中，节点具有度θ的概率由概率密度函数P(θ)∝θ^(-α)给出。另一个在真实网络中普遍存在的分布是对数正态分布，其中P(θ)=1/√(2πσθ)e^(-(lnθ-µ)^2/2σ^2)[28]。这两个分布都是02πσθe^(-(lnθ-µ)^2/2σ^2)0重尾度分布，即它们具有（近似）线性对数密度。我们首先研究查询重构网络的度分布。查询重构网络的度分布的观察到的经验模式总结如下。0观察1.查询-查询度分布。查询重构网络的入度分布遵循幂律分布，α=2.41，而出度分布遵循对数正态分布，µ=0.12，σ=0.38。0查询重构网络的度分布图如图2所示。入度遵循幂律分布，有多个节点的入度大于1000。另一方面，最大出度为9，与之相比可以忽略不计。需要注意的是，我们的噪声过滤过程在一定程度上减少了查询重构网络中最大出度的值。然而，最大出度的确切值远远小于我们的阈值所要求的值。这表明，虽然很可能许多查询会被一致地重新构造为一个查询，但并不是一个查询反复被重新构造为许多其他查询的情况。这一观察结果与其他网络非常不同，其他网络中的入度和出度往往具有类似的幂律分布[10,34]。我们发现具有最高入度的查询往往是非常通用的查询，例如“运动衫”，“平板电脑”，“电视”等。这些查询的入邻居往往是更专业的查询，例如“带帽绒毛运动衫”，“婴儿运动衫”，“惠普平板电脑”，“HTC平板电脑”等。在二分图项目点击网络B(Q,I,E,W)中，我们分别查看查询分区Q和项目分区I的度分布。我们观察到两个分区的度分布都遵循对数正态分布。同样，我们还观察到覆盖网络的度分布遵循对数正态分布，而复合点击网络的度分布遵循幂律分布。总之，我们发现我们所有CIN的度分布都遵循重尾度分布。重尾度分布表明，虽然存在一些与许多其他查询和项目连接的热门查询，但大多数查询只连接到少数查询和项目。因此，由于相关节点之间的稀疏连接，网络的连接较少。0Track: Industry WWW 2018，2018年4月23-27日，法国里昂18080（a）入度分布（b）出度分布0图2：查询重构网络的入度和出度分布。0在很大程度上保留查询和项目之间的关系。04.2关联性和度相关性0度关联性r ∈ [-1,1]是节点和其邻居之间在度数方面的相似度的度量[31]。形式上，度关联性被定义为连接节点对之间的度数的皮尔逊相关系数。当r =-1时，网络是非关联的（负相关），当r =1时，网络是关联的（正相关）。社交网络被认为是关联的。然而，其他网络，如蛋白质相互作用网络，被认为是非关联的[30]。关于我们的CINS网络关联性的观察如下：0观察2.度关联性。查询重构、项目点击和组合点击网络既不是关联的也不是非关联的，分别为r = -0.02，r = -0.09和r =-0.07，而覆盖网络是关联的，r = 0.22。0图3显示了查询重构和覆盖网络的关联性图。对于查询重构网络，我们观察到高度节点的邻居节点具有非常低的度数。另一方面，高度节点在覆盖网络中主要连接到彼此。对于项目点击和组合点击网络，我们没有观察到任何不对称的模式。覆盖网络的正关联性意味着它不适合查询意图挖掘，因为通常具有不同意图的一般有影响力的查询倾向于相互连接。查询重构网络的度分布和关联性表明网络中存在星状结构的主导地位。这表明不受欢迎的查询通常会被重新构造为相关的热门查询，捕捉查询的意图。04.3连通分量、直径和聚类0许多真实的有向网络被认为具有“蝴蝶结”结构，其中包含一个巨大的强连通分量（SCC）[10,39]。据报道，WWW具有占27.7％的SCC0（a）查询重构覆盖0图3：查询重构和覆盖网络的度与平均邻居度的关联性图。0节点[10]，而Java论坛的社区专业网络具有占节点的12.3％的SCC[39]。在我们唯一的有向网络中，查询重构网络中没有找到“蝴蝶结”结构，最大强连通分量中只有300个节点，而总节点数为211万个。缺少“蝴蝶结”结构的原因可以归因于客户行为。客户不太可能反复将具有明显不同意图的查询重构为具有不同意图的查询。最重要的重构是相关的，因此在两个方向上无法相互到达的图的不同分区。另一方面，Web页面可以任意链接到WWW中的其他页面，不同专业的人可能在Java论坛网络中相互交互，这导致这些网络中形成SCC。大多数真实世界网络都具有“小世界”现象，通常称为六度分隔。非常大的真实网络，如WWW、社交网络等，已知具有较小的直径[10,36]。然而，查询重构、项目点击和组合点击网络的直径分别为94、37和36，相对较大。这表明这些网络中缺少“弱链接”，这意味着客户通常不会连续搜索不相关的查询，也不会对给定查询的任意项目进行重复点击。另一方面，覆盖网络的直径仅为12，这表明覆盖网络不包含代表同质意图的区域。网络的平均聚类系数ACC ∈ [0,1]衡量节点之间的聚类程度。ACC = 0表示网络没有聚类，而ACC =1表示网络聚类良好。对于二分网络，聚类系数是根据同一分区中节点的重叠邻居来定义的[25]。我们计算了所有网络的平均聚类系数，并观察到查询重构、项目点击和组合点击网络的聚类系数非常低，分别为0.05、0.12和0.07，而覆盖网络的聚类系数非常高，为0.76。聚类系数进一步验证了先前的推论，即查询重构、项目点击和组合点击网络适用于查询意图挖掘，而覆盖网络不适用。0行业WWW 2018，2018年4月23日至27日，法国里昂118090表1：CINs属性总结。QQ代表查询重构，Qi代表项目点击，QQI代表组合点击，C代表覆盖网络。ACC代表平均聚类系数。0属性QQ QI QQI C0度幂律对数正态0对数正态幂律对数正态0同配性无无无正0直径94 37 36 120ACC 0.05 0.12 0.07 0.7604.4 总结0在本节中，我们探讨了我们的CINs所展示的各种属性。我们网络的属性表明它们与常见的现实世界网络不同，并且它们保持查询和项目之间的相关性。因此，我们的CINs可以用于各种查询挖掘任务。在接下来的三节中，我们将探讨CINs在查询意图挖掘和产品推荐中的应用。05 应用1：基于意图的查询聚类0在电子商务搜索中，识别查询意图对于返回相关项目至关重要。然而，在实践中，由于很少的参与数据，人们会遇到许多具有模糊意图的查询。识别此类查询意图的一种方法是将它们与已知意图的其他查询进行聚类，并利用聚类的一般意图为参与数据较低的查询推荐产品。基于意图的查询聚类在许多潜在应用中被证明是有用的，如查询推荐，分类等，无论是在Web还是电子商务搜索中[2，4]。由于我们的查询重构网络捕捉到了重要的重构关系，我们建议利用查询重构网络来对具有相同意图的查询进行聚类。05.1 问题形式化0回想一下，查询重构网络是一个查询到查询的重构网络。因此，查询重构网络中的相邻查询彼此相似。因此，直观上，查询重构网络中的一个社区预计由具有相似意图的查询组成。因此，查询重构网络中基于意图的查询聚类问题是有充分依据的。该问题可以如下所述：0非正式问题1. 查询聚类给定：一个查询重构网络G(Q，E，W)，一个整数k∈Z。找到：一个Q的k个分区，使得每个分区包含具有相同意图的查询。0为了形式化非正式问题1，必须解决两个问题（i）如何根据图结构定义意图？（ii）如何根据意图度量两个查询之间的“接近程度”？为了回答第一个问题，我们依赖于经验研究。如第4节所述，具有高入度的节点往往是广义的。0广义查询，如'tv'，'phone'，'sweater'等，大多数特定查询都会被转换为这些广义查询，因此这些在查询重构网络中具有高入度节点的广义查询是代表意图的好候选。为了回答第二个问题，我们看一下查询重构网络中的边关系。查询重构网络中的每条边都代表着重要的重构。因此，从一个查询到另一个查询的较短的重构路径是相似意图的一个很好的指示，反之亦然。因此，这两个问题（i）和（ii）可以通过图结构来回答。接下来，我们利用两个图属性（i）高入度节点和（ii）最短路径）来形式化非正式问题1。给定一个查询重构网络和不同意图的数量k，我们的目标是发现k个不相交的分区{C1，C2，...，Ck}。由于高入度节点很好地表示了意图，我们通过寻找这样的节点集合S = {s1，s2，...，sk}和分区C ={C1，C2，...，Ck}来形式化问题，其中Ci是由si表示的意图的分区。此外，由于短的重构路径表示查询之间更接近的意图，我们要求Ci中的节点与si之间的距离较短。让θi(v)是v的入度，d(a，b)是两个节点a和b之间的最短跳数，s(v)是S中的节点，使得节点v和s(v)属于同一个分区（即s(v)是v所属社区的种子节点）。现在，我们的正式问题，纯粹基于网络结构，可以如下所述：0问题1. 给定一个查询重构网络 G ( Q ,  E ) 和一个整数 k，确定一组一般查询节点 S � =  { S 1 , S 2 , ..., S k  } 和一组划分 C �=  { C 1 , C 2 , ..., C k  } ，使得 S i  ∈  C i 且0S � , C � =  arg min S , C J ( S , C )  =  argmin S , C0�� �0v  ∈ V d ( v ,s ( v ))0� ��0s  ∈S0θ i (s )0��05.2 方法0由于我们的原始问题需要划分，传统的社区检测方法是我们问题的自然基准。因此，我们使用了一种基于模块性的现有社区检测方法[32]，一种重叠社区检测方法和一种专门针对问题1设计的启发式方法作为基准方法。简要描述如下：0•  Louvian:我们使用流行的Louvian方法来最大化查询重构网络的模块性[5]。 •BigClam: 它是一种基于二分配模型的重叠社区检测方法[38]。 •LouvianSmall:大多数查询与其他查询共享意图。因此，我们修改了Louvian算法的第一阶段，以生成较小的社区。 •  Star:由于查询重构网络由星状结构主导，我们通过将高入度节点与其邻居聚类来生成星状社区。这种方法旨在选择高度节点作为社区中心。因此，它是问题1的一种启发式方法。0Track: Industry WWW 2018, 2018年4月23日至27日，法国里昂Composite ClickCover0.050.540.09ComLouvian0.070.330.12118.7LouvianSmall0.390.080.130.73Star0.380.120.183.01BigClam0.140.210.1717.7HubQExpansion0.370.140.200.54,δ PC qi ,PC qj18100我们运行Louvian算法来对Cover和Composite Click网络进行聚类。由于CompositeClick网络是一个异构网络，我们还使用了修改版本的Louvian算法来最大化在异构网络上定义的复合模块性[26]。我们将这种方法称为ComLouvian。虽然传统的社区检测方法是问题1的自然基准，但它们不会直接优化给定的目标，因此它们可能不是最优的。我们的主要思想是利用查询重构网络的结构特性来解决问题1。我们利用以下观察结果：（a）查询重构网络中超过一半的节点位于巨大的弱连接组件之外，（b）关联性图（见图3）显示高入度节点之间很少有边，最后，（c）查询重构网络具有较低的聚类系数和较长的直径，这表明具有不同意图的查询是相互分离的。基于这些观察结果，我们提出了我们的算法HubQEx- pansion（Hub-QueryExpansion），用于在电子商务查询重构网络中聚类具有相似意图的查询。属性（a）表明在巨大连接组件之外存在大量的查询，因此我们在每个连接组件中对查询进行聚类。我们按比例分配要在每个连接组件中找到的社区数量，即对于G中的每个连接组件G i (Q i ,  E i , W i ) ，要找到的社区数量设置为 k i  = | Q i  |0| Q  | . 根据属性（b），我们将组件 G i 中入度最高的 k i个节点分配给它们自己的社区。将高度节点分配给它们自己的社区是合理的，因为它们往往是一般查询，而且一般查询如“电视”和“毛衣”具有不同的意图是很直观的。最后，（c）表明具有不同意图的查询是相互分离的。因此，我们使用广度优先搜索扩展社区。我们继续扩展社区，直到连接组件中的所有节点都被分配到一个社区为止。完整的伪代码在算法1中。问题1的目标包括两个项 � v  ∈ V [ d ( v , s ( v ))] 和 � s  ∈ S � 10�。直观上，算法1试图通过将高入度节点分配为聚类中心来优化目标的第二项，并通过将节点分配给与最近（最短路径）聚类中心相同的社区来优化第一项。由于我们观察到高入度节点倾向于与许多查询之间存在短路径，并且彼此之间相互分离，我们期望从算法1得到的解决方案能够最小化目标中的两个项，并得到问题1的一个好的解决方案。0引理5.1。算法1的时间复杂度为O(m +n)，其中m是边的数量，n是节点的数量。05.3 实验0度量标准。衡量方法在问题1中最小化目标的能力可以展示它们解决问题的能力。然而，它并不能表明社区在意图方面的聚类效果如何。由于大多数查询没有相关项目的集合，我们将从准确的标记器学习到的产品类别视为查询意图的代理。直观上，如果两个查询有共同的关联项目，它们也应该有共同的产品类别。因此，产品类别是一个很好的代理0算法1 HubQExpansion0要求：查询重构网络G(Q, E,W)，社区数量k。确保：Q的k个不相交的分区。1：划分P = �2：对于G中的每个连通分量Gi(Qi, Ei, Wi)0| Q  | 4: 临时集合S = � 5: 对于Q i 中入度最高的ki个节点中的节点v 6: S = S ∪ { v } 7: 使用BFS将Q i中的节点分配给S中的节点08: P  =  P  ∪  S9:  返回  P0表2：Louvian在查询重构、CompositeClick和Cover网络上的性能。表格显示了基于类别的AIH，AIS和F1。Louvian在查询重构网络上的性能最好。0网络 AIH cat AIS cat F 1 cat0查询重构 0.26 0.11 0.150表3：查询聚类中各种方法的性能。表格显示了AIH，AIS和F1cat。还显示了最终目标值J。HubQ-Expansion优于所有基线方法。0方法 AIH cat AIS cat F 1 cat J (× 10 6 )0代表意图。我们获取了267K个查询的类别，用于评估所有的方法。一个社区的分类同质性是衡量其群体意图同质性的一个指标。为此，对于一个社区C，我们定义其社区意图同质性CIH为节点对的比例0| C  |×| C − 1 |，其中PC(q i)表示与节点q i相关联的类别，δ(a, b) = 1如果a =b，否则为0。注意，对于CIH，我们只包括具有类别信息的节点。然后，我们计算分区P的平均意图同质性AIH cat，即AIH cat = � C ∈ P CIH(C)0| P  | . AIH cat 评分为0表示分区中的社区是异质的，而AIH cat评分为1表示社区是完全同质的。AIH cat有一个缺点，即较小的社区往往得分较高。因此，为了克服这个问题，我们还测量了一个类别在多少个社区中被表示。理想情况下，我们0Track: Industry WWW 2018, April 23-27, 2018, Lyon, France18110我们希望每个类别都在一个社区中表示。因此，我们将一个类别的平均逆传播AIS cat定义为10传播，其中传播被定义为类别所在的平均社区数。AIS cat分数为1表示每个类别都在一个社区中表示，而接近0的分数表示类别分布在多个社区中。最后，我们计算F1 cat 作为AIH cat 和AIS cat的调和平均值。性能。首先，我们在查询重构、复合点击和覆盖网络上运行Louvian算法。结果总结如表2所示。结果显示，查询重构得到的聚类效果最好，表明它是最适合查询聚类的网络。接下来，我们在查询重构网络上运行所有方法，并在复合点击网络上运行ComLouvian算法。首先，我们根据问题1的目标计算方法的性能。结果如表3所示。如预期的那样，HubQ-Expansion在问题1的目标上胜过所有基准方法。接下来，我们计算了上述基于意图的度量指标。结果总结如表3所示。观察到，HubQExpansion胜过所有基准方法。Louvian表现良好，表明传统的社区检测方法确实适用于问题1。LouvianSmall的性能较差，表明人为地创建较小的聚类会阻止好的聚类形成。NaiveStar启发式方法表现良好，因为查询重构网络中的社区以“热门”查询为中心。然而，HubQExpansion胜过所有方法，因为它利用查询重构网络的独特结构来找到具有相同意图的社区。06 应用2：产品推荐0提高没有客户参与数据的查询的搜索质量是一项具有挑战性的任务。在本节中，我们提出利用复合点击网络将产品与表现不佳的查询关联起来，并评估这种方法是否确实提高了没有参与数据的查询的搜索质量。06.1 问题和方法0在这个任务中，我们探索基于复合点击网络进行的产品推荐是否能够帮助提高表现不佳的查询的搜索质量。我们以当前的Walmart.com产品搜索引擎作为基线，并确定了表现不佳的查询。选择的标准是点击率在最低的10%百分位数以及转化率，定义为（#有订单的查询数）0#Queries），为0。对于变体，我们使用了一种基于随机游走的方法，类似于[12]，不同之处在于我们的网络是有向的（我们将查询到项目的链接视为有向链接），而且项目没有出边，使其成为汇节点。我们计算了我们的复合点击网络的非归一化边权重，计算方法如下：0查询q1到q2的边：w(q1,q2)=c(q1,q2)0c(q1)∙查询q到产品i的边：w(q,i)=c(q,i)0c(q)0其中，c(q1,q2)表示q1被转化为q2的次数，c(q1)表示q1出现的次数，c(q,i)表示查询q中产品i被点击的次数。我们进一步通过从基础节点q出发的所有出边的权重之和对每个有向边(q,x)的权重进行归一化处理，其中x可以是查询或产品。为了为某个查询q进行产品推荐，我们从节点q开始，权重为1，并通过执行随机游走迭代在图上传播权重。经过多次迭代（通常50次足够），部分权重会落在产品节点上。然后，我们选择权重最高的5个产品作为q的推荐。我们的变体排序方法将这些推荐产品注入到查询q的前10个搜索结果中，将一些原始结果降低到第10个位置以下。06.2 实验0为了评估，我们随机选择了136个性能较差的查询样本2。通过从控制组和变量组中获取每个查询的前10个结果，创建了一个查询-产品对的数据集。然后，要求专家电子商务分析师为每个查询文档对分配一个0-4之间的相关性评分，其中4表示极其相关，0表示不相关。我们观察到，基于我们的推荐的变体表现得更好，平均NDCG@10[21]提高了34%（基线NDCG10: 0.439，NDCG10:0.588）。在136个查询中，有99个查询得到了改进，而31个查询得到了降低。从实际角度来看，这些降低并不会造成损害，因为这些查询的转化率已经很低。我们的在线A/B测试评估进一步证实了这一观察结果，显示点击率提高了5.8%，转化率提高了6.9%。07 应用3：关键查询0在前一节（第6节）中，我们展示了一个查询的参与数据可以被利用来提高其他相关（通过重构关系）查询的性能。在这种情况下，一个自然的问题是哪些查询对其他相关查询的性能有最大的累积影响？我们将这些查询称为“关键查询”。挖掘关键查询对于提高搜索系统的整体性能非常重要。通常在手动策划等过程中，通过手动改进搜索结果来提高搜索质量，选择出现最频繁的查询。然而，这种方法在整体性能上的改进是次优的，因为这些最频繁的查询不一定能提高其他查询的性能。另一方面，按定义，关键查询对相关查询的性能影响最大。因此，正确地识别关键查询对于策划过程将会带来更好的性能改进。注意，关键查询可以在电子商务中用于许多其他任务，如测量搜索系统的性能、识别广泛的搜索类别等。由于我们的查询重构网络很好地捕捉了重构关系，我们建议通过利用查询重构网络来挖掘关键查询。02 查询数量基于可用的众包预算获得。0Track: 2018年4月23日至27日，法国里昂举办的工业互联网18120(a) 交集 (b) ϕ(T) (c) 基于物品相关性的性能0图4：(a) 算法2返回的前k个关键查询与其他基线的交集。(b) 我们的方法在 ϕ(T) 方面优于所有基线。(c)根据可用性指标，我们的方法表现最佳。7.1 问题建模0为了明确选择最关键的查询的问题，我们需要正确地对查询重构过程中的客户行为进行建模。我们将查询重构中的客户行为建模为在查询重构网络上发生的离散时间动态过程。我们称之为随机用户导航（RUN）模型。RUN模型：在电子商务搜索系统中，客户（用户）向搜索系统提交任意查询。显示与查询相关的项目列表。根据搜索结果的满意度、产品相关性等许多因素，客户可能决定提交另一个查询或退出搜索系统。这个过程实际上可以看作是在查询重构网络 G(Q, E, W)上的离散时间概率动态过程。给定当前节点v，我们按照以下步骤进行：0(1) 以概率 p t 终止该过程 (2) 以概率 1 - p t 继续该过程，并从当前节点 v跳转到查询节点 u，其中 (v, u) ∈ E，概率为 p j = w(v, u) / ∑(v, a)∈E w(v, a)0该过程从均匀随机抽样的查询节点Q中的任意查询节点开始。注意，RUN模型的一个实例会产生一系列查询，我们称之为“重构日志”。现在，让T成为一组节点。我们将ϕ（T）定义为RUN模型的任意实例经过T中至少一个节点的概率。经验上，ϕ（T）是通过RUN模型的重复产生的重构日志中T中至少一个节点出现的次数的比例。备注。由于PageRank的随机浏览模型[33]和我们的RUN模型都模拟了网络上的随机行走者，它们看起来很相似。然而，PageRank的随机浏览模型与我们的RUN模型不同，因为它没有终止概率的概念，行走者可以跳转到网络中的任何节点。足够长的时间后，每个节点v ∈Q都会被访问，因此在随机浏览模型下，对于任何集合T，ϕ（T）始终为1-这在RUN模型下并非如此。RUN模型与级联样式模型（如IC[24]）也不同，因为在RUN模型中一次只访问一个节点，而级联模型中的“传染”传播可以一次性感染多个节点（取决于上一个时间步中的其他“感染”节点）。0定义了RUN模型和ϕ（∙）之后，我们可以正式陈述我们的关键查询识别问题如下：0问题2.关键查询 给定：查询重构网络G（Q，E，W），预算k ∈Z。找到：一组节点T� = {q | q ∈ Q}，使得|T�| = k且0T� = arg max Tϕ（T）07.2方法0问题2是NP难问题（我们可以从SetCover问题进行约简；由于空间限制，省略了证明）。虽然以高效的方式最优解决问题2具有挑战性，但可以使用各种中心性度量或基于查询日志的启发式方法来识别关键查询。其中一些方法可能包括以下内容： •MostFreq（MF）：在此方法中，我们从创建查询重构网络的相同数据中选择频率最高的查询。 •SessionFreq（MS）：在此方法中，我们选择出现在大多数会话中的查询。 •PageRank（PR）：我们选择查询重构网络上具有最高PageRank[33]的节点。 •EigCentrality（EigC）：我们选择查询重构网络上具有最高特征向量中心性[8]的节点。上述方法都不能直接解决问题2。因此，我们寻求具有性能保证的快速算法。结果表明，ϕ（∙）是次模的[24]。如果函数f（∙）将一个集合映射到一个实数，则称其为次模函数，如果它满足递减回报性质，即f（A∪{v}）-f（A）≥f（B∪{v}）-f（B），对于任何元素v和集合A �B。接下来，我们证明ϕ（∙）是次模的且单调的。0引理7.1.ϕ（∙）是次模的且单调的。证明。在RUN模型中，节