分組Apriori 在圖書借閱系統(tǒng)中的應用研究

司貫中，劉 旸

(遼寧石油化工大學計算機與通訊工程學院，撫順 113001)

1 引言

數(shù)據(jù)庫技術(shù)和網(wǎng)絡技術(shù)的快速發(fā)展，帶來了信息量的爆炸式增長，這些海量數(shù)據(jù)給人們帶來便利的同時，也產(chǎn)生了一些新的問題［1］:①信息數(shù)量的增長和對信息的消化能力不匹配，導致信息難以消化;②海量信息中存在大量的虛假無用垃圾信息，對信息的有效利用造成障礙;③信息的組織形式和存儲格式?jīng)]有統(tǒng)一標準，難以統(tǒng)一處理;④信息安全很難得到切實保證。面對這種“信息爆炸、知識貧乏”的困境，如何才能夠能獲取海量數(shù)據(jù)背后隱藏的知識、提高數(shù)據(jù)的利用率呢?正是在這種背景下，數(shù)據(jù)挖掘技術(shù)應運而生，它具有強大的生命力，迅速在各個領(lǐng)域得到成功應用。數(shù)據(jù)挖掘［2］即從大量的、不完全的、有噪聲的數(shù)據(jù)中，挖掘出隱含的、事先未知的、潛在的對決策者有用的信息和知識的過程。

數(shù)據(jù)挖掘技術(shù)［3］可以粗略地分為統(tǒng)計分析、分類、聚類、關(guān)聯(lián)規(guī)則、決策樹以及神經(jīng)網(wǎng)絡。其中關(guān)聯(lián)規(guī)則挖掘是數(shù)據(jù)挖掘的一個重要分支，它通過使用機器學習技術(shù)從復雜的、不精確的大量數(shù)據(jù)中推導其真正含義，并能夠檢測提取出數(shù)據(jù)中的趨勢和模式。

2 Apriori 算法

2.1 關(guān)聯(lián)規(guī)則基本模型

IBM 公司Almaden 研究中心的R.Agrawal［4］首先提出關(guān)聯(lián)規(guī)則模型，并給出了求解算法，隨后相關(guān)學 者 提 出 了SETM 和Apriori 算 法，其 中，Apriori是關(guān)聯(lián)規(guī)則算法的基礎(chǔ)，也是最經(jīng)典的算法之一。

設(shè)I={I1，I2，...，Im}為所有項目的集合，D 表示事務數(shù)據(jù)庫，事務T是一個項目子集(T?I)。每一個事務都用唯一的事務標識TID 來表示。設(shè)A是一個由項目構(gòu)成的集合，稱為項集。事務T 包含項集A，當且僅當A?T。關(guān)聯(lián)規(guī)則是形如X?Y的蘊含式，其中X 和Y是項集，且X?I，Y?I，X∩Y=?。X 稱為規(guī)則前項(通常也叫左項)，Y 稱為規(guī)則后項(通常也叫右項)。關(guān)聯(lián)規(guī)則X?Y的支持度s是數(shù)據(jù)庫中包含X∪Y的事務占全部事務的百分比，它是概率P(X∪Y)。關(guān)聯(lián)規(guī)則X?Y的置信度c是包含X∪Y的事務數(shù)與包含X的事務數(shù)的比值，它是條件概率P(Y|X)。

在進行關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘之前，由用戶預先設(shè)定最小支持度閾值(min_sup)和最小置信度閾值(min_conf)。那些支持度大于等于min_sup 并且置信度大于等于min_conf的規(guī)則稱為強關(guān)聯(lián)規(guī)則。如果某些項集的支持度大于等于設(shè)定的最小支持度閾值min_sup，稱這個項集為頻繁項集(也稱為大項集，Large Item Sets)。所有的“頻繁k－項集”組成的集合一般記為LK。

關(guān)聯(lián)規(guī)則挖掘過程主要包含兩個階段:第一階段先從數(shù)據(jù)集中找出所有的頻繁項集，它們的支持度都大于等于最小支持度閾值min_sup;第二階段由這些頻繁項集產(chǎn)生關(guān)聯(lián)規(guī)則，計算他們的置信度，刪掉那些置信度小于最小置信度閾值min_conf的關(guān)聯(lián)規(guī)則。

