\documentclass[namedreferences]{kluwer}
\usepackage{url,times,graphicx,amssymb}
\usepackage{array,../../tex/bar}
%\usepackage{multirow}
\newcommand{\egs}{521}

\newenvironment{smallitem}{
   \setlength{\topsep}{0pt}
   \setlength{\partopsep}{0pt}
   \setlength{\parskip}{0pt}
   \begin{itemize}
   \setlength{\leftmargin}{.2in}
   \setlength{\parsep}{0pt}
   \setlength{\parskip}{0pt}
   \setlength{\itemsep}{0pt}}{\end{itemize}}

\newcommand{\bi}{\begin{itemize}}
\newcommand{\ei}{\end{itemize}}
\newcommand{\be}{\begin{enumerate}}
\newcommand{\ee}{\end{enumerate}}
\newcommand{\bd}{\begin{description}}
\newcommand{\ed}{\end{description}}
\newcommand{\fig}[1]{Figure~\ref{fig:#1}}
\newcommand{\eq}[1]{Equation~\ref{eq:#1}}
\newcommand{\tion}[1]{\S\ref{sec:#1}}




\begin{document}
\begin{article}
\begin{opening}

\title{How Simple is Software Defect Detection?}

\author{Tim \surname{Menzies}\email{tim@menzies.us}\\
Kareem \surname{Ammar}\email{kammar@csee.wvu.edu}
}
\institute{Lane Department of Computer Science,West Virginia University}
\author{Allen \surname{Nikora}\email{allen.P.Nikora@jpl.nasa.gov}}
\institute{Jet Propulsion Laboratory,
California Institute of Technology}
\author{Justin Di Stefano\email{justin@lostportal.net}\thanks{
Submitted to the Journal of Empirical Software Engineering, October, 2003}
\thanks{
Available from \protect\url{http://menzies.us/pdf/03simpled.pdf}.}
\thanks{Work sponsored by
the NASA OSMA SAS Program led by the NASA IV\&V Facility.
The work was 
conducted at West Virginia University (partially supported by
NASA contract NCC2-0979/NCC5-685) and at the Jet Propulsion
Laboratory, California Institute of Technology (under a NASA
contract).  The JPL activity is managed locally at
JPL through the Assurance and Technology Program Office. Reference
herein to any specific commercial product, process, or service by
trade name, trademark, manufacturer, or otherwise, does not
constitute or imply its endorsement by the United States
Government or the Jet Propulsion Laboratory, California Institute
of Technology}}
\institute{Galaxy Global Corporation, Fairmont, West Virginia}


\begin{abstract} Software {\em defect detectors} input
structural metrics of code  and output a prediction of how faulty a
code module might be. Previous studies have shown
that such metrics many  be confused by the
high correlation between metrics. To resolve
this, {\em feature subset selection} (FSS) techniques such as {\em
principal components analysis} can be  used to reduce the
dimensionality of metric sets in hopes of creating smaller and
more accurate detectors. This study benchmarks several FSS
techniques and reports several studies where a large set metrics
were reduced to a handful with little loss of detection
accuracy. This result raises the possibility that software defect
detection may be much simpler than previously believed.
\end{abstract}
\keywords{
empirical studies and metrics;
software testing and verification;
principal
components analysis.
 fault models;
metrics: product metrics; defect detectors;
artificial intelligence: learning;
feature subset selection.
}
\end{opening}



\section{Introduction}

\begin{raggedleft}
{\em Perfection is reached, not when there is no \\
longer anything to add, but when there is no longer \\
anything to take away.} -- Antoine de Saint-Exupery\\
\end{raggedleft}

~\\

Over the past several years, many
  sophisticated  structural measurements of software systems
 have been used to
identify fault-prone components and predict their fault content.
Examples of this work include the classification methods proposed
by Khoshgoftaar and Allen~\cite{khoshgoftaar99} and by Ghokale and
Lyu~\cite{gokhale97}; Schneidewind's work on Boolean Discriminant
Functions~\cite{schn97}, Khoshgoftaar's application of
zero-inflated Poisson regression to predicting software fault
content~\cite{khoshgoftaar01}, and Schneidewind's investigation of
logistic regression as a discriminant of software
quality~\cite{schn01}. 

 An evident
trend found within the above work is the increasing sophistication
and complexity of the analysis techniques. Increasing the sophistication of
 our defect detection
is not necessarily  the best approach. This paper will argue
that such increasing complexity is unnecessary. It will be shown
that, at least for the data sets studied here, that very
unsophisticated and very simple methods can generate good defect
detectors.

Many researchers have explored methods to reduce modeling
complexity. In the reliability engineering literature, principal
components analysis (PCA)~\cite{Dil84} has been widely applied to
resolve problems with structural code measurements;
e.g.~\cite{Muns90,Muns91}. PCA eliminates the problem of highly
correlated measures by identifying the distinct orthogonal sources
of variation and mapping the raw measurements onto a set of
uncorrelated features that represent essentially the same
information contained in the original measurements. For example,
the data shown in two dimensions of \fig{pca} (left-hand-side)
could be approximated in a single transformed dimension,
(right-hand-side).


\begin{figure}
\begin{center}
\includegraphics[rotate=90,width=3in]{pcaeg.pdf}
\end{center}
\caption{Transformation of axis.}\label{fig:pca}
\end{figure}


\newcommand{\setuptabs}{
\hspace*{.3in}\=\hspace*{.2in}\=\hspace*{.2in}\=\hspace*{.2in}\=\hspace*{.1in}
\hspace*{.2in}\=\hspace*{.2in}\=\hspace*{.2in}\=\hspace*{.2in}\=\hspace*{.2in}
\hspace*{.2in}\=\hspace*{.2in}\=\hspace*{.2in}\=\hspace*{.2in}\=\hspace*{.2in}\kill
}


PCA has its drawbacks. Fault models developed from PCA results  are
expressed in terms that are not directly visible to users of the
model.  Such models relate fault content or fault-proneness to the
``domain scores'' resulting from the PCA.
 These domain
scores are weighted sums of the structural measurements standardized
with respect to a chosen baseline. The structure of these models
may be very simple. For example, we have used PCA
and a decision tree learner to find the  following defect detector:

\begin{tabular}{p{3.5in}}
{\footnotesize {\sf
\begin{tabbing}
\setuptabs
\>if \>$domain_1 \le 0.180$\\
\>then NoDefects\\
\>else \>if $domain_1  >  0.180$\\
\> \>  then \>\> if $domain_1  \le 0.371$ then NoDefects\\
\> \>  else \>\> if $domain_1  >  0.371$ then Defects\\
\end{tabbing}}}
\end{tabular}

Here, ``$domain_1$'' is one of the domains found by PCA. This tree
seems very simple, yet is very hard to explain to business
clients users since ``$domain_1$'' is calculated using the  following, somewhat intimidating,
weighted sum:


{\scriptsize
\begin{eqnarray}\nonumber
domain_1&=& 0.241*loc  +0.236*v(g) \\\nonumber
      &&+0.222*ev(g)+0.236*iv(g)  +0.241*n  \\\nonumber
      &&+0.238*v -0.086*l +0.199*d   \\\nonumber
      && +0.216*i  +0.225*e  +0.236*b +0.221*t\\\nonumber
     && +0.241*lOCode  +0.179*lOComment\\\nonumber
     && +0.221*lOBlank +0.158*lOCodeAndComment \\\nonumber
     && +0.163*uniq_Op +0.234*uniq_Opnd\\\nonumber
     && +0.241*total_Op  +0.241*total_Opnd \\\nonumber
     && +0.236*branchCount\\\nonumber
\end{eqnarray}}

(Here,  $v(g), ev(g), iv(g)$ are the standard
McCabe structural metrics~\cite{mccabe76}
while the rest are either Halstead metrics~\cite{halstead77}
or simple variants on lines of code count. 
The appendix of this article contains a brief tutorial on these metrics.)

This problem with explaining domain scores
encouraged us to look for alternatives to PCA.
 Our reading of the data mining literature
 suggested that PCA belongs to a class of {\em feature
subset selection} (FSS) techniques which aim to remove superfluous
features~\cite{hall03,kohavi97,me03d}. The goal of FSS is to
drastically reduce the dimensionality of the data, thus
simplifying any subsequent processing. The dimensionality
reduction of FSS means that any subsequent processing can ignore
irrelevant, redundant and noisy features and focus on only
relevant, highly predictive ones to improve its performance.
Lastly, detectors learnt from reduced dimensionality are more
compact, easily understandable representations of the underlying
concept.

To the best of our knowledge, it has not been previously noted in the
reliability literature that PCA is one member of a large set of FSS
techniques. This study benchmarks PCA against those FSS techniques,
in terms of accuracy of the learnt defect detectors. We will show
that in the special case of generating defect detectors, very simple
FSS methods can out-perform PCA both in terms of the number of
features rejected and the accuracy of the detectors learnt from the
remaining features.

\begin{figure}[!t]
\begin{center}
\includegraphics[width=3in]{bigtreejm1.pdf}
\end{center}
\caption{A large decision tree produced by the C4.5 decision
learner~\protect\cite{quinlan92} using all 22 metrics in the JM1
data set analyzed in this article.}\label{fig:bigtree}
\end{figure}

\begin{figure}[!t]
\begin{center}
\includegraphics[width=3in]{smalltreejm1.pdf}
\end{center}
\caption{Small decision tree produced by C4.5 from the JM1 data
set using just the three metrics selected by the SELECT FSS
method (described later in this paper).}\label{fig:smalltree}
\end{figure}

Unlike other studies (e.g.~\cite{Muns98}), which contained a mere
fifty observations, the experimental data used for this paper is
large (hundreds to thousands of records)
 and is drawn from  five different
software projects shown in \fig{datasets}.
Apart from being written in ``C'' or ``C++'',
there is little commonality in our sample.
These projects come from five different teams working at
four different locations around the country. 
This software performs a wide range of different functions
from spacecaft instrumentation to real-time predictive simulations.
That is our conclusions are based
on a broader experience base than previous work:
specifically,
15,730 modules for which there exist
3975 defect reports. 

\begin{figure}
{\footnotesize
\begin{center} {\small
\begin{tabular}{c@{~}|@{~}c@{~}|c@{~}|c@{~}|@{~}c|@{~}p{1.5in}}
 & \# & \% with&&developed&notes\\
project &modules&defects&language&at&notes\\\hline
AN1 &1719  & 58\%&C++&location 1&development project for reusable code libraries\\\hline
CM1 &496& 9.7\%&C&location 2&a NASA spacecraft instrument\\\hline
JM1 & 10885& 19\%&C&location 3&real-time predictive ground system 
(uses simulations to generate the  predictions)\\\hline
KC1 &2107&15.4\%&C++&location 4&storage management for receiving and processing ground data\\\hline
KC2 & 523  & 20\%&C++&location 4&science data processing;
another part of the same project as KC1;
different personnel to KC1. shared some third-party software libraries
as KC1, but no other software overlap. \\
\end{tabular}
}\end{center}}
\caption{Data sets used in this study. Here, a
``module''  is the equivalent of a C function
or a C++ method.
All
modules analyzed were built by NASA developers excluding several
thousands modules that are COTS software (COTS is an acronym for
Commercial Off The Shelf). The McCabe and Halstead
structural metrics were extracted from these systems and mapped
to the  defect logs  kept for
each project.
Note that AN1 is an artificially generated data set. That system
has not finished its testing phase so its defect logs are
incomplete. For this data set, we hence used all the log entries
relating to defects and a nearly equal number of entries with no
defects (selected at random).}\label{fig:datasets}
\end{figure}


Another important feature of this study is that it is a {\em
repeatable} experiment. Four of the five data sets used here
publicly available\footnote{\url{http://mdp.ivv.nasa.gov}, or
\url{http://menzies.us/data.html}}.
 These experiments also use freely
distributed tools available online, such as the WEKA machine
learning toolkit
\footnote{\url{http://www.cs.waikato.ac.nz/~ml/weka/}} and the
TAR2 treatment
learner~\cite{me01f,me01h,me02a}\footnote{\url{http://menzies.us/rx.html}}.
Repeatability is an important methodologically principle since it
allows other researchers to independently assess  our results.

The most important feature of our study was the dramatic reduction
in number of features. In all the case studies shown below,
over 75\% of the available features could be ignored, without
compromising the detector accuracy.
For example our case studies show that the  complex defect
detector decision tree of \fig{bigtree} can be reduce to simpler
tree of \fig{smalltree}, with little or no loss in defect
detection accuracy. Interestingly, these reductions are obtained
using  methods much simpler than anything used before in the
software reliability literature. This result has made us
reevaluate our own previous results~\cite{Muns98,me02e} that used
PCA and other techniques to simplify fault detectors.

This is not to say that the prior research on PCA was useless. On
the contrary, claims that method {\em X} is simpler, but just as
effective, as method {\em Y} is meaningless without knowledge of
method {\em Y}. The only way this paper can claim that
something is a better FSS than (e.g.) PCA is to have access to the prior
results on PCA. Hence, we say that prior research on PCA was an
essential precursor to this work.



\section{Related Results}

The thesis of this paper is that {\em many features are
ignorable}. That is, most of the available metrics can be omitted
from defect detectors without affecting the accuracy of those
detectors. There is some evidence for this thesis, scattered
throughout the literature. This section reviews that evidence.

A defect detector in this domain is a test that some
measured software structural feature has passed some threshold.
Different metric ranges may also be combined to form a composite
defect detector in order to compose trees or other classifier
structures.

Decision tree learning has been frequently applied to the task of
generating summaries of defect logs. Often, these summaries use
only a small subset of the available features. For example,
\fig{taghi} shows one study where,  of the 42 features offered in
the data set, only six were deemed significant by the learner.

\begin{figure}[!ht]
\begin{center}
\includegraphics[width=4.5in]{taghi.pdf}
\end{center}
\caption{Predicting fault-prone
modules~\protect\cite{khoshgoftaar99}. Learned from data collected
from a telecommunications system with $> 10$ million lines of code
containing a few thousand modules.  }\label{fig:taghi}
\end{figure}

For another example, \fig{some} shows 18 metrics given to  a
particular learner. \fig{tian} shows what that learner
generated. The key feature of \fig{tian} is what is {\em not
shown} in the learnt decision tree: of the 18 features available
to this learner, only the four underlined metrics appear in the
tree.

For yet another example,  we can look at the individual domains
learnt by PCAs for a mission software technology development
effort at JPL~\cite{Dvo99}. \fig{allen} shows that, with respect
to the index of cumulative faults, not all features are equally
associated with faults. \fig{allen} plots the cumulative domain
values for each of the system builds, together with the cumulative
number of faults for each build.  It is quite apparent from this
figure that Domain 1, associated with control, is most closely
associated with the cumulative fault count. Indeed, the
correlation coefficient between Domain 1 normalized cumulative
domain values and the cumulative fault values is 0.94. The
correlation between Domain 2 and cumulative faults is -0.20.
Finally, correlation between Domain 3 and cumulative faults is
0.71.

\begin{figure}[!t]
\begin{center}
\includegraphics[width=4.5in]{tian.pdf}
\end{center}
\caption{Predicting modules with  high cost modules and many
faults. Data from 16 NASA ground support software for unmanned
spacecraft control~\protect\cite{tiang95}. These systems were of
size 3,000 to 112,000 lines of FORTRAN and contained 4,700
modules. }\label{fig:tian}
\end{figure}



\begin{figure}
\begin{footnotesize}
\begin{center}
\begin{tabular}{p{1.3in}cp{1.3in}}
{\em Across whole module:}\newline total operators\newline total
operators\newline ~\newline {\em Averages per KSLOC:}\newline
assignment statements\newline \underline{cyclomatic
complexity}\newline executable statements\newline decision
statements\newline function calls (FC)\newline \underline{module
calls (MC)} && {\em Averages per KSLOC:}\newline \underline{FC plus
MC}\newline IO statements\newline IO parameters\newline
origin\newline operands\newline \underline{operators}\newline
comments (C)\newline source lines (SL)\newline SL minus C\newline
format statements\newline
\end{tabular}
\end{center}
\end{footnotesize}
\caption{Metrics available to the learner that generated~\fig{tian}.
``Cyclomatic complexity'' is a measure of internal program
intricacy~\protect\cite{mccabe76}.}\label{fig:some}
\end{figure}


\begin{figure}[!t]
\begin{center}
\includegraphics[width=3.5in]{allen.pdf}
\end{center}
\caption{Three domain scores and a cumulative total for one JPL
system.}\label{fig:allen}
\end{figure}


The above examples can only be found after reading widely  in the
literature. The rest of this article checks if the phenomenon that
{\em many features are ignorable} is easily repeatable. A range of
data sets will be explored using a range of {\em feature subset
selection} (FSS) techniques. With the exception of PCA, most of
these FSS techniques come from the data mining literature. Hence,
before we explain FSS, we must offer some background notes on data
mining.

\section{ Data Mining}\label{sec:ml}
Data mining is a summarization technique that reduces large sets
of examples to a small understandable pattern using a range of
techniques taken from statistics and artificial intelligence. It
is commonly referred to as searching for pearls in the sand. This
next section is a review of data mining methods and algorithms
used in this study. The subsequent section describes feature subset
selection.

\subsection{Methods and Algorithms}

{\bf Cross Validation:}\label{CrossVal} A common mistake that new
data miners make is \emph{over-training}. Over-training happens
when a data miner to get \emph{too} specific in its learning. If
that happens then
 your results, while
extremely applicable to current data, are unlikely to apply to
data seen in the future.

One way of avoiding this pitfall is by assessing the learnt
treatments against data not used during training.  One method for
doing so is N-way cross validation. In this process, a training
set is divided into $N$ buckets. For each bucket in turn, a select
is learned on the other $N-1$ buckets, then tested on the bucket
that was put aside. A learner is deemed {\em stable} if it works
in the majority of all $N$ turns.

{\bf Decision Tree Learning:} \fig{bigtree}, \fig{smalltree},
\fig{taghi} and \fig{tian} were generated via decision tree
learners. One way to learn such trees is to {\em split} the whole
example set into subsets based on some metric/threshold
comparison. The process then repeats recursively on the subsets.
Each splitter value becomes the root of a sub-tree. Splitting
stops when either  a subset gets so small that further splitting
is superfluous, or a subset is contains examples with only one
type (e.g. all the remaining examples are about defective
modules).

A {\em good split} decreases the percentage of different
types of modules in a subset. Such a good split ensures that
smaller subtrees will be generated since less further splitting is
required to sort out the subsets. Various schemes have been
described in the literature for finding good splits. For example,
the C4.5~\cite{quinlan92} and J4.8~\cite{witten99} decision tree
algorithms uses an information theoretic measure (entropy) to find
its splits while the CART~\cite{breiman84} decision tree learner
uses another measure called the GINA index.


{\bf Bayesian Learning:} An alternative to decision tree learning is
   Naive Bayesian   learning~\cite{witten99}. In this approach,
   a
  prior probability of an hypothesis $H$ is updated
   whenever new evidence $E$
comes to
  hand. Baye's rule tells us how:
\[P(H| E)=\frac{P(E |H) P(H)}{P(E)}\]
Such learners are ``naive'' in that they assume no correlation
between attributes. However, this seemingly ``naive'' assumption
has proven to be remarkably robust and useful in many domains.

For example of Bayesian learning,
consider the log of golf-playing behavior shown
in \fig{golfdata}.
In that log, the
 frequency of playing
some, or lots of golf
  is $P(none)=\frac{5}{14}$,
  $P(some)=\frac{3}{14}$ and
$P(lots)=\frac{6}{14}$ respectively.
  In the special case where it is not windy
   (i.e. $E=not windy$) then the
  probabilities change to
$P(not\;windy|none)$= $\frac{2}{8}$,
  $P(not\;windy|some)$= $\frac{3}{8}$,
  $P(not\;windy|lots)$= $\frac{3}{8}$.
If we have evidence that today is not windy,
we can update our
prior beliefs about golf-playing behavior.
First, we compute the
likelihoods
that we will play none,some, or lots
of golf:
\begin{eqnarray}\nonumber
likelihood(none|not\;windy)=
\frac{2}{5}*\frac{5}{14}=0.143\\\nonumber
likelihood(some|not\;
windy)=\frac{3}{3}*\frac{3}{14}=0.214\\
\nonumber
likelihood(lots|not\;
windy)=\frac{3}{6}*\frac{6}{14}=0.214\\
\nonumber
\end{eqnarray}
These likelihoods are then
 normalized in the standard way to get
probabilities:
\begin{eqnarray}\nonumber
P(none|not\;windy)=
\frac{0.143}{0.143+0.214+0.214}=0.250\\
\nonumber
P(some|not\;
windy)=\frac{0.214}{0.143+0.214+0.214}=
0.375\\\nonumber
P(lots|not\;
windy)=\frac{0.214}{0.143+0.214+0.214}=
0.375\\\nonumber
\end{eqnarray}
That is, on non-windy days, it is least
 probable that we will play
no golf.



\begin{figure}[!t]
{\footnotesize
 {\em
\begin{center}
\begin{tabular}{rcccl}
outlook & temp($^o$F) &  humidity & windy? & class
\\\hline
sunny&  85&     86&     false&  none\\
sunny&     80&     90&     true&   none\\
sunny&     72&     95&     false&  none\\
rain&  65&     70&     true&         none\\
rain&        71&     96&     true&   none\\\hline
      rain&         70&     96&     false&      some\\
      rain&      68&     80&     false&      some\\
      rain&      75&     80&     false&  some\\\hline
      sunny&    69&     70&     false&  lots \\
      sunny&    75&     70&     true&   lots\\
      overcast&  83&     88&     false&  lots\\
      overcast&  64&     65&     true&   lots\\
      overcast&  72&     90&     true&   lots\\
     overcast&  81&     75&     false&  lots\\\hline
\end{tabular}\end{center}}}

{\footnotesize
\begin{minipage}{.45\linewidth}
\begin{verbatim}
SELECT class FROM original
WHERE outlook = 'overcast'

lots
lots
lots
lots

\end{verbatim}
\end{minipage}\hfill
\begin{minipage}{.45\linewidth}\begin{verbatim}
SELECT class FROM original
WHERE humidity >= 90

none
none
none
some
lots
\end{verbatim}
\end{minipage}
} \caption{Attributes that select for golf playing behavior.}
\label{fig:golfdata}
\end{figure}

{\bf Treatment Learning:} A new data mining technique is the TAR2
treatment learning technique developed by Menzies and
Yu~\cite{ying02,me02a,me02f,me02c,me02a,me01f,me01h}. Treatment
learning searches for a strong {\em select statement} that most
{\em changes} the ratio of classes. To understand the concept of a
{\em strong select statement}, consider the log of golf playing
behavior seen in \fig{golfdata}. In that log, we only play {\em
lots} of golf in $\frac{6}{5+3+6}= 43\%$ of the cases. To improve
our game, we might search for conditions that increases our
golfing frequency. Two such searches are shown in the bottom of
\fig{golfdata}. In the case of {\tt outlook=overcast}, we play
{\em lots} of golf all the time. In the case of {\tt humidity
$\ge$ 90}, we only play {\em lots} of golf in 20\% of the cases.
The net effect of these two select statements is shown in
\fig{golft}.

\begin{figure}
\begin{center}
{\small
\begin{tabular}{p{0.7in}p{1.1in}p{1in}}
$baseline$  & $outlook =overcast$
&$humidity \ge 90$\\\\
\begin{barenv}
\setstyle{\sffamily} \setwidth{8}
     \setstretch{5}
  \setyaxis{0}{6}{2}
\sethspace{1} \setnumberpos{down} \bar{5}{1}
 \bar{3}{4}
 \bar{6}{8}
\end{barenv}&
\begin{barenv}
\setstyle{\sffamily} \setwidth{8}
 \setstretch{5}
  \setyaxis{0}{6}{2}
\sethspace{1} \setnumberpos{down} \bar{0}{1} \bar{0}{4} \bar{4}{8}
\end{barenv}&
\begin{barenv}
\setstyle{\sffamily} \setwidth{8}
 \setstretch{5}
  \setyaxis{0}{6}{2}
\sethspace{1} \setnumberpos{down} \bar{3}{1} \bar{1}{4} \bar{1}{8}
\end{barenv}\\\\~\\
\multicolumn{3}{c}{LEGEND: \protect\legend1{none}
\protect\legend4{some} \protect\legend8{lots}}
\end{tabular}}\end{center}
 \caption{Changes to golf playing behavior from the baseline.  }
\label{fig:golft}
\end{figure}

The {\tt WHERE} statements within a select statement can contain
conjunctions of arbitrary size. Exploring all such conjunctions
manually is a tedious task. TAR2 is an automatic tool for finding
the strongest select statements;
i.e., the statement that \emph{most} selects for preferred
behavior while \emph{most} discouraging undesirable behavior.
TAR2 calls this strongest select statement the ``treatment'' since
it is a recommended action for improving the current situation.
The algorithm is automatic and, as used in this study, searched
the entire range of possible conditions. TAR2's configuration file
lets an analyst search for the best select statement using
conjunctions of size 1,2,3,4, etc. Since TAR2's search is
elaborate, an analyst can automatically find the {\em best} and
{\em worst} possible situation within a data set. For example, the
select statements seen in \fig{golft} were learnt by TAR2 and show
the {\em best} and \emph{worst} possible situation for playing
{\em lots} of golf.

{\bf 1R:}
Simpler than any of the above techniques
is the 1R machine learner~\cite{holte93}. It creates a set of rules
from a single attribute. First 1R selects an attribute then
branches within the attribute to create a set of divisions based
on class value. For each division it assigns the most frequent
class and then computes the error rate. Finally, 1R simply
chooses the attribute with the total least error
rate.

{\bf ROCKY:}\label{rocky}
Simpler even than
1R is ROCKY~\cite{me03a}. Given a set of numeric metrics
\[attribute_1, attribute_2,... attribute_n
\]
ROCKY exhaustively explores all singleton rules of the form
\[attribute \ge threshold
\]
{\em Threshold}  is found  as
follows. Every numeric attribute is assumed to come from a
gaussian distribution. $Threshold$s are then selected
corresponding to equal areas under that distribution. For example,
in one of the data sets we examine, the McCabe
cyclomatic complexity $v(g)$ had a mean of $\mu=4.9$
and a standard deviation of $\sigma=11$. If this Gaussian is
converted to a unit Gaussian (by subtracting the mean and dividing
by the standard deviation), then standard Z-tables could be used
to calculate
 a $v(g)$ $threshold$ value of 7.65 could be found
 as follows:

{\small
\begin{eqnarray}\nonumber
area&=&0.6\mbox{~(just for example)}\\\nonumber
Z^{-1}(area)&=&\frac{v(g) - \mu}{\sigma} \\\nonumber
Z^{-1}(area)&\approx&0.25\\\nonumber \therefore
v(g).threshold(area)&\approx&7.65\end{eqnarray}}

{\em ROCKY} generates one  detector
\[
attribute_i \ge attribute_i[threshold(area)]
\]
for the range
 {\small
 \[\begin{array}{rl}
 area \in & \{0.05,0.1,0.15,\ldots
 0.9,0.95\}
 \end{array}\]}

A key point that will be important below
is that ROCKY and 1R can only ever find detectors
based on a single attribute.

\subsection{Feature Subset Selection}\label{FSS}

Feature subset selection finds what subset of the available
features is most informative. PCA is the FSS method best known to
the reliability engineering community. However, as we shall see,
numerous other FSS methods have been evolved in the data mining
community.

A repeated empirical observation is that ignoring features can
improve classifier accuracy. How can ignoring information be useful?
Kohavi \& John~\cite{kohavi97} review studies with Naive Bayes
classifiers. The accuracy of such classifiers decreases very slowly
as irrelevant features are added to an instance set. However, the
accuracy of the same classifiers can degrade sharply as the number of
correlated features increase. Note that this observation is similar
to the original motivations for using  PCA: i.e.  learning is simpler
when highly correlated features don't conflate the learning process.

Another explanation for the success of FSS is offered by Witten \&
Frank~\cite{witten99}. They note that effective generalization
requires numerous examples. Decision tree learners recursively split
instances by ranking features according to how much they decrease
the diversity of the classes in the split sets. As learning
progresses, fewer and fewer instances are available to learn the next
sub-tree. If the instances contain too many features of similar rank,
then many splits are quickly generated. Hence, instances become
sparser in the sub-trees, and effective generalization becomes
harder.

Yet another explanation for the success of FSS comes from Gunnalan,
Menzies, {\em et.al.}~\cite{me03d} who argue that solvable problems
have an average case property called {\em small backbones}. Small
backbone problems contain a small number of variables that control
all other variables in the system. Learning the essential features of
small backbone problems means finding the variables that are either
in the small backbone or   highly correlated to the backbone
variables.

{\bf PCA: Principal Component Analysis:} PCA first began to be used in modeling software reliability
    and fault content in the late 1980s and early 1990s,
    when Munson and Khoshgoftaar first developed the
    concept of relative complexity~\cite{Muns90,Muns91}, which is described
    as a weighted sum of the domain scores resulting from the application
     of PCA to raw structural measurements.  Unlike other complexity
     metrics, relative complexity simultaneously combines all
     feature dimensions of all structural measures.  In an early paper,
     they identified clear relationships between complexity
     metric domains and software quality~\cite{Muns90}.  In a
     later paper, they examined relationships between
      the relative complexity and software reliability~\cite{Muns91}.
      This study concluded that:

\bi

\item   The relative complexity measure is appropriate for
 the comparison and classification of software modules, and

\item   It is feasible to include relative complexity as a
 parameter in software reliability models.

\ei



In particular, they noted that relative complexity could be used to represent
the complexity of a particular software module for a particular build,
which laid the foundation for measuring the evolution of software system.



    In 1996, Munson and Werries presented a methodology for measuring
    software evolution that extended the notion of software
    complexity across sequential builds~\cite{Muns96}.  In this paper,
     they addressed the issue of establishing a baseline against
     which all change to a software system will be measured.
     To properly account for the amount of change that occurs
     between subsequent builds of a system, it is necessary to
     measure each build with respect to a baseline that remains
      constant across all builds.  This is accomplished by choosing
      one particular build as the baseline, and then standardizing
      the measurements from all other builds with respect to the means
       and standard deviations of the baseline measurements.  They also
        developed a mechanism wherein the precise manner in which builds
        differ from each other may be measured.  This is accomplished
         by computing the difference in relative complexity between
          subsequent versions of a module within the system.  The
           measurement mechanism also takes into account the
           situation in which a module is present in one of
           the builds but not the other.

    Recent investigations have focused on identifying
    relationships between the measured structural evolution of a
    software system and the rate at which faults are inserted into
     it during development (i.e., the number of faults inserted per
      unit of structural change).  In a small study~\cite{Muns98}, Nikora and
       Munson analyzed the flight software and software failure
       reports for the command and data handling subsystem of a
       NASA planetary exploration spacecraft, and found strong
       indications that measurements of a system's structural
       evolution could serve as predictors of the fault
       insertion rate.  However, this study had two limitations:
       The study was relatively small - fewer than 50 observations
        were used in the regression analysis relating the number
        of faults inserted to the amount of structural change.
         The definition of faults that was used was not quantitative.
          The ad-hoc taxonomy, first described in~\cite{Niko97}, was an
          attempt to provide an unambiguous set of rules for
          identifying and counting faults.  The rules
          were based on the types of changes made to source
          code in response to failures reported in the system.
            Although the rules provided a way of classifying
            the faults by type, and attempted to address faults
            at the level of individual modules, they were not
            sufficient to enable repeatable and consistent fault
             counts by different observers to be made.  The rules
             in and of themselves were unreliable.  To overcome these
             limitations, the investigators developed a quantitative
             definition of software faults, based on the grammar of
              the language of the software system~\cite{Muns02}.
               They also initiated a collaboration with the
               Mission Data System, a mission software technology
               development effort at the Jet Propulsion Laboratory~\cite{Dvo99}.
                They were able to collect significantly more information
                 than for the previous study; over the time interval
                  during which they study was conducted, there were
                   over 1500 builds of the MDS.  The total
                    number of distinct versions of all modules was
                    greater than 65,000, and over 1400 problem reports
                    were included in the analysis.  This study agreed
                    with the earlier study's conclusions that there
                    appear to be strong relationships between
                     measurements of a software system's
                     structural evolution and the number of
                     faults inserted into that system, and
                     extended the earlier work by identifying types
                      of structural change more likely to result in
                       the introduction of faults and types less
                       likely to do so.




{\bf WRP: Wrapper Subset Evaluation:}
\begin{figure}
\begin{center}
{\small \begin{tabular}{r@{~}c@{~}c@{~}c@{~}c@{~}c@{~}c@{~}c@{~}c@{~}c@{~}c@{~}c}\\
&\multicolumn{11}{c}{number of attributes}\\\cline{2-12}
before:& 10&13&15&180&22&8&25&36&6&6&6\\
 after:& 2&2&2&11&2&1&3&12&1&1&2\\
reduction:& 80\%& 84\%& 87\%&94\%&90\%& 87\%&
88\%&67\%&
83\%&83\%&67\%\\\hline
$\Delta$accuracy: & 0\%&6\%&5\%&4\%&2\%&1\%&0.5\%&0\%&-25\%  &6\%
&7\%
\end{tabular}}
\end{center}
\caption{Feature subset selection using a WRAPPER of a decision
tree leaner. The $\Delta$Accuracy
figure is the difference in the accuracies of the theories
found by decision tree learner using
 the $before$ and $after$ attributes.
From \protect\cite{kohavi97}.}\label{fig:reduce}
\end{figure}PCA is a common FSS method used by statisticians.
WRAPPER is a common FSS method used by data miners.
In this method, a {\em target learner} is augmented
with a pre-processor that used a
heuristic search to grow subsets of the available features.
At each step in the growth, the target learner is called
to find the accuracy of the model learned from the current subset.
Subset growth is stopped when the addition of new features did
not improve the accuracy.

\fig{reduce} shows some WRAPPER results from  experiments
by Kohavi and John~\cite{Kol97}.
In their experiments, 83\% (on average)
of the measures in a domain could be ignored with only a minimal
loss of accuracy.

The advantage of the this approach is that,
if some target learner is already implemented, then the WRAPPER
is simple to implement. The disadvantage of the wrapper method is
that each step in the heuristic search requires another call to
the target learner; i.e. it may be very slow.

For the results shown below, we will use a WRAPPER of two
target learners: a decision tree learner (C4.5) and a Naive Bayes
classifier.

{\bf IG: Information Gain Attribute Ranking:} This is a simple and
fast method for feature ranking~\cite{Dum98}. This method measures
the split criteria of the class before and after observing a
feature. The differences in the split criteria gives a measure of
the information gained because of that attribute~\cite{quinlan92}.
A final comparison of this measure is used in feature selection.

{\bf RLF: Relief:} Relief is an instance based learning
scheme~\cite{Kir92,Kon94}. It works by randomly sampling one
instance within the data. It then locates the nearest neighbors
for that instance from not only the same class but the opposite
class as well. The values of the nearest neighbor features are
then compared to that of the sampled instance and the feature
scores are maintained and updated based on this. This process is
specified for some user-specified M number of instances. Relief
can handle noisy data and other data anomalies by averaging the
values for K nearest neighbors of the same and opposite class for
each instance~\cite{Kon94}. For data sets with multiple classes,
the nearest neighbors for each class that is different from the
current sampled instance are selected and the contributions are
determined by using the class probabilities of the class in the
dataset.

{\bf CFS:Correlation-based Feature Selection:} CFS uses subsets of
features~\cite{Hall98}. This technique relies on a heuristic merit
calculation that assigns high scores to subsets with features that
are highly correlated with the class and poorly correlated with
each other. Merit can find the redundant features since they will
be highly correlated with the other features. It can also identify
ignorable features since they will be poor predictors of any
class. To do this CFS informs a heuristic search for key features
via a correlation matrix.

{\bf CBS: Consistency-based Subset Evaluation:} CBS is really a
set of methods that use class consistency as an evaluation metric.
The specific CBS studied by Hall and Holmes method finds the
subset of features whose values divide the data into subsets with
high class consistency~\cite{Alm91}.


\begin{figure}[!t]
\begin{center}
\includegraphics[width=3.5in]{tar2less-v2.pdf}
\end{center}
\caption{SELECT algorithm.} \label{fig:tar2lessf}
\end{figure}
{\bf SELECT:}
\fig{tar2lessf} shows the SELECT FSS developed by
Gunnalan, Menzies, {\em et.al.}~\cite{me03d}.
SELECT runs TAR2 many times, each time targeting
a different class;
e.g. defects, no defects:


{
\begin{enumerate}
\item
Initialize the SELECTED features to nil.
\item
For each class in turn, declare it to be TAR2's "best" class. Then enter the following loop:
\begin{smallitem}
\item
Set treatment size N to 1
\item    Find the "best" treatment of size N via TAR2.
\item  If the score of the best treatment is no better than that of the best treatment of size N-1, then…
\begin{smallitem}
\item
Add the features seen in the best treatment to SELECTED.
\end{smallitem}
\item
   Else, N++ and loop.
\end{smallitem}
\item
  Collect the average accuracy seen in a  10-way cross validation of the target learner using
\begin{smallitem}
\item
  just the features seen in SELECTED
\item   all features
\end{smallitem}
\end{enumerate}}

Note that each single run of TAR2
finds features that  most selected for one class. Over all the
runs, TAR2less finds the union of all the features that most
selected for every class.

{\bf 1R and ROCKY:} Most FSS methods input $M$ features and output
some subset $N, N<M$. An extreme form of feature subset selection
is to use learners that can only output theories containing $N=1$
features. Two such learners are the 1R and ROCKY systems described
above.

Note that this method is far less general than the other
methods described above since it will fail if
 $N>1$ features must be selected.






\section{Experiments}\label{projects}

The remainder of this paper is dedicated to a case study on the
AN1, CM1, KC1, KC2, JM1 datasets
described in \fig{datasets}.

{\bf Methods:}
FSS was conducted using the PCA, CBS, IG,
RLF, WRAPPER, and 1R implementations supplied
with the WEKA machine learning
toolkit\footnote{\url{http://www.cs.waikato.ac.nz/~ml/weka/}}.
We used our own implementations of ROCKY and TAR2\footnote{
Available from  \url{http://menzies.us/rx.html}
and \url{http://menzies.us/pace.html}}.
SELECT was applied
manually using TAR2.

Each FSS method {\em generated} candidate features
which were then {\em selected} and
{\em assessed}.
Usually, the selected features were {\em assessed}
by running them
through a 10-way cross validation over the
C4.5 and   Naive Bayes classifiers supplied within the WEKA.
Assessing FSS via these two learners is quite standard in the FSS literature (e.g.~\cite{kohavi97})
since these are widely used and understood learning systems. Also,
these two classifiers are  very different kinds of learners so results
that repeat in both C4.5 and Naive Bayes are guaranteed not to be the result of
quirks in (e.g.) decision tree learning.

Sometimes, however, other methods were required to assess the
selected features. For example,   if we were ``wrapping'' learner
``X'' then we assessed the WRAPPER's output only on learner ''X''.
Also, in the case of ROCKY and 1R, those learners have their own
cross-val facilities to assess the accuracies of their learnt
theories.

The {\em generation} methods varied. In the usual case, the WEKA
environment offered options to conduct FSS via a 10-way cross validation.
We disabled this option for WRAPPER since that was impractically slow,
especially for the 10,000 records in JM1. 10-way cross validation was also
used within SELECT when finding the best treatment of size N.




\begin{figure}
{\scriptsize
\begin{center}
\begin{tabular}{rcccccl}

           Learner& Attributes&  CM1   &KC1     &KC2& JM1& AN1\\\hline
Original (C4.5)    &  21      &89.52\%   &83.77\%   &82.11\% &79.34\%&65.90\%\\
Original (Bayes)   &  21      &84.88\%   &82.34\%   &83.65\% &80.41\%&58.27\%\\
1R                 &  1       &89.30\%    &83.10\%    &82.95\%&  79.55\%&   65.02\%\\
ROCKY              &  1       &\underline{90.50\%}    &\underline{85.63}   &\underline{\em {85.28\%}}& \underline{\em{81.10\%}}&\underline{\em {66.14\%}}\\

\end{tabular}
\end{center}}

\caption{1R and ROCKY runs. Baseline accuracies generated from all
features via C4.5 and Naive Bayes shown on lines one and two. \underline{
Underlined entries} denotes an increase over all baselines.}
\label{fig:onerroc}
\end{figure}

\begin{figure}[!t]
{\scriptsize
\begin{center}
\begin{tabular}{rccccl}
   &           &  \multicolumn{2}{c}{C4.5}&&  Naive Bayes\\\cline{3-4}\cline{6-6}
   & Attributes&  accuracy&   tree Size&&  accuracy\\\hline
Original&     15&  65.90\%&  131&& 58.27\%\\
SELECT&    4&   {\em {66.82\%}}& 119&& {\em {58.61\%}}\\
CFS&         5&   65.02\%&  17&&  {\em {60.42\%}}\\
CBS&         9&   {\em {66.07\%}}&  81&&  57.57\%\\
IG&          4&   64.55\%&  3&&  {\em {60.65\%}}\\
RLF&         4&  \underline{\em {67.11\%}}&  41&&  {\em {60.77\%}}\\
PCA&         7&        65.77\%& 13&& {\em 61.87\%}\\
Wrapper&     5 (c4.5)& {\em {66.88\%}}&  37&& \\
 &          2 (bayes)&  &   &&  \underline{\em {62.51\%}}\\\hline
& mean &{\em {66.02\%}} &mean&&{\em {60.08\%}}
\end{tabular}
\end{center}}

\caption{AN1 FSS and learner accuracy runs. Baseline accuracies
shown on line one. \underline{Underlined} entries mark the largest
accuracy generated by any method. \em {Italicized} entries mark an
increase over the baseline. WRAPPER's selected features were only
assessed on the ``wrapped'' learner- either C4.5 or Naive Bayes
(hence the blank cells on the WRAPPER line).} \label{fig:an1runs}
\end{figure}

\begin{figure}
{\scriptsize
\begin{center}
\begin{tabular}{rccccl}
   &           &  \multicolumn{2}{c}{C4.5}&&  Naive Bayes\\\cline{3-4}\cline{6-6}
           & Attributes&  accuracy       &   tree Size&&   accuracy          \\\hline
Original    & 24        &  89.52\%        &        33&&   84.88\%           \\
SELECT   &    6      &  \underline{{\em 90.32\%}}       &  1  &&   {\em 86.49\%}           \\
CFS        & 6         &  89.2\%        &  1 &&   {\em 86.90\%}       \\
CBS        & 1        &  {\em 89.92\%}        &  1     &&   \underline{{\em 89.11\%}}        \\
IG         &  4        &  {\em 90.12\%} & 1&& {\em 87.90\%}       \\
RLF        & 4         &  89.52\%        &  1    && 83.48\%        \\
PCA        & 7        &   89.52\%        &  13         && {\em 86.29\%}        \\
Wrapper    & 0 (C4.5)  &  N/A        &  1         &&                    \\
           & 0 (bayes) &                 &             && N/A      \\\hline
           & mean      &  {\em 89.84\%}  &  mean       && {\em 86.43\%}

\end{tabular}
\end{center}}

\caption{CM1 FSS and learner accuracy runs. Baseline accuracies
shown on line one. {\em Italicized} and blank entries have the
same meaning as in \fig{an1runs}.
N/A denotes runs were the feature subset selector returned
no attributes} \label{fig:cm1runs}
\end{figure}


\begin{figure}[!t]
{\scriptsize
\begin{center}
\begin{tabular}{rccccl}
   &           &  \multicolumn{2}{c}{C4.5}&&  Naive Bayes\\\cline{3-4}\cline{6-6}
   & Attributes&  accuracy&   tree Size&&  accuracy\\\hline
Original& 21&  79.34\%&  677&& 80.41\%\\
SELECT&    4&   {\em {81.06\%}}&  11&&  \underline{\em{80.70\%}}\\
CFS& 7&   {\em {80.51\%}}&  63&&  {\em {80.46\%}}\\
CBS& 19&  {\em {79.48\%}}&  671&& 80.25\%\\
IG&  4&   {\em {81.25\%}}&  15&&  {\em {80.43\%}}\\
RLF& 4&   {\em {80.98\%}}&  25&&  79.62\%\\
PCA& 8&   {\em {80.09\%}}&  17&&  79.67\%\\
Wrapper& 5 (C4.5)& \underline{\em {85.57\%}}&  15&&  \\
 & 2 (bayes)&  &   &&  {\em {80.90\%}}\\\hline
& mean &{\em {81.04\%}} & mean&& 80.31\%

\end{tabular}
\end{center}}

\caption{JM1 FSS and learner accuracy runs. Baseline accuracies
shown on line one. {\em Italicized} and blank entries have the
same meaning as in \fig{an1runs}. } \label{fig:jm1runs}
\end{figure}


\begin{figure}
{\scriptsize
\begin{center}
\begin{tabular}{rccccl}
   &           &  \multicolumn{2}{c}{C4.5}&&  Naive Bayes\\\cline{3-4}\cline{6-6}
           & Attributes&  accuracy       &   tree Size&&   accuracy          \\\hline
Original    & 21        &  83.79\%        &        163&&   82.34\%           \\
SELECT   &    3      &  {\em 85.00}\%        &  5  &&   {\em 83.82\%}           \\
CFS        & 7         &  {\em 84.24}\%        &  99 &&   {\em 82.91\%}       \\
CBS        & 18        &  83.29\%        &  135      &&   82.34\%        \\
IG         &  4        &  \underline{{\em 85.38}}\% & 5&& {\em 84.20\%}       \\
RLF        & 4         &  {\em 85.19}\%        &  9    && 80.83\%        \\
PCA        & 6        &   82.05\%        &  21         && {\em 83.00\%}        \\
Wrapper    & 5 (C4.5)  &  {\em 85.29\%}        &  13         &&                    \\
           & 1 (bayes) &                 &             && \underline{{\em 85.52}}\%       \\\hline
           & mean      &  {\em 84.65\%}  &  mean       && {\em 83.12\%}

\end{tabular}
\end{center}}

\caption{KC1 FSS and learner accuracy runs. Baseline accuracies
shown on line one. {\em Italicized} and blank entries have the
same meaning as in \fig{an1runs}.} \label{fig:kc1runs}
\end{figure}

\begin{figure}
{\scriptsize
\begin{center}
\begin{tabular}{rccccl}
   &           &  \multicolumn{2}{c}{C4.5}&&  Naive Bayes\\\cline{3-4}\cline{6-6}
   & Attributes&  accuracy&   tree Size&&  accuracy\\\hline
Original& 21&  82.11\%&  51&&  83.65\%\\
SELECT&    2&   {\em {82.89\%}}&  5&&   83.08\%\\
CFS& 2&   \underline{\em {85.25\%}}&  9&&   {\em {84.10\%}}\\
CBS& 6&   {\em {83.33\%}}&  23&&  {\em {83.72\%}}\\
IG&  4&   {\em {84.29\%}}&  3&&   {\em {84.10\%}}\\
RLF& 4&   81.61\%&  5&&   82.18\%\\
PCA& 2&   {\em {82.57\%}}&  5&&   {\em {84.87\%}}\\
Wrapper& 1 (C4.5) & {\em {85.57\%}}&  3&&   \\
 &  4 (bayes)     &         &   &&  \underline{\em {85.19\%}}\\\hline
 & mean&   {\em {83.45\%}}&  mean &&    {\em {83.86\%}}

\end{tabular}
\end{center}}

\caption{KC2 FSS and learner accuracy runs. Baseline accuracies
shown on line one. {\em Italicized} and blank entries have the
same meaning as in \fig{an1runs}.} \label{fig:kc2runs}
\end{figure}




%\newcommand{\sfrac}[2]{\leavevmode\kern.1em
 %           \raise.5ex\hbox{\footnotesize #1}\kern-.1em
  %                  /\kern-.15em\lower.25ex\hbox{\footnotesize #2}}
\newcommand{\sfrac}[2]{{#1/#2}}
\begin{figure}
{\scriptsize\begin{center}
\begin{tabular}{c|cccc|c}
\multicolumn{1}{c|}{} &C4.5 & Naive Bayes& 1R & ROCKY& total\\\hline
JM1  & $\sfrac{7}{7}$  & $\sfrac{4}{7}$& $\sfrac{0}{1}$& $\sfrac{1}{1}$&12/16\\
AN1  & $\sfrac{4}{7}$  & $\sfrac{6}{7}$& $\sfrac{0}{1}$& $\sfrac{1}{1}$&11/16\\
KC2  & $\sfrac{6}{7}$  & $\sfrac{5}{7}$& $\sfrac{0}{1}$& $\sfrac{1}{1}$&12/16\\
KC1  & $\sfrac{6}{7}$  & $\sfrac{5}{7}$& $\sfrac{0}{1}$& $\sfrac{1}{1}$&12/16\\
CM1  & $\sfrac{4}{7}$  & $\sfrac{5}{7}$& $\sfrac{0}{1}$& $\sfrac{1}{1}$&10/16\\
\hline
total&$\sfrac{27}{35}$  & $\sfrac{25}{35}$& $\sfrac{0}{5}$& $\sfrac{5}{5}$&57/80
\end{tabular}
\end{center}}
\caption{How often FSS generates theories of higher accuracy
than using all available features.}\label{fig:winloss}
\end{figure}

{\bf Results:}
\fig{onerroc} shows the classification
on 10-way generated by ROCKY and 1R.
Figures~\ref{fig:an1runs} to~\ref{fig:kc2runs}
show the average classification
accuracies seen in 10-way cross validation runs of Naive Bayes and WRAPPER
using just the features found by  our FSS methods.

The first line of \fig{an1runs}, \fig{cm1runs}, \fig{jm1runs},
\fig{kc1runs} and \fig{kc2runs} 
shows the results of running all available features through Naive
Bayes and C4.5. \underline{Underlined} entries mark the largest
accuracy generated by any method. {\em Italicized} entries show
where features found by  FSS generated detectors with a higher
accuracy than the baseline. \fig{winloss} is  a summary table
showing how often our FSS methods out-performed all baselines.

Of all our results, CM1 is most unusual.
\fig{cm1runs} shows that the accuracy after FSS was nearly the same
as before FSS. Further, in that dataset some FSS methods (WRAPPER) selected no
feature at all; i.e. WRAPPER found that no feature was more informative
than any other. This result can be partially explained by the nature of that data.
Of all our datasets, CM1 is the smallest and has
 the lowest defect rate (see \fig{datasets}). Perhaps
the target concept in CM1 is too small to be found by the 
methods discussed here.

\section{Questions and Answers} 

Our results let us comment on the the following issues.

{\em Q: Is throwing away information useful for defect
detection?} 

A: Surprisingly, it would seem so.  \fig{winloss} shows
that in $57/80=71\%$ of our experiments, using any FSS method
improved the accuracy over the baseline. Also, in all our
experiments, if all the FSS methods described here are used, then
detectors were found with a higher accuracy than the baseline,
while using far fewer features. If we look at the best detector
(the \underline{underlined} entries), then we see that the best
detectors used between 1 to 6 features selected from a space of 15
to 21 features. Hence, this study endorses FSS for defect detector
generation.

{\em Q: What is a good FSS method for defect detection?}

A: This is unclear but
the  very simple FSS methods (ROCKY and 1R) ran very fast and
resulted in highly accurate theories. Further, ROCKY out-performed
the other FSS methods in four of our five case studies. The
CPU-intensive WRAPPER method is slow to run but, of the more complex
FSS methods, always generated the most accurate theory (using either
C4.5 or Naive Bayes).

{\em Q:Comparatively speaking, how does PCA compare to other FSS methods?}

A:
In this study, PCA has not scored well. In none of our experiments
were the highest accuracy detectors learnt via FSS. Hall \& Holmes
have assessed  a similar set of FSS methods as this study, but on
a broader set of data (none of which related to software defect
detection). Their results are hardly supportive of PCA. They
conclude that if the slow run times of WRAPPER can be tolerated,
then it usually generates the most accurate theories. Otherwise,
in their opinion, CFS and RLF are best~\cite{hall03}. Our results
do not contradict their conclusions- we obtained high accuracies
with CFS, RLF and WRAPPER, and never with CBS, IG, or PCA.





{\em Q: How simple is defect detection?}

A: Apparently, very simple. The
``clean-up'' offered by FSS was very small. In all cases the accuracy
found using all features was less than 7\% of the best accuracy found
after FSS. This suggests that the correlations between variables in
these data sets do not greatly confound defect detector generation.
Note that if most defect data sets lack such correlations then
tools designed to handle highly-correlated datasets (e.g. PCA)
are not necessary.



{\em Q: Is accuracy the best way to judge the effectiveness of a defect detector?}

A: Perhaps not. A striking feature of 
Figures~\ref{fig:an1runs} to~\ref{fig:kc2runs}
is the very 
small variance in the accuracy figures.
In other work~\cite{me03a}, we have assessed hundreds of learnt theories
and found that accuracy can remain stable while other important features
can vary wildly. For example, two detectors with the same accuracy
can have very different probabilities of false alarms.
Other data mining research  suggests that accuracy alone  is not a good
indicator of learner performance in many domains~\cite{provost98case}.
This may be attributed to greatly skewed class
distributions or domain related anomalies. We are currently repeating
our study, but this time assessing detectors via:
\bi
\item
The {\em cost} of collecting
the data for the detectors (collecting cyclomatic complexity using Mccabes
can be very expensive due to licensing issues);
\item The probability of false alarms, given that the detector has been triggered;
\item The probability of true detection alarms, given that
the detector has been triggered;
\item The probability that a defect has been missed, given that the detector
has not been triggered;
\item The stability of the detector under N-way cross validation;
\item The stability of the detector when applied to different data sets;


\ei

Our current thinking is that finding a ``best'' detector judged on all the above criteria
will require some kind of N-dimensional optimization toolkit.

{\em Q: What is the best detector?}

A: We did not find that  McCabe's standard
detector  of $v(g)>10$ was the most accurate. However, we cannot
offer an external valid alternative.
The defect
detectors did not stabilize across the different data sets. For example,
the most accurate defect detectors found by ROCKY are shown
in \fig{bocky}
\begin{figure}
{\footnotesize\begin{center}\begin{tabular}{c|c|c}
dataset&detector& accuracy\\\hline
AN1& $unique\; operands >= 8.14$ &66.08\%\\
CM1& $I \ge 167.94$   & 90.54\%\\
JM1& $unique\; operands>= 60.48$                   &81.10\%\\
KC1&$V\ge 1106.55$& 85.62\%\\
KC2&  $ev(g)  >= 4.99$                       &85.28\% \\
\end{tabular}\end{center}}
\caption{Best detectors learnt by ROCKY.}\label{fig:bocky}
\end{figure}
(we report ROCKY's output here since that output is
small enough to read and
ROCKY's
best accuracies were always very close to the best overall accuracies).
Note that variations in the learnt detectors:
\bi
\item
The  McCabe $ev(g)$ value was the most accurate in KC2
\item
The Halstead values of {\em intelligence content} ($I$), 
the  {\em volume} of the program ($V$) or
the $unique\; operands$ value
were the feature that
yielded the most accurate
detectors in the other data sets (for an explanation on
these metrics, see the appendix).
\item
The threshold value for the two detectors that
use the same Halstead metric were wildly different: 60.48 in JM1 and
8.14 in AN1.
\ei
Clearly, the distributions of variables
seen in JM1 and AN1 are very different. If distributions always
vary
so wildly between defect data sets, then we it may be folly to
imagine that a single defect detector rule such as $v(g)>10$
will suit all software
development. Instead, companies should tune their defect detectors
according to their own historical logs describing their own people
building their own kind of application.

\section{Discussions}

We offer our results with two cautions.
Firstly, we have
only explored feature subset selection for defect detectors using
five data sets. To the best of our knowledge, our sample is much larger
and more repeatable than previous studies. While it would be
preferrable to base our analysis on more data sets,
to the best of our knowledge, our study is based on a broader
sample size than previous reports about defect detectors.
Most of our data is public domain 
and  encourage other researchers to test their methods
on our data.

Secondly, we caution researchers against restricting their analysis of
structural measurements and failure data to the simple techniques
described in this paper.  Although software defect detection may be a
simple task, and simple fault models may be deployed as part of
production software development efforts, the research underlying such
models must still apply the full range of measurement and analysis
techniques to develop the models in the first place.  This ensures
that a richer set of relationships between structural measures and
fault content will be developed, and allows the development of
meaningful benchmarks for the simpler models.

Those two cautions notwithstanding, our conclusion must be as follows.
If in the usual case we see that accurate defect detectors can be
found after trivially simple algorithms have rejected most of the
structural features, then software defect detection is a very
simple task indeed.



{\footnotesize
\bibliographystyle{klunamed}
\bibliography{refs,../../refs}}

\appendix
\section{Metrics}\label{metrics}

This appendix shows our standard tutorial on commonly used structure
metrics.


\subsection{McCabe}\label{mccabe}


In order to facilitate the search for error-prone modules or
functions, many tools have evolved over the past few years. One of
the most popular ones (and the one being used extensively at NASA
IV\&V) is the McCabe IQ\begin{scriptsize}\copyright\end{scriptsize}
package. This package can evaluate Ada, C and C++ source code, and
provides many different types of software metrics.

 The McCabe metrics
are a collection of four software metrics: essential complexity,
cyclomatic complexity, design complexity and LOC~\cite{mccabe76}. Of
these four, all but LOC are metrics which were developed by T. J.
McCabe. McCabe \& Associates claim that these complexity measurements
provide insight into the reliability and maintainability of a module.
For example, around NASA IV\&V, a cyclomatic complexity of over 10 or
an essential complexity of over 4 is flagged as a module that will be
difficult to maintain and/or debug. This paper will not attempt to
make any refutation to those claims and practices; however, these
metrics are also commonly used as predictors for error-prone modules.
As this paper will demonstrate, these complexity measurements do not
\emph{always} point the way towards modules with increased error
density.

The following paragraphs present a short overview of the three
complexity metrics mentioned previously.


Cyclomatic Complexity, or $v(G)$, measures the number of
\emph{linearly independent paths}\footnote{A set of paths is
linearly independent if no path in the set is a linear combination
of any other paths in the set} through a program's
flow graph\footnote{A flow graph is a directed graph where each node
corresponds to a program statement, and each arc indicates the
flow of control from one statement to another}.  $v(G)$ is
calculated by
$v(G) = e - n + 2$,
where $G$ is a program's flow graph, $e$ is the number of arcs in
the flow graph, and $n$ is the number of nodes in the
flow graph~\cite{fenton96}.

Essential Complexity, or $ev(G)$, is the extent to which a
flow graph can be ``reduced'' by decomposing all the sub-flow-graphs
of $G$ that are D-structured primes \footnote{D-structured primes
are also sometimes referred to as ``proper one-entry one-exit
sub-flow-graphs''.  For a more thorough discussion of D-primes, see
\cite{fenton96}}. $ev(G)$ is calculated by
$ev(G) = v(G) - m$
where $m$ is the number of sub-flow-graphs of $G$ that are
D-structured primes.~\cite{fenton96}

Design Complexity, or $iv(G)$, is the cyclomatic complexity of a
module's reduced flow graph.  The flow graph, $G$, of a module is
reduced to eliminate any complexity which does not influence the
interrelationship between design modules.  This complexity
measurement reflects the modules calling patterns to its immediate
subordinate modules.

\subsection{Halstead}\label{halstead}
Another commonly used collection of software metrics are the
Halstead Metrics~\cite{halstead77}. They are named after their
creator, Maurice H. Halstead.  Halstead felt that software (or the
writing of software) could be related to the themes which were
being advanced at that time in the psychology literature.  He
created several metrics which are meant to encapsulate these
properties; these metrics can be extracted by use of the McCabe IQ
tool mentioned previously, and are discussed in detail below.

Halstead began by defining some basic measurements (these
measurements are collected on a
per module basis):\\
\begin{center}
$\mu_{1} =$ number of unique operators\\
$\mu_{2} =$ number of unique operands\\
$N_{1} =$ total occurrences of operators\\
$N_{2} =$ total occurrences of operands\\
$\mu_{1}^* =$ potential operator count\\
$\mu_{2}^* =$ potential operand count\\
\end{center}
These six metrics are self explanatory, with the possible
exception of the potential operator/operand counts.  Halstead
defines $\mu_{1}^*$ and $\mu_{2}^*$ as the \emph{minimum} possible
number of operators and operands for a module.  This minimum
number would occur in a (potentially fictional) language in which
the required operation already existed, possibly as a subroutine,
function, or procedure.  In such a case, $\mu_{1}^*=2$, since at
least two operators must appear for any function; one for the name
of the function, and one to serve as an assignment or grouping
symbol. $\mu_{2}^*$ represents the number of parameters, without
repetition, which would need
to be passed to the function or procedure.

Using these measurements, Halstead defined the
\emph{length} of a program $P$ as:
$N = N_{1} + N_{2}$;
the vocabulary of $P$ is
$\mu = \mu_{1} + \mu_{2}$; and
the \emph{volume} of $P$ (akin to the number
of mental comparisons needed to write a program of length N) is
$V = N * log_{2}\mu$.

A variant of $V$ is
$V^{*}$ is the potential volume - the volume of the minimal size
implementation
of $P$:
$V^* = (2 + \mu{_2}^{*})log_{2}(2 + \mu{_2}^{*})$.
The \emph{program level} of a program $P$ with volume $V$ is
$L = V^{*}/V$.
The inverse of level is \emph{difficulty}; i.e.
$D = 1/L$

According to Halstead's theory,
we can calculate an estimate $\hat{L}$ of $L$ as
$\hat{L} = 1/D = \frac{2}{\mu_{1}} * \frac{\mu_{2}}{N_{2}}$.
The intelligence content of a program, $I$, is
$I = \hat{L} * V$ and
the effort required to generate $P$ is given by
$E = \frac{V}{\hat{L}} = \frac{\mu_{1}N_{2}Nlog_{2}\mu}{2\mu_{2}}$
where the unit of measurement
$E$ is elementary mental discriminations needed to understand $P$.
From $E$ we can generate $B$ (an estimate of the number of errors)
using $B=K*E^{0.67}$ (where $K$ is a language-specfic constant).
Finally,
according to Halstead,
the required programming time $T$ for a program of effort $E$ is
$T = E/18 seconds$.

\end{article}
\end{document}


This research has several motivations.
First, in our experience, defect detectors are widely used.
 Second, we work with the
NASA Independent Verification and Validation (IV\&V) Facility
which has a duty to assess and improve software practices within
NASA.  Third, there is some evidence in
the literature that dramatic reduction in detector complexity
is possible.

The IV\&V Facility in Fairmont, West
Virginia is responsible for verifying that software developed or
acquired to support NASA missions complies with the stated
requirements. Additionally, the Facility validates that the
software is suitable for its intended use. In short, the Facility
ensures that the software is being developed properly, and that
the right software is being developed or acquired. As the sole
entity with the responsibility for IV\&V of all NASA mission
software, the IV\&V Facility is in a unique position to create and
maintain a master repository of software metrics. Under this
charter, the IV\&V Facility reviews requirements, code, and test
results from NASA’s most critical projects; hence, many of the
required metrics are collected as a matter of course. No other
organization has insight into such a broad range of NASA projects.
This affords the IV\&V Facility an unequaled opportunity to
research not only the early life cycle indicators of software
quality, but other topics as well. Many large corporations have
similar software metrics repositories; however, it is not always
in their best interest to release data or results to the public.
In the case of the IV\&V Facility, the objective is to improve
NASA’s mission software regardless of the source. Once NASA
projects agree to distribution, then sanitized data\footnote{Sanitized data has
project-specific identifiers removed} would be made
available to NASA, industry, and academia to support software
development and research by other organizations. This is
consistent with the IV\&V Facilities research vision of “See more,
learn more, tell more.”

\section{Conclusion}\label{conclusion}

 We have shown that very simple FSS methods are adequate
 for generating comparatively good defect detectors.
 However, it would be premature to use our resettlement other more
 complex analysis methods of defect
 data such as PCA.
 Given the size of the international software industry,
 defect detection research is an important task.  This research must
 be in two parts. Firstly, a range of techniques must be explored
 in order to survey the space of possibilities. Secondly, the
 simplest useful subset of those techniques should be selected for
 widespread deployment. Without knowledge of the space of options,
 it is impossible to assess the merits of some proposed simple
 subset. Hence, we view our previous PCA research as an essential
 prerequisite to the results shown here.


Software with defects can be unreliable. Hence, it is standard
practice for software engineers to expend  effort searching for
potential defects. However, in many software projects, it may be too
expensive to rigorously search all parts of a systems for their
defects. When working against fixed deadlines, test engineers often
use {\em defect detectors} to indicate areas of code that deserve
more attention. Constructing good defect detectors has extensively
studied
(e.g.~\cite{Muns98,Muns02,Muns90,Muns91,Niko97,khoshgoftaar99,porter90,tiang95,me02e}).
Based on the case studies shown here, we will argue that the
technology used in that previous work was far too complicated.

Defect detectors are worth studying since they are widely used in the
software industry. We are aware  of several large government software
contractors that will routinely reject software modules if commercial
defect detectors such as  McCabes QA$^{\footnotesize\copyright}$
predict that they are fault prone. Hence, defect detectors have a
major economic impact on a project when they may force programmers to
rewrite code.


The danger with defect detectors is that  if they have weaknesses,
then it is possible that defects will slip by unnoticed. If the
defect detector is flawed, then test engineers will focus on the
wrong parts of the system; hence, they may miss important software
errors.

 However, a
major problems arise due to the significant correlations between the
measurements ~\cite{Muns90, Hall00} - for example, it is well known
that there is a high correlation between a function's or method's
cyclomatic complexity, $v(G)$ ~\cite{mccabe76}, and the number of
lines of source code in that function or method
(module)~\cite{shepperd94}.



