一種改進(jìn)的關(guān)聯(lián)規(guī)則挖掘算法在自選餐廳的應(yīng)用研究

[摘 要] 本文詳細(xì)分析傳統(tǒng)關(guān)聯(lián)規(guī)則Apriori算法的不足，提出了一種改進(jìn)的關(guān)聯(lián)規(guī)則快速挖掘算法。并使用該算法對(duì)某自選餐廳消費(fèi)信息進(jìn)行數(shù)理分析和仿真實(shí)驗(yàn)，挖掘了隱含的有用信息，具有重要的實(shí)用價(jià)值。

[關(guān)鍵詞] 關(guān)聯(lián)規(guī)則 自選餐廳 應(yīng)用研究

一、引言

隨著經(jīng)濟(jì)的日益發(fā)展，大中型自選餐廳在各個(gè)城市應(yīng)運(yùn)而生。本文根據(jù)傳統(tǒng)關(guān)聯(lián)規(guī)則Apriori算法的不足，提出了一種改進(jìn)的關(guān)聯(lián)規(guī)則快速挖掘算法，并使用該算法對(duì)某自選餐廳消費(fèi)信息進(jìn)行數(shù)理分析和仿真實(shí)驗(yàn)，挖掘了隱含的有用信息，為自選餐廳菜品設(shè)置和食品擺放提供決策性的作用，具有重要的實(shí)用價(jià)值。

二、數(shù)據(jù)挖掘中的關(guān)聯(lián)規(guī)則技術(shù)

數(shù)據(jù)挖掘是一個(gè)多學(xué)科交叉研究領(lǐng)域，它融合了數(shù)據(jù)庫技術(shù)等人工智能等新技術(shù)的研究成果。關(guān)聯(lián)規(guī)則是當(dāng)前數(shù)據(jù)挖掘研究的主要模式之一，側(cè)重于確定數(shù)據(jù)中不同領(lǐng)域之間的聯(lián)系，找出滿足給定支持度和可信度閾值的多個(gè)域之間的依賴關(guān)系。

1.關(guān)聯(lián)規(guī)則的思想

關(guān)聯(lián)規(guī)則的一般性描述是:設(shè)I={i1，i2，…，im}是m個(gè)不同項(xiàng)目的集合，D是針對(duì)I的事物集合，每一事物包含若干個(gè)項(xiàng)目i1，i2，…，ik，…屬于I，一個(gè)關(guān)聯(lián)規(guī)則是一種蘊(yùn)涵:X→Y，其中，XI，YI，并且X∩Y＝Φ，X稱作規(guī)則的前提，Y是結(jié)果。對(duì)于關(guān)聯(lián)規(guī)則X→Y成立的條件是：

(1)它具有支持度S，即事務(wù)數(shù)據(jù)庫D中至少有S%的事務(wù)同時(shí)包含X和Y。

(2)它具有置信度C，即在事務(wù)數(shù)據(jù)庫D中包含X的事務(wù)至少有C%同時(shí)也包含Y。

最經(jīng)典的關(guān)聯(lián)規(guī)則挖掘算法是Apriori算法。

2.Apriori算法存在的不足

該算法核心思想把發(fā)現(xiàn)關(guān)聯(lián)規(guī)則的工作通過迭代檢索出事務(wù)數(shù)據(jù)庫中的頻繁項(xiàng)集和從頻繁集中構(gòu)造出滿足用戶最低信任度的規(guī)則。很顯然在性能上有兩個(gè)瓶頸：

(1)需要多次掃描數(shù)據(jù)庫，需要很大的I／O負(fù)載，對(duì)每次循環(huán)，后選集中的每個(gè)元素都必須通過掃描數(shù)據(jù)庫一次來驗(yàn)證其是否加入頻繁集中。

(2)產(chǎn)生龐大的后選集，后選集是以指數(shù)形式增長的。如此大的后選集對(duì)時(shí)間和主存空間都是一個(gè)挑戰(zhàn)。

三、一種改進(jìn)的關(guān)聯(lián)規(guī)則挖掘算法

1.改進(jìn)算法的思想

該算法首先構(gòu)造事務(wù)規(guī)則樹并合并為規(guī)則鏈，然后在規(guī)則鏈上構(gòu)造事務(wù)規(guī)則樹模型，對(duì)所提取到的項(xiàng)目序列進(jìn)行計(jì)算，就可求出所有的關(guān)聯(lián)規(guī)則。該算法不需要查找頻繁項(xiàng)，直接找出關(guān)聯(lián)規(guī)則，方法快捷靈活，特別適用于動(dòng)態(tài)的、海量的數(shù)據(jù)庫關(guān)聯(lián)規(guī)則挖掘。

2.改進(jìn)算法的描述

首先遍歷數(shù)據(jù)庫找出有序集L={i1，i2，…，ik}為滿足支持度的頻繁1項(xiàng)集，令M={i1，i2，…，ik}是與L一一對(duì)應(yīng)的結(jié)點(diǎn)集合。

(1)開始。

(2)以i1，i2，…，ik為根結(jié)點(diǎn)分別構(gòu)造事務(wù)規(guī)則樹T1，T2，…，Tk。循環(huán):m以1為步長，從1到k，構(gòu)造事務(wù)規(guī)則樹Tm。

①先對(duì)i1，i2，…，ik進(jìn)行排序:將項(xiàng)目im放到有序集M的第1個(gè)位置。對(duì)其余項(xiàng)目按已有先后位置重新排列下標(biāo)號(hào)，形成新的有序集:M’={i1’，i2’，…，ik’}。

