多關(guān)系關(guān)聯(lián)規(guī)則挖掘在考勤數(shù)據(jù)分析中的應(yīng)用

姜麗莉 黃承寧

摘要：該文將關(guān)聯(lián)規(guī)則挖掘算法應(yīng)用于某煤礦的考勤數(shù)據(jù)的分析。針對(duì)關(guān)系數(shù)據(jù)庫的特點(diǎn)，對(duì)傳統(tǒng)的關(guān)聯(lián)規(guī)則挖掘算法進(jìn)行了優(yōu)化。算法借鑒元組ID傳播思想，將關(guān)系圖進(jìn)行切分，對(duì)每一部分建立了全局的鍵值映射哈希表，通過哈希表，將單表挖掘出的項(xiàng)集進(jìn)行連接，從而得到多關(guān)系間的頻繁項(xiàng)集。最后設(shè)計(jì)并實(shí)現(xiàn)了一個(gè)多關(guān)系的關(guān)聯(lián)規(guī)則挖掘系統(tǒng)，對(duì)考勤數(shù)據(jù)進(jìn)行分析。

關(guān)鍵詞：關(guān)聯(lián)規(guī)則;數(shù)據(jù)挖掘;多關(guān)系

中圖分類號(hào)：TP393? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A? ? ? ?文章編號(hào)：1009-3044（2018）36-0003-02

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

本文旨在分析某煤礦的考勤數(shù)據(jù)，數(shù)據(jù)存放在關(guān)系數(shù)據(jù)庫SQL Server中。為了避免統(tǒng)計(jì)偏斜、信息丟失等問題，需要在傳統(tǒng)算法的基礎(chǔ)之上，利用關(guān)系數(shù)據(jù)庫的特點(diǎn)，對(duì)算法進(jìn)行優(yōu)化。

1 關(guān)系數(shù)據(jù)庫中項(xiàng)集特點(diǎn)

1.1 關(guān)系圖

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

1.2 關(guān)系項(xiàng)集

關(guān)系表的屬性都具有多值特點(diǎn)，故跟事務(wù)數(shù)據(jù)庫不同，關(guān)系數(shù)據(jù)庫的項(xiàng)集中，每一項(xiàng)都是一個(gè)屬性-值對(duì)。多關(guān)系項(xiàng)集是項(xiàng)的集合，同一項(xiàng)集的不同項(xiàng)可以來自數(shù)據(jù)庫中的不同關(guān)系。而為了使不同關(guān)系的項(xiàng)出現(xiàn)在同一項(xiàng)集中，需要對(duì)關(guān)系進(jìn)行連接操作。

若一個(gè)項(xiàng)集中包含多個(gè)關(guān)系的項(xiàng)，其頻數(shù)的定義一般會(huì)被定義為項(xiàng)集在連接后的查詢表中的出現(xiàn)次數(shù)。這種定義方式很容易導(dǎo)致統(tǒng)計(jì)偏斜問題。

1.3 強(qiáng)語義項(xiàng)集

在關(guān)系數(shù)據(jù)庫中，隨著關(guān)系表間連接路徑的增長(zhǎng)，項(xiàng)集間的語義關(guān)系越弱，實(shí)際意義也越小[1]。

為了挖掘強(qiáng)語義的關(guān)聯(lián)規(guī)則，將E-R圖進(jìn)行切分。每一部分包括中心位置的聯(lián)系表，包含聯(lián)系表中的外鍵的實(shí)體表（主實(shí)體表），和包含這些實(shí)體表的外鍵的實(shí)體表（附屬實(shí)體表）。針對(duì)每一部分包含的關(guān)系表進(jìn)行多關(guān)系關(guān)聯(lián)規(guī)則挖掘。某一實(shí)體可能會(huì)同時(shí)屬于不同的部分，但無須重復(fù)對(duì)該實(shí)體進(jìn)行單表的挖掘。算法可以只考慮其中的一個(gè)部分，例如圖1所示。

2 改進(jìn)算法的描述

2.1 挖掘頻繁項(xiàng)集

根據(jù)上述分析，在關(guān)系數(shù)據(jù)庫中，為了挖掘強(qiáng)語義的頻繁項(xiàng)集，需要將關(guān)系圖進(jìn)行切分。對(duì)一個(gè)切分后的關(guān)系圖，包含如下三類表：主實(shí)體表、附屬實(shí)體表和聯(lián)系表。

基于這些關(guān)系表的頻繁挖掘方法可以采用直接連接的方法，形成一張大表。但是這種方法會(huì)導(dǎo)致性能低下、統(tǒng)計(jì)偏斜等問題。故本文利用關(guān)系數(shù)據(jù)庫的特點(diǎn)對(duì)傳統(tǒng)方法進(jìn)行改進(jìn)。算法主要包括如下4個(gè)步驟。

1） 挖掘單表頻繁項(xiàng)集

