毛 敬 玉

(蘭州職業(yè)技術(shù)學(xué)院，甘肅 蘭州 730070)

1 APRIORI算法和OLAP

數(shù)據(jù)挖掘是近年來研究數(shù)據(jù)庫領(lǐng)域的熱點之一。在眾多數(shù)據(jù)挖掘方法中，關(guān)聯(lián)規(guī)則是數(shù)據(jù)挖掘中的重要研究對象。它最典型的應(yīng)用就是在大量的數(shù)據(jù)庫信息中發(fā)現(xiàn)新的有用的信息。APRIORI算法是一種使用很廣泛的挖掘布爾關(guān)聯(lián)規(guī)則頻繁項集的算法，是關(guān)聯(lián)規(guī)則挖掘算法中的經(jīng)典算法之一。它的基本思想是：首先找出所有的項集，這些項集出現(xiàn)的頻繁性至少要與預(yù)定義的最小支持度一致。然后由這些頻集生成強關(guān)聯(lián)規(guī)則，這些規(guī)則必須滿足最小支持度與最小可信度。然后使用第1步找到的項集產(chǎn)生期望的規(guī)則，產(chǎn)生只包含集合的項的所有規(guī)則，其中每一條規(guī)則在右部只有一項，這里采用的是中規(guī)則的定義。一旦這些規(guī)則被生成，那么只有那些大于用戶所給定的最小可信度的規(guī)則才會被留下來。為了生成所有頻繁項集，使用了遞歸的方法。 程序如下：

algorithm apriori(T)

C1←init-pass(T)

while (k=2;Fk-1≠￠;k++)do

Ck←candidate-gen(Fk-1)

while each transaction t∈T do

while each condidate c∈Ck do

if c is contained int

then c.count++

end if

end while

end while

end while

return F←UkFk

OLAP聯(lián)機分析處理技術(shù)是目前數(shù)據(jù)倉庫中數(shù)據(jù)多維分析的使用最多的驗證型工具。OLAP系統(tǒng)采用數(shù)據(jù)存儲方案為物化數(shù)據(jù)立方體，以空間代價來換取時間效率。對關(guān)聯(lián)規(guī)則挖掘來說，挖掘過程中大量所需的中間數(shù)據(jù)已經(jīng)被物化在數(shù)據(jù)立方體中而無需重新計算，由此可以節(jié)約大量的數(shù)據(jù)挖掘時間。

圖書行業(yè)在其發(fā)展過程中，積累了大量的各種圖書的流通信息，以往的信息管理系統(tǒng)缺少尋找大量數(shù)據(jù)間的有用的、隱含的和潛在的信息能力，如何有效利用APRIPRI算法和OLAP關(guān)聯(lián)規(guī)則，從海量的數(shù)據(jù)中挖掘出有實用價值的信息，并在圖書管理過程中將其轉(zhuǎn)化為效益，是圖書管理者們的急迫任務(wù)之一。本文將根據(jù)APRIORI算法的特點對OLAP數(shù)據(jù)立方體維度、度量值等方面設(shè)計進(jìn)行充分考慮，設(shè)計出能高效地為關(guān)聯(lián)規(guī)則挖掘程序提供更多的中間數(shù)據(jù)，以此為基石，通過現(xiàn)存的圖書關(guān)系數(shù)據(jù)庫和實際的圖書信息數(shù)據(jù)，生成數(shù)據(jù)立方體并進(jìn)行關(guān)聯(lián)規(guī)則的挖掘。

2 APRIORI算法在圖書系統(tǒng)數(shù)據(jù)挖掘中的應(yīng)用

隨著專業(yè)的不斷分支發(fā)展，人們對于專業(yè)學(xué)習(xí)的不斷深入和細(xì)化，圖書在圖書營銷或圖書館建設(shè)過程中都積累了大量的圖書信息數(shù)據(jù)，并且這個數(shù)據(jù)與日俱增。如何處理和如何深入其內(nèi)部獲取有用的信息，研究人員進(jìn)行了大量的探索，而人們也不再只停留在對數(shù)據(jù)的簡單操作上轉(zhuǎn)而開始思考和探索如何從海量的數(shù)據(jù)中提取藏在數(shù)據(jù)背后的、潛在的知識或信息為最終的決策提供有力的數(shù)據(jù)支持。例如圖書館藏書的分類整理、圖書市場的運營管理決策、電子圖書館建設(shè)過程中對于圖書的選擇等等。

我們可以按圖2流程來進(jìn)行：

2.1 OLAP引擎和數(shù)據(jù)立方體

從圖1我們可以看出，OLAP引擎和數(shù)據(jù)立方體是不同的兩個模塊，但是兩者的關(guān)系很密切。數(shù)據(jù)立方體為OLAP引擎提供數(shù)據(jù)存儲，OLAP引擎為數(shù)據(jù)立方體提供I/O接口操作和其他數(shù)據(jù)立方體操作。

2.2 維度表和事實表的設(shè)計

