It is well-known in data science that 80% of the work is devoted to preprocessing and only 20% to the actual machine learning or data mining step. This motivates us to explore different ways to (help) automate that preprocessing step. This note focusses on the question whether it is possible to (help) automate the data wrangling process for tabular data in data science.
2.1
Spreadsheet Notation and Properties We only consider spreadsheets that contain one table, but any rectangle finder can be used to extract multiple tables from spreadsheets. A spreadsheet with m columns and n rows is naturally represented by an n m matrix in which each element is a cell.
Each cell has a known and given type. Because semantics of types aren’t used, types are simply labels such as integer and string or just natural numbers. Empty cells get a distinct type ?. The types are stored in a separate matrix. 2015
Hot Coffee 305 Tea 205
Cold
Ice Tea 181 Coke 147
Beer
OCT NOV DEC
An m-ary relation R (A1; : : : ; Am) of n tuples can be easily embedded in a spreadsheet, represented by an n m matrix. Each tuple simply becomes a row in the matrix and each attribute corresponds to a type.
Conversely, any spreadsheet S can be converted to a relation RS by constructing tuples from the rows. Each column becomes an attribute of the relation. We can see that the resulting relation will only be meaningful if each column only consists of elements of the same type. Such a column is called type-consistent and a spreadsheet is type-consistent if all of its columns are. 2.2
Spreadsheet Transformation Programs We limit ourselves to transformations that change the layout of the spreadsheet as in [5]. Such a transformation takes a matrix, optionally some arguments, and returns a new matrix which contains the same elements but repositioned, replicated or removed. 1
An example is the fold transformation, which takes a set of column indices as argument and folds them into one column by adding rows and using the column headers to indicate where it came from.
The list of all such transformations that we consider to construct spreadsheet transformation programs is given in Table 1. It is heavily inspired from those used by existing approaches [7,6,9]. We can extend this list of transformations in order to support more complex spreadsheets.
Applying a transformation results in a reconstruction error. This is a measure of how well it can be inverted given its arguments; or how much information is lost when applying the transformation on an n m spreadsheet. For example, the fold transformation has a reconstruction error of zero as it can be perfectly inverted, while delete has a reconstruction error that depends on of the number of non-empty cells it removes. The reconstruction errors for all operations are given in Table 1.
A spreadsheet transformation program P is then an ordered list of transformations (t1; : : : ; ta) that are applied in order on a spreadsheet S such that P(S) = ta(: : : t1(S) : : :): The reconstruction error of a program is the sum of reconstruction errors of its transformations. 2.3
Given a spreadsheet S and a set of spreadsheet transformation operators, the task is to learn a program P over the operators such that P(S) is type-consistent while keeping the reconstruction error caused by P at 0.
We start from the assumption that a relation R was embedded in spreadsheet space and then restructured using a transformation program over an unknown set of transformations. The result is a spreadsheet S for which RS is not equal to R, but for which we know that R can still be extracted by recovering the structure. A program that successfully transforms an arbitrary spreadsheet into a type-consistent one is believed to have uncovered this underlying structure. Keeping reconstruction error at 0 is necessary to discourage trivial results. For example, only keeping one arbitrary row from the spreadsheet will always result in type-consistency, but will probably not be a desired relation.
As we are only given an input example, this can be seen as a form of predictive program synthesis. The desired output is not given but predicted together with the program that produces it by using the type-consistency constraint, similar to using delimiter alignment in predicting text splitting tasks [10]. Strong enforcement of the type-consistency constraint results in rectangular output tables, another property of relational tables.
Simplifications In these first experiments some simplifications are taken into account. We assume that the types are known up to a granularity that distinguishes each attribute of the relation. For example, a binary relation having types int and int is not valid, but types Age and W eight or 1 and 2 are. The input spreadsheet furthermore contains no noisy, nor missing values. 3
This section explains the naïve algorithm used to perform predictive synthesis. First, we introduce an heuristic that allows to perform a greedy search. Next, this algorithm is presented. 3.1
The type-consistency constraints alone is not useful when searching the program space. We introduce a measure of how well the constraint is satisfied that can serve as a heuristic. Three main properties are taken into account.
First, columns that contain different types need to be punished. Empty values are a wildcard because they are not necessarily wrongly typed. For example, type might still have to be made explicit by a forward fill. This leads to the typeconsistency tcc of a column c to be defined as the joint proportion of the most occurring type and empty type over the total number of elements in the column.
Second, empty cells are addressed by rescaling tcc with the inverse proportion of missing values mc. While these first two properties already result in fully type-consistent tables, they don’t take the shape of the table into account. A table with two columns of the same type will get the maximal heuristic value, but it still violates the fact that each column has to contain a distinct attribute.
Finally, let the type of a column be the type that occurs most often in that column. We scale the heuristic a second time by the proportion of unique column values u. The heuristic value for a table TS with m columns then becomes H(TS ) = 1 Xm tcc(1 m c=1
!
mc) u:
(
Naïve Algorithm for Predictive Synthesis As we have a heuristic that we can optimise and a constraint to be satisfied, a naïve approach for predictive synthesis is a best-first search until the constraint is satisfied.
The parameter space for each transformation can be pruned based on the current table. Most transformations have a computable set of parameters that are useful to apply on a certain table. For example, if no empty values exist in a column, forward filling that column has no effect. Similarly, when folding some columns together we can assume their headers to be of the same type as they will be grouped in one column. Table 1 lists the pruned list of possible arguments for each transformations.
The naïve synthesis algorithm for a table TS is then a very simple greedy search. As long as no program P is found for which H(P(TS )) = 1, the best program so far is extended with all useful transformations. 4
Assume a bar has gathered spreadsheets as in Table 1a over the course of a few years. They now want to get insights in their data such as correlations between the month and sales of hot beverages or a prediction of sales. These are easy tasks that can be performed using e.g. Weka – given that the data is in an appropriate format. Unfortunately, it will not be able to handle the raw data from Table 1a.
Running the naïve synthesis algorithm on this spreadsheet proceeds like the
search tree in Figure 2. It can be seen that parameter pruning is highly effective
at only trying parameter sets that make sense. The desired STP
Fold(
Delete(0) is found without backtracking. Running this program on Table 1a results in a relation
(year, type, drink, month, amount): Different tables for all quarters can be easily joined. The results can be used by standard tools as the relation could be stored in a simple .csv file.
Other simple spreadsheets, based on real world spreadsheets such as those from the Fuse [2] corpus, are similarly wrangled correctly into a relational format. An additional use case is shown in Appendix 1.B. 5
In general, by trying to extract all relational information rather than a subset, we aim to wrangle relational data from spreadsheets without any user interaction. Previous approaches require some manual effort, but allow for a subset of the output space to be extracted. In the context of automated data analysis this tradeoff in flexibility is reasonable, if not beneficial, as features extraction and/or construction will still take place.
Wrangler enables the user to synthesise transformation programs by visually specifying regions of the spreadsheet that are to be fixed, for which an Drop(0) Error 16 Htc 0.75
Drop(
Drop(
Drop(
Fold(1; 3) Error 0 Htc 0.046
Split(0) Error 0 Htc 0.639
Delete(
Drop(0) Error 48 Htc 0.125
Drop(
Drop(
Split(0) Error 0 Htc 0.035
Delete(
Htc 0
ForwardFill(
Error 0 Error 0
Htc 0.263 Htc 0.3
ForwardFill(
Error 0
Htc 0.1125
Delete(0) Delete(
Htc 0.0 Htc 0.08 Htc 0.0 ordered list of transformations is suggested. For many spreadsheets that are similar but not entirely uniform, the scripts might not generalise well and a lot of effort is required. An example of this case is discussed in Appendix 1.B.
FlashRelate learns an extraction program rather than a transformation program. In cases where many sparse columns have to be folded together, many examples might still be needed.
Foofah is closest to the approach presented here, as it synthesises transformation programs similar to ours. It requires complete input-output examples which might not be easy to specify for large tables. 6
In this paper we introduced the problem of automatically wrangling relational data from spreadsheets. We presented a simple heuristic greedy algorithm that is able to synthesise STPs for simple spreadsheets. Parameter pruning for the transformations in the transformation language is an important property of the algorithm. Real world spreadsheets can be correctly wrangled into a relational format, given a distinction in types is known.
In future work, we want to expand on the set of used transformations and the way their parameters are pruned. More specifically, we want to perform extended analysis of their completeness with respect to real world spreadsheets. For now, parameter pruning is largely based on intuition. Furthermore, we are looking at how the type spreadsheet can be automatically generated using hierarchical clustering.
This work is part of the ERC Advanced Grant SYNTH – Synthesising inductive data models, see http://synth.cs.kuleuven.be. Operation Delete Drop Fold ForwardFill
Explanation Error Arguments Delete all rows which The number of non- (1; : : : ; m) have an empty value in empty deleted cells of a given column c. rows that are less specific than a row that is kept. A row is less specific than another row if it contains less values and all of its non-empty values are equal.
Delete column c. Number of no-empty (1; : : : ; m) cells in the deleted column.
Fold x columns into 0 two columns by replacing each row with x new rows where all other columns have the same value and the two new columns contain the old column name and value.
Fill each empty cell in 0 a column with the first preceding non-empty value.
All sets of subsequent columns that have the same type.
All columns with at least one missing value that do not have the first element missing.
All columns with at least two different types that are not ?. ? Split Split a column on type. 0 transpose Transpose columns.
rows and 0
The World Bank provides an interface to download World Development Indicator data in spreadsheet format [11], some exports of which were also found in Fuse. Using default parameters and the codes only option, an example exported spreadsheet is shown in Figure 3a. We can also find a classification for income groups of countries – already in relational format – as shown in Figure 3b.
Suppose we want to learn a classifier for income groups using a relational learner such as Tilde, using the WDI data as features. A desired format for the WDI data could be a relation
(country, indicator, year, value) which the learner can associate with the (country, class) relation to learn a classifier. Running our naïve synthesis algorithm on Figure 3a results in a simple STP that does the job. It managed to prune missing data as well. Other subsets of WDI data can be wrangled in the same way, not requiring any examples or intent. Country Code Series Code AFG PA.NUS.PPP.05 AFG PA.NUS.PRVT.PP.05 AFG EG.CFT.ACCS.ZS DZA PA.NUS.PPP.05 DZA PA.NUS.PRVT.PP.05 DZA EG.CFT.ACCS.ZS 2012 2013 (a) A sample of World Development Indicator data from [11].
Types are indicated using grayscales colors.