# PMSVM: An Optimized Support Vector Machine Classification Algorithm Based on PCA and Multilevel Grid Search Methods

Authors: Yukai Yao; Hongmei Cui; Yang Liu; Longjie Li; Long Zhang; Xiaoyun Chen
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

We propose an optimized Support Vector Machine classifier, named PMSVM, in which System Normalization, PCA, and Multilevel Grid Search methods are comprehensively considered for data preprocessing and parameters optimization, respectively. The main goals of this study are to improve the classification efficiency and accuracy of SVM. Sensitivity, Specificity, Precision, and ROC curve, and so forth, are adopted to appraise the performances of PMSVM. Experimental results show that PMSVM has relatively better accuracy and remarkable higher efficiency compared with traditional SVM algorithms.


---

## Body

## 1. Introduction

The swift development of machine learning technologies gives us a good chance to process and analyse data in a brand-new perspective. Machine learning, also known as knowledge discovery, is one of the most important branches of computer science, which aims to find useful patterns from data and is quite different from those traditional statistical methods. As a comparatively new machine learning algorithm, Support Vector Machine (SVM) has attracted much attentions recently and has been successfully used in various application vocations [1–6]. In this study, we focus on constructing an optimized SVM model, so as to use it on heart disease data classification, aiming to improve the classification efficiency and accuracy of SVM.Many literatures have involved contents of using Support Vector Machine to deal with data. Muthu Rama Krishnan et al. designed a SVM based classifier, which was used on two UCI mammogram datasets for breast cancer detection and reached the accuracy of 99.385% and 93.726%, respectively [7]. Xie and Wang integrated a hybrid feature selection method with SVM for erythematosquamous disease diagnosis, which reached the accuracy of 98.61% [8].Feature selection is the basis of machine learning algorithms; appropriate feature selection strategy can obviously improve the performances of machine learning methods. Deisy et al. proposed a novel information theory based feature selection algorithm to improve the classification accuracy for SVM classifiers [9–12]. Other feature selection methods such as mutual information measurement [13], kernel F-score feature selection, and explicit margin-based feature elimination method are often adopted to get better classification results for SVM or other machine learning algorithms [14–17].Most of the machine learning algorithms have their parameters; proper measures should be taken to decide the optimized values of them. Genetic Algorithm, Particle Swarm Optimization Algorithm, Artificial Immune System Algorithm and Grid Search Method are those most often used parameter optimization algorithms [18–23]. Generally, data feature selection methods and parameter optimization strategies are comprehensively considered. Lin et al. developed a Simulated Annealing approach for parameter determination and feature selection in SVM, and experiments showed the good performance of it [24]. Tan et al. proposed a new hybrid approach, in which Genetic Algorithm and Support Vector Machine are integrated effectively based on a wrapper strategy [25], which performed well on the UCI chromosome dataset. Literature [26] presented a hybrid approach based on feature selection, fuzzy weighted preprocessing, and artificial immune recognition system, which was used on the UCI heart disease and hepatitis disease datasets, and the obtained accuracies are 92.39% and 81.82%, respectively.Besides feature selection and parameter optimization, kernel function is another factor that should be considered for kernel based machine learning algorithms like SVM. Khemchandani et al. adopted an optimal kernel selection technique in Twin Support Vector Machines; the efficiency of it was testified with some UCI machine learning benchmark datasets [12, 27]. Abibullaev et al. introduced a linear programming SVM with multikernel function for brain signal data classification and got a good performance [15, 28–30].Artificial Neural Network [23], Extreme Learning Machine [31], K-Nearest Neighbor analysis, Fuzzy Logic based methods [32–34], Ensemble Learning algorithms [34–39], and so forth, are often used or hybridly used to finish data classification tasks and usually can get good classification results. As a new version of Support Vector Machine, Least Square SVM involves equality constraints instead of inequality constraints and works with a least squares cost function. An obvious drawback of the Least Square SVM is that the sparseness is lost [22, 40, 41]. Yang et al. developed an adaptive pruning algorithm based on the bottom-to-top strategy, in which the incremental and decremental learning procedures were used and solved the drawback of traditional Least Square SVM [42–45].Through the investigation of existing literatures, we noticed that the main points of studies using Support Vector Machine for classification are modifying and utilizing typical classification algorithms in combination and trying to acquire better classification performance. In general, the main process includes three procedures: (1) Data Preprocessing (feature selection, normalization, dimension reduction, etc.); (2) Constructing Optimized Classification Models (including parameter optimization); (3) Classification Accuracy and Efficiency Demonstration.Although lots of efforts have been made on SVM and its applications, the performance of it is undesirable and still needs to be optimized.The remaining parts of this paper are arranged as follows: The Mathematical Derivation of Support Vector Machine part shows the mathematical nature of SVM; the part Process of Principal Component Analysis gives the detail of Principal Component Analysis; the proposed System Normalization, Stratified Cross Validation, and Multilevel Grid Search based SVM algorithm are described in the Proposed Methods part; corresponding experiments are shown in the Experimental Results part; the following part gives the conclusions of this study.


## 2. Mathematical Derivation of Support Vector Machine

Support Vector Machine (SVM), as one of the most effective machine learning algorithms used for classification or regression problems, was firstly proposed by Vapnik and his Colleagues in 1995 and its history can be backtracked to the basic works of the Statistical Learning Theory since the 1960s [1–4]. SVM is good at processing nonlinear, high dimension, and little sample machine learning problems.SVM is built on the basis of the VC Dimension (Vapnik Chervonenkis Dimension) Theory and the Structural Risk Minimum Theory, which are the core contents of the Statistical Learning Theory [2]. SVM has both solid theoretical foundation and ideal generation ability [6]. Presently, SVM has been used in many domains and occasions, such as handwriting recognition, biological character recognition (e.g., face recognition), credit card cheat checking, image segmentation, bioinformatics, function fitting, and medical data analysis [6].As has been mentioned, SVM can be used to solve classification and regression problems, and SVM in these two different occasions are called SVC and SVR, respectively. In this paper, only SVC is involved, and it is uniformly referred to as “SVM.” Intuitively (e.g., in 2-dimensional space), the classification problems can be divided into Linearly Separable tasks (corresponding data is made of linearly separable samples) and Linearly Inseparable tasks (data is formed with linearly inseparable samples, also called nonlinearly separable data, or nonlinear data, for short.). Figure1 shows these two cases. Such situations can be extended into high dimensional space.Linear separable data and nonlinear separable data.


### 2.1. Linearly Separable Case

