基于真值发现的加油站车辆号牌缺损数据填充方法

彭新亮 程 力 王 轶 马 博 赵 凡 周 喜*

1(中国科学院新疆理化技术研究所 新疆 乌鲁木齐 830011)2(中国科学院大学 北京 100049)3(新疆理化技术研究所新疆民族语音语言信息处理实验室 新疆 乌鲁木齐 830011)

0 引 言

随着自动化数据采集技术的发展,加油站车辆加油数据的采集工作正在逐渐由人工采集转向物联网设备自动采集。由于数据采集设备的车牌识别精度不足、环境影响、网络不稳定等因素的影响，同一辆汽车在不同加油站终端数据系统中所采集到的车牌号码也有可能不同。并且，从这些设备汇总得到的数据中车牌号码存在大量丢失和错误(以下简称缺损)情况。某地区收集的车辆加油数据中，缺损数据约占总数据的20%以上。由于未采用有效的方法对此部分数据进行处理，严重影响了后续对这些数据的分析工作，不利于数据融合的开展。因此，针对这种多数据源离散型分类数据的缺损值填充问题的研究，对于提高原始数据的可用性和融合数据的正确性都至关重要。

在融合互联网多源数据时，由于不同数据源自身数据不完整的原因，导致相同数据在融合时产生冲突，无法确定真值的问题。Yin等[1]首次将此问题定义为真值发现，并提出了TruthFinder算法解决此问题。鉴于多源数据的特殊性和数据质量的重要性，本文提出了一种基于真值发现的缺损数据填充方法。该方法将经过预处理的数据通过改进的Truth Finder迭代计算真值，再按照一定的策略对缺损数据进行填充，有效地解决了多数据源离散型分类数据的缺损值填充的问题。

1 相关工作

对于缺损数据的处理在数据的预处理阶段十分常见。就目前而言，在数据挖掘和机器学习领域对于缺损值的处理方式主要分为两类，直接删除相应缺失数据所在数据行和算法填充[2]。又根据填充数据的产生规则，可将数据填充分为基于数据集自身统计特征的填充和基于机器学习模型的预测值填充两类[2]。

直接删去缺损值所在的数据行的方法，可以非常简单地使得原始数据成为完整的数据集。在缺损数据所占比重较小的时候采用这种方法是很有效的。然而，操作简单意味着其局限性也十分突出。因为直接删去了原始数据的若干记录会造成原始数据的缺失，一些隐藏在数据中的信息同时也会被遗弃，这将直接影响下一步的数据分析结果的有效性。甚至在缺损数据量较大时，使用这种方法会直接导致原始数据偏离正常分布，给出错误的数据挖掘结果。

在统计学领域，一些学者提出了用统一值、平均值等一些基本统计量来对缺损值进行直接替换，使得原始数据形成完备数据集。文献[3]介绍了使用方差校正的方法，对缺损数据进行插补。文献[4]介绍了使用最大期望算法(Expectation Maximization Algorithm, EM)和贝叶斯网络(Bayesian network)的丢失数据填充算法。该算法利用Naive Bayesian模型估计出EM算法的初始值，然后结合这两种模型迭代确定更新器，同时对缺损值进行填充。这些方法的优点是简单快速，对于数据维度不大的数据集而言是一种有效的处理手段。但是在缺损数据所占比重较大或者数据较为复杂时，这种方法很可能会丢弃原始数据中的大量隐藏信息，甚至影响原始数据整体的分布情况，直接影响数据的可用性。

更为普遍的方法是对缺损值进行预测填充，寻找缺损值的最近似值来进行替换。研究者们提出了大量基于统计分析、机器学习的模型和算法。文献[5]将数据分为决策属性和条件属性，利用支持向量机来预测条件属性的值，从而填充缺失数据。除此之外，也有采用K最近邻算法[6-8]、信息增益[9]、人工神经网络[10-12]等算法对缺损数据项进行预测，找出最有可能的数值来进行填充。

这些方法在处理缺失数据方面各有优势，某些算法模型在处理连续型数值数据时会取得较好的效果。而某些算法更适用于离散型数值数据。但是对于加油站车辆数据这种离散型分类数据而言，目前仍未找到有效的处理方法，一种可行的方法是按照不同加油站根据车辆加油的频率，按照少数服从多数的方式，使用投票(Voting)的策略估计缺失数据[13]。本文提出了使用改进过的用于真值发现的TruthFinder算法将处理过的原始数据输入到算法模型中，通过迭代计算的方式求得数据的真实值，然后按照一定策略对算法将得到的真值填充回原始数据中，以此解决加油站车辆号牌缺失数据的填充问题。通过在真实加油站数据集的实验结果证明，该方法相较于传统的Voting算法有23%的正确率提升，很大程度上提高了加油站数据的可用性。

