基于交替最小二乘法和規(guī)則匹配的菜品推薦

金琪文，王先傳，彭 亮，王順杰，陳秀明

（阜陽(yáng)師范大學(xué) 計(jì)算機(jī)與信息工程學(xué)院，安徽 阜陽(yáng) 236037）

隨著社會(huì)節(jié)奏的加快，人們?cè)谝蝗杖徒】店P(guān)注度上呈現(xiàn)漸低的情況，不合理的飲食結(jié)構(gòu),導(dǎo)致了一系列的健康問(wèn)題。目前，推薦算法一般是針對(duì)網(wǎng)上購(gòu)物領(lǐng)域的比較多，熟知的企業(yè)有淘寶和亞馬遜，但在菜品推薦方面研究較少。

受限于健康科學(xué)知識(shí)的了解，人們希望通過(guò)互聯(lián)網(wǎng)幫助自己規(guī)劃一日三餐的飲食。隨著大數(shù)據(jù)和互聯(lián)網(wǎng)時(shí)代的到來(lái)，網(wǎng)絡(luò)信息爆炸式增長(zhǎng)，逐漸超越了個(gè)人接受、處理和有效利用的范圍，并且人們開(kāi)始逐漸在海量的食品信息中迷失自我。所以，如何從海量的膳食數(shù)據(jù)中找到符合自身的食譜信息，已經(jīng)成為越來(lái)越多的用戶面臨的重大問(wèn)題。目前市場(chǎng)上的飲食推薦系統(tǒng)的推薦結(jié)果比較單一化，多是注重用戶喜好[1-4]，忽視了一日三餐的飲食搭配對(duì)身體的長(zhǎng)期影響。

1 相關(guān)研究

在信息時(shí)代，個(gè)性化推薦類算法成為了一個(gè)重要研究方向，延伸出了包括基于用戶、項(xiàng)目分類、內(nèi)容、社會(huì)網(wǎng)絡(luò)等推薦算法[5-10]。其中：基于用戶的協(xié)同過(guò)濾推薦算法存在矩陣稀疏問(wèn)題，而且不能對(duì)用戶的興趣進(jìn)行動(dòng)態(tài)衡量[11-12]；基于項(xiàng)目分類的協(xié)同過(guò)濾算法雖然一定程度上解決數(shù)據(jù)稀疏性問(wèn)題，但計(jì)算相似度穩(wěn)定性不佳[13-14]；基于內(nèi)容的推薦算法的基本思想是計(jì)算用戶未購(gòu)買(mǎi)的項(xiàng)目和當(dāng)前用戶過(guò)去選擇的項(xiàng)目的相似度[15]，其特點(diǎn)是不需要用戶評(píng)分?jǐn)?shù)據(jù)，沒(méi)有數(shù)據(jù)稀疏性問(wèn)題影響，但無(wú)法構(gòu)建用戶偏好模型。伴隨著多種社交軟件的興起，社會(huì)網(wǎng)絡(luò)數(shù)據(jù)的推薦算法大多從用戶間的社會(huì)關(guān)系角度出發(fā)，僅認(rèn)為相互信任的朋友間具有相似的興趣愛(ài)好，而忽視了推薦對(duì)象之間的關(guān)系對(duì)推薦結(jié)果的影響[16]。對(duì)于基于語(yǔ)境感知數(shù)據(jù)的推薦算法是區(qū)別于基于用戶和項(xiàng)目分類的推薦算法，通過(guò)上下文信息和場(chǎng)景信息進(jìn)行預(yù)測(cè)推薦，但由于飲食菜譜的多維復(fù)雜性，該算法的推薦質(zhì)量表現(xiàn)較普遍化。基于深度學(xué)習(xí)的推薦算法通過(guò)感知特殊數(shù)據(jù)格式，但由于其大規(guī)模、數(shù)據(jù)異構(gòu)復(fù)雜度較高、分布不均勻等問(wèn)題，目前還有諸多應(yīng)用于推薦引擎上的挑戰(zhàn)[17-18]。

