\documentclass[conference]{IEEEtran}
\usepackage{times,cite}
\usepackage{algorithmic}
\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 
\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}
Using data sets relating to effort estimation and defect prediction,
rules are either from
(1) a local analysis of neighboring clusters or  (2) from a global analysis of all data.
The generated rules were found to be very differnt;
i.e.
what {\em seems} like a good idea in general may be {\em irrelevant}
with a local context. This result calls into question much current empirical research in SE
that assumes that conclusions are stable within particular projects.
To aid further research in context-specific reasoning about SE data,
we present the WHERE tool that 
finds the local contexts within data;
the WHICH tool that exploits that context in order
to generate management advice; and the WHEN tool that
shows a manager when their context is about to change.

\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 apposed 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.
%%Deacdes later, hundreds of ther researchers have proposed numerous alternatve
%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 similiar result, Turhan et al.~\cite{me09b} applied defect
%predictors learned from other comparies 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.
The goal of science is {\em conclusion stability}, i.e.\ to find 
an effect $X$ that holds in multiple situations.  Sadly, there
are all too few examples of stable conclusions in software engineering
(SE). In fact, the typical result is {\em conclusion
\underline{in}stability} where what is true for project one, does
not hold for project two.

For example, in the field of {\em software development effort estimation},
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.
Also,
Mair and Shepperd~\cite{mair05} compared regression to analogy methods.
From 20 empirical studies, seven favored regression, four were indifferent and nine favored analogy. 
Further,
Kitchenham et al.~\cite{Mendes2007}  reviewed empirical studies that compared models
learned from data collection {\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).

A similar pattern of  no generality 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$.
In
a similiar result, Turhan et al.~\cite{me09b} applied defect
predictors learned from other comparies to some local company. The
resulting detectors had high detection rates (over 90\%) but at the
cost of very high false rates (over 60\%).



Software engineering is such a varied activity that we doubt that any
 general trisum (e.g. ``using the SEI capability maturity model reduces defects'')
will hold in all contexts. Rather, we need to restrict our generalizations
to {\em contexts of related projects}.
How can these contexts be defined?
Should we use:
\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 \& Turhan.
\ei
This paper argues that such divisions may be uninformative since,   within a group
of supposedly related projects, we can  local contexts which have very different properties
to the global context of all projects. 
To show these, we present
three automatic tools for finding and using groups of related
software artifacts with similar properties (we call such a grouping a ``context''):
\bi
\item 
The WHERE tool {\em infers project context}. Dimensionality synthesis methods will
find the dimensions of software projects that most seperates them. Using those
dimensions,  instances are
divided into a quadtree (where each quadrant has four sub-quadrants).
Neighboring leaf
quadrants with similar properties are then clustered together.
\item
The WHICH tool {\em learns the best management action for each context}.
Neighboring clusters
will be examined by contrast set learning to find the management action that would drive
projects from one cluster to its best neighbor.
\item 
The WHEN tool {\em advises when a project is changing context}. By fitting a spline to the history
 of a project, we  compute the trajectory of that project through
the clusters.  By extrapolating along that spline, it is possible to detect
when a project is about to enter another cluster where different ``best'' management actions
would apply.
\ei
Of the above, WHERE and WHEN are new tools while earlier versions of
WHICH have been reported previously~\cite{me00e,me02f,me07,me07d,me10a}.
Here, we optimize WHICH by focusing its inference on just the contexts found by the WHERE tool.

Using these tools,
we
compared the best management actions in the global space (learned by WHICH from
all 
data) and in the local contexts (learned by WHICH working within WHERE's clusters).
The key finding of this paper is:
\begin{quote}{\em
In the majority case, the local and global best actions are different.  
}\end{quote}
That is, the lessons learned
from a global analysis  of supposedly similar projects {\em may not apply to individual projects}.
Note that this explains the failure of empirical software engineering to demonstrate that some
method holds across mulitple projects. 
Empirical SE has not found general principles since {\em it has
been testing
treatments on the wrong projects}. As shown below, finding groups of similar projects
is not a simple manual task. Hence, when prior work tried to
test if some treatment works on similar projects,
their definition of ``similiar'' may have been wrong. With the tools of this paper, we can
improve on the current state of empirical SE since it is now possible to identify
``similar'' projects.


The rest of this paper is structured as follows. 
We first offer background notes on the lack of generality in software engineering, plus some technical descriptions of the internals of the clustering
tool used in the LOCAL analysis, and the WHICH data miner used to learn the management actions
(WHICH is a  
contrast set learner that finds
the minimum delta between two groups which has been used successfully in many other applications~\cite{me00e,me02f,gay10,me04a,me10a}).
% 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}. 
After describing this paper's clustering and data mining tools, we present the global and local studies.

\section{Background}
This section documents the current state of empirical software engineering.
In summary, despite years of research, there is a broad concensus
that empirical software engineering has not found treatments that result in  similar
effects across different projects. The work described in the rest of this paper is in direct
response to this issue.

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 Holzmann~\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
purportedly 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 ``lack of demonstrably 
generality''.
Menzies \& Shull~\cite{me10b}
 reviewed all presentations made at the PROMISE   conference on repeatable software engineering experiments based on publicly available data sets. In the period 2005 to 2009, at the PROMISE conference:
	there have been 68 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:
	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 PROMSIE 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 si that it is simpler to
