Document Open Access Logo

Qualitative Reasoning and Data Mining

Author Yakoub Salhi

PDF
Thumbnail PDF

File

LIPIcs.TIME.2019.9.pdf
  • Filesize: 0.5 MB
  • 15 pages

Document Identifiers

Author Details

Yakoub Salhi
  • CRIL - CNRS & Université d'Artois, Lens, France

Cite As Get BibTex

Yakoub Salhi. Qualitative Reasoning and Data Mining. In 26th International Symposium on Temporal Representation and Reasoning (TIME 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 147, pp. 9:1-9:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.TIME.2019.9

Abstract

In this paper, we introduce a new data mining framework that is based on qualitative reasoning. We consider databases where the item domains are of different types, such as numerical values, time intervals and spatial regions. Then, for the considered tasks, we associate to each item a constraint network in a qualitative formalism representing the relations between all the pairs of objects of the database w.r.t. this item. In this context, the introduced data mining problems consist in discovering qualitative covariations between items. In a sense, our framework can be seen as a generalization of gradual itemset mining. In order to solve the introduced problem, we use a declarative approach based on the satisfiability problem in classical propositional logic (SAT). Indeed, we define SAT encodings where the models represent the desired patterns.

Subject Classification

ACM Subject Classification
  • Information systems → Data mining
  • Information systems → Association rules
  • Theory of computation → Constraint and logic programming
  • Computing methodologies → Knowledge representation and reasoning
Keywords
  • Qualitative Database
  • Qualitative Pattern Mining
  • Declarative Approach
  • SAT Modeling

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Rakesh Agrawal, Tomasz Imielinski, and Arun N. Swami. Mining Association Rules between Sets of Items in Large Databases. In Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data, Washington, DC, USA, pages 207-216. ACM Press, 1993. Google Scholar
  2. James F. Allen. An Interval-Based Representation of Temporal Knowledge. In Proceedings of the 7th International Joint Conference on Artificial Intelligence, IJCAI '81, Vancouver, BC, Canada, pages 221-226. William Kaufmann, 1981. Google Scholar
  3. James F. Allen. Maintaining Knowledge about Temporal Intervals. Communications of the ACM, 26(11):832-843, 1983. Google Scholar
  4. Olivier Bailleux and Yacine Boufkhad. Efficient CNF Encoding of Boolean Cardinality Constraints. In Principles and Practice of Constraint Programming - CP 2003, 9th International Conference, CP 2003, Kinsale, Ireland, pages 108-122, 2003. Google Scholar
  5. Olivier Bailleux, Yacine Boufkhad, and Olivier Roussel. A Translation of Pseudo Boolean Constraints to SAT. JSAT, 2(1-4):191-200, 2006. Google Scholar
  6. Philippe Balbiani, Jean-François Condotta, and Gérard Ligozat. Reasoning about Cyclic Space: Axiomatic and Computational Aspects. In Spatial Cognition III, Routes and Navigation, Human Memory and Learning, Spatial Representation and Spatial Learning, pages 348-371. Springer, 2003. Google Scholar
  7. Fernando Berzal, Juan C. Cubero, Daniel Sánchez, María Amparo Vila Miranda, and José-María Serrano. An Alternative Approach to Discover Gradual Dependencies. International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, 15(5):559-570, 2007. Google Scholar
  8. Abdelhamid Boudane, Saïd Jabbour, Lakhdar Sais, and Yakoub Salhi. A SAT-Based Approach for Mining Association Rules. In Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI 2016, New York, NY, USA, pages 2472-2478. IJCAI/AAAI Press, 2016. Google Scholar
  9. Abdelhamid Boudane, Saïd Jabbour, Lakhdar Sais, and Yakoub Salhi. SAT-Based Data Mining. International Journal on Artificial Intelligence Tools, 27(1):1-24, 2018. Google Scholar
  10. Lisa Di-Jorio, Anne Laurent, and Maguelonne Teisseire. Fast extraction of gradual association rules: a heuristic based method. In CSTST 2008: Proceedings of the 5th International Conference on Soft Computing as Transdisciplinary Science and Technology, Cergy-Pontoise, France, pages 205-210. ACM, 2008. Google Scholar
  11. Lisa Di-Jorio, Anne Laurent, and Maguelonne Teisseire. Mining Frequent Gradual Itemsets from Large Databases. In Advances in Intelligent Data Analysis VIII, 8th International Symposium on Intelligent Data Analysis, IDA 2009, Lyon, France, pages 297-308. Springer, 2009. Google Scholar
  12. Tias Guns, Anton Dries, Siegfried Nijssen, Guido Tack, and Luc De Raedt. MiningZinc: A declarative framework for constraint-based mining. Artificial Intelligence, 244:6-29, 2017. Google Scholar
  13. Tias Guns, Siegfried Nijssen, and Luc De Raedt. Itemset mining: A constraint programming perspective. Artificial Intelligence, 175(12-13):1951-1983, 2011. Google Scholar
  14. Amar Isli and Anthony G. Cohn. A new approach to cyclic ordering of 2D orientations using ternary relation algebras. Artificial Intelligence, 122(1-2):137-187, 2000. Google Scholar
  15. Saïd Jabbour, Jerry Lonlac, Lakhdar Sais, and Yakoub Salhi. Extending modern SAT solvers for models enumeration. In Proceedings of the 15th IEEE International Conference on Information Reuse and Integration, IRI 2014, Redwood City, CA, USA, pages 803-810. IEEE Computer Society, 2014. Google Scholar
  16. Saïd Jabbour, Lakhdar Sais, and Yakoub Salhi. Boolean satisfiability for sequence mining. In 22nd ACM International Conference on Information and Knowledge Management, CIKM'13, San Francisco, CA, USA, pages 649-658. ACM, 2013. Google Scholar
  17. Saïd Jabbour, Lakhdar Sais, and Yakoub Salhi. Decomposition Based SAT Encodings for Itemset Mining Problems. In Advances in Knowledge Discovery and Data Mining - 19th Pacific-Asia Conference, PAKDD 2015, Ho Chi Minh City, Vietnam, pages 662-674. Springer, 2015. Google Scholar
  18. Saïd Jabbour, Lakhdar Sais, and Yakoub Salhi. On SAT Models Enumeration in Itemset Mining. CoRR, abs/1506.02561, 2015. URL: http://arxiv.org/abs/1506.02561.
  19. Saïd Jabbour, Lakhdar Sais, and Yakoub Salhi. Mining Top-k motifs with a SAT-based framework. Artificial Intelligence, 244:30-47, 2017. Google Scholar
  20. Anne Laurent, Marie-Jeanne Lesot, and Maria Rifqi. GRAANK: Exploiting Rank Correlations for Extracting Gradual Itemsets. In Flexible Query Answering Systems, 8th International Conference, FQAS 2009, Roskilde, Denmark, pages 382-393. Springer, 2009. Google Scholar
  21. Gérard Ligozat. Qualitative Spatial and Temporal Reasoning. ISTE. Wiley, 2013. Google Scholar
  22. Jerry Lonlac, Saïd Jabbour, Engelbert Mephu Nguifo, Lakhdar Saïs, and Badran Raddaoui. Extracting Frequent Gradual Patterns Using Constraints Modeling. CoRR, abs/1903.08452, 2019. URL: http://arxiv.org/abs/1903.08452.
  23. João P. Marques-Silva and Inês Lynce. Towards Robust CNF Encodings of Cardinality Constraints. In Principles and Practice of Constraint Programming - CP 2007, 13th International Conference, CP 2007, Providence, RI, USA, pages 483-497, 2007. Google Scholar
  24. Luc De Raedt, Tias Guns, and Siegfried Nijssen. Constraint Programming for Itemset Mining. In Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Las Vegas, Nevada, USA, pages 204-212, 2008. Google Scholar
  25. David A. Randell, Zhan Cui, and Anthony Cohn. A Spatial Logic Based on Regions and Connection. In Proceedings of the 3rd International Conference on Principles of Knowledge Representation and Reasoning (KR'92). Cambridge, MA, USA, 1992. Google Scholar
  26. Carsten Sinz. Towards an Optimal CNF Encoding of Boolean Cardinality Constraints. In Principles and Practice of Constraint Programming - CP 2005, 11th International Conference, CP 2005, Sitges, Spain, pages 827-831, 2005. Google Scholar
  27. Spiros Skiadopoulos and Manolis Koubarakis. Composing cardinal direction relations. Artificial Intelligence, 152(2):143-171, 2004. Google Scholar
  28. Spiros Skiadopoulos and Manolis Koubarakis. On the consistency of cardinal direction constraints. Artificial Intelligence, 163(1):91-135, 2005. Google Scholar
  29. Gregory S. Tseitin. On the complexity of derivations in the propositional calculus. In Structures in Constructives Mathematics and Mathematical Logic, Part II, pages 115-125, 1968. Google Scholar
  30. Willy Ugarte, Patrice Boizumault, Bruno Crémilleux, Alban Lepailleur, Samir Loudni, Marc Plantevit, Chedy Raïssi, and Arnaud Soulet. Skypattern mining: From pattern condensed representations to dynamic constraint satisfaction problems. Artificial Intelligence, 244:48-69, 2017. Google Scholar
  31. Marc B. Vilain and Henry A. Kautz. Constraint Propagation Algorithms for Temporal Reasoning. In Proceedings of the 5th National Conference on Artificial Intelligence. Philadelphia, PA, USA. Volume 1: Science, pages 377-382. Morgan Kaufmann, 1986. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact