% This is "sig-alternate.tex" V1.9 April 2009
% This file should be compiled with V2.4 of "sig-alternate.cls" April 2009
%
% This example file demonstrates the use of the 'sig-alternate.cls'
% V2.4 LaTeX2e document class file. It is for those submitting
% articles to ACM Conference Proceedings WHO DO NOT WISH TO
% STRICTLY ADHERE TO THE SIGS (PUBS-BOARD-ENDORSED) STYLE.
% The 'sig-alternate.cls' file will produce a similar-looking,
% albeit, 'tighter' paper resulting in, invariably, fewer pages.
%
% ----------------------------------------------------------------------------------------------------------------
% This .tex file (and associated .cls V2.4) produces:
%       1) The Permission Statement
%       2) The Conference (location) Info information
%       3) The Copyright Line with ACM data
%       4) NO page numbers
%
% as against the acm_proc_article-sp.cls file which
% DOES NOT produce 1) thru' 3) above.
%
% Using 'sig-alternate.cls' you have control, however, from within
% the source .tex file, over both the CopyrightYear
% (defaulted to 200X) and the ACM Copyright Data
% (defaulted to X-XXXXX-XX-X/XX/XX).
% e.g.
% \CopyrightYear{2007} will cause 2007 to appear in the copyright line.
% \crdata{0-12345-67-8/90/12} will cause 0-12345-67-8/90/12 to appear in the copyright line.
%
% ---------------------------------------------------------------------------------------------------------------
% This .tex source is an example which *does* use
% the .bib file (from which the .bbl file % is produced).
% REMEMBER HOWEVER: After having produced the .bbl file,
% and prior to final submission, you *NEED* to 'insert'
% your .bbl file into your source .tex file so as to provide
% ONE 'self-contained' source file.
%
% ================= IF YOU HAVE QUESTIONS =======================
% Questions regarding the SIGS styles, SIGS policies and
% procedures, Conferences etc. should be sent to
% Adrienne Griscti (griscti@acm.org)
%
% Technical questions _only_ to
% Gerald Murray (murray@hq.acm.org)
% ===============================================================
%
% For tracking purposes - this is V1.9 - April 2009

