%\VignetteIndexEntry{deducorrect}
\documentclass[11pt, fleqn, a4paper]{article}
\usepackage[english]{babel}
\usepackage{amsmath, amssymb}
\usepackage{natbib}
\usepackage{algpseudocode}
\usepackage{algorithm}
\renewcommand{\algorithmicrequire}{\textbf{Input:}}
\renewcommand{\algorithmicensure}{\textbf{Output:}}
\usepackage{threeparttable}

% stimulate latex to put multiple floats on a page.
\setcounter{topnumber}{2}
\setcounter{bottomnumber}{2}
\setcounter{totalnumber}{3}
\setcounter{dbltopnumber}{2}
\renewcommand{\topfraction}{.9}
\renewcommand{\textfraction}{.1}
\renewcommand{\bottomfraction}{.75}
\renewcommand{\floatpagefraction}{.9}
\renewcommand{\dblfloatpagefraction}{.9}
\renewcommand{\dbltopfraction}{.9}
\hyphenation{time-stamp}

\title{Correction of rounding, typing, and sign errors with the {\tt deducorrect} package}
\author{Mark van der Loo, Edwin de Jonge and Sander Scholtus\\
{\small Package version \Sexpr{packageVersion("deducorrect")}}}
\begin{document}
\maketitle
\begin{abstract}

Since raw (survey) data usually has to be edited before statistical analysis
can take place, the availability of data cleaning algorithms is important to
many statisticians.  In this paper the implementation of three data correction
methods in R are described. The methods of this package can be used to correct
numerical data under linear restrictions for typing errors, rounding errors,
sign errors and value interchanges. The algorithms, based on earlier work of
Scholtus, are described and implementation details with coded examples are given.
Although the algorithms have originally been developed with financial balance
accounts in mind the algorithms are formulated generically and can be applied
in a wider range of applications.

This vignette is a near-literal transcript of \cite{loo:2011a}, which corresponds to
package version {\sf 1.0-0}. Please refer to that paper in publications. The paper
is included in the package. This vignette will be updated with the package when necessary.

\end{abstract}

<<echo=FALSE,results=hide, keep.source=FALSE>>=
library(editrules)
library(deducorrect)
@
\maketitle

\newpage

\tableofcontents
\listofalgorithms
\newpage
\section{Introduction}
Raw statistical data  is often plagued with internal inconsistencies and errors
which inhibit reliable statistical analysis. Establishment survey data is
particularly prone to in-record inconsistencies, because the numerical
variables contained in these data are usually interrelated by many mathematical
relationships. Before statistical analysis can take place, these relationships
have to be checked and violations should be resolved as much as possible.
While establishing that a record violates certain relationships is
straightforward, deciding which fields in a record contain the actual errors
can be a daunting task. In the past, much attention has been paid to this
decision problem, often using Fellegi and Holt's principle \citep{fellegi:1976}
as the point of departure. This principle states that for non-systematic errors, and
with no information on the cause of errors, one should try to make a record
consistent by changing as few variables as possible.

This principle precludes using the data available in the (possibly erroneous)
fields to detect and correct the error. In certain cases, naively applying
Fellegi and Holt's principle will yield consistent records with nevertheless
faulty data. As an example, consider a survey record with three variables $x$,
$y$ and $z$, which have to obey the relationship $x=y-z$. Such relationships
frequently occur in financial profit-loss accounts. If a record happens to have
values such that $x=z-y$, then Fellegi and Holt's principle suggests that
either the numerical value of $x$, $y$ or $z$ should be adapted in such a way
that the relationship holds, while the values in the record suggest that the
values in fields $y$ and $z$ might have been interchanged. Swapping the values
of $z$ and $y$ therefore seems a reasonable solution although it formally means
changing two values.

This package provides three functions which do use the data in a record to 
detect and correct errors:
\begin{enumerate}
\item {\tt correctRounding} corrects rounding errors in numerical records that cause 
    violations of linear equality rules. The method works by making small changes
    to a large enough set of randomly chosen variables.
\item {\tt correctTypos} corrects typing erros in numerical records that cause violations
    of linear equality rules. The method works by computing correction suggestions and
    checking which suggestions correspond to correcting a typing error. 
\item {\tt correctSigns} corrects sign flips and value swaps in numerical records which
    violates linear equality rules. The method minimizes the number of value swaps and
    sign flips via a binary programming formulation.
\end{enumerate}
Both {\tt correctTypos} and {\tt correctSigns} are capable of taking account of possible 
rounding errors in the records.



\subsection{Deductive correction}
We use the term deductive correction to indicate methods which use information
available in inconsistent records to deduce and solve the probable cause of
error. Recently, a number of algorithms for deductive correction have
been proposed by \cite{scholtus:2008, scholtus:2009}. These algorithms
can solve problems not uncommon in numerical survey data, namely
%
\begin{itemize}
\item Rounding errors.
\item Simple typing errors.
\item Sign swaps and/or value interchanges.
\end{itemize}
%
The algorithms focus on solving problems in records that have to
obey a set of linear relationships, each of which can be written as
%
\begin{eqnarray}
{\bf a}\cdot{\bf x} \odot b \textrm{ where } \odot \in\{=,\leq,<\}
\label{edit}
\end{eqnarray}
%
Here, every $\bf a$ is a nonzero real vector, $\bf x$ a numerical data record and $b$ 
a constant. In data-editing literature the restrictions imposed on records are
often called edit rules, or edits in short. If an edit describes a relationship
between a number of variables $\{x_j\}$, we say that the edit {\em contains}
the variables $\{x_j\}$. Conversely, when $x_j$ is part of a relationship
defined by an edit we say that $x_j$ {\em occurs} in the edit. We will denote
a generic set of edits with $E$. The matrix representation of (in)equality parts
of $E$ will be denoted $\bf{A}$.


In this paper, we describe the {\tt deducorrect} package for R
\citep{R-core:2011}, which implements (slight) generalizations of the
algorithms proposed by \cite{scholtus:2008, scholtus:2009}. The purpose of this
paper is to provide details on the algorithms and to familiarize users with the
syntax of the package. For a detailed description of the available routines and
their arguments we refer the reader to the reference manual that comes with the
package.

