臺灣博碩士論文加值系統

以往的關聯式法則資料探勘，主要是在相同的交易中去尋找項目間的關聯性，本篇論文是探討“多維度交易間關連式法則之資料探勘”，主要是在尋求不同交易間的關連式法則，並推廣至高維度空間。我們提出E-Partition演算法並使用Grid File這個資料結構，來尋找資料庫中的大項目集合，此外，隨著資料的遞增，我們也提出E-DELTA演算法來尋找整個資料庫的大項目集合。
實驗證明E-Partition演算法優於傳統的E-Apriori演算法，且演算法中使用Grid File比搜尋資料庫有較佳的效能。

Traditionally, association rule data mining almost focuses on finding the associations among items within the same transaction. In this thesis, we explore “Multidimensional Intertrnasaction Association Rules”, which tries to find the association rule from different transactions and extend to multidimensional space. We propose the E-Partition algorithm and use the Grid File as our data structure to find the large itemsets in the database. Besides, we propose the E-DELTA algorithm to deal with the incremental data mining.
The experiment shows that the E-Partition algorithm performs better than the E-Apriori algorithm. Also, the algorithm using the Grid File has better efficiency than that scanning database does.

Chapter 1 Introduction......................................1
Chapter 2 Literature Survey.................................3
2.1 Partition.......................................3
2.2 Mining Multidimensional Intertransaction
Association Rules...............................3
2.3 Grid File.......................................8
2.4 Incremental Data Mining........................10
2.4.1 Equal-support............................11
2.4.2 Multi-support............................12
Chapter 3 Extension of Partition...........................14
3.1 E-Partition....................................14
3.2 Data Structure.................................23
3.4 Extending the E-Partition Algorithm to the
k-dimensional Space............................24
3.5 Finding the Large Itemsts in the Part of the
Grid File......................................24
3.6 Incremental Data Mining........................26
3.6.1 Efficiency Evaluation....................31
3.6.2 Rationale of E-DELTA Design..............32
3.6.3 The Extension of the Grid File...........32
Chapter 4 Performance Analysis.............................34
4.1 Generation of Synthetic Data...................34
4.2 Counting Supports of Candidates................36
4.3 Experiments on Synthetic Data..................38
4.4 Experiments on Real Data.......................40
4.5 Discussion.....................................43
Chapter 5 Conclusion.......................................44
References.................................................46

[1] R. Agrawal and R.Srikant, “Fast algorithms for mining
association rules,” In Proceedings of the 20th
International Conference on Very Large Databases (VLDB),
Santiago de Chile, Chile, pp. 487-499, 1994.
[2] A. Savasere,E. Omiecinski, and S.Navathe,”An efficient
algorithm for mining association rules in large databases,”
Proc. 21stInt’l Conf. Very Large Databasees. Morgan
Kaufmann, San Francisco, pp. 432-444,1995.
[3] Hongjun Lu , Ling Feng , Jiawei Han “Beyond
intratransaction association analysis: mining
multidimensional intertransaction association rules,” ACM
Transactions on Information Systems (TOIS), Vol. 18,No 4,
October 2000.
[4] J. Nievergelt, Hans Hinterberger, Kenneth C. Sevcik, “The
grid file: an adaptable, symmetric multikey file
structure,” ACM Transactions on Database Systems (TODS),
Vol. 9, Issue 1, January 1984.
[5] Vikram Pudi, Jayant R. Haritsa, “Quantifying the utility
of the past in mining large databases,” Information
Systems, Elsevier Science Publishers, Vol. 25, No. 5, pp.
323-344, July 2000.
[6] J.S.Park, M. Chen, and P.S.Yu, “An effective hash based
algorithm for mining association rules,” Proc. ACM SIGMOD
Conf., ACM Press, New York, pp. 175-186, 1995.
[7] H. Toivonen, “Sampling large databases for associations
rules,” In Proceedings of the 22nd International
Conference on Very Large Databases (VLDB), Bombay, India,
pp. 134-145, 1996.
[8] M. Zaki, S. Parthasarathy, M. Ogihara, W. Li, “New
algorithms for fast discovery of association rules,” In
Proc. of the 3rd International Conference on Knowledge
Discovery and Data Mining, pp. 283—286, 1997.