本文首先采用基于矩陣分解的ALS算法得到推薦列表，然后根據(jù)膳食搭配以及用戶特殊需求，采用規(guī)則匹配方法優(yōu)化推薦列表，給出基于多維度規(guī)則匹配的推薦列表的輔助優(yōu)化算法。

2 菜品推薦算法

2.1 菜品推薦流程

首先，收集用戶行為日志作為初始數(shù)據(jù)，然后對(duì)初始數(shù)據(jù)進(jìn)行預(yù)處理得到用戶偏好數(shù)據(jù)，再將用戶偏好數(shù)據(jù)和ALS推薦算法模型結(jié)合得到推薦列表，再基于用戶身體狀況和特殊需求，利用規(guī)則匹配算法優(yōu)化推薦列表，推薦列表獲取的流程如圖1所示。

2.2 交替最小二乘法

交替最小二乘法(alternating least square，ALS)，屬于機(jī)器學(xué)習(xí)中的協(xié)同過(guò)濾推薦算法[19]，同時(shí)它也屬于混合推薦（collaborative filtering，CF）算法?？紤]用戶和菜品兩個(gè)方面，于是可以使用一個(gè)三元組:＜User，Item，Rate＞來(lái)表示用戶、菜品和評(píng)分之間的關(guān)系。表1是用戶對(duì)菜品的評(píng)分結(jié)構(gòu)，其中u1～u3，v1～v4分別表示用戶和菜品，這里通過(guò)加入一定的規(guī)則評(píng)分設(shè)計(jì)輔助收集評(píng)分?jǐn)?shù)據(jù)，如點(diǎn)擊(1 分)，搜索(2 分)，收藏(3 分)，購(gòu)買(mǎi)(4 分)，未評(píng)分的為0分等。

圖1 菜品推薦流程圖

表1 用戶對(duì)菜品的評(píng)分結(jié)構(gòu)

將用戶對(duì)菜品的評(píng)分矩陣分解為用戶對(duì)菜品隱含特征的偏好矩陣和菜品所包含的隱含特征矩陣，利用ALS算法將分解出的矩陣進(jìn)行多次迭代，使得評(píng)分矩陣缺失項(xiàng)得到補(bǔ)充[20]。ALS算法可以使用公式（1）描述。

其中：U表示用戶對(duì)菜品的隱含的特征偏好矩陣；D表示菜品自身隱含的特征偏好矩陣；rij表示用戶ui對(duì)菜品vj的評(píng)分；函數(shù)f的目標(biāo)是使特征矩陣U和D盡可能的逼近rij組成的評(píng)分矩陣R；I表示評(píng)分矩陣中的評(píng)分集合；Ui表示用戶ui隱含的偏好特征向量；Dj表示菜品vj包含的隱含特征向量；表示用戶ui的評(píng)分次數(shù)；λ是正則項(xiàng)系數(shù)；表示用戶ui對(duì)菜品vj的偏好的預(yù)測(cè)值。作用是預(yù)防出現(xiàn)過(guò)度擬合問(wèn)題[20]。

ALS的求解思路：首先將U當(dāng)做常量，求解出D；然后把D當(dāng)做常量求解出U。反復(fù)上述過(guò)程，使U和D在滿足一定條件下逼近原始的評(píng)分矩陣R。

2.3 基于規(guī)則匹配的算法

雖然ALS解決了個(gè)性化飲食推薦的問(wèn)題，但對(duì)于膳食搭配和用戶特殊需求的滿足能力不足，這里使用基于規(guī)則匹配算法優(yōu)化ALS算法得到的推薦列表。

基于規(guī)則匹配算法如算法1。

images/BZ_55_288_1112_1171_1171.pngInput:ALS的推薦列表Top20 Output：優(yōu)化后的推薦列表Top10 Step 1:構(gòu)建用戶身體狀況表、菜品營(yíng)養(yǎng)表、食補(bǔ)知識(shí)表和食材禁忌表Step 2:依據(jù)Setp 1中的4種表構(gòu)建優(yōu)化規(guī)則Step 3:使用優(yōu)化規(guī)則對(duì)TOP20推薦列表進(jìn)行優(yōu)化Step 4:選擇優(yōu)化后的TOP10推薦給用戶

