# Intuitionistic Fuzzy Kernel Matching Pursuit Based on Particle Swarm Optimization for Target Recognition

Authors: Xiaodong Yu; Yingjie Lei; Shaohua Yue; Feixiang Meng
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

In order to overcome the long training time caused by searching optimal basic functions based on greedy strategy from a redundant basis function dictionary for the intuitionistic fuzzy kernel matching pursuit (IFKMP), the particle swarm optimization algorithm with powerful ability of global search and quick convergence rate is applied to speed up searching optimal basic function data in function dictionary. The approach of intuitionistic fuzzy kernel matching pursuit based on particle swarm optimization algorithm, namely, PS-IFKMP, is proposed. This algorithm is applied to the aerospace target recognition, which requires real-time ability. Simulation results show that, compared with the conventional approaches, the proposed algorithm can decrease training time and improve calculation efficiency obviously with almost unchanged classification accuracy, while the model has better sparsity and generalization. It is also demonstrated that this approach is suitable for the application requiring both accuracy and efficiency.


---

## Body

## 1. Introduction

The kernel matching pursuit (KMP) Classifier is a new classification technique proposed by Vincent and Bengio in 2002 [1]. The basic idea of KMP originates from matching pursuit (MP) method of sign processing theory, a greedy constructive algorithm that approximates a given function by a linear combination of basis functions chosen from a redundant basis function dictionary, and can be seen as a form of boosting. When training a KMP Classifier, there are mainly three steps. First, it maps training data into a redundant basis dictionary by a given kernel function and then uses greedy algorithm to find a linear expansion of basis functions that are selected from a redundant dictionary of functions to minimize the loss function and, at last, adjusts the corresponding coefficients by backfitting algorithm. The linear expansion of basis functions is the target function that we seek. The performance of the KMP Classifier is comparable to that of support vector machine (SVM) for classification, while typically requiring far fewer support points [2, 3]. Compared with the other Kernel methods, KMP is very flexible and has no constraint on the form of kernels. It can be allowed to mix several shapes of kernels in one instance. Up to now, the theory of KMP has been successfully applied to a variety of fields, such as pattern classification [4, 5], image recognition [6], and intrusion detection [7].However, there is a special case in practical application; the importance degree (or threat degree) of one type is higher than the other targets, so we need to classify the appointed important target much more precisely and reduce the recognition accuracy of the other unimportant targets. For example, in missile defense battle, the requirement of recognition accuracy of the true warhead is higher than that of bait, debris, and so forth. The traditional kernel matching pursuit algorithm deals with all samples equally and the decision function gives a full scale consideration for all samples in order to minimize total recognition error.Unfortunately, such algorithm cannot perform well in special cases. To circumvent the disadvantage, Li et al. [8] proposed a fuzzy kernel matching pursuit (FKMP) machine, which can classify the appointed important samples much more precisely according to the predefined importance of the data. However, this method sets the fuzzy factor on the basis of artificial experience, which may bring risks to the training process. Lei et al. [9] proposed intuitionistic fuzzy kernel matching pursuit (IFKMP) machine and expanded KMP algorithm into intuitionistic fuzzy field to solve the problem that some important data cannot be classified precisely by assigning the intuitionistic fuzzy parameters to different samples efficiently. Nevertheless, the IFKMP machine essentially uses MP greedy algorithm to find a linear combination of basis functions that are selected from a redundant dictionary of functions, so the problem of greatly computer burden has not been solved, and the computing time can be increased greatly with searching spaces increasing, which may be more serious when the dictionary has two or few functions [10]. To overcome the above drawback, the optimization methods have been introduced into MP algorithm. An improved genetic algorithm (GA) is proposed to simplify the calculation of MP algorithm in [11]; however, due to GA’s prematurity, the stable capability of learning machine is not good. In [12], a quantum genetic algorithm is introduced for modifying MP process; however, the computing time cannot reduce effectively due to the slow search speed of quantum genetic algorithm. In [13], a novel technique for KMP based on intuitionistic fuzzy c-means (IFCM) was proposed, but IFCM is still a local optimization algorithm and reduces the recognition accuracy of KMP. Particle swarm optimization (PSO) proposed by Kennedy and Eberhart [14] is a global optimization algorithm. Since its appearance, for its powerful ability of global search and quick convergence rate, PSO has received more and more attention [15, 16]. Based on analysis above, this paper put forward a novel technique for intuitionistic fuzzy kernel matching pursuit based on particle swarm optimization (PS-IFKMP), where the greedy algorithm is replaced by PSO algorithm. In order to test the effect and validity of PS-IFKMP algorithm, three different datasets are used for simulation. The results are compared with those based on KMP and IFKMP. Experiments results validate the preference and efficiency of PS-IFKMP.


## 2. Intuitionistic Fuzzy Kernel Matching Pursuit

### 2.1. Matching Pursuit

Matching pursuit was introduced in the signal-processing community as an algorithm that decomposes any signal into a linear expansion of waveforms that are selected from a redundant dictionary of functions.Givenl noisy observations {y1,y2,…,yl} at {x1,x2,…,xl} and a finite dictionary D of functions in Hilbert space H, we aim to find sparse approximations of {y1,y2,…,yl} that are expansion of the form fN=∑n=1Nαngn(x), which minimize the squared norm of the residue RN2=y-fN2, where α1,α2,…,αl∈RN and g1,g2,…,gl∈D.The process of MP can be described as follows: it starts at stage 0 withR0=y and f0=0 and recursively appends functions to an initially empty basis. Given fn, we build fn+1=fn+αn+1gn+1, by searching for gn+1∈D and αn+1∈R that minimize the squared norm of the residue RN+12=RN-αn+1gn+12,(1)gn+1,αn+1=argmin⁡g∈D,α∈RRN+1=∑k=1nαkgk+αg-y2.Moreover,(2)gn+1=argmax⁡g∈Dg,Rng,αn+1=gn+1,Rngn+12.From above, we can see that MP actually adopts greedy algorithm. In each iterative process, MP finds the most correlative basis function in D with the current residue Rn. As the basis is appended continuously, fn can approach observations {y1,y2,…,yl} more and more accurately. However, algorithm will generally stop when the norm of the residue Rn2 goes below a predefined threshold or the number of the bases reaches the maximum.


### 2.2. Kernel Matching Pursuit

Kernel matching pursuit is simply the idea of applying the matching pursuit family of algorithms to problem in machine learning, using a kernel-based dictionary [5]. Given a kernel function K:Rd×Rd→R, we construct the basis dictionary of KMP on the training data: D={gi=K(·,xi)∣i=1,…,l}.Kernel method is enlightened in great part to the success of the SVM, but there are some differences between them. The kernel used in SVM must satisfy the Mercer condition, while kernel in KMP has no such restriction. Simultaneously, one can use more than one kernel when constructing the function dictionary of KMP. There are some kernels in common use:(1)
polynomial kernel:K(x,xi)=x-xi+1d,(2)
radial basis function (RBF) kernel:(3)Kx,xi=exp⁡-x-xi22ρ.(3)
Sigmoid kernel:K(x,xi)=Svx,xi+c.


### 2.3. Intuitionistic Fuzzy Kernel Matching Pursuit