search large collections of reserach 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.

\section{Using WHERE to Find Similiar Projects}
Like other researchers, we assume that {\em structure implies behaviour}; i.e. that
software artifacts
that are similar with respect to their features will be also similar
with respect to their behavior. This is a widely-held belief in, say, the instance-based
effort estimation community where estimates of software effort
are generated using 
nearest neighbor algorithms~\cite{keung2008b,shepperd97,Walkerden1999,me10c,koc11,} 

This section describes WHERE, a fast clustering algorithm for multi-dimensional
data. WHERE is an adaptation of kd-trees~\cite{bentley75} but, instead of dividing
the data on all the observed attribites, it applies 
Fasloutsos \& Lin~\cite{Faloutsos1995}'s FASTMAP heuristic to synthesize
two dimensions at each level of the recursion. The leaves of the resulting tree of
clusters are then combined using 
Schikuta~\cite{Schikuta93}'s GRIDCLUS algorithm. 

\subsection{Quadtree Generation}

Dimensionality {\em selection} methods
prune less informative dimensions~\cite{hall03} while dimensionality {\em synthesis}
methods learn new dimensions that better describe the origianl data sets.
For example, matrix factoring methods such as principle component analysis (PCA) transforms
the $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.

Matrix factorization methods such as  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'' heurestic finds the
the dimension of greatest  variablility 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=3in]{geometry}
\end{center}
\caption{Dimensionality synthesis with FASTMAP.
Each blue dot is an D-dimensional instance mapped into a D=2 dimensional
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)$. 
}\label{fig:geo}
\end{figure}
\begin{figure*}
\begin{center}
\includegraphics[width=6in]{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 softwre 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 
\mbox{$\alpha,\delta=\sqrt{N},0.5$}.
}\label{fig:3part}
\end{figure*}


If we compute the median values of each dimension ($\hat{x},\hat{y}$), we can divide
the instances into 
four quadrants  {\em NorthWest, NorthEast,
SouthWest, SouthEast}. 
WHERE recurses on each quadrant to generate a 
balanced tree of quadrants.
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)$).


\subsection{Clustering Leaf Quadrants}
Schikuta~\cite{Schikuta93} warns that quadtrees can needlessly sub-divide the data
when, for example, neighboring leaf quadrants have similar properties. Hence, as a post-processor
to quadtree generation, WHERE
combines similiar leaf quadrants as follows:
\be
\item Stop WHERE's recursion when the divided instances contain less than $\alpha$ percent
of the original data (this stops the over-generation of an accessive amount of tiny leaf quadrants).
\item Sort all leaf quadrants
by their density (number of instances per clustering). 
\item Define {\em sparse} to be $\delta\%$ of the max density.
\item
Starting with the densest cluster,
perform a depth-first recursive search through neighbors of this first quadrant, stopping when the density
is below $sparse$.
\item
All quadrants connected
in this way are removed from the sort order and
added into their own seperate cluster.
\item Goto  step 4 to find  the next cluster or terminate if the first remaining
cluster  has  $sparse$ density.
\ee
\subsection{Example}
\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). 
For this run, we used $\alpha,\delta=\sqrt{N},0.5$ (respectively) where $N$  are the 93 instances
in NASA93. 
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 recursed into 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.
We formalizes this notion of ``what can effect a project''
using the
WHICH contrast set learner.

\subsection{WHERE: Discussion }
One theoretical disdvantage with WHERE is
that 
since it runs so fast (due to its use of  the  FASTMAP heuristic) it  may generate inaccurate dimensions.
To check this, elsewhere~\cite{nelson11}
we have conducted extensive experiments with the FASTMAP hueristic 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).

As to other technology options for WHERE, 
 see \fig{why}.

