article

Twain: Two-end association miner with precise frequent exhibition periods

Authors:

Ming-Syan ChenAuthors Info & Claims

ACM Transactions on Knowledge Discovery from Data (TKDD), Volume 1, Issue 2

Pages 8 - es

https://doi.org/10.1145/1267066.1267069

Published: 01 August 2007 Publication History

Abstract

We investigate the general model of mining associations in a temporal database, where the exhibition periods of items are allowed to be different from one to another. The database is divided into partitions according to the time granularity imposed. Such temporal association rules allow us to observe short-term but interesting patterns that are absent when the whole range of the database is evaluated altogether. Prior work may omit some temporal association rules and thus have limited practicability. To remedy this and to give more precise frequent exhibition periods of frequent temporal itemsets, we devise an efficient algorithm Twain (standing for TWo end AssocIation miNer.) Twain not only generates frequent patterns with more precise frequent exhibition periods, but also discovers more interesting frequent patterns. Twain employs Start time and End time of each item to provide precise frequent exhibition period while progressively handling itemsets from one partition to another. Along with one scan of the database, Twain can generate frequent 2-itemsets directly according to the cumulative filtering threshold. Then, Twain adopts the scan reduction technique to generate all frequent k-itemsets (k > 2) from the generated frequent 2-itemsets. Theoretical properties of Twain are derived as well in this article. The experimental results show that Twain outperforms the prior works in the quality of frequent patterns, execution time, I/O cost, CPU overhead and scalability.

References

[1]

Agarwal, R., Aggarwal, C., and Prasad, V. 2000. A tree projection algorithm for generation of frequent itemsets. J. Para. Distrib. Comput. (Special Issue on High Performance Data Mining).

Digital Library

[2]

Agrawal, R., Imielinski, T., and Swami, A. 1993. Mining association rules between sets of items in large databases. In Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data, ACM, New York, 207--216.

Digital Library

[3]

Agrawal, R. and Srikant, R. 1994. Fast algorithms for mining association rules in large databases. In Proceedings of the 20th International Conference on Very Large Data Bases, 478--499.

Digital Library

[4]

Ale, J. and Rossi, G. 2000. An approach to discovering temporal association rules. In Proceedings of the ACM Symposium on Applied Computing 1, ACM, New York, 294--300.

Digital Library

[5]

Ayad, A. M., El-Makky, N. M., and Taha, Y. 2001. Incremental mining of constrained association rules. In Proceedings of the 1st ACM-SIAM Conference on Data Mining. ACM, New York.

[6]

Besemann, C. and Denton, A. 2005. Integration of profile hidden Markov model output into association rule mining. In Proceedings of the 11th ACM SIGKDD International Conference on Knowledge Discovery in Data Mining, ACM, New York, 538--543.

Digital Library

[7]

Bettini, C., Wang, X., and Jajodia, S. 1998. Mining temporal relationships with multiple granularities in time sequences. Bulle. IEEE Comput. Soc. Tech. Comm. Data Eng.

[8]

Blanchard, J., Guillet, F., Gras, R., and Briand, H. 2005. Using information-theoretic measures to assess association rule interestingness. In Proceedings of the 5th IEEE International Conference on Data Mining. IEEE Computer Society Press, Los Alamitos, CA.

Digital Library

[9]

Chang, C.-Y., Chen, M.-S., and Lee, C.-H. 2002. Mining general temporal association rules for items with different exhibition periods. In Proceedings of the 2nd IEEE International Conference on Data Mining. IEEE Computer Society Press, Los Alamitos, CA.

Digital Library

[10]

Chen, J., He, H., Williams, G., and Jin, H. 2004. Temporal sequence associations for rare events. In Proceedings of the 8th Pacific Asia Conference on Knowledge Discovery and Data Mining.

[11]

Chen, X. and Petr, I. 2000. Discovering temporal association rules: algorithms, language and system. In Proceedings of the 16th IEEE International Conference on Data Engineering. IEEE Computer Society Press, Los Alamitos, CA.

Digital Library

[12]

Chen, X., Petrounias, I., and Heathfield, H. 1998. Discovery of association rules in temporal databases. In Proceedings of the Issues and Applications of Database Technology.

[13]

Cohen, E., Datary, M., Fujiwaraz, S., Gionisx, A., Indyk, P., Motwanik, R., Ullman, J. D., and Yangyy, C. 2001. Finding interesting associations without support pruning. IEEE Trans. Knowl. Data Eng., 64--78.

