%\documentclass[onecolumn,draftcls,journal,compsoc]{IEEEtran}
%\documentclass[technote]{IEEEtran}
\documentclass[twocolumn,technote,9pt,compsoc]{IEEEtran}
\usepackage{graphicx}
\usepackage{wrapfig,url,times}
\newcommand{\boxplot}[5]{
	\begin{picture}(100,10)
		\put(0,0){\line(0,1){8}}
		\put(100,0){\line(0,1){8}}
		\put(#1,4){\line(1,0){#2}}
		\put(#3,4){\circle*{6}}
		\put(#4,4){\line(1,0){#5}}
		\put(50,0){\line(0,1){8}}
	\end{picture}
}
\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.80}{\fontsize{5cm}{5cm}\selectfont{Draft v5}}}}}
%\makeatother
%
\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{\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}}

\usepackage{times}
\usepackage{alltt}
\usepackage{url}
% IEEE Computer Society needs nocompress option
% requires cite.sty v4.0 or later (November 2003)
\usepackage[nocompress]{cite}
% normal IEEE
 % \usepackage{cite}

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


\title{Limits of Learning  Defect Predictors}

%\author{Tim~Menzies,~\IEEEmembership{Member,~IEEE,}
%Burak Turhan,
%		Gregory~Gay,
%       and~Ayse Bener\thanks{Dr. Menzies and Mr. Gay are with the Lane Department of Computer Science and Electrical Engineering, West Virginia
%University.
%Emails: \protect\url{tim@menzies.us},
%\protect\url{jdistefano@ismwv.com}.
%}
%\thanks{Mr. Turhan and Dr. Bener are with the Department of Computer Engineering, Bogazici University, Turkey.
%Emails:
%\protect\url{turhanb boun.edu.tr},
%\protect\url{bener@boun.edu.tr}.
%}\thanks{The research described in this paper
%was supported by
%Bogazici University research fund      under grant number BAP-06HA104
%and at
%West Virginia  University
%under grants with NASA's Software Assurance Research Program.
%Reference herein to any specific commercial product, process, or service
%by trademark, manufacturer, or otherwise, does not constitute or imply
%its endorsement by the United States Government.
%}\thanks{See 
%See \protect\url{http://menzies.us/pdf/overunder.pdf} for an earlier draft of this paper.
%Manuscript received October 1, 2007; revised XXX,}} 

\markboth{Journal of ???,~Vol.~6, No.~1, January~2007}%
{Menzies \MakeLowercase{\textit{et al.}}: Limits of Learning Defect Predictors}
\begin{document}
\maketitle

\begin{abstract}

\end{abstract}



\section{Introduction}

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. 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.


One such lightweight sampling policy is the
use of {\em fault predictors}. To learn such prediction models,
either from projects previously developed in the same environment or
from a continually expanding base of current project's artifacts,
tables of examples are formed where one column has a boolean value
for ``faults detected'' and the other columns describe software
features such as (i)~lines of code, (ii)~number of unique
symbols~\cite{halstead77}, or (iii)~max. number of possible
execution pathways~\cite{mccabe76}. Each row in the table holds data
from one ``module''; i.e. the  unit of functionality. Depending on
the language, modules may be called ``functions'', ``methods'',
``procedures'' or ``files''. The data mining task is to find
combinations of  features that predict for the value in the defects
column.  Once such combinations are found, managers can use them to
determine where to best focus their QA effort. Better yet, if they
have already focused their QA effort on the most critical portions
of the system, the detectors can ``nudge'' them towards areas that
are also in need of quality improvement.


For many years we relied upon straightforward application of data mining algorithms
 to learn quality predictors
from the artifacts  generated by a software project; see  
\cite{%
chen05,%
come96,%
dekhtyar04,%
fea02a,%
hameph95,%
hame93,%
hame94,%
jiang07,%
lum06,%
me00e,%
me00p,%
me00u,%
me02c,%
me02f,%
me02g,%
me02k,%
me02l,%
me02n,%
me03c,%
me03h,%
me03i,%
me03j,%
me03k,%
me03n,%
me03q,%
me03r,%
me04a,%
me04c,%
me04g,%
me04h,%
me05a,%
me05c,%
me05d,%
me06a,%
me06d,%
me06e,%
me06f,%
me07b,%
me07e,%
me07f,%
Ramakrishnan1995,%
RamMe1996%
}.


Standard verification and validation (V\&V) textbooks
\cite{rakitin01} advise using static code complexity attributes to
decide which modules are worthy of manual inspections. For several
years, the PIs have worked on-site at the NASA Independent software
Verification and Validation facility where large government software
contractors won't review software modules {\em unless} tools like
the McCabe static source code analyzer predicts that they exhibit
high code complexity measures.

Nevertheless, static code attributes are hardly a complete
characterization of the internals of a program module. Fenton offers
an insightful example where {\em the same} functionality is achieved
using {\em different} programming language constructs resulting in
{\em different} static measurements for that module~\cite{fenton97}.
Fenton uses this example to argue the uselessness of static code
attributes for fault prediction.

An {\em alternative interpretation} of Fenton's example is that
static attributes can never be a certain indicator of the presence
of a  fault.  Nevertheless, they are useful as probabilistic
statements that the frequency of faults tends to increase in code
modules that trigger the predictor.

Shepperd~\&~Ince and Fenton~\&~Pfleeger might reject the {\em
alternative interpretation}. They present empirical evidence  that
the McCabe static attributes offer nothing more than uninformative
attributes that are mostly the derivatives of the lines of code.
Fenton~\&~Pfleeger note that the main McCabe's attribute (cyclomatic
complexity, or $v(g)$) is highly correlated with lines of
code~\cite{fenton97}. Also, Shepperd~\&~Ince remark that ``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}.

