基于交替最小二乘法和规则匹配的菜品推荐

金琪文，王先传，彭 亮，王顺杰，陈秀明

（阜阳师范大学 计算机与信息工程学院，安徽 阜阳 236037）

随着社会节奏的加快，人们在一日三餐健康关注度上呈现渐低的情况，不合理的饮食结构,导致了一系列的健康问题。目前，推荐算法一般是针对网上购物领域的比较多，熟知的企业有淘宝和亚马逊，但在菜品推荐方面研究较少。

受限于健康科学知识的了解，人们希望通过互联网帮助自己规划一日三餐的饮食。随着大数据和互联网时代的到来，网络信息爆炸式增长，逐渐超越了个人接受、处理和有效利用的范围，并且人们开始逐渐在海量的食品信息中迷失自我。所以，如何从海量的膳食数据中找到符合自身的食谱信息，已经成为越来越多的用户面临的重大问题。目前市场上的饮食推荐系统的推荐结果比较单一化，多是注重用户喜好[1-4]，忽视了一日三餐的饮食搭配对身体的长期影响。

1 相关研究

在信息时代，个性化推荐类算法成为了一个重要研究方向，延伸出了包括基于用户、项目分类、内容、社会网络等推荐算法[5-10]。其中：基于用户的协同过滤推荐算法存在矩阵稀疏问题，而且不能对用户的兴趣进行动态衡量[11-12]；基于项目分类的协同过滤算法虽然一定程度上解决数据稀疏性问题，但计算相似度稳定性不佳[13-14]；基于内容的推荐算法的基本思想是计算用户未购买的项目和当前用户过去选择的项目的相似度[15]，其特点是不需要用户评分数据，没有数据稀疏性问题影响，但无法构建用户偏好模型。伴随着多种社交软件的兴起，社会网络数据的推荐算法大多从用户间的社会关系角度出发，仅认为相互信任的朋友间具有相似的兴趣爱好，而忽视了推荐对象之间的关系对推荐结果的影响[16]。对于基于语境感知数据的推荐算法是区别于基于用户和项目分类的推荐算法，通过上下文信息和场景信息进行预测推荐，但由于饮食菜谱的多维复杂性，该算法的推荐质量表现较普遍化。基于深度学习的推荐算法通过感知特殊数据格式，但由于其大规模、数据异构复杂度较高、分布不均匀等问题，目前还有诸多应用于推荐引擎上的挑战[17-18]。

本文首先采用基于矩阵分解的ALS算法得到推荐列表，然后根据膳食搭配以及用户特殊需求，采用规则匹配方法优化推荐列表，给出基于多维度规则匹配的推荐列表的辅助优化算法。

2 菜品推荐算法

2.1 菜品推荐流程

首先，收集用户行为日志作为初始数据，然后对初始数据进行预处理得到用户偏好数据，再将用户偏好数据和ALS推荐算法模型结合得到推荐列表，再基于用户身体状况和特殊需求，利用规则匹配算法优化推荐列表，推荐列表获取的流程如图1所示。

2.2 交替最小二乘法

交替最小二乘法(alternating least square，ALS)，属于机器学习中的协同过滤推荐算法[19]，同时它也属于混合推荐（collaborative filtering，CF）算法。考虑用户和菜品两个方面，于是可以使用一个三元组:＜User，Item，Rate＞来表示用户、菜品和评分之间的关系。表1是用户对菜品的评分结构，其中u1～u3，v1～v4分别表示用户和菜品，这里通过加入一定的规则评分设计辅助收集评分数据，如点击(1 分)，搜索(2 分)，收藏(3 分)，购买(4 分)，未评分的为0分等。

图1 菜品推荐流程图

表1 用户对菜品的评分结构

将用户对菜品的评分矩阵分解为用户对菜品隐含特征的偏好矩阵和菜品所包含的隐含特征矩阵，利用ALS算法将分解出的矩阵进行多次迭代，使得评分矩阵缺失项得到补充[20]。ALS算法可以使用公式（1）描述。

