Learning Theory Analysis for Association Rules and Sequential Event Prediction

作者: Benjamin Letham , Cynthia Rudin , David Madigan

DOI:

关键词: Context (language use)Artificial intelligenceCold startStatistical learning theorySequenceGeneralizationMachine learningBayesian probabilityData miningAssociation rule learningEvent (probability theory)Computer science

摘要: We present a theoretical analysis for prediction algorithms based on association rules. As part of this analysis, we introduce problem which rules are particularly natural, called "sequential event prediction." In sequential prediction, events in sequence revealed one by one, and the goal is to determine will next be revealed. The training set collection past sequences events. An example application predict item placed into customer's online shopping cart, given his/her purchases. context problem, have distinct advantages over classical statistical machine learning methods: they look at correlations subsets co-occurring (items b imply c), can applied natural way, potentially handle "cold start" where small, yield interpretable predictions. work, two that incorporate These used both supervised classification, simple enough possibly understood users, customers, patients, managers, etc. provide generalization guarantees these algorithmic stability from theory. include discussion strict minimum support threshold often rule mining, an "adjusted confidence" measure provides weaker condition has support. paper brings together ideas theory, mining Bayesian analysis.

参考文章(19)
Ramakrishnan Srikant, Rakesh Agrawal, Fast algorithms for mining association rules very large data bases. pp. 580- 592 ,(1998)
Benjamin Letham, Cynthia Rudin, David Madigan, Sequential event prediction Machine Learning. ,vol. 93, pp. 357- 380 ,(2013) , 10.1007/S10994-013-5356-5
Grzegorz A. Rempała, Asymptotic factorial powers expansions for binomial and negative binomial reciprocals Proceedings of the American Mathematical Society. ,vol. 132, pp. 261- 272 ,(2003) , 10.1090/S0002-9939-03-07254-X
Liqiang Geng, Howard J. Hamilton, Choosing the Right Lens: Finding What is Interesting in Data Mining Quality Measures in Data Mining. pp. 3- 24 ,(2007) , 10.1007/978-3-540-44918-8_1
V. Romanovsky, Note on the Moments of a Binomial (p + q) n about its Mean Biometrika. ,vol. 15, pp. 410- ,(1923) , 10.2307/2331875
David Madigan, Krzysztof Mosurski, Russell G. Almond, Graphical Explanation in Belief Networks Journal of Computational and Graphical Statistics. ,vol. 6, pp. 160- 181 ,(1997) , 10.1080/10618600.1997.10474735
Jerome H. Friedman, Bogdan E. Popescu, Predictive learning via rule ensembles The Annals of Applied Statistics. ,vol. 2, pp. 916- 954 ,(2008) , 10.1214/07-AOAS148
Jay Ayres, Jason Flannick, Johannes Gehrke, Tomi Yiu, Sequential PAttern mining using a bitmap representation Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining - KDD '02. pp. 429- 435 ,(2002) , 10.1145/775047.775109
William DuMouchel, Daryl Pregibon, Empirical bayes screening for multi-item associations knowledge discovery and data mining. pp. 67- 76 ,(2001) , 10.1145/502512.502526
KEN MCGARRY, A survey of interestingness measures for knowledge discovery Knowledge Engineering Review. ,vol. 20, pp. 39- 61 ,(2005) , 10.1017/S0269888905000408