# Cost-Sensitive Support Vector Machine Using Randomized Dual Coordinate Descent Method for Big Class-Imbalanced Data Classification

Authors: Mingzhu Tang; Chunhua Yang; Kang Zhang; Qiyue Xie
Journal: Abstract and Applied Analysis
 (2014)

---

## Abstract

Cost-sensitive support vector machine is one of the most popular tools to deal with class-imbalanced problem such as fault diagnosis. However, such data appear with a huge number of examples as well as features. Aiming at class-imbalanced problem on big data, a cost-sensitive support vector machine using randomized dual coordinate descent method (CSVM-RDCD) is proposed in this paper. The solution of concerned subproblem at each iteration is derived in closed form and the computational cost is decreased through the accelerating strategy and cheap computation. The four constrained conditions of CSVM-RDCD are derived. Experimental results illustrate that the proposed method increases recognition rates of positive class and reduces average misclassification costs on real big class-imbalanced data.


---

## Body

## 1. Introduction

The most popular strategy for the design of classification algorithms is to minimize the probability of error, assuming that all misclassifications have the same cost and classes of dataset are balanced [1–6]. The resulting decision rules are usually denoted as cost insensitive. However, in many important applications of machine learning, such as fault diagnosis [7] and fraud detection, certain types of error are much more costly than others. Other applications involve significantly class-imbalanced datasets, where examples from different classes appear with substantially different probability. Cost-sensitive support vector machine (CSVM) [2] is one of the most popular tools to deal with class-imbalanced problem and unequal misclassification problem. However, in many applications, such data appear with a huge number of examples as well as features.In this work we consider the cost-sensitive support vector machine architecture [1]. Although CSVMs are based on a very solid learning-theoretic foundation and have been successfully applied to many classification problems, it is not well understood how to design big data learning of the CSVM algorithm. CSVM usually maps training vectors into a high dimensional space via a nonlinear function. Due to the high dimensionality of the weight vector, one solves the dual problem of CSVM by the kernel trick. In some applications, data appear in a rich dimensional feature space; the performances are similar with/without nonlinear mapping. If data are not mapped, we can often train much data set.Recently, many methods have been proposed for linear SVM in large-scale scenarios [4]. In all methods, dual coordinate descent methods for dual problem of CSVM are one of popular methods to deal with large-scale convex optimization problem. However, they do not focus on big data learning of CSVM. We focus on big data class-imbalanced learning by CSVM.This paper is organized as follows. In Section2 basic theory of cost-sensitive support vector machine is described. In Section 3 we derive our proposed algorithm. Section 4 discusses both speed-ups and four constrained conditions of cost-sensitive support vector machine. Implementation issues are investigated in Section 5. Experiments show efficiently our proposed method.


## 2. Basic Theory of Cost-Sensitive Support Vector Machine

Cost-sensitive support vector machine such as 2C-SVM is proposed in [1]. Consider examples set {(xi,yi)}i=1l, xi∈Rd, yi∈Y={+1,-1}, I+={i:yi=+1}, I-={i:yi=-1}. The 2C-SVM has primal optimization problem:
(1)min⁡w,b,ξ12∥w∥2+Cγ∑i∈I+ξi+C(1-γ)∑i∈I-ξis.t.iiiiiiyi(wTxi+b)≥1-ξii=1,2,…,liiiξi≥0i=1,2,…,liiiC>0.
Lagrange multipliers method can be used to solve the constrained optimization problem. In this method, the Lagrange equation is defined as follows:
(2)L(w,b,ξ)=12∥w∥2+Cγ∑i∈I+ξi+C(1-γ)∑i∈I-ξi+∑i=1lαi[1-ξi-yi(wTxi+b)]+∑i=1lβi[-ξi],
where the αi, βi’s are called the Lagrange multipliers. L’s partial derivatives are set to be zero as follows:
(3)∂L(w,b,ξ)∂w=0,∂L(w,b,ξ)∂b=0,∂L(w,b,ξ)∂ξi=0.And solvew,b,ξ. The formula (3) is extended to be
(4)∂L(w,b,ξ)∂w=w+∑i=1lαi[-yixi]=0,∂L(w,b,ξ)∂b=∑i=1lαi(-yi)=0,∂L(w,b,ξ)∂ξi=Cγ-αi-βi=0,i∈I+,∂L(w,b,ξ)∂ξi=C(1-γ)-αi-βi=0,i∈I-.Equation (4) can be reformatted as
(5)w=∑i=1lαiyixi,(6)∑i=1lαiyi=0,(7)Cγ-αi-βi=0,i∈I+,C(1-γ)-αi-βi=0,i∈I-.By incorporating (5) to (7), Lagrange equation (2) is rewritten as
(8)L(w,b,ξ)=12∥∑i=1nαiyixi∥2+Cγ∑i∈I+ξi+C(1-γ)∑i∈I-ξi+∑i=1lαi[1-ξi-yi((∑i=1nαiyixi)Txi+b)]+∑i∈I+(Cγ-αi)[-ξi]+∑i∈I-(C(1-γ)-αi)[-ξi].Lagrange equation (8) is simplified as
(9)L(w,b,ξ)=-12∑i=1lαi[yi((∑j=1lαjyjxj)Txi)]+∑i=1lαi.Recall that the equation above is obtained by minimizingL with respect to w and b. Putting this together with the constraints αi≥0 and the constraints (5) to (7), the following dual optimization problem of 2C-SVM is obtained as
(10)min⁡αf(α)=12∑i=1l∑j=1lαiαjyiyjxiTxj-∑i=1lαis.t.iiiiii0≤αi≤Cγ,i∈I+II0≤αi≤C(1-γ),i∈I-II∑i=1lαiyi=0,
where αi, i=1,…,l are Lagrange multipliers and Cγ, C(1-γ), C>0, γ∈[0,1] are misclassification cost parameters. The matrixes Q and α are defined, respectively, as follows:
(11)Q=[Qij]l×l,whereQij=αiαjyiyjxiTxj,α=[α1,…,αi,…,αj,…,αl].


