彭 虎 楊迎方 鄧長(zhǎng)壽

(九江學(xué)院信息科學(xué)與技術(shù)學(xué)院 江西九江 332005)

1 概述

隨著互聯(lián)網(wǎng)及硬件的發(fā)展，數(shù)據(jù)量呈現(xiàn)出幾何式增長(zhǎng)的趨勢(shì)[1]，從而加速了大數(shù)據(jù)人工智能時(shí)代的到來。其中，“數(shù)字化圖書館個(gè)性化服務(wù)”的概念逐漸被提出，讀者對(duì)新書推薦等個(gè)性化服務(wù)產(chǎn)生了更大的需求[2-3]。目前熱門的在線圖書網(wǎng)站中，亞馬遜能針對(duì)特定用戶提供不同的新書籍推薦明細(xì)[4]，而豆瓣圖書利用挖掘算法向讀者提供Top250類的圖書推薦榜單[5]。毫無疑問，個(gè)性化推薦技術(shù)在當(dāng)前的圖書推薦領(lǐng)域仍有著廣闊的研究前景。

當(dāng)前的個(gè)性化推薦領(lǐng)域中，協(xié)同過濾是其中發(fā)展較為成熟的一種推薦算法，但也不可避免地存在冷啟動(dòng)、稀疏性及可擴(kuò)展性等一系列關(guān)鍵性問題[6]。對(duì)于稀疏性問題，由于協(xié)同過濾主要依據(jù)為用戶對(duì)項(xiàng)目的偏好信息，而用戶僅僅評(píng)價(jià)少量項(xiàng)目就會(huì)導(dǎo)致用戶-項(xiàng)目偏好矩陣成為高維稀疏矩陣，從而導(dǎo)致推薦精度下降。對(duì)于可擴(kuò)展性問題，隨著用戶和項(xiàng)目的基數(shù)不斷擴(kuò)大，用戶-項(xiàng)目偏好矩陣規(guī)模龐大，算法進(jìn)行相似度計(jì)算和預(yù)測(cè)評(píng)分的工作量急劇增加，導(dǎo)致實(shí)時(shí)性下降。而當(dāng)用戶數(shù)據(jù)的時(shí)間跨度較大時(shí)仍對(duì)所有用戶偏好信息等同對(duì)待，顯然不是合理的推薦方式，忽視了新書推薦的時(shí)效性[7]。毫無疑問，對(duì)用戶偏好數(shù)據(jù)的正確使用，有助于提高協(xié)同過濾在新書推薦場(chǎng)景中的推薦質(zhì)量。

因此，文章提出了一種基于相似度傳播和時(shí)間綜合權(quán)重的協(xié)同過濾新書推薦算法，依據(jù)數(shù)據(jù)量劃分三個(gè)數(shù)據(jù)階段，不同階段動(dòng)態(tài)選擇適合的推薦方案，在相似度計(jì)算中采用傳播思想以解決稀疏性問題，引入時(shí)間綜合權(quán)重以應(yīng)對(duì)可擴(kuò)展性問題并提高推薦的時(shí)效性，具有重要的理論與實(shí)踐意義。

2 協(xié)同過濾

2.1 協(xié)同過濾算法

協(xié)同過濾(collaborative filtering，CF)是一種利用集體智慧的經(jīng)典方法，即在用戶群中找到與目標(biāo)用戶有著相似興趣和偏好的用戶，綜合相似用戶的偏好信息對(duì)目標(biāo)用戶進(jìn)行喜好程度預(yù)測(cè)，并進(jìn)一步為目標(biāo)用戶提供推薦。協(xié)同過濾一般可分為兩大類：

(1)基于內(nèi)存的協(xié)同過濾。數(shù)據(jù)量較小的應(yīng)用場(chǎng)景下，采取直接在線使用的實(shí)時(shí)推薦方法。一般又分為基于用戶的協(xié)同過濾和基于項(xiàng)目的協(xié)同過濾，這兩種推薦算法目前在實(shí)際應(yīng)用中得到了最廣泛的使用。

(2)基于模型的協(xié)同過濾。依據(jù)歷史數(shù)據(jù)得到模型，并依據(jù)模型進(jìn)行預(yù)測(cè)評(píng)分。一般又分為聚類、關(guān)聯(lián)規(guī)則、貝葉斯網(wǎng)絡(luò)和機(jī)器學(xué)習(xí)分類等。

