基于塊嵌套循環(huán)的海洋大數(shù)據質量檢驗方案選擇算法＊

黃冬梅，陳 括，王振華，施黎莉

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

1 引言

隨著世界各國對海洋資源探索和海洋事業(yè)發(fā)展的日益重視，海洋信息化成為全面了解和研究海洋的重要途徑之一。目前，海洋數(shù)據的獲取手段多種多樣，海洋數(shù)據的“量”急劇增長，同時海洋數(shù)據的“類”多樣化發(fā)展，可以說，海洋數(shù)據已逐漸成為大數(shù)據的典范。海洋大數(shù)據為海洋環(huán)境的監(jiān)測、海洋資源的探測以及海洋災害的預警預報等研究提供了重要的信息資源，但海洋大數(shù)據的“質”問題也成為大家關注的重點。

以某海域海洋養(yǎng)殖區(qū)監(jiān)測為例。該海域基礎數(shù)據包括經度、緯度以及海底地形；海洋環(huán)境要素數(shù)據包括溫、鹽、浪、流、潮等，要素數(shù)據采集周期為10分鐘；海洋養(yǎng)殖區(qū)域屬性數(shù)據包括養(yǎng)殖類型、養(yǎng)殖面積、養(yǎng)殖單位等。在海洋數(shù)據的整個生命周期中，從采集、傳輸、處理到應用，都有可能使數(shù)據產生質量問題，因此在使用數(shù)據前，需對該批海洋大數(shù)據進行質量檢驗。但是，傳統(tǒng)的數(shù)據質量檢驗方法不能直接應用于海洋大數(shù)據的質量檢驗，其原因在于：（1）海洋數(shù)據屬于空間數(shù)據的一類，其空間位置數(shù)據與屬性數(shù)據具有對應關系；（2）海洋數(shù)據采集周期為10分鐘，因此海洋數(shù)據具有動態(tài)性特征，且其量急劇積累；（3）由于各環(huán)境要素的獲取手段不同，其數(shù)據格式、精度要求等各不相同。

本文的主要貢獻有：（1）利用超幾何分布模型給出了不同質量檢驗方案的殘差集合；（2）基于skyline的塊嵌套循環(huán)BNL（Block-Nested-Loops）算法選擇出最優(yōu)質量檢驗方案；（3）針對多源、多類、多維以及動態(tài)性海洋大數(shù)據，快速確定其質量檢驗的優(yōu)化方案。

2 相關工作

質量檢驗是從一批海洋數(shù)據中隨機抽取一定量的數(shù)據進行檢驗，來判斷該批數(shù)據質量是否達到要求的精度［1］。針對數(shù)據質量的問題，文獻［2］通過定義數(shù)據質量標準，建立了數(shù)據質量管理閉環(huán)過程。文獻［3］從數(shù)據的準確性、完整性、代表性以及可比性方面對數(shù)據質量進行控制，同時用統(tǒng)計抽樣的方法對已有數(shù)據進行檢驗。文獻［4］將數(shù)據質量衡量指標分成客觀的數(shù)據質量指示器和主觀的數(shù)據質量參數(shù)，用戶根據需要選擇不同指標對數(shù)據工程中的數(shù)據進行衡量。文獻［5］將數(shù)據質量評估指標分成四類：內在質量和可訪問質量、上下文質量、表達質量，每個類又細分成具體的維度來評估，拓寬數(shù)據質量的認識。文獻［6］采取取樣計算的方法，對關系數(shù)據庫數(shù)據質量的兩個重要維度即精確度和完整度進行量化，并具體分析了數(shù)據質量對四種常見的關系代數(shù)操作（選擇、投影、笛卡爾積、連接）的影響。

以上的方法研究都是基于傳統(tǒng)數(shù)據的質量檢驗方法，海洋大數(shù)據不同于傳統(tǒng)數(shù)據，有其自身的特點：（1）海洋數(shù)據獲取難度大、成本高，因此大部分的海洋數(shù)據質量檢驗具有不可逆性；（2）海洋數(shù)據涵蓋區(qū)域廣、時空分布不均勻，因此如何根據海洋數(shù)據的不同批量范圍，快速給出其質量檢驗的優(yōu)化方案是海洋大數(shù)據質量檢驗的關鍵問題。針對海洋數(shù)據質量的檢驗研究較少，文獻［7］介紹了利用極值控制方法、檢驗法、迪克遜（Dixon）檢驗法等方法對海洋站的數(shù)據質量進行控制。文獻［8］針對GPS浮標側波數(shù)據的間斷現(xiàn)象，采用了插值法和后續(xù)值前移的接續(xù)方法對海洋數(shù)據進行質量控制。文獻［9］以海流觀測技術LADCP（Lowered Acoustic Doppler Current Profiler）獲取的流速信息為例，通過實驗說明了對流速信息進行質量控制前后的不同結果，并闡述了對海洋數(shù)據進行質量控制的重要性。這些學者針對不同類型的海洋數(shù)據進行了質量檢驗研究，但是面對類型復雜的海洋大數(shù)據時，如何確立其質量檢驗方案并對其質量進行控制的相關研究較少。

