基于关联规则的智能点餐推荐系统设计

2012-01-26 02:36廖旺宇

四川旅游学院学报 2012年4期

廖旺宇

(四川烹饪高等专科学校，四川成都 610100)

随着餐饮企业信息化应用的不断深入，经营者在经营过程中可以采集到大量的客户点餐数据。但由于数据量过大，又缺乏有效的处理手段，因此，这些数据往往无法转化为帮助提升管理水平和经营业绩的知识。同时，客户在点餐过程中面对菜单中大量的菜品信息可能无法快速找到满意的菜品。运用电子商务和数据挖掘的知识，利用企业已经拥有的点餐数据，设计开发点餐推荐系统，有针对性地向客户推荐菜品，帮助其制定出更适合的食谱则成为有效解决上述问题的方法。

以商业目的作为依据，电子商务推荐系统分为面向产品的推荐和面向客户的推荐两类。常用的方法有Top N推荐法、新品推荐法和关联推荐法等。［1］所谓关联推荐法，主要指通过使用数据挖掘中关联规则挖掘技术，深入分析用户数据，得到用户的消费规则，并以此为依据进行消费推荐。

由Agrawal R等人提出的关联规则挖掘［2］已经成为数据挖掘领域的重要研究课题。但是，传统、经典的关联规则算法，如Apriori等，在目标数据集发生变化，甚至仅仅是最小支持度阈值发生改变时运行效率便会大幅度降低。为了在目标数据集中数据增加、减少和数据集不变，但最小支持度阈值发生改变［3-4］时高效获取关联规则，产生了增量关联规则挖掘算法。

在点餐推荐的实际应用中，一方面点餐信息数据在不断地增长，且随着时间的发展，菜品的流行程度也会相应发生改变;另一方面，在进行菜品推荐时往往更注重推荐某些重点菜品，使得用户往往只关注所获得的规则中与重点推荐的菜品相关的规则。

本文在原有的“适合高效更新的关联规则挖掘算法”［5］的基础上，根据上述点餐推荐实际应用的具体情况，提出了面向分类预测的增量关联规则挖掘算法。该算法可以通过分析已有的点餐数据，高效获取可能选取企业希望推荐的重点菜品的目标客户的点餐特征，作为向其他客户进行菜品推荐的依据。并且，算法可以保证在数据集中的数据发生增长时，有效减少对数据集重复扫描的次数、保证执行效率。最后，还在此基础上对点餐推荐系统的结构设计进行了研究。

1 面向分类预测的增量关联规则算法

1.1 算法基础［6］

设原目标数据集为DB，其包含的事务总数为|DB|，新增加的数据集为db，其包含的事务总数为|db|，DB+db为增加数据后的新目标数据集。

设数据集DB、db、DB+db的实际支持度计数分别为s0、s1、s2，则有s2=s0+s1。

为便于讨论，设fx=cx-sx(x=0，1，2)，显然有：若f≤0，则该候选项集为数据集中的频繁项集;若f＞0，则该候选项集为数据集中的非频繁项集，且f2=f0+f1。

性质1：若一个候选项集在DB中为频繁项集，且在db中为频繁项集，则该候选项在DB+db中为频繁项集。

证明：因为候选项在DB中为频繁项集，所以f0≤0，又：该候选项在db中为频繁项集，所以f1≤0，于是有f2=f0+f1≤0，即该候选项集在DB+db中为频繁项集。

性质2：若一个候选项集在DB中为非频繁项集，且在db中也为非频繁项集，则该候选项集在DB+db中为非频繁项集。

证明：因为候选项在DB中为非频繁项集，所以f0＞0，又：该候选项在db中为非频繁项集，所以f1＞0，于是有f2=f0+f1＞0，即该候选项集在DB+db中为非频繁项集。

性质3：若一个候选项在DB和db中分别为频繁项集、非频繁项集或非频繁项集、频繁项集，则该候选项集在DB+db中是否为频繁项集不确定。

