一種分布式函數(shù)依賴挖掘算法

葛錫聰 葉飛躍 劉琪 張云猛

摘要：針對分布在不同節(jié)點的數(shù)據(jù)的函數(shù)依賴挖掘問題進行了研究，提出了一種分布式函數(shù)依賴挖掘算法，該算法是以傳統(tǒng)的函數(shù)依賴挖掘算法Tane算法為基礎(chǔ)設(shè)計的。其基本思想是：首先，使用Tane算法挖掘出各個節(jié)點的函數(shù)依賴;然后，得到各個節(jié)點的公共函數(shù)依賴;最后，以公共函數(shù)依賴的左部公共屬性值為散列值對數(shù)據(jù)進行重分布并對候選函數(shù)依賴進行驗證，得到最終的函數(shù)依賴。該算法的實現(xiàn)過程中幫助解決的數(shù)據(jù)遷移量大和負載不均衡的問題，通過在真實數(shù)據(jù)上的對比分析驗證了算法的可行性。

關(guān)鍵詞：函數(shù)依賴;Tane算法;數(shù)據(jù)重分布

中圖分類號：TP311

文獻標識碼：A

文章編號：1009-3044（2019）36-0084-04

1概述

函數(shù)依賴作為關(guān)系理論中的一個重要概念和關(guān)系數(shù)據(jù)庫的設(shè)計基礎(chǔ)，在知識發(fā)現(xiàn)、語義分析、依賴推理和數(shù)據(jù)質(zhì)量評估等領(lǐng)域有著廣泛的應(yīng)用[1，2]。假定R（U）是一個屬性集U上的關(guān)系模式，X和Y都是U的子集。對于關(guān)系r（U）中的任意元組tl、t2，當tI[X]=t2[X]，必有tl[Y]=t2[Y]，則稱X函數(shù)決定Y，或Y函數(shù)依賴X，可表示成：X～Y[3]，例如在職工信息表中，工號可以決定職工姓名，“工號決定職工姓名”就是一個函數(shù)依賴。

目前，對于函數(shù)依賴挖掘的研究比較多。比較典型的有基于層次優(yōu)先策略的Tane算法[4和Fun算法[5]、基于閉數(shù)據(jù)項集的FD_Mine[6]挖掘方法和基于深度優(yōu)先策略的FastFDs[7]算法等。這些挖掘算法僅僅適用于對集中的數(shù)據(jù)進行分析，如果想要利用這些算法分析分布在多個節(jié)點的數(shù)據(jù)屬性間的函數(shù)依賴關(guān)系，就需要將這些數(shù)據(jù)傳輸?shù)揭粋€節(jié)點進行挖掘。因為，在單個節(jié)點上挖掘出來的函數(shù)依賴不一定滿足所有節(jié)點的整體數(shù)據(jù)。

例1.如圖l所示，是一個分布式數(shù)據(jù)庫的實例。

在上述分布式數(shù)據(jù)庫中，圖l（c）是將sl上的數(shù)據(jù)和s2上的數(shù)據(jù)傳輸?shù)揭粋€節(jié)點后得到的整體數(shù)據(jù)。如圖l（a）（b）所示，實例r1和r2中均包含ID、A、B、C四個屬性，而且從圖l可以看出rl和r2上均存在函數(shù)依賴A→B、A→C和B→C，但是這些函數(shù)依賴在r上并不存在。所以，在單個節(jié)點上成立的函數(shù)依賴，在整體數(shù)據(jù)上不一定存在。由此可以看出，要準確挖掘出分布在多個節(jié)點的數(shù)據(jù)中的函數(shù)依賴關(guān)系，必然要對數(shù)據(jù)進行遷移。 通常情況下，容易想到一個基本的方法就是將所有節(jié)點的數(shù)據(jù)全部傳輸?shù)揭粋€執(zhí)行節(jié)點上去，然后再挖掘該執(zhí)行節(jié)點上的函數(shù)依賴，得到最終結(jié)果，但是該算法的會受到數(shù)據(jù)傳輸量和負載量的影響而降低效率[8-10]。針對傳輸量及負載量問題，提出了一種分布式函數(shù)依賴挖掘算法來幫助有效提高分布式環(huán)境下函數(shù)依賴的挖掘效率。

