Optimization Based Data Mining: Theory and Applications (Advanced Information and Knowledge Processing)

Optimization techniques have been widely adopted to implement various data mining algorithms. In addition to well-known Support Vector Machines (SVMs) (which are based on quadratic programming), different versions of Multiple Criteria Programming (MCP) have been extensively used in data separations. Since optimization based data mining methods differ from statistics, decision tree induction, and neural networks, their theoretical inspiration has attracted many researchers who are interested in algorithm development of data mining. __Optimization based Data Mining: Theory and Applications__, mainly focuses on MCP and SVM especially their recent theoretical progress and real-life applications in various fields. These include finance, web services, bio-informatics and petroleum engineering, which has triggered the interest of practitioners who look for new methods to improve the results of data mining for knowledge discovery. Most of the material in this book is directly from the research and application activities that the authors’ research group has conducted over the last ten years. Aimed at practitioners and graduates who have a fundamental knowledge in data mining, it demonstrates the basic concepts and foundations on how to use optimization techniques to deal with data mining problems. Optimization Based Data Mining: Theory and Applications 3 Preface 6 Contents 9 Part I: Support Vector Machines: Theory and Algorithms 14 Chapter 1: Support Vector Machines for Classification Problems 15 1.1 Method of Maximum Margin 15 1.2 Dual Problem 17 1.3 Soft Margin 18 1.4 C-Support Vector Classification 20 1.5 C-Support Vector Classification with Nominal Attributes 22 1.5.1 From Fixed Points to Flexible Points 22 1.5.2 C-SVC with Nominal Attributes 23 1.5.3 Numerical Experiments 24 Chapter 2: LOO Bounds for Support Vector Machines 26 2.1 Introduction 26 2.2 LOO Bounds for epsilon-Support Vector Regression 27 2.2.1 Standard epsilon-Support Vector Regression 27 2.2.2 The First LOO Bound 28 2.2.3 A Variation of epsilon-Support Vector Regression 37 2.2.4 The Second LOO Bound 38 2.2.5 Numerical Experiments 41 2.3 LOO Bounds for Support Vector Ordinal Regression Machine 43 2.3.1 Support Vector Ordinal Regression Machine 44 2.3.2 The First LOO Bound 49 Definition and Existence of Span 49 The Bound 51 2.3.3 The Second LOO Bound 53 2.3.4 Numerical Experiments 55 Chapter 3: Support Vector Machines for Multi-class Classification Problems 58 3.1 K-Class Linear Programming Support Vector Classification Regression Machine (K-LPSVCR) 58 3.1.1 K-LPSVCR 60 3.1.2 Numerical Experiments 61 Experiments on Artificial Data Sets 62 Experiments on Benchmark Data Sets 63 3.1.3 nu-K-LPSVCR 63 3.2 Support Vector Ordinal Regression Machine for Multi-class Problems 65 3.2.1 Kernel Ordinal Regression for 3-Class Problems 65 3.2.2 Multi-class Classification Algorithm 67 3.2.3 Numerical Experiments 68 Example in the Plane 69 Experiments on Benchmark Data Sets 70 Chapter 4: Unsupervised and Semi-supervised Support Vector Machines 72 4.1 Unsupervised and Semi-supervised nu-Support Vector Machine 73 4.1.1 Bounded nu-Support Vector Machine 73 4.1.2 nu-SDP for Unsupervised Classification Problems 74 4.1.3 nu-SDP for Semi-supervised Classification Problems 76 4.2 Numerical Experiments 77 4.2.1 Numerical Experiments of Algorithm 4.2 77 4.2.2 Numerical Experiments of Algorithm 4.3 78 4.3 Unsupervised and Semi-supervised Lagrange Support Vector Machine 80 4.4 Unconstrained Transductive Support Vector Machine 83 4.4.1 Transductive Support Vector Machine 84 4.4.2 Unconstrained Transductive Support Vector Machine 85 Unconstrained Optimization Problem 85 Smooth Unconstrained Optimization Problem 87 4.4.3 Unconstrained Transductive Support Vector Machine with Kernels 88 Chapter 5: Robust Support Vector Machines 91 5.1 Robust Support Vector Ordinal Regression Machine 91 5.2 Robust Multi-class Algorithm 103 5.3 Numerical Experiments 104 5.3.1 Numerical Experiments of Algorithm 5.6 104 5.3.2 Numerical Experiments of Algorithm 5.7 105 5.4 Robust Unsupervised and Semi-supervised Bounded C-Support Vector Machine 106 5.4.1 Robust Linear Optimization 107 5.4.2 Robust Algorithms with Polyhedron 107 5.4.3 Robust Algorithm with Ellipsoid 111 5.4.4 Numerical Results 113 Chapter 6: Feature Selection via lp-Norm Support Vector Machines 116 6.1 lp-Norm Support Vector Classification 116 6.1.1 lp-SVC 117 6.1.2 Lower Bound for Nonzero Entries in Solutions of lp-SVC 118 6.1.3 Iteratively Reweighted lq-SVC for lp-SVC 120 6.2 lp-Norm Proximal Support Vector Machine 120 6.2.1 Lower Bounds for Nonzero Entries in Solutions of lp-PSVM 122 6.2.2 Smoothing lp-PSVM Problem 122 6.2.3 Numerical Experiments 123 Comparison with l1-PSVM 125 Part II: Multiple Criteria Programming: Theory and Algorithms 126 Chapter 7: Multiple Criteria Linear Programming 127 7.1 Comparison of Support Vector Machine and Multiple Criteria Programming 127 7.2 Multiple Criteria Linear Programming 128 7.3 Multiple Criteria Linear Programming for Multiple Classes 131 7.4 Penalized Multiple Criteria Linear Programming 137 7.5 Regularized Multiple Criteria Linear Programs for Classification 137 Chapter 8: MCLP Extensions 141 8.1 Fuzzy MCLP 141 8.2 FMCLP with Soft Constraints 144 8.3 FMCLP by Tolerances 148 8.4 Kernel-Based MCLP 149 8.5 Knowledge-Based MCLP 151 8.5.1 Linear Knowledge-Based MCLP 151 8.5.2 Nonlinear Knowledge and Kernel-Based MCLP 155 8.6 Rough Set-Based MCLP 158 8.6.1 Rough Set-Based Feature Selection Method 158 8.6.2 A Rough Set-Based MCLP Approach for Classification 160 8.7 Regression by MCLP 163 Chapter 9: Multiple Criteria Quadratic Programming 165 9.1 A General Multiple Mathematical Programming 165 9.2 Multi-criteria Convex Quadratic Programming Model 169 9.3 Kernel Based MCQP 175 Chapter 10: Non-additive MCLP 179 10.1 Non-additive Measures and Integrals 179 10.2 Non-additive Classification Models 180 10.3 Non-additive MCP 186 10.4 Reducing the Time Complexity 187 10.4.1 Hierarchical Choquet Integral 187 10.4.2 Choquet Integral with Respect to k-Additive Measure 188 Chapter 11: MC2LP 190 11.1 MC2LP Classification 190 11.1.1 Multiple Criteria Linear Programming 190 11.1.2 Different Versions of MC2 193 11.1.3 Heuristic Classification Algorithm 196 11.2 Minimal Error and Maximal Between-Class Variance Model 198 Part III: Applications in Various Fields 200 Chapter 12: Firm Financial Analysis 201 12.1 Finance and Banking 201 12.2 General Classification Process 202 12.3 Firm Bankruptcy Prediction 205 Chapter 13: Personal Credit Management 208 13.1 Credit Card Accounts Classification 208 13.2 Two-Class Analysis 212 13.2.1 Six Different Methods 212 13.2.2 Implication of Business Intelligence and Decision Making 216 13.2.3 FMCLP Analysis 218 13.3 Three-Class Analysis 224 13.3.1 Three-Class Formulation 224 13.3.2 Small Sample Testing 227 13.3.3 Real-Life Data Analysis 232 13.4 Four-Class Analysis 233 13.4.1 Four-Class Formulation 233 13.4.2 Empirical Study and Managerial Significance of Four-Class Models 235 Chapter 14: Health Insurance Fraud Detection 237 14.1 Problem Identification 237 14.2 A Real-Life Data Mining Study 237 Chapter 15: Network Intrusion Detection 240 15.1 Problem and Two Datasets 240 15.2 Classification of NeWT Lab Data by MCMP, MCMP with Kernel and See5 242 15.3 Classification of KDDCUP-99 Data by Nine Different Methods 243 Chapter 16: Internet Service Analysis 245 16.1 VIP Mail Dataset 245 16.2 Empirical Study of Cross-Validation 246 16.3 Comparison of Multiple-Criteria Programming Models and SVM 249 Chapter 17: HIV-1 Informatics 251 17.1 HIV-1 Mediated Neuronal Dendritic and Synaptic Damage 251 17.2 Materials and Methods 253 17.2.1 Neuronal Culture and Treatments 253 17.2.2 Image Analysis 254 17.2.3 Preliminary Analysis of Neuronal Damage Induced by HIV MCM Treated Neurons 254 17.2.4 Database 255 17.3 Designs of Classifications 256 17.4 Analytic Results 258 17.4.1 Empirical Classification 258 Chapter 18: Anti-gen and Anti-body Informatics 261 18.1 Problem Background 261 18.2 MCQP, LDA and DT Analyses 262 18.3 Kernel-Based MCQP and SVM Analyses 268 Chapter 19: Geochemical Analyses 270 19.1 Problem Description 270 19.2 Multiple-Class Analyses 271 19.2.1 Two-Class Classification 271 19.2.2 Three-Class Classification 272 19.2.3 Four-Class Classification 272 19.3 More Advanced Analyses 273 Chapter 20: Intelligent Knowledge Management 277 20.1 Purposes of the Study 277 20.2 Definitions and Theoretical Framework of Intelligent Knowledge 280 20.2.1 Key Concepts and Definitions 280 20.2.2 4T Process and Major Steps of Intelligent Knowledge Management 288 20.3 Some Research Directions 290 20.3.1 The Systematic Theoretical Framework of Data Technology and Intelligent Knowledge Management 291 20.3.2 Measurements of Intelligent Knowledge 292 20.3.3 Intelligent Knowledge Management System Research 293 References 294 Subject Index 305 Author Index 309 Front Matter....Pages I-XV Front Matter....Pages 1-1 Support Vector Machines for Classification Problems....Pages 3-13 LOO Bounds for Support Vector Machines....Pages 15-46 Support Vector Machines for Multi-class Classification Problems....Pages 47-60 Unsupervised and Semi-supervised Support Vector Machines....Pages 61-79 Robust Support Vector Machines....Pages 81-105 Feature Selection via l p -Norm Support Vector Machines....Pages 107-116 Front Matter....Pages 117-117 Multiple Criteria Linear Programming....Pages 119-132 MCLP Extensions....Pages 133-156 Multiple Criteria Quadratic Programming....Pages 157-170 Non-additive MCLP....Pages 171-181 MC2LP....Pages 183-192 Front Matter....Pages 193-193 Firm Financial Analysis....Pages 195-201 Personal Credit Management....Pages 203-231 Health Insurance Fraud Detection....Pages 233-235 Network Intrusion Detection....Pages 237-241 Internet Service Analysis....Pages 243-248 HIV-1 Informatics....Pages 249-258 Anti-gen and Anti-body Informatics....Pages 259-267 Geochemical Analyses....Pages 269-275 Intelligent Knowledge Management....Pages 277-293 Back Matter....Pages 295-316 Optimization techniques have been widely adopted to implement various data mining algorithms. This book focuses on cutting-edge theoretical developments and real-life applications in optimization, covering a range of fields from finance to bioinformatics. By Yong Shi, Yingjie Tian, Gang Kou, Yi Peng, Jianping Li.