\documentclass[journal]{IEEEtran}
%\documentclass[9pt,journal,compsoc]{IEEEtran}
\newcommand{\aive}{{\"aive}}

\usepackage{times}
\usepackage{alltt}
\usepackage{graphicx}
\usepackage{url}
\newcommand{\boxplot}[5]{\begin{picture}(100,10)
\put(0,0){\line(0,1){8}}
\put(100,0){\line(0,1){8}}
\put(#1,4){\line(1,0){#2}}
\put(#3,4){\circle*{6}}
\put(#4,4){\line(1,0){#5}}
\put(50,0){\line(0,1){8}}
\end{picture}}


\newenvironment{smallitem}{
   \setlength{\topsep}{0pt}
   \setlength{\partopsep}{0pt}
   \setlength{\parskip}{0pt}
   \begin{itemize}
   \setlength{\leftmargin}{.2in}
   \setlength{\parsep}{0pt}
   \setlength{\parskip}{0pt}
   \setlength{\itemsep}{0pt}}{\end{itemize}}

\newenvironment{smallnums}{
   \setlength{\topsep}{0pt}
   \setlength{\partopsep}{0pt}
   \setlength{\parskip}{0pt}
   \begin{enumerate}
   \setlength{\leftmargin}{.2in}
   \setlength{\parsep}{0pt}
   \setlength{\parskip}{0pt}
   \setlength{\itemsep}{0pt}}{\end{enumerate}}
\usepackage{eso-pic}
\usepackage{color}
\usepackage{type1cm}
\makeatletter
  \AddToShipoutPicture{%
    \setlength{\@tempdimb}{.5\paperwidth}%
    \setlength{\@tempdimc}{.5\paperheight}%
    \setlength{\unitlength}{1pt}%
      \makebox(600,900){\rotatebox{45}{\textcolor[gray]{0.80}{\fontsize{9cm}{9cm}\selectfont{Draft}}}}}
\makeatother

\newcommand{\bi}{\begin{itemize}}
\newcommand{\ei}{\end{itemize}}
\newcommand{\be}{\begin{enumerate}}
\newcommand{\ee}{\end{enumerate}}
\newcommand{\bd}{\begin{description}}
\newcommand{\ed}{\end{description}}
\newcommand{\fig}[1]{Figure~\ref{fig:#1}}
\newcommand{\eq}[1]{Equation~\ref{eq:#1}}
\newcommand{\hyp}[1]{Hypothesis~\ref{hyp:#1}}
\newcommand{\tion}[1]{\S\ref{sec:#1}}

\newcommand{\princa}{\stress{software engineering data is quirky}}
\newcommand{\Princa}{\stress{Software engineering data is quirky}}

\newcommand{\princb}{\stress{try numerous data mining methods on each data set}}
\newcommand{\Princb}{\stress{ry numerous data mining methods on each data set}}

\newcommand{\stress}[1]{\sffamily{#1}}

% IEEE Computer Society needs nocompress option
% requires cite.sty v4.0 or later (November 2003)
\usepackage[nocompress]{cite}
% normal IEEE
 % \usepackage{cite}

% correct bad hyphenation here
\hyphenation{op-tical net-works semi-conduc-tor}

\begin{document}

\title{Learning Methods to Better\\ Explain Runaway Projects}

\author{Tim~Menzies,~\IEEEmembership{Member,~IEEE,}\thanks{
Dr. Menzies is with the Lane Department of Computer Science and Electrical Engineering,
West Viriginia University, USA; \protect\url{tim@menzies.us}.}
        Osamu Mizuno\thanks{Dr. Mizuno is with
the Graduate School of Information Science and Technology, Osaka University; \protect\url{o-mizuno@ist.osaka-u.ac.jp}.}
and Yasunari Takagi\thanks{Prof. Tagagi is with  the Social Systems Business Group, OMRON Corporation, Japan; \protect\url{y-tagkagi@ist.osaku-u.ac.jp}.}\thanks{See \protect\url{http://menzies.us/pdf/07dmrisk.pdf} for an earlier draft of this paper.
Manuscript received Feburary 21, 2007; revised March  11, 2007.}}

\markboth{Journal of ???,~Vol.~6, No.~1, January~2007}%
{Menzies \MakeLowercase{\textit{et al.}}: Open Issues With High Precision
Detectors }

\maketitle


%------------------------------------------------------------------------- 

\section{Introduction}
%
%An analyst in the $21^{st}$ century can access a plethora of data
%mining methods such as those in the WEKA toolkit of \fig{weka}.  Potentially, data mining can discover important
%structures in historical data that can be used to better control
%future projects.  However, before that, the analysts must understand
%how to use the tools.  
%
%Based on years of data mining for
%software engineering (SE) applications~\cite{me00a}\footnote{Please:
%what is your earliest data mining for SE publication}, we assert
%that a small list of data mining  %XXXX 
%principles simplifies both the learning process
%and the external validity of the conclusions  
%This paper reports those principles (in a {\stress special font}).
%
%To be sure,
%skilled data mining analysts use more than the principles described below.
%However, we can report that thee principles have been found useful in a dozen data mining studies on SE data
%over the last five years. The details of those studies are confidential so they cannot be discussed
%here.
%Nevertheless, we assert that these
%principles mitigate
%numerous common data mining errors.
%
%To demonstrate these principles, we use the following public domain case study.
\PARstart{T}{he} identification
and prediction of a runaway software project\footnote{Please: may we include here a concise definition of ``runaway
project''?} is an important problem faced by every software manager.
Such runaway projects are all too
common~\cite{glass98,karolak96}.
For example, in 2001, the Standish group reported that,
53\% of U.S. software projects ran over 189\% of the original
estimate~\cite{standish01}.  

It is vital to detect and avoid problems
in software development as early as possible  since
the longer they remain,
it becomes exponentially more expensive to rework software~\cite{boehm87}.
It is shown below that, at least for the project data shown here, such runaways can be 
detected via a simple questionnair-based approach, followed by some data mining.

The new analysis reported in this paper
improves the {\em explainability} of prior results.
Every teacher knows that generating
succinct explanations often means skipping over
the 
tedious and complex details.  While such explanations can be quickly
communicated, they may omit numerous important
aspects.

As with teaching, so too
 with data mining.
When data mining from noisy or complex
software engineering data sets,
we have foten
found that a tension between {\em
explanation}
and {\em performance}:  
\bi
\item
Increasingly complex methods can improve
performance;
\item 
But make it increasingly difficult to explain how
the conclusions were reached. 
\ei
For example,
in the past, runaway software projects have been characterized using
logistic regression analysis~\cite{mizuno00,takagi05}.  Candidate
risk factors were indentified and it was shown experimentally that
those canidates were useful in predicting runaways.  However, the
approach was not automatic since it relied on a manual selection
of features.  Subsequent work~\cite{abe06} automated the approach
using a N{\aive} Bayes classifier (defined below) but the
resulting model was difficult to explain:
\bi
\item 
Rule learners and decision tree learners can explain their predictions
via high-level logical strutures such as the decision tree shown in
\fig{weka}.
\item
N{\aive} Bayes classifers, on the other hand, do not generate such succinct
generalizations.  This is an issue since what
developers really want to know is what should be done to avoid
runaway status. 
\ei

This study is a counter example to the rule-of-thumb that ``better explanations
means worse performance''.
We report treatments to a 
a very simple  rule learner (PRISM~\cite{cend87}) 
that out-peforms:
\bi
\item
An 
intricate state-of-the-art rule learner (RIPPER~\cite{cohen95r}). 
\item
The previous state-of-the-art in predicting runaway software projects~\cite{abe06}
\ei
\begin{figure}[!b]
\begin{center}
\includegraphics[width=3.5in]{wekabw.pdf}
\end{center}
\caption{The WEKA open source tool~\protect\cite{witten99} contains dozens of learners.}\label{fig:weka}
\end{figure}
Lest we overstate our case, it is important to note
this study
does not  show how to find good explanation {\em and} performance
ststems for all software engineering data mining problems. 
However, this study is an existance proof that 
it {\em may} be possible.  
The methods described in the sequel are a guide
for how an
analysts can check if their data mining problem
can 
optimize for
both explainability {\em and} performance.for

\section{The Explanation Problem }

\PARstart{T}{o} motivate this paper,
we begin with notes on the ``explation vs performance'' issue.
In the 1970s~\cite{simon80},
cognitive pschologists proposed that
novices are slow at performing tasks since they spend too long wondering what to do next.
Experts, on the other hand,
became
experts by learning fast procedures within their private knowledge bases.

In this model experts are fast since the next best action is instantly accessible.
However, once they have ``compiled'' their knowledge into these fast-acting  procedures, experts 
find it hard to articulate their expertise.
That is, experts can {\em perform} well, but
can't {\em explain} how or why they reach their conclusions.
%Various {\em knowledge acqusition} techniques were hence devised to help analysts recreate descriptions
%of human expertise.
%motivates this paper~\cite{buch78,kahn85,buch84,bucsmi89,gardner00,sch99}. 

An analagous situation occurs with data miners. All data miners are {\em performance systems};
i.e. they can reach conclusions about a test case. However, only some data miners are {\em explanation
systems} that can offer a succinct high-level description of how they reach their conclusions.
Explanation systems often build a succinct summary of the training data
which they then apply to classifiy the test data. In this way, it is simple to explain the
performance of a learner- it is just following the high-level rules/ decision tree generated
during training.

Not all learners support explanations:
\bi
\item
Clustering alogithms~\cite{queen67}
and nearest neighbor methods~\cite{cover67,bey06}
do not condense their working memory into succinct descriptions.
Rather, inferences on new information is made by a query over all the old information.
\item 
Simulated anneallers~\cite{kirkpatrick83} learn constraints to an input space that results in higher
values in the output space.
There is no generalization or summarization in a simulated annealler such as which subset of the input
space is most important to control.
 \item Nueral networks store their knowledge as weights distributed across
a network. Concepts have no centralized location so it is impossible to inspect, say,
all the information about one idea at one location in  a network~\cite{towell93extracting}.
\item Similarly, N{\aive} Bayes classifiers~\cite{duda76} calculate their conclusions
from the products of frequencies derived from historical examples. 
As we shall see below,  those calculations can be surprisingly arcane, especially for business users
with limited mathematical training.
\ei

The ability to explain a conclusion is a powerful tool for helping users to understand and
accept the results from a data miner.
Despite this, performance systems are not always the best choice.
Sometimes, arcane and complex mathematical tools are required for especially complex domains.
In this domains, the  systems nueral nets, simulated annealers, N{\aive} Bayes classifiers
may be the prefered option.

\subsection{Case Study 1: Defect Prediction}

For example, recently Menzies, Greenwald \& Frank~\cite{me07b}
built predictors for software detectors 
using a N{\aive} Bayes classifier and two explanation systems- the OneR rule learner and the
J4.8 decision tree learner (an example decision tree generated by J4.8 is shown in \fig{weka}).
They were intrested in how different researchers reported different ``best'' defect predictors.
They found that:
\bi
\item
Many static code measures  have similar information content. 
\item
Hence, best predictions come from mathematical like N{\aive} Bayes classifiers
that accumulate the signal from many code measures.
\item On the other hand, decision tree learners and rule learners do not perform as well
since they assume there exist hard and fast boundaries between what is defective and what is not.
\ei

\begin{figure}
{\footnotesize
\begin{tabular}{|rr|r@{~}r@{~}l}\cline{1-2}
          method &  median &  &  & \\\cline{1-2}
 oneR &   -16.7 & -100\% & \boxplot{0}{20}{41}{50}{0}&100\%\\
     j48 &     0.0 & -100\% & \boxplot{0}{42}{50}{61}{38}&100\%\\      
   N{\aive} Bayes &    52.4 & -100\% & \boxplot{0}{50}{76}{91}{8}&100\%\\
\cline{1-2}\end{tabular}
}
\caption{Quartile charts from Menzies, Greenwald \& Frank~\cite{me07b}.
The 
charts
show the differences in performances seen when the different learners were applied
to identical parts of the training and test data.
Performance was measured in terms of {\em recall}; i.e. the percent of the
defective modules found by the learners.
The 
the upper and lower quartiles are  marked with black lines;
the
median is marked with a black dot; and
vertical bars  are added to
mark (i)~the zero point and (ii)~the minimum possible value
and (iii)~the maximum
possible value (in our case, -100\% and 100\%).
}\label{fig:qc}
\end{figure}
The results were quite marked: for the data sets explored by Menzies, Greenwald \& Frank,
N{\aive} Bayes out-peformed the decision and rule learners by a very wide margin (see \fig{quart}). 
The median improvement of N{\aive} Bayes over the other learners  was 52.4\%- which was much
larger than the other learners.


\begin{figure*}
\begin{scriptsize}
\begin{tabular}{rrrrr|rrrrr|rrrrrr|rrr|rrr|l}
\multicolumn{5}{c|}{Requirements}&
\multicolumn{5}{c|}{Estimation}&
\multicolumn{6}{c|}{Planning}&
\multicolumn{3}{c|}{Team Organizations}&
\multicolumn{3}{c|}{Management }
\\\hline
 R1& R2& R3& R4& R5& E1& E2& E3& E4& E5& P1& P2& P3& P4& P5& P6& O1& O2& O3& M1& M2& M3&       class\\\hline
  0&  0&  0&  0&  0&  2&  3&  3&  2&  0&  2&  0&  0&  0&  0&  0&  2&  1&  0&  0&  0&  0& ok\\
  0&  0&  0&  0&  0&  0&  0&  0&  0&  0&  0&  0&  0&  2&  0&  0&  0&  0&  0&  0&  0&  0& ok\\
  0&  0&  0&  0&  3&  0&  0&  2&  3&  0&  0&  0&  0&  0&  2&  0&  0&  0&  0&  0&  0&  0& ok\\
  3&  3&  2&  2&  3&  0&  0&  2&  2&  0&  2&  2&  0&  0&  0&  1&  2&  0&  0&  0&  0&  0& ok\\
  0&  0&  0&  0&  2&  0&  0&  0&  0&  0&  0&  2&  0&  2&  2&  0&  0&  0&  0&  0&  2&  0& ok\\
  0&  3&  2&  0&  0&  2&  2&  2&  0&  2&  0&  2&  0&  0&  0&  0&  0&  0&  0&  0&  0&  2& ok\\
  0&  0&  2&  3&  2&  0&  0&  0&  0&  0&  0&  2&  0&  3&  0&  0&  0&  0&  0&  0&  0&  0& ok\\
  0&  2&  3&  3&  0&  1&  0&  2&  0&  0&  2&  2&  0&  0&  2&  2&  0&  0&  1&  3&  0&  0& ok\\
  0&  2&  0&  2&  3&  0&  0&  0&  0&  0&  2&  2&  0&  2&  2&  0&  0&  0&  0&  0&  0&  2& ok\\
  0&  0&  0&  0&  2&  0&  2&  2&  0&  0&  0&  2&  0&  0&  2&  0&  0&  0&  0&  2&  0&  0& ok\\
  0&  3&  3&  2&  0&  0&  0&  3&  3&  0&  0&  0&  0&  0&  0&  0&  0&  0&  2&  0&  0&  0& ok\\
  0&  2&  2&  2&  0&  0&  2&  0&  0&  0&  0&  2&  0&  2&  0&  0&  0&  0&  0&  0&  0&  2& ok\\
  0&  2&  0&  2&  0&  0&  0&  0&  0&  0&  2&  3&  3&  0&  2&  2&  2&  2&  0&  2&  2&  1& ok\\
  0&  0&  0&  0&  3&  0&  0&  0&  0&  0&  0&  0&  0&  0&  0&  0&  0&  0&  0&  0&  0&  0& ok\\
  0&  2&  2&  2&  2&  0&  2&  2&  0&  0&  0&  0&  0&  0&  0&  0&  3&  2&  0&  3&  0&  0& ok\\
  0&  0&  0&  0&  2&  0&  2&  0&  2&  3&  3&  2&  0&  2&  3&  2&  3&  2&  0&  2&  2&  2& ok\\
  0&  0&  0&  0&  0&  0&  2&  0&  0&  0&  2&  2&  2&  3&  2&  2&  0&  0&  0&  2&  2&  0& ok\\
  0&  0&  0&  0&  1&  0&  0&  0&  0&  0&  0&  2&  2&  0&  0&  0&  0&  0&  0&  0&  0&  0& ok\\
  0&  0&  0&  0&  3&  0&  0&  0&  0&  0&  0&  0&  0&  0&  0&  0&  0&  0&  0&  0&  0&  0& ok\\
  0&  2&  3&  2&  3&  0&  0&  0&  0&  0&  3&  0&  0&  0&  3&  0&  2&  0&  0&  0&  3&  3& ok\\
  0&  2&  2&  0&  0&  0&  0&  0&  0&  0&  0&  0&  0&  0&  0&  0&  0&  0&  0&  0&  0&  0& ok\\
  3&  2&  3&  3&  2&  2&  1&  3&  2&  1&  0&  2&  2&  2&  0&  1&  3&  1&  2&  2&  2&  0& ok\\\hline
  2&  2&  0&  2&  3&  0&  0&  2&  3&  0&  2&  0&  2&  2&  3&  2&  0&  0&  0&  0&  2&  3&    runaway\\
  2&  2&  3&  3&  3&  2&  2&  3&  2&  3&  3&  3&  3&  2&  3&  2&  3&  3&  0&  2&  2&  2&    runaway\\
  3&  2&  0&  0&  3&  0&  0&  0&  0&  0&  3&  0&  0&  3&  3&  0&  0&  0&  0&  0&  0&  0&    runaway\\
  0&  2&  3&  2&  2&  3&  0&  2&  2&  1&  0&  2&  0&  0&  2&  2&  0&  2&  2&  2&  0&  2&    runaway\\
  0&  2&  2&  2&  2&  0&  3&  2&  3&  3&  0&  2&  2&  0&  0&  2&  2&  2&  0&  0&  0&  0&    runaway\\
  2&  3&  3&  2&  2&  0&  0&  3&  3&  2&  3&  0&  3&  0&  2&  3&  2&  0&  2&  0&  2&  2&    runaway\\
  3&  2&  3&  2&  0&  3&  2&  2&  2&  0&  0&  2&  2&  2&  3&  0&  2&  0&  2&  0&  3&  3&    runaway\\
  2&  2&  3&  3&  2&  0&  0&  2&  0&  2&  2&  2&  2&  2&  2&  0&  3&  0&  2&  0&  2&  0&    runaway\\
  0&  0&  0&  0&  0&  0&  0&  0&  0&  0&  3&  3&  3&  3&  3&  3&  3&  3&  0&  0&  3&  3&   runaway\\
  2&  3&  3&  3&  2&  2&  3&  3&  3&  3&  3&  3&  3&  2&  3&  3&  3&  3&  2&  3&  3&  0&    runaway\\\hline
\end{tabular}
\end{scriptsize}
\caption{Data used in this study, 
collected using the methods
described in
\protect\fig{method}.
For an explanation
of the columns, see \protect\fig{define}. 
From~\protect\cite{takagi05}. 
}\label{fig:data}\end{figure*}

\subsection{Case Study 2: Runaway Prediction}

Meanwhile, another team was exploring 
runaway software projects. Takagi, Muzuno, et.al.~\cite{mizuno00,takagi05}
had  collected the information of \fig{data}:

\bi
\item
Questions  covering the various aspects of software development (see \fig{define}) areas were delivered to 
development companies and collected one month later. These
projects are actual development of embedded systems in the industry
and they were performed from 1996 to 1998 (for more detail of the
project data used in our study, see~\cite{mizuno00,takagi05,abe06}).
\item
The questions were 
distributed to the project managers or
the project leaders of various target projects.
The detail and purpose of the questionnaire was explained.
Answers were coded
Strongly agree, Agree, Neither agree nor
disagree, and Disagree are 3, 2, 1, and 0,
respectively.
\item
All of these projects had completed their development.
As a result, some of the  projects could be classified
as 
``runaways''; i.e. projects where the management had felt out of control.
\ei
After analysis, this team generated a N{\aive} Bayes classifier 
that automatically
predicted for runaways~\cite{abe06}.  
It was a landmark result: its performance was very good
(over 80\% classification accuracy). 
However classifier was only a {\em performance system}
and not an {\em explanation system} that 
could offer insights into how to best change
a software project in order to avoid runaways.

\subsection{Does Explanation Always Reduce Performance?}

Combining the above,
the 
following pessimistic
conclusion is possible:
\bi
\item
Software engineering data can be complex, noisy, or confusing.
\item
Such complex data may require complex and arcane learning strategies.
\item
Complex and arcane learning stratgies will be hard to explain, but at least
they may perform well.
\ei
That is, good performance may imply poor 
explanatory power, especially for complex and noisy real world software engineering data sets.

The rest of this paper is a counter argument to such pessimism. We show that at least for
prediciting runaways, certain standard data mining methods result in models with both high 
performance and good explainability. 

\begin{figure}[!t]
\footnotesize
\begin{tabular}{|p{0.96\linewidth}|}\hline
{\bf
Requirements } features 
relate to the understanding and commitment of the requirements
among the project members:
\bi
\item[R1:] Ambiguous requirements;
\item[R2:] Insucient explanation of the requirements;
\item[R3:] Misunderstanding of the requirements;
\item[R4:] Lack of commitment regarding requirements between the customer and the project members;
\item[R5:] Frequent requirement changes;
\ei
{\bf 
Estimation} features  relate
to the technical methods for carrying out
the estimation, and the commitment between project members and
customers:
\bi
\item[E1:]
Insucient awareness of the importance of the estimation;
\item[E2:]
Insucient skills or knowledge of the estimation method;
\item[E3:]
 Insucient estimation for the implicit requirements;
\item[E4:]
Insucient estimation for the technical issues;
\item[E5:]
Lack of stakeholders commitment for estimation.
\ei
{\bf 
Planning} features
relate to
the planning or scheduling activity and the commitment for the
project plan among project members: 
\bi
\item[P1:]
 Lack of management review for the project plan;
\item[P2:]
Lack of assignment of responsibility;
\item[P3:]
Lack of breakdown of the work products;
\item[P4:]
Unspecied project review milestones;
\item[P5:]
Insucient planning of project monitoring and controlling;
\item[P6]:
Lack of project members commitment for the project plan.
\ei
{\bf 
Team organization} features
relate to the stang of the projects, the fundamental skills
and experience and morale of project members:
\bi
\item[O1]:
Lack of skills and experience;
\item[O2]:
Insucient allocation of resources;
\item[O3]:
Low morale.
\ei
{\bf Project management}
factors about management
activities:
\bi
\item[M1:]
  Project manager lack of resource management throughout a
project;
\item[M2:]
Inadequate project monitoring and controlling;
\item[M3:]
Lack of data needed to keep objective track of a project;
\ei\\\hline
\end{tabular}
\caption{Explanation of data used in this study.}\label{fig:define}
\end{figure}



\section{Two Kinds of Learners}

Before studying the runaway data, we need to understand the tools used in that study.

\subsection{N{\aive} Bayes Classifiers}

N{\aive} Bayes classifiers are based on Bayes' Theorem. 
Informally, the
theorem says $next=old*new$ i.e. what we'll believe {\em next} comes
from how {\em new} evidence effects {\em old} beliefs.  More formally:
\begin{equation}\label{eq:nb}
P(H|E)=\frac{P(H)}{P(E)}\prod_iP(E_i|H)
\end{equation}
i.e. given fragments of evidence $E_i$ and a prior probability for
a class $P(H)$, the theorem lets us calculate a  posteriori  probability
$P(H|E)$. 
When building predictors for runaways,
the
posterior probability of each class (``ok'' or ``runaway'')
is calculated, given the attributes
extracted from a 
project  such ``ambiguous requirements''
or ``low morale'' or any other of the features
shown in \fig{define}.
The project is assigned to the possibility
with the highest probability.  This is  straightforward processing
and involves simply estimating the probability of feature measurements
within the historical projects.

Simple frequency counts
are used to estimate the probability of discrete attribute attributes. 
For
numeric attributes it is common practice for N{\aive} Bayes classifiers
to use the gaussian probability
density function~\cite{witten05}:
\begin{equation}\label{eq:normal}
f(x) =
\frac{1}{\sqrt{2\pi}\sigma}e^{-\frac{(x-\mu)^2}{2\sigma^2}}\end{equation} where
$\{\mu,\sigma\}$ are the features's \{mean,standard
deviation\} (respectively)\footnote{   
To be precise, the probability of a
continuous attribute being a particular continuous value $x$ is zero,
but the probability that it lies within a small region, say $x \pm
\epsilon/2$, is $\epsilon \times f(x)$.  Since $\epsilon$ is a
constant that weighs across all possibilities, it cancels out and
needs not to be computed.} 
The means and standard deviations for \fig{data} are shown in \fig{meansd}.
\begin{figure}
\begin{center}
\scriptsize
\begin{tabular}{c|rr|rr}
\multicolumn{1}{c}{}&\multicolumn{2}{c}{P(ok) = 0.68}&\multicolumn{2}{c}{P(runaway) = 0.32}\\\hline
feature&mean&sd&mean&sd\\\hline
r1&0.2727&0.8624&1.35&1.0500\\
r2&0.9545&1.0650&1.65&0.8078\\
r3&0.9545&1.1571&1.95&1.3500\\
r4&0.8864&1.0759&1.65&1.0500\\
r5&1.4091&1.2670&1.90&1.0440\\
e1&0.3182&0.6998&1.00&1.2649\\
e2&0.7273&1.0082&1.00&1.2649\\
e3&0.8182&1.0824&1.65&1.0500\\
e4&0.5455&0.9642&1.65&1.2460\\
e5&0.2727&0.7497&1.40&1.2806\\
p1&0.6818&0.9833&1.80&1.3077\\
p2&0.9545&0.8516&1.50&1.1619\\
p3&0.3409&0.7744&1.80&1.1225\\
p4&0.6818&0.9833&1.35&1.0500\\
p5&0.7500&0.9857&2.25&1.0062\\
p6&0.4545&0.7820&1.70&1.1874\\
o1&0.6818&1.0824&1.65&1.2460\\
o2&0.3636&0.7100&1.30&1.3454\\
o3&0.2273&0.5979&1.00&1.0000\\
m1&0.6136&0.9762&0.60&0.9950\\
m2&0.4773&0.8323&1.50&1.1619\\
m3&0.5455&0.9404&1.50&1.2845
\end{tabular}
\end{center}
\caption{The means and standard deviations found by
 N{\aive} Bayes classifier for \fig{data}.}\label{fig:meansd}
\end{figure}
Note that this figure is
an incomplete characterization of 
\fig{data}. For example, row 1 of \fig{meansd} suggests that $r1$
(``ambiguous requirements'') for ``ok''  is a gaussian distribution
with a mean of 0.27 and a standard deviation of 0.86. A visual
inspection of column one of \fig{data} shows that this is not true:
$r1$ is usually zero except in two cases where it takes the value
of three. 

A common method of handling non-gaussians like \mbox{$P(r1=X | ok)$} is Johns and Langley's {\em kernel estimation}
technique~\cite{john95}. This technique approximates a continuous distribution sampled by
$n$ 
observations
$\{ob_1, ob_2,...,ob_n\}$
as  the sum of multiple  gaussians with means $\{ob_1, ob_2,...,ob_n\}$ and standard deviation
$\sigma=\frac{1}{\sqrt{n}}$. In this approach, to create
a highly skew distribution like $P(r1=X | ok)$,
multiple gaussians would be added together at $r1=0$.  

N{\aive} Bayes classifiers are called ``n\aive'' since they assume
independence of each attribute. While this assumption
 simplifies the implementation  
( frequency
counts are required only for each attribute),
 it is possible
that
correlated events are missed by this ``n\aive'' approach.

Domingos and Pazzani show theoretically
that the independance assumption is a problem in a vanishingly small percent
of cases~\cite{domingos97optimality}. This explains the repeated
empirical result that, on average, N{\aive} Bayes classifiers perform as well
as other seemingly more sophisticated schemes (e.g. see Table~1 in~\cite{domingos97optimality}).

N{\aive} Bayes classifiers
are frustrating tools in the data mining arsenal. 
They exhibit excellent performance, but do not give a clue about the structure of their models.
It is difficult to  explain to a typical business user
how N{\aive} Bayes classifier makes its conclusions:
\bi
\item
Many business users are not trained mathematicans. Hence,
they may find
\eq{nb}
and \eq{normal} confusing.
\item
Presenting the internal statistics (e.g. \fig{meansd}) is uninformative, at least for
the business users we have worked with.
\item
The problem is compounded if the data is non-gaussian (like \fig{data}) since this requires
explaining kernel estimation. 
\item
Worse, 
a standard N{\aive} Bayes classifier (with our without kernel estimation)
can not answer business-level questions such as 
``what minimal changes should be make to most decrease the odds of
runaway projects?''. 
\ei
\subsection{Rule Learners}

Many researchers have explored other kinds of learners that more directly
support high-level succinct explanations of a data set.
\fig{weka} shows the output of another kind of {\em decision tree
learner}  that generates symbolic descriptions of each target class.
That decision tree was generated using a JAVA port~\cite{witten05}
of Quinlan's C4.5 algorithm~\cite{quinlan92,quinlan86}.

Decision and regression tree learners such as C4.5
or CART~\cite{breiman84}
execute in local top-down
search, with no memory between different branches.  Hence, the same concept
can be needlessly repeated many times within the tree.
Consequently, such trees can be  cumbersome, needlessly large, and
difficult to understand. 

{\em Rule learners} like PRISM~\cite{cend87} and RIPPER~\cite{cohen95r} are alternatives to decision tree learners
that can return smaller, easier to understand, symbolic representations of the patterns in a data set. 
PRISM is a {\em covering} alogrithm that runs over the data in multiple passes. As
shown in the pseudo-code of \fig{prism},
PRISM learns one rule at each pass for the {\em majority class}
(e.g. in \fig{data}, at pass 1, the majority class is $ok$). 
The learned rule is a \mbox{$condition \longrightarrow conclusion$} pair of  the form:
\[
\underbrace{Feature_1 = Val_1 \wedge Feature_2 = Value_2 \wedge \ldots }_{condition} \longrightarrow 
\underbrace{Class}_{conclusion}\]
All the examples that satisfy the condition
are then marked as {\em covered} and removed from
the data set. PRISM then recurses on the remaining data. 
\begin{figure}
\footnotesize
\begin{center}
\begin{tabular}{|p{0.95\linewidth}|}\hline
\be
\item
Find the majoirty class $C$
\item
Create a $R$ with an empty condition that predicts for class $C$.
\item
 Until $R$ is perfect (or there are no more feautres) do
\be
\item
        For each feature $F$ not mentioned in $R$
\bi
\item For  each  value $v\in F$,
              consider adding $F = v$ to the condition of $R$
\ei
\item
              Select $F$ and $v$ to maximize $\frac{p}{t}$ where
$t$ is total number of examples of class $C$ and $p$ is the number
of exmaples of class $C$ selected by \mbox{$F=v$}.
               Break ties by choosing the condition with the largest $p$.
\item
       Add $F = v$ to $R$
\ee
\item Print $R$
\item
    Remove the examples covered by $R$.
\item
If there are examples left, loop back to (1)
\ee\\\hline
\end{tabular}
\end{center}
\caption{PRISM pseudo-code.}\label{fig:prism}
\end{figure}
The output of PRISM is an ordered {\em decision list} of rules where $rule_j$ is only tested if
all conditions in $rule_{i<j}$ fail. 
PRISM returns the conclusion of the first rule with a satisfied
condition.

PRISM suffers from the {\em overfitting problem}. In overfitting,
a learner 
fixates on spurious signals that do not predict for the target class. 
PRISM's overfitting arises from 
part 3.a of \fig{prism} where  the algorithm loops through all features.
If some feature is poorly measured, it might be noisy (contains spurious signals).
Ideally, a rule learner knows how to skip over noisy features.

RIPPER addresses the overfitting problem using two techniques:
\bi
\item  {\em Pruning:}
After building a {\em rule}, RIPPER performs a back-select to see what parts of a {\em condition}
can be deleted, without degrading the performance of the rule.
Similarly,
after building a {\em set of rules}, RIPPER performs a back-select to see what {\em rules}
can be deleted, without degrading the performance of the rule set.
These back-selects remove features/rules that add little to the overall performance.
\item {\em Description length:}
The learned rules are built while minimizing  their {\em description length}.
This is an information theoretic measure computed from the size of the learned rules,
as well as its errors. If a rule set is overfitted, the error rate increases,
the description length grows, and RIPPER applies a rule set pruning operator.
\ei
RIPPER also employs a nove
{\em rule set optimzation} algorithm that tries
replacing rules
some straw-man alternatives (i.e. rules grown very quickly).

RIPPER's psuedo-code is too lengthy to be shown here (see~\cite{dietterich97}
for a full description). Despite its complexity, it is one of the fastest
rule learners  known in the literature. 
The generated rules
perform as well
as 
C4.5's decision trees, yet  are much smaller and easier to read~\cite{cohen95r}.

The rest of this paper reports experiments with N{\aive} Bayes, PRISM and RIPPER on \fig{data}



%XXX why not decision tree learners

%\bi
%\item
%Neural nets never generate
%a succinct generalization of their knowledge~\cite{hinton92};
%\item
%The random search of genetic algorithms can produce models that are too
%complex to understand~\cite{witten99};
%\item
%Most decision/regression tree learners such as C4.5~\cite{quinlan86}
%or CART~\cite{breiman84}
%execute in local top-down
%search, with no memory between different branches.  Hence, the same concept
%can be needlessly repeated many times within the tree.
%Consequently, such trees can be  cumbersome, needlessly large, and
%difficult to understand.  \ei

\section{Performance Measures}

\PARstart{O}{ur} results are presented in terms of the following performance measures.
Suppose we have some historical log, like \fig{data} that can comment on the correct classification of
each row.  By comparing the historical log with the output of the larner, we can define several measures
of success.

Let $\{A,B,C,D\}$ denote the
true negatives, 
false negatives, 
false positives, and 
true positives
(respectively) found by a binary detector (binary detectors work on data sets with two classes, like \fig{data}). 
Certain standard measures can be computed from
$A,B,C,D$. 
For example, recall (or $pd$) comments on how much of the target was found.
\begin{equation}
pd=recall=\frac{D}{B+D}
\end{equation}
Precision (or $prec$) comments on how much of the instances that
triggered the detector actually containing the target concept.
\begin{equation}
prec=precision=\frac{D}{D+C}\\
\end{equation}


The $f$-measure is the harmonic mean of precision and
recall. It has the property that if {\em either} precision or recall
is low, then the $f$-measure is decreased. The $f$ measure is useful
for dual assessements that include {\em both} precision and recall.
\begin{equation}
\mbox{{\em f-measure}}=\frac{2*prec*pd}{prec + pd}\\
\end{equation}
Accuracy (or $acc$) comments on how the percentage of the true
positiives ($D$) an true negatives ($A$) were found by the detector.
\[acc=accuracy=\frac{A+D}{A+B+C+D}\]

All these measures fall in the range $0\le \{pd,prec,f,acc\} \le 1$. Also,
the {\em larger} these values, the better the model.

\fig{rx} shows these measures taken from 13 {\em treatments} of \fig{data}.
Each {\em treatment} is some combination of a data filter,
a learner, and a assessment method. The details of those treatments are explained below. For
now, the important features of \fig{data} are as follows.

\bi
\item
The results from treatments $b,c,..,m$ are
average values across
10-way
{\em cross validation} studies.   In a cross-validation
experiment, the available date is divided into $N$ buckets.
For each bucket in a $N=10$-way cross-evaluation, a model is
learned on the nine of the buckets, then tested on the remaining
bucket.  
\item
Note how, in \fig{rx}, precision does not predict for recall and vice versa
Treatment $f$, for example, has a high precision but the lowest recall,
Therefore it is important to define a rule that assesses
the learned theory by a combination of precision and recall.
\item
In this case study, the last treatment $m$ had the highest f-measure.
\item
Accuracy is widely used as the main performance measure of classifiers. As
However, as shown in \fig{rx}, {\em accuracy} can be an remarkably insenstive performance measure. Note how it remains
roughly constant, despite large changes in recall and precision. This result has been seen
in many other data sets~\cite{me03q,me07b}. Hence,  accuracy is depricated by this paper. 
\ei
%\section{start}
%
%The first of these principles is simply this: {\princa}.
%Commercial pressure prevent large scale data collection and dissemination. Hence, in many cases,
%data mining is be conducted on very small data sets; e.g. a few dozen cases, or less.
%Commonly used  assumptions (e.g. the central limit theorem)  may not apply for such small samples.
%Hence, (1)~the data miners that worked best in prior domians may not work best on the current domain and (2)~analysts
%are adivsed to {\princb}.
% In this case study, for example, 
%the best data mining method was found after an exploration of
%30 possibilities (3  learning algorithms with 2 discretization policies on 5 subsets of the data; 3*2*5=30).
%
%
%
\begin{figure}[!t]
\small
\begin{center}
\begin{tabular}{c}
\includegraphics[width=3in]{recall.pdf}\\
\includegraphics[width=3in]{prec.pdf}\\
\includegraphics[width=3in]{f.pdf}\\
\includegraphics[width=3in]{acc.pdf}
\end{tabular}
\end{center}

\begin{center}
\begin{tabular}{l|rllrr}
     &  bins & learner  & \#attributes & \#tests\\\hline
   a &  n/a    &ripper & 22 & 1\\
   b &  n/a    &ripper & 22& 10\\
   c  &  n/a   &   nb & 22& 10\\
   d  &    3  &ripper & 22& 10\\
  e  &    3 & nb    & 22& 10\\
  f   &    3 &prism  & 22& 10\\
  g    &  3 & ripper  & 1  (r1)& 10\\
 h &  3 & ripper & 2  (r1 + p5)& 10\\
  i & 3  & bayes & 1  (r1) & 10\\
  j &  3  &bayes  & 2 (r1 + p5)& 10\\
   k&   3  &prism & 1 (r1) & 10\\
   l&  3    &prism  & 2 (r1 + p6)& 10\\
   m&  3   & prism & 3  (r1 + p6 + o3)&10
\end{tabular}
\end{center}

\caption{Results from this study. The four plots, shown at top, come from the 13
treatments shown at bottom.  }\label{fig:rx}
\end{figure}

\section{Treatments}

This study went through 13 experiments to find the best
predictor for ruanways. This  resulted in the treatments $a,b,c,..,m$ shown in \fig{rx} and discussed
below.


\subsection{Cross-Validation}





Treatment $a$ was a  simple application of RIPPER to \fig{data}. The learned theory
was applied back on the training data used to generate it; i.e. all of \fig{data}.
As shown in \fig{rx}, this produced one of the largest f-measures  
seen in this study.

Treatment $a$ assessed a learned model using the data that generate it.
Such a {\em self-test}
can lead to an over-estimate of the value of
that model.
Cross-validation, on the other hand,
assesses a learned model using data {\em not}
used to generate it.
Such cross-val studies
are the 
preferred evaluation method when the
goal  is to produce predictors intended to  predict future 
events~\cite{witten05}. 

The results from tTreatment $b$'s cross-validation
 shows how badly Treatment $a$ 
overestimated the performance: changing the training data by as little
as 10\% nearly halved the precision and recall. Clearly, the conclusions
from the self-test from this data set are  {\em brittle}; i.e. unduly effected by minor changes
in the training data.

Treatment $c$ illustrates the explanation vs performance trade-off
discussed in the introduction.  As mentioned above, the output from
rule learners can be far easier to explain than the output of
treatment $c$; i.e.  a N{\aive} Bayes classifier (with kernel
estimation) running on data sets with non-Gaussian distributions
like \fig{data}.  So, if optimizing for {\em explainability}, an
analyst might favor  rule learners over Bayes classifiers.
On the other hand, \fig{rx} shows treatment $c$ out-performing treatment $b$, 
especially in terms of recall. So, if optimizing for {\em performance}
an analyst might favor a Bayes classifier over a rule learner. 

Note that treatement $c$ uses the method
favored 
by the previous high water mark
in this research~\cite{abe06}. 
The research challenge of this work is to optimize {\em both} explanability {\em without}
comprimising
performance. This goal is explored in the remaining treatments.

\subsection{Discretization}

Discretization clumps together
mulitple obseverations across a large continious
range into a small number of regions.
Humans often  discretize real world data. For example, parents often share
tips for  ``toddlers''; i.e. humans found between the breaks
of $age=1$ and $age=3$.

Many researchers 
report that discretization improves the performance of a learner
since it gives a learner a smaller space
to reason about, with more examples in each part of the 
space~\cite{dou95,lu06,yang02,FayIra93Multi}.
After Gama and Pinto~\cite{gama06}, we say that
discretization is the process of converting a continuous range into a histogram
with $k$ break points $b_1\ldots b_k$ where $\left(\forall i < j : b_i \le b_j\right)$. 
The histogram divides a continuous range into bins (one for each break)
and many observations from the  range may fall
betweem two break points $b_i$ and $b_{i+1}$
at frequency counts $f_i$.

Simple discretizers
are {\em unsupervised}  
methods that build their histograms without
exploiting information about the target class; e.g. \bi
\item
 {\em equal width}: 
$\left(\forall i,j:
\left(b_i - b_{i-1}\right) = 
\left(b_j - b_{j-1}\right)\right) $;
\item
{\em equal frequency}: 
$\left(\forall i,j: 
\left(f_i = f_j\right)\right)$.
For N\aive Bayes classifiers working on $n$ instances, 
Yang \& Webb~\cite{yang02} advocate equal
frequency with $f_i=f_j=\sqrt{n}$.
\ei

More sophisticated discretizers
are {\em supervised}
methods that build their histograms
using knowledge of the target class.
Specifically,  the continuous range is explored looking for a 
break that is a {\em cliff}; i.e. a point
where the classes frequencies are most different above and
below the cliff.
Once a top-level {\em cliff} is found,
this method usually recurses
into each region above and below the {\em cliff} to find the next
best sub-cliff, sub-sub-cliff, and so on. 

For example, a widely used supervised discretizer is 
Fayyad \& Irani's method~\cite{FayIra93Multi}.
This method assumes
that the best cliff
is the one
that most divides  target classes.  In terms of information theory,
this can be measured using $entrophy$; i.e.  
the number of bits required to encode the class
distribution\footnote{The entropy of 
classes occuring at frequencies 
$p_1, p_2,...$,
is
\mbox{$-p_1\cdot log(p_1) + 
-p_2\cdot log(p_2) +  \ldots$}.}.
If a break divides $n$ numbers into two regions 
of size
$n_1,n_2$,
then the best cliff is the one
that minimizes
the sum of
the entropy below and above
the cliff; i.e. 
$\frac{|n_1|}{|n|}\cdot Ent_1 + \frac{|n_2|}{|n|}\cdot Ent_2$.

Various discretizers were explored for \fig{data}, with disappointing results:
\bi
\item 
Yang \& Webb's rule ($f_i=\sqrt{33}\approx 6$)
was not useful here since our data has less than 6 distinct values per feature.
\item
Fayyad\&Irani's method
reduced most features to a single bin; i.e. it
found no information gain in focusing on   parts of our columns.
\item
Best results were seen with a simple {\em 3bin} equal width scheme \mbox{(i.e. $|b|=3$)} in Treatment $f$
where
PRISM achieved
precisions as high as the RIPPER self-test  results seen in treatment $a$.
However, the same experiment saw
the worst precisions seen to date. 
\item
The same $3bin$ scheme offered little help to RIPPER or N{\aive}  Bayes
(see treatments $d,e$).
\ei
\subsection{Feature Subset Selection}

Since it was the most promising seen to date, $3bin$ was retained
for the rest of our experiments. Other methods were employed to
achieve the benefits of $3bin$ (high precisions) without its
associated costs (low recall).

A
repeated result in the data mining community is
that simpler models with equivalent or higher performance
can be built via {\em feature subset selection}
algorithms that intelligently prune useless features~\cite{hall03}.
Features may be pruned for several reasons: 
\bi
\item
They may be noisy; i.e. contain
spurious signals unrelated to the target class; 
\item
They may be uniformative;
e.g. contain mostly one value, or no repeating values;
\item
They may be correlated to other variables- in which case, they can be pruned
since their signal is also present in other variables.
\ei
\noindent
The reduced feature set has many advantages:
\bi
\item 
Miller has shown that models
generally containing fewer variables
have less variance in their outputs~\cite{miller02}.
\item
The smaller the model, the fewer are the demands on interfaces 
(sensors and actuators) to the
external environment.
Hence, systems designed around 
small models
are easier to use (less to do)
and cheaper to build.
\item
In terms of this article, the most important asepect
of learning from a reduced features set is that it produces
smaller models. Such smaller models are easier to explain (or audit).
\ei

One such feature subset selector is
Kohavi \& Johns' WRAPPER algorithm~\cite{kohavi97}.
Starting with the empty
set, the WRAPPER adds some combinations of
features and asks some target
learner 
to build an effort model using just those
columns.  The WRAPPER then grows the set of
selected variables and checks if a
better model comes from learning over the larger set of variables.

If we applied WRAPPER to our three learners (RIPPER, PRISM, N{\aive} Bayes),
then WRAPPER's search through the
22 features of \fig{data} could require $3\cdot2^{22}=12,582,912$  calls to a learner.
In practice, some heuristic search techniques drastically reduce this search space.
The WRAPPER stops when there are no more variables to
select, or there has been no significant improvement in the learned
model for the last five additions (in which case, those last five
additions are deleted). Technically speaking, this is a hill-climing forward select
search with a ``stale'' parameter set to 5.
For data sets as small as \fig{data}, WRAPPER terminates in a under a minute
(but for large data sets, other feature selectors would be required- see~\cite{hall03}
for a survey).

This study tried 
the WRAPPER since experiments by other researchers
strongly suggest that it is superior to many other variable pruning
methods.  For example, Hall and Holmes~\cite{hall03} compare the
WRAPPER to several other variable pruning methods including principal
component analysis (PCA- a widely used technique).  Feature
selection
methods can be grouped according to: \bi
\item
Whether or not they make special use of the
target variable in the data set such as ``runaway'';
\item
Whether
or not pruning uses the target learner.
\ei
PCA
is unique since it {\em does not} make
special use of the target variable. WRAPPER is also unique, but for
different reasons: unlike other pruning methods, it {\em does} use the
target learner as part of its analysis. Hall and Holmes found that
PCA was one of the worst performing methods (perhaps because it
ignored the target variable) while WRAPPER was the best (since it can
exploit its special knowledge of the target learner).

\fig{wrapper} shows the results of running 10 WRAPPER experiments
on \fig{data} (discretized via 3bin) for our three learners. In each experiment,
10\% of the training data (selected at random) was ignored. 
The figure shows the number of times (out of 10), the WRAPPER selected
each feature. 

The four groups in that figure highlight how often 
features were selected.
\bi
\item Group \#1 shows the features that, on average,
were selected in the majority of the ten runs (6 times or more).
\item
Group \#2 shows the features that were selected between two and five times.
\item
Group \#3 shows the features that were selected only once.
\item
Group \#4 shows the features that were never selected.
\ei


There are only three features in Group \#1
suggesting that many of the  \fig{data}
features could be ignored.
This has implications for the cost of data collection and the 
explaining runaway projects:
\bi
\item Data collection could be constrained to just Group \#1, and perhaps
$p6$ (which PRISM selected eight times). Such a constrained data collection
program would be cheaper to conduct, especially over a large organization.
\item
\fig{rule} shows
a rule predicting runaway projects found by PRISM using just the features recommend by
te WRAPPER ($r1,p6,o3$)  on
3bin discretized data.
The figure shows that just using the top-ranked features of \fig{wrapper}
yields a very succinct, easy to explain model.
\ei
To test the {\em explainability} of \fig{rule},  we conducted a session with eight NASA engineers
managing software verification projects:
\bi
\item
 Psuedocoode for N{\aive} Bayes
(with kernel estiamtion) and PRISM (\fig{prism}) was introduced. PRISM's algorithm
was summarized
this ways: ``each rule covers some examples which are then deleted; the algorithm then repeats
on the remaining data''.
\item
None of the engineers tried to replciate the reasoning behind kernel estimation.
\item
However, within an hour, the engineers were hand-simulating PRISM on \fig{data}. Using a pen 
and ruler, all the rows of \fig{data} that matched rule \#1 (in \fig{rule}) were identified and crossed
off. The rows that matched rule \#2 were then identified and crossed off. The engineers
stopped after simulating PRISM's
acitivities on two or three rules, making comments like
``I see what is going on- the learner is finding
and handling the most obvious next thing.''
\ei

In summary, the simplicity of the PRISM algorithm and the rules of \fig{rule}
allowed them to be explained to one focus group, within one 60 minute session.
\begin{figure}
\scriptsize
\begin{center}
\begin{tabular}{lr|r|r|r|l}
\multicolumn{2}{c}{}&\multicolumn{3}{c}{Learner}\\\cline{3-5}
&feature&	PRISM	&N{\aive} Bayes	&RIPPER& avverage\\\hline	
group \#1&r1&	10&	10&	6&	8.7\\
usually&o3&	7&	&	&	7\\
selected
&p5&	&	8&	4&	6\\\hline
&p6&	8&	1&	&4.5\\
group \#2:&m3&	&	3&	&3\\
sometimes&r2&	&	&2	&2\\
selected&p2&	&	2&1	&1.5\\
&e1&	1&	2&1	&1.3\\
&o2&	1&	2&1	&1.3\\\hline
&e2&	&	&1	&1\\
group \#3:&e3&	&	&1	&1\\
rarely&m2&	1&	&	&1\\
selected&o1&	1&	&	&1\\
&p1&	&	1&1	&1\\
&p3&	&	&1	&1\\
&p4&	&	1&	&1\\
&r3&	1&	&	&1\\\hline
&r4 \\     
group \#4: &r5\\
never&e4\\
selected&e5\\
&m1
\end{tabular}
\end{center}
\caption{Number of times features were selected
in experiments with WRAPPER on three
learners, leaving out 10\% of the data, repeated 10 times.}\label{fig:wrapper}
\end{figure}
\begin{figure}
\footnotesize
\begin{alltt}
1: If                           o3 = 1   then ok
2: If r1 = 0,1 and p6 = 1                then ok
3: If r1 = 3   and p6 = 1,2              then ok
4: If r1 = 0,1 and p6 = 1,2 and o3 = 0   then ok
5: If r1 = 1,2                           then runaway
6: If              p6 = 3                then runaway
7: If r1 = 3   and p6 = 0                then runaway
8: If r1 = 0,1 and p6 = 1,2 and o3 = 2,3 then runaway
9: If r1 = 0,1 and p6 = 1,2 and o3 = 0   then runaway
\end{alltt}
\caption{A rule generated by treatment $m$.}
\label{fig:rule}
\end{figure}

Treatments $g,h,...m$ show the results of 
applying the top-ranked features on discretized data.
For each learner, if the WRAPPER usually selected  $N$ features, then 
that learner was tested in a 10-way cross-validation
using the top ranked feature, the second-top ranked features,
and so on up to using $N$ features.

The best results were obtained in treatment $m$.
That treatment applied PRISM using the three features
usually selected by WRAPPER+PRISM:
$r1,o3,p6$. This resulted in \fig{rule}. A 10-way cross-valdidation
study showed that this rule generation method yields an average precision, recall, and f-measure
across the 10-way of
of 1,0.85, and 0.92 (respectively).
This result is actually much better than it appears.
\bi
\item
To achieve average precisions and recalls of 1 and 0.85  in such a 10-way is something 
of an accomplishment.
In a 10-way cross-validation on the 33 records of \fig{data}, the test set is of size three or
four.
In such a small test set, a single outlier project can have a large and detremential result
on the collected statistics.
\item
As mentioned in the introduction,
runaway software projects have been previously
characterized using
logistic regression analysis~\cite{mizuno00,takagi05}.  The
approach was not automatic since it relied on a manual selection
of features.  Subsequent work~\cite{abe06} automated the approach
using a N{\aive} Bayes classifier but, for the reasons described above, the
resulting model was difficult to explain.
To the best of our knowledge,
this result with PRISM is the first time an explainable, high performing, explanation for runaway
projects has been generated.
\ei

%Neural nets never generate
%a succinct generalization of their knowledge~\cite{hinton92};
%\item
%The random search of genetic algorithms can produce models that are too
%complex to understand~\cite{witten99};
%\item
%Most decision/regression tree learners such as C4.5~\cite{quinlan86}
%or CART~\cite{breiman84}
%execute in local top-down
%search, with no memory between different branches.  Hence, the same concept
%can be needlessly repeated many times within the tree.
%Consequently, such trees can be  cumbersome, needlessly large, and
%difficult to understand.  \ei
\bibliographystyle{IEEEtran}
\bibliography{refs}
\end{document}

%------------------------------------------------------------------------- 

\section{Related Work}

\PARstart{D}{iscretization}

Other problems with prec and accuracy. neg/pos bad

explanation not as an algorithm thing but a user-specific thing.
leake. hayes.
\subsection{KDD Cycle}

\PARstart{T}he specific technical contribution of this paper
is a new high water mark in learning how to explaining runaway projects.
The more general contribution of this paper is an overview
of effective methods for
knowledge
discovery in databases (KDD) in software engineering. 
An analyst in the $21^{st}$ century can access a plethora of data
mining methods such as those in the WEKA toolkit of \fig{weka}.  Potentially, data mining can discover important
structures in historical data that can be used to better control
future projects.  However, before that, the analysts must understand
how to use the tools.  


The KDD process has been characterised by
Fayyad~\cite{fayyad97},
as the cycle of
\fig{kddcycle}. Note that data mining appears in that cycle, along with numerous other tasks:
\bi
\item
data preparation, 
\item
data selection, 
\item
data cleaning, 
\item
incorporating appropriate prior 
knowledge, 
\item
and proper interpretation of the results .
\ei
In this view, data mining is just one step within  KDD; i.e.
the 
application of specific algorithms for extracting patterns from data.
Fayyad cautions that
the 
blind application of data mining methods (sometimes called ``data dredging'' in 
the statistical literature) without the rest of the KDD cycle
can be a dangerous activity 
easily leading to the discovery of meaningless patterns.

\begin{figure*}[!t]
\begin{center}
\includegraphics[width=6in]{kddcycle.pdf}\\
\end{center}
\caption{The KDD (Knowledge Discovery in Databases) cycle, from 
\protect\cite{fayyad97}.}\label{fig:kddcycle}
\end{figure*}

KDD is normally discussed in the context of very large
databases~\cite{provost99survey,hulten02mining}. Yet its processes apply, even to
small data sets like \fig{data}.  For example, this paper uses KDD to find a
model that is more explaniable that prior results, as well as
performing better. That model was found via: \bi \item {\em Data
preperation} to {\em discretize} the columns; \item {\em Data
selection} to {\em prune} irrelevant columns; \item As recommended
by \fig{kddcycle}, we explored \fig{data} via   13 cycles.  In
each cycle, a data mining was called. The results of each cycle was
used to select the activity in the next cycle.  \ei 

It is important
that industrial practioners understand the KDD process.  
In our work with commercial software engineers, we 
see a common misconception-  that all they need to do is
run the data through a learner.
We 
find ourselves repeatedly advising them that running the learners is the least
complex of their tasks. Rather, most of their effort will be devoted
to
the rest of the KDD process; i.e.
pre-processing the data before running the learners,
then
intepreting the results.

On the other hand, it is important that these practioner also
understand that executing the KDD process is not always a complex task.
For example, in this case study, the data preperation and data
selection operators were not particularly complex.



\section{Conclusion}
quirky. supposedly state-of-the-art methods that usually work best may not work best on a particular data sets. e.g. fayyad irani,
ripper

when geenrating explainations, brevity is useful. discretize to reduce range. wrap to remove columns

An important feature of this study is that is it reproducible using 
open source data mining
 toolkits (e.g. the WEKA tool shown in  \fig{weka})
and the data shown in \fig{data}.
Reproducability 
is an important methodological principle in other disciplines since it allows a community to confirm,
refute, or even improve prior results. 
In our view, in the field of software engineering,
there are all too few examples of reproduced, and extended, results\footnote{
Exception: see  the reports of the PROMISE
workshop
\url{http://promisedata.org/repository/papers.html}}. 
This report begain when the second and third authors
published their data~\cite{takagi05} and defined a research challeng: how to
better explain the results of their learning to developers~\cite{abe06}.
The first author found a way to meet that challenge using the
methods described in this paper.


