基于近鄰傳播聚類和TANE算法的高校數(shù)據(jù)中函數(shù)依賴的發(fā)現(xiàn)

黃永鑫，唐雪飛

(電子科技大學(xué) 信息與軟件工程學(xué)院，成都 610054)

0 引言

高校信息化經(jīng)過多年的發(fā)展，很多高校已積累了大量的業(yè)務(wù)和相關(guān)數(shù)據(jù)，數(shù)據(jù)不同于有形的產(chǎn)品，但同樣具有質(zhì)量這一概念，但是因?yàn)閿?shù)據(jù)質(zhì)量不高、冗余數(shù)據(jù)大量存在和數(shù)據(jù)可用性不高，使很多數(shù)據(jù)處理工作還需要通過人工來確保正確，浪費(fèi)了大量的人力和時(shí)間[1]。

我國教育領(lǐng)域已初步解決數(shù)據(jù)的有無問題。然而，大量數(shù)據(jù)仍未得以充分應(yīng)用，究其原因，除了教育工作者對(duì)數(shù)據(jù)價(jià)值重視不夠等主觀原因外，數(shù)據(jù)質(zhì)量不高、數(shù)據(jù)狀態(tài)不能適應(yīng)當(dāng)前教育發(fā)展也是重要的客觀原因[2]。

數(shù)據(jù)缺失是數(shù)據(jù)質(zhì)量問題的其中一種，在高校數(shù)據(jù)中，比如對(duì)于學(xué)工系統(tǒng)中的數(shù)據(jù)來說，造成數(shù)據(jù)缺失的原因可能是由于人工錄入失誤，也可能是在數(shù)據(jù)傳輸過程中造成了缺失。大量缺失值將使得從數(shù)據(jù)中發(fā)現(xiàn)出的數(shù)據(jù)質(zhì)量檢測(cè)規(guī)則不準(zhǔn)確，使得領(lǐng)域?qū)＜覠o法根據(jù)發(fā)現(xiàn)出的數(shù)據(jù)質(zhì)量檢測(cè)規(guī)則有效修復(fù)數(shù)據(jù)集中存在的臟數(shù)據(jù)等問題。若直接將含有缺失值的數(shù)據(jù)刪掉，會(huì)使得數(shù)據(jù)集中丟失的數(shù)據(jù)較多，進(jìn)而使得基于該數(shù)據(jù)集所作出的數(shù)據(jù)分析結(jié)果產(chǎn)生較大偏差。

在高校信息化建設(shè)的過程中，通過開展高校數(shù)據(jù)治理以提高數(shù)據(jù)質(zhì)量，可以有效提高數(shù)據(jù)價(jià)值，為組織決策的制定提供幫助。同時(shí)，通過對(duì)高校信息化建設(shè)中數(shù)據(jù)治理的研究，可以認(rèn)清在高校信息化中存在的問題，有效促進(jìn)我國高校信息化的建設(shè)[1]。函數(shù)依賴(Functional Dependency, FD)這一概念首先在文獻(xiàn)[3]中被研究，它表征的是數(shù)據(jù)實(shí)例中字段之間的關(guān)聯(lián)關(guān)系，可以作為數(shù)據(jù)治理的檢測(cè)規(guī)則以提升高校數(shù)據(jù)的數(shù)據(jù)質(zhì)量。對(duì)于函數(shù)依賴的發(fā)現(xiàn)包括了發(fā)現(xiàn)一個(gè)給定關(guān)系中的函數(shù)依賴、多值依賴以及近似函數(shù)依賴[4-6]，而用于發(fā)現(xiàn)函數(shù)依賴的算法主要有：TANE[7]、FUN[8]、FD_MINE[9]、DFD[10]、DEP-MINER[5]、FASTFDS[6]、FDEP[11]等，這幾種算法可以被分成三類：第一類為屬性格遍歷算法，包含TANE、FUN、FD_MINE和DFD四種算法[12]。TANE、FUN和FD_MINE使用了基于apriori-gen候選生成原理的自下而上的遍歷策略[13]，DFD實(shí)現(xiàn)了深度隨機(jī)游走。雖然遍歷策略各不相同，但這四種算法都會(huì)連續(xù)生成新的候選函數(shù)依賴并使用精簡分區(qū)來單獨(dú)驗(yàn)證它們。本類中的所有算法都使用并擴(kuò)展了TANE算法的剪枝規(guī)則。第二類為差異-一致集算法，包含DEP-MINER、FASTFDS。第三類為依賴推理算法。

