基于分布式技術的多級數據真值發現?

基于分布式技術的多級數據真值發現?

呂維新殷軍

（云南電網有限責任公司昆明供電局昆明650200）

為了進一步提升數據管理系統的可靠性和準確性，論文提出了一種基于分布式技術的多級數據真值挖掘發現，消除了級別之間的差異性與獨立性。該方法將數據源的數據相值進行分級，利用級值與真實值相似度定義準確率迭代，避免了同一數據在不同級被抽取時的差異性。通過在分布式技術挖掘算法下，分別計算級值概率和偏離度來判斷多級數據真實值。最后，通過對重疊數據集的實驗說明了論文提出的多級數據真值發現的高效性。

多級數據；真值發現；分布式；數據挖掘

Class NumberTN919.3

1 引言

隨著互聯網計算機的興起，人們越來越依賴于大數據帶來的信息與資源，對于信息的可靠性與準確性提出了更高的要求［1～2］。多級數據在來源上具有復雜性與模糊性，已有的真值算法采用迭代機制來進行真值發現［3］。數據源質量越高，提供的值正確率也越高，與真實值的偏差也越小。來源提供的值與真實值的偏差越小，值質量越高，來源質量也越高，數據源質量和值質量二者相互依賴［4～5］。本研究也采用分布式真值發現迭代算法，用提供值的所有來源準確率衡量值可靠性，選出真實值，用來源提供的所有值與“真實值”的相似度衡量來源可靠性，在迭代過程中一步一步地逼近真實值。

2 多級數據理論

2.1符號說明

為了方便描述多級數據問題，給相關概念及其符號給出詳細解釋［6］，如表1所示。

根據表1對多級數據的定義，s→f表明由來源s提供事實f。f→i表明由事實f來對數據項I進行描述。fi表示事實f的第i級數據集的值，fi→f表示級值fi是事實f的一部分。tf表明由事實f進行描述的數據項的真值，tfi表明由事實f進行描述的數據項的真值在第i級上的體現。一般來說，每一個數據項真值情況有所不同，有的數據項存在多個真值，而有的數據項僅存在單真值，本文將僅對單真值的數據項進行考察。

表1 符號說明

2.2理論分析

對于每一組數據的來源，其在不同的數據項上提供事實，但存在對于不同的數據項覆蓋率不同的情況，一些數據來源能夠提供相當數量的數據項值，而有些數據來源僅能提供少量的數據項值［7］。這和數據來源的質量也有很大的關系。同一個數據來源其自身提供的值可能存在一定的沖突［8］，為了找出真實值，我們需要解決這樣的自沖突。因此，本文研究的問題可簡述如下：1）給定一定集合數據的數據源并提供其事實數據［9］；2）研究如何為不同的數據項篩選出其真實值［10］。基于分布式技術挖掘算法下，本文將給出以下假設來簡化所研究的問題，如下所示。

1）假設每個數據項僅存在單真值。當同一個數據項存在多個事件發生沖突時，必定能找到唯一的真值。

2）數據來源提供的數據相互獨立，對于不同數據源之間存在的聯系情況并不在考慮的范圍之內。

3）每個數據項之間是相互獨立的，對于不同的數據項的事實，其為真的概率相互之間沒有關聯。

4）數據項的級別之間互不干擾相互獨立，不同級值為真的概率相互之間沒有關聯。

分布式技術挖掘算法是基于迭代的思想而實現的［11］。在上述的四個假設之下，每一循環的迭代過程主要包含下述兩個主要的關鍵步驟：

1）針對每一個數據項的值進行分級，并對每件事實f進行拆分，將其劃分為多條級值{f1,f2,…,fL(f)}，根據數據項所提供的fi(1≤i≤L(f))的來源的配適率得出各個級值fi獲得的投票，同時以各條級值fi獲得的投票為依據來獲得完整的關于事實f的投票，再篩選出得到投票數最高的數據項的值作為“真實值”。