2 缺损值填充框架

2.1 问题的产生背景

数据质量问题作为制约数据可用性的关键问题，长久以来深受研究者的重视。如何对原始数据进行清洗，提高其可用性，是大家关注的重点。文献[14]针对数据质量问题提出了一个可以动态配置规则的数据清洗框架，如图1所示。

图1 动态配置规则的数据清洗流程

在对加油站数据进行预处理阶段，主要任务是对数据文件某些字段中的错误、缺失和不一致问题进行修正。如图1所示，该框架使用了三种可动态配置的规则(DRDDLS、REGEX、FUNCTION)以及规则间的逻辑运算，可以对脏数据进行保留、丢弃、回填三种修复操作。但是在实际应用于真实数据时发现，数据修复阶段往往由于大量数据的丢失，而无法为其配置合适的规则，从而导致无法有效地对数据开展清洗工作，使得最终的清洗结果无法达到要求。因此本文针对此问题提出了解决方案。

2.2 问题的定义及分析

在加油站车辆数据中，每条数据包含车辆的驾驶员信息、加油站信息、车辆的车牌号码等内容。

由于一些原因，数据中存在大量无法使用传统图像再识别等方式修复的数据，制约了数据的可用性。因此，如何使用算法将丢失的号牌尽可能修复出来，从而提高数据的可用性将十分有意义。

如图2所示，车主在加油站A与加油站B等多个加油站进行过加油。由于加油站设备的原因，导致不同的加油站数据库中存放车辆号牌产生区别，至少有一个车牌识别结果是错误的。在各加油站数据需要融合处理时，需要对其真值做出判断。此外，若存在此车主在加油站C的加油记录且此记录中车牌号码识别失败产生缺失数据时，又涉及到如何填充此缺损值的问题。因此，为了保证加油站数据的可用性，需要对这样的数据进行填充处理。

图2 加油站数据真值问题

在讨论缺损值填充问题之前，基于常识和对数据的观察，提出一些基本的假设，以便于下述问题的处理：

假设一：各个数据源之间不存在联系，所提供的数据相互独立，这个条件在加油站数据中显然成立，不同的加油站之间并没有任何数据间的联系。

假设二：在某个区域内的一段时间里，一个普通用户(以用户身份证号码为区分)不会频繁更换车辆加油。即一个用户不会每次都驾驶不同的车辆进行加油，显然，大多数人是满足该假设的。这样车辆就与用户关联起来了。

假设三：车辆加油存在一定的连续性，某辆车大概率会在某地区内频繁加油，而小概率不在本地区加油。

2.3 符号及其含义

表1给出了真值发现问题中的一些基本概念及其描述。

表1 规则、符号的意义

2.4 TruthFinder算法

在多源数据融合领域，不同数据源对数据的表示方式、格式等不同，在对多源数据进行融合时会遇到无法判断来自哪个数据源的值正确或者以哪个数据源的值为准的问题[15]。

为解决此问题，TruthFinder算法将各个数据源看作一张图上的节点，定义出了数据源的可信度和数据值的准确度两个变量描述这个图，使用迭代计算的思路分别计算数据值的准确度和数据值的可信度，直至收敛。

算法开始时，统一设定所有数据源的初始可信度为t(s)，假设一个实体真值数据只存在一种数据值f,则某数据源的数据值错误可能性为1-t(s)，故在全部数据源的基础上可计算得到数据值的准确度为：

(1)

在求得各个数据值的准确度之后，算法即可根据简单的几何概率模型求得某一数据源的可信度为该数据源所表示的所有数据准确度之和与该数据源所描述数据值的个数|F(S)|的比值。即数据源S的可信度为：

(2)

以上是简单模型中求解数据源可信度和数据值准确度的过程。由于一个现实实体真值在多源情况下不可能只有一个数据值描述值，因此，不同数据源中会有对同一数据的描述，往往这些描述是相互关联的。将数据值f1对数据值f2的关联记作imp(f1→f2)。故调整后的数据值准确度如下，其中ρ是调节参数：

(3)

原算法考虑到不同数据源之间的并非完全独立，在处理最终结果时加入了数据源独立参数γ调节最终结果:

s*(f)=1-e-γ·s(f)

(4)

由式(2)和式(4)即可迭代计算数据源的可信度和数据值的准确度，直至计算结果不再变化为止，所得到的准确度最高的数据值即为所求的真值。

2.5 基于真值发现的缺损值填充方法

本文所用方法整体框架如图3所示。

图3 基于TFD(Truth Filling Declare)算法的 缺损值填充计算框架

