3.1 基于二分图的经典个性化推荐

二分图作为网络形式的一种特殊形式有着广泛的应用，现实中有很多商业场景可以抽象为二分图，比如读者购买书籍、用户收藏商品等。

将用户的商品购买等行为数据表示为二分图结构后，向目标用户进行推荐的任务转变为预测用户与商品是否存在连接，即用户与未评价商品之间是否具有相关性。相关性越大，商品被推荐的可能性越大。

一个基于二分图的推荐系统的输入数据可以抽象为用户-项目二分图G=(U,O,E)，其中U={u1,u2……um}，表示所有的用户；O={o1,o2……on}，表示所有的项目。当用户uα评价项目oi后，二者之间便有一条连线，aαi=1，否则aαi=0。一个简化的4个用户、3个项目的用户-项目二分图可以表示为图3.1。

图3.1 简化的用户-项目二分图

如果要将图3.1映射为仅包含用户的网络图，则必须通过用户共同选择过的项目作为桥梁，找到用户之间的联系。假设用户之间的连接权重以用户共同选择过的项目数衡量，那么图3.1可以映射为如图3.2所示的无向用户网络图。

图3.2 用户-项目二分图映射的无向用户网络图

将用户-项目二分图映射为无向用户网络图后，意味着对于任意两个存在连接的用户ui与uj，ui认为uj的重要度sji等同于uj认为ui的重要度sji。这种映射机制存在用户网络图中权重的计算不完全符合实际情况的问题。比如，美食家与普通美食爱好者由于共同点评过某些美食而产生连接，但在推荐过程中，美食家认为普通美食爱好者对自己的推荐重要程度显然要低于美食爱好者认为美食家对自己的推荐重要程度。相似的情形也会出现在科研协作网络中，专家与普通科研人员的互相推荐重要程度也不相同。事实上，对于推荐网络中任意两个用户ui和uj，ui认为uj在推荐时的重要性与uj认为ui在推荐时的重要性往往不相等，也就是说映射后的图应该是有向的。此时，如何科学合理计算用户之间的连接权重是解决映射问题的关键。

借鉴复杂网络物质扩散原理，周涛等提出使用物质扩散的方法在用户或项目之间分配推荐能量。假设初始时每个用户都具有一定的推荐能量，这些推荐能量将等分地分配给用户所选择的项目，每个项目获得推荐能量后，再等分地分配给选择过它的用户，资源分配过程如图3.3所示。

图3.3 推荐资源分配过程

这种资源分配机制可以用公式（3-1）表示：

其中，表示用户uβ的出度，表示项目oi的出度，Sαβ表示uα认为uβ在推荐时的重要程度。如果uα评价过项目oi，则aαi=1，否则aαi=0。aβi则代表了uβ是否评价过项目oi。

预测用户uα对未评价项目oi的评分vαi的公式如下：

在上述算法中，只要用户uα选择了项目oi，就认为用户对此项目感兴趣，即aαi=1，该算法较适合两挡评分制的数据集，因为在此类型的数据集中可以根据用户的评分区分用户对项目感兴趣或不感兴趣。在五分制的评级中，一般认为3分以上为用户对某项目感兴趣；评分3分以下的如何在推荐系统中应用，是一个难题。