LBSN上基于興趣圈中社會(huì)關(guān)系挖掘的推薦算法

李 鑫 劉貴全 李 琳 吳宗大 丁君美

1(中國(guó)科學(xué)技術(shù)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 合肥 230022)2(科大訊飛股份有限公司大數(shù)據(jù)研究院 合肥 230088)3(武漢理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 武漢 430070)4 (溫州大學(xué)甌江學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 浙江溫州 325035) (xinli2@iflytek.com)

LBSN上基于興趣圈中社會(huì)關(guān)系挖掘的推薦算法

李 鑫1,2劉貴全1李 琳3吳宗大4丁君美1

1(中國(guó)科學(xué)技術(shù)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 合肥 230022)2(科大訊飛股份有限公司大數(shù)據(jù)研究院 合肥 230088)3(武漢理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 武漢 430070)4(溫州大學(xué)甌江學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 浙江溫州 325035) (xinli2@iflytek.com)

隨著帶有GPS定位功能的智能手機(jī)越來(lái)越普遍，人們喜歡分享他們的地理位置或者通過(guò)評(píng)論某個(gè)地方的商品從而留下用戶的足跡，這引發(fā)了以共同的興趣點(diǎn)(POIs)為中心，基于地理位置信息的社交網(wǎng)絡(luò)研究(location based social network, LBSN).社交網(wǎng)絡(luò)中的一類典型應(yīng)用是推薦系統(tǒng)，而推薦系統(tǒng)中最常見(jiàn)的問(wèn)題是冷啟動(dòng)，即在用戶很少點(diǎn)評(píng)商家或分享評(píng)論時(shí)如何為他推薦感興趣的商家.為解決冷啟動(dòng)問(wèn)題，提出了一種在社交網(wǎng)絡(luò)中基于興趣圈的社會(huì)關(guān)系挖掘推薦算法.興趣圈是由所有訪問(wèn)某一類別商品的用戶群及他們之間的社會(huì)關(guān)系構(gòu)成的社交聯(lián)系，不同的用戶訪問(wèn)同一類別商品表明他們對(duì)此類別具有相似興趣.該方法在傳統(tǒng)矩陣分解模型的基礎(chǔ)上考慮不同的興趣圈上的社會(huì)關(guān)系，使用的社會(huì)關(guān)系包括朋友關(guān)系(顯性關(guān)系)和相關(guān)專家(隱性關(guān)系)，并用它們作為規(guī)則化項(xiàng)來(lái)優(yōu)化矩陣分解模型.實(shí)驗(yàn)數(shù)據(jù)集來(lái)自第5屆Yelp挑戰(zhàn)賽和自己爬取的Foursquare數(shù)據(jù)集，提出的方法與已有模型進(jìn)行了充分的實(shí)驗(yàn)對(duì)比分析，結(jié)果表明，我們的模型特別是在解決冷啟動(dòng)問(wèn)題方面優(yōu)于多種現(xiàn)有的方法.

興趣點(diǎn)；推薦；興趣圈；社會(huì)關(guān)系；冷啟動(dòng)

近年來(lái)興起了基于地理位置信息服務(wù)的熱潮，如Foursquare和Yelp挑戰(zhàn)賽.用戶在這種在線服務(wù)上可以通過(guò)評(píng)論或者給商家評(píng)分分享他們的經(jīng)驗(yàn).同時(shí)，他們可以加好友或者成為別人的粉絲，從而形成了社交網(wǎng)絡(luò).上面的2個(gè)特性是基于位置的社交網(wǎng)絡(luò)(location based social network， LBSN)的基礎(chǔ).推薦算法可以幫助用戶在LBSN中找到自己感興趣的商家，成為學(xué)術(shù)界和工業(yè)界關(guān)注和研究的熱點(diǎn)問(wèn)題.

眾所周知，影響推薦系統(tǒng)性能的2個(gè)主要問(wèn)題是用戶冷啟動(dòng)和數(shù)據(jù)稀疏，而冷啟動(dòng)問(wèn)題研究的是在用戶很少點(diǎn)評(píng)商家或分享評(píng)論時(shí)如何為他推薦感興趣的商家.解決這類問(wèn)題的可行性方案之一是將社會(huì)關(guān)系融入到推薦模型中.一個(gè)用戶的品味跟與他有社會(huì)關(guān)系的人比較相似或受他們影響，這被稱為社會(huì)學(xué)中的同質(zhì)性.本文使用的社會(huì)關(guān)系包括朋友和專家關(guān)系.盡管現(xiàn)有的推薦系統(tǒng)在不斷改進(jìn)，但在LBSN上對(duì)社會(huì)關(guān)系的挖掘還存在很大的空間可以提升推薦系統(tǒng)的性能.其一，當(dāng)位置信息嵌入到社交網(wǎng)絡(luò)中形成新的LBSN時(shí)，社會(huì)聯(lián)系將會(huì)擴(kuò)大.除了現(xiàn)有的2個(gè)用戶之間的關(guān)系外，另一個(gè)聯(lián)系則是用戶的位置信息.如2個(gè)用戶訪問(wèn)了同一個(gè)商品時(shí)，說(shuō)明他們共處于同一地理位置，那么他們很可能會(huì)被聯(lián)系起來(lái)[1].其二，除了受自身朋友影響外，用戶也可能會(huì)受到訪問(wèn)過(guò)同類商品的專家的評(píng)分和評(píng)論影響.這是因?yàn)樵谀硞€(gè)商品的網(wǎng)頁(yè)上，專家的評(píng)論在這類商品中總是排名很高，從而影響后面的用戶.最后，傳統(tǒng)利用社會(huì)關(guān)系的方法解決冷啟動(dòng)問(wèn)題的假設(shè)是：雖然用戶訪問(wèn)的商品比較少，但是他有足夠的社會(huì)關(guān)系，我們可以通過(guò)學(xué)習(xí)他的朋友或者這方面專家的意見(jiàn)來(lái)給他們推薦.但當(dāng)用戶訪問(wèn)商品很少時(shí)，他很可能也沒(méi)有豐富的社會(huì)關(guān)系.