The correction algorithms in the package report the results in a uniform
matter. Section \ref{deducorrectObjectSection} provides details on the {\tt
deducorrect} output object which stores information on corrected records,
applied corrections, and more. Sections \ref{roundingErrors},
\ref{typingErrors} and \ref{signErrors} provide details on the classes of
problems that may be treated with the package, an exposition of the algorithms
used and coded examples with analysis of the results. It is also shown how the
examples from \cite{scholtus:2008} and \cite{scholtus:2009} can be treated with
this software. 

The package requires that linear relationships are defined with the {\tt
editrules} package \citep{jonge:2011}.  The {\tt editrules} package offers
functionality to define and manipulate sets of equality and
inequality restrictions. With the {\tt editrules} package, linear restrictions
can be defined as R-statements (in {\tt character} format) or as a matrix. As
a convenience, one can define edits in any of the forms
\begin{equation}
{\bf a}\cdot{\bf x} \odot b\textrm{ where } \odot \in\{=,\leq,<,\geq,>\},
\end{equation}
and have it automatically translated to the form in \eqref{edit}. A
short introduction to the {\tt editrules} package is given in the appendix of
this paper, but we refer the reader to the package documentation for more
detailed information.  Unless noted otherwise, all R-code examples in this
paper can be executed from the R commandline after loading the {\tt
deducorrect} and {\tt editrules} package. 

Throughout, we denote the Euclidean vector norm with double bars $||\cdot||$
while single bars $|\cdot|$ denote the elementwise absolute values of the
argument.


\subsection{The {\tt deducorrect} object and {\tt status} values}
\label{deducorrectObjectSection}
Apart from the corrected records, every {\tt correct-} function of the {\tt
deducorrect} package returns some logging information on the applied
corrections. Information on applied corrections, a status indicator per record,
a timestamp and user information are included and stored uniformly in a
{\tt deducorrect} object. See Table \ref{deducorrectObject} for an
overview of the contents of this object.
%
\begin{table}
\begin{threeparttable}
\caption{Contents of the {\tt deducorrect} object. All slots can be accessed through the {\tt \$} operator.}
\label{deducorrectObject}
\begin{tabular}{lp{0.7\textwidth}}
\hline
{\tt corrected}   & The input data with records corrected where possible.\\
{\tt corrections} & A {\tt data.frame} describing the corrections. Every record contains a row number, labeling the
row in the input data, a variable name of the input data, the old value and the new value.\\
{\tt status} & A {\tt data.frame} with at least one column giving treatment information of every record in the input data.
    Depending on the {\tt correct} function, some extra columns may be added. \\
{\tt timestamp}   & The date and time when the {\tt deducorrect} object was created.\\
{\tt generatedby} & The name of the function that called {\tt newdeducorrect} to create the object.\\
{\tt user}        & The name of the user running R, deduced from the environment variables of the system using R.\\
\hline
\end{tabular}
\end{threeparttable}
\end{table}
%
Because of the large amount of information in a {\tt deducorrect} object, the
contents are summarized for printing to screen. In the example below, we define one
record of data, a linear restriction in the form of an {\tt editmatrix}, and
apply the {\tt correctSigns} correction method\footnote{sometimes extra
brackets are included to force R to print the result}.
<<>>=
(d <- data.frame(x=1,y=0,z=1))
E <- editmatrix("x==y-z")
sol <- correctSigns(E,d)
sol
@
The individual components of {\tt sol} can be retrieved with the
dollar-operator. The slot {\tt corrected} is the same as the input data, but
with corrected records, where possible:
<<>>=
sol$corrected
@
The applied corrections are stored in the {\tt corrections} slot.
<<>>=
sol$corrections
@
Every row in {\tt corrections} tells which variable in which row of the input
data was changed, and what the old and new values are. The {\tt status} slot
gives details on the status of the record.
<<>>=
sol$status
@
The first column is an indicator which can take five different values,
indicating whether validity could be established, and/or if the record could be
(partially) corrected by the method which created the deducorrect object.  These
values are (see Table \ref{statusvalues} for an overview per {\tt correct}-function):
\begin{itemize}
\item{\sf valid}: The record violates none of the edit rules defined by the user.
\item{\sf corrected}: The record violated one or more edit rules but the {\tt correct-} function
    could adapt the record so no rules are violated afterwards.
\item{\sf partial}: The record violated one ore more edit rules. Some, but not all violations
    could be repaired.
\item{\sf invalid}: The records violates one or more edit rules. None of them could be repaired.
\item{\sf NA}: The record contains missing values, therefore edit violation cannot be establised.
\end{itemize}
%
%
\begin{table}
\begin{threeparttable}
\caption{The number of equalities $n$ and inequalities $m$ violated by an edit,
before and after treatment with one of the correct-functions of {\tt
deducorrect}. The label  {\sf N/A} indicates that this status value does not
occur for tat function. (Note that is is not the same as {\sf NA}, which occurs
when validity could not be established because the record has missing values.)
As an example, consider the fourth row.  In this case, a record enters a {\tt
correct}-function with $n$ linear equality violations. After being treated by
the function less than $n$, but more than 0 edit violations remain.  For {\tt
correctSigns}, this situation cannot occur: the method tries to find a comlete
solution. Both {\tt correctRounding} and {\tt correctTypos} allow for partially
repairing a record, so in their case, the status is labeled ``partial''.}
\label{statusvalues}
\begin{tabular}{cccclll}
\hline
\multicolumn{2}{c}{Before}&\multicolumn{2}{c}{After}&\multicolumn{3}{c}{status}\\
Eqs&  Ineqs &  Eqs  &Ineqs   &{\tt correctSigns}   & {\tt correctRounding} &{\tt correctTypos}\\
\hline
$0$  &  $0$     &  $0$    &$0$      &{\sf valid  }        &{\sf  valid     }      &{\sf  valid}\\
$0$  &  $m$     &  $0$    &$m$      &{\sf invalid}        &{\sf  invalid   }      &{\sf  invalid}\\
$n$  &  $0$     &  $n$    &$0$      &{\sf invalid}        &{\sf  invalid   }      &{\sf  invalid}\\
$n$  &  $0$     &  $<n$   &$0$      &{\sf N/A   }         &{\sf  partial   }      &{\sf  partial}\\
$n$  &  $0$     &  $0$    &$0$      &{\sf corrected}      &{\sf  corrected }      &{\sf  corrected}\\
$n$  &  $m$     &  $n$    &$m$      &{\sf invalid}        &{\sf  invalid   }      &{\sf  invalid}\\
$n$  &  $m$     &  $<n$   &$0$      &{\sf N/A     }       &{\sf  partial   }      &{\sf  partial}\\
$n$  &  $m$     &  $<n$   &$<m$     &{\sf N/A      }      &{\sf  partial   }      &{\sf  partial}\\
$n$  &  $m$     &  $0$    &$0$      &{\sf corrected}      &{\sf corrected  }      &{\sf corrected}\\
\hline
\end{tabular}
\end{threeparttable}
\end{table}
%

