Simulated annealing least squares twin support vector machine (SA-LSTSVM) for pattern classification

SVM is a maximum margin classifier which means that its goal is to minimize classification error and at the same time maximize the margin between two classes. For example, given a set of training points \((x_{i},y_{i})\), \(i=1,\ldots ,n\) each input training data \(x_{i} \in \mathbb {R}^{d}\) belongs to either of two classes with labels \(y_{i} \in {-1,+1}\). SVM seeks a hyperplane with equation \(w.x+b=0\) which can satisfy the following constraintswhere w is the weight vector and b is the bias term. Such a hyperplane could be obtained by solving Eq. 2:The geometric interpretation of this formulation is depicted in Fig. 1 for a toy example.

An important problem with SVM is its computational time. If “l” indicates the size of training data samples, then the computational complexity of SVM is of order \(O(l^{3})\), which is very expensive.

In SVM only one hyperplane performs the task of partitioning samples into two groups of positive and negative classes. In 2007, Khemchandani and Chandra (2007) proposed TSVM to use two hyperplanes in which samples are assigned to a class according to their distance from each hyperplane. The main equations of TSVM are:where \(w^{(i)}\) and \(b^{(i)}\) are weight vectors and bias terms of the ith hyperplane. In TSVM each hyperplane is a representative of the samples of its class. This concept is geometrically depicted in Fig. 2 for a toy example.

In TSVM, the two hyperplanes are non-parallel with each being closest to the samples of its own class and farthest from the samples of the opposite class (Ding et al. 2014; Shao et al. 2011). Assuming A and B indicate data points of class \(+1\) and class \(-1\), respectively, the two hyperplanes are obtained by solving (4) and (5). In these equations, q is a vector contains the slack variables, \(e_{i} \; (i \in \{1,2\})\) is a column vector of ones with arbitrary length, and \(c_{1}\) and \(c_{2}\) are penalty parameters. Once the hyperplanes are obtained, a new data point is assigned to class \(+1\) or class \(-1\) depending on to which hyperplane the point is closer in terms of perpendicular distance.

In TSVM, the number of constraints in the equation of each hyperplane is equal to the number of samples in the opposite class. Therefore, if there is an equal number of samples in the two classes, the number of constraints for each hyperplane in TSVM is equal to half the number of constraints in SVM. The computational complexity of TSVM is \(O((l/2)^{3})\) (Tomar and Agarwal 2014). It can be shown that the TSVM increases the speed of the algorithm by a factor of 4 compared to the traditional SVM, i.e. it is four times faster when compared to the SVM.

LSTSVM (Arun Kumar and Gopal 2009; Shao et al. 2012) is a binary classifier which combines the idea of LSSVM (Suykens and Vandewalle 1999; Mitra et al. 2007) and TSVM. LSTSVM employs “least squares of errors” to modify inequality constraints in TSVM to equality constraints by solving a set of linear equations rather than two quadratic programming problems (QPPs). Experiments have shown that LSTSVM can considerably reduce the training time, while still achieving competitive classification accuracy (Suykens and Vandewalle 1999; Gao et al. 2011). Because LSTSVM is a combination of TSVM and LSSVM, it dramatically reduces the time complexity of SVM. This is because LSTSVM solves equality constraints instead of inequality constraints as in LSSVM which makes the computational speed of the algorithm faster. The number of constraints in each hyperplane in LSTSVM is half of that in SVM which again results in very low computational complexity when compared to SVM. LSTSVM also has far better accuracy compared to SVM in most classification tasks.

LSTSVM finds its hyperplanes by minimizing Eqs. (6) and (7) which are linearly solvable. By solving (6) and (7), values of w and b for each hyperplane are obtained according to (8) and (9). where \(E=\begin{bmatrix} A&e \end{bmatrix}\) and \(F= \begin{bmatrix} B&e \end{bmatrix}\) whereas A, B, e and q are introduced in Sect. 2.2.

SA is a technique to find the best solution for an optimization problem by trying random variations of the current solution. It is a generalization of a Monte Carlo method for examining equations of state and frozen states of n-body systems. Figure 3 shows the pseudo code of the SA heuristic.

