基于块嵌套循环的海洋大数据质量检验方案选择算法＊

黄冬梅，陈 括，王振华，施黎莉

（上海海洋大学信息学院，上海201306）

1 引言

随着世界各国对海洋资源探索和海洋事业发展的日益重视，海洋信息化成为全面了解和研究海洋的重要途径之一。目前，海洋数据的获取手段多种多样，海洋数据的“量”急剧增长，同时海洋数据的“类”多样化发展，可以说，海洋数据已逐渐成为大数据的典范。海洋大数据为海洋环境的监测、海洋资源的探测以及海洋灾害的预警预报等研究提供了重要的信息资源，但海洋大数据的“质”问题也成为大家关注的重点。

以某海域海洋养殖区监测为例。该海域基础数据包括经度、纬度以及海底地形；海洋环境要素数据包括温、盐、浪、流、潮等，要素数据采集周期为10分钟；海洋养殖区域属性数据包括养殖类型、养殖面积、养殖单位等。在海洋数据的整个生命周期中，从采集、传输、处理到应用，都有可能使数据产生质量问题，因此在使用数据前，需对该批海洋大数据进行质量检验。但是，传统的数据质量检验方法不能直接应用于海洋大数据的质量检验，其原因在于：（1）海洋数据属于空间数据的一类，其空间位置数据与属性数据具有对应关系；（2）海洋数据采集周期为10分钟，因此海洋数据具有动态性特征，且其量急剧积累；（3）由于各环境要素的获取手段不同，其数据格式、精度要求等各不相同。

本文的主要贡献有：（1）利用超几何分布模型给出了不同质量检验方案的残差集合；（2）基于skyline的块嵌套循环BNL（Block-Nested-Loops）算法选择出最优质量检验方案；（3）针对多源、多类、多维以及动态性海洋大数据，快速确定其质量检验的优化方案。

2 相关工作

质量检验是从一批海洋数据中随机抽取一定量的数据进行检验，来判断该批数据质量是否达到要求的精度［1］。针对数据质量的问题，文献［2］通过定义数据质量标准，建立了数据质量管理闭环过程。文献［3］从数据的准确性、完整性、代表性以及可比性方面对数据质量进行控制，同时用统计抽样的方法对已有数据进行检验。文献［4］将数据质量衡量指标分成客观的数据质量指示器和主观的数据质量参数，用户根据需要选择不同指标对数据工程中的数据进行衡量。文献［5］将数据质量评估指标分成四类：内在质量和可访问质量、上下文质量、表达质量，每个类又细分成具体的维度来评估，拓宽数据质量的认识。文献［6］采取取样计算的方法，对关系数据库数据质量的两个重要维度即精确度和完整度进行量化，并具体分析了数据质量对四种常见的关系代数操作（选择、投影、笛卡尔积、连接）的影响。

以上的方法研究都是基于传统数据的质量检验方法，海洋大数据不同于传统数据，有其自身的特点：（1）海洋数据获取难度大、成本高，因此大部分的海洋数据质量检验具有不可逆性；（2）海洋数据涵盖区域广、时空分布不均匀，因此如何根据海洋数据的不同批量范围，快速给出其质量检验的优化方案是海洋大数据质量检验的关键问题。针对海洋数据质量的检验研究较少，文献［7］介绍了利用极值控制方法、检验法、迪克逊（Dixon）检验法等方法对海洋站的数据质量进行控制。文献［8］针对GPS浮标侧波数据的间断现象，采用了插值法和后续值前移的接续方法对海洋数据进行质量控制。文献［9］以海流观测技术LADCP（Lowered Acoustic Doppler Current Profiler）获取的流速信息为例，通过实验说明了对流速信息进行质量控制前后的不同结果，并阐述了对海洋数据进行质量控制的重要性。这些学者针对不同类型的海洋数据进行了质量检验研究，但是面对类型复杂的海洋大数据时，如何确立其质量检验方案并对其质量进行控制的相关研究较少。