证明：当一个候选项集在DB和db中分别为频繁项集、非频繁项集时，f0为负、f1为正;当一个候选项集在DB和db中分别为非频繁项集、频繁项集时，f0为正、f1为负。在这两种情况下都无法判断f2=f0+f1为正或为负，所以该候选项集在DB+db中是否为频繁项集不确定。

此时，只能通过将其在DB+db中的计数与(|DB|+|db|)*minsup比较进行判断。而该候选项集在DB+db中的支持度计数可以通过已知的其在DB和db中的支持度计数相加容易地得到。

因此，候选项集频繁与否的判断方式可以归纳为表1：

表1 正增量更新时候选项频繁状况判定表

由于本算法在对关联规则进行增量更新的时候，主要处理的是新增加的数据集db，且因为db的加入使得挖掘的目标数据集的大小呈现正增长，因此，本文又将本算法称为分类预测关联规则的正增量更新算法。

1.2 算法描述

正增量式分类关联规则挖掘算法分为两个步骤：首先，高效统计出新增数据集db中的每一非空项集的支持度计数;然后，利用该结果和已知的原数据集DB的挖掘结果，按照表1中的判定方法生成数据集DB+db满足用户指定的最小支持度阈值的频繁项集。

对于每一个项集都有一个count域来存储其支持度计数，算法描述如下：

算法1：统计各项集的支持度计数。

输入：新增的数据集db，项集I={i1，i2，…，im}。

输出：所有支持度计数非零的项集所产生的候选集C’，及C’中每一项集所对应的支持度计数。

算法描述：

1)初始化，令候选项集集合C’=Ø

2)设置关注的项目类别为项集中的项目ix

3)FOR all records t∈db do

3.1)FOR all itemsets c’⊆t do

3.2) 若c’包含项目ix

3.3) IF c’∈C’THEN //若c’存在于C’中

3.4) c’.count+ + //c’的支持度计数增加1

3.5) ELSE

3.6) C’=C’∪{c’} //将c’加入到C’中

3.7) c’.count=1 //设置其支持度计数为1

3.8) FOR all itemsets c’∈C’do //求当前候选项集合C’中各不包含项目ix的子集求支持度计数：

3.9) c’=c’-{ix}

3.10) IF c’∈C’THEN //若c’存在于C’中

3.11) c’.count+ +

3.12) ELSE C’=C’∪{c’}

//将c’加入到C’中

3.14) c’.count=1 //设置其支持度计数为1

由算法1，显然有：

定理1：由算法1所产生的候选项集的集合C’包含且仅包含数据库db中与项目ix相关的支持度计数非零的项集。

为方便讨论，本文假设已知原数据库DB的候选项集C和频繁项集F。若未知，则利用算法1，将输入的数据集改为DB，则将获得C，进而可以容易地获得F。

在已知原数据库DB中的C、F，以及新增加部分db的C’后，执行算法2将容易地获取到DB +db的频繁项集F，进而得到更新后的分类关联规则。

算法2［6］：

输入：最小支持度阈值minsup，候选谓词集C、C’，原数据集DB的频繁谓词集F。

输出：DB+db中具有最小支持的阈值minsup的所有频繁谓词集的集合F。

算法描述：

1)令C”=C+C’

2)//求db的频繁项集

令F’=Ø

2.1)FOR all itemsets f’∈C’do

2.2)IF f’.count≥|db|*minsup THEN

2.3) F’=F’∪{f’}

3)//以下为根据表1中的方法判断候选项集在DB+db中是否频繁

3.1)FOR all itemsets f”∈C”do

3.2)IF f”∈F THEN //若f”在DB中频繁

3.3) IF f”∉F’THEN //若f”在db中不频繁

3.4) f”.count=f.count+f’.count //计算f”支持度计数

3.5) IF f”.count≥(|DB|+|db|)* minsup THEN

3.6) F=F∪{f”}

3.7) ELSE F=F-{f”}

3.8) ELSE F=F∪{f”} //f”在DB中频繁，在db中也频繁

3.9) f”.count=f.count+f’.count

3.10)ELSE IF f”∈F’THEN //f”在DB不频繁，但在db中频繁

3.11) f”.count=f.count+f’.count //计算f”支持度计数

