基于關聯(lián)規(guī)則的餐飲服務智能推薦系統(tǒng)

張奧多 張昕 李怡婷

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

關鍵詞：個性化；推薦系統(tǒng)；數(shù)據(jù)挖掘；關聯(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ù)據(jù)挖掘技術[2-3]，即基于用戶喜愛商品的行為，相關網(wǎng)站通過算法在全網(wǎng)的商品庫里匹配然后進行推薦.智能推薦通常是將當前熱門的、用戶以往收藏或者購買的風格和用戶類似喜好的風格的物品推薦給用戶.餐飲服務智能推薦系統(tǒng)是針對智能推薦系統(tǒng)的進一步細化，作為必不可少的衣食住行之一的餐飲行業(yè)，與人們的生活密不可分，而在就餐時，顧客經(jīng)常在大量的菜品信息中，無法真正找到自己想要的菜品.因此，就應運產(chǎn)生了餐飲服務智能推薦系統(tǒng)[4].

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

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

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

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

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

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

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

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

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

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

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ù)由管理員在前臺界面維護設置，如表1所示，其中對于未設置主推系數(shù)的菜品，主推系數(shù)默認為0.1.

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

？酌毛利率=■（2）

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

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

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

支持度（s）形式定義：

s（X→Y）=■ （3）

置信度（c）形式定義：

c（X→Y）=■（4）

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

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

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

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

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

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

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

1） 構建FP-tree

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1.3.2 菜品推薦綜合評分

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

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

其中：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 結束語

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

參考文獻

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

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

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

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

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

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

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

[8] 孫自廣.FP-growth頻繁集挖掘算法的分析與實現(xiàn)[J].廣西工學院學報，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]. 成都大學學報（自然科學版）， 2013， 32（3）：285-288.

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

[12] 張良均， 云偉標， 王路， 等. R語言數(shù)據(jù)分析與挖掘實戰(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

（學科編輯：黎 婭）