改進的頻繁項集挖掘算法及其應(yīng)用研究

顧軍華 李如婷 張亞娟* 董彥琦

1(河北工業(yè)大學(xué)人工智能與數(shù)據(jù)科學(xué)學(xué)院 天津 300401)2(河北省大數(shù)據(jù)計算重點實驗室 天津 300401)

0 引 言

在當今大數(shù)據(jù)時代，如何從海量的數(shù)據(jù)中去粗存精，挖掘出隱藏的、有價值的信息，為各行各業(yè)的管理者提供決策支持具有十分重要的意義[1]。關(guān)聯(lián)規(guī)則挖掘是數(shù)據(jù)挖掘中一個十分重要的研究方向，其主要任務(wù)是發(fā)現(xiàn)數(shù)據(jù)庫中項集之間隱藏的關(guān)系，且廣泛應(yīng)用于商店營銷、庫存控制、農(nóng)作物選擇和生物信息學(xué)等多個領(lǐng)域[2]。關(guān)聯(lián)規(guī)則挖掘主要包括挖掘頻繁項集和發(fā)現(xiàn)強關(guān)聯(lián)規(guī)則兩部分，挖掘頻繁項集是其中很重要的一步。因此許多用于挖掘頻繁項集的算法被提出，這些算法主要分為兩類：Apriori類算法和FP-growth類算法[3]。

Apriori算法最初是由Agrawal等[4]提出來的，該算法先通過自連接(k-1)-項集產(chǎn)生候選k-項集，然后根據(jù)最小支持度和Apriori先驗定理對候選項集進行剪枝，從而獲得頻繁k-項集。Apriori算法簡單且易于理解，但是面對龐大的數(shù)據(jù)時，該算法存在以下兩個問題：(1) 產(chǎn)生大量的候選項集；(2) 需要重復(fù)多次掃描數(shù)據(jù)庫，造成了巨大的I/O負載。與Apriori類算法不同，F(xiàn)P-growth算法只需要兩次掃描數(shù)據(jù)庫且沒有候選項集生成，挖掘效率較Apriori算法有很大提升[5]。然而FP-growth算法在挖掘過程中需要頻繁構(gòu)建條件模式樹(Frequent Pattern tree,FP-tree)和條件模式基，帶來了巨大的時間和空間消耗。

利用FP-growth算法的思想，Deng等提出了PrePost算法[6]，該算法通過前序和后序遍歷FP-tree，構(gòu)建了一棵基于前序和后序編碼的樹(Pre-order and Post-order Code tree,PPC-tree)，從中得到1-項集的N-list，然后通過迭代連接兩個項集的N-list得到新的項集，減少了時間和空間的消耗。但PPC-tree的構(gòu)建需要兩次遍歷樹，而且在連接N-list時沒有進行剪枝操作，產(chǎn)生了大量冗余的N-list。在此基礎(chǔ)上，Deng等又提出了FIN算法[7]，該算法提出了一種新的數(shù)據(jù)結(jié)構(gòu)——Nodesets來挖掘頻繁項集，Nodesets是從前綴編碼樹(Pre-order Code tree,POC-tree)中得到的。相比PrePost算法，F(xiàn)IN算法在構(gòu)建POC-tree時只需要前序遍歷樹，建樹過程簡單，而且挖掘過程中使用了父子等價的剪枝策略，縮小了挖掘空間。但是在連接兩個Node-sets時，需要多次遍歷POC-tree，判斷二者是否滿足連接條件，耗費了大量的時間。為此，Aryabarzan等[8]提出了negFIN算法，該算法使用位圖表示樹中的節(jié)點信息，通過位運算連接兩個(k-1)-項集得到k-項集，避免了多次遍歷樹的過程，挖掘效率較FIN算法有一定提高。但是當面對大型數(shù)據(jù)庫時，位運算的過程較復(fù)雜，而且使用位圖表示節(jié)點會占用大量的空間。

