This chapter provides background information about this research. It is important to understand the previous work and existing problems in this area before
presenting the experiments and results since this study attempted to solve such problems.
The effort estimation concept and different approaches to effort estimation are discussed in Section \ref{b:effortEstimation}.
Section \ref{b:models} focuses on the COCOMO model used in this study and briefly discusses other models.
The concepts of pruning columns and row are provided in Sections \ref{b:columnPruning} and \ref{b:rowPruning} respectively.
In this study, these pruners are considered pre-processors to learners, discussed in Section \ref{b:learners}.
Different evaluation methods are discussed in Section \ref{b:evaluation} and the instability of such evaluations in effort estimation
is discussed in Section \ref{b:instability}. Finally, a summary of the current common problems in the effort estimation literature is presented in
Section \ref{b:currentProblems}.

\section{Effort Estimation}
\label{b:effortEstimation}

Effort estimation for software projects serves a major role in the success or failure of such projects, especially in the case of large projects.
As mentioned in Section \ref{introduction}, inaccurate estimates are reported widely in the literature and have caused the cancellation of overrunning projects.
Boehm and Papaccio's study about software costs concludes that ``understanding and controlling software costs is extremely important \cite{boehm88}.''
This section provides an overview of models and methods that could help in estimating such costs as accurately as possible, 
which could simplify the process of controlling software costs as \cite{boehm88} mentions.

Effort estimation methods can be classified in different ways. Section \ref{b:classification} takes a look at one such classification, which focuses 
on the type of effort estimation methods, broadly categorized based on the amount of historical data they need. 
The remaining sections discuss this classification in detail.

\subsection{Classification of Software Effort Estimation Methods}
\label{b:classification}

Myrtveit et al. published a study where they classified the current effort estimation methods in two groups of {\em sparse-data} and {\em many-data}
methods \cite{myrtveit05}. This is a classification based on the availability of historical data.
According to \cite{myrtveit05}, ``sparse-data methods are estimation methods requiring few or no historical data'' while many-data methods need
more historical data for effort estimation. Each group contains different types of methods.

\begin{figure}
\begin{center}
\includegraphics[scale=0.4]{figures/sparse-many}
\end{center}
\caption[Classification of Effort Estimation Methods.]{Classification of Effort Estimation Methods \cite{myrtveit05}.}
\label{figure:sparse-many}
\end{figure}

Sparse-data methods include:

\begin{itemize}
\item Analytic Hierarchy Process (AHP),
\item Expert Judgment, and
\item Automated Case-Based Reasoning (CBR).
\end{itemize}

Many-data methods are subdivided into functions and arbitrary function approximators (AFA). According to \cite{myrtveit05},
``arbitrary function approximators do not make any assumptions regarding the relationship between the predictor and response variables'' while
functions assume otherwise. AFA's include: 

\begin{itemize}
\item Estimation by Analogy (EBA),
\item Artificial Neural Networks (ANN), and
\item Classification and Regression Trees (CART).
\end{itemize}

Myrtveit et al. explore some of these methods.
Overall, there are 7 groups of effort estimation methods based on this classification. However, EBA may be considered a kind of CBR. 
As they mention, ``there is a spectrum between sparse and many-data methods'' and CBR may belong to both depending on how it is used.
``If CBR is used to identify the closest case, it is a many-data method. EBA is an example of this use of CBR. \cite{myrtveit05}.''
Therefore, they view EBA as a type of CBR and the same approach is used in Section \ref{b:rowPruning} to study both methods for row pruning.

\subsection{Analytic Hierarchy Process} 

Analytic Hierarchy Process (AHP) \cite{saaty80}, in general, is a technique for dealing with complex decisions by determining the right
decision suited for each case, or criteria, rather than using a generic decision. Each problem in analyzed through the hierarchy of smaller problems
that are easier to solve. In essence, this is a structured problem-solving technique that deals with sub-problems concurrently and makes
a decision based on the relative ranking of the solutions for each sub-problem.

AHP can be applied to effort estimation in various ways. As Shepperd and Cartwright suggest, ``an example would be to utilize the hierarchical
structure of AHP to predict effort by decomposing the problem into a number of criteria which all contribute to actual effort \cite{shepperd-cartwright01}.''
They use AHP (as well as a pairwise comparison technique) in the study of their sparse-data method and report promising results.
AHP, as a multicriteria decision-making technique, may be applied to effort estimation, which uses a single criterion, namely effort.
Moreover, other contributing factors to effort such as function points and other information about the project can extend this 
hierarchy \cite{shepperd-cartwright01}.

\subsection{Expert Judgment}

According to Jorgensen, an estimation strategy is categorized as expert estimation, or expert judgment, when ``the estimation
work is conducted by a person recognized as an expert on the task, and that a significant part of the estimation process is based on a non-explicit and
non-recoverable reasoning process \cite{jorg04}.'' Clearly, the extent to which the expert follows guidelines in this process can affect the successful
reproduction of the results of this process. Nonetheless, the expert may or may not follow any instructions or use the historical data.

There are twelve ``best practice'' expert estimation principles suggested by Jorgensen \cite{jorg04} based on empirical evidence:

\begin{quote}
\begin{enumerate}
\item Evaluate estimation accuracy, but avoid high evaluation pressure.
\item Avoid conflicting estimation goals.
\item Ask estimators to justify and criticize their estimates.
\item Avoid irrelevant and unreliable estimation information.
\item Use documented data from previous development tasks.
\item Find estimation experts with relevant domain background and good estimation records.
\item Estimate top-down and bottom-up, independently of each other.
\item Use estimation checklists.
\item Combine estimates from different experts and estimation strategies.
\item Assess the uncertainty of the estimate.
\item Provide feedback on estimation accuracy and task relations.
\item Provide estimation training opportunities.
\end{enumerate}
\end{quote}

According to Jorgensen \cite{jorg04}, principles 1 through 5 ``reduce situational and human biases,'' principles 7 through 10 ``support the
estimation process,'' and principles 11 and 12 ``provide feedback and training opportunities.'' Jorgensen also cautions that there is ``still a need
for more knowledge about how to apply them in various software estimation situations. \cite{jorg04}.'' Baker \cite{baker07} studied these principles
and implemented seven of the twelve best practices in the 2CEE tool designed for NASA's Jet Propulsion Laboratory.

Expert judgment approaches are widely used for effort estimation in the industry \cite{jorg04,jorgensen07}. Jorgensen \cite{jorg04}
reports five studies were 62\%, 72\%, 83\%, 84\%, and 86\% of the effort estimation in a wide range prominent organizations and companies
were performed using expert judgment.

In their review of effort estimation studies, Jorgensen and Shepperd claim that ``more formal estimation techniques'' or model-based methods 
``has been somewhat erratic to date, has not documented higher accuracy than expert judgment, and that expert-based 
estimation approaches are, by far, the most common used approaches by the software industry \cite{jorgensen07}.''
Although, according to \cite{jorgensen07}, model-based methods have not documented higher accuracies than expert-based methods, Jorgensen
mentions that ``it is not possible to conclude that expert estimation or estimation model, are more accurate'' and offers an observation
where expert-based methods seem to be more accurate ``when there are important domain knowledge {\em not} included in the estimation models, 
when the estimation uncertainty is high as a result of environmental changes not included in the model, or when simple estimation strategies 
lead to relatively accurate estimates \cite{jorg04}.'' Therefore, there is no clear winner in the comparison of the two approaches in effort estimation.
Jorgensen offers empirical results where he compared 15 studies that compare expert-based estimation with model-based estimation. 
Among these studies, five were in favor of expert-based estimation, five were in favor of model-based estimation, and five did not find any
difference \cite{jorg04}.

