# A Core Set Based Large Vector-Angular Region and Margin Approach for Novelty Detection

Authors: Jiusheng Chen; Xiaoyu Zhang; Kai Guo
Journal: Mathematical Problems in Engineering
 (2016)

---

## Abstract

A large vector-angular region and margin (LARM) approach is presented for novelty detection based on imbalanced data. The key idea is to construct the largest vector-angular region in the feature space to separate normal training patterns; meanwhile, maximize the vector-angular margin between the surface of this optimal vector-angular region and abnormal training patterns. In order to improve the generalization performance of LARM, the vector-angular distribution is optimized by maximizing the vector-angular mean and minimizing the vector-angular variance, which separates the normal and abnormal examples well. However, the inherent computation of quadratic programming (QP) solver takesO(n3) training time and at least O(n2) space, which might be computational prohibitive for large scale problems. By (1+ε)  and  (1-ε)-approximation algorithm, the core set based LARM algorithm is proposed for fast training LARM problem. Experimental results based on imbalanced datasets have validated the favorable efficiency of the proposed approach in novelty detection.


---

## Body

## 1. Introduction

The task of novelty detection is to learn a model from normal examples in training patterns and hence can classify the test patterns. In real-world novelty detection applications, it is usually assumed that normal training patterns can be well sampled, while abnormal training patterns are severely undersampled, which is due to expensive measurement cost or infrequency of abnormal events. Therefore, only normal training patterns are used to build detection model in most novelty detection algorithms. Generally, novelty detection may be seen as one-class classification problem. Recently, novelty detection has gained much research attention in real-world applications such as network intrusion detection [1], jet engine health monitoring [2], medical data [3], and aviation safety [4, 5].In this paper, the kernel-based novelty detection algorithm is studied in-depth, which is very popular and has been proved to be successful recently. Various kernel-based novelty detection approaches have been proposed, such as one-class support vector machine (OCSVM) [6] and support vector data description (SVDD) [7]. OCSVM was proposed by Schölkopf et al. [6], in which, to improve generalization ability, novelty detection boundary is constructed to separate the origin from the input samples with the maximal margin. The performance of OCSVM is very sensitive to the parameters, making it difficult to be generalized to other applications [8].SVDD was proposed by Tax and Duin [7], in which the minimal ball is constructed to enclose most of the training samples. Novelty point is assessed by determining whether a test point lies within the minimal ball or not. The margin between the closed boundary surrounding the positive data and that surrounding the negative data is zero, which makes the method of poor generalization ability. A small sphere and large margin (SSLM) approach was proposed by Wu and Ye [9], in which the smallest hypersphere is constructed to surround the normal data; meanwhile, the margin from any outlier to this hypersphere is as large as possible. An incremental weighted one-class support vector machine for mining streaming data was proposed by Krawczyk and Wózniak [10, 11], in which the weights to each object are modified according to its level of significance, and the shape of the decision boundary is influenced only by new objects that carry new and useful knowledge extending the competence of the classifier.Support vector machine (SVM) can be solved through figuring out quadratic programming (QP) problem, which has the important computational advantage of avoiding the problem of local minima. However, solving the corresponding SVM problems using the naive implementation of QP solver takesO(n3) computational time complexity and at least O(n2) space complexity if the number of training patterns is n. Obviously, the naive implementation of QP solver is difficult to meet the practical application of novelty detection in large scale datasets. Tsang et al. proposed the core vector machine (CVM) [12, 13] as the approximation algorithm of minimum enclosing ball (MEB) for large scale problems. The key idea is that the implementation of QP solver for corresponding SVM problems could be equivalently viewed as MEB problems. By utilizing an approximation algorithm for the MEB problem in computational geometry, the time complexity of CVM algorithm is linear to the number of training patterns. Moreover, the space complexity is irrelevant to the number of training patterns.As mentioned above, only normal training patterns are used to build the detection model in most novelty detection algorithms. In practical applications of novelty detection, it is difficult, but not impossible, to obtain a very few abnormal training patterns. For instance, in machine fault detection, in addition to extensive measurements on the normal working conditions, there may be also some measurements on faulty situations [14]. Recently, extensive and comprehensive researches have been carried out in both academia and industry to solve the imbalanced novelty detection problem.Kernel-based novelty detection based on imbalanced data is researched in this paper. SupposeS=xi,yi, i=1,…,n, is a given training dataset with n examples, where xi⊂Rd is the ith input instance, yi∈-1,+1 is a class identity label associated with instance xi, Smaj⊂S is the set of majority training patterns and Smaj=m1, Smin⁡⊂S is the set of minority training patterns and Smin⁡=m2, and m1+m2=n. ϕ(·) is the feature mapping function defined by a given kernel function κ·,·. The length of the perpendicular projection of the training pattern ϕxi onto the vector v is expressed as v,ϕxi, which actually reflects the information about the angular and the Euclidean distances between v and ϕxi in the Euclidean vector space. According to the definition in [15], v,ϕxi is called vector-angular.In this paper, a large vector-angular region and margin (LARM) algorithm and its fast training method based on core set are proposed for novelty detection, where the training patterns are imbalanced. The main contributions of this paper lie in three aspects. Firstly, the boundary of SVM is only determined by the support vectors and the distribution of the data in the training set is not considered [16]. However, recent theoretical results have proved that data distribution information is crucial to the generalization performance [17, 18]. The proposed algorithm in this paper aims to find an optimal vector v in the feature space, in which the mean and the variance of vector-angular are maximized and minimized, respectively. Therefore, normal and abnormal examples are well separated when projected onto the optimal vector v joining their large mean and small variance. Secondly, the proposed LARM integrates one-class and binary classification algorithms to tackle the novelty detection problem based on imbalanced data, which constructs the largest vector-angular region in the feature space to separate normal training patterns and maximizes the vector-angular margin between the optimal vector-angular region and the abnormal data. Since the number of normal training patterns is sufficient, the largest vector-angular region is constructed accurately, which can minimize the chance of accepting the normal examples. To achieve better generalization performance, the vector-angular margin between the surface of this optimal vector-angular region and the abnormal data is maximized. Thirdly, the core set based LARM algorithm is proposed for fast training LARM problem. The time and space complexity of core set based LARM are linear to and independent of the number of training patterns, respectively.The structure of this paper is organized as follows. Section1 introduces the novelty detection technique and presents an analysis of the existing problems. Section 2 introduces ν-support vector machine (ν-SVM), two-class SVDD, and maximum vector-angular margin classifier (MAMC). Section 3 presents the proposed LARM for novelty detection and its fast training method based on core set. Experimental results are shown in Section 4 and conclusions are given in Section 5.


## 2.ν-SVM, SVDD, and MAMC

### 2.1.ν-SVM

ν-SVM was proposed by Schölkopf et al. [19] to solve the binary classification problem, which uses the parameter ν to control the number of support vectors and the bound of the classification errors. ν-SVM can be modeled as follows:(1)minw,ρ,b,ξ12w2-νρ+1n∑i=1nξis.t.yiwTϕxi+b≥ρ-ξi,i=1,…,nξi≥0,i=1,…,n,ρ>0,where w is the normal vector of the decision hyperplane, b is the bias of the classifier, ρ is the margin, ξ=[ξ1,…,ξn]T is the vector of slack variables, and ν is a positive constant. ν-SVM obtains the optimal hyperplane wTϕxi+b=0 for separating the two classes with a maximal margin ρ/2w. To classify a testing instance z∈Rd, the decision function takes the sign function of the optimal hyperplane f(z)=sgn⁡wTϕz+b.


### 2.2. SVDD

One-class SVDD and two-class SVDD were proposed by Tax and Duin in 2004 [7], in which the minimal ball is constructed to enclose most of the training patterns. Here, we only review two-class SVDD that can utilize the abnormal data. Two-class SVDD can be modeled as follows:(2)minR,c,ξR2+C1∑i=1m1ξi+C2∑j=m1+1nξjs.t.ϕxi-c2≤R2+ξi,i=1,…,m1ϕxj-c2≥R2-ξj,j=m1+1,…,nξk≥0,k=1,…,n,where R and c are the radius and the center of the hypersphere, C1 and C2 are two trade-off parameters which can treat imbalanced datasets, and ξ=[ξ1,…,ξn]T is the vector of slack variables. The testing instance z∈Rd can be determined, whether it is inside of the optimal hypersphere or not. Hence, the decision function of two-class SVDD is f(z)=sgn⁡R2-ϕz-c2.


### 2.3. MAMC

MAMC was proposed by Hu et al. in 2012 [15], which attempts to find an optimal vector v in the feature space based on the maximum vector-angular margin. MAMC can be modeled as follows:(3)minρ,v,ξ-νρ+1n∑i=1nϕxi-v2+Cn∑i=1nξis.t.yiϕxiTv≥ρ-ξi,i=1,…,nξi≥0,i=1,…,n,where v is the optimized vector, ρ is the vector-angular margin, ξ=[ξ1,…,ξn]T is the vector of slack variables, and C and ν are two positive constants. To classify a testing instance z∈Rd, the decision function is defined as f(z)=sgn⁡∑i=1n1/n+αiyi/2κxi,z.


## 2.1.ν-SVM

ν-SVM was proposed by Schölkopf et al. [19] to solve the binary classification problem, which uses the parameter ν to control the number of support vectors and the bound of the classification errors. ν-SVM can be modeled as follows:(1)minw,ρ,b,ξ12w2-νρ+1n∑i=1nξis.t.yiwTϕxi+b≥ρ-ξi,i=1,…,nξi≥0,i=1,…,n,ρ>0,where w is the normal vector of the decision hyperplane, b is the bias of the classifier, ρ is the margin, ξ=[ξ1,…,ξn]T is the vector of slack variables, and ν is a positive constant. ν-SVM obtains the optimal hyperplane wTϕxi+b=0 for separating the two classes with a maximal margin ρ/2w. To classify a testing instance z∈Rd, the decision function takes the sign function of the optimal hyperplane f(z)=sgn⁡wTϕz+b.


## 2.2. SVDD

One-class SVDD and two-class SVDD were proposed by Tax and Duin in 2004 [7], in which the minimal ball is constructed to enclose most of the training patterns. Here, we only review two-class SVDD that can utilize the abnormal data. Two-class SVDD can be modeled as follows:(2)minR,c,ξR2+C1∑i=1m1ξi+C2∑j=m1+1nξjs.t.ϕxi-c2≤R2+ξi,i=1,…,m1ϕxj-c2≥R2-ξj,j=m1+1,…,nξk≥0,k=1,…,n,where R and c are the radius and the center of the hypersphere, C1 and C2 are two trade-off parameters which can treat imbalanced datasets, and ξ=[ξ1,…,ξn]T is the vector of slack variables. The testing instance z∈Rd can be determined, whether it is inside of the optimal hypersphere or not. Hence, the decision function of two-class SVDD is f(z)=sgn⁡R2-ϕz-c2.