By assigning the intuitionistic fuzzy parameters to different samples efficiently, IFKMP algorithm can classify the target samples of diverse importance much more precisely according to the predefined importance of samples.Definition 1 (⊙ operation).
Letx={x1,x2,…,xm} and y={y1,y2,…,ym} be two vectors; then we define the ⊙ operation as (4)x⊙y=x1·y1,…,xm·ym.Moreover,(5)x⊙y2=∑i=1mxi·yi2.Given l noisy samples {(x1,y1,ω(y1)),…,(xl,yl,ω(yl))}, where xi∈RN represents the sample feature, yi∈R represents the sample observation, and ω(yi) is intuitionistic fuzzy parameter and given a kernel function K:Rd×Rd→R, we construct the basis dictionary on the training data: D={gi=K(·,xi)∣i=1,…,l}.
Then the residue is(6)rN=ω⊙y-fN=ωy1y1-fNx1···ωylyl-fNxl,where fN(xi)=∑j=1Nαjgjxi represents the estimated value y^i of the ith sample; then the squared norm of the residue can be written as(7)rN2=ω⊙y-fN2=∑i=1lωyiyi-fNxi2.According to MP algorithm, we can get(8)rN+12=ω⊙y-fN+αN+1gN+12=ω⊙y-fN-ω⊙αN+1gN+12=rN-ω⊙αN+1gN+12=defrN-ω⊙αg2.Then,(9)rN+12=rN2-2αrN,ω⊙g+a2ω⊙g2.For any g∈D, α∈R that minimizes the squared norm of the residue rN+12 is given by(10)∂rN2∂α=0⟹-2rN,ω⊙g+2aω⊙g2=0⟹α=rN,ω⊙gω⊙g2.For this optimal value of α, we have(11)rN+12=rN2-2·rN,ω⊙gω⊙g2·rN,ω⊙g+rN,ω⊙gω⊙g22·ω⊙g2=rN2-rN,ω⊙gω⊙g2.So g∈D that minimizes expression (9) is the one that minimizes (11); we can get(12)gN+1=argmin⁡g∈DrN2-rN,ω⊙gω⊙g2⟹gN+1=argmax⁡g∈DrN,ω⊙gω⊙g,and the corresponding coefficient αN+1 is(13)αN+1=rN,ω⊙gN+1ω⊙gN+12.At every step in this algorithm, not only the set of basis functions gi but also their coefficients αi are obtained. So, the approximate form of observations {y1,y2,…,yl} in ith iteration is(14)fi=∑k=1i-1αkgk+αigi.However, when appending αigi, the linear combination may not be optimal. So a backfitting method is also done by reoptimizing all coefficients α1,…,αi to minimize the target cost:(15)α1,…,αi=argmin⁡αk∈Ri=1,…,iω⊙fi-y2=argmin⁡αk∈Ri=1,…,iω⊙∑k=1iαkgk-y2.
Finally, we can get the approximation functions in regression:(16)fNx=∑k=1Nαigi(x)=∑i∈spαik(x,xi)or decision function in classification:(17)fNx=sgn∑k=1Nαigix=sgn∑i∈svαikx,xi,where sv is the support vector set obtained by IFKMP algorithm.


### 2.4. The Selection of Intuitionistic Fuzzy Parameter

In practice, the recognition accuracy of different targets is different according to the threat degree. Generally, higher threat degree of the targets needs higher recognition accuracy. Aiming at this fact, the selection algorithm of intuitionistic fuzzy parameter can be listed as follows.Algorithm 1 (the selection algorithm of intuitionistic fuzzy parameter).
Input. Input is the type of sample yi.
Output. Output is the intuitionistic fuzzy parameter ω(yi).
Step
1. Determine yi as appointed important target or nonappointed target.
Step
2. Calculate the membership degree μ(yi) and nonmembership degree γ(yi); this paper uses Gaussian function as membership function, so (18)μyi=exp⁡-yi-c22ρ,γyi=δyi-exp⁡-yi-c22ρ,where ρ and c denote width and center point, respectively, δyi=1-π(yi) is denoted as nonhesitancy degree, and π(yi) denote the uncertainty degree which must be predefined on the basis of practice use.
Step
3. Calculate the intuitionistic fuzzy parameter ω(yi) by the following formula:(19)ωyi=μyi+σyiyiasappointedimportanttargetσyi-γyiσyi+γyiyiasnonappointedtarget.The intuitionistic fuzzy parameter can distinguish the appointed important target and nonappointed important target specifically and classify the appointed important samples much more precisely. Moreover, the total misclassification rate will still be lower even with a higher misclassification rateε of the nonappointed important target.


## 2.1. Matching Pursuit

Matching pursuit was introduced in the signal-processing community as an algorithm that decomposes any signal into a linear expansion of waveforms that are selected from a redundant dictionary of functions.Givenl noisy observations {y1,y2,…,yl} at {x1,x2,…,xl} and a finite dictionary D of functions in Hilbert space H, we aim to find sparse approximations of {y1,y2,…,yl} that are expansion of the form fN=∑n=1Nαngn(x), which minimize the squared norm of the residue RN2=y-fN2, where α1,α2,…,αl∈RN and g1,g2,…,gl∈D.The process of MP can be described as follows: it starts at stage 0 withR0=y and f0=0 and recursively appends functions to an initially empty basis. Given fn, we build fn+1=fn+αn+1gn+1, by searching for gn+1∈D and αn+1∈R that minimize the squared norm of the residue RN+12=RN-αn+1gn+12,(1)gn+1,αn+1=argmin⁡g∈D,α∈RRN+1=∑k=1nαkgk+αg-y2.Moreover,(2)gn+1=argmax⁡g∈Dg,Rng,αn+1=gn+1,Rngn+12.From above, we can see that MP actually adopts greedy algorithm. In each iterative process, MP finds the most correlative basis function in D with the current residue Rn. As the basis is appended continuously, fn can approach observations {y1,y2,…,yl} more and more accurately. However, algorithm will generally stop when the norm of the residue Rn2 goes below a predefined threshold or the number of the bases reaches the maximum.


## 2.2. Kernel Matching Pursuit

Kernel matching pursuit is simply the idea of applying the matching pursuit family of algorithms to problem in machine learning, using a kernel-based dictionary [5]. Given a kernel function K:Rd×Rd→R, we construct the basis dictionary of KMP on the training data: D={gi=K(·,xi)∣i=1,…,l}.Kernel method is enlightened in great part to the success of the SVM, but there are some differences between them. The kernel used in SVM must satisfy the Mercer condition, while kernel in KMP has no such restriction. Simultaneously, one can use more than one kernel when constructing the function dictionary of KMP. There are some kernels in common use:(1)
polynomial kernel:K(x,xi)=x-xi+1d,(2)
radial basis function (RBF) kernel:(3)Kx,xi=exp⁡-x-xi22ρ.(3)
Sigmoid kernel:K(x,xi)=Svx,xi+c.


## 2.3. Intuitionistic Fuzzy Kernel Matching Pursuit