\documentclass{sig-alternate}
\usepackage{times,url}
\usepackage{timm/tricks}
\newcommand{\boxplott}[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}
%
% --- Author Metadata here ---
\conferenceinfo{PROMISE}{'10  Timisoara, Romania}
%\CopyrightYear{2007} % Allows default copyright year (20XX) to be over-ridden - IF NEED BE.
%\crdata{0-12345-67-8/90/01}  % Allows default copyright data (0-89791-88-6/97/05) to be over-ridden - IF NEED BE.
% --- End of Author Metadata ---

\title{On the Value  of Learning From Highly-Dense\\ 
Components for Software Defect Prediction}
%
% You need the command \numberofauthors to handle the 'placement
% and alignment' of the authors beneath the title.
%
% For aesthetic reasons, we recommend 'three authors at a time'
% i.e. three 'name/affiliation blocks' be placed beneath the title.
%
% NOTE: You are NOT restricted in how many 'rows' of
% "name/affiliations" may appear. We just ask that you restrict
% the number of 'columns' to three.
%
% Because of the available 'opening page real-estate'
% we ask you to refrain from putting more than six authors
% (two rows with three columns) beneath the article title.
% More than six makes the first-page appear very cluttered indeed.
%
% Use the \alignauthor commands to handle the names
% and affiliations for an 'aesthetic maximum' of six authors.
% Add names, affiliations, addresses for
% the seventh etc. author(s) as the argument for the
% \additionalauthors command.
% These 'additional authors' will be output/set for you
% without further effort on your part as the last section in
% the body of your article BEFORE References or any Appendices.

\numberofauthors{2} %  in this sample file, there are a *total*
% of EIGHT authors. SIX appear on the 'first-page' (for formatting
% reasons) and the remaining two appear in the \additionalauthors section.
%
\author{
% You can go ahead and credit any number of authors here,
% e.g. one 'row of three' or two rows (consisting of one row of three
% and a second row of one, two or three).
%
% The command \alignauthor (no curly braces needed) should
% precede each author name, affiliation/snail-mail address and
% e-mail address. Additionally, tag each line of
% affiliation/address with \affaddr, and tag the
% e-mail address with \email.
%
% 1st. author
\alignauthor Hongyu Zhang\\
    \affaddr{School of Software,\\Tsinghua University}\\
    \affaddr{Beijing 100084, China}\\
    \email{hongyu@tsinghua.edu.cn}
\\
\alignauthor Adam Nelson, Tim Menzies\\
            \affaddr{CS \& EE, West Virginia University}\\
            \affaddr{Morgantown, WV, USA}\\
       \email{rabituckman@gmail.com, tim@menzies.us}
}
% There's nothing stopping you putting the seventh, eighth, etc.
% author on the opening page (as the 'third row') but we ask,
% for aesthetic reasons that you place these 'additional authors'
% in the \additional authors block, viz.
\date{30 July 1999}
% Just remember to make sure that the TOTAL number of authors
% is the number that will appear on the first page PLUS the
% number that will appear in the \additionalauthors section.

\maketitle
\begin{abstract}
\noindent
{BACKGROUND}: Defect predictors
learned from static code measures are a useful method
for isolating code modules with a higher than usual
probability of defects.

\vspace{2mm}

\noindent
{AIMS}: We seek to improve those learners but focusing the
learning on the defect-rich portions of the training sets.

\vspace{2mm}


\noindent
{METHOD}: Defect data from
 five projects (CM1, KC1, MC1, PC1, PC3) were separated
into their various components. 
A subset of the projects (selected at random)
were set aside for testing. 
Training sets were then generated for a NaiveBayes
classifier in two different ways.
In one sample (the {\em dense}
treatment), 
the subset of components
with higher than the median number of defects/component where
identified and used for training. In another sample
(the {\em standard} treatment), modules from any component were
used for training.
Both samples were then run against the test set and
evaluated using
precision, probability of false alarm, and precision.
This rig was repeated in a 10-by-10 cross-validation experiment,

\vspace{2mm}


\noindent
{RESULTS}: 
{\em Dense} sampling out-performed {\em standard} sampling
in $\frac{11}{14}$ results
(5 data sets * 3 evaluation criteria).

\vspace{2mm}


\noindent
{CONCLUSIONS}: Given training data where most of the defects exist in  small
number modules, effect defect predictors can be trained by ignoring
the modules with the lower number of defects.
\end{abstract}
\category{I.5}{learning}{machine learning}
\category{D.2.8}{software engineering}{product metrics}
\keywords{Algorithms,experimentation, measurement}
\newpage 
\section{Introduction}
It is widely believed that some internal properties of software
(e.g., metrics) have relationship with the external properties
(e.g., defects). Many prediction models have been proposed based
on software metrics; e.g.~\cite{lessmann09,journals/ese/KhoshgoftaarS03}.
For example,
Menzies et al.~\cite{me07b} performed
defect predictions for five NASA projects using static code metrics.
In their work, probability of detection (recall) and probability of
false alarm (pf) are used to measure the accuracy of a defect
prediction model. Their models generate the average results of
\mbox{recall
= 71\% and pf = 25\%}, using a Naive Bayes classifier.

Zhang and Zhang~\cite{zhang07}
pointed out that
the Menzies et al. results are not satisfactory when precision is considered.
They found that high recall and low pf do not necessarily lead to high
precision. 
In reply, Menzies et al.~\cite{me07e}  noted that 
for the defect data in the PROMISE repository,
the percentage of modules with defects is low.
They showed that, for such data, it is
mathematically impossible to expect high precision {\em and}
high recall
(that mathematical argument is reproduced in \tion{bal}).

This paper tries to refute the conclusions of~\cite{me07e} and to,
somehow, achieve defect predictors with 
The solution explored
here originated in the following observation:
\begin{quote}
{\em With software projects, most of the defects occur in a minority
of components.}
\end{quote}
The significance of this observation is that while the frequency
of defective modules {\em in the entire project} may be low, the frequency
{\em within a few components} is much higher.
This lead to the speculation that if we focused more on the densely defective
components, we might generate better defect predictors.

The rest of this paper explores this possibility.
In the following, we say that a software 
{\em project} is divided into {\em components} and {\em components}
have {\em modules}. In this terminology:
\bi
\item
 The {\em module} is the smallest unit of compilation;
e.g. a function in ``C'', or a method in ``JAVA'';
\item A {\em component} is a
 large groupings
of many  modules. 
\ei
Typically, one {\em project} contains dozens to hundreds of {\em components}, and
each {\em component} contains hundreds to thousands of  {\em modules}.

Using this terminology, we can summarize our findings as follows:
training on densely defective components produces better defect
predictors than otherwise.
\section{Background}
Before we present our specific results, this section
reviews the general area of defect prediction.

One method for assessing software is
to extrapolate the curve of post-release failures
In this {\em reliability engineering} approach, analysts
use knowledge of how the frequency of faults
seen in a running system changes over time~\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; i.e. not
until the entire system is assembled.
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}.  

Prior to building a fully functioning system, software engineers build modules
then, usually,  apply some quality assurance (QA) technique to assess the quality of those modules
(those techniques include inspections, unit tests, static source code analyzers, etc).
A record of the results of those QA techniques  is a {\em defect log}. Note that this
log can accumulate from very early in the development cycle (i.e. even before the entire
system is running).

{\em Defect predictors} can be learned from these historical logs.
We assume that these logs are tables of data, each row of which
contains {\em static code features}  and  a class label  ``{\em defective}''
whose values are
{\em true} or {\em false}. In those tables:
\bi
\item
Rows describe data from one {\em module}; a.k.a.
``functions'' or ``methods'' or
``procedures''. 
\item
Columns describe 
static code features such as lines of code measures,
the McCabe measures, and the Halstead measures.
\ei
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.

\subsection{How can these defect predictors be used?}
Defect predictors can be used to adjust
QA budgets that are inappropriately
focused on the
wrong parts of the code.

During development, developers {\em skew} their limited 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 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 project budgets are finite and QA
effectiveness increases with QA effort:
\bi
\item
 A {\em linear} increase in
the confidence $C$ of finding faults takes {\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 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 
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}
offer numerous other examples
where assessment effectiveness is exponential on effort.
\ei
Exponential costs 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,
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} like defect predictors
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{But Does It Work?}

