\documentclass{article}
\usepackage{aaai,times,epsfig,algorithmic,algorithm,flushend} % to reflect AAAI format (referring to aaai.sty).
\nocopyright % to eliminate AAAI copyright slug in the footnote.
% This needs to be placed prior to '\maketitle'

\def\BibTeX{Bib\TeX}
\parindent=0pt
\parskip=\baselineskip
%\renewcommand\floatpagefraction{.9}
%\renewcommand\topfraction{.9}
%\renewcommand\bottomfraction{.9}
%\renewcommand\textfraction{.1}   
%\setcounter{totalnumber}{50}
%\setcounter{topnumber}{50}
%\setcounter{bottomnumber}{50}

\begin{document}
\title{Confusion Matrix-based Feature Selection}
\author{Sofia Visa \\ Computer Science Department\\ College of Wooster\\Wooster, OH\\ \texttt{svisa@wooster.edu} 
\And Brian Ramsay \\ Sentry Data Systems, Inc. \\ Fort Lauderdale, FL \\ \texttt{brian.ramsay@gmail.com}
\And Anca Ralescu \\ Computer Science Department \\ University of Cincinnati \\ Cincinnati, OH \\ \texttt{anca.ralescu@uc.edu}
\And Esther van der Knaap \\ Ohio Agricultural Research \\and Development Center\\The Ohio State University \\Wooster, OH\\ \texttt{vanderknaap.1@osu.edu}
}

%\date{April 8, 1999}
\maketitle

\begin{abstract}
This paper introduces a new technique for feature selection and illustrates it on a real data set. Namely, the proposed approach creates subsets of attributes based on two criteria: (1) individual attributes have high discrimination (classification) power; and (2) the attributes in the subset are complementary - that is, they misclassify different classes. The method uses information from a confusion matrix and evaluates one attribute at a time. 
{\bf Keywords:} classification, attribute selection, confusion matrix, k-nearest neighbors;
\end{abstract}

\section{Background}
In classification problems, good accuracy in classification is the primary concern; however, the identification of the attributes (or features) having the largest separation power is also of interest. Even more, for very large data sets (such as MRI images of brain), the classification is highly dependent on feature selection. This is mainly because the larger the number of attributes, the more sparse the data become and thus many more (exponential growth) training data are necessary to accurately sample such a large domain. In this sense, the high dimensional data sets are almost always under represented. This problem is also known in literature as "the curse of dimensionality". For example, a 2-attribute data set having 10 examples in the square defined by the corners (0,0) and (1,1) covers the domain acceptably. If the domain to be learned is the cube defined by the corners (0,0,0) and (1,1,1), 10 points will not cover this 3-D domain as effectively. 

Reducing the number of attributes for a classification problem is a much researched field. The brute force approach in finding the best combination of attributes for classification requires the trial of all possible combinations of the available n attributes. That is, consider one attribute at a time, then investigate all combinations of two attributes, three attributes, etc. However, this approach is unfeasible because there are $2^n-1$ such possible combinations for n attributes and, for example, even for n=10 there are 1,023 different attribute combinations to be investigated. Additionally, feature selection is especially needed for data sets having large numbers of attributes (e.g. thousands). Examples of such data domains with many features include text categorization and gene expression analysis. In the first example, each document is described by the most frequent words, leading to 20,000 words or more. In working with expressed genes in order to separate healthy from cancer patients, for example, the number of attributes may grow as high as 30,000 \cite{Guyon}. Another example of a challenging domain is the microarray data found in \cite{Xing}, where a hybrid of filter and wrapper approaches is employed to successfully select relevant features to classify 72 data examples in a 7,130 dimensional space.   

In addition to reducing the data dimensionality, selecting fewer attributes may improve classification and may give a better understanding of the underlying process that generated that data. Here we propose an attribute-selection technique based on a confusion matrix with the two-fold objective of better classification and better data understanding.

Depending on where the feature selection module is placed in relation to the classification module, there are two classes of methods for feature selections \cite{Jain}:
\begin{itemize}
 \item {\bf Filter methods} \cite{Pudil} rank features (or feature subsets) independently of the predictor. These methods investigate irrelevant features to be eliminated by looking at correlation or underlying distribution. For example, if two attributes have the same probability distribution, then they are redundant and one of them can be dropped. Such analysis is performed regardless of the classification method. Another filtering method ranks attributes based on the notion of nearest hit (closest example of same the class) and nearest miss (closest example of a different class)  \cite{Kira}. The $i^th$ feature ranking is given by the score computed as the average (over all examples) of the difference between the distance to the nearest hit and the distance to the nearest miss, in the projection of the $i^th$ dimension  \cite{Guyon}.