Therefore, although the expert-based estimation is widely used in the industry, the lack of a clear winner between the two approaches has led
researchers to study the model-based effort estimation extensively .
Another reason for the tendency of researchers toward model-based methods may be the lack of expert judgments in the research community and ease of reproducing
model-based methods' results comparing to that of the expert-based methods.

In general, model-based methods, such as the ones in Figure \ref{figure:sparse-many} (functions, different arbitrary function approximators (AFA) 
including EBA, ANN, and CART, and even CBR in certain cases) use some algorithm to summarize the historical data and offer estimates for new projects.
These methods are discussed in their corresponding sections.
Menzies et al. \cite{me06d} extended the twelve best practices for expert-based estimation to include eight best practices for model-based estimation:

\begin{quote}
According to Boehm \cite{boehm81,boehm00b}; Chulani \cite{chulani98,chulani99}; Kemerer \cite{kemerer87}; Stutzke \cite{stutzke05}; 
Shepperd \cite{shepperd97}; our own work \cite{me04h,chen05a,me05c}; and a recent tutorial at the 2006 International 
Conference of the International Society of Parametric Analysts \cite{cpp06a}, best practices for model-based estimation include at least the following:
\begin{enumerate}
\setcounter{enumi}{12}
\item {\em Reuse regression parameters} learned from prior projects on new projects;
\item {\em Log-transforms} on costing data before performing {\em linear regression} to learn log-linear effort models;
\item {\em Model-tree} learning to generate models for non-linear relationships;
\item {\em Stratification}, i.e. given a database of past projects, and a current project to be estimated, 
just learn models from those records from similar projects;
\item {\em Local calibration}, i.e. tune a general model to the local data via a small number of special tuning parameters;
\item {\em Hold-out} experiments for testing the learned effort model \cite{me04h};
\item Assessing effort model uncertainty via the {\em performance deviations} seen during the hold-out experiments of item \#17;
\item {\em Variable subset selection} methods for minimizing the size of the learned effort model \cite{chen05a,me05c,miller02,kirsopp02}.
\end{enumerate}
\end{quote}

(These practices were applied or further explored in this study with the exception of performance deviations being rejected and replaced 
with a non-parametric test. The results are explained in Section \ref{s:results}.)

They also included best practices for the combination of expert-based and model-based estimation \cite{me06d}:

\begin{quote}
This separation of model-based and expert-based methods is not a strict division since some practices fall into both
categories: e.g. \#4 \& \#20 are similar as are \#10 \& \#19. Also, one way to view model-based methods is that they
seek algorithms to make maximal use of \#5. Further, some research actively tries to combine the two approaches:
\begin{enumerate}
\setcounter{enumi}{20}
\item Shepperd's {\em case-based reasoning} tools \cite{shepperd97} explore algorithmic methods for emulating expert analogical reasoning;
\item Chulani \& Boehm's {\em Bayesian tuning method} \cite{chulani99} for regression models allows an algorithm to carefully combine expert
judgment with the available data;
\item This paper will argue for the use of heuristic {\em rejection rules} to represent expert intuitions on how to rank different effort models.
\end{enumerate}
\end{quote}

(Case-based reasoning was applied and further explored in this study and rejection rules were replaced with a non-parametric test. The Bayesian tuning
method can be explored as a future work. The results of the case-based reasoning method are explained in Section \ref{s:results}.)

Baker's attempt \cite{baker07} to integrate as many as seven of Jorgensen's twelve best practices \cite{jorg04} into a tool, which also involves
model-based methods emphasizes the suggestions of other researchers \cite{shepperd07} to combine expert-based and model-based effort estimation 
methods and create a unified approach for effort estimation, which could potentially increase the accuracy of the estimates.
The Bayesian estimation approach suggested by Chulani et al. \cite{chulani99} is another method to merge ``expert prior information with software
engineering data,'' which is especially useful when the data is scarce and incomplete.

\subsection{Automated Case-Based Reasoning}
\label{b:cbr}

Case-based reasoning (CBR) is an approach for finding similarities between past projects and a future project
and using them in predicting certain features, such as effort, for future projects.
In this method, when seeking a solution to a current problem, the problem is matched against other solved problems and their solutions
(altogether called cases) in the case base.
Solutions to similar problems are then used to find a solution to the current problem, which is tested for success. This new solution
may be revised if necessary. The new problem and its solution will be stored as a new case in the case base.
In short, 
\begin{quote}
case-based reasoning has four distinct aspects:
\begin{itemize}
\item characterization of cases,
\item storage of past cases,
\item retrieval of similar cases to use as analogies, and
\item utilizing the retrieved case to solve the target case problem, sometimes known as case adaptation \cite{shepperd01}.
\end{itemize}
\end{quote}

In a general sense, CBR and the methods based on it may seem similar to rule induction algorithms such as C4.5 \cite{quinlan92}
in that both approaches look for similarities in the data.
However, there is a difference in how they use their training data.
CBR uses the test instance (current problem) to generalize as it is processing its train instances while a rule induction
algorithm finishes training a model before it can use it on a test instance.
In other words, according to Shepperd and Kadoda, 
\begin{quote}
CBR is considered to be fundamentally different from rule induction and
regression approaches in that it utilizes specific knowledge of previously solved cases to solve future ones, while the former
use generalized knowledge or relationships, respectively. In other words, CBR is model free \cite{shepperd01}.
\end{quote}

\subsection{Functions}

Functions are the first group of many-data methods analyzed by Myrtveit et al. \cite{myrtveit05} and are considered of the general form
$y = Ax^B$. In general, functions relate the features (also called the variables) of a model mathematically. The linear regression method
(discussed in Section \ref{s:coseekmoLearnerLSR}) is a function, and the only one discussed in \cite{myrtveit05}.
Boehm, who developed the COCOMO model \cite{boehm81} (discussed in Section \ref{b:cocomo}),
also developed the local calibration method, which is a specialized form of 
linear regression \cite[p526-529]{boehm81}. Local calibration is widely used as an effort estimation method, at least in the COCOMO community.
Local calibration is further discussed in Section \ref{s:coseekmoLearnerLocalCalibration}.

There are also other forms of regression, such as the multiple regression approach.

\begin{quote}
A multiple regression model can be written as

\begin{displaymath}
y_t = \beta_0 + \beta_1 x_{t1} + \cdots + \beta_k x_{tk} + \epsilon_t
\end{displaymath}

where $x_{t1} \cdots x_{tk}$ are the values of the predictor (or regressor) variables for the $x_{th}$ observation,
$\beta_0 \cdots \beta_k$ are the coefficient to be estimated, $\epsilon_t$ is the usual error term, and $y_t$ is the response variable for
the $y_{th}$ observation \cite{chulani99}.
\end{quote}

