0 引言

互联网技术的飞速发展以及电子商务的广泛应用, 信息过载问题变得日益严重^[1-2].为了分析用户偏好以及有针对性地向用户进行商品推荐, 大量的推荐算法及相关系统应运而生.从用户角度出发, 有上下文感知推荐系统^[3]、移动推荐系统^[4]等, 这些推荐系统大多是根据用户的偏好进行商品推荐.然而从商家的角度考虑, 商家更希望的是将销售产量较低而且没有普及的产品推广给用户, 实现多元化商品战略. "长尾理论"完美地解释了这一问题:如果商品的流通方式及商品存量足够多, 普及度较低的商品所带来的收益较热门商品更多, 即商品的销售量不在长尾分布曲线上的头部, 而是在更需要被推广的长尾尾部.因此位于尾部的商品有更大的价值挖掘空间, 位于尾部靠前的商品有较大的价值潜力而且普及度也较高, 有进一步被推广的价值^[5].以电影为例, 较为流行的电影都附有动作、喜剧、科幻等特性, 但是纪录片并不带有这些属性, 所以大多数人认为纪录片枯燥无味, 只有少数那些热爱历史的人会关注它, 因此纪录片的普及度并不高.如果将这种电影推广给更多的消费者, 让更多的消费者去了解历史, 关注历史, 从而喜欢上纪录片, 此时纪录片就不再是"偏门电影".由此可见, 对小众中的大众商品进行进一步挖掘是能够发现其原始价值的.出于这一目的, 本文着重研究发掘小众商品中的大众并推荐给用户, 从而提高位于尾部商品的销量并让商品销售多样化, 同时结合幂律对推荐算法进行了改进.

众多领域存在幂律分布现象, 其遍布于经济学、地理学、计算机科学等领域.对幂律分布研究做出重要贡献的是Zipf和Pareto. Zipf发现单词出现的次数与它的频率排名常数成反比; Pareto通过分析社会财富分布现象, 发现大部分财富掌握在少数人手里, 即80-20准则. Zipf定律和Pareto定律是幂律分布的典型代表^[6].

已有的推荐系统利用Top-$k$查询对用户进行推荐^[7-9].在空间数据库领域中, 已经有很多研究工作者进行了$k$NN ($k$-Nearest Neighbor)、RNN (Recurrent Neural Network)、R$k$NN (Reverse $k$-Nearest Neighbor)等相关技术的研究.反向最远邻(RFN)作为一个新颖的查询技术对它研究的人相对较少, 而RFN查询可以有效解决最弱影响集等问题^[10-12].由于商品信息的复杂多样性, 这些推荐系统为了筛选出符合用户偏好的商品需要做大量的信息处理工作.由以往文献可知, 到目前为止还没有人提出将RFN与推荐系统相结合的应用, 基于以上考虑, 本文提出将RFN与推荐相结合代替传统的基于Top-$k$查询的推荐.

本文的主要贡献如下.

(1) 总结了传统的偏好预测模型, 提出了基于新标准的专家偏好预测机制以及专家用户提取算法.采用标签连续化的策略将商品和用户映射到空间.

(2) 由于长尾分布是一种典型幂律分布, 提出的推荐算法主要是为了有效缓解"尾大"现象.为寻求幂律分布中的某一阈值点, 将头部忽略, 重点研究尾部的商品, 将原始庞大的商品信息进行范围缩减, 即对查询工作所需要的原始数据集进行范围缩小, 间接地减少了搜索查询算法的时间及空间耗费.

(3) 将RFN的空间数据库查询思想与推荐系统相结合, 对用户进行$k$个小众商品的推荐, 提出了基于RFN用户偏好推荐(RFN-Based User Preference Recommendation, RUPRA)算法.

本文后续结构是:第1节介绍相关工作; 第2节形式化一系列相关问题; 第3节介绍专家用户的提取、商品标签属性连续化、如何进行幂律的判断, 以及求解相关参数和利用幂律优化查询空间, 构建基于RFN的推荐系统; 第4节是实验与分析; 第5节是结论.

1 相关工作 1.1 偏好预测

