基于属性规则与关联规则的推荐模型设计

余鹏程，李 烨

(上海理工大学 光电信息与计算机工程学院，上海 200093)

基于属性规则与关联规则的推荐模型设计

余鹏程，李 烨

(上海理工大学 光电信息与计算机工程学院，上海 200093)

针对如何更好地描述商品属性与用户偏好之间关系的问题，提出了属性规则概念；并针对推荐系统的冷启动问题，将属性规则与关联规则相结合，设计了一种新的推荐模型；为解决在关联规则生成过程中，Apriori算法需要多次扫描数据库的问题，采用矩阵运算的方法，一次扫描数据库，生成频繁项集，同时利用频繁项集支持度计数生成属性规则；最后，匹配两种规则产生最终Top-N推荐列表。

属性规则；关联规则；推荐系统；Apriori算法

“+互联网”时代的到来，使得“信息过载”问题越来越明显，而作为解决“信息过载”问题并挖掘用户潜在需求的有效方法，推荐系统正吸引越来越多的关注[1]。搜索引擎作为解决“信息过载”问题的传统解决方案是指自动从因特网搜集信息，经过一定整理后，提供给用户进行查询的系统。然而，在满足用户的隐性偏好方面，搜索引擎却无能为力[2]。推荐系统是根据用户的潜在需求、兴趣等，将用户感兴趣的信息、产品推荐给用户。随着移动互联网的兴起，推荐系统的优势将会更加明显。

目前，运用较为成功的推荐技术是基于协同过滤的推荐，其是根据用户兴趣和特点寻找与用户需求相似的信息推荐给用户,或者寻找与用户有相似兴趣和特点的目标用户群进行推荐。协同过滤的关键是相似性计算，其核心是对推荐对象进行最近邻查询[3-4]。然而对于新用户，协同过滤推荐算法无法根据新用户的少量信息产生有效推荐，即冷启动问题[5-6]，并随着用户数量的上升，算法耗时也在增加，使得推荐效果在一定情况下变差。为了从新用户的少量信息中准确挖掘用户偏好，本文提出属性规则的概念，并且设计一种基于关联规则与属性规则相结合的推荐模型来解决冷启动问题。采用经典算法Apriori[7]来挖掘关联规则，为了避免Apriori算法多次扫描数据库的问题，采用矩阵计算的方式产生频繁项集[8]，同时利用各项的支持度计数产生属性规则。最后根据当前获取的用户信息，分别匹配关联规则与属性规则，综合两种规则产生的推荐结果来生成最终的Top-N推荐列表。

1 基本概念

设I={i1,i2,…,in}是数据库D中所有项的集合，T={t1,t2,…,tm}是所有交易的集合，每个ti称为T的子集，且每个事物ti包含的项均是I的子集[9]。

定义 数据库D中包含特定项集的事务个数称支持度计数，支持度计数除以事务总数即为该项集的支持度。设|·|表示集合中元素的个数，符号m代表事务总数。则对于某一项集X的支持度计数

(1)

定义 若项集X包含k个项，并且支持度c(X)大于支持度阈值α，则称项集X为频繁k项集。

定义 对于某一规则X⟹Y，其中X,Y∈T，且X∩Y=Ø，其支持度与置信度为

supp(X⟹Y)=δ(X∪Y)

(2)

(3)

若其满足supp(r)≥a,conf(r)≥β条件，则该规则即为X⟹Y的关联规则，用Rules_s表示为

Rules_s={r:X⟹Y|supp(r)≥α,

conf(r)≥β,X,Y⊂T,X∩Y=Ø}

(4)

其中，α和β分别为给定的支持度阈值与置信度阈值。

2 推荐模型设计

本文设计的推荐系统模型如图1所示，主要包括4个模块：数据预处理模块、推荐算法模块、用户信息采集模块、推荐结果综合处理模块，以下介绍4个的模块功能。

图1 推荐模型

2.1 数据预处理模块

首先，本文设计的推荐模型采用用户的历史购物数据，之所以采用历史购物数据，一是避免对用户产生侵袭性；二是客观反映用户偏好。原始交易记录包含诸多冗余成分，并不能直接作为系统的输入，需进行预处理。例如，天猫电器商城2015年11月份的交易数据中，每一种商品包含21条属性。因此要对其进行降维，特征提取，删除冗余信息，并保留关键属性，如商品的种类、外观、颜色等[10]。

2.2 推荐算法模块

推荐算法模块是本模型的核心部分，合适的推荐算法对推荐模型的优劣具有决定作用，本文采用基于矩阵的Apriori算法来生成频繁项集，并最终通过频繁项集生成关联规则与属性规则。

2.2.1 关联规则算法

Apriori是关联规则挖掘中的经典算法之一，其原理简单，效果明显，应用广泛。其的核心思想是对数据库进行多次扫描，利用已知的 频繁项集，联合一定的约束策略生成 频繁项集，然后由最终的k频繁项集生成关联规则[11-12]。

