% by Mirella M. Moro; version: January/18/2012 @ 04:16pm
% -- 01/18/2012: more discussion on SBBD + JIDM; overall revision
% -- 09/03/2010: bib file with names for proceedings and journals; cls with shrinked {received}
% -- 08/27/2010: appendix, table example, more explanation within comments, editors' data

\documentclass[jidm,a4paper]{jidm} % NOTE: JIDM is published on A4 paper


   \newcounter{rtaskno}
\newcommand{\case}[1]{\refstepcounter{rtaskno}\label{#1}}


\usepackage{pgfplots}

\usepackage{amsmath}

\usepackage{graphicx,url}  % for using figures and url format
\usepackage[T1]{fontenc}   % avoids warnings such as "LaTeX Font Warning: Font shape 'OMS/cmtt/m/n' undefined"

\usepackage{array,multirow,graphicx}

%\usepackage{cite} % NOTE: do **not** include this package because it conflicts with jidm.bst

% Standard definitions
\newtheorem{theorem}{Theorem}[section]
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newdef{definition}[theorem]{Definition}
\newdef{remark}[theorem]{Remark}

% New environment definition
\newenvironment{latexcode}
{\ttfamily\vspace{0.1in}\setlength{\parindent}{18pt}}
{\vspace{0.1in}}

% ALL FIELDS UNTIL BEGIN{document} ARE MANDATORY

% The following data (volume, number and page) are given by the editors prior to publishing your article
\jidmVolume{?}
\jidmNumber{?}
\jidmYear{17}
\jidmMonth{February}
\setcounter{page}{1}


% Includes headers with simplified name of the authors and article title
\markboth{Tiago Buarque Assun\c{c}\~{a}o de Carvalho \textit{et al.}}
{Principal Component Analysis for Supervised Leaning: a Minimum Classification Error Approach}
%  -> \markboth{}{}
%         takes 2 arguments
%         ex: \markboth{M. M. Moro}{Any article title}


% Title of the article
%\title{JIDM - Journal of Information \\ and Data Management\footnote{The original version of this template, which was used up to volume 3, was created by Alberto Laender and Mirella Moro}}

%\title{Analysing\\Minimum Classification Error\\Principal Component Analysis}
\title{Principal Component Analysis for Supervised Leaning: a Minimum Classification Error Approach}

% List of authors
%IF THERE ARE TWO or more institutions, please use:
%\author{Name of Author1\inst{1}, Name of Author2\inst{2}, Name of Author3\inst{2}}
\author{Tiago Buarque Assun\c{c}\~{a}o de Carvalho\inst{1},  Maria Aparecida Amorim Sibaldo\inst{1}, Ing Ren Tsang\inst{2}, George Darmiton da Cunha Cavalcanti\inst{2}}

%Tiago Buarque Assunção de Carvalho, Maria Aparecida Amorim Sibaldo, Ing Ren Tsang, George Darmiton da Cunha Cavalcanti

%Affiliation and email
\institute{Universidade Federal Rural de Pernambuco, Brasil \\ \email{\{tiago.buarque, mariaaparecida.sibaldo\}@ufrpe.br}
% IF THERE IS ANOTHER INSTITUTION:
\and Universidade Federal de Pernambuco, Brasil  \\ \email{\{tir,gdcc\}@cin.ufpe.br}
}


% Article abstract - it should be from 100 to 300 words
\begin{abstract}

We present an alternative method to use Principal Component Analysis (PCA) for supervised learning. The proposed method extract features similarly to PCA, but the features are selected by minimizing the Bayes error rate for classification. We show that the proposed method selects features that best separate the elements of the different classes. Using real datasets, along with four different classifiers, experimental results show that the recognition accuracy of the proposed technique is improved compared to PCA.

\end{abstract}


% ACM Computing Classification System categories
%\category{H.2}{Database Management}{Miscellaneous} 
%\category{H.3}{Information Storage and Retrieval}{Miscellaneous}
%\category{I.7}{Document and Text Processing}{Miscellaneous}
\category{I.2.6}{Artificial Intelligence}{Learning.} 

% Categories and Descriptors are available at the 1998 ACM Computing Classification System
% http://www.acm.org/about/class/1998/
%  -> \category{}{}{}
%         takes 3 arguments for the Computing Reviews Classification Scheme.
%         ex: \category{D.3.3}{Programming Languages}{Language Constructs and Features}
%                   [data types and structures]
%                   the last argument, in square brackets, is optional.

% Article keywords
\keywords{Principal component analysis, Dimensionality reduction and manifold learning,  Supervised learning by classification, Data mining.}
%  -> \keywords{} (in alphabetical order \keywords{document processing, sequences,
%                      string searching, subsequences, substrings})


% THE ARTICLE BEGINS
\begin{document}

% This is optional:
\begin{bottomstuff}
% similar to \thanks
% for authors' addresses; research/grant statements
This work was partially supported by CAPES, CNPq and FACEPE.
\end{bottomstuff}

\maketitle


% ARTICLE NEW SECTION
%%%%%%%%%%%
%%% 	INTRODUÇÃO
%%%%%%%%%%%

%\begin{figure}
%	\center
%%	\includegraphics[width=1.0\textwidth]%
%    \includegraphics{./fig/case1raw}% picture filename
%	\caption{cap}
%	\label{fig:L}
%\end{figure}

\section{Introduction}

Principal Component Analysis (PCA) is a technique used to reduce data dimensionality. It projects data points into the directions of maximal variance within data space. These directions are the eigenvectors of data covariance matrix. In most of the cases, only some few eigenvectors are selected, normally the ones that have the highest eigenvalues. The eigenvalue is equivalent to the variance of a new variable, that is obtained by projecting the data into an eigenvector. The new variables not only have maximal variance, but they are also uncorrelated \cite{Bishop}. PCA is a very well-known technique that is used in several different applications such as face recognition \cite{eigenfaces} and text classification \cite{bracisA}.

From the  perspective of machine learning, PCA is an unsupervised feature extraction technique. 
Nonetheless, it is also used in supervised tasks such as in classification and regression. Some versions of supervised PCA have been proposed, for example, Barshan et al. \cite{Barshan} proposed a version of supervised PCA for classification. The method defines class representatives and computes PCA for these points. Directions with maximal variances for those points are also the directions that better separate the classes. Another version of supervised PCA was proposed by Bair et al. \cite{spca} for regression. The technique selects features that have high predictive power and compute PCA using only those features. Therefore, avoiding the interference of features that have high variance but low predictive power.

The Bayesian approach for classification is very robust and, similarly to PCA, it depends on the data covariance matrix \cite{Duda}.  Here,  we propose a supervised version of PCA that minimizes  the Bayes error rate for classification. 
The method projects the same features as PCA but selects the ones that minimize the Bayes error rate, while PCA selects the features with maximal variance. Therefore, it can be more suitable for classification task than standard PCA.  Since projections of maximal variance might not be the best way to separate data from different classes \cite{Bishop}.

The remainder of the article is organized as follows: the next section introduces the mathematical notation and how to use PCA for feature extraction.
Section \ref{sec:bayeserror} describes the Bayes error rate for classification and the imposed restrictions for calculating it.
The proposed method is defined in Section \ref{sec:proposed}. 
Section \ref{sec:exp_artificial} presents an analysis, using artificial data, of which features selected by each technique: standard PCA and the proposed method.
Section \ref{sec:exp_real} present experiments using real datasets.
Conclusion and future work are discussed in Section \ref{sec:conclusion}.



%%%%%%%%%%%
%%% 	PCA
%%%%%%%%%%%
\section{Feature extraction with PCA}
Suppose that the dataset is represented in a matrix.
The dataset matrix $\textbf{X}'_{n \times d}$ with $n$ points and $d$ features.
Each row of $\textbf X'$ is a data point and each column is a feature.
\begin{equation}
\textbf X' = \begin{bmatrix}
\textbf{x}_1^T\\ 
\textbf{x}_2^T\\ 
\vdots \\ 
\textbf{x}_n^T
\end{bmatrix}.
\end{equation}
The $j$-th point is  defined as a $d$ dimensional column vector $\textbf{x}_j$, 
\begin{equation}
\textbf x_j = \begin{bmatrix}
x_{j1}\\ 
x_{j2}\\ 
\vdots \\ 
x_{jd}
\end{bmatrix},
\end{equation}
for $ j = 1, \ldots, n$ and the data mean vector is 
\begin{equation} 
\bar{\textbf{x}}~=~\frac{1}{n}\sum_{j=1}^{n} \textbf x_j.
\end{equation}

The centered matrix is $\textbf{X}$ having the $j$-th row equal to $(\textbf x_j -  \bar{\textbf{x}})^T$:
\begin{equation}
\textbf X = \begin{bmatrix}
(\textbf x_1 -  \bar{\textbf{x}})^T\\ 
(\textbf x_2 -  \bar{\textbf{x}})^T\\ 
\vdots \\ 
(\textbf x_n -  \bar{\textbf{x}})^T
\end{bmatrix}.
\end{equation}

The covariance matrix of $\textbf X$ is defined as 
\begin{equation} 
\boldsymbol \Sigma_{\textbf X} = \frac{1}{n} \textbf X ^T \textbf X. 
\end{equation} 

Each column $\boldsymbol \xi_i,$ for $i = 1, \ldots, k$, of the matrix 
\begin{equation} 
\textbf E_k = [\boldsymbol \xi_1 \ldots \boldsymbol  \xi_k],
\end{equation} 
 is an eigenvector of $\boldsymbol \Sigma_{\textbf X}$.
 $\textbf E_k$ have up to  $d$ eigenvectors, for $k = 1, \ldots, d$.
Each eigenvector $\boldsymbol \xi_i$ have an associated eigenvalue $\lambda_i$,
 which is the variance of the extracted feature $\textbf f_i$, 
\begin{equation} 
\textbf f_i = \textbf X \boldsymbol \xi_i.
\end{equation} 

The value of the $i$-th extracted feature for the $j$-th point is $w_{ij}$, where $\textbf f_i=[w_{1i} \ldots w_{ni}]^T$.

The projection of the point $\textbf x_j^T = [x_{j1} \ldots x_{jd}]$ for the space of projected features is $\textbf w_j^T = [w_{j1} \ldots w_{jk}]$, given by
\begin{equation}
\textbf w_j^T = \textbf x_j^T\textbf{E}_k.
\end{equation}

The eigenvectors in $\textbf E_k$ are sorted, so that $\lambda_ 1 > \ldots > \lambda_k$. 
In PCA, the points are projected in the directions of maximal variances, these directions are the eigenvectors of the covariance matrix that has the greatest eigenvalues. 
The new data matrix $\textbf W_{n \times k}$ is defined as:
\begin{align}
\label{eq:w}
\textbf W = \textbf{XE}_k.
\end{align}
 Each row of this matrix is a point and each column an extracted feature. 

The covariance matrix of $\textbf W$ is $\boldsymbol \Sigma_{\textbf W} = n^{-1} \textbf W ^T \textbf W$, so that $\boldsymbol \Sigma_{\textbf W} = diag(\lambda_1, \ldots, \lambda_k)$. The variables are uncorrelated since the off-diagonal elements of $\boldsymbol \Sigma_{\textbf W} $ are equal to 0.  This property is very important for supervised learning, because it allows the selection of any subset of the projected variables by ignoring their interaction. 
However, selecting the eigenvectors of highest eigenvalues may not be the best strategy for classification problems, since projections of maximal variance may mix points from different classes \cite{Bishop} within the same region. In Section \ref{sec:exp_artificial} we show an example which highlights how the component of the highest eigenvalue is less suitable for classification than another component.
Therefore,  we propose a method of selecting  the eigenvectors by minimizing the Bayes error rate for classification.

%%%%%%%%%%%
%%% 	TAXA DE ERRO BAYESIANO
%%%%%%%%%%%
\section{Bayes error rate}
\label{sec:bayeserror}
The Bayes error rate for classification is defined as the probability of the classification error, \textit{i.e.}, the expected error rate. This error estimation can have a simplified form by imposing some restrictions.  Here, we consider the following five restrictions: (1) The data presents a multivariate normal distribution. (2) The problem has only two classes.  (3) The prior probabilities of both classes are equal. (4) Both classes have the same covariance matrix; the same assumption is used for PCA. Finally, (5) the features are statistically independent, similarly to PCA. 
Then the Bayes error rate is given by  \cite{Duda}:
\begin{equation}
P(\text{error}) = \frac{1}{\sqrt{2\pi}}\int_{r/2}^{\infty}e^{-u^2/2}du.
\end{equation}

The Bayes error rate decreases as $r$ increases. 
We define $r^2$ as the Mahalanobis distance between the mean vectors of the classes ($\boldsymbol \mu_1$ and $\boldsymbol \mu_2$):
\begin{equation}
r^2 = (\boldsymbol{\mu}_1-\boldsymbol{\mu}_2) \boldsymbol \Sigma^{-1} (\boldsymbol{\mu}_1-\boldsymbol{\mu}_2),
\end{equation}
$\boldsymbol \Sigma$ is the data covariance matrix, which is the same for both classes;
$\boldsymbol{\mu}_1^T = [\mu_{11} \ldots \mu_{1d}]$ and 
$\boldsymbol{\mu}_2^T = [\mu_{21} \ldots \mu_{2d}]$ are the mean vector for classes 1 and 2, respectively.


For independent features, the covariance matrix is a diagonal matrix.
The off-diagonal elements are the features covariances, which have values equal to zero.
This means that each feature is uncorrelated so $r$ has a special form:
\begin{align}
\label{eq:r}
r = \sqrt{\sum_{i=1}^d \left( \frac{ \mu_{1i}- \mu_{2i}}{ \sigma_i}\right )^2},
\end{align}
where $i = 1, \ldots, d$ are the indexes for the features. The variables 
 $ \mu_{1i}$ and  $ \mu_{2i}$ are the mean of the feature $i$ for classes 1 and 2, respectively.
 And $\sigma_i$ is the variance of the feature $i$ that is the same for both classes. 

We emphasize that the probability of classification error decreases as $r$ increases.
 From Equation (\ref{eq:r}),  we can conclude that each feature contributes for minimizing the probability of classification error. In fact, some feature contributes more than others.
The larger the difference between the means of the two classes related to the feature variance, the higher is the contribution of this feature to minimize Bayes error.
In the next section, we derive the proposed method based on this criterion of Bayes error minimization.

%%%%%%%%%%%
%%% 	MÉTODO PROPOSTO
%%%%%%%%%%%
\section{Proposed method}
\label{sec:proposed}

Since PCA generates uncorrelated features, and it also considers that the covariance matrix is the same for every class in the dataset (because it computes direction of maximal variance for a covariance matrix estimated for all data), then the Bayes error rate can be minimized proportionally to $r$, as defined in Equation (\ref{eq:r}), 
for features extracted using  Equation (\ref{eq:w}).
The proposed method considers these equations to choose the PCA projected variables.
However, instead of selecting the directions of maximal variance for the classification task, we select the directions that minimize Bayes error rate.

The problem continues to be restricted to two classes, setting $\textbf W = \textbf{XE}_d$, as in Equation (\ref{eq:w}). However, now the features are extracted for $d$ eigenvectors.
We define $w_{ij}$ as the value of the $i$-th new feature ($i = 1, \ldots, d$) for the $j$-th point ($j=1,\ldots,n$).
The mean of the $i$-th feature for the $c$-th class ($c = 1, 2$) is 
\begin{align}
\label{eq:wci}
\bar{w}_{ci} = \frac{\sum_{j=1}^{n}  w_{ij} \delta_{jc}}{\sum_{j=1}^{n}\delta_{jc}},
\end{align} 
where $\delta_{jc}$ is the Dirac's delta function $\delta_{jc} = 1$ if the $j$-point belongs to the $c$-th class, and $\delta_{jc} = 0$, otherwise.

According  Equation (\ref{eq:r}), each feature has a relevance for the classification task. Then we propose a score for the relevance of a feature for classification.
This score is calculated for each feature extracted with PCA, $s_i$ is the score for the $i$-th extracted feature:

\begin{align} 
\label{eq:si}
s_i = \left\{\begin{matrix}
(\bar{w}_{1i} - \bar{w}_{2i})^2 / \lambda_i & \text{if $\lambda_i \neq 0$}
\\ 
%\text{$0$ \; \; \; \; \; \; \; \; \; \; \;, 
0 & \text{if $\lambda_i = 0$}
\end{matrix}\right.,
\end{align}
where $\lambda_i$ is the eigenvalue of the eigenvector from which the $i$-th feature were computed, and $\bar{w}_{ci}$ is the mean of the $i$-th feature for the $c$-th class ($c = 1, 2$).
If $\lambda_i = 0$ the variance of the $i$-th extracted feature is zero, which means that the variable has the same value for all points. Therefore it is not useful for classification and its score is set to $s_i = 0$.  Otherwise, the score is positive and is defined as the absolute value of the difference between the mean of each class divided by the variance of the feature.
Features selected according to this score minimize the Bayes error rate.
In summary, the proposed method consists of the following steps:
\begin{enumerate}
    \item Project the data as $\textbf W = \textbf{XE}_d$, similar to  Equation (\ref{eq:w}).
    \item Compute the mean of each feature for each class $\bar{w}_{ci}$,  Equation (\ref{eq:wci}).
    \item Compute the score $s_i$ of each feature, Equation (\ref{eq:si}).
    \item Select $k$ features with the highest score.
    \item Define the projection matrix as:
    \begin{align}
    \textbf S_k = [\boldsymbol \xi_1 \ldots \boldsymbol \xi_k]
    \end{align}
     with the eigenvectors that have the highest scores $s_i$, such that $s_i \geq s_j$ if $\boldsymbol \xi_i \in \textbf S$ and $\boldsymbol \xi_j \notin \textbf S$.
    \item Project  the data as:
    \begin{align}
    \textbf{V = XS}_k, 
    \end{align}
    where $\textbf V_{n \times k}$ is the projected data matrix with $n$ points and $k$ discriminant features.
\end{enumerate}

The difference between standard PCA and the proposed method is that the selected features in PCA are the ones of highest eigenvalues ($\lambda_i$) and the selected features in the proposed method are the ones with the highest discriminant score ($s_i$). In the next section, we present an example using an artificial dataset.


%%%%%%%%%%%
%%% 	EXPERIMENTOS
%%%%%%%%%%%
\section{Example with artificial dataset}
\label{sec:exp_artificial}
In this section, we aim to explain how the proposed method works through an example.
We use a synthetic dataset to explain better how the proposed method differs from the standard PCA and how it improves the classification accuracy.
The dataset has two variables, \textit{i.e.}, each data point has two features.
It allows us to visualize the datasets in a plot.
The scatter plots of each dataset can be visualized in Figure \ref{fig:case2raw}. 
In these figures, it is also depicted (as a bell curve) the mean and the variance of the normal distribution along each axis. There is a bell curve for each class. Horizontal Axis is the first of the two features, and Vertical Axis is the second feature.

For this dataset, we consider all the five restriction imposed by the proposed method in Section \ref{sec:bayeserror} (the data presents a multivariate normal distribution, the problem has only two classes, the prior probabilities of both classes are equal, both classes have the same covariance matrix, and the features are statistically independent).
There are 50 examples from each class randomly generate from a normal distribution given a mean vector and a covariance matrix.
 Half of the examples are randomly chosen as the training set, and the other half is used as the test set for each holdout evaluation.
The mean and standard deviation of the accuracy is computed for 100 holdout repetitions.
This experimental protocol is the same used with the real datasets (Section \ref{sec:exp_real}). 
We also used the same four classifiers: 1-NN, Naive Bayes, Linear Discriminant, and Decision Tree.
For all the four cases, the accuracy of the recognition using raw data (2 original features) and feature extraction (1 extracted feature) with PCA and Proposed method is described in Table \ref{tab:artificial_results}.



\begin{table}[b]
\caption{The results for the \textbf{artificial dataset} showing the Mean Accuracy (M.A.), Standard Deviation (S.D.) and the number of Extracted Features (E.F.) for each method, using 1-NN, Naive Bayes, Decision Tree, and Linear Discriminant classifiers. Maximum mean accuracy within each column is emphasized for each classifier.}
\centering
\label{tab:artificial_results}
{
\begin{tabular}{lrrrrrrrrr}
\hline
Method& E.F.	&	\multicolumn{2}{c}{\textbf{ Decision Tree	}}  	&	\multicolumn{2}{c}{\textbf{ Naive Bayes	}} &	\multicolumn{2}{c}{\textbf{ Linear Discrim.	}}    &	\multicolumn{2}{c}{\textbf{ 1-NN }}    \\	\hline

Raw & 2	
&	80.3\%	&(	6.0\%	) % tree
&	78.5\%	&(	7.3\%	) % Naive
&	\underline{97.2\%}	&(	1.8\%	) % discrim
&	\underline{93.0\%}	&(	3.4\%	) % 1-NN
\\


PCA & 1	
& 	52.1\%	&(	7.4\%	) % tree
&	55.0\%	&(	6.5\%	) % naive
&	61.0\%	&(	6.6\%	) % discrim
&	50.9\%	&(	6.8\%	) %1-NN
 \\


Proposed & 1	
&	\underline{93.9\%}	&(	4.4\%	) % tree
&	\underline{94.5\%}	&(	4.1\%	)  % naive
&	95.3\%	&(	3.4\%	) % discrim
&	92.9\%	&(	4.3\%	) % 1-NN
\\		
 \hline													
								



\end{tabular}
}{}
\end{table}


For the dataset, the mean vector for class 1 ($\boldsymbol \mu_1$), the mean vector for class 2 ($\boldsymbol \mu_2$), and shared covariance matrix ($\boldsymbol \Sigma$) are defined as:
$$\boldsymbol \mu_1 = \begin{bmatrix}
0.0\\ 
0.0
\end{bmatrix}, \;
\boldsymbol \mu_2 = \begin{bmatrix}
0.9\\ 
0.9
\end{bmatrix},\;
\boldsymbol \Sigma = \begin{bmatrix}
1.0 & -0.9\\ 
-0.9 & 1.0
\end{bmatrix}.$$
The full dataset can be visualized in Figure \ref{fig:case2raw}, it is presented data scatter plot and the distribution of both variables (horizontal and vertical axis).
It is easy to note that each feature individually has huge class overlap in the raw data in Figure \ref{fig:case2raw}.
Figure \ref{fig:case2pca} shows the data transformed by PCA, \textit{i.e.}, all the points of the dataset projected using all the two PCA eigenvectors.
After the PCA transformation, the Horizontal Axis is the feature with maximal variance.
We highlight that the distribution of this feature has almost the same mean and standard deviation for both classes, \textit{i.e.}, almost a full class overlap.
The proposed method gives a higher score for the other feature, the one that presents greater mean separability.

Using the 1-NN classifier the proposed method, with only one feature, has accuracy close to 93\%, similar to the raw data (2 features). The PCA (1 feature) has accuracy close to 51\%.
For the Naive Bayes classifier, the proposed method showed an accuracy close to 95\%, which is greater than using raw data (79\%). The PCA accuracy is 55\%.
Using the Linear Discriminant classifier, the proposed method has accuracy close to 95\%, raw data 97\%, and PCA 61\%.
For the Decision Tree classifier, the proposed method has accuracy close to 94\%, greater than using raw data (80\%), while PCA accuracy is close to 52\%.
In Case A, the proposed method presents accuracy greater than PCA.


\begin{figure}[t]
\center
 \includegraphics[scale=0.9]{./fig/case2raw}
\caption{\textbf{Case A.} Scatter plot and the distribution of both variables in \textbf{raw data}.}
\label{fig:case2raw}
\end{figure}
\begin{figure}[t]
\center
 \includegraphics[scale=0.9]{./fig/case2pca}
\caption{\textbf{Case A.} Scatter plot and the distribution of both variables after \textbf{PCA} transformation.}
\label{fig:case2pca}
\end{figure}


In this case, the proposed method has recognition accuracy higher than PCA. The proposed method selects the features that best separate the classes. By the other side,  PCA selects the features the spread data the most. 
The proposed method is the proper method to choose the PCA directions for the classification task.
In the next section, we assess the proposed method using nine real datasets.

%%%%%%%%%%%
%%% 	EXPERIMENTOS
%%%%%%%%%%%
\section{Experiments with real datasets}
\label{sec:exp_real}
The experiments were performed using nine datasets from the UCI Machine Learning Repository \cite{uci}. Each dataset has two classes:
\begin{itemize}
\item \textbf{Banknote:} the Banknote Authentication Data Set that has 1,372 points and four features.
\item \textbf{Bank:} the Bank Marketing Data Set that has 4,521  points and 44 features (we converted some of the original 16 categorical features to new binary features).
\item \textbf{Climate:} the Climate Model Simulation Crashes Data Set that has 540 points and 18 features.
\item \textbf{Debrecen:} The Diabetic Retinopathy Debrecen Data Set that has 1,151 points and 19 features.
\item \textbf{Occupancy:} the Occupancy Detection Data Set that has 8,143 points (only the training file) and five features (we remove the date time feature).
\item \textbf{Pima: } The Pima Indians Diabetes Data Set that has 768 points and eight features.
\item \textbf{Spambase:} the Spambase Data Set that has 4,601 points and 57 features.
\item \textbf{VColumn:} the Vertebral Column Data Set that has 310 points and six features.
\item \textbf{WDBC:} the Breast Cancer Wisconsin
(Diagnostic) Data Set that has 569 points and 30 features.
\end{itemize}

Accuracy, the rate of corrected classified points, is the metric used to evaluate the methods. 
Each mean accuracy is the average accuracy for 100 holdout experiments. In each holdout experiment, 50\% of the points from each class were randomly chosen for training and the remaining points were used for testing. The training set was used for both PCA and the proposed method.
Both training and test sets were projected using $k$ selected eigenvector, $k = 1, \ldots, d$.
The 1-NN (Nearest Neighbor) with Euclidean distance, Naive Bayes with normal kernel smoothing density estimate, pruned Decision Tree with Gini's diversity index and a minimum of 10 nodes per leaf, and Fisher's Linear Discriminant were used for classification. 
The experiment was performed using Matlab 2017b Statistics and Machine Learning Toolbox.
%\footnote{\url{http://www.mathworks.com/help/stats/index.html}.}.

%\newpage
We calculated the confidence intervals assuming that each mean follows a Student's $t$ distribution. 
For a 95\% confidence level this interval is [$\bar a - E$, $\bar a + E$], where $\bar a$ is the mean accuracy, $E = 1.984 b / \sqrt{100}$, and $b$ is the accuracy standard deviation.
If there is no overlap between the confidence intervals of PCA and the proposed method the difference is considered significant \cite{confidence}.
The error bars shown for the datasets in the Figures \ref{fig:real_Bank} to \ref{fig:real_WDBC}, represent the confidence intervals. 
For some figures, the values are too small to appear in the plots. 
If there is no overlap between the error bars, we consider that the accuracies are significantly different.


The classification accuracy for each dataset and the four classifiers are summarized in Table \ref{tab:real_results} and they are discussed in following.
For each of the nine datasets, there are 20 mean accuracies in Table \ref{tab:real_results}, five average accuracies for each one of the four classifiers.
The five results are, from top to bottom:
\begin{enumerate}
\item mean accuracy for raw data,
\item mean accuracy for the proposed method with maximum difference to PCA,
\item mean accuracy for the PCA with maximum difference to the proposed method,
\item maximum mean accuracy for the proposed method, and
\item maximum mean accuracy for PCA.
\end{enumerate}
Other relevant results that are not described in the table are described in details during the analysis of the results. 
The next subsections describe the analysis for each dataset.

\begin{table}[t]
\caption{Mean accuracy for each dataset and four classifiers. The number of features for the respective accuracy is indicated within square brackets.}
\centering
\label{tab:real_results}
\begin{tabular}{clrrrr}
&& \textbf{Decision Tree}& \textbf{Naive Bayes}& \textbf{Linear Discriminant}& \textbf{1-NN} \\ \hline  
\parbox[t]{2mm}{\multirow{5}{*}{\rotatebox[origin=c]{90}{\textbf{Bank}}}}  & Raw  & [48] 87.4\%  & [48] 88.4\%  & [48] 90.0\%  & [48] 84.4\% \\
 & Proposed  & [1] 83.9\%  & [3] 89.2\%  & [9] 89.9\%  & [1] 82.8\% \\
 & PCA  & [1] 81.9\% & [3] 86.0\% & [9] 88.8\% & [1] 80.2\%\\
 & Proposed  & [11] 86.4\% & [3] 89.2\% & [13] 90.0\% & [13] 85.2\%\\
 & PCA & [38] 86.2\% & [2] 88.5\% & [38] 90.1\% & [5] 84.5\%\\
 \hline
\parbox[t]{2mm}{\multirow{5}{*}{\rotatebox[origin=c]{90}{\textbf{Banknote}}}}  & Raw  & [4] 97.5\%  & [4] 91.4\%  & [4] 97.6\%  & [4] 99.9\% \\
 & Proposed  & [1] 85.7\%  & [1] 89.0\%  & [1] 88.9\%  & [1] 85.0\% \\
 & PCA  & [1] 69.7\% & [1] 69.4\% & [1] 61.3\% & [1] 68.4\%\\
 & Proposed  & [4] 98.8\% & [4] 97.4\% & [4] 97.6\% & [4] 99.9\%\\
 & PCA & [4] 98.7\% & [4] 97.4\% & [4] 97.6\% & [4] 99.9\%\\
 \hline
\parbox[t]{2mm}{\multirow{5}{*}{\rotatebox[origin=c]{90}{\textbf{Climate}}}}  & Raw  & [18] 90.4\%  & [18] 92.0\%  & [18] 94.5\%  & [18] 89.0\% \\
 & Proposed  & [2] 87.7\%  & [9] 92.2\%  & [11] 94.0\%  & [7] 89.9\% \\
 & PCA  & [2] 86.5\% & [9] 91.5\% & [11] 92.0\% & [7] 86.8\%\\
 & Proposed  & [7] 88.7\% & [11] 92.3\% & [18] 94.5\% & [10] 90.3\%\\
 & PCA & [7] 88.6\% & [18] 91.9\% & [18] 94.5\% & [18] 89.0\%\\
 \hline
\parbox[t]{2mm}{\multirow{5}{*}{\rotatebox[origin=c]{90}{\textbf{Debrecen}}}}  & Raw  & [19] 61.0\%  & [19] 55.8\%  & [19] 71.2\%  & [19] 61.7\% \\
 & Proposed  & [3] 63.2\%  & [1] 62.7\%  & [3] 68.7\%  & [3] 62.5\% \\
 & PCA  & [3] 58.8\% & [1] 58.2\% & [3] 60.5\% & [3] 58.5\%\\
 & Proposed  & [14] 65.5\% & [19] 70.0\% & [18] 71.3\% & [4] 62.5\%\\
 & PCA & [10] 66.2\% & [19] 70.0\% & [11] 71.8\% & [7] 61.8\%\\
 \hline
\parbox[t]{2mm}{\multirow{5}{*}{\rotatebox[origin=c]{90}{\textbf{Occupancy}}}}  & Raw  & [5] 99.1\%  & [5] 97.8\%  & [5] 98.8\%  & [5] 98.8\% \\
 & Proposed  & [3] 98.9\%  & [3] 96.1\%  & [3] 98.6\%  & [1] 92.8\% \\
 & PCA  & [3] 98.9\% & [3] 95.8\% & [3] 97.6\% & [1] 92.8\%\\
 & Proposed  & [5] 99.0\% & [3] 96.1\% & [4] 98.8\% & [5] 98.8\%\\
 & PCA & [4] 99.0\% & [5] 96.1\% & [5] 98.8\% & [4] 98.8\%\\
 \hline
\parbox[t]{2mm}{\multirow{5}{*}{\rotatebox[origin=c]{90}{\textbf{Pima}}}}  & Raw  & [8] 70.0\%  & [8] 73.8\%  & [8] 76.5\%  & [8] 67.1\% \\
 & Proposed  & [1] 67.4\%  & [1] 72.5\%  & [1] 72.5\%  & [1] 65.6\% \\
 & PCA  & [1] 62.6\% & [1] 58.7\% & [1] 65.4\% & [1] 61.4\%\\
 & Proposed  & [5] 70.1\% & [2] 73.5\% & [7] 76.5\% & [5] 68.5\%\\
 & PCA & [6] 70.0\% & [8] 72.9\% & [8] 76.5\% & [5] 67.2\%\\
 \hline
\parbox[t]{2mm}{\multirow{5}{*}{\rotatebox[origin=c]{90}{\textbf{Spambase}}}}  & Raw  & [57] 90.6\%  & [57] 56.3\%  & [57] 88.9\%  & [57] 79.4\% \\
 & Proposed  & [3] 82.2\%  & [3] 82.7\%  & [4] 80.8\%  & [2] 76.2\% \\
 & PCA  & [3] 73.9\% & [3] 69.5\% & [4] 67.0\% & [2] 73.4\%\\
 & Proposed  & [14] 87.1\% & [56] 86.8\% & [49] 88.9\% & [17] 79.6\%\\
 & PCA & [37] 87.0\% & [53] 86.9\% & [56] 88.9\% & [54] 79.5\%\\
 \hline
\parbox[t]{2mm}{\multirow{5}{*}{\rotatebox[origin=c]{90}{\textbf{VColumn}}}}  & Raw  & [6] 80.2\%  & [6] 77.0\%  & [6] 83.0\%  & [6] 81.5\% \\
 & Proposed  & [2] 77.2\%  & [2] 80.9\%  & [2] 80.4\%  & [2] 76.4\% \\
 & PCA  & [2] 73.1\% & [2] 75.2\% & [2] 71.6\% & [2] 72.9\%\\
 & Proposed  & [4] 80.2\% & [3] 82.2\% & [3] 83.0\% & [6] 81.5\%\\
 & PCA & [5] 80.3\% & [5] 80.8\% & [5] 83.5\% & [5] 81.5\%\\
 \hline
\parbox[t]{2mm}{\multirow{5}{*}{\rotatebox[origin=c]{90}{\textbf{WDBC}}}}  & Raw  & [30] 92.2\%  & [30] 93.8\%  & [30] 95.2\%  & [30] 91.3\% \\
 & Proposed  & [3] 92.1\%  & [3] 93.9\%  & [3] 94.3\%  & [1] 85.4\% \\
 & PCA  & [3] 90.2\% & [3] 89.6\% & [3] 87.5\% & [1] 85.4\%\\
 & Proposed  & [3] 92.1\% & [3] 93.9\% & [15] 95.3\% & [30] 91.3\%\\
 & PCA & [5] 91.9\% & [5] 92.0\% & [17] 95.8\% & [5] 91.4\%\\
 \hline
\end{tabular}


\end{table}


\subsection{Bank Dataset}
The maximum accuracy for the Bank dataset is 90\% using the Linear Discriminant (LD) classifier. The proposed method (PM) achieve this result using only 13 of the 48 features, and PCA using 34 features.
For 38 features with PCA and LD, the mean accuracy is 90.1\%, but it is not significantly higher.
For the Naive Bayes (NB) classifier using 2 features, the accuracy for PCA is 88.5\% and for PM 89.2\% (89.21\% for three features).
For LD with two features, the accuracies are 89.2\% (PM) and 88.9\% (PCA).
For many different numbers of features, considering the four classifiers, the proposed method presented significant higher accuracy, although the difference is only 1\% (Figure \ref{fig:real_Bank}).

\begin{figure}[t]
\center
 \includegraphics[scale=0.9]{./fig/real_Bank}
\caption{Mean accuracies for the Bank dataset per number of extracted features, per each classifier.}
\label{fig:real_Bank}
\end{figure}


\subsection{Banknote Dataset}
Figure \ref{fig:real_Banknote} depicts the results for Banknote dataset.
The maximum accuracy of 99.9\% occurs for the 1-NN classifier using all the four features.
However, the proposed method (PM) have an accuracy of 97.5\% using only two features, and PCA 85.1\%.
For Naive Bayes (NB) using four features after projection increases the accuracy to 97.4\% comparing to raw data (91.4\%), similar fact occurs to the Linear discriminant classifier.
The greatest difference is 89.0\% (PM) and 69.4\% (PCA) for one extracted feature using the NB classifier.
A similar difference occurs for other classifiers using the same number of features.


\begin{figure}[t]
\center
 \includegraphics[scale=0.9]{./fig/real_Banknote}
\caption{Mean accuracies for the Banknote dataset per number of extracted features, per each classifier.}
\label{fig:real_Banknote}
\end{figure}


\subsection{Climate Dataset}
Figure \ref{fig:real_Climate} depicts the results for Climate dataset.
The maximum accuracy of 94.5\% occurs using all the features with Linear Discriminant (LD) classifier.
However, the proposed method (PM) has an accuracy of 94\% using 11 features. For the same number of features with PCA, the accuracy is 92\%.
For the Decision Tree classifiers, the accuracy decreases when using more than seven features for both methods.
PM presents accuracy significantly higher for many numbers of features for all the classifiers.
The maximal accuracy for PM is higher or equivalent to PCA in all classifiers, and the PM requires fewer features for Naive Bayes and 1-NN.


\begin{figure}[t]
\center
 \includegraphics[scale=0.9]{./fig/real_Climate}
\caption{Mean accuracies for the Climate dataset per number of extracted features, per each classifier.}
\label{fig:real_Climate}
\end{figure}


\subsection{Debrecen Dataset}
Figure \ref{fig:real_Debrecen} depicts the results for Debrecen dataset.
For this dataset PCA and the proposed method (PM) achieve very similar accuracy using 7 or more extracted features.
For Decision Tree (DT) and Linear Discriminant (LD), PCA demands fewer features for the higher accuracy. 
Except for DT and LD (around ten extract features), PM presents accuracy higher or similar than PCA for the same number of features.
Most of the greatest difference occurs for three extracted features; they are 68.7\% (PM) and 60.5\% (PCA).
PM presented a result very close to the maximal accuracy (71.8\%, 11 features, PCA) using very few features.

\begin{figure}[b]
\center
 \includegraphics[scale=0.9]{./fig/real_Debrecen}
\caption{Mean accuracies for the Debrecen dataset per number of extracted features, per each classifier.}
\label{fig:real_Debrecen}
\end{figure}


\subsection{Occupancy Dataset}
Figure \ref{fig:real_Occupancy} depicts the results for Occupancy dataset.
For this dataset PCA and the proposed method present very similar accuracies.
The greatest difference occurs for three extracted features and Linear Discriminant classifier: 96.1\% (proposed) and 95.8\% (PCA).

\begin{figure}[t]
\center
 \includegraphics[scale=0.9]{./fig/real_Occupancy}
\caption{Mean accuracies for the Occupancy dataset per number of extracted features, per each classifier.}
\label{fig:real_Occupancy}
\end{figure}


\subsection{Pima Dataset}
Figure \ref{fig:real_Pima} depicts the results for Pima dataset.
The greatest difference occurs using a single extracted feature for all the classifiers, for Naive Bayes the results are 72.5\% (proposed method) and 58.7\% (PCA). The accuracy of the proposed method (PM) with one feature is similar to the accuracy of PCA using all the eight features (72.9\%).
The greatest of 76.5\% accuracy occurs for the Linear Discriminant and PM using seven features.

\begin{figure}[b]
\center
 \includegraphics[scale=0.9]{./fig/real_Pima}
\caption{Mean accuracies for the Pima dataset per number of extracted features, per each classifier.}
\label{fig:real_Pima}
\end{figure}


\subsection{Spambase Dataset}
Figure \ref{fig:real_Spambase} depicts the results for Spambase dataset.
PCA and the proposed method (PM) have similar accuracies. The greatest difference occurs for few extracted features.
The maximum accuracy of 90.6\% occurs for raw data (57 features) and the Decision Tree (DT) classifier.
A good trade-off result is for PM with DT 87.1\% for 14 extracted features, because it is a high accuracy for few extracted features.
PCA has similar accuracy with DT for 37 features (2,64 times more features).
The greatest difference between PCA and PM are for Linear Discriminant with four features, 80.8\%(PM) and 67\% (PCA).
A similar difference occurs for Naive Bayes (3 features) 82.7\% (PM) and 69.5\% (PCA), note that is higher than accuracy for raw data (56.3\%).

\begin{figure}[t]
\center
 \includegraphics[scale=0.9]{./fig/real_Spambase}
\caption{Mean accuracies for the Spambase dataset per number of extracted features, per each classifier.}
\label{fig:real_Spambase}
\end{figure}



\subsection{VColumn Dataset}
Figure \ref{fig:real_VColumn} depicts the results for VColumn dataset.
The greatest difference occurs for the Linear Discriminant (LD) classifier, 80.4\% (proposed method) and 71.6\% (PCA). 
The highest accuracy is also achieved using LD, 83.5\% (PCA, five features), but it is not significantly different from 83\% (PM, three features).
For 2 and three extracted features PM has accuracy significantly higher, and close to the maximum, with every classifier.

\begin{figure}[t]
\center
 \includegraphics[scale=0.9]{./fig/real_VColumn}
\caption{Mean accuracies for the VColumn dataset per number of extracted features, per each classifier.}
\label{fig:real_VColumn}
\end{figure}



\subsection{WDBC Dataset}
Figure \ref{fig:real_WDBC} depicts the results for WDBC dataset.
The greatest accuracy occurs for the Linear Discriminant (LD) classifiers, 95.8\% (PCA, 17 features), 95.3\% (proposed method, 15 features), and 95.2\% (raw data, 30 features).
The greatest difference also occurs for LD (3 features), 94.3\% (proposed) and 87.5\% (PCA), almost 7\%.
The proposed method presented accuracy very close to the maximum using only 10\% (3 out 30) of the features.

\begin{figure}[b]
\center
 \includegraphics[scale=0.9]{./fig/real_WDBC}
\caption{Mean accuracies for the WDBC dataset per number of extracted features, per each classifier}
\label{fig:real_WDBC}
\end{figure}

\subsection{Final remarks}
For all the 36 (4 classifiers $\times$ 9) plots, the only case where PCA has accuracy higher than proposed method (PM) for few extracted features is for 1-NN and WDBC dataset.
For the Bank dataset with Naive Bayes classifier, there is a case where PCA accuracy is significantly greater than proposed method (from 10 to 34 extracted features), but those accuracies are much smaller than the accuracy for two extracted features.
In 34 out 36 cases, PM present accuracy close or significantly greater than PCA for the same number of extracted features.
The greatest accuracy differences occur using less than half of the features.
The proposed method can extract more discriminant accuracy and reduce accuracy, and it seems more suitable for dimensionality reduction in supervised tasks.









%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Conclusion}
\label{sec:conclusion}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
We proposed a feature extraction technique that is similar to PCA but selects features that minimize the Bayes error rate instead of features that maximizes the variance. The method presented a higher mean accuracy compared to PCA  in two real datasets using a small number of features. 
The accuracy was evaluated using four distinct classifiers.
Experiments with four artificial datasets show how the proposed method chooses discriminant features.
We present some graphical examples to describe how the proposed method selects the directions that reduce the overlap between the classes.


For future work, the proposed method can be extended to problems with more than two classes. 
Also, the Bayes error rate can be computed using fewer restriction. 
By doing these extensions, it is possible to evaluate the proposed technique using other real datasets.
Another research investigation is to test the method presented herein other PCA-based techniques such as  Fractional Eigenfaces \cite{carvalho} and Supervised Fractional Eigenfaces \cite{carvalho15}. 

% INCLUDE BIBLIOGRAPHY WHICH MUST FOLLOW jidm.bst TEMPLATE
\bibliographystyle{jidm}
\bibliography{refs}
% For information on how to write bibliography entries, 
% see file jidmb.bib



\begin{received}
\end{received}

\end{document}