By assigning the intuitionistic fuzzy parameters to different samples efficiently, IFKMP algorithm can classify the target samples of diverse importance much more precisely according to the predefined importance of samples.Definition 1 (⊙ operation).
Letx={x1,x2,…,xm} and y={y1,y2,…,ym} be two vectors; then we define the ⊙ operation as (4)x⊙y=x1·y1,…,xm·ym.Moreover,(5)x⊙y2=∑i=1mxi·yi2.Given l noisy samples {(x1,y1,ω(y1)),…,(xl,yl,ω(yl))}, where xi∈RN represents the sample feature, yi∈R represents the sample observation, and ω(yi) is intuitionistic fuzzy parameter and given a kernel function K:Rd×Rd→R, we construct the basis dictionary on the training data: D={gi=K(·,xi)∣i=1,…,l}.
Then the residue is(6)rN=ω⊙y-fN=ωy1y1-fNx1···ωylyl-fNxl,where fN(xi)=∑j=1Nαjgjxi represents the estimated value y^i of the ith sample; then the squared norm of the residue can be written as(7)rN2=ω⊙y-fN2=∑i=1lωyiyi-fNxi2.According to MP algorithm, we can get(8)rN+12=ω⊙y-fN+αN+1gN+12=ω⊙y-fN-ω⊙αN+1gN+12=rN-ω⊙αN+1gN+12=defrN-ω⊙αg2.Then,(9)rN+12=rN2-2αrN,ω⊙g+a2ω⊙g2.For any g∈D, α∈R that minimizes the squared norm of the residue rN+12 is given by(10)∂rN2∂α=0⟹-2rN,ω⊙g+2aω⊙g2=0⟹α=rN,ω⊙gω⊙g2.For this optimal value of α, we have(11)rN+12=rN2-2·rN,ω⊙gω⊙g2·rN,ω⊙g+rN,ω⊙gω⊙g22·ω⊙g2=rN2-rN,ω⊙gω⊙g2.So g∈D that minimizes expression (9) is the one that minimizes (11); we can get(12)gN+1=argmin⁡g∈DrN2-rN,ω⊙gω⊙g2⟹gN+1=argmax⁡g∈DrN,ω⊙gω⊙g,and the corresponding coefficient αN+1 is(13)αN+1=rN,ω⊙gN+1ω⊙gN+12.At every step in this algorithm, not only the set of basis functions gi but also their coefficients αi are obtained. So, the approximate form of observations {y1,y2,…,yl} in ith iteration is(14)fi=∑k=1i-1αkgk+αigi.However, when appending αigi, the linear combination may not be optimal. So a backfitting method is also done by reoptimizing all coefficients α1,…,αi to minimize the target cost:(15)α1,…,αi=argmin⁡αk∈Ri=1,…,iω⊙fi-y2=argmin⁡αk∈Ri=1,…,iω⊙∑k=1iαkgk-y2.
Finally, we can get the approximation functions in regression:(16)fNx=∑k=1Nαigi(x)=∑i∈spαik(x,xi)or decision function in classification:(17)fNx=sgn∑k=1Nαigix=sgn∑i∈svαikx,xi,where sv is the support vector set obtained by IFKMP algorithm.


## 2.4. The Selection of Intuitionistic Fuzzy Parameter

In practice, the recognition accuracy of different targets is different according to the threat degree. Generally, higher threat degree of the targets needs higher recognition accuracy. Aiming at this fact, the selection algorithm of intuitionistic fuzzy parameter can be listed as follows.Algorithm 1 (the selection algorithm of intuitionistic fuzzy parameter).
Input. Input is the type of sample yi.
Output. Output is the intuitionistic fuzzy parameter ω(yi).
Step
1. Determine yi as appointed important target or nonappointed target.
Step
2. Calculate the membership degree μ(yi) and nonmembership degree γ(yi); this paper uses Gaussian function as membership function, so (18)μyi=exp⁡-yi-c22ρ,γyi=δyi-exp⁡-yi-c22ρ,where ρ and c denote width and center point, respectively, δyi=1-π(yi) is denoted as nonhesitancy degree, and π(yi) denote the uncertainty degree which must be predefined on the basis of practice use.
Step
3. Calculate the intuitionistic fuzzy parameter ω(yi) by the following formula:(19)ωyi=μyi+σyiyiasappointedimportanttargetσyi-γyiσyi+γyiyiasnonappointedtarget.The intuitionistic fuzzy parameter can distinguish the appointed important target and nonappointed important target specifically and classify the appointed important samples much more precisely. Moreover, the total misclassification rate will still be lower even with a higher misclassification rateε of the nonappointed important target.


## 3. IFKMP Based on Particle Swarm Optimization

Theoretically IFKMP algorithm solves the problem that some important data cannot be classified precisely according to the predefined importance of the data efficiently, but its implement is a greedy algorithm. Greedy algorithm requires that every step of searching process be global optimal searching in the redundant dictionary of function in order to select best matching signal structure, from which the large amounts of computing time have often not suffered. Particle swarm optimization algorithm with powerful ability of global search and quick convergence rate solves the problem, by replacing greedy algorithm to find a linear expansion of basis functions.


### 3.1. Theoretical Analysis

We notice that a bottleneck of the IFKMP algorithm is represented by the search of the current best element from the redundant dictionary to be added in the function expansion. Usually, this requires a full search over the whole dictionary and may necessitate a large number of floating point operations. An alternative is provided by the so-called Weak Greedy Algorithm (WGA) [17] which provides an approximation of the MP and related greedy algorithms. WGA and its different formulations have been analyzed in [17, 18] and proofs of convergence of the algorithm exist under various conditions. Unlike classical greedy algorithm, WGA generates an approximate sequence as follows:(20)f~N+1=f~N+tN+1αN+1gN+1=f~N+α~N+1gN+1,tN+1∈0,1,where α~N+1=tN+1αN+1, and, clearly, for tN+1=1, WGA retrieves the original algorithm. The sequence τ={t1,t2,…,tN} is named weakness sequence and it must obey some constraints for the algorithm to converge. While different conditions on τ result in different guaranteed convergence rates, we will simply require that ∃t~>0 such that ∀N≥1, tN>t~, which ensures the convergence [18]. These modifications imply that we are no longer forced to produce the global maximum at each iteration of the IFKMP algorithm but just an approximate optimal value. So we can use PSO algorithm to search the next element from the redundant dictionary instead of greedy algorithm. Compared with greedy algorithm, the PSO algorithm may only find an approximate optimal value; we still can ensure the convergence of PS-IFKMP algorithm according to the theory of WGA. As a consequence, the performance of the decision function we get from PS-IFKMP algorithm is similar to the decision function from IFKMP algorithm under the same termination condition. Based on this point, we believe that PS-IFKMP algorithm can decrease computational complexity while classification accuracy remains statistically the same by using PSO algorithm to find a linear expansion of basis functions.


### 3.2. Particle Swarm Optimization