The other columns of the {\tt status} slot depend on the function which created
the object and can provide more details on the chosen solutions. These are
described in the coming sections.  



\subsection{Balance accounts and totally unimodular matrices}
\label{totallyUnimodularSection}
Most algorithms described here have been designed with financial balance
accounts in mind. The balance accounts encountered in establishment surveys
mostly involve integer records since financial amounts are usually reported in
currency (kilo-)units. Therefore, linear edit rules of the form
%
\begin{equation}
\label{integerRestrictions}
{\bf Ax} = {\bf b} \textrm{ with } {\bf A}\in \{-1,0,1\}^{m\times n}\textrm{, } {\bf x}\in \mathbb{Z}^{n},\textrm{ and } {\bf b}\in\mathbb{Z}^m,
\end{equation}
are frequently encountered. In all the examples of financial balance accounts
encountered by the authors, the matrix $\bf A$ happened to be totally unimodular.
A (not necessarily square) matrix is called {\em totally unimodular} when every
square submatrix has determinant ${-1}$, $0$, or $1$. The scapegoat algorithm
\citep{scholtus:2008}, which is used in the {\tt correctRounding} function,
requires $\bf A$ to be totally unimodular. See appendix B of \cite{scholtus:2008}
for a further discussion of total unimodularity.  The {\tt deducorrect} package
offers the function {\tt isTotallyUnimodular} which checks if a matrix is
totally unimodular. The algorithm follows  a recursive procedure given below.
\begin{algorithmic}[1]
\Procedure{isTotallyUnimodular}{${\bf A}$}
\State ${\bf A}\leftarrow${\sc reduceMatrix}$({\bf A})$
\If {${\bf A}=\varnothing$}
\State\Return {\sc TRUE}
\ElsIf {Each column of $\bf A$ has exactly 2 nonzero elements}
\State\Return {\sc hellerTompkins}$({\bf A})$
\Else
\State $\mathcal{A} \leftarrow${\sc raghavachari}$({\bf A})$
\If { Every ${\bf A}\in\mathcal{A}$ {\sc isTotallyUnimodular}($\bf A$) }
\State \Return {\sc TRUE}
\Else
\State \Return{\sc FALSE}
\EndIf
\EndIf
\EndProcedure
\end{algorithmic}
Here, {\sc reduceMatrix} iteratively removes all rows and columns of $\bf A$ which
have at most one nonzero element (an operation of $\mathcal{O}(n)$ in the
number of columns and rows).  When possible, the criterium of
\cite{heller:1956}, which is $\mathcal{O}(2^n)$ in the number of columns is
used to determine unimodularity.  If this is not possible, a set of smaller
matrices $\mathcal{A}$ is derived with the method of \cite{raghavachari:1976}.
Every matrix in $\mathcal{A}$ is subsequently checked for total unimodularity
by calling {\sc isTotallyUnimodular}. In the worst case, Raghavachari's method
must be called recursively and checking for unimodularity is $\mathcal{O}(n!)$
in the number of columns. For this reason, our implementation is set up so that
Raghavachari's method is used only after the reduction method and the
Heller-Tompkins method have been tried. Also, matrices are transposed to make
sure that $n$ is minimized in every step. In practical applications $\bf A$ is
often fairly sparse and only a small portion of $\bf A$ has to be treated with the
Raghavachari method.



\section{\tt correctRounding}
\label{roundingErrors}
\subsection{Area of application}
This function can be used to correct violations of linear equality restrictions
because of rounding errors in one or more variables.  The rounding errors are
assumed to be measurement errors rather than rounding errors caused by machine
computation. Rounding errors caused at measurement are on the order of a unit
of measurement, much larger than errors caused by machine computation. The
linear equality restrictions must be of the form
\begin{displaymath}
{\bf A}{\bf x} = {\bf b} \textrm{ with } {\bf A}\in \{-1,0,1\}^{m\times n}\textrm{, } {\bf x}\in \mathbb{Z}^{n},\textrm{ and } {\bf b}\in\mathbb{Z}^m,
\end{displaymath}
where $\bf A$ is a totally unimodular matrix (see Section
\ref{totallyUnimodularSection}), which can be tested with the function {\tt
isTotallyUnimodular}. Linear inequalities with real coefficients can be imposed
as well. The {\tt correctRounding} function will only return solutions which do
not violate any extra inequality violations.

\subsection{How it works}
The {\tt correctRounding} function uses the scapegoat algorithm described in
\cite{scholtus:2008} to suggest corrections for linear equality violations.
Linear inequalities are ignored, except that corrections which cause new
inequality violations are not accepted.  The algorithm first selects linear edit
rules violated by rounding errors. Rounding errors cause small deviations from
equality and therefore deviations smaller than some $\varepsilon$ (say,
$\varepsilon=2)$ are assumed to stem from rounding errors.  Next, a number of
variables --called scapegoat variables-- are selected randomly in such a way
that rounding errors can be solved exactly and uniquely by altering the drawn
scapegoat variables. Note that the number of scapegoat variables is not fixed
and may vary over drawings. If the chosen solution happens to cause new
inequality violations, the solution is rejected and a new set of scapegoat
variables is drawn. This is repeated at most $k$ times.  See Algorithm
\ref{scapegoatAlgorithm} for a concise description of the basic procedure
(without checking for inequalities).
%
%
\begin{algorithm}[t]
\caption{Scapegoat algorithm}
\label{scapegoatAlgorithm}
\begin{algorithmic}[1]
\Require Equality restriction matrix $\bf A$ and constant vector $\bf b$, record $\bf x$,
    rounding tolerance $\varepsilon$. 