上述基于FP-growth思想的算法雖然提高了挖掘頻繁項集的效率，但大都存在生成頻繁k-項集過程復(fù)雜、耗費空間多的問題，如：FIN算法在連接Nodesets時需要多次遍歷樹，耗費了大量時間；negFIN算法使用位圖表示節(jié)點會占用大量空間。為此，本文提出了一種基于前序完全構(gòu)造鏈表(Pre and Finishbuilding List,PF-List)的頻繁項集挖掘算法(PF-List Frequent Itemsets Mining,PFLFIM)。該算法在POC-tree的基礎(chǔ)上，增加了節(jié)點在樹中被完全構(gòu)造的順序編號(Finishbuilding-order)，形成了一棵基于前序和完全構(gòu)造順序編碼的樹(Pre-order and Finishbuilding-order Coding tree,PFC-tree)，從中得到1-項集的PF-List，然后通過迭代連接(k-1)-項集的PF-List得到k-項集。在連接過程中，PFLFIM算法通過簡單比較兩個PF-List的pre-order和finishbuilding-order編號進行連接，避免了復(fù)雜的連接運算。此外，該算法用模式搜索樹表示搜索空間，并使用包含索引、提前停止交集和父子等價策略對搜索樹進行剪枝，減少了空間占用，加快了挖掘速度。在Pumsb和Retail數(shù)據(jù)集上進行實驗，結(jié)果表明，PFLFIM算法在運行時間和空間占用上均優(yōu)于FIN算法和negFIN算法。最后，利用PFLFIM算法對某高校人才數(shù)據(jù)進行關(guān)聯(lián)規(guī)則挖掘，從中提取隱含的且有價值的信息，并運用它們尋找影響人才發(fā)展的因素，為高校人才引進和選拔提供決策支持。

1 相關(guān)概念

1.1 基本概念

給定一個事務(wù)數(shù)據(jù)庫DB，如表1所示。設(shè)集合I={i1,i2,…,in}是數(shù)據(jù)庫中所有項的集合，集合T={T1,T2,…,Tm}是數(shù)據(jù)庫中所有事務(wù)的集合，且|DB|=m。每個事務(wù)Ti都是I的子集，即?Ti∈T,?Ti?I。

表1 事務(wù)數(shù)據(jù)庫DB

定義1設(shè)集合X={x1,x2,…,xk}是I的子集，即X?I，則稱X為I中的項集。如果項集X包含k個項，則稱X為k-項集。把包含項集X的事務(wù)數(shù)稱為X的支持度計數(shù)，記為support_count(X)，把X的支持度計數(shù)與事務(wù)總數(shù)之比稱為X的支持度，記為support(X)，其計算式表示為：

(1)

定義2給定一個最小支持度minSup(取值范圍為[0,1])，若support(X)≥minSup，則X是頻繁的，若X的長度為k，則稱X為頻繁k-項集。

由定義1可得表1所示數(shù)據(jù)庫的1-項集及其支持度計數(shù)，如表2所示。設(shè)minSup為0.4，由定義2可得頻繁1-項集為{a}、{b}、{c}、g0gggggg、{k}。將每個事務(wù)中不頻繁的項刪除，然后按項的支持度計數(shù)降序排列后的事務(wù)如表2所示。

表2 1-項集及其支持度計數(shù)

定義3關(guān)聯(lián)規(guī)則是形如X→Y的表達式，且X∩Y=?，它的強度可以用置信度衡量。置信度表示項集Y在包含X的事務(wù)中出現(xiàn)的頻繁程度，記為confidence(X→Y)，其計算式表示為：

(2)

式中:support(X∪Y)表示同時包含X和Y的事務(wù)數(shù)在事務(wù)數(shù)據(jù)庫中所占的比例，support_count(X∪Y)表示同時包含X和Y的事務(wù)數(shù)。給定一個最小置信度minConf(取值范圍為[0,1])，若confidence(X→Y)≥minConf，則稱X→Y是強關(guān)聯(lián)規(guī)則。

性質(zhì)1對于給定的事務(wù)數(shù)據(jù)庫DB，設(shè)定最小支持度和最小置信度，關(guān)聯(lián)規(guī)則挖掘是指查找數(shù)據(jù)庫中支持度不小于最小支持度且置信度不小于最小置信度的所有強關(guān)聯(lián)規(guī)則。

1.2 PFC-tree

PFC-tree是由一個空的root節(jié)點和前綴子樹構(gòu)成的，樹中的節(jié)點由item-name、count、child-list、pre-order和finishbuilding-order等五部分構(gòu)成。item-name存儲節(jié)點代表的項，count存儲從root到此節(jié)點的路徑表示的項集所匹配的事務(wù)數(shù)，child-list存儲節(jié)點的所有子節(jié)點，pre-order表示前序遍歷PFC-tree時節(jié)點的順序編號，finishbuilding-order表示節(jié)點在PFC-tree中被完全構(gòu)造的順序編號。

