基于关联规则的餐饮服务智能推荐系统

张奥多 张昕 李怡婷

摘 要：为了节省客户的点餐时间，方便客户从海量菜品中找到理想的菜品，本文尝试将关联规则与餐饮服务相结合.通过引入FP-tree关联规则算法，并利用得到的菜品推荐公式中的关联度指标，再综合商家利益最大化、热销菜品等因素及其重要程度创建菜品推荐综合评分公式.基于综合评分对各菜品进行推荐排序，排序结果最终以移动方式推送给顾客，实现菜品动态推荐服务.

关键词：个性化；推荐系统；数据挖掘；关联规则

中图分类号：TP274∶TS97 文献标志码：A

0 引言

近年来，随着互联网的飞速发展，人们的日常生活中产生了越来越多的数据信息，如此大量的数据信息满足了用户在大数据时代对数据的需求[1].基于互联网的智能推荐系统在人们的生活中占了越来越大的比重.智能推荐系统主要技术手段是数据挖掘技术[2-3]，即基于用户喜爱商品的行为，相关网站通过算法在全网的商品库里匹配然后进行推荐.智能推荐通常是将当前热门的、用户以往收藏或者购买的风格和用户类似喜好的风格的物品推荐给用户.餐饮服务智能推荐系统是针对智能推荐系统的进一步细化，作为必不可少的衣食住行之一的餐饮行业，与人们的生活密不可分，而在就餐时，顾客经常在大量的菜品信息中，无法真正找到自己想要的菜品.因此，就应运产生了餐饮服务智能推荐系统[4].

其中，菜品智能推荐系统是餐饮服务智能推荐系统的进一步细化，它的任务是将菜品呈现在顾客面前，一方面帮助顾客发现他们感兴趣的菜品，另一方面让餐饮企业期望推荐的菜品能够展现在对它有兴趣的顾客面前，从而实现餐饮消费者和餐饮企业的双赢.菜品智能推荐是帮助顾客发现合适的菜品，克服信息过载的方法.通过分析顾客的行为，对顾客兴趣建模，从而预测顾客的兴趣和喜好，并给顾客做相关联的菜品推荐.

1 工作流程及具体实现

1.1 推荐系统的工作流程

动态菜品智能推荐系统的工作流程包括菜品数据采集、菜品数据预处理、菜品推荐综合评分、动态智能推荐.流程图如图1所示，具体步骤如下：

Step 1 菜品数据采集：从餐饮企业采集用于计算菜品综合评分相关的数据，如顾客点餐数据、各类菜品单价成本数据、店家主推菜品数据等.

Step 2 菜品数据预处理：菜品数据预处理主要是对采集的数据进行清洗、数据变换，将原始数据转换成“适当的”格式，以适应后续计算菜品推荐综合评分的需要.通过数据预处理后将得到菜品热销度评分、店家主推度修正系数、菜品毛利率修正系数、菜品关联度修正系数.

Step 3 菜品推荐综合评分：从菜品热销度、店家主推度、菜品毛利率、菜品关联度等维度来计算某项菜品的推荐分值，菜品推荐分值大小一方面反映了顾客对菜品的喜好度，另一方面反映了餐饮企业对菜品主动推送的期望度.

Step 4 动态智能推荐：基于综合评分可对各菜品进行推荐排序，排序结果最终以移动服务的方式推送给餐饮点餐顾客，实现菜品动态推荐服务.

1.2 菜品数据预处理

菜品数据的预处理主要对采集的数据进行清洗、数据变换，通过数据预处理后将得到店家主推度修正系数、菜品热销度评分、菜品毛利率修正系数、菜品关联度系数.数据预处理的具体步骤如下：

Step 1 菜品热销度评分是根据餐饮企业最近30天的菜品销售记录，汇总后的排名经规范化后的计算得分，最高为1分，最低为0分.

？酌热销度评分=（1）

式（1）中：？酌热销度评分——某项菜品的热销度评分，取值范围：0～1；Qi——某项菜品的销售份数，其值大于0；Qmax——该餐饮企业最近30天内有销售记录的菜品中的最大销售份数；Qmin——该餐饮企业最近30 天内有销售记录的菜品中的最小销售份数.

Step 2 店家主推度修正系数是针对新推出的菜品做出排序得分，最高为1，最低为0.1，系数越高表示店家越期望推荐给顾客.该系数由管理员在前台界面维护设置，如表1所示，其中对于未设置主推系数的菜品，主推系数默认为0.1.

Step 3 菜品毛利率修正系数是根据菜品的单价和成本计算得到毛利率，再经归一化后得到的结果.

？酌毛利率=■（2）