2.2 協(xié)同過濾原理

協(xié)同過濾能為不同對(duì)象進(jìn)行推薦，且不受數(shù)據(jù)格式的影響，例如圖書、音樂、電影等難以處理的復(fù)雜數(shù)據(jù)都可以進(jìn)行推薦,并且能夠挖掘出用戶的潛在興趣，生成的推薦具有較高價(jià)值?；驹砣缦拢?/p>

(1)收集用戶偏好。用戶的偏好分為顯性和隱性收集，顯性如評(píng)分、評(píng)論、投票，隱性如購(gòu)買、查看等。在收集用戶行為數(shù)據(jù)后，需要對(duì)數(shù)據(jù)進(jìn)行處理，得到一個(gè)反映用戶偏好的二維矩陣，一維是用戶列表，另一維是項(xiàng)目列表，值為用戶對(duì)項(xiàng)目的偏好信息。

(2)尋找相似鄰居。相似度計(jì)算是協(xié)同過濾的核心，傳統(tǒng)的測(cè)算距離方法主要有：基于相關(guān)系數(shù)的相似度、基于余弦相似度以及基于調(diào)整的余弦相似度等。

(3)生成推薦集，具體表現(xiàn)形式為預(yù)測(cè)推薦或TOP-N推薦。其中，預(yù)測(cè)推薦為產(chǎn)生一個(gè)預(yù)測(cè)評(píng)分值Rui，表示目標(biāo)用戶u對(duì)目標(biāo)項(xiàng)目i的預(yù)測(cè)評(píng)分值。而TOP-N推薦為產(chǎn)生一個(gè)目標(biāo)用戶最喜歡的N個(gè)項(xiàng)目集合，表示目標(biāo)用戶未訪問的項(xiàng)目中值得推薦的項(xiàng)目列表。

2.3 基于用戶的協(xié)同過濾

盡管協(xié)同過濾種類繁多，但目前應(yīng)用最廣泛的仍然是基于內(nèi)存的協(xié)同過濾，以下介紹具體的基于用戶和基于項(xiàng)目的協(xié)同過濾算法原理。

基于用戶的協(xié)同過濾算法的基本原理是：根據(jù)用戶偏好信息，尋找與目標(biāo)用戶興趣相似的最近鄰居用戶，依據(jù)相似鄰居用戶的偏好信息，為目標(biāo)用戶提供個(gè)性化推薦。

算法步驟如下：

輸入 目標(biāo)用戶u、用戶-項(xiàng)目偏好矩陣R。

輸出 目標(biāo)用戶u的Top-N推薦集。

Step1 使用用戶-項(xiàng)目偏好矩陣R以及選定的相似度計(jì)算方法，計(jì)算用戶u和其他用戶之間的相似度矩陣S。

Step2 根據(jù)得到的相似度矩陣S，為用戶u選擇k個(gè)最相近的相似近鄰，建立相似近鄰集合N={u1，u2，u3，……，uk}，及相應(yīng)的相似度Sim={s1，s2，…，sk}。

Step3 對(duì)目標(biāo)用戶u和所有相似近鄰ui∈N，找出u的已評(píng)分項(xiàng)目集Iu和相似鄰居的項(xiàng)目集Ii，將所有Ii取并集；然后去掉Ii中在Iu已存在的項(xiàng)目，生成候選推薦集C。

Step4 對(duì)候選推薦集?j∈C，使用加權(quán)平均算法預(yù)測(cè)用戶u的評(píng)分Ruj。

Step5 采用Top_N形式推薦，按預(yù)測(cè)評(píng)分降序排列，選擇前N個(gè)項(xiàng)目作為推薦。

2.4 基于項(xiàng)目的協(xié)同過濾

基于項(xiàng)目的協(xié)同過濾的基本原理是：綜合用戶對(duì)項(xiàng)目的偏好信息，得到項(xiàng)目之間的相似性，進(jìn)一步依據(jù)目標(biāo)用戶的歷史偏好信息，將類似的項(xiàng)目推薦給用戶。

算法步驟如下：