2）演繹出事實f的級值fi(1≤i≤L(f))以及其與“真值”對應的級值tfi的相似程度，并以每級的相似度為依據來計算出完整事件事實f以及“真值”tf的相似程度，并根據所選數據來源的配適率來對下一輪的數據處理進行迭代。

3 分布式真值發現

3.1級值計算

本文借鑒貝葉斯公式計算fi，即P(fitrue|ψ(fi))，其中fi為計算概率為真的公式，并從中篩選出表示fi概率為真的投票值大小的算法并得出fi所獲得的投票［5］。根據上述的假設3），事實fi為真的概率僅僅與f所描述的提供真值的數據項來源相關。再根據上述的假設4），fi為真的概率僅僅與f所描述的數據項第i級值分布相關。|S(fi)|表示提供特定極值i的事實f來源的數量，其中絕對值表明該數據集合的大小。|S∧(fi)|表示提供特定極值i的事實f來源的數量，即提供錯誤極值的來源數量。利用|S∨(fi)|表示|S(fi)|∪|S∧(fi)|的集合，數據項來源的配適率由A(s)表示。某個數據項來源錯誤的概率在本文中用Pop(f)表示，簡寫為P(fi)，完整值的投票數由C(fi)表示，通過推算得到下式：

本文利用上式來計算提供不同質量的數據來源的不同極值i的事實fi的總投票數，其總的投票數量越高，fi為真的概率則越高。

3.2完整值計算

本文將采取按照級別的高低乘以權重再疊加的方法來計算出完整值的投票數。數據項分級越高則在決定完整值的投票數時其地位越發重要也越有話語權，規定級別從1開始，隨著數值的增大其代表的級別也越高［12］。當數據項的數值與地理信息位置相聯系的時候，其級別數越高，與其對應的地理位置的范圍就越廣，同樣，當數據項的數值與長度、重量、距離等相聯系的時候，其級別越高，相對應的等級也就越大。當一個數據項的數值為數字時，其級別越大越具有發言權，也就是數值的大小最大程度地取決于其數量等級較高的數字，在信息位置上此原理同等適用，級別越高的數值決定基本的位置的范圍。這樣的原理運用到完整值的投票數之上，則其等級越高，權重越大。

根據每個級值獲得的投票數和相對應的影響因子相乘并進行累加，可計算出完整值的投票數。假定數據項級別i的權重為1，各個級別之間的權重比均為α，同時設α＞1，可得到如下表達式：

根據上式，依據所選范圍內的所有數據項的事實f完整值投票數篩選出每一個數據項的“真值”。依據表1中的假設1），同一個數據項存在多個事件發生沖突時，必定能找到唯一的真值。因此可根據數據項上投票數目最多的原則選擇對應的事實f作為真值。

3.3真值計算

評判數據來源提供數據質量的標準是，數據來源所提供的值同“真值”之間的相似程度，兩者之間的相似程度越高則數據來源提供值的質量則越高，也就是說當數據來源所提供的值同“真值”之間的相似程度較低時，數據來源提供值的質量則越低。本文利用來源所提供的值同“真值”之間的相似程度來表示來源提供值的質量［13］。當數據項中來源提供值的質量越高，則其配適率越高。數據來源在它所提供了值的所有的數據項上的綜合表現會影響到來源配適率的評價。為了防止極端的數據項值兩極分化帶來的數據波動從而影響到數據配適率的計算，本文將來源所提供的值同“真值”之間的相似程度的平均值作為來源的配適率，如式（3）所示。在計算過程中將來源所提供的值同“真值”之間的相似程度的演算過程劃分為兩個步驟：1）計算出來源所提供的值同“真值”之間的相似程度；2）按照級別的高低乘以權重再疊加計算出完整值同真值之間的相似程度。假設相鄰的兩個級別之間的影響因子之比均為β，同時假定β＞1，所有的權重系數之和為1，由此可得：

