張奧多 張昕 李怡婷

摘 要：為了節(jié)省客戶的點餐時間，方便客戶從海量菜品中找到理想的菜品，本文嘗試將關(guān)聯(lián)規(guī)則與餐飲服務(wù)相結(jié)合.通過引入FP-tree關(guān)聯(lián)規(guī)則算法，并利用得到的菜品推薦公式中的關(guān)聯(lián)度指標，再綜合商家利益最大化、熱銷菜品等因素及其重要程度創(chuàng)建菜品推薦綜合評分公式.基于綜合評分對各菜品進行推薦排序，排序結(jié)果最終以移動方式推送給顧客，實現(xiàn)菜品動態(tài)推薦服務(wù).

關(guān)鍵詞：個性化；推薦系統(tǒng)；數(shù)據(jù)挖掘；關(guān)聯(lián)規(guī)則

中圖分類號：TP274∶TS97 文獻標志碼：A

0 引言

近年來，隨著互聯(lián)網(wǎng)的飛速發(fā)展，人們的日常生活中產(chǎn)生了越來越多的數(shù)據(jù)信息，如此大量的數(shù)據(jù)信息滿足了用戶在大數(shù)據(jù)時代對數(shù)據(jù)的需求[1].基于互聯(lián)網(wǎng)的智能推薦系統(tǒng)在人們的生活中占了越來越大的比重.智能推薦系統(tǒng)主要技術(shù)手段是數(shù)據(jù)挖掘技術(shù)[2-3]，即基于用戶喜愛商品的行為，相關(guān)網(wǎng)站通過算法在全網(wǎng)的商品庫里匹配然后進行推薦.智能推薦通常是將當(dāng)前熱門的、用戶以往收藏或者購買的風(fēng)格和用戶類似喜好的風(fēng)格的物品推薦給用戶.餐飲服務(wù)智能推薦系統(tǒng)是針對智能推薦系統(tǒng)的進一步細化，作為必不可少的衣食住行之一的餐飲行業(yè)，與人們的生活密不可分，而在就餐時，顧客經(jīng)常在大量的菜品信息中，無法真正找到自己想要的菜品.因此，就應(yīng)運產(chǎn)生了餐飲服務(wù)智能推薦系統(tǒng)[4].

其中，菜品智能推薦系統(tǒng)是餐飲服務(wù)智能推薦系統(tǒng)的進一步細化，它的任務(wù)是將菜品呈現(xiàn)在顧客面前，一方面幫助顧客發(fā)現(xiàn)他們感興趣的菜品，另一方面讓餐飲企業(yè)期望推薦的菜品能夠展現(xiàn)在對它有興趣的顧客面前，從而實現(xiàn)餐飲消費者和餐飲企業(yè)的雙贏.菜品智能推薦是幫助顧客發(fā)現(xiàn)合適的菜品，克服信息過載的方法.通過分析顧客的行為，對顧客興趣建模，從而預(yù)測顧客的興趣和喜好，并給顧客做相關(guān)聯(lián)的菜品推薦.

1 工作流程及具體實現(xiàn)

1.1 推薦系統(tǒng)的工作流程

動態(tài)菜品智能推薦系統(tǒng)的工作流程包括菜品數(shù)據(jù)采集、菜品數(shù)據(jù)預(yù)處理、菜品推薦綜合評分、動態(tài)智能推薦.流程圖如圖1所示，具體步驟如下：

Step 1 菜品數(shù)據(jù)采集：從餐飲企業(yè)采集用于計算菜品綜合評分相關(guān)的數(shù)據(jù)，如顧客點餐數(shù)據(jù)、各類菜品單價成本數(shù)據(jù)、店家主推菜品數(shù)據(jù)等.

Step 2 菜品數(shù)據(jù)預(yù)處理：菜品數(shù)據(jù)預(yù)處理主要是對采集的數(shù)據(jù)進行清洗、數(shù)據(jù)變換，將原始數(shù)據(jù)轉(zhuǎn)換成“適當(dāng)?shù)摹备袷剑赃m應(yīng)后續(xù)計算菜品推薦綜合評分的需要.通過數(shù)據(jù)預(yù)處理后將得到菜品熱銷度評分、店家主推度修正系數(shù)、菜品毛利率修正系數(shù)、菜品關(guān)聯(lián)度修正系數(shù).