2.2 Apriori 算法原理和算法描述

性質(zhì)1:頻繁項集的子集必為頻繁項集。

性質(zhì)2:非頻繁項集的超集一定是非頻繁的。

Apriori 算法利用性質(zhì)1，通過已知的頻繁項集來構(gòu)成更大的項集，并將它稱為潛在頻繁項集。然后計算潛在頻繁項集的支持度。具體實現(xiàn)過程如下:

(1)從頭到尾掃描整個事務數(shù)據(jù)庫D，計算每一個1 項集的支持度，從而得到頻繁1 項集構(gòu)成的集合L1。

(2)連接:若p，q∈Lk－1，p={p1，p2，...，pk－2，pk－1}，q={q1，q2，...qk－2，qk－1}，當1≤i p k－1時，p1=qi，當i=k－1，qk－1≠pk－1，則p∪q={p1，p2，...pk－2，pk－1，qk－1}是潛在頻繁k 項集的集合ck中的元素。

(3)剪枝:潛在k 項集的某個(k－1)子集不是Lk－1中的成員時，該潛在頻繁項集不可能是頻繁的(見性質(zhì)2)，所以從Ck中刪掉。

(4)掃描事務數(shù)據(jù)庫D，計算Ck中各個項集的支持度。

(5)將Ck中不滿足最小支持度閾值的項集刪除，形成由頻繁k 項集構(gòu)成的集合Lk。

(6)迭代循環(huán)，重復上面的步驟(2)－(5)，直到不能產(chǎn)生新的頻繁項集的集合為止。

2.3 Apriori 算法實現(xiàn)

整個算法由兩部分組成:Apriori 算法和Apriori－gen 算法［5］。

3 基于分組技術(shù)的Apriori 改進

Apriori 算法的優(yōu)點［6］是顯而易見的，它以遞歸迭代為基礎(chǔ)生成頻繁項集，思路簡單，容易實現(xiàn)。但同時也暴露了致命的缺點［7］:①對數(shù)據(jù)庫的頻繁掃描，在每一次循環(huán)中都要掃描數(shù)據(jù)庫，這造成相當大的I/O 開銷;②產(chǎn)生了大量的潛在候選項集。

針對Apriori 算法的不足，著力從兩個方面來改善這個算法，提高算法執(zhí)行的效率。針對缺點一，采取數(shù)據(jù)庫分組的方法減少掃描數(shù)據(jù)庫記錄的次數(shù)，減小了I/O 開銷。對于缺點二，我們采取先剪枝再連接的方法;經(jīng)典Apriori是先連接再剪枝，而分組Apriori 算法是先剪枝再連接，相當于減小了連接前的基數(shù)，刪掉了那些非頻繁項集，所以能夠有效的減少連接次數(shù)，從而增強了算法效率。

3.1 算法思想

(1)數(shù)據(jù)庫分組壓縮

在數(shù)據(jù)庫進行第一次掃描的時候，對每個項的出現(xiàn)次數(shù)進行計數(shù)，產(chǎn)生1－項候選集C1，然后根據(jù)事務中項的最大數(shù)對事務數(shù)據(jù)庫D 進行分組，也就是說有i個項的事務集合記為Di，從而把事務數(shù)據(jù)庫D 分為了N個組D1，D2，...，DN(N是包含最大項的個數(shù))。當由頻繁1－項集L1產(chǎn)生候選2－項候選集C2，對C2的每個候選項計數(shù)時，不必掃描整個數(shù)據(jù)庫D，而是只掃描D2到DN。以此類推，每次掃描的記錄數(shù)都在減少。

(2)先剪枝再連接