Digital Library

[14]

Han, J. and Fu, Y. 1995. Discovery of multiple-level association rules from large databases. In Proceedings of the 21th International Conference on Very Large Data Bases, 420--431.

Digital Library

[15]

Han, J. and Kamber, M. 2000. Data Mining: Concepts and Techniques. Morgan-Kaufmann. San Francisco, CA.

Digital Library

[16]

Han, J. and Pei, J. 2000. Mining frequent patterns by pattern-growth: Methodology and implications. ACM SIGKDD Explorations (Special Issue on Scaleble Data Mining Algorithms). ACM, New York.

Digital Library

[17]

Han, J., Pei, J., Mortazavi-Asl, B., Chen, Q., Dayal, U., and Hsu, M.-C. 2000a. FreeSpan: Frequent pattern-projected sequential pattern mining. In Proceedings of the 6th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ACM, New York. 355--359.

Digital Library

[18]

Han, J., Pei, J., and Yin, Y. 2000b. Mining frequent patterns without candidate generation. In Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data, ACM, New York. 486--493.

Digital Library

[19]

Harms, S. K. and Deogun, J. S. 2004. Sequential association rule mining with time lags. Journal of Intelligent Informatics Systems.

Digital Library

[20]

Jiang, N. and Gruenwald, L. 2006. An efficient algorithm to mine online data streams. In Proceedings of the 2006 KDD TDM Workshop.

[21]

Ke, Y., Cheng, J., and Ng, W. 2006. MIC framework: An information-theoretic approach to quantitative association rule mining. In Proceedings of the 22nd IEEE International Conference on Data Engineering. IEEE Computer Society Press, Los Alamitos, CA.

Digital Library

[22]

Kifer, D., Bucila, C., Gehrke, J., and White, W. 2002. DualMiner: A dual-pruning algorithm for itemsets with constraints. In Proceedings of the 8th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, New York.

Digital Library

[23]

Lakshmanan, L., Ng, R., Han, J., and Pang, A. 1998. Exploratory mining and pruning optimization of constrained associations rules. In Proceedings of the 1998 ACM SIGMOD International Conference on Management of Data. ACM, New York.

Digital Library

[24]

Lakshmanan, L. V. S., Ng, R., Han, J., and Pang, A. 1999. Optimization of constrained frequent set queries with 2-variable constraints. In Proceedings of the 1999 ACM SIGMOD International Conference on Management of Data, ACM, New York. 157--168.

Digital Library

[25]

Lee, C.-H., Chen, M.-S., and Lin, C.-R. 2003. Progressive partition miner: An efficient algorithm for mining general temporal association rules. IEEE Trans. Knowl. Data Eng. 15, 4 (Aug.), 1004--1017.

Digital Library

[26]

Lee, C.-H., Lin, C.-R., and Chen, M.-S. 2001a. On mining general temporal association rules in a publication database. In Proceedings of the 1st IEEE International Conference on Data Mining. (Nov.). IEEE Computer Society Press, Los Alamitos, CA.

Digital Library

[27]

Lee, C.-H., Lin, C.-R., and Chen, M.-S. 2001b. Sliding-window filtering: An efficient algorithm for incremental mining. In Proceedings of the 10th ACM International Conference on Information and Knowledge Management. ACM, New York.

Digital Library

[28]

Lin, J.-L. and Dunham, M. 1998. Mining association rules: Anti-skew algorithms. In Proceedings of the 14th IEEE International Conference on Data Engineering, IEEE Computer Society Press, Los Alamitos, CA. 486--493.

Digital Library

[29]

Liu, B., Hsu, W., and Ma, Y. 1999. Mining association rules with multiple minimum supports. In Proceedings of the 5th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, New York.

Digital Library

[30]

Mueller, A. 1995. Fast sequential and parallel algorithms for association rule mining: A comparison. Tech. Rep. CS-TR-3515, Dept. of Computer Science, Univ. of Maryland, College Park, MD.

Digital Library

[31]

Muhonen, B. G. J. and Toivonen, H. 2005. Mining non-derivable association rules. In Proceedings of the 5th ACM SIAM Conference on Data Mining. ACM, New York.

[32]

Ng, R. and Han, J. 1994. Efficient and effective clustering methods for spatial data mining. In Proceedings of the 20th International Conference on Very Large Data Bases, 144--155.

Digital Library

[33]

