〔摘 要〕關(guān)聯(lián)規(guī)則是數(shù)據(jù)挖掘的重要模式之一，有著極其重要的應(yīng)用價(jià)值。由于其自身的優(yōu)點(diǎn)，關(guān)聯(lián)規(guī)則得到了迅速發(fā)展，并開始了廣泛應(yīng)用，然而傳統(tǒng)的關(guān)聯(lián)規(guī)則算法在應(yīng)用中有很多的不足。因此本文提出了一種基于用戶層次信息的關(guān)聯(lián)規(guī)則圖書推薦系統(tǒng)，實(shí)驗(yàn)結(jié)果表明，該算法能夠有效減少運(yùn)算量，并能提高推薦的準(zhǔn)確度。

〔關(guān)鍵詞〕關(guān)聯(lián)規(guī)則；圖書推薦；數(shù)字圖書館

ＤＯＩ：１０．３９６９／ｊ．ｉｓｓｎ．１００８－０８２１．２０１０．１２．０２０

〔中圖分類號〕Ｇ２０２ 〔文獻(xiàn)標(biāo)識碼〕Ｂ 〔文章編號〕１００８－０８２１（２０１０）１２－００７３－０４

A Book Recommender System Based on User Hierarchy Association RulesTian Yan Li Jia Song Weihua

（Library，Xian University of Technology，Xian 710048，China）

〔Ａｂｓｔｒａｃｔ〕Association rule is one of the important modes in data mining and has a very important value.Because of its good quality，association rules is becoming the popular one and has used widely.However，the traditional algorithms of association rules have lots of limitation in practical applications.In this paper，a recommender system was presented based on multi-user association rules.Experiment result showed that this method could decrease the computation multiplications and improve the accuracy of the recommendation.

〔Ｋｅｙｗｏｒｄｓ〕association rule;book recommendation;digital library

高校圖書館作為高校師生的一個(gè)重要知識庫，在高等教育的發(fā)展中有著不可估量的重要作用。圖書館藏書所涉及的領(lǐng)域非常廣泛，圖書館每年購入大量的新書，因此圖書館藏書量在不斷增多。師生們要在眾多的書籍中找到自己需要的相關(guān)圖書是一件非常困難的事情。目前圖書館采用的圖書流通管理數(shù)據(jù)庫可以實(shí)現(xiàn)數(shù)據(jù)的錄入、查詢、統(tǒng)計(jì)等功能，但無法發(fā)現(xiàn)數(shù)據(jù)庫中存在的關(guān)系和規(guī)則，缺乏挖掘數(shù)據(jù)背后隱藏知識的手段。

圖書館流通管理數(shù)據(jù)庫每天都會產(chǎn)生大量的借閱數(shù)據(jù)，它們對圖書館了解讀者的借閱興趣有著很強(qiáng)的指導(dǎo)作用。如何充分利用這些日益增長的大量數(shù)據(jù)，從中找到有用的信息，迫切要求一種強(qiáng)有力的工具，依據(jù)讀者的行為特性與借閱習(xí)慣，提供智能圖書推薦服務(wù)。關(guān)聯(lián)規(guī)則正是這樣一種新興的技術(shù)。關(guān)聯(lián)規(guī)則作為當(dāng)前數(shù)據(jù)挖掘研究、開發(fā)和應(yīng)用最活躍的分支之一，引起了研究者的廣泛關(guān)注。

許多學(xué)者對關(guān)聯(lián)規(guī)則挖掘進(jìn)行了大量研究工作。本文在這些研究基礎(chǔ)之上，提出一種改進(jìn)算法，并將改進(jìn)的挖掘算法對圖書館流通數(shù)據(jù)進(jìn)行挖掘，為讀者提供個(gè)性化的圖書推薦信息服務(wù)。

