%\documentclass[10pt, conference, compsocconf]{IEEEtran}
\documentclass[journal,10pt,draftclsnofoot,onecolumn]{IEEEtran}
\usepackage[cmex10]{amsmath}
\usepackage{lineno}
\usepackage{algorithmic}
\usepackage{algorithm}
\usepackage{array}
\usepackage{cite}
\usepackage{color}
\usepackage{fancyvrb}
\usepackage{float}
\usepackage{graphicx}
\usepackage{multirow}
\usepackage{rotating}
\usepackage{stfloats}
\usepackage{subfigure}
\usepackage{times}
\usepackage{tricks}
\usepackage{url}
\usepackage{verbatim}
\usepackage[table]{xcolor}
\definecolor{lightergray}{gray}{.7}
\newcommand*\lgr{\color{lightergray}}
\newcommand{\W}{$W$}
\ifCLASSINFOpdf
  % \usepackage[pdftex]{graphicx}
  % declare the path(s) where your graphic files are
  % \graphicspath{{../pdf/}{../jpeg/}}
  % and their extensions so you won't have to specify these with
  % every instance of \includegraphics
  % \DeclareGraphicsExtensions{.pdf,.jpeg,.png}
\else
  % or other class option (dvipsone, dvipdf, if not using dvips). graphicx
  % will default to the driver specified in the system graphics.cfg if no
  % driver is specified.
  % \usepackage[dvips]{graphicx}
  % declare the path(s) where your graphic files are
  % \graphicspath{{../eps/}}
  % and their extensions so you won't have to specify these with
  % every instance of \includegraphics
  % \DeclareGraphicsExtensions{.eps}
\fi
\begin{document}
\title{{\LARGE {\bf What is ``Enough'' Quality for Data Repositories? }}}
\author{\IEEEauthorblockN{Tim Menzies, Adam Brady}
\IEEEauthorblockA{Lane Department of Computer Science and Electrical Engineering\\
West Virginia University,
Morgantown, West Virginia, USA,\\
tim@menzies.us, adam.m.brady@gmail.com}}
\maketitle
  \linenumbers
\begin{abstract}
~\\
\underline{BACKGROUND:} If project data is only approximately correct, this may
limit our ability to draw useful conclusions.
~\\\underline{AIM:} We seek the point at which it is still possible to  reason about software projects, despite inaccuracies in the data.
~\\\underline{METHOD:} Half a dozen real world data sets were selected from the PROMISE repository.
This data was analyzed by a   case-based planning algorithm called {\W}.
The planner seeks changes to a project that moves it from regions of (e.g.) large
effort estimates to other regions with lower effort estimates.
Details about that data was discarded {\em until} the conclusions found by {\W} started
to degrade.
Specifically, numerical data from the project was discretized into fewer and fewer bins.
~\\\underline{RESULTS:} In  all cases, it was possible to discard some details about the data without degrading
the reasoning. In some cases, it was possible to use very approximate versions of the data (e.g. all numerics divided
into just three bins). 
~\\\underline{CONCLUSIONS:}
It is possible to tune the degree of rigor of data collection to the planned use of that data.
For example, The degree to which we can simplify data collection, however, changes from data set to data set
(and even within one data set). Accordingly, this approach to reducing the cost of data collection must run in two phases.
Firstly, using small samples from the domain, this study should be repeated. Secondly, the conclusions from phase one
should be used to design a cost-effective data collection program.
\end{abstract}
\begin{IEEEkeywords}
data quality, planning, case-based reasoning
\end{IEEEkeywords}

\IEEEpeerreviewmaketitle



% For peer review papers, you can put extra information on the cover
% page as needed:
% \ifCLASSOPTIONpeerreview
% \begin{center} \bfseries EDICS Category: 3-BBND \end{center}
% \fi
%
% For peerreview papers, this IEEEtran command inserts a page break and
% creates the second title. It will be ignored for other modes.

\section{Introduction}
% no \IEEEPARstart
According to the old adage, ``garbage in, garbage out''; i.e.   reasoning about low
quality data will generate low quality results. 
Taken to an extreme, this adage could be used to motivate a needlessly elaborate and impractical
data quality collection program.
For example, data {\em could} be collected, accurate to seven decimal places,
by $N$ independent consultants, and then extensively audited prior to addition to a repository.
Such a collection procedure may be prohibitively expensive. 

The goal of this paper is to define a data quality
program that balances data collection $cost$ against the $benefits$ of having data at different levels of quality?
Recently, Brady~\cite{brady11b} has proposed an algorithm  for
determining if  data in a repository is of sufficient quality to
support business decision making.  The algorithm, called
$\Delta$-resiliency, works as follows: \bi \item Given some sample
data $data_0$, keep throwing  away details to generate $data_1$,
$data_2$ etc until something breaks; e.g.  our ability to make business decisions
start to degrade. \item The data set $data_{i-1}$ generated just
{\em before} the  breakdown at point $i$ has {\em enough} quality.
\item Design future data collection such that it collects data of quality $data_{i-1}$.
\ei 
For example, if it was  found that for effort estimation that lines of code needs only be accurate to the nearest ten KLOC, then we 
could avoid any expensive analysis method that collects data any more precisely than that.

More formally, we define $\Delta$-resiliency as follows:
\newtheorem{definition}{Definition}
\begin{quote}\begin{definition}
{\em A data set has ``enough'' quality if the data noise is $\Delta$
and the   inferences from that data set are not effected by noise up to the level of $\Delta$.
}
\end{definition}\end{quote}


Note that $\Delta$-resiliency requires some technique for
analyzing data (since the point $i$ at which this technique starts
to fail  is used to identify the point of $enough$ quality (at
$i-1$)).  That is, without knowledge of {\em how} the data is being
used, the above definition is not operational.  Hence, $\Delta$-resiliency
is defined for repositories that have reached level five maturity ~\cite{sen11}
(since, if a repository is below level five, then there are no
active optimizations being generated from the data).

$\Delta$-resiliency supports a cost/benefit analysis of data collection; specifically,  we need only collect data of $enough$ quality
since  more elaborate and expensive collection methods is superfluous.
The clear advantage of this approach  is that it expresses quality in terms business users
can understand; e.g. ``if you grant these funds, then we will be able to detect out-of-control projects sooner''.
This is useful since, as discussed below, other algorithms for data quality are more algorithmic and 
do not express their conclusions at the business-level (hence, it may be difficult to use those algorithms to lobby for
extra funding for data collection). 

