Error Correction for Massive Data Sets - uniroma1.it

1 Error Correction for Massive data Sets Renato BruniUniversit`adiRoma LaSapienza M. Buonarroti 12, Roma, Italy, 16, 2003 AbstractThe paper is concerned with the problem of automatic detection and cor-rection of errors into Massive data sets. As customary, erroneous datarecords are detected by formulating a set of rules. Such rules are hereencoded into linear inequalities. This allows to check the set of rulesfor inconsistencies and redundancies by using a polyhedral mathematicsapproach. Moreover, it allows to correct erroneous data records by in-troducing the minimum changes through an integer linear programmingapproach. Results of a particularization of the proposed procedure to areal-world case of census data Correction are : data Correction , Inconsistency localization, Massive IntroductionIn the past, for several fields, an automatic information processing have oftenbeen prevented by the scarcity of availabledata. Nowadays data have becomemore and more abundant, but the problem that frequently arises is that suchdata may containerrors.

2 This again makes an automatic processing not appli-cable, since the result is not reliable. Datacorrectnessis indeed a crucial aspectof data quality. The relevant problems of errordetectionandcorrectionshouldtherefo re be solved. When dealing withmassivedata sets, such problems areparticularly difficult to formalize and very computationally demanding to customary for structured information, data are organized has the formal structure of a set offields,orattributes. Giving avaluetoeach field, a record instance, or, simply, a record, is obtained [29]. The problemof Error detection is generally approached by formulating a set ofrulesthat each Work developed during the research collaboration between the University of Roma LaSapienza and the Italian Statistic Office (Istat).1record must respect in order to be declaredcorrect. A record not respecting allthe rules is declarederroneous. In the field of database theory, rules are alsocalledintegrity constraints[29], whereas in the field of statistics, rules are alsocallededits[13], and express the Error condition.

3 The automatic extraction ofsuch rules, or in general of patterns, from a given data -set, constitutes a centralproblem for the areas of data mining and data analysis, particularly in theirdescription aspects [5, 12, 22, 23].The problem oferror correctionis usually tackled by changing some of thevalues of an erroneous record, in order to obtain acorrected recordwhich satis-fies the above rules but preserves as much as possible the information containedin the erroneous record. This is deemed to produce a record which should beas close as possible to the (unknown)original record(the record that would bepresent in absence of errors ). Because of its relevance and spread, the aboveproblem have been extensively studied in a variety of scientific communities. Inthe field of statistics, the Correction process is often subdivided into anerrorlocalizationphase, in which the set of erroneous values within each record isdetermined, and adata imputationphase, in which the correct values for theerroneous fields are imputed.

4 Several different rules encoding and solution al-gorithm have been proposed ( [3, 11, 27, 35]). A very well-known approachto the problem, which implies the generation of all rules logically implied bythe initial set of rules, is due to Fellegi and Holt [13]. In practical case, how-ever, such methods suffer from severe computational limitations [27, 35], withconsequent heavy limitations on the number of rules and records that can beconsidered. In the field of computer science, on the other hand, the correc-tion process is also calleddata cleaning. Such problem is tackled by extractingpatterns from data in [19]. errors may also be detected as inconsistencies inknowledge representation,and corrected with many consistency restoring tech-niques [2, 25, 30]. Another approach to Error Correction , in database theory,consists in performing a cross validation among multiple sources of the same in-formation [29]. This involves relevantlinkageproblems. Recently, a declarativesemantics for the imputation problem has been proposed in [14], as an attemptto give an unambiguous formalization of the meaning of particular, previous approaches to data Correction problems by usingmathematical programming techniques have been used.

5 By requiring to changeat least one of the values involved in each violated rule, a (mainly)set coveringmodel of the Error localization problemhave been considered by many model have been solved by means ofcutting planealgorithms in [15] forthe case ofcategoricaldata, and in [16, 28] for the case above procedures have been adapted to the case of a mix of categoricaland continuous data in [11], were abranch-and-boundapproach to the problemis also considered. Such model, however, does not represent all the problem sfeatures, in the sense that the solution to such model may fail to be a solutionto the localization problem, the separation of the Error localization phase fromthe imputation phase may originate artificial restrictions during the latter one,and computational limitations still automatic procedure for generic data Correction by using new discrete2mathematical models of the problem is here presented. A similar but more lim-ited procedure, which uses only a propositional logic encoding, was describedin an earlier paper [7].

6 Our rules, obtained from several sources ( humanexpertise, machine learning), are accepted according to a specific syntax andautomatically encoded intolinear inequalities, as explained in Sect. 2. Such setof rules should obviously be free frominconsistencies( rules contradictingother rules) and, preferably, fromredundancies( rules which are logicallyimplied by other rules). As a first relevant point, the set of rules itself is checkedfor inconsistencies and redundancies by using the polyhedral mathematics ap-proaches shown in Sect. 3. Inconsistencies are selected by selectingirreducibleinfeasible subsystems(IIS, see also [1, 9, 10, 32]) by using a variant of Farkas lemma (see [31]), while redundancies are detected by finding implied in-equalities. This allows the use of a set of rules much more numerous than otherprocedures, with consequent increaseddetection power, andallows moreover amuch easier merging and updating of existing sets of rules, with consequent in-creased flexibility.

7 After this validation phase, rules are used to detect erroneousrecords. Such records are then corrected, hence changed in order to satisfy theabove rules. As a second relevant point,the Correction problem is modeled as theproblem of minimizing the weighted sum of the changes subject to constraintsgiven by the rules, by using the integer programming formulations describedin Sect. 4. This allows the use of very efficient solution techniques, besides ofhaving the maximum degree of flexibility with respect to data meaning. Theproposed procedure is tested by executing the process of Error detection and cor-rection in the case of real world census data , as clarified in Sect. 5. The abovedepicted models are solved by means of a state-of-the-art integer programmingsolver (ILOG Cplex [21]). The practicalbehavior of the proposed procedure isevaluated both from the computational and from the data quality point of latter analysis is carried out by means of recognized statistical indicators[24].

8 The overall software system developed for the census application, calledDIESIS ( data Imputation Editing System - Italian Software) is described in [6].2 Encoding Rules into Linear InequalitiesIn Database theory, arecord schemais a set of fieldsfi,withi= ,andarecord instanceis a set of valuesvi, one for each of the above fields. In order tohelp exposition, we will focus on records ,however,that the proposed procedure is completely general, because it is not influencedby the meaning of processed data . The record scheme will be denoted byP,whereas a generic record instance corresponding toPwill be denoted {f1,..,fm}p={v1,..,vm}Example records representing persons, fields are for instanceageormaritalstatus, and corresponding examples of values fieldfi,withi= ,hasitsdomainDi, which is the set of every pos-3sible value for that field. Since we are dealing with errors , the domains includeall values that can be found in data , even the erroneous ones. A distinctionis usually made betweenquantitative,ornumerical, fields, andqualitative,orcategoricalfields.

9 A quantitative field is a field on whose values are applied (atleast some) mathematical operators ( >, +), hence such operators shouldbe defined on its domain. Examples of quantitative fields are numbers, or eventhe elements of an ordered set. Quantitative fields can be eithercontinuous( real numbers) ordiscrete( integer numbers) ones. A qualitative fieldsimply requires its domain to be a discrete set with finite number of are not interested here in considering fields ranging over domains having anon-finite number of non-ordered values. The proposed approach is able to dealwith both qualitative and quantitative the qualitative fieldmarital status, answer can vary ona discrete set of possibilities in mutual exclusion, or, due to errors , be missingor not meaningful (blank).Dmarital status={single,married,separate,divorced ,widow,blank}For the quantitative fieldage, due to errors , the domain isDage=Z {blank}A record instance, and in particular a person instancep, is declared correct ifand only if it respects aset of rulesdenoted byR={r1.}

10 ,ru}.Eachrulecan be seen as a mathematical functionrkfrom the Cartesian product of all thedomains to the Boolean set{0,1}, as :D1 .. Dm {0,1}p 0,1 Rules are such thatpis a correct record if and only ifrk(p) = 1 for allk= should be expressed according to some syntax. In our case, each rule isexpressed as a disjunction ( ) of elementary statements calledconditions( h).Conditions can also be negated ( h). Therefore, rules have the structure ofclauses (which are disjunctions of possibly negated propositions). By introduc-ing, for each rulerk,theset kof the indices of its positive conditions and theset kof the indices of its negative conditions,rkcan be written as follows. h k h h k h(1)Since all rules must be respected, a conjunction ( ) of conditions is simplyexpressed using a set of different rules, each made of a single condition. Asknown, all other logic relations between conditions (implication ,etc.) canbeexpressed by using only the above operators ( , , ). Conditions have herean internal structure, and we need to distinguish between two different kind of4structures.