\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.
  % \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}{$RQC$}
\IEEEoverridecommandlockouts 
\begin{document}
%
\title{{\Large{\bf Business Intelligence using Data Miners for Software Engineering Applications}}}





\author{\IEEEauthorblockN{Tim Menzies, Andrew Butcher}
\IEEEauthorblockA{EE \& CS, WVU\\
 Morgantown, USA\\
\url{tim@menzies.us}\\
\url{ abutcher@afrolegs.com}}
\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}}
\and
\IEEEauthorblockN{Andrian Marcus}
\IEEEauthorblockA{Computer Science,\\
Wayne State University, USA\\
\url{amarcus@wayne.edu}}
\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}
We argue that automated support for
``business intelligence'' means more than   just applying last decade's data mining
tools to this decade's data.
In order to demonstate that,
this paper discusses 
(a) drawbacks with current data mining tools
as well as (b) what functionality is required to implment business intelligence. 
This information is used to assess
a novel 
data mining framework, called RQC, that targetted at supporing business intelligence.
An implementation is described called RQC-1 that
scales linearly on the size of the training set (and hence is suitable for large data sets). 
It also supports an intuiative visualization environment within which
business users can explore their data.
Examples of RQC-1 are described based on software defect and effort data from the PROMISE
repository of SE data. 
\end{abstract}

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


%
\IEEEpeerreviewmaketitle



\section{Introduction}
An ever-present need in business is to understand data collected from 
complex environments.  Hence, research into {\em business intelligence}
tools dates back to the 1950s~\cite{luhn58}.  Various 
support tools have been proosed to support
business intelligence including OLAP~\cite{Chaudhuri97}, decision
support systems~\cite{brookes86}, data warehouses~\cite{kimball08,sen11}
as well as numerous qualitative methods
that focus on (say) gathering and proirtizing the intelligence needs
of the business users~\cite{kimball08}.

Currently, many industrial and research groups are exploring the application
of 
data mining~\cite{witten11} to business intelligence:
\bi
\item
A
query at http://amazon.com on Apr20, 2011, for ``data mining'' and ``business intelligence'' returns 83 books dating back to 2001.
More than half those books ($\frac{44}{83}=53\%$) were published in the last two years.
\item
See also  recent publications on effort/ prediction
defect prediction~\cite{me10a,me09i,lessmann09,chen05,koc11,Menzies2006,me00e,me10c,me05c,me10d}, or 
many other SE tasks~\cite{busezimmermann11,gay10,me07f,me09g}.
\ei
In response to this interest,
several commercial packages such as SAP R/3 and Oracle and Microsoft SQL Sever 2005/2008
have began distributing business intelligence modules that augment their databases
with data mining.
Are those packages commercializing the right technology?
How are we to
assess the value (or otherwise) of those modules? What principles could be applied
to designing the next improvement in those packages?
To answer these questions, we need:
\bi
\item A critique of the current generation of data mining
tools.
\item
A statement of the core tasks of business intelligence.
\ei
From these, we can determing how the current generation of
data mining tools should be extended to handle
(a)~the issues raised in the critique as well as (b)~
the core tasks of business intelligence.

To generate these lists of extensions, this paper draws on
three sources.
Firstly, Buse \& Zimmermann (hereafter, ``Busmann'')
recently conducted a suvery of over 100 software developers and managers
to find nine tasks that support the
queries those developers wish to make on their project data. Using this
survey it is possible to assess data mining frameworks
by how well they cover the nine tasks.

Secondly, 
in a much-cited paper
``Classifier Technology and the Myth of Progress'', Hand warns that the apprent
progress in data mining fails to take into account important aspects of real-world problems.
Based on his critique, we
say that data mining frameworks must support 
three additional tasks.

Thirdly, we reflect over our own
 experience in building 
executable frameworks for data mining (see, for example,
~\cite{nelson11,me10d,Menzies2006}).
That previous work took numerous algorithms from different researchers and ``glued'' them together
using, say, shell scripts.
The resulting frameworks are
complex
to integrate and maintain, and therefore difficult to extend and use for experimentation.
  Also, given the diversity of tools
in such a  framework, it is difficult to reason about the
theoretical complexity of that union of tools.
Finally, that kind of framework tends to focus on what is {\em different} about the data mining
tools rather that what is the {\em same}. It turns out that focusing on those similarities
leads to  
unified data mining
frameworks that  can be designed and applied to business intelligence for software engineering.

