%XXX get rid of the fig{r1}r efgerences 
%XXX add the case for calibration
%\documentclass[twocolumn,10pt]{article}  
\documentclass[12pt,txt]{article}  
\usepackage{times,color,url,graphicx,textcomp,cite,amssymb,bar}
\usepackage[right,modulo]{lineno}
\DeclareGraphicsExtensions{.epsf,.jpg,.eps,.pdf}
%%\setlength{\parskip}{6ex}	   % space between paragraphs
\setlength{\parindent}{2em}	   % amount of indention
 \linenumbers
\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{Finding the Right Data for\\
Software Cost Modeling}
\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}
Strange to say, when building a software cost model, sometimes it is
useful to {\em ignore} much of the available cost data.  

Word count: 4000 words+ (5 figures*200)=5000
\end{abstract}

\section{Introduction}

Good software 
cost models can significantly help
the managers of software projects.
With  good models,
project stake holders can make informed decisions
about (e.g.) 
how to manage resources, how to control and plan the
project, and how to deliver the project on time, on schedule and on
budget. 

Off-the-shelf ``untuned'' models have been up
to 600\% inaccurate in their estimates, e.g.~\cite{kemerer87}.
Hence, the wise  manager uses a cost model built from  local data.  
But what data should we use to build a good cost model?
Real-world data sets, such as what comes from  software
engineering projects, often contain noisy or irrelevant or redundant
variables. 

Prior to getting the data, it is hard to know what parts of
the data are most important.  However, once a database is available,
automatic tools can be used to prune the data back to the most
important values. Therefore this paper proposes a change to current practice.
Often, cost models are built using all available data. Here, we propose
that {\em after}  data collection and {\em before} model building, cost
modelers should perform some data pruning experiments. As shown below, such pruning
experiments are simple and fast to perform.
 
Our process starts with a table of historical data divided into
columns and rows. Each column is a
different {\em variable} describing some aspect of a software project.
Each row shows data from different software sub-systems, so one
project can contribute many rows. For example, \fig{eg} shows data
from 17 variables and rows from three  sub-systems from two projects.
\begin{figure}
{\scriptsize
\[
\begin{array}{c|c|c|c|c|c|c|c}
\multicolumn{2}{c}{}  & \multicolumn{5}{c}{variables}\\\cline{3-7}
\multicolumn{2}{c|}{}  & 1        & 2        &  3         &... & 17                    \\\hline
        & sub     & analyst  & process  & required   &   & lines    & development\\
project & system  & ability  & maturity & reliability& ... & of\, code  & effort (months)\\\hline
proj_1   & DB api  & high     & low      & high       & ... & 100,000  & 467\\
proj_1   & GUI     & high     & low      & low        & ... & 200,000  & 847\\
proj_2   & guidance& high     & high     & nominal    & ... &  50,000  & 174\\
...     &    ...  & ...     & ...      &   ...       & ... & ...      & ...\\
\end{array}  
\]}
\caption{Some project data.}\label{fig:eg}
\end{figure}
The data in
such a table can be pruned by removing columns or removing rows:
\be
\item
In row pruning (also known as  {\em stratification}), rows from related projects are
collected together and different cost models are learned from these
different subsets.  
\item
In column pruning (also known as {\em feature subset selection}), the columns are
sorted left-to-right according to their ``usefulness''; i.e. how well that
column's variable predicts for the target variable (in our case,
software development effort). 
%% For example, the above table might be re-ordered to:
%% {\scriptsize
%% \[
%% \begin{array}{c|c|c|c|c|c|c|c}
%% \multicolumn{2}{c|}{}  & \multicolumn{5}{c|}{\mbox{variables, re-ordered by ``usefulness''}} &     \\
%% \multicolumn{2}{c|}{}  & \multicolumn{5}{c|}{least\;useful  \Longrightarrow most\;useful} &\\\cline{3-7}
%% \multicolumn{2}{c|}{}  & 3         & 1        &  17         & 2 & ...                    \\\cline{3-7}
%%         & sub     & required  & analyst  & lines  &process &     & development\\
%% project & system  & reliability & ability & of\,code& maturity & ...  & effort (months)\\\hline
%% proj_1   & DB api  & high     & high      &  100,000 & low & ... & 467\\
%% proj_1   & GUI     & low     & high       & 200,000 & low & ... & 847\\
%% proj_2   & guidance& nominal     & high   & 50,000 & .high & .. & 174\\
%% ...     &    ...  &  ...        & ...      &   ...         & ... & ...      & ...\\
%% \end{array}  
%% \]}
Column pruning then  proceeds left to right across the sorted columns, each time
removing some less-useful left-hand-side columns.   
At each step of the pruning, a cost model is learned from the remaining columns. 
\ee
The benefits of row pruning have been reported
previously. For example, Shepperd and Schofeld~\cite{shepperd97}
report experiments with row pruning where estimator performance improved by up
to 28\% (measured in terms of the ``PRED'' measure described later in this article),
However, and this is the point of this paper, we find that much larger improvements
result from
pruning {\em both} rows and columns. For example, the experiments
presented here include one data set called $p02$
where estimator performance improved from
15\% to 97\%.  

