A randomized algorithm for maximizing the diversity of recommendations

Abstract

This paper proposes a new approach, and studies an algorithm to address the Maximum Diversity Problem (MDP) of recommendations for composite products or services. First, the proposed approach is based on constructing and using a multi-dimensional diversity feature space, which is separate from the utility space used for utility elicitation. Second, we introduce a randomized algorithm, which is based on iterative relaxation of selections by the Greedy algorithm with an exponential probability distribution. The algorithm produces a competitive solution with respect to finding a diverse set from candidate recommendations. Finally, we conduct an experimental study to compare the efficacy and efficiency of the proposed algorithm with two broadly used diversity algorithms, as well as with the exhaustive algorithm, which we could only compute for sets of up to seven returned recommendations. The experimental results show that the proposed algorithm is highly efficient computationally and that in terms of diversity, it consistently outperforms the two competitive algorithms and converges to the optimal solutions on cases run with the exhaustive algorithm in under 100 ms.