3.4算法描述

input：對于來自每個數據源的事實的集合F劃分為若干個數據源S。

output：真值集合與數據源的質量指標。

Letα=2.5，β=1.5，A(s)=0.6根據（1）式計算βl

for eachs∈S//初始化數據源質量

end

repeat

for eachi=I//根據（16）式計算βl

for eachf,f→i//根據（7）、（8）式計算第i個數據項事實的投票數

for eachfi→f//根據（9）式計算事實的投票數

end//選出數據項i的真實值

end

end

for eachs∈S//計算第i個數據項事實級值與對應級數真實值之間的相似度

for eachf,s∈f//根據（15）式計算完整值f與對應真實值之間的相似度

for eachfi,fi∈f//根據（13）式計算數據來源s的準確率A(s)

end

end

end

until Convergence//計算直到真實值收斂于級值

returnP(f)andA(s)

4 實驗分析

4.1實驗準備

本文以Java語言為工具對本文算法同之前常用算法進行對比。JDK的版本為JDK6.0。實驗所選取的處理器為Intel Core i7-2600，實驗過程在內存為16GB的Thinkpad筆記本上進行，操作系統為Windows10。

4.2性能評價

本文采取配適率的指標來對算法進行評價。利用數據集來提供“真值”由此組成“真值”集合，由于數據集較為龐大，提供的數據項值數量眾多，如若全部采用人工驗證的方法其代價太大，因此僅包含少數部分的數據項。本文將算法輸出的真實值同真值的集合的數值比較以此來對算法的結果進行評價。集合A表示分布式數據真值發現輸出的同數據項所對應的“真實值”，集合B表示集合A描述的數據項的子集，它表示真實值集合所描述的數據項。算法準確率的計算公式為

本文所采取的分布式真值發現在對其輸出配適率計算時數據來源所提供的值同“真值”之間的相似程度進行衡量。依據不同的數據集的性質采取不同的數據采集方法和相似程度度量的方法。本文的試驗中選取天氣和人口的數據集為數值型的數據，依據其數值的大小進行相似程度的衡量，而像文本這樣的數據集為字符串型的數據，依據其字符串的長度對其相似程度進行衡量。本文將分布式數據真值發現同幾個常用的真值發現算法，如Vote、ACCUVOTE、Estimates等進行比較，并根據每個算法的特性對參數進行調整，選取最優結果來進行比較。

4.3實驗數據集

本文選取供電局都采用的能量管理系統（EMS）集控中心的變損、線損和負載損耗三個真值的數據集進行實驗并利用輸出結果進行比較。三者的數據集為數值型的數據，滿足多級空間值定義，各級別之間的獨立性比較明顯。“真實集”即真實值，其表明了由人工校準的方式篩選出的于數據集相對應的正確的數據項值的數量，各個算法的配適率則是通過將真實集同算法的輸出結果進行比較得出。具體描述了這三類數據集的詳細統計信息如表2所示。

表2 電網信息真實數據集統計

4.4結果分析

具體的算法準確率與時間開銷如表4所示。

表4 不同算法的準確率與時間開銷統計

由表3的準確率P可以看出，分布式數據真值發現在線損數據集挖掘上擁有出色的表現，比AC?CUVOTE算法的配適準確率高出4.1%。由于分布式數據真值發現參考了ACCUVOTE的一些原則，其配適率與ACCUVOTE算法存在一定的聯系，但最終實驗結果相較于ACCUVOTE算法要優越一些。而在變損和負載損耗數據集上，分布式數據真值發現和ACCUVOTE算法輸出結果的的配適率較低。分布式數據真值發現前提條件是數值擁有多級值空間，而對于數據項的值相對都比較小的數據集而言，分布式數據真值發現的多級值空間分級并不存在發揮其優勢的空間。ACCUVOTE方法輸出的結果在負載損耗數據集上表現也并不如人所愿，主要是負載損耗數據集中的數據來源的數量較少而與數據集對應的真值較多由此容易引發冗余數據的產生。由于數據源之間冗余數據的數據項數量較大，它作為指數，容易導致利用ACCUVOTE算法演算數據源之間存在依賴。