輸入 目標(biāo)用戶u、用戶-項(xiàng)目偏好矩陣R。

輸出 目標(biāo)用戶u的Top-N推薦集。

Step1 使用用戶-項(xiàng)目偏好矩陣R以及選定的相似度計(jì)算方法，計(jì)算項(xiàng)目間的相似度矩陣S。

Step2 找出用戶u的已評(píng)分項(xiàng)目集Iu，對(duì)所有已評(píng)分項(xiàng)目i∈Iu讀取S得到該項(xiàng)目的K最近鄰居集Ni={i1，i2，……，ik}，合并所有Ni并從中刪除Iu中已經(jīng)存在的項(xiàng)目，得到候選推薦集C。

Step3 對(duì)所有項(xiàng)目j∈C，在Iu中為該項(xiàng)目選擇相似近鄰，然后預(yù)測(cè)用戶u對(duì)該項(xiàng)目的評(píng)分。

Step4 采用Top_N形式推薦，按預(yù)測(cè)評(píng)分降序排列，選擇前N個(gè)項(xiàng)目作為推薦。

3 基于傳播和時(shí)間權(quán)重的協(xié)同過濾算法

研究表明，協(xié)同過濾相比其它推薦算法在新書推薦中有較大優(yōu)勢(shì)，但還是存在稀疏性和可擴(kuò)展性等問題，并且單一的協(xié)同過濾推薦難以適用于復(fù)雜的圖書推薦應(yīng)用場(chǎng)景。因此，對(duì)協(xié)同過濾的改進(jìn)，有助于提高新書推薦算法的推薦質(zhì)量。

文章提出一種基于相似度傳播和時(shí)間綜合權(quán)重的協(xié)同過濾(collaborative filtering based on similarity propagation and time comprehensive weight，PTCF)，算法根據(jù)讀者的偏好數(shù)據(jù)量劃分三個(gè)數(shù)據(jù)階段，不同階段可動(dòng)態(tài)選擇適合的推薦方案，將傳播的思想應(yīng)用于相似度計(jì)算以解決稀疏性問題，并引入時(shí)間綜合權(quán)重以應(yīng)對(duì)可擴(kuò)展性問題并提高新書推薦的時(shí)效性[8]。改進(jìn)算法的核心原理如下：

3.1 初始階段

初始階段是指讀者作為新用戶剛剛進(jìn)入推薦系統(tǒng)的階段，在這一階段讀者的訪問記錄為零或接近于零，因而新書推薦受到冷啟動(dòng)問題的影響[9]。顯然，這一階段使用傳統(tǒng)的基于內(nèi)存協(xié)同過濾并不合適，由于用戶偏好信息的匱乏，新書推薦結(jié)果的可靠性較低。

因此，初始推薦采用評(píng)分最優(yōu)的推薦方案，由讀者尚未閱讀的圖書生成候選推薦集，再匯總每本圖書的平均評(píng)分作為該圖書的預(yù)測(cè)評(píng)分值，最終以Top_N形式推薦給目標(biāo)讀者[10]。

3.2 稀疏階段

稀疏階段是指讀者的偏好信息數(shù)據(jù)已初具規(guī)模，但用戶-項(xiàng)目評(píng)分矩陣仍具有較大的稀疏性，使用一般性的基于內(nèi)存協(xié)同過濾推薦效率有限，新書推薦結(jié)果的可信度難以保證[11]。目前，對(duì)于稀疏性問題的解決方法主要是填充用戶-項(xiàng)目偏好矩陣，該種方法盡管有效，但是在實(shí)際應(yīng)用中的效率一般[12-14]。

因此，稀疏推薦將傳播的思想應(yīng)用到相似度計(jì)算中，即充分利用目標(biāo)用戶的近鄰以及近鄰的相似鄰居的偏好信息為用戶進(jìn)行新書推薦[15]。核心的相似度傳播技術(shù)具體如下：

表1是稀疏的二維矩陣，若采用基于用戶的協(xié)同過濾為用戶u1推薦，則先找到u1相似鄰居u3，然后根據(jù)u3的評(píng)分計(jì)算u1對(duì)i5的預(yù)測(cè)評(píng)分，顯然，由于鄰居個(gè)數(shù)及數(shù)據(jù)稀少會(huì)導(dǎo)致推薦精度較低。引入的傳播思想是，進(jìn)一步找到u3的相似鄰居u1和u5，再同時(shí)把u3和u5的數(shù)據(jù)用到對(duì)u1的評(píng)分預(yù)測(cè)和推薦上，能夠有效提高推薦效率[16]。

