基于Apriori關(guān)聯(lián)分析與協(xié)同過濾的圖書推薦算法

李文華

摘要：該文根據(jù)圖書借閱數(shù)據(jù)的特點(diǎn)，提出了一種基于Apriori關(guān)聯(lián)分析與協(xié)同過濾推薦算法。對于協(xié)同過濾算法的重要難點(diǎn)是計(jì)算圖書之間的相似性，尤其是在缺乏用戶評分?jǐn)?shù)據(jù)的情況下。該文通過將Apriori關(guān)聯(lián)性算法與協(xié)同過濾推薦算法相結(jié)合，利用圖書之間的關(guān)聯(lián)性來構(gòu)建圖書之間的相似性矩陣，從而解決了在圖書借閱數(shù)據(jù)中缺乏用戶評分的問題，試驗(yàn)結(jié)果表明該文在圖書借閱數(shù)據(jù)集上的推薦準(zhǔn)確率和效率都有較大改善。

關(guān)鍵詞： Apriori；關(guān)聯(lián)分析；協(xié)同過濾；圖書推薦；相似矩陣；圖書借閱

中圖分類號：TP181 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2017）33-0032-02

Abstract： Based on the characteristics of book borrowing data， this paper proposes an algorithm Based on Apriori association analysis and collaborative filtering recommendation. The important difficulty for collaborative filtering algorithms is to calculate the similarity between books， especially in the absence of user rating data. In this paper， the Apriori correlation algorithm and the collaborative filtering recommendation algorithm are combined to construct the similarity matrix between books by using the correlation between the books， which solves the problem of lack of user score in the book borrowing data. The experimental results show that The recommendation accuracy and efficiency of the book borrowing data set have improved greatly.

Key words： apriori； association analysis； collaborative filtering； book recommendation； similar matrix； books borrow

1 概述

近年來，隨著數(shù)據(jù)挖掘領(lǐng)域研究的活躍，數(shù)據(jù)挖掘技術(shù)在各行各業(yè)都得到了廣泛的應(yīng)用。如何有效地利用圖書借閱數(shù)據(jù)來提高圖書管理服務(wù)，是當(dāng)前圖書借閱數(shù)據(jù)挖掘的重點(diǎn)。在圖書管理服務(wù)中，有效的圖書推薦是提高讀者借閱查找效率和讀者借閱體驗(yàn)[1]。在過去的幾年中，協(xié)同過濾推薦算法在商品推薦中得到了廣泛的應(yīng)用，特別是在商品圖書推薦中，例如亞馬遜、當(dāng)當(dāng)、等電子商務(wù)中，都采用了協(xié)同推薦算法來實(shí)現(xiàn)商品推薦[2]。

但是在基于圖書借閱數(shù)據(jù)的協(xié)同推薦中，還存在著一些需要解決的難題。采用協(xié)同過濾算法根據(jù)借閱數(shù)據(jù)進(jìn)行借閱圖書推薦的難點(diǎn)包括以下兩個(gè)方面：

1） 評分?jǐn)?shù)據(jù)的獲取。在商品數(shù)據(jù)推薦中，協(xié)同過濾算法需要使用商品的評價(jià)來對計(jì)算用戶對商品之間的相似度。然而在高校圖書管理系統(tǒng)中，圖書借閱系統(tǒng)很少包括借閱后對圖書的評價(jià)，難以收集圖書評分?jǐn)?shù)據(jù)。這是協(xié)同過濾在圖書借閱數(shù)據(jù)中最大的難點(diǎn)。

2） 相似性度量。在傳統(tǒng)的商品推薦系統(tǒng)中，由于用戶之間很少存在相同的知識背景以及生活場景，所以用戶之間的相似性只能通過對商品的購買來判斷。但是在圖書借閱系統(tǒng)中，特別是高校讀書借閱系統(tǒng)中，借閱用戶通常會具有年齡、專業(yè)以及知識背景等相似性，傳統(tǒng)的商品推薦中的協(xié)同過濾算法并沒有考慮這些相似的背景。