Apriori算法主要分为两个阶段：候选项集的产生与剪枝、频繁项集的形成。其的核心也是围绕着如何高效生成候选项集进行的,而在生成候选项集的过程中，最重要的工作就是连接和剪枝。算法采用合并两个(k-1)频繁项集来产生候选k频繁项集的策略，这种方法虽保证了候选项集产生的完全性，但需要通过额外的算法来保证该候选项集的所有子集均是频繁的[13]。

从其原理可看出在生成频繁项集的过程中，Apriori算法需要多次扫描数据库，且会产生大量的候选项集，当数据库包含大量交易数据时，该方法效率极低，难以满足推荐系统对实时性的要求。而本文设计的推荐模型采用矩阵计算的方式通过一次扫描数据库，就能生成频繁项集。

基于矩阵的Apriori算法描述如下：

输入 交易数据库D、最小支持度α和最小置信度β。

输出 关联规则Rules_s。

(1)扫描交易数据库D，构建交易矩阵Dm×n，其中矩阵每一行代表一次交易记录，每一列代表一种商品项。当第i次交易包含商品j时，di×j=1，否则di×j=0；可得矩阵

(5)

(2)由频繁1项集产生候选2项集C2，对矩阵Dm×n的每一行求和，删除值<2的行(值<2不可能产生频繁2项集)。C2每一个元素IiIj的支持度为

(6)

其中，∧表示与运算。删除支持度<α的候选项，得到频繁2项集

L2={c∈Ck|Supp(IiIj)≥α}

(7)

(3)当k≥3时，根据频繁(k-1)项集Lk-1生成候选k项集Ck。首先删除矩阵Dm×n中行元素之和

(8)

删除支持度<α的候选项，得到k频繁项集Lk={c∈Ck|Supp(IiIj…It)≥α}；

(4)由频繁k项集Lk生成候选k+1项集Ck+1,如果Ck+1不等于空，执行步骤(3)，否则执行步骤(5)；

(5)遍历频繁项集，生成关联规则库Rules_s。

2.2.2 属性规则算法

定义 设集合A={a1,a2,…，an}是数据库中项的属性集合，在交易数据库D中，具有属性a的项按照支持度计数进行降序排列，取前N项为：IN={i1,i2,…,iN}，则属性a的规则 即为Rules_a

Rules_a={r:a⟹IN|Supp(i)≥α,a∈A,i∈IN}

(9)

其中，α为给定的支持度阈值。

在属性规则生成之前，首先需要根据商品的种类选择合适的属性，建立属性集合，然后遍历数据库，计算出每一种属性对应的商品项的数量，最后保留前N项即可。遍历数据库与生成属性规则可同时进行。

属性规则生成算法描述如下：

输入 频繁1项集L1，商品属性集合A,推荐商品数N。

输出 属性规则库Rules_a。

1.按照支持度对L1进行降序排列

2.for a∈A

3.fori∈L1

4.ifi具有a属性

5.IN←i

6.n++；

7.if n==N

8.rule_a←a⟹IN

9.Rules_a←rule_a

10.n=0;

11.break;

12.returnRules_a；

2.3 用户信息采集模块

用户信息采集模块的功能是收集用户信息与目标商品属性。当用户浏览商品时，如果是旧用户，则先获取用户的注册信息，根据其历史购物记录，隐性初步获取其偏好。然后获取用户所浏览商品的信息，如商品种类、商品的尺寸、商品的外观描述等，从而显性获取目标商品的属性[9]。然后将采集的信息传递给推荐算法模块，推荐算法模块根据用户浏览的商品信息分别进行关联规则与属性规则匹配，从而生成推荐商品列表。

2.4 推荐结果综合处理模块

在获取用户信息之后，将提取的商品信息与关联规则和属性规则匹配，生成推荐结果，完成商品的Top-N推荐。

首先，根据目标商品信息，匹配关联规则，生成关联规则推荐列表；然后按照支持度计数排序，若是旧用户，需去除用户购买过的商品，取前N项作为关联规则推荐的最终结果，并记为Result_s；另外，根据提取商品的不同属性，分别匹配属性规则，取前N项作为属性规则推荐的最终结果，并记为Result_a。

则最终推荐给用户的商品为

Result=(1-weight)Result_s+weight×Result_a

(10)

其中，weight为属性规则推荐结果所占权重[14-15]。

3 模型推荐实例

表1为事务数据库 包含的交易数据，表2表示每一个项的属性信息，设支持度阈值为0.2，置信度为0.5，N=2，weight=0.5。

表1 事务数据库

表2 商品属性

产生推荐列表的过程如下：

(1)根据支持度阈值以及设定的置信度，得到频繁1-项集{I1:6;I2:7,I3:5,I4:4,I5:3,I6:2}；关联规则：{I1⟹I2I4,I2⟹I1I4,I1I2⟹I4,I4⟹I1I2}；属性规则：{A0⟹I1I4,A1⟹I2I3,B0⟹I2I3,B1⟹I1I4I5}；

