分組Apriori 在圖書借閱系統中的應用研究

司貫中，劉 旸

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

1 引言

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

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

2 Apriori 算法

2.1 關聯規則基本模型

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

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

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

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

2.2 Apriori 算法原理和算法描述

性質1:頻繁項集的子集必為頻繁項集。

性質2:非頻繁項集的超集一定是非頻繁的。

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

(1)從頭到尾掃描整個事務數據庫D，計算每一個1 項集的支持度，從而得到頻繁1 項集構成的集合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中的成員時，該潛在頻繁項集不可能是頻繁的(見性質2)，所以從Ck中刪掉。

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

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

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

2.3 Apriori 算法實現

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

3 基于分組技術的Apriori 改進

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

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

3.1 算法思想

(1)數據庫分組壓縮

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

(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的時候對L2進行了再次劃分，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 //事務數據庫

s //支持度閾值

輸出:L 頻繁項集

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

(2)把頻繁1－項集L1中滿足條件l1［1］p l2［1］的l1和l2連接，生成2－項候選集C2。從D2開始一直掃描到Dm，對C2中出現的每項進行計數，將滿足最小支持度并且第一項為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，將結果放入候選的3－項集C3中，否則不進行連接操作。

(4)對于頻繁(k－1)－項集LK－1中符合條件的所有l1［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，并將結果放入k－項候選集CK中，如果不在，不進行連接操作。

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

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

4 分組Apriori 算法在圖書借閱系統中的應用

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

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

5 算法性能評測

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

圖1 圖書個性化推薦模型

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

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

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

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

圖3 不同事務數據量下兩種算法的運行時間

6 結束語

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

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

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

［3］胡艷翠.基于關聯規則的數據挖掘算法研究［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，著，數據挖掘導論［M］.范明，范宏建，譯.北京:人民郵電出版社，2006.

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

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

［8］鮑靜.關聯規則挖掘及其在圖書流通數據中的應用研究［D］.合肥:合肥工業大學，2007.

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

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