表1 用戶-項(xiàng)目偏好稀疏矩陣

根據(jù)上述的相似度傳播思想，文章在相似度計(jì)算上，分別給出了用戶u和用戶v的相似度計(jì)算以及項(xiàng)目i和項(xiàng)目j的相似度計(jì)算的公式。

Sims(u,v)(h+1)=

(1)

Sims(i,j)(h+1)=

(2)

其中，C(0

對(duì)于推薦過程，稀疏推薦從基于用戶和基于項(xiàng)目?jī)煞矫孢M(jìn)行考慮，以下為用戶u對(duì)項(xiàng)目i的預(yù)測(cè)評(píng)分Pre_Rui的計(jì)算公式。

Pre_Rui(h)=

(3)

3.3 豐富階段

豐富階段即在一定的時(shí)間跨度下，讀者的偏好信息數(shù)據(jù)較為豐富，能夠支持推薦運(yùn)算的用戶-項(xiàng)目偏好矩陣規(guī)模龐大。一方面，大量的偏好信息有助于提高新書推薦的效率，但過量的讀者及圖書基數(shù)必然帶來可擴(kuò)展性問題。另一方面，當(dāng)時(shí)間跨度較大時(shí)，用戶的實(shí)際興趣可能發(fā)生動(dòng)態(tài)地變化，不同時(shí)間段的偏好數(shù)據(jù)對(duì)于預(yù)測(cè)讀者興趣的價(jià)值不一致，等同對(duì)待所有偏好數(shù)據(jù)在推薦中的作用會(huì)忽視了推薦的時(shí)效性。因此，充分考慮時(shí)間特征，有助于應(yīng)對(duì)可擴(kuò)展性問題，提高新書推薦的時(shí)效性[17]。

基于以上，豐富推薦引入了一個(gè)基于時(shí)間和基于項(xiàng)目相似度的綜合權(quán)重TS(u，i)，表示用戶u對(duì)已訪問項(xiàng)目i的的興趣相關(guān)度[18]。

定義1 基于時(shí)間的數(shù)據(jù)權(quán)重。近期的用戶數(shù)據(jù)更能反映用戶的近期興趣，而早期的用戶數(shù)據(jù)對(duì)于推薦的價(jià)值相對(duì)較低。顯然，應(yīng)該重點(diǎn)突出近期用戶數(shù)據(jù)在推薦中的作用。時(shí)間權(quán)重函數(shù)T(u，i)，表示用戶u對(duì)于項(xiàng)目i的近期相關(guān)程度。

(4)

其中，Lu表示為用戶使用推薦系統(tǒng)的時(shí)間間距；Dui為用戶u最早訪問項(xiàng)目與訪問項(xiàng)目i的時(shí)間間距；a∈(0，1)為權(quán)重增長(zhǎng)系數(shù)，a越大則權(quán)重增長(zhǎng)速度越快，通過改變參數(shù)a的值可以進(jìn)一步優(yōu)化算法性能，當(dāng)a=0.5時(shí)，算法的推薦效果較優(yōu)。

定義2 基于項(xiàng)目相似度的數(shù)據(jù)權(quán)重。如果僅僅考慮用戶的近期數(shù)據(jù)，就會(huì)忽視掉早期的能夠反映用戶興趣的數(shù)據(jù)的推薦價(jià)值。基于項(xiàng)目相似度的權(quán)重函數(shù)S(u，i)，表示用戶u和項(xiàng)目i的當(dāng)前興趣的關(guān)聯(lián)程度。

(5)

其中，設(shè)Iu為用戶u的已訪問項(xiàng)目集合，T為時(shí)間窗，則IuT為在時(shí)間跨度T下用戶u的已訪問項(xiàng)目集合，其在一定程度上反映了用戶的近期興趣；size(IuT)為IuT中的物品數(shù)目；sim函數(shù)采用傳統(tǒng)的相似度度量函數(shù)。時(shí)間窗T是該權(quán)重值的核心參數(shù)，通過調(diào)整T的時(shí)間跨度可以改變推薦算法的平均性能。