其中：U表示用户对菜品的隐含的特征偏好矩阵；D表示菜品自身隐含的特征偏好矩阵；rij表示用户ui对菜品vj的评分；函数f的目标是使特征矩阵U和D尽可能的逼近rij组成的评分矩阵R；I表示评分矩阵中的评分集合；Ui表示用户ui隐含的偏好特征向量；Dj表示菜品vj包含的隐含特征向量；表示用户ui的评分次数；λ是正则项系数；表示用户ui对菜品vj的偏好的预测值。作用是预防出现过度拟合问题[20]。

ALS的求解思路：首先将U当做常量，求解出D；然后把D当做常量求解出U。反复上述过程，使U和D在满足一定条件下逼近原始的评分矩阵R。

2.3 基于规则匹配的算法

虽然ALS解决了个性化饮食推荐的问题，但对于膳食搭配和用户特殊需求的满足能力不足，这里使用基于规则匹配算法优化ALS算法得到的推荐列表。

基于规则匹配算法如算法1。

images/BZ_55_288_1112_1171_1171.pngInput:ALS的推荐列表Top20 Output：优化后的推荐列表Top10 Step 1:构建用户身体状况表、菜品营养表、食补知识表和食材禁忌表Step 2:依据Setp 1中的4种表构建优化规则Step 3:使用优化规则对TOP20推荐列表进行优化Step 4:选择优化后的TOP10推荐给用户

在Step 1中，用户身体情况一般包括基本身体情况和特殊身体情况，基本身体情况（体重、出生年月、身高、最近目的、口味偏好）和特殊身体状况(最低眼视力、沙眼、最高耳听力、眼疾、耳疾、鼻疾病、口腔、血压、皮肤、肺活量、肝、脾、四肢、关节、平跖足、既往病史、血糖、脉搏)。

收集常见的24种营养素：热量、脂肪、纤维素、维生素C、胡萝卜素、核黄素、胆固醇、钙、锌、锰、磷、硒、碳水化合物、蛋白质、维生素A、维生素E、硫胺素、烟酸、镁、铁、铜、钾、钠、维生素 B。每100 g原食材的营养素含量表（部分），如表2。

根据菜品各种主料和配料的食材使用含量，再结合表2，计算出每100 g菜品的营养素含量表，如表3所示（部分）。例如，西红柿炒蛋的主料是鸡蛋150 g、番茄300 g，调料是大蒜5 g、大葱5 g、食盐 3 g、白砂糖 5 g、味精 2 g[21]，则西红柿炒蛋的钠含量计算如下：

表2 每100 g原食材的营养素含量表（部分）

表3 每100g菜品的营养素含量表（部分）

食补知识表由功能名称、推荐原材料、推荐食谱构成，如表4。食材搭配禁忌表由食材、相克食材、相克关系描述构成，如表5。在Step 2中，基于身体异常状况，当菜品的营养素含量有益于身体异常状况的改善时，将相应菜品的权重增加i个，当菜品的营养素含量会不利于身体异常状况的改善时，将相应菜品的权重减少j个，得到部分优化规则如规则1和规则2。

规则1：有益身体状况→增加i个权重；

规则2：不利身体状况→减少j个权重。

表5 食材搭配禁忌表（部分）

下面以具体实例描述Step 3和4的过程。以高血压的菜品优化推荐列表流程为例，如图2。

首先检索用户身体状况库发现该用户有高血压症状，其它身体指标正常，对推荐列表TOP 20种菜品进行权重更新；使用优化规则，根据菜品营养表、食补知识表，即当菜品每100 g钠含量＜350 mg时，增加该菜品4个权重，当菜品每100 g钠含量＞600 mg时，减少该菜品3个权重，提高清淡和有益降血压菜品的权重，降低含钠量大的菜品权重。如表3部分所示，西红柿炒蛋、蒜泥菠菜的每100 g钠含量＜350 mg，土豆烧肉的每100 g钠含量＞600 mg，故对西红柿炒蛋、蒜泥菠菜增加4个权重，对土豆烧肉减少3个权重。

表4 食补知识表（部分）

图2 高血压状况的菜品推荐优化流程

下面结合食品搭配禁忌表排除发生食品搭配禁忌关系的菜品，如发现推荐列表中的韭菜炒鸡蛋和蒜泥菠菜是搭配禁忌，通过权重进行比较，剔除权重相比较低的菜品，如果权重相等，随机排除其中一种菜品，将排除的菜品权重更新为-1（代表菜品已经从推荐列表中剔除），得到了优化后的菜品推荐列表，如图2(b)。最后，按照权重从高到底的顺序从优化后的推荐列表中选择TOP 10的菜品推荐给用户，如图2(c)，优化过程结束。

