论文部分内容阅读
数据挖掘，又称为数据库中的知识发现(KDD)，出现于“信息丰富而知识贫乏”的二十世纪八十年代后期。之后，倍受关注，并得到广泛研究。
关联规则作为数据挖掘中的一种重要模式，在1997年由R.Agrawal等人首次提出[1]，其对应的挖掘算法Apriori[2]也被提出。最初提出的关联规则是不带联结词“”的正关联规则，而且目前大部分工作都集中在正关联规则的研究上。近来，否定关联规则挖掘引起人们的注意，并证明是有用的。
1997年，S.Brin等人在[5]中首次提及否定关联。据我们所知，自那以后人们提出了三种有代表性的否定关联规则形式，并提出了三种对应的挖掘方法。但这三种形式都不够一般化，比如它们都不能表达形如“α∧b∧()(c∧d)→e∧()f∧()(g∧h∧i)”的规则形式。而且，三种挖掘方法在挖掘能力、精确性和效率上存在一些缺陷。
本文提出了一种扩展的否定关联规则形式，并提出了一种相应的挖掘算法AMENAR以挖掘扩展的否定关联规则.这种扩展形式比以往提出的形式更一般化并具有更强的表达能力，因为以往的形式都是扩展形式的特例。AMENAR是一种基于内存的算法。我们选取一种高度压缩的数据结构Patriciatire将原始数据库存放在内存中。整个挖掘过程在内存中的Patriciatrie上执行，而且只需扫描两遍数据库。另外，AMENAR算法删除了有冲突的规则和两类冗余规则.我们将AMENAR算法和以往的两种算法运行在两个数据集上。实验结果表明：AMENAR算法在挖掘能力、精确性、空间效率上都优于以前的挖掘方法。而且，当用在稀疏、简单数据库上，当minsup值高到一定程度时，AMENAR算法具有更高的时间效率。我们的工作将把否定关联规则的相关应用推广到更宽的领域。