倪 東

(合肥職業(yè)技術(shù)學(xué)院,安徽 巢湖 238000)

引言

當(dāng)前人類社會處于一個信息爆炸時(shí)代,已經(jīng)步入了超大數(shù)據(jù)時(shí)代,因此如何對海量數(shù)據(jù)進(jìn)行處理,并從中找到隱含的有效知識和聯(lián)系,僅僅依靠當(dāng)前的檢索查詢和統(tǒng)計(jì)學(xué)方法已無法滿足需求了。因此,如何將海量的數(shù)據(jù)高效轉(zhuǎn)換為有用的信息,并從中發(fā)現(xiàn)數(shù)據(jù)之間的關(guān)聯(lián)信息就尤為迫切。

近些年隨著挖掘技術(shù)的進(jìn)一步發(fā)展,它能將隱含的、未知的有價(jià)值數(shù)據(jù)從海量的數(shù)據(jù)中挖掘出來。數(shù)據(jù)挖掘關(guān)聯(lián)規(guī)則對數(shù)據(jù)中的關(guān)聯(lián)性進(jìn)行分析,找出數(shù)據(jù)之間的潛在關(guān)聯(lián),并在實(shí)際應(yīng)用中起到指導(dǎo)和決策作用。

1 數(shù)據(jù)挖掘技術(shù)

數(shù)據(jù)挖掘技術(shù)[1-3]的主要目標(biāo)是從數(shù)據(jù)庫中挖掘出潛在的、用戶感興趣的、有意義的數(shù)據(jù),并通過對這些數(shù)據(jù)進(jìn)行分析,將其轉(zhuǎn)換為可供處理的數(shù)據(jù)格式,并通過經(jīng)典的算法如Apriori算法[4-5]提取出用戶需求的數(shù)據(jù)，對用戶工作進(jìn)行預(yù)測和決策。當(dāng)前數(shù)據(jù)挖掘技術(shù)已廣泛應(yīng)用在多個交叉學(xué)科領(lǐng)域中,例如人工智能、神經(jīng)網(wǎng)絡(luò)、數(shù)理統(tǒng)計(jì)等。

數(shù)據(jù)挖掘的對象一般為各類數(shù)據(jù)庫,如關(guān)系數(shù)據(jù)庫、對象數(shù)據(jù)庫。數(shù)據(jù)挖掘技術(shù)通常是隨著各類學(xué)科領(lǐng)域技術(shù)的發(fā)展而快速進(jìn)步的,接下來對其應(yīng)用的范圍進(jìn)行分類如表1所示。

表1 數(shù)據(jù)挖掘應(yīng)用范圍分類

數(shù)據(jù)挖掘過程是一個較為復(fù)雜的價(jià)值數(shù)據(jù)的發(fā)現(xiàn)過程,一般分為五個階段如圖1所示。

圖1 數(shù)據(jù)挖掘過程

數(shù)據(jù)集成:確定數(shù)據(jù)源的存儲狀態(tài),若數(shù)據(jù)是分散存儲的,則需要提前選定好數(shù)據(jù)源,并根據(jù)數(shù)據(jù)確定好數(shù)據(jù)抽取原則,明確數(shù)據(jù)的結(jié)構(gòu)和信息;接下來需要設(shè)計(jì)好數(shù)據(jù)的組織結(jié)構(gòu)、數(shù)據(jù)的交換機(jī)制、安裝機(jī)制;最后則正確抽取每個數(shù)據(jù)源中的需求信息,并以源數(shù)據(jù)的形式保存用戶動作。

數(shù)據(jù)選擇:通過在源數(shù)據(jù)中設(shè)置某些限制條件或約束條件,應(yīng)用某些算法來選擇有價(jià)值的數(shù)據(jù),刪除無價(jià)值的數(shù)據(jù),進(jìn)而獲取得到和挖掘任務(wù)緊密聯(lián)系的數(shù)據(jù)集,從而提高挖掘的效率。