本文針對(duì)上述冷啟動(dòng)和稀疏問(wèn)題，提出一種基于相同興趣圈的推薦系統(tǒng)，使用社交網(wǎng)絡(luò)為輔助信息來(lái)提高POI模型準(zhǔn)確率.興趣圈是由所有訪問(wèn)某一類別商品的用戶群及他們之間的社會(huì)關(guān)系構(gòu)成的社交聯(lián)系，不同的用戶訪問(wèn)同一類別商品表明他們對(duì)此類別具有相似興趣.模型同時(shí)采用了朋友和專家2種社會(huì)關(guān)系作為矩陣分解的2個(gè)正則化約束項(xiàng).對(duì)一個(gè)具體用戶而言，朋友或者專家的正則化項(xiàng)對(duì)他的影響可能有所不同，所以對(duì)它們的處理也完全不同.尤其對(duì)于解決冷啟動(dòng)情況，用戶評(píng)分?jǐn)?shù)比較少很可能朋友數(shù)也不多，所以同一類商品下的專家用戶可能對(duì)推薦有很大幫助.這些朋友和專家都根據(jù)歷史評(píng)分記錄以及評(píng)論被劃分成不同的興趣圈后，他們對(duì)系統(tǒng)推薦都發(fā)揮著重要的作用.我們根據(jù)LBSN信息提出基于興趣圈中社會(huì)關(guān)系挖掘的POI推薦算法(circle-based and social connection embedded recommendation in LBSN, CSCR).CSCR算法使用朋友和專家2種社會(huì)關(guān)系作為規(guī)則化項(xiàng)來(lái)優(yōu)化目標(biāo)函數(shù)的學(xué)習(xí).在真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明我們的方法優(yōu)于多種基于矩陣分解的經(jīng)典方法.綜上所述，本文的貢獻(xiàn)如下：

1) 提出了一種基于不同興趣圈的推薦算法，同時(shí)利用LBSN上顯性和隱性的社會(huì)關(guān)系來(lái)提高推薦系統(tǒng)的性能，尤其對(duì)于解決冷啟動(dòng)問(wèn)題效果顯著.

2) 設(shè)計(jì)了基于朋友關(guān)系和基于專家用戶的2個(gè)正則化項(xiàng)，用它們作為矩陣分解目標(biāo)函數(shù)的約束條件，并考慮到它們對(duì)不同的用戶的差異性影響.

3) 證明了2個(gè)等價(jià)定理.①無(wú)論2個(gè)用戶的相似性是以獨(dú)立方式還是平均值結(jié)合到正規(guī)化項(xiàng)中的，它們本質(zhì)都是一樣的;②目標(biāo)函數(shù)中所有正則化項(xiàng)可以被視為是不同高斯分布的組合.

4) 在Yelp和Foursquare數(shù)據(jù)集上進(jìn)行了充分的實(shí)驗(yàn)，結(jié)果表明CSCR算法優(yōu)于現(xiàn)有的基于社會(huì)信息的推薦算法.

1 相關(guān)工作

在LBSN上對(duì)有相同興趣點(diǎn)的推薦，可以將POIs看做普通的項(xiàng)用通常的方法來(lái)解決.基本的低秩矩陣分解技術(shù)由Salakhutdinov等人[2]用概率給出以及被Koren[3]巧妙地應(yīng)用并贏得了Netflix獎(jiǎng).低秩矩陣分解的前提是有一些潛在的因素分別控制用戶和商品的屬性.預(yù)測(cè)的評(píng)分由R=UVT給出，U和V分別是用戶-特征矩陣和商品-特征矩陣.模型訓(xùn)練是通過(guò)最小化含有Frobenius范數(shù)規(guī)則化項(xiàng)的目標(biāo)函數(shù)的誤差平方和.

Fig. 1 Description of interest circle圖1 在POIs不同類別下的基于興趣圈的模型描述

現(xiàn)在社交網(wǎng)絡(luò)信息較易獲得，許多模型通過(guò)結(jié)合社會(huì)關(guān)系提高推薦系統(tǒng)準(zhǔn)確率，如SocialMF[4],SoReg (social regularization)[5],hTrust (homophily trust)[6],ASS (adaptive social similarity)[7].這些模型假設(shè)用戶的特征向量與他相似的鄰居的特征向量相近，即使用戶只訪問(wèn)很少的商品也可以向鄰居學(xué)習(xí).同時(shí)也有研究者將信任傳播機(jī)制結(jié)合到模型中[4,8]，或通過(guò)設(shè)計(jì)規(guī)則化項(xiàng)[5-6]以及通過(guò)調(diào)查不同的用戶相似度度量方法和同質(zhì)性系數(shù)從本質(zhì)上區(qū)分目標(biāo)函數(shù).然而這些方法中2個(gè)用戶的相似性度量計(jì)算是通過(guò)他們?cè)L問(wèn)的共同商品集得到的，并不是所用的文章都采用這種方法，如Yu等人[7]則沒(méi)有使用用戶潛在的特征向量來(lái)度量用戶間的相似程度.關(guān)于人際關(guān)系的影響和社會(huì)關(guān)系的研究[9-10]以及結(jié)合協(xié)同過(guò)濾的推薦算法的研究[11-12]也非常普遍.