在Lk－1與自身進行連接時，對于符合條件l1［j］=l2［j ］(j=1，2，...，k－ 2)且l1［k－1］p l2［k－1］的l1和l2，需要先判斷{l1［k－1］，l2［k－1］}是否在l2中，再決定是否進行連接操作。要判斷{l1［k－1］，l2［k－1］}是否在L2中，需要掃描L2。本算法在生成L2的時候?qū)2進行了再次劃分，L2i1，L2i2...L2im，其中L2ij(j=1，2，...lm)中的元素{A，B}滿足A=ij，這樣在判斷{l1［k－1］，l2［k－1］}是不是在L2中時，只需要掃描L2i1［k－1］。

3.2 算法流程

輸入:I 基本項目集合

D //事務數(shù)據(jù)庫

s //支持度閾值

輸出:L 頻繁項集

(1)掃描數(shù)據(jù)庫D，把事務中項的數(shù)目等于J的事務放入DJ中，同時對C1所有項出現(xiàn)的次數(shù)進行計數(shù)，然后和最小支持度閾值進行比較，決定哪些項需要刪除，生成頻繁1－項集L1。

(2)把頻繁1－項集L1中滿足條件l1［1］p l2［1］的l1和l2連接，生成2－項候選集C2。從D2開始一直掃描到Dm，對C2中出現(xiàn)的每項進行計數(shù)，將滿足最小支持度并且第一項為ij的放入L2IJ。

