Directed acyclic graph fuzzy nonparallel support vector machine

Abstract

Classification problem is an important research direction in machine learning. Nonparallel support vector machine (NPSVM) is an important classifier used to solve classification problems. It is widely used because of its structural risk minimization principle, kernel trick, and sparsity. When solving multi-class classification problems, NPSVM will encounter the problem of sample noises, low discrimination speed and unrecognized regions, which will affect its performance. In this paper, based on the multi-class NPSVM model, two improvements are made, and a directed acyclic graph fuzzy nonparallel support vector machine (DAG-F-NPSVM) model is established. On the one hand, for the noises that may exist in the data set, the density information is used to add fuzzy membership to the samples, so that the contribution of each samples to the classification is treated differently. On the other hand, in order to reduce the decision time and solve the problem of unrecognized regions, the theory of directed acyclic graph (DAG) is introduced. Finally, the advantages of the new model in classification accuracy and decision speed is verified through UCI machine learning standard data set experiments. Finally, Friedman test and Bonferroni-Dunn test are used to verify the statistical significance of this new method.

Keywords

Multi-class classification problem nonparallel support vector machine fuzzy membership directed acyclic graph

1 Introduction

Machine learning is a common research hotspot in the field of artificial intelligence and pattern recognition, and support vector machine (SVM) is a supervised machine learning method. SVM is based on the structural risk minimization principle of statistical learning theory and the VC dimension theory [1]. It is proposed to solve the classification problem with the help of optimization theory. Compared with traditional models based on empirical risk minimization, SVM has better model generalization ability, and stronger learning ability for small sample, non-linear and high-dimensional data.

Initially, SVM was proposed for the binary classification problem. The former Soviet Union scholar Vladimir N. Vapnik and others discussed and established a standard support vector machine (C-SVM) [2]. In practical application research, many improved models have been put forward on the basis of C-SVM [3]. Some scholars proposed some parallel SVMs. For the least squares support vector machine (LSSVM) [4 –6] least squares function with equality constraints is used as a loss function instead of the complex quadratic programming problem of SVM, so the training speed is relatively fast. Since the training points in LSSVM all contribute to the decision function, the algorithm is not sparsity. For the ν-support vector machine (ν-SVM) [7 –9], a parameter ν lets one effectively control the number of support vectors. However, compared to regular C-SVM, the formulation of ν-SVM is more complicated, so up to now there have been no effective methods for solving large-scale classification problems with ν-SVM. Since the parallel SVMs does not consider the difference in data distribution of samples, some scholars proposed nonparallel SVMs on this basis. For the generalized eigenvalue proximal support vector machine (GEPSVM) [10 –12], each plane is as close as possible to one of the data sets and as far as possible from the other one. The nonparallel planes are eigenvectors corresponding to the smallest eigenvalues of two related generalized eigenvalue problems. However, as far as the classification rules of GEPSVM are concerned, classifying the sample to be tested as the nearest hyperplane will inevitably produce a large number of misclassified samples in the intersection area of the two fitted planes. For twin support vector machine (TWSVM) [13 –15], it seeks two nonparallel proximal hyperplanes such that each hyperplane is closer to one of the two classes and is at least one distance from the other. The result of this strategy is that TWSVM can solve two smaller quadratic programming problems (QPPs). But it must calculate the inverse of the matrix in the process of solving QPPs, which is difficult or even impossible for large data sets. For NPSVM [16], it seeks two nonparallel hyperplanes, such that each class locates as much as possible in the ɛ-band of the hyperplane and each hyperplane is at least one distance from the other. Compared with GEPSVM and TWSVM, NPSVM has the advantages of structural risk minimization principle, kernel trick and sparsity, so it has become a research hotspot in recent years [17 –22].

In practical applications, there are more common multi-class classification problems, and the application scope of NPSVM is limited. Therefore, how to effectively extend NPSVM to multi-class classification has become a research focus in this field. When establishing the multi-class classification model, some scholars consider all samples at one time and solve the optimization problem of a multi-objective function to achieve multi-class classification. Some scholars construct a series of binary classifiers in a certain way to realize multi-class classification. The latter has become a more widely used method by scholars due to its advantages such as reducing classification cost, improving classification accuracy and simplifying objective function. At present, two well-known strategies are One-Versus-Rest (OVR) strategy [23] and One-Versus-One (OVO) strategy [24]. In the training phase, OVR takes samples of a certain class as a separate class, and the samples of the other classes together as another class to form binary classification problems. In all binary classifiers, the class with the maximum value of the classification function is determined as the final result. But it has problems such as unrecognizable regions, unbalanced samples, and long training time. OVO constructs a classifier between every two classes, and evaluates the result of each decision function through voting. The class with the most votes is the final class. In practical applications, OVO is considered to be one of the most effective decomposition strategies due to its small solution scale, high classification accuracy, and fast training speed [25, 26]. Although OVO has these advantages in the training phase, it also has certain shortcomings. As the classes of samples increase, classifiers also increase rapidly, which will affect the decision-making speed. OVO also has problem of unrecognizable areas. In the voting phase, there may be situations that the voting results of several classes are the same, which will affect the performance of the classification. For OVO-NPSVM, when solving the multi-class classification problem, the above situation may be encountered. So this paper introduces the theory of directed acyclic graph (DAG) [27, 28] to solve the problem of unrecognizable area and speed up the decision-making.

Whether it is a binary classification problem or a multi-class one, the classifier will be affected by the noises in the samples, so the classification hyperplane is often not the true optimal one. At present, many scholars use the membership degree idea of fuzzy set theory to assign different samples with different penalty weights, so that the samples have different contributions to the objective function. This reduces the influence of noises to some extent. Lin [29, 30] et al. first proposed the fuzzy support vector machine (FSVM). According to the distance between the samples and the class center, the fuzzy membership degree with distinguishing ability was added to the training samples, but the support vector was not considered enough. Wu [31] et al. proposed a fuzzy multi-class classification support vector machine algorithm for unbalanced data. The algorithm uses the distance from the training samples to the class center and the weighted class overlap method to design fuzzy membership function for the samples. Ju [32] et al. proposed using fuzzy set theory, interval-valued fuzzy set theory and NPSVM theory to construct fuzzy nonparallel support vector machines and interval-valued fuzzy nonparallel support vector machines. Although the classification models with two membership degrees have better classification accuracy, the cost is that it takes time to adjust the parameters. In the current era of big data, a simple and effective method of adding membership should be the first choice. As OVO-NPSVM may be affected by noises when solving multi-class classification problems, this paper establishes a membership degree based on density for samples. The membership degree takes into account the structural information of the samples and effectively distinguishes the importance of different samples.

In summary, a novel nonparallel SVM, termed directed acyclic graph fuzzy nonparallel support vector machine (DAG-F-NPSVM) for multi-class classification is proposed in this paper. And it has the following incomparable over NPSVM.

The theory of DAG is introduced to solve the problem of unrecognizable area in OVO-NPSVM and speed up decision-making.

The fuzzy membership is added to the samples to solve the problem of noises, thus improving the classification accuracy.

In recent years, a series of achievements have been made in the research of multi-class classification support vector theory and algorithm. Among them, it is of great theoretical significance to study how to reduce the influence of sample noises and speed up decision-making. In addition, the application of multi-class classification model to recommendation algorithm, text classification, image recognition and other fields is also of great practical significance.

In this paper, many acronyms are used. To make it easier to understand, we summarize the important ones in Table 1.

Table 1
The full names and Acronyms of the main classifiers in the paper

Acronyms Full names

SVM Support vector machine

NPSVM Nonparallel support vector machine

OVO-SVM One-Versus-One support vector machine

DAG-SVM Directed acyclic graph Support Vector Machine

OVO-NPSVM One-Versus-One nonparallel support vector machine

DAG-NPSVM Directed acyclic graph nonparallel support vector machine

OVO-F-NPSVM One-Versus-One fuzzy nonparallel support vector machine

DAG-F-NPSVM Directed acyclic graph fuzzy nonparallel support vector machine

Acronyms	Full names
SVM	Support vector machine
NPSVM	Nonparallel support vector machine
OVO-SVM	One-Versus-One support vector machine
DAG-SVM	Directed acyclic graph Support Vector Machine
OVO-NPSVM	One-Versus-One nonparallel support vector machine
DAG-NPSVM	Directed acyclic graph nonparallel support vector machine
OVO-F-NPSVM	One-Versus-One fuzzy nonparallel support vector machine
DAG-F-NPSVM	Directed acyclic graph fuzzy nonparallel support vector machine