在這幾種算法中，最著名的就是文獻(xiàn)[7]中提出的基于層次搜索屬性包含格的TANE算法，該算法在元組數(shù)較大的情況下表現(xiàn)良好并且相對(duì)于屬性格遍歷算法中的其他算法，該算法在屬性進(jìn)行橫向擴(kuò)展時(shí)的表現(xiàn)也更好，因此，結(jié)合高校實(shí)際數(shù)據(jù)元組數(shù)較大、屬性個(gè)數(shù)較多的特點(diǎn)，本文選擇TANE算法來自動(dòng)發(fā)現(xiàn)函數(shù)依賴；但由于在進(jìn)行函數(shù)依賴的自動(dòng)發(fā)現(xiàn)時(shí)，真實(shí)的高校數(shù)據(jù)集中存在的大量缺失值會(huì)使得經(jīng)過TANE算法發(fā)現(xiàn)出的函數(shù)依賴不準(zhǔn)確，若直接使用這些函數(shù)依賴來進(jìn)行臟數(shù)據(jù)的修復(fù)，將可能使得數(shù)據(jù)集中的臟數(shù)據(jù)變得更多，影響學(xué)校領(lǐng)導(dǎo)、老師的決策，本文提出了一種使用近鄰傳播(Affinity Propagation, AP)聚類算法和TANE算法結(jié)合的先進(jìn)行缺失值填補(bǔ)，然后在不含缺失值的數(shù)據(jù)集上發(fā)現(xiàn)出函數(shù)依賴的APTANE方法。這一方法在之前的研究過程中并未受到關(guān)注，它有效解決了高校數(shù)據(jù)因存在大量缺失值使得從數(shù)據(jù)集中發(fā)現(xiàn)出的函數(shù)依賴不準(zhǔn)確，影響學(xué)校領(lǐng)導(dǎo)、老師作出進(jìn)一步?jīng)Q策等問題。

1 基本概念

1.1 數(shù)據(jù)質(zhì)量維度

數(shù)據(jù)和信息質(zhì)量思想家都采用了維度(dimension)一詞來確定可以測(cè)量數(shù)據(jù)的哪些方面[14]。雖然不同的專家提出了不同的數(shù)據(jù)質(zhì)量維度，但是幾乎都離不開完整性、完備性、一致性、有效性和及時(shí)性這五大維度。

完整性 完整性衡量的是數(shù)據(jù)所擁有的完整程度，它指的是未分割的整個(gè)狀態(tài)或統(tǒng)一的狀況[14]。該維度體現(xiàn)了對(duì)基本數(shù)據(jù)的質(zhì)量測(cè)量。可以通過檢測(cè)規(guī)則來保證數(shù)據(jù)完整性，而檢測(cè)規(guī)則可以通過領(lǐng)域?qū)＜抑贫ɑ驈臄?shù)據(jù)集中自動(dòng)發(fā)現(xiàn)的方式來獲得，如本文使用TANE算法發(fā)現(xiàn)出的函數(shù)依賴就是一組檢測(cè)規(guī)則。

完備性 完備性衡量的是數(shù)據(jù)所擁有的廣度、寬度以及深度。數(shù)據(jù)的廣度指的是模式所具有的字段數(shù)，數(shù)據(jù)的寬度指的是字段值的填充情況，而數(shù)據(jù)的深度則指的是模式所具有的數(shù)據(jù)條數(shù)。

一致性 一致性衡量的是字段、數(shù)據(jù)含義均相同的數(shù)據(jù)的一致程度[14]。在數(shù)據(jù)集合中，指的是每個(gè)信息都不包含語義錯(cuò)誤或相互矛盾的數(shù)據(jù)[15]。例如某些考評(píng)結(jié)果，有的是優(yōu)、良、差，有的是甲、乙、丙，這就造成了數(shù)據(jù)度量的不一致，因此滿足一致性是進(jìn)行數(shù)據(jù)集成的基礎(chǔ)[1]。

有效性 有效性是數(shù)據(jù)對(duì)一組業(yè)務(wù)規(guī)則的符合程度，有時(shí)被表達(dá)為一個(gè)標(biāo)準(zhǔn)，或在已定義的數(shù)據(jù)域中被表示。它是數(shù)據(jù)對(duì)數(shù)據(jù)標(biāo)準(zhǔn)、數(shù)據(jù)模型、業(yè)務(wù)規(guī)則、元數(shù)據(jù)和參考數(shù)據(jù)等的符合程度。例如，將輸入數(shù)據(jù)的值與某個(gè)數(shù)據(jù)標(biāo)準(zhǔn)的有效值進(jìn)行比較[1]，就是對(duì)輸入數(shù)據(jù)有效性的檢驗(yàn)。

及時(shí)性 及時(shí)性衡量的是存儲(chǔ)在系統(tǒng)中的數(shù)據(jù)與真實(shí)數(shù)據(jù)相比的更新程度。及時(shí)性可相對(duì)于某個(gè)設(shè)定的計(jì)劃，或某個(gè)事件的發(fā)生來測(cè)量。例如，及時(shí)性是數(shù)據(jù)從源系統(tǒng)交付時(shí)對(duì)交付計(jì)劃的符合程度[14]。