Further,
these large improvements were seen when most of the
columns are pruned away. For example, in our experiments, column pruning removed
65\% of all columns (on average).
Surprisingly,
when building a software cost model, it is
usually  
useful to ignore over half of the available cost data.  

More
 importantly, row and column pruning leads to the {\em largest}
 improvements in estimator performance in the {\em smallest} training
 sets (less than 30 examples).  This is a result of tremendous
 practical significance.  Modern software practices  change so
 rapidly that most organizations can't access large databases of
 relevant project data.  Our results suggest that this is not
 necessarily a problem, provided models are learned via row {\em and}
 column pruning.


This rest of this paper describes experiments with our tool for
column pruning. This tool is a set of UNIX scripts
that use the WRAPPER variable subtraction algorithm from the
public-domain WEKA data mining toolkit~\cite{witten99}.  
The tool is fully  automated, runs on a standard LINUX installation, and
is available from the authors.

\section{Background}

This paper applies column pruning methods to cost estimation.  These
pruning methods were evolved by the data mining community. While these
methods have been explored extensively~\cite{hall03,kohavi97}, there
is very little prior work on column pruning and software cost
modeling. 

To the best of our knowledge, the only other work on column pruning
for cost estimation was a limited experiment by Kirsopp \&
Shepperd~\cite{kirsopp02}.  Like this study, they found that column
pruning significantly improves effort estimation.  However, their
experimental base was much more restrictive than this study (they ran
only two data sets while we ran 15). Also, unlike our work, their
experiment is not reproducible. The Kirsopp \& Shepperd data sets are
not public domain while all our COCOMO-I data sets can be downloaded
from the PROMISE repository.

An earlier draft of this paper appeared previously in a workshop
publication~\cite{chen05}.  This paper extends that earlier draft in
two ways.  Firstly, this paper explores more data than before (double
the number of COCOMO-I project analyzed, two new COCOMO-II data sets).
Secondly, it includes an expanded discussion on the business
implications of column pruning.

\section{Pruning: Why?}

The case for pruning rows is quite simple. Software projects are not all the same. 
For example, real-time
safety critical systems are very different to batch financial processors. Given a database
of different kinds of software, it is just good sense to divide up the rows into different
project types and learn different cost models for each type. Then, in the future,
managers can use different cost models depending on what type of software they are developing.

The case for pruning columns is slightly more complex.  If a learned
cost model uses all the variables in the database then the only way to
use that cost model on future sub-systems is to collect information on
all those variables.  In many business situations, the cost of
reaching some goal is a function of how much data you have to collect
or monitor along the way.  But if the learned model uses only {\em some}
of the variables, then using that model in the future means collecting
less data.  This would be useful in several scenarios.  For example,
when monitoring an out-sourced project at a remote site, it is useful
to minimize the reporting requirements to just the variables that
matter the most.  Such a reporting structure reduces the overhead in
managing a contract.

