一种基于实例的数据转换方法

An Instance-Based Data Transformation Method

摘要: Web中包含大量有用的信息，但由于它们是半结构化的，非专家用户在进行数据转换和集成时不能很好地利用。为此本文提出了一种基于实例的数据转换方法，用户只需要提供适当的输入–输出示例就可以得到所需的转换。首先，利用基于序列比对的模式距离度量方法依据用户提供的示例生成代表性示例；其次，提出了一种基于信息熵的代码分析方法，利用该方法与代表性示例结合来筛选与转换任务相关的候选函数；最后，通过函数排名将相关函数先进行列转换，再行合成与所有示例一致的数据转换程序。本文利用房地产领域数据集进行了实验评估，结果表明，该方法可以处理目前许多现有系统不支持的常见转换，并且能够实现实验系统中近80%的数据转换，其准确率远高于其他同类型系统。

Abstract: The Web contains a lot of useful information, but because it is semi-structured, non-expert users are not able to make good use of it in data transformation and integration. Therefore, this paper pro-poses an instance-based data transformation method. Users only need to provide appropriate in-put-output examples to get the required transformation. First, a pattern distance measurement method based on sequence alignment is used to generate representative examples from us-er-provided examples. Secondly, a code analysis method based on information entropy is proposed, which is combined with representative examples to screen candidate functions related to transformation tasks. Finally, the related functions are converted into rows and columns through function rankings, and then a data conversion program is synthesized that is consistent with all the examples. In this paper, we use real estate data set to carry out experimental evaluation, and the results show that this method can deal with many common conversions that are not supported by existing systems, and can achieve nearly 80% of the data conversions in the experimental system, and its accuracy is much higher than other systems of the same type.

1. 引言

在Web数据集成过程中，数据通常是半结构化的状态，而数据转换(Data Transformation)是将数据从一种表现形式变为另一种表现形式的过程。用户在进行数据分析之前，通常需要对不同来源收集的原始数据进行预处理，其中包括数据清洗、数据归约、数据转换等。研究表明，数据分析师要花费近80%的时间在数据准备上 [1]，这对用户来说不仅困难而且耗时。为了解决这种现状，本文提出了一种基于实例的数据转换方法，它允许最终用户仅通过几个示例来实现数据转换，这种方法称为范例编程(PBE) [2]。PBE的好处 [3] 在于用户不必学习一种编程语言就可以自动的完成一些重复性的任务，并且用户是通过一个他所熟悉的界面将任务演示给系统的。FlashFill [4] 也使用这种范例进行数据转换，取得了很大的成功。但FlashFill是由领域特定语言(DSL)中预定义的少量字符串原语组成，表达性具有一定的限制。与现有的PBE系统相比，本文提出的方法可以从更大的搜索空间(成千上万个函数)中合成数据转换程序。

1.1. 主要实例

本文引用了实际项目中的城市房地产大数据，该数据是利用网络爬虫从各城市房地产交易备案信息网站所爬取，并经过数据集成处理的真实数据。图1给出了一个示例数据集，来自相同列的值是高度异构的，当数据来自不同的源，或者手动输入，这种情况经常发生。如果数据分析师想要找出某个月中哪一处房产销售最好，并不能通过执行一个SQL语句查询找到它。再比如说分析师可能想要根据城市或区域(从地址中提取)分析销售情况，这都需要非常复杂的数据转换。

Figure 1. Urban real estate transaction data with heterogeneous values

图1. 具有异构值的城市房地产交易数据

Figure 2. Standardized urban real estate transaction data

图2. 规范化的城市房地产交易数据

本文针对的是不同字段的规范化转换，其中输入是不同字段的字符串值，输出是对应字段规范化的数据类型值。用一个例子来说明这种转换，如图2所示。图2是图1中的数据经过转换后得到的规范化数据，也是用户想要的最终数据形式。

1.2. 本文主要工作

