基于馬爾科夫毯的近似函數(shù)依賴挖掘算法

夏秀峰，劉朝輝，張安珍

（沈陽航空航天大學(xué) 計(jì)算機(jī)學(xué)院，沈陽 110136）

數(shù)據(jù)分析最重要的任務(wù)之一是發(fā)現(xiàn)給定數(shù)據(jù)集中的函數(shù)依賴關(guān)系，在數(shù)據(jù)集成、數(shù)據(jù)清洗［1］、知識發(fā)現(xiàn)［2］、數(shù)據(jù)質(zhì)量評估等相關(guān)領(lǐng)域有著廣泛應(yīng)用。函數(shù)依賴（functional depen‐dency，F(xiàn)D）是數(shù)據(jù)集中屬性之間的一種依賴關(guān)系。對于給定數(shù)據(jù)集和兩個(gè)屬性集合X和A，若任意元組對在X中的屬性取值相同，在A中屬性取值也相同，則稱X→A是一個(gè)函數(shù)依賴。本文只考慮挖掘非平凡且最小的函數(shù)依賴，即A不包含于X，且X刪去任意一個(gè)子集B后，函數(shù)依賴XB→A不再成立。然而，實(shí)際數(shù)據(jù)往往存在各種錯(cuò)誤，這些錯(cuò)誤可能導(dǎo)致原本正確的函數(shù)依賴不再成立，無法出現(xiàn)在挖掘結(jié)果中，從而影響函數(shù)依賴挖掘結(jié)果的召回率。因此，研究人員提出了近似函數(shù)依賴挖掘算法，其核心思想是在適當(dāng)放寬函數(shù)依賴的成立條件下，允許數(shù)據(jù)中存在少量違反函數(shù)依賴的元組對，從而在一定程度上降低了數(shù)據(jù)錯(cuò)誤對函數(shù)依賴挖掘算法召回率的影響。例如，文獻(xiàn)［3］將所有元組對中違反函數(shù)依賴的元組對所占比例定義為函數(shù)依賴的誤差，并挖掘出誤差小于給定閾值的近似函數(shù)依賴。

根據(jù)近似函數(shù)依賴挖掘算法的性質(zhì)，可以分為行高效算法、列高效算法以及混合式算法。行高效的代表算法有Tane［4］、Fun［5］、FD_Mine［6］和Dfd［7］，它們將函數(shù)依賴的候選集建模為屬性組合的冪集格，通過遍歷得到最小且非平凡的函數(shù)依賴。雖然這4種算法的遍歷策略不同，但是都連續(xù)生成候選的函數(shù)依賴，并使用位置列表索引中的剝離分區(qū)驗(yàn)證候選的函數(shù)依賴。Tane、Fun、FD_Mine算法使用基于先驗(yàn)候選生成原則，由搜索候選格自底向上進(jìn)行遍歷，Dfd算法使用深度優(yōu)先隨機(jī)游走的遍歷策略。然而，這類算法的搜索空間是屬性數(shù)量的指數(shù)級，在屬性數(shù)量較多的數(shù)據(jù)集中表現(xiàn)不佳。列高效的代表算法有Fdep［8］，Dep-Miner［9］，F(xiàn)astFDs［10］，核心思想是兩兩比較所有元組，找出非函數(shù)依賴，然后利用非函數(shù)依賴推導(dǎo)出候選函數(shù)依賴，這類方法需要對全部數(shù)據(jù)進(jìn)行兩兩比較，時(shí)間開銷為O（n2），對于元組較多的數(shù)據(jù)集表現(xiàn)較差?；旌鲜剿惴℉YFD［11］結(jié)合了行高效以及列高效的優(yōu)點(diǎn)，在第一階段使用采樣對部分元組提取非函數(shù)依賴；然后在第二階段對第一階段得到的函數(shù)依賴候選集進(jìn)行驗(yàn)證。針對這兩個(gè)階段的切換標(biāo)準(zhǔn)是基于采樣和驗(yàn)證標(biāo)準(zhǔn)的度量方法，如果切換過早，與直接利用搜索算法無異；切換過晚，無異于直接利用歸納技術(shù)，都會非常耗時(shí)。

現(xiàn)有的近似函數(shù)依賴挖掘方法雖然可以降低數(shù)據(jù)錯(cuò)誤對函數(shù)依賴挖掘結(jié)果的影響，但仍然存在以下兩方面的問題：（1）現(xiàn)有方法大多需要系統(tǒng)地枚舉所有可能的FD，并逐一驗(yàn)證其共現(xiàn)頻率是否滿足閾值要求，導(dǎo)致候選FD規(guī)模巨大，挖掘效率較低。例如，假設(shè)數(shù)據(jù)中有m個(gè)屬性，文獻(xiàn)［3］的搜索空間為O（2m），搜索代價(jià)是指數(shù)級的；（2）現(xiàn)有的方法容易出現(xiàn)過擬合問題，挖掘出大量左部屬性數(shù)量較多的虛假FD，挖掘結(jié)果準(zhǔn)確率較低。例如，對于只有幾十個(gè)屬性的數(shù)據(jù)集，基于共現(xiàn)頻率的方法會挖掘出成百上千條FD，其中大部分是過擬合的。