From a technical perspective, there are also good reasons
to subtract variables:
\bd
\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. Hence, a variable that is {\em theoretically} useful
may be {\em practically} useless.
For example, \fig{dels} shows how in {\em na60} data set, nearly all those
those NASA projects were rated as having
 a {\em high} complexity (see \fig{dels}).  
\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 na60}  data set. 
}
\label{fig:dels}
\end{figure}
Therefore, this data set would not support
conclusions about the interaction of, say, 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'').
\item[Reducing Variance:]
Miller offers an extensive survey of column pruning for linear models
and regression~\cite{miller02}. That survey includes a very strong
argument for column pruning:
the variance of a linear model learned by
minimizing least squares error decreases as the number of  columns
in the model. That is, the fewer the columns, the more restrained are the
model predictions.
\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 database. Without column pruning, a cost
model learned from that database might contain these irrelevant
variables.  Anyone trying to use that model in the future would then
be forced into excessive data collection.
\item[Noise:] 
Learning a cost estimation model is easier when
the learner does not have to struggle with fitting the model
to confusing noisy data  (i.e. when the data  
contains spurious signals not associated with
variations to projects).  Noise can come from many sources such clerical errors
or missing data.
For example, organizations that only build word processors may have little
data on software projects with high reliability requirements.
\item[Correlated 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 pruning away 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}).
\ed

\section{Pruning: How?}

The column pruning method used in this study was is called the ``WRAPPER''~\cite{kohavi96}.
The WRAPPER selects
combinations of columns and asks some learner to build a cost model
using just those columns.  The WRAPPER then grows the selected columns
and checks if a better model comes from learning over the larger set
of columns.  

The WRAPPER stops when there are no more columns to
select, or there has been no significant improvement in the learned
model for the last five additions (in which case, those last five
additions are deleted). Technically speaking, this is a forward select
search with a ``stale'' parameter set to 5.

WRAPPER is thorough but, theoretically, it is quite slow since (in the
worst case), it has to explore all subsets of the available
columns. However, all the data sets in this study are quite small.
Our experiments only required around 20 minutes per data set.
                                                                   
We use the WRAPPER since other experiments by other researchers
strongly suggest that it is superior to many other column pruning
methods.  For example, Hall and Holmes~\cite{hall03} compare the
WRAPPER to several other column pruning methods including principle
component analysis (PCA- a widely used technique).  Column pruning
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 pruning.
\ei
PCA
is unique since it {\em does not} make
special use of the target attribute. WRAPPER is also unique, but for
different reasons: unlike other pruning methods, it {\em does} use the
target learner as part of its analysis. Hall and Holmes found that
PCA was one of the worst performing methods (perhaps because it
ignored the target attribute) while WRAPPER was the best (since it can
exploit its special knowledge of the target learner).


\section{Cost Modeling with COCOMO}

Before pruning data, we first need to understand how cost models might use that data.
This study uses COCOMO for our cost modeling.
COCOMO stands for
Constructive Cost Model~\cite{boehm81, boehm00b}.
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. 
One advantage of COCOMO (and this is why we use it)
is that unlike other many other costing models such as SLIM or SEER,
COCOMO is an {\em
open model} with numerous published data~\cite{boehm81, boehm00b}.




%\vspace{6 pt}


There are two versions of COCOMO: COCOMO-I and COCOMO-II.  In going
from the 1981 COCOMO-I 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.


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. More specifically,
\eq{one} shows the COCOMO~I model~\cite{boehm81}:

