A Data Mining Formalization to Improve Hypergraph Minimal Transversal Computation

• Autorzy: Hébert C. , Bretto A. , Crémilleux B.
• Języki publikacji: EN

Abstrakty

EN

Finding hypergraph transversals is a major algorithmic issue which was shown having many connections with the data mining area. In this paper, by defining a new Galois connection, we show that this problem is closely related to the mining of the so-called condensed representations of frequent patterns. This data mining formalization enables us to benefit from efficient algorithms dedicated to the extraction of condensed representations. More precisely, we demonstrate how it is possible to use the levelwise framework to improve the hypergraph minimal transversal computation by exploiting an anti-monotone constraint to safely prune the search space. We propose a new algorithm MTminer to extract minimal transversals and provide experiments showing that our method is efficient in practice.

Słowa kluczowe

EN

data mining; hypergraph minimal transversals; levelwise framework; condensed representations

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2007
• Tom: Vol. 80, nr 4
• Strony: 415--433
• Opis fizyczny: bibliogr. 23 poz., rys., tab.

Twórcy

autor

Hébert C.

autor

Bretto A.

autor

Crémilleux B.

• GREYC, CNRS-UMR 6072, Campus Côte de Nacre, boulevard du Maréchal Juin BP 5186, 14032 Caen Cedex,

Bibliografia

• [1] Bailey, J., Manoukian, T., Ramamohanarao, K.: A Fast Algorithm for Computing Hypergraph Transversals and its Application in Mining Emerging Patterns, Proceedings of the 3rd IEEE International Conference on Data Mining (ICDM'03), IEEE Computer Society, Los Alamitos, CA, USA, 2003.
• [2] Berge, C.: Hypergraphs: Combinatorics of Finite Sets, North-Holland, Amsterdam, 1989.
• [3] Boros, E., Elbassioni, K., Gurvich, V., Khachiyan, L.: An Efficient Implementation of a Quasi-Polynomial Algorithm for Generating Hypergraph Transversals, Proceedings of the 11th Annual European Symposium on Algorithms (ESA'03), LNCS 2832, Springer, Budapest, Hungary, 2003.
• [4] Boulicaut, J. F., Bykowski, A., Rigotti, C.: Free-sets: a Condensed Representation of Boolean Data for the Approximation of Frequency Queries, Data Mining and Knowledge Discovery journal, 7(1), 2003, 5-22.
• [5] Calders, T., Goethals, B.: Minimal k-Free Representations of Frequent Sets, Proceedings of the 7th European Conference on Principles and Practice of Knowledge Discovery in Databases (PKDD'03), LNAI 2838, Springer, Dubvronik, Croatia, 2003.
• [6] Damaschke, P.: Parameterized Enumeration, Transversals, and Imperfect Phylogeny Reconstruction, Proceedings of the 1st InternationalWorkshop on Parameterized and Exact Computation, LNCS 3162, Springer, Bergen, Norway, 2004.
• [7] Denecke, K., Wismath, S. L.: Universal Algebra and Applications in Theoretical Computer Science, Chapman and Hall/CRC, 2002.
• [8] Durand, N., Crémilleux, B., Suzuki, E.: Visualizing Transactional Data with Multiple Clusterings for Knowledge Discovery, Proceedings of the 16th International Symposium on Methodologies for Intelligent Systems (ISMIS 2006), LNAI 4203, Springer, Bari, Italy, 2006.
• [9] Eiter, T., Gottlob, G.: Hypergraph Transversal Computation and Related Problems in Logic and AI, Proceedings of the 8th European Conference on Logic in Artificial Intelligence (JELIA'02), LNCS 2424, Springer, Cosenza, Italy, 2002.
• [10] Erdös, P., Rényi, A.: On Random Graphs, Publicationes Mathematicae, 6, 1959, 290-297.
• [11] Fredman,M. L., Khachiyan, L.: On the Complexity of Dualization of Monotone Disjunctive Normal Forms, Journal of Algorithms, 21(3), 1996, 618-216.
• [12] Gunopulos, D., Khardon, R., Mannila, H., Saluja, S., Toivonen, H., Sharm, R. S.: Discovering all most specific sentences, ACM Transactional Database System, 28(2), 2003, 140-174.
• [13] Gunopulos, D., Khardon, R., Mannila, H., Toivonen, H.: Data mining, Hypergraph Transversals, and Machine Learning, Proceedings of the 16th ACMSIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS'97), ACM Press, Tucson, Arizona, 1997.
• [14] Hébert, C., Crémilleux, B.: Mining Frequent _-Free Patterns in Large Databases, Proceedings of the 8th International Conference on Discovery Science (DS'05), LNAI 3735, Springer-Verlag, Singapore, 2005.
• [15] Kavvadias, D. J., Stavropoulos, E. C.: Evaluation of an Algorithm for the Transversal Hypergraph Problem, Proceedings of the 3rd Workshop on Algorithm Engineering (WAE'99), LNCS 1668, Springer, London, UK, 1999.
• [16] Kavvadias, D. J., Stavropoulos, E. C.: An Efficient Algorithm for the Transversal Hypergraph Generation, Journal of Graph Algorithms and Applications, 9(2), 2005, 239-264.
• [17] Khachiyan, L., Boros, E., Elbassioni, K. M., Gurvich, V.: A New Algorithm for the Hypergraph Transversal Problem, Proceedings of the 11th International Computing and Combinatorics Conference (COCOON'05), LNCS 3595, Springer, Kunming, China, 2005.
• [18] Lhote, L., Rioult, F., Soulet, A.: Average Number of Frequent (Closed) Patterns in Bernoulli and Markovian Databases, Proceedings of the 5th IEEE International Conference on Data Mining (ICDM'05), Houston, Texas, 2005.
• [19] Mannila, H., Toivonen, H.: Levelwise Search and Borders of Theories in KnowledgeDiscovery, DataMining and Knowledge Discovery journal, 1(3), 1997, 241-258.
• [20] Pasquier, N., Bastide, Y., Taouil, R., Lakhal, L.: Discovering Frequent Closed Itemsets for Association Rules, Proceedings of 7th International Conference on Database Theory (ICDT'99), LNAI 1331, Springer Verlag, Jerusalem, Israel, 1999.
• [21] Satoh, K., Uno, T.: Enumerating Maximal Frequent Sets Using Irredundant Dualization, Proceedings of the 6th International Conference on Discovery Science (DS'03), LNCS 2843, Springer, Sapporo, Japan, 2003.
• [22] Soulet, A., Crémilleux, B., Rioult, F.: Condensed Representation of EPs and Patterns Quantified by Frequency-based Measures, Proceedings of the 4th International Workshop on Knowledge Discovery in Inductive Databases (KDID'05), LNCS 3377, Springer, Porto, Portugal, 2005.
• [23] Wahlström, M.: Exact Algorithms for Finding Minimum Transversals in Rank-3 Hypergraphs, Journal of Algorithms, 51(2), 2004, 107-121.