一種分布式函數依賴挖掘算法

葛錫聰 葉飛躍 劉琪 張云猛

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

關鍵詞：函數依賴;Tane算法;數據重分布

中圖分類號：TP311

文獻標識碼：A

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

1概述

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

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

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

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

2相關工作

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

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

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

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

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

以圖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函數依賴X→A成立，當且僅當滿足條件[∏x]=[nx∪A]。

3分布式函數依賴挖掘算法

和傳統的函數依賴挖掘相比較，分布式函數依賴的挖掘難度更高，所挖掘出來的函數依賴既要滿足局部數據又要滿足全局數據，這就要求在分布式環境下進行函數依賴挖掘時，需要對相應數據進行傳輸。

3.1 GetFD集中式算法

GetFD算法是將分布式函數依賴挖掘問題轉化成及集中式函數依賴挖掘問題去解決的，通過數據傳輸將分布在多個節點的數據集中起來使用傳統函數依賴挖掘算法Tane進行挖掘。首先，統計各個節點的元組數，選擇元組個數最多的節點作為運行節點，并將其他節點的數據傳輸到該運行節點，然后再用Tane函數依賴算法挖掘所有的函數依賴。具體的算法如下：

算法I：GetFD算法

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

輸出：挖掘的函數依賴集合Ω，

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

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

（3） end for

（4） flnd max（count（i）

（5）找出元組最多的節點作為運行節點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）/*這里使用經典的Tane算法挖掘函數依賴*/

（12） returnn

以上算法，是將所有分散的節點傳輸到一個節點后進行函數依賴挖掘的，在算法執行過程中，存在數據傳輸量大和負載不均衡的問題，會影響算法的執行效率。

3.2 MDFD分布式函數依賴挖掘算法

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

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

算法2：MDFD算法

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

輸出：挖掘的函數依賴集合n

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

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

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

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

（4） end for

（5）Ω=∩ni，Ωi

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

（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

//針對重分布數據檢測公共函數依賴

（16） for each'p∈Ω

（17） check（ψ）;

（18） if check（ψ）！=true

（19）Ω一=ψ

（20） else

（21）Ω+=ψ;

（22） Ω一=ψ;

（23） end for

（24） retumn

其中，驗證函數如下所示：

check（）函數

輸入：候選函數依賴ψ：X→Y

輸出：true or false

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

（2） return true

（3） else

（4） return false

4實驗

4.1實驗環境

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

4.2實驗數據

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

4.3實驗結果及分析

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

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

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

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

5結束語

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

參考文獻：

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

[2]孟小峰，慈祥.大數據管理：概念、技術與挑戰[J].計算機研究與發展，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）;江蘇省研究生科研與實踐創新計劃項目（SJCX18_1021）

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

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