Step 3 菜品推薦綜合評分：從菜品熱銷度、店家主推度、菜品毛利率、菜品關(guān)聯(lián)度等維度來計算某項菜品的推薦分值，菜品推薦分值大小一方面反映了顧客對菜品的喜好度，另一方面反映了餐飲企業(yè)對菜品主動推送的期望度.

Step 4 動態(tài)智能推薦：基于綜合評分可對各菜品進行推薦排序，排序結(jié)果最終以移動服務(wù)的方式推送給餐飲點餐顧客，實現(xiàn)菜品動態(tài)推薦服務(wù).

1.2 菜品數(shù)據(jù)預(yù)處理

菜品數(shù)據(jù)的預(yù)處理主要對采集的數(shù)據(jù)進行清洗、數(shù)據(jù)變換，通過數(shù)據(jù)預(yù)處理后將得到店家主推度修正系數(shù)、菜品熱銷度評分、菜品毛利率修正系數(shù)、菜品關(guān)聯(lián)度系數(shù).數(shù)據(jù)預(yù)處理的具體步驟如下：

Step 1 菜品熱銷度評分是根據(jù)餐飲企業(yè)最近30天的菜品銷售記錄，匯總后的排名經(jīng)規(guī)范化后的計算得分，最高為1分，最低為0分.

？酌熱銷度評分=（1）

式（1）中：？酌熱銷度評分——某項菜品的熱銷度評分，取值范圍：0～1；Qi——某項菜品的銷售份數(shù)，其值大于0；Qmax——該餐飲企業(yè)最近30天內(nèi)有銷售記錄的菜品中的最大銷售份數(shù)；Qmin——該餐飲企業(yè)最近30 天內(nèi)有銷售記錄的菜品中的最小銷售份數(shù).

Step 2 店家主推度修正系數(shù)是針對新推出的菜品做出排序得分，最高為1，最低為0.1，系數(shù)越高表示店家越期望推薦給顧客.該系數(shù)由管理員在前臺界面維護設(shè)置，如表1所示，其中對于未設(shè)置主推系數(shù)的菜品，主推系數(shù)默認為0.1.

Step 3 菜品毛利率修正系數(shù)是根據(jù)菜品的單價和成本計算得到毛利率，再經(jīng)歸一化后得到的結(jié)果.

？酌毛利率=■（2）

式（2）中：？酌毛利率為某項菜品的毛利率修正系數(shù)，取值范圍：0.1～1，當(dāng)值為負時設(shè)為0.1；？籽單價為某項菜品的單價，？籽成本為某項菜品的估計成本.

Step 4 菜品關(guān)聯(lián)度修正系數(shù)是基于歷史點餐數(shù)據(jù)，采用FP關(guān)聯(lián)規(guī)則算法[5]得到菜品的關(guān)聯(lián)度推薦評分值，再經(jīng)歸一化后的結(jié)果，反映了各菜品與顧客已點菜品的關(guān)聯(lián)程度.

關(guān)聯(lián)規(guī)則[6-7]是形如X→Y的函數(shù)（X項集和Y項集不相交）.引入兩個概念用來衡量關(guān)聯(lián)規(guī)則的強度.一是支持度（support），用于確定規(guī)則可以對給定數(shù)據(jù)集的頻繁程度；二是置信度（confidence），用于確定項集Y在包含項集X的事務(wù)中出現(xiàn)的頻繁程度.

支持度（s）形式定義：

s（X→Y）=■ （3）

置信度（c）形式定義：

c（X→Y）=■（4）

支持度很低的規(guī)則出現(xiàn)，很可能只是偶然，所以可以確定閾值來刪去那些沒有意義的支持度較低的規(guī)則.

一般對于給定的規(guī)則，置信度與包含的事務(wù)中出現(xiàn)的可能性成正比關(guān)系，即置信度越小，包含事務(wù)中出現(xiàn)的可能性也就越小.而在特定的支持度和置信度閾值下，即使數(shù)量很少的原數(shù)據(jù)集也會產(chǎn)生難以計算的關(guān)聯(lián)規(guī)則，故本文介紹的餐飲服務(wù)智能推薦系統(tǒng)采用FP增長算法，根據(jù)最小支持度閾值找出頻繁項集，得到頻繁項集之后，再由頻繁項集產(chǎn)生滿足一定支持度和置信度條件的強關(guān)聯(lián)規(guī)則.