## 3. Cost-Sensitive Support Vector Machine Using Randomized Dual Coordinate Descent Method

In this section, randomized dual coordinate descent method is used to solve 2C-SVM that is one version of cost-sensitive support vector machine. The optimization process starts from an initial pointα0∈Rl and generates a sequence of vectors αk, k=0,…,∞. The process from αk to αk+1 is called an outer iteration. In each outer iteration l is called inner iteration, so that α1,α2,…,αl are sequentially updated. Each outer iteration thus generates vectors αk,i∈Rl, i=1,2,…,l+1, such that
(12)αk,1=αk,i=1,αk,i=[α1k+1,…,αi-1k+1,αik,…,αlk],∀i=2,…,l,αk,l=αk,i=l+1.For updatingαk,i to αk,i+1, the following one-variable subproblem is solved as
(13)min⁡d⁡f(αk,i+dei),
where ei=[0,…,1,…,0]T. This is general process of one-variable coordinate descent method. However, the sum constrained condition of the optimization problem (13) is denoted as follows:
(14)∑i=1nαiyi=0,
where αi is exactly determined by the other αi,s, and if we were to hold {αi}i=1n∖αi fixed, then we cannot make any change αi without violating the constraint condition (14) in the optimization problem.Thus if we want to update some subject of theαi,s, we must update at least two of them simultaneously in order to keep satisfying the constraints. We currently have some setting of the αis that satisfy the constraint conditions (14) and suppose we have decided to hold {αi}i=1n∖αi,αj fixed and reoptimize the dual problem of CSVM (10) with respect to αi, αj (subject to the constraints). Equation (6) is reformatted as
(15)αiyi+αjyj=∑m=1lαmym-αiyi-αjyj.Since the right hand side is fixed, we can just let it be denoted by some constantζ:
(16)ζ=∑m=1lαmym-αiyi-αjyj.We can form the updated coordinates before and after with respect toαi, αj:
(17)αikyi+αjkyj=αik+1yi+αjk+1yj=ζ.αikyi, αik+1yi are updated coordinates before and after with respect to αik. Consider the following dual two-variable subproblem of 2C-SVM:
(18)f(αk,i+diei)+f(αk,j+djej)=Qiidi2+{2(αk,iQ-)i-1}di+Qjjdj2+{2(αk,jQ-)j-1}dj+c,
where c is constant, Qi=[Qi,s,…,Qi,s-1,Qi,s,…,Qi,l], and
(19)(αk,iQ-)i=∑s=1lQi,sαik,s.From (18), we obtain
(20)f′(α)=αTQ-1,(21)∂f(αk,i)∂αi=2(αk,iQ-)i-1,
where ∂f(αk,i)/∂αi is the ith component of the gradient f′(α). By incorporating (21), (18) is rewritten as
(22)f(αk,i+diei)+f(αk,j+djej)=Qiidi2+∂f(αk,i)∂αidi+Qjjdj2+∂f(αk,j)∂αjdj+c.From (17), we have dj=-diyiyj. Equation (22) is reformed as follows:
(23)f(αk,i+diei)+f(αk,j+djej)=Qiidi2+∂f(αk,i)∂αidi+Qjjdi2-∂f(αk,j)∂αjdiyiyj+c=(Qii+Qjj)di2+(∂f(αk,i)∂αi-∂f(αk,j)∂αjyiyj)di+c.Treating(Qii+Qjj), ((∂f(αk,i)/∂αi)-(∂f(αk,j)/∂αj)yiyj), c as constants, we should be able to verify that this is just some quadratic function in di. We can easily maximize this quadratic function by setting its derivative to zero and solving the optimization problem. The following two-variable optimization problem is obtained as
(24)min⁡dif(αk,i+diei)+f(αk,j+djej).The closed form is derived as follows:(25)di=(∂f(αk,i)/∂αi)-(∂f(αk,j)/∂αj)(yiyj)2(Qii+Qjj).We now consider the box constraints (10) of the two-variable optimization problem. The box constraints as 0≤αi≤Cγ, i∈I+, 0≤αi≤C(1-γ), i∈I- are classified to four boxes constraints according to the labels of examples from some two coordinates.Firstly, suppose that the labels of examples are as(26)yi=+1,yj=-1.The sum constraints of Lagrange multipliers according to these labels are as(27)αiyi+αjyj=ζ.Another expressing of sum constraints of Lagrange multipliers is as(28)αi-αj=ζ,orαi=αj+ζ.The box constraints of Lagrange multipliers are defined as(29)0≤αi≤γC,0≤αj≤(1-γ)C.We obtain the new expressing of box constraints of Lagrange multipliers as the following:(30)0≤ζ≤(1-γ)C,0≤αi≤αi-αj-(1-γ)C,or-(1-γ)C≤ζ≤0,αi-αj≤αi≤γC.Thus we obtain stricter box constraints of Lagrange multipliersαi, αj according to yi=+1, yj=-1 as the following:
(31)U1=max⁡(0,αi-αj),V1=min⁡(αi-αj-(1-γ)C,γC).Secondly, suppose that the labels of examples are as(32)yi=+1,yj=+1.Similarly, similar stricter box constraints of Lagrange multipliersαi, αj are obtained as follows:
(33)U2=max⁡(0,αi+αj-γC),V2=min⁡(αi+αj,γC).Thirdly, suppose that the labels of examples are as(34)yi=-1,yj=-1.Similarly, the similar stricter box constraints of Lagrange multipliersαi,αj are obtained as follows:
(35)U3=max⁡(0,-αi-αj-(1-γ)C),V3=min⁡(-αi-αj,(1-γ)C).Finally, suppose that the labels of examples are as(36)yi=-1,yj=+1.Similarly, the similar stricter box constraints of Lagrange multipliersαi,αj are obtained as follows:
(37)U4=max⁡(0,-αi-αj),V4=min⁡(γC-αi-αj,(1-γ)C).For the simplification, set(38)αitemp=αik,i+di,αik,i+1 is defined as the temp solution, which would be edited to satisfy
(39)αik,i+1={Vi,ifαitemp>Vi,i=1,2,3,4αitemp,ifUi<αitemp<Vi,i=1,2,3,4Ui,ifαitemp<Ui,i=1,2,3,4.From linear constraints with respect toαik,i+1 in (17), the value of αik,j+1 is obtained as
(40)αik,j+1=yj(yiαik,i+yjαik,j-yiαik,i+1).


## 4. The Modified Proposed Method

### 4.1. Two Speeding-Up Strategies

To avoid duplicate and invalid iterative process calculations, the two given conditions are not updated. If one of two conditions is met, then the algorithm skips this iteration that can significantly reduce the computational amount and accelerate the convergence speed.Condition 1.
Ifαik,i=αik,j=0 or αik,i=αik,j=C, then the constrained conditions are not updated.Due to the box constraints of (10), there will appear a lot of boundary points of coordinates (αik,i=C or αik,i=0) in computing process. If there are two coordinates (αik,i and αik,i) as the value of 0 or C in an iteration process, the analytical solution of the two subvariables updates coordinates without calculating. The reason is that the formula (17) guarantees αik,i+αik,j=0 or αik,i+αik,j=2C, while double restricted box constrained optimization 0≤αik,i≤C if the result is 0 or C. Constrained conditions will be edited ultimately as 0 or C. The constrained conditions are not updated.Condition 2.
If projected gradient is 0, the constrained conditions are not updated.


### 4.2. Dual Problem of Cost-Sensitive Support Vector Machine Using Randomized Dual Coordinate Descent Method and Its Complexity Analysis

From the above algorithm derivation of view, solving of CSVM seems to have been successful, but the computational complexity of the solving process is also larger. Assume that the average value of nonzero feature of each sample isn-. Firstly, the computational complexity of the inner product matrix Qii=yixiTxiyi, i=1,2,…,l is O(ln-), but the process can be operated in advance and stored into memory. Secondly, the calculation of (αk,iQ-)i=∑s=1lQi,sαik,s takes the computational complexity O(ln-). The amount of calculation is very great when the data size is large. However, there is a linear relationship model CSVM:
(41)w=∑s=1lαik,sxsys.Thus,(αk,iQ-)i is further simplified as follows:
(42)(αk,iQ-)i=∑s=1lQi,sαik,s=∑s=1l(αik,sysxsT)xsys=wTxiyi.Solving the corresponding formula (23) can be simplified as follows:
(43)di=2(αk,iQ-)i-1-(2(αk,jQ-)j-1)yiyj2(Qii+Qjj)=2wTxiyi-1-(2wTxjyj-1)yiyj2(Qii+Qjj).As can be seen, computingdi with the complexity of O(ln-) becomes computing wTxiyi with the complexity of O(n-). Thus the calculation times reduce l-1. However,
(44)w=∑s=1lαik,sxsys,
where w is the updated still computational complexity O(ln-). The amount of calculation can be reduced significantly when w is updated by changing αik,s. Let αik,i, αik,j be the values of the current selection; αik,i+1, αik,j+1 are updated values, which can be updated via a simple way:
(45)w⟵w+(αik,i-αik,i+1)xiyi+(αik,j-αik,j+1)xjyj.Its computational complexity only isO(n-). So, whether calculating di or updating w, coordinate gradient computation complexity is O(n-), which is one of the coordinate gradient method rapid convergence speed reasons.When assigned an initial value and constraints based on(46)∑i=1nαiyi=0,0≤αi≤γC,0≤αj≤(1-γ)C,
set the initial point
(47)α0=[…,αi,…,αj,…,]1×lT,
where αi=1/t, αj=(1/(l-t))l,t are the total number of samples and the number of positive samples, respectively. Thus the weight vector w of the original problem is obtained by optimizing Lagrangian multipliers α of the dual problem.


### 4.3. Description of Cost-Sensitive Support Vector Machine Using Randomized Dual Coordinate Descent Method

Accelerated conditions are judged by Section4.1. One chooses the coordinate optimized number i,j. We use formula (43) to calculate di, formulas (39) and (40) to update αik,i, αik,j, and the formula (45) to update w, respectively. We can see that inner iteration takes O(n-) effort. The computer memory is mainly used to store samples information x1,x2,…,xl and each sample point and their inner products Qii=yixiTxiyi. Cost-sensitive support vector machine using dual randomized coordinate gradient descent algorithm is described as follows.Algorithm  3. Cost-sensitive support vector machine using randomized dual coordinate descent algorithm (CSVM-RDCD).Input: sample information{(xi,yi)}i=1l, α0.Output:αTw.Initializeα0 and the corresponding w=∑i=1lαixiyi.Fork=1,2,…,T do
(48)αk,1⟵αk.Step 1.
Randomly choosei,j∈{1,2,…,l}, i≠j and the corresponding yi, yj.Step 2.
(49)
If
(
y
i
=
+
1
,
y
j
=
-
1
)
{
U
1
=
max
⁡
(
0
,
α
i
-
α
j
)
;
I
V
1
=
min
⁡
(
α
i
-
α
j
-
(
1
-
γ
)
C
,
γ
C
)
;
U
1
}
if
(
y
i
=
+
1
,
y
j
=
+
1
)
{
U
2
=
max
⁡
(
0
,
α
i
+
α
j
-
γ
C
)
;
I
V
2
=
min
⁡
(
α
i
+
α
j
,
γ
C
)
;
U
2
}
if
(
y
i
=
-
1
,
y
j
=
-
1
)
{
U
3
=
max
⁡
(
0
,
-
α
i
-
α
j
-
(
1
-
γ
)
C
)
;
I
V
3
=
min
⁡
(
-
α
i
-
α
j
,
(
1
-
γ
)
C
)
;
}
if
(
y
i
=
-
1
,
y
j
=
+
1
)
{
U
4
=
max
⁡
(
0
,
-
α
i
-
α
j
)
;
I
V
4
=
min
⁡
⁡
(
γ
C
-
α
i
-
α
j
,
(
1
-
γ
)
C
)
;
}
.Step 3.
(50)
α
i
temp
=
α
i
k
,
i
+
2
w
T
x
i
y
i
-
1
-
(
2
w
T
x
j
y
j
-
1
)
y
i
y
j
2
(
Q
i
i
+
Q
j
j
)
.Step 4.
(51)
if
(
y
i
=
1
,
y
j
=
-
1
)
m
=
1
;
if
(
y
i
=
1
,
y
j
=
1
)
m
=
2
;
if
(
y
i
=
-
1
,
y
j
=
-
1
)
m
=
3
;
f
(
y
i
=
-
1
,
y
j
=
+
1
)
m
=
4
;
α
i
k
,
i
+
1
=
{
V
m
,
if
α
i
temp
>
V
m
α
i
temp
,
if
U
m
<
α
i
temp
<
V
m
U
m
,
if
α
i
temp
<
U
m
.Step 5.
(52)
α
i
k
,
j
+
1
=
y
j
{
y
i
α
i
k
,
i
+
y
j
α
j
k
,
j
-
y
i
α
i
k
,
i
+
1
}
.Step 6.
(53)
w
⟵
w
+
(
α
i
k
,
i
-
α
i
k
,
i
+
1
)
x
i
y
i
+
(
α
i
k
,
j
-
α
i
k
,
j
+
1
)
x
j
y
j
.
Until A stopping condition is satisfied,(54)αk+1⟵αk.
End for.


## 4.1. Two Speeding-Up Strategies

To avoid duplicate and invalid iterative process calculations, the two given conditions are not updated. If one of two conditions is met, then the algorithm skips this iteration that can significantly reduce the computational amount and accelerate the convergence speed.Condition 1.
Ifαik,i=αik,j=0 or αik,i=αik,j=C, then the constrained conditions are not updated.Due to the box constraints of (10), there will appear a lot of boundary points of coordinates (αik,i=C or αik,i=0) in computing process. If there are two coordinates (αik,i and αik,i) as the value of 0 or C in an iteration process, the analytical solution of the two subvariables updates coordinates without calculating. The reason is that the formula (17) guarantees αik,i+αik,j=0 or αik,i+αik,j=2C, while double restricted box constrained optimization 0≤αik,i≤C if the result is 0 or C. Constrained conditions will be edited ultimately as 0 or C. The constrained conditions are not updated.Condition 2.
If projected gradient is 0, the constrained conditions are not updated.


## 4.2. Dual Problem of Cost-Sensitive Support Vector Machine Using Randomized Dual Coordinate Descent Method and Its Complexity Analysis

From the above algorithm derivation of view, solving of CSVM seems to have been successful, but the computational complexity of the solving process is also larger. Assume that the average value of nonzero feature of each sample isn-. Firstly, the computational complexity of the inner product matrix Qii=yixiTxiyi, i=1,2,…,l is O(ln-), but the process can be operated in advance and stored into memory. Secondly, the calculation of (αk,iQ-)i=∑s=1lQi,sαik,s takes the computational complexity O(ln-). The amount of calculation is very great when the data size is large. However, there is a linear relationship model CSVM:
(41)w=∑s=1lαik,sxsys.Thus,(αk,iQ-)i is further simplified as follows:
(42)(αk,iQ-)i=∑s=1lQi,sαik,s=∑s=1l(αik,sysxsT)xsys=wTxiyi.Solving the corresponding formula (23) can be simplified as follows:
(43)di=2(αk,iQ-)i-1-(2(αk,jQ-)j-1)yiyj2(Qii+Qjj)=2wTxiyi-1-(2wTxjyj-1)yiyj2(Qii+Qjj).As can be seen, computingdi with the complexity of O(ln-) becomes computing wTxiyi with the complexity of O(n-). Thus the calculation times reduce l-1. However,
(44)w=∑s=1lαik,sxsys,
where w is the updated still computational complexity O(ln-). The amount of calculation can be reduced significantly when w is updated by changing αik,s. Let αik,i, αik,j be the values of the current selection; αik,i+1, αik,j+1 are updated values, which can be updated via a simple way:
(45)w⟵w+(αik,i-αik,i+1)xiyi+(αik,j-αik,j+1)xjyj.Its computational complexity only isO(n-). So, whether calculating di or updating w, coordinate gradient computation complexity is O(n-), which is one of the coordinate gradient method rapid convergence speed reasons.When assigned an initial value and constraints based on(46)∑i=1nαiyi=0,0≤αi≤γC,0≤αj≤(1-γ)C,
set the initial point
(47)α0=[…,αi,…,αj,…,]1×lT,
where αi=1/t, αj=(1/(l-t))l,t are the total number of samples and the number of positive samples, respectively. Thus the weight vector w of the original problem is obtained by optimizing Lagrangian multipliers α of the dual problem.


## 4.3. Description of Cost-Sensitive Support Vector Machine Using Randomized Dual Coordinate Descent Method

Accelerated conditions are judged by Section4.1. One chooses the coordinate optimized number i,j. We use formula (43) to calculate di, formulas (39) and (40) to update αik,i, αik,j, and the formula (45) to update w, respectively. We can see that inner iteration takes O(n-) effort. The computer memory is mainly used to store samples information x1,x2,…,xl and each sample point and their inner products Qii=yixiTxiyi. Cost-sensitive support vector machine using dual randomized coordinate gradient descent algorithm is described as follows.Algorithm  3. Cost-sensitive support vector machine using randomized dual coordinate descent algorithm (CSVM-RDCD).Input: sample information{(xi,yi)}i=1l, α0.Output:αTw.Initializeα0 and the corresponding w=∑i=1lαixiyi.Fork=1,2,…,T do
(48)αk,1⟵αk.Step 1.
Randomly choosei,j∈{1,2,…,l}, i≠j and the corresponding yi, yj.Step 2.
(49)
If
(
y
i
=
+
1
,
y
j
=
-
1
)
{
U
1
=
max
⁡
(
0
,
α
i
-
α
j
)
;
I
V
1
=
min
⁡
(
α
i
-
α
j
-
(
1
-
γ
)
C
,
γ
C
)
;
U
1
}
if
(
y
i
=
+
1
,
y
j
=
+
1
)
{
U
2
=
max
⁡
(
0
,
α
i
+
α
j
-
γ
C
)
;
I
V
2
=
min
⁡
(
α
i
+
α
j
,
γ
C
)
;
U
2
}
if
(
y
i
=
-
1
,
y
j
=
-
1
)
{
U
3
=
max
⁡
(
0
,
-
α
i
-
α
j
-
(
1
-
γ
)
C
)
;
I
V
3
=
min
⁡
(
-
α
i
-
α
j
,
(
1
-
γ
)
C
)
;
}
if
(
y
i
=
-
1
,
y
j
=
+
1
)
{
U
4
=
max
⁡
(
0
,
-
α
i
-
α
j
)
;
I
V
4
=
min
⁡
⁡
(
γ
C
-
α
i
-
α
j
,
(
1
-
γ
)
C
)
;
}
.Step 3.
(50)
α
i
temp
=
α
i
k
,
i
+
2
w
T
x
i
y
i
-
1
-
(
2
w
T
x
j
y
j
-
1
)
y
i
y
j
2
(
Q
i
i
+
Q
j
j
)
.Step 4.
(51)
if
(
y
i
=
1
,
y
j
=
-
1
)
m
=
1
;
if
(
y
i
=
1
,
y
j
=
1
)
m
=
2
;
if
(
y
i
=
-
1
,
y
j
=
-
1
)
m
=
3
;
f
(
y
i
=
-
1
,
y
j
=
+
1
)
m
=
4
;
α
i
k
,
i
+
1
=
{
V
m
,
if
α
i
temp
>
V
m
α
i
temp
,
if
U
m
<
α
i
temp
<
V
m
U
m
,
if
α
i
temp
<
U
m
.Step 5.
(52)
α
i
k
,
j
+
1
=
y
j
{
y
i
α
i
k
,
i
+
y
j
α
j
k
,
j
-
y
i
α
i
k
,
i
+
1
}
.Step 6.
(53)
w
⟵
w
+
(
α
i
k
,
i
-
α
i
k
,
i
+
1
)
x
i
y
i
+
(
α
i
k
,
j
-
α
i
k
,
j
+
1
)
x
j
y
j
.
Until A stopping condition is satisfied,(54)αk+1⟵αk.
End for.


## 5. Experiments and Analysis

### 5.1. Experiment on Big Class-Imbalanced Benchmark Datasets Classification Problem

In this section, we analyze the performance of the proposed cost-sensitive support vector machine using randomized dual coordinate descent method (CSVM-RDCD). We compare our implementation with the state-of-the-art cost-sensitive support vector. Three implementations of related cost-sensitive SVMs are compared. We proposed the cost-sensitive SVM using randomized dual coordinate descent method (CSVM-RDCD) by modifying the LibSVM [8, 9] source code. Eitrich and Lang [10] proposed parallel cost-sensitive support vector machine (PCSVM). [6] proposed cost-sensitive support vector machines (CSSVM).Table1 lists the statistics of data sets. KDD99, Web Spam, Covertype, MNIST, SIAM1, and SIAM11 are obtained from the following data website.KDD99 is at http://kdd.ics.uci.edu/databases/kddcup99/kddcup99.html. Web Spam is at http://www.cc.gatech.edu/projects/doi/WebbSpamCorpus.html. Covertype is at http://archive.ics.uci.edu/ml/datasets/Covertype. MNIST is at http://yann.lecun.com/exdb/mnist/. SIAM is at https://c3.nasa.gov/dashlink/resources/138/.Table 1
Specification of the benchmark datasets. Number of ex. is the number of example data points. Number of feat. is the number of features. Ratio is the class imbalance ratio. Target specifies the target or positive class. Number is the number of the datasets.
Dataset
Number of ex.
Number of feat.
Ratio
Positive class
Number
KDD99 (intrusion detection)
5,209,460
42
1 : 4
Normal
1
Web span
350,000
254
1 : 2
−1
2
MNIST
70,000
780
1 : 10
5
3
Covertype
581,012
54
1 : 211
Cottonwood/Willow(4)
4
SIAM1
28,596
30,438
1 : 2000
1, 6, 7, 11
5
SIAM11
28,596
30,438
1 : 716
11, 12
6To evaluate the performance of CSVM-RDCD method, we use a stratified selection to split each dataset to 9/10 training and 1/10 testing. We briefly describe each set below. For each dataset we choose the class with the higher cost or fewer data points as the target or positive class. All multiclass datasets were converted to binary data sets. In particular, the binary datasets SIAM1 and SIAM2 are datasets which have been constructed from the same multiclass dataset but with different target class and different imbalance ratios.Evaluation of the performance of the three algorithms using CSVM was 10-fold cross-validation tested average misclassification cost, the training time, and the recognition rate of the positive class (i.e., the recognition rate of the minority class).Average misclassification cost (AMC) represents 10-fold cross-validation average misclassification cost on test datasets for related CSVMs, described as follows:(55)AMC=fp×Cγ+fn×C(1-γ)N,
where fp and fn represent the number of the positive examples misclassified as the negative examples in the test dataset and the number of the negative examples misclassified as the positive examples in the test data set, respectively. Cγ and C(1-γ) denote the cost of the positive examples misclassified as the negative examples in the test data set and the cost of the negative examples misclassified as the positive examples in the test data set, respectively. N denotes the number of test examples.The recognition rate of the positive class is the number of classified positive classes and the number of the positive classes on testing dataset.Training time in seconds is used to evaluate the convergence speeding of three algorithms using CSVM on the same computer.Cost-sensitive parameters of three algorithms using CSVM are specified as the following Table2. Cost-sensitive parameters Cγ and C(1-γ) are valued according to the class ratio of datasets, namely, the class ratio of minority class and majority class.Table 2
Cost-sensitive parameters of three algorithms using CSVM on 6 datasets.
Dataset
C
γ
C
(
1
-
γ
)
KDD99 (intrusion detection)
4
1
Web span
2
1
MNIST
10
1
Covertype
211
1
SIAM1
2000
1
SIAM11
716
1Three datasets with relative class imbalance are examined. Namely, KDD99 (intrusion detection), Web span, and MNIST datasets are considered. Three datasets with severe class imbalance are examined. Namely, Covertype, SIAM1, and SIAM11 datasets are considered. The average misclassification cost comparison of three algorithms using CSVM is shown in Figure1 for each of the datasets. The CSVM-RDCD algorithm outperforms the PCSVM and CSVM on all datasets.Figure 1
Average misclassification cost comparison of three algorithms using CSVM on 6 datasets.The recognition rate of positive class comparison of three algorithms using CSVM is shown in Figure2 for each of the datasets. The CSVM-RDCD algorithm outperforms the PCSVM and CSSVM on all datasets, surpasses the PCSVM on four datasets, and ties with the PCSVM on two datasets.Figure 2
The positive class recognition rate comparison of three algorithms using CSVM.We examine large datasets with relative imbalance ratios and severe imbalance ratios to evaluate the convergence speed of CSVM-RDCD algorithm. The training time comparison of three algorithms using CSVM is shown in Figure3 for each of the datasets. The CSVM-RDCD algorithm outperforms the PCSVM and CSSVM on all datasets.Figure 3
Training time (s) comparison of three algorithms using CSSVM.


### 5.2. Experiment on Real-World Big Class-Imbalanced Dataset Classification Problems

In order to verify the effectiveness of the proposed algorithm CSVM-RDCD on real-world big class-imbalanced data classification problems, it was evaluated using the real vibration data measured in the wind turbine. The experimental data were from the SKF WindCon software and collected from a wind turbine gearbox type TF138-A [11]. The vibration signals were continuously acquired by an accelerometer mounted on the outer case of the gearbox.All parameter settings for the dataset are listed in Table3. The statistical results of the big class-imbalanced data problems that measure the quality of results (average misclassification cost, recognition rate of positive class, and training time) are listed in Table 4. From Table 4, it can be concluded that CSVM-RDCD is able to consistently achieve superior performance in the big class-imbalanced data classification problems.Table 3
Specification of the benchmark datasets and cost-sensitive parameters on the dataset.
Dataset
Fault diagnosis of wind turbine
Number of ex.
20000
Number of feat.
56
Ratio
190
Positive class
Local crack fault
C
γ
190
C
(
1
-
γ
)
1Table 4
Classification performance of three algorithms using CSVM on the dataset.
Name of algorithms
AMC
Recognition of positive class
Training time
CSVM-RDCD
0.01825
98.5%
5.43 s
PCSVM
0.0334
97.6%
6.15 s
CSSVM
0.0379
97.2%
7.34 sExperimental results show that it is applicable to solve cost-sensitive SVM dual problem using randomized dual coordinate descent method on the large-scale experimental data sets. The proposed method can achieve superior performance in the average misclassification cost, recognition rate of positive class, and training time. Large-scale experimental data sets show that cost-sensitive support vector machines using randomized dual coordinate descent method run more efficiently than both PCSVM and CSSVM; especially randomized dual coordinate descent algorithm has advantage of training time on large-scale data sets. CSSVM needs to build complex whole gradient and kernel matrixQ and needs to select the set of complex work in solving process of decomposition algorithm. Decomposition algorithm updates full uniform gradient information as a whole, the computational complexity O(ln-) for the full gradient update. PCSVM also has similar computational complexity. Randomized dual coordinate gradient method updates linearly the coordinates, its computational complexity as O(n-), which increases considerably the convergence speed of the proposed method.


## 5.1. Experiment on Big Class-Imbalanced Benchmark Datasets Classification Problem

In this section, we analyze the performance of the proposed cost-sensitive support vector machine using randomized dual coordinate descent method (CSVM-RDCD). We compare our implementation with the state-of-the-art cost-sensitive support vector. Three implementations of related cost-sensitive SVMs are compared. We proposed the cost-sensitive SVM using randomized dual coordinate descent method (CSVM-RDCD) by modifying the LibSVM [8, 9] source code. Eitrich and Lang [10] proposed parallel cost-sensitive support vector machine (PCSVM). [6] proposed cost-sensitive support vector machines (CSSVM).Table1 lists the statistics of data sets. KDD99, Web Spam, Covertype, MNIST, SIAM1, and SIAM11 are obtained from the following data website.KDD99 is at http://kdd.ics.uci.edu/databases/kddcup99/kddcup99.html. Web Spam is at http://www.cc.gatech.edu/projects/doi/WebbSpamCorpus.html. Covertype is at http://archive.ics.uci.edu/ml/datasets/Covertype. MNIST is at http://yann.lecun.com/exdb/mnist/. SIAM is at https://c3.nasa.gov/dashlink/resources/138/.Table 1
Specification of the benchmark datasets. Number of ex. is the number of example data points. Number of feat. is the number of features. Ratio is the class imbalance ratio. Target specifies the target or positive class. Number is the number of the datasets.
Dataset
Number of ex.
Number of feat.
Ratio
Positive class
Number
KDD99 (intrusion detection)
5,209,460
42
1 : 4
Normal
1
Web span
350,000
254
1 : 2
−1
2
MNIST
70,000
780
1 : 10
5
3
Covertype
581,012
54
1 : 211
Cottonwood/Willow(4)
4
SIAM1
28,596
30,438
1 : 2000
1, 6, 7, 11
5
SIAM11
28,596
30,438
1 : 716
11, 12
6To evaluate the performance of CSVM-RDCD method, we use a stratified selection to split each dataset to 9/10 training and 1/10 testing. We briefly describe each set below. For each dataset we choose the class with the higher cost or fewer data points as the target or positive class. All multiclass datasets were converted to binary data sets. In particular, the binary datasets SIAM1 and SIAM2 are datasets which have been constructed from the same multiclass dataset but with different target class and different imbalance ratios.Evaluation of the performance of the three algorithms using CSVM was 10-fold cross-validation tested average misclassification cost, the training time, and the recognition rate of the positive class (i.e., the recognition rate of the minority class).Average misclassification cost (AMC) represents 10-fold cross-validation average misclassification cost on test datasets for related CSVMs, described as follows:(55)AMC=fp×Cγ+fn×C(1-γ)N,
where fp and fn represent the number of the positive examples misclassified as the negative examples in the test dataset and the number of the negative examples misclassified as the positive examples in the test data set, respectively. Cγ and C(1-γ) denote the cost of the positive examples misclassified as the negative examples in the test data set and the cost of the negative examples misclassified as the positive examples in the test data set, respectively. N denotes the number of test examples.The recognition rate of the positive class is the number of classified positive classes and the number of the positive classes on testing dataset.Training time in seconds is used to evaluate the convergence speeding of three algorithms using CSVM on the same computer.Cost-sensitive parameters of three algorithms using CSVM are specified as the following Table2. Cost-sensitive parameters Cγ and C(1-γ) are valued according to the class ratio of datasets, namely, the class ratio of minority class and majority class.Table 2
Cost-sensitive parameters of three algorithms using CSVM on 6 datasets.
Dataset
C
γ
C
(
1
-
γ
)
KDD99 (intrusion detection)
4
1
Web span
2
1
MNIST
10
1
Covertype
211
1
SIAM1
2000
1
SIAM11
716
1Three datasets with relative class imbalance are examined. Namely, KDD99 (intrusion detection), Web span, and MNIST datasets are considered. Three datasets with severe class imbalance are examined. Namely, Covertype, SIAM1, and SIAM11 datasets are considered. The average misclassification cost comparison of three algorithms using CSVM is shown in Figure1 for each of the datasets. The CSVM-RDCD algorithm outperforms the PCSVM and CSVM on all datasets.Figure 1
Average misclassification cost comparison of three algorithms using CSVM on 6 datasets.The recognition rate of positive class comparison of three algorithms using CSVM is shown in Figure2 for each of the datasets. The CSVM-RDCD algorithm outperforms the PCSVM and CSSVM on all datasets, surpasses the PCSVM on four datasets, and ties with the PCSVM on two datasets.Figure 2
The positive class recognition rate comparison of three algorithms using CSVM.We examine large datasets with relative imbalance ratios and severe imbalance ratios to evaluate the convergence speed of CSVM-RDCD algorithm. The training time comparison of three algorithms using CSVM is shown in Figure3 for each of the datasets. The CSVM-RDCD algorithm outperforms the PCSVM and CSSVM on all datasets.Figure 3
Training time (s) comparison of three algorithms using CSSVM.


## 5.2. Experiment on Real-World Big Class-Imbalanced Dataset Classification Problems

In order to verify the effectiveness of the proposed algorithm CSVM-RDCD on real-world big class-imbalanced data classification problems, it was evaluated using the real vibration data measured in the wind turbine. The experimental data were from the SKF WindCon software and collected from a wind turbine gearbox type TF138-A [11]. The vibration signals were continuously acquired by an accelerometer mounted on the outer case of the gearbox.All parameter settings for the dataset are listed in Table3. The statistical results of the big class-imbalanced data problems that measure the quality of results (average misclassification cost, recognition rate of positive class, and training time) are listed in Table 4. From Table 4, it can be concluded that CSVM-RDCD is able to consistently achieve superior performance in the big class-imbalanced data classification problems.Table 3
Specification of the benchmark datasets and cost-sensitive parameters on the dataset.
Dataset
Fault diagnosis of wind turbine
Number of ex.
20000
Number of feat.
56
Ratio
190
Positive class
Local crack fault
C
γ
190
C
(
1
-
γ
)
1Table 4
Classification performance of three algorithms using CSVM on the dataset.
Name of algorithms
AMC
Recognition of positive class
Training time
CSVM-RDCD
0.01825
98.5%
5.43 s
PCSVM
0.0334
97.6%
6.15 s
CSSVM
0.0379
97.2%
7.34 sExperimental results show that it is applicable to solve cost-sensitive SVM dual problem using randomized dual coordinate descent method on the large-scale experimental data sets. The proposed method can achieve superior performance in the average misclassification cost, recognition rate of positive class, and training time. Large-scale experimental data sets show that cost-sensitive support vector machines using randomized dual coordinate descent method run more efficiently than both PCSVM and CSSVM; especially randomized dual coordinate descent algorithm has advantage of training time on large-scale data sets. CSSVM needs to build complex whole gradient and kernel matrixQ and needs to select the set of complex work in solving process of decomposition algorithm. Decomposition algorithm updates full uniform gradient information as a whole, the computational complexity O(ln-) for the full gradient update. PCSVM also has similar computational complexity. Randomized dual coordinate gradient method updates linearly the coordinates, its computational complexity as O(n-), which increases considerably the convergence speed of the proposed method.


## 6. Conclusions

Randomized dual coordinate descentmethod (RDCD) is the optimization algorithm to update the global solution which is obtained by solving an analytical solution of the suboptimal problem. The RDCD method has the rapid convergence rate, which is mainly due to the following:(1) the subproblem has formal analytical solution, which is solved in solving process without complex numerical optimization; (2) the next component of RDCD method in solving process is updated on the basis of a previous component; compared with the full gradient information updated CSSVM method as a whole, the objective function of RDCD method can decline faster; (3) the single coordinate gradient calculation of RDCD method is simpler and easier than the full gradient calculation.Randomized dual coordinate descent method is applied to cost-sensitive support vector machine, which expanded the scope of application of the randomized dual coordinate descent method. For large-scale class-imbalanced problem, a cost-sensitive SVM using randomized dual coordinate descent method is proposed. Experimental results and analysis show the effectiveness and feasibility of the proposed method.



---

*Source: 416591-2014-07-03.xml*