2相關(guān)工作

假定存在一個關(guān)系模式U，其中，I表示該關(guān)系模式上的一個實例，attr（U）表示該模式上的全體屬性集，A、B、C、D表示該模式上的一個屬性，用X、Y表示屬性集合[11]。

定義l函數(shù)依賴[12]在關(guān)系模式U上成立的函數(shù)依賴通常用形如X→Y的表達式來表示，其中，X、Y∈U，且是兩個屬性的集合，對于實例I上的任意兩個元組tl、t2，如果tl（X）=t2（X），則必然有tl（Y）=t2（Y），那么，在實例I上就存在Y函數(shù)依賴于X。并且，X是函數(shù)依賴的左部，Y是函數(shù)依賴的右部。

定義2最小函數(shù)依賴[13]設(shè)X∈U，A∈U，且X→A是實例I上的一個函數(shù)依賴，對X的任意真子集Xi，即Xi∈X，Xi→A都不成立，那么X→A就是實例I上的最小函數(shù)依賴。

定義3等價類[14]所謂等價類就是在屬性集上取值相等的元組的集合。例如，圖l（c）中，{1，4}就是屬性A上的一個等價類。

定義4劃分[15]在關(guān)系r上屬性集X上所有等價類的集合就是r在X上的一個劃分，并用∏x符號來表示該劃分。其中[∏x]表示劃分∏x中等價類的個數(shù)。

以圖l（c）為例，分別基于屬性集{A}、{B}和{C}將r劃分成等價類?！荹A]={{l，4}，{2，5}，{3，6}、∏{B}={{1，5}，{2，4}，{3，6}）和∏{C}-{{1，6}，{2，4}，{3，5}}，其中[∏{A}]=[{B}]=[∏x]=3.

引理l函數(shù)依賴X→A成立，當且僅當滿足條件[∏x]=[nx∪A]。

3分布式函數(shù)依賴挖掘算法

和傳統(tǒng)的函數(shù)依賴挖掘相比較，分布式函數(shù)依賴的挖掘難度更高，所挖掘出來的函數(shù)依賴既要滿足局部數(shù)據(jù)又要滿足全局數(shù)據(jù)，這就要求在分布式環(huán)境下進行函數(shù)依賴挖掘時，需要對相應(yīng)數(shù)據(jù)進行傳輸。

3.1 GetFD集中式算法

GetFD算法是將分布式函數(shù)依賴挖掘問題轉(zhuǎn)化成及集中式函數(shù)依賴挖掘問題去解決的，通過數(shù)據(jù)傳輸將分布在多個節(jié)點的數(shù)據(jù)集中起來使用傳統(tǒng)函數(shù)依賴挖掘算法Tane進行挖掘。首先，統(tǒng)計各個節(jié)點的元組數(shù)，選擇元組個數(shù)最多的節(jié)點作為運行節(jié)點，并將其他節(jié)點的數(shù)據(jù)傳輸?shù)皆撨\行節(jié)點，然后再用Tane函數(shù)依賴算法挖掘所有的函數(shù)依賴。具體的算法如下：

算法I：GetFD算法

輸入：D=（D1，…，Dn），屬性集合U

輸出：挖掘的函數(shù)依賴集合Ω，

（l） for each i∈[l，n] do

（2） count（i）=[Di]/*其中Di表示節(jié)點i所包含的元組個數(shù)*/

（3） end for

（4） flnd max（count（i）

（5）找出元組最多的節(jié)點作為運行節(jié)點Sk

（6） for each j∈[l，n] do

（7）DK+=Di

（8）if-j==k.

（91 continue

（10） end for

（11） fl，=Discover（DK，U）/*這里使用經(jīng)典的Tane算法挖掘函數(shù)依賴*/

（12） returnn

以上算法，是將所有分散的節(jié)點傳輸?shù)揭粋€節(jié)點后進行函數(shù)依賴挖掘的，在算法執(zhí)行過程中，存在數(shù)據(jù)傳輸量大和負載不均衡的問題，會影響算法的執(zhí)行效率。

3.2 MDFD分布式函數(shù)依賴挖掘算法