3 实验

3.1实验环境与数据

使用3台实验计算机构建出一个主节点和二个从属节点，并且每台计算机安装CentOS 7操作系统，采用SSH工具实现三台计算机的相互连接访问。其中实验软件包括：JDK1.7、Spark1.2.2；开发工具：IDEA。

食材和菜品资源数据来自薄荷网和美食杰。从薄荷网爬取食材的名称、食材营养成分及含量、菜品的名称、主料、调料和各食材使用含量。从美食杰上爬取疾病调制食品原料和禁忌食品原料、功能性调制食品原料和菜品等。通过对所爬取的信息进行冗余数据的剔除以及缺失数据的填充等清洗数据工作后存入数据库，同时包括菜品评分数据，构建出数据量在122 019条的数据集。

3.2 实验设计

实验设计包括：1）ALS和ALS+规则匹配算法的准确率对比实验；2）分布式环境下的ALS和ALS+规则匹配算法的运行时间对比实验。

准确率对比测试。评价标准采用均方根误差衡量个性化推荐算法的准确率[22]，如公式（2）

其中rij表示用户i对菜品j的历史评分，表示rij的预测值，T表示测试集中标注的集合，|T|表示测试集中标注的个数。

分别选取 20 000、40 000、60 000、80 000、100 000条数据，在Spark上实现ALS和ALS+规则匹配算法的运行时间对比实验。

3.3 实验结果与分析

实验时，在不同数量的实验数据上，首先仅使用ALS算法，然后再采用ALS与规则匹配相结合的算法进行实验，实验结果如图3。

图3 准确率对比实验结果

由图3可知，实验数据增大时，ALS算法的均方根误差呈现上升趋势，而ALS+规则匹配算法均方根误差呈现下降趋势，达到较为满意的预期效果。当实验数据量为20 000和40 000时，两个算法的均方根误差基本一致；当数据量大于40 000时，ALS算法的均方根误差呈现上升趋势，ALS+规则匹配算法的均方根误差呈现稳定缓降趋势；当数据量大于60 000时，ALS算法的均方根误差上升趋势显著，ALS+规则匹配算法的均方根误差下降趋势明显。对结果进行分析，可能原因如下：随着用户个性化需求属性的增加，ALS算法渐渐难以满足这一复杂的个性化需求，这是由于ALS算法主要是基于用户评分数据进行计算，而ALS+规则匹配即满足用户的食品喜好需求，而且通过结合用户的身体状况、食品、食疗、食品搭配禁忌知识库对ALS的推荐结果进行反复迭代和重新排序，从而满足了用户的“喜好+健康”需求。

由图4，可以发现ALS和ALS+规则匹配算法在运行时间上相差较小。随着数据量的增加，ALS和ALS+规则匹配算法的运行时间呈线性趋势上升。在不同数据量时，两者运行时间大致相同。分析原因如下：ALS+规则匹配算法主要是基于ALS算法生成的推荐列表，规则匹配主要是对推荐列表进行优化，对算法的时间复杂度影响不大，因此，当数据量相同时，ALS算法和ALS+规则匹配算法两者的运行时间相差很小。

图4 运行时间对比实验结果

4 小结

本文针对用户对饮食的营养搭配关注度不高的需求问题，首先采用基于矩阵分解的ALS算法对用户偏好数据进行了处理，获得了初步的饮食推荐列表，然后再利用营养搭配数据库和用户特殊需求等数据，使用规则匹配算法优化了推荐列表。实验数据表明，随着数据量增大，该算法具有较低的均方根误差。这说明该算法获得的饮食推荐列表在营养搭配方面一定程度上是合适的。目前，该算法还有较多不完善之处，如算法准确率的提升、超大数据量的算法准确率测试和算法改进、菜品推荐依赖数据维度不够、膳食搭配合理性解释等，有待改进或解决。未来将继续针对食品/菜品推荐算法做更近一步的研究，在推荐中融入对算法的性能优化和用户中医体质数据等信息。