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

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

0 引 言

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

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

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

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

1 相關(guān)概念

1.1 基本概念

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

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

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

(1)

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

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

表2 1-項(xiàng)集及其支持度計(jì)數(shù)

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

(2)

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

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

1.2 PFC-tree

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

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

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

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

輸出:頻繁1-項(xiàng)集F1,PFC-tree

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

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

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

4: 初始化finish=0;

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

6: 創(chuàng)建節(jié)點(diǎn)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,得到每個(gè)節(jié)點(diǎn)的前序編號(hào)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-項(xiàng)集的PF-List，為了定義PF-List，首先給出PFC-tree中每個(gè)節(jié)點(diǎn)信息的定義。

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

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

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

圖2 頻繁1-項(xiàng)集的PF-List

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

定義6假設(shè)一個(gè)2-項(xiàng)集{ij}，其中項(xiàng)集{i}的支持度大于項(xiàng)集{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-項(xiàng)集{ij}的PF-List。

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

(2) 檢查項(xiàng)集{ij}的PF-List，把前序編號(hào)相同的節(jié)點(diǎn)的count相加，合并為一個(gè)節(jié)點(diǎn)。

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

定義7頻繁k-項(xiàng)集的PF-List是通過連接兩個(gè)頻繁(k-1)-項(xiàng)集的PF-List得到的。設(shè)頻繁(k-1)-項(xiàng)集I1={ixi1i2…ik-2},I2={iyi1i2…ik-2},其中項(xiàng)集{ix}的支持度大于項(xiàng)集{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-項(xiàng)集I=I1∪I2={ixiyi1i2…ik-2}。

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

圖3 1-項(xiàng)集的PF-List連接

圖4 k-項(xiàng)集的PF-List連接

2 基于PF-List的頻繁項(xiàng)集挖掘算法

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

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

2.1.1模式搜索樹

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

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

2.1.2優(yōu)化策略

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

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

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

Nj是Ni的祖先}

(3)

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

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

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

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

(4)

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

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

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

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

(3) 若C1

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

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

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

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

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

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

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

5: for each PFL(I2)中的節(jié)點(diǎn)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父子等價(jià)剪枝策略[12]。給定項(xiàng)集F和項(xiàng)i，且i?F。如果F的支持度等于F∪{i}的支持度，即support(F)=support(F∪{i})。則對于任意項(xiàng)集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}，一個(gè)包含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})。證畢。

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

2.2 PFLFIM算法描述

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

算法3PFLFIM算法

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

輸出: 頻繁項(xiàng)集F

1:F←?;

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

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

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

5: for eachF1中的項(xiàng)集{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中其他項(xiàng)集{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中的項(xiàng)集{ixiy}(ix≤Liy) do

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

17: for each Cad_items中的項(xiàng)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 實(shí)驗(yàn)結(jié)果與分析

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

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

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

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

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

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

(a) 運(yùn)行時(shí)間

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

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

(a) 運(yùn)行時(shí)間

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

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

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

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

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

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

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

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

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

表6 特征屬性

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

(5)

續(xù)表7

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

表8 高校人才信息表

(5) 數(shù)據(jù)轉(zhuǎn)換。數(shù)據(jù)轉(zhuǎn)換是將數(shù)據(jù)變換為適合挖掘的形式。首先需要對數(shù)值型屬性進(jìn)行離散化處理，例如采用深度等分劃法，將年齡劃分為若干個(gè)區(qū)間；對類別型屬性進(jìn)行變量值歸約，例如將所屬學(xué)科歸約為“理工科和人文社科”兩類。關(guān)聯(lián)規(guī)則挖掘中各屬性值均為布爾類型，因此需要將各個(gè)屬性值轉(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ù)進(jìn)行實(shí)驗(yàn)，將PFLFIM算法與FIN算法和negFIN算法進(jìn)行比較，發(fā)現(xiàn)當(dāng)最小支持度相同時(shí)，挖掘出的頻繁項(xiàng)集的內(nèi)容和數(shù)量相同。三種算法在不同最小支持度下挖掘頻繁項(xiàng)集的運(yùn)行時(shí)間如圖9所示。可以看出，隨著支持度的變化，PFLFIM算法的運(yùn)行時(shí)間始終較其他兩種算法少，說明PFLFIM算法適用于該數(shù)據(jù)集，且挖掘速度較快。

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

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

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

續(xù)表11

4.3 規(guī)則分析

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

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

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

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

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

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

5 結(jié) 語

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