\documentstyle[eclepsf]{llncs}

%% \title{Can a negative selection detect unique non-self cell 
%% in infinitely large sample of self cells?}

%% \title{Can a negative selection detect only a few non-self cells
%% existed in an enormous amount of self cells?}

\title{Can an immuno-fuzzy approach detect only a few non-self cells
existed in an enormous amount of self cells?}

\author{Akira Imada}
\institute{Brest State Technical University\\
           Moskowskaja 267, 224017 Brest, Republic of Belarus\\
           akira@bsty.by}

\begin{document}
\maketitle
\pagestyle{empty}
\thispagestyle{empty}

\begin{abstract}
We apply a technique lately reported to generate
a set of fuzzy rules that can recognize the non-self (abnormal) patterns
using only self (normal) samples to a kind of extreme case 
in which a  sample of non-self patterns are crucially smaller than the one of 
self-cells. Experiment is made with a data --- what we call a tiny flat island   
in a huge lake.
\end{abstract}




\section{Intoroduction}
\noindent
{\it ``A tiny flat island in a huge lake''} --- this is a problem we'd proposed in which
a few number of unknown patterns should be recognized or classified
from an enormous number of known patterns~\cite{akir}, which is up to now still an open issue.
Originally the problem desclibed, in particular, a fitness landscape 
when we searched for a weight configuration 
which was to givex a network with fully-conected spiking neurons a function of associative memory.
In this paper, we approach the problem from a view point of 
Negative Selection in Artificial Immune System.
That is, we take it just a pattern classification problem, in general,  
on the condition that we have two classes one of which has an extremely few patterns
while the other has almost infinite number of patterns. 
Or, we might as well take it  a task of discrimination of 
a few of non-self cells as anomaly patterns
from enormous amount of self cells which represent normal pattersn.\\


\noindent
One of the latest approaches, among others, from this point of view is by 
Ji \& Dasgupta~\cite{ji}. They wrote

\begin{quotation}
\noindent
{\it "The idea of negative selection was from T cell development process in the thymus. 
If a T cell recognizes self cells, it is eliminated before deployment
for immune functionality. In an analogous manner,
the negative selection algorithm generates the detector set
by eliminating any detector candidates that match self
samples. It is thus used as an anomaly detection
mechanism with the advantage that only the negative (normal) 
training data are needed.} 
\end{quotation}
Then authors proposed two algorithms: one is to generate detectors
of constant sized and the other variable sized sphers. 
They successfully created detectors which detect anomoaly patterns
just by training with normal patterns.


\noindent
When we think of a network intrusion detection, we usually don't know
what do anomaly patterns look like in advance. Hence this feature of
training with only normal pattern is really advantageous.
Our concern then is what if the number of non-self cells is extremely smaller
than self cells, which is of usual cases when we think of a network intrusion detection. 
In order to explore this issue, we formalize the problem as follows.
Assuming we have $n$-dimensiona7l patterns all of whose real-valued co-ordinates lie
in $[-1,1]$
%% between -1 and 1 
in which anomaly pattern has its co-ordinate whose value 
%% ranges from $-a$ to $a$ 
lie in $[-a,a]$ while all other patterns are normal patters.
We can control the difficulty of the task by changing the value of $a$.
In the ultimate case in which the pattern whose co-ordinates are all zero,
is called a-needle-in-a-haystack problem.


\section{Experiment}
\noindent
A set of fuzzy rules is used to cover the non-self rules.
Self/non-self sells are representecd by $n$-dimensional real valued vectors
whose coordinate lies in $[-1, 1]$.
That is, the self/non-self space is $[-1,1]^n$ and a self/non-self pattern
is represented by a vectore $(x_1, \cdots, x_n)$ where $x_i \in [-1,1]$.
Then a fuzzy rule to detect non-self patterns is
\begin{center}
If $x_1$ is $T_1$, $\cdots$, and $x_n$ is $T_n$ Then {\bf x} is non-self.
\end{center}
where $T_i$ is a fuzzy linguistic terms which is either of 
Low, Low-Middle, Middle, Middle-High, and High, here.
Each of $T_i$ maps the $x_i$ to a real value between 0 and 1
which expresses degree to how it is likely to via a membership function, which is defined
here using triangular and trapezoidal fuzzy membership functions 