Particle swarm optimization is an evolutionary optimization technique based on metaphors for social interaction and communication such as flocks of birds and schools of fish. This stochastic, population-based approach has been proven effective for solving both continuous and discrete optimization problems. Each particle in a swarm, which is analogous to a bird in a flock or a fish in a school, moves around ind dimensional search space. Based on its own experience and that of the swarm, it moves toward the best position in the search space [19].The position and velocity of particlei at iteration t are represented by Xit and Vit, which can be defined as Xit=xi1t,xi2t,…,xidt and Vit=vi1t,vi2t,…,vidt, respectively, and the personal best (pbest) of particle i is represented by Pit, which denotes the position of particle i with the best fitness value found so far and is defined as Pit=pi1t,pi2t,…,pidt. The global best (gbest) of all particles at iteration t is represented by Pgt, which denotes the best position of the particle with the best fitness value in the swarm found so far and is defined as Pgt=pg1t,pg2t,…,pgdt. The new velocity and position of particle i can be obtained by (20) and (21), respectively:(21)vidt+1=ω·vidtt+c1·r1pidt-xidt+c2·r2pgdt-xidt,(22)xidt+1=xidt+vidt+1,where vidt(t) represents velocity of particle i at iteration t with respect to the dth dimension and vidt+1 is new velocity at iteration t+1, xidt is position of particle i at iteration t with respect to the dth dimension, and xidt+1 is new position at iteration t+1. pidt is position value of the ith pbest at iteration t with respect to the dth dimension and pgdt is position value of the gbest at iteration t. t is current iteration. c1, c2 are acceleration coefficients. r1, r2 are uniform random numbers between 0 and 1. ω is the inertia weight. Moreover, in order to make the speed of the particle not too high, a speed threshold vmax⁡ should be set. If vidt>vmax⁡, then vidt=vmax⁡, and if vidt<-vmax⁡, then vidt=-vmax⁡.


### 3.3. Target Recognition Algorithm of IFKMP Based on PSO

IFKMP algorithm uses greedy algorithm to find a linear combination of basis functions, that is, the decision functionfN in classification from a redundant dictionary of functions to minimize the objective function f. The PS-IFKMP algorithm first maps training data into a redundant basis dictionary D by a given kernel function and then sets the population size according to the scale of the training dataset. At last, the linear expansion of basis functions is found by using PSO algorithm. Because the larger the value of linear expansion of basis functions, the more effective the Classifier, formula (16) is selected as the fitness function. The detailed steps of PS-IFKMP algorithm are listed as follows.Algorithm 2 (intuitionistic fuzzy kernel matching pursuit based on particle swarm optimization).
Input. Input is the training dataset {(x1,y1),…,(xl,yl)}, the intuitionistic fuzzy parameters ω(yi), and the kernel parameter ρ.
Output. Output is the decision function fN(x).
Step
1 (initialization). Set the maximum iterations L and iterative threshold ε of IFKMP, set the population size N and the maximum iterations itermax⁡ of PSO, and suppose generation k=1, t=1.
Step
2. Construct the basis dictionary D on the training data: D={gi=K(·,xi)∣i=1,…,l}.
Step
3. Calculate coefficients αi=giT(x)·y/gi(x)2 based on the rule min⁡αiω⊙(y-αigi(x)); then α1t,α2t,…,αNt are selected as the initial population of particles randomly.
Step
4. Measure the fitness of each particle in the population by ft(αi,gi)=∑t=1Lαitgit.
Step
5. Update particles according to formulas (21) and (22); then update the pbest Pit and gbest Pgt.
Step
6. If k≥itermax⁡, stop the iteration; otherwise k=k+1, and go to Step 4.
Step
7. Let y=y-ft, and if y≥ε and t<L, go to Step 3 by using the updated y and solve the next basic function gi and weight coefficient αi.
Step
8. Recompute the optimal set of coefficients α1,…,αi by backfitting algorithm; then output the linear combination of the best weight coefficients and the corresponding basic functions, which is also the decision function fN(x).The flowchart of Algorithm2 is shown in Figure 1.Figure 1
Flowchart of PS-IFKMP algorithm.


### 3.4. Parameters Setting of PS-IFKMP

The inertia weightω can be a positive constant or even a positive linear or nonlinear function of time. When ω>1.2, the velocity item becomes the main item in the search direction of the particle. It extends the search area and finds the global optimum. When ω is between 0.8 and 1.2, three factors, velocity, pbest, and gbest, affect the velocity calculation for both local search and global search. When ω<0.8, only the pbest and gbest affect the new velocity calculation, which converges to the local optimum. Therefore, the value of inertia weight ω is a tradeoff between the global search and the local search. In this paper, the inertia weight starts with a high value ωmax⁡ and nonlinearly decreases to ωmin⁡ at the maximal number of iterations [20]:(23)ω=ωmin⁡+itermax⁡-iteritermax⁡β×ωmax⁡-ωmin⁡,where ωmax⁡ and ωmin⁡ are the initial and final values of the inertia weight, respectively, iter denotes the current number of iterations, and itermax⁡ denotes the maximum number of iterations. The value β is a constant coefficient.The acceleration factorsc1 and c2 are positive constants controlling the relative impact of the personal (local) and common (global) knowledge on the movement of each particle, and we improve the selection of acceleration factors by introducing inheritance mechanism:(24)c1·r1=ω1=pidtfidt+ω,c2·r2=ω2=pgdtpidt,where fidt is the fitness value of particle i at iteration t and the convergence rate of PS-IFKMP speeds up efficiently by introducing inheritance mechanism.In order to keep the diversity of the population, the Gaussian distribution is introduced. If thePgt has not been improved in a few steps, a certain proportion of particles should be randomly selected for mutation:(25)xidt′=xidt+r0·xidt,where r0 is a Gaussian random number with mean of 0 and standard deviation of 1.


### 3.5. Complexity Analysis

The performance of the proposed PS-IFKMP algorithm is analyzed in theory in this section. The IFKMP is a novel algorithm which was proposed in 2011, and no relevant improved algorithms have been proposed at present. Therefore we mainly compared theoretical complexity of the treatment of the proposed PS-IFKMP algorithm with IFKMP algorithm. IFKMP algorithm maps training data into a high-dimensional Hilbert space by a given kernel function to construct the basis function dictionary and then searches the best basis functions and the corresponding weight in each iteration. So the computation complexity can be described by the number of multiplications in one matching process in this paper.Assuming that the size of dictionary isn and the iteration number is L, IFKMP algorithm requires n·L single-precision multiplications in one matching process, and the complexity can be described as O(n·L) based on the computational analyses of Montgomery reduction algorithm. In PSO algorithm, position, velocity, and fitness of each particle need to be calculated in every iteration, so the algorithm requires 3·N·L single-precision multiplications in one matching process, where N is the population size and the complexity of PS-IFKMP can be described as O(3·N·L). As the population size N is far less than the dictionary size n, the computational cost of PS-IFKMP is far smaller than that of IFKMP when n is quite big, while the costs are familiar when n is small.


## 3.1. Theoretical Analysis

