\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{EE \& CS, 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{Tom 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 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}
  Contrast set learners can infer what needs to
  change in order to alter the effort/defect predictions of a
  project/software module.  We show that rules found from a {\em local
    analysis} of neighboring clusters are markedly different to those
  found from a {\em global analysis} of all data. That is, at least for the data sets
explored here, what
  appears to be useful in a global context was {\em mostly irrelevant in
  particular  local contexts}. 

We therefore recommend {\em locality testing} for supposedly general conclusions:
SE researchers should test their conclusions by applying them to subsets
of the data. To be meaningful, those subsets should contain related projects.
This paper discusses the types of tools needed to support such locality tests.
\end{abstract}

\begin{IEEEkeywords}
Business intelligence, data mining, visualization, contrast set learning,
clustering, PROMISE.
\end{IEEEkeywords}

\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.
There are many  kinds of empirical software engineering:
\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 observes 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
As discussed in the next section, a 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 was 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\%).



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 thesis of this paper is that such divisions may be uninformative.
If we apply clustering tools to SE data, the resulting divisions
do not conform to any category that we can identify. 
More importantly, for the purposes of learning {\em treatments} (changes that are intended
to improve some quality measure), the following {\em locality test} shows that
it is important to constrain conclusions regarding ``what is the best treatment''
to within those divisions.
When we compare the treatments found via a 
{\em local} analysis (using data from one cluster)
and a  {\em global} analysis (using data from all clusters), we found:
\begin{quote}{\em
The local and global treatments  are usually different.  
}\end{quote}
That is, the lessons learned
from a global analysis  of supposedly similar projects {\em may not apply to individual projects}.

As shown below, generating these clusters is not a simple manual
analysis.  Hence, when testing their treatments, prior induction
studies may not have used data subsets that generate similar
conclusions.  That is, induction studies have not found general
principles since {\em they have  been tested on the wrong
data}.  Further, if researchers expect general conclusions from
induction studies, they may be disappointed: {\em conclusions about
software projects may not generalize beyond small subsets of
projects}.

Our conclusion is that empirical SE needs to focus less on
generalities and more on context-specific principles. This conclusion
could refuted using the same locality test described in this paper.
That is, our conclusions are wrong if, when researchers apply the
locality test, they find that the {\em local lessons are the same as
the global lessons}.

If our conclusion cannot be thus refuted, then four research
questions arise.  Firstly: how to find subsets of
similar data?  Like other researchers, 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.  This assumption is widely-held in the instance-based
effort estimation community (where estimates of software effort are
generated using nearest neighbor
algorithms~\cite{keung2008b,shepperd97,Walkerden1999,me10c,koc11}).
The ``WHERE'' tool, discussed below, is a linear time clustering
algorithm that assumes {\em structure implies behavior}.

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.  This assumptions is shared by
many other researchers including those use feature weighting based on
variance (e.g.~\cite{baker07}) or principle component analysis
(e.g.~Nagappan, Ball \& Zeller~\cite{nag06}).  

Thirdly: how to  extract treatments from local
regions?  Often, these regions are too small to enable parametric
model.  Consider a data set with two dozen attributes that forms clusters
containing less that 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 contrast set learner that infers what needs to change
in order to best alter the distribution of some target quality variable.
 
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'' tools offers a
simple visualization that simplifies that tracking process.


Regardless of the technology used, the
main contribution of this paper is that local lesson learning is an
open and urgent issue.  The results of this paper make us
uncomfortable with global claims about software projects and software
processes.  The tools presented here (WHERE, WHICH, and WHEN) 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. A challenge problem we offer other researchers is to review our
our methods to propose refinements/alternatives.


The rest of this paper is structured as follows. 
After some offer background notes on conclusion instability in software engineering and contrast set learning, we discuss the technical
details of WHERE, WHICH, and WHEN.
% 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}. 
These tools are then applied to data from the PROMISE repository (http://promisedata.org/data).

\section{Background}

This section is our evidence for an assertion made in the introduction:
 that conclusion instability is a common problem in empirical SE.

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 in the empirical SE literature.
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 software engineering 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 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). According to EBSE, 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 the state of the art in EBSE 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 propose a different solution.
Rather than restructure the literature, we propose
regrouping software artifacts into clusters with similar properties.
Management decisions for a local region can then be generated by asking for the difference 
between neighboring clusters that selects for the neighbors with higher quality (in the following,
we will measure quality in terms of development effort or number of defects).