{\scriptsize
\begin{equation}\label{eq:one}
months=a*\left(KSLOC^b\right)*\left(\prod_jEM_j\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%



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


Here,
$EM_i$ is one of 15 
{\em effort multipliers} such as {\em cplx} (complexity)
or {\em pcap} (programmer capability).
The COCOMO-I effort multipliers are shown defined in \fig{em} and their
numeric values are shown in \fig{effortmults}.
In COCOMO-II, the number of effort multipliers changed from 15 to 17.


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


In the COCOMO-I
model, $a$ and $b$ are domain-specific variables and KSLOC (thousands of lines
of non-commented source code)
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).

%\vspace{6 pt}

A standard method for assessing COCOMO performance is
PRED(30). 
PRED(30) is calculated from 
the relative error, or RE, which is the relative
size of the difference between the actual and estimated value:

{\footnotesize
\[
RE = \frac{estimate - actual}{actual}
\]}

The mean magnitude of the relative error, or MMRE, is the average percentage
of the absolute values of the relative errors over an entire data sets.
PRED(N) reports the average percentage of estimates that were within
N\% of the actual values. If a data set has $R$ rows, then:

{\footnotesize
\[
PRED(N) = \frac{100}{R} \sum_i^R\left\{
\begin{array}{l}
1\;if\;MRE_i\;{\le}\;\frac{N}{100}\\
0\;otherwise
\end{array}\right.
\]}

For example, a PRED(30)=50\% means that half the estimates are within
30\% of the actual.  Note that, we report results in terms of PRED(N),
not MMRE. This is a pragmatic decision- we have found PRED(N) easier
to explain to business users than MMRE. Also, there are more PRED(N)
reports in the literature than MMRE. This is perhaps due to the
influence of the COCOMO researchers who reported their 1999 landmark
study using PRED(N)~\cite{chulani99}. Further, we report here PRED(30)
results since the major experiments of that 1999 study also used
PRED(30). The results for PRED(25) are similar with those for PRED(30)
except that the accuracies for PRED(30) is a little better than those
for PRED(25).

In order to use
the linear least squares regression, which is the most widely used
and the simplest modeling method, it is common to transform
COCOMO model into
linear model by taking the logs of \eq{one}.

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

Note that, if \eq{twol} is used, then {\em before} computing PRED(N), the
estimated effort has to be converted back from a logarithm.



\section{Case Study Data}
This study uses datasets in both COCOMO-I and COCOMO-II format:
 \bi
\item
The {\em cii0} data set was used to build the  COCOMO-II model.
\item
The {\em cii4} data 
set is also in the COCOMO-II format and includes the 72 projects from {\em cii0}
developed after 1990, plus 47 new projects.
\ei
The COCOMO-II data is not published since it was
collected on condition of confidentiality with the companies supplying
the data. Further research must be conducted in terms of the same
conditions.
In contrast, several COCOMO-I data sets are available
in the PROMISE repository~\cite{Sayyad-Shirabad+Menzies:2005}: 
\bi
\item
{\em Coci}  comes from the  COCOMO-I text~\cite{boehm81}
and includes  data from a variety of domains
including engineering, science, financial, etc.
\item
{\em
na60} comes from 20 years of NASA projects and is recorded using
the COCOMO-I variables.
\ei
The {\em na60}  data  can be stratified into the following data sets:
\bi
\item  {\em c01,c02,c03} store data from three different NASA geographical locations;
\item {\em p02,p03,p04} stores data from three different NASA projects;
\item {\em t02,t03} stores data from two tasks such as
ground data receiving and flight guidance.
\ei
For reasons of
confidentiality, the exact details of those centers, tasks, and
projects cannot be disclosed.  The other centers, projects, and tasks
from {\em na60} were not included in cX, pX, or tX 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 coci} describes projects
from before 1982; 
{\em cii4} contain  data from the most recent projects; and the NASA data
sets ({\em na60, pX,cX,tX}) described projects newer than {\em coci}
and before {\em cii4}.
Also, the COCOMO-I data sets ($coci,na60,c01,c02,c03,p02,p03,p04,t02,t03,call,pall,tall$)
have the 15 columns of \fig{em} 
 COCOMO-II data sets ($cii0, cii4$) have 24 columns.


For experimental purposes, we group the above as follows:
\bi
\item {\em call} combines {all} the center data; i.e. $call=c1+c2+c3$;
\item {\em tall} combines {all} the task data; i.e. $tall=t02+t03$;
\item {\em pall} combines {all} the project data; i.e. $pall=p02+p03$;
\ei

\section{Experimental Method}

Having described COCOMO, the WRAPPER, and our data sets,
we can now describe how an analyst can use them all together
to find better cost models.

Column pruning using the WRAPPER
was discussed above.
Recall that the WRAPPER sorts
columns are
sorted left-to-right according how well
that column's variable predicts for the target variable (in our case,
software development effort).  Column pruning then proceeds left to
right across the sorted columns, each time removing some less-useful
left-hand-side columns.  At each step of the pruning, a cost model is
learned from the remaining columns. Column pruning stops when removing
more columns does not improve the best result seen so far.