Goldbeg等人提出的协同过滤(Collaborative Filtering, CF)方法^[13]开创了推荐系统的新思路, 大多数推荐系统对于用户偏好预测一般都采用这种协同过滤的方法. Sarwar等人提出了基于物品的协同过滤算法^[14], Peng等人对传统的协同过滤算法进行了改进^[15].所谓协同过滤主要是通过相似度计算, 将相似度较高的对象来近似代表目标对象的偏好属性.协同过滤主要分为基于用户的协同过滤^[16](User-Based Collaborative Filtering, UBCF)和基于物品的协同过滤^[17](Item-Based Collaborative Filtering, IBCF). UBCF的基本思想是寻找与目标用户相似度最高的用户群体, 通过分析此用户群体的偏好对目标用户进行推荐. IBCF就是寻找与目标用户喜欢的物品相似的物品, 然后把相似的物品推荐给目标用户. Vozalis等人通过实验对比了这两种协同过滤策略^[18], 发现不管是UBCF还是IBCF都涉及相似度的计算.在基于用户的推荐系统中, 用户之间的相似度计算公式为

$ \begin{equation} {\rm sim}(u, e)=\frac{\sum\limits_{s\in S_{u, e} } {(R_{u, s} -\overline {R}_u)(R_{e, s} -\overline{R}_u )} }{\sqrt {\sum\limits_{s\in S_{u, e}} {(R_{u, s} -\overline{R}_u )^2\times \sum\limits_{s\in S_{u, e}} {(R_{e, s} -\overline{R}_u )^2} } } }, \end{equation} $

其中, $S_{u, e}$表示任意用户$u$和$e$共同评分的项目, $R_{u, s}$表示任意用户$u$对指定项目$s$的评分, $R_{e, s}$表示任意用户$e$对指定项目$s$的评分, $\overline{R}_{u}$表示用户$u$对项目的平均评分值.

通过相似度计算可以得到与目标用户相似的用户集合.基于物品的协同过滤的相似度计算方法和上述类似, 在此不再赘述.

1.2 商品标签属性连续化

目前, 基于标签的推荐系统在各类网站尤其是社交、音乐、视频等网站得到了广泛应用.例如将标签与社会关系相结合应用于微博的推荐^[19], 通过标签对物品的内容、特征进行准确描述.文献[20]是基于标签个性化的推荐研究, 提出了融合标签流行度、时间权重以及矩阵分解的推荐算法.本文推荐算法在对用户进行个性化推荐时, 需要用户及推荐物品的标签属性信息, 例如推荐电影, 电影是有类别的, 如动作片、喜剧片、爱情片等这些是电影所具有的标签.在进行标签标记时, 某一物品是否带有某个属性通常以0, 1表示, 比如电影Star Wars是否为动作片, 1表示该电影属于动作片, 0表示该电影不是动作片, 没有动作片的特点; 但是0, 1离散化表示不能体现商品附有某种属性的程度, 因此应该将商品属性进行标签值连续化.比如Star Wars电影的Action属性值为0.5 (一般用0$\sim $1之间的数值表示).这种连续属性标签表示法有如下优点.

(1) 可以表示某种商品附有某种属性的程度, 不再是单一选择的形式, 当用户想要附带某种属性的商品时, 选择了该属性标签为1的商品, 如果用户体验之后感到这种属性并不明显, 这种推荐效果可能就有点差强人意.运用了连续化的标签后, 可以很直观地了解该商品带有某种属性色彩的程度, 便于用户更好地进行选择.

(2) 将属性标签连续化后, 可以将商品抽象为空间中的点, 例如某种商品有$n$种属性, 可以将该商品抽象为$n$维空间中的点, 每种属性值即为每个坐标轴上的度量.这有利于将空间中的搜索查询算法运用到推荐系统中.

1.3 带空间属性的幂律求解

目前许多研究工作者在自然科学现象中发现了众多服从幂律分布的现象, 例如Faloutsos等人研究了互联网的拓扑结构, 并且发现了互联网路由节点间的度数服从幂律分布^[21]; Clementi等人探索发现了意大利居民收入呈现幂律分布的态势^[22]; Newman等人将Zipf定律和Pareto定律和幂律进行了比较与总结^[23]; Clauset等人利用经验模型对幂律的相关参数进行了预估评判^[24].本文主要是利用幂律进行原始数据集的过滤, 将过滤后的数据集根据其属性进行空间化处理, 然后利用空间查询策略进行筛选, 选出符合用户偏好的推荐结果.