为了提高数据转换的效率，减少用户工作量，本文利用基于序列比对的模式级度量方法来生成代表性示例。在生成代表性示例之后，我们需要弄清楚哪些函数可能与给定的转换任务相关，由于盲目测试所有爬取到的函数会耗费大量的精力，所以本文提出了一种基于信息熵的代码分析方法，把代表性示例作为函数参数，用该方法来筛选候选函数。之后对候选函数进行排名，目的是找到要执行的相关函数，根据执行结果合成数据转换程序，最终生成目标输出。通过实验验证了没有编程能力的用户利用该方法也能够进行相关的数据转换工作，同时减少了专家用户的精力消耗。本文做的主要贡献如下：

1) 由于用户提供的示例有限，本文在引入模式距离、元素距离等概念的基础上，利用基于序列比对的模式级距离度量方法，生成实现数据转换的代表性示例。

2) 本文提出了一种基于信息熵的代码分析方法，用于筛选与转换任务相关的候选函数。并利用L1-Ranking和L2-Ranking两种排名方法，对候选函数进行排名，根据执行结果选择相关字段的转换函数(列转换)，综合生成数据转换程序(行合成)。

3) 在房地产大数据的真实数据集上进行了实验，实验结果表明本文提出的基于实例的数据转换方法与现有的数据转换方法相比具有良好的效果。

2. 相关研究

目前在数据转换方面的代表性研究方法大致可分为如下几类：

1) 基于菜单的转换

大多数现有的数据准备系统都有常用于转换的菜单，用户也希望在这些菜单上找到合适的转换，比如Paxata和OpenRefine，但是这两个系统只支持有限数量的简单类型数据转换。

2) 基于语言的转换

有的现有系统定义了自己的转换语言，用户需要学习怎么编写数据转换程序。比如Trifacta定义了一种叫Trifacta的“牧马人”语言；OpenRefine也有自己的表达式语言。但是对于这种领域特定语言来说，它们不仅表达能力有限，而且具有局限性。

3) 基于输入进行转换

Trifacta采用了一种PBE变体形式，用户可以选择输入一部分数据，然后系统给出可能的转换建议(称为预测性交互 [5])。同样的还有Informatica Rev和Talend，这两个系统也可以根据所选输入建议进行数据转换。但是仅通过输入，系统不确定要使用哪个输出，而且经常会产生许多不相关的建议。

4) 使用字符串原语的示例驱动搜索进行的转换

FlashFill [3] 使用PBE范例用于表格数据转换，以及与FlashFill相类似的系统Foofah [6]、Blinkfill [7]、Flashextract [8] 等，它们通过用户提供输入–输出示例，之后系统将使用简单的字符串原语来查找与示例一致的程序。尽管PBE范例在很大程度上改善了易用性，但是现有系统的表达能力受到了限制，不支持需要特定领域知识的复杂转换。

5) 使用搜索引擎的示例驱动进行的转换

DataXFormer [9] 使用搜索引擎查找相关的Web表，可以从中提取转换任务所需的输出值。值得注意的是，与只使用示例的PBE不同，DataXFormer需要列标题作为构建关键字查询的输入。虽然Web表是重要的数据源，但是DataXFormer缺乏综合处理复杂转换的结果的能力。

表1总结了相关系统之间的比较情况。

Table 1. Comparison of related systems

表1. 相关系统的比较

3. 系统概述

在本节中主要展示了系统的工作框架，该系统有两个主要阶段：离线阶段和在线阶段，下面将叙述这两个阶段的主要工作内容。

离线阶段：首先从现有的资源GitHub上爬取了大量代码片段，索引了.Net系统库中的所有函数，以及来自 [10] 变体中的映射关系。鉴于爬取到的代码片段数量庞大，最关键的一步是在需要运行时快速地找到与转换任务相关的函数。所以对函数进行离线分析，使用代码分布分析技术，筛选出候选函数(第4节)。映射关系与字典查找类似，是补充代码的一部分(本文不做叙述)。对于一些需要大量外部资源的复杂转换，该系统还会用到Web服务，因为只有Web服务具有复杂的特定于域的逻辑，可以执行较为复杂的转换。

