协同过滤和粒子群算法在饮食推荐中的应用

何金超 罗 芳 袁知才 黄慧中

(武汉理工大学计算机与科学技术学院 湖北 武汉 430061)

0 引 言

随着人们生活水平的不断提高，在饮食方面，人们越来越注重健康饮食。营养失衡容易导致肥胖症、高血压以及糖尿病等疾病的发生。健康饮食不是一味追求“高营养”，而是要营养均衡，也就是指人体每日的各种营养元素摄入量达到健康标准。但是，仅凭人们的生活经验往往很难均衡各种营养元素及其含量，而且现如今人们早已习惯用手机解决衣食住行等各种生活问题，因此，各种饮食推荐软件应运而生。

现有的饮食推荐软件大多从用户饮食偏好或营养均衡入手。从用户饮食偏好方面做出推荐的算法主要有基于用户的协同过滤算法、基于内容的协同过滤算法[1]等。王玉山等[2]通过分析用户的饮食记录，利用基于用户的协同过滤算法，选取k个近邻对食物进行加权推荐，并使用轮盘选赌法使推荐的食物多样化。Cheng等[3]使用基于内容的协同过滤算法，通过保存用户浏览的食谱记录，分析食谱间的相似性，向目标用户推荐其可能喜欢的食谱。韦素云等[4]提出一种基于Co-Clustering平滑的协同过滤算法解决协同过滤算法普遍存在的冷启动和稀疏性问题。从营养均衡方面做出推荐的算法主要有多目标粒子群优化算法[5]、Apriori算法[6]等。张继新等[7]根据用户的年龄、性别等信息确定用户每天所需的能量、蛋白质和钙等三种营养元素含量，利用多目标粒子群优化算法使得推荐的食物满足这三种营养元素的需求。周万珍等[8]采用k-means聚类算法和Apriori算法实现食物营养成分含量之间的关联规则挖掘，让用户可根据自身对营养成分的需求选择不同“簇”内的某类食物。

综上所述，现有的大多数饮食推荐方案难以同时满足用户饮食偏好和营养均衡的需求。从用户饮食偏好出发的推荐方案，只给用户推荐他喜欢的菜品，这样往往会让用户养成偏食习惯，导致营养不良。从营养均衡出发的推荐方案，虽然可以给出明确的营养元素和食物重量，但没有考虑用户个性化需求。本文提出一种两者兼顾的推荐方案，根据中国营养学会发布的中国居民膳食营养素参考摄入量(recommended nutrient intake，RNI)[9]和中国食品营养网上发布的各种食材的营养信息，以及用户的饮食记录，采用基于用户饮食偏好的协同过滤，进行每日的食谱推荐；在此基础上，利用多目标粒子群优化算法，使得推荐的食物九种营养元素达到每日推荐摄入量(recommended dietary allowances，RDAs)标准。

1 个性化饮食推荐问题的数学模型

1.1 问题描述

在个性化饮食推荐问题中，需考虑用户的饮食偏好和营养均衡两种需求。针对饮食偏好需求，用户经常选择符合自己口味的食物，但这仅仅是单一的几种，造成了饮食的单一性，所以需向用户推荐更多符合其口味的食物。针对营养均衡需求，用户希望通过每天的饮食，使摄入的各种营养元素含量达到健康标准，所以需精确控制每餐食物的摄入量。鉴于此，本文研究基于用户偏好和营养均衡的个性化饮食推荐，用于解决以下问题：(1) 为目标用户推荐符合其饮食偏好的每日食谱；(2) 为推荐食谱中的各种食物含量做多目标优化，使用户各种营养素摄入量达到健康标准。

1.2 个性化饮食推荐模型建立

个性化饮食推荐模型主要由基于用户偏好的协同过滤模型和多目标粒子群优化算法模型构成。基于用户偏好的协同过滤模型用于解决饮食偏好问题，多目标粒子群优化模型用于解决营养均衡问题。

1.2.1基于用户偏好的协同过滤模型

