一种基于用户行为的个性化优惠券推荐算法

佟　强　赵星秋

(对外经济贸易大学信息学院，北京100029)

本文提出了一种基于用户行为的个性化的优惠券推荐算法，根据用户购买过的商品、购买过的商品的分类、用户的偏好、优惠券的兑换次数递进地向用户推荐他可能喜欢的、潜在兑换率高的个性化的优惠券。优惠券以推荐邮件的形式发送给用户，目标是提高电子优惠券的兑换率，促进优惠券对应产品的销售，以及增强用户的忠诚度。

1　概述

随着电子商务的飞速发展，电子优惠券作为一种新型的促销手段正在广泛地被电子商务企业所采用。对于一个大型电子商务网站，电子优惠券的种类繁多数目成百上千。此时，给一个特定的用户推荐哪些优惠券就成为一个值得研究的问题。一个好的推荐算法将会导致更高的兑换率，其对应的销售额也会更高。这不但会给企业带来更多的利润，更会增强用户的忠诚度。研究表明，电子商务的销售行业使用个性化推荐系统后，销售额能提高2%～8%[5]，尤其在书籍、电影、日用百货等产品相对较为低廉且商品种类繁多、用户使用个性化推荐系统程度高的行业，推荐系统能大大提高企业的销售额。

根据发现相关性的方法，推荐系统可以分为两大类：基于协同过滤的推荐[1]和基于内容的推荐[2][3]。根据用户对物品或者信息的偏好，发现物品或者内容本身的相关性，或者是发现用户的相关性，这种被称为基于协同过滤的推荐(Collaborative Filtering-based Recommendation)。根据推荐物品或内容的元数据，发现物品或者内容的相关性，这种被称为基于内容的推荐(Content-based Recommendation)。此外也有将协同推荐和基于内容的推荐结合起来的推荐系统[4]。协同过滤和基于内容的推荐都有各自的优缺点，因此现在的推荐系统都采用了几种技术相结合的推荐技术。

本文提出的优惠券推荐算法综合使用协同过滤和基于内容的推荐，采用递进的步骤来推荐用户可能喜欢的个性化的优惠券。推荐算法的步骤简单描述如下：

(1)根据用户一周前购买的商品的UPC进行推荐

(2)根据用户购买的商品的分类进行推荐

(3)根据用户的偏好进行推荐

(4)根据优惠券被兑换的次数进行推荐

2　算法描述

优惠券推荐算法的步骤如图1所示，算法采用递进的步骤进行推荐，一旦中间某个步骤达到要推荐的优惠券个数，即完成推荐。

图1　优惠券推荐算法的步骤

2.1　基于UPC的推荐

UPC，即Universal Product Code，是普遍采用的用于追踪店内商品的条码符号。UPC最普通的形式是UPC－A，它由12位数字构成，唯一地分配给每一个用于交易的商品。

基于UPC的推荐被广泛用于实体店的销售。一般来讲，如果一个顾客购买了某个厂家的特定产品，在结账的时候收银员会给他一张厂家优惠券。他再次购买这个厂家的优惠券上指定产品的时候就能获得优惠券对应的促销优惠。

作为推荐逻辑的第一步，算法首先查找用户订单中商品的UPC并和优惠券进行匹配。如果用户购买了某个电子优惠券所要求的UPC列表中的任意一个商品，那么将这个电子优惠券推荐给这个用户。与传统的实体店不同的是，如果购买发生在一周以内，我们认为用户购买相同产品的概率很小，并不推荐对应的电子优惠券。因此，推荐算法只考虑一周前的订单。由于是电子优惠券，一周后我们仍然可以通过电子邮件、会员中心等电子形式在更恰当的时机将这个电子优惠券推荐给用户。

2.2　基于商品分类的推荐

我们要在给用户发送的推荐邮件中展示固定数量的电子优惠券，比如16个，每行4个，共4行。很多用户可能没有足够多的订单，导致基于UPC的推荐不能够找到足够数量的优惠券。因此，我们需要扩展推荐算法从购买过特定商品到购买过某些分类的商品。

电子商务网站的商品分类通常分为3级，但有些情况第3级分类下还有不同的产品类型，可以理解为存在第4级分类。例如3级分类“家用电器>大家电>烟机/灶具”的下面还有几个产品类型：烟灶套装、吸油烟机、嵌入式燃气灶、台式燃气灶。因此，推荐算法按照4级分类从低到高将用户订单和商品分类进行匹配。

如果用户购买过的某个商品和一个优惠券在同一个四级分类下面，那么推荐这个优惠券；如果用户购买过的某个商品和一个优惠券在同一个三级分类下面，那么推荐这个优惠券；如果用户购买过的某个商品和一个优惠券在同一个二级分类下面，那么推荐这个优惠券；如果用户购买过的某个商品和一个优惠券在同一个一级分类下面，那么推荐这个优惠券；这个步骤是一个递进的过程，其中任何一个步骤的执行，如果导致累计找到的优惠券达到16个，则不再执行后续步骤。