(2)设用户当前输入为I1，获取I1的两种属性值A0、B1，再分别匹配关联规则与属性规则，通过匹配关联规则产生推荐列表：I2、I4；匹配属性规则产生推荐列表：I1、I4、I5。由于weight=0.5，即属性规则推荐结果占最终推荐结果的1/2。为避免新商品的冷启动问题，在关联规则与属性规则中分别随机选取一件商品，组成最终的推荐列表，如{I1I5}。

若用户输入的商品项匹配不到关联规则，如I6，则可匹配属性规则，产生推荐列表{I2I3}。

4 结束语

本文设计的推荐模型，在采集用户信息时，采用显性与隐性相结合的方式，既客观获取用户的偏好，又动态实时获取最新数据，使数据更能反映出用户的兴趣[16]；本文首次提出属性规则概念来描述商品属性与用户偏好的关系，根据历史购物数据，生成属性规则，采用关联规则经典算法Apriori，利用矩阵计算频繁项集，只扫描数据库一次，产生关联规则；采用属性规则与关联规则相结合的方式来产生推荐列表，并根据用户对象不同，利用不同的权重系数来调整推荐结果，使整个推荐系统更加有效可行。

[1] 王国霞,刘贺平.个性化推荐系统综述[J].计算机工程与应用,2012,48(7):66-76.

[2] 许海玲,吴潇,李晓东,等.互联网推荐系统比较研究[J].软件学报,2009,20(2):350-362.

[3] 马宏伟,张光卫,李鹏.协同过滤推荐算法综述[J].小型微型计算机系统,2009,30(7):1282-1288.

[4] 文俊浩,舒珊.一种改进相似性度量的协同过滤推荐算法[J]. 计算机科学,2014,41(5):68-71.

[5] 孙冬婷,何涛,张福海.推荐系统中的冷启动问题研究综述[J].计算机与现代化,2012(5):59-63.

[6] 于洪,李俊华.一种解决新项目冷启动问题的推荐算法[J]. 软件学报,2015,26(6):1395-1408.

[7] Agrawl R,Srikant R.Fast algorithms for mining assoeiation rules[C].Santiago,Chile:Proe of the 20th International Conference on Very Large Data Bases,1994.

[8] 李超,余昭平.基于矩阵的Apriori算法改进[J].计算机工程,2006,32(23):68-69.

[9] Pang-Ning Tan,Michael Steinbach,Vipin Kumar.数据挖掘导论[M].2版.范明,范宏建,译.北京:人民邮电出版社,2011.

[10] 菅志刚,金旭.数据挖掘中数据预处理的研究与实现[J].计算机应用研究,2004,21(7):117-118,157.

[11] 罗昌银.一种基于动态排序的最大频繁项集挖掘算法[D].重庆:重庆大学,2010.

[12] 李杰,徐勇,王云峰,等.面向个性化推荐的强关联规则挖掘[J].系统工程理论与实践,2009,29(8):144-152.

[13] 杨泽民.数据挖掘中关联规则算法的研究[J].软件,2013(11):71-72,92.

[14] 陈君,唐雁.基于Web社会网络的个性化Web信息推荐模型[J].计算机科学,2006,33(4):185-187,193.

[15] 李忠俊,周启海,帅青红.一种基于内容和协同过滤同构化整合的推荐系统模型[J]. 计算机科学,2009,36(12):142-145.

[16] 杨引霞,谢康林,朱扬勇,等.电子商务网站推荐系统中关联规则推荐模型的实现[J]. 计算机工程,2004,30(19):57-59.

Design of Recommendation Model Based on Attribute Rule and Association Rule

YU Pengcheng，LI Ye

(School of Optical-Electrical and Computer Engineering, University of Shanghai for Science and Technology,Shanghai 200093, China)

Currently, as an effective method to mining potential demand of the users，recommendation system is applied more and more widely. However, in order to solve the problem how to describe the relationship between the attribute of commodity and users’ preferences, this paper proposes the concept of attribute rules in first time. For the cold start problem of recommendation system, we design a new recommendation model by combining attribute rules and association rules; we use Apriori algorithm and matrix operation to mining association rules and avoid the problem of scanning database repeatedly in the process of generating frequent item sets. At the same time, using the support of frequent item set to generate attribute rules; Finally, match two kinds of rules and generate the final Top-N recommendaion list.

attribute rules; association rules; recommended system; Apriori algorithm

2016- 04- 20

沪江基金资助项目(C14002)

余鹏程(1989-)，男，硕士研究生。研究方向：数据挖掘和机器学习。李烨(1974-)，男，高级工程师。研究方向：工业控制与监测等。

10.16180/j.cnki.issn1007-7820.2017.03.008

TP301.6

A

1007-7820(2017)03-026-04