## 2.3. MAMC

MAMC was proposed by Hu et al. in 2012 [15], which attempts to find an optimal vector v in the feature space based on the maximum vector-angular margin. MAMC can be modeled as follows:(3)minρ,v,ξ-νρ+1n∑i=1nϕxi-v2+Cn∑i=1nξis.t.yiϕxiTv≥ρ-ξi,i=1,…,nξi≥0,i=1,…,n,where v is the optimized vector, ρ is the vector-angular margin, ξ=[ξ1,…,ξn]T is the vector of slack variables, and C and ν are two positive constants. To classify a testing instance z∈Rd, the decision function is defined as f(z)=sgn⁡∑i=1n1/n+αiyi/2κxi,z.


## 3. Core Set Based Large Vector-Angular Region and Margin

In this section, LARM algorithm and its fast training method based on core set are proposed for novelty detection with imbalanced data.


### 3.1. LARM

To tackle the novelty detection problem on imbalanced data, the distribution of vector-angular and maximization of vector-angular margin are considered in this paper. Figure1 illustrates the principle of LARM.Figure 1
The schematic illustration of LARM principle.Firstly, LARM is adopted to find an optimal vectorv in the feature space, which attempts to maximize the vector-angular mean and minimize the vector-angular variance simultaneously. Here, the vector-angular expresses the length of projection of training pattern ϕxi onto the optimal vector v. Therefore, the normal and abnormal examples are well separated when projected onto the optimal vector v joining their large mean and small variance.Secondly, for the learning problem on imbalanced data, the largest vector-angular region in the feature space is constructed to separate the normal data. Since the number of normal training patterns is sufficient, the largest vector-angular region is constructed accurately, which can minimize the chances of accepting the normal examples. Meanwhile, to achieve a favorable generalization performance, the vector-angular margin between the surface of this optimal vector-angular region and the abnormal data is maximized.


#### 3.1.1. Primal Formulation of LARM

Formally, define the training pattern matrixX=[ϕ(x1),…,ϕ(xn)], label column vector y=[y1,…,yn]T, and label diagonal matrix Y=diag⁡(y1,…,yn). According to the definition in [18], the vector-angular mean γ- and vector-angular variance γ^ between training patterns ϕ(xi),yi, i=1,…,n and vector v can be expressed as(4)γ-=1n∑i=1nyivTϕxi=1nXyTv,γ^=1n2∑i=1n∑j=1nyivTϕxi-yjvTϕxj2=2n2nvTXXTv-vTXyyTXTv.Then, the primal LARM can be formulated as the following optimization problem:(5)min⁡ω,ρ,v,ξ-ω2-νρ2+2λn2nvTXXTv-vTXyyTXTv-λnXyTv+1ν1m1∑i=1m1ξi+1ν2m2∑j=m1+1nξjs.t.vTϕxi≥ω2-ξi,i=1,…,m1vTϕxj≤ω2-ρ2+ξj,j=m1+1,…,nξi≥0,i=1,…,n,where v is the optimal vector, ω2(ω>0) is the width of vector-angular region, ρ2(ρ>0) is the vector-angular margin, ξ=[ξ1,…,ξn]T is the vector of slack variables, and ν, ν1, ν2, and λ are four positive constants.According to [18], v∗ for problem (5) is expressed as follows:(6)v∗=∑i=1nαiϕxi=Xα.Hence,XTv=XTXα=Kα can be obtained, where K=XTX is the kernel matrix. Problem (5) can be formulated as follows:(7)minω,ρ,α,ξ-ω2-νρ2+12αTQα+qTα+1ν1m1∑i=1m1ξi+1ν2m2∑j=m1+1nξjs.t.αTK:i≥ω2-ξi,i=1,…,m1αTK:j≤ω2-ρ2+ξj,j=m1+1,…,nξi≥0,i=1,…,n,where Q=4λ(nKTK-(Ky)(Ky)T)/n2, q=-λ(Ky)/n, and K:i is the ith column of K.


#### 3.1.2. Dual Problem

To investigate the problem with constraints described as (7), the Lagrangian function is constructed as follows:(8)Lω,ρ,α,ξ,β,η=-ω2-νρ2+12αTQα+qTα+1ν1m1∑i=1m1ξi+1ν2m2∑j=m1+1nξj-∑i=1m1βiαTK:i-ω2+ξi+∑j=m1+1nβjαTK:j-ω2+ρ2-ξj-∑i=1nηiξi,where β=[β1,…,βn]T and η=[η1,…,ηn]T are Lagrange multipliers. The following equations can be obtained by making the partial derivatives of Lω,ρ,α,ξ,β,η with respect to the primal variables to zero:(9)∂L∂ω=0⟹-2ω+2ω∑i=1m1βi-2ω∑j=m1+1nβj=0⟹2ω-1+∑i=1nβiyi=0(10)∂L∂ρ=0⟹-2νρ+2ρ∑j=m1+1nβj=0⟹2ρ∑j=m1+1nβj-ν=0(11)∂L∂ξi=0⟹1ν1m1-βi-ηi=0,i=1,…,m1(12)∂L∂ξj=0⟹1ν2m2-βj-ηj=0,j=m1+1,…,n(13)∂L∂α=0⟹Qα+q-∑i=1m1βiK:i+∑j=m1+1nβjK:j=0⟹Qα+q-∑i=1nβiyiK:i=0.Substituting (9)–(13) into (8), the dual form can be obtained, which omits constants without influence on optimization:(14)maxβ-12βTHβ+pTβs.t.0≤βi≤1ν1m1,i=1,…,m10≤βi≤1ν2m2,i=m1+1,…,n∑i=1nβiyi=1∑i=1nβi=1+2ν,where H=YKQ-1KY, p=-λ(He)/n, and Q-1 is the inverse matrix of Q and e=[1,…,1]T.The dual problem (14) is a QP problem, which has the same form as the dual of the ν-SVM [19, 20]. Therefore, the QP problem (14) can be easily solved by SMO algorithm in LIBSVM [21].Supposeβ∗ is the optimal vector of the dual problem (14). According to (13), α∗ can be expressed as follows:(15)α∗=Q-1∑i=1nβi∗yiΚ:i-q=Q-1ΚYβ∗-q.To computeω2 and ρ2, two sets are considered:(16)S1=0<βi<1ν1m1,i=1,…,m1,S2=0<βj<1ν2m2,j=m1+1,…,n.According to the Karush-Kuhn-Tucker (KKT) conditions(17)βivTϕxi-ω2+ξi=0,i=1,…,m1,βjvTϕxj-ω2+ρ2-ξi=0,j=m1+1,…,n,ηiξi=0,i=1,…,n,and (11) and (12), ηi>0, ξi=0, ηj>0, and ξj=0 can be obtained. Hence, set n1=|S1| and n2=|S2|, and ω2 and ρ2 can be expressed as(18)ω2=1n1∑xi∈S1vTϕxi=1n1∑xi∈S1∑k=1nαk∗ϕxkTϕxi=1n1∑xi∈S1∑k=1nαk∗κxi,xk,ρ2=1n1∑xi∈S1vTϕxi-1n2∑xj∈S2vTϕxj=1n1∑xi∈S1∑k=1nαk∗ϕxkTϕxi-1n2∑xj∈S2∑k=1nαk∗ϕxkTϕxj=1n1∑xi∈S1∑k=1nαk∗κxi,xk-1n2∑xj∈S2∑k=1nαk∗κxj,xk.


#### 3.1.3. Decision Function

It can be seen that minimizing the cost function (5) will make the width of vector-angular region ω2 and vector-angular margin ρ2 as large as possible. Meanwhile, the optimal vector v in feature space is found, which makes the normal and abnormal examples well separated when projected onto the optimal vector v joining their large mean and small variance. Therefore, the testing patterns can be classified in terms of the vector-angular between the vector v and the training patterns ϕx. The optimal separating hyperplane of SVM is wTϕx+b=0, which is at the middle of the margin. Similarly, the separating hyperplane of LARM is defined at the center of the margin. Hence, for testing instance z∈Rd, the decision function is expressed as follows:(19)fz=sgn⁡vTϕz-ω2+ρ22=sgn⁡∑i=1nαi∗κxi,z-ω2+ρ22.


#### 3.1.4.ν-Property

Letm+ and m- represent the number of margin errors of the normal and abnormal training patterns and s+ and s- denote the number of support vectors of the normal and abnormal training patterns, respectively. According to (9) and (10), the following formulas can be obtained:(20)∑i=1m1βi=ν+1,∑j=m1+1nβj=ν.By using similar proof aboutν-property in [19] and by making use of (20), inequalities (21) can be obtained:(21)m+m1≤ν1ν+1≤s+m1,m-m2≤ν2ν≤s-m2.The inequalities (21) indicate that ν1ν+1 (or ν2ν) is a lower bound of the fraction of support vectors in the normal (or abnormal) dataset and an upper bound of the fraction of misclassified patterns in the normal (or abnormal) dataset. The ν-property of LARM can be used for parameter selection in the following experiments.


### 3.2. Core Set Based LARM

As mentioned above, the dual problem of LARM can be actually formulated as a QP problem. So, solving the corresponding QP problem of LARM takesO(n3) computational time complexity and O(n2) space complexity. When the number of training patterns is large, it is thus computationally infeasible. Inspired from the core set based approximate MEB algorithms, (1+ε) and (1-ε)-approximation algorithm is utilized for fast training LARM problem, which is called core set based LARM. Firstly, core sets of training patterns are obtained by (1+ε) and (1-ε)-approximation algorithm to achieve the distribution of vector-angular region of the normal and abnormal examples. The core set is a subset of the original training patterns and the optimization problem can be approximately solved on the core set. Secondly, the LARM problem is solved by SMO algorithm [22] using the obtained core set. According to [12, 13], the number of core sets is independent of both the number and the dimension of training patterns, and the time complexity is linear to the number of training patterns while the space complexity is independent of the number of training patterns. The schematic illustration of core set based LARM is shown in Figure 2.Figure 2
Schematic illustration of core set based LARM.SupposeSt is the core set of the tth iteration, vt is the optimal vector in the feature space of the tth iteration, ϖ˘t is the minimum distance between the center of the vector-angular margin and any point in core set of the tth iteration, and ϖ⌢t is the maximum distance between the center of the vector-angular margin and any point in core set of the tth iteration. Given ε>0, according to [12, 13], the core set based LARM is trained as follows.(i)
InitializeS0, ε, ϖ˘0 and ϖ⌢0.(ii)
Terminate if there is no training pointϕz falls outside the vector-angular region [(1-ε)×ϖ˘t,(1+ε)×ϖ⌢t]. Go to step (vi).(iii)
Findza and zb; vtTϕ(za) is the furthest away from the center of the vector-angular margin and vtTϕ(zb) is the shortest away from the center of the vector-angular margin. Set St+1=St∪{za,zb}.The distance between the center of the vector-angular margin and any pointϕ(zl) is expressed as follows:(22)ϖt=vtTϕzl-ωt2+ρt22=∑zi∈StStαi∗κzi,zl-ωt2+ρt22,where ωt2 is the width of vector-angular region at the tth iteration, ρt2 is the vector-angular margin at the tth iteration, and the set {zl} is constructed by all training patterns outside the vector-angular region [(1-ε)×ϖ˘t,(1+ε)×ϖ⌢t].Computing (22) for all n training patterns, takes O(|St|2+n|St|)=O(n|St|) time at the tth iteration. When n is large, time cost will be enormous. In order to reduce the computation cost, the probabilistic speedup method [23] is used to accelerate the vector-angular computations in steps (ii) and (iii). The details of time and space complexities can be seen in [12, 13].(iv)
Find the new vector-angular region[(1-ε)×ϖ˘t+1,(1+ε)×ϖ⌢t+1].(v)
Increaset by 1 and go back to step (ii).(vi)
Solve the LARM problem (14) by the core set St.(vii)
Classify the test pattern by the decision function (19).


## 3.1. LARM

To tackle the novelty detection problem on imbalanced data, the distribution of vector-angular and maximization of vector-angular margin are considered in this paper. Figure1 illustrates the principle of LARM.Figure 1
The schematic illustration of LARM principle.Firstly, LARM is adopted to find an optimal vectorv in the feature space, which attempts to maximize the vector-angular mean and minimize the vector-angular variance simultaneously. Here, the vector-angular expresses the length of projection of training pattern ϕxi onto the optimal vector v. Therefore, the normal and abnormal examples are well separated when projected onto the optimal vector v joining their large mean and small variance.Secondly, for the learning problem on imbalanced data, the largest vector-angular region in the feature space is constructed to separate the normal data. Since the number of normal training patterns is sufficient, the largest vector-angular region is constructed accurately, which can minimize the chances of accepting the normal examples. Meanwhile, to achieve a favorable generalization performance, the vector-angular margin between the surface of this optimal vector-angular region and the abnormal data is maximized.


### 3.1.1. Primal Formulation of LARM

Formally, define the training pattern matrixX=[ϕ(x1),…,ϕ(xn)], label column vector y=[y1,…,yn]T, and label diagonal matrix Y=diag⁡(y1,…,yn). According to the definition in [18], the vector-angular mean γ- and vector-angular variance γ^ between training patterns ϕ(xi),yi, i=1,…,n and vector v can be expressed as(4)γ-=1n∑i=1nyivTϕxi=1nXyTv,γ^=1n2∑i=1n∑j=1nyivTϕxi-yjvTϕxj2=2n2nvTXXTv-vTXyyTXTv.Then, the primal LARM can be formulated as the following optimization problem:(5)min⁡ω,ρ,v,ξ-ω2-νρ2+2λn2nvTXXTv-vTXyyTXTv-λnXyTv+1ν1m1∑i=1m1ξi+1ν2m2∑j=m1+1nξjs.t.vTϕxi≥ω2-ξi,i=1,…,m1vTϕxj≤ω2-ρ2+ξj,j=m1+1,…,nξi≥0,i=1,…,n,where v is the optimal vector, ω2(ω>0) is the width of vector-angular region, ρ2(ρ>0) is the vector-angular margin, ξ=[ξ1,…,ξn]T is the vector of slack variables, and ν, ν1, ν2, and λ are four positive constants.According to [18], v∗ for problem (5) is expressed as follows:(6)v∗=∑i=1nαiϕxi=Xα.Hence,XTv=XTXα=Kα can be obtained, where K=XTX is the kernel matrix. Problem (5) can be formulated as follows:(7)minω,ρ,α,ξ-ω2-νρ2+12αTQα+qTα+1ν1m1∑i=1m1ξi+1ν2m2∑j=m1+1nξjs.t.αTK:i≥ω2-ξi,i=1,…,m1αTK:j≤ω2-ρ2+ξj,j=m1+1,…,nξi≥0,i=1,…,n,where Q=4λ(nKTK-(Ky)(Ky)T)/n2, q=-λ(Ky)/n, and K:i is the ith column of K.


### 3.1.2. Dual Problem

To investigate the problem with constraints described as (7), the Lagrangian function is constructed as follows:(8)Lω,ρ,α,ξ,β,η=-ω2-νρ2+12αTQα+qTα+1ν1m1∑i=1m1ξi+1ν2m2∑j=m1+1nξj-∑i=1m1βiαTK:i-ω2+ξi+∑j=m1+1nβjαTK:j-ω2+ρ2-ξj-∑i=1nηiξi,where β=[β1,…,βn]T and η=[η1,…,ηn]T are Lagrange multipliers. The following equations can be obtained by making the partial derivatives of Lω,ρ,α,ξ,β,η with respect to the primal variables to zero:(9)∂L∂ω=0⟹-2ω+2ω∑i=1m1βi-2ω∑j=m1+1nβj=0⟹2ω-1+∑i=1nβiyi=0(10)∂L∂ρ=0⟹-2νρ+2ρ∑j=m1+1nβj=0⟹2ρ∑j=m1+1nβj-ν=0(11)∂L∂ξi=0⟹1ν1m1-βi-ηi=0,i=1,…,m1(12)∂L∂ξj=0⟹1ν2m2-βj-ηj=0,j=m1+1,…,n(13)∂L∂α=0⟹Qα+q-∑i=1m1βiK:i+∑j=m1+1nβjK:j=0⟹Qα+q-∑i=1nβiyiK:i=0.Substituting (9)–(13) into (8), the dual form can be obtained, which omits constants without influence on optimization:(14)maxβ-12βTHβ+pTβs.t.0≤βi≤1ν1m1,i=1,…,m10≤βi≤1ν2m2,i=m1+1,…,n∑i=1nβiyi=1∑i=1nβi=1+2ν,where H=YKQ-1KY, p=-λ(He)/n, and Q-1 is the inverse matrix of Q and e=[1,…,1]T.The dual problem (14) is a QP problem, which has the same form as the dual of the ν-SVM [19, 20]. Therefore, the QP problem (14) can be easily solved by SMO algorithm in LIBSVM [21].Supposeβ∗ is the optimal vector of the dual problem (14). According to (13), α∗ can be expressed as follows:(15)α∗=Q-1∑i=1nβi∗yiΚ:i-q=Q-1ΚYβ∗-q.To computeω2 and ρ2, two sets are considered:(16)S1=0<βi<1ν1m1,i=1,…,m1,S2=0<βj<1ν2m2,j=m1+1,…,n.According to the Karush-Kuhn-Tucker (KKT) conditions(17)βivTϕxi-ω2+ξi=0,i=1,…,m1,βjvTϕxj-ω2+ρ2-ξi=0,j=m1+1,…,n,ηiξi=0,i=1,…,n,and (11) and (12), ηi>0, ξi=0, ηj>0, and ξj=0 can be obtained. Hence, set n1=|S1| and n2=|S2|, and ω2 and ρ2 can be expressed as(18)ω2=1n1∑xi∈S1vTϕxi=1n1∑xi∈S1∑k=1nαk∗ϕxkTϕxi=1n1∑xi∈S1∑k=1nαk∗κxi,xk,ρ2=1n1∑xi∈S1vTϕxi-1n2∑xj∈S2vTϕxj=1n1∑xi∈S1∑k=1nαk∗ϕxkTϕxi-1n2∑xj∈S2∑k=1nαk∗ϕxkTϕxj=1n1∑xi∈S1∑k=1nαk∗κxi,xk-1n2∑xj∈S2∑k=1nαk∗κxj,xk.


### 3.1.3. Decision Function

It can be seen that minimizing the cost function (5) will make the width of vector-angular region ω2 and vector-angular margin ρ2 as large as possible. Meanwhile, the optimal vector v in feature space is found, which makes the normal and abnormal examples well separated when projected onto the optimal vector v joining their large mean and small variance. Therefore, the testing patterns can be classified in terms of the vector-angular between the vector v and the training patterns ϕx. The optimal separating hyperplane of SVM is wTϕx+b=0, which is at the middle of the margin. Similarly, the separating hyperplane of LARM is defined at the center of the margin. Hence, for testing instance z∈Rd, the decision function is expressed as follows:(19)fz=sgn⁡vTϕz-ω2+ρ22=sgn⁡∑i=1nαi∗κxi,z-ω2+ρ22.


### 3.1.4.ν-Property

Letm+ and m- represent the number of margin errors of the normal and abnormal training patterns and s+ and s- denote the number of support vectors of the normal and abnormal training patterns, respectively. According to (9) and (10), the following formulas can be obtained:(20)∑i=1m1βi=ν+1,∑j=m1+1nβj=ν.By using similar proof aboutν-property in [19] and by making use of (20), inequalities (21) can be obtained:(21)m+m1≤ν1ν+1≤s+m1,m-m2≤ν2ν≤s-m2.The inequalities (21) indicate that ν1ν+1 (or ν2ν) is a lower bound of the fraction of support vectors in the normal (or abnormal) dataset and an upper bound of the fraction of misclassified patterns in the normal (or abnormal) dataset. The ν-property of LARM can be used for parameter selection in the following experiments.


## 3.1.1. Primal Formulation of LARM