\begin{figure}
{\small
\begin{tabular}{|p{.92\linewidth}|}\hline
Unlike clustering methods such as
k-means, WHERE's use of quadtree  does not require multiple passes to learn the approapriate
number of clusters. 

~\\

Also, unlike clustering methods such as  EM~\cite{witten11} (that makes 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.

~\\

Further,  this approach scales very well to large data sets.  WHERE scales
lineraly 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 dimensioanlity''. Since WHERE alwayys 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 nuber of rows, the following plots  shows runtimes after applying WHERE to
data sets from the PROMISE repository, 
where the rows are copied once, twice,
four, or eight times.
\begin{center}
\includegraphics[width=3.2in]{all.pdf}
\end{center}
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, KC2, MW1, KC3, PC1, KC1 from http://goo.gl/fNgNW) using 
\mbox{$\alpha,\delta=\sqrt{N},0.5$}.
Note that the runtimes scale
linearly on number of rows.\\\hline
\end{tabular}
}
\caption{Concerning Technology Choices in WHERE.}\label{fig:why}
\end{figure}
\newpage


\section{Using WHICH to Learn Policy Changes}
When we show managers diagrams like  \fig{3part}, their natural first question is ``what
does this say about how to improve a project?''. To answer this question, we use
{\em constrast set learning} to infer rules describing differences between clusters
found by WHERE. A contrast set rule takes the form 
\[if~CONDITION~then~CHANGE=\frac{\epsilon_1}{\epsilon_0}\]
where $condition$ is some conjunction of attribute values and $change$ is some measure
of how much the performance score 
in the data selected by $condition$  
(denoted $\epsilon_1$) 
improves
the
baseline scores in the original training data (denoted $\epsilon_0$).
This section describes WHICH, our preferred tool for generating rules describing how
to covert instances in one context to some other.

\subsection{Main Loop}
WHICH loops over the space of
possible attribte ranges, evaluating various combinations of attributes:
\be
\item
Data from continuous features is discretized into ``$\beta$'' bins using the
Fayyad-Irani descritizer~\cite{FayIra93Multi}. 
\item
WHICH maintains a stack of attribute combinations,
sorted by a customizable search  bias $\epsilon$ .
For example, given a training set containing two clusters found by WHERE,
$\epsilon_0$ could be the median performance score see across the two clusters
and $\epsilon_1$ could be the median performance score seen in the instances that match
the attribute ranges in the 
combination.
\item
Initially, WHICH's ``combinations'' are just each range of 
each attributes. Subsequently,
they can grow to   two or more attributes.
\item Two combinations are picked at random, favoring those combinations 
that are ranked highly by $\epsilon_1/\epsilon_0$.
\item The two combinations are themselves combined, scored, then sorted into the stacked
population of prior combinations.
\item Go to step 4.
\ee
For the reader aware of the artificial intelligence (AI) literature, we remark that WHICH is a variant of  beam search.
Rather than use a fixed beam size, WHICH uses a fuzzy beam where combinations deeper in the
stack are exponentially less likely to be selected. Also, while a standard beam search just adds child
states to the current frontier, WHICH can add entire sibling branches in the search tree (these sibling
branches are represented as other combinations on the stack).

After numerous loops, WHICH's contrast set is the rule with the highest ranked combination
of attrubutes. 
%\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}).
To control the number of loops,
WHICH loops 100 times
then looked at top-of-stack. If a new best top-of-stack had been found,
then algorithm loops another  100 times more (and more, if a new best top-of-stack is found). Otherwise, the algorithm terminates. 
\begin{figure}
\includegraphics[width=3.5in]{Norm_Traj}
\caption{Simulated rocket trajectories studied by WHICH at NASA. From~\cite{gay10b}.}\label{fig:traj}
\end{figure}

We use this algorithm to learn management actions since it is {\em fast} and {\em relatively
more proficient} than alternate methods we have explored.
This algorithm
has been used at NASA to find settings that improved the
performance of complex guidance, navigation and control flight
simulators~\cite{schmann07,me08fh,me09c}.  These simulators have
hundreds of inputs with many complex and difficult-to-understand
interactions.  The simulators generated the rocket trajectories of
\fig{traj} (each trajectories are colored according to their distance
from the proposed touch-down point: the closer to touch-down, the
better). In comparisons with state-of-the-art gradient descent
algorithms (a Quasi-Newton method that incremental updates a Hessian
approximation), our approach ran 30 to 48 times {\em faster} that the
state-of-the-art optimizer, and found {\em better} solutions (much
higher precision and recall)~\cite{gay10b}. 
\begin{figure}
\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 
\mbox{$\alpha,\delta=\sqrt{N},0.5$}.
}\label{fig:traj}
\end{figure}

\section{Learning When to Change Policies With WHEN}
The thesis of this paper is that the best management policy for a project is context dependent.
Such a claim is most useful it it comes with tools to recognize when the context, and hence the policies
need changing.
In the above, we describe the WHERE tool (to learn contexts) and the WHICH tool (which can learn the
deltas between contexts). This section describes the WHEN tool which advises when a project is about
to change context.

By showing a manager their project within this
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 shoukd expect slower progress.



\section{Experiments}

\begin{figure*}
\begin{center}
{\scriptsize
\begin{tabular}{r|l|l|l|l|l|l|l|l|l|l}
attribute&1&2&3&4&5&6&7&8&9&10\\\hline
AFP&ALL&ALL&ALL, C3&ALL&&&&&&\\
Input&ALL&&&ALL&&&&&&\\
Output&C3&&&&&C3&&&&\\
Enquiry&&&ALL&&&&&&&\\
File&C3&ALL&ALL, C3&C3&&C3&&&&\\
Interface&C0, C3, C5&&&&&&&&&\\
Added&&&ALL&ALL, C3&&&&&&\\
Changed&C0, C3, C7&&&&&&ALL&C3&&\\
Deleted&C0, C2, C3, C4, C5, C7&&&&&&&&&\\
PDR\_AFP&ALL&&&&&C3&&&&\\
PDR\_UFP&ALL&&C3&&&&&&&\\
NPDR\_AFP&ALL&&&&&&C3&&&\\
NPDU\_UFP&&&&&&C3&&&&\\
Resource&C0, C2, C4, C5&&&&&&&&&\\
Dev.Type&C0, C1, C2, C3, C4, C5, C6, C7&&&&&&&&&\\
Duration&ALL&ALL, C3&&&&&&&&
\end{tabular}}
\end{center}
\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. similiar densities). 
%The result is a tree of quadrants whose leaves are clusters.
%
%{\IT} generates the quadrants by finding (1)~the dimension of greatst 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'' heurestic finds the
%the dimension of greatest  variablility 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}
%%includegraphics[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} plit 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 recusively 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 seperate 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 indiciated 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 calcualte Bayes liklihoods 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{Related Work}


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

Clutering 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 rediced
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 acqusition 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}
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 similiar 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 fugure. 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 evaulation 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 contenxts. 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, cirticality, 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 similair 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 intuiative
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}





