Associative classifier

An associative classifier (AC) is a kind of supervised learning model that uses association rules to assign a target value. The term associative classification was coined by Bing Liu et al.,[1] in which the authors defined a model made of rules "whose right-hand side are restricted to the classification class attribute".

Model

The model generated by an AC and used to label new records consists of association rules, where the consequent corresponds to the class label. As such, they can also be seen as a list of "if-then" clauses: if the record matches some criteria (expressed in the left side of the rule, also called antecedent), it is then labeled accordingly to the class on the right side of the rule (or consequent).

Most ACs read the list of rules in order, and apply the first matching rule to label the new record.[2]

More recent approaches have formulated the problem of combining pre-mined association rules in a decision list or rule list optimally. These methods use different forms of Occam's razor (the rule of parsimony) and can divided in three main types based on the theory used:

\end{enumerate} The first approach finds decision lists and solves the problem optimally through a branch-and-bound algorithm. The second finds a probabilistic rule list for binary classification and resorts to a Markov Chain Monte Carlo (MCMC) that approximately solves the problem, as it only accepts small amounts of pre-mined rules. The third, also finds a probabilistic rule list although for multiclass classification, and uses a greedy algorithm to scale for large datasets.

Metrics

The rules of an AC inherit some of the metrics of association rules, like the support or the confidence.[7] Metrics can be used to order or filter the rules in the model[8] and to evaluate their quality.

Implementations

The first proposal of a classification model made of association rules was CBA,[1] although other authors had previously proposed the mining of association rules for classification.[9] Other authors have since then proposed multiple changes to the initial model, like the addition of a redundant rule pruning phase[10] or the exploitation of Emerging Patterns.[11]

Notable implementations include:

References
  1. Liu, Bing; Hsu, Wynne; Ma, Yiming (1998). "Integrating Classification and Association Rule Mining": 80––86. CiteSeerX 10.1.1.48.8380. Cite journal requires |journal= (help)
  2. Thabtah, Fadi (2007). "A review of associative classification mining" (PDF). The Knowledge Engineering Review. 22 (1): 37–65. doi:10.1017/s0269888907001026. ISSN 0269-8889.
  3. Angelino, Elaine; Larus-Stone, Nicholas; Alabi, Daniel; Seltzer, Margo; Rudin, Cynthia (1 January 2017). "Learning certifiably optimal rule lists for categorical data". The Journal of Machine Learning Research. 18 (1): 8753–8830. arXiv:1704.01701. ISSN 1532-4435.
  4. Letham, Benjamin; Rudin, Cynthia; McCormick, Tyler H.; Madigan, David (September 2015). "Interpretable classifiers using rules and Bayesian analysis: Building a better stroke prediction model". Annals of Applied Statistics. 9 (3): 1350–1371. arXiv:1511.01644. doi:10.1214/15-AOAS848. ISSN 1932-6157. S2CID 17699665.
  5. Yang, Hongyu; Rudin, Cynthia; Seltzer, Margo (17 July 2017). "Scalable Bayesian Rule Lists". International Conference on Machine Learning. PMLR: 3921–3930. arXiv:1602.08610.
  6. Proença, Hugo; van Leeuwen, Matthijs (May 2019). "Interpretable multiclass classification by MDL-based rule lists". Information Sciences. 512: 1372–1393. arXiv:1905.00328. doi:10.1016/j.ins.2019.10.050. S2CID 141461238.
  7. Liao, T Warren; Triantaphyllou, Evangelos (2008). Recent Advances in Data Mining of Enterprise Data: Algorithms and Applications. Series on Computers and Operations Research. WORLD SCIENTIFIC. doi:10.1142/6689. ISBN 9789812779854. S2CID 34599426.
  8. "CBA homepage". Retrieved 2018-10-04.
  9. Ali, Kamal; Manganaris, Stefanos; Srikant, Ramakrishnan (1997-08-14). "Partial classification using association rules". KDD'97. AAAI Press: 115–118. Cite journal requires |journal= (help)
  10. Wenmin Li; Jiawei Han; Jian Pei (2001). CMAR: accurate and efficient classification based on multiple class-association rules. Proceedings 2001 IEEE International Conference on Data Mining. IEEE Comput. Soc. pp. 369–376. CiteSeerX 10.1.1.13.219. doi:10.1109/icdm.2001.989541. ISBN 978-0769511191. S2CID 2243455.
  11. Dong, Guozhu; Zhang, Xiuzhen; Wong, Limsoon; Li, Jinyan (1999), "CAEP: Classification by Aggregating Emerging Patterns", Discovery Science, Springer Berlin Heidelberg, pp. 30–42, CiteSeerX 10.1.1.37.3226, doi:10.1007/3-540-46846-3_4, ISBN 9783540667131
  12. "CMAR Implementation". cgi.csc.liv.ac.uk. Retrieved 2018-10-04.
  13. Yin, Xiaoxin; Han, Jiawei (2003), "CPAR: Classification based on Predictive Association Rules", Proceedings of the 2003 SIAM International Conference on Data Mining, Society for Industrial and Applied Mathematics, pp. 331–335, CiteSeerX 10.1.1.12.7268, doi:10.1137/1.9781611972733.40, ISBN 9780898715453
  14. "THE LUCS-KDD IMPLEMENTATIONS OF THE FOIL, PRM AND CPAR ALGORITHMS". cgi.csc.liv.ac.uk. Retrieved 2018-10-04.
  15. Baralis, E.; Chiusano, S.; Garza, P. (2008). "A Lazy Approach to Associative Classification". IEEE Transactions on Knowledge and Data Engineering. 20 (2): 156–171. doi:10.1109/tkde.2007.190677. ISSN 1041-4347. S2CID 14829459.
  16. "L3 implementation". dbdmg.polito.it. Retrieved 2018-10-08.
  17. Chen, Guoqing; Liu, Hongyan; Yu, Lan; Wei, Qiang; Zhang, Xing (2006). "A new approach to classification based on association rule mining". Decision Support Systems. 42 (2): 674–689. doi:10.1016/j.dss.2005.03.005. ISSN 0167-9236.
  18. Wang, Ke; Zhou, Senqiang; He, Yu (2000). Growing decision trees on support-less association rules. Proceedings of the Sixth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining - KDD '00. New York, New York, USA: ACM Press. CiteSeerX 10.1.1.36.9265. doi:10.1145/347090.347147. ISBN 978-1581132335. S2CID 8296096.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.