We notice that a bottleneck of the IFKMP algorithm is represented by the search of the current best element from the redundant dictionary to be added in the function expansion. Usually, this requires a full search over the whole dictionary and may necessitate a large number of floating point operations. An alternative is provided by the so-called Weak Greedy Algorithm (WGA) [17] which provides an approximation of the MP and related greedy algorithms. WGA and its different formulations have been analyzed in [17, 18] and proofs of convergence of the algorithm exist under various conditions. Unlike classical greedy algorithm, WGA generates an approximate sequence as follows:(20)f~N+1=f~N+tN+1αN+1gN+1=f~N+α~N+1gN+1,tN+1∈0,1,where α~N+1=tN+1αN+1, and, clearly, for tN+1=1, WGA retrieves the original algorithm. The sequence τ={t1,t2,…,tN} is named weakness sequence and it must obey some constraints for the algorithm to converge. While different conditions on τ result in different guaranteed convergence rates, we will simply require that ∃t~>0 such that ∀N≥1, tN>t~, which ensures the convergence [18]. These modifications imply that we are no longer forced to produce the global maximum at each iteration of the IFKMP algorithm but just an approximate optimal value. So we can use PSO algorithm to search the next element from the redundant dictionary instead of greedy algorithm. Compared with greedy algorithm, the PSO algorithm may only find an approximate optimal value; we still can ensure the convergence of PS-IFKMP algorithm according to the theory of WGA. As a consequence, the performance of the decision function we get from PS-IFKMP algorithm is similar to the decision function from IFKMP algorithm under the same termination condition. Based on this point, we believe that PS-IFKMP algorithm can decrease computational complexity while classification accuracy remains statistically the same by using PSO algorithm to find a linear expansion of basis functions.


## 3.2. Particle Swarm Optimization

Particle swarm optimization is an evolutionary optimization technique based on metaphors for social interaction and communication such as flocks of birds and schools of fish. This stochastic, population-based approach has been proven effective for solving both continuous and discrete optimization problems. Each particle in a swarm, which is analogous to a bird in a flock or a fish in a school, moves around ind dimensional search space. Based on its own experience and that of the swarm, it moves toward the best position in the search space [19].The position and velocity of particlei at iteration t are represented by Xit and Vit, which can be defined as Xit=xi1t,xi2t,…,xidt and Vit=vi1t,vi2t,…,vidt, respectively, and the personal best (pbest) of particle i is represented by Pit, which denotes the position of particle i with the best fitness value found so far and is defined as Pit=pi1t,pi2t,…,pidt. The global best (gbest) of all particles at iteration t is represented by Pgt, which denotes the best position of the particle with the best fitness value in the swarm found so far and is defined as Pgt=pg1t,pg2t,…,pgdt. The new velocity and position of particle i can be obtained by (20) and (21), respectively:(21)vidt+1=ω·vidtt+c1·r1pidt-xidt+c2·r2pgdt-xidt,(22)xidt+1=xidt+vidt+1,where vidt(t) represents velocity of particle i at iteration t with respect to the dth dimension and vidt+1 is new velocity at iteration t+1, xidt is position of particle i at iteration t with respect to the dth dimension, and xidt+1 is new position at iteration t+1. pidt is position value of the ith pbest at iteration t with respect to the dth dimension and pgdt is position value of the gbest at iteration t. t is current iteration. c1, c2 are acceleration coefficients. r1, r2 are uniform random numbers between 0 and 1. ω is the inertia weight. Moreover, in order to make the speed of the particle not too high, a speed threshold vmax⁡ should be set. If vidt>vmax⁡, then vidt=vmax⁡, and if vidt<-vmax⁡, then vidt=-vmax⁡.


## 3.3. Target Recognition Algorithm of IFKMP Based on PSO

IFKMP algorithm uses greedy algorithm to find a linear combination of basis functions, that is, the decision functionfN in classification from a redundant dictionary of functions to minimize the objective function f. The PS-IFKMP algorithm first maps training data into a redundant basis dictionary D by a given kernel function and then sets the population size according to the scale of the training dataset. At last, the linear expansion of basis functions is found by using PSO algorithm. Because the larger the value of linear expansion of basis functions, the more effective the Classifier, formula (16) is selected as the fitness function. The detailed steps of PS-IFKMP algorithm are listed as follows.Algorithm 2 (intuitionistic fuzzy kernel matching pursuit based on particle swarm optimization).
Input. Input is the training dataset {(x1,y1),…,(xl,yl)}, the intuitionistic fuzzy parameters ω(yi), and the kernel parameter ρ.
Output. Output is the decision function fN(x).
Step
1 (initialization). Set the maximum iterations L and iterative threshold ε of IFKMP, set the population size N and the maximum iterations itermax⁡ of PSO, and suppose generation k=1, t=1.
Step
2. Construct the basis dictionary D on the training data: D={gi=K(·,xi)∣i=1,…,l}.
Step
3. Calculate coefficients αi=giT(x)·y/gi(x)2 based on the rule min⁡αiω⊙(y-αigi(x)); then α1t,α2t,…,αNt are selected as the initial population of particles randomly.
Step
4. Measure the fitness of each particle in the population by ft(αi,gi)=∑t=1Lαitgit.
Step
5. Update particles according to formulas (21) and (22); then update the pbest Pit and gbest Pgt.
Step
6. If k≥itermax⁡, stop the iteration; otherwise k=k+1, and go to Step 4.
Step
7. Let y=y-ft, and if y≥ε and t<L, go to Step 3 by using the updated y and solve the next basic function gi and weight coefficient αi.
Step
8. Recompute the optimal set of coefficients α1,…,αi by backfitting algorithm; then output the linear combination of the best weight coefficients and the corresponding basic functions, which is also the decision function fN(x).The flowchart of Algorithm2 is shown in Figure 1.Figure 1
Flowchart of PS-IFKMP algorithm.


## 3.4. Parameters Setting of PS-IFKMP

The inertia weightω can be a positive constant or even a positive linear or nonlinear function of time. When ω>1.2, the velocity item becomes the main item in the search direction of the particle. It extends the search area and finds the global optimum. When ω is between 0.8 and 1.2, three factors, velocity, pbest, and gbest, affect the velocity calculation for both local search and global search. When ω<0.8, only the pbest and gbest affect the new velocity calculation, which converges to the local optimum. Therefore, the value of inertia weight ω is a tradeoff between the global search and the local search. In this paper, the inertia weight starts with a high value ωmax⁡ and nonlinearly decreases to ωmin⁡ at the maximal number of iterations [20]:(23)ω=ωmin⁡+itermax⁡-iteritermax⁡β×ωmax⁡-ωmin⁡,where ωmax⁡ and ωmin⁡ are the initial and final values of the inertia weight, respectively, iter denotes the current number of iterations, and itermax⁡ denotes the maximum number of iterations. The value β is a constant coefficient.The acceleration factorsc1 and c2 are positive constants controlling the relative impact of the personal (local) and common (global) knowledge on the movement of each particle, and we improve the selection of acceleration factors by introducing inheritance mechanism:(24)c1·r1=ω1=pidtfidt+ω,c2·r2=ω2=pgdtpidt,where fidt is the fitness value of particle i at iteration t and the convergence rate of PS-IFKMP speeds up efficiently by introducing inheritance mechanism.In order to keep the diversity of the population, the Gaussian distribution is introduced. If thePgt has not been improved in a few steps, a certain proportion of particles should be randomly selected for mutation:(25)xidt′=xidt+r0·xidt,where r0 is a Gaussian random number with mean of 0 and standard deviation of 1.


## 3.5. Complexity Analysis