近年来skyline计算［10］受到了众多国内外研究者的关注，文献［11］将skyline计算应用在集中静态环境中，并利用空间索引技术快速进行skyline查询。文献［12］基于簇结构的思想提出了一种新的skyline算法，并将该算法用于无线传感器网络。skyline查询是一个多目标决策问题，可以使同一问题中的几个不同的因素达到平衡，为用户做出更好的决策。

本文采用传统的百分比方法给出待检验海洋大数据的质量检验方案集，并根据超几何分布模型计算所有质量检验方案的残差集合，运用skyline的块嵌套循环算法对已有的质量检验方案集进行优化选择。通过平衡检验精度和费用，快速给出该批海洋大数据的最优质量检验方案。

3 海洋大数据质量检验方案和方案残差

3.1 海洋大数据质量检验方案

将海洋数据的质量检验记为S（N，n，c），其中，N为批量，即待检验的海洋数据的总体数量；n为样本量，即从批量中抽取的用来检查的海洋数据样本数量；c为接收数，即样本中允许出现的海洋数据不合格数的最大值。从待检验海洋数据检验批N中抽取n个样本，逐一检查其质量；记海洋样本数据中的不合格品数为d，若海洋数据不合格数小于或等于接收数c，则该批海洋数据达到了精度要求，待检验海洋数据被认为未发现质量问题，反之则说明该批海洋数据存在质量问题。

本文使用检验批的不合格品率来衡量海洋数据质量水平的标准，用海洋数据平均质量水平来衡量数据的平均质量。海洋数据不合格品率的计算如公式（1）所示，海洋数据平均质量水平的计算如公式（2）所示：

其中，di为对第i批海洋数据样本逐个检查时，发现的不合格品数据的个数；n为第i检验批海洋数据中抽取的样本量；m为待检验海洋数据批量。

3.2 海洋大数据质量方案残差

针对每一批待检验海洋数据，其存在一个接收质量限 AQL［13］（Acceptance Quality Level）和极限质量限 LQL［14］（Limit Quality Level）。接收质量限AQL是当一批连续序列被提交验收检验时，可允许的最差过程平均质量水平，它是可以接收和拒绝接收的过程平均界限值。在对一批海洋数据质量检验前，先根据所需数据质量要求给出该次检验过程的AQL值，即检验批可允许的不合格品率p。极限质量限LQL指为了抽样检验，限制在某一低接收概率的质量水平，它是在抽样检验中对不应接收的批质量的最小值。

基于超几何分布模型［15］，质量检验方案的接收概率记为L（）p：

因此，基于AQL的接收质量限接收概率残差Ea和LQL的极限质量限接收概率残差Eb由下式给出：

其中，α为生产方风险，当海洋数据的质量达到质量接收限AQL，其接收概率L（pa）应在（1－α）附近，Ea为接收质量限接收概率残差；β为使用方风险，当质量水平劣于极限质量限LQL，其接收概率L（pb）应在β附近，Eb为极限质量限接收概率残差。

4 海洋大数据质量检验方案的优化选择算法

块嵌套循环BNL［16］是对具有两类属性值的数据点的两两比较方法的一种优化算法，其本质是多目标决策算法。本文采用百分比质量检验方案对海洋数据的质量检验方案S（N，n，c）的数据进行检验，运用BNL对质量检验方案中的接收质量限接收概率残差Ea和极限质量限接收概率残差Eb进行优化选择，在兼顾生产方风险和使用方风险的条件下，选出最优化的质量检验方案。

输入：待检验的海洋数据集O，｜O｜＝N；

输出：最优的海洋大数据质量检验方案S（N，n，c）。

步骤1 求海洋大数据质量检验方案集Q，｜Q｜＝N2；

步骤2 for（i＝1；i≤N；i＋＋ ）｛

利用公式（5）求残差ai，并将其放入残差集Ea中；

利用公式（6）求残差bi，并将其放入残差集Eb中；

／／利用公式（5）和（6）求残差集Ea和Eb；

