Research On Construction Of Piecewise Linear Classifiers In The Multiconlitron Framework

The design of piecewise linear classifiers is a fundamental problem in pattern recognition and machine learning, which has attracted a lot of attention but not been well solved yet. Recently, with the emergence of multiconlitron, the above-mentioned research has stepped into a new stage. Multiconlitron is a general theoretical framework for designing piecewise linear classifiers, defining the core concepts of convexly separable, commonly separable and conlitron. For any two-class commonly separable dataset(i.e., there are no common points between the two different classes), it can achieve an effective separation.The original construction method of multiconlitron is called support multiconlitron algorithm(SMA), which has generally exhibited good performance in the practical classification task. However, it still has two major drawbacks:(1) The classifier generated by the SMA contains a large number of linear functions, leading to the overly complex structure of classification model, so that its generalization ability needs to be improved.(2) The SMA requires the datasets must be commonly separable, thus influencing its usage environment and scope.In the framework of multiconlitron, this paper focuses on the construction problem of piecewise linear classifiers, with the aim of dealing with the shortcomings of the original construction method and finally improving classification performance and generalization ability. Driven by the goal, the research consists of four main aspects, namely, the improvement of classification accuracy, the simplification of classification model, the breakthrough of the restriction on common separability, and the development of new technologies. Accordingly, several new construction methods, including the growing, the maximal cutting, the soft margin, and the alternating, are respectively proposed to design more effective piecewise linear classifiers. Overall, the main contents and innovations of this research are as follows:1. Growing construction of multiconlitron for improving the classification accuracyThe method consists of two basic operations: SQUEEZE and INFLATE. In the convexly separable case, by using SQUEEZE the growing process moves the initial classification boundary closer to the interior convex region for fitting the data distribution better statistically. In the commonly separable case, by using INFLATE and SQUEEZE the growing process makes the initial classification boundary adjusted to a more reasonable position for enhancing the generalization ability. Experiments confirm that compared with the SMA, the growing construction method can obviously improve the classification accuracy, even up to around 10% on some datasets. Mean-while, the structure of classification model has been simplified to some extent.2. Maximal cutting construction of multiconlitron for simplifying the structure of classification modelThe method is composed of two training stages. In the first stage, the maximal cutting process is iteratively utilized to find a classification boundary so that it can cut off the maximum number of training samples. Thus, the process can reduce the number of linear functions to construct a minimal set of decision functions, and ultimately simplify the classification model. In order to further improve the generalization ability, in the second stage the boundary adjusting process is employed to retrain the classification boundaries and make them adjusted to the appropriate position. Compared with the SMA, the maximal cutting construction method can produce much simpler classification model in general. Experiments on benchmark datasets confirm that, under the premise of ensuring the testing accuracy, the number of linear functions has fallen by at least 50%, even more than 90% on some datasets.3. Soft margin construction of multiconlitron for overcoming the restriction on common separabilityThe method is proposed by adopting a property of second-order soft margin support vector machine. First of all, the training samples are mapped from input space to a high dimensional feature space, and then one class of them is clustered into some groups by K-means algorithm. Next, conlitrons are iteratively constructed between each group and the other class, and they eventually integrate a multiconlitron. The proposed method can improve the classification performance and further alleviate the overfitting effect. More importantly, it does solve the problem that the SMA cannot apply to commonly nonseparable dataset. Experimental evaluation confirms its effectiveness, and its competitiveness has also been showed when compared with some other piecewise linear classifiers.4. Construction of alternating multiconlitron as a novel general framework for piecewise linear classificationThe method first defines the concept of alternating multiconlitron on the basis of maximal convexly separable subset. Then, the existence and uniqueness of alternating multiconlitron are proved through several theorems. Different from multiconlitron, alternating multiconlitron generally has a nested structure of conlitrons, which provides a new general theoretical framework for designing piecewise linear classifiers. In the framework, the support alternating multiconlitron algorithm is employed to construct a series of conlitrons alternately from a subset of one class to the maximal convexly separable subset of the other class. These conlitrons eventually integrate an alternating multiconlitron in a specific order. Experimental results show that in practice an alternating multiconlitron generally has a much simpler structure than a corresponding multiconlitron, performing very fast in testing phase with similar or better accuracies.This research strives to promote the development and progress of multiconlitron framework, and in the framework continues to improve the classification performance of piecewise linear classifiers. These proposed methods can not only help us to understanding the nature of piecewise linear classifiers, but also should be regarded as an attractive advancement of piecewise linear learning.