一种扩展的否定关联规则形式及其挖掘算法

摘要

数据挖掘，又称为数据库中的知识发现(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算法具有更高的时间效率。我们的工作将把否定关联规则的相关应用推广到更宽的领域。

目录

文摘

英文文摘

Chapter1Introduction

1.1 What Is Data Mining?

1.2 What Motivated Data Mining?

1.3 Data Mining - on What Kind of Data?

1.3.1 Relational Databases

1.3.2 Data Warehouses

1.3.3 Transactional Databases

1.4 The Patterns that Can Be Mined

1.4.1 Association Rules

1.4.2 Classification and Prediction

1.4.3 Clustering Analysis

1.4.4 Outlier Analysis

1.4.5 Evolution Analysis

1.5 Classification of Association Rules

1.6 Main Contribution

1.7 Organization of the Thesis

Chapter2(Positive) Association Rules

2.1 Formal Statement

2.1.1 Basic Concepts

2.1.2 Definitions

2.2 Typical Mining Methods

2.2.1 Apriori

2.2.2 Variations of the Apriori Algorithm

2.2.3 Frequent Pattern-Growth

3.1 What Is Negative Association Rule?

3.2 Why Negative Association Rule Was Intro-duced?

3.3 Related Work

3.3.1 Form 1 and Mining Method 1

3.3.2 Form 2 and Mining Method 2

3.3.3 Form 3 and Mining Method 3

3.4 Limitations of Related Work

3.4.1 Expressive Power of the Forms

3.4.2 Mining Power

3.4.3 Accuracy

3.4.4 Time Efficiency

3.4.5 Space Efficiency

3.5 Motivation

4.1 Concept and Notation

4.2 Definitions

5.1 Basic Idea

5.2 Why Choose Patricia Tries as Data Structure?

5.3 The AMENAR Algorithm

5.3.1 Phase 1

5.3.2 Phase 2

5.3.3 Phase 3

5.3.4 Phase 4

5.4 Properties of AMENAR

6.1 Experimental Design and Environment

6.2 Datasets

6.3 Experimental Results and Analysis

7.1 Conclusion

7.2 Future Work

Acknowledgements

ATheFP-growth*Algorithm

BTheAMENARAlgorithm

Bibliography

附录

原创性声明和关于学位论文使用授权的声明