\section{Methodology}
\label{sect:methodology}

%The methodology we adopted in this research is summarized in this section.
%Our methodology section includes an introduction of the datasets used in our research as well as an explanation of our experimental design.
%Since the testing strategy in software effort estimation studies is becoming a point of interest, at the end of this section, we also provide a discussion on this topic.



%When we consider previously proposed methods in effort estimation literature and their variations, the number of different options to consider easily exceeds thousands.
%\fig{cbr} provides different design options associated with only instance-based effort estimation and for this approach alone the number of possible combinations is above $6000$.
%Since it is impractical to explore thousands of options, we elected to explore variants commonly used in the literature.  
%For more details on methods refer to \tion{methods}.
%For example, we explore neural nets, regression, and analogy because those methods were explored by Shepherd and Kododa. 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.


\input{data}
\subsection{Multiple Error Measures}
%In our experiments, numerous performance measures were collected over solo and multi-methods that were applied to the data of \fig{datasets}. 
%This section describes those performance measures.
%We will build our ensembles from top-ranked solo methods.
%Recall from the above that Shepperd et. al caution that ${\delta}r>0$;
%i.e. the rank of an effort estimation method can change, depending on how the performance of
%that method is assessed.
%Hence, in order to check that a method is indeed across a top-ranked
%method across different experimental conditions, we need to find {\em both}
%the ranks of our methods and the changes ${\delta}r$
%in those ranks.
%Accordingly, we must assess our estimation methods using multiple performance measures. 
%
This section describes several performance measures used in this research. All the performance
measures listed here have the property that we can find at least one publication proposing their use for effort estimation.


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

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{Shepperd1997, Foss}. 
MRE measures the error ratio between the actual effort and the predicted effort. It 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{Foss}):
{\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}}

A summary of MRE can be derived as the Mean Magnitude
of Relative Error  (MMRE) or Median Magnitude of Relative Error (MdMRE), which can be calculated as follows respectively: 

{\begin{eqnarray}\small\label{one}
MMRE={\sum_{i=1}^n   MRE_i\over {n} }
\end{eqnarray}}

{\begin{eqnarray}\small\label{one}
MdMRE = median(MRE_1, MRE_2, ... , MRE_n )
\end{eqnarray}}

A common alternative error measure is PRED(25), which can be defined as the percentage of predictions falling within 25\% of the actual values:
{\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 falling within 25\% of the actual values \cite{Shepperd1997}.

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

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

%All afore mentioned error measures provide us different perspectives of comparing various methods.
Interpreting these error measures without any statistical test may be misleading.
A recent discussion about this issue can be found in~\cite{Kitchenham2009}.
To evaluate our results subject to a statistical test, we make use of so called \textit{win-tie-loss} statistics.
Win-tie-loss statistics employ a Wilcoxon non-parametric statistical hypothesis test with 95\% confidence.
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 outliers 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}. 

