基于相關(guān)性分析的不完整數(shù)據(jù)函數(shù)依賴挖掘方法

尹詩寧 張安珍 夏秀峰

摘 要：函數(shù)依賴（FD）挖掘方法通常專注于發(fā)現(xiàn)所有滿足函數(shù)依賴語法特征的結(jié)果，在數(shù)據(jù)不完整的情況下常導(dǎo)致大量成立但無意義的FD。針對(duì)挖掘無效FD的問題，提出基于相關(guān)性分析的不完整數(shù)據(jù)FD挖掘方法。利用概率圖模型構(gòu)建具有缺失值屬性的概率分布，通過相關(guān)性分析捕捉屬性之間的關(guān)聯(lián)關(guān)系，避免枚舉所有可能性，以挖掘具有統(tǒng)計(jì)學(xué)意義的FD。實(shí)驗(yàn)結(jié)果表明，該方法可以更準(zhǔn)確地定位到有意義的FD，與最先進(jìn)的FD發(fā)現(xiàn)方法相比，F(xiàn)1分?jǐn)?shù)平均提高1.5倍。

關(guān)鍵詞：函數(shù)依賴；相關(guān)性分析；不完整數(shù)據(jù)

中圖分類號(hào)：TP301?? 文獻(xiàn)標(biāo)志碼：A??? 文章編號(hào)：1001-3695（2024）05-013-1368-06

doi： 10.19734/j.issn.1001-3695.2023.09.0451

Correlation analysis for discovering functional dependencies in incomplete data

Abstract：Function dependency （FD） discovery methods typically focus on identifying all results that satisfy the syntax features of function dependencies. In the case of incomplete data， it often results in a significant number of established but meaningless FD. In response to the issue of discovering invalid FD， this paper proposed a method for incomplete data FD discovery based on correlation analysis. It constructed a probability distribution with attributes containing missing values using a probability graph model， captured the relationships between attributes through correlation analysis， avoided enumerating all possibili-ties， to discover FD with statistical significance. The experimental results show that the proposed method can more accurately pinpoint meaningful FD， more accurately， with an average F1-score improvement of 1.5 times compared to state-of-the-art FD discovery methods.

Key words：functional dependency; correlation analysis; incomplete data

0 引言

函數(shù)依賴（functional dependency，F(xiàn)D）是數(shù)據(jù)庫管理系統(tǒng)中的一個(gè)關(guān)鍵概念，用于描述數(shù)據(jù)庫表中字段之間的關(guān)系，在許多領(lǐng)域有著廣泛應(yīng)用，如數(shù)據(jù)庫設(shè)計(jì)、數(shù)據(jù)清洗、特征選擇等。近年來，研究人員圍繞FD挖掘展開了大量研究工作，這些研究工作通常假設(shè)數(shù)據(jù)是完整的。然而，真實(shí)應(yīng)用中的數(shù)據(jù)通常存在大量的缺失值，如何在不完整數(shù)據(jù)中挖掘出正確的FD是一個(gè)亟待解決的問題。

不難發(fā)現(xiàn)，不完整數(shù)據(jù)上的FD挖掘比完整數(shù)據(jù)上的FD挖掘更具挑戰(zhàn)性。一方面，若直接使用現(xiàn)有的完整數(shù)據(jù)上的FD挖掘方法在不完整數(shù)據(jù)上進(jìn)行挖掘，將導(dǎo)致結(jié)果中出現(xiàn)大量過擬合的FD規(guī)則。這是由于現(xiàn)有的FD挖掘方法通常根據(jù)FD的語法特征進(jìn)行挖掘，導(dǎo)致所有滿足左部取值相同時(shí)右部取值也相同的規(guī)則出現(xiàn)在結(jié)果集中。例如，在只有幾十個(gè)屬性的數(shù)據(jù)集上，會(huì)找出成百上千條FD［1］，這些FD中大部分沒有任何統(tǒng)計(jì)學(xué)意義。另一方面，現(xiàn)有的不完整數(shù)據(jù)上，F(xiàn)D挖掘方法［2］通常將所有滿足近似度閾值的FD規(guī)則挖掘出來，然后再根據(jù)缺失值的概率分布驗(yàn)證每個(gè)FD規(guī)則的真?zhèn)巍Ｈ欢?，為了保證在不完整數(shù)據(jù)上所有真實(shí)FD規(guī)則都被挖掘出來，需要設(shè)置一個(gè)很大的近似度閾值，最壞情況下，閾值等于缺失的元組數(shù)量，此時(shí)，結(jié)果中將出現(xiàn)大量假的FD規(guī)則。

為此，本文提出基于相關(guān)性分析的不完整數(shù)據(jù)FD挖掘方法，利用FD的語義特征指導(dǎo)挖掘過程，在處理缺失值的同時(shí)，挖掘出具有統(tǒng)計(jì)學(xué)意義的函數(shù)依賴。具體過程如下：首先，采用概率圖模型建立各個(gè)屬性的概率分布，給出缺失值填充方案正確性概率的計(jì)算模型。其次，利用相關(guān)性分析捕捉每對(duì)屬性之間的關(guān)聯(lián)關(guān)系，保留具有強(qiáng)關(guān)聯(lián)性的屬性，并組合中度關(guān)聯(lián)的屬性形成新的候選FD集合。最后，對(duì)候選FD進(jìn)行細(xì)化，通過檢查互補(bǔ)的、未經(jīng)驗(yàn)證的依賴候選項(xiàng)，直到找到所有最小FD。

綜上所述，本文的主要貢獻(xiàn)如下：