In each step, SA considers some neighboring state \(s_{i}\) of the current state \(s_{\mathrm{current}}\), and decides between moving to state \(s_{i}\) or staying in state \(s_{\mathrm{current}}\) with some probability. The new state (\(s_{i}\)) will be accepted if it has a better fitness compared to the current state (\(s_{\mathrm{current}}\)). If, however, the new state has lower fitness, it will be accepted with the probability showed in line 13 of the pseudo code. Note that the definition of “fitness” depends on the goal of the problem. These probabilistic movements ultimately lead the system to a state with almost optimum solution.

This section presents the proposed SA-LSTSVM algorithm in more detail. As already stated, LSTSVM has four parameters, two for each of the hyperplanes, which depend on nature of the problem. In SA a set of states is defined where each state has a set of parameters which include \(c_{1}\), \(c_{2}\), sigma\(_{1}\) and sigma\(_{2}\). The start state and its parameters are initiated by the user. For each state, SA defines a set of neighbors (which are also part of the state set). To find optimum values for LSTSVM parameters, the values of parameters for each particular state will initially differ from its neighbors. At first, there is a great difference between the parameter values of each two neighbor states, but the difference decreases as the algorithm iterates. In each iteration, a neighbor will be selected randomly. If the selected neighbor has higher accuracy than the current state, the selected neighbor will be taken and its parameters values (c and sigma) used as new parameter values. Figure 4 shows the pseudo code of the combined algorithm.

In this section, nine standard small data sets from the UCI repository (Bache and Lichman 2013) were evaluated. Table 1 shows some features of these data sets.

Table 2 presents the evaluation results of SA-LSTSVM and six other algorithms on these data sets. These algorithms are SVM, four different versions of SVM and a decision tree classification algorithm, C4.5 (Quinlan 1993), which has been selected because of its good performance in classification tasks. Bold text indicates best accuracies for each data set.

In this table the average accuracy of tenfold cross-validation together with the variance of the accuracies are shown as accuracy \(\pm \) variance. For SA-LSTSVM the best values of c and sigma are shown, too. Reported accuracies for TSVM, GEPSVM (Mangasarian and Wild 2006), and PSVM (Fung and Mangasarian 2001) are all extracted from Arun Kumar and Gopal (2009).

Figures 4, 5, 6, 7, 8, 9, 10, 11 and 12 show the accuracy of the SA-LSTSVM algorithm for each of the nine data sets for different values of c and sigma. In some figures, the relation between values of the parameters and the accuracy of SA-LSTSVM is obvious, e.g. Fig. 9, however, for some others, e.g. Fig. 7 there is not an obvious relationship between the accuracy of SA-LSTSVM and values of the parameters. As it is mentioned before the optimum values for parameters are problem dependent. The SA algorithm is used to find the highest accuracy among continuous values of c and sigma.

Figures 13, 14, 15, 16, 17, 18, 19, 20 and 21 show how the values of c and sigma changed during iterations of the SA algorithm for the nine data sets. In these figures, the blue shows the changes in the value of c and the red curve shows how sigma changes during the iterations. As it can be seen from the figures, the way the algorithm moves toward the optimum values for parameters depends on the data set.

Figures 22, 23, 24, 25, 26, 27, 28, 29, 30 and 31 show how the accuracy of the SA-LSTSVM algorithm changes during iterations of SA algorithm on the data sets. The figures show that as the algorithm iterates the average accuracy increases, but the accuracy variances decreased. The figures also show that using SA-LSTSVM it is possible to achieve the global best accuracy in a limited number of iterations (\(<\)60 iteration in most of the data sets).

To evaluate the performance of SA-LSTSVM on larger data sets, we used David Musicant’s NDC Data Generator (Musicant 1998) to generate data sets with 3000, 4000, 5000, 10,000, and 100,000 samples and 32 features. Results of running each algorithm are shown in Table 3. The best accuracy for each data set is shown in boldface. As it is shown in the table, again SA-LSTSVM has the highest accuracies among all versions of SVM for all data sets. However, only in NDC-100k data set, C4.5 obtains a better accuracy compared to SA-LSTSVM.

