# Particle Swarm for Attribute Selection in Bayesian Classification: An Application to Protein Function Prediction

Authors: ElonS. Correa; AlexA. Freitas; ColinG. Johnson
Journal: Journal of Artificial Evolution and Applications
 (2008-01-27)

---

## Abstract

The discrete particle swarm optimization (DPSO) algorithm is an
optimization technique which belongs to the fertile paradigm of Swarm Intelligence.
Designed for the task of attribute selection, the DPSO deals with discrete
variables in a straightforward manner. This work empowers the DPSO algorithm
by extending it in two ways. First, it enables the DPSO to select attributes for a
Bayesian network algorithm, which is more sophisticated than the Naive Bayes
classifier previously used by the original DPSO algorithm. Second, it applies the
DPSO to a set of challenging protein functional classification data, involving a
large number of classes to be predicted. The work then compares the performance
of the DPSO algorithm against the performance of a standard Binary PSO
algorithm on the task of selecting attributes on those data sets. The criteria used
for this comparison are (1) maximizing predictive accuracy and (2) finding the
smallest subset of attributes.


---

## Body

## 1. Introduction

Most of the particle swarm algorithms present in the
literature deal only with continuous variables [1–3]. This is a significant
limitation because many optimization problems are set in a search space
featuring discrete variables. Typical examples include problems which require
the ordering or arranging of discrete variables, such as scheduling or routing
problems [4].
Therefore, the design of particle swarm algorithms that deal directly with
discrete variables is pertinent to this field of study.The work in [5] proposed a discrete particle swarm optimization (PSO)
algorithm for attribute selection in Data Mining. Hereafter, this algorithm
will be refereed to as the discrete particle swarm optimization (DPSO) algorithm.
The DPSO deals directly with discrete variables, and its population of
candidate solutions contains particles of different sizes—the DPSO forces
each particle to carry a constant number of attributes across iterations. The
DPSO algorithm interprets the concept of velocity, used in traditional PSO, as
“probability;" renders velocity as a
proportional likelihood; and uses this information
to sample new particle positions. The motivation behind the DPSO algorithm is
indeed to introduce a probability-like approach to particle swarm.Although specifically designed for the task of
attribute selection, the DPSO is not limited to this kind of application. By
performing a few modifications, one can apply this algorithm to many other
discrete optimization problems, such as facility location problems [6].Many data mining applications involve the task of
building a model for predictive classification. The goal of such a model is to
classify examples—records or data instances—into classes or categories of
the same type. Noise or unnecessary attributes may reduce the accuracy and
reliability of a classification or prediction model. Unnecessary attributes also
increase the costs of building and running a model—particularly on large
data sets. Before performing classification, it is therefore important to
select an appropriate subset of “good" attributes. Attribute selection
tries to simplify a data set by reducing its dimensionality and identifying
relevant underlying attributes without sacrificing predictive accuracy. As a
result, it reduces redundancy in the information provided by the attributes
used for prediction. For a more detailed review of the attribute selection task
using genetic algorithms, see [7].The main difference between the DPSO and other
traditional PSO algorithms is that the particles in the DPSO do not represent
points inside ann-dimensional
Euclidean space (continuous case) or lattice (binary case) as in the standard
PSO algorithms [8].
Instead, they represent a combination of selected attributes. In previous work,
the DPSO was used to select attributes for a Naive Bayes (NB) classifier. The
resulting NB classifier was then used to predict postsynaptic function in
proteins.The study presented here extends previous work
reported in [5, 9] in two ways.
First, it enables the DPSO to select attributes for a Bayesian network
algorithm, which is more sophisticated than the Naive Bayes algorithm previously
used. Second, it increases the number of data sets used to evaluate the PSO
from 1 to 6. All the 6 functional classification data sets used have a much
greater number of classes to be predicted—in contrast with the postsynaptic
data set used in [5]
which had just two classes to be predicted.The work is organized as follows. Section2 briefly
addresses Bayesian networks and Naive Bayes classifier. Section 3 shortly
discusses PSO algorithms. Section 4 describes the standard binary PSO algorithm
and Section 5 the DPSO algorithm. Section 6 describes the G-protein-coupled
receptors (GPCRs) and Enzyme data sets used in the computational experiments.
Section 7 reports computational experiments—it also includes a discussion of
the results obtained. Section 8 presents conclusions and points out future
research directions.


## 2. Bayesian Networks and Naive Bayes