1.3 推薦系統(tǒng)的具體實現(xiàn)

1.3.1 基于關(guān)聯(lián)規(guī)則的推薦算法

經(jīng)過數(shù)據(jù)預(yù)處理后，基于關(guān)聯(lián)規(guī)則的餐飲服務(wù)智能推薦算法的描述如下：

引進FP-tree算法[8]，該算法只進行兩次菜品數(shù)據(jù)庫掃描，直接壓縮數(shù)據(jù)庫成一個頻繁模式樹并生成關(guān)聯(lián)規(guī)則.

算法關(guān)鍵步驟：Step 1利用菜品數(shù)據(jù)庫中的數(shù)據(jù)構(gòu)造FP-tree；Step 2從FP-tree中挖掘頻繁模式.

1） 構(gòu)建FP-tree

如表2所示的一個菜品數(shù)據(jù)集，它包含10個菜品組和5種菜品.

在第一次掃描歷史點餐數(shù)據(jù)集之后，得到所有項的支持度度量計數(shù).由于支持度很低的規(guī)則出現(xiàn)很可能只是偶然，所以將非頻繁項丟棄，然后將頻繁項按照支持度的遞減順序排序.

隨后進行第二次掃描，構(gòu)建FP-tree.讀入第一個菜品組之后，創(chuàng)建標記結(jié)點；然后形成路徑，對該組菜品編碼，該路徑上的所有結(jié)點的頻度計數(shù)為1.

讀入第二組菜品后，為菜品項創(chuàng)建新的結(jié)點集；然后，連接結(jié)點形成一條代表該菜品組的路徑，該路徑上每個結(jié)點的頻度計數(shù)等于1.盡管前兩個菜品組都具有共同一個菜品，但是它們的路徑不相交，因為這兩個菜品組沒有共同的前綴.

第三個菜品組與第一個菜品組共享一個前綴，所以第三個菜品組的路徑與第一個菜品組的路徑部分組合.因為它們的部分路徑相同，于是將菜品結(jié)點的頻度計數(shù)增加為2，而新創(chuàng)建的結(jié)點的頻度計數(shù)均等于1.圖2為讀入前3個菜品組之后的FP-tree的結(jié)構(gòu).

繼續(xù)該過程，直到每個菜品組都映射到FP-tree的一條路徑，讀入第10個菜品組之后的FP-tree的結(jié)構(gòu)如圖3所示.

2） FP增長算法產(chǎn)生頻繁項集

FP增長（FP-growth）是對FP-tree自F而上的方法進行探索產(chǎn)生頻繁項集的算法[9].算法首先查找以菜品e結(jié)尾的頻繁項集，然后使用FP-tree增長算法發(fā)現(xiàn)以e結(jié)尾的頻繁項集，如圖4所示.接下來是菜品d，菜品c和菜品b，最后是菜品a.

先收集包含菜品結(jié)點的所有路徑，這些初始的路徑稱為前綴路徑[10]（prefix path）.

由前綴路徑，通過把與菜品結(jié)點相關(guān)聯(lián)的支持度相加得到菜品的支持度計數(shù).假定最小支持度為2，由于菜品e的支持度為3大于2，所以它是頻繁項集.需要找到那些以菜品de，ce，be和ae結(jié)尾的頻繁項集的子問題，并加以解決.在此之前，必須先找到前綴路徑，然后將其轉(zhuǎn)化為條件FP-tree.條件FP-tree與FP-tree結(jié)構(gòu)上類似，但條件FP-tree可以用來發(fā)現(xiàn)以某特定后綴結(jié)尾的頻繁項集.條件FP-tree通過以下步驟得到.

Step 1 首先，重新計算前綴路徑上的支持度度量，因為某些度量包含那些不含菜品e的菜品組；

Step 2 刪除菜品e的結(jié)點，修剪前綴路徑.原因是沿這些前綴路徑的支持度度量已經(jīng)更新，發(fā)現(xiàn)以de，ce，be，ae結(jié)尾的頻繁項集的子問題不再需要菜品結(jié)點的信息；

