% THIS IS SIGPROC-SP.TEX - VERSION 3.1
% WORKS WITH V3.2SP OF ACM_PROC_ARTICLE-SP.CLS
% APRIL 2009
%
% It is an example file showing how to use the 'acm_proc_article-sp.cls' V3.2SP
% LaTeX2e document class file for Conference Proceedings submissions.
% ----------------------------------------------------------------------------------------------------------------
% This .tex file (and associated .cls V3.2SP) *DOES NOT* produce:
%       1) The Permission Statement
%       2) The Conference (location) Info information
%       3) The Copyright Line with ACM data
%       4) Page numbering
% ---------------------------------------------------------------------------------------------------------------
% It 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.
%
% Questions regarding SIGS should be sent to
% Adrienne Griscti ---> griscti@acm.org
%
% Questions/suggestions regarding the guidelines, .tex and .cls files, etc. to
% Gerald Murray ---> murray@hq.acm.org
%
% For tracking purposes - this is V3.1SP - APRIL 2009

\documentclass{acm_proc_article-sp}
%\usepackage{bibspacing}
\usepackage{alltt,url,cite}
\usepackage{algpseudocode}
\usepackage{algorithm}
\usepackage{colortbl}
\usepackage{times}
% Different font in captions
%\newcommand{\captionfonts}{\sffamily\footnotesize}