Chulani et al. report the popular classical multiple regression approach as the most commonly used technique for empirical calibration \cite{chulani99}.
Their study explores the problems faced by the multiple regression approach during the calibration of COCOMO II \cite{boehm00b}, an updated version of COCOMO.
Their study suggests the Bayesian approach over the multiple regression approach.
Nonetheless, regression is widely used in many studies in the effort estimation literature. According to Jorgensen and Shepperd \cite{jorgensen07},
``regression-based estimation approaches dominate'' the space of estimation approaches with a total of 49\% of the studies published between 1989 and 2004.
It should be noted that they also included the methods based on COCOMO in this list.

\subsection{Estimation by Analogy}
\label{b:eba}

Estimation by analogy can be considered a type of case-based reasoning \cite{myrtveit05} and has become the focus of more studies recently \cite{jorgensen07}.
Among other methods, Boehm suggested estimation by analogy as a method for effort estimation \cite{boehm81}.
According to Boehm, ``the main strength of estimation by analogy is that the estimate is based on actual experience on a project \cite{boehm81}.''
Since it is not clear to what degree the previous project represents the current project, and Boehm considered
this its main weakness, estimation by analogy should be used with caution. However, Boehm did not explore the possibility
of automating this process at that time.

Later, Cowderoy and Jenkins \cite{cowderoy88} mentioned estimation by analogy as a ``widely exercised practice within the
software industry'' and as a partly automated process. Nonetheless, this process was not fully automated until later.
Among other tools, ANGEL software tool described by Shepperd et al. is an automated tool that uses estimation by analogy \cite{shepperd96}.
In their effort estimation study, Shepperd and Schofield suggested using estimation by analogy 
as a viable technique in addition to other effort estimation methods \cite{shepperd97}.
Effort estimation using estimation by analogy and case-based reasoning in general are extensively studied by other
researchers as well \cite{mair06,auer,jorgensen03,kadoda00,mukhopadhyay92,kadoda,myrtveit04,premraj04,premraj03,li07}.
Some, however, are skeptical about the application of case-based reasoning in effort estimation in every domain.
Delany et al. studied the problems associated with extending the use of CBR for cost estimation
to operate across broader domains \cite{delany98}.

\subsection{Artificial Neural Networks}

As their name suggests, artificial neural networks (ANN) are mathematical methods designed based on the neural activities of neurons of
living organisms in the nervous system, and more specifically the brain. Similar to the brain, where an input (stimuli) can be related to 
an output (action), an ANN can model the relations between inputs and outputs.

An application of ANN is in data mining and finding patterns. Effort estimation is also possible using ANN models, although Myrtveit et al. mentioned
contradicting studies about the relative performance of ANN models comparing to regression models discussed before \cite{myrtveit05}.
Another study (also discussed in Section \ref{b:instability}) is the Shepperd and Kadoda's study where they found ANN usually performing worse than
stepwise regression (a variant of regression), rule induction, and case-based reasoning \cite{shepperd01}.
Nonetheless, researchers have used and recently focused more on ANN as an effort estimation method \cite{jorgensen07}.

\subsection{Classification and Regression Trees}

Classification trees were studied both in statistics and in artificial intelligence.
The statistics studies by Breiman et al. led to the classification and regression trees (CART) \cite{breiman84}
and among other studies in artificial intelligence, classification trees led Quinlan to ID3, which was later extended into C4.5 \cite{quinlan92}.
In essence, CART creates a classification tree of a group of variables and their split points that most reduce the impurity of the root node,
where impurity is measured using a specific function \cite{yohannes99}.

The application of CART in effort estimation may seem strange due to the presence of a classification tree. However, as Briand et al. explain,
this is possible:

\begin{quote}
CART examines the data and determines data splitting criteria that will most successfully partition the dependent variable. To build a regression
tree the data set is recursively split until a stopping criterion is satisfied. All but the terminal nodes in a tree specify a condition based on one of the
variables that have an influence on project effort or any other dependent variable.

After a tree is generated it may be used for effort prediction of a project. To predict the effort for a project, a path is followed through the tree
according to the project's specific variable values until a terminal node is reached. The mean or median value of the terminal node may then be used
as the predicted value \cite{briand00}.
\end{quote}

According to Jorgensen and Shepperd \cite{jorgensen07}, CART is used in effort estimation studies, which is 5\% of studies over a span of 15 years.
Myrtveit et al. \cite{myrtveit05} report contradicting studies about the merits of CART comparing to regression models. One of such
studies is by Briand et al. \cite{briand00}, where they report contradicting results comparing to their previous studies on the benefits of CART when
used alone or in combination with other methods. They conclude that ``depending on the structures present in the data, we have to expect 
variations in performance across data sets \cite{briand00}.'' Kitchenham applied CART to the COCOMO data set and reported other simpler methods 
outperforming it \cite{kitchenham98}. Kitchenham suggest using an algorithm like CART when there is a large number of data points in the data set.

\section{Software Effort Estimation Models}
\label{b:models}

There are many software effort estimation models available. This study focuses on COCOMO, discussed in Section \ref{b:cocomo}. 
Other effort estimation models are also discussed briefly in Section \ref{b:otherModels}.

\subsection{COCOMO}
\label{b:cocomo}

The COnstructive COst MOdel (COCOMO) was developed in 1981 by Barry Boehm and was published along with a data set containing 63 projects \cite{boehm81}.
At that time, Boehm published the COCOMO model in three versions (all are considered COCOMO 81 hereafter).
{\em Basic COCOMO} is a relatively simple model ``good for quick, early, rough order of magnitude estimates of software costs'' with a limited 
accuracy \cite{boehm81}. Basic COCOMO applies to three modes of software projects,
{\em organic}, {\em semidetached}, and {\em embedded}. In the organic mode ``relatively small software teams develop software in a highly 
familiar, in-house environment,'' whereas in the embedded mode, ``project should operate within tight constraints (strongly coupled complex 
of hardware, software, regulations, and operational procedures) \cite{boehm81}.'' The semidetached mode is ``an intermediate stage between the 
organic and embedded modes \cite{boehm81}.'' Basic COCOMO only uses the lines of code (or delivered source instructions, DSI) in its estimates.
Due to the limited accuracy of Basic COCOMO, being ``within a factor of 1.3 of the actuals only 29\% of the time, and within
a factor of 2 of the actuals only 60\% of the time \cite{boehm81},'' as well as other limitations, this study does not focus on Basic COCOMO. Instead,
{\em Intermediate COCOMO} is used in this research.

The core intuition behind COCOMO is that, as a program grows in size, the development effort grows exponentially. This is the case with either models. 
Similar to Basic COCOMO, Intermediate COCOMO also supports the three software modes. The constants for these modes, which are different from Basic COCOMO,
are provided in Table \ref{table:standardModes}. The equation for estimating effort in these modes \cite{boehm81} is
\begin{equation}
{effort=a*\left(KLOC^b\right)}
\label{equation:standardLC}
\end{equation}
where $a$ and $b$ are the constants in Table \ref{table:standardModes} and $KLOC$ is the thousand lines of code (or delivered source instructions).
Effort is measured in man-month, which consists of 152 hours of working time and includes those activities related to the development or managing a project.

\begin{table}
\begin{center}
\begin{tabular}{|l|c|c|}
\hline
Development Mode & $a$ & $b$  \\
\hline
Organic          & 3.2 & 1.05 \\
Semidetached     & 3.0 & 1.12 \\
Embedded         & 2.8 & 1.20 \\
\hline
\end{tabular}
\end{center}
\caption{Intermediate COCOMO 81 development modes.}
\label{table:standardModes}
\end{table}