The above experiments showed that for all of the studied datasets, the accuracy of SA-LSTSVM is higher than other compared algorithms. However, there still a question remains which is “Are these differences statistically significant?”. In other words, it is important to show that these algorithms are statistically different. In Demšar (2006), Demsar introduced different ways of comparing algorithms over multiple data sets. Since we have seven algorithms for comparison, we choose to use Friedman test which is a non-parametric counterpart of ANOVA. Although there are some implementations of the Friedman test in some software tools like MATLAB and KEEL (Alcal-Fdez et al. 2009), we chose to implement the test by ourselves in MATLAB. The Friedman test ranks the algorithms for each dataset separately in the way that the best performing algorithm getting the rank 1, the second best ranked 2 and so on. In case of ties, e.g. in CMC, Hepatitis, Congressional Voting Records, and NDC-4k, the average ranks are assigned. Table 4 shows the ranks of the classifiers for different datasets used in this paper. Numbers inside the parenthesis are the ranks of classifiers for the corresponding dataset. The final row contains the average ranks of each classifier which is computed as \(R_{j} = \frac{1}{N}\sum _{i}r_{i}^{j}\), where \(r_{i}^{j}\) is the rank of the jth algorithm on the ith dataset. Note that since for NDC-100k two of the algorithms do not converged, we do not count this dataset in the evaluation.

The null-hypothesis is that all the algorithms are equivalent. Then the Friedman statistic is calculated and finally the critical value of the distribution of the Friedman statistic is compared with the statistic itself. The null-hypothesis will be rejected if the statistic is higher than the critical value.

The Friedman statistic is computed as follows:In this equation, k and N are the total number of classifiers and the total number of datasets, respectively. In our case \(k = 7\) and \(N = 13\). The statistic is distributed according to \(\chi _{\mathrm{F}}^{2}\) with \(k-1\) degrees of freedom, when N and k are big enough (as a rule of thumb, \(N>10\) and \(k>5\)) which is our case (Demšar 2006). Iman and Davenport (1980) showed that Friedman’s \(\chi _{\mathrm{F}}^{2}\) is undesirably conservative and they proposed a better statistic as bellow.which is distributed according to the F-distribution with \(k-1\) and \((k-1)(N-1)\) degrees of freedom.

The computed Friedman statistic and the corresponding \(F_{\mathrm{F}}\) statistic for our experiments are: With seven algorithms and 13 datasets, \(F_{\mathrm{F}}\) is distributed according to the F distribution with \(7-1=6\) and \((7-1)\times (13-1) = 72\) degrees of freedom. The critical value of F(6, 72) for \(\alpha = 0.05\) is 2.23, so we reject the null-hypothesis which means that the algorithms are statistically different.

By rejecting the null-hypothesis we can proceed with a post-hoc test. Since we want to compare all other classifiers with our proposed SA-LSTSVM, we will use the Bonferroni–Dunn test (Dunn 1961). In Demšar (2006) it is explained that based on Nemenyi test (Nemenyi 1963), the performance of two classifiers is significantly different if the corresponding average ranks differ by at least the critical differencewhere \(q_{\alpha }\) is the critical value.

The Bonferroni–Dunn test controls the family wise error rate by diving \(\alpha \) by the number of comparisons made which is \(k-1\) in this case. The alternative way to compute the same test as it is introduced in Demšar (2006) is to compute the critical difference, CD, using the same equation as the Nemenyi test, but using the critical values for \(\frac{\alpha }{(k-1)}\). The critical value \(q_{0.05}\) for seven classifiers is 2.638 and, therefore, we have CD \( = 2.638\sqrt{\frac{7*8}{6*13}}=2.235\). Using this critical difference, we can conclude that:

As stated in Sect. 2.3, LSTSVM is computationally faster than SVM with a computational time better than SVM by a factor of 4. SA is a probabilistic meta heuristic algorithm which takes random walks through the problem space. This may suggest that the SA-LSTSVM algorithm may be computationally very slow. However, our computational time analysis indicates otherwise.

Table 5 shows the computational times in second for the SA-LSTSVM, LSTSVM and SVM algorithm for all of the data sets. For the SA-LSTSVM algorithm the maximum number of iterations considered in the experiment was 25. This number was chosen because with this value for \(k_{\mathrm{max}}\), the algorithm achieves good accuracies for each of the different data sets. Although, we did not have any claim about the running time of the proposed SA-LSTSVM, Table 5 shows that the computational time of the SA-LSTSVM algorithm falls between the computational time of LSTSVM algorithm, which is the fastest version of SVM, and the standard SVM. In the table, the \(*\) sign shows that the computational time is extremely high and the algorithm does not converge to an acceptable accuracy in a reasonable time. Although, the obtained computational times for LSTSVM are better than SA-LSTSVM and SVM, the proposed SA-LSTSVM has higher accuracies when compared to both LSTSVM and SVM for all data sets.