英语原文共 13 页，剩余内容已隐藏，支付完成后下载完整资料

Computational Statistics (2008) 23:303–315

DOI 10.1007/s00180-007-0062-z

原始论文

选择性关联规则生成

Michael Hahsler · Christian Buchta · Kurt Hornik

收录时间： 2007.2.28 / 网络出版时间: 2007.7.25

copy; Springer-Verlag 2007

摘要 在大型数据库中，挖掘变量间的关联规则是一个广受关注和研究的问题。但实际的问题是, 只有在数据库中，时间较长的大量的高频的数据才能找到一个基于大数量的关联规则。一种广为人知的解决方法是先逐步提高最小的支持度和信任度或用更为客观的方法来使这个规则所有的误差在可控的范围内，这样再选择出关联规则。在本文中,我们使用一个不同的方法，这个方法主要是基于一个概念的集，首先定义一组“有趣”项集(例如,用数据挖掘和其他知识来组成),然后，第二步是有选择地生成一个规则。这种方法的主要优势在增加阈值或选择规则的同时，选择出合适的规则且不会为了增加支持度和信任度而减少数据集中的重要信息。

关键字：数据挖掘 关联规则 规则生成

--------------------------------------

M. Hahsler (B)

Department of Information Systems and Operations, Institut fuuml;r Informationswirtschaft,

Wirtschaftsuniversitauml;t Wien, Augasse 2-6, 1090 Wien, Austria

e-mail: Michael.Hahsler@wu-wien.ac.at; hahsler@ai.wu-wien.ac.at

C. Buchta Institute for Tourism and Leisure Studies, Wirtschaftsuniversitauml;t Wien, Wien, Austria

K. Hornik Department of Statistics and Mathematics, Wirtschaftsuniversitauml;t Wien, Wien, Austria

1背景

在大型数据库中，挖掘关联规则是一个广受关注和研究的探索变量之间的关系的方法。Piatetsky-Shapiro(1991)分析并发现了一个十分强烈的规则，他发现在数据集中，不同的兴趣度的措施。基于强烈规则的内容,Agrawal等(1993)发现了一个规则。该规则发现在大规模事务在超市销售点系统记录的数据中，出售产品之间的某些规律。例如,该规则

{洋葱, 蔬菜} rArr; {牛肉}

在超市的销售数据中发现,如果一个客户同时购买了洋葱和蔬菜,那么他或她很可能也买牛肉。这些规则发现的信息可以超市决策活动的参考,例如,促销定价或产品配售。在今天,关联规则也用于许多领域，包括网络使用模式分析(Srivastava 等，2000),入侵检测(Luo和 Bridges，2000)和生物信息学(Creighton和Hanash， 2003)。

一般情况下，,从交易数据中挖掘关联规则的方法可以表示如下(Agrawal等， 1993)：

令是一个n维项集，令是一组交易数据。每个交易数据在D有一个独特的ID,并在I中有一个子集。关联规则的形式为：

XrArr;Y X,Ysube;I且Xcap;Y =empty;。

数据的组集(简称为项集)X和Y分别是先导(先导顺序，简称为LHS)和后继(后继顺序，简称为RHS) 为了从所有的规则中选择出最合适规则，我们广泛使用各种限制的方法。最著名的规则是支持度和信任度的最低阈值法。定义大量的包含项集的交易数据为具有支持度的项集。而所有具有支持度的项集被称为用户指定的最小支持度阈值的高频项集。规则XrArr;Y定义为conf(XrArr;Y)=supp(Xcup;Y)/supp(X)。其含义为估计值P(Y | X)的概率，概率是在RHS方法和LHS方法的共同交易项集中发现。(Hipp 等， 2000)。 关联规则必须同时满足用户指定的最小支持度和用户指定的最小信任度。关联规则的生成一直是两步的过程。首先,最小支持度应来自于数据库中所找出所有的高频项集。其次,高频项集和最小信任度之间用一个共同形式的规则来约束。

在时间较长的情况下,通常在数据集中，对大量的关联规则的高频项集或一个更大的项集分析关联规则是非常耗费时间,有时甚至是不可能的。有人也提出了几个方法来解决这个问题。一个可行的策略是增加用户指定支持度或信任度来减少挖掘规则的阈值。当然，许多人也习惯选择或使用其他的措施(Tan 等分析，2004)。然而,增加阈值和选择规则到可控范围内也只能改进已经十分明显的和众所周知的规则的一些问题。