②求解規(guī)則鏈第1層項(xiàng)目序列集合L1。令i1’的事務(wù)集與M’中的其他項(xiàng)目的事務(wù)集進(jìn)行‘交’運(yùn)算，將滿足支持度的項(xiàng)集形成序列保存到L1中。其中，每個(gè)項(xiàng)目序列里i1’式為第一元素，其他項(xiàng)目為第二元素。

③循環(huán):t以1為步長，從2到k，求解規(guī)則鏈第2，3，…k的層項(xiàng)目序列集合L1，L2，…Lk;循環(huán):j以1為步長，從1到t-l，求解L1，對(duì)L2，L3，…LK-1進(jìn)行擴(kuò)充。

④根據(jù)L1，L2，…Lk里的序列，按照路徑規(guī)則法求出所有的關(guān)聯(lián)規(guī)則放入規(guī)則集P中。

將n條規(guī)則鏈求出的項(xiàng)目序列放人集合P中。P=P1∪P2∪…∪Pn。對(duì)P中的序列運(yùn)用路徑規(guī)則法和規(guī)則過濾求出無冗余的關(guān)聯(lián)規(guī)則。

(3)對(duì)所求出的事務(wù)規(guī)則樹T1，T2，…，Tk的規(guī)則進(jìn)行規(guī)則過濾以消除冗余。

(4)結(jié)束。

四、在自選餐廳的應(yīng)用研究

實(shí)驗(yàn)數(shù)據(jù)來自重慶某自選餐廳2007年的銷售信息庫，記錄總數(shù)為88695條。考察啤酒與其他食品銷售的關(guān)聯(lián)規(guī)則挖掘。掃描數(shù)據(jù)庫信息如下：

消費(fèi)啤酒:15354人；消費(fèi)燒烤：9872人；消費(fèi)火鍋：10681人(清湯：3724人；紅湯：6957人)；消費(fèi)啤酒和燒烤：5864人；消費(fèi)啤酒又消費(fèi)火鍋：8756人(啤酒和清湯:1026人；啤酒和紅湯：7730人)；消費(fèi)燒烤和火鍋：892人(燒烤和清湯：635人：燒烤和紅湯：257人)。記消費(fèi)啤酒為事務(wù)A，消費(fèi)燒烤為事務(wù)B，消費(fèi)火鍋為事務(wù)C。消費(fèi)清湯為事務(wù)C1，消費(fèi)紅湯為事務(wù)C2。則計(jì)算出如下關(guān)聯(lián)規(guī)則：

1.support(AB)==P(A∪B)=5864／88695=6.61%=support (BA)；

confidence(AB)=P=(B/A)=5864／15354=38.19%；

correlation(A，B)=P(A∪B)/(P(A)P(B))=18.56>1。

據(jù)此可得如下形式的關(guān)聯(lián)規(guī)則：

AB[support=6.61%，confidence=38.19%]。

2.support(AC)=P(A∪C)=8756／88695=9.87%=support (CA)；

confidence(AC)=P(C/A)=8756／15354=57.02%；

correlation(A，C)=P(A∪C)/(P(A)P(C))=24.55>1。

據(jù)此可得如下形式的關(guān)聯(lián)規(guī)則：

AC[support=9.87%，confidence=57.02%]。

同理可得其他形式的關(guān)聯(lián)規(guī)則，部分關(guān)聯(lián)規(guī)則如下表所示。

以上規(guī)則說明如下：

(1)有6.61%的消費(fèi)者消費(fèi)啤酒時(shí)會(huì)吃燒烤，消費(fèi)啤酒的有38.19%的可能會(huì)吃燒烤，反之，吃燒烤的有59.4%的可能會(huì)消費(fèi)啤酒。

(2)有9.87%的消費(fèi)者消費(fèi)啤酒時(shí)會(huì)吃火鍋，消費(fèi)啤酒的有57.20%的可能會(huì)吃火鍋，反之，吃火鍋的有80.29%的可能會(huì)消費(fèi)啤酒。

五、結(jié)束語

本文在研究和分析傳統(tǒng)關(guān)聯(lián)規(guī)則Apriori算法不足的基礎(chǔ)上提出了一種改進(jìn)的關(guān)聯(lián)規(guī)則快速挖掘算法，并針對(duì)某自選餐廳消費(fèi)信息進(jìn)行數(shù)據(jù)挖掘和知識(shí)發(fā)現(xiàn)，快速提取出大量隱含的有價(jià)值的信息為經(jīng)營者菜品設(shè)置和擺放提供參考，具有一定的實(shí)用性和參考性。

參考文獻(xiàn)：

[1]Hand D，Maunila H 張銀奎譯:數(shù)據(jù)挖掘原理[M].北京:機(jī)械工業(yè)出版社，2003

[2]Min Song， I1-Yeol Song， Xiaohua Hu. Semantic Query Expansion Combining Association Rules with Ontologies and Information Retrieval Techniques[C].DaWaK 2005:326～335

[3]丁衛(wèi)平等:基于關(guān)聯(lián)規(guī)則的電子病歷挖掘算法研究與應(yīng)用. 微電子學(xué)與計(jì)算機(jī)， 2007，24(3)

[4]蘆沽等:挖掘關(guān)聯(lián)規(guī)則中對(duì)Apriori算法的一個(gè)改進(jìn).微電子學(xué)與計(jì)算機(jī)， 2006， 23(2):10～12