%\documentclass[onecolumn,draftcls,journal,compsoc]{IEEEtran}
%\documentclass[technote]{IEEEtran}
\documentclass[twocolumn,technote,9pt,compsoc]{IEEEtran}
\usepackage{graphicx}
\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 v4}}}}}
\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}

\begin{document}

\title{Cross- vs Within-Company Defect Prediction Studies}

\author{Tim~Menzies,~\IEEEmembership{Member,~IEEE,}
Burak Turhan,~\IEEEmembership{Student Member,~IEEE,}
        Ayse Bener,~\IEEEmembership{Member,~IEEE,} and 
		Justin~Distefano
\thanks{Dr. Menzies,  Mr. Distefano
are with the Lane Department of Computer Science and Electrical Engineering, West Virginia
University.
Mr. Distefano is also Chief Programmer and Integrated Software Metrics.
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/07interra.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.}}: Cross- vs Within-Company Defect Estimation Studies}

%We found that the cross-company model provided poor 
%predictions for the single-company projects and much worse 
%predictions than the single-company model.
\maketitle

\begin{abstract}
Part of good research is knowing what questions to ask, and when to ask them.
In a May 2007 IEEE TSE article,
Kitchenham et.al. pose a timely question: when should companies 
learn from their own data, and when should they use someone else's?