为了提高算法执行效率，我们可以构建分类到优惠券的倒排索引。也就是说，预先计算好全部第n级分类对应的优惠券的列表，并存储到哈希表中。这样就可以快速查到某个分类下的优惠券。

2.3　基于用户偏好的推荐

用户偏好的构建对于电子商务系统至关重要。通常情况下，电子商务系统可以根据用户浏览过哪些商品，用户将哪些商品添加到了购物车，购买过哪些商品，评价过哪些商品，以及用户发表的评论内容来构建用户偏好。用户偏好分为不同的偏好类型：品牌、商品分类、主题词、网站、产品型号、颜色、评价得分、尺寸、质保、安装信息、维护信息等。用户偏好的表示为不同偏好类型下面的若干主题词。

我们将每个电子优惠券提取主题词。主题词的来源可以采用电子优惠券的标题、描述、分类、品牌、购买要求等。具体做法是将这些文本信息分词并过滤掉非主题词，从而得到一个电子优惠券的主题词集合。

基于用户偏好的推荐通过求一个用户的偏好主题词集合与一个电子优惠券的主题词集合的交集，然后根据主题词交集中主题词个数从多到少排序，优先推荐交集中主题词个数多的电子优惠券。

2.4　基于兑换次数的推荐

如果以上的推荐步骤仍然无法找到足够数量的电子优惠券，我们根据优惠券兑换次数的多少作推荐，将兑换次数从高到低排序，取前面兑换次数高的几个补充到之前的推荐结果的末尾，以凑齐4行4列共16个电子优惠券。

3　算法实现

3.1　数据存储

优惠券表中保存的是可以推荐给用户的全部优惠券。

Coupon=(Coupon ID，Category，Brand，Head Line，Description，Requirement，Required UPCs，Redeem Count)；

Coupon ID：电子优惠券的ID，唯一标识一个Coupon。

Category：电子优惠券所属三级分类的文字描述。

Brand：品牌。

Head Line：标题。

Description：优惠券描述信息。

Requirement：使用该电子优惠券的购买要求。

Required UPCs：逗号分隔的多个UPC，一周前购买过这些UPC对应的商品将推荐该优惠券。

RedeemCount：优惠券被兑换的次数。

商品表中保存的是商品的UPC已经对应的4级分类。

Item=(UPC，Division，Line，SubLine，Class)。

UPC：商品的Universal Product Code。

Division：商品一级分类。

Line：商品二级分类。

SubLine：商品三级分类。

Class：商品的类型，我们认为是第4级分类。

用户订单明细表保存的是用户的购物记录。(www.daowen.com)

OrderDetail=(OrderID，UserID，UPC，PlaceOrderTime)。

OrderID：订单ID。

UserID：用户ID。

UPC：用户购买的商品的UPC。

PlaceOrderTime：下单时间。

用户偏好表保存的是用户的偏好，用户偏好的计算我们这里不做详细的介绍。

Prefecence=(UserID，PreferenceTypeID，Theme Word ID)。

UserID：用户ID。

Preference Type ID：偏好类型ID。

Theme Word ID：主题词ID。

优惠券发送表保存的发送给用户的优惠券和优惠券的状态。

Coupon Sent=(UserID，CouponID，Coupon Status，StatusChangeTime)。

UserID：用户ID。

CouponID：优惠券ID。

CouponStatus：Coupon的状态，取值可以是Sent、Clipped、UnClipped、Redeemed。StatusChangeTime：Coupon状态改变的时间。

3.2　算法数据结构

优惠券推荐算法中需要初始化的核心数据结构描述如下：

CouponThemeMap

关键字是CouponID，值是该Coupon提取主题词之后的主题词ID的列表：

UPCCoupounMap；

关键字是UPC，值是该UPC对应的优惠券列表，如果一个用户购买了这个UPC的商品，那么一周后可以推荐对应的优惠券列表：

ClassCouponMap

关键字是4级分类，即Division/Line/SubLine/Class，值是该4级分类对应的优惠券列表。如果一个用户购买了该4级分类下的产品，那么一周后可以推荐对应的优惠券列表：

SubLineCouponMap

关键字是Division/Line/SubLine，值是该3级分类对应的优惠券列表。

LineCouponMap

关键字是Division/Line，值是该2级分类对应的优惠券列表。

DivCouponMap

关键字是Division，值是该1级分类对应的优惠券列表。

3.2　算法步骤描述

要给某个用户的email发送推荐邮件，首先根据email得到该用户的UserID，然后将UserID作为推荐算法的输入参数，以下步骤描述根据用户UserID推荐个性化的优惠券的过程。

(1)根据UserID查询订单明细表OrderDetail得到该用户的购买记录。初始化FoundCouponIDSet为空。