然而，以上方法忽略了用戶社交關(guān)系的多類別性.Yang等人[13]提出了基于興趣圈的推薦方法，他們通過(guò)推斷特定類別的社交圈和設(shè)計(jì)這個(gè)興趣圈中不同朋友的不同權(quán)重，大量實(shí)驗(yàn)驗(yàn)證了這一方法優(yōu)于SocialMF模型.在此基礎(chǔ)上Zhao等人[14]也基于興趣圈研究了人際關(guān)系和人與人之間興趣的相似度對(duì)模型的影響.本文的特色是在每個(gè)興趣圈內(nèi)不僅利用了明確的社會(huì)關(guān)系(朋友),而且考慮了隱含的社會(huì)關(guān)系(專家)來(lái)解決冷啟動(dòng)問(wèn)題.Tang等人[15]利用了局部和全局的社會(huì)關(guān)系，同時(shí)考慮自己的朋友和所有用戶中具有較高聲譽(yù)的用戶，這篇文章的工作和我們的觀點(diǎn)比較相近，但其整個(gè)網(wǎng)絡(luò)中有影響力用戶的影響是通過(guò)在目標(biāo)函數(shù)中設(shè)置權(quán)重明確對(duì)模型的影響，然后設(shè)計(jì)一個(gè)正則化項(xiàng)集成到模型中來(lái).而本文是通過(guò)對(duì)目標(biāo)函數(shù)的優(yōu)化學(xué)習(xí)得到這些權(quán)重.

2 問(wèn)題定義

本文研究的問(wèn)題是以社交網(wǎng)絡(luò)信息為基礎(chǔ)的POI推薦.令U={u1,u2,…,uM}，V={v1,v2,…,vN}分別是用戶的集合和POIs的集合，其中M和N分別指用戶數(shù)和POIs數(shù).用戶之間的關(guān)系可以用一個(gè)矩陣F∈M×M表示，當(dāng)用戶ui是用戶uj的朋友時(shí)，矩陣元素fij值為1，否則為0.所以F是一個(gè)對(duì)稱矩陣，這也使得社交網(wǎng)絡(luò)中用戶間的連接是一個(gè)無(wú)向圖(如Facebook).每1個(gè)POI屬于1個(gè)類別c，例如飯店或者酒店.根據(jù)每個(gè)用戶的評(píng)級(jí)記錄，社交網(wǎng)絡(luò)可以被劃分成不同的興趣圈，而在每個(gè)興趣圈中用戶之間的社會(huì)連接是整個(gè)社交網(wǎng)絡(luò)的子圖，如圖1所示.具體定義如下：

有一些用戶會(huì)被網(wǎng)站選中并標(biāo)記成“專家”，例如圖1(a)中的用戶u3，其表示u3在某個(gè)領(lǐng)域或興趣圈里經(jīng)驗(yàn)很高.而所有的專家用戶組成的集合我們定義為E.

我們目標(biāo)是通過(guò)用戶關(guān)系F、專家集合E和POI類別c作為輔助信息，預(yù)測(cè)每一組(u,v)的評(píng)分.尤其當(dāng)用戶的評(píng)分很少時(shí)即冷啟動(dòng)情況，仍能給出令人滿意的推薦結(jié)果.

3 模 型

本文在LBSN上基于興趣圈中社會(huì)關(guān)系挖掘的POI推薦是在傳統(tǒng)矩陣分解模型基礎(chǔ)上引入朋友和專家關(guān)系作為規(guī)則化項(xiàng)來(lái)優(yōu)化矩陣分解模型.新模型也可以視為CircleCon[13]增加了專家正則化項(xiàng)的延伸，這也是為了更好地解決冷啟動(dòng)問(wèn)題.

3.1 基本矩陣分解模型

基本的矩陣分解技術(shù)是將整個(gè)用戶評(píng)分矩陣R分解成2個(gè)矩陣U∈M×D和V∈N×D.通過(guò)對(duì)矩陣迭代學(xué)習(xí)，最大限度地減少有正則化項(xiàng)的平方誤差損失函數(shù)，直到收斂.其中U和V分別是用戶-特征矩陣和POI-特征矩陣，特征維數(shù)D?M,N.因?yàn)楸疚牟捎昧伺d趣圈的概念，所以用戶評(píng)分矩陣R根據(jù)類別c被劃分成更小的塊，即Rc，而目標(biāo)函數(shù)根據(jù)每個(gè)類別修改后為：

(1)

其中,?是Hadamard乘積;Uc，Vc分別是類別c下的用戶-特征矩陣和POI-特征矩陣;J是與矩陣Rc大小相同的指示矩陣，如果用戶對(duì)POI給出了評(píng)分，則J矩陣相應(yīng)位置的值為1，否則為0.

3.2 基于朋友關(guān)系的正則化項(xiàng)

LBSN在模型中使用的前提是用戶與他的朋友有著相同的興趣而且他容易受朋友的影響，這分別被稱為同質(zhì)性[16]和社會(huì)影響力[17].對(duì)于冷啟動(dòng)情況，當(dāng)用戶評(píng)分?jǐn)?shù)很少但朋友較多，那么相同興趣圈內(nèi)有相同愛(ài)好的朋友與他對(duì)某個(gè)商品的喜好程度可能比較相近，所以利用朋友關(guān)系設(shè)計(jì)正則化項(xiàng)具有一定的合理性.

(2)

通過(guò)歸一化矩陣Sc中每一行記錄得到新的矩陣S*，類別c下的朋友關(guān)系規(guī)則化項(xiàng)為：

(3)

