結(jié)合對象屬性與近似檢索的協(xié)同過濾算法

陳 樂，余 粟

1(上海工程技術(shù)大學(xué) 電子電氣工程學(xué)院,上海 201620)

2(上海工程技術(shù)大學(xué) 圖文信息中心,上海 201620)

1 引 言

隨著互聯(lián)網(wǎng)與人們生活日趨密切，互聯(lián)網(wǎng)產(chǎn)生的數(shù)據(jù)量和信息量呈爆發(fā)式增長，如何從海量數(shù)據(jù)中快速準(zhǔn)確地找到用戶所需信息成為一大難題[1，2].因此，個性化的推薦系統(tǒng)應(yīng)運而生，它將根據(jù)用戶的網(wǎng)絡(luò)歷史行為和自身屬性預(yù)測人們可能需要的商品或信息[3].

協(xié)同過濾技術(shù)[4，5]因其模型通用性強和易于實現(xiàn)而成為推薦系統(tǒng)的主流技術(shù)之一.其又包含近鄰模型[6]和隱變量模型[7]兩種主要的實現(xiàn)方式.近鄰模型通過挖掘由用戶與商品的交互行為而產(chǎn)生的歷史數(shù)據(jù)，例如評分?jǐn)?shù)據(jù)、行為數(shù)據(jù)(點贊、評論、轉(zhuǎn)發(fā))等，將具有相似行為偏好的用戶群作為目標(biāo)用戶的近鄰用戶集，再基于近鄰用戶集計算目標(biāo)用戶對未評分物品的預(yù)測得分[8，9].

為了解決原始評分?jǐn)?shù)據(jù)高維稀疏，物品和用戶自有屬性缺失等問題，國內(nèi)專家進行了相關(guān)研究.朱磊等[10]采用用戶評分偏好模型改進用戶間原始評分?jǐn)?shù)據(jù)的偏好差異性，但是原始評分?jǐn)?shù)據(jù)的稀疏性和近鄰用戶的檢索性能有待改進.王永貴等[11]提出構(gòu)建用戶類別偏好矩陣，并利用花朵授粉優(yōu)化模糊聚類算法，一定程度上改進了數(shù)據(jù)的稀疏性和近鄰用戶的檢索性能，但是算法時間復(fù)雜度較大，且并未考慮用戶評分偏好.李紅梅等[12]利用基于精確歐式局部敏感哈希對評分?jǐn)?shù)據(jù)降維并構(gòu)建索引，能顯著提高近鄰用戶檢索性能，但并未挖掘評分?jǐn)?shù)據(jù)中隱藏的用戶和物品特性.

對已有的相關(guān)協(xié)同過濾技術(shù)綜合分析可知，僅從用戶或物品單一方面改進評分?jǐn)?shù)據(jù)都存在一定的片面性，另外提高檢索效率的同時還要保證穩(wěn)定的時間復(fù)雜度，故本文提出一種結(jié)合對象屬性和近似檢索的推薦模型.該模型利用物品和用戶的自有屬性同時改進原始評分?jǐn)?shù)據(jù)，并通過近似最近鄰檢索技術(shù)對評分?jǐn)?shù)據(jù)降維索引，進而可以有效提高推薦質(zhì)量和推薦效率.

2 相關(guān)工作

2.1 對象相似性度量

基于近鄰模型的協(xié)同過濾算法中，推薦結(jié)果的精準(zhǔn)與否主要取決于用戶或物品的相似性計算[13].相似性度量方式主要采用Person相關(guān)系數(shù)、歐式距離和修正余弦相似系數(shù)等，且Pearson相關(guān)系數(shù)在度量精度上優(yōu)于修正余弦相似系數(shù)[14].基于Pearson相關(guān)系數(shù)的用戶間相似性sim(u,v)計算如下：

(1)

2.2 近似最近鄰檢索

在近鄰模型中，如何在高維稀疏的評分?jǐn)?shù)據(jù)空間快速準(zhǔn)確地通過相似性檢索以獲取目標(biāo)用戶的近鄰用戶集合成為影響推薦性能的關(guān)鍵之一.為此，相比低效率的精確檢索，近似最近鄰檢索技術(shù)在可接受的精度范圍內(nèi)具有更好的檢索性能.δ-近似最近鄰檢索(Approximate Nearest Neighbor Search，ANNS)定義表述如下：

定義 1.(δ-近似最近鄰搜索)在數(shù)據(jù)空間Rt中任取一個數(shù)據(jù)集合M，并給定近似系數(shù)δ>1.則空間Rt中任意一點q，若存在p∈M，使得對任意一點x∈M滿足d(p,q)≤δ·d(x,q)，則稱p是q的δ-近似最近鄰.

