協(xié)同過濾和粒子群算法在飲食推薦中的應(yīng)用

何金超 羅 芳 袁知才 黃慧中

(武漢理工大學(xué)計算機(jī)與科學(xué)技術(shù)學(xué)院 湖北 武漢 430061)

0 引 言

隨著人們生活水平的不斷提高，在飲食方面，人們越來越注重健康飲食。營養(yǎng)失衡容易導(dǎo)致肥胖癥、高血壓以及糖尿病等疾病的發(fā)生。健康飲食不是一味追求“高營養(yǎng)”，而是要營養(yǎng)均衡，也就是指人體每日的各種營養(yǎng)元素攝入量達(dá)到健康標(biāo)準(zhǔn)。但是，僅憑人們的生活經(jīng)驗(yàn)往往很難均衡各種營養(yǎng)元素及其含量，而且現(xiàn)如今人們早已習(xí)慣用手機(jī)解決衣食住行等各種生活問題，因此，各種飲食推薦軟件應(yīng)運(yùn)而生。

現(xiàn)有的飲食推薦軟件大多從用戶飲食偏好或營養(yǎng)均衡入手。從用戶飲食偏好方面做出推薦的算法主要有基于用戶的協(xié)同過濾算法、基于內(nèi)容的協(xié)同過濾算法[1]等。王玉山等[2]通過分析用戶的飲食記錄，利用基于用戶的協(xié)同過濾算法，選取k個近鄰對食物進(jìn)行加權(quán)推薦，并使用輪盤選賭法使推薦的食物多樣化。Cheng等[3]使用基于內(nèi)容的協(xié)同過濾算法，通過保存用戶瀏覽的食譜記錄，分析食譜間的相似性，向目標(biāo)用戶推薦其可能喜歡的食譜。韋素云等[4]提出一種基于Co-Clustering平滑的協(xié)同過濾算法解決協(xié)同過濾算法普遍存在的冷啟動和稀疏性問題。從營養(yǎng)均衡方面做出推薦的算法主要有多目標(biāo)粒子群優(yōu)化算法[5]、Apriori算法[6]等。張繼新等[7]根據(jù)用戶的年齡、性別等信息確定用戶每天所需的能量、蛋白質(zhì)和鈣等三種營養(yǎng)元素含量，利用多目標(biāo)粒子群優(yōu)化算法使得推薦的食物滿足這三種營養(yǎng)元素的需求。周萬珍等[8]采用k-means聚類算法和Apriori算法實(shí)現(xiàn)食物營養(yǎng)成分含量之間的關(guān)聯(lián)規(guī)則挖掘，讓用戶可根據(jù)自身對營養(yǎng)成分的需求選擇不同“簇”內(nèi)的某類食物。

綜上所述，現(xiàn)有的大多數(shù)飲食推薦方案難以同時滿足用戶飲食偏好和營養(yǎng)均衡的需求。從用戶飲食偏好出發(fā)的推薦方案，只給用戶推薦他喜歡的菜品，這樣往往會讓用戶養(yǎng)成偏食習(xí)慣，導(dǎo)致營養(yǎng)不良。從營養(yǎng)均衡出發(fā)的推薦方案，雖然可以給出明確的營養(yǎng)元素和食物重量，但沒有考慮用戶個性化需求。本文提出一種兩者兼顧的推薦方案，根據(jù)中國營養(yǎng)學(xué)會發(fā)布的中國居民膳食營養(yǎng)素參考攝入量(recommended nutrient intake，RNI)[9]和中國食品營養(yǎng)網(wǎng)上發(fā)布的各種食材的營養(yǎng)信息，以及用戶的飲食記錄，采用基于用戶飲食偏好的協(xié)同過濾，進(jìn)行每日的食譜推薦；在此基礎(chǔ)上，利用多目標(biāo)粒子群優(yōu)化算法，使得推薦的食物九種營養(yǎng)元素達(dá)到每日推薦攝入量(recommended dietary allowances，RDAs)標(biāo)準(zhǔn)。

1 個性化飲食推薦問題的數(shù)學(xué)模型

1.1 問題描述

