一種基于用戶層次信息的關聯規則圖書推薦系統

〔摘 要〕關聯規則是數據挖掘的重要模式之一，有著極其重要的應用價值。由于其自身的優點，關聯規則得到了迅速發展，并開始了廣泛應用，然而傳統的關聯規則算法在應用中有很多的不足。因此本文提出了一種基于用戶層次信息的關聯規則圖書推薦系統，實驗結果表明，該算法能夠有效減少運算量，并能提高推薦的準確度。

〔關鍵詞〕關聯規則；圖書推薦；數字圖書館

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

〔中圖分類號〕Ｇ２０２ 〔文獻標識碼〕Ｂ 〔文章編號〕１００８－０８２１（２０１０）１２－００７３－０４

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

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

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

許多學者對關聯規則挖掘進行了大量研究工作。本文在這些研究基礎之上，提出一種改進算法，并將改進的挖掘算法對圖書館流通數據進行挖掘，為讀者提供個性化的圖書推薦信息服務。

本文第二部分闡述關聯規則的基本原理與算法；第三部分介紹基于多用戶關聯規則的圖書推薦算法；第四部分介紹實驗結果；第五部分為結論。

１ 關聯規則的基本原理與算法

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

１.１ 關聯規則基本原理

在介紹關聯規則之前，我們首先介紹幾個相關定義。

定義１：設I=｛I1，I2，…，Im｝是一個項的有限集合，稱為項集；TD是一個事務數據庫，T表示其中的一個事務，有惟一的標識符TID，且有ＴＩ；設ＸＩ，當且僅當ＸＩ時稱事務T支持項集X

定義２：關聯規則表示為：Ｘ＝＞Ｙ的蘊涵式，這里ＸＩ，ＹＩ，并且Ｘ∩Ｙ＝Φ。若規則Ｘ＝＞Ｙ在事物集TD中成立，則關聯規則Ｘ＝＞Ｙ具有支持度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）是包含項集X∪Y的事務數，｜TD｜是數據庫D中所有的事務數，count(X)是包含項集X的事務數。

１.２ 關聯規則基本算法

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

Apriori算法主要包括3個步驟：

１.２.１ 連接步

為找Lk+1，通過Lk與自己連接產生（k+1）-項集的集合。該侯選項的集合記作Ck+1。設li和lj是Lk的項集，li［k］記號表示li的第k項。執行連接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］）是簡單的保證不產生重復。連接li和lj產生的結果項集是：li［1］li［2］…li［k-1］li［k］。

１.２.２ 剪枝步

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

１.２.３ 掃描數據庫

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

２０１０年１２月第３０卷第１２期一種基于用戶層次信息的關聯規則圖書推薦系統Ｄｅｃ.，２０１０２ 基于多用戶關聯規則的圖書推薦算法

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

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

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

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

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

針對以上的問題，本文提出了基于多用戶的關聯規則的圖書推薦系統。

２.１ 多用戶關聯規則的圖書推薦系統

本系統的主要步驟就是首先根據讀者類型將借閱數據分層歸類，并存入到子數據庫中，然后先根據子數據生成局部關聯規則，最后通過分布式關聯規則生成算法生成全局關聯規則。當讀者登陸系統后，系統根據讀者所屬的最高一層子數據庫的借閱規則為讀者推薦書目，如果不滿足讀者需求，進入到下一級子數據庫，根據下一級數據庫的關聯規則為讀者提供圖書推薦服務，直至根數據庫的關聯規則為讀者提供服務。數據庫分層結構示意圖如圖１所示。

其中，最底層數據庫子集稱為葉子節點數據庫，最上一層數據稱為根數據庫。

基于數據庫分層的關聯規則挖掘的優點是，能針對性的給讀者推薦圖書，而且不容易漏掉對讀者有價值的關聯規則。

例如：假設數據庫有流通記錄100萬條，｛計算機網絡，網絡安全｝該事務有3萬條，計算機專業學生借閱記錄中有20萬條，其中包含｛計算機網絡，網絡安全｝事務1.5萬條，設置支持度為5。