近年来空间距离查询策略已经被大量研究, 这些查询可以被概括为以下几种类型:最近邻居和$k$最近邻居; 反向最近邻和反向$k$最近邻; 反向最远邻.大多数科研工作者研究的是最近邻居和$k$最近邻居、反向最近邻和反向$k$最近邻; 相比之下, 研究RFN的人员较少.比较著名的有Yao等人最先提出的判定RFN查询的方法^[10], 例如PFC (Progressive Furthest Cell)算法和CHFC (Convex Hull Furthest Cell)算法; Liu等人提出的基于安全域的PIV算法^[11], 这在某些情况下避免了冗余的查询, 提高了算法执行效率; Wang等人提出了反向$k$最远邻相关定义以及进行了R$k$FN算法的研究^[12]; Li等人对空间中的动态移动对象的RFN进行了深入研究, 并且利用TPR-tree进行修剪, 提出了移动对象的动态反向最远邻算法^[25].本文则是将RFN查询与推荐系统结合, 构建不同于Top-$k$的推荐系统.

2 问题描述

传统的基于用户的协同过滤算法是通过用户–项目评分表来计算用户相似度, 如果用户集的数量巨大, 对于新加入的用户需要计算和每个老用户的相似度就变得十分复杂.如果能选出一批有代表性的用户, 当新用户加入时, 首先与这些代表性的用户计算相似度, 然后再进行偏好预测可以减少计算时间.本文用专家用户来代表这些代表性用户.

定义1   (专家用户)在推荐系统^[26]中, 当用户满足以下3个条件, 这样的用户被称为专家用户.

(1) 用户在其擅长领域相对于大部分用户有更高的活跃度, 并且会对该领域给出更多的评价.

(2) 用户相对于大部分用户有更高的专业性, 并且他们给出的评价一般比较准确.

(3) 用户在社交领域相对于大部分用户有更高的声誉值, 即有较多信任他们的用户.

定义2   (属性专家用户)对于用户$u$所有评价记录的商品, 其中含有属性标签$t$的个数不少于$s$个, 此时用户$u$为$t$属性的属性专家用户, 其中$s$的大小为可变参数, 用于表示属性专家用户的最低可靠度, 可根据不同应用场景进行设置.

计算用户$u$和专家$e$之间相似度的公式为

$ \begin{align} {\rm sim}(u, e)=\frac{\sum\limits_{s\in S_{u, e} } {(R_{u, s} -\overline {R}_u )(R_{e, s} -\overline{R}_u )} }{\sqrt {\sum\limits_{s\in S_{u, e} } {(R_{u, s} -\overline{R}_u )^2\times \sum\limits_{s\in S_{u, e} } {(R_{e, s} -\overline{R}_u )^2} } } }\times \frac{2\vert I_{u, e} \vert }{\vert I_u \vert +\vert I_e \vert }, \end{align} $

(2)

其中, $\vert I_u \vert $和$\vert I_e \vert $分别表示用户$u$与专家$e$的评论项目集合.用户$u$对项目$i$的预测评分值为

$ \begin{align} R_{u, i} =\overline {R}_u +\frac{\sum\limits_{e\in E_{{u}, k} } {[{\rm sim}(u, e)\times (R_{e, i} -\overline {R}_e)]} }{\sum\limits_{e\in E_{u, k} } {\vert {\rm sim}(u, e)\vert } }, \end{align} $

(3)

其中, $\overline{R}_u $和$\overline {R}_e $分别表示用户$u$和专家用户$e$对评价过的所有项目的评分平均值, $E_{u, k}$表示与用户$u$相似度最高的$k$个专家用户集合.

在计算用户与专家的相似度之前需要知道哪些用户是专家用户, 因此本文提出如下几个衡量标准.

(1) 活跃度:普通用户和专家用户的区别之一在于专家用户在某些方面的专业知识是非常丰富的.所以专家用户的评价是比较公认及准确的, 用户的活跃度与用户评价的商品数量成正比.计算用户的活跃度的公式为

$ \begin{align} {\rm ACT}(u)=\frac{N(u)}{N(U)}, \end{align} $

(4)

其中, $N(u)$表示用户$u$的评价次数, $N(U)$表示所有用户的评价次数.

(2) 准确性:普通用户和专家用户的另一个区别在于专家用户对商品评价的准确程度通常高于普通用户, 即专家评分与物品的平均评分几乎相同.为了衡量用户评分的准确性, 首先需要知道物品$i$的平均评分, 如果物品$i$被$N$个用户评分过, 则物品$i$的平均评分可由公式

$ \begin{equation} \overline {R}_i =\frac{1}{N}\times \sum\limits_{u=1}^N {R_{u, i} } \end{equation} $

(5)

得出, 则用户对每件商品的评分偏差为$\vert R_{u, i} -\overline {R}_i \vert $.为了将评分偏差归一化以便更好地分析, 本文做如下处理, 即