本文第二部分闡述關(guān)聯(lián)規(guī)則的基本原理與算法；第三部分介紹基于多用戶關(guān)聯(lián)規(guī)則的圖書推薦算法；第四部分介紹實(shí)驗(yàn)結(jié)果；第五部分為結(jié)論。

１ 關(guān)聯(lián)規(guī)則的基本原理與算法

關(guān)聯(lián)規(guī)則（Association Rules）的概念首先由R.Agrawal等于1993年提出的，是反映一個(gè)事物與其他事物之間的相互依賴性或相互關(guān)聯(lián)性［１］。該算法的基本原理就是尋找描述數(shù)據(jù)庫中數(shù)據(jù)項(xiàng)(屬性、變量)之間存在(潛在)的關(guān)聯(lián)，利用關(guān)聯(lián)規(guī)則的數(shù)據(jù)挖掘技術(shù)，找出大量數(shù)據(jù)之間未知的依賴關(guān)系。隨著關(guān)聯(lián)規(guī)則挖掘算法的不斷改進(jìn)，使關(guān)聯(lián)規(guī)則理論得到了更廣泛的應(yīng)用。

１.１ 關(guān)聯(lián)規(guī)則基本原理

在介紹關(guān)聯(lián)規(guī)則之前，我們首先介紹幾個(gè)相關(guān)定義。

定義１：設(shè)I=｛I1，I2，…，Im｝是一個(gè)項(xiàng)的有限集合，稱為項(xiàng)集；TD是一個(gè)事務(wù)數(shù)據(jù)庫，T表示其中的一個(gè)事務(wù)，有惟一的標(biāo)識符TID，且有ＴＩ；設(shè)ＸＩ，當(dāng)且僅當(dāng)ＸＩ時(shí)稱事務(wù)T支持項(xiàng)集X

定義２：關(guān)聯(lián)規(guī)則表示為：Ｘ＝＞Ｙ的蘊(yùn)涵式，這里ＸＩ，ＹＩ，并且Ｘ∩Ｙ＝Φ。若規(guī)則Ｘ＝＞Ｙ在事物集TD中成立，則關(guān)聯(lián)規(guī)則Ｘ＝＞Ｙ具有支持度Support(X＝＞Y)和置信度Confidence(X＝＞Y)。

Support（X＝＞Y）=count（X∪Y）／（｜TD｜）×100%

Confidence（X＝＞Y）=count（X∪Y）／count（X）×100%

其中，count（X∪Y）是包含項(xiàng)集X∪Y的事務(wù)數(shù)，｜TD｜是數(shù)據(jù)庫D中所有的事務(wù)數(shù)，count(X)是包含項(xiàng)集X的事務(wù)數(shù)。

１.２ 關(guān)聯(lián)規(guī)則基本算法

挖掘關(guān)聯(lián)規(guī)則的算法很多，下面主要介紹的是經(jīng)典的Apriori算法［２］。Apriori算法是一種最具影響力的挖掘布爾關(guān)聯(lián)規(guī)則的頻繁項(xiàng)集的算法。它的主要思想是利用逐層搜索的迭代方法，來尋找數(shù)據(jù)庫中頻繁出現(xiàn)的項(xiàng)集。

Apriori算法主要包括3個(gè)步驟：

１.２.１ 連接步

為找Lk+1，通過Lk與自己連接產(chǎn)生（k+1）-項(xiàng)集的集合。該侯選項(xiàng)的集合記作Ck+1。設(shè)li和lj是Lk的項(xiàng)集，li［k］記號表示li的第k項(xiàng)。執(zhí)行連接Lk∞Lk，其中Lk的元素是可以連接的。如果（li［1］=lj［1］）∧（li［2］=lj［2］）∧…∧（li［k-1］=lj［k-1］）∧（li［k］＜lj［k］），其中條件（li［k］＜lj［k］）是簡單的保證不產(chǎn)生重復(fù)。連接li和lj產(chǎn)生的結(jié)果項(xiàng)集是：li［1］li［2］…li［k-1］li［k］。