在文獻[3]中提出了一種分布式大數(shù)據(jù)中函數(shù)依賴挖掘的框架FMFD，其算法思想是先通過發(fā)現(xiàn)各個節(jié)點的函數(shù)依賴來生成初始候選函數(shù)依賴集，在對各個節(jié)點的函數(shù)依賴進行剪枝，最后將各節(jié)點數(shù)據(jù)傳輸?shù)揭粋€中心節(jié)點進行檢測得到最終的函數(shù)依賴集。該方法在進行終極函數(shù)依賴發(fā)現(xiàn)是需要將數(shù)據(jù)集中驗證，這導(dǎo)致其效率比較低。

為了有效提高上述算法的執(zhí)行效率，本文針對數(shù)據(jù)傳輸量大和負載不均衡這兩個問題，提出了一種分布式函數(shù)依賴挖掘算法，算法的基本思想是：首先，使用Tane算法挖掘出各個節(jié)點的函數(shù)依賴;其次，挖掘出各個節(jié)點的公共函數(shù)依賴;然后，以函數(shù)依賴左部公共屬性為散列值對各節(jié)點數(shù)據(jù)進行哈希重分布，如圖1所示，以A為公共屬性進行分析，A→B、A→C在（a）、（b）中成立，假定A→B、A→C為候選函數(shù)依賴集，對A的屬性之進行哈希計算對數(shù)據(jù)進行重分布，將（1））中的元組4和6傳輸?shù)剑╝）中，（a）中的元組2傳輸?shù)剑╞）中;最后，在各個節(jié)點并行檢測公共函數(shù)依賴，只要某一公共函數(shù)依賴在其中一個節(jié)點上被檢測到不成立，則該函數(shù)依賴就不滿足全局數(shù)據(jù)。上述實例并行檢測，可以檢測出A→B、A→C在全局環(huán)境下是不成立的。

算法2：MDFD算法

輸入：D=（Dl，…，Dn）

輸出：挖掘的函數(shù)依賴集合n

/*使用Tane算法挖掘每個節(jié)點的函數(shù)依賴并得出公共函數(shù)依賴n*/

（1）n=（），Ω=（），ni-（）

（2） for each ie[l，n] do

（3） Ωi=Discover（Di）//這里使用Tane算法挖掘

（4） end for

（5）Ω=∩ni，Ωi

//以Ω的左部單個公共屬性值為散列值進行數(shù)據(jù)重分布

（6） for each m∈[l，n] do

（7） for eac：h tEDi do

（8） ifhash（t）==m-l;

（9）Hmi←Hmi∪t;

（10） end for

（11） end for

（12） for each me[l，n] do

（13） ifi≠k

（14） send Himto Sk

（15） end for

//針對重分布數(shù)據(jù)檢測公共函數(shù)依賴

（16） for each'p∈Ω

（17） check（ψ）;

（18） if check（ψ）！=true

（19）Ω一=ψ

（20） else

（21）Ω+=ψ;

（22） Ω一=ψ;

（23） end for

（24） retumn

其中，驗證函數(shù)如下所示：

check（）函數(shù)

輸入：候選函數(shù)依賴ψ：X→Y

輸出：true or false

（1） if （i//xi=i//xu yl）

（2） return true

（3） else

（4） return false

4實驗

4.1實驗環(huán)境

為了驗證MDFD算法的可行性，在處理器為Intel（R） Core（TM）i7-4790 CPU 3.60GHz，內(nèi)存：16.OGB的PC上進行了實驗。操作系統(tǒng)為Ubuntu16.04.所有算法均由python實現(xiàn)。

4.2實驗數(shù)據(jù)

該實驗選取UCI標準數(shù)據(jù)集上的Adult數(shù)據(jù)集和與之相似的Census-income（KDD）數(shù)據(jù)集，其中，Adult數(shù)據(jù)集包含32561條元組和14個屬性，Census-income（KDD）數(shù)據(jù)集包含299285條元組和40個屬性。

4.3實驗結(jié)果及分析

本文設(shè)計了3組實驗，對本文中提出的GetFD算法和MDFD算法進行測試，在實驗過程中，分別改變元組個數(shù)，節(jié)點個數(shù)以及屬性個數(shù)，每一組實驗都以運行4次后的實驗結(jié)果的均值為最終結(jié)果。