近年來skyline計算［10］受到了眾多國內外研究者的關注，文獻［11］將skyline計算應用在集中靜態(tài)環(huán)境中，并利用空間索引技術快速進行skyline查詢。文獻［12］基于簇結構的思想提出了一種新的skyline算法，并將該算法用于無線傳感器網絡。skyline查詢是一個多目標決策問題，可以使同一問題中的幾個不同的因素達到平衡，為用戶做出更好的決策。

本文采用傳統(tǒng)的百分比方法給出待檢驗海洋大數(shù)據的質量檢驗方案集，并根據超幾何分布模型計算所有質量檢驗方案的殘差集合，運用skyline的塊嵌套循環(huán)算法對已有的質量檢驗方案集進行優(yōu)化選擇。通過平衡檢驗精度和費用，快速給出該批海洋大數(shù)據的最優(yōu)質量檢驗方案。

3 海洋大數(shù)據質量檢驗方案和方案殘差

3.1 海洋大數(shù)據質量檢驗方案

將海洋數(shù)據的質量檢驗記為S（N，n，c），其中，N為批量，即待檢驗的海洋數(shù)據的總體數(shù)量；n為樣本量，即從批量中抽取的用來檢查的海洋數(shù)據樣本數(shù)量；c為接收數(shù)，即樣本中允許出現(xiàn)的海洋數(shù)據不合格數(shù)的最大值。從待檢驗海洋數(shù)據檢驗批N中抽取n個樣本，逐一檢查其質量；記海洋樣本數(shù)據中的不合格品數(shù)為d，若海洋數(shù)據不合格數(shù)小于或等于接收數(shù)c，則該批海洋數(shù)據達到了精度要求，待檢驗海洋數(shù)據被認為未發(fā)現(xiàn)質量問題，反之則說明該批海洋數(shù)據存在質量問題。

本文使用檢驗批的不合格品率來衡量海洋數(shù)據質量水平的標準，用海洋數(shù)據平均質量水平來衡量數(shù)據的平均質量。海洋數(shù)據不合格品率的計算如公式（1）所示，海洋數(shù)據平均質量水平的計算如公式（2）所示：

其中，di為對第i批海洋數(shù)據樣本逐個檢查時，發(fā)現(xiàn)的不合格品數(shù)據的個數(shù)；n為第i檢驗批海洋數(shù)據中抽取的樣本量；m為待檢驗海洋數(shù)據批量。

3.2 海洋大數(shù)據質量方案殘差

針對每一批待檢驗海洋數(shù)據，其存在一個接收質量限 AQL［13］（Acceptance Quality Level）和極限質量限 LQL［14］（Limit Quality Level）。接收質量限AQL是當一批連續(xù)序列被提交驗收檢驗時，可允許的最差過程平均質量水平，它是可以接收和拒絕接收的過程平均界限值。在對一批海洋數(shù)據質量檢驗前，先根據所需數(shù)據質量要求給出該次檢驗過程的AQL值，即檢驗批可允許的不合格品率p。極限質量限LQL指為了抽樣檢驗，限制在某一低接收概率的質量水平，它是在抽樣檢驗中對不應接收的批質量的最小值。

基于超幾何分布模型［15］，質量檢驗方案的接收概率記為L（）p：

因此，基于AQL的接收質量限接收概率殘差Ea和LQL的極限質量限接收概率殘差Eb由下式給出：

其中，α為生產方風險，當海洋數(shù)據的質量達到質量接收限AQL，其接收概率L（pa）應在（1－α）附近，Ea為接收質量限接收概率殘差；β為使用方風險，當質量水平劣于極限質量限LQL，其接收概率L（pb）應在β附近，Eb為極限質量限接收概率殘差。

4 海洋大數(shù)據質量檢驗方案的優(yōu)化選擇算法

