
%\documentclass[9pt,journal,compsoc]{IEEEtran}
\documentclass[12pt,onecolumn, 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{Explanation vs Performance in Data Mining: \\A Case Study with Predicting Runaway Projects}

\author{Tim~Menzies~\IEEEmembership{Member,~IEEE,},\thanks{
Dr. Menzies is with the Lane Department of Computer Science and Electrical Engineering,
West Virginia University, USA; \protect\url{tim@menzies.us}.}
        Osamu Mizuno~\IEEEmembership{Member,~IEEE},\thanks{Dr. Mizuno is with
the Graduate School of Information Science and Technology, Osaka University; \protect\url{o-mizuno@ist.osaka-u.ac.jp}.}\\
Yasunari Takagi\thanks{Prof. Takagi is with  the Social Systems Business Group, OMRON Corporation, Japan; \protect\url{yasunari@omron.co.jp}.} 
and Tohru Kikuno~\IEEEmembership{Senior Member,~IEEE}\thanks{
Dr. Kikuno is with the Graduate School of Information Science and Technology, Osaka University; \protect\url{kikuno@ist.osaka-u.ac.jp}.}
\thanks{See \protect\url{http://menzies.us/pdf/07runaways.pdf} for an earlier draft of this paper.
Manuscript received April 15, 2007; revised ???  ??, 2007.}}

\markboth{Journal of ???,~Vol.~6, No.~1, XYZ~2007}%
{Menzies \MakeLowercase{\textit{et al.}}: Explanation vs Performance Systems}

\maketitle


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

%
%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 three 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.
\begin{abstract}
Often, the {\em explanatory power} of a learned model must be traded off
against model {\em performance}. In the case of predicting runaway software projects,
we show that the twin goals of high performance {\em and} good explanatory power
are achievable after applying a variety of data mining techniques 
(discretization, feature subset
selection, rule covering algorithms).
This result is a new high water mark in predicting runaway
projects. Measured in terms of precision, this new model is as
good as can be expected for our data. Other 
methods might out-perform our result (e.g. by
generating a smaller, more explainable model) but no other
method could out-perform the precision of our learned model.
\end{abstract}
\section{Introduction}
\begin{raggedleft}
{\em Seek simplicity, and distrust it.\\
-- Alfred North Whitehead}

\end{raggedleft}
\PARstart{E}{very} teacher knows that generating
succinct explanations means skipping over
tedious details.  Such explanations can be quickly
communicated, but can miss the details needed 
to apply that knowledge in a real world setting. 

An analogous 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 offer a high-level description of how the learned model  functions.
%Explanation systems often build a succinct summary of the training data
%which they then apply to classify new test data. One such summary is the decision tree shown
%in \fig{weka}, was learned by the J4.8 data miner.
%It is simple to explain the
%conclusions of such a  data miner- it is just following (e.g.) the high-level rules or tree generated
%during training.
%\begin{figure}[!b]
%\includegraphics[width=\linewidth]{wekabw.pdf}
%\caption{The WEKA open source data mining workbench~\protect\cite{witten99}.
%}\label{fig:weka}
%\end{figure}
\begin{figure*}
\begin{center}
\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}
\end{center}
\caption{Data used in this study, 
collected using the methods.
For an explanation
of the columns features, see \protect\fig{define}. 
From~\protect\cite{takagi05}. 
}\label{fig:data}\end{figure*}


The ability to {\em explain how}  a conclusion was reached is a
very powerful tool for helping users to understand and accept the
conclusions of a data miner.  Despite this, sometimes explanatory
power must be {\em decreased}  in order to {\em increase} the
efficacy of the predictor.  For example, previously Abe, Muzono, Takagi,
et.al.  used a N{\aive} Bayes classifier to generate a predictor
for runaway software projects~\cite{abe06,takagi05,mizuno00}. That model {\em performs}
well but, as shown below, cannot
easily {\em explain}
how it reaches its conclusions.

This paper repairs the
{\em explainability} of that prior result.
Using  an iterative exploration
of data mining techniques (cross-validation,
different rule learners, discretization, feature subset selection),
we found a particular combination of methods
that 
yielded succinct explanations of how to predict for runaway software projects
while out-performing the N{\aive} Bayes classifier. 
In hold-out experiments,
this new model exhibited perfect precision; i.e. precision = 1.0.
Other methods  {\em might} be able to out-perform this new result  (e.g. by finding a more succinct
and explainable model) but no other method could be more precise (since $0{\le}precision{\le}1$).

%An important feature of this study is its
%{\em reproducibility}.
%Reproducibility
%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 begin when the second and third authors
%published their data~\cite{takagi05} and defined a research challenge: how to
%better explain the results of their learning to developers~\cite{abe06}.
%We would strongly encourage software engineering researchers
%to share data, define challenges, and to
%take the time to rework the results of others.

The rest of this paper is structured as follows. First, the software runaway problem is defined
and the explanation problems of prior results are discussed. 
Next, the general problem of explaining a learned model is explored using a range of data miners. 
and examples from the software engineering literatures (in summary,
the best {\em performing} models may be  very poor at {\em explaining}
how those models make their conclusions). A class of data
miners called {\em rule learners} will then be introduced and applied
to our data via various {\em treatments} (some combination of discretizer,
feature selector, and learner). 
The subsequent discussion
will review (a)~related work; (b)~the external validity of these results;
as well as 
(c)~general principles of building
explainable models via data
mining. 

\section{Runaway Software}\label{sec:runaway}
\PARstart{G}{lass} defines a ``runaway software project'' as
``a project that goes out of control primarily because
of the difficulty of building the software needed by the system''~\cite{glass97}.
For Glass ``out of control'' means
``schedule, cost, or functionality that was twice as bad as the original estimates''. 

Many software projects suffer from runaways:
\bi
\item
In 2001, the Standish group reported that
53\% of U.S. software projects ran over 189\% of the original
estimate~\cite{standish01}. This 189\% is not the 200\% required by  Glass' definition,
but it is close enough and large enough to be alarming.  
\item
Figure~\ref{fig:data} shows data from 31 real-world projects, 10 of which
(32\%) 
are classified as ``runaway''.
\ei
\fig{data} was collected by~\cite{mizuno00,takagi05,abe06}
as follows:
\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 industrial software development projects of embedded systems 
in the period 1996 to 1998.
\item
The questions were 
distributed to the project managers or
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 as 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''.
Takagi et.al. took care to ensure that all
developers held a consensus                                                  
view
that some prior project had been a 
runaway. Also, to be classified as a runaway,
the researchers used
other objective measures
such as 
cost and duration.
\ei

Using manual methods, Takagi et.al.~\cite{takagi05} found
four features from \fig{data} ($e3,e5,p3,p5$)
that seemed
promising predictors for runaways. The coefficients of those terms (found via  logistic
regression) were combined as follows:
\begin{equation}\label{eq:runaway}
\small
\begin{array}{r@{~}c@{~}l}
X(e3,e5,p3,p5)&= &-8,834\cdot e3 + 1.577\cdot e5 + 0.964\cdot p3 \\
              &  &+ 1.228 \cdot p3 + 2.222\cdot p5\\
P(runaway|X)& =& \frac{e^X}{1+e^X}
\end{array}
\end{equation}
Unlike prior results~\cite{glass97,jiang02,ropp00},  this model
is {\em operational}; it is possible
to
precisely characterize the strengths and weaknesses of its performance:
\bi
\item
For {\em high} and {\em low} values of $P(runaway|X)$, \eq{runaway} is a perfect predictor for
runaways in \fig{data}. No project with \mbox{$P \le 0.03$} is a ``runaway''
and no project with $P \ge 0.81$ is ``ok''. 
This is the majority ($\frac{22}{33}=67\%$) of the data in \fig{data}.
\item
In the minority case ($\frac{11}{33}$),
$P$ is 
mid-range 
\mbox{($0.03<P(runaway|X)<0.81$)} 
and \eq{runaway} yields incorrect predictions in $\frac{4}{11}$
rows.
\ei
\begin{figure}

\footnotesize
\begin{tabular}{|p{0.96\linewidth}|}\hline
{\bf Features of \fig{data}.}\\\hline

{\em
Requirements } features 
relate to the understanding and commitment of the requirements
among the project members:
\bi
\item[R1:] Ambiguous requirements;
\item[R2:] Insufficient 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\\\hline
{\em 
Estimation} features  relate
to the technical methods for carrying out
the estimation, and the commitment between project members and
customers:
\bi
\item[E1:]
Insufficient awareness of the importance of the estimation;
\item[E2:]
Insufficient skills or knowledge of the estimation method;
\item[E3:]
 Insufficient estimation of the implicit requirements;
\item[E4:]
Insufficient estimation of the technical issues;
\item[E5:]
Lack of stake holder' commitment of estimation.
\ei\\\hline
{\em 
Planning} features
relate to
the planning or scheduling activity and the commitment to 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:]
Unspecified project review milestones;
\item[P5:]
Insufficient planning of project monitoring and controlling;
\item[P6:]
Lack of project members' commitment for the project plan.
\ei\\\hline
{\em 
Team organization} features
relate to the state of the projects; e.g. the fundamental skills
or experience and morale of project members:
\bi
\item[O1:]
Lack of skills and experience;
\item[O2]]:
Insufficient allocation of resources;
\item[O3]]:
Low morale.
\ei\\\hline
{\em 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 the features seen in \protect\fig{data}.}\label{fig:define}
\end{figure}

