多层关联规则

多层关联规则（精选7篇）

多层关联规则 篇1

0 引言

数据仓库以及其上进行的联机分析处理(OLAP)、数据挖掘共同构建了现代决策支持系统的核心框架,已成为数据库领域的热点问题[1]。在当前,大多数的数据仓库的应用都是进行统计、建立多维模型以及OLAP的分析工作。关联规则挖掘以其从大量商务数据库记录中发现有趣的相关联系进而帮助制定商务决策的特征成为数据挖掘研究关注的主题之一。在现今的关联规则挖掘应用领域[2],特别是电子商务的应用中,源于商品项目的多样化,数据项目属性概念集之间存在层次之分的现状,在低层或原始数据层的数据项之间往往很难找出强关联规则和有趣的购买模式,有时会将一些具有高价值性的信息丢失;相反,在多个概念层的项之间找有趣的关联比仅在原始层数据之间更容易,在较高的抽象层发现的强关联规则可能提供常识性知识,因此,数据挖掘系统应当提供一种在多维以及维上多个抽象层挖掘关联规则的能力。同时,激烈的商业竞争要求决策支持系统不仅具有优良的查询及挖掘性能而且要求具备快速的反应能力[3,4]。鉴于商空间粒度理论在实现粗细粒度层次间的灵活转换功能时具有不俗表现能力,以及OLAP提供的在不同数据集、不同细节上进行的切片、切块、展开、过滤等各种操作的规范流程,可以考虑将商空间粒度计算理论、OLAP和关联规则挖掘相结合,一方面,基于OLAP的关联规则挖掘就可以提供在不同数据集、不同的细节上的挖掘,是实现良好挖掘效能的保证。另一方面,采用商空间理论指导下的关联规则挖掘可以实现在不同的抽象层次空间自由转换,大大的提高了数据挖掘的灵活性和快速反应能力。因此为了满足决策支持系统在挖掘效能及响应速度上的应用要求,如何构建运算策略以实现多维多层次规则挖掘及加速OLAP中Cube算子的计算速度是数据挖掘的核心问题,值得探索研究。

1 相关知识及OLAP关联规则挖掘的结构

1.1 商空间理论粒度模型

以三元组(X,f,T)描述一个问题,其中X是论域,f(*)表示论域上(元素)的属性,f:X→Y,Y可以是n维空间,也可以是一般的集合,T是论域的结构,它表示论域中各元素之间的关系。求解问题(X,f,T)就是对论域X及其相关的结构、属性进行分析研究。当较细粒度X很复杂时,人们常用较粗等价关系将X提升划分成比较“粗”的粒度来考察问题,这里所谓粒度,就是将论域中的子集当作新的元素进行研究,即对X进行划分得到商集[X],然后对[X]进行研究[5]。

1.2 关联规则挖掘的结构

因其交易事务数据库表中事务项记录不能显示出商品项集之间的层次关系,若用OLAP中聚集操作每个Cuboid表示任意项目商品项集,则用Cuboid构建的Cube代数格可表示体现其层次感的项目商品项集。一个Cube里所有Cuboid就存在着依赖关系。其依赖关系数学定义如下:

定义1.1(Cube代数格)设L(28){c 1,c2,…,cm}是对数据集合P(D1,D2,…,Dn,M)实施Cube操作的Cuboid集合。对于∀ci、cj∈L,如果下面两个条件成立,我们说ci和cj满足直接计算关系(即cj可以由ci直接计算出来,表示为ci→cj):

(i)ci⊇cj

(ii)|ci|=cj+1其中,|c|表示节点Cuboid维属性的个数.

如果ci→cj,我们称ci是cj的直接前辈或cj是ci的直接后裔.称为对数据集合P进行的Cube代数格.可以用有向图G=(V,E)表示,其中V=L,E={(ci,cj)|ci、cj∈L,ci→cj}.G称为Cube操作的概念分层(Concept Hierarchies)。

例如事务数据库中某事务T1,其购买的商品项集为:

那么.其中ALL表示空商品项目集合。各商品属性项逐层向上泛化后得出如图1所示的Cube概念分层。

定义1.2维内关联规则、多维关联规则

(i)维内关联规则:所有的项目都在同一维内,因此也称为单维关联规则。

如buys(X,“digital camera”)=>buys(X,“HP printer”);

(ii)多维关联规则:涉及两个或多个维的关联规则称为多维关联规则,多维关联规则中因其是否存在重复谓词又可分为维间关联规则和混合维关联规则。

维间关联规则如:age(X,“20…35”)occupation(X,“student”)=>buys(X,“laptop”)

混合维关联规则如:age(X,“20…35”)buys(X,“HPprinter”)=>buys(X,“laptop”)

对于关联规则的挖掘由单层扩展为多层时,必须考虑的一个问题是最小支持度的选择,通常有两种支持度策略可以采用,即所有层使用统一最小支持度或递减的最小支持度。因其两种策略的弊端比较显然。本文提出基于分组的支持度。

定义1.3基于分组的支持度。

由于用户或专家通常清楚哪些分组比其他分组更重要,在挖掘多层规则时,有时更希望建立用户指定的基于项或分组的最小支持度阀值。例如,用户可以根据产品价格或根据感兴趣的商品设置最小支持度阀值。

从上面讨论得知,OLAP关联规则挖掘的结构由三部分组成,数据仓库,OLAP引擎和关联规则挖掘引擎。确定了关联规则挖掘的结构后,则OLAP多维多层次关联规则挖掘方法是以Cube概念分层的数据结构为基础,把OLAP技术,FP改进频繁项集挖掘算法和关联规则挖掘合成起来的方法,下面重点讨论用户给定关注商品项集序列后,其对应基于商空间理论Cube概念分层的构建。以带维层次结构三个属性数据集合为例介绍基于商空间粒度理论的Cube分层结构简称商立方体概念分层QCCH(Quotient Cube Concept Hierarchies)结构,其构建方法参照文献[6]HQCL结构的构建。

2 基于商空间理论的OLAP多维多层次关联规则挖掘算法

将前面讨论的OLAP多维多层次关联规则挖掘方法明确后其步骤如下:

(i)预处理,对用户关心的商品序列项目集进行基于商空间理论的Cube概念分层的构建;

(ii)在已构建的概念分层上,执行QCHFP-growth算法,以等价关系R为层次游标因子,分别找出各个层次的频繁项集;

(iii)以各层次频繁项集为基础进行多维及多层关联规则的挖掘

2.1 预处理

1)按照用户所感兴趣指定的商品序列项集指导从销售事务数据库表中过滤出相关的信息,得出经过清洗后的事务数据库D;

2)对D序列项集自底向上构建基于商空间理论Cube概念层次树。按照自底向上顺序逐层扫描概念层次树,将各层的序列分项集分别用矩阵序列Q={Q1,Q2,……}存储。

2.2 执行Algorithm of Quotient Concept Hierarchies Based on FP-growth(QCHFP-growth)算法

QCHFP-growth算法思想:自顶向下,逐层寻找每层的频繁项集,QCHFP-growth首先根据用户关注的实际商品序列项集,查询各商品维及维上层次集合,依据中各成员粒度由细到粗构建QCCH结构;然后结合节点缓存集从QCCH结构的最粗粒度节点(即各商品成员均由最粗等价关系Rn所对应的粒度数据)开始,结合各层指定的最小支持度阀值,按照层次先深度、后广度的原则沿粒度由粗到细逐层执行FP-growth算法,直到每层产生出用户所要求的满足指定支持度的频繁项集为止;最后依据E{}(E{}为计算路径集)中提供的路径由商空间理论预算出所需的I-SET(I为商品序列目标节点项集),最终输出R级对应层次的商品序列的频繁项集iR,记IR={iR}。

QCHFP-growth算法:

输入:itemsetn,R,min_supR,。itemsetn为最高层(L=n)上对应的最粗节点,L为QCCH总的层数;R为概念分层中用户关注的商品序列项集层次对应的等价关系。min_supR为与R对应用户指定的最小支持度阀值。

输出:I-SET,IR。I-SET为商品序列目标节点项集,IR为与R对应商品序列层次的频繁项集。

算法步骤如下:

1)取L层上itemseti=itemsetn,按从左向右方向依次选择itemseti上的项(如果同一节点内某个项已经选择过,则不再选择)设为Di;