The performance of the proposed PS-IFKMP algorithm is analyzed in theory in this section. The IFKMP is a novel algorithm which was proposed in 2011, and no relevant improved algorithms have been proposed at present. Therefore we mainly compared theoretical complexity of the treatment of the proposed PS-IFKMP algorithm with IFKMP algorithm. IFKMP algorithm maps training data into a high-dimensional Hilbert space by a given kernel function to construct the basis function dictionary and then searches the best basis functions and the corresponding weight in each iteration. So the computation complexity can be described by the number of multiplications in one matching process in this paper.Assuming that the size of dictionary isn and the iteration number is L, IFKMP algorithm requires n·L single-precision multiplications in one matching process, and the complexity can be described as O(n·L) based on the computational analyses of Montgomery reduction algorithm. In PSO algorithm, position, velocity, and fitness of each particle need to be calculated in every iteration, so the algorithm requires 3·N·L single-precision multiplications in one matching process, where N is the population size and the complexity of PS-IFKMP can be described as O(3·N·L). As the population size N is far less than the dictionary size n, the computational cost of PS-IFKMP is far smaller than that of IFKMP when n is quite big, while the costs are familiar when n is small.


## 4. Experiment Results and Analysis

This section evaluates the performance of the proposed PS-IFKMP algorithm by comparing its classification results with those obtained for the same cases by the KMP in [1] and IFKMP in [9] where PSO is encoded by real number and RBF kernel is used for both algorithms. To avoid the weak problem, each experiment has been performed at 50 independent runs. The average results and standard deviations (Std. in short) are given. All experiments were carried on a Pentium (R) Dual-Core CPU E5500 @2.8 GHz with 2 GB RAM using MATLAB 7.6 compiler.


### 4.1. Test on UCI Data

In this experiment, five UCI datasets of Musk, Waveform, German, Diabetes, and Breast Cancer Wisconsin (Breast in short) are used to test our methods, where Waveform contains three classes, and two of them (class 0 and class 2) are selected as experimental dataset. The characteristics of the UCI datasets are shown in Table1, which shows a wide range of attributes sizes and class sizes.Table 1
UCI dataset characteristics.
Title
Instances
Attributes
Classes
Musk
6598
166
2
Waveform
5000
21
3
German
1000
20
2
Diabetes
768
8
2
Breast
699
9
2The selection of different kernel function parameters has great influence on algorithm performance, so this paper validates the kernel parameter by a special training dataset. The intuitionistic fuzzy parameters are set asω(y1)=ω(y2)=1, L=200, ε=0.05, N=30, and itermax⁡=50 and the kernel function parameter ρ is taken in [1,500] by equal interval sampling. The influence of ρ on the accuracy is shown in Figure 2.Figure 2
Accuracy varying withρ.
(a)
Accuracy varying withρ based on Musk data
(b)
Accuracy varying withρ based on Diabetes data
(c)
Accuracy varying withρ based on Waveform
(d)
Accuracy varying withρ based on German data
(e)
Accuracy varying withρ based on Breast dataFrom Figure2, we can notice that the optimal kernel function parameters based on different datasets are different. Validated by experiments, ρ=360, 3, and 6 for Musk, Waveform, and German, respectively. There is no special requirement on the importance of samples; we can set ω(y1)=ω(y2)=1; then IFKMP algorithm is equivalent to KMP algorithm, so we only compare PS-IFKMP with the KMP in this section; the results are listed in Tables 2–4.Table 2
Testing of Musk dataset.
Title
Training set
Tested data
Method
# s. v.a
Training time (s)
Accuracy (%)
Std. of error (%)
Musk
1000
2000
KMP
156
0.389
92.12
2.17
PS-IFKMP
132
0.097
92.43
2.92
300
2000
KMP
100
0.084
90.44
4.76
PS-IFKMP
97
0.036
90.26
4.69
a# s. v.: number of support vectors.Table 3
Testing of Waveform dataset.
Title
Training set
Tested data
Method
# s. v.
Training time (s)
Accuracy (%)
Std. of error (%)
Waveform
1000
1000
KMP
120
0.297
92.70
3.16
PS-IFKMP
113
0.094
92.43
3.08
300
1000
KMP
123
0.072
91.56
1.59
PS-IFKMP
115
0.022
91.47
1.30Table 4
Testing of German dataset.
Title
Training set
Tested data
Method
# s. v.
Training time (s)
Accuracy (%)
Std. of error (%)
German
600
500
KMP
28
0.096
73.62
1.35
PS-IFKMP
23
0.029
73.86
1.33
300
500
KMP
32
0.022
71.80
2.82
PS-IFKMP
27
0.008
71.60
2.19From the above experiments, the average accuracy of KMP and PS-IFKMP is 85.37% and 86.34%, respectively, so the performance of the PS-IFKMP is competitive to that of KMP for classification. However, the average training time in one matching process of KMP and PS-IFKMP is 0.16 and 0.048, respectively; compared with KMP, the average training time of PS-IFKMP is decreased by 70%. So the proposed PS-IFKMP algorithm can decrease obviously training time with almost unchanged classification accuracy, especially for the large size datasets.Diabetes contains 500 negative samples and 268 positive samples, and Breast contains 241 negative samples and 458 positive samples. As we know, the positive samples describe the pathological features of diseases, so the positive samples should be classified much more precisely in terms of medical diagnosis. Validated by experiments,ρ=15 and 3 for Diabetes and Breast, respectively. The intuitionistic fuzzy parameters are selected by Algorithm 1, ω(y1) of appointed positive samples is 1.6, and ω(y2) of nonappointed negative samples is 0.3. The results are listed in Table 5.Table 5
Testing of appointed important samples.
Title
Training set
Tested data
Method
# s. v.
Training time (s)
Accuracy (%)
Std. of error (%)
Diabetes
Positive: 54Negative: 100
Positive: 67
KMP
32
0.014
66.67
3.14
IFKMP
33
0.016
98.45
2.76
PS-IFKMP
29
0.008
98.82
2.97
Breast
Positive: 60Negative: 115
Positive: 72
KMP
16
0.012
78.26
3.37
IFKMP
13
0.014
99.12
3.14
PS-IFKMP
15
0.009
98.92
3.07From Table5, facing imbalanced training set, standard KMP cannot classify the appointed important samples efficiently. IFKMP solves the aforementioned problem by assigning the intuitionistic fuzzy parameters to different samples and studying the weak samples sufficiently. Compared with IFKMP, the proposed PS-IFKMP algorithm can decrease training time obviously, and the classification accuracy is almost unchanged simultaneously.


### 4.2. Test on Artificial Data

