廖旺宇

(四川烹飪高等?？茖W(xué)校，四川 成都 610100)

隨著餐飲企業(yè)信息化應(yīng)用的不斷深入，經(jīng)營者在經(jīng)營過程中可以采集到大量的客戶點餐數(shù)據(jù)。但由于數(shù)據(jù)量過大，又缺乏有效的處理手段，因此，這些數(shù)據(jù)往往無法轉(zhuǎn)化為幫助提升管理水平和經(jīng)營業(yè)績的知識。同時，客戶在點餐過程中面對菜單中大量的菜品信息可能無法快速找到滿意的菜品。運用電子商務(wù)和數(shù)據(jù)挖掘的知識，利用企業(yè)已經(jīng)擁有的點餐數(shù)據(jù)，設(shè)計開發(fā)點餐推薦系統(tǒng)，有針對性地向客戶推薦菜品，幫助其制定出更適合的食譜則成為有效解決上述問題的方法。

以商業(yè)目的作為依據(jù)，電子商務(wù)推薦系統(tǒng)分為面向產(chǎn)品的推薦和面向客戶的推薦兩類。常用的方法有Top N推薦法、新品推薦法和關(guān)聯(lián)推薦法等。［1］所謂關(guān)聯(lián)推薦法，主要指通過使用數(shù)據(jù)挖掘中關(guān)聯(lián)規(guī)則挖掘技術(shù)，深入分析用戶數(shù)據(jù)，得到用戶的消費規(guī)則，并以此為依據(jù)進行消費推薦。

由Agrawal R等人提出的關(guān)聯(lián)規(guī)則挖掘［2］已經(jīng)成為數(shù)據(jù)挖掘領(lǐng)域的重要研究課題。但是，傳統(tǒng)、經(jīng)典的關(guān)聯(lián)規(guī)則算法，如Apriori等，在目標(biāo)數(shù)據(jù)集發(fā)生變化，甚至僅僅是最小支持度閾值發(fā)生改變時運行效率便會大幅度降低。為了在目標(biāo)數(shù)據(jù)集中數(shù)據(jù)增加、減少和數(shù)據(jù)集不變，但最小支持度閾值發(fā)生改變［3-4］時高效獲取關(guān)聯(lián)規(guī)則，產(chǎn)生了增量關(guān)聯(lián)規(guī)則挖掘算法。

在點餐推薦的實際應(yīng)用中，一方面點餐信息數(shù)據(jù)在不斷地增長，且隨著時間的發(fā)展，菜品的流行程度也會相應(yīng)發(fā)生改變;另一方面，在進行菜品推薦時往往更注重推薦某些重點菜品，使得用戶往往只關(guān)注所獲得的規(guī)則中與重點推薦的菜品相關(guān)的規(guī)則。

本文在原有的“適合高效更新的關(guān)聯(lián)規(guī)則挖掘算法”［5］的基礎(chǔ)上，根據(jù)上述點餐推薦實際應(yīng)用的具體情況，提出了面向分類預(yù)測的增量關(guān)聯(lián)規(guī)則挖掘算法。該算法可以通過分析已有的點餐數(shù)據(jù)，高效獲取可能選取企業(yè)希望推薦的重點菜品的目標(biāo)客戶的點餐特征，作為向其他客戶進行菜品推薦的依據(jù)。并且，算法可以保證在數(shù)據(jù)集中的數(shù)據(jù)發(fā)生增長時，有效減少對數(shù)據(jù)集重復(fù)掃描的次數(shù)、保證執(zhí)行效率。最后，還在此基礎(chǔ)上對點餐推薦系統(tǒng)的結(jié)構(gòu)設(shè)計進行了研究。

1 面向分類預(yù)測的增量關(guān)聯(lián)規(guī)則算法

1.1 算法基礎(chǔ)［6］

設(shè)原目標(biāo)數(shù)據(jù)集為DB，其包含的事務(wù)總數(shù)為|DB|，新增加的數(shù)據(jù)集為db，其包含的事務(wù)總數(shù)為|db|，DB+db為增加數(shù)據(jù)后的新目標(biāo)數(shù)據(jù)集。

設(shè)用戶給定的最小支持度閾值為minsup，若數(shù)據(jù)集DB、db、DB+db的候選項集中的項頻繁，則其所需滿足的最小支持度計數(shù)分別為c0=minsup*|DB|、c1=minsup*|db|、c2=minsup*|DB +db|，且顯然有c2=c0+c1。

設(shè)數(shù)據(jù)集DB、db、DB+db的實際支持度計數(shù)分別為s0、s1、s2，則有s2=s0+s1。