Formally, define the training pattern matrixX=[ϕ(x1),…,ϕ(xn)], label column vector y=[y1,…,yn]T, and label diagonal matrix Y=diag⁡(y1,…,yn). According to the definition in [18], the vector-angular mean γ- and vector-angular variance γ^ between training patterns ϕ(xi),yi, i=1,…,n and vector v can be expressed as(4)γ-=1n∑i=1nyivTϕxi=1nXyTv,γ^=1n2∑i=1n∑j=1nyivTϕxi-yjvTϕxj2=2n2nvTXXTv-vTXyyTXTv.Then, the primal LARM can be formulated as the following optimization problem:(5)min⁡ω,ρ,v,ξ-ω2-νρ2+2λn2nvTXXTv-vTXyyTXTv-λnXyTv+1ν1m1∑i=1m1ξi+1ν2m2∑j=m1+1nξjs.t.vTϕxi≥ω2-ξi,i=1,…,m1vTϕxj≤ω2-ρ2+ξj,j=m1+1,…,nξi≥0,i=1,…,n,where v is the optimal vector, ω2(ω>0) is the width of vector-angular region, ρ2(ρ>0) is the vector-angular margin, ξ=[ξ1,…,ξn]T is the vector of slack variables, and ν, ν1, ν2, and λ are four positive constants.According to [18], v∗ for problem (5) is expressed as follows:(6)v∗=∑i=1nαiϕxi=Xα.Hence,XTv=XTXα=Kα can be obtained, where K=XTX is the kernel matrix. Problem (5) can be formulated as follows:(7)minω,ρ,α,ξ-ω2-νρ2+12αTQα+qTα+1ν1m1∑i=1m1ξi+1ν2m2∑j=m1+1nξjs.t.αTK:i≥ω2-ξi,i=1,…,m1αTK:j≤ω2-ρ2+ξj,j=m1+1,…,nξi≥0,i=1,…,n,where Q=4λ(nKTK-(Ky)(Ky)T)/n2, q=-λ(Ky)/n, and K:i is the ith column of K.


## 3.1.2. Dual Problem

To investigate the problem with constraints described as (7), the Lagrangian function is constructed as follows:(8)Lω,ρ,α,ξ,β,η=-ω2-νρ2+12αTQα+qTα+1ν1m1∑i=1m1ξi+1ν2m2∑j=m1+1nξj-∑i=1m1βiαTK:i-ω2+ξi+∑j=m1+1nβjαTK:j-ω2+ρ2-ξj-∑i=1nηiξi,where β=[β1,…,βn]T and η=[η1,…,ηn]T are Lagrange multipliers. The following equations can be obtained by making the partial derivatives of Lω,ρ,α,ξ,β,η with respect to the primal variables to zero:(9)∂L∂ω=0⟹-2ω+2ω∑i=1m1βi-2ω∑j=m1+1nβj=0⟹2ω-1+∑i=1nβiyi=0(10)∂L∂ρ=0⟹-2νρ+2ρ∑j=m1+1nβj=0⟹2ρ∑j=m1+1nβj-ν=0(11)∂L∂ξi=0⟹1ν1m1-βi-ηi=0,i=1,…,m1(12)∂L∂ξj=0⟹1ν2m2-βj-ηj=0,j=m1+1,…,n(13)∂L∂α=0⟹Qα+q-∑i=1m1βiK:i+∑j=m1+1nβjK:j=0⟹Qα+q-∑i=1nβiyiK:i=0.Substituting (9)–(13) into (8), the dual form can be obtained, which omits constants without influence on optimization:(14)maxβ-12βTHβ+pTβs.t.0≤βi≤1ν1m1,i=1,…,m10≤βi≤1ν2m2,i=m1+1,…,n∑i=1nβiyi=1∑i=1nβi=1+2ν,where H=YKQ-1KY, p=-λ(He)/n, and Q-1 is the inverse matrix of Q and e=[1,…,1]T.The dual problem (14) is a QP problem, which has the same form as the dual of the ν-SVM [19, 20]. Therefore, the QP problem (14) can be easily solved by SMO algorithm in LIBSVM [21].Supposeβ∗ is the optimal vector of the dual problem (14). According to (13), α∗ can be expressed as follows:(15)α∗=Q-1∑i=1nβi∗yiΚ:i-q=Q-1ΚYβ∗-q.To computeω2 and ρ2, two sets are considered:(16)S1=0<βi<1ν1m1,i=1,…,m1,S2=0<βj<1ν2m2,j=m1+1,…,n.According to the Karush-Kuhn-Tucker (KKT) conditions(17)βivTϕxi-ω2+ξi=0,i=1,…,m1,βjvTϕxj-ω2+ρ2-ξi=0,j=m1+1,…,n,ηiξi=0,i=1,…,n,and (11) and (12), ηi>0, ξi=0, ηj>0, and ξj=0 can be obtained. Hence, set n1=|S1| and n2=|S2|, and ω2 and ρ2 can be expressed as(18)ω2=1n1∑xi∈S1vTϕxi=1n1∑xi∈S1∑k=1nαk∗ϕxkTϕxi=1n1∑xi∈S1∑k=1nαk∗κxi,xk,ρ2=1n1∑xi∈S1vTϕxi-1n2∑xj∈S2vTϕxj=1n1∑xi∈S1∑k=1nαk∗ϕxkTϕxi-1n2∑xj∈S2∑k=1nαk∗ϕxkTϕxj=1n1∑xi∈S1∑k=1nαk∗κxi,xk-1n2∑xj∈S2∑k=1nαk∗κxj,xk.


## 3.1.3. Decision Function

It can be seen that minimizing the cost function (5) will make the width of vector-angular region ω2 and vector-angular margin ρ2 as large as possible. Meanwhile, the optimal vector v in feature space is found, which makes the normal and abnormal examples well separated when projected onto the optimal vector v joining their large mean and small variance. Therefore, the testing patterns can be classified in terms of the vector-angular between the vector v and the training patterns ϕx. The optimal separating hyperplane of SVM is wTϕx+b=0, which is at the middle of the margin. Similarly, the separating hyperplane of LARM is defined at the center of the margin. Hence, for testing instance z∈Rd, the decision function is expressed as follows:(19)fz=sgn⁡vTϕz-ω2+ρ22=sgn⁡∑i=1nαi∗κxi,z-ω2+ρ22.


## 3.1.4.ν-Property

Letm+ and m- represent the number of margin errors of the normal and abnormal training patterns and s+ and s- denote the number of support vectors of the normal and abnormal training patterns, respectively. According to (9) and (10), the following formulas can be obtained:(20)∑i=1m1βi=ν+1,∑j=m1+1nβj=ν.By using similar proof aboutν-property in [19] and by making use of (20), inequalities (21) can be obtained:(21)m+m1≤ν1ν+1≤s+m1,m-m2≤ν2ν≤s-m2.The inequalities (21) indicate that ν1ν+1 (or ν2ν) is a lower bound of the fraction of support vectors in the normal (or abnormal) dataset and an upper bound of the fraction of misclassified patterns in the normal (or abnormal) dataset. The ν-property of LARM can be used for parameter selection in the following experiments.


## 3.2. Core Set Based LARM

As mentioned above, the dual problem of LARM can be actually formulated as a QP problem. So, solving the corresponding QP problem of LARM takesO(n3) computational time complexity and O(n2) space complexity. When the number of training patterns is large, it is thus computationally infeasible. Inspired from the core set based approximate MEB algorithms, (1+ε) and (1-ε)-approximation algorithm is utilized for fast training LARM problem, which is called core set based LARM. Firstly, core sets of training patterns are obtained by (1+ε) and (1-ε)-approximation algorithm to achieve the distribution of vector-angular region of the normal and abnormal examples. The core set is a subset of the original training patterns and the optimization problem can be approximately solved on the core set. Secondly, the LARM problem is solved by SMO algorithm [22] using the obtained core set. According to [12, 13], the number of core sets is independent of both the number and the dimension of training patterns, and the time complexity is linear to the number of training patterns while the space complexity is independent of the number of training patterns. The schematic illustration of core set based LARM is shown in Figure 2.Figure 2
Schematic illustration of core set based LARM.SupposeSt is the core set of the tth iteration, vt is the optimal vector in the feature space of the tth iteration, ϖ˘t is the minimum distance between the center of the vector-angular margin and any point in core set of the tth iteration, and ϖ⌢t is the maximum distance between the center of the vector-angular margin and any point in core set of the tth iteration. Given ε>0, according to [12, 13], the core set based LARM is trained as follows.(i)
InitializeS0, ε, ϖ˘0 and ϖ⌢0.(ii)
Terminate if there is no training pointϕz falls outside the vector-angular region [(1-ε)×ϖ˘t,(1+ε)×ϖ⌢t]. Go to step (vi).(iii)
Findza and zb; vtTϕ(za) is the furthest away from the center of the vector-angular margin and vtTϕ(zb) is the shortest away from the center of the vector-angular margin. Set St+1=St∪{za,zb}.The distance between the center of the vector-angular margin and any pointϕ(zl) is expressed as follows:(22)ϖt=vtTϕzl-ωt2+ρt22=∑zi∈StStαi∗κzi,zl-ωt2+ρt22,where ωt2 is the width of vector-angular region at the tth iteration, ρt2 is the vector-angular margin at the tth iteration, and the set {zl} is constructed by all training patterns outside the vector-angular region [(1-ε)×ϖ˘t,(1+ε)×ϖ⌢t].Computing (22) for all n training patterns, takes O(|St|2+n|St|)=O(n|St|) time at the tth iteration. When n is large, time cost will be enormous. In order to reduce the computation cost, the probabilistic speedup method [23] is used to accelerate the vector-angular computations in steps (ii) and (iii). The details of time and space complexities can be seen in [12, 13].(iv)
Find the new vector-angular region[(1-ε)×ϖ˘t+1,(1+ε)×ϖ⌢t+1].(v)
Increaset by 1 and go back to step (ii).(vi)
Solve the LARM problem (14) by the core set St.(vii)
Classify the test pattern by the decision function (19).


## 4. Experimental Results

The proposed core set based LARM is evaluated on twenty datasets, including both LIBSVM datasets [24] and UCI datasets [25]. Details of the datasets are listed in Table 1, where d is the data dimension, #pos is the total number of normal patterns, #neg is the total number of abnormal patterns, m1 is the number of normal training patterns, and m2 is that of abnormal training patterns. The dataset size is ranged from 178 to more than 495,141, and the proportion of major and minor data is ranged from 10 : 1 to 1000 : 1. Experiments are repeated for 10 times with random data partitions, the geometric mean accuracy and the standard deviation are recorded.Table 1
Datasets used in experiments.
Dataset
#pos
#neg
m
1
m
2
d
Australian
383
307
192
11
14
Banknote authentication (B. authentication)
762
610
381
19
4
Breast Cancer (B. Cancer)
458
241
229
22
9
Cod-rna
39690
19845
19845
99
8
Covtype
283301
211840
141651
141
54
Diabetic
611
540
306
15
19
Fourclass
307
555
154
7
2
Glass
144
70
72
7
11
Heart
120
150
60
6
13
Hill valley with noise (H. valley)
299
307
150
15
100
Ionosphere
225
126
113
5
34
Liver disorders (L. disorders)
200
145
100
10
6
Magic gamma telescope (MC)
12332
6688
6166
12
10
Sensorless drive diagnosis (SDD)
5319
53190
2660
26
48
Skin segmentation (S. segmentation)
194198
50859
97099
97
3
Sonar
111
97
56
5
60
Shuttle
34108
9392
17054
17
9
Svmguide1
2000
2000
1000
10
4
Wilt
4265
74
2133
10
5
Wine
119
59
84
8
13