\section{Contrast Set Learning with WHICH}

When we show data mining output to business users, their
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~change=\epsilon_1 / \epsilon_0\]
where $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 subset of the baseline and target instances
selected by $R_x$. 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 $better$ instances.

Apart from minimizing $\epsilon_1/\epsilon_0$,
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 the applying the C4.5 decision tree learner~\cite{quinlan92} to 
20,000 outputs from a Monte Carlo simulation of a software
process model.  The outputs of that simulation were grouped into
 {\em low, medium} and {\em high} risk where ``risk''
was computed using the software process model.  The left-hand side of
\fig{trees} counts the number of branches in that tree that lead to
different outputs.
Our business users could not understand that tree. 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 ranked those differences by how much they pruned/retain
branches to undesired/desired classes (respectively).  
This process often generates tiny rules. For example,
TARZAN's analysis of a decision tree with 400 nodes returned the small
rules  shown middle and left of \fig{trees}.
As a result, we can could our users  succinct rules
describing what needs to change in order to select for certain desired classes.

TARZAN was designed as a post-processor to  C4.5. Subsequent
research showed how to achieve the same goal, without requiring
C4.5~\cite{me03c,me07}.  Later versions optimized the reasoning with
stochastic~\cite{hu02} and Bayesian reasoning~\cite{clark05}. 
The latest version, called WHICH~\cite{me10e},
allows for arbitrary evaluation criteria.
WHICH loops over 
attribute values combinations, combining those that look most promising:
\be
\item
Data from continuous attributes are discretized into ``$\beta$'' equal frequency values.
\item
A stack is built that sorts treatments (pairs of attribute values),
according to their $\epsilon_1/\epsilon_0$ scores.
\item
That stack is initialized to hold one rule for every attribute value.
\item $\kappa$ number of times, do:
\bi
\item Generate $\lambda$ number of new rules, as follows.
\bi
\item Pick a  pair of old rules at random, favoring those with 
better $\epsilon_1/\epsilon_0$.
\item Combine the pair into a new rule. Score it.
\ei
\item
Sort the  $\lambda$ new rules into the stack.
\ei
\item Repeat step 4 until no new improvements seen in the best score.
Return the rule 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}).

\begin{figure}[!t]
\begin{center}
{\footnotesize
\begin{tabular}{|c|c@{~}p{1.3in}|p{0.8in}|}\hline
tool & name &  notes & default\\\hline
WHICH & $\beta$  & number of bins for descretizing number attributes & $\beta=7$\\\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$
\\\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}

\begin{figure}[!b]
\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}

WHICH is controlled by the settings of \fig{parems}.
Note that WHICH will accept  a variety of functions to calculate $epsilon_i$:
any function that returns a positive real number
is acceptable.
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 by
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 ever 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.

Like TARZAN, WHICH generates tiny rules that business users can quick read. Since it also can be customized for different tasks
(as seen in \fig{allr}) then we often use it in induction studies
 to generate recommendations for business users on how to improve their projects. 
In the following, 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). 


\section{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 principle 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 raw data and the orthogonal component $I+1$ tries to account for the remaining variability.
\begin{figure}[!b]
\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}

Matrix factoring methods like  PCA 
take 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 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).

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 instances 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*}[!t]
\begin{center}
\includegraphics[width=5.5in]{ab.png}

{\em {\footnotesize \begin{tabular}{p{1.9in}p{1.9in}p{1.9in}}
Initial two dimensions. &After quadtree generation.& After  clustering 
of neighboring leaf
quadrants.
\end{tabular}}}

\end{center}
\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}.
}\label{fig:3part}
\end{figure*}