另外,每个规则发现可以匹配一组额外生成的规则来判断是否很有用(Klemettinen等，1994)。同时,Imielinski和Virmani(1998)描述一种从一大组挖掘规则中用查询语言来检索规则匹配的特定条件。更快的方法是字母系数的方法，其方法是在项集中应用附加约束项条件或附加选项 (如，Bayardo等， 2000;Srikant 等，1997)。在使用这种方法时,我们发现挖掘大型数据库的时间和所发现的规则的数量可以显著减少。广为人知的实验过程由Borgelt(2006)以及一些商业数据挖掘的规定提供了一个类似的原理,即用户可以指定在LHS或RHS的部分中，哪些项目是需要的或不需要的。

在本文中,我们讨论一个新方法。不同于上述数据挖掘关联规则中的指定结构两步过程(如按示例的规则),我们为获得更多的灵活性，完全忽略高频项集规则生成中的发掘。这样的话，规则可以从所有项集中的任意项集中来生成。这样，分析人员可以任意定义一组“有用”的项集，而且找出这些项集的大致规律。有用的项集可以在综合使用数据挖掘、实际试验和更多的知识的基础上分析结果。

2高效选择性规则生成

为了方便起见,我们定义为一组项集。类似地,我们定义的规则为。

生成关联规则是一般分为两个步骤。首先,挖掘所有高频项集然后生成一组的规则。鉴于广大分析员对于第一个任务的研究(如，Hipp 等，2000; Goethals 和 Zaki，2004),因此,我们主要讨论接下来的第二个任务,规则生成。

一般情况下，RHS先导规则为对任意大小的维的每个 ，我们用所有非空子集对Z中的Y，检查对的规则，由此作为规则RHS。对大数据集，这显然会导致一个巨大的计算量。因此,大部分也符合本文一开始的定义--Agrawal等(1993)坚持限制Y的数据,这减少了问题只检查项集长度的大小。

这个规则的发现改进了众所周知的关联规则(如先验的算法,改进由Borgelt ，2003， 2006)，它通过再次使用数据结构来建立广泛的标准，并用科学的算法和确定的高频项集的基础上有效地生成规则。数据结构包含了所有已知信息，并快速计算得出规则的信任度和其他特征的方法。

如果一组项集是由一些普通的项集组成,即没有特殊的数据结构。向下封闭性属性的出现(Agrawal和Srikant，1994)保证高频项集的所有子集也高频出现的,数据结构可以从一组完整的高频的项集和它所有已知的值来构造。然而,本文的目的是有效地找出任意项集的规则,比如可以指定由一个专家不用数据挖掘工具的帮助来寻找。在这种情况下,支持的信息需要计算的信任度是不可能的。例如,如果所有可用的信息是某个包含五项的项集,它需要生成所有可能的项集的规则就必须包含所有项目,而我们必须知道项集的支持信息(我们可能知道)和所有的子集的可知长度。这个丢失的信息必须可以从数据库中获得。

一个简单的方法是用中的已知的最少的高频项集来再次实现关联规则。如果信息已知,我们会找出。否则,我们可以迭代减少已知信息的要求，直到发现包含的所有项的也在中。规则生成时会产生所有规则的集合,这些规则来自于的项集。从这组规则排除不源于的项集,只留下我们所需的规则。很明显,这是一个无效的方法，因为它可能会产生包含很多规则的集合，而其中大部分必须过滤,这需要一个庞大的计算过程。解决这个问题的方法是使用几个限制条件。例如,我们可以限制最大高频项集的长度和中的维数。另一个减少计算复杂性的方法是可以在数据分析前删除数据库中所有不在项集中的子集。然而,这一过程仍不是最佳,特别是如果包含许多高频项集或者包含一些非高频的项集。

为有效地生成规则，对于一个给定可信度或其他限制条件的规则的任意的项集，则必要计算步骤如下:

1、计算每个项集的值和项X，规则生成需要通过数据库的检验并将它们存储在一个合适的数据结构。

2、填充，只通过选择性地生成规则集合的项集使用的步骤1中已知数据结构的信息。

这种方法的优点是不需要复杂的规则,并且一些包含在内但非高频的项集可以被忽略。

计算出来的所需的数据结构需要提供快速查看和计算检验的方法。一个合适的数据结构是斐波那契数列(Knuth，1997)。通常,高频项集的挖掘使用斐波那契数列来压缩数据库。在这里子集需严格前缀排序，且每个节点包含斐波那契数列的前缀内容。

