%----------------------------------------------------------
% Nusrat Jahan
%
% Name of this file is ece2.tex
%----------------------------------------------------------
\documentstyle[fullpage,11pt,twocolumn]{article}
\begin{document}
\def\frac#1#2{{{#1}\over {#2}}}
\font\bftwo=cmbx10 scaled\magstep2
\title{\bftwo{An Application of Kernel Density Estimation in a Classification Problem}}
\author{\it Nusrat Jahan\\
Department of Mathematics and Statistics
\\ Mississippi State University,Mississippi State, MS 39762 USA
\\email:njahan@ra.msstate.edu}
\date{}
\maketitle
\begin{abstract}

A fundamental problem with sample data is that the underlying distribution is 
unknown. Therefore any modelling of the data or any kind of analysis has to be
carried out based on the estimated distribution of the data. kernel density estimation technique is one of the widely used technique for density estimation.
This is a non parametric technique. Therefore it does not impose any rigid
distributional assumption on the data. When we have a data set containing data from different densities(or classes), the problem becomes identifying which data belongs to which class or density. Using kernel method, the maximum likelihood value for each data is computed for each class. The class that produces highest maximum likelihood, it is highly likely that the data point belong to that class than any other class.
 

\end{abstract}
\section{Introduction}


If we have a set of observed data points assumed to be a sample from an 
unknown probability density then
there are primarily two different ways of estimating the underlying density 
[1].

\vspace{4mm}
\noindent
(i) Parametric Approach : If it can be reasonably assumed that the observed sample
is drawn from a known parametric family of distribution, then the values of
corresponding parameters can be estimated from the observed data and 
substituted in the density function.

\vspace{4mm}
\noindent
(ii) Nonparametric Approach : In this approach, no rigid assumption about the 
distribution of the observed data will be made. The underlying density will
be estimated from the observed sample data.

\vspace{4mm}
\noindent 
There are various nonparametric approaches to density estimation [2]. A brief 
introduction of some those methods are provided here.
Let $x_1, x_2, \ldots, x_n$ be independently and identically distributed random observations from unknown density, then there estimated density is denoted by
$ \hat{f}$.The methods discussed
here are primaily for univariate data, but they can be easily generalized to 
multivariate case.
\vspace{4mm}
\noindent
Histogram : the most widely used density estimator is the histogram.
$$ \hat {f}(x) =\frac{1}{n}x \frac {\mbox{ (no.of $X_{i}$ in same bin as x)}}
{ \mbox{(width of bin containing x)} } $$

\noindent The naive estimator :$$ \hat {f}(x) =\frac{1}{n}\sum_{i=1}^n 
\frac{1}{h}w \left(\frac{x-X_i}{h} \right) $$

\noindent 
where h is a small number and w(x) is a weight function defined as,