For the sake of simplicity, we only consider two-class classification situations.Given a datasetD, D
=
{
(
x
i
,
y
i
)
}
i
=
1
n, where x
i
∈
R
d, y
i
∈
{
-
1,1
}. Essentially, dataset D is a set of binary group (
x
i
,
y
i
); here x
i
=
{
x
i
1
,
x
i
2
,
…
,
x
i
d
} stands for a data sample, and y
i
=
±
1 is the corresponding class label of x
i. Particularly, we use X to represent arbitrary data sample, and its corresponding class label is represented with Y. In such situations, SVM searches for the hyperplane with the largest separation “Margin” [1–4], that is, the Maximum Marginal Hyperplane (MMH). A separating hyperplane can be written as
(1)
W
·
X
+
b
=
0
,
where W
=
{
w
1
,
w
2
,
…
,
w
d
} is weight vector; b is called as bias. Let q
(
X
)
=
W
·
X
+
b, the geometrical distance from a sample X to the optimal hyperplane can be expressed as
(2)
r
=
q
(
X
)
W
;
here, q
(
X
) is referred to as discriminant function. The purpose of SVM is to find the parameters W and b, so as to maximize the margin of separation (δ in (5)). Without loss of generality, the function margin can be fixed to be equal to 1. Thus, given a training set {
(
x
i
,
y
i
)
}
i
=
1
n
∈
R
d
×
{
±
1
}, we get
(3)
W
·
x
i
≥
+
1
,
∀
y
i
=
+
1
,
W
·
x
i
≤
-
1
,
∀
y
i
=
-
1
.
The particular samples (
x
i
)
s satisfy the equalities of (3) which are referred to as Support Vectors; that is, they are exactly the closest samples to the optimal separating hyperplane. Accordingly, the geometrical distance from the Support Vector x
* to the optimal separating hyperplane is
(4)
r
*
=
q
(
x
*
)
W
=
1
W
,
∀
y
*
=
+
1
,
-
1
W
,
∀
y
*
=
-
1
.Obviously, the margin of separationδ is
(5)
δ
=
2
r
*
=
2
W
.To get the maximum margin hyperplane is to maximizeδ with respect to W and b. 								(6)
max
⁡
W
,
b
2
W
s
.
t
.
y
i
W
x
i
+
b
≥
1
,
i
=
1,2
,
…
,
n
.Equivalently,(7)
min
⁡
W
,
b
1
2
W
2
s
.
t
.
y
i
(
W
x
i
+
b
)
≥
1
,
i
=
1,2
,
…
,
n
.The constrained optimization problem in (7) is known as the Primal Problem. Through the method of Lagrange Multiplier, we construct the following Lagrange Function:
(8)
L
W
,
b
,
α
=
1
2
W
T
W
-
∑
i
=
1
n
‍
α
i
y
i
W
x
i
+
b
-
1
,
where α
i is the Lagrange Multiplier with respect to the i
th inequality. We can get the following conditions of optimality, through differentiating L
(
W
,
b
,
α
) with respect to W and b and setting the results equal to 0:
(9)
∂
L
(
W
,
b
,
α
)
∂
W
=
0
,
∂
L
(
W
,
b
,
α
)
∂
b
=
0
;
thus, we obtain
(10)
W
=
∑
i
=
1
n
α
i
y
i
x
i
,
∑
i
=
1
n
α
i
y
i
=
0
.
The corresponding Dual Problem can be inferred by means of substituting (10) into (8):
(11)
max
⁡
α
W
(
α
)
=
∑
i
=
1
n
‍
α
i
-
1
2
∑
i
=
1
n
‍
∑
j
=
1
n
α
i
α
j
y
i
y
j
x
i
T
x
j
s
.
t
.
∑
i
=
1
n
α
i
y
i
=
0
vvvvv
α
i
≥
0
,
i
=
1,2
,
…
,
n
.The following equation (12) gives the Karush-Kuhn-Tucker (KKT) complementary condition:
(12)
α
i
y
i
W
x
i
+
b
-
1
=
0
,
i
=
1,2
,
…
,
n
.As a result of it, only the support vectors(
x
i
,
y
i
) (the closest samples to the optimal separating hyperplane, which determine the maximal margin) correspond to the nonzero α
i
s (all the other α
i
s equal to zero); (11), which describes the Dual Problem, is a typical Convex Quadratic Programming Optimization Problem. In most cases, the Convex Quadratic Programming Optimization Problem function can efficiently converge to the global optimum, by means of adopting some appropriate optimization techniques. We can acquire the optimal weight vector W
* with (13) after determining the optimal Lagrange multipliers α
i
*:
(13)
W
*
=
∑
i
=
1
n
α
*
y
i
x
i
;
therefore, the corresponding optimal bias b
* can be expressed as follows:
(14)
b
*
=
1
-
W
*
x
s
,
for
y
s
=
+
1
.


### 2.2. Linearly Inseparable Cases

#### 2.2.1. Soft Margin SVM

Soft margin SVM aims to extend the Maximal Separating Margin SVM (so-called, hard margin SVM), so that the hyperplane allows a few of noisy data to exist. On this occasion, a variableξ
i, named Slack factor, is introduced to account for the amount of a violation of classification of the classifier. Classification problem in such cases can be described as
(15)
W
x
i
+
b
≥
1
-
ξ
i
,
∀
y
i
=
+
1
,
W
x
i
+
b
≤
-
1
+
ξ
i
,
∀
y
i
=
-
1
;
that is,
(16)
y
i
W
x
i
+
b
≥
1
-
ξ
i
,
i
=
1,2
,
…
,
n
.The Primal Problem can be described as(17)
min
⁡
W
,
b
1
2
W
2
+
C
∑
i
=
1
n
ξ
i
s
.
t
.
y
i
(
W
x
i
+
b
)
≥
1
-
ξ
i
,
vvvvv
ξ
i
≥
0
,
i
=
1,2
,
…
,
n
.
The corresponding Dual Problem Function (Dual Function) of the soft margin is formulated as
(18)
max
⁡
α
W
(
α
)
=
∑
i
=
1
n
‍
α
i
-
1
2
∑
i
=
1
n
‍
∑
j
=
1
n
α
i
α
j
y
i
y
j
x
i
T
x
j
s
.
t
.
∑
i
=
1
n
α
i
y
i
=
0
vvvvv
0
≤
α
i
≤
C
,
i
=
1,2
,
…
,
n
.KKT complementary condition in such inseparable case is(19)
α
i
y
i
W
x
i
+
b
-
1
+
ξ
i
=
0
,
i
=
1,2
,
…
,
n
,
(20)
β
i
ξ
i
=
0
,
i
=
1,2
,
…
,
n
,
where β
i’s are the Lagrange Multipliers corresponding to ξ
i that have been introduced to enforce the nonnegativity of ξ
i. At the point (saddle point), at which the derivative of the Lagrange function for the primal problem with respect to ξ
i is zero, the evaluation of the derivative yields
(21)
α
i
+
β
i
=
C
.Simultaneously considering (20) and (21), we acquire
(22)
ξ
i
=
0
if
α
i
<
C
.Consequently, the optimal weightW
* can be expressed as follows:
(23)
W
*
=
∑
i
=
1
n
α
i
*
y
i
x
i
.The optimal biasb
* can be obtained by means of taking any sample (x
i
,
y
i) in the training set, for which we have 0
<
α
i
*
<
C and the corresponding ξ
i
=
0, and using the sample in (19)(24)
b
*
=
1
-
ξ
i
-
∑
s
v
α
i
*
y
i
x
i
x
s
,
∀
y
s
=
+
1
.


#### 2.2.2. Kernel Trick Based SVM