3.12) IF f”.count≥(|DB|+|db|)* minsup THEN

3.13) F=F∪{f”}

3.14) ELSE F=F-{f”}

3.15) ELSE F=F-{f”} //f”在DB和db中均不频繁

4) C=C”

2 算法有效性实验及结果分析

2.1 应用实例

设给定如表2所示的事务数据库DB［5］。其中：TID为事务标识符，标识每位顾客的一次点餐事务;Itemset为相应事务所包含的项目，即顾客所点的具体菜品标识符。

表2 事务数据库

本文以关注菜品A为例对算法进行了实验。并设原数据集DB所包含的数据为TID值是1—4的数据，TID值是5—8的数据为新增数据(即，db)。

原有数据集DB的候选项集C可以通过执行算法1容易地得到，进而快速地获取到DB的频繁项集F。因此，本文为方便讨论正增量关联规则更新情况下算法的有效性，假定已知原目标数据集DB的候选项集C和频繁项集F，有：

C={(A，3)，(B，3)，(C，3)，(D，1)，(E，2)，(F，1)，(AB，2)，(AC，2)，(AD，1)，(AE，1)，(AF，1)，(BC，3)，(BE，2)，(CE，2)，(DF，1)，(ABC，2)，(ABE，1)，(ACE，1)，(ADF，1)，(BCE，2)，(ABCE，1)}

其中：(x，y)∈C，则x表示DB中的项集，y表示其对应的支持度计数，下同。

设minsup=50%，则|DB|*minsup=2。此时，DB的频繁项集F为：

F={(A，3)，(B，3)，(C，3)，(E，2)，(AB，2)，(AC，2)，(BC，3)，(BE，2)，(CE，2)，(ABC，2)，(BCE，2)}

对新增的数据集db(表2中TID为5—8的记录)：

(1)执行算法1，产生db中所有支持度计数非零的候选项集C’，得：

C’={(A，2)，(B，3)，(C，3)，(D，1)，(F，2)，(AB，1)，(AC，2)，(AD，1)，(AF，1)，(CD，1)，(BC，2)，(BF，2)，(CF，2)，(ABC，1)，(ABF，1)，(ACD，1)，(ACF，1)，(BCF，1)，(ABCF，1)}

(2)执行算法2

①获取数据集db中的频繁项集F’。此时，F’中的项目所需满足的最小支持度阈值为minsup*|db|=50%*4=2，有：

F’={(A，2)，(B，3)，(C，3)，(F，2)，(AC，2)，(BC，2)(BF，2)，(CF，2)，(BCF，2)}

②对C”中的所有子集根据表1中的判断方式进行判断。

例如，在候选项集C”中：

a)项目A在DB和db中均为频繁项，因此，项目A属于频繁项集F。

b)项目E在DB中为频繁项，但在db中为非频繁项，需从全局判断其是否属于F。此时，各项目需满足的最小支持度阈值为minsup*|DB+db| =4，而项目E的支持度计数为2+0=2。因此，项目E不再是频繁项，需从F中删除。

c)项目F在db中为频繁项，但在DB中为非频繁项，需从全局判断其是否属于F。此时，各项目需满足的最小支持度阈值为minsup*|DB+db| =4，而项目F的支持度计数为0+2=2。因此，项目F不是数据集DB+db的频繁项。

d)项目D在DB和db中均为非频繁项，因此，也不是DB+db的频繁项。

在对C”中的所有子集都进行判断之后，便可得到DB+db的频繁项集F：

F={(A，5)，(B，6)，(C，6)，(AC，4)，(BC，5)}

2.2 算法分析及与原算法的比较

新算法只对相对较小的新增部分数据集db进行了两次扫描。首次扫描获取到支持度计数非零的、包含所关注的项目(如算法实验中关注项目A)的候选项集的集合，第二次扫描在首次扫描的基础上获得所有与关注项目相关的候选项集的集合，从而使得算法可以在更新关联规则第二个步骤快速获取频繁项集，进而得到计算频繁项集的所有非空子集是否满足最小置信度阈值(minconf)并得到更新后的关联规则。