遍歷一次數(shù)據(jù)庫就可以得到PFC-tree中各節(jié)點的item-name、count、child-list和finishbuilding-order信息，然后前序遍歷PFC-tree，得到每個節(jié)點的pre-order，完成PFC-tree的構(gòu)建。同POC-tree相比，節(jié)點中的finishbuilding-order是在構(gòu)建PFC-tree時得到的，不用花費多余的時間。而且PFC-tree主要用于生成頻繁1-項集的PF-List，在生成列表后，可以直接從內(nèi)存中刪除。但POC-tree在構(gòu)建后仍需多次遍歷，消耗了大量的內(nèi)存。所以相比POC-tree，構(gòu)建PFC-tree在沒有耗費多余時間的基礎(chǔ)上，還節(jié)省了空間，提高了挖掘的效率。PFC-tree的構(gòu)建如算法1所示。

算法1構(gòu)建PFC-tree

輸入:事務(wù)數(shù)據(jù)庫DB,最小支持度minSup

輸出:頻繁1-項集F1,PFC-tree

1: 掃描數(shù)據(jù)庫DB,得到頻繁1-項集F1;

2: 根據(jù)F1處理數(shù)據(jù)庫中的事務(wù);

3: 創(chuàng)建根節(jié)點Node,Node.item-name←root,parent←Node;

4: 初始化finish=0;

5: for each事務(wù)中的項i do

6: 創(chuàng)建節(jié)點N,parent.child-list←N,

N.item-name←i,

N.count←包含i的事務(wù)數(shù);

N.finishbuilding-order←++finish;

parent←N;

7: end for

8: 遍歷PFC-tree,得到每個節(jié)點的前序編號pre-order;

9: returnF1,Node;

根據(jù)算法1，構(gòu)建表1所示數(shù)據(jù)庫的PFC-tree，如圖1所示。

圖1 事務(wù)數(shù)據(jù)庫對應(yīng)的PFC-tree

1.3 PF-List的概念與性質(zhì)

由PFC-tree可得到頻繁1-項集的PF-List，為了定義PF-List，首先給出PFC-tree中每個節(jié)點信息的定義。

定義4對于PFC-tree中的每個節(jié)點N，用<(pre-order,finishbuilding-order):count>表示N的信息，稱其為節(jié)點N的PF-info。

性質(zhì)2給定PFC-tree中的兩個節(jié)點N1和N2，N1和N2的前序編號和完全構(gòu)造編號分別為N1.pre-order、N1.finishbuilding-order和N2.pre-order、N2.finishbuilding-order。當且僅當N1.pre-orderN2.finishbuilding-order時，N1是N2的祖先。

定義5頻繁1-項集的PF-List是指將所有代表項i的PF-info按照前序編號升序排列得到的列表，頻繁1-項集{i}的PF-List記作PFL({i})。以圖1所示的PFC-tree為例，得到的頻繁1-項集的PF-List如圖2所示。例如，項集{b}的PF-List，PFL({b})={<(1,7):4>}。

圖2 頻繁1-項集的PF-List

性質(zhì)3若PFL(I)={<(pre1,finish1):c1>,<(pre2,finish2):c2>,…,<(pres,finishs):cs>}，那么項集I的支持度計數(shù)support_count(I)=c1+c2+…+cs。

定義6假設(shè)一個2-項集{ij}，其中項集{i}的支持度大于項集{j}的支持度,且PFL({i})={<(pre1i,finish1i):c1i>,<(pre2i,finish2i):c2i>,…,<(premi,finishmi):cmi>},PFL({j})={<(pre1j,finish1j):c1j>,<(pre2j,finish2j):c2j>,…,<(prenj,finishnj):cnj>}，根據(jù)以下規(guī)則生成2-項集{ij}的PF-List。

(1) 根據(jù)性質(zhì)2判斷，如果PFL({i})中某個節(jié)點<(premi,finishmi):cmi>是PFL({j})中某個節(jié)點<(prenj,finishnj):cnj>的祖先，那么將<(premi,finishmi):cnj>加入項集{ij}的PF-List。

(2) 檢查項集{ij}的PF-List，把前序編號相同的節(jié)點的count相加，合并為一個節(jié)點。

(3) 根據(jù)性質(zhì)3計算出項集{ij}的支持度計數(shù)support_count({ij})，若support_count({ij})≥minSup×|DB|，則項集{ij}是頻繁2-項集。