For linearly inseparable cases, kernel trick is another commonly used technique. An appropriate kernel function, which is based on the inner product between the given samples, is to be defined as a nonlinear transformation of samples from the original space to a feature space with higher or even infinite dimension so as to make the problems linearly separable. That is, a complicated classification problem cast in a high-dimensional space nonlinearly is more likely to be linearly separable than in a low-dimensional space. Actually, we can adopt a nonlinear mapping function(25)
Φ
:
X
⟶
ϕ
X
,
R
d
⟶
F
to map data X in original (or primal) space into a higher (ever infinite) dimension space F, such that the mapped data in new feature space is more likely linearly separable. Thus we can extend the separating hyperplane function into the following form:
(26)
W
·
ϕ
x
i
+
b
≥
+
1
∀
y
i
=
+
1
,
W
·
ϕ
x
i
+
b
≤
-
1
∀
y
i
=
-
1
;
that is,
(27)
y
i
W
·
ϕ
x
i
+
b
≥
+
1
,
i
=
1,2
,
…
,
n
.
The separating hyperplane is
(28)
W
·
ϕ
(
X
)
+
b
=
0
.The primal problem in such case is(29)
min
⁡
w
,
b
W
2
2
s
.
t
.
y
i
[
W
·
ϕ
(
x
i
)
+
b
]
≥
+
1
,
i
=
1,2
,
…
,
n
.Using the same mathematical trick in linearly separable SVM, we get the corresponding Dual Function(30)
max
⁡
α
W
(
α
)
=
∑
i
=
1
n
α
i
vvvvvvvvvivv
-
1
2
∑
i
=
1
n
∑
j
=
1
n
α
i
α
j
y
i
y
j
ϕ
(
x
i
)
T
ϕ
(
x
j
)
s
.
t
.
∑
i
=
1
n
‍
α
i
y
i
=
0
vvvvv
α
i
≥
0
,
i
=
1,2
,
…
,
n
.The KKT complementary condition is(31)
α
i
y
i
W
ϕ
x
i
+
b
-
1
=
0
,
i
=
1,2
,
…
,
n
.After getting the optimal Lagrange Multipliersα
i
*, we acquire the optimal weight vector and the corresponding bias that are described with function (32) and function (33), respectively:
(32)
W
*
=
∑
i
=
1
n
α
i
*
y
i
ϕ
x
i
,
(33)
b
*
=
1
-
∑
s
v
α
i
*
y
i
ϕ
x
i
ϕ
x
s
,
∀
y
s
=
+
1
.Fortunately, the inner product like the form ofϕ
(
x
i
)
ϕ
(
x
j
) can be instituted with K
(
x
i
,
x
j
), that is,
(34)
K
x
i
,
x
j
=
ϕ
x
i
ϕ
x
j
;
thus, we only need to calculate inner product in the original space not in the feature space, which reduces the calculation complexity obviously; meanwhile, we are refrained from searching for the proper nonlinear mapping function ϕ
(
X
).In fact, the kernel trick cannot always guarantee the mapped problems to be absolutely linearly separable, so soft margin SVM and kernel based SVM are integrated to exert the different advantages of them two and thus can solve the linearly inseparable problems more efficiently. The corresponding Dual form for the constrained optimization problem in the kernel soft margin SVM is listed as follows:(35)
max
⁡
α
W
(
α
)
=
∑
i
=
1
n
α
i
-
1
2
∑
i
=
1
n
∑
j
=
1
n
α
i
α
j
y
i
y
j
K
(
x
i
,
x
j
)
s
.
t
.
∑
i
=
1
n
α
i
y
i
=
0
vvvvv
0
≤
α
i
≤
C
,
i
=
0,1
,
…
,
n
.Accordingly, the optimal classifier is(36)
f
x
=
∑
i
=
1
n
α
i
*
y
i
K
x
i
,
x
+
b
*
,
where
(37)
b
*
=
1
-
∑
i
=
1
n
‍
α
i
*
y
i
K
(
x
i
,
x
s
)
,
∀
y
s
=
+
1
.The most frequently used kernel functions are(i)
K
(
x
,
y
)
=
x
·
y;
(ii)
K
(
x
,
y
)
=
(
x
·
y
+
c
)
h, c
≥
0;
(iii)
K
(
x
,
y
)
=
exp
⁡
{
-
x
-
y
2
/
2
σ
2
};
(iv)
K
x
,
y
=
tanh
(
k
x
·
y
-
δ
), k
>
0.The third one is the RBF kernel function, which is used in our experiments.


## 2.1. Linearly Separable Case

For the sake of simplicity, we only consider two-class classification situations.Given a datasetD, D
=
{
(
x
i
,
y
i
)
}
i
=
1
n, where x
i
∈
R
d, y
i
∈
{
-
1,1
}. Essentially, dataset D is a set of binary group (
x
i
,
y
i
); here x
i
=
{
x
i
1
,
x
i
2
,
…
,
x
i
d
} stands for a data sample, and y
i
=
±
1 is the corresponding class label of x
i. Particularly, we use X to represent arbitrary data sample, and its corresponding class label is represented with Y. In such situations, SVM searches for the hyperplane with the largest separation “Margin” [1–4], that is, the Maximum Marginal Hyperplane (MMH). A separating hyperplane can be written as
(1)
W
·
X
+
b
=
0
,
where W
=
{
w
1
,
w
2
,
…
,
w
d
} is weight vector; b is called as bias. Let q
(
X
)
=
W
·
X
+
b, the geometrical distance from a sample X to the optimal hyperplane can be expressed as
(2)
r
=
q
(
X
)
W
;
here, q
(
X
) is referred to as discriminant function. The purpose of SVM is to find the parameters W and b, so as to maximize the margin of separation (δ in (5)). Without loss of generality, the function margin can be fixed to be equal to 1. Thus, given a training set {
(
x
i
,
y
i
)
}
i
=
1
n
∈
R
d
×
{
±
1
}, we get
(3)
W
·
x
i
≥
+
1
,
∀
y
i
=
+
1
,
W
·
x
i
≤
-
1
,
∀
y
i
=
-
1
.
The particular samples (
x
i
)
s satisfy the equalities of (3) which are referred to as Support Vectors; that is, they are exactly the closest samples to the optimal separating hyperplane. Accordingly, the geometrical distance from the Support Vector x
* to the optimal separating hyperplane is
(4)
r
*
=
q
(
x
*
)
W
=
1
W
,
∀
y
*
=
+
1
,
-
1
W
,
∀
y
*
=
-
1
.Obviously, the margin of separationδ is
(5)
δ
=
2
r
*
=
2
W
.To get the maximum margin hyperplane is to maximizeδ with respect to W and b. 								(6)
max
⁡
W
,
b
2
W
s
.
t
.
y
i
W
x
i
+
b
≥
1
,
i
=
1,2
,
…
,
n
.Equivalently,(7)
min
⁡
W
,
b
1
2
W
2
s
.
t
.
y
i
(
W
x
i
+
b
)
≥
1
,
i
=
1,2
,
…
,
n
.The constrained optimization problem in (7) is known as the Primal Problem. Through the method of Lagrange Multiplier, we construct the following Lagrange Function:
(8)
L
W
,
b
,
α
=
1
2
W
T
W
-
∑
i
=
1
n
‍
α
i
y
i
W
x
i
+
b
-
1
,
where α
i is the Lagrange Multiplier with respect to the i
th inequality. We can get the following conditions of optimality, through differentiating L
(
W
,
b
,
α
) with respect to W and b and setting the results equal to 0:
(9)
∂
L
(
W
,
b
,
α
)
∂
W
=
0
,
∂
L
(
W
,
b
,
α
)
∂
b
=
0
;
thus, we obtain
(10)
W
=
∑
i
=
1
n
α
i
y
i
x
i
,
∑
i
=
1
n
α
i
y
i
=
0
.
The corresponding Dual Problem can be inferred by means of substituting (10) into (8):
(11)
max
⁡
α
W
(
α
)
=
∑
i
=
1
n
‍
α
i
-
1
2
∑
i
=
1
n
‍
∑
j
=
1
n
α
i
α
j
y
i
y
j
x
i
T
x
j
s
.
t
.
∑
i
=
1
n
α
i
y
i
=
0
vvvvv
α
i
≥
0
,
i
=
1,2
,
…
,
n
.The following equation (12) gives the Karush-Kuhn-Tucker (KKT) complementary condition:
(12)
α
i
y
i
W
x
i
+
b
-
1
=
0
,
i
=
1,2
,
…
,
n
.As a result of it, only the support vectors(
x
i
,
y
i
) (the closest samples to the optimal separating hyperplane, which determine the maximal margin) correspond to the nonzero α
i
s (all the other α
i
s equal to zero); (11), which describes the Dual Problem, is a typical Convex Quadratic Programming Optimization Problem. In most cases, the Convex Quadratic Programming Optimization Problem function can efficiently converge to the global optimum, by means of adopting some appropriate optimization techniques. We can acquire the optimal weight vector W
* with (13) after determining the optimal Lagrange multipliers α
i
*:
(13)
W
*
=
∑
i
=
1
n
α
*
y
i
x
i
;
therefore, the corresponding optimal bias b
* can be expressed as follows:
(14)
b
*
=
1
-
W
*
x
s
,
for
y
s
=
+
1
.


## 2.2. Linearly Inseparable Cases

### 2.2.1. Soft Margin SVM