$$  w(x) = \left\{
           \begin{array}{ll}
           \frac{1}{2}  & {\mbox{if $x \le 1$}} \\
            0    & {\mbox{otherwise.}} \\
           \end{array}
           \right.
$$   

\vspace{4mm}
\noindent 
The kernel Estimator :
$$ \hat {f}(x) =\frac{1}{nh}\sum_{i=1}^n K
\left(\frac{x-X_i}{h}\right) $$

\noindent
where h is the window width, that is the smoothing parameter or bandwidth and 
the kernel function K satisfies the condition,

$$ \int_{- \infty}^{\infty} K(x)dx = 1. $$

\vspace{4mm}
\noindent 
The nearest neighbour method :
\noindent
 If the density at t is $f(t)$, then for a sample
of size n, exactly $(k-1)$ observations will fall in the interval $[t-d_{k} 
(t),t+d_{k} (t)]$, where $d_{k} (t)$ is the kth distance from t to the points 
of the 
sample. Therefore an estimate of the density at $t$ can be derived using,
$$ k-1 = 2d_k (t)n \hat{f}(t) $$
so kth nearest neighbour density estimate is 
defined by,
$$ \hat{f}(x) =\frac{(k-1)}{2nd_k (t).} $$

\vspace{4mm}
\noindent 
Variable Kernel method : The density estimate is constructed in the same way as
it is done in kernel estimation method, except the scale parameter is allowed 
to vary from one data point to another.

\vspace{4mm}
\noindent 
Orthogonal Series Estimators : In this approach the density function is 
estimated by estimating the coefficients of its Fourier expansion.

\vspace{4mm}
\noindent 
Maximum Penalized Likelihood Estimators :  This method places restrictions on
the class of densities over which the likelihood is to be maximized.

\vspace{4mm}
\noindent 

For this study, kernel density estimation technique ( for multivariate data)
combined with maximum likelihood method has been used. 


\vspace{4mm}
\noindent 

In this article, section 2 presents how kernel density estimation works. 
Section 3 discusses  the results from the data sets. An
overall summarization section ends this paper.



\section{Kernel Density Estimation}

The kernel estimator for univariate case (discussed in section 1) can easily 
be generalized for multivariate case [2]. In this case we assume, $x_1, x_2, \ldots, x_n$ be independently and identically distributed d-dimensional random vectors from unknown density, then there estimated density is denoted by,


$$ \hat {f}(x) =\frac{1}{n h^d}\sum_{i=1}^n K
\left(\frac{x-X_i}{h}\right) $$

\noindent
where h is the window width (smoothing parameter), d is the dimension of the  
data vector $x$ and 
the kernel function K(x) is now a function, defined for d-dimensional $x$ which
satisfies the condition,

$$ \int_{- \infty}^{\infty} K(x)dx = 1. $$

\noindent

Usually the kernel function is chosen to be symmetric unimodal probability
density function. If we look at the 
definition of kernel estimator it is easily understood that the smoothness of
the estimated density depends on the choice of h and the form of the estimated
 density depends on the form of the kernel function.

\vspace{4mm}
\noindent

{\bf{Properties of Kernel Estimate $\hat{f}$ }}

$(i)$ The kernel K is a density function and it is non-negative 
everywhere, therefore the estimated $\hat{f}$ will be a probability density 
function [3] .

$(ii)$  The $\hat{f}$ will contain all the continuity and differentiability 
properties of the kernel K [3].

\noindent

The kernel estimator becomes inefficient in case of long-tailed distribution.
The reason for this is because the window width is fixed across the entire 
sample, sometimes spurious noise appear at the tail part of the estiamted 
density [2]. 
 

\vspace{6mm}
Couple of widely used kernel functions are given below [2].

\vspace{4mm}
\noindent

Standard Multivariate Normal Density :
$$ K(x) = {(2 \pi)}^{d/2} exp(- \frac{1}{2} x^T x).  $$

\vspace{4mm}
\noindent

Multivariate Epanechnikov Kernel :

$$  K_e (x) = \left\{
           \begin{array}{ll}
         \frac{1}{2} c_{d}^{-1} (d+2)(1-x^T X)  & {\mbox{if $x^T x \le 1$}} \\
            0    & {\mbox{otherwise.}} \\
           \end{array}
           \right.
$$   
Where $c_d$ is the volume of the unit d-demensional sphere.
\vspace{4mm}
\noindent
For the special case of $d=2$, some useful kernels are available. These are


$$  K(x) = \left\{
           \begin{array}{ll}
            3 \pi^{-1}{(1-x^T x)}^2  & {\mbox{if $x^T x \le 1$}} \\
            0    & {\mbox{otherwise;}} \\
           \end{array}
           \right. $$   
\noindent
and
$$  K(x) = \left\{
           \begin{array}{ll}
           4 \pi^{-1}{(1-x^T x)}^3  & {\mbox{if $x^T x \le 1$}} \\
            0    & {\mbox{otherwise.}} \\
           \end{array}
           \right.  $$   


\vspace{6mm}

The choice of smoothing parameter, that is bandwidth is very crucial to 
density estimation. If it is too small, then the estimated density will be
rough, local maxima and minima will dominate. On the other hand if $h$, the 
bandwith is too big, the density will be smooth, but some specific 
characteristics will be lost due to smoothness. So in choosing $h$ one has to 
balance the desired smoothness with the desire to see the effect of actual 
data points. An optimal window width for smoothing of normally distributed
data with unit variance has been suggested by [1],

$$ h_{opt} = A(K) n^{-1/(d+4)}  $$

\noindent
where A(K) depends on the form of the kernel function. For a general data set 
with estiamted covariance matrix $S$, the numerical values for $A(K)$ can be
as given below for different kernels.

\noindent

Multivariate Normal K :

$$ A(K) = {4/(2d+1)}^{1/(d+4)} $$

\noindent

Multivariate Epanechnikov $K_e$ :
 
$$ A(K) ={ \frac{8d(2d+1)(d+4){(2 \sqrt{\pi})}^d}{(2d+1)c_d}}^{1/(d+4)} $$




\section{\bf{Discussion}}

For this project, two data sets (evaluation sets) were provided to be 
classified into different
classes (or densities). For each data set, a training set with known 
clssifications and a test set were provided. The purpose of the test set and training set was to train the specific classification algorithm that is to be used on evaluation sets. No information regarding to the context of the data were available.

In this paper I have used kernel density estimation technique to estimate the density or class for each evaluation set vectors, depending on the information obtained from training and test set vectors (whose classifications were known).

The application involved for each of the ith evaluation set vectors, the calculation of maximum likelihood value corresponding to each of k classes of the training set. Then all these maximum likelihood values were compared. The class that produced the highest ML value, has been identified as the class for the ith evaluation set vector. This process continued untill all the vectors of evaluation set were classified.

In this paper the multivariate normal kernel function is used. So the form of 
the estimated density function is,

$$ \hat {f}(x) =\frac{1}{n h^d {(2 \pi)}^{-d/2}}
     exp  {\sum_{i=1}^n \sum_{j=1}^m K
\left(\frac{x-X_{ij}}{h}\right)}^T 
\left(\frac{x-X_{ij}}{h}\right) $$

\noindent

where x represent each vector of the evaluation set and $X_{ij}$ is the jth 
training set vector for the ith class. And m is the number of vectors in ith class, n is the number of classes in training set. And ofcourse each vector is
d (10) dimensional.



\vspace{4mm}
\noindent
{\bf{  Group 1}}

\noindent

The dimension of the data sets in this group is 10 with 11 classes or densities
from where the data came. The training set has 528 vectors and the test set has
379 vectors. The bandwidth (h) used in this case is equal to .6737.

When the kernel density estimation algorithm has been used to identify the classes of test set vectors errors have been found in $55 \%$ of the cases.


\vspace{4mm}
\noindent
{\bf{  Group 2}}

\noindent

The dimension of the data sets in this group is 39 with 5 classes or densities
from where the data came. The training set has 925 vectors and the test set has
350 vectors.

When the kernel density estimation algorithm has been used to identify the classes of test set vectors, it identified only one class :class 1. error rate is
approximately $80 \%$.

\section{\bf {Summary}}

Kernel density estimation technique has wide applications in the area of statistical data mining. The mathematical properties are well established for kernel
densities. Though the results obtained here are not promising, still this method should be investigated further. 

  

\begin{thebibliography}{9}
\bibitem{}
Rao,Prakas.Nonpaarmetric Functional Estimation.Academic Press,London,1983.
\bibitem{}
Silverman,B.W. Density Estimation for Statistics and Data Analysis. Chapman and Hall, London, 1986.
\bibitem{}
Wegman,E.J. Nonparametric Probability Density estimation. Technometrics,14, pp.533-546,1972.

\end{thebibliography}


\end{document}