為了解決以上問題，本文提出了基于馬爾科夫毯的近似函數(shù)依賴挖掘算法。該算法利用馬爾科夫毯的條件獨(dú)立性推導(dǎo)候選函數(shù)依賴，從而減少候選函數(shù)依賴的規(guī)模，在保證挖掘出最小且非平凡的近似函數(shù)依賴的同時(shí)，不會出現(xiàn)過擬合情況。具體算法流程如下：首先，對輸入數(shù)據(jù)集進(jìn)行采樣，在樣本上學(xué)習(xí)貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)，得到每個(gè)屬性的馬爾科夫毯；其次，根據(jù)每個(gè)屬性的馬爾科夫毯創(chuàng)建其左部決定集的搜索空間；最后，對于搜索空間中最大候選函數(shù)依賴不斷向下泛化驗(yàn)證，得到誤差小于給定錯(cuò)誤閾值的最小且非平凡的近似函數(shù)依賴。通過引入馬爾科夫毯的條件獨(dú)立性，該算法可以有效減少候選函數(shù)依賴的規(guī)模，并且避免了過擬合問題，從而提高了近似函數(shù)依賴挖掘的效率和準(zhǔn)確性。

1 先驗(yàn)知識和問題定義

1.1 函數(shù)依賴

定義1 函數(shù)依賴：給定屬性集U，關(guān)系模式為R，X和A是U的子集。若對于R的任意一個(gè)可能的關(guān)系r，r中不存在兩個(gè)元組在X上的屬性值相等，而在A上的屬性值不等，則稱X函數(shù)確定A或A函數(shù)依賴于X，記作X→A，稱X為FD左部（left-hand-side，lhs）或者決定項(xiàng)，A為FD的右部（right-hand-side，rhs）或者依賴項(xiàng)。

例1 表1為部分美國醫(yī)院信息表，包含5個(gè)屬性ProviderNumber、HospitalName、County‐Name、MeasureCode、MeasureName，分別表示編號、醫(yī)院名稱、城市名稱、診斷代碼和診斷名稱。該表中存在2條函數(shù)依賴，Measure‐Code→MeasureName和ProviderNumber→Hos‐pitalName。其中MeasureCode→MeasureName表示診斷代碼可以唯一確定診斷名稱，換言之，MeasureCode取值相同的元組，其Measure‐Name的取值也相同。如表1中所示，t1［Mea‐sureCode］=t7［MeasureCode］=pn-5c，t1［Mea‐sureName］=t7［MeasureName］=pxeumoxia。

表1 部分美國醫(yī)院信息表

對于一條函數(shù)依賴X→A，若X?Y，則稱X→A是Y→A的泛化，Y→A是X→A的細(xì)化；若X→A的任意泛化在數(shù)據(jù)集中都不成立，則稱其為最小函數(shù)依賴；若A?X，則稱該函數(shù)依賴是非平凡的。精確的函數(shù)依賴挖掘方法旨在挖掘出所有非平凡的最小函數(shù)依賴，這就意味著數(shù)據(jù)中不允許出現(xiàn)任何違反函數(shù)依賴的元組。然而，真實(shí)數(shù)據(jù)集往往不是干凈的，存在一些數(shù)據(jù)錯(cuò)誤或缺失值，導(dǎo)致原本成立的函數(shù)依賴不再成立。為了不丟失任何可能正確的函數(shù)依賴，對函數(shù)依賴成立的條件進(jìn)行松弛，允許一定比例的違反，將松弛后的函數(shù)依賴稱為近似函數(shù)依賴。下面從概率的角度給出近似函數(shù)依賴的形式化定義。

定義2 近似函數(shù)依賴（Approximate Func‐tinal Dependency，AFD）：給定關(guān)系模式R，令R上每個(gè)屬性A的值域?yàn)閂(A)，則屬性集合X={A1，A2，…，Ak}?R對應(yīng)的值域V(X)=V(A1)×V(A2)×…×V(Ak)，假設(shè)R中的每個(gè)實(shí)例D都有一個(gè)概率密度fR(D)，這些概率密度形成有效的概率分布PR。給定分布PR及FD：X→A，若存在函數(shù)?：V(X)→V(A)，使得下面公式（1）成立，則稱X→A為近似函數(shù)依賴，其中X?R，A∈R，ε是一個(gè)很小的常數(shù)。