Compared to certain reports of standard industrial practice, defect predictors
are better than humans are identifying which modules will require further QA.
Previously we have reported studies where defect predictors had probabilities
of defection (recall) and probabilities of false alarm (pf) of (recall,pf)=(71\%,25\%),   
on average~\cite{me07b}.
These values are higher than known results from manual inspection methods.
For example,
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's
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}.}  
In other work,
Raffo found that the defect detection capability of
industrial review methods can vary from 
\[
Recall=TR(35, 50, 65)\%\]
for full Fagan inspections~\cite{fagan76} to
\[
Recall=TR(13, 21, 30)\%\]
for less-structured inspections~\cite{raffo05}
(note: ``$TR(a,b,c)$'' is a triangular distribution with
min/mode/max of $a,b,c$).

Defect prediction can also be faster than human-intensive methods.
Static code features can can be automatically and cheaply extracted
from source code, 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}.

Also, there are industrial reports where this style of defect prediction
was found pragmatically useful by industry:
\bi
\item Defect predicting technology has been commercialized in the
  {\em Predictive} tool and sold across the United States.
One
company used it to manage  safety critical
software for  fighter aircraft  
  (the software controlled a
 lithium ion battery, which can overcharge and possibly
  explode).  After applying a more expensive tool for structural
  code coverage was applied,  the company ran Predictive on the same code base.
  Predictive produced consistent results with the more expensive tools
 while
being able to faster process a larger code base than the 
  more expensive tool~\cite{ism06}.
\item
 Defect predictors
developed at NASA ~\cite{me07b}
have been applied to software development companies in
other country (in Turkey).
When inspection teams focused on the modules that trigger the defect predictors, 
they found up to 70\% of the defects using
40\% of the effort (measured in staff hours)~\cite{tosun09}. 
\item
A  subsequent study on the Turkish software
compared how much code needs to be
inspected using random selection vs selection via our
defect predictors. Using random testing,  
87\% of the files
would have to be inspected in order to detect 87\% of the
defects.
However, if the inspection process was restricted to the
25\% of the files that trigger the defect
predictors, then 88\% of the defects could be found. 
That is, the same level of defect detection (after inspection)
can be achieved using $\frac{87-25}{87}=71\%$ less effort~\cite{tosun10}.
\ei

\subsection{Building Better Detectors}

There are several proposals for improving defect predictors.
One argument is to augment these static code attributes with {\em social metrics}
describing patterns of interactions between developers.  This has proved useful
in some domains~\cite{nach08} but not in others~\cite{weyuker08}.

Another approach is to use {\em other static code measures} such as
{\em churn} (the rate at which the code base changes)~\cite{hall00}.
As far as we are aware, there is no definitive result showing that some static code measures
are better than any other.

As to {\em  use of better data mining algorithms}, the current state of the art
is curiously static:
\bi
\item 
Khoshgoftaar and Seliya~\cite{journals/ese/KhoshgoftaarS03}
performed an extensive study on NASA JM1 and KC2 datasets using 25
classification techniques with 21 static code metrics. They observed
low prediction performance, and they did not see much improvement by
using different classification techniques.
\item
Lessmann et al.
report an extensive study on the 
statistical differences  between 19
data miners commonly used for defect prediction~\cite{lessmann09}.  The learners'
performance was remarkably similar: all but four shared top ranking in their analysis.
\ei

Recently, Milton and Menzies et. al. have had some success with {\em tuning data miners to the local business
goals}. Their WHICH learner performs a stochastic beam search across combinations
of attribute ranges to maximize a domain-specific scoring function.
In a study with one scoring function, WHICH significantly out-performed
standard methods like C4.5 and Naive Bayes~\cite{milton08,me10a}.

While the WHICH study is indeed interesting, it is only wins by changing the rules
of the game. In standard defect prediction, the learned detectors are assessed
via their precision, false alarm rate, or recall (probability of detection). 
Note that by ``standard defect prediction'' we mean every piece of research
referenced in this paper 
(with the sole exception of WHICH)
and every defect prediction paper ever published at PROMISE.
Therefore, having noted the WHICH experiments, the rest of this paper will only
explore
standard defect prediction.

\section{Breaking Through the Ceiling}

The high water mark in this field has been static for several years. 
For example, for four 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.
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, \citeN{lessmann09} conclude \begin{quote}
{\em ...the
importance of the classifier  model is less than generally assumed ...
practitioners are free to choose from a broad set of models.}\end{quote}


If better data miners do not offer improvements, perhaps it is time to explore other approaches. 
If we cannot  {\em improve the data miners}, perhaps we can {\em improve the data}?
To understand this approach, this section reviews the mathematics of defect prediction:
\bi
\item This mathematical
analysis will highlight the importance of the
$neg/pos$ ratio. The $neg/pos$ ratio expresses the percentage of defective modules in the training set: if
a training set contains 10\% defective modules, then $neg/pos=10$.
\item
We then present experiments that carefully select the training data in order to most change the $neg/pos$ ratio.
\ei
\subsection{Defect Prediction Mathematics}\label{sec:bal}

Let $\{A,B,C,D\}$ denote the
true negatives, 
false negatives, 
false positives, and 
true positives
(respectively) found by a binary detector. 
Certain standard measures can be computed from
$A,B,C,D$: 
\[
{\small \begin{array}{ll}
pd=recall=&D/(B+D)\\
pf=&C/(A+C)\\
prec=precision=&D/(D+C)\\
acc=accuracy=&(A+D)/(A+B+C+D)\\
bal=balance=&1 - \sqrt{recall^2 + (1- pf)^2}\\
neg/pos=&(A+C)/(B+D)
\end{array}}
\]
The last measure ($neg/pos$) is most important to the subsequent discussion.
The following expression offers a relationship
between $prec,recall,pf$. Note that this relationship changes according to the ratio
of the target class in the training data; i.e. the   $\frac{neg}{pos}$ ratio.

