This chapter describes the laboratory studies performed throughout this research.
In this work, COSEEKMO served as the framework in which many types of experiments became possible.
As a result of these studies, several tools such as Locomo were developed. Also, an existing systematic error 
in the evaluation of methods became clear, which resulted in using a new evaluation method called the Mann-Whitney U test.
Finally, many of the methods developed by other researchers
such as Shepperd's nearest neighbor method \cite{shepperd01} and Baker's column pruning method \cite{baker07} were incorporated in COSEEKMO.

The experimental design is described in Section \ref{s:experimentalDesign}, including the data used in this study,
the experimental method, and a general description of the evaluation of the results.
This study focuses on column and row pruning among other methods for effort estimation.
Column pruning is discusses in detail in \cite{baker07} and is mentioned in the methods used in COSEEKMO
in Section \ref{s:coseekmoColumn}.
On the other hand, part of this study is mainly about different row pruning methods. These methods are discussed
in Section \ref{s:rowPruning}.

Another part of this study is designated to the evaluation methods used to compare effort estimation methods.
Sections \ref{s:parametricTests} and \ref{s:nonparametricTests} explain several different parametric and non-parametric
tests used respectively. Section \ref{s:mwu} explains the Mann-Whitney U test, a non-parametric test, in detail.

Section \ref{s:coseekmo} categorizes all different methods in COSEEKMO and space of combined methods
possible in COSEEKMO. Such combinations are used in this study to find the group of best methods suitable
for effort estimation. (A manual for COSEEKMO is provided in Appendix \ref{a:manual}.)
Section \ref{s:results} provides the results and discusses the findings based on these results.

\section{Experimental Design}
\label{s:experimentalDesign}

All the experiments in this work were done using the COSEEKMO tool. This study focus on 
effort estimation methods based upon Boehm's 1981 version of the COCOMO model \cite{boehm81}, also called COCOMO 81, since there is
publicly available data sets in this model's format. Boehm's updated version of COCOMO, called COCOMO II \cite{boehm00b},
can also be supported in the methods present in COSEEKMO as it is shown for one
such method called Cocomin \cite{baker07}. However, since there is no publicly available data set
in the COCOMO II format, this study does not explore this model. 
The COCOMO model is further explained in Section \ref{b:cocomo}.
 
\subsection{Data}
\label{s:data}

The data used in this study was from two data sets:

\begin{itemize}
\item $COC81$ containing 63 records in the COCOMO 81 format \cite[p496-497]{boehm81} and
\item $NASA93$ containing 93 NASA records in the COCOMO 81 format.
\end{itemize}