為便于討論，設(shè)fx=cx-sx(x=0，1，2)，顯然有：若f≤0，則該候選項集為數(shù)據(jù)集中的頻繁項集;若f＞0，則該候選項集為數(shù)據(jù)集中的非頻繁項集，且f2=f0+f1。

性質(zhì)1：若一個候選項集在DB中為頻繁項集，且在db中為頻繁項集，則該候選項在DB+db中為頻繁項集。

證明：因為候選項在DB中為頻繁項集，所以f0≤0，又：該候選項在db中為頻繁項集，所以f1≤0，于是有f2=f0+f1≤0，即該候選項集在DB+db中為頻繁項集。

性質(zhì)2：若一個候選項集在DB中為非頻繁項集，且在db中也為非頻繁項集，則該候選項集在DB+db中為非頻繁項集。

證明：因為候選項在DB中為非頻繁項集，所以f0＞0，又：該候選項在db中為非頻繁項集，所以f1＞0，于是有f2=f0+f1＞0，即該候選項集在DB+db中為非頻繁項集。

性質(zhì)3：若一個候選項在DB和db中分別為頻繁項集、非頻繁項集或非頻繁項集、頻繁項集，則該候選項集在DB+db中是否為頻繁項集不確定。

證明：當(dāng)一個候選項集在DB和db中分別為頻繁項集、非頻繁項集時，f0為負(fù)、f1為正;當(dāng)一個候選項集在DB和db中分別為非頻繁項集、頻繁項集時，f0為正、f1為負(fù)。在這兩種情況下都無法判斷f2=f0+f1為正或為負(fù)，所以該候選項集在DB+db中是否為頻繁項集不確定。

此時，只能通過將其在DB+db中的計數(shù)與(|DB|+|db|)*minsup比較進行判斷。而該候選項集在DB+db中的支持度計數(shù)可以通過已知的其在DB和db中的支持度計數(shù)相加容易地得到。

因此，候選項集頻繁與否的判斷方式可以歸納為表1：

表1 正增量更新時候選項頻繁狀況判定表

由于本算法在對關(guān)聯(lián)規(guī)則進行增量更新的時候，主要處理的是新增加的數(shù)據(jù)集db，且因為db的加入使得挖掘的目標(biāo)數(shù)據(jù)集的大小呈現(xiàn)正增長，因此，本文又將本算法稱為分類預(yù)測關(guān)聯(lián)規(guī)則的正增量更新算法。

1.2 算法描述

正增量式分類關(guān)聯(lián)規(guī)則挖掘算法分為兩個步驟：首先，高效統(tǒng)計出新增數(shù)據(jù)集db中的每一非空項集的支持度計數(shù);然后，利用該結(jié)果和已知的原數(shù)據(jù)集DB的挖掘結(jié)果，按照表1中的判定方法生成數(shù)據(jù)集DB+db滿足用戶指定的最小支持度閾值的頻繁項集。

對于每一個項集都有一個count域來存儲其支持度計數(shù)，算法描述如下：

算法1：統(tǒng)計各項集的支持度計數(shù)。

輸入：新增的數(shù)據(jù)集db，項集I={i1，i2，…，im}。

輸出：所有支持度計數(shù)非零的項集所產(chǎn)生的候選集C’，及C’中每一項集所對應(yīng)的支持度計數(shù)。

算法描述：

1)初始化，令候選項集集合C’=?

2)設(shè)置關(guān)注的項目類別為項集中的項目ix

3)FOR all records t∈db do

3.1)FOR all itemsets c’?t do

3.2) 若c’包含項目ix

3.3) IF c’∈C’THEN //若c’存在于C’中

3.4) c’.count+ + //c’的支持度計數(shù)增加1

3.5) ELSE

3.6) C’=C’∪{c’} //將c’加入到C’中

3.7) c’.count=1 //設(shè)置其支持度計數(shù)為1

3.8) FOR all itemsets c’∈C’do //求當(dāng)前候選項集合C’中各不包含項目ix的子集求支持度計數(shù)：

3.9) c’=c’-{ix}

3.10) IF c’∈C’THEN //若c’存在于C’中

3.11) c’.count+ +

3.12) ELSE C’=C’∪{c’}

//將c’加入到C’中

3.14) c’.count=1 //設(shè)置其支持度計數(shù)為1

由算法1，顯然有：

定理1：由算法1所產(chǎn)生的候選項集的集合C’包含且僅包含數(shù)據(jù)庫db中與項目ix相關(guān)的支持度計數(shù)非零的項集。

