第三章 周期性关联规则的挖掘
在数据挖掘的研究领域中,关联规则挖掘的研究开展得比较积极和深入。在R.Agrawal等人提出了关联规则的挖掘问题后,该问题就成为众多研究人员关注的焦点,许多学者提出了各种各样的挖掘算法。但绝大多数算法都是将事务数据库作为一个整体,而没有考虑数据中时间属性的影响。所以,这些挖掘算法都很难解决如下的问题:通过对事务数据库的扫描,发现“面包和牛奶”在整个事务数据库中的支持度小于用户设定的最小支持度阈值,很显然原有的关联规则挖掘算法在频繁项集生成过程中将因为“面包和牛奶”的支持度小于最小支持度阈值而忽略,因而也就不可能发现“面包和牛奶”两者之间潜在的某种关联关系。实际上,如果我们重点对每天早上8:00—9:00的时间单元中的数据进行考察,就会发现“面包→牛奶”在这一时间单元里的支持度和置信度要远大于用户设定的最小支持度和最小置信度阈值,也就是说在每天早上8:00—9:00这样的时间单元中是一条强规则。这样的发现是相当有意义的。
如果对事务数据库根据数据的时间属性进行不同的划分并分别进行分析和研究,则可以发现事务数据库中许多潜在的关联关系。比如对商场的销售数据按月划分后进行挖掘,也许就可以发现商品的销售会因为季节的变化而产生某种周期性的变化。所以在合适的时间单元内对数据进行分析,往往会发现某些事务经常在一些时间单元内周期性地重复发生,而在另外的时间单元却很少发生的某种周期性规律。换句话说,当数据包含时间属性时,也许会存在某种周期性的变化规律。显然,这样的研究将有助于确定销售趋势和用户需求模式的变化,从而为决策者提供决策依据,使决策者能够及时调整经营策略以适应市场的需要。
周期性关联规则挖掘是对关联规则挖掘研究的一个扩展,它主要是揭示数据随时间的变化呈周期性变化的规律。Ozden等人讨论了固定周期条件下的周期性关联规则的挖掘及可变周期条件下的关联规则挖掘问题。在此基础上,我们重点对固定周期和可变周期两种情况下的周期性关联规则挖掘进行深入研究,提出了针对这两种情况的周期性关联规则挖掘的高效算法。算法结合了支持度剪枝和周期性剪枝技术,测试结果表明算法具有较高的挖掘效率。
一、周期性关联规则概念
假定事务数据库中所有的事务记录都已经包含了时间标记,而用户已经根据实际需要确定了对事务数据库的时间单元划分。另外,为了简单起见,我们认为各时间单元之间是相互独立的,我们不讨论时间单元之间相互重叠以及时间单元的自动划分等问题。
假如在一系列有一定周期间隔的时间单元内,一条关联规则的发生次数与最大周期数之间的比率大于用户设定的最小周期性支持度,则称该规则是周期性关联规则。
为了能处理周期性关联规则,假定事务数据库DB中的数据已经根据其时间属性划分为n个互不相交的时间标记的数据子集,每个数据子集对应于某一时间单元内的事务。我们记第i个时间单元为ti,其中0≤i<n,则ti相当于时间间隔[i×t,(i+1)×t],t为时间单位。对应每个时间单元ti,用dti表示在该时间单元内事务的集合,我们称dti为对应时间单元ti的数据子集。所以事务数据库可以表示为dti的序列:db=dt1,dt2,dt3,…,dtn,db为事务数据库本身或其子集。
对应数据子集dti中的一条关联规则具有如下形式其中如果数据子集dti中有s%的事务包含X∪ Y,则说明数据子集dti中关联规则X→Y的支持度为s%;如果数据子集dti中包含X的事务中有c%的事务同时也包含Y,则说数据子集dti中关联规则的置信度为c%,表示为
可以用数对(l,o)来表示一个时间周期,其中l为周期间隔的长度,o是偏移量,表示循环发生的起始时间单元,0≤o<l。对于给定的时间周期(l,o),如果对时间单元ti,有imodl=o,则称时间单元ti在周期(l,o)中。当时间单元ti在周期(l,o)中时,其对应的数据子集dti,也称其在周期(l,o)中,将所有在周期中的数据子集记为:db(l,o)。于是有:db(l,o)={dt×l+o|k∈Z,0≤k<n/l},记周期(l,o)中的第k个时间单元对应的数据子集记为
一条关联规则在周期(l,o)中的周期性支持数为Y).Sup=|{k|0≤k<|n/l|而且是一条关联规则}|,其中l为周期间隔的长度,o是偏移量。关联规则在周期(l, o)中的周期性支持度为SupportSup/|n/l|。如果一条关联规则在周期(l,o)中的周期性支持度大于用户设定的最小周期性支持度,则称这条关联规则是周期性关联规则,周期为(l,o)。在数据库中发现周期性关联规则就是在给定的时间周期或周期范围内,找出所有满足最小周期性支持度的关联规则。
与周期性关联规则相对应,还可以定义周期性频繁项集。如果项集在周期(l,o)中的周期性支持度大于用户设定的最小周期性支持度,则我们称该项集是周期性频繁项集。
周期性关联规则的一个典型例子就是前面提到的这样的关联规则。规则在每天早上的8:00—9:00时间单元内满足最小支持度和最小置信度。如果以小时为时间单位,则我们称关联规则具有周期c=(24,8)。为了处理上的方便,我们可以用0和1这样的二进制序列来代表一条关联规则在一系列时间单元中的成立与否,用1表示该规则在当前时间单元内成立,而0则表示在当前时间单元内该规则不成立。例如用001100010101这样的二进制序列来表示关联规则在不同时间单元内的成立与否,很显然,该规则在时间单元dt2、dt3、dt7、dt9和dt11成立。我们可以确定该规则具有周期c=(4,3),因为该规则每隔四个时间单元,且在第三个时间单元时该规则均成立。我们也可以将周期c=(4,3)表示成0001。与关联规则一样,我们也可以定义频繁项集的周期性序列。用1表示该项集在当前时间单元内是频繁项集,用0表示该项集在当前时间单元内为弱项集。
二、固定周期的周期性关联规则挖掘
由于现在绝大多数的关联规则挖掘算法都是将事务数据库看做一个整体,而没有考虑时间属性的影响,因此现有的关联规则挖掘算法不能够直接应用于周期性关联规则的挖掘。这里我们首先讨论在给定周期(l,o)情况下的周期性关联规则的发现问题,然后再对周期在一定范围内变化时的周期性关联规则挖掘问题进行研究。假定事务数据库DB已经根据数据的时间属性划分为n个互不相交的数据子集dti,其中0≤i<n。
一种最直接的方法就是利用现有的关联规则挖掘算法分别计算出各时间单元内的关联规则,然后用统计或模式匹配的方法来发现周期性关联规则。各时间单元内的关联规则的挖掘问题可以用第二章中的关联规则挖掘算法进行挖掘。
设给定的周期为(l,o),各个时间单元内的关联规则挖掘问题可分为两个步骤来完成:
(1)扫描各数据子集并生成其中所有的频繁项集;
(2)根据(1)得到的各数据子集中的频繁项集,生成所有满足最小置信度的关联规则。
当每个时间单元都完成关联规则的挖掘后,我们需要利用统计方法来确定这些关联规则的周期性属性。定义各符号如表3-1所示。
表3-1 固定周期关联规则挖掘用到的符号和含义
1.算法FCARM_1(Fixed Cycle Association Rule Mining)
输入:数据子集dti,其中0≤i<n
最小支持度Smin、最小置信度Cmin、最小周期性支持Fmin
用户给定的时间周期(l,o)
输出:所有周期性关联规则CR
算法FCARM_1首先初始化周期(l,o)对应的周期性关联规则候选集CR,然后调用LargeItemset_Gen函数生成周期(l,o)中各数据子集中所有的频繁项集L(dti),使LargeItemset_Gen可以利用现有的关联规则挖掘算法。我们这里以Apriori算法作为频繁项集生成算法来生成各数据子集dti中频繁项集。Apriori算法从长度为1的项集开始,不断地循环。在每次循环时首先构造一个候选频繁项集,然后扫描数据库并计算候选项集中各元素的支持数,在循环过程中利用频繁项集的任意子集也必是频繁项集的剪枝原则对候选项集进行剪枝(称为支持度剪枝),从而可以大幅度地减少需要进行支持数计数的候选项集的大小,有效地提高算法的挖掘效率。LargeItemset_Gen算法执行后得到各数据子集dti中的大项集L(dti),然后调用Rules_Gen函数生成各数据子集dti中的关联规则R(dti),Rules_Gen函数以LargeItemset_Gen函数返回的频繁项集为参数,返回的是对应数据子集dti中的关联规则。我们利用ap_genrules来生成各数据子集dti中的关联规则。在生成各数据子集dti中的关联规则之后,我们对这些关联规则分别进行周期性支持数计数,满足用户设定的最小周期性支持度的关联规则就是周期性关联规则,周期为(l,o)。
实际上,对db(l,o)中每个数据子集的关联规则进行周期性支持数计数是没有必要的。因为如果某条关联规则在周期(l,o)的前|db(l,o)|×(1-Fmin)+1个数据子集中的周期性支持数小于l,则我们可以确定该规则在周期(l,o)中不可能成为周期性关联规则。同样的,在统计了db(l,o)中的前m个数据子集后,如果关联规则在前m个数据子集的周期性支持数小于m-|db(l,o)|×(1-Fmin),则该规则在(l,o)中也不可能是周期性关联规则。所以我们可以通过检查候选集CR中各元素的周期性支持数对周期性关联规则候选集进行剪枝,这一剪枝方法称为周期性剪枝。于是,可以将算法FCARM_l进行改进得到算法FCARM_2。
2.算法FCARM_2(Fixed Cycle Association Rule Mining)
输入:数据子集dti,其中0≤i<n
最小支持度Smin、最小置信度Cmin、最小周期性支持度Fmin
用户给定的时间周期(l,o)
输出:所有周期性关联规则CR
算法FCARM_2利用LargeItemset_Gen和Rules_Gen函数发现db(l,o)中所有数据子集dti中的大项集和关联规则,然后初始化周期db(l,o)的周期性关联规则候选集。对于db(l,o)中的前|db(l,o)|×(1-Fmin)+l个数据子集中的关联规则,如果候选集CR中没有当前规则,则将其加入到候选集中,并设该规则的周期性支持数为1,否则该规则的周期性支持数加1。对于db(l,o)中其余的数据子集,检查周期性关联规则候选集中的关联规则在其中是否成立,如果成立则该规则的周期性支持数加1,否则检查该规则的周期性支持数,如果该规则的周期性支持数小于|i/l|-|n/l|×(1-Fmin),其中i为当前的数据子集,则将其从周期性关联规则候选集中删除。最后候选集中保留的关联规则都将满足最小周期性支持度,因而都是周期性关联规则,周期为(l,o)。
在算法FCARM_1和算法FCARM_2中,算法的执行时间主要消耗在每个数据子集中候选大项集的支持数计数上,因此可以利用周期性剪枝技术来减少候选大项集的大小,从而减少运行时间,进一步提高算法的挖掘效率。其实,我们可以利用某条关联规则在周期(l,o)的前|db(l,o)|×(1-Fmin)+1个数据子集中的周期性支持数小于1,则该规则在周期(l,o)中就不可能成为周期性关联规则的性质来提高周期性关联规则的发现效率:首先找出db(l,o)前|db(l,o)|×(1-Fmin)+1个数据子集中出现过至少一次的关联规则,并根据这些关联规则生成周期性关联规则候选集,然后在其余的数据子集中验证候选集中的各规则的周期性支持度,支持度大于用户设定的最小周期性支持度的关联规则就是周期性关联规则。可见,根本不需要产生所有数据子集中的关联规则或是大项集。由于Fmin的值一般都比较大,所以我们只需要生成小部分数据子集中的大项集或关联规则,就可以确定所有的周期性关联规则或周期性大项集,挖掘效率的提高是显而易见的。
3.算法FCARM_3(Fixed Cycle Association Rule Mining)
输入:数据子集dti,其中0≤i<n
最小支持度Smin、最小置信度Cmin、最小周期性支持度Fmin
用户给定的时间周期(l,o)
输出:所有周期性关联规则CR
算法FCARM_3首先找出db(l,o)中前|db(l,o)|×(1-Fmin)+1个数据子集中所有的关联规则,将这些规则及其周期性支持数存入周期性关联规则候选集中,然后扫描其余的数据子集,检查候选集中的关联规则在这些数据子集中是否成立,每次扫描一个数据子集后就进行周期性剪枝。当所有数据子集的检查完成后,候选集中所有的关联规则就都是周期性关联规则,周期为(l,o)。与算法FCARM_2相比,算法FCARM_3由于不需要计算所有数据子集中的频繁项集和关联规则,从而减少了在频繁项集计算上的时间消耗,因而效率比算法FCARM_2要高很多。
性质3.1 如果关联规则X→Y具有周期(l,o),则项集X和X ∪Y在周期(l,o)中必是频繁项集,而且它们的周期性支持度必大于最小周期性支持度。根据周期性关联规则和周期性频繁项集的定义,这是很显然的。
性质3.2 如果频繁项集X具有周期(l,o),则其任意子集在周期(l,o)中也为频繁项集,且其周期性支持度一定大于最小周期性支持度。
利用性质3.1和性质3.2,我们可以对候选周期性大项集进行周期性剪枝。由于一个数据子集中产生频繁项集的时间主要消耗在频繁2-项集的计算上,在大多数情况下,长度为2的候选集都十分庞大,所以如果能够减小候选2-项集的大小就可以显著地减少算法的执行时间。(www.xing528.com)
由于我们只关心周期性的频繁项集,所以根本不必知道数据子集中所有的频繁项集。根据性质3.2,如果频繁k-项集是周期性频繁项集,则其k-1子集也必是周期性频繁项集。因此,可以首先找出所有长度为k-1的周期性频繁项集,用LargeItemset_Gen函数生成长度为k的周期性频繁k-项集的候选集,然后扫描所有数据子集并得到长度为k的周期性频繁项集。因为周期(l,o)中长度为k-1的周期性频繁项集中元素的数量一般要少于长度为k-1的频繁项集中的元素的数量,所以用周期(l,o)中长度为k-1的周期性频繁项集产生周期性频繁k-项集的候选集比直接用长度为k-1的频繁项集产生的候选集要小得多。在扫描数据子集时,使用这个候选集将减少支持数计数时间,从而提高了算法挖掘的效率。
基于这样的想法,可以得到算法FCARM_4。
4.算法FCARM_4(Fixed Cycle Association Mining)
输入:数据子集dti,其中o≤i<n
最小支持度Smin、最小置信度Cmin、最小周期性支持度Fmin
用户给定的时间周期(l,o)
输出:所有周期性关联规则CR
在周期(l,o)中的前|db(l,o)|×(1-Fmin)+1个数据子集中发现所有长度为1的频繁项集,将它们及周期性支持数加入到候选周期性频繁1-项集中。对于其余的数据子集,检查候选周期性频繁1-项集中的元素在各数据子集中是否是频繁项集。如果是频繁项集,则该元素的周期性支持数加1,否则则对其进行周期性剪枝。当所有的数据子集完成扫描后得到周期性频繁1-项集。
利用LargeItemset_Gen函数和周期性频繁1-项集生成所有长度为k的周期性频繁k-项集的候选集。对周期(l,o)中的前|db(l,o)|×(1-Fmin)+1个数据子集,检查候选集中元素是否在数据子集中为频繁项集,如果为频繁项集则该元素的周期性支持数加1,否则则对其进行周期性剪枝。当所有的数据子集完成扫描后得到周期性频繁k-项集,重复循环直到不能生成新的候选周期性频繁项集时算法结束。
利用前面得到的周期(l,o)中的所有的周期性大项集和Rules_Gen函数可以生成各数据子集中的关联规则,然后再对它们进行周期性剪枝就可以得到最终所有的周期性关联规则。
我们通过模拟数据生成算法生成测试数据。为了强调实际情况下,有周期性关联规则也有非周期性关联规则的事实,测试数据生成过程中不是用同一个L来产生所有的数据子集,而是为每一个数据子集产生一个L,并用相似性参数u(百分比)来刻画一个周期中数据子集的相似性。我们首先产生一个有L/u个可能的频繁项集组成的候选集,然后每次从中选出L个项集来产生数据子集。一个项集被选中的可能性与其产生时得到权值有关。当u值越大时,用于产生各个数据子集的项集的集合就越相似,数据子集也就越相似,这也意味着发现的周期性关联规则会越多。所有的参数含义如表3-2所示。
表3-2 测试数据相关符号及含义
在测试过程中,我们使用P4 3.0GHz、2G内存,Windows XP的计算机为测试的平台,使用Apriori算法作为基本的关联规则发现算法。为了提高匹配速度,采用hash树存储候选项集。在进行周期性频繁项集和周期性关联规则的支持数统计时采用的是哈希表的结构。
(1)时间单元总数变化时性能的改变
当周期中数据子集的数量从10变到60时,算法FCARM_1、FCARM_2、FCARM_3、FCARM_4所用的时间都呈线性增加。当最小周期性支持度为0.85时,算法FCARM_1的执行时间为算法FCARM_3和算法FCARM_4执行时间的6~7倍,比算法FCARM _2执行时间多20%左右。这是因为在算法FCARM_3和FCARM_4中只有大约15%的数据子集被用来产生频繁项集,其余的数据子集只被扫描一次。扫描一个数据子集的时间比产生频繁项集使用的时间要短得多,所以算法FCARM_3和FCARM_4整体时间的花费大大减少。
在测试中,算法FCARM_4的执行时间比算法FCARM_3要稍少一些,这是因为算法FCARM_4对长度为l的周期性频繁1-项集进行周期性剪枝,利用周期性频繁1-项集生成候选2-项集,这样的候选集要小于直接利用频繁1-项集所生成的候选2-项集,所以挖掘的速度有了一定程度的提高。
图3-1 时间单元总数变化时的执行情况
(2)最小周期性支持度发生变化时的执行情况
最小周期性支持度逐渐增大时,对算法FCARM_1没有什么影响,而算法FCARM_2相应地有所减少,但减小得十分有限。算法FCARM_3和算法FCARM_4的执行时间都将随着最小周期性支持度的增大而相应较快地减少,这是因为用于产生周期性候选频繁项集的数据子集的个数减少了。
三、可变周期的周期性关联规则挖掘
在前一小节中我们讨论了在给定周期(l,o)情况下周期性关联规则的发现算法,但由于周期(l,o)是由用户事先给定的,当周期(l,o)发生变化时,则必须重新对各数据子集中的关联规则进行周期性判定,这显然是极为耗时和不合理的。如果能够在用户感兴趣的最小周期间隔lmin和最大周期间隔lmax之间发现所有的周期性关联规则,将会十分有意义。很明显,在已知周期取值范围的情况下,要发现所有周期性关联规则的最简单方法就是利用前述固定周期的周期性关联规则挖掘算法对每个可能的周期进行挖掘,但是这样的结果就需要对数据子集进行多次扫描,而没有充分利用每个数据子集的扫描结果,所以显然是低效率和不可取的。
图3-2 最小支持度变化时的执行情况
如果我们只需要对各数据子集进行一次扫描,在对各候选周期进行周期性判断时,不需要再次扫描各数据子集,就可以大大地提高周期性关联规则挖掘的效率。算法过程简单如DCARM_1所示。
为了描述方便,定义各符号如表3-3所示。
表3-3 可变周期的周期性关联规则挖掘相关符号及含义
1.算法DCARM_1(Dynamic Cyclic Association Rules Mining)
输入:数据子集dti,其中0≤i<n
最小支持度Smin、最小置信度Cmin、最小周期性支持度Fmin
用户感兴趣的最小周期间隔lmin和最大周期间隔lmax
输出:所有周期性关联规则RCset
//初始化生成在最小周期间隔lmin和最大周期间隔lmax所有可能的周期
在算法DCARM_1中由于需要计算所有数据子集中的频繁项集和关联规则,另外在周期性判断过程中仅利用了统计的方法,而且也没有采用任何剪枝的手段,所以算法DCARM_1的时间耗费是十分惊人的。
其实可以利用前一小节中的周期性剪枝技术来提高周期性关联规则的挖掘效率。如下面的算法DCARM_2所示:我们首先生成前k(k=max(|n/lmin|×(1-Fmin))+lmin,|n/lmax|×(1-Fmin)+lmax)数据子集中的候选周期性1-项集,然后在其余的数据子集中计算这些候选周期性1-项集的周期性支持数,并进行周期性剪枝。在得到周期性1-项集后,在前k个数据子集中生成所有的候选周期性频繁项集,然后在其余的数据子集中计算候选项集中各元素的周期性支持数并进行周期性剪枝,最后得到所有周期的周期性关联规则。
由于在频繁项集的支持数计算过程中,候选2-项集往往十分庞大,所以候选2-项集的支持数计数时间的消耗是最多的。算法DCARM_2在生成周期性2-项集的过程中,充分利用了前面得到的周期性1-项集的结果,从而缩小了周期性候选2-项集,所以算法的效率有较大程度的提高。
2.算法DCARM_2(Dynamic Cyclic Association Rules Mining)
//按周期进行归并,得到每个可能周期对应的大1-项集集合
与DCARM_1相比,DCARM_2算法只需要计算部分数据子集中的周期性频繁项集,然后充分利用周期性剪枝技术进行剪枝,因此算法的效率比DCARM_1有较大程度的提高。
算法DCARM_1需要计算出每个数据子集中的频繁项集和关联规则,然后利用统计方法计算各候选元素的周期性支持数,而没有采用周期性剪枝技术,所以算法的时间消耗是相当可观的。与DCARM_1算法相比,算法DCARM_2利用了算法FCARM_4中的剪枝技术,在候选周期性频繁项集的生成过程中,由于候选周期性2-项集的大小最为可观,所以算法在候选周期性2-项集中元素的支持数计算上将消耗大量的时间。如果我们能够减小候选周期性2-项集的大小,显然就可以较大程度地缩减算法的执行时间。由于周期性频繁1-项集中元素的数量要远少于频繁1-项集中元素的数量,周期性频繁1-项集与频繁1-项集中元素数量的比值同周期性支持度有关,一般地,周期性支持度的值往往较大,所以在频繁1-项集中只有很少的一部分项集满足周期性支持度的约束。因此可以利用周期性频繁1-项集所生成候选周期性2-项集,这样得到的候选项集显然要小于直接利用频繁1-项集所生成的候选项集,在后续的候选周期性k-项集生成时也采用同样的方法,即利用周期性(k-1)-项集生成候选周期性k-项集。由此,算法DCARM_2在候选项集支持数的计数上所消耗的时间将会有较大程度的减少,挖掘效率的提高是显而易见的。
四、拟周期的周期性关联规则挖掘
在现实生活中,周期性现象是广泛存在的。周期性现象以及多个事物周期之间的相互影响现象,广泛存在于自然界和日常生活中。如果人们能够及时发现事物的某种周期性规律,将会避害趋利,获得较好的社会效益和经济效益。但是,也有很多的周期性现象并不是数学上严格意义的周期现象。在许多时候,周期性现象往往在时间上发生了不规则的伸缩,在幅度上也叠加了干扰信号,这就很难利用前面的固定周期和可变周期性的方法进行处理。我们称这种情况为拟周期现象。目前对于拟周期的现象进行挖掘的研究仍然比较少见。
图3-3 超市销售拟周期实例分析
我们以超市的销售情况为例,图3-2为超市两个不同年度某一商品的销售额历史数据,x轴为月份,y轴为销售额(万元)。从图中可以看出该商品的销售曲线有五种势态:峰(如2009.2),谷(如2009.5)、上升(如2009.8)、下降(如2009.4)和边界(如2009.1)。从曲线可以看出存在一定的噪声和趋势惯量,如2010.4的销售量低于2010.5,但差值不超过2,我们可以设这样的波动对整个发展态势没有什么影响,视为可以忽略的噪声。另外,从图中还可以峰(P1=2009.9,P3=2006.8)、谷(V1=2009.5,V3=2010.6)之间的间隔不同,从P1到P3间隔11个月,从V1到V3间隔13个月,可知时间轴上有不均匀的伸缩。我们可以从峰谷的变化情况和整个曲线在某一时间段内的变化趋势中发现潜在的规则和知识。
由于缺乏成熟的拟周期的规则挖掘算法和噪声数据的影响,使得拟周期规则的挖掘方面还存在不少的困难。由于拟周期现象更加贴近客观现实,所以对这一现象的研究将更有价值和意义。
免责声明:以上内容源自网络,版权归原作者所有,如有侵犯您的原创版权请告知,我们将尽快删除相关内容。