To find the relative value of each column, we ran the WRAPPER ten
             times (each time using a randomly selected 90\% of the
             rows).  The value of a column was then set to the number
             of times the WRAPPER selected that column.

Once the WRAPPER ordered the columns, we randomized the order of the
rows and starting column pruning.  To ensure statistical validity,
randomization (followed by column pruning) was repeated 30 times.  

For each repeat, at each stage of the pruning, the lowest value column
was removed.  The rows in the remaining columns were then divided into
training and test sets (each time using a randomly selected 67\% of
the rows for the training set). A cost model was learned (using linear
regression) from the training set and then assessed, using PRED, on
the test set.

Once the 30 repeats were completed, a best model was selected by
looking at the mean and standard deviation of model performance at
each pruning step.  The best model was the one that t-tests confirmed
out-performed all the other states of the column pruning. The mean
value of that model over the 30 repeats was then reported.

The above process us fully automated using our own Unix scripts which
control a JAVA data mining library called the
WEKA~\cite{witten99}. The WEKA comes complete with a linear regression
learner and an implementation of the WRAPPER. The whole system is
available from the authors.


\section{Results}

\begin{figure}
{\footnotesize
\begin{center}
\includegraphics[width=6in]{pruned.pdf}
\end{center}}
\caption{Number of columns.}\label{fig:prunep}
\end{figure}

The results of our column pruning are shown in \fig{prunep}.  The red
and green lines of show the number of columns in our data sets before
and after pruning. The data sets are on the x-axis.  The $before$
values are 22 for the COCOMO-II data sets ($cii0$ and $cii4$) while
the $before$ values for the COCOMO-I data sets are all 15.  The blue
line shows the percentage of the $before$ columns removed by pruning.
For example, very little was pruned from $cii$ while most of the columns were
pruned from $p03$.  On average, over 65\% of the columns were
pruned. Sometimes, the pruning was quite heavy with over 80\% of the
columns pruned away.

\begin{figure}[!t]
{\footnotesize
\begin{center}
%Results from Schofield~\cite{shepperd97}&~&Results from this paper\\\cline{1-1}\cline{3-3}
\includegraphics[width=1.75in]{colp.pdf}\includegraphics[width=1.75in]{lightRowColp.pdf}\includegraphics[width=1.75in]{heavyRowColp.pdf}
\end{center}}
\caption{Effects on PRED of
different pruning methods. 
For space reasons,
only the PRED(30) results are shown. A longer version of this paper, in preparation,
includes PRED(20) and PRED(25) results.
}\label{fig:rowp}
\end{figure}

A concern with such large scale pruning is that the resulting models would be
somehow sub-standard. This proved not to the case.
The PRED(30) results associated with the pruned data sets are shown
 in \fig{rowp}. This figure shows  mean values in 30 experiments where
the learned model was tested on rows not seen during training. Note that pruning
{\em always} improved PRED.


The red lines on \fig{rowp} show the mean PRED(30) seen in 30 trials using all the columns.
These are the baseline results
for learning  cost models {\em before} applying any pruning method.
The green lines show the best mean PRED(30) seen {\em after} automatic column pruning.
The difference between the red and the green lines is the improvement produced by pruning.

The data sets are sorted by pruning method into three plots.  Within
each plot, the data sets are sorted left-to-right in increasing value
of $\frac{after-before}{before}$.  The x-axis shows the names of the
data sets used in these studies.  The blue lines show the number of
rows in each data set.  

The plots of \fig{rowp} have three labels: ``pruning just columns'',
``pruning columns and some rows'', and ``pruning columns and many
rows''.  The data sets are sorted into three labels according to their
stratification.  The left-hand-side
results, labeled ``pruning just columns'', come
from the largest data sets that combing project information form many
sources (i.e. $cii0,cii4,coc1,na60$). These data sets are not divided
up into data from similar sources. Hence, there is no row pruning used
on these data sets.  

