%XXX designed detectors
%XXX external validity turkey
%% XXX return to worst case below
%%% used mann-whitney cause this is not paired test. 
%XX recall our experimental rig: 

%% bare_jrnl.tex
%% V1.1
%% 2002/08/13
%% by Michael Shell
%% mshell@ece.gatech.edu
%%
%% NOTE: This text file uses MS Windows line feed conventions. When (human)
%% reading this file on other platforms, you may have to use a text
%% editor that can handle lines terminated by the MS Windows line feed
%% characters (0x0D 0x0A).
%%
%% This is a skeleton file demonstrating the use of IEEEtran.cls
%% (requires IEEEtran.cls version 1.6 or later) with an IEEE journal paper.
%%
%% Support sites:
%% http://www.ieee.org
%% and/or
%% http://www.ctan.org/tex-archive/macros/latex/contrib/supported/IEEEtran/
%%
%% This code is offered as-is - no warranty - user assumes all risk.
%% Free to use, distribute and modify.

% *** Authors should verify (and, if needed, correct) their LaTeX system  ***
% *** with the testflow diagnostic prior to trusting their LaTeX platform ***
% *** with production work. IEEE's font choices can trigger bugs that do  ***
% *** not appear when using other class files.                            ***
% Testflow can be obtained at:
% http://www.ctan.org/tex-archive/macros/latex/contrib/supported/IEEEtran/testflow


% Note that the a4paper option is mainly intended so that authors in
% countries using A4 can easily print to A4 and see how their papers will
% look in print. Authors are encouraged to use U.S. letter paper when
% submitting to IEEE. Use the testflow package mentioned above to verify
% correct handling of both paper sizes by the author's LaTeX system.
%
% Also note that the "draftcls", not "draft", option should be used if
% it is desired that the figures are to be displayed in draft mode.

% *************************************************************************
% You can now use this template both for submitting to peer review and,
% if your paper is accepted, for sending in final publication materials.
% To change from peer review format (single column, double-spaced) to
% final publication format (double column, single-spaced), just move the
% comment-line sign (%) from one \documentclass line to the other.
% The first is for peer review format(single column), the second is for final publication(double column).

%\documentclass[12pt,journal,draftcls,letterpaper,onecolumn]{IEEEtran}
%\renewcommand{\baselinestretch}{1.4}
%\documentclass[9.5pt,journal,cite, compsoc,twocolumn]{IEEEtran}
%\documentclass[9.5pt,journal,cite,final,finalsubmission,twocolumn]{IEEEtran}
\documentclass[9pt,journal,compsoc,twocolumn]{IEEEtran}
% *************************************************************************

\usepackage{pifont}
\usepackage{eso-pic}
\usepackage{color}
\usepackage{type1cm}
%\makeatletter
%  \AddToShipoutPicture{%
%    \setlength{\@tempdimb}{.5\paperwidth}%
%    \setlength{\@tempdimc}{.5\paperheight}%
%    \setlength{\unitlength}{1pt}%
%      \makebox(600,900){\rotatebox{45}{\textcolor[gray]{0.85}{\fontsize{9cm}{9cm}\selectfont{Draft}}}}}
%\makeatother
%
% If the IEEEtran.cls has not been installed into the LaTeX system files,
% manually specify the path to it:
% \documentclass[journal,draftcls,onecolumn]{../sty/IEEEtran}


% some very useful LaTeX packages include:
\usepackage[all]{xy}
\usepackage{cite}      % Written by Donald Arseneau
                        % V1.6 and later of IEEEtran pre-defines the format
                        % of the cite.sty package \cite{} output to follow
                        % that of IEEE. Loading the cite package will
                        % result in citation numbers being automatically
                        % sorted and properly "ranged". i.e.,
                        % [1], [9], [2], [7], [5], [6]
                        % (without using cite.sty)
                        % will become:
                        % [1], [2], [5]--[7], [9] (using cite.sty)
                        % cite.sty's \cite will automatically add leading
                        % space, if needed. Use cite.sty's no adjust option
                        % (cite.sty V3.8 and later) if you want to turn this
                        % off. cite.sty is already installed on most LaTeX
                        % systems. The latest version can be obtained at:
                        % http://www.ctan.org/tex-archive/macros/latex/contrib/supported/cite/

\usepackage{graphicx}  % Written by David Carlisle and Sebastian Rahtz
                        % Required if you want graphics, photos, etc.
                        % graphicx.sty is already installed on most LaTeX
                        % systems. The latest version and documentation can
                        % be obtained at:
                        % http://www.ctan.org/tex-archive/macros/latex/required/graphics/
                        % Another good source of documentation is "Using
                        % Imported Graphics in LaTeX2e" by Keith Reckdahl
                        % which can be found as esplatex.ps and epslatex.pdf
                        % at: http://www.ctan.org/tex-archive/info/

%\usepackage{psfrag}    % Written by Craig Barratt, Michael C. Grant,
                        % and David Carlisle
                        % This package allows you to substitute LaTeX
                        % commands for text in imported EPS graphic files.
                        % In this way, LaTeX symbols can be placed into
                        % graphics that have been generated by other
                        % applications. You must use latex->dvips->ps2pdf
                        % workflow (not direct pdf output from pdflatex) if
                        % you wish to use this capability because it works
                        % via some PostScript tricks. Alternatively, the
                        % graphics could be processed as separate files via
                        % psfrag and dvips, then converted to PDF for
                        % inclusion in the main file which uses pdflatex.
                        % Docs are in "The PSfrag System" by Michael C. Grant
                        % and David Carlisle. There is also some information
                        % about using psfrag in "Using Imported Graphics in
                        % LaTeX2e" by Keith Reckdahl which documents the
                        % graphicx package (see above). The psfrag package
                        % and documentation can be obtained at:
                        % http://www.ctan.org/tex-archive/macros/latex/contrib/supported/psfrag/

%\usepackage{subfigure} % Written by Steven Douglas Cochran
                        % This package makes it easy to put subfigures
                        % in your figures. i.e. "figure 1a and 1b"
                        % Docs are in "Using Imported Graphics in LaTeX2e"
                        % by Keith Reckdahl which also documents the graphicx
                        % package (see above). subfigure.sty is already
                        % installed on most LaTeX systems. The latest version
                        % and documentation can be obtained at:
                        % http://www.ctan.org/tex-archive/macros/latex/contrib/supported/subfigure/

\usepackage{url}       % Written by Donald Arseneau
                        % Provides better support for handling and breaking
                        % URLs. url.sty is already installed on most LaTeX
                        % systems. The latest version can be obtained at:
                        % http://www.ctan.org/tex-archive/macros/latex/contrib/other/misc/
                        % Read the url.sty source comments for usage information.

\usepackage{stfloats}  % Written by Sigitas Tolusis
                        % Gives LaTeX2e the ability to do double column
                        % floats at the bottom of the page as well as the top.
                        % (e.g., "\begin{figure*}[!b]" is not normally
                        % possible in LaTeX2e). This is an invasive package
                        % which rewrites many portions of the LaTeX2e output
                        % routines. It may not work with other packages that
                        % modify the LaTeX2e output routine and/or with other
                        % versions of LaTeX. The latest version and
                        % documentation can be obtained at:
                        % http://www.ctan.org/tex-archive/macros/latex/contrib/supported/sttools/
                        % Documentation is contained in the stfloats.sty
                        % comments as well as in the presfull.pdf file.
                        % Do not use the stfloats baselinefloat ability as
                        % IEEE does not allow \baselineskip to stretch.
                        % Authors submitting work to the IEEE should note
                        % that IEEE rarely uses double column equations and
                        % that authors should try to avoid such use.
                        % Do not be tempted to use the cuted.sty or
                        % midfloat.sty package (by the same author) as IEEE
                        % does not format its papers in such ways.

\usepackage{amsmath}   % From the American Mathematical Society
                        % A popular package that provides many helpful commands
                        % for dealing with mathematics. Note that the AMSmath
                        % package sets \interdisplaylinepenalty to 10000 thus
                        % preventing page breaks from occurring within multiline
                        % equations. Use:
%\interdisplaylinepenalty=2500
                        % after loading amsmath to restore such page breaks
                        % as IEEEtran.cls normally does. amsmath.sty is already
                        % installed on most LaTeX systems. The latest version
                        % and documentation can be obtained at:
                        % http://www.ctan.org/tex-archive/macros/latex/required/amslatex/math/



% Other popular packages for formatting tables and equations include:

% Frank Mittelbach's and David Carlisle's array.sty which improves the
% LaTeX2e array and tabular environments to provide better appearances and
% additional user controls. Array.sty is already installed on most systems.
% The latest version and documentation can be obtained at:
% http://www.ctan.org/tex-archive/macros/latex/required/tools/

% Mark Wooding's extremely powerful MDW tools, especially mdwmath.sty and
% mdwtab.sty which are used to format equations and tables, respectively.
% The MDWtools set is already installed on most LaTeX systems. The lastest
% version and documentation is available at:
% http://www.ctan.org/tex-archive/macros/latex/contrib/supported/mdwtools/

% V1.6 of IEEEtran contains the IEEEeqnarray family of commands that can
% be used to generate multiline equations as well as matrices, tables, etc.


% Also of notable interest:

% Scott Pakin's eqparbox package for creating (automatically sized) equal
% width boxes. Available:
% http://www.ctan.org/tex-archive/macros/latex/contrib/supported/eqparbox/




% *** Do not adjust lengths that control margins, column widths, etc. ***
% *** Do not use packages that alter fonts (such as pslatex).         ***
% There should be no need to do such things with IEEEtran.cls V1.6 and later.


% correct bad hyphenation here
\hyphenation{op-tical net-works semi-conduc-tor}


\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}}

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