由于本文改进后的新算法在更新正增量关联规则时，可以只扫描新增部分的数据集db，因此，以下只针对新增部分数据集db的实验结果与文章［5］中的原算法比较。实验结果表明，本文根据点餐推荐系统的实际提出的算法，在对与菜品项目A相关的关联规则获取过程当中所产生的候选项集C’，无论是单个k-候选项集(k=1，2，…，4)中项的数量，还是整个候选项集中项的总数均小于等于原算法，从而节约了算法运行所需占用的空间。具体结果分析见图1。

图1 候选项集中项的数量比较

且由于预先设置了所关注的项目，在获取频繁项集后，产生的关联规则结果的聚焦度更高，更加便于用户使用。

3 系统结构设计

基于面向分类预测的增量关联规则挖掘算法，本文提出了基于分类预测关联规则的点餐推荐系统的系统结构如图2所示。使用餐饮企业信息化系统中搜集的点餐数据作为数据源，在通过数据预处理使之成为适合进行数据挖掘的数据之后，便可利用面向分类预测的增量关联规则挖掘算法，寻找可能选择企业推荐菜品的消费者的点餐关联规则，并保存在规则库中备用。获取关联规则的过程比较费时，且关联规则的获取不必实时进行，因此可以利用离线周期获取规则。［7］在获取到用户的点餐意向或部分点餐信息后，根据关联规则，即可实时向客户推荐相关菜品。

图2 基于分类预测关联规则的点餐推荐系统结构

产生菜品推荐结果的步骤如下：

(1)根据餐饮信息化系统中每位客户的点餐历史数据库中选取相关字段，建立点餐事务记录集。并通过数据预处理使之成为适合进行关联规则挖掘的目标数据集。

(2)使用面向分类预测的增量关联规则算法对目标数据集进行关联规则挖掘。将结果存放至关联规则集合R。

(3)对每位当前客户ui(i∈N)，设置一个用户已选(意向)集合Iu、一个候选推荐集合Pu，并将Iu和Pu初始化为空。

(4)对每位当前客户ui，以Iu作为关联规则的左侧部分搜索关联规则集合R，得到用户支持的所有强规则的集合Ru。

(5)将集合Ru中，除顾客ui已经选择的菜品以外的、所有关联规则的右侧部分包含的菜品加入推荐候选集Pu中，并依据所属关联规则的置信度取值降序排序。若出现菜品被重复加入Pu的情况，则仅保留该菜品置信度取值的最大的一项。

(6)服务员依据情况，按照系统反馈的结果，按照置信度由高至低选择合适数量的菜品，推荐给顾客ui(i∈N)选择。

4 结束语

本文将电子商务中的推荐系统与关联规则挖掘相结合，在对传统关联规则挖掘算法研究的基础上，针对点餐推荐系统的应用实际，提出了面向分类预测的增量关联规则挖掘算法。该算法在继承了原“适合于高效更新的关联规则算法”［5］减少扫描数据库次数的优点的基础上，可以只扫描新增的少部分数据集就完成关联规则的更新，并使挖掘结果聚焦于用户关心的相关需推荐的菜品，有效减少了算法产生的候选项集的大小、节约算法运行空间，并通过实验验证了算法的有效性。在此基础上，还对基于分类预测关联规则的点餐推荐系统的结构进行了有益的探索和研究。

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

［2］Agrawal R et al.Mining association rules between sets of items in large databases［C］//Proceedings of ACM SIGMOD Conference on Management of Data，Washington DC，1993：207-216.

［3］冯玉才，冯建琳.关联规则的增量式更新算法［J］.软件学报，1998，9(4)：301-306.

［4］周海岩.关联规则的开采与更新［J］.软件学报，1999，10(10)：1078-1084.

［5］周海岩.适合于高效更新的关联规则挖掘算法［J］.小型微型计算机系统，2004，25(4)：634-637.

［6］廖旺宇.面向分类预测的增量关联规则应用研究［D］.四川师范大学，2010：21-24.

［7］索琪，卢涛.基于关联规则的电子商务推荐系统研究［J］.哈尔滨师范大学自然科学学报，2005，21(2)：50-53.