论文部分内容阅读
随着web2.0的发展，互联网迎来了一个数据爆炸的时代，搜索引擎的关键字搜索已经不能满足用户的个性化需求，取而代之的是推荐引擎的出现。推荐引擎带给了用户更为个性化的内容，用户得以从海量的数据中解放出来。标签推荐作为推荐引擎的重要分支之一，越来越受到关注，并在电子商务、社交网站中得到了广泛的应用。 标签推荐中也存在一定的问题。现行的标签推荐算法产生的结果集，虽然能够比较准确的描述物品，有较好的相关性，但是往往多样性较差，标签之间存在语义相似，冗余严重的问题。这种情况降低了推荐结果集的新颖性和多样性，严重影响了用户的体验。本文的主要工作如下: (1)本文基于局部和全局标签共现矩阵定义了相关性的度量。局部标签共现矩阵表现了用户的兴趣爱好，而全局的标签共现情况则反映了每个标签的流行度和被喜好度。这样相关性的度量不仅融入了用户的个人兴趣爱好，同时还考虑了标签的被认可度，从而提高了准确度。 (2)根据目前的了解，本文第一次在标签推荐中提出了语义覆盖的概念。基于普林斯顿大学的WordNet字典，从IC(Information Content)的角度定义了语义多样性，有效的去除了推荐结果中的语义冗余。同时，采用覆盖的概念，推荐结果集可以很好地在语义上代表候选标签集合。 (3)通过对基于多样性覆盖的标签推荐问题的深入研究，本文设计实现了三个算法:EDC(Exact Algorithm of Diversified Coverage)、GDC(Greedy Algorithm of DiversifiedCoverage)以及MDC(More Algorithm of Diversified Coverage)算法。EDC算法通过将多样性覆盖标签推荐问题转换为图的最小独立支配集问题，在优先处理图中包含的团和二分图后，递归的在剩余的图中搜索最小独立支配集。考虑到数据集非常大的时候，EDC算法的时间复杂度非常大，因此本文提出了GDC算法贪心地获得推荐结果集。同时，为了满足动态增量扩充结果集的需要，文中提出MDC算法，该算法无需重新计算，采用增量扩充的方式，不仅扩充了结果集，还保证了扩充结果集与原结果集间较小的Jaccard距离。 (4)本文为了验证算法的效率和有效性，在MovieLens和Last.fm数据集上对算法进行了大量验证工作。在效率方面，算法对各种影响因素有着不同的表现。在有效性方面，虽然算法的相关性有所降低，但是多样性有了明显提升。