定義3 基于時(shí)間和基于項(xiàng)目相似度的時(shí)間綜合權(quán)重。為了有效結(jié)合以上兩種權(quán)重的各自優(yōu)勢(shì)，給出了一個(gè)時(shí)間綜合權(quán)重函數(shù)TS(u，i)，表示用戶u對(duì)已訪問項(xiàng)目i的興趣相關(guān)度[19]。

TS(u，i)=β×WT(u，j)+(1-β)×WS(u，i)

(6)

其中，系數(shù)β∈[0，1]，通過改變?chǔ)轮档拇笮】梢哉{(diào)整兩種權(quán)重值的比重，從而實(shí)現(xiàn)優(yōu)勢(shì)互補(bǔ)，提高算法的性能。

下面將時(shí)間綜合權(quán)重TS(u，i)引入到基于項(xiàng)目的協(xié)同過濾。

改進(jìn)的算法步驟如下：

輸入用戶-項(xiàng)目時(shí)間矩陣、目標(biāo)用戶u。

輸出 Top_N形式的推薦集Rankings。

Step1 計(jì)算每個(gè)項(xiàng)目的相似鄰居得到相似鄰居集S，即每個(gè)物品的最近鄰居集合，存儲(chǔ)其相似鄰居及對(duì)應(yīng)相似度，每個(gè)物品的相似鄰居個(gè)數(shù)設(shè)定在20個(gè)。

Step2 設(shè)Iu為用戶u的已評(píng)分物品集合，對(duì)i∈Iu，讀取其在離線字典S中的最近鄰居，匯總所有的最近鄰居并刪除Iu中已存在的項(xiàng)目，得到候選推薦集Rankings。

Step3 對(duì)j∈Rankings，計(jì)算用戶u對(duì)物品j的預(yù)測(cè)評(píng)分值。

(7)

Step4 采用Top_N形式推薦，按預(yù)測(cè)評(píng)分值降序排列，前N個(gè)作為指定推薦。

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

4.1 實(shí)驗(yàn)環(huán)境及數(shù)據(jù)集

實(shí)驗(yàn)在 Windows 10環(huán)境下進(jìn)行，以 Python實(shí)現(xiàn)。實(shí)驗(yàn)數(shù)據(jù)集為GoodBook，原始數(shù)據(jù)來源于BookCrossing官方網(wǎng)站上278 858個(gè)用戶對(duì)271 379本書的評(píng)分記錄，通過數(shù)據(jù)清洗及預(yù)處理最終得到了實(shí)驗(yàn)數(shù)據(jù)。

其處理步驟如下：首先，去除評(píng)分值為0的評(píng)分記錄并隨機(jī)生成評(píng)分時(shí)間；其次，篩選出500個(gè)評(píng)分記錄在10條以上的用戶，由他們的評(píng)分信息構(gòu)成GoodBook，包含了500個(gè)用戶對(duì)17 696本書共計(jì)27 300條圖書評(píng)分記錄，每條記錄格式為(用戶，圖書，評(píng)分，訪問時(shí)間)；最后，采用五折交叉驗(yàn)證的方式，劃分出了測(cè)試集和訓(xùn)練集，其中每個(gè)用戶20%的評(píng)分?jǐn)?shù)據(jù)作為測(cè)試集，剩余部分的數(shù)據(jù)作為訓(xùn)練集。

4.2 評(píng)價(jià)標(biāo)準(zhǔn)

實(shí)驗(yàn)的評(píng)價(jià)指標(biāo)采用準(zhǔn)確率(Precision)，即推薦結(jié)果中正確的個(gè)數(shù)與總推薦個(gè)數(shù)的比重，若由訓(xùn)練集數(shù)據(jù)計(jì)算所得的推薦結(jié)果能在測(cè)試集中找到，則視為產(chǎn)生了一條正確推薦。

(8)

其中，N為總的推薦個(gè)數(shù)；Right為正確的推薦個(gè)數(shù)。

4.3 實(shí)驗(yàn)方案及參數(shù)設(shè)定