在线阶段：在这个阶段，给定一个转换任务，系统使用离线阶段构建的索引快速查找相关的转换函数，然后将其用于合成与所有输入–输出示例匹配的数据转换程序。本文设计了两种排序方法，以及程序合成算法，可以有效地将相关函数组合成复杂的数据转换程序(第5节)，从而完成用户提交的转换任务。

系统架构图如图3所示。

Figure 3. System architecture

图3. 系统架构图

4. 离线函数索引

在给定大量代码的情况下，最关键的是我们要弄清楚哪些函数与转换任务相关。盲目测试所有爬取到的函数会大大降低数据转换的效率，所以我们对黑盒函数进行离线分析。先前的代码分析技术(静态编码和动态生成)利用的是代码中的现有数据，尽管有用，但是这几种技术可能会受代码编写方式的限制。因此，本文提出的代码分析技术，利用“信息论”来测试黑盒函数。首先通过序列比对的方式生成一组代表性示例E (包括很多数据类型)，然后将E中的每个值作为参数传递给每个函数f，通过观察f在其输出分布方面的行为，来判断适合f的合适输入。下面将介绍该方法的具体理论研究。

4.1. 生成代表性示例

标点符号通常充当丰富数据类型的结构定界符，因此本文通过使用标点符号对字符串进行“分段”来生成标点符号诱导序列。

定义1 给定字符串v，定义 $s_v$ 是其标点符号诱导序列，其中每个元素要么是单个标点符号，要么是不带标点符号的最大子字符串。

例如，“2020/2/9”的标点符号诱导序列为{“2020”，“/”，“2”“/”，“9”}。

给定两个序列 $s_u$ 和 $s_v$，根据序列比对定义它们的模式水平距离。在一般的序列比对中 [11]，两个序列 $s_u$ 和 $s_v$ 之间的距离是通过用特殊间隙符号“-”来填充两个序列并计算的，从而产生具有相同数量元素的序列 $s_u$ 和 $s_v$，以便它们可以“对齐”，并且在所有这样的 $s_u$ 和 $s_v$ 上最小化它们的元素距离之和，计算公式如下：

${\displaystyle {\sum }_{i\in \left[\left|{\bar{s}}_u\right|\right]}d\left({\bar{s}}_u\left[i\right],{\bar{s}}_v\left[i\right]\right)}$ (1)

其中 $s\left[i\right]$ 表示序列s的第i个元素。

本文采用此序列比对框架来定义模式距离，然后基于字符类定义不同的元素距离。具体来说，我们考虑三类字符：字符，数字和标点符号P。一对元素之间的距离定义如下：

定义2 两个元素e，e'之间的距离为 $d\left(e,e^{\prime }\right)$，则

