改進的頻繁項集挖掘算法及其應用研究

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

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

0 引 言

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

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

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

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

1 相關概念

1.1 基本概念

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

表1 事務數據庫DB

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

(1)

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

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

表2 1-項集及其支持度計數

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

(2)

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

性質1對于給定的事務數據庫DB，設定最小支持度和最小置信度，關聯規則挖掘是指查找數據庫中支持度不小于最小支持度且置信度不小于最小置信度的所有強關聯規則。

1.2 PFC-tree

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

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

算法1構建PFC-tree

輸入:事務數據庫DB,最小支持度minSup

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

1: 掃描數據庫DB,得到頻繁1-項集F1;

2: 根據F1處理數據庫中的事務;

3: 創建根節點Node,Node.item-name←root,parent←Node;

4: 初始化finish=0;

5: for each事務中的項i do

6: 創建節點N,parent.child-list←N,

N.item-name←i,

N.count←包含i的事務數;

N.finishbuilding-order←++finish;

parent←N;

7: end for

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

9: returnF1,Node;

根據算法1，構建表1所示數據庫的PFC-tree，如圖1所示。

圖1 事務數據庫對應的PFC-tree

1.3 PF-List的概念與性質

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

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

性質2給定PFC-tree中的兩個節點N1和N2，N1和N2的前序編號和完全構造編號分別為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所示。例如，項集的PF-List，PFL()={<(1,7):4>}。

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

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

定義6假設一個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>}，根據以下規則生成2-項集{ij}的PF-List。

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

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

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

定義7頻繁k-項集的PF-List是通過連接兩個頻繁(k-1)-項集的PF-List得到的。設頻繁(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>}，根據定義6中的規則生成頻繁k-項集I=I1∪I2={ixiyi1i2…ik-2}。

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

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

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

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

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

2.1 頻繁項集挖掘

2.1.1模式搜索樹

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

圖5 數據庫DB的模式搜索樹

2.1.2優化策略

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

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

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

Nj是Ni的祖先}

(3)

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

表3 1-項集和對應的包含索引

性質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，根據性質4可知，support({dk})=support({k})=3。在挖掘頻繁項集時，使用包含索引策略，可以直接得到一些頻繁項集及其支持度，節省了執行連接操作的時間，提高了算法的運行速度。

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

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

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

(3) 若C1

根據性質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)中的節點Nxdo

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

6: ifNx與Ny不存在祖先-后代關系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);

性質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})。

證明：設I1=L∪F，I2=L∪F∪{i}，一個包含I1但不包含I2的事務T，由于i∈I2但i?I1，因此i?T。由于support(F)=support(F∪{i})，說明如果事務包含F的話，則肯定包含{i}。由于事務T包含I1且I1=L∪F，說明事務T包含F，則事務T包含{i}，即i∈T，與上面矛盾。因此如果事務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}的支持度計數等于項集{bdk}的支持度計數，即support({bk})=support({bdk})。那么模式搜索樹中，代表項集{bdk}節點的所有子節點項集的支持度都可以根據性質6得到，無需再遍歷樹。因此，剪掉模式搜索樹中以{bdk}為根節點的子樹。

2.2 PFLFIM算法描述

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

算法3PFLFIM算法

輸入: 事務數據庫DB,最小支持度minSup

輸出: 頻繁項集F

1:F←?;

2: 掃描數據庫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 實驗結果與分析

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

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

表4 數據集及特征

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

表5 Pumsb數據集下頻繁項集數量

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

(a) 運行時間

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

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

(a) 運行時間

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

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

4 PFLFIM算法在高校人才引進中應用

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

圖8 關聯規則挖掘流程

4.1 數據處理

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

(1) 數據清理。由于原始數據多存在不完整性和不一致性，需要清洗掉不完整的數據，并糾正數據中的不一致性。比如，刪除剛入校不久信息不完善的教師。清理后共有1 622條教師數據。

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

表6 特征屬性

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

(5)

續表7

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

表8 高校人才信息表

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

表9 屬性轉化表

利用屬性轉化表將原始數據庫轉換成布爾型的事務數據庫，如表10所示。

表10 事務數據庫

4.2 關聯規則挖掘

使用上文處理后的數據進行實驗，將PFLFIM算法與FIN算法和negFIN算法進行比較，發現當最小支持度相同時，挖掘出的頻繁項集的內容和數量相同。三種算法在不同最小支持度下挖掘頻繁項集的運行時間如圖9所示?？梢钥闯?，隨著支持度的變化，PFLFIM算法的運行時間始終較其他兩種算法少，說明PFLFIM算法適用于該數據集，且挖掘速度較快。

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

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

表11 關聯規則挖掘結果

續表11

4.3 規則分析

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

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

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

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

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

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

5 結 語

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