司貫中，劉 旸

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

1 引言

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

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

2 Apriori 算法

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

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

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

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

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

2.2 Apriori 算法原理和算法描述

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

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

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

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

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

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

(4)掃描事務(wù)數(shù)據(jù)庫(kù)D，計(jì)算Ck中各個(gè)項(xiàng)集的支持度。

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

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

2.3 Apriori 算法實(shí)現(xiàn)

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

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

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

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

3.1 算法思想

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

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

(2)先剪枝再連接

在Lk－1與自身進(jìn)行連接時(shí)，對(duì)于符合條件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中，再?zèng)Q定是否進(jìn)行連接操作。要判斷{l1［k－1］，l2［k－1］}是否在L2中，需要掃描L2。本算法在生成L2的時(shí)候?qū)2進(jìn)行了再次劃分，L2i1，L2i2...L2im，其中L2ij(j=1，2，...lm)中的元素{A，B}滿足A=ij，這樣在判斷{l1［k－1］，l2［k－1］}是不是在L2中時(shí)，只需要掃描L2i1［k－1］。

3.2 算法流程

輸入:I 基本項(xiàng)目集合

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

s //支持度閾值

輸出:L 頻繁項(xiàng)集

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

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

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

(4)對(duì)于頻繁(k－1)－項(xiàng)集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 項(xiàng)組成基集{l1［k－1］，l2［k－1］}，然后再掃描L2l1［k－1］，判斷{l1［k－1］，l2［k－1］}是不是在L2l1［k－1］，如果在，就連接l1和l2，并將結(jié)果放入k－項(xiàng)候選集CK中，如果不在，不進(jìn)行連接操作。

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

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

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

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

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

5 算法性能評(píng)測(cè)

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

圖1 圖書個(gè)性化推薦模型

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

圖2 不同最小支持度下兩種算法的運(yùn)行時(shí)間

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

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

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

6 結(jié)束語

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

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

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

［3］胡艷翠.基于關(guān)聯(lián)規(guī)則的數(shù)據(jù)挖掘算法研究［D］.大連:大連海事大學(xué)，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ī)則挖掘中對(duì)Apriori 算法的一種改進(jìn)研究［J］.計(jì)算機(jī)應(yīng)用，2007，27(2):418－420.

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

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

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

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