Compact MILP Models and a Meta-heuristic Method for Pattern Generation in Logical Analysis of Data
- 주제(키워드) LAD , MILP , Pareto-optimal patterns , Tabu Search , Heuristic algorithm
- 발행기관 고려대학교 정보경영공학전문대학원
- 지도교수 류홍서
- 발행년도 2013
- 학위수여년월 2013. 8
- 학위구분 박사
- 학과 정보경영공학전문대학원 정보경영공학과
- 원문페이지 105 p
- 실제URI http://www.dcollection.net/handler/korea/000000046307
- 본문언어 영어
- 제출원본 000045764413
초록/요약
This dissertation develops MILP models for various optimal and Pareto-optimal patterns for LAD that involve at most 2n 0-1 decision variables, where n is the number of support features for the data under analysis which usually is small. In view that the previous MILP models are defined in 2n + m 0-1 variables, where m is the number of records in the dataset with m ≫ n in general, the new models are expected to generate useful LAD patterns more efficiently. By considering the relationship among those binary features generated from the same numerical attribute, we redefine the Hamming convex hull and the Perato-optimal patterns defined on it. We also revise the proposed MILP models according to these new definitions. To avoid the case that the power of patterns is predetermined by the quality of support features, we design an efficient algorithm based on Tabu-search for LAD pattern generation without feature selection procedure. With experiments on six well-studied machine learning datasets, we first demonstrate the efficiency of the new MILP models, next use them to show the different utilities of strong prime patterns and strong spanned patterns in enhancing the overall classification accuracy of a LAD decision theory, and finally demonstrate the more efficiency of the proposed heuristic algorithm.
more목차
List of Tables v
List of Figures vii
Abbreviations viii
Chapter
1. Introduction 1
1.1 Binarization 2
1.2 Feature Selection 3
1.3 Notation & Definitions 6
1.4 Overview 9
2. Compact MILP Models 14
2.1 Introduction & Motivation 14
2.2 Compact MILP Models for Strong Pattern 16
2.3 Models for Pareto-Optimal Patterns 23
2.4 Numerical Studies 27
2.4.1 Utility of Compact MILP Pattern Generation Models 27
2.4.2 Utility of Strong Prime Patterns & Strong Spanned Patterns 29
2.5 Concluding Remarks 37
3. New Definition and Classification of LAD Patterns 39
3.1 Introduction & Motivation 39
3.2 Revision of Constraints in Chapter 2 42
3.3 Generality Preference & Redefinition of Prime Patterns 43
3.4 Redefinition of Spanned Patterns 45
3.5 Corrections of Theorems, Lemmas and Proof 47
3.6 New Definition and Classification of LAD Patterns 52
3.7 Concise Strong Spanned Pattern 54
3.8 New Classification of LAD Patterns 56
3.9 Numerical Studies 57
3.9.1 Comparison of Strong Simple Patterns & Strong Prime Patterns 58
3.9.2 Comparison of Strong Spanned Patterns & Concise Strong Spanned Patterns 63
3.10 Concluding Remarks 63
4. Meta-heuristic Procedure for LAD Pattern Generation 67
4.1 Introduction 67
4.2 Tabu Search Algorithm 69
4.2.1 Scores for Tabu Moves on Binary Data Set 69
4.2.2 Scores for Tabu Moves on Numerical Data Set 75
4.2.3 Generating Patterns from a Term 78
4.2.4 Transfer a SPL Pattern to a Spanned Pattern 81
4.3 Results and Discussion 81
4.3.1 Utilities of tabuPattern Procedures 81
4.4 Concluding Remarks 85
5. Conclusion 89
Bibliography 91