塊嵌套循環(huán)BNL［16］是對具有兩類屬性值的數(shù)據點的兩兩比較方法的一種優(yōu)化算法，其本質是多目標決策算法。本文采用百分比質量檢驗方案對海洋數(shù)據的質量檢驗方案S（N，n，c）的數(shù)據進行檢驗，運用BNL對質量檢驗方案中的接收質量限接收概率殘差Ea和極限質量限接收概率殘差Eb進行優(yōu)化選擇，在兼顧生產方風險和使用方風險的條件下，選出最優(yōu)化的質量檢驗方案。

輸入：待檢驗的海洋數(shù)據集O，｜O｜＝N；

輸出：最優(yōu)的海洋大數(shù)據質量檢驗方案S（N，n，c）。

步驟1 求海洋大數(shù)據質量檢驗方案集Q，｜Q｜＝N2；

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

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

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

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

｝

步驟3 將殘差集Ea和Eb作為輸入，調用skyline的塊嵌套循環(huán)算法，計算出最優(yōu)解（ak，bk）（0＜k≤｜Ea｜）；

步驟4 根據（ak，bk）從方案集Q中選出最優(yōu)方案S（N，n，c）。

算法分析：在該算法中，求海洋大數(shù)據質量檢驗方案集Q的時間復雜度為O（N2）；求殘差集的時間復雜度為O（N2）；塊嵌套循環(huán)算法的時間復雜度為O（N2）；從方案集Q中選出最優(yōu)方案的時間復雜度為O（N）。因此，該算法的時間復雜度為O（N2）。

5 實驗分析

5.1 實驗數(shù)據

Figure 1 Breed area distribution chart圖1 養(yǎng)殖區(qū)域分布圖

以如圖1所示的某海域部分養(yǎng)殖區(qū)域監(jiān)測站點數(shù)據為例，來檢驗本文所提方法的可行性。其中，研究區(qū)域內包括監(jiān)測點位數(shù)據N為1 392個，其每一點位包括三大類數(shù)據，分別是空間位置數(shù)據、海洋要素數(shù)據和養(yǎng)殖信息數(shù)據，如表1所示（因需要將位置數(shù)據及典型要素數(shù)據隱藏）。

采用四種不同的抽樣比f對海洋數(shù)據進行質量檢驗，對于該批海洋數(shù)據的批量N，樣本量n分別取批量N 的5%、10%、15%和20%，接收數(shù)c取不同的值，表2所列為海洋數(shù)據的百分比質量檢驗方案。

5.2 質量檢驗方案優(yōu)化選擇

根據以上四種不同的百分比抽樣方法，利用超幾何分布模型，根據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 養(yǎng)殖區(qū)分布屬性信息

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），其中接收數(shù)c從0開始取值，依次以1遞增；當接收數(shù)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）。當接收數(shù)c大于或等于10時，AQL的接受概率L（Pa）約等于1，即無論待檢驗數(shù)據質量如何，采用該方案對其進行質量檢驗，均可判為合格數(shù)據，該現(xiàn)象不利于使用方。所以當抽樣比為f＝10%，接收數(shù)c大于或等于10的質量檢驗方案，不予考慮。同理，（3）當抽樣比為f＝15%，質量檢驗方案樣本量n為208，接收數(shù)c大于或等于13的質量檢驗方案，不予考慮。（4）當抽樣比為f＝20%，質量檢驗方案樣本量n為278，接收數(shù)c大于或等于15的質量檢驗方案，不予考慮。

利用BNL算法對不同抽樣比產生的海洋數(shù)據質量檢驗方案進行選擇。首先將海洋數(shù)據抽樣方案 殘 差 點 的 集 合 定 義 為 S ＝ ｛S1（Ea1，Eb1），S2（Ea2，Eb2），…，Sn（Ean，Ebn）｝，對 所 有 質 量 檢 驗方案的殘差點集兩兩交互比較，從而篩選出平衡兩殘差的最優(yōu)解，即選出最優(yōu)化的質量檢驗方案，在保證使用方精度的同時考慮生產方的風險。

抽樣比為f＝5%時，海洋數(shù)據質量檢驗方案為S（1 392，69，c）的接收概率殘差如圖2所示。

Figure 2 Distribution of 5%quality inspection scheme residuals圖2 5%質量檢驗方案殘差集合