2)对itemseti的项Di由Ri对应的属性粒度成员下钻到Ri-1对应的粒度,设其生成的项记为Dj,若Dj在S_result{}中,则转至1),否则转至3);

3)添加Dj到S_result{},边(Di,Dj)到E{},变量Intitemseti减1;

4)对项Dj重复1)-3),直到itemseti中项Di粒度层次达到R为止;

5)对itemseti中剩余项,重复2)-4)直到Intitemset=0,此时itemseti中所有项Di粒度层次均达到R。

6)由E{}协助结合S_result{}得出R对应层所有项集I-SET,依据min_supR对I-SET执行FP-Growth算法[7](此时FP-growth算法中输入元素为QR,min_supR),获得对应于R粒度层的频繁项集IR。

其中:Intitemseti为用户关注节点itemseti从itemsetn开始到R对应层的层次个数;Intitemset为用户关注节点itemseti涉及到的商品项个数。

2.3 多维及多层次关联规则的挖掘

在3.2节找出所有各层的频繁项集后,接下来自然是由频繁项集产生各种类型的强关联规则,由于篇幅的原因,这里只分析维间关联规则,维间关联规则就是存在于两个或两个以上维之间的相关规则。

基本思想:自底向上,从R层的频繁项集开始,因为项目存在于不同的维中,这里通过利用商立方体的概念分层结构来获取每个项目集的关联规则。关联规则步骤如下:

1)对于每个频繁项集IR,产生IR的所有非空子集。

2)对于IR的每个非空子集s,如果,则输出强规则“s⇒(IR-s)”,其中min_confR为与R对应用户指定的最小置信度阀值。

3 实验分析

本文验证了算法QCHFP-growth的有效性,并和FP-growth算法进行了比较。实验在一台CPU为Intel(R)Core(TM)i3 M350 2.27GHz,内存1.92 GB,操作系统为Windows XP的PC机上进行,算法采用Microsoft Visual C++6.0编写。实验数据为人工合成的数据集T10I4D100K。T10I4D100K可由IBM提供的标准数据生成器获得。表1列举了本数据集的一些参数,AvgTlen表示的是平均事务长度,MaxTlen表示的是最大事务长度,T10I4D100K表示的是数据集中事务(T)的平均长度为10,频繁项集(I)的平均长度为4,数据库(D)中事务的总数目为100K。

QCHFP-growth算法只需要扫描数据库一次,之后将排列好的对应于R级的商品属性泛化项集存储到矩阵QR中,在构造DFP-Tree过程中,矩阵也只需要被扫描一次,在挖掘过程中,不产生候选项集,大大的减少了内存的需要,使算法的性能有了明显的提高。图2表示的是QCHFP-growth和FP-growth算法在T10I4D100K各层次数据集中随着不同支持度而显示的运行时间。从图中可以看出,相同支持度下,QCHFP-growth算法的运行时间要明显少于FP-growth算法的运行时间。说明了QCHFP-growth算法挖掘多维多层次频繁项集较FP-growth算法有较高的挖掘效率。

4 总结

针对电子商务关联规则挖掘领域的数据稀疏性,本文提出基于商空间理论的OLAP多维多层次的关联规则挖掘QCH-FP-growth算法,在继承FP-growth算法思想的基础上,利用商空间理论层次间灵活转换的特征对用户指定的商品序列项目集进行Cube概念分层的构建,同时利用OLAP的不同数据集、不同的细节上的规范技术在Cube概念分层结构上以R为游标因子进行灵活的多维多层次关联规则挖掘。实验结果表明,该算法较FP-growth算法在多维多层次规则挖掘效率方面有显著提高。

参考文献

[1]H.F.Li,S.Y.Lee.Mining frequent itemsets over data streams using efficient window sliding techniques[J].Expert Systems with Applications,2009,36(2):1466-1477.

[2]杨泽民,王文军,郭显娥.基于协同微粒群的股票数据关联规则挖掘[J].吉林师范大学学报(自然科学版),2012,33(3):31-34.YANG Z M,WANG W J,GUO X E.Stock Data Mining of Association Rules Based on Synergy of Particle Swarm[J].Jilin Normal University Journal(Natural Science Edition)2012,33(3):31-34.(in Chinese)

[3]Wuzhou Dong,Juan Yi,Haitao He,Jiadong Ren,“An incremental algorithm for frequent pattern mining based on bit-sequence”,IJACT:International Journal of Advancements in Computing Technology,Vol.3,No.9,pp.25-32,2011.

[4]J.Han,J.Pei,“Mining frequent patterns without candidate generation”,In Proceedings of the SIGMOD International Conference on Management of Data,pp.1-12,2000.

[5]张钹,张铃著.问题求解理论及应用[M].北京:清华大学出版社,1990.12.ZHANG B,ZHANG L.Problem Solving Theory and Application[M].Beijing:Tsinghua University Press,1990.12

[6]郭显娥,王文军.基于商空间理论层次Cube操作的聚集算法研究[J].宁夏大学学报(自然科学版),2009,30(2),128～131.GUO X E,WANG W J.Research of Aggregate Algorithm of Hierarchical Cube Operation Base on Theory of Quotient Space[J].Journal of Ningxia University(Natural Science Edi-tion),2009,30(2),128～131.

[7]Jiawei Han,Micheline Kamber.Data Mining Concepts and Techniques[M].Beijing:Higer Education press,2001.

多层关联规则 篇2

随着网络贸易的飞速发展,越来越多的企业迫切需要高效、精确与安全地收集分析数据,挖掘出潜在的商机,在激烈的现代竞争中出奇制胜。面对大量零散分布、无法集中处理的数据信息和企业对信息集中整合利用的迫切需求,商务智能由此应运而生。如何加强农产品的智能经营管理,让农产品销售企业最大程度地发掘和牢牢地把握住能给企业带来最大价值的客户群和商机,成为农产品电子商务发展必须要解决的问题。

1 多层关联规则及其存在的问题

1.1 多层关联规则

关联规则作为研究商务智能的重要数据挖掘技术之一,是从大量数据中提取人们未知却又潜在有用的规则,通过这些规则对用户购买模式进行分类,安排商品货架等。多层关联规则是在单层关联规则的基础上扩展的。 在应用的过程中,人们发现底层数据间挖掘的规则往往意义不大,而真正有价值的规则通常需要从不同概念层间寻找。同时,将商品项目进行概念分层再完成多概念层关联规则挖掘,可以有效避免一些高价值信息的丢失。因此,挖掘多层的关联规则就具有重要的意义。本文针对分布式数据库中的多概念层数据进行隐私保护的关联分析,通过多层次关联规则挖掘提高决策的准确性,并保证了研究中的信息安全性。

1.2 多层关联规则挖掘存在的问题

当前的多层关联规则挖掘仍存在一些问题:底层的数据由于频率远远低于其祖先,导致其支持度不能满足最小支持度的要求,因而很难找出强关联规则;真正有意义的规则往往存在于相对较高的概念层中,但可能会挖掘到较多的冗余规则。

在应用中,由于多维数据空间数据的稀疏性,导致底层的数据项之间很难找出强关联规则。如这个明显的层次关系:水果—果类—苹果,在数据库中通常是按“苹果”这一具体物品来记录的。传统关联规则挖掘算法只能得到诸如“苹果—西瓜”这类的结果,无法得到诸如“果类—瓜类”之类位于更高概念层次上的关联规则,因此需要在较高的层次发现强关联规则来获取有意义的知识。最小支持度和最小置信度是挖掘关联规则过程中的重要因素,而最小置信度是通过最小支持度得到的,因此最小支持度就成了影响关联规则挖掘的一个关键因素。传统关联规则方法通常在整个过程中只设定一个最小支持度。如下面两条规则:

buys(X,“鲜果”)⇒buys(X,“板栗”) (式1)

[sup=8%,confidence=70%]

buys(X,“苹果”)⇒buys(X,“板栗”) (式2)

[sup=2%,confidence=72%]

如果将最小支持度设置为8%,则无法发现处于底层的规则(式2);而将最小支持度设置为2%,由于最小支持度过低,会导致频繁项集间产生关联,可能会产生很多无意义的规则,导致组合爆炸。根据不同项的最小支持度挖掘多层关联规则的频繁项集,再比较最小置信度产生关联规则,这种方法可以发现一些稀少数据项中潜在的规则,而且不会因为高频产生大量无用和冗余规则。