1) 用户偏好:基于用户的协同过滤，通过分析用户饮食-频次矩阵，计算用户间的相似度，找到饮食记录相似的用户集合，推荐目标用户未吃过但可能喜欢吃的食物。用户-饮食频次矩阵R(m,n)定义如下：

式中：Rij为用户Ui(1≤i≤m)对第j(1≤j≤n)种食物Fj的饮食频次。

由于有的用户饮食记录数据较多，有的较少，特别是新老用户之间，饮食数据差异很大。本文引出用户饮食偏好的概念，利用用户-饮食偏好矩阵来计算用户间的相似度。用户的饮食偏好定义如下：

Lij=Fij/Ni

(1)

式中：Lij为用户Ui对于第j种食物Fj的饮食偏好，Fij为用户Ui对于食物Fj的饮食频次，Ni为用户Ui总的饮食频次。

利用式(1)，将用户-饮食频次矩阵R(m,n)转化为用户-饮食偏好矩阵L(m,n)，其矩阵定义如下：

式中：用户-饮食偏好矩阵L(m,n)同样包含上述的m个用户集合和n种食物集合，Lij为用户Ui(1≤i≤m)对食物Fj(1≤j≤n)的饮食偏好。

2) 模型定义:皮尔逊相关系数用来描述两个变量之间的线性相关程度。为获取与目标用户饮食偏好相似的用户集合，需要计算用户间的相似度，本文采用皮尔逊相关系数计算用户间的相似度，在计算用户间饮食偏好的相似性时，把每个用户作为一个变量，用户对于n种不同食物的饮食偏好作为该变量的一组样本值。两个变量间的皮尔逊相似度作为两个用户间的相似度的值。

定义1设目标用户为Ua，则用户Ua与其他用户Ub的相似度Sim(Ua,Ub)定义如下：

(2)

式中：Sim(Ua,Ub)为用户Ua和用户Ub间的皮尔逊相似度，Laj为用户Ua对第j种食物Fj的饮食偏好，Lbj为用户Ub对食物Fj的饮食偏好。

计算出目标与其他用户的相似度之后，需要计算每种食物的加权推荐值，将食物推荐值高的食物推荐给目标用户。

定义2设目标用户为Ua，对于目标用户Ua，食物Fj的加权推荐值Raj定义如下：

式中：k为目标用户Ua饮食偏好的近邻个数，Sim(Ua,Ui)为用户Ua和Ui间的皮尔逊相似度，lij为用户Ui对于食物Fj的饮食偏好。Raj为对于目标用户Ua食物Fj的推荐值。

1.2.2多目标粒子群优化模型

多目标粒子群优化算模型是基于经典粒子群算法和多目标优化问题的模型。本文根据多目标优化问题的相关定义，在《中国居民膳食营养素参考摄入量》[9]标准下设置多目标函数及约束条件。

1) 粒子群算法:粒子群优化算法是由Kennedy和Eberhart[10]于1995年提出的基于鸟群觅食模型的优化算法。粒子的位置更新由粒子的当前速度和上一周期位置确定，粒子的速度更新由粒子个体历史最优位置和群体最优位置加权确定。基于上述原理，粒子位置和速度更新的数学模型定义如下：

2)多目标优化:多目标优化问题通常也被称为多标准优化问题，一个具有n维决策变量，m维子目标的多目标优化问题可以表述如下：

miny=F(x)=(f1(x),f2(x),…,fm(x))

(6)

式中：y为m维的目标空间；F(x)为m个由决策空间向目标空间的映射函数；fm(x)为第m个子目标的目标函数；gi(x)≤0(i=1,2,…,q)和hj(x)=0(j=1,2,…,p)分别为q个不等式约束条件和p个等式约束条件；Ω为n维的决策空间。

3) 设置目标函数:根据推荐食谱中的八道菜，本文分别以其所含热量、蛋白质、脂肪、碳水化合物、维生素A、维生素B、钙、铁、维生素C九种营养素含量与标准值差值的绝对值作为目标函数。

miny=|X1×8×A8×9-S1×9|

(7)