式（2）中：？酌毛利率为某项菜品的毛利率修正系数，取值范围：0.1～1，当值为负时设为0.1；？籽单价为某项菜品的单价，？籽成本为某项菜品的估计成本.

Step 4 菜品关联度修正系数是基于历史点餐数据，采用FP关联规则算法[5]得到菜品的关联度推荐评分值，再经归一化后的结果，反映了各菜品与顾客已點菜品的关联程度.

关联规则[6-7]是形如X→Y的函数（X项集和Y项集不相交）.引入两个概念用来衡量关联规则的强度.一是支持度（support），用于确定规则可以对给定数据集的频繁程度；二是置信度（confidence），用于确定项集Y在包含项集X的事务中出现的频繁程度.

支持度（s）形式定义：

s（X→Y）=■ （3）

置信度（c）形式定义：

c（X→Y）=■（4）

支持度很低的规则出现，很可能只是偶然，所以可以确定阈值来删去那些没有意义的支持度较低的规则.

一般对于给定的规则，置信度与包含的事务中出现的可能性成正比关系，即置信度越小，包含事务中出现的可能性也就越小.而在特定的支持度和置信度阈值下，即使数量很少的原数据集也会产生难以计算的关联规则，故本文介绍的餐饮服务智能推荐系统采用FP增长算法，根据最小支持度阈值找出频繁项集，得到频繁项集之后，再由频繁项集产生满足一定支持度和置信度条件的强关联规则.

1.3 推荐系统的具体实现

1.3.1 基于关联规则的推荐算法

经过数据预处理后，基于关联规则的餐饮服务智能推荐算法的描述如下：

引进FP-tree算法[8]，该算法只进行两次菜品数据库扫描，直接压缩数据库成一个频繁模式树并生成关联规则.

算法關键步骤：Step 1利用菜品数据库中的数据构造FP-tree；Step 2从FP-tree中挖掘频繁模式.

1） 构建FP-tree

如表2所示的一个菜品数据集，它包含10个菜品组和5种菜品.

在第一次扫描历史点餐数据集之后，得到所有项的支持度度量计数.由于支持度很低的规则出现很可能只是偶然，所以将非频繁项丢弃，然后将频繁项按照支持度的递减顺序排序.

随后进行第二次扫描，构建FP-tree.读入第一个菜品组之后，创建标记结点；然后形成路径，对该组菜品编码，该路径上的所有结点的频度计数为1.

读入第二组菜品后，为菜品项创建新的结点集；然后，连接结点形成一条代表该菜品组的路径，该路径上每个结点的频度计数等于1.尽管前两个菜品组都具有共同一个菜品，但是它们的路径不相交，因为这两个菜品组没有共同的前缀.

第三个菜品组与第一个菜品组共享一个前缀，所以第三个菜品组的路径与第一个菜品组的路径部分组合.因为它们的部分路径相同，于是将菜品结点的频度计数增加为2，而新创建的结点的频度计数均等于1.图2为读入前3个菜品组之后的FP-tree的结构.

继续该过程，直到每个菜品组都映射到FP-tree的一条路径，读入第10个菜品组之后的FP-tree的结构如图3所示.

2） FP增长算法产生频繁项集

FP增长（FP-growth）是对FP-tree自F而上的方法进行探索产生频繁项集的算法[9].算法首先查找以菜品e结尾的频繁项集，然后使用FP-tree增长算法发现以e结尾的频繁项集，如图4所示.接下来是菜品d，菜品c和菜品b，最后是菜品a.

先收集包含菜品结点的所有路径，这些初始的路径称为前缀路径[10]（prefix path）.

由前缀路径，通过把与菜品结点相关联的支持度相加得到菜品的支持度计数.假定最小支持度为2，由于菜品e的支持度为3大于2，所以它是频繁项集.需要找到那些以菜品de，ce，be和ae结尾的频繁项集的子问题，并加以解决.在此之前，必须先找到前缀路径，然后将其转化为条件FP-tree.条件FP-tree与FP-tree结构上类似，但条件FP-tree可以用来发现以某特定后缀结尾的频繁项集.条件FP-tree通过以下步骤得到.

Step 1 首先，重新计算前缀路径上的支持度度量，因为某些度量包含那些不含菜品e的菜品组；

Step 2 删除菜品e的结点，修剪前缀路径.原因是沿这些前缀路径的支持度度量已经更新，发现以de，ce，be，ae结尾的频繁项集的子问题不再需要菜品结点的信息；

Step 3 当重新计算沿前缀路径上的支持度度量后，一些项的频繁状态可能会发生改变.例如，菜品b只出现了一次，它的支持度为1，意思是同时包含菜品b和菜品e的组合只有一个.因为任何以菜品b，e结尾的菜品项集肯定不是频繁项集，所以在将来的研究中可以直接忽略菜品b.