在個性化飲食推薦問題中，需考慮用戶的飲食偏好和營養(yǎng)均衡兩種需求。針對飲食偏好需求，用戶經(jīng)常選擇符合自己口味的食物，但這僅僅是單一的幾種，造成了飲食的單一性，所以需向用戶推薦更多符合其口味的食物。針對營養(yǎng)均衡需求，用戶希望通過每天的飲食，使攝入的各種營養(yǎng)元素含量達(dá)到健康標(biāo)準(zhǔn)，所以需精確控制每餐食物的攝入量。鑒于此，本文研究基于用戶偏好和營養(yǎng)均衡的個性化飲食推薦，用于解決以下問題：(1) 為目標(biāo)用戶推薦符合其飲食偏好的每日食譜；(2) 為推薦食譜中的各種食物含量做多目標(biāo)優(yōu)化，使用戶各種營養(yǎng)素攝入量達(dá)到健康標(biāo)準(zhǔn)。

1.2 個性化飲食推薦模型建立

個性化飲食推薦模型主要由基于用戶偏好的協(xié)同過濾模型和多目標(biāo)粒子群優(yōu)化算法模型構(gòu)成?；谟脩羝玫膮f(xié)同過濾模型用于解決飲食偏好問題，多目標(biāo)粒子群優(yōu)化模型用于解決營養(yǎng)均衡問題。

1.2.1基于用戶偏好的協(xié)同過濾模型

1) 用戶偏好:基于用戶的協(xié)同過濾，通過分析用戶飲食-頻次矩陣，計算用戶間的相似度，找到飲食記錄相似的用戶集合，推薦目標(biāo)用戶未吃過但可能喜歡吃的食物。用戶-飲食頻次矩陣R(m,n)定義如下：

式中：Rij為用戶Ui(1≤i≤m)對第j(1≤j≤n)種食物Fj的飲食頻次。

由于有的用戶飲食記錄數(shù)據(jù)較多，有的較少，特別是新老用戶之間，飲食數(shù)據(jù)差異很大。本文引出用戶飲食偏好的概念，利用用戶-飲食偏好矩陣來計算用戶間的相似度。用戶的飲食偏好定義如下：

Lij=Fij/Ni

(1)

式中：Lij為用戶Ui對于第j種食物Fj的飲食偏好，F(xiàn)ij為用戶Ui對于食物Fj的飲食頻次，Ni為用戶Ui總的飲食頻次。

利用式(1)，將用戶-飲食頻次矩陣R(m,n)轉(zhuǎn)化為用戶-飲食偏好矩陣L(m,n)，其矩陣定義如下：

式中：用戶-飲食偏好矩陣L(m,n)同樣包含上述的m個用戶集合和n種食物集合，Lij為用戶Ui(1≤i≤m)對食物Fj(1≤j≤n)的飲食偏好。

2) 模型定義:皮爾遜相關(guān)系數(shù)用來描述兩個變量之間的線性相關(guān)程度。為獲取與目標(biāo)用戶飲食偏好相似的用戶集合，需要計算用戶間的相似度，本文采用皮爾遜相關(guān)系數(shù)計算用戶間的相似度，在計算用戶間飲食偏好的相似性時，把每個用戶作為一個變量，用戶對于n種不同食物的飲食偏好作為該變量的一組樣本值。兩個變量間的皮爾遜相似度作為兩個用戶間的相似度的值。

定義1設(shè)目標(biāo)用戶為Ua，則用戶Ua與其他用戶Ub的相似度Sim(Ua,Ub)定義如下：

(2)

式中：Sim(Ua,Ub)為用戶Ua和用戶Ub間的皮爾遜相似度，Laj為用戶Ua對第j種食物Fj的飲食偏好，Lbj為用戶Ub對食物Fj的飲食偏好。

計算出目標(biāo)與其他用戶的相似度之后，需要計算每種食物的加權(quán)推薦值，將食物推薦值高的食物推薦給目標(biāo)用戶。

定義2設(shè)目標(biāo)用戶為Ua，對于目標(biāo)用戶Ua，食物Fj的加權(quán)推薦值Raj定義如下：

式中：k為目標(biāo)用戶Ua飲食偏好的近鄰個數(shù)，Sim(Ua,Ui)為用戶Ua和Ui間的皮爾遜相似度，lij為用戶Ui對于食物Fj的飲食偏好。Raj為對于目標(biāo)用戶Ua食物Fj的推薦值。

