
\subsection{About $Application_x$}
WHICH's current implementation offers 10 different
$C$ including all the ones listed in \fig{measures}.
It is 
trivial to implement other criteria, once it is designed.
To design the best $C$ for the local application, that application must be
studied.

Our study will focus on $application_x$, 
the details of which are shown  in  \fig{task1}. In $application_x$,
a QA team working on a limited budget wants to
{\em sort} the {\em modules} that the  {\em data miner}  {\em predicts}
are defective to find
(a)~ those that require urgent inspection, and (b)~others
than could be inspected later (or never).  
\begin{figure}
\begin{displaymath}
    \xymatrix{ 
old\; data \ar[r] & data\;miner \ar[d] & \\
new\; data \ar[r] & predictor \ar[r]                    & predicitons \ar[lld]\\
sorted \ar[r] & QA\; team \ar[r]   &  defect\; reports\\
    }
\end{displaymath}
\caption{$Application_x$: the QA team inspects  the  new data modules that the data miner predicts are faulty.
The modules predicted to be faulty are sorted by their
 {\em relative defect frequency} (RDF)
where one module is ranked higher than another if it is more likely to contain defects.
The QA team inspects those modules in that sort order.
 }\label{fig:task1}
\end{figure}
We make no presumption that $application_x$ is the only possible way to use data miners.
There are many other business applications of defect predictors that do not conform to $application_x$
(e.g. two other applications were discussed above).
However, $application_x$ was chosen for two reasons.
Firstly, it is a common usage of automatic defect predictors. For example, if a V\&V company is
hired to audit the code from some new off-shore client, they may have a large code base to inspect
in the shortest possible time.

Secondly,  $application_x$ addresses current concerns in the defect prediction literature.
Arisholm \& Briand~\cite{arisholm06} argue {\em against} certain standard measures of predictor performance such as accuracy (defined in
\fig{measures}), saying that a highly accurate predictor can be undesirable in other ways.
For example, accuracy says nothing about the appropriate sort order for reading modules.
In $application_x$ we want to support a
 QA team 
 {\em reading less} while {\em finding more} defects.
For such a budget-conscious team, 
if X\% of the modules are predicted to be faulty and if those modules contain less than X\% of the detects,
then the costs of generating the defect predictor is not worth the effort. 

Koru et al.~\cite{koru07} have much to say about  the relative defect
frequency (RDF) of different biasing strategies for selecting which modules should be inspected next.
They speculate that the relationship between module {\em size} and
{\em number of defects} is not linear, but {\em logarithmic};
i.e. smaller modules are proportionally more
troublesome. Accordingly, they argue that LOC can be be used in to create a biasing
strategy with higher RDF. For example: if one has the resources to
inspect 10,000 LOC, then their {\em logarithm defect hypothesis} would say that it
is better to pick 100 classes of size
100-LOC as opposed to picking 10 classes of 1,000 LOC.

We can use $application_x$ to  test the logarithmic defect hypothesis by exploring two
$sort$ orders:
\bi
\item In Koru's preferred    {\em manualUp}  policy, the  {\em smaller} modules (those with less LOC)
 will be inspected first. 
\item In the opposite  {\em manualDown} policy,  the  larger  {\em larger} modules will be inspected  first.
\ei

The relative merits of biasing strategies like {\em manualUp} and {\em manualDown} 
can be compared using 
the Effort-vs-PD diagram of \fig{effort}.
The curves in that figure are generated as follows:
\bi
\item Some oracle {\em selects} a set of modules to inspect. In the case of automatic data mining, this would be the modules predicted
to be defective. In the case of {\em manualUp} and {\em manualDown}, it would be all modules.
\item The {\em selected} are sorted. For example,
except for {\em manualDown}, we sort all modules
ascending  on LOC.
\item In {\em selected} set is explored in the sorted order \mbox{$1 \le i \le |selected|$}.
Each $x$ value in \fig{effort} shows $\sum_i LOC_i$ found in the first $i$ modules.
\item
For each $x$ value, the $y$
value is the percentage of the defective modules seen in the first $i$ modules.
\ei
Note that:
\bi
\item
 If Koru et al. are right then the {\em manualUp} and {\em manualDown} curves should appear as drawn in
 \fig{effort}; i.e. {\em manualUp} should find defective modules faster than {\em manualDown}.
\item
Typically, defect detectors do not trigger on all modules, and have some false alarm rate. 
For example, the {\em good} curve of \fig{effort} triggers on B=43\% of the code while only
detecting 85\% of the defective modules.  Similarly, the {\em bad} curve stops after finding 30\% of the defective
modules in 24\% of the code.
\ei
\fig{effort} lets us define reasonable lower bounds on the performance of  an automatic data miner being used for  $application_x$:
\bi
\item
For Arisholm \& Briand to approve of a data miner, its curve must fall {\em above} the diagonal line marked as {\em minimum}.
This is the region where $PD > Effort$; i.e where
 QA team can  {\em read less}