當(dāng)a=?(x)，特別地，當(dāng)ε=0時(shí)，X→A為函數(shù)依賴?？梢钥闯?，近似函數(shù)依賴通過引入誤差ε放寬了函數(shù)依賴成立的條件，允許數(shù)據(jù)中存在一些違反函數(shù)依賴的元組。

例2 表1中的一條真實(shí)的函數(shù)依賴為MeasureCode→MeasureName。當(dāng)數(shù)據(jù)發(fā)生錯(cuò)誤時(shí)，t2元組的MeasureCode值由ami-1變?yōu)閜n-2，此時(shí)，t2、t3、t5、t6的MeasureCode值都為pn-2，但t3、t5、t6的MeasureName為pneumonia，而t2的MeasureName為heart attack，導(dǎo)致Mea‐sureCode→MeasureName這條函數(shù)依賴不再成立。令誤差ε=0.25，則PR（MeasureName=pneu‐monia|MeasureCode=pn2）=0.75，此時(shí)可以認(rèn)為在表1的數(shù)據(jù)集中函數(shù)依賴Measure‐Code→MeasureName近似成立。

現(xiàn)有的近似函數(shù)依賴挖掘的方法通常利用樣本實(shí)例D中(X，A)的共現(xiàn)計(jì)數(shù)與X值的計(jì)數(shù)比值作為PR（A|X）的估計(jì)，即count（X，A）/count（X）。然而，在給定的樣本中，隨著X中屬性數(shù)量的增加，該比值有可能接近1，進(jìn)而滿足公式（1），此時(shí)挖掘出的函數(shù)依賴是過擬合的。例如，Country Name，Measure Code，Measure Name→HosptialName就是過擬合的近似函數(shù)依賴，因?yàn)樽蟛繉傩詳?shù)量較多，導(dǎo)致每種左部屬性取值的計(jì)數(shù)都為1，左部屬性與右部屬性共現(xiàn)的計(jì)數(shù)也為1，從而比值為1。因此，在確定每個(gè)右部屬性的左部決定集時(shí)，應(yīng)盡量縮小左部屬性范圍，防止過擬合，提高挖掘的準(zhǔn)確率。

1.2 馬爾科夫毯

本節(jié)首先介紹馬爾科夫毯，然后分析馬爾科夫毯獨(dú)立性與函數(shù)依賴之間的關(guān)系。

定義3 馬爾科夫毯［12-13］：指在隨機(jī)變量的全集U中，對于給定的變量X∈U和變量集MB?U，(X?MB)，屬性之間若存在X⊥{UMB-{X}}|MB（⊥：獨(dú)立），則稱滿足上述條件的最小變量集MB為X的馬爾科夫毯。具體而言，當(dāng)全集U是貝葉斯網(wǎng)絡(luò)的各個(gè)結(jié)點(diǎn)時(shí)，節(jié)點(diǎn)X的馬爾科夫毯是由該節(jié)點(diǎn)的父節(jié)點(diǎn)Pa(X)、子節(jié)點(diǎn)Ch(X)和配偶節(jié)點(diǎn)Sp(X)組成，即MB(X)=Pa(X)∪Ch(X)∪Sp(X)。這種定義方式將馬爾科夫毯與節(jié)點(diǎn)的獨(dú)立性以及節(jié)點(diǎn)間的函數(shù)依賴關(guān)系聯(lián)系在一起。

例3 圖1是一個(gè)貝葉斯網(wǎng)絡(luò)，節(jié)點(diǎn)X5的父節(jié)點(diǎn)Pa(X5)={X2、X3}，子節(jié)點(diǎn)為Cha(X5)={X8}，配偶節(jié)點(diǎn)為Sp(X5)={X6}，因此，MB(X5)={X2，X3，X6，X8}。

圖1 馬爾科夫毯示意圖

根據(jù)馬爾科夫毯條件獨(dú)立性的原理，可以得出影響一個(gè)變量取值分布的變量都在其馬爾科夫毯中。基于這一原理，做出如下猜想：對于函數(shù)依賴X→A中的右部屬性A，既然X的取值能夠唯一確定A的取值，那么X應(yīng)該在A的馬爾科夫毯中。經(jīng)過引理1的證實(shí)，這一猜想得到了驗(yàn)證。

引理1給定屬性集U上的關(guān)系模式R，對于U中任意屬性A，假設(shè)其有唯一的左部決定集X，即存在函數(shù)依賴X→A，則X一定在A的馬爾科夫毯中，即X?MB(A)。