Step 3 當(dāng)重新計算沿前綴路徑上的支持度度量后，一些項的頻繁狀態(tài)可能會發(fā)生改變.例如，菜品b只出現(xiàn)了一次，它的支持度為1，意思是同時包含菜品b和菜品e的組合只有一個.因為任何以菜品b，e結(jié)尾的菜品項集肯定不是頻繁項集，所以在將來的研究中可以直接忽略菜品b.

在找到菜品a和e結(jié)尾的頻繁項集的子問題之后，可以通過FP增長，使用菜品e的條件FP-tree來找到并解決.首先需要找到以菜品a和e結(jié)尾的頻繁項集，可以從菜品的條件FP-tree來發(fā)現(xiàn)菜品a的前綴路徑；然后利用菜品結(jié)點d相關(guān)聯(lián)的頻度計數(shù)求和，得支持度計數(shù)為2的頻繁項集；之后構(gòu)建菜品de的條件FP-tree.重新計算了支持度度量并修剪了不是頻繁項集的菜品c.原因是該條件FP-tree只包含了菜品a（支持度等于最小支持度的項），算法在找出頻繁項集之后轉(zhuǎn)到其他子問題，最后產(chǎn)生的頻繁項集是以菜品ce結(jié)尾.在修剪完菜品的前綴路徑后，只發(fā)現(xiàn)項集{c，e}是頻繁的，在此之后，待算法繼續(xù)處理之后的子問題時會發(fā)現(xiàn)只有項集{a，e}是頻繁項集.得到頻繁項集后，將它們各自全排序之后再輸出.

3） 產(chǎn)生強關(guān)聯(lián)規(guī)則

前面已經(jīng)用最小支持度閾值找出所有的頻繁項集，接著再使用最小置信度閾值由頻繁項集產(chǎn)生強關(guān)聯(lián)規(guī)則.

先驗原理：確定一個項集，假定該項集是頻繁的，那么其所有子集也肯定是頻繁的.

由先驗原理知如果頻繁項集存在，那么其頻繁子項集必然存在.故對于頻繁項集，計算其對應(yīng)頻繁子項集的置信度，使用頻繁項集的支持度除以對應(yīng)頻繁子項集的支持度得到頻繁項集的置信度.

若菜品置信度大于設(shè)定的閾值，則將它們輸出，并對它們的置信度歸一化后作為對應(yīng)的關(guān)聯(lián)度.

1.3.2 菜品推薦綜合評分

本文所述的菜品推薦系統(tǒng)是對菜品關(guān)聯(lián)系數(shù)、店家主推、菜品毛利率、菜品熱銷度的綜合考量，某項菜品推薦綜合評分計算公式如下：

S綜合評分=（E-Y）AYT（5）

其中：

E=（1，1，1，1）；Y=（？酌熱銷度評分，？酌店家主推度，？酌毛利率，？酌關(guān)聯(lián)度）；A=，？琢1+？琢2+？琢3+？琢4=10.

S綜合評分——某項菜品推薦綜合評分，取值范圍0～40；？酌熱銷度評分——某項菜品熱銷度的評分，取值范圍0～1，？琢1為其權(quán)值；？酌店家主推度——店家對某項菜品的主推修正系數(shù)，取值范圍0.1～1.0，？琢2為其權(quán)值；？酌毛利率——某項菜品的毛利率修正系數(shù)，取值范圍0.1～1.0，？琢3為其權(quán)值；？酌關(guān)聯(lián)度——某項菜品與已選菜品的關(guān)聯(lián)度修正系數(shù)，取值范圍0.1～1.0，？琢4為其權(quán)值.（注：4種評分因素分配的權(quán)值不同則菜品推薦綜合評分的取值也會不同，但無論怎么分配，都不會超出0～40的范圍.）

傳統(tǒng)綜合評分公式只能對每個指標加權(quán)求和得到綜合評分，而該新公式在此基礎(chǔ)上加入后綴影響因式，可以自行根據(jù)指標數(shù)值的情況提升重要指標（占權(quán)值較大的指標）排序時的優(yōu)勢地位，即權(quán)值較大的指標值越大，在總體中排序更具優(yōu)勢.但綜合評分排序并不會完全按照權(quán)值大的指標的數(shù)值大小去排序，而是還會考慮其他指標的影響.