｝

步骤3 将残差集Ea和Eb作为输入，调用skyline的块嵌套循环算法，计算出最优解（ak，bk）（0＜k≤｜Ea｜）；

步骤4 根据（ak，bk）从方案集Q中选出最优方案S（N，n，c）。

算法分析：在该算法中，求海洋大数据质量检验方案集Q的时间复杂度为O（N2）；求残差集的时间复杂度为O（N2）；块嵌套循环算法的时间复杂度为O（N2）；从方案集Q中选出最优方案的时间复杂度为O（N）。因此，该算法的时间复杂度为O（N2）。

5 实验分析

5.1 实验数据

Figure 1 Breed area distribution chart图1 养殖区域分布图

以如图1所示的某海域部分养殖区域监测站点数据为例，来检验本文所提方法的可行性。其中，研究区域内包括监测点位数据N为1 392个，其每一点位包括三大类数据，分别是空间位置数据、海洋要素数据和养殖信息数据，如表1所示（因需要将位置数据及典型要素数据隐藏）。

采用四种不同的抽样比f对海洋数据进行质量检验，对于该批海洋数据的批量N，样本量n分别取批量N 的5%、10%、15%和20%，接收数c取不同的值，表2所列为海洋数据的百分比质量检验方案。

5.2 质量检验方案优化选择

根据以上四种不同的百分比抽样方法，利用超几何分布模型，根据AQL和LQL对应的不合格品率值，不合格品率分别取Pa＝0.02，Pb＝0.1，计算得出接收概率值L（Pa）和L（Pb），以及其对应的残差值Ea和Eb。百分比抽样方案的接收概率值和残差如表3所示。

Table 1 Attribute information of the breed area distribution表1 养殖区分布属性信息

Table 2 List of the percentage sampling plan表2 百分比抽样方案列表

Table 3 Accept probability and residual of the percentage sampling plan表3 百分比质量检验方案接收概率值和残差

由表3可以看出：

（1）抽样比f＝5%时，质量检验方案的样本量n为69，质量检验方案为S（1 392，69，c），其中接收数c从0开始取值，依次以1递增；当接收数c大于或等于4时，其极限质量限接收概率残差小于0，如表中方案S（1 392，69，4）、S（1 392，69，5）、S（1 392，69，6）、S（1 392，69，7）的极限质量限接收概率残差分别为－0.062 1、－0.195 6，－0.359 9、－0.517 0，此时所有方案只顾及了生产方风险，但没有考虑使用方风险，故此舍去。（2）当抽样比为f＝10%，质量检验方案的样本量n为139，质量检验方案为S（1 392，139，c）。当接收数c大于或等于10时，AQL的接受概率L（Pa）约等于1，即无论待检验数据质量如何，采用该方案对其进行质量检验，均可判为合格数据，该现象不利于使用方。所以当抽样比为f＝10%，接收数c大于或等于10的质量检验方案，不予考虑。同理，（3）当抽样比为f＝15%，质量检验方案样本量n为208，接收数c大于或等于13的质量检验方案，不予考虑。（4）当抽样比为f＝20%，质量检验方案样本量n为278，接收数c大于或等于15的质量检验方案，不予考虑。

利用BNL算法对不同抽样比产生的海洋数据质量检验方案进行选择。首先将海洋数据抽样方案 残 差 点 的 集 合 定 义 为 S ＝ ｛S1（Ea1，Eb1），S2（Ea2，Eb2），…，Sn（Ean，Ebn）｝，对 所 有 质 量 检 验方案的残差点集两两交互比较，从而筛选出平衡两残差的最优解，即选出最优化的质量检验方案，在保证使用方精度的同时考虑生产方的风险。

抽样比为f＝5%时，海洋数据质量检验方案为S（1 392，69，c）的接收概率残差如图2所示。

Figure 2 Distribution of 5%quality inspection scheme residuals图2 5%质量检验方案残差集合