基于以上考慮，本文提出了一種基于Apriori關(guān)聯(lián)分析的協(xié)同過濾圖書推薦算法。通過圖書之間的關(guān)聯(lián)性分析來解決缺乏用戶評分的問題，同時(shí)，通過對數(shù)據(jù)庫的解析，在計(jì)算相似性矩陣時(shí)，嵌入了用戶的背景知識，如：用戶年紀(jì)、年級、專業(yè)、學(xué)院等。本方法在高校圖書借閱數(shù)據(jù)中的測試表明了推薦的有效性。

2 相關(guān)研究

2.1 Apriori關(guān)聯(lián)分析

關(guān)聯(lián)規(guī)則的挖掘最早是應(yīng)用在商品數(shù)據(jù)庫中的挖掘[3-5]，其中最為著名的關(guān)聯(lián)規(guī)則挖掘算法是基于Apriori算法[4-6]。Apriori算法可以快速的挖掘數(shù)據(jù)集合中的頻繁項(xiàng)集，其中頻繁項(xiàng)集指的是數(shù)據(jù)集中出現(xiàn)頻率最高的數(shù)據(jù)項(xiàng)組合，其具體算法流程是：

1） 首先，找出所有1項(xiàng)頻繁集[L1]。

2） 根據(jù)[L1]頻繁項(xiàng)計(jì)算得到候選集[M2]。

3） 根據(jù)新的候選集[M2]得到頻繁集[L2]。

4） 依次迭代，直到得到指定項(xiàng)的頻繁集，最后根據(jù)設(shè)定的最小置信度和頻繁集產(chǎn)生關(guān)聯(lián)規(guī)則。

2.2 協(xié)同過濾

協(xié)同過濾算法[7-9]進(jìn)行推薦是根據(jù)其他用戶的對商品的評論，從而產(chǎn)生對目標(biāo)用戶的推薦列表。協(xié)同過濾的基本假設(shè)是：不同用戶對項(xiàng)目的評分相似，那么他們對其他相似項(xiàng)目的評價(jià)也比較相似?；趨f(xié)同過濾系統(tǒng)的推薦算法主要是通過統(tǒng)計(jì)技術(shù)來尋找目標(biāo)用戶的最近鄰鄰居，然后從鄰居相似的列表中產(chǎn)生推薦列表。在協(xié)同過濾算法中最重要的是找到目標(biāo)用戶的最近鄰居，必須度量用戶之間的相似性，然后選擇相似性最高的若干用戶作為目標(biāo)用戶的最近鄰居。目標(biāo)用戶的最近鄰居查詢是否準(zhǔn)確，直接關(guān)系到整個(gè)推薦系統(tǒng)的推薦質(zhì)量.準(zhǔn)確查詢目標(biāo)用戶的最近鄰居是整個(gè)協(xié)同過濾推薦成功的關(guān)鍵。

在協(xié)同過濾算法中，用戶評分?jǐn)?shù)據(jù)可以用[m×n]階矩陣[A（m，n）]表示， m行代表m個(gè)用戶，n列代表n個(gè)項(xiàng)目，第i行第j列的[Rij]代表用戶i對項(xiàng)目j的評分。用戶評分?jǐn)?shù)據(jù)矩陣如表1所示。度量用戶i和用戶j之間相似性的方法是，首先得到經(jīng)用戶i和用戶j評分的所有項(xiàng)目，然后通過不同的相似性度量方法計(jì)算用戶i和用戶j之間的相似性，記為sim（i，j）。

基于協(xié)同過濾推薦算法的核心是構(gòu)建用戶之間的相似性矩陣，在商品推薦系統(tǒng)中，用戶之間的相似性是通過用戶對商品的評價(jià)來計(jì)算。然而在圖書借閱記錄數(shù)據(jù)中，讀者很少會對圖書進(jìn)行評分，因此，在利用借閱數(shù)據(jù)進(jìn)行圖書推薦時(shí)，需要提出新的相似性度量方法以便構(gòu)建借閱用戶之間的相似性矩陣。

3 基于關(guān)聯(lián)分析的協(xié)同過濾推薦算法

