基于用戶特征和相似置信度的協(xié)同過濾算法

(河南理工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院， 河南 焦作 454000)

網(wǎng)絡(luò)的普及提高了人們的生活質(zhì)量，每天在我們所生活的這個(gè)世界出現(xiàn)了大量的信息，信息的增長(zhǎng)速度絕對(duì)是一件近乎恐怖的事情——我們稱之為“信息爆炸”[1]。面對(duì)如此多的信息，較快地獲取用戶想要的或感興趣的信息變得較為困難。推薦系統(tǒng)可以推薦給用戶有用的信息，減少了用戶獲取信息的時(shí)間和精力。協(xié)同過濾推薦技術(shù)是在推薦系統(tǒng)中應(yīng)用最早和最為成功的技術(shù)之一，因其可以充分利用信息間的聯(lián)系，執(zhí)行效率高，能夠得到較好的推薦結(jié)果，因而成為當(dāng)前研究的熱點(diǎn)[2]。

協(xié)同過濾一般采用最近鄰技術(shù)，利用用戶的歷史喜好信息計(jì)算用戶之間的距離，再利用目標(biāo)用戶的最近鄰居用戶對(duì)商品評(píng)價(jià)的加權(quán)評(píng)價(jià)值來預(yù)測(cè)目標(biāo)用戶對(duì)特定商品的喜好程度，從而根據(jù)這一喜好程度來對(duì)目標(biāo)用戶進(jìn)行推薦[3]。對(duì)于新用戶而言是沒有歷史數(shù)據(jù)的，這就出現(xiàn)用戶冷啟動(dòng)問題。針對(duì)此問題，魏琳東[4]等人采用了矩陣分解的方法和神經(jīng)網(wǎng)絡(luò)映射的知識(shí)各自對(duì)興趣向量進(jìn)行計(jì)算再融合。在現(xiàn)實(shí)生活中用戶并不是對(duì)每一個(gè)項(xiàng)目都進(jìn)行評(píng)分等行為，這就帶來評(píng)分?jǐn)?shù)據(jù)的稀疏性問題。針對(duì)此問題，王竹婷[5]等人用懲罰因子應(yīng)對(duì)共同評(píng)分項(xiàng)較少的用戶，并用依據(jù)自信息量所得的項(xiàng)目權(quán)值修正傳統(tǒng)的相似度計(jì)算方法。

為了緩解算法存在的問題，本文提出一種基于用戶特征和相似置信度的協(xié)同過濾算法(Attributes and Similar Confidence Collaborative Filtering，ASCCF)。將置信度和用戶特征按比例引入到用戶之間的相似性計(jì)算，得到較為可靠的用戶最近鄰居集合進(jìn)而計(jì)算預(yù)測(cè)評(píng)分，并將評(píng)分從大到小的前N個(gè)推薦給用戶。置信度可以避免兩個(gè)用戶共同評(píng)分項(xiàng)目很少時(shí)所帶來的虛假相似現(xiàn)象，用戶特征可以避免新用戶因沒有歷史數(shù)據(jù)所造成的推薦質(zhì)量較低的問題。

1 基礎(chǔ)協(xié)同過濾算法

推薦算法一般包括三步：建立用戶模型、尋找最近鄰居和產(chǎn)生推薦[6]。

1.1 用戶模型的建立

用戶對(duì)項(xiàng)目的評(píng)分信息一般用R表示，R是一個(gè)m×n的矩陣。m表示用戶的數(shù)量，n表示項(xiàng)目的數(shù)量，Rij表示用戶i對(duì)項(xiàng)目j的評(píng)分。評(píng)分在[1～5]之間，用戶的喜好程度與評(píng)分大小成正比。

表1 用戶評(píng)分矩陣

1.2 尋找最近鄰居集合

目標(biāo)用戶的最近鄰居通過相似度計(jì)算來尋找，相似度越大說明兩用戶之間越相似。最常用的相似度計(jì)算方法有皮爾遜(Pearson)相關(guān)系數(shù)、余弦(Cosine)相似度和修正的余弦(Adjust Cosine)相似度[7]。

(1) 皮爾遜(Pearson)相關(guān)系數(shù)：首先會(huì)找出兩位用戶都曾評(píng)論過的項(xiàng)目，然后計(jì)算兩者的評(píng)分總和與平方和，并求得評(píng)分的乘積之和。

(1)

(2) 余弦(Cosine)相似度：用向量空間中兩個(gè)向量夾角的余弦值作為衡量?jī)蓚€(gè)個(gè)體間差異的大小的度量。

(2)

式中，rai、rbi分別為用戶a和用戶b對(duì)項(xiàng)目i的打分；simcos(a,b)為兩用戶的余弦相似度。