The structure of this article is as follows: Section 2 briefly reviews the basic concepts of NPSVM. The third section introduces the DAG-F-NPSVM method and gives the corresponding algorithm. The fourth section is the results and analysis of numerical experiments. The last section is the conclusion.

2 NPSVM

In this section, a review of linear and nonlinear NPSVM will be described briefly.

Consider the binary classification problem with the training set: $T = {(x_{1}, y_{1}), \dots, (x_{l}, y_{l})},$ where x_i ∈ Rⁿ are the inputs, y_i ∈ {-1, + 1} , i = 1, …, l are the outputs. The goal is to find the two hyperplanes $(w_{+} \cdot x) + b_{+} = 0$ (1)

and $(w_{-} \cdot x) + b_{-} = 0$ (2) on Rⁿ. For any new x, determine the label according to its distance to this two hyperplanes.

2.1 Linear NPSVM

For the linear classification problem, the two nonparallel hyperplanes (1) and (2) are solved by the following two convex QPPs, so that each class of points is located in the ɛ-band of the hyperplane as much as possible, and each hyperplane is at least one distance from the other. $\begin{matrix} min_{w_{+}, b_{+}, η_{+}^{(*)}, ξ_{-}} \frac{1}{2} {∥ w_{+} ∥}^{2} + C_{1} \sum_{i = 1}^{p} (η_{i} + η_{i}^{*}) + C_{2} \sum_{j = p + 1}^{p + q} ξ_{j} \\ s . t . (w_{+} \cdot x_{i}) + b_{+} ⩽ ɛ + η_{i}, i = 1, \dots, p \\ - (w_{+} \cdot x_{i}) - b_{+} ⩽ ɛ + η_{i}^{*}, i = 1, \dots, p \\ (w_{+} \cdot x_{j}) + b_{+} ⩽ - 1 + ξ_{j}, j = p + 1, \dots, p + q \\ η_{i}, η_{i}^{*} ⩾ 0, i = 1, \dots, p \\ ξ_{j} ⩾ 0, j = p + 1, \dots, p + q \end{matrix}$ (3)

and $\begin{matrix} min_{w_{-}, b_{-}, η_{-}^{(*)}, ξ_{+}} \frac{1}{2} {∥ w_{-} ∥}^{2} + C_{3} \sum_{i = p + 1}^{p + q} (η_{i} + η_{i}^{*}) + C_{4} \sum_{j = 1}^{p} ξ_{j} \\ s . t . (w_{-} \cdot x_{i}) + b_{-} ⩽ ɛ + η_{i}, i = p + 1, \dots, p + q \\ - (w_{-} \cdot x_{i}) - b_{-} ⩽ ɛ + η_{i}^{*}, i = p + 1, \dots, p + q \\ (w_{-} \cdot x_{j}) + b_{-} ⩾ 1 + ξ_{j}, j = 1, \dots, p \\ η_{i}, η_{i}^{*} ⩾ 0, i = p + 1, \dots, p + q \\ ξ_{j} ⩾ 0, j = 1, \dots, p \end{matrix}$ (4)

In the objective function of (3), $\frac{1}{2} | | w_{+} | |^{2}$ represents the purpose of maximizing the margin of hyperplanes; ξ_- = (ξ_p+1, …, ξ_p+q) ^T and $η_{+}^{(*)} = {(η_{1}, \dots, η_{p}, η_{1}^{*}, \dots, η_{p}^{*})}^{T}$ are slack variable; $\sum_{i = 1}^{p} (η_{i} + η_{i}^{*})$ represents the empirical risk, which limits the positive inputs to be located as much as possible in the ɛ-band between the hyperplanes (w₊ · x) + b₊ = ɛ and (w₊ · x) + b₊ = - ɛ, $\sum_{j = p + 1}^{p + q} ξ_{j}$ is another empirical risk, which limits the negative inputs to be located below the plane (w₊ · x) + b₊ = -1. The parameter C₁, C₂ (>0) controls the tradeoff between maximizing the boundary and the number of misclassifications. The geometric interpretation of NPSVM is depicted in Fig. 1.

Fig. 1

Geometrical illustration of NPSVM in R².

Introduce Lagrange multiplier vectors $α_{+}^{(*)} = (α_{1}, . . ., α_{p}, α_{1}^{*}, . . ., α_{p}^{*})^{T}, β_{-} = (β_{p + 1}, . . ., β_{p + q})^{T}$ and $α_{-}^{(*)} = (α_{p + 1}, . . ., α_{p + 1}, α_{p + 1}^{*}, . . ., α_{p + 1}^{*})^{T}$ , β₊ = (β₁, . . . , β_p) ^T. The Wolfe dual forms of the original questions (3) and (4) are:

$\begin{matrix} min_{α_{+}^{(*)}, β_{-}} \frac{1}{2} \sum_{i = 1}^{p} \sum_{j = 1}^{p} (α_{i}^{*} - α_{i}) (α_{j}^{*} - α_{j}) (x_{i} \cdot x_{j}) \\ - \sum_{i = 1}^{p} \sum_{j = p + 1}^{p + q} (α_{i}^{*} - α_{i}) β_{j} (x_{i} \cdot x_{j}) \\ + \frac{1}{2} \sum_{i = p + 1}^{p + q} \sum_{j = p + 1}^{p + q} β_{i} β_{j} (x_{i} \cdot x_{j}) \\ + ɛ \sum_{i = 1}^{p} (α_{i}^{*} + α_{i}) - \sum_{j = p + 1}^{p + q} β_{j} \\ s . t . \sum_{i = 1}^{p} (α_{i} - α_{i}^{*}) + \sum_{j = p + 1}^{p + q} β_{j} = 0 \\ 0 ⩽ α_{i}, α_{i}^{*} ⩽ C_{1}, i = 1, \dots, p, \\ 0 ⩽ β_{j} ⩽ C_{2}, j = p + 1, \dots, p + q . \end{matrix}$ (5)

and $\begin{matrix} min_{α_{-}^{(*)}, β_{+}} \frac{1}{2} \sum_{i = p + 1}^{p + q} \sum_{j = p + 1}^{p + q} (α_{i}^{*} - α_{i}) (α_{j}^{*} - α_{j}) (x_{i} \cdot x_{j}) \\ + \sum_{i = p + 1}^{p + q} \sum_{j = 1}^{p} (α_{i}^{*} - α_{i}) β_{j} (x_{i} \cdot x_{j}) \\ + \frac{1}{2} \sum_{i = 1}^{p} \sum_{j = 1}^{p} β_{i} β_{j} (x_{i} \cdot x_{j}) \\ + ɛ \sum_{i = p + 1}^{p + q} (α_{i}^{*} + α_{i}) - \sum_{j = 1}^{p} β_{j} \\ s . t . \sum_{i = p + 1}^{p + q} (α_{i} - α_{i}^{*}) - \sum_{j = 1}^{p} β_{i} = 0 \\ 0 ⩽ α_{i}, α_{i}^{*} ⩽ C_{3}, i = p + 1, \dots, p + q, \\ 0 ⩽ β_{j} ⩽ C_{4}, j = 1, \dots, p . \end{matrix}$ (6)

By solving the dual problems (5) and (6), w₊ and w_- can be obtained respectively, and the expressions are: $w_{+} = \sum_{i = 1}^{p} (α_{i}^{*} - α_{i}) x_{i} - \sum_{j = p + 1}^{p + q} β_{j} x_{j}$ (7)

and $w_{-} = \sum_{i = p + 1}^{p + q} (α_{i}^{*} - α_{i}) x_{i} - \sum_{j = 1}^{p} β_{j} x_{j}$ (8)

Choose a component of $α_{+}^{(*)}, α_{i} \in (0, c_{3}), i = p + 1, . . ., p + q$ , we have: $b_{+} = - (w_{+} \cdot x_{i}) + ɛ$ (9)

and $b_{-} = - (w_{-} \cdot x_{i}) + ɛ$ (10)

The decision functions are: $f_{+} (x) = \sum_{i = 1}^{p} (α_{i}^{*} - α_{i}) (x_{i} \cdot x) - \sum_{j = p + 1}^{p + q} β_{j} (x_{j} \cdot x) + b_{+}$ (11)

and $f_{-} (x) = \sum_{i = p + 1}^{p + q} (α_{i}^{*} - α_{i}) (x_{i} \cdot x) - \sum_{j = 1}^{p} β_{j} (x_{j} \cdot x) + b_{-}$ (12)

A new test point x is classified as +1 or –1 depending on which of the two hyperplanes it lies closer to, i.e. $class i = \underset{k = +, -}{arg min} \frac{| w_{k} \cdot x + b_{k} |}{∥ w_{k} ∥}$ (13) where | · | takes the absolute value and ∥ · ∥ denotes the L₂ norm.