\section*{Acknowledgment}


The authors would like to thank...
more thanks here


%\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}

\section{Information Needs}
This section samples the space of information needs
of different communities.
First, we
present a use case for {\IT} from the perspective of the Surgeon-General
tracking disease patterns across the country.
Next,
we review a recent analysis of information needs from a recent survey of 100+ programmers at
Microsoft. 
A case will be made that this concept of {\em information needs}
is common to a variety of domains: specifically, we will
show that
there are many similarities
between the information needs of the
Surgeon-General, and of the Microsoft software developers.

\subsection{Use Case}
Every morning, the Surgeon General checks for new disase patterns.
Waving at the display wall of her office, she orders
``show infectious cases presenting to ERs''.
Dots appeared on a map of the country. ``Show
percent admissions to main hospitals ... benchmark against
same from last year''.
Concerned, the Surgeon General leant forward to study the map which
now shows an 
increase in admission rates. Needing
to explain this, she displays other properties saying ``show regional
median unemployment times..  show temperature min .. show temperature
max ...''.

After a while, the  map is chocked with too many
symbols. ``Fold'' she orders, and the geographical map disappears
as hospitals on different sides of the country marched
towards their nearest similar institution.
 ``Cluster'', she orders, and
 similar hospitals 
are grouped together into sectors. She then orders
``overlay with  percent admissions to hospitals'' which highlights 
the hospitals where most the ER patients with infections were not
discharged home.

She taps twice in the air to
 highlight two clusters with highest and lowest
discharge rates. ``Constrast'' she commands, so {\IT} searchers for
rules (conjunctions of hospital properties)
that selects for one cluster while avoiding the other. The
pattern is now clear.

Waving at her ear, she says ``Utah, Health''.
A few seconds later, she is sharing her displays with Salt Lake City.
Utah agrees that  their unseasonal rains has lead to spore
counts generating severe URTIs in infants.   They agree to issue
an advisory about updating air conditioner filters.

``How do we monitor this?'' asks Utah. The Surgeon General draws a line in the air
between the highest and lowest clusters. Sensing her moves, a line
appears on her display (copied to Utah) connecting regions of lowest
and highest infection rates.
Twirling her fingers
here, here, and here she defines three goal points and marks them with
a date.  They agree to meet on those dates to see if the at-risk
hospitals are
moving towards regions of lower infection.

\subsubsection{Analysis of Use Case}
The technology described above divides into 1) motion-aware controllers;
2) data warehousing (that {\em collects} and {\em stores} data); and
3) business intelligence operators
(that {\em extract} knowledge from the warehouse). 
Motion-aware controllers are now
available from commercial vendors (e.g. Microsoft Kinect\textsuperscript{\textregistered}) 
and data warehousing
is a well-studied problem~\cite{sen11}. Hence, in this paper, we  focus just
on 
the business intelligence.
 
\subsection{Information Needs at Microsoft}
{\IT} adapts $kd$-trees~\cite{bentley90} to
recusively divides high-dimensional data according 
the two dimensions of greatest variability seen at every level of the clustering
(so it may be considered a $k(d=2)$-tree algorithm).
These two dimensions are found in linear time using FASTMAP~\cite{Faloutsos1995}.

Leaf clusters are combined using grid-clustering 
to combine related neighboring regions. In $log_4(N)$ time, new test instances
can be mapped down the $k(d=2)$ tree to their relevant cluster.
Each cluster maintains histograms describing the distribution of data seen
in that cluster.  
Each cluster can be scored in numerous ways such as (a) the median of some
dependent variable in that cluster or (b) the performance bias and variance
of a classifer applied to that cluster.
The delta between histograms reveals ranges
that most distinguish 
two sets of clusters, which might be called $asIs$ and $toBe$.
Management actions can be computed by restricting those deltas to just the features
that management can control.
If those contollable deltas are computed using a $toBe$ with better scores than the current
$asIs$, then 
those deltas are now a \underline{plan} of how to move to a better place. Conversely,
if $toBe$ has a worse score, then the those deltas are  \underline{alerts} which, if they occur,
should be notified to management.
\section{Motivating Example}
\section{Related Work}
There is a long history of attempts to clarify and extend prior
information processing research into some simpler and unifed new framework.
For example, knowledge engineering research into rule-based programming


learners  
This document defines a unified toolkit to support the Busmann. In
this toolkit, we make decisions based on our experience with
building low-order polynomial time instance-based reasoning tools. We
offer this implementation as a baseline business intelligence
toolkit. At the very least, it is the tool that generates lower-bound
performance values (and, hopefully, other tools will do better). At
the very most, it is the tool that will be a framework that glues
together a community of researchers exploring business intelligence.