Taken together, these two data sets are the largest COCOMO-style data source in the public domain 
(for reasons of corporate confidentiality, access to Boehm's COCOMO II data set is highly restricted).
Boehm used the 63 projects present in $COC81$ in his study to calibrate the COCOMO 81 model.
$NASA93$ was originally collected to create a NASA-tuned version of COCOMO, funded by the Space Station Freedom Program.
It contains data from six NASA centers including the Jet Propulsion Laboratory. 
Menzies et al. report that there is a large deviation seen in the $NASA93$ data \cite{me06d}. According to them,
this was caused by the presence of a wide variety of projects rather than poor data collection.
They explain the process of data collection in detail and believe that
``$NASA93$ was collected using methods equal to or better than standard industrial practice \cite{me06d}.''
However, this work shows that the reason for the large deviations in $NASA93$ as well $COC81$ is the
evaluation method used, which was based on parametric assumptions. These assumptions are shown
not to hold. Therefore, their belief that equal or larger deviation can be seen in industrial data based on
what they observed in $NASA93$ does not hold.

In this study, effort estimators were built using all or some part of data from $COC81$ and $NASA93$ data sets.
These two data sets contain several different subsets. The name of these subsets and the number of subsets used (in parenthesis) are:

\begin{itemize}
\item All (2): selects all records from a particular source.
\item Category (2): $NASA93$ designation selecting the type of project such as avionics.
\item Center (2): $NASA93$ designation selecting records relating to where the software was built.
\item Fg (1): $NASA93$ designation selecting either ``$f$'' (flight) or ``$g$'' (ground) software.
\item Kind (2): $COC81$ designation selecting records relating to the development platform such as max for mainframe.
\item Lang (2): $COC81$ designation selecting records about different development languages such as ftn for FORTRAN.
\item Mode (4): designation selecting records relating to the COCOMO 81 development mode such as semi-detached, embedded, or organic.
\item Project (2): $NASA93$ designation selecting records relating to the name of the project.
\item Year (2): $NASA93$ term that selects the development years, grouped into units of five. For example, years 1970, 1971, 1972, 1973, and 1974
are labeled ``1970''.
\end{itemize}

Overall, $COC81$ and $NASA93$ data sets contain 57 subsets (including the super sets).
However, only 19 of these subsets were used in this study. Their names and sizes are provided in Table \ref{table:subsetNames}.
The reason is that the rest of the subsets contain fewer than 20 projects (with 25 of them containing fewer than 10 projects).
As described in \cite{me06d}, due to choosing a test set size of 10, there will not be enough projects to train a model in the subsets
that contain fewer than 20 projects.

\begin{table}
\begin{center}
\begin{tabular}{|c|l|l|c|}
\hline
Number & Data Set & Name & Size \\
\hline
1 & $COC81$ & all & 63 \\
2 & $COC81$ & kind-max & 31 \\
3 & $COC81$ & kind-min & 21 \\
4 & $COC81$ & lang-ftn & 24 \\
5 & $COC81$ & lang-mol & 20 \\
6 & $COC81$ & mode-e & 28 \\
7 & $COC81$ & mode-org & 23 \\
8 & $NASA93$ & all & 93 \\
9 & $NASA93$ & category-avionicsmonitoring & 30 \\
10 & $NASA93$ & category-missionplanning & 20 \\
11 & $NASA93$ & center-2 & 37 \\
12 & $NASA93$ & center-5 & 39 \\
13 & $NASA93$ & fg-g & 80 \\
14 & $NASA93$ & mode-embedded & 21 \\
15 & $NASA93$ & mode-semidetached & 69 \\
16 & $NASA93$ & project-gro & 23 \\
17 & $NASA93$ & project-X & 38 \\
18 & $NASA93$ & year-1975 & 37 \\
19 & $NASA93$ & year-1980 & 38 \\
\hline
\end{tabular}
\end{center}
\caption{Names and sizes of subsets of $COC81$ and $NASA93$.}
\label{table:subsetNames}
\end{table}

The subsets of each data set can overlap with each other since a project may be categorized in different ways (for example year and center may share
projects). Therefore, different projects may belong to more than one subset of each data set. These overlaps for $COC81$ and $NASA93$ 
data sets are provided separately in tables \ref{table:coc81Overlap} and \ref{table:nasa93Overlap} respectively.
It should be noted that the subset {\em all} is the super set for each data set and therefore will overlap with every other subset.
In each data set, the overlap is shown as $\frac{|A \cap B|}{|A \cup B|}$ for all pairs of subsets $A$ and $B$.

\begin{table}
\begin{scriptsize}
\begin{center}
\begin{tabular}{c|cccccc}
Subset &      2 &      3 &      4 &      5 &      6 &      7 \\ 
\hline
     1 &  31/63 &  21/63 &  24/63 &  20/63 &  28/63 &  23/63 \\ 
     2 &        &   0/52 &  16/39 &   2/49 &  10/49 &  15/39 \\ 
     3 &        &        &   6/39 &  14/27 &  16/33 &   4/40 \\ 
     4 &        &        &        &   0/44 &   7/45 &  12/35 \\ 
     5 &        &        &        &        &  13/35 &   4/39 \\ 
     6 &        &        &        &        &        &   0/51 \\ 
\end{tabular}
\end{center}
\end{scriptsize}
\caption[Overlap of subsets of $COC81$.]{Overlap of subsets of $COC81$ shown as intersection/union for each pair of subsets.
Subset numbers match the ones in Table \ref{table:subsetNames}.}
\label{table:coc81Overlap}
\end{table}

\begin{table}
\begin{scriptsize}
\begin{center}
\begin{tabular}{c|ccccccccccc}
Subset &      9 &     10 &     11 &     12 &     13 &     14 &     15 &     16 &     17 &     18 &     19 \\
\hline
     8 &  30/93 &  20/93 &  37/93 &  39/93 &  80/93 &  21/93 &  69/93 &  23/93 &  38/93 &  37/93 &  38/93 \\ 
     9 &        &   0/50 &  13/54 &  17/52 &  30/80 &   3/48 &  24/75 &   4/49 &  17/51 &  20/47 &   5/63 \\
    10 &        &        &   1/56 &   7/52 &  20/80 &   2/39 &  18/71 &   1/42 &   7/51 &   3/54 &  15/43 \\ 
    11 &        &        &        &   0/76 &  32/85 &   5/53 &  32/74 &  23/37 &   0/75 &  10/64 &  13/62 \\  
    12 &        &        &        &        &  33/86 &  13/47 &  23/85 &   0/62 &  38/39 &  23/53 &  14/63 \\ 
    13 &        &        &        &        &        &   8/93 &  69/80 &  20/83 &  33/85 &  31/86 &  31/87 \\ 
    14 &        &        &        &        &        &        &   0/90 &   3/41 &  12/47 &  12/46 &   9/50 \\ 
    15 &        &        &        &        &        &        &        &  20/72 &  23/84 &  25/81 &  27/80 \\ 
    16 &        &        &        &        &        &        &        &        &   0/61 &   0/60 &   9/52 \\ 
    17 &        &        &        &        &        &        &        &        &        &  23/52 &  13/63 \\ 
    18 &        &        &        &        &        &        &        &        &        &        &   0/75 \\ 
\end{tabular}
\end{center}
\end{scriptsize}
\caption[Overlap of subsets of $NASA93$.]{Overlap of subsets of $NASA93$ shown as intersection/union for each pair of subsets.
Subset numbers match the ones in Table \ref{table:subsetNames}.}
\label{table:nasa93Overlap}
\end{table}

\subsection{Experimental Method}
\label{s:experimentalMethod}

This work is based on cross-validation. COSEEKMO uses cross-validation to partition the data
into train and test sets. COSEEKMO does this is two different ways in order to study the effects of
stratification (discussed later in Section \ref{s:rowPruning}) suggested by Boehm \cite{boehm00b}.
Each subset (of $COC81$ or $NASA93$) is partitioned into a test set and a train set.
Also, all the instances in the superset (of the subset) that are not present in the test set are
stored in another train set. The first train set is used when studying the effect of stratified data and 
the second train set is used when studying the effects of non-stratified data. In each run, each train set is
used individually to train a model. That model is then tested on the test set.

In general, a model is trained on the records in the train set and tested on the records in the test set, each representing
a {\em hold out} record. Using a set of hold out records, represented by the test set in this study, is a common practice \cite{witten99,Witten05,me04h}.
For each run, COSEEKMO uses a different seed for random number generation, resulting in different
train and test sets. Hence, each method is trained and tested on different sets.
In these experiments, test sets have a constant size, set to 10. This size is chosen as a result of prior research \cite{me06d} using COSEEKMO.
This process is repeated 20 times as described in Section \ref{s:coseekmoAlgorithm}.

One of the other possible options is to use all the data set to train a model and test on the same data set.
However, this option is not suitable since in the real world examples, the goal is
to assess how a model predicts the effort for a new project \cite{me06d} not seen before.
Also, as Ferens and Christensen \cite{ferens98} describe in their study, the failure to use a hold out sample,
like the test set in this work, can overstate a model's accuracy on new examples.

Another option is the k-fold cross-validation, where a set is partitioned into k subsets. Each time,
exactly one different subset is used in testing the model while the other k-1 subsets are used in training the model.
This option allows for the maximum amount of data for training a model.
On the other hand, it is computationally expensive for large data sets. Although only some of the subsets of $COC81$ and $NASA93$
are large, this option is not feasible in COSEEKMO in general. COSEEKMO contains several methods resulting in numerous combined
methods. There are also multiple runs in each experiment. Therefore, k-fold cross-validation and other
computationally expensive methods such as bootstrapping are not practically possible in this study.

Bouckaert \cite{brouck03} claims that experiments using cross-validation suffer from low replicability.
However, this is not the case with COSEEKMO since the random number generation can be replicated exactly when the same seed is used,
providing the same results.

\subsection{Evaluation of Results}

The methods in COSEEKMO were evaluated using the non-parametric Mann-Whitney U test, described
in detail in Section \ref{s:mwu}.
The parametric alternatives were not suitable since the error distributions were not normal.
The Mann-Whitney U test compares all the methods and combinations used in COSEEKMO
and returns a table of win-loss-tie values for each data set or its subsets.
Depending on the experiment, one or more of the values reported in such a table were
used to decide the best method or methods. In this study, minimizing the number of losses is used for such decisions.
However, when two methods have the same number of losses, the one with more wins is ranked higher. 
Although non-parametric tests are preferred in this study, the parametric alternatives
are available as well. COSEEKMO originally used parametric tests only and depended on
rejection rules \cite{me06d} that chose one method over others based on parametric criteria.
This is further discussed in Section \ref{s:parametricTests}.

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

Row pruning is used as a pre-processor in this study. This work explores two distinct row pruning methods with different variations.
These are automatic in the way they select similar instances.

This study was initiated partly to explore row pruning methods in order to reduce the presence of outliers as described in Section \ref{b:rowPruning}.
However, after row pruning methods were introduced into COSEEKMO initially, the comparison of methods
did not report row pruning as an effective method. Column pruning methods usually outperformed row pruning methods \cite{jalali07a}.
Nonetheless, soon after the prior study was published, further research showed a systematic error
in evaluation criteria used in COSEEKMO and other effort estimation studies in general. This is further discussed in Sections \ref{b:evaluation}
and \ref{s:parametricTests}.
The evaluation criteria was the reason for the outliers problem as well, which was the driving force for developing an effective row pruning method.
Since outliers were artifacts of the previous evaluation criteria and did not exist in the current results,
the first conclusion was that row pruning was not required anymore.
Nonetheless, once this evaluation error was resolved, new experiments proved row pruning to be a worthy pre-processor,
ranking among the top methods reported by COSEEKMO. This is shown in Section \ref{s:results}.

Section \ref{s:manualStratification} briefly discusses manual stratification for certain few similarities it has with automatic row pruning methods in
the remainder of this section. Nearest neighbor, described in Section \ref{s:nearestNeighbor}, uses all the attributes to select similar instances.
This is done using a Euclidean distance measure.
Locomo is similar to the nearest neighbor method in using all the attributes to select similar instances. However,
it uses the local calibration method (described in Section \ref{s:coseekmoLearnerLocalCalibration}) internally to evaluate the selected instances.
Hence, it can be considered a combination method, combining a row pruner and a learner. Therefore, in the remainder of this work whenever Locomo
is mentioned in the results as the row pruning method, it is always followed by the local calibration method as its learner, which is
used internally. Locomo and its variations are discussed in detail in Section \ref{s:locomo}.

\subsection{Manual Stratification}
\label{s:manualStratification}

Boehm et al. advises that effort estimates can be improved via manual stratification (using domain knowledge to select relevant past data) \cite{boehm00b}.
As described in Section \ref{s:data}, both $COC81$ and $NASA93$ data sets are composed of different subsets.
Each subset can be distinguished from other instances in the main data set using the information stored in the instances of the main 
data set such as where and when it was gathered. This is a stratification method that makes use of the similarities between instances. 
It is considered a manual method since the only way to stratify the data is to use the manually gathered information about the data such as
the location and time of the project or instance. As a result, each subset contains similar instances.
Each subset is then partitioned into train and test sets. This assures that the training and testing are done on data that contains similar instances.

This method is a pre-processor and can be compared to its counterpart, which is described in Section \ref{s:coseekmoAlgorithm}. In the other method,
a model is trained using the information in the superset and not in the subset. It is then tested on a test set derived from
the subset. Hence, this study can present the results of comparison of these two methods applied to the data as pre-processors.
These two methods are applied to every other method, whether a pre-processor or not. These two methods are discussed and their results
are analyzed as {\em train type}s since they are more similar to each other in their approach and less similar to automatic row pruning methods discussed here.

\subsection{Nearest Neighbor}
\label{s:nearestNeighbor}

The ANGEL project \cite{shepperd96} inspired this study to explore estimation by analogy as a way to find similarities among train instances,
which can be used to find effort estimates for test instances.
Nearest neighbor uses the normalized Euclidean distance as a measure of similarity. For two instances $X$ and $Y$ each having $m$ attributes,
the normalized Euclidean distance, called distance hereafter, is:

\begin{displaymath}
\sqrt{\sum_{a=1}^m (\frac{X_a - Y_a}{Max_a - Min_a})^2}
\end{displaymath}

Nearest neighbor takes a train file with $n_{train}$ instances as input and finds the distance between every pair of train instances.
It then tries to find the best neighborhood for each train instance $i$.
To do so, it first sorts the remaining instances in ascending order using their distance from $i$.
Then, for each neighborhood $k$, where $1 \le k < n_{train}$, it averages the actual efforts of the first $k$ sorted instances.
This average value is used as the estimate for the effort of instance $i$ when a neighborhood of size $k$ is used.
Finally, depending on the variation of nearest neighbor used, the MRE or AR (also called ME and described in Section \ref{b:evaluation}) is calculated 
for instance $i$ and is added to the sum of MRE's or AR's for neighborhood $k$.
The neighborhood with the minimum sum of MRE or AR is chosen as the best neighborhood.

Once nearest neighbor found the best neighborhood $b$, it uses this neighborhood to find the estimate for each test instance.
Therefore, similar to the training part, the distance between every test instance and all train instances is calculated.
For each test instance $j$, the train instances are sorted in ascending order using their distance from $j$.
Finally, the average of the actual efforts for the first $b$ train instances is used as the estimate of effort for $j$.

\subsection{Locomo}
\label{s:locomo}

Locomo is a row pruner that combines a nearest neighbor method with the local calibration method described in Section \ref{s:coseekmoLearnerLocalCalibration}.
When Locomo was first developed in this work, it only accepted neighborhoods that were set before and would not look for
the most suitable neighborhood. Hence, it was given the name static Locomo. 

On the other hand, dynamic Locomo tries to find the best neighborhood while processing the train set in order. This
neighborhood can change from one train set to another and hence it is dynamic.
Although the two methods and their variations are different, they both use the local calibration method in finding effort estimates.
The local calibration method uses the $k$ nearest train instances (whether $k$ is a constant or it was found during training)
to find that estimate.

\subsubsection{Static Locomo}

Similar to the nearest neighbor method described in Section \ref{s:nearestNeighbor}, static Locomo
uses the normalized Euclidean distance to measure the distance of each test instance $j$ from all train instances.
Then, using the provided neighborhood, $k$, it finds the $k$ closest train instances to $j$. These train instances
are then passed to the local calibration method, which finds an estimate for the test instance $j$.

This process is repeated until an effort estimate is found for every test instance in the test set.
However, since it is not possible to predict the best neighborhood for this method, this study tries
a set of neighborhoods $\{5, 10, 20, 40, 80\}$ as the possible best neighborhoods.
Therefore, for each pair of train and test sets, each one of these neighborhoods is tried
separately and all the results are stored under this method's results when comparing this method against all other methods.

While static Locomo was being developed, the goal was to find a minimum set of neighborhoods that represent other neighborhoods
in their performance. Several neighborhoods were tested and in general the neighborhoods in the set $\{5, 10, 20, 40, 80\}$  
were shown to provide same or better estimates (depending on the data sets) comparing to all other neighborhoods tested.
In addition to performance considerations, these neighborhoods take into account the data set bounds.
The largest data set, $NASA93$, has 93 instances. Since in this study
a test set always contains 10 instances, a train set can contain at most 83 instances. Therefore, a neighborhood of 80 provides 
an upper bound for the neighborhoods that can be used in static Locomo. It should be noted that a neighborhood of 83 will
use all the train set instances, and hence static Locomo simplifies to the local calibration method.
Other neighborhoods were included in this list for similar reasons of representing proper upper and lower bounds for data sets.
Overall, these neighborhoods provided an adequate coverage of the data sets used in this study. 

\subsubsection{Dynamic Locomo}

Although the neighborhoods used in static Locomo were generally the best choices, there were several unavoidable, redundant procedures
used in static Locomo. Also, the choice of neighborhood was not based on a training process using the train set. Therefore,
static Locomo's set of neighborhoods was only suitable for the data sets used in this study and needed revision once new data sets
would be used. Therefore, dynamic Locomo was developed.

Dynamic Locomo can process any COCOMO 81 data set and can be easily modified to accept other data sets based on other models used in effort estimation.
There are no static neighborhoods used in dynamic Locomo. Therefore, it can find the best neighborhood most suitable for a given train set.
Dynamic Locomo uses a similar algorithm to the nearest neighbor algorithm described in Section \ref{s:nearestNeighbor} when looking
for the best neighborhood in the train set.

When given a train set of size $n_{train}$, it first calculates the distance of every train instance $i$ from all other
train instances using a normalized Euclidean distance. Like the algorithm for the nearest neighbor method,
dynamic Locomo tries to find the best neighborhood for each train instance $i$.
To do so, it sorts the remaining train instances in ascending order using their distance from $i$.
Unlike the nearest neighbor method where an average of actual efforts was used, dynamic Locomo uses the local calibration method
to find an effort estimate. So, for each neighborhood $k$, where $1 \le k < n_{train}$, the first $k$ sorted train instances
are passed to the local calibration method along with instance $i$ to find an effort estimate for $i$. This estimated effort is used 
(along with the actual effort) to calculate the MRE value for instance $i$ when neighborhood $k$ is used.

At the end of this process, there will be $n_{train}$ MRE values for each neighborhood.
The neighborhood that has the lowest median or mean MRE (depending on the variation of dynamic Locomo) is chosen as the
best neighborhood $b$. This neighborhood is used to select the closest $b$ train instances to each test instance $j$.
These train instances along with $j$ are passed to the local calibration method to find an effort estimate for $j$.

Dynamic Locomo's source code is available at \url{http://unbox.org/wisp/tags/coseekmo/2.0/locomo/dynamicLocomoMedian.awk}.

\section{Parametric Tests}
\label{s:parametricTests}

Initially, this study used parametric tests to compare different effort estimation methods.
As described in Section \ref{b:parametricTests}, parametric tests assume that there is an underlying parameterized
distribution in the data. For most parametric tests (including all the ones used in this study before),
this underlying distribution is the normal distribution. The parametric tests in this study were used to 
compare different error distributions such as AR and MRE. As it is shown in Figure \ref{figure:nonNormal}, 
these error distributions do not represent a normal distribution.

\begin{figure}
\begin{center}
\includegraphics[width=2.5in]{figures/re_coc81_langftn.pdf}
\includegraphics[width=2.5in]{figures/re_coc81_langmol.pdf}
\includegraphics[width=2.5in]{figures/re_nasa93_fg_g.pdf}
\includegraphics[width=2.5in]{figures/re_nasa93_mode_embedded.pdf}
\includegraphics[width=2.5in]{figures/re_nasa93_project_gro.pdf}
\includegraphics[width=2.5in]{figures/re_nasa93_year_1975.pdf}
\end{center}
\caption[Distributions of relative error in COSEEKMO experiments.]{Relative error (RE) values seen in experiments with COSEEKMO on six different subsets.
Thin lines show the actual values. Thick lines show a Gaussian (normal) distribution that uses mean and standard deviation of the actual values.}
\label{figure:nonNormal}
\end{figure}

Although it is clear that parametric tests are not suitable for this study in particular,
it is beneficial to study such parametric tests in general since they can be used when the underlying distribution
is shown to be normal. Therefore, these tests are discussed in detail in the following sections.

\subsection{General Tests}

There are several evaluation criteria discussed in Section \ref{b:evaluation} such as AR and MRE.
Previously, this study made use of these criteria in different ways.
Mean and standard deviation of these criteria were used extensively. As discussed before, using mean and standard deviation
only make sense if the underlying distribution is normal.

\subsection{Rejection Rules}
\label{s:rejectionRules}

Previously, effort estimation methods used in this study were compared using rejection rules \cite{me06d}.
These rules and their order are shown in Figure \ref{figure:rejectionRules}.
There are five rules used in the given order to compare two methods $x$ and $y$.
The goal is to find the method that performs worse than the other, for every pair of methods in the experiment.
The methods that survive this comparison are reported as the best methods.
These methods cannot be rejected when comparing them to other methods.

Rule 1 is only applied if the MRE values of $x$ and $y$ are statistically different. This is tested
using a two-tailed t-test at the 95\% confidence interval. Therefore, two methods are statistically different
if the following inequality holds:

\begin{displaymath}
\frac{|meanMRE(x) - meanMRE(y)|}{\sqrt{\frac{sdMRE(x)^2}{n(x)-1} + \frac{sdMRE(y)^2}{n(y) - 1}}} > 1.96
\end{displaymath}

Rule 1 returns the method with the higher mean MRE value as the worse method.
However, if the two methods do not have statistically different MRE distributions, other rules may apply.

Rule 2 compares the standard deviation of the MRE values for $x$ and $y$ and returns the method with higher standard deviation as
the worse method. Rule 3 compares the correlation between the predicted and actual values and reports the method with the lower correlation
as the worse method. Rule 4 uses the PRED(30) measure on MRE values and reports the method with the lower PRED(30) value as the worse method.
Rule 5 compares the number of attributes of the subsets used in both methods and reports the one with more attributes as the worse method (since
both have similar performances).

\begin{figure}
{\begin{alltt}\sffamily
\textbf{FUNCTION} worse(x,y)
    \textbf{IF} statisticallyDifferent(x,y) \textbf{THEN}
        \textbf{IF} meanMRE(x) \textless meanMRE(y)     \textbf{THEN} \textbf{RETURN} y \textbf{FI} {\em # rule1}
        \textbf{IF} meanMRE(y) \textless meanMRE(x)     \textbf{THEN} \textbf{RETURN} x \textbf{FI} {\em # rule1}
    \textbf{ELSE}    
        \textbf{IF} sdMRE(x) \textless sdMRE(y)               \textbf{THEN} \textbf{RETURN} y \textbf{FI} {\em # rule2}
        \textbf{IF} sdMRE(y) \textless sdMRE(x)               \textbf{THEN} \textbf{RETURN} x \textbf{FI} {\em # rule2}

        \textbf{IF} correlation(x) \textless correlation(y)     \textbf{THEN} \textbf{RETURN} x \textbf{FI} {\em # rule3}
        \textbf{IF} correlation(y) \textless correlation(x)     \textbf{THEN} \textbf{RETURN} y \textbf{FI} {\em # rule3}

        \textbf{IF} pred(x) \textless pred(y)                        \textbf{THEN} \textbf{RETURN} x \textbf{FI} {\em # rule4}
        \textbf{IF} pred(y) \textless pred(x)                        \textbf{THEN} \textbf{RETURN} y \textbf{FI} {\em # rule4}

        \textbf{IF} \(|Subset(x)|\) \textless \(|Subset(y)|\)           \textbf{THEN} \textbf{RETURN} y \textbf{FI} {\em # rule5}
        \textbf{IF} \(|Subset(y)|\) \textless \(|Subset(x)|\)           \textbf{THEN} \textbf{RETURN} x \textbf{FI} {\em # rule5}
    \textbf{FI}
\textbf{RETURN} 0 {\em # if no reason to return true}
\end{alltt}}
\caption{COSEEKMO's rejection rules.}
\label{figure:rejectionRules}
\end{figure}

These rules were obtained from an earlier study using COSEEKMO by Menzies et al. \cite{me06d}.
They mention that their rejection rules can reproduce Boehm's 1981 COCOMO 81 analysis.
However, this study achieved the same results when the order of the rules were modified \cite{jalali07a}.
Rule 2 was also modified from their study to use the standard deviation only, which did not change the results.
According to their study, lower priority rules were used with a much lower frequency when methods were compared pairwise.

\subsection{Instability}
\label{s:instability}

Although the parametric tests used in this study were able to reproduce the results in the literature, they lacked
the stability when reporting the best methods. Different methods performed differently for different data sets and their subsets.
This is clearly shown in the previous work \cite{jalali07a} prior to this study, reproduced here in 
Figures \ref{figure:pruningTactics} and \ref{figure:neighborhoods}.

\begin{figure}
\begin{center}
\includegraphics{figures/PruningTactics-SdMRE}
\includegraphics{figures/PruningTactics-MeanMRE}
\includegraphics{figures/PruningTactics-Pred}
\end{center}
\caption{Effects of different pruning methods showing instability in using parametric tests.}
\label{figure:pruningTactics}
\end{figure}

\begin{figure}
\begin{center}
\includegraphics{figures/LocalWrapper-Precise-LOCOMO-SdMRE}
\includegraphics{figures/LocalWrapper-Precise-LOCOMO-MeanMRE}
\includegraphics{figures/LocalWrapper-Precise-LOCOMO-Pred}
\end{center}
\caption{Effects of different neighborhoods showing instability in using parametric tests.}
\label{figure:neighborhoods}
\end{figure}

Each figure shows three parametric tests in three separate graphs.
A vertical line in any set of graphs in these figures shows the results of different methods (shown in the legend) on the same subset of a data set.
As it can be seen from these results, different methods perform differently across different data sets and from one parametric test to another.
Hence, it is hard to compare different methods across different data sets. This would be even harder when the results were compared from one run
of the experiment to another, where two runs only differed in their random number generator's seeds.
The source of this problem could be considered the parametric tests. These tests were not suitable for this study 
since the error distributions were not normal.
However, this problem was solved by using non-parametric tests, discussed in Section \ref{s:nonparametricTests}.

\section{Non-Parametric Tests}
\label{s:nonparametricTests}

This study originally used parametric tests. However, as explained before, these tests make assumptions about the
underlying distributions. Such assumptions cannot be guaranteed in every experiment and as Figure \ref{figure:nonNormal}
shows, the experiments done in this study do not have a normal distributions required for the parametric tests done before.
Therefore, non-parametric tests replaced parametric tests in this study.

Non-parametric tests do not assume an underlying distribution and therefore can be used in this study. 
Among different non-parametric tests, the Mann-Whitney U test, also known as the Wilcoxon rank-sum test, is the most
suitable test for comparing the methods used in this study. This test is discussed in Section \ref{s:mwu}.
However, before this test was chosen, other non-parametric tests were explored and studied in detail. One such test
is the median test, discussed in Section \ref{s:medianTest}. 

\subsection{Median Test}
\label{s:medianTest}

The median test used in this study compared two different distributions using their median and spread.
This test sorts the error estimates, using AR, MRE, etc. It then reports value in the middle as the median and
the difference between the values at one-third and two-third of the sorted list as the spread.
Finally, the method with the lowest median and spread was reported as the best method.

Although this test was simple, it did not produce stable and conclusive results. Most of the methods reported as the winners
in one experiment were not reported as the winners in another experiment with a different random number generator seed. Therefore,
a stronger test was needed, which led this research to the Mann-Whitney U test.

\subsection{Mann-Whitney U Test}
\label{s:mwu}

This test was developed independently by Wilcoxon in 1945 and Mann and Whitney in 1947 \cite[p109-118]{sprent93}.
Therefore, it is known by two different names: the Wilcoxon rank-sum test and the Mann-Whitney U test.
Wilcoxon proposed this test as well as the Wilcoxon signed-rank test in the same paper \cite{wilcoxon45a}.
The Wilcoxon signed-rank test is suitable for cases where the two samples are related or are two replications
of the same experiment on the same sample. Since this study explores different samples with different methods,
the Wilcoxon signed-rank test could not be used.

On the other hand, the Wilcoxon rank-sum test requires the two samples to be statistically independent. This is the case in this study, where
two methods applied to a data set create two statistically independent error samples.
However, the Wilcoxon rank-sum test only explores equal sample sizes \cite{mann47}. This could not be assured in this work
since certain pre-processor methods could create error samples with different sizes depending on their heuristics.
Nonetheless, the test proposed by Mann and Whitney, which is an extension of the Wilcoxon rank-sum test, resolved this problem.
As a result, this study uses the Mann-Whitney U test, or the MWU test hereafter.

The MWU test assesses the null hypothesis, which states that the two samples come from identical distributions.
Also, the MWU test requires the samples to have continuous measurements \cite{mann47}.
For two samples $X$ and $Y$, the MWU test first ranks the two samples. To do so, the samples
are sorted into one large sample while maintaining the information about which sample each value came from.
Each value is then ranked with a number between 1 and $|X| + |Y|$. If there are two or more identical values,
the average of the ranks of these values is assigned as their identical ranks. For example, if
$k$ identical values $v_1, ..., v_k$ have ranks $r_1, ..., r_k$, they all get the same rank of:

\begin{displaymath}
\frac{\sum_{i=1}^k r_i}{k}
\end{displaymath}

It is clear that ranking the values removes the effects of the outliers present in certain tests such as the parametric tests.
A value large enough to be considered an outlier will have a larger rank than the previous non-outlier value in the sorted list.
However, this rank is only larger by a constant $c < k$.
Once all the values of both samples are ranked, the MWU test calculates the sum of the ranks for all the values in each sample.
Therefore, for a sample $X$, the sum of the ranks is:

\begin{displaymath}
R_X = \sum_{r_i \in X} r_i
\end{displaymath}

$R_Y$ is calculated the same way.
Using the sum of the ranks for each sample, the $U$ statistic is calculated as follows, where $n_X = |X|$:

\begin{displaymath}
U_X = R_X - \frac{n_X(n_X+1)}{2}
\end{displaymath}

$U_Y$ is calculated the same way.
In addition to $U_X$ and $U_Y$, the mean and standard deviation of $U$ must also be found using the following equations, where
$m_U$ is the mean of $U$, $\sigma_U$ is the standard deviation of $U$, and $n_Y = |Y|$:

\begin{displaymath}
m_U = \frac{n_Xn_Y}{2}
\end{displaymath}

\begin{displaymath}
\sigma_U = \sqrt{\frac{n_X n_Y(n_X + n_Y + 1)}{12}}
\end{displaymath}

Finally, the following normal approximation can be used to calculate the standard normal deviate, $z$, also known as the standard score:

\begin{displaymath}
z = \frac{U - m_U}{\sigma_U}
\end{displaymath}

Since there are two samples $X$ and $Y$, there will be two standard scores, $z_X$ and $z_Y$.
These values are always equal in magnitude and opposite in sign.
Therefore, they are simply identified by $z$, where $z = \left|z_X\right| = \left|z_Y\right|$.
In order to assess the null hypothesis, a confidence interval is used.
This study uses two different confidence intervals. At 95\% confidence interval, $z <= 1.96$ must hold to accept the
null hypothesis. At 99\% confidence interval, $z <= 2.576$ must hold to accept the null hypothesis.

Given two methods $m_X$ and $m_Y$, the acceptance or rejection of the null hypothesis can only 
identify these methods' performance (based on their error samples $X$ and $Y$) as being identical or not respectively.
In the case of non-identical methods, the MWU test does not help in identifying which method performed better.
Nonetheless, in comparison of different methods it is
more interesting to find the ones that performed best. Therefore, in case of two non-identical samples, 
which happens when the null hypothesis is rejected, another non-parametric test can augment the MWU test.
The simplest and most useful non-parametric test is to compare the median ranks of the two samples after the MWU test
considered them non-identical. If the performance measure used in the MWU test is an error estimate (such as AR, MRE, etc.),
a lower value is better. Therefore, if sample $X$ has a lower median rank than sample $Y$, then method $m_X$ is
considered better than method $m_Y$. On the other hand, if the performance measure used in the MWU test is considered better when 
it has a higher value, then method $m_Y$ is considered better than method $m_X$.
Finally, if both samples have the same median rank, their corresponding methods are considered identical.

To summarize, the MWU test augmented with the median rank test can score two methods as follows (when a lower value in a sample is considered better):
\begin{itemize}
\item If the null hypothesis holds, both methods get a {\em tie}. 
\item If the null hypothesis is rejected and the median rank of $X$ is lower than the median rank of $Y$,
method $m_X$ gets a {\em win} and method $m_Y$ gets a {\em loss}.
\item If the null hypothesis is rejected and the median rank of $X$ is higher than the median rank of $Y$,
method $m_X$ gets a {\em loss} and method $m_Y$ gets a {\em win}.
\item If the null hypothesis is rejected and the median rank of $X$ is equal to the median rank of $Y$,
both methods get a {\em tie}.
\end{itemize}
It is clear that if a higher value in a sample is considered better, the above assignments of wins and losses must be switched.

The slowest part of the described algorithm for the MWU test augmented with the median rank test is the sorting
done in the first step. There are two samples of size $n_X$ and $n_Y$ and the combined sample of size $n_X + n_y$ must be sorted.
The rest of the algorithm has a time complexity of $\theta(n_X + n_Y)$.
Therefore, depending on the sorting algorithm, the MWU test's algorithm can be implemented efficiently.
An example of the MWU test is provided in Figure \ref{figure:mwuExample}.

\begin{figure}
\begin{tabular}{|p{.95\linewidth}|}
\hline
There are two samples $A$ and $B$ with $|A| = 5$ and $|B| = 6$:
\begin{center}
$A = \{5,7,2,0,4\}$ \\
$B = \{4,8,2,3,6,7\}$ \\
\end{center}

They are sorted as follows: 
\begin{center}
\begin{tabular}{c|c|c|c|c|c|c|c|c|c|c|c}
Samples & A & A & B & B & A & B & A & B & A & B & B \\
Values  & 0 & 2 & 2 & 3 & 4 & 4 & 5 & 6 & 7 & 7 & 8 \\
\end{tabular} 
\end{center}

The rankings are:
\begin{center}
\begin{tabular}{c|c|c|c|c|c|c|c|c|c|c|c}
Samples & A & A   & B   & B & A   & B   & A & B &  A  & B   & B  \\
Values  & 0 & 2   & 2   & 3 & 4   & 4   & 5 & 6 &  7  & 7   & 8  \\
Ranks   & 1 & 2.5 & 2.5 & 4 & 5.5 & 5.5 & 7 & 8 & 9.5 & 9.5 & 11 \\
\end{tabular} 
\end{center}

The sum and median of A's ranks are:
\begin{center} 
$R_A = 1 + 2.5 + 5.5 + 7 + 9.5 = 25.5$ \\
$median_A = 5.5$ \\
\end{center}

and the sum and median of B's ranks are:
\begin{center}
$R_B = 2.5 + 4 + 5.5 + 8 + 9.5 + 11 = 40.5$ \\
$median_B = (5.5 + 8)/2 = 6.75$ \\
\end{center}

The $U$ statistic for $A$ and $B$ is:
\begin{center}
$U_A = 25.5 - 5*6/2 = 10.5$ \\
$U_B = 40.5 - 6*7/2 = 19.5$ \\
\end{center}

Mean and standard deviation of $U$ are:
\begin{center}
$m_U = 5*6/2 = 15$\\
$\sigma_U = \sqrt{5*6*(5+6+1)/12} = 5.477$ \\
\end{center}

Finally, the $z$ values for $A$ and $B$ are:
\begin{center}
$z_A = (10.5 - 15)/5.477 = -0.82$ \\
$z_B = (19.5 - 15)/5.477 = 0.82$ \\
\end{center}

Since $\left|z_A\right| = \left|z_B\right| = 0.82 < 1.96$, the null hypothesis holds and thus
samples $A$ and $B$ are considered identical (at the 95\% significance level). 
In this case, both methods corresponding to $A$ and $B$ get a tie.
If the null hypothesis did not hold, since $median_A < median_B$, $A$'s method gets a win and $B$'s method gets a loss
(assuming that a low value in the sample is considered better).
\\\hline
\end{tabular}
\caption{An example of the Mann-Whitney U test.}
\label{figure:mwuExample}
\end{figure}

It is clear that the MWU test can only compare a pair of methods. In this study, there are several methods
used in a single experiment. Therefore, the MWU test was applied to each distinct pair of methods once.
The resulting number of wins, ties, and losses for each method were used to identify the best method or methods in each experiment.
Since $N$ methods are compared in a pairwise fashion, a method is compare against $N-1$ other methods.
Hence, the sum of the number of wins, ties, and losses for each method is equal to $N-1$.
In order to identify the best method or methods, this work explored using wins, ties, losses, and different 
combinations of these three numbers such as the difference between the number of wins and losses.

Since the goal is to find the best method or methods, the remaining methods can be discarded.
Therefore, an insightful metric is the number of losses. If this is non-zero, then there is a case for discarding that method.
However, in case of several methods having the same number of losses, the number of wins plays a role in making a decision.
As a results, if two or more methods have the same number of losses, the ones with more wins are considered better.
Using only the number of losses (and wins if necessary) might render the calculation of the number of ties redundant.
However, before the number of wins and losses can be found, a decision must be made about the acceptance or rejection of the
null hypothesis, which automatically results in calculating the number of ties.

In general, the MWU test described here can be used to compare any number of methods using any performance measure, such
as error estimates. It should be noted that, wins, ties, losses, or any combination of these numbers cannot necessarily be the suitable
identifier of superiority of a method over others in every study. As an example, if in a study the number of wins
was to be used as the way of identifying the best method, it might not be a suitable measure for other studies. This
is because if a method ties with the majority of other methods and does not lose to any, it can be considered a superior
method since it performs at least as well as any other method. Therefore, each study requires an in-depth understanding
of its performance measure and possible ways of interpreting the MWU test's results.

As another example, the confidence interval should be used with great care. Since the critical value for the
confidence interval of 99\% is greater than that of 95\% confidence interval, it is more likely that
the null hypothesis holds. Therefore, there are more ties possible and as a result, the number
of wins and losses will be reduced. Hence, if the number of losses or wins were to be used to
identify the best methods, such identification could become harder to achieve, resulting in a possible confusion in the comparison.
Thus, it is helpful to understand these details about the MWU test before applying it. The complete
source code of the MWU test along with instructions are available at \url{http://unbox.org/wisp/tags/mwu/1.0/lib/mwu.awk}.

\section{COSEEKMO}
\label{s:coseekmo}

COSEEKMO is a tool used in effort estimation experiments. Menzies et al. designed it initially
and discussed its several uses \cite{lum06,me06d,me06e,me06f,jalali07a}.
COSEEKMO's goal is to find the best group of methods for effort estimation on COCOMO-style data sets.
Currently, COSEEKMO uses COCOMO 81 data sets for experimentation. However, it can easily be extended to use 
COCOMO II data sets. Shepperd considers COSEEKMO's main limiting factor to be the required conformity of the collected data to the COCOMO model,
although he considers the motivation for COSEEKMO ``attractive'' \cite{shepperd07}.
At the time of developing COSEEKMO (and until now) COCOMO data sets were the only accessible and publicly available data sets for effort estimation experiments.
However, it is possible (and rather simple) to modify COSEEKMO to work with other models as well.

There are several different methods currently present in COSEEKMO. Some of these methods are simple while others
use complex algorithms for effort estimation. Usually, more complex methods are preferred since they are believed
to explore more possibilities and provide the best effort estimate in this case. However, as Menzies et al. suggest, 
``it is good practice to benchmark elaborate or resource intensive techniques against simpler alternatives \cite{me04h}.''
According to Cohen's argument \cite{cohen95}, it is possible that simpler methods can achieve similar results to 
sophisticated methods and hence the latter is superfluous in such cases. As an example, they mention Holte's
famous study where he compared classification rules and showed how simple ones usually performed well \cite{holte93}.
Similarly, as presented in Section \ref{s:results}, in every case, the more complex methods are superfluous and simpler
ones perform at least as well as any other method.

Since its introduction, COSEEKMO has been modified and improved constantly to explore a wider range of 
effort estimation methods. For example, it is possible that the combination of any number of effort 
estimation methods can provide better effort estimates. Therefore, COSEEKMO explores all such combinations.
Also, the evaluation methods of COSEEKMO have been modified to include non-parametric tests such as
the MWU test (introduced in Section \ref{s:mwu}).

Although the methods explored in COSEEKMO are integrated for increased performance, they can be used
individually as well. For example, NASA's Jet Propulsion Laboratory uses the dynamic Locomo method (discussed in Section \ref{s:locomo}),
which is currently a method integrated into COSEEKMO \cite{baker07}. This satisfies one of the main
goals of COSEEKMO, which is to find a group of best methods to be used in effort estimation practices. 
Also, new effort estimation and evaluation methods can be easily added to COSEEKMO for analysis and comparison.
Cocomin \cite{baker07} is an effort estimation method that was added to COSEEKMO in this work.
The MWU test is an example of evaluation methods added to COSEEKMO.
Such additions increased the stability of results in COSEEKMO, which can be seen in Section \ref{s:results}.

This section provides an overview of COSEEKMO's algorithm (Section \ref{s:coseekmoAlgorithm}), numeric estimation methods (Section \ref{s:coseekmoNum}), 
pre-processors (Sections \ref{s:coseekmoRow} and \ref{s:coseekmoColumn}), learners (Section \ref{s:coseekmoLearner}), and combinations of methods and experiments
(Section \ref{s:coseekmoCombination}).

\subsection{Algorithm}
\label{s:coseekmoAlgorithm}

The algorithm for COSEEKMO is presented in Figure \ref{figure:coseekmoAlgorithm}. 
In this algorithm, {\em Data} represents all 19 subsets of $COC81$ and $NASA93$ data sets.
{\em Runs} is a constant representing the number of runs for each data set. Previous studies used 30 runs \cite{me06d}.
However, in this work, 20 runs showed the same stability. Therefore, COSEEKMO uses 20 runs in this study.

\begin{figure}
{\begin{alltt}\sffamily
\textbf{FOR} datum \textbf{IN} Data \textbf{DO}
    \textbf{FOR} run \textbf{IN} Runs \textbf{DO}
        \textbf{FOR} train type \textbf{IN} \{superset,subset\} \textbf{DO}
            partition datum into train and test sets            # train set is created using train type
            \textbf{FOR} numeric estimation \textbf{IN} \{precise,proximal\} \textbf{DO}
                apply numeric estimation to train and test sets
                apply methods and their combinations to train and test sets
            \textbf{DONE}
        \textbf{DONE}
    \textbf{DONE}
\textbf{DONE}
run evaluation methods on the results
\end{alltt}}
\caption{COSEEKMO's algorithm.}
\label{figure:coseekmoAlgorithm}
\end{figure}

As discussed in Section \ref{s:experimentalMethod}, in each run and for each subset, 10 instance are chosen at random to create a test set.
Then, based on the {\em train type}, a train set is generated.
One train set is generated using all the instances in the subset except for the ones in the test set.
This method is called the {\em subset} train type.
The other train set is generated using all the instances in the superset except for the ones in the test set. 
This method is called the {\em superset} train type.
These train sets are used separately to train different models later.

Once the numeric estimation methods (discussed in Section \ref{s:coseekmoNum}) are applied to the train and test sets,
different methods or combinations of methods are applied to each train set and the trained models are used
to generate effort estimates. These methods are categorized into two groups of pre-processors (column pruners and row pruners) and
various learners, all discussed in the following sections. Finally, an evaluation method compares the effort estimates generated
from each method or combination of methods and reports the best methods. This study used the MWU test as described in Section \ref{s:mwu}.

\subsection{Numeric Estimation Methods}
\label{s:coseekmoNum}

COSEEKMO uses COCOMO data sets for its effort estimation experiments.
As described in Section \ref{b:cocomo}, there are several cost drivers in the COCOMO 81 model, represented in ordinal values in
a rating scale. Table \ref{table:costDrivers} provided the names of these cost drivers and Table \ref{table:preciseEffortMultipliers}
provided the numeric values of the effort multipliers matching their ordinal values in the rating scale. In this study,
the numeric estimation method that uses these effort multipliers is called the {\em precise} numeric estimation method.

These values were generated by Boehm, using his project experience \cite{boehm81}.
It is hard to regenerate these values for each new organization requiring effort estimation since
there is usually not enough relevant data available within most organization.
Therefore, another approach is to use a {\em proximal} numeric estimation of the values in Table \ref{table:preciseEffortMultipliers}, 
as suggested by Menzies et al. \cite{me06d}.
These proximal values are generated by mapping the precise values into two approximate straight lines.
One line has a negative slope and is used for ACAP, PCAP, AEXP, MODP, TOOL, VEXP, and LEXP cost drivers.
The other one has a positive slope and is used for DATA, TURN, VIRT, STOR, TIME, RELY, and CPLX cost drivers.
A third proximal set of values is used for the SCED cost driver, which has identical negative and positive slopes.
The proximal effort multiplier values are shown in Table \ref{table:proximalEffortMultipliers}.
Both precise and proximal values are used in COSEEKMO.

\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.2      & 1.1  & 1.00    & 0.9  & 0.8       &            \\
Upper     & PCAP        & 1.2      & 1.1  & 1.00    & 0.9  & 0.8       &            \\
(increase & AEXP        & 1.2      & 1.1  & 1.00    & 0.9  & 0.8       &            \\
these to  & MODP        & 1.2      & 1.1  & 1.00    & 0.9  & 0.8       &            \\
decrease  & TOOL        & 1.2      & 1.1  & 1.00    & 0.9  & 0.8       &            \\
effort)   & VEXP        & 1.2      & 1.1  & 1.00    & 0.9  &           &            \\
          & LEXP        & 1.2      & 1.1  & 1.00    & 0.9  &           &            \\
\hline
Middle    & SCED        & 1.2      & 1.1  & 1.00    & 1.1  & 1.2       &            \\
\hline
          & DATA        &          & 0.9  & 1.00    & 1.1  & 1.2       &            \\
Lower     & TURN        &          & 0.9  & 1.00    & 1.1  & 1.2       &            \\
(increase & VIRT        &          & 0.9  & 1.00    & 1.1  & 1.2       &            \\
these to  & STOR        &          &      & 1.00    & 1.1  & 1.2       & 1.3        \\
increase  & TIME        &          &      & 1.00    & 1.1  & 1.2       & 1.3        \\
effort)   & RELY        & 0.8      & 0.9  & 1.00    & 1.1  & 1.2       &            \\
          & CPLX        & 0.8      & 0.9  & 1.00    & 1.1  & 1.2       & 1.3        \\
\hline
\end{tabular}
\end{center}
\caption{The proximal COCOMO 81 effort multiplier values.}
\label{table:proximalEffortMultipliers}
\end{table}

\subsection{Column Pruning Pre-Processors}
\label{s:coseekmoColumn}

COSEEKMO uses several column pruning methods as pre-processors.
Column pruning is useful in removing columns (also known as features, attributes, or variables) of a data set that create noise, mostly in terms 
of deviations, in the model. In order to study the effects of column pruning, COSEEKMO compares several column pruners (including no column pruner) as
pre-processors. These column pruners differ mostly in the thoroughness of their search algorithms.

\subsubsection{Wrapper}
\label{s:coseekmoWrapper}

Wrapper \cite{kohavi97} is a standard best-first search through the space of possible features. 
At worst, the Wrapper must search the whole space, or all the subsets of features $F$ in a data set, which
is an exponential number $2^F$.
However, a simple best-first heuristic makes Wrapper practical for effort estimation.
At each step of the search, all the current subsets are scored by passing them to
a target learner. Two different target learners, LSR and M5p, are used in this study. 
These learners are further discussed in Section \ref{s:coseekmoLearner}.
Wrappers used in COSEEKMO use the forward search, meaning that they start with an empty subset of features and
add useful features. If an added feature does not help the subset containing that feature score better than a smaller
or different subset of the same size, that feature gets a negative point. Once a feature has a certain number of negative points,
it is removed from the subset of features reported by the Wrapper at the end of its algorithm. The Wrappers used in COSEEKMO remove a feature if it has
more than 5 negative points. The remaining features are reported by the Wrapper and are used to train and test a model later by COSEEKMO. 
When LSR or M5p are used as target learners, the data sets are usually logged and the results are unlogged.
Therefore, the Wrappers used in COSEEKMO with LSR and M5p as target learners also log the data. However, to study the effects of logging,
non-logged data sets are also used and compared with logged data sets.

\subsubsection{Local Wrapper}
\label{s:coseekmoLocalWrapper}

Local Wrapper, developed by Chen et al. \cite{me05c,me06d}, also uses a thorough search. However, it uses the local calibration 
method as its target learner. This further specializes Local Wrapper for effort estimation.

\subsubsection{Cocomin}
\label{s:coseekmoCocomin}

Cocomin, developed by Baker \cite{baker07}, is another column pruning method that uses a less thorough search algorithm.
Cocomin is a near-linear-time column pruner. Since it uses some heuristic criteria to select features, it does not explore
all the subsets and hence, Cocomin is a very fast column pruner that ``runs in $O(F.log(F))$ for the sort and $O(F)$ for
the exploration of the selected features \cite{baker07}.''

Baker describes Cocomin as follows:
\begin{quote}
Cocomin is defined by the following operators:
\begin{displaymath}
\{sorter, order, learner, scorer\}
\end{displaymath}
The algorithm runs in linear time over a {\em sorted} set of features, $F$.

Cocomin pre-sorts the features on some heuristic criteria. Some of these criteria, such as standard deviation or entropy, are gathered
without evaluation of the target learner. Others are gathered by evaluating the performance of the learner using only the feature in
question plus any required features, such as $KLOC$ for COCOMO, to calibrate the model. 

This search can be {\em order}ed in one of three ways:
\begin{itemize}
\item A ``backward elimination'' process starts with all features $F$ and throws some away, one at a time.
\item A ``forward selection'' process starts with one feature and adds in the rest, one at a time.
\item ``Both'' forward and backward searches are run separately and the best performing result is chosen. 
\end{itemize}

Regardless of the search order, at some point the current set of features $F' \subseteq F$ 
is passed to a {\em learner} to generate a performance {\em score} by applying 
the model learned on the current features to the train set. 
Cocomin returns the features associated with the highest score.

After the features are ordered, each feature is
considered for backward elimination, or forward selection if chosen, in a single linear pass through the feature space, $F$. The decision to
keep or discard the feature is based on an evaluation measure generated by calibrating and evaluating the model with the training data \cite{baker07}.
\end{quote}

There are three variations of Cocomin used in COSEEKMO as a column pruning pre-processor.
The first one
\begin{itemize}
\item sorted the features by the highest median MRE;
\item used a backward elimination search order;
\item learned using the local calibration method;
\item scored using mean MRE.
\end{itemize}

\noindent The second one
\begin{itemize}
\item sorted the features by their native order (simply meaning that it did not do any additional sorting);
\item used a backward elimination search order;
\item learned using the local calibration method;
\item scored using mean MRE.
\end{itemize}

\noindent Finally, the third one (which was an older version of Cocomin)
\begin{itemize}
\item sorted the features by their native order (simply meaning that it did not do any additional sorting);
\item ran both forward selection and backward elimination search orders to find the best;
\item learned using the local calibration method;
\item scored using mean MRE.
\end{itemize}

These variations only differ in the internal settings. These settings were decided through several experiments.
Some of the results of these experiments are available in Table 3.7 of \cite{baker07}.
The experiments performed using COSEEKMO over all such settings suggested the same results and hence, the
above three settings were selected.

Theoretically, a Wrapper (with target learners such as local calibration, LSR, and M5p) uses an exponential-time
search algorithm and is more thorough. Hence, it is believed to be more useful than a simpler method such as Cocomin.
However, as shown later in Section \ref{s:results}, Cocomin is superior to Wrapper pre-processors.

\subsection{Row Pruning Pre-Processors}
\label{s:coseekmoRow}

Row pruning methods are another group of pre-processors that are used in COSEEKMO.
After the addition of new column pruning methods discussed before, several row pruning methods were added to COSEEKMO
in order to remove instances or projects in the data sets that could create noise in the trained models.

There are two types of row pruning used in COSEEKMO. The {\em manual} method, called manual stratification, uses the information stored
in each instance and divides each data set into several subsets. This is discussed in Sections \ref{s:manualStratification}
and \ref{s:coseekmoAlgorithm} with details of the method and the subset and superset train types. However, a better comparison of pre-processors
compares this pre-processor, also called the subset train type, with another pre-processor, called the superset train type, for their similarities.

The {\em automatic} row pruning methods include the nearest neighbor method, described in Section \ref{s:nearestNeighbor},
and Locomo, described in Section \ref{s:locomo}. Both static Locomo and dynamic Locomo are used in COSEEKMO.
The nearest neighbor method has two variations. One of the variations uses the MRE in training the model and the other uses AR.
The static Locomo method uses different neighborhoods in the set $\{5, 10, 20, 40, 80\}$ as described before.
Dynamic Locomo has two variations. One variation uses the mean of MRE's in training the model and the other uses the median of MRE's.
Overall, Locomo is superior to the nearest neighbor method as shown in Section \ref{s:results}.

\subsection{Learners}
\label{s:coseekmoLearner}

Several learners are used in COSEEKMO. Learners are usually applied to the processed data after pre-processors are used.
Learners train and test on the data available in order to find the best performing method.
In COSEEKMO, some learners must be applied without a previously applied pre-processor. These learners, including Cocomin and Cocomost, are
actually pre-processors used as learners for simplicity. COSEEKMO allows for such learners.
On the other hand, other learners such as local calibration, LSR, and M5p can be applied with or without pre-processors applied to the data.
All the learners used in COSEEKMO are discussed below.

\subsubsection{Linear Regression}
\label{s:coseekmoLearnerLSR}

Linear regression assumes that the data can be approximated by one linear model that includes lines of code
($KLOC$) and other features $f \in F$ seen in a software development project:

\begin{displaymath}
effort = \beta_0 + \sum_i\beta_i\cdot f_i
\end{displaymath}

Linear regression adjusts $\beta_i$ to minimize the error.
Boehm argues that effort is exponential on $KLOC$ \cite{boehm81}:

\begin{displaymath}
effort = a \cdot KLOC^b \cdot \prod_i\beta_i
\end{displaymath}

where $a$ and $b$ are domain-specific constants. Such exponential functions can be learned via linear regression after they are
converted to the following linear form:

\begin{displaymath}
log(effort)=log(a)+b{\cdot}log(KLOC)+\sum_ilog(\beta_i)
\end{displaymath}

In general, it is useful to transform from a more complex space (in this case, the exponential model) to a simpler one
(in this case, the linear model) since it is easier to explain and work with the simpler space.
In this case, it is especially useful to find $a$ and $b$ values when dealing with a linear model rather than solving an exponential equation for $a$ and $b$.
The majority of the methods in COSEEKMO transform the data in this way. This approach is also suggested by Myrtveit et al. \cite{myrtveit05} in their
study involving linear regression.
It is necessary to unlog the estimates returned from each method after the trained model has been tested.

Weka \cite{Witten05} provides the functionality needed for linear regression. This is called LSR and COSEEKMO uses it through Weka.

\subsubsection{Model Trees}
\label{s:coseekmoLearnerM5p}

Model trees are a generalization of linear regression. Instead of fitting the data to one linear model,
model trees learn multiple linear models and a decision tree that decides which linear model to use.
Model trees are useful when the projects form regions and different models are appropriate for different regions.
COSEEKMO includes the M5p model tree learner defined by Quinlan \cite{quinlan92b}. Weka \cite{Witten05} provides the functionality needed for M5p.
As discussed in the case with LSR, M5p also logs the data in order to transform the space and therefore, the estimate must be unlogged.

\subsubsection{Local Calibration}
\label{s:coseekmoLearnerLocalCalibration}

Local calibration is a specialized form of linear regression developed by Boehm \cite[p526-529]{boehm81}.
Local calibration assumes that project effort is exponential on $KLOC$: 

\begin{displaymath}
effort = a \cdot KLOC^b \cdot \prod_i\beta_i
\end{displaymath}

Table \ref{table:preciseEffortMultipliers} shows the $\beta_i$ values recommended by Boehm 
(with the names on the left hand side defined in Table \ref{table:costDrivers}).
When $\beta_i$ values are used in the above equation, they yield estimates in months 
where one month is 152 hours (and includes development and management hours).
To operate, local calibration linearizes the exponential equation to generate 

\begin{displaymath}
log(effort)=log(a)+b{\cdot}log(KLOC)+\sum_ilog(\beta_i)
\end{displaymath}

Linear regression would try to adjust all the $\beta_i$ values.
This is not practical when training on a very small number of projects.
Hence, local calibration fixes the $\beta_i$ values while adjusting $a$ and $b$ values to minimize
the prediction error.

COSEEKMO uses local calibration on the training set to find $a$ and $b$ values and applies those to the test set to find
estimates. However, COSEEKMO also applies the three values for $a$ and $b$ as suggested by Boehm for embedded, organic, and
semidetached software modes. These values can be found in Table \ref{table:standardModes}.

\subsubsection{Cocomin}
\label{s:coseekmoLearnerCocomin}

Cocomin (described in Section \ref{s:coseekmoCocomin}) is a column pruning method with local calibration as its target learner.
Although COSEEKMO usually uses Cocomin as a pre-processor, Cocomin can also be used as a learner without any column or row pruning 
pre-processors applied to it. COSEEKMO uses three variations of Cocomin as explained in Section \ref{s:coseekmoCocomin}. 

\subsubsection{Cocomost}
\label{s:coseekmoLearnerCocomost}

Cocomost is another column pruning pre-processor with local calibration as its target learner. It was developed by Baker \cite{baker07} 
and is used as a learner in COSEEKMO without any column or row pruning pre-processors applied to it.
Cocomost evaluates all of the possible subsets of features. There are several evaluation methods used, similar to the evaluation methods in Cocomin.
As shown in Section \ref{s:results}, Cocomost performs similar to Cocomin although Cocomost explores more subsets.
A detailed analysis of Cocomost and Cocomin is available in \cite{baker07}.

\subsection{Combinations of Methods And Experiments}
\label{s:coseekmoCombination}

COSEEKMO can use every possible combination of pre-processors and learners as well as numeric estimation methods and train types to
create a combination of methods. Certain methods can also be used individually, such as Cocomin and Cocomost learners.
Each method, whether combined or single, is evaluated against every other method using the MWU test.
The results of such comparisons in the experiments using COSEEKMO are presented in Section \ref{s:results}.
The total number of methods can be found by calculating the possible combinations.
There are 8 column pruning pre-processors applied to 8 row pruning pre-processors and learners.
Therefore, there are a total of $8*8=64$ combinations of column pruning pre-processors, row pruning pre-processors, and learners.
All the 8 row pruning pre-processors and learners can be applied without a column pruning pre-processor.
In addition, 6 more learners are also applied without a column pruning pre-processor. Therefore, there are $8+6=14$ more combinations possible
that do not use any column pruning pre-processor.
Overall, $64+14=78$ combinations of pre-processors and learners are used in COSEEKMO.
Since there are 2 train types and 2 numeric estimation methods applied to each combination, a total of $2*2*78=312$ combinations are used
in COSEEKMO.

\section{Results And Discussions}
\label{s:results}

This section offers the results of the current study in detail. However, this study have been under careful review for a relatively long time since, 
as shown later, it shows stability in the results that is not reported elsewhere in the literature. Many runs of the previous versions of the experiments
were analyzed in detail before and showed the same conclusions as this study's results. The more interesting fact is that, as the experiments evolved and 
were expanded to include more methods, the conclusions did not change. For example, comparing to the most recent version of the experiments using COSEEKMO,
the train types were added, which doubled the number of combinations possible. Although this could have potentially changed the conclusions from the previous 
versions of the experiment, it had no effect on them. Overall, these results show a great amount of stability as the experiments evolved,
and as they are discussed in this section, they will provide a clear sense of how to arrive at the final conclusions.

The results of the experiments using COSEEKMO are extensive.
There are 19 subsets of data sets used in this study and 312 combinations of methods possible.
Therefore, reporting the results of these methods applied to all these subsets cannot be done using simple win-loss-tie tables obtained
from the MWU test. Also, understanding such tables is a very time-consuming task. In addition, these results are analyzed using
three different evaluation criteria (AR, MER, and MRE), adding to the amount of analysis required.
Hence, it is essential to categorize these findings through analyzing the results across different subsets and data sets, 
different evaluation criteria, and different runs. This will provide better perspectives about these biases and will offer a gradual path 
toward selecting the best effort estimation methods in COSEEKMO.

COSEEKMO was used with its 312 methods to generate the results in one representative run. Such a run is called a complete run.
The results of a random complete run is provided in Sections \ref{s:resultsTop10}, \ref{s:resultsTop20}, and \ref{s:resultsAll}.
Each section provides a different analysis of the results.
In order to simplify the results and focus on the more useful methods,
the training type was reduced to subset and half of all the combinations of these methods
($312 / 2 = 156$) were used. Also, the proximal numeric estimation method was removed from the results and only $156 / 2 = 78$ methods were reported.
Such a run is called a simple run. Simple runs take less time to complete and are relatively easier to analyze. 
The justification for simpler runs as well as the results of such a run are provided in Section \ref{s:resultsSimpler}. 
Finally, a detailed look at the best and worst performers are provided in Section \ref{s:resultsSimplerTop}, where an additional
4 runs of the experiment are reported for the 8 representative methods selected from the list of 78 methods.

\subsection{Top 10 Methods For Each Subset Across Three Evaluation Criteria}
\label{s:resultsTop10}

This is the most complete set of results since it explores the findings across different subsets and different evaluation criteria.
The top 10 methods for each subset is reported individually in Tables \ref{table:top10Subset1-AR} through \ref{table:top10Subset19-MRE}.
This contains the top 3\% of the methods that have the fewest number of losses (and the most number of wins in case of the same number of losses).
The justification for not showing more results is offered in Section \ref{s:resultsAll}.
These detailed tables help in identifying the methods suitable for each subset.
The reason for reporting these individual tables is that, one method may be more suitable for a subset while it might perform worse for other
subsets. However, such a method may be ignored when the results are reported in any other fashion.
It should be noted that the total number of losses (as well as wins and ties) possible is 311 for each method.

\clearpage

\input{tables/top10/top10-Subset1-AR}
\input{tables/top10/top10-Subset2-AR}
\input{tables/top10/top10-Subset3-AR}

\clearpage

\input{tables/top10/top10-Subset4-AR}
\input{tables/top10/top10-Subset5-AR}
\input{tables/top10/top10-Subset6-AR}

\clearpage

\input{tables/top10/top10-Subset7-AR}
\input{tables/top10/top10-Subset8-AR}
\input{tables/top10/top10-Subset9-AR}

\clearpage

\input{tables/top10/top10-Subset10-AR}
\input{tables/top10/top10-Subset11-AR}
\input{tables/top10/top10-Subset12-AR}

\clearpage

\input{tables/top10/top10-Subset13-AR}
\input{tables/top10/top10-Subset14-AR}
\input{tables/top10/top10-Subset15-AR}

\clearpage

\input{tables/top10/top10-Subset16-AR}
\input{tables/top10/top10-Subset17-AR}
\input{tables/top10/top10-Subset18-AR}

\clearpage

\input{tables/top10/top10-Subset19-AR}

\input{tables/top10/top10-Subset1-MER}
\input{tables/top10/top10-Subset2-MER}

\clearpage

\input{tables/top10/top10-Subset3-MER}
\input{tables/top10/top10-Subset4-MER}
\input{tables/top10/top10-Subset5-MER}

\clearpage

\input{tables/top10/top10-Subset6-MER}
\input{tables/top10/top10-Subset7-MER}
\input{tables/top10/top10-Subset8-MER}

\clearpage

\input{tables/top10/top10-Subset9-MER}
\input{tables/top10/top10-Subset10-MER}
\input{tables/top10/top10-Subset11-MER}

\clearpage

\input{tables/top10/top10-Subset12-MER}
\input{tables/top10/top10-Subset13-MER}
\input{tables/top10/top10-Subset14-MER}

\clearpage

\input{tables/top10/top10-Subset15-MER}
\input{tables/top10/top10-Subset16-MER}
\input{tables/top10/top10-Subset17-MER}

\clearpage

\input{tables/top10/top10-Subset18-MER}
\input{tables/top10/top10-Subset19-MER}

\input{tables/top10/top10-Subset1-MRE}

\clearpage

\input{tables/top10/top10-Subset2-MRE}
\input{tables/top10/top10-Subset3-MRE}
\input{tables/top10/top10-Subset4-MRE}

\clearpage

\input{tables/top10/top10-Subset5-MRE}
\input{tables/top10/top10-Subset6-MRE}
\input{tables/top10/top10-Subset7-MRE}

\clearpage

\input{tables/top10/top10-Subset8-MRE}
\input{tables/top10/top10-Subset9-MRE}
\input{tables/top10/top10-Subset10-MRE}

\clearpage

\input{tables/top10/top10-Subset11-MRE}
\input{tables/top10/top10-Subset12-MRE}
\input{tables/top10/top10-Subset13-MRE}

\clearpage

\input{tables/top10/top10-Subset14-MRE}
\input{tables/top10/top10-Subset15-MRE}
\input{tables/top10/top10-Subset16-MRE}

\clearpage

\input{tables/top10/top10-Subset17-MRE}
\input{tables/top10/top10-Subset18-MRE}
\input{tables/top10/top10-Subset19-MRE}

\clearpage

\subsubsection{All Subsets And One Evaluation Criterion}

Tables \ref{table:top10Subset1-AR} through \ref{table:top10Subset19-AR} show the results of running the MWU test using the 
AR evaluation criterion for each of the 19 subsets of $COC81$ and $NASA93$ data sets. The names of these data 
sets can be found from Table \ref{table:subsetNames}. 

As expected, the top 10 methods for each subset is different from other subsets.
There is no general trend as to which method performs better in each subset. For example,
both superset and subset train types are present in the results. Also, both precise and proximal numeric estimation methods are present in
the top 10 methods for these subsets. Moreover, column pruners, row pruners, and learners based on local calibration as well as other methods
are represented in the results.

Nonetheless, this was anticipated. A single method cannot possibly be useful for all subset and data sets. If so, such a method would have been
reported in the literature. However, no such method is known to exist at the time of writing the results of this study.
Therefore, this study is in agreement with other studies in this respect.
However, this work does not consider these results without any direction or decisive content. Although no single method is best, there are certain
points that can be made about the top methods for the subsets used in this study. Furthermore, clear points can be made about methods not in the
top reported list.

These findings for AR are as follows:
\begin{enumerate}
\item In 18 of 19 subsets, the top method either had a simple column pruning method (Cocomin) or required no column pruning method at all.
This is a key finding since it simplifies and speeds up the effort estimation process.
\item In all subsets, the top method either used no row pruning method or used one based on local calibration.
\item In addition, the nearest neighbor method was not used in the top 10 performing methods. This and the previous point
clearly state that row pruning without any domain knowledge, which is the nearest neighbor method in this case,
is actually less useful than not doing row pruning at all.
\item All the top methods in every subset used learners employing linear regression to learn a model. Local calibration and all methods based on that,
as well as LSR and M5p are such methods. Once again the nearest neighbor method that does not use any of these learners fails. 
This re-emphasizes the need for methods that have some domain knowledge about the data (where it is assumed by 
methods such as local calibration that project effort is exponential on $KLOC$).
\item In 12 of 19 subsets, local calibration and learners based on that, including its standard modes were the 
top method's learner. LSR was used in the other 5 subsets and M5p was only used in 2 subsets. This clearly states that 
in 17 of the 19 subsets, model trees were not selected as the preferred learner and simpler linear regression learners performed better.
\item In all subsets, when column pruning using LSR or M5p as target learners is present, it logs the data. The absence of methods that
do not log the data simplifies the search for the top performing methods in Section \ref{s:resultsSimplerTop}.
\item Although simple column pruners based on local calibration (such as Cocomin) are useful, the more thorough one (Local Wrapper)
is never used in the top method. Hence, sophisticated column pruners can be removed when looking for the top performing methods 
in Section \ref{s:resultsSimplerTop}.

\end{enumerate}

\subsubsection{All Subsets And All Evaluation Criteria}

The importance of these findings is that, they can be generalized to other evaluation criteria. The results of the MWU test
based on the MER evaluation criterion are presented in Tables \ref{table:top10Subset1-MER} through \ref{table:top10Subset19-MER}.
Similarly, the results based on the MRE evaluation criterion are presented in Tables \ref{table:top10Subset1-MRE} through \ref{table:top10Subset19-MRE}.
The goal is to identify any similarities or differences in the results across these evaluation criteria for each individual subset.

\begin{itemize}
\item Finding 1 holds for both MER and MRE. In MER results, the top methods of 18 of 19 subsets used a simple column pruning method (Cocomin) or required no
column pruning method at all. In MRE tables, 17 of the 19 subsets showed the same results, with 1 of the 2 other subset showing Cocomin very close
to the top method.
\item Finding 2 holds for all subsets evaluated using MER and MRE as well.
\item Finding 3 holds for all subsets evaluated using MER and MRE as well. In addition, these two findings demonstrate the importance of using
methods that have some domain knowledge about the data.
\item Finding 4 holds for all subsets evaluated using MER and MRE as well.
\item Finding 5 holds for MER and MRE as well. For MER, 15 of the subsets used local calibration and learners based on it and 3 used LSR. Only 1 used M5p, meaning
that 18 of the 19 subsets used simple linear regression learners. For MRE, 13 used local calibration and learners based on it, 5 used LSR, and only 1 used
M5p. Therefore, 18 of the 19 subsets used simpler linear regression learners again. It is even more interesting that in 15 of the 19
subsets, the top method's learner across all evaluation criteria was from the same type of learner (meaning that for all three criteria,
it was either based on local calibration, or was one of the LSR or M5p learners). This further shows the agreement between different evaluation criteria. 
\item Finding 6 holds for all subsets evaluated using MER and MRE as well except for subset 17 evaluated using MER. However, a simple local calibration
performs better in this subset. Therefore, the same point can be made about simplifying the search for top performing methods by removing methods 
that do not log the data.
\item Finding 7 holds for all subsets when using MER and MRE as well. Sophisticated and complex column pruning methods are not required in general.
\end{itemize}

The agreement in the findings among the three evaluation criteria and across all 19 subsets proves the fact that different
evaluation criteria show stable results (using the MWU test). This is an essential point in studying the effects of evaluation bias
in effort estimation studies and is further discussed in Chapter \ref{conclusions}.

\subsection{Top 20 Methods For Each Data Set Across Three Evaluation Criteria}
\label{s:resultsTop20}

Although the results for the subsets of each data set are useful in finding the most appropriate methods for each subset, it is also
useful to find the best methods applied to each data set based on the results for each individual subset of that data set.
This is done by summing the number of ties, wins, and losses individually for each method across all subsets of a data set.
In this section, the top 20 methods for each data set ($COC81$ and $NASA93$) are reported. This includes the top 6\% of the methods that have
the fewest number of total losses over all subsets of that data set (and most number of total wins in case of the same number of total losses).
The justification for not showing more results is offered in Section \ref{s:resultsAll}.

The goal of presenting the results in this way is to find methods that can perform best across most, if not all, subsets of a data set.
Similar to reporting the results in Section \ref{s:resultsTop10}, these results are also reported for two data sets, $COC81$ and $NASA93$, across
all three evaluation criteria, AR, MER, and MRE. Tables \ref{table:top20DatasetCOC81-AR} through \ref{table:top20DatasetNASA93-MRE} contain these
results. It should be noted that the total number of losses (as well as wins and ties) possible is $311*7=2177$ for $COC81$ and $311*12=3732$ for $NASA93$.

\clearpage

\input{tables/top20/top20-coc81-AR}
\input{tables/top20/top20-nasa93-AR}

\clearpage

\input{tables/top20/top20-coc81-MER}
\input{tables/top20/top20-nasa93-MER}

\clearpage

\input{tables/top20/top20-coc81-MRE}
\input{tables/top20/top20-nasa93-MRE}

\clearpage

Looking at the results for $COC81$ and $NASA93$ across all three evaluation criteria, these points can be made about the results in
of Tables \ref{table:top20DatasetCOC81-AR} through \ref{table:top20DatasetNASA93-MRE}:

\begin{enumerate}
\item The only methods present in all 6 tables are based on the local calibration method. In every case, the learner
is either the local calibration method or is based on local calibration, including the standard modes. This is an outstanding finding.
This simply means that none of the more sophisticated column pruning methods (such as Wrappers that use LSR or M5p target learners) 
and also learners such as LSR and M5p are as useful as methods based on local calibration in effort estimation.
\item Although methods based on local calibration are the only top performers in these results, they do not require to be sophisticated.
As an example, Local Wrapper, which uses a thorough search and the local calibration method, is not present in these results.
Hence, it is adequate to use simple pre-processors and learners based on local calibration.
\item In addition to the absence of sophisticated methods, methods such as nearest neighbor that do not use the domain knowledge about the data
are also absent from these results. Such methods represent the other end of the spectrum with their simplistic designs. 
\item In all the results, the top two methods use the subset train type and the precise numeric estimation method.
This can greatly simplify the search for the top performing methods in Section \ref{s:resultsSimplerTop} by removing methods that use the 
superset train type and the proximal numeric estimation method.
\item In every data set and for all the evaluation criteria, the methods using dynamic Locomo always ranked higher than the methods using static
Locomo. This shows that fixed neighborhoods cannot be as effective in row pruning as specific neighborhoods found for each data set. 
Therefore, although simpler methods are usually desired, row pruning requires a focused search of the instances to find the most appropriate neighborhood.
\item All the methods found in these results use linear regression (since they are all based on local calibration) and all log the data.
This clarifies the need for logging the data. 
\item Except in one case (Table \ref{table:top20DatasetNASA93-MRE}) one or both of the top two methods use one or more of a column pruner, a row pruner, 
or a learner such as Cocomin that prunes columns automatically in training the model. Even in that one case, the next methods (which are very
close to the top two) satisfy this finding. Therefore, pruning the data in effort estimation can be considered beneficial.
\end{enumerate}

Similar to the case with the subsets, these findings across different data sets and evaluation criteria also show stability in the results. The stability
seen across the data sets has a different nature from the stability seen across their subsets. This is not the weakness but rather is the strength
of these experiments in that, they show how changing the view of the results (for example from subsets to their data sets) 
can affect the results of the evaluation, and hence illustrate the evaluation bias present in the effort estimation literature.
This is further discussed in Chapter \ref{conclusions}.

\subsection{All Methods For Each Data Set}
\label{s:resultsAll}

There is another way of looking at the results of these experiments and that is by looking at the trend present in each data set across different
evaluation criteria. Therefore, instead of listing only the top 10 or 20 results, all methods are presented together in a graph. 
In order to do so, the number of losses across all subsets of a data set is summed up. This is done for each evaluation criteria.
The methods are then sorted based on their number of losses for AR and the same sort order is applied to MER and MRE results.
Hence, the same method is present at the same X-axis location. Figures \ref{figure:lossesAllCOC81-SortAR} and  \ref{figure:lossesAllNASA93-SortAR}
show these graphs.

\begin{figure}
\begin{center}
\includegraphics{figures/results/complete/losses-coc81-1}
\end{center}
\caption[All 312 methods applied to $COC81$.]{All 312 methods applied to $COC81$ and arranged using the sort order in AR.}
\label{figure:lossesAllCOC81-SortAR}
\end{figure}

\begin{figure}
\begin{center}
\includegraphics{figures/results/complete/losses-nasa93-2}
\end{center}
\caption[All 312 methods applied to $NASA93$.]{All 312 methods applied to $NASA93$ and arranged using the sort order in AR.}
\label{figure:lossesAllNASA93-SortAR}
\end{figure}

These results show a clear trend in the performance of methods regardless of the evaluation criteria used. Although there are spikes
present in these graphs, the general trend remains the same. It should be mentioned that, these spikes are usually small, except for
three large spikes in $NASA93$'s MER results. However, these spikes are irrelevant when considering the number of methods (312) and the
total number of losses possible, which is $311*7=2177$ for $COC81$ and $311*12=3732$ for $NASA93$.

Another important feature of these graphs can be seen in performance of the top performers (seen at the leftmost part of each graph).
These methods are the same and usually perform at least as well as any other method. This further illustrates the similar effects of
different evaluation criteria. Furthermore, it shows that the majority of the 312 methods are not needed. This clarifies the reason
for showing only a small group of top methods in Tables \ref{table:top10Subset1-AR} through \ref{table:top20DatasetNASA93-MRE} 
rather than showing all such methods.

\begin{figure}
\begin{center}
\includegraphics{figures/results/complete/losses-1}
\end{center}
\caption[All 312 methods applied to both $COC81$ and $NASA93$.]
{All 312 methods applied to both $COC81$ and $NASA93$ and arranged using the sort order in the top left graph.}
\label{figure:lossesAll-SortAR}
\end{figure}

As shown before, Figures \ref{figure:lossesAllCOC81-SortAR} and  \ref{figure:lossesAllNASA93-SortAR} show a general trend across different
evaluation criteria. Such a trend also exists when the same sort order is applied to the graphs of both data sets, $COC81$ and $NASA93$.
This can be seen in Figure \ref{figure:lossesAll-SortAR}. The three graphs on the left are the same as the graphs in Figure \ref{figure:lossesAllCOC81-SortAR}.
Therefore, they have the same spikes. However, there are more spikes, with some large ones, in the $NASA93$ graphs.
This was anticipated since as stated before, a method may not perform the same way across different data sets. Nonetheless, the trend seen
in either data set is similar across different evaluation criteria.

Once more, it is helpful to look at the top performing methods (seen at the leftmost part of each graph). Although they show more spikes,
they still perform at least as well as all other methods. Therefore, in order to study these methods, Section \ref{s:resultsSimpler} focuses
on a smaller group of methods, namely 78 of them. Section \ref{s:resultsSimplerTop} reduces the number of methods studied even further.

\subsection{Simpler Results}
\label{s:resultsSimpler}

Simplifying the results is helpful in many ways. Presenting too many methods makes it harder to compare the performance of these methods individually.
In addition, there is a great amount of difference in the performance of certain groups of methods, as described below, such as the ones that 
use the superset train type or the proximal numeric estimation method. Therefore, this section aims at removing such methods and as a result, focusing
on other aspects of the results of these experiments, such as finding the methods that perform worse than the others.

The results in Section \ref{s:resultsTop20} show that the train type can be simplified. In every case, the top performing method
used the subset train type, which performed at least as well as the superset train type in the top method (Table \ref{table:top20DatasetNASA93-MRE})
and otherwise much better than any method using the superset train type (Tables \ref{table:top20DatasetCOC81-AR} through \ref{table:top20DatasetNASA93-MER}).
(There might seem to be a case against removing the superset train type when looking at the tables in Section \ref{s:resultsTop10} since superset appears
repeatedly in the results. Also, the lack of space does not allow for showing more than 10 results in each table. 
Therefore, in tables with only the superset train type, it seems that the superset train type performs better. 
However, the fact is that all those results show similar (and mostly zero) number of losses. Therefore, when looking at all, rather than top 10, methods
the superset train type performs no better that the subset train type in 96.5\% of the tables and only slightly better in the remaining 3.5\% tables.
Hence, removing the superset train type can greatly simplify the results in these tables as well.
These results are available at \url{http://unbox.org/wisp/var/omid/extras/results/}.) 

Therefore, there is a case for simplifying the results and only looking at the subset train type in the results of the remaining experiments. 
In addition to reducing the search space of the methods by half, it also reduces the time of the experiment by more than half.
The reason is that, training on the superset takes at least as much time as, and usually more than, training on the subset (since the size
of the superset is at least as large as the subset). Therefore, the time required to train each model is reduced by more than half.

There is also a case for removing the proximal numeric estimation method from further consideration in the results.
As Tables \ref{table:top20DatasetCOC81-AR} through \ref{table:top20DatasetNASA93-MRE} show, the top performing method in each data set never used proximal.
This further proves the point that having some domain knowledge about the data (by using precise instead of proximal numeric estimation) helps the performance 
of methods. This was also seen in the case with the nearest neighbor method, which did not use the domain knowledge about the data, comparing to other 
methods such as local calibration.

These simplifications reduce the number of methods analyzed from 312 to a quarter of that, or 78. At this stage of reporting the results, there is no
benefit in removing individual methods (such as nearest neighbor). The reason is that removing individual methods will not reduce the number
of methods more than a few, which does not affect the runtime greatly. Also, the performance of such methods comparing to the top methods 
is worth analyzing since they are present in the literature. The next section takes a look at the best and worst performers of these 78 methods 
across different evaluation criteria, subsets, and an additional 4 runs. 

The results of this section are generated by removing all methods with superset train type or proximal numeric estimation method 
and running the MWU test on the remaining 78 methods. These results are provided in 
Tables \ref{table:top10bottom10DatasetCOC81-AR} through \ref{table:top10bottom10DatasetNASA93-MRE}. It should be noted that
the total number of losses (as well as wins and ties) possible is $77*7=539$ for $COC81$ and $77*12=924$ for $NASA93$.

\clearpage

\input{tables/top10bottom10/top10bottom10-coc81-AR}
\input{tables/top10bottom10/top10bottom10-nasa93-AR}

\clearpage

\input{tables/top10bottom10/top10bottom10-coc81-MER}
\input{tables/top10bottom10/top10bottom10-nasa93-MER}

\clearpage

\input{tables/top10bottom10/top10bottom10-coc81-MRE}
\input{tables/top10bottom10/top10bottom10-nasa93-MRE}

\clearpage

These findings can be stated from Tables \ref{table:top10bottom10DatasetCOC81-AR} through \ref{table:top10bottom10DatasetNASA93-MRE}.
For the top methods:

\begin{enumerate}
\item Dynamic Locomo (with mean MRE) is the row pruner of the top performing method for $COC81$ across all three evaluation criteria.
\item There is no column pruner used in the top performing method for $COC81$ across all three evaluation criteria. Nonetheless, column pruning
always appeared repeatedly in the top 10 methods.
\item Hence, the same method is ranked as the top performing method for $COC81$ across all three evaluation criteria. 
\item Unlike in $COC81$, in $NASA93$ and across all evaluation criteria, simple column pruning based on local calibration (such as Cocomin) 
was ranked in the top two methods, whether used as a pre-processor or a learner.
\item Also, unlike in $COC81$, in $NASA93$ and across all evaluation criteria, no row pruning was used in the top performing method. Nonetheless, 
row pruning always appeared repeatedly in the top 10 methods.
\item In both $COC81$ and $NASA93$, the top methods' learners were based on local calibration.
\item In both $COC81$ and $NASA93$, dynamic Locomo performs better than static Locomo, repeating the same finding as before. 
\end{enumerate}

According to these findings, row pruning using dynamic Locomo and using mean MRE as its internal evaluation method is selected for comparison in
Section \ref{s:resultsSimplerTop}. Also, column pruning based on Cocomin (with its newer variation and using median MRE to sort) is selected for this
comparison. This variation of Cocomin always performs at least as well as all other variations of Cocomin and all other column pruning methods
(when looking at the number of losses in these tables). Finally, local calibration is also selected as a learner for these comparisons.

For the bottom methods:

\begin{enumerate}
\item In both $COC81$ and $NASA93$ and across all evaluation criteria, the nearest neighbor method constantly performed worse than any other
row pruner.
\item Although Cocomin appears in both the top and bottom lists, it does so due to the presence of nearest neighbor. However, Local Wrapper
never appears in the top methods and is always present in the bottom methods. Therefore, as stated before, sophisticated column pruning cannot
necessarily improve the performance of methods.
\item Except for one method (in MER results for $NASA93$) all other bottom methods lack the use of a learner. (The exception actually
does not use a learner, but rather uses a standard mode of COCOMO and hence, it is not really an exception to this finding.)
When comparing the performance of the top and bottom methods in each table, it is clear that a learner with domain knowledge about the data (local calibration)
makes a big difference in the performance of these methods.
\end{enumerate}

According to these findings, the nearest neighbor method is selected as the worst performing row pruner for comparison in Section \ref{s:resultsSimplerTop}.
Also, Local Wrapper is selected as a thorough column pruner for these comparisons.

So far, both the best and worst performing methods have been analyzed. However, there are two other methods missing from this list. These
are Wrappers using LSR and M5p target learners. These methods did not appear in either top or bottom 10 methods. Therefore, there is a case
for including them in the comparisons in Section \ref{s:resultsSimplerTop}. These methods are believed to perform better than other column
pruning methods for their thorough search.

\subsection{Top Performers For Each Data Set}
\label{s:resultsSimplerTop}

This section provides the last set of results from all experiments using COSEEKMO. 
Thus far, all the previous sections focused on finding trends as well as best and worst performing methods across different evaluation criteria and
different subsets and data sets. This section focuses on another aspect of these experiments and that is the stability of results across
different runs of these experiments.

The results in this section are from a total of 5 runs of COSEEKMO. These are simple runs (defined before) 
with the last run being the simplified version of the run that all the previous results are derived from.
Each run uses a different random seed to generate the train and test sets.
Except for the last run, run 5, none of the other runs were presented before. There are two reasons for doing so. One is that, all these runs showed
very similar performances and hence, it was redundant to show them. The second reason is the amount of space needed for illustrating these results.
However, all these results are available at \url{http://unbox.org/wisp/var/omid/extras/results/}.

The graphs presented in this section will include the methods discussed and selected in Section \ref{s:resultsSimpler}.
These methods are provided in Table \ref{table:topPerformers}.

\begin{table}
\begin{center}
\begin{tabular}{|c|c|l|l|l|}
\hline
Method Number & Symbol             & Column Pruner & Row Pruner       & Learner           \\
\hline
1             & $\times$           & None          & None             & Local Calibration \\
2             & $\Diamond$         & None          & Dynamic Locomo   & Local Calibration \\
3             & $\Square$          & Cocomin       & None             & Local Calibration \\
4             & $\Circle$          & Cocomin       & Dynamic Locomo   & Local Calibration \\
5             & $\bigtriangleup$   & Local Wrapper & None             & Local Calibration \\
6             & $\bigtriangledown$ & LSR Wrapper   & None             & LSR               \\
7             & $\pentagon$        & M5p Wrapper   & None             & M5p               \\
8             & \ding{83}          & None          & Nearest Neighbor & None              \\
\hline
\end{tabular}
\end{center}
\caption{The chosen methods from every category of methods in COSEEKMO experiments.}
\label{table:topPerformers}
\end{table}

The graphs of the number of losses of the methods in Table \ref{table:topPerformers} are 
presented in Figures \ref{figure:lossesTop8-Run1} through \ref{figure:lossesTop8-Run5}.
These graphs show the results of five different runs across three different evaluation criteria and also across two data sets and their 19 subsets.
Each graph shows both $COC81$ and $NASA93$ data sets and each data sets' results are generated by finding the number of losses of each of its subsets for each
specific method and graphing it. Therefore, for each method, there are 7 points in each of the $COC81$ graphs and 12 points for each of the $NASA93$ graphs,
corresponding to the 7 and 12 subsets of each data set respectively. The lower the points are (fewer losses), the better the performance is for each method.

These graphs illustrate both the big picture and the small details of these results. The big picture is offered through categorizing 312 methods into 8 methods
showing methods with best, worst, and average performances. These methods are either developed in this study as well as Baker's study \cite{baker07}
or represent well-known methods in the effort estimation literature. Hence, these results can offer clear comparisons of effort estimation methods.
The small details help in drawing conclusions about the evaluation bias and the stability of effort estimation methods.
These details are categorized into three groups of different evaluation criteria, different data set and subsets, and different runs.

\begin{figure}
\begin{center}
\includegraphics{figures/results/simple/top8/losses-run1}
\end{center}
\caption{Performance of top 8 methods from Table \ref{table:topPerformers} for run 1.}
\label{figure:lossesTop8-Run1}
\end{figure}

\begin{figure}
\begin{center}
\includegraphics{figures/results/simple/top8/losses-run2}
\end{center}
\caption{Performance of top 8 methods from Table \ref{table:topPerformers} for run 2.}
\label{figure:lossesTop8-Run2}
\end{figure}

\begin{figure}
\begin{center}
\includegraphics{figures/results/simple/top8/losses-run3}
\end{center}
\caption{Performance of top 8 methods from Table \ref{table:topPerformers} for run 3.}
\label{figure:lossesTop8-Run3}
\end{figure}

\begin{figure}
\begin{center}
\includegraphics{figures/results/simple/top8/losses-run4}
\end{center}
\caption{Performance of top 8 methods from Table \ref{table:topPerformers} for run 4.}
\label{figure:lossesTop8-Run4}
\end{figure}

\begin{figure}
\begin{center}
\includegraphics{figures/results/simple/top8/losses-run5}
\end{center}
\caption{Performance of top 8 methods from Table \ref{table:topPerformers} for run 5.}
\label{figure:lossesTop8-Run5}
\end{figure}

There are several points that can be made about these methods:

\begin{enumerate}
\item At least one and usually all four methods ${1,2,3,4}$ perform better than all other 4 methods ${5,6,7,8}$.
The first four methods are based on local calibration and use zero or one simple column pruning and row pruning methods.
\item As shown in every graph, thorough column pruning based on local calibration (method $5$) is always inferior to simple column pruning based
on local calibration (method $3$).
\item Although no conclusions can be made on the relative performance of column pruning methods with Wrappers using local calibration, LSR, or M5p 
(methods ${5,6,7}$), all these methods always perform worse than simple column pruners based on local calibration (method $3$).
\item Method $8$, which never applies the domain knowledge, always perform worse than any other method. Methods $2$ and $8$ are both
row pruners that use a similar nearest neighbor algorithm. However, method $2$ uses local calibration while method $8$ does not use a learner.
\item When a row pruner (method $2$) performs well, adding a column pruner (method $3$) does not increase the performance of the resulting method ($4$).
This can be seen from the $COC81$ graphs.
\item Similarly, when a column pruner (method $3$) performs well, adding a row pruner (method $2$) does not increase the performance of 
the resulting method ($4$). This can be seen from the $NASA93$ graphs.
\item Hence, applying one of the two pre-processors (based on local calibration) suffices.
\item Local calibration (method $1$) as a learner and without any pre-processor usually performs well (and always perform better than methods not using
local calibration). However, its performance is always increased when a simple row pruner (method $2$) or a simple column pruner (method $3$)
is used as its pre-processor. 
\item Model trees (method $7$) usually perform similar (while they may perform slightly better or worse than) single linear regression, LSR (method $6$).
However, model trees always perform worse than other single linear regression methods (${1,2,3,4}$).
\end{enumerate}

Finally, there are several points that can be made about the stability of results across different evaluation criteria, data sets, and random runs.
All the above findings hold across all evaluation criteria, data sets, and runs, showing a great amount of stability in the observations
made when studying the biases in effort estimation. Nonetheless, as the observations become more fine-grained, biases show their nature more clearly:

\begin{enumerate}
\item $COC81$ responds better to row pruning (method $2$) while $NASA93$ responds better to column pruning (method $3$).
\item In $NASA93$, model trees (method $7$) always perform worse than any simple linear regression method (including method $6$). However,
in $COC81$, method $7$ performs similar and sometimes slightly better than method $6$, although it never performs better than other simple linear regression
methods.
\item Methods ${1,2,3,4}$ show better performances in general when evaluated using AR comparing to MER and MRE. This is also usually 
the case for methods ${5,6,7,8}$.
\item None of the runs have exactly the same performance for the any specific method across different data sets or evaluation criteria.
\end{enumerate}

The interesting point is that, no matter how fine-grained these observations are made (depending on the bias), the previous findings still hold independent of
the biases in the study.