$d\left(e,e^{\prime }\right)=\{\begin{array}{ll}1,\hfill & \text{if}e=“\text{-}”o\text{r}{e}^{\prime }=“\text{-}”\hfill \\ 0,\hfill & \text{if}e,e^{\prime }\in P,e=e^{\prime }\hfill \\ 1,\hfill & \text{if}e,e^{\prime }\in P,e\ne e^{\prime }\hfill \\ 1,\hfill & \text{if}e\in P,e^{\prime }\notin P\hfill \\ \text{1}-\frac{\min \left(n_l\left(e\right),n_l\left(e^{\prime }\right)\right)+\min \left(n_d\left(e\right),n_d\left(e^{\prime }\right)\right)}{\max \left(n\left(e\right),n\left(e^{\prime }\right)\right)},\hfill & \text{if}e,e^{\prime }\notin P\hfill \end{array}$ (2)

其中“-”表示插入的特殊间隙字符； $n\left(e\right)$ 、 $n_l\left(e\right)$ 、 $n_d\left(e\right)$ 分别表示e中的字符、字母、数字总数，当 $e\notin P$ 时， $n\left(e\right)=n_l\left(e\right)+n_d\left(e\right)$。

上述定义确保了元素之间的距离 $d\left(e,e^{\prime }\right)\in \left[0,1\right]$。然后将两个序列的模式距离定义为它们的平均元素距离，类似于其他序列比对距离，定义如下：

定义3 序列 $s_u$ 和 $s_v$ 之间的模式距离 $d\left(s_u,s_v\right)$ 定义为

$d\left(s_u,s_v\right)=\underset{{\bar{s}}_u,{\bar{s}}_v}{\min }av{g}_{i\in \left[\left|{\bar{s}}_u\right|\right]}d\left({\bar{s}}_u\left[i\right],{\bar{s}}_v\left[i\right]\right)$ (3)

使用这种模式级别的距离，我们可以计算出相同列中的字符串之间的距离都很短，所以是“相似的”，因此我们可以选择其中一个字符串来代表每一列，该字符串即为代表性示例。

4.2. 基于熵的分布分析算法的相关理论

在获得以E表示的代表性示例之后，将E作为参数来执行所有的候选函数F。其思想是，通过观察在 $f\in F$ 上执行E之后的结果分布，我们可以推断出 $E_f\subset E$ 是f的合适输入。具体来说，有两种方案：

方案一：函数f需要严格检查输入参数的有效性，如果输入值不是预期的格式，则f会出错(引发异常，返回空对象等)。例如，如果输入不是函数可以处理的预期日期时间字符串，比如DateTime.Parse()函数将引发格式错误。对于此类函数，由于E中只有一小部分合适的值会被执行，因此观察所有E组的结果会使 $E_f$ 变得简单。

方案二：并非所有函数都会严格检查输入是否存在错误，许多函数可能不会因为输入不当而出错，但仍会返回一些结果，基于分布的分析仍将显示适合f的 $E_f\subset E$。具体来说，f通常对特定类型的输入数据执行某种类型的转换，然后用适当的结果填充返回对象。例如，一个解析日期值的GitHub函数返回一个日期对象，该对象具有诸如int year，int month，int day，string day-of-the-week等等的属性，当日期字符串有效并且作为参数传递时，返回对象中的这些属性值将被正确填充。但是，如果输入值不是日期时间而是其他字符串，则该函数可能会以不同的方式终止，返回对象中的属性值将具有默认初始值，在这种情况下，年，月，日为0，一周中的某天为空字符串。

在f上执行E之后，我们可能会看到返回了一大堆(可能是“默认”)值，然后是一小群不同的值(可能是f有意义的输出)。一大组相同结果(可能毫无意义)和一小撮不同结果(可能有意义)之间的划分实际上始终适用于方案一和方案二。在方案一中，我们也可以将异常视为输出。

由于这些期望的分布对应于信息论中的低熵分布 [12]，因此我们使用熵来识别此类函数f及其对应的 $E_f$。分布X的熵定义为：

$H\left(X\right)=-{\displaystyle \underset{i}{\overset{n}{\sum }}P\left(x_i\right)}\log P\left(x_i\right)$ (4)

其中 $P\left(x_i\right)$ 是第i个结果 $x_i$ 在X的概率。因为熵对于具有更大域的变量(例如，字符串/布尔型)会自然变大，因此我们使用归一化使之对域不敏感，用归一化熵定义为：

$N\left(X\right)=-\frac{{\displaystyle {\sum }_i^{n}P\left(x_i\right)\log P\left(x_i\right)}}{\log n}$ (5)

$N\left(X\right)$ 小表明分布高度偏斜，可以从中相应地识别出 $E_f$。

这种基于熵的方法适用于多种函数，例如处理特定数据类型(IP地址，电话号码等)的特定于域的函数，以及诸如阶乘函数(只接受非负整数)等一般数值函数。当我们推断出给定函数f的 $E_f$ 之后，这些 $E_f$ 就可以用于填充表2中的索引表，该索引表又将用于函数排名，接下来将进行讨论。

Table 2. Sample functional index table

表2. 示例函数索引表

5. 在线程序合成

使用第4节中的技术，我们可以离线地将每个函数f与适合f的示例参数 $E_f$ 关联。在本节中，我们讨论在线阶段的以下几个步骤：

1) 给定一个带有输入/输出示例的用户任务T，对所有候选函数F进行排名以找到要执行的相关函数；

2) 利用L1-Ranking和L2-Ranking两种排名方法，对候选函数进行排名；