在Step 1中，用戶身體情況一般包括基本身體情況和特殊身體情況，基本身體情況（體重、出生年月、身高、最近目的、口味偏好）和特殊身體狀況(最低眼視力、沙眼、最高耳聽(tīng)力、眼疾、耳疾、鼻疾病、口腔、血壓、皮膚、肺活量、肝、脾、四肢、關(guān)節(jié)、平跖足、既往病史、血糖、脈搏)。

收集常見(jiàn)的24種營(yíng)養(yǎng)素：熱量、脂肪、纖維素、維生素C、胡蘿卜素、核黃素、膽固醇、鈣、鋅、錳、磷、硒、碳水化合物、蛋白質(zhì)、維生素A、維生素E、硫胺素、煙酸、鎂、鐵、銅、鉀、鈉、維生素 B。每100 g原食材的營(yíng)養(yǎng)素含量表（部分），如表2。

根據(jù)菜品各種主料和配料的食材使用含量，再結(jié)合表2，計(jì)算出每100 g菜品的營(yíng)養(yǎng)素含量表，如表3所示（部分）。例如，西紅柿炒蛋的主料是雞蛋150 g、番茄300 g，調(diào)料是大蒜5 g、大蔥5 g、食鹽 3 g、白砂糖 5 g、味精 2 g[21]，則西紅柿炒蛋的鈉含量計(jì)算如下：

表2 每100 g原食材的營(yíng)養(yǎng)素含量表（部分）

表3 每100g菜品的營(yíng)養(yǎng)素含量表（部分）

食補(bǔ)知識(shí)表由功能名稱、推薦原材料、推薦食譜構(gòu)成，如表4。食材搭配禁忌表由食材、相克食材、相克關(guān)系描述構(gòu)成，如表5。在Step 2中，基于身體異常狀況，當(dāng)菜品的營(yíng)養(yǎng)素含量有益于身體異常狀況的改善時(shí)，將相應(yīng)菜品的權(quán)重增加i個(gè)，當(dāng)菜品的營(yíng)養(yǎng)素含量會(huì)不利于身體異常狀況的改善時(shí)，將相應(yīng)菜品的權(quán)重減少j個(gè)，得到部分優(yōu)化規(guī)則如規(guī)則1和規(guī)則2。

規(guī)則1：有益身體狀況→增加i個(gè)權(quán)重；

規(guī)則2：不利身體狀況→減少j個(gè)權(quán)重。

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

下面以具體實(shí)例描述Step 3和4的過(guò)程。以高血壓的菜品優(yōu)化推薦列表流程為例，如圖2。

首先檢索用戶身體狀況庫(kù)發(fā)現(xiàn)該用戶有高血壓癥狀，其它身體指標(biāo)正常，對(duì)推薦列表TOP 20種菜品進(jìn)行權(quán)重更新；使用優(yōu)化規(guī)則，根據(jù)菜品營(yíng)養(yǎng)表、食補(bǔ)知識(shí)表，即當(dāng)菜品每100 g鈉含量＜350 mg時(shí)，增加該菜品4個(gè)權(quán)重，當(dāng)菜品每100 g鈉含量＞600 mg時(shí)，減少該菜品3個(gè)權(quán)重，提高清淡和有益降血壓菜品的權(quán)重，降低含鈉量大的菜品權(quán)重。如表3部分所示，西紅柿炒蛋、蒜泥菠菜的每100 g鈉含量＜350 mg，土豆燒肉的每100 g鈉含量＞600 mg，故對(duì)西紅柿炒蛋、蒜泥菠菜增加4個(gè)權(quán)重，對(duì)土豆燒肉減少3個(gè)權(quán)重。

表4 食補(bǔ)知識(shí)表（部分）