Notes:
\bi
\item[1.] Alerts are the monitors (learned in modeling) being triggered.
\item[2.] Summarization is range ranking (e.g. BORE the ranges, show a plot).
Modeling is exploring the effects of combinations of ranges, biased by the range rankings,
where the targets are neighboring clusters with higher or lower scores.
Simulation is also exploring the effects of combinations of ranges, but this
time, the user specifies those ranges.
\item[3.] Overlays are showing the clusters, colored by their mean performance score.
Goals are overlays where the performance score is the mean of the cluster - goal values.
Benchmarks are overlays where the performance score is the mean of the cluster - industrial standards.
\ei
\newpage
\section{to do}
\section{Origins}
{\IT} began as an optimzer to a rule-based learner. Everytime that learner proposed a rule, it was
assessed by passing it over a database of labelled test cases, then counting how often the rule's conclusions
were the same as   the labels of the instances selected by that rule.
To optimize that process, the database of examples was clustered and an index tree was built on-top of the clusters
so that a rule can find the nearest subset of test cases  $O(log_2(N))$ time. Then, it was realized that if
the same indexing scheme was applied to the training data, that many of the queries used to form the rules
could also be quickly executed. After a time, the rule learner faded away as more of its functionality was moved
into the tree-of-clusters abstract data type.

This approach is only interesting if the tree of clusters can be quickly generated. Naive
approaches to generating this tree take time $O(N^2)$ and have issues with high dimensionality data.
For example, 
Agglomerative Clustering (GAC)~\cite{Beeferman2000,Guha1998,Eisen}. 
GAC executes
bottom-up by grouping
together at a higher level $(i+1)$ the closest pairs of instances found at level
$i$.  The  resulting tree has $N$ instances at each level $i$ so building level $i+1$ 
requires $O(N^2)$ distance
calculations.

A faster approach may be to use Bentley's kd-tree algorithm~\cite{bentley90}. The algorithm
cycles through the $k$-dimensions of the data, splitting first on $k_1$, then $k_2$, etc, cycling back
to $k_1$ (unless some stopping criteria is satisfied). At each level,  the data is sorted according to
$k_i$ and a split created at the median point. This approach is faster than GAC since
two new splits are created in $O(N{\cdot}log(N))$ time
from the $N$ instances found in the current split. The algorithm can be further optimized via heuristics
that randomly select some subset of the $x$ points in the current split.

$kd$-trees can be further optimized by reducing the number of dimensions.
In other work, we have found that such {\em dimensionality reduction} is  a useful pre-processor for learning.
Real world data is often 
``noisey''  (containing spurious signals not associated with target values), or may contain irrelevant or
correlated dimensions. 
Hence, a standard result is that $k$ dimensions can be replaced wth $k' \ll k$, without lose of performance in
the learner~\cite{kohavi98,hall03,chen05}. A commonly used dimensionality reduction  mechanism is to replace
the original $k$ dimensions with an sorted list of orthogonal $component$. Each $component_i$ is a linear
combination of $k$, that accounts for as much of the variability of the data as possible (and the orthogonal
$component_{i+1}$ tries to account for the remaining variance).  The traditional way to find these components
is principled components analysis (PCA) but Du \& Fowler~\cite{Du2008} report that the matrix manipultions required for PCA
takes time $O(N{\cdot}k^2)$ 
for
data with $k$ columns and $N$ rows. Whiile this is less that then $O(N^2)$ cost of GAC, we still wish to avoid
polynomical time inference in the core of algorithm. 

