Design and behavior study of a grammar-guided genetic programming algorithm for mining association rules

作     者：Luna, Jose M. Romero, Jose Raul Ventura, Sebastian 

作者机构：Univ Cordoba Dept Comp Sci & Numer Anal E-14071 Cordoba Spain 

出 版 物：《KNOWLEDGE AND INFORMATION SYSTEMS》 (知识和信息系统季刊)

年 卷 期：2012年第32卷第1期

页      面：53-76页

核心收录：

学科分类：0711[理学-系统科学] 07[理学] 08[工学] 070105[理学-运筹学与控制论] 081101[工学-控制理论与控制工程] 0701[理学-数学] 071101[理学-系统理论] 0811[工学-控制科学与工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：Regional Government of Andalusia [P08-TIC-3720] Ministry of Science and Technology [TIN2008-06681-C06-03] FEDER funds 

主　　题：Association rules Genetic programming Grammar-guided genetic programming Evolutionary algorithms 

摘      要：This paper presents a proposal for the extraction of association rules called G3PARM (Grammar-Guided Genetic Programming for Association Rule Mining) that makes the knowledge extracted more expressive and flexible. This algorithm allows a context-free grammar to be adapted and applied to each specific problem or domain and eliminates the problems raised by discretization. This proposal keeps the best individuals (those that exceed a certain threshold of support and confidence) obtained with the passing of generations in an auxiliary population of fixed size n. G3PARM obtains solutions within specified time limits and does not require the large amounts of memory that the exhaustive search algorithms in the field of association rules do. Our approach is compared to exhaustive search (Apriori and FP-Growth) and genetic (QuantMiner and ARMGA) algorithms for mining association rules and performs an analysis of the mined rules. Finally, a series of experiments serve to contrast the scalability of our algorithm. The proposal obtains a small set of rules with high support and confidence, over 90 and 99% respectively. Moreover, the resulting set of rules closely satisfies all the dataset instances. These results illustrate that our proposal is highly promising for the discovery of association rules in different types of datasets.