多關系關聯規則挖掘在考勤數據分析中的應用

姜麗莉 黃承寧

摘要：該文將關聯規則挖掘算法應用于某煤礦的考勤數據的分析。針對關系數據庫的特點，對傳統的關聯規則挖掘算法進行了優化。算法借鑒元組ID傳播思想，將關系圖進行切分，對每一部分建立了全局的鍵值映射哈希表，通過哈希表，將單表挖掘出的項集進行連接，從而得到多關系間的頻繁項集。最后設計并實現了一個多關系的關聯規則挖掘系統，對考勤數據進行分析。

關鍵詞：關聯規則;數據挖掘;多關系

中圖分類號：TP393? ? ? ? 文獻標識碼：A? ? ? ?文章編號：1009-3044（2018）36-0003-02

關聯規則挖掘是數據挖掘的重要研究領域之一。傳統算法是將多個關系連接成一個泛關系表。這種算法存在著性能較低、統計偏斜和信息丟失等問題。針對性能問題，許多學者根據元組傳播的思想，提出了一些避免多表間直接連接的算法。但是，這些算法一般都是針對星型模式或者雪花模式的數據庫，不可以直接應用于更加廣泛的實體聯系模式的數據庫。另外，這些算法存在著統計偏斜問題。基于ILP（歸納邏輯程序設計）技術的關聯規則挖掘算法可以避免統計偏斜問題，但是存在著效率低、可擴展性差等問題。

本文旨在分析某煤礦的考勤數據，數據存放在關系數據庫SQL Server中。為了避免統計偏斜、信息丟失等問題，需要在傳統算法的基礎之上，利用關系數據庫的特點，對算法進行優化。

1 關系數據庫中項集特點

1.1 關系圖

在關系數據庫中，關系模式是有概念模式生成的。概念模式的表示方法一般為E-R圖。在E-R圖中，包括實體和聯系兩個元素，實體與實體之間的聯系類型有“1對1”、“1對多”和 “多對多”三種，根據一定的規則和規范化要求，可以導出由實體和聯系生成的關系模式。因此，關系模式可以分為實體關系模式（實體表）和聯系關系（聯系表）模式兩類。根據關系數據模型的參照完整性要求，關系表之間存在主外鍵的約束關系，形成了關系圖。

1.2 關系項集

關系表的屬性都具有多值特點，故跟事務數據庫不同，關系數據庫的項集中，每一項都是一個屬性-值對。多關系項集是項的集合，同一項集的不同項可以來自數據庫中的不同關系。而為了使不同關系的項出現在同一項集中，需要對關系進行連接操作。

若一個項集中包含多個關系的項，其頻數的定義一般會被定義為項集在連接后的查詢表中的出現次數。這種定義方式很容易導致統計偏斜問題。

1.3 強語義項集

在關系數據庫中，隨著關系表間連接路徑的增長，項集間的語義關系越弱，實際意義也越小[1]。

為了挖掘強語義的關聯規則，將E-R圖進行切分。每一部分包括中心位置的聯系表，包含聯系表中的外鍵的實體表（主實體表），和包含這些實體表的外鍵的實體表（附屬實體表）。針對每一部分包含的關系表進行多關系關聯規則挖掘。某一實體可能會同時屬于不同的部分，但無須重復對該實體進行單表的挖掘。算法可以只考慮其中的一個部分，例如圖1所示。

2 改進算法的描述

2.1 挖掘頻繁項集

根據上述分析，在關系數據庫中，為了挖掘強語義的頻繁項集，需要將關系圖進行切分。對一個切分后的關系圖，包含如下三類表：主實體表、附屬實體表和聯系表。

基于這些關系表的頻繁挖掘方法可以采用直接連接的方法，形成一張大表。但是這種方法會導致性能低下、統計偏斜等問題。故本文利用關系數據庫的特點對傳統方法進行改進。算法主要包括如下4個步驟。

1） 挖掘單表頻繁項集

挖掘單表的頻繁項集可以采用現有的經典關聯規則挖掘算法Apriori算法、Fp-Growth算法，或者使用一些基于經典算法的改進算法。但是本文對挖掘出的頻繁相項集的格式做如下規定。頻繁項集包括鍵鏈表、頻繁項集、支持計數三個域，如圖2所示。其中鍵鏈表指的是包含該項集的鍵的鏈表，用于實現項集的虛擬連接。支持計數為鍵鏈表中結點的個數。

2） 構建元組ID映射哈希表

一般認為，在關系數據庫中，如果將多張表進行連接操作，形成的臨時表中包含某個項集，則可以認為該項集在數據庫中是存在的，是待挖掘的對象。而如果該項集中的項存在于不同的關系表中，則可以認為這些不同的項是可以連接的。借鑒元組ID傳播方法，可以將多個項集通過項集對應的鍵進行連接，進而實現關系表的虛擬連接。通過該方法，可以通過項集的連接，挖掘存在于多個關系表中的頻繁項集。

