没有合适的资源?快使用搜索试试~ 我知道了~
使用约束改进数据挖掘算法.doc
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 37 浏览量
2024-04-02
14:31:20
上传
评论
收藏 2.6MB DOC 举报
温馨提示
![preview](https://dl-preview.csdnimg.cn/89070975/0001-db035d00ec8b44931588b171c423209f_thumbnail-wide.jpeg)
![preview-icon](https://csdnimg.cn/release/downloadcmsfe/public/img/scale.ab9e0183.png)
试读
78页
使用约束改进数据挖掘算法.doc
资源推荐
资源详情
资源评论
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![thumb](https://img-home.csdnimg.cn/images/20210720083646.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![thumb](https://img-home.csdnimg.cn/images/20210720083646.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![](https://csdnimg.cn/release/download_crawler_static/89070975/bg1.jpg)
The Open University of Israel
Department of Mathematics and Computer Science
The Computer Science Division
IMPROVING DATA MINING ALGORITHMS USING
CONSTRAINTS
By
Shai Shimon
ID 028455863
Email shaishimon@gmail.com
Cell 0526-126207
Prepared under the supervision of Professor Ehud Gudes
Feb 2012
![](https://csdnimg.cn/release/download_crawler_static/89070975/bg2.jpg)
2
TABLE OF CONTENTS
LIST OF FIGURES..................................................................................................................................................................3
LIST OF TABLES ...................................................................................................................................................................4
1 ABSTRACT AND INTRODUCTION...........................................................................................................................5
1.1 ABSTRACT ................................................................................................................................................................5
1.2 INTRODUCTION .......................................................................................................................................................6
2 BASIC CONCEPTS ......................................................................................................................................................8
2.1 INTRODUCION........................................................................................................................................................12
2.2 APRIORI- FAST ALGORITHMS FOR MINING ASSOCIATION RULES [1] ......................................................................12
2.3 FP-TREE ALGORITHM [8] .....................................................................................................................................19
3 PAPERS SURVEY ......................................................................................................................................................34
3.1 USING CONSTRAINTS ....................................................................................................................................34
3.1.1 INTRODUCTION AND MOTIVATION........................................................................................................34
3.1.2 MINING FREQUENT ITEMSETS WITH CONVERTIBLE CONSTRAINTS [9] ...................................34
3.1.2.1 Introduction..............................................................................................................................................................34
3.1.2.2 Convertible constraints - motivation ....................................................................................................................35
3.1.3 MINING ASSOCIATION RULES WITH ITEM CONSTRAINTS [10].....................................................37
3.1.3.1 Abstract....................................................................................................................................................................37
3.1.3.2 Introduction..............................................................................................................................................................37
3.1.3.3 Algorithms................................................................................................................................................................37
3.1.3.4 Tradeoffs..................................................................................................................................................................38
3.1.3.5 Conclusions.............................................................................................................................................................38
3.1.4 EXAMINER OPTIMIZED LEVEL-WISE FREQUENT PATTERN MINING WITH MONOTONE
CONSTRAINTS ALGORITHM [4] .............................................................................................................................39
3.1.4.1 Abstract....................................................................................................................................................................39
3.1.4.2 Introduction..............................................................................................................................................................39
3.1.4.3 Definitions................................................................................................................................................................40
3.1.4.4 ExAMiner algorithm................................................................................................................................................41
3.1.4.5 Flowchart of exaMiner ...........................................................................................................................................43
3.1.4.6 ExaMiner algorithm example................................................................................................................................44
3.1.4.7 Experiments ............................................................................................................................................................53
3.1.5 FP-BONSAI ALGORITHM [5]......................................................................................................................56
3.1.5.1 Introduction..............................................................................................................................................................56
3.1.5.2 FP-bonsai algorithm...............................................................................................................................................57
3.1.5.3 FP-Bonsai algorithm example ..............................................................................................................................58
3.1.5.4 Disadvantage ..........................................................................................................................................................63
3.1.5.5 Experiments ............................................................................................................................................................64
3.1.5.6 Summary .................................................................................................................................................................65
3.2 SHORT PAPERS SURVEYS .....................................................................................................................................65
4 IMPLEMENTAION.......................................................................................................................................................70
5 SUMMARY AND CONCLUSIONS ...........................................................................................................................74
6 REFERENCES.............................................................................................................................................................75
![](https://csdnimg.cn/release/download_crawler_static/89070975/bg3.jpg)
3
LIST OF FIGURES
Figure 2.1.1-1
pass execution times of Apriori and AprioriTId
16
Figure 2.1.1-2
Execution times for decreasing minimum support (max potentially large itemset is 2
17
Figure 2.1.1-3
Execution times for decreasing minimum support (max potentially large itemset is 4
18
Figure 2.1.1-4
Execution times for decreasing minimum support (max potentially large itemset is 6
18
Figure 2.1.1-5
FP grows example
26
Figure 2.1.1-6
FP grows example for p (1)
26
Figure 2.1.1-7
FP grows example for p (2)
27
Figure 2.1.1-8
FP grows example for m (1)
27
Figure 2.1.1-9
FP grows example for m (2)
28
Figure 2.1.1-10
FP grows example for am
28
Figure 2.1.1-11
FP grows example for cam and fam
29
Figure 2.1.1-12
FP grows example for cam and cm
29
Figure 2.1.1-13
FP grows example for cam and fm
30
Figure 2.1.1-14
FP grows example results
30
Figure 2.1.1-15
FP tree algorithm experiment –Run time ,support threshold
32
Figure 2.1.1-16
FP grows algorithm experiment –Transactions number with threshold=1.5%
32
Figure 3.1.4-1
ExAMiner0
43
Figure 3.1.4-2
ExAMiner1 & ExAMiner2
44
Figure 3.1.4-3
ExaMiner experiment Data Reduction Rate (min_sup = 1100)
54
Figure 3.1.4-4
ExaMiner experiment Data Reduction Rate (min_sup = 500)
54
Figure 3.1.4-5
ExaMiner experiment Run time synthetic (min_sup =1200)
55
Figure 3.1.4-6
ExaMiner experiment Run time synthetic (sum(prices) > 2800)
56
Figure 3.1.5-1
FP Bonsai Examiner experiment (BMS-POS) (1)
64
Figure 3.1.5-2
FP Bonsai Examiner experiment (BMS-POS) (2
65
Figure 4-1
Application window – main panel
72
Figure 4-2
Application window – FP tree result panel
73
![](https://csdnimg.cn/release/download_crawler_static/89070975/bg4.jpg)
4
LIST OF TABLES
Table 2-1
Market-Basket transactions
8
Table 2-2
Convertible anti-monotone
9
Table 2-3
Convertible monotone
10
Table 2-4
strongly convertible constraints
11
Table 2.1.1-1
FP tree algorithm example Tid, item, and frequency (1)
22
Table 2.1.1-2
FP tree algorithm example Tid, item, and frequency (2)
22
Table 2.1.1-3
FP tree algorithm example Tid, item, and frequency (3)
23
Table 2.1.1-4
FP tree algorithm example Tid, item, and Header table (1)
23
Table 2.1.1-5
FP tree algorithm example Tid, item, and Header table (2)
24
Table 2.1.1-6
FP tree algorithm example Tid, item, and Header table (3)
24
Table 2.1.1-7
F tree algorithm example Tid, item, and Header table (4)
27
Table 2.1.1-8
FP tree algorithm example Tid, item, and Header table (5)
27
Table 2.1.1-9
FP tree algorithm experiment – Synthetic data set
31
Table 3.1.2-1
Transaction Id AND transaction
36
Table 3.1.2-2
Frequent itemsets with support threshold
36
Table 3.1.4-1-A
ExaMiner 0
43
Table 3.1.4-1-B
ExaMiner 1
44
Table 3.1.4-2
ExaMiner example level one (1)
45
Table 3.1.4-3
ExaMiner example level one (2)
45
Table 3.1.4-4
ExaMiner example level one (3)
46
Table 3.1.4-5
ExaMiner example level one (4)
47
Table 3.1.4-6
ExaMiner example level one (5)
48
Table 3.1.4-7
ExaMiner example level one (6)
49
Table 3.1.4-8
ExaMiner example level two (1)
49
Table 3.1.4-9
ExaMiner example level two (2)
50
Table 3.1.4-10
ExaMiner example level two (4)
50
Table 3.1.4-11
ExaMiner example level two (5)
51
Table 3.1.4-12
ExaMiner example level two (7)
52
Table 3.1.4-13
ExaMiner example level two (7)
52
Table 3.1.4-14
ExaMiner example level two (7)
53
Table 3.1.5-1
FP Bonsai example - item, value table
58
Table 3.1.5-2
FP Bonsai example- Tid ,items table
59
Table 3.1.5-3
FP Bonsai example
�
-pruning – (constraint check)
59
Table 3.1.5-4
FP Bonsai example Run
�
-pruning (Support check)
60
Table 3.1.5-5
FP Bonsai example
�
-pruning (1)
60
Table 3.1.5-6
FP Bonsai example Run
�
-pruning (2)
61
Table 3.1.5-7
FP Bonsai example
�
-pruning (3)
61
Table 3.1.5-8
FP Bonsai example Run
�
-pruning (4)
62
Table 3.1.5-9
FP Bonsai example
�
-pruning (5)
62
Table 3.1.5-10
FP Bonsai example results
62
Table 4-1
Transactions table
71
Table 4-2
Items and prices
71
Table 4-3
Experiments results
71,72
![](https://csdnimg.cn/release/download_crawler_static/89070975/bg5.jpg)
5
1 ABSTRACT AND INTRODUCTION
1.1 ABSTRACT
The purpose of data mining is to identify and predict patterns, trends and relationships in
data. The main steps in data mining process are:
Defining the problem, preparation of information, data analysis, evaluation of the results,
displaying the results.
In this work I'll present a number of data mining algorithms using association rules. First I'll
present the basic algorithms (Apriori Algorithm and FP Tree) and then we'll discuss
algorithms with constraints. We will present the algorithms with constraints in detail, and also
we shall discuss the differences between them.
In fact this work will focus on data mining algorithms with constraints. We will focus on the
importance of constraints in data mining, on their use, and explore different types of
constraints and effective methods of data mining algorithms. As it's well known, since the size
of data mining results may sometimes be very large, using constraints help the user find the
desired information and improves the system performance. This work will focus on certain
types of constraints, and algorithms that were built for them. Specifically, the algorithms that
we will review are:
✓ MINING FREQUENT ITEMSETS WITH CONVERTIBLE CONSTRAINTS[10]
✓ MINING ASSOCIATION RULES WITH ITEM CONSTRAINTS [11]
✓ EXAMINER OPTIMIZED LEVEL-WISE FREQUENT PATTERN MINING WITH MONOTONE
CONSTRAINTS ALGORITHM [4]
✓ FP-BONSAI ALGORITHM [5]
In addition we will review briefly six other articles: Four articles on constraints and two
advanced algorithms than Apriori.
The last phase of the work is an implementation of two algorithms: Bonsai-tree and FP-tree.
The implementation was coded in the JAVA language. The Database input is a synthetic
database and it was built by a random generator that was especially developed for this
purpose. The results and conclusions of the evaluation are summarized in the paper.
剩余77页未读,继续阅读
资源评论
![avatar-default](https://csdnimg.cn/release/downloadcmsfe/public/img/lazyLogo2.1882d7f4.png)
![avatar](https://profile-avatar.csdnimg.cn/68ef26bd67034c68b8d314222b3e4014_weixin_41429382.jpg!1)
百态老人
- 粉丝: 2304
- 资源: 2万+
![benefits](https://csdnimg.cn/release/downloadcmsfe/public/img/vip-rights-1.c8e153b4.png)
下载权益
![privilege](https://csdnimg.cn/release/downloadcmsfe/public/img/vip-rights-2.ec46750a.png)
C知道特权
![article](https://csdnimg.cn/release/downloadcmsfe/public/img/vip-rights-3.fc5e5fb6.png)
VIP文章
![course-privilege](https://csdnimg.cn/release/downloadcmsfe/public/img/vip-rights-4.320a6894.png)
课程特权
![rights](https://csdnimg.cn/release/downloadcmsfe/public/img/vip-rights-icon.fe0226a8.png)
开通VIP
上传资源 快速赚钱
我的内容管理 展开
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助
![voice](https://csdnimg.cn/release/downloadcmsfe/public/img/voice.245cc511.png)
![center-task](https://csdnimg.cn/release/downloadcmsfe/public/img/center-task.c2eda91a.png)
安全验证
文档复制为VIP权益,开通VIP直接复制
![dialog-icon](https://csdnimg.cn/release/downloadcmsfe/public/img/green-success.6a4acb44.png)