关联规则数据挖掘所用的采样方法
专利名称关联规则数据挖掘所用的采样方法
技术领域一般说来，本发明涉及一种方法、系统和程序产品，用于揭示大数据库中项目之间的关系即关联规则。
背景技术 数据挖掘是一个新兴的技术领域，其目的是从大数据库中提取重要的模式即引起关注的规则；一般说来，数据挖掘的领域包括可应用于从大量的现有数据中提取“知识”的所有方法。整个过程称为数据库中的知识探索。在研究数据挖掘方法所要完成的任务中，寻找关联规则只是其中之一。
关联规则挖掘已经由Agrawal等人引入(参见例如R.Agrawal andR.Srikant，Fast algorithms for mining association rules，in Proc.20thVLDB Conf.，Sept.1994.)，并且受到购货篮分析的促进。为了发现商店中哪些物品或者说货物是一起购买，产生了若干规则。更为一般地说，关联规则能够用于在数据库中若干记录的属性值之间发现依赖性。即使更具体的购货篮数据，对每个顾客通常也包括交易数据以及该顾客购买之货物的一个记录。在这样一个数据库中关联规则的一个实例，是买面包和牛奶的顾客中可能有80％也买鸡蛋。寻找关联规则的数据挖掘任务可以分解为两个步骤。第一个步骤包括寻找项目的所有集合，称之为项集，它们在数据库中以用户指定的一定频度出现，该频度称为最小支持。此类项集称为大项集。包含k个项目的项集称为k项集。第二个步骤包括在第一个步骤中找到的大项集之间形成隐含规则。
为了高效地产生关联规则，已经研究了几种算法。例如在上述文档中，Agrawal等人已经公开了众所周知的和非常成功的APRIORI(演绎)算法。衡量关联规则最重要的数值是支持值，它是在一种规则中，一个项目或者几个项目一起出现的相对频度。
目前在数据库非常大(条目数目为几百万记录及以上)的情况下，产生关联规则可能是极为耗时的。对于关联规则的数据挖掘提出的许多算法，一遍又一遍地搜索数据库以便确定共同出现的项集(即项目的集合)。对于大数据库，扫描数据库时的I/O开销可能极高。这种处理时间不仅仅是执行挖掘算法本身所需要。在预处理步骤期间也会耗用大量的时间。这包括数据输入所用的处理时间，也包括为了应用该算法而进行数据变换所用的处理时间。即使在大的MVS系统的情况下，这种准备也可能要花费几小时的宝贵CPU时间。
为了改善这种性能因素，已经建议不是对整个数据库来产生关联规则，而是抽取一个样本并以它为基础来产生关联规则。H.Toivonen，Sampling Large Database for Association Rules，Proceedings of the 22ndVLDB Conference Mumbai(Bombay)，India以及Zaki，M.J.，Parthasarathy，S.，Li，W.，Ogihara，M.，Evaluation of Sampling for DataMining of Association Rules，Computer Science Department，TechnicalReport 617，University of Rochester(1996)两篇文章中，已经引入了这种思路。
Toivonen等人论述了一种算法，用于探索“严格的”(不基于某个样本的)关联规则。按照这种思路，采样仅仅是用于规则支持值的预计算，它作为算法的一个步骤；对于根据某个样本获得“估计的”(近似的)关联规则的数据挖掘思路，Toivonen等人保持完全沉默。Toivonen等人也公开了样本规模的必要界限。使用一种单变量方法，已经估计出任意关联规则的支持值。通过使用二项式分布和应用Chernoff约束，Toivonen等人计算了真支持值和估计的支持值之间的误差超过一个给定阈值的概率。利用这项成果他们导出了一个公式，用于计算充分样本的规模。
Zaki等人发展了这种思路，发表了在采样条件下产生近似关联规则的这些约束。使用Toivonen建议的单变量方法，包括Chernoff约束，也计算了这些约束。这些研究表明这些约束的效率不很高，因为所需的样本规模可能非常巨大。如Zaki等人所示，所需的样本规模可能变得甚至比原始数据库还大(！)。因此当前的技术思路完全不能令人满意，实际上不能应用于真实世界的问题。
所以从原理上来说，基于样本的关联规则数据挖掘的方法，既可以在预处理步骤中节省处理时间，也可以在分析阶段节省时间。但是出现的基本问题是产生的关联规则的准确性。如果适当地选择了样本，就有可能估计这种方法带来的误差。通过计算足够大的样本规模，能够控制这种误差。但是目前完全不清楚如何确定合理的样本规模。
本发明基于改善关联规则数据挖掘所用技术性能的目的。
本发明的目的由独立的权利要求书实现。本发明更优越的安排和实施例在各自的从属权利要求中阐述。
本发明涉及一种数据挖掘技术，用于在众多的N种事务——每种事务包括多至p种不同的项目——之内确定关联规则。
依据本发明，在众多的N种事务中，根据精度需求确定一个样本规模n。选择样本规模n时，使它至少处于一种估计样本规模n*的量级上。
最后，在众多的N种事务中，根据样本规模为n的一个样本，按照关联规则挖掘所用的任何整套方法，使用关联规则作为众多的N种事务的估计关联规则，计算关联规则。
在本发明的所有实施例中，潜在的重要概念是以下观测结果如果在样本规模确定中引入了体现众多事务特征的更多参数，就能够确定小得多的样本规模，同时满足所需的精度需求。这与现有技术知识(例如参考上述的Chernoff约束)恰恰相反，在现有技术中不使用众多事务的性质。作为这些特征性质，本发明建议使用事务数目的规模N或者事务之内出现之不同项目的数目p。当然，一旦确定了包括这些特征性质的样本规模计算公式，还可以应用附加的近似技术来再次去除这些特征性质。即使是基于这些附加近似的样本规模，比起所有的现有技术的估计也有显著的改善。
正如若干实例所示，依据本发明确定的样本规模比原始的事务数目要小得多，比已知的现有技术方法要小得多。所以，对于关联规则的数据挖掘，本发明会非常显著地改善性能。
附图简要说明附图说明
图1显示了p＝2时置信椭圆的一个实例；图2显示了p＝3时置信椭球的一个实例；图3显示了一幅处理流程图，用于多变量情况下关联规则的采样。这个处理流程也可以同样应用于单变量模型而不会有任何另外的问题；图4显示了一个分布式处理模型，用于关联规则的挖掘。
具体实施例方式
在附图和说明中阐述了本发明的一个优选实施例，虽然使用了特定的术语，但是在此给出的说明仅仅是以通用的和说明性的意义下使用术语，而不是为了限制的目的。不过显而易见，可以作出多种修改和改变，而不脱离本发明的广义实质和范围，如同在附带的权利要求书中的阐述。
在硬件、软件或者硬件和软件的结合中都能够实现本发明。任何种类的计算机系统——或者适于实现本文介绍之方法的其它装置——都适用。硬件和软件的一种典型结合可以是带有一个计算机程序的一种通用计算机系统，该程序在加载和执行时，控制该计算机系统使之实现本文介绍的方法。本发明也能够嵌入到一种计算机程序产品中，它包括使本文介绍的方法能够实施的所有特性，而且当它加载到一个计算机系统中时，能够实现这些方法。
计算机程序意味着或者说计算机程序在目前的上下文中意味着以任何语言、代码或记号写成的任何表达式，形成一组指令，意图使具有信息处理能力的一个系统执行一种具体的功能，或者是直接执行，或者是执行之前经过以下两个步骤或其中之一a)转换为另一种语言、代码或记号；b)以一种不同的材料形式再现。
在目前的说明书之内，一个事务记录，或者简言之事务，仅仅指项目的一个元组；当然不需要这样一个记录已经成为任何计算机事务的一部分。使用事务记录这个词仅仅是由于历史的原因。除此以外，一个项目也可以表示任何类型的属性，而不必与真实世界中的一个物品相关。
一、引言在数据挖掘领域中，所谓的关联规则是一整套方法，为了从通常很大的数据集内确定未知的关系或者说规则。这套方法包括以下的过程。指定所谓项目的一个集合。这些项目可以从超级市场购货篮数据中购买。项目这个集合的子集是所谓的事务，例如啤酒和薯片作为一种事务，而另一种事务可能包括面包和黄油。项目的集合往往也成为项集。所以每一种事务包含一个项集。
更正式地说，在购货篮数据——它有众多的N种事务——中，挖掘关联规则的问题可以阐述如下。
令I＝(i1，i2，...，ip)为具有p个截然不同的属性值也称为项目的一个集合。事务数据库D(它有众多的N种事务)中的每种事务T，都具有惟一的标识符TID，并且包含着一个项目集合，比如T?I。一种关联规则是一个表达式A＝＞B，其中项集A∶B?I，而且A∩B＝φ。对于每个项集，如果D中s％的事务包含该项集，就说它具有s支持(因此，支持衡量表示相对频度)。如果包含A的事务中有c％也包含B，就说该关联规则具有置信度c，换言之，c＝支持(A∪B)/支持(A)，即在若干事务包含项集A的情况下，又包含项集B的条件概率。例如，在购买面包和牛奶的顾客中，可能有80％也购买鸡蛋。数字80％就是该规则的置信度，该规则的支持为支持(A∪B)。从此类数据库中进行关联规则的数据挖掘，包括发现所有此类规则的集合，条件是它们满足用户指定的最小置信度和支持值。
探索关联规则的数据挖掘任务可以分解为以下两个步骤1.对于k＝1；2；...；发现所有大的k项集。
2.根据这些大的项集产生规则。假设X是一个大的项集，对于每一个非空子集A?X，产生一种形式为A＝＞B的规则，其中B＝X-A，而且这种规则具有所需的置信度。
注意，基于所关注之所有事务的集合，确定上述的所有衡量值。
为了改善性能，此时我们可以考虑从所有事务的集合中，恰当地选择一个样本，并且估计这些所需的衡量值。在采样理论的语言中，所有事务的集合会对应于总体，其性质(即相对频度和其它衡量值)应当由恰当选择的样本进行估计。限于这个样本，我们可以计算所需事件的相对频度，作为总体上这些事件相对频度的估计量。
因此我们必须解决以下问题1.应当如何选择样本，才能尽可能地消除在数据库中可能的次序造成的可能的系统性偏差？2.最重要的是应当如何选择样本的规模，才能确保估计量(在我们的情况下是相对频度)的所需精度？3.应当如何理解估计量的精度？第一个问题旨在消除可能的系统误差。例如，从数据库中每n个记录选择一个作为样本，就可能会选中这种严重的系统性误差。
第二个问题涉及应当从整个总体中提取多少事务，即样本规模。从直觉上十分清楚，这个问题涉及从该样本能够达到的精度。这意味着100个事务的样本能够确保的估计量精度，比10000个事务的样本要低得多。
第三个问题涉及以下内容假设所有事务的集合包含1,000,000个事务。如果我们偶然提取了100个事务的样本，我们就能够计算一个项目(比如说)A的相对频度，作为整个总体上项目A之相对频度的一个估计量。如果我们又偶然提取了100个事务的第二个样本，我们也能够根据这第二个样本计算项目A的相对频度，并作为一个估计量，但是两次计算的频度将会不同。如果我们重复这个过程几百次，那么如此计算的相对频度将会或多或少地散布在整个总体上项目A的相对频度周围。
二、采样方法最著名的采样方案之一是所谓的柏努利采样。这样做假设是以例如一个顺序文件或数据库形式给出数据，其中的记录可以从1到N编号，并且可以沿着这种次序穿过数据库。给定了一个概率π，每个元素都能够以它被选中，这种采样方案如下对于第i个元素，进行一个随机实验以概率π选中这个元素。通过在区间(0，1)上产生一个随机数，如果所考虑的随机数小于π就选取第i个元素，否则就拒绝这个元素，就能够做到这一点。
注释如果使用所谓的线性同余随机数发生器，十分重要的一点是这样一个发生器的周期足够大。这意味着在周期为例如5的情况下，从区间(0，1)上产生出5个随机数之后，数字就会重复，这当然不是很明智的。作为某种经验法则，我们需要周期L和总体的数目N应当满足N&L]]&因为使用这种采样方案，样本规模不是一个固定的数目，而是在概率理论意义下的一个随机变量，其统计参数数学期望E和方差Var如下EBE(n)＝Nπ以及VarBE(n)＝Nπ(1-π)另外，对于指定的置信度水平(1-α)，可以由下式计算出一个置信区间，其中α为对于样本规模n，指定的误差概率N&&PlusMu1-&2N&(1-&)]]&这里 为标准正态分布N(0，1)-对于一个给定概率α之分布的百分位。给定了一个概率α，那么百分位 就是单位正态分布的随机变量(简写为N(0，1))超过概率 的数值。因此P(X&u1-&2)=&2]]&其中X(作为N(0，1)分布的随机变量)的密度d为
d(t)=12&exp(-12t2)]]&那么第i次观察要放入样本中的包括概率πi由下式给出πi＝π这意味着对于每一个元素，这个概率不变并且等于指定的概率π。
在这种情况下，第i个以及第j个元素同时放入样本中的包括概率πij等于π2。
这种采样方案的主要优点在于在计算机上很容易实施。缺点在于样本规模不再是一个固定量而是一个随机变量。
如果我们事先关注样本规模的固定量，那么我们就不得不使用所谓的简单随机采样。这是一种另外的采样方案，其中每一种观察放入规模为n之样本的包括概率不变&i=nN]]&其中n为样本规模，N为总体规模。
对于第i个以及第j个元素同时放入样本中的包括概率πij，我们得到&ij=n(n-1)N(N-1)]]&这样一种采样方案可以实施如下。假设ε1、ε2、...为区间
上均匀分布的独立随机变量。
1.如果&1&nN]]&那么选取元素k＝1，否则不选。
2.对于随后的元素k＝2、3、...假设nk为整个总体中最初k-1个元素中已经选取之元素的数目。如果在第k个随机变量εk的情况下，我们有&k&n-nkN-k+1]]&那么选取第k个元素，否则不选。
3.如果我们有nk＝n，本过程终止。
这样一种采样方案的缺点在于，必须保存已经选取之元素的数目。另一方面我们也有如下优点达到所需的元素数目之后，现在就能终止采样过程。
三、关联规则的数据挖掘所用的采样方法本发明介绍了一整套方法，基于一个样本而不是整个总体来计算关联规则。我们建议把这些关联规则用作整个事务总体的估计关联规则。那么，由于关联规则挖掘所用的这套实际方法能够限于仅仅这个样本，所以能够实现显著的性能改善。
所提议发明的重要特性是在达到指定的精度需求的同时，确定样本规模所用的技术。如同上面已经针对当前的现有技术进行的介绍，本发明的实质概念是，如果在样本规模确定时引入了更多的参数来描述众多事务的特征，就能够确定小得多的样本规模，同时使观察满足所需的精度需求。在本发明的一个实施例中，我们建议使用众多事务的规模N作为这种特征性质。在本发明的另一个实施例中，在事务中出现之不同项目的数目p用作特征性质。当然，一旦确定了包括这些特征性质的样本规模计算公式，还可以应用附加的近似技术来再次去除这些特征性质。即使是基于这些附加近似的样本规模，也比所有现有技术估计有显著的改善。或者换言之即使后来附加的近似再次去除了这些参数，也不会丧失通过考虑众多事务的更多参数特征，实现更小样本规模的显著优点。
按照当前的现有技术计算的估计结果(例如支持值的估计结果)，仅仅是基于单变量分析而获得。单变量分析意味着仅仅估计单一的数值。
与之相反，本发明的一个实施例通过一种多变量估计分析，建议了一种全新的方法。多变量分析意味着在估计分析中使用一个向量，该向量的每个分量都是一个估计量，而且所有分量同时估计。例如对于支持值，这种方法的思路是有一个样本规模，同时估计所有单一项目对指定正确结果的支持值。所提议的多变量方法是根据置信椭圆来确定必要的样本规模，具有几种优点。这种方法背后的基本思路是每个项目不仅仅估计一个支持值，而是同时估计所有支持值。如果支持值的这个向量离支持值的真正的现有向量足够近，那么在样本内数据中的结构也是有效的，所以这些规则将具有较好的精度；或者换言之，此时样本包含着与总体相同的结构，因而有相同的规则。
即使在Zaki等人或Toivonen等人的的文献中，也没有指出这样一个基于多变量分析的实施例。
另外，还介绍了如何做到尽可能随机地选择数据库中的记录。
三(1)、单变量模型基本概念是任何规则R的支持值都能够视为一个相对频度。这个数值能够通过一个估计量近似衡量如下。
假设整个数据库包括N个顺序地排序的元素(其中每个元素由一个记录表示)。对于每个元素我们都能够构建一个二进制属性，如果该元素支持该规则，即记录中出现规则的项目时，属性为1，如果该元素不支持该规则，属性就为0。这个二进制属性的平均值就是支持值(由p表示)。在一个样本不更换的情况下，提取这个支持值的一个无偏估计量(如果一个估计量的数学期望值等于应当估计的参数，该估计量就是无偏的)，就是该样本中对所有元素测得的二进制属性的均值(这个均值由 表示)。不仅如此，还可以为支持值构建一个置信区间。以下是一个置信区间背后的思路。从样本提取的估计量将近似于真值，这意味着估计量将不会每次都取得相同的数值。但是如果我们提取大量的样本并计算估计量，即可见到这些数值围绕真值散布。我们现在试图寻找一个围绕着计算出之估计量的区间，使得我们知道真值以一个给定的概率1-α处于这个区间中。按照我们的采样方法和估计量的种类，我们可以使用以下公式，推导出构建的置信区间 式中 为估计量， 为标准正态分布的百分位，N为整个总体的规模，n为样本规模。
给定了一个概率α，那么百分位 就是单位正态分布的随机变量(简写为N(0，1))超过概率 的数值。因此
P(X&u1-&2)=&2]]&其中X(作为N(0，1)分布的随机变量)的密度d为d(t)=12&exp(-12t2)]]&这意味着如果我们对一种规则计算这样一个区间，我们就能够确信这个区间覆盖真值的概率为1-α。该公式表明，样本规模能够控制这个区间的长度。样本规模越大，置信区间将越小；当给定了置信区间的最大长度时，它就能够用于计算样本规模。
问题在于我们不能直接使用以上公式，因为在提取样本之前 的数值未知。所以我们需要考虑以下公式，其中替换了求和的第二项。(差异在于在第一个公式中考虑 方差的估计量，而在第二个公式中是 的真实方差) 有两个概率来定义置信区间的长度。一个给出与真值的相对误差，另一个给出绝对误差。两个概率下面都要介绍。
一个用户将说明，最大近似误差应当偏离真值一个因子δ，因此是一个相对误差。由此我们可以使用下面的已知公式计算样本规模n=u1-&22Np(1-p)(N-1)&2p2+u1-&22p(1-p)---(1)]]&这个公式的问题在于我们需要知晓真值。看到了这个数值超过了一个给定的阈值Minsup以及该函数随p下降，我们就能够使用以下公式，确定最小样本规模的界限n=u1-&22NMinsup(1-Minsup)(N-1)&2Minsup2+u1-&22Minsup(1-Minsup)---(2)]]&以下的实例将会表明该公式的用途给定一个4000000个记录的数据库。指定的Minsup值为0.01，一种规则R的估计量以概率90％偏离真值不超过1％。那么需要提取规模为1415204个元素的一个样本。
Zaki建议使用以下公式来估计，从规模为n的样本得到的估计值 小于{大于}真值p的(1-δ){(1+δ)}，这意味着偏离p的相对误差小于δ
从上式他通过把右方与一个给定的误差概率α相比，就得到了必要的样本规模。
通过这样做，他获得了n＝-2ln(α)/pδ2为低限n＝-3ln(α)/pδ2为高限。
通过这样做，Zaki并没有考虑一个封闭的置信区间，如同我们以上所做。他仅仅论述了我们后面将要涉及之开区间的概率。至此我们可以说，我们的方法通过提取一个更小的样本，会得出更高的准确度。为了说明我们的方法优于Zaki的方法，再次考虑样本规模的计算。我们可以给出样本规模的近似公式(表示(1)式的近似值)n=u1-&22(1-p)&2p]]&此式将与Zaki的低限公式进行比较(按照Zaki的说法，它给出了最小的样本规模)。
两个公式的分母相同，因此只须证明-2ln(&)&GreaterEu1-&22(1-p).]]&在实践中通常选择0.1、0.05和0.01作为α。下表显示了对于上述α值的-2ln(α)和
因此对于所述数值，-2ln(α)总是大于 由此我们可以得出结论，对于这些数值以上给出的不等式成立。
计算样本规模的另一种概率涉及指定估计量和真值之间的绝对误差d。根据绝对误差度量d，可以推导出以下公式n=u1-&22p(1-p)d21+1N(u1-&22p(1-p)d2-1)---(3)]]&这个公式再次需要知晓真实参数p。但是一项分析表明，当p＝0.5时，上述公式具有最高的数值。因此要计算样本规模的一种可能方法是代入p＝0.5，得出样本规模n=u1-&224d21+1N(u1-&224d2-1)---(4)]]&以下实例将说明计算过程。给定一个7000000的总体规模、一个99％的置信区间和一个0.01的绝对误差，我们获得了一个16551的样本规模，它比现有技术有显著的改善。
Toivonen等人建议给定绝对误差d和误差概率α之后，采用以下的样本规模n=12d2ln2&]]&如同上面，我们可以表明我们的方法会产生一个更小的样本规模。我们再次使用一个近似公式n=u1-&22p(1-p)d2]]&只须证明12ln2&&GreaterEu1-&22p(1-p).]]&注意到对于0≤p≤1，有p(1-p)≤0.25，只须证明2ln2&&GreaterEu1-&22]]&如同上面，我们表明这个不等式至少对于普通的α值成立。
这表明与Toivonen等人的方法相比，我们的方法产生了更小的样本规模。
我们现在说明另一个结果，它可以应用于计算必要的样本规模。如果我们考虑以上的置信区间，能够发生两种误差。一种是真实支持值大于计算出的上限，另一种真实支持值小于下限。在实际情况下，有时仅仅需要真实值的置信区间在一侧进行限制(与Zaki等人比较)。
如果我们仅仅关注如何获得真值将以概率α超过的一个界限，我们就可以使用置信区间 这意味着我们可以确信，一种规则的真实支持值将不会大于该上限。对于支持值大于Minsup阈值的一种规则，如果我们要控制在样本中没有这种性质的误差，这一点可能很重要。例如假设Minsup值给定，在样本中一种规则的支持值产生了上述的置信区间，其上限小于Minsup。那么，这种规则在总体上已经获得了一个支持值，它大于Minsup的概率小于α。
我们可能关注的另一种情况是使用以下的只有一个低限的置信区间 如果我们仅仅关注真实支持值小于该下限的误差小于误差概率α，就可以使用这个置信区间。如果一种规则的支持值大于Minsup阈值，而真实值小于这个阈值，在要控制这种误差时，可能就是这种情况。例如，假若在样本中一种规则将具有一个支持值，使得对应置信区间的下限大于Minsup阈值，那么真实值小于这个界限的误差概率最多也仅仅是α。
从这两个公式，以我们在上面所做的相同方式，我们都能得到样本规模。在公式中仅有的改变是由 替换了 因此，对于一个单界的置信区间，当真实值的相对误差δ给定时，其样本规模为n=u1-&2Np(1-p)(N-1)&2p2+u1-&2p(1-p)---(5)]]&如上所述以Minsup替换p，有n=u1-&2NMinsup(1-Minsup)(N-1)&2Minsup2+u1-&2Minsup(1-Minsup)---(6)]]&给定了一个绝对误差时，我们可以使用以下公式计算样本规模n=u1-&2p(1-p)d21+1N(u1-&2p(1-p)d2-1)---(7)]]&式中p可以选为0.5，使得n取最大值，有n=u1-&24d21+1N(u1-&24d2-1)---(8)]]&由这些公式获得的样本规模小于对应的封闭置信区间计算出的样本规模。由于已经证明后面的样本规模小于Zaki等人和Toivonen等人建议的样本规模，这里得到的样本规模也如此。
三(2)、多变量模型在前一节中，我们说明了如何使用置信区间来估计一个项目或者一个项目集的支持值，它指明一种规则的支持值。如上所述，具有(1-α)置信水平的一个置信区间，其意义在于，在所有样本的百分之(1-α)×100中，整个总体上项目A的相对频度被对应的置信区间所覆盖。
这个思路(在同时考虑p个项目的意义下)的一种扩展，包括构建一个所谓的在置信水平(1-α)的置信椭球。p维中的一个置信椭球在p维中定义了一个区域，使得真值以一定的概率(1-α)处于这个区域中。
在p＝2个项目的情况下，这个椭球就是一个椭圆。图1显示了对于p＝2之置信椭球的一个实例。在p＝3个项目的情况下，置信椭球的一个实例显示在图2中。
另一方面，宽度(分别为面积或体积)是精度的一种度量。所以，如果我们需要一定的精度，我们就可以如此选择样本规模，使得宽度(分别为面积或体积)(对于所需的置信水平)不超过规定的界限。
为了同时估计若干单个项目的支持值，需要把每一个事务变换为一个二进制向量。那么，这样一种向量的每一个分量对应于一个项目，其中数值1意味着所考虑的项目在所考虑的事务中存在，而数值0则是该项目不存在。注意，二进制向量的维数由所有可能的单个项目的数目p隐含着。
现在假设对于i＝1，...，N，我们从总体中提取了一个样本，以若干p维向量表示Yi=Yi(1)&CenterD&CenterD&CenterDYi(p)]]&对于i＝1，...，N，我们进一步定义Y&OverB&CenterD(k)=1N&Si=1NYi(k)]]&Y&OverB&CenterD=1N&Si=1NYi=Y&OverB&CenterD(1)&CenterD&CenterD&CenterDY&OverB&CenterD(p)]]&SY(k),Y(k)=SY(k)2=1N-1&Si=1N(Yi(k)-Y&OverB&CenterD(k))2]]&对于k＝1，......p；SY(k),Y(l)=1N-1&Si=1N(Yi(k)-Y&OverB&CenterD(k))(Yi(l)-Y&OverB&CenterD(l))]]&对于k≠l＝1，......，p&SY=(SY(k),Y(l))k,l=1,...p]]&样本中的这些向量将由yi表示，使得我们以y替换Y，以n替换N，就得到样本上对应的量，仅有样本的协方差矩阵例外，它由下式表示s=(sy(k),y(l))k,l=1,...p]]&式中sy(k)，y(l)为根据该样本之协方差的对应估计量。
利用这种记法，对于一个简单的随机样本，我们能够证明以下定理定理1y.是Y.的一个无偏估计量。
Cov(y&OverB&CenterD)=1n(1-nN)&SY]]&是y.的协方差矩阵。
是Cov(y.)的一个无偏估计量。
另外我们还能够说明对于估计量y.的一个中心极限定理定理2在一种简单随机采样的情况下，假设nv→∞并且如果nv→∞，(Nv-nv)→∞令Iv＝{1，...，Nv}对于i∈Iv，Yvi=Yvi(1)&CenterD&CenterD&CenterDYvi(p)]]&对于i＝1，...，nv，yvi=yvi(1)&CenterD&CenterD&CenterDyvi(p)]]&对于所有τ＞0和k＝1，...，p，Iv&(k)={i&EIv:|Yvi-Y&OverBv(k)|&&Var(&Si=1nvyvi(k))}]]&对于所有k＝1，...，p，&v(k)2maxaj|&Yv(k),&Sj&NotEkajYv(j)|,limv&RightA&sup&v(k)2&1]]&第k个和其余p-1个变量之间的多重相关系数y&OverBv&CenterD=1nv&Si=1nvyvi]]&Cov(y.)是y.的协方差矩阵那么我们有量Cov(y&OverB&CenterD)-12(y&OverB&CenterD-E(y&OverB&CenterD))]]&的分布对一个N(0，Idp)分布中的收敛，等价于条件limv&RightA&&Si&EIv&(Yvi(k)-Y&OverBv.(k))2&Si&EIv(Yvi(k)-Y&OverBv.(k))2=0]]&
式中的p维N(0，Idp)分布随机变量Y具有密度函数ff(y)=(2&)-p2exp(-12yty)]]&(注意y也是p维的)这个定理开拓了对于向量Y.，建立至少是近似置信椭球的可能性。
因为我们关注多变量的情况(与现有技术和前节中给出的改善相反)，我们现在要考虑置信椭球及其结构。
让我们首先考虑以下情况，观测结果是独立的和同等地多变量正态分布的p维向量，具有数学期望向量μ0和协方差矩阵∑，其逆存在。
现在让我们假设，我们要根据规模为n的一个样本，对于未知的数学期望向量μ0，构建所需的置信椭球。这样一个椭球由下式给出K&S={&0|n(x&OverB-&0)t&S-1(x&OverB-&0)&&1-&:p2}]]&式中x由下式给出x&OverB=1n&Si=1nxi]]&而且χ1-α:p2是这样一个数值，给定一个概率α，那么P(Y&GreaterE&1-&:P2)=&]]&式中Y具有p个自由度的一种χ2分布，即密度函数 式中Γ表示伽码函数&G(y)=&I0&ty-1exp(-t)dt]]&因此χ1-α:p2是具有p个自由度之χ2分布的百分位。
这是由于以下事实，如果数据是多变量正态分布，量n(x-μ0)t∑-1(x-μ0)就是具有p个自由度的χ2分布。
在协方差矩阵∑未知的情况下，就必须从数据中估计这个矩阵。∑的一个可能的估计量由下式给出S=1n-1&Si=1n(xi-x&OverB)(xi-x&OverB)t]]&那么对应的置信椭球由下式给出
KS={&0|n(x&OverB-&0)tS-1(x&OverB-&0)&(n-1)pn-pF1-&:p,n-p}]]&现在式中F1-α:p，n-p是使给定的一个概率α，下式成立的值P(Y≥F1-α:p，n-p)＝α式中Y是具有m1(＝p)个和m2(＝n-p)个自由度的F分布，即密度函数为 式中Γ表示伽码函数。
在数据是多变量正态分布的条件不满足的情况下，如果不使用数学期望向量之估计量的中心极限定理成立，那么以上给出的置信椭球仅仅是近似有效。根据这样一种近似，可以引入以下替换向量Y.替换数学期望向量μ0；估计量y.替换数学期望向量μ0的估计量x；协方差矩阵∑Y及其估计量s替换协方差矩阵∑及其估计量S。
如果我们假设中心极限定理成立，那么给定的置信椭球保持原样。所以我们得到了椭球K∑yK&Sy={Y&OverB&CenterD|n(y&OverB&CenterD-Y&OverB&CenterD)t&Sy-1(y&OverB&CenterD-Y&OverB&CenterD)&&1-&:p2}]]&以及KsKs={Y&OverB&CenterD|n(y&OverB&CenterD-Y&OverB&CenterD)ts-1(y&OverB&CenterD-Y&OverB&CenterD)&(n-1)n-pF1-&:p,n-p}]]&注意，当n→∞时，F1-&:p,n-p&RightA1p&1-&:p2]]&当p≥1时，n-1n-p&GreaterE1]]&这就给出了以下的近似置信椭球Ks={Y&OverB&CenterD|n(y&OverB&CenterD-Y&OverB&CenterD)ts-1(y&OverB&CenterD-Y&OverB&CenterD)&&1-&:p2}]]&为了确定必要的样本规模，我们固定所需的置信水平和所需的置信椭球最大体积。注意，p维椭球的体积由下式给出
V=const(p)Πk=1phk]]&式中hk(k＝1，...，p)表示椭球的半轴，const(p)是一个取决于维数p的常数。
如果我们定义了一个最大可容许的置信体积V*，那么就有V*=const(p)n-p2(&(1-&):p2)p2dets]]&从这个方程我们就获得了必要的n作为样本规模nV*=const(p)p2&(1-&):p2(dets)1p(V*)2p]]&涉及这个方程求解必要的样本规模是以下两个问题a.常数const(p)取决于维数p；b.我们需要协方差矩阵的一个先验估计。
为了解决这些问题，可以提议以下步骤以边长为2dk(k＝1，...，p)的长方体围绕半轴为dk(k＝1，...，p)的置信椭球。结果对于体积来说，该长方体围绕的最大椭球具有以下体积Vmax*=const(p)Πk=1pdk]]&从这个公式就有可能推导出以下的必要样本规模nn*=&(1-&):p2(Πk=1psy:k2dk2)1p---(9)]]&式中sy:k2为协方差矩阵s的第k个对角线元素。
如果我们由以下关系来定义量εk2dk=&ksy:k&DoubleLeftRightAdk=12&ksy:k---(10)]]&那么必要的样本规模将会按照相对精度 给出，这意味着半轴的长度是标准差sy:k的一个分数。
所以，必要的样本规模能够按照εk来表示n*=&(1-&):p2(Πk=1p4&k2)1p=&(1-&):p24(Πk=1p1&k2)1p---(11)]]&利用这样一个必要样本规模n*，对应的置信椭球将会被边长为2dk＝εksy:k的长方体所围绕。
选择所有εk等于一个所需的相对精度ε，那么我们就得到了必要的样本规模n*=&(1-&):p241&2---(12)]]&它可以用作专业人员的一个公式，尤其是在p相当大的情况下。
最后我们将探讨以下问题由于我们从整个总体提取了一个样本这一事实，我们就只能把一个支持值的估计结果与用户选定的所需之最小支持值进行比较。所以我们遇到了这样一个问题，由于随机的变化，我们可能获得了一个估计量，它仅仅是偶然低于给定的最小支持值。这表明我们应当关注一种统计测量，这种情况对于一个所考虑的项目或变量具有怎样的重要性。从统计的观点，这会导致我们下面将讨论的联合置信区间的理论。
从构建的置信椭球，可以获得这些区间如下。
对于任意 和假设为正定的pxp矩阵A，我们有 根据这个表达式，我们得到椭球K 所以我们能够把K直接嵌入在p维的长方体中，如果v是第k个单位向量(k＝1，...，p)，该长方形是以下面若干区间的积给出 这些区间中的每一个都表示为一个联合置信区间。以分量形式我们得到了Y.(k)的一个区间y&OverB&CenterD(k)&PlusM1n&(1-&):p2sy:k2---(13)]]&
三(2)、关联规则采样的处理流程图3显示了一幅处理流程图，用于前面章节中概述的多变量情况下关联规则的采样。这个处理流程也可以同样应用于单变量模型而不会有任何另外的问题。
在步骤301中作出一个决定，进行关联规则的数据挖掘是根据完全的众多事务记录(选择路径302)，还是根据一个样本(选择路径303)。在选定路径302的情况下，就在步骤304之内应用关联挖掘的一整套方法，随后由步骤305显示计算出的关联规则。
如果是存取路径303，根据一个样本来计算关联规则，首先就必须在步骤306之内确定样本规模。一种方法将包括直接指定样本规模。另一种方法将包括在一个步骤中计算样本规模。在多变量方法中，样本规模将根据以下因素计算a.在众多事务之内发生的不同项目的数目p，作为更完全地描述众多事务特征的参数，b.对于近似质量的进一步精度需求，例如包括b1.根据一个样本之估计的置信度(1-α)b2.按照(10)式对于各个项目的相对精度需求εk或者对于所有项目的公共精度需求ε。如果某些项目需要以比其它项目更高的精度来估计，那么就必须选择对于各个项目指定相对精度需求的方法。
根据这些指标，按照近似公式(11)或(12)，在步骤307之内将计算一个估计的样本规模。这个估计的样本规模可以直接用作样本规模，也可以仅仅用作一种定向。在后一种情况下，将必须在至少是估计样本规模的量级上，选定最终的样本规模。
根据记录的数量和计算出的样本规模，将在步骤308中通过随机采样，提取最终的样本。
使用这个样本作为输入，就可以在步骤304之内应用关联挖掘的现有技术诸方法，确定关联规则的估计结果，随后由步骤305显示出关联规则的估计结果。
如果步骤306也将包括指定一个所需的最小支持值，那么在步骤305中甚至也可能作出一个决定，是否关注一个所考虑的关联规则。为了达到这个目的，可以利用(13)式之内计算出的联合置信区间。将会应用以下的判断过程1.如果按照(13)式的置信区间完全处于这个最小支持值的左侧(即这个区间的上限小于最小支持值)，那么就不关注所考虑的项目，因为其支持值的估计量低于最小支持值。
2.如果对于所考虑的项目，按照(13)式的置信区间包括最小支持值或者完全在其右侧，那么就要关注该项目，因为其支持值的估计量高于最小支持值(记住，我们定义一个项目受关注是因为其支持值大于或等于预定的最小支持值)。
由于构建了这些置信区间，我们就能够确信，我们以公共置信度(1-α)，获得了所有受关注的规则。
四、应用依据现有技术，由于组成了众多事务记录之数据的巨大规模以及计算关联规则的处理时间极长，计算关联规则的计算机系统必须就是存放众多事务记录的同一计算机系统。由于本发明能够缩小数据量，实际的挖掘技术仅仅应用于事务记录的一个非常小的样本(与完全的众多事务记录相比极小)，所以建议了一种新的分布式处理模型，包括一台客户计算机和一台服务器计算机，由某种通信网络如因特网进行连接。
图4显示了一个分布式处理模型，用于关联规则的挖掘。
在图4之内展示了一台客户计算机401，用于控制关联规则的确定。客户计算机存放子众多的N个事务记录402。在步骤403之内，客户计算机以一个样本规模n，从众多的N个事务中提取一个样本404。样本规模可以由前面公开的方法中的任何一种来确定。
使用通信网络405把样本传送到服务器计算机406，它为关联规则的挖掘提供一种特定的服务。在步骤407之内，根据提供的样本计算关联规则，并且通过通信网络返回到客户计算机。由于现在分析所用的时间短(仅仅根据一个小样本)，就有可能很快地送回近似规则的计算结果。
那么最后，在步骤408之内，这些规则可以在客户系统中分析，进行进一步的操作。
根据服务器系统中提供的关联规则挖掘服务的程度，可能有两种不同的实施例或者客户计算机本身确定样本规模，或者服务器计算机负责确定样本规模。在任何一种情况下都是利用本说明书之内公开的确定样本规模的技术。
1.一种计算机化的数据挖掘方法，用于在众多的N种事务之内确定关联规则，每种事务包括多至p个不同的项目，所述方法包括一个第一步骤，确定所述众多的N种事务的一个样本规模n其中所述样本规模n是根据精度需求而确定，以及其中所述样本规模n是根据达到所述精度需求之多变量估计分析而确定，以及所述方法包括一个第二步骤，按照挖掘关联规则所用的任何整套方法，根据所述众多的N种事务中样本规模为n的一个样本，计算关联规则，使用所述关联规则作为所述众多的N种事务的估计关联规则。
2.根据权利要求1的确定关联规则所用之计算机化的数据挖掘方法，其特征在于所述精度需求包括一个置信度(1-α)，用于根据一个样本的一个估计，以及一个相对精度εk，用于一个样本的一个项目k，所述相对精度εk定义了与在所述众多的N种事务之内相比，在一个样本之内项目k之支持值的一个可接受的偏差，所述相对精度εk是相对于项目k之支持值的标准差而测量的，其中所述样本规模n至少是在一个估计样本规模n*的量级上，n*=&(1-&):p24(Πk=1p1&k2)1p]]&式中x1-α∶p2为具有p个自由度之x2分布的百分位，p为描述所述众多的N种事务特征的所述不同项目的数目。
3.根据权利要求2的确定关联规则所用的计算机化的数据挖掘方法，其特征在于所述相对精度εk＝ε对于所有项目k是同一的，以及其中所述样本规模n至少是在一个估计样本规模n*的量级上。n*=&(1-&):p241&2]]&
4.一种计算机化的数据挖掘方法，用于在众多的N种事务之内确定关联规则，每种事务包括多至p个不同的项目，所述方法包括一个第一步骤，确定所述众多的N种事务的一个样本规模n其中所述样本规模n是根据关联规则所用的精度需求而确定，其中所述精度需求包括一个置信度(1-α)，用于根据一个样本进行的估计，以及其中所述精度需求包括一个相对精度δ，定义了与在所述众多的N种事务之内相比，在一个样本之内，一个某种规则的支持值的一个可接受的偏差，所述相对精度δ是相对于所述某种规则的支持值而测量的，以及其中所述精度需求包括一个期望支持值的一个下界p，以及其中所述样本规模n至少是在一个估计样本规模n*的量级上，n*=u1-&22Np(1-p)(N-1)&2p2+u1-&22p(1-p)]]&式中 为标准正态分布的百分位，以及所述方法包括一个第二步骤，按照关联规则挖掘所用的任何整套方法，根据所述众多的N种事务中样本规模为n的一个样本，使用所述关联规则作为所述众多的N种事务的估计关联规则，计算关联规则。
5.一种计算机化的数据挖掘方法，用于在众多的N种事务之内确定关联规则，每种事务包括多至p个不同的项目，所述方法包括一个第一步骤，确定所述众多的N种事务的一个样本规模n其中所述样本规模n是根据关联规则所用的精度需求而确定，其中所述精度需求包括一个置信度(1-α)，用于根据一个样本进行的估计，以及其中所述精度需求包括一个相对精度δ，定义了与在所述众多的N种事务之内相比，在一个样本之内，一个某种规则的支持值的一个可接受的或正或负的偏差，所述相对精度δ是相对于所述某种规则的支持值而测量的，以及其中所述精度需求包括一个期望支持值的一个下界p，以及其中所述样本规模n至少是在一个估计样本规模n*的量级上，n*=u1-&2Np(1-p)(N-1)&2p2+u1-&2p(1-p)]]&式中u1-α为标准正态分布的百分位，以及所述方法包括一个第二步骤，按照关联规则挖掘所用的任何整套方法，根据所述众多的N种事务中样本规模为n的一个样本，使用所述关联规则作为所述众多的N种事务的估计关联规则，计算关联规则。
6.根据权利要求4或5的确定关联规则所用的计算机化的数据挖掘方法，其特征在于一个期望支持值的所述下界p，是关联规则挖掘的所述整套方法所用的一个最小支持值p＝Minsup。
7.一种计算机化的数据挖掘方法，用于在众多的N种事务之内确定关联规则，每种事务包括多至p个不同的项目，所述方法包括一个第一步骤，确定所述众多的N种事务的一个样本规模n其中所述样本规模n是根据关联规则所用的精度需求而确定，其中所述精度需求包括一个置信度(1-α)，用于根据一个样本进行的估计，以及其中所述精度需求包括一个绝对精度d，定义了与在所述众多的N种事务之内相比，在一个样本之内，一个某种规则的支持值的一个可接受的偏差，以及其中所述精度需求包括一个期望支持值的一个上界p，以及其中所述样本规模n至少是在一个估计样本规模n*的量级上，n*=u1-&22p(1-p)d21+1N(u1-&22p(1-p)d2-1)]]&式中 为标准正态分布的百分位，以及所述方法包括一个第二步骤，按照关联规则挖掘所用的任何整套方法，根据所述众多的N种事务中规模为n的一个样本，使用所述关联规则作为所述众多的N种事务的估计关联规则，计算关联规则。
8.一种计算机化的数据挖掘方法，用于在众多的N种事务之内确定关联规则，每种事务包括多至p个不同的项目，所述方法包括一个第一步骤，确定所述众多的N种事务的一个样本规模n其中所述样本规模n是根据关联规则所用的精度需求而确定，其中所述精度需求包括一个置信度(1-α)，用于根据一个样本进行的估计，以及其中所述精度需求包括一个绝对精度d，定义了与在所述众多的N种事务之内相比，在一个样本之内，一个某种规则的支持值的一个可接受的或正或负的偏差，以及其中所述精度需求包括一个期望支持值的一个上界p，以及其中所述样本规模n至少是在一个估计样本规模n*的量级上，n*=u1-&2p(1-p)d21+1N(u1-&2p(1-p)d2-1)]]&式中u1-α为标准正态分布的百分位，以及所述方法包括一个第二步骤，按照关联规则挖掘所用的任何整套方法，根据所述众多的N种事务中规模为n的一个样本，使用所述关联规则作为所述众多的N种事务的估计关联规则，计算关联规则。
9.根据权利要求7或8的确定关联规则所用之计算机化的数据挖掘方法，其特征在于一个期望支持值的所述上界p，是p＝0.5。
10.根据权利要求1、4、5、7或8中任何一条的确定关联规则所用的计算机化的数据挖掘方法，其特征在于挖掘关联规则所用的所述整套方法，是APRIORI方法。
11.根据权利要求1、4、5、7或8中任何一条的确定关联规则所用之计算机化的数据挖掘方法，其特征在于所述样本通过随机采样而提取。
12.一种客户计算机，用于控制在众多的N种事务之内确定关联规则，每种事务包括多至p个不同的项目，所述客户计算机从所述众多的N种事务中提取一个样本规模为n的样本，它至少是在一个估计样本规模n*的量级上，根据权利要求1至11中的任何一条的方法确定所述估计样本规模，所述客户计算机把所述样本发送到一台服务器计算机，以便确定关联规则，以及所述客户计算机从所述服务器计算机接收所述确定的关联规则，使用所述关联规则作为所述众多的N种事务的估计关联规则。
13.根据权利要求12的控制确定关联规则的客户计算机，其特征在于，所述客户计算机确定估计样本规模n*，或者所述服务器计算机代表所述客户计算机来确定估计样本规模n*。
14.一种数据处理程序，用于在一个数据处理系统中执行，它包括若干软件代码部分，当所述程序在所述计算机上运行时，执行根据前面的权利要求1至11中任何一条的方法。
15.一种存放在一种计算机可用介质上的计算机程序产品，包括计算机可读程序装置，用于当所述程序在所述计算机上运行时，使一台计算机执行根据前面的权利要求1至11中任何一条的方法。
本发明涉及一种数据挖掘技术，用于在众多的N种事务之内确定关联规则，每种事务包括多至p个不同的项目。依据本发明，在众多的N种事务中，根据精度需求确定一个样本规模n。选择样本规模n时，使它至少处于一个估计样本规模n*的量级上。最后，在众多的N种事务中，根据样本规模为n的一个样本，按照关联规则挖掘所用的任何整套方法，使用关联规则作为众多的N种事务的估计关联规则，计算关联规则。
文档编号G06F17/30GK817246
公开日日 申请日期日 优先权日日
发明者弗兰克·比克曼, 罗兰·格伦德, 安德里亚斯·鲁道夫 申请人:国际商业机器公司}