a）提出了一種基于相關(guān)性分析的近似函數(shù)依賴挖掘方法，利用統(tǒng)計(jì)學(xué)概念快速定位具有相關(guān)性的屬性，使得發(fā)現(xiàn)的FD結(jié)果可解釋性更好。

b）建立了一種針對(duì)缺失值的概率模型，計(jì)算缺失值的取值概率，從而避免了缺失值解釋的單一性可能引發(fā)的誤差。

c）通過對(duì)候選FD細(xì)化，檢查互補(bǔ)的、未經(jīng)驗(yàn)證的依賴候選項(xiàng)，直到找到所有最小FD，確保輸出的結(jié)果是最小且有意義的。

1 相關(guān)工作

常見的完整性約束包括函數(shù)依賴規(guī)則［3～5］、包含依賴規(guī)則［6］、順序依賴關(guān)系［7］等，其中最常用的是函數(shù)依賴規(guī)則，得到了學(xué)術(shù)界的廣泛研究。它有許多應(yīng)用，如維護(hù)數(shù)據(jù)質(zhì)量［8］、模式標(biāo)準(zhǔn)化［9］、修復(fù)數(shù)據(jù)不一致［10，11］等。

以TANE［12］為代表的行高效算法，使用分層搜索策略將FD的搜索空間建模為屬性格。晶格從較小的屬性集到較大的屬性集逐級(jí)遍歷，并使用剪枝技術(shù)縮減搜索空間，以發(fā)現(xiàn)精確和近似的FD。后續(xù)算法Fun［13］、FD-mine［14］、DFD［15］引入了不同的剪枝和格遍歷策略。該類方法對(duì)數(shù)據(jù)量有良好的擴(kuò)展性。

列高效算法FDep［16］、DepMiner［17］和FastFDs［18］，通過計(jì)算元組的不一致集確定FD的屬性組合，以便生成兩組不同的屬性子集，從這些屬性子集派生候選FD。這類方法對(duì)屬性數(shù)量有良好擴(kuò)展，但復(fù)雜度是數(shù)據(jù)量的平方。

混合算法［19，20］在行高效算法和列高效算法之間切換，結(jié)合前兩種算法的優(yōu)點(diǎn)，具體地說，采樣后利用列高效算法得到非函數(shù)依賴，使用行高效部分進(jìn)行驗(yàn)證，在元組和屬性數(shù)量都增加的情況下有更好的伸縮性，但它不適用于近似函數(shù)依賴關(guān)系。

CORDS考慮相關(guān)性以獲得軟FD［21］，只研究LHS上具有單一屬性的FD，提出了一種基于示例的方法，該方法使用系統(tǒng)編目檢索列中不同值的數(shù)量。然而，CORDS中考慮的共現(xiàn)度量發(fā)現(xiàn)了邊際依賴，而不是對(duì)應(yīng)于真正FD的條件獨(dú)立。

上述方法都是基于共現(xiàn)頻率的，當(dāng)左部屬性多時(shí)容易出現(xiàn)過擬合的情況。為此提出了結(jié)構(gòu)學(xué)習(xí)方法FDX［22］，依賴于稀疏回歸，對(duì)樣本進(jìn)行結(jié)構(gòu)學(xué)習(xí)，通過從原始數(shù)據(jù)獲取采樣的元組對(duì)的值差異。假設(shè)屬性之間有一個(gè)全局優(yōu)先級(jí)，通過逆協(xié)方差矩陣得到FD。

當(dāng)數(shù)據(jù)中有缺失值時(shí)，現(xiàn)有FD挖掘方法通常采用以下三種策略。第一種策略是忽略不完整的元組［23］，直接在完整元組集合上挖掘FD規(guī)則。然而，這種方法存在一個(gè)嚴(yán)重問題，結(jié)果中可能包含大量虛假的FD規(guī)則。這些虛假規(guī)則在完整元組集合上成立，但在對(duì)應(yīng)的不完整元組集合上不成立。第二種策略是根據(jù)給定的缺失值語義來挖掘FD規(guī)則［24］。常見的缺失值語義有兩種：缺失值取值都相同（NULL-EQ）和缺失值取值都不同（NULL-NOT-EQ）。然而，真實(shí)的缺失值取值通常更加復(fù)雜，可能部分相同、部分不同，這導(dǎo)致在采用NULL-EQ語義時(shí)可能會(huì)挖掘出大量虛假的FD規(guī)則，而采用NULL-NOT-EQ語義時(shí)可能會(huì)錯(cuò)過真正的FD規(guī)則。第三種策略是首先填充缺失值，然后在填充后的完整數(shù)據(jù)上進(jìn)行FD挖掘。然而，這種方法的準(zhǔn)確性嚴(yán)重依賴于缺失值填充方法的準(zhǔn)確性，不準(zhǔn)確的填充可能導(dǎo)致錯(cuò)誤的FD規(guī)則。

為了應(yīng)對(duì)這些問題，Berti-quille等人［2］提出了一種方法，利用現(xiàn)有的近似FD挖掘方法在不完整數(shù)據(jù)上找出所有可能的近似FD規(guī)則，然后計(jì)算每個(gè)規(guī)則的概率，只保留概率較高的FD規(guī)則。然而，這種方法需要挖掘出所有近似度的FD規(guī)則才能保證真實(shí)FD規(guī)則不會(huì)被遺漏，而且后續(xù)的概率驗(yàn)證階段代價(jià)非常大。之前關(guān)于FD發(fā)現(xiàn)的工作并沒有試圖分析缺失值數(shù)據(jù)上有意義的函數(shù)依賴，找出大量近似成立但無效的FD。

