一種改進的關聯規則挖掘算法在自選餐廳的應用研究

[摘 要] 本文詳細分析傳統關聯規則Apriori算法的不足，提出了一種改進的關聯規則快速挖掘算法。并使用該算法對某自選餐廳消費信息進行數理分析和仿真實驗，挖掘了隱含的有用信息，具有重要的實用價值。

[關鍵詞] 關聯規則 自選餐廳 應用研究

一、引言

隨著經濟的日益發展，大中型自選餐廳在各個城市應運而生。本文根據傳統關聯規則Apriori算法的不足，提出了一種改進的關聯規則快速挖掘算法，并使用該算法對某自選餐廳消費信息進行數理分析和仿真實驗，挖掘了隱含的有用信息，為自選餐廳菜品設置和食品擺放提供決策性的作用，具有重要的實用價值。

二、數據挖掘中的關聯規則技術

數據挖掘是一個多學科交叉研究領域，它融合了數據庫技術等人工智能等新技術的研究成果。關聯規則是當前數據挖掘研究的主要模式之一，側重于確定數據中不同領域之間的聯系，找出滿足給定支持度和可信度閾值的多個域之間的依賴關系。

1.關聯規則的思想

關聯規則的一般性描述是:設I={i1，i2，…，im}是m個不同項目的集合，D是針對I的事物集合，每一事物包含若干個項目i1，i2，…，ik，…屬于I，一個關聯規則是一種蘊涵:X→Y，其中，XI，YI，并且X∩Y＝Φ，X稱作規則的前提，Y是結果。對于關聯規則X→Y成立的條件是：

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

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

最經典的關聯規則挖掘算法是Apriori算法。

2.Apriori算法存在的不足

該算法核心思想把發現關聯規則的工作通過迭代檢索出事務數據庫中的頻繁項集和從頻繁集中構造出滿足用戶最低信任度的規則。很顯然在性能上有兩個瓶頸：

(1)需要多次掃描數據庫，需要很大的I／O負載，對每次循環，后選集中的每個元素都必須通過掃描數據庫一次來驗證其是否加入頻繁集中。

(2)產生龐大的后選集，后選集是以指數形式增長的。如此大的后選集對時間和主存空間都是一個挑戰。

三、一種改進的關聯規則挖掘算法

1.改進算法的思想

該算法首先構造事務規則樹并合并為規則鏈，然后在規則鏈上構造事務規則樹模型，對所提取到的項目序列進行計算，就可求出所有的關聯規則。該算法不需要查找頻繁項，直接找出關聯規則，方法快捷靈活，特別適用于動態的、海量的數據庫關聯規則挖掘。

2.改進算法的描述

首先遍歷數據庫找出有序集L={i1，i2，…，ik}為滿足支持度的頻繁1項集，令M={i1，i2，…，ik}是與L一一對應的結點集合。

(1)開始。

(2)以i1，i2，…，ik為根結點分別構造事務規則樹T1，T2，…，Tk。循環:m以1為步長，從1到k，構造事務規則樹Tm。

①先對i1，i2，…，ik進行排序:將項目im放到有序集M的第1個位置。對其余項目按已有先后位置重新排列下標號，形成新的有序集:M’={i1’，i2’，…，ik’}。

②求解規則鏈第1層項目序列集合L1。令i1’的事務集與M’中的其他項目的事務集進行‘交’運算，將滿足支持度的項集形成序列保存到L1中。其中，每個項目序列里i1’式為第一元素，其他項目為第二元素。

③循環:t以1為步長，從2到k，求解規則鏈第2，3，…k的層項目序列集合L1，L2，…Lk;循環:j以1為步長，從1到t-l，求解L1，對L2，L3，…LK-1進行擴充。

④根據L1，L2，…Lk里的序列，按照路徑規則法求出所有的關聯規則放入規則集P中。

將n條規則鏈求出的項目序列放人集合P中。P=P1∪P2∪…∪Pn。對P中的序列運用路徑規則法和規則過濾求出無冗余的關聯規則。

(3)對所求出的事務規則樹T1，T2，…，Tk的規則進行規則過濾以消除冗余。

(4)結束。

四、在自選餐廳的應用研究

實驗數據來自重慶某自選餐廳2007年的銷售信息庫，記錄總數為88695條。考察啤酒與其他食品銷售的關聯規則挖掘。掃描數據庫信息如下：

消費啤酒:15354人；消費燒烤：9872人；消費火鍋：10681人(清湯：3724人；紅湯：6957人)；消費啤酒和燒烤：5864人；消費啤酒又消費火鍋：8756人(啤酒和清湯:1026人；啤酒和紅湯：7730人)；消費燒烤和火鍋：892人(燒烤和清湯：635人：燒烤和紅湯：257人)。記消費啤酒為事務A，消費燒烤為事務B，消費火鍋為事務C。消費清湯為事務C1，消費紅湯為事務C2。則計算出如下關聯規則：

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。

據此可得如下形式的關聯規則：

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。

據此可得如下形式的關聯規則：

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

同理可得其他形式的關聯規則，部分關聯規則如下表所示。

以上規則說明如下：

(1)有6.61%的消費者消費啤酒時會吃燒烤，消費啤酒的有38.19%的可能會吃燒烤，反之，吃燒烤的有59.4%的可能會消費啤酒。

(2)有9.87%的消費者消費啤酒時會吃火鍋，消費啤酒的有57.20%的可能會吃火鍋，反之，吃火鍋的有80.29%的可能會消費啤酒。

五、結束語

本文在研究和分析傳統關聯規則Apriori算法不足的基礎上提出了一種改進的關聯規則快速挖掘算法，并針對某自選餐廳消費信息進行數據挖掘和知識發現，快速提取出大量隱含的有價值的信息為經營者菜品設置和擺放提供參考，具有一定的實用性和參考性。

參考文獻：

[1]Hand D，Maunila H 張銀奎譯:數據挖掘原理[M].北京:機械工業出版社，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]丁衛平等:基于關聯規則的電子病歷挖掘算法研究與應用. 微電子學與計算機， 2007，24(3)

[4]蘆沽等:挖掘關聯規則中對Apriori算法的一個改進.微電子學與計算機， 2006， 23(2):10～12