\documentclass{svjour3}                     % onecolumn (standard format)
%\documentclass[smallextended]{svjour3}     % onecolumn (second format)
%\documentclass[twocolumn]{svjour3}         % twocolumn
%
\smartqed  % flush right qed marks, e.g. at end of proof
%
\usepackage{graphicx}
\usepackage{verbatim}
\usepackage{fancyvrb}
\usepackage{algorithmic}
\usepackage{cite}
\usepackage{multirow}
\usepackage{rotating}
\usepackage{subfigure}
\usepackage{float}
\restylefloat{figure}
\usepackage{times}
\usepackage{algorithm}

\newenvironment{smallitem}
 {\setlength{\topsep}{0pt}
  \setlength{\partopsep}{0pt}
  \setlength{\parskip}{0pt}
  \begin{itemize}
  \setlength{\leftmargin}{.2in}
  \setlength{\parsep}{0pt}
  \setlength{\parskip}{0pt}
  \setlength{\itemsep}{0pt}}
 {\end{itemize}}

\newenvironment{smallenum}
 {\setlength{\topsep}{0pt}
  \setlength{\partopsep}{0pt}
  \setlength{\parskip}{0pt}
  \begin{enumerate}
  \setlength{\leftmargin}{.2in}
   \setlength{\parsep}{0pt}
  \setlength{\parskip}{0pt}
  \setlength{\itemsep}{0pt}}
 {\end{enumerate}}