\newcommand{\sect}[1]{\S\ref{sec:#1}}
\newcommand{\bd}{\begin{description}}
\newcommand{\ed}{\end{description}}
\newcommand{\bi}{\begin{smallitem}}
\newcommand{\ei}{\end{smallitem}}
\newcommand{\be}{\begin{smallenum}}
\newcommand{\ee}{\end{smallenum}}
\newcommand{\fig}[1]{Figure~\ref{fig:#1}}
\newcommand{\eq}[1]{Equation~\ref{eq:#1}}
\newcommand{\tion}[1]{\S\ref{sec:#1}}
\newcommand{\aive}{{\"aive}\ }

\newcommand{\boxplot}[5]{
	\begin{picture}(100,7)
		%\put(#1,4){\circle*{2}}
		\put(#3,4){\circle*{4}}
                %\put(#5,4){\circle*{1}}
		\put(50,0){\line(0,1){7}}
                \linethickness{0.25mm}
                \put(#2,4){\line(1,0){#4}}		
	\end{picture}
} 

\begin{document}
%
% paper title
\title{ 
Learning Better Defect Predictors From Static Code Features 
}
%
%
% author names and IEEE memberships
% note positions of commas and non breaking spaces ( ~ ) LaTeX will not break
% a structure at a ~ so this keeps an authors name from being broken across
% two lines.
% use \thanks{} to gain access to the first footnote area
% a separate \thanks must be used for each paragraph as LaTeX2e's \thanks
% was not built to handle multiple paragraphs
\author{Tim Menzies,
       Zach Milton,  
Burak Turhan, Bojan Cukic,  Yue Jiang, Ay\c{s}e Bener%
% <-this % stops a space
\thanks{Dr. Menzies, Mr. Milton, Dr. Cukic, and Ms. Jiang are with the Lane Department
of Computer Science and Electrical Engineering, West Virginia University, USA:
\protect\url{tim@menzies.us}, 
\protect\url{zmilton@mix.wvu.edu};
\protect\url{bojan.cukic@mail.csee.wvu.edu};
\protect\url{yjiang1@mix.wvu.edu}.}%
\thanks{Dr. Bener and Dr. Turhan are with the
Dept. of Computer Engineering, Bo{\u g}azi{\c c}i  University, Turkey:
\protect\url{bener,turhanb@boun.edu.tr}}%
\thanks{
This research was supported by NSF grant CCF-0810879 and the Turkish Scientific Research Council (Tubitak EEEAG 108E014).}
\thanks{For enquiries on this work,
email \protect\url{tim@menzies.us}.
For an earlier draft,  see \protect\url{http://menzies.us/pdf/08bias.pdf}.}
}

% note the % following the last \IEEEmembership and also the first \thanks -
% these prevent an unwanted space from occurring between the last author name
% and the end of the author line. i.e., if you had this:
%
% \author{....lastname \thanks{...} \thanks{...} }
%                     ^------------^------------^----Do not want these spaces!
%
% a space would be appended to the last name and could cause every name on that
% line to be shifted left slightly. This is one of those "LaTeX things". For
% instance, "A\textbf{} \textbf{}B" will typeset as "A B" not "AB". If you want
% "AB" then you have to do: "A\textbf{}\textbf{}B"
% \thanks is no different in this regard, so shield the last } of each \thanks
% that ends a line with a % and do not let a space in before the next \thanks.
% Spaces after \IEEEmembership other than the last one are OK (and needed) as
% you are supposed to have spaces between the names. For what it is worth,
% this is a minor point as most people would not even notice if the said evil
% space somehow managed to creep in.
%
% The paper headers
\markboth{Journal of VVV,~Vol.~WWW, No.~XXX,~Month~200Y}{Menzies \MakeLowercase{\textit{et al.}}:
Customizing Defect Predictors Business Goals}
% The only time the second header will appear is for the odd numbered pages
% after the title page when using the two side option.


% If you want to put a publisher's ID mark on the page
% (can leave text blank if you just want to see how the
% text height on the first page will be reduced by IEEE)
%\pubid{0000--0000/00\$00.00~\copyright~2002 IEEE}

% use only for invited papers
%\specialpapernotice{(Invited Paper)}

% make the title area

%\IEEEaftertitletext{\vspace{-1\baselineskip}\noindent
%\begin{abstract}
%While data miners 
%can 
%learn defect predictors from static code features, the performance
%improvement in such detectors is curiously static.
%One explanation for this {\em ceiling effect} is that
%static code features have {\em limited information content}. 
%If so, then
%it should be useful to give
%our learners more knowledge about the problems they are processing.
%Data miners build predictors using a performance
%criteria $P$ (e.g. accuracy), then assess them
%using another criteria $Q$ (e.g. probability of detection).
%Typically, $P \not= Q$, so
%learners are {\em blind to their purpose}. Therefore, it   is hardly surprising  
%that they cannot find ways to better their performance.
%WHICH is a new data miner with $P \approx Q$; i.e.  a similar evaluation
%criteria is applied during training and testing. After  matching
%$P$ to  the goals of a particular business application, we found that
%commonly used data miners perform {\em no
%better than} simple manual methods; and that
%WHICH outperforms
%other methods, coming close to a theoretical upper bound
%in performance  (50 and 75 percentile of 70.9\% and 80\%, respectively).
%That is, with knowledge of the business
%application, it is possible to build new data miners that overcome
%ceiling effects.
%%XXX close and can do better
%\end{abstract}
%\noindent\begin{keywords}
%product metrics, defect prediction, data mining, decision-tree learning, rule-learning,
%C4.5, RIPPER.
%\end{keywords}
%}
\maketitle
\begin{abstract}
When applying data mining to defect prediction, the standard goal is  to maximize ``AUC(pf,pd)'';
i.e. the area under the curve of a probability of detection vs false
alarm plot.  
Recent research results have been
curiously static: despite much work, there have been no 
progress towards better achieving this goal.  

We speculate that current data mining methods may have
exhausted the information relevant to the AUC(pf,pd) goal.  
Accordingly, we
explore changing the standard goal.  
Learners that maximize ``AUC(effort,pd)''
find the {\em smallest} set of modules 
that contain the {\em most} errors. 

WHICH is a meta-learner framework
that can be quickly customized to different goals.
When customized to AUC(effort,pd),
WHICH performs best of all the data mining methods studied here.
More
importantly,  measured in terms of this new goal,  certain widely
used learners perform {\em much worse} than simple manual methods.

We therefore caution against the  indiscriminate application of
learners.  Learners must be carefully chosen and
customized to the goal at hand.  WHICH is a simple method for quickly
tuning a learner to the specific local business goals.
\end{abstract}
\section{Introduction} A repeated result
is that static code features such as lines of code per module,
number of symbols in the module, etc can be used by a data miner
to learn a predictor which modules are more likely to contain defects
(e.g.
\cite{weyeuker08,halstead77,mccabe76,chapman02,me04g,polyspace,nagappan05,hall00,nikora03,conf/icse/NagappanB05a,khoshgoftaar01,conf/ictai/TangK04,journals/ese/KhoshgoftaarS03,me03a,me02e,me03k,me03q,porter90,tiang95,khoshgoftaar99,srinivasan95,me07b}).
Such defect predictors can be used to allocate the appropriate
verification and validation budget assigned to different code
modules~\cite{me03q}.

The current high water mark in this field has been curiously static for several years. 
For example, for three years we have been unable to improve on our 2006 results~\cite{me07b}.
Other studies report the same {\em ceiling effect}: 
many methods learn defect predictors that
perform statistically insignificantly different to the best results.
For example, after a careful study 19 data miners for learning defect predictors seeking
to maximize the area under the curve of detection-vs-false alarm curve,
Lessmann et.al.~\cite{lessmann09} conclude \begin{quote}
{\em ...the
importance of the classification model is less than generally assumed
and that practitioners are free to choose from a broad set of candidate models when building defect predictors.}\end{quote}
This article argues for a very different conclusion.
The results of  Lessmann et al. are undoubtably correct, in the context of
maximizing detection and minimizing false alarm rates- but this is not the only possible
goal of a defect predictor.
WHICH~\cite{milton08} 
is a meta-learning scheme
where domain specific goals can be inserted into the core of the learner.
When those goals are set to one particular business goal (``find the {\em fewest} modules that contain the
{\em most} errors'') then the ceiling effect disappears:
\bi
\item
WHICH significantly out-performs other learning schemes.
\item
More importantly, 
when measured in terms of this new goal, certain widely used learners perform {\em worse that simple manual methods}. 
\ei
That is, contrary to the views of Lessmann et al,
the selection of a learning method appropriate to a particular goal is very critical.
Learners
that appear useful when perusing certain goals, can be demonstrably inferior when perusing others.
We recommend WHICH as a simple method to creating such customizations.

The rest of this paper is structured as follows. \sect{back} describes and defends
the use of static code features for learning defect predictors. \tion{ceiling} documents
the ceiling effect that has stalled progress in this field. After that, the rest of the paper
discusses novel methods to break through the ceiling effect.

Note that parts of \tion{back} have appeared before~\cite{me03q} or will soon appear~\cite{me09b}.
Also \tion{ceiling} comes from~\cite{me08d}. The rest of this paper is unpublished work.


\section{Background}\label{sec:back}
\subsection{Reliability Engineering}
In order to explain defect predictors, it is useful
to distinguish them from reliability engineering~\cite{musa87,littlewood97}.
Given a history of defects in a running system,
reliability engineers extrapolate a {\em reliability growth curve}
that predicts the
future probability of failure on demand of a developing system.  Such curves
can predict how long before a system
reaches a required level of reliability.

Reliability engineering assumes that the system is running. Hence, they can not
be used during development. 
In many cases,
it is undesirable to delay software rework until after the system
is running since the longer a defect remains in code, the more
expensive it is to remove~\cite{boehm88}.  
Hence, this article focuses on what quality predictions can be made {\em before}
a system can execute.

\subsection{Blind Spots}

Our premise is that building high quality software is
expensive. Hence, during development, developers {\em skew} their limit quality assurance (QA)
budgets
towards artifacts they believe most require extra QA.
For example, it is common at NASA to focus QA more on the on-board guidance system than
the ground-based database storing scientific data collected from a satellite.

This skewing process can introduce an inappropriate bias to quality
assurance (QA). If  the QA activities concentrate on  project
artifacts, say {\em A,B,C,D}, then that leaves {\em blind spots} in
{\em E,F,G,H,I,...}. 
Blind spots can compromise high assurance
software. Leveson remarks that in modern complex systems, unsafe
operations often result from an unstudied interaction between
components~\cite{leven95}. For example, Lutz and
Mikulski~\cite{lutz03} found a blind spot in NASA deep-space
missions: most of the mission critical {\em in-flight} anomalies
resulted from errors in {\em ground software} that fails to
correctly collect in-flight data.

To avoid blind spots, one option is to rigorously assess all aspects
of all  software modules. But this is
impractical. Software projects budgets are finite and QA
effectiveness increases with QA effort. A {\em linear} increase in
the confidence $C$ that we have found all faults can take {\em
exponentially} more effort. For example, to detect one-in-a-thousand
module faults, moving $C$ from 90\% to 94\% to 98\% takes 2301,
2812, and 3910 black box tests (respectively)\footnote{A randomly
selected input to a program will find a fault with probability $x$.
Voas observes~\cite{voas95} that after $N$ random black-box tests,
the chance of the inputs not revealing any fault is $(1-x)^N$.
Hence, the chance $C$ of seeing the fault is $1-(1-x)^N$ which can
be rearranged to
 $N(C,x)=\frac{log(1 -
C)}{log(1-x)}$. For example, $N(0.90,10^{-3})=2301$.}.
%\item {\bf Automatic formal methods:}
%The
%infamous state space explosion problem imposes
%strict limits on how much a system can be explored
%via automatic formal methods~\cite{me00q}.
Lowry et.al.~\cite{lowrey98} and Menzies and Cukic~\cite{me99q,me00y}
offer numerous other examples
where assessment effectiveness is exponential on effort.

Exponential cost increase quickly exhausts finite QA resources.
Hence, blind spots can't be avoided and must be managed. Standard
practice is to apply the best available assessment methods on the
sections of the program that the best available domain knowledge
declares is the most critical.  We endorse this approach.  Clearly,
the most critical sections require the best known assessment
methods, in hope of minimizing the risk of safety or mission
critical failure occurring post deployment. However, this focus on
certain sections can blind us to defects in other areas which,
through interactions, may cause similarly critical failures.
Therefore, the standard practice should be augmented with a {\em
lightweight sampling policy} that (a)~explores the rest of the
software and (b)~raises an alert on parts of the software that
appear problematic.  This sampling approach is incomplete by
definition. Nevertheless, it is the only option when 
resource limits block
complete assessment.

\subsection{Lightweight Sampling}

\subsubsection{Data Mining}
One method for building a lightweight sampling policy is
{\em data mining} over {\em static code features}.
For this paper, we define {\em data mining} to be the process of summarizing
tables of data where rows are {\em examples} and columns are the {\em features}
collected for each example\footnote{Technically, this is 
{\em supervised 
learning} in the {\em absence of a  background theory}.
For notes on {\em unsupervised learning}, see papers discussing {\em clustering}
such as~\cite{bradley98scaling}.
For notes on {\em using a background theory}, see (e.g.) papers discussing
the learning or tuning of Bayes nets~\cite{fenton99}. 
}
One special feature is called the {\em class}.
The appendix to this paper described various kinds of data miners including the following:
\bi
\item N\aive Bayes classifiers use statistical combinations of features
to predict for class value. Such classifiers are called ``naive'' since they assume
all the features are statistically independent. 
Nevertheless, a repeated
empirical result that, on average, seemingly n\aive Bayes classifiers perform as well
as other seemingly more sophisticated schemes (e.g. see Table~1 in~\cite{domingos97optimality}).
\item Rule learners like RIPPER~\cite{cohen95} generate lists of rules. When 
classify a new code module, we take features extracted from that module and
run down the rule list. The output classification is the first rule in the list
whose condition is satisfied.
\item Decision tree learners like C4.5~\cite{quinlan92} build one  single-parent tree whose
internal nodes test for feature values and whose leaves refer to class ranges.
The output of a decision tree is a branch of satisfied tests leading to a single
leaf classification.
\ei
There are many alternatives and extensions to these learners.
Much recent work has explored the value of building {\em forests}
of decision trees using randomly selected subsets of the features~\cite{briemann01,jiang08a}.
Regardless of the learning method, the output is the same: 
combinations of standard features that predict
for different class values. 

\begin{figure}
\begin{center}{\scriptsize
\begin{tabular}{l@{~}|l@{~}|l@{~}|c@{~}p{3.9cm}|}\cline{2-5}
%\begin{tabular}{|l|l|lcl|}\hline
%\multicolumn{3}{|c}{grouping}&\multicolumn{2}{|c|}{measure}\\\hline
		&\multicolumn{2}{l}{m = Mccabe }       &$v(g)$  &cyclomatic\_complexity  \\
        &        \multicolumn{2}{l}{~}                                 & $iv(G)$&design\_complexity\\
        &         \multicolumn{2}{l}{~}                                & $ev(G)$&essential\_complexity\\\cline{2-5}
        &locs&{loc}                         &   &loc\_total (one line = one count\\\cline{3-5}
	&	&loc(other)                      &   &loc\_blank           \\
        &       &                                &   &loc\_code\_and\_comment\\
        &       &                                &   &loc\_comments         \\
        &        &                                &   &loc\_executable\\
        &       &                                &    &number\_of\_lines (opening to closing brackets)\\\cline{2-5}
	&{Halstead} & h& $N_1$ &num\_operators\\
        &       &                                 &$N_2$ &num\_operands \\
        &       &                                 &$\mu_1$ &num\_unique\_operators\\
        &       &                                 &$\mu_2$ &num\_unique\_operands\\\cline{3-5}
        &       &  { H}&$N$  &length: $N= N_1 + N_2$\\
        &       &                                 & $V$  &volume: $V=N * log_{2}\mu$\\
        &       &                                 & $L$  &level: $L=V^*/V$ where\newline $V^*=(2+\mu{_2}^{*})log_{2}(2+\mu{_2}^{*})$\\
        &       &                                 & $D$  &difficulty: $D=1/L$\\
        &       &                                 &$I$   &content: $I=\hat{L}*V$ where\newline $\hat{L}=\frac{2}{\mu_{1}} * \frac{\mu_{2}}{N_{2}}$ \\
        &       &                                 & $E$  &effort: $E=V/\hat{L}$\\
        &       &                                 & $B$  &error\_est\\
        &       &                                 & $T$  &prog\_time: $T=E/18$ seconds\\\cline{2-5}
\end{tabular}}
\end{center}
\caption{Static code features.}\label{fig:features}
\end{figure}
\begin{figure*}
\scriptsize
\begin{center}
\begin{tabular}{ll|l|l|r|rr@{.}l}
project & source &language & description &\# modules & features  & \multicolumn{2}{c}{\%defective}\\\hline
pc1  &NASA& C++ &flight software for earth orbiting satellites& 1,109    & 21          & 6&94\\
kc1  &NASA& C++ &storage management for ground data& 845      & 21          & 15&45\\
kc2  &NASA& C++ &storage management for ground data& 522      & 21          & 20&49\\
cm1  &NASA&C++&spacecraft instrument & 498      & 21          & 9&83\\
kc3  &NASA&JAVA &storage management for ground data& 458      & 39          & 9&38\\
mw1  &NASA&C++ &a zero gravity experiment related to combustion& 403      & 37          & 7&69\\
 ar4 &Turkish white goods manufacturer&C &refrigerator&107 &  30            & 18 & 69\\
 ar3&Turkish white goods manufacturer&C &dishwasher& 63 &    30          & 12 & 70\\
mc2  &NASA&C++ &video guidance system& 61      & 39          & 32&29\\
 ar5 &Turkish white goods manufacturer& C&washing machine& 36 &  30           & 22 & 22\\
\cline{5-5}
     \multicolumn{4}{c}{~}       & \multicolumn{1}{r}{Total: ~~ 4,102} 

\end{tabular}
\end{center}
\caption{Tables of data, sorted in order of number of examples, taken from 
\protect\url{http://promisedata.org/data}.
The rows labeled ``NASA'' come from NASA aerospace projects while the rows
labeled ``SOFTLAB'' come  from a Turkish software company writing
applications for domestic appliances.
All this data conforms to the format of
\tion{scf}.
}\label{fig:data}
\end{figure*} 


\subsubsection{Static Code Features}\label{sec:scf}
Defect predictors can be learned from tables
of data containing static code features and  whose class label is {\em defective?}
and whose values are
{\em true} or {\em false}. In those tables:
\bi
\item
Rows describes data from one {\em module}.
Depending on
the language, modules may be called ``functions'', ``methods'',
``procedures'' or ``files''. 
\item
Columns describes one
of the 
static code feature of \fig{features}. The appendix of this paper offers further details
on these features.
\ei
These static code features are collected from prior development work. The {\em defective?} class
summarizes the results of a whole host of QA methods that were applied to that historical data.
If any manual or automatic technique registered a problem with this module, then it was marked ``defective?=true''.
For these data sets, the data mining goal is to learn a binary prediction for
$defective?$  from past projects that can be applied
to future projects.

This paper argues that such defect predictors are useful and describes a novel method for improving their
performance. Lest we overstate our case, it is important to note that defect predictors learned from static
code features can only
{\em augment}, but never {\em replace}, standard QA methods. Given a limited budget for QA.
the manager's task is to decide which set of QA methods $M_1,M_2,...$ that
cost $C_1,C_2,...$ should be applied. Sometimes, domain knowledge is available that can indicate that
certain modules deserve the most costly QA methods. If so,
then some subset of the system may receive more attention by the QA team.
We
propose defect predictors as a rapid and cheap lightweight sampling policy for checking if the rest of
the system
deserves additional attention.
As argued above, such a sampling method is essential for generating high-quality systems under the constraint
of limited budgets.


\subsection{Frequently Asked Questions}
\subsubsection{Why Binary Classifications?}
The reader may wonder why we persue such a 
simple binary classification scheme ({\em defective? $\in \{true,false\}$}) and not, say, {\em number of defects} or {\em severity of defects}. In reply, we say:
\bi
\item We do not use {\em number of defects} since 
our knowledge of defects comes from a pre-release analysis. After release, many fault may be apparent. However, pre-release,
only a few of those may have been found. For example, in our data sets, 
only a vanishingly small percent of modules have more than one issue report.
\item We do not use {\em severity of defects} since 
in large scale data collections, such as those used below, it is hard
to distinguish defect ``severity'' from defect ``priority''. All too often, we have found that
developers will declare a defect ``severe'' when they are really only stating a preference
on what bugs they wish to fix next. Nikora cautions that ``without
a widely agreed upon  definition of severity, we can not reason about it''~\cite{nikora04}.
\ei
\subsubsection{Why Static Code Features?}
Another common question is why just use static code features? Fenton~\cite{fenton94} divides 
software metrics  into process, product, and personnel and uses these to 
 collect information on
how the software was built, what was built, and who built it.
Static code measures are just product metrics and, hence, do not reflect process and personnel details.
For this reason, other researchers use more that just static code measures. For example:
\bi
\item
As mentioned above, reliability engineers use knowledge of how the frequency of faults
seen in a running system changes over time~\cite{musa87,littlewood97}.
\item 
Other researchers use knowledge of the development team to comment on defect rates. For example,
Nagappan et al. comment of the effects of organizational structure on software 
quality~\cite{nach08} while 
Weyuker et al. explore the effect of large team sizes on defect rates~\cite{weyeuker08}.
\ei
When replying to this question, we say that static code features are one of the few measures we 
can collect in a consistent manner across many projects.
Ideally, data mining occurs in some
CMM level 5 company where processes and data collection is precisely defined. In that ideal
case, there exists extensive data sets collected over many projects and many years. These
data sets are in a consistent format and there is no ambiguity in the terminology of the
data (e.g. no confusion between ``severity'' and ``priority''). 

We do not work in that ideal situation. Since 1998, two of the
authors (Menzies and Cukic) have been research consultants to NASA.
Working with NASA's Independent Software Verification and Validation
Facility (IV\&V), we have tried various methods to add value to the QA
methods of that organization.  As we have come to learn,
NASA is a very dynamic organization:
\bi
\item The number of software projects
analyzed at the IV\&V facility site has grown from four per year (in 1998) to 42 per year.
\item These projects come from an
ever-changing set of sub-contractors and sub-cub-contractors.  
\item 
 The director of the IV\&V facility has changed six times, 
resulting is six 
different directions
for the facility. 
\item Meanwhile, the overall administration for the
site had changed four times:  Washington D.C. to Texas, to the west coast, to NASA Goddard.
\item Finally,
the NASA enterprise has undergone major upheavals following
the 2003 loss of the Columbia shuttle, then President Bush's new
vision for interplanetary space exploration in 2004.  
\ei
The pace of
change has not slowed down. At the time of this writing (February
2009), NASA is negotiating its next direction with the new Obama
administration and further extensive changes are expected\footnote{
This is not to say that NASA's software processes are somehow
sub-standard or out-of-control. In many areas, NASA leads the field
in innovative software QA~\cite{pressburger06,regan04}. Indeed,
we are aware of many other organizations with far less control
over their data than NASA.}.

We mention this organization history since 
the way NASA collects data on software can change whenever there is:
\bi
\item A new project;
\item A new sub-contractor; 
\item A new director; 
\item A new administration; or 
\item If there is a major
upheaval to the entire organization. 
\ei
As research consultants, we cannot precisely define and data collection in such a dynamic environment. 
Hence,
we do not
ask ``what are the right features to collect?''. Instead, we can
only ask ``what features can we access, right now?''. This question is relevant
to NASA 
as well as any organization where
data collection is not controlled by a centralized authority such as:
\bi
\item agile software projects;
\item out-soured projects;
\item open-soured projects;
\item  and organizations that make extensive use of sub-contractors and
sub-sub contractors.
\ei
In our experience, the one artifact that can usually be accessed in 
different projects is
the source code. 
These features 
can be automatically and cheaply collected, even for very large systems~\cite{nagappan05}.
By contrast, 
other methods such as manual code reviews are labor-intensive.
Depending on the review methods 8 to 20 LOC/minute can be
inspected and this effort repeats for all members of the review team,
which can be as large as four or six~\cite{me02f}. 


For all the above reasons, 
many industrial practitioners and
researchers (including ourselves) 
use static attributes to guide software 
quality predictions  
(see \cite{halstead77,mccabe76,chapman02,me04g,polyspace,nagappan05,hall00,nikora03,conf/icse/NagappanB05a,khoshgoftaar01,conf/ictai/TangK04,journals/ese/KhoshgoftaarS03,me03a,me02e,me03k,me03q,porter90,tiang95,khoshgoftaar99,srinivasan95}).
Verification and validation (V\&V) textbooks~\cite{rakitin01} advise using static code complexity attributes
to decide which modules are worthy of manual inspections.  
At the NASA IV\&V 
facility, 
we 
knows of several large government software contractors that will not
review software modules {\em unless} tools like McCabe predict that
some of them might be fault prone.  

\subsubsection{What Can be Learned from Static Code Features?}
The previous section argued that,
for pragmatic reasons, all we can often collect are
static code measures. This
is not to say that if we {\em use} those features, then they yield useful
or interesting results.
Hence, a very common question we hear about is
``what evidence is that anything
useful can be learned from static code measures?''.

There is a large body of literature arguing that static code
features are an inadequate characterization of
the internals of a function:
\bi
\item Fenton offers an insightful example where
{\em the same} functionality is achieved via {\em different}
language constructs resulting in {\em different} static
measurements for that module~\cite{fenton97}.  
Using this example, Fenton argues against the use of static code features.
\item
Shepperd \& Ince
present 
empirical evidence  that  the McCabe
static attributes offer
nothing more than
uninformative attributes like  lines of code. They comment
``for a large class of software it
(cyclomatic complexity) is no more than a proxy for, and in many cases
outperformed by, lines of code''~\cite{shepperd94}.
\item
In a similar result, Fenton~\&~Pfleeger  
note that the main McCabe's attribute
(cyclomatic complexity, or $v(g)$) 
are highly correlated with lines of code~\cite{fenton97}.
\ei
To test this pessimistic view of static code measures,
we can use them to build defect predictors.
In order to allow for repeatability, we use the publicly available data sets
of 
\fig{data}. These data sets are quite diverse and are  written in different languages
(C,C++,JAVA); written in different countries
(United Stated and Turkey);
and written for different 
purposes (control and monitoring of white goods,
NASA flight systems, ground-based software).

If static code features were truly useless, then the defect predictors learned from
\fig{data}
would:
\bd
\item[{\bf Prediction1:}] ~~~~~~~~~Perform  badly (not predict for defect);
\item[{\bf Prediction2:}] ~~~~~~~~~Would have no generality (predictors learned from one data set would not be insightful to another).
\ed
Recently~\cite{me09b} we have shown that at least for the \fig{data} data sets,
{\bf Prediction1} and {\bf Prediction2} are false~\cite{me09b}. 
Before we can show that experiment, we must first digress to define
performance measures for defect prediction. 
When such a predictor fires
then
$\{A,B,C,D\}$ denotes the
true negatives, 
false negatives, 
false positives, and 
true positives
(respectively).
From these measures we can compute:
\[
\begin{array}{ll}
pd=recall=&\frac{D}{B+D}\\
pf=&\frac{C}{A+C}\\
\end{array}
\]
In the above, $pd$ is the {\em probability of detecting} a faulty
module while $pf$ is the {\em probability of false alarm}.  
Other performance measures are
$accuracy=\frac{A+D}{A+B+C+D}$ and $precision=\frac{D}{B+D}$. 
\fig{perform} shows an example of the calculation of these measures. 
\begin{figure}
{\scriptsize 
\begin{center}
\begin{tabular}{r|r|r|r|}
\multicolumn{2}{c}{}&\multicolumn{2}{c }{module found in defect
logs?}\\\cline{3-4} \multicolumn{2}{c|}{}&no&yes\\\cline{2-4}
 signal&no &A = 395
 &B = 67\\\cline{2-4}
detected?&yes &C = 19
&D = 39\\\cline{2-4}
\end{tabular}
\begin{eqnarray}\nonumber
pf=&Prob.falseAlarm=&5\%\\\nonumber
pd=&Prop.detected=&37\%\\\nonumber
acc=&accuracy=&83\%\\\nonumber
prec=&precision=&67\%\\\nonumber
\end{eqnarray}
\end{center}}
\caption{Performance measures}\label{fig:perform}
\end{figure}

Elsewhere\cite{me07e},
we show that accuracy and precision are highly unstable performance
indicators for data sets like \fig{data} where  the target concept occurs
with relative infrequency: in \fig{data}, only $\frac{1}{7}th$ (median value) of the modules are marked
as defective. Therefore, for the rest of this paper, we will not refer to accuracy or precisions.

Having defined performance measures, we can now check {\bf Predictions1\&2}; i.e.
static defect features lead to ``bad'' fault predictors and
defect predictors have no generality between data sets. If $D$ denotes all the data in \fig{data}, and
$D_i$ denote one particular data set $D_i \in D$, then we can conduct two kinds of experiments:
\bd
\item[SELF:]  {\em Self-learning}  experiments where we {\em train} on 90\% of $D_i$ then test on the remaining
10\% of that data set. 
Note that such self-learning experiments will let us comment on {\bf Prediction1}.
\item[RR:] {\em Round-robin} experiments where
we 
{\em test} on 10\% (randomly selected) of data set $D_i$ after 
{\em training} on the remaining nine data sets $D-D_i$.
Note that such round-robin experiments will let us comment on {\bf Prediction2}.
\ed 
It turns out that the round-robin results are unimpressive due to an {\em irrelevancy effect}, discussed below.   
Hence, it is also useful to conduct
\bd
\item[RR2:] Round-robin experiments where a {\em relevancy filter} 
is used to
filtered away irrelevant parts
of the training data. 
\ed
\begin{figure}
\begin{center}
{\scriptsize
\begin{tabular}{r|l|r|r}
 &    & \multicolumn{2}{c}{median}\\\cline{3-4}
experiment & notes &pd\% & pf\%\\\hline
RR &round-robin  & 94 &68\\
RR2 &round-robin + relevancy filtering&  69 &27\\
SELF &self test& 75 &29
\end{tabular}}
\end{center}
\caption{Results of round-robin and self experiments. From~\cite{me09b}.
All the $pd$ and $pf$ results are statistically different at the 95\% level
(according to a Mann-Whitney test). 
}\label{fig:rrself}
\end{figure}
After repeating  experiments {RR, SELF, RR2} twenty times for each data set $D_i \in D$, the median results
are shown in \fig{rrself}.
At first glance, the round-robin results of RR seem quite impressive: a 98\% probability of detection. 
Sadly, these high detection probabilities are  associated
with
an
unacceptably high false alarm rate of 68\%. 

In retrospect, this high false alarm rate might have been anticipated. A
median sized data set from \fig{data} (e.g. $mw1$) has around 450 modules. In a round-robin experiment, the median
size of the training set is over 3600 modules taken from nine other projects.  In such an experiment, it is highly
likely that the defect predictor will be learned from numerous irrelevant details from other projects.

To counter the problem of irrelevant training data, the second set of round-robin experiments constructed
training sets for $D_i$ 
from the union of the 10 nearest neighbors within 
$D - D_i$. 
The RR2 results of \fig{rrself} show the beneficial
effects of relevancy filtering: false alarm rates reduced by $\frac{68}{27}=252\%$ with only
a much smaller reduction in $pd$ of $\frac{94}{69}=136\%$.


Returning now to {\bf Prediction1}, the SELF and RR2 $pd\ge69\%$ results are much larger
than those seen in industrial practice:
\bi
\item
A panel at {\em IEEE Metrics
2002}~\cite{shu02} concluded that manual software  reviews can find ${\approx}60\%$ 
of defects\footnote{That panel supported neither Fagan
claim~\cite{fagan86} that inspections can find 95\% of defects before
testing or Shull's claim that specialized directed inspection methods
can catch 35\% more defects that other
methods~\cite{shull00a}.}  
\item
Raffo found that the defect detection capability of
industrial review methods can vary from \mbox{$pd=TR(35, 50,
65)\%$}\footnote{ $TR(a,b,c)$ is a triangular distribution with
min/mode/max of $a,b,c$.}.
 for full Fagan inspections~\cite{fagan76} to
\mbox{$pd=TR(13, 21, 30)\%$} for less-structured inspections~\cite{raffo05}.
\ei
That is, contrary to {\bf Prediction1}, defect predictors learned from static code features perform 
well, relative to
standard industrial methods.

Turning now to {\bf Prediction2}, we note that
the RR2 round-robin results (with relevancy filtering) 
are close to the SELF results seen after a self-test: 
\bi
\item
 The $pd$ results are only $1-\frac{75}{69}=8\%$ different;
\item
The $pf$ results are only $\frac{29}{27}-1=7\%$ different.
\ei
That is, contrary to {\bf Prediction2}, there is generality in the defect predictions learned from static code features. Learning from
local data is clearly best (SELF's $pd$ results are better than RR2), However,
nearly the same performance results as seen in SELF can be achieved by
applying defect data from one site (e.g. NASA fight systems) to
another (e.g. Turkish white good software). 
\subsection{Summary}
For all the above reasons,  we research defect predictors based on static code features.
Such predictors are:
\bi
\item {\em Useful:} they out-perform standard industrial methods. Also, as the RR2 results show,
the predictions of these models generalize across data sets taken from
different organizations working in different countries.
\item {\em Easy to use:}
they can automatically process thousands of modules in a matter of seconds. Alternative methods such as
manual inspections are much slower (8 to 20 LOC per minute).
\item {\em Widely-used:} We can trace their use as far back as 1990~\cite{porter90}. We are also aware of hundreds of publications
that explore this method (including~\cite{weyeuker08,halstead77,mccabe76,chapman02,me04g,polyspace,nagappan05,hall00,nikora03,conf/icse/NagappanB05a,khoshgoftaar01,conf/ictai/TangK04,journals/ese/KhoshgoftaarS03,me03a,me02e,me03k,me03q,porter90,tiang95,khoshgoftaar99,srinivasan95,me07b}).
\ei
\section{Ceiling Effects in Defect Predictors}\label{sec:ceiling}
Despite several years
of exploring different learners and data pre-processing methods, the performance of our
learners has not improved. 
This section documents that ceiling effect (and the rest of this paper explores methods to break through the ceiling effect).

In 2006~\cite{me07b} we defined a
repeatable defect prediction experiment
which, we hoped, others could improve upon. That experiment used public
domain data sets and open source data miners.
Surprisingly, a simple n\aive Bayes classifiers (with some basic
pre-processor for the numerics)
out-performed the other studied methods. For details on n\aive Bayes classifiers,
see the appendix.

\begin{figure}
\begin{center}
\includegraphics[width=2.9in]{logandnom.pdf}
\end{center}
\caption{Box plot for AUC(pf,pd) seen with 9 learners
when, 100 times, a random 90\% selection of the data is  used for training and
the remaining data is used for testing.
The rectangles show the inter-quartile range (the
25\% to 75\% quartile range). The 
line shows the minimum to maximum range, unless that range extends
beyond 1.5 times the inter-quartile range (in which case dots are used
to mark these extreme outliers).
 From~\cite{jiang08a}.}\label{fig:logandnom}
\end{figure}

\begin{figure}
\begin{center}
\includegraphics[width=2.9in]{all.pdf}
\end{center}
\caption{Range of AUC(pf,pd) ranks seen in 19 learners building
defect predictors
when, 
10 times, a random 66\% selection of the data is  used for training and
the remaining data is used for testing.
In ranked data, values from one method
are replaced
by their rank in space of all sorted values (so {\em smaller} ranks means 
{\em better}
performance). In this case, the performance
value was  {\em area under the false positive vs true-positive curve}
(and larger values are better).
Vertical lines divide the results into regions where the results are 
statically similar. For example,
all the methods whose top ranks are 4 to 12
are statistically {\em
insignificantly different}.  From~\cite{lessmann09}. }\label{fig:all}
\end{figure}

We made the experiment repeatable in the hope that other researchers could
improve or refute our results. So far,   to the best of our knowledge,
no study using just  static code features
has out-performed our 2006 result.
Our
own experiments~\cite{jiang08a} found little or no 
improvement from the application of 
numerous data mining methods. \fig{logandnom} shows some of those results
using (in order, left to right)
$aode$ average one-dependence estimators~\cite{yang06}; 
$bag$ bagging~\cite{brieman96}; 
$bst$ boosting~\cite{FreSch97}; 
$IBk$ instance-based learning~\cite{cover67}; 
$C4.5$ C4.5~\cite{quinlan92}; 
$jrip$ RIPPER~\cite{cohen95r}; 
$lgi$  logistic regression~\cite{breiman84}; 
$nb$ n\aive Bayes (second from the right);
and 
$rf$ random forests~\cite{briemann01}.
These histograms show area under the curve of a pf-vs-pd curve.
To generate such a ``AUC(pf,pd)'' curve:
\bi
\item
A learner is executed multiple times on different subsets of data;
\item 
The $pd,pf$ results are collected from each execution;
\item
The results are sorted on increasing order of $pf$;
\item 
The results are plotted on a 2-D graph using $pf$ for the x-axis and $pd$ for the y-axis.
\ei
A  statistical analysis of the  \fig{logandnom} results showed that  
only  boosting
on
discretized data offers a statistically better result than 
n\aive Bayes.
However, we cannot recommend boosting: 
boosting is orders of
magnitudes slower than  n\aive Bayes;
and the median
improvement over n\aive Bayes is negligible. 

Other researchers have also failed to improve our results.
For example,  \fig{all} shows results from a study by Lessmann et al.
on
statistical differences  between 19
learners used for defect prediction~\cite{lessmann09}. 
At first glance, our preferred n\aive Bayes method  (shown as ``NB'' on the sixth line of \fig{all})
seems to perform poorly: it is ranked in the lower third of all 19 methods.
However, as with all statistical analysis,
it is important to examine not only central tendencies but also the  variance in the performance measure.
The vertical dotted lines in \fig{all} show Lessmann et al.'s statistical analysis that divided the results into regions where
all the results are significantly different: 
the performance of the top 16 methods are
statistically {\em insignificantly different} from each other (including our preferred
``NB'' method). Lessmann et.al. comment:
\begin{quote}
{\em ``Only four competitors are significantly
inferior to the overall winner (k-NN, K-start, BBF net, VP).
The empirical data
does not provide sufficient evidence to judge whether RndFor (Random Forest),
performs
significantly better than QDA  (Quadratic Discriminant Analysis)  
 or any classifier with better average
rank. }\end{quote}
In other words, Lessmann et al. are reporting a ceiling effect where a large number
of learners exhibit performance results that are indistinguishable.

\section{Breaking Through the Ceiling}\label{sec:b}
One constant in the results of \fig{logandnom} and \fig{all} is the performance {\em goal}
used in those studies: both those results assumed the goal 
of the learning was to maximize AUC(pf,pdf), i.e. the area under a $pf$-vs-$pd$ curve.
As shown below,
if we change the goal of the learning,
then we can break the ceiling effect and find better (and worse) methods for learning defect predictors
from static code measures.

Depending on the business case that funded
the data mining study, different goals may be most appropriate.
To see this, consider the typical $pf$-vs-$pd$-vs-$effort$ curve of \fig{pdpf}:
\bi
\item The $pf$,$pd$ performance
measures were defined above. 
\item
$Effort$ is the percentage of the code base found in the modules predicted
to be faulty (so if all modules are predicted to be faulty, the 100\% of the code base must be processed by
some other, slower, more expensive QA method).
\ei
For the moment, we will just focus on the $pf,pd$ plane of \fig{pdpf}. 
A perfect detector
has no false alarm rates and finds all fault modules; i.e. $pf,pd$=$0,1$. 
As shown in \fig{pdpf}, the AUC(pf,pd) can bend towards this ideal point  but may 
never reach there:
\bi
\item 
Detectors learned from past experience have to make some inductive leaps and, in doing so, make
some mistakes. That is, the only way to achieve high $pd$s is to accept some level of $pf$s.
\item
The only way to avoid false alarms is to decrease the probability that the detector
will trigger. That is, the only way to achieve low $pf$s is to decrease $pd$.
\ei
Different businesses prefer different regions of \fig{pdpf} curve:
\bi
\item Mission-critical systems are
{\em risk adverse} and may accept very high false alarm rates, 
just as long as they 
catch any
life-threatening possibility.
\item For less critical software, {\em cost adverse} managers may accept lower probabilities of detection, just as long
as they do not waste budgets on false alarms. 
\ei
That is, different businesses have different $goals$:
\bd
\item[{\bf Goal1}:] Risk adverse developments prefer high $pd$; 
\item[{\bf Goal2}:] Cost adverse developments accept mid-range $pd$, provided they get low $pf$.
\ed
Arisholm \& Briand~\cite{arisholm06} propose yet another another goal:
\bd
\item[{\bf Goal3}:] 
A 
budget-conscious team wants to know that 
if X\% of the modules are predicted to be defective, then modules contain more than X\% of the defects.
Otherwise, they argue,
the cost of generating the defect predictor is not worth the effort. 
\ed
The $effort$-based evaluation of {\bf Goal3}
uses a dimension not 
explored  by the prior work that reported ceiling effects
(Lessmann et al. or 
our work~\cite{jiang08a,jiang08b,me07b}).
Hence, for the rest of this paper, we will assess the impacts of the Arisholm \& Briand goal 
of maximizing the ``AUC(effort,pd)''. 

\subsection{Experimental Set Up}
\begin{figure}
\begin{center}
\includegraphics[width=2.5in]{rocsh.pdf}
\end{center}
\caption{$Pf$-vs-$pd$-vs-$effort$.}\label{fig:pdpf}
\end{figure}
\subsubsection{Operationalizing AUC(effort,pd)}
To operationalize {\bf goal3} from Arisholm \& Briand evaluation, we assume that:
\bi
\item
After a data miner predicts a module is defective, it is inspected by a
team of human experts. 
\item
This team correctly recognizes some subset $\Delta$  of the truly defective modules
(and
$\Delta=1$ means that the inspection teams are perfect at their task).
\item
Our goal is to maximize inspection team effectiveness;
 i.e. we   seek learners that find the $most$ number of defective modules
in the $smallest$ number of modules (measured in terms of LOC).
\ei

For Arisholm \& Briand to approve of a data miner, it must fall in the region
$pd > effort$.
The $minimum$ curve in \fig{effort} shows the 
lower boundary of this region and a ``good'' detector (according to AUC(effort,pd)) must fall
above this line.
Note that the y-axis of this figure assumes $\Delta=1$;
i.e. inspection teams  correctly recognizes all defective modules
(other values of $\Delta$ are discussed below).

\subsubsection{Upper and Lower Bounds on Performance}

It is good practice to
compare the performance of some technique against 
theoretical {\em upper} and {\em lower} bounds~\cite{cohen95}.
Automatic data mining methods 
are interesting if they out-perform manual methods. Therefore, for a {\em lower-bound} on expected
performance, we compare them against some
manual   methods proposed by Koru et.al.~\cite{koru07}:
\bi
\item
They argue that 
the relationship between module {\em size} and
{\em number of defects} is not linear, but {\em logarithmic};
i.e. smaller modules are proportionally more
troublesome. 
\item
The {\em manualUp} and {\em manualDown} curves of \fig{effort}
show the results expected by Koru et al. from
inspecting modules in increasing/decreasing order of size (respectively). 
\item
With {\em
manualUp}, all modules are selected and sorted in increasing order of size,
so that curve runs from 0 to
100\% of the LOC.  
\ei
\begin{figure}[!t]
\begin{center}
\includegraphics[width=2.25in]{plots/effort.pdf}
\end{center}
\caption{$Effort$-vs-$PD$.}\label{fig:effort}
\end{figure}
In a result consistent with Koru et.al., 
our experiments show $manualUp$ usually defeating $manualDown$
As shown in \fig{effort},
$manualUp$ scores higher on $effort$-vs-$PD$  than $manualDown$.
Hence, we define 
an {\em upper bound} on our performance as follows.
Imagine an  omniscient oracle restricted module
inspections to just the modules that are truly defective.
If {\em manualUp} is applied to just these modules, then this would show the  upper-bound
on detector performance.
For example, \fig{effort} shows this $best$ curve where 30\% of the LOC
are in defective modules.

In our experiments, we ask our learners to make a binary decision ($defective, nonDefective$).
All the modules identified as $defective$ are then sorted
in
 order of increasing size (LOC).
We then assess their performance
by AUC(effort,pd).
For example,
the $bad$ learner in \fig{effort} performs worse than the $good$ learner since the
latter has a larger area under its curve.

In order to provide an upper-bound on our AUC, we report
them
as a ratio of the area under the $best$ curve. All the performance
scores mentioned in the rest of this paper are hence {\em normalized AUC(effort,pd)}
values ranging from 0\% to 100\% of the $best$ curve.

Note that normalization simplifies our assessment criteria.
If the effectiveness of the inspection team is independent of the method
used to select the modules that they inspect then   $\Delta$ is the {\em same across all data miners}.
By expressing the value of a defect predictor as a ratio of the area under the {\em best} curve, 
this $\Delta$ cancels out so we 
can assess the relative merits of different defect predictors {\em independently} of $\Delta$.

\subsubsection{Details}

Two more  details will complete our discussion of \fig{effort}.
Defect detectors usually do not trigger on
all modules.  For example, the {\em good} curve of \fig{effort}
triggers on B=43\% of the code while only detecting 85\% of the
defective modules.  Similarly, the {\em bad} curve stops after
finding 30\% of the defective modules in 24\% of the code.  To
complete the $effort$-vs-$PD$ curve, we must fill in
the gap between the termination point  and $X=100$.  In the sequel,
we will assume that test engineers  inspect the modules referred
to by the data miner.  Visually, for the $good$ curve, this  assumption
 would correspond to
a flat line running to the right from point $C=85$ (i.e. the 85\% of
the code triggered by the learner that generated the $good$ curve). 

Secondly, the following observation will become significant when we tune
a learner to AUC(effort,pd).
Even though \fig{effort} shows $effort$-vs-$PD$, it can also indirectly
show false alarms.
Consider the plateau in the $good$ curve of \fig{effort},
marked with ``D'', at around $effort=10,PD=45$. Such plateaus mark false
alarms where the detectors are selecting modules that have no defects.
That is, to  maximize the area under an $effort$-vs-$PD$, we could assign a heavy penalty
against false alarms that lead to plateaus. 

\subsection{Initial results}
\fig{effort}'s $bad$ and $manuaUp$ curves  show 
our first attempt at applying this new evaluation bias.
These curves were  generated by   
applying $manualUp$ and the C4.5 tree learner~\cite{quinlan92}
to  one of the data sets studied by Lessmann et al.
Observe how the the automatic method performed far worse than a   manual one.
To explain this poor performance, we comment that
data miners grow their models using a search bias $B_1$, then we assess them using
a different evaluation bias $B_2$. For example:
\bi
\item
During {\em training}, a decision-tree learner may stop branching if the diversity of the instances in a 
leaf of a branch\footnote{For numeric classes, this diversity measure might  be the standard deviation of the class feature.
For discrete classes, the diversity measure might be the entropy measure used in C4.5.}
falls below some heuristic threshold.
\item 
During {\em testing}, the learned decision-tree might be tested on a variety of criteria such as Lessmann et al.'s
AUC measure or our operationalization of AUC(effort,pd).
\ei
It is hardly surprising that C4.5 performed so poorly in \fig{effort}.
C4.5 was not designed to optimize AUC(effort,pdf)
(since
$B_1$ was so  different to $B_2$).
Some 
learning schemes support
biasing the learning according to the overall goal of the system; for example:
\bi
\item The  {\em cost-sensitive learners} discussed by Elkan~\cite{elkan01};
\item The   {\em ROC ensembles} discussed by Fawcett~\cite{fawcett01}  where
the conclusion is a summation of the conclusions of the ensemble of 
ROC curves\footnote{ROC= receiver-operator characteristic curves such as Lessmann et al.'s plots of
PD-vs-PF or PD-vs-precision}, 
proportionally weighted, to
yield a new learner.
\item Our our cost curve meta-learning scheme permits an understanding of the performance of a learner
across the entire  space of pd-vs-pf trade-offs~\cite{jiang08b,me08h}.
\ei 
At best,  such biasing is only an indirect
control of the $B_1$ criteria. If the underlying criteria used to guide the search
is orthogonal to the success criteria of, say, maximizing $effort$-vs-$pd$, then cost-sensitive learning
or  ensemble combinations or cost curve meta-learning will not be able to generate a learner
that  supports that business application.
Accordingly, we decided to experiment with a new learner, called WHICH, whose internal search criteria
can be tuned to a range of goals such as AUC(effort,pd).

\section{WHICH}
%For the reader conversant with the AI literature, we remark that
%WHICH is a stochastic variant of beam search where the maximum
%height of the stack is the size of the beam.  A standard beam search
%explores a tree of options and performs cautious additions to each
%leaf (at most, only grafts one more test to the current branch).
%WHICH's original design was a non-cautious beam search that grafted
%entire sub-trees from other branches onto the current branch. On
%reflection, we realized that the the following stack structure achieves
%the same goal, while being much simpler to implement.
%
Most learners use a hard-wired search bias to grow their models. WHICH, on the other hand,
is a meta-learning scheme that uses a configurable search bias to grow its models.

For a full description of WHICH see ~\cite{milton08}\footnote{Download from
from \url{www.unbox.org/wisp/tags/which}.}.
In summary, WHICH loops over the space of
possible feature ranges, evaluating various combinations of features:
\be
\item
Data from continuous features is discretized into ``$N$'' equal width bins. We tried
various bin sizes and, for this study, best results were seen using
$N\in\{2,4,8\}$ bins of width $(max-min)/N$. 
\item
WHICH maintains a stack of feature combinations,
sorted by a customizable search  bias $B_1$ .
For this study,  WHICH used the AUC(effort,pd) criteria, discussed below. 
\item
Initially, WHICH's ``combinations'' are just each range of 
each feature. Subsequently,
they can grow to   two or more features.
\item Two combinations are picked at random, favoring those combinations 
that are ranked highly by $B_1$.
\item The two combinations are themselves combined, scored, then sorted into the stacked
population of prior combinations.
\item Go to step 4.
\ee
For the reader aware of the AI literature, we remark that WHICH is a variant of  beam search.
Rather than use a fixed beam size, WHICH uses a fuzzy beam where combinations deeper in the
stack are exponentially less like to be selected. Also, while a standard beam search just adds child
states to the current frontier, WHICH can add entire sibling branches in the search tree (these sibling
branches are represented as other combinations on the stack).

After numerous loops, WHICH returns the highest ranked combination
of features. During testing, modules that satisfy this combination are  predicted as being
``defective''. These modules are sorted 
on increasing order of size and the statistics of \fig{effort} are collected.

The looping termination criteria was set using our engineering judgment. In studies
with UCI data sets~\cite{Blake+Merz:1998}, Milton showed that 
  the score of top-of-stack condition usually stabilizes in less than 100 picks~\cite{milton08}.
Hence, to be cautious, we looped 200 times.
%This early stabilization of the top-of-stack is consistent
%with the {\em back door variable} effect discussed in the constraint
%satisfaction literature~\cite{williams03}; i.e. many domains have
%a small number of variables that control everything else.  If a
%domain has such ``back doors'' then (a)~all solutions must use them;
%(b)~all changes to the output variables will be associated with
%different ranges for the back doors; (c)~a stochastic search like
%WHICH will suffice to find them. Elsewhere, we  offer extensive
%discussions on the implications of back doors on decision making
%in software engineering~\cite{me02c,me03l}.
%

%\begin{figure}
%\begin{center}
%\includegraphics[width=2.5in]{picks.pdf}
%\end{center}
%\caption{Top-of-stack scores of the WHICH stack seen after multiple ``picks'' (selection and scoring
%of two conditions picked at random, then combined) for seven data sets from the UCI data mining repository~\cite{Blake+Merz:1998}.
%Usually, top-of-stack stabilizes after just a  dozen pick. However, occasionally,
%modest improvements are seen after a few hundred ``picks''
%(see the plot marked   with  an ``A''). }\label{fig:picks}
%\end{figure}
%

%Note that, when combining conditions, ranges from {\em different} features are joined using a {\em  conjunction} and ranges from the 
%{\em same}
%feature are joined with a {\em disjunction}. For example,  adding  $a=1$ to  \mbox{``$a=2 \wedge b=3$''} results in
%\mbox{``$(a=1 \vee a=2) \wedge b=3$''}.
%
%In the following experiment, we wanted to isolate the effect resulting from making the internal
%search bias of the leaner ($B_1$) similar to the evaluation bias $B_2$.
%Accordingly,  we ``crippled'' WHICH and disabled various internal options:
%\bi
%\item
%WHICH can optimize each combination via
%a back select that discards superfluous parts of the combination.
%\item
%The maximum stack size of WHICH can be reduced to prune the search space. For this study, that maximum size was set to
%infinity; i.e. no pruning.
%\ei
%Hence, the following results were obtained
%by a data miner that knows nothing special about over-fitting avoidance  or any other AI
%search technique. 
%The {\em only} intelligence used by WHICH to find better defect predictors
%is use of a $B_1$ search bias that was very similar to the $B_2$ evaluation criteria.

%Due to quirks in our data set,
%WHICH's search criteria $B_1$   could not directly use $effort$-vs-$PD$.
%Instead, we used a search  bias that 
%approximates maximizing $effort$-vs-$PD$,
%but does not implement it directly.
The following expression guides WHICH's search:
\begin{equation}\label{eq:pprime}\scriptsize
 B_1 = 1 - \frac{\sqrt{PD^2*\alpha + (1-PF)^2*\beta + (1-effort)^2*\gamma}}{\sqrt{\alpha+\beta+\gamma}}
\end{equation}
The $(PD,PF,effort)$ values are normalized to fall between zero and one.
The  $(\alpha,\beta,\gamma)$ terms in \eq{pprime}
model
the relative utility of $PD,PF,effort$ respectively.
These values range $0 \le \left(\alpha,\beta,\gamma\right) \le 1$.
Hence:
\bi
\item
$0 \le B_1 \le 1$; 
\item larger values of $B_1$ are better; 
\item
increasing $(effort,PF,PD)$ leads to  $(decreases, decreases, increases)$ in $B_1$ (respectively).
\ei

Initially, we gave $PD$ and $effort$ equal weights and ignored $PF$; i.e. 
\mbox{$\alpha=1, \beta=0, \gamma=1$}. 
This yielded disappointing results: the performance of the learned detectors
varied wildly across our cross-validation experiments.
%XXX needs to say what those results were. wild invariance
An examination of our data revealed why:
there exists a small number
of modules with very large LOCs. 
For example, in one data set with 126 modules, most have 
under 100 lines of code but a few of them
are over 1000 lines of code long.
The presence of small numbers of very large modules means that $\gamma=1$ is not recommended.
If the very large modules fall into a particular subset of some cross-val, then 
the performance associated with WHICH's rule can vary
unpredictably from one run to another.

Accordingly, we had to 
use $PF$ as a surrogate  measure for $effort$.
Recall from the above discussion that 
we can restrain decreases in $PD$  by  assigning a heavy penalty
to the false alarms that lead to plateaus in a $effort$-vs-$PD$ curve. 
In the following experiments, we used a $B_1$ equation that disables
$effort$ but places a very large penalty on $PF$; i.e.
\begin{equation}\label{eq:weights}
\alpha=1,\; \beta=1000,\; \gamma=0
\end{equation}
We acknowledge that the choice \eq{pprime} and \eq{weights} is somewhat arbitrary.
In defense of these decisions, we note that in the following results, these decisions
lead to a learner that significantly out-performed standard learning methods.



%\begin{figure}
%\begin{center}
%{\scriptsize
%\begin{tabular}{l|lrrrr}
%rank & treatment & wins & ties & losses  \\\hline
%1 &      WHICH-2&    1&   7&    0\\
%1 &     MICRO-20&    1&   7&    0\\
%2 &    manualUp&    0&   6&    2\\
%3 &       Bayes&    0&   5&    3\\
%4 &  manualDown&    0&   4&    4\\
%5 &      WHICH-4&    0&   3&    5\\
%6 &         C4.5&    1&   1&    6\\
%6 &      WHICH-8&    2&   0&    6\\
%7 &        RIPPER&    1&   0&    7\\
%\end{tabular}}
%\end{center}
%\caption{Mann-Whitney (99\%) analysis of the \fig{allr} results.  Each row shows
%a comparison of one treatment again the other eight.
%The rankings, shown on the left-hand-side,
%group together any treatments with the same ties+losses.
%}\label{fig:allrmann}
%\end{figure}

\subsection{Results}
\fig{allr} shows results from experimental runs with different learners
on the data sets of \fig{data}. Each run
randomized the order of the data ten times, then performed a N=3-way cross-val study
(N=3 was used since some of our data sets were quite small). For each part of the cross-val study,
pd-vs-effort curves were generated using:
\bi
\item {\em Manual methods}: manualUp and manualDown;
\item {\em Using standard data miners}: the C4.5 decision tree learner, the RIPPER rule learner, and our previously
recommended  n\aive Bayes method. For more details on these learners, see Appendices I,II, and III.
Note that these standard miners included methods that we have advocated in prior publications \cite{%
jiang07,%
me00p,%
me02g,%
me02k,%
me03q,%
me04c,%
me05d,%
me07b,%
me07e%
}. 
\item {\em Three versions of WHICH:}
This study applied several variants of WHICH. WHICH-2, WHICH-4, and WHICH-8 
discretize numeric ranges into 2,4, and 8 bins (respectively).
\item
{\em MICRO-20:} MICRO-20 was another variant motivated by the central limit theorem.
According to the central limit theorem, the sum of a large enough sample will approximately
normally distributed (the theorem explains the prevelance of the normal
probability distribution). The sample can be quite small, sometimes even as low as N=20.
Accordingly, MICRO-20 was a variant of WHICH-2 that learns from just 20+20 examples
of defective and non-defective modules (selected at random). 
\ei

\subsubsection{Overall Results}
\fig{allr} shows the results for {\em all} the  data sets of \fig{data}, combined:
\bi
\item
Each row shows the normalized AUC(effort,pdf) results for a particular learner 
over
30 experiments (10 repeats of a three-way).
These results are shown as a 
25\% to 75\% quartile range (and the  large black dot 
indicates the median score).
\item
The left-hand-side column of each row shows the results of a Mann-Whitney (95\% confidence test) of 
each row. Row $i$ has a different rank to row $i+1$ if their median scores are different and the
Mann-Whitney test indicates that the two rows have a different wins+ties results. 
See the appendix for a discussion on why the Mann-Whitney test was used on these results.
\ei

In \fig{allr}, WHICH performs {\em relatively} 
and {\em absolutely} better than
all of the other methods studied in this paper:
\bi
\item {\em Relative performance:} WHICH-2 and the MICRO-20 learner have the highest ranks;
\item {\em Absolute performance:}
In our discussion of \fig{effort}, the $best$ curve was presented as the upper bound 
in performance for any learner tackling AUC(effort,pd).
WHICH's performance rises close to this upper bound, rising to to 70.9 and 80\% (median  and 75\% percentile range) 
of the $best$ possible performance. 
\ei
\begin{figure}[!t]
\renewcommand{\baselinestretch}{1}
\begin{center}
{\scriptsize\begin{tabular}{l@{~}l@{~}l@{~}r@{~}c} 
\multicolumn{4}{c}{~}& \multicolumn{1}{c}{2nd quartile, median }\\
data &rank & treatment & median $Q'$ & \multicolumn{1}{c}{and 3rd quartile} \\\hline
all& 1 &      WHICH-2&  70.9&\boxplot{   0.0}{  52.5}{  70.9}{27}{ 100.2}\\
& 1 &     MICRO-20&  67.0&\boxplot{   0.0}{  50.0}{  67.0}{25.9}{ 100.0}\\
&2 &    manualUp&  61.1&\boxplot{   0.0}{  52.0}{  61.1}{16.4}{  99.3}\\
&3 &       n\aive Bayes&  56.8&\boxplot{   0.0}{  47.5}{  56.8}{15.6}{ 100.2}\\
&4 &  manualDown&  49.5&\boxplot{   0.0}{  43.8}{  49.5}{14.9}{ 100.5}\\
&5 &      WHICH-4&  49.2&\boxplot{   0.0}{  30.1}{  49.2}{29.6}{ 100.0}\\
&6 &      WHICH-8&  31.2&\boxplot{   0.0}{   1.7}{  31.2}{40.9}{ 100.0}\\
&6 &         C4.5&  27.6&\boxplot{   0.0}{  16.9}{  27.6}{26.3}{ 100.1}\\
&7 &        RIPPER&  21.9&\boxplot{   0.0}{  10.6}{  21.9}{26.3}{ 100.2}\\\hline
&& & & \multicolumn{1}{c}{50\%} 
\end{tabular}}
\end{center}
\caption{Results from all data sets of \fig{data}, combined from 10 repeats of a 3-way cross-val,
sorted by {\em median} $Q'$. 
Each row shows 25 to 75\% percentile range of the
 normalized AUC(effort,pdf) results
(and the  large black dot 
indicates the median score).
Two rows have different $ranks$ (in the left-hand-side column)
if 
their  median AUC scores are different and 
a Mann-Whitney test (95\% confidence) indicates that the two rows have a different wins+ties results. 
}\label{fig:allr}
\end{figure}
\begin{figure}[!t]
\renewcommand{\baselinestretch}{0.5}
\begin{center}
{\scriptsize\begin{tabular}{l@{~}l@{~}l@{~}r@{~}c} 
\multicolumn{4}{c}{~}& \multicolumn{1}{c}{2nd quartile, median }\\
data &rank & treatment & median $Q'$ & \multicolumn{1}{c}{and 3rd quartile} \\\hline
ar4 &1 &      WHICH-2&  58.6&\boxplot{  33.6}{  49.6}{  58.6}{16.4}{  78.6}\\
& 1 &  manualDown&  56.5&\boxplot{  42.5}{  45.2}{  56.5}{18.5}{  84.2}\\
& 1 &       n\aive Bayes&  56.2&\boxplot{  33.6}{  47.7}{  56.2}{18.2}{  76.6}\\
& 1 &    manualUp&  56.2&\boxplot{  32.0}{  45.7}{  56.2}{16.9}{  70.4}\\
& 1 &      WHICH-4&  49.3&\boxplot{  11.6}{  36.7}{  49.3}{24.3}{  71.9}\\
& 1 &        RIPPER&  47.3&\boxplot{   0.0}{  34.0}{  47.3}{21.8}{  87.7}\\
&2 &     MICRO-20&  49.2&\boxplot{   0.1}{  38.5}{  49.2}{17.9}{  78.6}\\
&3 &      WHICH-8&  42.6&\boxplot{   0.0}{  31.3}{  42.6}{15.3}{  66.1}\\
&3 &         C4.5&  38.8&\boxplot{   9.2}{  21.2}{  38.8}{31.2}{  67.2}\\\hline
cm1&1 &      WHICH-2&  68.1&\boxplot{   0.0}{  57.4}{  68.1}{14.1}{  81.5}\\
& 1 &     MICRO-20&  64.7&\boxplot{   0.0}{  48.9}{  64.7}{21}{  89.1}\\
& 1 &    manualUp&  59.8&\boxplot{  48.3}{  57.4}{  59.8}{7.9}{  71.5}\\
&2 &       n\aive Bayes&  52.1&\boxplot{  36.2}{  46.0}{  52.1}{13.1}{  69.2}\\
&3 &  manualDown&  47.6&\boxplot{  33.6}{  40.3}{  47.6}{9}{  60.2}\\
&4 &      WHICH-8&  11.4&\boxplot{   0.0}{   0.0}{  11.4}{26.2}{  35.6}\\
& 4 &        RIPPER&   5.8&\boxplot{   0.0}{   0.0}{   5.8}{11.5}{  24.1}\\
& 4 &         C4.5&   0.1&\boxplot{   0.0}{   0.0}{   0.1}{12.9}{  33.3}\\
& 4 &      WHICH-4&   0.0&\boxplot{   0.0}{   0.0}{   0.0}{41.2}{  69.0}\\\hline
kc1&1 &      WHICH-2&  76.0&\boxplot{  71.4}{  73.8}{  76.0}{4.2}{  81.8}\\
&1  &     MICRO-20&  75.1&\boxplot{   1.9}{  70.3}{  75.1}{5.9}{  80.1}\\
&2 &    manualUp&  67.6&\boxplot{  64.5}{  65.8}{  67.6}{3.1}{  70.0}\\
&3 &       n\aive Bayes&  61.9&\boxplot{  54.9}{  60.2}{  61.9}{2.8}{  67.7}\\
&4 &      WHICH-4&  52.9&\boxplot{   0.0}{  49.8}{  52.9}{5.4}{  60.5}\\
&5 &  manualDown&  43.3&\boxplot{  39.7}{  42.2}{  43.3}{3}{  47.7}\\
&6 &         C4.5&  27.8&\boxplot{  11.6}{  20.5}{  27.8}{11.2}{  40.1}\\
&7 &        RIPPER&  21.3&\boxplot{  10.2}{  17.3}{  21.3}{7.9}{  32.4}\\
&8 &      WHICH-8&   0.0&\boxplot{   0.0}{   0.0}{   0.0}{2}{  33.9}\\\hline
kc2&1 &      WHICH-2&  81.6&\boxplot{  65.6}{  76.0}{  81.6}{8.6}{  88.5}\\
&2 &     MICRO-20&  74.8&\boxplot{  61.1}{  71.6}{  74.8}{7.8}{  88.4}\\
&3 &    manualUp&  69.3&\boxplot{  57.9}{  65.4}{  69.3}{5.6}{  76.6}\\
&4 &      WHICH-4&  59.4&\boxplot{  43.1}{  52.5}{  59.4}{14.3}{  79.6}\\
&4 &       n\aive Bayes&  58.7&\boxplot{  47.0}{  54.8}{  58.7}{6.2}{  69.4}\\
&5  &  manualDown&  46.1&\boxplot{  37.9}{  43.1}{  46.1}{9.2}{  62.4}\\
&5  &        RIPPER&  42.2&\boxplot{  22.2}{  36.0}{  42.2}{13.5}{  65.2}\\
&6 &      WHICH-8&  41.2&\boxplot{  26.3}{  36.5}{  41.2}{11.1}{  56.5}\\
&6 &         C4.5&  41.2&\boxplot{  26.0}{  36.1}{  41.2}{9.8}{  59.8}\\\hline
kc3&1 &      WHICH-2&  87.3&\boxplot{  73.3}{  82.4}{  87.3}{8.1}{  95.4}\\
&2 &     MICRO-20&  76.3&\boxplot{  56.0}{  69.8}{  76.3}{11.6}{  94.6}\\
&3 &       n\aive Bayes&  64.2&\boxplot{  45.5}{  59.2}{  64.2}{10.4}{  75.4}\\
&3  &    manualUp&  64.2&\boxplot{  50.7}{  57.5}{  64.2}{10.6}{  77.4}\\
&4 &      WHICH-4&  47.8&\boxplot{   0.0}{  40.5}{  47.8}{18.1}{  67.2}\\
&4  &  manualDown&  47.6&\boxplot{  31.3}{  39.5}{  47.6}{16.1}{  66.8}\\
&4  &      WHICH-8&  46.7&\boxplot{   0.0}{  36.2}{  46.7}{16.5}{  62.1}\\
&5 &         C4.5&  23.1&\boxplot{   0.0}{  13.6}{  23.1}{15.3}{  42.6}\\
&5 &        RIPPER&  17.7&\boxplot{   0.0}{  13.1}{  17.7}{10.8}{  54.2}\\\hline
mw1&1 &      WHICH-2&  62.4&\boxplot{  35.8}{  57.4}{  62.4}{13.4}{  83.3}\\
&1  &  manualDown&  60.2&\boxplot{  42.8}{  52.1}{  60.2}{11.6}{  71.8}\\
&1  &     MICRO-20&  55.7&\boxplot{   0.0}{  44.1}{  55.7}{19.9}{  78.5}\\
&2 &    manualUp&  47.8&\boxplot{  37.1}{  44.0}{  47.8}{7.9}{  62.5}\\
&3 &      WHICH-4&  42.7&\boxplot{   0.0}{  25.8}{  42.7}{24}{  60.6}\\
&3 &       n\aive Bayes&  41.7&\boxplot{  19.5}{  33.1}{  41.7}{14.6}{  62.1}\\
&4 &      WHICH-8&  39.3&\boxplot{   0.1}{  35.6}{  39.3}{12}{  60.4}\\
&5 &         C4.5&  20.0&\boxplot{   0.0}{  10.0}{  20.0}{14.3}{  42.9}\\
&5  &        RIPPER&  15.8&\boxplot{   0.0}{   7.9}{  15.8}{23.3}{  49.4}\\\hline
pc1&1 &      WHICH-2&  65.0&\boxplot{   0.0}{   0.0}{  65.0}{71.1}{  81.8}\\
&1  &     MICRO-20&  64.4&\boxplot{   0.0}{  51.0}{  64.4}{17.9}{  78.6}\\
&1  &    manualUp&  60.6&\boxplot{  52.1}{  58.4}{  60.6}{5}{  71.6}\\
&2 &       n\aive Bayes&  51.5&\boxplot{  36.4}{  46.1}{  51.5}{7.3}{  60.9}\\
&3  &  manualDown&  44.6&\boxplot{  32.3}{  41.9}{  44.6}{4.3}{  55.3}\\
&4 &      WHICH-8&  22.6&\boxplot{   0.0}{   9.1}{  22.6}{21.6}{  47.7}\\
&4  &         C4.5&  19.2&\boxplot{   3.1}{  12.5}{  19.2}{12.1}{  41.5}\\
&4  &        RIPPER&  15.1&\boxplot{   0.0}{  11.0}{  15.1}{12.2}{  30.8}\\
&4  &      WHICH-4&   0.0&\boxplot{   0.0}{   0.0}{   0.0}{50.3}{  59.0}\\\hline
&& & & \multicolumn{1}{c}{50\%} 
\end{tabular}}
\end{center}
\caption{Seven examples of pattern \#1: WHICH-2 ranked \#1 {\em and} has highest median.
This figure is reported in the same format as \fig{allr}.
}\label{fig:bands1}
\end{figure}

%XXXX why 10*3
% XXX from  the perspective of different proponents

\begin{figure}[!t]
\renewcommand{\baselinestretch}{1}
\begin{center}
{\scriptsize\begin{tabular}{l@{~}l@{~}l@{~}r@{~}c} 
\multicolumn{4}{c}{~}& \multicolumn{1}{c}{2nd quartile, median }\\
data &rank & treatment & median $Q'$ & \multicolumn{1}{c}{and 3rd quartile} \\\hline
ar3 &1 &  manualDown&  54.7&\boxplot{   0.0}{  40.0}{  54.7}{39.3}{ 100.5}\\
&1  &    manualUp&  52.6&\boxplot{   0.0}{  26.0}{  52.6}{34.3}{  99.3}\\
& 1 &         C4.5&  47.8&\boxplot{   0.0}{   0.1}{  47.8}{59.1}{ 100.0}\\
&1 &      WHICH-8&  42.7&\boxplot{   0.0}{   0.1}{  42.7}{61.6}{ 100.0}\\
&1 &      WHICH-2&  40.4&\boxplot{   0.0}{  20.6}{  40.4}{31.1}{ 100.2}\\
&2 &      WHICH-4&  41.8&\boxplot{   0.0}{  24.4}{  41.8}{28}{  89.2}\\
& 2 &     MICRO-20&  38.0&\boxplot{   0.0}{   0.4}{  38.0}{54.1}{  77.2}\\
&3 &       n\aive Bayes&  34.4&\boxplot{   0.0}{   0.4}{  34.4}{42.3}{  60.8}\\
&4 &        RIPPER&   0.2&\boxplot{   0.0}{   0.0}{   0.2}{35.5}{  64.1}\\\hline
ar5&1 &     MICRO-20&  77.6&\boxplot{  31.6}{  49.9}{  77.6}{37.2}{ 100.0}\\
& 1 &      WHICH-4&  71.4&\boxplot{   0.2}{  51.1}{  71.4}{32.1}{ 100.0}\\
& 1 &  manualDown&  69.6&\boxplot{  41.3}{  51.0}{  69.6}{30.5}{ 100.5}\\
& 1 &      WHICH-2&  67.6&\boxplot{   0.0}{  44.2}{  67.6}{36.2}{ 100.0}\\
& 1 &         C4.5&  56.1&\boxplot{   0.1}{  35.8}{  56.1}{34.7}{ 100.1}\\
& 1 &        RIPPER&  55.0&\boxplot{   0.0}{   0.2}{  55.0}{73.5}{ 100.2}\\
& 1 &       n\aive Bayes&  54.1&\boxplot{  24.3}{  42.7}{  54.1}{34.8}{ 100.2}\\
&2 &    manualUp&  56.5&\boxplot{   2.0}{  24.1}{  56.5}{39.5}{  80.9}\\
&3 &      WHICH-8&   0.0&\boxplot{   0.0}{   0.0}{   0.0}{31.1}{ 100.0}\\
\hline
&& & & \multicolumn{1}{c}{50\%} 
\end{tabular}}
\end{center}
\caption{Two examples of pattern \#2: While WHICH-2 did not achieve the highest medians,
it was still ranked \#1 compared to eight other methods.
This figure is reported in the same format as \fig{allr}.
}\label{fig:bands2}
\end{figure}

\begin{figure}[!t]
\renewcommand{\baselinestretch}{1}
\begin{center}
{\scriptsize\begin{tabular}{l@{~}l@{~}l@{~}r@{~}c} 
\multicolumn{4}{c}{~}& \multicolumn{1}{c}{2nd quartile, median }\\
data &rank & treatment & median $Q'$ & \multicolumn{1}{c}{and 3rd quartile} \\\hline
mc2&1 &    manualUp&  74.3&\boxplot{  63.3}{  70.9}{  74.3}{7.4}{  80.4}\\
&2 &     MICRO-20&  57.1&\boxplot{   0.0}{   6.3}{  57.1}{61.5}{  81.7}\\
&2  &       n\aive Bayes&  55.9&\boxplot{  21.4}{  46.6}{  55.9}{12.5}{  79.1}\\
&3 &         C4.5&  43.7&\boxplot{  21.9}{  29.3}{  43.7}{26.1}{  69.7}\\
&3  &  manualDown&  42.8&\boxplot{  29.7}{  38.1}{  42.8}{9.1}{  57.4}\\
&4 &        RIPPER&  28.5&\boxplot{  12.7}{  17.0}{  28.5}{18.2}{  56.4}\\
&5 &      WHICH-8&  21.9&\boxplot{   0.0}{  11.2}{  21.9}{16.2}{  42.4}\\
&6 &      WHICH-4&   5.6&\boxplot{   0.0}{   0.0}{   5.6}{25.3}{  47.9}\\
&6  &      WHICH-2&   0.0&\boxplot{   0.0}{   0.0}{   0.0}{40.8}{  99.7}\\
\hline
&& & & \multicolumn{1}{c}{50\%} 
\end{tabular}}
\end{center}
\caption{The only example of pattern \#3:  WHICH-2 loses (badly) but  MICRO-20 still ranks high.
This figure is reported in the same format as \fig{allr}.}\label{fig:bands3}
\end{figure}


Several other results from \fig{allr} are noteworthy.
\bi
\item
There is no apparent benefit in detailed discretization: WHICH-2 outperforms WHICH-4 and WHICH-8.
\item
In a result consistent with our prior publications~\cite{me07b},  our n\aive Bayes
classifier
out-performs other standard data miners (C4.5 and RIPPER).
\item
In a result consistent with Koru et.al.'s logarithmic defect hypothesis,
manualUp defeats manualDown. 
\item
In \fig{allr}, standard data miners are defeated by a manual method (manualUp). 
The size of the defeat is very large: median values of 61.1\% to 27.6\% from manualUp to C4.5.
\ei
This last result is very sobering.
In \fig{allr}, two widely used methods (C4.5 and RIPPER) are defeated by manualDown; i.e. by a
a manual inspection method that Koru et al. would argue is the {\em worst} possible inspection policy.
These results calls into question the numerous prior defect prediction results,
including several papers written by the authors
\cite{%
jiang07,%
me00p,%
me02g,%
me02k,%
me03q,%
me04c,%
me05d,%
me07b,%
me07e%
}. 

%data mining technology. performs very well, defeating 
\subsubsection{Individual Results}
\fig{allr} combines results from all data sets.
Figures \ref{fig:bands1},
\ref{fig:bands2}, and
\ref{fig:bands3} 
look at each data set in isolation. 
The results divide into three patterns:
\bi
\item In the eight data sets of pattern \#1 (shown in \fig{bands1}),
WHICH-2 has {\em both} the highest median $Q'$ performance 
{\em and} is found to be in the top rank by the Mann-Whitney statistical analysis.
\item
In the two data sets of pattern \#2 (shown in \fig{bands2}),
WHICH-2 does not score the highest median performance, but still
is found in the top-rank.
\item
In the one data set that shows pattern \#3 (shown in \fig{bands3}),
WHICH-2 is soundly defeated by manual methods (manualUp).
However, in this case, the WHICH-2 variant MICRO-20 falls into the second rank
\ei
In summary, when looking at each data set in isolation, WHICH performs very well
in $\frac{9}{10}$ of the data sets. 

% Reminder: the "draftcls", not "draft", class option should be used if
% it is desired that the figures are to be displayed while in draft mode.

% An example of a floating figure using the graphicx package.
% Note that \label must occur AFTER (or within) \caption.
% For figures, \caption should occur after the \includegraphics.
%
%\begin{figure}
%\centering
%\includegraphics[width=2.5in]{myfigure.eps}
%\caption{Simulation Results}
%\label{fig_sim}
%\end{figure}


% An example of a double column floating figure using two subfigures.
% (The subfigure.sty package must be loaded for this to work.)
% The subfigure \label commands are set within each subfigure command, the
% \label for the overall fgure must come after \caption.
% \hfil must be used as a separator to get equal spacing
%
%\begin{figure*}
%\centerline{\subfigure[Case I]{\includegraphics[width=2.5in]{subfigcase1.eps}
%\label{fig_first_case}}
%\hfil
%\subfigure[Case II]{\includegraphics[width=2.5in]{subfigcase2.eps}
%\label{fig_second_case}}}
%\caption{Simulation results}
%\label{fig_sim}
%\end{figure*}



% An example of a floating table. Note that, for IEEE style tables, the
% \caption command should come BEFORE the table. Table text will default to
% \footnotesize as IEEE normally uses this smaller font for tables.
% The \label must come after \caption as always.
%
%\begin{table}
%% increase table row spacing, adjust to taste
%\renewcommand{\arraystretch}{1.3}
%\caption{An Example of a Table}
%\label{table_example}
%\centering
%% The array package and the MDW tools package offers better commands
%% for making tables than plain LaTeX2e's tabular which is used here.
%\begin{tabular}{|c||c|}
%\hline
%One & Two\\
%\hline
%Three & Four\\
%\hline
%\end{tabular}
%\end{table}

\subsection{External Validity}

We argue that the data sets used in this paper are far broader (and hence, more
externally valid)
than seen in prior defect
prediction papers. All the data sets explored by Lessmann et al.~\cite{lessmann09} and
our prior work~\cite{me07b} come from NASA aerospace applications. Here, 
we use that data, plus three extra data sets from SOFTLAB, a Turkish company writing software controllers
for dishwashers (ar3), washing machines (ar4) and refrigerators (ar5).
The development practices from these two organizations are very different:
\bi
\item The SOFTLAB software was built in a profit- and 
revenue-driven commercial organization, whereas NASA is a cost-driven government entity
\item The SOFTLAB software was developed by very small teams (2-3 people) working in the same
physical location while the NASA
software was built by much larger team spread around the United States.
\item The SOFTLAB development was carried out in an ad-hoc,
informal way rather than the formal, process oriented approach used
at  NASA.
\ei
Our general conclusion,  that
WHICH is preferred to other methods for $applciation_x$, holds for $\frac{6}{7}$ 
of the NASA data sets and $\frac{3}{3}$ of the SOFTLAB sets.
The fact that the same result
holds  for such radically different organizations
is a strong argument for the external validity of our results.


While the above results, based on ten data sets,
 are no promise of the efficacy of WHICH on future data sets,
these results are  strong evidence that, when a learner is assessed using AUC(effort, pd), then:
\bi
\item Of all the learners studied here, WHICH or MICRO-20 is preferred over other learners;
\item Standard learners such as n\aive Bayes, the RIPPER rule learner, and the C4.5 decision tree learner
perform much worse than simple manual methods. Hence, we must strongly deprecate their use
when optimizing for AUC(effort,pd).
\ei


\section{Conclusion}
Given limited QA budgets, it is not possible to apply the most effective QA method  to all parts
of a system. The manager's job is to decide  needs to be tested most, or tested least.
Static code defect predictors are one method for auditing those decisions. 
Learned from historical data,
these
detectors can check which parts of the system deserve more QA effort.

Defect predictors learned from static code measures  are {\em useful}, 
{\em easy  to use}, and are {\em widely-used}:
\bi
\item
{\em Useful:} They out-perform standard industrial methods.  Also, 
the predictions of these models generalize across data sets taken from
different organizations working in different countries.
\item
{\em Easy to use:}
They
can automatically process thousands of modules in a matter of seconds while alternative methods such as
manual inspections are much slower (8 to 20 LOC per minute).
\item {\em Widely-used:} We can trace their use as far back as 1990~\cite{porter90}. We are also aware of hundreds of publications
that explore this method (including~\cite{weyeuker08,halstead77,mccabe76,chapman02,me04g,polyspace,nagappan05,hall00,nikora03,conf/icse/NagappanB05a,khoshgoftaar01,conf/ictai/TangK04,journals/ese/KhoshgoftaarS03,me03a,me02e,me03k,me03q,porter90,tiang95,khoshgoftaar99,srinivasan95,me07b}).
\ei
Based on our own results, and those of Lessmann et al., it seems natural to conclude that many learning
methods have equal effectiveness at learning defect predictors from static code features.
In this paper, we have shown that this {\em ceiling effect} is specific to the AUC(pf,pd) performance gal.
When
defect predictors are
assessed by other criteria such as ``read less, see more defects'' (i.e. AUC(effort,pd)),
then the selection
of the appropriate learner becomes critical:
\bi
\item
A learner tuned to ``read less, see more defects''
performs best;
\item
A simple
manual analysis  out-performs certain standard learners (NB, C4.5, RIPPER).
\ei
Therefore, our conclusion is that  knowledge of the {\em goal} of the learning
can and should be used to select
a preferred learner for a particular domain. The WHICH meta-learning framework is one method
for quickly customizing a learner to different goals.


\section{Future Work}
We hope that this  result prompts a new cycle of defect prediction research
focused on selecting the {\em best} learner(s) for {\em particular} business goals.
In particularly, based on this paper, we now caution that it is an open and urgent
question whether or not many of our learners perform not better than simple
manual methods.

As to other future work, it would be fruitful to extend the WHICH learner.
WHICH is a new learner with scope for much future experimentation:
\bi
\item Should the number of loops be set dynamically? 
\item
Do
different discretization policies improve WHICH? 
\item
Are there better values 
for $(\alpha,\beta,\gamma)$ than \eq{weights}?
\ei
It is possible that answers to these and  other questions could improve
WHICH's performance, but that is not the point of this paper.  To
comment on the generality of Lessmann et al.'s result, we only needed
to show one example where knowledge of the evaluation biases alters
which learner ``wins'' a comparative evaluation study. The current
version of WHICH offers that example.

Finally, the above study only explored AUC(effort,pd). As discussed in \tion{b}, optimizing
AUC(effort,pd) is only one possible goal of a defect predictor. It could be insightful to
explore other goals.
\bibliographystyle{IEEEtran}
\bibliography{refs}
\appendix
\section*{Learners Used in This Study}
\noindent
WHICH, $manualUp$, and $manualDown$ was described above.
The other learners used in this study come from the WEKA toolkit~\cite{witten05} and are described below.

Naive Bayes classifiers, or NB,
offer a relationship between  fragments of evidence $E_i$,
a prior probability for
a posteriori  probability
an hypothesis given some evidence
$P(H|E)$; and  
a class hypothesis $P(H)$ probability (in our case, we have two hypotheses: $H\in \{defective,nonDefective\}$).
The relationship comes from Bayes Theorem: 
$P(H|E)= \prod_iP(E_i|H) \frac{P(H)}{P(E)}$
%For example, in our data sets, there are two hypotheses: modules are either
%defective or note; i.e. \mbox{$H\in {defective,nonDefective}$}.
%Also, if a particular module has $numberofSymbols=27$ and
%$LOC=40$ and was previously classified
%as ``defective'' then
%\[
%\begin{array}{lcl}
%E_1&:& numberOfSymbols=27\\
%E_2& :& LOC=40
%\end{array}
%\]
%When building defect predictors,
%the
%posterior probability of each class (``defective'' or ``defect-free'')
%is calculated, given the features
%extracted from a 
%module.
%So, if a data set has 100 modules and 25 of them are faulty, then:
%\[P(defective)=0.25\]
%When testing new data, a module is assigned to the class
%with the higher probability, calculated from \eq{bayes}.
%
For
numeric features, 
a feature's mean $\mu$ and standard deviation $\sigma$ are used in
a
Gaussian  probability
function~\cite{witten05}:
$f(x) =
1/(\sqrt{2\pi}\sigma)e^{-\frac{(x-\mu)^2}{2\sigma^2}}$. 
Simple  naive Bayes classifiers are called ``naive'' since they assume
independence of each feature. 
Potentially, this is a significant problem for data sets where
the static code measures are highly correlated (e.g. the number of
symbols in a module increases linearly with the module's lines of code). 
However, Domingos and Pazzini have shown theoretically
that the independence assumption is a problem in a vanishingly small percent
of cases~\cite{domingos97optimality}. 
This result
explains (a)~the repeated
empirical result that, on average, seemingly n\aive Bayes classifiers perform as well
as other seemingly more sophisticated schemes (e.g. see Table~1 in~\cite{domingos97optimality});
and
(b) our prior experiments where naive Bayes did not perform
worse than other learners that continually re-sample the data for dependent
instances (e.g. decision-tree learners like C4.5 that recurse
on each ``split'' of the data~\cite{quinlan92}).

This study used J48~\cite{witten05}, a JAVA port of Quinlan's C4.5 decision tree learner
C4.5, release 8~\cite{quinlan92}.
C4.5 is  a {\em   iterative dichotomization algorithm} that seek the best attribute 
value {\em splitter} that most simplifies the data that falls into the different splits. Each 
such splitter becomes a root of a tree. Sub-trees are generated by calling iterative 
dichotomization recursively on each of the splits. 
C4.5 is defined for discrete 
class classification and uses an information-theoretic measure to describe the diversity 
of classes within a data set. 
A leaf generated by C4.5 stores the most frequent class seen during training. During test,
an example falls into one of the branches in the decision tree and is assigned the class from
the leaf of that branch.
C4.5 tends to produce big ``bushy'' trees so the algorithm includes a {\em pruning} step.
Sub-trees are eliminated if their removal does not greatly change the error rate of the tree.


JRip is a JAVA port of the RIPPER~\cite{cohen95r}  {\em rule-covering} algorithm.
One rule is learned at each pass for one  class.
All the examples that satisfy the rule condition
are marked as {\em covered} and are removed from
the data set. The algorithm then recurses on the remaining data. 
JRip takes a rather unique stance to rule generation and has operators
for 
{\em pruning}, {\em description length} and {\em rule-set
optimization}
For a full description of these techniques, see\cite{dietterich97}.
In summary,
after building a {\em rule}, RIPPER performs a back-select to see what parts of a {\em condition}
can be pruned, without degrading the performance of the rule.
Similarly,
after building a {\em set of rules}, RIPPER tries pruning away some of the rules.
The learned rules are built while minimizing  their {\em description length};
the size of the learned rules,
as well as a measure of the rule errors. 
Finally, after building rules, RIPPER
tries
replacing 
straw-man alternatives (i.e. rules grown very quickly by some
naive method).
\section*{Details on Static Code Features}
This section offers some details on the Halstead and Mccabe features.

The Halstead features were derived by Maurice Halstead in 1977. He
argued that modules
that are hard to read are more likely to be fault
prone~\cite{halstead77}. Halstead estimates reading complexity by
counting the number of operators and operands in a module: see the
$h$ features of \fig{features}.  These three raw $h$  Halstead
features were 
then used to compute the $H$: the eight derived Halstead features
using the equations shown in
\fig{features}.  In between the raw and derived Halstead features are
certain intermediaries:
 \bi
\item
$\mu= \mu_1 + \mu_2$;
\item
minimum operator count: $\mu_1^*=2$;
\item
$\mu_2^*$  is the minimum operand count (number of module parameters).
\ei

An alternative to the Halstead features 
are the complexity features proposed by Thomas McCabe in 1976.
Unlike Halstead,
McCabe
 argued that the complexity of
pathways {\em between} module symbols are more insightful than just a count of the symbols~\cite{mccabe76}. 
The Mccabe measures are defined as follows.
\bi
\item
A
module is said to have a {\em flow graph}; i.e. a directed graph where each node corresponds to a
program statement, and each arc indicates the flow of control from
one statement to another.
\item
The {\em cyclomatic complexity} of a module is   $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}.
\item
The {\em essential complexity}, ($ev(G)$) of a module is  the extent to which a
flow graph can be ``reduced'' by decomposing all the subflowgraphs
of $G$ that are {\em D-structured primes}
(also sometimes referred to as ``proper one-entry
one-exit subflowgraphs''~\cite{fenton96}). $ev(G) = v(G) - m$ where $m$ is the number of subflowgraphs of
$G$ that are D-structured primes~\cite{fenton96}.
\item
Finally, the
{\em design complexity}   ($iv(G)$) of a module is the cyclomatic complexity of a
module's reduced flow graph.
\ei
\section*{Choice of Statistical Test}

For several reasons, this study uses the Mann Whitney test.
Firstly,
many authors, including Demsar~\cite{demsar06}, remark that ranked  statistical tests such as Mann-Whitney
are 
not susceptible to errors caused by non-Gaussian performance distributions. Accordingly,
we do not use t-tests since they make a Gaussian assumption.


Also, recall that \fig{effort} shows the results of a two-stage process: first, select some detectors;
second, rank them and watch the $effort$-vs-$pd$ curve grow as we sweep right across
\fig{effort}   
(this two-stage process is necessary to baseline the learners against $manualUp$ and $manualDown$,
as well as allowing us to express the results as the ratio of a $best$ curve).
The second stage of this process violates the paired assumptions of, say, the Wilcoxon tests since
different test cases may appear
depending on which modules are predicted to be defective.
Accordingly, we require
a non-paired test like Mann Whitney to compare distributions (rather than pairs of treatments applied
to the same test case).

Further, while much has been written of the inadequacy of other statistical tests~\cite{demsar06,huang05},
to the best of our knowledge, there is no current negative critique of Mann Whitney as
a statistical test for data miners.

Lastly, unlike some other tests (e.g. Wilcoxon), Mann-Whitney does not
demand that the two compared populations are of the same size.
Hence, it is possible to run one test that compares each row of \fig{bands1} to every other row in the same division. This simplifies the presentation of the results (e.g. avoids the need for a display of, say,
the  
Bonferroni-Dunn test shown in Figure 2 of Demsar~\cite{demsar06}).


\end{document}
 that's all folks