\fig{3part} shows four quadrants defined by the
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 depth-first recursive search through 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 in 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).
Note that some clusters can have less than $\alpha$ members. This occurs when a parent cluster has less
than $2*\alpha$ items.


An important inference supported by these visualizations
is detecting when a project is {\em brittle}; i.e.
minor changes to the project may cause large changes to its properties.
This is important when (e.g.) small changes to a project can drive that project from
regions of (say) low development effort to regions of high development effort.
In this regard, the manager of project ``A'' (in \fig{3part}) should be more alarmed
that the manager of project ``B'', since the former is much closer to regions of much high
development effort.
Note that we can formalizes this notion of ``what can effect a project''
using the
WHICH contrast set learner.

This approach scales very well to large data sets.  WHERE scales
linearly on number of rows and dimensionality of the data.
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.


As to linear scalability on the number of rows, \fig{scales}  shows runtimes after applying WHERE to
data sets from the PROMISE repository, 
where the rows are copied once, twice,
four, or eight times.
\begin{figure}[!b]
\includegraphics[width=3.2in]{all.pdf}
\caption{WHERE's runtimes scale linearly on number of rows.}\label{fig:scales}
\end{figure}
The above shows runtimes for a PYTHON version of WHERE measured against
data sets whose rows have been copied once, twice, four, and eight times. 
Note that the runtimes scale linearly with data set size.
Generate from PROMISE defect prediction data
(CM1, KB2, MW1, KC3, PC1, KC1 from http://goo.gl/fNgNW) using 
the defaults of \fig{parems}.
Note that the runtimes scale
linearly on number of rows.



Note that FASTMAP is a  heuristic technique that may not
find the points that  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
Fasloutsos \& Lin~\cite{Faloutsos1995}: in practice, the approximate dimensions
found by FASTMAP 
does not degrade inferencing (compared to other more reflective, and slower, approaches).

\section{Learning WHEN to Change Policies}
The thesis of this paper is that the best management policy for a
project is context dependent.  Such a claim is most useful if it comes
with tools to recognize context shift.
This is task of the WHEN tool.
By showing a manager their project within a 2-D
display, it is possible to visualize the space of options around the
current situation.
For example, given $X$ historical
snapshots of a project, we can show its path through instance space by fitting a spline through
those points. \fig{traj} shows one such progression. As the project moves into the red regions,
managers should expect slower progress.

The trajectory shown in \fig{traj} is based on an extrapolation of past changes to a project.
The more we extrapolate that trajectory, the less certain it becomes.
Hence, we assign more confidence to near predictions (that a project is about to jump out
of its current context) than its far predictions. In future work, we plan to explore
the effects of uncertainty in WHEN's trajectory. For example:
\bi
\item
In the following
experiment we use WHICH between two neighboring clusters in order to find the action
that most reduces effort or defects. 
\item
In future work, we might apply WHICH to find actions that are most likely to work across
the space of possible clusters (where ``possible clusters'' are those near the future trajectory mapped
out by WHEN).
We do not explore this issue in this paper since we are still collecting information about
uncertainty in our data collection.
\ei
\begin{figure}[!b]
\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}.
}\label{fig:traj}
\end{figure}


\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{4.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=\left(\left(  \frac{1}{a} \sum_j^a \mu(a_j)\right) - m \right)/ (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. The last row is the dependent variable.}\label{fig:lucene}
\end{figure*}

\section{Experiments}

The goal of these experiments is to compare the ``best'' management action 
learned from a global analysis over all data vs the ``best'' action learned from
a local per-cluster analysis.
The WHERE and WHICH tools described above were  used to  find those management actions.

For this study, two data sets from http://promisedata.org/data were used.
CHINA is a collection of 499 software development projects, each 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).
LUCENE2.4 is a defect log on the 340 classes of  an object-oriented JAVA-based search engine optimized for text mining.
Each class is described in terms of the standard C-K metrics for object-oriented systems~\cite{chid94}.
The attributes of these data sets are shown in \fig{china} and \fig{lucene}.

These data sets were selected for this study since:
\bi
\item
They are as different as possible (one relates to effort estimation and the other to defect prediction).
\item
They are public domain, so other researchers will be
 able to reproduce/ improve/ or even refute our conclusions.
