论文部分内容阅读
数据挖掘的任务是发现大型数据集中隐藏的、预先未知的知识。关联规则的挖掘是数据挖掘研究的重要问题之一。该问题自1993年被R.Agrawal等人提出以来,一直受到广泛关注和重视。通常,关联规则的挖掘分两步: (1) 挖掘所有的频繁项集; (2) 由频繁项集产生强关联规则。其中第一步的时间复杂度远高于第二步。从频繁项集产生关联规则的方法是简单的,但是可能导致无意义的关联规则的产生。
一些研究者注意到这一问题,提出在产生关联规则时利用提升度判断规则前、后件之间的正相关性,进一步过滤掉一些无意义的规则。但是,这种做法仍然存在两个问题:(1)不能减少挖掘频繁项集的时间开销。(2)不能保证规则前件(后件)中的项是正相关的,当规则的前件或后件内部存在负相关的项时,仍然可能产生无意义的关联规则。
针对以上问题,本文基于数学期望,引进正相关的频繁项集的概念,并给出一种挖掘正相关的频繁项集的算法。本文的算法可以直接在FP-树中挖掘正相关的频繁项集,将正相关性的判断推进到了挖掘频繁项集的过程中。这样,不仅可以大幅度地减少产生频繁项集的数量,显著地提高挖掘频繁项集的效率,而且在由频繁项集产生关联规则时,可以有效地避免产生无意义的关联规则。此外,在挖掘频繁项集时,本文的算法还通过提取公共项,进一步降低了递归地构造条件FP-树的时间开销。在UCI机器学习基准数据集上实验表明,本文算法可以大幅度地减少产生频繁项集的数量,显著地提高挖掘频繁项集的效率,具有很好的性能,对于大型、稠密数据集尤其如此。