3.3 基于專家的正則化項(xiàng)

相對(duì)于朋友關(guān)系，專家關(guān)系則是一種隱性的社會(huì)關(guān)系.專家關(guān)系是指人們有時(shí)也會(huì)受到一個(gè)領(lǐng)袖人物(專家)的影響，容易接受他們的觀點(diǎn)并對(duì)用戶自身行為產(chǎn)生影響.如果假設(shè)用戶的興趣應(yīng)該與他們興趣圈中專家用戶的較為接近，那么我們就可以加入專家的影響.而且，當(dāng)用戶的朋友數(shù)少時(shí)專家關(guān)系的參考性將更大.所以為了更好地解決冷啟動(dòng)問(wèn)題，我們?cè)谂笥殃P(guān)系的基礎(chǔ)上又提出了基于專家關(guān)系的規(guī)則化項(xiàng).

在傳統(tǒng)的社交網(wǎng)絡(luò)分析中，往往通過(guò)影響力傳播的方法研究專家的影響，這種方法并不要求用戶之間有直接關(guān)系.然而LBSN可以提供額外的地理范圍信息，為我們研究專家的影響提供了新的方法.我們知道用戶在LBSN上的信息是以位置為中心的，同時(shí)專家的評(píng)論和評(píng)分在每個(gè)商家的頁(yè)面上等級(jí)很高，從而反過(guò)來(lái)影響普通用戶.因此來(lái)自專家的影響有2個(gè)前提：1)專家用戶影響普通用戶需要他們?cè)L問(wèn)了同一商品；2)一個(gè)專家不會(huì)受到其他專家的影響.基于上述前提，我們用矩陣Ec設(shè)計(jì)了2種定義專家對(duì)普通用戶的影響，定義如下：

(4)

因?yàn)橛袝r(shí)候嚴(yán)格標(biāo)記好的專家用戶這個(gè)信息是無(wú)法獲得的，所以我們又提出了一種方法來(lái)估計(jì)用戶的專業(yè)度.這個(gè)想法是專家用戶應(yīng)該有更多的朋友，可以吸引更多的關(guān)注.我們使用每個(gè)用戶對(duì)他朋友的平均吸引力來(lái)定義他的專業(yè).這種情況下的用戶影響力定義如下：

(5)

(6)

3.4 有2個(gè)規(guī)則化項(xiàng)的基于興趣圈的模型

目前為止，我們通過(guò)式(1)(3)(6)可以得到最終的模型如下：

(7)

其中α和β分別是2個(gè)正則化項(xiàng)的參數(shù).

式(7)將朋友和專家的影響融合到了模型中，但這并不意味著它們兩者是同時(shí)有效的.如圖1(b)中，u3是標(biāo)記的專家用戶，與u4和u5分別有聯(lián)系.對(duì)u4來(lái)說(shuō)，只用專家的規(guī)則化項(xiàng)對(duì)他有影響，因?yàn)樗cu3用戶訪問(wèn)了同一個(gè)地方但是與他又沒(méi)有直接的聯(lián)系.而對(duì)u5而言，不管是專家的規(guī)則化項(xiàng)還是朋友的規(guī)則化項(xiàng)都對(duì)他有影響.

3.5 分析推斷

由于模型已經(jīng)被分解成不同的興趣圈，所以每個(gè)類別下的訓(xùn)練過(guò)程是獨(dú)立的.一般來(lái)說(shuō)可以采用批處理梯度下降來(lái)最小化目標(biāo)函數(shù)知道收斂.學(xué)習(xí)過(guò)程如下：

(8)

(9)

其中I為單位矩陣.一旦學(xué)習(xí)好每個(gè)類別c中的Uc和Vc之后，就可以預(yù)測(cè)這個(gè)類別下用戶-商品對(duì)(ui,vj)的評(píng)分.模型同時(shí)考慮了2種正則化項(xiàng)，即使對(duì)冷啟動(dòng)用戶也可以給出有效的評(píng)分.具體如算法1所示.

算法1. 基于興趣圈中社會(huì)關(guān)系的推薦模型.

輸入：Rc,S*c,E*c；

輸出：Uc,Vc.

① 隨機(jī)輸入U(xiǎn)c,Vc；

② 循環(huán)從step=1到MAXSTEP：

⑥ 循環(huán)結(jié)束；

3.6 算法復(fù)雜度分析

3.7 等價(jià)定理

現(xiàn)在已經(jīng)有很多模型假設(shè)用戶的興趣可能與他的鄰居比較接近，并結(jié)合了社交網(wǎng)絡(luò)信息設(shè)計(jì)不同的規(guī)則化項(xiàng)[4-6,13].實(shí)際上，無(wú)論2個(gè)用戶的相似性是獨(dú)立結(jié)合到正規(guī)化項(xiàng)中的還是以平均值結(jié)合到正規(guī)化項(xiàng)中的，它們的本質(zhì)都是一樣的.

證明. 像文獻(xiàn)[6]中式(7)提到的一樣，L=D-S是一個(gè)拉普拉斯矩陣，其中，

我們需要做的就是以平均為基礎(chǔ)的正則化項(xiàng)與獨(dú)立的有相同的表示形式.

證畢.

定理2. 第二等價(jià)定理.目標(biāo)函數(shù)中的所有正則化項(xiàng)可以被視為是由各種估計(jì)用戶興趣標(biāo)準(zhǔn)差的高斯分布的組合.

在i.i.d.(independent and identically distributed)假設(shè)下，這3個(gè)分布的線性組合是：

因此在我們的模型中，用戶的興趣服從均值為αμ1+βμ2的高斯分布.

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