\noindent
While an important result, \eq{runaway} has several drawbacks:
\bi
\item
{\em Not automatic:}
\eq{runaway}
was created
after a manual inspection of the data by a team of skilled mathematicians. Such a manual
analysis is hard to reproduce
or
apply 
to a new data set. 
Subsequent work by Abe, Takagi, et.al ~\cite{abe06} automated the method with
a N{\aive} Bayes classifier, but this compromised
the {\em explainability} of the predictive model (see below).
\item
{\em Only explores one subset:}
 Takagi et.al. did not compare
the feature subset
$\{e3,e5,p3,p5\}$ with other feature subsets. Hence, while they showed that 
this subset was useful, they did not demonstrate that it was the {\em most} useful subset.
\item
{\em Ambiguous:}
At low and high $P$ values, \eq{runaway} sends a clear signal about what is, and is not,
a potentially runaway project. However, at middle-range $P$ values, \eq{runaway}'s
conclusions are
ambiguous and, hence, hard to explain.
\ei

%In contrast, the analysis reported in the rest of this paper generates a 
%predictive model for runaways via  automatic methods that thoroughly search 
%many 
%feature subsets. 
%This paper also addresses the ambiguity problem.
%The {\em covering}  algorithms
%used below seeks the subsets of the data that can be most clearly explained by a single rule.
%That part of the data is declared {\em covered} (a.k.a. explained)
%and covering then recurses
%on the remaining data. Hence, for ambiguous regions
%(e.g. dta yielding $0.03<P(runaway|X)<0.81$), a covering algorithm performs
%a
%recursuve procedure that reduces (or removes) that ambiguity.
%
\section{The Explanation Problem }
\PARstart{L}{earning} explainable models
is harder than it may appear.
This section offers examples where learned 
models {\em perform} well, but  {\em explain} themselves poorly.

\subsection{Learning Latent Features}

Numerous data mining methods check if the available features 
can be combined in useful ways. In this way, {\em latent} features
within a data set can be discovered.

For example,
principal
components analysis (PCA)~\cite{Dil84} has been widely applied to
resolve problems with structural code measurements;
e.g.~\cite{Muns91}. PCA identifies the distinct orthogonal sources
of variation in a data sets, while mapping the raw features onto a set of
uncorrelated features that represent essentially the same
information contained in the original data. For example,
the data shown in two dimensions of \fig{pca} (left-hand-side)
could be approximated in a single latent feature
(right-hand-side).


\begin{figure}
\begin{center}
\includegraphics[angle=270,width=2in]{pca.pdf}
\end{center}
\caption{The two features in the left plot can be transferred to the right plot via one latent feature.
}\label{fig:pca}
\end{figure}
Since  PCA combines many features into fewer latent features,
the structure of PCA-based models
may be very simple. For example, previously~\cite{me07c}, we have used PCA
and a decision tree learner to find the  following predictor for defective software modules:~\\

\newcommand{\setuptabs}{
\hspace*{.3in}\=\hspace*{.2in}\=\hspace*{.2in}\=\hspace*{.2in}\=\hspace*{.1in}
\hspace*{.2in}\=\hspace*{.2in}\=\hspace*{.2in}\=\hspace*{.2in}\=\hspace*{.2in}
\hspace*{.2in}\=\hspace*{.2in}\=\hspace*{.2in}\=\hspace*{.2in}\=\hspace*{.2in}\kill
}

\begin{minipage}{\linewidth}
{\footnotesize 
\begin{tabbing}
\setuptabs
\>if \>$domain_1 \le 0.180$\\
\>then NoDefects\\
\>else \>if $domain_1  >  0.180$\\
\> \>  then \>\> if $domain_1  \le 0.371$ then NoDefects\\
\> \>  else \>\> if $domain_1  >  0.371$ then Defects\\
\end{tabbing}}
\end{minipage}