(2)遍历全部购买记录，如果下单时间发生在7天前，根据购买产品的UPC去UPCCouponMap里面获取优惠券列表，如果得到列表不为空，则将找到的CouponID加入到FoundCouponIDSet，同时记录这些Coupon的推荐理由是MatchUPC。

(3)再次遍历全部购买记录，根据UPC在商品表Item中查到一个商品的Division、Line、SubLine和Class。根据Division/Line/SubLine/Class去ClassCouponMap中获取优惠券列表，如果得到列表不为空，则将找到的CouponID加入到FoundCouponIDSet，同时记录这些Coupon的推荐理由是MatchClass。根据Division/Line/SubLine去SubLineCouponMap中获取优惠券列表，如果得到的列表不为空，则将找到的CouponID加入到FoundCouponIDSet，同时记录这些Coupon的推荐理由是MatchSubLine。根据Division/Line去LineCouponMap中获取优惠券列表，如果得到的列表不为空，则将找到的CouponID加入到FoundCouponIDSet，同时记录这些Coupon的推荐理由是MatchLine。根据Division去DivCouponMap中获取优惠券列表，如果得到的列表不为空，则将找到的CouponID加入到FoundCouponIDSet，同时记录这些Coupon的推荐理由是MatchDiv。

(4)根据UserID从用户偏好表Preference获得代表一个用户偏好的ThemeWord ID的列表。

(5)遍历全部没有过期的Coupon的列表，根据CouponID从CouponThemeMap中获得一个Coupon对应的主题词ID的列表。求Coupon主题词ID列表和用户主题词列表的交集，如果交集中元素个数大于0，设置Coupon的weight为交集中元素的个数，同时设置推荐理由为MatchTheme。如果交集元素个数为0，则设置Coupon的weight为这个Coupon的兑换次数RedeemCount，同时设置推荐理由为MostRedeem。

(6)多关键字排序：对于不同的推荐理由，按照顺序MatchUPC、MatchClass、MatchSubLine、MatchLine、MatchDiv、MatchTheme、MostRedeem排列，即MatchUPC的在最前面，MostRedeem的在最后面。推荐理由相同时，按照weight降序排列，即推荐理由相同时，按照主题词匹配次数倒序排列，如果主题词匹配次数为0，则按照兑换次数倒序排列。

(7)截取排序后的Coupon列表的前16个做为推荐给该用户的Coupon列表，并为每个Coupon分配一个唯一的条码。将Coupon列表保存在CouponSent表中。

(8)优惠券的状态：当一个用户将某个Coupon收藏的时候，Coupon的状态转换为Clipped；当一个Coupon被取消收藏的时候，状态转换为UnClipped；当一个Coupon被兑换后，状态转换为Redeemed。

(9)更新推荐列表：当发给一个用户的Coupon列表中有着几种情况：(1) Coupon过期；(2) Coupon被Clip；(3) Coupon被Unclip；(4) Coupon被Redeem。那么需要补充一定数量的Coupon，算法同上面的步骤1－7。

4　结论

本文提出了一种基于用户行为的个性化优惠券推荐算法，根据用户购买过的产品、购买过的产品的分类、用户的偏好、优惠券的兑换次数递进地向用户推荐他可能喜欢的、潜在兑换概率高的优惠券。本文给出了个性化优惠券推荐算法的算法描述和算法实现，该算法已经在某大型零售企业得到应用，每个月都会给2000万用户发送个性化优惠券的电子邮件，并提供JSON API将个性化的优惠券显示到每个用户交易中心。

参考文献

[1] Herlocker，L.，Konstan，J.A.，Terveen，L.G.，Riedl，J.T.：Evaluating Collaborative Filtering Recommender Systems. ACM Transactions on Information Systems 22 (1)，5–53(2004)

[2] P. Lops，M. de Gemmis，G. Semeraro. Content-based Recommender Systems：State of the Art and Trends. In：P. Kantor，F. Ricci，L. Rokach and B. Shapira，editors，Recommender Systems Handbook：A Complete Guide for Research Scientists＆Practitioners，Chapter 3，pages 73－105，BERLIN：Springer，2010.

[3] Pazzani，M.J.，Billsus，D.：Content-Based Recommendation Systems. In：P. Brusilovsky，A. Kobsa，W. Nejdl(eds.) The Adaptive Web，Lecture Notes in Computer Science，vol. 4321，pp. 325–341(2007). ISBN 978－3－540－72078－2

[4] Claypool，M.，Gokhale，A.，Miranda，T.，Murnikov，P.，Netes，D. and Sartin，M.：Combining Content-Based and Collaborative Filters in an Online Newspaper. In Proceedings of SIGIR 99 Workshop on Recommender Systems：Algorithms and Evaluation，Berkeley，CA(1999)

R.D. LAWRENCE，G.S. ALMASI，V. KOTLYAR，M.S. VIVEROS，S.S. DURI，Personalization of Supermarket Product Recommendations，Data Mining and Knowledge Discovery，5，11－32，2001