定義7頻繁k-項集的PF-List是通過連接兩個頻繁(k-1)-項集的PF-List得到的。設(shè)頻繁(k-1)-項集I1={ixi1i2…ik-2},I2={iyi1i2…ik-2},其中項集{ix}的支持度大于項集{iy}的支持度，且PFL(I1)={<(pre11,finish11):c11>,<(pre21,finish21):c21>,…,<(prem1,finishm1):cm1>，PFL(I2)={<(pre12,finish12):c12>,<(pre22,finish22):c22>,…,<(pren2,finishn2):cn2>}，根據(jù)定義6中的規(guī)則生成頻繁k-項集I=I1∪I2={ixiyi1i2…ik-2}。

例如:根據(jù)定義6，連接項集{b}和項集{a}的PF-List得到項集{ba}的過程如圖3所示；根據(jù)定義7，連接項集{ba}和項集{da}的PF-List得到項集{bda}的過程如圖4所示。

圖3 1-項集的PF-List連接

圖4 k-項集的PF-List連接

2 基于PF-List的頻繁項集挖掘算法

PFLFIM算法使用PF-List表示項集，通過簡單比較兩個PF-List的節(jié)點信息，判斷其是否滿足連接條件，若滿足則連接得到新的PF-List，從中得到頻繁項集及其支持度，連接過程較FIN算法和negFIN算法簡單，降低了時間復(fù)雜度。在挖掘頻繁項集的過程中，為了避免重復(fù)連接，PFLFIM算法用模式搜索樹代表搜索空間。在搜索過程中，使用了包含索引、提前停止交集和父子等價策略對搜索空間進行剪枝，縮小了算法的搜索空間，提高了挖掘效率。

2.1 頻繁項集挖掘

2.1.1模式搜索樹

在挖掘頻繁k-項集時，為了避免重復(fù)連接，PFLFIM算法使用模式搜索樹來代表搜索空間。模式搜索樹是根據(jù)事務(wù)數(shù)據(jù)庫中的項按照某全序關(guān)系≤L生成的[10]。對于表1中的事務(wù)數(shù)據(jù)庫DB，所有頻繁1-項集組成的項集F={b,d,a,k,c}，規(guī)定全序關(guān)系為將F中的項按照支持度計數(shù)降序進行排列，即b≤Ld≤La≤Lk≤Lc，則表1所示數(shù)據(jù)庫的模式搜索樹如圖5所示。樹的根節(jié)點為空集，其余節(jié)點都是F的非空子集，假定樹的最上層為第0層，層數(shù)依次遞增，每層都包含與該層層數(shù)一致的項集，那么通過遍歷樹的第k層就可以得到所有的k-項集。

圖5 數(shù)據(jù)庫DB的模式搜索樹

2.1.2優(yōu)化策略

遍歷模式搜索樹時，使用包含索引、提前停止交集和父子等價策略對模式搜索樹進行剪枝操作，從而減小了搜索空間。

包含索引是一門用于減少頻繁模式挖掘搜索空間的技術(shù)[9]。1-項集{i}的包含索引subsume({i})的定義表示為：

subsume({i})={j∈I|?Ni∈PFL(i),?Nj∈PFL(j)∧

Nj是Ni的祖先}

(3)

式中:Ni表示項集{i}的PF-List中的某個節(jié)點，Nj表示項集{j}的PF-List中的某個節(jié)點。若項集{i}的PF-List中的任何一個節(jié)點Ni，都可以在項集{j}的PF-List中找到一個祖先節(jié)點Nj，那么項集{j}就是項集{i}的包含索引。例如，從表1所示數(shù)據(jù)庫得到的1-項集及其包含索引如表3所示。

表3 1-項集和對應(yīng)的包含索引

性質(zhì)4若存在一個項集F，且F的包含索引subsume(F)={f1,f2,…,fs}，那么F與{f1,f2,…,fs}中任何一個非空子集求并集得到的項集的支持度都等于F的支持度，其計算式表示為：

support(F)=support(F∪J)|?J?subsume(F)

(4)

例如，表3中項集{k}的包含索引subsume({k})=g0gggggg，根據(jù)性質(zhì)4可知，support({dk})=support({k})=3。在挖掘頻繁項集時，使用包含索引策略，可以直接得到一些頻繁項集及其支持度，節(jié)省了執(zhí)行連接操作的時間，提高了算法的運行速度。

性質(zhì)5提前停止交集剪枝策略[11]。設(shè)有兩個頻繁(k-1)-項集I1和I2，使用提前停止交集策略連接I1和I2的PF-List的具體步驟如下所示：

(1) 根據(jù)性質(zhì)2，計算項集I1和I2的PF-List的總計數(shù)，分別記為C1和C2。

(2) 依次取兩個PF-List中的每個節(jié)點N，判斷與另一個PF-List中的節(jié)點是否存在祖先-后代的關(guān)系。如果不存在，若N∈PFL(I1)，則C1=C1-N.count，若N∈PFL(I2)，則C2=C2-N.count。

(3) 若C1

根據(jù)性質(zhì)5連接兩個頻繁(k-1)-項集I1和I2的PF-List，得到頻繁k-項集的過程，如算法2所示。

算法2連接頻繁(k-1)-項集的PF-List

輸入: PFL(I1),PFL(I2),最小支持度minSup

輸出: 頻繁k-項集Fk,PFL(Fk)

1:Fk←?,PFL(Fk)←?;

2: 初始化i=0,j=0,C1=0,C2=0;

4: for each PFL(I1)中的節(jié)點Nxdo

5: for each PFL(I2)中的節(jié)點Nydo

6: ifNx與Ny不存在祖先-后代關(guān)系then

7:C1=C1-Nx.count;

8:C2=C2-Ny.count;

9: ifC1

10: return null;

11: else

12:Fk=I1∪I2;

13: PFL(Fk)←{};

14: end if

15: end for

17: returnFk, PFL(Fk);

性質(zhì)6父子等價剪枝策略[12]。給定項集F和項i，且i?F。如果F的支持度等于F∪{i}的支持度，即support(F)=support(F∪{i})。則對于任意項集L，若L∩F=?且i?L，則L∪F的支持度等于L∪F∪{i}的支持度，即support(L∪F)=support(L∪F∪{i})。

證明：設(shè)I1=L∪F，I2=L∪F∪{i}，一個包含I1但不包含I2的事務(wù)T，由于i∈I2但i?I1，因此i?T。由于support(F)=support(F∪{i})，說明如果事務(wù)包含F(xiàn)的話，則肯定包含{i}。由于事務(wù)T包含I1且I1=L∪F，說明事務(wù)T包含F(xiàn)，則事務(wù)T包含{i}，即i∈T，與上面矛盾。因此如果事務(wù)T包含I1的話則必包含I2，則support(L∪F)=support(L∪F∪{i})。證畢。

例如，項集{bk}的PFL({bk})={<(1,7):2>}，項集{bk}和項集{dk}連接得到的項集{bdk}的PFL({bdk})={<(1,7):2>}，項集{bk}的支持度計數(shù)等于項集{bdk}的支持度計數(shù)，即support({bk})=support({bdk})。那么模式搜索樹中，代表項集{bdk}節(jié)點的所有子節(jié)點項集的支持度都可以根據(jù)性質(zhì)6得到，無需再遍歷樹。因此，剪掉模式搜索樹中以{bdk}為根節(jié)點的子樹。

2.2 PFLFIM算法描述

PFLFIM算法主要包括四個步驟：(1) 掃描事務(wù)數(shù)據(jù)庫DB，得到頻繁1-項集F1，構(gòu)建PFC-tree。(2) 遍歷PFC-tree，得到頻繁1-項集F1對應(yīng)的PF-List。(3) 連接兩個頻繁1-項集的PF-list，得到頻繁2-項集，并使用包含索引策略節(jié)省連接時間。(4) 使用模式搜索樹代表搜索空間來挖掘頻繁k-項集，并使用提前停止交集和父子等價策略對模式搜索樹進行剪枝操作。結(jié)合前面提到的算法1和算法2，PFLFIM算法如算法3所示。

算法3PFLFIM算法

輸入: 事務(wù)數(shù)據(jù)庫DB,最小支持度minSup

輸出: 頻繁項集F

1:F←?;

2: 掃描數(shù)據(jù)庫DB,得到頻繁1-項集F1,F=F∪F1;

3: PFC-tree=BuildingPFC_Tree(DB,minSup);

4: 遍歷PFC-tree,得到F1的PF-List和包含索引subsume;

5: for eachF1中的項集{i} do

6: ifsubsume({i})≠? then

7: for eachsubsume({i})中的子集{j} do

8:F2={i}∪{j},

F2.count={i}.count,

F=F∪F2;

9: end for

10: else for eachF1中其他項集{j} do

11:F2=Intersection(PFL({i}), PFL({j}),minSup),

F=F∪F2;

12: end for

13: end if

14: end for

15: for eachF2中的項集{ixiy}(ix≤Liy) do

16: Cad_items←{i|i∈F1且ix≤Li};

17: for each Cad_items中的項ido

18:P1={ixiy},P2=P1[0]∪{i};

19: PFL(P)=Intersection(PFL(P1), PFL(P2),minSup);

20:F=F∪P;

21: end for

22: returnF;

3 實驗結(jié)果與分析

通過比較PFLFIM算法與FIN算法和negFIN算法在挖掘頻繁項集時使用的時間和占用的內(nèi)存，驗證PFLFIM算法的性能。為了保證實驗結(jié)果的公平有效，在同一臺機器上運行三種算法并比較結(jié)果，從而避免其他客觀因素帶來的性能差異。實驗在一臺內(nèi)存為8 GB，CPU為Intel(R) Core(TM) i5-2430M @ 2.40 GHz，操作系統(tǒng)為Windows 10專業(yè)版的PC上進行，所有算法均用Java語言編寫。

由于不同算法在不同特征的數(shù)據(jù)集上的表現(xiàn)差異較大，分別選擇稠密數(shù)據(jù)集Pumsb和稀疏數(shù)據(jù)集Retail來完成實驗，這兩個數(shù)據(jù)集是從頻繁模式挖掘測評比賽官方網(wǎng)站上下載的真實數(shù)據(jù)集。其中：Pumsb數(shù)據(jù)集記錄的是人口普查數(shù)據(jù)，含有大量的項目和事務(wù)，整體規(guī)模較大，即使在較高的最小支持度下也包含大量的頻繁項集；Retail數(shù)據(jù)集來源于比利時某零售店的銷售數(shù)據(jù)，是具有代表性的、十分稀疏的數(shù)據(jù)集，常用于頻繁項集挖掘的研究。兩個數(shù)據(jù)集的基本情況如表4所示。

表4 數(shù)據(jù)集及特征

在相同的數(shù)據(jù)集下，將PFLFIM算法的挖掘結(jié)果與FIN算法和negFIN算法的挖掘結(jié)果進行比較，發(fā)現(xiàn)當最小支持度相同時，3種算法挖掘出的頻繁項集的內(nèi)容和數(shù)量一致，說明使用PFLFIM算法挖掘頻繁項集是正確的。在Pumsb數(shù)據(jù)集下，三種算法挖掘出的頻繁項集的數(shù)量如表5所示。

表5 Pumsb數(shù)據(jù)集下頻繁項集數(shù)量

圖6展示了三種算法在Pumsb數(shù)據(jù)集上的運行情況，其中圖6(a)和圖6(b)分別是三種算法在運行時間和最大內(nèi)存占用上的對比。從圖6(a)中可以看出，在不同的最小支持度下，PFLFIM算法的運行速度是最快的。在最小支持度較大時，三種算法的運行時間相差不大，但是隨著最小支持度的減小，三種算法運行時間的差距被不斷拉大，當最小支持度小于55%時，可以觀察到PFLFIM算法在運行時間上的優(yōu)勢。從圖6(b)可以看出，隨著最小支持度的減少，三種算法的內(nèi)存消耗均逐漸增大，但是PFLFIM算法的內(nèi)存消耗始終小于其他兩種算法。

(a) 運行時間

(b) 最大內(nèi)存占用圖6 三種算法在Pumsb數(shù)據(jù)集上的運行情況

圖7展示了三種算法在Retail數(shù)據(jù)集上的運行情況。圖7(a)是三種算法在運行時間上的對比，從圖中可以看出三種算法在Retail數(shù)據(jù)集上的運行比較穩(wěn)定，隨著最小支持度的減小，運行時間變化不大，但是PFLFIM算法始終比其他兩種算法的運行時間少。圖7(b)是三種算法在最大內(nèi)存占用上的對比，從中可以看出隨著最小支持度的變化，三種算法的內(nèi)存消耗變化不明顯。這是因為Retail數(shù)據(jù)集十分稀疏，挖掘過程中占用的內(nèi)存本就不多，但還是可以看出，PFLFIM算法在內(nèi)存消耗上略優(yōu)于其他兩種算法。

(a) 運行時間

(b) 最大內(nèi)存占用圖7 三種算法在Retail數(shù)據(jù)集上的運行情況

由上面兩組實驗可以發(fā)現(xiàn)，PFLFIM算法在運行時間和內(nèi)存占用方面都優(yōu)于FIN算法和negFIN算法。相比于FIN算法，PFLFIM算法通過比較兩個節(jié)點的PF-List就可以判斷二者之間的祖先-后代關(guān)系，節(jié)省了多次遍歷樹查找祖先節(jié)點的時間。相比于negFIN算法，PFLFIM算法的節(jié)點信息所占的空間少，而且連接過程簡單。PFLFIM算法還使用了包含索引、提前停止交集和父子等價的優(yōu)化策略，避免產(chǎn)生大量冗余的PF-List，減少了內(nèi)存占用，加快了挖掘頻繁項集的速度。此外，Pumsb數(shù)據(jù)集是稠密的，Retail數(shù)據(jù)集是稀疏的，通過理論分析和實驗結(jié)果表明，PFLFIM算法適用于在稠密數(shù)據(jù)庫中挖掘頻繁項集，同樣也適用于稀疏數(shù)據(jù)庫。

4 PFLFIM算法在高校人才引進中應(yīng)用

將PFLFIM算法應(yīng)用于某高校人力資源管理系統(tǒng)中，對該系統(tǒng)中專任教師的基本信息、科研信息和教學(xué)信息進行規(guī)則挖掘，從中提取隱含的、有用的信息，尋找影響人才發(fā)展的因素，為高校管理者在人才引進和選拔中提供決策支持，總體挖掘流程如圖8所示。本文使用的人力資源數(shù)據(jù)取自國內(nèi)一所雙一流重點建設(shè)高校，包含了2 554名專任教師的基本信息、科研信息和教學(xué)信息，數(shù)據(jù)中隱去了工號、姓名、身份證號等個人隱私信息。

圖8 關(guān)聯(lián)規(guī)則挖掘流程

4.1 數(shù)據(jù)處理

應(yīng)用本文算法解決問題的主要目標是尋找影響人才發(fā)展的因素，所以需要整理高校教師的基本信息、科研信息和教學(xué)信息，建立人才分類模型，選取與高校人才發(fā)展可能相關(guān)的特征。數(shù)據(jù)處理主要包括數(shù)據(jù)清理、特征構(gòu)造、人才模型構(gòu)建、數(shù)據(jù)集成和數(shù)據(jù)變換五個步驟。

(1) 數(shù)據(jù)清理。由于原始數(shù)據(jù)多存在不完整性和不一致性，需要清洗掉不完整的數(shù)據(jù)，并糾正數(shù)據(jù)中的不一致性。比如，刪除剛?cè)胄２痪眯畔⒉煌晟频慕處煛Ｇ謇砗蠊灿? 622條教師數(shù)據(jù)。