Soft margin SVM aims to extend the Maximal Separating Margin SVM (so-called, hard margin SVM), so that the hyperplane allows a few of noisy data to exist. On this occasion, a variableξ
i, named Slack factor, is introduced to account for the amount of a violation of classification of the classifier. Classification problem in such cases can be described as
(15)
W
x
i
+
b
≥
1
-
ξ
i
,
∀
y
i
=
+
1
,
W
x
i
+
b
≤
-
1
+
ξ
i
,
∀
y
i
=
-
1
;
that is,
(16)
y
i
W
x
i
+
b
≥
1
-
ξ
i
,
i
=
1,2
,
…
,
n
.The Primal Problem can be described as(17)
min
⁡
W
,
b
1
2
W
2
+
C
∑
i
=
1
n
ξ
i
s
.
t
.
y
i
(
W
x
i
+
b
)
≥
1
-
ξ
i
,
vvvvv
ξ
i
≥
0
,
i
=
1,2
,
…
,
n
.
The corresponding Dual Problem Function (Dual Function) of the soft margin is formulated as
(18)
max
⁡
α
W
(
α
)
=
∑
i
=
1
n
‍
α
i
-
1
2
∑
i
=
1
n
‍
∑
j
=
1
n
α
i
α
j
y
i
y
j
x
i
T
x
j
s
.
t
.
∑
i
=
1
n
α
i
y
i
=
0
vvvvv
0
≤
α
i
≤
C
,
i
=
1,2
,
…
,
n
.KKT complementary condition in such inseparable case is(19)
α
i
y
i
W
x
i
+
b
-
1
+
ξ
i
=
0
,
i
=
1,2
,
…
,
n
,
(20)
β
i
ξ
i
=
0
,
i
=
1,2
,
…
,
n
,
where β
i’s are the Lagrange Multipliers corresponding to ξ
i that have been introduced to enforce the nonnegativity of ξ
i. At the point (saddle point), at which the derivative of the Lagrange function for the primal problem with respect to ξ
i is zero, the evaluation of the derivative yields
(21)
α
i
+
β
i
=
C
.Simultaneously considering (20) and (21), we acquire
(22)
ξ
i
=
0
if
α
i
<
C
.Consequently, the optimal weightW
* can be expressed as follows:
(23)
W
*
=
∑
i
=
1
n
α
i
*
y
i
x
i
.The optimal biasb
* can be obtained by means of taking any sample (x
i
,
y
i) in the training set, for which we have 0
<
α
i
*
<
C and the corresponding ξ
i
=
0, and using the sample in (19)(24)
b
*
=
1
-
ξ
i
-
∑
s
v
α
i
*
y
i
x
i
x
s
,
∀
y
s
=
+
1
.


### 2.2.2. Kernel Trick Based SVM

For linearly inseparable cases, kernel trick is another commonly used technique. An appropriate kernel function, which is based on the inner product between the given samples, is to be defined as a nonlinear transformation of samples from the original space to a feature space with higher or even infinite dimension so as to make the problems linearly separable. That is, a complicated classification problem cast in a high-dimensional space nonlinearly is more likely to be linearly separable than in a low-dimensional space. Actually, we can adopt a nonlinear mapping function(25)
Φ
:
X
⟶
ϕ
X
,
R
d
⟶
F
to map data X in original (or primal) space into a higher (ever infinite) dimension space F, such that the mapped data in new feature space is more likely linearly separable. Thus we can extend the separating hyperplane function into the following form:
(26)
W
·
ϕ
x
i
+
b
≥
+
1
∀
y
i
=
+
1
,
W
·
ϕ
x
i
+
b
≤
-
1
∀
y
i
=
-
1
;
that is,
(27)
y
i
W
·
ϕ
x
i
+
b
≥
+
1
,
i
=
1,2
,
…
,
n
.
The separating hyperplane is
(28)
W
·
ϕ
(
X
)
+
b
=
0
.The primal problem in such case is(29)
min
⁡
w
,
b
W
2
2
s
.
t
.
y
i
[
W
·
ϕ
(
x
i
)
+
b
]
≥
+
1
,
i
=
1,2
,
…
,
n
.Using the same mathematical trick in linearly separable SVM, we get the corresponding Dual Function(30)
max
⁡
α
W
(
α
)
=
∑
i
=
1
n
α
i
vvvvvvvvvivv
-
1
2
∑
i
=
1
n
∑
j
=
1
n
α
i
α
j
y
i
y
j
ϕ
(
x
i
)
T
ϕ
(
x
j
)
s
.
t
.
∑
i
=
1
n
‍
α
i
y
i
=
0
vvvvv
α
i
≥
0
,
i
=
1,2
,
…
,
n
.The KKT complementary condition is(31)
α
i
y
i
W
ϕ
x
i
+
b
-
1
=
0
,
i
=
1,2
,
…
,
n
.After getting the optimal Lagrange Multipliersα
i
*, we acquire the optimal weight vector and the corresponding bias that are described with function (32) and function (33), respectively:
(32)
W
*
=
∑
i
=
1
n
α
i
*
y
i
ϕ
x
i
,
(33)
b
*
=
1
-
∑
s
v
α
i
*
y
i
ϕ
x
i
ϕ
x
s
,
∀
y
s
=
+
1
.Fortunately, the inner product like the form ofϕ
(
x
i
)
ϕ
(
x
j
) can be instituted with K
(
x
i
,
x
j
), that is,
(34)
K
x
i
,
x
j
=
ϕ
x
i
ϕ
x
j
;
thus, we only need to calculate inner product in the original space not in the feature space, which reduces the calculation complexity obviously; meanwhile, we are refrained from searching for the proper nonlinear mapping function ϕ
(
X
).In fact, the kernel trick cannot always guarantee the mapped problems to be absolutely linearly separable, so soft margin SVM and kernel based SVM are integrated to exert the different advantages of them two and thus can solve the linearly inseparable problems more efficiently. The corresponding Dual form for the constrained optimization problem in the kernel soft margin SVM is listed as follows:(35)
max
⁡
α
W
(
α
)
=
∑
i
=
1
n
α
i
-
1
2
∑
i
=
1
n
∑
j
=
1
n
α
i
α
j
y
i
y
j
K
(
x
i
,
x
j
)
s
.
t
.
∑
i
=
1
n
α
i
y
i
=
0
vvvvv
0
≤
α
i
≤
C
,
i
=
0,1
,
…
,
n
.Accordingly, the optimal classifier is(36)
f
x
=
∑
i
=
1
n
α
i
*
y
i
K
x
i
,
x
+
b
*
,
where
(37)
b
*
=
1
-
∑
i
=
1
n
‍
α
i
*
y
i
K
(
x
i
,
x
s
)
,
∀
y
s
=
+
1
.The most frequently used kernel functions are(i)
K
(
x
,
y
)
=
x
·
y;
(ii)
K
(
x
,
y
)
=
(
x
·
y
+
c
)
h, c
≥
0;
(iii)
K
(
x
,
y
)
=
exp
⁡
{
-
x
-
y
2
/
2
σ
2
};
(iv)
K
x
,
y
=
tanh
(
k
x
·
y
-
δ
), k
>
0.The third one is the RBF kernel function, which is used in our experiments.


## 2.2.1. Soft Margin SVM