為了根據(jù)借閱數(shù)據(jù)來實(shí)現(xiàn)借閱圖書推薦，首先需要解決的問題是如何定義借閱用戶之間的相似性。因此基于關(guān)聯(lián)分析的協(xié)同過濾推薦算法主要是通過圖書關(guān)聯(lián)來構(gòu)建圖書相似性矩陣，從而進(jìn)一步實(shí)現(xiàn)圖書推薦。通過對圖書館的借閱數(shù)據(jù)的分析，可知，在圖書卡的信息中包含了兩部分信息，一是學(xué)生的基本信息，如年級、專業(yè)、出生日期、性別等；二是學(xué)生的書籍借閱歷史信息。通常，我們可以根據(jù)學(xué)生之間的基本信息快速的定義學(xué)生之間的相似性矩陣，但是這種相似性定義僅僅只考慮了學(xué)生的基本信息，并沒有考慮學(xué)生之間借閱相似性進(jìn)行。因此，在本文中，提出了一種基于關(guān)聯(lián)分析的協(xié)同過濾借閱圖書推薦算法。其算法的核心思想是通過對借閱數(shù)據(jù)中頻繁項(xiàng)集的挖掘來定義學(xué)生之間對圖書的興趣，并基于此構(gòu)建學(xué)生之間的相似性矩陣。算法的流程基本流程如下：

1） 首先分別根據(jù)圖書的借閱數(shù)據(jù)進(jìn)行圖書之間的關(guān)聯(lián)性挖掘，得到2項(xiàng)集頻繁集置信度。

2） 從借閱數(shù)據(jù)中，提取學(xué)生專業(yè)、年紀(jì)等屬性信息，并向量化。

3） 利用圖書之間的關(guān)聯(lián)性與基本信息之間的相似性，構(gòu)建相似性矩陣。

4） 根據(jù)相似性矩陣查找目標(biāo)用戶的最近鄰。

5） 根據(jù)目標(biāo)用戶最近鄰，生成圖書推薦列表。

在本算法中，最為關(guān)鍵的兩點(diǎn)是如何利用圖書關(guān)聯(lián)性來構(gòu)建相似性矩陣，以及如何定義用戶之間的相似性。對于用戶來說，相似性可以根據(jù)用戶的屬性信息來定義，用戶的相似性定義如下：

[SimUseri，Userj=Majori， Agei，Sexi，Gradei×Majorj， Agej，Sexj，Gradej] （1）

對于圖書相似性，可以通過挖掘圖書之間的關(guān)聯(lián)性來進(jìn)行定義。例如在圖書集合[B={B1，B2，B3，B4，B5}]中，通過關(guān)聯(lián)分析可以得到圖書之間的被同時(shí)借閱的頻率，基于此我們即可構(gòu)建圖書的相似性矩陣。圖書相似性矩陣定義，如存在圖書[Bi，Bj]，其中由關(guān)聯(lián)挖掘得到的2-項(xiàng)支持度，定義為：

[AssociationBi，Bj=Sup（Bi，Bj）Max（Bi，Bj）] （2）

采用式（2）中的關(guān)聯(lián)度來定義相似性會存在一個(gè)問題，通過對數(shù)據(jù)庫中的數(shù)據(jù)挖掘可知，在大部分的圖書之間沒有被同時(shí)借閱過，因此，這會造成相似矩陣過于稀疏，不利于進(jìn)一步進(jìn)行協(xié)同過濾算法。為了解決該問題，在度量圖書相似度時(shí)，本文還引入了常見的圖書屬性，例如書名、分類、出版年限等。對于圖書[Bi=α1，α2，…αn，Bj={β1，β2，…，βn}]，其矩陣相似度

[EuclideanBi，Bj=（α1-β1）2+ （α2-β1）2+（αn-βn）2] （3）

由圖書之間的關(guān)聯(lián)性和圖書屬性之間的相似性我們可以定義圖書之間的相似度如式（4）所示：

[SimBi，Bj=α*EuclideanBi，Bj+1-α*EuclideanBi，Bj] （4）

其中[α]用來控制在相似性屬性中屬性距離和關(guān)聯(lián)性所占的比重，在實(shí)際推薦中可以對其進(jìn)行調(diào)節(jié)。

下面以表2為例，假設(shè)歷史借閱數(shù)據(jù)如表2所示，當(dāng)需要對新的借閱用戶進(jìn)行圖書推薦時(shí)，首先通過式（1）得到該用戶的最近的幾個(gè)相似性鄰居用戶，然后查找得到鄰居用戶的借閱圖書記錄。再將這些圖書數(shù)據(jù)與該用戶的借閱圖書記錄根據(jù)式（4）計(jì)算得到圖書之間的相似性，并排序，并將排序的[Topk]推薦給該用戶。