本節(jié)將本文提出的CSCR模型與已經(jīng)存在的一些模型比較,有BaseMF[2]，PRM[18]，CircleCon3[13]，SocialMF[4]，SR[19].所有的實(shí)驗(yàn)將在Yelp和Foursquare數(shù)據(jù)集上進(jìn)行.

4.1 數(shù)據(jù)集

我們采用第5屆Yelp挑戰(zhàn)賽的數(shù)據(jù)集①http://www.yelp.com/dataset challenge.根據(jù)商品類別可以劃分成10個(gè)類：Activelife，Arts，Beauty，Education，Hotels，Nightlife，Pets，Restaurants，Services，Shopping.數(shù)據(jù)集中所有用戶數(shù)為366 715，每個(gè)用戶或商品還包含很多信息，我們只提取一些對(duì)我們有用的數(shù)據(jù).表1給出了10個(gè)類別下的用戶數(shù)和商品數(shù)的統(tǒng)計(jì)量，其中rc指的是用戶在類別c下的平均評(píng)分.

Table 1 Statistics of Various Categories on Yelp Dataset表1 Yelp數(shù)據(jù)集上各個(gè)類別記錄統(tǒng)計(jì)

另外，實(shí)驗(yàn)還在自己爬取的Foursquare數(shù)據(jù)集的4個(gè)類別上做了對(duì)比.這4個(gè)類別分別是Hotels，Sports，Traffic，Arts.其中,Hotels類別下共有4 728個(gè)用戶和6 078種商品，用戶評(píng)分的商品數(shù)共有10 991次；Sports類別下含3 443個(gè)用戶和3 037種商品，用戶評(píng)分的商品數(shù)共有5 872次；Traffic類別下含2 590個(gè)用戶和2 791種商品，用戶評(píng)分的商品共有4 894次；Arts類別下含1 659個(gè)用戶和1 291種商品，用戶評(píng)分的商品數(shù)共2 812次.

4.2 評(píng)價(jià)指標(biāo)

Yelp數(shù)據(jù)集的每個(gè)類別下，我們使用5-折交叉驗(yàn)證訓(xùn)練模型.每次使用80%的數(shù)據(jù)作為訓(xùn)練集，剩下的20%作為測(cè)試集.實(shí)驗(yàn)的度量標(biāo)準(zhǔn)采用的是平方根誤差(root mean squared error,RMSE)和平均絕對(duì)誤差(mean absolute error,MAE)，這也是推薦系統(tǒng)中常用的2種度量方法.RMSE的定義如下：

4.3 對(duì)比實(shí)驗(yàn)

本節(jié)給出了我們的模型與已有模型的對(duì)比：

1) BaseMF[2].基本的矩陣分解方法通過(guò)將用戶-商品矩陣分解成用戶-矩陣和商品矩陣，該方法只用到了用戶的評(píng)分矩陣，沒(méi)用到任何的社交網(wǎng)絡(luò)信息.

2) PRM[18].這個(gè)模型考慮了用戶的個(gè)性和社交網(wǎng)絡(luò)信息，考慮了用戶和用戶之間以及用戶和商品之間的關(guān)系.

3) CircleCon3[13].基于興趣圈的推薦模型將朋友圈的新特征與評(píng)分結(jié)合起來(lái)推斷值得信任的興趣圈.

4) SocialMF[4].基于信任傳播的矩陣分解方法假設(shè)社交網(wǎng)絡(luò)連接了所有的用戶.在模型中加入了信任信息來(lái)提高推薦系統(tǒng)的準(zhǔn)確率.

5) SR[19].基于社交網(wǎng)絡(luò)的推薦系統(tǒng)不僅使用了用戶對(duì)商品的評(píng)分信息而且增加了社交網(wǎng)絡(luò)中隱含的用戶與商品間的關(guān)系，而且包括了相同的和不相同的關(guān)系.

6) CSCR.這是我們提出的基于2種正則化項(xiàng)和興趣圈的模型.與CircleCon3相比增加了專家用戶對(duì)推薦的影響.

設(shè)置矩陣分解維度d=10，正則化項(xiàng)參數(shù)λ=0.01,α=β=1.在表2和表3中，我們展示了不同模型在Yelp數(shù)據(jù)集上2種評(píng)價(jià)指標(biāo)下的結(jié)果.

Table 2 MAE Metric on Ten Categories表2 10個(gè)類別上的MAE度量結(jié)果

Table 3 RMSE Metric on Ten Categories表3 10個(gè)類別上的RMSE度量結(jié)果

從表2可以看出在MAE評(píng)價(jià)指標(biāo)下，CircleCon3的準(zhǔn)確率在前5個(gè)對(duì)比實(shí)驗(yàn)中是最高的.但是文獻(xiàn)[18]中PRM模型的效果優(yōu)于CircleCon3，這是因?yàn)椋?)我們發(fā)現(xiàn)盡管PRM用的也是Yelp數(shù)據(jù)集，但是我們的數(shù)據(jù)量明顯多于他們使用的數(shù)據(jù)量；2)從PRM數(shù)據(jù)集可以看出他們使用的用戶量更少，而商品數(shù)更多，而且每個(gè)用戶平均對(duì)很多商品有評(píng)分.PRM方法更關(guān)注的是用戶與用戶之間以及用戶與商品之間的關(guān)系，所以在用戶可以評(píng)分很多商品時(shí)模型表現(xiàn)效果會(huì)很好.相應(yīng)的CircleCon3考慮更多的則是用戶信任的朋友，所以當(dāng)用戶量很多時(shí)，模型效果可能會(huì)較好.結(jié)合我們的數(shù)據(jù)特點(diǎn)，就可以理解為什么CircleCon3的效果好于PRM了.但是我們也可以看出在某些類別，PRM的性能也可能比CircleCon3要好(如Nightlife).

