基于關聯規則和協同過濾的混合圖書推薦算法

游卓霖++周翔

摘 要：文章結合關聯規則挖掘和協同過濾算法的特點，根據圖書館的實際情況，提出了混合圖書推薦算法。將該算法應用于廣大圖書管理系統中，有助于提高用戶體驗。

關鍵詞：關聯規則；協同過濾；圖書推薦

中圖分類號：TP391.3 文獻標識碼：A

一、引言

現如今，應用大數據技術已成為時代的主流，但海量的數據能給我們提供什么呢？答案是信息，而且是有價值的信息，能使我們提高工作效率。以圖書館為例，傳統圖書館管理系統中不僅有大量圖書信息、用戶信息，也有許多借閱者的借閱信息，這就帶來一個問題，這么多借閱信息能帶來什么好處？通過數據挖掘，我們就能從中很容易發現用戶的一些興趣偏好，并以此為依據，向用戶推薦他/她可能感興趣的書籍。

二、現狀

推薦系統運用十分廣泛，最常見的可能就是電商網站上的推薦系統。國內如阿里旗下的淘寶、天貓等購物網站，同時網易云音樂在推薦系統方面也建樹頗豐，往往能向用戶推薦可滿足其喜好的音樂。在圖書推薦領域，國內外專家學者在其作品中也有涉及。如吉林大學李欣弘發表的《基于關聯規則和情感分析的圖書 推薦算法研究》中就介紹了利用關聯規則和情感分析算法實現圖書推薦，F.Heylighen的“Hebbian algorithms for a digital library recommandation system”等。但是相對其他領域，推薦算法在圖書推薦方面的應用還是相對較少的。

三、關鍵技術介紹

1.基于KNN的協同過濾推薦算法

鄰居模型通常又稱為KNN模型（K-nearest neighbors），KNN算法的核心思想是：如果一個樣本在特征空間中的k個最相鄰的樣本中的大多數屬于某一個類別，則該樣本也屬于這個類別，并具有這個類別上樣本的特性。該方法在確定分類決策上只依據最鄰近的一個或者幾個樣本的類別來決定待分樣本所屬的類別。采用 KNN方法進行類別決策時，只與極少量的相鄰樣本有關。相關性的計算本例中使用的是Pearson相關系數。Pearson相關系數考慮到不同用戶的評分尺度問題，將同一個用戶對不同的項目評分進行歸一化的處理，這樣就可消除因由用戶個人主觀因素而造成的對相似性結果的影響。結合本例Pearson相關系數公式如下：

sim（i，j）=

sim（i，j）表示書本i和j的相似度，Pmn表示對書m、n都評過分的用戶集合rm，rn，分別表示書m和n的平均評分，分別表示用戶v對書本m、n的評分。

2.關聯規則

（1）關聯分析（Association Analysis）

用于發現隱藏在大型數據集中的令人感興趣的聯系，所以發現的模式通常為關聯規則（Association Rule），或以頻繁項集的形式表示。

Apriori算法是關聯規則挖掘中最常用的算法，在介紹Apriori算法之前要首先了解何謂先驗原理。先驗原理是減少候選集數量的方法之一，其核心思想是：如果一個項集是頻繁的，則它的所有子集一定也是頻繁的；反之，如果一個項集是非頻繁的，那么它的所有超集一定也是非頻繁的。Apriori算法正是運用這一性質。算法的主要步驟主要由連接步和剪枝步組成。這里不再描述連接步和剪枝步的具體實施步驟。不過Apriori算法存在一定的缺陷，如會產生龐大的候選集；多次掃描事務數據庫時，需要很大的I/O負載。為此Jiawei Han等于2000年提出了不產生候選挖掘頻繁項集的方法——頻繁模式增長（Frequent-Pattern Growth，FP-Growth）算法。該算法通過把頻繁項集的數據庫壓縮到一棵頻繁模式樹上，然后將這個壓縮后的數據庫劃分成一組條件數據庫并分別挖掘每個條件數據庫，實驗證明，采用這種方法可以克服改正數據集過大的缺點。

四、圖書推薦的實現

1.目前圖書推薦方面存在的問題

（1）KNN協同過濾算法相似度計算依賴共同評分的項目，對數據集的大小或者說數據的稀疏程度特別敏感，數據集數量越大，往往推薦的結果越精確，但系統剛上線時，往往數據較少，這時如果使用KNN協同過濾算法計算推薦的書籍時，結果可能不盡如人意。

（2）新用戶的問題。其實和第一個問題類似，主要是新用戶可能沒有借閱過相應的書籍，或者借閱的數量太少，盲目使用KNN協同過濾推薦算法時并不會產生很好的結果。

（3）用戶口味的變化。比如，某位讀者可能以前經常看同一類書籍，例如，讀者平常都會借閱一些與計算機相關的書籍，可是有一天該讀者突然想看一本小說，就借了一本小說，期間讀者可能還想再看其他小說類的書籍。這時運用算法進行推薦時，產生的推薦可能還會是計算機方面的書籍居多，這樣的結果就不會準確。

2.針對以上問題，我們可以將兩種算法適當做點改變并加以應用