現(xiàn)有的解決方案沒有充分利用屬性之間的關(guān)聯(lián)關(guān)系，而是系統(tǒng)地枚舉有可能的FD規(guī)則并逐一驗(yàn)證，導(dǎo)致候選FD挖掘結(jié)果效率低且沒有找到有意義的依賴關(guān)系。本文引入了相關(guān)性分析的方法提高函數(shù)依賴挖掘的準(zhǔn)確性，大大減少候選FD的規(guī)模，有效避免了屬性數(shù)量過多導(dǎo)致的過擬合現(xiàn)象。通過對(duì)缺失值建立概率模型，規(guī)避了僅考慮缺失值解釋的單一性可能帶來的誤差問題。

2 預(yù)備知識(shí)及問題定義

定義1 函數(shù)依賴（functional dependency，F(xiàn)D）。給定屬性集D上的關(guān)系模式R。R上的一個(gè)FD表示為X→Y，其中XR，Y∈R，表示X中的所有元組唯一地決定Y中的值。更正式地說，設(shè)ti［Y］是屬性Y中的元組ti的值；t，t′∈r，t［X］=t′［X］t［Y］=t′［Y］，稱X為FD的左部（LHS），Y為FD的右部（RHS）。

例1 以表1為例，表1為部分美國醫(yī)院信息，主要包括醫(yī)院編號(hào)、名稱所在地、代碼等，假設(shè)有FD：ProviderNumber→HospitalName，表示數(shù)據(jù)集中所有ProviderNumber取值相同的元組，對(duì)應(yīng)屬性HospitalName的取值一定相同。如果不相等，則該數(shù)據(jù)違反函數(shù)依賴規(guī)則。

定義2 空語義。將數(shù)據(jù)集中的缺失值表示為NULL值，用⊥表示。如前所述，在處理NULL值時(shí)，傳統(tǒng)上提出了兩種語義：第一種解釋，NULL-EQ，表示為（⊥=⊥），認(rèn)為所有缺失值都是相同的；第二種語義，NULL-NOT-EQ，表示（⊥≠⊥），認(rèn)為每個(gè)缺失值都是不同的。這兩種語義有不同的動(dòng)機(jī)，并導(dǎo)致發(fā)現(xiàn)不同的FD集合。

定義3 卡方檢驗(yàn)。卡方檢驗(yàn)是一種用于檢驗(yàn)兩個(gè)分類變量之間是否存在顯著關(guān)聯(lián)性的統(tǒng)計(jì)方法，基于觀察值與期望值之間的差異來判斷兩個(gè)變量是否獨(dú)立。卡方檢驗(yàn)的原假設(shè)是兩個(gè)變量是獨(dú)立的，備擇假設(shè)是兩個(gè)變量之間存在關(guān)聯(lián)。

定義4 Cramers V系數(shù)。Cramers V是用于衡量兩個(gè)分類變量之間關(guān)聯(lián)性強(qiáng)度的指標(biāo)。它是從卡方統(tǒng)計(jì)量中派生出來的，用于標(biāo)準(zhǔn)化卡方統(tǒng)計(jì)量，以便在不同的表格尺寸和自由度下進(jìn)行比較。Cramers V的取值在0～1，值越接近1，表示兩個(gè)變量之間的關(guān)聯(lián)性越強(qiáng)。Cramers V的計(jì)算公式為

其中：χ2是卡方統(tǒng)計(jì)量；n是樣本總數(shù)；k是第一個(gè)分類變量的類別數(shù)；r是第二個(gè)分類變量的類別數(shù)?？ǚ綑z驗(yàn)用于檢驗(yàn)分類變量之間的關(guān)聯(lián)性是否顯著，而Cramers V則是一種衡量分類變量關(guān)聯(lián)性強(qiáng)度的標(biāo)準(zhǔn)化指標(biāo)。

3 不完整數(shù)據(jù)上近似函數(shù)依賴挖掘方法

針對(duì)不完整數(shù)據(jù)的函數(shù)依賴挖掘問題，本文提出基于相關(guān)性分析的近似函數(shù)依賴挖掘框架，旨在提高不完整近似函數(shù)依賴挖掘的效率和可解釋性，緩解過擬合問題。

3.1 不完整數(shù)據(jù)上近似函數(shù)依賴挖掘框架

本文提出的不完整數(shù)據(jù)上近似函數(shù)依賴挖掘方法包括建立概率模型、相關(guān)性分析和候選FD規(guī)則驗(yàn)證與細(xì)化三個(gè)步驟，如圖1所示。輸入為帶有缺失值的數(shù)據(jù)集D和錯(cuò)誤閾值，輸出為最小且非平凡的函數(shù)依賴集合。

a）建立概率模型：首先，在給定的不完整數(shù)據(jù)集上訓(xùn)練貝葉斯網(wǎng)，學(xué)習(xí)屬性之間的相關(guān)關(guān)系以及條件概率分布；其次，建模缺失值填充方案正確性概率為P（A|E），即給定完整部分屬性取值時(shí)，有缺失值屬性取值的概率；最后，利用貝葉斯推理預(yù)測不完整數(shù)據(jù)的所有取值概率。

b）相關(guān)性分析：利用上一步輸出對(duì)屬性之間進(jìn)行相關(guān)性分析，對(duì)相互獨(dú)立的屬性進(jìn)行剪枝，減小候選FD的規(guī)模，剩下的屬性進(jìn)行逐層搜索，從底層單個(gè)節(jié)點(diǎn)開始，快速定位候選的FD。

c）候選FD規(guī)則驗(yàn)證與細(xì)化：如果LHS和RHS之間有強(qiáng)相關(guān)性，則認(rèn)為這樣的節(jié)點(diǎn)是最小的決定集。對(duì)于其他的節(jié)點(diǎn)進(jìn)行組合，進(jìn)一步驗(yàn)證相關(guān)性。如果不滿足閾值，就繼續(xù)添加屬性細(xì)化，直到滿足閾值或者無法繼續(xù)添加屬性，得到完整的FD集合。