在表3的RMSE度量標(biāo)準(zhǔn)下，CircleCon3，SocialMF模型效果相對(duì)較好，而SocialMF的整體效果可能稍微比CircleCon3好一些.在Arts，Hotels，Pets這些類別下，SocialMF優(yōu)于CircleCon3.這3個(gè)類別的數(shù)據(jù)特點(diǎn)是數(shù)據(jù)稀疏度相對(duì)較低.因?yàn)镾ocialMF使用的是所有可用的社會(huì)關(guān)系，所以它可能會(huì)表現(xiàn)較好.但是在其他的類別下，CircleCon3的效果則更好.

我們的模型在2種度量標(biāo)準(zhǔn)下分別是最優(yōu)的.基于興趣圈的方法使用信任的朋友及專家信息來(lái)輔助推薦.通過(guò)實(shí)驗(yàn)結(jié)果，可以看出加入專家群體的推薦效果是顯著的.因?yàn)楫?dāng)數(shù)據(jù)集中有更多的用戶而每個(gè)用戶平均評(píng)分的商品數(shù)又比較少時(shí)，在相同圈子的專家可能會(huì)對(duì)推薦有很大的影響.在表2中MAE的度量標(biāo)準(zhǔn)下我們方法的效果也并不總是最好的，在Education類別下CircleCon3的準(zhǔn)確率更高.這可能是因?yàn)檫@個(gè)類別中的用戶數(shù)和商品數(shù)都比較少，所以受專家的影響并不明顯.但整體來(lái)說(shuō)CSCR方法比前面提出的方法效果都好.

圖2(a)是baseMF，PRM，CircleCon3，CSCR這4個(gè)算法在Foursquare數(shù)據(jù)集的4個(gè)類別上MAE度量結(jié)果，圖2(b)則是RMSE度量結(jié)果.從圖2(b)中可以看出除了在Sports類別的RMSE度量上CircleCon3效果最好外，CSCR算法總體來(lái)說(shuō)效果是最好的.而CircleCon3之所以在Sports類別下RMSE值最小可能是因?yàn)樵擃悇e下用戶的偏好更傾向于他們的朋友.

Fig. 2 Algorithm results on 4 categories of Foursquare圖2 算法在Foursquareo數(shù)據(jù)集4個(gè)類別上的結(jié)果

下面我們對(duì)比了模型中參數(shù)α,β,λ分別在MAE和RMSE度量下不同取值的模型效果.實(shí)驗(yàn)選取了Activelife和Hotels兩個(gè)類別的數(shù)據(jù).其中α取值為{0,0.001,0.01,0.1,0.3,0.5,1,5,10}，β取值為{0,0.001,0.01,0.1,0.3,0.5,1,5,10}，λ取值為{0,0.001,0.01,0.05,0.1,0.3,0.5,1,10}.

圖3展示了α變化對(duì)模型的影響.可以看出當(dāng)α=1時(shí)在2種度量標(biāo)準(zhǔn)下的準(zhǔn)確率都是最高的.當(dāng)α=0時(shí)，模型不考慮朋友的影響，可以看出這時(shí)模型效果也不是最優(yōu)的.隨著α值的增大，可以看出加入朋友信息可以提高推薦性能，直到達(dá)到最優(yōu)點(diǎn)，然后再增加α值，模型效果將會(huì)下降，甚至在一個(gè)類別上會(huì)比不考慮朋友的影響還差.這是因?yàn)槟Ｐ瓦^(guò)擬合了U矩陣而對(duì)V矩陣又估計(jì)不足.

Fig. 3 The results of CSCR algorithm on two categories with the change of α圖3 CSCR算法在2個(gè)類別上隨α變化的結(jié)果

Fig. 4 The results of CSCR algorithm on two categories with the change of β圖4 CSCR算法在2個(gè)類別上隨β變化的結(jié)果

圖4給出了β值對(duì)模型的影響.當(dāng)β=0時(shí)，模型不考慮專家群體對(duì)推薦的影響，這也就是CircleCon3模型，從圖4中可以發(fā)現(xiàn)這時(shí)的模型效果并不是最優(yōu)的;隨著β值的增加模型準(zhǔn)確率越來(lái)越高直到最優(yōu),這也說(shuō)明了專家群體對(duì)推薦是有幫助的;但是再增加β值，模型準(zhǔn)確率又會(huì)下降，所以更大的β值并不一定會(huì)使推薦效果更好.

圖5則給出了λ值對(duì)模型的影響.從2個(gè)類別的數(shù)據(jù)分別在MAE和RMSE度量標(biāo)準(zhǔn)下的表現(xiàn)來(lái)說(shuō)，當(dāng)λ值在0～0.01過(guò)程中，模型效果是越來(lái)越好的；在0.01～1的過(guò)程中，模型對(duì)λ值變化并不敏感；但是當(dāng)其特別大(如λ=10)，模型的性能會(huì)迅速下降.所以對(duì)U，V的規(guī)則化的系數(shù)不應(yīng)太大.

Fig. 5 The results of CSCR algorithm on two categories with the change of λ圖5 CSCR算法在2個(gè)類別上隨λ變化的結(jié)果

4.4 用戶冷啟動(dòng)問(wèn)題

冷啟動(dòng)實(shí)驗(yàn)在Yelp數(shù)據(jù)集Nightlife，Restaurants，Shopping三個(gè)類別上進(jìn)行，對(duì)比用戶評(píng)分的商品數(shù)變化時(shí)不同算法的效果.最終給出的結(jié)果則是3個(gè)類別下的平均值.測(cè)試集根據(jù)用戶的評(píng)分?jǐn)?shù)被分成了5組，分別是：0～10，11～20，21～40，41～80，>80.