If Shepperd \& Ince and Fenton \& Pfleeger are right, then
%\bi\item
%Learning from just lines of code should do as well as anything else;
%\item
the performance of  predictors learned by  data mining static code
features should be poor. However, this is not true, at least for the
NASA code we have
studied~\cite{me07e,me07b,me04g,me04c,me03q,me03k,me02l,me02g,me02e,jiang07}.
Using NASA data, our fault prediction models find defect
predictors~\cite{me07b} with a probability of detection ($pd$) and
probability of false alarm ($pf$) of $mean(pd,pf)=(71\%,25\%)$.
These values can be best understood via a comparison against known
industrial baselines \cite{fagan86, shu02}.

The research work referenced above has produced useful results.
However, there is much room for improvement; e.g. probabilities of
detection reported in recent repeatable studies, should not only be
achievable on a regular basis but improved.

It has proved difficult to achieve those improvements. In our
January 2007 TSE study~\cite{me07b} we set out to define a
repeatable experiment in learning defect  predictors. The intent of
that work was to offer a benchmark in defect prediction that other
researchers could repeat/ improve/ refute. That experiment included:
\bi
\item
Public domain data sets (from the the PROMISE
repository\footnote{\url{http://promisedata.org/repository}});
\item
Open source data mining
tools (the WEKA toolkit~\cite{witten05});
\item
Repeated  randomization of the  order of training data (to avoid
order effects);
\item
10-way cross-validation (to assess the results via data {\em not} used in training);
\item
Learning via multiple types of machine learning algorithms (rule
learners, decision tree learners, Bayes classifiers);
\item
Assessment via multiple criteria such as probability of detection ($pd$),
probability of false alarm ($pf$), and $balance$ that combines $\{pd,pf\}$ ;
\item
Statistical hypothesis tests over the assessment criteria;
\item
Novel visualization methods for the results;
\item
Feature subset selection to find the most important subset of the static code
features;
\ei

Since that study, we have tried to find  better data mining
algorithms for defect prediction. To date, we have failed. Our
recent (as yet, unpublished) experiments have found no additional
statistically significant improvement from the application of the
following data mining methods: logistic regression; average
one-dependence estimators~\cite{webb05}; under- or
over-sampling~\cite{drummond03} random forests~\cite{breiman01},
RIPPER~\cite{cohen95r}, J48~\cite{quinlan92}, OneR~\cite{holte93}
and bagging~\cite{brieman96}. Only boosting~\cite{FreSch97} on
discretized data offers a statistically better result than a Bayes
classifier. However, we cannot recommend boosting: the median
improvement is quite negligible and  boosting is orders of
magnitudes slower than a simple Bayes classifier.

Other researchers have also failed to improve our results. For the
past four years, we participated in the PROMISE workshop on
repeatable software engineering experiments. The rule of that
workshop reauires that if  a paper offers an empirical conclusion,
then it must also offer the data used to reach the conclusions. That
data is stored on-line in the PROMISE repository, which we
administer and maintain for the PROMISE community. Our work on that
web site, plus our interaction with the PROMISE community, gives us
a unique insight into the empirical analysis as well as access to,
as yet, unpublished results. Consequently, we are aware of studies
by other researchers (currently under review) that tried 25 other
data mining methods in fault prediction experiments. Those studies
investigated the statistical difference of the results from 25
learners on the same datasets using the Wilcoxon signed ranked
test~\cite{wilcoxon45}. The Bayesian method discussed above ties in
first place along with 15 other methods.


How can we  explain all these failed attempts to improve fault
prediction models in repeatable experiments using same (PROMISE)
data sets? One possibility is that all these experiments use
simplistic static code features such as lines of code, number of
unique symbols in the module, etc. We agree with Shepperd \& Ince
and Fenton \& Pfleeger that such simplistic static code features are
hardly a complete characterization of the internals of a module.
Static code features might be best described having {\em limited
information content}, with two properties. Firstly, they can be
quickly and completely discovered by even simple Bayesian
classifiers. Secondly, more sophisticated methods will discover no
further information.


Based on all that work we make the following assertion:
\begin{quote} 
{\em There has been 
\underline{too much} emphasis on machine learning, and 
\underline{too little} attention
on the use of specific software engineering knowledge.}
\end{quote}
Decades of AI research into data mining have resulted
in automatic and rapid methods, which can be easily applied to the learning of software 
quality predictors.  While the current generation of detectors are demonstrably 
useful and better than current
industrial best practice~\cite{me06d,me07b}, we believe that these AI methods 
have hit a {\em performance ceiling};
i.e., some inherent upper bound on the amount
of information offered by, say, static code features when identifying modules which contain faults.
Hence,  we doubt that better quality predictors can be found just by trying better machine 
learning methods.

\section{Validation of Limited Information Content}
We  have made two tests of this {\em limited information}
conjecture. {\em Test one} checked how {\em little}
information was required to learn a defect predictor. 
{\em Test
two} augmented the static code features with other features.
In {\em test one}, fault predictors were learned from
\mbox{$N\in\{100, 200, 300,...\}$} instances  then $Test$ed on another 100
instances. For each $N$, 10 experiments were performed where
training was conducted on $Train=90\%*N$ instances. For all
experiments, the $N,Train,Test$ instances were selected at random.

\begin{figure}[t]
\noindent
\includegraphics[angle=90,width=2in]{incrementalPC5.pdf}\newline
\includegraphics[angle=90,width=2in]{incrementalMC1.pdf}
\caption{Training set size vs $balance$.
}\label{fig:tone}
\end{figure}

Test one was conducted on twelve data sets, all of which yielded
results like those depicted in \fig{tone}~\cite{me07i}. In that
figure, the X-axis is the size of training set and the  Y-axis is
the $balance$ measure.
%All results come from a hold-out set of 100 instances.
Note that the performance foes not change much regardless of whether
the model is inferred from 100 instances or from up to several
thousand instances. In fact, learning from too many training
examples was actually detrimental (witness the widening variance as
the training set increases). A Mann Whitney U test~\cite{mann47}
(95\% confidence) confirms the visual pattern apparent in
\fig{tone}: static code features used as the basis for predicting
module's fault content reveal all that they can reveal after as
little as 100 instances.

To implement {\em test two}, we linked code modules to the
requirements that prompted their development. Features were
extracted from the requirements using a lightweight linear-time text
parser. Those features included {\em weak words} such as ``TBD'' and
``but not limited to''; {\em imperatives} such as ``must'',
``should''; and {\em options} such as ``can'', and ``may''. Training
instances for the fault prediction models were then created using
just static code features, just requirements features, or both
(using a database inner join operation to connect requirements with
modules in which they have been implemented).

The results are shown in \fig{ttwo}. This figure  plots $pd$ vs $pf$
seen in the two data sets after a 10-way cross validation.
% when modules were considered defective if $\frac{M}{N}$ of the 10-ways
%classified a module as ``defective''. The curves in those plots
%result from varying $M$ from one to ten.
The ideal spot on these ROC curves is top left; i.e. no false alarms
and perfect detection ($\{pd,pf\}=\{1,0\}$). The dashed lines on
those plots show $\{pd,pf\}$ results when fault prediction models
used requirements or code features in isolation. The solid lines
show the results of models which used these two kinds of features in
combination. Note the remarkable improvement: learning from {\em
multiple perspectives} such as code {\em and} requirements measures
in conjunction, lead to dramatically improved $pd$ and $pf$.

\begin{figure}[!t]
\begin{center}
\includegraphics[width=2.3in]{pc1r.png}
\includegraphics[width=2.3in]{cm1r.png}
\end{center}
\caption{$\{pd,pf\}$ curves seen when using
code and/or requirements features.
From~\cite{jiang07}.}\label{fig:ttwo}
\end{figure}
The knowledge of the values of multiple feature sets from different
sources along the project's development life cycle leads to
conclusion that the resulting models likely represent
domain-specific, if not project-specific solutions. \fig{ttwo}
strongly suggest in favor of for using multiple feature sets from
different software artifacts.  While an exciting result, it has some
drawbacks. Different projects use different tools and build software
using different processes. Hence, different projects have access to
different sets of features which may be useful for predicting where
faults hide; e.g. an agile process may have no access to the
detailed requirement documents used to build model in \fig{ttwo}.

Other experiments  also suggest that the {\em best} set of features
are domain specific. {\em Feature subset selection} (FSS) checks if
feature subsets
performs as well as  supersets.
In all the data sets studied
in~\cite{me07b}, 38 static code features could be pruned down to
three {\em without} reducing the efficacy of the defect predictor.
Significantly,
in each data sets, FSS selected
{\em different features}. That is, FSS found no universally {\em
best} features for defect prediction.  An analogous result has been
been reported by Shepperd and Ince~\cite{shepperd94}. They reviewed
18 publications in which no {\em best} predictive feature was found.
In those publications, an equal number of studies reported that 
cyclomatic complexity is the same, is better, or is worse
than LOC in predicting defects.

\fig{sorted} explains the FSS results and the results of Shepperd
and Ince. It also cautions that the best set of features will change
from domain to domain. This figure plots the {\em information gain}
associated with 38 static code features.  This {\em infogain}
measure is used in decision tree learners~\cite{quinlan92} to select
the feature that best divides up the examples\footnote{Infogain
compares the number of bits required to encode the distribution of
defective/non-defective classes before and after dividing the
examples amongst the range of feature F.}. The first 16 features
have very similar information content. In fact, given the standard
deviations shown in the error bars of that figure, the 16th-ranked
feature is statistically insignificantly different to the top-ranked
features. Hence, minor changes in the training sample
 change what features are found to be the {\em best} software  quality predictors.


\begin{figure}{r}{3.5in}
\begin{center}
\includegraphics[width=3.5in]{infogain.pdf}
\end{center}
\caption{Mean and standard deviation (t-bars)
of InfoGain in 10*90\% random samples of defect data.
}\label{fig:sorted}
\end{figure}
Based on the above, in contrast with the current trend in the
literature, we recommend against trying supposedly better AI methods
to learn defect predictors. We make this recommendation
for two reasons.

Firstly, different  data miners have failed to improve the state of the art
in learning defect predictors. The early plateau effect of
\fig{tone} suggests that static code features yield all they can
yield after as little as a few hundred examples. This information
can be found by relatively simple learners such as Naive Bayes. That
is, the added value of more sophisticated AI data miners must be
questioned.

Secondly, there is a limited generality in the predictors learned by standard
AI data miners. \fig{ttwo} showed that combining data sources can
yield fault predictors that out-perform predictors learned from
either source in isolation. Different domains and different projets
offer different data sources and, consequently, the {\em best} set
of features to use in a quality prediction will be domain-dependent.
Further evidence for the domain dependent nature of quality
predictors comes from \fig{sorted}. Given a set of features, many of
them compete to be the {\em ``best"} one and minor variations in the
sampling methods can yield different selection of {\em best}
predictors. 

\section{Over-Under Sampling}

Over and under-sampling are well known techniques in the field of Data Mining. Both of these preprocessing techniques have the potential to improve the results of a learner. To sample, you must first pick a particular class as a goal. For the MDP datasets, we picked “true.” Your sampling program will take two passes through the data. During the first pass, a table of frequency counts is built. If the desired goal is reached in fewer instances than the other classes, a second pass is taken through the data. This is where the two sampling techniques differ. In the case of under-sampling, instances are printed until the combined number of instances with other classes is equal to the number of instances with the desired goal. This results in a much smaller dataset, but your desired goal is not lost in the great big data soup. 

Over-sampling follows a similar procedure. Instead of limiting the number of instances with other classes, the sampling program instead add new instances with your desired goal. Ultimately, you have a much larger dataset. We have used a fairly simple sampling method. For both sampling techniques, half of the final dataset will consist of instances with the desired goal.

In this field, many hold the opinion that more data is better. If you are looking for the diamonds in the dust, you’ll find more diamonds when you have more dust. Through this experiment, we hope to show the effects of over and under-sampling on the MDP datasets as they are processed with the Naïve Bayes classifier and the J48 implementation of the C4.5 tree learner. We actually believe that under-sampling will yield the best results, challenging the “more is better” mantra.  


%\subsection{Related Work}

%Holte and Drummond \cite{drummond03} are responsible for some of the best research in the area of under and over-sampling. Their 2003 paper explored a very similar situation. They took a look at the effects of sampling with the C4.5 tree learner. Rather than using balance, they used their own “cost curve” measurement \cite{drummond00a}. They found that under-sampling produced excellent results,  it was sensitive to changes in misclassification costs and class distribution. On the other hand, over-sampling produced little to no change in the results.  Over-sampling could be made cost-sensitive if pruning and early stopping parameters were set in proportion to the amount of oversampling to be done. This is, however, computational costly and completely unnecessary as under-sampling removes and need for pruning at no additional cost. Under-sampling does have some problems of its own. For instance, under-sampling introduces non-determinism into the previously deterministic learning process. This variance could make a difference in some research. They ultimately conclude that C4.5 with under-sampling is a good baseline for cost sensitivity research. 

%Drummond and Holte are hardly the only ones to explore this space. C4.5 combined with a sampling policy has become something of a baseline in cost-sensitivity research \cite{domingos99, pazzani94}. Kate McCarthy, Bibi Zabar and Gary Weiss, in their 2005 paper \cite{mccarthy05}, examined whether under-sampling, over-sampling, or cost-sensitive learning yielded the best results. Their goal was to show that cost-sensitive learning beat sampling methods on the C5.0 learner \cite{rulequest} when trying to find total cost (Total Cost = (False Negatives × CFN) + (False Positives × CFP) \cite{zadrozny04}). Their research found no clear winner. When analyzing smaller datasets, they found that over-sampling beat both under-sampling and cost-sensitive learning on all but one dataset. On larger sets, cost-sensitive learning narrowly beat over-sampling. They explain this difference by hypothesizing that cost-sensitive learning performs better with a large amount of training data. 



%\input{timm/challenges.tex}

\subsection{Experiment}
 
To confirm our hypothesis, and to test the general effects of the sampling techniques, we put together a 10-way  cross-validation experiment. We first created two sets, each with a different sampling method. For each of these and the original dataset, we split into a training set (90\%) and a test set (10\%). We then learned on the data using the Weka implementations of Naïve Bayes and J48. We repeated each of these steps ten times for each of the MDP datasets. 

We compared the results based on the balance (a combination of $\{pd,pf\}$that decreases if $pd$ decreases or $pf$ increases). We ran Mann-Whitney U tests and formed win-loss-tie tables based on the learner and the sampling method used. We also created win-loss-tie tables for learner, sampling method, and dataset. 

\subsection{Results}

\begin{figure}
\begin{center} \includegraphics[width=2.4in]{gregwlt.png}
\end{center}
\caption{W-L-T table for learner and sampling policy.}
\label{fig:wltoverunder} \end{figure}


We can see from \fig{wltoverunder} that when processing datasets with the J48 learner, under-sampling dramatically improves our results. Oversampling shows a slight advantage over no sampling at all. These results aren’t quite so clear for Naïve Bayes. Under-sampling tied with filter, and over-sampling produced worse results. This didn’t quite produce the level of detail that we would like, so we have also looked at quartile results. 

Naive Bayes, Under-Sampled [19.9, 67.1, 74.1, 81.6,100.0]
\begin{center}
{\small
\[0\%\; \boxplot{19.9}{47.2}{74.1}{81.6}{18.4}\; 100\%\]}
\end{center}
Naive Bayes, Over-Sampled [17.5, 42.0, 62.5, 72.2,100.0]
\begin{center}
{\small
\[0\%\; \boxplot{17.5}{24.5}{62.5}{72.2}{27.8}\; 100\%\]}
\end{center}
Naive Bayes, No Sampling [21.9, 67.7, 74.6, 81.9,100.0]
\begin{center}
{\small
\[0\%\; \boxplot{21.9}{45.8}{74.6}{81.9}{18.1}\; 100\%\]}
\end{center}
J48, Under-Sampled [21.6, 64.8, 73.6, 82.6,100.0]
\begin{center}
{\small
\[0\%\; \boxplot{21.6}{43.2}{73.6}{82.6}{17.4}\; 100\%\]}
\end{center}
J48, Over-Sampled [0.0, 29.3, 45.6, 56.2,100.0]
\begin{center}
{\small
\[0\%\; \boxplot{0}{29.3}{45.6}{56.2}{43.8}\; 100\%\]}
\end{center}
J48, No Sampling [0.0, 29.3, 42.3, 54.5,100.0]
\begin{center}
{\small
\[0\%\; \boxplot{0}{29.3}{42.3}{54.5}{45.5}\; 100\%\]}
\end{center}

We can more clearly see the difference from the quartile data. The balance increase from under-sampling for J48 is huge. Over-sampling only presents a small improvement, only a three percent increase in balance. The Naïve Bayes results were higher to begin with. On sets with no sampling policy, Naïve Bayes had a midpoint of 74.6 compared with J48’s 42.3. In fact, Naïve Bayes performed slightly better when no sampling was done at all, scoring a midpoint of 74.6 when not sampling and 74.1 when under-sampling.  Over-sampling hurt the results, bringing the midpoint down to 62.5.

\fig{under} shows the results of an under-sampling study where $N\in\{25,50,75,...\}$
defective modules were selected along with an equal $N$ number of defect-free modules.
Note the same visual pattern as before: increasing data does not necessarily improve $balance$.

Mann-Whitney tests were applied to test this visual pattern. 
Detectors learned from just $N$ instances do as well
as detectors learned from any other number of instances:

\bi
\item
N=25 for \{CM1,KC2,KC3,MC1,MC2,MW1,PC1,PC2\}
\item
N=75 for \{PC3\} (and N=25 losses three times out of 11).
\item
N=200 for \{PC4\} (but N=25 losses once out of 13 trials)
\item
N=575 for \{KC1\} (for N=25 only lost once out of 25 trials)
\item
N=1025 for \{PC5\} (but at N=25, the lost lose only once our of 25 trials)
\ei



\section{How much data is required?}
\begin{figure*}
\begin{center}
\begin{tabular}{ccc}
\includegraphics[angle=90,width=2in]{log/incrementalCM1.pdf}&
\includegraphics[angle=90,width=2in]{log/incrementalKC1.pdf}&
\includegraphics[angle=90,width=2in]{log/incrementalKC2.pdf}\\
\includegraphics[angle=90,width=2in]{log/incrementalKC3.pdf}&
\includegraphics[angle=90,width=2in]{log/incrementalMC1.pdf}&
\includegraphics[angle=90,width=2in]{log/incrementalMC2.pdf}\\
\includegraphics[angle=90,width=2in]{log/incrementalMW1.pdf}&
\includegraphics[angle=90,width=2in]{log/incrementalPC1.pdf}&
\includegraphics[angle=90,width=2in]{log/incrementalPC2.pdf}\\
\includegraphics[angle=90,width=2in]{log/incrementalPC3.pdf}&
\includegraphics[angle=90,width=2in]{log/incrementalPC4.pdf}&
\includegraphics[angle=90,width=2in]{log/incrementalPC5.pdf}
\end{tabular}
\end{center}
\caption{Results from experiment \#2. Training set size grows in units of 100 examples,
 moving left to right
over the x-axis. The MC2 results only appear at the maximum x-value since MC2 
has less than 200 examples.
}\label{fig:inc}
\end{figure*}



\subsection{Design}
A curious aspect of the above results is that defect predictors
were learned using only a handful of defective modules.
For example, consider a 90\%/10\% train/test split on
$pc1$ with 1,109 modules, only 6.94\% of which are defective.
On average, the test set will only contain \mbox{$1109 * 0.9 * 6.94/100=69$}
defective modules. Despite this, $pc1$ yields an adequate median $\{pd,pf\}$ results
of $\{88,34.5\}$\%. 

Experiment \#2 was therefore designed to check how {\em little} data is required
to learn defect predictors. Experiment \#2 was essentially the same
as the last experiment, but
without treatment \#1 (the
cross-company study). Instead,
experiment \#2
took the 12 example tables
and 
learned predictors using:
\bi
\item Treatment 3 (reduced WC):  a randomly selected
subset of the 90\% rows of this table;
\ei
Specially, after randomizing the order of the rows, training sets
were built using just the first 100,200,300,\ldots rows in the tables.
After training, the learned theory was applied to  100 rows
not used in training (selected at random).

Experiment \#1 only used the features found in all tables of data.
For this experiment, we imposed no such restrictions and used whatever features
were available in each data set.
\subsection{Results from Experiment \#2}
Recall that "balance'' is defined to be a combination of $\{pd,pf\}$
that decreases if $pd$ decreases or $pf$ increases.
As shown in \fig{inc}, there was very little change in balanced 
performance  after learning from 100,200,300,... examples.
Indeed, there is some evidence that
learning from larger training sets had detrimental effects: the more
training data, the larger the variance in the performance of the learned predictor.
Observe how, in $pc2$, as the training set size increases (moving right along the x-axis)
the dots showing the on balance performance start spreading out.
A similar, but smaller, {\em spread effect} can be see in $kc2$ and $mc1$.

The Mann-Whitney U test was applied to check the visual trends seen in \fig{inc}.
For each table, all results from training sets of size 100,200,300\ldots were
compared to all other results from the same table. The issue was ``how much data is enough?''
 i.e.
what is the $min$imum
training set size that never lost to other training set of a larger size. Usually, that 
$min$ value 
was quite small:

\bi
\item In seven tables $\{cm1,kc2,kc3,mw1,pc3,pc4\}$, $min=100$;
\item In  \{$kc1,pc1$\}, $min=\{200,300\}$ instances, respectively.
\ei

In other tables of data, $min$ was much larger. In $\{pc2,mc1,pc5\}$ the 
$min$ values were found at $\{4900, 8300, 11000\}$, respectively.  However, much smaller
training set sizes performed nearly as well as these larger training sets:
\bi
\item
In $pc5$, predictors learned from 300 examples only lost to other sizes 
twice in 169 trials;
\item
In $mc1$, predictors learned from 400 examples only lost to other sizes
once out of 92 trials);
\item In $pc2$, predictors learned from 800 examples only
lost to other size twice out of 53 trials.
\ei

We explain the experiment \#2 results as follows.
These experiments used simplistic static code features such as lines of code, number of
unique symbols in the module, etc.  
Such simplistic static code features are hardly a complete characterization of
the internals of a function. Fenton offers an insightful example where
{\em the same} functionality is achieved using {\em different}
programming language constructs resulting in {\em different} static
measurements for that module~\cite{fenton97}.  
We would characterize such static code features as having 
{\em limited information content}. 
Limited content
is soon exhausted by repeated sampling.
Hence, such simple features reveal all they can reveal after
a small sample

\begin{figure}
\begin{center} \includegraphics[width=2.4in]{plateaus/plateaudots.pdf}
\includegraphics[width=2.4in]{plateaus/plateaudotsC.pdf} \end{center}
\caption{Y-axis shows plateau point after learning from data sets
that have up to $X$ examples (from~\cite{orrego04}).
The top plot shows results from using
Naive Bayes (nbk) or a decision tree learner (j48)~\cite{quinlan92}
to predict for discrete classes. Bottom plot shows results from
using linear regression (lsr) or model trees (m5)~\cite{quinlan92b}
to learn predictors for continuous classes. In this study, data
sets were drawn from the UC Irvine data repository~\cite{Blake+Merz:1998}.
}\label{fig:plateau} \end{figure}

\subsection{Sanity Checks on Experiment \#2}
This section checks for precedents on the Experiment \#2 results
and can be skipped at first reading of this paper.

There is also some evidence that the  results of Experiment 2 (that
performance improvements stop after a few hundred examples) has
been seen previously in the data mining literature (caveat: to the
best of our knowledge, this is first report of this effect in the
defect prediction literature): \bi \item In their discussion on how
to best handle numeric features, Langley and John offers plots of
the accuracy of Naive Bayes classifiers after learning on 10,20,40,..200
examples. In those plots, there is little change in performance
after 100 instances~\cite{john95}.  \item Orrego~\cite{orrego04}
applied four data miners (including Naive Bayes) to  20 data sets
to find the {\em plateau point}: i.e. the point after which there
was little net change in the performance of the data miner.  To
find the plateau point, Oreggo used t-tests to compare the results
of learning from $Y$ or $Y+\Delta$ examples. If, in  a 10-way
cross-validation, there was no statistical difference between $Y$
and $Y+\Delta$, the plateau point was set to $Y$.  As shown in
\fig{plateau}, many of those plateaus where found at $Y\le100$ and
most were found at $Y\le200$. Note that these plateau sizes are
consistent with the results of Experiment 2.  \ei

\section{Conclusions}

From these results, it is clear that J48 is improved by both over and under-sampling. Under-sampling, in fact, represents a huge improvement. Less data is clearly better than more. It is less clear how Naïve Bayes is affected by sampling policies. When looking at results by dataset, under-sampling and no sampling policy are usually indistinguishable. In some cases, one outperforms the other. Over-sampling universally produced worse results. This does clearly show that for Naïve Bayes, more data is not better. It also shows that narrowing your current data will not hurt the results, even if it does not improve them. 

\begin{figure*}
\begin{center}
\begin{tabular}{ccc}
\includegraphics[angle=90,width=2in]{log/underCM1.pdf}&
\includegraphics[angle=90,width=2in]{log/underKC1.pdf}&
\includegraphics[angle=90,width=2in]{log/underKC2.pdf}\\
\includegraphics[angle=90,width=2in]{log/underKC3.pdf}&
\includegraphics[angle=90,width=2in]{log/underMC1.pdf}&
\includegraphics[angle=90,width=2in]{log/underMC2.pdf}\\
\includegraphics[angle=90,width=2in]{log/underMW1.pdf}&
\includegraphics[angle=90,width=2in]{log/underPC1.pdf}&
\includegraphics[angle=90,width=2in]{log/underPC2.pdf}\\
\includegraphics[angle=90,width=2in]{log/underPC3.pdf}&
\includegraphics[angle=90,width=2in]{log/underPC4.pdf}&
\includegraphics[angle=90,width=2in]{log/underPC5.pdf}
\end{tabular}
\end{center}
\caption{Under-sampling results}\label{fig:under}
\end{figure*}
In summary, the research challenge is clear:
\bi
\item 
We should stop trying
out supposedly better AI data miners. Instead, we must
look to
other sources of information based on the software engineering
knowledge and project's business environment if we are going to
improve on our current generation of quality predictors. 
\item
We
must acknowledge that it is insufficient to merely apply one
machine learning method and then use the model on all future
problems. Rather, we need to find cost-effective methods to quickly
learn domain dependent quality predictors.
\ei


\bibliographystyle{IEEEtran}
\bibliography{refs}

\end{document}
