Classification algorithms via integer optimization

Abstract

In this thesis, classification problems are considered. There are various classification algorithms, but they have some weak points in their modeling and it is generally accepted that no algorithm is superior to others on all data sets. Therefore, it is still worthwhile to develop new classification algorithms. Due to the heavy burden in computation of integer optimization, integer optimization-based classification methods had not been seriously investigated. However, since the late 2000s, novel classification approaches via integer optimization have been proposed with some ideas to overcome the computational issues. These new algorithms are different from the previous classification algorithms via integer optimization in two points. First, these new algorithms have excellent modeling power. Most previous approaches generate a single hyperplane to separate two classes and their application is limited to the cases of which two classes can be mostly separated by a single hyperplane. However, these new algorithms make groups of points of the same class and determine non-overlapping group regions and finally they predict class labels of unknown points based on the group regions. Therefore, they can construct non-linear decision boundaries between classes and can model various data distributions. Second, these new algorithms alleviate the computational burden of integer optimization with some ideas. Until now, two ideas are presented to reduce the computational load. One is to make clusters of points and assign clusters, not individual points, to groups. By doing this, the size of the integer optimization problem can be reduced and the computational load can be alleviated. The other one is to start with a simplified integer optimization problem and iteratively modify and solve it. By using this iterative solution approach, the structural issue which increases the computational burden can be avoided. In this study, we provide a unified view on the classification a...