2 基于粒度的多层次关联规则挖掘

2.1 基于粒度的多层关联规则挖掘步骤

与传统关联规则挖掘方法一样,基于多最小支持度的多层关联规则挖掘也是通过两步完成:首先,要找到所有的频繁项集;然后,再通过所有的频繁项集产生关联规则。在这两步中第2步较容易,并且关联规则挖掘的第1步是决定总体性能的关键。因此,这里主要讨论一下怎样找出频繁项集。挖掘多层关联规则的步骤:

1) 依据粒度划分层次并编码;

2) 计算基于粒度的支持度并产生频繁项集;

3) 根据计算的基于粒度的多最小支持度产生规则。

2.2 基于粒度的层次化编码

粒计算[1,2,3]是一种能够表示存储在系统中的数据语义信息的知识处理方法。把大量复杂信息按其各自的特征和性能划分成若干较简单的块,其中划分出来的每个块被看成一个信息粒。这种处理信息的过程被称为信息粒化。利用粒计算进行关联规则的挖掘,使得人们更方便地从不同粒度上观察问题、分析问题和求解问题。

根据树状结构中节点与节点之间的关系,可以构成层次化分类结构。如果树状结构中的子节点之间是有顺序关系的,就称为有序树。通过使用不同的代号标记有序树上的每个节点来表示它所在位置的信息,这样的有序树称为定址树。

2.3 基于粒度的支持度与置信度计算

在解决和处理大量复杂信息问题时,将信息按其各自的特征和性能划分成若干较简单的块,每个划分出来的块都可以看成是一个信息粒。有关粒的定义如下[1,2,3]:

定义3.15 若给定一个信息系统S=(U,A=C∪D),其中U是整个对象的集合,A是由条件属性集合C和决策属性集合D组成的属性集合,设B∈C,若B的值域VB={b1,b2,b3,…,bK},值域的个数|VB|=k,且|U/IND{B}|=k,则B可按商集U/IND{B}分解为k个二进制信息子粒。对于决策属性D,则可按商集U/IND{D}分解成为|U/IND{D}|个二进制信息子粒。

例如:表1中项在TID中各个对象相应的取值分别为{板栗,苹果,山葡萄,西瓜,梨,核桃}可分解为6个二进制信息粒如下:

a1={100100},a2={100100},a3={010010},a4={011100},a5={001000},a6={000001}

定义3.16 二进制信息粒P中1的个数称为二进制信息粒的粒度,记为|P|。

例如:二进制信息a1={100100},a6={000001}的粒度分别为2和1。

定义3.17 信息系统S=(U,A =C∪D),{C1,C2,…,Ck}∈C,ci为Ci的某个二进制信息子粒,则ci∧cj∧…∧ck(其中∧代表二进制数的布尔“与”运算)称为粒的关联运算。

例如:两个二进制信息粒:a1={101000011001},b2={100101001101},进行关联运算如下所示:101000011001∧100101001101=100000001001。

基于以上定义,给出了基于二进制信息粒的支持度和置信度的定义。

定义3.18 对于任意项目集X⊂I,Y⊂I,X∩Y=ϕ,X的支持度sup(X)=|[X]| / |U|,其中|U|代表对象集合的个数;[X]= [x1] ∧[x2] ∧…∧[xn],xi是X中的项目;Y同理。

规则X⇒Y的支持度为

sup(X∪Y) =|[X]∩[Y]|/|U|

规则X⇒Y的置信度为

confidence(X⇒Y)= (sup(X∪Y)/ |U|)/ (sup(X) /|U|)= sup(X∪Y) / sup(X)

例如:a1,b2两个二进制信息粒之间的支持度sup(a1∪b2) =|100000000001|/|U|= 2/12=1/6,a1的置信度是confidence(a1⇒b2)= sup(a1∪b2) / sup(a1)=2/5。

2.4 基于粒度的多最小支持度计算

根据上节中的多最小支持度计算方法,设计基于粒度的多最小支持度计算方法,即

定义3.9 设I={a1,a2,…,an},sup(ai)≤sup(ai+1),1≤i≤n-1,则

如果A,B满足和undefined,conf(A⇒B) ≥minconf,则广义关联规则A⇒B是强关联规则。

判断出项集间的相关性后,根据正负关联规则的支持度、置信度及多最小支持度的计算公式挖掘项集间的各种规则。

2.5 算法设计

设项目集c的形式为,它是由项目c[1],c[2],…,c[k]组成,同时各项目的MIS值按升序排列,即MIS(c[1]) ≤MIS(c[2]) ≤…≤MIS(c[k])。

输入:挖掘数据库T,最小项支持度集MS。

输出:频繁项目集L

处理流程:

(1) M=sort(I,MS);//根据MIS(i)的值进行升序排列

(2) F=init-pass(M,T);//进行初次数据库扫描

(3) L1={︳f∈F,f.eount≥MIS(f)};

(4) for(k=2;Lk-1≠Φ;k++)do

(5)if k=2 then C2=level2–candidate -gen(F)

(6) else Ck=candidate-gen(Lk-1)

(7) end

(8) for each transaetion t∈T do

(9) Ct=subset(Ck,t);

(10) for each candidate c∈Ct do c.count++;

(11) end

(12) Lk={c∈Ck︳c.count≥MIS(c[1])};

(13) end

(14) Answer=UkLk;

Level2-eandidate-gen(F1)//产生长度为2的候选集

(15)for each item f in F in the same order do

(16) if f.count≥MIS(f) then

(17) for each item h in F that is after f do

(18) if h.count≥MIS(f) then

(19) insert into C2

(20) end

(21) end

Candidate-gen-prune(Lk-1)//长度大于2的候选集产生过程的剪枝过程

(22) for each itemset c∈Ck do

(23) for each(k-l)-subset s of c do