3) 根据执行结果选择相关字段的转换函数(列转换)，综合生成数据转换程序(行合成)。

5.1. L1-Ranking

按输入模式进行L1排名。该方法是基于比较函数f接受的输入参数的模式和任务T的输入值的模式。令T.I为任务T的输入示例，函数f的输入排序为

$R\left(f,T\right)={\min }_{v\in E_f,u\in T.I}d\left(v,u\right)$ (6)

因为我们使用距离，所以得分越低表示匹配越好。这种排名方法适用于各种语义数据值，例如IP地址、电话号码、电子邮件、日期时间、邮政地址等，其中大多数都有固定标点序列的结构化模式，基于模式的排名可以很好地识别。

按输入–输出关系对进行L1排名。该方法适用于语法转换的一类函数，例如用于驼峰/标题换行的函数，或用于修剪空白或删除连续空白的函数。对于此类函数，输入可以是没有独特模式的任何字符串。具体来说，使用英文字母中的标准字符分组(例如，小写/大写字母，字母，数字，字母数字等)，我们“描述”函数f的输入/输出之间的语法差异。例如，对于修剪空白的函数，一种描述其输入/输出差异的简洁方法是从输入中删除空白，而其他类别的字符不受影响(描述为{删除：{“”}，插入：∅，更新：∅})。

然后给定用户任务T(例如标题框)，我们可以类似地将其输入/输出差异简要描述为{删除：∅，插入：∅，更新：{小写→大写}}。可以通过计算删除/插入/更新类别之间的平均相似性得分，并相应地对函数f进行排名，从而将T的描述与每个f的描述进行比较。对于这种T函数(例如上壳体、骆驼壳体)将排在较高的位置，而空间修剪函数将排在较低的位置。

两种L1排序方法是相当互补的(一种侧重于处理语义数据的函数，而另一种则更适合于语法函数)，在转换任务中常常从两个排名中获取top-K函数的并集。

5.2. 列转换

$R_K$ 表示L1排序器返回的前K个函数，T表示转换任务，T中总共提供了m个(通常为3个)输入/输出示例。令 $T.I\left[i\right]$ 为第i个输入单元， $T.O\left[i\right]$ 为第i个输出单元。目标是使用 $T.I\left[i\right]$ 作为输入执行 $R_K$ 中的函数，为所有 $0\le i\le m$ 生成目标输出 $T.O\left[i\right]$。

我们首先考虑使用 $T.I\left[i\right]$ 作为输入执行 $f\in R_K$，以产生目标 $T.O\left[i\right]$， $\forall i\in \left[m\right]$。其中，目标 $T.I\left[i\right]$ 是字符串，而函数f的输出可以是字符串，但在一般情况下，函数返回面向对象语言的对象。但是即使我们对T具有正确的函数f，f的输出也不可能与目标输出完全匹配。这里的关键是自动合成程序把结果对象转换为目标输出字符串。

拿转换图1中的销售时间任务 $T_{\text{date}}$ 来说，由于函数System.DateTime.Parse( )对于 $T_{\text{date}}$ 排名较高，因此我们将使用 $T_{\text{date}}.I\left[i\right]$ 中的输入作为参数来执行它，这将导致DateTime对象。我们使用一种称为反射 [13] 的编程语言机制，该机制允许我们以编程方式访问每个活动对象并在运行时遍历其成员属性和方法。具体来说，如图4所示，我们能够使用此反射来“转储”每个返回的DateTime对象的所有成员属性的值，其中包括几十个属性，例如Year，Month等。此外，我们可以使用反射来枚举DateTime对象中的成员方法，例如ToLongDateString( )和ToUTC( )。由于这些都是无参数方法，因此我们可以再次从每个返回的DateTime对象中调用以产生更加丰富的中间结果，如图4所示。

给定中间表具有从输入值派生的丰富语义信息，从而“组合”其中的位和片段以产生目标 $T.O\left[i\right]$。

Figure 4. Reflection dump process of T_date

图4. T_date反射转储过程

5.3. L2-Ranking