由表3的時間開銷與迭代次數之間的關系不難發現，Vote算法的時間耗費最小，分布式數據真值發現時間耗費較小，ACCUVOTE時間耗費次之。由于算法中需要采取迭代來計算數據源之間的依賴程度們因此需要大量的計算時間，因而時間開銷較大，其中變損數據集的時間開銷最為明顯。

對參數α與β的調整對實驗結果會產生影響，具體的結果如圖1和圖2所示。

圖1 不同α調整分布式真值發現準確率

圖2 不同β調整分布式真值發現準確率

根據圖1中描繪了在β不變且各自選取最優值的條件下，當參數α從1.5不斷調整到4時，變損、線損和負載損耗三個數據集在算法輸出的結果中其配適率變化的曲線。當變損數據集的參數設定為2.5時，分布式真值發現的配適率最高。當線損數據集的參數設定為1.5時，各個“級別”之間的獨立性較強，不存在拆分的關聯原則，導致各個級別之間的權重比越大因此結果也越差。當線損數據集的參數設定為2時，結果最優。圖2中描繪了在α不變且各自選取最優值的條件下，當參數β從1.2不斷調整到2時，三個數據集在算法輸出的結果中其配適率變化的曲線。參數均取為1.2時，線損和負載損耗數據集各個級別之間的權重比越低，結果最優。當變損數據集的β取為1.6時，結果最優。

5 結語

論文針對數據管理系統中存儲的多級數據真值發現問題，從多級數據源特征出發，利用數據集分級后級值與真實值相似度定義分布式迭代真值發現。通過貝葉斯公式構建不同質量的數據來源級值計算，結合級別權值迭代生成完整值并利用相似度定義不同級別之間的差異性，最終設計了一套分布式真值發現算法。該多級數據真值發現算法準確率高，可為數據信息管理系統的數據分類與挖掘提供一種新的途徑。

［1］楊志.一種實時大數據查詢技術-對象分布式查詢［J］.計算機與數字工程，2015（10）：1851-1856.

YANG Zhi.A Real-Time Big Data Query Technology-Objects Distributed Queries［J］.Computer&Digital Engi?neering，2015（10）：1851-1856.

［2］付仲良，劉思遠，田宗舜，等.基于多級R-tree的分布式空間索引及其查詢驗證方法研究［J］.測繪通報，2012（11）：42-46.

FU Zhongliang，LIU Siyuan，TIAN Zongshun，et al.Meth?od of Distributed Spatial Indexing and Query Authentica?tion Based on Multi-Level R-Tree［J］.Bulletin of Surcey?ing and Mapping，2012（11）：42-46.

［3］張濤，余煬，李弋.Linux服務器安全審計系統的設計與實現［J］.計算機應用與軟件，2014（5）：17-22.

ZHANG Tao，YU Yang，LI Ge.Design and Implementa?tion of Linux Server Security Audit System［J］.Computer Applications and Software，2014（05）：17-22.

［4］李天義，谷峪，馬茜，等.一種多源感知數據流上的連續真值發現技術［J］.軟件，2016（7）：341-349.

LI Tianyi，GU Yu，MA Qian，et al.A multi-Source-Aware Continuous Stream on the True Value of Data Discovery Technology［J］.software.2016（7）：341-349.

［5］張志強，劉麗霞，謝曉芹，等.基于數據源依賴關系的信息評價方法研究［J］.計算機學報，2012，35（11）：2392-2402.

ZHANG Zhiqiang，LIU Lixia，XIE Xiaoqin，et al.Evalua?tion Method of Information Based on the Data Source De?pendency［J］.Journal of Computers，2012，35（11）：2392-2402.