According to Boehm, ``Intermediate COCOMO incorporates an additional 15 predictor variables which account for much of the software project 
cost variation left unexplained by Basic COCOMO \cite{boehm81}.'' This extension to Basic COCOMO provides a better accuracy, where 
``the estimates are within 20\% of the project actuals 68\% of the time \cite{boehm81}.'' The 15 factors, also called {\em cost drivers}, are provided
in Table \ref{table:costDrivers}.

\begin{table}
\begin{center}
\begin{tabular}{|c|c|l|}
\hline
          & Cost Driver & Description \\
\hline
          & ACAP        & Analyst capability\\
Upper     & PCAP        & Programmer capability\\
(increase & AEXP        & Applications experience\\
these to  & MODP        & Use of modern programming practices\\
decrease  & TOOL        & Use of software tools\\
effort)   & VEXP        & Virtual machine experience\\
          & LEXP        & Programming language experience\\
\hline
Middle    & SCED        & Required development schedule\\
\hline
          & DATA        & Data base size\\
Lower     & TURN        & Computer turnaround time\\
(increase & VIRT        & Virtual machine volatility\\
these to  & STOR        & Main storage constraint\\
increase  & TIME        & Execution time constraint\\
effort)   & RELY        & Required software reliability\\
          & CPLX        & Product complexity\\
\hline

\end{tabular}
\end{center}
\caption{COCOMO 81 cost drivers.}
\label{table:costDrivers}
\end{table}

As a result, equation \ref{equation:standardLC} is extended \cite{boehm81} to include these cost drivers.

\begin{displaymath}
{effort=a*\left(KLOC^b\right)*\left(\prod_jEM_j\right)}
\label{equation:lc}
\end{displaymath}

Here, $KLOC$ is the thousand lines of code, $EM_j$ is one of the cost drivers from Table \ref{table:costDrivers} with precise values from 
Table \ref{table:preciseEffortMultipliers}, and $a$ and $b$ are the parameters tuned by Boehm's local calibration procedure (further discussed
in Section \ref{s:coseekmoLearnerLocalCalibration}).
Cost drivers may increase or decrease the effort. This can be seen with labels upper or lower in Tables \ref{table:costDrivers}
and \ref{table:preciseEffortMultipliers}.

\begin{table}
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|c|}
\hline
          & Cost Driver & Very Low & Low  & Nominal & High & Very High & Extra High \\
\hline
          & ACAP        & 1.46     & 1.19 & 1.00    & 0.86 & 0.71      &            \\
Upper     & PCAP        & 1.42     & 1.17 & 1.00    & 0.86 & 0.70      &            \\
(increase & AEXP        & 1.29     & 1.13 & 1.00    & 0.91 & 0.82      &            \\
these to  & MODP        & 1.2      & 1.10 & 1.00    & 0.91 & 0.82      &            \\
decrease  & TOOL        & 1.24     & 1.10 & 1.00    & 0.91 & 0.83      &            \\
effort)   & VEXP        & 1.21     & 1.10 & 1.00    & 0.90 &           &            \\
          & LEXP        & 1.14     & 1.07 & 1.00    & 0.95 &           &            \\
\hline
Middle    & SCED        & 1.23     & 1.08 & 1.00    & 1.04 & 1.10      &            \\
\hline
          & DATA        &          & 0.94 & 1.00    & 1.08 & 1.16      &            \\
Lower     & TURN        &          & 0.87 & 1.00    & 1.07 & 1.15      &            \\
(increase & VIRT        &          & 0.87 & 1.00    & 1.15 & 1.30      &            \\
these to  & STOR        &          &      & 1.00    & 1.06 & 1.21      & 1.56       \\
increase  & TIME        &          &      & 1.00    & 1.11 & 1.30      & 1.66       \\
effort)   & RELY        & 0.75     & 0.88 & 1.00    & 1.15 & 1.40      &            \\
          & CPLX        & 0.70     & 0.85 & 1.00    & 1.15 & 1.30      & 1.65       \\
\hline
\end{tabular}
\end{center}
\caption{The precise COCOMO 81 effort multiplier values.}
\label{table:preciseEffortMultipliers}
\end{table}

The third and last version of COCOMO 81 is the {\em Detailed COCOMO}, which provides ``a set of phase-sensitive effort multipliers for each cost driver
attribute'' and takes into account an assessment of the impact of each cost driver in different levels of development \cite{boehm81}.
Detailed COCOMO is rather complex and was not used in this study.

COCOMO 81 has two public data sets ($COC81$ and $NASA93$, discussed in Section \ref{s:data}) and several researchers have published
baseline results based on COCOMO \cite{chulani99,me06d}. According to Jorgensen and Shepperd, where they reviewed effort estimation studies from
1989 to 2004, ``roughly half of all estimation papers try to build, improve or compare with regression model-based estimation methods'' with COCOMO
being one of the most common parametric estimation model in this dominant category of research \cite{jorgensen07}.

Boehm later updated the COCOMO 81 model to COCOMO II in 2000 \cite{boehm00b}. COCOMO II adds five {\em scale factors} that
exponentially influence effort. However, COCOMO II is not used in this study since there is no publicly available data set for it. Hence, COCOMO II
is not further discussed.

\subsection{Other Models}
\label{b:otherModels}

There are several other software models. This study follows previous studies in the literature that uses COCOMO and hence, it does
not explore these models. Furthermore, there is either no publicly available data or few baseline results for some of these models, making
it hard to compare the results of this study with others. However, as Section \ref{c:future} mentions, these models can be studied in future works upon
the availability of data. Boehm suggests this as a good practice as well \cite{boehm00a}.

Some of these models and approaches with references are listed below:

\begin{itemize}
\item CHECKPOINT: is a commercial model \cite{ferens98}.
\item ESTIMACS: is a commercial model \cite{kemerer87}.
\item PRICE-S \cite{park88} is privately owned \cite{ferens98}.
\item REVIC: Revised Enhanced Intermediate Version of COCOMO, is privately owned by the government \cite{ferens98}.
\item SAGE: is a commercial model \cite{ferens98}.
\item SASET: Software Architecture Sizing and Estimating Tool, is privately owned by the government \cite{ferens98}.
\item SEER-SEM: System Evaluation and Estimation of Resources --- Software Estimating Model \cite{jensen83} is privately owned \cite{ferens98}.
\item SLIM: Software Lifecycle Management \cite{putnam92} is privately owned \cite{ferens98}.
\item SoftCost: is a commercial model \cite{ferens98}.
\end{itemize}

\section{Column Pruning}
\label{b:columnPruning}

Column pruning, also known as feature subset selection \cite{hall03} and variable subset selection \cite{miller02}, is a
pre-processing method to select a subset of columns of a data set, while removing the others, which could reduce the noise in the data.
Reducing the noise can improve the accuracy of the trained model, hence improving the performance of an effort estimation method.
Chen et al. \cite{me05c} as well as other researchers \cite{kirsopp02,baker07,jalali07a} have reported this as well.