This paper conducts an in-depth study of $\Delta$-resiliency on six real-world data sets. Since $\Delta$-resiliency
requires some operational definition of how data is used to make decisions, we
will assume an instance-based reasoning decision framework. Instance-based reasoning is a general method for reasoning
about (say) software engineering data~\cite{Auer2006,Walkerden1999,%
Kirsopp2003,Shepperd1997,Shepperd1996}
 and is known to work for the kinds of complex data sets collected
from real-world projects~\cite{Myrtveit}.
Further, as shown in this paper, 
instance-based
reasoning performs as well, or better, that other more complex approaches
(at least for the data sets used in this study). 
For this work, we use our {\W} instance-based reasoning algorithm~\cite{brady10a,brady10b,brady11a}.

Our results will be  mixed:
\be
\item
The good news is that it is possible to reduce the level of detail within data without compromising the analysis technique. This, in turn,
raises the possibility of extensive cost-savings in repositories (by avoiding needlessly over-elaborate data collection
policies);
\item
The other news is that the point at which data breaks down is not {\em data set} dependent by {\em instance}
dependent. That is, we cannot declare that for one data set that ``\underline{this} is enough quality''. Rather, we have to say
that ``for instances of a certain type within a data set, then \underline{this} is enough quality.
\ee
The first result should encourage more research for algorithms like $\Delta$-resiliency.
The second result tells us that data quality is not an issue that can be retired with a single paper. Rather,
it is very complex issue that will require extensive further research.

The rest of this paper is structures as follows. the {\em Background} section of the paper documents 
how real world data sets can be both {\em noisy} and {\em over-specified} (collected with excessive
detail). In {\em Algorithms for Data Quality}, the standard methods for improving data quality are
discussed (outlier removal, prototype selection, column selection). Our preferred approach based
on $\Delta$-resiliency will then be discussed which, in turn, will lead to a discussion of which
reasoning method will be used to implement $\Delta$-resiliency. It will be argued that our {\W} algorithm
is an effective choice. This will then be applied to six real-world data sets from the PROMISE repository.

\section{Background}

Recent research results highlight the value of  repositories of example problems. 
Such repositories are useful for 
(a)~storing the results of case-study based research;
(b)~for documenting existing baseline results; 
(c)~for one researcher to defend a claim that their new analysis method exceeds those baselines;
(d)~for other researchers to audit such claims.