(3)對于L2IJ中所有滿足條件(l1［2］p l2［2］的l1和l2，將它們的第二項組成項集{l1［2］，l2［2］}，然后掃描L2l1［2］，判斷{l1［2］，l2［2］}是否在l2l1［2］，如果在，就連接l1和l2，將結(jié)果放入候選的3－項集C3中，否則不進行連接操作。

(4)對于頻繁(k－1)－項集LK－1中符合條件的所有l(wèi)1［j］=l2［j］(j=1，2，...，k－2)且(l1［k－1］p l2［k－1］)的l1和l2，將它們的K－1 項組成基集{l1［k－1］，l2［k－1］}，然后再掃描L2l1［k－1］，判斷{l1［k－1］，l2［k－1］}是不是在L2l1［k－1］，如果在，就連接l1和l2，并將結(jié)果放入k－項候選集CK中，如果不在，不進行連接操作。

(5)從DK掃描到DM，對k－項候選集CK中所有項出現(xiàn)次數(shù)計數(shù)，把大于等于最小支持度min_sup的項放入LK。

(6)一直循環(huán)重復第四步和第五步，直到不能產(chǎn)生新的頻繁項集為止，此時，算法結(jié)束。

4 分組Apriori 算法在圖書借閱系統(tǒng)中的應用

數(shù)字化圖書館［8－9］相比于傳統(tǒng)的圖書館，給人們帶來了更多的時空便利，人們不再需要花費大量的時間到巨大的圖書館中查找借閱自己感興趣的圖書，只需要一臺電腦和一個能接入互聯(lián)網(wǎng)的網(wǎng)絡就可以解決這個問題，登陸數(shù)字圖書館，就可以方便的查詢和借閱。數(shù)據(jù)挖掘技術(shù)應用到數(shù)字化圖書館后，使數(shù)字圖書館更加智能化、高效化、個性化。從某種意義上說，數(shù)字化圖書館讓每個人都可以擁有一個定制的屬于個人的小型圖書館。

分組Apriori 算法引入到圖書個性化推薦系統(tǒng)，該系統(tǒng)工作流程如下:數(shù)據(jù)預處理模塊對圖書館借閱歷史信息數(shù)據(jù)庫提取原始數(shù)據(jù)，并對原始數(shù)據(jù)庫進行預處理;數(shù)據(jù)挖掘模塊利用引入的分組Apriori算法對數(shù)據(jù)進行挖掘，得到的結(jié)果存入關(guān)聯(lián)數(shù)據(jù)庫;讀者登陸數(shù)字化圖書館，打開查詢頁面，輸入自己感興趣的信息，查找到所需求的圖書，當點擊這些圖書時，這時圖書推薦系統(tǒng)給讀者推薦相關(guān)的圖書供讀者選擇。圖書推薦模型工作流程如圖1 所示。

5 算法性能評測

實驗采用的事務數(shù)據(jù)全部來之于某高校的圖書館借閱信息數(shù)據(jù)庫，以讀者的一次借閱行為作為一個事務數(shù)據(jù)。那些只有一個數(shù)據(jù)項的事務直接舍棄(一位讀者一次只借一本書沒有任何研究意義)，經(jīng)過數(shù)據(jù)清洗后得到有效借閱記錄。Apriori 算法和分組Apriori 算法均用JAVA 語言在Eclipse 下實現(xiàn)，其中經(jīng)典Apriori 算法采用的是開源數(shù)據(jù)挖掘平臺WEKA［10］源碼。實驗環(huán)境:CPU(Pentium R 2.0G)，MEMORY(DDR2 2G)，操作系統(tǒng)(WINDOWS XP)。

圖1 圖書個性化推薦模型

實驗一:采用50000個有效的事務項，在不同各支持度下對兩種算法進行比較，得到的實驗結(jié)果如圖2 所示。在支持度比較小的情況下，兩種算法的運行時間相差較大，隨著支持度取值的不斷增加，兩種算法的運行時間差別較小。這是因為較高的支持度下，候選項集急劇減少，兩種算法掃描數(shù)據(jù)庫的開銷都相對較小。

圖2 不同最小支持度下兩種算法的運行時間

實驗二:取固定的最小支持度0.002，事務數(shù)據(jù)集分別采用1W、2W、3W、4W、5W，兩種算法運行的時間如圖3 所示。

綜上實驗和分析算法原理，分組Apriori 算法在事務分組特別多的情況下效果相當良好，在數(shù)字圖書館借閱系統(tǒng)中，讀者至少借一本，最多可以借15本(高校最多借閱量情況不同)，讀者所能借閱的書籍最大數(shù)數(shù)目越大，則分組Apriori 算法效率越能得到體現(xiàn)。

圖3 不同事務數(shù)據(jù)量下兩種算法的運行時間

6 結(jié)束語

個性化服務是數(shù)字化圖書館不可避免的主流趨勢。分析了關(guān)聯(lián)規(guī)則挖掘經(jīng)典算法Apriori的算法思想和流程，提出使用分組技術(shù)對原算法進行改進。將分組Apriori 算法應用到數(shù)字圖書館的借閱系統(tǒng)中，對不同讀者需求的圖書進行智能推薦。

［1］George M.Marakas，著.數(shù)據(jù)倉庫、挖掘和可視化:核心概念［M］.敖富江，譯.北京:清華大學出版社，2004.

［2］李寶東，宋瀚濤.數(shù)據(jù)挖掘語言研究現(xiàn)狀及發(fā)展［J］.計算機工程與應用，2003(6):62－64.

［3］胡艷翠.基于關(guān)聯(lián)規(guī)則的數(shù)據(jù)挖掘算法研究［D］.大連:大連海事大學，2009.

［4］Agrawal R，Imielinsi T，Swami A.Mining association rules between sets of items in large database［R］.the 1993 ACM SIGMOD conference，Washington D.C，USA，1993.

［5］(美)Pang－Ning Tan，Michael Steinbach，Vipin Kumar，著，數(shù)據(jù)挖掘?qū)д摚跰］.范明，范宏建，譯.北京:人民郵電出版社，2006.

［6］劉以安，羊斌.關(guān)聯(lián)規(guī)則挖掘中對Apriori 算法的一種改進研究［J］.計算機應用，2007，27(2):418－420.

［7］毛國君，段立娟.數(shù)據(jù)挖掘原理與算法［M］.北京:清華大學出版社，2005.

［8］鮑靜.關(guān)聯(lián)規(guī)則挖掘及其在圖書流通數(shù)據(jù)中的應用研究［D］.合肥:合肥工業(yè)大學，2007.

［9］尤鳳英.數(shù)據(jù)挖掘技術(shù)及其在數(shù)字圖書館中的應用［J］.辦公自動化雜志，2007(9):51－52.

［10］于辰云，劉旸，周金枝.基于插件技術(shù)的數(shù)據(jù)挖掘平臺設(shè)計與實現(xiàn)［J］.2010，30(2):46－49.