Comparing association rules and decision trees for disease prediction

ABSTRACT

Association rules represent a promising technique to find hidden patterns in a medical data set. The main issue about mining association rules in a medical data set is the large number of rules that are discovered, most of which are irrelevant. Such number of rules makes search slow and interpretation by the domain expert difficult. In this work, search constraints are introduced to find only medically significant association rules and make search more efficient. In medical terms, association rules relate heart perfusion measurements and patient risk factors to the degree of stenosis in four specific arteries. Association rule medical significance is evaluated with the usual support and confidence metrics, but also lift. Association rules are compared to predictive rules mined with decision trees, a well-known machine learning technique. Decision trees are shown to be not as adequate for artery disease prediction as association rules. Experiments show decision trees tend to find few simple rules, most rules have somewhat low reliability, most attribute splits are different from medically common splits, and most rules refer to very small sets of patients. In contrast, association rules generally include simpler predictive rules, they work well with user-binned attributes, rule reliability is higher and rules generally refer to larger sets of patients.

REFERENCES

• 1: Rakesh Agrawal , Tomasz Imieliński , Arun Swami, Mining association rules between sets of items in large databases, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.207-216, May 25-28, 1993, Washington, D.C., United States
• 2: Rakesh Agrawal , Ramakrishnan Srikant, Fast Algorithms for Mining Association Rules in Large Databases, Proceedings of the 20th International Conference on Very Large Data Bases, p.487-499, September 12-15, 1994
• 3: Yves Bastide , Nicolas Pasquier , Rafik Taouil , Gerd Stumme , Lotfi Lakhal, Mining Minimal Non-redundant Association Rules Using Frequent Closed Itemsets, Proceedings of the First International Conference on Computational Logic, p.972-986, July 01, 2000
• 4: Constraint-Based Rule Mining in Large, Dense Databases, Proceedings of the 15th International Conference on Data Engineering, p.188, March 23-26, 1999
• 5: C. Becquet, S. Blachon, B. Jeudy, J.F. Boulicaut, and O. Gandrillon. Strong association-rule mining for large-scale gene-expression data analysis: a case study on human {SAGE data. Genom Biol., 3(12), 2002.
• 6: Sergey Brin , Rajeev Motwani , Jeffrey D. Ullman , Shalom Tsur, Dynamic itemset counting and implication rules for market basket data, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.255-264, May 11-15, 1997, Tucson, Arizona, United States
• 7: S.E. Brossette, A.P. Sprague, J.M. Hardin, K.B. Waites, W.T. Jones, and S.A. Moser. Association rules and data mining in hospital infection control and public health surveillance. J Am Med Inform Assoc. (JAMIA), 5(4):373--381, 1998.
• 8: S.E. Brossette, A.P. Sprague, W.T. Jones, and S.A. Moser. A data mining system for infection control surveillance. Methods Inf Med., 39(4):303--310, 2000.
• 9: Artur Bykowski , Christophe Rigotti, DBC: a condensed representation of frequent patterns for efficient mining, Information Systems, v.28 n.8, p.949-977, December 2003 [doi>10.1016/S0306-4379(03)00002-4]
• 10: T.J. Chen, L.F. Chou, and S.J. Hwang. Application of a data mining technique to analyze coprescription patterns for antacids in {Taiwan. Clin Ther, 25(9):2453--2463, 2003.
• 11: C. Creighton and S. Hanash. Mining gene expression databases for association rules. Bioinformatics, 19(1):79--86, 2003.
• 12: M. Delgado, D. Sanchez, M.J. Martin-Bautista, and M.A. Vila. Mining association rules with improved semantics in medical databases. Artificial Intelligence in Medicine, 21(1-3):241--5, 2001.
• 13: S.M. Down and M.Y. Wallace. Mining association rules from a pediatric primary care decision support system. In Proc of AMIA Symp., pages 200--204, 2000.
• 14: U. Fayyad and G. Piateski-Shapiro. From Data Mining to Knowledge Discovery. MIT Press, 1995.
• 15: H.S. Fraser, W.J. Long, and S. Naimi. Evaluation of a cardiac diagnostic program in a typical clinical setting. J Am Med Inform Assoc. (JAMIA), 10(4):373--381, 2003.
• 16: Alex A. Freitas, Understanding the crucial differences between classification and discovery of association rules: a position paper, ACM SIGKDD Explorations Newsletter, v.2 n.1, p.65-69, June, 2000 [doi>10.1145/360402.360423]
• 17: Jiawei Han , Micheline Kamber, Data mining: concepts and techniques, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2000
• 18: T. Hastie, R. Tibshirani, and J.H. Friedman. The Elements of Statistical Learning. Springer, New York, 1st edition, 2001.
• 19: Marzena Kryszkiewicz, Concise Representation of Frequent Patterns Based on Disjunction-Free Generators, Proceedings of the 2001 IEEE International Conference on Data Mining, p.305-312, November 29-December 02, 2001
• 20: Marzena Kryszkiewicz, Reducing borders of k-disjunction free representations of frequent patterns, Proceedings of the 2004 ACM symposium on Applied computing, March 14-17, 2004, Nicosia, Cyprus [doi>10.1145/967900.968017]
• 21: Brian Lent , Arun N. Swami , Jennifer Widom, Clustering Association Rules, Proceedings of the Thirteenth International Conference on Data Engineering, p.220-231, April 07-11, 1997
• 22: W. Long, Medical diagnosis using a probabilistic causal network, Applied Artificial Intelligence, v.3 n.2-3, p.367-383, 1989 [doi>10.1080/08839518908949932]
• 23: W.J. Long, H.S. Fraser, and S. Naimi. Reasoning requirements for diagnosis of heart disease. Artificial Intelligence in Medicine, 10(1):5--24, 1997.
• 24: Raymond T. Ng , Laks V. S. Lakshmanan , Jiawei Han , Alex Pang, Exploratory mining and pruning optimizations of constrained associations rules, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.13-24, June 01-04, 1998, Seattle, Washington, United States
• 25: Carlos Ordonez , Norberto Ezquerra , Cesar A. Santana, Constraining and summarizing association rules in medical data, Knowledge and Information Systems, v.9 n.3, p.259-283, March 2006 [doi>10.1007/sl0115-005-0226-5]
• 26: Carlos Ordonez , Edward Omiecinski , Levien de Braal , Cesar A. Santana , Norberto Ezquerra , Jose A. Taboada , David Cooke , Elizabeth Krawczynska , Ernest V. Garcia, Mining Constrained Association Rules to Predict Heart Disease, Proceedings of the 2001 IEEE International Conference on Data Mining, p.433-440, November 29-December 02, 2001
• 27: T. Oyama, K. Kitano, T. Satou, and T. Ito. Extraction of knowledge on protein-protein interaction by association rule discovery. Bioinformatics, 18(5):705--714, 2002.
• 28: Viet Phan Luong, The Representative Basis for Association Rules, Proceedings of the 2001 IEEE International Conference on Data Mining, p.639-640, November 29-December 02, 2001
• 29: John F. Roddick , Peter Fule , Warwick J. Graco, Exploratory medical knowledge discovery: experiences and issues, ACM SIGKDD Explorations Newsletter, v.5 n.1, p.94-99, July 2003 [doi>10.1145/959242.959243]
• 30: Ramakrishnan Srikant , Rakesh Agrawal, Mining Generalized Association Rules, Proceedings of the 21th International Conference on Very Large Data Bases, p.407-419, September 11-15, 1995
• 31: Ramakrishnan Srikant , Rakesh Agrawal, Mining quantitative association rules in large relational tables, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.1-12, June 04-06, 1996, Montreal, Quebec, Canada
• 32: R. Srikant, Q. Vu, and R. Agrawal. Mining association rules with item constraints. In ACM KDD Conference, pages 67--73, 1997.
• 33: Mining Bases for Association Rules Using Closed Sets, Proceedings of the 16th International Conference on Data Engineering, p.307, February 28-March 03, 2000
• 34: Ke Wang , Yu He , Jiawei Han, Pushing Support Constraints Into Association Rules Mining, IEEE Transactions on Knowledge and Data Engineering, v.15 n.3, p.642-658, March 2003 [doi>10.1109/TKDE.2003.1198396]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

Additional Classification:
  J. Computer Applications
  J.3 LIFE AND MEDICAL SCIENCES
      Subjects: Health

General Terms:
Algorithms, Experimentation

Keywords:
association rule, decision tree, medical data