(3) 修正的余弦(Adjust Cosine)相似度:考慮到每個(gè)用戶打分時(shí)都打分習(xí)慣的影響，經(jīng)用戶的評(píng)分去掉用戶的平均評(píng)分來均衡用戶的評(píng)分差異。

(3)

式中，rbi為用戶b在項(xiàng)目i上評(píng)論分?jǐn)?shù)；Ia、Ib分別為兩用戶各自評(píng)論的項(xiàng)目集合；sima-cos(a,b)為用戶間調(diào)整的余弦相關(guān)性。

1.3 產(chǎn)生推薦

用以上任一種相似度計(jì)算方法進(jìn)行計(jì)算，獲取最近鄰居集合之后，利用式(4)對(duì)用戶沒有打分的項(xiàng)目進(jìn)行預(yù)測(cè)打分，并將預(yù)測(cè)分?jǐn)?shù)從大到小取前N個(gè)推薦給目標(biāo)用戶。

(4)

式中，Ua為目標(biāo)用戶a的最近鄰居集合；sim(a,b)為皮爾遜相關(guān)系數(shù)；prea,i為目標(biāo)用戶a對(duì)沒有打分的任一項(xiàng)目i的預(yù)測(cè)打分。

2 算法改進(jìn)

2.1 基于置信度的相似度計(jì)算

并不是用戶對(duì)所有的項(xiàng)目都進(jìn)行評(píng)分，由于不同用戶的不同的興趣愛好，所以用戶的打分項(xiàng)目各種各樣，所得到的用戶評(píng)分矩陣稀疏度很大。在獲取用戶最近鄰居集合的時(shí)候，無法反映用戶的相似喜好，尤其是兩個(gè)用戶共同評(píng)價(jià)的項(xiàng)目只有一個(gè)的情況下，他們的相似度很高[8]。

因此，在計(jì)算用戶相似度時(shí)需要有一個(gè)置信度，本文將Jaccard函數(shù)[9]作為置信度的度量函數(shù)，公式如下：

(5)

式中,I(a)、I(b)分別為用戶a和用戶b各自打分的項(xiàng)目集合；|I(a)∩I(b)|為兩用戶打分項(xiàng)目的交集數(shù)量；|I(a)∪I(b)|為兩用戶打分項(xiàng)目的總數(shù)量。

將式(5)引入到相似性計(jì)算公式(1)中，得到一個(gè)改進(jìn)的相似性度量公式，如下：

(6)

式中，S(a,b)為相似置信度。simi(a,b)在一定程度上緩解了兩用戶共同打分項(xiàng)目少時(shí)造成的相似虛假現(xiàn)象，提高了推薦的質(zhì)量。

2.2 基于用戶特征的相似度計(jì)算

用戶一般擁有用戶編號(hào)、年齡、性別、職業(yè)、郵編等基本的信息。這些基本特征在一定程度上會(huì)影響著用戶的興趣喜好，擁有相同特征的用戶可能會(huì)是相似用戶。這些信息可以分為三類：① 年齡；② 性別；③ 職業(yè)和郵編。在新用戶來臨沒有歷史數(shù)據(jù)的情況下，用戶特征顯得尤為重要，所以將用戶的基本特征引入到相似度的計(jì)算中，可以避免用戶冷啟動(dòng)所帶來的推薦效果不好的問題。

(1) 用戶年齡特征。不同年齡的人喜好會(huì)有所不同，比如兒童喜歡動(dòng)畫片，少年喜歡青春偶像劇，老年人喜歡經(jīng)典影視。兩用戶的年齡差距越小，其喜好相似性越大，超出一定范圍時(shí)相似度受年齡的影響微弱。本文中將這一范圍定為10，年齡特征的相似度計(jì)算如下：

(7)

式中,UAa、UAb分別為目標(biāo)用戶a和相似用戶b各自的年齡；simage(a,b)為兩用戶的年齡相似度。

(2) 用戶性別特征。性別相同的用戶喜好一般會(huì)相同，如女性比較喜歡化妝品，男性比較喜歡汽車等。性別的取值只有兩個(gè)，所以性別特征的相似計(jì)算公式如下：

(8)

式中,Sa、Sb分別為用戶a和用戶b各自的性別；simsex(a,b)為用戶間性別的相似度。

(3) 用戶標(biāo)稱特征。有相同職業(yè)的人可能有相同的喜好，如學(xué)生?？磿?，醫(yī)生?？床±龋挥邢嗤]編的人說明所處地區(qū)相同，他們可能會(huì)對(duì)該區(qū)域內(nèi)的一些東西感興趣。對(duì)用戶的標(biāo)稱特征的相似計(jì)算公式如下：

(9)

式中，n為兩用戶間相同標(biāo)稱特征的數(shù)量；m為用戶標(biāo)稱特征的總數(shù)量；simother(a,b)為標(biāo)稱特征的相似程度。

