推荐系统可以简单看成一个用户-商品的二部分图，推荐算法要做的就是分析用户浏览、收藏、购买的记录，以及用户和商品的其他辅助信息，自动化找到用户喜欢的商品。推荐系统往往规模巨大，以刚刚上市的阿里巴巴为例，其淘宝平台是“10亿用户-10亿商品”的规模。是不是每一个用户都携带了同样价值的信息，对于算法贡献相同呢？我们认为不是，事实上，我们所要寻找的“推荐系统中的信息核”，就是一个用户的子集，却包含了推荐系统中绝大部分信息。如果这样的子集存在的话，就可以只使用这个子集进行算法的实施，从而大幅度降低算法复杂性。
做推荐系统的朋友，肯定都知道协同过滤方法[1]，其中基于用户的协同过滤的基本思想是找到和目标用户购买行为类似的用户，然后把这些人买过而目标用户没有买过的东西推荐给目标用户。其中有一种算法叫做top-k协同过滤，就是说不要考虑目标用户和所有用户的相似性并做加权，只考虑最相似的k个，这样效果反而更好。这个思想不新奇，主成分分析等等都有类似的观点，因为很弱的那些关联，基本上可以看成噪音。我们在展开信息核挖掘之前，先做了一个热身试验，就是把物质扩散算法[2]改造成了top-k最近邻的物质扩散，这里的top-k邻居也可以采用cosine相似性来进行选择。我们在豆瓣、Flickr和Last.fm三个数据集上作了实验，发现采用top-k最近邻物质扩散方法，比原来的物质扩散还好，当然，k也不能太小或者太大。
这个实验给了我们比较大的信心，就是去掉一些信息，推荐算法的精确性可能也能保持，甚至提高。但是热身实验是每一个用户的top-k都不一样，我们需要在系统层面，找到对于所有用户而言都相同的一个信息核。为了找到这个信息核，我们尝试了4种策略：（1）由最大度的节点组成这个核（这个核也包括他们的连边和连接的商品，如果一个目标用户不在这个核里面，对他推荐的时候，只有他自己的信息和信息核的信息可以使用）；（2）随机选择；（3）首先计算每个用户最相似的N个邻居，例如N=50，然后计算一个用户有多少次出现在其他所有用户最相似邻居，选出现得多的；（4）计算一个用户在其他所有用户的相似性列表中所处的位置，按照位置的倒数加权求和（大于N得0分）。相似性可以简单用cosine，其他也差不多。
我们发现，策略(4)效果最好，信息核在包含20%的用户时，有的时候比用所有信息得到的推荐精确度还要高。最差的情况下，也能达到91.4%的精确性，而且对很多方法用这种萃取的核来进行推荐，效果都非常不错。
进一步地，我们分析一下得到的信息核到底有什么特征。大家肯定会觉得，里面是不是有很多大度的用户，他们选择了很多商品，所以信息也充分。让人惊讶的是，策略(3)和策略(4)是表现最好的两个策略，而他们选择出来的用户度并不大，实际上在豆瓣和Flickr上面都比平均度还要小10%左右，在Last.fm上和平均度一样大。但是他们所选择的商品度都比较大，应该是流行品，统计上讲质量也比较高。而且，被选出来的信息核中的用户之间的相似性也明显比按照最大度选择出来的用户之间要小。总结起来，是选出了一批自身度不大，但是相互之间选择具有多样性，而且倾向于选择高质量商品的用户。
文章有一个比较明显的缺陷，就是获得这个子集的算法复杂性本身，比推荐算法还要高！当然，我们主要的目的是在现象和数值层面揭示这个信息核的存在性，可以看成应用基础性的研究，还不能直接应用。稍微利好一点的信息是，在真实数据分析中，我们发现信息核（选取20%用户）中超过90%的成员，在一个月以后，还保持在信息核中，因此信息核的更新，或许不必实时来做。
转载：http://blog.sciencenet.cn/home.php?mod=space&uid=3075&do=blog&id=829574