跳到主要內容

臺灣博碩士論文加值系統

(3.235.120.150) 您好!臺灣時間:2021/08/03 04:53
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:連育傑
研究生(外文):Yu-Chieh Lien
論文名稱:一個有效率的漸進式探勘頻繁樣式演算法
論文名稱(外文):An Efficient Algorithm for Incremental Mining of Frequent Patterns
指導教授:李御璽李御璽引用關係
指導教授(外文):Yue-Shi Lee
學位類別:碩士
校院名稱:銘傳大學
系所名稱:資訊工程學系碩士班
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2008
畢業學年度:96
語文別:中文
論文頁數:54
中文關鍵詞:漸進式關聯規則探勘資料串流的關聯規則探勘關聯規則探勘
外文關鍵詞:Association rule miningIncremental mining of association rulesMining association rules in data streams
相關次數:
  • 被引用被引用:0
  • 點閱點閱:140
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
傳統的關聯規則探勘主要是從給定的交易資料庫中,找出關聯規則。然而在許多實際的應用中,都不斷地有大量資料產生,而使用者想取得的卻是資料更新後,最新的關聯規則。因此許多學者便開始研究,如何在交易資料會不斷增加的情況下,有效率地維持最新的關聯規則。這方面的研究也稱為漸進式關聯規則探勘或資料串流的關聯規則探勘。
近期提出之漸進式及資料串流的關聯規則探勘演算法,普遍採取Tree-Based架構。首先把交易資料庫建構成一個樹狀結構,以類似FP Growth演算法,找出頻繁項目集。當有新增交易資料,要探勘更新後交易資料庫中的頻繁項目集時,便將新增交易資料加入先前建立的樹狀結構,再以類似FP Growth演算法整個重新探勘。然而在漸進式或資料串流的環境中,既有的交易資料往往遠大於新增交易資料,若每次探勘更新後的交易資料庫,僅將新增交易資料加入先前建立的樹狀結構,之後便整個重新探勘,恐怕效率不佳。因此本論文提出一個新的Tree-Based漸進式探勘頻繁樣式演算法,在探勘更新後的交易資料庫時,先針對新增交易資料進行探勘,再將此探勘結果和先前的探勘結果進行整合,找出更新後交易資料庫中的頻繁項目集,來產生最新的關聯規則。從實驗的結果也印證這樣的做法確實較重新探勘有效率。
Traditional association rule mining is to find association rules in a given transaction database. However in many real applications, there are a lot of new data generated continuously and the user wants to get the new association rules in the updated transaction database. Hence how to find association rules efficiently under the circumstances where data would be added continuously becomes an important research issue for a practical purpose. It is called incremental mining of association rules or mining association rules in data streams.
Many incremental mining algorithms and data streams mining algorithms proposed recently adopt the tree-based structure. It constructs a tree structure to store transactions in memory and then uses an algorithm similar to FP growth to find frequent itemsets from the tree structure. When the incremental transactions arrive and we want to find frequent itemsets in the updated transaction database, it would add the incremental transactions to the tree structure constructed previously and then uses the algorithm similar to FP growth to mine frequent itemsets from the updated tree structure again. However the size of the original transaction database is often much larger than that of incremental transactions. So it would be inefficient. In the paper, we propose an efficient algorithm for incremental mining of frequent patterns. When mining from the updated transaction database, it mines frequent itemsets from the incremental transactions and then integrates the mining result with the previous result to get the new frequent itemsets in the updated transaction database. Finally, we can use these new frequent itemsets to generate new association rules. Experiment results show our approach is more efficient.
中文摘要 i
英文摘要 ii
誌謝 iv
目錄 v
表目錄 vii
圖目錄 viii
第壹章 導論 1
第一節 研究背景 1
第二節 研究動機及目的 3
第三節 論文組織 4
第貳章 文獻探討 5
第一節 關聯規則探勘演算法 5
第二節 漸進式及資料串流的關聯規則探勘演算法 7
第參章 漸進式探勘頻繁樣式演算法 12
第一節 概述 12
第二節 刪除節點 13
第三節 新增節點 16
第四節 我們的演算法 19
第五節 演算法實例 26
第六節 演算法實作 32
第肆章 實驗及效能分析 36
第一節 測試資料集 36
第二節 實驗結果 36
第伍章 結論 42
參考文獻 43
1.R. Agrawal, T. Imielinski and A. Swami, “Mining Association Rules between Sets of Items in Large Databases,” in Proceedings of the 12th ACM International Conference on Management of Data (SIGMOD), pp. 207–216, 1993.
2.R. Agrawal and R. Srikant, “Fast Algorithm for Mining Association Rule in Large Databases,” in Proceedings of the 20th International Conference on Very Large Data Bases (VLDB), pp. 487–499, 1994.
3.N. F. Ayan, A. U. Tansel and E. Arkun, “An Efficient Algorithm to Update Large Itemsets with Early Pruning,” in Proceedings of the 5th ACM International Conference on Knowledge Discovery and Data Mining (KDD), pp. 287–291, 1999.
4.D. W. Cheung, J. Han, V. T. Ng and C. Y. Wong, “Maintenance of Discovered Association Rules in Large Databases: An Incremental Update Technique,” in Proceedings of the 12th International Conference on Data Engineering (ICDE), pp. 106–114, 1996.
5.D. W. Cheung, S. D. Lee and B. Kao, “ General Incremental Technique for Maintaining Discovered Association Rules,” in Proceedings of the 5th International Conference on Database Systems for Advanced Applications (DASFAA), pp. 185–194, 1997.
6.W. Cheung and O. R. Zaiane, “Incremental Mining of Frequent Patterns without Candidate Generation or Support Constraint,” in Proceedings of the 7th International Database Engineering and Applications Symposium (IDEAS), pp. 111–116, 2003.
7.Chin-Chen Chang, Yu-Chiang Li and Jung-San Lee, “An Efficient Algorithm for Incremental Mining of Association Rules,” in Proceedings of the 15th International Workshop on Research Issues in Data Engineering: Stream Data Mining and Applications, pp. 3–10, 2005.
8.Jiawei Han, Jian Pei and Yiwen Yin, “Mining Frequent Patterns without Candidate Generation,” in Proceedings of the 2000 ACM SIGMOD international conference on Management of data, pp.1–12, 2000.
9.Hai-Tao He and Shi-Ling Zhang, “A New Method for Incremental Updating Frequent Patterns Mining,” in Proceedings of the 2th International Conference on Innovative Computing, Informatio and Control (ICICIC 2007), pp. 561, 2007.
10.Tzung-Pei Hong, Chun-Wei Lin and Yu-Lung Wu, “Incrementally Fast Updated Frequent Pattern Trees,” Expert Systems with Applications: An International Journal, Vol. 34, No. 4, pp. 2424-2435, 2008.
11.J. L. Koh and S. F. Shieh, “An Efficient Approach for Maintaining Association Rules Based on Adjusting FP-Tree Structures,” in Proceedings of the 12th International Conference on Database Systems for Advanced Applications (DASFAA), pp. 417–424, 2004.
12.Chang-Hung Lee, Cheng-Ru Lin and Ming-Syan Chen, “Sliding-Window Filtering: An Efficient Algorithm for Incremental Mining,” in Proceedings of the 10th international conference on Information and knowledge management, pp. 263–270, 2001.
13.C. K. Leung, Q. I. Khan and T. Hoque, “CanTree: A Tree Structure for Efficient Incremental Mining of Frequent Patterns,” in Proceedings of the 5th IEEE International Conference on Data Mining (ICDM), pp. 274-281, 2005.
14.H. F. Li, S. Y. Lee and M. K. Shan, “Online Mining (Recently) Maximal Frequent Itemsets over Data Streams,” in Proceedings of the 15th International Workshop on Research Issues in Data Engineering: Stream Data Mining and Applications (RIDE-SDMA), pp. 11-18, 2005.
15.Wang Lian, David W. Cheung and S. M. Yiu, “Maintenance of Maximal Frequent Itemsets in Large Databases,” in Proceedings of the 2007 ACM Symposium on Applied Computing, pp. 388–392, 2007.
16.G.S. Manku and R. Motwani, “Approximate Frequency Counts over Data Streams,” in Proceedings of the 28th International Conference on Very Large Data Bases (VLDB), pp.346–357, 2002.
17.Xiu-Li Ma, Yun-Hai Tong, Shi-Wei Tang and Dong-Qing Yang, “Efficient Incremental Maintenance of Frequent Patterns with FP-tree,” Journal of Computer Science and Technology, Vol. 19, No. 6, pp. 876-884, 2004.
18.J. S. Park, M. S. Chen and P. S. Yu, “An Effective Hash Based Algorithm for Mining Association Rules,” in Proceedings of the 14th ACM International Conference on Management of Data (SIGMOD), pp. 175-186, 1995.
19.J. Pei, J. Han, H. Lu, S. Nishio, S. Tang, and D. Yang, “H-Mine: Hyper-Structure Mining of Frequent Patterns in Large Databases,” in Proceedings of the 2001 IEEE International Conference on Data Mining, pp.441–448, 2001.
20.Ke Wang, Liu Tang, Jiawei Han and Junqiang Liu, “Top Down FP-Growth for Association Rule Mining,” in Proceedings of the 6th Pacific-Asia Conference on Advances in Knowledge Discovery and Data Mining, pp.334–340, 2002.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top