and  {\em finds more}.
\item A {\em bad}  automatic method performs worse  than simple manual methods; i.e.
its Effort-vs-PD curve falls {\em below} both the  {\em manualDown} and {\em manualUp} curves.
In $application_x$, there would be not business justification for such a learner (e.g. 
see the {\em bad} curve of \fig{effort}).
\ei
\fig{effort} also lets us define a theoretical upper bound
on the performance of any learner tackling $application_x$.  Imagine an  omniscient oracle that restricts the
inspections to just the $A\%$ defective modules (in \fig{effort}, $A=30\%$). 
If  {\em manualUp} was then applied to just those defective modules,
then that would result in the {\em best} curve.  
Realistically, defect predictors can approach the {\em best} curve, but never reach it.  Hence, the most we can hope for 
is something like the {\em good} curve that  falls {\em below} the {\em best} curve and 
 {\em above} the {\em manualUp} and {\em manualDown} curves.

\begin{figure}
\begin{center}
\includegraphics[width=2.5in]{plots/effort.pdf}
\end{center}
\caption{Effort-vs-PD.}\label{fig:effort}
\end{figure}

Two more details will complete our discussion of  \fig{effort}. 
Firstly, as mentioned above, the curves from our data miners terminate at some 
value less than 100\%.  For example, the {\em good}
curve of \fig{effort} terminates at some point $B=45\%$. 
To compute the area under the Effort-vs-PD curve, 
we must fill in the gap between 
the termination point  and $X=100$.  In the sequel, we will assume
\bi
\item 
The QA team {\em only} inspects the modules referred to it by the
data miner;
\item
That is, if a module is not recommended by the data miner it is not inspected. 
\ei
Visually, for the $good$ curve, this  assumption
 would correspond to
a flat line running to the right from point $C=85$.  Our use of this assumption means that our results
will {\em under-estimate} the efficacy of our learners (and we will return to this point, below).


Secondly, when comparing  supposedly {\em good} defect predictors,
it is useful to express their performance in terms of (a)~the area under the Effort-vs-PD curve expressed as (b)~a ratio of
the area under the {\em best} curve. To be complete, that evaluation should contain the ``$\delta$'' factor that models the effectiveness
of QA teams that inspect modules according to the defect predictors' recommendation
(and at $\delta=1$, the inspection teams are perfect at recognize defective modules). 
Note that 
 that factor applies to
the activity that occurs {\em after} the data miners runs and the modules are sorted in ascending order by LOC. 
Hence:
\bi
\item $\delta$ 
is the {\em same across all data miners};
\item
By expressing the value of a defect predictor a ratio of the area under the {\em best} curve, 
$\delta$ cancels out.
\item
So we can assess the relative merits of different defect predictors {\em independently} of $\delta$.
\ei
%XXX return to this point
We use $C'_2$ to denote this performance measure; i.e. area under the effort-vs-PD curve, measured
as a percentage of the area under the $best$ curve.
\subsection{Designing $C_1$ for $Application_x$}
Recall that $C_1$ is the criteria used internally by the learner to grow a model. When the learner
terminates and outputs a model,  $C_2$ is
used to assess the outputted model.

Our preferred $C'_2$ was described in the last section. 
This section describes the $C_1$ used by WHICH to incrementally grow candidate rule sets.
In summary, our experiments will using a $C'_1$ criteria that 
approximates the intent of $C'_2$ 
even it does not implement it directory.

The $C'_2$ criteria maximizes $pd$ while minmizing $effort$. To emulate
that criteria during rule generation, we experimented with the following $C'_1$ criteria:
\[
 C'_1 = 1 - \frac{\sqrt{pd^2*\alpha + (1-pf)^2*\beta + (1-effort)^2*\gamma}}{\sqrt{\alpha+\beta+\gamma}}
\]
where $0 \le \left(C'_1, \alpha,\beta,\gamma,pd,pf,effort\right) \le 1$ and larger values of $C'_1$ are better.
The $pf$ term was absent from the first version of $C'_1$ but was added after some initial experiments
that returned rules with high false alarm rates.
Note that {\em increasing} the $effort$ or $pf$ leads to a {\em decrease} in $C'_1$.

The  $\alpha,\beta,\gamma$ terms of this expression represent
the relative utility of $pd,pf,effort$ respectively.
Setting any of these utilities to zero  
removes some factor from consideration in the rule learning.

Initially, we gave $pd$ and $effort$ equal weights; i.e. \mbox{$\alpha=\gamma=1$}.
This yielded disappointing results. In the data of \fig{measures}, there exists a small number
of modules with very large LOCs. Hence, on cross-validation, the LOC (and hence $effort$) of the selected
modules can vary wildly.
\fig{sizes} illustrates this effect:
for example, there are 126 modules
in the $kc4$ data set, most of them are under 100 lines of code but a few of them
are over 1000 lines of code long.
The presence of small numbers of very large modules means that $\gamma=1$ is not recommended.
If the very large modules fall into a particular subset of some cross-val, then 
the performance assocated with WHICH's rule can vary
unpredictably from one run to another.

\begin{figure}
\begin{center}
\includegraphics[width=2.5in]{lines.pdf}
\end{center}
\caption{Lines of code in a sample of our data sets.}\label{fig:sizes}
\end{figure}

It turns out that $pf$ can be used as a surrogate for $effort$: if the effort
is large then too many non-faulty modules will be selected and $pf$ will increase.
Hence, in the following experiments, we used a variant of $C'_1$ that disables
$effort$ but places a very large penalty on $pf$;
\[\alpha=1,\; \beta=1000,\; \gamma=0\]

