基于离散选择的推荐系统模型与算法

推荐系统在电子商务中有着广泛的应用，它根据用户的输入条件从产品库中确定一组最能引起用户兴趣的产品返回给用户，目的是增大用户的点击概率，从而增加销售收入。现有的推荐系统文献均来自计算机科学领域，通过考察产品与输入条件的"匹配性"以及结果集内部的"多样性"来生成推荐结果。这些文献的共同局限在于未能直接对用户的选择行为建模，并把结果集质量割裂为"匹配性"和"多样性"两个独立的指标。. 本课题拟从离散选择分析的角度研究推荐系统的模型和算法，通过离散选择模型直接考察用户对结果集的"选择概率"，并以此作为衡量结果集质量的指标。本课题将先考察"选择概率"的数学性质，然后建立基于离散选择的推荐系统模型。模型的建立将考虑两种形式，一种是基于可行解性质的模型，一种是基于最优解性质的模型。针对不同的模型，将设计相应的最优解算法。同时，本课题将把理论研究的结果应用到实际系统中，对模型和算法做进一步的验证。

本课题研究了基于离散选择的推荐系统，我们提出用“选择概率”来衡量推荐列表整体的质量，从而能够把推荐系统所关心的“精准性”与“多样性”这两个指标统一起来。我们还引入“不购买”（Do not buy）这个选择支，从而使得“选择概率”这一指标恰好对应着网上商店的一个重要运营指标--“转化率”（Conversion rate）。在建模的过程中，我们采用多层Nested Logit模型，这使得它能够合理地处理产品间存在多个相似维度的情况。该问题的数学模型是一个包含0-1变量的非线性优化问题，我们通过仔细研究其最优解的性质，给出了一个基于动态规划的最优解求解框架。我们证明，在这个框架内，每个子问题都可以被转化为一个包含0-1变量的整数规划问题。针对子问题的求解，我们设计了两种不同的求解算法：第一种算法用分支定界的方法求解，这种方法的好处是便于实现，但其最坏情形下的复杂度较高，不能满足网上商店对计算效率的要求。在第二种算法里，我们进一步考察子问题最优解的性质，然后设计了一个多项式复杂度的算法，极大地提高了算法的效率。..我们根据课题的研究成果，撰写了题目为Choice-based recommender systems: A unified approach to achieving relevancy and diversity的学术论文。该论文已发表在英文期刊Operations Research上。