Soft margin SVM aims to extend the Maximal Separating Margin SVM (so-called, hard margin SVM), so that the hyperplane allows a few of noisy data to exist. On this occasion, a variableξ
i, named Slack factor, is introduced to account for the amount of a violation of classification of the classifier. Classification problem in such cases can be described as
(15)
W
x
i
+
b
≥
1
-
ξ
i
,
∀
y
i
=
+
1
,
W
x
i
+
b
≤
-
1
+
ξ
i
,
∀
y
i
=
-
1
;
that is,
(16)
y
i
W
x
i
+
b
≥
1
-
ξ
i
,
i
=
1,2
,
…
,
n
.The Primal Problem can be described as(17)
min
⁡
W
,
b
1
2
W
2
+
C
∑
i
=
1
n
ξ
i
s
.
t
.
y
i
(
W
x
i
+
b
)
≥
1
-
ξ
i
,
vvvvv
ξ
i
≥
0
,
i
=
1,2
,
…
,
n
.
The corresponding Dual Problem Function (Dual Function) of the soft margin is formulated as
(18)
max
⁡
α
W
(
α
)
=
∑
i
=
1
n
‍
α
i
-
1
2
∑
i
=
1
n
‍
∑
j
=
1
n
α
i
α
j
y
i
y
j
x
i
T
x
j
s
.
t
.
∑
i
=
1
n
α
i
y
i
=
0
vvvvv
0
≤
α
i
≤
C
,
i
=
1,2
,
…
,
n
.KKT complementary condition in such inseparable case is(19)
α
i
y
i
W
x
i
+
b
-
1
+
ξ
i
=
0
,
i
=
1,2
,
…
,
n
,
(20)
β
i
ξ
i
=
0
,
i
=
1,2
,
…
,
n
,
where β
i’s are the Lagrange Multipliers corresponding to ξ
i that have been introduced to enforce the nonnegativity of ξ
i. At the point (saddle point), at which the derivative of the Lagrange function for the primal problem with respect to ξ
i is zero, the evaluation of the derivative yields
(21)
α
i
+
β
i
=
C
.Simultaneously considering (20) and (21), we acquire
(22)
ξ
i
=
0
if
α
i
<
C
.Consequently, the optimal weightW
* can be expressed as follows:
(23)
W
*
=
∑
i
=
1
n
α
i
*
y
i
x
i
.The optimal biasb
* can be obtained by means of taking any sample (x
i
,
y
i) in the training set, for which we have 0
<
α
i
*
<
C and the corresponding ξ
i
=
0, and using the sample in (19)(24)
b
*
=
1
-
ξ
i
-
∑
s
v
α
i
*
y
i
x
i
x
s
,
∀
y
s
=
+
1
.


## 2.2.2. Kernel Trick Based SVM

For linearly inseparable cases, kernel trick is another commonly used technique. An appropriate kernel function, which is based on the inner product between the given samples, is to be defined as a nonlinear transformation of samples from the original space to a feature space with higher or even infinite dimension so as to make the problems linearly separable. That is, a complicated classification problem cast in a high-dimensional space nonlinearly is more likely to be linearly separable than in a low-dimensional space. Actually, we can adopt a nonlinear mapping function(25)
Φ
:
X
⟶
ϕ
X
,
R
d
⟶
F
to map data X in original (or primal) space into a higher (ever infinite) dimension space F, such that the mapped data in new feature space is more likely linearly separable. Thus we can extend the separating hyperplane function into the following form:
(26)
W
·
ϕ
x
i
+
b
≥
+
1
∀
y
i
=
+
1
,
W
·
ϕ
x
i
+
b
≤
-
1
∀
y
i
=
-
1
;
that is,
(27)
y
i
W
·
ϕ
x
i
+
b
≥
+
1
,
i
=
1,2
,
…
,
n
.
The separating hyperplane is
(28)
W
·
ϕ
(
X
)
+
b
=
0
.The primal problem in such case is(29)
min
⁡
w
,
b
W
2
2
s
.
t
.
y
i
[
W
·
ϕ
(
x
i
)
+
b
]
≥
+
1
,
i
=
1,2
,
…
,
n
.Using the same mathematical trick in linearly separable SVM, we get the corresponding Dual Function(30)
max
⁡
α
W
(
α
)
=
∑
i
=
1
n
α
i
vvvvvvvvvivv
-
1
2
∑
i
=
1
n
∑
j
=
1
n
α
i
α
j
y
i
y
j
ϕ
(
x
i
)
T
ϕ
(
x
j
)
s
.
t
.
∑
i
=
1
n
‍
α
i
y
i
=
0
vvvvv
α
i
≥
0
,
i
=
1,2
,
…
,
n
.The KKT complementary condition is(31)
α
i
y
i
W
ϕ
x
i
+
b
-
1
=
0
,
i
=
1,2
,
…
,
n
.After getting the optimal Lagrange Multipliersα
i
*, we acquire the optimal weight vector and the corresponding bias that are described with function (32) and function (33), respectively:
(32)
W
*
=
∑
i
=
1
n
α
i
*
y
i
ϕ
x
i
,
(33)
b
*
=
1
-
∑
s
v
α
i
*
y
i
ϕ
x
i
ϕ
x
s
,
∀
y
s
=
+
1
.Fortunately, the inner product like the form ofϕ
(
x
i
)
ϕ
(
x
j
) can be instituted with K
(
x
i
,
x
j
), that is,
(34)
K
x
i
,
x
j
=
ϕ
x
i
ϕ
x
j
;
thus, we only need to calculate inner product in the original space not in the feature space, which reduces the calculation complexity obviously; meanwhile, we are refrained from searching for the proper nonlinear mapping function ϕ
(
X
).In fact, the kernel trick cannot always guarantee the mapped problems to be absolutely linearly separable, so soft margin SVM and kernel based SVM are integrated to exert the different advantages of them two and thus can solve the linearly inseparable problems more efficiently. The corresponding Dual form for the constrained optimization problem in the kernel soft margin SVM is listed as follows:(35)
max
⁡
α
W
(
α
)
=
∑
i
=
1
n
α
i
-
1
2
∑
i
=
1
n
∑
j
=
1
n
α
i
α
j
y
i
y
j
K
(
x
i
,
x
j
)
s
.
t
.
∑
i
=
1
n
α
i
y
i
=
0
vvvvv
0
≤
α
i
≤
C
,
i
=
0,1
,
…
,
n
.Accordingly, the optimal classifier is(36)
f
x
=
∑
i
=
1
n
α
i
*
y
i
K
x
i
,
x
+
b
*
,
where
(37)
b
*
=
1
-
∑
i
=
1
n
‍
α
i
*
y
i
K
(
x
i
,
x
s
)
,
∀
y
s
=
+
1
.The most frequently used kernel functions are(i)
K
(
x
,
y
)
=
x
·
y;
(ii)
K
(
x
,
y
)
=
(
x
·
y
+
c
)
h, c
≥
0;
(iii)
K
(
x
,
y
)
=
exp
⁡
{
-
x
-
y
2
/
2
σ
2
};
(iv)
K
x
,
y
=
tanh
(
k
x
·
y
-
δ
), k
>
0.The third one is the RBF kernel function, which is used in our experiments.


## 3. Process of Principal Component Analysis

Principal Components Analysis (PCA), as was firstly introduced by Pearson in 1901, is a methodology that can be used to reduce the number of explicative variables of a dataset. In this paper, PCA is used for dimension reduction.The main procedure of PCA is introduced as follows.Given a datasetD
′, where D
′
=
{
x
1
,
x
2
,
…
,
x
n
}, x
i
∈
R
d, i
=
1,2
,
…
,
n. Essentially, dataset D
′ is a n
×
d matrix. Firstly, D
′ should be normalized to get matrix with d normalized n dimensional column vectors, in case that attributes with large domains dominate with smaller ones (the following procedures will be exerted on these column vectors). Then, K orthonormal vectors will be calculated to act as a basis for the normalized input data, which are referred to as the principal components. Let Y
1
,
Y
2
,
…
,
Y
K denote these K mutually perpendicular unit vectors; they should satisfy the following requirements:
(38)
COV
(
Y
i
,
Y
j
)
=
0
,
where
i
,
j
∈
{
1,2
,
…
,
K
}
,
i
≠
j
.
Thirdly, these principal components are sorted descendingly according to their “significance.” Finally, those first several components will be chosen to reconstruct a good approximation of the original data. Thus the dimension size of the data is reduced; that is, PCA can be used to reduce data dimension.


## 4. The Proposed Methods

