%XXX better than greedy search
%XXX the controllability assumption
%XXXX need to generate succinct theories.
%XXX simplicity first

% This is "sig-alternate.tex" V1.8 June 2007
% This file should be compiled with V2.3 of "sig-alternate.cls" June 2007
%
% This example file demonstrates the use of the 'sig-alternate.cls'
% V2.3 LaTeX2e document class file. It is for those submitting
% articles to ACM Conference Proceedings WHO DO NOT WISH TO
% STRICTLY ADHERE TO THE SIGS (PUBS-BOARD-ENDORSED) STYLE.
% The 'sig-alternate.cls' file will produce a similar-looking,
% albeit, 'tighter' paper resulting in, invariably, fewer pages.
%
% ----------------------------------------------------------------------------------------------------------------
% This .tex file (and associated .cls V2.3) produces:
%       1) The Permission Statement
%       2) The Conference (location) Info information
%       3) The Copyright Line with ACM data
%       4) NO page numbers
%
% as against the acm_proc_article-sp.cls file which
% DOES NOT produce 1) thru' 3) above.
%
% Using 'sig-alternate.cls' you have control, however, from within
% the source .tex file, over both the CopyrightYear
% (defaulted to 200X) and the ACM Copyright Data
% (defaulted to X-XXXXX-XX-X/XX/XX).
% e.g.
% \CopyrightYear{2007} will cause 2007 to appear in the copyright line.
% \crdata{0-12345-67-8/90/12} will cause 0-12345-67-8/90/12 to appear in the copyright line.
%
% ---------------------------------------------------------------------------------------------------------------
% This .tex source is an example which *does* use
% the .bib file (from which the .bbl file % is produced).
% REMEMBER HOWEVER: After having produced the .bbl file,
% and prior to final submission, you *NEED* to 'insert'
% your .bbl file into your source .tex file so as to provide
% ONE 'self-contained' source file.
%
% ================= IF YOU HAVE QUESTIONS =======================
% Questions regarding the SIGS styles, SIGS policies and
% procedures, Conferences etc. should be sent to
% Adrienne Griscti (griscti@acm.org)
%
% Technical questions _only_ to
% Gerald Murray (murray@acm.org)
% ===============================================================
%
% For tracking purposes - this is V1.8 - June 2007

