An efficient algorithm for the incremental construction of a piecewise linear classifier

In this paper the problem of finding piecewise linear boundaries between sets is considered and is applied for solving supervised data classification problems. An algorithm for the computation of piecewise linear boundaries, consisting of two main steps, is proposed. In the first step sets are approximated by hyperboxes to find so-called “indeterminate” regions between sets. In the second step sets are separated inside these “indeterminate” regions by piecewise linear functions. These functions are computed incrementally starting with a linear function. Results of numerical experiments are reported. These results demonstrate that the new algorithm requires a reasonable training time and it produces consistently good test set accuracy on most data sets comparing with mainstream classifiers.

Research highlights
► We propose an algorithm for constructing a classifier based on piecewise linear boundaries between classes.
► In the first step of this algorithm we approximate each class using a single hyperbox, then only keep points lying in the intersection of two or more hyperboxes.
► The second step of the algorithm is based on constructing the piecewise linear boundaries incrementally, solving a nonsmooth nonconvex optimization problem at each iteration.