\ei
Apart from that, to the best of our knowledge, there is nothing special or unique about these data sets.
For example, the effects we find in CHINA and LUCENE2.4  (that  the best local action is mostly different to
the best global action) have also been seen in every other PROMISE data set we have analyzed
(those studies, with data sets other than CHINA and LUCENE2.4, are not shown here for reasons of space).

\begin{figure*}[!t]
{\scriptsize
\begin{tabular}{|c|c|}\hline
Cluster&	Size\\\hline
C0&	28\\
C1	&97\\
C2&	117\\
C3&	39\\
C4&	40\\
C5&	$<$ 20\\
C6&	29\\
C7&	$<$ 20\\
ALL    & 499\\\hline
\end{tabular}\hspace{0.5in}
\begin{tabular}{|r|l|l|l|l|l|l|l|l|l|l|}\cline{2-11}
        \multicolumn{1}{c|}{~}&\multicolumn{10}{c|}{value}\\\hline
attribute&1&2&3&4&5&6&7&8&9&10\\\hline
added&&&\G ALL&\G ALL, C3&&&&&&\\
afp&\G ALL&\G ALL&\G ALL, C3&\G ALL&&&&&&\\
changed&C0, C3, C7&&&&&&\G ALL&C3&&\\
deleted&C0, C2, C3, C4, C5, C7&&&&&&&&&\\
dev.type&C0, C1, C2, C3, C4, C5, C6, C7&&&&&&&&&\\
duration&\G ALL&\G ALL, C3&&&&&&&&\\
enquiry&&&\G ALL&&&&&&&\\
file&C3&\G ALL&\G ALL, C3&C3&&C3&&&&\\
input&\G ALL&&&\G ALL&&&&&&\\
interface&C0, C3, C5&&&&&&&&&\\
npdr\_afp&\G ALL&&&&&&C3&&&\\
npdu\_ufp&&&&&&C3&&&&\\
output&C3&&&&&C3&&&&\\
pdf\_afp&\G ALL&&&&&C3&&&&\\
pdf\_ufp&\G ALL&&C3&&&&&&&\\
resource&C0, C2, C4, C5&&&&&&&&&\\\hline
\end{tabular}}
\caption{Effort reduction results from CHINA.
{\bf Left-hand-side:} cluster sizes found by WHERE. Contrast sets C5,C7 where
excluded from this analysis due to their small size.
{\bf Right-hand-side:} WHICH rules' attribute values for contrast
 between  clusters C0..C4,C6 and their neighboring clusters with lowest median development
effort.
``All'' denotes attribute values seen in
contrast sets learned from all the data, divided into 20\% lowest development effort and 80\% rest.
Note that the ``All'' attribute values have little
overlap with values from other contrast sets.
}\label{fig:chinaresults}
\end{figure*}