數(shù)據(jù)預(yù)處理:在數(shù)據(jù)預(yù)處理之前,要檢查數(shù)據(jù)的一致性。若源數(shù)據(jù)中存在不一致、不完整、含雜質(zhì)的數(shù)據(jù),則必須對源數(shù)據(jù)進(jìn)行清洗、刪除、修補(bǔ),通常不完整的數(shù)據(jù)完善可通過全局值屬性為補(bǔ)充未知的數(shù)據(jù);采用平均值法補(bǔ)充空缺項(xiàng);利用回歸或線性工具預(yù)測可能值進(jìn)行填充;定義數(shù)據(jù)源的變換規(guī)則,從而使得在數(shù)據(jù)挖掘前保持?jǐn)?shù)據(jù)形式的統(tǒng)一。

數(shù)據(jù)挖掘算法:數(shù)據(jù)挖掘的核心是挖掘算法的選擇和應(yīng)用,不同的挖掘算法在不同領(lǐng)域中的優(yōu)勢是不一樣的,具體的數(shù)據(jù)挖掘方法如表2所示[6-8]。

表2 數(shù)據(jù)挖掘算法

2 關(guān)聯(lián)規(guī)則的數(shù)據(jù)挖掘技術(shù)

關(guān)聯(lián)規(guī)則是近年來在數(shù)據(jù)挖掘技術(shù)領(lǐng)域中應(yīng)用較為廣泛的技術(shù),它通過定義一種規(guī)則來描述數(shù)據(jù)的特征[9-10]。本文中的關(guān)聯(lián)規(guī)則挖掘技術(shù)的基本概念如表3所示。

關(guān)聯(lián)規(guī)則表示數(shù)據(jù)之間的相互關(guān)系,例事務(wù)X和Y,其中XI和XY,且X∩Y=φ,則稱X為先決條件,Y為結(jié)果,此關(guān)聯(lián)規(guī)則表示為事務(wù)X和事務(wù)Y不可能同時(shí)出現(xiàn)的,相互排斥。根據(jù)應(yīng)用場景范圍不同,關(guān)聯(lián)規(guī)則可分類為:

表3 關(guān)聯(lián)規(guī)則挖掘基本概念

1)基于源數(shù)據(jù)中變量的類型——布爾型和數(shù)值型

布爾型變量的值一般都是離散的,反應(yīng)了這些變量之間的關(guān)聯(lián),例如年齡=“18”=>職業(yè)=“學(xué)生”。數(shù)值型變量一般為多維或多層關(guān)聯(lián)項(xiàng)結(jié)合,通常需要對數(shù)值型進(jìn)行動態(tài)處理。再如工作年限=“5”=>收入=7000。

2)基于源數(shù)據(jù)中的抽象層次——單層、多層關(guān)聯(lián)規(guī)則

單層關(guān)聯(lián)規(guī)則中源數(shù)據(jù)中的數(shù)據(jù)都是單一的,并不對其進(jìn)行擴(kuò)展分析;多層關(guān)聯(lián)則對源數(shù)據(jù)中的多個方面都進(jìn)行擴(kuò)展分析,必須充分考慮各方面的情況。例如Levono電腦=>HP打印機(jī)是一個單層關(guān)聯(lián)規(guī)則;電腦=>HP打印機(jī),則是一個多層關(guān)聯(lián)規(guī)則。

3)基于源數(shù)據(jù)中的維數(shù)——單維和多維關(guān)聯(lián)規(guī)則

單維關(guān)聯(lián)規(guī)則通常是在同一個空間中進(jìn)行數(shù)據(jù)關(guān)聯(lián),是單一項(xiàng)之間的關(guān)系,但多維規(guī)則將會涉及多個事務(wù)之間的關(guān)系。例如面包=>牛奶,都是用戶可能會想買的日常品,所以這是一個單維關(guān)聯(lián)規(guī)則;年齡=18=>職業(yè)=“學(xué)生”,涉及到“年齡”、“職業(yè)”兩個不同的事務(wù),則是多維規(guī)則。