式中：y=(y1,y2,…,y9)为目标函数矩阵；A8×9为单位重量的食物含营养素量的约束关系矩阵，其中aij(i=1,2,…,8;j=1,2,…,9)表示单位重量的食物i含营养素j的量；X1×8=(x1,x2,…,x8)为求解8种食物含量的未知变量矩阵；S1×9=(s1,s2,…,s9) 为根据《中国居民膳食营养素参考摄入量》标准得到的成年人每天应摄入九种营养素含量矩阵。

4) 约束条件:根据早中晚三餐的热量摄入比例应为3 ∶4 ∶3，设置等式约束条件如下：

式中：xi(i=1,2),xj(j=3,4,5),xk(k=6,7,8)分别为早中晚三餐的食物重量，am1(m=1,2,…,8)为单位重量的食物m所含热量值。

2 求解算法描述

基于用户的协同过滤算法用于输出推荐食谱，多目标粒子群优化算法用于输出推荐食谱中各种食物的具体含量。

2.1 基于用户的协同过滤算法

根据基于用户偏好的协同过滤模型，设计基于用户偏好的协同过滤算法伪代码如下：

输入：用户-饮食频次矩阵，阈值p，近邻个数k

输出：推荐的食物集foodRecmd[m]

Begin

Fori=0 tomdo

//读取饮食总频次N>p的用户饮食频次矩阵

If foodSumFreq(i)>pThen

init(foodFreq[i])

end if

cvtMatrix(foodFreq,foodLike)

//将用户饮食频次矩阵转换为用户饮食偏好矩阵

getUserMap(foodLike,userMap)

//建立userMap

getUserSim(userMap, psMap)

//计算皮尔逊相似度

Collections.sort(psMap,k)

//取相似度高的k个近邻

getFoodSco(psMap,scoMap)

//计算食物推荐值

getLsFood(scoMap,foodFreq,x)

//获得用户没有吃过但推荐值较高的的x种食物

Collections.sort(scoMap,y)

//获得推荐值较高的y种食物(不包含之前的x种食物)

m←x+y

Fori=0 tomdo

//将推荐的m种食物保存在foodRecmd数组中

foodRecmd[i]←scoreMap.getKey(i)

End for

End

2.2 多目标粒子群优化算法

针对营养均衡问题，本文采用由Coello等[11]于2004年提出的基于自适应栅格的多目标粒子群优化算法。该算法在基本多目标优化算法基础上，提出了新的群体最优选择策略、存储器管理策略和自适应栅格调整策略。

1) 群体最优gbest选择策略:根据目标函数的维度建立超立方体空间，并将该空间划分为若干个栅格。为每个栅格设计一个密度值，计算方式如下所示：

式中：ni是第i个栅格中解的个数，N是常数。基于密度值大的栅格容易选中的思想，从密度值最大的栅格中随机选择一个解，作为群体最优，使粒子群向搜索不足的方向搜索。

2) 存储器管理策略:当存储器没有满时，存储所有搜索到的非支配解。当存储器满后，根据各个栅格的密度值大小，选择在密度值高的栅格中随机剔除一个解。

3) 自适应栅格调整策略:由于每次迭代后，单一目标函数的最大值都会改变，若将超立方体空间每个维度横坐标的上限设为定值，则会出现目标函数最大值超出坐标范围。因此需动态扩展横坐标，使其上限为单一目标函数最大值，并重新调整单位刻度，使划分后的栅格总数不变。

4) 多目标粒子群优化算法流程：设计多目标粒子群优化算法伪代码如下：

输入：惯性因子w，学习因子c1、c2，迭代次数k，粒子数量m，外部存档size,栅格数N

输出：外部档案集

Begin

Init(m);

//对种群进行初始化

Fori=1 tok

CalTarget();

//计算粒子的各目标函数值

GetNonInfSet();

//获得非劣解集

UpdateArchive(archive);

//将非劣解集加入外部档案，并剔除劣解，即更新外部档案

CalDensity(N,archive);

//计算栅格密度

DelSolution(size,archive);

//限制外部档案规模

Update(m);

//更新粒子速度，位置，个体最优位置，群体最优位置

End for

Print(archive);

//输出外部档案集

End

3 实验验证