Fasloutsos \& Lin~\cite{Faloutsos1995} offer a linear-time
heuristic for generating components. Given $N$ instances,
their ``FASTMAP'' heurestic sets the
the dimension of greatest  variablility 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 PCA's $component_1$. 
An orthogonal 
$component_{2}$ 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 of the $N$ instances has a distance $a$ to the 
origin (instance $X$) and distance $b$ to most remote point (instance $Y$).
\item By the cosine rule, each instance can be mapped into a 2-D space as follows: 
\begin{equation}\label{eq:ab}
\begin{array}{ccl}
x&=&(b^2 - c^2 -a^2)/(-2c)\\
y&=&\sqrt{a^2 -x^2}
\end{array}
\end{equation}
\ei
Note that this process maps the $N$ instances in $k$ dimensions to the two-dimensions $(x,y)$
in time $O(2N)$.
Since such a two dimensional space can be readily visualized, we experimented with this approach.
{\IT}'s modification to $kd$-trees is,  at each recursive step:
\be
\item 
Use the FASTMAP heuristic to find two distant points $X$ and $Y$ .
\item Using $X$ and $Y$ and \eq{ab}, map the data into $k=2$ dimensions.
\item On each dimension, find $\hat{x},\hat{y}$,  the distance of the median points to the origin.
We say that $\hat{x}$ and $\hat{y}$ divides the data west-vs-east
and south-vs-north, respectively. 
\item Split the data into one of four quadrants $(north,east)$ or 
$(north,west)$ or $(south,east)$ or $(south,west)$.
\item
Recurses into each quadrant.
\item
Stop when  a quadrant contains
less that $\sqrt{N}$ of the original
$N$ instances in the entire training set.
\ee
As a side-effect of the above,
{\IT} builds a tree of quadrants (and the top-most quadrant contains  the entire data set). Each node
of this tree is defined by \[(X,Y,c,\hat{x},\hat{y}\] 
A test instance $T$ can find its relevant sub-quadrant by computing $a=dist(T,X)$, $b=dist(T,Y)$,
$x=(b^2 - c^2 -a^2)/(-2c)$, and $y=\sqrt{a^2-x^2}$. The correct sub-quadrant could be found from
the following labels:
\bi
\item
if $y > \hat{y}$, then ``north'', else ``south'';
\item
if $x >\hat{x}$ then ``east'', else ``west''.
\ei
uhe instance then recurses to one of the quadrants (e.g. $(north,east)$).
Since
this process divides the data into four equal regions at each level of the tree, test instances
find their relevant data in time $log_4(N)$.

Once the data is projected into $k=2$ dimensions, we can visualize the results. Since we are using the most
remote point to define our dimensions, the presence of a single outlier can lead to very uneven displays of the
data. Hence, in our displays, we  set $x=log(x)$ and $y=log(y)$.

rule is This generates an index tree of clusters

The data is then split
into four (one each s
 
That is, ``optimizing'' $kd$-trees in this way would incur a computational cost
equivalent to GAC trees.

process. Real-world data is often ``noisey'' (contains signals not associated with  
The variability in the output of a model is some product of the variability in the $k$ dimensions
of the training data. Miller shows that reducing $k$

eften, $k$ dimensions
can be replaced with $k' \ll k$ 

used to split the data at the median a split is created
at the median point where (according  the k-dimensions
of the data set,  which, for a data sets
with $k$ dimensions, takes average time that is linear for 

For example kd-trees~\cite{bentley90}


prediction: probablity mass ina  cluster

minitoring: 2d constrast sets  from now to worse

planning: 2d constrast set from now to better

explanation: nd contrast sets 

unsupervised learning: split on median

k-th enarest neighbor: unsupervised, then membersho

contrast sets: 
	give a path root to node with sub-trees c1,c2
    give ignored clusters on path c3,c4,c5...
    find the stuff that is in c1 that is not in c2,c3,c4,c5,...
    i.e. fss

ripple down rules: see contrast sets

classification: walk the cluster tree then runa  classifer at the leaves

association rules:
 	high probabilty entriesl in local region that are not high prob elswhere. aka. contrast sets

feature sunset selection 
	difference in split points of two clusters. and if we keep some simple stats on each cluster, can rank those contrast sets

instance selection
	prune sub-trees with ambigous results (e.g. large variance)
	prune sub-trees with clear results (low variance)

dimensionality reduction
	comes for free

\subsection{meta-stuff}
anomaly detection
	outside the certification envelope

active learning
	find two clusters you want to prune and ask around the middle (i.e around their daddy)

stability: repeat above analysis using 20*66% of data

bagging: do stability and report mean predictions

integration: do for N and sum over the results

	
\section{Definitions}
\subsection{Distance}

A set of instances $I$ consists of independent and dependent attributes. For
example, the ``LOC'' of a system might be an independent attribute
while ``number of bugs'' or ``effort hours" might be dependent.

We assume that discrete classes can be mapped to some numeric utility
$U$ and that numeric classes have some direction of $better$ and
$worst$.

We also assume some distance function $dist$ defined for independent
attributes that satisfies the standard distance axioms; i.e.  for
instances $(x,y,z) \in I$:

\bi
\item
$dist(x,x)=0$
\item
$dist(x,y) = dist(y,x)$
\item
$dist(x,z) \le dist(x,y) + dist(y,z)$.
\ei
Also, we assume that $dist$ is defined between two instances
with values for some subset of their independent attributes.

\subsection{Clusters}

At time $T_i$, instances $I_j$ belong to clusters $C_k,C_l,...$ where
probability at probability $0 \le in(T_i,I_j,C_k) \le 1$.

Each cluster holds a set $D$ containing the intra-cluster distances
between all pairs $(x,y) \in C_i, x > y$, sorted in ascending order.
If the cardinality of $D$ is $d$, then the cumulative probability
distribution function $pdf$ is computed by normalizing the first $i$
elements of $D$ according to the sum of all sorted distances in $D$:
\[pdf_i =  \frac{\sum_i D_i}{\sum_d D_d}\]
(This $pdf$ function will be used to detect anomalies, see below.)

\subsection{Predictions}
The $prediction$ of the dependent attributes is computed from a $summary$
of the $k$-th $nearest$ neighbors.

This definition is independent of the clustering method. For example:
\bi
\item
Some clustering such as EM algorithms allows for instances to exist in
multiple clusters at one time.
\item
On the other hand, clustering algorithms such as k-means, demand that
an instance can only exist in one cluster at one time, i.e.
\[in(T_i,I_j,C_x)=1
\wedge \forall x \not= y, in(T_i,I_j,C_y)=0\]
\item
Within these definitions, an implementation is free to make its own
decisions regarding how to $summarize$ the neighbors, how many
neighbors to include in that summary (i.e. what value to use for $k$)
and how to compute $nearest$.  \ei Optionally, it may be a useful
optimization to pre-compute and cache the $summary$ values for each
cluster before processing test instances.

\section{Some Details}
Our current implementation uses a top-down recursive partitioning of
the instance space, followed by a clustering together of neighboring
sub-trees with similar densities of instances.  In this approach: \bi
\item
Two instances are $near$ if they exist in the same cluster.
\item
Each cluster has its own $summary$ being the expected value of the
dependent variables in that cluster (which is the median for number
dependent variables and the most frequent value for discrete dependent
variables).
\ei 
This approach results in a binary tree that can map a
new test instance to its near neighbors in time logarithmic on the
number of instances. 

The root of the binary tree contains all instances. Each leaf represents a cluster containing a subset of the instance space. Intra-cluster distances computed amongst clusters allow us to compare metrics applied to cluster $C_i$ with neighbors $C_j, C_k...$.

Something about linear-time dimensionality reduction allowing us to graphically represent clusters, summarizing performance with respect to metrics applied to dependent variables amongst instances within a cluster.  Or is this too specific?

Doodle?

Something about being able to ``Drill Down'' to the instance level.

\section{Graphics Placeholder}
\newpage
\begin{figure}
\center{\includegraphics[width=200pt]
{includes/neighborhood_effort_grayscale_trimmed_small.png}}
\caption{\label{fig:neighborhood} 
Instances are mapped into a two-dimensional space and are then 
clustered through a recursive, equal frequency partitioning of the 
instance space.}
\end{figure}

\begin{figure}
\center{\includegraphics[width=200pt]
{includes/neighborhood_effort_grayscale_trimmed_small_scores.png}}
\caption{\label{fig:neighborhood2}
Same thing with a score scale.}
\end{figure}

\begin{figure}
\center{\includegraphics[width=200pt]
{includes/zoom3_you_are_here_grayscale_trimmed_small.png}}
\caption{\label{fig:neighborhood3}
Close view of clusters. You are here is the larger instance.}
\end{figure}
\pagebreak
\section{Implementing the Busmann9}
\subsection{Exploration}
\subsubsection{Trends}

We say that the $trend$ for of an instance is ordered set of pairs
$((T_i,C_k), ...)$ denoting when an instance was in some cluster at
probability $in>0$.

\subsubsection{Alerts}

We raise an alert on an  instance if either:
\bi
\item Its {\em dependent variables} values are significantly different to
the $summary$ value of the cluster containing them.
\item Or if the {\em independent variables} values are ``too
far away'' from its closest neighbor.
Our current implementation defines ``too far away'' as
follows. If the distance of an instance to its nearest neighbor in a cluster
is $x$, then we find the position of $x$ in $pdf$ using 
\[i= argmin_i \left(D_{i+1} > x\right)\] 
Then, 
the instance is anomalous if   $rand() > \frac{i}{|D|}$ (where $0 \le rand() \le 1$).
\ei

\subsubsection{Forecasting}
If an instance falls into some cluster, then the distribution of
attribute values within a cluster are the forecasts for all instances
in that cluster.

\subsection{Analysis}

\subsubsection{Summarization}
To summarize the key aspects of a cluster, we perform range ranking:
\bi
\item Discretize the numeric dependent variables into X\% $best$ and (100-X)\% $rest$;
\item Discretize the numeric independent variables into $B$ equal frequency
bins;
\item Find the frequency of each bin in each class for best or rest;
\item Find the bins whose frequency is very different in the different classes;
\item Present those as a nomogram.
\ei
\subsubsection{Overlay}
We present a visualization of the clusters, each one colored according
to its utility scores (0 for worst, 8 for best, sliding scale in
between).  We then indicate ``you are here''.

\subsubsection{Goals}
Goals are displayed in the same way as overlays, but this time worst,
best is computed from a user-supplied table of goal values. If a
cluster meets a goal, it scores 4. Otherwise, if it falls below goal,
it scores zero to three.  Otherwise, if it falls above goal, it scores
five to eight.

\subsection{Experimentation}
\subsubsection{Modeling}
In this instance-based framework, a model is the delta between two
clusters (selected by users) computed by ranking bins using BORE,
then testing what happens if all items in cluster one are changed by
the top $i$-th ranked items in the BORE list. This is reported as a
decision ordering diagram (see http://menzies.us/pdf/10keys.pdf).

Note that models can result in:
\bi
\item $Plans$ that we want to perform; (i.e. deltas between worse and better clusters);
\item or $Monitors$ for conditions we want to avoid; i.e. deltas between
better and worse clusters).
\ei
\subsubsection{Benchmarking}
Benchmarks are displayed in the same way as overlays/ goals, but this
time worst, best are computed from a user-supplied table of
established benchmarks.

\subsubsection{Simulation}
Simulations are almost the same as modeling. However, in modeling, the
contrast sets were between clusters. Here, there are a set of proposed
changes (made by the user) and we want to assess the effects of these
changes on the ``you are here''. If the users' changes are ordered
(from ``really want to do'' to ``might do'') then the results of these
``what-if'' queries can be presented as decision ordering diagrams.


 F


At each recursive call, WHERE builds its quadrants using

This continues till some stopping criteria is 
Data mining technology can find patterns in complex data.
Consquently, much current research is applying data mining technology to the new
discipline of business intellgience
(a.k.a. predictive analytics).

After decades of work in this area, we assert that there are significant gaps between
what business users want and what is provided by data miners.
For example:
\bi
\item
Some learners produce verbose and hard to understand output
(e.g. the decision trees of C4.5~\cite{quinlan92}).
Such verboisty can be dramatically reduced using
tree-pruning algorithms~\cite{me00e} that report just the minimal, most influential,
differences between 
classifications~\cite{me03o,me07}.
\item
Users may evaluate the learnt
rules by domain-specific criteria (i.e. not merely accuracy but
other issues relating to local business goals). For such users,  we have built stochastic
learners that biased their internal model selection via domain-specific
predictates~\cite{me10a,milton08}.  
\item
Sometimes users want to rewrite local
business policies using the  learner output. For these uses,
feature subset selection
to reduce the variance in that output~\cite{me10c,me05c,me10d}.
\item
For business client that use learners 
to find better management actions, we used learners in a cylic
manner (where the model learned at round $i$ constrains the simulations studied
in round $i+1$)~\cite{me07f,me09g,me09i}.
\ei
Based on this experience, we are concerned
that 
the future of applying data mining to software engineering
is an endless sequence of hacks and tweaks of existing data miners to accomodate
an endless sequence of new business requirements?
Perhaps it is time to take a more basic look at the information processing
needs of business users.
Rather than 
{\em reacting} to the needs of our current
business users, it might be better to
should  {\em anticipate} those needs.

One place to start would be
to
synthesize past work into a simpler combined framework that was easily extended
to future needs.
Such a framework should:
\be
\item
{\em Unify} many business-level learning functions;
\item
Offer a {\em simple interface} to its users;
\item
Increase {\em trust} in the models generated by the learners;
\item
Enable {\em sharing} of knowledge across communities;
\item
Be based on a some underlying {\em small set of simple} data structures and algorithms;
\item
Simplify the {\em implementation of current methods};
\item
Simplify the {\em creation of new methods};
\item
{\em Scale} to large and complex data sets.
\ee
{\IT}  is a candidate framework that supports the above eight points.
It is an instance-based approach
for
uncovering important business patterns from multi-dimensional data.
{\IT} indexes historical cases using a recursuve
divisive (top-down) clustering  algorithm
and  constrast set learners
report the minimum deltas between clusters.
It scale to very large dimensionality data and
offers a intuitive visualization interface.
Also, {\IT} supports sharing and privacy and discovery tools (compression, noise reduction,
hyper-k anomization, active learning).

Our analysis shows that {\IT}
subsumes a decade  of our research into business-level learning: all the essential
functionality
of~\cite{me00e,me03o,me07,me10a,milton08,me10c,me05c,me10d,me07f,me09g,me09i}
can be coded using {\IT}
(specifically:
clustering, contrast-set learning, classification
can execute in {\IT}, and in linear time). 
At the very least, {\IT} could be used as an
optimization of the working memory of other learning methods
(e.g. instance selection, feature selection,
association rule learning, anomlay detection).
At the very most, it replaces those methods with faster implementations.
 
This paper introduces {\IT} and, using examples from software effort estimation
and defect detection, show the current empirical from tools built in this framework.
Also, we audit {\IT} using a recent survey of information processing needs conducted at 
Microsoft~\cite{busezimmermann11}:
we show that {\IT} offers support across the full space of those information needs.

The rest of this paper is structured as follows.
XXX


\section{Scalability}
If our advice widely applied, the then the hunt for local lessons will become very extensive.
In that case, it is vital that the device used to find localities within a software project
will scale to large data sets. One reason we prefer the algorithms described above is that they
support such scaling.  This is not true for other approaches:
\bi
\item Like WHERE, KD-trees build an index structure over a set of divided instances.
For each attribute in turn, the data is divided on median point of that attribute.
Recursive calls to KD-trees further divide the data on the remaining attributes. 
As the number of attributes grows, 
KD-trees become slow.
WHERE, on the other hand, recursively divides the
data on the two dimensions of greatest variance and so can handle very large attribute sets.
\item
Like WHERE, principle component analysis (or PCA) generates orthogonal dimensions that span the direction
of greatest variance. However, matrix factoring methods like PCA take polynomial time to execute~\cite{Du2008}
while WHERE takes linear time (since it uses the FASTMAP heuristic~\cite{Faloutsos1995}).
\ei

{\em Scalability:}
To assess the scalabilty of this process, we collected the runtimes for the different stages
of {\IT}-1 using data sets where the rows were copied once, twice, four, and eight times.
The results are show in \fig{runtimes}: note the linear growth rates in the total time, as well
as the main sub-routines of the process. 
\begin{figure}[!b]
\begin{center}
\includegraphics[width=3.5in]{all.pdf}
\end{center}
\caption{Runtimes for a PYTHON version of RPC-1,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.
}\label{fig:all}
\end{figure}


{\em Low complexity:} Overall, the complexity for quadtree generation and GRIDCLUS is very low:
\bi
\item
Each recursive call for quadtree generation requires
2N distance calculations to find the distant points that define the 2D plot
of \fig{geo}. At each recursive level of quadtree generation,
this $O(N)$ calculation is repeated four times on 
one-fourth the data seen in the previous level of recursion. Hence, the total time for quadtree
generation is linear on the training data size $N$. 
\item
GRIDCLUS must sort the leaf quadrants, which takes times
$L(C{\cdot}log(L))$, where $L$ is the number of leaf quadrants. Typically, $L$ is some small fraction
of $N$ so, as shown in \fig{all}, it is the fastest sub-routine inside {\IT}. 
\ei
{\em Indexing:}  a side-effect of this process is the creation of the quadtree over a set of clusters.
 This quadtree can be used by
test instances to find their nearest neighboring instances in $O(log_4N)$ (at each level of the quadtree,
select the sub-quadrant by relecting over the distance of the instance to $X,\hat{x},\hat{y}$).

{\em Speed:}
One implementation RPC-1 can complete the above process in 2.5 seconds
for an 800K table
of data (6500 rows, 26 columns) with  $\alpha=20$\footnote{ 
On a OS/X iMac,
with 4GB of RAM. Time excludes load time from disk}\footnote{andrew: what data?}. 
That implementation was written in Steel Bank Common Lisp so faster speeds could result
from coding this in ``C''.