Kitchenham et.al. explored 
{\em effort estimation}. 
XXXX and found little stability.
XXXX very different picture w.r.t. defect prediction (diversity of attributes- note
that mendes had strict data collection controls and reported a great icnrease. perhaps
to key to udnerstanind WC-vs CC is to first restrict the data dictionary

This paper  explores cross-vs within-company static
code data
for {\em defect prediction}.
Cross-company learning will be found to be indicated for mission critical software
were the extra costs associated with high false alarm rates  
are compensated by an associated increase the probability of detecting fault
modules.

For other classes of software, 
false alarm rates can be decreased using a small amount of local data (often,
just 100 modules).
In our experiments, the use of
within-company data halved the false
alarm rate while only decreasing detection rates by only $\approx10\%$.
Hence, for non-mission-critical software,
we strongly recommend the use of within-company data.
\end{abstract}

%------------------------------------------------------------------------- 

\section{Introduction}
In the age of open source development, web-accessible XML data, mash-ups, and
reusable
libraries of SE data, it is quite possible that organizations can access more
data on software engineering
{\em outside} their company than {\em within}.
It is hence tempting to use such {\em cross-company} data since, as
Kitchenham et.al.~\cite{kitch07}  observe:
\bi
\item
The time required to collect enough data on past projects from within a  company
may be prohibitive.
\item
By the time enough data is collected with within a company,
technologies may have changed so older
projects may not represent current practice.
\ei

In the case of software effort estimation
the value of using such external data is an open
question.  
In one case study, Mendes et.al.~\cite{mendes07} found within-company data
performed much better than cross-company data for predicting
estimation effort of web-based projects.  They only recommend using
cross-company data in the special case when that ``data is obtained
using rigorous quality control procedures''.  
A similar conclusion was reached by Abrahansson et.al.
who  discussed learning effort predictors in the context
of an agile development process~\cite{abrahamsson07}. They strongly advocate
the use of WC-data.

Other studies are not so positive.
MacDonnel and Shepperd tried
to find trends in a set of papers relating to project management and effort estimation~\cite{macdonell07}. However, the
 papers studied by MacDonnel and Shepperd used a wide range of data
sets so these authors found it hard to offer  a definitive combined
conclusion.  
In other work, after a review of numerous case studies, Kitchenham
et.al.~\cite{kitch07} concluded that the value of CC vs WC data for effort estimation
is
unclear: \begin{quote} {\em 
{\ldots}some organizations would benefit from using models derived from
cross-company benchmarking databases but others would not.}~\cite{kitch07}.
\end{quote}

While the effort estimation results are ambiguous, the defect prediction results
are not. This paper reports a CC-vs WC-data study on the 12 tables
of defect data
shown in
\fig{data}. 
In this data, the relative merits of CC-vs-WC is clear and unambiguous, as revealed
by two experiments.
The first
experiment concerns cross-company data and will show how cross-company data
increases the probability of detecting a module
($pd$) dramatically at the cost of increasing the probability of false alarms ($pf$).
When such large $pf$s are unacceptable, companies must take the time to collect
within-company data. 

The second experiment explores how {\em little}  within-company data.
is required to learn useful predictors.
We will show that, often,
the detectors learned from a 
mere one hundred examples  perform as well as detectors learned from many more examples.
Hence, there are
two reasons not to use cross-company data for learning defect predictors:
\bi
\item Detectors tuned to the particulars of one company can
be learned using very little data, collected in a very small amount of time;
\item  Using within-company data  avoids the problem of high false alarm rates.
\ei
\begin{figure}[!t]
\scriptsize
\begin{center}
\begin{tabular}{l|lrrr@{.}l}
     &          & (\# modules)         &          &  &\\
data & language & examples & features  & \multicolumn{2}{c}{\%defective}\\\hline
pc5  & C++ & 17,186   & 38          & 3&0\\
mc1  & C++ & 9,466    & 38          & 0&71\\
pc2  & C++ & 5,589    & 36          & 0&41 \\
pc3  & C++ & 1,563    & 37          & 10&23\\
pc4  & C & 1,458    & 37          & 12&2\\
pc1  & C++ & 1,109    & 21          & 6&94\\
kc1  & C++ & 845      & 21          & 15&45\\
kc2  & C++ & 522      & 21          & 20&49\\
cm1  & C++ & 498      & 21          & 9&83\\
kc3  & JAVA & 458      & 39          & 9&38\\
mw1  & C++ & 403      & 37          & 7&69\\
mc2  & C++ & 61      & 39          & 32&29\\\cline{3-3}
     \multicolumn{2}{c}{~}     &  39,158 

\end{tabular}
\end{center}
\caption{Twelve tables of data, sorted in order of number of examples.
For details on this data, see the appendix.}\label{fig:data}
\end{figure} 



The rest of this paper discusses the data of \fig{data} and reviews the design and results
of the two experiments.
An important aspect of this work is its 
{\em reproducibility}.
All the data used in this study is freely available, on-line\footnote{\url{http://promisedata.org/repository}}.
Reproducibility
is an important methodological principle in other disciplines since it allows a community to confirm,
refute, or even improve prior results. 
In our view, in the field of software engineering,
there are all too few examples of reproduced and extended results.
We would strongly encourage software engineering researchers
to share data, define challenges, and to
take the time to rework the results of others.

\section{Background}

The \fig{data} data
comes from
12
NASA systems.  These systems were developed
 in
different geographical locations across North America.
Within a system, the sub-systems
shared some common code base but did not pass personnel or code
between sub-systems. 

The external validity of generalizing from NASA examples
like \fig{data}
has been discussed elsewhere~\cite{me07b}. In summary, 
NASA makes extensive use of
contractors who are contractually obliged (ISO-9O01) to demonstrate
their understanding and usage of current industrial best
practices. These contractors service many other industries;
for example, Rockwell-Collins builds systems for many government and
commercial organizations.  For these reasons, other noted researchers
such as Basili, Zelkowitz, et al.~\cite{basili02} have argued that
conclusions from NASA data are relevant to the general software
engineering industry.

At first glance, this data  appears to come from one company (NASA). However, that 
``company''
is really an umbrella organization that the American government uses to fund
a large and diverse set of organizations. All the \fig{data} was built by different
groups, often at different geographical locations, usually for different tasks.
That is, this data satisfies Kitchenham et.al.'s definition of ``cross-company'' data.

Previously~\cite{me07b}, we have explored the drawbacks and advantages of learning
module defect predictors from static code features.
To learn such predictors,  tables of examples are formed (like those in \fig{data})
where one column has a boolean
value for
``defects detected'' and the other columns describe static code features
such as  lines of code,
number of unique symbols, or max. number of possible execution pathways. 
Each row in the table holds data from one ``module''; i.e.
the smallest unit of functionality.
Depending
on the language, modules may be called ``function'', ``method'' or ``procedures''.


The data mining task is to learn combinations of the code features that best predict
for the value in the defects column.
The results of such data mining should be baselined against known industrial best practices:
\bi
\item
Raffo found that the defect detection capability of
current 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.
\item
Similar conclusions were made at a
 panel at IEEE Metrics 2002. That panel
declined to endorse claims by
Fagan~\cite{fagan86} and Schull~\cite{shull00a} regarding the efficacy of their
inspection or directed inspection methods. Rather, it
concluded that
manual software reviews
can find ${\approx}60\%$ of defects~\cite{shu02};
\ei
We have shown that automatically learned defect predictors perform better
than these two baselines~\cite{me07b}.
On tables of  NASA examples, our new 
defect predictors had 
a  probability of detection ($pd$) and probability of false alarm ($pf$) of
\[mean(pd,pf)=(71\%,25\%)\]
It is difficult to compare these results
with those
reported by Raffo or those reported at the 2002 IEEE Metrics since they were collected
by  a variety of different methods. The least we can say is that automatically generated
defect detectors do not appear to perform {\em worse} than industrial averages and
might even perform somewhat better. Also, while the manual methods require manual effort,
our defect detectors can be automatically and rapidly
learned, then quickly and cheaply applied to very large
libraries of code.


In any case,  according to the terminology of Kitchenham et.al. our prior work was a within-company (WC)
study: 
the new defect predictors were learned
on 90\% of the rows in one table
(selected at random)
then tested on the remaining rows in that table.
The rest of this paper extends our methodology to the study of the relative
merits of within-vs cross-company data for defect prediction.

\section{Experiment \#1: WC-vs-CC}
\subsection{Design}
Our first WC-vs-CC experiments repeated the following procedure
for all  12 example tables of \fig{data}.
For each table,
test sets were built from
10\% of the rows, selected at random.  Defect
predictors were then learned from:
\bi
\item Treatment 1 (CC): all rows from the other 11 tables.
\item Treatment 2 (WC):  just the other 90\% rows of this table;
\ei
Most of the \fig{data} tables comes from systems written in ``C/C++''
but at
least of one of the  system was written in JAVA.
For cross-company data, an industrial practitioner may not have access to 
detailed meta-knowledge (e.g. whether it was developed in ``C'' or JAVA).
They may only be aware
that data, from an unknown
source, is available for download from a certain url.
To replicate that scenario,  we will make no
use of our meta-knowledge about \fig{data}. As we shall see, 
a clear stable effect will occur
across all the tables, regardless of (say) the implementation language.

In order to control for   {\em order effects} (where the 
learned theory is unduly affected by the order of the examples)
the entire procedure was repeated 10 times
where, each time, the order of the rows in the table was randomized.
In all, we ran 1200 experiments to compare WC-vs-CC:
\[\left(\mbox{10*10\% test sets}\right) * \left(\mbox{10 randomized orderings}\right) * \left(\mbox{12 tables}\right)\]

All the numeric distributions in the \fig{data}
data
are exponential. A ``log-filter'' replaces all numerics $N$ with $log(N)$.
This 
spreads out exponential
curves more evenly across the space from the minimum to maximum values
(to avoid numerical errors with  $ln(0)$,
all numbers under 0.000001 are replaced with  $ln(0.000001)$). 
This ``spreading'' can significantly
improve the effectiveness of data mining~\cite{me07b}.

In prior work we have explored a range of data mining methods
for defect prediction and found that
classifiers based on Bayes theorem work best for the \fig{data} data~\cite{me07b}.
This theorem 
offers a relationship between  fragments of evidence $E_i$,
a prior probability for
a class $P(H)$, and a posteriori  probability
$P(H|E)$: 
\[
P(H|E)=P(H)/ P(E)\prod_iP(E_i|H)
\]
When building defect detectors,
the
posterior probability of each class (``defective'' or ``defect-free'')
is calculated, given the features
extracted from a 
module.
The module is assigned to the possibility
with the highest probability.  
For
numeric attributes, 
a feature's mean $\mu$ and standard deviation $\sigma$ is used in
a
Gaussian  probability
function~\cite{witten05}:
\[f(x) =
1/(\sqrt{2\pi}\sigma)e^{-\frac{(x-\mu)^2}{2\sigma^2}}\] 
Data mining effectiveness was measured using $pd$, $pf$ and $balance$.
Let $\{A,B,C,D\}$ denote the
true negatives, 
false negatives, 
false positives, and 
true positives
(respectively) found by a defect predictor.
From these:

{\footnotesize
\begin{eqnarray}
pd=&recall=&D/(B+D)\\
pf=&&C/(A+C)\\\label{eq:bal}
bal=&balance=&1 - \frac{\sqrt{\left(0 - pf\right)^2 + \left(1 - pd\right)^2}}{\sqrt{2}}
\end{eqnarray}
}
All these values range zero to one.
Better and {\em larger} balances fall  {\em closer} to the desired  zone 
of no false alarms ($pf=0$) and 100\% detection ($pd=1$).

Other commonly used measures such as $accuracy$  and $precision$
were not used since, as shown in \fig{data}, the percent of defective examples
in our tables was usually very small (median value around 8\%).
Accuracy and precision
are poor indicators
of performance for data were the target class is so rare
(for more on this issue, see~\cite{me07b,me07e}). 

The WC and CC results were visualized using
{\em
quartile charts}.  To generate these charts, the performance
deltas for some treatment
are sorted to isolate the median and the lower and upper quartile of numbers.
For example:

\[
{\footnotesize
\{\overbrace{4,7,15}^{q1},20,31,\overbrace{40}^{median},52, 64, \overbrace{70,81,90}^{q4}\}}
\]

In our quartile charts,
the upper and lower quartiles are  marked with black lines;
the
median is marked with a black dot; and
vertical bars  are added to
mark the zero value.
The above numbers
would therefore be drawn as follows:


{\small
\[0\%\; \boxplot{4}{11}{40}{70}{20}\; 100\%\]}

The Mann-Whitney U test~\cite{mann47} was used to test
for statistical difference between treatments.
This is a non-parametric test that replaces all (e.g.) $pd$ values with their
rank inside the population of all observed and sorted $pd$ values. The U tests then checks
if the median rank of the WC treatments
 were equal, less then, or greater than the CC treatments.
Such non-parametric tests are recommended in data mining since many of the performance
distributions are non-Gaussian~\cite{demsar06}. 

We report one deviation from our prior procedure. The tables of data 
come from different sources and, hence,
have different features. For this study, all the tables were pruned such
that they only contained features that appear in all the twelve tables (see appendix).

\subsection{Results from Experiment \#1}

\fig{ccwsnum} shows the $\{pd,pf\}$ quartile charts for CC vs WC data.
The trend is very clear: CC data dramatically increases {\em both}
the probability of detection and the probability of false alarms. The $pd$
results are particularly striking. For cross-company data:
\bi
\item 25\% of the $pd$ values are at 100\%.
\item 50\% of the $pd$ values are above 90\%
\item 75\% of the $pd$ values are at or above 80\%;
\item And all the $pd$ values are at or over 50\%.
\ei
By way of comparison, recall from the above that
than our previous result had a  average $pd$ of $71\%$~\cite{me07b}.

To the best of our knowledge, \fig{ccwsnum} are the largest $pd$ values ever reported
from this data.
However, these very high $pd$ values come at some considerable cost. Note in \fig{ccwsnum}
that the median false alarm
rate has changed from 26\% (with WC) to 52\% (with CC) and the maximum $pf$ rate
now reaches 100\%.

Once a {\em general result} is defined (e.g. CC dramatically
increases both $pf$ and $pd$), it is good practice to check for specific exceptions
to that pattern.
The following notes 
perform that check. In summary, while some exceptions exist, the general result
holds in the majority of cases.

\fig{ccwsnum} shows
results 
from all tables.
\fig{ccwc} shows a summary of results when the U test (95\% confidence)
was applied to
test results from each of the 12 tables,  in isolation. 
In the majority case ($\frac{8}{12}$, see group $a$), the general pattern repeats where
using CC instead of WC increases both $pd$ and $pf$ (see group $a$). 
In one case (see group $b$), there was no difference in the results of the different
treatments. In another case, two tables of data (see group $c$) saw no change to
$pd$ but the false alarm grew worse.
In only one case was there a clear contradiction to the majority
case. In group $d$, which only contains the $pc5$ table, using cross-company data
made the $pf$ better (decreased it) at the
cost of also decreasing the $pd$.
In summary, the {\em general result} 
holds in the majority of cases and is only clearly contradicted in the $pc5$ table.

We explain these increases in $pd,pf$ with the following speculation.
Using  a large training set (e.g. eleven of the tables in \fig{data}) informs
not only all the causes of errors, but
also of numerous irrelevancies (e.g. applying statistics gathered from JAVA
programs to ``C'' programs).  Hence, large training sets increase the probability
of detection (since there are more known sources of errors) as well
as the probability of false alarms (since there are more extraneous factors
introduced to the analysis).

As to the contradictory $pc5$ result, 
recall from \fig{data} that this table is the far and away the largest data set used
in this study. $Pc5$ contains $\frac{17,186}{39,158}=43\%$ of the modules, in a single
data set.
Cross-company effects may be invisible when relatively small number of examples
are added to a data set. Hence, it is not
surprising that effects seen in the other, much smaller,
tables of data do not hold in such an exceptionally large table of data.
\begin{figure}[!t]
\begin{center}
{\scriptsize
\begin{tabular}{r@{}r|r@{~}r@{~}r@{~}r@{~}r@{~}|l}
&treatment & min & Q1 & median & Q3 & max  \\\hline
 pd & CC&       50&  80&  91&  100& 100& \boxplot{50}{30}{91}{100}{0}\\
 & WC&       17&  67&  80&   88& 100& \boxplot{17}{50}{80}{88}{12}\\\hline
 pf & CC&        4&  26&  52&   73& 100& \boxplot{4}{22}{52}{73}{27}\\
 & WC&        0&  17&  26&   33&  73& \boxplot{0}{17}{26}{33}{40}\\
\hline\end{tabular}
}
\end{center}
\caption{Experiment \#1 results.
Numeric results on left; quartile charts on right. ``Q1'' and ``Q3'' denote
the 25\% and 75\% percentile points (respectively). }\label{fig:ccwsnum}
\end{figure}
\begin{figure}
\begin{center}
{\footnotesize
\begin{tabular}{|r|c|c|p{2cm}|l|}\hline
%pd(inter) vs  & pf(intra) vs & &  \\
&$pd$    & $pf$ & &  \\
group & $WC \rightarrow CC$    &  $WC \rightarrow CC$& tables & $|tables|$ \\\hline\hline
a& increased               &        increased & CM1 KC1 KC2 MC2 MW1 PC1 PC3 PC4 & 8\\\hline
b& same                    & same             & KC3& 1\\\hline
c& same                    &  increased            & MC1 PC2 &2\\\hline
d& decreased      		 & decreased        &     PC5 &1\\\hline
\end{tabular}}
\end{center}
\caption{U test results (95\% confidence): moving from WC to CC}\label{fig:ccwc}
\end{figure}



\subsection{Discussion of Experiment \#1}
When practitioners use defect detectors with high false alarm rates,
they must allocate a large portion of their debugging budget to 
the unfruitful exploration of erroneous alarms.
Hence:
\bi
\item
 For most software applications, very high  $pf$ rates like the CC results
of \fig{ccwsnum} make the detectors impractical to use.
\item
Therefore, we can only recommend cross-company learning 
for mission critical software
were the extra costs associated with high false alarm rates  
are compensated by the associated increase in software assurance.
\ei
When budgetary considerations restrict the exploration of numerous false
alarms,  projects seek detectors with lower $pf$ values and adequate $pd$
values. Our next experiment addresses this concern.



\section{Experiment \#2: Incremental WC }
\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 only
contains 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 of \fig{data}
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).


\subsection{Results from Experiment \#2}
Recall that
\eq{bal} defined ``balance'' to be a combination of $pf$ and $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 detector.
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
\subsection{Discussion of Experiment \#2}
In the majority case, predictors learned from as little as one hundred
examples perform as well as predictors learned from many more examples.
This suggests that the effort associated with learning defect predictors
from within-company data may not be overly large.
For example, \fig{estimate} estimates that the effort required to build and test
100 modules may be as little as 2.4 to 3.7 months.

\begin{figure}
\scriptsize
\begin{tabular}{|p{.95\linewidth}|}\hline
100  modules may take as little as two to four months to construct. This estimate
was generated as follows:
\bi
\item
In the $cm1$ data base, the median module size is 17 lines. 100 modules therefore
take 1700 lines.
\item
To generate an effort estimate for these modules,
we used the on-line COCOMO~\cite{boehm00a} effort estimator (\url{http://sunset.usc.edu/research/COCOMOII/expert_cocomo/expert_cocomo2000.html}). Estimates were generated
assuming the required reliability for the module varied from very low to very high.
\item
The resulting estimates ranged from
between 2.4 and 3.7 person months to build and test those modules.
\ei\\\hline
\end{tabular}
\caption{An estimate of the effort required to build and test 100 modules.}\label{fig:estimate}
\end{figure}


At first glance,it may seem quite remarkable
that such small training sets (as few as 100 examples)
works so well. However, on reflection, these  results are not too surprising:
\bi
\item
All these experiments use very simplistic static code measures such as lines of code, number of
unique symbols in the module, etc.  
\item
Such simplistic static code attributes 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}.  
\item We would characterize such static code measures as having 
{\em limited information content}. 
Limited content
is soon exhausted by repeated sampling.
Hence, such simple measures reveal all they can reveal after
a small sample
\ei

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 (but not for the defect prediction task):
\bi
\item
In their discussion on how to best handle numeric attributes, 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 found 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
\begin{figure}
\begin{center}
\includegraphics[width=2.5in]{plateaus/plateaudots.pdf}
\includegraphics[width=2.5in]{plateaus/plateaudotsC.pdf}
\end{center}
\caption{Y-axis shows plateau point after learning from data sets that have up to $X$
examples. 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}.
From~\cite{orrego04}.
}\label{fig:plateau}
\end{figure}

%\input{exp3}

%The 
%The results of the above procedure fall into the four groups of \fig{ccwc}.
%In the usual case ($\frac{8}{12}$),
%moving from within-company (WC) to cross-company (CC) data significantly
%increased {\em both}
%probabilities of detection $pd$ and false alarm $pf$.
%The size of $pd$ increase was quite remarkable. \fig{ccwcnums}
%
%The following chart shows that across our 12 data sets,
%the top quarter of the $pd$s in the inter-experiment were all in the maximum range of $pd=100\%$.
%As predicted by \fig{typical}, the price of this dramatic increase in $pd$ is an near doubling
%of the median $pf$: 
%
%~\\
%
%The increase in individual 
%data sets was even larger. For example, in $KC2$, the median $pf$ rose from 73 to 91\% while
%the median $pf$ rose from 31\% to 64\%:
%
%%\section{Group D- eight examples such as ``KC2''}
%{\scriptsize
%\begin{tabular}{r|r@{~}r@{~}r@{~}r@{~}r@{~}|l|}\cline{2-6}
% & min & q1 & median & q3 & max  \\\cline{2-7}
%pd / inter &  82 &  91 &  91 & 100 & 100 & \boxplot{82}{9}{91}{100}{0}\\
%pd / intra &  55 &  73 &  73 &  82 &  91 & \boxplot{55}{18}{73}{82}{9}\\
%pf / inter &  57 &  62 &  64 &  74 &  81 & \boxplot{57}{5}{64}{74}{7}\\
%pf / intra &  14 &  24 &  31 &  33 &  45 & \boxplot{14}{10}{31}{33}{12}\\
%\cline{2-7}\end{tabular}
%}
%
%~\\
%
%In one data set,  a completely opposite effect was observed to the main effect.
%In ``PC5'', the inter-experiment made the the $pd$ worse
%and the $pf$ better:
% 
%
%
%
%
%%\section{Group A- one example: ``PC5''}
%{\scriptsize
%\begin{tabular}{r|r@{~}r@{~}r@{~}r@{~}r@{~}|l|}\cline{2-6}
% & min & q1 & median & q3 & max  \\\cline{2-7}
%pd / inter &  69 &  73 &  75 &  77 &  83 & \boxplot{69}{4}{75}{77}{6}\\
%pd / intra &  81 &  85 &  88 &  90 &  96 & \boxplot{81}{4}{88}{90}{6}\\
%pf / inter &   4 &   5 &   5 &   5 &   6 & \boxplot{4}{1}{5}{5}{1}\\
%pf / intra &  11 &  12 &  12 &  12 &  14 & \boxplot{11}{1}{12}{12}{2}\\
%\cline{2-7}
%\end{tabular}
%}
%
%~\\
%
%XXX nothing in the data.

%\section{Open Issues}
%\noindent
%Future work in this area should:
%\bi
%\item
%Benchmark 
%automatic data mining.
%against 
%{\em manual case-based reasoning} methods 
%\item
%Check the stability of our conclusions between {\em random} and
%{\em natural} orderings of project data.:1
%\ei
%\noindent
%The rest of this section expands on these two points.
%
%\subsection{How complex is defect detection?}
%
%Assuming that the above results are externally valid, then it is possible
%that, for five years,
%we have needlessly over-elaborated a very simple problem. 
%Since 2002,  the authors have explored a diverse and complex range
%of data mining methods to learn defect 
%predictors
%(e.g.
%\cite{me02e,me03a,me04c,me07b,me07e,jiang07,gay07}).
%If a few dozen examples
%are enough for defect prediction, then 
%perhaps automatic data miners 
%may not the most
%an inappropriate technology for defect prediction.
%
%For small sample sizes,
%it is possible that 
%a human-in-the-loop case-based reasoning system could perform as well, or better,
%for finding combinations of features that predict for problematic code.
%For example, such an environment could ask
%humans to inspect a random sample of modules and comment on any ``bad smells''
%(to use Martin Fowler's terminology\footnote{For a list of ``bad smells'' see~\cite{fowler99} or
%)\url{http://wiki.java.net/bin/view/People/SmellsToRefactorings}.}).
%
%\subsection{Natural vs Random Orderings}
%
%One threat to external validity of our conclusion that ``a few dozen examples are enough''
% is that 
%it relies on very small randomly selected
%samples. In practice, such {\em random ordering} may not reflect the 
%{\em natural ordering} of 
%module creation and inspection in real-world projects.  
%The random sampling used above in Experiments \#1,2,3 select modules across
%all these different module types. 
%While our results hold for a few dozen modules selected at random across the system,
%they may not hold  
%for a particular order of module creation and inspection seen in real-world projects.
%
%For example, in a real project,
%developers may first generate modules relating to version control,
%then configuration management, then database accessors, then some high-level business 
%reports, and then (finally) the GUI. It is possible that the pattern and frequency
%of defects
%is very different in these different kinds of modules- in which case a few dozen
%examples of defective and non-defective modules may not be sufficient.
%Future research should check this possibility.
%
\section{Conclusion}
The value of cross-vs-within-company data (CC vs WC)
for effort estimation is an open question. Three of the paper
reviewed in the introduction comment that it can be hard to use
CC data 
due to different data collection practices at different organizations~\cite{mendes07,kitch07,shepperd07}.

It may be easier to use CC-data from defect prediction. Static code measures can be
collected in a uniform, rapid and automatic manner.
For example, in this study, we have found a clear and unambiguous conclusion amongst
our static code data:
\bi
\item CC-data dramatically increases the probability of detecting defective modules;
\item But CC-data also dramatically increases the false alarm rate. 
\item
 Therefore, we can only recommend cross-company learning for
 mission critical software were the extra costs associated with
 high false alarm rates are compensated by the associated increase
 in software assurance.
\ei

Another clear and unambiguous conclusion from static code attributes is that, for
the purposes of defect prediction,
the need for CC data may be less than previously believed.
Kitchenham et.al. list many reasons to use CC-data including these two points:

\bi
\item
 The time required to collect enough data on past projects from
   within a company may be prohibitive.
\item
 By the time enough data is collected with within a company,
   technologies may have changed so older projects may not
   represent current practice.
\ei

Our incremental WC results suggest that, in the case of defect detection,
these two points may not be compelling arguments. 
In most of our experiments, as little as 100 modules may be enough to learn
adequate defect detectors. 
When so few examples are enough,
projects can learn local defect detectors that are relevant to their
current technology in a matter of months (recall \fig{estimate}).
\bibliography{refs}
\appendix
\section{Data}

The data tables used in this study can be downloaded from the PROMISE repository\footnote{\url{http://promisedata.org/repository}}.
The static code features of our 12 tables of data are  shown in \fig{attr}.
These features divide into lines of code measures, Halstead measures, and
McCabe measures.

The Halstead attributes 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$ attributes of \fig{attr}.  These three raw $h$  Halstead
attributes were 
then used to compute the $H$: the eight derived Halstead attributes
using the equations shown in
\fig{attr}.  In between the raw and derived Halstead attributes 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 and equals the number of module parameters.
\ei

%XXXX conclusion. Halstead and McCabe very odd 1970s. sureyin the 21st cenyru we can do better

An alternative to the Halstead attributes are the complexity attributes 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 first three lines of \fig{attr}
shows McCabe three
main attributes for this pathway complexity. These are defined as follows.
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.
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}.
The {\em essential complexity}, ($ev(G)$) or 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}.
Finally, the
{\em design complexity}   ($iv(G)$) of a module is the cyclomatic complexity of a
module's reduced flow graph.

\begin{figure}[!t]
\begin{center}
{\footnotesize
\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{Features used in this study. }\label{fig:attr}
\end{figure}

\bibliographystyle{IEEEtran}


\end{document}
 
\section{Accessing Data Mining Tools and Data}

The  goals of this paper were achieved due to the large number of tools and data sets readily
available for free download from the Internet.
Anyone with access to Google can easily find and download
numerous robust data mining toolkits supports hundreds of
combinations of learners, data pre-processors, feature subset
selectors, etc\footnote{
e.g. the R project\footnote{\url{http://www.r-project.org/}},
Orange\footnote{\url{http://www.ailab.si/orange/}},
RapidMiner\footnote{\url{http://rapid-i.com/content/view/10/32/lang,en/}}
and the WEKA~\cite{witten05}.}
Also, there is more data to process. 
For example, the PROMISE repository of SE
data\footnote{\url{http://promisedata.org/repository}} has only
been active for 3 years but already contains 44 data sets. That repository
is growing rapidly (on average, 37\% more data sets each year).
This  growing supply of on-line data sources is due to several recent
developments. 
Organizational inertia means that
once procedures are
in place to:
\bi
\item Build and maintain an artifacts repository;
\item
 Build a sanitizer that
can ``scrub'' data of corporate identifies prior to release;
\item
Resolve any remaining legal issues;
\ei
then once one data set is generated,
many more will follow.  (one for each new product and for each
new release of each product). This has the added benefit that data
collected from multiple projects may have the same same schema.
For example:
\bi
\item The open
source community has proven to be a rich source of information.
PROMISE holds six ECLIPSE data sets (file and package- level metrics
for ECLIPSE 2.0, 2.1, 3.0) as well as data from FreeBSD, Xfree,
Xorg, and other projects.  
\item NASA's Metrics Data Program is now defunct
but that program generated twelve of the data sets used in this
study.
\ei
The increasing  availability of cross-company data 
makes the Kitchenham et.al. research question a very pressing question.

One interesting phenomonen observed in the PROMISE repository is the 
is the {\em flood} effect: by the time an organization 
The Kitchenham et.al. study was a 
{\em systematic review} that drew its conclusions from a wide-ranging literature search.
Such systematic reviews are becoming more frequent and are an example of the {\em evidence-based
software engineering} movement.


Software managers can use predictor of defective modules to 
focus the testing on parts of the system that seem defect-prone.
These potential defect-prone trouble spots can then
be examined in more detail by, say, model checking, intensive testing, etc.
Previously we have explored the use of data miners to learn such predictors from static
code attributes. We found that a large class of predictors proposed in numerous
publications were out-performed by Bayes classifiers that combined partial evidence
from multiple attributes~\cite{me07d}. 

Kitchenham et.al. would characterize that previous work as a {\em within-company} (WC) study
where the data from one organization is applied to new examples within the same organization.
%XXX much more regularity in software engineering that previously suspected

Therefore, companies are tempted to eskew WC studies, preferring instead to use some
cross-company (CC) study where data from elsewhere is applied locally.
The value of cross- vs within-company studies for effort estimation has been the subject
of much recent work.
In the special case of effort prediction from static code features, some of those quality controls can be automated.
In the following cross- vs within- study, features of code 
modules were extracted automatically using the same tool set (the McCabe HiQ tool\footnote{justin?}) that is
widely used in industry\footnote{Justin- can we say that predict is an alternate data collector that HiQ}.
We find that

\section{Data}

\begin{figure}
\begin{center}
\begin{tabular}{l|rrr}
data & examples & features  & defective\\\hline
pc5  & 17,186   & 38          & 3.0\%\\
mc1  & 9,466    & 38          & 0.71\%\\
pc2  & 5,589    & 36          & 0.41\% \\
pc3  & 1,563    & 37          & 10.23\%\\
pc4  & 1,458    & 37          & 12.2\%\\
pc1  & 1,109    & 21          & 6.94\%\\
kc1  & 845      & 21          & 15.45\%\\
kc2  & 522      & 21          & 20.49\%\\
cm1  & 498      & 21          & 9.83\%\\
kc3  & 458      & 39          & 9.38\%\\
mw1  & 403      & 37          & 7.69\%\\
mc2  & 161      & 39          & 32.29\%
\end{tabular}
\end{center}
\caption{Twelve data sets, sorted in order of \#examples.}\label{fig:data}
\end{figure} 
\subsection{Detector Mathematics}

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$: 
\[
\begin{array}{ll}
pd=recall=&\frac{D}{B+D}\\
pf=&\frac{C}{A+C}\\
prec=precision=&\frac{D}{D+C}\\
acc=accuracy=&\frac{A+D}{A+B+C+D}\\
selectivity=&\frac{C+D}{A+B+C+D}\\
neg/pos=&\frac{A+C}{B+D}
\end{array}
\]
The last measure ($neg/pos$) is quite interesting and
can be used within the above equations as follows:
\begin{equation}\label{eq:one}
prec = \frac{D}{D+C} = \frac{1}{1+ \frac{C}{D}} = \frac{1}{1 + neg/pos \cdot pf/recall}
\end{equation}

Ideally, our detectors have high precision {\em and} high recall {\em and } low false alarm
rates. This ideal situation is very hard to achieve. In practice, detectors must trade-off one goal
for the other.

\subsection{Trade-offs with Recall (pd) and False Alarm Rates (pd)}
Detector performance can be  assessed via {\em
receiver-operator} (ROC) curves.
Formally,  a defect {\em predictor}   hunts for a {\em signal} that a
software module is defect prone. Signal detection
theory~\cite{heeger98} offers 
ROC curves as an analysis method for assessing different
predictors.
%% ROC curves are widely used in various fields including
%% assessing different clinical computing systems~\cite{adlassnig89} and
%% assessing different machine learning methods~\cite{provost98case}.
%% The central intuition of ROC curves is that different detectors can
%% be assessed via how often they correctly or incorrectly respond to
%% the a signal.
A typical ROC curve is shown in \fig{typical}. The y-axis shows
probability of detection ($pd$) and the x-axis shows probability of false alarms ($pf$).
By definition,
the ROC
curve must pass through the points $pf=pd=0$ and $pf=pd=1$
(a predictor that
never triggers never makes false alarms; a predictor that always
triggers always generates false alarms).
Three interesting trajectories connect these points:
\be
\item
 A straight line from
(0,0) to (1,1) is of little interest since it offers {\em no
information}: i.e.  the probability of
a  predictor firing is the same as it being silent.
\item
Another trajectory is the {\em negative curve} that bends away
from the ideal point. Elsewhere~\cite{me02e}, we have found that
if predictors negate their tests, the negative curve will transpose into a {\em
preferred
curve}.
\item
The point ($pf=0$, $pd=1$) is the ideal position (a.k.a. ``sweet spot'')
on a ROC curve. This is
where we recognize all errors and never make mistakes. {\em Preferred curves} bend
up towards this ideal point.
\ee

In the ideal case, a predictor has a high probability of detecting a
genuine fault ($pd$) and a very low probability of false alarm
($pf$). This ideal case is very rare. The only way to achieve high probabilities
of detection is to trigger the predictor more often. This, in turn, incurs the cost
of more false alarms.

In practice, engineers {\em balance}
between $pf$ and $pd$. To operationalize this notion of {\em
balance}, we define $bal$ to be the Euclidean distance from the sweet
spot $pf=0,pd=1$ to a pair of $<pf,pd>$. For convenience, we
(a)~normalize $bal$ by the maximum possible distance across the ROC square
( $\sqrt{2}$); (b)~subtract this from 1; and (c)~express it as a percentage; i.e.
\begin{equation}\label{eq:bal}
balance= bal             = 1 - \frac{\sqrt{\left(0 - pf\right)^2 + \left(1 - pd\right)^2}}{\sqrt{2}}
\end{equation}
Hence, better and {\em higher} balances fall  {\em closer} to the desired  sweet spot  of $pf=0,pd=1$.
\subsection{Trade-offs with Precision}

Note that \eq{one} can be re-expressed as follows:
\begin{equation}\label{two}
pf = \frac{pos}{neg}\cdot\frac{ (1 -  prec) }{ prec}\cdot recall
\end{equation}
That is, in Equation~\ref{two}, when $recall$ is fixed then
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:
\begin{equation}\label{three}
pf = \alpha\cdot \frac{1-prec}{prec}
\end{equation}
From Equation~\ref{three}, it is clear that it is problematic to demand detectors
with high recall {\em and} high precision {\em and} low false alarm rates.
For example, 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. The effect is particularly marked for data sets
with large $neg/pos$ ratios.

Many software engineering data sets have extremely
large
$neg/pos$ ratios.
%Elsewhere~\cite{me03a,me03q}\footnote{See also the PREDICTIVE toolkit~  \url{http://www.ismwv.com/}},
%we have conducted extensive studies
%on methods for  generating and selecting detectors appropriate to different business contexts.
%The Zhangs' equation enables a more nuanced  selection process.
\begin{figure}[!b]
\begin{center}
\includegraphics[width=2.7in]{locplatonic.pdf}
\end{center}
\caption{Regions of a typical ROC curve.}\label{fig:typical}
\end{figure}
For example:
\bi
\item In our previous DMP study~\cite{me07b}, the data sets studied
had $neg/pos$ ratios
of
1.04, 
7.33,
9,
10.11,
13.29,
15.67, and
249.
\item
  Hayes, Dekhtyar and Sundaram \cite{hayes06} use text mining to                                                                     
find pairs of connected requirements in a corpus of 220 requirements and                                                                     
235 design elements (the same CM-1 dataset used in 
\cite{me07b}).
The total number of possible links in the dataset is $220\cdot 235 =                                                                        
51,700$, while the the ground truth RTM contains 361 links, for the                                                                         
$neg/pos$ ratio of $51,700/361 = 143.2$.   
\item
For an extreme example, Google reports that
over $10^{9}$ web pages contain the phrase ``software''
but only one them is the home page of this journal. Hence, $neg/pos$ for
web searching is at least $10^9$. 
\ei
%For example, consider the  the mission critical situation requiring $recall=1$.
%Equation~\ref{two}
%shows that when $prec=0.25$ and
%$neg=500$ and $pos=100$, achieving the goal of $recall=1$ requires
%a detector with  $pf=0.6$.
%As precision increases, detectors become harder and harder to
%design. For example, continuing the security example,
%at $recall=1$ and $neg/pos=5$,
%increasing the precision 
%0.25 to
%0.5 to 0.75 requires detectors with
%false alarm rates of 0.6 to  0.2 to 0.067 (respectively).
%As discussed below, building high precision detectors
%can be expensive.
%Depending on the available research budget, companies
%might elect to use lower precision detectors that are cheaper to build.
%
%experiments - some minor changes in formulas may affect the exact numbers,
%but not the ball parks), our pf for CM-1 dataset, without filtering,
%feeback, or any other tricks, is probably around 60-65% (we retrieve
%around 33,000 links outright, out of 51700 possible). Only with filtering
%(either by absolute value, or by relative rank) can we get to pf of 0.1 or
%better with decent recall.
%MGF report probability of detection and false alarm rates of
%of \{pd=75\%, pf=25\%\}, respectively. MGF argue that these are high enough to be useful.
%However,  Zhang\&Zhang derive an expression that can compute precision from the data found
%in MGF. Those computed  precisions suggest that the MGF results are  quite useless:
%\[
%\{min,median,max\}=\{2\% 20\%, 70\%\}
%\]
%
%Here, we show that Zhang\&Zhang
%do not take their conclusions far enough. 
%A large number of current industrial problems can be characterized by ``small targets'' and
%``some false alarms''  (quoted terms are defined below).
%Using the expression derived by Zhang\&Zhang, we show that all such domains are prone to
%the problem of low precision.
%However, unlike Zhang\&Zhang, we will argue that low precisions are acceptable in some
%of those domains.
%Also, unlike Zhang\&Zhang, we also will offer a specific research direction 
%on how to improve the MGF results. Interestingly, that research direction
%{\em requires} accepting low precision detectors, at least initially.

Figure~\ref{pprnp}
graphs \eq{one} for the  DMP $neg/pos$ ratios.
\begin{figure}
\begin{center}
\includegraphics[width=3in]{y_0.pdf}
\end{center}
\caption{The relationship between
$pd, prec, recall$ and $neg/pos$. 
}\label{pprnp}
\end{figure}
\begin{figure}
\begin{center}
\includegraphics[width=3in]{y_05.pdf}
\end{center}
\caption{
Figure~\ref{pprnp},
cropped to the region
where $prec>0.5$.
}\label{pprnp1}
\end{figure}
Figure~\ref{pprnp1} does the same, 
but is restricted to zones of higher precision:
only the surface for
$0.5\le prec \le 1$ is shown. 
That shadow of the  surface on the bottom plane
shows that this zone of high precision, high recall, and large
$neg/pos$.
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$}, 
Equation~\ref{two} reports that $pf$ falls into the following ranges:
\begin{itemize}
\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$;
\end{itemize}
Detectors learned in the domain of
software engineering
rarely yield
high precision detectors (see Figure~\ref{precs}).
Using the above  equations, the reasons for this are very clear:
\bi
\item
Those detectors all try to maximize recall; 
\item
Figure~\ref{pprnp} shows that such 
detectors can only achieve high precision in the rare case of very low $pf$.
\ei

Not only do our   equation explain the Figure~\ref{precs} results,
they also inform the 
 the instability of precision {\em and} the stability of $pf$ and $pd$ (recall) 
seen 
in previous studies~\cite{me04c}"
\bi
\item
Note how, in Figure~\ref{pprnp},
that at very small $pf$ values,
tiny changes in $pf$ can lead to very large changes in $prec$ 
(sudden jumps from zero to one).
\item
The other measures in
Figure~\ref{pprnp}, on the other hand, change far more smoothly and slowly.
\ei
That is, the mathematics of these detectors
explains numerous prior results such as those shown in Figure~\ref{precs} 
(i.e. \cite{me03q,me07b,huan06,hayes06,antoniol02,antoniol05,marcus03}).
\begin{figure}[!b]
\small
\begin{center}
\begin{tabular}{|p{0.95\linewidth}|}\hline
\bi
\item
The DMP paper achieved recalls over 70\% and minimum false alarm
rates of 15\%.  Using our equation and data from DMP, it
can be shown that the DMP precisions were quite low:
$\{min,median,max\}=\{2\% 20\%, 70\%\}$ (the last number came from
a data set with $neg/pos\approx 1$).
\item
Huang et.al.~\cite{huan06} won ``best paper'' at the 2006 IEEE
Requirements Engineering conference with detectors exhibiting
$prec\approx 0.25$.
\item
Without extensive feedback from human experts, the classifiers used
by Hayes, Dekhtyar, and Sundaram exhibited $pf>0.6$ (hence, very
low precisions)~\cite{hayes06}.
\item
Other such as Antoniol et.al.~\cite{antoniol02,antoniol05} and
Marcus et.al.~\cite{marcus03} researchers into software traceability
report that high recall is achievable only with low precision
detectors.  Antoniol has also been exploring bug traces in Mozilla
components and has found the same high-precision, low-recall
trade-off.
\item
After much experiments with linear regression, model tree learners,
Bayes classifiers, decision tree learners, singleton rule learners,
and some home-brew learners~\cite{me03q}, the general trend is very
clear. For those learners, executing on the DMP datasets, $pf \le
pd - 0.5$; That is, for those learners and those data sets, obtaining
high recall figures of $pd>0.6$ implies $pf>0.1$ and, consequently,
low precision.
\ei  
\\\hline \end{tabular} \end{center} 
\caption{Some
low precisions seen in the SE literature.}\label{precs} 
\end{figure}

\subsubsection{When Low Precision is Useful}

Achieving both high precision\& recall \& low false alarm rates can be problematic.
Optimizing for one often compromises the other (especially for data sets with large $neg/pos$ ratios).
Fortunately, there are may industrial
situations 
where low precision and high recall
detectors are useful.
For example, one of us (DiStefano) has used
our low-precision detectors to review flight code
developed at
the NASA Glenn Research Center (Ohio, USA).
When the results of these detectors were presented to the lead flight
engineer, he confirmed that the identified sections (which did not
have any recorded defects) had been problematic to maintain, and
contained several bugs which had not yet been entered into the
defect system. 


For another example,
from
outside the field of SE, 
a user of commercial
web search engine like Google can quickly flick through (say) three
pages of results before finding a page of interest.  Google has so
many return customers since even with precisions of (say) $\frac{1}{30}$,
the effort involved in looking at a page is so low that users don't
mind examining 29 false alarms.  

More generally, there are several situations where low precision
detectors are useful:
\begin{itemize}
\item
{\em When the cost of missing the target is prohibitively expensive.}
In mission critical or security  applications, the goal of
100\% recall may be
demanded in all situations, regardless of the  precision.
\item {\em When only a small  fraction
the data
is returned.}
Hayes, Dekhtyar, \& Sundaram call this fraction
$selectivity$ and offer an extensive discussion of the merits of
this measure~\cite{hayes06}.  \item {\em When there is little or no cost in checking
false alarms.}  For example,  a detector we have found useful in industrial settings is to
check modules  where \[\frac{lines\; of\; comments}{lines\; of\; code} > 0.25\]
This detector triggers on complex functions that 
programmers comment extensively, instead of splitting up into smaller, more maintainable,
functions.
This detector is imprecise- it often triggers on well-written
functions with detailed comments. 
However, based on commercial experience, we assert
that it is fast and simple for
a human agent to inspect  the identified modules and discern which                                                                    
ones were well-written and which were over-commented to disguise being                                                                      
badly coded.
We use this detector to find code that should be rewritten prior to release.
\end{itemize} 

\section{Data}

This section discusses the data used in this study.
Each module of each data
sets describes the attributes of that module,
plus the number of defects known for that module.
This data comes from
eight
sub-systems taken from four systems.  These systems were developed
 in
different geographical locations across North America.
Within a system, the sub-systems
shared some a common code base but did not pass personnel or code
between sub-systems. 

Each data set was pre-processed by removing the module identifier attribute
(which  is different for each row). Also, the
$error\_count$ column was converted into a boolean attribute called {\em defective?}  as follows:
$defective? = (error\_count \ge 1)$.
Finally, the $error\_density$ column was removed (since it can be
derived from line counts and $error\_count$).
The pre-processed data
sets had 38 attributes, plus one target attribute
({\em defective?})
shown in \fig{attr} and include Halstead, McCabe, lines of code, and other miscellaneous
attributes.
% XXX need introduction words saying contribution is definition of baseline experiment
At the end of \fig{attr} are a set of {\em misc} attributes that are less well-defined than lines of code attributes
or the Halstead and McCabe attributes. 
The meaning of these attributes is 
   poorly documented in the MDP database. Indeed,
   they seem to be values generated from some unknown tool set that
   was available at the time of uploading the data into the MDP.
Since there are difficulties in reproducing these attributes at other sites, an argument could be made
for removing them from this study.
A counter-argument is that if static code attributes are as weak as suggested by Shepherd, Ince, Fenton and Pfleeger
then we should use all possible attributes in order to make maximum use of the available information.
This study took a middle ground: all these attributes were passed to the learners and they determined
which ones had most information.

%Two different categories of re-sampling methods commonly used to overcome the 
%problem of imbalanced data.  The first increases the frequency of the minority class in 
%the training set (Oversampling) and the other decreases the frequency of the majority 
%class in the training set (Undersampling) (Weiss and Provost 2001; Drummond and 
%Holte 2003).
%Drummond, C. and R. C. Holte (2003). C4.5, class imbalance, and cost sensitivity: why 
%under-sampling beats over-sampling. Workshop on Learning from Imbalanced 
%Datasets II. 

%In this paper, we used cost curves to explore the in- 
%teraction of over and under-sampling on the decision 
%tree learner C4.5. Surprisingly, over-sampling is in- 
%effective, at least when the default settings are used, 
%often producing little or no change in performance. 
%Under-sampling does produce a reasonable sensitivity 
%to changes in misclassification costs and class distri- 
%bution. But representing these changes internally by 
%down-weighting gives the best performance overall. 

%~\cite{yun04}

An interesting repeated pattern in our data sets are {\em exponential distributions}
in the numeric attributes.
Elsewhere, we have conducted limited experiments suggesting that a
{\em logarithmic filter} on all numeric values might improve predictor
performance~\cite{me02e}.  
Such a filter replaces all numerics $n$ with their logarithm.
$ln(n)$.
The
log-filtered values are now more evenly spread across the y-range, making it easier
to reason about them. 
To test the value of log-filtering, all the data was passed through one of two filters:
Hence, all our numerics were pre-processed as follows:
\bi
\item {\em logNums}; i.e. logarithmic filtering where all numbers $n$ where replaced
with $log(n)$.
\item
To avoid numerical errors with  $ln(0)$,
all numbers under 0.000001 are replaced with  $ln(0.000001)$.
\ei

\section{Non-parametric Analysis of Results}

\subsection{Quartile Charts of Performance Deltas}


The experiment described below explored numerous combinations of
filters, attributes, and learners all within a
$(M=20)*(N=10)$-way cross-evaluation 
study. Hence,
this experiment 
generated nearly thousands of measuring
$pd,pf,bal$
values from different {\em methods} applied to the
same $test$ data.

The performance
results for each method were sorted and displayed as {\em
quartile charts}.  To generate these charts, the performance
deltas for some $method$ 
were sorted to isolate the median and the lower and upper quartile of numbers.

\[
{\footnotesize
\overbrace{4,7,15}^{q1},20,31,\underbrace{40}_{median},52, 64, \overbrace{70,81,90}^{q4}}
\]
In a quartile chart,
the upper and lower quartiles are  marked with black lines;
the
median is marked with a black dot; and
a vertical bar  is added to
mark the 50\%  value.
The above numbers
would therefore be drawn as follows:


{\small
\[0\%\; \boxplot{4}{11}{40}{70}{20}\; 100\%\]}
We prefer quartile charts of performance deltas to other summarization
methods for M*N studies. Firstly, they offer a very succinct summary
of a large number of experiments. For example, in the next few pages
we will display thousands of results in very little area.
Secondly, they
are a {\em non-parametric} display; i.e. they make no assumptions
about the underling distribution.  Standard practice in data mining is
to compare the mean performance of different methods using
t-test~\cite{witten05}. T-tests are a {\em parametric method} that
assume that the underling population distribution is a Gaussian.
Recent results suggest that there are many statistical issues left to
explore regarding how to best to apply those t-tests for summarizing
M*N-way studies~\cite{brouck03,demsar06}.  
\subsection{Comparison Statistics}

The problem of comparatively assessing $L$ learners run on multiple sub-samples of $D$ data sets
has been extensively studied in the data mining community. 
T-tests that assume Gaussian distributions are strongly deprecated.
For example, Demsar~\cite{demsar06}
 argues that non-Gaussian populations are common enough to require a methodological
change in data mining. 

After reviewing a wide range of
comparisons methods\footnote{Paired t-tests with and without the use of geometric means of the relative ratios;
binomial tests with the Bonferroni correction;
paired t-tests; ANOVA; Wilcoxon; Friedman},
Demsar advocates the use of the 1945 Wilcoxon~\cite{wilcoxon45} 
signed-rank test that compares the ranks for the positive and negative differences (ignoring the signs). 
Writing five years early,
Kitchenham et.al.~\cite{kitc01} comment that the Wilcoxon test has its limitations.
Demsar's report  offers the same conclusion, 
noting that the Wilcoxon test requires that the sample sizes are the same.
To fix this problem, Demsar augments Wilcoxon with the Friedman test.

One test not studied by Demsar is Mann and Whitney's 1947
modification~\cite{mann47} to Wilcoxon rank-sum test (proposed along with his signed-rank test).
We prefer this test since:
\bi
\item
The Mann-Whitney U-test does not require that the sample sizes are the same.
So, in a single U-test, learner $L_1$ can be compared to all its rivals. 
\item
The U-test does not require any post-processing
(such as the Friedman test) to conclude if the median rank of one population (say, the $L_1$ results)
is greater than, equal to, or less than the median rank of another (say, the $L_2,L_3,..,L_x$ results).
\ei
The U-test uses {\em ranks}, not precise numeric values.
For example, if treatment $A$ generates $N_1=5$ values \{5,7,2,0,4\} and treatment $B$ generates $N_2=6$ values \{4,8,2,3,6,7\}, 
then these sort as follows:
\begin{center}
{\small
\begin{tabular}{c|c|c|c|c|c|c|c|c|c|c|c}
Samples& A & A & B & B & A & B & A & B & A & B & B\\
Values & 0 & 2 & 2 & 3 & 4 & 4 & 5 & 6 & 7 & 7 & 8\\
\end{tabular}}\end{center}
On ranking, averages are used when values are the same:
\begin{center}
{\small
\begin{tabular}{c|c@{~}|c@{~}|c@{~}|c@{~}|c@{~}|c@{~}|c@{~}|c@{~}|c@{~}|c@{~}|c}
Samples& A&  A  &B&  B&  A & B  &A&  B&  A&  B & B\\
Values&  0  &2  &2&  3&  4 & 4  &5&  6&  7&  7 & 8\\
Ranks&   1 &2.5&2.5 &4& 5.5&5.5 &7&  8& 9.5&9.5& 11\\
\end{tabular}}\end{center}
Note that, when ranked in this manner,
the largest value (8) gets the same rank
even if it was
ten to a hundred times larger.
That is, such rank tests
are less susceptible to large outliers.

\fig{mw} shows the U-test for 
$A$ and $B$.
The test concludes that these treatments have the same
median ranked values (at the 95\% significance level). 
As defined in \fig{mw}, this test  counts
the  $wins$, $ties$, and $losses$ for $A$ and $B$
(where $A$ and $B$ are single or groups of methods).
Since we seek methods that can be rejected, the value of interest to us is
how often methods {\em lose}.
\begin{figure}
\begin{tabular}{|p{.95\linewidth}|}\hline
\footnotesize
The sum and median of A's ranks is
\[\begin{array}{ccl}
sum_A &=& 1 + 2.5 + 5.5 + 7 + 9.5 = 25.5\\
median_A& =&5.5
\end{array}\]
and the sum and median of B's ranks is
\[\begin{array}{ccl}
sum_B&=& 2.5 + 4 + 5.5 + 8 + 9.5 + 11 = 40.5\\
median_B&=& 6.75
\end{array}\]
The $U$ statistic is then calculated 
where \mbox{$U_x=sum_x-(N_1(N_2+1))/2$}:
\[\begin{array}{c}
U_A = 25.5 - 5*6/2 = 10.5\\
U_B = 40.5 - 6*7/2 = 19.5
\end{array}\]
These can be converted to a Z-curve using:
\[
\begin{array}{rclcl}
\mu&= &(N_1N_2)/2&=&516.4\\
\sigma & = & \sqrt{\frac{N_1N_2(N_1 + N_2 + 1)}{12}}&=&5.477\\
Z_A & = & (U_A - \mu)/\sigma&=&-0.82\\
Z_B & = & (U_B - \mu)/\sigma&=&0.82\\
\end{array}
\]
(Note that $Z_A$ and $Z_B$ have the same absolute value.
In all case, these will be the same, with opposite signs.)

If $abs(Z) < 1.96$ then the samples $A$ and $B$ have the same median rankings (at
the 95\% significance level). In this case, we add one to both $ties_A$ \& $ties_B$.
Otherwise, their median values can be
compared, using some domain knowledge. In this work, {\em lower} values
are better since we are comparing relative errors. Hence:
\bi
\item
If $median_A < median_B$ add 1 to both $wins_A$ \& $losses_B$.
\item
Else if $median_A > median_B$ add 1 to both $losses_A$ \& $wins_B$.
\item
Else, add 1 to both $ties_A$ \& $ties_B$. 
\ei
\\\hline
\end{tabular}
\caption{An example of the Mann-Whitney U test.}\label{fig:mw}
\end{figure}



\section{Incremental Studies}
\fig{inc}
shows the inter-experimental results as the size 
of the training set increased in size. Note two main visual patterns:
\bi
\item Increasing the training set size does little or nothing to the median $balance$ values.
\item In some data sets, increasing the training set size increased the variability (spread)
in the $balance$ values.
\ei
Mann-Whitney tests were applied to test the first visual pattern. 
Detectors learned from just $N$ instances do as well
as detectors learned from any other number of instances.

\bi
\item
N=100 for \{CM1,KC2,KC3,MC2,MW1,PC3,PC4\}
\item
N=200 for  \{KC1\}
\item
N=300 for \{PC1\}
\item
N=4,900 for \{PC2\} (but N=800 only lost 2 out of 53 trials)
\item
N=8,300 for \{MC1\} (but N=400 only lost once out of 92 trials)
\item
N=11,000 for \{PC5\} (but N=300 only lost twice out of 169 trials)
\ei

%\section{Group B- one example: ``KC3''}
%{\scriptsize
%\begin{tabular}{r|r@{~}r@{~}r@{~}r@{~}r@{~}|l|}\cline{2-6}
% & min & q1 & median & q3 & max  \\\cline{2-7}
%pd / inter &  60 &  80 &  80 &  80 & 100 & \boxplot{60}{20}{80}{80}{20}\\
%pd / intra &  40 &  60 &  80 &  80 & 100 & \boxplot{40}{20}{80}{80}{20}\\
%pf / inter &  14 &  19 &  24 &  31 &  38 & \boxplot{14}{5}{24}{31}{7}\\
%pf / intra &  10 &  17 &  21 &  26 &  36 & \boxplot{10}{7}{21}{26}{10}\\
%\cline{2-7}\end{tabular}
%}
%
%\section{Group C- two examples such as ``MC1''}
%{\scriptsize
%\begin{tabular}{r|r@{~}r@{~}r@{~}r@{~}r@{~}|l|}\cline{2-6}
% & min & q1 & median & q3 & max  \\\cline{2-7}
%pd / inter &  57 &  71 &  86 &  86 & 100 & \boxplot{57}{14}{86}{86}{14}\\
%pd / intra &  57 &  71 &  86 &  86 & 100 & \boxplot{57}{14}{86}{86}{14}\\
%pf / inter &  17 &  18 &  19 &  20 &  21 & \boxplot{17}{1}{19}{20}{1}\\
%pf / intra &  15 &  16 &  17 &  18 &  20 & \boxplot{15}{1}{17}{18}{2}\\
%\cline{2-7}\end{tabular}
%}
%


\section{Under-sampling Studies}
\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


%------------------------------------------------------------------------- 

\end{document}