Park, J.-S., Chen, M.-S., and Yu, P. S. 1997. Using a hash-based method with transaction trimming for mining association rules. IEEE Trans. Knowl. Data Eng. 9, 5 (Oct.), 813--825.

Digital Library

[34]

Pei, J. and Han, J. 2000. Can we push more constraints into frequent pattern mining? In Proceedings of the 6th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, New York.

Digital Library

[35]

Pei, J., Han, J., Mortazavi-Asl, B., Pinto, H., Chen, Q., Dayal, U., and Hsu, M.-C. 2001. PrefixSpan: Mining sequential patterns efficiently by prefix-projected pattern growth. In Proceedings of the 17th IEEE International Conference on Data Engineering. IEEE Computer Society Press, Los Alamitos, CA.

Digital Library

[36]

Savasere, A., Omiecinski, E., and Navathe, S. 1995. An efficient algorithm for mining association rules in large databases. In Proceedings of the 21th International Conference on Very Large Data Bases, 432--444.

Digital Library

[37]

Srikant, R. and Agrawal, R. 1995. Mining generalized association rules. In Proceedings of the 21th International Conference on Very Large Data Bases. 407--419.

Digital Library

[38]

Srikant, R. and Agrawal, R. 1996. Mining quantitative association rules in large relational tables. In Proceedings of the 1996 ACM SIGMOD International Conference on Management of Data. ACM, New York.

Digital Library

[39]

Steinbach, M., Tan, P.-N., and Kumar, V. 2005. Support envelopes: A technique for exploring the structure of association patterns. In Proceedings of the 10th ACM SIGKDD International Conference on Knowledge Discovery in Data Mining. ACM, New York.

Digital Library

[40]

Szymon and Jaroszewicz. 2006. Polynomial association rules with applications to logistic regression. In Proceedings of the 11st ACM SIGKDD International Conference on Knowledge Discovery in Data Mining. ACM, New York.

Digital Library

[41]

Tansel, A. and Ayan, N. 1998. Discovery of association rules in temporal databases. In Proceedings of the AAAI on Knowledge Discovery in Databases.

[42]

Toivonen, H. 1996. Sampling large databases for association rules. In Proceedings of the 22nd International Conference on Very Large Data Bases, 134--145.

Digital Library

[43]

Wang, K., He, Y., and Han, J. 2000. Mining frequent itemsets using support constraints. In Proceedings of the 26th International Conference on Very Large Data Bases.

Digital Library

[44]

Xuan-Hieu, P., Le-Minh, N., Tu-Bao, H., and Susumu, H. 2005. Improving discriminative sequential learning with rare-but-important associations. In Proceedings of the 10th ACM SIGKDD International Conference on Knowledge Discovery in Data Mining. ACM, New York.

Digital Library

[45]

Yang, C., Fayyad, U., and Bradley, P. 2001. Efficient discovery of error-tolerant frequent itemsets in high dimensions. In Proceedings of the 7th ACM SIGKDD International Conference on Knowledge Discovery in Data Mining. ACM, New York.

Digital Library

[46]

Zheng, Z., Kohavi, R., and Mason, L. 2001. Real world performance of association rule algorithms. In Proceedings of the 7th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, F. Provost and R. Srikant, Eds. ACM, New York. 401--406.

Digital Library

Cited By

Agarwal R(2021)An Approach for Estimating the Opportunity Cost Using Temporal Association Rule Mining and ClusteringEncyclopedia of Organizational Knowledge, Administration, and Technology10.4018/978-1-7998-3473-1.ch046(631-643)Online publication date: 2021
https://doi.org/10.4018/978-1-7998-3473-1.ch046
Yousefi LTucker A(2020)Predicting Type 2 Diabetes Complications and Personalising Patient Using Artificial Intelligence MethodologyType 2 Diabetes [Working Title]10.5772/intechopen.94228Online publication date: 19-Dec-2020
https://doi.org/10.5772/intechopen.94228
Agarwal R(2020)Modified Ranking With Temporal Association Rule Mining in Supply ChainsInternational Journal of Service Science, Management, Engineering, and Technology10.4018/IJSSMET.202010010411:4(58-71)Online publication date: 1-Oct-2020
https://doi.org/10.4018/IJSSMET.2020100104
Show More Cited By

Index Terms

Twain: Two-end association miner with precise frequent exhibition periods
1. Information systems
  1. Information systems applications
    1. Data mining

Recommendations

Developing Novel and Effective Approach for Association Rule Mining Using Progressive Sampling
ICCEE '09: Proceedings of the 2009 Second International Conference on Computer and Electrical Engineering - Volume 01