节点的组成就如一个普通的斐波那契数列的节点树。数据库表1中表示为图1中的前缀树,每个节点包含一个前缀和数据库中的前缀的计数。例如,第一个前缀{ a,b,c }是负责创建(如果节点已经不存在了)节点与前缀,ab和abc和增加每个节点的计算。

表1 示范数据

图1 数据的前缀树

虽然添加一个前缀树非常有效,包含子集的树的计算十分庞大，因为需要计算的是几个节点访问的次数和他们的数量加起来的数字。例如, 从前缀树在图1中检查项集X的支持度X = { d，e },所有节点除了abce,bce和e外都必须访问。因此, 计算应包含的单个子集对于选择规则生成是必须的 ,使用这种前缀树不是非常有用。

Borgelt 和 Kruse (2002)提出，选择规则时，生成我们用一个前缀树代替项集树。但是,我们并不生成大范围的树,但是我们首先生成一个前缀树只包含必要的节点来保存所有项集的计算过程。例如,生成规则项集{ a,b,c },我们需要计算项集,除了{ a、b },{ a,c }和{ b,c }。相应的前缀树图2所示。项集的包含节点树使它一个前缀树必要的节点和所有计数刚开始为零。同时，我们注意到,随着越来越多的项集,树中的节点的增长将减少,因为项集通常共享子集,因此节点也在其中。

图2　前缀树对项集计数 一个包含空树计算所需的项集的规则，包含{ a,b,c }和b包含计数

表2 递归函数

T

在创建树之后,我们在表二中用递归函数计算了所有前缀点。函数COUNT(t,p)是指计算一个项(作为数组)代表一个完全有序集的项)和前缀树的根节点。开始,我们测试如果项是空的(第1行),且如果是这样,则递归。在第2行中,我们试图获得当前节点的后续节点对应于第一项在t上的数字。如果找到一个节点n,我们增加节点的数量,继续递归地计算与剩下的项(4和5行),否则不需要进一步计算这个分支的树。最后,我们递归地计算事务删除第一个元素也为根节点的子树p(第6行)。这是在一个项中所有必要计算的项集。例如,一个个的计算项{ a,b,c,e }的前缀树在图2中增加节点,ab,abc,ac,b,bc。

说明有几个方法来建立一个n维前缀树的结构(如,每个节点包含一个项集的数组或使用散列表)。在实现用于实验在这篇文章中,我们使用一个链表来存储所有直接往下实现的一个节点。这种结构简单,节约内存,但随着时间复杂度不断增加且有直接往下的节点，还能在项集中用递归函数进行计算(参见表2中第2行)。然而,这个缺点可以减轻第一次排序子集的非高频性。这确保子集可以通常出现在数据库的链表的开始。

表3 项集数据表

计算后,每个节点中包含的项目集的信息的前缀等于项集。因此,我们可以从前缀树中查找所需的信息并直接生成规则。

3实验结果

我们实现了提出的选择性规则生成程序使用C代码和添加到R包arules(Hahsler 等，2007)。1检查效率我们使用三个不同的数据集表3所示。成年人的数据集被Kohavi提取(1996)于1994年美国人口普查局数据库,其可以从UCI机器学习数据库的存储库中找到(纽曼等，1998)。然后，我们的属性映射到序数属性,每个属性的值被一个项目编码。记录的数据集arules也包含在内。T10I4D100K是一种由Agrawal 和Srikant (1994)提出的人工生成的标准数据集，它被用于许多论文的评价过程。POS是电子商务数据集，包含由蓝色马提尼软件提供KDD Cup 2000(Kohavi等，2000)的好几年的销售点数据。这三个数据集的大小有相对较小的少于50000交易和大约100件物品交易超过500000和500000项。且来源也不同,因此使用这些数据集应该提供洞察该方法的效率。

我们比较上述的规则生成方法和高度优化的先验的实现Borgelt(2006)产生关联规则的运行时间。首先,我们规定以下条件:

bull;与表3中的方式不同,我们使用最小的支持项集X的值作为约束和最小支持我们限制挖掘项集不超过最长的项集 X。同时,我们删除所有在数据库但不在X中的项集。这些设置也显著减少搜索空间,因此须一开始就设定。然而,必须指出的是,设置最低要求的项集X的信息是已知的。事实并非如此,如果该项集由一个无法挖掘

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[31713]，资料为PDF文档或Word文档，PDF文档可免费转换为Word