The reduction of noise can be more clearly explained in mathematical notations.
In a linear model with constants $\beta_i$ that inputs features $f_i$ from a set of features $F$ to predict for $y$,
\begin{displaymath}
y = \beta_0 + \beta_1 \cdot f_1 + \beta_2 \cdot f_2 + \beta_3 \cdot f_3 + \cdots
\end{displaymath}
the variance of $y$ is some function of the variances in $f_i$.
If the set $F$ contains noise, then random variations in $f_i$ can increase the uncertainty of $y$.
Column pruning methods decrease the number of features $f_i$, thus increasing the stability of $y$'s predictions. 
That is, the fewer the features, the more restrained are the model predictions.
Taken to an extreme, column pruning can reduce $y$'s variance to zero by pruning the above equation back to $y=\beta_0$,
but increases model error since the equation $y=\beta_0$ will ignore all project data when generating estimates.
Hence, intelligent column pruners experiment with some proposed subsets $F' \subseteq F$ before changing that set.

The removed columns are not necessarily useless. They are, however, not suitable for the model being generated from the data.
Therefore, the same column may not be removed if another column pruner was used.
The inclusion of such columns happens during the data collection process when several features are included in the data for the possibility
of being used in the future. Column pruners may also remove redundant columns if they exist, which can improve the efficiency of the learning algorithm
and produce smaller theories and models \cite{chen05a}.

Column pruning is generally used in machine learning, and is often referred to as attribute selection. 
According to Hall and Holmes \cite{hall03}, there are several attribute selection methods, which are often categorized 
as either {\em filter}s or {\em wrapper}s. The main difference between the two is in their evaluation method.
A wrapper uses a target learner to evaluate an attribute while a filter uses general characteristics of the data and does not use the target learner in
evaluating the attributes \cite{hall03}. There are other classifications of attribute selection methods as well. Ranking attributes individually
or in subsets and ranking them based on their class type (being numeric or discrete) are among such classifications \cite{hall03}.

Hall and Holmes \cite{hall03} compared six attribute selection methods, including information gain attribute ranking (a simple and fast method that uses
entropy and information gain measures), Relief (an instance-based method with its extension, ReliefF, to handle noise and multiclass data sets), 
Principal Component (an statistical technique that can reduce the dimensionality of data using transformations), 
CFS (Correlation-based Feature Selection that evaluates subsets rather than individual attributes using some heuristic), 
consistency-based subset evaluation (that uses class consistency as an evaluation metric), and the Wrapper attribute selection method.
They benchmarked their results across 15 UCI data sets \cite{Blake+Merz:1998} and against C4.5 \cite{quinlan92} and naive Bayes \cite{domingos97optimality}.
Their results show that attribute selection can improve the performance of common learning algorithms and that there is no single best attribute
selection method for all cases. However, they show that \cite{hall03} Wrapper is the most accurate attribute selection method (when speed is not an issue).

Hall and Holmes' study has led this study to explore different column pruning methods, including Wrapper and a variation of Wrapper called Local Wrapper
developed by Chen et al. \cite{me05c,me06d}, and also simple, near-linear-time column pruning methods developed by Baker \cite{baker07}.
These column pruning methods are described in Section \ref{s:coseekmoColumn}.

Column pruning methods can search for the best attributes using {\em forward selection} or {\em backward elimination} of the attributes.
In forward selection, the column pruner starts with an empty subset and adds attributes to the list as they are evaluated.
In backward elimination, the column pruner starts with the the set of all attributes and removes them one at a time as they are evaluated.
These two approaches, as well as the combination of both \cite{baker07}, are applied in several of the column pruners studied in this study.

\section{Row Pruning}
\label{b:rowPruning}

Row pruning, also known as stratification, is used as a pre-processor in effort estimation.
For a given project, row pruning finds similar projects and uses them in estimating the effort for the given project.
This is especially helpful when calibrating an effort estimation method since similar projects have less variation.
Row pruning is applicable to several software models, including COCOMO 81.
Ferens and Christensen stratified data for all of the nine software models they used (REVIC, SASET, 
PRICE-S, SEER-SEM, SLIM, SoftCost, CHECKPOINT, COCOMO II, and SAGE) before calibration \cite{ferens98}.

Researchers have studied row pruning in effort estimation extensively \cite{me04h,me05a,me05c,me06d,shepperd97,shepperd01,lum02}.
The problem of {\em outliers} have been reported in \cite{me06f}.
Outliers are projects that exist in a data set used for calibration of an effort estimation method and negatively
affect the produced model. Row pruning is an ideal method for identifying and removing such outliers.
(An earlier and smaller version of this study did not report row pruning as an effective method. Column pruning methods usually outperformed 
row pruning methods \cite{jalali07a}. However, this is considered to be a problem with the evaluation methods in that study. This study reports
row pruning as an effective method, as it can be seen in Section \ref{s:results}.)

There are many other studies that predict row pruning can improve the performance of methods used in effort estimation in general.
Menzies et al. reported large improvements in terms of PRED(N), defined in Section \ref{b:parametricTests}, when using stratified data 
instead of unstratified data \cite{me04h}. In another study, they report that pruning in general is most important for small datasets \cite{me05c}.
This may seems reasonable since an outlier or an irrelevant attribute can
more negatively affect a model when the size of the data set is smaller.
Such outliers can be removed using row pruning and the irrelevant attributes can be removed using column pruning.
(However, this study has not found any relation between the data set size and the effectiveness of row or column pruning methods. Their
conclusion could be related to the wrong evaluation criteria they used.)

This study only comments on the effectiveness of row pruning for effort estimation in COCOMO 81 models.
However, in a study using COCOMO II, SEER-SEM, and PRICE-S models, Lum et al. predicted that 
adjusting the models for the local environment should improve the performance of these models \cite{lum02}.
Such adjustments can be done using row pruning.

There are also studies that report negative results from certain row pruning methods.
In a more recent study using stratification, Menzies et al. reported negative results for the $NASA93$ data set \cite{me06d}.
This data set is further explained in Section \ref{s:data}.
(This is not consistent with the results of this study on stratification. The reason could be the wrong evaluation criteria they used.)

Stratification is not limited to software effort estimation. Cost estimation in general is a wide research area
and researchers have tried to use similar methods, such as stratification, for cost estimation in many other fields.
Chen and Huang studied stratification for Monte Carlo production cost simulation \cite{huang97}, which is a probabilistic method.
Their study compares a proposed stratification method with conventional stratification methods and reported better variance reduction
in estimates using their proposed methods.

\subsection{Manual and Automatic Row Pruning}

Previous studies such as \cite{me05c,me06d} mostly focused on manual row pruning (also discussed in Section \ref{s:manualStratification}).
However, there exists an automatic approach as well, which was developed in this study and is discussed in Section \ref{s:rowPruning}.
There are similarities between automatic row pruning methods and nearest neighbor methods, which are estimation by analogy methods.
As discussed before, estimation by analogy is a many-data method and is therefore suitable for selecting similar instances from the historical data
to find an estimate for a new project. In general, case-based reasoning methods, which encompasses estimation by analogy, can be used
as automatic row pruning methods. This is discussed in the next section.

\subsection{Case-Based Reasoning and Row Pruning}