１.２.２ 剪枝步

Ck是Lk的超集；利用Apriori性質(zhì)：任何非頻繁的（k-1）-項(xiàng)集都不可能是頻繁k-項(xiàng)集的子集。因此，如果一個(gè)候選k-項(xiàng)集的（k-1）-子集不在Lk中，則該候選項(xiàng)集也不可能是頻繁的，從而可以從Ck中刪除。

１.２.３ 掃描數(shù)據(jù)庫

掃描數(shù)據(jù)庫，累計(jì)Ck中的每一項(xiàng)出現(xiàn)的次數(shù)。若某記錄包括該候選項(xiàng)，這候選項(xiàng)的支持度計(jì)數(shù)加1，最后通過比較其支持度和最小支持度確定該候選項(xiàng)是否為頻繁項(xiàng)。

２０１０年１２月第３０卷第１２期一種基于用戶層次信息的關(guān)聯(lián)規(guī)則圖書推薦系統(tǒng)Ｄｅｃ.，２０１０２ 基于多用戶關(guān)聯(lián)規(guī)則的圖書推薦算法

通過上面的介紹，如果將Apriori算法直接用于圖書推薦算法存在以下幾個(gè)問題：

（１）圖書館中的流通數(shù)據(jù)庫數(shù)據(jù)量非常大，一般的計(jì)算機(jī)內(nèi)存容量很有限，不可能將所有數(shù)據(jù)庫中的數(shù)據(jù)加載到計(jì)算機(jī)內(nèi)存中。根據(jù)Apriori算法，Ck只能通過多次掃描數(shù)據(jù)庫得到Lk，而掃描數(shù)據(jù)庫時(shí)需要對數(shù)據(jù)換進(jìn)換出，因此面向海量數(shù)據(jù)，Apriori算法由于需要頻繁地掃描數(shù)據(jù)庫，運(yùn)算時(shí)間將很長，運(yùn)行效率較低，系統(tǒng)開銷非常大。

（２）圖書館流通數(shù)據(jù)庫中的數(shù)據(jù)比較稠密，由稠密集生成的頻繁項(xiàng)集數(shù)量很大，因此導(dǎo)致Ck很大，頻繁項(xiàng)集的長度也變的很大，從而使APriori算法失效，不能運(yùn)行［３］。

（３）Apriori算法利用支持度和置信度縮減挖掘數(shù)據(jù)庫的搜索空間和約束規(guī)則產(chǎn)生的數(shù)量。支持度和置信度選擇不當(dāng)可能導(dǎo)致生成的關(guān)聯(lián)規(guī)則過于龐大，應(yīng)用在圖書推薦，生成的有些規(guī)則是讀者不感興趣或興趣不大的，甚至是讀者已經(jīng)知道的規(guī)則。

（４）圖書館的讀者成千上萬，他們性別不同，專業(yè)不同，閱讀興趣和愛好也各不相同，因此如果簡單的用Apriori算法生成的規(guī)則，可能生成的關(guān)聯(lián)規(guī)則過于單一，無法針對不同類型的讀者提供個(gè)性化的圖書推薦服務(wù)，從而使生成的關(guān)聯(lián)規(guī)則毫無意義。

針對以上的問題，本文提出了基于多用戶的關(guān)聯(lián)規(guī)則的圖書推薦系統(tǒng)。

２.１ 多用戶關(guān)聯(lián)規(guī)則的圖書推薦系統(tǒng)