This paper  presents proposes ``{\IT}'' as the basis of
a unified data mining framework for business intelligence:
\begin{center}
{\em {\IT} = dimension \underline{R}eduction + \underline{Q}uadtrees + \underline{C}ontrast sets}
\end{center}
In {\IT},
a quadtree-based clustering algorithm builds a tree
by recusiving dividing instances
along the two orthoginal dimensions that account for most of the data variance.
After the tree of quadrants is geneated, {\IT} forms
clusters by combining leaf quadrants with similiar densities.
Test instances can then search down the quadtree to find relevant examples in time
$O(log_4N)$. 
Each cluster is then summarized as a set of distribution histograms.
The deltas between these histograms is then used by
contrast set learners to succinctly report
the similarities and differences
between clusters.  

One way to assess such a framework is 
how well it extends to new data mining tasks.
The nine+three Busmann\&Hand
tasks were not known when {\IT} was first designed. Yet, as shown below, {\IT} can easily 
accomodate those tasks. 

Also, due to the uniformity of {\IT}'s design, we can reason about 
complexity. For example, in {\IT}-1, nearly all the Busmann tasks can execute
in linear time.

Further, using RQC,
business users can explore their data
within visual
representations that display projects in the top two orthogonal dimensions of the quadtree.

Finally, looking beyong just Bussmann\&Hand, we can see how RQC would naturally support other
data mining applications such as active learning. XXX

The contributions of this paper are five-fold:
\be
\item The definition of the {\IT} framework;
\item An audit of {\IT} with respect to Busmann\&Hand;
\item The baseline implementation, {\IT}-1, against which future imporvements in this area can be assessed.
\item Complexity results for {\IT}-1.
\item Comparative performance results for {\IT}-1.
\ee
As to the last point, {\IT}-1 implements such a large range of data mining tasks that,
within the space of one paper, it is not practical
to compare its performance against all approaches proposed by other researchers.
For this reason, this paper focuses on just a handful of possible experiments: specifically
those relating
to scalability and visualizations (and, in future work, we will conduct other experiments).

Also absent in this paper are user trials where we assess how  SE
project managers react and use the framework. Such trials are planned for the near
future (summer of 2011).


The rest of this paper is structured as follows.

\section{Preliminaries}

While RQC is useful automating {\em some} of business intelligence,
we strongly believe that
no automated tool can support {\em all} aspects of business intelligence. 
Business intelligence supports business managers making decisions about their organization.
Tools like RQC-1 are useful 
for decisions based on electronically stored data. However, not all data is stored
electronically and, to reason about that data, intelligence business managers
should walk away from 
automated tools and spend time collecting data via informal
channels.

Also, while this paper describes  {\em one} framework, we make no claim that is
the {\em only} way to
automatically support  business intelligence. 
{\IT}-1 is merely  the first implementation of {\IT} and, as such,
it contains many low-level design decisions that should be questioned in future
reserach. 
In this paper, we will denote all those decisions with lower case greek letters $\alpha, \beta, \gamma,.. $ etc. 
In  future work, we will 
explores other alternatives for
those decisions.

It is the intent of this paper
to
spawns a research sub-field within which
reserachers debate different ways to implement business intelligence frameworks
that support the nine and three tasks required by Busmann\&Hand. 
For that  field, it is useful to have a baseline implementation against which
other approaches can be assessed. {\IT}-1 is a candidate  baseline tool since:
\bi
\item
It
is  fast to run,
\item
It is simple to understand and implement;
\item
As shown below,  it scales well to larger
problems and performs as well as more traditional approaches.
\ei