Learning to tell two spirals apart is important both for purely academic reasons and for industrial application. In the research of the pattern recognition, it is a well-known problem for its difficulty. The parametric equation of the two spirals can be presented as follows:(26)Spiral-1:x1=k1θ+e1cos⁡θy1=k1θ+e1sinθaaaaθ∈U~0,2π,Spiral-2:x2=k2θ+e2cos⁡θy2=k2θ+e2sinθaaaaθ∈U~0,2π,where k1, k2, e1, and e2 are parameters. In our experiment, we choose k1=k2=4, e1=1, and e2=3. We generate 12000 samples randomly, and the samples distribution is shown in Figure 3(a). Moreover, a set of concentric circles samples also is selected to test our methods, and the parametric equation of the concentric circles data can be shown as (27)x=σ·cos⁡θy=σ·sinθθ∈U~0,2π.Parameter σ of the first class is of continuous uniform distribution U[0,55] and the second class σ~U[45,100]. 16000 samples are generated randomly, and the samples distribution is shown in Figure 3(b). Setting L=150, ε=0.02, N=50, itermax⁡=50, and ρ=8, the intuitionistic fuzzy parameters are selected by Algorithm 1; ω(y1) of appointed important samples (shown by “∙” in Figure 3) is 1.5 and ω(y2) of nonappointed samples (shown by “×” in Figure 3) is 0.3. Before the training, noise is added to training data, randomly choosing 10% samples and changing its class attributes. The results are listed in Table 6.Table 6
Testing of artificial dataset.
Title
Training set
Tested data
Method
# s. v.a
Training time (s)
Accuracy (%)
Std. of error (%)
Two spirals
Positive: 500Negative: 500
Positive: 1000
KMP
24
0.362
90.26
2.43
IFKMP
18
0.396
97.16
2.17
PS-IFKMP
15
0.047
98.12
1.85
Concentric circles
Positive: 500Negative: 500
Positive: 1000
KMP
200
0.453
91.13
1.96
IFKMP
165
0.470
99.03
1.22
PS-IFKMP
165
0.121
98.46
1.52Figure 3
The distribution map of artificial data.
(a)
The distribution map of two-spirals data
(b)
The distribution map of concentric circlesIn Table6, it is easily found that KMP cannot classify the appointed important samples efficiently when training Classifier with a subset of the data. IFKMP can classify the appointed important samples much more precisely by assigning the intuitionistic fuzzy parameters to different samples and studying the weak samples sufficiently. The proposed PS-IFKMP with advantage of both PSO and IFKMP reduces the training time enormously with the classification accuracy almost unchanged.


### 4.3. Test on Aerospace Target Data

In order to test the performance of the proposed PS-IFKMP algorithm in practical application, the aerospace targets data are selected for experiment. Generally, the threat degree of tactical ballistic missile (TBM), cruise missile (CM), and stealth aircraft (SA) is higher than the other targets, so we set these three targets as the appointed important targets. The radar cross section (RCS) values of the target are simulated by FEKO software, and the maximum, minimum, mean, and variance of RCS sequence are selected as sample features. And the RCS sequence of TBM within 30 seconds is showed in Figure4.Figure 4
RCS sequence of TBM within 30 s.Beside the appointed important targets, a large number of debris, baits, and other aircrafts, and so forth, are selected as negative samples. SettingL=200, ε=0.05, N=30, itermax⁡=50, and ρ=3.5, the ω(y1) of TBM equals 1.5, the ω(y2) of CM equals 1.3, and the ω(y3) of CM equals 1.6 by Algorithm 1. The results are listed in Table 7.Table 7
Testing of artificial dataset.
Title
Training set
Tested data
Method
Training time (s)
Accuracy (%)
Std. of error (%)
TBM
Positive: 122Negative: 478
Positive: 83
KMP
0.285
47.76
6.49
IFKMP
0.289
80.89
4.26
PS-IFKMP
0.116
81.65
4.75
CM
Positive: 223Negative: 387
Positive: 148
KMP
0.247
67.35
5.62
IFKMP
0.254
84.66
4.88
PS-IFKMP
0.095
85.99
4.37
SA
Positive: 188Negative: 412
Positive: 125
KMP
0.234
54.26
6.36
IFKMP
0.255
82.75
4.65
PS-IFKMP
0.130
82.51
5.02From Table7, by providing equal treatment on all training samples, the classical KMP algorithm cannot classify the weak important data efficiently. The IFKMP circumvents this problem by studying the important samples sufficiently and the less important samples roughly; however, the complexity problem still exists by adopting the greedy algorithm. By introducing particle swarm optimization algorithm, PS-IFKMP decreases the time complexity and reduces the training time with almost unchanged classification accuracy. It is also demonstrated that this approach is suitable to the application requiring both accuracy and timeliness.


## 4.1. Test on UCI Data

In this experiment, five UCI datasets of Musk, Waveform, German, Diabetes, and Breast Cancer Wisconsin (Breast in short) are used to test our methods, where Waveform contains three classes, and two of them (class 0 and class 2) are selected as experimental dataset. The characteristics of the UCI datasets are shown in Table1, which shows a wide range of attributes sizes and class sizes.Table 1
UCI dataset characteristics.
Title
Instances
Attributes
Classes
Musk
6598
166
2
Waveform
5000
21
3
German
1000
20
2
Diabetes
768
8
2
Breast
699
9
2The selection of different kernel function parameters has great influence on algorithm performance, so this paper validates the kernel parameter by a special training dataset. The intuitionistic fuzzy parameters are set asω(y1)=ω(y2)=1, L=200, ε=0.05, N=30, and itermax⁡=50 and the kernel function parameter ρ is taken in [1,500] by equal interval sampling. The influence of ρ on the accuracy is shown in Figure 2.Figure 2
Accuracy varying withρ.
(a)
Accuracy varying withρ based on Musk data
(b)
Accuracy varying withρ based on Diabetes data
(c)
Accuracy varying withρ based on Waveform
(d)
Accuracy varying withρ based on German data
(e)
Accuracy varying withρ based on Breast dataFrom Figure2, we can notice that the optimal kernel function parameters based on different datasets are different. Validated by experiments, ρ=360, 3, and 6 for Musk, Waveform, and German, respectively. There is no special requirement on the importance of samples; we can set ω(y1)=ω(y2)=1; then IFKMP algorithm is equivalent to KMP algorithm, so we only compare PS-IFKMP with the KMP in this section; the results are listed in Tables 2–4.Table 2
Testing of Musk dataset.
Title
Training set
Tested data
Method
# s. v.a
Training time (s)
Accuracy (%)
Std. of error (%)
Musk
1000
2000
KMP
156
0.389
92.12
2.17
PS-IFKMP
132
0.097
92.43
2.92
300
2000
KMP
100
0.084
90.44
4.76
PS-IFKMP
97
0.036
90.26
4.69
a# s. v.: number of support vectors.Table 3
Testing of Waveform dataset.
Title
Training set
Tested data
Method
# s. v.
Training time (s)
Accuracy (%)
Std. of error (%)
Waveform
1000
1000
KMP
120
0.297
92.70
3.16
PS-IFKMP
113
0.094
92.43
3.08
300
1000
KMP
123
0.072
91.56
1.59
PS-IFKMP
115
0.022
91.47
1.30Table 4
Testing of German dataset.
Title
Training set
Tested data
Method
# s. v.
Training time (s)
Accuracy (%)
Std. of error (%)
German
600
500
KMP
28
0.096
73.62
1.35
PS-IFKMP
23
0.029
73.86
1.33
300
500
KMP
32
0.022
71.80
2.82
PS-IFKMP
27
0.008
71.60
2.19From the above experiments, the average accuracy of KMP and PS-IFKMP is 85.37% and 86.34%, respectively, so the performance of the PS-IFKMP is competitive to that of KMP for classification. However, the average training time in one matching process of KMP and PS-IFKMP is 0.16 and 0.048, respectively; compared with KMP, the average training time of PS-IFKMP is decreased by 70%. So the proposed PS-IFKMP algorithm can decrease obviously training time with almost unchanged classification accuracy, especially for the large size datasets.Diabetes contains 500 negative samples and 268 positive samples, and Breast contains 241 negative samples and 458 positive samples. As we know, the positive samples describe the pathological features of diseases, so the positive samples should be classified much more precisely in terms of medical diagnosis. Validated by experiments,ρ=15 and 3 for Diabetes and Breast, respectively. The intuitionistic fuzzy parameters are selected by Algorithm 1, ω(y1) of appointed positive samples is 1.6, and ω(y2) of nonappointed negative samples is 0.3. The results are listed in Table 5.Table 5
Testing of appointed important samples.
Title
Training set
Tested data
Method
# s. v.
Training time (s)
Accuracy (%)
Std. of error (%)
Diabetes
Positive: 54Negative: 100
Positive: 67
KMP
32
0.014
66.67
3.14
IFKMP
33
0.016
98.45
2.76
PS-IFKMP
29
0.008
98.82
2.97
Breast
Positive: 60Negative: 115
Positive: 72
KMP
16
0.012
78.26
3.37
IFKMP
13
0.014
99.12
3.14
PS-IFKMP
15
0.009
98.92
3.07From Table5, facing imbalanced training set, standard KMP cannot classify the appointed important samples efficiently. IFKMP solves the aforementioned problem by assigning the intuitionistic fuzzy parameters to different samples and studying the weak samples sufficiently. Compared with IFKMP, the proposed PS-IFKMP algorithm can decrease training time obviously, and the classification accuracy is almost unchanged simultaneously.


