\section{Feature Subset Selection}

We now investigate methods of feature subset selection to intelligently reduce attributes in data sets.

\subsection{Motivation}

We earlier discussed the application of active learning to the field of software engineering.  Software engineering data sets are typically large batches being input at once and can be very time consuming to process.  Feature subset selection algorithms provide a method to reduce the features of a data set to those that are deemed to be the most valuable to the analysis.  This reduction can lead to higher true positive and lower false positive rates while significantly reducing the time required to analyze the data set.

\subsection{Principle Component Analysis}

Principle Component Analysis is a feature subset selection technique that employees Eigen-vectors to find the most significant features of the data \cite{Smith05}.    

Principle Component Analysis works as follows\cite{Smith05}.  We begin by computing the mean $m$ for each attribute $x$ in the data set $D$.  We subtract $m$ from all values $x_i$ producing a \textit{zero-mean} data set..  We then calculate the covariance matrix of the zero-mean data set. The covariance matrix is then used to calculate the eigen-values and eigen-vectors of the data set.  Larger eigen-values indicate strong patterns for a given attribute while smaller eigen-values indicate weaker, less interesting patterns for an attribute. 


\subsection{Term Frequency-Inverse Document Frequency}

Term Frequency-Inverse Document Frequency (tf-idf) is a simple feature subset selection technique that traditionally been applied to text document mining but has been applied to search-based software engineering with much success.

\begin{figure}[htb]
%\begin{algorithmic}
%\STATE int distance(point p1, point p2)
%\STATE $\lbrace$
%\STATE return $sqrt( ( p1.x - p2.x )^2 + (p1.y - p2.y)^2 )$
%\STATE $\rbrace$
%\end{algorithmic}
\includegraphics[scale=0.6]{ExampleFunction.eps}
\caption{An example function \cite{Binkley10}.}
\label{fig:Function}
\end{figure}

tf-idf begins by extracting terms from source code in our case.  Binkley notes that terms are most often extracted from identifiers and comments in the source code.  Binkley provides the example function in Figure \ref:{fig:Function}. We extract identifiers \textbf{int}, \textbf{distance}, \textbf{p1}, \textbf{p2}, \textbf{return}, \textbf{sqrt}, \textbf{x}, and \textbf{y} from the example function.  

 We begin by calculating the \textit{term frequency (tf)} by counting the frequency of the term $t_i$ in code modules $m_j$ and optionally normalizing by the number of all terms in $m_j$ to offset a bias in large documents.  We calculate the \textit{inverse document frequency (idf)} by dividing the number of modules $M$ by the number of modules containing the $t_i$ and applying a logarithm to the result. We construct the weight vector for our terms by multiplying $tf_{i,j}$ and $idf_{i,j}$.  
 
\begin{figure}[htb]
\begin{center}
%\doublespacing
%$tf_{i,j} = \frac{n_{i,j}}{\Sigma_{k} n_{k,j}}$
%\\
%$idf_i = log \frac{|M|}{\lbrace|m : t_i \in m|\rbrace|}$
%\\
%$tfidf_{i,j} = tf_{i,j} \times idf_{i}$
\includegraphics[scale=0.6]{TFIDFFormulas.eps}
\end{center}
\caption{Formulas for tf, idf, and the final tf-idf feature vector.}
\label{fig:FormulasTFIDF}
\end{figure}

The weight of a term expresses the importance of the term in a document relevant to the entire collection of documents.  A term that occurs rarely in the entire collection of documents but frequently in a module would receive a high weight, while a term that appears frequently in all modules in the collection such as programming language constructs would receive a low weight and could be safely removed from our feature selection.

Table \ref{tab:ReducerCluster} demonstrates Principle Component Analysis and tf-idf with a combination of clustering algorithms.  It is worth noting that tf-idf requires less time than Principle Component Analysis for each respective clustering algorithm.  tf-idf performs well with K-means and GenIc clustering algorithms when comparing information gain to their Principle Componenent Analysis counterparts.  