A challenging task in data mining is the process of discovering association rules from a large database. Most of the existing association rule mining algorithms make repeated passes over the entire database to determine the frequent itemsets, which is ...
SRIHASS - a similarity measure for discovery of hidden time profiled temporal associations

Mining and visualization of time profiled temporal associations is an important research problem that is not addressed in a wider perspective and is understudied. Visual analysis of time profiled temporal associations helps to better understand hidden ...
Knowledge Discovery from Series of Interval Events
Data warehousing and knowledge discovery

Knowledge discovery from data sets can be extensively automated by using data mining software tools. Techniques for mining series of interval events, however, have not been considered. Such time series are common in many applications. In this paper, we ...

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Knowledge Discovery from Data

ACM Transactions on Knowledge Discovery from Data Volume 1, Issue 2

August 2007

89 pages

ISSN:1556-4681

EISSN:1556-472X

DOI:10.1145/1267066

Issue’s Table of Contents

Copyright © 2007 ACM.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 August 2007

Published in TKDD Volume 1, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

19
Total Citations
View Citations
743
Total Downloads

Downloads (Last 12 months)2
Downloads (Last 6 weeks)0

Reflects downloads up to 07 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Agarwal R(2021)An Approach for Estimating the Opportunity Cost Using Temporal Association Rule Mining and ClusteringEncyclopedia of Organizational Knowledge, Administration, and Technology10.4018/978-1-7998-3473-1.ch046(631-643)Online publication date: 2021
https://doi.org/10.4018/978-1-7998-3473-1.ch046
Yousefi LTucker A(2020)Predicting Type 2 Diabetes Complications and Personalising Patient Using Artificial Intelligence MethodologyType 2 Diabetes [Working Title]10.5772/intechopen.94228Online publication date: 19-Dec-2020
https://doi.org/10.5772/intechopen.94228
Agarwal R(2020)Modified Ranking With Temporal Association Rule Mining in Supply ChainsInternational Journal of Service Science, Management, Engineering, and Technology10.4018/IJSSMET.202010010411:4(58-71)Online publication date: 1-Oct-2020
https://doi.org/10.4018/IJSSMET.2020100104
Agarwal R(2020)Application of Utility Mining in Supply Chain ManagementBusiness Management and Communication Perspectives in Industry 4.010.4018/978-1-5225-9416-1.ch012(209-225)Online publication date: 2020
https://doi.org/10.4018/978-1-5225-9416-1.ch012
Segura‐Delgado AGacto MAlcalá RAlcalá‐Fdez J(2020)Temporal association rule mining: An overview considering the time variable as an integral or implied componentWIREs Data Mining and Knowledge Discovery10.1002/widm.136710:4Online publication date: 27-Apr-2020
https://doi.org/10.1002/widm.1367
Upadhyay PKohli NPandey M(2019)Discovering Cyclic and Partial Cyclic Patterns Using the FP Growth Method Incorporated with Special ConstraintsNext Generation Computing Technologies on Computational Intelligence10.1007/978-981-15-1718-1_19(221-235)Online publication date: 24-Nov-2019
https://doi.org/10.1007/978-981-15-1718-1_19
Agarwal RMittal M(2018)Optimal Ordering Policy With Inventory Classification Using Data Mining TechniquesHandbook of Research on Promoting Business Process Improvement Through Inventory Control Techniques10.4018/978-1-5225-3232-3.ch017(305-326)Online publication date: 2018
https://doi.org/10.4018/978-1-5225-3232-3.ch017
Patil DTirmare H(2018)Efficient Method for Mining Frequent Itemsets using Temporal Data2018 International Conference on Information , Communication, Engineering and Technology (ICICET)10.1109/ICICET.2018.8533739(1-4)Online publication date: Aug-2018
https://doi.org/10.1109/ICICET.2018.8533739
Xie TZheng QZhang W(2018)Mining temporal characteristics of behaviors from interval events in e-learningInformation Sciences10.1016/j.ins.2018.03.018447(169-185)Online publication date: Jun-2018
https://doi.org/10.1016/j.ins.2018.03.018
Agarwal RMittal MPareek S(2016)Loss Profit Estimation Using Temporal Association Rule MiningInternational Journal of Business Analytics10.4018/IJBAN.20160101033:1(45-57)Online publication date: Jan-2016
https://doi.org/10.4018/IJBAN.2016010103
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents