李改，李磊

（1.順德職業(yè)技術(shù)學(xué)院電子與信息工程學(xué)院，廣東 順德528333；2.中山大學(xué)信息科學(xué)與技術(shù)學(xué)院，廣東 廣州510006；3.中山大學(xué)軟件研究所，廣東 廣州510275）

0 引言

隨著互聯(lián)網(wǎng)的快速發(fā)展，互聯(lián)網(wǎng)上的數(shù)據(jù)量急劇增長(zhǎng)，從而使得如何快速而高效地從如此浩瀚的數(shù)據(jù)海洋中獲取我們所需要的信息變得越來(lái)越緊迫.在此背景下推薦系統(tǒng)應(yīng)運(yùn)而生，推薦系統(tǒng)通過(guò)收集和分析用戶的各種信息來(lái)學(xué)習(xí)用戶的興趣和行為模式，根據(jù)分析得到用戶的興趣和行為模式，為用戶推薦所需要的服務(wù).這些系統(tǒng)的例子包括：卓越亞馬遜（www.amazon.com）、當(dāng)當(dāng)網(wǎng)（www.dangdang.com）為用戶推薦各種其可能喜歡的商品，如書(shū)籍、音像、電器、服裝等；Netflix電影出租系統(tǒng)（www.netflix.com）為用戶推薦各種其可能喜歡的電影.Google、Baidu、Yahoo等為用戶推薦這種個(gè)性化的新聞和搜索服務(wù).推薦系統(tǒng)中運(yùn)用最廣泛的是基于協(xié)同過(guò)濾的推薦算法［1－3］.

近年來(lái)協(xié)同過(guò)濾的算法在國(guó)內(nèi)外得到了廣泛研究，按處理數(shù)據(jù)的不同主要分為兩類(lèi)：一類(lèi)是處理明確偏好的顯式數(shù)據(jù)，如：評(píng)分.另一類(lèi)則是處理無(wú)明確偏好的隱式數(shù)據(jù)，如：對(duì)網(wǎng)頁(yè)點(diǎn)擊與否.這種隱式數(shù)據(jù)廣泛存在于真實(shí)世界的應(yīng)用環(huán)境中，譬如用戶是否購(gòu)買(mǎi)過(guò)某個(gè)商品，用戶是否點(diǎn)擊過(guò)某個(gè)網(wǎng)頁(yè)等等.由于這里信息不需要用戶提供明確的評(píng)分，因此相比評(píng)分?jǐn)?shù)據(jù)更容易獲取.該類(lèi)數(shù)據(jù)中僅有正例可以明確區(qū)分開(kāi)來(lái)，負(fù)例不確定，故我們把該類(lèi)問(wèn)題稱(chēng)為單類(lèi)協(xié)同過(guò)濾（OCCF）問(wèn)題［4］.單類(lèi)協(xié)同過(guò)濾的任務(wù)就是通過(guò)分析這些隱式信息來(lái)針對(duì)特定用戶的偏好對(duì)推薦對(duì)象集按該用戶的喜歡程度排序.盡管這類(lèi)數(shù)據(jù)獲取很容易，但該類(lèi)數(shù)據(jù)極度稀疏且類(lèi)高度不平衡，解釋起來(lái)也存在很大困難.以用戶點(diǎn)擊網(wǎng)頁(yè)的數(shù)據(jù)為例，這些數(shù)據(jù)中用戶點(diǎn)擊過(guò)的網(wǎng)頁(yè)構(gòu)成的數(shù)據(jù)可以解釋為正例，其余絕大部分?jǐn)?shù)據(jù)是負(fù)例和漏掉的正例的混合，如何解決數(shù)據(jù)的高度稀疏性及不平衡性問(wèn)題，和如何解釋這類(lèi)混合數(shù)據(jù)并對(duì)解釋后的數(shù)據(jù)進(jìn)行有效處理，是當(dāng)前單類(lèi)協(xié)同過(guò)濾問(wèn)題研究的難點(diǎn)所在.目前對(duì)該問(wèn)題的研究還很少，C.Wang等把概率矩陣分解（PMF）技術(shù)運(yùn)用到單類(lèi)協(xié)同過(guò)濾問(wèn)題［5］，他們把觀察到的點(diǎn)擊數(shù)據(jù)作為正例數(shù)據(jù)，其余的混合數(shù)據(jù)均作為負(fù)例數(shù)據(jù)，Zhang S等提出運(yùn)用奇異值分解（SVD）技術(shù)來(lái)解決該類(lèi)問(wèn)題［6］.Rendle S等提出運(yùn)用基于KNN的協(xié)同過(guò)濾算法來(lái)解決該類(lèi)問(wèn)題［7］.Pan等提出了運(yùn)用加權(quán)的低秩逼近算法（OCCF）來(lái)解決該類(lèi)問(wèn)題［4］.

近來(lái)社交網(wǎng)絡(luò)在協(xié)同過(guò)濾算法中的應(yīng)用研究已經(jīng)成為一個(gè)熱點(diǎn)研究領(lǐng)域，如Ma等人就提出了在顯式數(shù)據(jù)的推薦算法中引入社會(huì)化規(guī)范來(lái)提高推薦性能，同時(shí)解決帶顯式數(shù)據(jù)的推薦系統(tǒng)的數(shù)據(jù)稀疏性問(wèn)題［8－12］.

在研究帶顯式數(shù)據(jù)的社會(huì)化推薦算法的基礎(chǔ)上，提出一種新的基于社交網(wǎng)絡(luò)的單類(lèi)協(xié)同過(guò)濾推薦算法，即在Pan等提出的單類(lèi)協(xié)同過(guò)濾算法的基礎(chǔ)上引入社會(huì)化規(guī)范，以進(jìn)一步提高單類(lèi)協(xié)同過(guò)濾算法的性能，進(jìn)而在真實(shí)的社會(huì)化數(shù)據(jù)集上實(shí)現(xiàn)本文中所提出的算法，并將其與幾個(gè)傳統(tǒng)的單類(lèi)協(xié)同過(guò)濾算法的性能作比較.實(shí)驗(yàn)結(jié)果表明，SOCCF算法在各個(gè)性能評(píng)價(jià)指標(biāo)下均優(yōu)于幾個(gè)傳統(tǒng)的單類(lèi)協(xié)同過(guò)濾算法.

1 基本定義和傳統(tǒng)的單類(lèi)協(xié)同過(guò)濾算法

1.1 基本定義 本文中矩陣用斜體大寫(xiě)字母表示（如：R），標(biāo)量用小寫(xiě)字母表示（如：i，j）.給定一個(gè)矩陣R，Rij表示它的一個(gè)元素，Ri.表示矩陣R的第i行，R.j表示矩陣R 的第j列，RT表示矩陣R的轉(zhuǎn)置.R－1表示矩陣R的逆.在本文中給定的矩陣R表示具有m個(gè)用戶、n個(gè)對(duì)象的評(píng)分矩陣，矩陣U、V分別表示用戶和推薦對(duì)象的特征矩陣.

1.2 傳統(tǒng)的單類(lèi)協(xié)同過(guò)濾算法 在傳統(tǒng)的單類(lèi)協(xié)同過(guò)濾算法［4］中為了找到一個(gè)低秩矩陣X來(lái)最大程度地逼近隱式數(shù)據(jù)矩陣R，我們最小化加權(quán)的Frobenius損失函數(shù)L（U，V）.

在目標(biāo)函數(shù)L（U，V）中，（Rij－Ui.VTj.）是低秩逼近中常見(jiàn)平方誤差項(xiàng).Wij表示各個(gè)數(shù)據(jù)點(diǎn)對(duì)最小化總的加權(quán)的Frobenius損失函數(shù)的貢獻(xiàn)，Wij＝θ∈［0，1］，具體的加權(quán)策略詳見(jiàn)文獻(xiàn)［4］.U、V 表示用戶和推薦對(duì)象的特征矩陣.

為了防止過(guò)擬合，我們給（1）式加上正則化項(xiàng)，則（1）式可改寫(xiě)為：

為了找到（2）式的最小值，可以通過(guò)對(duì)（2）式實(shí)施梯度下降法得到.固定V，對(duì)Ui.求導(dǎo)得到：

同理，固定U，對(duì)Vj.求導(dǎo)得到：

2 基于社交網(wǎng)絡(luò)的單類(lèi)協(xié)同過(guò)濾算法

2.1 基于社交網(wǎng)絡(luò)的單類(lèi)協(xié)同過(guò)濾算法 在傳統(tǒng)的單類(lèi)協(xié)同過(guò)濾算法（OCCF）的基礎(chǔ)上引入社會(huì)化規(guī)范，進(jìn)一步提高傳統(tǒng)的單類(lèi)協(xié)同過(guò)濾算法的性能.我們把本節(jié)中所提出的算法簡(jiǎn)稱(chēng)為SOCCF.

在這里我們假定，在社交網(wǎng)絡(luò)中具有朋友關(guān)系的兩個(gè)用戶之間的特征向量相似，并且不同的評(píng)分相識(shí)性的用戶之間的特征向量的相識(shí)程度也不同.在此引入下面的社會(huì)化正則項(xiàng)公式來(lái)對(duì)社交網(wǎng)絡(luò)中具有朋友關(guān)系的兩個(gè)用戶之間的特征向量進(jìn)行規(guī)范［8］.

這里添加的社會(huì)化正則項(xiàng)是為了使得用戶的特征向量盡可能與他的朋友的特征向量相似.參數(shù)β用于約束社交網(wǎng)絡(luò)信息的影響.F（i）是用戶ui的朋友集.‖Ui.－Uf.‖2F用于表示某個(gè)用戶和他的朋友之間的偏好差異，用戶ui和他的朋友uf之間的偏好差異越大，則‖Ui.－Uf.‖2F越大.其中Sim（i，f）表示用戶ui和他的朋友uf之間的評(píng)分模式上的相似度.Sim（i，f）‖Ui.－Uf.‖2F表示用戶ui和他的朋友uf通過(guò)相似度加權(quán)后的偏好差異.

在（5）式中Sim（i，f）用于計(jì)算用戶ui和他的朋友uf之間的相似度，由于向量空間相似度（VSS）和皮爾生相關(guān)系數(shù)（PCC）均基于用戶之間的共同評(píng)分項(xiàng)目集來(lái)計(jì)算相似度，而在現(xiàn)實(shí)世界中可能存在兩個(gè)用戶各自都有很多評(píng)分項(xiàng)，但這兩個(gè)用戶之間沒(méi)有共同評(píng)分項(xiàng)目集，因此不能運(yùn)用這兩個(gè)函數(shù)來(lái)計(jì)算相應(yīng)的用戶間的相似度，從而導(dǎo)致這兩個(gè)用戶之間的社交網(wǎng)絡(luò)信息丟失.為了解決該問(wèn)題，提出的SOCCF算法采用了YU等提出的一種新的社會(huì)化相似度計(jì)算函數(shù)NSS使其能計(jì)算沒(méi)有共同評(píng)分的用戶間的相似度［11］：

這里Ui.和Uf.表示兩個(gè)用戶ui和uf的潛在特征向量.因此如果用戶ui和uf偏好相同，則特征向量Ui.和Uf.也相近，從而算出來(lái)的兩個(gè)用戶ui和uf的相似度Sim（i，f）接近于1.如果運(yùn)用向量空間相似度（VSS）和皮爾生相關(guān)系數(shù)（PCC）來(lái)計(jì)算相似度將導(dǎo)致沒(méi)有共同評(píng)分項(xiàng)目集的用戶之間的社會(huì)化信息丟失，因?yàn)閅U等提出的NSS相似度計(jì)算方法，不需要的用戶之間的共同評(píng)分項(xiàng)目集，因此不會(huì)導(dǎo)致用戶之間的社會(huì)化信息丟失.

社會(huì)化正則項(xiàng)引入傳統(tǒng)的單類(lèi)協(xié)同過(guò)濾算法，我們就得到了本文中所提出的基于社交網(wǎng)絡(luò)的單類(lèi)協(xié)同過(guò)濾算法：

為了最小化損失函數(shù)，在（7）式上，對(duì)Ui.和Vj.實(shí)施梯度下降法，我們得到：

總結(jié)以上分析，我們給出SOCCF的求解算法如下：

算法1中的參數(shù)H表示一輪更新中所抽取的負(fù)例數(shù)據(jù)的個(gè)數(shù)與正例數(shù)據(jù)的個(gè)數(shù)相比的倍數(shù).

2.2 算法計(jì)算復(fù)雜度分析 提出的SOCCF算法的計(jì)算復(fù)雜度主要與目標(biāo)函數(shù)L2（U，V）和其各個(gè)偏導(dǎo)項(xiàng)的計(jì)算復(fù)雜度有關(guān).分析（7）式，得到L（U，V）的計(jì)算復(fù)雜度為O（k＋2ρRmk），ρR表示評(píng)分矩陣R中正例評(píng)分點(diǎn)的個(gè)數(shù)，k表示特征矩陣U、V中的特征數(shù)表示用戶的平均朋友個(gè)數(shù)，m 表示用戶數(shù).分析（8～9）式，得到偏導(dǎo)項(xiàng)的計(jì)算復(fù)雜度分別為O（ρRk2＋m）和O（ρRk2）.由于?ρR，故一輪迭代中算法的復(fù)雜度為O（（H＋1）（ρRk2＋ρRk）），假定算法迭代d次后收斂，則整個(gè)算法的復(fù)雜度為O（d（H＋1）（ρRk2＋ρRk））.由于本算法采取抽樣的隨機(jī)梯度下降法來(lái)求解，迭代次數(shù)d將是一個(gè)常數(shù).故本算法的時(shí)間復(fù)雜度與評(píng)分矩陣R中的正例數(shù)據(jù)點(diǎn)的個(gè)數(shù)線性相關(guān).從以上分析可知，本文中所提的算法是一個(gè)高效算法，適合大數(shù)據(jù)的處理需要.

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

3.1 實(shí)驗(yàn)數(shù)據(jù)集 本實(shí)驗(yàn)中使用廣泛運(yùn)用的、公用的包含社交網(wǎng)絡(luò)數(shù)據(jù)的數(shù)據(jù)集Epinions［11－12］.在這個(gè)數(shù)據(jù)集中，用戶對(duì)其感興趣的產(chǎn)品和服務(wù)進(jìn)行評(píng)分，評(píng)分范圍是1～5分的整數(shù)值.Epinions數(shù)據(jù)集中有用戶的社交網(wǎng)絡(luò)信息，這些關(guān)系與用戶所信任的朋友的關(guān)系存在.Epinions數(shù)據(jù)集中包含49 290個(gè)用戶，139 738個(gè)不同的評(píng)分項(xiàng).總的評(píng)分?jǐn)?shù)據(jù)點(diǎn)是664 824個(gè).在社交網(wǎng)絡(luò)中，總共有511 799個(gè)信任關(guān)系.為了把該數(shù)據(jù)集變?yōu)殡[式數(shù)據(jù)集，所有有評(píng)分?jǐn)?shù)據(jù)的數(shù)據(jù)點(diǎn)均設(shè)置評(píng)分值為1，其他沒(méi)有評(píng)分?jǐn)?shù)據(jù)的數(shù)據(jù)點(diǎn)設(shè)置評(píng)分值為0.經(jīng)過(guò)上述處理，該Epinions數(shù)據(jù)集就變成了適合于單類(lèi)協(xié)同過(guò)濾算法的數(shù)據(jù)集.

3.2 實(shí)驗(yàn)的評(píng)價(jià)標(biāo)準(zhǔn) 實(shí)驗(yàn)采用留一策略作為評(píng)價(jià)機(jī)制，也即我們從每個(gè)用戶的評(píng)分歷史中隨機(jī)地選取并移除一個(gè)評(píng)分點(diǎn)作為測(cè)試集Stest，余下的數(shù)據(jù)構(gòu)成訓(xùn)練集Strain，這兩個(gè)集合不相交.我們?cè)赟train上訓(xùn)練出相應(yīng)的模型，接著在測(cè)試集上評(píng)估模型預(yù)測(cè)出的推薦對(duì)象的個(gè)性化排序.這里采用的評(píng)估標(biāo)準(zhǔn)是平均 AUC［7］：

在這里δ是一個(gè)指標(biāo)函數(shù)：

每個(gè)用戶的評(píng)估對(duì)象為：

AUC值越高表示該算法的性能越好.由隨機(jī)模型產(chǎn)生的AUC值為0.5，最好模型的AUC值為1.對(duì)每個(gè)實(shí)驗(yàn)我們均反復(fù)運(yùn)行10次，每次均對(duì)每個(gè)用戶隨機(jī)選取一個(gè)評(píng)分點(diǎn)，構(gòu)成新的訓(xùn)練集和測(cè)試集，最終結(jié)果取10次運(yùn)算結(jié)果的平均值.

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

3.3.1 規(guī)范化參數(shù)λ和β對(duì)SOCCF實(shí)驗(yàn)結(jié)果的影響 參數(shù)λ是正則化參數(shù)，可以通過(guò)交叉確認(rèn)的方法學(xué)習(xí)得到，我們?cè)O(shè)置該參數(shù)為0.01.另一個(gè)參數(shù)β用于控制社交網(wǎng)絡(luò)信息對(duì)SOCCF算法性能的影響.在極端情況下，如果我們?cè)O(shè)置參數(shù)β＝0，則在推薦過(guò)程中社交網(wǎng)絡(luò)信息沒(méi)有產(chǎn)生任何作用，推薦算法退化為傳統(tǒng)的單類(lèi)協(xié)同過(guò)濾推薦算法.

圖1 參數(shù)β對(duì)算法SOCCF性能的影響

圖1 顯示了當(dāng)特征數(shù)為5時(shí)，參數(shù)β對(duì)算法SOCCF的性能的影響，其中橫軸表示參數(shù)β值的變化，縱軸表示算法SOCCF的AUC值.從圖1不難看出開(kāi)始隨著參數(shù)β的增大，算法SOCCF的AUC值首先快速上升，隨后又逐漸降低，參數(shù)β的最優(yōu)值是0.01.這個(gè)結(jié)果正好和現(xiàn)實(shí)世界中朋友之間相互推薦的實(shí)際效果相符合，如果我們既考慮自身的喜好又考慮朋友的推薦，則我們就更能找到符合我們自己偏好的推薦對(duì)象.如果僅僅只是考慮自身喜好而忽略朋友的推薦，或者是僅僅考慮朋友的推薦而忽略自身的喜好，則都會(huì)走向極端，而不能得到最好的推薦效果.3.3.2 SOCCF算法和幾個(gè)經(jīng)典的單類(lèi)協(xié)同過(guò)濾算法的性能比較 本文中所有算法均在裝有Linux系統(tǒng)環(huán)境的計(jì)算機(jī)下運(yùn)行，計(jì)算機(jī)配置環(huán)境是4核CPU，每個(gè)核主頻是3.2GHz，內(nèi)存是7.6G.各個(gè)算法的程序代碼用Java開(kāi)發(fā)工具Eclipse編寫(xiě).各個(gè)算法均反復(fù)運(yùn)行10次取平均結(jié)果作為該算法的最終運(yùn)行結(jié)果.

圖2 SOCCF算法與其他經(jīng)典單類(lèi)協(xié)同過(guò)濾算法的比較

圖2 表示在Epinions數(shù)據(jù)集上，所提出的SOCCF算法與傳統(tǒng)的OCCF算法，PMF算法、SVD算法、基于用戶的KNN算法（KNNUser）和基于項(xiàng)目的KNN算法（KNNItem）的性能對(duì)比.圖1中橫軸表示各個(gè)算法中用戶／推薦對(duì)象的特征矩陣中特征的個(gè)數(shù)，特征個(gè)數(shù)從1變化到40，縱軸表示各個(gè)算法的AUC值.通過(guò)實(shí)驗(yàn)驗(yàn)證，SOCCF算法在Epinions數(shù)據(jù)集上取得最優(yōu)值的負(fù)例權(quán)值參數(shù)θ為0.15，正則化參數(shù)λ為0.015 625.對(duì)于基于用戶的KNN算法和基于項(xiàng)目的KNN算法，該實(shí)驗(yàn)中的結(jié)果取最優(yōu)值，由于這兩個(gè)算法的性能與特征矩陣中特征的個(gè)數(shù)無(wú)關(guān)，故在各個(gè)特征數(shù)下取值均一致.

從圖2中可以看出在各個(gè)特征數(shù)下，提出的SOCCF算法幾乎均優(yōu)于傳統(tǒng)的OCCF算法、PMF算法和SVD算法，也優(yōu)于最優(yōu)的基于用戶的KNN算法（KNNUser）和基于項(xiàng)目的KNN算法（KNNItem），并且這種優(yōu)勢(shì)隨著特征數(shù)的增加越發(fā)明顯.其中SVD算法的AUC值隨著特征數(shù)的增大先增大，而后急速下降，這是由于SVD算法在解決單類(lèi)協(xié)同過(guò)濾問(wèn)題時(shí)也出現(xiàn)了過(guò)擬合現(xiàn)象.

4 總結(jié)

在傳統(tǒng)的單類(lèi)協(xié)同過(guò)濾算法的基礎(chǔ)上，引入社會(huì)化正則項(xiàng)，提出了一種新的基于社交網(wǎng)絡(luò)的單類(lèi)協(xié)同過(guò)濾算法.并以AUC值為性能評(píng)價(jià)標(biāo)準(zhǔn)，將其與傳統(tǒng)的LRA算法、SVD算法、基于用戶的KNN算法和基于項(xiàng)目的KNN算法的性能進(jìn)行了比較，實(shí)驗(yàn)結(jié)果表明提出的SOCCF算法遠(yuǎn)優(yōu)于其他幾個(gè)經(jīng)典的單類(lèi)協(xié)同過(guò)濾推薦算法.在以后的工作中我們還將考慮SOCCF算法的冷啟動(dòng)問(wèn)題、并行化的問(wèn)題、以及與其他算法結(jié)合提出更加高性能的混合模型.

［1］Wu J L.Collaborative filtering on the Netflix prize dataset［D］.Beijing：Peking University，2010.

［2］Ricci F，Rokach L，Shapira B，et al.Recommender system handbook［M］.Belin：Springer，2011：12－120.

［3］Adomavicius G，Tuzhilin A.Toward the next generation of recommender systems：a survey of the state－of－the－art and possible extenstions［J］.TKDE，2005，17（6）：734－749.

［4］Pan R，Zhou Y，Cao B，et al.On e－class collaborative filtering［C］／／In IEEE International Conferenc e on Data Mining，2008：502－511.

［5］Wang C，Lei B，David M.Collaborative topic modeling for recommending scientic articles［C］／／Proceedings of the 2011Conference of the Knowledge Discovery and Data Mining，California，2011：448－456.

［6］Paterek A.Improving regularized singular value decomposition for collaborative filtering［C］／／in：KDD－Cup and Workshop，ACM press，2007：39－42.

［7］Rendle S，F(xiàn)reudenthaler C，Gantner，et al.BPR：bayesian personalized ranking from implicit feedback［C］／／In UAI，2009：452－461.

［8］Ma H，Zhou D Y，Liu C，et al.Recommendation systems with Social Regularization［C］／／In WSDM，2011：287－296.

［9］Zhu J K，Ma H，Chen C，et al.Social recommendation using low－rank semidefinite program［C］／／In AAAI，2011：158－163.

［10］Jamali M，Ester M.Matrix factorization technique with trust propagation for recommendation in social networks［C］／／In IJCAI，2011：2644－2649.

［11］Yu L，Pan R，Li Z.Adaptive social similarities for recommender systems［C］／／In Proceedings of the fifth ACM conference on Recommender systems（RecSys），2011：257－260.

［12］Tang J L，Hu X，Gao H J，et al.Exploitting local and global social context for recommendation［C］／／In IJCAI，2013：264－269.