3.2 統(tǒng)計(jì)學(xué)習(xí)與推理

本節(jié)給出了缺失值概率模型和概率推理方法，目的是根據(jù)缺失值取值的概率分布分析屬性之間的相關(guān)性。

為了推斷缺失值的概率，使用了一個(gè)廣泛使用的概率圖模型——貝葉斯網(wǎng)絡(luò)，它提供了一種簡潔地描述屬性的概率分布方法。根據(jù)貝葉斯網(wǎng)絡(luò)中的局部馬爾可夫性質(zhì)，每個(gè)變量在其父變量的條件下都與非子變量無關(guān)。因此，影響一個(gè)變量取值分布的變量都在馬爾可夫毯中，通過觀察有缺失值的屬性A的馬爾可夫毯上的屬性，可以推斷出屬性A的可能取值范圍，其他屬性對(duì)屬性A的取值不會(huì)產(chǎn)生直接影響。將有缺失值的屬性A作為查詢屬性，其他屬性E=attr（R）＼A為證據(jù)屬性集，通過證據(jù)屬性集預(yù)測查詢屬性各個(gè)取值的概率。

對(duì)于有缺失值屬性A的元組t，有t［E］=t［E1，E2，…，EL］和t［A］。設(shè)SE=DOM（E1）×DOM（E2）×…×DOM（EL）表示t的證據(jù)屬性的空間，SA=DOM（A）表示t的查詢屬性的空間。假設(shè)根據(jù)SA×SE上的概率分布P（A，E）隨機(jī)生成元組。將t的缺失值概率建模為給定證據(jù)屬性值的查詢屬性值的條件概率，即P（A=t［A］|E=t［E］）（簡稱P（t［A］|t［E］）），根據(jù)貝葉斯定理可得

給定總體上的貝葉斯網(wǎng)絡(luò)，網(wǎng)絡(luò)中所有變量的聯(lián)合分布都可以因式分解為以其父變量為條件的單個(gè)密度函數(shù)的乘積。式（2）中的分子P（t［A］，t［E］），可以用式（3）來近似：

其中：父節(jié)點(diǎn)（Ej）表示Ej的父節(jié)點(diǎn)集。注意，由于所有屬性的值都是已知的，所以P（t［A］|parent（A））和P（t［Ej］|parent（Ej））是貝葉斯網(wǎng)絡(luò)中條件概率表（CPT）中的常量。當(dāng)涉及式（2）中的分母P（t［E］）時(shí)，推理變得有點(diǎn)復(fù)雜。注意，P（t［E］）是證據(jù)屬性的邊際分布，可以通過邊際化查詢屬性上的聯(lián)合分布來計(jì)算，如式（4）所示。

P（t［E］）=P（A，t［E］）（4）

當(dāng)同一元組t上存在多個(gè)缺失值的情況，每個(gè)查詢屬性Ai的分布通常不獨(dú)立于其他屬性。事實(shí)上，Ai的分布取決于其馬爾可夫毯中屬性的聯(lián)合分布。因此，提出在Ai的馬爾可夫毯的基礎(chǔ)上對(duì)Ai的域進(jìn)行剪枝。具體地說，使用MB（A）表示A的馬爾可夫毯，且MB（A）=MB（A1）∪MB（A2）∪…∪MB（Ak）是所有查詢變量的馬爾可夫毯的交集。然后使用MB（A）中的證據(jù)屬性對(duì)A的域剪枝，即考慮與E∪MB（A）的值在數(shù)據(jù)集中同時(shí)出現(xiàn)的查詢屬性值。

算法1 不完整數(shù)據(jù)概率推理算法

在算法1中，輸入為關(guān)系模式R上的不完整數(shù)據(jù)集D，輸出為帶有概率的完整數(shù)據(jù)集D′。首先在不完整數(shù)據(jù)集D上訓(xùn)練貝葉斯網(wǎng)絡(luò)，得到屬性之間的關(guān)系和概率表，并初始化查詢屬性集合Q、證據(jù)屬性集合E以及帶概率的完整數(shù)據(jù)集D′（第1、2行），判斷t［Ai］是否為空，并將空值屬性添加到查詢屬性Q中（第4、5行），其次查找Q中所有屬性的馬爾可夫毯屬性使其相交，得到共同馬爾可夫毯屬性MB（Q），并篩選出t［Ai］的所有可能填充的值V（第6～9行），然后將t［E∩MB（Q）］在D中至少出現(xiàn)一次的查詢屬性值添加到q_set，并利用式（3）計(jì)算P（t［E］）（第10～14行），遍歷V中屬性值利用式（2）計(jì)算P（t［Q］，t［E］）（第15～17行），最后計(jì)算P［ti］，將其和ti添加到D′中（第18、19行）。

3.3 相關(guān)性分析

本節(jié)介紹了一種基于卡方分布和Cramers V的方法，用于量化屬性之間的相關(guān)性，卡方統(tǒng)計(jì)量衡量了觀察值與期望值之間的偏離程度，當(dāng)兩個(gè)屬性相互獨(dú)立時(shí)，卡方值接近于零。Cramers V是一種用于衡量兩個(gè)分類變量之間關(guān)聯(lián)性強(qiáng)度的標(biāo)準(zhǔn)化指標(biāo)，派生自卡方統(tǒng)計(jì)量，其目的是使不同表格尺寸和自由度下的卡方統(tǒng)計(jì)量可進(jìn)行比較。Cramers V值為0～1，數(shù)值越接近1，說明兩個(gè)變量之間的關(guān)聯(lián)性越強(qiáng)?？ǚ綑z驗(yàn)用于驗(yàn)證分類變量之間的關(guān)聯(lián)性是否具有顯著性，而Cramers V則進(jìn)一步提供了這種關(guān)聯(lián)性的強(qiáng)度度量。