圖6(a)和圖6(b)分別表現(xiàn)了在不同的用戶評(píng)分量下的這些算法效果.圖6橫軸上的數(shù)字表示用戶給多少商品評(píng)分了，如“0～10”表示用戶評(píng)分量在0～10之間，“11～20”表示用戶評(píng)分量在11～20之間，“80～”表示用戶評(píng)分?jǐn)?shù)超過(guò)80，以此類推.圖6(a)的縱軸表示MAE值，圖6(b)的縱軸表示RMSE值.從這2幅圖可以看出，當(dāng)用戶評(píng)分的商品增加時(shí)，算法的準(zhǔn)確率也會(huì)提高；當(dāng)用戶評(píng)分的商品很少時(shí)，BaseMF算法效果很差，但是隨著評(píng)分?jǐn)?shù)目的增加，算法性能會(huì)變得越來(lái)越好.不管怎樣，從圖6(a)和圖6(b)都可以看出，我們提出的方法在Yelp數(shù)據(jù)集上MAE和RMSE的度量標(biāo)準(zhǔn)下值都最低.這是因?yàn)榛谂d趣圈的推薦不僅考慮了信任的朋友關(guān)系而且用到了專家群體的意見(jiàn)，這在推薦過(guò)程中確實(shí)是有用的.

Fig. 6 The impact on the model with different user rating counts圖6 用戶評(píng)分的商品數(shù)對(duì)模型的影響

我們的方法在5組冷啟動(dòng)實(shí)驗(yàn)組效果始終是最好的.因?yàn)槲覀兊臄?shù)據(jù)集中用戶數(shù)很多，商品數(shù)相對(duì)較少，而大部分用戶評(píng)分的商品數(shù)并不是很多，在這種情況下我們提出的基于用戶信任的朋友關(guān)系和專家的關(guān)系在推薦中就有重要的作用.從圖5中也可以得知，當(dāng)用戶評(píng)分很多商品時(shí)，算法的性能也會(huì)變得越來(lái)越好，第5組實(shí)驗(yàn)的結(jié)果彼此就非常接近了.所以用戶評(píng)分更多的商品對(duì)模型是有幫助的，但是也可以發(fā)現(xiàn)這個(gè)提升度是逐漸降低的.

5 結(jié)束語(yǔ)

本文的目標(biāo)是解決冷啟動(dòng)問(wèn)題，文中提出了一種在LBSN上基于興趣圈中社會(huì)關(guān)系的模型來(lái)提高推薦效果.具體來(lái)說(shuō)，社會(huì)關(guān)系有朋友關(guān)系和專家用戶，由此設(shè)計(jì)的2個(gè)規(guī)則化項(xiàng)作為矩陣分解目標(biāo)函數(shù)的約束項(xiàng).在CircleCon3模型的基礎(chǔ)上，我們不僅考慮了顯性的用戶信息而且考慮了隱含的關(guān)系來(lái)提高推薦系統(tǒng)的冷啟動(dòng)問(wèn)題.朋友或者專家都有自己的評(píng)分記錄，分別根據(jù)不同的興趣圈做出劃分，每個(gè)圈子中的所有商品都屬于同一類別.在Yelp和Foursquare兩個(gè)數(shù)據(jù)集上的實(shí)驗(yàn)表明本文提出的使用混合社交網(wǎng)絡(luò)信息的方法整體優(yōu)于已有方法.

[1]Bao Jie, Zheng Yu, Wilkie D, et al. Recommendations in location based social networks: A survey[J]. GeoInformatica, 2015, 19(3): 525-565

[2]Salakhutdinov R, Mnih A. Probabilistic matrix factorization[C] //Proc of the Int Conf on Machine Learning. New York: ACM, 2012: 880-887

[3]Koren Y. Factorization meets the neighborhood: A multifaceted collaborative filtering model[C] //Proc of the 14th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2008: 426-434

[4]Jamali M, Ester M. A matrix factorization technique with trust propagation for recommendation in social networks[C] //Proc of the 4th ACM Conf on Recommender Systems. New York: ACM, 2010: 135-142

[5]Ma Hao, Zhou Dengyong, Liu Chao, et al. Recommender systems with social regularization[C] //Proc of the 4th ACM Int Conf on Web Search and Data Mining. New York: ACM, 2011: 287-296

[6]Tang Jiliang, Gao Huiji, Hu Xia, et al. Exploiting homophily effect for trust prediction[C] //Proc of the 6th ACM Int Conf on Web Search and Data Mining. New York: ACM, 2013: 53-62

[7]Yu Le, Pan Rong, Li Zhangfeng. Adaptive social similarities for recommender systems[C] //Proc of the 5th ACM Conf on Recommender Systems. New York: ACM, 2011: 257-260

[8]Guo Lei, Ma Jun, Chen Zhumin. Trust strength aware social recommendation method[J]. Journal of Computer Research and Development, 2015, 52(9): 1805-1813 (in Chinese)(郭磊, 馬軍, 陳竹敏. 一種信任關(guān)系強(qiáng)度敏感的社會(huì)化推薦算法[J]. 計(jì)算機(jī)研究與發(fā)展, 2015, 52(9): 1805-1813)

[9]Huang Junming, Cheng Xueqi, Guo Jiafeng, et al. Social recommendation with interpersonal influence[C] //Proc of the 19th European Conf on Artificial Intelligence. Amsterdam, Netherlands: IOS Press, 2010: 601-606