Here, ``$domain_1$'' is one of the latent features found by PCA. This tree
seems very simple, yet is very hard to explain to business
clients users since ``$domain_1$'' is calculated using a very complex
weighted sum (in this sum,
$v(g), ev(g), iv(g)$ are 
McCabe or Halstead static code metrics~\cite{mccabe76,halstead77}
or variants on line counts): 
\begin{equation}\label{eq:latent}
{\scriptsize
\begin{array}{r@{}c@{~}l}
domain_1&=& 0.241*loc  +0.236*v(g) \\
      &&+0.222*ev(g)+0.236*iv(g)  +0.241*n  \\
      &&+0.238*v -0.086*l +0.199*d   \\
      && +0.216*i  +0.225*e  +0.236*b +0.221*t\\
     && +0.241*lOCode  +0.179*lOComment\\
     && +0.221*lOBlank +0.158*lOCodeAndComment \\
     && +0.163*uniq_Op +0.234*uniq_Opnd\\
     && +0.241*total_Op  +0.241*total_Opnd \\
     && +0.236*branchCount\\
\end{array}}
\end{equation}
As we shall see below, other learners can yield effective models that are simpler to
explain without using
complex latent features.


\subsection{Ensemble Learning}

Data mining for SE means summarizing the  complex
behavior of a  group of developers struggling to build intricate
artifacts.
Data mining over such complex multi-dimensional data often requires {\em
fusing} together the results from multiple learners~\cite{toh04}.  
Such ensembles may {\em perform} well but, as we shall see,
are hard to {\em explain}.

In {\em basic ensemble method} (BEM), $l$ learners are run on
various subsets of the available data. These learners use
some features $r$ to predict for classes $s$  to find a
function $x_j(r,s)$ that returns the probability of the target
 classes $s$.
BEM returns the mean probability:
\begin{equation}
\hat{x}_{BEM} = \frac{1}{l}\sum^l_{j=1}x_j(r,s)
\end{equation}
The {\em linear generalized ensemble method} (GEM) returns a weighted
sum of the conclusions of each learner $x$ in the ensemble. 
\begin{equation}\label{eq:lgem}
\hat{x}(\alpha)_{GEM} = \sum^l_{j=1}\alpha_jx_j(r,s)
\end{equation}
where $\alpha_j$ is the normalized performance score of $x_j$
on the training data (so 
learners that performed the worst,
contribute the least).

For some data sets, the combination rule is non-linear and 
complex. For example, Toh et.al.~\cite{toh04}'s
variant of \eq{lgem} uses a Jacobian matrix for $\hat{x}$ with
 different coefficients for
each feature $r_i\in r$ and target class $s_m \in s$.
These coefficients are learned via multivariate polynomial regression.
Toh et.al. report that their
 resulting ensemble {\em performs} better than
simpler schemes.
However, it may be harder to {\em explain} the ensemble
since
that explanation must cover:
\bi
\item The learning methods used to generate 
$x_j$;
\item
The combination rule that computes $\hat{x}$; and
\item
The regression method used to tune the coefficients used in the combination
method.
\ei
Such an explanation is not required if the users are willing
to accept the conclusions of the learner, without explanation. However,
for data sets as small \fig{data}, it seems reasonable to expect that
a simple explanation of runaway projects should be possible. Also, if
managers are to use the results of the learner as part of their deliberations,
they need some succinct structures that they can reflect over.

\subsection{N{\aive} Bayes Classifiers}

It is hardly surprising that complex latent features (e.g. \eq{latent})
or 
intricate combinations of multiple learners
(e.g. \eq{lgem}) are hard to explain. What is surprising is
how hard it is to explain the results of even a single, supposedly
simple, learner.  For example, this section offers a complete
description of how a N{\aive} Bayes classifiers makes its conclusions.
The reader is asked to consider how
many users would understand this description (in our experience,
we have yet to meet a single one).

A N{\aive} Bayes classifier~\cite{duda76}
is
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  posterior  probability
$P(H|E)$. 

When building predictors for runaways,
the
posterior probability of each hypothesis class ($H \in $\{``ok'' or ``runaway''\})
is calculated, given the features
extracted from a 
project  such ``ambiguous requirements''
or ``low morale'' or any other of the features
shown in \fig{define}.
The classification is the hypothesis $H$ with the highest
posterior $P(H|E)$.

N{\aive} Bayes classifiers are called ``n\aive'' since they assume
independence of each feature. While this assumption
 simplifies the implementation  
(frequency
counts are required only for each feature),
 it is possible
that
correlated events are missed by this ``n\aive'' approach.
Domingos and Pazzani show theoretically
that the independence 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}).

\eq{nb} offers a simple method for handling missing values. Generating a
posterior probability means of tuning a prior probability
to new evidence. If that evidence is missing,
then no tuning is needed. In this case \eq{nb} sets $P(E_i|H)=1$ which, in effect,
makes no change to $P(H)$.

When estimating the prior probability of hypothesis $H$, 
it is common practice~\cite{yang02} to  use 
 an {\em M-estimate} as follows.
Given 
that the total number of hypothesis is $C$,
the total number of training instances is $I$, and  $N(H)$ is the frequency the hypothesis $H$ within
$I$, then
\begin{equation}\label{eq:b}
P(H) = \frac{N(H) + m}{I + m\cdot C}
\end{equation}
Here $m$ is a small non-zero constant (often, $m=1$). Three special cases of \eq{b} are:
\bi
\item
For high frequency hypothesis 
in
large training sets,
$N(H)$ and $I$ 
 are much larger than 