實(shí)驗(yàn)?zāi)康臑閷?duì)比改進(jìn)的PTCF算法與傳統(tǒng)的基于用戶(UserCF)和基于物品(ItemCF)的協(xié)同過濾之間的性能差異，從而驗(yàn)證PTCF在新書推薦中的推薦效率。

文章設(shè)計(jì)了兩組實(shí)驗(yàn)，實(shí)驗(yàn)一是采取五折交叉驗(yàn)證的方式，考察不同算法的推薦效果；實(shí)驗(yàn)二是觀察不同推薦個(gè)數(shù)時(shí)各算法的準(zhǔn)確率情況。其中，實(shí)驗(yàn)指標(biāo)precision的值為用戶的平均值加權(quán)匯總。

實(shí)驗(yàn)參數(shù)設(shè)定如表2 所示。

表2 實(shí)驗(yàn)參數(shù)設(shè)定

參數(shù)解讀：Ra及Rb：數(shù)據(jù)階段的劃分指標(biāo)；n：返回推薦結(jié)果的個(gè)數(shù)；h：稀疏推薦方案中，尋找相似鄰居的迭代次數(shù)；c：稀疏推薦方案中，表示相似度隨迭代次數(shù)增加的傳播衰減率；a：豐富推薦方案中，調(diào)整權(quán)重隨訪問時(shí)間變化的速度的權(quán)重增長(zhǎng)指數(shù)；T：豐富推薦方案中，表示近期數(shù)據(jù)的時(shí)間跨度；β：豐富推薦方案中，調(diào)整兩種權(quán)重的比例因子；sim：表示傳統(tǒng)的相似度度量函數(shù)，sim_distance為歐幾里得距離計(jì)算方法。

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

(1)實(shí)驗(yàn)一的具體情況如圖1所示。

圖1 GoodBook上5折交叉驗(yàn)證實(shí)驗(yàn)情況

從圖1可以看出，三種算法的precision值集中于0.15～0.20之間，K不同取值情況下值波動(dòng)較?。籔TCF的值普遍接近于0.20，對(duì)比UserCF和ItemCF值更大；而ItemCF較userCF推薦精度更高，反映出對(duì)于新書推薦，當(dāng)項(xiàng)目總數(shù)大于用戶總數(shù)時(shí)，采取基于項(xiàng)目的協(xié)同過濾有著更高的推薦效率。

(2)實(shí)驗(yàn)二的具體情況如圖2所示。

圖2 GoodBook上不同推薦個(gè)數(shù)實(shí)驗(yàn)情況

從圖2可以看出，三種算法的precision值集中于0.18到0.5之間，并且隨著推薦個(gè)數(shù)的增加，各算法的preciosion值出現(xiàn)較大幅度地遞減；PTCF整體遞減速度平緩，且平均值大于UserCF和ItemCF，反映出相對(duì)較高的推薦效率；而ItemCF和UserCF的值距離較小，隨著推薦個(gè)數(shù)的增加precision值逐漸接近。

實(shí)驗(yàn)表明，不同的數(shù)據(jù)情況下對(duì)協(xié)同過濾算法的性能影響很大，采取傳統(tǒng)的協(xié)同過濾的效率有限，無法克服稀疏性和可擴(kuò)展性問題，單一推薦算法在實(shí)際推薦過程中不能滿足個(gè)性化推薦的復(fù)雜需求。PTCF的提出能夠考慮到多樣化的推薦需求，且算法的準(zhǔn)確率(precision)情況良好，使推薦性能得到保障。故改進(jìn)的PTCF算法完全適用于新書推薦這一具體應(yīng)用場(chǎng)景，且推薦質(zhì)量較優(yōu)。

5 結(jié)語(yǔ)

文章提出了一種改進(jìn)的PTCF算法，將其應(yīng)用于新書推薦的具體場(chǎng)景中，具有重要的理論與實(shí)踐意義。今后,將對(duì)數(shù)據(jù)階段的劃分將采用更精確的方法，對(duì)初始階段著手挖掘讀者的基本信息提出更加個(gè)性化的推薦，對(duì)稀疏階段可以嘗試降低相似度計(jì)算的時(shí)空開銷，對(duì)于豐富階段需要考慮比例因子β的最優(yōu)值情況。