吳文波，吳昌錢，胡 永

(1. 閩南科技學(xué)院計(jì)算機(jī)信息學(xué)院，福建 泉州 362000；2. 西藏民族大學(xué)信息工程學(xué)院，陜西 咸陽 712082)

1 引言

當(dāng)下隨著信息時(shí)代的深入發(fā)展，導(dǎo)致各類數(shù)據(jù)急劇增長(zhǎng)，同時(shí)數(shù)據(jù)結(jié)構(gòu)類型也逐漸繁多，海量的多源異構(gòu)數(shù)據(jù)集存在于多領(lǐng)域中；該類數(shù)據(jù)集的特性，導(dǎo)致數(shù)據(jù)的可利用率較低[1]。為實(shí)現(xiàn)該類數(shù)據(jù)集中的數(shù)據(jù)的有效利用，對(duì)其進(jìn)行智能挖掘是主要手段?；诖?，本文依據(jù)隨機(jī)森林理念，提出基于隨機(jī)森林的頻繁項(xiàng)集智能挖掘算法，對(duì)該類數(shù)據(jù)集進(jìn)行挖掘分類，實(shí)現(xiàn)數(shù)據(jù)集的充分利用。

頻繁項(xiàng)集指的是數(shù)據(jù)集中出現(xiàn)頻率較高的相關(guān)變量，可通過對(duì)該項(xiàng)集的挖掘得出，挖掘結(jié)果可作為目標(biāo)處理的依據(jù)[2]。數(shù)據(jù)分類作為數(shù)據(jù)挖掘的重要步驟或者目標(biāo)，對(duì)于數(shù)據(jù)處理和應(yīng)用具有重要意義。隨機(jī)森林是一種通過分類器完成數(shù)據(jù)挖掘分類的模型，數(shù)個(gè)FP-tree樹是其實(shí)現(xiàn)挖掘目的的依據(jù)，同時(shí)參與模型訓(xùn)練，且模型輸出類別需以其類別為依據(jù)[3]。因此，模型性能的優(yōu)劣，與各個(gè)FP-tree樹的性能優(yōu)劣存在直接且較大關(guān)聯(lián)。該算法的運(yùn)算依據(jù)是統(tǒng)計(jì)學(xué)理論，充分結(jié)合引導(dǎo)聚集和隨機(jī)子空間兩種算法，通過樣本抽取和FP-tree樹建模，形成多顆FP-tree樹，最終結(jié)果的輸出需依據(jù)投票完成[4]。

2 基于隨機(jī)森林的頻繁項(xiàng)集智能挖掘算法

2.1 基于改進(jìn)FP-tree的頻繁項(xiàng)集挖掘算法

2.1.1 頻繁項(xiàng)集

以數(shù)據(jù)頻繁項(xiàng)集為出發(fā)點(diǎn)，設(shè)計(jì)基分類器，其與各個(gè)類別相對(duì)應(yīng)，并在該設(shè)計(jì)過程中，需確定優(yōu)先類別，該過程為隨機(jī)選擇。分類器的差異導(dǎo)致其針對(duì)的數(shù)據(jù)類別存在差異，同時(shí)，使形成的FP-tree樹結(jié)構(gòu)也存在差異，以此保證基分類器的多樣性[5]。由于隨機(jī)森林算法是通過構(gòu)建FP-tree樹完成算法運(yùn)行，F(xiàn)P-tree樹則是完成頻繁項(xiàng)集挖掘的典型算法。

如果項(xiàng)集合用I={i1，i2，…，in}表示，事物的集合用D表示，其屬于數(shù)據(jù)庫(kù)；項(xiàng)集合則構(gòu)成各個(gè)事物T，且保證T∈I，以所有的T∈I為參照，僅在該條件下，T中包含項(xiàng)集X。X在D中的事物數(shù)量用于表示計(jì)數(shù)，且屬于X的支持度。X在D中的事物比例用于表示X的支持度，當(dāng)n表示T的數(shù)量，且屬于D，則X/n獲取的百分比即為X的支持度。在任意個(gè)給定的支持度小于X的支持度時(shí)，X即為頻繁項(xiàng)集，此時(shí)給定的支持度為最小。