2.2 Nonlinear NPSVM

In many cases, the data samples cannot be separated by the linear class boundary. Therefore, we can use the kernel trick to extend the linear NPSVM to the nonlinear case. After the sample are projected into the high-dimensional feature space, they are easier to separate. By introducing kernel function K (x_i, x_j) = φ (x_i) · φ (x_j) and the corresponding transformation x = φ (x), where $x \in H$ , $H$ is the Hilbert space. We can construct the corresponding problems of (3) and (4) in $H$ , the only difference is that the weight vectors w₊ and w_- in Rⁿ change to w₊ and w_-, respectively. The optimization problems corresponding to problems (3) and (4) are as follows: $\begin{matrix} min_{α_{+}^{(*)}, β_{-}} \frac{1}{2} \sum_{i = 1}^{p} \sum_{j = 1}^{p} (α_{i}^{*} - α_{i}) (α_{j}^{*} - α_{j}) K (x_{i}, x_{j}) \\ - \sum_{i = 1}^{p} \sum_{j = p + 1}^{p + q} (α_{i}^{*} - α_{i}) β_{j} K (x_{i}, x_{j}) \\ + \frac{1}{2} \sum_{i = p + 1}^{p + q} \sum_{j = p + 1}^{p + q} β_{i} β_{j} K (x_{i}, x_{j}) \\ + ɛ \sum_{i = 1}^{p} (α_{i}^{*} + α_{i}) - \sum_{j = p + 1}^{p + q} β_{j} \\ s . t . \sum_{i = 1}^{p} (α_{i} - α_{i}^{*}) + \sum_{j = p + 1}^{p + q} β_{j} = 0 \\ 0 ⩽ α_{i}, α_{i}^{*} ⩽ C_{1}, i = 1, \dots, p, \\ 0 ⩽ β_{j} ⩽ C_{2}, j = p + 1, \dots, p + q . \end{matrix}$ (14)

and $\begin{matrix} \min_{α_{-}^{(*)}, β_{+}} \frac{1}{2} \sum_{i = p + 1}^{p + q} \sum_{j = p + 1}^{p + q} (α_{i}^{*} - α_{i}) (α_{j}^{*} - α_{j}) K (x_{i}, x_{j}) \\ + \sum_{i = p + 1}^{p + q} \sum_{j = 1}^{p} (α_{i}^{*} - α_{i}) β_{j} K (x_{i}, x_{j}) \\ + \frac{1}{2} \sum_{i = 1}^{p} \sum_{j = 1}^{p} β_{i} β_{j} K (x_{i}, x_{j}) \\ + ɛ \sum_{i = p + 1}^{p + q} (α_{i}^{*} + α_{i}) - \sum_{j = 1}^{p} β_{j} \\ s . t . \sum_{i = p + 1}^{p + q} (α_{i} - α_{i}^{*}) - \sum_{j = 1}^{p} β_{j} = 0 \\ 0 ⩽ α_{i}, α_{i}^{*} ⩽ C_{3}, i = p + 1, \dots, p + q, \\ 0 ⩽ β_{j} ⩽ C_{4}, j = 1, \dots, p . \end{matrix}$ (15)

Its decision function and discriminant method are also determined in a similar way to linear NPSVM: $f_{+} (x) = \sum_{i = 1}^{p} (α_{i}^{*} - α_{i}) K (x_{i}, x) - \sum_{j = p + 1}^{p + q} β_{j} K (x_{j}, x) + b_{+}$ (16)

Fig. 2

Flow chart of DAG-F-NPSVM.

and $f_{-} (x) = \sum_{i = p + 1}^{p + q} (α_{i}^{*} - α_{i}) K (x_{i}, x) - \sum_{j = 1}^{p} β_{j} K (x_{j}, x) + b_{-}$ (17)

The way to identify an unknown sample is similar to the linear problem.

3 DAG-F-NPSVM

In this paper, on the basis of multi-class classification NPSVM, the idea of fuzzy membership in fuzzy set theory and DAG in graph theory are introduced at the same time, thereby constructing DAG-F-NPSVM model. The introduction of fuzzy membership is to reduce the influence of sample noise on finding the optimal hyperplane. The introduction of the directed acyclic graph theory is to overcome the problem of unrecognizable areas in the multi-class classification and reduce the decision-making time. The detailed flow chart of this method is shown in Fig. 2.

3.1 Fuzzy membership based on sample density

Adding membership degree to the samples can improve the classification accuracy of the model to a certain extent. However, it is not advisable to add too complex membership in the classification of large data sets. The membership degree added to the samples in this paper is an improved one related to density. It makes use of the distribution information of samples and treats each sample differently for the importance of decision function. At the same time, it also considers the simplicity and operability in calculation.

Given data set $T = {(x_{1}, y_{1}), . . ., (x_{l}, y_{l})},$ where x_i ∈ Rⁿ, y_i ∈ {1, . . . , M} , i = 1, . . . , l.

Let

$\begin{matrix} τ (x_{i}, r) = Num {x_{j} | D (x_{i}, x_{j}) \\ ⩽ r, i = 1, 2, \dots, l; j = 1, 2, \dots, l} \end{matrix}$ (18) indicates the number of all samples in the circle with x_i as the center and r as the radius;

$\begin{matrix} τ^{+} (x_{i}, r) = Num {x_{j} | D (x_{i}, x_{j}) \\ ⩽ r, y_{i} = y_{j}, i = 1, 2, \dots, l; j = 1, 2, \dots, l} \end{matrix}$ (19) indicates the number of all samples of the same kind in the circle with x_i as the center and r as the radius;

$\begin{matrix} τ^{-} (x_{i}, r) = Num {x_{j} | D (x_{i}, x_{j}) \\ ⩽ r, y_{i} \neq y_{j}, i = 1, 2, \dots, l; j = 1, 2, \dots, l} \end{matrix}$ (20) indicates the number of all heterogeneous samples in the circle with x_i as the center and r as the radius.

Obviously, $τ (x_{i}, r) = τ^{+} (x_{i}, r) + τ^{-} (x_{i}, r) .$ (21)

Establish fuzzy membership based on sample density for x_i: $u (x_{i}) = \frac{τ^{+} (x_{i}, r)}{max_{k} τ^{+} (x_{k}, r)} \cdot \frac{τ^{+} (x_{i}, r)}{τ (x_{i}, r)}$ (22) where, x_k and x_i belong to the same class.

The membership degree consists of the product of two ratios. First of all, find the number of homogeneous samples in the circle of samples x with radius r. After that, divide it by the number of homogeneous samples in the densest circle of the class to obtain the first ratio. Then divide it by the number of all samples in the r circle of the samples to the second ratio. The membership degree of this product form indicates that when x_i is densely distributed with homogeneous points and relatively sparsely distributed with heterogeneous points, u (x_i) approaches 1. Meanwhile, when x_i is sparsely distributed with homogeneous points and relatively densely distributed with heterogeneous points, u (x_i) tends to be 0. In this way, from the membership degree u (x_i), we can see the relative density of x_i.

3.2 DAG-F-NPSVM model and algorithm

In the training phase, DAG-F-NPSVM uses the pairwise classification method. That is, one class and the other class are used for training. For the M-class classification problem, it is necessary to construct (M-1)/2 NPSVMs and solve M(M-1) QPPs to obtain M(M-1) nonparallel hyperplanes. In the testing phase, this method constructs all classifiers into a two-way DAG, which includes M(M-1)/2 nodes and M leaves. Among them, each node is an NPSVM classifier and is connected to two nodes (or leaves) in the next layer. The vertex contains only one node, which is called the root node. The second layer has two nodes, and so on, the i_th layer contains i nodes, the bottom layer contains M leaf nodes, among them the i_th node of the j_th layer points to the i_th and i + 1_th nodes of the j + 1_th layer. When an unknown sample is classified, it starts from the root node at the top. According to the classification results of the root node, the left node or right node of the next layer is used to continue the classification until a leaf at the bottom is reached. The class represented by the leaf is the class of the unknown sample.

3.2.1 Linear DAG-F-NPSVM

Consider the training set for a multi-class classification problem: $T = {(x_{1}, y_{1}), . . ., (x_{l}, y_{l})},$ where x_i ∈ Rⁿ, y_i ∈ {1, . . . , M} , i = 1, . . . , l.

We aim to construct M nonparallel hyperplanes $(w_{m} \cdot x) + b_{m} = 0, m = 1, . . ., M$ (23) by solving the following convex QPPs for each one.

