基于近鄰傳播聚類和TANE算法的高校數據中函數依賴的發現

黃永鑫，唐雪飛

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

0 引言

高校信息化經過多年的發展，很多高校已積累了大量的業務和相關數據，數據不同于有形的產品，但同樣具有質量這一概念，但是因為數據質量不高、冗余數據大量存在和數據可用性不高，使很多數據處理工作還需要通過人工來確保正確，浪費了大量的人力和時間[1]。

我國教育領域已初步解決數據的有無問題。然而，大量數據仍未得以充分應用，究其原因，除了教育工作者對數據價值重視不夠等主觀原因外，數據質量不高、數據狀態不能適應當前教育發展也是重要的客觀原因[2]。

數據缺失是數據質量問題的其中一種，在高校數據中，比如對于學工系統中的數據來說，造成數據缺失的原因可能是由于人工錄入失誤，也可能是在數據傳輸過程中造成了缺失。大量缺失值將使得從數據中發現出的數據質量檢測規則不準確，使得領域專家無法根據發現出的數據質量檢測規則有效修復數據集中存在的臟數據等問題。若直接將含有缺失值的數據刪掉，會使得數據集中丟失的數據較多，進而使得基于該數據集所作出的數據分析結果產生較大偏差。

在高校信息化建設的過程中，通過開展高校數據治理以提高數據質量，可以有效提高數據價值，為組織決策的制定提供幫助。同時，通過對高校信息化建設中數據治理的研究，可以認清在高校信息化中存在的問題，有效促進我國高校信息化的建設[1]。函數依賴(Functional Dependency, FD)這一概念首先在文獻[3]中被研究，它表征的是數據實例中字段之間的關聯關系，可以作為數據治理的檢測規則以提升高校數據的數據質量。對于函數依賴的發現包括了發現一個給定關系中的函數依賴、多值依賴以及近似函數依賴[4-6]，而用于發現函數依賴的算法主要有：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實現了深度隨機游走。雖然遍歷策略各不相同，但這四種算法都會連續生成新的候選函數依賴并使用精簡分區來單獨驗證它們。本類中的所有算法都使用并擴展了TANE算法的剪枝規則。第二類為差異-一致集算法，包含DEP-MINER、FASTFDS。第三類為依賴推理算法。

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

1 基本概念

1.1 數據質量維度

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

完整性 完整性衡量的是數據所擁有的完整程度，它指的是未分割的整個狀態或統一的狀況[14]。該維度體現了對基本數據的質量測量。可以通過檢測規則來保證數據完整性，而檢測規則可以通過領域專家制定或從數據集中自動發現的方式來獲得，如本文使用TANE算法發現出的函數依賴就是一組檢測規則。

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

一致性 一致性衡量的是字段、數據含義均相同的數據的一致程度[14]。在數據集合中，指的是每個信息都不包含語義錯誤或相互矛盾的數據[15]。例如某些考評結果，有的是優、良、差，有的是甲、乙、丙，這就造成了數據度量的不一致，因此滿足一致性是進行數據集成的基礎[1]。

有效性 有效性是數據對一組業務規則的符合程度，有時被表達為一個標準，或在已定義的數據域中被表示。它是數據對數據標準、數據模型、業務規則、元數據和參考數據等的符合程度。例如，將輸入數據的值與某個數據標準的有效值進行比較[1]，就是對輸入數據有效性的檢驗。

及時性 及時性衡量的是存儲在系統中的數據與真實數據相比的更新程度。及時性可相對于某個設定的計劃，或某個事件的發生來測量。例如，及時性是數據從源系統交付時對交付計劃的符合程度[14]。

1.2 AP聚類算法

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

與一般的聚類算法，比如k-means算法相比，由于AP聚類算法在運算開始前不需要指定聚類的簇數，使得先驗經驗不是必需的；除此之外，數據集樣本中所有的數據點都可能成為AP算法的核，而不是像k-means等算法是通過求平均的方式來獲得聚類中心；由于k-means聚類算法需要人工設定簇數，且多次運算的結果可能不同，因此會影響聚類效果，導致聚類結果不穩定，而AP聚類算法多次執行后，每次的結果是完全相同的，因此聚類結果相對于k-means等一般的聚類算法來說更加穩定。目前為止，AP聚類算法已經被應用到了多個領域，如圖像識別、文本挖掘等，均取得了較好的效果[18-20]。

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

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

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