\documentclass{sig-alternate}
\usepackage{times}
\usepackage{url}
\usepackage{cite}
\usepackage{colortbl}
\usepackage{graphicx}
%\usepackage{caption}
\newcommand{\bi}{\begin{smallitem}}
\newcommand{\ei}{\end{smallitem}}
\newcommand{\be}{\begin{smallenum}}
\newcommand{\ee}{\end{smallenum}}
\newcommand{\tion}[1]{\S\ref{tion:#1}}
\newcommand{\eq}[1]{Equation~\ref{eq:#1}}
\newcommand{\fig}[1]{Figure~\ref{fig:#1}}
\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{smallenum}
 {\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}}
\DeclareMathAlphabet{\mathscr}{OT1}{pzc}%
                                 {m}{it}
\newcommand{\W}{$\mathscr{W}$}
\input{boxplot}

\begin{document}
%
% --- Author Metadata here ---
\conferenceinfo{~}{~}
%\CopyrightYear{2007} % Allows default copyright year (200X) to be over-ridden - IF NEED BE.
%\crdata{0-12345-67-8/90/01}  % Allows default copyright data (0-89791-88-6/97/05) to be over-ridden - IF NEED BE.
% --- End of Author Metadata ---

\title{Case-Based Reasoning for Reducing Software Development Effort}
%\subtitle{An Introduction, Description, and Brief User Guide}
%
% You need the command \numberofauthors to handle the 'placement
% and alignment' of the authors beneath the title.
%
% For aesthetic reasons, we recommend 'three authors at a time'
% i.e. three 'name/affiliation blocks' be placed beneath the title.
%
% NOTE: You are NOT restricted in how many 'rows' of
% "name/affiliations" may appear. We just ask that you restrict
% the number of 'columns' to three.
%
% Because of the available 'opening page real-estate'
% we ask you to refrain from putting more than six authors
% (two rows with three columns) beneath the article title.
% More than six makes the first-page appear very cluttered indeed.
%
% Use the \alignauthor commands to handle the names
% and affiliations for an 'aesthetic maximum' of six authors.
% Add names, affiliations, addresses for
% the seventh etc. author(s) as the argument for the
% \additionalauthors command.
% These 'additional authors' will be output/set for you
% without further effort on your part as the last section in
% the body of your article BEFORE References or any Appendices.

\numberofauthors{3}
%  in this sample file, there are a *total*
% of EIGHT authors. SIX appear on the 'first-page' (for formatting
% reasons) and the remaining two appear in the \additionalauthors section.
%
\author{
% You can go ahead and credit any number of authors here,
% e.g. one 'row of three' or two rows (consisting of one row of three
% and a second row of one, two or three).
%
% The command \alignauthor (no curly braces needed) should
% precede each author name, affiliation/snail-mail address and
% e-mail address. Additionally, tag each line of
% affiliation/address with \affaddr, and tag the
% e-mail address with \email.
%
% 1st. author
\alignauthor
Adam Brady, \\Tim Menzies\\
       \affaddr{Lane Department of CS\&EE}\\
       \affaddr{West Virginia University, USA}\\
       \email{adam.m.brady@gmail.com}, \email{tim@menzies.us} 
\and
\alignauthor
Jacky Keung\\
       \affaddr{NICTA}\\
       \affaddr{University of NSW}\\
         \affaddr{Sydney}\\
         \affaddr{Australia}\\
       {\small \email{Jacky.Keung@nicta.com.au}}
\and
\alignauthor
Oussama El-Rawas, Ekrem Kocaguneli\\
       \affaddr{Lane Department of CS\&EE}\\
       \affaddr{West Virginia University, USA}\\
        \email{orawas@gmail.com, kocaguneli@gmail.com}
}
% There's nothing stopping you putting the seventh, eighth, etc.
% author on the opening page (as the 'third row') but we ask,
% for aesthetic reasons that you place these 'additional authors'
% in the \additional authors block, viz.
%\additionalauthors{}
\date{\today}
% Just remember to make sure that the TOTAL number of authors
% is the number that will appear on the first page PLUS the
% number that will appear in the \additionalauthors section.

\maketitle
\begin{abstract}
%How can we best find project changes that most improve project estimates? Prior solutions to this problem required the use of standard  software process models that may not be relevant to some new project.  Also, those prior solutions  suffered from limited  veri?cation (the  only way to assess the results of those studies was to run the recommendations back through the standard process models).  
 
%Combining case-based reasoning and contrast set learning, the "W"
%system  requires no underlying parametric model. Hence, it is widely
%applicable (since there is is  no requirement for the data sets to
%be in the format required by  the standard software process models).
%Also, W ?s results can be veri?ed (using hold-out sets). For example,
%in the experiments reported here, W found changes to projects that
%greatly reduced estimate median and variance by up to 95/% and 83/%
%(respectively).

%Over the course of about 2 semesters, research related to effort estimation within the WVU AI group has transitioned from the modeling based approach, shown in STAR and NOVA\cite{elrawas08, me09i}, to a case based reasoning (CBR) approach in a tool we called \textit{"W - The Decider"}. In a similar manner to its predecessors, \textit{W} is a planning tool for software systems aimed at reducing the effort needed for development. Unlike its predecessors however, it does not require model calculations in order produce the effort estimates; rather it utilizes a project case base to determine those estimates. In this document, we will present the motivation behind \textit{W}. We will also attempt to document what makes \textit{W}, including the project case bases used, the file hierarchy, in addition to describing the algorithm itself as well as the methods of use.


%% A category with the (minimum) three required fields
%\category{H.4}{Information Systems Applications}{Miscellaneous}
%%A category including the fourth, optional field follows...
%\category{D.2.8}{Software Engineering}{Metrics}[complexity measures, performance measures]

%\terms{CBR, Agents}

%\keywords{}


How can we best find project changes that most improve project
estimates? Prior solutions to this problem required the use of
standard  software process models that may not be relevant to some
new project.  Also, those prior solutions  suffered from limited
verification (the  only way to assess the results of those studies
was to run the recommendations back through the standard process
models).

Combining case-based reasoning and contrast set learning, the {\W}
system  requires no underlying model. Hence, it is widely
applicable (since there is  no need for data to
conform to some software process models).
Also, {\W}'s results can be verified (using hold-out sets). For example,
in the experiments reported here, {\W} found changes to projects that
greatly reduced estimate median and variance by up to 95\% and 83\%
(respectively).


 \end{abstract}
\section{Introduction}
Existing research in effort estimations focuses mostly  on deriving
estimates from  past project data using (e.g.) parametric models~\cite{boehm00b}
or case-based reasoning (CBR)~\cite{shepperd97} or genetic algorithms~\cite{Li2009}.  That research is curiously
	silent on how to change  a project in order to, say, reduce development
	effort. That is, that research reports {\em what is} and not
{\em what should  be changed}.

Previously~\cite{elrawas08,me09a,me09f,me07f}, 
we have tackled this problem using  STAR/NOVA, a suite of
AI search algorithms
that explored the input space of standard software process models
to find project options that most reduced the effort estimates.
That approach had some drawbacks including (a)~the dependency of
the data to be in the format of the standard process models, (b)~the implementation complexity
of the Monte Carlo simulator and the AI search engines, and (c)~the
lack of an  independent verification module (the only way to assess
the results  of those studies was to run the recommendations back
through the standard process models).

This paper describes ``{\W}'', a simpler, yet more general solution to the
problem of finding project changes that most improves project
estimates.  Combining  case-based reasoning
and contrast set learning,
{\W}
requires no underlying parametric
model.
Hence, {\W} can be applied to more data
sets since there is is no requirement for the data sets to be in the
format required by the standard software process models. For example, 
this paper explores five data sets with {\W}, three of which cannot be processed
using STAR/NOVA.

{\W} is simpler to implement and easier to use than STAR/NOVA, requiring hundreds of lines of the scripting language AWK rather than thousands of lines of C++/LISP.
For example, we describe below a case
study that finds a loophole in Brooks's Law (``adding manpower [sic] to a late project makes it later'').
Using {\W}, that study took  three days which included the time to build {\W}, from scratch. 
An analogous study, based on state-of-the-art model-based AI techniques,
took two years.

Also, the accuracy of STAR/NOVA
is only as good as the underlying model (the USC COCOMO suite~\cite{boehm00b}). 
{\W}'s results, on the other hand, are verified using  hold-out sets on real-world data.
In the experiments reported below, we show that {\W} can find changes to projects
that greatly reduce estimate median and variance by up to 95\% and
83\%,  respectively. 

Finally, the  difference between {\W}, which finds what to change in order to improve
an estimate, and a
standard case-based effort estimator, which only generates estimates, is very
small. Based on the this experiment, we advise augmenting standard CBR tools
with modules like 
the planning sub-systems in
{\W}.

The rest of this paper is structured as follows.
After some background notes on effort estimation and STAR/NOVA, we describe the general 
framework for case-based reasoning. The {\W} extension to CBR is then described (contrast
set learning over the local neighborhood), using  a small example. This is followed by
fourteen case studies, one with Brooks's Law, and thirteen others.
Our conclusion will discuss when {\W} is preferred over STAR/NOVA.

\section{Background}

\subsection{Why Study Effort Estimation?}

Generating (and
regenerating) project effort estimates is an important and  continuous process
for project managers.  Not only do good estimates allow the better use of resources,
but by reviewing and improving their estimation process, a
software company can learn and improve from their past experience.

Sadly, we often get estimates wrong.
Consider the  NASA's Check-out Launch Control
System, which was canceled when the initial estimate of \$200 million
was overrun by an {\em additional} \$200M \cite{CLCS03}.  This case is
not unique, despite the significant effort put into designing more
accurate estimation models. It has been reported that many predictions
are wrong by a factor of four or more \cite{boehm81,kemerer87}.


%
%The field of software development effort estimation is one that has been researched and studied both in academia and industry (references). From a business point of view, there is always a need for the ability to determine the cost of software development project. This is needed not only for managing costs, but also in order to enable project managers to properly plan the development process and allocate resources accordingly. 

In order to conduct software effort estimation, it is standard practice
to use
 models to estimate effort.
Many software process models have emerged aiming to achieve that task, and
there has not emerged a single standardized model that is widely
used by the software engineering industry. There several reasons
for this including {\em generality}, {\em data islands}
and {\em instability}.
 Software models may not be {\em general} so it can be inappropriate
to apply a software model learned in one environment one to another.
Also, many companies
prefer to keep cost related data confidential.
This {\em data island} effect has also contributed
to the fragmentation of the field by companies preferring to build private
models rather than using publicly available models. This multiplicity
of software effort models has lead to scarcity of publicly available,
local data needed for model based effort estimation.
Without sufficient data to build, audit, and tune models, the predictions
generated by these models may be highly {\em unstable}.
Baker~\cite{baker07} reports a study that learned values for
the $(a,b)$ (linear,exponential) constants in Boehm'
COCOMO software process model~\cite{boehm81}. The study was repeated 100 times, each time
selecting from a random sample of 90\% of the project data. 
The learned values for $(a,b)$ exhibited an alarming variance:
\begin{equation}\footnotesize\label{eq:ab}
\left( 2.2 \le a \le 9.18 \right) \wedge \left(0.88 \le b \le 1.09\right)
\end{equation} 
Such large variations make it hard to understand the effects
of changing project options.  Suppose some proposed change  doubles
productivity, but $a$ moves from 9 to 4.5.  The improvement resulting
from that change would be obscured by the tuning variance.
\subsection{Handling Large Variances and Uncertainty}
The process simulation community (e.g. Raffo~\cite{raffo05c}) studies
elaborate software process models.
While such models
offer a detailed insight into an organization, the effort required
to tune them is non-trivial. For example, Raffo spent two years
tuning one such model to one particular site~\cite{raffo95}. Slow
tuning time means that models will exhibit large variances for
much of their lifetime.

These large variances defeat standard decision making algorithms.
For example, a standard tool in sensitivity analysis~\cite{saltelli00}
is to partially
differentiate the equations of a model, then explore the coefficients
on the partials. Large variances like \eq{ab} guarantee that
any such gradient analysis will yield highly variable results.

Miller \cite{miller02} reports that {\em feature selection}  can reduce
model prediction variance. While he was talking specifically
about least squares regression, the more general point is that
the fewer the variables, the less the contribution
of variable variance to output variance. 
Inspired by Miller, we conducted feature selection
experiments with effort data sets~\cite{me05c,me05d,me06d},
with disappointing results. As predicted by Miller, variance
is decreased when, say, 20 attributes are reduced to 10. But note
in Baker's study that large variances persist for effort data, even
after reducing the number of variables to two. Clearly, we need
to look further than just feature selection.

An alternative to feature selection is {\em case selection}, where
data sets of size $D$ are replaced with
a smaller data set of {\em prototypes}.
The smaller the data set, the fewer the values and (hopefully),
the smaller the variance.
{\em Prototype generation} should not be confused with nearest neighbor methods:
the latter is run on a per-query basis while the former is run once as a pre-processor
to all subsequent inferencing.
The art of prototype generation is to find
or generate a set of representative
examples that best represents and replaces the training cases. Typically, prototype
generation removes most of the training data. 
For example,
Chang's prototype generators~\cite{chang74} replaced training sets
of size \mbox{$T=(514,150,66)$} with prototypes of size \mbox{$N=(34,14,6)$}  (respectively).
That is,  prototypes may be as few as $\frac{N}{T}=(7,9,9)\%$ of the original
data. 
The problem with prototype generation is that it can be very slow.
\cite{Li2009} discusses genetic algorithms that combine feature and case
selection. Dr. Li was kind enough to share his code.
 Using that system, we have learned that searching the
$2^D$ space of possible cases
can be very slow.
A similar result was reported by Kirsopp and
Shepperd~\cite{kirsopp02}, who found that case selection was
only practical for very small data sets.

If we cannot remove variance, we must deal with the uncertainties
it presents.  Much of the related work on uncertainty in software
engineering uses a Bayesian analysis.  For example, Pendharkar
et.al.~\cite{pendharkar05} demonstrate the utility of Bayes networks
in effort estimation while Fenton and Neil explore Bayes nets in
defect prediction~\cite{fenton99}. We take a different approach
here due to the simplicity of our implementation (see below).
 
Of all the literature, we found Search-Based Software Engineering
(SBSE) ~\cite{harman04} to be closest to this work.  SBSE
uses optimization techniques from operations research and meta-heuristic
search (e.g. simulated annealing and genetic algorithms) to hunt
for near optimal solutions to complex and over-constrained software
engineering problems.  The SBSE approach can and has been applied
to many problems in software engineering (e.g. requirements
engineering~\cite{jalali08})
 but most often in the field of software testing~\cite{andrews07}.

\subsection{STAR and NOVA} \label{star}
The SBSE literature
inspired us to try simulated annealing to search the
what-ifs associated with \eq{ab}. This lead to the
STAR system~\cite{me07f,elrawas08}. NOVA was a generalization of STAR
that included simulated annealing and other search engines~\cite{me09a,me09f}.

STAR/NOVA handled model variance by finding conclusions that were
stable across the space of possible tunings.
This analysis assumed
that, for a mature effort estimation model, the range of possible
tunings was known (this is the case for models like COCOMO).  
For such models, it is possible for the AI search engines to
find conclusions that hold across the space of all tunings.

STAR and NOVA constrain project options $P$ but not the tuning
options $T$. Hence, their  recommendations  contains
subsets of the project options $P$ that most improve the score,
despite variations in the tunings $T$. This approach meant we could
reuse COCOMO models requiring using local tuning data. The following
is a description that briefly presents the operation of STAR and
NOVA:


\be
\item {\em SAMPLE:} We sample across the ranges of all the attributes in the model $n_1$ times. Most of the time we sample randomly across the range, with some heuristics that allow us to concentrate more on the extremes of the range.
\item {\em DISCRETIZE:} The data seen in the $n_1$ samples is then discretized into $D=10$ bins. Equal frequency bins were used.
\item {\em CLASSIFY:} The top $n$\% projects are classified as {\em best} or {\em rest}.
\item {\em RANK:} The ranges are then ranked in increasing order using Support-Based Bayesian Ranking.
\item {\em PRUNE:}  STAR runs $n_2$ experiments with the models where the top ranked ranges $1..X$ ranges are pre-set and the remaining ranges can be selected at random. 
\item {\em REPORT:} STAR returns the $1..X$ settings that optimize the best for the fitness function. These settings are determined by iterating back from the minimum point achieved towards the first point that is statistically similar to the minimum point.
\ee
%Note that this approach is completely dependent on some  underlying
%software process model (in our case, the COCOMO models):
%\bi
%\item 
%The conclusions reached by STAR/NOVA are only as good as the model
%used by the AI search engines.
%\item
%\ei
%\input{star-winloss}

%Even given the limitations of this approach, we were able to produce
%very good results when it came to reductions in effort projections
%for COCOMOII based projects as illustrated in \fig{star-perc}. We
%also demonstrated, as a sanity check, that modifying projects based
%on recommended policies is clearly statistically better than keeping
%projects as is. This is demonstrated in \fig{star-winloss}, which
%represents a quartile chart, along with Mann-Whitney ranking, showing
%use of STAR vs. ``doing nothing''.
%
%Having presented our previous stochastic approach, we will proceed to briefly explain Case Based Reasoning (CBR) that avoids the pitfalls of our previous stochastic approach.
%

In practice, STAR/NOVA approach was very effective. \fig{compare1} shows the
large effort reductions found by STAR in three out of 
four cases presented at  ASE'09. It is insightful to reflect about
STAR/NOVA's failure to find large
reductions in the fourth case study ({\em nasa93 osp2}). In this project,
management had already fixed most of the project options. STAR/NOVA failed,
in this case, since there was  very little left  to try and change.
This fourth case study lead to one of the lessons learned of STAR/NOVA:
apply project option exploration tools as early as possible in the lifecycle
of a project. Or, to say that more succinctly: {\em if you fix everything,
there is nothing left to fix}~\cite{me07g}.
 
\input{star-percentages}
While a successful prototype, STAR/NOVA has certain drawbacks:
\bi
\item {\em Model dependency:} 
STAR/NOVA requires a model to calculate (e.g.) estimated effort.
In order to do so, we had to use some software process
models to generate the estimates. Hence, the conclusions reached by STAR/NOVA
are only as good as this model. 
That is, if a client doubts the relevance of those models, then the conclusions
will also be doubted.
\item {\em Data Dependency:}
STAR/NOVA's AI algorithms explored an underlying software process model.
Hence, it could only process project data in a format compatible with the
underlying model. In practice, this limits the scope of the tool.
\item {\em Inflexibility}: It proved to be trickier than we thought
to code up the process models, in a manner suitable for Monte Carlo simulation. By our count,
STAR/NOVA's models required 22 design decisions to handle certain special
cases\footnote{E.g. one user required the following modification:
do not increase automatic tools usage without increasing  analyst capability.
}. Lacking guidance from the literature, we just had to
apply ``engineering judgment'' to make  those decisions. While we think we made the right
decisions, we cannot  
rigorously justify them.
\item {\em Performance}: Our stochastic approach conducted several tens
of thousands of iterations to explore the search space, with several
effort estimates needed calculated for each iteration. This resulted
in a performance disadvantage.  \item {\em Size and Maintainability}: Due
to all the above factors, our code base proved
difficult to maintain.
\ei
While there was nothing in principle against applying our techniques
to other software effort models, we believe that the limiting
factor on disseminating our technique is the complexity of
our implementation. As partial evidence for this, we
note that in the three years since we first
reported our technique~\cite{me07f}:
\bi
\item
We have only coded one
set of software process models (COCOMO), which inherently limited the scope of our study.
\item
 No other research group
has applied these techniques.
\ei

Therefore, rather than elaborate a complex code base,
we now explore a different option,
based on Case Based Reasoning (CBR).
This new approach had no model restrictions (since it is
does not use a model) and can accommodate a wide range of data
sets (since there are no restrictions of the variables that can
be processed). 
\input{cbr}
%Located in the projects folder of the \textit{W} file hierarchy, the project files are defined in arff format similar to the case bases (\fig{nasaproj} is one such example of this format). Unlike the case bases, each project is define by a set of controllable and uncontrollable attributes. Within \textit{W}, only controllables are explored. This practice makes sense since project managers are only interested in recommendations for attributes that they are able to control. The controllable attributes within a single project can either include the whole range for that attribute within the dataset, or can be restricted to a subset of the possible attribute range. Note that a project needs to have at least one defined controllable attribute range for \textit{W} to evaluate.
%
%Exploring the project files, is it apparent that the naming scheme follows the following format: \textit{``case base''.``project name''}. The first part of the name shows the case base that this project belongs to. This not only determines the case base, but also the model attributes that \textit{W} will be evaluating. The second part, the project name, is simply a designation for this particular project belonging to a case base. 
%
%In addition to the above characteristics of the projects used within \textit{W}, it is important to note one more characteristic. There are two main groups of projects:
%
%\bi
%\item Projects that are manually defined to enable \textit{W} to explore a case base. Generally, projects under this category include with generic names such as ``proj*''. Most of the defined projects fall under this category.
%\item Projects and project templates that are based on real world specifications. This group includes the NASA projects such as OSP and others shown in \fig{cases}.
%\ei
%

%The following is a brief description of those NASA projects presented in \fig{cases}:
%\bi
%\item {\em Flight} is a general description of flight software at NASA's Jet Propulsion Laboratory.
%\item {\em Ground} is a general description of ground software at NASA's Jet Propulsion Laboratory. 
%\item {\em OSP} is a specific flight system: the GNC (guidance, navigation, and control)
%component of NASA's 1990s {\em Orbital Space Plane}; 
%\item {\em OSP2} is a later version of OSP.
%\ei
%
%In the next section, we will present \textit{W} and how it operates. We will also present the general organization of the \textit{W} code base, as well as show an example of \textit{W} operation.
%w
\section{From CBR to {\Large {\W}}}

A standard CBR algorithm reports the median class value of some local neighborhood.
The {\W} algorithm treats the local neighborhood in a slightly different manner:
\bi
\item
The local neighborhood is divided into  {\em best} and {\em rest};
\item
A {\em contrast set} is learned that most separates the regions (contrast
sets contain attribute ranges that are common in one region,
but rare in the other).
\item
{\W} then searches for  a subset of the contrast set that best selects
for (e.g.) the region with lower effort estimates.
\ei
The rest of this section details the above process. \subsection{Finding
Contrast Sets}
Once a contrast set
learner is available, it is a simple matter to
add {\W} to CBR. 
{\W} finds contrast sets using a 
greedy search, where candidate contrast sets are ranked by the 
log of
the odds ratios.
%\begin{figure}[h]
%\begin{center}
%\includegraphics[width=3.5in]{nomnom.png}
%\end{center}
%\label{fig:nom}
%\caption{Nomograms modeling survival odds on the HMS Titanic.
%From \cite{mozina04}. For ease of readability,
%the nomogram scores are top are normalized 0 to max(LOR), 0 to 100.
%}\label{fig:titanic}
%\end{figure}
Let some attribute range $x$ appear at frequency $N_1$ and $N_2$ in two
regions of size $R_1$ and $R_2$. Let the $R_1$ region be the preferred goal
and $R_2$ be some undesired goal.
The log of the odds ratio, or LOR, is:
\[
LOR(x) = log\left(\frac{N_1 / R_1}{N_2 / R_2}\right)
\]
Note that when $LOR(x)=0$, then $x$ occurs with the same probability in each region
(such ranges are therefore not useful for selecting on region or another). 
On the other hand, when $LOR(x)>0$, then $x$  is more common in the preferred
region than otherwise.  These LOR-positive ranges are candidate members of the
contrast set that selects for the desired outcome.

It turns out that, for many data sets, the LOR values for all the ranges
contain a small number of very large values (strong contrasts) and a large
number of very small values (weak contrasts).  The reasons for this 
distribution do not concern us here (and if the reader is interested
in this {\em master-variable} effect, they are referred to~\cite{me07d,me03l}).
What is relevant is that the
LOR can be used to rank candidate members
of a contrast set. {\W} computes the LORs for all ranges, then
conducts experiments applying the top {\em i-th} ranked ranges.

For more on LOR, and their use for  multi-dimensional
data, see~\cite{mozina04}.

%For example, a nomogram describing who survived and who died on the
%Titanic  is shown in \fig{titanic}.  Of 2201 passengers on
%Titanic, 711 (32.3\%) survived. That is 
%$P(survival=yes) =\frac{711}{2201}=32.3\%$.
%The nomogram shows how to increase that probability.
%The contribution of each LOR is measured as a point score (topmost
%axis in the nomogram), and the individual point scores are summed
%to determine the probability of survival (bottom two axes of the
%nomogram). The nomogram  shows the case when we know that the
%passenger is a child; this score is slightly less than 50 points,
%and increases the posterior probability to about 52\%. If we further
%know that the child traveled in ?rst class (about 70 points), the
%points would sum to about 120, with a corresponding probability of
%survival of about 80\%.
%of a contrast set;
%\item  In that ranking, we can expect most benefit from the first few ranges
%with the larger LORs.
%\ei
%\begin{equation}\label{eq:lor2p}
%\[
%$P(C) = \left(1+e^{-log\left(\frac{p}{1-p}\right) - LOR}\right)^{-1}$
%\]
%\end{equation}
%
%relate to the {\em master-variable effect }~\cite{me03e} in which
%a small number of variables 
%
%Besides enabling prediction, the nomogram reveals the structure of
%the model and the relative influences of attribute values on the
%chances of surviving.  For the Titanic data set, gender is an
%attribute with the biggest potential in?uence on the probability
%of survival: being female increases the chances of survival the
%most (100 points), while being male decreases it (about ?30 points).
%The corresponding line in the nomogram for this attribute is the
%longest. Age is apparently the least in?uential, where being a child
%increases the probability of survival.  Most lucky were also the
%passengers of the ?rst class for which ? considering the status
%only ? the probability of survival was much higher than the prior.
%
%
%Nomograms use the simple Naive Bayesian rule to determine whether
%a given attribute will belong to the instance of the "best" neighbors.
%By taking the log of the odds ratio of an attribute appearing in
%best compared to rest, we are given an individual score for that
%attribute. That score allows us to determine what the probability
%of a particular attribute or combination of attributes occurring
%in best or rest. By taking the log, these scores have the unique
%property of obeying the property of addition.
%
%\begin{equation}
%odds = \frac{P(c)\prod_iP(a_a\vert c)}{P(\bar{c}}
%\end{equation}

%In figure~\ref{fig:nom} the nomograms for survival rates of the RMS Titanic passengers are presented. Each bar represents a different attribute of a passenger, and the labeled marks along that bar represent the attribute values. By adding up the numeric values seen above each attribute value, you can determine how strongly each attribute value predicts for an outcome of survival. After adding these "points" together, you can calculate the Bayesian probability of survival by converting "Total Points" to P(yes). As shown in figure~\ref{fig:nom}, when considering no other attributes a child has a survival chance of slightly above 50\%.

%For ``W,'' nomograms represent another means to rank attributes with the future potential to combine attribute scores for ranking paired attributes.

\subsection{The Algorithm}
CBR systems input a query $q$ and a set of cases. They return the subset
of cases $C$ that is relevant to the query.
In the case of {\W}:
\bi
\item
Each case $C_i$ is an historical record of one software projects, plus the development
effort required for that project.  Within the case, the project is described
by  a set of attributes which we assume have been discretized into a small
number of discrete values (e.g. analyst capability $\in \{1,2,3,4,5\}$ denoting
very low, low, nominal, high, very high respectively). 
\item
Each query $q$ is a set of constraints describing the particulars of a project.
For example, if we were interested in a schedule over-run
for a complex, high reliability projects that
have only minimal access to tools, then 
those constraints can be expressed in the syntax of \fig{nasaproj}.
\ei
{\W} seeks $q'$ (a change to the original query)
that finds another set of
cases $C'$ such that the median effort values in $C'$ are less than that of $C$ (the cases found by $q$).
{\W} finds $q'$ by first dividing the data into two-thirds training and one-third testing.
{\em Retrieve} and {\em reuse} are applied to the training set, then {\em revising}
is applied to the test set.
	\be
	\item {\em Retrieve}: The initial query $q$ is used
to find the $N$ training cases nearest to $q$ using a Euclidean
distance measure where all the attribute values are normalized from 0 to 1.
 \item
{\em Reuse} (adapt): The $N$ cases are sorted by effort and divided into
the $K_1$ best cases (with lowest efforts) and $K_2$ rest
cases. For this study, we used $K_1=5, K_2=15$.
Then we seek  the contrast
sets that select for the $K_1$ best cases with lowest estimates.
All the attribute ranges that the user has marked as ``controllable'' are scored and sorted by LOR.
This sorted order $S$ defines a set of candidate $q'$ queries
that use the first {\em i-th} entries in $S$:
\[
q_i' = q \cup S_1 \cup S_2 ... \cup S_i
\]
\ee
\input{datasets}
Formally, the goal of {\W} is find the smallest $i$ value such
$q_i'$ selects cases with the least median estimates.

According to \fig{cbr}, after {\em retrieving} and {\em reusing} comes
{\em revising} (this is the ``verify'' step).
When revising $q'$, {\W} prunes away irrelevant ranges as follows:
	\be
	\item Set $i=0$ and $q_i'=q$ 
	\item Let $Found_i$ be  the test cases consistent with  $q_i'$ (i.e. that
do not contradict any of the attribute ranges in $q_i'$).
	\item Let $Effort_i$ be  the median efforts seen in $Found_i$.
	\item If $Found$ is too small then terminate (due to over-fitting). 
After Shepperd~\cite{shepperd97}, we
terminated for $|Found|<3$. 
	\item If $i>1$ and $Effort_i < Effort_{i-1}$, then terminate (due to no improvement).
	\item Print $q_i'$ and $Effort_i$.
    \item Set $i=i+1$ and $q_i'= q_{i-1} \cup S_i$ 
	\item Go to step 2.
	\ee
On termination, {\W} recommends changing a project according to the set $q'-q$.
For example, in \fig{nasaproj}, if $q' -q$ is $rely=3$ then this treatment recommends
that the best way to reduce the effort this project is to 
reject $rely=4\;or\;5$.


One useful feature of the above loop is that it is not a 
black box that offers a single ``all-or-nothing''
solution. Rather it generates
enough information for a user to
make their own cost-benefit tradeoffs.
In practice, users may not accept all the treatments
found by this loop. Rather, for pragmatic reasons, they may only
adopt the first few
$S_i$ changes seen in the first few rounds of this loop. Users might adopt this strategy
if (e.g.) they have limited management control
of a project (in which case,  they may decide to apply just the most influential $S_i$ decisions).

Implementing {\W}  is simpler than the STAR/NOVA approach:
\bi
\item
Both  NOVA and STAR contain a set process models for predicting
effort, defects, and project threats as well as  Monte Carlo routines to randomly
select values from known ranges. STAR and NOVA implement simulated annealing while
NOVA also implements other search algorithms such as A*, LDS, MAXWALKSAT, beam search, etc.
STAR/NOVA are 3000 and 5000 lines of C++ and LISP, respectively.
\item {\W}, on the other hand, is a 300 line AWK script.
\ei
Our pre-experimental suspicion was that {\W} was too simple and would need extensive enhancement.
However, the results shown below suggest that, at least for this task, simplicity can suffice (but see
the future work section for planned extensions).

Note that
{\W} verification results are more rigorous than those of STAR/NOVA.
{\W} reports results on data that is external to its deliberation process
(i.e. on the test set).
STAR/NOVA, on the other hand, only reported the changes to model output
once certain new constraints were added to the model input space. 

\section{Data}
Recall that a CBR system takes input a query $q$ and cases $C$.
{\W}
has been tested using  multiple queries on the data sets of \fig{data}.
These queries and data sets are described below.
\subsection{Data Sets}
As shown in \fig{data}, our data includes:
\bi
\item The standard public domain COCOMO data set (Cocomo81);
\item Data from NASA;
\item Data from the International Software Benchmarking Standards Group (ISBSG);
\item The Desharnais and Maxwell data sets;
\ei
Except for ISBSG, all the data used in this study is 
available at \protect\url{http://promisedata.org/data} or from the
authors.

Note the skew of this data (min to median much smaller
than median to max). Such asymmetric distributions complicate
model-based methods that use Gaussian approximations to
variables.  

There is also
much divergence in the attributes used in our data:
\bi
\item 
While our data include effort values (measured in terms of months or hours),
no other feature is shared by all data sets.
\item
The COCOMO and NASA data sets all use the attributes defined by Boehm~\cite{boehm81}; e.g.
analyst capability, required software reliability, memory constraints, and use of software tools.
\item
The other data sets use a variety of attributes such as the number of data model entities,
the number of basic logical transactions,  and number of distinct business units serviced.
\ei
This attribute divergence is a significant
problem for model-based methods like STAR/NOVA since those systems
can only accept data that conforms to the space of attributes
supported by their model. 
For example,  this study uses the  five data sets listed in \fig{nasaproj}.
STAR/NOVA can only process two of them (coc81 and nasa93).

CBR tools like {\W}, on the other hand, avoid
these two problems:
\bi
\item
{\W} makes no assumption about the distributions of the variables.
\item
{\W} can be easily applied to any attribute space (caveat: as long
but there are some dependent variables).
\ei
\begin{figure}
\scriptsize
\begin{verbatim}
@project example
@attribute ?rely 3 4 5 
@attribute tool  2 
@attribute cplx 4 5 6 
@attribute ?time 4 5 6
\end{verbatim}
\caption{{\W}'s syntax for describing
the input query $q$. Here,  all the values run 1 to 6.
$4\le cplx \le 6$ denotes projects with above average complexity.
Question marks denote what can be controlled- in this
case, $rely,time$ (required reliability and development time)}
\label{fig:nasaproj}
\end{figure}
\subsection{Queries}
\fig{nasaproj} showed an example of the
{\W} query language:
\bi
\item The idiom ``{\em @attribute name range}`` defines the range of interest
for some attribute ``name''.
\item If ``{\em range}'' contains multiple values, then this represents a disjunction
of possibilities.
\item If ``{\em range}'' contains one value, then this represents a fixed decision
that cannot be changed.
\item
 The idiom ``{\em ?x}''
denotes a controllable attribute (and {\W} only generates contrast sets from these
controllables).  
Note that the ``{\em range}''s defined for ``{\em ?x}''  must contain more than
one value, otherwise there is no point to making this controllable.
\ei
\section{Example}
\fig{exrun} shows {\W} running on the (dataset,query) of (coc81,$osp$).
The osp query comes from our contacts at the Jet Propulsion Laboratory and describes 
the constraints that apply to the flight guidance system of the Orbital Space plane
(see \fig{osp}).

The \textbf{training results} are shown on lines 5 to 8. These are the
the $S_i$ scores on all the ranges with a positive LOR.
Note that one range has an outstandingly high LOR; $stor=3$ has an LOR or 0.41
while all the rest are under 0.1. That is, we should expect most of the benefit
from applying just one range ($stor=3$).

The \textbf{baseline effort estimates} of $q_0$ are on
lines 10,11. These are all the efforts of all the cases selected by the osp query.
These efforts are summarized on lines 13,14 (the median effort is 313.5).

The \textbf{testing results} are  after line 18. In this example, $q_1$ is
$q_0$ (osp) plus the top-ranked attribute range ($stor=3$). The effects
of $q_1$ are on lines 19. Now, only five cases are selected with a
median effort of 55. 
Testing stops at line 19 since applying the next ranges
did not improve the median or spread results.

As to performance measures, if
$Improvement=\frac{initial - final}{initial}$, then
the $median$ $improvement$ of \fig{exrun} is $\frac{313-55}{313}=82\%$.
Also, let the  $spread$ be the $75th-25th$ percentile interval (a non-parametric measure of estimate
variance).
The spreads of \fig{exrun} are, for $q_0$,
$653-52=601$ and, for $q_1$, $240-50=190$. 
Hence,  the  {\em spread\;improvement} was $\frac{601-190}{601}=68\%$.
Reducing {\em both}  median and spread are useful since the former relates to development
cost and the latter relates to how much we can trust and estimate (the smaller the
spread, the more we can trust it).
\begin{figure}
\scriptsize
\begin{verbatim}
 1	historical data : coc81
 2	new project(s)  : osp
 3	     #n	score	range
 4	------	-----	--------------
 5	     1	 0.41	stor = 3
 6	     2	 0.09	acap = 5
 7	     3	 0.00	cplx = 4
 8	
 9  q_0:	
10	9 15 40 41 50 55 61 79 83 240 387 
11	423 523 539 605 702 1063 1600 2040 6400 
12	 
13	                  25%	50%	   75%
14	  Baseline:       52.5	313.5  653.5
15	
16	Results of applying the  top n-th ranges 
17	found during training
18	
19	q_1: stor=3 : {15 50 55 240 702} (median,spread)= 55,190
\end{verbatim}
\caption{Running (coc81,osp).}
\label{fig:exrun}
\end{figure}
\begin{figure}[!t]
\scriptsize
\begin{verbatim}
@project osp
@attribute data 3 
@attribute rely 5 
@attribute ?team 2 3 
@attribute pcap 3 
@attribute ?stor 3 4 5 
@attribute ?acap 2 3 
@attribute ?aexp 2 3 
@attribute ?tool 2 3 
@attribute ?sced 1 2 3 
@attribute ?cplx 5 6 
@attribute kloc 75 80 90 95 100 105 110 115 120 125
\end{verbatim}
\caption{The $osp$ query query says, in part, that system size is between 75 and 125 $kloc$;
that required reliability $rely$ is very high; but analyst capability $acap$ is only
fair to medium. For a full description of this query, see~\cite{me07f}.}
\label{fig:osp}
\end{figure}

\section{Case Studies}
\subsection{Case Study \#1: Brooks's Law}
This section applies {\W} to Brooks's Law.
Writing in the 1970s~\cite{brooks75}, Brooks noted
that
software production is a very human-centric activity
and managers need to be aware
of the human factors that increase/decrease productivity. For example, a common practice
at that time at IBM was to solve deadline problems by allocating more resources.
In the case of programming, this meant adding more programmers to the team. Brooks argued
that this was an inappropriate response since, according to Brooks's law ``adding manpower [sic]
to a late software project makes it later''.
The reason for this slowdown is two-fold:
\bi
\item
The more people involved the greater the communication
overhead. While this is certainly an issue if all parts of the software system are accessible to all other
parts, with an intelligent module design, this first issue can be mitigated. 
\item
The second issue is more fundamental. Software construction is a complex activity. Newcomers to a project
suffer from inexperience in the tools, the platform, the problem domain, etc. 
\ei
The query of \fig{brookslaw} models this second issue. In this query, all the experience attributes have been
set to their lowest value ($apex$, $plex$, $ltex$ are analyst experience, programmer language experience, and language
and tool experience, respectively).  The remaining attributes are all controllable (as denoted by the ``?'' in front of each one) and are allowed to move over their full range.
\begin{figure}
\scriptsize
\begin{verbatim}
@project brooks
@attribute ?prec 1 2 3 4 5 6
@attribute ?flex 1 2 3 4 5
@attribute ?resl 1 2 3 4 5
@attribute ?team 1 2 3 4 5
@attribute ?pmat 1 2 3 4 5
@attribute ?rely 1 2 3 4 5
@attribute ?data 2 3 4 5
@attribute ?cplx 1 2 3 4 5 6
@attribute ?ruse 2 3 4 5 6
@attribute ?docu 1 2 3 4 5
@attribute ?time 3 4 5 6 
@attribute ?stor 3 4 5 6
@attribute ?pvol 2 3 4 5
@attribute ?acap 1 2 3 4 5
@attribute ?pcap 1 2 3 4 5
@attribute ?pcon 1 2 3 4 5
@attribute apex 1
@attribute plex 1
@attribute ltex 1
@attribute ?tool 1 2 3 4 5
@attribute ?site 1 2 3 4 5 6
@attribute ?sced 1 2 3 4 5
@attribute kloc 0.9 2.2 3 [snip]  339 350 352 423 980
\end{verbatim}
\caption{The $brookslaw$ query.}\label{fig:brookslaw}
\end{figure}

For a (dataset,query) of (nasa93,$q=brookslaw$), {\W} returns\[
q' = q \cup \left(data=2\right)\]
That is, {\W} is recommended setting the database size to its lowest value. 
Databases are used to store program and data elements. In effect, {\W} is recommending
reigning in the scope of the project. The recommendation can be paraphrased as follows:
\begin{quote}
{\em If the project is late, and you add more staff with less experience, you can still
finish on time if you decrease the scope of the project.}
\end{quote}

\fig{brook} shows the effects of this recommendation. The {\em AsIs} row shows the median and spread
of the effort values in nasa93. The {\em ToBe1} row shows the effect of Brooks's Law. In the subset
of the data consistent with $aexp=plex=ltex=1$, the median effort has nearly doubled. 
The {\em ToBe2} row shows the impact of {\W}'s recommendation: the project will now finish in nearly
the the time as the {\em AsIs} row, and the spread is greatly reduced.
\begin{figure}
\center
\begin{tabular}{l|r|r}
Treatment              & median & spread \\\hline
 AsIs = Nasa93          & 225   &670 \\ 
 ToBe1 = $nasa93 \cup q$ & 380 & 680\\
 ToBe2 = $nasa93 \cup q'$ & 220 & 290 \\
\end{tabular}
\caption{Effort estimates seen in different treatments for the Brooks' Law Experiment.}\label{fig:brook}
\end{figure}

One of the reasons we are exploring {\W} is the simplicity of the implementation.
In this regard, it is useful to compare our results on Brooks's Law to other researchers.
Brooks's Law is a well-researched effect and other researchers have
found special cases where the general law does not hold. For example,
using sophisticated qualitative reasoning techniques, Zhang et
al.~\cite{zhang06} found their own loopholes in Brooks's Law.
One of us (Keung) worked on site with the Zhang team and reports that the Brooks analysis was the main result
of a two year masters graduate thesis. 
In contrast, writing {\W} took three days and 
the specific analysis of Brooks's Law took
took twenty minutes from first posing the question, to graphing the output.

\subsection{Thirteen More Case Studies}
Apart from the Brooks' Law experiment, we have tested $W$ on thirteen other case studies:
\bi
\item For the ISBSG data set, we used our recent experience to describe
the constraints suitable for a stand-alone or client server system
(denoted {\em stdalone} and {\em clientsrv}).
\item
For the Desharnais data set, we posed queries
representing:
\bi
\item 
$(s,m,l)$ 
denotes (small, medium,large) projects;
\item $(mngr, team)$ denotes (manager,team) experience being low.
\ei
For example, \fig{desh} shows the Desharnais-team-m query.
\item For the Cocomo and NASA data sets, we used our contacts at the Jet Propulsion
Laboratory to write queries  describing (a)~$osp$ (see above); 
(b)~the second version of that system called $osp2$;  as well as (c)~generic {\em flight} and (d)~{\em ground} systems.
\item
Lacking direct experience with the Finnish financial system, we could
not pose specific queries to the Maxwell dataset. Instead, we made half
the attributes controllable and used that for the Maxwell query (see \fig{maxwell}).
\ei
\begin{figure}
\scriptsize
\begin{verbatim}
@project desharnais-team-m
@attribute ?TeamExp -1 0 1
@attribute ?ManagerExp 3 4 5 7
@attribute PointsAjust 302 397 697
\end{verbatim}
\caption{The $desharnais-team-m$ query selects for medium sized projects being developed
by 
teams with low experience.}\label{fig:desh}
\end{figure}
\begin{figure}
\scriptsize
\begin{verbatim}
@project maxwell
@attribute ?T01 1 2 3 4 5
@attribute ?T02 1 2 3 4 5
@attribute ?T03 2 3 4 5
@attribute ?T04 2 3 4 5
@attribute ?T05 1 2 3 4 5
@attribute ?T06 1 2 3 4
@attribute ?T07 1 2 3 4 5
@attribute ?T08 2 3 4 5
@attribute ?T09 2 3 4 5
@attribute ?T10 2 3 4 5
@attribute ?T11 2 3 4 5
@attribute ?T12 2 3 4 5
@attribute ?T13 1 2 3 4 5
@attribute ?T14 1 2 3 4 5
@attribute ?T15 1 2 3 4 5
\end{verbatim}
\caption{The $maxwell$ query.}\label{fig:maxwell}
\end{figure}

\fig{tsize} shows the improvements seen in our 13 queries, running on
the data sets of \fig{data}. 
\input{tsize}
As shown by the last line of \fig{tsize}, the usual
improvements where (36,68) for (median,spread).
Note that, unlike STAR/NOVA, these are results on real-world data sets
not used during training. 

\fig{run} displays the \fig{tsize} results graphically. The dashed line indicates
the median of the improvements for each axis. 
\begin{figure}[!t]
\begin{center}
\includegraphics[width=2.5in]{reduce.pdf}
\end{center}
\caption{Median and spread improvements for effort estimation.
Dashed lines mark the median values of both axes.}
\label{fig:run}
\end{figure}
One data set had consistently worse results than any other.
The gray cells of \fig{tsize} 
indicate when {\W} failed (i.e. where the treatments increased 
median development effort
or spread, or both). Note that the gray cells are found only in the Desharnais results.

On investigation, the root cause of the problem was the granularity of the data.
Whereas (e.g.) coc81 assigns only one of six values to each attribute,
Desharnais's attributes had a very wide range. Currently, we are exploring
discretization policies to~\cite{YanWeb02Comparative,dou95} reduce attributes with large cardinality to a smaller
set. Tentatively, we can say that discretization solves the problem
with Desharnais but we are still studying this aspect of our system.

Even counting the negative Desharnais results, in the majority of cases {\W} found treatments that improved
both  the median and spread
of the effort estimates.
Sometimes, the improvements were modest: in the case of (coc81,flight),
the median did not improve (but did not get worse) while the spread was only reduced
by
18\%.
But sometimes  the improvements are quite dramatic.
\bi
\item
In the case
of (ISBSG,stalone), a 100\% improvement in spread was seen when $q'$
selected a group of projects that were co-developed and, hence,
all had the same development time.
\item
In the case of (coc81,ground), a 95\% effort improvement was seen when $q'$ 
found that ground systems divide into two groups (the very expensive,
and the very simple). In this case {\W} found the factor
that drove a ground system into the very simple case. 
\ei
\newpage
\section{Discussion}
%XX controllability
\subsection{Comparisons to NOVA}
\fig{compare} shows that estimation improvements found  by {\W} (in
this report) to the improvements  reported previously (in Figure 1).
This table is much shorter than \fig{tsize} since, due to the modeling
restrictions imposed by the software process models, NOVA cannot
be applied to all the data sets that can be processed by {\W}.
The numbers in \fig{compare} cannot be directly compared due to the different
the different goals of the two systems: {\W} tries to minimize effort while
NOVA tries to minimize effort {\em and} development time {\em and} delivered defects
(we are currently extending {\W} to handle such multiple-goal optimization tasks).
Nevertheless,
it is encouraging to note that the results
are similar and  that the {\W} improvements are not always less than those
found by STAR/NOVA.
\begin{figure}[!h]
\begin{center}
\begin{tabular}{r|rr}
study & NOVA & {\W}\\\hline
nasa93 flight & 72\% & 61\% \\ 
nasa93 ground & 73\% & 77\%\\
nasa93 osp & 42\%    & 49\% \\
nasa93 ops2 & 5\%   & 27\%\\
\end{tabular}
\end{center}
\caption{
Comparing  improvements ($\frac{initial - final}{initial}$) found
by NOVA (from~\protect\fig{compare1})  and {\W} (\fig{tsize}).
}\label{fig:compare}
\end{figure}

Regardless of the results in \fig{compare},
even though we prefer {\W} (due to the simplicity of the analysis)
there are 
clear indicators of when we would still use  STAR/NOVA.
{\W} is a case-based method. If historical cases are not
available, then STAR/NOVA is the preferred method.
On the other hand, STAR/NOVA is based on the USC COCOMO suite of models.
If the local business users do not endorse that mode,
then {\W} is the preferred method.


\subsection{Threats to Validity}
{\em External validity} is the ability to generalize results outside
the specifications of that study\cite{Milic2004}.  To ensure the
generalizability of our results, we studied a large number of projects.
Our
datasets contain a wide diversity of projects in terms of their
sources, their domains and the time period they were developed in.
Our reading of the literature
is that this study uses more project data, from more sources,
than numerous other papers. 
Table 4 of~\cite{Mendes2007} list the total number of projects in all data sets
used by other studies. The median value of that sample is 186, which is less much less
than the 
the 328 projects used in our study.



{\em Internal validity}  questions to what extent the
cause-effect relationship between dependent and independent variables
hold~\cite{Alpaydin2004}.  %This paper faces a general and specific internal validity issue.
For example, the above results showed
reductions in the effort estimates of up to
95\%;
i.e. by a factor of 20. Are such massive reductions possible?

As shown in \fig{coceffects}, 
these reductions  are theoretically possible.
\fig{coceffects} shows the relative effects of different factors
seen in 161 projects. According to this chart, making maximal changes to the first factor (personnel/team capability)
can affect the development effort by up to a 3.53. Making maximal changes just to the first four factors
could have a net effect of up to \[3.53*2.38*1.62*1.54\approx 21 > 20\]
By the same  reasoning,
making maximal changes to all factors  could have a net effect of up to eleven thousand.
Hence, an improvement of 95\% (or even more) is theoretically possible.
\begin{figure}
\scriptsize
\begin{center}
\begin{tabular}{l@{}|l@{~}r@{~}l}
%& & relative\\
id & features  & relative weight\\\hline
1&Personnel/team capability  & 3.53	&\rule{17mm}{2mm}\\
2&  Product complexity & 2.38&	\rule{12mm}{2mm}\\
3& Time constraint & 1.63&	\rule{8mm}{2mm}\\
4&    Required software reliability & 1.54&	\rule{8mm}{2mm}\\
5&    Multi-site development   &	1.53&	\rule{7mm}{2mm}\\
6&       Doc. match to life cycle  & 	1.52	&\rule{7mm}{2mm}\\
7&  Personnel continuity  &	1.51&	\rule{7mm}{2mm}\\
8&  Applications experience & 1.51	&\rule{7mm}{2mm}\\
9& Use of software tools & 1.50	&\rule{7mm}{2mm}\\
10& Platform volatility & 1.49&	\rule{7mm}{2mm}\\
11& Storage constraint & 1.46&	\rule{7mm}{2mm}\\
12& Process maturity  &	1.43	&\rule{7mm}{2mm}\\
13&    Language \& tools experience  &	1.43	&\rule{7mm}{2mm}\\
14&     Required dev. schedule & 1.43	&\rule{7mm}{2mm}\\
15&Data base size & 1.42&	\rule{7mm}{2mm}\\
16&  Platform experience & 1.40&	\rule{7mm}{2mm}\\
17&     Arch. \& risk resolution  &	1.39&	\rule{7mm}{2mm}\\
18&  Precedentedness  &	1.33&	\rule{6mm}{2mm}\\
19&  Developed for reuse  	&1.31	&\rule{6mm}{2mm}\\
20& Team cohesion  &	1.29&	\rule{6mm}{2mm}\\
21&    Development mode   &	1.32	&\rule{6mm}{2mm}\\
22& Development flexibility &	1.26	&\rule{6mm}{2mm}\\
\end{tabular}
\end{center}
\caption{Relative effects  on development effort.
Data from
a regression analysis of 161 projects. From \protect\cite{boehm00b}.  
}\label{fig:coceffects}
\end{figure}

As to what is pragmatically possible, that is a matter for human decision making. No automatic tool such as
STAR/NOVA/{\W} has access to all the personnel factors and organizational constraints known to a human manager.
Also, some projects are inherently expensive (e.g. the flight guidance system of a manned spacecraft) and 
cutting costs by, say, reducing the required reliability of the code is clearly not appropriate.
Tools like {\W} are useful for uncovering options that a human manager might have missed, yet ultimately 
the actual project changes must be a human decision.


%An experiment was conducted with ``W'' across a variety of historical Software Engineering datasets from the PROMISE dataset repository. While the datasets use COCOMO's Lines of Code (KSLOC) and Function Points for quantifying project complexity, any representative discrete model can be used. The datasets used were:
%
%\bi
%\item{NASA: effort prediction data representing 93 different NASA projects collected in the 80s and 90s. (COCOMO)}
%\item{Desharnais: University of Montreal software costs (Function Points)}
%\item{ISBSG: StandAlone and Client/Server software costs (Function Points)}
%\item{Maxwell: Finish banking data~\cite{maxwelldata}}
%\ei
%
%For each dataset ``W'' generated 50 synthetic examples, took the 20 kth nearest neighbors, and ranked the "best" of these neighbors as being in the 5 lowest effort rankings. ``W'' trained it's theories on 67\% of each dataset and applied learned treatments to the other 33\%. Nomograms were used as a means of ranking treatments.
%
%As shown in figure \ref{fig:run}, the upper-right quadrant of the chart consist of projects where ``W'' generated theories that reduced both the median effort and th "spread" between the 25\% and 75\% quartiles. On average we show a 29\% reduction in median effort along with a 54\% reduction in spread.
%
%While we have consistent improvements across all datasets, outliers in the Desharnais dataset present some problems. This can possibly be attributed to only having synthetic project descriptions rather than real-world representations. For the NASA datasets using USC COCOMO we see larger improvements with the majority of projects demonstrating improvements in both effort and spread reduction. Also, when a decision from ``W'' negatively impacts either effort or spread reduction, only one of these performance metrics is significantly impacted. There exist no decisions that significantly increase both the spread and effort of our results.
%
%Finally, figure \ref{fig:tsize} contrasts the different treatments generated within the same dataset. Three interesting patterns emerge. First, the theories we generate are extremely small. For all projects in the NASA93 only a single treatment brings us the largest reduction. Second, each theory is vastly different. Using the USC COCOMO attributes no consistent pattern emerges in our recommendations, despite consistent effort reduction. Finally, the majority of theories generated include values in the middle of the possible ranges. 
%


%\section{Discussion}
%
%With ``W'' we have demonstrated how contrast sets can be used to
%extend case-based reasoning into the treatment realm. Even with the
%simplicity of Euclidean nearest-neighbors for measuring case relevancy
%we achieved significant and consistent software effort
%reduction(figure~\ref{fig:run}). We have demonstrated that even
%small, local theories may offer meaningful improvement for the
%business user (figure~\ref{fig:tsize}).
%
%While an automatic stopping procedure is considered useful,
%practitioners may appreciate the ability for a human expert to sit
%in-the-loop with ``W'' and shape treatment options. This flexibility
%allows a user to easily and quickly decide themselves what theory
%works best for their situation, and immediately judge the effects
%of such a theory with historical backing. These theories are small,
%easy to understand, and useful for the busy reader. Compared to
%complex decision trees or rule learners ``W'' offers a refreshing
%simplicity with real results.
%
\section{Conclusion}

If a manager is given an estimate for developing some software,
they may ask ``how do I change that?''.  The model variance problem
makes it difficult to answer this question.  Our own prior 
solution to this problem required an underlying
process model that limited the data sets that can be analyzed.  

This paper has introduced {\W}, a case-based reasoning
approach (augmented with a simple linear-time greedy search for
contrast sets). {\W}
provides
a mechanism that allows projects to improve over time based on historical events, greatly assist in the project planning and resource allocation.
{\W} has proven to be simpler to implement and use than our prior solutions. 
Further,
since this new method has
no model-based assumptions, it can be applied to more data sets.
When tested on 13 real-world case studies, this approach found changes
to projects that could greatly reduce the median and variance of
the effort estimate. 

\section{Future Work}
This paper has presented {\W} in the context of effort estimation.
We suspect, but cannot yet show, that the algorithm would be a useful
decision aid in many other domains.

While a promising prototype, there are many design options left to explore
within {\W}. For example,
Equation 2 is a generalization of the Euclidean
distance measure used in {\W}'s training phase:
\begin{equation}\footnotesize
Distance = \sqrt{\sum_{i=1}^{n}{w_i(x_{i} - y_{i})^{2}}}
\end{equation}
In the above, $w_i$ is a weighting applied
to each attribute.
Currently, {\W} uses $w_i=1$ but there are any number of proven and fast
feature weighting schemes that can focus the inferencing away
from noisy attributes~\cite{hall03,chen05}.

Also, there a few too many {\em magic numbers} within the current version of
{\W}. For example, during training, the best and rest sets are of size $K_1=5$ and $K_2=15$.
Now that we have baseline results, it would be prudent to conduct experiments
to see  if there are better values for $K_1$ and $K_2$.

One issue is {\W}'s  greedy linear-time search to explore the contrast set.
Perhaps some of STAR/NOVA's search algorithms could be applied to {\W} to improve
that aspect of the inference.

Finally,
 given the power of contrast sets to extract relevant attributes,
future work exists in seeing if  {\W} is a useful 
feature subset selector for other domains.


%\end{document}  % This is where a 'short' article might terminate

%ACKNOWLEDGMENTS are optional
%\section{Acknowledgments}
%I would like to acknowledge and thank Adam Brady and Ekrem Kocaguneli for allowing me to use part of their content within this document, as well as being responsive to my inquiries and requests. As such I have added them as co-authors to this document.

%\appendix
%\section{The File Hierarchy and Code Organization}
%Within the \textit{W} directory there are two types of files. The first are the data files which store the case bases and the projects specifications. The former are stored within the ``datasets'' folder, while the latter are stored in the ``projects'' folder.
%
%The other type of files are the awk code files. Most of these are in the root \textit{W} directory, and include the following:
%
%\bi
%\item \texttt{w.awk}: This is the file that houses the main function, and that is responsible for initiating all the function calls. By exploring this file, one can get a good idea about the operation of \textit{W}.
%\item \texttt{project.awk}: contains the sampler function that builds the random case base sample.
%\item \texttt{neighbors.awk}: contains the functions responsible for determining project similarity, as well as determine the most similar projects (k-nearest neighbor).
%\item \texttt{contrast.awk}: contains the functions that determine the best attribute settings and ranking the attributes. This is done via contrast set leaning after determining the best project cases in our sample.
%\item \texttt{constrain.awk}: contains the functions that apply the highest ranked attributes, as well as readjust our estimated effort statistics based on the remain sample subset. This file also contains the stopping conditions.
%\item \texttt{util.awk}: contains random utility functions used in \textit{W}, such as the Mann-Whitney U test \cite{mann47}.
%\ei
%
%Note that there also exists a bash script called \texttt{w} which is responsible for fetching settings from the command line and relaying them to the awk file to be used. It is the wrapper that allows us to run the awk code in a simple manner.
%
%\newpage
%\section{COCOMO}
%\input{cocmo}
%
% The following two commands are all you need in the
% initial runs of your .tex file to
% produce the bibliography for the citations in your paper.
\bibliographystyle{abbrv}
\bibliography{myrefs,refs}

% You must have a proper ".bib" file
%  and remember to run:
% latex bibtex latex latex
% to resolve all references
%
% ACM needs 'a single self-contained file'!
%
%APPENDICES are optional
%\balancecolumns
%\appendix

\end{document}