\section{Background}
\subsection{Busmann's Nine Tasks for Business Intelligence}



In order to analyze current business intelligence needs,
Buse and Zimmermann~\cite{busezimmermann11}
surveyed 110 developers and managers at  Microsoft. Their survey explored many issues such as  ``what questions
are important to difficult to answer?''.
According to that survey, those requirements divide into
the tasks labelled 1,2,3,4,5,6,7,8,9 in \fig{bus}.
\bi
\item[1.] {\bf Trends}:  traces over past data; 
\item[2.] {\bf Alerts}: currently, are we nearing any point of interest? Alerts include
anomaly detection.
\item[3.] {\bf Forecasts}: given our current situation, what is predicted?
\item[4,7.] {\bf Summarize or Modeling}: how to focus on important issues within  a large mass of data? In COMPASS,
{\em summarize}  and {\em modeling} deals with univariate and mutlivariate analysis (respectively).
\item[5.] {\bf Overlays:} display current status over top of the data.
\item[6,8.] {\bf Goals or Benchmarking:} same as overlays, but display the {\em delta} between current status 
and {\em goals} or established {\em benchmarks} in this domain.
\item[9.] {\bf Simulation}: based on the above, conduct what-if queries to decide between decision alternatives
\ei

Note that other researchers have
proposed hierarchy data mining tasks to support business intelligence. For example, at KDD-07,
Usama Fayyad\footnote{See http://goo.gl/NkHxz} 
offers a range of business tasks that data mining should support: resource acquistion, market conversion, maximizes average orders, 
customer retention and loyalty. While that ontology 
was certainly useful for Fayyad's own industrial work,
he offers no empirical basis for those particular business tasks.
We focus our research around Busmann's nine tasks since they
are based,
at least in part, on a documented data collection exercise~\cite{busezimmermann11}.

\begin{figure}[!h]
\begin{center}
{\footnotesize
\begin{tabular}{|c|l|l|l|}
\hline
&past & present & future \\\hline
exploration & 1.trends & 2.alerts & 3.forecasts \\
(find)       &        &        & \\\hline
analysis  & 4.summarize & 5.overlay & 6.goals \\
(explain) &               &          & \\\hline
experiment& 7.model & 8.benchmark& 9.simulate \\
(what-if)       &          &              &
\\\hline
\end{tabular}}
\end{center}
\caption{Nine kinds of information needs; from~\cite{busezimmermann11}.}\label{fig:bus}
\end{figure}


\subsection{Data Mining}
%We define data mining to be {\em agents monitoring and explaining significant
%similarities and differences between groups
%of electronically stored
%data}. We prefer this definition to that of, say, Witten et al.~\cite{witten11}, 
%who define data mining as ``as the automatic or semiautomatic
%process of discovering patterns in data''~\cite[p5]{witten11} since,
%once the patterns are found, they have to be comunnicated (explained) to some audience. Also,
%once discovered, it becomes important to study how those patterns evolve over time. Further, 
%our definition emphaisis that in many applications, combinations of many learning agents
%may colloberative to reach conclusions.

Example data mining technologies include regression,
statistical and pattern recognition algorithms~\cite{duda00},
clustering,
association rule learners~\cite{agrawal92},
contrast set learners~\cite{cai98,me07} and many other approaches including
classification algorithms like
neural nets~\cite{shavlik91},
decision tree learners~\cite{quinlan92}, and Naive Bayes classifiers~\cite{campbell82}.

Of the above, we focus
on contrast set learning since it is useful for reporting the difference between groups.
This is used in in RQC-1,
when users select two clusters and ask the question
``how can we change from this one to that one?''. 
This question can be answered using the WHICH~\cite{me00e,me02f,me07,gay10,me10a} algorithm 
that builds 
contrast set rules over weighted classes to select for the  preferred classes.
WHICH begins by
scoring all classes with some domain-specific utility score, then cacluating
the {\em baseline}
from the weighted sum of the utilities seen in the raw data.
WHICH then
builds contrast sets using a stochastic search that executes
in several 
{\em generations}:
\be
\item At generation 1, all attributes are descritized
and one rule is generated for each attribute range.
\item
The rules are scored by {\em lift};
i.e. the weighted sum of the class utilities
in the instances selected by a rule, divided by the {\em baseline}.
Rules with higher scores are better at selected for the most preferred class(es).
\item
The next generation of rules are built by
stochastically selecting pairs of rules
seen in the current generation (and this selection process is
biased
towards 
rules with higher score). The condition of the combined rule is the conjunction of the
two selected rule conditions.  
\item Goto step 3.
\ee
The algorithm terminates after five generations {\em unless} it discovers a new rule
with a {\em lift}
greater than all those seen so far (in which case, the 
algorithm grants itself 5 more lives). 

Other technologies can find the border that divided preferred from other classes 
(e.g. support vector machines~\cite{burgess98}). We prefer WHICH to, say, SVM since:
it is relatively simple to implement and
fast to execute.
In practice, WHICH usually terminates in 10 generations or less~\cite{me10a}. 

Another reason to prefer WHICH to other approaches is that
this algorithm described border between different classes
in terms of a handful of conjunctions of attributes.
For example,
at 
ASE'00 and ASE'02 we compared contrast set
learning to that of decision tree learners: data sets that generate decision trees
with hundreds of nodes can generate contrast sets rules containing only a few attributes~\cite{me00e,me02f}.

In our experience,
WHICH's succinct human-readable rules are more comprehensible to most business
users than (say) a multi-dimensional complex parametric equation.
WHICH's contrast set rules are  very small since,
when 
we focus on just the contrasts between the most preferred class
and all others, we can avoid learning rules for classes with lower utility scores.
\begin{figure*}
\begin{tabular}{c|cp{4.5in}l}
name & type & notes & setting in RQC-1\\\hline
$\alpha$ & variable & Stopping rule for recursive quadtree generation.& $\alpha=\sqrt{N}$\\
$\beta$ &  function  &  Reduces $D$ dimensions to two. & $\beta=FASTMAP$\\
$\gamma$ &  function  &  Combines neighboring quadtree leaves.& $\gamma=GRIDCLUS$\\
$\delta$ &  variable  &  GRIDCLUS stopping rule: a fraction
                          of $maxDensity$ (instances per quadrant).
                           & $\delta=0.5*maxDensity$\\
\hline\end{tabular}
\caption{Design options within RQC, and the settings for those
options within RQC-1. $N,D$ are the number of instances,attributes
 in the data set (respectively).
}\label{fig:options}
\end{figure*}
\subsection{Hand's Critique of Data Mining}

Hand's critique of the state-of-the-art in data mining focuses on classifiers but,
as Gaylor notes~\cite{gaylor06}, his critique is  also releveant in other areas (e.g. regression).

Hand complains that while the classifier literature {\em seems} to
report substantive progress, it fails in several areas.
Hand's first complaint is that classifiers are typically assessed by some procedure that
assumes that the current training data is representative of future
data.  Hand doubts this assumption, arguing that real world data
often exhibits {\em drifts} in its distributions such that prior
conclusions no longer hold (he presents examples of such drift from
real-world data examples).

Hand's second complaint is that the evaluation criteria for these
classifications is often applied with excessive zeal.  In our own
research~\cite{me10a,me09i} we have seen that changes to the
evaluation criteria can lead to radical changes in what models are
preferred.  When growing a model, some optimization criteria is
applied that may be irreleant to the goal of the learning. With
Milton et al.~\cite{me10a} we have shown that  standard data miners
that strive to optimize internal search criteria (such as minimizing
entropy) perform very badly when assessed according to some business
goal (such as finding the most errors after inspecting the fewest
lines of code).  Other researchers have noted that widely-used
performance measures (such as accuracy~\cite{provost98case}
 or precision~\cite{me07e}) may not be informative with respect to
 the actual
achievements of a learner.  Consequently, we have argued elsewhere
that the performance criteria of a learner should {\em not} be some
trite ``one size fits all'' measure; rather, it should be tuned to
the local business goals~\cite{me09i,me10a}.

Hand's third complaint is that  model-fitting is a sequential process
of elabtorating simple models in order to better represent the
details of the training data.  Hand notes that most of the predictive
accuracy of these algorithms comes from the relatively simple models
seen at the start of that process. That, the continual extension
of classification models reported in the literature may be superflous.
There is much support for Hand's view.  Holte~\cite{holte93}, then
Auer et al.~\cite{Auer95theoryand} show that decision trees of max
depth one or two can perform as well  than decision tree learners
generated to an arbitary depth.  Kohavi reports that, after pruning
irrelevant attributes, a simple table look-up algorithm performs
well as more elaborate decision tree learning~\cite{Kohavi95thepower}.
In  experiments comparing simple learners with more elaborate
learners, Domingos \& Pazzani found that a simple Naive Bayes
performed just as well as more elaborate
learners~\cite{domingos97optimality}.  Further Lessmann et
al.~\cite{lessmann09} compare 15 classifiers for software defect
prediction including simple Naive Bayes and more elaborate classifiers
such as support vector machines and random forests.  That study
found very little difference in the performance of the simple and
elaborate classifiers. 



%A repeated result~\cite{chang74,me10c,kohavi97,hall03} is that given a table of data with $R$ rows
%and $C$ columns, then (a)~{\em instance} and {\em feature} selection algorithms can generate a reduced
%table with  about 10\% of the
%rows and around $\sqrt{C}$ of the columns; and (b)~a classifier learned on this reduced set
%performs as well (or better) as one trained  from the larger table. 

\subsection{Responding to Hand's Critique}

One way to appease Hand might be to {\em augment} current classifier technology with the
various tools for anomaly detection (to detect data set drift) as well as revision tools
for incrementally updating models as new data arrives. 
Also,
the criteria used to grow and assess a model should not be hardwired into the learner; rather,
it should be tuned to local business concerns.
Finally, 
based on Hand's critique and the other results shown above~\cite{holte93,Auer95theoryand,Kohavi95thepower,domingos97optimality,lessmann09}, it is clear that the augmentation should not invlove overly complex modeling
since
much  of the value from a data miner comes from the first few steps in model fitting.


There are many ways to implement the augmentation.
Incremental revision
of learned models has been extensively explored;
e.g.~\cite{Gupta2004,gama06,widmer96learning,Farnstrom00scalabilityfor}.
Anomaly detection is a well studied field both by
ourselves~\cite{me06c,me02n} and others~\cite{Chandola2009a}.  
Feature subset selection~\cite{chen05}
and instance selection~\cite{koc11} can reducing the size
of the hypothesis space and training data, thus simplying the
resulting model.  
In prior work, we have built toolkits that combine these algorithms by
treating them black-boxes,
linked together via (e.g.) shell scripts~\cite{nelson11}.
As said in the introduction, that kind of  combination can be complex
to build and maintain.  For the rest of this paper, we will
assess how well a much simpler tool, based on {\IT}, handles the Busmann\&Hand tasks.

\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.
Schikuta~\cite{Schikuta03} notes that quadtree algorithms like {\IT} can needlessly sub-divide the data
when, for example, neighboring leaf quadrants have similar properties. Hence, {\IT}
requires some operator $\gamma$ to combine 
quadrants. RQC-1 use
 $\gamma = $ Schikuta's GRIDCLUS algorithm:
\be
\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 3 to find  the next cluster or terminate if the first remaining
cluster  has  $sparse$ density.
\ee
%Αα	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}
\begin{center}
\includegraphics[width=3.5in]{ab.png}

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

\end{center}
\caption{Dimensionality reduction and quadtrees in RQC. Each 2-d dots represents 
24 descriptors for a softwre projects. 
Colors 
on the right-hand-side show median intra-cluster development effort (green= lowest effort;
red= highest effort).
}\label{fig:3part}
\end{figure}

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

\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:} 
By showing a manager where they sit within this
display, it is possible to visualize the neighborhood around their current project.
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).
Later in this paper, we will re-express 
this kind of ``what can go wrong'' reasoning using the
WHICH contrast set learner.

{\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''.

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

{\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. 

{\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

The two disadvantages of our approach are $approximation$ and $explanation$.

{\em Approximation:}
Like any heuristic
dimensionality reduction method, the two-dimensional space used in quadtree generation
is only an approximation
to the original data. However studies by 
Fasloutsos \& Lin~\cite{Faloutsos1995}, 
Nelson et al.~\cite{nelson11}, and this paper
 report that inference over this approximate representation of the data can be effective.

{\em Explanation:} The core of this technique is the
\section{Coverage of the Bussman Tasks}

\subsection{Trends}
\subsection{Alerts}
\subsection{Forecasts}
fast classification
\subsection{Overlays}
\subsection{Benchmarks and Goals}
\subsection{Summarization and Modeling}
\subsection{Simulation}
\section{Coverage of the Hand Tasks}
\subsection{Minimal Inference}
\subsection{Anomaly Detection}
\subsection{Repair}

\section{Other Applications}
\subsection{Active Learning}
active learning to reflect over interactive simulation

\section{Related Work}
dimensionality reduction with PCA

other ``theories of everything'': abduction

kd-trees

\section{Discussion}

{\IT}  cannot
support {\em all possible} needs of all possible future business users. Indeed, it would
be naive to think that any tool could do that.
Instead, this paper makes
the lesser claim that, given what we have implemented to date,
and given what we see just over the horizon, {\IT} supports an interesting percent of
that functionality. 

One future direction of this project would be a {\em gap analysis}
to identify areas where {\IT} can be extended as well as areas where tools like {\IT} cannot
and should not be applied. As an example of the latter, 
managers should always be given extensive access to multiple ad hoc query tools that allow them
to use their intelligence to find the patterns that all their current tools 
are missing. 

Note that, if managers ever find a certain kind of query to be often
very productive and insightful, then researchers should explore frameworks for simplifying
that query. In that case,  tools like {\IT} might be assessed, along with other tools,
as candidate methods for that simplification.


\section{Conclusion}
Following n from this paper, we hopethat no one longer believes that business intelligence
is jsut the application of standard data mining technology to the analysis of business data.

We have presented a baseline approach for modeling business
intelligence. It is our hope that this approach will serve as a foundation for
further tools that will empower software development teams.

%
%
%\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, COMPASS 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.