圖2 給出了抽樣比為5%時，各海洋數(shù)據質量檢驗方案的殘差集合，其中，橫坐標表示接收質量限接收概率殘差Ea，縱坐標表示極限質量限接收概率殘差Eb。由圖2可以看出，質量檢驗方案S（1 392，69，3）的殘差點S13（0.004 0，0.028 3）完全支配其它質量檢驗方案殘差點，即該方案的接收質量限接受概率殘差Ea和極限質量限接收概率殘差Eb都優(yōu)于其它方案的殘差。故此，質量檢驗方案S（1 392，69，3）為抽樣比為5%時的最優(yōu)化海洋數(shù)據質量檢驗方案。

抽樣比為f＝10%時，海洋數(shù)據質量檢驗方案為S（1 392，139，c）的接收概率殘差如圖3所示。

Figure 3 Distribution of 10%quality inspection scheme residuals圖3 10%質量檢驗方案殘差集合

圖3 給出了抽樣比為10%時，各海洋數(shù)據質量檢驗方案的殘差集合。由圖3可以看出，質量檢驗方案為S（1 392，139，c）的殘差點S25（0.002 8，0.096 9）和S26（0.033 3，0.091 1）完全支配這組質量檢驗方案其它殘差點，但是這兩個點并不相互支配，即這兩個方案的接收質量限接收概率殘差Ea和極限質量限接收概率殘差Eb都優(yōu)于其它方案的殘差，而這兩個方案之間各有優(yōu)劣。因此，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）為這組質量檢驗方案的最優(yōu)解。

同樣的方法可以得出在抽樣比為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%這兩組質量檢驗方案的最優(yōu)解。

然后將不同百分比的質量檢驗方案最優(yōu)解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 不同百分比最優(yōu)質量檢驗方案接收概率值和殘差

Figure 4 Distribution of different percentage quality inspection scheme residuals圖4 不同百分比最優(yōu)質量檢驗方案殘差點集合

圖4 給出了不同百分比最優(yōu)質量檢驗方案殘差點集合，通過BNL算法對不同百分比最優(yōu)質量檢驗方案的殘差點進行比較，可以得出質量檢驗方案S（1 392，139，5）的殘差點S25（0.002 8，0.096 9）完全支配其他殘差點，即該方案的接收質量限接收概率殘差Ea和極限質量限接收概率殘差Eb都優(yōu)于其它方案的殘差。因此，S25（0.002 8，0.096 9）為不同百分比最優(yōu)質量檢驗方案的殘差點的skyline集合點，其所對應的質量檢驗方案：f＝10%，n＝139，c＝5為這批N＝1 392的最優(yōu)質量檢驗方案，即S（1 392，139，5）為不同百分比的最優(yōu)質量檢驗方案。

6 結束語

本文將skyline思想引入海洋數(shù)據質量優(yōu)化檢驗方案的選擇。運用超幾何分布模型求出殘差并通過塊嵌套循環(huán)算法選出最優(yōu)的海洋數(shù)據質量檢驗方案，實驗驗證了該方法的可行性，從而實現(xiàn)了快速海洋數(shù)據最優(yōu)質量檢驗方案的選擇，完善了海洋數(shù)據質量檢驗理論體系。

［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］ 韓京宇，徐立臻，董逸生.數(shù)據質量研究綜述［J］.計算機科學，2008，35（2）：1-12.

［2］ 包陽，齊璇.大型軟件系統(tǒng)數(shù)據質量問題研究［J］.計算機工程與設計，2011，32：963.

［3］ 徐自舟，宋德瑞.海洋環(huán)境監(jiān)測數(shù)據質量計算機控制方法研究［J］.海洋環(huán)境科學，2009，28（3）：329-334.

［7］ 史靜濤，周智海.海洋站數(shù)據質量控制技術探討［J］.海洋技術，2011，30（1）：114-117.

［8］ 張鎖平.單點GPS浮標測波方法與數(shù)據質量控制研究［J］.海洋技術，2008，27（3）：15-18.

［9］ 謝玲玲，熊學軍，楊慶軒.LADCP配置文件和數(shù)據質量控制的參數(shù)設定［J］.海洋技術，2009，28（1）：19-23.

［10］ 朱琳，周水庚.Skyline計算研究綜述［J］.計算機工程與應用，2008，44（6）：160-165.

［12］ 王艷杰.基于數(shù)據流的skyline計算及應用研究［D］.鎮(zhèn)江：江蘇大學，2011.

［13］ 王振華.空間數(shù)據質量抽樣檢驗與控制的理論、方法和應用［D］.上海：同濟大學，2011.

［15］ Wetherill.抽樣檢驗與質量控制［M］.于善奇，譯.北京：北京大學出版社，1991.