1.2 AP聚類算法

AP聚類算法是2007年Clustering by Passing Messages Between Data Points[16]一文中提出的一種新的聚類算法。該算法在執(zhí)行之前不需要定義聚類的類數(shù)，算法通過在迭代過程中不斷搜索合適的聚類中心，自動(dòng)從數(shù)據(jù)點(diǎn)間識(shí)別類中心(Exemplars)的位置及個(gè)數(shù)，使所有的數(shù)據(jù)點(diǎn)到最近的類代表點(diǎn)的相似度之和最大[17]。算法最開始將所有的數(shù)據(jù)點(diǎn)都視為聚類中心，并基于數(shù)據(jù)點(diǎn)之間的信息傳遞來實(shí)現(xiàn)聚類過程。

與一般的聚類算法，比如k-means算法相比，由于AP聚類算法在運(yùn)算開始前不需要指定聚類的簇?cái)?shù)，使得先驗(yàn)經(jīng)驗(yàn)不是必需的；除此之外，數(shù)據(jù)集樣本中所有的數(shù)據(jù)點(diǎn)都可能成為AP算法的核，而不是像k-means等算法是通過求平均的方式來獲得聚類中心；由于k-means聚類算法需要人工設(shè)定簇?cái)?shù)，且多次運(yùn)算的結(jié)果可能不同，因此會(huì)影響聚類效果，導(dǎo)致聚類結(jié)果不穩(wěn)定，而AP聚類算法多次執(zhí)行后，每次的結(jié)果是完全相同的，因此聚類結(jié)果相對(duì)于k-means等一般的聚類算法來說更加穩(wěn)定。目前為止，AP聚類算法已經(jīng)被應(yīng)用到了多個(gè)領(lǐng)域，如圖像識(shí)別、文本挖掘等，均取得了較好的效果[18-20]。

在AP聚類算法中，消息的傳遞是通過更新代表信息矩陣R(Responsibility)和選擇信息矩陣A(Availability)來進(jìn)行的。代表信息矩陣中的元素r(i,k)表征的是數(shù)據(jù)點(diǎn)k適合作為數(shù)據(jù)點(diǎn)i的聚類中心的程度，如圖1所示，它代表了從點(diǎn)i到點(diǎn)k的消息，而選擇信息矩陣中的元素a(i,k)表征的是數(shù)據(jù)點(diǎn)i選擇數(shù)據(jù)點(diǎn)k作為其聚類中心的適合程度，如圖2所示，它代表了從點(diǎn)k到點(diǎn)i的消息。

圖1 代表信息的更新過程Fig. 1 Update process of responsibilities

圖2 選擇信息的更新過程Fig. 2 Update process of availabilities

要更新代表信息矩陣R和選擇信息矩陣A需要對(duì)任意數(shù)據(jù)點(diǎn)i計(jì)算其他所有數(shù)據(jù)點(diǎn)k與點(diǎn)i的r(i,k)和a(i,k)。在算法初始化時(shí)，令a(i,k)=0，可以通過式(1)、(2)來分別計(jì)算r(i,k)和a(i,k)：

r(i,k)=s(i,k)-max[a(i,k′)+s(i,k′)];k′≠k

(1)

a(i,k)=

(2)

需要注意的是，a(i,k′)和s(i,k′)代表的是上一次的迭代更新結(jié)果。由式(1)和(2)可以得到r(i,k)與a(i,k)的和，即式(3)：

r(i,k)+a(i,k)=s(i,k)+a(i,k)-

(3)

對(duì)于數(shù)據(jù)點(diǎn)i，若r(i,k)與a(i,k)的和最大，則數(shù)據(jù)點(diǎn)k即為類中心，當(dāng)r(i,k)與a(i,k)的和在迭代過程中保持不變時(shí)，消息的傳遞過程結(jié)束。

1.3 函數(shù)依賴

關(guān)系R上的函數(shù)依賴可以表示成X→A的形式，其中，X是給定關(guān)系R中的屬性集，A是R上的某個(gè)屬性，A的值唯一地由X的值決定。對(duì)于一個(gè)形如X→A的函數(shù)依賴，屬性集X稱為該函數(shù)依賴的左部，而屬性A稱為右部。為了保證發(fā)現(xiàn)的函數(shù)依賴是有意義且非冗余的，要求發(fā)現(xiàn)出的函數(shù)依賴必須滿足非平凡和最小這兩個(gè)條件。非平凡函數(shù)依賴指的是：屬性A不屬于屬性集X，即：X(〗A}→A就是一個(gè)非平凡函數(shù)依賴，而最小函數(shù)依賴指的是：如果X→A是一個(gè)函數(shù)依賴，并且對(duì)于X的任何一個(gè)真子集Y，都沒有Y→A成立，那么X→A就是最小的函數(shù)依賴。

1.3.1 分區(qū)

在給定關(guān)系R中，屬性X的分區(qū)可以用πX來表示，πX={[t]X|t∈r}，其中，[t]X為分區(qū)πX中的等價(jià)類，可表示為：[t]X={u∈r|t[A]=u[A]}[4]，其中，A∈X。

對(duì)于數(shù)據(jù)表中的某個(gè)字段，將具有相同字段值的元素歸為同一個(gè)等價(jià)類，這樣，該字段具有多少個(gè)不同值，對(duì)應(yīng)的分區(qū)中就有多少個(gè)等價(jià)類。比如，在表1所示的學(xué)生信息實(shí)例中，字段“專業(yè)”的分區(qū)為：π專業(yè)={{1,6,7,8},{2,4},{3},{5}}。

表1 學(xué)生信息實(shí)例 Tab. 1 Examples of student information

1.3.2 精煉分區(qū)

1.3.3 右部集

為了找到最小的函數(shù)依賴，需要對(duì)屬于屬性集X并且對(duì)于所有屬于屬性集X的屬性B，檢測(cè)XA}→A是否滿足，其中，A∈C(XB})。

1.3.4 超鍵

如果任何兩個(gè)元組在屬性集X上的值都不等，那么屬性集X就是一個(gè)超鍵。令B∈X，并且令XB}→B是一個(gè)有效的依賴，此時(shí)，如果X是一個(gè)超鍵，那么XB}也是一個(gè)超鍵。通常，在X∪{A}被處理時(shí)需要測(cè)試X→A(A?X)是否成立，這就需要使用πX∪{A}來進(jìn)行有效性測(cè)試，然而，如果X是超鍵，那么X→A將始終有效，因此可以不再額外使用πX∪{A}來進(jìn)行有效性測(cè)試。

1.3.5 剪枝

對(duì)TANE的搜索空間進(jìn)行剪枝可以基于：如果C(X)=?，那么C(Y)=?，其中Y是X的超集。也就是說，如果XA}→A是最小的函數(shù)依賴，則不會(huì)再有形如YA}→A的函數(shù)依賴是最小的函數(shù)依賴，集合Y也不會(huì)再被處理，因此Y可以被剪掉。

2 方法流程及相關(guān)算法介紹

由于在研究使用TANE算法從高校數(shù)據(jù)中發(fā)現(xiàn)函數(shù)依賴時(shí)，數(shù)據(jù)表中存在的缺失值使得發(fā)現(xiàn)的函數(shù)依賴個(gè)數(shù)較少，且所表征的字段間的關(guān)聯(lián)關(guān)系不準(zhǔn)確，因此本文針對(duì)這一問題，提出使用AP聚類算法和TANE算法結(jié)合來發(fā)現(xiàn)高校數(shù)據(jù)中函數(shù)依賴的APTANE方法。首先介紹本方法的具體流程：1)在數(shù)據(jù)預(yù)處理階段，若待測(cè)字段中含有中文字段，則首先對(duì)該字段的中文字段值進(jìn)行列剖析，用該中文字段值在該列中出現(xiàn)的次數(shù)來替換對(duì)應(yīng)中文字段值；2)使用AP聚類算法對(duì)待測(cè)字段中包含有缺失字段值的字段進(jìn)行缺失值填補(bǔ)；3)在經(jīng)過上述步驟處理后的不含缺失值的數(shù)據(jù)集上使用TANE算法自動(dòng)發(fā)現(xiàn)滿足非平凡、最小要求的函數(shù)依賴。下面對(duì)該方法中涉及到的已有算法進(jìn)行簡要介紹。

2.1 進(jìn)行缺失值填補(bǔ)的AP聚類算法

在自動(dòng)發(fā)現(xiàn)函數(shù)依賴之前，首先使用AP聚類算法對(duì)高校數(shù)據(jù)集當(dāng)中所選字段存在的缺失值進(jìn)行填補(bǔ)。下面對(duì)該過程使用算法1進(jìn)行描述。

算法1 AP_For_Filling_Missing_Values。

輸入：待修復(fù)數(shù)據(jù)集，阻尼系數(shù)和最大迭代次數(shù)。

輸出：已進(jìn)行缺失值填補(bǔ)的數(shù)據(jù)集。

初始化λ，maxIterNum，計(jì)算相似度矩陣S

setChineseToNum()

setPreference()

Fori:=0 TomaxIterNum

updateResponsibility()

updateAvailability()

End For

assignClusterPoint()

setPredictValue()

setNewValue()

AP聚類算法首先需要設(shè)定阻尼系數(shù)λ和最大迭代次數(shù)maxIterNum的值，以初始化算法，并計(jì)算相似度矩陣S，相似度矩陣S中的元素s(i,j)表征的是數(shù)據(jù)點(diǎn)i，j之間的相似度，使用歐幾里得距離計(jì)算公式得出，即：s(i,j)=-‖xi-xj‖2。使用AP聚類算法來進(jìn)行缺失值填補(bǔ)時(shí)，由于高校數(shù)據(jù)中可能存在中文字段，而AP聚類算法在計(jì)算兩點(diǎn)之間的相似度時(shí)無法直接對(duì)中文字段值進(jìn)行處理，因此本算法使用了setChineseToNum()方法將中文字段值替換成對(duì)應(yīng)的數(shù)值，然后再進(jìn)行聚類的后續(xù)步驟。setChineseToNum()方法通過計(jì)算中文字段中不同字段值出現(xiàn)的次數(shù)，以此來替換原有值。

算法1使用setPreference()方法來設(shè)定參考度Preference的值。Preference指的是點(diǎn)i作為聚類中心的參考度(不能為0)，表示為p(i)或s(i,i)，取值為S對(duì)角線的值，此值越大，作為聚類中心的可能性就越大。Preference的值決定了AP聚類算法輸出的類別，在無先驗(yàn)知識(shí)的情況下，所有數(shù)據(jù)點(diǎn)都可以看成是潛在的聚類中心代表。

AP聚類算法迭代過程的核心是兩個(gè)信息矩陣的交替更新過程。首先應(yīng)計(jì)算樣本點(diǎn)間的r(i,k)和a(i,k)。樣本點(diǎn)間的r(i,k)的計(jì)算方法為：

樣本點(diǎn)間的a(i,k)的計(jì)算方法為：

在計(jì)算了樣本點(diǎn)間的r(i,k)和a(i,k)之后，算法1使用式(4)、(5)來分別更新代表信息矩陣和選擇信息矩陣：

rt+1(i,k)=λ*rt(i,k)+(1-λ)*rt+1(i,k)

(4)

at+1(i,k)=λ*at(i,k)+(1-λ)*at+1(i,k)

(5)

在AP算法實(shí)現(xiàn)的過程中任何點(diǎn)的r(i,k)和a(i,k)都與定義聚類中心相關(guān)聯(lián)。對(duì)于a(i,k)+r(i,k)取最大值時(shí)的k值，如果k=i，則將數(shù)據(jù)點(diǎn)i作為聚類中心，否則將數(shù)據(jù)點(diǎn)k作為點(diǎn)i的聚類中心。

assignClusterPoint()方法用于將各數(shù)據(jù)點(diǎn)分配到聚類中心所在的類中。若迭代次數(shù)超過設(shè)定的最大值或者當(dāng)聚類中心在若干次迭代過程中不再發(fā)生改變，則停止計(jì)算，得出最終的聚類中心及各個(gè)類所擁有的樣本點(diǎn)。setPredictValue()方法用于得到AP聚類算法對(duì)于缺失值的預(yù)測(cè)值，setNewValue()方法用于將數(shù)據(jù)集的缺失值填補(bǔ)為AP聚類算法所預(yù)測(cè)出的值以得到經(jīng)過AP聚類算法處理后的不含缺失值的數(shù)據(jù)集，以便進(jìn)行后續(xù)從數(shù)據(jù)集中自動(dòng)發(fā)現(xiàn)函數(shù)依賴的步驟。

2.2 發(fā)現(xiàn)函數(shù)依賴的TANE算法

從數(shù)據(jù)集中自動(dòng)發(fā)現(xiàn)字段之間的關(guān)聯(lián)關(guān)系，可以減少領(lǐng)域?qū)＜遗渲脭?shù)據(jù)質(zhì)量檢測(cè)規(guī)則的工作量，提高工作效率；并且，自動(dòng)產(chǎn)生的數(shù)據(jù)質(zhì)量檢測(cè)規(guī)則可以作為進(jìn)一步檢測(cè)臟數(shù)據(jù)的指標(biāo)，提升高校數(shù)據(jù)所擁有的數(shù)據(jù)質(zhì)量。本文使用TANE算法從已進(jìn)行了缺失值填補(bǔ)的數(shù)據(jù)集上自動(dòng)發(fā)現(xiàn)函數(shù)依賴。從文獻(xiàn)[7]可知，該算法使用的是基于層次搜索屬性包含格的方法，算法首先從空集開始，向下生成屬性集，然后在當(dāng)前層計(jì)算候選函數(shù)依賴，對(duì)候選函數(shù)依賴進(jìn)行非平凡性和最小性的檢測(cè)，剪掉不滿足要求的節(jié)點(diǎn)，節(jié)約搜索空間，然后繼續(xù)從當(dāng)前層生成下一層，重復(fù)以上過程，直到找出所有滿足要求的函數(shù)依賴。當(dāng)算法在處理每一層的屬性集X時(shí)，它會(huì)檢測(cè)形如XA}→A(A∈X)的函數(shù)依賴是否成立，這就可以保證只有非平凡的函數(shù)依賴會(huì)被考慮。另外，算法由小到大的擴(kuò)展方向可以保證只有最小的函數(shù)依賴被輸出，并且由于TANE算法基于的是上一層的結(jié)果來生成下一層的屬性集，也減小了相應(yīng)的計(jì)算量。下面對(duì)算法2 TANE算法進(jìn)行詳細(xì)描述。

