Abstract
We describe a new tool for mining association rules, which is of special value in text mining. The new tool, called maximal associations, is geared toward discovering associations that are frequently lost when using regular association rules. Intuitively, a maximal association rule \({X}\stackrel{\rm max}{\Longrightarrow}{Y}\) says that whenever X is the only item of its type in a transaction, than Y also appears, with some confidence. Maximal associations allow the discovery of associations pertaining to items that most often do not appear alone, but rather together with closely related items, and hence associations relevant only to these items tend to obtain low confidence. We provide a formal description of maximal association rules and efficient algorithms for discovering all such associations. We present the results of applying maximal association rules to two text corpora.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Agrawal, R., Imielinski, T., and Swami, A.N. (1993). Mining Association Rules Between Sets of Items in Large Databases. In Buneman, Peter and Jajodia, Sushil (Eds.), Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data, (pp. 207–216). Washington, D.C.
Agrawal, R., Imielinski, T., and Swami, A.N. (1993). Mining Association Rules Between Sets of Items in Large Databases. In Buneman, Peter and Jajodia, Sushil (Eds.), Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data, (pp. 207–216). Washington, D.C.
Ahonen, H., Heinonen, O., Klemettinen, M., and Verkamo, I. (1997). Applying Data Mining Techniques in Text Analysis. Technical Report C-1997-23, University of Helsinki.
Ahonen, H., Heinonen, O., Klemettinen, M., and Verkamo, I. (1997). Applying Data Mining Techniques in Text Analysis. Technical Report C-1997-23, University of Helsinki.
Bench-Capon, T.J.M., Frans, Coenen, and Leng, P. (2000). An Experiment in Discovering Association Rules in the Legal Domain. In Proceeding of the Workshop on Legal Information Systems and Applications (LISA) (pp. 1056–1060).
Bench-Capon, T.J.M., Frans, Coenen, and Leng, P. (2000). An Experiment in Discovering Association Rules in the Legal Domain. In Proceeding of the Workshop on Legal Information Systems and Applications (LISA) (pp. 1056–1060).
Brijs, Tom, Swinnen, Gilbert, Vanhoof, Koen, and Wets, Geert. (1999). Using Association Rules for Product Assortment Decisions: A Case Study. In Knowledge Discovery and Data Mining (pp. 254–260).
Brijs, Tom, Swinnen, Gilbert, Vanhoof, Koen, and Wets, Geert. (1999). Using Association Rules for Product Assortment Decisions: A Case Study. In Knowledge Discovery and Data Mining (pp. 254–260).
Brin, Sergey, Motwani, Rajeev, and Silverstein, Craig. (1997). Beyond Market Baskets: Generalizing Association Rules to Correlations. In Proceedings of the ACM SIGMOD International Conference on Management of Data (pp. 265–276).
Brin, Sergey, Motwani, Rajeev, and Silverstein, Craig. (1997). Beyond Market Baskets: Generalizing Association Rules to Correlations. In Proceedings of the ACM SIGMOD International Conference on Management of Data (pp. 265–276).
Cai, C.H., Fu, Ada Wai-Chee, Cheng, C.H., and Kwong, W.W. (1998). Mining Association Rules with Weighted Items. In International Database Engineering and Application Symposium (pp. 68–77).
Cai, C.H., Fu, Ada Wai-Chee, Cheng, C.H., and Kwong, W.W. (1998). Mining Association Rules with Weighted Items. In International Database Engineering and Application Symposium (pp. 68–77).
Dong, Jianning, Perrizo, William, Ding, Qin, and Zhou, Jingkai. (2000). The Application of Association Rule Mining to Remotely Sensed Data. In SAC (1) (pp. 340–345).
Fayyad, U.M., Piatetsky-Shapiro, G., and Smyth, P. (1996). Knowledge Discovery and Data Mining: Towards a Unifying Framework. In Knowledge Discovery and Data Mining (pp. 82–88).
Fayyad, U.M., Piatetsky-Shapiro, G., and Smyth, P. (1996). Knowledge Discovery and Data Mining: Towards a Unifying Framework. In Knowledge Discovery and Data Mining (pp. 82–88).
Feldman, R., Aumann, Y., Amir, A., Zilberstein, A., and Klosgen, W. (1997). Maximal Association Rules: A New Tool for Mining for Keyword Co-Occurrences in Document Collections. In Proceedings of the 3rd International Conference on Knowledge Discovery and Data Mining (KDD) (pp. 167–170).
Feldman, R. and Dagan, I. (1995). KDT-Knowledge Discovery in Texts. In Proceedings of the First International Conference on Knowledge Discovery (KDD) (pp. 112–117).
Feldman, R. and Dagan, I. (1995). KDT-Knowledge Discovery in Texts. In Proceedings of the First International Conference on Knowledge Discovery (KDD) (pp. 112–117).
Feldman, R., Dagan, I., and Hirsh, H. (1998). Mining Text Using Keyword Distributions. Journal of Intelligent Information Systems, 10(3), 281–300.
Feldman, R., Dagan, I., and Hirsh, H. (1998). Mining Text Using Keyword Distributions. Journal of Intelligent Information Systems, 10(3), 281–300.
Feldman, R., Fresko, M., Kinar, Y., Lindell, Y., Liphstat, O., Rajman, M., Schler, Y., and Zamir, O. Text Mining at the Term Level. In Principles of Data Mining and Knowledge Discovery (pp. 65–73).
Feldman, R., Fresko, M., Kinar, Y., Lindell, Y., Liphstat, O., Rajman, M., Schler, Y., and Zamir, O. Text Mining at the Term Level. In Principles of Data Mining and Knowledge Discovery (pp. 65–73).
Feldman, R. and Hirsh, H. (1996). Mining Associations in Text in The Presence of Background Knowledge. In Knowledge Discovery and Data Mining (pp. 343–346).
Feldman, R. and Hirsh, H. (1996). Mining Associations in Text in The Presence of Background Knowledge. In Knowledge Discovery and Data Mining (pp. 343–346).
Han, J. and Fu, Y. (1999). Mining Multiple-Level Association Rules in Large Databases. Knowledge and Data Engineering, 11(5), 798–804.
Han, J. and Fu, Y. (1999). Mining Multiple-Level Association Rules in Large Databases. Knowledge and Data Engineering, 11(5), 798–804.
Hearst, M. (1999). Untangling Text Data Mining. In Proceedings of ACL'99: the 37th Annual Meeting of the Association for Computational Linguistics (pp. 3–10).
Hearst, M. (1999). Untangling Text Data Mining. In Proceedings of ACL'99: the 37th Annual Meeting of the Association for Computational Linguistics (pp. 3–10).
Hipp, J., Güntzer, U., and Nakhaeizadeh, G. (2000). Algorithms for Association Rule Mining—A General Survey and Comparison. SIGKDD Explorations, 2(1), 58–64.
Lee, W., Stolfo, S.J., and Mok, K.W. (1999). A Data Mining Framework for Building Intrusion Detection Models. In IEEE Symposium on Security and Privacy (pp. 120–132).
Lee, W., Stolfo, S.J., and Mok, K.W. (1999). A Data Mining Framework for Building Intrusion Detection Models. In IEEE Symposium on Security and Privacy (pp. 120–132).
Liu, B., Hsu, W., and Ma, Y. (1999). Mining Association Rules with Multiple Minimum Supports. In Knowledge Discovery and Data Mining (pp. 337–341).
Liu, B., Hsu, W., and Ma, Y. (1999). Mining Association Rules with Multiple Minimum Supports. In Knowledge Discovery and Data Mining (pp. 337–341).
Ma, Y., Liu, B., Wong, C.K., Yu, P.S., and Lee, S.M. (2000). Targeting the right students using data mining. In Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining (KDD) (pp. 457–464).
Ma, Y., Liu, B., Wong, C.K., Yu, P.S., and Lee, S.M. (2000). Targeting the right students using data mining. In Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining (KDD) (pp. 457–464).
Mannila, H., Toivonen, H., and Verkamo, A.I. (1995). Discovering Frequent Episodes in Sequences. U.M. Fayyad and R. Uthurusamy (Eds.), Proceedings of the First International Conference on Knowledge Discovery and Data Mining (KDD-95), Montreal, Canada. AAAI Press.
Mannila, H., Toivonen, H., and Verkamo, A.I. (1995). Discovering Frequent Episodes in Sequences. U.M. Fayyad and R. Uthurusamy (Eds.), Proceedings of the First International Conference on Knowledge Discovery and Data Mining (KDD-95), Montreal, Canada. AAAI Press.
Michail, Amir. (2000). Data Mining Library Reuse Patterns Using Generalized Association Rules. In International Conference on Software Engineering (pp. 167–176).
Michail, Amir. (2000). Data Mining Library Reuse Patterns Using Generalized Association Rules. In International Conference on Software Engineering (pp. 167–176).
Rajman, M. and Besancon, R. (1997). Text Mining: Natural Language Techniques and Text Mining Applications. In Proceedings of the seventh IFIP Working Conference on Database Semantics.
Satou, K., Shibayama, G., Ono, T., Yamamura, Y., Furuichi, E., Kuhara, S., and Takagi, T. (1997). Finding Association Rules on Heterogeneous Genome Data. In Proceedings of the Second Pacific Symposium on Biocomputing (PSB) (pp. 397–408).
Srikant R. and Agrawal, R. (1997). Mining Generalized Association Rules. Future Generation Computer Systems, 13(2/3), 161–180
Srikant R. and Agrawal, R. (1997). Mining Generalized Association Rules. Future Generation Computer Systems, 13(2/3), 161–180
Tao, F., Murtagh, F., and Farid, M. (2003). Weighted Association Rule Mining Using Weighted Support and Significance Framework. In The Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (To appear).
Tung, A.K.H., Lu, H., Han, J., and Feng, L. (1999). Breaking the Barrier of Transactions: Mining Inter-Transaction Association Rules. In Knowledge Discovery and Data Mining (pp. 297–301).
Tung, A.K.H., Lu, H., Han, J., and Feng, L. (1999). Breaking the Barrier of Transactions: Mining Inter-Transaction Association Rules. In Knowledge Discovery and Data Mining (pp. 297–301).
Wang, W., Yang, J., and Yu, P.S. (2000). Efficient Mining of Weighted Association Rules (WAR). In Proceedings of the Sixth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (pp. 270–274).
Wang, W., Yang, J., and Yu, P.S. (2000). Efficient Mining of Weighted Association Rules (WAR). In Proceedings of the Sixth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (pp. 270–274).
Wong, P.C., Whitney, Paul, and Thomas, Jim. (1999). Visualizing Association Rules for Text Mining. In IEEE Symposium on Information Visualization (INFOVIS) (pp. 120–123).
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Amir, A., Aumann, Y., Feldman, R. et al. Maximal Association Rules: A Tool for Mining Associations in Text. J Intell Inf Syst 25, 333–345 (2005). https://doi.org/10.1007/s10844-005-0196-9
Received:
Revised:
Accepted:
Issue Date:
DOI: https://doi.org/10.1007/s10844-005-0196-9