局部敏感哈希(Locality-Sensitive Hashing,LSH)是目前實現(xiàn)ANNS最為廣泛的索引技術(shù)之一，其具有高效的檢索效率和良好的誤差保證[14].LSH是一種特殊的哈希函數(shù)，將原始數(shù)據(jù)空間中的數(shù)據(jù)點哈希之后，相鄰數(shù)據(jù)點哈希值相等的概率較大，將投影在同一區(qū)段，即落入同一哈希桶中，因此篩選出不相鄰的數(shù)據(jù)點，降低計算復(fù)雜度的同時可以快速獲取近鄰用戶集合.

3 原始評分?jǐn)?shù)據(jù)修正與索引

3.1 物品類別偏好模型

在現(xiàn)實應(yīng)用中，物品具有類別屬性，用戶間對于同一類別物品的評價數(shù)往往遠(yuǎn)大于同一物品的評價數(shù).通過建立用戶對物品類別的偏好模型可以實現(xiàn)對原始評分?jǐn)?shù)據(jù)中相似用戶群的細(xì)粒度劃分.

設(shè)物品類別矩陣為Cngy，Cij=1表示物品i屬于類別cj，Cij=0表示物品i不屬于類別cj.同一物品也可能屬于多個類別，如Ci(j+l)=1表示物品i也屬于類別cj+l.故矩陣Cngy是一個0或1值填充的矩陣.設(shè)原始用戶評分矩陣為Rmgn，m表示用戶數(shù)，n表示物品數(shù)，Ru,i表示用戶u對物品i的評分.物品類別偏好模型定義如下：

(2)

式(2)中，preCu,cj表示用戶u對物品類別cj的偏好值；Ccj表示用戶u評分物品中屬于類別cj的物品集合；Ru,i表示用戶u對物品i的評分；Ncj表示所有物品中屬于類別cj的數(shù)量，對應(yīng)于矩陣Cngy中cj列等于1的行數(shù)；Ncjo表示所有物品中不僅屬于類別cj的數(shù)量，對應(yīng)矩陣Cngy中不止cj列唯一等于1的行數(shù)；Noo表示所有物品中僅屬于一類的數(shù)量，對應(yīng)矩陣Cngy中僅唯一列等于1的行數(shù).式中不僅考慮了某一類別在所有類別中的評分比重，而且還在物品空間中考慮該類別的比重，所以可以較好地衡量用戶對某一類別的偏好值.

則用戶u對物品i的類別偏好得分計算如下：

(3)

式(3)中，Ru,i表式用戶u對物品i的評分；Ci表示物品i所屬類別集合；preCu,cj表示用戶u對類別cj的偏好值.

3.2 用戶評分偏好模型

因主觀差異性，不同用戶評分時具有不同的評分偏好.某些用戶評分標(biāo)準(zhǔn)較高，評分習(xí)慣偏低，而某些用戶評分標(biāo)準(zhǔn)較低，評分習(xí)慣偏高，當(dāng)這兩類用戶對某一物品打出相同評分時，評分標(biāo)準(zhǔn)較高的用戶可能更加偏好這個物品.假設(shè)有評分類別集合{η1,η2,…,ηn}，例如標(biāo)準(zhǔn)五分制可以表示為{1,2,…,5}，則用戶u對于評分類別ηi的偏好得分preRRu,ηi可以通過如下公式計算[10]：

(4)

式(4)中，Nηj<ηi是用戶u所有評分中小于類別ηi的數(shù)量；Nηi是用戶u評分類別為ηi的數(shù)量；Nu是用戶u的所有評分?jǐn)?shù)量.通過評分偏好模型，用戶u對于評分值屬于評分類別ηi的物品i的評分偏好得分為preRRu,ηi.

最終，線性融合物品類別偏好模型與用戶評分偏好模型，如式(5)所示，并用finalRu,i替換掉原始用戶評分矩陣Rm·n中的對應(yīng)值，得到修正用戶評分矩陣comRm·n.

finalRu,i=λpreCRu,i+(1-λ)preRRu,ηi

(5)

式(5)中，λ表示調(diào)節(jié)參數(shù)，用于合理分配兩種模型在原始評分?jǐn)?shù)據(jù)中的占比，λ∈[0，1]，最優(yōu)值由后面實驗部分給出.

3.3 修正評分?jǐn)?shù)據(jù)索引與查詢

3.3.1 基于p-穩(wěn)態(tài)分布的局部敏感哈希

基于p-穩(wěn)態(tài)分布的局部敏感哈希具有更低的時空復(fù)雜性和更高的查詢準(zhǔn)確率，對于高維稀疏數(shù)據(jù)具有高效的查詢效率和穩(wěn)定的運行時間[15，16].基于p-穩(wěn)態(tài)分布的哈希函數(shù)族如下：