(2) 特征構(gòu)造。基本信息、科研信息和教學(xué)信息中有許多特征是與挖掘任務(wù)無關(guān)的，如民族、項目經(jīng)費、授課班級等。為了去掉多余的特征，需要進行特征構(gòu)造。根據(jù)高校的實際情況，同時結(jié)合專家意見，構(gòu)造的各數(shù)據(jù)子集的特征屬性如表6所示。

表6 特征屬性

(3) 人才模型構(gòu)建。設(shè)科研信息的第i個特征屬性為Si，對應(yīng)的權(quán)重分值為wi，教學(xué)信息的第j個特征屬性為Ej，對應(yīng)的權(quán)重分值為vj，通過分析客戶細分模型和現(xiàn)有的人才模型構(gòu)建方法[13]，得到人才類型H的計算式表示為：

(5)

續(xù)表7

(4) 數(shù)據(jù)集成。將教師基本信息和人才類型利用教師編號匹配并連接在一起，形成完整的數(shù)據(jù)集，組成高校人才信息表，其中部分數(shù)據(jù)如表8所示。

表8 高校人才信息表

(5) 數(shù)據(jù)轉(zhuǎn)換。數(shù)據(jù)轉(zhuǎn)換是將數(shù)據(jù)變換為適合挖掘的形式。首先需要對數(shù)值型屬性進行離散化處理，例如采用深度等分劃法，將年齡劃分為若干個區(qū)間；對類別型屬性進行變量值歸約，例如將所屬學(xué)科歸約為“理工科和人文社科”兩類。關(guān)聯(lián)規(guī)則挖掘中各屬性值均為布爾類型，因此需要將各個屬性值轉(zhuǎn)化為布爾量，部分屬性的轉(zhuǎn)化如表9所示。