Just as the machine learning community focused on the
UC Irvine machine learning repository\footnote{UCI: http://archive.ics.uci.edu/ml},
entire research communities
in software engineering 
have now formed around:
\bi
\item
Numerous open-source repositories such as Bugzilla\footnote{BUGZILLA: http://www.bugzilla.org/installation-list/};
\item
The Software Infrastructure Repository (SIR)\footnote{SIR: http://sir.unl.edu};
\item
The PROMISE
repository of reproducible SE results\footnote{PROMISE: http://promisedata.org/data};
\item
The ISBSG estimating benchmark suite\footnote{ISBSG: http://goo.gl/2AJCH}.
\ei
Numerous publications are now based on this data.
While the number of papers using ISBSG and Bugzilla data are not known, since the
PROMISE and SIR repositories came on line in 2006 and 2001, their
data
has been used in at least 90 and 200 publications, 
respectively\footnote{SIR publications: http://sir.unl.edu/portal/usage.html}.

Sen et al. document a parallel interest in commercial {\em data warehouses}. They report that
``data warehousing (DW) has experienced tremendous growth in the last decade ...  
it was cited as the highest-priority post-millennium project of more than half 
of IT executives''.~\cite{sen11}. They define a {\em data warehouse process maturity model}
in which, at level five, ensures that organizations can use their data to {\em optimize} their performance.

Given this increasing use of data repositories by researchers and industrial practitioners,
 it is important to certify the quality of that data.
Software engineering data can contain large amounts of {\em noise} (signals
not connected to the known target variables). Sen et al. note that managing poor data quality is a very expensive task
requiring ``subject matter 
experts, who are knowledgeable about business as well as data, are often employed to define data 
cleansing rules and data quality metrics''.

%We foresee that the next generation of IT specialists will include ``data quality engineers'' who are charged
%with the task of designing cost-effective data quality plans that take into account {\em both} the need for good quality
%{\em and} the limited resources available for that task.
%For those engineers, the question will be is there 
%some threshold
%after which a repository has ``enough'' quality (and, after that threshold, further expenditure on data quality
%has a decreasing return on investment).
%%While it was not their intention to so, Sen et al.'s research implies
%%a  strong criticism of current research into effort estimation.
%% 
%%From this perspective, much prior work is not fully
%%mature.  Consider, for example, our prior publications that explored
%%different ways to generate effort estimates on software
%%development~\cite{Menzies2006,chen05}.  Most of that work dealt
%%with issues on how to {\em predict} how long it takes to build
%%software. Such predictors are incomplete, from the perspective of
%%Sen et al., unless they can also comment on how to {\em change} and
%%{\em optimize} those estimates.
%To operationalize this definition, we must study the inferences that can be made
%from a data repository:
%\bi
%\item
%Sen et al. argue that the goal of a most-mature {\em level five} repository is to optimize some
%business goals.
%\item That is, for mature  level five repositories,
%we have ``enough'' quality when the performance of
%that optimization process is not compromised by noise in the data. 
%\ei
%Our proposed methodology for certifying data as sufficiently $\Delta$-resilient against noise is:
%\be
%\item Define an optimizing task;
%\item Implement that optimizer;
%\item For the data in the repository, determine the noise threshold after which the performance of that optimizer 
%is compromised;
%\item 
%A data set has ``enough'' quality if the known noise in the domain is less than that threshold.
%\ee
%As discussed below, other data quality operators (e.g row and column pruning of
%noisy data items)
%are more heuristic and  they do not readily translate into engineering
%goals. Hence, they are more tactical methods for coping with bad quality, after it has arrived. $\Delta$-resiliency, on the other
%hand, is a management-level strategic method for designing the goals of
%a data quality program that ensures ``enough'' quality.
%
\fig{defs} shows Yoon \& Bae's hierarchy of data quality issues for software engineering~\cite{yoon10}
 \definecolor{Mygrey}{gray}{0.75}
\begin{figure}[!t] \[\scriptsize \begin{array}{r} project\\ data
\end{array}
     \left<\begin{array}{l}
	      correct~~~
		    \left<\begin{array}{l}
			       normal\; data\\
			       rarely\;occuring\;data\\
			       incorrect\;values\;on\;correct\;data
			   \end{array}
		     \right.
	      \\~\\ incorrect
		    \left<\begin{array}{l}
			       incorrect\;values\;on\;poorly\;measured\;data\\
				incorrectly\;formatted\\ incomplete
			   \end{array}
		     \right.

	    \end{array}
     \right.
\] \caption{Data quality definitions (gray cells denote different
kinds of outliers).  Adapted from Yoon \&
Bae~\cite{yoon10}.}\label{fig:defs} \end{figure} 
The SE literature explores this hierarchal with different levels of rigor. For example,
much of the SE data mining literature discusses the problem of {\em missing data} (which Yoon \& Bae
would call ``incorrect values''):
\bi
\item
Aranda \&
Venolia~\cite{aranda09} audited bug reports at Microsoft by
interviewing developers related to the reports.  They found much
missing information in the bug reports.  
\item
This result was confirmed
by Bird et al.~\cite{bird09} who, in a found many missing links (up
to 50\%) between change logs and bug reports were not linked. 
\item
Yet
another study confirmed the Aranda \& Venolia \& Bird result.  Kim
et al.~\cite{kim11} found 32\% and 22\% unlinked bugs in open source
systems (Eclipse 3.1 and 3.4).
\item
Note that 
change that is not linked to a bug would result in an incorrect
value on the classification of that change.  
Bird et al. caution
that such incorrect values can degrade the performance of some
predictor built from noisy data~\cite{bird09}.
\ei
Another issue related to ``incorrectly formatted'' or ``incorrect values''
from \fig{defs} is that of {\em granularity}.
\input{figs/delta-ranges.tex}
How much detail is sufficient for including data in a warehouse? 
If data arrived rounded to the nearest integer,
should we reject it and ask for more details?

While there may not exist domain-general answers to this question, it is easy to show
that data is collected with very wide ranges of granularity:
\bi
\item
Take data from some public source (e.g.  the PROMISE repository) and  sort the  columns of numeric data
to form the list $C_{i,1}, C_{i,2}, C_{i,3},...$ for each attribute $i$.
\item
Next, find the differences between adjacent members in that list; i.e. $diff(i)_j=C_{i,j+1} - C_{i,j}$.
\item
Finally, sort those $diff(i)$ values and report their 25th, 50th and 75-th percentile.
\ei
The results on one such analysis from PROMISE data are shown in \fig{delta-ranges}.
Several aspects of this sample are worthy of comment: (1)~{\em wide ranges}, 
(2)~{\em flat attributes}, (3)~{\em occasionally,
surprisingly high precision}.

\subsubsection{Wide Ranges}
In \fig{delta-ranges}, there is 
enormous difference
in data collection precision for different data values. Some attributes
show {\em wide ranges} (i.e. have
have very large median differences):
\bi
\item
The $RAWFP$ attribute of $Kemerer$ has a median
difference of 124,  which is nearly as large as the entire inter-quartile for that attribute \mbox{(170-21 = 149)}.
\item
The $AdjFP$ attribute of $Kemerer$ has a median difference of 130 which is also nearly as large as that attribute's
inter-quartile range \mbox{(182-34.7 = 147.3)}.
\ei
Are such large median differences are too large or  too small? This paper argues that such questions are unanswerable
{\em unless} we know the intended use of that data. That is, in this research, we say that
data is of {\em enough}
quality if it supports the inference to which it is intended.

\subsubsection{Flat attributes}
Such a concept of {\em intent} lets us resolve other issues. Consider the
{\em ``flat''} attributes of \fig{delta-ranges}
(those where the 25-th percentile is the same as the 75-th percentile):
\bi
\item In $China$, the $DevType$ attribute is {\em ``flat''};
\item In $Kermer$, the $Hardware$ attribute is {\em ``flat''};
\item In $Finish$, the $at$ and $co$ attributes are {\em ``flat''};
\ei
(Note that the variance of such {\em ``flat''} attributes can be very small. Hence,
many machine learning algorithms would simply ignore them since they do not offer significant differences between classes.)

Are such {\em ``flat''} attributes of low quality? Is it worthwhile  to inject more domain knowledge into such attributes, discover
more distinctions, and make them unflat? Perhaps not- especially if the inferences made from this data do not require
such {\em ``flat''} data. As before, we are arguing that if the data supports the planned inferences, then 
the data is of sufficient quality.

\subsubsection{Occasionally, surprisingly high precision}
Finally, observe how some of the data in \fig{delta-ranges} is collected to a very exacting
degree of procession:
\bi
\item
 In the $China$ data set, the median difference between numeric column entries
for some of the specialized function points is very small; e.g. 
see the median difference of 0.1 for {\em PDR-AFP}.
\item
In the $Finnish$ data set, the median difference between numeric column entries is very small for the $insize$ measure
(median value of 0.05).
\ei
Should we always encourage such high degrees of precision? Perhaps not since infinite precision would be infinitely expensive.
Such exacting standards of precision are nonsensical for noisy data (since all they do is precisely measure some
random value).
We
 say that 
the numeric precision of the measurements are {\em over-elaborated} if, after some rounding, the inferences do not change
(and this statement is the basis of the $\Delta$-resiliency definition from the introduction).

\section{Algorithms for Data Quality}
\subsection{Standard Methods }

A standard method for data cleansing noise is to {\em prune} data items associated 
with noise~\cite{miller02,hall03}. 
Recent research in {\em defect prediction} focuses on two different kinds of {\em row pruning}:
\bi
\item {\em \underline{Outlier removal} that deletes a minority of rows}:
Kim et al.~\cite{kim11} use case-based reasoning to prune neighboring  rows containing too many contradictory conclusions.
Also
Yoon \& Bae~\cite{yoon10} use association rule learning methods to find
frequent item sets. In this framework, outliers are those rows with few frequent items. Their
methods prune  20\% to 30\%  of the rows.
\item
{\em \underline{Prototype selection} that deletes most rows}: 
Turhan et al.~\cite{me09b} pruned away all but 10 training examples per test instance using nearest neighbor methods. In doing so,
they dramatically reduced the false alarm rate of defect predictors being trained on data from other companies.
\ei
Recent research in {\em effort estimation} demonstrates the value pruning
{\em both} row and columns:
\bi
\item Chen et al.~\cite{chen05} found that removing up to 80\% of the columns 
 significantly improved PRED(30)\footnote{The percentage of estimated within 25\% of actuals.} values from (approx) 20 to 60 \%.
The effect was particularly marked in smaller data sets (those with less than 30 rows).
\item
Kocaganeuli et al. ~\cite{me10c} showed that when building an effort estimator for local data,
then importing effort data from other organizations severely damages predictor performance.
However, this
damaging effect is removed if, prior to learner a predictor,
they
they pruned away neighboring rows with high variance in their effort values. 
\ei
(As an aside, we note that while the techniques of Kocaganeuli et al. were evolved separately to Kim et al,
they
are clearly analogous techniques.
For another example of analogous research, see our work with Guo et al. where we  
explored a similar association-rule approach to detect anomalies in flight guidance systems~\cite{me02n}.)

While row and column pruning can sometimes patch poor data quality,
they are only heuristic methods that may not work on particular data sets.
For example, for many years, we have tried column and row pruning to reduce the noise in this manner.
The results have been disappointing.
Jalali et al. report that
row pruning reduce variance in our predictions~\cite{jalali07}.
As to column pruning, while
it reduces
the median performance variance somewhat (in our experiments, from
150\% to 53\%~\cite{me06d}), the residual error rates are still unacceptably  large.

In summary,
standard methods such as row and column pruning are not sufficient to repair low-quality data.
\subsection{$\Delta$-Resiliency}

Row and column pruning are data cleansing methods for patching low quality data {\em after}
it arrives in a repository.
In terms of setting corporate policy on
data quality, the preferred alternative 
is
 a {\em data collection quality standard}. Such a standard can be used by
data providers to certify that their data has ``enough'' quality {\em before} it is
added to a repository.

Recall from the above that if a repository reaches level five maturity,
then it is used for
some
business
optimization task.
$\Delta$-resiliency certifies that, up until some noise threshold $\Delta$,
that the functioning of that optimizer is {\em not} effected by uncertainty in
values.  Once that  value is determined, then the task
of data providers is to demonstrate that the noise resulting from their data collection methods is {\em less than} $\Delta$.

Consider a model that accepts $N$ inputs $N_1...N_n$. Let the known values for $N_i$ be the range $V_1,...V_v$:
\bi
\item
Since we seek a measure of noise across all $N_i$, we study the $rank$ of the values $V_i$ using the normal ranking rules\footnote{
$X$ numbers will be ranked $1..n$. Runs of consecutive equal numbers are ranked via their average position. That is,
the following $n=6$ numbers $(1,2,2,3,4,5)$ are ranked $1,2.5,2.5,4,5,6)$. For more details, see http://goo.gl/FY4Na.}
\item
Noise can change the value of that input $N_i$ by some rank $r$. Given $v$ values for $N_i$, then we
can express that rank 
as the
$\delta_i$ percentage  $\frac{100*r}{v}$. 
\item
Let $\Delta$ be the maximum $\delta_i$ for all optimizer inputs.
\ei
Then:
\begin{quote}
\begin{definition}
{\em 
The outputs of a $\Delta$-resilient optimizer are not degraded when
the majority of ranks in the optimizer inputs are changed by up to $\Delta$\%.}
\end{definition}
\end{quote}
One way to find $\Delta$ is via $descritization$ studies.
{\em Equal frequency discretization} maps numerics  $N_i$ into $B$ bins (labeled $1,2,...,B$), each of which
 contain equal
number of values~\cite{gama06}.
If an optimizer's  inner processing requires precise numeric values, then we replace all values $V_i$ in one bin
with the median of all the values in that bin.

To compute $\Delta$-resiliency, 
we divide the model inputs into $B$ bins, then execute the model.
Next, we seek the smallest value $B'$ such that:
\be
\item
Optimization results from inputs divided into 
$B'-1$ bins are no {\em worse} than $B'$;
\item
Optimization results from inputs divided into 
$B'+1$ bins are no {\em better} than $B'$.
\ee
$B'$ offers a lower-bound on the level of detail required for the optimizer. It is superfluous to
collect data at any level of detail greater than $B'$ since that extra level of detail does not
improve the optimizers.

Also, $B'$ offers an upper bound of the resilience of the optimizer to noise.
If we divide ranked values $V_1,V_2,..V_v$ into $B$ equal frequency bins, then each bin will have cardinality $\frac{v}{B}$.
For the majority of  entries in any bin, 
any uncertainty  in rank (due to noise) less than $V/B/4$ will not change the bin
of those values (see \fig{binwidth}).
Hence, once $B'$ is known,  we say that the optimizer is resilient to rank changes dues to noise
up to $\Delta=100/B'/4$\%.



\begin{figure}
\begin{center}
\includegraphics[width=2.5in]{delta.png}
\end{center}
\caption{Ranked values divided into $B$ equal frequency bins. For the majority of the ranking 
(e.g. those between 1.25 and 1.75),
any rank change due to noise less than a rank of 0.25 will {\em not} change the bin of those values.}
\label{fig:binwidth}
\end{figure}
\section{Building Optimizers From SE Data}
This definition of $\Delta$-resiliency
is based around an optimizer that studies
data in a repository to find ways to improve a business.
Hence,
as a pre-condition for operationalizing $\Delta$-resiliency,
we need a working optimizer.

This section discusses a range of  optimizers that might be used, from which it selects the {\W}
instance-based planner. {\W} takes a current project description and, using historical examples,
proposes changes to that project in order to achieve some goal (e.g. decreased development effort).
This discussion is somewhat technical and may be skipped
during a first read of this paper. 

\subsection{Gradient Descent Optimizers}
Using ``what-if'' queries, it is possible to use software process  models 
to find the fewest changes to a project that most reduce development effort~\cite{boehm81}.
Such optimization tasks are traditionally implemented by
computing
partial differential equations of a model, and then exploring the surface of steepest change.

A premise of this gradient descent
approach is {\em tuning stability}; i.e. that the gradients at any point in the model can be determined
with certainty.
Baker~\cite{baker07} tested tuning stability in the NASA93 data set
(93 NASA projects using the COCOMO ontology, see http://promisedata.org/?p=35).
He tuned the COCOMO $(a,b)$ parameters that control for linear and exponential effects (respectively)
using 
from 100 samples of 90\% of NASA93.
The observed  tunings on $(a,b)$ covered a very large range:
\begin{equation}\small
\left( 2.2 \le a \le 9.18 \right) \wedge \left(0.88 \le b \le 1.09\right)
\end{equation} 

Gradient descent algorithms are confused by  such large amounts of noise.
Suppose some proposed technology  doubles productivity, but $a$ moves from 9 to 4.5.
The improvement resulting from that change would be obscured by tuning instability.

\subsection{AI Optimizers}
The previous section argued that
traditional gradient descent
optimizers executing over simple linear models may be ineffective
(due to the noise in SE data).
When traditional methods fail, AI search algorithms can sometimes
be effective.
In this approach, we perturb the internal tunings of a model in accordance with known
variations (e.g.
the known ranges of the internal COCOMO parameters seen in 30 years of COCOMO research).
The AI algorithms can then sample the space of possible behaviors,
looking for stable conclusions within a large space of possibilities.
For example, given a space of {\em possible} changes to a project,
we have used AI search algorithms to find
the {\em smallest} set of  changes that {\em most improves} model
output. For example,
\bi
\item
In~\cite{me07g,me07f}, we built optimizers using
simulated annealing (SA) and COCOMO effort/time/defect 
models.
\item
In~\cite{orrego09,me09a,me09e,me09f,me09i,me10f}, we showed that
SA is out-performed by other
AI algorithms. We also found that,
for the purposes of COCOMO-based optimization,
our own
algorithms called SEESAW 
out-performed
the usual AI algorithms (beam search, A-star, etc)~\cite{me09i}.
\ei
The output of these AI search algorithms is an ordered set of
recommendations. It then takes linear time to explore the  first $1 \le x \le all$ of these recommendations to
find the smallest number of recommendations that most improve a project.
For example, in \fig{run},
the y-axis shows one case study using the predictions generated by
the COCOMO effort/time estimator and the COQUALMO defect estimator\footnote{
These y-values are
the median predictions seen in 100 simulations, where we picked
inputs stochastically from the range of known project options.}
The x-axis of that figure shows the effect of  set of changes proposed to the project. For
example:
\bi
\item
 At $x=0$, we see the predictions from the original project.
\item
At $x=1,2,..$ etc, we see the results of applying the top ranked, then
the second ranked (etc) recommendation generated by the SEESAW optimizer.
\item
After some point ($x=13$), the changes no longer become statistically 
significantly different. After that point, we prune all remaining recommendations.
\ei
\begin{figure}[!t]
\footnotesize
\begin{center}
\includegraphics[width=2.5in]{single-seesaw-tpts100-all-trio-2-1.pdf}

\begin{tabular}{|p{.35\linewidth}|p{.35\linewidth}|}
\multicolumn{2}{l}{SEESAW's ranked for 1 to 13.}\\\hline
round0: $r_x = \emptyset$\newline
round1 added \{pmat=3\}\newline
round2: added  \{resl=4\} \newline
round3: added   \{team=5\}\newline
round4: added \{aexp=4\} \newline
round5: added  \{docu=3\}\newline
round6: added  \{plex=4\}
&
round7: added \{rely=3\} \newline
round8: added  \{stor = 3\}\newline 
round9: added \{time = 3\}\newline
round10: added  \{tool = 4\}\newline
round11: added \{sced = 2\}\newline
round12: added \{site = 4\}\newline
round13: added  \{acap = 5\}
\\\hline
\end{tabular}
\end{center}
\caption{Effects of SEESAW optimization. As the $x$ value increases,
more and more of SEESAW's recommendations are applied. After some point
$x=13$, future changes to the recommendations result in statistically
insignificant changes. From~\cite{me09i}.}
\label{fig:run}
\end{figure}
Observe how  the optimization recommendations of SEESAW:
\bi
\item
Dramatically reduces
development time (from over 300 calendar months to less than 100);
\item
Halves the effort prediction (from   
over 150 months of effort to under 75 months);
\item
Offers modest reductions in the number of delivered defects (from 150 to 110).
\ei
\subsection{Instance-Based Optimizers}
While a successful prototype, SEESAW has certain limitations.
In our view, these  limitations will be found in 
any model-based optimizer applied to SE data:
\bi
\item
{\em Data restrictions:} SEESAW is a wrapper around COCOMO models. Hence,
it can only accept projects described in the ontology of that model- a limitation that
Shepperd views as a significant drawback in the COCOMO family of models~\cite{shepperd07}.
\item
{\em Cost:} SEESAW's optimizations are only as good as the underlying model. Building, tuning, and maintaining
convincing software process models is a time consuming tasks. For example,
Raffo spent two years building and tuning
a software process model of the development processes of a North American software company~\cite{raffo95}.
\item
{\em Over-fitting:}
SEESAW samples increasingly narrow segments of the state space of a model (``ﬂying in'', as 
it were, into small cracks between the training data).
If the test data does not fall into those tiny region, then the 
recommendations will fail. For example,
when SEESAW's recommendations
are tested on project data {\em not} used to train the model, then those recommendations fail to (e.g.) 
decrease development effort in over half those experiments~\cite{brady11a}.
\ei
When model-based methods fail, the alternative are instance-based methods
that store training data in an n-dimensional space.
Inferences are then drawn from the neighbors of test instances in the training space.

Instance-based methods use no model, hence they do not demand that the data comes in a particular form.
Hence, they do not suffer from {\em data restrictions}. As
to the {\em cost} issue, they are cheaper to develop and maintain
since, in instance-based reasoning, there is no difference in  those two activities (when new data arrives,
it is added to the training space, thus updating the instance-based reasoner). 
Finally, regarding {\em over-fitting}, since there is no model, there no model to over fit.

%One drawback with
%simple instance-based learning algorithms are very susceptible to noise.
%However, with a little statistical bookkeeping, 
%they perform well in the presence of noise- this has been seen in the IB3
%algorithm~\cite{Aha1991} as well as with our own
%{\W} instance-based planner~\cite{brady10a,brady10b,brady11a}.
%For example, with {\W},
%we can find recommendations that 
%decrease effort in over 90\% of our case studies~\cite{brady11a}. 
%Note that this result was on test data {\em not} used to find the recommendations.
%Significantly,
%those case studies include the noisy data set of \fig{coc}.
%Also, when compared to the model-based results reported above, {\W} fails far fewer
%times on test data than SEESAW.
%
%
%In summary, our most promising optimizer for SE data is the {\W} instance-based planner.
%{\W} can accept data in many formats and has minimal development and maintenance cost.
%Also, 
%{\W}
%can handle noisy data while avoiding the
%{\em over-fitting} problem seen with SEESAW's model-based reasoning.
%
%The next section of this paper offers a tutorial example on {\W}.
%The most important feature of that description is that {\W} works on discretized
%data. That is, if we run {\W} with different levels of discretization,
%it is a natural tool for computing the $\Delta$-resilience of a repository.
%
%

%Therefore
%Worse, such tuned  models may not port to other domains without even further expensive customizations and tuning.
%
%
%  
%\subsection{The Problem with Numbers}
%
%\bi
%\item incomplete historical record;
%\item inaccuracies during data collection;
%\item translation of data bases from one form to another (e.g. function points to LOC);
%noisy: spurious signals unrelated to the target; 
%\item
%uninformative: contain mostly one value, or no 
%\item
%repeating or correlated values; 
% correlated to other variables: so, if pruned, their signal 
%will remain in other variables. 
%\ei
%\subsection{Noise in SE Data}
%
%As documented in 
%an ICSE'11 paper, managing noise in SE data is an open and urgent issue in SE data.
%\input{zhang}
%
%\subsection{Effort Estimation}
%
%\subsection{Parametric Modeling}
%
%\subsection{Fuzzy Logic}
%
%\section{Qualitative Reasoning}
%
%\subsection{Qualitative Approximations}
%
%\subsection{Qualitative Methods}
%We take care to distinguish our use of the term {\em qualitative} from
%its standard use in the software engineering literature. Carolyn Seimans (personnel
%communication) offered the following notes on how our approach differs
%from {\em qualitative methods} (a large an active area of SE research).
%
%
%Thanks for your interest in the special issue, and for sharing this idea with us. I like the idea a lot, and it addresses a discomfort I've had as well for a long time with estimation and other model-building efforts. Of course, for me, it's related to my discomfort with all things quantitative and the fascination with digits to the right of the decimal point. I think there would be great merit in relaxing the requirements for precision where it's not really needed and allowing things that are intrinsically fuzzy to be fuzzy.
%
%But here's the rub. I don't think what you're talking about is actually "qualitative". It's certainly more coarse-grained, possibly more subjective, and probably somewhat uncomfortable for hard-core engineering types, but it's still quantitative. A qualitative description of an effort estimation would be a paragraph or so of text describing all the different aspects of the effort that will go into the project, the different ways one could try to predict the level of effort, what types of effort will be required, differences in opinions about the level of effort, etc. But a depiction in terms of "upper" and "lower" is still a discrete, numeric scale, i.e. still quantitative. For example, you could still do some (simple) statistical tests on it; you could at least count it (e.g. number of "upper" vs. number of "lower" projects; how many people think a project is "upper" vs. "lower", etc.). If the description were truly qualitative you wouldn't be able to do that. The definition of "qualitative" that I'm using here is "expressed in text or images, not numbers or discrete categories". I'm not familiar with the references you give to qualitative reasoning, so I'm open to education on other definitions.
%
%Again, this isn't to say it isn't a good idea. I think it's an excellent idea. I just don't think it would fit into this special issue. But please publish it somewhere!
%
%Just to add to Carolyn's comments. An important part of your study of the alternative approach to estimation would be that your research method has a strong qualitative component. That is, your estimation process is one thing - coarse grained quantitative or qualitative - while your empirical study of that method is another thing - which for this special issue should primarily be a qualitative approach.
%




\subsection{Improving Software Projects with {\W}}

%Before we can offer evidence of $\Delta$-resilience in our work with {\W}, we present the following case study demonstrating the {\W} algorithm. As an instance-based planner, {\W} operates entirely on historical cases, making no assumptions of underlying distributions or domain-specific models. Summarized, {\W} suggests changes that occur more frequently in desirable cases and less often in undesirable cases.

{\W} is an instance-based planning system that seeks changes that improve a project according
to some measure (e.g. decreased development time).
{\W} requires a set of historical cases as well as a defined $context$ of controllable feature ranges within those cases. Historical cases are expressed via a set of $P$ project descriptors such as analyst capability, function points, schedule constraints, etc. Each of these cases must also be labeled with some known goal metric, such as development effort in man-months. The $context$ consists of a subset of the project descriptors that describe the project at hand, as well as which descriptors are controllable. {\W} uses the entire $context$ to determine the relevant neighborhood, then restricts recommendations to the controllable descriptors only.

For example, a company may track prior software projects via the COCOMO descriptors for analyst capability (acap), schedule requirements (sced), lines of code (KLOC), and so on. When planning with {\W}, the project manager could define a new project using all available descriptors. However, business decisions (such as a hiring freeze on analysts) would constrain the controllable descriptors to only those deemed implementable. From these controllables, {\W} can begin reasoning.


{\W} assumes that a manager can offer us (a) a description of the  $context\subseteq P$ that interests them and (b) a list of $control$able options which they can change ($control \subseteq context$). For example, consider the following context for a Finnish banking software project. For simplicity's sake, each descriptor is rated either high, medium, or low:
\[\small
\begin{array}{r@{~}c@{~}l}
\multicolumn{3}{l}{context_1 =}\\ 
\mbox{~~~~~~}&  & ?hw \in \left\{lo, md \right\}\wedge 
 ?at\in \left\{md, hi\right\} \wedge
     ?FP\in \left\{lo, md \right\} \wedge \\
& & ?co\in \left\{lo, md\right\} \wedge
    ?prod\in \left\{md, hi \right\} \wedge
 size\in \left\{md, hi\right\}\wedge\\
\end{array}
\]
Here,  ``?'' are the $control$ labels; the manager is only concerned with projects that have a low or average number of function points (FP).

{\W} finds a project treatment $R_x$ by studying the project similar to the context in the case repository. Formally, {\W}2 explores the $neighorhood$ of the $context$, looking for ways to select for the ``best'' cases using some utility measure. In this case, minimizing software effort requirements.
In {\W}, this is a six step procedure:
\be
\item Divide cases randomly into $train:test$ in the ratio $N_1:N_2$.
\item Use $context$ to find $K$ nearest-neighbors within $train$.
\item Using the utility measure, the neighborhood into (a)~the $best$ cases that should be emulated, and (b) the remaining cases to avoid (which we call $rest$).
\item Rank all differences between  (a) and (b) according to how strongly they select for the $best$ cases.
\item Use the $train$ set again, experiment with treatments $R_x$ built from the  top ranked items found in $Step4$.
Return the treatment that  selects for the cases in the $train$ set with highest median $value$.
\item Test the treatment from $Step6$ using relevant cases from the $test$ set; i.e. find all rows in the neighborhood of the $context$ in $test$ set; then find the subset of those rows that match  the treatment.
\ee
The current implementation of $W$ using $N_1=2$, $N_1=1$, $K=20$.
%\section{Data}
%\input{data}
%As stated prior, {\W} operates on the controllable space of project ranges from historical cases. Because {\W} operates on discrete, actionable changes to software projects, continuous features must be discretized. This requirement initially lead us to the concept of $\Delta$-resiliency. Our initial concern was that upon discretization, performance would drop as data was inserted into coarse bins.
%
%The precision expressed in these datasets demonstrates our motivations in discussing $\Delta$-resiliency. For example, the Finnish dataset represents a the $prod$ feature as a floating-point number accurate to \emph{six} decimal places. If equivalent effort reduction could be achieved without such precision, then a business need not expend resources in obtaining that precision.
%
% \fig{data} describes the number of features (Cols) and instances (Rows) for each dataset. All of these datasets are freely available from the PROMISE repository (\footnote{PROMISE: http://promisedata.org/data}). Also, while the datasets used in this paper describe projects scored by development effort, there is no formal requirement that {\W} be presented with effort data. We offer a case study only in effort reduction to better allow comparison between results.
%
The following case study demonstrates one run of {\W} using the $Finnish$\footnote{PROMISE: http://promisedata.org/data} dataset. After setting aside $2/3$rds of the data for training in $Step1$, \fig{train-filter} shows the most neighborhood generated in $Step2$. Each instance is ranked by how many features fall within $context$, labeled as ``overlap'' in \fig{train-filter}. Cells in gray represent ranges that fall outside $context$. The top 20 rows with the highest overlap are selected.

\input{figs/train-filter.tex}

Next, $Step3$ sorts the cases by utility, with $K_1=5$ rows placed into the $best$ set and the remaining $K_2=15$ rows placed into the $rest$ set (\fig{train-contrast}). The \emph{contrast set} between these two sets is shown in \fig{train-bestrest}. Frequency counts are computed for each discrete feature value, with each potential treatment $R_x$ ranked as follows:
\begin{equation}\label{eq:ps}\small
rank(E) * support(E) = \frac{ratio(E|best)^2}{ratio(E|best) + ratio(E|rest)}
\end{equation}

\input{figs/train-contrast.tex}
\input{figs/train-bestrest.tex}
\input{figs/test-constrain.tex}
Note that all treatments are ranked in \fig{train-bestrest}, even those that never occur in the $best$ set. To decide which treatments should be included as the final recommendation, the best to worst ($R_1$, $R_2$, ...) individual treatments are applied to the $train$ set. Each time a treatment is added, the $train$ set is constrained to rows that only match that treatment. The median utility of the constrained set is compared to the original $train$ set.
$Step5$  explores $R_x$ upwards from $x=1$ while:
\bi
\item
The median $value$ of the rows selected by $R_{x+1}$ is  greater than that of $R_x$.
\item The number of selected rows $|R_x \wedge neighborhood| \ge 3$;
In the case of \fig{testing-constrained}, $Step5$ returns $R_1$ ($FP=lo$). 
\ei
\fig{testing-constrained} shows 
the cases from this neighborhood 
that satisfy $R_1 : FP=lo$.


\fig{testing-constrained} applies $R_1$  on the test data.  Its impact is reported as the median effort value of the cases. Using   $FP=lo$, the constrained testing set gives a median effort of 6.67, a 31\% reduction from the original estimate of 8.8.

\clearpage
\section{Experiments}
To summarize the above, given data divided into $B$ bins, we can
compute $\Delta$-resiliency by the smallest $B' \le B$ such that optimizations
from $B'-1$ bins are \emph{no worse} than $B'$ and optimizations
from $B'+1$ bins are \emph{no better} than $B'$. At this point
$\Delta$-resiliency defines the optimizer's resilience for up to $100 / B' /
4\%$ noise levels.
This section describes such a study using the 
{\W} instance-based planner.

The data used in this study  comes from the PROMISE repository and is shown in \fig{datasets}. One of these data sets ($China$)
is large (499 instances) so  explored two subsets ($china1$ and $china2$ relating to different application types).
\begin{figure}[!b]
\centering
{\footnotesize 
%\begin{sideways} 
\begin{tabular}{l|rrp{1in}|l}  
 \textbf{Dataset} & \textbf{Features} & \textbf{Size} & \textbf{Description}&\textbf{Units}\\\hline
  finnish &8 &38 &Software projects developed in Finland  &hours \\
  kemerer &7 &15 &Large business apos  &months \\
  telecom &3 &18 &Maintenance projects, telecom companies  &months \\
  china &18 &499 &Projects from Chinese software companies  &hours
\end{tabular}
%\end{sideways}
}
\caption{Data used in this study. All data sets are on-line at http://promisedata.org/data.
}\label{fig:datasets}
\end{figure}

\input{figs/effort-results}


We ran {\W} across a series of discretized effort datasets defined
in \fig{datasets}. For bin partitioning we used equal frequency
discretization (i.e. value $x$ is discretized to bin $round\left(\frac{x - min}{(max-min)/B}\right)$) with the number of bins ranging from $B=2$ to $B=10$. 
Some of the results were quite varied so \fig{testing} only shows the results where the inter-quartile range was less than 50\%.

\subsection{Results}

Before presenting the results, we digress to list the result that suggest some pessimism
about the 
thesis of this paper.
If we cannot ignore any data details, and
 those details are required  in order to plan for better software projects, then the planning
results will get steadily {\em worse} as we {\em decrease} the number of bins.

The results of \fig{testing} do not support that pessimistic result.
Measured in terms of how much we can reduce project effort,
sometimes we could ignore most of the details of the data: 
\bi

\item
While results varied from data set to data set, often a $4Bin$ of
$6Bins$ policy performed as well, or better, than anything else
(see $China1, China2, Kemerer, Telecom, Finnish$). 
\item 
In one data set, we could even use $3Bin$ (see $China$) with little lose of reasoning power.
\item
Interestingly,
the fine-grain distinctions of a $10Bin$ discretization never
performed best, suggesting that the data collection methods for all
this data could be relaxed.
\ei
Overall, our results demonstrate little need for fine granularity
in data collection. It's quite possible to reduce data into course
chunks without damaging the ability to make business decisions.




\section{External Validity}

\subsection{Generality Across Different Inference Algorithms}
The above results come from the application of the {\W} instance-based planner. Clearly,
the results may not hold for other planning algorihtms.
Hence, {\em before} an organization applies our definition to their data, they should {\em first}
spend some effort considering how that data will be used.
For example,
in {\S}IV, we compared {\W} to of  gradient descent numerical
optimizers and AI optimers and argued that  {\W} is the
current
``best of breed'' of all the algorithms we have studied so far.
 Nevertheless, a clear future direction for this work is to repeat this study using other
optimizers.

\subsection{Generality Across Different Data Sets}
$\Delta$-resiliency is a general method for determining what level of quality is appropriate for
a particular data set. However,  the  
conclusions drawn from this method are data set dependent:
\fig{testing} shows that
{\em different} sized binnings perform differently in {\em different} data sets.
Looking into the literature, we can see a similar result in machine learning research:
\bi
\item A common result is that some level of discretization is useful~\cite{dou95}.
\item However, the ``best'' level of discretization varies from data set to data set~\cite{FayIra93Multi}.
\ei
Hence, we strongly advise {\em against} applying some data quality policy across a repository {\em without} first conducting some experiments on sample data.

Note only is appropriate level of discretization {\em data set} dependent, it is also {\em instance dependent}.
\fig{bins} shows three bins generated for KLOC for the $Kemerer$ data sets.
In that figure,
the vertical dashed lines indicate the $\frac{B_i}{4}$
ranges for each bin. A measure of interest is $delta_{ij}$, the
the size of the last quartile of one bin and the first quartile
of the next. If this sum is large, then we can be very inexact with our measurements (and otherwise,
we need to be more precise).   


%\input{figs/results-summary}

%\includegraphics[width=3in]{figs/finnish-delta.pdf}
%\includegraphics[width=3in]{figs/china-delta.pdf}
\begin{figure}
\begin{center}
\includegraphics[width=3in]{figs/kem-delta.pdf}
\end{center}
\caption{$\Delta$-resiliency results form the $Kermer$ data set. KLOC divided into 3 bins: $B_1, B_2, B_3$.
Vertical black lines indicate bin boundaries. Vertical dashed lines indicate the $\frac{B_i}{4}$
ranges for each bin. $Delta_{ij}$ denotes the size of the last quartile of one bin and the first quartile
of the next. }\label{fig:bins}
\end{figure}

The important result of \fig{bins} is that $delta_{ij}$ gets {\em smaller} as the KLOC gets {\em larger}.
That is, for this sample of data, we must measure the size
of larger projects with more precision than smaller projects.
This is a counter-intuitive result (to say the least) tell us
that
we should
{\em not} make assertions about appropriate levels of data quality {\em without} making some investigations of the paper.

That said, even though we must use {\em different precision}  when measuring {\em different kinds of project}
(and we cannot know what those differences are without experimentation),
\fig{bins} is still a ``good news'' result:
\bi
\item
 Even thought we cannot determine the exact size
of $delta_{ij}$ for KLOC, we can still say that KLOC does {\em not} need to be measured with great precision.
The smallest $delta_{ij}$ value in \fig{bins} is still relatively large.
\item
For example, our LOC measures
can be up to 31\% inaccurate (100/2/160) for small projects, without unduly influencing estimates
using the $Kemerer$ data set. 
\ei
Note that we do not offer this as a general rule for {\em all} projects.
But for projects collecting data sets like the 14 examples in $Kemerer$ (which are just a few examples
over a very large range), then very precise measurements of LOC are clearly an over-elaboration.
\section{Conclusion}

When analyzing data,  ``garbage in'' means ``garbage out''. But as shown above,
some levels of ``garbage'' can be tolerated by some analyze methods. Before dictating an expensive
corporate-wide 
data quality program, it would be prudent to conduct some experimentation with data samples
in order to determine appropriate levels of data quality.


% conference papers do not normally have an appendix


% use section.on* for acknowledgment
\section*{Acknowledgment}
The work was partially funded by a National Science Foundation grant
CCF-1017330.



% trigger a \newpage just before the given reference
% number - used to balance the columns on the last page
% adjust value as needed - may need to be readjusted if
% the document is modified later
%\IEEEtriggeratref{8}
% The "triggered" command can be changed if desired:
%\IEEEtriggercmd{\enlargethispage{-5in}}

% references section

% can use a bibliography generated by BibTeX as a .bbl file
% BibTeX documentation can be easily obtained at:
% http://www.ctan.org/tex-archive/biblio/bibtex/contrib/doc/
% The IEEEtran BibTeX style support page is at:
% http://www.michaelshell.org/tex/ieeetran/bibtex/
\bibliographystyle{IEEEtran}
% argument is your BibTeX string definitions and bibliography database(s)
\bibliography{refs0,tim,adam}
%
% <OR> manually copy in the resultant .bbl file

% that's all folks
\end{document}

At the point 
\be
\item
Take samples of data.
\item
Take example analytical techniques that run on that data.
\item
Generate a baseline result by running (2) on (1). If that baseline produces interesting and useful results, then
continue (otherwise, this approach will not work).
\item
Inject a little noise into the data. 
\item
Re-run the analytical technique to collect a comparison result.
\item
While the comparison is no different to the baseline, goto 22
\ee