(6)

式(6)中，a是Rt內(nèi)某一隨機直線的方向矢量，且各分量相互獨立并服從p-穩(wěn)態(tài)分布，t維空間向量s投影到a所在的直線上，b∈[0,w]是直線上的平移量，該直線按w劃分，?·」為向下取整操作，哈希值h(s)便是投影點所在直線的區(qū)段號，由相關(guān)實驗證明，w=4時檢索效果最好.

3.3.2 建立索引與查詢

在實際查詢時，為了提高相似點碰撞概率和不相似點不碰撞概率，需要對哈希函數(shù)進行“與構(gòu)造”和“或構(gòu)造”.“或構(gòu)造”即構(gòu)建復(fù)合LSH函數(shù)，隨機，均勻地選取l個哈希函數(shù)連接起來形成l維的哈希函數(shù)組H={g:Rt→Ul}，其中g(shù)(s)=(h1(s),h2(s),…,hl(s)).所以，原始數(shù)據(jù)空間Rt中的數(shù)據(jù)點經(jīng)過函數(shù)g(s)處理后降至l維，在降維的同時也保證了數(shù)據(jù)間的相似性.“與構(gòu)造”即從H中隨機均勻選取L個函數(shù)g1(s),g2(s),…,gL(s),構(gòu)造L個哈希表，將原始數(shù)據(jù)集存儲在L個哈希表中的不同桶中.

4 改進的協(xié)同過濾算法

近似近鄰集合中的所有用戶與u的相似性度量依據(jù)公式(1)計算，返回前k個相似度較高的用戶，得到目標(biāo)用戶u的最近鄰用戶集合.基于最近鄰用戶集，采用加權(quán)策略計算目標(biāo)用戶u對物品i的預(yù)測評分Pu,i.

(7)

算法1.改進的協(xié)同過濾算法

輸入：Rm·n，Cn·y，l，L，近鄰數(shù)k

輸出：用戶u對物品i的預(yù)測評分Pu·i

1.FOR(eachu∈Ru,g)DO

2.FOR(eachi∈Ci,g)DO

3. ComputepreCu,cj,preCRu,iBy Formula(2)，(3)

4. ComputepreRRu,ηiBy Formula(4)

5. ComputefinalRu,iBy Formula(5)

6.comRm·n←ReplaceRu·iWithfinalRu,i

7.g(u)=(h1(u),h2(u),…,hl(u))

8.YmgL=(g1(u),g2(u),…,hL(u))

9.ENDFOR

10.ENDFOR

11.FOR(eachu∈comRm·n)DO

12. Compute ANN FromYm·L

13. ComputekNN From ANN By Formula(1)

14. ComputePu·iFromkNN By Formula(7)

15.ENDFOR

算法1的3-8行表示對原始評分?jǐn)?shù)據(jù)的修正、降維和索引.算法1的12-14行表示依次計算近似近鄰集合、k近鄰集合和最終的預(yù)測評分.

5 實驗設(shè)計與結(jié)果分析

5.1 實驗數(shù)據(jù)集和算法評價指標(biāo)

5.1.1 實驗數(shù)據(jù)集

本文采用推薦算法經(jīng)典測試數(shù)據(jù)集MovieLens 100k，該數(shù)據(jù)集包含943位用戶對1682部電影的90570次評級.實驗時，將原始數(shù)據(jù)集按照8：2比例隨機劃分為訓(xùn)練集和測試集.實驗中，取5次實驗的算術(shù)平均值作為最終結(jié)果.

5.1.2 評價指標(biāo)

本文采用統(tǒng)計精度度量方法即平均絕對誤差(Mean Absolute Error,MAE)來測試在不同參數(shù)條件下的推薦質(zhì)量，MAE值越小，推薦質(zhì)量越高.其定義如下：

(8)

式(8)中，Pi表示預(yù)測用戶評分向量，Ri表示實際用戶評分向量，m表示用戶數(shù).

另外，采用top-N推薦算法中最為常用的兩個指標(biāo)準(zhǔn)確率(Precision)和召回率(Recall)來更加細(xì)致和精準(zhǔn)地對比本文算法與其它相關(guān)算法的推薦質(zhì)量.準(zhǔn)確率和召回率定義如下：

(9)

(10)

式(9)和式(10)中，U是測試集所有用戶集合；T(u)是訓(xùn)練集上對目標(biāo)用戶u的推薦列表；L(u)是目標(biāo)用戶u測試集上喜歡的物品集合.

5.2 結(jié)果分析

1)不同調(diào)節(jié)參數(shù)λ和組合哈希函數(shù)個數(shù)l下的MAE值.