%ranking is illustrated in \cite{Kira}: for each example, the closest example of the same class (nearest hit) and the closest of a different class (nearest miss) are selected. 
 
 \item {\bf Wrapper methods} \cite{Kohavi} use a classifier to assess features (or feature subsets). For example, the decision tree algorithm selects the attributes having the best discriminatory power and places them closer to the root. Hence, besides the classification tree, a ranking of attributes results. 
\end{itemize}

Another classification of attribute selection methods considers the search technique of the feature subsets. There are two main greedy search strategies: forward selection and backward elimination. Both techniques yield nested subsets of features. The forward selection starts with one attribute and continues adding one attribute at a time if the newly formed subset gives better classification. During backward elimination, unpromising attributes are progressively eliminated \cite{Guyon}. This greedy search technique is often used in system identification. The result, in either case, is not guaranteed to yield the optimal attribute subset \cite{sugeno1993fuzzy}. 
%\begin{center}
% \begin{figure}[tbp]
%    {\centerline{\epsfig{figure=classes.eps,height=0.45\textheight,width= 0.4\textwidth,angle=270}}}
%     \caption{Illustration of the 8 morphological classes of the tomato fruits.}
% 			\label{fig:classes}
%\end{figure}
%\end{center}

In this research we investigate the use of the confusion matrix \cite{KP98} (which contains information about actual and predicted classifications) for attribute selection. In the context described above, this approach is a wrapper method because it uses a classifier to estimate the classification power of an attribute (or subset of attributes).
%In the context described above, this approach combines the wrapper and filter methods. This is because it uses a classifier (here, the k-nearest neighbors algorithm \cite{Duda}) to assess the performance of individual (or subsets of) attributes while considering the entries in the confusion matrix.   

\section{The Confusion Matrix and Disagreement Score} 
A confusion matrix of size n x n associated with a classifier shows the predicted and actual classification, where n is the number of different classes. Table \ref{conf-table} shows a confusion matrix for n = 2, whose entries have the following meanings:
\begin{itemize}
\item $a$ is the number of correct negative predictions;
\item $b$ is the number of incorrect positive predictions;
\item $c$ is the number of incorrect negative predictions;
\item $d$ is the number of correct positive predictions.
\end{itemize}
\begin{table}[t]
\caption{The confusion matrix for two-class classification problem.}
\label{conf-table}
\vskip 0.15in
\begin{center}
\begin{small}
\begin{sc}
\begin{tabular}{c|ccc} \hline \hline%\abovespace\belowspace
{}              & Predicted & Predicted \\
{}              & Negative  & Positive\\ \hline
Actual Negative &  $a$               & $b$ \\ 
Actual Positive &  $c$               & $d$ \\ \hline\hline
\end{tabular}
\end{sc}
\end{small}
\end{center}
\vskip -0.1in
\end{table}

The prediction accuracy and classification error can be obtained from this matrix as follows:
\begin{equation}
Accuracy = \frac{a+d}{a+b+c+d}
\end{equation}
\begin{equation}
Error = \frac{b+c}{a+b+c+d}
\end{equation}