{\small \begin{equation}\label{one}
prec = \frac{D}{D+C} = \frac{1}{1+ \frac{C}{D}} = \frac{1}{1 + neg/pos \cdot pf/recall}
\end{equation}}
which can be rearranged to

{\small
\begin{equation}\label{two}
pf = \frac{pos}{neg}\cdot\frac{ (1 -  prec) }{ prec}\cdot recall
\end{equation}}
Menzies et al.~\cite{me07e} called this expression {\em Zhangs' equation}
after the authors of the paper that first reported it~\cite{zhang07}.
Observe how,  when $recall$ is fixed then
the 
false alarm rate becomes controlled by precision and a 
fixed constant determined by the data set being examined; i.e.
when ($\alpha=neg/pos$) and \mbox{$recall=1$}
then:

{\small
\begin{equation}\label{three}
pf = \alpha\cdot \frac{1-prec}{prec}
\end{equation}}
From this equation, it is clear that for any targeted recall value,
{\em increasing} 
precision requires
{\em decreasing}
false alarm rates; e.g. for \mbox{$prec\in\{0.5,0.70,0.9,0.95\}$}, $pf$ 
becomes $\{1,0.43, 0.11, 0.005\}$,
respectively. 
As $neg/pos$ increases, 
high recall\&precision
is only possible when $pf$ becomes vanishingly small.
For example, in the ranges 
\mbox{$0.65 \le prec,recall \le 0.8$}, 
Zhangs' equation reports that $pf$ falls into the following ranges:
\bi
\item  $0.023 \le pf \le 0.062$  for $neg/pos = 7$;
\item  $0.0108 \le pf \le 0.0287$ for $neg/pos = 15$;
\item  $0.007 \le pf \le  0.0017$ for $neg/pos = 250$;
\ei
In our experience \cite{me08d,me07b,me09b,me10a}, such small $pf$ values are not achievable, at least with
the defect data in the PROMISE repository.

In summary, Zhangs' equation represents a fundamental limit on our ability to improve defect predictors
for domains where the defective modules are relatively infrequent.
This analysis is highly pertinent to the PROMISE defect data sets that have
$neg/pos$ ratios
of
1.04, 
7.33,
9,
10.11,
13.29,
15.67, and
249. That is, unless we can do something about these $neg/pos$ ratios, the mathematics
of defect prediction assert that further improvements in defect prediction will requiring relaxing the goal
of building defect predictors with  high precision {\em and} high recall.
%
%\subsection{Changing the $neg/pos$ Ratio}
%
%One obvious way to change $neg/pos$ ratio is to {\em over-sample} the training data.
%In {\em over-sampling}, randomly selected instances from the minority
%class are copied. 
%
%For the purposes of contrast, we compare over-sampling with {\em none} (i.e. use the raw data, as is) and
%{\em under-sampling}.
%In the case of {\em under-sampling}, random instances from the majority classification
%are removed. This
%results in a much smaller dataset, but the minority class is no
%longer buried inside a larger set of other classes.
%
%At PROMISE'08,  Menzies et al.~\cite{me08e} reported the following sampling experiment.
%Different sampling policies
% were applied to the data sets from \fig{data} using
% 10-way cross-validation. For the ``no-sampling'' experiments, the raw data was used for
%training  and testing without any adjustment  to the class frequencies.
%
%
%\begin{figure}
%\renewcommand{\baselinestretch}{1}
%\small
%\begin{center}
%\begin{tabular}{l|lrrr@{.}l}
%     &          & (\# modules)         &          &  &\\
%project & language & examples & features  & \multicolumn{2}{c}{\%defective}\\\hline
%pc1 & c++ & 1,109    & 21          & 6&94\\
%kc1  & c++ & 845      & 21          & 15&45\\
%%%nasa&kc2  & c++ & 522      & 21          & 20&49\\
%cm1  & c++ & 498      & 21          & 9&83\\
%kc3  & java & 458      & 39          & 9&38\\
%mw1  & c++ & 403      & 37          & 7&69
%%%softlab& ar4 & c++ &107 &  30            & 18 & 69\\
%%%softlab& ar3& c++ & 63 &    30          & 12 & 70\\
%%%nasa&mc2  & c++ & 61      & 39          & 32&29\\
%%%softlab & ar5 & c++& 36 &  30           & 22 & 22\\
%\end{tabular}
%\end{center}
%\caption{Data used in~\cite{me08e}.
%}\label{fig:data}
%\end{figure} 
%\begin{figure}
%\begin{center}
%{\small\begin{tabular}{cllrc} 
%\multicolumn{3}{c}{~}& \multicolumn{1}{c}{2nd quartile, median }\\
%rank&treatment&median& \multicolumn{1}{c}{and 3rd quartile}\\\hline
%1&NB/ none & 74.6& \boxplott{21.9}{67.7}{74.6}{14}{100}\\ 
%1&NB/ under& 74.1& \boxplott{19.9}{67.1}{74.1}{15}{100}\\
%1&j48/ under& 73.6& \boxplott{21.6}{64.8}{73.6}{18}{100}\\ 
%2&NB/ over  &62.5&\boxplott{17.5}{42}{62.5}{30}{100}\\
%3&j48/ over &  45.6&\boxplott{0}{29.3}{45.6}{27}{100}\\
%4&j48/ none & 42.3&\boxplott{0}{29.3}{42.3}{25}{100}\\\hline
%&& & \multicolumn{1}{c}{50\%} 
%\end{tabular}}
%\end{center}
%\caption{
%Over- \& under- \& no sampling results. 
%Sorted descending by median $balance$ results ($balance$ is defined in \tion{bal}).
%The right-hand side show median values (as a circle) within a 25\% to 75\% 
%percentile range. The {\em rank}, shown left-hand-side, come from the 
%statistical analysis of
%\fig{stats}.
%Three methods share top rank: NB/none, NB/under, j48/under.
%}\label{fig:bands}
%\end{figure}
%\begin{figure}
%\renewcommand{\baselinestretch}{1}
%\small
%\begin{center} 
%\begin{tabular}{r|rrrr}
%rank & treatment &  win & loss & ties\\\hline
%1& nb / none & 3 & 0& 2\\
%1& nb / under& 3 & 0 & 2\\
%1& j48/ under &  3  & 0 & 2\\
%2&nb / over & 2 & 3 & 0\\
%3&j48/ over & 1 &4&0 \\
%4&j48/ none &  0 & 5 & 0
%\end{tabular}
%\end{center}
%\caption{Statistical tests on the \fig{bands} results:
%sorted in ascending
%order on the number of losses
%(so {\em better} methods appear at the {\em top} of the table.
%First column
%shows
%a comparison of one treatment against the other eight.
%Two treatments have the same rank if their median ranks are
%statistically insignificantly different  
%(Mann-Whitney, 95\% confidence).
%}
%\label{fig:stats} \end{figure}
%
%In these studies,
%two data miners were used: a Naive Bayes classifier and 
%the J48
%decision tree learner~\cite{witten05,quinlan92}.  
%J48 was used to test our rig against known over- and under- 
%sampling results described in the literature~\cite{drummond03,kamei07}.
%Other learners were not used since, as discussed above,
%Lessmann et al. reports that experiments with 
%with other learners have yet to be productive \cite{lessmann09}.
%
%\fig{bands} shows the $balance$ results for different sampling policies.
%$Balance$,
%defined in \tion{bal}, is the distance to an ``ideal'' detector of
%perfect recall and no false alarms:
%\bi
%\item
%Curiously,
%throwing away data (i.e. under-sampling) 
%did not degrade the performance of the learner. 
%In fact, in the case of j48, throwing away data
% improved the median $balance$
%performance from around 40\% to over 70\%.  
%The implications of this ``under-sampling is ok'' result
%are discussed in~\cite{me08e}.
%\item
%For this discussion, the most important result is that
%over-sampling did not improve classifier performance.
%This result is
%consistent with Drummond \& Holte's sub-sampling experiments~\cite{drummond03}
%and the sub-sampling
%classification tree experiments of Kamei et.al.~\cite{kamei07}.
%\ei
%
%In summary, we cannot recommend over-sampling and must  try other methods.
%

\section{The Distribution of Defects}
In this paper, we exploit the naturally occurring distributions inside 
defect data sets.
A repeated result~\cite{zhang08,zhang09}  is  that in a large software
system, the distribution of defects are skewed - that a small number
of modules accounts for a large proportion of the defects. For
example:
\bi
\item  In Eclipse 3.0, 20\% of the largest packages are
responsible for 60.34\% of the pre-release defects (defects found
six months before the release) and 63.49\% of post-release defects
(defects found six months after the release). 
\item
At the file level,
20\% of the largest Eclipse 3.0 files are responsible for 62.29\%
pre-release defects and 60.62\% post-release defects~\cite{zhang09}.
\item
These results are consistent with those reported by other researchers
such as Fenton and Ohlsson~\cite{fenton00b} and Andersson and Runeson~\cite{andersson07}\footnote{hongyu: reference}.
\ei
The skewed distribution of defects is also found in the PROMISE defect datasets; i.e.
a few modules (at the function/method level) have a
large number of defects and a large number of modules have a few
defects. As an example, \fig{dist} shows the distribution of defects
over CM1 and KC1 modules from the PROMISE repository. All modules are ranked by the number of
defects they are responsible for. Clearly the distributions are
highly skewed- a few modules have many defects and most
modules have 0 or 1 defect. 
\begin{figure} 
\small
\begin{center}
%\includegraphics[width=80.0mm, height=58.0mm]{hongyu/figures/cm1.png}
%\includegraphics[width=80.0mm, height=58.0mm]{hongyu/figures/kc1.png}
\includegraphics[height=2in,angle=90]{hongyu/kc1r.pdf}
\includegraphics[height=2in,angle=90]{hongyu/cm1r.pdf}
\caption{The Distribution of Defects in CM1 and KC1}\label{fig:dist}
\end{center}
\end{figure}


We also calculate the cumulative
percentage of defects over components\footnote{hongyu: your text said modules. did you mean
components?}:
\bi
\item
 We find that the top 5\% ``most
defective'' CM1 components contain 68.57\% of the defects, the top 10\% ``most
defective'' CM1 components contain 100\% of the defects. 
\item
For KC1, the top 5\%
components contain 55.81\% defects and the top 10\% components contain
77.90\% defects. 
\ei
We obtained similar results for other NASA
projects.

This distribution follows the 
Weibull distribution. The CDF (cumulative density
function) of the Weibull distribution can be formally defined as:

\begin{equation}
P(x ) = 1 - exp \left(- \left(\frac{x}{\gamma}\right)^{\beta}\right)
\end {equation}

Using a statistical package such as SPSS, we are able to perform
non-linear regression analysis and derive the parameters for each
distribution. To statistically compare the goodness-of-fit of the
Weibull distribution, we compute the coefficient of determination
($R^2$) and the Standard Error of Estimate (Se). \fig{w}  summarizes
the Weibull parameters and the accuracy measures. The $R^2$ values
ranging from 0.979 to 0.994 and Se values ranging from 0.009 to
0.025, confirming the Weibull distribution of defects.
In summary, most of the defects are found in the  minority of components.

\begin{figure}[!t]
\small\renewcommand\arraystretch{1.1}%
%\caption{The Weibull distribution of NASA defects across
%modules}\label{tab:metrics}
\begin{center}
\begin{tabular}{|l|l|l|l|l|}
\hline
\textbf{Project} & \textbf{$\gamma$} & \textbf{{$\beta$}} & \textbf{$R^2$} & \textbf{Se}\\
\hline
JM1 & 0.076 & 0.965 & 0.979 & 0.025\\
\hline
KC1 & 0.067 & 1.313 & 0.994 & 0.013\\
\hline
KC3 & 0.030 & 0.950 & 0.987 & 0.009\\
\hline
PC4 & 0.049 & 0.960 & 0.986 & 0.016\\
\hline
PC5 & 0.011 & 1.045 & 0.994 & 0.006\\
\hline
MC1 & 0.011 & 1.736 & 0.991 & 0.007\\
\hline
\end{tabular}
\end{center}
\caption{Matching Defect Distributions to the Weibull function.}\label{fig:w}
\end{figure}

\subsection{The Experiment}
The goal of this experiment is to assess the value of component-level, rather than project-level,
training for defect predictors. For the component-level training, we will favor training data from
components with higher than usual defect frequencies.

Five NASA defect data sets from the PROMISE repository were used:
CM1, KC1, MC1, PC1, PC3. These data sets
were chosen because:
\bi
\item
They have been studied in the field extensively;
\item
They are widely available to the PROMISE community;
\item They are projects which divide into numerous components.
\ei
For each data set, components were extracted (using a unique identifier)
containing both defective and non-defective modules (also labeled
with a unique value). 
The subset of components with higher-than-usual defect densities were extracted as follows:
\bi
\item
If the number of defective modules
per component exceeds the median number of defects across $all$
components in that data set, it is labeled as a defect-$dense$
component.
\ei
For example, in \fig{kc1-defects} the bottom horizontal
line represents the median number of defects in the KC1 data set.
Thus, those components lying under this line are not used in further
stages of the experiment, and so are denoted as $sparse$ components.
\begin{figure}
\begin{center}
%\includegraphics[width=4in]{hongyu/figures/cs-kc1-dist.pdf}
\includegraphics[width=3in]{kc1distsnap.png}
\caption[Component defect distribution example]{Defect distributions of components found in the KC1 data set. Note that only a small number of components contain a relatively high number of defects.}\label{fig:kc1-defects}
\end{center}
\end{figure}

The pseudocode in \fig{dense-comp-experiment} illustrates the
remaining setup of the experiment:
Lines 1 and 5 of \fig{dense-comp-experiment} illustrate the use of
the 10 X 10-way cross validation used in the experimental process.
The standard 10 X 10-way cross validation operates by selecting
90\% of the data randomly for training, and the remaining 10\% for
testing 
(this process is then repeated 10 times  to guard against order effects).
Since the objective
is to analyze the performance of training on modules in components
containing a high number of defects compared to standard methods
of training on all components, a minute alteration was made to 
cross-validation for this experiment. A ``pool'' of training data was
constructed by focusing on only those instances $within$ a dense
component, as in line 3 of the pseudocode. The available pool of
testing instances, thus, are gathered from the $remaining$ components
in the data set (line 4). This is employed to prevent training and
testing on modules within the same component. Lines 6 and 7 illustrate
collecting 90\% of the current dense component's instances as the
final training set $Train'$, and 10\% of the modules from the
available instances in components $not$ labeled dense as $Test'$.
\begin{figure}
{\small
\begin{verbatim}
1 For run = 1 to 10
2   For each dense component C in data set D
3     Train = C
4     Test  = D - c
5     For bin = 1 to 10
6        Test'  = 10% of Test (picked at random)
7        Train' = Train - Test'
8        Naive Bayes (Train', Test')
9     end bin
10   end component
11 end run
\end{verbatim}}
\caption[Training on Dense Components Vs. All Components]{Training on dense components versus all components. The experiment performs training on modules residing in dense components, and testing on modules contained in all other components in the data set.}\label{fig:dense-comp-experiment}
\end{figure}

%While this represents a slight modification to the standard practice
%of performing a cross-validation, it is within our engineering
%judgement to apply techniques that best mimic current methods in
%an area of experimentation still in its infancy. Thus, the recentness
%of this specific branch of research invites further techniques to
%be discovered and implemented.
%
Line 8 of \fig{dense-comp-experiment} executes the classifier (in
this case, Naive Bayes) on the previously created training and
testing sets $Train'$ and $Test'$. The Naive Bayes classifier was
utilized because of its speed, and also for the fact that it has
been shown to perform well on PROMISE defect data against other
learners ~\cite{lessmann08}.

Determining a possible benefit of training our classifiers using fewer, but more densely-packed components also requires the comparative analysis of learning on all components (and thus all modules). Comparisons are made between each approach, and the results are shown in the following section.
\input{datatable}

\subsection{Results}

The metrics used in the analysis of comparing results from training on dense components over the traditional method of using all components in the data set are $recall$, $pf$ and $precision$. 

%If $A$,$B$,$C$, and $D$ denote the true negatives, false negatives, false positives and true positives (respectively) found by a classifier, then:

%\begin{equation}
%pd = Recall = \frac{D}{(B+D)}
%\end {equation}

%and

%\begin{equation}
%pf = \frac{C}{(A+C)}
%\end {equation}

%and

%\begin{equation}
%precision = \frac{D}{(D+C)}
%\end{equation}

%Therefore, $pd$ and $precision$ values are best if maximized, while $pf$ results should be minimized.
\begin{figure}
\scriptsize
\begin{center}
\begin{tabular}{l@{~}|l@{~}|r@{~}r@{~}@{~}r@{~}|c}
%\multicolumn{2}{c}{~}&\multicolumn{5}{c}{quartiles}\\\cline{3-5}
%&min& & median & &max\\\cline{3-5}
\multicolumn{2}{c}{~}&\multicolumn{3}{c}{recall}&2nd quartile\\
\multicolumn{2}{c}{~}&\multicolumn{3}{c}{percentiles}&median,\\\cline{3-5}
Rank&Treatment& 25\%& 50\% & 75\%&3rd quartile\\\hline
1&Train on Dense Components& 31& 69& 91&  \boxplot{0}{31}{69}{91}{3}  \\
2&Train on All Components& 35& 71& 93&  \boxplot{0}{35}{71}{93}{3}    \\ \hline
\multicolumn{5}{c}{~}&~~~~~0~~~~~~~~50~~~~100
\end{tabular}
\end{center}
\caption[Dense Component vs. All Component learning - $recall$ - All Data]{$Recall$ values for learning on dense components compared to learning on all components across all data sets, sorted by statistical ranking via a Mann-Whitney test at 95\% confidence.}\label{fig:pds-all}
\end{figure}
\begin{figure}
\scriptsize
\begin{center}
\begin{tabular}{l@{~}|l@{~}|r@{~}r@{~}@{~}r@{~}|c}
%\multicolumn{2}{c}{~}&\multicolumn{5}{c}{quartiles}\\\cline{3-5}
%&min& & median & &max\\\cline{3-5}
\multicolumn{2}{c}{~}&\multicolumn{3}{c}{pf}&2nd quartile\\
\multicolumn{2}{c}{~}&\multicolumn{3}{c}{percentiles}&median,\\\cline{3-5}
Rank&Treatment& 25\%& 50\% & 75\%&3rd quartile\\\hline
1&Train on Dense Components& 0& 15& 52&  \boxplot{0}{0}{15}{52}{3}  \\
1&Train on All Components& 0& 26& 65&  \boxplot{0}{7}{26}{65}{3}    \\ \hline
\multicolumn{5}{c}{~}&~~~~~0~~~~~~~~50~~~~100
\end{tabular}
\end{center}
\caption[Dense Component vs. All Component learning - $pf$ - All Data]{$PF$ values for learning on dense components compared to learning on all components across all data sets, sorted by statistical ranking via a Mann-Whitney test at 95\% confidence.}\label{fig:pfs-all}
\end{figure}
\begin{figure}[!t]
\scriptsize
\begin{center}
\begin{tabular}{l@{~}|l@{~}|r@{~}r@{~}@{~}r@{~}|c}
%\multicolumn{2}{c}{~}&\multicolumn{5}{c}{quartiles}\\\cline{3-5}
%&min& & median & &max\\\cline{3-5}
\multicolumn{2}{c}{~}&\multicolumn{3}{c}{precision}&2nd quartile\\
\multicolumn{2}{c}{~}&\multicolumn{3}{c}{percentiles}&median,\\\cline{3-5}
Rank&Treatment& 25\%& 50\% & 75\%&3rd quartile\\\hline
1&Train on All Components& 20& 78& 95&  \boxplot{0}{20}{78}{95}{3}  \\
1&Train on Dense Components& 12& 75& 96&  \boxplot{0}{12}{75}{96}{3}    \\ \hline
\multicolumn{5}{c}{~}&~~~~~0~~~~~~~~50~~~~100
\end{tabular}
\end{center}
\caption[Dense Component vs. All Component learning - $precision$ - All Data]{$Precision$ values for learning on dense components compared to learning on all components across all data sets, sorted by statistical ranking via a Mann-Whitney test at 95\% confidence.}\label{fig:prec-all}
\end{figure}


\fig{pds-all}, \fig{pfs-all} and \fig{prec-all}
show statistical
rankings of each treatment, as well as {\em quartile charts} displaying
the median and variance of each metric for the $combined$ data sets,
as a whole, used in the experiment:
\bi
\item
 The black circle in the center
of each plot is the median;
\item
 The line going from left
to right from this circle shows the second and third quartile
respectively. 
\item
Each chart is  $ranked$ (see left-hand-side column) by a Mann-Whitney test (95\% confidence).
\ei
We prefer quartile charts of performance to other
summarization methods for a multitude of studies, as they offer a
very succinct summary of a large number of experiments.

Over all the data sets studied here,
training on dense components (those containing a higher
number of defective modules)
yields similar medians (for $recall$ and $precision$); 
while $precision$.
However, dramatic gains are seen with
$pf$: the median error rates decrease by nearly \underline{half}.

The overall results of
\fig{pds-all}, \fig{pfs-all} and \fig{prec-all} obscure some interesting
effects. If we look at the results for individual data sets,
as shown in
\fig{metrics},  a more interesting result appears.
This figure is divided into our five data sets (CM1, KC1, MC1, PC1, PC3),
our three evaluation criteria (recall, pf, precision), and our
two treatments ($dense$, $all$).
Quartile charts are shown, along with a statistical analysis
that ranks pairs of treatments:
\bi
\item
 If two treatments score $1,1$, then
their is no statistically significant different in their performance.
\item
If two treatments score $1,2$, then they are statistically different
and the first one has a better median than the other.
\ei
A summary of these statistical rankings is shown in \fig{plus-minus}.
Each treatment is assigned one of $\{+,0,-\}$ depending
on if it won,tied,lost in the statistical rankings of \fig{metrics}
(based on a Mann-Whitney test at 95\% confidence). 
For example, in CM1:
\bi
\item
 The two treatments tied on precision;
\item
Training on $all$ produced a better $recall$ than training on $dense$;
\item
Training on $dense$ produced a better $pf$ than training on $all$.
\ei
The bottom of \fig{plus-minus}
shows a summary of these comparisons:
$dense$ losses far less than $all$ ($1/15$ times vs $10/15$ times).

In summary, in the majority case, training on $dense$ components
yielded statistically significantly better detectors than training on
$all$ components.

\begin{figure}
\small
\begin{center}
\begin{tabular}{|c|r|c|c|}\hline
data & performance & all & dense \\
set & measure & components& components\\\hline
CM1&	precision&	0&	0\\
	&	recall&			+&	-\\
	&	pf&			-&	+\\\hline
KC1&	precision&	0&	0\\
	&	recall&			-&	+\\
	&	pf&			-&	+\\\hline
MC1&	precision&	0&	0\\
	&	recall&			-&	+\\
	&	pf&			-&	+\\\hline
PC1&	precision&	-&	+\\
	&	recall&			-&	+\\
	&	pf&			+&	-\\\hline
PC3&	precision&	-&	+\\
	&	recall&			-&	+\\
	&	pf&			0&	0\\\hline\hline
summary& +&         1& 10\\
       &0 &         4& 4\\
       &- &        10& 1\\\hline         
\end{tabular}
\end{center}
\caption[Dense vs. All Component Learning - all metrics per data
set.]{Each treatment is assigned one of $\{+,0,-\}$ depending
on if it $won,tied,lost$ in the statistical rankings of Table~1
(based on a Mann-Whitney test at 95\% confidence). 
Note that $dense$ lost far less than $all$ ($1/15$ vs $10/15$).
}\label{fig:plus-minus}

\end{figure}
\section{Conclusion}
A previously unexplored feature of the PROMISE defect data sets
are the small number of components containing most of the defects.
This skewed defect distribution implies a systematic error in our data
analysis of the PROMISE defect datasets. We have been reporting $neg/pos$ ratios
for those data sets as varying from 1 to 249 (see \tion{bal}). This statistic is
clearly incorrect since it is a mean value across a highly skewed distribution:
\bi
\item An entire {\em project} like KC1 may have a overall $neg/pos$ ratio.
\item This mean ratio characterizes very little about the $neg/pos$ ratio of individual components.
\ei


Mathematically, this skewed distribution is an interesting region of the data since such
components have lower $neg/pos$ ratios which, according to the maths
of \tion{bal}, means that they could (in theory) yield detectors
with high precision and recall.

To test this possibility, we restricted training to just the components
with higher than the median number of components.
This was compared to training using all the data (which, according
to our understanding of the literature, is the more usual treatment).

We found that 
training via $dense$ sampling
is useful for generating better defects. 
The improvements are not startlingly better:
and the newly
achieved recall and precision  mean values that are close to standard practice
(see \fig{metrics}).
Nevertheless, the improvements  are a clear effect that occurred in most of the examples
explored above $11/14$. Given the simplicity of the technique (just select training data from a subset
of the components), we see reason {\em not} to recommended density-sampling whenever it becomes
apparent that components have different defect densities. 

This result has negative and positive implications.
On the positive side,  we have shown here that the skewed defect distributions within a project can be exploited
to generate better defect predictors.

On the negative side, it means that there are aspects of the PROMISE data sets that
have not been missed in dozens of prior publications. The PROMISE repository data is used
widely in the literature, usually in papers of the form ``here is a new learner applied
to data sets X,Y,Z from PROMISE''. Such papers may be so focused on the {\em learner} that they
miss important aspects of
the {\em data}. 
In the future, we would recommend visualizations of data {\em before} applying data miners,
lest we miss other important aspects of our data.
%ACKNOWLEDGMENTS are optional
\section*{Acknowledgments}
This work was partially funded by the United Stated National Science Foundation (CCF-1017263).
%
% The following two commands are all you need in the
% initial runs of your .tex file to
% produce the bibliography for the citations in your paper.
\bibliographystyle{abbrv}
\bibliography{timm1,timm2,hongyu/refs}
\end{document}