The right-hand-side results, labeled ``pruning columns and many rows'',
come from eight data sets that have been heavily stratified into just
specific NASA centers (i.e. $c01,c02,c03$); or specific NASA projects
(i.e. $p01,p02,p03$); or specific NASA software tasks
(i.e. $t02,to3$).

The middle results, labeled ``pruning columns and some rows'', show data
sets that have been somewhat stratified. The data sets in this group
combine together data from either:
\bi
\item
All the NASA centers (i.e. $call$); 
\item
Or all the
NASA projects (i.e. $pall$); 
\item
Or all the NASA tasks (i.e. $tall$).
\ei
This
middle group samples a point half-way between the unstratified data
sets on the left and the heavily stratified data sets on the right.

Three are three features of \fig{rowp}:
\be
\item
Pruning {\em always} improved estimation effectiveness.  
That is,
in all our case studies, it was {\em always} useful to ignore a portion 
of the available data.
\item
Column pruning by itself can offer some improvements to PRED. However,
column pruning combined with row pruning can result in dramatic
improvements of effort estimation.
\item
With one exception ($c03$), the general trend across the three graphs
is clear: as data set size {\em shrinks}, the improvement {\em
increases}. That is, pruning is most important when dealing with small data sets.
\ee

\section{When Not to Prune}

While column pruning is clearly useful, sometimes it cannot
or should not be applied.
Firstly, our variable subtraction methods require an historical
database of projects.  If there is {\em no} such database, then our
column pruning techniques won't work.

Secondly,
even if a historical database exists and our techniques suggest
pruning 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 prune variables is that you still
might need them.  For example, the experiments shown above often
subtract over half of the attributes in a COCOMO-I model while
(usually) improve effort estimation.
However, suppose that a business decision has to be made using some of
the pruned 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

Hence, we propose using column pruning with some care.  If there is no
historical data for learning specialized data sets, then managers
should use the general background knowledge within COCOMO.  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 managers
could tune the general COCOMO background knowledge by 
adjusting the coefficients  within the COCOMO equations.
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 toolkit methods requires more effort
(i.e. some UNIX scripting) than local calibration.  \fig{rowp}
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{me05a}.
Nevertheless, column pruning
is {\em
not} appropriate when there are business reasons to use all available
variables (e.g. the three reasons  described above).

\section{Conclusion}

The specific goal of this paper was to encourage more column pruning
in cost modeling, particularly when dealing with very small data sets.
The improvements seen in \fig{rowp} seem quite impressive. Row and
column and pruning, in combination, are very useful for cost modeling-
particularly when dealing with small data sets.  Hence, we propose a
change to current practice.  Cost models {\em should not} be  built using all
available data. Rather, {\em after} data collection and {\em before}
model building, cost modelers perform some data pruning experiments.

The more general goal of our work is to encourage repeatable,
refutable, and improvable experiments in software engineering. To that
end, as much as possible, we use public domain tools and public domain
data sets.  Hence, this paper uses a 
open source cost model (COCOMO) and, as much as possible,
publicly available data. 
All the COCOMO-I data sets used in this study
can be downloaded from the PROMISE
repository~\cite{Sayyad-Shirabad+Menzies:2005}. We urge other
researchers to produce more results  based on open source models and data sets.

\section*{Acknowledgments}

The advice of the anonymous reviewers helped to clarify an earlier draft
of this paper. 
Helen Burgess offered invaluable editorial assistance. 

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

\end{document}


%% \section{Discussion}

%% What makes this paper unique is a focus on column pruning software cost data
%% for very small data sets.
%% The benefits of column pruning has been shown in many
%% domains~\cite{miller02,hall03}. However, 
%% With exception of one study by
%% Kirsopp and Shepperd~\cite{kirsopp02}, we are the first to study the
%% effects of column pruning on cost estimation. 

