Data Mining Using Grammar Based Genetic Programming and Applications

by Wong, Man Leung; Leung, Kwong-Sak

• ISBN13: 9780792377467
• ISBN10: 079237746X
• Format: Hardcover
• Copyright: 2000-01-01
• Publisher: Kluwer Academic Pub

Summary

Data mining involves the non-trivial extraction of implicit, previously unknown, and potentially useful information from databases. Genetic Programming (GP) and Inductive Logic Programming (ILP) are two of the approaches for data mining. This book first sets the necessary backgrounds for the reader, including an overview of data mining, evolutionary algorithms and inductive logic programming. It then describes a framework, called GGP (Generic Genetic Programming), that integrates GP and ILP based on a formalism of logic grammars. The formalism is powerful enough to represent context- sensitive information and domain-dependent knowledge. This knowledge can be used to accelerate the learning speed and/or improve the quality of the knowledge induced. A grammar-based genetic programming system called LOGENPRO (The LOGic grammar based GENetic PROgramming system) is detailed and tested on many problems in data mining. It is found that LOGENPRO outperforms some ILP systems. We have also illustrated how to apply LOGENPRO to emulate Automatically Defined Functions (ADFs) to discover problem representation primitives automatically. By employing various knowledge about the problem being solved, LOGENPRO can find a solution much faster than ADFs and the computation required by LOGENPRO is much smaller than that of ADFs. Moreover, LOGENPRO can emulate the effects of Strongly Type Genetic Programming and ADFs simultaneously and effortlessly. Data Mining Using Grammar Based Genetic Programming and Applications is appropriate for researchers, practitioners and clinicians interested in genetic programming, data mining, and the extraction of data from databases.

Table of Contents

List of Figures	ix
List of Tables	xi
Preface	xiii
Introduction	1	(1)
Data Mining	1	(8)
Motivation	3	(2)
Contributions of the Book	5	(2)
Outline of the Book	7	(2)
An Overview of Data Mining	9	(18)
Decision Tree Approach	9	(3)
ID3	10	(1)
C4.5	11	(1)
Classification Rule	12	(4)
AQ Algorithm	13	(1)
CN2	14	(1)
C4.5Rules	15	(1)
Association Rule Mining	16	(3)
Apriori	17	(1)
Quantitative Association Rule Mining	18	(1)
Statistical Approach	19	(3)
Bayesian Classifier	19	(1)
Forty-Niner	20	(1)
Explora	21	(1)
Bayesian Network Learning	22	(3)
Other Approaches	25	(2)
An Overview on Evolutionary Algorithms	27	(30)
Evolutionary Algorithms	27	(2)
Genetic Algorithms (GAs)	29	(12)
The Canonical Genetic Algorithm	30	(4)
Selection Methods	34	(2)
Recombination Methods	36	(3)
Inversion and Reordering	39	(1)
Steady State Genetic Algorithms	40	(1)
Hybrid Algorithms	41	(1)
Genetic Programming (GP)	41	(7)
Introduction to the Traditional GP	42	(5)
Strongly Typed Genetic Programming (STGP)	47	(1)
Evolution Strategies (ES)	48	(5)
Evolutionary Programming (EP)	53	(4)
Inductive Logic Programming	57	(44)
Inductive Concept Learning	57	(2)
Inductive Logic Programming (ILP)	59	(5)
Interactive ILP	61	(1)
Empirical ILP	62	(2)
Techniques and Methods of ILP	64	(7)
Bottom-up ILP Systems	64	(1)
Top-down ILP Systems	65	(1)
Foil	65	(3)
mFoil	68	(3)
The Logic Grammars Based Genetic Programming System (LOGENPRO)	71	(1)
Logic Grammars	72	(2)
Representations of Programs	74	(7)
Crossover of Programs	81	(13)
Mutation of Programs	94	(3)
The Evolution Process of LOGENPRO	97	(2)
Discussion	99	(2)
Data Mining Applications Using LOGENPRO	101	(36)
Learning Functional Programs	101	(14)
Learning S-expressions Using LOGENPRO	102	(2)
The Dot Product Problem	104	(6)
Learning Sub-functions Using Explicit Knowledge	110	(5)
Inducing Decision Trees Using LOGENPRO	115	(10)
Representing Decision Trees as S-expressions	115	(2)
The Credit Screening Problem	117	(2)
The Experiment	119	(6)
Learning Logic Program From Imperfect Data	125	(12)
The Chess Endgame Problem	127	(1)
The Setup of Experiments	128	(3)
Comparison of LOGENPRO With FOIL	131	(2)
Comparison of LOGENPRO With BEAM-FOIL	133	(1)
Comparison of LOGENPRO With mFOIL1	133	(1)
Comparison of LOGENPRO With mFOIL2	134	(1)
Comparison of LOGENPRO With mFOIL3	135	(1)
Comparison of LOGENPRO With mFOIL4	135	(1)
Discussion	136	(1)
Applying LOGENPRO for Rule Learning	137	(24)
Grammar	137	(4)
Genetic Operators	141	(2)
Evaluation of Rules	143	(2)
Learning Multiple Rules From Data	145	(16)
Previous Approaches	146	(1)
Pre-selection	146	(1)
Crowding	146	(1)
Deterministic Crowding	147	(1)
Fitness Sharing	147	(1)
Token Competition	148	(2)
The Complete Rule Learning Approach	150	(2)
Experiments With Machine Learning Databases	152	(1)
Experimental Results on the Iris Plant Database	153	(3)
Experimental Results on the Monk Database	156	(5)
Medical Data Mining	161	(8)
A Case Study on the Fracture Database	161	(3)
A Case Study on the Scoliosis Database	164	(5)
Rules for Scoliosis Classification	165	(1)
Rules About Treatment	166	(3)
Conclusion and Future Work	169	(8)
Conclusion	169	(3)
Future Work	172	(5)
APPENDIX A THE RULE SETS DISCOVERED	177	(20)
A.1. The Best Rule Set Learned from the Iris Database	177	(1)
A.2. The Best Rule Set Learned from the Monk Database	178	(5)
A.2.1. Monk1	178	(1)
A.2.2. Monk2	179	(3)
A.2.3. Monk3	182	(1)
A.3. The Best Rule Set Learned from the Fracture Database	183	(6)
A.3.1. Type I Rules: About Diagnosis	183	(1)
A.3.2. Type II Rules: About Operation/Surgeon	184	(2)
A.3.3. Type III Rules: About Stay	186	(3)
A.4. The Best Rule Set Learned from the Scoliosis Database	189	(8)
A.4.1. Rules for Classification	189	(1)
A.4.1.1. King-I	189	(1)
A.4.1.2. King-II	190	(1)
A.4.1.3. King-III	191	(1)
A.4.1.4. King-IV	191	(1)
A.4.1.5. King-V	192	(1)
A.4.1.6. TL	192	(1)
A.6.1.6. L	193	(1)
A.4.2. Rules for Treatment	194	(1)
A.4.2.1. Observation	194	(1)
A.4.2.2. Bracing	194	(3)
APPENDIX B THE GRAMMAR USED FOR THE FRACTURE AND SCOLIOSIS DATABASES	197	(2)
B.1. The Grammar for the Fracture Database	197	(1)
B.2. The Grammar for the Scoliosis Database	198	(1)
References	199	(12)
Index	211