
\documentclass[runningheads,a4paper]{llncs}

%In order to omit page numbers and running heads
%please use the following line instead of the first command line:
%\documentclass{llncs}.
%Furthermore change the line \pagestyle{headings} to
%\pagestyle{empty}.

%\input{psfig.sty}
\usepackage{epsfig}
\usepackage{amssymb}
\usepackage{amsmath}
\setcounter{tocdepth}{3}
\usepackage{graphicx}

\usepackage{url}
\urldef{\mailsa}\path|antanas.verikas@hh.se;|
\urldef{\mailsb}\path|jonas.guzaitis@stud.ktu.lt|
\urldef{\mailsc}\path|{adas.gelzinis, marija.bacauskiene}@ktu.lt|
\newcommand{\keywords}[1]{\par\addvspace\baselineskip
\noindent\keywordname\enspace\ignorespaces#1}


\begin{document}

\pagestyle{headings}
%In order to omit page numbers and running heads
%please change this line to
\pagestyle{empty}
%and change the first command line too, see above.


\mainmatter

\title{A framework for designing a fuzzy rule-based classifier
\thanks{We acknowledge the support from the agency for international science and technology
development programmes in Lithuania (COST IC0602).}}

\titlerunning{A framework for designing a fuzzy rule-based classifier}

\author{J. Guzaitis\inst{1}  A. Verikas\inst{1,2,\ddag}  A.
Gelzinis\inst{1}  M. Bacauskiene\inst{1} }

\authorrunning{J. Guzaitis et al.}

\institute{Department Electrical \& Control Instrumentation,
   Kaunas University of Technology,\\
   Studentu 50, LT-51368, Kaunas, Lithuania\\
\and Intelligent Systems Laboratory,
   Halmstad University,\\
   Box 823, S-30118 Halmstad, Sweden\\
$\ddag$ Corresponding author\\
\mailsa \ \
\mailsb\\
\mailsc\\
}


\maketitle



\begin{abstract}

This paper is concerned with a general framework for designing a
fuzzy rule-based classifier. Structure and parameters of the
classifier are evolved through a two-stage genetic search. The
classifier structure is constrained by a tree created using the
evolving SOM tree algorithm. Salient input variables are specific
for each fuzzy rule and are found during the genetic search process.
It is shown through computer simulations of four real world problems
that a large number of rules and input variables can be eliminated
from the model without deteriorating the classification accuracy.


\keywords{Classifier, Fuzzy rule, Genetic algorithm, Knowledge
extraction, Variable selection}
\end{abstract}



\section{Introduction}

\label{sec:intro}

Neural networks and support vector machines are probably the most
popular data classification techniques. However, classifiers based
on these techniques are not transparent enough and are often
considered as ``black boxes". The transparency is very important in
some application areas, such as medical decision support or quality
control. By contrast, fuzzy rule-based systems and fuzzy decision
trees are known for their transparency and ability of accounting for
uncertainty. ANFIS~\cite{Jan93}, fuzzy ARTMAP~\cite{CarGro92} are
examples of the most prominent fuzzy logic-based systems. It is well
known that designing of fuzzy rule-based systems in high dimensional
spaces is rather problematic. However, there are many problems
characterized by a small or moderate number of variables. Moreover,
quite often high dimensional data vary in a much lower number of
dimensions if compared to the dimensionality of an input space.
System structure identification and parameter optimization are two
main issues to consider when designing a fuzzy rule-based
system~\cite{Jan93}. Fuzzy partitioning, variable selection, and
fuzzy reasoning are the tasks to be solved for identifying the
system structure.

Various approaches have been used for dealing with the two main
fuzzy rule-based system design issues. The initial system structure,
often termed as fuzzy partitioning, is usually identified through
K-Means~\cite{Dud}, Fuzzy C-Means~\cite{Bez81}, Learning Vector
Quantization (LVQ)~\cite{Koh90} or SOM-based
clustering~\cite{CheLin01,ZhoKho07} as well as incremental
clustering~\cite{Kas01,MinLud08} or by constructing a decision
tree~\cite{AboRou03,PulKoi07}.



Variable selection based on: the output sensitivity to the input
change~\cite{CasCas05,VerBac02}, the output sensitivity combined
with the correlation between variables~\cite{CheLin01}, Fisher's
interclass separability measure~\cite{RouSet03}, variable
correlation with the output~\cite{NauKru99} are the most popular
variable selection techniques applied. However, quite often,
variable selection is not considered at all~\cite{ZhoKho07}.


It seems that the simple gradient decent~\cite{CheLin01,CasCas05},
error correction~\cite{NozIsh96}, and genetic
search~\cite{ZhoKho07,AboRou03} are the most popular parameter
optimization techniques utilized in various studies. The combined
optimization of both structure and parameters has also been
considered by applying genetic algorithms (GA)~\cite{OzyAlh07},
unsupervised and reinforcement learning~\cite{ErZho08}, or simple
heuristics~\cite{NauKru99}. In~\cite{OzyAlh07} the genetic search
process focusses on ``hard" data points by assigning a higher weight
to such points. Such an approach has also been adopted for learning
weights $z_j^q$ of fuzzy rules~\cite{NakSch07}. In~\cite{IshNoj07},
genetic search-based multi-objective optimization was applied to
design a fuzzy rule-based system. The task was to maximize $f_1(S)$,
minimize $f_2(S)$, and minimize $f_3(S)$, where $S$ is a set of
fuzzy rules, $f_1(S)$ stands for correctly classified training
samples, $f_2(S)$ is the number of fuzzy rules in $S$, and $f_3(S)$
is the total number of antecedent conditions in $S$. Thus, $f_3(S)$
can be considered as the total rule length. The optimization starts
with all possible rules in the search space defined by the training
patterns.


Generalization ability is an important issue to consider when
designing a fuzzy rule-based classifier. The most popular technique
applied to improve the generalization ability is rule pruning based
on similarity of fuzzy sets~\cite{RouSet03,CheLin01}. Other
approaches utilized are: GA~\cite{ChaLia06}, simulated
annealing~\cite{MohHab08}, similarity of fuzzy sets combined with
GA~\cite{ZhoKho07}, through forgetting by decaying the grade of
certainty of fuzzy rules~\cite{NozIsh96}, pruning of rarely used
rules~\cite{NauKru99}.


\subsection{Fuzzy rule-based and nearest neighbour techniques}

The fuzzy rule based classification techniques are closely related
to nearest neighbour (NN)-based classification approaches. NN-based
classification has a sound basis, since there is a considerable body
of evidence from the literature that classification and recognition
of patterns by humans is best explained as a form of interpolation
between similar patterns~\cite{Low95}. NN methods are frequently
criticized as requiring much greater use of memory than, for
example, neural network algorithms. However, NN learning algorithms
can reduce their memory usage by only retaining the full density of
exemplars near to classification boundaries and thinning them in
other regions~\cite{Chang74,VerNCA03}. The location of fuzzy sets,
reference patterns in the NN approach, can be further optimized by
applying the LVQ techniques. LVQ has been widely used to learn
reference patterns for classification based on the NN approach. Each
class $C_j$ is described by several reference patterns ${\bf m}_j^l$
(fuzzy sets in the rule-based approach), which are properly placed
within each class region. An unknown $\bf x$  is then determined to
belong to the class $k$, if:
%
\begin{equation}\label{eq:E1}
    k=\arg\min_j[\min_ld({\bf x},{\bf m}_j^l),\ \ l=1,...,N_j,\ \ j=1,...,Q]
\end{equation}
%
where {\it Q} is the number of classes, ${N_j}$ is the number of
reference patterns representing the class {\it j} and  ${d({\bf
x},{\bf m}_j^l)}$ is the distance between {\bf x}  and
${{\bf m}_j^l}$.



One more drawback of classical NN and fuzzy rule-based methods is
the often exhibited poor generalization performance as compared to
neural networks, for example. In NN methods, the degradation in
performance often accompanies the addition of new unimportant
features. However, there are many problems where different features
are important in different regions of the input space.
Fig.~\ref{fig:F1} provides an example illustrating such a situation.
%
\begin{figure}[htb]
\centering
\includegraphics[height=4.0cm,angle=0] {dmfig1.eps}
\caption{Four decision classes in the two-dimensional space.} \label{fig:F1}
\end{figure}

The four data clusters illustrated in Fig.~\ref{fig:F1} represent
four decision classes. It is obvious that the feature $q$ is
unimportant for discriminating the classes $A$ and $B$, likewise the
feature $k$ is unimportant for discriminating the classes $C$ and
$D$. Thus, a subset of features used should be reference pattern or
fuzzy rule dependent. However, in most of the known fuzzy rule-based
classification algorithms, the feature selection problem is
considered independently of the input space region or not considered
at all. The objective of this work is to develop a fuzzy modeling
framework capable of automatically generating a rule base for
classification of numeric data, finding the optimal number of rules
and input variables for each rule, and finding the optimal parameter
values of fuzzy rules.


\section{The fuzzy model}


We use the Mamdani model~\cite{MamAss75}, which is the most popular
fuzzy model applied in various studies for fuzzy
reasoning~\cite{ZhoKho07,CasCas05,CheLin01}. Concerning
classification, the model is a collection of fuzzy rules $R_j$ of
the following form:
%
\begin{equation}\label{mamd}
    R_j: \texttt{IF}\ x_1 \ \texttt{is} \ A_{j1} \ \texttt{AND} \ ... \ \texttt{AND}\  x_n \ \texttt{is} \  A_{jn} \
    \texttt{THEN} \  \texttt{class} \ C_q \ \texttt{with} \ z_j^q
\end{equation}
%
where $A_{ji} (i=1,...,n)$ are fuzzy sets defined over the input
variables $x_i$, $C_q$ is a class label and $z_j^q$ is a rule
weight. Each fuzzy set is represented by a membership function. A
triangular or a Gaussian function of the form
%
\begin{equation}\label{membG}
    \mu_{ji}=\exp\bigg (-\frac{(x_i-c_{ji})^2}{\sigma_{ji}^2}  \bigg )
\end{equation}
%
where $c_{ji}$ and $\sigma_{ji}$ are the center and the width of the
Gaussian function, respectively, are common choices. We use Gaussian
membership functions in this study. There are various ways to
determine the rule weights $z_j^q$. In this work, the weight $z_j^q$
is given by:
%
\begin{equation}\label{weightcf}
    z_j^q=\frac{\sum_{{\bf x}_p\in C_q}\mu_{{\bf A}_j}({\bf x}_p)- \sum_{{\bf x}_p \notin C_q}\mu_{{\bf A}_j}({\bf x}_p)}{\sum_{p=1}^N\mu_{{\bf A}_j}({\bf x}_p)}
\end{equation}
%
where $N$ is the number of training patterns and the matching degree
of the input pattern ${\bf x}_p$ with the antecedent part ${\bf A}_j =
(A_{j1},...,A_{jn})$ is calculated using a $T$-norm
%
\begin{equation}\label{miu}
    \mu_{{\bf A}_j}({\bf x}_p) =
    T(\mu_{A_{j1}}(x_{p1}),...,\mu_{A_{jn}}(x_{pn}))
\end{equation}
%
We use the min $T$-norm operator in this work. Weights $z_j^q$ of
this type were studied in~\cite{IshNoj07}.

A winning rule is used to make a decision. Thus, given a rule base
$S$ consisting of $L$ rules, an input pattern ${\bf x}_p$ is
assigned to the class $q$ if
%
\begin{equation}\label{clasR}
    q= \arg \max_k \ \{T[\mu_{{\bf A}_j}({\bf x}_p), z_j^k], \
    j=1,...,L\}
\end{equation}
%
where $T$ is the product $T$-norm operator, in this work.

Having defined the membership functions, we formulate the fuzzy modeling problem
in the following way. Given $N$ pairs of
input-output patterns $({\bf x},y)$, create a minimal number of
fuzzy rules $r$ with the optimal number of features $n_i$ for each rule and find the
optimal values of parameters $({\bf c}, \boldsymbol{\sigma}, {\bf z})$ of the fuzzy model $F({\bf c},
\boldsymbol{\sigma}, {\bf z},r,n_i,i=1,...,r)$.





\section{The approach}

The procedure to construct the fuzzy rule-based classifier
consists of the following steps.

\begin{enumerate}
  \item Divide the data set into learning and test subsets.
  \item Cluster the learning set data by applying the evolving SOM tree.\label{tree}
  \item Based on the evolved tree, generate a population of sub-trees. Each sub-tree
  defines the initial structure of one fuzzy rule-based classifier.
  The generation is accomplished by randomly cutting branches of the tree grown in
  Step~\ref{tree}. The cutting occurs approximately between 25 and 75\% of the tree depth.
  \item Represent each node in the sub-tree population by a set of fuzzy sets with the
  Gaussian membership functions.
  \item Encode the structure of each sub-tree of the population into
  a separate chromosome.

  \item Take one sub-tree (classifier of a given structure) from the sub-tree population and encode
  features (used/not used) and parameters of the membership functions
  of the classifier into a chromosome. When encoding, enable feature selection
  independently for each fuzzy rule.\label{sub-tree}
  \item Generate a population of chromosomes encoding individual classifiers of the given structure.
  The individual classifiers differ in features and values of the parameters.
  \item Apply the modified LVQ-3 algorithm to the individuals of the
    population and test the fitness of the individuals.\label{genqual}
  \item Apply genetic operations (to features and parameters) and generate a
  new population.\label{genop}
  \item Repeat Steps~\ref{genqual}--\ref{genop} until convergence.
  \item Take the best individual of the given structure.\label{best}
  \item Repeat Steps~\ref{sub-tree}--\ref{best} for the whole
  population of sub-trees.
\item  Apply genetic operations (to structure of sub-trees) and generate a
  new population of sub-trees.\label{genoptree}
  \item Repeat Steps~\ref{sub-tree}--\ref{genoptree} for a given number of generations.

\end{enumerate}

Next, we briefly describe the main topics of the technique.


\subsection{The evolving SOM tree}\label{sec:tree}

Like SOM, the evolving SOM tree~\cite{PakIiv04} exhibits the
self-organization property. The evolving tree structure enables the
SOM tree to efficiently handle large scale problems. Moreover, there
is no need of choosing the map size beforehand. Like in ordinary
SOM, each node of the SOM tree has a weight vector ${\bf w}_i$. When
training the tree, for each training vector $\bf x$, the best
matching unit (BMU) is found by a greedy tree search. BMU is always
a leaf node. Weight vectors of the BMU and its neighbours are then
updated using the SOM adaptation rule:
%
\begin{equation}\label{eq:adaptSOM}
    {\bf w}_i(t+1)={\bf w}_i(t)-h_{ci}(t)[{\bf x}(t)-{\bf
    w}_i(t)]
\end{equation}
%
where $h_{ci}(t)$ is the neighbourhood function. We used the
Gaussian neighbourhood function
%
\begin{equation}\label{neigh}
    h_{ci}(t)=\beta(t) \exp \bigg ( \frac{\|{\bf r}_c - {\bf r}_i \|^2}{2s^2(t)} \bigg )
\end{equation}
%
where $s(t)$ is the width of the Gaussian function, ${\bf r}_c$ and
${\bf r}_i$ denote location of nodes $c$ and $i$, and $\beta(t)$ is
the learning rate. The meaning of $s(t)$ and $\beta(t)$ is the same
as in SOM~\cite{Koh01}, while the meaning of the norm $\|{\bf r}_c -
{\bf r}_i \|$ is quite different. The basic idea of calculating the
distance is to count how many "hops" are needed to get from the BMU
to the considered node along the shortest path~\cite{PakIiv04}. The
distance $\|{\bf r}_c - {\bf r}_i \|$ is then given by the number of
hops minus one.






\subsection{The modified LVQ-3 algorithm}

Assume that  $d_i$ and $d_j$  are the Euclidean distances from the
pattern $\bf x$ to the reference patterns ${\bf m}_i$  and  ${\bf
m}_j$, respectively. Then $\bf x$ is defined to fall into a window
of the relative width $\lambda$, if
%
\begin{equation}\label{eq:win}
    \min \Bigg (\frac{d_i}{d_j}, \frac{d_j}{d_i} \Bigg ) > \frac{1-\lambda}{1+\lambda}
\end{equation}

For all $\bf x$  falling into the window adapt:
%
\begin{equation}\label{eq:adapt1}
    {\bf m}_i(t+1)={\bf m}_i(t)-\alpha (t)[{\bf x}(t)-{\bf
    m}_i(t)]
\end{equation}
%
\begin{equation}\label{eq:adapt2}
   {\bf m}_j(t+1)={\bf m}_j(t)+\alpha (t)[{\bf x}(t)-{\bf
    m}_j(t)]
\end{equation}
%
where $\alpha (t)$ decreases with time and $0<\alpha (t)<1$, ${\bf
m}_i$ and ${\bf m}_j$ are two closest reference patterns to $\bf x$,
whereby $\bf x$ belongs to the same class as ${\bf m}_j$, but not as
${\bf m}_i$. If $\bf x$, ${\bf m}_i$ and ${\bf m}_j$ belong to the
same class:
%
\begin{equation}\label{eq:same}
{\bf m}_k(t+1)={\bf m}_k(t)+\gamma \alpha (t)[{\bf x}(t)-{\bf
    m}_k(t)]
\end{equation}
%
for $k \in \{i,j\}$. If $\bf x$ belongs to a different class than
${\bf m}_i$ and ${\bf m}_j$:
%
\begin{equation}\label{eq:diff}
{\bf m}_k(t+1)={\bf m}_k(t)-\gamma \alpha (t)[{\bf x}(t)-{\bf
    m}_k(t)]
\end{equation}
%
for $k \in \{i,j\}$, where $\gamma$ is a parameter.

The algorithm performs fine tuning of the centers of membership
functions. The last adaptation step is not used in the original
version of the Lvq-3 algorithm. We have found that the use of the
step quite noticeably improved the accuracy of the algorithm.



\subsection{Encoding}

There are two loops of genetic evolution: the outer loop concerning
structure evolution and the inner loop concerning features and
parameters of membership functions. The structure is determined by a
sub-tree and is encoded as a connected graph. The chromosome
encoding features and parameters of the membership functions can be
split into \emph{sections} and \emph{sub-sections}. The number of
sections is equal to the number of leaf nodes in the actual sub-tree
(the number of fuzzy rules in the classifier). The actual sub-tree
is a sub-tree governing the inner loop of genetic evolution. There
are $2n+1$ sub-sections in each section, where $n$ is the
dimensionality of the input space. One subsection ($n$ bits) encodes
features (used/not used--0/1) and the other $2n$ sub-sections encode
the centers $c$ and the widths $\sigma$ of the $n$ membership
functions $\mu$.



\subsection{Genetic operations}

Crossover and mutation are the genetic operations applied in both
loops of genetic evolution: the loop concerning structure evolution
and the loop concerning features and parameters of membership
functions. The crossover and mutation operations are executed with
the probability of crossover $p_c$ and mutation probability $p_m$,
respectively. When performing crossover for structure evolution,
parts of two sub-trees are exchanged. Mutation in structure
evolution amounts to taking one step up or down (the direction is
selected randomly) along a randomly selected branch of the tree.
Regarding a chromosome encoding features and parameters of
membership functions, crossover and mutation are performed
separately in each sub-section of the chromosome. The crossover
points are randomly selected in the ``feature mask" sub-section and
the parameter sub-sections and the corresponding parts of two
chromosomes chosen for the crossover operation are exchanged at the
selected points. The mutation is accomplished by reversing the value
of a bit in the ``feature mask" and by adding a random value from a
given, symmetric around zero, interval to parameters in the
parameters subsections selected for mutation.



\subsection{Fitness function}


The fitness value of the $i$th chromosome $f_i$ is given by
%
\begin{equation}\label{fitness}
    f_i=\chi_i + \eta \frac{\sum_{j=1}^{r_i} n_j}{r_0 \times n}
\end{equation}
%
where $\chi_i$ is the classification accuracy obtained from the
classifier encoded in the $i$th chromosome, $\eta$ is a parameter,
$n$ is the total number of available features, $n_j$ is the number
of features used by the $j$th rule, $r_0$ is the number of rules in
the initial tree, and $r_i$ stands for the number of rules used by
the $i$th classifier. The selection probability of the $i$th
chromosome $p_i$ for genetic operations is given by
%
\begin{equation}\label{selProb}
    p_i=\frac{f_i}{\sum_{j=1}^M f_j}
\end{equation}
%
where $M$ is the population size. The roulette selection principle
was applied.


\section{Experimental Investigations}\label{sec:exp}

\subsection{Data Used}


Four data sets have been used in the tests.

{\bf US congressional voting records problem}. The United States
Congressional voting records data set consists of the voting records
of 435 congressman on 16 major issues in the 98th Congress. The
votes are categorized into one of the three types of votes: (1)
(\emph{Yea}), (2) (\emph{Nay}), and (3) (\emph{Unknown}). The task
is to predict the correct political party affiliation of each
congressman. The 98th Congress consisted of 267 Democrats and 168
Republicans.

{\bf The breast cancer diagnosis problem}. The University of
Wisconsin Breast Cancer Data Set consists of 699 patterns. Amongst
them there are 458 benign samples and 241 malignant ones. Each of
these patterns consists of nine measurements taken from fine needle
aspirates from a patient's breast.

{\bf The diabetes diagnosis problem}. The Pima Indians diabetes data
set contains 768 samples taken from patients who may show signs of
diabetes. Each sample is described by eight features. There are 500
samples from patients who do not have diabetes and 268 samples from
patients who are known to have diabetes. These three data sets are
available at: http://archive.ics.uci.edu/ml/.

{\bf Pavement tiles surface inspection problem}. A pavement tile
surface is to be assigned into a \emph{quality} or \emph{defective}
class. Features for the classification are extracted from a camera
image. Five features characterizing the image texture and the grey
level distribution~\cite{GuzVer08} have been used to design a
classifier. Fig.~\ref{fig:F2} presents four examples of pavement
tile surfaces used in the study. In total, 200 quality and 200
defective surfaces were available.
%
\begin{figure}[htb]
\centering
\includegraphics[height=2.9cm,angle=0] {tile1.eps}
\includegraphics[height=2.9cm,angle=0] {tile2.eps}
\includegraphics[height=2.9cm,angle=0] {tile3.eps}
\includegraphics[height=2.9cm,angle=0] {tile4.eps}
\caption{Examples of pavement tile surfaces: a quality surface on
the left and three defective surfaces.} \label{fig:F2}
\end{figure}

\subsection{Experimental Setup}


We randomly assign the available data points into the learning $D_L$
and test $D_T$  data sets. The data are normalized to have zero mean
and unit variance. We run an experiment 30 times with different
random splits of the database into the sets  $D_L$ and  $D_T$. The
results obtained are averaged over the 30 runs.


\subsection{Optimization Parameters}

The optimal size of the Lvq-3 window depends on the number of
training samples. If a large number of samples is available, a
narrow window would guarantee the most accurate location of the
decision boundary. For good statistical accuracy, however, the
number of samples falling into the widow must be
sufficient~\cite{Koh90}. The optimal value of $ \gamma $ depends on
the size of the window, being smaller for narrower
windows~\cite{Koh90}. After some experiments the following values of
the Lvq-3 parameters have been used: $\lambda=0.05$, $\alpha=0.02$,
and $\gamma=0.4$.

There are two loops of genetic evolution: the outer loop concerning
structure evolution and the inner loop concerning features and
parameters of the membership functions. The genetic search lasted
for 100 generations (for both loops) with the following parameters:
the population size was set to 50 and the number of offsprings
produced for creating the next population was equal to 50. The
number of generations was determined experimentally by monitoring
changes of the fitness function value. The number chosen was such
that no fitness function value increase was observed in the last 10
generations. The values of crossover and mutation probabilities were
found experimentally. The following values worked well in the tests:
$p_c=0.95$ and $p_m=0.01$. The appropriate value of the parameter
$\eta$ was found to be $\eta = 0.05$.


\subsection{Results}

In the first set of experiments, the feature selection has not been
applied and the classification accuracy obtained from the fuzzy
rule-based classifier was compared with the accuracy achieved by
other techniques. The multi layer perceptron (MLP), k-NN, and LVQ-3
classifiers have been used for the comparison. The appropriate
number of hidden nodes in the MLP and the $k$ value of the k-NN
classifier were found experimentally. The leaf nodes created by the
evolving SOM tree were used as initial reference patterns for the
LVQ-3 classifier. Table~\ref{ta:comp} presents the average test data
set classification accuracy (\%) obtained from the different
classifiers using all available features. As can be seen from
Table~\ref{ta:comp}, the proposed fuzzy rule-based classifier
provided the highest classification accuracy for all the problems
studied.


\setlength{\tabcolsep}{13pt}
\begin{table}[htb!]
\caption{The average test data set classification accuracy (\%)
obtained from different classifiers using all available
features.}\label{ta:comp}
\begin{center}
\begin{tabular}{l c c c c}
\hline {\raisebox{0pt}[12pt][6pt] {\bf Data Set$\setminus$Classifier}} & {\bf k-NN} & {\bf MLP} & {\bf LVQ-3} & {\bf Proposed}\\
\hline
 {Voting}                  & {91.24} & {93.78} & {77.41} & {94.68}\\
 {Breast cancer}           & {88.73} & {97.18} & {75.87} & {98.54}\\
 {Diabetes}                & {71.19} & {71.49} & {64.22} & {71.92}\\
 {Surface inspection}      & {77.30} & {81.63} & {78.13} & {84.13}\\
\hline
\end{tabular}
\end{center}
\end{table}

In the next set of experiments, feature selection was activated and
features, specific for each rule were found through the genetic
search. Table~\ref{ta:reje} presents the average test data set
classification accuracy obtained from the approach proposed using
selected features. The classification accuracy obtained using all
the available features is also presented for the sake of comparison.
The obtained improvement in classification accuracy should be
obvious from Table~\ref{ta:reje}. Assuming that the classification
errors are log-normally distributed and applying the $t$-test it was
found that the difference between the classification accuracy
obtained using the selected and all features is significant with
95\% confidence, except for the Breast cancer data.


\setlength{\tabcolsep}{20pt}
\begin{table}[htb!]
\caption{The average test data set classification accuracy obtained
from the approach proposed using all and selected
features.}\label{ta:reje}
\begin{center}
\begin{tabular}{l c c}
\hline {\raisebox{0pt}[12pt][6pt] {\bf Data Set$\setminus$Features}} & {\bf All features} & {\bf Selected features}\\
\hline
 {Voting}                  & {94.68} & {98.68}\\
 {Breast cancer}           & {98.54} & {99.02}\\
 {Diabetes}                & {71.92} & {75.92}\\
 {Surface inspection}      & {84.13} & {99.63}\\
\hline
\end{tabular}
\end{center}
\end{table}


Table~\ref{ta:NumberofRules} presents information on the number of
rules and features used to classify the data. In the parentheses
given are the number of initial rules and the number of available
features. Ranges in the ``Features" column indicate the minimum and
the maximum number of features used by different rules. As can be
seen from Table~\ref{ta:NumberofRules}, the number of features used
by different rules varies significantly. Observe that even if the
number features used by two different rules is the same, the
features used are often different. Thus, features used are rule
specific, indeed.


\setlength{\tabcolsep}{30pt}
\begin{table}[htb!]
\caption{The number of rules and features used to classify data from
the different data sets.}\label{ta:NumberofRules}
\begin{center}
\begin{tabular}{l c c}
\hline {\raisebox{0pt}[12pt][6pt] {\bf Data Set}} & {\bf \# Rules} & {\bf \# Features}\\
\hline
 {Voting}                  & {15 (25)} & {05--09 (16)}\\
 {Breast cancer}           & {10 (14)} & {12--20 (30)}\\
 {Diabetes}                & {10 (16)} & {02--08 (\ 8)}\\
 {Surface inspection}      & {09 (13)} & {03--04 (\ 5)}\\
\hline
\end{tabular}
\end{center}
\end{table}

Next, the influence of crossover and mutation probabilities, $p_c$
and $p_m$, on classification accuracy was studied. The same $p_c$
and $p_m$ values were used for both structure and parameter
evolution. To speed up the convergence, the studies were performed
without employing feature selection. A very similar performance was
observed for $p_m$ values raging from 0 to 0.05. A value of
$p_m=0.01$ was selected. When studying the influence of $p_c$, the
$p_m$ was set to $p_m=0$. Table~\ref{ta:pc} presents the average
test set classification accuracy obtained for different $p_c$
values.



\setlength{\tabcolsep}{12pt}
\begin{table}[htb!]
\caption{The average test set classification accuracy obtained for
different $p_c$ values.}\label{ta:pc}
\begin{center}
\begin{tabular}{l c c c c}
\hline {\raisebox{0pt}[12pt][6pt] {\bf Data Set}} & {\bf $p_c=0.25$} & {\bf $p_c=0.50$} & {\bf $p_c=0.75$} & {\bf $p_c=1.0$}\\
\hline
 {Voting}                  & {92.89} & {93.01} & {93.21} & {94.68}\\
 {Breast cancer}           & {94.12} & {93.32} & {94.78} & {95.02}\\
 {Diabetes}                & {67.21} & {68.45} & {69.53} & {71.92}\\
 {Surface inspection}      & {82.01} & {82.10} & {83.02} & {84.13}\\
\hline
\end{tabular}
\end{center}
\end{table}


\section{Conclusions}\label{sec:concl}

Proposed is a general framework for designing a fuzzy rule-based
classification system. The two-stage GA developed partitions the
search space and enables evolving both structure and parameters of
the classifier. Salient input variables, specific for each fuzzy
rule, are also found during the search process.

Computer simulations of four real world problems have shown that the
performance obtained from the classifier is comparable or even
higher than the best performance obtained by other authors when
using ``black box" models. The proposed variable selection tool
allowed to significantly increase the classification accuracy if
compared to the case of using all the available input variables. It
was shown through computer simulations that a large number of rules
and input variables can be eliminated from the model without
deteriorating the classification accuracy. Moreover, the
classification accuracy of the test set data increased due to the
reduction.

\begin{thebibliography}{10}

\bibitem{Jan93}
Jang, J.R.:
\newblock \textsc{ANFIS}: adaptive-network-based fuzzy inference system.
\newblock IEEE Trans Systems Man Cybernetics \textbf{23} (1993)  665--685

\bibitem{CarGro92}
Carpenter, G.A., Grossberg, S., , Markuzon, N., Reynolds, J.H., Rosen, D.B.:
\newblock Fuzzy \textsc{ARTMAP}: A neural network architecture for incremental
  supervised learning of analog multidimensional maps.
\newblock IEEE Trans Neural Networks \textbf{3}(5) (1992)  698--713

\bibitem{Dud}
Duda, R.O., Hart, P.E., Stork, D.G.:
\newblock Pattern Classification. 2 edn.
\newblock John Wiley \& Sons, New York (2001)

\bibitem{Bez81}
Bezdek, J.C.:
\newblock Pattern Recognition with Fuzzy Objective Function Algorithms.
\newblock Plenum Press, New York (1981)

\bibitem{Koh90}
Kohonen, T.:
\newblock The self-organizing map.
\newblock Proceedings of the IEEE \textbf{78}(9) (1990)  1461--1480

\bibitem{CheLin01}
Chen, M.Y., Linkens, D.A.:
\newblock A systematic neuro-fuzzy modeling framework with application to
  material property prediction.
\newblock IEEE Trans Systems Man, Cybernetics, Part B \textbf{31}(5) (2001)
  781--790

\bibitem{ZhoKho07}
Zhou, E., Khotanzad, A.:
\newblock Fuzzy classifier design using genetic algorithms.
\newblock Pattern Recognition \textbf{40}(12) (2007)  3401--3414

\bibitem{Kas01}
Kasabov, N.:
\newblock Evolving fuzzy neural networks for supervised/unsupervised on-line,
  knowledge-based learning.
\newblock IEEE Trans Systems, Man and Cybernetics \textbf{31}(6) (2001)
  902--918

\bibitem{MinLud08}
Minku, F.L., Ludermir, T.B.:
\newblock Clustering and co-evolution to construct network ensembles:
  \textsc{A}n experimental study.
\newblock Neural Networks \textbf{21} (2008)  1363--1379

\bibitem{AboRou03}
Abonyi, J., Roubos, J.A., Szeifert, F.:
\newblock Data-driven generation of compact, accurate, and linguistically sound
  fuzzy classifiers based on a decision-tree initialization.
\newblock International Journal of Approximate Reasoning \textbf{32}(1) (2003)
  1--21

\bibitem{PulKoi07}
Pulkkinen, P., Koivisto, H.:
\newblock Identification of interpretable and accurate fuzzy classifiers and
  function estimators with hybrid methods.
\newblock Applied Sof Computing \textbf{7} (2007)  520--433

\bibitem{CasCas05}
Castellano, G., Castiello, C., Fanelli, A.M., Mencar, C.:
\newblock Knowledge discovery by a neuro-fuzzy medeling framework.
\newblock Fuzzy Sets and Systems \textbf{149} (2005)  187--207

\bibitem{VerBac02}
Verikas, A., Bacauskiene, M.:
\newblock Feature selection with neural networks.
\newblock Pattern Recognition Letters \textbf{23}(11) (2002)  1323--1335

\bibitem{RouSet03}
Roubos, J.A., Setnes, M., Abonyi, J.:
\newblock Learning fuzzy classification rules from labeled data.
\newblock Information Sciences \textbf{150} (2003)  77--93

\bibitem{NauKru99}
Nauck, D., Kruse, R.:
\newblock Obtaining interpretable fuzzy classification rules from medical data.
\newblock Artificial Intelligence in Medicine \textbf{16}(2) (1999)  149--169

\bibitem{NozIsh96}
Nozaki, K., Ishibuchi, H., Tanaka, H.:
\newblock Adaptive fuzzy rule-based classification systems.
\newblock IEEE Trans Fuzzy Systems \textbf{4}(3) (1996)  238--250

\bibitem{OzyAlh07}
Ozyer, T., Alhajj, R., Barker, K.:
\newblock Intrusion detection by integrating boosting genetic fuzzy classifier
  and data mining criteria for rule pre-screening.
\newblock Journal of Network and Computer Applications \textbf{30}(1) (2007)
  99--113

\bibitem{ErZho08}
Er, M.J., Zhou, Y.:
\newblock Automatic generation of fuzzy inference systems via unsupervised
  learning.
\newblock Neural Networks \textbf{21}(10) (2008)  1556--1566

\bibitem{NakSch07}
Nakashima, T., Schaefer, G., Yokota, Y., Ishibuchi, H.:
\newblock A weighted fuzzy classifier and its application to image processing
  tasks.
\newblock Fuzzy Sets and Systems \textbf{158} (2007)  284--294

\bibitem{IshNoj07}
Ishibuchi, H., Nojima, Y.:
\newblock Analysis of interpretability-accuracy tradeoff of fuzzy systems by
  multiobjective fuzzy genetics-based machine learning.
\newblock International Journal of Approximate Reasoning \textbf{44}(1) (2007)
  4--31

\bibitem{ChaLia06}
Chang, P.C., Liao, T.W.:
\newblock Combining som and fuzzy rule base for flow time prediction in
  semiconductor manufacturing factory.
\newblock Applied Soft Computing \textbf{6} (2006)  198--206

\bibitem{MohHab08}
Mohamadi, H., Habibi, J., Abadeh, M.S., Saadi, H.:
\newblock Data mining with a simulated annealing based fuzzy classification
  system.
\newblock Pattern Recognition \textbf{41}(5) (2008)  1824--1833

\bibitem{Low95}
Lowe, D.G.:
\newblock Similarity metric learning for a variable-kernel classifier.
\newblock Neural Computation \textbf{7} (1995)  72--85

\bibitem{Chang74}
Chang, C.L.:
\newblock Finding prototypes for nearest neighbour classifiers.
\newblock IEEE Trans Computers \textbf{23} (1974)  1179--1184

\bibitem{VerNCA03}
Verikas, A., Bacauskiene, M., Malmqvist, K.:
\newblock Learning an adaptive dissimilarity measure for nearest neighbour
  classification.
\newblock Neural Computing \& Applications \textbf{11}(3-4) (2003)  203--209

\bibitem{MamAss75}
Mamdani, E.H., Assilian, S.:
\newblock An experiment in linguistic synthesis with a fuzzy logic controller.
\newblock International Journal of Man-Machine Studies \textbf{7}(1) (1975)
  1--12

\bibitem{PakIiv04}
Pakkanen, J., Iivarinen, J., Oja, E.:
\newblock The evolving tree---\textsc{A} novel self-organizing network for data
  analysis.
\newblock Neural Processing Letters \textbf{20} (2004)  199--211

\bibitem{Koh01}
Kohonen, T.:
\newblock Self-Organizing Maps. 3 edn.
\newblock Springer-Verlag, Berlin (2001)

\bibitem{GuzVer08}
Guzaitis, J., Verikas, A.:
\newblock An efficient technique to detect visual defects in particleboards.
\newblock Informatica \textbf{19}(3) (2008)  363--376

\end{thebibliography}



%\bibliographystyle{splncs}
%\bibliography{c:/Users/av/av/Latex/References/featSel}
%\bibliography{d:/av/Latex/References/featSel}
%\bibliography{C:/Users/av/av/Latex/References/featSel}

\end{document}