1.2.2多目標(biāo)粒子群優(yōu)化模型

多目標(biāo)粒子群優(yōu)化算模型是基于經(jīng)典粒子群算法和多目標(biāo)優(yōu)化問題的模型。本文根據(jù)多目標(biāo)優(yōu)化問題的相關(guān)定義，在《中國居民膳食營養(yǎng)素參考攝入量》[9]標(biāo)準(zhǔn)下設(shè)置多目標(biāo)函數(shù)及約束條件。

1) 粒子群算法:粒子群優(yōu)化算法是由Kennedy和Eberhart[10]于1995年提出的基于鳥群覓食模型的優(yōu)化算法。粒子的位置更新由粒子的當(dāng)前速度和上一周期位置確定，粒子的速度更新由粒子個體歷史最優(yōu)位置和群體最優(yōu)位置加權(quán)確定?；谏鲜鲈恚Ｗ游恢煤退俣雀碌臄?shù)學(xué)模型定義如下：

2)多目標(biāo)優(yōu)化:多目標(biāo)優(yōu)化問題通常也被稱為多標(biāo)準(zhǔn)優(yōu)化問題，一個具有n維決策變量，m維子目標(biāo)的多目標(biāo)優(yōu)化問題可以表述如下：

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

(6)

式中：y為m維的目標(biāo)空間；F(x)為m個由決策空間向目標(biāo)空間的映射函數(shù)；fm(x)為第m個子目標(biāo)的目標(biāo)函數(shù)；gi(x)≤0(i=1,2,…,q)和hj(x)=0(j=1,2,…,p)分別為q個不等式約束條件和p個等式約束條件；Ω為n維的決策空間。

3) 設(shè)置目標(biāo)函數(shù):根據(jù)推薦食譜中的八道菜，本文分別以其所含熱量、蛋白質(zhì)、脂肪、碳水化合物、維生素A、維生素B、鈣、鐵、維生素C九種營養(yǎng)素含量與標(biāo)準(zhǔn)值差值的絕對值作為目標(biāo)函數(shù)。

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

(7)

式中：y=(y1,y2,…,y9)為目標(biāo)函數(shù)矩陣；A8×9為單位重量的食物含營養(yǎng)素量的約束關(guān)系矩陣，其中aij(i=1,2,…,8;j=1,2,…,9)表示單位重量的食物i含營養(yǎng)素j的量；X1×8=(x1,x2,…,x8)為求解8種食物含量的未知變量矩陣；S1×9=(s1,s2,…,s9) 為根據(jù)《中國居民膳食營養(yǎng)素參考攝入量》標(biāo)準(zhǔn)得到的成年人每天應(yīng)攝入九種營養(yǎng)素含量矩陣。

4) 約束條件:根據(jù)早中晚三餐的熱量攝入比例應(yīng)為3 ∶4 ∶3，設(shè)置等式約束條件如下：

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

2 求解算法描述

基于用戶的協(xié)同過濾算法用于輸出推薦食譜，多目標(biāo)粒子群優(yōu)化算法用于輸出推薦食譜中各種食物的具體含量。

2.1 基于用戶的協(xié)同過濾算法

根據(jù)基于用戶偏好的協(xié)同過濾模型，設(shè)計基于用戶偏好的協(xié)同過濾算法偽代碼如下：

輸入：用戶-飲食頻次矩陣，閾值p，近鄰個數(shù)k

輸出：推薦的食物集foodRecmd[m]

Begin

Fori=0 tomdo

//讀取飲食總頻次N>p的用戶飲食頻次矩陣

If foodSumFreq(i)>pThen

init(foodFreq[i])

end if

cvtMatrix(foodFreq,foodLike)

//將用戶飲食頻次矩陣轉(zhuǎn)換為用戶飲食偏好矩陣

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數(shù)組中

foodRecmd[i]←scoreMap.getKey(i)

End for

End

2.2 多目標(biāo)粒子群優(yōu)化算法

針對營養(yǎng)均衡問題，本文采用由Coello等[11]于2004年提出的基于自適應(yīng)柵格的多目標(biāo)粒子群優(yōu)化算法。該算法在基本多目標(biāo)優(yōu)化算法基礎(chǔ)上，提出了新的群體最優(yōu)選擇策略、存儲器管理策略和自適應(yīng)柵格調(diào)整策略。