在關系數據庫中，附屬實體表與主實體表的聯系類型為“1對多”，每一個附屬實體的鍵對應若干個主實體表的鍵。而主實體表與聯系表之間的聯系類型也是“1對多”，每一個主實體表的鍵，對應多個聯系表的鍵。對于“多”方的多個鍵可以通過鏈表的方式連起來。而對于聯系類型“1對多”，可以創建一個哈希表，實現從“1”方到“多”方的映射。該哈希表的鍵為“1”方的鍵，哈希表的值為與“1”方對應的“多”方的鍵的鏈表。因此，可以采用如下方法，構建全局的元組ID傳播哈希表，將多個關系實現虛擬連接。

（1） 創建附屬實體與主實體的哈希表

遍歷每個主實體表，對每個元組中的每個外鍵，創建該外鍵與實體表主鍵的映射，實現附屬實體與主實體鍵的哈希表，其鍵為該外鍵（對應附屬實體的主鍵），其值為該外鍵在該元組中對應的主鍵。

（2） 創建主實體表與聯系表的哈希表

遍歷每個聯系表，對每個元組中的每個外鍵，創建該外鍵與聯系表主鍵的映射，實現主實體表與聯系表的鍵的哈希表，其鍵為該外鍵（對應主實體的主鍵），其值為該外鍵在該元組中對應的主鍵。

3） 計算主實體表與附屬實體表頻繁項集

設由第（1）步得到的某一實體[Ei]的所有頻繁項集的集合為[MSi]，頻繁項集數為[m]，附屬實體個數為[n]，每個附屬實體[Eij][（0≤j≤n）]的所有頻繁項集的集合為[ASj]，頻繁項集數為[aj];由第（2）步得到的[Eij]與[Ei]的ID傳播哈希表為[Hashij]，則連接算法描述如下。

輸入：[MSi]，[m]，對應[n]個[Eij][（0≤j≤n）]的[ASj]，[aj]，[Hashij]

輸出：存在于主實體[Ei]和[n]個附屬實體[Eij][（0≤j≤n）]間的所有頻繁項集[MASi]。

算法：

（1） MASi：=[?]

（2） 計算[Ei]與[n]個[Eij]的所有組合。

（3） For 每一個組合

（3-1）利用Hash表表組合內項集進行連接

（3-2）利用Hash表及實體的鍵鏈表，求連接后項集對于主實體[Ei]的支持計數。

（3-3）若項集支持計數大于最小支持度，指定其鍵為對應主實體[Ei]的鍵，并入[MASi]。

由于實際數據庫中，一張主實體表中包含的外鍵個數一般不會太多，故步驟2）中組合數不會太大。步驟（3-1）中，包含外鍵的項集不參與連接，該類頻繁項集實際意義為該外鍵對應的實體與主實體屬性的聯系。

4） 計算主實體表與聯系表的頻繁項集

主實體表與聯系表的關系與附屬實體表與主實體表的關系類似，都是“1對多”的關系，故可以參照步驟3），將每個聯系表的頻繁項集與其對應的主實體表的頻繁項集進行連接。

2.2 關聯規則的提取

關聯規則的提取方法與傳統算法是一致。

根據2.1可以，挖掘出的每個頻繁項集都有一個鍵鏈表，規則前件與規則后件的鍵鏈表相同，同一張表的關聯規則，其置信度計算是針對單張表的，多表見的關聯規則，其置信度的計算是針對多張表的連接的。因此，可以最大限度地避免統計偏斜。

3 基于改進算法的挖掘系統

本文待分析的數據涉及員工基本信息表、工種表、部門表、出勤表和勤種表五張表。其中主關系表有5000條記錄，聯系表有44萬條記錄。系統的開發環境為Visual C++2010，后臺數據庫為SQL Server 2008。系統主要包括數據導入、數據預處理、系統配置、頻繁項集挖掘和關聯規則導出五個功能模塊。

通過菜單項“數據導入”，導入需要分析的數據（可以選擇指定的時間段），再通過菜單項“數據預處理”對所選擇的數據進行數據清洗、格式轉換等操作，然后通過菜單項“系統配置”設置本系統的最小支持度和最小置信度，最后通過菜單項“頻繁屬性集挖掘”，挖掘出所選數據的頻繁項集。

得到頻繁項集以后，通過菜單項“關聯規則導出”，即可導出關聯規則，對導出的關聯規則，進行進一步分析，找到有意義的規則，對公司的決策提供支持。

本文旨在對某煤礦的考勤數據進行關聯規則挖掘。在借鑒前人研究的基礎上，充分研究并利用了關系數據庫的特點，對傳統的關聯規則進行了優化，避免了統計偏斜和信息丟失的現象，優化了性能，實現了一個簡單的關聯規則挖掘系統，供該煤礦的考勤數據分析使用。

參考文獻：

[1] 何軍，劉紅巖，杜小勇.挖掘多關系關聯規則[J].軟件學報，2007，18（11）：2752-2765.

[2] 崔妍，包志強.關聯規則挖掘綜述[J].計算機應用研究，2016，33（2）：330-334.

[3] 王英博，馬菁，柴佳佳，等.基于Hadoop平臺的改進關聯規則挖掘算法[J].計算機工程，2016，42（10）：69-74，79.

[通聯編輯：光文玲]