由表１可知，如果不采用數據庫分層的關聯規則挖掘，那么這條對于計算機專業學生有價值得事務就被丟失，而采用基于數據庫分層的關聯規則挖掘，則可以為計算機專業的學生產生有價值的關聯規則。圖１ 數據庫分層結構示意圖

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

項目不采用數據庫分層的

關聯規則挖掘采用數據庫分層的

關聯規則挖掘支持度37.5

２.１.１ 基于多用戶關聯規則的圖書推薦算法

本算法在對多層數據庫進行關聯規則挖掘時，采用的是文獻［４］提出的分布式關聯規則挖掘算法，并對其進行了一些改動。

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

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

步驟二：根據用戶的層次樹H，將對應的圖書借閱數據存放在相應的數據庫中；

步驟三：為各個最低層子數據庫（葉子節點數據庫）生成1-項集；

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

步驟五：對于每一個數據集X∈Cik，掃描同一個父節點下的每一個局部數據庫DBi，以計算本地支持度X.support。

步驟六：Cik對進行剪枝，如果X在結點DBi滿足局部闕值，那么將其加入到DBi的頻繁項目集Lik中，否則對其進行剪枝；

步驟四：發送支持數，然后計算同一父節點下全局頻繁k項集的總支持數；

步驟五：將同一父節點下各個局部數據庫DBi的全局頻繁k項集傳給其他同一父節點下局部數據庫DBi(j≠i)；

步驟六：重復步驟（4）～（5），直到沒有新的頻繁項集生成；

步驟七：根據本地最大頻繁項集LGk-1生成關聯規則并存入到當前節點的關聯規則庫中，同時將本層生成的全局最大頻繁項放入到上一級父節點當中，如果沒有上一層父節點則算法結束。

步驟八：將子節點生成的全局最大頻繁項作為本節點的事務數據庫，然后重復步驟（4）～（8）。直到為整個樹的根節點生成全局最大頻繁項后，程序結束。

下面介紹當關聯規則算法生成完成后，如何為讀者提供圖書推薦推薦服務，步驟如下：

步驟一：讀者登錄后根據讀者基本信息以及讀者上一次借閱信息，在根節點根據關聯規則為讀者提供圖書推薦服務。如果推薦的圖書是讀者需要的圖書，則算法結束，否則進入下一步；

步驟二：根據讀者分類進入到下一子節點，并在下一結點中生成的關聯規則為讀者提供圖書推薦服務，如果推薦的圖書是讀者需要的圖書，則算法結束，否則根據讀者分類進入下一子節點，這樣直到整個用戶樹中的葉子節點為止。

３ 實驗結果及分析

為了驗證本文提出的基于多用戶層次關聯規則的圖書推薦算法的有效性。本論文針對標準Apriori算法以及本文提出的基于多用戶層次關聯規則的圖書推薦算法進行測試，兩種算法均采用標準C#實現。

３.１ 評測標準

決策支持精度度量是衡量一個系統的預測用戶選擇合適項目時候的準確程度，這種度量假設對項目的推薦過程是一個布爾操作，一個物品要么被推薦，要么不被推薦。最常見的決策支持精度度量的例子是召回率（Recall）：

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

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

３.２ 數據集

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

３.３ 實驗結果及分析

根據用戶樹的分層，最大推薦次數為4，也就是說用葉子節點中生成的關聯規則給讀者推薦圖書。實驗結果見實驗結果見表２。

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

項 目Apriori算法

（％）用戶層次關聯規則的

圖書推薦算法（％）數據集18786.4數據集288.685.1 續表２

項 目Apriori算法

（％）用戶層次關聯規則的

圖書推薦算法（％）數據集385.385數據集488.188.4數據集587.286.3平均準確度87.2486.24４ 結 論

關聯規則已經普遍存在于機器學習的許多實際應用領域中。如何快速的提高關聯規則的生成算法，同時有效的給用戶提供推薦物品是目前機器學習的一個熱點問題。

通過上面的實驗結果以及理論分析可以得出結論：本文提出的基于用戶層次關聯規則的圖書推薦算法，有效的提高了基于關聯規則的圖書推薦算法的準確度。

參考文獻

［１］朱玉全，孫志揮.基于頻繁模式樹的關聯規則增量式更新算法［Ｊ］.計算機學報，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，Florida，1996．