$ \begin{align} D(R_{u, i} )=1-\frac{\vert R_{u, i} -\overline {R}_i \vert }{\sum\limits_{j=1}^N {\vert R_{u, j} -\overline {R}_j \vert } }. \end{align} $

(6)

将式(6)得到的评分偏差取平均值, 并将其用来表示用户评分的准确性, 公式为

$ \begin{align} C(u)=\frac{1}{M}\sum\limits_{i=1}^M {D(R_{u, i} )} , \end{align} $

(7)

其中$M$是用户的评价次数.

(3) 声誉值:普通用户和专家用户的第三个区别在于专家用户在整个社交网络中具有较高的声誉, 即有信任他们的用户较多.用信任用户$u$的用户数量与有最多信任者用户的信任用户数量的比值来表示用户$u$的声誉值, 公式为

$ \begin{align} R(u)=\frac{M_u }{M_{\max } }. \end{align} $

(8)

有了以上3个衡量标准, 本文采用公式

$ \begin{equation} {\rm EVAL}(u)={\alpha \times {\rm ACT}(u)}+\beta \times C(u)+\gamma \times R(u) \end{equation} $

(9)

来评估专家用户.式(9)中$\alpha +\beta +\gamma =1$, $\alpha $、$\beta $和$\gamma $分别表示各部分的权重.

对于用户集合$U$, 专家集合$E=\left\{ {u\vert \forall u\in U, {\rm EVAL}(u)>t} \right\}$, 其中$t$表示阈值, 当EVAL($u)>t$时, 用户$u$才可被认定为专家用户, 因此可以通过控制阈值$t$来控制专家用户的数量.

假设$D$表示$n$维空间中的数据集合. RFN技术关注的是欧氏距离即$\left\| {p-q} \right\|(p, q$为空间中任意两点).