3 經(jīng)典Apriori算法及改進(jìn)

3.1 經(jīng)典Apriori算法

Apriori算法是常見的挖掘項(xiàng)頻繁集的高效算法之一,它基于頻繁項(xiàng)集理論遞推方法,通過多次迭代來逐步挖掘出相關(guān)的規(guī)則,而這些規(guī)則中的數(shù)據(jù)之間的支持度和置信度都不小于給定的最低值,因而第一次迭代時(shí),計(jì)算數(shù)據(jù)庫中每個項(xiàng)的支持度并將所有的頻繁項(xiàng)記錄為K-;后續(xù)的迭代中每一個頻繁項(xiàng)都會生成對應(yīng)的k+1候選集,在K輪迭代過程中,必須計(jì)算每一次迭代后中的所有候選項(xiàng)集(k+1)項(xiàng)的實(shí)際支持度,以此來生成下一個子項(xiàng)集;循環(huán)直至迭代過程不在產(chǎn)生新的項(xiàng)集則結(jié)束。

Apriori算法的實(shí)現(xiàn)過程如下:首先將數(shù)據(jù)庫進(jìn)行全集的掃描后,將包含所有項(xiàng)的項(xiàng)集為n階為初始值;然后在此項(xiàng)集中進(jìn)行迭代,直至項(xiàng)集為空,迭代規(guī)則為i階迭代,都對i-1次階中的項(xiàng)集Ii-1進(jìn)行Apriori運(yùn)算,進(jìn)而得到i階的候選項(xiàng)集Ci;接下來繼續(xù)在數(shù)據(jù)庫中掃描,并獲得相對應(yīng)的支持?jǐn)?shù),找到Ci中大于等于最小支持?jǐn)?shù)的i階項(xiàng)集。算法的偽代碼如下:

輸入:數(shù)據(jù)集D,以及最小的支持度min-up 輸出:最大的頻繁項(xiàng)集Ii,事務(wù)t0=D 1I1=D 2for(i=2;Ii-1≠?;i++) 3Ci=Apriori(Ii-1) 4while(t∈D) 5Ct=subset(Ci,t) 6while(C∈Ct) 7C.sup++ 8Ii={C∈Ck|C.sup≥min.up}

關(guān)聯(lián)規(guī)則在生成的過程中分為兩個步驟:根據(jù)計(jì)算獲取得到所有的頻繁項(xiàng)集,然后找到強(qiáng)頻繁項(xiàng)集中的強(qiáng)關(guān)聯(lián)規(guī)則。如何快速精確地獲取得到頻繁項(xiàng)集是關(guān)聯(lián)規(guī)則算法中的核心內(nèi)容,強(qiáng)關(guān)聯(lián)項(xiàng)之間的關(guān)聯(lián)則相對來說比較簡單,具體的關(guān)聯(lián)規(guī)則的基本思想為:

設(shè)D為數(shù)據(jù)庫中的m個項(xiàng)集合,其中事務(wù)I為非空子集。而在X的關(guān)聯(lián)規(guī)則生成中,X,Y都是I的子集,且當(dāng)中的D包含了X的百分比,則認(rèn)為是X關(guān)聯(lián)規(guī)則的支持度,而在事務(wù)X中包含了Y的百分比則是置信度。若X關(guān)聯(lián)規(guī)則的置信度和支持度均大于設(shè)置的最小值,則表示事務(wù)X,Y具備關(guān)聯(lián)性。

該算法的優(yōu)勢為支持度較低的情況下,掃描數(shù)據(jù)庫的次數(shù)較少且空間復(fù)雜度較低。但該算法會產(chǎn)生大量的候選集和數(shù)據(jù)庫的掃描次數(shù)劇增,這就會占用大量的內(nèi)存空間,增加了運(yùn)算時(shí)間和降低了運(yùn)算速度。