%% ** preset experiment in a reporducible way. public doamin data sets and tools
%% ** larger effects that what has been previously reported
%% ** prior researchers have focused on just throwing away columns ~\cite{miller02,hall03} or just throwing away
%% rows (XXX boehm). here, we do both.


%% generality: use cocomo cause it is the most freely available.

%% usefulness: fully authomatic. stopping criteria automated

%% beyond just cocomo: possibly.

%% repeatable: (shepherd)

%% more practical: smaller data sets that seen before (shepherd)

%% why not more data?

%% Yet those experiments Data collection from real-world software engineering
%% projects is notoriously difficult. This is understandable:
%% Software projects are notoriously difficult
%% to control.   The Standish group reported in 2001 that
%%  23\%
%% of software development
%% projects totally fail, 28\% meet all expectations,
%% and the remaining 49\% were significantly challenged in some way
%% (e.g. ran out of time, ran out of budget, did not deliver the required
%% features)~\cite{standish01}.
%% Corporations are therefore  very reluctant to expose their own 
%% less-successful software
%% development practices to public scrutiny.




%% Here, we argue that better software cost models can be generated
%% by pruning rows {\em and} columns.  In the case studies shown below, 

%% ``Feature subset
%% selection''~\cite{hall03,miller02} is a method that scores each 
%% column according to how well that column's variable  predicts for the target value 
%% (which, in our work, is the software development effort). The columns of the data are then
%% re-ordered, left to right, lowest scoring to highest scoring. For example, the columns
%% in the above table might be re-ordered as follows:


%% There is
%% a good reason for this.  
%% This , while surprising, is supported by much theory and
%% much experiments. This article shows some of that theory and some new
%% experiments where we selectively remove Some of those experiments are
%% shown in this article. In


%% Ideally, a good software cost model

%% XXX data straved problem
%% XXX accessing data

%% XXX propose a somewhat counter-intuiative solution. ignore data

%% XXX two directions of data reduction: less rows, less
%% columns. suprisingly, it can be helpful to throw away BOTH rows and
%% columns. while this result may seem surprising, we show ehre that it
%% is well backed by theory and numerous experiments. Our contribution is three-fold:


%% As we learn more about software, the number of variables in those
%%     models tends to grow. In going from the 1981 COCOMO model~\cite{boehm81} to
%%     the 2000 COCOMO II model~\cite{boehm00b}, one variable, ``Turnaround Time'', was
%%     dropped to reflect the almost-universal use of interactive
%%     software development.  Another variable, ``Modern Programming
%%     Practices'', was dropped in favor of a more general ``Process Maturity''
%%     variable. But several more variables were added to reflect the
%%     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 variables, 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.  


%% \section{XXX}

%% 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 data sets are so small that this search
%% did  not take 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 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  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:onea}
%% 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 variables and KSLOC (thousands of lines
%% of non-commented source code)
%% 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, a 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}

%% Our 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} showed
%% 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 set is  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,
%% certain landmark studies  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
%% ``wins'' and ``losses''.  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 losses''
%%  (and if two sets
%% score the same ``total wins - total losses'', 
%% 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 a down side to always conducting feature subtraction (but
%% see of final section-
%%  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{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).


%% \section{Discussion}


%% 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 if 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 variables due to their
%% wide usage and acceptance in the IFPUG community.

%% A third 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 containing $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).
%% that seems to run contrary to much of 
%% our own research:
%% \be
%% \item
%% As part of the COCOMO project, Boehm has been collected
%% software costing data from his industrial partners for
%% decades~\cite{boehm81,boehm00}. 
%% \item
%% Port is a member of the
%% HACKYSTAT project that instruments open source development tools in
%% order to validate metrics for software
%% development\footnote{\url{http://csdl.ics.hawaii.edu/Tools/Hackystat/}}
%% \item
%% Menzies founded the PROMISE project (with Jelber Sayyad Shirabad) 
%% that collects and
%% maintains public domain data sets relating to software
%% engineering\footnote{\url{http://promise.site.uottawa.ca/SERepository/}}.
%% \ee

%% % LocalWords:  occored saperate improvable
