基于约束推荐的网络可视化分析

张超杰，吴果林,2

(1.桂林航天工业学院 理学院，广西 桂林 541004;2.桂林航天工业学院 广西航空物流研究中心，广西 桂林 541004)

0 引 言

随着网络购物的兴起，如何在成千上万的商品中给出用户需求的产品推荐列表,就成了亟待解决的问题。基于知识的推荐系统[1-3]能够根据用户的明确需求、产品的领域知识、通过推理为用户给出推荐。由于不依赖于用户评分等关于用户偏好的历史数据，故不存在冷启动问题。在已应用的案例中[4-6]，基于知识的推荐技术表现出优异的性能，已成为推荐系统研究的一个重要分支和热点。一般地，基于知识的推荐系统有两种类型[1]：基于约束的推荐[2]和基于案例的推荐[3]。虽然基于知识的推荐技术不依赖用户的评分，但是从复杂网络的观点来看，以往的推荐记录形成一个用户需求与用户意向物品的二部图网[7]。显然这个二部图网络隐藏了用户需求与意向物品的内在联系，也包含了用户之间、物品之间的深层联系。为了能更好地分析这些深层联系，将这些信息用于推荐系统，提高推荐技术的性能，文中对基于约束的推荐过程中形成的用户需求与意向物品的二部图网络进行了可视化分析，主要包括以下几方面的内容：二部图结构可视化，用户、物品节点的度分布，单模网络的社团结构可视化等。

1 基于约束推荐的网络整理与分析

基于约束推荐网络对优质雪茄领域推荐的数据集进行分析研究,以期找到用户和物品之间的一些深层联系。该数据集是由瑞士一个在线雪茄销售商店于2005年10月至2009年5月收集，并由Zanker等[8]整理后应用于约束推荐研究的案例数据集，包含了535个显示用户偏好与用户意向物品的会话。表1显示了其中3个用户会话的数据。

表1 用户偏好与意向物品数据(部分)

表1中，用户变量列表示用户偏好提问，值列表示用户偏好回答，其中用户变量UM010所对应的值表示用户意向物品回答，关于每个用户变量的意义以及用户变量与物品属性之间的约束关系等其他详细信息可参考文献[9]。这些数据堆砌在一起时，如果仅用数据表格或文字的形式来表示，则理解的内容非常有限。易见，上面数据集包含了用户偏好与意向物品的二元关系，为了更直观、更清晰地描述用户偏好与意向物品、用户之间、物品之间的联系，因而将该数据集提炼成一个关于用户偏好与意向物品的二部图网络。为方便计，可以将一个用户的所有偏好看成一个节点(即每个用户看成一个节点)，每个物品看成一个节点，这样得到一个由535个用户偏好节点、141个物品节点以及1 422条边构成的二部图网络，如图1所示。

图1 用户偏好与意向物品网络

图1中黑色表示用户节点，灰色表示物品节点，节点的大小由节点的度来决定。不难发现，图中除了一个物品节点与一个用户节点单独相连外，其余的节点都相互链接且组成一个连通图。另外，从图1也可以看出，多数用户选择一、两个物品，少数用户选择多个物品。也即大部分用户节点只有少数几个链接，某些用户节点却拥有与物品节点的大量链接，在度分布上具有幂律形式。相对而言，物品节点也有度数较大的集散节点，但是度数较少的节点也不是很多，分布相对比较平均，幂律分布不明显。图2显示了用户与物品节点的度分布。

图2 用户与物品节点的度分布

图2中点划线表示用户节点，虚线表示物品节点，实线表示BA无标度网络[10]。图中显示的是500个节点，连边为1的BA无标度网络，记为BA(500, 1)。BA(500, 1)模型有两个重要特性：(1)每次引入一个新的节点，并且连到1个已存在的节点上；(2)一个新节点与一个已经存在的节点vi相连接的概率pi与节点vi的度ki满足如下关系：

易见，用户节点的度分布近似于BA(500, 1)的度分布。如果将每次用户偏好调查看成引入一个新的节点，就能很好地解释度分布近似于BA(500, 1)的度分布。这是因为，多数用户选择一、两个物品类似于BA(500, 1)模型的特性(1)；BA(500, 1)模型随着节点的增加，大度的节点也开始少量出现，而在基于约束推荐的网络中，也有少量用户选择多个意向物品，这与BA(500, 1)模型的第二个特性相吻合。从物品节点的度分布来看，尽管多数用户选择一、两个物品，但物品节点的度为1、2的概率不是最高的，度为3的概率最大，度为4～9的概率都要大于度数为1、2的节点。此外，物品节点的度分布不像用户节点的度分布那样直线下降，而是缓慢下降，且大度节点的数量也比用户节点的数量要多，这体现了一些物品获得用户的普遍爱好。