3.2 Apriori算法改進(jìn)

通過對經(jīng)典Apriori算法的研究可知,在性能方面需解決兩個問題:數(shù)據(jù)庫的多次迭代問題造成的I/O負(fù)載過大;候選集的大量生成給內(nèi)存空間造成的壓力。針對以上兩個問題,提出了一種基于頻繁項(xiàng)集樹模式的改進(jìn)算法,具體的形式描述為將海量的數(shù)據(jù)應(yīng)用切塊技術(shù)對其進(jìn)行劃分處理;并將切塊后的數(shù)據(jù)應(yīng)用二位數(shù)組存儲在內(nèi)存中;最后應(yīng)用動態(tài)剪枝技術(shù)將非目標(biāo)節(jié)點(diǎn)刪掉,應(yīng)用深度遍歷方式掃描頻繁項(xiàng)樹種的節(jié)點(diǎn),以此來獲取得到數(shù)據(jù)間的關(guān)聯(lián)規(guī)則。計(jì)算的步驟如下:

1)應(yīng)用劃分技術(shù),隨機(jī)的將源數(shù)據(jù)劃分為n塊,并導(dǎo)入數(shù)據(jù)庫,得到數(shù)據(jù)集D={D1,D2,…,Dn};

2)經(jīng)典Apriori算法中的頻繁項(xiàng)集將數(shù)據(jù)庫保存在磁盤中,本文將其保存在主存中,因此設(shè)計(jì)特殊的二維數(shù)組類型來存儲有效信息,行表示項(xiàng),列表示事務(wù);

3)設(shè)D中頻繁項(xiàng)集Tk={t1,t2,…,tn},全集Tall中的所有項(xiàng)集都是按照Tk={t1,t2,…,tn}排序,就將第一前綴劃分到不同的項(xiàng)集中,并以此為依據(jù)推算出之后的頻繁項(xiàng)集;

4)根據(jù)全集Tall的長度n確定要構(gòu)造的鏈,并固定其位置,然后隨機(jī)的選擇一個項(xiàng)集，并以其為根節(jié)點(diǎn)進(jìn)行遍歷,從而建立相對應(yīng)的規(guī)則鏈,直至項(xiàng)集為空。此方法是通過對生成的規(guī)則進(jìn)行遍歷過濾,來獲取置信度最小的關(guān)聯(lián)規(guī)則。

3.3 改進(jìn)算法性能分析

實(shí)驗(yàn)環(huán)境:內(nèi)存2G,CPU 2.59GHZ,Windows7系統(tǒng)。

原始數(shù)據(jù)采用的是某高校的錄取信息,共有3000多條信息,格式如圖2所示。

并通過經(jīng)典的Apriori在時(shí)間上進(jìn)行對比,可知其在構(gòu)造頻繁項(xiàng)集數(shù)算法Tree-Alr在時(shí)間上是占據(jù)比較大的優(yōu)勢如表4所示。

表4 實(shí)驗(yàn)結(jié)果對比

4 結(jié)論

本文是基于數(shù)據(jù)挖掘的關(guān)聯(lián)規(guī)則的研究,針對經(jīng)典的挖掘關(guān)聯(lián)算法Apriori中數(shù)據(jù)庫掃描次數(shù)較多,占用較多內(nèi)存空間的情況下,提出了一種新的頻繁項(xiàng)構(gòu)造方法,通過劃分塊的方式,并采用二維數(shù)組來保存數(shù)據(jù)庫,將頻繁項(xiàng)集構(gòu)造為樹結(jié)構(gòu),并獲取得到關(guān)聯(lián)規(guī)則。實(shí)驗(yàn)結(jié)果表明,改進(jìn)算法能夠降低迭代次數(shù),使用的時(shí)間更短。

圖2 某高校錄取信息數(shù)據(jù)集