圖2 高血壓狀況的菜品推薦優(yōu)化流程

下面結(jié)合食品搭配禁忌表排除發(fā)生食品搭配禁忌關(guān)系的菜品，如發(fā)現(xiàn)推薦列表中的韭菜炒雞蛋和蒜泥菠菜是搭配禁忌，通過(guò)權(quán)重進(jìn)行比較，剔除權(quán)重相比較低的菜品，如果權(quán)重相等，隨機(jī)排除其中一種菜品，將排除的菜品權(quán)重更新為-1（代表菜品已經(jīng)從推薦列表中剔除），得到了優(yōu)化后的菜品推薦列表，如圖2(b)。最后，按照權(quán)重從高到底的順序從優(yōu)化后的推薦列表中選擇TOP 10的菜品推薦給用戶，如圖2(c)，優(yōu)化過(guò)程結(jié)束。

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

3.1實(shí)驗(yàn)環(huán)境與數(shù)據(jù)

使用3臺(tái)實(shí)驗(yàn)計(jì)算機(jī)構(gòu)建出一個(gè)主節(jié)點(diǎn)和二個(gè)從屬節(jié)點(diǎn)，并且每臺(tái)計(jì)算機(jī)安裝CentOS 7操作系統(tǒng)，采用SSH工具實(shí)現(xiàn)三臺(tái)計(jì)算機(jī)的相互連接訪問(wèn)。其中實(shí)驗(yàn)軟件包括：JDK1.7、Spark1.2.2；開(kāi)發(fā)工具：IDEA。

食材和菜品資源數(shù)據(jù)來(lái)自薄荷網(wǎng)和美食杰。從薄荷網(wǎng)爬取食材的名稱、食材營(yíng)養(yǎng)成分及含量、菜品的名稱、主料、調(diào)料和各食材使用含量。從美食杰上爬取疾病調(diào)制食品原料和禁忌食品原料、功能性調(diào)制食品原料和菜品等。通過(guò)對(duì)所爬取的信息進(jìn)行冗余數(shù)據(jù)的剔除以及缺失數(shù)據(jù)的填充等清洗數(shù)據(jù)工作后存入數(shù)據(jù)庫(kù)，同時(shí)包括菜品評(píng)分?jǐn)?shù)據(jù)，構(gòu)建出數(shù)據(jù)量在122 019條的數(shù)據(jù)集。

3.2 實(shí)驗(yàn)設(shè)計(jì)

實(shí)驗(yàn)設(shè)計(jì)包括：1）ALS和ALS+規(guī)則匹配算法的準(zhǔn)確率對(duì)比實(shí)驗(yàn)；2）分布式環(huán)境下的ALS和ALS+規(guī)則匹配算法的運(yùn)行時(shí)間對(duì)比實(shí)驗(yàn)。

準(zhǔn)確率對(duì)比測(cè)試。評(píng)價(jià)標(biāo)準(zhǔn)采用均方根誤差衡量個(gè)性化推薦算法的準(zhǔn)確率[22]，如公式（2）

其中rij表示用戶i對(duì)菜品j的歷史評(píng)分，表示rij的預(yù)測(cè)值，T表示測(cè)試集中標(biāo)注的集合，|T|表示測(cè)試集中標(biāo)注的個(gè)數(shù)。

分別選取 20 000、40 000、60 000、80 000、100 000條數(shù)據(jù)，在Spark上實(shí)現(xiàn)ALS和ALS+規(guī)則匹配算法的運(yùn)行時(shí)間對(duì)比實(shí)驗(yàn)。

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

實(shí)驗(yàn)時(shí)，在不同數(shù)量的實(shí)驗(yàn)數(shù)據(jù)上，首先僅使用ALS算法，然后再采用ALS與規(guī)則匹配相結(jié)合的算法進(jìn)行實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如圖3。

圖3 準(zhǔn)確率對(duì)比實(shí)驗(yàn)結(jié)果