2 智能推薦系統(tǒng)的應(yīng)用實例

為了驗證新推薦綜合評分算法的有效性，說明算法的優(yōu)良特點，設(shè)計下面實驗將此算法與一般綜合評分算法進行驗證和比較研究.

某顧客在某餐館先點了皮蛋瘦肉粥，從該餐館收集相關(guān)菜品數(shù)據(jù)如表3，它包含12個菜品組和20個菜品.

掃描表3菜品數(shù)據(jù)集，統(tǒng)計每個菜品的支持度計數(shù)如表4所示.

設(shè)最小支持度為2，丟棄非頻繁項，得到頻繁項，按照支持度遞減的排序為：皮蛋瘦肉粥、排骨拼鳳爪、香煎蔥油餅、陳皮蒸牛丸、香煎蔥油餅、特色蛋松、白灼生菜、上湯云吞面.

接著按照上述算法構(gòu)建FP-tree和FP增長算法，產(chǎn)生以皮蛋瘦肉粥結(jié)尾的頻繁項集，并將其中歸一化后達到最小置信度0.40的具有強關(guān)聯(lián)規(guī)則的項集輸出：{排骨拼鳳爪，皮蛋瘦肉粥}、{香煎蔥油餅，皮蛋瘦肉粥}、{陳皮蒸牛丸、皮蛋瘦肉粥}、{香煎蔥油餅、皮蛋瘦肉粥}、{特色蛋松、皮蛋瘦肉粥}，它們的置信度分別為：0.80，0.70，0.50，0.40，0.40.

整理與皮蛋瘦肉粥具有強關(guān)聯(lián)規(guī)則的5個菜品的銷售量、單價、成本的數(shù)據(jù)如表5示.

根據(jù)原始數(shù)據(jù)及式（1）—式（4），計算出熱銷度評分、毛利率、店家主推度、關(guān)聯(lián)度.現(xiàn)將4種數(shù)據(jù)變量整理如表6所示.

根據(jù)經(jīng)驗設(shè)定權(quán)值，由傳統(tǒng)綜合評分公式和本文綜合評分公式分別計算得到各菜品的綜合分數(shù)如表7.

對比分析兩種方法：由傳統(tǒng)方法計算出的香煎蔥油餅和特色蛋松的分數(shù)都是6，故當(dāng)顧客先點了皮蛋瘦肉粥和樂膳蝦餃皇，智能推薦這兩菜品處于同等推薦位置，但顯然是不合理的，因為香煎蔥油餅與皮蛋瘦肉粥和樂膳蝦餃皇關(guān)聯(lián)度是0.7，遠遠大于特色蛋松與皮蛋瘦肉粥和樂膳蝦餃皇的關(guān)聯(lián)度0.4，香煎蔥油餅應(yīng)比特色蛋松更具有推薦優(yōu)勢位置，且香煎蔥油餅和特色蛋松的分數(shù)差為1.184也在合理范圍內(nèi)，不會太懸殊.

特色蛋松和香煎韭菜餃的關(guān)聯(lián)度都是0.4，特色蛋松熱銷度0.70，毛利率0.62，主推度0.90，對應(yīng)香煎韭菜餃熱銷度0.85，毛利率0.60，主推度0.70，推測它們的推薦地位應(yīng)該是比較接近的.而特色蛋松與香煎菜餃的改進式分數(shù)只相差0.033 5，比它們的一般式分數(shù)差0.225 0更符合實際.

3 結(jié)束語