在整個數(shù)據(jù)挖掘過程中，需要用到事實表和維度表。事實表是數(shù)據(jù)倉庫架構(gòu)中的中央表，它包含連接事實與維度表之間的數(shù)字度量值和關(guān)鍵字。事實數(shù)據(jù)表包含描述運作過程中特定事件的數(shù)據(jù)。維度表可以是用戶用來分析數(shù)據(jù)的窗口。維度表中包含事實數(shù)據(jù)表中事實記錄的特性，有些提供描述性特性信息，有些指定如何匯總事實數(shù)據(jù)表特性數(shù)據(jù)，以便提供有用的信息給分析者，維度表包含幫助匯總數(shù)據(jù)的特性的層次結(jié)構(gòu)。

我們給每一個信息表建立一張對應(yīng)的維度表，為了避免重復(fù)，我們需要給這些維度表重新用一個序號來標(biāo)識，同時建立一張事實表，以各維度表的主關(guān)鍵字為關(guān)鍵字，并建立一個事實表的關(guān)鍵字序號，形成一個相應(yīng)的星型結(jié)構(gòu)，如圖3所示。

以圖書館管理為例，我們需要用到的主要的數(shù)據(jù)表有以下內(nèi)容：

圖書基本信息表書號書名作者定價出版社名稱出版日期登記日期圖書庫存信息表書號書名類別所存書庫在庫量入庫時間出庫時間出版社信息出版社名稱地址網(wǎng)址電子郵箱聯(lián)系電話聯(lián)系人郵政編碼借閱信息表書號證號借閱時間歸還日期是否續(xù)借借閱數(shù)量借閱類別讀者基本信息表證號姓名性別年齡從事職業(yè)所在單位聯(lián)系電話

這些表格產(chǎn)生的維度表構(gòu)成的星型結(jié)構(gòu)圖如下：

APRIORI算法存在以下兩個比較明顯的缺陷。首先，有可能產(chǎn)生大量的候選集；其次，需要重復(fù)掃描數(shù)據(jù)倉庫中的數(shù)據(jù)，在挖掘過程中會因迭代產(chǎn)生候選項集用來統(tǒng)計其支持度而花費大量的時間。為了節(jié)約運算時間，我們需要將算法加以改進(jìn)來提高效率，改進(jìn)的算法描述如下：

任何長度為k的事務(wù)都不可能包含(k+1)-項子集。對原始事務(wù)數(shù)據(jù)庫中的每一個事務(wù)進(jìn)行第一次掃描并計數(shù)后，立即刪除長度為1的當(dāng)前事務(wù)，因為該事務(wù)不會對后面的頻繁2-項集的生成起作用，所以以后的操作不再需要該事務(wù)了。在進(jìn)行第二次掃描并對2-項集計數(shù)之后，立即刪除長度為2的事務(wù)。這樣，第二遍掃描的事務(wù)數(shù)據(jù)庫就被壓縮了，從而提高了算法的效率。該方法可以應(yīng)用到以后的每一趟掃描中，即在對候選k-項集計數(shù)之后，立即刪除長度為k的事務(wù)。

procedure apriori-whb(Lk-l,min-sup)

forall items l1∈Lk-l

forall items l2∈Lk-l

if ((l1[1]=l2[1])∧...∧(l1[k-2]=l2[k-2])∧l1[k-1]

C=l1?l2 //連接兩個項集

if has-infrequent-item set(C,Lk-l)

delete C

else Ck=Ck∨{C}

end if

Dk=whb-del(Dk-l,Lk-l)//刪除不滿足條件項集，減少下次掃描DB的記錄次數(shù)

end if

return Ck

procedure whb-del(Lk-l,Dk-l)

forall items l1∈Dk-l

if |l1|

end if

if l1≮Lk-l then delete l1

end if

return Dk

procedure has-infrequent-sub set(C,Lk-l)

forall (K-1)subset s of C

if s￠Lk-l then return true

else return false

end if

L1={large l-itemsets}//D中的L項集

for(k=2;Lk-l≠?;k++)do begin

Ck=apriori-gen(Lk-l,minsup)

forall transaction t∈D do begin

Ct=subset(Ck,t)//t所包含的候選項集

forall candidate c∈Ct do

c.count++

end

Lk={c∈Ck|c.count≥minsup}

end

answer=UkLk

3 結(jié)語

本文主要介紹了基于APRIORI算法和OLAP的關(guān)聯(lián)規(guī)則對圖書信息分類模型的設(shè)計，為圖書館或者學(xué)校圖書管理提供了很好的技術(shù)支持，使圖書管理和圖書分類變得越來越簡單，越來越方便。

參考文獻(xiàn)：

[1][美]陳封能，斯坦巴赫，庫瑪爾.數(shù)據(jù)挖掘?qū)д揫M].北京：人民郵電出版社，2011.

[2]董琳.數(shù)據(jù)挖掘?qū)嵱脵C器學(xué)習(xí)技術(shù)[M].北京：機械工業(yè)出版社，2006.

[3]林杰斌.數(shù)據(jù)挖掘與OLAP理論與實務(wù)[M].北京：清華大學(xué)出版社，2003.

[4]何玉潔，張俊超.數(shù)據(jù)倉庫與OLAP實踐教程[M].北京：清華大學(xué)出版社，2008.