在传统的真值发现算法中，数据值之间的支持度imp(f1→f2)定义比较模糊，大部分直接将数据看作普通文本，使用两个数据值的余弦相似度用于计算。由于处理数据的类型不同，这样的做法在加油站车辆数据这种短文本数据中显然是不合理的。例如，用户A在f1加油站加油时识别的车辆号牌为“京A12345”,在加油站f2加油时识别的车辆号牌为“津A12345”。这其中显然有一个加油站的数据是错误的，此时若按照传统的相似度作为支持度的计算，则:

imp(f1→f2)=cosine(f1,f2)=

在上例中，根据词频可以将f1的向量表示为(1,0,1,1,1,1,1,1)，f2的向量可以表示为(0,1,1,1,1,1,1,1)。可以计算得到二者的余弦相似度为0.857，显然这样的相似度表明这两个数据之间存在较高的支撑关系。反映到实际的计算中就会导致异常高的支持度，这样在进行迭代计算的过程中，某些实际错误的数据会因为其他数据的较高支持，也计算得到较高的准确度，从而影响最终进行数据填充的结果。为了解决加油站车牌数据中使用文本相似度所带来的问题，本文提出采用0-1相似度来计算数据之间的支持度，其计算公式如下：

这样可以使得在短文本真值算法处理时获得更加准确的计算结果。

2.6 数据填充过程

如图3所示，在原始数据预处理阶段需要从数据库中抽取数据，由于原始数据在维度、格式上与TFD算法要求的输入存在差异，需要进行相应的格式转换。格式转换完成后，会对原始数据进行适当删减，去除那些不满足算法假设的数据。例如在整个数据集中只进行过一次加油或者某辆车每次加油都是不同的车主驾驶，这些数据将无法被算法框架所计算。另外，在实际情况中，单个数据源内部由于一些原因，其多次提供的数据值可能也存在偏差。因此需要统一单一数据源的描述值。

通过对原始数据的预处理，得到相应的实验数据集，实验数据集将直接作为TFD算法的输入。之后将采用迭代计算的方式计算真值，根据输出结果即可知道不同数据的真实情况。计算过程的伪代码如下：

输入：经过处理的各个加油站不同用户的加油数据{F(S)}S,∈M。

输出：各个用户所驾驶车辆的真实车牌号码数据值{s(f)},f∈N和各个加油站数据可信度{t(S)},S∈M。

(1) Initialization, 初始化各个数据源的可信度{t(S)},S∈M;

(2) Repeat:

(3) Fori< 1 to│M│ do

//循环计算每个数据源

(4) 根据式(3)与式(5)计算数据值的准确度s(f);

(5) End for

(6) 根据所求得的准确度和式(2)更新此轮迭代计算 的数据源可信度t(S)；

(7) Until计算结果收敛;

(8) Return准确度最高的数据值s(f),f∈N作为真实值，数据源的可信度{t(S)},S∈M。

经过上述迭代计算之后，即可求出在此模型下某个用户驾驶车辆车牌号码的真实值。算法的最后一步中，真实值将被用于回填数据库。此过程分为两类，对于缺失的数据，将直接填充TFD算法求得的数据值；对于错误的数据，由于实际数据中存在一个用户会驾驶多辆机动车加油的情况，因此采用比较算法真实值与实际值编辑距离的方式进行填充。编辑距离Levenshtein distance[16]是一种常用的比较文本相似度的算法，设两个字符串为a、b。其长度分别为i、j，则两者编辑距离计算方法如下：

(7)

若两者编辑距离小于某一阈值β，则表明原始数据中的错误值可能是由算法真实值丢失数据产生，应该进行替换。否则二者应该不是同一数据，不应该进行替换。根据对加油站数据的观察，发现数据错误字符个数为1～2个，因此实验中相似度阈值β取3。

至此，算法完成了对所有数据的缺损值填充过程，依此方法可以得到可用性提高的新数据集。

3 实验与结果

3.1 实验配置

为了验证上文中提出的缺损值填充算法的有效性，本次实验使用了真实环境中加油站车辆加油的数据,抽取某一区域的部分数据形成实验数据集。实验机器系统为Windows7 64位，CPU型号为Intel(R) Core(TM) i5-3470 CPU @ 3.20 GHz，内存8 GB，全部代码使用java语言实现，jdk版本为1.8。数据存储使用Oracle 11g。

3.2 加油数据集

数据来源于新疆维吾尔自治区乌鲁木齐市的真实加油站加油数据，该数据集从原始数据库中，抽取市区了31个加油站2017年1月至2017年11月的加油数据总计702 508条。为了保证实验的准确性，去除了数据中部分无效数据，例如整个时间段内加油次数为1次、整个时间段内所有车牌数据均为错误等无法被填充框架处理的数据。经过数据筛选和格式转换等步骤，最终形成了总共659 155条记录的实验数据集。其中完全缺失车牌号字段的数据128 354条，数据缺失率为24.18%。参与运算的完整数据(包含错误数据23 851条)530 801条。其中每条记录主要包括唯一性标识、加油人员身份证号码、加油站编号、车牌号等信息。以某一用户为例，数据集中了不同数据源对其描述数据以及真实情况下加油车辆的电子照片，如表2所示，其中“#”号表示数据缺失，(敏感部分以*代替)。

