TRiER: A Fast and Scalable Method for Mining Temporal Exception Rules

• Thábata Amaral USP
• Elaine P. M. de Sousa USP

DOI: https://doi.org/10.5753/sbbd.2019.8803

Resumo

Association rules are a common task to discover useful and comprehensive relationships among items. Our interest is to find exception rules, i.e. patterns that rarely occur but have critical consequences. Existing approaches for exception rules usually handle Itemset databases and are unfeasible for mining large ones due to high computational complexity. We thus propose TRiER (TempoRal Exception Ruler), an efficient method for mining temporal exception rules that not only discover unusual behaviors and their causative agents, but also identifies how long consequences take to appear. We performed an extensive experimental analysis in real data and results show TRiER is faster and more scalable than existing approaches while finding meaningful rules.

Palavras-chave: exception rules, patterns, temporal exception rules, temporal exception mining, multivariate time series

Referências

Agrawal, R., Imielinski, T., and Swami, A. (1993). Mining association rules between sets of items in large databases. In Proceedings of SIGMOD, pages 207–216. DOI: https://doi.org/10.1145/170036.170072

Agrawal, R. and Srikant, R. (1995). Mining sequential patterns. In Proceedings of ICDE, pages 3–14. DOI: https://doi.org/10.1109/ICDE.1995.380415

Berzal, F., Blanco, I., S´anchez, D., and Vila, M. (2002). Measuring the accuracy and interest of association rules: a new framework. Intelligent Data Analysis, pages 221– 235. DOI: https://doi.org/10.3233/IDA-2002-6303

Calvo-Flores, M., Ruiz, M., and S´anchez, D. (2011). New approaches for discovering exception and anomalous rules. International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, 19:361–399. DOI: https://doi.org/10.1142/S0218488511007039

Daly, O. and Taniar, D. (2008). Exception rules in data mining. Applied Mathematics and Computation, pages 735–750. DOI: https://doi.org/10.1016/j.amc.2008.05.020

Dong, G. (2009). Sequence data mining. Springer-Verlag, Berlin, Germany. DOI: https://doi.org/10.1007/3-540-45571-X_11

Hussain, F., Liu, H., Suzuki, E., and Lu, H. (2000). Exception rule mining with a relative interestingness measure. In Proceedings of KDD, pages 86–97. DOI: https://doi.org/10.1007/3-540-45571-X_11

Mitsa, T. (2010). Temporal data mining. Chapman & Hall/CRC, Minneapolis, U.S.A. DOI: https://doi.org/

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 ICDE, pages 215–224. DOI: https://doi.org/10.1109/ICDE.2001.914830

Ruiz, M. D., S´anchez, D., Delgado, M., and Martin-Bautista, M. J. (2016). Discovering fuzzy exception and anomalous rules. IEEE Transactions on Fuzzy Systems, 24(4):930–944. DOI: https://doi.org/10.1109/TFUZZ.2015.2489240

Srikant, R. and Agrawal, R. (1996). Mining sequential patterns: Generalizations and performance improvements. In Apers, P., Bouzeghoub, M., and Gardarin, G., editors, Advances in Database Technology — EDBT ’96, pages 1–17, Berlin, Heidelberg. Springer Berlin Heidelberg. DOI: https://doi.org/10.1007/bfb0014140

Suzuki, E. (1996). Discovering unexpected exceptions : a stochastic approach. Proceedings of RSFD 1996, pages 259–262. DOI: https://doi.org/10.1007/3-540-46846-3_17

Zaki, M. J. (2000). Scalable algorithms for association mining. IEEE Transactions on Knowledge and Data Engineering, pages 372–390. DOI: https://doi.org/10.1109/69.846291

Zaki, M. J. (2001). Spade: An efficient algorithm for mining frequent sequences. Machine Learning, pages 31–60. DOI: https://doi.org/10.1023/A:1007652502315