本系統(tǒng)的主要步驟就是首先根據(jù)讀者類型將借閱數(shù)據(jù)分層歸類，并存入到子數(shù)據(jù)庫中，然后先根據(jù)子數(shù)據(jù)生成局部關(guān)聯(lián)規(guī)則，最后通過分布式關(guān)聯(lián)規(guī)則生成算法生成全局關(guān)聯(lián)規(guī)則。當(dāng)讀者登陸系統(tǒng)后，系統(tǒng)根據(jù)讀者所屬的最高一層子數(shù)據(jù)庫的借閱規(guī)則為讀者推薦書目，如果不滿足讀者需求，進(jìn)入到下一級子數(shù)據(jù)庫，根據(jù)下一級數(shù)據(jù)庫的關(guān)聯(lián)規(guī)則為讀者提供圖書推薦服務(wù)，直至根數(shù)據(jù)庫的關(guān)聯(lián)規(guī)則為讀者提供服務(wù)。數(shù)據(jù)庫分層結(jié)構(gòu)示意圖如圖１所示。

其中，最底層數(shù)據(jù)庫子集稱為葉子節(jié)點(diǎn)數(shù)據(jù)庫，最上一層數(shù)據(jù)稱為根數(shù)據(jù)庫。

基于數(shù)據(jù)庫分層的關(guān)聯(lián)規(guī)則挖掘的優(yōu)點(diǎn)是，能針對性的給讀者推薦圖書，而且不容易漏掉對讀者有價(jià)值的關(guān)聯(lián)規(guī)則。

例如：假設(shè)數(shù)據(jù)庫有流通記錄100萬條，｛計(jì)算機(jī)網(wǎng)絡(luò)，網(wǎng)絡(luò)安全｝該事務(wù)有3萬條，計(jì)算機(jī)專業(yè)學(xué)生借閱記錄中有20萬條，其中包含｛計(jì)算機(jī)網(wǎng)絡(luò)，網(wǎng)絡(luò)安全｝事務(wù)1.5萬條，設(shè)置支持度為5。

由表１可知，如果不采用數(shù)據(jù)庫分層的關(guān)聯(lián)規(guī)則挖掘，那么這條對于計(jì)算機(jī)專業(yè)學(xué)生有價(jià)值得事務(wù)就被丟失，而采用基于數(shù)據(jù)庫分層的關(guān)聯(lián)規(guī)則挖掘，則可以為計(jì)算機(jī)專業(yè)的學(xué)生產(chǎn)生有價(jià)值的關(guān)聯(lián)規(guī)則。圖１ 數(shù)據(jù)庫分層結(jié)構(gòu)示意圖

表１ 采用不同方法得出支持度

項(xiàng)目不采用數(shù)據(jù)庫分層的

關(guān)聯(lián)規(guī)則挖掘采用數(shù)據(jù)庫分層的

關(guān)聯(lián)規(guī)則挖掘支持度37.5

２.１.１ 基于多用戶關(guān)聯(lián)規(guī)則的圖書推薦算法

本算法在對多層數(shù)據(jù)庫進(jìn)行關(guān)聯(lián)規(guī)則挖掘時(shí)，采用的是文獻(xiàn)［４］提出的分布式關(guān)聯(lián)規(guī)則挖掘算法，并對其進(jìn)行了一些改動(dòng)。

這里首先介紹基于用戶層次信息的關(guān)聯(lián)規(guī)則圖書推薦挖掘算法步驟如下：

步驟一：根據(jù)讀者的顯性或隱性的層次屬性，采取相關(guān)算法對用戶進(jìn)行合理分層，即生成讀者的層次樹H；

步驟二：根據(jù)用戶的層次樹H，將對應(yīng)的圖書借閱數(shù)據(jù)存放在相應(yīng)的數(shù)據(jù)庫中；

步驟三：為各個(gè)最低層子數(shù)據(jù)庫（葉子節(jié)點(diǎn)數(shù)據(jù)庫）生成1-項(xiàng)集；