證明：采用反證法，假設(shè)X不在A的馬爾科夫毯中，根據(jù)函數(shù)依賴X→A可知，X值可以確定唯一的A值。假設(shè)X=xi時(shí)，對應(yīng)的A=ai，即P(A=ai|X=xi)=1，因此P(A=ai|MB(A)，X=xi)=1。換言之，當(dāng)給定X=xi時(shí)，A一定為ai，與MB(A)中的屬性取值無關(guān)，與馬爾科夫毯條件獨(dú)立性相違背，假設(shè)不成立，因此X一定在A的馬爾科夫毯中。

經(jīng)過引理1的驗(yàn)證，可以得知，對于每個(gè)函數(shù)依賴中的右部屬性，可以在其馬爾科夫毯中搜索左部的決定集，從而避免了在全部屬性空間中的搜索。這種優(yōu)化不僅提高了搜索效率，同時(shí)也能有效解決過擬合問題。

1.3 問題定義

給定噪聲數(shù)據(jù)集關(guān)系模式R及其概率分布PR，噪聲數(shù)據(jù)集D'和錯(cuò)誤閾值ε，挖掘PR的最小且非平凡的近似函數(shù)依賴如式（2）所示

式中：X?R，A∈R。對于PR采樣中的任意一對元組ti、tj，當(dāng)左部屬性集X的取值相同時(shí)，右部A的取值也相同的概率是1-ε（ε的值很小）。

2 MB_AFD算法概述

為了解決近似函數(shù)依賴挖掘算法的準(zhǔn)確率低及過擬合問題，本文提出了基于馬爾科夫毯的近似函數(shù)依賴挖掘算法MB_AFD。輸入為噪聲數(shù)據(jù)集D'以及最大錯(cuò)誤閾值emax，輸出為每個(gè)屬性對應(yīng)的最小近似函數(shù)依賴集AFDs，算法MB_AFD的工作內(nèi)容分為以下3個(gè)部分，如圖2所示。

圖2 算法MB_AFD總體框架圖

（1）構(gòu)建每個(gè)屬性的馬爾科夫毯

對于輸入的噪聲數(shù)據(jù)集D'進(jìn)行采樣，訓(xùn)練其貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)，為每個(gè)節(jié)點(diǎn)屬性構(gòu)建馬爾科夫毯Attribute_MB。

（2）鎖定搜索空間的峰值

對數(shù)據(jù)集中的每個(gè)屬性，生成其左部決定集的搜索空間，其中每個(gè)屬性的搜索空間searchSpace可以表示為一個(gè)冪集格。接下來，利用每個(gè)屬性的馬爾科夫毯Attribute_MB，在搜索空間中鎖定頂峰Peak，從而剪枝去掉大部分的搜索空間，減少搜索的復(fù)雜性。

（3）向下泛化搜索

在鎖定每個(gè)屬性搜索空間的頂峰節(jié)點(diǎn)Peak后，采用向下泛化驗(yàn)證的策略。具體而言，根據(jù)包含的所有子集逐步減少左部候選項(xiàng)的屬性個(gè)數(shù)，從而降低搜索冪級格中的級別。在驗(yàn)證過程中，計(jì)算節(jié)點(diǎn)的實(shí)際誤差e，并與預(yù)先設(shè)定的最大錯(cuò)誤閾值emax進(jìn)行比較，直到找出最小的左部屬性候選集。最后，MB_AFD采用分治策略遍歷其他屬性的搜索空間，依次發(fā)現(xiàn)每個(gè)屬性的最小近似函數(shù)依賴。通過這種方式，在搜索過程中可以高效地減少搜索空間，從而提高搜索效率并找到最小的近似函數(shù)依賴。

3 MB_AFD算法的搜索策略

本節(jié)介紹一種基于馬爾科夫毯的近似函數(shù)依賴挖掘算法，其基本思想是通過構(gòu)建貝葉斯網(wǎng)絡(luò)來生成每個(gè)屬性的馬爾科夫毯，然后利用每個(gè)屬性的馬爾科夫毯來鎖定該屬性所在搜索空間的峰值。最后，采用向下泛化的方式不斷挖掘最小的近似函數(shù)依賴。

3.1 構(gòu)建每個(gè)屬性的馬爾科夫毯