\State Remove rows from the system  $\bf Ax=b$ not satisfying $|{\bf a}\cdot{\bf x}-b|<\varepsilon$. 
\If{${\bf A}\not=\varnothing$ {\bf and} $||{\bf Ax-b}||>0$}
\State Randomly permute columns of $\bf A$. Permute $\bf x$ accordingly.
\State Use QR decomposition to partition $\bf A$ columnwise in a square invertible
    matrix ${\bf A}_1$ and remaining columns ${\bf A}_2$.  Partition $\bf x$ in ${\bf x}_1$ and ${\bf x}_2$ accordingly.
\State ${\bf x}_1\leftarrow {\bf A}_1^{-1}({\bf b}-{\bf A}_2{\bf x}_2)$
\State Unpermute $[{\bf x}_1,{\bf x}_2]$
\EndIf
\State Restore $\bf x$ by adding the previously removed elements.
\Ensure ${\bf x}$
\end{algorithmic}
\end{algorithm}
%
%

%
%
\subsection{Examples}
Here, we will reproduce the example of \cite{scholtus:2008}, Section 5.3.2.
Consider an integer-valued record with 11 variables, subject to the rules:
<<keep.source=true>>=
E <- editmatrix( c("X1 + X2 == X3"
                  ,"X2 == X4"
                  ,"X5 + X6 + X7 == X8"
                  ,"X3 + X8 == X9"
                  ,"X9 - X10 == X11"))
@
Consider also the following inconsistent record:
<<>>=
(dat <- data.frame(t(c(12, 4, 15, 4, 3, 1, 8, 11, 27, 41, -13))))
violatedEdits(E,dat)
@
As reported by the {\tt violatedEdits} function, this record violates edit rules
1, 3, 4, and 5.  

Repairing the record can be done with
<<>>=
set.seed(1)
sol <- correctRounding(E,dat)
cbind(sol$corrected, sol$status)
sol$corrections
@
Here, we used {\tt set.seed} to make results reproducible. The result is not
exactly the same as the solution found in the reference. Here, variables $x_3$,
$x_8$ and $x_9$ have been adapted, while in the reference $x_3$, $x_4$, $x_8$, 
$x_9$, and $x_{10}$ were adapted.  Since corrections are very small, smearing out the
effect of adaptations over a number of variables is a reasonable option.

%
%
%
\section{\tt correctTypos}
\label{typingErrors}
%
\subsection{Area of application}
This function can be used to correct typographical errors in an integer record.
Examples of typographical errors include extra or to few digits, digit
permutations and/or digit substitutions.  To be precise, the method can be
applied to integer records $\bf x$ which violate linear equality constraints as
in Eq.\ \eqref{integerRestrictions}:
\begin{displaymath}
{\bf Ax} = {\bf b} \textrm{ with } {\bf A}\in \{-1,0,1\}^{m\times n}\textrm{, } {\bf x}\in \mathbb{Z}^{n},\textrm{ and } {\bf b}\in\mathbb{Z}^m.
\end{displaymath}
In fact, the function will also run when ${\bf A}\in \mathbb{R}^{m\times n}$.
However, the nature of the algorithm is such that it is unlikely that typing
errors will be found for such systems.  The algorithm was developed with sets
of financial balance equations in mind, where these type of problems are very
common. As far as inequalities are concerned, they are currently ignored by the
algorithm, in the sense that no attempt is made to repair inequality
violations. However, the algorithm does not generate solutions causing extra
inequality violations.

The function has a parameter $\varepsilon$ which allows for a tolerance so that
rounding errors can be ignored. The default value of $\varepsilon$ is almost
zero: it is set to the square root of {\tt .Machine\$double.eps} which amounts
to approximately $10^{-8}$.  The value should be increased, to 2 units of
measurement for example, to allow for rounding errors that are caused by
measurement rather then machine computation. This way, records containing just
rounding errors can be ignored by {\tt correctTypos} but do note that in that
case they will receive the status {\tt valid}, since no typos were found.

\subsection{How it works}
In short, the algorithm first computes a list of suggestions which correct one
or more violated edits (Algorithm \ref{generateCandidates}). The corrections
not corresponding to a typographical error are removed, after which  the set of
suggestions that maximize the number of satisfied edit rules is determined
(Algorithm \ref{maximizeResolvedEdits}). 

Suggestions are generated for the set of variables which {\em only} occur in
violated edits since altering these variables will have no effect on already
satisfied edits. For every variable $x_j$, define the matrix ${\bf A}^{(j)}$ who's
rows represent edits containing ${x}_j$. Suggestions $\tilde{x}^{(i)}_j$ for
every row $i$ of ${\bf A}^{(j)}$ can be generated by solving for ${x}_j$:
%
\begin{equation}
\tilde{x}_j^{(i)} = \frac{1}{A_{ij}^{(j)}} \left(b_i - \sum_{j'\not=j}A_{ij'}^{(j)}x_j\right).
\end{equation}
%
We keep only the unique suggestions, and reject solutions which are more than a
certain Damerau-Levenshtein distance removed from the original value. The {\em
Damerau-Levenshtein} distance $d_{\rm DL}$ between two strings $s$ and $t$ is
the minimum number of character insertions, deletions, substitutions and
transpositions necessary to change $s$ into $t$ or {\em vice versa}
\citep{damerau:1964,levenshtein:1966}.  The remaining set of suggestions
$\{x^{(i)}_j\}$ will in general contain multiple suggestions for each violated
edit $i$ and multiple suggestions for each variable $x_j$. Using a tree search
algorithm, a subset of $\{x^{(i)}_j\}$ is selected which maximizes the number
of resolved edits. The tree search is sped up considerably by pruning branches
which resolve the same edit multiple times or use multiple suggestions for the
same variable. When multiple solutions are found, only the variables which
obtain the same correction suggestion in each solution are adapted.

