\documentclass[conference]{IEEEtran}
\usepackage{times,cite,colortbl}
\usepackage{algorithmic,bar}
\usepackage[normalem]{ulem}
\ifCLASSINFOpdf
 %  \usepackage[pdftex]{graphicx}
  % declare the path(s) where your graphic files are
  % \graphicspath{{../pdf/}{../jpeg/}}
  % and their extensions so you won't have to specify these with
  % every instance of \includegraphics
  % \DeclareGraphicsExtensions{.pdf,.jpeg,.png}
\else
  % or other class option (dvipsone, dvipdf, if not using dvips). graphicx
  % will default to the driver specified in the system graphics.cfg if no
  % driver is specified./includeincl
  % \usepackage[dvips]{graphicx}
  % declare the path(s) where your graphic files are
  % \graphicspath{{../eps/}}
  % and their extensions so you won't have to specify these with
  % every instance of \includegraphics
  % \DeclareGraphicsExtensions{.eps}
\fi
\usepackage[cmex10]{amsmath}
\usepackage{algorithmic}
\usepackage{array}
\usepackage[tight,footnotesize]{subfigure}
\usepackage{stfloats}
\usepackage{url}
\usepackage{tricks}
\usepackage{graphicx}
\newcommand{\IT}{WHERE}
\IEEEoverridecommandlockouts 
\newcommand{\G}{\cellcolor[gray]{.8}}


\newcommand{\boxes}[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}
%
\title{{\Large{\bf Local vs Global Models for Effort Estimation and Defect Prediction}}}






\author{\IEEEauthorblockN{Tim Menzies, Andrew Butcher}
\IEEEauthorblockA{CS \& EE, WVU\\
 Morgantown, USA\\
\url{tim@menzies.us}\\
\url{ abutcher@afrolegs.com}}
\and
\IEEEauthorblockN{Andrian Marcus}
\IEEEauthorblockA{Computer Science,\\
Wayne State University, USA\\
\url{amarcus@wayne.edu}}
\and
\IEEEauthorblockN{Thomas Zimmermann}
\IEEEauthorblockA{Microsoft Research\\
Redmond, USA\\
\url{tzimmer@microsoft.com}}
\and
\IEEEauthorblockN{David Cok}
\IEEEauthorblockA{GrammaTech Inc.\\
Ithaca, New York\\
\url{dcok@grammatech.com}}
\thanks{
The work was partially funded by NSF grant CCF:1017330.
The research reported in this document/presentation was performed in connection with contract/instrument
W911QX-10-C-0066 with the U.S. Army Research Laboratory. The views and conclusions contained in this
document/presentation are those of the authors and should not be interpreted as presenting the official policies or
position, either expressed or implied, of the U.S. Army Research Laboratory or the U.S. Government unless so
designated by other authorized documents. Citation of manufacturer’s or trade names does not constitute an official
endorsement or approval of the use thereof. The U.S. Government is authorized to reproduce and distribute reprints
for Government purposes notwithstanding any copyright notation hereon.}

}


