Movatterモバイル変換


[0]ホーム

URL:


Skip to main content

Advertisement

Springer Nature Link
Log in

Modeling Pattern Set Mining Using Boolean Circuits

  • Conference paper
  • First Online:

Abstract

Researchers in machine learning and data mining are increasingly getting used to modeling machine learning and data mining problems as parameter learning problems over network structures. However, this is not yet the case for several pattern set mining problems, such as concept learning, rule list learning, conceptual clustering, and Boolean matrix factorization. In this paper, we propose a new modeling language that allows modeling these problems. The key idea in this modeling language is that pattern set mining problems are modeled as discrete parameter learning problems overBoolean circuits. To solve the resulting optimisation problems, we show that standard optimization techniques from the constraint programming literature can be used, including mixed integer programming solvers and a local search algorithm. Our experiments on various standard machine learning datasets demonstrate that this approach, despite its genericity, permits learning high quality models.

The first author is supported by the FRIA-FNRS (Fonds pour la Formation à la Recherche dans l’Industrie et dans l’Agriculture, Belgium).

This is a preview of subscription content,log in via an institution to check access.

Access this chapter

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 5719
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 7149
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide -see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Similar content being viewed by others

References

  1. Angluin, D.: Queries and concept learning. Mach. Learn.2(4), 319–342 (1987)

    MathSciNet  Google Scholar 

  2. Aoga, J.O.R., Guns, T., Nijssen, S., Schaus, P.: Finding probabilistic rule lists using the minimum description length principle. In: Soldatova, L., Vanschoren, J., Papadopoulos, G., Ceci, M. (eds.) DS 2018. LNCS (LNAI), vol. 11198, pp. 66–82. Springer, Cham (2018).https://doi.org/10.1007/978-3-030-01771-2_5

    Chapter  Google Scholar 

  3. Aoga, J.O.R., Guns, T., Schaus, P.: Mining time-constrained sequential patterns with constraint programming. Constraints22(4), 548–570 (2017)

    Article MathSciNet  Google Scholar 

  4. Bertsimas, D., Dunn, J.: Optimal classification trees. Mach. Learn.106(7), 1039–1082 (2017)

    Article MathSciNet  Google Scholar 

  5. Clark, P., Niblett, T.: The CN2 induction algorithm. Mach. Learn.3, 261–283 (1989)

    Google Scholar 

  6. Coquery, E., Jabbour, S., Saïs, L., Salhi, Y.: A SAT-based approach for discovering frequent, closed and maximal patterns in a sequence. In: ECAI (2012)

    Google Scholar 

  7. Darwiche, A.: Compiling knowledge into decomposable negation normal form. In: Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, IJCAI 1999, pp. 284–289. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA (1999)

    Google Scholar 

  8. De Raedt, L., Zimmermann, A.: Constraint-based pattern set mining. In: Proceedings of the Seventh SIAM International Conference on Data Mining, Minneapolis, Minnesota, USA, 26–28 April 2007, pp. 237–248 (2007)

    Google Scholar 

  9. Fisher, D.H., Langley, P.: Approaches to conceptual clustering. In: Joshi, A.K. (ed.) Proceedings of the 9th International Joint Conference on Artificial Intelligence, Los Angeles, CA, USA, August 1985, pp. 691–697. Morgan Kaufmann (1985)

    Google Scholar 

  10. Gay, D., Selmaoui, N., Boulicaut, J.: Pattern-based decision tree construction. In: Second IEEE International Conference on Digital Information Management (ICDIM), Lyon, France, Proceedings, 11–13 December 2007, pp. 291–296. IEEE (2007)

    Google Scholar 

  11. Guns, T., Dries, A., Tack, G., Nijssen, S., De Raedt, L.: MiningZinc: a modeling language for constraint-based mining. In: Twenty-Third International Joint Conference on Artificial Intelligence (2013)

    Google Scholar 

  12. Guns, T., Nijssen, S., De Raedt, L.: Evaluating pattern set mining strategies in a constraint programming framework. In: Huang, J.Z., Cao, L., Srivastava, J. (eds.) PAKDD 2011. LNCS (LNAI), vol. 6635, pp. 382–394. Springer, Heidelberg (2011).https://doi.org/10.1007/978-3-642-20847-8_32

    Chapter MATH  Google Scholar 

  13. Guns, T., Nijssen, S., De Raedt, L.: Itemset mining: a constraint programming perspective. Artif. Intell.175(12–13), 1951–1983 (2011)

    Article MathSciNet  Google Scholar 

  14. Guns, T., Nijssen, S., De Raedt, L.: k-Pattern set mining under constraints. IEEE Trans. Knowl. Data Eng.25(2), 402–418 (2013)

    Article  Google Scholar 

  15. Hubara, I., Courbariaux, M., Soudry, D., El-Yaniv, R., Bengio, Y.: Binarized neural networks. In: Lee, D.D., Sugiyama, M., Luxburg, U.V., Guyon, I., Garnett, R. (eds.) Advances in Neural Information Processing Systems 29, pp. 4107–4115. Curran Associates Inc., New York (2016).http://papers.nips.cc/paper/6573-binarized-neural-networks.pdf

    Google Scholar 

  16. Kemmar, A., Lebbah, Y., Loudni, S., Boizumault, P., Charnois, T.: Prefix-projection global constraint and top-k approach for sequential pattern mining. Constraints22(2), 265–306 (2017)

    Article MathSciNet  Google Scholar 

  17. Lam, H.T., Pei, W., Prado, A., Jeudy, B., Fromont, É.: Mining top-k largest tiles in a data stream. In: Calders, T., Esposito, F., Hüllermeier, E., Meo, R. (eds.) ECML PKDD 2014. LNCS (LNAI), vol. 8725, pp. 82–97. Springer, Heidelberg (2014).https://doi.org/10.1007/978-3-662-44851-9_6

    Chapter  Google Scholar 

  18. Lazaar, N., et al.: A global constraint for closed frequent pattern mining. In: Rueher, M. (ed.) CP 2016. LNCS, vol. 9892, pp. 333–349. Springer, Cham (2016).https://doi.org/10.1007/978-3-319-44953-1_22

    Chapter  Google Scholar 

  19. Meo, R., Psaila, G., Ceri, S.: A new SQL-like operator for mining association rules. In: Vijayaraman, T.M., Buchmann, A.P., Mohan, C., Sarda, N.L. (eds.) VLDB 1996, Proceedings of 22th International Conference on Very Large Data Bases, Mumbai (Bombay), India, 3–6 September 1996, pp. 122–133. Morgan Kaufmann (1996)

    Google Scholar 

  20. Michalski, R.S.: On the quasi-minimal solution of the general covering problem (1969)

    Google Scholar 

  21. Negrevergne, B., Guns, T.: Constraint-based sequence mining using constraint programming. In: Michel, L. (ed.) CPAIOR 2015. LNCS, vol. 9075, pp. 288–305. Springer, Cham (2015).https://doi.org/10.1007/978-3-319-18008-3_20

    Chapter MATH  Google Scholar 

  22. Ouali, A., Loudni, S., Lebbah, Y., Boizumault, P., Zimmermann, A., Loukil, L.: Efficiently finding conceptual clustering models with integer linear programming. In: Kambhampati, S. (ed.) Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI 2016, New York, NY, USA, 9–15 July 2016, pp. 647–654. IJCAI/AAAI Press (2016)

    Google Scholar 

  23. Ouali, A., et al.: Integer linear programming for pattern set mining; with an application to tiling. In: Kim, J., Shim, K., Cao, L., Lee, J.-G., Lin, X., Moon, Y.-S. (eds.) PAKDD 2017. LNCS (LNAI), vol. 10235, pp. 286–299. Springer, Cham (2017).https://doi.org/10.1007/978-3-319-57529-2_23

    Chapter  Google Scholar 

  24. Rudin, C., Ertekin, Ş.: Learning customized and optimized lists of rules with mathematical programming. Math. Program. Comput.10(4), 659–702 (2018)

    Article MathSciNet  Google Scholar 

  25. Schaus, P., Aoga, J.O.R., Guns, T.: CoverSize: a global constraint for frequency-based itemset mining. In: Beck, J.C. (ed.) CP 2017. LNCS, vol. 10416, pp. 529–546. Springer, Cham (2017).https://doi.org/10.1007/978-3-319-66158-2_34

    Chapter MATH  Google Scholar 

  26. Sejnowski, T.J.: The Deep Learning Revolution. MIT Press, Cambridge (2018)

    Book  Google Scholar 

  27. Verwer, S., Zhang, Y.: Learning optimal classification trees using a binary linear program formulation. In: 33rd AAAI Conference on Artificial Intelligence (2019)

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. ICTEAM/INGI, UCLouvain, Ottignies-Louvain-la-Neuve, Belgium

    John O. R. Aoga, Siegfried Nijssen & Pierre Schaus

Authors
  1. John O. R. Aoga

    You can also search for this author inPubMed Google Scholar

  2. Siegfried Nijssen

    You can also search for this author inPubMed Google Scholar

  3. Pierre Schaus

    You can also search for this author inPubMed Google Scholar

Corresponding author

Correspondence toJohn O. R. Aoga.

Editor information

Editors and Affiliations

  1. INRA, Castanet Tolosan, France

    Thomas Schiex

  2. INRA, Castanet Tolosan, France

    Simon de Givry

Rights and permissions

Copyright information

© 2019 Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Aoga, J.O.R., Nijssen, S., Schaus, P. (2019). Modeling Pattern Set Mining Using Boolean Circuits. In: Schiex, T., de Givry, S. (eds) Principles and Practice of Constraint Programming. CP 2019. Lecture Notes in Computer Science(), vol 11802. Springer, Cham. https://doi.org/10.1007/978-3-030-30048-7_36

Download citation

Publish with us

Access this chapter

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 5719
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 7149
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide -see info

Tax calculation will be finalised at checkout

Purchases are for personal use only


[8]ページ先頭

©2009-2025 Movatter.jp