In the class M, if the samples of the i_th class is trained with the samples of the j_th class. It is required that samples of the i_th class should be located in the ɛ-band of its hyperplane as much as possible, and the i_th hyperplane should be at least one distance from the j_th hyperplane. Then the linear DAG-F-NPSVM classifier solves following two QPPs: $\begin{matrix} min_{w_{ij}, b_{ij}, η_{ij}^{(*)}, ξ_{ji}} \frac{1}{2} {∥ w_{ij} ∥}^{2} + C_{1} u_{ij} e_{i}^{T} (η_{ij} + η_{ij}^{*}) + C_{2} u_{ji} e_{j}^{T} ξ_{ji} \\ s . t . {Aw}_{ij} + e_{i} b_{ij} ⩽ ɛ e_{i} + η_{ij}, \\ - {Aw}_{ij} - e_{i} b_{ij} ⩽ ɛ e_{i} + η_{ij}^{*}, \end{matrix}$ $\begin{matrix} {Bw}_{ij} + e_{i} b_{ij} ⩽ - e_{j} + ξ_{ji}, \\ η_{ij}, η_{ij}^{*} ⩾ 0, ξ_{ji} ⩾ 0 \\ i = 1, . . ., M, j = 1, . . ., M, i \neq j \end{matrix}$ (24)

and $\begin{matrix} min_{w_{ji}, b_{ji}, η_{ji}^{(*)}, ξ_{ij}} \frac{1}{2} {∥ w_{ji} ∥}^{2} + C_{3} u_{ji} e_{j}^{T} (η_{ji} + η_{ji}^{*}) + C_{4} u_{ij} e_{i}^{T} ξ_{ij} \\ s . t . {Bw}_{ij} + e_{j} b_{ji} ⩽ e_{j} ɛ + η_{ji} \\ - {Bw}_{ji} - e_{j} b_{ji} ⩽ e_{j} ɛ + η_{ji}^{*} \\ {Aw}_{ji} + e_{j} b_{ji} ⩾ e_{i} - ξ_{ij} \\ η_{ji}, η_{ji}^{*} ⩾ 0, ξ_{ij} ⩾ 0 \\ i = 1, . . ., M, j = 1, . . ., M, i \neq j \end{matrix}$ (25) where, A = (x₁, . . . , x_p) ^T ∈ R^p×n represents the samples of the i_th class, B = (x_p+1, . . . , x_p+q) ^T ∈ R^q×n represents the samples of the j_t h class, C_i ⩾ 0, i = 1, . . . , 4 are the penalty parameters, u_ij and u_ji are the membership degrees of samples in the i_th class and the j_t h class respectively, and ξ_ij = (ξ₁, . . . , ξ_p) ^T, ξ_ji = (ξ_p+1, . . . , ξ_p+q) ^T, $η_{ij}^{(*)} = (η_{1}, . . ., η_{p}, η_{1}^{*}, . . ., η_{p}^{*})^{T}$ , $η_{ji}^{(*)} = (η_{p + 1}, . . ., η_{p + q}$ , $η_{p + 1}^{*}, . . ., η_{p + q}^{*})^{T}$ are slack variables.

In order to obtain the solutions of (24) and (25), we need to solve the dual problem. Taking formula (24) as an example, construct the Lagrangian function: $\begin{matrix} L (w_{ij}, b_{ij}, η_{ij}^{(*)}, ξ_{ji}, α_{i}^{(*)}, β_{j}, γ_{i}^{(*)}, λ_{j}) \\ = \frac{1}{2} {∥ w_{ij} ∥}^{2} + C_{1} u_{ij} e_{i}^{T} (η_{ij} + η_{ij}^{*}) + C_{2} u_{ji} e_{j}^{T} ξ_{ji} \\ + α_{i}^{T} ({Aw}_{ij} + e_{i} b_{ij} - e_{i} ɛ - η_{ij}) \\ + α_{i}^{* T} (- {Aw}_{ij} - e_{i} b_{ij} - e_{i} ɛ - η_{ij}^{*}) \\ + β_{j}^{T} ({Bw}_{ij} + e_{i} b_{ij} + e_{j} - η_{ji}) \\ - γ_{i}^{T} η_{ij} - γ_{i}^{* T} η_{ij}^{*} - λ_{j}^{T} ξ_{ji} \end{matrix}$ (26) where $α_{i}^{(*)} = (α_{1}, . . ., α_{p}, α_{1}^{*}, . . ., α_{p}^{*})^{T}$ , β_j = (β_p+1, . . . , β_p+q) ^T, $γ_{i}^{(*)} = (γ_{1}, . . ., γ_{p}, γ_{p + 1}, . . ., γ_{p + q})^{T}, λ_{j} = (λ_{p + 1}, . . ., λ_{p + q})^{T}$ , are all Lagrange multiplier vectors. According to the Karush–Kuhn–Tucker (KKT) [33]: $\nabla_{w_{ij}} L = w_{ij} + A^{T} α_{i} - A^{T} α_{i}^{*} + B^{T} β_{j} = 0$ (27) $\nabla_{b_{ij}} L = e_{i}^{T} α_{i} - e_{i}^{T} α_{i}^{*} + e_{j}^{T} β_{j} = 0$ (28) $\nabla_{η_{ij}} L = C_{1} u_{ij} e_{i} - α_{i} - γ_{j} = 0$ (29) $\nabla_{η_{ij}^{*}} L = C_{1} u_{ij} e_{i} - α_{i}^{*} - γ_{i}^{*} = 0$ (30) $\nabla_{ξ_{ji}} L = C_{2} u_{ji} e_{j} - β_{j} - λ_{j} = 0$ (31) ${Aw}_{ij} + e_{i} b_{ij} ⩽ e_{i} ɛ + η_{ij}$ (32) $- {Aw}_{ij} - e_{i} b_{ij} ⩽ e_{i} ɛ + η_{ij}^{*}$ (33) ${Bw}_{ij} + e_{i} b_{ij} ⩽ - e_{j} + ξ_{ji}$ (34) $η_{ij}, η_{ij}^{*} ⩾ 0$ (35) $ξ_{ji} ⩾ 0$ (36) where, e_i = (1, . . . , 1) ^T ∈ R^p, e_j = (1, . . . , 1) ^T ∈ R^q, because $γ_{i}, γ_{i}^{*} ⩾ 0, λ_{j} ⩾ 0$ _, from (29), (30) and (31), we can get: $0 ⩽ α_{i}, α_{i}^{*} ⩽ C_{1} u_{ij} e_{i}$ (37) $0 ⩽ β_{j} ⩽ C_{2} u_{ji} e_{j}$ (38)

From Equation (27) we can get: $w_{ij} = A^{T} (α_{i}^{*} - α_{i}) - B^{T} β_{j}$ (39)

Then substituting Equation (39) into Equation (26) and combining Equations (27)–(36), the dual problem of the original problem (24) can be obtained: $\begin{matrix} min_{α_{i}^{(*)}, β_{j}} \frac{1}{2} (α_{i}^{*} - α_{i})^{T} {AA}^{T} (α_{i}^{*} - α_{i}) - (α_{i}^{*} - α_{i})^{T} {AB}^{T} β_{j} \\ + \frac{1}{2} β_{j}^{T} {BB}^{T} β_{j} + ɛ e_{i}^{T} (α_{i}^{*} + α_{i}) - e_{j}^{T} β_{j} \\ s . t . e_{i}^{T} (α_{i} - α_{i}^{*}) + e_{j}^{T} β_{j} = 0 \\ 0 ⩽ α_{i}, α_{i}^{*} ⩽ C_{1} u_{ij} e_{i} \\ 0 ⩽ β_{j} ⩽ C_{2} u_{ji} e_{j} \\ i = 1, . . ., M, j = 1, . . ., M, i \neq j \end{matrix}$ (40)

When formula (39) is obtained, a component $α_{i}^{*} \in (0, C_{1})$ in the support vector $α_{ij}^{*}$ is selected, and b_ij can be calculated: $b_{ij} = - {Aw}_{ij} - ɛ$ (41)