步驟四：在任意子數(shù)據(jù)庫DBi中，根據(jù)本地的全局頻繁k-1項(xiàng)集LGk-1，利用公式Cik=apriorigen(LGk-1）生成本地候選頻繁項(xiàng)目集Cik；

步驟五：對于每一個(gè)數(shù)據(jù)集X∈Cik，掃描同一個(gè)父節(jié)點(diǎn)下的每一個(gè)局部數(shù)據(jù)庫DBi，以計(jì)算本地支持度X.support。

步驟六：Cik對進(jìn)行剪枝，如果X在結(jié)點(diǎn)DBi滿足局部闕值，那么將其加入到DBi的頻繁項(xiàng)目集Lik中，否則對其進(jìn)行剪枝；

步驟四：發(fā)送支持?jǐn)?shù)，然后計(jì)算同一父節(jié)點(diǎn)下全局頻繁k項(xiàng)集的總支持?jǐn)?shù)；

步驟五：將同一父節(jié)點(diǎn)下各個(gè)局部數(shù)據(jù)庫DBi的全局頻繁k項(xiàng)集傳給其他同一父節(jié)點(diǎn)下局部數(shù)據(jù)庫DBi(j≠i)；

步驟六：重復(fù)步驟（4）～（5），直到?jīng)]有新的頻繁項(xiàng)集生成；

步驟七：根據(jù)本地最大頻繁項(xiàng)集LGk-1生成關(guān)聯(lián)規(guī)則并存入到當(dāng)前節(jié)點(diǎn)的關(guān)聯(lián)規(guī)則庫中，同時(shí)將本層生成的全局最大頻繁項(xiàng)放入到上一級父節(jié)點(diǎn)當(dāng)中，如果沒有上一層父節(jié)點(diǎn)則算法結(jié)束。

步驟八：將子節(jié)點(diǎn)生成的全局最大頻繁項(xiàng)作為本節(jié)點(diǎn)的事務(wù)數(shù)據(jù)庫，然后重復(fù)步驟（4）～（8）。直到為整個(gè)樹的根節(jié)點(diǎn)生成全局最大頻繁項(xiàng)后，程序結(jié)束。

下面介紹當(dāng)關(guān)聯(lián)規(guī)則算法生成完成后，如何為讀者提供圖書推薦推薦服務(wù)，步驟如下：

步驟一：讀者登錄后根據(jù)讀者基本信息以及讀者上一次借閱信息，在根節(jié)點(diǎn)根據(jù)關(guān)聯(lián)規(guī)則為讀者提供圖書推薦服務(wù)。如果推薦的圖書是讀者需要的圖書，則算法結(jié)束，否則進(jìn)入下一步；

步驟二：根據(jù)讀者分類進(jìn)入到下一子節(jié)點(diǎn)，并在下一結(jié)點(diǎn)中生成的關(guān)聯(lián)規(guī)則為讀者提供圖書推薦服務(wù)，如果推薦的圖書是讀者需要的圖書，則算法結(jié)束，否則根據(jù)讀者分類進(jìn)入下一子節(jié)點(diǎn)，這樣直到整個(gè)用戶樹中的葉子節(jié)點(diǎn)為止。

３ 實(shí)驗(yàn)結(jié)果及分析

為了驗(yàn)證本文提出的基于多用戶層次關(guān)聯(lián)規(guī)則的圖書推薦算法的有效性。本論文針對標(biāo)準(zhǔn)Apriori算法以及本文提出的基于多用戶層次關(guān)聯(lián)規(guī)則的圖書推薦算法進(jìn)行測試，兩種算法均采用標(biāo)準(zhǔn)C#實(shí)現(xiàn)。

３.１ 評測標(biāo)準(zhǔn)

決策支持精度度量是衡量一個(gè)系統(tǒng)的預(yù)測用戶選擇合適項(xiàng)目時(shí)候的準(zhǔn)確程度，這種度量假設(shè)對項(xiàng)目的推薦過程是一個(gè)布爾操作，一個(gè)物品要么被推薦，要么不被推薦。最常見的決策支持精度度量的例子是召回率（Recall）：