在找到菜品a和e结尾的频繁项集的子问题之后，可以通过FP增长，使用菜品e的条件FP-tree来找到并解决.首先需要找到以菜品a和e结尾的频繁项集，可以从菜品的条件FP-tree来发现菜品a的前缀路径；然后利用菜品结点d相关联的频度计数求和，得支持度计数为2的频繁项集；之后构建菜品de的条件FP-tree.重新计算了支持度度量并修剪了不是频繁项集的菜品c.原因是该条件FP-tree只包含了菜品a（支持度等于最小支持度的项），算法在找出频繁项集之后转到其他子问题，最后产生的频繁项集是以菜品ce结尾.在修剪完菜品的前缀路径后，只发现项集{c，e}是频繁的，在此之后，待算法继续处理之后的子问题时会发现只有项集{a，e}是频繁项集.得到频繁项集后，将它们各自全排序之后再输出.

3） 产生强关联规则

前面已经用最小支持度阈值找出所有的频繁项集，接着再使用最小置信度阈值由频繁项集产生强关联规则.

先验原理：确定一个项集，假定该项集是频繁的，那么其所有子集也肯定是频繁的.

由先验原理知如果频繁项集存在，那么其频繁子项集必然存在.故对于频繁项集，计算其对应频繁子项集的置信度，使用频繁项集的支持度除以对应频繁子项集的支持度得到频繁项集的置信度.

若菜品置信度大于设定的阈值，则将它们输出，并对它们的置信度归一化后作为对应的关联度.

1.3.2 菜品推荐综合评分

本文所述的菜品推荐系统是对菜品关联系数、店家主推、菜品毛利率、菜品热销度的综合考量，某项菜品推荐综合评分计算公式如下：

S综合评分=（E-Y）AYT（5）

其中：

E=（1，1，1，1）；Y=（？酌热销度评分，？酌店家主推度，？酌毛利率，？酌关联度）；A=，？琢1+？琢2+？琢3+？琢4=10.

S综合评分——某项菜品推荐综合评分，取值范围0～40；？酌热销度评分——某项菜品热销度的评分，取值范围0～1，？琢1为其权值；？酌店家主推度——店家对某项菜品的主推修正系数，取值范围0.1～1.0，？琢2为其权值；？酌毛利率——某项菜品的毛利率修正系数，取值范围0.1～1.0，？琢3为其权值；？酌关联度——某项菜品与已选菜品的关联度修正系数，取值范围0.1～1.0，？琢4为其权值.（注：4种评分因素分配的权值不同则菜品推荐综合评分的取值也会不同，但无论怎么分配，都不会超出0～40的范围.）

传统综合评分公式只能对每个指标加权求和得到综合评分，而该新公式在此基础上加入后缀影响因式，可以自行根据指标数值的情况提升重要指标（占权值较大的指标）排序时的优势地位，即权值较大的指标值越大，在总体中排序更具优势.但综合评分排序并不会完全按照权值大的指标的数值大小去排序，而是还会考虑其他指标的影响.

2 智能推荐系统的应用实例

为了验证新推荐综合评分算法的有效性，说明算法的优良特点，设计下面实验将此算法与一般综合评分算法进行验证和比较研究.

某顾客在某餐馆先点了皮蛋瘦肉粥，从该餐馆收集相关菜品数据如表3，它包含12个菜品组和20个菜品.

扫描表3菜品数据集，统计每个菜品的支持度计数如表4所示.

设最小支持度为2，丢弃非频繁项，得到频繁项，按照支持度递减的排序为：皮蛋瘦肉粥、排骨拼凤爪、香煎葱油饼、陈皮蒸牛丸、香煎葱油饼、特色蛋松、白灼生菜、上汤云吞面.

接着按照上述算法构建FP-tree和FP增长算法，产生以皮蛋瘦肉粥结尾的频繁项集，并将其中归一化后达到最小置信度0.40的具有强关联规则的项集输出：{排骨拼凤爪，皮蛋瘦肉粥}、{香煎葱油饼，皮蛋瘦肉粥}、{陈皮蒸牛丸、皮蛋瘦肉粥}、{香煎葱油饼、皮蛋瘦肉粥}、{特色蛋松、皮蛋瘦肉粥}，它们的置信度分别为：0.80，0.70，0.50，0.40，0.40.

整理与皮蛋瘦肉粥具有强关联规则的5个菜品的销售量、单价、成本的数据如表5示.

根据原始数据及式（1）—式（4），计算出热销度评分、毛利率、店家主推度、关联度.现将4种数据变量整理如表6所示.

根据经验设定权值，由传统综合评分公式和本文综合评分公式分别计算得到各菜品的综合分数如表7.

