Multi-Dimensional Relational Sequence Mining

• Autorzy: Esposito F. , Di Mauro N. , Basile T.M.A. , Ferilli S.
• Języki publikacji: EN

Abstrakty

EN

The issue addressed in this paper concerns the discovery of frequent multi-dimensional patterns from relational sequences. The great variety of applications of sequential pattern mining, such as user profiling, medicine, local weather forecast and bioinformatics, makes this problem one of the central topics in data mining. Nevertheless, sequential information may concern data on multiple dimensions and, hence, the mining of sequential patterns from multi-dimensional information results very important. In a multi-dimensional sequence each event depends on more than one dimension, such as in spatio-temporal sequences where an event may be spatially or temporally related to other events. In literature, the multi-relational data mining approach has been successfully applied to knowledge discovery fromcomplex data. However, there exists no contribution to manage the general case of multi-dimensional data in which, for example, spatial and temporal information may co-exist. This work takes into account the possibility to mine complex patterns, expressed in a first-order language, in which events may occur along different dimensions. Specifically, multidimensional patterns are defined as a set of atomic first-order formulae in which events are explicitly represented by a variable and the relations between events are represented by a set of dimensional predicates. A complete framework and an Inductive Logic Programming algorithm to tackle this problem are presented along with some experiments on artificial and real multi-dimensional sequences proving its effectiveness.

Słowa kluczowe

EN

multi-relational sequence mining; inductive logic programming; sequence analysis

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2008
• Tom: Vol. 89, nr 1
• Strony: 23--43
• Opis fizyczny: bibliogr. 45 poz., tab., wykr.

Twórcy

autor

Esposito F.

autor

Di Mauro N.

autor

Basile T.M.A.

autor

Ferilli S.

• Universita degli Studi di Bari, Dipartimento di Informatica 70125 Bari, Italy,

Bibliografia