對于給定的噪聲數(shù)據(jù)集D'，每個(gè)屬性的左部決定項(xiàng)的候選空間包含了數(shù)據(jù)集中其他屬性所有可能的組合，需要逐一對這些組合進(jìn)行驗(yàn)證，確保其精確誤差小于錯(cuò)誤閾值。然而，這樣的計(jì)算復(fù)雜度會隨著數(shù)據(jù)集中屬性的數(shù)量和元組數(shù)量的增加而增大，導(dǎo)致求解過程緩慢，并可能生成大量的過擬合近似函數(shù)依賴AFDs，從而降低實(shí)驗(yàn)結(jié)果的精確性。為了解決這個(gè)問題，本文提出利用給定的噪聲數(shù)據(jù)集訓(xùn)練數(shù)據(jù)集中各個(gè)屬性馬爾科夫毯的方法。通過構(gòu)建每個(gè)屬性的馬爾科夫毯，可以將無關(guān)屬性排除在左部決定項(xiàng)的候選空間之外，同時(shí)刪除包含無關(guān)屬性的集合，從而減小左部決定項(xiàng)的候選空間，并提高挖掘算法的精確率，避免近似函數(shù)依賴過擬合。這個(gè)方法作為MB_AFD算法的初始步驟，根據(jù)定義3依次構(gòu)建出每個(gè)屬性的馬爾科夫毯，如算法1所示。

算法1：創(chuàng)建屬性的馬爾科夫毯算法（Create_MB）輸入：關(guān)系模式R上的噪聲數(shù)據(jù)集D'；輸出：每個(gè)屬性的馬爾科夫毯Attribute_MB ；1.V ←數(shù)據(jù)集D'中的屬性；2.θ←結(jié)構(gòu)參數(shù)的最大似然估計(jì)；3.oldScore←f（skeleton，θ，D'）；4.while true do 5.for newSkeleton of adding or reducing or deleting do 6.tempScore ←f（skeleton，θ，D'）；7.if tempScore＞oldScore then 8. skeleton=newSkeleton；9. end；10.end；11.end；12.for each attribute X∈V do 13.MB（X）←search（X，skeleton，Pa（X）∪Ch（X）∪Sp（X））；14.Attribute_MB ←MB（X）；15.end；16.return Attribute_MB；

算法1首先從給定的輸入數(shù)據(jù)集中進(jìn)行采樣，并學(xué)習(xí)屬性之間的依賴關(guān)系，從而訓(xùn)練生成貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)。本文采用了爬山法［14-16］來生成貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)（第2～11行），該算法通過貪婪選擇來判斷是否對模型結(jié)構(gòu)進(jìn)行更新（第6行），目標(biāo)是要找出評分最高的模型，從初始的無邊空網(wǎng)絡(luò)模型出發(fā)開始搜索，隨后進(jìn)入迭代的搜索階段。用搜索算子對當(dāng)前模型進(jìn)行局部修改，得到一系列候選模型，然后計(jì)算每個(gè)候選模型的評分，并將最優(yōu)候選模型與當(dāng)前模型進(jìn)行比較。若最優(yōu)候選模型的評分大于當(dāng)前模型的評分，則將當(dāng)前模型替換為最優(yōu)候選模型，繼續(xù)搜索；否則，停止搜索，并返回當(dāng)前最優(yōu)模型。評分函數(shù)中的評分高低作為操作（加邊、減邊、刪邊）的依據(jù)（第5行），生成所需的貝葉斯網(wǎng)絡(luò)拓?fù)鋱D，接著再根據(jù)拓?fù)鋱D中每個(gè)屬性的父節(jié)點(diǎn)、子節(jié)點(diǎn)以及配偶節(jié)點(diǎn)，生成該屬性的馬爾科夫毯（第12～15行）。

3.2 向下泛化搜索算法

由函數(shù)依賴的定義可知，當(dāng)挖掘右部屬性的決定項(xiàng)時(shí)，搜索空間會變得非常龐大，且可能會出現(xiàn)過擬合現(xiàn)象，例如rhs=xi，左部可能是其他剩余屬性的組合，即lhs=2Rxi。為了避免這類問題的出現(xiàn)，本文提出向下泛化搜索算法。在每個(gè)屬性的搜索空間中，從鎖定的頂峰向下泛化驗(yàn)證，峰值所包含的所有子集，最終生成最小近似函數(shù)依賴。算法的輸入包括噪聲數(shù)據(jù)集D'、各個(gè)屬性的馬爾科夫毯Attribute_MB以及錯(cuò)誤閾值emax。輸出為數(shù)據(jù)集中存在的最小近似函數(shù)依賴集合AFDs，算法2如下所示。

算法2：向下泛化搜索最小近似函數(shù)依賴算法（Discovery_AFDs）輸入：屬性的馬爾科夫毯Attribute_MB，錯(cuò)誤閾值emax，關(guān)系模式R上的噪聲數(shù)據(jù)集D'；輸出：挖掘出來的所有最小且非平凡的近似函數(shù)依賴AFDs；初始化searchSpaces；初始化PLI ←D'；1.searchSpaces ←UA∈R Create _ AFD_Space（R｛A｝，A，e）；2.for each space _ X ∈searchSpaces do 3. peak ←new priority queue Attribute_MB（X）；4. while peak ≠? do 5. P←peek from peak；6. M' ←look up subsets of P；7. if M' ≠ ? then 8. remove P from Peak；9. for each H ∈ hitting-set（M'） do 10. if P H is not an （estimated）11. non-dependency then 12. add P H to peak；13. else；14. e ←calculateError（P，X，PLI）；15. if e＜emax do 16. M ←Discovery Generalization（P，

