臺灣博碩士論文加值系統

關聯式規則之資料挖掘可以分成兩個階段：第一階段，找出在資料庫的出現頻率大於或等於使用者所指定門檻值的所有高頻率項目組。第二階段，以第一階段所產生的高頻率項目組來產生可靠性高的關聯式規則。如何從一個大型資料庫中找出所有的高頻率項目組決定了關聯式規則之資料挖掘的整體執行效率。在本篇論文中，我們提出一個以雜湊為基礎的HMFS方法，用來尋找資料庫中最大的高頻率項目組。HMFS 方法結合了DHP和Pincer-Search這兩個演算法的優點。這兩個演算法的結合使得HMFS的優點有二：第一，一般而言，HMFS方法可以減少資料庫蒐尋的次數。第二，HMFS方法可以過濾出低頻率候選項目組，然後利用這些被過濾掉的低頻率項目組來尋找高頻率項目組。這兩個優點可以把要找出所有高頻率項目組所需要的時間降低。除此之外，為了降低蒐尋空間，HMFS方法也提供了一個有效率的機制來建構最大的高頻率候選項目組。我們實做了HMFS，DHP和Pincer-Search這三個演算法，在Pentium III 800 MHz PC上執行的結果顯示出，對於大部分的測試資料庫，HMFS方法的執行效率都比DHP和Pincer-Search這兩個演算法好。特別是對於筆數較多的資料庫以及資料庫中高頻率項目組的長度較長時，我們所提出的方法有更顯著的改善。

The association rule mining can be divided into two steps.
The first step is to find out all frequent itemsets, whose occurrences are greater than or equal to the user-specified threshold. The second step is to generate reliable association rules based on all frequent itemsets found in the first step. Identifying all frequent itemsets in a large database dominates the overall performance in the association rule mining. In this paper, we propose an efficient hash-based method, HMFS, for discovering the maximal frequent itemsets. The HMFS method combines the advantages of both the DHP (Direct Hashing and Pruning) and the Pincer-Search algorithms. The combination leads to two advantages. First, the HMFS method, in general, can reduce the number of database scans. Second, the HMFS can filter the infrequent candidate itemsets and can use the filtered itemsets to find the maximal frequent itemsets. These two advantages can reduce the overall computing time of finding the maximal frequent itemsets. In addition, the HMFS method also provides an efficient mechanism to construct the maximal frequent candidate itemsets to reduce the search space. We have implemented the HMFS method along with the DHP and the Pincer-Search algorithms on a Pentium III 800 MHz PC. The experimental results show that the HMFS method has better performance than the DHP and the Pincer-Search algorithms for most of test cases. In particular, our method has significant improvement over the DHP and the Pincer-Search algorithms when the size of a database is large and the length of the longest itemset is relatively long.

1.INTRODUCTION1
2.PRELIMINARIES5
3.RELATED ALGORITHMS8
3.1 THE APRIORI ALGORITHM8
3.2 THE DHP ALGORITHM9
3.3 THE PINCER-SEARCH ALGORITHM11
4.THE HMFS METHOD14
5.EXPERIMENTAL RESULTS21
6.CONCLUSIONS28

[1]A. Savasere, E. Omiecinski, and S. Navathe, "An Efficient Algorithm for Mining Association Rules in Large Databases", In Proceedings of 21st VLDB, pp. 432-444, 1995.
[2]D. Lin and Z. M. Kedem, "Pincer-Search: A New Algorithm for Discovering the Maximum Frequent Set", In Proceedings of VI Intl. Conference on Extending Database Technology, 1998.
[3]Eui-Hong Han, George Karypis and Vipin Kumar, “Scalable Parallel Data Mining for Association Rules”, IEEE Transactions on Knowledge and Data Engineering, Vol. 12, No. 3, MAY/JUNE 2000.
[4]H. Toivonen, “Sampling Large Databases for Association Rules”, VLDB, pp. 134-145, 1996.
[5]IBM Quest Data Mining Project, “Quest Synthetic Data Generation Code”, “http”//www. almaden. ibm. com/cs/quest/syndata. html”, 1996
[6]J. S. Park, M. S. Chen, and P. S. Yu, "An Effective Hash Based Algorithm for Mining Association Rules", Proceedings of the ACM SIGMOD, pp. 175-186, 1995.
[7]M. Houtsma and A. Swami, “Set-Oriented Mining of Association Rules in Relational Databases,” 11th Int''l Conference on Data Engineer, 1995.
[8]M. J. Zaki, S. Parthasarathy, M. Ogihara, and W. Li, "New Algorithms for Fast Discovery of Association Rules", 3rd Int''l Conference on Knowledge Discovery & Data Mining (KDD), Newport, CA, August 1997.
[9]Mohammed J. Zaki, “Scalable Algorithm for Association Mining”, IEEE Transactions on Knowledge and Data Engineering, Vol. 12, No. 3, MAY/JUNE 2000.
[10]M. S. Chen, J. Han, and P. S. Yu, “Data Mining: An Overview from a Database Perspective”, IEEE Transactions on Knowledge and Data Engineering, Vol. 8, No. 6, December 1996.
[11]M. S. Chen, J. S. Park, and P. S. Yu, "Efficient Data Mining for Path Traversal Patterns", IEEE Transactions on Knowledge and Data Engineering, Vol. 10, No. 2, 1998, pp. 209-220.
[12]R. Agrawal, T. Imilienski, and A. Swami, "Mining Association Rules between Sets of Items in Large Databases", In Proceedings of the ACM SIGMOD Int''l Conference on Management of Data, pp. 207-216, May 1993.
[13]R. Agrawal and R. Srikant, "Fast Algorithm for Mining Association Rules in Large Databases", In Proceedings of 1994 Int''l Conference on VLDB, pp. 487-499, Santiago, Chile, Sep. 1994.
[14]R. Agrawal, H. Mannila, R. Srikant, H. Toivonen, and A. Inkeri Verkamo, “Fast Discovery of Association Rules,” Advances in Knowledge Discovery and Data Mining, U. Fayyad and et al., eds., pp. 307-328, Menlo Park, Calif.: AAAI Press, 1996.
[15]R. Agrawal and J. Shafer, “Parallel Mining of Association Rules,” IEEE Transactions on Knowledge and Data Engineering, Vol. 8, No. 6, pp. 962-969, Dec. 1996.
[16]R. J. Bayardo Jr., "Efficiently Mining Long Patterns from Databases", In Proceedings of the ACM SIGMOD Conference on Management of Data, pp. 85-93, Seattle, Washington, June 1998.
[17]S. Brin, R. Motwani, J. D. Ullman, and S. Tsur, "Dynamic Itemset Counting and Implication Rules for Market Basket Data", 1997 ACM SIGMOD Conference on Management of Data, pp. 255-264, 1997.