In this paper, we select the Stalog Heart Disease Dataset, which is from the UCI (University of California at Irvine) Machine Learning Repository, as our experimental data. The dataset contains 270 tuples; each tuple includes thirteen data attributes and one class attribute. The detail of the dataset is described with Table1.Table 1
Description of the UCI Stalog Heart Disease Dataset.
Number
Attributes
Full name of attributes
Value types
1
age
Age in years
Real
2
sex
Sex (1 = male; 0 = female)
Binary
3
cp
cp: chest pain type (1 = typical angina; 2 = atypical angina; 3 = nonanginal pain; 4 = asymptomatic)
Nominal
4
trestbps
Resting blood pressure (in mm Hg on admission to the hospital)
Real
5
chol
Serum cholesterol in mg/dL
Real
6
fbs
(Fasting blood sugar>120 mg/dL) (1 = true; 0 = false)
Binary
7
restecg
Resting electrocardiographic results (values 0, 1, 2)
Nominal
8
thalach
Maximum heart rate achieved
Real
9
exang
Exercise induced angina (1 = yes; 0 = no)
Binary
10
oldpeak
ST depression induced by exercise relative to rest
Real
11
slope
The slope of the peak exercise ST segment
Ordered
12
ca
Number of major vessels (0–3) colored by fluoroscopy
Real
13
thal
3 = normal; 6 = fixed defect; 7 = reversible defect
Nominal
14
num
Diagnosis of heart disease (angiographic disease status: 1 = absence; 2 = presence)
BinaryBecause the value ranges of different attributes vary greatly, the tuples in Stalog Heart Disease Dataset are preprocessed as follows. Firstly, to facilitate the following experiments, we change the values of the attribute “class” into 1 and −1, respectively. That is, let 1 represent “presence,” and −1 represent “absence.” Then tuples in the dataset are normalized by column to[
-
1,1
]. In the normalized process, only the front thirteen data attributes are considered. We name such attribute data normalization process as System Normalization. The actual normalization procedure for each column vector C
j, j
=
1,2
,
…
,
d, in Dataset D
′ is illustrated with (39).LetD
(
i
,
j
) represent the i
th element of C
j. 						(39)
D
(
i
,
j
)
=
D
(
i
,
j
)
-
max
⁡
(
C
j
)
+
min
⁡
(
C
j
)
/
2
max
⁡
(
C
j
)
-
min
⁡
(
C
j
)
/
2
vv
∀
i
,
j
,
i
=
1,2
,
…
,
n
;
j
=
1,2
,
…
,
d
.To demonstrate the performance of SVM classifier, we often adopt cross validation method to get the accuracy of the class model. Traditionally, when usingK-fold cross validation, the input dataset is randomly divided into K subsets, so that all the subsets have almost the same number of samples. In the training phase of the classification model, each subset will act as testing subset only once and will act as training subset K
-
1 times. In other words, when using K-fold classification validation, K classification models will be founded, each of them using K
-
1 subsets as training set, and the remaining one subset as testing set. The final classification performance is to be appraised by using the average result of the K classification models.In this paper, the stratified sample technology is adopted to generate theK folds (subsets); thus each subset will have the same number of positive samples and the same number of negative samples; the ratio between positive samples and negative samples of each subset is just the same as that of the whole dataset. That is, the acquired subsets will keep the statistical distribution of the original dataset. Algorithm 1 describes the main process of the Stratified Cross Validation.Algorithm 1:Stratified Cross Validation.
Require:  D
,
K
Ensure:  D
1
,
D
2
,
…
,
D
K
,
A
C
C
a
v
e
r
a
g
e
(1)Calculate the row size (S
r) of dataset D;
(2)Count the number of positive samples (
N
+
) and negative samples (
N
-
), respectively;
(3)
T
1
=
N
+
K;
(4)
T
2
=
N
-
K;
(5)
i
=
1;
(6)
U
=
D;
(7)
for  (
i
<
K
)  do
(8) D
i
=
ϕ;
(9) Sample T
1 positive samples from U;
(10)Sample T
2 negative samples from U;
(11)Add those sampled samples into subset D
i;
(12)
U
=
U
-
D
i;
(13)
i
=
i
+
1;
(14)end  for
(15)D
i
=
U;
(16)i
=
1;
(17)for  (
i
≤
K
)  do
(18)  using subsetD
i as testing set, the remaining K
-
1 subsets as training set;
(19)  using the training set to create classification model of SVM;
(20)  using the testing set to generate the accuracy rateA
C
C
i;
(21)i
=
i
+
1;
(22)end  for
(23)A
C
C
a
v
e
r
a
g
e
=
1
k
∑
i
=
1
K
‍
A
C
C
i
(24)return  the average accuracy rate A
C
C
a
v
e
r
a
g
e;


### 4.1. Multilevel Grid Search

In this paper, we selectC-SVC as our SVM classifier, and the RBF kernel as the kernel function. Thus we need to decide the values of the punishment parameter C of C-SVC and the parameter g of the RBF kernerl function. Generally, Grid Search technique is the most frequently used skill for deciding the optimal value of these two parameters. Given initial value ranges and search steps for the two parameters, respectively, Grid Search algorithm will iteratively check every value pair of C and g to try to obtain the optimal values of the value pair. Different settings of the initial value ranges and the steps for these two parameters will influence greatly the optimum results. Meanwhile, because the Grid Search method is of typical exhaustive search technology, the search process is time consuming.Here, we present an adapted grid search method named Multilevel Grid Search (MGS), which effectively spares the search time and gets the same search result as the traditional grid search process.Algorithm2 reveals the details of our Multilevel Grid Search method.Algorithm 2:Multilevel Grid Search (MGS).
Require:  K
,
X
,
t
h
r
e
s
h
o
l
d
_
A
C
C
Ensure:  B
e
s
t
C
,
B
e
s
t
g
,
A
C
C
(1)INPUT: C
min
⁡
,
C
max
⁡
,
b
i
g
C
s
t
e
p;
(2)INPUT: g
min
⁡
,
g
max
⁡
,
b
i
g
g
s
t
e
p;
(3)GridSearch(T
r
a
i
n
l
a
b
e
l
,
T
r
a
i
n
d
a
t
a
,
C
min
⁡
,
C
max
⁡
,
g
min
⁡
,
g
max
⁡
,
b
i
g
C
s
t
e
p
,
b
i
g
g
s
t
e
p
,
K);
(4)
C
s
t
e
p
=
0.5
,
g
s
t
e
p
=
0.5
(5)
while  A
C
C
≠
t
h
r
e
s
h
o
l
d
_
A
C
C  do
(6) Record the best ACC and the corresponding C, g;
(7) C
mid
=
C
max
⁡
+
C
min
⁡
2
(8) g
mid
=
g
max
⁡
+
g
min
⁡
2
(9) if  C
≥
C
mid  then
(10)C
min
⁡
=
C
mid
(11)else
(12)C
max
⁡
=
C
mid
(13)end if
(14)if  g
≥
g
mid  then
(15)g
min
⁡
=
g
mid
(16)else
(17)g
max
⁡
=
g
mid
(18)end if
(19)  GridSearch(T
r
a
i
n
l
a
b
e
l
,
T
r
a
i
n
d
a
t
a
,
C
min
⁡
,
C
max
⁡
,
g
min
⁡
,
g
max
⁡
,
C
s
t
e
p
,
g
s
t
e
p
,
K);
(20)end while
(21)return  B
e
s
t
C
,
B
e
s
t
g.Figures2 and 3 show the parameters optimization results of the MGS method. Figure 2(a) gives the Grid Search results on S-DATA3; Figure 2(b) demonstrates the Grid Search results on PCA and System Normalization process based S-DATA3; Figures 2(c)-2(d) demonstrate the Multilevel Grid Search process on PCA and System Normalization process based S-DATA3; the situation of Figure 3 is about the same as Figure 2, but its experimental data is R-DATA6.MGS on S-DATA3.
(a)
SVM parameters selection result [GS method]: Bestc
=
22.6274; Best g
=
0.0625; CV Accuracy = 83.3333%
(b)
SVM parameters selection result [GS method]: Bestc
=
11.3137; Best g
=
0.015625; CV Accuracy = 81.6667%
(c)
SVM parameters selection result [MGS method]: Bestc
=
4; Best g
=
0.015625; CV Accuracy = 80.5556%
(d)
SVM parameters selection result [MGS method]: Bestc
=
11.3137; Best g
=
0.015625; CV Accuracy = 81.6667%MGS on R-DATA6.
(a)
SVM parameters selection result [GS method]: Bestc
=
1; Best g
=
0.022097; CV Accuracy = 86.1111%
(b)
SVM parameters selection result [GS method]: Bestc
=
8; Best g
=
0.015625; CV Accuracy = 87.2222%
(c)
SVM parameters selection result [MGS method] Bestc
=
1; Best g
=
0.0625; CV Accuracy = 86.1111%
(d)
SVM parameters selection result [MGS method] Bestc
=
32; Best g
=
0.0039063; CV Accuracy = 87.2222%Figures2(a) and 3(a) show that PCA has little influence on the classification accuracy of SVM, and averagely, experimental results in our study show that when adopting proper PCA threshold, PCA based SVM has similar classification accuracy as traditional SVM algorithms.