算法2首先根據(jù)屬性集依次建立搜索空間，并進(jìn)行遍歷（第4～5行）。將該屬性的馬爾科夫毯確定為頂峰節(jié)點(diǎn)peak（第6行），然后根據(jù)節(jié)點(diǎn)peak剪枝搜索空間，并驗(yàn)證當(dāng)前節(jié)點(diǎn)是否滿足實(shí)際誤差小于給定的誤差閾值（第17行），如果滿足，則會迭代地逐級向下泛化（第22～36行），目的是找到最小的近似函數(shù)依賴；如果當(dāng)前節(jié)點(diǎn)peak及其所有的泛化節(jié)點(diǎn)均驗(yàn)證結(jié)束，則返回⊥。

引理2 給定屬性集U上的關(guān)系模式R，假設(shè)近似函數(shù)依賴X→A在屬性集U上驗(yàn)證成立，則Y→A(Y?X)可能是最小的近似函數(shù)依賴，即A的最小左部決定項(xiàng)則是X的子集。

證明 假設(shè)Y→A和X→A在給定屬性集U上均成立，并且Y?X，可證集合X中的屬性個(gè)數(shù)一定大于等于Y中的屬性個(gè)數(shù)，因此X不是最小的左部決定項(xiàng)。

例3 圖3表示屬性E在屬性集U上的左部決定項(xiàng)候選搜索空間，假設(shè)A，C，D→E的實(shí)際誤差小于給定的錯(cuò)誤閾值，則認(rèn)為A，C，D→E在屬性集U上近似成立，但可能不是最小的近似函數(shù)依賴。因此，需要減小左部屬性集中屬性的個(gè)數(shù)，依次計(jì)算A，C→E，A，D→E，C，D→E，A→E，C→E，D→E的實(shí)際誤差與錯(cuò)誤閾值，并進(jìn)行比較，不斷向下泛化來尋找最小的近似函數(shù)依賴。

圖3 屬性E左部決定項(xiàng)的候選搜索空間

引理 3 給定屬性集U上的關(guān)系模式R，假設(shè)近似函數(shù)依賴X→A在屬性集U上驗(yàn)證成立，則Y→A(X?Y)不是最小的近似函數(shù)依賴。

證明 假設(shè)Y→A和X→A在給定屬性集U上均成立，并且X?Y，可證集合Y中的屬性個(gè)數(shù)一定大于等于X中的屬性個(gè)數(shù)。因此，Y不是最小的左部決定項(xiàng)。

例4 圖4表示屬性E在屬性集U上的左部決定項(xiàng)候選搜索空間，假設(shè)A，C→E的實(shí)際誤差小于給定的錯(cuò)誤閾值，則認(rèn)為A，C→E在屬性集U上近似成立。而A，B，C→E，A，C，D→E，A，B，C，D→E則是過擬合的。因此，搜索空間中的A，C→E的細(xì)化形式需要剪枝。

圖4 屬性E左部決定項(xiàng)的剪枝過程

4 實(shí)驗(yàn)測試與結(jié)果分析

4.1 實(shí)驗(yàn)設(shè)置

本節(jié)首先介紹了實(shí)驗(yàn)環(huán)境，接著說明了實(shí)驗(yàn)中真實(shí)數(shù)據(jù)集和合成數(shù)據(jù)集的獲取，最后介紹數(shù)據(jù)集中噪聲引入的方法以及F1-score的定義。

算法采用Java實(shí)現(xiàn)，實(shí)驗(yàn)環(huán)境為Intel（R）Core（TM） i5-6300HQ 2.30 GHz的4核處理器；1TB內(nèi)存；操作系統(tǒng)為Windows10。

真實(shí)數(shù)據(jù)集使用Rayyan、Beers、Flights及Hospital 4個(gè)數(shù)據(jù)集，Rayyan，Beers［Ouzzani et al.，2016］和Flights［Li et al.，2012］是由用戶手動收集并清理的數(shù)據(jù)集，Hospital數(shù)據(jù)集是常用于數(shù)據(jù)清洗的基準(zhǔn)數(shù)據(jù)集，其中4個(gè)數(shù)據(jù)集分別包含3、3、4和15條真實(shí)的FD，如表2所示。

表2 真實(shí)數(shù)據(jù)集基本信息