1) 群體最優(yōu)gbest選擇策略:根據(jù)目標(biāo)函數(shù)的維度建立超立方體空間，并將該空間劃分為若干個柵格。為每個柵格設(shè)計一個密度值，計算方式如下所示：

式中：ni是第i個柵格中解的個數(shù)，N是常數(shù)?；诿芏戎荡蟮臇鸥袢菀走x中的思想，從密度值最大的柵格中隨機(jī)選擇一個解，作為群體最優(yōu)，使粒子群向搜索不足的方向搜索。

2) 存儲器管理策略:當(dāng)存儲器沒有滿時，存儲所有搜索到的非支配解。當(dāng)存儲器滿后，根據(jù)各個柵格的密度值大小，選擇在密度值高的柵格中隨機(jī)剔除一個解。

3) 自適應(yīng)柵格調(diào)整策略:由于每次迭代后，單一目標(biāo)函數(shù)的最大值都會改變，若將超立方體空間每個維度橫坐標(biāo)的上限設(shè)為定值，則會出現(xiàn)目標(biāo)函數(shù)最大值超出坐標(biāo)范圍。因此需動態(tài)擴(kuò)展橫坐標(biāo)，使其上限為單一目標(biāo)函數(shù)最大值，并重新調(diào)整單位刻度，使劃分后的柵格總數(shù)不變。

4) 多目標(biāo)粒子群優(yōu)化算法流程：設(shè)計多目標(biāo)粒子群優(yōu)化算法偽代碼如下：

輸入：慣性因子w，學(xué)習(xí)因子c1、c2，迭代次數(shù)k，粒子數(shù)量m，外部存檔size,柵格數(shù)N

輸出：外部檔案集

Begin

Init(m);

//對種群進(jìn)行初始化

Fori=1 tok

CalTarget();

//計算粒子的各目標(biāo)函數(shù)值

GetNonInfSet();

//獲得非劣解集

UpdateArchive(archive);

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

CalDensity(N,archive);

//計算柵格密度

DelSolution(size,archive);

//限制外部檔案規(guī)模

Update(m);

//更新粒子速度，位置，個體最優(yōu)位置，群體最優(yōu)位置

End for

Print(archive);

//輸出外部檔案集

End

3 實(shí)驗(yàn)驗(yàn)證

3.1 實(shí)驗(yàn)過程

首先將本班40位同學(xué)作為用戶對象，統(tǒng)計近一個月的飲食情況。將用戶一天的飲食情況記為一條飲食記錄并存入數(shù)據(jù)庫中，共有1 200條飲食記錄。依據(jù)飲食記錄做菜譜推薦，然后通過多目標(biāo)粒子群算法優(yōu)化推薦食譜中各種食物的重量，將推薦結(jié)果呈現(xiàn)給用戶。其中多目標(biāo)粒子群優(yōu)化算法的參數(shù)設(shè)置如下：慣性因子w=0.5，學(xué)習(xí)因子c1=c2=2，迭代次數(shù)k=40，粒子數(shù)量m=30，外部存檔size=500,柵格數(shù)N=10。

3.2 實(shí)驗(yàn)結(jié)果與分析

3.2.1推薦結(jié)果與分析

(1) 推薦結(jié)果：對每個同學(xué)，每天推薦8種食物，記錄他們對于中國食品營養(yǎng)網(wǎng)上列出的80種食物的飲食數(shù)據(jù)。從這上千條數(shù)據(jù)中，隨機(jī)選擇A同學(xué)連續(xù)十天的飲食數(shù)據(jù)，包括這十天對于A同學(xué)的推薦數(shù)據(jù)和實(shí)際飲食記錄，如表1所示。統(tǒng)計每天成功推薦的食物數(shù)量，計算推薦的成功率。

表1 A同學(xué)十天的飲食數(shù)據(jù)

根據(jù)這40位同學(xué)一個月的飲食記錄，按照基于用戶偏好的協(xié)同過濾模型，對A同學(xué)進(jìn)行一天的食譜推薦，推薦結(jié)果為：大米、豬肉、生菜、梨、茄子、豆腐、基圍蝦、黃瓜。