Similarly, we can also get the dual problem of the original problem (25): $\begin{matrix} min_{α_{j}^{(*)}, β_{i}} \frac{1}{2} (α_{j}^{*} - α_{j})^{T} {BB}^{T} (α_{j}^{*} - α_{j}) + (α_{j}^{*} - α_{j})^{T} {BA}^{T} β_{i} \\ + \frac{1}{2} β_{i}^{T} {AA}^{T} β_{i} + ɛ e_{j}^{T} (α^{*} + α) - e_{i}^{T} β_{i} \\ s . t . e_{j}^{T} (α_{j} - α_{j}^{*}) - e_{i}^{T} β_{i} = 0, \\ 0 ⩽ α_{j}, α_{j}^{*} ⩽ C_{3} u_{ji} e_{j}, \\ 0 ⩽ β_{i} ⩽ C_{4} u_{ij} e_{i} \\ i = 1, . . ., M, j = 1, . . ., M, i \neq j \end{matrix}$ (42)

and $w_{ji} = B^{T} (α_{j}^{*} - α_{j}) - A^{T} β_{i}$ (43)

When a component $α_{j}^{*} \in (0, C_{3})$ in the support vector $α_{ji}^{*}$ is selected, b_ji can be calculated: $b_{ji} = - {Bw}_{ji} - ɛ$ (44)

Once we get solutions (w_ij, b_ij) and (w_ji, b_ji) in problems (24) and (25). A new testing point x is classified as i_th or j_th depending on which of the two hyperplanes it lies closer to, i.e., $Class x = \underset{k = ij, ji}{arg min} \frac{| (w_{k} \cdot x) + b_{k} |}{∥ w_{k} ∥}$ (45)

The decision method by DAG-F-NPSVM is shown in Fig. 3. If we consider four classes, DAG-F-NPSVM will comprise 4*3/2 = 6 internal nodes. However, a new test point only needs to be judged by three classifiers to get the judgment result.

Fig. 3

The decision method of four-class classification of DAG-F-NPSVM.

3.2.2 Nonlinear DAG-F-NPSVM

In the original problems (24) and (25), the kernel functions K (x, x^T) = φ (x) · φ (x) ^T can be applied directly in order to extend the linear DAG-F-NPSVM to the nonlinear case. The corresponding optimization problems are as follows: $\begin{matrix} min_{α_{i}^{(*)}, β_{j}} \frac{1}{2} (α_{i}^{*} - α_{i})^{T} K (A, A^{T}) (α_{i}^{*} - α_{i}) \\ + (α_{i}^{*} - α_{i})^{T} K (A, B^{T}) β_{j} \\ + \frac{1}{2} β_{j}^{T} K (B, B^{T}) β_{j} \end{matrix}$

$\begin{matrix} + ɛ e_{i}^{T} (α_{i}^{*} + α_{i}) - e_{j}^{T} β_{j} \\ s . t . e_{i}^{T} (α_{i} - α_{i}^{*}) - e_{j}^{T} β_{j} = 0 \\ 0 ⩽ α_{i}, α_{i}^{*} ⩽ C_{1} u_{ij} e_{i} \\ 0 ⩽ β_{j} ⩽ C_{2} u_{ji} e_{j} \\ i = 1, . . ., M, j = 1, . . ., M, i \neq j \end{matrix}$ (46)

and $\begin{matrix} min_{α_{j}^{(*)}, β_{i}} \frac{1}{2} (α_{j}^{*} - α_{j})^{T} K (B, B^{T}) (α_{j}^{*} - α_{j}) \\ + (α_{j}^{*} - α_{j})^{T} K (B, A^{T}) β_{i} \\ + \frac{1}{2} β_{i}^{T} K (A, A^{T}) β_{i} \\ + ɛ e_{j}^{T} (α^{*} + α) - e_{i}^{T} β_{i} \\ s . t . e_{j}^{T} (α_{j} - α_{j}^{*}) - e_{i}^{T} β_{i} = 0 \\ 0 ⩽ α_{j}, α_{j}^{*} ⩽ C_{3} u_{ji} e_{j} \\ 0 ⩽ β_{i} ⩽ C_{4} u_{ij} e_{i} \\ i = 1, . . ., M, j = 1, . . ., M, i \neq j \end{matrix}$ (47)

The way to identify an unknown sample is similar to the linear problem.

Regardless of the linear or non-linear DAG-F-NPSVM model, if the fuzzy membership takes a constant value of one, it means that all samples are treated equally and given the same weight. The model will degenerate into a directed acyclic graph nonparallel support vector machine (DAG-NPSVM). Therefore, DAG-NPSVM is a special case of DAG-F-NPSVM.

The algorithm for the DAG-F-NPSVM is described as follows:

Training phase

Input the training set A and B

for i = 1 to M, j = j+1 to M

If i_th class is trained with j_th class.

1. Define fuzzy membership degree for x by the formula (22);

2. Choose appropriate parameters ɛ > 0, C₁, C₂ > 0 for problem (40), C₃, C₄ > 0 for problem (42);

3. Choose appropriate kernel K, construct and solve the two convex QPPs (46) and (47), then obtain α^(*) and β;

4. Construct the decision functions $f_{ij} (x) = K (x, A^{T}) \cdot (α_{i}^{*} - α_{i}) + K (x, B^{T}) \cdot β_{i} + b_{ij}$

and $f_{ji} (x) = K (x, B^{T}) \cdot (α_{i}^{*} - α_{i}) + K (x, A^{T}) \cdot β_{j} + b_{ji}$

separately.

end

Testing phase

for a test data, define i = 1 and j = M.

while (i !=j)

If Class_i < Class_j

j = j - 1

else

i = i + 1

end

return Class _i

3.3 Computational complexity

When DAG-F-NPSVM algorithm is used for the M-class classification problem with l samples, M(M-1)/2 binary NPSVM classifiers are constructed to solve M(M-1) QPPs. Assume that samples are evenly distributed among the classes, so that each class contains approximately l / M samples. The DAG-F-NPSVM classifier is trained with a pairwise classification method. That is, all possible binary classifiers are constructed from the training set of M classes, and each classifier is only trained between two classes. Each class provides constraints for another class. In this way, each binary classifier is given l/M constraints. Therefore, the training complexity of the DAG-F-NPSVM classifier is: $O (M (M - 1) (\frac{l}{M})^{3}) = O (\frac{l^{3} (M - 1)}{M^{2}})$

Since fuzzy membership degree is added before training, it doesn’t affect training complexity.

4 Numerical experiment and analysis

4.1 Experimental environment and data

In order to verify the performance of DAG-F-NPSVM, we compare it with OVO-SVM, DAG-SVM, OVO-NPSVM, OVO-F-NPSVM and DAG-NPSVM on different types of data sets. These methods are all performed on a PC with Intel(R) Core (TM)i5-3317U 1.70 GHz processor and 4GB memory in MATLAB 2014b. In this paper, from the UCI database [34] these 10 data sets are selected for training and testing, including Iris, Wine, Seeds, Soybeans, E coli, Glass, Vowels, Dermatology, Zoo, and Yeast. The number of samples, feature dimensions, and the number of classes of each data set are shown in Table 2.

Table 2
Basic data set description

Data sets Number of samples Feature dimension Number of classes

Iris 150 4 3

Wine 178 13 3

Seeds 210 7 3

Soybean 47 35 4

E coli 327 7 5

Glass 214 9 6

Vowel 871 3 6

Dermatology 358 34 6

Zoo 101 16 7

Yeast 1484 8 10

Data sets	Number of samples	Feature dimension	Number of classes
Iris	150	4	3
Wine	178	13	3
Seeds	210	7	3
Soybean	47	35	4
E coli	327	7	5
Glass	214	9	6
Vowel	871	3	6
Dermatology	358	34	6
Zoo	101	16	7
Yeast	1484	8	10

4.2 Numerical experiment

In order to compare the test results fairly, the five-fold cross-validation method is adopted in this article, that is, the data set is randomly divided into five groups, four of which are used as training samples, and the other group is used as test samples. Repeat the experiment five times to make each group of data equal as a test sample. Different parameter settings have a certain impact on the classification results. The grid search method is used to optimize the parameters, and the kernel function uses Gaussian kernel function (RBF): $K (x_{i}, x_{j}) = exp (- {\frac{∥ x_{i} - x_{j} ∥}{2 p^{2}}}^{2})$ . The optimal parameters are used for five-fold cross-validation, and the average of five experiments is taken as the final classification accuracy. Table 3 shows the comparison results in terms of accuracy and training time for OVO-SVM, DAG-SVM, OVO-NPSVM, OVO-F-NPSVM, DAG-NPSVM and DAG-F-NPSVM in ten datasets. Table 4 records the test time of these six classifiers.

Table 3
Comparison of classification results of several multi-class classification models

Data sets OVO-SVM DAG-SVM OVO-NPSVM OVO-F-NPSVM DAG-NPSVM DAG-F-NPSVM

acc(%)±var training time(s) acc(%)±var training time(s) acc(%)±var training time(s) acc(%)±var training time(s) acc(%)±var training time(s) acc(%)±var training time(s)

