Computing Implications with Negation from a Formal Context

• Autorzy: Missaoui R. , Nourine L. , Renaud Y.
• Języki publikacji: EN

Abstrakty

EN

The objective of this article is to define an approach towards generating implications with (or without) negation when only a formal context K = (G,M, I) is provided. To that end, we define a two-step procedure which first (i) computes implications whose premise is a key in the context K| K representing the apposition of the context K and its complementary �K with attributes in M (negative attributes), and then (ii) uses an inference axiom we have defined to produce the whole set of implications.

Słowa kluczowe

EN

formal concept analysis; implication; negation; inference system

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2012
• Tom: Vol. 115, nr 4
• Strony: 357--375
• Opis fizyczny: Bibliogr. 46 poz., tab.

Twórcy

autor

Missaoui R.

autor

Nourine L.

autor

Renaud Y.

• Université du Québec en Outaouais, Département d’informatique et d'ingénierie 101, rue St-Jean Bosco, Gatineau (Québec), J8X 3X7 Canada,

Bibliografia

• [1] Agrawal, R., Imielinski, T., Swami, A.: Mining association rules between sets of items in large databases, In ACM SIGMOD conf. Management of data, May 1993, 265-290.
• [2] Agrawal, R., Srikant, R.: Fast algorithms for mining association rules, VLDB'94, Proceedings of 20th International Conference on Very Large Data Bases, September 1994, 487-499 .
• [3] Alachaher, L. N., Guillaume, S.: Mining Negative and Positive Influence Rules Using Kullback-Leibler Divergence, ICCGI '07: Proceedings of the International Multi-Conference on Computing in the Global Information Technology, IEEE Computer Society,Washington, DC, USA, 2007.
• [4] Antonie, M.-L., Za¨ıane, O. R.: Mining Positive and Negative Association Rules: An Approach for Confined Rules, PKDD, 2004, 27-38.
• [5] Bastide, Y., Pasquier, N., Taouil, R., Stumme, G., Lakhal, L.: Mining Minimal Non-redundant Association Rules Using Frequent Closed Itemsets, Proceedings of Computational Logic, Springer-Verlag, London, UK, 2000, 972-986, ISBN 3-540-67797-6.
• [6] Boulicaut, J.-F., Bykowski, A., Jeudy, B.: Towards the Tractable Discovery of Association Rules with Negations, FQAS, 2000, 425-434.
• [7] Brin, S., Motwani, R., Silverstein, C.: Beyond market baskets: generalizing association rules to correlations, SIGMOD '97: Proceedings of the 1997 ACM SIGMOD international conference on Management of data, 26(2), ACM Press, New York, NY, USA, 1997, 265-276, ISBN 0-89791-911-4.
• [8] Diatta, J., Feno, D. R., Totohasina, D.: Galois Lattices and Bases for MGK-Valid Association Rules, CLA'2006: Proceedings of the 4th international conference on Concept Lattices and Their Applications, Springer, 2006, 186-197, ISBN978-3-540-78920-8.
• [9] János Demetrovics and Vu Duc Thi: Describing Candidate Keys by Hypergraphs, Computers and Artificial Intelligence, 18(3), 1999
• [10] Eiter, T., Gottlob, G., Makino, K.: New results on monotone dualization and generating hypergraph transversals, Proceedings of the thirty-fourth annual ACMsymposium on Theory of computing, STOC '02, ACM, New York, NY, USA, 2002, 14-22, ISBN 1-58113-495-9.
• [11] Eiter, T., Gottlob, G.: Hypergraph Transversal Computation and Related Problems in Logic and AI, JELIA, Cosenza, Italy, September 2002, 549-564, ISBN 3-540-44190-5.
• [12] Fredman, M. L., Khachiyan, L.: On the complexity of dualization of monotone disjunctive normal forms, J. Algorithms, 21(3), 1996, 618-628, ISSN 0196-6774.
• [13] Ganter, B., Wille, R.: Formal Concept Analysis: Mathematical Foundations, Springer-Verlag New York, Inc., 1999, Translator-C. Franzke.
• [14] Ganter, B.,Wille, R.: Contextual attribute logic . InWilliam M. Tepfenhart andWalling R. Cyre, editors, 7th International Conference on Conceptual Structures, ICCS '99, Blacksburg, Virginia, USA, July 12-15, 1999, Lecture Notes in Computer Science, Springer, 1999, 377-388, ISBN 3-540-66223-5.
• [15] Gasmi, G., Ben Yahia, S., Mephu Nguifo, E., Bouker, S.: Extraction of Association Rules Based on Literalsets, DaWaK'2007: Proceedings of the 9th International Conference on Data Warehousing and Knowledge Discovery, Springer-Verlag, Regensburg, Germany, 2007, 293-302, ISBN 978-3-540-74552-5.
• [16] Guigues, J.-L., Duquenne, V.: Familles minimales d'implications informatives résultant d'un tableau de données binaires, Mathématiques et Sciences Humaines, 95(1), 1986, 5-18.
• [17] Guillaume, S.: Traitement des données volumineuses. Mesures et algorithmes d'extraction des règles d'association et règles ordinales, Ph.D. Thesis, Université de Nantes, 2000.
• [18] Khachiyan, L., Boros, E., Elbassioni, K., Gurvich,V.: A global parallel algorithmfor the hypergraph transversal problem, Inf. Process. Lett., 101(4), 2007, 148-155, ISSN 0020-0190.
• [19] Kryszkiewicz,M.: Concise Representation of Association Rules, Proceedings of the ESF Exploratory Workshop on Pattern Detection and Discovery, Springer-Verlag, London, UK, 2002, 92-109, ISBN 3-540-44148-4.
• [20] Kryszkiewicz, M.: Generalized disjunction-free representation of frequent patterns with negation, J. Exp. Theor. Artif. Intell., 17(1-2), 2005, 63-82.
• [21] Kryszkiewicz,M.: Reasoning about Frequent Patterns with Negation, in: Encyclopedia of DataWarehousing and Mining (M. Kryszkiewicz, Ed.), Idea Group Reference, 2005, 941-946.
• [22] Kryszkiewicz, M.: Non-Derivable Item Set and Non-Derivable Literal Set Representations of Patterns Admitting Negation, DaWaK'2009: Proceedings of the 11th International Conference on Data Warehousing and Knowledge Discovery, Springer-Verlag, Linz, Austria, 2009, 138-150, ISBN 978-3-642-03729-0.
• [23] Luxenburger, M.: Implications partielles dans un contexte, Mathématiques, informatique et sciences humaines, 29(113), 1991, 35-55.
• [24] Maier, D.: The Theory of Relational Databases., Computer Science Press, 1983.
• [25] Mannila, H., Räihä, K-J.: Algorithms for Inferring Functional Dependencies from Relations, Data Knowl. Eng., 12(1), 1994, 83-99.
• [26] Mannila, H., Toivonen, H.: Multiple Uses of Frequent Sets and Condensed Representations (Extended Abstract), In Proc. KDD Int. Conf. Knowledge Discovery in Databases, 1996, 189-194.
• [27] Missaoui, R., Nourine, L., Renaud, Y.: Generating Positive and Negative Exact Rules using Formal Concept Analysis: Problems and Solutions, ICFCA, 2008, 169-181.
• [28] Missaoui, R., Nourine, L., Renaud, Y.: An Inference System for Exhaustive Generation of Mixed and Purely Negative Implications from Purely Positive Ones, Seventh International Conference on Concept Lattices and Applications (CLA'2010), 2010, 271-282.
• [29] Keisuke Murakami and Takeaki Uno: Efficient Algorithms for Dualizing Large-Scale Hypergraphs, CoRR, abs 1102.3813, 2011.
• [30] Nourine, L., Raynaud, O.: A fast incremental algorithm for building lattices, J. Exp. Theor. Artif. Intell., 14(2-3), 2002, 217-227.
• [31] Pasquier, N., Bastide, Y., Taouil, R., Lakhal, L.: Efficient Mining of Association Rules Using Closed Itemset Lattices, Information Systems, 24(1), 1999, 25-46.
• [32] Pfaltz, J., Taylor, C.: Scientific Discovery through Iterative Transformations of Concept Lattices, Proceedings of the 1st International Workshop on Discrete Mathematics and Data Mining, April 2002, 65-74.
• [33] Renaud, Y.: Quelques aspects algorithmiques sur les systèmes de fermeture, Ph.D. Thesis, Université Blaise Pascal, décembre 2008.
• [34] Francois Rioult, Bruno Zanuttini, and Bruno Crémilleux. Nonredundant generalized rules and their impact in classification. In Zbigniew W. Ras and Li-Shiang Tsay, editors, Advances in Intelligent Information Systems, volume 265, pages 3-25. Springer, 2010, ISBN 978-3-642-05182-1.
• [35] Savasere, A., Omiecinski, E., Navathe, S. B.: Mining for Strong Negative Associations in a Large Database of Customer Transactions, ICDE, 1998, 494-502.
• [36] Shock, R. C.: Computing the Minimum Cover of Functional Dependencies, Inf. Process. Lett., 22(3), 1986, 157-159.
• [37] Suzuki, E.: Data Mining Methods for Discovering Interesting Exceptions from an Unsupervised Table, J. UCS, 12(6), 2006, 627-653.
• [38] Szathmary, L., Valtchev, P., Napoli, A., Godin, R.: Constructing Iceberg Lattices from Frequent Closures Using Generators, DS'2007: Proceedings of the 11th international Conference on Discovery Science, Budapest, Hungary, October, 2008, Springer, ISBN 978-3-540-88410-1.
• [39] Teng, W.-G., Hsieh, M.-J., Chen, M.-S.: A statistical framework for mining substitution rules, Knowl. Inf. Syst., 7(2), 2005, 158-178.
• [40] Toivonen, H.: Discovery of frequent patterns in large data collections, Ph.D. Thesis, Report A-1996-5, University of Helsinki, 1996.
• [41] Valtchev, P., Missaoui, R., Godin, R.: Formal Concept Analysis for Knowledge Discovery and Data Mining: The New Challenges, ICFCA, 2004, 352-371.
• [42] Valtchev, P., Missaoui, R., Lebrun, P.: A partition-based approach towards constructing Galois (concept) lattices, Discrete Math., 256(3), 2002, 801-829, ISSN 0012-365X.
• [43] Wang, H., Zhang, X., Chen, G.: Mining a Complete Set of Both Positive and Negative Association Rules from Large Databases, PAKDD, 2008, 777-784.
• [44] Wu, X., Zhang, C., Zhang, S.: Efficient mining of both positive and negative association rules, ACM Trans. Inf. Syst., 22(3), 2004, 381-405, ISSN 1046-8188.
• [45] Yevtushenko, S. A.: System of data analysis "Concept Explorer", Proceedings of the 7th national conference on Artificial Intelligence KII 2000, 2000.
• [46] Zaki, M. J., Hsiao, C.-J.: Charm: An efficient algorithmfor closed itemset mining, Proceedings of the Second SIAM International Conference on Data Mining, Arlington, VA, USA, April 11-13, 2002.