3.1 实验过程

首先将本班40位同学作为用户对象，统计近一个月的饮食情况。将用户一天的饮食情况记为一条饮食记录并存入数据库中，共有1 200条饮食记录。依据饮食记录做菜谱推荐，然后通过多目标粒子群算法优化推荐食谱中各种食物的重量，将推荐结果呈现给用户。其中多目标粒子群优化算法的参数设置如下：惯性因子w=0.5，学习因子c1=c2=2，迭代次数k=40，粒子数量m=30，外部存档size=500,栅格数N=10。

3.2 实验结果与分析

3.2.1推荐结果与分析

(1) 推荐结果：对每个同学，每天推荐8种食物，记录他们对于中国食品营养网上列出的80种食物的饮食数据。从这上千条数据中，随机选择A同学连续十天的饮食数据，包括这十天对于A同学的推荐数据和实际饮食记录，如表1所示。统计每天成功推荐的食物数量，计算推荐的成功率。

表1 A同学十天的饮食数据

根据这40位同学一个月的饮食记录，按照基于用户偏好的协同过滤模型，对A同学进行一天的食谱推荐，推荐结果为：大米、猪肉、生菜、梨、茄子、豆腐、基围虾、黄瓜。

(2) 实验分析：本文用推荐的准确率指标来衡量推荐系统的好坏，推荐食物与用户实际食用的食物重合率越高，说明推荐准确性越高，推荐效果越好。准确率定义如下：

(9)

式中：counti(Rf)为第i天推荐的食物数量，counti(Rf∩Af)为第i天推荐的食物与实际食物的交集的食物个数，也就是第i天成功推荐的食物数量，precision为这十天食物推荐的准确率。

计算得precision=0.82。重复实验获得班上七名同学一个月的饮食推荐数据与实际饮食记录，计算其推荐的准确率，结果如图1所示。

图1 准确率

由图1可以看出，推荐的准确率几乎都在0.80以上，平均准确率达到0.85，说明本文基于用户偏好的协同过滤算法稳定，推荐效果好。

3.2.2优化结果与分析

(1) 优化结果：由推荐模型得出目标用户的推荐食谱为：大米、猪肉、生菜、梨、茄子、豆腐、基围虾、黄瓜，依据本文优化模型得出优化结果为：大米223 g、猪肉130 g、生菜262 g、梨357 g、茄子100 g、豆腐100 g、基围虾246 g、黄瓜297 g。与标准摄入的比较结果见表2。

表2 营养调配与标准摄入的差值结果比较

为避免实验的偶然性，对本次推荐结果做30次重复独立实验，统计各营养素平均误差如表3所示。

表3 30次重复独立实验后各营养素平均误差

(2) 实验分析：从单次实验结果来看，9种营养素中有6种营养素误差在百分之十以内，最低误差为1.2%，最高误差为33.2%。其中蛋白质误差达到最大33.2%的原因在于推荐食谱中同时包含了基围虾和猪肉两类食物，这两种食物单位重量含蛋白质异常高，所以在调优时造成蛋白质含量较高。除去蛋白质，最高误差为22.8%，平均误差为9.425%。

从多次实验结果来看，9种营养素中有6种营养素误差在百分之十以内。除去蛋白质外，平均最低误差为0.9%，平均最高误差为20.2%，平均误差为9.4%。通常而言，各营养素摄入量与标准值误差在±10%以内属于营养摄入正常[12]。所以本文所用多目标粒子群优化算法在营养均衡问题上效果显著。

4 结 语

针对个性化饮食推荐问题，本文综合考虑饮食偏好和营养均衡需求，建立个性化饮食推荐模型，先通过基于用户偏好的协同过滤算法做饮食推荐，然后以人体摄入营养素含量与标准含量差值的绝对值作为目标函数，运用多目标粒子群优化算法对推荐食谱中的各食物含量进行调优。算法中基于自适应栅格筛选非劣解和全局最优解，控制Pareto分布的均匀性和多样性。经过实验测试，验证了本文构建的个性化饮食推荐模型在解决饮食偏好和营养均衡需求问题上的有效性。