表2 加油数据集部分数据

本文中采用真值发现常用的正确率[1-13]来衡量最终结果准确性。其计算方式如下：

式中：TP表示算法计算的结果中为真的数据值个数，P表示算法返回的结果集对应取样数据的数量。为更加真实地计算算法的准确性，本文采用真值发现通用的Gold standards[1]准则进行评价，测试数据的具体选择方法为：随机挑选实验数据集中的数据，采用人工的方式在后台数据库中寻找此数据未缺失的真实值，真值以数据库中记录的图片数据为准。

本次实验共分为两个部分，第一部分比较TruthFinder算法中的两个参数ρ和γ对于实验结果的影响，并选择合适的参数进行第二部分实验。第二部分实验中比较Voting算法、原始TruthFinder算法与改进后的TFD算法在实验性能对比及分析。

3.3 参数对结果的影响

为了更好地建模数据源之间的关系，原算法加入了两个参数ρ和γ。其中ρ表示最终结果中本数据源和其他相关数据源对结果的贡献比例，一般取0.5；γ是数据源的独立性参数，为了防止数据源不独立时迭代结果异常的现象产生。不同参数对实验结果的影响如图4所示。

图4 不同γ取值对正确率的影响

上述实验中，固定算法支持度参数ρ为0.5，即数据的准确度计算同时考虑当前数据源结果与其他数据源对本数据的描述，这是大多数真值发现算法所采取的策略。得到参数γ在不同数值下算法最终正确率的情况。参数γ在算法中描述的是不同数据源之间的独立性，即一个数据源的数据是否与其他数据源的数据有关。由实验结果可知，随着γ在参数范围0～1内变化，最终算法正确率虽然有少许波动，但整体来看变化不大。

3.4 实验性能对比及分析

本小节比较了三种算法在实验数据集上的效果。具体包括作为对比的Voting投票算法[17]，即按照少数服从多数的方式选择真值、基于原始未修改的TruthFinder填充算法和本文提出的改进原TruthFinder算法中关于数据值支持度的TFD算法。本实验中所选取的参数均以上述实验中获得最优结果为准：ρ=0.5，γ=0.1。实验结果如表3所示。

表3 不同算法的正确率对比

由实验结果可以看出：基于TFD的缺损值填充方法取得了最高的结果正确率。相较于TruthFinder算法和基于投票的Voting算法有了7%和23%的正确率提高。Voting算法作为处理类似问题的通用计算方法，采用少数服从多数的经典处理策略，并未考虑到不同数据源本身的特点，计算模型过于简单，仅考虑某一数据值的出现次数。虽然在处理离散型多源数据填充问题上有一定的使用价值，但是正确率不高。

基于TFD的填充算法在TruthFinder的基础上改进了其支持度的计算规则，最终在正确率上有一定的提高，说明在加油站数据中，相较于余弦相似度这种在文本相关性方面较为优势的算法，离散的0-1相似度更具有效性。TFD算法将车牌之间的支持度离散化处理，因此在实际实验中获得了比TruthFinder算法更好的效果。

如图5所示，算法在最开始的三轮迭代中正确率有明显变化，且变化率不断降低，之后正确率稳定，表明迭代已收敛。而且，即使是在首轮迭代中，算法的正确率依然有0.866，可见，在一轮迭代后其结果已有一定的可用性。基于TFD的缺损值填充算法在处理数据量较大的数据集时，也可以在较短的时间内得到令人满意的结果。

图5 算法正确率随迭代次数的变化

4 结 语

针对于多源离散型分类数据缺损值填充问题，本文提出了一种基于改进的TFD算法进行填充的思路。该方法使用真值发现，迭代计算各个数据源的可信度和数据值的准确度，使用改进的二值相似度解决了数据之间支持度的计算问题，以最终迭代收敛时的计算结果作为缺损值填充的备选值。最后通过在实际数据集上的实验验证了这种方法的有效性。本文为解决此类问题提供了一种全新的解决思路。但是真值发现算法发展至今已有大量的研究进展[18-20]，本文所使用的算法只是其中较为简单易于理解的一种。由于采用迭代计算的方式，其时间效率不高。其次，由于算法的局限性[21]，仅能处理单真值的问题。在后期对填充结果分析的过程中，发现小部分数据存在多真值的现象，导致算法填充结果不准确。因此，后续工作中将对真值发现问题进行更深入的研究，考虑采用不同的运算模型，提高在实际数据上的准确度和时间效率。