定义3  任意点$q$关于集合点$P$的最远邻居: FN$(q, P)=p$使得$p\in P$, 对于$\forall p'\in P$和$p'\ne p$, $\left\| {p-q} \right\|\ge \left\| {p'-q} \right\|$.

定义4  $q\in Q$, RFN是数据集合$P$中的点相对于查询集合$Q$以$q$为最远邻居的集合点, 即RFN$(q, Q, P)=\left\{ {p\vert p\in P, {\rm FN}(p, Q)=q} \right\}$.

表 1所示为本文所用到的符号及其定义.

3 基于RFN的推荐方法

第2节的定义1对专家用户进行了定义, 本节将进行专家用户提取以及对商品属性进行连续空间映射化.

3.1 专家用户提取算法

对于新用户, 系统并不知道其偏好, 只能通过协同过滤的方式找到其最近的邻居, 通过其最近邻居的偏好来预测该新用户的偏好.

本文对新用户进行相似度计算, 寻求$k$最近邻居时先与专家用户进行相似度计算; 然后根据专家用户对新用户进行预测评分.如果没有专家用户或者专家用户数量不足时, 将缺少的邻居到普通用户中去寻找, 然后根据预测评分模型给出新用户的预测评分, 从而降低系统进行相似度计算的时间.

3.2 标签属性连续化算法

对商品属性标签进行连续化处理时, 本文采用属性专家用户的方式将离散化的标签变为连续化的标签.为了更清楚地展示本文所做的工作, 主要以电影为例进行说明.

3.2.1 属性专家用户的获取

在推荐系统当中, 当拥有了用户$-$物品的评分矩阵之后, 应该如何提取属性专家用户呢？下面结合电影推荐系统对专家用户提取算法(Expert Extraction Algorithm, EEA)进行详细说明. EEA见算法1.

算法1: EEA
输入:用户$-$物品评分矩阵$R$, 用户$U$
输出:专家用户集合EU
1. EU$\leftarrow \varnothing $//将EU集合初始化为空
2. for $i\leftarrow $0 to U.numberdo
3.   ACT$\leftarrow $act$(u)$//计算用户$u$的活跃度
4.   accuracy_rate$\leftarrow E(u)$//计算用户$u$的准确度
5.   if EVAL(u)$>t$//如果用户最终得分大于阈值
6.     EU.add$(u)$//将用户$u$加入到专家集合EU
7.   end if
8. end for
9. return EU//专家用户集合返回

首先需要获取用户的类型矩阵UTM, 通过UTM对用户进行详细的定义. 表 2截取了评分矩阵中部分关于用户A (UserA)的评分记录, UserA对表 2中的5部电影有过观赏并给出了相关评价.结合离散化电影标签属性, 可以得到用户的类型矩阵UTM, 如表 3所示.

对表 3而言, Total这一行即为UserA对类型的偏好向量UTV, 如果在电影推荐场景中, 所设置的最低属性专家用户可靠度$s$为3的情况下, 那么UserA为属性标签Action的专家用户, 可以认为UserA对于动作类型的电影比较有经验, 可以作为评定动作片方面的专家.在这里设置一个阈值来控制属性专家的数量.

对于一个用户集合$U$, 属性专家集合$AE(i)=\left\{ {u\vert \forall u\in U, {\rm Total}(u, i)>t} \right\}$, 其中$t$表示阈值, 当用户$u$评论过带有$i$属性商品的数量超过$t$时, 该用户才能被认定为$i$属性的专家用户.因此可以通过控制$t$来控制专家用户的数量.

3.2.2 离散属性标签连续化算法

当需要对一个物品的某一属性标签进行衡量评判时, 该领域的专家对该物品的意见往往具有参考价值.通过对用户$-$评分矩阵的处理, 已经获取到了标签属性的专家用户, 接下来将通过属性空间连续化(Discrete Attribute Space Continuation, DASC)算法将物品的属性标签连续化.

首先, 获取需要被属性空间连续化物品$i$的离散属性向量DAV$_{i}$, DAV$_{i}$=(da$_{i, 1}$, da$_{i, 2}$, ${\cdots}$, da$_{i, n})$, da$_{i, m}$=0$\vert $1, $m\leqslant n$, 此外还需获取对$i$评过分的用户集合user_set$_{i}$; 然后针对每一个值为1的向量属性$a$, 获取到user_set$_{i}$中关于该属性的所有专家用户集合expert_set$_{i, a}$, 对于expert_set$_{i, a}$中的每一个用户, 通过公式

$ \begin{equation} a_{u, i, a} =\frac{\max \_{\rm rating}\times R_{u, i} +\min \_{\rm rating}\times R_{u, i} }{4\times\overline {R}_{u, a} } \end{equation} $

(10)

获取用户对物品$i$的评判.式(10)中, $a_{u, i, a}$为用户$u$对于物品$i$的$a$属性的专家评分; max_rating为推荐系统评分的最大值, min_rating则为最小值; $R_{u, i}$为用户$u$对于物品$i$的真实评分, $\overline{R}_{u, a}$为用户$u$对于所有关于带有$a$标签属性物品的平均评分.

因为不同用户之间的打分尺度会有所不同, 有些用户习惯打高分, 而有些用户习惯打低分, 为了防止这种情况影响判定结果, 用式(10)将每个用户的评分做统一化的处理; 得到expert_set$_{i, a}$中每个用户的评判之后, 再对所有的结果值取平均值, 然后将该平均值转化为0到1之间的连续值, 即有

$ \begin{align} {\rm ca}_{i, a} =\sum\limits_{u\in \exp {\rm ert}\_{\rm set}_{i, a} } {\frac{R_{u, i} }{\max \_{\rm rating}\_a\times \overline {R}_{u, a} \vert \exp {\rm ert}\_{\rm set}_{i, a} \vert }}, \end{align} $

(11)

其中, ca$_{i, a}$为物品$i$关于属性标签$a$的连续值, max_rating_$a$为对属性$a$的评分最大值.

基于式(11), 便可将物品$i$的离散型属性向量DAV$_{i}$转换成连续型属性向量CAV$_{i}$, CAV$_{i}$=(ca$_{i, 1}$, ca$_{i, 2}$, ${\cdots}$, ca$_{i, n})$, 0$\leqslant$ca$_{i, m}\leqslant 1$, $m\leqslant n$. DASC算法见算法2.

算法2: DASC算法
输入:用户-物品评分矩阵$R$, 需要被连续化的物品$i$, 物品$i$的离散化属性向量DAV$_{i}$
输出:物品$i$的连续化属性向量CAV$_{i}$
1. U$\leftarrow $getUserSet(i)//获取所有对$i$有过评分记录的用户集合
2. for a$\leftarrow $0 to $\vert $DAV$_{i}$$\vert $ do//对于DAV$_{i}$的每一个属性
3.   if DAV$_{i, a} == 0 $
4.     CAV$_{i, a}$$\leftarrow $ 0//如果DAV$_{i}$的属性为0, 那么CAV$_{i}$的该属性也为0
5.   else
6.     expert_set$_{i, a}\leftarrow $extract_expert_a($i)$//获取该物品属性专家用户集合
7.   if $\vert $ expert_set$_{i, a}$$\vert $==0
8.     $ca_{i, a}$$\leftarrow $ 0//对$ca_{i, a}$赋初值
9.     for $u$ in $U$ do
10.       ca$_{i, a}\leftarrow$ca$_{i, a} + R_{u, i}$
11.       ca$_{i, a}\leftarrow$ca$_{i, a}$/U.number//将对ca$_{i, a}$设为所有用户对$a$属性的均值
12.   else
13.     ca$_{i, a }$$\leftarrow $0//对ca$_{i, a}$赋初值
14.     for every $u$ in expert_set$_{i, a}$ do
15.       ca$_{i, a}\leftarrow$ca${\_}{i, a} + R_{u, i}/(\max{\_}{\rm rating}{\_}a^{\ast}$ave$(R_{u})^{\ast}\vert {\rm expert}{\_}{\rm set}_{i, a}\vert$)//通过专家用户计算ca$_{i, a}$
16.       end for
17.     end if
18.     CAV$_{i, a}\leftarrow$ca$_{i, a}$//将ca$_{i, a}$赋值到对应的属性向量位置上
19.   end if
20. end for
21. return CAV$_{i}$//返回物品$i$的连续化属性向量CAV$_{i}$

以电影为例, 经属性标签连续化后如表 4所示.

因此, 经过属性连续化后的商品信息向量可以映射到空间中.空间坐标的维数和商品属性类型的数量相等, 并且每个属性值表示相应的坐标轴上的值.为了更清晰地表达本文所做的工作, 在此采用了以电影为例而进行说明分析, 以上工作并不仅仅针对电影, 标签连续化策略以及专家用户的提取普适于商品的相关研究.

3.3 推荐结合幂律

由于原始商品信息复杂而且庞大, 增加了查询算法的执行时间, 因此需要将原始商品信息中的大众商品剔除, 留下小众商品, 进而选取小众中的大众商品推荐给用户.本文利用幂律来对商品信息进行过滤.

3.3.1 幂律判断

幂律分布的概率密度函数为$y=cx^{-a}$.其特征明显, 大部分的分布规模较小, 少数的分布规模很大, 随着分布的增长, 其概率密度衰减缓慢, 此分布与"长尾分布"相似.对幂律两边同时取自然对数, 则ln$y$=ln$c-a$ln$x$.此函数在双对数坐标系下, 呈现为一条斜率为负的直线.此方法是判断幂律分布的标准, 同时可以进一步对幂律参数进行估计.

3.3.2 求解幂律

文献[27]通过训练经验数据得出了幂律分布相关的模型.幂律分布的概率密度函数为

$ {p}(x) =\frac{\alpha -1}{{x}_{\rm min}}\left(\frac{x}{x_{\min }}\right)^{-\alpha}, $

(12)

$ {p}(x\vert\alpha) =\prod\limits_{i=1}^n {\frac{\alpha {-1}}{{x}_{\rm min}}\left({\frac{x_i }{x_{\min }}}\right)^{-\alpha }}. $

(13)

本文采用最大似然估计来求解幂律指数.当对函数采用最大似然估计(Maximum Likelihood Estimation, MIE)后, 函数和取对数后的函数极大值点是相同的, 有

$ \begin{align} L=\ln p(x\vert \alpha )&=\ln \prod\limits_{i=1}^n {\frac{\alpha -1}{x_{\min } }\Big( {\frac{x_i }{x_{\min } }}\Big)^{-\alpha }} \nonumber\\[2mm] & =\sum\limits_{i=1}^{\rm n} {\Big[ {\ln (\alpha -1)-\ln x_{\min } -\alpha \ln \frac{x_i }{x_{\min } }} \Big]} \nonumber\\[2mm] & =n\ln (\alpha -1)-n\ln x_{\min } -\alpha \sum\limits_{i=1}^n {\ln \frac{x{ }_i}{x_{\min } }}. \end{align} $

(14)

通过对$\alpha $求偏导得到$\partial L/\partial \alpha $=0, 有

$ \begin{equation} \widehat{\alpha} =1+n\Big[ {\sum\limits_{i=1}^n {\ln \frac{x_i }{x_{\min } }} } \Big]^{-1}. \end{equation} $

(15)

最后得到近似求解$\alpha $的模型.

式(15)中$x_{\rm min}$为幂律分布变量的最小值.已经有相关研究发现顾客连续评论的时间间隔服从幂律分布^[28].

为了有效缩减原始数据空间, 本文通过寻找一个阈值, 以此阈值为界限对商品进行范围缩减, 后续工作只需对缩减后的商品选取$k$个进行推荐.因此下面需要考虑的是如何选取阈值.

3.3.3 阈值的选取

评论时间间隔越长, 则间接表明商品的流行度越低.为了对小众中的大众商品进行推荐, 首先应选取评论间隔时间较长的商品, 然后针对这些商品再选取时间间隔较短的商品进行推荐.所以应该合理选取这个阈值点. 图 1为幂律分布曲线.

由于曲率表示曲线的变化程度, 曲率越大, 曲线的弯曲程度变化越大.因此, 曲率最大的点可以用来表示阈值, 有

$ \begin{equation} \rho =\frac{1}{k}=\frac{[1+(f')^{2}(t)]^{\frac{3}{2}}}{{\vert f"(t)\vert}}, \end{equation} $

(16)

其中, $f(t)$表示关于间隔时间的幂律分布函数, 通过此曲率公式可以获得阈值点.因为此阈值点以上部分的曲线较陡且时间间隔较短, 能充分显示此商品颇为流行.根据商品的历史记录可以计算平均评论时间间隔, 间隔时间低于阈值的商品可说明销售情况良好.为了充分挖掘小众中的大众商品, 要过滤掉间隔时间低于阈值的商品信息, 只针对时间间隔大于此阈值的商品进行研究, 这在某种程度上极大地减少了推荐的样本空间, 提高了搜索查询效率.

3.4 基于用户偏好的空间映射化

前面已经将商品属性进行了标签连续化, 并且将处理后的商品信息向量映射到了空间中.为了利用空间搜索算法向用户推荐商品, 也将用户进行空间映射化, 可用公式

$ \begin{equation} P_{u, k} =\frac{\sum\limits_{i=1}^M {R_{u, i} \times } I_{i, k} }{M} \end{equation} $

(17)

对用户偏好进行标签连续化.公式(17)中, $P_{u, k} $表示用户$u$对商品第$k$个属性的偏好度, $I_{i, k} $表示商品$i$的第$k$个属性值, $M$表示用户评分的商品数量.通过此式可得出用户对商品不同属性的偏好程度, 从而将用户偏好向量映射到与商品信息向量相同的空间中.

3.5 支持RFN的推荐算法

在第3.2和第3.4节中, 已将商品和用户进行了空间化的处理, 将商品和用户映射为$n$维空间中的点.设$U$、$P$分别表示空间中的用户集合和商品集合, 在本节中结合RFN查询优化用户的推荐结果, 即根据定义4, 以用户偏好和商品属性的匹配程度值为衡量标准, 计算$k$个最远邻居中包含用户$u$的商品$p$, 并且将商品$p$加入到用户$u$的推荐列表中.

表示用户偏好和商品属性之间匹配程度$MC$的公式为

$ \begin{align} MC=\frac{1}{\sqrt {\sum\limits_{i=1}^n {(u_i -p_i )^2} } }, \end{align} $

(18)

其中, $u_{i}$表示用户$u$对商品$i$属性的需求度, $p_{i}$表示商品$p$附有$i$属性的程度. MC越大, 表示该商品越接近用户的喜好.基于RFN的用户偏好推荐(RUPRA)算法见算法3.

算法3: RUPRA算法
输入:经连续空间化的用户集合$U$、商品集合$I$
输出:推荐列表$L$集合
1. L$\leftarrow $$\emptyset $//将$L$列表集合初始化为空
2. for i$\leftarrow $0 to U.number do
3.   UPC($u$)//对每个用户进行偏好连续化
4. end for
5. for i$\leftarrow $0 to I.number do
6.   Ii.knn$\leftarrow $Compute_knn(Ii)//针对用户集合$U$计算商品$Ii$的knn
7.   for k$\leftarrow $0 to U.number do
8.     if Uk $\in $Ii.knn//如果用户属于商品$Ii$的knn
9.        Lk.add($Ii$)//将商品$Ii$加入到列表集合的第$k$个列表项中
10.     end if
11.   end for
12. end for
13. return $L$//推荐列表集合返回

通过上述算法, 就得到了推荐给用户的商品列表集合.

4 实验结果及分析 4.1 实验数据集

本实验选用MovieLens 100k数据集, 其中包括943个用户和1 682部电影的相关信息, 以及100 000条用户对电影的评分记录, 评分结果采用5等级制(1$\sim $5分), 并且每个用户至少对20部电影评过分.

4.2 评估标准和方法

实验采用的评估方法是机器学习中常见的leave-one-out方法.先将已有的用户偏好隐藏起来, 然后利用推荐系统对该用户偏好进行预测后, 进行商品推荐, 根据推荐商品的平均属性与已有的用户偏好的差距来对推荐系统进行评估.采用平均绝对误差MAE(Mean Absolute Error)对系统进行评估.假设$p_{i}$表示用户对商品第$i$种属性的喜好度, $q_{i}$表示商品带有第$i$种属性的程度, 那么该用户的MAE的计算公式为

$ \begin{align} {\rm MAE}&=\sum\limits_{i=1}^c {{\vert }p_i -q_i \vert }, \end{align} $

(19)

其中$c$表示商品属性的个数.公式(19)通过对比商品的平均属性与用户偏好得到绝对误差MAE.

根据公式(19), 评价较多的用户会有比较大的权值, 而数据中的大量评价较少的新用户只有很少的权值.为了平衡所有用户, 本文采用平均绝对用户误差MAUE (Mean Absolute User Error)这个标准, 即对每个用户计算MAE, 然后进行平均.设$m$为用户数, MAE$_{u}$为对用户$u$进行推荐后的绝对误差, 平均绝对用户误差计算公式为

$ \begin{equation} {\rm MAUE}=\frac{\sum\limits_{u=1}^m {{\rm MAE}_u }}{m}. \end{equation} $

(20)

平均绝对用户误差可以更好地反映系统推荐准确性.

4.3 实验结果与分析

本实验首先对不同数量的相似邻居和反向$k$最远邻进行偏差度量; 然后基于幂律过滤进行偏差度量; 最后基于不同数量的数据集进行度量.在专家评估公式中, 基于数据集的限制, 只考虑活跃度和准确性, 给出的活跃度和准确性权重分别是$\alpha $=0.5、$\beta $=0.5.根据实验, 当专家数量大于10个时, 实验准确性会明显下降, 因此在本实验中选取专家用户的数量是10.

图 2是基于不同数量$m$个专家用户的准确性比较, 可以发现当近似邻居数量达到某一值时, 继续增加数量会导致系统准确性下降.

图 3是基于不同$k$个最远用户的准确性比较, 可以发现适当的增加商品$k$个最远用户的数量可以提高系统推荐的准确性.

根据第3.3节中的幂律求解方法, 首先从原始数据集中拟合出幂律曲线, 并利用第3.3节中的公式计算其中的参数, 然后利用公式(16)计算出评论时间间隔阈值点, 并以此点为界限, 只保留原始数据集中评论时间间隔大于此阈值点的数据(评论时间间隔越短, 说明商品颇为流行, 关注商品且评论的人也比较多; 相反商品的评论间隔越长, 关注的人越少, 商品的流传度越低).通过这种方式来选取原始数据集中的小众商品, 从而挖掘小众商品中有较大潜力的大众商品来进行推荐.实验结果如图 4、图 5所示.

图 4、图 5是经过幂律进行过滤后, 将有较大潜力的电影推荐给用户的误差展示, 图 2、图 3和图 4、图 5相比, 图 4、图 5的误差程度明显高于图 2、图 3.因为经过幂律筛选后, 评分较高、口碑较好的电影已经被过滤掉, 剩下的有潜力的电影可能并不是完全符合用户偏好的, 但是拥有值得推荐的价值, 因此误差相对较高.

图 6是在最近邻居$m$=20的情况下, 本文模型(RUPRA)与Pearson模型准确性的对比情况.在$k$较小时, $m$占据主导作用, 专家用户是通过考虑多个因素而选取出来的; 而Pearson模型只是将普通用户与被推荐用户进行相似度计算, 因此在$m$占据主导作用时, Pearson模型准确度稍高, 但是随着反向最远邻居数的增加, 即要推荐给用户的商品数量增大的情况下, 本文模型的准确度逐渐高于传统模型.

图 7表示在$m$=10, $k$=10, 不同数据样本数量下的MAUE变化情况, 即商品越多, 用户可供选择的余地越多, 推荐给用户的商品更符合用户的偏好.

以上分析证明了在不同情况下本文推荐系统(RUPRA)的准确性, 以及不同的近似专家数量、商品的最远用户数量和样本数量对本文推荐系统准确性的影响.

5 结论

本文基于传统的协同过滤提出了基于RFN的专家用户协同过滤算法.为了充分挖掘小众中的大众商品的价值潜力, 本文通过幂律对商品信息进行过滤, 同时对商品属性及用户偏好进行空间映射化, 结合空间查询思想向用户进行推荐.实验证明本文的推荐系统准确率较高, 可以让非主流商品吸引更多的目标用户, 实现了对小众中的大众进行推荐, 对推荐系统的应用具有重要意义.