This algorithm generalizes the algorithms of \cite{scholtus:2009} in the
following two ways: first, the imposed linear restrictions are generalized from
${\bf Ax=0}$ to $\bf Ax=b$. Secondly, the original algorithm allowed for a single {\em
digit} insertion, deletion, transposition or substitution. The more general
Damerau-Levenshtein distance used here treats the digits as characters,
allowing for sign changing, which is forbidden if only digit changes are
allowed. Also, by applying a standard Damerau-Levenshtein algorithm it is easy
to allow for corrections spanning larger values $d_{\rm DL}$. That is, one
could allow for multiple typos in a single field. Moreover, the
Damerau-Levenshtein distance as implemented in the {\tt deducorrect} package
allows one to define different weights to the four types of operations
involved, adding some extra flexibility to the method.
%
%
\begin{algorithm}[t]
\caption{Generate solution candidates}
\label{generateCandidates}
\begin{algorithmic}[1]
\Require Record $\bf x$, a set of linear equality restrictions and a list of variables to {\tt fixate}. A maximum
Damerau-Levenshtein distance {\tt maxdist}.
\State $L\leftarrow\varnothing$
\State Determine $J_0=\{j: x_j \textrm{ occurs {\em only} in violated edits and not in {\tt fixate}}\}$
\For { $j\in J_0$}
\State Determine the matrix ${\bf A}^{(j)}$ of violated edits containing $x_j$ and associated constant vector ${\bf b}^{(j)}$
\For { every row $i$ of $A^{(j)}$}
\State $\tilde{x}_j^{(i)} \leftarrow \left(b_i^{(j)}-\sum_{j'\not=j}A_{ij'}^{(j)}x_{j'}\right)/A_{ij}^{(j)} $
\State $L\leftarrow L\cup\tilde{x}_j^{(i)}$ \Comment{Only new values are added}
\EndFor
\EndFor
\State Remove $\tilde{x}^{(i)}_j$ from $L$ for which $d_{\rm DL}(\tilde{x}^{(i)}_j,x_j)>{\tt maxdist}$ 
\Ensure List $L$ of $m$ unique solution suggestions for record ${\bf x}$.
\end{algorithmic}
\end{algorithm}
%
\begin{algorithm}[t]
\caption{Maximize number of resolved edits}
\label{maximizeResolvedEdits}
\begin{algorithmic}[1]
\Require Record ${\bf x}$, a list of linear equality restrictions and a list of solution suggestions
$L = \{L_\ell=\tilde{x}^{(i_\ell)}_{j_\ell}:\ell=1,2,\ldots, m\}$
\State $k\leftarrow 0$ 
\State $s\leftarrow {\sf NULL}$
\Procedure{tree}{${\bf x},L$}
\If{$L\not=\varnothing$}
\State {\sc tree}$({\bf x},L\backslash L_1)$\Comment{Left branch: don't use suggestion}
\State $x_{j_1}\leftarrow L_1$ \Comment{Right branch: use suggestion}
\State $L\leftarrow L\backslash \{x^{(i_\ell)}_{j_\ell}\in L: j_\ell=j_1 \textrm{ \bf  or } x^{(i_\ell)}_{j_\ell}\textrm{ occurs in same edit as } L_1\}$
\State {\sc tree}$({\bf x},L)$
\Else
\If{Number of edits $n$ resolved by $x$ larger then $k$}
\State $k \leftarrow n$
\State $s \leftarrow x$
\EndIf
\EndIf
\EndProcedure
\Ensure { (partial) solution $s$, resolving maximum number of edits. }
\end{algorithmic}
\end{algorithm}

\subsection{Examples}
In this section we show the most important options of the {\tt correctTypos}
function.  After a simple, worked-out example we reproduce the results in
Chapter 4 of \cite{scholtus:2009}.

First, define a simple one-record dataset with an associated edit rule.
<<>>=
dat <- data.frame(x = 123, y = 192, z = 252)
(E <- editmatrix("z == x + y"))
@
Obviously, the edit in {\tt E} is not satisfied since $123+192=315$. As can be
seen from the output of {\tt editmatrix}, we have $b=0$, so the correction
candidates here are:
\begin{eqnarray}
\tilde{x}^{(1)} &=& 0 - \frac{-1\cdot 192+1\cdot252}{-1} = 60\\
\tilde{y}^{(1)} &=& 0 - \frac{-1\cdot 123+1\cdot252}{-1} = 129\\
\tilde{z}^{(1)} &=& 0 - \frac{-1\cdot 123-1\cdot192}{1} = 315 
\end{eqnarray}
The Damerau-Levenshtein distances between the candidates and their originals
are given by:
\begin{eqnarray}
d_{\rm DL}(\tilde{x}^{(1)},x) = d_{\rm DL}(60,123) &=& 3\textrm{ (two substitutions and an insertion)}\\
d_{\rm DL}(\tilde{y}^{(1)},y) = d_{ DL}(129,192)   &=& 1\textrm{ (one transposition)}\\
d_{\rm DL}(\tilde{z}^{(1)},z) = d_{ DL}(315,252)   &=& 3\textrm{ (three substitutions)}
\end{eqnarray}
In this case, there is just one candidate with $d_{\rm DL}=1$, solving the 
inconsistency with just one digit transposition. Running the record through 
{\tt correctTypos} indeed finds the digit transposition:
<<>>=
correctTypos(E, dat)$corrected
@
%
\cite{scholtus:2009} (Chapter 4) treats a series of examples which we will
reproduce here.  We consider a dataset with 11 variables, subject to the
following edit rules.
<<keep.source=true>>=
E <- editmatrix( c("x1 + x2 == x3"
                  ,"x2 == x4"
                  ,"x5 + x6 + x7 == x8"
                  ,"x3 + x8 == x9"
                  ,"x9 - x10 == x11"))
@
%
The following dataframe contains the correct record ({\tt example 4.0}) as well
as the manipulated erroneous records.
<<keep.source=true,echo=false>>==
dat <-as.data.frame( matrix(c(
    1452, 116, 1568, 116, 323, 76, 12, 411,  1979, 1842, 137,
    1452, 116, 1568, 161, 323, 76, 12, 411,  1979, 1842, 137,
    1452, 116, 1568, 161, 323, 76, 12, 411, 19979, 1842, 137,
    1452, 116, 1568, 161,   0,  0,  0, 411, 19979, 1842, 137,
    1452, 116, 1568, 161, 323, 76, 12,   0, 19979, 1842, 137), 
    byrow=TRUE,nrow=5))
rownames(dat) <- paste("example 4.",0:4,sep="")
colnames(dat) <- paste("x",1:11,sep="")
@
<<>>=
dat
@
This {\tt data.frame} can be read into R by copying the code from the {\tt
correctTypos} help page. As can be seen, example 4.1 has a single digit
transposition in $x_4$, example 4.2 has the same error, and an extra 9 inserted
in $x_9$, example 4.3 contains multiple extra errors (in $x_5$, $x_6$ and $x_7$
which cannot be explained by simple typing errors.  Finally, example 4.4 also
has multiple errors which cannot all be explained by simple typing errors. This
example has multiple solutions which solve an equal amount of errors.

The violated edit rules may be listed with the function
<<>>=
violatedEdits(E,dat)
@
Now, to apply as many typo-corrections as possible:
<<>>=
sol <- correctTypos(E, dat)
cbind(sol$corrected, sol$status)
@
Our implementation finds the exact same solutions as in the original paper of
\cite{scholtus:2009}.  Also see this reference for a thorough analysis of the
results.

%
%
%
\section{\tt correctSigns}
\label{signErrors}
\subsection{Area of application}
This function can be used to solve sign errors and value swaps which cause
linear equalities to fail. Possible presence of linear inequalities are taken
into account when resolving errors, but they are not part of the error
detection process. The function has an argument $\varepsilon$ which allows one
to ignore rounding errors that can mask sign errors and value swaps.  The
standard value is the square root of machine accuracy ({\tt
.Machine\$double.eps}).  It should be increased to 2 units of measurement or
more to account for rounding errors caused by measurement.


\subsection{How it works}
The function {\tt correctSigns} tries to change the sign of (combinations of)
variables and/or swap the order of variables to repair inconsistent records.
Sign flips and value swaps are closely related since
\begin{equation}
-(x - y) = y - x,
\end{equation}
These simple linear relations frequently occur in profit-loss accounts for
example.  Basically, {\tt correctSigns} first tries to correct a record by
changing one sign. If that doesn't yield any solution, it tries changing two,
and so on. If the user allows value swaps as well, it starts by trying to
correct the record with a single sign flip or variable swap. If no solution is
found, all combinations of two such actions are tried, and so on. The algorithm
only treats the variables which have nonzero coefficients in one of the
violated equality constraints.  Since the number of combinations grows
exponentially with the number of variables to treat, the user is given some
control over the volume of the search space to cover in a three different ways. 
\begin{enumerate}
\item The variables which are allowed to flip signs or variable pairs which
may be interchanged simultaneously can be determined by the user. Knowledge of
the origin of the data will usually give a good idea on which variables are
prone to sign errors.  For example, in surveys on profit-loss accounts,
respondents sometimes erroneously submit the cost as a negative number.
\end{enumerate}
Once variables which may change sign, and variable pairs which may be permuted
are determined, the number of combinations may still become large. If there are
$n$ possible sign flips and value swaps, there are $\sum_{k}{ n \choose k}=2^n$
possible repair actions in total. The second option allows the user to
\begin{enumerate}
\setcounter{enumi}{1}
\item limit the maximum number $k$ of simultaneous sign flips and/or value swaps
that may be tested. This is controlled by the {\tt maxActions} parameter in
Algorithm \ref{correctSigns}.  
\end{enumerate}
Since the function tries to repair the record with $k=1$, $k=2,\ldots$, an extra control parameter
allows the user to
\begin{enumerate}
\setcounter{enumi}{2}
\item exit the function when the number of combinations ${ n \choose k}$ becomes too large. This is controlled by the {\tt
maxCombinations} parameter in Algorithm \ref{correctSigns}.
\end{enumerate}
%
%
\begin{algorithm}[t]
\caption{Record correction for {\tt correctSigns}}
\label{correctSigns}
\begin{algorithmic}[1]
\Require A numeric record $\bf x$, a tolerance $\varepsilon$. A set of equality and
    inequality constraints of the form
\begin{eqnarray*}
{\bf Ax} &=& {\bf b}\\
{\bf Bx} &\leq& {\bf c},
\end{eqnarray*}
A list {\tt flip} of variables of which the signs may be flipped, a list {\tt swap} of
variable pairs of which the values may be interchanged, an integer {\tt maxActions}, an
integer {\tt maxCombinations} and a weight vector.

\State Create a list {\tt actions}, of length $n$ containing those elements of {\tt flip} and {\tt swap} that
    affect variables that occur in violated rows of $A$.
\State Create an empty list $S$.
\State $k\leftarrow 0$
\While {$S=\varnothing$ {\bf and} $k<\min({\tt maxActions},n)$}
  \If {{\bf not} ${n\choose k}>{\tt maxCombinations}$}
   \State $k\leftarrow k+1$ 
   \State Generate all ${n\choose k}$ combinations of $k$ actions.
   \State Loop over those combinations, applying them to $x$. Add solutions
obeying $|{\bf Ax-b}|<\varepsilon$ and ${\bf Bx}\leq{\bf c}$ to $S$.
  \EndIf
\EndWhile
\If {{\bf not} $S=\varnothing$ }
\State Compute solution weights and choose solution with minimum weight. Choose
the first solution in the case of degeneracy.
\EndIf
\State Apply the chosen solution, if any, to {\bf x}.
\Ensure {\bf x}
\end{algorithmic}
\end{algorithm}

To account for sign errors and variable swap errors which are masked by
rounding errors, the user can provide a nonnegative tolerance $\varepsilon$, so
the set of equality constraints are checked as
\begin{equation}
|{\bf Ax -b}| < \varepsilon,
\end{equation}
elementwise.

The function tries to find and apply the minimal number of actions (sign flips
and/or variable swaps) necessary to repair the record. It is not guaranteed
that a solution exists, nor that the solution is unique. If multiple solutions
are found, the solution which minimizes a weight is chosen.  The user has the
option to assign weights to every variable, or to every action.  The total
weight of a solution is the sum over the weights of the altered variables or
the sum over the weight of the actions performed. Actions with higher weight
are therefore less likely to be performed and variables with higher weight are
less likely to be altered.

This algorithm is a generalization of the original algorithms in
\cite{scholtus:2008} in two ways. First, the original algorithm was designed
with a specific type of profit-loss account in mind, while the algorithm of
{\tt deducorrect} can handle any set of linear equalities. Second, the original
algorithm was not designed to take account of inequality restrictions, which is
a feature of the algorithm in this work. In Section
\ref{exScholtusCorrectSigns} it is shown how the results of the original
example can be reproduced.



%
%
\subsection{Some simple examples}
In this section we walk through most of the options of the {\tt correctSigns}
function.  We will work with the following six records as example.
<<keep.source=TRUE>>=
(dat <- data.frame(
    x = c( 3, 14, 15,  1, 17, 12.3),
    y = c(13, -4,  5,  2,  7, -2.1),
    z = c(10, 10,-10, NA, 10, 10 )))
@
We subject this data to the rule
\begin{equation}
z = x-y.
\end{equation}
With the {\tt editrules} package, this rule can be parsed to an {\tt editmatrix}.
<<keep.source=true>>=
E <- editmatrix(c("z == x-y"))
@
Obviously, not all records in {\tt dat} obey this rule. This can be checked with 
a function from the {\tt editrules} package:
<<>>=
cbind(dat, violatedEdits(E,dat))
@
Records 1, 2, 3 and 6 violate the editrule, record 5 is valid and for record 4
validity cannot be established since it has no value for $z$.  If  {\tt
correctSigns} is called without any options, all variables $x$, $y$ and $z$ can
be sign-flipped:
<<>>=
sol <- correctSigns(E, dat)
cbind(sol$corrected, sol$status)
sol$corrections
@
So, the first three records have been corrected by flipping the sign of $z$, $y$
and $z$ respectively.  Since no weight parameter was given, the {\tt weight} in the output 
is just the number of variables whose have been sign-flipped. The {\tt degeneracy} column
records the number of solutions with equal weight that were found for each record.
Record 4 is not treated,
since validity could not be established, record 5 was valid to begin with and
record 6 could not be repaired with sign flips. However, record 6 seems to have
a rounding error.  We can try to accomodate for that by allowing a tolerance
when checking equalities.
<<>>=
sol <- correctSigns(E, dat, eps=2)
cbind(sol$corrected, sol$status)
sol$corrections
@
Indeed, changing the sign of $y$ in the last record brings the record within
the allowed tolerance.  Suppose that we have so much faith in the value of $z$,
that we do not wish to change its sign.  This can be done with the {\tt
fixate} option:
<<>>=
sol <- correctSigns(E, dat, eps=2, fixate="z")
cbind(sol$corrected, sol$status)
sol$corrections
@
Indeed, we now find solutions whitout changing $z$, but at the price of more
sign flips.  By the way, the same result could have been obtained by
<<results=hide>>=
correctSigns(E, dat, flip=c("x","y"))
@
The sign flips in record one and three have the same effect of a variable swap. Allowing
for swaps can be done as follows.
<<keep.source=true>>=
sol <- correctSigns(E, dat, swap=list(c("x","y")), 
    eps=2, fixate="z")
cbind(sol$corrected, sol$status)
sol$corrections
@
Notice that apart from swapping, the algorithm still tries to correct records
by flipping signs.  What happened here is that the algorithm first tries to
flip the sign of $x$, then of $y$, and then it tries to swap $x$ and $y$.  Each
is counted as a single action. If no solution is found, it starts trying
combinations. In this relatively simple example the result turned out well. In
cases with more elaborate systems of equalities and inequalities, the result of
the algorithm becomes harder to predict for users. It is therefore in general
advisable to 
\begin{itemize}
\item Use as much knowledge about the data as possible to decide which
variables to flip sign and which variable pairs to swap.  The problem treated
in section \ref{exScholtusCorrectSigns} is a good example of this.
\item Keep {\tt flip} and {\tt swap} disjunct. It is better to run the data a few times 
        times through {\tt correctSigns} with different settings.
\end{itemize}
Not allowing any sign flips can be done with the option {\tt flip=c()}.
<<>>=
sol <- correctSigns(E, dat, flip=c(), swap=list(c("x","y")))
cbind(sol$corrected, sol$status) 
sol$corrections
@
This yields less corrected records. However running the data through 
<<>>==
correctSigns(E, sol$corrected, eps=2)$status
@
will fix the remaining edit violations. The last two statements are easier to
interpret than the one before that.

<<echo=false, results=hide>>=
# make x and y swappable, swap a counts as one flip
correctSigns(E, dat, flip="z", swap=list(c("x","y")))

# same, but now, swapping is preferred (has lower weight)
correctSigns(E, dat, flip="z", swap=list(c("x","y")), weight=c(2,1))

# same, but now becayse x any y carry lower weight. Also allow for rounding errors
correctSigns(E, dat, flip="z", swap=list(c("x","y")), eps=2, weight=c(x=1, y=1, z=3))

# demand that solution has y>0
E <- editmatrix(c("z==x-y", "y>0"))
correctSigns(E,dat)

# demand that solution has y>0, taking acount of roundings in equalities
correctSigns(E,dat,eps=2)
@

\subsection{Sign errors in a profit-loss account}
\label{exScholtusCorrectSigns}
Here, we will work through the example of chapter $3$ of \citet{scholtus:2008}.
This example considers 4 records, labeled case a, b, c, and d, which can be
defined in {\tt R} as
<<keep.source=TRUE>>=
dat <- data.frame(
   case = c("a","b","c","d"),
   x0r = c(2100,5100,3250,5726),
   x0c = c(1950,4650,3550,5449),
   x0  = c( 150, 450, 300, 276),
   x1r = c(   0,   0, 110,  17),
   x1c = c(  10, 130,  10,  26),
   x1  = c(  10, 130, 100,  10),
   x2r = c(  20,  20,  50,   0),
   x2c = c(   5,   0,  90,  46),
   x2  = c(  15,  20,  40,  46),
   x3r = c(  50,  15,  30,   0),
   x3c = c(  10,  25,  10,   0),
   x3  = c(  40,  10,  20,   0),
   x4  = c( 195, 610,-140, 221))
@
A record consists of 4 balance accounts of which the results have to add up to
a total.  Each $x_{i,r}$ denotes some kind of revenue, $x_{ic}$ some kind of
cost and $x_i$ the difference $x_{i,r}-x_{i,c}$. There are operating,
financial, provisions and exeptional incomes and expenditures. The differences
$x_0$, $x_1$, $x_2$ and $x_3$ have to add up to a given total $x_4$.  These
linear restrictions must be defined with the use of the {\tt editrules} package.
<<keep.source=TRUE>>=
E <-editmatrix(c(
    "x0 == x0r - x0c",
    "x1 == x1r - x1c",
    "x2 == x2r - x2c",
    "x3 == x3r - x3c",
    "x4 == x0 + x1 + x2 + x3"))
E
@
Checking which records violate what edit rules can be done with the {\tt
violatedEdits} function of {\tt editrules}. 
<<>>=
violatedEdits(E,dat)
@
So record 1 (case a) for example, violates the restrictions $e_1$:
$x_1=x_{1,r}-x_{1,c}$ and $e_5$, $x_0+x_1+x_2+x_3=x_4$.  We can try to solve the
inconsistencies by allowing the following flips and swaps:
<<keep.source=TRUE>>= 
swap <- list(
    c("x1r","x1c"), 
    c("x2r","x2c"), 
    c("x3r","x3c"))
flip <- c("x0","x1","x2","x3","x4")
@
%
Trying to correct the records by just flipping and swapping variables
indicated above corresponds to trying to solve the system of equations
\begin{equation}
\left\{\begin{array}{lcl}
x_0s_0 &=& x_{0,r}-x_{0,c}\\
x_1s_1 &=& (x_{1,r}-x_{1,c})t_1\\
x_2s_2 &=& (x_{2,r}-x_{2,c})t_2\\
x_3s_3 &=& (x_{3,r}-x_{3,c})t_3\\
x_4s_4 &=& x_0s_0 + x_1s_1 + x_2s_2 + x_3s_3\\
\multicolumn{3}{l}{(s_0,s_1,s_2,s_3,s_4,t_1,t_2,t_3)\in\{-1,1\}^{8}},
\end{array}\right.
\end{equation}
where every $s_i$ corresponds to a sign flip and $t_j$ corresponds
to a value swap, see also Eqn.\ (3.4) in \cite{scholtus:2008}.
Using the {\tt correctSigns} function, we get the following.
<<>>=
cor <- correctSigns(E, dat, flip=flip, swap=swap)
cor$status
@
As expected from the example in the reference, the last record could
not be corrected because the solution is masked by a rounding errors.
This can be solved by allowing a tolerance of two measurements units.
<<>>=
cor <- correctSigns(E, dat, flip=flip, swap=swap, eps=2)
cor$status
cor$corrected
@
The latter table corresponds exactly to Table $2$ of \cite{scholtus:2008}.

\section{Final remarks}
This paper demonstrates our implementation of three data correction methods,
initially devised by one of us (\cite{scholtus:2008, scholtus:2009}).  With the
{\tt deducorrect} R package, users can correct numerical data records which
violate linear equality restrictions for rounding errors, typographical errors
and sign errors and/or value transpositions. Since both the algorithms
correcting for typographical and sign errors can take rounding errors into
account, a typical data-cleaning sequence would be to start with correcting for
sign- and typographical errors, ignoring rounding errors and subsequently
treating the rounding errors. We note that data cleaning can be sped up
significantly if independent blocks of editrules are treated separately.  If an
matrix representation of a set of edits can be written as a direct sum ${\bf
A}={\bf A}_1\oplus {\bf A}_2$, data can be treated for editrules in ${\bf A}_1$
and ${\bf A}_2$ independently.  The {\tt editrules} package offers
functionality to split editmatrices into blocks via the {\tt findblocks}
function.



\bibliographystyle{chicago}
\bibliography{deducorrect}

\newpage
\appendix
\section{Some notes on the {\tt editrules} package}
The {\tt editrules} package \citep{jonge:2011} is a package for reading, parsing and
manipulating numerical and categorical editrules. It offers functionality to
conveniently construct edit matrices from verbose edit rules, stated as 
R statements. As an example consider the following set of edits on 
records with profit $p$, cost $c$, and turnover $t$.
\begin{equation}
\left\{\begin{array}{lcl}
t &\geq& 1\\
c &\geq& 0\\
t &=& p + l \\
p &<& 0.6t.  
\end{array}\right.
\end{equation}
The first two rules indicate that cost must be nonnegative, and turnover must
larger than or equal to 1. The third rule indicates that the profit-loss
account must balance, and the last rule indicates that profit cannot be more
thatn 60\% of the turnover. Denoting a record as a vector $(p,l,t)$,  these
rules can be denoted as matrix equations:
\begin{eqnarray}
\left[\begin{array}{ccc}
0 & 0 & 1\\
0 & 1 & 0\\
\end{array}\right]
\left[\begin{array}{c}p\\l\\t\end{array}\right] &\geq& 
\left[\begin{array}{c}1\\0\end{array}\right]\\
\left[\begin{array}{ccc}
1 & 1 & -1
\end{array}\right]
\left[\begin{array}{c}p\\l\\t\end{array}\right] &=& 0\\
\left[\begin{array}{ccc}
1 & 0 & -0.6
\end{array}\right] 
\left[\begin{array}{c}p\\l\\t\end{array}\right] &<& 0
\end{eqnarray}
In the {\tt editrules} package, these linear rules are all stored in a single object, called an
{\tt editmatrix}. It can be constructed as follows:
<<keep.source=true>>=
(E <- editmatrix(c(
    "t >= 1", 
    "l >= 0",
    "t == p + l",
    "p < 0.6*t")))
@
An {\tt editmatrix} object stores a stacked matrix representation of linear
edit resrictions. Alternatively, one can define edits as a matrix and
cast it into an {\tt editmatrix} object:
<<keep.source=true>>=
E <- matrix(c(
     1,   0, 0,
     0,   1, 0,
     1,  -1,-1,
    -0.6, 1, 1),
    nrow=4,
    byrow=TRUE,
    dimnames=list(
        1:4,
        c("t","l","p")
    )
)
b <- c(1,0,0,0)
ops <- c(">=", ">=", "==", ">")
(E <- as.editmatrix(E,b,ops))
@


There are more storage modes in {\tt editrules} which we will
not detail here. Users can extract
(in)equalities through the {\tt getOps} function which returns a vector of
comparison operators for every row. For example:
<<keep.source=true>>=
E[getOps(E)==">=", ]
@
Alternatively, the comparison operators of an edit matrix may be normalized:
<<>>=
editmatrix(editrules(E),normalize=TRUE)
@
The {\tt editrules} package offers functionality to check data against any set
of editrules. The function {\tt violatedEdits}, for example returns a boolean
matrix indicating which record violates what editrules. {\tt editrules} also
offers editrule manipulation functionality, for example to split editmatrices
into independent blocks. For further functionality of the {\tt editrules}
package, refer to the package documentation.




\end{document}