為方便討論，本文假設(shè)已知原數(shù)據(jù)庫DB的候選項集C和頻繁項集F。若未知，則利用算法1，將輸入的數(shù)據(jù)集改為DB，則將獲得C，進而可以容易地獲得F。

在已知原數(shù)據(jù)庫DB中的C、F，以及新增加部分db的C’后，執(zhí)行算法2將容易地獲取到DB +db的頻繁項集F，進而得到更新后的分類關(guān)聯(lián)規(guī)則。

算法2［6］：

輸入：最小支持度閾值minsup，候選謂詞集C、C’，原數(shù)據(jù)集DB的頻繁謂詞集F。

輸出：DB+db中具有最小支持的閾值minsup的所有頻繁謂詞集的集合F。

算法描述：

1)令C”=C+C’

2)//求db的頻繁項集

令F’=?

2.1)FOR all itemsets f’∈C’do

2.2)IF f’.count≥|db|*minsup THEN

2.3) F’=F’∪{f’}

3)//以下為根據(jù)表1中的方法判斷候選項集在DB+db中是否頻繁

3.1)FOR all itemsets f”∈C”do

3.2)IF f”∈F THEN //若f”在DB中頻繁

3.3) IF f”?F’THEN //若f”在db中不頻繁

3.4) f”.count=f.count+f’.count //計算f”支持度計數(shù)

3.5) IF f”.count≥(|DB|+|db|)* minsup THEN

3.6) F=F∪{f”}

3.7) ELSE F=F-{f”}

3.8) ELSE F=F∪{f”} //f”在DB中頻繁，在db中也頻繁

3.9) f”.count=f.count+f’.count

3.10)ELSE IF f”∈F’THEN //f”在DB不頻繁，但在db中頻繁

3.11) f”.count=f.count+f’.count //計算f”支持度計數(shù)

3.12) IF f”.count≥(|DB|+|db|)* minsup THEN

3.13) F=F∪{f”}

3.14) ELSE F=F-{f”}

3.15) ELSE F=F-{f”} //f”在DB和db中均不頻繁

4) C=C”

2 算法有效性實驗及結(jié)果分析

2.1 應(yīng)用實例

設(shè)給定如表2所示的事務(wù)數(shù)據(jù)庫DB［5］。其中：TID為事務(wù)標(biāo)識符，標(biāo)識每位顧客的一次點餐事務(wù);Itemset為相應(yīng)事務(wù)所包含的項目，即顧客所點的具體菜品標(biāo)識符。

表2 事務(wù)數(shù)據(jù)庫

本文以關(guān)注菜品A為例對算法進行了實驗。并設(shè)原數(shù)據(jù)集DB所包含的數(shù)據(jù)為TID值是1—4的數(shù)據(jù)，TID值是5—8的數(shù)據(jù)為新增數(shù)據(jù)(即，db)。

原有數(shù)據(jù)集DB的候選項集C可以通過執(zhí)行算法1容易地得到，進而快速地獲取到DB的頻繁項集F。因此，本文為方便討論正增量關(guān)聯(lián)規(guī)則更新情況下算法的有效性，假定已知原目標(biāo)數(shù)據(jù)集DB的候選項集C和頻繁項集F，有：

C={(A，3)，(B，3)，(C，3)，(D，1)，(E，2)，(F，1)，(AB，2)，(AC，2)，(AD，1)，(AE，1)，(AF，1)，(BC，3)，(BE，2)，(CE，2)，(DF，1)，(ABC，2)，(ABE，1)，(ACE，1)，(ADF，1)，(BCE，2)，(ABCE，1)}

其中：(x，y)∈C，則x表示DB中的項集，y表示其對應(yīng)的支持度計數(shù)，下同。

設(shè)minsup=50%，則|DB|*minsup=2。此時，DB的頻繁項集F為：

F={(A，3)，(B，3)，(C，3)，(E，2)，(AB，2)，(AC，2)，(BC，3)，(BE，2)，(CE，2)，(ABC，2)，(BCE，2)}

對新增的數(shù)據(jù)集db(表2中TID為5—8的記錄)：

(1)執(zhí)行算法1，產(chǎn)生db中所有支持度計數(shù)非零的候選項集C’，得：

C’={(A，2)，(B，3)，(C，3)，(D，1)，(F，2)，(AB，1)，(AC，2)，(AD，1)，(AF，1)，(CD，1)，(BC，2)，(BF，2)，(CF，2)，(ABC，1)，(ABF，1)，(ACD，1)，(ACF，1)，(BCF，1)，(ABCF，1)}

