论文部分内容阅读
关联规则挖掘是数据挖掘中最活跃的研究方法之一。最早是由Agrawal等人提出的(1993年)。最初提出的动机是针对购物篮分析(Basket Analysis)问题提出的,其目的是为了发现交易数据库(Transaction Database)中不同商品之间的联系规则。交易数据库可以把顾客的相关交易(如所购物品项目等)存储下来。通过对这些数据的智能分析,可以获得有关顾客购买模式的一般性规则。这些规则刻画了顾客的购买行为模式,可以用来指导商家科学地安排进货、库存以及货架设计等。关联规则在其它领域也可以得到广泛讨论,如目录设计、商品广告邮寄分析、追加销售、仓库规划、网络故障分析、市场规则、广告策划、分类设计等。关联知识(Association)反映一个事件和其它事件之间的依赖或关联,关联可分为简单关联、时序(Time Series)关联、因果关联、数量关联等。这些关联并不总是事先知道的,而是通过数据库中数据的关联分析得到的,因而对商业决策具有新价值。 大多数算法得到的关联规则事实上假设其是永远有效的,但是时间是现实世界的重要属性,大容量数据集中的时间属性对用户来说可能是很关键的。用户关心的往往是某一时间区域的数据而不是整个数据,而特定时间区域的数据又可能导致特定的数据间的关联规则。解决这一问题的方法就是在算法中考虑时间因素,因此,数据库中表的字段要至少包括事务号、时态区间和项目序列三个字段。这里的时态区间反映了对应的项目序列发生或被收集的时间范围。关联规则的挖掘可以利用时态约束来进行预处理等工作,可以过滤掉用户不关心的时段上的数据。过滤数据库以减少扫描空间、降低输入输出代价、减少内存需求进而提高挖掘效率的关键。如果数据库中的每个元组均有其时态约束的规则,那么就可以更好的描述客观情况,因而更有价值。 目前,大部分的工作都集中在时间并∪T的范围内进行考虑的,显然和时间并∪T相关的所有事务中的所有项目在时间并∪T中都是必然发生的,但在时间交∩T中却不一定,换言之,在时间并∪T中,如果事务中某些项目的组合构成了频繁项目集,但在时间交∩T中至少包含该频繁项目集的概率和P却不同。根据专家知识给此概率和一个阈值θgt,当P>=θgt时,其P所在的时间交∩T就称为黄金时间段。假设把黄金时间段的思想应用到超市的话,那么在时间交∩T这些黄金时间段内,商家应根据不同的黄金时间段内出现的极大的频繁商品的不同而有的放矢的更准确的准备充足的货源,以供顾客购买。很显然,对于黄金时间段的研究也是一个很有意义的课题。 由于计算机在处理海量的数据项的过程中,将是对内存的极大考验,而通过已经学过的极大团的特点,将关联性最强、项目之间最容易产生极大有序频繁项目集的项生成一个极大团,这样就可以把原来海量的数据项进行了有效的划分,缓解了内存不足的问题。 本研究是将时序逻辑、极大团和数据挖掘的知识有效的结合在一起,针对上述问题提出了9个算法,并给出了算法复杂度的分析。主要成果与创新:①在时间并∪T内求极大有序频繁项目集;②求至少包含出现在时间并∪T内的那些极人有序频繁项目集同时发生在相应的时间交∩T的概率