Soybean (47×35×4) 100 ± 0 0.0105 100 ± 0 0.0104 100 ± 0 0.0036 100 ± 0 0.0043 100 ± 0 0.0039 100 ± 0 0.0041

Zoo (101×16×7) 93.09±4.86 0.0107 93.85±4.16 0.0110 97.00±2.46 0.0044 97.81±2.43 0.0048 97.54±2.14 0.0050 98.41 ± 1.95 0.0042

Iris (150×4×3) 96.67±3.65 0.0158 96.67±3.65 0.0154 97.33±2.49 0.0054 98.33 ± 2.37 0.0047 97.33±2.49 0.0051 98.33 ± 2.37 0.0055

Wine (178×13×3) 97.19±3.04 0.0158 97.46±2.96 0.0147 100 ± 0 0.0065 100 ± 0 0.0068 100 ± 0 0.0063 100 ± 0 0.0070

Seeds (210×7×3) 93.33±3.16 0.0223 92.86±2.13 0.0217 95.71±2.33 0.0068 96.24 ± 1.51 0.0070 95.3±2.33 0.0074 96.10±1.51 0.0064

Glass (214×9×6) 61.23±2.74 0.0132 61.23±2.74 0.0145 70.58±2.81 0.0063 71.01 ± 3.38 0.0065 70.32±2.71 0.0067 70.98±2.20 0.0069

E coli (327×7×5) 85.02±2.16 0.0245 84.78±2.64 0.0221 88.67±2.90 0.0073 89.30±3.84 0.0080 88.70±2.87 0.0072 89.55 ± 3.84 0.0075

Dermatology (358×34×6) 95.55±1.81 0.0268 95.74±1.74 0.0297 98.25±1.58 0.0081 99.14±1.86 0.0083 98.61±1.64 0.0079 99.57 ± 1.86 0.0087

Vowel (871×3×6) 85.30±2.88 0.1158 85.44±2.66 0.1199 85.66±2.53 0.0310 86.22±2.45 0.0334 85.85±2.89 0.0324 86.51 ± 2.28 0.0315

Yeast (1484×8×10) 58.48±3.01 0.1268 58.71±2.92 0.1253 63.42±2.52 0.0553 64.35±2.40 0.0551 63.70±2.32 0.0547 64.64 ± 2.44 0.0542

Average accuracy 86.59 86.67 89.66 90.24 89.74 90.41

Data sets	OVO-SVM	DAG-SVM	OVO-NPSVM	OVO-F-NPSVM	DAG-NPSVM	DAG-F-NPSVM
Soybean (47×35×4)	100 ± 0 0.0105	100 ± 0 0.0104	100 ± 0 0.0036	100 ± 0 0.0043	100 ± 0 0.0039	100 ± 0 0.0041
Zoo (101×16×7)	93.09±4.86 0.0107	93.85±4.16 0.0110	97.00±2.46 0.0044	97.81±2.43 0.0048	97.54±2.14 0.0050	98.41 ± 1.95 0.0042
Iris (150×4×3)	96.67±3.65 0.0158	96.67±3.65 0.0154	97.33±2.49 0.0054	98.33 ± 2.37 0.0047	97.33±2.49 0.0051	98.33 ± 2.37 0.0055
Wine (178×13×3)	97.19±3.04 0.0158	97.46±2.96 0.0147	100 ± 0 0.0065	100 ± 0 0.0068	100 ± 0 0.0063	100 ± 0 0.0070
Seeds (210×7×3)	93.33±3.16 0.0223	92.86±2.13 0.0217	95.71±2.33 0.0068	96.24 ± 1.51 0.0070	95.3±2.33 0.0074	96.10±1.51 0.0064
Glass (214×9×6)	61.23±2.74 0.0132	61.23±2.74 0.0145	70.58±2.81 0.0063	71.01 ± 3.38 0.0065	70.32±2.71 0.0067	70.98±2.20 0.0069
E coli (327×7×5)	85.02±2.16 0.0245	84.78±2.64 0.0221	88.67±2.90 0.0073	89.30±3.84 0.0080	88.70±2.87 0.0072	89.55 ± 3.84 0.0075
Dermatology (358×34×6)	95.55±1.81 0.0268	95.74±1.74 0.0297	98.25±1.58 0.0081	99.14±1.86 0.0083	98.61±1.64 0.0079	99.57 ± 1.86 0.0087
Vowel (871×3×6)	85.30±2.88 0.1158	85.44±2.66 0.1199	85.66±2.53 0.0310	86.22±2.45 0.0334	85.85±2.89 0.0324	86.51 ± 2.28 0.0315
Yeast (1484×8×10)	58.48±3.01 0.1268	58.71±2.92 0.1253	63.42±2.52 0.0553	64.35±2.40 0.0551	63.70±2.32 0.0547	64.64 ± 2.44 0.0542
Average accuracy	86.59	86.67	89.66	90.24	89.74	90.41

Table 4

Test time comparison of several multi-class classification models (s)

Data sets	OVO-SVM	DAG-SVM	OVO-NPSVM	OVO-F-NPSVM	DAG-NPSVM	DAG-F-NPSVM
Soybean (47×35×4)	0.0120	0.0082	0.0126	0.0122	0.0106	0.0097
Zoo (101×16×7)	0.0717	0.0395	0.0705	0.0758	0.0206	0.0203
Iris (150×4×3)	0.0441	0.0268	0.0481	0.0420	0.0178	0.0200
Wine (178×13×3)	0.0611	0.0375	0.0622	0.0651	0.0296	0.0281
Seeds (210×7×3)	0.0786	0.0520	0.0712	0.0726	0.0541	0.0558
Glass (214×9×6)	0.2330	0.1140	0.2701	0.2773	0.1245	0.1211
E coli (327×7×5)	0.3594	0.1214	0.3569	0.3577	0.1152	0.1288
Dermatology (358×34×6)	0.5601	0.2607	0.5384	0.5383	0.2667	0.2464
Vowel (871×3×6)	3.3250	1.5086	3.3514	3.3560	1.4279	1.5597
Yeast (1484×8×10)	16.3071	8.4084	16.0245	16.0325	8.4156	8.3015
Average time	2.1052	1.0577	2.0806	2.0830	1.0483	1.0491

4.3 Analysis of experimental results

Table 3, it can be found that among the 10 data sets, the classification accuracy of DAG-F-NPSVM ranks first on 8 data sets, two of which are tied for first on one data set. Therefore, the average accuracy of DAG-F-NPSVM ranks first, OVO-F-NPSVM ranks second, DAG-NPSVM ranks third, OVO-NPSVM ranks fourth, DAG-SVM ranks fifth, and OVO-SVM ranks last.

DAG-NPSVM is an improvement of DAG-SVM, which increases the average accuracy of DAG-SVM by 3.41%. For OVO-NPSVM and OVO-SVM, the average accuracy of OVO-NPSVM is also 3.44% higher than that of OVO-SVM. It shows that in this experiment, for the same multi-class classification strategy, the classify-cation result of NPSVM is much better than SVM.

Compared with the multi-class classification under the DAG and OVO strategies, the average accuracy of DAG-SVM is about 0.1% higher than that of OVO-SVM, the average accuracy of DAG-NPSVM is about 0.1% higher than that of OVO-NPSVM, and the average accuracy of DAG-F-NPSVM is about 0.19% higher than that of OVO-F-NPSVM, which proves that the accuracy of the classifier in DAG strategy is slightly higher than that in OVO strategy.

DAG-F-NPSVM is another improvement of DAG-NPSVM. It increases the average accuracy of DAG-NPSVM by 0.75%. And OVO-F-NPSVM is 0.64% higher than that of OVO-NPSVM, indicating that adding fuzzy member-ship will increase the classification accuracy and achieve the purpose of reducing the impact of noises in the sample. A new classification method is effective for data sets containing noises.

The corresponding training time is also listed in Table 4. It can be found that:

The training time between DAG-SVM and OVO-SVM is roughly the same. The training time between DAG-F-NPSVM, DAG-NPSVM, OVO-NPSVM and OVO-F-NPSVM is also similar. This shows that DAG strategy and OVO strategy both use pairwise classification approach in the training phase.

When comparing the training time of DAG-NPSVM and DAG-SVM, OVO-NPSVM and OVO-SVM, it can be seen that the training time of DAG-NPSVM is about a quarter of that of DAG-SVM. Similarly, the training time of OVO-NPSVM is about a quarter of the time of OVO-SVM. This is because the two-classifier NPSVM solves two smaller convex QPPs, while SVM solves a large convex QPP. In theory, the training time of NPSVM is a quarter of SVM.