首先，用關聯規則算法挖掘圖書與圖書之間的關聯程度，找出強關聯。這可能需要大量的數據進行模型訓練，所以，初期的數據集可以來源于網絡或者其他資源，這樣就產生了一個巨大的關聯規則庫，初期的用戶圖書推薦就可以使用這個關聯規則庫。例如用戶A的借閱記錄集合為{A，C，D，F，G}，關聯規則庫{{A=>B}，{D，F=>Z}，...etc}，這時候就可以把書B和書Z推薦給用戶A。隨著用戶借閱記錄的增多，關聯規則庫也會逐漸豐富，借閱數據達到一定量時，可以挖掘符合本管借閱者的借閱習慣的關聯規則庫。關聯規則挖掘所需的時間較長，規則庫的更新可以考慮每周更新或者每月更新。

其次，使用KNN協同過濾算法可用于實時在線的推薦，即推薦的書籍會根據用戶的借閱記錄改變而改變。這里又涉及一個問題，就是用戶喜好突然發生改變，數據中可表示為近期的借閱記錄的圖書的種類與以往借閱圖書的種類產生了區別，其實這種喜好變化也很難界定，因此每個人的借閱習慣不同。但我們可以大概猜測到最近的借閱記錄一般對推薦書籍的影響比較大。二八定律可以解釋生活中的一些現象，在這里我們也同樣可以運用。一般來說，最近借閱的書籍對近期可能想看的書籍的影響程度是80%，而之前看的書可就只有20%。通過應用二八定律我們可以這么界定，假設用戶A的借閱記錄如下{計算機類書A，計算機類書B，計算機類書C}，假設用戶A近期突然借閱了一本文學類書D，那么用戶A的借閱記錄就可以表示成{計算機類書A，計算機類書B，計算機類書C，文學類書D}，那么接下來用戶A可能就有80%的可能還想借文學類的書來看，產生推薦結果時，也可以有80%的書籍是屬于與文學類書籍D強關聯的書，或者至少文學類的叢書應占大多數，這個問題的解決方案后文有闡述。

考慮到實時推薦，響應的時間往往是決定性因素，為了減少響應的時間，應該對數據集進行精簡。圖書的分類是個很好的切入點，根據中圖分類法，書籍分為五個基本部類及下設的二十二個大類，不用通過實驗計算，從理論上就可以知道一本相似的圖書也應該是屬于它所在的分類，或者在父分類、子分類里。例如，讀者借閱的是一本小說類書籍，則認為推薦給該讀者的書籍也一般是小說類。所以可以先從小說這個分類底下的所有叢書中尋找相似的圖書。如果找不到適合的可推薦的書籍，則再從子分類中查找。如果圖中小說分類底下沒有子分類，則從父分類中進行查找，即從中國文學這個分類下查找，以此類推，一般來說父級的父級類別下的書與當前書的相關性也不高。相似程度從大到小可以分為：當前分類>子分類>父分類。

通過這種方式，可以大大縮短尋找可能推薦書籍的時間。

是否可進行推薦，主要是預測用戶對這本書可能的評分，如果大于一個閾值，則可進行推薦。公式如下：

其中為用戶對書籍ru，m的（預測）評分，Smn為書籍m和書籍n的相似度，ru，n是用戶對書籍n的評分，書籍n的選擇就是運用到了KNN算法找到的和書本m相似的k個“鄰居”之一。采用該算法得出的結論其實往往并不是用戶真實想得到的，為此，我們提出了兩個場景的假設。場景1：讀者讀書的喜好的變化不大，都是在一個類別下面的書，即新借閱的書籍的類型和以往的書籍基本類似。場景2：讀者讀書興趣比較廣泛，新借閱的書籍往往和近一段時間所借閱的書籍的類型不同，可能之前有借閱過，也有可能之前并沒有借閱過。

針對以上兩個場景，可以靈活運用這兩個算法：針對場景1，在數據量足夠大的前提下，可以使用KNN協同過濾算法進行推薦。該算法很重要的一點，是在預測一本書可能的評分時，會去尋找讀者借閱記錄中與該本書相似的書，如果讀者的讀書喜好變化不大，則找到的“鄰居”就足夠多，計算結果也就更加準確。而場景2，則采用關聯規則即可。關聯規則算法彌補了傳統協同過濾算法的不足。如遇到數據集的稀疏性和冷啟動問題，同時針對場景2和上文遺留下的問題，如果發現用戶的喜好發生了改變，應用二八定律，80%的書本可以為最近剛借閱的書的類似書本，20%為以前借閱的書籍的類似書。

最后，同時對關聯規則加以挖掘，采用Apriori算法可以產生關聯規則，也可使用FP-Growth算法，兩者各有優缺點，可根據實際情況進行選擇；不過在如此大規模數據量的情況下，FP-Growth算法的效率可能會更高。

五、結語

本文主要介紹了關聯規則和協同過濾算法在圖書推薦方面的應用，在圖書應用方面，我們可以巧妙運用圖書分類的特點，縮小候選圖書集，從而提高圖書推薦的效率，因而可以運用于實時圖書推薦方面。此外，關聯規則挖掘可以發據一些潛在的、不容易讓人察覺的聯系。本文所闡述的推薦方法還有待優化，以實現目標。

參考文獻：

[1]賀嘉楠，董立巖.基于權重調節的矩陣補全協同過濾算法的研究[D].長春：吉林大學，2016

[2]梁亞聲，徐 欣.數據挖掘原理、算法與應用[M].北京：機械工業出版社，2015.

[3]汪 靜.一種基于混合推薦模式的圖書推薦系統[J].計算機光盤軟件與應用，2014（11）.

[4]王雪梅.基于混合協同過濾推薦的圖書館管理系統設計與實現[D].秦皇島：燕山大學，2015.