挖掘單表的頻繁項(xiàng)集可以采用現(xiàn)有的經(jīng)典關(guān)聯(lián)規(guī)則挖掘算法Apriori算法、Fp-Growth算法，或者使用一些基于經(jīng)典算法的改進(jìn)算法。但是本文對(duì)挖掘出的頻繁相項(xiàng)集的格式做如下規(guī)定。頻繁項(xiàng)集包括鍵鏈表、頻繁項(xiàng)集、支持計(jì)數(shù)三個(gè)域，如圖2所示。其中鍵鏈表指的是包含該項(xiàng)集的鍵的鏈表，用于實(shí)現(xiàn)項(xiàng)集的虛擬連接。支持計(jì)數(shù)為鍵鏈表中結(jié)點(diǎn)的個(gè)數(shù)。

2） 構(gòu)建元組ID映射哈希表

一般認(rèn)為，在關(guān)系數(shù)據(jù)庫中，如果將多張表進(jìn)行連接操作，形成的臨時(shí)表中包含某個(gè)項(xiàng)集，則可以認(rèn)為該項(xiàng)集在數(shù)據(jù)庫中是存在的，是待挖掘的對(duì)象。而如果該項(xiàng)集中的項(xiàng)存在于不同的關(guān)系表中，則可以認(rèn)為這些不同的項(xiàng)是可以連接的。借鑒元組ID傳播方法，可以將多個(gè)項(xiàng)集通過項(xiàng)集對(duì)應(yīng)的鍵進(jìn)行連接，進(jìn)而實(shí)現(xiàn)關(guān)系表的虛擬連接。通過該方法，可以通過項(xiàng)集的連接，挖掘存在于多個(gè)關(guān)系表中的頻繁項(xiàng)集。

在關(guān)系數(shù)據(jù)庫中，附屬實(shí)體表與主實(shí)體表的聯(lián)系類型為“1對(duì)多”，每一個(gè)附屬實(shí)體的鍵對(duì)應(yīng)若干個(gè)主實(shí)體表的鍵。而主實(shí)體表與聯(lián)系表之間的聯(lián)系類型也是“1對(duì)多”，每一個(gè)主實(shí)體表的鍵，對(duì)應(yīng)多個(gè)聯(lián)系表的鍵。對(duì)于“多”方的多個(gè)鍵可以通過鏈表的方式連起來。而對(duì)于聯(lián)系類型“1對(duì)多”，可以創(chuàng)建一個(gè)哈希表，實(shí)現(xiàn)從“1”方到“多”方的映射。該哈希表的鍵為“1”方的鍵，哈希表的值為與“1”方對(duì)應(yīng)的“多”方的鍵的鏈表。因此，可以采用如下方法，構(gòu)建全局的元組ID傳播哈希表，將多個(gè)關(guān)系實(shí)現(xiàn)虛擬連接。

（1） 創(chuàng)建附屬實(shí)體與主實(shí)體的哈希表

遍歷每個(gè)主實(shí)體表，對(duì)每個(gè)元組中的每個(gè)外鍵，創(chuàng)建該外鍵與實(shí)體表主鍵的映射，實(shí)現(xiàn)附屬實(shí)體與主實(shí)體鍵的哈希表，其鍵為該外鍵（對(duì)應(yīng)附屬實(shí)體的主鍵），其值為該外鍵在該元組中對(duì)應(yīng)的主鍵。

（2） 創(chuàng)建主實(shí)體表與聯(lián)系表的哈希表

遍歷每個(gè)聯(lián)系表，對(duì)每個(gè)元組中的每個(gè)外鍵，創(chuàng)建該外鍵與聯(lián)系表主鍵的映射，實(shí)現(xiàn)主實(shí)體表與聯(lián)系表的鍵的哈希表，其鍵為該外鍵（對(duì)應(yīng)主實(shí)體的主鍵），其值為該外鍵在該元組中對(duì)應(yīng)的主鍵。

3） 計(jì)算主實(shí)體表與附屬實(shí)體表頻繁項(xiàng)集

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

輸入：[MSi]，[m]，對(duì)應(yīng)[n]個(gè)[Eij][（0≤j≤n）]的[ASj]，[aj]，[Hashij]

輸出：存在于主實(shí)體[Ei]和[n]個(gè)附屬實(shí)體[Eij][（0≤j≤n）]間的所有頻繁項(xiàng)集[MASi]。

算法：

（1） MASi：=[?]

（2） 計(jì)算[Ei]與[n]個(gè)[Eij]的所有組合。

（3） For 每一個(gè)組合

（3-1）利用Hash表表組合內(nèi)項(xiàng)集進(jìn)行連接

（3-2）利用Hash表及實(shí)體的鍵鏈表，求連接后項(xiàng)集對(duì)于主實(shí)體[Ei]的支持計(jì)數(shù)。

（3-3）若項(xiàng)集支持計(jì)數(shù)大于最小支持度，指定其鍵為對(duì)應(yīng)主實(shí)體[Ei]的鍵，并入[MASi]。

由于實(shí)際數(shù)據(jù)庫中，一張主實(shí)體表中包含的外鍵個(gè)數(shù)一般不會(huì)太多，故步驟2）中組合數(shù)不會(huì)太大。步驟（3-1）中，包含外鍵的項(xiàng)集不參與連接，該類頻繁項(xiàng)集實(shí)際意義為該外鍵對(duì)應(yīng)的實(shí)體與主實(shí)體屬性的聯(lián)系。

4） 計(jì)算主實(shí)體表與聯(lián)系表的頻繁項(xiàng)集

主實(shí)體表與聯(lián)系表的關(guān)系與附屬實(shí)體表與主實(shí)體表的關(guān)系類似，都是“1對(duì)多”的關(guān)系，故可以參照步驟3），將每個(gè)聯(lián)系表的頻繁項(xiàng)集與其對(duì)應(yīng)的主實(shí)體表的頻繁項(xiàng)集進(jìn)行連接。

2.2 關(guān)聯(lián)規(guī)則的提取

關(guān)聯(lián)規(guī)則的提取方法與傳統(tǒng)算法是一致。

根據(jù)2.1可以，挖掘出的每個(gè)頻繁項(xiàng)集都有一個(gè)鍵鏈表，規(guī)則前件與規(guī)則后件的鍵鏈表相同，同一張表的關(guān)聯(lián)規(guī)則，其置信度計(jì)算是針對(duì)單張表的，多表見的關(guān)聯(lián)規(guī)則，其置信度的計(jì)算是針對(duì)多張表的連接的。因此，可以最大限度地避免統(tǒng)計(jì)偏斜。

3 基于改進(jìn)算法的挖掘系統(tǒng)

本文待分析的數(shù)據(jù)涉及員工基本信息表、工種表、部門表、出勤表和勤種表五張表。其中主關(guān)系表有5000條記錄，聯(lián)系表有44萬條記錄。系統(tǒng)的開發(fā)環(huán)境為Visual C++2010，后臺(tái)數(shù)據(jù)庫為SQL Server 2008。系統(tǒng)主要包括數(shù)據(jù)導(dǎo)入、數(shù)據(jù)預(yù)處理、系統(tǒng)配置、頻繁項(xiàng)集挖掘和關(guān)聯(lián)規(guī)則導(dǎo)出五個(gè)功能模塊。

通過菜單項(xiàng)“數(shù)據(jù)導(dǎo)入”，導(dǎo)入需要分析的數(shù)據(jù)（可以選擇指定的時(shí)間段），再通過菜單項(xiàng)“數(shù)據(jù)預(yù)處理”對(duì)所選擇的數(shù)據(jù)進(jìn)行數(shù)據(jù)清洗、格式轉(zhuǎn)換等操作，然后通過菜單項(xiàng)“系統(tǒng)配置”設(shè)置本系統(tǒng)的最小支持度和最小置信度，最后通過菜單項(xiàng)“頻繁屬性集挖掘”，挖掘出所選數(shù)據(jù)的頻繁項(xiàng)集。

得到頻繁項(xiàng)集以后，通過菜單項(xiàng)“關(guān)聯(lián)規(guī)則導(dǎo)出”，即可導(dǎo)出關(guān)聯(lián)規(guī)則，對(duì)導(dǎo)出的關(guān)聯(lián)規(guī)則，進(jìn)行進(jìn)一步分析，找到有意義的規(guī)則，對(duì)公司的決策提供支持。

本文旨在對(duì)某煤礦的考勤數(shù)據(jù)進(jìn)行關(guān)聯(lián)規(guī)則挖掘。在借鑒前人研究的基礎(chǔ)上，充分研究并利用了關(guān)系數(shù)據(jù)庫的特點(diǎn)，對(duì)傳統(tǒng)的關(guān)聯(lián)規(guī)則進(jìn)行了優(yōu)化，避免了統(tǒng)計(jì)偏斜和信息丟失的現(xiàn)象，優(yōu)化了性能，實(shí)現(xiàn)了一個(gè)簡(jiǎn)單的關(guān)聯(lián)規(guī)則挖掘系統(tǒng)，供該煤礦的考勤數(shù)據(jù)分析使用。

參考文獻(xiàn)：

[1] 何軍，劉紅巖，杜小勇.挖掘多關(guān)系關(guān)聯(lián)規(guī)則[J].軟件學(xué)報(bào)，2007，18（11）：2752-2765.

[2] 崔妍，包志強(qiáng).關(guān)聯(lián)規(guī)則挖掘綜述[J].計(jì)算機(jī)應(yīng)用研究，2016，33（2）：330-334.

[3] 王英博，馬菁，柴佳佳，等.基于Hadoop平臺(tái)的改進(jìn)關(guān)聯(lián)規(guī)則挖掘算法[J].計(jì)算機(jī)工程，2016，42（10）：69-74，79.

[通聯(lián)編輯：光文玲]