一种改进的关联规则挖掘算法在自选餐厅的应用研究

[摘 要] 本文详细分析传统关联规则Apriori算法的不足，提出了一种改进的关联规则快速挖掘算法。并使用该算法对某自选餐厅消费信息进行数理分析和仿真实验，挖掘了隐含的有用信息，具有重要的实用价值。

[关键词] 关联规则 自选餐厅 应用研究

一、引言

随着经济的日益发展，大中型自选餐厅在各个城市应运而生。本文根据传统关联规则Apriori算法的不足，提出了一种改进的关联规则快速挖掘算法，并使用该算法对某自选餐厅消费信息进行数理分析和仿真实验，挖掘了隐含的有用信息，为自选餐厅菜品设置和食品摆放提供决策性的作用，具有重要的实用价值。

二、数据挖掘中的关联规则技术

数据挖掘是一个多学科交叉研究领域，它融合了数据库技术等人工智能等新技术的研究成果。关联规则是当前数据挖掘研究的主要模式之一，侧重于确定数据中不同领域之间的联系，找出满足给定支持度和可信度阈值的多个域之间的依赖关系。

1.关联规则的思想

关联规则的一般性描述是:设I={i1,i2,…,im}是m个不同项目的集合，D是针对I的事物集合，每一事物包含若干个项目i1,i2,…,ik,…属于I，一个关联规则是一种蕴涵:XY，其中，XI,YI,并且X∩Y＝Φ，X称作规则的前提，Y是结果。对于关联规则XY成立的条件是：

(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