## 4.1. Multilevel Grid Search

In this paper, we selectC-SVC as our SVM classifier, and the RBF kernel as the kernel function. Thus we need to decide the values of the punishment parameter C of C-SVC and the parameter g of the RBF kernerl function. Generally, Grid Search technique is the most frequently used skill for deciding the optimal value of these two parameters. Given initial value ranges and search steps for the two parameters, respectively, Grid Search algorithm will iteratively check every value pair of C and g to try to obtain the optimal values of the value pair. Different settings of the initial value ranges and the steps for these two parameters will influence greatly the optimum results. Meanwhile, because the Grid Search method is of typical exhaustive search technology, the search process is time consuming.Here, we present an adapted grid search method named Multilevel Grid Search (MGS), which effectively spares the search time and gets the same search result as the traditional grid search process.Algorithm2 reveals the details of our Multilevel Grid Search method.Algorithm 2:Multilevel Grid Search (MGS).
Require:  K
,
X
,
t
h
r
e
s
h
o
l
d
_
A
C
C
Ensure:  B
e
s
t
C
,
B
e
s
t
g
,
A
C
C
(1)INPUT: C
min
⁡
,
C
max
⁡
,
b
i
g
C
s
t
e
p;
(2)INPUT: g
min
⁡
,
g
max
⁡
,
b
i
g
g
s
t
e
p;
(3)GridSearch(T
r
a
i
n
l
a
b
e
l
,
T
r
a
i
n
d
a
t
a
,
C
min
⁡
,
C
max
⁡
,
g
min
⁡
,
g
max
⁡
,
b
i
g
C
s
t
e
p
,
b
i
g
g
s
t
e
p
,
K);
(4)
C
s
t
e
p
=
0.5
,
g
s
t
e
p
=
0.5
(5)
while  A
C
C
≠
t
h
r
e
s
h
o
l
d
_
A
C
C  do
(6) Record the best ACC and the corresponding C, g;
(7) C
mid
=
C
max
⁡
+
C
min
⁡
2
(8) g
mid
=
g
max
⁡
+
g
min
⁡
2
(9) if  C
≥
C
mid  then
(10)C
min
⁡
=
C
mid
(11)else
(12)C
max
⁡
=
C
mid
(13)end if
(14)if  g
≥
g
mid  then
(15)g
min
⁡
=
g
mid
(16)else
(17)g
max
⁡
=
g
mid
(18)end if
(19)  GridSearch(T
r
a
i
n
l
a
b
e
l
,
T
r
a
i
n
d
a
t
a
,
C
min
⁡
,
C
max
⁡
,
g
min
⁡
,
g
max
⁡
,
C
s
t
e
p
,
g
s
t
e
p
,
K);
(20)end while
(21)return  B
e
s
t
C
,
B
e
s
t
g.Figures2 and 3 show the parameters optimization results of the MGS method. Figure 2(a) gives the Grid Search results on S-DATA3; Figure 2(b) demonstrates the Grid Search results on PCA and System Normalization process based S-DATA3; Figures 2(c)-2(d) demonstrate the Multilevel Grid Search process on PCA and System Normalization process based S-DATA3; the situation of Figure 3 is about the same as Figure 2, but its experimental data is R-DATA6.MGS on S-DATA3.
(a)
SVM parameters selection result [GS method]: Bestc
=
22.6274; Best g
=
0.0625; CV Accuracy = 83.3333%
(b)
SVM parameters selection result [GS method]: Bestc
=
11.3137; Best g
=
0.015625; CV Accuracy = 81.6667%
(c)
SVM parameters selection result [MGS method]: Bestc
=
4; Best g
=
0.015625; CV Accuracy = 80.5556%
(d)
SVM parameters selection result [MGS method]: Bestc
=
11.3137; Best g
=
0.015625; CV Accuracy = 81.6667%MGS on R-DATA6.
(a)
SVM parameters selection result [GS method]: Bestc
=
1; Best g
=
0.022097; CV Accuracy = 86.1111%
(b)
SVM parameters selection result [GS method]: Bestc
=
8; Best g
=
0.015625; CV Accuracy = 87.2222%
(c)
SVM parameters selection result [MGS method] Bestc
=
1; Best g
=
0.0625; CV Accuracy = 86.1111%
(d)
SVM parameters selection result [MGS method] Bestc
=
32; Best g
=
0.0039063; CV Accuracy = 87.2222%Figures2(a) and 3(a) show that PCA has little influence on the classification accuracy of SVM, and averagely, experimental results in our study show that when adopting proper PCA threshold, PCA based SVM has similar classification accuracy as traditional SVM algorithms.


## 5. Experimental Results