要更新代表信息矩陣R和選擇信息矩陣A需要對任意數據點i計算其他所有數據點k與點i的r(i,k)和a(i,k)。在算法初始化時，令a(i,k)=0，可以通過式(1)、(2)來分別計算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′)代表的是上一次的迭代更新結果。由式(1)和(2)可以得到r(i,k)與a(i,k)的和，即式(3)：

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

(3)

對于數據點i，若r(i,k)與a(i,k)的和最大，則數據點k即為類中心，當r(i,k)與a(i,k)的和在迭代過程中保持不變時，消息的傳遞過程結束。

1.3 函數依賴

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

1.3.1 分區

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

對于數據表中的某個字段，將具有相同字段值的元素歸為同一個等價類，這樣，該字段具有多少個不同值，對應的分區中就有多少個等價類。比如，在表1所示的學生信息實例中，字段“專業”的分區為：π專業={{1,6,7,8},{2,4},{3},{5}}。

表1 學生信息實例 Tab. 1 Examples of student information

1.3.2 精煉分區

1.3.3 右部集

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

1.3.4 超鍵

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

1.3.5 剪枝

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

2 方法流程及相關算法介紹

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

2.1 進行缺失值填補的AP聚類算法

在自動發現函數依賴之前，首先使用AP聚類算法對高校數據集當中所選字段存在的缺失值進行填補。下面對該過程使用算法1進行描述。

算法1 AP_For_Filling_Missing_Values。

輸入：待修復數據集，阻尼系數和最大迭代次數。

輸出：已進行缺失值填補的數據集。

初始化λ，maxIterNum，計算相似度矩陣S

setChineseToNum()

setPreference()

Fori:=0 TomaxIterNum

updateResponsibility()

updateAvailability()

End For

assignClusterPoint()

setPredictValue()

setNewValue()

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

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

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

樣本點間的a(i,k)的計算方法為：

在計算了樣本點間的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算法實現的過程中任何點的r(i,k)和a(i,k)都與定義聚類中心相關聯。對于a(i,k)+r(i,k)取最大值時的k值，如果k=i，則將數據點i作為聚類中心，否則將數據點k作為點i的聚類中心。

assignClusterPoint()方法用于將各數據點分配到聚類中心所在的類中。若迭代次數超過設定的最大值或者當聚類中心在若干次迭代過程中不再發生改變，則停止計算，得出最終的聚類中心及各個類所擁有的樣本點。setPredictValue()方法用于得到AP聚類算法對于缺失值的預測值，setNewValue()方法用于將數據集的缺失值填補為AP聚類算法所預測出的值以得到經過AP聚類算法處理后的不含缺失值的數據集，以便進行后續從數據集中自動發現函數依賴的步驟。

2.2 發現函數依賴的TANE算法

從數據集中自動發現字段之間的關聯關系，可以減少領域專家配置數據質量檢測規則的工作量，提高工作效率；并且，自動產生的數據質量檢測規則可以作為進一步檢測臟數據的指標，提升高校數據所擁有的數據質量。本文使用TANE算法從已進行了缺失值填補的數據集上自動發現函數依賴。從文獻[7]可知，該算法使用的是基于層次搜索屬性包含格的方法，算法首先從空集開始，向下生成屬性集，然后在當前層計算候選函數依賴，對候選函數依賴進行非平凡性和最小性的檢測，剪掉不滿足要求的節點，節約搜索空間，然后繼續從當前層生成下一層，重復以上過程，直到找出所有滿足要求的函數依賴。當算法在處理每一層的屬性集X時，它會檢測形如XA}→A(A∈X)的函數依賴是否成立，這就可以保證只有非平凡的函數依賴會被考慮。另外，算法由小到大的擴展方向可以保證只有最小的函數依賴被輸出，并且由于TANE算法基于的是上一層的結果來生成下一層的屬性集，也減小了相應的計算量。下面對算法2 TANE算法進行詳細描述。

算法2 TANE。

輸入：已進行缺失值填補的數據集。

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

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層計算出第L2層，由第L2層計算出第L3層，以此類推。當第Ll層不為空時，使用compute_dependencies(Ll)方法來計算該層的候選函數依賴。方法為：對于第Ll層中的每個屬性集X先計算C+(X)。要得到C+(X)，需要先計算C+(XA})，此處的屬性A是屬性集X中的單一屬性，然后把計算出的結果取交集，即可得到C+(X)。對于每一個屬于X∩C+(X)集合中的屬性A，如果XA}→A是有效的，則輸出XA}→A這一候選函數依賴，并且從C+(X)中移除屬性A，從C+(X)中移除所有屬于RX集合的屬性B。

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

3 實驗結果及分析

本實驗的運行環境為使用Intel酷睿i7- 3.2 GHz的CPU，16 GB內存的Windows計算機，實驗使用的數據集分為測試數據集和真實數據集。測試數據集來自UCI數據集的breast-cancer-Wisconsin數據集，包含腫塊厚度、細胞大小均勻性、細胞形狀均勻性、類別等11個屬性，共有699條元組。使用breast-cancer-Wisconsin數據集的原因在于該數據集的屬性之間存在著一定的關聯關系，便于進行函數依賴自動發現這一過程。表2為該數據集的字段信息。

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

真實數據集來自某高校學生信息數據集，共有30 648條元組，是用學生信息表以及貧困補助表兩者進行合并形成的數據集。表3為該數據集的字段信息。

表3 高校數據集字段信息 Tab. 3 Field information of university dataset

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

圖3顯示了在缺失率e的取值分別為0.02、0.04、0.06、0.08時AP聚類算法填補測試數據集上的缺失值的準確率，可以看出，缺失值填補的準確率隨著e值的增大呈現平穩增長的趨勢，在e大于等于0.04時維持在較高水平，并且在缺失率為0.06時，使用AP聚類算法填補缺失值的準確率最高，為94.87%，在缺失率為0.08時，由于字段值缺失數增加使得最近鄰點以及近鄰區域對聚類代表點產生了影響，導致準確率有所下降，但仍然保持在90%以上。

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

圖4是在測試數據集上將本文的APTANE方法分別與TANE、DFD、FUN算法所發現出的函數依賴個數的對比。

圖4 不同缺失率下的各算法發現的FDs個數Fig. 4 Number of FDs found by each algorithm under different missing rates

TANE、DFD和FUN算法都是基于屬性格的遍歷來發現函數依賴的方法，它們在具有大量元組數的數據集上表現比差異-一致集算法以及依賴推理算法更好[11]，因此本文根據實際應用場景中高校真實數據集的特點選擇將APTANE方法與TANE、DFD、FUN算法進行比較。從圖4可以看出：在不處理缺失值，直接從原始數據集上使用TANE、DFD、FUN這三個算法時，發現的函數依賴個數較少，三個算法中，DFD算法能發現的函數依賴最多為21個，而FUN算法和TANE算法不管缺失率的值如何變化，均只能發現8個；而本文提出的APTANE方法由于對數據集中的缺失值進行了填補，完善了字段值之間隱藏的關聯信息，因此能發現出更多的函數依賴，并且個數接近于測試數據集不存在空值時所發現出的46個函數依賴。

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

表4 e的取值為0和0.06時APTANE發現的FDs對比 Tab. 4 Comparison of FDs found by APTANE when e is 0 and 0.06

圖5 高校數據集上各算法發現出的FDs個數Fig. 5 Number of FDs found by each algorithm in university dataset

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

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

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

本文實驗在測試數據集和真實數據集上的結果表明了使用AP聚類算法來填補缺失值是有效且準確的，并且在填補缺失值后的數據集上發現的函數依賴的個數更多，含義更準確，能有效減少領域專家的工作量，提升高校數據的數據質量。

4 結語

為了解決在高校數據集存在缺失值時，發現的函數依賴個數較少且不準確的問題，本文提出了一種使用AP聚類算法和TANE算法相結合的APTANE方法。經過該方法的處理可以有效地補全缺失信息，提高發現的函數依賴的個數和準確度，為學校領導、老師從數據中分析學生行為、制定發展方略提供數據支撐，并且本文也證明了AP聚類算法在對缺失值進行填補方面是有效且穩定的。

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