图2 给出了抽样比为5%时，各海洋数据质量检验方案的残差集合，其中，横坐标表示接收质量限接收概率残差Ea，纵坐标表示极限质量限接收概率残差Eb。由图2可以看出，质量检验方案S（1 392，69，3）的残差点S13（0.004 0，0.028 3）完全支配其它质量检验方案残差点，即该方案的接收质量限接受概率残差Ea和极限质量限接收概率残差Eb都优于其它方案的残差。故此，质量检验方案S（1 392，69，3）为抽样比为5%时的最优化海洋数据质量检验方案。

抽样比为f＝10%时，海洋数据质量检验方案为S（1 392，139，c）的接收概率残差如图3所示。

Figure 3 Distribution of 10%quality inspection scheme residuals图3 10%质量检验方案残差集合

图3 给出了抽样比为10%时，各海洋数据质量检验方案的残差集合。由图3可以看出，质量检验方案为S（1 392，139，c）的残差点S25（0.002 8，0.096 9）和S26（0.033 3，0.091 1）完全支配这组质量检验方案其它残差点，但是这两个点并不相互支配，即这两个方案的接收质量限接收概率残差Ea和极限质量限接收概率残差Eb都优于其它方案的残差，而这两个方案之间各有优劣。因此，S25（0.002 8，0.096 9）和 S26（0.033 3，0.091 1）同 为skyline集合点，其所对应的S（1 392，139，5）和S（1 392，139，6）为这组质量检验方案的最优解。

同样的方法可以得出在抽样比为15%和20%的两组质量检验方案中，质量检验方案为S（1 392，208，c）的 残 差 点 S37（0.004 1，0.099 9）、S38（0.033 7，0.099 6）以及质量检验方案 S（1 392，278，c）的残差点S48（0.037 2，0.100 0）、S49（0.012 8，0.100 0）分别完全支配所在组的其它质量检验方案残差点，因此 S37（0.004 1，0.099 9）、S38（0.033 7，0.099 6）以及 S48（0.037 2，0.100 0）、S49（0.012 8，0.100 0）分别为15%组和20%组的skyline集合点。同理，其所对应的S（1 392，208，7）、S（1 392，208，8）以及S（1 392，278，8）、S（1 392，278，9）也分别为15%和20%这两组质量检验方案的最优解。

然后将不同百分比的质量检验方案最优解S（1 392，69，3）、S（1 392，139，5）、S（1 392，139，6）、S（1 392，208，7）、S（1 392，208，8）、S（1 392，278，8）和S（1 392，278，9）整合进行二次BNL筛选比较，结果如表4和图4所示。

Table 4 Accept probability and residuals of different percentage quality inspection scheme表4 不同百分比最优质量检验方案接收概率值和残差

Figure 4 Distribution of different percentage quality inspection scheme residuals图4 不同百分比最优质量检验方案残差点集合

图4 给出了不同百分比最优质量检验方案残差点集合，通过BNL算法对不同百分比最优质量检验方案的残差点进行比较，可以得出质量检验方案S（1 392，139，5）的残差点S25（0.002 8，0.096 9）完全支配其他残差点，即该方案的接收质量限接收概率残差Ea和极限质量限接收概率残差Eb都优于其它方案的残差。因此，S25（0.002 8，0.096 9）为不同百分比最优质量检验方案的残差点的skyline集合点，其所对应的质量检验方案：f＝10%，n＝139，c＝5为这批N＝1 392的最优质量检验方案，即S（1 392，139，5）为不同百分比的最优质量检验方案。

6 结束语

本文将skyline思想引入海洋数据质量优化检验方案的选择。运用超几何分布模型求出残差并通过块嵌套循环算法选出最优的海洋数据质量检验方案，实验验证了该方法的可行性，从而实现了快速海洋数据最优质量检验方案的选择，完善了海洋数据质量检验理论体系。

［1］ Han Jing－yu，Xu Li-zhen，Dong Yi-sheng.Data quality sur-vey［J］.Computer Science，2008，35（2）：1-120.（in Chinese）

