\documentclass{sig-alternate}
\usepackage{times}
\usepackage{cite}
\usepackage{algorithm}
\usepackage{algorithmic}
\usepackage{multirow}
\usepackage{rotating}


%\usepackage[none]{hyphenat} 
\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}
%
% --- Author Metadata here ---
\conferenceinfo{ICSE}{2011 Waikiki, Honolulu, Hawaii USA}
\CopyrightYear{2011} % Allows default copyright year (20XX) to be over-ridden - IF NEED BE.
%\crdata{X-XXXXX-XX-X/XX/XX}  % Allows default copyright data (0-89791-88-6/97/05) to be over-ridden - IF NEED BE.
% --- End of Author Metadata ---

%\title{An Empirical Study on the Influence of Evaluation Criteria used in Software Cost Estimation  }
\title{Where is the Best Effort Estimator? }

%\numberofauthors{4}
%\author{
% You can go ahead and credit any number of authors here,
% e.g. one 'row of three' or two rows (consisting of one row of three
% and a second row of one, two or three).
%
% The command \alignauthor (no curly braces needed) should
% precede each author name, affiliation/snail-mail address and
% e-mail address. Additionally, tag each line of
% affiliation/address with \affaddr, and tag the
% e-mail address with \email.
%
% 1st. author
%\alignauthor
%Author1
% 2nd. author
%\alignauthor
%Author2
% 3rd. author
%\alignauthor 
%Author3
%\and  % use '\and' if you need 'another row' of author names
% 4th. author
%\alignauthor 
%Author4

%}


\numberofauthors{2} %  in this sample file, there are a *total*
% of EIGHT authors. SIX appear on the 'first-page' (for formatting
% reasons) and the remaining two appear in the \additionalauthors section.
%
\author{
% You can go ahead and credit any number of authors here,
% e.g. one 'row of three' or two rows (consisting of one row of three
% and a second row of one, two or three).
%
% The command \alignauthor (no curly braces needed) should
% precede each author name, affiliation/snail-mail address and
% e-mail address. Additionally, tag each line of
% affiliation/address with \affaddr, and tag the
% e-mail address with \email.
%
% 1st. author
\alignauthor Vincent Rogers\\
    \affaddr{CS, WVU, Morgantown, USA}\\
    \email{email@email.com}
\\
\alignauthor  William Sica\\
            \affaddr{CS, WVU, Morgantown, USA}\\
       \email{filler@filler.fill }
}



\maketitle
\begin{abstract}
\input{abstract}
\end{abstract}

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

\terms{Software effort Estimation, Linear Regression, Regression Trees, Neural Nets, Analogy, MMRE, Evaluation Criteria}

\keywords{Software Effort Estimation, MMRE, Evaluation Criteria}

\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 {\em weak}
at distinguishing between different learners. 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.
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 project data, 
we are able to discover stable conclusions such as
that 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.

\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 the Mean Inverted Balanced Relative Error (MIBRE) studied by Foss et al.~\cite{foss03}:
\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 
first 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 AR, MRE, MER, MdMRE, MMRE, PRED(25), and MIBRE).
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}

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.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{wins_error_methods} and \fig{wins_error_methods25}
test the stability of the algorithms and data sets offered above.
In those plots, we check if the sort orders are changed
by different performance criteria:
\bi
\item
In \fig{wins_error_methods}, we report percentage of {\em wins}, instead of the {\em losses} reported above.
\item
In \fig{wins_error_methods25}, we report percentage of wins seen with {\em 
a single criteria}, PRED(25), instead of the seven criteria used above.
\ei
The sort order on the x-axes of \fig{wins_error_methods} and \fig{wins_error_methods25} was kept the same as the
before. If focusing on wins, or just PRED(25), did {\em not} change the sort orders, then we would
see a smooth plot running left to right. In a result consistent with prior reports on conclusion
instability, the plots are not exactly smooth. However, they do closely follow the same general trends
as \fig{error_methods} and \fig{error_datasets}. 