ｐｒｅｃｉｓｉｏｎ（Ｒｅｃｓｅｔ）＝Ｒｅｃｓｅｔ∩ＴｅｓｔｂａｃｋＲｅｃｓｅｔ

其中：Recset為推薦集，Testback為測試集。本文用產(chǎn)生的數(shù)據(jù)與測試集之間的差異作為衡量算法的有效性的依據(jù)。

３.２ 數(shù)據(jù)集

本次試驗(yàn)用到的數(shù)據(jù)集是我校圖書館近五年來的圖書借閱數(shù)據(jù)。我們將該數(shù)據(jù)集分為80%和20%兩部分，其中80%作為訓(xùn)練數(shù)據(jù)，而另外20%的數(shù)據(jù)作為測試數(shù)據(jù)。另外本文對數(shù)據(jù)集進(jìn)行了5次不同的劃分，每次劃分產(chǎn)生的不同測試數(shù)據(jù)集，進(jìn)行5折交叉驗(yàn)證。

３.３ 實(shí)驗(yàn)結(jié)果及分析

根據(jù)用戶樹的分層，最大推薦次數(shù)為4，也就是說用葉子節(jié)點(diǎn)中生成的關(guān)聯(lián)規(guī)則給讀者推薦圖書。實(shí)驗(yàn)結(jié)果見實(shí)驗(yàn)結(jié)果見表２。

從表２可以看出，本文提出的用戶層次關(guān)聯(lián)規(guī)則的圖書推薦算法除了對數(shù)據(jù)集4的精確度不如Apriori算法外，其它數(shù)據(jù)集的精確度都高于Apriori算法。表２ Apriori算法和基于用戶層次關(guān)聯(lián)規(guī)則的圖書推薦算法

項(xiàng) 目Apriori算法

（％）用戶層次關(guān)聯(lián)規(guī)則的

圖書推薦算法（％）數(shù)據(jù)集18786.4數(shù)據(jù)集288.685.1 續(xù)表２

項(xiàng) 目Apriori算法

（％）用戶層次關(guān)聯(lián)規(guī)則的

圖書推薦算法（％）數(shù)據(jù)集385.385數(shù)據(jù)集488.188.4數(shù)據(jù)集587.286.3平均準(zhǔn)確度87.2486.24４ 結(jié) 論

關(guān)聯(lián)規(guī)則已經(jīng)普遍存在于機(jī)器學(xué)習(xí)的許多實(shí)際應(yīng)用領(lǐng)域中。如何快速的提高關(guān)聯(lián)規(guī)則的生成算法，同時(shí)有效的給用戶提供推薦物品是目前機(jī)器學(xué)習(xí)的一個(gè)熱點(diǎn)問題。

通過上面的實(shí)驗(yàn)結(jié)果以及理論分析可以得出結(jié)論：本文提出的基于用戶層次關(guān)聯(lián)規(guī)則的圖書推薦算法，有效的提高了基于關(guān)聯(lián)規(guī)則的圖書推薦算法的準(zhǔn)確度。

參考文獻(xiàn)

［１］朱玉全，孫志揮.基于頻繁模式樹的關(guān)聯(lián)規(guī)則增量式更新算法［Ｊ］.計(jì)算機(jī)學(xué)報(bào)，2003，26(1):91－96.

［２］AGRAWAL R，SR1KANT R.Fast algorithms for mining association rules.Proceedings of the 20th International Conference On Very Large Databases［Ｃ］.Santiago，1994:487-499.

［３］Z.Zheng，R.Kohavi，L.Mason，Real World Performance of Association Rule Algorithms， InProc.2001 ACM-SIGKDD Intl.Conf.on Knowledge Discovery and Data Mining，New York，ACM，2001:401-406.

［４］D W Cheung，J W Han，V T Ng et al.A fast distributed algorithm for mining association rules.IEEE 4th Intl Conf on Parallel and Distributed Information Systems，Miami Beach，F(xiàn)lorida，1996．