［2］ Bao Yang，Qi Xuan.Large software systems data quality issues［J］.Computer Engineering and Design，2011，32：963.（in Chinese）

［3］ Xu Zi-zhou，Song De-rui.The control method of marine environmental monitoring data quality［J］.Marine Environmental Science，2009，28（3）：329-3340.（in Chinese）

［4］ Wang R Y，Kon H B，Madnick S E.Data quality requirements analysis and modeling［C］∥Proc of the 9th ICDE’93，1993：670-677.

［5］ Rahm E，Do Hong-hai.Data cleaning：Problems and current approaches［J］.IEEE Data Engineering Bulletin，2000，23（4）：3-13.

［6］ Parssian A，Sarkar S，Jacob V S.Assessing information quality for the composite relational operation joins［C］∥Proc of the 7th International Conference on Information Quality，2002：225-237.

［7］ Shi Jing-tao，Zhou Zhi-hai.Ocean station data quality control technology［J］.Marine Technology，2011，30（1）：114-117.（in Chinese）

［8］ Zhang Suo-ping.Single point GPS wave research methods and data quality control［J］.Marine Technology，2008，27（3）：15-18.（in Chinese）

［9］ Xie Ling-ling，Xiong Xue-jun，Yang Qing-xuan.LADCP configuration files and data quality control parameter settings［J］.Marine Technology，2009，28（1）：19-23.（in Chinese）

［10］ Zhu Lin，Zhou Shui-geng.Skyline computation：Survey［J］.Computer Engineering and Applications，2008，44（6）：160-165.（in Chinese）

［11］ Bartolini I，Ciaccia P，Patella M.Efficient sort-based skyline evaluation［J］.ACM Transactions on Database Systems（TODS），2008，33（4）：1-49.

［12］ Wang Yan-jie.Research on skyline computation and application based on data stream［D］.Zhenjiang：Jiangsu University，2011.（in Chinese）

［13］ Wang Zhen-hua.Principle，methods and application of sampling inspection for quality control of geospatial data ［D］.Shanghai：Tongji University，2011.（in Chinese）

［14］ Kuralmani V，Govindaraju K.Modified tables for the selection of double sampling attribute plan indexed by AQL and LQL［J］.Communications in Statistics.Part A：Theory and Methods，1995，24（7）：1897.

［15］ Wetherill.Sampling Inspection and Quality Control［M］.Yu Shan-qi，translation.Beijing：Peiking University Press，1991.（in Chinese）

［16］ Borzsonyi S，Kossmann D，Stocker K.The skyline operator［C］∥Proc of the 17th International Conference on Data Engineering（ICDE），2001：421-430.

附中文参考文献：

［1］ 韩京宇，徐立臻，董逸生.数据质量研究综述［J］.计算机科学，2008，35（2）：1-12.

［2］ 包阳，齐璇.大型软件系统数据质量问题研究［J］.计算机工程与设计，2011，32：963.

［3］ 徐自舟，宋德瑞.海洋环境监测数据质量计算机控制方法研究［J］.海洋环境科学，2009，28（3）：329-334.

［7］ 史静涛，周智海.海洋站数据质量控制技术探讨［J］.海洋技术，2011，30（1）：114-117.

［8］ 张锁平.单点GPS浮标测波方法与数据质量控制研究［J］.海洋技术，2008，27（3）：15-18.

［9］ 谢玲玲，熊学军，杨庆轩.LADCP配置文件和数据质量控制的参数设定［J］.海洋技术，2009，28（1）：19-23.

［10］ 朱琳，周水庚.Skyline计算研究综述［J］.计算机工程与应用，2008，44（6）：160-165.

［12］ 王艳杰.基于数据流的skyline计算及应用研究［D］.镇江：江苏大学，2011.

［13］ 王振华.空间数据质量抽样检验与控制的理论、方法和应用［D］.上海：同济大学，2011.

［15］ Wetherill.抽样检验与质量控制［M］.于善奇，译.北京：北京大学出版社，1991.