頻繁模式樹也稱為FP-tree樹，由3個(gè)域可構(gòu)成其中的一個(gè)節(jié)點(diǎn)，分別為項(xiàng)名item、支持度計(jì)數(shù)sup-count和鏈node-link，后兩者均屬于節(jié)點(diǎn)。為保證遍歷的便捷性，完成項(xiàng)頭表的建構(gòu)，其用Header-tabie表示，其中包含2個(gè)域，分別為項(xiàng)名item、鏈頭head of node-link。

FP-tree的構(gòu)建主要依據(jù)FP-growth算法完成，需對(duì)數(shù)據(jù)集進(jìn)行掃描，且次數(shù)為2次，每一次掃描的內(nèi)容分別如下：

1)為形成全部頻繁1-項(xiàng)集及其支持度，對(duì)D進(jìn)行掃描得出，按照獲取的結(jié)果由高至低順序，向Header-tabie中插入。

2)完成根節(jié)點(diǎn)null的構(gòu)建，且屬于T，采取手段對(duì)D中的各個(gè)T進(jìn)行處理，分別為：第一，對(duì)項(xiàng)頭表執(zhí)行第一次掃描，獲取其中的頻繁項(xiàng)集，且掃描標(biāo)準(zhǔn)為按照順序完成[6]；[p|P]表示排列后的結(jié)果，其中兩個(gè)參數(shù)均表示項(xiàng)目，前者對(duì)應(yīng)第一個(gè)，后者對(duì)應(yīng)剩余的。第二，使用insert-tree[p|P]，當(dāng)子女N存在于T中時(shí)，則N.item=p，同時(shí)N的數(shù)量加1；反之，需創(chuàng)建新節(jié)點(diǎn)，其名稱用p表示，sup-count則設(shè)為1，確定其父節(jié)點(diǎn)，并進(jìn)行鏈接，相同的項(xiàng)名節(jié)點(diǎn)可利用node-link完成鏈接，在p不是空的情況下，采用insert-tree[p|P]完成遞歸。

2.1.2 基于FP-數(shù)組技術(shù)的頻繁項(xiàng)集挖掘算法

由于T具備base、header和FP-數(shù)組三種屬性，因此，采用T作為程序的參數(shù)，T在三種屬性下，分別包含X、項(xiàng)頭表以及FP-數(shù)組Ax。該算法對(duì)頻繁項(xiàng)集進(jìn)行挖掘的詳細(xì)步驟如下所述：

輸入：FP-array

輸出：屬于T中的全部頻繁項(xiàng)集

1)if T′ only contains a single branch B

2)for each subset y of the set of items in B

3)output itemset Y∪Tbase with count-min-count of nodes in Y；

4)else for each i in T header do begin

5)output Y=T base ∪{i}with i count；

6)if T FP-array is define

7)construct a new header table foe Y′s FP-tree fromT FP-array ；

8)else construct a new header table from T；

9)construct Y′s conditional FP-tree Ty and possibly its FP-arry AY；

10)ifTY≠φ

11)call FP-growth+(TY)；

12)end

樣本x在測(cè)試階段的預(yù)測(cè)通過產(chǎn)生的FP-tree樹完成，且數(shù)量為L(zhǎng)，在隨機(jī)森林算法中，一顆FP-tree樹可完成一個(gè)結(jié)果挖掘，基于此，可得出L個(gè)挖掘結(jié)果，為T1(x)，T2(x)，….，TL(x)；x的最終頻繁項(xiàng)集類別標(biāo)簽為y，該結(jié)果的獲取通過投票的方式完成，其計(jì)算公式為

(1)

式中：指示函數(shù)用I(·)表示；在Ti(x)=ωj的情況下，I(Ti(x)=ωj)結(jié)果為1，反之其結(jié)果為0。

通過上述步驟，獲取最終的頻繁項(xiàng)集輸出結(jié)果，其類別判斷標(biāo)準(zhǔn)為得出的投票數(shù)量的高低，票數(shù)多的作為頻繁項(xiàng)集類的確定結(jié)果。

2.2 基于優(yōu)化隨機(jī)森林算法的頻繁項(xiàng)集分類

由于隨機(jī)森林算法需要構(gòu)建大量FP-tree樹，因此會(huì)導(dǎo)致內(nèi)存被大量占用；同時(shí)，該算法結(jié)合引導(dǎo)聚集和隨機(jī)子空間兩種算法，兩者均會(huì)對(duì)分類精度和多樣性造成影響[7]。因此，為保證算法分類精度對(duì)隨機(jī)森林算法進(jìn)行改進(jìn)，主要從兩個(gè)方面完成，一是獲取精度較高的部分FP-tree樹，且由隨機(jī)森林形成；二是對(duì)選取出的FP-tree樹進(jìn)行聚類，且樹的選取標(biāo)準(zhǔn)為精度較高、相對(duì)程度較低[8]。改進(jìn)后的隨機(jī)森林算法流程見圖1。

圖1 改進(jìn)后的算法流程

2.2.1 高精度子森林選取

(2)

式中：A表示AUC的平均值，屬于森林中全部FP-tree樹；如果F的數(shù)量低于SubF數(shù)量的三分之一，則待聚類子森林為SubF，反之需要將選取標(biāo)準(zhǔn)降低。σ表示AUC值的標(biāo)準(zhǔn)差，屬于森林中全部FP-tree樹，獲取該值后，完成子森林構(gòu)成，其由FP-tree樹組成[10]，且AUC≥A-σ。組成的子森林公式為

(3)

依據(jù)上述內(nèi)容，完成待聚類子森林的構(gòu)成，其過程如下所述：

輸入：訓(xùn)練集和測(cè)試集

輸出：高精度子森林

1)抽取訓(xùn)練子集，且數(shù)量為K，從訓(xùn)練集D中抽取得出。

2)基分類器的訓(xùn)練，采用FP-tree樹生成算法完成，其屬于各個(gè)訓(xùn)練子集中。

3)為獲取AUC的值，輸入待測(cè)樣本，完成所有FP-tree樹的分類。

4)對(duì)獲取的A和σ進(jìn)行統(tǒng)計(jì)，以AUC≥A-σ或者AUC≥A作為標(biāo)準(zhǔn)，選取FP-tree樹，形成SubF。

2.2.2 聚類選擇多樣性子森林

通過2.2.1小節(jié)獲取SubF后，對(duì)其進(jìn)行聚類，獲取數(shù)據(jù)點(diǎn)，為相同測(cè)試點(diǎn)上的多顆FP-tree樹分類結(jié)果。P表示數(shù)量，屬于FP-tree樹，為SubF中，因此可獲取的待聚類樣本數(shù)量也用P表示。

對(duì)聚類后的簇進(jìn)行劃分，使其形成數(shù)個(gè)類簇，相似度較低、精度較高的隨機(jī)森林的組成是由其中典型的樹完成，其步驟如下所述：

輸入：聚類數(shù)量Q

輸出：改進(jìn)的隨機(jī)森林模型

1)選取SubF作為數(shù)據(jù)集，獲取其中的初始聚類中心，數(shù)量為Q。

2)完成所有數(shù)據(jù)遍歷，計(jì)算距離，其屬于對(duì)各個(gè)數(shù)據(jù)至聚類中心兩者之間；并對(duì)數(shù)據(jù)屬性進(jìn)行劃分處理，將距離中心簇的距離遠(yuǎn)近作為劃分依據(jù)。

3)對(duì)各個(gè)聚類中心進(jìn)行重復(fù)計(jì)算。

4)重復(fù)上述兩個(gè)步驟，當(dāng)滿足最大迭代次數(shù)為止。

5)隨機(jī)森林的組成由分類精度高的FP-tree樹完成，該FP-tree樹屬于Q中。

為避免Q的選擇對(duì)聚類結(jié)果造成影響，聚類中心的選擇通過最大最小距離完成，詳細(xì)步驟如下所述：

1)聚類中心z1為平均多樣性最佳的FP-tree樹，該多樣性即可表示平均值，屬于森林中全部樹，其計(jì)算公式為

(4)

(5)

2)z2表示第二個(gè)聚類中心，其確定標(biāo)準(zhǔn)為距離z1最近。

3)獲取距離，屬于剩余的樣本和已經(jīng)確定的全部聚類中心，確定其中的最小距離。

4)選取最大距離，新增的聚類中心為與其對(duì)應(yīng)的樣本。

5)重復(fù)上述兩個(gè)步驟，停止條件為獲取聚類中心，且數(shù)量為Q。

6)完成聚類中心計(jì)算后，向相應(yīng)的類別中劃分樣本集，屬于聚類中心，且以最小距離為劃分標(biāo)準(zhǔn)。

綜上所述，完成算法優(yōu)化，使算法在構(gòu)建大量FP-tree樹進(jìn)行挖掘時(shí)性能得到提升，完成數(shù)據(jù)集中頻繁項(xiàng)智能挖掘和數(shù)據(jù)分類。

3 測(cè)試分析

選取某機(jī)器學(xué)習(xí)數(shù)據(jù)庫(kù)中的4個(gè)數(shù)據(jù)集，作為測(cè)試本文方法應(yīng)用性能和應(yīng)用效果的測(cè)試對(duì)象，數(shù)據(jù)集信息詳情見表1。

表1 測(cè)試對(duì)象數(shù)據(jù)信息

在進(jìn)行測(cè)試時(shí)，測(cè)試環(huán)境為：64位Windows10操作系統(tǒng)，Intel(R) Core(TM) i7-7700HQ，CPU 3.09GHz，安裝內(nèi)存為16GB。構(gòu)建初始隨機(jī)森林，數(shù)量和深度分別為100顆和10。依據(jù)文中方法步驟得出預(yù)測(cè)結(jié)果。在此基礎(chǔ)上，生成隨機(jī)森林，其標(biāo)準(zhǔn)為精度較高、相似程度較低。選取測(cè)試集，將其用于測(cè)試改進(jìn)前后算法的性能，測(cè)試結(jié)果通過分類評(píng)估指標(biāo)完成對(duì)比分析。本文采用的評(píng)估指標(biāo)為Kappa系數(shù)，該指標(biāo)計(jì)算公式為

(6)

式中：P1和P2均表示概率，屬于兩個(gè)分類器，前者表示兩者獲取結(jié)果一致，后者表示兩者偶然相同。其中

(7)

(8)

式中：mk，s表示概率，位于ωk和ωs類中，且由Ti和Tj劃分完成。該系數(shù)的取值為[-1，1]，值越大，說明一致性越佳，測(cè)試指標(biāo)用于評(píng)估本文方法挖掘結(jié)果與實(shí)際結(jié)果的一致性程度。

算法在運(yùn)算過程中，生成的FP-tree樹數(shù)量L和類別數(shù)量K對(duì)于算法的運(yùn)算存在直接關(guān)聯(lián)，因此需確定最佳的兩者取值，測(cè)試在不同L和K數(shù)量下，本文算法的挖掘AUC值和預(yù)測(cè)準(zhǔn)確率，結(jié)果見圖2。AUC值越高，表示算法真實(shí)性越高，其取值范圍[0.5，1]。

圖2 最佳取值測(cè)試結(jié)果

分析圖2測(cè)試結(jié)果可得：FP-tree樹數(shù)量的增加，AUC值隨之變化，呈現(xiàn)上升、下降、上升的循環(huán)狀態(tài)，當(dāng)FP-tree樹數(shù)量達(dá)到60時(shí)，AUC值最佳，為0.984；并且類別數(shù)量為30個(gè)時(shí)，預(yù)測(cè)準(zhǔn)確率最佳，0.977。因此為保證算法的最佳效果和性能，L和K的取值分別為0.984和0.977。

為測(cè)試本文算法對(duì)于多樣性子森林的聚類效果，測(cè)試本文算法在差異化最佳聚類數(shù)量時(shí)，算法每次獲取的子森林集成準(zhǔn)確率，結(jié)果見圖3。為了最大程度保證測(cè)試結(jié)果的可靠性，測(cè)試結(jié)果為5次結(jié)果的平均值。

圖3 聚類準(zhǔn)確率測(cè)試結(jié)果

分析圖3測(cè)試結(jié)果可知：聚類數(shù)量越多，聚類正確率則隨之提升，但是當(dāng)其達(dá)到飽和后，則不再上升，聚類數(shù)量為30個(gè)時(shí)，聚類正確率達(dá)到99.1%，聚類數(shù)量繼續(xù)增加至35后，聚類正確率平穩(wěn)，不再發(fā)生變化。

頻繁項(xiàng)集的挖掘效果是體現(xiàn)算法應(yīng)用性能的直觀標(biāo)準(zhǔn)，將4種數(shù)據(jù)集中的屬性數(shù)量和頻繁項(xiàng)集數(shù)量分別作為挖掘目標(biāo)，用于進(jìn)一步衡量本文算法的挖掘效果。測(cè)試本文算法對(duì)4個(gè)數(shù)據(jù)集中的屬性數(shù)量和頻繁項(xiàng)集數(shù)量分別進(jìn)行挖掘，獲取挖掘結(jié)果，以此分析本文算法的挖掘效果，結(jié)果見圖4。

圖4 挖掘測(cè)試結(jié)果

根據(jù)圖4測(cè)試結(jié)果可知：本文算法在對(duì)四種數(shù)據(jù)集進(jìn)行挖掘后，可較為準(zhǔn)確完成數(shù)據(jù)集中頻繁項(xiàng)集數(shù)量以及屬性數(shù)量的挖掘，其中只有在挖掘數(shù)據(jù)集2中的屬性數(shù)量挖掘時(shí)，挖掘結(jié)果與實(shí)際結(jié)果存在一個(gè)數(shù)量的差異，其它數(shù)據(jù)集的頻繁項(xiàng)集數(shù)量以及屬性數(shù)量挖掘結(jié)果均與實(shí)際結(jié)果相同，可在整體挖掘誤差較低的情況下完成數(shù)據(jù)集挖掘。

4 結(jié)論

數(shù)據(jù)的信息化發(fā)展，促使數(shù)據(jù)的應(yīng)用需求極大增加，也導(dǎo)致對(duì)于各類數(shù)據(jù)的處理需求顯著增加，頻繁項(xiàng)集作為數(shù)據(jù)集中可體現(xiàn)數(shù)據(jù)中變量情況的一種項(xiàng)集，其對(duì)于數(shù)據(jù)的處理和應(yīng)用具有重要作用。頻繁項(xiàng)集的準(zhǔn)確、有效挖掘，可使數(shù)據(jù)集中的各類數(shù)據(jù)利用率極大程度提升，但是頻繁項(xiàng)集的智能挖掘一直面臨諸多問題。本文以隨機(jī)森林理論為依據(jù)，對(duì)其進(jìn)行改進(jìn)，提升數(shù)據(jù)集中頻繁項(xiàng)集的挖掘效果，研究基于隨機(jī)森林的頻繁項(xiàng)集智能挖掘算法。通過測(cè)試表明：本文算法改進(jìn)后具備良好的挖掘性能，挖掘正確率越高，可在極低的誤差下完成數(shù)據(jù)集中的頻繁項(xiàng)集挖掘。