由圖3可知，實(shí)驗(yàn)數(shù)據(jù)增大時(shí)，ALS算法的均方根誤差呈現(xiàn)上升趨勢(shì)，而ALS+規(guī)則匹配算法均方根誤差呈現(xiàn)下降趨勢(shì)，達(dá)到較為滿意的預(yù)期效果。當(dāng)實(shí)驗(yàn)數(shù)據(jù)量為20 000和40 000時(shí)，兩個(gè)算法的均方根誤差基本一致；當(dāng)數(shù)據(jù)量大于40 000時(shí)，ALS算法的均方根誤差呈現(xiàn)上升趨勢(shì)，ALS+規(guī)則匹配算法的均方根誤差呈現(xiàn)穩(wěn)定緩降趨勢(shì)；當(dāng)數(shù)據(jù)量大于60 000時(shí)，ALS算法的均方根誤差上升趨勢(shì)顯著，ALS+規(guī)則匹配算法的均方根誤差下降趨勢(shì)明顯。對(duì)結(jié)果進(jìn)行分析，可能原因如下：隨著用戶個(gè)性化需求屬性的增加，ALS算法漸漸難以滿足這一復(fù)雜的個(gè)性化需求，這是由于ALS算法主要是基于用戶評(píng)分?jǐn)?shù)據(jù)進(jìn)行計(jì)算，而ALS+規(guī)則匹配即滿足用戶的食品喜好需求，而且通過(guò)結(jié)合用戶的身體狀況、食品、食療、食品搭配禁忌知識(shí)庫(kù)對(duì)ALS的推薦結(jié)果進(jìn)行反復(fù)迭代和重新排序，從而滿足了用戶的“喜好+健康”需求。

由圖4，可以發(fā)現(xiàn)ALS和ALS+規(guī)則匹配算法在運(yùn)行時(shí)間上相差較小。隨著數(shù)據(jù)量的增加，ALS和ALS+規(guī)則匹配算法的運(yùn)行時(shí)間呈線性趨勢(shì)上升。在不同數(shù)據(jù)量時(shí)，兩者運(yùn)行時(shí)間大致相同。分析原因如下：ALS+規(guī)則匹配算法主要是基于ALS算法生成的推薦列表，規(guī)則匹配主要是對(duì)推薦列表進(jìn)行優(yōu)化，對(duì)算法的時(shí)間復(fù)雜度影響不大，因此，當(dāng)數(shù)據(jù)量相同時(shí)，ALS算法和ALS+規(guī)則匹配算法兩者的運(yùn)行時(shí)間相差很小。

圖4 運(yùn)行時(shí)間對(duì)比實(shí)驗(yàn)結(jié)果

4 小結(jié)

本文針對(duì)用戶對(duì)飲食的營(yíng)養(yǎng)搭配關(guān)注度不高的需求問(wèn)題，首先采用基于矩陣分解的ALS算法對(duì)用戶偏好數(shù)據(jù)進(jìn)行了處理，獲得了初步的飲食推薦列表，然后再利用營(yíng)養(yǎng)搭配數(shù)據(jù)庫(kù)和用戶特殊需求等數(shù)據(jù)，使用規(guī)則匹配算法優(yōu)化了推薦列表。實(shí)驗(yàn)數(shù)據(jù)表明，隨著數(shù)據(jù)量增大，該算法具有較低的均方根誤差。這說(shuō)明該算法獲得的飲食推薦列表在營(yíng)養(yǎng)搭配方面一定程度上是合適的。目前，該算法還有較多不完善之處，如算法準(zhǔn)確率的提升、超大數(shù)據(jù)量的算法準(zhǔn)確率測(cè)試和算法改進(jìn)、菜品推薦依賴數(shù)據(jù)維度不夠、膳食搭配合理性解釋等，有待改進(jìn)或解決。未來(lái)將繼續(xù)針對(duì)食品/菜品推薦算法做更近一步的研究，在推薦中融入對(duì)算法的性能優(yōu)化和用戶中醫(yī)體質(zhì)數(shù)據(jù)等信息。