In this paper, the UCI Stalog heart-disease dataset is used to test our method. The main purpose of our study is to create a more efficient and available SVM model. The original dataset is processed based on the holdout method; that is, the given data are partitioned into two independent sets, one as training set, the other as test set. Two-thirds of the original data are allocated to the training set; the remaining one-third is allocated to the test data. Firstly, we repeat stratified subsampling based holdout method 10 times to generate 10 stratified datasets S-DATA1,S-DATA
2
,
…
,
S-DATA
10; then, random subsampling based holdout method is repeated 10 times to generate R-DATA1, R-DATA
2
,
…
,
R-DATA
10; in this paper, the experiments are mainly based on S-DATA1, S-DATA
3
,
…
,
S-DATA
9, and R-DATA2, R-DATA
4
,
…
,
R-DATA
10.To study the necessity of our System Normalization process, lots of experiments are done on our datasets, and the results show that System Normalization exerts a great influence on the classification result of SVM; that is, it can effectively advance the classification accuracy of SVM. For simplicity, only part of the results are demonstrated. Figure4 shows the influence of normalization on the classification result using traditional SVM classifier.Roc curve for scaled and unscaled data.SVM is a promising machine learning algorithm, which has solid theory foundation and good generalization ability. But the training time of even the fastest SVMs can be extremely slow. In this paper, PCA is adopted to reduce the dimension of our data. Here, the threshold of PCA is 85%.Figure5 shows the PCA results on the Stalog Herat Disease Dataset. As shown in Figure 5, the System Normalization process has no obvious effect on PCA. Further study shows that, when adopting proper threshold (in this study, it is 85%), PCA has no direct influence on the classification accuracy of SVM. Figure 6 shows the ROC curve of SVM classifier on two different sampled Heart Disease Datasets: one is random sampled and the other is stratified sampled. It is obvious that PCA based SVM has similar classification accuracy as traditional SVM, but it can reduce the time complexity in some extent (about a 25% reduction).PCA results on two different datasets.ROC curve on original data and PCA processed data (5-fold CV).We name the classifier based on PCA and MGS methods as PMSVM, and we call the classifier based on PCA strategy as PLSVM. All experimental results are compared with that of the famous LIBSVM algorithm. To demonstrate the performances of PMSVM, PLSVM with that of LIBSVM, Confusion Matrix, Sensitivity, Specialty, Precision, ROC curve, and AUC are used as the main evaluative criteria for classification accuracy; meanwhile, the time overhead is checked for measuring the efficiency of our method. All SVM algorithms are based onC-SVC classification model and RBF kernel function.Confusion Matrix is a useful tool to a classifier for describing the classification results for different classes. GivenQ classes, the Confusion Matrix is a Q
×
Q matrix, the element C
M
i
,
j describes the number of samples that a classifier classifies class i into class j. For an ideal classifier that has 100
% classification accuracy, all the samples should be described with the elements on the main diagonal of the Confusion Matrix. That is, let D represent the number of total samples of dataset D; we can get the following:
(40)
∑
i
=
1
Q
C
M
i
,
j
=
D
,
i
=
j
.
Table 2 gives an example for a 2-class classifiers, where, Tru
e
Positive represents the number of positive samples that are correctly classified as positive samples; Faus
e
Negative represents the number of positive samples that are wrongly classified as negative samples; Tru
e
Negative represents the number of negative samples that are correctly classified as negative samples; Fals
e
Positive represents the number of negative samples that are wrongly classified as positive samples.Table 2
Confision matrix for 2-class classifiers.
Class
Positive
Negative
Positive
True
Positive
Fause
Negative
Negative
False
Positive
True
NegativeThe following results of Sensitivity, Specialty, Precision, and so forth, closely rely on the contents of Confusion Matrix. LetPos represent the total number of positive samples, and let Neg represent the total number of negative samples; it is easy to get the following relations, which are described as
(41)
Pos
=
Tru
e
Positive
+
Fals
e
Negative
,
Neg
=
Tru
e
Negative
+
Fas
e
Positive
.“Sensitivity” is the ratio betweenTru
e
Positive and Pos. That is, it is the ratio of truly classified positive samples. Sensitivity can be described as
(42)
Sensitivity
=
Tru
e
Positive
Pos
.“Specificity” is the ratio betweenTru
e
Negative and Neg. In another word, it is the ratio of truly sampled negative samples. Specificity can be defined as
(43)
Specificity
=
Tru
e
Negative
Neg
.Precision gives the ratio between the number of truly classified positive samples and the total number of samples that are classified as true samples. Precision can be described as(44)
Precision
=
Tru
e
Positive
Tru
e
Positive
+
Fals
e
Positive
.ROC curve is a useful visual tool for comparing the performances of different classification models. ROC is the abbreviation of Receiver Operating Characteristic. ROC curve displays the comparative performance evaluation between the true positive rate and the false positive rate of a given classifier. Here, AUC means the area under the curve (ROC), and it can express the accuracy of a given classification model. Figure7 demonstrates the ROC curve of of standard LIBSVM on 10 stratified sampled datasets using 5-fold cross validation and 10-fold cross validation methods, respectively. As we can see from the classification results, shown with Figure 7, that there are no obvious differences between the results of 5-fold cross validation method and that of 10-fold cross validation method. So, we will adopt the 5-fold cross validation technology as our default cross validation way in the following experiments, and the cross validation technology we used is referred as Stratified Cross Validation (SCV), as is mentioned in Algorithm 1.Figure 7
5-fold and 10-fold ROC curve on 10 stratified sampled datasets.Figure8 demonstrates the ROC curve of PMSVM, PLSVM, and LIBSVM. Here, both parameters, C and g, of PLSVM and LIBSVM are set to the constant experience value 0.1. As is shown in Figure 8, the classification results of PLSVM and LIBSVM are quite similar; the difference between them is that PLSVM can effectively progress the classification efficiency by 25
% or so, because of the PCA process adopted. Generally, the classification performances of the PMSVM, which is based on our PCA and MGS strategies, have obvious advantages; the classification accuracy is more than that of PLSVM and LIBSVM; meanwhile, the running time of PMSVM is significantly shorter than that of them; that is, the time consuming of our PMSVM has about a reduction of 75% or so than that of traditional LIBSVM.Figure 8
ROC curve of LIBSVM, PLSVM, and PMSVM.Tables3 and 4 show the overall situations between PMSVM and LIBSVM (here, parameters C and g of PMSVM and LIBSVM are acquired through Multilevel Grid Search and Grid Search, resp.). Figure 9 demonstrates the time overhead of PMSVM, PLSVM, and LIBSVM.Table 3
Comparison of the accuracy and efficiency of algorithms on stratified sampled data.
Dataset
Algorithm
Parameters
Time (S)
Accuracy
C
g
Sensitivity
Specificity
Precision
AUC
CVA (%)
S-DATA1
LIBSVM
90.5097
0.011049
19.740543
0.813
0.890
0.856
0.94463
84.4444
PMSVM
2.82840
0.176780
4.6617020
0.838
0.910
0.882
0.97575
84.4444
S-DATA3
LIBSVM
22.6274
0.062500
20.844411
0.813
0.910
0.878
0.93363
83.8889
PMSVM
11.3137
0.015625
4.9883590
0.763
0.870
0.824
0.91788
81.6667
S-DATA5
LIBSVM
0.35355
0.125000
20.070109
0.788
0.880
0.840
0.91075
84.4444
PMSVM
0.50000
0.125000
4.8111860
0.788
0.880
0.840
0.91910
84.4444
S-DATA7
LIBSVM
1.41420
0.353550
20.134157
0.838
0.920
0.893
0.91213
85.0000
PMSVM
8.00000
0.044194
4.7952370
0.880
0.910
0.877
0.92675
85.0000
S-DATA9
LIBSVM
0.17678
0.083880
19.628079
0.800
0.880
0.842
0.92212
85.5556
PMSVM
2.82840
0.250000
4.8249560
0.863
0.920
0.896
0.94350
86.6667Table 4
Comparison of the accuracy and efficiency of algorithms on random sampled datasets.
Dataset
Algorithm
Parameters
Time (S)
Accuracy
C
g
Sensitivity
Specificity
Precision
AUC
CVA (%)
R-DATA2
LIBSVM
0.50000
0.1767800
19.610260
0.805
0.857
0.825
0.90640
82.2222
PMSVM
256.000
0.0039063
5.5637770
0.780
0.857
0.825
0.96925
83.8889
R-DATA4
LIBSVM
1.00000
0.0888388
19.566909
0.842
0.913
0.877
0.94345
87.7778
PMSVM
2.82840
0.0883880
4.1918490
0.842
0.923
0.889
0.95078
87.7778
R-DATA6
LIBSVM
1.00000
0.0220970
19.573738
0.802
0.909
0.878
0.93628
86.1111
PMSVM
8.00000
0.0156250
4.5530740
0.802
0.929
0.903
0.94762
87.2222
R-DATA8
LIBSVM
0.17678
1.0000000
19.871964
0.785
0.911
0.873
0.89034
83.8889
PMSVM
4.00000
0.0312500
5.1134920
0.797
0.861
0.818
0.91580
83.3333
R-DATA10
LIBSVM
0.12500
0.1767800
19.638424
0.750
0.885
0.826
0.89020
84.4444
PMSVM
0.25000
0.0883880
4.8284440
0.763
0.885
0.829
0.89890
83.8889Figure 9
Comparison of time consuming.In the whole experiment, Stratified Sampling and Random Sampling methods show no direct influences on classification results of PMSVM, PLSVM, and LIBSVM, but Stratified Cross Validation provides more reliable results. And the influence of Stratified Sample technology on the classification results of imbalanced data is what we will study further in our future work.


## 6. Conclusions

In this paper, an optimized Support Vector Machine classifier, named PMSVM, is proposed, in which System Normalization, PCA, and MGS methods are used to try to average up the performances of SVM. Experimental results show that System Normalization can effectively assure the classification accuracy (Figure4). PCA (Principal Component Analysis) can play a role of dimensionality reduction. As shown in our experiments, chosing proper threshold value, PCA can both economize classification time and assure classification accuracy. The most prominent character in our study is whenever adopting our PCA and Multilevel Grid Search (MGS) methods, the time consuming of our PMSVM algorithm can be reduced by 75
% or so, averagely, and meanwhile can get similar or better classification accuracy than the classical LIBSVM algorithm.



---

*Source: 320186-2015-02-22.xml*