给定任务T，由于程序合成过程利用了 $R_K$ 中的许多函数，因此它可能会产生与所有给定示例一致的多个程序。为了适当地排序合成程序以供用户检查，我们引入了另一级别的排名，称为L2排名。在L2排名中，我们使用L1排名中不可用的执行信息来对合成程序进行重新排名。

我们的观察结果是，一个数据转换程序的复杂性通常是一个很好的指标，它可以很好地概括T中的几个示例(通常只有3个)。例如，对于图4中的输入，假设目标输出是星期几，一个正确的数据转换程序利用函数DateTime.Parse()产生目标输出。该程序总体上将(1)调用一个外部函数，(2)从结果中合成一个子字符串操作，总复杂度为2。

5.4. 行合成

把图1中异构的数据转换成图2规范化的数据，首先需要对表中的每个字段进行数据转换，由于表中的每行记录都是由不同类型的字段组成的，因此需要用到不同的转换函数。为了转换成用户最终期望得到的规范化数据表，我们需要对表中多个字段进行列转换(第5.2节)，之后再进行行合成。行合成的定义如下：

定义4 定义 $\Gamma =\left(T_1,T_2,\cdots ,T_n\right)$，其中 $T_n$ 表示第n个转换任务，每个转换任务都是针对列进行的，所以每个 $T_n$ 都有其各自对应的 $R{}_K$。对 $T_n$ 做列转换，把与 $T_n$ 所有相关的 $f\in R_K$ 进行程序合成，合成一组与 $\Gamma$ 对应的组函数 $\Lambda =\left(f_1,f_2,\cdots ,f_n\right)$。

6. 实验与分析

6.1. 数据集

本文采用的数据集是从中国土地网、安居客等房地产网站爬取的关于房产销售方面真实数据，经过数据清洗、无关信息删除两个预处理过程，数据信息属性见表3所示。为了验证本文提出的方法的可行性和有效性，我们还构建了关于房地产销售方面的数据转换任务实例，以供我们进行实验研究。

Table 3. Property description of real estate information data sheet

表3. 房地产信息数据表属性说明

6.2. 实验设置

大多数任务有5~6对输入/输出示例，对于所有被测试的系统，我们使用3对输入/输出作为训练示例，并将其余的作为测试用例进行测试，以验证数据转换合成程序是否正确。只有当一个程序的所有输出都符合基本事实时，它才被认为是正确的。在本文中，我们测试每个系统的平均精度，定义为解决的任务数量除以总任务数量，如下列公式所示：

$\text{Precision}=\frac{解决的任务数量}{总任务数量}\times 100\text{\%}$

本文提出的L1-Ranking排名方法是从索引到的所有函数中选择一组有希望的函数，它是判断系统与用户交互性能的关键组成部分：排名越好，程序合成的速度就越快。

6.3. 实验结果及分析

图5显示了在同一数据集下，本文原型系统TDE与其他系统的比较结果。总的来说，TDE为近80%的转换任务生成了预期的合成程序，大大优于其他系统，因为TDE利用了其他系统所没有的各种特定于领域的强大功能。

Figure 5. System comparison chart

图5. 系统比较情况图

Figure 6. Validity test of L1-Ranking

图6. L1-Ranking的有效性测试

图6评估了两种L1-Ranking方法的有效性，其中y轴显示仅使用L1-Ranking的top-K函数可以解决的任务百分比，x轴显示数量K，K会影响响应时间。从图中我们可以看到，两种L1-Ranking方法是互补的，并且它们结合起来要好得多。总体而言，使用top-200的函数可以解决大约70%的情况，而使用top-1000的函数可以解决90％的情况(对应于我们计算机上约5秒的响应时间)。

7. 结论

本文首先通过用户提供的原始数据，利用序列比对的方式生成代表性示例，并通过基于信息熵的代码分析方法筛选候选函数，之后通过L1-Ranking方法对候选函数排名，并针对给定的数据转换实例综合生成Web表的字段(列)和记录(行)数据转换程序。实现验证了本文提出的方法在很大程度上为缺乏编程技能的用户提供了便利，能完成近80%的转换任务，其中通过实验评估了两种L1-Ranking方法的有效性。