Although DAG-F-NPSVM is an improvement of DAG-NPSVM, and OVO-F-NPSVM is also an improvement of OVO-NPSVM, their training time does not increase due to the increase of fuzzy membership, which is added before training. It can be shown that adding fuzzy membership in DAG-NPSVM and OVO-NPSVM, respectively, not only improves the classification accuracy to a certain extent, but also does not change the computational complexity of the model.

Table 4 lists the test times of ten data sets under six classifiers. From the Table, we can see that the test times of DAG-NPSVM and DAG-F-NPSVM are almost the same. The average test time of DAG-F-NPSVM is 50.42% less than that of OVO-F-NPSVM, which shows the absolute advantage of DAG in the test phase. Because under the DAG strategy, the classification results can be obtained without accessing all the classifiers, which fully reflects its advantages in the testing phase.

4.4 Statistical test

In order to further analyze the performance of the six algorithms, Friedman test [35] and Bonferroni-Dunn test [35] are used to test if there is a significant difference between the experimental results.

4.4.1 Friedman test

Friedman test is proved to be a simple non- parametric statistic method. To compute the Friedman statistic, the average ranking based on classification accuracy in Table 3 is listed in Table 5. Under the null hypothesis that all the algorithms are equivalent, the Friedman statistic can be computed as follows:

Table 5
Average ranking based on classification accuracy in Table 3

Data set OVO-SVM DAG-SVM OVO-NPSVM OVO-F-NPSVM DAG-NPSVM DAG-F-NPSVM

Soybean 3.5 3.5 3.5 3.5 3.5 3.5

Zoo 6 5 4 2 3 1

Iris 5.5 5.5 3.5 1.5 3.5 1.5

Wine 5 4 2.5 2.5 2.5 2.5

Seeds 5 6 3 1 4 2

Glass 5.5 5.5 3 1 4 2

E coli 5 6 4 2 3 1

Dermatology 6 5 4 2 3 1

Vowel 6 5 4 2 3 1

Yeast 6 5 4 2 3 1

Average rank 5.35 5.05 3.55 1.95 3.25 1.65

Data set	OVO-SVM	DAG-SVM	OVO-NPSVM	OVO-F-NPSVM	DAG-NPSVM	DAG-F-NPSVM
Soybean	3.5	3.5	3.5	3.5	3.5	3.5
Zoo	6	5	4	2	3	1
Iris	5.5	5.5	3.5	1.5	3.5	1.5
Wine	5	4	2.5	2.5	2.5	2.5
Seeds	5	6	3	1	4	2
Glass	5.5	5.5	3	1	4	2
E coli	5	6	4	2	3	1
Dermatology	6	5	4	2	3	1
Vowel	6	5	4	2	3	1
Yeast	6	5	4	2	3	1
Average rank	5.35	5.05	3.55	1.95	3.25	1.65

$χ_{F}^{2} = \frac{12 N}{M (M + 1)} [\sum_{j} R_{j}^{2} - \frac{M (M + 1)^{2}}{4}],$ (48) where $R_{j} = \frac{1}{N} \sum_{i} r_{i}^{j}$ and $r_{i}^{j}$ denotes the j_th of M algorithms on the i_th of N datasets. Here M = 6 and N = 10. Then a more desirable statistic is derived: $F_{F} = \frac{(N - 1) χ_{F}^{2}}{N (M - 1) - χ_{F}^{2}},$ (49) which is distributed according to the F-distribution with M-1 and (M-1) (N-1) degrees of freedom.

According to (48) and (49), for the nonlinear case, we can obtain $χ_{F}^{2} = 29 . 4714$ and F_F = 12.9207, according to F-distribution with (5, 45) degrees of freedom. As can be seen from the Table of critical values for F-distribution, the critical value of F (5,45) is about 2.90, 2.45 and 2.00 for the significance level _F = 0.025, _F = 0.05, and _F = 0.1, respectively. Since the real value of F_F is much larger than the critical values, the null hypothesis which is all algorithms are performing equivalently is clearly rejected.

4.4.2 Bonferroni-dunn test

Now, Bonferroni–Dunn test can be used to further analyze the relative performance among the comparing algorithms. Here, the difference between the average ranks of DAG-F-NPSVM and one baseline is compared with the following critical difference (CD): $CD = q_{α} \sqrt{\frac{M (M + 1)}{6 N}}$ (50)

We have q_α = 2 . 326 at significance level α = 0.1, and thus CD = 1.95 (M = 6, N = 10). To visually show the relative performance of DAG-F-NPSVM comparing with other algorithms, Fig. 4 provides the CD diagram, among them the average ranks of each comparing algorithm are plotted along the axis. The lowest (best) rank on the axis is to the right since we perceive the algorithms on the right side as better. And any comparing algorithm with the average rank within one CD is interconnected with DAG-F-NPSVM. Otherwise, any other algorithm whose average rank is one CD outside DAG-F-NPSVM is considered to have significantly different performance with DAG-F-NPSVM. As shown in Fig. 4, the average ranks of OVO-SVM (5.35-1.65 = 3.7 > 1.95), DAG-SVM (5.05-1.65 = 3.4 > 1.95) are both one CD outside DAG-F-NPSVM, while the average rank of OVO-NPSVM (3.55-1.65 = 1.9 < 1.95) and DAG-NPSVM (3.25-1.65 = 1.6 < 1.95) are less than but close to one CD. Although The average ranks of OVO-F-NPSVM (1.95-1.65 = 0.3 < 1.95) is less than to one CD. This is because compared with this classifier, the new classifier in this paper has a significant advantage in decision-making speed rather than classification accuracy.

Fig. 4

Comparison of the DAG-F-NPSVM against other five comparing algorithms with the Bonferroni–Dunn test.

The results show that DAG-F-NPSVM is statistically significantly better than OVO-SVM and DAG-SVM. Although the DAG-F-NPSVM is not statistically superior to OVO-NPSVM, DAG-NPSVM and OVP-F-NPSVM, however, compared to the three methods in Table 5, DAG-F-NPSVM can obtain better accuracy on most data sets. This shows that DAG-F-NPSVM has better generalization ability.

5 Conclusion

NPSVM is widely used as an important binary classifier for solving classification problems. Moreover, it can be extended to solve multiple classification problems. But the problems of sample noises, unrecognized regions and low decision speed affect its performance. To improve the situation, DAG-F-NPSVM model is established in this paper. This new method proposes improvements in two aspects. Firstly, as the sample noises in the data set affect the determination of the optimal hyperplane, fuzzy membership degree is added based on sample density. In this way, different samples play different roles in determining the optimal hyperplane. Secondly, DAG theory is introduced to solve the problem of unrecognizable regions and speed up the decision-making speed of the model. The experimental results on UCI benchmark data sets show that DAG-F-NPSVM is superior to several other multi-class support vector machines in terms of classification accuracy and decision speed.

Although DAG-F-NPSVM has the above advantages, there are also some disadvantages that need to be improved. First of all, the DAG strategy classification algorithm has the phenomenon of error accumulation in the classification process. How to overcome this influence needs further research. Secondly, it is necessary to optimize the additional parameters when adding fuzzy membership degree to the samples. Although the grid search method can search for ideal parameters, this work requires a certain amount of calculation time. In other words, the improvement of classification accuracy comes at the cost of parameter optimization time. Therefore, how to quickly and effectively select the best parameter is a problem for further study.

Footnotes

Acknowledgments

This work was supported by the National Natural Science Foundation of China (NO. 71771028), Beijing Intelligent Logistics System Collaborative Innovation Center and Major scientific research project of Beijing WUZI university (NO. 2019XJZD06)

References

Vapnik

V.N.

, The Nature of Statistical Learning Theory, Springer, (1995).

Cortes

and Vapnik

V.N.

, Support-Vector Networks, Machine Learning 20(3) (1995), 273–297. DOI: 10.10 23/A:10226274 11411

Izonin

, Trostianchyn

, Duriagina

, Tkachenko

, Tepla

and Lotoshynska

, The Combined Use of the Wiener Polynomial and SVM for Material Classification Task in Medical Implants Production, International Journal of Intelligent Systems and Applications(IJISA) 10(9) (2018), 40–478. DOI: 10.5815/ijisa.2018.09.05

Suykens

J.A.K.

and Vandewalle

, Least Squares Support Vector Machine Classifiers, Neural Processing Letters 9 (1999), 293–300. DOI: 10.1023/A: 101862 8609742

Wang

, Yu

, Zhu

