《一种发掘周期性关联规则之演算法》由会员分享,可在线阅读,更多相关《一种发掘周期性关联规则之演算法(62页珍藏版)》请在金锄头文库上搜索。
1、 國中山大學電機工程學系 碩士文 一種發掘週期性關規則之演算法 An algorithm for discovering periodical association rules 研究生:江忠 撰 指導教授:錫智 博士 中華民國九十三七月 摘要 摘要 本文主要內容有個部分,第一部分我們設計一個新的、有效的演算法採掘資庫中具有多層次關係時間週期性質的calendar-based association rules。同於一般使用 apriori-like的方法,我們的方法用最多掃瞄資庫次的架構,可避免多次掃瞄資庫,以節大的資庫掃瞄時間,並且用時間週期的特性減少掃瞄資庫過程中所要搜尋的 candid
2、ate calendar patterns目以增進程式執的速。以上這個特點使我們的方法能夠有效的採掘出整個資庫中所有具有時間週期的 association rules。 在第一部分中,我們所考慮的是具有嚴格限制,必須在週期上固定時間點循環出現的 calendar-based association rules,沒有考慮到位(非同步)的情形,但是在真實世界所收集到的資中,很可能具有非同步週期出現的規則存在,而這些規則可能是有用的。因此,我們在文的第二部份透過 membership function 定義所要找尋的非同步週期 fuzzy calendar pattern,並進一步搜尋出資庫中符合
3、fuzzy calendar pattern 的 association rules , 以得到 fuzzy periodical association rules。 由實驗結果得知,我們的方法能有效的從資庫中挖掘出calendar-based及 具 有 非 同 步 週 期 的fuzzy periodical association rules。 關鍵字:temporal association rules, calendar-based association rules, fuzzy periodical association rules. iAbstract Abstract The
4、re are two main contributions in the thesis . Firstly, we design a novel and efficient algorithm for mining calendar-based association rules which have multilevel time granularities in temporal databases. Unlike apriori-like approaches , our method scans the database twice at most. By avoiding multi
5、ple scans over the database , our method can reduce the database scanning time. Secondly, we use membership functions to construct fuzzy calendar patterns which represent asynchronous periods. With the use of fuzzy calendar patterns, we can discover fuzzy periodical association rules which are assoc
6、iation rules occurring in asynchronous periods. Experimental results have shown that our method is more efficient than others, and we can find fuzzy periodical association rules satisfactorily. Keywords: temporal association rules, calendar-based association rules, fuzzy periodical association rules
7、 ii目 摘要.i Abstract.ii 目.iii 圖表目.iv 第一章、文內容簡介.1 第二章、Mining calendar-based periodical association rules .3 1.Introduction.3 2.Problem definition.7 2.1 Association rule.7 2.2 Calendar-based pattern.9 2.3 Calendar-based periodical association rules 14 3.Algorithms.17 3.1 Temporal apriori.17 3.2 Our meth
8、od.21 第三章、Mining fuzzy periodical association rules.28 1. Introduction.28 2. Problem definition.29 2.1 Fuzzy calendar pattern.29 2.2 Fuzzy periodical association rule.30 3. Algorithm.36 第四章、Experiments.38 Experiment 1.39 Experiment 2.41 Experiment 3.44 Experiment 4.46 第五章、Conclusion.52 考文獻.54 iii圖表目
9、 1.圖 1.圖 圖 (II-2.1) 舉明 association rule 的各項定義.9 圖 (II-2.2) 以布函表示 (1998,2,14) .11 圖 (II-2.3) 以布函的組合表示 (1998,2,14) .12 圖 (II-2.4) 以布函的組合表示 ( , 2 , 14) . .13 圖(II-2.5)Calendar-based periodical association rules 的一 個子.16 圖 (II-3.1) Calendar schema 的階層式架構.24 圖 (II-3.2) Calendar candidate patterns pruning
10、 的子.27 圖 (III-1.1) Membership function 的一個子.29 圖(III-2.1)以 membership function 表示 close to(,11, 25) .31 圖(IV-1.1)Experiment 1 種方法的執時間比較圖.41 圖(IV-2.1)Experiment 2 種方法的執時間比較圖.42 圖(IV-2.2)Experiment 2 種方法產生的 calendar itemsets 及 採掘出的 frequent itemsets 平均圖.43 圖 (IV-2.3) Experiment 2 種方法產生的 candidate 與 fr
11、equent calendar patterns 平均圖.43 圖(IV-3.1)Experiment 3 第一次掃瞄資庫時只保 1-star calendar patterns 與保全部的 k-star calendar patterns 的 比較.45 圖(IV-3.2)Experiment 3 第一次掃瞄資庫時只保 1-star calendar patterns 與保全部的 k-star calendar patterns 的 執時間之比較.45 圖(IV-4.1)Experiment 4 close to (,15)的 membership function FC1.47 圖(IV-4.2)Experiment 4 close to (,15)的 membership ivfunction FC2.48 圖(IV-4.3)Experiment 4 在資庫中(,15)附近加入特 定 patterns 的日期.49 2.程圖 2.程圖 程圖 (II-3.1) Temporal apriori 的演算法.19 程圖 (II-3.2) 我們的方法之演算法.22 3.表 3.表 表(IV-1.1)Experiment 1 種方法產生的 calendar candidat