Abstract

Classification is an important task in data mining and machine learning, which has been studied extensively and has a wide range of applications. Lots of algorithms have been proposed to build accurate and scalable classifiers. Most of these algorithms can only applied to single “flat“ relations, whereas in the real world most data are stored in multiple tables. As converting data from multiple relations into single flat relation usually causes many problems, development of classification across multiple database relations becomes important. In this paper, we present the several kinds of classification method across multiple database relations including Inductive Logic Programming (ILP) , Relational database , Emerging Pattern , Associative approaches and their characteristics, the comparisons in detail.

References

• Appice, A., Ceci M., Malgieri C., Maleraba D. 2007. Discovering relational emerging patters, AI*AI 2007, LNCS (LNAI), Vol. 4733, 206-217, springer,Heidelberg.
• Atramentov, A., Leiva, H., and Honavar, V. 2003. A Multi- relational Decision Tree Learning Algorithm- Implementation and Experiments, ILP LNCS, Vol.2835, pp. 38-56.
• Blockeel, H. 1998. Top-down induction of first order logical decision trees, Artificial Intelligence Journal, vol.101, pp.285-297.
• Ceci, M., Appice, A., and Malerb, D.2003. Mr-SBC: a Multi-Relational Naïve Bayes Classifier, Knowledge Discovery in Databases PKDD 2003, LNAI, vol.2838, pp.95-106.
• Ceci, M., Appice, A., Maleraba, D. 2008. Emerging Pattern Based Classification in Relational Data Mining, DEXA 2008, LNCS, vol.5181, pp.283-296.
• Chen, H., Liu, H., Han, J., Yin, X. 2009. Exploring Optimization of Semantic Relationship Graph for Multi-relational Bayesian Classification, In Decision Support System, Vol.48, pp.112-121.
• Cheng, Q. 2007. PRM based multi relational association rule mining, Thesis Report, Simon Fraser University.
• Cumby, C., Roth, D. 2003. On kernel methods for relational learning, In Proceedings of 20th International Conf. on Machine Learning (ICML-2003,) Washington.
• De Raedt, L. 2008. Kernels and Distances for Structured Data: Logical and Relational Learning, 289-324, springer.
• Dehaspe, L., Raedt, D. 1997. Mining Association Rules in Multiple Relations, In Proceedings of the ILP, Springer-Verlang, London UK, pp.125-132.
• Dong, G., Li, J. 1999. Efficient mining of emerging patterns: Discovery trends and differences, In International Conference on Knowledge Discovery and Data Mining, pp. 43-52. ACM Press, New York.
• Dong, G., Zhang, X., Wong, L., and Li, J. 1999. CAEP: Classification by aggregating emerging patterns, In Proceedings of the Second International Conference on Discovery Science, Tokyo, Japan, pages 30-42.
• Dzeroski, S. 2003. Multi-relational data mining: an introduction, [J]. SIGKDD Explorations, vol. 5(1):1-16.
• Dzeroski, S., Lavtac, N. 2001. eds, Relational data mining, Berlin: Springer.
• Emde, W., Wettschereck, D. 1996. Relational instance–based learning, In Proceedings of the 13th Int. Conference on Machine Learning, Morgan Kaufmann, San Mateo, CA, 122-130.
• Fan, H., Ramamonanarao, K. 2002. An efficient single scan algorithm for mining essential jumping emerging patterns for classification, In Pacific-Asia Conference on Knowldege Discovery and Data Mining , pp.456-462.
• Frank, R., Moser, F., Ester, M. 2007. A Method for Multi-Relational Classification Using Single and Multi-Feature Aggregation Functions, In Proceedings of 11th European Conf. on PKDD, Springer, Verlag Berlin Heidelberg.
• Gaertner, T., Flach, P., Kowalczyk, A. 2002. Multi-instance kernels, In Proceedings of 19th International Conf. on Machine Learning, pp.179-186.
• Gaertner, T., Lloyed, J., Flach, P. 2004. Kernels and distances for structured data, In Machine Learning, vol.57, No.3, pp.205-332.
• Getoor, L. 2001. Multi-Relational Data Mining was using probabilistic Models Research Summary, In Proc. Of 1st workshop in MRDM.
• Getoor, L., Friedman, N., Koller, D., and Pfeffer, A. 2001. Learning Probabilistic Relational Models, pp.307-355, Springer Verlage, New York.
• Getoor, L., Friedman, N., Koller, D., Taskar, B. 2001. Learning Probabilistic Models of Relational Structure, ICMl’01 Proceedings of 8th International Conference on Machine Learning.
• Gu,Y., Liu, H., He, J. 2009. MrCAR: A Multi relational Classification Algorithm based on Association Rules, Int. Conf. on Web Information Systems and Mining, pp.256-260.
• Guo, H., Herna, L., Viktor. 2008. Multirelational classification: a multiple view approach, Knowl. Inf. Systems, vol.17, pp.287–312, Springer-Verlag London.
• Guo, JF., Li, J., Bian, WF. 2007. An Efficient Relational Decision Tree Classification Algorithm, In proceedings of 3rd ICNC, vol.3.
• Han, J., Kamber, M. 2007. Data Mining: Concepts and Techniques”, 2nd Edition, Morgan Kaufmann.
• H, J. Liu,H.,et at, 2010. Selecting Effective Features and Relations For EfficientMulti-Relational Classification, Computational Intelligence, Vol 26, No.3.
• Horva, T., Wrobel, S., Bohnebeck, U. 2001. Relational Instance-Based Learning with Lists and Terms, Machine Learning, vol.43, pp.53–80.
• Kalousis, A., Woznica, A., and Hilario, M. 2006. A unifying framework for relational distance-based learning founded on relational algebra, Technical Report, University of Geneva..
• Kirsten, M., Wrobel, S., Horvath, T. 2002.Distance Based Approaches to Relational Learning and Clustering: Relational Data Mining, Morgan Kaufmann (2005) 6, pp.213-232, springer, Heidelberg.
• Koller, Pfeffer, A. 1998. Probabilistic frame-based systems, In Proceedings of the 15th National Conference on Artificial Intelligence, pp. 580–587, Madison, WI.
• Kramer, S., Widmer, G. 2001. Inducing Classification and Regression Tress in First Order Logic: Relational Data Mining, pp.140-159, Springer.
• Leiva, HA. 2002. A multi-relational decision tree learning algorithm, ISU-CS-TR, Lowa State University, pp.02-12.
• Li, J., Dong, G., Ramamohanarao, K., Wong, L. 2004. A new instance-based lazy discovery and classification system”, Machine Learning , vol.54, No.2, pp0. 99-124.
• Li, J., Dong, Ramamohanarao, K. 2000. DeEPs: Instance-based classification by emerging patterns, Technical Report, Dept of CSSE, University of Melbourne.
• Li, W., Han, J., Pei, J. 2001. CMAR: Accurate and efficient Classification Based on Multiple Class Association Rules, In Proceedings of the ICDM, IEEE Computer Society, San Jose California, pp.369-376.
• Li, J., Dong, G., and Ramamohanarao, K.1999. JEP-Classifier. Classification by Aggregating Jumping Emerging Patterns, Technical report, Univ of Melbourne.
• Liu, H., Yin, X., and Han, J. 2005. A Efficient Multi-relational Naïve Bayesian Classifier Based on Semantic Relationship Graph, In MRDM’05 Proceedings of 4th international workshop on MRDM.
• Muggleton, SH. 2000. Learning Stochastic Logic Programs, In Proceedings of the AAAI-2000 Workshop on Learning Statistical Models from Relational Data, Technical Report WS-00-06, pp. 36-41.
• Nijssen, S., Kok, J. 2001. Faster Association Rules for Multiple Relations, In Proceedings of the IJCAI, pp.891-896.
• Pan Cao, Wang Hong-yuan. 2009. Multi-relational classification on the basis of the attribute reduction twice, Communication and Computer,Vol. 6, No.11. pp: 49-52.
• Taskar B, Segal E, Koller D, “Probabilistic Classification and Clustering in Relational Data”, In Proceedings of International Conf. Artificial Intelligence, vol.2,2001.
• Woznica, A, Kalousis A, and Hilario M, “ Kernel-based distances for relational learning,” In Proceedings of the workshop on Multi-Relational Data Mining at KDD -2004.
• Wrobel S, “Inductive Logic Programming for Knowledge Discovery in Databases: Relational Data Mining”, Berlin: Springer, pp.74-101, 2001.
• Xu GM, Yang BR, Qin YQ, “ New multi relational naïve Bayesian classifier”, Systems Engineering and Electronics, vol. 30, No.4, pp 655-655, 2008.
• Yin X., Han J, “CPAR: Classification based on Predictive Association Rules”, In Proceedings of the SDM, SIAM, Francisco California, 2003.
• Yin X, Han J, and Yu PS, “CrossMine: Efficient Classification across Multiple Database Relations”. In Proceedings of 20th Int. Conf. on Data Engineering (ICDE’04), 2004.
• Yin X, Han J, and Yu PS, “Efficient Classification across Multiple Database Relations: A CrossMine Approach”, IEEE Transactions on Knowledge and Data Engineering, Vol 16, No.6, 2006.
• Yin, X., Han, J., Yang, J. 2003. Efficient Multi-relational Classification by Tuple ID Propagation, In Proceedings of KDD workshop on MRDM.
• Zhang, X., Dong, G., Ramamohanarao, K. 2000. Exploring constraints to efficiently mine emerging patterns from large high-dimensional datasets, In Proceedings of 6th SIGKDD international conference on Knowledge Discovery and Data Mining, pp. 310-314.