算法2 TANE。

輸入：已進(jìn)行缺失值填補(bǔ)的數(shù)據(jù)集。

輸出：數(shù)據(jù)集上存在的非平凡、最小函數(shù)依賴。

L0:={?}

C+(?):=R

L1:={{A}|A∈R}

l:=1

whileLl≠?

compute_dependencies(Ll)

prune(Ll)

Ll+1:=generate_next_level(Ll)

l:=l+1

TANE算法首先令第L0層為空集，然后從L1={{A}|A∈R}開始，由第L1層計(jì)算出第L2層，由第L2層計(jì)算出第L3層，以此類推。當(dāng)?shù)贚l層不為空時(shí)，使用compute_dependencies(Ll)方法來計(jì)算該層的候選函數(shù)依賴。方法為：對(duì)于第Ll層中的每個(gè)屬性集X先計(jì)算C+(X)。要得到C+(X)，需要先計(jì)算C+(XA})，此處的屬性A是屬性集X中的單一屬性，然后把計(jì)算出的結(jié)果取交集，即可得到C+(X)。對(duì)于每一個(gè)屬于X∩C+(X)集合中的屬性A，如果XA}→A是有效的，則輸出XA}→A這一候選函數(shù)依賴，并且從C+(X)中移除屬性A，從C+(X)中移除所有屬于RX集合的屬性B。

使用generate_next_level(Ll)可以從第Ll層生成第Ll+1層。首先令Ll+1這一層為空集，對(duì)于Ll這一層中的每一個(gè)前綴塊K進(jìn)行如下操作：對(duì)于每一對(duì)包含于前綴塊K中的兩個(gè)不同的屬性集Y、Z，將Y∪Z的結(jié)果賦給X，并判斷如果對(duì)于所有屬于屬性集X中的屬性A，都有從X中去掉屬性A之后，余下的屬性仍然屬于第Ll層這一結(jié)果，那么就將Ll+1∪{X}的結(jié)果賦給Ll+1，以生成第Ll+1層。當(dāng)找出了給定的已進(jìn)行缺失值填補(bǔ)的數(shù)據(jù)集上存在的所有滿足非平凡、最小條件的函數(shù)依賴之后，算法會(huì)終止，不再繼續(xù)生成下一層。

3 實(shí)驗(yàn)結(jié)果及分析

本實(shí)驗(yàn)的運(yùn)行環(huán)境為使用Intel酷睿i7- 3.2 GHz的CPU，16 GB內(nèi)存的Windows計(jì)算機(jī)，實(shí)驗(yàn)使用的數(shù)據(jù)集分為測(cè)試數(shù)據(jù)集和真實(shí)數(shù)據(jù)集。測(cè)試數(shù)據(jù)集來自UCI數(shù)據(jù)集的breast-cancer-Wisconsin數(shù)據(jù)集，包含腫塊厚度、細(xì)胞大小均勻性、細(xì)胞形狀均勻性、類別等11個(gè)屬性，共有699條元組。使用breast-cancer-Wisconsin數(shù)據(jù)集的原因在于該數(shù)據(jù)集的屬性之間存在著一定的關(guān)聯(lián)關(guān)系，便于進(jìn)行函數(shù)依賴自動(dòng)發(fā)現(xiàn)這一過程。表2為該數(shù)據(jù)集的字段信息。

表2 breast-cancer-Wisconsin數(shù)據(jù)集字段信息 Tab. 2 Field information of Breast-cancer-Wisconsin dataset

真實(shí)數(shù)據(jù)集來自某高校學(xué)生信息數(shù)據(jù)集，共有30 648條元組，是用學(xué)生信息表以及貧困補(bǔ)助表兩者進(jìn)行合并形成的數(shù)據(jù)集。表3為該數(shù)據(jù)集的字段信息。

表3 高校數(shù)據(jù)集字段信息 Tab. 3 Field information of university dataset