$m$ and $m\cdot C$, so  \eq{b} simplifies
to 
$P(H)= \frac{N(H)}{I}$, as one might expect. 
\item
For low frequency classes
in large training sets,
$N(H)$ is small, $I$ is large,
and 
the prior probability for a rare class is never less than $\frac{1}{I}$;
i.e. the inverse of the number
of instances. If this were not true, rare classes would never appear in predictions.  
\item
For very small data sets, $I$ is small and $N(H)$ is even smaller.
In this case,
\eq{b} approaches the inverse of the number of classes; i.e. $\frac{1}{C}$.
This is a useful approximation when learning from very small data sets 
when all the data relating to a certain class has not yet been seen.
\ei
The prior probability calculated in \eq{b} is a useful lower bound for $P(E_i|H)$.
If some value $v$ is seen $N(f=v|H)$ times in feature $f$'s observations for 
hypothesis $H$, then\begin{equation}\label{eq:laplace}
P(E_i|H) = \frac{N(f=v|H) +l\cdot P(H)}{N(H) + l} 
\end{equation} 
Here, $l$ is the {\em L-estimate} and is set to a 
small constant (Yang \&Webb~\cite{yang02} recommend $l=2$).
Two special cases of are:
\bi
\item
A common situation is when there are many examples of 
an  hypothesis 
and numerous observations have been made
for a particular value. In that situation, 
$N(H)$ and $N(f=v|H)$ are large and
\eq{laplace}
approaches \mbox{$\frac{N(f=v|H)}{N(H)}$}, as one might expect. 
\item
In the case of very
little evidence 
for a rare hypothesis,
\mbox{$N(f=v|H)$} and $N(H)$ are small and \eq{laplace}
approaches $\frac{l\cdot P(H)}{l}$; i.e. the default frequency of an observation in  a hypothesis
is a fraction of
the probability of that hypothesis. This is a useful approximation when very
little data is available. 
\ei
For
numeric features it is common practice for N{\aive} Bayes classifiers
to use the Gaussian probability
density function~\cite{witten05}:
\begin{equation}\label{eq:normal}
g(x) =
\frac{1}{\sqrt{2\pi}\sigma}e^{-\frac{(x-\mu)^2}{2\sigma^2}}\end{equation} where
$\{\mu,\sigma\}$ are the feature's \{mean,standard
deviation\}, respectively.
To be precise, the probability of a
continuous feature having exactly the  value $x$ is zero,
but the probability that it lies within a small region, say $x \pm
\epsilon/2$, is $\epsilon \times g(x)$.  Since $\epsilon$ is a
constant that weighs across all possibilities, it cancels out and
needs not be computed. 

\begin{figure}[!t]
\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{Means and standard deviations 
 from \fig{data}.}\label{fig:meansd}
\end{figure}
N{\aive} Bayes classifiers
are frustrating tools in the data mining arsenal. 
They exhibit excellent performance, but offer few
clues about the structure of their models.
The means and standard deviations for \fig{data} are shown in \fig{meansd}.
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 values for ``ok'' projects in
\fig{data} shows that this is not true:
$r1$ is usually zero except in two cases where it takes the value
of three. 

One 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$.  Conclusions are made by asking all the
Gaussians which class they believe is most likely.

\subsection{N{\aive} Bayes and Software Engineering}


N\aive Bayes classifiers are widely used in the SE literature for 
several reasons. 
N\aive Bayes classifiers summarize the
training data in one frequency table per class.  Hence,
they consume very little memory and can quickly 
modify their knowledge by incrementing the frequency
count of feature ranges seen in new training examples.
Also, many studies 
(e.g. ~\cite{hall03,dou95,domingos97optimality})
report that N{\aive} Bayes
exhibit excellent performance compared to 
other learners. 

For example,
recently Menzies, Greenwald \& Frank~\cite{me07b}
have 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.
In that study, the learner with the {\em worst} 
explanation power (N{\aive} Bayes)
had the {\em best} performance, by far.
For the data sets explored by Menzies, Greenwald \& Frank,
the median advantage of N{\aive} Bayes, the C4.5 decision tree learner~\cite{quinlan92},
and the OneR rule learner~\cite{holte93} over the other learners was 52.4\%, 0\%,\mbox{-16.7\%}, respectively
(see \fig{qc}).
On analysis, Menzies, Greenwald \& Frank concluded that 
N{\aive} Bayes worked so well because of the
the product calculation of \eq{nb}. They reasoned as follows.
Many static code features  have similar information content. 
Hence, minor  changes in how the training data was sampled yielded different ``best'' features
for predicting defects.
The best predictions come from mathematical methods
like N{\aive} Bayes 
that accumulate the signal from many code features (using \eq{nb}'s product rule).
Decision tree learners like C4.5 and rule learners like OneR, on the other hand,
do  not perform well
in this domain
since they assume hard and fast boundaries between what is defective and what is not.


\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 {\em differences} when learners were applied
to the same the training and test data.
Performance was measured using {\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.
Vertical bars  are added to
mark (i)~the zero point and (ii)~the minimum possible value
and (iii)~the maximum
possible value.
The median performance of N{\aive} Bayes
was much higher than the other methods. 
}\label{fig:qc}
\end{figure}

In summary, when mining software engineering data,
there are many reasons to start with a
N{\aive} Bayes classifier.
Abe, Muzono, Takagi,
et.al.~\cite{abe06} used such classifiers to
 extend their prior work on runaway software
projects~\cite{takagi05,mizuno00}.
However, this
classifier was only a {\em performance system}.
not an {\em explanation system}, so it
could not offer insights into, say, how to best change
a software project in order to avoid runaways.
As shown above,
N{\aive} Bayes classifiers do not generate such succinct
generalizations.  This is a problem  since what
developers really want to know is what should be done to avoid
runaway status. 

\subsection{Discussion of the Explanation Problem}

As the mathematics gets more elaborate, it becomes harder
to explain 
a N{\aive} Bayes classifier 
to a typical business user:
\bi
\item
Many users are not trained mathematicians. Hence,
they may be confused by
\eq{nb}, \eq{b}, 
\eq{laplace}
and \eq{normal}.
\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

To be fair, N{\aive} Bayes' explanation problems are seen in other kinds of data miners:
\bi
\item
The problems with PCA and ensemble-based learners 
were discussed above.
\item
Tree learners such as C4.5~\cite{quinlan92}
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.
Such trees can be  cumbersome, needlessly large, and
difficult to understand. 
\item
Clustering algorithms~\cite{queen67}
and nearest neighbor methods~\cite{cover67,bey06}
do not condense their working memory into succinct descriptions.
Rather, inferences on new information are made by a query over all the old information.
\item 
Simulated annealers~\cite{kirkpatrick83} learn constraints to an input space that results in higher
values in the output space.
However, 
there is no generalization or summarization in a simulated annealer such as which subset of the input
space is most important to control.
 \item Neural 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}.
\ei

The problem of explaining the performance of these learners to end-users
has been explored extensively in the literature (see the review in~\cite{taylor05}). 
Often, some {\em post-processor} is used to convert an opaque model into a more
understandable form:
\bi
\item
Towell and Shavlik 
generate refined rules from the internal data structures of a neural network~\cite{towell93extracting}. 
\item
Quinlan implemented  a post-processor to C4.5 called  C45rules 
that generates succinct rules from cumbersome decision tree branches via (a)~a greedy pruning
algorithm followed by (b)~duplicate removal then
(c)~exploring subsets of the  rules relating
to the same class~\cite{quinlan92}.
\item
TARZAN was another post-processor to C4.5 that searched for the smallest
number of decisions in decision tree branches that (a)~pruned the most branches
to undesired outcomes while (b)~retaining branches leading to desired outcomes~\cite{me00e}.
\ei
\section{Learning Methods}
\subsection{Rule Learners}
\PARstart{R}{ather} than patch an opaque learner with a post-processor,
it may be better to build learners than directly generate succinct high-level descriptions of a domain.
For example,
RIPPER~\cite{cohen95r}  is one of the fastest
{\em rule learners}  known in the literature. 
The generated rules
are of the form
\mbox{$condition \longrightarrow conclusion$}:
\[
\underbrace{Feature_1 = Value_1 \wedge Feature_2 = Value_2 \wedge \ldots }_{condition} \longrightarrow 
\underbrace{Class}_{conclusion}\]
The rules generated by RIPPER perform 
as 
well as
C45rules, yet  are much smaller and easier to read~\cite{cohen95r}.