## 4.2. Test on Artificial Data

Learning to tell two spirals apart is important both for purely academic reasons and for industrial application. In the research of the pattern recognition, it is a well-known problem for its difficulty. The parametric equation of the two spirals can be presented as follows:(26)Spiral-1:x1=k1θ+e1cos⁡θy1=k1θ+e1sinθaaaaθ∈U~0,2π,Spiral-2:x2=k2θ+e2cos⁡θy2=k2θ+e2sinθaaaaθ∈U~0,2π,where k1, k2, e1, and e2 are parameters. In our experiment, we choose k1=k2=4, e1=1, and e2=3. We generate 12000 samples randomly, and the samples distribution is shown in Figure 3(a). Moreover, a set of concentric circles samples also is selected to test our methods, and the parametric equation of the concentric circles data can be shown as (27)x=σ·cos⁡θy=σ·sinθθ∈U~0,2π.Parameter σ of the first class is of continuous uniform distribution U[0,55] and the second class σ~U[45,100]. 16000 samples are generated randomly, and the samples distribution is shown in Figure 3(b). Setting L=150, ε=0.02, N=50, itermax⁡=50, and ρ=8, the intuitionistic fuzzy parameters are selected by Algorithm 1; ω(y1) of appointed important samples (shown by “∙” in Figure 3) is 1.5 and ω(y2) of nonappointed samples (shown by “×” in Figure 3) is 0.3. Before the training, noise is added to training data, randomly choosing 10% samples and changing its class attributes. The results are listed in Table 6.Table 6
Testing of artificial dataset.
Title
Training set
Tested data
Method
# s. v.a
Training time (s)
Accuracy (%)
Std. of error (%)
Two spirals
Positive: 500Negative: 500
Positive: 1000
KMP
24
0.362
90.26
2.43
IFKMP
18
0.396
97.16
2.17
PS-IFKMP
15
0.047
98.12
1.85
Concentric circles
Positive: 500Negative: 500
Positive: 1000
KMP
200
0.453
91.13
1.96
IFKMP
165
0.470
99.03
1.22
PS-IFKMP
165
0.121
98.46
1.52Figure 3
The distribution map of artificial data.
(a)
The distribution map of two-spirals data
(b)
The distribution map of concentric circlesIn Table6, it is easily found that KMP cannot classify the appointed important samples efficiently when training Classifier with a subset of the data. IFKMP can classify the appointed important samples much more precisely by assigning the intuitionistic fuzzy parameters to different samples and studying the weak samples sufficiently. The proposed PS-IFKMP with advantage of both PSO and IFKMP reduces the training time enormously with the classification accuracy almost unchanged.


## 4.3. Test on Aerospace Target Data

In order to test the performance of the proposed PS-IFKMP algorithm in practical application, the aerospace targets data are selected for experiment. Generally, the threat degree of tactical ballistic missile (TBM), cruise missile (CM), and stealth aircraft (SA) is higher than the other targets, so we set these three targets as the appointed important targets. The radar cross section (RCS) values of the target are simulated by FEKO software, and the maximum, minimum, mean, and variance of RCS sequence are selected as sample features. And the RCS sequence of TBM within 30 seconds is showed in Figure4.Figure 4
RCS sequence of TBM within 30 s.Beside the appointed important targets, a large number of debris, baits, and other aircrafts, and so forth, are selected as negative samples. SettingL=200, ε=0.05, N=30, itermax⁡=50, and ρ=3.5, the ω(y1) of TBM equals 1.5, the ω(y2) of CM equals 1.3, and the ω(y3) of CM equals 1.6 by Algorithm 1. The results are listed in Table 7.Table 7
Testing of artificial dataset.
Title
Training set
Tested data
Method
Training time (s)
Accuracy (%)
Std. of error (%)
TBM
Positive: 122Negative: 478
Positive: 83
KMP
0.285
47.76
6.49
IFKMP
0.289
80.89
4.26
PS-IFKMP
0.116
81.65
4.75
CM
Positive: 223Negative: 387
Positive: 148
KMP
0.247
67.35
5.62
IFKMP
0.254
84.66
4.88
PS-IFKMP
0.095
85.99
4.37
SA
Positive: 188Negative: 412
Positive: 125
KMP
0.234
54.26
6.36
IFKMP
0.255
82.75
4.65
PS-IFKMP
0.130
82.51
5.02From Table7, by providing equal treatment on all training samples, the classical KMP algorithm cannot classify the weak important data efficiently. The IFKMP circumvents this problem by studying the important samples sufficiently and the less important samples roughly; however, the complexity problem still exists by adopting the greedy algorithm. By introducing particle swarm optimization algorithm, PS-IFKMP decreases the time complexity and reduces the training time with almost unchanged classification accuracy. It is also demonstrated that this approach is suitable to the application requiring both accuracy and timeliness.


## 5. Conclusion

Theoretically IFKMP algorithm is an excellent method but its implement is based on a greedy algorithm. Therefore, the defect of great computer time has not been solved when dealing with huge volume of data. In order to overcome the limitation, we propose the PS-IFKMP algorithm which optimizes searching process based on particle swarm optimization and reduces computational complexity of IFKMP algorithm. Simulation results show that, compared with the conventional approaches, the proposed algorithm can decrease training time and improve calculation efficiency obviously with the classification accuracy almost unchanged, especially for large size datasets. However, further improvements are needed by this algorithm, and the future research should focus on problems such as how to provide better multiclass recognition performance and how to select the parameters of the kernel function.



---

*Source: 587925-2015-06-01.xml*