Journal of Frontiers of Computer Science and Technology ›› 2019, Vol. 13 ›› Issue (2): 226-238.DOI: 10.3778/j.issn.1673-9418.1803021

Previous Articles     Next Articles

Diversified Recommendation Approach Under Non-Uniform Partition Matroid Constraints

HE Fengzhen1+, SHI Jinping2   

  1. 1. School of Information, Yunnan University Travel and Culture Institute, Lijiang, Yunnan 674100, China
    2. Science and Technology Settlement Center, Yunnan Rural Credit Cooperatives, Kunming 650228, China
  • Online:2019-02-01 Published:2019-01-25

非均匀划分拟阵约束下的多样性推荐方法

和凤珍1+,石进平2   

  1. 1. 云南大学旅游文化学院 信息学院,云南 丽江 674100
    2. 云南省农村信用社 科技结算中心,昆明 650228

Abstract: Diversified recommendation methods aim to provide top-k recommendations that are both relevant and diverse. Most existing methods for diversity recommendation do not take into consideration diversity and accuracy at the same time, and these methods assume that each item is of equal significance. Inspired by this, this paper proposes a novel method for diversity recommendation based on user preference. For the personalized recommendation system, the approach models user’s aggregate category preference, inner category preference and relevance, which jointly merges diversity and relevance into a submodular function and enforces an non-uniform partition matroid constraints (i.e., different users have different preference degree for each item category even in the same category and each item is not equally important) on all categories. This paper proves that maximizing the proposed object fuction is NP-hard, and by local greedy select in the same category to solve submodular function can obtain a guaranteed approximation ratio of [1-1/e], and also reduces the complexity of the algorithm. Last but not least, a penalty factor is introduced to automatically adjust the hardness of item belonging to the same category included in recommendation list. Extensive experiments on different real data sets demonstrate that the proposed method can not only achieve a good tradeoff between diversity and relevance, but also have high efficiency.

Key words: personalized recommendation, user preference, recommender system, diversity, partition matroid constraints, submodular function

摘要: 多样性推荐方法旨在提供既满足相关性又具有多样性的top-k推荐结果。大多数现有的多样性方法没有同时考虑多样性和准确度,而且这些方法假设每个推荐项的重要程度是相同的。受此启发,针对个性化推荐系统,提出一种新的基于用户偏好的多样性推荐模型。该模型对用户的整体类别偏好程度、同一类别内部的偏好程度和相关度进行建模;将多样性和相关性同时融合到子模函数中,同时在模型上施加了非均匀划分拟阵约束(即不同用户对不同类别的偏好程度以及同一类别内部的偏好程度不同,每个推荐项的重要程度也不同);证明了最大化提出的目标函数是NP-hard问题,并通过类别簇内局部贪心求解子模函数获得[(1-1/e)]的近似保证率,同时降低了算法复杂度。最后,引入一个惩罚因子自动调节同一类别中的推荐项加入推荐列表的困难程度。不同数据集上的实验结果表明:提出的方法不仅能够在准确度和多样性之间取得有效的折中,而且具有高效性。

关键词: 个性化推荐, 用户偏好, 推荐系统, 多样性, 划分拟阵约束, 子模函数