%XXX get rid of the fig{r1}r efgerences 
%XXX add the case for calibration
%\documentclass[twocolumn,10pt]{article}  
\documentclass[12pt]{article}  
\usepackage{times,color,url,graphicx,textcomp,cite,amssymb,bar}
\DeclareGraphicsExtensions{.epsf,.jpg,.eps,.pdf}
%%\setlength{\parskip}{6ex}	   % space between paragraphs
\setlength{\parindent}{2em}	   % amount of indention
\newenvironment{smalldescriptions}
               {\setlength{\topsep}{0pt}
                 \setlength{\partopsep}{0pt}
                 \setlength{\parskip}{0pt}
                 \begin{description}
                   \setlength{\leftmargin}{.2in} 
		   \setlength{\parsep}{0pt}
                   \setlength{\parskip}{0pt}
                   \setlength{\itemsep}{0pt}}
               {\end{description}
}

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

\newcommand{\bd}{\begin{smalldescriptions}}
\newcommand{\ed}{\end{smalldescriptions}}
\newcommand{\bi}{\begin{smallitem}}
\newcommand{\ei}{\end{smallitem}}
\newcommand{\be}{\begin{smallnum}}
\newcommand{\ee}{\end{smallnum}}
\newcommand{\fig}[1]{Figure~\ref{fig:#1}}
\newcommand{\eq}[1]{Equation~\ref{eq:#1}}
\newcommand{\tion}[1]{\S\ref{sec:#1}}

\begin{document}

%\conferenceinfo{IEEE Software}{Submitted June 2005}

%\CopyrightYear{2005}

%\crdata{}

\title{Software Cost Models: When  Less is  More}
\author{
Zhihao Chen$^\dag$,  Tim Menzies$^\star$, Dan Port$^\ddag$, 
Barry Boehm$^\dag$\\
$^\dag$Center for Software Engineering, University. of Southern California\\
 $^\star$Computer Science, Portland State University\\
  $^\ddag$Computer Science, University of Hawaii\\
{\small \url{zhihaoch@cse.usc.edu;  tim@timmenzies.net}}\\
{\small \url{dport@hawaii.edu; boehm@cse.usc.edu}}}
\date{}
\maketitle
\begin{abstract}
If experience tells us when to {\em add} variables to a cost
model, it should also be able to tell us when to {\em subtract}
variables. Data mining methods can  intelligently
select variables to subtract and so generate
 reduced models which  are
much better at estimating efforts within an organization's particular context.

Word count: 3975 words+ (7 figures*200)=5375
\end{abstract}

\section{Introduction}

\footnotetext{Submitted to IEEE Software, \date{\today}.
Earlier drafts available at:  \url{http://menzies.us/pdf/05lessismore.pdf}.}
Good software 
cost models can significantly help
the managers of software projects.
With such  good models,
project stake holders can make informed decisions
about (e.g.) 
``buy-or-make'', how to manage resources, how to control and plan the
project, and how to deliver the project on time, on schedule and on
budget. 

As we learn more about software, the number of parameters in those
    models tends to grow. In going from the 1981 COCOMO model~\cite{boehm81} to
    the 2000 COCOMO II model~\cite{boehm00b}, one parameter, ``Turnaround Time'', was
    dropped to reflect the almost-universal use of interactive
    software development.  Another parameter, ``Modern Programming
    Practices'', was dropped in favor of a more general ``Process Maturity''
    parameter. But several more parameters were added to reflect the
    subsequently-experienced influences of such factors as ``Development
    for Reuse'', ``Multisite Development'', ``Architecture and Risk
    Resolution'', and ``Team Cohesion''. The COCOMO II book~\cite{boehm00b} also
    provides capabilities and guidelines for an organization to add
    new parameters, reflecting their particular situations.
 
\begin{figure}[!t]
\begin{center}
{\footnotesize
\begin{tabular}{rlr|rr|r}
\multicolumn{3}{c}{}&\multicolumn{2}{c}{\%estimates within}\\
\multicolumn{3}{c}{}&\multicolumn{2}{c}{30\% of actuals }\\\cline{4-5}
&data set & \#projects &before & after & $\frac{after}{before}$\\\hline
1.&nasa60  &60 &  68\% & 82\% & 120\%\\
2.&coc81 & 63 &  44\% & 51\% & 116\%\\
3. & cii04 & 119 & 68\% & 72\% & 106\%\\
4.&cii00& 161 & 75\% & 76\% & 101\% \\\hline
\multicolumn{3}{r|}{mean}&64\%&70\%&110\%\\
\multicolumn{6}{r}{}\\\hline
&data set & \#projects &before & after & $\frac{after}{before}$\\\hline
5.&t03 &  10 & 28\% & 62\% & 221\%\\
6.&p03 & 12 & 8\% & 52\% & 650\%\\
7.&c02 & 12 &  11\% & 48\%& 436\%\\
8.&c01 & 13 & 20\% & 58\%& 290\%\\
9.&t02 & 14 & 19\% & 81\% & 426\%\\
10.&p04 & 14 &  25\% & 63\% & 252\%\\
11.&p02 & 22& 15\% & 97\% & 646\%\\
12.&c03 & 31 & 88\% & 95\% & 108\%\\\hline
\multicolumn{3}{r|}{mean}&27\%&70\%&379\%\\
\end{tabular}
}
\end{center}
\caption{
Estimation and variable subtraction.
}\label{fig:summ}
\end{figure}


But if experience can tell us when to {\em add} variables, it should
also be able to tell us when to {\em subtract} variables. If not, then
our models may grow forever and become needlessly complex. \fig{summ}
shows that subtracting variables can be surprisingly useful.  For data
sets containing many projects, variable subtraction made little
difference. But for data sets containing just a few dozen projects (or
less), the improvement in estimation effectiveness was dramatic (on
average, a 379\% improvement).

The rest of this paper describes experiments with our tool for
variable subtraction. This tool, called CMP, is a set of UNIX scripts
that use the WRAPPER variable subtraction algorithm from the
public-domain WEKA data mining toolkit~\cite{witten99}.  This paper
expands on a prior workshop publication~\cite{chen05} in two ways.
Firstly, it includes an expanded discussion on the business
implications of subtracting variables.  Secondly, this paper explores
more data than before (double the number
of COCOMO-I project analyzed, two new COCOMO-II data sets).

\section{When Less is \underline{NOT} More}

The improvements seen in
\fig{summ} are quite large
and the rest of this paper discusses the data mining methods
used to find which variables to subtract. Before that,
we first describe
situations in which variables
should not be subtracted, {\em even it subtracting them improves
estimation effectiveness}. 

Firstly, our variable subtraction methods require an historical
database of projects.  If there is {\em no} such database,then our
variable subtraction techniques won't work.

Secondly, even a historical database exists and our techniques suggest
subtracting variable $X$, then it may still be important to ignore
that advice.  If a cost model {\em ignores} certain effects that
business users believe are important, then those users may {\em not
trust} that model.  In that case, even if a variable has no noticeable
impact on predictions, it should be left in the model.  By leaving
such variables in a model we are acknowledging that, in many domains,
expert business users hold in their head more knowledge that what may
be available in historical databases.  Suppose that there is some
rarely occurring combination of factors which leads to a major
productivity improvement.  Even if there is little data on some
situation, it still should be included in the model.  For example,
even though some studies have shown that reduced-parameter function
point counting rules are equally good in most
situations~\cite{boehm00b}, COCOMO~II supports the full International
Function Point Users' Group (IFPUG) set of parameters due to their
wide usage and acceptance in the IFPUG community.

Thirdly, another reason not to subtract variables is that you still
might need them.  For example, the experiments shown below often
subtract over half of the attributes in a COCOMO-I model. As shown in
\fig{summ}, this can dramatically improve the effort estimation.
However, suppose that a business decision has to be made using some of
the subtracted variables. The reduced model has no information on
those subtracted variables so a business user would have to resort to
other information for making their decisions.

For these reasons, we propose the {\em
decision ladder} of \fig{ladder}.  
\begin{figure}[!t]
\begin{center}
\includegraphics[angle=270,width=3in]{ladder.pdf}
\end{center}
\caption{A ladder of decisions in cost modeling.}\label{fig:ladder}
\end{figure}
The ladder has three parts: general COCOMO, followed by local
calibration, followed by variable reduction.  The ladder represents how much
variable subtraction is suitable for different business situations.

%Crosstalk: April 2000
%Does Calibration Improve Predictive Accuracy?
%Daniel V. Ferens
%David S. Christensen
%http://www.stsc.hill.af.mil/crosstalk/2000/04/ferens.html

%% \begin{figure}
%% \begin{center}
%% {\footnotesize
%% \begin{tabular}{rlr|rr|r}
%% \multicolumn{3}{c}{}&\multicolumn{2}{c}{\%estimates within}\\
%% \multicolumn{3}{c}{}&\multicolumn{2}{c}{25\% of actuals }\\\cline{4-5}

%% #&dataset&n&before&after&delta&reference

%% 13 & ground support     &  7 & 20 & 286\\
%% 15 & nasa60             & 60 & 45 & 70 & 155\\
%% 11 &command and control & 12 & 30 & 40 & 133\\
%% 12 &signal processing   & 19 & 33 & 40 & 121\\
%% 14 & military models    & 12 & 10 & 0 & 0\\
%% \end{tabular}}
%% \end{center}
%% \caption{
%% Cost estimation effectives before and 
%% after stratification.
%% }\label{fig:summ}
%% \end{figure}


%% #11&mermaid1&<28&21&39&186&\citePshep}
%% #12&desharnais4&<77&42&70&167&\citePshep}
%% #  13&coc87&83&52&64&123&\cite{chulani99}
%% #  14&mermaid2&<28&21&25&119&\citePshep}
%% #    15&desharnais2&<77&42&48&114&\citePshep}
%% #      16&desharnais1&<77&42&47&111&\citePshep}
%% #	17&coc00&161&75&80&107&\cite{chulani99}\\
%% #&&mean&42&53%132

At the base of the
ladder is {\em general public domain knowledge}.  The 1981 regression
co-efficients of COCOMO-I  or the updated
co-efficients of COCOMO-II~\cite{boehm00b} are the best general-purpose
indicators we can currently offer for cost estimation.  
Management decisions can use that public knowledge
to make software process decisions.  For example, according to the
coefficients on the COCOMO-II {\em pmat} variable, the increase in
cost between a CMM3 and CMM4 project contain $N$ lines
of code is  $N^{3.13}/N^{1.56}$. With this
estimate in hand, a business user could then make their own assessment
about the cost of increased software process maturity vs the benefits
of that increase.

If historical data from the local site is available, then effort
estimation can rise to the next rung in the estimation ladder.
COCOMO-I and COCOMO-II contain with several {\em local calibration}
variables that can quickly tune a model to local project data. Our
experience has been that 10 to 20 projects are adequate to achieve
such tunings~\cite{me04h}.

Local calibration is a simple tuning method that is supported by many
tools\footnote{e.g. \url{http://sunset.usc.edu/available_tools/index.html}}.
Currently, our {\em variable reduction} methods requires more effort
(i.e. some UNIX scripting) than local calibration.  \fig{summ}
suggests that the extra effort may well be worthwhile, particularly
when building models from a handful of projects.  Also, we
have found that it is easier to extrapolated costs from old projects
to new projects with reduced variable sets~\cite{me05c,me05a}.
Nevertheless,
variable reduction is {\em
not} appropriate when there are business reasons to use all available
variables (e.g. the three reasons  described above).


\section{Why Subtract Variables?}

Having made the case for {\em keeping} variables, we now explore the other
side of the coin. There are many reasons for
{\em subtracting} variables.
For example,
from a {\em business perspective}, there are several situations
where managing less variables is useful. For example:
\bi
\item
When monitoring
an out-sourced project at a remote site, it is useful to have minimized
the reporting requirements to just the variables that matter the most.
Such a minimized reporting structure reduces the overhead in managing a contract.
\item
When assessing competing bids, a knowledge
of what is most important can simplify the task 
of  assessing the bids. For example:
\bi
\item
All material relating
to irrelevant variables can
be safely ignored.
\item
When doubling-checking the contractor's
quotes against industrial standards, it is only necessary to check
the variables that matter the most.
\ei
\ei

Also, from a {\em technical perspective}, there are good reasons
to subtract variables:
\bd
\item[Irrelevancy:] Sometimes, modelers are incorrect in their beliefs
about what variables effect some outcome. In this case, they might
add irrelevant variables to a model.
\item[Noise:] 
Data collection was somehow flawed for a particular variable with the
result that one or more variables are {\em noisy} (i.e. 
contains spurious signals not associated with
variations to projects).  Noise can come from many sources
including the situation when
 data collectors have to  guess (a.k.a. ``make up'')
values for a variables
that is not collected in a particular domain/ organization/ projects.
For example, organizations that only build word processors may have little
data on software projects with high reliability requirements.
Learning a cost estimation model is easier when
the learner does not have to struggle with fitting the model
to confusing noisy data.
\item[Correlated variables:] 
The reverse problem of noise is
associated variables.  If multiple variables are tightly correlated,
then using all of them will diminish the likelihood that either
variable attains significance.  A repeated result in data mining is
that subtracting some of the correlated variables increases the
effectiveness of the learned model (the reasons for this are subtle
and vary according to which particular learner is being
used~\cite{hall03}).
\item[Under-sampling:] The number of possible influences on a project
is quite large and, usually, historical data sets on projects for a 
particular company are quite small. This motivates the subtraction
of variables, even if those variables are theoretically useful.
\ed

To understand the under-sampling
problem,
consider two models for project {\em p02} (from
\fig{summ}) that use two variables
or four variables. 
Suppose that each variable takes one of
five values (e.g. they are COCOMO variables with values 
{\em very high, high,
nominal, low, very low}). The smaller model with two variables
has an internal state
space of $5^2=25$ and the larger model with four variables
has an internal state space
of $5^4=625$.  \fig{summ} records that project {\em p02} comprises
22 projects. These 22 projects could sample a large
part of the two-variable model (up to $\frac{22}{25}=88\%$).
However, those same 22 projects can only ever sample a {\em very small
fraction} ($\frac{22}{625}=3.5\%$) of the four-variable model.


\fig{dels} shows that under-sampling
is not just a theoretical concern.
In the {\em nasa60} data set, most
 projects cluster were rated as having
 a {\em high} complexity.  Therefore, this data set would not support
conclusions about the interaction of extra high complex
projects with other variables. A learner would be wise to
subtract this variable (and a cost modeling analyst would be wise
to suggest to their NASA clients that they 
refine the local definition of ``complexity'').

\begin{figure}[!t]
\begin{center}
{\footnotesize {
\begin{barenv}
\setstyle{\sffamily}
\setyaxis{0}{50}{10} 
\setwidth{30}
\sethspace{0.2}
%\setxaxis{2}{6}{1}
 \bar{2}{8}[\small low] % -5
 \bar{5}{8}[\small nominal] %-4
 \bar{50}{8}[\small high] % -3
 \bar{2}{8}[\small v.high] % -2
 \bar{1}{8}[\small x.high]  % -1
\end{barenv}}}
\end{center}
\caption{Distribution of software complexity {\em cplx}
within the {\em nasa60}  data set. 
}
\label{fig:dels}
\end{figure}

Whatever the reason (business or technical),
a repeated result in the data mining community is that simpler
models with equivalent or higher performance can be built
by {\em feature subset selection} (FSS) algorithms that 
intelligently subtraction of useless variables. 
For example,  Kohavi and John's
WRAPPER~\cite{kohavi97} 
builds models using an increasing number
of variables; i.e. \mbox{$N=1,2,3,4,...$}.
For each $N$, there is a current {\em selected} set (initially,
the empty set)
 and a set of remaining variables (those that have not
been selected). For each remaining variable, a new
bigger set is tried containing the current set, plus one of the remaining
variables. The set that yields the best learned model
becomes the current set, $N$ becomes $N+1$  
and the process continues.
WRAPPER stops when either the remaining set is empty or
there has been no significant improvement in the learned model
for the last five additions (in which case, those last five
additions are deleted).

WRAPPER is thorough and, according to Hall and Holmes,
often yields the best results~\cite{hall03}.
However, it can be too slow to run.
It is simple to see why: there are a large
number of possible subsets to explore.
A naive search through all possible 
subsets of the 15 COCOMO-I variables
would have to explore  32768 subsets.
Happily, our study did not too long. 
The data sets of \fig{summ} are quite small
and  our experiments only required
around 20 minutes per data set.
                                                                   
The Hall and Holmes results were also negative about another
widely used
FSS technique: principle component analysis (PCA). FSS methods can be
grouped according to:
\bi
\item
Whether or not they make special use of the
target attribute in the data set such as ``development cost'';
\item
Whether
or not they use the target learner as part of their FSS analysis.
\ei
PCA
is unique since, unlike other FSS methods, it {\em does not} make
special use of the target attribute. WRAPPER is also unique, but for
different reasons: unlike other FSS methods, it {\em does} use the
target learner as part of the FSS analysis. Hall and Holmes found that
PCA was one of the worst performing FSS methods (perhaps because it
ignored the target attribute) while WRAPPER was the best (since it can
exploit its special knowledge of the target learner).
                                                                                    



%% \begin{figure}[!t]
%% \begin{center}
%% {\scriptsize
%% \begin{tabular}{l|r@{:~}l|}\cline{2-3}
%% increase&acap&analysts capability\\
%% these to&pcap&programmers capability\\
%% decrease&aexp&application experience\\
%% effort &modp&modern programming practices\\
%% &tool&use of software tools\\
%% &vexp&virtual machine experience\\
%% &lexp&language experience\\\cline{2-3}
%%       &sced&schedule constraint\\\cline{2-3}

%% decrease&data&data base size\\
%% these to&turn&turnaround time\\
%% decrease&virt&machine volatility\\
%% effort&stor&main memory constraint\\
%% &time&time constraint for cpu\\
%% &rely&required software reliability\\
%% &cplx&process complexity\\\cline{2-3}
%% \end{tabular}}
%% \end{center}
%% \caption{{
%% COCOMO~I effort multipliers.}}\label{fig:em}
%% \end{figure}

\section{Case Study}

To test the effectiveness
of subtracting variables,
we used WRAPPER to select subtractable variables
from the  \fig{summ} projects. Those projects were described in terms
of the COCOMO set of variables.

COCOMO~\cite{boehm81, boehm00b}  is used for
estimating software cost, effort and schedule. COCOMO helps software developers
reason about the cost and schedule implications of their software
decisions such as software investment decisions; setting project budgets
and schedules; negotiating cost, schedule, and performance
tradeoffs; making software risk management decisions, and making
software improvement decisions.

COCOMO
measures effort in calendar months where one month is 152
hours (and includes development and management hours). The core
intuition behind COCOMO-based estimation is that as systems grow
in size, the effort required to create them grows exponentially; i.e.

{\footnotesize
\begin{equation}\label{eq:one}
months=a*\left(KSLOC^b\right)*\left(\prod_iEM_i\right)
\end{equation}}
%XXXwhat about repeatability (folks repeating other people's work), straw man.
%also, acceptable if >= cocomo1 stratified results
%competent if pred(30) cocomo stratified results
%good if pred(25)> 83%

Here,
$EM_i$ is one of 15 
{\em effort multipliers} such as {\em cplx} (complexity)
or {\em pcap} (programmer capability).
In the COCOMO-I
model, $a$ and $b$ are domain-specific parameters and KSLOC is estimated
directly or computed from a function point analysis.  In COCOMO II,
$b$ was expanded to include {\em scale factors}:

{\footnotesize
\[
b=0.91+\sum_jSF_j\]}
\noindent
where $SF_j$ is one of five {\em scale factors} that exponentially
influence effort. Examples of scale factors include {\em pmat}
(process maturity) or {\em resl} (attempts to resolve project risks).

Various learning methods have been applied to COCOMO.
Elsewhere~\cite{me05a}, we have seen that best results come from
transforming the COCOMO-I
equation of \eq{one} into the {\em linearized model} of \eq{two}:


{\footnotesize
\begin{equation}\label{eq:two}
LN(effort)=b*LN(Size)+LN(EM_{1})+LN(EM_{2})+{\ldots}
\end{equation}}

\noindent
For COCOMO-II, the linearized model is:

{\footnotesize
\begin{eqnarray}\nonumber
LN(effort)&=&SF_1*LN(Size)+SF_2*LN(Size)+...\\\label{eq:three}
&&LN(EM_{1})+LN(EM_{2})+{\ldots}
\end{eqnarray}}


At each step in the WRAPPER, some learner built a model from the
current set of variables. Elsewhere we have tried various methods for
such learning. In those experiments, simple linear regression on
over the linearized COCOMO models did as well as any other
method~\cite{me05a}.



%% \begin{figure}[!t]
%% \begin{center}
%% {\scriptsize
%% \begin{tabular}{|c|r@{~}|r@{~}|r@{~}|r@{~}|r@{~}|r|r|}
%%     \hline
%%     &very&&&&very&extra&productivity\\
%%     &low&low&nominal&high&high&high&range\\
%%     \hline
%% ACAP   &1.46   &1.19   &1.00   &0.86   &0.71   &&2.06\\
%% PCAP   &1.42.  &1.17   &1.00   &0.86   &0.70 &&2.03\\
%% AEXP   &1.29   &1.13   &1.00   &0.91   &0.82   &&1.57\\
%% MODP   &1.24.  &1.10 &1.00 &0.91 &0.82 &&1.51\\
%% TOOL   &1.24 &1.10 &1.00 &0.91 &0.83 &&1.49\\
%% VEXP   &1.21 &1.10 &1.00 &0.90 &  &&1.34\\
%% LEXP   &1.14 &1.07 &1.00 &0.95 &  &&1.20\\\hline
%% SCED   &1.23 &1.08 &1.00 &1.04 &1.10 &  &\\\hline
%% DATA   &    & 0.94 &1.00 &1.08 &1.16&&-1.23\\
%% TURN   &       &0.87   &1.00   &1.07   &1.15   &&-1.32\\
%% VIRT   &       &0.87   &1.00   &1.15   &1.30   &&-1.49\\
%% STOR   &       &       &1.00   &1.06   &1.21   &1.56&-1.56\\
%% TIME   &  &    &1.00   &1.11   &1.30   &1.66&-1.66\\
%% RELY   &0.75& 0.88& 1.00 & 1.15 & 1.40&&-1.87\\
%% CPLX   &0.70 &0.85 &1.00 &1.15 &1.30 &1.65&-2.36\\
%%     \hline
%% \end{tabular}}
%% \end{center}
%% \caption{{ COCOMO I effort multiplier
%% values.}}\label{fig:effortmults}
%% \end{figure}

%\vspace{6 pt}

\subsection{Data}

This study used two data sets described using  COCOMO~I variables
and two using COCOMO-II variables:
\bi
\item
{\em Coc81}  comes from the  COCOMO-I text~\cite{boehm81}
and includes  data from a variety of domains
including engineering, science, financial, etc.
\item
The {\em cii00} data set is the COCOMO-II data.
\item
The {\em cii04} data
set includes the 72 projects from {\em cii00}
developed after 1990, plus 47 new projects.
\item
{\em
Nasa60} comes from 20 years of NASA projects and is recorded using
the COCOMO-I variables.
This data comes  from  multiple {\em projects} developed at NASA centers
at different geographical {\em locations}; 
performing different {\em tasks} such as
 ground data receiving, flight guidance,etc.
\ei

\fig{summ} shows
results from the above four data sets
as well as several subsets of {\em nasa60}.
Those subsets come from
three NASA centers {\em c01,c02,c03}; three NASA 
projects {\em p02,p03,p04}; and two NASA tasks {\em t02,t03}. For reasons
of confidentiality, the exact details of those centers, tasks, and
projects cannot be disclosed.  The other centers, projects, and tasks
from {\em nasa60}
were not included for a variety of pragmatic reasons (e.g. suspicious
repeated entries suggesting data entry errors, too few examples for
generalization, etc).

Of these data sets, {\em coc81} describes projects
from before 1982; 
{\em ci04} contain  data from the most recent projects; and the NASA data
sets ({\em nasa60, pX,cX,tX}) described projects newer than {\em coc81}
and before {\em ci04}.

\begin{figure}[!t]
\begin{center}
{\scriptsize
\begin{tabular}{|r|c|r||r|c|r|}
\hline \multicolumn{3}{|c||}{coc81} & \multicolumn{3}{|c|}{p02} \\
\hline 
     &         & \# times&    &          &\# times \\
 FSx &variable &selected &FSx &variable &selected \\
 \hline\hline
 10 &loc  &10&7 &loc &10 \\
      \hline
 9 &sced &10&6 &turn &7 \\
      \hline
 9 &pcap &10&6 &lexp &7 \\
      \hline
 9 &time &10&5 &time &4 \\
      \hline
 8 &virt &9 &4 &modp &3 \\
      \hline
 7 &cplx &6 &3 &data &2 \\
      \hline
 6 &modp &5 &3 &tool &2 \\
      \hline
 6 &acap &5 &3 &sced &2 \\
      \hline
 6 &rely &5 &2 &rely &1 \\
      \hline
 5 &vexp &4 &2 &vexp &1 \\
      \hline
 4 &tool &3 &2 &cplx &1 \\
      \hline
 4 &data &3 &1 &aexp &0 \\
      \hline
 3 &aexp &2 &1 &pcap &0 \\
      \hline
 3 &stor &2 &1 &virt &0 \\
      \hline
 2 &lexp &1 &1 &acap &0 \\
      \hline
 1 &turn &0 &1 &stor &0 \\
\hline
\end{tabular}
}\end{center}
\caption{Some of the generated features sets.}\label{fig:fsets}
\end{figure}


\subsection{Using the Data}

For each dataset,
our experiments were in two parts: {\em
feature set generation}, followed by 
{\em feature set subtraction}.

Randomization was used extensively in our experiments.
Many algorithms have an {\em order effect} such that their performance
changes dramatically if the inputs are re-ordered.
Kermer reported order effects in his analysis data
from 15 projects: if training was restricted to 9 particular
projects, the learning was far more successful~\cite{kemerer87}.
Randomization
avoids such order effects.

\begin{figure*}[!t]
\begin{center}
\includegraphics[width=5in]{pred30_mean_no.pdf}
\includegraphics[width=5in]{pred30_mean.pdf}
\end{center}
\caption{Feature sets. 
The results from each data set stop at the point of greatest
``total wins - total losses''.}\label{fig:fs}
\end{figure*}

In {\em feature set  ordering}, the WRAPPER was called on 10 randomly
sub-samples
of the data set. Each sub-sample contained 90\% of the data
(selected at random).
Variable were
then grouped together according to how often they were {\em selected}
in the 10 sub-samples.
All the variables that were selected with the same frequency were
placed together into the same {\em feature set} FSx. The feature sets
are then ordered by their frequency counts and then numbered. 
To these feature sets, an extra sets are added:
``All'' (holding all the variables).
For example the table of \fig{fsets} shows the 
feature sets found in {\em coc81} and {\em p02} (note that
different feature sets are found in different data sets,
a point we will return to in the conclusion).


After {\em generation}, came {\em feature set subtraction}.
30 times, we randomized the order of the data.
Next, starting  with all the features, we
subtracted each feature set in turn. For each set, we 
conducted a hold-out experiments to assess the value of that particular
subset of the variables.   
In those hold-outs, we divided the project data described
using some FSx set into a $\frac{2}{3}:\frac{1}{3}$ subsets, trained
on the $\frac{2}{3}rd$ subset and tested on the $\frac{1}{3}rd$ test
subset.  The whole point of cost models is that they can be used to
estimate the cost of {\em new} projects.  Such hold-out experiments
ensure that we are assessing the learned model on the {\em new data}
in the test subset.
For each set, the mean and standard
deviation of the performance score on the test set
was collected. Scores from
different sets were then compared using t-tests:

\bi
\item
The performance of each model was scored using 
PRED(30); i.e. the percentage of
estimates in the test set that are within 30\% of the actual values.
We have found PRED(30)
easier to explain to business than alternate measures.  Also, landmark
high-water marks in software cost estimation report their results in
terms of PRED(30)~\cite{chulani99}. A longer version of this paper
(in preparation), scores our models on a wider range of criteria
including
PRED(20), PRED(25), and  MMRE (these were not included here for space reasons).
\item
To conduct the t-tests, the mean and standard
deviation of the different PRED(30)s seen in all pairs
of FSx and FSy were
computed. FSx and FSy were said to ``tie'' if there was no statistical
difference (at the $\alpha=0.05$ level) detectable.  If the comparison
did not ``tie'', then the means were numerically compared to compute
``win''s and ``loss''es.  The ``best'' FSx set was selected as the one
with the highest ``total wins- total losses'' score.
\ei

 All the plots
in \fig{fs} start at ``All'' and stop at the feature subset with the maximum
`total wins - total loses''
 (and if two sets
score the same ``total wins - total loses'', 
then the one with highest mean was selected as the winner).
\fig{summ} was generated by comparing the ``All'' mean PRED(30)
to the ``best'' mean PRED(30).

As shown in the top ``number of remaining variables''
plot of \fig{fs},
in the usual case, most of the variables
are subtracted. Usually, the data sets were 
pruned back to less than five variables.
Three data sets ({\em p03, p04, t02})
got pruned back to just one variable (lines of code).
The larger data sets ({\em cii04,cii00,coc81,nasa60}) were pruned
back the least. This is hardly surprising: the more data the more interesting
the inter-relationships and the less the win in subtracting variables.

The bottom ``mean PRED(30)''  plot of \fig{fs}
shows results from  30 {\em
hold-out} experiments conducted for each features set.
  One interesting feature of this ``mean'' plost
is  that ``best'' PRED never
results from using ``All'' variables.
This result  endorses the merits of variable subtraction: in terms of
generating models with high PRED, we have no evidence here that
there is any down side to always conducting feature subtraction (but
recall our previous remarks- sometimes there are business reasons
for {\em not} subtracting features).

When we looked at the standard deviations in our 30 hold-outs (see
\fig{summsd}),
we found
no extra evidence for or against variable subtraction.
For larger data sets, variable substraction
always reduced standard deviation. For smaller data sets, there
was no clear pattern: subtraction changed standard deviation
anywhere from 49\% to 150\% and, on average, there was little
change (last=99\% of first). 
\begin{figure}
\begin{center}
{\footnotesize
\begin{tabular}{lr|rr|r}
\multicolumn{2}{c}{}&\multicolumn{2}{c}{standard deviation on}\\
\multicolumn{2}{c}{}&\multicolumn{2}{c}{PRED(30) in 30 hold-outs}\\\cline{3-4}
data set & \#projects &before & after & $\frac{after}{before}$\\\hline
nasa60&  60&11\%&8\%&68\%\\
cii00&161&9\%&7\%&83\%\\
coc81& 63&11\%&10\%&89\%\\
cii04& 119&5\%&5\%&94\%\\\hline
\multicolumn{2}{r|}{mean}&9\%&7\%&83\%\\
\multicolumn{5}{r}{}\\\hline
data set & \#projects &before & after & $\frac{after}{before}$\\\hline
p02& 22&12\%&6\%&49\%\\
c03&31&12\%&6\%&51\%\\
t02& 14&26\%&19\%&74\%\\
c01& 13&21\%&21\%&100\%\\
p03& 12&15\%&16\%&105\%\\
p04& 14&21\%&26\%&126\%\\
c02& 12&17\%&24\%&139\%\\
t03& 10&22\%&32\%&150\%\\\hline
\multicolumn{2}{r|}{mean}&18\%&19\%&99\%\\
\end{tabular}
}
\end{center}
\caption{
Effects on standard deviation of variable subtraction.
}\label{fig:summsd}
\end{figure}


\section{Related Work}

Variable subtraction (a.k.a. feature subset selection) has been widely
studied in the data mining literature (e.g.~\cite{hall03,kohavi97}).
Mostly those studies have focused on discrete classes.  To the best of
our knowledge, the only other work on variable reduction and for
continuous class cost estimation data is Kirsopp \& Shepperd's (K\&S) case
base reasoning (CBR) work~\cite{kirsopp02}.

In CBR, decisions about the current case are then made by studying
similar historical cases.  A common technique is to use some form of
distance metric to extract the k-th nearest neighbors from the current
case within a case library. Some extrapolation mechanism is then
applied to analyze the nearest neighbors and make some decision about
expected properties of the current case.

K\&S explores CBR for cost estimation using feature subset selection
using two data sets:
\bi
\item
The {\em small} data set containing 10 variables and data from 77
projects;
\item
The {\em large} data set containing 48 variables and data from
407 projects.
\ei
Like us, K\&S found that FSS
significantly improves effort estimation.  However, and contrary to
\fig{summ}, they found that FSS improved effort estimation more in
the {\em large} data sets than in the {\em small} data set.
There are several possible explanations of why our results are so
different to those of K\&S. 
Firstly,  the K\&S definition of ``small'' is much larger than
our definition. For example, our ``small'' data sets contain 10 to 22
projects while K\&S's {\em small} 
data set contains 77 projects. It is possible
that if K\&S ran their toolkit over our very small data sets, they
might find a different effect.
Secondly, the studied
algorithms are different: K\&S
use CBR while we use regression over a parametric COCOMO models.  It
is possible that CBR is confused by smaller data sets.
Thirdly, we are using different data sets and to really compare
K\&S with our results, we need to run COCOMO data through their toolkit.

\section{Discussion}

The benefits of variable subtraction should be
carefully weighed against the business implications of subtracting
seemingly irrelevant variables:
\bi
\item
Cost models should contain all available variables
when business knowledge argues for retention. 
\item
Cost models should reject some variables (selected by WRAPPER) when
the goal is to improve effort estimation. As seen in \fig{summ}, for
small data sets (30 projects or less), the improved effort estimation
can be quite dramatic. 
This increased
improvement in the smaller data sets is an important result since, typically,
organizations only have data on a small number of projects.
\ei

For most of our data sets, variable subtraction selected different
variables.  For example, \fig{fsets} showed that different feature
sets were selected in different data sets (exception: $loc$, or lines
of code, was always selected).  To date, we have found no general
conclusions of the form ``it is always useful to remove variable
X''. If our goal was a {\em single} reduced-COCOMO model, then this
lack of selection repeatability in different data sets would reflect
poorly on our technique. However, our generality comes not from
the created model but from {\em the methods used to create that
model}. While it is true that different data sets select for different
variables, the {\em same} method (WRAPPER) can be used to find them in all
data sets.


When discussing these results, we are often asked why
we have not run these experiments on more data sets.
Accessing such further data sets is a non-trivial task.
It is hard enough getting {\em any} data from
{\em any} organization, let alone data in the COCOMO format.  There is
a good reason for this.  Software projects are notoriously difficult
to control.  Recall the 2001 report of the Standish group that
described a  software industry where 23\%
of projects totally fail, 28\% meet all expectations,
and the remaining 49\% were significantly challenged in some way
(e.g. over-budget, over the time estimate, fewer features and functions
that initially specified)~\cite{standish01}.
Corporations are therefore reluctant to expose their own 
less-successful software
development practices to public scrutiny.

Nevertheless, our goal is to apply our methods to more data from more
projects.  For example, we plan to run our data sets through the K\&S
toolkit.  Also we are teaming with the University of Ottawa to extend
the PROMISE repository of public-domain data sets relating to software
engineering~\cite{Sayyad-Shirabad+Menzies:2005}.  For example, if the
reader want us to try our techniques on their data, they just need to
submit it to that
repository\footnote{\url{http://promise.site.uottawa.ca/SERepository/dataset-software-donation-page.html}}
(perhaps with some anonymization of any business-critical
information).


\bibliographystyle{plain}
\bibliography{../../refs}

\end{document}

% LocalWords:  occored saperate