\usepackage[table]{xcolor}
\usepackage{url,graphicx}
\newcommand{\G}{\cellcolor[rgb]{0.8,0.8,0.8}}
\newcommand{\fig}[1]{Figure~\ref{fig:#1}}
\newcommand{\eq}[1]{Equation~\ref{eq:#1}}
\newcommand{\hyp}[1]{Hypothesis~\ref{hyp:#1}}
\newcommand{\tion}[1]{\S\ref{sec:#1}}

\newcommand{\bi}{\begin{smallitem}}
\newcommand{\ei}{\end{smallitem}}
\newcommand{\be}{\begin{smallenum}}
\newcommand{\ee}{\end{smallenum}}
\newcommand{\bd}{\begin{description}}
\newcommand{\ed}{\end{description}}



\begin{document}

\title{Where is the best effort estimator?%\thanks{Grants or other notes
%about the article that should go on the front page should be
%placed here. General acknowledgments should be placed at the end of the article.}
}
\subtitle{Investigation of stability}

%\titlerunning{Short form of title}        % if too long for running head

%\author{Ekrem Kocaguneli        \and
%        Tim Menzies \and
%        Jacky W. Keung
%}

%\authorrunning{Short form of author list} % if too long for running head

%\institute{E. Kocaguneli and T. Menzies\at
%              Lane Department of Computer Science and Electrical Engineering \\
%              West Virginia University\\
%              Morgantown, WV 26505, USA\\
%              \email{ekocagun@mix.wvu.edu, tim@menzies.us}
%           \and
%           Jacky W. Keung \at
%              School of Computer Science and Engineering\\
%              University of New South Wales\\
%              Sydney, Australia\\
%              \email{jacky.keung@nicta.com.au}
%}

\date{Received: date / Accepted: date}
% The correct dates will be entered by the editor


\maketitle

\begin{abstract}
\input{abstract}

\keywords{Effort estimation, Data mining, Stability, Linear Regression, Regression Trees, Neural Nets, Analogy, MMRE, Evaluation Criteria}
\end{abstract}

\section{Introduction}

For decades, researchers have been seeking the ``best'' software development effort estimator.
To date, no such ``best'' estimator has been found. 
The usual conclusion is that effort estimation suffers from a {\em conclusion instability}
problem; i.e. different researchers offer conflicting rankings as to what is 
``best''~\cite{shepperd01b,myrtveit05}.

This is an open and urgent
issue since accurate effort estimation is vital to Software
Engineering, and is often a challenging task for many software
project managers. Both overestimating and underestimating would
result unfavorable impacts to the business's competitiveness and project resource
planning. 

%The literature reports many  effort estimation methods.
%For example, if we just look at instance-based methods,
%\fig{cbr} lists thousands of  
%algorithms  for instance-based effort estimator. 
%A similiar list for model-based 
%effort estimation would be just as long
%(and include 
%linear regression, regression trees, neural nets, etc.).
%
\input{ekrem/combination-algorithms}

Effort estimation research focuses 
on the
{\em learner} used to generate the estimate (e.g. linear regression, neural nets, etc)
in many cases, overlooking the importance of the quality and characteristics of  the {\em data} being used
in the estimation process. We will argue that this approach is somewhat misguided since, as shown below, learner
performance is greatly influenced by the data preprocessing and the datasets being used to  evaluate the learner.
This paper shows that many datasets used by prior publications are very  limited in number
to distinguish {\em strong/weak} datasets. 
%All the results based on these {\em weak} datasets
%(including many results by the authors of this papers) must hence be revisited.

%The good news is that there are {\em strong} datasets that clearly
%illustrate the value of any estimator.  
In all, this study
applies 90 estimators to 20 datasets and measures their performance
in terms of seven different performance criteria.  To the best of
our knowledge, this is the largest effort estimation study yet
reported in the literature. One result of exploring such a large
space of data and algorithms is that we 
can report stable conclusions (while prior studies have not).

This  paper is structured as follows.
In Motivation, we specifically address our motivations.
Related work discusses effort estimation and the prior reports on {\em conclusion instability}.
Those reports used a
dataset to {\em seed} the generation of artificial data. Our results section shows that
if we extend the experiments to a broader set of methods and project data, 
we are able to discover stable conclusions such as
that we can list best (and worst) effort estimators; on the other hand, we need more datasets to make a similar claim of \textit{strong/weak} datasets.
%some datasets are {\em weak}; and that the {\em strong} datasets
%show which estimators are consistently better than others.
%Based on those results, our conclusion will list best (and worst)
%  effort  estimators.
  
\input{ekrem/motivation}

\section{Related Work}


\input{jacky/related}
\input{ekrem/accuracy}

\section{Experiment Design}
In our experiments, numerous performance measures were collected after
various {\em algorithms} (combinations of preprocessors and learners) were applied
to the data of \fig{datasets}. 
This section describes those performance measures,
preprocessors, and learners.

Since it
is impractical to explore (say) the thousands of options
described in \fig{cbr}, 
we elected to explore variants
commonly used in the literature.  For example,
we explore neural nets, regression, and analogy
because those methods were explored by Shepherd and Kododa~\cite{shepperd01b}.
Nevertheless, it is important to note that our conclusions come
only from the estimators/performance criteria/datasets used in this
study.  Further work is required to confirm our findings on other
estimators/performance criteria/datasets.

\subsection{Performance Measures}
Performance measures comment on the success of a prediction.
For example, the absolute residual (AR) is the difference between the predicted and the actual:
{\begin{equation}\label{ar}
AR_i={x_i-\hat{x_i}}
\end{equation}}
(where $x_i,\hat{x_i}$ are the actual and predicted value for test instance $i$).

The Magnitude of Relative Error measure a.k.a. MRE is a very widely used evaluation criterion for selecting the best effort estimator from a number of competing software prediction models\cite{shepperd97}\cite{foss03}. MRE measures the error ratio between the actual effort and the predicted effort and can be expressed as the following equation:  
{\begin{equation}\small\label{one}
MRE_i=\frac{\mid{x_i-\hat{x_i}}\mid}{{x_i}} = \frac{\mid{AR_i}\mid}{{x_i}}
\end{equation}}
A related measure is MER (Magnitude of Error Relative to the estimate \cite{foss03}):
{\begin{equation}\label{one}
MER_i=\frac{\mid{x_i-\hat{x}_i}\mid}{\hat{x}_i} = \frac{\mid{AR_i}\mid}{\hat{x}_i}
\end{equation}}

The overall average error of MRE can be derived as the Mean or Median Magnitude of Relative Error measure (MMRE, or MdMRE respectively), can be calculated as: 

{\begin{eqnarray}\small\label{one}
MMRE={\sum_{i=1}^n   MRE_i\over {n} } \\
MdMRE={median(all MRE_i) }
\end{eqnarray}}


A common alternative to MMRE is PRED(25), and defined as the percentage of predictions failing within 25\% of the actual values, and can be expressed as:
{\begin{equation}\small
PRED(25) = \frac{100}{N}\sum_{i=1}^N\left\{\begin{array}{ll}
\mbox{1 if $MRE_i \le \frac{25}{100}$}\\
\mbox{0 otherwise}
\end{array}\right.
\end{equation} 
}
For example, PRED(25)=50\% implies that half of the estimates are failing within 25\% of the actual values \cite{shepperd97}.

There are many other performance measures including Mean Balanced Relative Error (MBRE) and the Mean Inverted Balanced Relative Error (MIBRE) studied by Foss et al.~\cite{foss03}:

\begin{equation}\small
MBRE_i = \frac{\hat{x_i} - x_i}{min(\hat{x_i},x_i)}
\end{equation} 

\begin{equation}\small
MIBRE_i = \frac{\hat{x_i} - x_i}{max(\hat{x_i},x_i)}
\end{equation} 


\input {ekrem/pre-processor}
\input {ekrem/learner}


\subsection{Experimental Rig}

This study copied the experimental rig of a recent prominent study~\cite{LiandRuheAtPRomise2007}.
In their
leave-one-out experiment, given $T$ projects, then $\forall t \in T$, $t$ is the  test  and the remaining 
$T-1$ projects are used for  training. The resulting $T-1$ predictions are then used 
to compute our seven evaluation criteria given in Section 3.1.

To compare the performance of one algorithm versus the rest, we used a Wilcoxon
non-parametric statistical hypothesis test.
Wilcoxon is
more robust than the Student's {\em t}-test as it compares the sums
of ranks, unlike Student's {\em t}-test which may introduce spurious
findings as a result of presence of outliers may be existed in the
given datasets. Ranked statistical tests like the Wilcoxon are also
useful if it is not clear that the underlying distributions are
Gaussian~\cite{kleijnen97}. 
%For example in a ranking analysis, the
%raw results (10.2, 21.3, 22.1, 24, 25, 30, 100) are replaced with
%their ranks in the sort order; i.e.  (1, 2, 3, 4, 5, 6, 7).

Using the Wilcoxon test, for each dataset, the performance measures
collected from each of our 90 algorithms was compared to the 89
others. This allowed us to collect {\em win-tie-loss} statistics using
the algorithm of  Figure \ref {FigureWinTieLossPseudocode}.  
First,
we 
want to check if two
distributions $i, j$ are statistically different according to the
Wilcoxon test (95\% confident);  otherwise we increment $tie_i$ and $tie_j$. 
If the distributions are statistically different, we update $win_i,win_j$
and $loss_i,loss_j$ after comparing their median
values. 
\begin{figure}[!h]
\renewcommand{\baselinestretch}{1}
\begin{algorithmic} \footnotesize
\IF{~WILCOXON(\textit{$P_i$}, \textit{$P_j$}, 95) says they are the same}
	\STATE \textit{$tie_{i}$} = \textit{$tie_{i}$} + 1;
	\STATE \textit{$tie_{j}$} = \textit{$tie_{j}$} + 1;
\ELSE
   	\IF{~better( median(\textit{$P_{i}$}), median(\textit{$P_{j}$}))}
   		\STATE \textit{$win_{i}$} = \textit{$win_{i}$} + 1
   		\STATE \textit{$loss_{j}$} = \textit{$loss_{j}$} + 1
   	\ELSE
   		\STATE \textit{$win_{j}$} = \textit{$win_{j}$} + 1
   		\STATE \textit{$loss_{i}$} = \textit{$loss_{i}$} + 1 \ENDIF \ENDIF
\end{algorithmic}
\caption{Comparing algorithms (\textit{i},\textit{j})
on performance ($P_i$,$P_j$). The ``better'' predicate changes according to $P$.
For error measures like MRE, ``better'' means lower medians. However, for PRED(25),
``better'' means higher medians.}
\label{FigureWinTieLossPseudocode}
\end{figure}


\input{ekrem/algorithm-ranks}
\section{Results}
After applying leave-one-out to all 20 data sets,
the procedure of  Figure \ref {FigureWinTieLossPseudocode} was repeated seven times
(once for MAR, MMRE, MMER, MBRE, MIBRE, MdMRE and PRED(25)).
Our ninety algorithms were then sorted by their total number of losses over all datasets.
The resulting sort order is shown in \fig{res_rank}.
The algorithm, with fewest
losses ({\bf norm/CART(yes)}) was ranked \#1 and the
algorithm with the most losses ({\bf PCA/LReg}) was ranked 
\#90.


Given 89 comparisons and seven performance measures and 20 datasets, the maximum
number of losses for any algorithm was $89\times7\times20=12,460$. 
\fig{error_methods} 
sorts all 90 algorithms according to their
 total losses seen in all seven
performance criteria (expressed as a percentage of 12,460).
The {\em x-index} of that figure corresponds to the ranks of \fig{res_rank};
e.g. the top ranked
method of {\bf norm/CART(yes)} lost in nearly zero percent of our experiments.



\begin{figure}[!h]
\begin{center} \includegraphics[width=3in]{lib/rows.pdf} \end{center}
\caption{The ninety algorithms of \fig{res_rank}, sorted
by their
percentage of maximum possible losses (so 100\% = 12,460). }\label{fig:error_methods}
\end{figure}

%In \fig{error_datasets}, we report percentage of {\em losses} for each error measure separately, instead of the {\em losses} reported above.
%The maximum number of wins for any dataset over ninety algorithms per error measure is $89\times90=8,010$. 
%\fig{error_datasets} sorts all 20 data sets by their total wins
%in all 
%seven performance criteria separately (expressed as a ratio of $8,010$). For example,
%with 
%the TELECOM dataset, all 90 methods rarely won.
Similarly, the maximum number of losses for any dataset over ninety algorithms is $89\times7\times90=56,070$. 
\fig{error_datasets} sorts all 20 data sets by their total losses
in all 
seven performance criteria (expressed as a ratio of 50,070). For example,
with 
the TELECOM dataset, all 90 methods rarely lost.

%\begin{figure}[!b]
%\begin{center} \includegraphics[width=3in]{lib/cols-win-all-together.pdf} \end{center}
%\caption{Total wins seen in 20 datasets, expressed as a percentage
%of the maximum number of possible wins seen for one datasets (so 100\%=8,010).}\label{fig:error_datasets}
%\end{figure}

\begin{figure}[!b]
\begin{center} \includegraphics[width=3in]{lib/cols.pdf} \end{center}
\caption{Total losses seen in 20 datasets, expressed as a percentage
of the maximum number of possible losses seen for one datasets (so 100\%=50,070).}\label{fig:error_datasets}
\end{figure}

\fig{rank_changes_dataset} is somewhat a continuation of \fig{error_datasets}, in the sense that it deals with the stability of datasests.
To test the stability, we question the mean of maximum rank change among datasets, when sorted w.r.t. $win$, $tie$, $win-loss$ over 7 error measures.
\fig{rank_changes_dataset} shows that the maximum value of mean-rank change is $18$, i.e. a method ranked as $2^{nd}$ in one scenario can rank as $20^{th}$ in another scenario.
Therefore, with that amount of datasets, it is not healthy to propose {\em strong} or {\em weak} datasets that always attain lowest/highest performance values.
If a dataset can change its position with a $+x$ or $-x$ amount, then there is a need for a window size of at least $2x$ and possibly some more datasets to actually observe how datasets would rank.

%\fig{rank_changes_dataset} distinguishes 3 regions when we impose a less than 10 mean rank change line.
%In these 3 regions, only $r2$ has datasets with less than 10 mean rank change.
%$r2$ contains 9 different datasets from cocomo81o to desharnais.
%When we impose these 3 regions onto \fig{error_datasets}, we see that stable datasets fall between the loss percentages of $5\%$ to $15\%$ (see dashed lines).

\begin{figure}[!b]
\begin{center} \includegraphics[width=0.7\textwidth]{lib/rank-changes-dataset.pdf} \end{center}
\caption{Datasets and the mean of their maximum rank changes over all performance measures w.r.t. $win$, $loss$ and $win-loss$ values. Some datasets have lower rank-changes. However, the maximum mean-rank change is around $18$ and we need more than $2 \times 18 = 36$ datasets to claim an order, hence strong/weak rekationship, between datasets.}
\label{fig:rank_changes_dataset}
\end{figure}

In a similar fashion, \fig{rank_changes} tests the stability of the methods.
In this plot, we check if the sort orders are changed by different performance criteria:
\bi
\item
In \fig{rank_changes}, we report the mean of maximum rank changes for each method with respect to their ordering in \fig{res_rank}. 
\bi
\item Each error measure defines its own ordering of methods w.r.t. its $win$, $loss$ or $win-loss $ values.
\item Maximum rank change is the maximum absolute difference between either of these orderings and the ordering of \fig{res_rank}.
\item Then, mean of maximum rank changes coming from 7 performance measures gives us \fig{rank_changes}.
\ei
\ei
The sort order on the x-axis of \fig{rank_changes} was kept the same as the
before. 
A line drawn parallel to x-axis at $y=10$ gives methods, whose mean rank change is less/more than 10.
See in \fig{rank_changes} that $y=10$ line divides all methods into 3 regions: $a$ (from method 1 to 13), $b$ (from method 14 to 64) and $c$ (from method 65 to 90).
Regions $a$ and $c$ show \textit{``high-ranked''} and \textit{``low-ranked''} methods respectively.
None of the methods in regions $a$ and $c$ exceed mean rank change of 10, i.e. they are \textit{``stable''} in high and low ranks.
In region $b$ \textit{``medium-ranked''} methods are accumulated.
However, all methods in region $b$ have mean rank changes above 10, i.e. they are \textit{``unstable''} in this region.
In a result consistent with prior reports on conclusion instability, the lines in each region are not exactly smooth. 
However, they do closely follow the same general trends as \fig{error_methods} and \fig{error_datasets}. 


\begin{figure}[!b]
\begin{center} \includegraphics[width=0.7\textwidth]{lib/rank-changes.pdf} \end{center}
\caption{Algorithms and the mean of their maximum rank changes over all performance measures. Mean rank change of smaller than 10 divides 90 methods into 3 regions. Region a consists of high-ranked stable methods, whereas region \c contains low-ranked but still stable methods. Region b on the other hand shows middle-ranked and non-stable methods.}
\label{fig:rank_changes}
\end{figure}


\begin{figure}[!t]
\begin{center}
\includegraphics[width=2.7in]{lib/thinks.pdf} \end{center}
\caption[Dot-Plot]{Number of losses seen in 90 methods and 20 datasets.
expressed as a percentage of the maximum losses possible for one method
in one dataset (so 100\% =623; 50\%=311; 25\%=156; 12.5\%=78).
The algorithms on the y-axis are sorted according to 
\fig{error_methods}.
} \label{fig:dot-plot}
\end{figure}


Since the  sort orders seen using the number of losses and mean rank changes over seven performance criteria 
are
mostly stable, we use them to draw
\fig{dot-plot}. In that figure,
each {\em x,y}  position shows the results of 623 comparisons
(each algorithm compared to 89 others using seven performance measures; \mbox{$89\times7=623$}).
The 
{\em y}-axis of that figure shows the 90 
algorithms sorted in the rank order of \fig{res_rank}. For example,
the top-ranked algorithm {\bf norm/CART(yes)} appears at {\em y}=1;
the {\bf log/ABE0-1NN} result appears at {\em y}=12;
the {\bf log/LReg} results appear at {\em y}=80;
and the worst-ranked algorithm {\bf PCA/LReg} appears at {\em y}=90.

In order to discuss which learners/preprocessors are ``best'', we divide \fig{dot-plot}
into 3 bands of \fig{rank_changes}. 
We reserve the lowest band from method 1 to 13 (containing the ``best'' estimators)
for the region where all algorithms have a mean rank change of smaller than 10.
Note that algorithms in that region almost always lose less than $\frac{1}{8}$th
of the time (i.e. the rows $y=1$ to $y=13$ that are almost completely yellow in  \fig{dot-plot}).
In the other bands (boundaried at $y=14$ to $y=64$ and $y=65$ to $y=90$), algorithms lose much more frequently, i.e. behavior of methods in the loss percentage graph of \fig{dot-plot} are in agreement with rank change graph of \fig{rank_changes}.

\fig{error_pred_methods} shows the spectrum of PRED(25) values across the 3 bands. 
As might be expect, the y-axis sort order of \fig{error_pred_methods} predicts for estimation accuracy.
As we move over the three bands from worst to best, the PRED(25) values double (approximately), thus
confirming the unique performance of algorithms in each band.      
\begin{figure}[!t]
\begin{center} \includegraphics[width=2.5in]{lib/pred25s.pdf} \end{center}
\caption{Spectrum of Pred(25) across the bands}\label{fig:error_pred_methods}
\end{figure}


\fig{freq_method} shows the frequency counts of preprocessors and learners grouped into the five bands:
\bi
\item
A ``good'' preprocessor/learner appears often in the lower bands (tendency towards band a).
In \fig{freq_method},  CART is an example of a ``good'' learner.
\item
A ``poor'' preprocessor/learner appears more frequently in the higher bands (tendency towards band c).
In \fig{freq_method}, all the discretization preprocessors (e.g. {\bf freq3bin}) are ``poor'' preprocessors.
\item
The gray rows of \fig{freq_method} shows 
preprocessor/learner that are neither ``good'' nor ``poor'' (since they exist in all 3 bands have high frequency counts in bands b and c);
e.g. see the {\bf log} preprocessor.
\ei
\input{ekrem/position-summary}

\section{Discussion}

\subsection{Findings}

Based on these figures and results, we  summarize our findings as follows.

{\em Result1:} Observe how the majority
of the squares
on the left-hand-side of \fig{dot-plot} are yellow. 
In that mostly-yellow region, algorithms loss vary rarely against other
algorithms (in less that $\frac{1}{8}^{th}$ of all comparisons).
Also notice how higher loss percentages (more than $50\%$) become dominant on the right-hand-side.
For the purposes of finding the best effort estimator, the
data sets on the far left and right-hand-sides 
are not very suitable
%{\em weak}
 since they hardly  distinguish the performance of different algorithms.
However, to make a stronger claim as to which datasets are stronger or weaker, we need more publicly available datasets.
In our opinion, one future direction of research in effort estimation should be providing more publicly available datasets.

%Using engineering judgement,
%we use $10$ mean rank change to divide the ``weak'' and ``strong'' datasets
%(and acknowledge that 
%this rule is somewhat subjective).
%The  dashed lines  of  \fig{rank_changes_dataset},
%shows that this 10-mean-rank-change rule selects nine ``strong''
%data sets 
%(cocomo81o, desharnaisL1, cocomo81s, desharnaisL3, albrecht, cocomo81e, nasa93\_center\_5, desharnaisL2 and desharnais) 
%and excludes widely-used datasets such as albrecht, kemerer
%and
%telecom. 
%Note that while a data set may be ``weak'', it may contain
%``strong'' subsets. 
%For example, all subsets of cocomo81 are ``strong''.
%
%In our opinion, future research in effort estimation should use the stronger data sets
%and avoid the weaker ones.
%Also,
%we need to revisit
%all conclusions in prior publications  that are based on the weaker  data sets.
%As shown in
%\fig{dataranks}, there are many such  publications
%(including several written by the authors of this paper).
%
%
%\input{ekrem/data-in-literature}

%\begin{figure}[!t]
%\begin{center}
%\includegraphics[width=3in]{lib/mmres.pdf} \end{center}
%\caption{Median and mean MRE performance measurements from 90 estimation
%algorithms.
%} \label{fig:mmres}
%\end{figure}

{\em Result2:} 
Observing the small amounts of ``jitter'' in
\fig{rank_changes} we can see  that our results
are not 100\% stable, they are only sufficiently stable to draw conclusions. 
We conjecture that prior reports on conclusion instability could stem from using
too few data sets or too few algorithms.


{\em Result3:}
Observe how, in \fig{res_rank}, 
learners found at one rank with a one
preprocessor, can jump to a very different rank if the
different preprocessor is changed.
For example, the top-ranked method that uses {\bf CART(yes)}, is driven down to rank 60 if the preprocessor
is changed from norm to {\bf freq3bin}.
Clearly,
the
effectiveness
of
a
learner
can be significantly altered 
by seemingly trivial details relating to data preprocessing.
Hence, in future, researchers should explore  learners {\em and} the preprocessors, as they are both equally important.

{\em Result4:}
Observe in \fig{freq_method} how  {\bf SWR}, {\bf LReg} and {\bf NNet} are stand-out learners
in that fall entirely into the worst two bands. 
Proponents of these learners need to defend their value for  the purposes of effort estimation.

The relatively poor performance of simple linear regression is a highly significant result.
{\bf LReg}, with a log preprocessor,
is the core technology of many prior publications; e.g. the entire COCOMO project~\cite{Boehm1981}.
Yet as shown in \fig{dot-plot}, w.r.t. loss values over all error measures, {\bf log/LReg} ranks very poorly (position
80 out of a maximum of 90 algorithms).
We also did experiments at individual level of error measures.
At individual level the ranking is not very different either, i.e. the ranking of LReg w.r.t. loss values over MAR, MMRE, MMER, MBRE, MIBRE, MdMRE and Pred(25) are 80, 76, 81, 80, 75, 76 and 78 respectively.

{\em Result5:}
While
{\bf SWR} falls into the {\em worst two bands}
of the learners,
it is most commonly found in the {\em best two bands} of the preprocessors.
That is,  stepwise regression is a {\em poor learner} but a {\em good preprocessor}. 
Hence, in future, the fate of {\bf SWR} might be as an assistant to other algorithms.

{\em Result6:}
While simple regression methods like {\bf LReg} are depreciated by this study,
more intricate regression methods like regression trees (CART)
and partial linear regression {\bf PLSR} are found in the better bands.
Hence, in future, proponents of regression for effort estimation might elect to explore
more intricate forms of regression than just simple {\bf LReg}.

{\em Result7:}
The top-ranked algorithm was {\bf norm/CART}.


{\em Result8:}  
Simple methods (e.g. \textit{k}=1 nearest neighbor on the log 
of the numerics) perform nearly as well as the top-ranked algorithm.
\fig{error_pred_comp} compares the PRED(25) results between rank=12 and rank=1.
The datasets in that figure are sorted by the difference between the top-ranked and the twelfth-ranked
algorithm. 
Except for China dataset, the difference in PRED(25) values is either slightly negative, or positive.
That is, even though the rank=1 algorithm is {\em relatively} ``best'' (measured according to our comparative Wilcoxon tests),
when measured in an {\em absolute} sense,
it is not impressively better than simpler alternatives.
\begin{figure}[!th]
\begin{center}
{\scriptsize
\begin{tabular}{r|rr|r}
&norm/CART(yes)&log/ABE0-1NN& difference\\\hline
kemerer	&	7	&	27	&	-20	\\
desharnaisL3	&	20	&	40	&	-20	\\
nasa93\_center\_2	&	43	&	57	&	-14	\\
nasa93	&	29	&	39	&	-10	\\
cocomo81s	&	9	&	18	&	-9	\\
albrecht	&	33	&	42	&	-9	\\
telecom1	&	33	&	39	&	-6	\\
cocomo81	&	13	&	16	&	-3	\\
nasa93\_center\_5	&	36	&	33	&	3	\\
desharnaisL1	&	39	&	35	&	4	\\
cocomo81o	&	29	&	21	&	8	\\
desharnaisL2	&	48	&	40	&	8	\\
cocomo81e	&	18	&	7	&	11	\\
desharnais	&	43	&	32	&	11	\\
sdr	&	42	&	29	&	13	\\
miyazaki94	&	40	&	25	&	15	\\
maxwell	&	32	&	15	&	17	\\
finnish	&	61	&	37	&	24	\\
nasa93\_center\_1	&	58	&	33	&	25	\\
china	&	95	&	43	&	52	\\
\end{tabular}}\end{center}
\caption{Using all data sets to compare the Pred(25) of {\bf norm/CART}  (rank=1) and {\em log/ABE0-1NN}
(rank=12).}\label{fig:error_pred_comp}
\end{figure}


Result8 is an important result, for three reasons. Firstly, there are
many claims in the literature that software project follows a
particular parametric form. For example, in the COCOMO project,
that form is $effort\propto KLOC^x$)  The fact that non-parametric
instance methods perform nearly as well as our best method suggests
that debates about {\em the} parametric form of effort estimation
is misguided. Also, it means that the value of certain commercial
estimation tools based on a particular  parametric form may not be
much more than simple instance-based learners.

Secondly, analogy-based estimation methods are widely used~\cite{Auer2006,Walkerden1999,%
Kirsopp2003,shepperd97,shepperd96,Li2006,LiandRuheAtPRomise2007,
Li2009,%
keung2008a,keung2008b,keung2008c}. 
Result8 says that while this approach
may not be 100\% optimal in all cases,  
compared to our
best estimator found by this study,
there is not a dramatic lost if estimates are generated by analogy.
Prior to this publication,
we are unaware of a large comparative study relating to this matter.

Thirdly
it is easier to teach and experiment with simpler algorithms (like the {\bf log/ABE0-1NN}
algorithm at rank=12) than more complex algorithms (like the {\bf norm/CART} algorithm at rank=1).
For example, recently we have been experimenting with a very simple variant of ABE0-1NN that
is useful as a learner to find software process change~\cite{MenziesBrady10}. Such 
experimentation would have been hindered if we tried to modify the more complex CART algorithm
(particularly if we included sub-tree pruning).
% specifically, ten
%datasets (in common use  in the effort estimation literature)   are
%{\em weak}; i.e. poorly distinguish the behavior of different
%estimators.  
%
%
%Another result of interest is a comparison of the PRED(25) results seen in the five bands.
%\section{Analysis}
%\fig{error_pred_methods} shows PRED(25) values seen in all bands 
%%
%%
%%\subsection{The World is ``Flat''}
%%
%%We have observed over 50\% of the estimates have Wilcoxon losses less than 12.5\%, only a small fraction of the results with losses greater than 50\%.
%%In all 90 method combinations (Table \ref {table:res_rank}), CART ({\em Classification And Regression Tree}) had the least losses, that is, CART consistently achieves lower MRE values of all the methods using given datasets in the study. For top 10 method combinations, CART as a learner outperformed all other prediction models, such as Analogy and Linear Regression Analysis. 
%%
%%In addition to the given results shown in Table \ref{table:freq_method}, there are some interesting findings deserve some attention. Firstly, as mentioned above, CART performed consistently better than any other methods as a learner, this is evident in the learner section of Table \ref{table:freq_method}, where CART (subtree search) and CART (full tree search) ranked in the top according to the least losses in the race. Interestingly, the worst learners are the Regression methods (SWR, and LR) and the NeuralNet method (NNet).The best combinations is (simple max/min data normalization with CART). 
%%
%%Although SWR (stepwise regression) as a learner did not perform well, but as a pre-processor in the prediction system it is significantly important. Of the 90 different combinations, SWR leads to least losses combining with different learners. This is evident by its occurrence indicated in Table \ref{table:freq_method} showing a summary of position of methods, 2 SWRs exists in the top ranked category, and 4 exists in the 2nd top ranked category.   The 2nd most important data pre-processor is SFS (Stepwise Forward Selection). The implication in here is that combining SWR or SFS with any other learners will result in favourable prediction accuracy, as both stepwise procedures (SWR and SFS) are likely to statistically filter only the relevant project features for the learners to predict estimates. The finding coincides with Keung et al.'s work \cite{keung08a}, which argues the importance of a data preprocessor in software effort estimation, in their experiments, a stepwise feature selection system similar to that of SWR was adopted, results showing improved prediction performance as well. 
%%
%%Finally, a very important finding was found relating to different evaluation criteria. Our results show that regardless of the evaluation criteria used (AR, MRE, MMRE, MdMRE, PRED25 and MIMRE) they all lead to the same overall rankings of algorithms and datasets. 
%%The implication is that different evaluation criteria can be used, as using different evaluation criteria are statistically insignificant. This perhaps leads to the end of a continuous debate as to whether we should use MMRE, MdMRE, etc. or an alternative metric for comparing different prediction models. 
%%
%%From the dot-plot graph we can see that the contour data pattern showing that the "world is flat", especially based on the first few datasets such as telecom, kemerer, cocomo81o. The implication is that using different prediction models may result similar findings in most cases, again this is largely depends upon on the dataset characteristics and quality. In this study, dataset China is a cross-company dataset, performed worst among the 20 datasets, nevertheless, CART learner is still the preferred method which result in least losses. 
%
%Given similar estimates can be achieved using different methods, we are arguing that using a simpler solution may be adequate in most of the cases. 
%To support our claim, we compared ({\em simple max/min data normalization with CART}) with ({\em simple log norm.+ KNN=1}) measured by Pred(25) in Figure  \ref{fig:error_pred_comp}. As we have observed, except china and sdr datasets, the other differences are not significant. In particular, the two method combinations using albrecht and mizayaski94 datasets produced identical estimates.
%
%
%
%\subsection {Spectrum Analysis}
%Figure \ref{fig:error_pred_datasets}
%shows the estimation spectrum across all the datasets based on
%Pred(25), and a similar data pattern was formed in all 4 groups.
%
%Similarly Figure \ref{fig:error_pred_methods} evaluates the
%effectiveness of 90 different method combinations by grouping them
%into 5 categories. Method combination 1 to 8 performed the best
%among all 5 categories and a linear trend is present in each category.
%
%
%%\begin{figure} %\begin{center}
%%\includegraphics[width=3in]{lib/pred25sByData.pdf} \end{center}
%%\caption{Spectrum of Pred(25) across the
%datasets}\label{fig:error_pred_datasets} %\end{figure} \subsection
%{Error Estimates} Figure \ref {fig:error_methods} shows the total
%number of losses of each method, using all the datasets in the
%study. It clearly shows that there is a general conclusion that
%method 1-8 are performing consistently better than any other methods,
%method range 8-60 can maintain a similar number of losses for each
%method. Method range 60-90 performed badly. Method 1-8 belongs to
%the CART prediction family, consistently outperformed other methods.
%
%Figure \ref {fig:error_datasets} shows the total number of losses
%across the datasets.  The subtle increase in the graph was caused
%by the inclusion of the china dataset.  This suggesting some of the
%datasets should not be used for effort estimation, we recommend to
%avoid datasets with the number of losses > 10,000 cases, including
%dataset china, sdr, maxwell etc. as shown in Figure \ref
%{fig:error_datasets} .
%


\input{jacky/validity}

\section{Conclusion}
In this study, ten learners and nine data preprocessors were combined
 into 90 effort estimation algorithms. These
were applied to twenty datasets.
Performance
was measured using  seven performance indicators (AR, MRE, MER,
MdMRE, MMRE, PRED(25), MBIRE). Performances were compared using a
Wilcoxon ranked test (95\%).
To the best of our 
knowledge, this is the largest and most comprehensive effort estimation study yet reported 
in the literature. Eight results are noteworthy:
\be
\item %1
Our  datasets could be sorted according to how well
they can distinguish between  effort estimators; for that matter, there is a need for more publicly available datasets.
%specifically, eleven
%datasets (in common use  in the effort estimation literature)   are
%{\em weak}; i.e. poorly distinguish the behavior of different
%estimators.  
\item %2
Prior reports of conclusion instability about effort
estimation may have been overly pessimistic. Given relatively large number
of publicly  available effort estimation datasets, it is now
possible to make stable conclusions about the relative value of different effort estimators.
\item %3
The effectiveness of a learner used for effort
estimation (e.g. regression or analogy methods) can be significantly
altered by data preprocessing (e.g. logging all numbers or
normalizing them zero to one).  
\item %5
Neural nets
and simple linear regression perform much worse than other learners
such as analogy learners.  
\item %4
Stepwise regression was a very
useful preprocessor, but surprisingly a poor learner.  
\item %6
Non-simple regression methods such
as regression trees and partial linear regression are relatively
strong performers.   
\item %7
Regression trees that use tree pruning performed best of all in
this study (with a preprocessor that normalized the numerics into the range zero
to one).    
\item %8
Very simple methods (e.g. {\em K}=1 nearest neighbor on
the log of the numerics)  performed nearly as well as regression
trees.   
\ee
%Based on these results, our conclusions are:
%\bi
%\item
%Prior papers on effort estimation have not taken proper account of
%the data used to evaluate the effort estimator.  
%\item
%Conversely, future publications
%in effort estimation should take greater consideration to explore
%the characteristics of data and data preprocessing mechanisms (and not just the learner).
%\item
%Researchers need to revisit prior publications
%that used the weaker datasets (including numerous papers by the
%authors of this paper - see  \fig{dataranks}).
%%\ei
%%As to the more specific conclusions:
%\bi
%\item
%We recommend effort estimation using
%regression trees or analogy methods. 
%\item 
%We recommend against
%effort  estimation based on neural nets or simple linear regression.
%\ei
%These recommendations are based only on the selected algorithms studied in this paper and
%should be assessed using other algorithms.
%That assessment should be based on the 
%strong datasets identified in this study (cocomo81o, desharnaisL1, cocomo81s, desharnaisL3, albrecht, cocomo81e, nasa93\_center\_5, desharnaisL2 and desharnais).


%This study empirically examined nearly one hundred different combinations of data preprocessors and algorithms executed on 20 software project datasets. 
%For over half of the datasets executed, most cost estimation algorithms performed nearly the same, at least their differences are not statistically significant. 
%The implication is that the traditional evaluation criteria such as MMRE may be less than important. 
%There exists an ordering to the best effort estimator in our experiment, CART performed consistently better than any other algorithms throughout the execution of all the datasets, this is unexpected and not commonly known to the research community in software metrics.  
%
%From all of these important findings, we can conclude that the features and quality of the datasets are far more important that features and quality of the algorithms. Without having investigation the characteristics and quality of the dataset being used in an experiment, the result produced may be flawed with influential biases inherited within the dataset. Our study also shows that a suitable data preprocessor such as stepwise feature selection will improve the overall prediction accuracy.  
%
%We recommend researchers to explore the important research area of data quality rather than the space of possible algorithms which may produce a small improvement that is statistically insignificant. Data quality certification and data preprocessing processes are subject to further investigation, combining these techniques together with robust algorithms will lead to ultimate success in effort estimation. 
% 
%


Lastly, this is an empirical paper that {\em reports}, but does not {\em explain}, the rankings of data sets and
algorithms seen in \fig{dot-plot}. An open question raised by this work is what features of our algorithms
and datasets resulted in their rankings.
While
we have no current theory on what explains the algorithm ordering,
we speculate that the dataset ordering might be explained
by the regions of local {\em high variance} in their internal structure. However, at the time of this writing,
we have no convincing evidence for that speculation. 

Given the significance of this study, an important goal for future work would be to determine the reason for the algorithm / data ranking seen in this study.


\bibliographystyle{abbrv}
\bibliography{icse,timm}

\end{document}