%\makeatletter  % Allow the use of @ in command names
%\long\def\@makecaption#1#2{%
%  \vskip\abovecaptionskip
%  \sbox\@tempboxa{{\captionfonts #1: #2}}%
%  \ifdim \wd\@tempboxa >\hsize
%    {\captionfonts #1: #2\par}
%  \else
%    \hbox to\hsize{\hfil\box\@tempboxa\hfil}%
%  \fi
%  \vskip\belowcaptionskip}
%\makeatother   % Cancel the effect of \makeatletter
%

\newcommand{\boxplot}[5]{
\begin{picture}(100, 7)
\put(#1, 2){\line(0, 1){4}}
\put(#1, 4){\line(1, 0){#2}}
\put(#3, 4){\circle*{3}}
\put(#3, 4){\line(1, 0){#4}}
\put(#5, 2){\line(0, 1){4}}
\put(50, 3){\line(0, 1){4}}
\end{picture}
}


\newcommand{\bd}{\begin{description}}
\newcommand{\ed}{\end{description}}
\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}$}


%\ifCLASSINFOpdf
%   \usepackage[pdftex]{graphicx}
  % declare the path(s) where your graphic files are
%   \graphicspath{{../pdf/}{../jpeg/}}
  % and their extensions so you won't have to specify these with
  % every instance of \includegraphics
%   \DeclareGraphicsExtensions{.pdf,.jpeg,.png}
%\else
  % or other class option (dvipsone, dvipdf, if not using dvips). graphicx
  % will default to the driver specified in the system graphics.cfg if no
  % driver is specified.
  % \usepackage[dvips]{graphicx}
  % declare the path(s) where your graphic files are
  % \graphicspath{{../eps/}}
  % and their extensions so you won't have to specify these with
  % every instance of \includegraphics
  % \DeclareGraphicsExtensions{.eps}
%\fi

\newfloat{program}{thp}{lop}
\floatname{program}{Program}

\begin{document}

\title{Comparing Case-Based Reasoning with Model-Based Systems for Software Effort Estimation}
%
% 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{2} %  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\\
       \affaddr{Lane Department of CS\&EE}\\
       \affaddr{West Virginia University, USA}\\
       \email{adam.m.brady@gmail.com}
% 2nd. author
\alignauthor
Tim Menzies\\
       \affaddr{Lane Department of CS\&EE}\\
       \affaddr{West Virginia University, USA,}\\
       \email{tim@menzies.us}
}
% 3rd. author
%\alignauthor Lars Th{\o}rv{\"a}ld\titlenote{This author is the
%one who did all the really hard work.}\\
%       \affaddr{The Th{\o}rv{\"a}ld Group}\\
%       \affaddr{1 Th{\o}rv{\"a}ld Circle}\\
%       \affaddr{Hekla, Iceland}\\
%       \email{larst@affiliation.org}

\date{28 May 2010}
% 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}
%Machine learning has been incredibly successful. We are drowning in choice as to how we can infer the cost of building software. Two conflicting choices ask whether we should construct an abstract model to represent software projects, or if simply reasoning from historical cases is enough. This paper presents {\W}, a case-based reasoning algorithm, and compares it to SEESAW, a model-based method for local AI search within COCOMO. We demonstrate that a simple, calibrationless, model-agnostic algorithm such as {\W} performs just as well if not better than SEESAW for reducing software cost across multiple goals such as development effort, project defects, and completion time.

\emph{\textbf{Background:}} Machine learning has been incredibly successful. We are drowning in choice as to how we can infer the cost of building software. Two conflicting choices ask whether we should construct an abstract model to represent software projects, or if simply reasoning from historical cases is enough.\\
\emph{\textbf{Aim:}} We aim to show a comparison between two software cost estimation methods, one case-based and the other model-based.\\
\emph{\textbf{Method:}} We present {\W}, a case-based, calibrationless, model-agnostic reasoning algorithm, and compare its software cost reduction estimations to those of SEESAW, a model-based method for local AI search within COCOMO.\\
\emph{\textbf{Results:}} In 32 different tests {\W} always performs at least as good as SEESAW. For 9 of those tests {\W} performs better.\\
\emph{\textbf{Conclusion:}} {\W} performs just as well if not better than SEESAW for reducing software cost across multiple goals such as development effort, project defects, and completion time. 

\end{abstract}

\keywords{Software Effort Estimation, Cost Models, Case Based Reasoning} % NOT required for Proceedings

%Sources:

%CBR stuff:
%CBR (4 things): ~\cite{aamodt94}
%Chris Riesbeck, anti-agent: ~\cite{antiAgent}
%CBR description: Teak: not published

%"The use of accurate, systematic, historical data for building
%useful effort prediction systems is extremely important, yet
%in practice, such data is seldom available." ~\cite{01sparse}

%"Similarity is defined as Euclidean distance in n-dimensional space where n is the number of project features" ~\cite{shepperd97}
%CBR for SE~\cite{She02}
%Dynamic memory, founding CBR ~\cite{schank83}
%Leake book, two tenants of CBR ~\cite{leake96}

%Background

%09BFC: ~\cite{me09f}
%Shepphard econ: ~\cite{shepperd07}
%Data set size (doesn't matter): ~\cite{me06f}

%SEESAW:

%Drastic (SEESAW description): ~\cite{me09a}
%Origin: ~\cite{me07g}
%Andre Reuse paper (also covers CO*) ~\cite{orrego09}

%NOVA:
%Description of NOVA, value paper: ~\cite{me09i}

%Model stuff:
%Cocomo: ~\cite{boehm81}
%COCOMOII: ~\cite{boehm00b}
%Local calibration / model variance with COCOMO: ~\cite{me09e}

\section{Introduction}

Accurately estimating software cost remains a core aspect of businesses today. For example, in the case of NASA's Check-out Launch Control System~\cite{CLCS03}, the initial estimate of \$200 million was quickly overrun, with the project burning another \$200 million before being cancelled. Not only are these estimates often wrong ~\cite{boehm81}, they are often wrong by a factor of four or more~\cite{kemerer87}.

To assist humans in creating these estimates, a torrent of machine learning research has emerged. A quick search over major journals and conferences revealed over 600 different papers on estimating software cost.~\cite{shepperd07}. Of these papers, the dominant topic was to introduce new estimation techniques. What users are left with is an abundance of choice. Without a single, unifying banner to weave together cost estimation techniques, no one method has achieved \emph{de facto} status in the cost estimate community.

For example, the standard method of software cost estimation involves parametric model construction. A representation of a software project is generalized into a mathematical abstraction, then all future projects are estimated according to the parameters of the model. A benefit of which is that once a model can show general trends, extrapolate patterns, and generally reduce complex, human behavior into a mere formula.

There several reasons for the lack of a standard software cost model. These includes generality, data islands and instability. Software models may not be general so it can be inappropriate to apply a software model learned in environment one to environment two. Also, many companies prefer to keep cost related data confidential. This data island effect has also contributed to the fragmentation of the field by preferring building private models rather than using publicly available models. This multiplicity of software effort models has lead to scarcity of the publicly available local data needed for the model based effort estimation. Without sufficient data to build, audit, and tune models, the predictions generated by these models may be highly unstable.~\cite{me09e}

However, the locality of software models may not necessarily be a bad thing. Rather than attempt to generalize all software into a standard model, we can instead simply reason from the data. Case-based reasoning attempts to capitalize on two tenents of the world: similar problems have similar solutions, and that problems encountered once are likely to occur again.~\cite{leake96} As C. Riesbeck explains, "We don't think, we remember." ~\cite{antiAgent}

Model-based and case-based methods represent two ends of a wide spectrum of cost estimation techniques. Rather than attempt to settle an ongoing debate, we simply offer an experiment between the two strategies. This paper introduces {\W}, a simple, case-based algorithm for software effort estimation and reduction. Competing with {\W} is SEESAW, a model-based (USC COCOMO~\cite{boehm81}) algorithm that extends from MaxWalkSat.~\cite{kautz97} {\W} is a much smaller program with hundreds of lines of awk, whereas SEESAW exists as thousands of lines of C++/LISP. The relative complexity of these two algorithms resides not just in their languages; we will show the intrinsic simplicity of {\W} compared to the Monte Carlo simulator an AI search of SEESAW.

This paper is structured in the following order: First we present a deeper look at the technical tradeoffs of model-based reasoning and case-based reasoning. Second, we pose three research questions to be answered by the results of our experiment. Then, we'll explore the implementations of SEESAW and {\W}. Finally, we present an experiment that compares the software cost recommendations from {\W} with those of SEESAW.

\subsection{Research Questions}

\textbf{RQ1:} Can the recommendations produced by a case based reasoning system such as W perfom better than a model-based approach?

\textbf{RQ2:} Do different datasets effect the relative performance of one method over another?

\textbf{RQ3:} In which situations should one prefer a particular method over another?

\section{Background}

\subsection{Estimation Techniques}

Sheppherd categorizes the current landscape of software cost estimation methods into three groups.~\cite{shepperd07}
\begin{itemize}
\item Human-centric techniques (a.k.a. expert judgment)
\item Algorithmic/parametric models such as COCOMO ~\cite{boehm81}~\cite{boehm00b}
\item Induced prediction systems such as case-based reasoning.
\end{itemize}
\emph{Human centric techniques} are the most widely-used estimation method ~\cite{shepperd07}, but are problematic.
If an estimate is disputed, it can be difficult to reconcile competing human intuitions (e.g.) when one estimate is generated by a manager who is senior to the other estimator. Also, Jorgensen ~\cite{jorgensen04} reports that humans are surprisingly poor at reflecting and improving on their expert judgments. For the purposes of this paper, we will set aside the comparision to human-centric techniques as another topic.

%-GENERAL OVERVIEW OF 3 CLASSIFICATIONS-

%Human-centric is the most widely-used(teac S2 has refs), but are problematic. In human-centric approaches...

%Human factors influence bias into estimations. The choice of one manager's analysis over another may come not from the intrinsic quality of the analysis, but hierarchal factors like seniority.

%Another approach is model based...
%generate model only once (time-consuming), then no data needed. Can show general trends, extrapolate said %trends. Nice abstractions. Experts can inject knowledge.

%third: CBR:
%satisfying justifications, fewer assumptions, data-agnostic, local data might not fit the model, no %calibration
%(cite: chris riesbeck)

\subsection{Modeling Techniques}

One alternative to expert judgment is a \emph{model-based} estimate. Models are a reproducible methods for generating an estimate. This is needed for (e.g.) U.S. government software contracts that require a model-based estimate at each project milestone. Such models are used to generate and audit an estimate, or to double-check a human-centric estimate. Model based estimates can be generated using an algorithmic/parametric approach or via induced prediction systems. In the former, an expert proposes a general model, then domain data is used to tune that model to specific projects. For example, Boehm's 1981 COCOMO model ~\cite{boehm81} hypothesized that development effort was exponential on LOC and linear on 15 effort multipliers such as analyst capability, product complexity, etc. Boehm defined a local calibration procedure to tune the COCOMO model to local data. Induced prediction systems are useful if the available local training data does not conform to the requirements of a pre-defined algorithmic/parametric model such as COCOMO. There are many induction methods including stepwise regression, linear regression, ruleinduction, neural nets, model trees, and analogy, just to name a few. All these methods have underlying assumptions.

\subsection{Case Based Reasoning}

Case based reasoning is a method of machine learning that seeks to emulate human recollection and adaptation of past experiences in order to find solutions to current problems. That is, as humans we tend to base our decisions not on complex reductive analysis, but on an instantaneous survey of past experiences \cite{schank83}; i.e. we don't think, we remember. CBR is purely based on this direct adaptation of previous cases based on the similarity of those cases with the current situation. Having said that, a CBR based system has no dedicated world model logic, rather that model is expressedthrough the available past cases in the case cache. This cache is continuously updated and appended with additional cases.

Aamodt \& Plaza \cite{aamod94} describe a 4-step general CBR cycle, which consists of:
\be
\item \textit{Retrieve}: Find the most similar cases to the target problem. 
\item \textit{Reuse}: Adapt our actions conducted for the past cases to solve the new problem.
\item \textit{Revise}: Revise the proposed solution for the new problem and verify it against the case base.
\item \textit{Retain}: Retain the parts of current experience in the case base for future problem solving.
\ee


Having verified the results from our chosen adapted action on the new case, the new case is added to the available case base. The last step allows CBR to effectively learn from new experiences. In this manner, a CBR system  is able to automatically maintain itself.
As discussed below, {\W} supports $retreive$, $reuse$, and $revise$ (as well as $retain$ if the user collecting data so decides).

\begin{figure}[!ht]
\begin{center}
         \includegraphics[scale=0.4]{figs/cbrcycle1.png}
         \caption{figure}{A diagram describing the steps of CBR (source: http://www.peerscience.com/Assets/cbrcycle1.gif).}
         \label{fig:cbr}
 \end{center}
\end{figure}

This 4-stage cyclical CBR process is sometimes referred to as the R4 model \cite{She02}.
Shepperd \cite{She02} considered the new problem as a case that comprises two parts.
There is a description part and a solution part forming the basic data structure of the system.
The description part is normally a vector of features that describe the case state at the point at which the problem is posed.The solution part describes the solution for the specific problem (the problem description part).

The similarity between the target case and each case in the case base is determined by a similarity measure.
Different methods of measuring similarity have been proposed for different measurement contexts.
A similarity measure is measuring the closeness or the distance between two objects in an n-dimensional Euclidean space,
the result is usually presented in a distance matrix (similarity matrix) identifying the similarity among all cases in the dataset.
Although there are other different distance metrics available for different purposes, the Euclidean distance metric is probably the most commonly 
used in CBR for its distance measures.

Irrespective of the similarity measure used, the objective is to
rank similar cases from case-base to the target case and utilize
the known solution of the nearest $k$-cases. The value of $k$ in
this case has been the subject of debate \cite{kadoda00,shepperd97}:
Shepperd~\cite{shepperd97},
Mendes~\cite{Mendes2003} argue for $k=3$ while
Li~\cite{Li2009} propose $k=5$. 

Once the actual value of the
target case is available it can be reviewed and retained in the
case-base for future reference. Stored cases must be maintained
over time
 to prevent information irrelevancy and inconsistency. This is a
 typical case of incremental learning in an organization utilizing
 the techniques of CBR.

Observe that these 4 general CBR application steps (retreive, reuse, revise, retain)
do not include any explicit model based
calculations; rather we are relying on our past experience, expressed
through the case base, to estimate any model calculations based on the
similarity to the cases being used. 
This has two advantages:
\be
\item
It allows us to operate independently of the models being used. 
For example, our prior report to this
conference~\cite{me09i}  ran over two data sets. This 
this study, based on CBR, uses twice as many data sets.
\item
This improves our performance,
since data retrieval can be  more efficient than calculation,
especially given that many thousands of iterations of calculation
were needed with our traditional modeling based tool. 
As evidence of this, despite the use of a slower language, {\W}'s AWK code
 runs faster than the C++/LISP used in SEESAW.
 It takes just minutes to conduct 20 trials over 13 data sets with
{\W}. A similar trial, conducted with SEESAW, can take hours to run.
\ee

%"Similarity is defined as Euclidean distance in n-dimensional space where n is the number of project features" ~\cite{shepperd97}
%CBR for SE~\cite{She02}
%Dynamic memory, founding CBR ~\cite{schank83}
%Leake book, two tenants of CBR ~\cite{leake96}

\section{Implementations}

\subsection{SEESAW}
SEESAW searches within the ranges of project attributes to find constraints that most reduce development effort, development time, and defects. Figure ~\ref{fig:seesaw} shows SEESAW's pseudo-code. The code is an adaption of Kautz \& Selman's MaxWalkSat local search procedure [13]. The main changes are that each solution is scored via a Monte Carlo procedure (see score in Figure ~\ref{fig:seesaw}) and that SEESAWseeks to minimize that score (since, for our models it is some combination of defects, development effort, and development time in months). 

SEESAW first combines the ranges for all project attributes. These constraints range from Low to High values. If a project does not mention a feature, then there are no constraints on that feature, and the combine function (line 4) returns the entire range of that feature. Otherwise, combine returns only the values from Low to High. In the case where a feature is fixed to a single value, then Low = High. Since there is no choice to be made for this feature, SEESAW ignores it. The algorithm explores only those features with a range of Options where Low < High (line 5). In each iteration of the algorithm, it is possible that one acceptable value for a feature X will be discovered. If so, the range for X is reduced to that single value, and the feature is not examined again (line 17). SEESAW prunes the final recommendations (line 21). This function pop off the N selections added last that do not significantly change the final score (t-tests, 95\% confidence). This culls any final irrelevancies in the selections. The score function shown at the bottom of Figure 6 calls COCOMO/COQUALMO models 100 times, each time selecting random values for each feature Options. The median value of these 100 simulations is the score for the current project settings. As SEESAW executes, the ranges in Options are removed and replaced by single values (lines 16-17), thus constraining the space of possible simulations.

\begin{figure}[!ht]
{\small
\begin{verbatim}
1 function run (AllRanges, ProjectConstraints) {
2   OutScore = -1
3   P = 0.95
4   Out = combine(AllRanges, ProjectConstraints)
5   Options = all Out features with ranges low < high
6   while Options {
7     X = any member of Options, picked at random
8     {Low, High} = low, high ranges of X
9     LowScore = score(X, Low)
10    HighScore = score(X, High)
11    if LowScore < HighScore
12      then Maybe = Low; MaybeScore = LowScore
13      else Maybe = High; MaybeScore = HighScore
14    fi
15    if MaybeScore < OutScore or P < rand()
16      then delete all ranges of X except Maybe from Out
17      delete X from Options
18      OutScore = MaybeScore
19    fi
20  }
21  return backSelect(Out)
22 }
23 function score(X, Value) {
24   Temp = copy(Out) ;; don't mess up the Out global
25   from Temp, remove all ranges of X except Value
26   run monte carlo on Temp for 100 simulations
27   return median score from monte carlo simulations
28 }
\end{verbatim}
}
\caption{Pseudocode for SEESAW}
\label{fig:seesaw}
\end{figure}

\subsection{W}

The standard procedure for CBR is to report the median class value of some local neighborhood. This neighborhood is typically defined as the Euclidean distance from a defined project in n-dimensional space with n project features. ~\cite{shepperd97} {\W} works similarly, but defines a project as a range of values:

\begin{itemize}
\item From a range of project values, cases are retrieved that match a specific amount of \emph{overlap} with the defined project ranges. A case's overlap is defined as the percentage of attributes that fall within the specified ranges of the defined project.
\item From these selected similar cases, the cases are sorted by a measure of utility. In the case of effort, defect, and month estimations, this utility is the normalized euclidean distance from the lowest possible cost for all three factors.
\item From these sorted ranges, a \emph{contrast set} is learned. The top 5 "best" cases (those with the best utility measure) are placed into a set labelled "best". The next 15 ranked cases are placed into a set labelled "rest", for a combined total of 20 cases.
\item From the contrast set, {\W} selects the features that best select for the region with the best utility measurements.
\end{itemize}

\subsubsection{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 frequency of which they appear in the "best" set squared divided by how often the candidate appears in both the "best" and "rest" sets. A simple strategy to score more favorably towards attributes that occur most often in the best case is to square the number of times. Taking this heuristic one step further, given an attribute $x$, we can penalize $x$'s occurance in the "rest" by dividing the sum of the frequency counts in best and rest~\cite{me09f}, the ensuring rare attributes are weighted appropriately:

\begin{equation}
like = \frac{freq(x\vert best)^2}{freq(x\vert best) + freq(x\vert rest)}
\end{equation}

From this measure we need only sort each attribute by it's $like$ score to prioritize our recommendations

\subsubsection{The W Algorithm}

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


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

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$.

\subsection{Multiple Goals}

Optimizing for simply effort in software cost estimation can be bad. For instance, it may require less effort to produce software with much lower quality standards, but doing so may drastically increase defects. Additionally, reducing the schedule constraints will incur larger development time. To solve this problem, {\W} bases it's recommendations on multiple goals.

It does this by ranking on some measure of utility for each case. If, say, we wish to reduce the effort, defects, and months requirements, a simple utility measure can be derived from the normalized euclidian distance from the best possible values for all goals (\textbf{E}ffort, \textbf{D}efects, \textbf{M}onths):

$$score = \frac{E - E_{min}}{E_{max} - E_{min}} + \frac{D - D_{min}}{D_{max} - D_{min}} + \frac{M - M_{min}}{M_{max} - M_{min}}$$

\section{Comparing {\W} to SEESAW}

\subsection{Methodology}
We present an experiment to compare the effort, defects, and months reduction power of W compared to SEESAW. Each algorithm will be given a set of 4 real-world projects with defined COCOMO attribute ranges. The goal of each algorithm will be to choose specific recommendations for these value ranges that will maximize the reduction the project's effort, defects, and months.

Before we can measure the relative effectiveness of one effort reduction recommendation over another, we need a way to compare the recommendations from both SEESAW and W in common terms. This is trivial, as once each tool generates its recommendations, these recommendations can then be applied using any model or inference prediction system. Once applied, regardless of the testing environment we can compare the relative effectiveness of each algorithm. For the sake of simplicity we have chosen to test recommendations using W.

\subsection{Dataset and Project Descriptions}

In order to test the efficacy of model-based and case-based estimation techniques, we need a source of case data for W. Because SEESAW was built around COCOMO and W is a data-agnostic, we chose the free COCOMO NASA93 dataset available from \texttt{http://promisedata.org/data}. This dataset represents 93 different NASA projects collected from the 1980's and 1990's represented as feature vectors describing each project in COCOMO format.

However, the NASA93 data only contains historical information for actual project effort. In order to provide a comparison in reducing multiple goals, the development time in \emph{months} was computed using the COCOMO model. Also, the COQUALMO ~\cite{boehm00b} model for defect removal was employed to synthesize \emph{defects} estimations for each project. Combined, each historical project case had three attributes that needed to be minimized.

\input{figs/projects.tex}

Next, project definitions are needed to provide grounds on which to improve. Along with the NASA93 dataset comes four real-life case studies at NASA, each representing a unique range of possible COCOMO scale factors and effort multipliers.
\begin{itemize}
\item \emph{Ground} and \emph{flight} represent typical ranges for most NASA projects at JPL
\item \emph{OSP} represents the guidance, navigation, and control aspects of NASA's 1990 Orbital Space Plane.
\item \emph{OSP2} represents a second, later version of OSP with a more limited scope of COCOMO attributes.
\end{itemize}
Figure ~\ref{fig:cases} shows in detail each project. The low and high ranges define the space of possible recommendations for that project. For instance, the reliability of the JPL flight software can vary from a ranking of 3 (nominal) to 5 (very high). SEESAW and W will each attempt to improve the overall estimation in effort, defects, and months by recommending changes to these values.

\subsection{Testing Procedure}

A testing rig was built to inject recommendations generated within SEESAW into W's testing phase. Because the testing phase of W only requires the recommendations gained from the training phase, testing with SEESAW's recommendations is identical to testing with W's.

Once in place, recommendations for each of the four case studies was tested 50 times. Each test reported the reduction in median effort, defects, months, and the synthesized "score" attribute.

This measure gives a more general picture of the overall reductions across the entire space rather than each individual goal.

Also reported is the "spread", or the distance between the third (75\%) and first (25\%) quartiles. This measure gives a rough estimate on how much more \emph{certain} the estimations have become. A reduction in this "spread" constitutes a narrowing of the range of estimations, implying a less varied outcome. Both the median reduction and the spread reduction are reported in terms of before and after estimates.

\section{Results}

%A detailed summary of the reductions in effort, defects, and overall "score" of the four Nasa case studies can be found in figures figures ~\ref{fig:score} ~\ref{fig:effort} ~\ref{fig:defects} ~\ref{fig:months}. 

The four datasets were split into four separate goals (score, effort, defects, months) measured as both average reduction (lower cost) and average "spread" reduction (narrower recommendations). The following figures show the results for ``score''[~\ref{fig:score-medians},~\ref{fig:score-spreads}], effort[~\ref{fig:effort-medians},~\ref{fig:effort-spreads}], defects[~\ref{fig:defect-medians},~\ref{fig:defect-spreads}], and months[~\ref{fig:month-medians},~\ref{fig:month-spreads}]. 

To determine statistical significance for each comparison, A Mann Whitney U test was performed on the two sets of reduction distributions from each comparison. Given a 95\% confidence interval, figure ~\ref{fig:win-loss-tie} shows that overall W performs better than SEESAW on 9 of the 32 tests, and performs no worse than SEESAW on the other 21 tests.

On individual datasets, W performs better on reducing estimations given projects with more constrained ranges such as OSP2. On 5 out of the 8 comparisons involving OSP2, W outperformed SEESAW. Less conclusive results were achieved regarding the other, more openly-defined projects. Only 3 out of the 24 comparisons resulted in a statistically significant improvement using {\W} over SEESAW.

Overall, {\W} performs no worse than SEESAW, and shows clear improvements in certain circumstances.

\input{figs/win-loss-tie.tex}

%\input{figs/w-vs-seesaw.tex}

\input{figs/average-reductions.tex}

\section{Answers to Research Questions}

With the above results, we can now answer the research questions proposed at the beginning of the paper.

\textbf{RQ1: Can the recommendations produced by a case based reasoning system such as W perfom better than a model-based approach?}\\

We've demonstrated that {\W} can perform just as well if not better than SEESAW ~\ref{fig:win-loss-tie}. More importantly, similar results have been achieved while making fewer assumptions, and without the need for any model calibration.\\

\textbf{RQ2: Do different datasets effect the relative performance of one method over another?}\\

The results for the OSP2 dataset[~\ref{fig:score-medians},~\ref{fig:score-spreads},~\ref{fig:effort-medians},~\ref{fig:effort-spreads},~\ref{fig:defect-medians},~\ref{fig:defect-spreads},~\ref{fig:month-medians},~\ref{fig:month-spreads}] show that there exists a discrepancy between performance in datasets with few recommendation options. 

\textbf{RQ3: In which situations should one prefer a particular method over another?}

This is left as an open question. One of the ongoing issues in effort estimation is model vs case based. While we currently cannot extrapolate enough evidence to make a solid statement in the general case, we offer the preceeding comparison as a nexus point for further research along with a few considerations.

One consideration is how much local data is available. In situations where, say, a company has recently formed or is breaking new ground in software engineering practices, the lack of relevant historical cases prevents the use of CBR. As Martin Shepphard says, "the use of accurate, systematic, historical data for building useful effort prediction systems is extremely important, yet in practice, such data is seldom available." ~\cite{01sparse} However, previous work has shown that one may not need much data in order to successfully perform CBR tasks ~\cite{me06f}. After all, "history repeats itself, but not exactly" ~\cite{shepperd07}.

Another consideration is how satisfying a justification is from concrete, documented cases compared to abstract mathematical extrapolations? In our experience, users, especially business users, have found more solace in being able to use their own intuition to justify a recommendation. The core algorithms inside {\W} such as contrast sets are fast and easy to explain, bearing one accepts the underlying locality assumption.

Finally, one must consider the lack of a single, unifying model for software effort estimation. Building a model requires assumptions from the underlying statistical distributions of the data to the calibration parameters needed to ensure accuracy. While a model benefits from reuse once created, as you only need to build it once, the potential range of these parameters~\cite{me09e} can undermine the usefulness of the tool as a whole.

We haven't faulted previous work ~\cite{me09i}~\cite{me07g} with model-based approaches, but we have demonstrated that tools like {\W} can compete and exceed more complex methods. With only a few extensions to the premise of case based reasoning, {\W} has shown promise.

\subsection{Threats to Validity}

Currently, we do not have results for datasets with actual historical measurements for defects and months. Synthesizing the defects and months for the NASA93 dataset using COQUALMO and COCOMO may have removed underlying patterns in the data. Because these values were generated from COCOMO scale factors and effort multipliers, a direct correlation exists between defects and months in regards to the project features.

Secondly, the comparison between SEESAW and {\W} took place inside {\W}'s testing procedure. While this decision allowed a direct comparision between recommendations, the estimations generated for each were just that, estimations. We do not have a means to compare how these recommendations might perform in a real-world setting at this time.

\section{Conclusion}

{\W} has shown tangible potential in terms of direct performance, but the question of choosing model-based reasoning over case-based reasoning remains an ongoing discussion. Research scientists relish the idea that we can reduce complex, human-centered domains to beautiful, intuitive patterns. However, while the models we produce may be useful, effort estimation has yet to find a single, unifying abstraction under which to explain all software projects. As long as this goal remains unrealized, tradeoffs will exist between model-based reasoning and case-based.


\bibliographystyle{abbrv}
\bibliography{refs}  

\balancecolumns

\end{document}