2 基于约束推荐的网络社团可视化

从上面物品节点的度分布结构可以看出，一些物品被多数用户所喜好，一些物品被部分用户所喜好，而另一些物品被少数用户所喜好，物品节点存在明显的社团属性。因此可以对物品节点进行社团可视化，观察它们的社团结构。然而，物品节点处于一个二部图网络，对物品节点进行社团划分不像单模网络那样可以直接应用现有的社团分割算法。当前，针对二部图网络社团划分有两种思路：一种是直接作用在二部图网络上，设计专门针对二部图网络的社团分割算法或者在原有针对单模网络的算法上进行修改使之能够用于二部图网络的算法，诸如Barber基于模块的算法[11]、Barber与Clark的LPAb算法[12]以及Aikin与Francis的统计模型方法[13]；另一种是将二部图网络映射成单模网络，利用已有的单模网络的社团探测算法进行社团划分。在已知的单模网络的社团探测算法中，比较优秀的算法有Blondel等的Louvain算法[14]、Rosvall与Bergstrom的Infomap算法[15]以及Newman的基于模块的算法[16-17]。鉴于Guimera发现在二部图网络其中一类节点社团探测时，无论是先映射到该类节点后模块最大化社团划分，还是先二部图网络模块最大化社团划分再映射到这类节点上，两者之间没有差别[18]。因此，文中采用先将二部图网络映射到物品节点上，形成一个关于物品节点的单模网络，然后再利用单模网络划分社团的方式来划分物品节点的社团。

考虑一个基于约束的推荐网络G=(U∪I,E)，其中U为用户节点，I为物品节点，E为两者之间的连边。GI=(I,EI)为网络G在物品节点上的映射，GI中的边由网络G确定，当且仅当I的节点vi，vj在U中至少有一个共同邻居节点时，则节点vi，vj之间存在一条边。映射有权重映射与非权重映射两种。在基于约束的推荐网络G中，I中的节点vi，vj有多个共同邻居节点表示有多个用户都喜好物品vi，vj，也即权重映射更能清楚地表达节点之间链接的信息[19]。因此文中选择权重映射作为图G到图GI的映射。设f为图G到图GI的映射，图GI的边(vi,vj)的权重wij定义如下：

wij=|n(vi)∩n(vj)|，i≠j

其中，n(vi)表示节点vi的邻居节点。

利用上述映射方法，将基于约束的优质雪茄推荐网络映射到物品节点上，得到一个由141个物品节点以及2 300条边构成的单模网络，并测得网络的模块度为0.321，是一个具有明显社团结构的网络。应用Louvain算法[14]，计算出物品单模网络可分成7个社团，每个社团的节点数量分布如图3所示。

图3 物品网络的社团数量分布

从图3可知，有1个社团只有1个物品节点，这与二部图网络中只有1个物品和1个用户组成的连通子集相对应，可见Louvain算法能够很好地区分连通分支。除此之外，在其他的社团中，最大的社团含有34个物品节点，次大的社团有31个节点，次小的社团也有12个节点。整个网络除了一个只含单个节点的社团外，聚集程度还是很大的，表现了大社团的特征。图4可视化了社团分类的结果。由图4不难看出，权重较大的边所对应的节点大都归属于同一类，这与定义的节点间权重越大，两个节点包含更丰富的关联信息一致。

图4 物品网络的社团结构

3 结束语

基于约束的推荐系统能够根据用户指定的需求进行个性化的推荐，在Felfernig和Zanker等[2-6,8-9]许多学者的努力下，基于约束的推荐已成为基于知识的推荐系统一个主要的研究方向，并成为一个研究热点。尽管基于约束的推荐不依赖于用户评分等关于用户偏好的历史数据，但以往的推荐记录形成的用户需求与用户意向物品的二部图网络显然包含了许多对推荐有价值的信息。且混合的推荐方法也是当前推荐技术发展的一种趋势[1,20-21]。通过可视化客户购物的历史记录形成的二部图网络，以期发现对推荐有价值的信息，为开发或构造混合的推荐算法提供直观的帮助。分析某在线雪茄销售记录表明：在基于用户需求与用户意向物品的二部图网络中，用户节点的度表现为类似BA(500, 1)的分布；物品节点里含有许多大度的节点，呈现出集结性、社团性特点；对物品节点的社团分析显示，物品节点可以分为7个网络社团，这些社团具有很强的层次性。

社团可视化表明，社团中的节点通过共同用户的多少聚集在一起，因此对于给定物品，可以根据物品社团内给定节点间的度进行排序，然后进行相应的推荐，将此推荐方法加入到基于约束的推荐方法中，构造一个混合的推荐算法，增加推荐的精确度，为推荐算法的设计提供帮助。