本文致力于設(shè)計一種基于關(guān)聯(lián)規(guī)則綜合評分算法的餐飲服務(wù)智能推薦系統(tǒng).根據(jù)已點菜品的關(guān)聯(lián)度、商家利益最大化、熱銷菜品等因素，以及各因素的重要程度創(chuàng)建菜品推薦綜合公式，基于綜合評分對各菜品進行推薦排序，排序結(jié)果最終以移動方式推送給顧客，實現(xiàn)菜品動態(tài)推薦服務(wù)，幫助顧客快速發(fā)現(xiàn)自己感興趣的菜品；同時餐飲企業(yè)發(fā)現(xiàn)了客戶同時選擇的多種菜品間的關(guān)聯(lián)關(guān)系 ，并采取相應(yīng)措施 ，既穩(wěn)定了客戶，營業(yè)利潤也得到了相應(yīng)提高[11]，從而實現(xiàn)消費者和餐飲企業(yè)的雙贏[12].經(jīng)驗證，本文所提出的餐飲服務(wù)智能推薦系統(tǒng)優(yōu)于傳統(tǒng)的推薦算法，既能夠兼顧顧客對菜品的興趣愛好，又能有效的為餐飲企業(yè)提升菜品銷售量，提高餐飲企業(yè)的收入.

參考文獻

[1] 朱建軍， 周強. 互聯(lián)網(wǎng)信息生命周期研究[J]. 鐵路計算機應(yīng)用， 2015，24（3）：45-49.

[2] 沙志強. 數(shù)據(jù)挖掘技術(shù)在智能推薦系統(tǒng)中的研究與應(yīng)用[D]. 北京：北京工業(yè)大學(xué)， 2005.

[3] 翟悅. 改進的關(guān)聯(lián)規(guī)則挖掘算法在個性化推薦系統(tǒng)中應(yīng)用[D]. 大連：大連交通大學(xué)， 2008.

[4] 廖旺宇. 基于關(guān)聯(lián)規(guī)則的智能點餐推薦系統(tǒng)設(shè)計[J].四川烹飪高等專科學(xué)校學(xué)報， 2012（4）：32-36.

[5] 莫同， 褚偉杰， 李偉平， 等. 一種基于擴展FP-TREE的服務(wù)推薦方法[J]. 華中科技大學(xué)學(xué)報（自然科學(xué)版）， 2013（S2）：81-87.

[6] 張勇杰， 楊鵬飛， 段群， 等. 基于關(guān)聯(lián)規(guī)則的商品智能推薦算法[J]. 現(xiàn)代計算機， 2016（7）：25-27.

[7] 張晶晶. 基于關(guān)聯(lián)規(guī)則的電子商務(wù)智能推薦系統(tǒng)研究[D]. 鞍山：遼寧科技大學(xué)， 2012.

[8] 孫自廣.FP-growth頻繁集挖掘算法的分析與實現(xiàn)[J].廣西工學(xué)院學(xué)報，2005，16（3）：64-67.

[9] YUAN J B，DING S L. Research and improvement on association rule algorithm based on FP-growth[J].Springer Berlin Heiclelberg，

2012，7529：306-313.

[10] 翁偉， 林開標， 朱順痣， 等. 基于最長前綴頻繁子路徑樹的Web日志挖掘算法[J]. 成都大學(xué)學(xué)報（自然科學(xué)版）， 2013， 32（3）：285-288.

[11] 韋艷玲.關(guān)聯(lián)規(guī)則在健身服務(wù)項目組合中的數(shù)據(jù)挖掘[J].廣西工學(xué)院學(xué)報，2008，19（2）：62-65，70.

[12] 張良均， 云偉標， 王路， 等. R語言數(shù)據(jù)分析與挖掘?qū)崙?zhàn)[M]. 北京：機械工業(yè)出版社，2015.

One intelligent recommendation system for catering service

based on association rules

ZHANG Ao-duo1，2， ZHANG Xin*1， LI Yi-ting2

（1. College of Mathematics and Informatics， South China Agricultural University， Guangzhou 510642， China；

2.TipDM Intelligent Technology Co.， Ltd.， Guangzhou 510670， China）

Abstract：With the advent of the information era， the relationship between e-commerce and data mining becomes closer， and personalized recommendation service gradually walks into our daily life. In order to save the time of ordering dishes， and to help customers find their favorite dishes from numerous dishes， this paper attempts to develop an intelligent recommendation system for catering service based on the association rules. We establish the comprehensive score formula of dish selection by introducing the FP-tree association rules， using the correlation index of the recommended formula and synthesizing some factors such as the maximum of benefits， hot dishes， etc. The dishes recommendation service is based on the rank of comprehensive score and the sorted results are finally pushed to the customer in a mobile way.

Key words： personalization； recommendation system； data mining； association rules

（學(xué)科編輯：黎 婭）