The Naive Bayes
(NB) classifier uses a probabilistic approach to assign each record of the data
set to a possible class. In this work, the NB classifier assigns a protein of a
data set of proteins to a possible class. A Naive Bayes classifier assumes that
all attributes are conditionally independent of one another given the class
[10].A Bayesian network (BN), by contrast, detects probabilistic
relationships among these attributes and uses this information to aid the
attribute selection process.Bayesian networks are graphical representations of a
probability distribution over a set of variables of a given problem domain
[11, 12]. This graphical
representation is a directed acyclic graph in which nodes represent the
variables of the problem and arcs represent conditional probabilistic
independencies among the nodes. A directed acyclic graph G is an ordered
pair G=(V,E), where V is a set whose
elements are called vertices or nodes and E is a set whose
elements are called directed edges, arcs, or arrows. The graph G contains no
directed cycles—for any vertex v∈V, there is no directed path that starts and ends on v.An example of a Bayesian network is as follows. (This is a modified version of
the so-called “Asia" problem [13].)
Suppose that a doctor is treating a patient who has been suffering from
shortness of breath—called dyspnoea. The doctor knows that diseases such as
tuberculosis, bronchitis, and lung cancer are possible causes for that. The
doctor also knows that other relevant information includes whether the patient
is a smoker—increasing the chances of lung cancer and bronchitis—and what
sort of air pollution the patient has been exposed to. A positive x-ray would
indicate either tuberculosis or lung cancer. The set of variables for this
problem and their possible values are shown in Table 1.Table 1
Bayesian network: nodes and values for the
lung cancer problem. L = low, H = high, T = true, F = false, Pos = positive,
and Neg = negative.
Node nameValuesPollution{L,H}Smoker{T,F}Cancer{T,F}Dyspnoea{T,F}X-ray{Pos,Neg}Figure1 shows a Bayesian network representing this
problem. For applications of Bayesian networks on evolutionary algorithms and
optimization problems, see [14, 15].Figure 1
A Bayesian
network representing the lung cancer problem.More formally, letX={X1,X2,…,Xn} be a
multivariate random variable whose components Xi are also random
variables. A corresponding lower-case letter xi denotes an
assignment of state or value to the random variable Xi. Parents(Xi) represent the
set of nodes—variables or attributes in this work—that have a directed
edge pointing to Xi. Let us consider a BN containing n nodes, X1 to Xn, taken in that order. A particular value of X={X1,X2,…,Xn} in the joint
probability distribution is represented by (1)p(X)=p(X1=x1,⁢X2=x2,…,Xn=xn), or more
compactly, p(x1,x2,...,xn). The chain rule of probability theory allows the
factorization of joint probabilities, therefore(2)p(X)=p(x1)p(x2∣x1)⋯p(xn∣x1,…,xn−1)=∏ip(xi∣x1,…,xi−1).As the structure of a BN implies that the value of a
particular node is conditional only on the values of its parent nodes, (2) may be
reduced to(3)p(X)=∏ip(Xi∣Parents(Xi)).Learning the structure of a BN is an NP-hard problem
[16, 17]. Many algorithms that were developed to this end use a scoring metric and a search procedure. The scoring
metric evaluates the goodness-of-fit of a structure to the data. The search
procedure generates alternative structures and selects the best one based on
the scoring metric. To reduce the search space of networks, only candidate
networks in which each node has at most k-inward arcs
(parents) are considered —k is a parameter
determined by the user. In the present work, k is set to 20 (k=20) to avoid overly complex models.A greedy search algorithm is used to generate
alternative structures for the BN starting with an empty network, the greedy
search algorithm adds into the network the edge that most increases the score
of the resulting network. The search stops when no other edge addition improves
the score of the network. Algorithm1 shows the pseudocode of this generic greedy
search algorithm.To evaluate the “goodness-of-fit” (score) of a
network structure to the data, an unconventional scoring metric—specific for
the target classification task—is adopted. The entire data set is divided
into mutually exclusive training and test sets—the standard methodology for
evaluating classifiers, see Section7.1. The training set is further divided
into two mutually exclusive parts. The first part is used to compute the
probabilities for the Bayesian network. The second part is used as the
validation set. During the search for the best possible network structure, only
the validation set is used to compute predictive accuracy. The score of a
candidate network is given by the classification accuracy in the validation
set. The graphical model of the network that shows the highest predictive
accuracy on the validation set—during the entire PSO run—is then used to
compute the predictive accuracy on the test set.Once the best network structure is selected, at the
end of the PSO run, the validation set and the other part of the training set
are merged and this merged data—that is, the entire original training set—is used to compute the probabilities for the selected Bayesian network. The
predicted accuracy—reported as the final result—is then computed on the
previously untouched test set. This process is discussed again, in more
details, in Section7.1. A similar process is adopted for the computation of
the predictive accuracy using the Naive Bayes classifier.


## 3. A Brief Introduction to Particle Swarm Optimization

Particle swarm optimization (PSO) comprises a set of
search techniques, inspired by the behavior of natural swarms, for solving
optimization problems [8]. In PSO, a potential solution to a problem is represented
by a particle, Y(i)=(Y(i,1),Y(i,2),…,Y(i,n)) in an n-dimensional
search space. Y(i) represents the ith particle in
the population and n represents the
number of variables of the problem. The coordinates Y(i,d) of these particles
have a rate of change (velocity) V(i,d), d=1,2,…,n. Note that the use of the double subscript notation
(i, d)
like in Y(i,d) represents the dth component of the ith particle in the swarm Y(i)—the same
rationale is used for V(i,d), and so forth.Every particle keeps a record of the best position
that it has ever visited. Such a record is called the particle's previous best
position and denoted byB(i). The global best position attained by any particle so
far is also recorded and stored in a particle denoted by G. An iteration
comprises evaluation of each particle, then stochastic adjustment of V(i,d) in the direction of particle Y(i)'s previous
best position and the previous best
position of any particle in the neighborhood [18]. There is much variety in
the neighborhood topology used in PSO, but quite often gbest or lbest topologies are used. In the gbest topology, the neighborhood of a
particle consists of all the other particles in the swarm, and therefore all
the particles will have the same global best neighbor—which is the best
particle in the entire population. In the lbest topology, each particle
has just a “local" set of neighbors, typically much fewer than the number
of particles in the swarm, and so different particles can have different best
local neighbors. For a review of the neighborhood topologies used in PSO the
reader is referred to [8, 19].As a whole, the set of rules that govern PSO are evaluate,
compare, and imitate. The evaluation phase measures how well each particle
(candidate solution) solves the problem at hand. The comparison phase
identifies the best particles. The imitation phase produces new particle
positions based on some of the best particles previously found. These three
phases are repeated until a given stopping criterion is met. The objective is
to find the particle that best solves the target problem.Important concepts in PSO are velocity and
neighborhood topology. Each particle,Y(i), is associated with a velocity vector. This velocity
vector is updated at every generation. The updated velocity vector is then used
to generate a new particle position Y(i). The neighborhood topology defines how other
particles in the swarm, such as B(i) and G,
interact with Y(i) to modify its
respective velocity vector and, consequently, its position as well.


## 4. The Standard Binary PSO Algorithm

Potential solutions to the target problem are encoded
as fixed size binary strings; that is,Y(i) = (Y(i,1),Y(i,2),…,Y(i,n)), where Y(i,j)∈{0,1}, i=1,2,…,N, and j=1,2,…,n [8]. Given a list of attributes A=(A1,A2,…,An), the first element of  Y(i), from the left to the right hand side, corresponds to
the first attribute “A1," the second
to the second attribute “A2," and so
forth. A value of 0 on the site associated to an attribute indicates that the
respective attribute is not selected. A value of 1 indicates that it is
selected.


### 4.1. The Initial Population for the
Standard Binary PSO Algorithm

For the initial
population,N binary strings
of size n are randomly
generated. Each particle Y(i) is generated
independently. For every position Y(i,d) in Y(i), a uniform random number φ is drawn on the
interval (0, 1). If φ<0.5, then Y(i,d)=1, otherwise Y(i,d)=0.


### 4.2. Updating the Records for the Standard Binary PSO Algorithm

At the
beginning, the previous best position ofY(i), denoted by B(i), is empty. Therefore, once the initial particle Y(i) is generated, B(i) is set to B(i) = Y(i). After that, every time that Y(i) is updated, B(i) is also updated
if f(Y(i)) is better than f(B(i)). Otherwise, B(i) remains as it
is. Note that f(⋅) represents the
fitness function used to measure the quality of the candidate solutions. A
similar process is used to update the global best position G. Once that
all the B(i) have been
determined, G is set to the fittest B(i) previously
computed. After that, G is updated if the fittest B(i) in the swarm is
better than G. And, in that case, f(G) is set to f(G) = f(fittest B(i)). Otherwise, G remains as it is.


### 4.3. Updating the Velocities for the Standard Binary PSO Algorithm

Every particleY(i) is associated
to a unique vector of velocities V(i) = (V(i,1),V(i,2),…,V(i,n)). Note that, for simplicity, this work uses row
vectors rather than column vectors. The elements V(i,d) in V(i) determine the
rate of change of each respective coordinate Y(i,d) in Y(i), d=1,2,…,n. Each element V(i,d)∈V(i) is updated
according to the equation
(4)V(i,d)=wV(i,d)+φ1(B(i,d)−Y(i,d))+φ2(G(d)−Y(i,d)),
where w (0<w<1), called the inertia weight, is a constant value
chosen by the user and d=1,2,…,n. Equation (4) is a standard equation used in PSO
algorithms to update the velocities [20, 21]. The factors φ1 and φ2 are uniform
random numbers independently generated in the interval (0, 1).


### 4.4. Sampling New Particle Positions for the Standard Binary PSO Algorithm

For each
particleY(i) and each
dimension d, the value of the new coordinate Y(i,d)∈Y(i) can be either 0
or 1. The decision of whether Y(i,d) will be 0 or 1
is based on its respective velocity V(i,d)∈V(i) and is given by
the equation
(5)Y(i,d)={1,if(rand<S(V(i,d))),0,otherwise;
where 0≤ rand ≤1 is a uniform
random number, and (6)S(V(i,d))=11+exp(−V(i,d)) is the sigmoid
function. Equation (5) is a standard equation used to sample new particle
positions in the binary PSO algorithm [8]. Note that the lower the value of V(i,d) is, the more
likely the value of Y(i,d) will be 0. By
contrast, the higher the value of V(i,d) is, the more
likely the value of Y(i,d) will be 1. The
motivation to use the sigmoid function is to map the interval [−V(i,d), V(i,d)]  for alli,d into the
interval (0, 1) which is equivalent to the interval of a probability function.


## 4.1. The Initial Population for the
Standard Binary PSO Algorithm

For the initial
population,N binary strings
of size n are randomly
generated. Each particle Y(i) is generated
independently. For every position Y(i,d) in Y(i), a uniform random number φ is drawn on the
interval (0, 1). If φ<0.5, then Y(i,d)=1, otherwise Y(i,d)=0.


## 4.2. Updating the Records for the Standard Binary PSO Algorithm

At the
beginning, the previous best position ofY(i), denoted by B(i), is empty. Therefore, once the initial particle Y(i) is generated, B(i) is set to B(i) = Y(i). After that, every time that Y(i) is updated, B(i) is also updated
if f(Y(i)) is better than f(B(i)). Otherwise, B(i) remains as it
is. Note that f(⋅) represents the
fitness function used to measure the quality of the candidate solutions. A
similar process is used to update the global best position G. Once that
all the B(i) have been
determined, G is set to the fittest B(i) previously
computed. After that, G is updated if the fittest B(i) in the swarm is
better than G. And, in that case, f(G) is set to f(G) = f(fittest B(i)). Otherwise, G remains as it is.


## 4.3. Updating the Velocities for the Standard Binary PSO Algorithm

Every particleY(i) is associated
to a unique vector of velocities V(i) = (V(i,1),V(i,2),…,V(i,n)). Note that, for simplicity, this work uses row
vectors rather than column vectors. The elements V(i,d) in V(i) determine the
rate of change of each respective coordinate Y(i,d) in Y(i), d=1,2,…,n. Each element V(i,d)∈V(i) is updated
according to the equation
(4)V(i,d)=wV(i,d)+φ1(B(i,d)−Y(i,d))+φ2(G(d)−Y(i,d)),
where w (0<w<1), called the inertia weight, is a constant value
chosen by the user and d=1,2,…,n. Equation (4) is a standard equation used in PSO
algorithms to update the velocities [20, 21]. The factors φ1 and φ2 are uniform
random numbers independently generated in the interval (0, 1).


## 4.4. Sampling New Particle Positions for the Standard Binary PSO Algorithm

For each
particleY(i) and each
dimension d, the value of the new coordinate Y(i,d)∈Y(i) can be either 0
or 1. The decision of whether Y(i,d) will be 0 or 1
is based on its respective velocity V(i,d)∈V(i) and is given by
the equation
(5)Y(i,d)={1,if(rand<S(V(i,d))),0,otherwise;
where 0≤ rand ≤1 is a uniform
random number, and (6)S(V(i,d))=11+exp(−V(i,d)) is the sigmoid
function. Equation (5) is a standard equation used to sample new particle
positions in the binary PSO algorithm [8]. Note that the lower the value of V(i,d) is, the more
likely the value of Y(i,d) will be 0. By
contrast, the higher the value of V(i,d) is, the more
likely the value of Y(i,d) will be 1. The
motivation to use the sigmoid function is to map the interval [−V(i,d), V(i,d)]  for alli,d into the
interval (0, 1) which is equivalent to the interval of a probability function.


## 5. The Discrete PSO (DPSO) Algorithm

The DPSO
algorithm deals directly with discrete variables
(attributes) and, unlike the binary PSO algorithm, its population of candidate
solutions contains particles of different sizes. Potential solutions to the
optimization problem at hand are represented by a swarm of particles. There areN particles in a
swarm. The size of each particle may vary from 1 to n, where n is the number
of variables—attributes in this work—of the problem. In this context, the
size of a particle refers to the number of different attribute indices that the
particle is able to represent at a single time.For example, giveni,j∈{1,2,…,N}, in DPSO it may occur that a particle Z(i) in the
population has size 6 (Z(i)={*,*,*,*,*,*}), whereas another particle Z(j) in the same
population has size 2 (Z(i)={*,*}), and so
forth, or any other sizes between 1 and n.Each particleZ(i) keeps a record
of the best position it has ever attained. This information is stored in a
separate vector labeled as B(i). The swarm also keeps a record of the global best
position ever attained by any particle in the swarm. This information is also
stored in a separate vector labeled G. Note that G is equal to
the best B(i) present in the
swarm.


### 5.1. Encoding of the Particles for the
DPSO Algorithm

Each attribute
is represented by a unique positive integer number, or index. These numbers,
indices, vary from 1 ton. A particle is a subset of nonordered indices without
repetition, for example, Z(k)={2,4,18,1}, k∈{1,2,…,N}.


### 5.2. The Initial Population for the DPSO
Algorithm

The original work on DPSO [5] used a randomly generated
initial population for the standard PSO algorithm and a new randomly generated
initial population for the DPSO algorithm, when comparing these algorithms'
performances in a given data set. However, the way in which those populations
were initialized generated a doubt about a possible advantage of one initial
population over the other—which would bias the performance of one algorithm
over the other. In this work, to eliminate this possible bias, the initial
population used by the DPSO is always identical to the initial population used
by the binary PSO. They differ only in the way in which solutions are
represented. The conversion of every particle in the initial population of
solutions of the binary PSO to the Discrete PSO initial population is as
follows.The index of every attribute that has value 1 is
copied to the new solution (particle) of the DPSO initial population. For
instance, an initial candidate solution for the binary PSO algorithm equal toY(k)=(1,0,1,1,0) is converted into Z(k)={1,3,4} for
the DPSO algorithm—because attributes A1, A3, and A4 are set to 1
(are present) in Y(k), k∈{1,2,…,N}. Note that the same initial population of solutions
is used to both algorithms, binary PSO and DPSO, to make the comparison between
the performances of these algorithms as free from initialization bias as
possible.Initializing the particlesZ(i) in this way
causes different particles, in DPSO, to have different sizes. For instance, an
initial candidate solution Y(j)=(1,1,0,0,0) (from the binary PSO algorithm) is converted into the initial candidate
solution Z(j)={1,2} (to the
DPSO algorithm) which has size 2, whereas another initial candidate solution Y(k)=(0,1,1,1,1) (binary PSO) is converted into the initial candidate solution Z(k)={2,3,4,5}
(DPSO) which has size 4, j,k∈{1,2,…,N} and n=5.In the DPSO algorithm, for simplicity, once the size
of a particle is determined at the initialization, the particle will keep that
same size during the entire execution of the algorithm. For example, particleZ(k)={2,3,4,5}
above, which has been initialized with 4 indices, will always carry exactly 4
indices, Z(k)={*,*,*,*}.
The values of those 4 indices, however, are likely to change every time that
the particle is updated.


### 5.3. Velocities = Proportional Likelihoods

The DPSO
algorithm does not use a vector of velocities as the standard PSO algorithm
does. It works with proportional likelihoods instead. Arguably, the notion of
proportional likelihood used in the DPSO algorithm and the notion of velocity
used in the standard PSO are somewhat similar. DPSO usesM(i) to represent an
array of proportional likelihoods and M(i,d) to represent
one of M(i)'s components.Every particle in DPSO is associated with a 2-by-n array of
proportional likelihoods, where 2 is the number of rows in this array and n is the number
of columns—note that the number of columns in M(i) is equal to the
number of variables of the problem n.This is an example of a generic proportional
likelihood array(7)M(i)=(proportional‐likelihood‐rowattribute‐index‐row). Each of the n elements in the
first row of M(i) represents the
proportional likelihood that an attribute be selected. The second row of M(i) shows the
indices of the attributes associated with the respective proportional
likelihoods.There is a one-to-one correspondence between the
columns of this array and the attributes of the problem domain. At the
beginning, all elements in the first row ofM(i) are set to 1,
for example,
(8)M(i)=(1.01.01.01.01.012345). After the
initial population of particles is generated, this array is always updated
before a new configuration for the particle associated to it is generated. The
updating of the likelihoods M(i,d) is based on Z(i), B(i), G and three constant updating factors,
namely, α, β, and γ. The updating factors (α, β, and γ) determine the
strength of the contribution of Z(i), B(i), and G to the adjustment of every coordinate M(i,d)∈M(i).Note thatα, β, and γ are parameters chosen
by the user. The contribution of these parameters to the updating of M(i,d) is as follows.
All indices present in Z(i) have their
correspondent proportional likelihood increased by α. In addition to that, all indices present in B(i) have their
correspondent proportional likelihood increased by β. The same for G for which the proportional
likelihoods are increased by γ.For instance, givenn=5, α=0.10, β=0.12, γ=0.14, Z(i)={2,3,4}, B(i)={3,5,2}, G={5,2}, and also (9)M(i)=(1.01.01.01.01.012345),the updated  M(i) would be(10)M(i)=((1.0)(1.0+α+β+γ)(1.0+α+β)(1.0+α)(1.0+β+γ)12345).Note that index 1 is absent inZ(i), B(i), and G. Therefore, the proportional likelihood
of attribute 1 in M(i) remains as it
is. In this work, the values used for α, β, and γ were α=0.10, β=0.12, and γ=0.14. These
values were empirically determined in preliminary experiments; but this work
makes no claim that these are optimal values. Parameter optimization is a topic
for future research. As a whole, these values make the contribution of B(i) (β=0.12) to the updating of the V(i) a bit stronger
than the contribution of Z(i) (α=0.10); and the contribution of G (γ=0.14) even stronger.The new updated arrayM(i) replaces the
old one and will be used to generate a new configuration to the particle
associated to it as follows.


### 5.4. Sampling New Particle Positions for
the DPSO Algorithm

The
proportional likelihood arrayM(i) is then used to
sample a new instance of particle Z(i)—the particle
associated to M(i). For this sampling process, a series of operations is
performed on the array. To start with, every element of the first row of the
array M(i) is multiplied
by a uniform random number between 0 and 1. A new random number is drawn for
every single multiplication performed.To illustrate, suppose that(11)M(i)=(1.001.361.221.101.2612345). The multiplied
proportional likelihood array would be (12)M(i)=((1.00⋅φ1)(1.36⋅φ2)(1.22⋅φ3)(1.10⋅φ4)(1.26⋅φ5)12345),where φ1,…,φ5 are uniform
random numbers independently drawn on the interval (0, 1).Suppose that this is the resulting arrayM(i) after the
multiplication (13)M(i)=(0.110.860.570.621.0912345).A new particle position is then defined by ranking the
columns inM(i) by the values
in its first row. That is, the elements in the first row of the array are
ranked in a decreasing order of value; and the indices of the attributes—in
the second row of M(i)—follow their
respective proportional likelihoods. For example, ranking the array M(i) (shown
immediately above) would generate (14)M(i)=(1.090.860.620.570.1152431).The next operation now is to select the indices that
will compose the new particle position. After ranking the arrayM(i), the first si indices (in the
second row of M(i)), from left to
right, are selected to compose the new particle position. Note that si represents the
size of the particle Z(i)—the particle
associated to the ranked array M(i).Suppose that
the particleZ(i) associated to (15)M(i)=(1.090.860.620.570.1152431)  has size 3 (Z(i)={*,*,*}).
That makes si=3—note
that Z(j), for instance, may have a different size and
consequently a different sj value. For the Z(i) above, however,
as si=3 the first 3
indices from the second row of M(i) would be
selected to compose the new particle position. Based on the array M(i) given above and si=3, the
indices (attributes) 5, 2, and 4 would be selected to compose the new particle
position, that is, Z(i)={5,2,4}. Note
that indices that have a higher proportional likelihood are, on average, more
likely to be selected.The updating ofZ(i), B(i), and G follows what is described in Section
4.2.Once the algorithms have been explained, the next
section briefly introduces the particular data sets (case studies) used to test
the algorithms.


## 5.1. Encoding of the Particles for the
DPSO Algorithm

Each attribute
is represented by a unique positive integer number, or index. These numbers,
indices, vary from 1 ton. A particle is a subset of nonordered indices without
repetition, for example, Z(k)={2,4,18,1}, k∈{1,2,…,N}.


## 5.2. The Initial Population for the DPSO
Algorithm

The original work on DPSO [5] used a randomly generated
initial population for the standard PSO algorithm and a new randomly generated
initial population for the DPSO algorithm, when comparing these algorithms'
performances in a given data set. However, the way in which those populations
were initialized generated a doubt about a possible advantage of one initial
population over the other—which would bias the performance of one algorithm
over the other. In this work, to eliminate this possible bias, the initial
population used by the DPSO is always identical to the initial population used
by the binary PSO. They differ only in the way in which solutions are
represented. The conversion of every particle in the initial population of
solutions of the binary PSO to the Discrete PSO initial population is as
follows.The index of every attribute that has value 1 is
copied to the new solution (particle) of the DPSO initial population. For
instance, an initial candidate solution for the binary PSO algorithm equal toY(k)=(1,0,1,1,0) is converted into Z(k)={1,3,4} for
the DPSO algorithm—because attributes A1, A3, and A4 are set to 1
(are present) in Y(k), k∈{1,2,…,N}. Note that the same initial population of solutions
is used to both algorithms, binary PSO and DPSO, to make the comparison between
the performances of these algorithms as free from initialization bias as
possible.Initializing the particlesZ(i) in this way
causes different particles, in DPSO, to have different sizes. For instance, an
initial candidate solution Y(j)=(1,1,0,0,0) (from the binary PSO algorithm) is converted into the initial candidate
solution Z(j)={1,2} (to the
DPSO algorithm) which has size 2, whereas another initial candidate solution Y(k)=(0,1,1,1,1) (binary PSO) is converted into the initial candidate solution Z(k)={2,3,4,5}
(DPSO) which has size 4, j,k∈{1,2,…,N} and n=5.In the DPSO algorithm, for simplicity, once the size
of a particle is determined at the initialization, the particle will keep that
same size during the entire execution of the algorithm. For example, particleZ(k)={2,3,4,5}
above, which has been initialized with 4 indices, will always carry exactly 4
indices, Z(k)={*,*,*,*}.
The values of those 4 indices, however, are likely to change every time that
the particle is updated.


## 5.3. Velocities = Proportional Likelihoods

The DPSO
algorithm does not use a vector of velocities as the standard PSO algorithm
does. It works with proportional likelihoods instead. Arguably, the notion of
proportional likelihood used in the DPSO algorithm and the notion of velocity
used in the standard PSO are somewhat similar. DPSO usesM(i) to represent an
array of proportional likelihoods and M(i,d) to represent
one of M(i)'s components.Every particle in DPSO is associated with a 2-by-n array of
proportional likelihoods, where 2 is the number of rows in this array and n is the number
of columns—note that the number of columns in M(i) is equal to the
number of variables of the problem n.This is an example of a generic proportional
likelihood array(7)M(i)=(proportional‐likelihood‐rowattribute‐index‐row). Each of the n elements in the
first row of M(i) represents the
proportional likelihood that an attribute be selected. The second row of M(i) shows the
indices of the attributes associated with the respective proportional
likelihoods.There is a one-to-one correspondence between the
columns of this array and the attributes of the problem domain. At the
beginning, all elements in the first row ofM(i) are set to 1,
for example,
(8)M(i)=(1.01.01.01.01.012345). After the
initial population of particles is generated, this array is always updated
before a new configuration for the particle associated to it is generated. The
updating of the likelihoods M(i,d) is based on Z(i), B(i), G and three constant updating factors,
namely, α, β, and γ. The updating factors (α, β, and γ) determine the
strength of the contribution of Z(i), B(i), and G to the adjustment of every coordinate M(i,d)∈M(i).Note thatα, β, and γ are parameters chosen
by the user. The contribution of these parameters to the updating of M(i,d) is as follows.
All indices present in Z(i) have their
correspondent proportional likelihood increased by α. In addition to that, all indices present in B(i) have their
correspondent proportional likelihood increased by β. The same for G for which the proportional
likelihoods are increased by γ.For instance, givenn=5, α=0.10, β=0.12, γ=0.14, Z(i)={2,3,4}, B(i)={3,5,2}, G={5,2}, and also (9)M(i)=(1.01.01.01.01.012345),the updated  M(i) would be(10)M(i)=((1.0)(1.0+α+β+γ)(1.0+α+β)(1.0+α)(1.0+β+γ)12345).Note that index 1 is absent inZ(i), B(i), and G. Therefore, the proportional likelihood
of attribute 1 in M(i) remains as it
is. In this work, the values used for α, β, and γ were α=0.10, β=0.12, and γ=0.14. These
values were empirically determined in preliminary experiments; but this work
makes no claim that these are optimal values. Parameter optimization is a topic
for future research. As a whole, these values make the contribution of B(i) (β=0.12) to the updating of the V(i) a bit stronger
than the contribution of Z(i) (α=0.10); and the contribution of G (γ=0.14) even stronger.The new updated arrayM(i) replaces the
old one and will be used to generate a new configuration to the particle
associated to it as follows.


## 5.4. Sampling New Particle Positions for
the DPSO Algorithm

The
proportional likelihood arrayM(i) is then used to
sample a new instance of particle Z(i)—the particle
associated to M(i). For this sampling process, a series of operations is
performed on the array. To start with, every element of the first row of the
array M(i) is multiplied
by a uniform random number between 0 and 1. A new random number is drawn for
every single multiplication performed.To illustrate, suppose that(11)M(i)=(1.001.361.221.101.2612345). The multiplied
proportional likelihood array would be (12)M(i)=((1.00⋅φ1)(1.36⋅φ2)(1.22⋅φ3)(1.10⋅φ4)(1.26⋅φ5)12345),where φ1,…,φ5 are uniform
random numbers independently drawn on the interval (0, 1).Suppose that this is the resulting arrayM(i) after the
multiplication (13)M(i)=(0.110.860.570.621.0912345).A new particle position is then defined by ranking the
columns inM(i) by the values
in its first row. That is, the elements in the first row of the array are
ranked in a decreasing order of value; and the indices of the attributes—in
the second row of M(i)—follow their
respective proportional likelihoods. For example, ranking the array M(i) (shown
immediately above) would generate (14)M(i)=(1.090.860.620.570.1152431).The next operation now is to select the indices that
will compose the new particle position. After ranking the arrayM(i), the first si indices (in the
second row of M(i)), from left to
right, are selected to compose the new particle position. Note that si represents the
size of the particle Z(i)—the particle
associated to the ranked array M(i).Suppose that
the particleZ(i) associated to (15)M(i)=(1.090.860.620.570.1152431)  has size 3 (Z(i)={*,*,*}).
That makes si=3—note
that Z(j), for instance, may have a different size and
consequently a different sj value. For the Z(i) above, however,
as si=3 the first 3
indices from the second row of M(i) would be
selected to compose the new particle position. Based on the array M(i) given above and si=3, the
indices (attributes) 5, 2, and 4 would be selected to compose the new particle
position, that is, Z(i)={5,2,4}. Note
that indices that have a higher proportional likelihood are, on average, more
likely to be selected.The updating ofZ(i), B(i), and G follows what is described in Section
4.2.Once the algorithms have been explained, the next
section briefly introduces the particular data sets (case studies) used to test
the algorithms.


## 6. Case Study: the GPCR and Enzyme Data Sets Used in the Computational Experiments

The experiments involved 6 data sets comprising two
kinds of proteins, namely, G-protein-coupled receptors (GPCRs) and Enzymes.The G-protein-coupled receptors (GPCRs) are a protein
superfamily of transmembrane receptors. Their function is to transduce signals
that induce a cellular response to the environment. GPCRs are involved in many
types of stimulus-response pathways, from intercellular communication to
physiological senses. GPCRs are of much interest to the pharmaceutical industry
because these proteins are involved in many pathological conditions—it is
estimated that GPCRs are the target of 40% to 50% of modern medical drugs [22]Enzymes are proteins that
accelerate chemical reactions—they participate in many processes in a
biological cell. Some enzymes are used in the chemical industry and other
industrial applications where extremely specific catalysts are required. In
Enzyme Nomenclature, enzymes are assigned and identified by an Enzyme Commission
(EC) number. For instance, EC 2.3.4 is an enzyme with class value 2 in the
first hierarchical class level, class value 3 in the second class level, and so forth.
This work uses the GPCRs and EC data sets described in Table2.Table 2
GPCR and EC data sets. “Cases" represents the
number of proteins in the data set, “Attributes" represents the total
number of attributes that describe the proteins in
the data set, and “L1",…, “L4" represent the number of classes at
hierarchical class levels 1,…, 4, respectively.
# Classes atData setCasesAttributesL1L2L3L4GPCR-PRINTS3302818365244GPCR-PROSITE19012783232—GPCR-InterPro58044812436746EC-PRINTS50038064383—EC-PROSITE57058364284—EC-Pfam73070664192—These
data sets were derived from the data sets used in [23, 24]. Note that both the GPCR
and the Enzyme data sets have hierarchical classes. Each protein in these data
sets is assigned one class at the first (top) hierarchical level, corresponding
to a broad function, another class at the second level, corresponding to a more
specialized function, and another class at the third level, corresponding to an
even more specialized function, and so forth. This work copes with these hierarchical
classes in a simple way by predicting classes one level at a time, as explained
in more detail later.The data sets used in the experiments involved four
kinds of protein signatures (biological “motifs"), namely, PROSITE
patterns, PRINTS fingerprints, InterPro entries, and Pfam signatures.PROSITE is a database of protein families and domains.
It is based on the observation that, while there is a huge number of different
proteins, most of them can be grouped, on the basis of similarities in their
sequences, into a limited number of families (a protein consists of a sequence
of amino acids). PROSITE patterns are essentially regular expressions
describing small regions of a protein sequence which present a high sequence
similarity when compared to other proteins in the same functional family.In the data sets, the absence of a given PROSITE
pattern is indicated by a value of 0 for the attribute corresponding to that
PROSITE pattern. The presence of it is indicated by a value of 1 for that same
attribute.PRINTS is a compendium of protein fingerprints. A
fingerprint is a group of conserved motifs used to characterize a protein
family. In the PRINTS data sets, a fingerprint corresponds to an attribute. The
presence of a fingerprint is indicated by a value of 1 for that same attribute;
the absence by a 0.Pfam signatures are produced by hidden Markov models,
and InterPro integrates a number of protein signature databases into a single
database. In this work, Pfam and InterPro entries also correspond to binary
attributes indicating whether or not a protein matches those entries, using the
same codification described for the PROSITE patterns and Fingerprints.The objective of the binary PSO and DPSO algorithms is
to classify each protein into its most suitable functional class level. The
classification of the proteins is performed in each class level individually.
For instance, given proteinϒ, at first, a conventional “flat” classification algorithm
assigns a class to ϒ at the first
class level only. Once ϒ has been
classified at the first class level, the conventional flat classification
algorithm is again applied to assign a class to ϒ at the second
level—no information about ϒ's class at the
previous level is used. The same process is used to assign a class to protein ϒ at the third
class level, and so forth.


## 7. Experiments

The quality of
a candidate solution (fitness) is evaluated in three different ways: (1) by a
baseline algorithm—using all possible attributes; (2) by the binary PSO—using
only the attributes selected by this algorithm; and (3) by the discrete PSO
(DPSO) algorithm—using only the attributes selected by this algorithm. Each
of these algorithms computes the fitness of every given solution using two
distinct techniques: (a) using a Naive Bayes classifier; and (b) using a
Bayesian network.


### 7.1. Experimental Methodology

Note that the
computation of the fitness functionf(⋅) for the
particles Y(i) (binary PSO
algorithm) and Z(i) (DPSO
algorithm) follows the description given below. For simplicity, only the
process using Y(i) is described—but the same is applicable to Z(i). f(Y(i)) is equal to
the predictive accuracy achieved by the Naive Bayes classifier—and the
Bayesian network—on each data set and using only the attributes selected in Y(i).The measurement off(Y(i)) follows a
wrapper approach. The wrapper approach searches for an optimal attribute subset
tailored to a particular algorithm, such as the Naive Bayes classifier or
Bayesian network. For more information on wrapper and other attribute selection
approaches, see [25].The computational experiments involved a 10-fold
crossvalidation method [25]. First, the data set being considered is divided into
10 equally sized folds. The folds are randomly generated but under the
following criterion. The proportion of classes in every single fold must be
similar to the proportion of classes found in the original data set containing
all records. This is known as stratified crossvalidation.Each of the 10 folds is used once as a test set and
the remaining of the data is used as training set. Out of the 9 folds in the
training set one is reserved to be used as a validation set. The Naive Bayes
classifier and the Bayesian network use the remaining 8 folds to compute the
probabilities required to classify new examples. Once those probabilities have
been computed, the Naive Bayes (NB) classifier and the Bayesian network (BN)
classify the examples in the validation set.The accuracy of this classification on the validation
set is the value of the fitness functionsfNB (Y(i)) and fBN (Y(i))—the same
for fNB (Z(i)) and fBN (Z(i)). When the run
of the PSO algorithm is completed, the 9 folds are merged into a full training
set. The Naive Bayes classifier and the Bayesian network are then trained again
on this full-training set (9 merged folds), and the probabilities computed in
this final, full-training set are used to classify examples in the test set
(the 10th fold), which was never accessed during the run of the algorithms.The reasons for having separate validation and test
sets are as follows. In the classification task of data mining, by definition,
the goal is to measure predictive accuracy—generalization ability—on a
test set unseen during training. Hence, the test set cannot be accessed by the
PSO, and is reserved just to compute the predictive accuracy associated with
the Bayesian classifier constructed with the best set of attributes selected at
the end of the PSO run.Concerning the validation set, which is used to
compute the fitness of particles during the PSO run, this is a part of the
original training set which is different from the part of the training set used
to build the Bayesian classifier, and the reason for having these two separate
parts of the training set is to avoid overfitting of the classifier to the
training data; for overfitting in the context of classification, see [7, pages 17, 18]. In other
words, if the same training set that was used to build a Bayesian classifier
was also used to measure the fitness (accuracy) of the corresponding particle,
there would be no pressure to build classifiers with a good generalization
ability on data unseen during training, and a classifier could obtain a high
accuracy by simply being overfitted to idiosyncrasies of the training set which
are unlikely to generalize well to unseen data. By measuring fitness on a
validation set separated from the data used to build the classifier, this is
avoided, and a pressure to build classifiers with good generalization ability
is introduced in the fitness function.In each of the 10 iterations of the crossvalidation
procedure, the predictive accuracy of the classification is assessed by 3
different methods, as follows.(1)
Using all
possible original attributes: all possible attributes are used by the Naive
Bayes classifier and the Bayesian network—there is no attribute selection.(2)
Standard
binary PSO algorithm: only the attributes selected by the best particle
found by the binary PSO algorithm are used by the Naive Bayes classifier and
the Bayesian network.(3)
DPSO
algorithm: only the attributes selected by the best particle found by the
DPSO algorithm are used by the Naive Bayes classifier and the Bayesian network.Since the Naive Bayes and Bayesian network classifiers
used in this work are deterministic, only one run—for each of these
algorithms—is performed for the classification using all possible
attributes.For the binary PSO and the DPSO algorithms, 30
independent runs are performed for each iteration of the crossvalidation
procedure. The results reported are averaged over these 30 independent runs and
over the 10 iterations of the crossvalidation procedure.The population size used for both algorithms (binary
PSO and DPSO) is 200 and the search stops after 20 000 fitness evaluations—or 100 iterations.The binary PSO algorithm uses an inertia weight value
of 0.8 (i.e.,w=0.8). The
choice of the value of this parameter was based on the work presented in
[26].Other choices of parameter values for the DPSO wereα=0.10, β=0.12, and γ=0.14, chosen
based on empirical experiments but probably not optimal values.The measurement of the predictive accuracy rate of a
model should be a reliable estimate of how well that model classifies the test
examples—unseen during the training phase—on the target problem.In Data Mining, typically, the
equation(16)standardaccuracyrate=TP+TNTP+FP+FN+TNis used to assess the accuracy
rate of a classifier—where TP, TN, FP, and FN are the numbers
of true positives, true negatives, false positives, and false negatives,
respectively [25].However, if the class distribution is highly
unbalanced, (16) is an ineffective way of measuring the accuracy rate
of a model. For instance, in many problems, it is easy to achieve a high value
for (16) by
simply predicting always the majority class. Therefore, on the experiments
reported on this work, a more demanding measurement for the accuracy rate of a
classification model is used.This measurement has been used before in [27]. It is given by the
equation
(17)predictiveaccuracyrate=TPR⋅TNR,
where, TPR = TP/(TP+FN) and TNR = TN/(TN+FP)—TPR stands for true
positive rate and TNR stands for true
negative rate.Note that if any of the quantitiesTPR or TNR is zero, the
value returned by (17) is also zero.


### 7.2. Discussion

Computational
results are reported in Tables5 and 6. Let us focus the discussion on the
results obtained by the 3 algorithms (binary PSO, DPSO, and baseline algorithm)
for attribute selection on the GPCR-PROSITE data set, see Table 5. The results
obtained for the other 5 data sets are similar. To start with, the results
obtained using the Naive Bayes classifier are presented.Results obtained using the Naive Bayes classifier
approach
To assess the performance of the algorithms, two
criteria were considered: (1) maximizing predictive accuracy; and (2) finding
the smallest subset of attributes.The results for the first criterion, accuracy, show
that both versions of the PSO algorithm did better—in all class levels—than the baseline algorithm using all attributes.Furthermore, the DPSO algorithm did slightly better
than the binary PSO algorithm also in all class levels. Nevertheless, the
difference in the predictive accuracy performance between these algorithms is,
in some cases, statistically insignificant.Table3 shows the results of a paired two-tailed t-test for the
predictive accuracy of the binary PSO versus the predictive accuracy of the
DPSO at a significance level of 0.05.Table 3
Predictive accuracy:
binary PSO versus DPSO. Paired two-tailedt test for the
predictive accuracy—significance level 0.05.
Class levelNaive BayesBayesian network1t(9) = 0.467, p = 0.651t(9) = 3.407, p = 0.0072t(9) = 2.221, p = 0.053t(9) = 3.200, p = 0.0103t(9) = 3.307, p = 0.009t(9) = 3.556, p = 0.006Table3 shows that, using Naive Bayes as classifier,
the only statistically significant difference in performance—in terms of
predictive accuracy—between the algorithms binary PSO and DPSO is at the
third class level. By contrast, using Bayesian networks as classifier, the
difference in performance is statistically significant at all class levels.Nevertheless, the discriminating factor between the
performance of these algorithms is on the second comparison criterion—finding
the smallest subset of attributes.The DPSO not only outperformed the binary PSO in
predictive accuracy, but also did so using a smaller subset of attributes in
all class levels. Moreover, when it comes to effectively pruning the set of
attributes, the difference in performance between the binary PSO and the DPSO
is always statistically significant, as Table4 shows.Table 4
Number of selected attributes: binary PSO versus DPSO. Paired two-tailedt test for the
number of attributes selected—significance level 0.05.
Class levelNaive BayesBayesian network1t(9) = 7.248, p = 4.8E-5t(9) = 8.2770, p = 1.6E-52t(9) = 9.052, p = 8.1E-6t(9) = 14.890, p = 1.2E-73t(9) = 6.887, p = 7.1E-5t(9) = 9.1730, p = 7.3E-6Table 5
Results for the
GPCRs data sets. For the binary PSO and DPSO algorithms, 30 independent runs
are performed. The results reported are averaged over these 30 independent
runs. The best result on each line for each performance criterion is marked
with an asterisk (*).
GPCR-PRINTS (281 attributes)Average predictive accuracyAverage number of selected attributesMethodClass levelUsing all attributesBinary PSODiscrete PSOBinary PSODiscrete PSONaive Bayes172.36± 2.6473.10± 2.71*73.98 ± 3.1397.40± 1.26*73.30 ± 4.35235.56± 2.5637.10± 3.10*40.74 ± 5.36130.30± 1.34*117.30 ± 6.04327.00± 1.8229.05± 2.71*31.55 ± 4.54171.10± 3.93*145.70 ± 3.80424.26± 1.7526.97± 2.24*30.14 ± 3.78165.00± 4.11*141.30 ± 5.21Bayesian network188.67± 1.7289.46± 1.73*89.97 ± 2.1189.30± 3.77*63.80 ± 3.99253.46± 1.4056.75± 2.47*58.91 ± 3.95123.70± 3.89*103.00 ± 4.27338.93± 1.9243.08± 3.03*50.33 ± 6.45158.20± 4.21*134.50 ± 4.60428.47± 1.9030.56± 2.63*39.52 ± 5.32152.60± 3.53*126.80 ± 4.59GPCR-PROSITE (127 attributes)Average predictive accuracyAverage number of selected attributesMethodClass levelUsing all attributesBinary PSODiscrete PSODiscrete PSOBinary PSONaive Bayes171.27± 2.0872.88± 2.40*73.05 ± 2.3185.60± 2.84*74.90 ± 3.48230.00± 2.1031.34± 2.47*32.60 ± 2.31101.50± 3.14*83.80 ± 4.64320.47± 0.9621.47± 1.16*23.25 ± 1.08102.30± 3.77*87.50 ± 4.25Bayesian network178.05± 2.3379.03± 2.57*80.54 ± 2.4678.50± 3.50*65.50 ± 3.41239.08± 2.6740.31± 2.85*43.24 ± 4.6794.10± 3.70*73.30 ± 2.67324.70± 1.8326.14± 2.11*28.97 ± 2.7794.90± 3.90*77.60 ± 4.35GPCR-INTERPRO (448 attributes)Average predictive accuracyAverage number of selected attributesMethodClass levelUsing all attributesBinary PSODiscrete PSOBinary PSODiscrete PSONaive Bayes154.17± 2.2655.33± 2.36*56.55 ± 2.61136.40± 1.17*120.70 ± 5.01225.19± 1.5026.08± 1.62*27.27 ± 1.87158.60± 1.07*136.20 ± 5.53320.03± 0.6521.19± 1.03*22.03 ± 1.63203.60± 1.26*162.40 ± 6.62427.97± 1.1329.95± 2.18*30.43 ± 2.56168.00± 0.94*150.10 ± 7.31Bayesian network186.68± 2.9989.20± 3.06*89.49 ± 4.28122.60± 4.03*107.70 ± 5.12261.85± 1.7164.57± 1.43*68.66 ± 3.82146.80± 3.12*128.40 ± 5.02340.77± 2.1344.11± 2.48*46.51 ± 3.41184.60± 2.41*148.10 ± 3.98434.05± 1.6436.89± 2.56*39.03 ± 3.63149.70± 2.41*131.50 ± 4.12Table 6
Results for the
EC data sets. For the binary PSO and the DPSO algorithms, 30 independent runs are
performed. The results reported are averaged over these 30 independent runs.
The best result on each line for each performance criterion is marked with an
asterisk (*).
EC-PRINTS (380 attributes)Average predictive accuracyAverage number of selected attributesMETHODClass levelUsing all attributesSBinary PSODiscrete PSOBinary PSODiscrete PSONaive Bayes172.35± 3.3373.78± 3.78*74.81 ± 3.79102.80± 1.23*64.20 ± 4.37231.19± 2.2632.07± 2.48*34.06 ± 2.91149.00± 1.25*112.30 ± 3.06323.37± 1.7324.64± 2.01*26.97 ± 2.49211.10± 1.37*150.60 ± 5.58Bayesian network188.30± 1.9489.51± 2.51*90.73 ± 2.5992.80± 4.57*48.90 ± 4.68253.15± 1.4955.14± 1.87*56.92 ± 2.93129.70± 4.11*102.00 ± 5.52336.24± 1.6238.26± 2.65*40.95 ± 4.16190.40± 4.55*135.10 ± 4.28EC-PROSITE (583 attributes)Average predictive accuracyAverage number of selected attributesMETHODClass levelUsing all attributesBinary PSODiscrete PSOBinary PSODiscrete PSONaive Bayes169.52± 5.0270.37± 5.15*72.31 ± 5.44118.80± 1.14*98.90 ± 1.85235.70± 1.7337.73± 2.04*38.83 ± 2.66154.50± 0.85*134.90 ± 4.93321.91± 1.1322.86± 1.30*24.36 ± 1.66197.70± 1.16*154.50 ± 5.34Bayesian network182.80± 1.0984.83± 1.46*85.95 ± 2.31105.00± 3.62*92.70 ± 4.00245.30± 2.4147.82± 2.80*49.50 ± 3.33135.20± 3.65*119.00 ± 3.89328.44± 2.3729.40± 2.64*32.52 ± 3.71172.00± 2.94*146.50 ± 4.40EC-PFAM (706 attributes)Average predictive accuracyAverage number of selected attributesMETHODClass levelUsing all attributesBinary PSODiscrete PSOBinary PSODiscrete PSONaive Bayes171.61± 3.5272.87± 4.02*74.62 ± 3.77131.60± 5.50*102.20 ± 3.85246.70± 1.2148.24± 1.39*49.02 ± 1.17212.60± 5.10*153.90 ± 5.26331.00± 1.0832.20± 1.53*33.24 ± 1.76244.40± 4.53*177.70 ± 2.58Bayesian network185.94± 1.8087.94± 1.80*89.64 ± 3.27116.60± 4.22*91.80 ± 4.52255.34± 1.3056.84± 1.49*58.02 ± 2.02198.00± 4.40*141.90 ± 4.63336.56± 1.5637.61± 1.44*39.44 ± 3.07221.70± 4.64*168.60 ± 4.43Results obtained using the the Bayesian network
approach
Again, the
predictive accuracy attained by both versions of the PSO algorithm surpassed
the predictive accuracy obtained by the baseline algorithm in all class levels.
DPSO obtained the best predictive accuracy of all
algorithms in all class levels. Regarding the second comparison criterion,
finding the smallest subset of attributes, again DPSO always selected the
smallest subset of attributes in all hierarchical levels.The results on the performance of the classifiers—Naive Bayes versus Bayesian networks—show that Bayesian networks did a much
better job. For all class levels, the predictive accuracy obtained by the 3
approaches (baseline, binary PSO and DPSO) using Bayesian networks was significantly
better than the predictive accuracy obtained using Naive Bayes classifier. The
Bayesian networks approach also enabled the two PSO algorithms to do the job
using fewer selected attributes—compared to the Naive Bayes approach.The results emphasize the importance of taking
relationships among attributes into account—as Bayesian networks do—when
performing attribute selection. If these relationships are ignored, predictive
accuracy is adversely affected.The results also show that for all 6 data sets tested,
the DPSO algorithm not only selected the smallest subset of attributes, but
also obtained the highest predictive accuracy in every single class level.


## 7.1. Experimental Methodology

Note that the
computation of the fitness functionf(⋅) for the
particles Y(i) (binary PSO
algorithm) and Z(i) (DPSO
algorithm) follows the description given below. For simplicity, only the
process using Y(i) is described—but the same is applicable to Z(i). f(Y(i)) is equal to
the predictive accuracy achieved by the Naive Bayes classifier—and the
Bayesian network—on each data set and using only the attributes selected in Y(i).The measurement off(Y(i)) follows a
wrapper approach. The wrapper approach searches for an optimal attribute subset
tailored to a particular algorithm, such as the Naive Bayes classifier or
Bayesian network. For more information on wrapper and other attribute selection
approaches, see [25].The computational experiments involved a 10-fold
crossvalidation method [25]. First, the data set being considered is divided into
10 equally sized folds. The folds are randomly generated but under the
following criterion. The proportion of classes in every single fold must be
similar to the proportion of classes found in the original data set containing
all records. This is known as stratified crossvalidation.Each of the 10 folds is used once as a test set and
the remaining of the data is used as training set. Out of the 9 folds in the
training set one is reserved to be used as a validation set. The Naive Bayes
classifier and the Bayesian network use the remaining 8 folds to compute the
probabilities required to classify new examples. Once those probabilities have
been computed, the Naive Bayes (NB) classifier and the Bayesian network (BN)
classify the examples in the validation set.The accuracy of this classification on the validation
set is the value of the fitness functionsfNB (Y(i)) and fBN (Y(i))—the same
for fNB (Z(i)) and fBN (Z(i)). When the run
of the PSO algorithm is completed, the 9 folds are merged into a full training
set. The Naive Bayes classifier and the Bayesian network are then trained again
on this full-training set (9 merged folds), and the probabilities computed in
this final, full-training set are used to classify examples in the test set
(the 10th fold), which was never accessed during the run of the algorithms.The reasons for having separate validation and test
sets are as follows. In the classification task of data mining, by definition,
the goal is to measure predictive accuracy—generalization ability—on a
test set unseen during training. Hence, the test set cannot be accessed by the
PSO, and is reserved just to compute the predictive accuracy associated with
the Bayesian classifier constructed with the best set of attributes selected at
the end of the PSO run.Concerning the validation set, which is used to
compute the fitness of particles during the PSO run, this is a part of the
original training set which is different from the part of the training set used
to build the Bayesian classifier, and the reason for having these two separate
parts of the training set is to avoid overfitting of the classifier to the
training data; for overfitting in the context of classification, see [7, pages 17, 18]. In other
words, if the same training set that was used to build a Bayesian classifier
was also used to measure the fitness (accuracy) of the corresponding particle,
there would be no pressure to build classifiers with a good generalization
ability on data unseen during training, and a classifier could obtain a high
accuracy by simply being overfitted to idiosyncrasies of the training set which
are unlikely to generalize well to unseen data. By measuring fitness on a
validation set separated from the data used to build the classifier, this is
avoided, and a pressure to build classifiers with good generalization ability
is introduced in the fitness function.In each of the 10 iterations of the crossvalidation
procedure, the predictive accuracy of the classification is assessed by 3
different methods, as follows.(1)
Using all
possible original attributes: all possible attributes are used by the Naive
Bayes classifier and the Bayesian network—there is no attribute selection.(2)
Standard
binary PSO algorithm: only the attributes selected by the best particle
found by the binary PSO algorithm are used by the Naive Bayes classifier and
the Bayesian network.(3)
DPSO
algorithm: only the attributes selected by the best particle found by the
DPSO algorithm are used by the Naive Bayes classifier and the Bayesian network.Since the Naive Bayes and Bayesian network classifiers
used in this work are deterministic, only one run—for each of these
algorithms—is performed for the classification using all possible
attributes.For the binary PSO and the DPSO algorithms, 30
independent runs are performed for each iteration of the crossvalidation
procedure. The results reported are averaged over these 30 independent runs and
over the 10 iterations of the crossvalidation procedure.The population size used for both algorithms (binary
PSO and DPSO) is 200 and the search stops after 20 000 fitness evaluations—or 100 iterations.The binary PSO algorithm uses an inertia weight value
of 0.8 (i.e.,w=0.8). The
choice of the value of this parameter was based on the work presented in
[26].Other choices of parameter values for the DPSO wereα=0.10, β=0.12, and γ=0.14, chosen
based on empirical experiments but probably not optimal values.The measurement of the predictive accuracy rate of a
model should be a reliable estimate of how well that model classifies the test
examples—unseen during the training phase—on the target problem.In Data Mining, typically, the
equation(16)standardaccuracyrate=TP+TNTP+FP+FN+TNis used to assess the accuracy
rate of a classifier—where TP, TN, FP, and FN are the numbers
of true positives, true negatives, false positives, and false negatives,
respectively [25].However, if the class distribution is highly
unbalanced, (16) is an ineffective way of measuring the accuracy rate
of a model. For instance, in many problems, it is easy to achieve a high value
for (16) by
simply predicting always the majority class. Therefore, on the experiments
reported on this work, a more demanding measurement for the accuracy rate of a
classification model is used.This measurement has been used before in [27]. It is given by the
equation
(17)predictiveaccuracyrate=TPR⋅TNR,
where, TPR = TP/(TP+FN) and TNR = TN/(TN+FP)—TPR stands for true
positive rate and TNR stands for true
negative rate.Note that if any of the quantitiesTPR or TNR is zero, the
value returned by (17) is also zero.


## 7.2. Discussion

Computational
results are reported in Tables5 and 6. Let us focus the discussion on the
results obtained by the 3 algorithms (binary PSO, DPSO, and baseline algorithm)
for attribute selection on the GPCR-PROSITE data set, see Table 5. The results
obtained for the other 5 data sets are similar. To start with, the results
obtained using the Naive Bayes classifier are presented.Results obtained using the Naive Bayes classifier
approach
To assess the performance of the algorithms, two
criteria were considered: (1) maximizing predictive accuracy; and (2) finding
the smallest subset of attributes.The results for the first criterion, accuracy, show
that both versions of the PSO algorithm did better—in all class levels—than the baseline algorithm using all attributes.Furthermore, the DPSO algorithm did slightly better
than the binary PSO algorithm also in all class levels. Nevertheless, the
difference in the predictive accuracy performance between these algorithms is,
in some cases, statistically insignificant.Table3 shows the results of a paired two-tailed t-test for the
predictive accuracy of the binary PSO versus the predictive accuracy of the
DPSO at a significance level of 0.05.Table 3
Predictive accuracy:
binary PSO versus DPSO. Paired two-tailedt test for the
predictive accuracy—significance level 0.05.
Class levelNaive BayesBayesian network1t(9) = 0.467, p = 0.651t(9) = 3.407, p = 0.0072t(9) = 2.221, p = 0.053t(9) = 3.200, p = 0.0103t(9) = 3.307, p = 0.009t(9) = 3.556, p = 0.006Table3 shows that, using Naive Bayes as classifier,
the only statistically significant difference in performance—in terms of
predictive accuracy—between the algorithms binary PSO and DPSO is at the
third class level. By contrast, using Bayesian networks as classifier, the
difference in performance is statistically significant at all class levels.Nevertheless, the discriminating factor between the
performance of these algorithms is on the second comparison criterion—finding
the smallest subset of attributes.The DPSO not only outperformed the binary PSO in
predictive accuracy, but also did so using a smaller subset of attributes in
all class levels. Moreover, when it comes to effectively pruning the set of
attributes, the difference in performance between the binary PSO and the DPSO
is always statistically significant, as Table4 shows.Table 4
Number of selected attributes: binary PSO versus DPSO. Paired two-tailedt test for the
number of attributes selected—significance level 0.05.
Class levelNaive BayesBayesian network1t(9) = 7.248, p = 4.8E-5t(9) = 8.2770, p = 1.6E-52t(9) = 9.052, p = 8.1E-6t(9) = 14.890, p = 1.2E-73t(9) = 6.887, p = 7.1E-5t(9) = 9.1730, p = 7.3E-6Table 5
Results for the
GPCRs data sets. For the binary PSO and DPSO algorithms, 30 independent runs
are performed. The results reported are averaged over these 30 independent
runs. The best result on each line for each performance criterion is marked
with an asterisk (*).
GPCR-PRINTS (281 attributes)Average predictive accuracyAverage number of selected attributesMethodClass levelUsing all attributesBinary PSODiscrete PSOBinary PSODiscrete PSONaive Bayes172.36± 2.6473.10± 2.71*73.98 ± 3.1397.40± 1.26*73.30 ± 4.35235.56± 2.5637.10± 3.10*40.74 ± 5.36130.30± 1.34*117.30 ± 6.04327.00± 1.8229.05± 2.71*31.55 ± 4.54171.10± 3.93*145.70 ± 3.80424.26± 1.7526.97± 2.24*30.14 ± 3.78165.00± 4.11*141.30 ± 5.21Bayesian network188.67± 1.7289.46± 1.73*89.97 ± 2.1189.30± 3.77*63.80 ± 3.99253.46± 1.4056.75± 2.47*58.91 ± 3.95123.70± 3.89*103.00 ± 4.27338.93± 1.9243.08± 3.03*50.33 ± 6.45158.20± 4.21*134.50 ± 4.60428.47± 1.9030.56± 2.63*39.52 ± 5.32152.60± 3.53*126.80 ± 4.59GPCR-PROSITE (127 attributes)Average predictive accuracyAverage number of selected attributesMethodClass levelUsing all attributesBinary PSODiscrete PSODiscrete PSOBinary PSONaive Bayes171.27± 2.0872.88± 2.40*73.05 ± 2.3185.60± 2.84*74.90 ± 3.48230.00± 2.1031.34± 2.47*32.60 ± 2.31101.50± 3.14*83.80 ± 4.64320.47± 0.9621.47± 1.16*23.25 ± 1.08102.30± 3.77*87.50 ± 4.25Bayesian network178.05± 2.3379.03± 2.57*80.54 ± 2.4678.50± 3.50*65.50 ± 3.41239.08± 2.6740.31± 2.85*43.24 ± 4.6794.10± 3.70*73.30 ± 2.67324.70± 1.8326.14± 2.11*28.97 ± 2.7794.90± 3.90*77.60 ± 4.35GPCR-INTERPRO (448 attributes)Average predictive accuracyAverage number of selected attributesMethodClass levelUsing all attributesBinary PSODiscrete PSOBinary PSODiscrete PSONaive Bayes154.17± 2.2655.33± 2.36*56.55 ± 2.61136.40± 1.17*120.70 ± 5.01225.19± 1.5026.08± 1.62*27.27 ± 1.87158.60± 1.07*136.20 ± 5.53320.03± 0.6521.19± 1.03*22.03 ± 1.63203.60± 1.26*162.40 ± 6.62427.97± 1.1329.95± 2.18*30.43 ± 2.56168.00± 0.94*150.10 ± 7.31Bayesian network186.68± 2.9989.20± 3.06*89.49 ± 4.28122.60± 4.03*107.70 ± 5.12261.85± 1.7164.57± 1.43*68.66 ± 3.82146.80± 3.12*128.40 ± 5.02340.77± 2.1344.11± 2.48*46.51 ± 3.41184.60± 2.41*148.10 ± 3.98434.05± 1.6436.89± 2.56*39.03 ± 3.63149.70± 2.41*131.50 ± 4.12Table 6
Results for the
EC data sets. For the binary PSO and the DPSO algorithms, 30 independent runs are
performed. The results reported are averaged over these 30 independent runs.
The best result on each line for each performance criterion is marked with an
asterisk (*).
EC-PRINTS (380 attributes)Average predictive accuracyAverage number of selected attributesMETHODClass levelUsing all attributesSBinary PSODiscrete PSOBinary PSODiscrete PSONaive Bayes172.35± 3.3373.78± 3.78*74.81 ± 3.79102.80± 1.23*64.20 ± 4.37231.19± 2.2632.07± 2.48*34.06 ± 2.91149.00± 1.25*112.30 ± 3.06323.37± 1.7324.64± 2.01*26.97 ± 2.49211.10± 1.37*150.60 ± 5.58Bayesian network188.30± 1.9489.51± 2.51*90.73 ± 2.5992.80± 4.57*48.90 ± 4.68253.15± 1.4955.14± 1.87*56.92 ± 2.93129.70± 4.11*102.00 ± 5.52336.24± 1.6238.26± 2.65*40.95 ± 4.16190.40± 4.55*135.10 ± 4.28EC-PROSITE (583 attributes)Average predictive accuracyAverage number of selected attributesMETHODClass levelUsing all attributesBinary PSODiscrete PSOBinary PSODiscrete PSONaive Bayes169.52± 5.0270.37± 5.15*72.31 ± 5.44118.80± 1.14*98.90 ± 1.85235.70± 1.7337.73± 2.04*38.83 ± 2.66154.50± 0.85*134.90 ± 4.93321.91± 1.1322.86± 1.30*24.36 ± 1.66197.70± 1.16*154.50 ± 5.34Bayesian network182.80± 1.0984.83± 1.46*85.95 ± 2.31105.00± 3.62*92.70 ± 4.00245.30± 2.4147.82± 2.80*49.50 ± 3.33135.20± 3.65*119.00 ± 3.89328.44± 2.3729.40± 2.64*32.52 ± 3.71172.00± 2.94*146.50 ± 4.40EC-PFAM (706 attributes)Average predictive accuracyAverage number of selected attributesMETHODClass levelUsing all attributesBinary PSODiscrete PSOBinary PSODiscrete PSONaive Bayes171.61± 3.5272.87± 4.02*74.62 ± 3.77131.60± 5.50*102.20 ± 3.85246.70± 1.2148.24± 1.39*49.02 ± 1.17212.60± 5.10*153.90 ± 5.26331.00± 1.0832.20± 1.53*33.24 ± 1.76244.40± 4.53*177.70 ± 2.58Bayesian network185.94± 1.8087.94± 1.80*89.64 ± 3.27116.60± 4.22*91.80 ± 4.52255.34± 1.3056.84± 1.49*58.02 ± 2.02198.00± 4.40*141.90 ± 4.63336.56± 1.5637.61± 1.44*39.44 ± 3.07221.70± 4.64*168.60 ± 4.43Results obtained using the the Bayesian network
approach
Again, the
predictive accuracy attained by both versions of the PSO algorithm surpassed
the predictive accuracy obtained by the baseline algorithm in all class levels.
DPSO obtained the best predictive accuracy of all
algorithms in all class levels. Regarding the second comparison criterion,
finding the smallest subset of attributes, again DPSO always selected the
smallest subset of attributes in all hierarchical levels.The results on the performance of the classifiers—Naive Bayes versus Bayesian networks—show that Bayesian networks did a much
better job. For all class levels, the predictive accuracy obtained by the 3
approaches (baseline, binary PSO and DPSO) using Bayesian networks was significantly
better than the predictive accuracy obtained using Naive Bayes classifier. The
Bayesian networks approach also enabled the two PSO algorithms to do the job
using fewer selected attributes—compared to the Naive Bayes approach.The results emphasize the importance of taking
relationships among attributes into account—as Bayesian networks do—when
performing attribute selection. If these relationships are ignored, predictive
accuracy is adversely affected.The results also show that for all 6 data sets tested,
the DPSO algorithm not only selected the smallest subset of attributes, but
also obtained the highest predictive accuracy in every single class level.


## 8. Conclusions

Computational
results show that the use of unnecessary attributes tends to derail classifiers
and hurt classification accuracy. Using only a small subset of selected
attributes, the binary PSO and DPSO algorithms obtained better predictive
accuracy than the baseline algorithm using all attributes. Previous work had
already shown that the DPSO algorithm outperforms the binary PSO in the task of
attribute selection [5], but that work involves only one data set. This
current work shows much stronger evidence for the effectiveness of DPSO in 6
data sets. In addition, the 6 data sets mined in this work are much more
challenging than the two-class data set mined in [5], because the former have
several hierarchical class levels per data set, leading to a much larger number
of classes to be predicted for each data set.Even when the difference in predictive accuracy is
insignificant, by selecting fewer attributes than the binary PSO, the DPSO
certainly enhances computational efficiency of the classifier and is therefore
preferable.The original work on DPSO [5] questioned whether the
difference in performance between these two algorithms was attributable to
variations in the initial population of solutions. To overcome this possible
advantage/disadvantage for one algorithm or the other, the present work used
the same initial population for both algorithms.The results demonstrate that, even using an identical
initial population of particles, the DPSO is still outperforming the binary PSO
in both predictive accuracy and number of selected attributes. The DPSO is
arguably not too different from traditional PSO but still the algorithm has
features that enable it to improve over binary PSO on the task of attribute
selection.Another result—although expected—from the
experiments is the clear difference in performance between Naive Bayes and
Bayesian networks used as classifiers. The Bayesian networks approach
outperformed the Naive Bayes approach in all experiments and in all
hierarchical class levels.In this work, the hierarchical classification problem
was dealt with in a simple way by “flattening" the hierarchy, that is, by
predicting classes for one class level at a time, which permitted the use of
flat classification algorithms. The algorithms made no use of the information
of the class assigned to a protein in one level to help predict the class at
the next hierarchical level. Future work intends to look at an algorithm that
makes use of this information.Algorithm 1:Pseudocode for a generic greedy search
algorithm.
Require:  Initialize an empty
Bayesian network G containing n nodes (i.e., a BN with n nodes but no edges)1: Evaluate the score ofG: Score (G)2:BEST = Score (G)3:repeat4:FROM = 05:TO = 06:fori = 1 to ndo7:forj = 1 to ndo8:G′=G9:ifi≠jthen10:if there is no edge between the nodes i and j in G′then11:      ModifyG′: add an edge between the
nodes i and j in G′ such that i is a parent of j: (i→j)12:if the resulting G′ is a DAG then13:if (Score(G′)>BEST) then14:BEST = Score(G′)15:FROM = i16:TO = j17:end if18:end if19:end if20:end if21:end for22:end for23:ifFROM> 0 then24:  ModifyG: add an edge between the nodes FROM and TO in G such that FROM is a parent of TO:
(FROM→TO)25:end if26:untilFROM = 027:returnG as the
structure of the BN



---

*Source: 876746-2008-03-18.xml*