### 4.1. Performance Measurement and Parameter Selection

The performance of core set based LARM is compared with three kernel-based algorithms:ν-SVM, SVDD, and MAMC. The geometric mean accuracy g=(a+·a-)1/2 [26] is used for both parameter selection and algorithm evaluation, where a+ is the classification accuracy of the positive class and a- is the classification accuracy of the negative class. The measurement is widely applied in imbalanced data [14, 26, 27], and it considers the classification results on both the positive and the negative classes. To make the experimental results persuasive enough, all the parameters of ν-SVM, SVDD, MAMC, and core set based LARM are selected by fivefold cross validation.In all experiments, the Radial Basis Function (RBF) is taken as the kernel function:(23)κxi,xj=exp-γxi-xj2,0<γ<+∞,where γ is the kernel parameter of the RBF. For all the algorithms, RBF parameter γ is calculated by [12, 13](24)γ=n-1∑i=1ndiag⁡K--1/n∑i=1n∑j=1nK-i,j,where K-i,j=xiTxj and diag⁡(K-) is the diagonal elements of matrix K-.Forν-SVM, parameter ν is searched in {0.1k,0.01k,0.001k,0.0001k}, where k=1,3,5,7,9.For SVDD, parameterC1 is searched in {0.01,0.05,0.1,0.5,1,5,10,50,100,500} and parameter C2 is searched by the ratio C2/C1 belonging to m1/4m2,m1/2m2,m1/m2,2m1/m2,4m1/m2.For MAMC, parameterC is searched in {10,30,50,70,90} and parameter ν is searched in {2,5,7,9,20,50,70,90}.For core set based LARM, parameterν is searched in {10,30,50,70,90} and parameters ν1 and ν2 are searched in {0.001,0.01}. From (21), ν1ν+1∈[0.01,0.9] and νν2∈[0.01,0.9] can be achieved, which are most associated with the percentage of support vectors and margin errors. From Section 4.2, we can see that parameters λ and ε have faint effect on the accuracy rate. Therefore, parameters λ and ε are set to 1 and 10-5, respectively.


### 4.2. Parameters Influence

There are five parameters in core set based LARM, that is,ν, ν1, ν2, λ, and ε. To verify the influence of the parameters on the performance of core set based LARM, experiments on some representative datasets are performed. By fixing other parameters, the influence of every parameter on some representative datasets is further studied, which is shown in Figures 3–7.Figure 3
Influence of parameterν on geometric mean accuracy and the number of core sets.
(a)
Influence ofν on geometric mean accuracy
(b)
Influence ofν on the number of core setsFigure 4
Influence of parameterν1 on geometric mean accuracy and the number of core sets.
(a)
Influence ofν1 on geometric mean accuracy
(b)
Influence ofν1 on the number of core setsFigure 5
Influence of parameterν2 on geometric mean accuracy and the number of core sets.
(a)
Influence ofν2 on geometric mean accuracy
(b)
Influence ofν2 on the number of core setsFigure 6
Influence of parameterλ on geometric mean accuracy and the number of core sets.
(a)
Influence ofλ on geometric mean accuracy
(b)
Influence ofλ on the number of core setsFigure 7
Influence of parameterε on geometric mean accuracy and the number of core sets.
(a)
Influence ofε on geometric mean accuracy
(b)
Influence ofε on the number of core setsFigure3 shows the influence of ν on the geometric mean accuracy and the number of core sets by varying ν from 10 to 100 while fixing ν1, ν2, λ, and ε as the suggested value obtained by the cross validation described in Section 4.1. Figure 4 shows the influence of ν1 on the geometric mean accuracy and the number of core sets by varying ν1 from 0.001 to 0.01 while fixing ν, ν2, λ, and ε in the same way. Figure 5 shows the influence of ν2 on the geometric mean accuracy and the number of core sets by varying ν2 from 0.001 to 0.01 while fixing ν, ν1, λ, and ε in the same way. Figure 6 shows the influence of λ on the geometric mean accuracy and the number of core sets by varying λ from 2-9 to 20 while fixing ν, ν1, ν2, and ε in the same way. Figure 7 shows the influence of ε on the geometric mean accuracy and the number of core sets by varying ε from 1e-9 to 1e-2 while fixing ν, ν1, ν2, and λ in the same way.From Figures3–7, it can be seen that parameters ν, ν1, ν2, λ, and ε have faint effect on the geometric mean accuracy and the number of core sets, which make the core set based LARM even more attractive in practice. Therefore, parameters ν, ν1, ν2, λ, and ε obtained by the cross validation described in Section 4.1 are acceptable for all experiments.


### 4.3. Numerical Results

#### 4.3.1. Detection Performance

For each dataset, samples are randomly split into training patterns and testing patterns with the proportion described in Table1. Parameters of ν-SVM, SVDD, MAMC, and core set based LARM are selected by fivefold cross validation to make the experimental results persuasive enough.The geometric mean accuracy is used for the performance evaluation. Experiments are repeated for 10 times with random data partitions. The average accuracy and the standard deviation are listed in Table2. NULL shows that there is no return result in 10 hours. Furthermore, with regard to every dataset, the difference between the bold results and the best geometric mean accuracy is not significant, which is determined by the Wilcoxon rank-sum test, with the confidence level of 0.05.Table 2
Average geometric mean accuracy and standard deviation on datasets.
Dataset
ν-SVM (%)
SVDD (%)
MAMC (%)
Core set based LARM (%)
Australian
47.88 ± 14.46
56.03 ± 9.21
35.11 ± 10.36
63.67 ± 9.12
B. authentication
97.25 ± 1.66
98.60 ± 0.95
95.34 ± 3.65
98.60 ± 2.30
B. Cancer
92.38 ± 1.43
95.25 ± 0.89
92.75 ± 2.43
93.61 ± 3.53
Cod-rna
45.63 ± 15.18
NULL
NULL
75.46 ± 8.79
Covtype
NULL
NULL
NULL
57.51 ± 8.27
Diabetic
42.91 ± 9.34
52.26 ± 9.01
50.14 ± 8.54
53.50 ± 8.90
Fourclass
77.23 ± 7.34
81.74 ± 11.27
64.31 ± 13.04
81.97 ± 8.16
Glass
95.12 ± 4.27
80.78 ± 5.71
94.56 ± 4.47
96.56 ± 3.52
Heart
42.01 ± 14.10
52.23 ± 5.80
51.50 ± 10.84
54.29 ± 8.32
H. valley
43.05 ± 9.25
42.00 ± 10.79
35.76 ± 19.45
44.16 ± 2.34
Ionosphere
46.44 ± 16.10
66.54 ± 9.81
36.07 ± 16.80
71.17 ± 14.91
L. disorders
50.21 ± 5.83
54.72 ± 7.49
45.80 ± 6.58
58.55 ± 3.14
MC
20.46 ± 3.84
67.36 ± 3.87
41.57 ± 7.12
62.94 ± 5.46
SDD
40.26 ± 9.63
25.93 ± 9.54
20.64 ± 21.66
45.67 ± 10.30
S. segmentation
NULL
NULL
NULL
95.91 ± 1.92
Sonar
52.27 ± 8.87
31.39 ± 6.99
55.79 ± 11.36
46.37 ± 9.04
Shuttle
91.65 ± 5.49
40.23 ± 21.59
NULL
92.88 ± 4.11
Svmguide1
82.17 ± 6.91
90.21 ± 6.88
89.95 ± 4.18
91.83 ± 2.69
Wilt
82.14 ± 9.29
56.95 ± 15.52
64.76 ± 3.81
84.95 ± 13.94
Wine
82.32 ± 4.57
86.00 ± 6.95
87.19 ± 4.32
87.62 ± 1.97From Table2, it can be concluded that the performance of core set based LARM is comparable to the best of ν-SVM, SVDD, and MAMC on all datasets. The core set based LARM performs significantly better than ν-SVM, SVDD, and MAMC on 12, 9, and 13 over 20 datasets, respectively. It illustrates that, by using (1+ε) and (1-ε)-approximation algorithm for training LARM, the generalization performance of core set based LARM is comparable to or even better than the best of ν-SVM, SVDD, and MAMC.


#### 4.3.2. Time Cost