(2) 實(shí)驗(yàn)分析：本文用推薦的準(zhǔn)確率指標(biāo)來衡量推薦系統(tǒng)的好壞，推薦食物與用戶實(shí)際食用的食物重合率越高，說明推薦準(zhǔn)確性越高，推薦效果越好。準(zhǔn)確率定義如下：

(9)

式中：counti(Rf)為第i天推薦的食物數(shù)量，counti(Rf∩Af)為第i天推薦的食物與實(shí)際食物的交集的食物個數(shù)，也就是第i天成功推薦的食物數(shù)量，precision為這十天食物推薦的準(zhǔn)確率。

計算得precision=0.82。重復(fù)實(shí)驗(yàn)獲得班上七名同學(xué)一個月的飲食推薦數(shù)據(jù)與實(shí)際飲食記錄，計算其推薦的準(zhǔn)確率，結(jié)果如圖1所示。

圖1 準(zhǔn)確率

由圖1可以看出，推薦的準(zhǔn)確率幾乎都在0.80以上，平均準(zhǔn)確率達(dá)到0.85，說明本文基于用戶偏好的協(xié)同過濾算法穩(wěn)定，推薦效果好。

3.2.2優(yōu)化結(jié)果與分析

(1) 優(yōu)化結(jié)果：由推薦模型得出目標(biāo)用戶的推薦食譜為：大米、豬肉、生菜、梨、茄子、豆腐、基圍蝦、黃瓜，依據(jù)本文優(yōu)化模型得出優(yōu)化結(jié)果為：大米223 g、豬肉130 g、生菜262 g、梨357 g、茄子100 g、豆腐100 g、基圍蝦246 g、黃瓜297 g。與標(biāo)準(zhǔn)攝入的比較結(jié)果見表2。

表2 營養(yǎng)調(diào)配與標(biāo)準(zhǔn)攝入的差值結(jié)果比較

為避免實(shí)驗(yàn)的偶然性，對本次推薦結(jié)果做30次重復(fù)獨(dú)立實(shí)驗(yàn)，統(tǒng)計各營養(yǎng)素平均誤差如表3所示。

表3 30次重復(fù)獨(dú)立實(shí)驗(yàn)后各營養(yǎng)素平均誤差

(2) 實(shí)驗(yàn)分析：從單次實(shí)驗(yàn)結(jié)果來看，9種營養(yǎng)素中有6種營養(yǎng)素誤差在百分之十以內(nèi)，最低誤差為1.2%，最高誤差為33.2%。其中蛋白質(zhì)誤差達(dá)到最大33.2%的原因在于推薦食譜中同時包含了基圍蝦和豬肉兩類食物，這兩種食物單位重量含蛋白質(zhì)異常高，所以在調(diào)優(yōu)時造成蛋白質(zhì)含量較高。除去蛋白質(zhì)，最高誤差為22.8%，平均誤差為9.425%。

從多次實(shí)驗(yàn)結(jié)果來看，9種營養(yǎng)素中有6種營養(yǎng)素誤差在百分之十以內(nèi)。除去蛋白質(zhì)外，平均最低誤差為0.9%，平均最高誤差為20.2%，平均誤差為9.4%。通常而言，各營養(yǎng)素攝入量與標(biāo)準(zhǔn)值誤差在±10%以內(nèi)屬于營養(yǎng)攝入正常[12]。所以本文所用多目標(biāo)粒子群優(yōu)化算法在營養(yǎng)均衡問題上效果顯著。

4 結(jié) 語

針對個性化飲食推薦問題，本文綜合考慮飲食偏好和營養(yǎng)均衡需求，建立個性化飲食推薦模型，先通過基于用戶偏好的協(xié)同過濾算法做飲食推薦，然后以人體攝入營養(yǎng)素含量與標(biāo)準(zhǔn)含量差值的絕對值作為目標(biāo)函數(shù)，運(yùn)用多目標(biāo)粒子群優(yōu)化算法對推薦食譜中的各食物含量進(jìn)行調(diào)優(yōu)。算法中基于自適應(yīng)柵格篩選非劣解和全局最優(yōu)解，控制Pareto分布的均勻性和多樣性。經(jīng)過實(shí)驗(yàn)測試，驗(yàn)證了本文構(gòu)建的個性化飲食推薦模型在解決飲食偏好和營養(yǎng)均衡需求問題上的有效性。