通過上述所得的各種特征的相似性可以用公式(10)計(jì)算用戶a和用戶b在用戶特征上的整體相似度。

(10)

式中,c為用戶特征的分類數(shù)；sima(a,b)為用戶特征的整體相似度。本文按用戶各類特征所占比例相同計(jì)算。

2.3 基于最終相似度的推薦

改進(jìn)的相似度計(jì)算能夠應(yīng)對(duì)數(shù)據(jù)稀疏性和用戶冷啟動(dòng)，把基于用戶特征的相似計(jì)算公式與基于置信度的相似計(jì)算公式進(jìn)行結(jié)合：先計(jì)算基于用戶特征的相似度；再計(jì)算基于置信度的相似度；最后將單獨(dú)計(jì)算所得的兩個(gè)相似度按照前者w的比重，后者(1-w)的比重進(jìn)行相加得到最終的相似度。相似計(jì)算公式如下：

Fsim(a,b)=wsima(a,b)+(1-w)simi(a,b)

(11)

式中,Fsim(a,b)為用戶的整體相似度。整體相似度越高，說明兩用戶越相似，喜好也越接近，推薦給目標(biāo)用戶的結(jié)果也更符合用戶的需求。

2.4 改進(jìn)的算法描述

Input:用戶評(píng)分矩陣Rm×n，用戶特征信息，最近鄰居數(shù)K，目標(biāo)用戶a。

Output:目標(biāo)用戶a的Top-N推薦集。

① 將用戶評(píng)分信息轉(zhuǎn)化為用戶評(píng)分矩陣Rm×n，利用式(6)計(jì)算用戶間的相似程度，獲得simi；

② 利用用戶特征信息，獲取用戶的各類特征，并分別計(jì)算用戶間的年齡相似程度simage，性別相似性simsex，標(biāo)稱特征相似程度simother；

③ 將所得的各類特征相似程度代入到式(10)中，從而獲得用戶特征的整體相似程度sima；

④ 把第①步所得的結(jié)果和第③步所得結(jié)果利用式(11)進(jìn)行計(jì)算，取得最終用戶相似度，并得到目標(biāo)用戶a的最近鄰居集合Ua；

⑤ 根據(jù)目標(biāo)用戶a的最近鄰居集合Ua和式(4)對(duì)未打分的項(xiàng)目進(jìn)行預(yù)測(cè)打分，對(duì)分?jǐn)?shù)從大到小排序，形成Top-N集合進(jìn)行推薦。

2.5 算法分析

本文的相似度算法與傳統(tǒng)的相似度算法(余弦相似度)復(fù)雜度都為O(n2)。本文中每?jī)蓚€(gè)用戶特征總相似度計(jì)算需2次加法，一次除法，開銷很小；計(jì)算置信度相似度計(jì)算時(shí)，在Pearson相關(guān)系數(shù)計(jì)算公式之后乘以一個(gè)置信度。而文獻(xiàn)[5]在計(jì)算相似度時(shí)，在Pearson相關(guān)系數(shù)計(jì)算公式中為每個(gè)項(xiàng)目增加權(quán)值。兩相比較知本文算法的開銷小于文獻(xiàn)[5]中算法的開銷。

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

3.1 實(shí)驗(yàn)數(shù)據(jù)

實(shí)驗(yàn)選取的MovieLens數(shù)據(jù)集，是由GroupLens研究小組在明尼蘇達(dá)大學(xué)研究項(xiàng)目上收集的。其中包括943個(gè)用戶對(duì)1682部電影的100000條評(píng)分記錄[10]。用戶的打分最低為1，最高為5，所打的分?jǐn)?shù)與用戶的喜歡程度成正比。根據(jù)數(shù)據(jù)稀疏性公式可以計(jì)算該數(shù)據(jù)集的數(shù)據(jù)稀疏度[11]。

(12)

式中,Spa為數(shù)據(jù)集的稀疏程度；num為打分總數(shù)量；m為用戶的數(shù)量；n為項(xiàng)目的數(shù)量。用式(12)計(jì)算得到該數(shù)據(jù)集的稀疏程度為93.69%。

3.2 評(píng)測(cè)標(biāo)準(zhǔn)

推薦系統(tǒng)準(zhǔn)確性測(cè)量分為3類：預(yù)測(cè)準(zhǔn)確測(cè)量(如MAE、RMSE)、分類準(zhǔn)確測(cè)量(如ROC曲線)和排序準(zhǔn)確測(cè)量[12]。本文采用平均絕對(duì)誤差(Mean Absolute Error，MAE)作為度量標(biāo)準(zhǔn)，MAE的定義如下[13]

(13)

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