Rule learners like RIPPER and 
PRISM~\cite{cend87}
generate
small, easier to understand, symbolic representations of the patterns in a data set. 
PRISM is a less sophisticated learner than RIPPER and is not widely used.
It was initially added to this study to generate a lower bound on the possible
performance. However, as we shall see, it proved surprisingly effective.
\begin{figure}
\footnotesize
\begin{center}
\begin{tabular}{|p{0.95\linewidth}|}\hline
\be
\item
Find the majority 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 features) 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 examples 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}

Like RIPPER,
PRISM is a {\em covering} algorithm 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$). 
All the examples that satisfy the condition
are marked as {\em covered} and removed from
the data set. PRISM then recurses on the remaining data. 

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.

One way to visualize a covering algorithm is to
imagine the data as a table on a piece of paper. If there exists a clear pattern between the features
and the class,
define that pattern as a rule
and cross out all the rows covered by that rule.  
As covering
recursively explores the remaining data, it keeps splitting the data into:
\bi
\item
 what is easiest to explain, and
\item
any remaining ambiguity that requires a more detailed analysis.
\ei

PRISM is a n{\"aive} covering algorithm and has problems
with {\em residuals} and {\em over-fitting}.
If there are rows with similar patterns and similar
frequencies occur in different classes, then:
\bi
\item
these {\em residual} rows are the {\em last} to be removed for each class; 
\item so
the {\em same} rule can be generated for {\em different} classes.
\ei

In {\em over-fitting},
a learner 
fixates on spurious signals that do not predict for the target class. 
PRISM's over-fitting 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 residuals and over-fitting problem three techniques:
{\em pruning}, {\em description length} and {\em rule-set
optimization}
For a full description of these techniques, see\cite{dietterich97}.
In summary:
\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.
For example, back pruning could remove the residual rules.
\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 the rule errors. If a rule set is over-fitted, the error rate increases,
the description length grows, and RIPPER applies a rule set pruning operator.
\item
{\em Rule set optimization} 
tries
replacing rules
straw-man alternatives (i.e. rules grown very quickly by some
n\"aive method).
\ei

%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

\subsection{Performance Measures}

Our 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 learner, 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}). 
$A,B,C,D$ can be combined in many ways. 
For example, accuracy (or $acc$) is the percentage of true
positives ($D$) and negatives ($A$) found by the detector.
\begin{equation}acc=accuracy=(A+D)/(A+B+C+D)\end{equation}

Also, recall (or $pd$) comments on how much of the target was found.
\begin{equation}
pd=recall=D/(B+D)
\end{equation}
Precision (or $prec$) comments on how many of the instances that
triggered the detector actually containing the target concept.
\begin{equation}
prec=precision=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 assessments that include {\em both} precision and recall.
\begin{equation}
\mbox{{\em f-measure}}=\frac{2 \cdot prec \cdot pd}{prec + pd}\\
\end{equation}
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.
%\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 domains may not work best on the current domain and (2)~analysts
%are advised 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]
\footnotesize
\begin{center}
\begin{tabular}{c}
\includegraphics[width=2.5in]{recall.pdf}\\
\includegraphics[width=2.5in]{prec.pdf}\\
\includegraphics[width=2.5in]{f.pdf}\\
\includegraphics[width=2.5in]{acc.pdf}
\end{tabular}
\end{center}

\begin{center}
\begin{tabular}{l|rllrr}
     &  bins & learner  & \#features & \#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}



\subsection{Experiments With the Learning Methods}\label{sec:cycle}

\PARstart{V}{arious} combinations of the 
learning method described above were applied to \fig{data}.
The results are shown in
Figure~\ref{fig:rx}.
In all 13 {\em treatments} where applied to  \fig{data}.
Each {\em treatment} is some combination of a data filter,
a learner, and a assessment method. 
This section discusses how each treatment was designed using results from
the proceeding treatments.


Before moving on, we call attention to the $accuracy$
results of \fig{rx}.
Observe how  {\em accuracy} can be an remarkably insensitive performance measure; i.e.  it remained
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 deprecated by this paper. 


\subsubsection{Cross-Validation}

Treatment $a$ is 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 generated 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.
The data is divided into, say, 10 buckets. Each bucket is set aside as a test set and
a model is learned from the remaining data. This learned model is then assessed using the
test set. Such cross-validation studies
are the 
preferred evaluation method when the
goal  is to produce predictors intended to  predict future 
events~\cite{witten05}. 

In treatment $b$, a cross-validation experiment was applied to the data.
The treatment $b$ results
 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 altered 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. 

Note that treatment $c$ uses the method
favored 
by the previous high water mark
in this research~\cite{abe06}. 
In the sequel, we show how this study found data mining methods that significantly out-perform
that prior work.

\subsubsection{Discretization}

Treatments $d,e$ and $f$ explore {\em discretization}.
Discretization clumps together
observations taken over a continuous
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
between two break points $b_i$ and $b_{i+1}$
at frequency counts $c_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(c_i = c_j\right)\right)$.
For N{\aive} Bayes classifiers working on $n$ instances, 
Yang \& Webb~\cite{yang02} advocate equal
frequency with $c_i=c_j=\sqrt{n}$.
\ei
For example, \fig{data} holds 32 instances
so a $b=3$ equal frequency discretion hopes
to place
 $\frac{32}{3}\approx 10$ values
into each part of the histogram.
However, 
\fig{data} does not have ten instances for each feature  value so, as shown in \fig{efd},
a skewed histogram is generated.
\begin{figure}
\begin{center}
\scriptsize
\begin{tabular}{r|r|rl}
feature & range & frequency &\\\hline
o3 & 0 & 24 & \rule{24mm}{2mm}\\
   & 1 & 1 & \rule{1mm}{2mm}\\
   & 2,3 & 7 & \rule{7mm}{2mm}\\\hline
p6 & 0   & 19 & \rule{19mm}{2mm}\\
   & 1,2 & 10 & \rule{10mm}{2mm}\\
   & 3    & 3 &\rule{3mm}{2mm}\\\hline