定理1 在干凈數(shù)據(jù)集中，X→Y是一個(gè)FD，則Cramers V值為1。

當(dāng)X和Y的頻數(shù)分布集中在一個(gè)單元時(shí)，會(huì)導(dǎo)致偏離程度較大。定理1解釋了隨機(jī)變量之間的相關(guān)性可以用Cramers V來表示，因此求解屬性之間的函數(shù)依賴關(guān)系等同于求解Cramers V的值，而這可以從觀察到的數(shù)據(jù)樣本中獲取。FD發(fā)現(xiàn)，問題可以看作是在屬性之間尋找強(qiáng)相關(guān)的屬性，當(dāng)屬性之間存在強(qiáng)相關(guān)性時(shí)，則稱它們是一個(gè)函數(shù)依賴。通過計(jì)算屬性之間的關(guān)聯(lián)關(guān)系，而不是直接遍歷整個(gè)搜索空間，可以將函數(shù)依賴的發(fā)現(xiàn)問題簡化為尋找屬性之間的相關(guān)性。隨后，進(jìn)行逐層搜索，從底層開始，即單個(gè)屬性節(jié)點(diǎn)，計(jì)算給定右部屬性與其他屬性的Cramers V值，并選取了大于給定閾值的屬性對(duì)作為候選的函數(shù)依賴項(xiàng)。為了提高挖掘效率，采取了剪枝策略，即排除相互獨(dú)立的屬性；當(dāng)Cramers V值超過給定閾值時(shí)，將這兩個(gè)屬性視為強(qiáng)相關(guān)屬性，從而減小了候選函數(shù)依賴項(xiàng)的數(shù)量。

例2 圖2表示美國醫(yī)院數(shù)據(jù)集所有屬性之間的相關(guān)性分析熱圖，當(dāng)ProviderNumber和HospitalName完全獨(dú)立時(shí)，總體上的分布和某個(gè)取值上的分布情況應(yīng)該是相同的，當(dāng)ProviderNumber和HospitalName完全相關(guān)時(shí)，也就是說， ProviderNumber的值就可以唯一地確定一個(gè)HospitalName，這就是Cramers V可能出現(xiàn)的最高值，也就是函數(shù)依賴關(guān)系。

3.4 候選FD規(guī)則驗(yàn)證與細(xì)化

本節(jié)將詳細(xì)介紹對(duì)候選FD規(guī)則驗(yàn)證與細(xì)化的過程，其目的是找到所有最小的函數(shù)依賴集合。當(dāng)左部是多個(gè)屬性時(shí)，可以進(jìn)行細(xì)化操作而不會(huì)引入額外的誤差。為實(shí)現(xiàn)這一目標(biāo)，該過程執(zhí)行以下步驟：首先，對(duì)于關(guān)系模式R的每個(gè)屬性A，尋找以A為RHS的最小AFDs。其次，計(jì)算屬性A與attr（R）＼A的每個(gè)屬性的Cramers V值。如果屬性A與某個(gè)屬性之間存在強(qiáng)相關(guān)性，確定該屬性為FD并報(bào)告它。如果屬性之間是中度相關(guān)關(guān)系，則將它們存入候選項(xiàng)中進(jìn)行組合，直到無法從候選集中添加屬性。在此過程中，不斷剪枝相互獨(dú)立的屬性，并組合中度關(guān)聯(lián)的屬性，以確保找到的屬性集合都具有相關(guān)性。

在分析關(guān)系模式R時(shí)，每個(gè)候選RHS屬性A都需要被過濾，以確定是否有關(guān)聯(lián)關(guān)系。該過濾需要計(jì)算Cramers V值，以確定每個(gè)候選左部屬性是否適合作為FD的左部候選項(xiàng)。如果某個(gè)候選左部屬性被中度關(guān)聯(lián)的屬性作為細(xì)化候選，則可以使用算法2來執(zhí)行細(xì)化，用于生成給定關(guān)系數(shù)據(jù)集D′的下一層級(jí)的FD。逐步增加屬性組合的規(guī)模，繼續(xù)計(jì)算它們之間的相關(guān)性，直到滿足閾值或不能繼續(xù)添加屬性。

算法2 候選FD規(guī)則驗(yàn)證與細(xì)化算法

算法2接受一個(gè)帶有概率的完整數(shù)據(jù)集D′作為輸入，并輸出一組形式為X→Y的FD。在算法的開始，初始化一個(gè)用于存儲(chǔ)候選依賴項(xiàng)的新字典結(jié)構(gòu)M以及一個(gè)空集合FD，用于存儲(chǔ)最終的FD集合（第1行）。接下來，算法遍歷關(guān)系模式R中的每個(gè)屬性，并針對(duì)每個(gè)屬性A遍歷attr（R）＼A中的屬性X（第2行）。通過調(diào)用函數(shù)計(jì)算X和A屬性之間的Cramers V（第6行），與上限閾值Vupper比較確保是一個(gè)FD，并將它儲(chǔ)存在集合FD中（第7、8行），例如圖2中的屬性B為依賴項(xiàng)，因此可以將B的超集剪枝。如果計(jì)算得到的Cramers V在上限閾值Vupper和下限閾值Vlower之間，則將屬性X添加到候選依賴項(xiàng)M中，就像圖2中的屬性{A，C，D}，只需要對(duì)中度關(guān)聯(lián)的屬性進(jìn)行細(xì)化，這是潛在的最小依賴項(xiàng)，如果遞歸產(chǎn)生最小的函數(shù)依賴項(xiàng)，則會(huì)立即報(bào)告它。