(2)執(zhí)行算法2

①獲取數(shù)據(jù)集db中的頻繁項集F’。此時，F(xiàn)’中的項目所需滿足的最小支持度閾值為minsup*|db|=50%*4=2，有：

F’={(A，2)，(B，3)，(C，3)，(F，2)，(AC，2)，(BC，2)(BF，2)，(CF，2)，(BCF，2)}

②對C”中的所有子集根據(jù)表1中的判斷方式進行判斷。

例如，在候選項集C”中：

a)項目A在DB和db中均為頻繁項，因此，項目A屬于頻繁項集F。

b)項目E在DB中為頻繁項，但在db中為非頻繁項，需從全局判斷其是否屬于F。此時，各項目需滿足的最小支持度閾值為minsup*|DB+db| =4，而項目E的支持度計數(shù)為2+0=2。因此，項目E不再是頻繁項，需從F中刪除。

c)項目F在db中為頻繁項，但在DB中為非頻繁項，需從全局判斷其是否屬于F。此時，各項目需滿足的最小支持度閾值為minsup*|DB+db| =4，而項目F的支持度計數(shù)為0+2=2。因此，項目F不是數(shù)據(jù)集DB+db的頻繁項。

d)項目D在DB和db中均為非頻繁項，因此，也不是DB+db的頻繁項。

在對C”中的所有子集都進行判斷之后，便可得到DB+db的頻繁項集F：

F={(A，5)，(B，6)，(C，6)，(AC，4)，(BC，5)}

2.2 算法分析及與原算法的比較

新算法只對相對較小的新增部分?jǐn)?shù)據(jù)集db進行了兩次掃描。首次掃描獲取到支持度計數(shù)非零的、包含所關(guān)注的項目(如算法實驗中關(guān)注項目A)的候選項集的集合，第二次掃描在首次掃描的基礎(chǔ)上獲得所有與關(guān)注項目相關(guān)的候選項集的集合，從而使得算法可以在更新關(guān)聯(lián)規(guī)則第二個步驟快速獲取頻繁項集，進而得到計算頻繁項集的所有非空子集是否滿足最小置信度閾值(minconf)并得到更新后的關(guān)聯(lián)規(guī)則。

由于本文改進后的新算法在更新正增量關(guān)聯(lián)規(guī)則時，可以只掃描新增部分的數(shù)據(jù)集db，因此，以下只針對新增部分?jǐn)?shù)據(jù)集db的實驗結(jié)果與文章［5］中的原算法比較。實驗結(jié)果表明，本文根據(jù)點餐推薦系統(tǒng)的實際提出的算法，在對與菜品項目A相關(guān)的關(guān)聯(lián)規(guī)則獲取過程當(dāng)中所產(chǎn)生的候選項集C’，無論是單個k-候選項集(k=1，2，…，4)中項的數(shù)量，還是整個候選項集中項的總數(shù)均小于等于原算法，從而節(jié)約了算法運行所需占用的空間。具體結(jié)果分析見圖1。

圖1 候選項集中項的數(shù)量比較

且由于預(yù)先設(shè)置了所關(guān)注的項目，在獲取頻繁項集后，產(chǎn)生的關(guān)聯(lián)規(guī)則結(jié)果的聚焦度更高，更加便于用戶使用。

3 系統(tǒng)結(jié)構(gòu)設(shè)計

基于面向分類預(yù)測的增量關(guān)聯(lián)規(guī)則挖掘算法，本文提出了基于分類預(yù)測關(guān)聯(lián)規(guī)則的點餐推薦系統(tǒng)的系統(tǒng)結(jié)構(gòu)如圖2所示。使用餐飲企業(yè)信息化系統(tǒng)中搜集的點餐數(shù)據(jù)作為數(shù)據(jù)源，在通過數(shù)據(jù)預(yù)處理使之成為適合進行數(shù)據(jù)挖掘的數(shù)據(jù)之后，便可利用面向分類預(yù)測的增量關(guān)聯(lián)規(guī)則挖掘算法，尋找可能選擇企業(yè)推薦菜品的消費者的點餐關(guān)聯(lián)規(guī)則，并保存在規(guī)則庫中備用。獲取關(guān)聯(lián)規(guī)則的過程比較費時，且關(guān)聯(lián)規(guī)則的獲取不必實時進行，因此可以利用離線周期獲取規(guī)則。［7］在獲取到用戶的點餐意向或部分點餐信息后，根據(jù)關(guān)聯(lián)規(guī)則，即可實時向客戶推薦相關(guān)菜品。