本文推薦質(zhì)量的高低主要依賴于調(diào)節(jié)參數(shù)λ，組合哈希函數(shù)個數(shù)l，哈希表個數(shù)L，其中L的取值又依賴于數(shù)據(jù)集大小和實際運行內(nèi)存大小，所以根據(jù)實際實驗情況取L=8.至于λ,l的取值則通過MAE的實驗結(jié)果來確定.實驗時，針對不同的l值，計算在取不同λ值的情況下MAE的變化趨勢，λ∈[0,1]，步長為0.2.實驗結(jié)果如圖1所示.

圖1 不同調(diào)節(jié)參數(shù)λ與組合哈希函數(shù)個數(shù)l下的MAE值

由圖1數(shù)據(jù)可知，當(dāng)調(diào)價參數(shù)λ=0.6時，對于所有不同組合哈希函數(shù)個數(shù)l的MAE值都取得最小，故本文取λ=0.6.這一結(jié)果直觀反映了在用戶評分中，物品類別偏好相比于用戶評分偏好具有更大的比重，也符合客觀事實.此外，當(dāng)l=15時，在不同的調(diào)節(jié)參數(shù)λ下，MAE值均取得最低，故本文取組合哈希函數(shù)個數(shù)l=15.

2)相似協(xié)同過濾推薦算法與本文算法的推薦質(zhì)量對比.

結(jié)合前文分析，本文算法將與朱磊等提出的PTP-Item-CF、王永貴等提出的優(yōu)化算法和李紅梅等提出的優(yōu)化算法在準(zhǔn)確率和召回率上做出對比.實驗時，將針對不同近鄰用戶數(shù)k分別計算每個算法的準(zhǔn)確率和召回率，k∈[20,120]，步長為15，本文算法中取λ=0.6，l=15，實驗結(jié)果如圖2，圖3所示.

圖2 不同k值下各算法準(zhǔn)確率對比

圖3 不同k值下各算法召回率對比

由圖2，圖3可知，隨著近鄰用戶數(shù)k的不斷增加，各算法的準(zhǔn)確率和召回率均不斷增加再趨于穩(wěn)定，且對于不同算法，MAE值的穩(wěn)定k值點均有所差異，但是本文所提算法的準(zhǔn)確率和召回率無論在哪種k值條件下均高于其它算法.

3)相似協(xié)同過濾推薦算法與本文算法的運行效率對比.

為了驗證本文采用的近似近鄰檢索技術(shù)能夠顯著提高近鄰用戶查詢效率，本文算法將與其它3種算法在運行時間上做出對比.實驗時，將針對不同近鄰用戶數(shù)k分別計算每個算法的運行時間，k∈[15,120]，步長為15，本文算法中取λ=0.6，l=15，實驗結(jié)果如圖4所示.

由圖4可知，隨著近鄰用戶數(shù)目的增加，基于傳統(tǒng)檢索方式的PTP-Item-CF的算法的運行時間急劇增加，而王永貴等提出的基于聚類優(yōu)化的協(xié)同過濾算法的運行時間增加幅度相對較為緩慢.本文算法和李紅梅所提優(yōu)化算法由于采用相同檢索方式，所以運行時間趨勢較為一致，但是由于本文算法對原始評分?jǐn)?shù)據(jù)有所修正，所以檢索效率更高，運行時間更短.最終可知，本文算法相對其它算法具有更高的檢索效率.

圖4 不同k值下各算法的運行時間

6 結(jié) 語

本文針對傳統(tǒng)協(xié)同過濾算法中存在的評分?jǐn)?shù)據(jù)高維稀疏、用戶評分偏好和物品類別偏好特征性較低等問題，提出一種基于對象屬性和近似檢索的協(xié)同過濾算法.通過線性融合兩種偏好模型對原始評分?jǐn)?shù)據(jù)進行修正，使得修正的評分值中可以合理地體現(xiàn)物品類別偏好和用戶評分偏好，從而提高不同偏好的用戶間的區(qū)分度.此外，針對評分?jǐn)?shù)據(jù)的高維稀疏性，通過近似近鄰搜索技術(shù)可以更加穩(wěn)定和高效地獲得近鄰用戶集合.由于本文算法的運行性能依賴與多個關(guān)鍵參數(shù)的設(shè)置，所以該模型對參數(shù)的敏感性較高.另外，文中偏好模型僅依賴于評分?jǐn)?shù)據(jù)和物品類別信息，故對用戶的偏好描述不夠完善.下一步研究方向?qū)⒃谔岣哧P(guān)鍵參數(shù)的自適應(yīng)性的同時，利用文本挖掘技術(shù)從用戶的文字評論信息中挖掘出更多偏好信息，完善偏好模型.