對(duì)于候選依賴項(xiàng)進(jìn)入細(xì)化部分，從候選依賴項(xiàng)M中選擇一個(gè)沒有被修剪的候選組合，向它添加M中單個(gè)屬性，組成一個(gè)沒有被修剪過的新候選項(xiàng)（第11行），在圖3中細(xì)化訪問的ACD是一個(gè)函數(shù)依賴項(xiàng)，并將它儲(chǔ)存在集合FD中（第14～16行）。如果錯(cuò)誤地假設(shè)ACD是一個(gè)依賴項(xiàng)，將ACD添加到候選項(xiàng)M中，并繼續(xù)對(duì)ACD進(jìn)行細(xì)化（第18行），直到無法從候選項(xiàng)中添加屬性，返回最終函數(shù)依賴項(xiàng)FD。與遍歷所有搜索空間相比，從單一屬性開始，對(duì)相互獨(dú)立的屬性剪枝，并對(duì)于中度關(guān)聯(lián)的屬性進(jìn)行組合，大大減少了候選FD的規(guī)模。

例3 對(duì)于表1，當(dāng)Stateavg作為右部屬性時(shí)，與State和 MeasureCode存在相關(guān)關(guān)系，且并非強(qiáng)相關(guān)性，將它們存入候選項(xiàng)中進(jìn)行組合。通過驗(yàn)證，確認(rèn){State，MeasureCode}與Stateavg為強(qiáng)相關(guān)關(guān)系，因此State，MeasureCode→Stateavg是一個(gè)FD。繼續(xù)驗(yàn)證所有候選項(xiàng)，直到滿足預(yù)設(shè)閾值或無法繼續(xù)添加屬性。

4 實(shí)驗(yàn)分析

本章通過實(shí)驗(yàn)，評(píng)估了在不完整數(shù)據(jù)上挖掘近似函數(shù)依賴的方法，并展示了在合成數(shù)據(jù)集上的性能實(shí)驗(yàn)結(jié)果。具體而言，本章將深入分析算法的準(zhǔn)確率（P）、召回率（R）以及F1分?jǐn)?shù)。

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

實(shí)驗(yàn)采用Java實(shí)現(xiàn)了優(yōu)化方法的編寫，命名為SFD，并與最先進(jìn)的挖掘語義FD的方法FDX進(jìn)行對(duì)比。

a）對(duì)比方法：FDX［20］是最先進(jìn)的查詢有意義的函數(shù)依賴，從統(tǒng)計(jì)學(xué)角度出發(fā)，將FD發(fā)現(xiàn)轉(zhuǎn)換為線性結(jié)構(gòu)化方程模型上的結(jié)構(gòu)學(xué)習(xí)問題，在處理噪聲數(shù)據(jù)集時(shí)更具有魯棒性。參數(shù)保留其默認(rèn)設(shè)置。

b）數(shù)據(jù)集：實(shí)驗(yàn)數(shù)據(jù)使用合成數(shù)據(jù)集，給定一個(gè)具有r屬性的關(guān)系模式。考慮類別型和數(shù)值型兩種常見模式的函數(shù)依賴。對(duì)于類別型的FD，首先為LHS中的每個(gè)屬性分配一個(gè)域dom（X），并將RHS的域分配為dom（Y）。然后，對(duì)于每個(gè)值x∈dom（X）隨機(jī)選擇一個(gè)值y∈dom（Y）作為其對(duì)應(yīng)的RHS值。如果LHS中有多個(gè)屬性，則將它們視為一個(gè)整體，并遵循與上述相同的流程。生成的樣本數(shù)量由分配給元組數(shù)量的參數(shù)t的值決定；對(duì)于數(shù)值型的FD，首先為LHS屬性分別分配一個(gè)域，dom（X1）和dom（X2）。屬性Y是FD的右部，使得X1+X2=Y。由于數(shù)值型函數(shù)依賴的可逆性質(zhì)，X1+X2→Y、Y－X1→X2、Y－X2→X1也成立。

c）缺失值：使用Uniform和Pareto兩種模式，注入從5%到30%的缺失值百分比。在Uniform模式下，將隨機(jī)注入的缺失值均勻分布在屬性集上；對(duì)于Pareto模式，在80%的屬性中隨機(jī)注入20%的缺失值，在其余20%的屬性中隨機(jī)注入80%的缺失值。

d）實(shí)驗(yàn)評(píng)價(jià)：為了評(píng)估算法對(duì)數(shù)據(jù)集檢測的準(zhǔn)確性，實(shí)驗(yàn)使用準(zhǔn)確率（P）定義在所有識(shí)別的FD中正確檢測到的真實(shí)FD的百分比，召回率（R）定義在所有實(shí)際FD中正確發(fā)現(xiàn)的真實(shí)FD的百分比；而F1分?jǐn)?shù)計(jì)算為2PR/（P+R），同時(shí)考慮了準(zhǔn)確率和召回率。F1分?jǐn)?shù)可以看作是模型準(zhǔn)確率和召回率的調(diào)和平均值，最大值為1，最小值為0。

4.2 實(shí)驗(yàn)分析

在本章實(shí)驗(yàn)中，通過改變輸入數(shù)據(jù)的不同關(guān)鍵因素，評(píng)估了提出的不完整數(shù)據(jù)上的近似函數(shù)依賴挖掘方法和其他方法在合成數(shù)據(jù)集中挖掘FD的性能。

4.2.1 評(píng)估FD挖掘方法對(duì)元組數(shù)量的拓展性