［6］馬如霞，孟小峰.基于數據源分類可信性的真值發現方法研究［J］.計算機研究與發展，2015（9）：1931-1940.

MA Ruxia，MENG Xiaofeng.Credibility of the Discovery of the True Value Based on the Data Source Classification［J］.Research and Development of Computer，2015（9）：1931-1940.

［7］唐向紅，李國徽，楊觀賜.快速挖掘數據流中離群點［J］.小型微型計算機系統，2011，32（1）：9-16.

TANG Xianghong，LI Guohui，YANG Guanci.Fast Mining Data Stream Outliers［J］.Journal of Chinese Computer Sys?tems，2011，32（01）：9-16.

［8］祝然威，王鵬，劉馬金.基于計數的數據流頻繁項挖掘算法［J］.計算機研究與發展，2011，48（10）：1803-1811.

ZHU Ranwei，WANG Peng，LIU Majin.Data Stream Min?ing Algorithms Based on Frequent Item Count［J］.Re?search and Development of Computer，2011，48（10）：1803-1811.

［9］余祖坤，許景楠，鄭小林，等.基于信任的真實數據判定方法［J］.系統工程理論與實踐，2013，33（9）：2404-2414.

YU Zukun，XU Jingnan，ZHENG Xiaolin，et al.Real Data Determination Method Based on Trust［J］.Systems Engi?neering Theory and Practice，2013，33（9）：2404-2414.

［10］廖國瓊，吳凌琴，萬常選.基于概率衰減窗口模型的不確定數據流頻繁模式挖掘［J］.計算機研究與發展. 2012，49（5）：1105-1115.

LIAO Guoqiong，WU Linqin，WAN Changxuan.Mining Model Based on Probability Attenuation Window of Un?certain Data Stream Frequent Pattern［J］.Research and Development of Computer，2012，49（5）：1105-1115.

［11］王繼奎，李少波.多數據源沖突的主數據真值發現算法［J］.計算機工程與設計，2014，35（1）：177-182.

WANG Jikui，LI Shaobo.Master Data Multiple Data Sources Conflicts True Value Discovery Algorithm［J］. Engineering and Design of Computer，2014，35（1）：177-182.

［12］郭繼東，李學慶，楊成偉.基于子空間的魯棒射影重建方法［J］.計算機學報，2013，36（12）：2560-2576.

GUO Jidong，LI Xueqing，YANG Chengwei.A Robust Subspace Algorithm for Projective Reconstruction from Multiple Images［J］.Journal of Computers，2013，36（12）：2560-2576.

［13］劉暢，唐達.一種改進的加權隨機抽樣算法［J］.軟件，2011，32（1）：14-17.

LIU Chang，TANG Da.An Improved Algorithm of Weighted Random Sampling［J］.Computer Engineering &Software，2011，32（1）：14-17.

Multi-level Data True Value Discovery Based on Distributed Technology

LV WeixinYIN Jun
（Yunnan Power Grid Co.，Ltd.Kunming Power Supply Bureau，Kunming650200）

To further enhance the reliability and accuracy of the data management system，this study presents a multi-level data based on distributed technology discovered the true value of mining and eliminates the difference between the level of indepen?dence.This method grades the data phase values of data source and use level values and the real value of the defined similarity itera?tive accuracy to avoid the same data is extracted in a different level when differences.By distributed technical mining algorithm the probability of level values and the degree of deviation are calculated to determine the true value of the multi-level data.Finally，through the overlapping data sets of experiments the efficiency of multi-level data true value discovery is illustrated.

multi-level data，true value discovery，distributed，data mining

TN919.3

10.3969/j.issn.1672-9722.2017.05.030

2016年11月7日，

2016年12月19日

國家自然科學基金資助項目（編號：51277085）資助。

呂維新，男，高級工程師，研究方向：云計算。殷軍，男，工程師，研究方向：信息技術與信息管理，計算機技術。