As mentioned in Section \ref{b:cbr}, case-based reasoning (CBR) is a more general approach for finding similarities between past projects and a current project.
While row pruning methods use a similar approach to CBR, they may differ in the way CBR trains a model. CBR finds
solutions to similar existing problems to generate a solution to a current problem.
In training, a row pruning method may function similar to a rule induction algorithm (as discussed before), in that it trains a model without
any knowledge of the current problem. However, in order to train the best model possible, a train instance
can simulate the role of the current problem in training the model, similar to CBR.
It is clear that such a train instance may or may not be similar to the current problem. Hence, the resulting model may not perform well.
There are similarities between estimation by analogy (discussed in Section \ref{b:eba}) as a type of CBR
and the row pruning methods used in this study (discussed in Section \ref{s:rowPruning}).

Since CBR is model free \cite{shepperd01}, using CBR methods (such as the nearest neighbor algorithm, discussed in Section \ref{s:nearestNeighbor}) 
in effort estimation can reduce the need for a certain model such as COCOMO.
The reason is that, nearest neighbor algorithms make few or no assumptions about the domain. Therefore, they can be applied to a variety
of data sets based on different effort estimation models. However, this can also be considered a drawback of this algorithm since ignoring 
important domain knowledge and searching for similar instances ``blindly'' can later lower the performance of the learned model or increase the
error in the estimate. (This is confirmed by the current study as it can be seen in Section \ref{s:results}. There is a solution to this problem
and that is to augment the nearest neighbor algorithm with another method that takes into account the domain assumptions. The row pruning method
developed in this study follows this approach. This is further discussed in Section \ref{s:locomo}.)

\section{Learners}
\label{b:learners}

Learners are essentially machine learning tools that can find a pattern in the data or generate a model, among many other application for them.
In effort estimation, learners are used to learn a model from the historical data, which can later be applied to new projects. The learned theory
is used to find an estimate for those new projects. This study generally applies the name learner to any effort estimation method that
can find an estimate. There may be other classifications for learners as well. For example, the nearest neighbor algorithm discussed before (or
other CBR methods) do not generally learn a model. They use the historical data to find an estimate for a new project without generating a model
that can be applied to a second project, meaning that, there is no actual learning involved. (As a result, when the nearest neighbor is analyzed
in Section \ref{s:results}, it is shown without a learner and only as a row pruner.)

This study focuses on regression methods such as linear regression, local calibration \cite{boehm81}, and model trees \cite{quinlan92b} as learners.
Linear regression and model trees can be found in Weka, Waikato Environment for Knowledge Analysis, along with numerous other machine 
learning tools \cite{Witten05}. These learners are discussed in detail in Section \ref{s:coseekmoLearner}.

In general, different machine learning methods can be combined in different orders to create different methods.
Effort estimation methods can also be combined this way. The goal is to create a better estimation method using the aggregate performance of such methods.
Clearly, not all combinations will result in a more powerful method due to the conflicting nature of some methods.