[10]Jiang Meng, Cui Peng, Wang Fei, et al. Scalable recommendation with social contextual information[J]. IEEE Trans on Knowledge and Data Engineering, 2014, 26(11): 2789-2802

[11]Yang Yongxiang. Recommendation algorithms based on combination of matrix factorization and random walk[D]. Beijing: Beijing Jiaotong University, 2014 (in Chinese)(楊永向. 基于矩陣分解和隨機(jī)游走相結(jié)合的推薦算法[D]. 北京: 北京交通大學(xué), 2014)

[12]Wei Suyun, Xiao Jingjing, Ye Ning. Collaborative filtering algorithm based on co-clustering smoothing[J]. Journal of Computer Research and Development, 2013, 50(1): 163-169 (in Chinese)(韋素云, 肖靜靜, 業(yè)寧. 基于聯(lián)合聚類平滑的協(xié)同過(guò)濾算法[J]. 計(jì)算機(jī)研究與發(fā)展, 2013, 50(1): 163-169)

[13]Yang Xiwang, Steck H, Liu Yong. Circle-based recommendation in online social networks[C] //Proc of the 18th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2012: 1267-1275

[14]Zhao Guoshuai, Qian Xueming, Feng He. Personalized recommendation by exploring social users’ behaviors[C] //Proc of the Multi Media Modeling. Berlin: Springer, 2014: 181-191

[15]Tang Jiliang, Hu Xia, Gao Huiji, et al. Exploiting local and global social context for recommendation[C] //Proc of the Int Joint Conf on Artificial Intelligence. San Francisco, CA: Morgan Kaufmann, 2013: 264-269

[16]McPherson M, Smith-Lovin L, Cook J M. Birds of a feather: Homophily in social networks[J]. Annual Review of Sociology, 2001, 27(1): 415-444

[17]Sun Jimeng, Tang Jie. A survey of models and algorithms for social influence analysis[M] //Social Network Data Analytics. Berlin: Springer, 2011: 177-214

[18]Feng He, Qian Xueming. Recommendation via user’s personality and social contextual[C] //Proc of the 22nd ACM Int Conf on Information & Knowledge Management. New York: ACM, 2013: 1521-1524

[19]Ma Hao. An experimental study on implicit social recommendation[C] //Proc of the 36th Int ACM SIGIR Conf on Research and Development in Information Retrieval. New York: ACM, 2013: 73-82

Li Xin, born in 1989. PhD. Received his PhD degree from the University of Science and Technology of China (USTC) in 2015. His main research interests include location based services, recommender system, machine learning.

Liu Guiquan, born in 1970. PhD. Associate professor in the University of Science and Technology of China (USTC). His main research interests include data and knowledge management systems, data and text mining, multiagent systems.

Li Lin, born in 1977. PhD. Professor in Wuhan University of Technology. Her current research interests include text mining, machine learning, information retrieval and recommender system (cathylilin@whut.edu.cn).

Wu Zongda, born in 1983. PhD. Associate professor in Wenzhou University. His research interests include information retrieval and personal privacy (zongda1983@163.com).

Ding Junmei, born in 1991. Master candidate in computer science at the University of Science and Technology of China(USTC). Her main research interests include machine learning and data mining.

2015年《計(jì)算機(jī)研究與發(fā)展》高被引論文TOP10

數(shù)據(jù)來(lái)源：CSCD，中國(guó)知網(wǎng)；統(tǒng)計(jì)日期：2016-12-05

Circle-Based and Social Connection Embedded Recommendation in LBSN

Li Xin1,2, Liu Guiquan1, Li Lin3, Wu Zongda4, and Ding Junmei1

1(SchoolofComputerScienceandTechnology,UniversityofScienceandTechnologyofChina,Hefei230022)2(BigDataResearchInstitute,iFlytekCo.,Ltd,Hefei230088)3(SchoolofComputerScienceandTechnology,WuhanUniversityofTechnology,Wuhan430070)4(SchoolofComputerScienceandTechnology,OujiangCollegeWenzhouUniversity,Wenzhou,Zhejiang325035)

With the pervasiveness of GPS-enabled smart phones, people tend to share their locations online or check in at somewhere by commenting on the merchants, thus arousing the prevalence of LBSN (location based social network), which takes POIs (point-of-interests) as the center. A typical application in social networks is the recommendation system, and the most common problem in recommendation system is cold start, that is, how to recommend for the users who rarely comment on the item or share comments. In this paper, we propose a recommendation algorithm based on circle and social connections in social networks. The circle is made up by all users who visit a particular category of items and their social connections. It means he is interested in this category that a user accesses the category of items. Our algorithm considers different social connections and circles on tradition matrix factorization. The social connections we use include the relationship between friends(explicit relation) and relevant experts(implicit), which are used as the rule to optimize the matrix factorization model. Experiments are conducted on the datasets from the 5th Yelp Challenge Round and Foursquare. Experimental results demonstrate that our approach outperforms traditional matrix factorization based methods, especially in solving cold-start problem.

point-of-interests (POIs)；recommendation; interest circle; social connection; cold-start

2015-09-01；

2016-06-30

國(guó)家自然科學(xué)基金項(xiàng)目(61202171)；浙江省自然科學(xué)基金項(xiàng)目(LY15F020020)；國(guó)家“八六三”高技術(shù)研究發(fā)展計(jì)劃基金項(xiàng)目(2015AA015403) This work was supported by the National Natural Science Foundation of China (61202171), the Natural Science Foundation of Zhejiang Province (LY15F020020), and the National High Technology Research and Development Program of China (863 Program) (2015AA015403).

劉貴全(gqliu@ustc.edu.cn)

TP181