Then a genetic algorithm is used to evolve these fuzzy rules.
with chromosomes being $(T_1, \cdots, T_n)$ starting with those
chromosomes randomly created. 
To be more specific, our chromosome is made up of $n$ integer genens
whose value is chosen from ${0, 1, 2, 3, 4}$.
The fitness of a rule is calculated by applying the rule
to all the self patterns one by one.

Each of such rules are applied to a pattern $\mbox{\bf x} = (x_1, \cdots, x_n)$
and evaluated how the pattern {\bf x} is likely to be a non-self by
\begin{displaymath}
\mbox{eval}_{R}(\mbox{\bf x}) = \min_{i=1, \cdots, m} \{ \mu_{T_i} (x) \}
\end{displaymath}

Fitness evaluation of a rule is made according to
\begin{displaymath}
\mbox{fitness} (R) = \frac{\sum_{\mbox{\bf x} \in Self} \mbox{eval}_R (\mbox{\bf x})}
{\vert Self \vert}
\end{displaymath}
which implys how the rule cover the non-self space.\\

The size of self cells is fixed to 400; each GA run is iterated for1000 generations
population of chromosmes are 100, to be comparable with Dasgupt et al's experiment.

%% Assuming our rule base is made up of $m$ such rules, and 

\section{Results and Discussion}
We have two criteria when we evaluate an anomaly detection system

There are two elements that define the cost function of
an anomaly detection system: 
the false positive (or false alarm) rate
--- the rate at which system warns when normal,
and the true positeve rate (or the detection) rate 
--- the system detects an attack correctly.
A good system should shown low false and high true positve rate. 
In general, a plot of the true positive rate against the false positive rate is called 
a Receiver Operating Characteristic curve (or ROC curve.)~\footnote{The accuracy of the test, 
in general, depends on how well the test separates 
the group being tested into those with and without the disease in question. 
Accuracy is measured by the area under the ROC curve.}. 
The evolution of the rule will be shown by ROC curve.



{\it
(1) First of all, create $N$ samples of $n$-dimensional continuous patterns each of 
whose coordinate $x_i$ $(i = 1, 2, \cdots, n)$ fullfils $a < \vert x \vert \le 1$.
These patterns represent self cells. (2) Then create hyper-sphere whose center locates
at random in our universe and radius is also randomely determined. 
This is a candidate detector of non-self cells.
(3) If this hyper shpere does not contain any self cells put it in $D$, the detector set.
Otherwise mutate the candidate detector 
until we find no self cells inside but at the maximum of $k$ times.
If we don't find such detector delete the candidate detector. (4) Repeat 2-3 until we 
find $p$ detectors.}

%The large area of non-self space is now covered by much fewer detectors. 

%% learning is all from self 
%%  more or less successful
%% but our concern is one non-self versus infinit number of self

%% Ayara wrote
%% Furthermore, it ensures that generated
%% detectors achieve as much coverage of non-self space as
%% possible (D'haeseleer, Forrest et al. 1996). 



\section{Algorithms}
Ayara et al
It was observed that the number of candidate detectors
increases exponentially with the size of the self-set,




In the latest version of a series
a real-valued negative selection algorithm

in the sense that
The negative detectors are chosen by matching
them to the self strings: if a detector matches it is discarded, otherwise,
it is kept.

\section{Experiments}
In those proposals, one of the goals is to create detectors 
which cover non-self space as much as possible.




%%\begin{tiny}
\begin{thebibliography}{99}

\bibitem{gome}
J. Gomez, F. Gonzalez, and  D. Dasgupta (2003)
"An Immuno-Fuzzy Approach to Anomaly Detection"
proceedings of the 12th IEEE International Conference on Fuzzy Systems, 
Vol. 2, pp. 1219-1224.


\bibitem{}
F. Provost, T. Fawcett, and R. Kohavi (1989)
``The case against accuracy estimation for comparing induction algorithms.''
Proceedings of international conference on machine learning, (San Francisco, Ca),
pp. 445--453.

\end{thebibliography}
%%\end{tiny}
\end{document}

1