實(shí)驗(yàn)評(píng)估了元組數(shù)量對(duì)方法的擴(kuò)展性，生成了一組合成數(shù)據(jù)集，并比較了不同元組數(shù)量下的性能。為了確定算法在行數(shù)上的可擴(kuò)展性，使用了一個(gè)包含17列，缺失率為10%的合成數(shù)據(jù)集，在具有{1000、2000、5000、10000、20000、50000、100000}不同元組數(shù)量的數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn)，并在圖4中描述了結(jié)果。SFD在處理更多元組時(shí)展現(xiàn)出可擴(kuò)展性，隨著元組數(shù)量的增加，在準(zhǔn)確率、召回率和F1分?jǐn)?shù)上呈現(xiàn)出更好的表現(xiàn)。同時(shí)，兩種缺失值語義和跳過缺失元組的變化相對(duì)穩(wěn)定，相比之下，F(xiàn)DX無法識(shí)別具有環(huán)形結(jié)構(gòu)的依賴，即同一屬性既出現(xiàn)在一個(gè)規(guī)則的左部，又出現(xiàn)在另一個(gè)規(guī)則的右部，導(dǎo)致準(zhǔn)確率和召回率較低。

4.2.2 評(píng)估FD挖掘方法對(duì)缺失率的魯棒性

在Uniform模式下，實(shí)驗(yàn)評(píng)估了缺失值的百分比對(duì)方法的影響。使用了一個(gè)包含17列，10 000行合成數(shù)據(jù)集，并隨機(jī)將與參與真實(shí)函數(shù)依賴的屬性對(duì)應(yīng)的單元格翻轉(zhuǎn)為空值，以模擬高缺失率環(huán)境。通過控制“缺失率”設(shè)置來調(diào)整翻轉(zhuǎn)單元格百分比，并測量在{0.01，0.05，0.1，0.15，0.2，0.25，0.3}不同缺失率下各方法的性能表現(xiàn)。對(duì)比了兩種缺失值語義（⊥=⊥）和（⊥≠⊥），跳過缺失值所在的行與FDX方法，實(shí)驗(yàn)結(jié)果如圖5所示，在高缺失率的情況下，所有方法都受到影響而性能惡化。SFD始終保持相對(duì)穩(wěn)定且F1分?jǐn)?shù)優(yōu)于其他方法；對(duì)于兩種缺失值語義和跳過缺失元組，會(huì)挖掘出大量虛假的FD規(guī)則或錯(cuò)過真正的FD規(guī)則，導(dǎo)致準(zhǔn)確率、召回率和F1分?jǐn)?shù)偏低。FDX總體上仍有非常低的準(zhǔn)確率和召回率。

4.2.3 評(píng)估FD挖掘方法對(duì)缺失值分布的影響

現(xiàn)實(shí)世界中缺失值的分布通常是不均勻的，使用Pareto模式注入缺失值以模擬真實(shí)世界上的缺失值分布，如圖6所示。通過比較實(shí)驗(yàn)結(jié)果發(fā)現(xiàn)，與Uniform模式相同，當(dāng)缺失率過高時(shí)，所有方法的準(zhǔn)確率、召回率和F1分?jǐn)?shù)都會(huì)明顯降低。但提出的方法在F1分?jǐn)?shù)上優(yōu)于其他方法，并且在保持高召回率方面表現(xiàn)出色。由于FDX的列排序限制了屬性之間的優(yōu)先級(jí)，無法挖掘具有環(huán)形結(jié)構(gòu)的FD，可能會(huì)錯(cuò)過一些依賴關(guān)系，導(dǎo)致無法完整挖掘到所有存在的函數(shù)依賴，使得準(zhǔn)確率和召回率偏低。SFD通過基于相關(guān)性分析和概率模型的思想，更加靈活地捕捉屬性之間的關(guān)聯(lián)關(guān)系。

所提算法存在一些限制，其中最主要的限制是它無法發(fā)現(xiàn)數(shù)值型的FD。該算法專注于識(shí)別LHS和RHS之間的相關(guān)性，并且它不能進(jìn)行逆向推導(dǎo)，找到數(shù)值型的函數(shù)依賴。然而，在實(shí)際應(yīng)用中，用于數(shù)據(jù)清洗的函數(shù)依賴大多具有語義關(guān)系。未來的研究可以進(jìn)一步完善算法，以更好地滿足實(shí)際數(shù)據(jù)清洗的需求。

5 結(jié)束語

本文提出了一種語義FD發(fā)現(xiàn)方法，探討了現(xiàn)有的函數(shù)依賴挖掘方法在面對(duì)缺失值和語義關(guān)系時(shí)的局限性。為了克服這些問題，本文提出了一種基于統(tǒng)計(jì)學(xué)的FD挖掘方法，考慮屬性之間的關(guān)聯(lián)性，并利用概率圖模型對(duì)不完整數(shù)據(jù)進(jìn)行建模，可以在不完整數(shù)據(jù)上挖掘出有意義的函數(shù)依賴規(guī)則。利用屬性之間的關(guān)聯(lián)關(guān)系而不是遍歷所有的搜索空間來提高FD發(fā)現(xiàn)的準(zhǔn)確率和召回率。測試表明，提出的方法在合成數(shù)據(jù)集上得到了高準(zhǔn)確率和召回率。但當(dāng)數(shù)據(jù)集中的缺失率較高時(shí)，存在大量缺失信息，使得通過概率建模難以準(zhǔn)確捕捉屬性之間的真實(shí)語義關(guān)系。在處理大規(guī)模真實(shí)數(shù)據(jù)集時(shí)，算法的計(jì)算開銷較大。未來的研究可以致力于應(yīng)對(duì)這些挑戰(zhàn)，優(yōu)化算法以適應(yīng)高缺失率情況，并尋找更有效的方法來處理大規(guī)模真實(shí)數(shù)據(jù)集。