\begin{figure}[!t]
\includegraphics[width=1.5in]{lib/rows-win-all.pdf}\includegraphics[width=1.9in]{lib/cols-win-all.pdf}
\caption{Algorithms and datasets, sorted as per 
but this
time showing their percentage of 
maximum {\em wins} over all performance measures.}\label{fig:wins_error_methods}
\end{figure}
\begin{figure}[!t]
\includegraphics[width=1.5in]{lib/rows-win-pred25.pdf}\includegraphics[width=1.9in]{lib/cols-win-pred25.pdf} 
\caption{Algorithms and datasets, sorted as per 
\fig{error_methods} and \fig{error_datasets}, 
but this time showing their percentage of 
maximum {\em wins} over {\em just the PRED(25)} performance measures.}\label{fig:wins_error_methods25}
\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 (a)~the number of losses over (b)~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 5 bands. We reserve the lowest band (containing the ``best'' estimators)
for the region where 
all algorithms always lose less than $\frac{1}{8}$th
of the time (i.e. the rows $y=1$ to $y=8$ that are completely yellow in  \fig{dot-plot}).
In the other bands (boundaried at $y=30,50,70,90$), algorithms loss more frequently.

\fig{error_pred_methods} shows the spectrum of PRED(25) values across the 5 bands. 
As might be expect, the y-axis sort order of \fig{dot-plot} predicts for estimation accuracy.
As we move over the five 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.
In \fig{freq_method},  CART is an example of a ``good'' learner.
\item
A ``poor'' preprocessor/learner appears more frequently in the higher bands.
In \fig{freq_method}, all the discretization preprocessors (e.g. {\bf freq3bin}) are ``poor''.
\item
The gray rows of \fig{freq_method} shows 
preprocessor/learner that are neither ``good'' nor ``poor'' (since they are  found in low, medium and high bands);
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).
For the purposes of finding the best effort estimator, the
data sets on the  left-hand-side 
are 
{\em weak} since they hardly  distinguish the performance of different algorithms.

Using engineering judgement,
we use 15\% losses to divide the ``weak'' and ``strong''
(and acknowledge that 
this rule is somewhat subjective).
The  dashed lines  of \fig{error_datasets}, 
\fig{wins_error_methods}, and  \fig{wins_error_methods25},
shows that this 15\% rule selects ten ``strong''
data sets 
(DESHARNAIS, MAXWELL, SDR, 
NASA93$_{center1,2}$,  
MIYAZEKI94,\newline FINNISH, COCOMO81, NASA93, and CHINA) 
and excludes widely-used datasets such as ALBRECHT, KERMERER
and
TELECOM. Note that while a data set may be ``strong'', it may contain
``weak'' subsets. For example, all subsets of DESHARNAIS are ``weak''.

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{wins_error_methods} and \fig{wins_error_methods25}, we see  that our results
are not 100\% stable, they are sufficiently stable to make external valid conclusions. 
We conjecture that prior reports on conclusion instability resulted from using
too few data sets, or too many weak data sets.


{\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 trial 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 three 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}, {\bf log/LReg} ranks very poorly (position
80 out of a maximum of 90 algorithms).

{\em Result5:}
While
{\bf SWR} falls into the {\em worst three 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 PLR} 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. 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 strong data sets in that figure are sorted by the difference between the top-ranked and the twelfth-ranked
algorithm. 
In most of the ten strong data sets, 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}[!b]
\begin{center}
{\scriptsize
\begin{tabular}{r|rr|r}
&norm/CART(yes)&log/ABE0-1NN& difference\\\hline
china&95&43&-52\\
sdr&42&17&-25\\
desharnaisL2&48&32&-16\\
nasa93\_center\_1&58&42&-16\\
maxwell&32&31&-1\\
miyazaki94&40&40&0\\
finnish&61&66&5\\
cocomo81&13&22&9\\
nasa93&29&41&12\\
nasa93\_center\_2&43&59&16\\
\end{tabular}}\end{center}
\caption{Using the strong 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 very little 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; 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 the 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 general 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 (DESHARNAIS, MAXWELL, SDR, 
NASA93$_{center1}$, 
NASA93$_{center2}$, 
MIYAZEKI94, FINNISH, COCOMO81, NASA93, and CHINA).


%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} 
% You must have a proper ".bib" file
%  and remember to run:
% latex bibtex latex latex
% to resolve all references
%
% ACM needs 'a single self-contained file'!
%
\appendix
\input{ekrem/aboutdata}

\end{document}


In order to support this claim,  this paper demonstrates a study of nearly one
hundred different algorithms executed on numerous datasets. For example,
this paper explores The experiment explores the following research questions:

{\bf RQ1:} Is there any stability in the conclusions gained from the currently available
datasets of real project data?

{\bf RQ2:} 
Our reading of the effort estimation
literature is that there is {\em little,little,extensive} focus on the {\em datasets,preprocessors,learners}.
Is this current emphasis correct and sound? 

{\bf RQ3:} Are there datasets to avoid when conducting estimation experiments?

{\bf RQ4:} Can we reasonably to declare a best effort estimator?