对比分析两种方法：由传统方法计算出的香煎葱油饼和特色蛋松的分数都是6，故当顾客先点了皮蛋瘦肉粥和乐膳虾饺皇，智能推荐这两菜品处于同等推荐位置，但显然是不合理的，因为香煎葱油饼与皮蛋瘦肉粥和乐膳虾饺皇关联度是0.7，远远大于特色蛋松与皮蛋瘦肉粥和乐膳虾饺皇的关联度0.4，香煎葱油饼应比特色蛋松更具有推荐优势位置，且香煎葱油饼和特色蛋松的分数差为1.184也在合理范围内，不会太悬殊.

特色蛋松和香煎韭菜饺的关联度都是0.4，特色蛋松热销度0.70，毛利率0.62，主推度0.90，对应香煎韭菜饺热销度0.85，毛利率0.60，主推度0.70，推测它们的推荐地位应该是比较接近的.而特色蛋松与香煎菜饺的改进式分数只相差0.033 5，比它们的一般式分数差0.225 0更符合实际.

3 结束语

本文致力于设计一种基于关联规则综合评分算法的餐饮服务智能推荐系统.根据已点菜品的关联度、商家利益最大化、热销菜品等因素，以及各因素的重要程度创建菜品推荐综合公式，基于综合评分对各菜品进行推荐排序，排序结果最终以移动方式推送给顾客，实现菜品动态推荐服务，帮助顾客快速发现自己感兴趣的菜品；同时餐饮企业发现了客户同时选择的多种菜品间的关联关系 ，并采取相应措施 ，既稳定了客户，营业利润也得到了相应提高[11]，从而实现消费者和餐饮企业的双赢[12].经验证，本文所提出的餐饮服务智能推荐系统优于传统的推荐算法，既能够兼顾顾客对菜品的兴趣爱好，又能有效的为餐饮企业提升菜品销售量，提高餐饮企业的收入.

参考文献

[1] 朱建军， 周强. 互联网信息生命周期研究[J]. 铁路计算机应用， 2015，24（3）：45-49.

[2] 沙志强. 数据挖掘技术在智能推荐系统中的研究与应用[D]. 北京：北京工业大学， 2005.

[3] 翟悦. 改进的关联规则挖掘算法在个性化推荐系统中应用[D]. 大连：大连交通大学， 2008.

[4] 廖旺宇. 基于关联规则的智能点餐推荐系统设计[J].四川烹饪高等专科学校学报， 2012（4）：32-36.

[5] 莫同， 褚伟杰， 李伟平， 等. 一种基于扩展FP-TREE的服务推荐方法[J]. 华中科技大学学报（自然科学版）， 2013（S2）：81-87.

[6] 张勇杰， 杨鹏飞， 段群， 等. 基于关联规则的商品智能推荐算法[J]. 现代计算机， 2016（7）：25-27.

[7] 張晶晶. 基于关联规则的电子商务智能推荐系统研究[D]. 鞍山：辽宁科技大学， 2012.

[8] 孙自广.FP-growth频繁集挖掘算法的分析与实现[J].广西工学院学报，2005，16（3）：64-67.

[9] YUAN J B，DING S L. Research and improvement on association rule algorithm based on FP-growth[J].Springer Berlin Heiclelberg，

2012，7529：306-313.

[10] 翁伟， 林开标， 朱顺痣， 等. 基于最长前缀频繁子路径树的Web日志挖掘算法[J]. 成都大学学报（自然科学版）， 2013， 32（3）：285-288.

[11] 韦艳玲.关联规则在健身服务项目组合中的数据挖掘[J].广西工学院学报，2008，19（2）：62-65，70.

[12] 张良均， 云伟标， 王路， 等. R语言数据分析与挖掘实战[M]. 北京：机械工业出版社，2015.

One intelligent recommendation system for catering service

based on association rules

ZHANG Ao-duo1，2， ZHANG Xin*1， LI Yi-ting2

（1. College of Mathematics and Informatics， South China Agricultural University， Guangzhou 510642， China；

2.TipDM Intelligent Technology Co.， Ltd.， Guangzhou 510670， China）

Abstract：With the advent of the information era， the relationship between e-commerce and data mining becomes closer， and personalized recommendation service gradually walks into our daily life. In order to save the time of ordering dishes， and to help customers find their favorite dishes from numerous dishes， this paper attempts to develop an intelligent recommendation system for catering service based on the association rules. We establish the comprehensive score formula of dish selection by introducing the FP-tree association rules， using the correlation index of the recommended formula and synthesizing some factors such as the maximum of benefits， hot dishes， etc. The dishes recommendation service is based on the rank of comprehensive score and the sorted results are finally pushed to the customer in a mobile way.

Key words： personalization； recommendation system； data mining； association rules

（學科编辑：黎 娅）