合成數(shù)據(jù)集獲取的方法為：給定一個(gè)具有n個(gè)屬性的模式。生成器首先為這些屬性分配一個(gè)全局順序，并將有序的屬性分成連續(xù)的屬性集，其大小在2～4之間。設(shè)定(X，Y)為這種分割中的屬性集，生成器從與域基數(shù)設(shè)置相關(guān)的范圍內(nèi)采樣一個(gè)值v，并將X中的每個(gè)屬性分配一個(gè)域，以便屬性值的笛卡爾積對應(yīng)于該值，還會將Y的定義域大小賦值為v。在上述過程引入函數(shù)依賴，生成了(X，Y)組，其他剩余的屬性集執(zhí)行條件概率分布，生成相關(guān)屬性集。生成合成數(shù)據(jù)集的具體設(shè)置如表3所示。

表3 合成數(shù)據(jù)集設(shè)置

向已知給定函數(shù)依賴的干凈合成數(shù)據(jù)集中引入噪聲的具體方法為：將給定的干凈數(shù)據(jù)集中的元組數(shù)量標(biāo)記為n，注入的錯(cuò)誤率標(biāo)記為σ，生成噪聲數(shù)據(jù)的方法為元組t中任意一個(gè)屬性值t[a]改成t[a']。其中a，a'∈A并且a≠a'，也就是用該屬性在數(shù)據(jù)集中值域的其他取值來替換該值，注入的噪聲數(shù)據(jù)數(shù)量為n×σ。在許多案例和研究中，真實(shí)數(shù)據(jù)集的錯(cuò)誤率不高于30%，因此本實(shí)驗(yàn)中將噪聲數(shù)據(jù)錯(cuò)誤率的最大值設(shè)置為30%。

用F1-score來評估挖掘近似函數(shù)依賴方法的準(zhǔn)確性，其中，精確率是指輸出的結(jié)果中所包含的真實(shí)FD條數(shù)占所有輸出結(jié)果的FD條數(shù)的比率，記為Precision；召回率是指輸出的結(jié)果中所包含的真實(shí)FD條數(shù)占全部真實(shí)FD條數(shù)的比率，記為Recall；F1-score由準(zhǔn)確率和召回率計(jì)算得到，定義為

4.2 真實(shí)數(shù)據(jù)實(shí)驗(yàn)對比分析

將本文提出的方法標(biāo)記為MB_AFD，并與以下目前比較流行的最優(yōu)晶格遍歷算法PY‐RO、TANE，模式驅(qū)動類算法DFD以及文獻(xiàn)［8］提到的數(shù)據(jù)驅(qū)動類算法FDEP進(jìn)行實(shí)驗(yàn)對比。真實(shí)數(shù)據(jù)集中存在自然發(fā)生的缺失值錯(cuò)誤，為了進(jìn)行定量分析，需測量出各方法發(fā)現(xiàn)的所有近似函數(shù)依賴，并與真實(shí)的函數(shù)依賴進(jìn)行對比分析。通過表4可以發(fā)現(xiàn)其他4種方法的準(zhǔn)確率只有2%～3%，造成這種情況的原因是PY‐RO、TANE等方法可以為數(shù)據(jù)集找到所有語義上成立的函數(shù)依賴，通常情況下挖掘出的函數(shù)依賴的數(shù)量都是成百上千的，與此同時(shí)挖掘出來的函數(shù)依賴大多都是過擬合或虛假FD，并不是真實(shí)存在的。而MB_AFD則根據(jù)每個(gè)屬性的馬爾科夫毯縮小左部決定集的候選空間，可以看出MB_AFD很好地刪除了無關(guān)屬性，并剪枝了過多無用的節(jié)點(diǎn)，只在馬爾科夫毯的頂峰節(jié)點(diǎn)的子集中進(jìn)行向下泛化驗(yàn)證，得到最小的近似函數(shù)依賴，從而解決了過擬合的問題。從實(shí)驗(yàn)結(jié)果來看，MB_AFD的精確率、召回率以及F1-score的值遠(yuǎn)遠(yuǎn)高于其他4種方法，對比試驗(yàn)結(jié)果如表4所示。

表4 真實(shí)數(shù)據(jù)集的對比實(shí)驗(yàn)結(jié)果

4.3 合成數(shù)據(jù)集實(shí)驗(yàn)對比分析

為了研究合成數(shù)據(jù)集中不同因素對近似函數(shù)依賴挖掘方法的性能影響，通過改變表3中輸入合成數(shù)據(jù)集的關(guān)鍵因素進(jìn)行實(shí)驗(yàn)探究。

相應(yīng)的實(shí)驗(yàn)結(jié)果如圖5所示，圖5a～5d表明算法在低噪聲合成數(shù)據(jù)集上的F1-score，MB_AFD在不同數(shù)據(jù)集的得分始終優(yōu)于其他方法，而且與其他方法相比，MB_AFD受屬性數(shù)量和元組數(shù)量的影響較小，且MB_AFD對于低噪聲的數(shù)據(jù)保持良好的F1-score。PYRO、TANE以及DFD傾向于在合成數(shù)據(jù)集中生成接近完整的FD圖，而不是稀疏的FD圖，這使得PYRO、TANE和DFD都具有高召回率，但是精度低、F1-score低。算法FDEP在元組數(shù)量很多的情況下，表現(xiàn)出較差的伸縮性，比較元組對的時(shí)間過長，不能在短時(shí)間內(nèi)終止程序，測試的結(jié)果也是F1-score值低。

圖5 5種方法合成數(shù)據(jù)的對比實(shí)驗(yàn)分析圖

4.4 不同噪聲對實(shí)驗(yàn)的影響

為了對比上述所提及的方法在不同錯(cuò)誤率噪聲數(shù)據(jù)集中的準(zhǔn)確性，首先通過向給定干凈的合成數(shù)據(jù)集中隨機(jī)注入錯(cuò)誤，人為地在數(shù)據(jù)集中引入噪聲，得到注入錯(cuò)誤率從5%到30%均勻變化的噪聲數(shù)據(jù)集；然后分別求解出這5種方法在不同錯(cuò)誤率的噪聲數(shù)據(jù)集中挖掘的近似函數(shù)依賴結(jié)果；最后在同一錯(cuò)誤率的噪聲數(shù)據(jù)集中對比每種算法的F1-score。

實(shí)驗(yàn)結(jié)果如圖6所示，通過改變合成數(shù)據(jù)集中的錯(cuò)誤比率進(jìn)行實(shí)驗(yàn)探究，本文提出的MB_AFD方法在每個(gè)噪聲數(shù)據(jù)集上都表現(xiàn)很穩(wěn)定，并未受到數(shù)據(jù)中的不同錯(cuò)誤率的噪聲數(shù)據(jù)影響，F(xiàn)1-score值始終未發(fā)生改變，說明MB_AFD對于噪聲數(shù)據(jù)并不敏感。然而，其他4種方法在不同錯(cuò)誤率的噪聲數(shù)據(jù)中的F1-score會受到輕微的影響，而且F1-score值也非常低。究其原因，主要是其他4種方法仍保持不斷地挖掘語義上成立的近似函數(shù)依賴，導(dǎo)致挖掘出的FD數(shù)量是龐大的。雖然在不同噪聲數(shù)據(jù)集中挖掘出來的近似函數(shù)依賴數(shù)量存在變化，但是相比于挖掘出來的近似函數(shù)依賴集總體數(shù)量還是很微弱的，因而只是有輕微的波動。而MB_AFD的F1-score不但保持不變，而且準(zhǔn)確率和召回率也很高，原因是MB_AFD先在噪聲數(shù)據(jù)集上采樣并訓(xùn)練貝葉斯網(wǎng)絡(luò)，生成的馬爾科毯并未受到數(shù)據(jù)中的噪聲影響，說明MB_AFD對于噪聲數(shù)據(jù)集有更好的魯棒性，并允許更低的樣本復(fù)雜性。因此，MB_AFD在不同錯(cuò)誤率的噪聲數(shù)據(jù)中依然可以更準(zhǔn)確地發(fā)現(xiàn)近似函數(shù)依賴。

圖6 不同噪聲數(shù)據(jù)集實(shí)驗(yàn)結(jié)果

綜上，本文提出的基于馬爾科夫毯的近似函數(shù)依賴挖掘算法比當(dāng)前最優(yōu)的模式驅(qū)動類算法和數(shù)據(jù)驅(qū)動類算法的F1-score更高，并且當(dāng)數(shù)據(jù)集中存在噪聲時(shí)，并未影響MB_AFD的性能。MB_AFD通過創(chuàng)建屬性的馬爾科夫毯并不斷向下泛化驗(yàn)證，不僅縮小了近似函數(shù)依賴左部決定集的候選空間，還解決了過擬合問題，使得MB_AFD方法更穩(wěn)定，精確率和F1-score更高。

5 結(jié)論

針對在數(shù)據(jù)集中挖掘最小函數(shù)依賴的問題，本文提出了一種基于馬爾科夫毯的近似函數(shù)依賴挖掘的算法，通過引入右部屬性的馬爾科夫毯，鎖定左部決定集搜索空間的峰值。通過剪枝左部決定集的搜索空間，解決挖掘近似函數(shù)依賴的過擬合問題，同時(shí)提出了基于馬爾科夫毯挖掘近似函數(shù)依賴的框架。實(shí)驗(yàn)表明本方法能夠高效且高精確率地挖掘出最小的近似函數(shù)依賴，同時(shí)還適用于錯(cuò)誤率不同的噪聲數(shù)據(jù)。