(24) if ((c[1]∈s) or (MIS(c[2]=MIS(c[l]))) then

(25) if(s∉ Lk-1) then delete c from Ck;

(26) end

(27) end

3多层次关联规则挖掘技术在农产品电子商务中的应用

将表1中的用户购买信息用层次化结构编码的形式表示,对层次化编码后的各个项在TID中各个对象对应的取值进行信息粒化表示,并计算出层次化结构编码后的每一项对应的支持度,如表2所示。利用基于粒计算的多最小支持度定义和表2中已求出的各项的支持度计算出各个项及层项的最小支持度,如表3所示。

多层次关联规则的整个流程是从搜寻高层的频繁项集开始。各项按定义2设定的最小支持度,对交易数据表2进行搜索,找出同层及层间满足最小支持度的频繁项集,同时记录到表4。例如,通过计算得[1**]和[2**]的多最小支持度为1/3,sup([1**]∪[2**])= |(111100∧100101)|/ |6|=|100100|/6=2/6,满足多最小支持度1/3,于是将[1**]和[2**]结合得到频繁一项集;滤掉不满足多最小支持度的候选项集。如此反复进行项集间频繁项集求取,最后将所有的频繁2-项集列于表4中。由于层次不再增加,整个搜索过程结束。

接着从表4中获得的所有频繁2-项集中查找所有的满足定义2的多最小支持度的频繁3-项集,滤掉不符合多项最小支持度的候选项集。反复进行频繁3-项集的求取,直至整个搜索过程结束,其结果如表5所示。

下面是多层次挖掘过程中频繁项集产生的过程。

由各项目的多最小支持度和表中各项组合后的支持度进行比较,可以得到表5中最终各项构成的集合。从结果中可以得到同层间的关联规则,如[11*]and[12*]and[22*],且它们都满足多最小支持度MIS([11*]and[12*]and[22*])=min[MIS([11*]), MIS([12*]),MIS([22*])]=1/6;还可以得到层间的关联规则,如[12*]and[111]and[2**],他们也满足多最小支持度MIS([12*]and[111]and[2**])=min[MIS([12*]), MIS([111]), MIS([2**])]=1/6,从而实现了多层次间的关联规则挖掘。

不同数据项产生的不同规则的支持度,需要满足不同的多最小支持度才能被发现,如[12*]and[2**]的支持度sup([12*]and[2**]) =(011100∧100101)/6=1/6,而多最小支持度MIS([12*]and[2**])=min[MIS([MIS([12*]), MIS([2**])]=1/4〉MIS([12*]and[2**])。因此,可以将该规则删除,减少了高频频繁项集的向下生成搜索空间。

4 结束语

本文通过引入粒计算,实现了多层交叉的关联规则挖掘。通过实例证明,此方法可以有效地挖掘稀有项和去除冗余规则,产生有意义的负关联规则和交叉层的规则,且计算简单,有利于硬件实现,有利于对数据进行深层分析和处理,为企业决策者提供相关的决策依据,从而提高决策效率和水平。

摘要：针对多层关联规则挖掘问题,引入粒计算,给出了基于粒度的多层关联规则挖掘算法,使得人们可以方便地从不同粒度上观察问题、分析问题和求解问题。通过实例验证证明,该方法可以有效地挖掘稀有项和去除冗余规则,产生有意义的负关联规则和交叉层规则。将这些技术具体应用到农产品电子商务中,旨在为多层关联规则挖掘技术在该领域的广泛应用提供借鉴。

关键词：农产品电子商务,关联规则,粒计算,粒度

参考文献

[1]Lin Q.Granular language and its deductive reasoning[J].Communications of ACM,2002,5(2):63-66.

[2]徐健锋,刘斓,邱桃荣,等.基于二进制信息粒的数据挖掘算法研究[J].计算机科学,2008,35(3):202-205.

关联规则挖掘研究 篇3

关联规则是发现交易数据库中不同商品(项)之间的联系,这些规则找出顾客购买行为模式,如购买了某一商品对购买其它商品的影响。发现这样的规则可以应用于商品货架设计、货存安排以及根据购买模式对用户进行分类。

关联规则是关联分析中的一种常用技术。关联规则是寻找在同一个事件中出现的不同项的相关性。其形式如下[1]。

设L=邀i1,i2,...im妖是所有项的集合。D是交易集合,其中每个交易T是一个项的集合并且T哿L。每一个交易T都有一个唯一的标识TID。如果项集合X哿L且X哿T,则交易T包含X。一个关联规则就是这样一种形式的关系:X==>Y,其中X奂L,Y奂L,并且X∪Y=φ。

另外两个和关联规则有关的概念是支持度和可信度。

根据文献[1]的定义,对于一个关联规则X==>Y,在交易集合D中,Txy=邀T|(X∪Y)哿T∩T∈D妖,Tx=邀T|X奂T∩T∈D妖,支持度为s,|Txy|/|D|=s%;可信度为c,|Txy|/|Tx|=c%。

举例说明,有一个特定的关联规则,锤子==>钉子,这个规则可能意味着买锤子的人也有倾向买钉子。有10000条交易记录的交易数据库中,若有300条记录既包含了锤子又包含了钉子,则关联规则的支持度为300/10000=3%,这个支持度是比较高的,但并不能就此作出这个关联有意义的结论。但是假如只有600人购买了锤子,则其中有一半的人又去购买了钉子,这个现象就值得关注了。

另一个更详细的例子来自于文献[2]:

总交易笔数:1000;

包含“锤子”:50;

包含“钉子”:80;

包含“钳子”:20;

包含“锤子”和“钉子”:15;

包含“钳子”和“钉子”:10;

包含“锤子”和“钳子”:10;

包含“锤子”,“钳子”和“钉子”:15。

则可以计算出:

“锤子和钉子”的支持度=1.5%(15/1000);

“锤子,钉子和钳子”的支持度=0.5(5/1000);

“锤子==>钉子”的可信度=30%(15/50);

“钉子==>锤子”的可信度=19%(15/80);

“锤子和钉子==>钳子”的可信度=33%(5/15);

“钳子==>锤子和钉子”的可信度=25%(5/20)。

数据挖掘得到的关联规则,只是对数据库中数据之间相关性的一种描述。还没有其它数据来验证规则的正确性。

除了支持度和可信度外关联规则评价标准还有改善度和兴趣度。

2 关联规则的种类

(1)基于规则中处理的变量的类别,分为布尔型和数值型。布尔型关联规则处理的值都是离散的、种类化的,显示了这些变量之间的关系;而数值型关联规则可以和多维关联或多层关联规则结合起来,对数值型字段进行处理,将其进行动态的分割,或者直接对原始的数据进行处理,当然数值型关联规则中也可以包含种类变量。例如:性别=“女”=>职业=“秘书”,是布尔型关联规则;性别=“女”=>avg(收入)=2300,是一个数值型关联规则。

(2)基于规则中数据的抽象层次,分为单层关联规则和多层关联规则。在单层的关联规则中,所有的变量都没有考虑到现实的数据是具有多个不同层次的;而在多层的关联规则中,对数据的多层性已经进行了充分的考虑。例如:IBM台式机=>Sony打印机,是一个细节数据上的单层关联规则;台式机=>Sony打印机,是一个较高层次和细节层次之间的多层关联规则。

(3)基于规则中涉及到的数据维数,分为单维的和多维的。在单维的关联规则中,只涉及到数据的一个维,如用户购买的物品;而在多维的关联规则中,要处理的数据将会涉及多个维。换句话说,单维关联规则是处理单个属性中的一些关系;多维关联规则是处理各个属性之间的某些关系。例如:啤酒=>尿布,这条规则只涉及到用户购买的物品;性别=“女”=>职业=“秘书”,这条规则就涉及到两个字段的信息,是两个维上的一条关联规则。

给出了关联规则的分类之后,在分析过程中,就可以考虑某个具体的方法适用于哪一类规则的挖掘,某类规则又可以用哪些不同的方法进行处理。

3 关联规则挖掘的算法

3.1 经典频集方法

Agrawal等于1993年首先提出了挖掘顾客交易数据库中项集间的关联规则问题[3],其核心方法是基于频集理论的递推方法。以后诸多的研究人员对关联规则的挖掘问题进行了大量的研究。其工作包括对原有的算法进行优化,如引入随机采样、并行的思想等,以提高算法挖掘规则的效率;提出各种变体,如泛化的关联规则、周期关联规则等,对关联规则的应用进行推广。

(1)核心算法Agrawal等设计了一个基本算法[3],提出了挖掘关联规则的一个重要方法,将关联规则挖掘算法的设计分解为两个子问题:(1)找到所有支持度大于最小支持度的项集,这些项集称为频集;(2)使用(1)找到的频集产生期望的规则。

(2)频集算法的几种优化方法:(1)基于划分的方法;(2)基于hash的方法;(3)基于采样的方法;(4)减少交易的个数。

3.2 其它的频集挖掘方法

前面介绍的都是基于Apriori的频集方法。即使进行了优化,Apriori方法一些固有的缺陷还是无法克服。

(1)可能产生大量的候选集。当长度为1的频集有1-0000个的时候,长度为2的候选集个数将会超过10M。当要生成一个很长的规则的时候,要产生的中间元素也是巨大量的。

(2)无法对稀有信息进行分析。由于频集使用了参数minsup,因此就无法对小于minsup的事件进行分析;如果将minsup设成一个很低的值,那么算法的效率将很难处理。

4 结束语

关联规则可以在下面一些方向上进行深入研究:在处理极大量的数据时,如何提高算法效率的问题;对于挖掘迅速更新数据的挖掘算法的进一步研究;在挖掘的过程中,提供一种与用户进行交互的方法,将用户的领域知识结合在其中;对于数值型字段在关联规则中的处理问题;生成结果的可视化方面等等。

参考文献

[1]Rakesh Agrawal,Ramakrjshnan Srjkant.Fast Algorithms for Mining Association Rules.[S.l].:Proceedings of the20th VLDB Conference,c19xx/20xx.

[2]朱扬勇.数据挖掘入门.http://datamining.126.com.

关联规则算法综述 篇4

关键词：数据挖掘,关联规则,Apriori算法

0 引言

关联规则是数据挖掘的典型方法, 它是描述在一个交易中物品之间同时出现的规律的知识模式。关联规则的分析方法用于隐藏在大型数据集中令人感兴趣的联系。所发现的联系可以用关联规则或频繁项集的形式表示。关联规则可以揭示事物之间的联系, 也用于购物篮分析, 金融服务和科学数据分析等。

1 关联规则概念

关联规则是Agrawal等人提出的数据挖掘领域中的一个重要课题。关联规则是在交易数据、关系数据或其他信息载体中, 查找存在于项目集合或对象集合之间的频繁模式、关联、相关性或因果结构, 通过分析数据或记录间的关系, 决定哪些事情将一起发生。关联规则的蕴涵表达式形如X→Y, 其中X和Y是不相关的项集, 即X∩Y=Ф。关联规则强度可用它的支持度和置信度度量。支持度确定规则可以用于给定数据集的频繁程度, 而置信度确定Y在包含X的事物中出现的频繁程度。支持度和置信度的形式定义如下:

2 关联规则挖掘的过程

在事务数据库中找出具有用户给定的最小支持度和最小确信度的关联规则, 分解成两个子任务为:①找出事务数据库中所有大于等于用户指定最小支持度的项目集, 即频繁项目集;②利用频繁项目集生成所需要的关联规则。目前有很多产生频繁项目集的算法, 这些算法产生频繁项目集时, 扫描数据库的每个事务, 确定最小支持度, 在第k次迭代出所有频繁项目集, 然而, 由于数据库的规则通常是非常大的, 所以在每次迭代时产生候选项目集以统计其支持度是非常耗时的, 因此, 寻找频繁项目集的有效产生算法是问题的关键。

3 关联规则挖掘算法描述

1993年R.Agrawal等人提出了关联规则的挖掘问题以后, 得到了更广范围的发展, 其挖掘算法包括Agraw等人提出的AIS、Apriori、Apriori Tid算法, Park等人提出DHP、Savasere等人的Partition以及Toivonen提出的抽样算法Sampling等。

3.1 Apriori算法思想

为了生成所有频集, 使用了递推的方法。其算法思想如下:

输入:

Apriori算法是一种布尔型关联规则频繁项集的算法。Apriori算法的实现过程分为两步:一为连接, 二为剪枝。该算法基于一个频繁项集中任一子集也应该是频繁项集的性质, 使用一种逐层搜索的迭代方法, k-项集用于 (k+1) -项集。其算法流程如下:首先遍历目标数据库一次, 记录每个项目或属性的出现次数, 即计算每个项目的支持度, 收集所有支持度不低于用户最小支持度的项目构成频繁1-项集L1, 然后链接L1中所有的元素形成候选2项集C2, 再次遍历事务数据库, 计算C2中每个候选2-项集的支持度, 收集所有支持度不低于用户最小支持度的项目构成频繁2-项集L2, 再链接L2形成C3, 遍历数据库得L3, 反复执行以上过程, 直到没有候选项集为止。

在整个过程中, 多次循环, 产生大量的候选集, 验证环节需要反复扫描可能很大的交易数据库。由上可知, Apriori算法存在产生大量的候选集和需要重复扫描数据库两大缺点。

3.2 Apriori算法的优化方法

因为Apriori算法在实际的应用中, 存在不太令人满意的地方, 所以人们提出了一些优化的方法。

(1) 基于划分的方法。

算法先把数据库从逻辑上分成几个互不相交的块, 每次单独考虑一个分块并对它生成所有的频集, 然后合并产生的频集生成所有可能的频集, 最后计算这些项集的支持度。这里分块的大小选择要使每个分块可放入主存, 每个阶段只需被扫描一次。而算法的正确性是由每一个可能的频集至少在某一个分块中是频集保证的。

(2) 基于采样的方法。

基于前一遍扫描得到的信息进行组合分析, 得到一个改进的算法, 即在计算k-项集时, 如果认为某个 (k+1) -项集可能是频集时, 就并行地计算这个 (k+1) -项集的支持度, 该算法需要的总的扫描次数通常少于最大的频集的项数。

(3) 动态项集计数。

该技术动态地评估已被计数的所有项集, 不像Apriori算法仅在每次完整的数据库扫描之前确定新的候选, 它可以在任何点添加, 一旦一个项集的所有子集被确定为是频繁的, 就可以启动对该项集支持度的计算。因此, 该算法所需的数据库扫描次数要比Apriori算法少。

此外, 还有事务压缩、基于杂凑等优化方法。

4 关联规则的应用

4.1 购物篮分析

销售商为了取得更多的经济效益, 需要对市场形式进行分析, 了解顾客的购买习惯和偏爱。在买一件物品的同时购买相关物品的概率增加会使商品的销量增加, 获得更高的利润。关联规则采掘可以提供这些信息。在销售行业, 关联规则采掘的最有效的应用就是对销售的物品进行数据分析, 从而得知顾客的购买特性, 进行更有效的销售行动。例如, 人们在购买面包的时候同时购买牛奶, 销售商会把这两种产品放在一起进行销售, 极大的提高了销售额。

4.2 金融服务

金融服务行业广泛地应用了关联规则采掘技术。银行分析家运用关联规则采掘技术去分析大量的数据, 并为投资活动建立起贸易和风险模型。

4.3 科学数据分析

在地球科学数据分析中, 关联模式可以揭示海洋、陆地和大气过程之间的有趣关系。这些信息能够帮助地球科学家更好的理解地球系统中不同的自然力之间的相互作用。

5 结束语

社会信息量不断更新变化, 隐含的规则也在不断变化着, 而算法的研究是一个十分复杂的问题。本文对关联规则的算法进行了一定的分析。提高算法效率并应用于社会各个领域仍是人们关心的问题。

参考文献

[1]R Agrawal.Mining Association Rules Between Sets of Items in Large Databases[C].Washington:Proceedings of the ACM SIGMOD Inter-national Conference Management of Data, 1993.

[2]H.Toivonen.Sampling Large Databases for Association Rules[C].Pr-oceedings of the22nd International Conference on Very Large Data-base, Bombay, India, September1996.

[3]范明, 范宏建.数据挖掘导论[M].北京:人民邮电出版社, 2006.

[4]钱雪忠.关联规则挖掘中对Apriori算法的研究[J].计算机工程与应用, 2008 (17) .

[5]朱慧爽.关联规则挖掘算法初探[J].科技信息, 2008 (3) .

兴趣关联规则的挖掘 篇5

1 关联规则问题的形式化定义

我们假设I={i1, i2, …, im}是由m个不同的项目组成的集合。给定一个事务数据库D, D中的每一个事务T都是由I中的一些项目组成的集合, 即T⊆I, T有一个唯一的标示符TID, 关联规则就是形如X⇒Y的蕴涵式, 其中X⊆I, Y⊆I, 且X∩Y=ф, X⇒Y的支持度和可信度分别大于用户指定的最小支持度 (minsupp) 和最小可信度 (minconf) 。支持度和可信度的定义如下: X 是I的一个子集, 其补集记为Xc。如果满足X⊆T, 则称事务T支持X。否则, 如果Xc⊆T, 称T支持Xc, 设X是I的一个子集, X的支持度是指数据库D中支持X的记录数与总记录数之比, 记为P (X) , 也可理解为X在D中发生的概率, 蕴涵式X⇒Y的支持度是指数据库中同时支持X和Y的记录数与总记录数之比, 记为SX⇒Y, 则SX⇒Y =P (XY) ;蕴涵式X⇒Y的可信度是指数据库中同时支持X和Y的记录数与支持X的记录数之比, 记为CX⇒Y, 即:

undefined

由此可见关联规则的支持度给出了该规则发生的频度, 其可信度给出了规则发生的强度。

从统计学的角度解释, 关联规则的开采问题就是在事务数据库D中找出具有用户给定的最小支持度和最小可信度的关联规则[6], 可以分解为以下两个问题。

(1) 找出事务数据库D中所有具有用户指定最小支持度的项目集。

(2) 利用频繁项目集生成规则。

2 支持度和可信度存在的问题的提出

已有的研究大多数是基于支持度和可信度框架的完善和改进[2,3,4,7], 在实际应用中, 发现用支持度和可信度为标准来产生关联规则, 会产生大量不相关、甚至是误导的关联规则, 有一些规则即使满足用户指定的最小支持度和可信度, 但仍没有给我们提供有用的信息, 这些规则是没有实际意义的。下面通过例子来说明。

例1:设事务数据库D由以下事务组成:

T1={i1, i2, i3, i4},

T2={i1, i4, i5, i7, i9},

T3={i1, i2, i3, i6, i9},

T4={i0, i1, i2, i3, i8},

T5={i0, i1, i4, i7, i8},

T6={i0, i1, i9},

T7={i0, i1, i2, i3, i6, i7, i9},

T8={i0, i1, i6, i7, i9},

T9={i1, i2, i3, i4, i5, i6, i7, i8},

T10={i1, i4, i5, i6}。

假如最小支持度和可信度分别为45%、90%, 通过计算我们可以得到以下两条规则:

i2 ⇒ i3, 其支持度为50%, 可信度为100%。

i0 ⇒ i1, 其支持度为50%, 可信度为100%。

观察数据库D我们可以发现, i2和i3总是同时出现, 因此i2和i3具有很强的关联性, 所以关联规则i2 ⇒ i3被挖掘出来;而对于i0和i1来说, 不管i0是否出现总有i1出现, 也就是说i0和i1之间没有关联性, 因此规则i0 ⇒ i1是错误的。但在现有的关联规则挖掘算法中, 它仍被挖掘了出来。

下面再来看一个关系数据库的例子。

例2:如下表:

其中im表示男性, iw 表示女性, ie表示工程师, iot表示工程师之外的其他职称。

通过计算支持度和可信度, 我们可以得到以下规则:i1 ⇒ i2, 其支持度为40%, 可信度为66%。然而, 挖掘出的这一条规则并没有提供给我们更多的信息, 因为事先我们从数据库中已经知道了男性职工中大部分是工程师。

从例1和例2中可看出, 一条即使可信度和支持度都很高的规则, 它的实际价值已经没有人们期望的那么高了, 更严重的话, 这条规则确实会是误导性的。因此, 人们引入了新的标准——兴趣度来加强对关联规则的判定[8]。

3 兴趣关联规则

通过上面的例子可以看出, 挖掘出的关联规则X⇒Y, 尽管满足用户指定的最小支持度和可信度, 但当Y与X不相关或先验知识知道较多的情况下, 这些关联规则是没有现实意义的, 或者说我们对这些关联规则并不感兴趣。为了克服这些问题, 引入关联规则的兴趣度概念。

规则X⇒Y的兴趣度为:

undefined

其中:

undefined

当规则X⇒Y的支持度和可信度分别大于用户指定的最小支持度minsupp和可信度minconf, 并且它的兴趣度大于用户指定的最小兴趣度minint时, 称规则X⇒Y为兴趣关联规则。

分析I的含义:

当I>0时有C-C’>0, 即P (XY) >P (X) P (Y) , 从而有:

undefined

说明X的发生对Y的发生起积极作用。特别当I=1时, 有P (XY) =P (X) 成立, 说明X发生时必然有Y发生。

当I<0时有C-C’<0, 即P (XY)

undefined

说明X的发生对Y的发生起抑制作用, 也可理解为Xc的发生对Y的发生起积极作用。特别I=-1时, 有 P (XcY) =P (Xc) 成立, 说明X不发生时必然有Y发生。

当I=0时有C-C’=0, 整理得P (XY) =P (X) P (Y) 。

说明X与Y没有关系, 即Y的发生独立于X的发生。

当I的值越接近1时, X与Y的关联性越强, 规则X⇒Y越具有现实意义。

当I的值越接近-1时, Xc 与Y的关联性越强, 规则Xc⇒Y越具有现实意义。

当I的值越接近0时, X与Y越不相关, 规则X⇒Y没有提供太多有用的信息, 这些规则没有实际的意义。

再来看上面的例子。对于例1来说, 由于I=0, 所以规则i1 ⇒ i2将不被发现。对于例2来说, 如果设最小兴趣度为30%, 由于I=-23.85%, 因此规则i1 ⇒ i2也不被发现。

4 关联规则挖掘算法的修改

下面将只考虑支持度和可信度的关联规则挖掘算法进行修改, 将它运用到引入兴趣度之后的情况。

由于关联规则的挖掘分为搜寻频繁项目集和产生关联规则两步。对于第一步, 我们可以采用现有的挖掘算法如Apriori等, 来产生频繁项目集。对于第二步, 找到的规则, 除了满足用户指定的支持度和可信度之外, 还要满足兴趣度阈值。

兴趣关联规则的挖掘算法描述如下:

(1) 利用Apriori等算法得到所有频繁项目集[9,10]L。

(2) 对L中的频繁项目集A和A的每一个非空子集B, 计算支持度P (A) 、P (B) 和P (A-B) 。

计算规则B⇒A-B的可信度C和兴趣度I的值。

undefined

其中:

undefined

(3) 根据C、I的值输出规则

如果C≤minconf, 说明规则B⇒A-B的可信度较低, 淘汰。

如果C> minconf, |I|

如果C>minconf, I>minint, 说明B对 (A-B) 具有积极作用, 规则B⇒ (A-B) 的兴趣度较高, 具有实际意义, 输出。

如果C>minconf, I<-minint, 说明B对 (A-B) 具有抑制作用, 此时我们对规则Bc ⇒ (A-B) 感兴趣, 输出此规则。

整个兴趣度关联挖掘算法描述如下:

输入: 最小支持度、最小可信度、有趣度阈值: minsupport、minconfidence、ri。

输出: 所有有趣的强关联规则。

首先利用经典 Apriori产生出大项目集:

再利用大项目集产生有兴趣度约束的关联规则:

5 应用结果说明

在用引入兴趣度的关联规则挖掘方法对局部的学生成绩数据库挖掘后, 得出了以下所示的兴趣度阈值和挖掘出的规则数目的关系如表1。

根据表1可以看出, 随着兴趣度阈值的提高, 挖掘出的规则的数量急剧减少, 成功的实现了无用规则的过滤。

6 结束语

文章对现有关联规则进行了分析, 指出了其不足之处:有些关联规则即使支持度和可信度都很高, 但仍没有实际意义。提出了一种度量关联规则兴趣度的方法, 并给出了兴趣关联规则的挖掘算法。通过对关联规则兴趣度的度量, 在挖掘关联规则时可以避免无意义规则的产生。

参考文献

[1]Agrawal R, Imielinski T, Swami A.Mining associationrules between sets of items in Large databases.[J].Pro-ceedings of the ACM SIGMOD Conference on Manage-ment of Data.Washington D.C, 1993, :207-216.

[2]Wu Xindong, Zhang Chengqi, Zhang Shichao.Miningboth positive and negative association rules[C]//Pro-ceedings of the 19th International conference on MachineLearning (ICML-2002) .San Francisco:Morgan Kauf-mann Publishers, 2002:658-665.

[3]张梅峰, 张建伟, 张新敬.基于Apriori的有效关联规则挖掘算法的研究[J].计算机工程与应用, 2003 (19) :196-198.

[4]宋海声.关联规则增量式更新算法[J].兰州大学学报 (自然科学版) , 2004 (2) :47-50.

[5]刘渊, 吴以才.基于效益度的高效关联规则挖掘算法[J].浙江大学学报 (工学版) , vol.41 No.6 Jun.2007:909-914.

[6]史忠植.知识发觋[M].北京:清华大学出版社, 2002.

[7]Han Jiawei, Kamber M.数据挖掘:概念与技术[M].北京:机械工业出版社, 2001.

[8]李伟东, 倪志伟, 刘晓.基于兴趣度的关联规则挖掘[J].计算机技术与发展, 2007 (6) :80-82.

[9]王珊等.数据仓库技术与联机分析处理[M].科学出版社, 1998.

关联规则算法优化研究 篇6

在数据挖掘的知识模式中, 关联规则模式是比较重要的一种, 也是最活跃的一个分支。关联规则表示数据库中一组对象之间某种关联关系的规则。采用关联模型比较典型的例子是“啤酒和尿布”的故事。关联规则经典算法Aprior是由美国学者R.Agrawa1等人于1993年首先提出, 随即引起了广泛的关注。目前的大多数关联规则挖掘算法在这些情况下效率较低, 必须对关联规则挖掘算法作进一步的研究, 设计高效的算法。所以, 如何设计高效的更新、维护算法也是非常重要的研究课题。

1 关联规则算法简介

关联规则挖掘主要分为两个问题:a.找出事务数据库D中所有大于等于用户指定最小支持度的项目集 (itemset) 。具有最小支持度的项目集称为最大项目集, 简称大项集。项目集的支持度指包含该项目集的数目。b.利用最大项目集生成所需要的关联规则。对每一最大项目集A找到A的所有非空子集a, 如果比率support (A) /support (a) ≥minconfidence, 就生成关联规则a: (A-a) .support (A) /support (a) 即规则aÞ (A-a) 的置信度。

事实上, 由于第2步比较简单, 所以挖掘关联规则的关键就是寻找频繁集。

Apriori算法的中心思想是首先通过对事务数据库进行扫描, 找出支持度不小于最小支持度的所有项目, 即频繁I项集。接下来的工作是循环的, 每次循环分3步进行:a.连接, 对频繁k项集中的项进行连接, 前提条件是前k-1项必须相同。b.减枝, 在减枝这一步主要根据一个频繁项目集的任何一个子集都应该是频繁的这一思想对连接后的项目集进行筛选, 删除那些子集不是频繁集的项目集, 得出候选 (k+1项集。c.对数据库进行扫描, 计算候选项的支持度, 从候选集中删除支持度小于最小支持度的候选项, 进而得出频繁 (k+1) 项集。循环的终止条件是频繁k项集为空, 也就是说再也找不出相关联的项目了。

2 关联规则挖掘算法存在的缺陷

Apriori算法的频繁项集方法已被证明是在大型数据库中挖掘关联规则的有效工具, 但在实际应用中, 还存在不足之处。

2.1 关联规则有较大的冗余性。

2.2 由于该算法只用支持度和置信度这两

个标准来衡量关联规则, 在实际应用中常会产生一些没有价值的规则, 甚至是错误的结果。

2.3 关联规则挖掘算法的挖掘效率有待进一步提高。

通过前面算法的介绍, 我们知道Apriori算法在进行相应计算和操作时总是要对整个数据库进行扫描, 数据库有时候可达GB甚至TB数量级, 而数据库中有的事务是可以在扫描中略去的, 这样效率就会比较低。

3 关联规则算法优化

如何提高关联规则挖掘算法的效率一直是关联规则挖掘问题研究的热点。对关联规则问题的研究主要集中在以下几个方面:减少候选项目集的数量;减少对数据库的扫描次数;减少所需扫描的数据库的大小;为此, 特提出如下优化方案:

3.1 增加衡量标准

目前, 衡量和生成关联规则的标准主要有最小支持度和最小置信度两个。但仅用这两个标准来衡量关联规则显然是不够的, 由此提出增加如下标准:

3.1.1 兴趣度

一般来说, 如果挖掘出的关联规则具有新颖性———与人们以前的认识和观点不同, 或具有实用性———用户根据所挖掘出的关联规则可以辅助决策, 那么这样的关联规则就是用户感兴趣的规则, 或称关联规则是兴趣的。

兴趣度度量一条规则给用户带来的信息的多少, 不同的兴趣度的计算将具有不同的修剪效果。

在数值关联规则的挖掘中, 通过比较一条规则的预测支持率与实际支持率之间的差距来确定该规则的兴趣度。例如:对如下两条规则

(1) Þ (支持率8%, 置信度70%)

(2) Þ (支持率2%, 置信度70%)

如果己经得到了第一条规则, 则可以预测第二条规则具有2%左右的支持率和70%左右的置信度。因此第二条规则并没有带给用户更多的信息而可以被删除掉。

3.1.2 有效度

考虑数据库中X不出现而Y出现的可能性, 能较全面地描述X对Y的影响程度。将在数据库中X和Y同时出现的概率P (XY) 减去X不出现而Y出现时的概率P (XY) 定义为有效度, 取值在[0, 1]区间, 记为Validity。如果Validity<0, 则XÞY规则是无意义的。

如果在挖掘关联规则时, XÞY的有效度小于或等于零, 即使支持度和置信度均满足要求, 该规则仍是无用的。

所以, 将类似兴趣度、有效度这样的标准加入到关联规则的定义之中, 能够减少关联规则挖掘的盲目性, 从而提高算法的效率。

3.2 运用领域知识

领域知识就是在数据库中未明确表达, 而在该领域内达成共识的信息知识。

在数据准备与预处理阶段, 可以利用领域知识排除与关联规则发现无关的数据库中的记录或数据项, 有效地降低问题的维数, 缩减数据库的大小, 使设计出的挖掘算法更加有效。

在数据挖掘的产生假设阶段, 用领域知识排除假设中不必要的条件以优化假设, 减少从数据库发现有用信息的搜索时间。

在发现新模式阶段, 利用领域知识及对规则的关注程度或兴趣度无意义的候选关联规则进行修剪, 以提高挖掘效率。

但领域知识也应该认真使用以防阻碍一些有用规则的发现。

3.3 改进挖掘方式

关联规则挖掘的基本模型在数据集更新 (事务数的少量增减) 时, 需要对整个数据集重新进行挖掘。关联规则挖掘的增量算法对数据集中的事务增加时的关联规则挖掘进行了优化, 算法只需要找出新增数据集中的频繁项目集并对原数据集扫描一次就可以确定更新后的整个数据集中的新的频繁项目集。

Online关联规则挖掘是针对关联规则挖掘的基本模型的封闭性而作的改进。关联规则挖掘的基本模型的封闭性是指在寻找频繁项目集的过程中, 用户难以与挖掘算法交互。Online关联规则挖掘使用户在第一次扫描数据集的任何时候都可以根据需要调整最小支持率和最小置信度, 以挖掘出所需的关联规则, 该算法只需对数据集扫描两次。

4 结论

本文通过对Apriori算法的分析, 找到该算法存在的缺陷, 并提出算法改进的可能方向和途径。

参考文献

[1]Vipin Kumar, Mahesh V.Joshi, Eui-Hong Sam Han, etal.High Performance Data Mining[M].Lecture Notes in Computer Science.2003, 8:63-88页

[2]陈辉, 向伟忠, 单健.关联规则挖掘在教师教学评价系统中的应用[J].南华大学学报 (自然科学版) Vol.19.No.1

多层关联规则 篇7

1 概化处理

数据挖掘的目的是从大量日常业务数据中抽取一些有价值的知识或信息。原始业务数据是知识和信息提取的源泉,对于数据挖掘十分重要。数据挖掘算法中的数据往往受噪声数据、丢失数据和不一致数据的侵扰,一般都具有不完整性、冗余性和模糊性,很少能直接满足数据挖掘算法的要求。对财务报表来说,由于每个公司季度报表推出时间不一致,在行业内的公司没有全部推出季报时进行数据挖掘分析,就存在数据不完整的现象。所以对不理想的原始数据进行有效的归纳和预处理成为数据挖掘的关键问题。

数据预处理是数据挖掘前的准备工作,一方面保证挖掘数据的正确性与有效性;另一方面通过对数据格式和内容的调整,使数据更符合挖掘的需要。对财务报表预处理包括对财务报表进行数据清理与数据变换。数据清理目的是填写缺失的报表数据,数据变换是对连续的财务指标数据进行离散化,进而进行概化处理。

概化处理完成数据预处理工作,其获取行业内个股财务信息,求取行业平均值,并存入数据库,利用行业均值,对个股财务记录信息做数值型数据转化处理,生成事务表。

1.1 数据清理

对于每一项财务报表指标,求取一个行业平均水平值,所有的财务指标均值,即统计中的算数平均值,组成的报表,也在此称为行业均值报表。

对每一个行业,查询行业内上市公司财务报表中的各指标值,统计和并计算均值,构成均值报表后写入数据库保存。例如:资产负债的行业均值表,如表1。

每项均值的计算为所统计的上市公司该项财务指标值的和除于参加统计公司数,例行业的流动比率均值为:

因为上市公司的财务报表公布不同步,对于未公布数据的空缺项,用均值来补充,即假定该公司在该项取得行业均值。这样处理后,为后续的处理过程准备完整的数据。

1.2 数据概化处理

由于财务报表指标数据为数值型数据,所以首先概化处理为布尔型,以便在后续的数据挖掘中用布尔型关联规则挖掘方法进行挖掘。进行布尔型转换的第一步是将数值型数据进行概念分层,将数值型财务指标概化为三个数值区间{Ei-K==Ei+K},其中FINi为第i项财务指标,Ei为FINi的期望值,即FINi的行业均值,K为行业分析师对该指标期望值得一个评估估算值,当FINi在(Ei-K,Ei+K)时行业分析师认为该指标处于行业的平均水平。每个区间映射成一个变量,上述三个区间映射为{FINi1,FINi2,FINi3}。公司的该项FINi数值落在哪个区间,则取值为1,否则为0。财务指标数据转化规则表,如下表2。

例如:取某个行业的某季度的主营业务收入增长率,流动比率,每股收益增长率构成数据挖掘前的事务表,该数据转化规则表如表3。

该行业内上市公司该季度的这三项实际数据表,如表4。

该行业内上市公司该季度的这三项转化后的财务指标的布尔数据表,如表5。

在表中如果有多个取值一样的行,则添加一个属性统计记录相同行数,而证劵代码的属性取值较多,由数据概化中基于属性的归纳法原理可知当一个属性的属性值有许多个不同的值,且没有合适的泛化操作,应该做删除该属性处理。如表6所示。

2 关联规则挖掘

对之前做的概化处理都是为关联规则的挖掘做准备工作的,关联规则的挖掘工作将在概化处理形成的事务表上进行。将前面的布尔数据表每行中列为1的项取出组成一个事务,如表5第一行{FIN11,FIN22,FIN32},下面对数据挖掘的基础知识做简要介绍。

2.1 关联规则理论概述

定义1关联规则挖掘的数据集记为D(D一般为事务数据库D={t1,t2,t3,t4,t5,…tn},tk(k=1,2,…,n)称为事务,im(m=1,2,…,p)称为项。

定义2 I={i1,i2,i3,…,ip}是D中全体数据项组成的集合,I的任何子集X称为D中的项集,若|X|=k,称集合X为k-项集。tK和X分别为D中的事务和项集,如果X t K,称事务tK包含项集X。

定义3数据集D中包含项集X的事务数称为项集X的支持数,记为σX。项集X的支持度记为support(X),

support(X)=σX/|D|×100%(1-1)

其中,|D|是数据集D中的事务数,若support(X)不小于用户指定的最小支持度阈值minsup,则称为X为频繁项集,否则成X为非频繁项集。

对于项集和其子集在支持度上的关系有定理如下:

定理1 X、Y是数据集D中的项集

(1)X Y,则support(X)≥support(Y)

(2)X Y,如果X是频繁项集,则Y也是频繁项集

(3)X Y,如果Y是频繁项集,则X也是频繁项集

频繁项集是进行关联规则挖掘的基础,找出频繁项集后,关联规则的定义如下:

定义4若X、Y为项集,且X∩Y=ø,蕴涵式X=>Y称为关联规则,X、Y分别称为关联规则X=>Y的前提与结论。项集X∪Y的支持度称为关联规则X=>Y的支持度,记为support(X=>Y)

support(X=>Y)=support(X∪Y)(1-2)

关联规则X=>Y的置信度记为:confi dence(X=>Y)

confidence(X=>Y)=support(X∪Y)/support(X)×100%(1-3)

最小置信度阈值记为minconf。

定义5若support(X=>Y)≥minsup且confi dence(X=>Y)≥minconf,称为关联规则X=>Y为强关联规则。

上述两个定义中的X、Y项集在应用中为频繁项集的子集。所以关联规则的挖掘分为两个问题:

(1)根据minsup找出数据集D中的所以频繁项集

(2)在频繁项集的子集中找出满足minconf的子集

对于第二步在实际应用中,对于每个找出的频繁项集S,输出所有的规则a=>S–a,其中a是S的一个子集,检验confi dence(a=>S–a)≥minconf成立,则a=>S–a为强关联规则。根据定理1,若果有a的子集ã,则ã的支持度不小于a的支持度,所以confi dence(ã=>S–ã)≥minconf如果成立,则confi dence(a=>S–a)≥minconf也成立,因为confi dence(a=>S–a)大于confi dence(ã=>S–ã)。

频繁项集的寻找采用算法Apriori,Apriori使用逐层搜索的迭代算法,利用k-项集来探索(k+1)-项集。

2.2 行业财务指标的关联规则挖掘

由上节中表6某行业的某季度财务指标转化后的布尔数据统计表,来说明采用算法Apriori寻找频繁项集。设最小支持度为20%,最小置信度阈值为60%。

首先由表6得到事务集表,如表7:

最小支持度minsup=(2+2+3+4+5+2+3)×20%=4.2

(1)所有的项构成候选1-项集,如表8。

构成频繁项集支持度个数要满足大于4.2,项集中的支持度计数大于4.2的项集构成频繁1-项集,如表9。

(2)对表9频繁1-项集中的项集做连接操作得到候选2-项集,在这里有一个数据类型约束条件,即同类型属性的不同取值的连接操作是无效的,如{FIN11,FIN12},或{FIN12,FIN13},因为FIN11,FIN12,FIN13是同一个财务指标的不同取值,一个财务指标不可能有两个值,所以他们的连接是无效的。候选2-项集如表10。

提取支持度个数满足大于4.2的项集构成频繁2-项集如表11。

(3)对表11频繁2-项集中的项集做连接操作得到候选3-项集,在连接时同理要考虑到数据类型约束条件,候选3-项集如表12。

提取支持度个数满足大于4.2的项集构成频繁3-项集如表13。

(4)因为事务表项中事务最大项集个数为3,不可能有包含频繁4-项集,即频繁4-项集为空。算法停止。

根据所得频繁3-项集生成关联规则如下:

FIN12=>FIN22∪FIN32置信度为:

满足最小置信度60%要求的规则有FIN12=>FIN22∪FIN32,

根据上述项集与其子集的关联规则关系,ã为a的子集,则confi dence(ã=>S–ã)≥minconf如果成立,则confi dence(a=>S–a)≥minconf也成立。所以可知,因为FIN12=>FIN22∪FIN32能满足最小置信度,所以其超集FIN12∪FIN22,FIN12∪FIN32构成的规则:

都能满足最小置信度,所以得到上述两个满足条件的关联规则。

对于不满足最小置信度的两条规则

FIN22的超集有FIN12∪FIN22和FIN2∪FIN32,FIN32∪FIN12,这里只有FIN2∪FIN32=>FIN12未知其置信度是否满足最小置信度。

FIN22∪FIN32=>FIN12的置信度为:

该规则不满足最小置信度,舍弃。最后得到的符合条件的关联规则有:

由FIN12,FIN22,FIN32的财务指标意义来看,FIN2是主营业务收入增长率的取值,FIN22是流动比率取值,FIN32是每股收益增长率取值。

规则(1)说明了当主营业务收入增长率取得平均水平时,该行业的流动比率或每股收益增长率取值也会取得平均水平。

规则(2)说明了当主营业务收入增长率或每股收益增长率取得平均水平时,该行业的流动比率或取值也会取得平均水平。

规则(3)说明了当主营业务收入增长率或流动比率取得平均水平时,该行业的流动比率或每股收益增长率取值也会取得平均水平。

在实际应用中,因为每股收益是企业经营成果的指标,是对某个季度结束后经营结果的综合体现。而主营业务收入增长率或流动比率是反映企业财务某一方面的指标,所以规则(1)和规则(3)更有应用意义。根据挖掘出来的关联规则在查询该行业时的上市公司财务是,就可以进行有目的选择主营业务收入增长率和流动比率进行查看,从而形成该企业经营成果是否有增长的佐证。

每次将挖掘出来的关联规则进行存储进数据库,以便查询时提供给用户参考。

摘要：在一个行业的财务报表中,蕴含着行业的经营规律,找出这些规律对投资者在做财务分析时有潜在的价值。本文介绍一种运用数据挖掘理论中的关联规则挖掘算法来发现这些行业经营规律的方法,文中重点讨论了如何在财务报表数据的支持下运用关联规则算法探寻这些规律。

关键词：数据挖掘算法,关联规则,概化处理事务表,频繁项集,置信度

参考文献

[1]lan H.Witten Eibe Frank.Data Mining Practical Machine Learning Tools and Techniques with Java Implementations.China Machine Press.2003.9,57-116.

[2]朱济生,徐全智,朱宏.概率论与数理统计[M].成都:电子科技大学出版社,1995,155-156.

[3][美]Pang-Ning Tan,Michael Steinbach.,Vipin Kumar.数据挖掘导论[M].北京:人民邮电出版社,2006,53-83.