表9 屬性轉(zhuǎn)化表

利用屬性轉(zhuǎn)化表將原始數(shù)據(jù)庫轉(zhuǎn)換成布爾型的事務(wù)數(shù)據(jù)庫，如表10所示。

表10 事務(wù)數(shù)據(jù)庫

4.2 關(guān)聯(lián)規(guī)則挖掘

使用上文處理后的數(shù)據(jù)進行實驗，將PFLFIM算法與FIN算法和negFIN算法進行比較，發(fā)現(xiàn)當最小支持度相同時，挖掘出的頻繁項集的內(nèi)容和數(shù)量相同。三種算法在不同最小支持度下挖掘頻繁項集的運行時間如圖9所示。可以看出，隨著支持度的變化，PFLFIM算法的運行時間始終較其他兩種算法少，說明PFLFIM算法適用于該數(shù)據(jù)集，且挖掘速度較快。

圖9 三種算法在高校人才數(shù)據(jù)集上的運行時間

應(yīng)用PFLFIM算法對轉(zhuǎn)換后的高校人才信息進行關(guān)聯(lián)規(guī)則挖掘，找出支持度不小于最小支持度且置信度不小于最小置信度的強關(guān)聯(lián)規(guī)則。設(shè)最小支持度為10%，最小置信度為70%，去掉結(jié)果中互相包含且無意義的規(guī)則，只保留與挖掘目標相符合的、置信度較高的且對決策有參考價值的規(guī)則，最后得到的結(jié)果如表11所示。

表11 關(guān)聯(lián)規(guī)則挖掘結(jié)果

續(xù)表11

4.3 規(guī)則分析

分析表11中的規(guī)則可以得到下述信息：

(1) 高學(xué)歷高職稱且在校期間有過職稱變動的教師，多為教學(xué)科研型人才。在人才引進時，多注意引進高學(xué)歷高職稱的人才，一方面能夠在一定程度上優(yōu)化人才隊伍，另一方面能夠有效地帶動高校發(fā)展。

(2) 有重點高校學(xué)習經(jīng)歷的理工科教師，更容易向科研型人才發(fā)展。在引進科研崗位的人才時，應(yīng)優(yōu)先考慮畢業(yè)于名校的博士研究生，這樣不但可以在一定程度上改善高校教師的學(xué)歷結(jié)構(gòu)，還能促進高校科研水平的提升。

(3) 男性教師偏向于向科研型人才發(fā)展，女性教師偏向于向教學(xué)型人才發(fā)展，說明高校教師在發(fā)展上存在一定的性別差異。因此在人才引進時，應(yīng)充分考慮人才的性別差異，為其制定合適的發(fā)展道路。

(4) 校齡小于5年、學(xué)歷一般且無職稱變動的教師，教學(xué)和科研能力不太突出，這與他們來校不久有很大關(guān)系。但是這類人員大多有較大的發(fā)展?jié)摿Γ咝９芾碚邞?yīng)多關(guān)注這類教師的工作，制定適合他們的培養(yǎng)機制，幫助他們迅速成長起來。在人才引進時也應(yīng)多關(guān)注這類有潛力的人員，為高校的發(fā)展注入新鮮力量。

通過分析以上信息發(fā)現(xiàn)，挖掘得出的規(guī)則與現(xiàn)實情況基本符合，一些沒有預(yù)料的結(jié)果也客觀反映了實際情況。通過分析挖掘出來的規(guī)則，發(fā)現(xiàn)了影響人才發(fā)展的因素，為高校人才引進和選拔提供了策略，也為高校管理者制定決策提供了科學(xué)依據(jù)。

5 結(jié) 語

本文通過對FP-growth類算法進行研究，提出了一種基于PF-List的頻繁項集挖掘算法(PFLFIM)。該算法主要有以下優(yōu)勢：(1) 使用PF-List表示項集，通過簡單比較兩個項集的PF-List就可以直接連接得到頻繁項集，降低了算法的時間復(fù)雜度。(2) 使用包含索引、提前停止交集和父子等價策略對搜索空間進行優(yōu)化，減少了內(nèi)存占用。將PFLFIM算法與FIN算法和negFIN算法結(jié)合實驗進行比較，結(jié)果表明PFLFIM算法在挖掘時間和內(nèi)存占用上均有較高的效率。將該算法應(yīng)用于對某高校專任教師的基本信息和人才類型進行關(guān)聯(lián)規(guī)則挖掘上，從中提取潛在的有價值的信息，發(fā)現(xiàn)影響人才發(fā)展的因素，并且為高校人才引進和選拔提供科學(xué)依據(jù)，從而促進高校的全面發(fā)展，提高高校的競爭力。