r1 & 0,1 & 23 & \rule{23mm}{2mm}\\
   & 2   & 5 & \rule{5mm}{2mm}\\
   & 3   & 4 & \rule{5mm}{2mm}\\
\end{tabular}
\end{center}
\caption{Some $3bin$ results from \fig{data}.
}\label{fig:efd}
\end{figure}



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 class 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, the
Fayyad \& Irani~\cite{FayIra93Multi} supervised discretizer
assumes
that the best cliff
is the one
that most divides  target classes.  In terms of information theory,
this can be measured using $entropy$; i.e.  
the number of bits required to encode the class
distribution. If the classes in a sample
of $n$ instances occur at frequencies 
counts
$c_1, c_2,...$,
then the entropy of that sample is
\[
Ent(c_1,c_2,...) = -\frac{c_1}{n}\cdot log_2\left(\frac{c_1}{n}\right)  
-\frac{c_2}{n}\cdot log_2\left(\frac{c_2}{n}\right) -  \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, with disappointing results:
\bi
\item 
Yang \& Webb's rule ($c_i=\sqrt{n}=\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 any parts of our ranges.
\item
Best results were seen with a simple {\em 3bin} equal frequency 
scheme \mbox{(i.e. $|b|=3$)} in Treatment $f$
where
PRISM achieved
precisions as high as the RIPPER self-test (treatment $a$).
However, the same experiment saw
the worst recall. 
\item
The same $3bin$ scheme offered little help to RIPPER or N{\aive}  Bayes
(see treatments $d,e$).
\ei

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

\subsubsection{Feature Subset Selection}

The remaining treatments ($g,h,i,j,k,l,m$) explore how different {\em feature subsets}
change the performance of the learning.
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 uninformative;
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 aspect
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, WRAPPER adds some combinations of
features and asks some target
learner 
to build a model using just those
features.  WRAPPER then grows the set of
selected features and checks if a
better model comes from learning over the larger set of features.

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, a heuristic search drastically reduce this search space.
WRAPPER stops when there are no more features 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-climbing 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).

\begin{figure}[!t]
\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& average\\\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 WRAPPER
selected
features in ten experiments on 90\% samples of the data.
}\label{fig:wrapper}
\end{figure}
\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 \fig{data}  (selected at random) was ignored: 
\bi
\item Group \#1 shows the features that, on average,
were selected in the majority of ten runs (on average, 6 times or more).
\item
Group \#2 shows the features that were selected 2 to 5 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
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
\begin{figure}[!t]
\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{Rules generated by treatment $m$.}
\label{fig:rule}
\end{figure}
Treatments $g,h,...m$ show the results of 
applying the top-ranked features to the discretized data.
For each learner, if 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.


\subsubsection{Best Results}
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}. 

\fig{efd} showed 
$r1\in\{0,1\}$, $p6\in\{1,2\}$,  $o3=0$ is a frequent pattern in our data.
Hence, after a covering algorithm removes
all other more interesting structures, the residual rows can contain
this frequent pattern. This, in turn, means that
identical rules could be generated for different
classes; e.g. rules 4\&9 of \fig{rule}  (this is the {\em residual rule} problem
discussed above).

It is important to read these rules top to bottom since a rule fires
{\em only} if {\em all} the rules above it {\em fail}.  In practice,
this means that the residual rule 9 is never used (it is blocked
by rule 4).

A 10-way cross-validation
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.
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 detrimental result
on the collected statistics.

\subsubsection{User Studies}
To test the {\em explainability} of \fig{rule},  we ran a session with eight software
engineers
managing large software verification projects.

 Pseudocode for N{\aive} Bayes
(with kernel estimation) and PRISM (\fig{prism}) was introduced. PRISM
was summarized
this way: ``each rule handles some examples,
which are then removed, and  the algorithm repeats
on the remaining data''.

Within an hour, the engineers were hand-simulating PRISM. 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 identified, then crossed off. The engineers
stopped after simulating PRISM's
activities 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.''
Significantly, none of the engineers tried to apply
N{\aive} Bayes; i.e. m-estimates, l-estimates, the $\epsilon$ approximation, and the Gaussians
of kernel estimation.


In summary, the simplicity of PRISM the rules of \fig{rule}
allowed them to be explained to one focus group, all within  a one hour session.
%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{Discussion}

\subsection{Related Work}\label{sec:related}

\PARstart{T}{his} research aims at producing a precise, explainable, operational definition
of a runaway project. Other work is this area is less precise and not operational.

For example, in 1997, Glass~\cite{glass97}  had informally
sampled several high-profile software disasters and found the following features
to   be predictive for runaways:
\bi
\item
Project objectives not fully specified
(in 51\% of the sample);
\item       Bad planning and estimating (48\%);
\item
Technology new to the organization (45\%);
\item
Inadequate/no project management methodology
(42\%);
\item
Insufficient senior staff on the team (42\%);
\item       Poor performance by suppliers of hardware/software (42\%)
\item
Other- performance (efficiency) problems (42\%)
\ei
Glass did not offer an clear operational method
for combining their features into an effective predictor. 
Other work carefully documented the software risk problem, but did not offer
automatic tool support:
\bi
\item
Jiang et.al.~\cite{jiang02}
studied
40 features collected from questionnaires posted to personnel with recent
experience with an IS project. Their study is an exemplary example of
software engineering research: after clearly defined six hypotheses about software
risk, they identify those hypotheses not supported by their data.
\item
Ropponen \& Lyytinen~\cite[p110]{ropp00}
studied self-reported data from 83 project managers and 1,110 projects to
find 
26 software risk components:
six scheduling and timing risks;
four system functionality risks;
three subcontracting risks;
four requirements management risks;
four resource usage and performance risks; and
five personnel management risks.
\ei
Both reports have the same limitations:
their
conclusions
contain a somewhat
ill-defined and manual  procedure for managers to explore the above risks.
For example, both reports list risks and their weighted contribution
to total risk.
However, no combination rule is offered on how to best combine evidence 
of {\em multiple} risks.

Another aspect that sets this work apart from other studies is 
{\em reproducibility}.
Neither the Jiang et.al. nor Ropponen \& Lyytinen~\cite[p110]{ropp00}
studies are reproducible since they did not made their data available to other researchers.
Reproducibility
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 current report began when the second and third authors
published their data~\cite{takagi05} and defined a research challenge: how to
better explain the results of their learning to developers~\cite{abe06}.
We would strongly encourage software engineering researchers
to share data, define challenges, and to
take the time to rework the results of others.

\subsection{External Validity}


