Multi-pattern generation framework for logical analysis of data
详细信息 查看全文
- 作者：Chun-An Chou ; Tibérius O. Bonates ; Chungmok Lee…
- 关键词：Logical analysis of data ; Combinatorial optimization ; Column generation ; Pattern mining ; Classification
- 刊名：Annals of Operations Research
- 出版年：2017
- 出版时间：February 2017
- 年：2017
- 卷：249
- 期：1-2
- 页码：329-349
- 全文大小：
- 刊物类别：Business and Economics
- 刊物主题：Operation Research/Decision Theory; Combinatorics; Theory of Computation;
- 出版者：Springer US
- ISSN：1572-9338
- 卷排序：249
文摘
Logical analysis of data (LAD) is a rule-based data mining algorithm using combinatorial optimization and boolean logic for binary classification. The goal is to construct a classification model consisting of logical patterns (rules) that capture structured information from observations. Among the four steps of LAD framework (binarization, feature selection, pattern generation, and model construction), pattern generation has been considered the most important step. Combinatorial enumeration approaches to generate all possible patterns were mostly studied in the literature; however, those approaches suffered from the computational complexity of pattern generation that grows exponentially with data (feature) size. To overcome the problem, recent studies proposed column generation-based approaches to improve the efficacy of building a LAD model with a maximum-margin objective. There was still a difficulty in solving subproblems efficiently to generate patterns. In this study, a new column generation framework is proposed, in which a new mixed-integer linear programming approach is developed to generate multiple patterns having maximum coverage in subproblems at each iteration. In addition to the maximum-margin objective, we propose an alternative objective (minimum-pattern) to solve the LAD problem as a minimum set covering problem. The proposed approaches are evaluated on the datasets from the University of California Irvine Machine Learning Repository. The computational experiments provide comparable performances compared with previous LAD and other well-known classification algorithms.