4 實(shí)驗(yàn)與結(jié)果

對于一個(gè)推薦算法來說，首先需要驗(yàn)證的是其推薦結(jié)果的有效性。在試驗(yàn)中，通過將本文提出的算法與基于K-means聚類算法以及基于模糊聚類（FCM）的協(xié)同推薦算法進(jìn)行了對比。

在本文中，我們通過將已有的9000條借閱數(shù)據(jù)，隨機(jī)分成了3份，采用3交叉驗(yàn)證方法對算法進(jìn)行了對比。對于，每個(gè)算法，我們將3000條數(shù)據(jù)算作歷史數(shù)據(jù)，其余6000條數(shù)據(jù)進(jìn)行測試，計(jì)算并比較算法的推薦準(zhǔn)確率。其中推薦準(zhǔn)確率定義如式（6）所示：

[Precision= 推薦準(zhǔn)確圖書數(shù)目總借閱圖書數(shù)] （6）

3組實(shí)驗(yàn)結(jié)果統(tǒng)計(jì)如表3所示：

從實(shí)驗(yàn)結(jié)果對比可以看到，本文提出的算法在推薦準(zhǔn)確率上有了較為顯著的提高，一方面是由于本文通過關(guān)聯(lián)分析增加了圖書相似性的屬性，另一方面是由于考慮了學(xué)生之間的屬性，增加了推薦算法的針對性，從而提高了算法的準(zhǔn)確率。

5 結(jié)論

本文提出了一種基于Apriori關(guān)聯(lián)分析算法的協(xié)同過濾推薦算法。在本文中，通過對圖書之間關(guān)聯(lián)性的分析，提出了一種基于關(guān)聯(lián)分析的相似性計(jì)算方法，并應(yīng)用它將協(xié)同過濾算法應(yīng)用到圖書借閱推薦中來。與K-means以及FCM算法的結(jié)果對比，可知本文提出的方法在推薦準(zhǔn)確率上得到了顯著的提高。

參考文獻(xiàn)：

[1] 趙祖應(yīng)， 丁勇， 鄧平. 基于Apriori算法的購物籃關(guān)聯(lián)規(guī)則分析[J]. 江西科學(xué)， 2012， 30（1）：96-98.

[2] 焦亞琴， 劉曉云， 張銀葉. 基于Mahout的個(gè)性化電子商務(wù)推薦系統(tǒng)研究[J]. 電腦知識與技術(shù)， 2015（4X）：261-264.

[3] 周發(fā)超， 王志堅(jiān)， 葉楓，等. 關(guān)聯(lián)規(guī)則挖掘算法Apriori的研究改進(jìn)[J]. 計(jì)算機(jī)科學(xué)與探索， 2015， 9（9）：1075-1083.

[4] 張啟徽. 關(guān)聯(lián)規(guī)則挖掘中查找頻繁項(xiàng)集的改進(jìn)算法[J]. 統(tǒng)計(jì)與決策， 2015（4）：32-35.

[5] 李仕瓊. 數(shù)據(jù)挖掘中關(guān)聯(lián)規(guī)則挖掘算法的分析研[J]. 電子技術(shù)與軟件工程， 2015（4）：200-200.

[6] 陳方健， 張明新， 楊昆. 一種具有跳躍式前進(jìn)的Apriori算法[J]. 計(jì)算機(jī)應(yīng)用與軟件， 2015（3）：34-36.

[7] 吳月萍， 鄭建國. 協(xié)同過濾推薦算法[J]. 計(jì)算機(jī)工程與設(shè)計(jì)， 2011，32（9）：3019-3021.

[8] 張光衛(wèi)， 李德毅， 李鵬，等. 基于云模型的協(xié)同過濾推薦算法[J].軟件學(xué)報(bào)， 2007，18（10）：2403-2411.

[9] 黃創(chuàng)光， 印鑒， 汪靜，等. 不確定近鄰的協(xié)同過濾推薦算法[J].計(jì)算機(jī)學(xué)報(bào)， 2010，33（8）：1369-1377.