We stored  the performance of every method w.r.t. 7 error measures over 20 datasets.
This enabled us to collect {\em win-tie-loss} statistics using the algorithm of  \fig {WinTieLossPseudocode}.  
In \fig {WinTieLossPseudocode}, we first check if two
distributions $i, j$ are statistically different according to the
Wilcoxon test (95\%);  if they are not, then 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 error measures. 
\begin{figure}[!h]
\renewcommand{\baselinestretch}{1}
\begin{algorithmic} \footnotesize
\IF{~WILCOXON(\textit{$E_i$}, \textit{$E_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(\textit{$E_{i}$}, \textit{$E_{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}).}
\label{fig:WinTieLossPseudocode}
\end{figure}

The $better$ function in  the $if$ statement of \fig{WinTieLossPseudocode} 
varies according to the performance criteria. For most error measures like MRE, “better” means lower medians. However, for 
PRED(25), “better” means higher medians. 

\subsection{Experimental Conditions}
Recall the results of Shepperd et al.~\cite{shepperd01} and Menzies et al.~\cite{Menzies2010}:
different experimental conditions can change the rank of an effort estimator.
Hence, it is important to study not just the rank of an estimator, but also how well that
method performs across multiple experimental conditions such as:
\be
\item
{\em Error measures} that measure a method's performance;
\item
{\em Comparison summaries} used to report the performance of many methods over many data sets; 
\item
{\em Data sets} used in the experiments.
\ee
The {\em error measures} used in this study, as defined above, are MAR, MMRE, MdMRE, MMER, PRED(25), MBRE, MIBRE. 

As to {\em comparison summaries}, the following procedure was repeated for each error measure.
Each of our 90 methods were compared to 89 others using the procedure of \fig{WinTieLossPseudocode}.
In our procedure,
we sum the $wins$, $losses$, $ties$ of \fig{WinTieLossPseudocode} and we rank our methods by that sum.
That is, for an estimation method to be highly ranked, it must perform well across {\em all} error measures.

The results of those comparisons are contained in the $win$, $tie$, $loss$ counters of \fig{WinTieLossPseudocode}.
These comparisons can be summarized through many ways:
\be
\item Number of losses;
\item Number of wins;
\item Number of wins-losses
\ee
Demsar~\cite{Demsar2006} reports that there is no generally
accepted method of  {\em comparison summarization}. 
Hence,
we compute ${\delta}r$ from the changes
in the ranks seen when we move across all three
summarization methods:
\bi
\item
Firstly, we generate rankings of estimators
using  {\em number of losses} (repeated for all error measures)
via 
a leave-one-out procedure  (where each example becomes a test and
the remaining data is used for training).
\item
Next, we compare that rank to other ranks generated by other comparisons summaries (again,
repeated for all error measures).
\item
The maximum rank change for a method over all the dimensions is the ${\delta}r$ value for that method.
\ei
Finally, we run our rig over multiple data sets.
Our experiments use the $20$ publicly available effort estimation
datasets currently available in the PROMISE repository (see http://promisedata.org/?cat=14).
The names and properties of these datasets are provided in \fig{datasets}.
See  Appendix \ref{sect:data-used-in-this-study} for more explanatory notes.

Combining the above, we can see that the experiments of this paper are an extensive analysis of different conditions
for effort estimation experiments.
Given 89 comparisons, 7 error measures, and 20 datasets, then each method appears in
$89\times7\times20=12,460$ comparisons. 

%%\input{ekrem/bottom-16-methods}

\subsection{Focus on Superior Methods}

The x-axis of \fig{rank_changes} shows the the ranking of the 90 solo-methods, according to number of losses over all 20 data sets.
Better methods appear on the left-hand-side of that figure (so the top-ranked method appears at position $x=1$).

The y-axis of that figure shows the maximum \textit{changes}, ${\delta}r$, seen for each method as we compare the ranks across number of losses, number of wins, and number of wins-losses.
In a result consistent with Shepperd et al., all methods have ${\delta}r>0$. However, the good news is that the top-ranked methods have a very low ${\delta}r$. That is,
even if these top-ranked methods jumped rank by their maximum ${\delta}r$, then they would still be performing better than most of the other 90 methods.



In signal processing, it is standard practice to segment data based on the region 
of maximal change~\cite{oppenheim96}.
An inspection of \fig{rank_changes} shows that the region
of maximal ${\delta}r$ occurs after $X=13$.
%We call the methods at $64\le X \le 90$ $inferior$
%since they are clearly :ranked last. 
This is an interesting division since
the region $1 \le X \le 13$ contains
methods with high rank and low ${\delta}r$. 
We call these methods {\em superior} and the rest \textit{inferior}.
The list of top $13$ methods are shown  in \fig{top-13-methods}.

\begin{figure}[!t]
\begin{center} \includegraphics[width=0.5\textwidth]{plots/rank-changes.pdf} \end{center}
\caption{Algorithms and the associated changes, i.e. ${\delta}r$ values. 
Note the sudden increase in ${\delta}r$ values, after $X=13$.
We call methods in the region $1 \le X \le 13$ as {\em superior}.
}
\label{fig:rank_changes}
\end{figure}
\input{ekrem/top-13-methods}


%In between the {\em superior} and {\em inferior} methods are a set of methods with large ${\delta}r$. These will be ignored in
%our analysis since they are not clearly superior nor inferior.

\fig{rank_changes} is discussed further in a related paper that
discusses the relative rankings of the solo-methods~\cite{keung2011a}.
For reasons of space, a detailed discussion of that paper is not included here. 
However, we will
make the comment that none of the superior solo-methods
try to fit one model to all the data:
\bi
\item The CART regression tree learner appears at ranks 1 through 10
of \fig{top-13-methods}. Each branch of a regression tree
defines one context in which an estimate may be different.
\item Analogy-based estimation (ABE) appears at ranks 11,12,13.  
ABE builds a different model for each test instance (using the test instance's
k-th
nearest neighbors).
\ei
Solo-methods are not the focus of this paper. Hence, we move on to
discuss multi-methods.

\subsection{Build Ensembles}

To form multi-methods, we build ensembles using the top $M$ solo-methods in the sort order of \fig{top-13-methods}.
In this study, we use $M\in\{2, 4, 8, 13\}$. 

To generate an estimate, we ask all members of an ensemble to offer a prediction. These are combined in one of three ways:
mean, median and IRWM.

With this scheme, we have \textit{4 solo-methods (method 2, 4, 8 and 13) times 3 (mean, median, IRWM) = 12 multi-methods}. 
These multi-methods are then ranked along-side the solo-methods in the same manner as \fig{rank_changes}.
This gives us the comparison of \textit{90 solo-methods + 12 multi-methods = 102 methods}.
Every method is compared to 101 others with respect to seven error measures and over 20 datasets. 
Therefore, the maximum number of comparisons for any method now becomes $101\times7\times20=14,140$.
To the best of our knowledge this is the most extensive effort estimation experiment yet reported
in the literature
(and for extensive non-experimental studies, see~\cite{Jorgensen2007,Mendes2007}).




%%In 3-way cross-validation, the data set of  $N$ projects is divided into three
%%bins, projects in $bin_i$ ($i\in \left\lbrace 1,2,3 \right\rbrace $) are used for testing while the projects in the remaining bins are used for testing.
%%Since some of our data sets are quite small (e.g. Cocomo81o has $24$ instances), we used a  3-way cross validation (and not the 10-way used by, say, Quinlan~\cite{quinlan92}).
%%Some thought was given to using 3-way for small data sets and 10-way for larger
%%data sets. However, this would  introduce a complication into the analysis
%%that is neither recommended by the literature, nor handled by any statistical
%%technique that we are aware of. 
%
%We use both leave-one-out and N-way cross-validation since the effort estimation
%literature is ambiguous on which is most appropriate.
%In the Kitchenham et al.
%%survey~\cite{Mendes2007}, all the projects reviewed in their Table~3 used N-way
%cross-validation. However, other prominent studies prefer leave-one-out~\cite{Li2007}. 