%\author{\IEEEauthorblockN{Michael Shell\IEEEauthorrefmark{1},
%Homer Simpson\IEEEauthorrefmark{2},
%James Kirk\IEEEauthorrefmark{3}, 
%Montgomery Scott\IEEEauthorrefmark{3} and
%Eldon Tyrell\IEEEauthorrefmark{4}}
%\IEEEauthorblockA{\IEEEauthorrefmark{1}School of Electrical and Computer Engineering\\
%Georgia Institute of Technology,
%Atlanta, Georgia 30332--0250\\ Email: see http://www.michaelshell.org/contact.html}
%\IEEEauthorblockA{\IEEEauthorrefmark{2}Twentieth Century Fox, Springfield, USA\\
%Email: homer@thesimpsons.com}
%\IEEEauthorblockA{\IEEEauthorrefmark{3}Starfleet Academy, San Francisco, California 96678-2391\\
%Telephone: (800) 555--1212, Fax: (888) 555--1212}
%\IEEEauthorblockA{\IEEEauthorrefmark{4}Tyrell Inc., 123 Replicant Street, Los Angeles, California 90210--4321}}




%\IEEEspecialpapernotice{(Invited Paper)}




\maketitle


\begin{abstract}
Data miners can infer rules showing how to
improve either (a)~ the  effort estimates of a project
or (b)~the 
defect predictions of a
software module.  Such  studies often exhibit {\em conclusion instability}
regarding what is the most effective action for different projects or modules.

This instability can be explained by data heterogeneity.
We show that effort and defect data contain many  local regions with markedly
different properties to the global space. 
In other words, what appears to be useful in a global context {\em is often
irrelevant for particular local contexts}.

This result raises questions about 
the generality of conclusions from empirical SE.
At the very least, SE researchers should test if their supposedly general
conclusions are valid within subsets of their data. At the very most,
empirical SE should become 
a search for
local regions with similar properties (and
conclusions should be constrained to just those regions).
\end{abstract}

\begin{IEEEkeywords}
Data mining, defect/effort estimation,  validation, empirical SE.
\end{IEEEkeywords}
\thispagestyle{plain}
\pagestyle{plain}
\IEEEpeerreviewmaketitle
\section{Introduction}
%Software is everywhere. Software has become a critical enabling
%technology for realization of functions central to our society. New
%cars are executing tens of million of lines of software code,
%controlling everything from the brakes, to the intensity of the
%headlights, to the volume of the radio\footnote{http://goo.gl/Ru83}.
%Software failures can bring down the international ﬁnancial and
%transport systems; our energy generation and distribution systems;
%and even the pacemakers that control our hearts.
%
%Nevertheless, the discipline of software engineering discipline
%continues to lag in terms of its ability to provide processes for
%delivering artifacts of predictable quality within pervasive resource
%constraints.  Decades of software engineering (SE) research have
%resulted in a maze-like set of methods that, in theory, improve
%software development.  However, the literature is mostly silent on
%which of those  methods are most effective for a given context.
%For example, Menzies et al.~\cite{me08a} performed a literature search
%on the 52 core methods listed described in the IEEE-1012 standard for
%software verification and validation. They found very few attempts to
%assess the relative cost-effectiveness of those tools. Instead, nearly
%all the work found by that survey took the form of one team assessing
%one method one project (as opposed to a team assessing multiple
%methods on multiple projects). A similar pattern was reported by
%Zannier et al.~\cite{zannier06} in their review of empirical software
%engineering papers from the International Conference on Software
%Engineering. Only 2\% of those  papers compared
%their approach to some other method.
%
%Worse still, when researchers try to port conclusions from one project
%to another, they usually fail dismally.  
%%In 1976, McCabe offered a general rule for predicting defecting software module- the (in)famous $(v(g) \ge 10$
%%rule.
%%Decades later, hundreds of their researchers have proposed numerous alternative
%Shepperd et
%al.~\cite{shepperd01} found that conclusions regarding ``which is the
%best software project effort estimator'' varies wildly when the
%training and test data are changed.  Zimmermann~\cite{zimmermann09}
%studied 629 pairs of (project1, project2).  In only 4\% of cases was a
%defect prediction model learned from project1 useful on project2.  In
%a similar result, Turhan et al.~\cite{me09b} applied defect
%predictors learned from other companies to some local company. The
%resulting detectors had high detection rates (over 90\%) but at the
%cost of very high false rates (over 60\%).
%
%We conjecture that the reason empirical SE has not found treatments on software projects
%is that it has been looking in the wrong place.
Research in  empirical software engineering research takes many forms including:
\be
\item
{\em Literature reviews}: over sets of related papers; e.g.~\cite{jorgensen05}.
\item
 {\em Project-based experiments}: these vary a small number of
 factors are changed, then observe the 
results; e.g.~\cite{audris09}. 
\item
{\em Case studies}: observation of  projects; e.g.~\cite{runeson09}.
\item
{\em Induction studies}: look for effects within  data 
found by project-based or case-study research; e.g.~\cite{me07b}. 
\ee
A repeated pattern amongst all this research is  
{\em conclusion instability}, i.e.
finding that some 
effect $X$ is not generally true.
For example, in the field of {\em software development effort estimation},
Mair and Shepperd~\cite{mair05} compared regression to analogy methods.
From 20 empirical studies they found no conclusion regarding which methods were best
 (seven favored regression, four were indifferent and nine favored analogy). 
% J{\o}rgensen~\cite{jorg04}
% reviewed 15 studies comparing model-based to expert-based 
% methods. No conclusion was seen: five papers found in favor
% or expert-based; five for model-based; and five found no conclusion.
A similar pattern of  conclusion instability can be found in {\em module defect predictors learned from static code
features}.
Zimmermann et al.~\cite{zimmermann09} learned
defect predictors from 622 pairs of projects $\langle project_1, project_2 \rangle$. In only 4\% of pairs did defect predictors learned in $project_1$ work in $project_2$.
Other conclusion instability results
in effort/defect estimation are reported in~\cite{mair05,Mendes2007,me09b}.

% Also,
% 
% Further,
% Kitchenham et al.~\cite{Mendes2007}  reviewed empirical studies that compared models
% learned from data collected {\em within} or {\em across}
% organizational boundaries. 
% Three studies found that they both performed the same,
% while four found that they were significantly different (and worse).



% In
% a similar result, Turhan et al.~\cite{me09b} applied defect
% predictors learned from other companies to some local company. The
% resulting detectors had high detection rates (over 90\%) but at the
% cost of very high false rates (over 60\%).


One explanation for conclusion instability is data heterogeneity.
If data sets contain local regions with very different properties, then
an induction cross-validation study would exhibit high variance when
tests are conducted on  stratifications with unusual properties.
%Inductions studies test their inferred model by exploring the effect
%of that model on distributions with the data. For example, 
%Boehm~\cite{boehm81} argued
%that software development effort is exponential on the size of the software.
%To test that claim, an induction study would take some test
%data, plot if LOC vs effort for that data,
%then check if that plot conformed to $effort \propto LOC^N$.
%In this process, it is vital  to select the right test data.
%Software engineering is such a varied activity that we doubt that any
%general truism (e.g. ``using the SEI capability maturity model reduces defects'')
%will hold in all contexts. 
%Tests are therefore best conducted within 
%{\em contexts of related projects}
%But what defines those contexts? Is it:
%\bi
%\item
%Project size; or
%\item
%Their target industry, e.g guidance \& control or 
%finance or database or military; or 
%\item 
%Their intended platform, e.g. embedded, distributed, web app, smart phone; or
%\item
%Software criticality, e.g. mission critical / low risk; or
%\item The location where they were developed, e.g. the local or other
%  companies explored by Zimmermann.  
%\ei 
%The results  of this paper suggest that such divisions may be uninformative.
To test this conjecture, we compared the learning of {\em treatments} (changes that are intended
to improve some quality measure) using:
\bi
\item
Just the {\em local} data in adjacent clusters; to
\item
All the 
{\em global} data found in all clusters;
\ei
Based on the literature on outlier removal in software engineering
(e.g.~\cite{kim11,yoon10}), we expected to find a few heterogeneous
clusters spread around other clusters that were mostly homogeneous.
To our surprise, we found the reverse.  Usually, every cluster was
different to the others
 and in those clusters:
\begin{quote}{\em
The treatments from local regions
were different and superior to the global
treatments.}
\end{quote}
It is neither novel nor interesting to say that particular
cases can {\em sometimes} contradict general principles. What was surprising, however,
is that in these results, the global
treatments were {\em nearly always} inferior to the local treatments.
This conclusion
is only based on the data explored in this study and needs to
be checked in other data sets.
However, in support of our conclusion it should be noted
that  SE data heterogeneity would explain the 
prevalence of conclusion instability.

If other studies find that  (in the usual case)
global lessons do not hold locally,
 then this would necessitate a change to the practices and goals of
empirical SE.
Rather than focusing on
generalities (that may be irrelevant to any particular project),
empirical SE should focus more on context-specific principles. 

Such a change in focus suggest 
new research questions.
Firstly: how to find subsets of
similar data?  We assume that {\em structure
  implies behavior}; i.e. that software artifacts that are similar
with respect to their features will be also similar with respect to
their behavior.  Using this assumption, we discuss below 
a linear time clustering
algorithm called ``WHERE''.

Secondly: on what properties or dimensions should
we cluster?  WHERE assumes that the dimensions of most interest are
the ones that most separate the data.  Hence, during clustering,
WHERE uses a dimensionality synthesis technique to infer those dimensions.

Thirdly: how to  extract treatments from local
regions?  Often, these regions are too small to support a parametric
model.  Consider a data set with two dozen attributes that forms clusters
containing less than 100 instances in each (these numbers are
consistent with the results shown below).  Hihn's heuristic is that
regression requires around 10 examples for each
attribute~\cite{me06d}. By that rule, our clusters are far too small
for that kind of parametric modeling ($24*10=240\gg 100$). 
Instead we use ``WHICH'', a non-parametric contrast set learner that infers what needs to change
in order to best alter the distribution of some target quality variable (e.g. number of defects,
project development effort).
 
%Fourthly:  how to recognize when a project is
%leaving a context?  This is important since, if conclusions are
%restricted to local regions, then it is vital to track a project to
%determine if a project is leaving that region (at which time, new
%local treatments will have to be learned). Our ``WHEN'' tool offers a
%simple visualization that simplifies that tracking process.
%
The techniques presented here (WHERE and  WHICH) are one
way to manage local learning.  We currently favor these since they are
based on years of our research and incorporate the best practices we
have found so far in our work.  Also, they scale to large data
sets. This does not mean that the community should uncritically accept
them. Like any learner, WHERE and  WHICH rely on certain tuning parameters
to control their operation. We have used our best engineering judgment to set those
parameters but it is possible that other settings or, indeed, other algorithms are better
suited to this task.
A challenge problem we offer other researchers is to review our
our methods to propose refinements/alternatives.

But the details of tuning parameters for WHERE and  WHICH are orthogonal to this discussion.
To defend our conclusions, this paper 
shows that when  the {\em same analysis method}
is applied (1)~{\em globally} to 
all data or (2)~{\em locally} to just some intra-cluster data,  then {\em different and
better treatments} are found from the local analysis.
In this paper, our example SE domains will be effort estimation and defect prediction.

The rest of this paper is structured as follows.
First, we motivate this work with a small case study on local learning.
Then, we discuss techniques for localized reasoning (WHERE and WHICH).
Next, we use those techniques in an experiment that compares
the treatments learned from global or local contexts.
This followed by notes on validity and related work.

\section{Local Learning: Motivations}
To motivate this paper, we offer the following simple example of the
value of local learning.

There are many general truisms in the field of software engineering.
Our results are only interesting if our treatments could have been
generated in a much simpler way, just by applying the truisms.
For example,
the COCOMO/COQUALMO effort/defect predictors~\cite{boehm00b}
assume that
defects and efforts are mostly reduced by decreasing
functionality  (measured either in function points or lines of code).
According to this assumption, the best thing a manager can do to control defects
and cost is to discard needless functionality.
This process, of discarding requirements, is also one of Brooks' key recommendations
in {\em The Mythical Man Month}~\cite{brooks95}.

In the {\em Experiments} section of this paper, we present experiments where
WHICH learns treatments (i.e., changes) from four data sets.
Some of those treatments  agree with this truism of ``make it smaller''.
For example, WHICH can learn this treatment:
\[loc=1\]
To read this, note that we discretize all variables min..max into the range
 1..7. Hence, $loc=1$ is read as ``set lines of
code to minimum''.

Significantly, of the 24 treatments learned in the {\em Experiments}
section, the ``make it smaller'' treatment
appears far more often in the
$global$ treatments than in the $local$ treatments (as we expected). Our experiments used four data sets (two on effort estimation and two on defect prediction) and in two of those data sets, the learned $global$ treatment recommends minimizing the function points or lines of code of that system.  However, in the 20 $local$ treatments learned by our experiments, only 2 of them recommend ``make it smaller''.
That is, what {\em seems} to be a good idea overall (e.g. ``make it
smaller'') is actually irrelevant to 18 sub-groups within the data (i.e., local contexts).

Notice that our results do not disagree with the overall conclusions
of Boehm and Brooks.
In general, ``make it smaller'' is a valid method of reducing the
effort and defects associated with a software
system.
Indeed, our $global$ analysis reaches the same conclusion in half the
experiments we present below.

However, we would add that for particular kinds of projects, other
factors may be more important than
just size.
For example, for one data set explored below we learn a treatment from
a $local$ region of the form
\[
pcap=nominal
\]
which, in COCOMO-speak, means avoid programmers with poor or very poor
programming capability.
Note that this treatment makes no reference to the {\em size} of the
system since, this particular data set,
the size effects were dominated by the impact of poorly trained programmers.
Examples like this motivate our research into local lesson learning in
software engineering.
Our preferred method of learning those treatments is to combine two
tools: WHICH and WHERE.


% Earlier versions of WHICH were reported at ASE'00 and ASE'02~\cite{me00e,me02f}. Later versions have been applied successfully
%to complex tasks such as optimizing the settings on (a)~software process models~\cite{me04a}
%or NASA flight guidance systems~\cite{gay10}; or (c)~learning defect prediction rules that detect the greatest number of defects
%in the fewest lines of code~\cite{me10a}. 

%{\em Novelty of this paper:}
%The use of
%WHICH and WHERE to check for data heterogeneity, and the implications
%of that heterogeneity on empirical SE, is new work.
%Also, while WHERE has not been published before,
%WHICH has appeared previously~\cite{me00e} 
%(but the optimization presented here
%of scoping WHICH  to just adjacent clusters found by WHERE is  novel).
%This section  documents conclusion instability in SE.
%In our view, this is also evidence for the 
%need for tools like WHERE, WHICH, \& WHEN to manage
%SE data heterogeneity.
%
%%There are many software engineering (SE) methods that might 
%%be applied to a software development project. These divide into at least three groups:
%%\bi
%%\item
%%	Paper-based methods; e.g.  the checklists of orthogonal defect classification~\cite{chill92}.
%%\item
%%	Tool-based methods; e.g. new functional languages or the execution and testing tools used in Menzies~\cite{me07b}
%%or the automated analysis recommended by Holzman~\cite{holzmann97}.
%%\item
%%	Process-based methods; e.g. optimizations like the continual adjustment of iteration size in an agile software development cycle to optimize requirements priorities~\cite{port08}.
%%\ei
%Ideally, we should be able to select the right methods for the right
%project using empirical results from the SE literature. Surprisingly
%such results are by and large missing.
%%To illustrate this deficiency, consider two software projects
%%project1 and project2. Suppose, in project1, it was shown that
%%method1 was better than method2 for improving the quality of that
%%project. Here, method1 might be ``static analysis tools'' and method2
%%could be ``formal code reviews''.  In the literature, there are few
%%convincing reports of any such lessons being found in one project,
%%then  successfully applied to another. Moreover, rarely is a
%%sufficient characterization of project1 provided to determine
%%relevance of application to other projects. 
%Textbooks listing
% best/worst SE practices fall into two groups:
%\bi
%\item
%	Texts like Shull~\cite{shull07} or Fenton~\cite{fenton97} 
%discuss techniques for making conclusions, without extensive lists of lessons learned from those techniques;
%\item	Texts like Glass~\cite{glass02} or Endres~\cite{endres03} offer lists of lessons learned, but insufficient details on the evidence used to learn those lessons.
%\ei
%%One explanation for the lack of comparison are the research practices in the field of software engineering.
%%Roblles~\cite{robles10,barr10} reports that of the 154 experimental studies published at the International Conference on
%%Mining Software Repositories up to 2009, only two of those papers keep their data on-line.
%%For this reason, numerous initiatives now exist to house data from SE research papers\footnote{
%%See the open-source repositories such as Bugzilla (http://www.bugzilla.org/installation-list),
%%the Software Infrastructure Repository (http://sir.unl.edu);
%%the PROMISE
%%repository of reproducible SE results (http://promisedata.org/data).
%%and the ISBSG estimating benchmark suite (http://goo.gl/2AJCH).}
%%While these initiatives are valuable, to date,
%%there is still little evidence that results from one project can be generalized to others:
%%\bi
%%\item
%%	As mentioned above,
%%Zimmermann~\cite{zimmermann09}  studied 629 pairs of (project1, project2). In only 4\% of cases was a defect prediction model learned from project1 useful on project2.
%%\item
%%	Kitchenham~\cite{kitch07}   survey claimed that project1’s data is useful for effort estimation of project2. They found the existing evidence inconclusive and even contradictory.
%%\ei
%
%Even at forums focused on empirical studies, there is a pattern of conclusion instability.
%Menzies \& Shull~\cite{me10b}
% reviewed presentations made at the PROMISE   conference on repeatable SE experiments.
%In the period 2005 to 2009,
%	there have been 68 PROMISE presentations, 48 of which either tried a new analysis on old data or made reports in the style of Zannier~\cite{zannier06}
%(i.e. that a new method was shown to work for one, and only one, project).
%	Nine of those papers raised questions about the validity of prior results; e.g.  Menzies~\cite{menzies08a}.
%	Four papers argued that SE model generality was unlikely and/or impossible; e.g.~\cite{briand06}.
%	Only rarely (7/68) did researchers report successful generalizations from one project to other projects; e.g.~\cite{wey07}.
%	Four papers reported a software quality predictor learned from one project that was usefully applied to a new project; e.g. Tosun~\cite{tosun09}.
%	Only three other papers made a partial case that such generality was possible; e.g. Boehm~\cite{boehm09}.
%In summary, taken as a whole, most of the PROMISE community {\em does not} report conclusions
%that are stable across multiple projects.
%
%We have discussed this survey of  empirical SE with leading researchers
%in the field. They were not surprised at our findings
%that there are so few examples of methods generalizing from one project to
%another.
%Vic Basili (personnel communication) 
%has been exploring empirical SE for over thirty years. After commenting that empirical SE is healthier now than in back in the 1980s, he acknowledged that (a) results thus far are incomplete, and (b) there are few examples of methods that are demonstrably useful on multiple projects. 
%We also contacted David Budgen who, with Barbara Kitchenham,
%is a leading European advocate of ``evidence-based software
%engineering'' (EBSE). 
\section{Algorithms: WHICH and WHERE}
\subsection{Contrast Set Learning with WHICH}

When we show data mining output to business users, 
their first question is usually ``what
does this say about how to improve a project?''. To answer this question, we use
{\em contrast set learning} to infer rules describing differences between a current
context (called the {\em baseline})
and a better context (called the {\em target}).
A contrast set rule takes the form 
\[if~R_x~then~\left(change=\epsilon_1 / \epsilon_0 * support\right)\]
We say this rule selects some $support\%$  of the data
that contains a different (and hopefully better) distribution of the dependent quality variables
(and by ``select'', we mean it finds all rows consistent with $R_x$).
Here,  $R_x$ is a $treatment$ containing a set of attribute value pairs $a_v$;  
$\epsilon_0$ is the median score of all instances in the  baseline and target; 
and $\epsilon_1$ is the  median score in the selected subset of baseline and target.
For effort and defect prediction, where {\em less} is {\em better},
then 
the ratio
$\epsilon_1/\epsilon_0$ is smaller if the treatment selects for {\em better} instances.

%Apart from minimizing $\epsilon_1/\epsilon_0$ and max
%another measure of success is how well $R_x$ maximizes the probability
%of $R_x$ selecting the target.
%If $N$ instances divide into $B+T$ baseline plus target instances,
%and if $a_v \in R_x$ occurs with frequency $F_B$ and $F_T$ in the baseline and target (respectively),
%then by Bayes' rule:
%\begin{equation}\footnotesize
%\begin{array}{ccccl}
%l_1&=& L(baseline|R_x)& =& B / N * \left(\prod F_B(a_v \in F_B)/B\right)\\
%l_2& =& L(target|R_x)       & =& T / N * \left(\prod F_T(a_v \in F_B)/T\right)\\
%&& P(target|R_x)&= &l_1 / (l_1 + l_2)
%\end{array}
%\end{equation}
%

%\newcommand{\res}[5]{
%\vspace{1mm}
%\begin{barenv}
%\setstyle{\sffamily} \setwidth{8}
% \setyaxis{0}{#2}{10}
%\sethspace{0.5} \setnumberpos{down} \bar{#3}{1} \bar{#4}{4}
%\bar{#5}{8}
%\end{barenv}
%
%~\newline
%{\em #1}
%}
%
%\begin{figure}[!t]
%{\footnotesize
%\begin{tabular}{|cp{0.9in}|p{0.9in}|p{0.9in}|}\hline
% &\res{$baseline$}{24}{7}{24}{8}
%&\res{ $acap=2 \newline \wedge sced=2$}{24}{2}{1}{0}
%
% &\res{ $acap=2 \newline \wedge ltex=3 \newline \wedge pmat=3 \newline \wedge sced=2$}{24}{2}{0}{0}\\\hline
%\multicolumn{4}{c}{Legend: 
%\protect\legend1{=low risk}
%\protect\legend4{=medium risk}
%\protect\legend8{=high risk}}\\
%\multicolumn{4}{c}{{\em acap = analyst capability; ltex= language and tools experience; }}\\
%\multicolumn{4}{c}{{\em pmat= process maturity; sced= schedule pressure.}}
%\end{tabular}}
%\caption{Number of branches to different classifications. 
%For each histogram,
%all branches that violate the contrast set have been pruned. 
% have constrained the choices in the decision tree. From~\protect\cite{me00e}.
%}\label{fig:trees}
%\end{figure}
We turned to contrast set learning as a result of certain drawbacks with conventional
learners. At ASE'00, we presented the results of applying the C4.5 decision tree learner~\cite{quinlan92} to 
20,000 outputs from a Monte Carlo simulation of a software
process model.  The resulting decision tree had 400 nodes, which business users
found too complex to read and understand.
One 
user  threw the tree in the trash 
and gruffly demanded ``stop telling me what {\em is}; just tell me what to {\em do}''.

To satisfy this demand, we built the   
TARZAN contrast set learner~\cite{me00e} that swung through the trees
looking for attribute values that occur at different frequencies in  different classes.
TARZAN returned the smallest set of differences that most 
pruned/retained
branches to undesired/desired classes (respectively). 

It turns out that
the minimal description of the {\em differences} between two things, is often much smaller
than a full {\em description} of both things.
For example:
\bi
\item
TARZAN's analysis of a decision tree with 400 nodes returned two small
rules mentioning only four attributes each.
\item
In the experiments shown below, we generate treatments that reference only one attribute.
\ei
As a result, we can show our users  succinct rules
describing what needs to change in order to select for certain desired classes.

Subsequent research into contrast set learning dispensed with C4.5 and optimized the inference
using 
stochastic~\cite{hu02} and bayesian reasoning~\cite{clark05}. 
The current version, called 
WHICH~\cite{me10e},
loops over
attribute values combinations, combining those that look most promising:
\be
\item
Continuous attributes are discretized to ``$\beta$'' values.
\item A stack is created: one item for every attribute value.
\item
The items in that  stack are sorted 
using $\epsilon_1/\epsilon_0*support$.
\item $\kappa$ number of times, do:
\bi
\item Generate $\lambda$ number of new items, as follows.
\bi
\item Pick two  items at random, favoring those with 
better $\epsilon_1/\epsilon_0*support$.
\item Combine the pair into a new item. Score it.
\ei
\item
Sort the  $\lambda$ new items rules into the stack.
\ei
\item Repeat step 4 until no new improvements seen in the best score.
Return the item with best score.
\ee
%\begin{figure}
%\begin{center}
%\includegraphics[width=2.5in]{picks}
%\end{center}
%\caption[Top-of-stack scores of the WHICH]{Top-of-stack scores of the WHICH stack seen after multiple ``picks'' (selection and scoring
%of two conditions picked at random, then combined) for seven data sets from the UCI data mining repository~\cite{Blake+Merz:1998}.
%Usually, top-of-stack stabilizes after just a  dozen pick. However, occasionally,
%modest improvements are seen after a few hundred ``picks''
%(see the plot marked   with  an ``A''). }\label{fig:picks}
%\end{figure}
%The looping termination criteria was set using our engineering judgment. In studies
%with UCI data sets~\cite{Blake+Merz:1998}, Milton showed that 
%  the score of top-of-stack condition usually stabilizes in less than 100 picks~\cite{milton08}
%(those results are shown in \fig{picks}).


WHICH is controlled by the settings of \fig{parems}.
Two settings change
the maximum size of WHICH's stack ($\gamma$)
and the minimum acceptable
$\epsilon_1/\epsilon_0*support$ score ($\omega$). WHICH runs fastest when $\gamma$ and $\omega$
only allow for small stacks processing rules with largest $\epsilon_1/\epsilon*support$
scores. However, this fast version of WHICH can miss rules which, in isolation, are not
promising but, when combined, are useful. To avoid that issue, this study uses $\gamma=\infty$
and $\omega=0$ (i.e.
 do not prune the stack and  all rules are acceptable).

In the following section, we will use WHICH on pairs of neighboring clusters found by WHERE.
In those experiments, where clusters range in size from 20 to 120 instances, WHICH runs very quickly indeed:
on a 4GB machine with a 2.5GHz processor, a PYTHON version of WHICH terminates in under a second (excluding time
to read any data from disk). 


%One important difference between WHICH and other learners
%is that the function used to evaluate rules can be any
%calculation  that returns
%a positive real number.
%This is different to other learners like C4.5~\cite{quinlan92} or
%RIPPER~\cite{cohen95} that are hard-wired to return trees or rules that minimize entropy.
%Such hard-wired evaluations are not suited to all SE tasks. For example,
%suppose an software inspection team wants to read the {\em fewest} lines of code
%to uncover the {\em most} number of defects. 
%If all defect locations are known, it is possible to sort the defective
%modules 
%of LOC to generate a maximal $LOC$ vs $recall$ curve.  
%Other learners can be assessed by how close to this  maximal curve they can achieve, as follows:
%(1)~determine
%which modules they predict to be defective; (2)~sort those modules by $LOC$;
%(3)~use
%historical data to determine $recall$ at each point in that sort order.
%\fig{allr} shows the results of such an analysis. WHICH comes closes to maximal
%since it can select treatments using an $\epsilon_i$ especially customized to
%this specific task (see \cite{me10a} for details).
%Other learners perform (much) worse than WHICH since they strive to maximize accuracy or minimize
%entropy, which may be irrelevant to the tasks of maximizing the area under a $LOC$ vs $recall$ curve.
%\begin{figure}[!t]
%\renewcommand{\baselinestretch}{1}
%\begin{center}
%{\footnotesize\begin{tabular}{l|r|c} 
%&   median \% achieved & \multicolumn{1}{c}{~} \\
%&   of maximum & \multicolumn{1}{c}{~} \\
% learner &  AUC(LOC, recall)  & \multicolumn{1}{c}{ 25\% to 75\% percentile} \\\hline
%            WHICH&  71\%&\boxes{   0.0}{  52.5}{  70.9}{27}{ 100.2}\\
%       Naive Bayes&  57\%&\boxes{   0.0}{  47.5}{  56.8}{15.6}{ 100.2}\\
%              C4.5&  28\%&\boxes{   0.0}{  16.9}{  27.6}{26.3}{ 100.1}\\
%            RIPPER&  22\%&\boxes{   0.0}{  10.6}{  21.9}{26.3}{ 100.2}\\\hline
% & & \multicolumn{1}{c}{50\%} 
%\end{tabular}}
%\end{center}
%\caption{10 repeats of a 3-way cross-valiation study
%on 10 defect data sets from http://promisedata.org/data. From~\cite{me10e}.
%}\label{fig:allr}
%\end{figure}
%

\begin{figure}[!t]
\begin{center}
{\footnotesize
\begin{tabular}{|c|c@{~}p{1.3in}|p{0.8in}|}\hline
technique & name &  notes & default\\\hline
WHICH & $\beta$  & number of bins for descretizing number attributes & $\beta=7$ equal
frequency bins\\\cline{2-4}
      & $\epsilon$  &generates performance score for a set of instances & e.g. median effort\\\cline{2-4}
      & $\lambda$  & number of loops & $\lambda=5$\\\cline{2-4}
     & $\kappa$   & number of pairs to be picked and combined & $\kappa=20$\\\cline{2-4}
	 & $\gamma$   & maximum acceptable height of WHICH's stack & $\gamma=\infty$\\\cline{2-4}
	 & $\omega$   & minimum acceptable $\epsilon_i/\epsilon_0*support$ score & $\omega=0$\\
\hline
WHERE &$\alpha$  &stopping rule for quadtree tree recursion & $\alpha=\sqrt{N}$\\\cline{2-4}
      & $\delta$  &stopping rule for clustering &  $\delta=0.5$
\\ \hline
\end{tabular}
}
\end{center}
\caption{Default settings ($N$ refers to the number
of instances).}\label{fig:parems}
\end{figure}

\subsection{Using WHERE to Find Similar Projects}


This section describes WHERE, a fast clustering algorithm for finding software artifacts
with similar attributes. This process is controlled by the settings of
\fig{parems}.


WHERE clusters data on dimensions synthesized along the axis of greatest variability
in the data.
One way to find such dimensions is via
methods such as principal component analysis (PCA) that transform
$D$ basic dimensions (that might be correlated) into a fewer number of uncorrelated (orthogonal)
components. In PCA, component $I$ accounts for as much variability as possible
in the data and an orthogonal component $I+1$ tries to account for the remaining.

Matrix factoring methods like  PCA 
take polynomial time to execute~\cite{Du2008}.
Faloutsos \& Lin~\cite{Faloutsos1995} offer a linear-time
heuristic for generating these dimensions. Given $N$ instances,
their ``FASTMAP'' heuristic finds 
the dimension of greatest  variability to a line drawn between the two furthest points. 
These two points are found in linear time, as follows:
\bi
\item Pick any instance $Z$ at random;
\item Find the instance $X$ that is furthest away from $Z$;
\item Find the instance $Y$ that is furthest away from $X$;
\ei
The line $\overline{XY}$ is an approximation to the first component found by PCA and
is computed using $2N$ distance calculations (i.e. faster than PCA's polynomial time inference).
\begin{figure}[!t]
\begin{center}
\includegraphics[width=2.6in]{geometry}
\end{center}
\caption{
Each dot is an D-dimensional instance mapped into  D=2 
using \eq{ab}. One dimension is the line between $X$ (at the origin) and
the most remote instance $Y$ (at $0,c$). Each dot has distance $a$ from the origin
and $b$ from the most remote point. The median point on the $x$ and $y$ axis
are $\hat{x}$ and $\hat{y}$, respectively. These median points divide the space into four quadrants.
}\label{fig:geo}
\end{figure}


As shown in \fig{geo},
an orthogonal dimension to $\overline{XY}$ can be found by
declaring that the line $\overline{XY}$ is of length $c$ and runs from point $(0,0)$ to $(0,c)$.
Each instance now has a distance $a$ to the 
origin (instance $X$) and distance $b$ to most remote point (instance $Y$).
From the Pythagoras and cosine rule,  each instance is  at the point $(x,y)$:
\begin{equation}\label{eq:ab}
\begin{array}{ccl}
x&=&(a^2 + c^2 - b^2)/(2c)\\
y&=&\sqrt{a^2 -x^2}
\end{array}
\end{equation}

\begin{figure*}[!b]
{\em {\footnotesize \begin{tabular}{p{0.8in}p{1.7in}p{1.7in}p{1.7in}}
&Initial two dimensions. &After quadtree generation.& After  clustering 
of neighboring leaf
quadrants.
\end{tabular}}}

\hspace{0.8in}\includegraphics[width=5.5in]{ab.png}
\caption{Recursive dimensionality synthesis.  Each 2-d dots represents 
24 descriptors of a software project. 
Colors 
on the right-hand-side show median intra-cluster development effort (green= lowest effort;
red= highest effort). White denotes a region too sparse to cluster.
Generated from the NASA93 effort estimation data set (http://goo.gl/WlzCC) using 
the default parameters of \fig{parems}.
Note to reviewers: in the camera-ready version of this paper,
the color choices in this figure will be changed 
to support readers with red-green colorblind issues.
}\label{fig:3part}
\end{figure*}


\fig{geo} shows four quadrants defined by 
the median values of each dimension ($\hat{x},\hat{y}$):
{\em NorthWest, NorthEast,
SouthWest, SouthEast}. 
WHERE recurses on each quadrant to generate a 
balanced tree of quadrants (stopping when a sub-quadrant has less than $\alpha$ instances).
That is, after an $O(N)$ process that generates the quadtrees,
WHERE can use the quadtrees as an index that maps test instances to related instances 
in time $O(log_4N)$).



Schikuta~\cite{Schikuta93} warns that quadtrees needlessly sub-divide data
when neighboring leaf quadrants have similar properties. Hence, as a post-processor
to quadtree generation, WHERE
combines similar leaf quadrants as follows:
\be
\item Sort all leaf quadrants
by their density (number of instances divided by cluster size).
\item Prune all quadrants from the sort with a density less than
$\delta *$  maximum density.
\item
Starting with the densest cluster,
perform a geometric search through immediate neighbors of this first quadrant.
\item
All quadrants connected
in this way are removed from the sort order and
added into their own separate cluster.
\item If the sort is not empty, goto step 2 to find the next cluster.
\ee
\fig{3part} shows the results of running WHERE on
the  NASA93
effort estimation dataset from the PROMISE repository (see http://goo.gl/WlzCC). Each dot 
describes one project using 24 independent attributes
and one dependent attribute showing the development effort (in months). 

The left-hand-side of that figure places the data within the top two dimensions learned by
FASTMAP. The middle figure shows the leaf quadrants found after WHERE recursively
explored  the NorthWest,
NorthEast, SouthWest, SouthEast quadrants. The right-hand-side figure shows the results of leaf
quadrant clustering.
Each cluster has been colored to show the median intra-cluster development
effort.
The colors range from dark red (highest effort) to dark green (lowest effort).
The white clusters contain  less than $\alpha$ members (this occurs when a parent cluster has less
than $2*\alpha$ items).


One inference supported by \fig{3part}
is {\em what to change}. Consider the three clusters in \fig{3part} labelled $C,C',C''$.
Suppose a manager of a project in the pink cluster $C$ is considering how to decrease the development
effort of that project (of all the neighbors of that cluster, the green cluster
$C'$ has the lowest development
effort). Accordingly, that manager would run WHICH over the $C'$ data to learn
treatments that
convert projects of type $C$ to $C'$.

Note that such a strategy is {\em not} available to the manager of a project in 
the dark green cluster $C''$.
No neighbor of $C''$ has a shorter development effort so we would advise that manager to avoid applying
any global rules and to maintain
the status quo.


One advantage of WHERE is that it scales to large data sets. 
Unlike other algorithms like kd-trees~\cite{bentley75}, our approach does 
not suffer from the ``curse
of dimensionality''. Since WHERE always recurses on two dimensions synthesized
in linear time (via FASTMAP)
from the data, this algorithm   scales linearly on the number of attributes.
WHERE also scales very well on the number of instances.
\fig{scales}  shows runtimes after applying WHERE to
data sets from the PROMISE repository 
(CM1, KB2, MW1, KC3, PC1, KC1 from http://goo.gl/fNgNW) 
where the instances are copied once, twice,
four, or eight times.
\begin{figure}[!t]

\includegraphics[width=3.2in]{all.pdf}
\caption{WHERE's runtimes scale linearly on number of rows. Generated using the
defaults on \fig{parems}.
}\label{fig:scales}
\end{figure}
Note that the runtimes scale linearly with data set size.



One potential drawback with WHERE is that since it uses
the FASTMAP heuristic, it may not find the
points that  best represent the dimensions of greatest variability in the data.
To check this if this heuristic generates inaccurate dimensions, elsewhere~\cite{nelson11}
we have conducted extensive experiments with the FASTMAP heuristic versus other, more considered
clustering methods such as k-means. 
Our results agree with those of
Faloutsos \& Lin~\cite{Faloutsos1995}: in practice, the approximate dimensions
found by FASTMAP 
does not degrade inferencing (compared to other more complete, and slower, approaches).

\begin{figure*}[!t]
{\scriptsize
\begin{tabular}{c|p{2in}|p{4in}}
 afp & 
adjusted function points& adjusted size by the standard value adjustment factor (vaf)\\\hline
 input & function points (ufp) of input\\\hline
output  & function points (ufp) of external output \\\hline
 enquiry & function points (ufp) of external enquiry\\\hline
file & function points (ufp) of internal logical files or entity references\\\hline
 interface &function points (ufp) of external interface
 added  &function points (ufp) of new or added functions \\\hline
 changed &  function points (cfp) of changed functions\\\hline
deleted &  function points (cfp) of deleted functions\\\hline
pdr\_ufp &
normalized level 1 productivity delivery rate &
norm. level 1 effort (for development team ) divided by functional size (unadjusted function points). \\\hline

npdr\_afp &
normalized productivity delivery rate 
&
normalized effort divided by functional size (unadjusted function points). \\\hline

 npdu\_ufp & productivity delivery rate (adjusted function points) &
summary work effort divided by adjusted function point count. \\\hline

resource & team type &
1 = development team effort (e.g., project team, project management) ;
2 = development team support (e.g., database administration, data administration, quality assurance) ;
3 = computer operations involvement (e.g., information center
support, computer operators, network administration) '
4 = end users or clients (e.g., user liaisons, user training time)\\\hline

 dev.type & development type & 
1= new development, 2= enhancement; 3= redevelopment.\\\hline

duration & 
total elapsed time for the project & in calendar months.\\\hline\hline

effort &
summary work effort &
provides the total effort in hours recorded against the project.

\end{tabular}
}
\caption{The function point metrics used in CHINA. The last row is the dependent variable.}\label{fig:china}
\end{figure*}



\begin{figure*}[!t]
{\scriptsize
\begin{tabular}{c|p{1.5in}|p{5in}}
amc & average method complexity & e.g. number of JAVA byte codes\\\hline

avg\_cc & average McCabe & average McCabe's cyclomatic complexity seen in class\\\hline
ca & afferent couplings & how many other classes use the specific class. \\\hline

cam & cohesion amongst classes & summation of number of different types of method parameters in every method divided by a multiplication of number of different method parameter types in whole class and number of methods. \\\hline

cbm &coupling between methods &  total number of new/redefined methods to which all the inherited methods are coupled\\\hline

cbo & coupling between objects & increased when the methods of one class access services of another.\\\hline

ce & efferent couplings & how many other classes is used by the specific class. \\\hline

dam & data access & ratio of the number of private (protected) attributes to the total number of attributes\\\hline

dit & depth of inheritance tree &\\\hline

ic & inheritance coupling &  number of parent classes to which a given class is coupled (includes counts
of methods and variables inherited) \\\hline 

lcom & lack of cohesion in methods &number of pairs of methods that do not share a reference to an instance variable.
\\\hline

locm3 & another lack of cohesion measure & if $m,a$ are  the number of $methods,attributes$ 
in a class number and $\mu(a)$  is the number of methods accessing an attribute, then
$lcom3=((\frac{1}{a} \sum_j^a \mu(a_j)) - m)/ (1-m)$.
\\\hline

loc & lines of code &\\\hline

max\_cc & maximum McCabe & maximum McCabe's cyclomatic complexity seen in class\\\hline
mfa & functional abstraction & number of methods inherited by a class plus number of methods accessible by member methods of the class\\\hline
moa &  aggregation &  count of the number of data declarations (class fields) whose types are user defined classes\\\hline
noc &  number of children &\\\hline

npm & number of public methods & \\\hline
rfc & response for a class &number of  methods invoked in response to a message to the object.\\\hline



wmc & weighted methods per class &\\\hline\hline






defects & defects & number of defects per class, seen in post-release bug-tracking systems.

\end{tabular}
}
\caption{The C-K metrics used in LUCENE2.4
and XALAN2.6. The last row is the dependent variable.}\label{fig:lucene}
\end{figure*}



\section{Experiments}
In the following experiments, we apply WHICH and WHERE  
to test if $locally$ learned treatments are better
and different to $global$ treatments (using effort estimation and defect prediction data).

\subsection{Data}

This study used data from http://promisedata.org/data: 
\bi
\item
CHINA is a collection of 499 software development projects, 
tagged with the development effort (in months).
Each project is described in terms of {\em function points} 
(i.e. number of high-level operations within the system) shown in \fig{china}.
\item
NasaCoc are the 156 cost estimation instances
in  the combined NASA93 and COC81 datasets
converted to COC-II via Reifer et al.'s RosettaStone 
algorithm~\cite{reifer99}\footnote{http://goo.gl/8hjF5, http://goo.gl/lwxqq}. 
\item
LUCENE2.4 is a defect log on the 340 classes of  an object-oriented 
JAVA-based search engine optimized for text mining.
\item
XALAN2.6 is a defect log on the 875 classes of an OO Java implementation of an XLST processor.
\ei
The last two data
sets describe their 
classes in terms of the 
standard C-K metrics for object-oriented systems~\cite{chid94}
shown in
\fig{lucene}. 

These data sets were selected for this study since they are as
different as we could find in the PROMISE repository (two relate
to effort estimation and the other two to defect prediction; also,
CHINA predicts for total staff effort while NasaCoc predict for
calendar months of development).  Also, they are public domain, so
it is possible for
other researchers to
reproduce, improve, or even refute our conclusions.

Note that WHERE and WHICH can work on defect and effort data (and, indeed, any other source of
supervised data) since these techniques make no particular commitment to the semantics of
a particular domain.
\subsection{Method}
For this study, we used the WHERE and WHICH settings of \fig{parems}.
After WHERE was applied to each data set,
then for each cluster $C$, a {\em local}  analysis
was conducted as follows:
\bi
\item  
Let $M,M'$ be the median scores of cluster
$C$ and neighboring cluster $C'$.  For LUCENE2.4 and XALAN2.6, that score reflects a defect count per class.
For the other data set, that score reflects the total staff development effort (CHINA) or the development
time (NasaCoc).
\item
Let $N,N'$ be the number of
instances in $C,C'$.  For the neighbor with best $M'$ mean score,
use WHICH to learn a {\em local} treatment with $baseline=C \cup
C'$ and $target=C'$.  
\ei
Note that cluster $C$ was skipped if it is was too small (for this study,
we used $N < 20$) or if there is no neighbor with a better score
$M' < M$. In practice, this removed less than 40 instances per data set. 

For the {\em global} analysis, all available training data
was sorted on some quality measure. In order to permit  valid
comparisons, all data from clusters skipped by the
{\em local} analysis was removed. WHICH was used to learn  a {\em global} treatment
with $baseline=best \cup rest$ and $target=best$.  

For both the $local$ and $global$ studies,
we reported the distribution of quality measures  in (a)~the baseline 
(b)~in the instances selected by $local$ and $global$ treatments.


\subsection{Results}
\fig{rx} shows the attribute values found in the treatments learned from either the $global$ analysis
or in a $local$ analysis.
All values are discretized to the range 1..7, min..max so, for example, pcap=4 in the NasaCoc results 
translates to programmer capability is nominal (a.k.a. average) in the standard COCOMO ontology.

Line one of that figure shows the treatments generated via the $global$ analysis
while the other lines show treatments learned from local clusters.
Note that
different data sets produced differing numbers of clusters: e.g. XALAN2.6 generated ten while
NasaCoc generated only two.
Of the local treatments generated, none used more than one attribute
and only two used more than one value (see {\em dit} and {\em loc} in XALAN2.6).
For an explanation of the attribute names, see \fig{china} or \fig{lucene} or \cite{boehm00a}.

The bottom of \fig{rx} shows how often an attribute, or an attribute value,
was seen in more than one treatment:
\bi
\item
In two data sets (NasaCoc, LUCENE2.4), all
treatments were different. 
\item
In one data set (CHINA) the number of deleted function points
was important in two local treatments. 
\item
In the remaining data set, lines of code (loc), cohesion
amounts classes (cam), and aggregation (moa) was important in more than one cluster.
\ei
Also shown at the very bottom of \fig{rx} is how often a global treatment was the same
as a local treatment. This occurred in only one data set (XALAN2.6) and only in two of the ten
clusters of that data sets.
\begin{figure}
{\footnotesize
\begin{tabular}{|p{0.7in}@{~}|p{0.4in}@{~}|p{0.6in}@{~}|p{0.55in}@{~}|p{0.5in}|}\hline
cluster &NasaCoc&CHINA&LUCENE2.4&XALAN2.6\\\hline
global&ltex=1&afp=1&rfc=2&loc=1\\
C1&pcap=4&added=4&amc=7&amc=1\\
C2&prec=4&deleted=1&ca=1&cam=2\\
C3&&deleted=1&dam=5&cam=3\\
C4&&&mfa=1&dit=2 or 4\\
C5&&&moa=1&loc=1\\
C6&&&&loc =1 or 2\\
C7&&&&moa=1\\
C8&&&&moa=4\\
C9&&&&rfc=1\\
C10&&&&wmc=3\\\hline
\multicolumn{1}{c}{~}\\\hline
repeat attribute&0&2 (deleted)&0&3 (loc) \newline 2 (cam) \newline 2 (moa)\\\hline
repeat attribute values&0&2 (deleted=1)&0&3 (loc=1)\\\hline
local = global&0&0&0&2 (loc=1)\\\hline
\end{tabular}
}
\caption{Treatments learned by WHICH for clusters found by WHERE.}\label{fig:rx}
\end{figure}


From \fig{rx}, we can make three important observations:
\bi
\item
{\em The treatments are succinct:}
(never more than one attribute). This is important from a management perspective since it can
be difficult for managers to control multiple factors in a project.
\item
{\em The local treatments are insightful:} As discussed in \S2,
defect and effort reduction is often seen as a matter
of reducing function points or lines of code. That view can be seen in the 
$global$ treatments of CHINA and XALAN2.6 that recommends setting function points (afp) and lines of
code (loc) to their minimum value. However, in 18 of 20 clusters, such a simplistic recommendation
was {\em not} found in the learned treatments.
\item
{\em The local treatments are different to  the global treatments:} for 18 out of 20
locally generated treatments. 
\ei
When the treatments of \fig{rx} where applied to the data, the 
distributions of \fig{dists} were generated.
These distributions are expressed in terms of their percentile bands:
\bi
\item The {\em O th} percentile row is the {\em minimum} observed value;
\item The {\em 50 th} percentile row is the {\em median} observed value.
\item The {\em 100 th} percentile row is the {\em maximal} observed value;
\ei
In order to simplify comparisons, all results are normalized 0 to 100 against the minimum
to maximum $raw$ value. These raw min and max values are shown on the right-hand-side of each table in \fig{dists}.

\begin{figure}[!t]
\renewcommand{\baselinestretch}{0.8}
{\footnotesize

\parbox{0.5in}{CHINA (effort)}
\begin{tabular}{|r|r|rr|}
   \multicolumn{4}{l}{} \\\cline{3-4}
   \multicolumn{2}{c|}{} & \multicolumn{2}{c|}{treated}\\\hline
percentile &          raw & global & local\\\hline
0 th&0&0&0\\
25 th&1&1&1\\
median = 50 th&4&4&3\\
75 th&9&8&7\\
worst = 100 th&100&100&74\\\hline
75th - 25th & 8& 8 & 6\\\hline
\end{tabular}
\begin{tabular}{r@{~=~}l}
 min&	26\\
       maxs&	49,034\\
\end{tabular}

~\\~\\

\parbox{0.5in}{NasaCoc (months)}
\begin{tabular}{|r|r|rr|}
   \multicolumn{4}{l}{} \\\cline{3-4}
   \multicolumn{2}{c|}{} & \multicolumn{2}{c|}{treated}\\\hline
percentile &          raw & global & local(*)\\\hline
0 th&0&0&0\\
25 th&12&10&2\\
median = 50 th&21&17&7\\
75 th&30&26&8\\
worst = 100 th&100&100&9\\\hline
75th - 25th & 19& 16 & 6\\\hline
\end{tabular}
\begin{tabular}{r@{~=~}l}
 min&	4.9\\
       max&	96.4\\
\end{tabular}

~\\~\\

\parbox{0.6in}{LUCENE2.4 (defects)}
\begin{tabular}{|r|r|rr|}
   \multicolumn{4}{l}{} \\\cline{3-4}
   \multicolumn{2}{c|}{~} & \multicolumn{2}{c|}{treated}\\\hline
percentile &          raw & global & local(*)\\\hline
0 th&0&0&0\\
25 th&0&0&0\\
median = 50 th&3&0&0\\
75 th&10&3&0\\
worst = 100 th&100&23&0\\\hline
75th - 25th & 10& 3 & 0\\\hline
\end{tabular}
\begin{tabular}{r@{~=~}l}
 min&	0\\
       max&	30\\
\end{tabular}

\vspace{3mm}

\parbox{0.6in}{XALAN2.6 (defects)}
\begin{tabular}{|r|r|rr|}
   \multicolumn{4}{l}{} \\\cline{3-4}
   \multicolumn{2}{c|}{~} & \multicolumn{2}{c|}{treated}\\\hline
percentile &          raw & global & local(*)\\\hline
0 th&0&0&0\\
25 th&13&13&13\\
median = 50 th&13&13&13\\
75 th&33&25&13\\
worst = 100 th&100&100&63\\\hline
75th - 25th & 20& 13 & 0\\\hline
\end{tabular}
\begin{tabular}{r@{~=~}l}
 min&	0\\
       max&	8\\
\end{tabular}
}
\caption{Effects on effort/defect distributions.
All values $x$ normalized via \mbox{$round(100*(x-min)/(max-min))$}.
$Raw$ denotes distributions in original data.
$Treated$ denotes distributions in the subset of either (a)~the raw data
selected by the 
$global$ treatment or (b)~two neighboring clusters selected by the 
$local$ treatment.
$Local(*)$ denotes a distribution than that is
statistically different to the $global$ distribution
(Mann-Whitney, 95\%).
}
\label{fig:dists}
\end{figure}

In order to interpret those results,
we offer the following notes.
In this experiment, an ideal learner:
\bi
\item
Reduces the median defect or costs measures seen in
the untreated $raw$ data.  
\item
One treatment learner is superior 
if the former has a statistically different and lower median than the other.
\item
Another measure of interest is the {\em intra-quartile range}; i.e. the 75-25th percentile
range: the {\em smaller} this range, then the {\em more confidence} we have that the treatment
will produce effects around the median value.
\item
Finally,
a treatment learner should not select for outstandingly
bad outcomes.
Therefore it is 
useful to consider the {\em worst-case scenario} seen
in the {\em worst} rows (the 100-th percentile range where defects and effort are maximal).
\ei
An examination of the 100-th percentile range shows that
the worst-case scenario of {\em local} learning is much
less than  other treatments.
While this is a clear effect in
all the results, it is particularly marked in NasaCoc
and LUCENE2.4. In the latter, $local$ treatments avoided
{\em all} defective modules (as witnessed by the column of zeros in the
local LUCENE2.4 results).

Another result to note is that (except for CHINA)
the spread of the results (75th-25th percentile range)
is less with $local$ learning than with $global$. This effect is particularly
marked in NasaCoc and XALAN2.6.

In summary, $local$ treatments were different and superior to the  $global$ treatments. 
The differences in those treatments was shown in \fig{rx} while the $local$ superiority
is shown in \fig{dists}.
In all
data sets, $local$ treatments
reduced the worst-case scenario and the intra-quartile range.
While some of those reductions are modest, others are quite marked.
As to the median results, $local$'s medians were never worse than $global$
and, in one case (NasaCoc) they were significantly better.

%\begin{figure}
%{\scriptsize
%~~~~~\begin{tabular}{l@{~}|p{7mm}@{~~}|p{7mm}@{~~}|p{7mm}@{~~}|p{7mm}@{~~}|p{7mm}@{}|p{7mm}@{~~}|p{7mm}}\cline{2-8}
%        \multicolumn{1}{c|}{~}&\multicolumn{7}{c|}{value}\\\cline{2-8}
%attribute&1&2&3&4&5&6&7\\\hline
%afp&1 4&&3 6 8&&&&2\\\hline
%input&6 8&&&\G g 1 4 8&8&&\G g 1 4\\\hline
%output&&1&2 8&&&&\G g 2 4\\\hline
%enquiry&\G g 1 4&&&&2 3 6&&\\\hline
%file&8&3 6 8&\G g 1 8&&&&2\\\hline
%interface&&&&&&&2 3\\\hline
%added&3 6 8&&\G g 1 4 8&\G g 1 4 8&&&\\\hline
%changed&&&&3 6 8&&&2\\\hline
%deleted&\G g 1 2 3 4 8&&&&&&\\\hline
%pdr\_afp&&\G g 1 4&2&8&&&\G g 1 4 6\\\hline
%pdr\_ufp&&&2 6&\G g 1 4 6&2&2 6&3\\\hline
%npdr\_afp&&\G g 1&3 6&\G g 1 4&&&1 4 6\\\hline
%npdu\_ufp&&\G g 4&2 6&&&\G g 1 3 4 6&1 3 4 6\\\hline
%resource&&&&&2 3 8&&2 3\\\hline
%dev.type&\G g 1 2 3 4 6 8&&&&&&\\\hline
%duration&\G g 3 6 8&&&&2 3 8&&\G g 3\\\hline
%\end{tabular}}
%\caption{CHINA:
%attribute values in (a)~{\em global}  treatments (denoted ``g'')
%or (b)~{\em local} treatments
%for clusters 1,2,3,4.6,8.
%} \label{fig:chinaresults}
%\end{figure}
%
%\fig{options}
%lists the design options within {\IT}. The options, and how they are used, are
%discussed below.
%
%
%{\IT} is a diversive (i.e. top down) quadtree clustering algorithm 
%that divides $N$ training instances into four quadrants, then recurses on each quadrant until
%some stopping criteria is meet (e.g. quadrants contain less than $\alpha$ instances).
%Clusters are formed by combining
%neighboring leaf quadrants, if they have similar properties (e.g. similar densities). 
%The result is a tree of quadrants whose leaves are clusters.
%
%{\IT} generates the quadrants by finding (1)~the dimension of greatest variance in the data
%then (2)~an orthogonal dimension to (1). The median point of each dimension is then computed
%and the data split into the four quadrants above/below each dimensions. 
%We say that $\beta$ is the function used to find (1) and (2).
%This process $\beta$ is the core
%of {\IT}, so for RQC-1 we did not use any matrix manipulation method such as  PCA since
%such methods  require polynomial time to execute~\cite{Du2008}.
%Fasloutsos \& Lin~\cite{Faloutsos1995} offer a linear-time
%heuristic for generating these dimensions. Given $N$ instances,
%their ``FASTMAP'' heuristic finds the
%the dimension of greatest  variability to a line drawn between the two furthest points. 
%These two points are found in linear time, as follows:
%\bi
%\item Pick any instance $Z$ at random;
%\item Find the instance $X$ that is furthest away from $Z$;
%\item Find the instance $Y$ that is furthest away from $X$;
%\ei
%The line $\overline{XY}$ is the FASTMAP approximation to the first component found by PCA.
%An orthogonal dimension can be found as follows:
%\bi
%\item Declare that the line $\overline{XY}$ is of length $c$ and runs from point $(0,0)$ to $(0,c)$.
%\item Each instances has a distance $a$ to the 
%origin (instance $X$) and distance $b$ to most remote point (instance $Y$).
%\item Applying Pythagoras and the cosine rule,  each instance is  at the point $(x,y)$:
%\begin{equation}\label{eq:ab}
%\begin{array}{ccl}
%x&=&(a^2 + c^2 - b^2)/(2c)\\
%y&=&\sqrt{a^2 -x^2}
%\end{array}
%\end{equation}
%\ei
%\begin{figure}[!t]
%\begin{center}
%\includegraphics[width=2.3in]{geometry}
%\end{center}
%\caption{The geometry of {\IT}. Each blue dot is an N-dimensional instance mapped into a 2-D
%space using \eq{ab}. One dimension is the line between the instance $X$ (at the origin) and
%the most remote instance $Y$ (at the point $0,c$). Each dot has as distance $a$ from the origin
%and $b$ from the most remote instance. The median point of the dots on the $x$ and $y$ axis
%is $\hat{x}$ and $\hat{y}$, respectively. These median points divide the space into four quadrants:
%$(NorthWest)$, $(NorthEast)$, $(SouthWest)$, and $(SouthEast)$. {\IT} 
%recurses into each quadrant.}\label{fig:geo}
%\end{figure}
%
%As shown in \fig{geo}, this process can generate the four quadrants  {\em NorthWest, NorthEast,
%SouthWest, SouthEast}. To find this quadrants, we find the median points $\hat{x},\hat{y}$ that evenly divides the instances
%across each dimension. Once the quadrants are defined, {\IT} recurses into each one.
%%Αα	Alpha	Νν	Nu
%%Ββ	Beta	Ξξ	Xi
%%Γγ	Gamma	Οο	Omicron
%%Δδ	Delta	Ππ	Pi
%%Εε	Epsilon	Ρρ	Rho
%%Ζζ	Zeta	Σσς	Sigma
%%Ηη	Eta	Ττ	Tau
%%Θθ	Theta	Υυ	Upsilon
%%Ιι	Iota	Φφ	Phi
%%Κκ	Kappa	Χχ	Chi
%%Λλ	Lambda	Ψψ	Psi
%%Μμ	Mu	Ωω	Omega
%%
%
%\begin{figure}[!t]
%\begin{center}
%%include graphics[width=3.5in]{ratio.pdf}
%\end{center}
%\caption{Comparison of runtimes of Naive Bayes (one learner per cluster),
%versus the same classifier running over all the data. Data sets
%are the standard defect data sets from PROMISE. Target class is boolean:
%defective or non-defective. Data sets sorted in increasing size, left to right.
%The {\em ratio}   shows that 
%Naive Bayes localized to each cluster runs an order of magnitude
%faster than Naive Bayes.
%}\label{fig:all}
%\end{figure}
%
%
%This process can be implemented using a single sort of the clusters: after that, the algorithm
%takes linear time.
%\fig{3part} displays the leaf quadrants and clusters found by one
%run of  {\IT}-1 on XXX\footnote{andrew: what data?}.
%
%
%Five advantages of this approach are that (a) dimensionality reduction;
%(b) visualizations; (c)
%indexing; (d) fast speed; (e) low complexity; (f) scalability. 
%
%{\em Dimensionality reduction:} The 
%the recursively clustering
%on two synthesize dimensions
%avoids the
%curse of dimensionality that complicates other clustering methods such as kd-trees~\cite{bentley75};
%
%{\em Visualization:} 
%%Not only is the above process fast, but subsequent inference over the generated data structures
%%is also fast. Butcher implemented a modified Naive Bayes classifier that ran as a post-processor
%%to RQC-1. His {\em Local}  classifier  built one Naive Bayes
%%classifier for each GRIDCLUS clusters. Within those
%%classifiers, training data had three columns: the $X,Y$ co-ordinates found in the first recursive
%%call to quadtree generation and the class variable. Test instances (which were kept separate to the training
%%data) were classified using the standard Naive Bayes classifier found at the leaves of the quadtree.
%%The performance of this tree-of-classifiers was compared to that of a single {\em Global} Naive Bayes classifier training
%%on all the data. The performance statistics were collected using the standard PROMISE defect data sets
%%(source code modules described using
%%24 static code attributes and one binary class indicated defective/not-defective):
%%\bi
%%\item
%%In a 10-way cross-validation experiment, there was not performance difference (measured in terms of recall)
%%between $Local$ and $Global$ (classifiers compared using a Mann-Whitney test, 95\% confidence).
%%\item
%%The {\em ratio} plot in in \fig{all} shows the ratio of the runtimes of $\frac{Global}{Local}$.
%%Since $Local$ had to calculate Bayes likelihoods over two $X,Y$ attributes,
%%and not the 24 attributes in the raw data,
%%$Local$ ran an order of magnitude (or faster) than $Global$.
%%\ei
%%
%%The two disadvantages of our approach are $approximation$ and $explanation$.
%
%\section{WHICH}
%
%\section{WHICH}
%%For the reader conversant with the AI literature, we remark that
%%WHICH is a stochastic variant of beam search where the maximum
%%height of the stack is the size of the beam.  A standard beam search
%%explores a tree of options and performs cautious additions to each
%%leaf (at most, only grafts one more test to the current branch).
%%WHICH's original design was a non-cautious beam search that grafted
%%entire sub-trees from other branches onto the current branch. On
%reflection, we realized that the the following stack structure achieves
%the same goal, while being much simpler to implement.



\section{Validity}
{\em Assumptions:}
Our techniques assumed {\em structure implies behavior} so that
changing attribute values will also change the properties of a project (e.g.
number of defects or development time). Another assumption made by our techniques is that
the dimensions of most interest
are the {\em dimensions of greatest variability}. While we cannot prove these assumptions,
we note that they are shared by many other SE researchers:
\bi
\item
Structure implies behavior is
a widely-held in the instance-based
effort estimation community, where estimates of software effort are
generated using nearest neighbor
algorithms; e.g.~\cite{keung2008b,shepperd97,Walkerden1999,me10c,koc11}.
\item
The value of the dimensions of greatest variability is an assumption
shared by
many other researchers including those who use feature weighting based on
variance~\cite{baker07} or principal component analysis;
e.g.~Nagappan, Ball \& Zeller~\cite{nag06}. 
\ei

{\em Clustering:} One explanation for our experimental results  is that our clustering techniques are
somehow in error, and that defect/effort estimation should always
be based on the groupings identified manually by human experts.  
We
doubt this,  for two reasons. Much research
concludes that inferencing results improve after dividing data
according to automatically inferred clusters: see
~\cite{frank03,kohavi96,turhan08}, and papers at
TSE~\cite{shepperd97,keung2008b,koc11} and ASE~\cite{me10c}).

{\em Effects of stochastic search:}
Another explanation for $local$ being so different to $general$ is that we are sampling
both with a stochastic device (recall that WHICH builds rules via a stochastic search through the
space  old rules; and WHERE builds clusters by picking random points, then searching for
points further away from that 
initial point). Perhaps all that stochastic sampling has added some jitter
into the treatment selection?
We discount this possibility since we agree with
Motwani and Raghavan~\cite{motwani95}: when
sampling a space containing uncertainty, a randomized optimizer (like WHICH)
 may give you {\em greater}
stability since it is not distracted by minor gradients in the data.
We have seen evidence for this stability in the above results.
Recall the intra-quartile ranges of \fig{dists}: WHICH's rules learned from WHERE's
clusters are {\em more} stable than those learned from the $global$ analysis.

{\em Parameter settings:}
Finally, the conclusions reached here come from two specific algorithms 
run under very specific conditions (the parameter settings of \fig{parems}).
Perhaps all our conclusions are due to quirks in those algorithms and settings?
This point was discussed in the introduction. 
Certainly, there should be more work in the internals of WHERE and  WHICH
as well as other algorithms that can reason locally within data subsets or
globally across all available data. However, the internal details
of these techniques is less important than their effects when applied to data.
The goal of the above experiments is to check our
base premise; i.e. that 
when the {\em same} analysis
method is applied to {\em local} and {\em global} data, then we discover 
better and different results with  the {\em local} analysis.

\section{Related Work}

{\em Issues with Empirical SE:}
This paper opened with a commentary on conclusion instability in software engineering.
Other researchers have made similar comments.
Ideally, the practices of software engineers
should be based on methods with well-founded support in the literature.
Unfortunately, this is not currently possible.
In their pessimistically entitled paper 
	``Is Evidence Based Software Engineering mature enough for Practice \& Policy?'',
Budgen  et al.~\cite{budgen09} warn that the state of the art in empirical SE  does not 
yet recommend itself for setting management policies.
Budgen et al.'s solution is to restructure the SE literature so that it is simpler to
search large collections of research papers to find related work.
We observe that that restructuring will not solve the data heterogeneity problem
unless researchers stumble on the same clusters found by techniques like WHERE.
As shown above, finding those clusters is not a simple manual task. Therefore,
we argue for {\em both} the literature restructuring proposed by Budgen {\em as well as}
the regrouping software artifacts into clusters with similar properties.

{\em Tackling instability:}
Previously, we have 
tried to reduce conclusion instability via:
\bi
\item
Feature selection to prune spurious details~\cite{chen05};
\item
 Instance selection to prune irrelevancies~\cite{Menzies2006,koc11,me10c};
\item
 Extended data collection. 
\item
Monte Carlo simulation over the space of options~\cite{me09i}
\ei
Despite all that work, the variance observed in our 
models remains very large. Even the application of 
techniques such as instance-based learning have failed 
to reduce variance in our effort predictions~\cite{Menzies2006}.
Feature subset selection has also been disappointing: while 
(in our experiments, from 150\% to 53\%~\cite{Menzies2006}, the 
residual error rates are large enough that it is hard to 
use the predictions of these models as evidence for the 
value of some proposed approach. Lastly, further data 
collection has not proven useful. Certainly, there is an 
increase in the availability of historical data on prior 
projects (e.g. in the PROMISE repository used for this study). 
However, Kitchenham et al.~\cite{kitch07} cautions that the 
literature is contradictory regarding the value of using 
data from other companies to learn local models. 

{\em Context-specific SE:} Many authors discuss contextualizing
empirical SE. For example, Petersen \& Wohlin~\cite{petersen09} offer a rich
set of dimensions along which software projects can be contextualized (processes,
product, organization, market, etc). They offer no way to
learn new contextualizations for new projects whereas, in this paper, we only need to run WHERE
on new data to find new contexts. Also, while their arguments are convincing, they offer
no experimental confirmation that their contexts are the ``right'' contexts. This paper,
on the other hand, offers an operational test for any candidate context: the context
is interesting if it results in different and better treatments.

{\em Other clustering techniques:}
We prefer WHERE to other clustering methods like
k-means since WHERE's quadtrees  do not require multiple passes to learn the appropriate
number of clusters. 
Also, unlike clustering methods such as  EM~\cite{witten11} (that requires
some kernel assumptions to define ``near'' and ``far'' from a cluster centroid),
our cluster algorithm is a non-parametric method that works without kernel tuning.
Finally, thanks to leaf quadrant clustering, WHERE can handle clusters of very irregular
shapes (while k-means and EM work best on clusters that are mostly convex is shape).


{\em Dimensionality synthesis:}
In text mining, it is standard practice to infer a reduced
set of dimensions  via some matrix factorization
process such as PCA or the LSI technique preferred by Marcus~\cite{posh07}. Such reduction is essential
since, when text mining, the upper bound on the number of dimensions is the number of unique words in a language.
Also, some research in effort estimation infers dimensions using PCA as a pre-processor to model construction. For example, Wen et al.
use PCA as a pre-processor to analogy based effort estimation~\cite{wen09}.

To the best of our knowledge, in the fields of empirical SE,
there is no other work combining 
{\em both} clustering {\em and} inferred dimensions. 
Outside of SE, however, we can find a few examples
of such a combined approach.
For the purposes of logistic planning, Chen and Meng performing
principle components analysis, followed by clustering, as a pre-processor to their planning process~\cite{chen08}.
Also,
knowledge acquisition researchers also use clustering over synthesized dimensions. For example, in their KSS0 tool,
Gaines and Shaw display examples collected from a user in a 2D space defined by the first two dimensions
of PCA~\cite{gaines93}. This space is then studied to find gaps between the existing instances.



\section{Conclusion and Future Work}
It is to be expected that  lessons learned {\em across a population} may be somewhat different to the lessons
learned from {\em individuals within} that population. What was unexpected was just how different where
the  $local$ treatments, and how important where those differences.

In this paper, we 
compared the learning of {\em treatments} (changes that are intended
to improve some quality measure) using:
\bi
\item
Just the {\em local} data in adjacent clusters; to
\item
All the 
{\em global} data found in all clusters;
\ei
After clustering data with WHERE, and learning treatments with WHICH from either the intra-cluster data
or from all the data,
it was found that
in 18 out of 20 $local$ treatments, the treatments were completely different to the treatments
learned from a $global$ analysis of  all the data.
When those treatments were applied to the data, distributions were observed with the following properties:
\bi
\item The $local$ treatments resulted in distributions with lower variance. Specifically, the intra-quartile
range was much lower than that seen in the raw data, or the data generated with the $global$ treatments.
\item
The {\em worst-case scenario} was much less in the data generated from the $local$ treatments. 
For example, in one data set (LUCENE2.4) , for defect prediction, the treated $local$
clusters had zero defects (while in the data generated from the 
$global$ treatments, some defective modules did appear).
\item
As to the 
median results, $local$’s medians were never worse than the $global$ 
medians
and, in one case (NasaCoc) they were significantly better. 
\ei
Hence we conclude that the local treatments are both {\em different and superior to the global treatments}.

This conclusion has implications for the practices and goals of empirical SE.
Rather than seek general principles
that apply to many projects, we now advise that empirical SE should focus on ways to find 
the best local
lessons for groups of related projects.

Future work should proceed on four fronts:
\bi
\item
Techniques like WHICH and WHERE  are
useful for finding and exploiting those local groups of related projects. 
A challenge problem we offer other researchers is to review our
our methods to propose refinements and/or alternatives. 
\item
The core experiment of this paper should be repeated on many other data sets. Before making any 
general pronouncement along the lines of ``the best
way to improve software developments is...'', researchers should check if their preferred method
holds for subsets of the data.
\item
In this paper, we have only explored using WHICH and WHERE to {\em improve} a project.
The conclusions of such an analysis is a recommendation to  a manager along the lines of ``this
is what you should do''. 
An alternate analysis would be to find the actions
that most {\em degrade} a project; e.g. drives projects in cluster $C$ to a {\em worse}
cluster $C'$.
The conclusions of that other kind an analysis would
be a recommendation ``whatever you do, do \underline{not} do this''.
\item
Given  historical
snapshots of a project, we can show its path through instance space by fitting a spline through
past positions of a project. \fig{traj} shows one such progression. From this spline,
we could learn when a project is about to change contexts and, hence, will need
to change it local policies. Also,
by extrapolating forward along this curve, we could
guess the space of possible future trajectories of a project through instance space,
then try to find treatments that maintain (or improve quality)  across the space
of possible future contexts. 
\ei
\begin{figure}[!t]
\begin{center}
\includegraphics[width=1.8in]{china_polyfit_trends.png}
\end{center}
\caption{Trajectory of a project through instance space.
Generated from the CHINA effort estimation data set (http://goo.gl/0bMAR) using 
the default settings of \fig{parems}.
Note to reviewers: in the next version of this paper,
the color choices in this figure will be changed 
to support readers with red-green colorblind issues.
}\label{fig:traj}
\end{figure}

%sparse or white clusters. teac. just use nearest.

%\section{Discussion}
%This paper calls into questions 
%any number of data mining papers that
%learn models across an entire dataset, including papers by the current
%authors (e.g.~\cite{me06d,me07b}).  In those papers, it is standard
%practice to 
%(1)~report the performance of the model 
%within one data set;
%and to generate those performance statistics using
%using some hold-out study that assumes (2) the data in the hold-out set is similar to
%the training data; and that (3) the training data is representative of the kinds of data this
%model will see in its future operation.
%
%Based on this paper, we now suspect that
%reports  of type (1) are too coarse-grained (since any report of global performance
%across a range of  data may be very different to the performance
%score within local contexts. Further, we must doubt assumptions (2,3) which means, in turn,
%we
%must also doubt the evaluation results of prior papers
%(since training data has local contexts with radically different properties).
%
%On the other hand, the good news is that the tools presented in this paper describe, in detail,
%the methods required for a manager to find the specific local lessons tuned to their particular
%project.
%WHERE 
%let us uncover the local contexts while like WHICH can find the management actions that are best
%in specific contents. Also,  WHEN
%can recognize when projects are changing context (so management actions have to change).
%
%

%
%Software projects are more
%complex that previously believed. For the purposes of a coarse-grained
%analysis, it may be useful to divide projects by size, target
%industry, intended platform, criticality, location, etc. However, when
%making specific recommendations about specific projects, those
%divisions may be less informative that others that are automatically
%inferred.
%
%The results of this paper can explain the sorry state of empirical SE.
%We have so far
%failed to find general principles that hold globally
%across groups of similar projects since {\em we did not not what
%similar meant}.  Projects connect to each other in complex
%multi-dimensional patterns. Consequently, it is difficult to manually
%identify which projects are similar to each other.  
%Since (a) we can only expect
%SE principles to hold for similar projects,  and (b) it has been hard
%to 
%find such similarities, then it is hardly 
%surprising that  we
%have so few reports of SE methods that have similar effects in different projects.
%
%We recommend that,  prior to any future empirical analysis over groups of 
%software artifacts, those artifacts need to be sub-divided into their related sub-groups. That is, tools
%like those discussed in this paper are now a necessary preprocessor to any empirical analysis.
%
%Further,  we should doubt if any specific claim 
%holds across all software projects (for example, McCabe claimed that software modules
%with a cyclomatic complexity greater than 10 is likely to be defective~\cite{mccabe76}).
%Every such claim needs to be accompanied by the project artifacts used to generate that claim
%since, without those artifacts, other developers cannot judge if that conclusion drawn from
%those projects holds for the current project.
%
%Finally,
%the  {\em this search for local lessons is essential} since lessons learned from a global
%analysis may be irrelevant to specific local contexts.  While the recommend the tools discussed
%in the paper (since they scale linearly to large instance libraries and they support intuitive
%visualizations), we would hope that future research focuses on methods for (a) discovering contexts
%and (b) tuning conclusions to those conclusions. 
%
%
%
%
%\begin{figure}[!t]
%\centering
%\includegraphics[width=2.5in]{myfigure}
%\caption{Simulation Results}
%\label{fig_sim}
%\end{figure}



%
%\begin{figure*}[!t]
%\centerline{\subfloat[Case I]\includegraphics[width=2.5in]{subfigcase1}%
%\label{fig_first_case}}
%\hfil
%\subfloat[Case II]{\includegraphics[width=2.5in]{subfigcase2}%
%\label{fig_second_case}}}
%\caption{Simulation results}
%\label{fig_sim}
%\end{figure*}
%


%
%\begin{table}[!t]
%% increase table row spacing, adjust to taste
%\renewcommand{\arraystretch}{1.3}
%\caption{An Example of a Table}
%\label{table_example}
%\centering
%% Some packages, such as MDW tools, offer better commands for making tables
%% than the plain LaTeX2e tabular which is used here.
%\begin{tabular}{|c||c|}
%\hline
%One & Two\\
%\hline
%Three & Four\\
%\hline
%\end{tabular}
%\end{table}


 
% \section{BORE (Best OR Rest)}

% \begin{algorithmic}
% \STATE LET Data = \{Instances\} 
% \STATE LET Attributes = \{Column-wise attributes\}
% \STATE LET Best = \{Instances $\in$ Data of the best class\}
% \STATE LET Rest = \{Instances $\in$ Data of all other classes\}
% \FOR {A $\in$ Attributes}
%     \FOR {bin $\in$ A}
%     	\STATE Prob\_BEST = $|Best|$ / $|Data|$
%     	\STATE Prob\_REST = $|Rest|$ / $|Data|$
%     	\STATE FREQ($bin|Best$) = $|$ $\{ bin | bin \in  Best_A\}$ $|$ / $|Best|$
%     	\STATE FREQ($bin|Rest$) = $|$ $\{ bin | bin \in Rest_A \}$ $|$ / $|Rest|$
%     	\STATE LIKE($Best|bin$) = $FREQ(bin|Best) * Prob\_Best$
%     	\STATE LIKE($Rest|bin$) = $FREQ(bin|Rest) * Prob\_Rest$
%    		\STATE LIKE\_BEST\_REST = LIKE($Best|bin$) + LIKE($Rest|bin$)
%    		\STATE RANK = LIKE$(Best|bin)^2$ / LIKE\_BEST\_REST
%     \ENDFOR
% \ENDFOR
% \end{algorithmic}


% \section{Cliff}
% \begin{algorithmic}
% \STATE LET Data = \{Instances\}
% \STATE LET Criterias = \{Highest ranked value,attribute sets for each class obtained from BORE\}
% \STATE LET Prototypes = \{\}

% \FOR { value,attributes $\in$ Criterias }
% 	\STATE Prototypes = Prototypes $\cup$ $ \{ instances | instances \in data, value \in instance_{attributes}\}$
% \ENDFOR

% \end{algorithmic}

% \section{Midpoint Sampling}
% \begin{algorithmic}
% \STATE Pick a point $P_1$ randomly from training set.
% \STATE Pick the closest point $P_2$ in the training set belonging to the opposite class.
% \STATE Find the midpoint $M$ between $P_1$ and $P_2$.
% \STATE Request a classification for the closest unlabeled point to point $M$.
% \end{algorithmic}







%\IEEEtriggeratref{8}
%\IEEEtriggercmd{\enlargethispage{-5in}}


\bibliographystyle{IEEEtran}
\bibliography{bi,refsold}
%
%\begin{thebibliography}{1}
%
%\bibitem{IEEEhowto:kopka}
%H.~Kopka and P.~W. Daly, \emph{A Guide to \LaTeX}, 3rd~ed.\hskip 1em plus
%
%\end{thebibliography}
%



\end{document}