• [1] Agrawal, R., Manilla, H., Srikant, R., Toivonen, H., Verkamo, A.: Fast discovery of association rules, in: Advances in Knowledge Discovery and Data Mining (U. Fayyad, G. Piatetsky-Shapiro, P. Smyth, R. Uthurusamy, Eds.), AAAI Press, 1996, 307-328.
• [2] Agrawal, R., Srikant, R.: Mining sequential patterns, in: Proceedings of the Int. Conf. on Data Engineering (ICDE95), 1995, 3-14.
• [3] Allen, J., Ferguson, G.: Actions and Events in Interval Temporal Logic, Technical Report TR521, University of Rochester Rochester, NY, USA, 1994.
• [4] de Amo, S., Furtado, D.: First-order temporal pattern mining with regular expression constraints, Data &Knowledge Engineering, 62(3), 2007, 401-420.
• [5] de Amo, S., Giacometti, A., Junior, W. P.: Mining First-Order Temporal Interval Patterns with Regular Expression Constraints, in: Proceedings of the 9th International Conference on Data Warehousing and Knowledge Discovery (I. Y. Song, J. Eder, T. M. Nguyen, Eds.), vol. 4654 of LNCS, Springer, 2007, 459-469.
• [6] Bennett, B., Cohn, A. G., Wolter, F., Zakharyaschev, M.: Multi-Dimensional Modal Logic as a Framework for Spatio-Temporal Reasoning, Applied Intelligence, 17(3), 2002, 239-251.
• [7] Beyer, K. S., Ramakrishnan, R.: Bottom-Up Computation of Sparse and Iceberg CUBEs, in: Proceedings ACM SIGMOD International Conference on Management of Data (A. Delis, C. Faloutsos, S. Ghandeharizadeh, Eds.), ACM Press, 1999, 359-370.
• [8] Blockeel, H., Dehaspe, L., Demoen, B., Janssens, G., Ramon, J., Vandecasteele, H.: Executing query packs in ILP, in: Proceedings of the 10th International Conference on Inductive Logic Programming (J. Cussens, A. Frisch, Eds.), vol. 1866 of LNAI, Springer, 2000, 60-77.
• [9] Blockeel, H., F¨urnkranz, J., Prskawetz, A., Billari, F.: Detecting temporal changes in event sequences: An application to demographic data, in: Proceedings of the 5th European Conference on Principles of Data Mining and Knowledge Discovery (L. D. Raedt, A. Siebes, Eds.), vol. 2168, Springer, 2001, 29-41.
• [10] Bratko, I.: Prolog programming for artificial intelligence, 3rd ed., Addison-Wesley Longman Publishing Co., 2001, ISBN 0-201-40375-7.
• [11] Dehaspe, L., Toivonen, H.: Discovery of frequent Datalog patterns, Data Mining and Knowledge Discovery, 3(1), 1999, 7-36.
• [12] Gardner, M.: The fantastic combinations of John Conway's new solitaire game "life", Scientific American, 2(223), October 1970, 120-123.
• [13] Garofalakis, M. N., Rastogi, R., Shim, K.: SPIRIT: Sequential Pattern Mining with Regular Expression Constraints, in: Proceedings of 25th International Conference on Very Large Data Bases (M. P. Atkinson, M. E. Orlowska, P. Valduriez, S. B. Zdonik,M. L. Brodie, Eds.), Morgan Kaufmann, 1999, 223-234.
• [14] Greenberg, S.: Using Unix: collected traces of 168 users, Research Report 88/333/45, Department of Computer Science, University of Calgary, Alberta, 1988.
• [15] Han, J., Pei, J., Yin, Y.: Mining frequent patterns without candidate generation, in: Proceedings of the 2000 ACM SIGMOD international conference on Management of data, ACM, 2000, 1-12.
• [16] Harinarayan, V., Rajaraman, A., Ullman, J. D.: Implementing Data Cubes Efficiently, in: Proceedings of the 1996 ACM SIGMOD International Conference on Management of Data (H. V. Jagadish, I. S.Mumick, Eds.), ACM Press, 1996, 205-216.
• [17] Jacobs, N.: Relational Sequence Learning and User Modelling, Ph.D. Thesis, Department of Computer Science, K.U.Leuven, Leuven, Belgium, October 2004.
• [18] Jacobs, N., Blockeel, H.: From shell logs to shell scripts, in: Proceedings of the 11th International Conference on Inductive Logic Programming (C. Rouveirol, M. Sebag, Eds.), vol. 2157, Springer, 2001, 80-90.
• [19] Kamber, M., Han, J., Chiang, J.: Metarule-Guided Mining of Multi-Dimensional Association Rules Using Data Cubes, in: Proceeding of the 3rd International Conference on Knowledge Discovery and Data Mining, 1997, 207-210.
• [20] Kaplan, C. A., Fenwick, J., Chen, J.: Adaptive Hypertext Navigation Based On User Goals and Context, User Modeling and User-Adapted Interaction, 3(3), 1993, 193-220.
• [21] Kersting, K., Gärtner, T.: Fisher Kernels for Logical Sequences, in: Proceedings of the 15th European Conference on Machine Learning (J.-F. Boulicaut, F. Esposito, F. Giannotti, D. Pedreschi, Eds.), vol. 3201 of LNCS, Springer, 2004, 205-216.
• [22] Kersting, K., Raedt, L. D., , Raiko, T.: Logical Hidden Markov Models, Journal of Artificial Intelligence Research, 25, 2006, 425-456.
• [23] Kersting, K., Raiko, T.: 'Say EM' for Selecting ProbabilisticModels for Logical Sequences, in: Proceedings of the 21st Conference on Uncertainty in Artificial Intelligence (F. Bacchus, T. Jaakkola, Eds.), AUAI Press, 2005, 300-307.
• [24] Lavrac, N., Dzeroski, S.: Inductive Logic Programming: Techniques and Applications., Ellis Horwood, New York, 1994.
• [25] Lee, S., De Raedt, L.: Constraint based mining of first order sequences in SeqLog, in: Database Support for Data Mining Applications (R. Meo, P. Lanzi, M. Klemettinen, Eds.), vol. 2682 of LNCS, Springer, 2004, 155-176.
• [26] Lenat, D.: The Dimensions of Context-Space, Cycorp, 1998.
• [27] Liao, L., Patterson, D. J., Fox, D., Kautz, H. A.: Learning and inferring transportation routines, Artificial Intelligence, 171(5-6), 2007, 311-331.
• [28] Malerba, D., Lisi, F.: Discovering associations between spatial objects: An ilp application, in: Proceedings of the 11th International Conference on Inductive Logic Programming, vol. 2157 of LNCS, Springer, 2001, 156-166.
• [29] Masson, C., Jacquenet, F.: Mining frequent logical sequences with SPIRIT-LoG, in: Proceedings of the 12th International Conference on Inductive Logic Programming (S. Matwin, C. Sammut, Eds.), vol. 2583 of LNAI, Sringer, 2003, 166-181.
• [30] McCarthy, J., Hayes, P.: Some Philosophical Problems from the Standpoint of Artificial Intelligence, in: Machine Intelligence 4 (B. Meltzer, D. Michie, Eds.), Edinburgh University Press, 1969, 463-502.
• [31] Moyle, S., Muggleton, S.: Learning Programs in the Event Calculus, in: Proceedings of the 7th International Workshop on Inductive Logic Programming, Springer, 1997, 205-212.
• [32] Muggleton, S., De Raedt, L.: Inductive Logic Programming: Theory and Methods, Journal of Logic Programming, 19/20, 1994, 629-679.
• [33] Pei, J., Han, J.,Mortazavi-Asl, B., Pinto, H., Chen, Q., Dayal, U., Hsu,M.-C.: PrefixSpan: Mining Sequential Patterns Efficiently by Prefix-Projected Pattern Growth, Proceedings of the 17th International Conference on Data Engineering, 2001, 215-226.
• [34] Pei, P., Han, J., Wang, W.: Mining Sequential Patterns with Constraints in Large Databases, in: Proceedings of the 11th ACM International Conference on Information and Knowledge Management, 2002, 18-25.
• [35] Pinto, H., Han, J., Pei, J., Wang, K., Chen, Q., Dayal, U.: Multi-dimensional sequential pattern mining, in: Proceedings of the tenth international conference on Information and knowledge management, ACM Press, 2001, 81-88.
• [36] Popel´ınsky, L.: Knowledge Discovery in Spatial Data by Means of ILP, in: Proceedings of the Second European Symposium on Principles of Data Mining and Knowledge Discovery, Springer, 1998, 185-193.
• [37] Randell, C., Muller, H.: Context Awareness by Analysing Accelerometer Data, in: The Fourth International Symposium on Wearable Computers (B. MacIntyre, B. Iannucci, Eds.), IEEE Computer Society, 2000, ISBN 1530-0811, 175-176.
• [38] Rodrıguez, J., Alonso, C., Böstrom, H.: Learning first order logic time series classifiers, in: Proceedings of the 10th International Workshop on Inductive Logic Programming (J. Cussens, A. Frisch, Eds.), Springer, 2000, 260-275.
• [39] Si, H., Kawahara, Y., Morikawa, H., Aoyama, T.: A Stochastic Approach for Creating Context-Aware Services based on Context Histories in Smart Home, in: Proceeding of the 3rd International Conference on Pervasive Computing, Exploiting Context Histories in Smart Environments, 2005, 37-41.
• [40] Siewiorek, D., Smailagic, A., Furukawa, J., Krause, A., Moraveji, N., Reiger, K., Shaffer, J., Wong, F. L.: SenSay: A Context-Aware Mobile Phone, in: Proceedings of the 7th IEEE International Symposium on Wearable Computers, IEEE, 2003, 248-249.
• [41] Souchon, N., Limbourg, Q., Vanderdonckt, J.: Task Modelling in Multiple Contexts of Use, in: Proceedings of the 9th International Workshop on Interactive Systems. Design, Specification, and Verification, Springer, 2002, ISBN 3-540-00266-9, 59-73.
• [42] Ullman, J.: Principles of Database and Knowledge-Base Systems, vol. I, Computer Science Press, 1988.
• [43] Yu, C.-C., Chen, Y.-L.: Mining Sequential Patterns from Multidimensional Sequence Data, IEEE Transactions on Knowledge and Data Engineering, 17(1), 2005, 136-140, ISSN 1041-4347.
• [44] Zaki,M.: SPADE: An efficient algorithmfor mining frequent sequences, Machine Learning Journal: Special issue on Unsupervised Learning, 42(1/2), 2001, 31-60.
• [45] Zhao, Q., Bhowmick, S.: Sequential pattern mining: a survey, Technical report, Center for Advanced Information Systems, School of Computer Engineering,Nanyang TechnologicalUniversity, Singapore, 2003.