We define the disagreement score associated with a confusion matrix in equation (\ref{eq:disagreement}). 
%between the actual label (also known as target) and the predicted label (also referred to as output) in equation (\ref{eq:disagreement}). 
According to this equation the disagreement is 1 when one of the quantities b or c is 0 (in this case the classifier misclassifies examples of one class only), and is 0 when b and c are the same. 
\begin{equation}
\label{eq:disagreement}
D = \left\{ \begin{array}{ll}
0 & \mbox{if $b=c=0$};\\
 \frac{|b-c|}{max\{ b,c\}} & \mbox{otherwise}.\end{array} \right. 
\end{equation}  
The attribute selection methodology proposed here selects attributes that not only have good discrimination power on their own, but more importantly are complementary to each other. For example, consider two attributes A1 and  A2, having similar classification accuracy. Our approach will select them as a good subset of attributes if they have a large disagreement in terms of what examples they misclassify. A large disagreement is indicated by D values closer to 1 for both attributes, but distinct denominators in equation (\ref{eq:disagreement}).    

\section{Algorithm for Confusion Matrix-based Attribute Selection}
The pseudocode outlined below shows the steps to perform confusion matrix-based attribute selection for a 2-class classification problem. This method basically constructs attribute-subsets that: (1) have attributes with good individual classification power, and (2) have attributes that are complementary (i.e. they disagree in their misclassifications).

Note that the algorithm may lead to several subsets of attributes to be further investigated, i.e. further the subset yielding higher classification accuracy may be selected.

Also, the algorithm does not account for the possibility that two individually lower ranked attributes may combine in a high classification accuracy subset due to their high complementarity. 

\begin{algorithm}
\caption{Pseudocode for Confusion Matrix-based Attribute Selection Algorithm}
\begin{algorithmic}
\REQUIRE 2-class data of $n$ attributes
\REQUIRE classification technique
\REQUIRE $k$ - number of member subset 
\ENSURE Output k-attribute subset as tuple $S_k = {(A_1,A_2,...,A_k)}$
\STATE  {Compute classifier $C_i$ based on feature $A_i$, $i=1..n$} 
\STATE {Obtain:} $Accuracy(C_i)$ and $ConfMatrix(C_i)$ 
\STATE {Rank $A_i$ according to} $Accuracy(C_i) \Rightarrow R_A$  
\FOR{$i = 1$ ... n} 
\STATE {Compute disagreement based on $ConfMatrix(C_i)$ as: }$D_i = \frac{|b-c|}{max\{b,c\}}$
%\STATE Compute k clusters (and their corresponding edges) using k-means\\
\ENDFOR%i
\STATE {Rank $A_i$ according to} $D_i \Rightarrow R_D$  
\STATE {Select top k (according to $R_A$) attributes having large D (according to $R_D$) but in different classes: $\Rightarrow S_k = {(A_1,A_2,...,A_k)}$}
\end{algorithmic}
\end{algorithm}

\begin{center}
 \begin{figure}[tbp]
    {\centerline{\epsfig{figure=decTree.eps,height=0.4\textheight,width= 0.4\textwidth,angle=270}}}
     \caption{Decision tree obtained with CART for all data and all attributes.}
 			\label{fig:decTree}
\end{figure}
\end{center}

\begin{table}[ht]
\caption{Data distribution across classes. In total, there are 416 examples each having 34 attributes.}
\label{data}
\centering
\scriptsize
\begin{tabular}{ l  l l }
\hline\hline
Class 	& Class label & No. of examples \\
\hline
1 &Ellipse &110\\
2 &Flat &115 \\
3 &Heart &29\\ 
4 &Long &36 \\
5 &Obvoid &32 \\
6 &Oxheart &12\\
7 &Rectangular &34\\
8 &Round &48\\
\hline\hline
\end{tabular}
\end{table}

\section{The Tomato Fruit Data Set}
\label{sec:DataSet}
The data set used in the experimental part of this research consists of 416 examples having 34 attributes and distributed in 8 classes (the class-distribution is shown in Table \ref{data}). This set was obtained from the Ohio Agricultural Research and Development Center (OARDC) research group led by E. Van Der Knaap \cite{TA} and the classification task is to correctly label a tomato fruit based on morphological measurements such as width, length, perimeter, circularity (i.e. how well a transversal cut of a tomato fits a circle), angle at the tip of the tomato, etc.

The data set was collected as follows: from the scanned image of a longitudinally section of a tomato fruit the 34 measurements are extracted by the Tomato Analyzer Software (TA) \cite{TA} developed by the same group. For a complete description of the 34 tomato fruit measurements and the TA software see \cite{TA2}.

%The 8 classes are illustrated in Figure \ref{fig:classes} and the distribution of the 416 examples is shown in Table \ref{data}. 

In addition to tomato classification, of interest here is to find which attributes have more discriminative power and further to find a ranking of the attributes.

\section{Data Classification and Attribute Selection}
In this section we show the decision tree classification of the tomato data set, then we illustrate our attribute selection algorithm (in combination with a k-nearest neighbor classifier) on two (out of 8) classes. These two classes (1 and 7) are identified by both, decision trees and k-nearest neighbors, as highly overlapping.
 
\subsection{Classification with Decision Trees - CART}
We used the Classification and Regression Trees (CART) method \cite{CART} because it generates rules that can be easily understood and explained. At the same time, classification trees have a built-in mechanism to perform attribute selection \cite{CART} and we can compare our set of selected attributes, obtained from the confusion matrix and k-nearest neighbors analysis, with the set of attributes identified by CART. However, we anticipate that these sets will not perfectly coincide, which only means that the two approaches quantify the importance of a given attribute (or subset of attributes) differently and that the two methods learn the data differently.%incorporate attribute selection as part of the training process 

The pruned decision tree obtained using CART is shown in Figure \ref{fig:decTree}. The train and test error associated with this tree are $11.54\%$ and $18.27\%$, respectively. As it can be seen from this figure, 10 rules can be extracted. In addition, CART selects the following 8 attribute as best in classification (listed in decreasing order of their importance): 
\begin{itemize}
\item 7 - Fruit Shape Idx Ext1
\item 13 - Circular 
\item 12 - Ellipsoid 
\item 11 - Fruit Shape Triangle 
\item 14 - Rectangular 
\item 10 - Distal Fruit Blockiness 
\item 8 - Fruit Shape Idx Ext2 
\item 1 - Perimeter 
\end{itemize}

We also investigate the k-nearest neighbors classifier as we will use this classification method in combination with our attribute selection approach. Figure \ref{fig:euclidian} shows the k - nearest neighbors classification error for k = 2,...,15. The top (blue) line corresponds to runs that include all 34 attributes and the bottom (red) line shows the error when only the best five attributes (identified by CART classification) are used. %As the figure shows, there is less error when using the five attributes then when using all 34. 
\begin{center}
 \begin{figure}[tbp]
    {\centerline{\epsfig{figure=euclidian.eps,height=0.45\textheight,width= 0.4\textwidth,angle=270}}}
     \caption{K - nearest neighbors classification error for k = 2,...,15. The top (blue) line corresponds to runs that include all 34 attributes and the bottom (red) line shows the error when only the best five attributes are used (these attributes were identified through CART classification).}
 			\label{fig:euclidian}
\end{figure}
\end{center}

As shown in Figure \ref{fig:euclidian}, the k-nearest neighbors classification technique consistently scores lower error when using only 8 attributes (the one selected by CART), rather then all 34. Thus, a natural question arising here is: is there a better combination of attributes then the one selected by CART for classification?  For k = 4 the k-nearest neighbors technique yields the lowest error, which justifies our choice of using k = 4 in the next experiments. 

\subsection{The Confusion Matrix for the Tomato Data Set }
When using all 34 attributes and all 8 classes, the confusion matrix obtained from the k-nearest neighbors clustering with k=4 is shown in Figure \ref{fig:confMatrixAll}, where along the x-axis are listed the true class labels and along the y-axis are the k-nearest neighbors class predictions. Along the first diagonal are the correct classifications, whereas all the other entries show misclassifications. The bottom right cell shows the overall accuracy. 

In this confusion matrix it can be seen that 8 examples of class 7 are wrongly predicted as class 1. %Similarly, class 8 has 3 examples wrongly predicted as class 1 and 2 as class 2. Thus we will further consider these two case studies for our confusion matrix-based attribute selection.  
Additionally, from the CART classification, the classes 1 and 7 are identified as the two classes overlapping the most. 
%Even more, Figure \ref{fig:classes} shows that, indeed, the tomato fruits in these two classes are very similar in size and shape. 
Thus the experiment presented next uses the confusion matrix attribute selection to better separate these two classes. Namely, we search for a subset of the 34 attributes such that the attributes are complementary in the sense described above and quantified in equation (\ref{eq:disagreement}). 

\begin{center}
 \begin{figure}[tbp]
    {\centerline{\epsfig{figure=confMatrixAllAttrAllClass.eps,height=0.4\textheight,width= 0.5\textwidth}}}
     \caption{Confusion matrix for all classes and all attributes. Class 7 has 8 examples wrongly predicted as class 1 (see top row).}
 			\label{fig:confMatrixAll}
\end{figure}
\end{center}

\begin{center}
 \begin{figure}[tbp]
    {\centerline{\epsfig{figure=conf14.eps,height=0.4\textheight,width=0.35\textwidth,angle=270}}}
     \caption{Confusion matrix for class 1 and 7 along attribute 14. Four examples of class 1 are misclassified as class 7, and 3 examples of class 7 belong to class 1.}
 			\label{fig:conf14}
\end{figure}
\end{center}

\begin{center}
 \begin{figure}[tbp]
    {\centerline{\epsfig{figure=conf20.eps,height=0.4\textheight,width= 0.35\textwidth,angle=270}}}
     \caption{Confusion matrix for class 1 and 7 along attribute 20. Fourteen examples of class 7 are misclassified as class 1.}
 			\label{fig:conf20}
\end{figure}
\end{center}

\begin{table}[ht]
\caption{Attribute ranking based on disagreement score.  The best classification attributes found by CART are shown in bold (they are also underlined). The attributes marked by (*) are the ones identified by our selection algorithm.}
\label{disagr}
\centering
\scriptsize
\begin{tabular}{ l  l l }
\hline\hline
Attr. number & Disagreement score & Class of largest error\\ \hline
	20   &  1   &  7  \\
   22   &  1   &  7 \\
   24    & 1    & 7 \\
   25    & 1    & 7 \\
   26   &  1    & 7 \\
   27    & 1    & 7 \\
   31   &  1    & 7 \\
   23   &  0.9655   & 7 \\
   28   &  0.9565   & 7 \\
   15   &  0.9524   & 7 \\
    2   &  0.9375   & 7 \\
   21   &  0.9375   & 7 \\
   29   &  0.9231   & 7 \\
   {\bf 12}  &  {\bf 0.9167}   & {\bf 7} \\\hline
   30   &  0.9167   & 7 \\
    {\bf 1}   &  {\bf 0.9091}   & {\bf 7} \\\hline
    3   &  0.9091   & 7 \\
    {\bf 7}   &  {\bf 0.9000}   & {\bf 7} \\\hline
   17   &  0.9000   & 7 \\
    5   &  0.8889   & 7 \\
   {\bf 11}   & {\bf 0.8824}   & {\bf 7 }\\\hline
   32   &  0.8750   & 7 \\
   34   &  0.8667   & 7 \\
   18   &  0.8462   & 7 \\
   {\bf 13}   & {\bf 0.8235}   & {\bf 7 }\\\hline
   19   &  0.8235   & 7 \\
    6   &  0.8182   & 7 \\
   33   &  0.8125   & 7 \\
   4  &  0.7273  &  7 \\
   {\bf 9*}   &  {\bf 0.7273}  & {\bf 7} \\
   {\bf 16*}   &  {\bf 0.6875}  & {\bf 7} \\
    {\bf 8*}   & {\bf 0.6250}  & {\bf 7} \\\hline
   {\bf 10* }  & {\bf 0.3000} &   {\bf 7 }\\\hline
   {\bf14*}   & {\bf 0.2500}&  {\bf  1} \\
\hline\hline
\end{tabular}
\end{table}
\subsection{Confusion Matrix-based Attribute Selection for Classes 1 and 7}
When using the data from classes 1 (Ellipse) and 7 (Rectangular), a data set of size 145 is obtained (110 in class 1 and 34 from class 7). 

As illustrated in Algorithm 1, for each of the 34 attributes, the k-nearest neighbor algorithm (with k = 4) is used for classification and the corresponding classification accuracy and confusion matrix are obtained (for each attribute). Further, the 34 attributes are ranked in the order of their individual performance in distinguishing between class 1 and 7, leading to the ranking set R = {14, 7, 8, 17, 1, 3, 6, 12, 30, 4, 9, 20, 29, 18, 26, 2, 10, 21, 34, 32, 11, 33, 5, 13, 19, 16, 15, 31, 25, 28, 24, 27, 22, 23}.

We first create growing nested subsets of attributes in the order specified by their individual classification abilities. Note that this particular choice of subsets is not part of Algorithm 1 and makes no use of the complementarity. We simply introduce it as a comparative model for our selection approach, which, besides the accuracy ranking, incorporates complementarity information as well.

Figure \ref{fig:acc17} shows the classification accuracy for subsets of attributes consisting of the top 1, top 2, top 3, etc. attributes from R (the subsets are shown on x-axis, while the y-axis shows classification accuracy). From Figure \ref{fig:acc17} it can be seen that the highest accuracy is achieved when the top 3 attributes are used together (i.e. attributes 14, 7, and 8), yielding a $97.2\%$ correct classification. 

The above approach is a (greedy) forward selection method, i.e. the attributes are progressively incorporated in larger and larger subsets. However, here we incorporate the attributes in the order dictated by their individual performance, yielding nested subsets of attributes. For example, we do not evaluate the performance of the subset consisting of first and third attribute. Indeed, it may be that this subset can perform better then considering all top three attributes. However, as indicated earlier in this paper, evaluating all possible combination is not a feasible approach. Thus, we propose {\bf to combine the attributes that are complementary, i.e. two (or more) attributes that may achieve individually similar classification accuracy but they have the largest disagreement (this information is extracted from the confusion matrix).}  

The disagreement scores for all 34 attributes when classifying data from classes 1 and 7 are listed in Table \ref{disagr}, column 2. As column 3 of the same table shows, only attribute 14 misclassifies more examples of class 1 then of class 7 (see bottom row). All other 33 attributes have the largest number of misclassifications attributed to class 7. Thus, for this particular data set, we will consider subsets that combine attribute 14 with one or more other attributes having the largest disagreement.

For example, Figures \ref{fig:conf14} and \ref{fig:conf20} show the confusion matrix for classes 1 and 7 when using attribute 14 and 20, respectively. These two attributes disagree the most as the above figures and Table \ref{disagr} show. %This table lists the attribute number, the disagreement score as defined by equation (\ref{eq:disagreement}), and the class having the largest number of errors in the corresponding confusion matrix.

Algorithm 1 is illustrated here for k = 2,3,4, and 5 only (note for k =1 the classification results are the same as in Figure \ref{fig:acc17}). The classification accuracy for these experiments is shown in Figures \ref{fig:a14Disagr}, \ref{fig:a14Disagr3}, \ref{fig:a14Disagr4}, and \ref{fig:a14Disagr5}, respectively. In addition to selecting the top k attributes in Table \ref{disagr} (this combination yields the first star in the above plots), we also plot the classification accuracy of the sliding (moving from top to bottom in Table \ref{disagr}) window of k attributes. %However, we do not form k-subsets arbitrarily chosen 

Figures	\ref{fig:a14Disagr}, \ref{fig:a14Disagr3}, \ref{fig:a14Disagr4}, and \ref{fig:a14Disagr5} show the classification accuracy of the k-nearest neighbor algorithm when attribute 14 is combined with all the other attributes in decreasing order of their disagreement scores (see Table \ref{disagr}). Figure \ref{fig:a14Disagr} shows results for 2-member subsets and the results from Figure \ref{fig:a14Disagr3} are obtained for 3-member subsets: attribute 14 and two consecutive attributes from Table \ref{disagr}.  

As Figure \ref{fig:a14Disagr5} illustrates, simply selecting the top attributes from Table \ref{disagr} (having the largest disagreement) does not ensure a better classification, nor is an increasing or decreasing trend observed when sliding down the table. This is because classification ability is not additive and opens up the question of whether a better k-subset of attributes can be obtained by mixing attributes across the table, not only the k-neighbors selection used here. 

Among the k-member subsets investigated here (note, there are more sliding window subsets for $k > 5$), the largest classification accuracy (98\%) is achieved for a 5-member subset, namely for the attribute-set 14, 9, 16, 8, and 10. The CART classifier recognizes these two classes with 93\% accuracy (using attributes 7, 13, 12, 14, 11, and 10), and the accuracy-ranking only (no complementarity information incorporated) selection achieves 97.3\% (using top 3 attributes: 14, 7 and 8). The attribute subset with the largest discriminating power (when using a k-nearest neighbors clustering, k = 4) is obtained with the confusion matrix-based attribute selection; however, it is not a large improvement as the classes are pretty well separated to begin with. 
\begin{center}
 \begin{figure}[tbp]
    {\centerline{\epsfig{figure=TopNAccuracy.eps,height=0.3\textheight,width= 0.5\textwidth}}}
     \caption{K - nearest neighbors classification accuracy for k = 4 when using data from classes 1 and 7 only. On x-axis are listed the nested subsets of attributes having top 1,2,3,...,34 attributes. The highest accuracy (97.2\%) is obtained for the subset having the top 3 attributes: 14,7, and 8.}
 			\label{fig:acc17}
\end{figure}
\end{center}
\begin{center}
 \begin{figure}[tbp]
    {\centerline{\epsfig{figure=AccuracyA14AndADisagr.eps,height=0.3\textheight,width= 0.5\textwidth}}}
     \caption{K - nearest neighbors classification accuracy for k = 4 when using 2-member subsets of attributes. Each subset contains attribute 14 and one of the remaining attributes; x-axis shows these subsets listed in the order of their complementarity - see Table \ref{disagr}. Largest accuracy is 97.3\%.}
 			\label{fig:a14Disagr}
\end{figure}
\end{center}

\begin{center}
 \begin{figure}[tbp]
    {\centerline{\epsfig{figure=AccuracyA14AndADisagr3.eps,height=0.3\textheight,width= 0.5\textwidth}}}
     \caption{K - nearest neighbors classification accuracy for k = 4 when using 3-member subsets of attributes. Each subset contains attribute 14 and two consecutive attributes (in the order of their complementarity - see Table \ref{disagr}). Largest accuracy is 97.3\%.}
 			\label{fig:a14Disagr3}
\end{figure}
\end{center}

\begin{center}
 \begin{figure}[tbp]
    {\centerline{\epsfig{figure=AccuracyA14AndADisagr4.eps,height=0.3\textheight,width= 0.5\textwidth}}}
     \caption{K - nearest neighbors classification accuracy for k = 4 when using 4-member subsets of attributes. Each subset contains attribute 14 and three consecutive attributes (in the order of their complementarity - see Table \ref{disagr}). Largest accuracy is 96.7\%.}
 			\label{fig:a14Disagr4}
\end{figure}
\end{center}

\begin{center}
 \begin{figure}[tbp]
    {\centerline{\epsfig{figure=AccuracyA14AndADisagr5.eps,height=0.3\textheight,width= 0.5\textwidth}}}
     \caption{K - nearest neighbors classification accuracy for k = 4 when using 5-member subsets of attributes. Each subset contains attribute 14 and four consecutive attributes (in the order of their complementarity - see Table \ref{disagr}). Largest accuracy is 98\%.}
 			\label{fig:a14Disagr5}
\end{figure}
\end{center}
%\subsection{Experiment 2 - Round vs. Ellipse and Flat}
%There are 273 examples for this experiment, 48 from the Round class (class 8), 110 from the Ellipse class (class 1), and 115 from the Flat class (class 2). The k-mean algorithm applied over each of the 34 attributes leads to 34 confusion matrices. By sorting the attributes in decreasing order of their individual performance, the top 10 ranked are: 7, 8, 33, 21, 18, 19, 13, 12, 20, 9. The accuracy obtained for nested subsets of attributes incorporating one attribute at the time (in the orther dictated by their individual ranking) is shown in Figure \ref{fig:acc128}.
%\begin{center}
% \begin{figure}[tbp]
%    {\centerline{\epsfig{figure=TopAccuracy128.eps,height=0.3\textheight,width= 0.6\textwidth}}}
%     \caption{K - nearest neighbors classification accuracy for k = 4 when using data from classes 1, 2, and 8 only.}
% 			\label{fig:acc128}
%\end{figure}
%\end{center}

\section{Conclusions and Future Work}
A new technique for attribute selection is proposed here. The method selects attributes that are complementary to each other, in the sense that they misclassify different classes, and favors attributes that have good classification abilities by themselves. This new approach is illustrated on a real data set. For two classes of interest within this data set, this technique found a better (i.e. yielding higher classification accuracy) subset of attributes, than using all attributes or even using the 8 attributes identified by CART. However, we must investigate this new approach in more data sets and in combination with other classification techniques (here only the k-nearest neighbor classifier was investigated). Another future direction is to investigate the use of subsets that combine complementary attributes, even if these attributes are weak classifiers by themselves. The challenging factor for this approach is the large number of subsets that must be investigated. Depending on the data set, if this search space is very large, then genetic algorithms can be used to explore the version space. We must also extrapolate this method to multi-class data sets and investigate its scalability factor. 
%We did not address the possibility that even if two variables are useless by themsekves, they can be useful together. 

\section{Acknowledgments}
Esther van der Knaap acknowledges support from the NSF grant NSF DBI-0922661. Sofia Visa was  partially supported by the NSF grant DBI-0922661(60020128) and by the College of Wooster Faculty Start-up Fund. 

\bigskip
\bibliography{maics11}
\bibliographystyle{aaai}
\end{document}