由于使用的測(cè)試數(shù)據(jù)集breast-cancer-Wisconsin不包含空值，因此，為了檢測(cè)使用AP聚類算法來進(jìn)行缺失值填補(bǔ)之后能提升TANE算法所檢測(cè)出的函數(shù)依賴的個(gè)數(shù)和準(zhǔn)確度的可行性和有效性，采用了通過設(shè)定不同缺失率e向數(shù)據(jù)集中注入n*e個(gè)空值由此來形成含有空值的數(shù)據(jù)集，并在此數(shù)據(jù)集上進(jìn)行測(cè)試數(shù)據(jù)集缺失值填補(bǔ)實(shí)驗(yàn)的方式。其中，n為元組個(gè)數(shù)。

圖3顯示了在缺失率e的取值分別為0.02、0.04、0.06、0.08時(shí)AP聚類算法填補(bǔ)測(cè)試數(shù)據(jù)集上的缺失值的準(zhǔn)確率，可以看出，缺失值填補(bǔ)的準(zhǔn)確率隨著e值的增大呈現(xiàn)平穩(wěn)增長的趨勢(shì)，在e大于等于0.04時(shí)維持在較高水平，并且在缺失率為0.06時(shí)，使用AP聚類算法填補(bǔ)缺失值的準(zhǔn)確率最高，為94.87%，在缺失率為0.08時(shí)，由于字段值缺失數(shù)增加使得最近鄰點(diǎn)以及近鄰區(qū)域?qū)垲惔睃c(diǎn)產(chǎn)生了影響，導(dǎo)致準(zhǔn)確率有所下降，但仍然保持在90%以上。

圖3 聚類準(zhǔn)確率隨e值的變化Fig. 3 Clustering accuracy changing withe value

圖4是在測(cè)試數(shù)據(jù)集上將本文的APTANE方法分別與TANE、DFD、FUN算法所發(fā)現(xiàn)出的函數(shù)依賴個(gè)數(shù)的對(duì)比。

圖4 不同缺失率下的各算法發(fā)現(xiàn)的FDs個(gè)數(shù)Fig. 4 Number of FDs found by each algorithm under different missing rates

TANE、DFD和FUN算法都是基于屬性格的遍歷來發(fā)現(xiàn)函數(shù)依賴的方法，它們?cè)诰哂写罅吭M數(shù)的數(shù)據(jù)集上表現(xiàn)比差異-一致集算法以及依賴推理算法更好[11]，因此本文根據(jù)實(shí)際應(yīng)用場(chǎng)景中高校真實(shí)數(shù)據(jù)集的特點(diǎn)選擇將APTANE方法與TANE、DFD、FUN算法進(jìn)行比較。從圖4可以看出：在不處理缺失值，直接從原始數(shù)據(jù)集上使用TANE、DFD、FUN這三個(gè)算法時(shí)，發(fā)現(xiàn)的函數(shù)依賴個(gè)數(shù)較少，三個(gè)算法中，DFD算法能發(fā)現(xiàn)的函數(shù)依賴最多為21個(gè)，而FUN算法和TANE算法不管缺失率的值如何變化，均只能發(fā)現(xiàn)8個(gè)；而本文提出的APTANE方法由于對(duì)數(shù)據(jù)集中的缺失值進(jìn)行了填補(bǔ)，完善了字段值之間隱藏的關(guān)聯(lián)信息，因此能發(fā)現(xiàn)出更多的函數(shù)依賴，并且個(gè)數(shù)接近于測(cè)試數(shù)據(jù)集不存在空值時(shí)所發(fā)現(xiàn)出的46個(gè)函數(shù)依賴。

從表4測(cè)試數(shù)據(jù)集不存在缺失值以及缺失率為0.06時(shí)APTANE所發(fā)現(xiàn)的FDs的對(duì)比中可以看出，在e為0.06時(shí)所發(fā)現(xiàn)出的FDs完全覆蓋了不存在缺失值的情況下所發(fā)現(xiàn)的所有FDs，結(jié)合圖3準(zhǔn)確率的增長趨勢(shì)，表明了在聚類準(zhǔn)確率越高的情況下，所發(fā)現(xiàn)的FDs越準(zhǔn)確、越完整。本文使用的高校真實(shí)數(shù)據(jù)集是存在大量缺失值的數(shù)據(jù)集，存在的缺失值主要集中在”困難程度”字段。圖5是在高校真實(shí)數(shù)據(jù)集上將本文的APTANE方法分別與TANE、DFD、FUN算法所發(fā)現(xiàn)出的函數(shù)依賴個(gè)數(shù)進(jìn)行對(duì)比后得出的結(jié)果。

表4 e的取值為0和0.06時(shí)APTANE發(fā)現(xiàn)的FDs對(duì)比 Tab. 4 Comparison of FDs found by APTANE when e is 0 and 0.06

圖5 高校數(shù)據(jù)集上各算法發(fā)現(xiàn)出的FDs個(gè)數(shù)Fig. 5 Number of FDs found by each algorithm in university dataset