The time cost ofν-SVM, SVDD, MAMC, and core set based LARM on different datasets is shown in Tables 3 and 4. The average and standard deviation of training time (including parameters selection and model training time) are shown in Table 3. The average and standard deviation of testing time are shown in Table 4. All the experiments are conducted on the computer with an i5-2400@3.10 GHz CPU and 8 GB SDRAM. NULL shows that there is no return result in 10 hours. Furthermore, with regard to every dataset, the difference between the bold results and the best time cost is not significant, which is determined by the Wilcoxon rank-sum test, with the confidence level of 0.05.Table 3
Training time on different datasets.
Dataset
ν-SVM (s)
SVDD (s)
MAMC (s)
Core set based LARM (s)
Australian
0.0739 ± 0.0086
0.5975 ± 0.0993
0.6325 ± 0.0122
0.8819 ± 0.4613
B. authentication
0.1627 ± 0.0699
0.3441 ± 0.0199
1.3943 ± 0.0131
1.1103 ± 0.1658
B. Cancer
0.0975 ± 0.0063
0.2462 ± 0.0152
0.7309 ± 0.0126
2.2633 ± 0.2803
Cod-rna
388.7901 ± 24.6651
NULL
NULL
7.4578 ± 0.1622
Covtype
NULL
NULL
NULL
64.9519 ± 7.3727
Diabetic
0.2096 ± 0.0063
1.1188 ± 0.0819
1.9243 ± 0.0119
5.7415 ± 1.0748
Fourclass
0.0354 ± 0.0030
0.1271 ± 0.0151
0.2706 ± 0.0117
0.5652 ± 0.1175
Glass
0.0255 ± 0.0038
0.0587 ± 0.0038
0.1459 ± 0.0088
0.2079 ± 0.0220
Heart
0.0229 ± 0.0016
0.0858 ± 0.0082
0.1148 ± 0.0070
0.8305 ± 0.2195
H. valley
0.1457 ± 0.0119
1.0385 ± 0.0278
1.4355 ± 0.0164
0.8506 ± 0.2926
Ionosphere
0.0634 ± 0.0097
0.1999 ± 0.0134
0.4018 ± 0.0087
1.9758 ± 0.3947
L. disorders
0.0399 ± 0.0058
0.1861 ± 0.0202
0.1809 ± 0.0095
1.6280 ± 0.4039
MC
19.5417 ± 0.3331
49.0111 ± 10.8097
472.2837 ± 1.3679
17.1713 ± 5.3223
SDD
13.8246 ± 1.0316
145.7426 ± 18.0463
218.5634 ± 0.6386
8.3123 ± 0.5485
S. segmentation
NULL
NULL
NULL
7.2536 ± 0.3645
Sonar
0.0463 ± 0.0050
0.1406 ± 0.0061
0.1896 ± 0.0054
2.3453 ± 0.4481
Shuttle
226.0020 ± 3.1471
268.0641 ± 145.7989
NULL
7.3061 ± 0.2336
Svmguide1
0.4634 ± 0.0171
1.3081 ± 0.3742
8.9181 ± 0.0539
1.0625 ± 0.0781
Wilt
2.0750 ± 0.0774
8.6527 ± 0.7402
52.8582 ± 0.7763
3.6379 ± 0.3202
Wine
0.0263 ± 0.0049
0.0983 ± 0.0274
0.1785 ± 0.0111
0.2936 ± 0.0494Table 4
Testing time on different datasets.
Dataset
ν-SVM (s)
SVDD (s)
MAMC (s)
Core set based LARM (s)
Australian
0.0009 ± 0.0005
0.0035 ± 0.0014
0.0023 ± 0.0017
0.0013 ± 0.0004
B. authentication
0.0050 ± 0.0129
0.0010 ± 0.0004
0.0070 ± 0.0032
0.0018 ± 0.0012
B. Cancer
0.0011 ± 0.0003
0.0013 ± 0.0004
0.0032 ± 0.0012
0.0012 ± 0.0003
Cod-rna
0.2901 ± 0.2182
NULL
NULL
0.0584 ± 0.0085
Covtype
NULL
NULL
NULL
1.5096 ± 1.1866
Diabetic
0.0015 ± 0.0009
0.0054 ± 0.0016
0.0075 ± 0.0056
0.0029 ± 0.0010
Fourclass
0.0004 ± 0.0001
0.0006 ± 0.0002
0.0015 ± 0.0007
0.0007 ± 0.0002
Glass
0.0002 ± 0.0002
0.0002 ± 0.0001
0.0005 ± 0.0004
0.0004 ± 0.0003
Heart
0.0003 ± 0.0001
0.0005 ± 0.0001
0.0008 ± 0.0004
0.0007 ± 0.0004
H. valley
0.0021 ± 0.0013
0.0101 ± 0.0021
0.0050 ± 0.0032
0.0031 ± 0.0009
Ionosphere
0.0007 ± 0.0003
0.0016 ± 0.0008
0.0018 ± 0.0009
0.0011 ± 0.0003
L. disorders
0.0004 ± 0.0002
0.0006 ± 0.0002
0.0006 ± 0.0002
0.0006 ± 0.0003
MC
0.0282 ± 0.0073
0.6090 ± 0.3269
0.7920 ± 0.9542
0.0269 ± 0.0132
SDD
0.2947 ± 0.3511
9.4060 ± 3.3205
2.6391 ± 4.2971
0.1829 ± 0.0488
S. segmentation
NULL
NULL
NULL
0.1504 ± 0.0331
Sonar
0.0006 ± 0.0003
0.0011 ± 0.0003
0.0013 ± 0.0003
0.0010 ± 0.0004
Shuttle
0.0393 ± 0.0147
4.5419 ± 3.2784
NULL
0.0342 ± 0.0082
Svmguide1
0.0027 ± 0.0009
0.0031 ± 0.0021
0.0696 ± 0.0214
0.0039 ± 0.0010
Wilt
0.0020 ± 0.0003
0.0052 ± 0.0056
0.1133 ± 0.0230
0.0040 ± 0.0009
Wine
0.0002 ± 0.0004
0.0003 ± 0.0003
0.0004 ± 0.0003
0.0003 ± 0.0001From Table3, it can be clearly seen that the training time of core set based LARM is longer than the best of ν-SVM, SVDD, and MAMC, when the number of the training patterns is less than 2,143. However, when the number of training patterns is larger than 2,686 such as SDD, MC, Shuttle, Cod-rna, S. segmentation, and Covtype, the training time of core set based LARM is shorter than the best of ν-SVM, SVDD, and MAMC. When the number of training patterns increases to 141,792, the average training time of core set based LARM does not exceed 65 seconds. Therefore, the training time of core set based LARM does not increase very quickly with the number of training patterns.As can be seen from Table4, the best testing time of ν-SVM, SVDD, and MAMC performs slightly better than core set based LARM on 11 over 20 datasets; the longest time gap is 0.002 second. However, the testing time of core set based LARM is not the worst one. When the number of testing patterns is 353,349, such as Covtype, the average testing time of core set based LARM is about 1.5 seconds. It shows that the core set based LARM can detect testing examples fast.


## 4.1. Performance Measurement and Parameter Selection

The performance of core set based LARM is compared with three kernel-based algorithms:ν-SVM, SVDD, and MAMC. The geometric mean accuracy g=(a+·a-)1/2 [26] is used for both parameter selection and algorithm evaluation, where a+ is the classification accuracy of the positive class and a- is the classification accuracy of the negative class. The measurement is widely applied in imbalanced data [14, 26, 27], and it considers the classification results on both the positive and the negative classes. To make the experimental results persuasive enough, all the parameters of ν-SVM, SVDD, MAMC, and core set based LARM are selected by fivefold cross validation.In all experiments, the Radial Basis Function (RBF) is taken as the kernel function:(23)κxi,xj=exp-γxi-xj2,0<γ<+∞,where γ is the kernel parameter of the RBF. For all the algorithms, RBF parameter γ is calculated by [12, 13](24)γ=n-1∑i=1ndiag⁡K--1/n∑i=1n∑j=1nK-i,j,where K-i,j=xiTxj and diag⁡(K-) is the diagonal elements of matrix K-.Forν-SVM, parameter ν is searched in {0.1k,0.01k,0.001k,0.0001k}, where k=1,3,5,7,9.For SVDD, parameterC1 is searched in {0.01,0.05,0.1,0.5,1,5,10,50,100,500} and parameter C2 is searched by the ratio C2/C1 belonging to m1/4m2,m1/2m2,m1/m2,2m1/m2,4m1/m2.For MAMC, parameterC is searched in {10,30,50,70,90} and parameter ν is searched in {2,5,7,9,20,50,70,90}.For core set based LARM, parameterν is searched in {10,30,50,70,90} and parameters ν1 and ν2 are searched in {0.001,0.01}. From (21), ν1ν+1∈[0.01,0.9] and νν2∈[0.01,0.9] can be achieved, which are most associated with the percentage of support vectors and margin errors. From Section 4.2, we can see that parameters λ and ε have faint effect on the accuracy rate. Therefore, parameters λ and ε are set to 1 and 10-5, respectively.


## 4.2. Parameters Influence

There are five parameters in core set based LARM, that is,ν, ν1, ν2, λ, and ε. To verify the influence of the parameters on the performance of core set based LARM, experiments on some representative datasets are performed. By fixing other parameters, the influence of every parameter on some representative datasets is further studied, which is shown in Figures 3–7.Figure 3
Influence of parameterν on geometric mean accuracy and the number of core sets.
(a)
Influence ofν on geometric mean accuracy
(b)
Influence ofν on the number of core setsFigure 4
Influence of parameterν1 on geometric mean accuracy and the number of core sets.
(a)
Influence ofν1 on geometric mean accuracy
(b)
Influence ofν1 on the number of core setsFigure 5
Influence of parameterν2 on geometric mean accuracy and the number of core sets.
(a)
Influence ofν2 on geometric mean accuracy
(b)
Influence ofν2 on the number of core setsFigure 6
Influence of parameterλ on geometric mean accuracy and the number of core sets.
(a)
Influence ofλ on geometric mean accuracy
(b)
Influence ofλ on the number of core setsFigure 7
Influence of parameterε on geometric mean accuracy and the number of core sets.
(a)
Influence ofε on geometric mean accuracy
(b)
Influence ofε on the number of core setsFigure3 shows the influence of ν on the geometric mean accuracy and the number of core sets by varying ν from 10 to 100 while fixing ν1, ν2, λ, and ε as the suggested value obtained by the cross validation described in Section 4.1. Figure 4 shows the influence of ν1 on the geometric mean accuracy and the number of core sets by varying ν1 from 0.001 to 0.01 while fixing ν, ν2, λ, and ε in the same way. Figure 5 shows the influence of ν2 on the geometric mean accuracy and the number of core sets by varying ν2 from 0.001 to 0.01 while fixing ν, ν1, λ, and ε in the same way. Figure 6 shows the influence of λ on the geometric mean accuracy and the number of core sets by varying λ from 2-9 to 20 while fixing ν, ν1, ν2, and ε in the same way. Figure 7 shows the influence of ε on the geometric mean accuracy and the number of core sets by varying ε from 1e-9 to 1e-2 while fixing ν, ν1, ν2, and λ in the same way.From Figures3–7, it can be seen that parameters ν, ν1, ν2, λ, and ε have faint effect on the geometric mean accuracy and the number of core sets, which make the core set based LARM even more attractive in practice. Therefore, parameters ν, ν1, ν2, λ, and ε obtained by the cross validation described in Section 4.1 are acceptable for all experiments.


## 4.3. Numerical Results

### 4.3.1. Detection Performance

