基于層次頻繁模式樹的數(shù)據(jù)自動挖掘算法

王景蘭, 方 曉

(亳州職業(yè)技術(shù)學(xué)院 信息工程系, 安徽 亳州 236800)

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

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

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

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

由于算法實(shí)現(xiàn)以層次分類頻繁模式樹為依據(jù),故在算法進(jìn)行之前需要生成層次頻繁模式樹,生成過程如下:

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

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

(3) 對事務(wù)數(shù)據(jù)庫進(jìn)行一次投影操作,將原始項(xiàng)集中不在H—List的項(xiàng)刪除。

(4) 對于每一個(gè)事務(wù)Ti,根據(jù)處理后的項(xiàng)集,結(jié)合項(xiàng)在TS—List的層次關(guān)系生成層次頻繁模式樹(HCFP—Tree)。HCFP—Tree生成時(shí),相同層次的特征節(jié)點(diǎn)可以共享路徑、類別節(jié)點(diǎn)。

(5) 生成標(biāo)頭Header表,表中指針指向?qū)?yīng)的類標(biāo)簽節(jié)點(diǎn)。

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

2 建立數(shù)據(jù)自動連接矩陣

根據(jù)層次頻繁模式樹給出的挖掘任務(wù),對需要整合的數(shù)據(jù)進(jìn)行權(quán)重分析,以此建立相對應(yīng)的連接矩陣,根據(jù)層次分析法的權(quán)重生成模式,對變量數(shù)據(jù)進(jìn)行離散。以每組連續(xù)數(shù)據(jù)的取值范圍[0,1]作為單次節(jié)點(diǎn)出入項(xiàng),確定不同任務(wù)層級的連接權(quán)重,每個(gè)層級的數(shù)據(jù)個(gè)數(shù)設(shè)置為g,數(shù)據(jù)向量的輸入矩陣表示為

式中:S為輸入向量的連接權(quán)重,在輸入樣本向量中設(shè)置f×g的矩陣類型,f為輸入數(shù)據(jù)的記錄數(shù)值。

根據(jù)連接權(quán)重的數(shù)據(jù)分別設(shè)置相鄰數(shù)據(jù)向量的期望值,利用隱藏函數(shù)作為反復(fù)迭代的補(bǔ)充,計(jì)算其輸出向量,表達(dá)式為

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

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

3 最小支持度裁剪隊(duì)列完成數(shù)據(jù)挖掘

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

式中:E為相對項(xiàng)的執(zhí)行集合;W為其中包含的對應(yīng)項(xiàng);R為能夠被執(zhí)行的對應(yīng)項(xiàng)數(shù)據(jù),用單一集合標(biāo)識;I為給定集合中能夠被執(zhí)行的數(shù)據(jù)可信比。

此時(shí)產(chǎn)生的集合T可作為定義項(xiàng)中的執(zhí)行選項(xiàng),當(dāng)其屬于執(zhí)行對象集合時(shí),在兩者之間能夠生成可信比,可以作為等待執(zhí)行的選項(xiàng)進(jìn)行最小度計(jì)算,表達(dá)式為

在其中能夠?qū)τ脩舻淖钚≈С侄群妥钚】尚哦冗M(jìn)行關(guān)聯(lián),通過掃描數(shù)據(jù)集合的矩陣隊(duì)列對重復(fù)數(shù)據(jù)進(jìn)行裁剪,即可完成頻繁模式樹下的候選集數(shù)據(jù)挖掘。

至此本文通過理清層次頻繁模式樹的基本概念,結(jié)合候選集剪枝思想的基礎(chǔ)上,提出優(yōu)先定義數(shù)據(jù)挖掘任務(wù)選項(xiàng),在建立數(shù)據(jù)自動連接矩陣選集中,利用最小支持度裁剪隊(duì)列自動挖掘數(shù)據(jù),完成基于層次頻繁模式樹的數(shù)據(jù)自動挖掘算法設(shè)計(jì)。

4 實(shí)驗(yàn)結(jié)果分析

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

表1 數(shù)據(jù)節(jié)點(diǎn)名稱和性能參數(shù)

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

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

圖1 不同算法下對數(shù)據(jù)總量的挖掘時(shí)間結(jié)果

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

表2 不同算法下數(shù)據(jù)內(nèi)容保留總數(shù)

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

5 結(jié) 語

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