多源異構數(shù)據(jù)集下的改進挖掘算法設計

吳文波，吳昌錢，胡 永

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

1 引言

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

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

2 基于隨機森林的頻繁項集智能挖掘算法

2.1 基于改進FP-tree的頻繁項集挖掘算法

2.1.1 頻繁項集

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

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

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

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

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

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

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

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

輸入：FP-array

輸出：屬于T中的全部頻繁項集

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在測試階段的預測通過產生的FP-tree樹完成，且數(shù)量為L，在隨機森林算法中，一顆FP-tree樹可完成一個結果挖掘，基于此，可得出L個挖掘結果，為T1(x)，T2(x)，….，TL(x)；x的最終頻繁項集類別標簽為y，該結果的獲取通過投票的方式完成，其計算公式為

(1)

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

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

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

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

圖1 改進后的算法流程

2.2.1 高精度子森林選取

(2)

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

(3)

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

輸入：訓練集和測試集

輸出：高精度子森林

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

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

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

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

2.2.2 聚類選擇多樣性子森林

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

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

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

輸出：改進的隨機森林模型

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

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

3)對各個聚類中心進行重復計算。

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

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

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

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

(4)

(5)

2)z2表示第二個聚類中心，其確定標準為距離z1最近。

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

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

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

6)完成聚類中心計算后，向相應的類別中劃分樣本集，屬于聚類中心，且以最小距離為劃分標準。

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

3 測試分析

選取某機器學習數(shù)據(jù)庫中的4個數(shù)據(jù)集，作為測試本文方法應用性能和應用效果的測試對象，數(shù)據(jù)集信息詳情見表1。

表1 測試對象數(shù)據(jù)信息

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

(6)

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

(7)

(8)

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

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

圖2 最佳取值測試結果

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

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

圖3 聚類準確率測試結果

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

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

圖4 挖掘測試結果

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

4 結論

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