For each dataset, samples are randomly split into training patterns and testing patterns with the proportion described in Table1. Parameters of ν-SVM, SVDD, MAMC, and core set based LARM are selected by fivefold cross validation to make the experimental results persuasive enough.The geometric mean accuracy is used for the performance evaluation. Experiments are repeated for 10 times with random data partitions. The average accuracy and the standard deviation are listed in Table2. NULL shows that there is no return result in 10 hours. Furthermore, with regard to every dataset, the difference between the bold results and the best geometric mean accuracy is not significant, which is determined by the Wilcoxon rank-sum test, with the confidence level of 0.05.Table 2
Average geometric mean accuracy and standard deviation on datasets.
Dataset
ν-SVM (%)
SVDD (%)
MAMC (%)
Core set based LARM (%)
Australian
47.88 ± 14.46
56.03 ± 9.21
35.11 ± 10.36
63.67 ± 9.12
B. authentication
97.25 ± 1.66
98.60 ± 0.95
95.34 ± 3.65
98.60 ± 2.30
B. Cancer
92.38 ± 1.43
95.25 ± 0.89
92.75 ± 2.43
93.61 ± 3.53
Cod-rna
45.63 ± 15.18
NULL
NULL
75.46 ± 8.79
Covtype
NULL
NULL
NULL
57.51 ± 8.27
Diabetic
42.91 ± 9.34
52.26 ± 9.01
50.14 ± 8.54
53.50 ± 8.90
Fourclass
77.23 ± 7.34
81.74 ± 11.27
64.31 ± 13.04
81.97 ± 8.16
Glass
95.12 ± 4.27
80.78 ± 5.71
94.56 ± 4.47
96.56 ± 3.52
Heart
42.01 ± 14.10
52.23 ± 5.80
51.50 ± 10.84
54.29 ± 8.32
H. valley
43.05 ± 9.25
42.00 ± 10.79
35.76 ± 19.45
44.16 ± 2.34
Ionosphere
46.44 ± 16.10
66.54 ± 9.81
36.07 ± 16.80
71.17 ± 14.91
L. disorders
50.21 ± 5.83
54.72 ± 7.49
45.80 ± 6.58
58.55 ± 3.14
MC
20.46 ± 3.84
67.36 ± 3.87
41.57 ± 7.12
62.94 ± 5.46
SDD
40.26 ± 9.63
25.93 ± 9.54
20.64 ± 21.66
45.67 ± 10.30
S. segmentation
NULL
NULL
NULL
95.91 ± 1.92
Sonar
52.27 ± 8.87
31.39 ± 6.99
55.79 ± 11.36
46.37 ± 9.04
Shuttle
91.65 ± 5.49
40.23 ± 21.59
NULL
92.88 ± 4.11
Svmguide1
82.17 ± 6.91
90.21 ± 6.88
89.95 ± 4.18
91.83 ± 2.69
Wilt
82.14 ± 9.29
56.95 ± 15.52
64.76 ± 3.81
84.95 ± 13.94
Wine
82.32 ± 4.57
86.00 ± 6.95
87.19 ± 4.32
87.62 ± 1.97From Table2, it can be concluded that the performance of core set based LARM is comparable to the best of ν-SVM, SVDD, and MAMC on all datasets. The core set based LARM performs significantly better than ν-SVM, SVDD, and MAMC on 12, 9, and 13 over 20 datasets, respectively. It illustrates that, by using (1+ε) and (1-ε)-approximation algorithm for training LARM, the generalization performance of core set based LARM is comparable to or even better than the best of ν-SVM, SVDD, and MAMC.


### 4.3.2. Time Cost

The time cost ofν-SVM, SVDD, MAMC, and core set based LARM on different datasets is shown in Tables 3 and 4. The average and standard deviation of training time (including parameters selection and model training time) are shown in Table 3. The average and standard deviation of testing time are shown in Table 4. All the experiments are conducted on the computer with an i5-2400@3.10 GHz CPU and 8 GB SDRAM. NULL shows that there is no return result in 10 hours. Furthermore, with regard to every dataset, the difference between the bold results and the best time cost is not significant, which is determined by the Wilcoxon rank-sum test, with the confidence level of 0.05.Table 3
Training time on different datasets.
Dataset
ν-SVM (s)
SVDD (s)
MAMC (s)
Core set based LARM (s)
Australian
0.0739 ± 0.0086
0.5975 ± 0.0993
0.6325 ± 0.0122
0.8819 ± 0.4613
B. authentication
0.1627 ± 0.0699
0.3441 ± 0.0199
1.3943 ± 0.0131
1.1103 ± 0.1658
B. Cancer
0.0975 ± 0.0063
0.2462 ± 0.0152
0.7309 ± 0.0126
2.2633 ± 0.2803
Cod-rna
388.7901 ± 24.6651
NULL
NULL
7.4578 ± 0.1622
Covtype
NULL
NULL
NULL
64.9519 ± 7.3727
Diabetic
0.2096 ± 0.0063
1.1188 ± 0.0819
1.9243 ± 0.0119
5.7415 ± 1.0748
Fourclass
0.0354 ± 0.0030
0.1271 ± 0.0151
0.2706 ± 0.0117
0.5652 ± 0.1175
Glass
0.0255 ± 0.0038
0.0587 ± 0.0038
0.1459 ± 0.0088
0.2079 ± 0.0220
Heart
0.0229 ± 0.0016
0.0858 ± 0.0082
0.1148 ± 0.0070
0.8305 ± 0.2195
H. valley
0.1457 ± 0.0119
1.0385 ± 0.0278
1.4355 ± 0.0164
0.8506 ± 0.2926
Ionosphere
0.0634 ± 0.0097
0.1999 ± 0.0134
0.4018 ± 0.0087
1.9758 ± 0.3947
L. disorders
0.0399 ± 0.0058
0.1861 ± 0.0202
0.1809 ± 0.0095
1.6280 ± 0.4039
MC
19.5417 ± 0.3331
49.0111 ± 10.8097
472.2837 ± 1.3679
17.1713 ± 5.3223
SDD
13.8246 ± 1.0316
145.7426 ± 18.0463
218.5634 ± 0.6386
8.3123 ± 0.5485
S. segmentation
NULL
NULL
NULL
7.2536 ± 0.3645
Sonar
0.0463 ± 0.0050
0.1406 ± 0.0061
0.1896 ± 0.0054
2.3453 ± 0.4481
Shuttle
226.0020 ± 3.1471
268.0641 ± 145.7989
NULL
7.3061 ± 0.2336
Svmguide1
0.4634 ± 0.0171
1.3081 ± 0.3742
8.9181 ± 0.0539
1.0625 ± 0.0781
Wilt
2.0750 ± 0.0774
8.6527 ± 0.7402
52.8582 ± 0.7763
3.6379 ± 0.3202
Wine
0.0263 ± 0.0049
0.0983 ± 0.0274
0.1785 ± 0.0111
0.2936 ± 0.0494Table 4
Testing time on different datasets.
Dataset
ν-SVM (s)
SVDD (s)
MAMC (s)
Core set based LARM (s)
Australian
0.0009 ± 0.0005
0.0035 ± 0.0014
0.0023 ± 0.0017
0.0013 ± 0.0004
B. authentication
0.0050 ± 0.0129
0.0010 ± 0.0004
0.0070 ± 0.0032
0.0018 ± 0.0012
B. Cancer
0.0011 ± 0.0003
0.0013 ± 0.0004
0.0032 ± 0.0012
0.0012 ± 0.0003
Cod-rna
0.2901 ± 0.2182
NULL
NULL
0.0584 ± 0.0085
Covtype
NULL
NULL
NULL
1.5096 ± 1.1866
Diabetic
0.0015 ± 0.0009
0.0054 ± 0.0016
0.0075 ± 0.0056
0.0029 ± 0.0010
Fourclass
0.0004 ± 0.0001
0.0006 ± 0.0002
0.0015 ± 0.0007
0.0007 ± 0.0002
Glass
0.0002 ± 0.0002
0.0002 ± 0.0001
0.0005 ± 0.0004
0.0004 ± 0.0003
Heart
0.0003 ± 0.0001
0.0005 ± 0.0001
0.0008 ± 0.0004
0.0007 ± 0.0004
H. valley
0.0021 ± 0.0013
0.0101 ± 0.0021
0.0050 ± 0.0032
0.0031 ± 0.0009
Ionosphere
0.0007 ± 0.0003
0.0016 ± 0.0008
0.0018 ± 0.0009
0.0011 ± 0.0003
L. disorders
0.0004 ± 0.0002
0.0006 ± 0.0002
0.0006 ± 0.0002
0.0006 ± 0.0003
MC
0.0282 ± 0.0073
0.6090 ± 0.3269
0.7920 ± 0.9542
0.0269 ± 0.0132
SDD
0.2947 ± 0.3511
9.4060 ± 3.3205
2.6391 ± 4.2971
0.1829 ± 0.0488
S. segmentation
NULL
NULL
NULL
0.1504 ± 0.0331
Sonar
0.0006 ± 0.0003
0.0011 ± 0.0003
0.0013 ± 0.0003
0.0010 ± 0.0004
Shuttle
0.0393 ± 0.0147
4.5419 ± 3.2784
NULL
0.0342 ± 0.0082
Svmguide1
0.0027 ± 0.0009
0.0031 ± 0.0021
0.0696 ± 0.0214
0.0039 ± 0.0010
Wilt
0.0020 ± 0.0003
0.0052 ± 0.0056
0.1133 ± 0.0230
0.0040 ± 0.0009
Wine
0.0002 ± 0.0004
0.0003 ± 0.0003
0.0004 ± 0.0003
0.0003 ± 0.0001From Table3, it can be clearly seen that the training time of core set based LARM is longer than the best of ν-SVM, SVDD, and MAMC, when the number of the training patterns is less than 2,143. However, when the number of training patterns is larger than 2,686 such as SDD, MC, Shuttle, Cod-rna, S. segmentation, and Covtype, the training time of core set based LARM is shorter than the best of ν-SVM, SVDD, and MAMC. When the number of training patterns increases to 141,792, the average training time of core set based LARM does not exceed 65 seconds. Therefore, the training time of core set based LARM does not increase very quickly with the number of training patterns.As can be seen from Table4, the best testing time of ν-SVM, SVDD, and MAMC performs slightly better than core set based LARM on 11 over 20 datasets; the longest time gap is 0.002 second. However, the testing time of core set based LARM is not the worst one. When the number of testing patterns is 353,349, such as Covtype, the average testing time of core set based LARM is about 1.5 seconds. It shows that the core set based LARM can detect testing examples fast.


## 4.3.1. Detection Performance

