论文部分内容阅读
【摘 要】为了在解决儿童饮食问题,不仅要满足儿童的营养标准,同时还要满足儿童的喜好。为了解决这个问题,提出了一种利用Item CF算法和LFM模型来进行第一层推荐,然后基于FTRL算法来推荐最终儿童喜欢的食物,最后采用差分进化算法来进行食物的匹配及食谱的推送。该模型结合幼儿园现状,匹配出符合儿童营养标准的食谱。
【关键词】协同过滤;FTRL;多目标优化;个性化推荐;营养均衡
引言
近几年也有基于营养标准和食物个性推荐算法的相关研究,如利用协同过滤并且使用引入差分变 异策略算子的NSGA-2个性化健康饮食推荐方法[1],基于情境感知的校园餐饮推荐方法[2],利用粒子群,聚类和Slope one等算法的基于营养饮食推荐系统研究[3],食材搭配推荐算法 研究[4]则是利用了基于NSGA-2改进的MOGA-UP算法和BP算法。本文则在经典的协同过滤推荐算法LMF和Item CF的基础上,又利用Google用于广告点击率的FTRL- Proximal增量算法, 将这几种算法进行融合,最后利用加上一点改进,最终实现了较好的效果。本文提出的推荐系统会根据不断更新的用户对食物的喜好数据来训练模型,每次会推荐出一周的食谱,不仅考虑到了每个学生的口味和营养指标,而且还考虑到了学校对各种食材或原料的准备,方便学校进行对每个学生不同的套餐的准备。
1.相关工作
1.1基于矩阵分解的推荐算法——LFM模型
1.2基于物品的协同过滤算法——Item CF算法
Item CF算法是根据两个物品的相似度给用户推荐的,计算公式如下:
计算完相似度,得到相似度矩阵后。对于某个用户u,先找出用户u每一个喜欢的物品的最相似的前k个其他物品。以其中一个喜欢的物品i为例,将用户u对物品i的评分作为这个物品的权重,将与物品i最相似的k个物品的相似度与这个权重相乘,作为这k个未知物品分数的一部分,将所有用户u喜欢的物品按照以上方式计算后,将每一个物品的每一部分的分数相加就得到每一个物品的分数,按照这个分数将物品排序,取分数最高的几个物品推荐给用户。
经Karypis[7]研究发现,传统的相似度的计算有着一定的缺陷,若用户喜欢的物品有不同的类别时,类别A的物品之间的相似度可能会比类别B的物品之间的相似度高,在推荐时就会更偏向于推荐类别A的物品,而忽略了用戶喜欢的类别B的物品,所以Karypis提出了相似度矩阵的归一化。在得到相似度矩阵后,找到每一行的最大值,再将这一行的所有数除以这个最大值,从而上述只推荐A类物品的情况就可以得到抑制。
1.3 FTRl算法
FTRL算法属于增量学习算法,最早由谷歌的H. Brendan McMahan提出,以下公式来自于H. Brendan McMahan[8]的论文,与传统的机器学习算法不同,每次训练不需要处理所搜集到的全部数据,只需要处理部分数据即可,可以更容易的处理流式数据,所以在推荐领域有着广泛的应用。
FTRL与SGD类似,每次只需要处理一个数据,下式为FTRL的参数更新公式,
为超参数,T为样本总数,每次接收一个样本。先找出样本不为0的样本维度数,将这些维度数保存到I中,然后按照以上公式中对参数w中I中存在的维度数进行更新。然后根据更新的参数对这个样本进行预测,计算出损失函数,然后对其他参数进行更新。
1.4差分进化算法
差分进化算法最早是由R.Storn和K.Price为求解Chebyshev多项式而提出的,是遗传算法的一种,以下公式来源于R.Storn和K.Price[9]的论文。
(1)种群初始化:
其中是度第i个个体的第j维的下界,其中是度第i个个体的第j维的上界。
(2)变异(DE/best/1):
F为缩放因子,是一个常数,g表示的是第g代种群。若当前种群大小为n,则进行n次变异,生成n个变异向量。
(3)交叉:
对于每一个种群中的个体,找到序号对应的变异向量进行交叉。CR为交叉概率,若进行第j维的交叉时,生成的随机数小于CR,则这个个体交叉后的第j维为变异向量的第j维。反之则为原来的数。
(4)选择:
将进行变异交叉之后的个体向量与原个体向量进行比较,选取最优个体。
2.个性化饮食推荐系统的建立
2.1问题描述
儿童的餐饮问题一直有重要意义,合理搭配食谱,全面提高膳食质量水平是社会关注重点[10],健康饮食是搭配食谱的第一步,考虑儿童的口味和需求也十分必要。如今,幼儿园中的食谱搭配能满足儿童营养的需求,儿童的爱好和口味没有过多的进行了解,出现了虽然给儿童提供的饭菜营养均衡,但学生并不喜欢吃,达不到营养的均衡摄入的情况。为了解决这个问题,本文提出了基于营养标准的个性化食物推荐系统用于解决这个问题。
2.2个性化饮食推荐
对于食物的推荐,一个算法显然是不够的,需要多个算法进行融合才能达到较好的效果。
对于此食物推荐系统,总体上来说,分为两个部分,第一个部分是FTRL模型的训练,第二个部分是根据所训练的模型进行食谱的推荐。
(1)模型的训练。FTRL模型可以处理不断更新的数据。训练时要为每个班级及个人都训练一个模型,训练完成后将更新的参数保存起来。给班级训练模型是为了限制每顿饭学校需要做的菜的种类数,这是考虑到了现实的情况。因为如果只给每个学生训练模型,则在推荐时,每个人的菜可能都不同,学校可能就要每顿饭做几百种菜,这显然是不现实的,所以要训练每一个班级的模型,为每一个班级找出可能的喜欢人数最多的菜。
(2)食物的推荐。在为每一个学生推荐食谱时,首先考虑到的是所推荐的食物用户是否喜欢,然后才进行食物的匹配从而达到对11种营养物质的标准摄入。如果先考虑营养物质的摄入标准,若要达到较好的推荐效果的话就会需要差分进化算法匹配出很多误差较小的食物套餐,但是这会需要很多时间,所以应该先推荐再进行差分进化去匹配。 在推荐时先是使用了LFM模型和Item CF算法。首先使用LFM模型进行推荐,得到每个用户对每个食物的分数,然后使用Item CF算法,得到另一个分数,将这两个分数按照权重相加,得到总分,取前分数最高的k个食物。一个学校刚开始使用时由于学生对食物的喜好的数据少,而且食物的分布也可能很分散或有些学生口味与大众的口味很不同,就会导致有的学生会没有推荐的食物,即使有也可能会很少,所以如果Item CF算法推荐的食物很少,就需要LFM模型来补充,这时如果有一个食物两个算法的分数都有,就按照权重相加,取前几项,如果数量较少,剩下的就要按照LFM模型的分数从高到低来选取。
在LFM模型和Item CF算法运行完成之后,每一个学生就会得到推荐的食物。然后将这些食物进行整理,将每一个班级的食物汇总,汇总的同时去掉学校由于一些原因不能制作的菜。之后利用每一个班级的FTRL模型为每一个班级推荐,进行第一次筛选,减少食物种类的同时又不会对最终的推荐结果造成很大的影响。
最后在筛选出来的食物中为每一个学生推荐,在推荐时由于会有些学生口味很符合整个班级的,而有些学生的口味却很不符合,所以就会出现有的学生所推荐的食物很多,有些学生所推荐的食物很少。这时就要统计一下在一个班级中的每种菜的喜欢的人数,选取喜欢人数最多的前k种菜,对于每一个学生都只保留这k种菜,进行菜的种类数控制,如果存在学生的推荐菜数很少,就按照每种菜喜欢的人数多少来添加,直到有足够的数量进行接下来的差分进化。
2.3食物及其重量的匹配
给每一个学生推荐食物完成后就可以根据每个学生的食物进行食物种类及对应重量的匹配,从而满足各种营养的标准摄入量。每次对每一个学生进行差分进化前差分进化前要进行对学生身高,体重及性别的判断,大致确定这个学生缺少那些营养或者那种营养过多,从而实现营养标准的个性化。然后对这个学生的推荐食物进行编号,种群中的每个个体都由两种或三种食物组成,每种食物都有一个对应的重量,下图分别为一顿饭两种菜和三种菜的营养误差。每次差分进化都找出最优的五个个体,每天分配一个最优的个体,每个学生进行三次差分进化,分别对应早,中,晚三顿饭。
差分进化的每一个个体的适应度由下式计算:
其中x为种群中的一个个体,为第i种营养物质的权重,为个体的第i种营养物质的含量,为第i种营养物质的标准摄入量。每次差分进化的种群规模为25个,种群代数为80就可以找到较好的个体,而且运行时间较快。由于一个种群进化到最后种群中的个体的相似度都很大,所以在挑选其中的5个最好个体时要根据食物的种类进行去重,如果去重后的个体数少于5个就多次运行差分进化算法。
3.实验结果与分析
3.1实验结果
搜集到了大概有100人40天的食物喜好数据,本文只使用精确率(precision)作为性能度量的指标,计算公式为
因为考虑到了现实中学校不可能做很多种类的饭,所以限制了每次推荐出的食物种类数,所以推荐系统中常用的召回率以及F1值并没有太大的参考意义。经过训练后,得到了下图中所有同学的平均的精确率的增长曲线。
为了检验推荐系统的每一个部分都起到了作用,又将本文提出的推荐系统拆分开进行多次实验,下图为各种拆分方案的最终平均准确率。
推荐进行完成后,要进行食物的匹配,下图为进行一次差分进化过程中,误差的变化轨迹。
下图为差分进化出的个体的各个营养物质的平均误差。
3.2实验分析
在经过训练后,可以看出推荐系统的精确率达到了90%左右,在任意去掉此推荐系统的一部分后精确率都有不同的下降,说明几种算法的结合取得了较好的效果。在最后的不同食物的匹配过程中,可以看到误差在一次的差分进化中有着快速的下降,其中能量误差最小,在0.07%左右,而且在最后的结果中一些比较重要的营养物质的误差较小,脂肪的误差较大,在56.35%,除了脂肪和硒的误差较大以外,其他的误差都较小,而且并不都是缺少,也有营养多于标准营养,多余的部分的影响并不会很大。
4.总结
本文不仅使用了在食物推荐系统中最为常用的协同过滤算法,而且还结合了在食物推荐中少见的FTRL增量学习算法,在最后的基于营养标准的食物的匹配中,利用了差分进化算法,将每种营养标准与营养摄入量的差的绝对值以相应权值相加得到的数作为种群适应度。经过实验的测试,验证了本文提出的模型在解决儿童既要营养的均衡摄入也要符合个人喜好的难题时有着较好的效果。
参考文献
[1]方琦.个性化健康饮食推荐方法研究[D].长安大学,2018.
[2]王伟伟.基于情境感知的校园餐饮推荐方法研究及应用[D].太原理工大学,2018.
[3]刘兴姿.基于营养饮食推荐系统研究[D].西安电子科技大学,2019.
[4]梅子杰. 食材搭配推荐算法研究[D].重庆邮电大学,2018.
[5]项亮2012. 推荐系统实战. 北京市崇文区夕照寺街:人民郵电出版社. 197pp.
[6] Sarwar B M, Karypis G, Konstan J A, et al. Item-based collaborative filtering recommendation algorithms[C]. the web conference, 2001: 285-295.
[7] G. Evaluation of Item-Based Top- N Recommendation Algorithms[C]. conference on information and knowledge management, 2001: 247-254.
[8] Mcmahan H B, Holt G, Sculley D, et al. Ad click prediction: a view from the trenches[C]. knowledge discovery and data mining, 2013: 1222-1230.
[9] Storn R , Price K . Differential Evolution-A Simple and Efficient Heuristic for Global Optimization over Continuous Spaces[J]. Journal of Global Optimization, 1997, 11.
[10]丁汝金,杨慧,裴丹丹.农村留守儿童营养膳食调配分析[J].现代食品,2019(09):117-120+128.
【关键词】协同过滤;FTRL;多目标优化;个性化推荐;营养均衡
引言
近几年也有基于营养标准和食物个性推荐算法的相关研究,如利用协同过滤并且使用引入差分变 异策略算子的NSGA-2个性化健康饮食推荐方法[1],基于情境感知的校园餐饮推荐方法[2],利用粒子群,聚类和Slope one等算法的基于营养饮食推荐系统研究[3],食材搭配推荐算法 研究[4]则是利用了基于NSGA-2改进的MOGA-UP算法和BP算法。本文则在经典的协同过滤推荐算法LMF和Item CF的基础上,又利用Google用于广告点击率的FTRL- Proximal增量算法, 将这几种算法进行融合,最后利用加上一点改进,最终实现了较好的效果。本文提出的推荐系统会根据不断更新的用户对食物的喜好数据来训练模型,每次会推荐出一周的食谱,不仅考虑到了每个学生的口味和营养指标,而且还考虑到了学校对各种食材或原料的准备,方便学校进行对每个学生不同的套餐的准备。
1.相关工作
1.1基于矩阵分解的推荐算法——LFM模型
1.2基于物品的协同过滤算法——Item CF算法
Item CF算法是根据两个物品的相似度给用户推荐的,计算公式如下:
计算完相似度,得到相似度矩阵后。对于某个用户u,先找出用户u每一个喜欢的物品的最相似的前k个其他物品。以其中一个喜欢的物品i为例,将用户u对物品i的评分作为这个物品的权重,将与物品i最相似的k个物品的相似度与这个权重相乘,作为这k个未知物品分数的一部分,将所有用户u喜欢的物品按照以上方式计算后,将每一个物品的每一部分的分数相加就得到每一个物品的分数,按照这个分数将物品排序,取分数最高的几个物品推荐给用户。
经Karypis[7]研究发现,传统的相似度的计算有着一定的缺陷,若用户喜欢的物品有不同的类别时,类别A的物品之间的相似度可能会比类别B的物品之间的相似度高,在推荐时就会更偏向于推荐类别A的物品,而忽略了用戶喜欢的类别B的物品,所以Karypis提出了相似度矩阵的归一化。在得到相似度矩阵后,找到每一行的最大值,再将这一行的所有数除以这个最大值,从而上述只推荐A类物品的情况就可以得到抑制。
1.3 FTRl算法
FTRL算法属于增量学习算法,最早由谷歌的H. Brendan McMahan提出,以下公式来自于H. Brendan McMahan[8]的论文,与传统的机器学习算法不同,每次训练不需要处理所搜集到的全部数据,只需要处理部分数据即可,可以更容易的处理流式数据,所以在推荐领域有着广泛的应用。
FTRL与SGD类似,每次只需要处理一个数据,下式为FTRL的参数更新公式,
为超参数,T为样本总数,每次接收一个样本。先找出样本不为0的样本维度数,将这些维度数保存到I中,然后按照以上公式中对参数w中I中存在的维度数进行更新。然后根据更新的参数对这个样本进行预测,计算出损失函数,然后对其他参数进行更新。
1.4差分进化算法
差分进化算法最早是由R.Storn和K.Price为求解Chebyshev多项式而提出的,是遗传算法的一种,以下公式来源于R.Storn和K.Price[9]的论文。
(1)种群初始化:
其中是度第i个个体的第j维的下界,其中是度第i个个体的第j维的上界。
(2)变异(DE/best/1):
F为缩放因子,是一个常数,g表示的是第g代种群。若当前种群大小为n,则进行n次变异,生成n个变异向量。
(3)交叉:
对于每一个种群中的个体,找到序号对应的变异向量进行交叉。CR为交叉概率,若进行第j维的交叉时,生成的随机数小于CR,则这个个体交叉后的第j维为变异向量的第j维。反之则为原来的数。
(4)选择:
将进行变异交叉之后的个体向量与原个体向量进行比较,选取最优个体。
2.个性化饮食推荐系统的建立
2.1问题描述
儿童的餐饮问题一直有重要意义,合理搭配食谱,全面提高膳食质量水平是社会关注重点[10],健康饮食是搭配食谱的第一步,考虑儿童的口味和需求也十分必要。如今,幼儿园中的食谱搭配能满足儿童营养的需求,儿童的爱好和口味没有过多的进行了解,出现了虽然给儿童提供的饭菜营养均衡,但学生并不喜欢吃,达不到营养的均衡摄入的情况。为了解决这个问题,本文提出了基于营养标准的个性化食物推荐系统用于解决这个问题。
2.2个性化饮食推荐
对于食物的推荐,一个算法显然是不够的,需要多个算法进行融合才能达到较好的效果。
对于此食物推荐系统,总体上来说,分为两个部分,第一个部分是FTRL模型的训练,第二个部分是根据所训练的模型进行食谱的推荐。
(1)模型的训练。FTRL模型可以处理不断更新的数据。训练时要为每个班级及个人都训练一个模型,训练完成后将更新的参数保存起来。给班级训练模型是为了限制每顿饭学校需要做的菜的种类数,这是考虑到了现实的情况。因为如果只给每个学生训练模型,则在推荐时,每个人的菜可能都不同,学校可能就要每顿饭做几百种菜,这显然是不现实的,所以要训练每一个班级的模型,为每一个班级找出可能的喜欢人数最多的菜。
(2)食物的推荐。在为每一个学生推荐食谱时,首先考虑到的是所推荐的食物用户是否喜欢,然后才进行食物的匹配从而达到对11种营养物质的标准摄入。如果先考虑营养物质的摄入标准,若要达到较好的推荐效果的话就会需要差分进化算法匹配出很多误差较小的食物套餐,但是这会需要很多时间,所以应该先推荐再进行差分进化去匹配。 在推荐时先是使用了LFM模型和Item CF算法。首先使用LFM模型进行推荐,得到每个用户对每个食物的分数,然后使用Item CF算法,得到另一个分数,将这两个分数按照权重相加,得到总分,取前分数最高的k个食物。一个学校刚开始使用时由于学生对食物的喜好的数据少,而且食物的分布也可能很分散或有些学生口味与大众的口味很不同,就会导致有的学生会没有推荐的食物,即使有也可能会很少,所以如果Item CF算法推荐的食物很少,就需要LFM模型来补充,这时如果有一个食物两个算法的分数都有,就按照权重相加,取前几项,如果数量较少,剩下的就要按照LFM模型的分数从高到低来选取。
在LFM模型和Item CF算法运行完成之后,每一个学生就会得到推荐的食物。然后将这些食物进行整理,将每一个班级的食物汇总,汇总的同时去掉学校由于一些原因不能制作的菜。之后利用每一个班级的FTRL模型为每一个班级推荐,进行第一次筛选,减少食物种类的同时又不会对最终的推荐结果造成很大的影响。
最后在筛选出来的食物中为每一个学生推荐,在推荐时由于会有些学生口味很符合整个班级的,而有些学生的口味却很不符合,所以就会出现有的学生所推荐的食物很多,有些学生所推荐的食物很少。这时就要统计一下在一个班级中的每种菜的喜欢的人数,选取喜欢人数最多的前k种菜,对于每一个学生都只保留这k种菜,进行菜的种类数控制,如果存在学生的推荐菜数很少,就按照每种菜喜欢的人数多少来添加,直到有足够的数量进行接下来的差分进化。
2.3食物及其重量的匹配
给每一个学生推荐食物完成后就可以根据每个学生的食物进行食物种类及对应重量的匹配,从而满足各种营养的标准摄入量。每次对每一个学生进行差分进化前差分进化前要进行对学生身高,体重及性别的判断,大致确定这个学生缺少那些营养或者那种营养过多,从而实现营养标准的个性化。然后对这个学生的推荐食物进行编号,种群中的每个个体都由两种或三种食物组成,每种食物都有一个对应的重量,下图分别为一顿饭两种菜和三种菜的营养误差。每次差分进化都找出最优的五个个体,每天分配一个最优的个体,每个学生进行三次差分进化,分别对应早,中,晚三顿饭。
差分进化的每一个个体的适应度由下式计算:
其中x为种群中的一个个体,为第i种营养物质的权重,为个体的第i种营养物质的含量,为第i种营养物质的标准摄入量。每次差分进化的种群规模为25个,种群代数为80就可以找到较好的个体,而且运行时间较快。由于一个种群进化到最后种群中的个体的相似度都很大,所以在挑选其中的5个最好个体时要根据食物的种类进行去重,如果去重后的个体数少于5个就多次运行差分进化算法。
3.实验结果与分析
3.1实验结果
搜集到了大概有100人40天的食物喜好数据,本文只使用精确率(precision)作为性能度量的指标,计算公式为
因为考虑到了现实中学校不可能做很多种类的饭,所以限制了每次推荐出的食物种类数,所以推荐系统中常用的召回率以及F1值并没有太大的参考意义。经过训练后,得到了下图中所有同学的平均的精确率的增长曲线。
为了检验推荐系统的每一个部分都起到了作用,又将本文提出的推荐系统拆分开进行多次实验,下图为各种拆分方案的最终平均准确率。
推荐进行完成后,要进行食物的匹配,下图为进行一次差分进化过程中,误差的变化轨迹。
下图为差分进化出的个体的各个营养物质的平均误差。
3.2实验分析
在经过训练后,可以看出推荐系统的精确率达到了90%左右,在任意去掉此推荐系统的一部分后精确率都有不同的下降,说明几种算法的结合取得了较好的效果。在最后的不同食物的匹配过程中,可以看到误差在一次的差分进化中有着快速的下降,其中能量误差最小,在0.07%左右,而且在最后的结果中一些比较重要的营养物质的误差较小,脂肪的误差较大,在56.35%,除了脂肪和硒的误差较大以外,其他的误差都较小,而且并不都是缺少,也有营养多于标准营养,多余的部分的影响并不会很大。
4.总结
本文不仅使用了在食物推荐系统中最为常用的协同过滤算法,而且还结合了在食物推荐中少见的FTRL增量学习算法,在最后的基于营养标准的食物的匹配中,利用了差分进化算法,将每种营养标准与营养摄入量的差的绝对值以相应权值相加得到的数作为种群适应度。经过实验的测试,验证了本文提出的模型在解决儿童既要营养的均衡摄入也要符合个人喜好的难题时有着较好的效果。
参考文献
[1]方琦.个性化健康饮食推荐方法研究[D].长安大学,2018.
[2]王伟伟.基于情境感知的校园餐饮推荐方法研究及应用[D].太原理工大学,2018.
[3]刘兴姿.基于营养饮食推荐系统研究[D].西安电子科技大学,2019.
[4]梅子杰. 食材搭配推荐算法研究[D].重庆邮电大学,2018.
[5]项亮2012. 推荐系统实战. 北京市崇文区夕照寺街:人民郵电出版社. 197pp.
[6] Sarwar B M, Karypis G, Konstan J A, et al. Item-based collaborative filtering recommendation algorithms[C]. the web conference, 2001: 285-295.
[7] G. Evaluation of Item-Based Top- N Recommendation Algorithms[C]. conference on information and knowledge management, 2001: 247-254.
[8] Mcmahan H B, Holt G, Sculley D, et al. Ad click prediction: a view from the trenches[C]. knowledge discovery and data mining, 2013: 1222-1230.
[9] Storn R , Price K . Differential Evolution-A Simple and Efficient Heuristic for Global Optimization over Continuous Spaces[J]. Journal of Global Optimization, 1997, 11.
[10]丁汝金,杨慧,裴丹丹.农村留守儿童营养膳食调配分析[J].现代食品,2019(09):117-120+128.