為驗證當節(jié)點和屬性個數(shù)保持不變時，增加元組數(shù)量對于MDFD算法、FMFD算法和GetFD算法執(zhí)行效率的影響與對比，本文選取了Census-income（KDD）數(shù)據(jù)集進行實驗，保證屬性個數(shù)n=8，節(jié)點個數(shù)s=4，元組個數(shù)從30000條增加到70000條，每次增加個數(shù)為10000條，由于元組數(shù)量在增加，數(shù)據(jù)傳輸量與負載量也隨之增加，這就使得三種算法的執(zhí)行時間也會隨之增加。從圖2中很容易看出這一規(guī)律。與此同時，從圖2也能看出，隨著元組個數(shù)的增加，MDFD算法、FMFD算法和GetFD算法的執(zhí)行時間差也逐漸增大，這說明MDFD算法的運行效率也逐漸高于FMFD算法和GetFD算法，而且元組個數(shù)越多，MDFD算法的優(yōu)勢更明顯。

為驗證當元組和屬性個數(shù)保持不變時，增加節(jié)點數(shù)量對MDFD算法、FMFD算法和GetFD算法執(zhí)行效率的影響，本文選取了Adult數(shù)據(jù)集進行實驗，保證屬性個數(shù)n=8，元組個數(shù)為20000條，節(jié)點個數(shù)從2個增加到6個，每次增加個數(shù)為1個，從圖3中可以看出，兩個算法隨著節(jié)點增加運行時間的變化情況，隨著節(jié)點個數(shù)的增加，GetFD算法的執(zhí)行時間隨著節(jié)點個數(shù)的增加而增加，而MDFD算法和FMFD算法的執(zhí)行時間隨著節(jié)點個數(shù)的增加而減少，這與理論預(yù)期結(jié)果相一致，在執(zhí)行GetFD算法時，隨著節(jié)點數(shù)的增加傳輸量增加，因此執(zhí)行時間也不斷增加，對于MDFD算法和FMFD算法，它們都是先對函數(shù)依賴進行并行挖掘，節(jié)點增加使得單個節(jié)點的負載量下降且負載均衡度得到提高，因而其算法的執(zhí)行時間也將隨之下降，但是FMFD算法是在初步挖掘之后，通過集中數(shù)據(jù)進行終極檢測的，相對MDFD算法的并行檢測，其并行度較低。所以，在節(jié)點增加時，MDFD算法的運行效率是明顯優(yōu)于FMFD算法和GetFD算法的。

為驗證當元組和節(jié)點個數(shù)保持不變時，增加屬性個數(shù)對于MDFD算法、FMFD算法和GetFD算法執(zhí)行效率的影響與對比，本文選取了Adult數(shù)據(jù)集進行實驗，保證節(jié)點個數(shù)s=4，元組個數(shù)為20000條，屬性個數(shù)從4個增加到8個，每次增加個數(shù)為1個，由于隨著屬性個數(shù)的不斷增加，單個節(jié)點的數(shù)據(jù)傳輸量與負載量也隨之增加，這就使得三種算法的執(zhí)行時間也會隨之增加。從圖4中很容易看出這一規(guī)律。與此同時，從圖4也能看出，隨著屬性個數(shù)的增加，MDFD算法、FMFD算法和GetFD算法的執(zhí)行時間差也逐漸增大，這說明MDFD算法的運行效率也逐漸高于FMFD算法和GetFD算法，而且屬性個數(shù)越多，MDFD算法的優(yōu)勢更明顯。

5結(jié)束語

隨著分布式數(shù)據(jù)存儲的廣泛應(yīng)用，傳統(tǒng)的集中式函數(shù)依賴挖掘方法難以滿足實際應(yīng)用需要。當前，國內(nèi)外相關(guān)研究人員正在對分布式環(huán)境下的函數(shù)依賴理論及應(yīng)用進行深入研究。本文基于基本的函數(shù)依賴挖掘算法Tane算法，提出了一種分布式函數(shù)依賴挖掘算法MDFD算法，算法包含基礎(chǔ)函數(shù)依賴挖掘、數(shù)據(jù)重分布和函數(shù)依賴驗證等內(nèi)容的實現(xiàn)，并通過相關(guān)實驗對比驗證了該算法的可行性。