參考文獻(xiàn)：

［1］Kruse S，Naumann F. Efficient discovery of approximate dependencies ［J］. Proceedings of the VLDB Endowment，2018，11（7）： 759-772.

［2］Berti-quille L，Harmouch H，Naumann F，et al. Discovery of genuine functional dependencies from relational data with missing values ［J］. Proceedings of the VLDB Endowment，2018，11（8）： 880-892.

［3］張安珍，司佳宇，梁天宇，等. 規(guī)則與概率相結(jié)合的不一致數(shù)據(jù)子集修復(fù)方法 ［J/OL］. 軟件學(xué)報(bào)，2023. https：//doi. org/10. 13328/j.cnki.jos.006972. （Zhang Anzhen，Si Jiayu，Liang Tianyu，et al. Subset repair method combining rules and probabilities for inconsistent data ［J/OL］. Journal of Software，2023. https：//doi. org/10. 13328/j. cnki. jos. 006972.）

［4］Zheng Zheng，Zheng Longtao，Alipourlangouri M，et al. Contextual data cleaning with ontology functional dependencies ［J］. ACM Journal of Data and Information Quality，2022，14（3）： 1-26.

［5］Song Shaoxu，Gao Fei，Huang Ruihong，et al. Data dependencies extended for variety and veracity： a family tree ［J］. IEEE Trans on Knowledge and Data Engineering，2020，34（10）： 4717-4736.

［6］Kaminsky Y，Pena E H M，Naumann F. Discovering similarity inclusion dependencies ［J］. Proceedings of the ACM on Management of Data，2023，1（1）： 1-24.

［7］Schmidl S，Papenbrock T. Efficient distributed discovery of bidirectional order dependencies ［J］. The VLDB Journal，2022，31（1）： 49-74.

［8］Fan Wenfei，Geerts F. Uniform dependency language for improving data quality ［J］. IEEE Data Engineering Bulletin，2011，34（3）： 34-42.

［9］Papenbrock T，Naumann F. Data-driven schema normalization ［C］//Proc of the 20th International Conference on Extending Database Technology. 2017： 342-353.

［10］夏秀峰，劉朝輝，張安珍. 基于馬爾可夫毯的近似函數(shù)依賴挖掘算法 ［J］. 沈陽航空航天大學(xué)學(xué)報(bào)，2023，40（4）： 8-18. （Xia Xiufeng，Liu Zhaohui，Zhang Anzhen. Approximate functional depen-dence discovering algorithm based on Markov blanket ［J］. Journal of Shenyang Aerospace University，2023，40（4）： 8-18.）

［11］Beskales G，Ilyas I F，Golab L. Sampling the repairs of functional dependency violations under hard constraints ［J］. Proceedings of the VLDB Endowment，2010，3（1-2）： 197-207.

［12］Huhtala Y，Krkkinen J，Porkka P，et al. TANE： an efficient algorithm for discovering functional and approximate dependencies ［J］. The Computer Journal，1999，42（2）： 100-111.

［13］Novelli N，Cicchetti R. Functional and embedded dependency infe-rence： a data mining point of view ［J］. Information Systems，2001，26（7）： 477-506.

［14］Hong Yao，Hamilton H，Butz C. FD-Mine： discovering functional dependencies in a database using equivalences ［C］// Proc of IEEE International Conference on Data Mining. Piscataway，NJ： IEEE Press，2002： 729-732.

［15］Abedjan Z，Schulze P，Naumann F.DFD： efficient functional depen-dency discovery ［C］// Proc of the 23rd ACM International Confe-rence on Information and Knowledge Management. New York： ACM Press，2014： 949-958.

［16］Flach P A，Savnik I. Database dependency discovery： a machine learning approach ［J］. AI Communications，1999，12（3）： 139-160.

［17］Lopes S，Petit J M，Lakhal L. Efficient discovery of functional depen-dencies and Armstrong relations ［C］// Proc of International Confe-rence on Extending Database Technology. Berlin： Springer，2000： 350-364.

［18］Wyss C，Giannella C，Robertson E. FastFDs： a heuristic-driven，depth-first algorithm for mining functional dependencies from relation instances extended abstract ［C］// Proc of International Conference on Data Warehousing and Knowledge Discovery. Berlin：Springer，2001： 101-110.

［19］Papenbrock T，Naumann F. A hybrid approach to functional depen-dency discovery ［C］// Proc of International Conference on Management of Data. New York： ACM Press，2016： 821-833.

［20］Wei Ziheng，Link S. Discovery and ranking of functional dependencies ［C］// Proc of the 35th IEEE International Conference on Data Engineering. Piscataway，NJ： IEEE Press，2019： 1526-153.

［21］Ilyas I F，Markl V，Haas P，et al. CORDS： automatic discovery of correlations and soft functional dependencies ［C］// Proc of ACM SIGMOD International Conference on Management of Data. New York： ACM Press，2004： 647-658.

［22］Zhang Yunjia，Guo Zhihan，Rekatsinas T. A statistical perspective on discovering functional dependencies in noisy data ［C］// Proc of ACM SIGMOD International Conference on Management of Data. New York： ACM Press，2020： 861-876.

［23］Badia A，Lemire D. Functional dependencies with null markers ［J］. The Computer Journal，2015，58（5）： 1160-1168.

［24］Badia A，Lemire D. On desirable semantics of functional dependencies over databases with incomplete information ［J］. Fundamenta Informaticae，2018，158（4）： 327-352.