Theoretically, the {\em stacking} or combining of $n$ methods can be done in $n!$ ways. A {\em meta-learner} is used in stacking to learn 
which methods are reliable and find the best way to stack different methods \cite{Witten05}. This process becomes harder as more methods have to be considered.
The number of available methods is large and grows larger with new data mining toolkits appearing more frequently. 
Weka, the R Project (available online at \url{http://www.r-project.org/}), and Orange (available online at \url{http://www.ailab.si/orange/}) are among 
such toolkits. Therefore, such a large number of methods can potentially create thousands of combinations, which must be evaluated and pruned 
before the search space gets filled with several over-elaborate methods. (This study compares 312 combinations and prunes the majority of them.)

{\em Bagging} and {\em boosting} are among other meta-learning algorithms \cite{Witten05}. Their application in effort estimation was recently investigated by
Baker \cite{baker07} and no significant improvement in model accuracy was reported. This study does not explore these methods.

\section{Evaluation}
\label{b:evaluation}

Evaluation of effort estimation methods is probably as important as finding such methods. Without a proper evaluation of these methods,
no decision can be made about their relative performance. Hence, effort put into developing them may have well been wasted.
Usually the comparison of effort estimation methods is done through some statistical test that compares their error distributions \cite{Witten05}.
It is important to choose the right statistical test for a comparison. This section describes the benefits and limitations of two different categories of tests.

First, it is helpful to understand different ways of collecting error distributions. 
In general, error is defined as the difference between the actual and expected behavior of a certain object.
In effort estimation, error of a method is measured as a function of the actual effort needed and the prediction (or estimate) of effort provided by that method.
Here are some of the most used error definitions in effort estimation:

\begin{itemize}
\item {\em Absolute Residual} (AR) is defined as
\begin{displaymath}
\left| actual - prediction \right|
\end{displaymath}
which is one of the simplest error definitions and is the absolute value (magnitude) of the difference between actual and predicted efforts.
Another terminology, also used in this study, for AR is {\em Magnitude of Error}, ME.

\item {\em Relative Error} (RE) is defined as
\begin{displaymath}
\frac{actual - prediction}{actual}
\end{displaymath}
and has both negative and positive error values possible.

\item {\em Magnitude of Relative Error} (MRE) is defined as
\begin{displaymath}
\frac{\left| actual - prediction\right|}{actual}
\end{displaymath}
which is simply the magnitude of RE.

\item {\em Magnitude of Error Relative to the estimate} (MER) is defined as
\begin{displaymath}
\frac{\left| actual - prediction \right|}{prediction}
\end{displaymath}
and differs from MRE in the fact that it measures the error relative to the predicted value. MER was proposed by Kitchenham et al. \cite{kitc01}.

\item {\em Balanced Relative Error} (BRE) is defined as
\begin{displaymath}
\begin{cases}
\frac{prediction - actual}{actual} & \text{if } prediction - actual \geq 0 \\
\frac{prediction - actual}{prediction} & \text{if } prediction - actual < 0 \\
\end{cases}
\end{displaymath}
and was suggested by Miyazaki et al. \cite{miyazaki94}. 

\item {\em Inverted Balanced Relative Error} (IBRE) is defined as
\begin{displaymath}
\begin{cases}
\frac{prediction - actual}{actual} & \text{if } prediction - actual < 0 \\
\frac{prediction - actual}{prediction} & \text{if } prediction - actual \geq 0 \\
\end{cases}
\end{displaymath}
and was also suggested by Miyazaki et al. \cite{miyazaki94}. 
\end{itemize}

Some of these error definitions such as AR, MER, and MRE are used in many studies \cite{shepperd01,shepperd-kadoda01,myrtveit05,foss05,kitc01}.
On the other hand, BRE and IBRE have not been used in many studies and the study by Foss et al. does not report the tests based on 
these any better than the ones based on MER or MRE \cite{foss05}.
Therefore, this study uses AR, MER, and MRE as the {\em evaluation criteria} in the analysis of results of different effort estimation methods.

Many statistical tests only specify whether the distributions are identical (equal) or not.
This is also known as verifying the {\em null hypothesis} that the two samples are identical.
A null hypothesis is a hypothesis compared with an alternative hypothesis using statistical tests.
This type of tests is frequently used and several well-known tests such as {\em Student's t-test} are among the tests in this category.

Other tests can offer comparisons where one distribution can be considered better or worse than another. This will offer conclusive results
about the performance of test subjects represented with these distributions. Hence, these tests may be preferred over the tests that only verify the 
null hypothesis. However, not many statistical tests can provide such a comparison. Usually, these tests are created based on the needs of the study by augmenting
a test that verifies the null hypothesis with a simple test, such as the median or mean comparisons. In this case, if the null hypothesis is rejected,
meaning that the distributions are not identical, the medians (or means) of each distribution are compared to find which one performed better.

In general, statistical tests are categorized into two groups of {\em parametric} and {\em non-parametric} tests.
These are defined in the following sections. 

\subsection{Parametric Tests}
\label{b:parametricTests}

Parametric tests assume parameterized distributions in the data. The most common parameterized distribution is the {\em normal} or {\em Gaussian} distribution.
Parametric tests such as the t-test and ANOVA (analysis of variance) assume a normal underlying distribution.
Student's t-test is one of the most popular parametric tests. Using its different versions, it can be applied to two independent distributions (where
each distribution contains a random instance, which may or may not have a relationship with another instance in the other distribution) or to two paired 
distributions (where each instance of one distribution has a unique relationship to an instance of the other distribution).
It can be used to test whether two error distributions (based on MRE for example) are
statistically the same or not \cite{chen05a,me05c,me06d}. However, there are several limitations to a parametric test such as the t-test.

The main limitation of a parametric test is that it assumes an underlying distribution when such a distribution may or may not exist.
For example, several previous studies \cite{me06d,me05c,me04h,jalali07a} uses t-tests to compare the error distributions. This study repeated the experiments
in \cite{me06d,jalali07a} and as Figure \ref{figure:nonNormal} shows, the underlying distributions are not normal. Hence, there is a need for
checking the underlying distribution before proceeding with parametric tests, which are frequently used in the literature.
Such verifications may certainly fail in different cases and hence, there is a need for tests that do not assume an underlying distribution.
Such tests belong to the category of non-parametric tests, which is described in the next section.

Another limitation of a parametric test such as the t-test is that they are usually susceptible to outliers (defined before).
Outliers have large deviations comparing to other instances in the distribution and greatly affect the mean and standard deviation calculations
used frequently in parametric tests.
As Menzies et al. mention in their study \cite{me06d}, the presence of large deviations makes it harder to assess the performance of different methods.
Therefore, comparisons will show instability and evaluation of effort estimation methods becomes pointless.
The instability problem is discussed further in Section \ref{b:instability}.
One way to avoid the problem of outliers is to use rankings of error values, instead of the error values, to compare methods.
This is the approach in some non-parametric tests, as described in the next section.

Student's t-test is not the only parametric test used. Most of the studies mentioned before also used mean and standard deviations of 
the error estimates, such as MRE, in their evaluation methods. Although mean MRE is more frequently used in the literature than other
mean values, it is neither the best choice nor it is suitable in every case.
In a study by Foss et al. \cite{foss05}, mean MRE (MMRE), mean MER (MMER), mean BRE (MBRE), mean IBRE (MIBRE), and median MRE (MdMRE) were compared
to SD, RSD, and LSD, which are defined below. (Unlike all other tests in their study, MdMRE is not a parametric test.)
According to the results of their study, although ``MMRE has for many years been, and still is, the de facto 
criterion to select between competing prediction models in software engineering,'' it is ``an unreliable criterion'' and therefore, 
cannot be relied on in comparison of effort estimation methods  \cite{foss05}.
They suggest MMER to be preferred over MMRE and conclude that MMRE, MMER, MBRE, MIBRE, and MdMRE are ``substantially more unreliable as evaluation criteria
than SD, RSD, and LSD \cite{foss05}.'' Even so, they consider none of these as universal solutions for comparing effort estimation methods due
to either a flaw or a limitation in these criteria.

{\em Standard Deviation} (SD) is defined as
\begin{displaymath}
\sqrt{\frac{\sum(actual_i - prediction_i)^2}{n - 1}}
\end{displaymath}
where $n$ is the size of the distribution and $actual_i$ and $prediction_i$ are the corresponding values for each instance in the distribution.

{\em Relative Standard Deviation} (RSD) is defined as
\begin{displaymath}
\sqrt{\frac{\sum(\frac{actual_i - prediction_i}{x_i})^2}{n - 1}}
\end{displaymath}
where $x_i$ is a certain variable in the data such as function points, FP \cite{foss05}.

{\em Logarithmic Standard Deviation} (LSD) is defined as
\begin{displaymath}
\sqrt{\frac{\sum(e_i - (- \frac{s^2}{2}))^2}{n - 1}}
\end{displaymath}
where $e_i$ is define as
\begin{displaymath}
\ln actual_i - \ln prediction_i
\end{displaymath}
and $s^2$ is the variance of $e_i$ \cite{foss05}.

Another popular parametric test using MRE is PRED(N) defined as
\begin{displaymath}
\frac{1}{T}\sum_{i=1}^{T}
\begin{cases}
1 & \text{if } MRE_i \leq N \\
0 & \text{if } MRE_i > N \\
\end{cases}
\end{displaymath}
and is usually used with $N = 0.25$ and $N = 0.30$. It is also described in terms of percentages such as PRED(30).
PRED(N) is used in many studies where MMRE and other MRE-based methods are used \cite{me04h,me06d,shepperd96,briand00}.
However, Foss et al.  ``do not believe that reporting several measures that are all based on MRE would improve matters'' in comparing methods \cite{foss05}.
Menzies et al. \cite{me06d} suggest using a combination of parametric tests, which they call {\em rejection rules}. This is further discussed in
Section \ref{s:rejectionRules}.

\subsection{Non-Parametric Tests}

Non-parametric statistics includes a large group of tests that do not assume an underlying distribution and are hence considered {\em distribution free}.
This makes non-parametric tests a suitable candidate for effort estimation studies since, unlike parametric tests, they do not require verification
of the underlying distribution. Moreover, if such a verification fails, non-parametric tests become the only possible choice.
In general, due to fewer assumptions they make, non-parametric tests are considered statistically more robust (meaning that violations of
their assumptions do not affect them unpredictably and they still perform well).

The application of non-parametric tests in effort estimation studies \cite{demsar06,kitc01,briand00,kadoda00,foss05} have not been as frequent as 
the parametric ones. Usually, simple non-parametric tests are used. For example, Foss et al. studied median MRE \cite{foss05}, which can be considered 
a non-parametric test since it does not need to have any specific distribution. 
Other researchers have used median values as well. However, similar to the results from \cite{foss05}, no conclusive results were offered as to 
which evaluation method performed well for general use.
Demsar \cite{demsar06} suggests using non-parametric tests, which are mentioned to be ``simple, yet safe and robust.'' Demsar's study
analyzes other papers and compares different evaluation methods on classifiers' performance. In order to compare two classifiers, Demsar uses methods such as
averaging over data sets, paired t-tests, Wilcoxon signed-rank test \cite{wilcoxon45a}, and finally counts of wins, losses, and ties based on a sign test
(also suggested by \cite{brouck03}). The non-parametric Wilcoxon signed-rank test is considered an alternative to the parametric 
paired t-test \cite{briand00,demsar06}.
When comparing multiple classifiers, Demsar uses ANOVA and Friedman test, which was augmented with other tests in case the null hypothesis was rejected.
Friedman test is a non-parametric equivalent of the parametric test ANOVA.

Demsar's results show that the parametric test ANOVA is no better than the non-parametric Friedman test. 
More generally, using empirical results, Demsar suggests using the two non-parametric tests, Wilcoxon signed-rank and Friedman tests.
Although the results of Demsar's study clearly suggest non-parametric tests, there are better non-parametric tests that can be used in a wider range
of experiments. More specifically, Friedman test requires other additional tests and Wilcoxon signed-rank test can only be applied 
where the two samples are related or are two replications of the same experiment on the same sample.

Another non-parametric test that verifies the null hypothesis is the Mann-Whitney U test \cite{mann47}, which is discussed in detail in Section \ref{s:mwu}.
Although the Mann-Whitney test can only verify the null hypothesis, a simple comparison of the two medians of the ranks for each distribution, 
generated during the procedure, will determine the preferred distribution. This test shows a great amount of stability as shown in
Section \ref{s:results}.

There are other alternatives for non-parametric tests as well. Kitchenham et al. \cite{kitc01} suggest using {\em boxplot}s as alternatives to 
parametric tests such as MMRE and PRED(N). According to their study, boxplots show the median values as the central location for the distribution
and show two tails for each boxplot. A boxplot shows the spread of the distribution using the height of the box and the skewness
of the distribution using the position of the median and the length of boxplot tails. Using the residuals, $prediction - actual$, is suggested as one of 
the possible variables for boxplots.

Menzies et al. have a similar approach using {\em quartile charts} \cite{me07b}. A quartile chart is generated by sorting the distribution and
dividing the results into four quartiles. The median is represented with a dot and the upper and lower quartiles are represented with vertical lines.

Although boxplots and quartile charts are non-parametric tests that summarize the data, they use visual representations.
Analyzing visual representations in studies where a large number of methods are used across different data sets requires a great amount of 
time and accuracy and therefore, offering a summary of the results becomes a cumbersome task. As a result, this study does not focus on boxplots or 
quartile charts for evaluating its large number of methods.

\subsection{Evaluation Bias}

There are numerous evaluation methods and inherently, every effort estimation study ignores some evaluation method. Therefore, 
every study is biased toward a certain group of evaluation methods. In general, evaluation bias cannot be avoided and without it no major study can find any
conclusive results, since each evaluation method can suggest a different conclusion. Nonetheless, its extent can be reduced to a minimum such 
that the choice of evaluation methods does not affect the results as much while making it possible to find stable conclusions.

Evaluation bias can exist in effort estimation studies in different forms. One of the most common evaluation biases is the way that an evaluation method
behaves across different data sets. In order to avoid several underlying characteristics of a data set that may unpredictably affect the conclusions,
Shepperd and Kadoda's study uses simulated data to control these characteristics \cite{shepperd01}. Their study shows that as the characteristics
of the data sets change, the conclusions made using the same methods also change. However, none of the methods studied could be considered better than
others in the comparisons made using several evaluation methods across the simulated data sets with different characteristics.
Hence, different data sets can affect the evaluation of the same methods in different ways, causing evaluation bias in the study.

Another place that evaluation bias is visible is when comparing different studies using the same methods. Menzies et al. reported that their
rejection rules, a type of evaluation method they created, reported that stratification was useful \cite{me05c}. A later study \cite{jalali07a}
using the same rejection rules and experimental approach contradicted the previous results, showing that stratification was not useful.
This shows the amount of instability some evaluation methods can create when an experiment is repeated.

Finally, evaluation bias can be caused by the underlying criteria used in the evaluation method. For two underlying criteria of MRE and MER used
in a simple mean test, Foss et al. argue that mean MER is a better test than mean MRE \cite{foss05}. Although this test is very simple, it shows
how much different criteria can affect a test. More sophisticated tests are usually more affected by different underlying evaluation criteria 
since there are many factors involved and changing one could have an adverse effect on the others.

This study aims at reducing the evaluation bias in comparing effort estimation methods by using a better test, several evaluation criteria,
different data sets and subset of those data sets, and several randomized runs of the same experiment to produce different results.

\section{Instability}
\label{b:instability}

Stability is a defining factor in accepting the conclusions of a study and without it, it is impossible to compare studies, approaches, or methods.
The effort estimation literature has reported many instabilities in the results and as a result, no clear conclusion has been accepted widely
as to which method or methods perform the best. For example, Shepperd and Kadoda \cite{shepperd01} compared different methods and reported
no stable conclusions despite their many efforts.

Recently, some researchers have realized this problem and attempted at analyzing its sources \cite{myrtveit05,shepperd01,kitc01,foss05}. Among these
studies, some were pessimistic about finding a possible solution to the problem while a few suggested general approaches without a detailed plan.
Foss et al. \cite{foss05} compared several evaluation methods and reported no clear conclusion about the preferred method as a universal evaluation method.
As a result, they state that, ``it probably is futile to search for the Holy Grail: a single, simple-to-use, universal goodness-of-fit kind of metric,
which can be be applied with ease to compare'' different methods \cite{foss05}. 

Myrtveit et al. \cite{myrtveit05} consider the problem of instability a ``poorly understood'' problem and suggest that the research procedure in 
effort estimation studies (using a single data sample, an accuracy indicator, and cross-validation) is the source of the problem due to its unreliability.
As a result, they ``cast some doubt on the conclusions of any study of competing software prediction models that used this research procedure as a basis
of model comparison \cite{myrtveit05}.'' Their solution is a rather general solution, which suggests developing more reliable research procedures.

Kitchenham et al. \cite{kitc01} consider it essential to understand how to make comparison between competing models and mention that some of the
different accuracy indicators used by different researchers generated contradictory results. They continue, ``without understanding what the various 
indicators are describing, meaningful comparison is not possible. Furthermore, if we cannot make meaningful comparisons we cannot make progress \cite{kitc01}.''
Once again, only a general solution is given for the problem of instability in comparing methods.
Shepperd and Kadoda's study \cite{shepperd01} suggests exercising caution when comparing different approaches along with few general guidelines and methods.

Although none of the above studies suggested a clear solution to the problem of instability in comparing effort estimation methods, this does
not mean that such a solution does not exist. As a matter of fact, this study reports stability in comparing a wide range of effort estimation
methods across different data sets, evaluation criteria, and randomized runs. This might be the first study that reports such stability and it
is expected that future studies will find similar stabilities as well.

\section{Summary of Current Problems}
\label{b:currentProblems}

There are many problems that an effort estimation study may face. Four of the more prominent problems are summarized here.

\begin{itemize}
\item Effort estimation studies lack stability in their conclusions in general. Recently, researchers attempted at finding the source of such instabilities.
However, no clear approach is suggested to reduce or diminish instability. 
\item Lack of publicly available data sets has affected effort estimation studies greatly since their suggested methods cannot be tested thoroughly.
Moreover, these data sets may not be suitable for every study since they were collected using certain models.
Unless a researcher can access private or commercial data, which makes the experiments unrepeatable for others, the study has to use simulated data.
Simulated data has its own limitations and cannot always represent the real-world examples.
\item There are too many effort estimation methods and without a proper pruning of this list, researchers will not be able to compare them conclusively.
Hence, little progress can be made in finding better methods.
\item The evaluation approaches used in effort estimation studies need to be revised and better approaches, accepted by the majority of researchers, 
have to be applied in order to reduce the instability present in the current studies.
\end{itemize}

This research applies better evaluation criteria and as a result, offers solutions for the instability problem.
It also prunes many effort estimation methods and provides a framework for continuing this pruning.
Although in this study the lack of data is offset by using different subsets of data sets, this problem requires the help of 
the software engineering industry by releasing their data, which will ultimately benefit them by providing them with better effort estimation methodologies.