經(jīng)過在該真實(shí)數(shù)據(jù)集上進(jìn)行缺失值填補(bǔ)的實(shí)驗(yàn)后發(fā)現(xiàn)，在使用AP聚類算法對(duì)缺失值進(jìn)行填補(bǔ)之后，從數(shù)據(jù)集中發(fā)現(xiàn)的滿足非平凡、最小要求的有效函數(shù)依賴個(gè)數(shù)增加到了80個(gè)，相對(duì)于直接在原始數(shù)據(jù)集上使用TANE、DFD、FUN算法來發(fā)現(xiàn)函數(shù)依賴的結(jié)果來看，分別增長了35.6%、29.0%、20%。表5展示了發(fā)現(xiàn)的部分有效FDs，在使用AP聚類算法填補(bǔ)缺失值之后，發(fā)現(xiàn)的有效函數(shù)依賴完全覆蓋了之前存在缺失值時(shí)所發(fā)現(xiàn)的函數(shù)依賴。

表5 高校數(shù)據(jù)集部分有效函數(shù)依賴 Tab. 5 Partial effective functional dependencies of university dataset

從表5中可以看出：相比于數(shù)據(jù)集存在缺失值時(shí)發(fā)現(xiàn)出的函數(shù)依賴集合而言，使用AP聚類算法填補(bǔ)缺失值之后，除了在含有缺失值時(shí)發(fā)現(xiàn)的諸如：學(xué)號(hào)→困難程度，身份證號(hào)碼→出生日期這些函數(shù)依賴之外，新增的函數(shù)依賴中包括了人均年收入→困難程度，困難等級(jí)、人均年收入→困難程度等函數(shù)依賴，這些FDs可以在后續(xù)的數(shù)據(jù)治理過程中，作為根據(jù)學(xué)生對(duì)應(yīng)的家庭人均年收入來判斷困難程度是否正確的檢測(cè)規(guī)則。可以看到含有缺失值對(duì)于從數(shù)據(jù)集中準(zhǔn)確發(fā)現(xiàn)有效的FDs影響較大，并且發(fā)現(xiàn)的函數(shù)依賴可能不準(zhǔn)確，如果使用含義錯(cuò)誤的函數(shù)依賴對(duì)高校數(shù)據(jù)進(jìn)行數(shù)據(jù)治理，將可能在數(shù)據(jù)集中產(chǎn)生更多的臟數(shù)據(jù)。

本文實(shí)驗(yàn)在測(cè)試數(shù)據(jù)集和真實(shí)數(shù)據(jù)集上的結(jié)果表明了使用AP聚類算法來填補(bǔ)缺失值是有效且準(zhǔn)確的，并且在填補(bǔ)缺失值后的數(shù)據(jù)集上發(fā)現(xiàn)的函數(shù)依賴的個(gè)數(shù)更多，含義更準(zhǔn)確，能有效減少領(lǐng)域?qū)＜业墓ぷ髁浚嵘咝?shù)據(jù)的數(shù)據(jù)質(zhì)量。

4 結(jié)語

為了解決在高校數(shù)據(jù)集存在缺失值時(shí)，發(fā)現(xiàn)的函數(shù)依賴個(gè)數(shù)較少且不準(zhǔn)確的問題，本文提出了一種使用AP聚類算法和TANE算法相結(jié)合的APTANE方法。經(jīng)過該方法的處理可以有效地補(bǔ)全缺失信息，提高發(fā)現(xiàn)的函數(shù)依賴的個(gè)數(shù)和準(zhǔn)確度，為學(xué)校領(lǐng)導(dǎo)、老師從數(shù)據(jù)中分析學(xué)生行為、制定發(fā)展方略提供數(shù)據(jù)支撐，并且本文也證明了AP聚類算法在對(duì)缺失值進(jìn)行填補(bǔ)方面是有效且穩(wěn)定的。

但本文研究也存在不足之處，由于AP聚類算法的時(shí)間復(fù)雜度為O(N*N*logN)，N為數(shù)據(jù)集的元組數(shù)，因此，在使用AP聚類算法對(duì)數(shù)據(jù)量較大的數(shù)據(jù)集進(jìn)行缺失值填補(bǔ)時(shí)，算法耗時(shí)較長，并且發(fā)現(xiàn)的函數(shù)依賴所表達(dá)的字段間的含義并非都是準(zhǔn)確的，因此，今后的研究將著眼于：1)如何在使用AP聚類算法保證缺失值填補(bǔ)準(zhǔn)確率的同時(shí)減少算法運(yùn)行時(shí)間；2)如何進(jìn)一步提升發(fā)現(xiàn)的函數(shù)依賴所表達(dá)的字段間關(guān)聯(lián)關(guān)系的準(zhǔn)確度。