在數(shù)據(jù)集中給出了5個(gè)訓(xùn)練集(u1.base，u2.base，u3.base，u4.base，u5.base)和5個(gè)測(cè)試集(u1.test，u2.test，u3.test，u4.test，u5.test)。隨機(jī)選取一個(gè)訓(xùn)練集和與其相對(duì)應(yīng)的測(cè)試集進(jìn)行實(shí)驗(yàn)。

改進(jìn)的相似度計(jì)算是由基于置信度的相似計(jì)算公式與基于用戶特征的相似計(jì)算公式用一個(gè)因子w進(jìn)行結(jié)合得到的。對(duì)于新用戶而言，沒有歷史數(shù)據(jù)作為推薦的依據(jù)，此時(shí)用戶的特征起到主要作用；對(duì)于老用戶而言，大量的歷史數(shù)據(jù)可以為用戶提供充足的依據(jù)，此時(shí)用戶的特征作用會(huì)有所減小，所以理論上w取值在0～0.5之間。下面由實(shí)驗(yàn)進(jìn)一步來確定w的最佳取值。

w的值從0開始取間隔為0.1，到1為止，w=0表示相似性計(jì)算公式中只有置信度，w=1表示相似性計(jì)算公式中只有用戶特征，不同w的取值所得的MAE值結(jié)果如圖1所示。從圖1可以看出w在取0.1時(shí)，MAE取值最小，算法效果最好。

圖1 不同w的取值與所得MAE

目標(biāo)用戶的最近鄰居數(shù)的不同取值對(duì)MAE也有一定的影響，最近鄰居數(shù)越小，用戶冷啟動(dòng)的可能性越大。利用上述實(shí)驗(yàn)所得結(jié)果，將w的值定為0.1，最近鄰居數(shù)從10開始間隔為10直到100為止，計(jì)算不同鄰居數(shù)下的MAE值大小，結(jié)果如圖2所示。從圖2中可以知道用戶最近鄰居數(shù)最小時(shí)MAE取值最小，這就說明改進(jìn)的協(xié)同過濾算法的推薦質(zhì)量在用戶冷啟動(dòng)時(shí)有所提高。

圖2 不同最近鄰居數(shù)下的MAE取值

為更好地體現(xiàn)改進(jìn)的協(xié)同過濾算法的效果，將本文的改進(jìn)算法(ASCCF)與傳統(tǒng)的協(xié)同過濾算法(修正余弦相似度)和文獻(xiàn)[5]的改進(jìn)算法相比較。用戶最近鄰居數(shù)從10開始間隔為10依次增加到100 為止，比較不同鄰居數(shù)量下各自算法的MAE取值。所得的實(shí)驗(yàn)結(jié)果如圖3所示。從圖3可知，最近鄰居很少時(shí)本文的算法結(jié)果最好，隨著最近鄰居數(shù)量的增加，本文改進(jìn)的協(xié)同過濾算法所得的MAE值雖然有所增大，在70點(diǎn)處與文獻(xiàn)[5]相同，80點(diǎn)處比文獻(xiàn)[5]好，最近鄰居數(shù)大于85時(shí)稍遜色與文獻(xiàn)[5]，但依然比傳統(tǒng)算法的MAE值小，所以本文改進(jìn)的算法更適用于最近鄰居數(shù)小的情況。

圖3 3種方法的比較

4 結(jié)束語

本文針對(duì)算法中存在的數(shù)據(jù)稀疏和用戶冷啟動(dòng)問題，對(duì)最初的傳統(tǒng)過濾算法進(jìn)行改進(jìn)，提出一種基于用戶特征與相似置信度的協(xié)同過濾算法。置信度的引入讓兩用戶在共有打分項(xiàng)目較少情況下，減少了兩用戶間相似的假象，用戶相似度得到保證進(jìn)而提高了推薦的準(zhǔn)確性。用戶特征的加入，讓新用戶通過自身特征計(jì)算用戶間的相似程度，避免了冷啟動(dòng)所帶來的困擾，進(jìn)而保證了推薦的質(zhì)量。再用一個(gè)因子將兩種相似度計(jì)算方法聯(lián)系起來，控制各自所占比重計(jì)算用戶間最終相似程度，獲取目標(biāo)用戶的K個(gè)最近鄰居集進(jìn)行預(yù)測(cè)打分，按照打分的高低形成Top-N推薦給目標(biāo)用戶。實(shí)驗(yàn)表明，在評(píng)分矩陣稀疏和冷啟動(dòng)的情況下，本文改進(jìn)的算法效果很好。但沒有考慮用戶的興趣會(huì)隨時(shí)間的變遷而發(fā)生變化，在最近鄰居數(shù)越大的情況下算法也有待改進(jìn)，因此考慮用戶興趣的時(shí)間有效性和在較大最近鄰居數(shù)下提高推薦質(zhì)量將是本文的下一步研究。