\documentclass[twocolumn]{article}
\usepackage{tricks}
\usepackage{times}
\usepackage{graphicx}
\newcommand{\IT}{$PRECIOUS$}
\begin{document}
\title{Better Support for Business Intelligence}
\author{Tim Menzies, Andrew Butcher\\Modeling Intelligence Lab\\WVU\date{\today}}
\small
\maketitle
\newpage
\section{About this Document}
\begin{raggedleft}
{\em One Ring to rule them all,\\
One Ring to find them,\\
One Ring to bring them all\\
and in the darkness bind them.}\\
-- J.R.R. Tolkein

\end{raggedleft}


~\\
Business users need to understand complex data collected from their complex environments.
Data miners summarize data and present it in certain specific ways. 
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, while the current generation of data mining tools are useful,
they usually need customization before they can be successfully
applied in some business context.
For example,  business users can find C4.5's decision trees~\cite{quinlan92} to
be to verbose, For those business users,  we have built tree-pruning algorithms~\cite{me00e}
and other learners that generated very tiny rule sets~\cite{me03o,me07}.
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}.  
Sometimes users want to rewrite local
business policies using the  learner output. For these uses,
we have used feature subset selection
to reduce the variance in that output~\cite{me10c,me05c,me10d}.
One last example: when business user want to use learners 
to find better management actions, we found ways to use learners in a cylic
manner (where the model learned at round $i$ constrains the simulations studied
in round $i+1$)~\cite{me07f,me09g,me09i}.

How can we increase
the overlap between what is generated by data miners and what is required by buiness users?
Rather than 
{\em reacting} to the needs of our current
business users, we should  {\em anticipate} their
future 
needs and, hence,  be better prepared to meet those needs.
Rather than constantly hacking and tweaking existing algorithms, it would be preferable
to synthesize past work into a simpler combined framework that was easier to extend
for future business needs.
Ideally, this framework should:
\be
\item
{\em Unify} many business-level learning functions;
\item
Offer a {\em simple interface} to its users;
\item
Increase our {\em trust} in the models generated by the learners;
\item
Enable more {\em sharing} of knowledge across communities;
\item
Be based on a some underlying {\em small set of simple} data structures and algorithms;
\item
Enables the {\em re-creation} of functionality from prior tools;
\item
Simplifies the {\em creation of new tools};
\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.
We find that {\IT}
subsumes a decade  of our research into business-level learning~\cite{me00e,me03o,me07,me10a,milton08,ne10c,me05c,me10d,me07f,me09g,me09i}. Also, it
implements in linear time 
a variety of data mining methods (clustering, contrast-set learning, classification).
At the very least, it is an underlying data structure that could be used
to optimize 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.
It scale to very large dimensionality data and
offers a intuitive visualization interface.
Lastly, it supports sharing and privacy and discovery tools (compression, noise reduction,
hyper-k anomization, active learning).
 
This paper introduces {\IT} and presents its currently available empirical results.
We audit {\IT} using a recent survey of information processing needs conducted at 
Microsoft~\cite{busezimmermann11}
(it will be shown that {\IT} offers support across the full space of those information needs).

The rest of this paper is structured as follows.

One digression before we continue. 
{\IT}  does not and 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).
Rather, we only make the lesser claim in this paper 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. However, if we ever see that managers find a certain kind of query to be often
very productive and insightful, then researchers should explore frameworks for simplifying
that query (in which case, tools like {\IT} might be assessed, along with other tools,
as candidate methods for that simplification).
 
\section{Two Views of {\IT}}
This section offers two overviews of {\IT}: XXX which is explained
in more detail below.

{\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  
In {\em Information Needs for Software Development Analytics}\cite{busezimmermann11}, Buse
and Zimmermann describe surveys of hundreds of Microsoft developers
that document their decision making requirements.  The results of that
survey is a table we call the Busmann9, a three-by-three table of
different kinds of requirements needed for different aspects of
decision making:

\begin{center}
{\small
\begin{tabular}{|c|c|c|c|}
\hline
&past & present & future \\\hline
exploration & trends & alerts$^1$ & forecasting \\
(find)       &        &        & \\\hline
analysis  & summarization$^2$ & overlays$^3$ & goals$^3$ \\
(explain) &               &          & \\\hline
experimentation & modeling$^2$ & benchmarking$^3$ & simulation$^2$ \\
(what-if)       &          &              &
\\\hline
\end{tabular}}
\end{center}

This document defines a unified toolkit to support the Busmann9. 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}


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,...
	l-distance . maintain a global count in root, do l distance in current - sub

ripple down rules: see contrast sets

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

association rules:
	partial match of new case to old cases down the tree
	when subtrees equi-distant, then stop. that selects a region of space containing "it"
    then do contrast sets between that space and all space
	the result are the defining  characteristics of it vs not it.

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)
	return centroids of the remaining space; i.e. the parent nodes

dimensionality reduction
	comes for free

\subsection{meta-stuff}
anomaly detection
	outside the certification envelope
	1d or 2d? , divided into N bins (N^2 bins), frequency counts in each, sorted, cdf-ed,
			prob of item > f . note: most regions will be zero.

incremental
	prob of reorg sub-tree is inverse to anomaly detector

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.

\section{Conclusion}
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.

\bibliographystyle{plain}
\bibliography{bi}
\end{document}
