Anytime Discovery of a Diverse Set of Patterns with Monte Carlo Tree Search

Autor: Jean-François Boulicaut, Chedy Raïssi, Mehdi Kaytoue, Guillaume Bosc
Přispěvatelé: Data Mining and Machine Learning (DM2L), Laboratoire d'InfoRmatique en Image et Systèmes d'information (LIRIS), Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École Centrale de Lyon (ECL), Université de Lyon-Université Lumière - Lyon 2 (UL2)-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Université Lumière - Lyon 2 (UL2), Knowledge representation, reasonning (ORPAILLEUR), Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Department of Natural Language Processing & Knowledge Discovery (LORIA - NLPKD), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), European Project: 612334,EC:FP7:PEOPLE,FP7-PEOPLE-2013-IAPP,GRAISEARCH(2014), Université Lumière - Lyon 2 (UL2)-École Centrale de Lyon (ECL), Université de Lyon-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Lumière - Lyon 2 (UL2)-École Centrale de Lyon (ECL), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS), Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)
Jazyk: angličtina
Rok vydání: 2018
Předmět:
FOS: Computer and information sciences
Class (set theory)
Computer Networks and Communications
Computer science
Property (programming)
media_common.quotation_subject
Monte Carlo tree search
Brute-force search
02 engineering and technology
Machine learning
computer.software_genre
Pattern search
[INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI]
Set (abstract data type)
020204 information systems
Computer Science - Data Structures and Algorithms
0202 electrical engineering
electronic engineering
information engineering
Data Structures and Algorithms (cs.DS)
Quality (business)
[INFO]Computer Science [cs]
K-optimal pattern discovery
media_common
[INFO.INFO-DB]Computer Science [cs]/Databases [cs.DB]
business.industry
Computer Science Applications
020201 artificial intelligence & image processing
Artificial intelligence
Data mining
business
computer
Information Systems
Zdroj: Data Mining and Knowledge Discovery
Data Mining and Knowledge Discovery, Springer, 2018, 32 (3), pp.604-650. ⟨10.1007/s10618-017-0547-5⟩
Data Mining and Knowledge Discovery, 2018, 32 (3), pp.604-650. ⟨10.1007/s10618-017-0547-5⟩
ISSN: 1384-5810
1573-756X
DOI: 10.1007/s10618-017-0547-5⟩
Popis: The discovery of patterns that accurately discriminate one class label from another remains a challenging data mining task. Subgroup discovery (SD) is one of the frameworks that enables to elicit such interesting hypotheses from labeled data. A question remains fairly open: How to select an accurate heuristic search technique when exhaustive enumeration of the pattern space is infeasible? Existing approaches make use of beam-search, sampling and genetic algorithms for discovering a pattern set that is non-redundant and of high quality w.r.t. a pattern quality measure. We argue that such approaches produce pattern sets that lack of diversity: Only few patterns of high quality, and different enough, are discovered. Our main contribution is then to formally define pattern mining as a game and to solve it with Monte Carlo tree search (MCTS). It can be seen as an exhaustive search guided by random simulations which can be stopped early (limited budget) by virtue of its best-first search property. We show through a comprehensive set of experiments how MCTS enables the anytime discovery of a diverse pattern set of high quality. It outperforms other approaches when dealing with a large pattern search space and for different quality measures. Thanks to its genericity, our MCTS settings can be used for SD but also for many other pattern mining tasks.
This article has been accepted for publication in the journal \textit{Data Mining and Knowledge Discovery} (December 5th, 2017)
Databáze: OpenAIRE
Externí odkaz: