基于層次頻繁模式樹的數據自動挖掘算法

王景蘭, 方 曉

(亳州職業技術學院 信息工程系, 安徽 亳州 236800)

近些年,隨著信息網絡的迅速發展,數據挖掘技術得到了廣泛關注[1-2],主要是由于大量的數據被轉換為有用的信息和知識,能夠在獲取過程中應用于多種類型的產業結構[3-4]。隨著數據庫的成熟發展,人類日積月累產生的數據信息越來越復雜,在不同產業內部形成了超過數百萬條的信息記錄[5-6],需要對其進行更深層次的分析才能被有效利用。但由于數據庫系統只能完成錄入和查詢功能,在數據存在的相關聯系中,無法根據現有數據進行未來預測,不能實現現有數據的隱藏功效,導致數據繁多且知識貧乏的局面[7]。如何在海量數據中有效提出對應知識點,成為目前最需要解決的問題之一。數據挖掘的任務主要是從信息中發現關聯模式,以此判斷選項集合中的規則,為不同產業提供預知行為可能性[8-9]。

其中頻繁模式樹能從數據的底部進行挖掘,從下至上依次對關聯節點進行支持度分類,根據數據的首尾相接模式,減少不必要的數據搜索,可在有限時間內提高挖掘效率[10]。本文以此為基礎,研究層次頻繁模式樹的數據自動挖掘算法,為最大限度地保留信息完整度,提高算法運行效率提供理論支持。

1 基于層次頻繁模式樹定義挖掘任務

頻繁模式樹是指在數據庫的信息集合中,將原來龐大的事務數據壓縮儲存為“一棵樹”,在其內部可以包含多個類型的數據挖掘信息,根據不同密度將數據分為幾個小的事務數據集合,通過其相似度定義挖掘任務。在每個小事務數據集合中,包含有相鄰選項相似度最高的數據,根據層次分析方法將相鄰的數據依次劃分,直到小事務數據集合之間的頻繁項相似度降為零[11-12]。

由于算法實現以層次分類頻繁模式樹為依據,故在算法進行之前需要生成層次頻繁模式樹,生成過程如下:

(1) 對模式樹T進行一次掃描,將支持度滿足最小支持度閾值的頻繁1項集按降序生成頭表H—List。

(2) 將分類標簽按字母順序排序在特征屬性的后面,形成三元組順序表TS—List,表中的每個元素由特征項或類別項、層次號兩部分組成。

(3) 對事務數據庫進行一次投影操作,將原始項集中不在H—List的項刪除。

(4) 對于每一個事務Ti,根據處理后的項集,結合項在TS—List的層次關系生成層次頻繁模式樹(HCFP—Tree)。HCFP—Tree生成時,相同層次的特征節點可以共享路徑、類別節點。

(5) 生成標頭Header表,表中指針指向對應的類標簽節點。

當數據集合不存在相似度后可以對任意集合進行關聯,首先根據每個事務集合中,最高支持度的數據選項進行初次歸類,以具有相同數據最多的集合作為第1個事務集合的合并,利用支持度對余下的非最高相同事務進行篩選查詢,其他數據選項是否都屬于此類事務集合的任務目標,這樣這些事務任務就構成了一個新的集合[13-14],以此類推直到所有事物集合重新完成任務分類。為減少集合的分類負荷,在每個頻繁出入的集合中進行原生數據的任務處理,保證在同一個任務集合分塊中的頻繁項相似度較高,不同集合分塊中的相似度要接近于零[15]。在定義完成數據挖掘任務后,根據關聯規則對應建立數據矩陣,以保證自動挖掘算法的順利完成。

2 建立數據自動連接矩陣

根據層次頻繁模式樹給出的挖掘任務,對需要整合的數據進行權重分析,以此建立相對應的連接矩陣,根據層次分析法的權重生成模式,對變量數據進行離散。以每組連續數據的取值范圍[0,1]作為單次節點出入項,確定不同任務層級的連接權重,每個層級的數據個數設置為g,數據向量的輸入矩陣表示為

式中:S為輸入向量的連接權重,在輸入樣本向量中設置f×g的矩陣類型,f為輸入數據的記錄數值。

根據連接權重的數據分別設置相鄰數據向量的期望值,利用隱藏函數作為反復迭代的補充,計算其輸出向量,表達式為

式中:v j為相鄰數據向量期望值的輸出向量;j為某個數據向量期望值;h f為輸出相對誤差;f為輸出相對誤差數量;m jf為上一層級相鄰數據向量期望值的輸出向量。

當期望輸出的權重包含相對誤差h f時,假定兩個層級v j和m jf之間的函數包含第i個可能性。在誤差大于0時可以設置為迭代完成,將所得結果作為輸出數據的期望值,用于后期隊列的排序,根據最小支持度進行裁剪即可。

3 最小支持度裁剪隊列完成數據挖掘

在建立連接矩陣后可對潛在的數據進行關聯,有效收集海量數據中較為頻繁的模式關系,根據其特性分析存在的同一事物,選擇影響度最小的數據值進行數據挖掘即可。以候選集合裁剪枝的思想理念,設定數據向量集合的規則定義,在集合Q中會有相對項的執行集合,每個集合中包含對應項,其中項所在的集合必須滿足定義集合,表達式為

式中:E為相對項的執行集合;W為其中包含的對應項;R為能夠被執行的對應項數據,用單一集合標識;I為給定集合中能夠被執行的數據可信比。

此時產生的集合T可作為定義項中的執行選項,當其屬于執行對象集合時,在兩者之間能夠生成可信比,可以作為等待執行的選項進行最小度計算,表達式為

在其中能夠對用戶的最小支持度和最小可信度進行關聯,通過掃描數據集合的矩陣隊列對重復數據進行裁剪,即可完成頻繁模式樹下的候選集數據挖掘。

至此本文通過理清層次頻繁模式樹的基本概念,結合候選集剪枝思想的基礎上,提出優先定義數據挖掘任務選項,在建立數據自動連接矩陣選集中,利用最小支持度裁剪隊列自動挖掘數據,完成基于層次頻繁模式樹的數據自動挖掘算法設計。

4 實驗結果分析

為驗證設計的數據自動挖掘算法的實際意義,選擇某動車組的運維數據作為樣本,在調取近3個月的數據信息中利用分布式集群實驗環境進行模擬,將多個路由器和動車組計算機端口完成連接,導入歷史數據。該實驗的主要目的是對本文設計的方法進行全部數據篩選,在有效時間內完成關聯對象的挖掘任務,具體測試環境的連接節點性能和參數如表1所示。

表1 數據節點名稱和性能參數

由表1可見,在實驗中共包含4組數據節點,每個節點的內存大小和主機連接形式相一致,能夠減少數據采集和儲存過程中的誤差。將動車運維計算機和建立的數據節點依次連接,其中每組數據節點為自動信息獲取模式。為能夠更加直觀地驗證新算法的優越性,選擇兩組傳統算法進行對照,分別為單機前向傳播算法和并行前向傳播算法,與本文算法進行性能對比。利用VC++6.0在內存為128 GB、CPU 為Pentium Ⅲ-733 MHz、操作系統為Windows 10的電腦中實現3種算法。設置每組數據節點的接收總量分別為200萬條、300萬條,其各自的挖掘時間測試結果,如圖1所示。

根據圖1每組數據節點,數據接收的時間間隔均設置為10 s,對不同接收數據總量的挖掘結果來看,本文方法在數據處理時間上對比兩組傳統算法,用時較少。其中在200萬條數據中3種方法的處理時間相持平,但當數據總量增加至300萬條時,所用時間的差值拉大,兩組傳統方法所用時間均高于400 s,而本文方法仍然能保持在150 s之內。綜上所述,本文方法能夠在較短的時間內完成大量繁雜數據的挖掘,具有實際應用意義。

圖1 不同算法下對數據總量的挖掘時間結果

為進一步證明本文方法能提高數據挖掘的完整性,在對比3種方法的處理時間上,以150 s為樣本數據的挖掘時間,選擇200萬條數據總量進行多輪測試,具體結果如表2所示。

表2 不同算法下數據內容保留總數

由表2可見,本文算法在多輪測試中挖掘的數據總量,與節點接收的數據相一致,基本上沒有任何出入。兩組傳統算法雖然能夠在規定時間內完成數據挖掘,但數據總量保留的平均值分別為190萬條和192萬條,比本文算法分別少了10萬條和8萬條。綜上所述,在對復雜的數據挖掘中,本文算法能夠在有效時間內執行任務,且所得數據可以完整保存,不會產生丟失現象,具有實際操作意義。

5 結 語

本文在層次頻繁模式樹的理論基礎上,結合候選集剪枝思想重新定義挖掘任務,以建立數據自動連接矩陣為基礎,利用最小支持度裁剪隊列自動挖掘數據,完成新的數據自動挖掘算法設計。實驗結果表明:在本文算法的應用下,能夠對選擇的數據總量進行有效執行,且挖掘后的數據與原有節點接收總量相一致,最大限度地保存信息的完整度,能夠被廣泛應用。后續研究中將針對挖掘后的數據進行測試,檢驗是否存在重復數據擬補丟失數據的現象,為更高效能的數據挖掘提供理論支持。