參考文獻：

[1]李建中，劉顯敏.大數(shù)據(jù)的一個重要方面：數(shù)據(jù)可用性[J].計算機研究與發(fā)展，2013，50（6）：1147-1162.

[2]孟小峰，慈祥.大數(shù)據(jù)管理：概念、技術(shù)與挑戰(zhàn)[J].計算機研究與發(fā)展，2013，50（1）：146-169.

[3] Ye Feiyue，Liu Jixue，Qian Jin， et al.A framework for miningfunctional dependencies from large distributed databases[C]//Proc of 2010 Intemational Conference on Artificial Intelli-gence and Computational Intelligence.Alamitos，CA：IEEE，2010：109-113.

[4] Huhtala Y，Karkkainen J，Porkka P，et al.TANE：An efficientalgorithm for discovering functional and approximate depen-dencies[J].C omputer Joumal，1999，42（2）：100-11 1.

[5]Novelli N，Cicchetti R.Fun： An efficient algorithm for miningfunctional and embedded dependencies[C]//Proc of the 8th In-ternational Conference of Database 'l'heory. New York：ACM，2001：189-203.

[6] Hong Yao， Howard J. Hamilton， Cory J. Butz. FD_Mine： Dis-covering Functional Dependencies in a Database Using Equiv-alences[C]. Proc of the 2002 IEEE International Conferenceon Data Mining. Japan：lDCM， 2002：9-12.

[7] Wyss C， Giannella C， Robertson E. FastFDs： A heuristicdriv-en， depth-first algorithm for mining functional dependenciesfrom relation instances[C]//Proc of the 3rd IntConf on DataWarehousing and Knowledge Discovery. New York， 2001：101-110.

[8] ShouzhongTu， Minlie Huang. Scalable Functional Dependen-cies Discovery from Big Data[C]//Proc of 2016 IEEE Secom'lInternational Conference on Multimedia Big Data （BigMM），2016：426-431.

[9] Jixue Liu， FeiyueYe，Jiuyong Li， et al. On discovery of' func-tional dependencies from data[J].Data & Knowledge Engineer-ing， 2013，86：146-159.

[10] Weibang Li， Zhanhuai Li， Qun Chen， Tao Jiang，HailongLiu：Discovering Functional dependencies in Vertically DistributedBig Data.WISE（2）2015：199-207.

[11] Jixue Liu， Jiuyong Li， Chengfei Liu， et al. Discover Depen-dencies from Data-A Review[C]. IEEE 'rransactions on Knowl-edge and Data Engineering，2012，4（2）：251-264.

[12] H. Yao，H. J.Hamilton. Mining functional dependencies fromdata[J].Journal Data Mining and Knowledge Discovery，2008，16（2）：197-219.

[13]王新，馬萬青 . -種有效的最小函賴挖掘方法 [J].云南民族大學學報：自然科學報， 2005， 14（4） ： 356-362.

[14] Abedjan Z， Schulze P， Naumann F. DFD： Efficient functionaldependency discovery[C]// Proc of the 23rd ACM InternationalConference on Information and Knowledge Management. NewYork： ACM， 2014：949-958.

[15] Shyue-Liang Wang， Ju-Wen Shen， 'rzung_Pei Hong.lncre-mental discovery of functional dependencies using partitions[C]//IFSA World Congress and 20th NAFIPS Intemational Con-ferenee：IEEE，2001：1322-1326.

收稿日期：2019-09-25

基金項目：國家自然科學基金項目（No.61472166）;江蘇省研究生科研與實踐創(chuàng)新計劃項目（SJCX18_1021）

作者簡介：葛錫聰（1995-），女，江蘇南通人，碩士研究生，主要研究方向為數(shù)據(jù)挖掘、智能裝備運行與管理;葉飛躍（1960-），男，浙江

東陽人，教授，博士，主要研究方向為數(shù)據(jù)挖掘、人工智能;劉琪（1993-），女，江蘇南通人，碩士研究生，主要研究方向為數(shù)據(jù)挖掘、智能裝備運行與管理;張云猛（1996-），男，江蘇鹽城人，碩士研究生，主要研究方向為數(shù)據(jù)挖掘、機電產(chǎn)品檢測與智能控制。