\begin{figure*}[!t]
{\scriptsize
\begin{tabular}{|c|c|}\hline
cluster&	size\\\hline
C0&	79\\
C1&	26\\
C2&	26\\
C3&	64\\
C4&	35\\
C5&	$<$ 20\\
C6&	$<$ 20\\
C7&	$<$ 20\\
ALL&	340\\\hline\end{tabular}\hspace{0.5in}
\begin{tabular}{|r|l|l|l|l|l|l|l|l|l|l|}\cline{2-11}
\multicolumn{1}{c|}{~}&\multicolumn{10}{c|}{value}\\\hline
attribute&1&2&3&4&5&6&7&8&9&10\\\hline
amc&\G ALL&&&&&&&&&\\
avg\_cc&\G ALL&&&&&&&&&\G ALL\\
ca&&C3&&&&&&&&\\
cam&&&&&&&C0&&&\G ALL, C4\\
cbm&C0, C3, C4&&&&&&&&&\\
cbo&\G ALL&\G ALL&&&&&&&&\\
ce&\G ALL&\G ALL&&&&&&&&\\
dam&C0, C4&&&&&&C0, C3&&&\\
dit&C0, C3, C4&&&&C0, C3&&&&&\\
ic&C0, C3, C4&&&&&&&&&\\
lcom&C0, C3&&C0, C4&&\G ALL&\G ALL&&&&\\
lcom3&&&&&&&&&&\\
loc&\G ALL, C4&&&&&&&&&\\
max\_cc&C0, C4&&&&&&&&&\\
mfa&C0, C3, C4&&&&&&&&&\\
moa&C0, C2, C3, C4&&&&&&&&&\\
noc&C0, C1, C2, C3, C4&&&&&&&&&\\
npm&\G ALL&\G ALL&\G ALL&&&&&&C3&\\
rfc&\G ALL, C4&\G ALL, C0&\G ALL&&&&&&&\\
version&C0, C1, C2, C3, C4&&&&&&&&&\\
wmc&\G ALL, C4&&\G ALL&&&&&&&\\\hline
\end{tabular} 
}
\caption{Defect reduction results from LUCENE2.4.
{\bf Left-hand-side:} cluster sizes found by WHERE. Contrast sets C5,C6,C7 were excluded from this
analysis due to their small size.
{\bf Right-hand-side:} WHICH rules' attribute value for contrast
 between  clusters C0..C4 and their neighboring clusters with lowest median development
effort.
``All'' denotes attribute values seen in
contrast sets learned from all the data, divided into 20\% lowest defects and 80\% rest.
Note that the ``All'' attribute values have little
overlap with values from other contrast sets.
}\label{fig:luceneresults}
\end{figure*}
%\section{Inside {\IT}}
%\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.



\bi
\item
For each cluster $C$, a {\em local}  analysis was conducted as follows. 
Let $C'$ be the neighboring cluster with the best median quality score.
\item
For the {\em global} analysis, all available training data
was sorted on some quality measure. This data was then  divided into a 20\% ``best''
group and a 80\% ``rest'' group (the 20\% value was selected to match, approximately, the size
of the clusters used in the local analysis). 
\ei

\section{Validity}


One explanation for this is that our clustering tools are somehow in error,
and that defect/effort estimation should always be based on the groupings indentified manually
by human experts. We doubt that conclusion since much research concludes
that 
 when we divide data according to automatically inferred clusters, then the r
 contradicts much work on the value
of constraining data mining to automatically detected subsets of interest within a 
data set~\cite{frank03,kohavi96,turhan08}, including papers at TSE~\cite{shepperd97,keung2008b,koc11}
and ASE~\cite{me10c}. 
For example, Turhan found taht NN improved reasoning

why has it not been seen before? it has. boehm cheery picks

Other data sets.

other default settings

other optimizers

\section{Related Work}
Unlike clustering methods like
k-means, 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.


other reans for isntability: statiscal anomalies

porrt lit review

context-specific nature of SE reasoning widely recognized (basili, rumbaugh). but as to what we do about it...

lots of work on correlation work based on components. e,g, machine PCA. 

XXX change evil measures. weight results by distance data to test.
this will be a sum over many which will be simplified by pre-clustering.
suspect we will see more of our clustering methods in future

NB tree. 

Turhan's instance then NB

Many researchers use clustering or inferred dimensions. The
combination of the two techniques, as used in this work, is not very
common.

Clustering has been applied in many software engineering fields to
(e.g.) infer the structure of software projects~\cite{sel}. In the
that, the researchers did not check the recommendations of best
practice associated with each cluster.

In text mining, it is standard practice to perform 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.

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 software engineering (the two case
studies explored in this paper), 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:
\bi
\item
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}.
\item
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.
\ei

\section{Discussion}

Question f which metrics to collect now irrelevant

explains variable in feature selection results seen in prior work: cant feature select for whole space
cause its all local

Also, raises questions about evaluation. A common practice in data mining is to assess the performance 
of data via some hold-out study where a model is learned on some examples, then tested on some {\em other}
set of examples. A premise of that procedure is that (a)~the other examples are similar to the training data;
and that (b)~the training and test data is similar to the kinds of examples the model will be applied too 
in the figure. Based on this work, we now doubt both assumptions.
XXX.

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



\section{Conclusion}

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}