This study has produced:
\be
\item
A recommended {\em feature subset} for predicting runaways ($r1,p6,o3$);
\item
A recommended {\em model} that combines those features (\fig{rule}); and
\item
A recommended {\em method} for generating that subset and that model:
\bi
\item
$3bin$ discretization;
\item
a WRAPPER around PRISM;
\item
10-way cross-validation using PRISM on the subsets found by WRAPPER.
\ei
\ee
It is good practice to question the external validity of these recommendations.

WRAPPER selected different features than the manual method that produced
\eq{runaway}. 
That is, the recommended feature subset learned by our recommended method is different to that 
found by our earlier work.
This raises a concern about external validity: why do our conclusions keep changing? 

We endorse the conclusions of this study over our prior
work~\cite{takagi05} for two reasons.  Firstly, this study explored
far more feature subsets that before:
\bi
\item \eq{runaway} was generated
after a manual analysis of a few features. \item
\fig{rule} was generated
after an automatic search through thousands of subsets.  
\ei
Secondly,
the results of this study perform better than our prior results:
\bi
\item
\eq{runaway} offers ambiguous conclusions in the range
\mbox{($0.03<P(runaway|X)<0.81$)}.
\item
\fig{rule} offers categorical conclusions
about the runaway status of a project. Further, it  does so with perfect precision.
\ei

A more serious validity threat comes from the data used in this study. Any inductive process suffers from
a {\em sampling bias}; i.e. the conclusions of the study are a function of the data used in that study.
In that regard, we have evidence that our results are stable across small to medium-sized
changes to our project sample.
In a 10-way cross-validation experiment, 10\% of the data (in our case, 3 to 4 records) is set aside and the 
model is learned from the remaining information. Our learned model had an average precision of 1.0 in a 10-way;
i.e. the precision of our model remained perfect, despite a 10\% change in the training data.

Also, \fig{data} does not show all the data available to this study.
Some of the data available to this research group is proprietary and
cannot be generally released.
In order to check the external validity of our methods,
these ten extra records were not analyzed until {\em after} we
reached the above conclusions regarding 
the recommended  data mining method for this data.
When our recommended  method was applied to \fig{data}, plus the extra ten records,
WRAPPER still found the features shown in \fig{wrapper}.
Further, the
performance of the rule set learned from the extended data
had the same properties as \fig{rule}; i.e. 
\bi
\item It out-performed
N\aive Bayes;
\item
It exhibited perfect precision (precision=1.0)
over the 10-way cross-validation.
\ei
In summary,
despite the data set size changing by a small to medium amount (-10\% to +33\%), 
there is:
\bi
\item no instability in the recommended features;
\item no  instability in the performance of of the recommended model;
\item no instability in the recommended method.
\ei

%
%proposed by Glass~\cite{glass97},
%Jiang et.al.~\cite{jiang02},  
%Ropponen \& Lyytinen~\cite{ropp00}
%
%Recalling the above discussion on the top rule of \fig{rule},
%the generated predictor is clearly biased by the data used to generate it 
%One of the motivations
%of this work was to produce an automatic predictor for a runaway software project.
%While \fig{rule} could be automated, it is our experience that it takes
% one graduate-level subject  to train analysts in how to
%repeat \tion{cycle}'s
%cyclic exploration of data mining
%methods. That is, while \fig{rule} is automatic, the process of generating \fig{rule} is manual, error-prone,
%and requires some level of expertise to reproduce. 
%
%could be repeated 
%
%XXX
%
\subsection{Method Selection for Quirky Data}