For each dataset, samples are randomly split into training patterns and testing patterns with the proportion described in Table1. Parameters of ν-SVM, SVDD, MAMC, and core set based LARM are selected by fivefold cross validation to make the experimental results persuasive enough.The geometric mean accuracy is used for the performance evaluation. Experiments are repeated for 10 times with random data partitions. The average accuracy and the standard deviation are listed in Table2. NULL shows that there is no return result in 10 hours. Furthermore, with regard to every dataset, the difference between the bold results and the best geometric mean accuracy is not significant, which is determined by the Wilcoxon rank-sum test, with the confidence level of 0.05.Table 2
Average geometric mean accuracy and standard deviation on datasets.
Dataset
ν-SVM (%)
SVDD (%)
MAMC (%)
Core set based LARM (%)
Australian
47.88 ± 14.46
56.03 ± 9.21
35.11 ± 10.36
63.67 ± 9.12
B. authentication
97.25 ± 1.66
98.60 ± 0.95
95.34 ± 3.65
98.60 ± 2.30
B. Cancer
92.38 ± 1.43
95.25 ± 0.89
92.75 ± 2.43
93.61 ± 3.53
Cod-rna
45.63 ± 15.18
NULL
NULL
75.46 ± 8.79
Covtype
NULL
NULL
NULL
57.51 ± 8.27
Diabetic
42.91 ± 9.34
52.26 ± 9.01
50.14 ± 8.54
53.50 ± 8.90
Fourclass
77.23 ± 7.34
81.74 ± 11.27
64.31 ± 13.04
81.97 ± 8.16
Glass
95.12 ± 4.27
80.78 ± 5.71
94.56 ± 4.47
96.56 ± 3.52
Heart
42.01 ± 14.10
52.23 ± 5.80
51.50 ± 10.84
54.29 ± 8.32
H. valley
43.05 ± 9.25
42.00 ± 10.79
35.76 ± 19.45
44.16 ± 2.34
Ionosphere
46.44 ± 16.10
66.54 ± 9.81
36.07 ± 16.80
71.17 ± 14.91
L. disorders
50.21 ± 5.83
54.72 ± 7.49
45.80 ± 6.58
58.55 ± 3.14
MC
20.46 ± 3.84
67.36 ± 3.87
41.57 ± 7.12
62.94 ± 5.46
SDD
40.26 ± 9.63
25.93 ± 9.54
20.64 ± 21.66
45.67 ± 10.30
S. segmentation
NULL
NULL
NULL
95.91 ± 1.92
Sonar
52.27 ± 8.87
31.39 ± 6.99
55.79 ± 11.36
46.37 ± 9.04
Shuttle
91.65 ± 5.49
40.23 ± 21.59
NULL
92.88 ± 4.11
Svmguide1
82.17 ± 6.91
90.21 ± 6.88
89.95 ± 4.18
91.83 ± 2.69
Wilt
82.14 ± 9.29
56.95 ± 15.52
64.76 ± 3.81
84.95 ± 13.94
Wine
82.32 ± 4.57
86.00 ± 6.95
87.19 ± 4.32
87.62 ± 1.97From Table2, it can be concluded that the performance of core set based LARM is comparable to the best of ν-SVM, SVDD, and MAMC on all datasets. The core set based LARM performs significantly better than ν-SVM, SVDD, and MAMC on 12, 9, and 13 over 20 datasets, respectively. It illustrates that, by using (1+ε) and (1-ε)-approximation algorithm for training LARM, the generalization performance of core set based LARM is comparable to or even better than the best of ν-SVM, SVDD, and MAMC.


## 4.3.2. Time Cost

The time cost ofν-SVM, SVDD, MAMC, and core set based LARM on different datasets is shown in Tables 3 and 4. The average and standard deviation of training time (including parameters selection and model training time) are shown in Table 3. The average and standard deviation of testing time are shown in Table 4. All the experiments are conducted on the computer with an i5-2400@3.10 GHz CPU and 8 GB SDRAM. NULL shows that there is no return result in 10 hours. Furthermore, with regard to every dataset, the difference between the bold results and the best time cost is not significant, which is determined by the Wilcoxon rank-sum test, with the confidence level of 0.05.Table 3
Training time on different datasets.
Dataset
ν-SVM (s)
SVDD (s)
MAMC (s)
Core set based LARM (s)
Australian
0.0739 ± 0.0086
0.5975 ± 0.0993
0.6325 ± 0.0122
0.8819 ± 0.4613
B. authentication
0.1627 ± 0.0699
0.3441 ± 0.0199
1.3943 ± 0.0131
1.1103 ± 0.1658
B. Cancer
0.0975 ± 0.0063
0.2462 ± 0.0152
0.7309 ± 0.0126
2.2633 ± 0.2803
Cod-rna
388.7901 ± 24.6651
NULL
NULL
7.4578 ± 0.1622
Covtype
NULL
NULL
NULL
64.9519 ± 7.3727
Diabetic
0.2096 ± 0.0063
1.1188 ± 0.0819
1.9243 ± 0.0119
5.7415 ± 1.0748
Fourclass
0.0354 ± 0.0030
0.1271 ± 0.0151
0.2706 ± 0.0117
0.5652 ± 0.1175
Glass
0.0255 ± 0.0038
0.0587 ± 0.0038
0.1459 ± 0.0088
0.2079 ± 0.0220
Heart
0.0229 ± 0.0016
0.0858 ± 0.0082
0.1148 ± 0.0070
0.8305 ± 0.2195
H. valley
0.1457 ± 0.0119
1.0385 ± 0.0278
1.4355 ± 0.0164
0.8506 ± 0.2926
Ionosphere
0.0634 ± 0.0097
0.1999 ± 0.0134
0.4018 ± 0.0087
1.9758 ± 0.3947
L. disorders
0.0399 ± 0.0058
0.1861 ± 0.0202
0.1809 ± 0.0095
1.6280 ± 0.4039
MC
19.5417 ± 0.3331
49.0111 ± 10.8097
472.2837 ± 1.3679
17.1713 ± 5.3223
SDD
13.8246 ± 1.0316
145.7426 ± 18.0463
218.5634 ± 0.6386
8.3123 ± 0.5485
S. segmentation
NULL
NULL
NULL
7.2536 ± 0.3645
Sonar
0.0463 ± 0.0050
0.1406 ± 0.0061
0.1896 ± 0.0054
2.3453 ± 0.4481
Shuttle
226.0020 ± 3.1471
268.0641 ± 145.7989
NULL
7.3061 ± 0.2336
Svmguide1
0.4634 ± 0.0171
1.3081 ± 0.3742
8.9181 ± 0.0539
1.0625 ± 0.0781
Wilt
2.0750 ± 0.0774
8.6527 ± 0.7402
52.8582 ± 0.7763
3.6379 ± 0.3202
Wine
0.0263 ± 0.0049
0.0983 ± 0.0274
0.1785 ± 0.0111
0.2936 ± 0.0494Table 4
Testing time on different datasets.
Dataset
ν-SVM (s)
SVDD (s)
MAMC (s)
Core set based LARM (s)
Australian
0.0009 ± 0.0005
0.0035 ± 0.0014
0.0023 ± 0.0017
0.0013 ± 0.0004
B. authentication
0.0050 ± 0.0129
0.0010 ± 0.0004
0.0070 ± 0.0032
0.0018 ± 0.0012
B. Cancer
0.0011 ± 0.0003
0.0013 ± 0.0004
0.0032 ± 0.0012
0.0012 ± 0.0003
Cod-rna
0.2901 ± 0.2182
NULL
NULL
0.0584 ± 0.0085
Covtype
NULL
NULL
NULL
1.5096 ± 1.1866
Diabetic
0.0015 ± 0.0009
0.0054 ± 0.0016
0.0075 ± 0.0056
0.0029 ± 0.0010
Fourclass
0.0004 ± 0.0001
0.0006 ± 0.0002
0.0015 ± 0.0007
0.0007 ± 0.0002
Glass
0.0002 ± 0.0002
0.0002 ± 0.0001
0.0005 ± 0.0004
0.0004 ± 0.0003
Heart
0.0003 ± 0.0001
0.0005 ± 0.0001
0.0008 ± 0.0004
0.0007 ± 0.0004
H. valley
0.0021 ± 0.0013
0.0101 ± 0.0021
0.0050 ± 0.0032
0.0031 ± 0.0009
Ionosphere
0.0007 ± 0.0003
0.0016 ± 0.0008
0.0018 ± 0.0009
0.0011 ± 0.0003
L. disorders
0.0004 ± 0.0002
0.0006 ± 0.0002
0.0006 ± 0.0002
0.0006 ± 0.0003
MC
0.0282 ± 0.0073
0.6090 ± 0.3269
0.7920 ± 0.9542
0.0269 ± 0.0132
SDD
0.2947 ± 0.3511
9.4060 ± 3.3205
2.6391 ± 4.2971
0.1829 ± 0.0488
S. segmentation
NULL
NULL
NULL
0.1504 ± 0.0331
Sonar
0.0006 ± 0.0003
0.0011 ± 0.0003
0.0013 ± 0.0003
0.0010 ± 0.0004
Shuttle
0.0393 ± 0.0147
4.5419 ± 3.2784
NULL
0.0342 ± 0.0082
Svmguide1
0.0027 ± 0.0009
0.0031 ± 0.0021
0.0696 ± 0.0214
0.0039 ± 0.0010
Wilt
0.0020 ± 0.0003
0.0052 ± 0.0056
0.1133 ± 0.0230
0.0040 ± 0.0009
Wine
0.0002 ± 0.0004
0.0003 ± 0.0003
0.0004 ± 0.0003
0.0003 ± 0.0001From Table3, it can be clearly seen that the training time of core set based LARM is longer than the best of ν-SVM, SVDD, and MAMC, when the number of the training patterns is less than 2,143. However, when the number of training patterns is larger than 2,686 such as SDD, MC, Shuttle, Cod-rna, S. segmentation, and Covtype, the training time of core set based LARM is shorter than the best of ν-SVM, SVDD, and MAMC. When the number of training patterns increases to 141,792, the average training time of core set based LARM does not exceed 65 seconds. Therefore, the training time of core set based LARM does not increase very quickly with the number of training patterns.As can be seen from Table4, the best testing time of ν-SVM, SVDD, and MAMC performs slightly better than core set based LARM on 11 over 20 datasets; the longest time gap is 0.002 second. However, the testing time of core set based LARM is not the worst one. When the number of testing patterns is 353,349, such as Covtype, the average testing time of core set based LARM is about 1.5 seconds. It shows that the core set based LARM can detect testing examples fast.


## 5. Conclusion

In this paper, a novel LARM algorithm and its fast training method based on core set are proposed for novelty detection on imbalanced data. The proposed LARM algorithm combines the ideas of one-class and binary classification algorithms, which constructs the largest vector-angular region in the feature space to separate normal training patterns and maximizes the vector-angular margin between this optimal vector-angular region and the abnormal data. In order to make the generalization performance of LARM better, the vector-angular distribution is optimized by maximizing the vector-angular mean and minimizing the vector-angular variance. To improve the computation efficiency,(1+ε) and (1-ε)-approximation algorithm is proposed for fast training LARM based on core set. The time and space complexity of core set based LARM are linear to and independent of the number of training patterns, respectively. Comprehensive experiments have validated the effectiveness of proposed approach. In the future, it will be interesting to extend the idea of LARM to handle one-class learning problem.



---

*Source: 1658758-2016-02-10.xml*