圖2 基于分類預(yù)測關(guān)聯(lián)規(guī)則的點餐推薦系統(tǒng)結(jié)構(gòu)

產(chǎn)生菜品推薦結(jié)果的步驟如下：

(1)根據(jù)餐飲信息化系統(tǒng)中每位客戶的點餐歷史數(shù)據(jù)庫中選取相關(guān)字段，建立點餐事務(wù)記錄集。并通過數(shù)據(jù)預(yù)處理使之成為適合進行關(guān)聯(lián)規(guī)則挖掘的目標(biāo)數(shù)據(jù)集。

(2)使用面向分類預(yù)測的增量關(guān)聯(lián)規(guī)則算法對目標(biāo)數(shù)據(jù)集進行關(guān)聯(lián)規(guī)則挖掘。將結(jié)果存放至關(guān)聯(lián)規(guī)則集合R。

(3)對每位當(dāng)前客戶ui(i∈N)，設(shè)置一個用戶已選(意向)集合Iu、一個候選推薦集合Pu，并將Iu和Pu初始化為空。

(4)對每位當(dāng)前客戶ui，以Iu作為關(guān)聯(lián)規(guī)則的左側(cè)部分搜索關(guān)聯(lián)規(guī)則集合R，得到用戶支持的所有強規(guī)則的集合Ru。

(5)將集合Ru中，除顧客ui已經(jīng)選擇的菜品以外的、所有關(guān)聯(lián)規(guī)則的右側(cè)部分包含的菜品加入推薦候選集Pu中，并依據(jù)所屬關(guān)聯(lián)規(guī)則的置信度取值降序排序。若出現(xiàn)菜品被重復(fù)加入Pu的情況，則僅保留該菜品置信度取值的最大的一項。

(6)服務(wù)員依據(jù)情況，按照系統(tǒng)反饋的結(jié)果，按照置信度由高至低選擇合適數(shù)量的菜品，推薦給顧客ui(i∈N)選擇。

4 結(jié)束語

本文將電子商務(wù)中的推薦系統(tǒng)與關(guān)聯(lián)規(guī)則挖掘相結(jié)合，在對傳統(tǒng)關(guān)聯(lián)規(guī)則挖掘算法研究的基礎(chǔ)上，針對點餐推薦系統(tǒng)的應(yīng)用實際，提出了面向分類預(yù)測的增量關(guān)聯(lián)規(guī)則挖掘算法。該算法在繼承了原“適合于高效更新的關(guān)聯(lián)規(guī)則算法”［5］減少掃描數(shù)據(jù)庫次數(shù)的優(yōu)點的基礎(chǔ)上，可以只掃描新增的少部分?jǐn)?shù)據(jù)集就完成關(guān)聯(lián)規(guī)則的更新，并使挖掘結(jié)果聚焦于用戶關(guān)心的相關(guān)需推薦的菜品，有效減少了算法產(chǎn)生的候選項集的大小、節(jié)約算法運行空間，并通過實驗驗證了算法的有效性。在此基礎(chǔ)上，還對基于分類預(yù)測關(guān)聯(lián)規(guī)則的點餐推薦系統(tǒng)的結(jié)構(gòu)進行了有益的探索和研究。

［1］楊引霞，謝康林，朱揚勇，等.電子商務(wù)網(wǎng)站推薦系統(tǒng)中關(guān)聯(lián)規(guī)則推薦模型的實現(xiàn)［J］.計算機工程，2004，30(19)：57 -59.

［2］Agrawal R et al.Mining association rules between sets of items in large databases［C］//Proceedings of ACM SIGMOD Conference on Management of Data，Washington DC，1993：207-216.

［3］馮玉才，馮建琳.關(guān)聯(lián)規(guī)則的增量式更新算法［J］.軟件學(xué)報，1998，9(4)：301-306.

［4］周海巖.關(guān)聯(lián)規(guī)則的開采與更新［J］.軟件學(xué)報，1999，10(10)：1078-1084.

［5］周海巖.適合于高效更新的關(guān)聯(lián)規(guī)則挖掘算法［J］.小型微型計算機系統(tǒng)，2004，25(4)：634-637.

［6］廖旺宇.面向分類預(yù)測的增量關(guān)聯(lián)規(guī)則應(yīng)用研究［D］.四川師范大學(xué)，2010：21-24.

［7］索琪，盧濤.基于關(guān)聯(lián)規(guī)則的電子商務(wù)推薦系統(tǒng)研究［J］.哈爾濱師范大學(xué)自然科學(xué)學(xué)報，2005，21(2)：50-53.