Several times we found that
certain widely regarded methods  (RIPPER; discretization using
Fayyad\&Irani; discretization with Yang \& Webb's $\sqrt{n}$ rule)
did not yield the best results for this data set.
The reason for this is simple:
software engineering data sets are often small:
\bi
\item
\fig{data} is one table with only
22*33 cells; 
\item
Elsewhere we have published results
on even smaller data sets~\cite{me02k,me06d}. 
\ei
It is hard to know {\em apriori} what are 
the quirks of small software engineering
data sets.
Hence, we recommend trying many methods,
even supposedly out-dated ones.
For example, in this study, a very simple rule-learner (PRISM)
produced the best performance while being
most understandable to our users.

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


More
generally, Fayyad~\cite{fayyad97} argues persuasively
that data mining should be viewed as a {\em small part} of
the knowledge and data discovery (KDD) cycle shown in
\fig{kddcycle}. 
For example, in this report we used  discretization
and feature subset-selection for {\em pre-processing} and {\em
selection} steps shown in \fig{kddcycle}.  Also, we looped through the KDD
cycle  13 times: each time,
the results from the previous round informed our work
for the next round.

\subsection{Data Mining Methods}
Based on this work, and certain standard texts in the data mining 
field~\cite{witten05,fayyad97},
we offer the following advice to other researchers
data mining on SE data.
 
It is important to understand
the  {\em goals} of the data mining task. If the learned
model only needs to {\em perform}, and not {\em explain} then any
data mining method might do ranging from
\bi
\item
N{\aive} Bayes classifiers 
\item
to clustering algorithms, decision tree learners, neural nets, etc
\item 
or, as explored in \eq{lgem}, ensembles of the above.
\ei 
The simplest of the above is N{\aive} Bayes. Such classifiers
scale to very large data sets and,
in many domains, have performed very well~\cite{dou95,hall03,domingos97optimality}.
Also, in at least one SE domain~\cite{me07b}, they far out-performed
other methods.

However, if the goal is to generate an {\em explainable}
theory, then:
\bi
\item 
Many business users do not have the background required to
understand mathematical-based learners. For such users,
the rule learners (e.g. RIPPER) may be most useful
since they produce
succinct summaries of the data.
\item
It is useful
to reduce the range of number variables with discretization. Once reduced,
the learned
model can be simpler since it only needs to comment on a few discrete
ranges rather than the entire number line.
\item
It is also useful
to reduce the number of features with feature subset selection. 
A repeated result in the literature~\cite{miller02,kohavi97,hall03}
is that 
the majority of the features can be pruned away and the resulting model
is either simpler, performs better or both.
For example, in this case
study, the
best performance and the most succinct/explainable  model were found using just $\frac{3}{22}$ of
the available data.
\ei
As to the choice of feature subset selector:
\bi
\item
Hall and Holmes~\cite{hall03} compare 
WRAPPER to several other variable pruning methods including the principal
component analysis (PCA) method used by Ropponen \& Lyytinen and Munson~\cite{Muns91} (amongst others).
Feature
selection
methods can be grouped according to
(a)~whether or not they make special use of the
target variable in the data set such as ``runaway'';
(b)~whether
or not pruning uses the target learner.
PCA
does not make
special use of the target variable. Also,unlike other pruning methods, WRAPPER {\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).
\item
For large data sets, WRAPPER can be too slow. When WRAPPER is not possible,
see the conclusion of the
Hall \& Holmes study~\cite{hall03} for
recommendations on two other feature subset
selection methods.
\item
If the data set is small enough (e.g. \fig{data}), use WRAPPER around a rule learner.
WRAPPER is the slowest feature subset selector but it is the only
one that can tune itself to the target learner.
\ei

Regarding performance measures, we have two recommendations:
\bi
\item
Comparing the $f$-measures in
treatment $a$ and $b$ of \fig{rx}, it is clear that self-tests
can over-estimate the value of a learned 
model. 
Hold-out sets are the recommended way to assess a learned model.
\item
Accuracy is
a widely  used measure for assessing a learned theory.
\fig{rx} shows that it can be remarkably uninformative. In that figure,
large changes in precision and recall make very little impact on the
accuracy. Hence, we strongly recommend against the use of accuracy.
\ei
The above issues are widely discussed in 
the data mining literature (e.g. ~\cite{fayyad97,provost98case,witten05,brouck03}). 
Nevertheless,
our reading of the literature is that multiple traversals
of the KDD cyclic application
using a range of techniques
 (e.g. different learners, discretizers, and feature subset selectors)
 is quite rare.
Often researchers take one learner, apply it once, then report the
conclusion.  
Also, despite many positive empirical studies,
feature selection is rarely seen in software
engineering
(exceptions:~\cite{kirsopp02,me07b}).
Further, it is still standard practice for software engineers
to present their data mining results in terms of accuracy of non-hold-out experiments (e.g.
\cite[p6]{nagappan05}).
We hope our results encourage a change 
in that standard practice.

\section{Conclusion}

\PARstart{I}{ntuitively}, it seems reasonable that optimizing for performance can compromise
explainability.
Software engineering data can be complex, noisy, or confusing.
Such complex data may require complex and arcane learning strategies; 
e.g. the defect
data sets studied by Menzies, Greenwald, and Frank.
Complex and arcane learning strategies will be hard to explain.
That is, good performance in  a learned model may imply poor 
explanatory power, especially for real world software engineering data.

This paper is a  counter-argument to such pessimism. We show that
at least for predicting runaway software projects, 
certain standard data mining
methods resulted in models with both:
\bi
\item High performance: i.e. precision=1.0;  and
\item
good
explainability: i.e. small rule sets, understandable by our users;
\ei
This result is a new
high water mark in predicting runaway projects.
This new predictor out-performs 
prior results in several ways:
\bi
\item
Our results are fully reproducible: the data for our analysis comes from \fig{data}; the software
used is freely available\footnote{\url{http://www.cs.waikato.ac.nz/~ml/weka/}}.
\item
Prior work by other researchers~\cite{glass97,ropp00,jiang02} has carefully documented the influence of features on
software risk, but  did not offer an  operational model
(by ``operational'', we mean that the model can generate performance statistics
like \fig{rx}).
\item
As to our own prior results, the logistic regression method~\cite{takagi05} required
some manual intervention on the part of the analyst. In contrast to that,
the techniques
described here are automatic.
Also,
due to ambiguities in the middle $P$ ranges of
\eq{runaway}, or the inner complexities of our N{\aive} Bayes classifier~\cite{abe06},
our prior mathematical results were much harder to explain
than the new rules of \fig{rule}.
\item
Comparing treatment $c$ and treatment $m$ in \fig{rx},
we see that our new data mining method (treatment $m$: $3bin$, WRAPPER, PRISM) has similar recall but much higher
precision than
our
old data mining method (treatment $c$: N\aive Bayes, from~\cite{abe06}). 
\item
Measured in terms of precision, 
this new model is as good as can ever be expected for our data.
Other combination data mining methods
could out-perform our result (e.g. by generating
a smaller, more explainable model with higher recall) but no other method
could be more
precise (since precision's maximum value is 1.0).
\item
Prior results conducted a manual exploration of a few subsets of the features~\cite{takagi05}. 
Here, we employed a feature subset selector that explored
thousands of feature subsets. Hence, we have far more confidence that
the following factors are most useful in recognizing runaways:
ambiguous requirements; 
low morale;
lack of project members' commitment to the project plan.
\ei
%This results also shows that 
%high performance and explainability
%are not always mutually exclusive.
%It is possible, for some data sets,
%to learn models
%that {\em both} perform well
%{\em and} explain themselves well, albeit with some effort (e.g. this study required
%13 attempts). 
%%Based on this work, the next step is clear:
%build data mining environments that automate some or all of the exploration required for this study.
\bibliographystyle{IEEEtran}
\bibliography{refs}
\begin{biography}[{\includegraphics[width=0.8in,keepaspectratio]
{tim_menzies}}]{Tim Menzies}
is a  associate professor
at the Lane Department of Computer Science at West Virginia University
(USA), and has been working with
NASA on software quality issues since 1998. He has a CS degree and a PhD
from the University of New South Wales and is the author of over 160 publications.
His doctoral research explored the validation of possibly inconsistent
knowledge-based systems in the QMOD specification language. 
\end{biography}

\begin{biography}[{\includegraphics[width=0.8in,keepaspectratio]
{osamu_mizuno}}]{Osamu Mizuno} is an assistant professor at the Graduate School of
Information Science and Technology at Osaka University (Japan). He has
a PhD degree of Engineering from Osaka University. His research
interests include software runaway detection, and fault-prone module
detection.  He is a member of IEEE and IEICE (the Institute
of Electronics, Information and Communication Engineers in Japan).
\end{biography}

\begin{biography}[{\includegraphics[width=0.8in,keepaspectratio]
{yasunari_takagi}}]{Yasunari Takagi} is an advisory technology specialist at OMRON
corporation, Japan. He has a PhD degree in Information Science and
Technology from Osaka University. He has been a leader in process
improvement activities in his company for a decade.
\end{biography}


\begin{biography}[{\includegraphics[width=0.8in,keepaspectratio]
{tohru_kikuno}}]{Tohru Kikuno} is a professor at the Graduate School of Information
Science and Technology at Osaka University (Japan). He received the
B.E., M.Sc., and Ph.D. degrees in electrical engineering from Osaka
University, Toyonaka, Osaka, Japan, in 1970, 1972, and 1975,
respectively. He joined Hiroshima University from 1975 to 1987. Since
1990, he has been a Professor at Osaka University. His research
interests include the analysis and design of fault-tolerant systems,
the quantitative evaluation of software development processes, and the
design of procedures for testing communication protocols.  He is a
senior member of IEEE, a member of ACM, and a fellow of IPSJ
(Information Processing Society of Japan) and IEICE (the Institute of
Electronics, Information and Communication Engineers in Japan).
\end{biography}       
\end{document}