and Jiang

, A Robust Decoupling Control Method Based on Artificial Bee Colony-Multiple Least Squares Support Vector Machine Inversion for Marine Alkaline Protease MP Fermentation Process, in, IEEE Access 7 (2019), 32206–32216. DOI: 10.1109/ACCESS.2019.2903542

Yin

, Jiang

, Tian

and Kaynak

, A Data-Driven Fuzzy Information Granulation Approach for Freight Volume Forecasting, IEEE Transactions on Industrial Electronics 64(2) (2017), 1447–1456. DOI: 10.1109/TIE.2016.2613974

Scholkopf

, Smola

A.J.

, Williamson

R.C.

and Bartlett

P.L.

, New support vector algorithms, Neural Computaion 12(5) (2000), 1207–1245. DOI: 10.1162/0 89976600300015565

and Law

, An intelligent forecasting model based on robust wavelet ν-support vector machine, Expert Systems with Applications 38(5) (2011), 4851–4859. DOI: 10.1016/j.eswa.2010.09.036

Bazikar

, Ketabchi

and Moosaei

, DC programming and DCA for parametric-margin ν-support vector machine, Appl Intell 50 (2020), 1763–1774. DOI: 10.1007/s10489-01901618-x

10.

Mangasarian

O.L.

and Wild

E.W.

, Multisurface Proximal Support Vector Machine Classification via Generalized Eigenvalues, IEEE Transactions on Pattern Analysis & Machine Intelligence 28(1) (2006), 69–74. DOI: 10.1109/TPA MI.2006.17

11.

Chen

, Yang

, Shao

, Chen

, Ju , & Zhang

and Jing

, A Trace Lasso Regularized Robust Nonparallel Proximal Support Vector Machine for Noisy Classification, IEEE Access (2019), 1–1. DOI:10.1109/ACCESS.2019.2893531

12.

, Ren

, Shao

, Ye

and Guo

, Generalized elastic net Lp-norm nonparallel support vector machine, Engineering Applications of Artificial Intelligence 88 (2020). DIO: 10.1016/j.engappai.2019.103397

13.

Jayadeva

R.K.

and Chandra

, Twin support vector machines for pattern classification, IEEE Trans Pattern Anal Mach Intell. IEEE Transactions on Pattern Analysis and Machine Intelligence 29(5) (2007), 905–910. DOI: 10.1109/TPAMI.2007.1068

14.

Xie

and Xu

, An efficient regularized K-nearest neighbor structural twin support vector machine, Appl Intell 49 (2019), 4258–4275. DOI: 10.1007/s10489-019-01505-5

15.

Lima

M.D.D.

, Lima

J.D.O.R.E.

and Barbosa

R.M.

, Medical data set classification using a new feature selection algorithm combined with twin-bounded support vector machine, Med Biol Eng Comput 58 (2020), 519–528. DOI: 10.1007/s11517-019-02100-z

16.

Tian

, Qi

, Ju

, Shi

and Liu

, Nonparallel Support Vector Machines for Pattern Classification, IEEE Transactions on Cybernetics 44(7) (2014), 1067–1079. DOI: 10.1109/TCYB.2013.2279 167

17.

Tian

, Zhang

and Liu

, ν -Nonparallel support vector machine for pattern classification, Neural Comput and Applic 25(5) (2014), 1007–1020. DOI: 10.10 07 /s00521-014-1575-3

18.

Liu

, Shi

and Tian

, Ramp loss nonparallel support vector machine for pattern classification, Knowledge-Based Systems 85 (2015), 224–233. DOI: 10.1016/j.knosys.2015. 05.008

19.

Bai

and Liu

, Improved Non-parallel Hyperplanes Support Vector Machines for Multi-class Classification, 2018 IEEE 23rd International Conference on Digital Signal Processing (DSP), Shanghai, China, (2018), 1–5. DOI:10.1109/ICDSP.201 8.8631672.

20.

Hou

, Liu

, Zhen

and Jing

, A novel projection nonparallel support vector machine for pattern classification, Engineering Applications of Artificial Intelligence 75 (2018), 64–75. DOI: 10.1016/j.enga ppai.2018.08.003

21.

López

, Maldonado

and Carrasco

, Robust Non-parallel Support Vector Machines via Second-Order Cone Programming, Neurocomputing (2019), 227–238. DOI: 10.1016/j.neucom.2019.07.072

22.

Liu

, Gong

, Chu

and Peng

, Nonparallel support vector machine with large margin distribution for pattern classification, Pattern Recognition 106 (2020), 107374–10.1016/j.patcog.2020.107374

23.

Hsu

and Lin

, A comparison of methods for multiclass support vector machines, IEEE Transactions on Neural Networks 13(2) (2002), 415–425. DOI: 10.1109/72.991427.

24.

Kreβel

, Pairwise classification and support vector machines, Advances in Kernel Methods: Support Vector Learning (1999), 255–268.

25.

Liu

, Bi

and Fan

, A method for multi-class sentiment classification based on an improved one-vs-one (OVO) strategy and the support vector machine (SVM) algorithm, Information Sciences 394 (2017), 38–52. DOI: 10. 1016/j.ins. 2017.02.016

26.

Galar

, Fernández

, Barrenechea

and Herrera

, DRCW-OVO: distance-based relative competence weighting combination for one-vs-one strategy in multi-class problems, Pattern Recogn 48(1) (2015), 28–42. DOI: 10.1016/j.patcog.20 14.07.023

27.

Zhang

, Ding

and Sun

, Multi-class LSTMSVM based on optimal directed acyclic graph and shuffled frog leaping algorithm, International Journal of Machine Learning and Cybernetics 7(2) (2016), 241–251. DOI: 10.1007/s13042-015-0435-5

28.

, Bie

, Feng

and Tian

, Multiclass SVM active learning algorithm based on decision directed acyclic graph and one versus on, Cluster Comput 22 (2019), 6241–6251. DOI: 10.1007/ s10586-018-19 51-3

29.

Lin

and Wang

, Fuzzy support vector machines with automatic membership setting, Studies in Fuzziness and Soft Computing 177 (2005), 233–254. DOI: 10. 1007/10984697_11

30.

Lin

and Wang

, Fuzzy support vector machines, IEEE Transactions on Neural Networks 3(2) (2002), 464–471. DOI: 10.1109/72.991432

31.

, Shen

and Zhang

, Fuzzy multiclass support vector machines for unbalanced data, 2017 29th Chinese Control And Decision Conference (CCDC), Chongqing, (2017), 2227–2231. DOI: 10.1109/CCDC.2017.7978885.

32.

, Hou

and Jing

, Fuzzy and interval-valued fuzzy nonparallel support vector machine, Journal of Intelligent and Fuzzy Systems 36(3) (2019), 2677–2690. DOI: 10.3233/JIFS-18702

33.

Drud

A.S.

and Lasdon

, Nonlinear Programming. In: Gal T., Greenberg H.J. (eds) Advances in Sensitivity Analysis and Parametic Programming. International Series in Operations Research & Management Science 6. Springer, Boston, MA, (1997). DOI: 10.1007/978-1-4615-6103-3_10.

34.

Blake

C.L.

and Merz

C.J.

, UCI repository for machine learning databases. Department of Information and Computer Science, University of California, Irvine (Online). (1998), https://archive.ics.uci.edu/ml/index.php.

35.

Janez

and Dale

, Statistical Comparisons of Classifiers over Multiple Data Sets, Journal of Machine Learning Research 7(1) (2006), 1–30. DOI: 10.1007/s10846-005-9016-2

Directed acyclic graph fuzzy nonparallel support vector machine

Abstract

Keywords

1 Introduction

3.1 Fuzzy membership based on sample density

3.2.1 Linear DAG-F-NPSVM

4 Numerical experiment and analysis

4.1 Experimental environment and data

Table 2 Basic data set description Data sets Number of samples Feature dimension Number of classes Iris 150 4 3 Wine 178 13 3 Seeds 210 7 3 Soybean 47 35 4 E coli 327 7 5 Glass 214 9 6 Vowel 871 3 6 Dermatology 358 34 6 Zoo 101 16 7 Yeast 1484 8 10

4.4 Statistical test

4.4.1 Friedman test

Footnotes

Acknowledgments

References

Table 2
Basic data set description

Data sets Number of samples Feature dimension Number of classes

Iris 150 4 3

Wine 178 13 3

Seeds 210 7 3

Soybean 47 35 4

E coli 327 7 5

Glass 214 9 6

Vowel 871 3 6

Dermatology 358 34 6

Zoo 101 16 7

Yeast 1484 8 10