羅 斌，陳 翔

(北京理工大學(xué)管理與經(jīng)濟(jì)學(xué)院,北京 100081)

1 引言

推薦系統(tǒng)通常根據(jù)用戶的歷史行為和興趣來(lái)進(jìn)行推薦活動(dòng)，大量的用戶行為數(shù)據(jù)是推薦的基礎(chǔ)，系統(tǒng)中的新用戶或者新物品就面臨著推薦冷啟動(dòng)的問題。在社交網(wǎng)絡(luò)中，研究發(fā)現(xiàn)社交網(wǎng)絡(luò)上的用戶行為數(shù)據(jù)呈現(xiàn)冪律分布規(guī)律，存在少量的活躍用戶和大量位于長(zhǎng)尾部分的不活躍用戶，這也就是常說(shuō)的長(zhǎng)尾現(xiàn)象。對(duì)于長(zhǎng)尾部分的用戶，他們有著較少的歷史行為或者相關(guān)活動(dòng)數(shù)據(jù)，雖然不是冷啟動(dòng)，但在對(duì)這部分用戶進(jìn)行推薦的時(shí)候難免會(huì)遇到數(shù)據(jù)稀疏性問題，而長(zhǎng)尾部分的用戶卻又?jǐn)?shù)量巨大，且極具潛在的開發(fā)價(jià)值。最經(jīng)典的應(yīng)用就是亞馬遜對(duì)于長(zhǎng)尾商品的發(fā)掘，大部分商家重視暢銷商品的銷售，而忽略冷門商品，而亞馬遜銷售的圖書中冷門書籍的銷售量接近占到整體的一半。

在推薦系統(tǒng)的實(shí)際應(yīng)用中基于鄰域的算法得到了廣泛的研究和應(yīng)用[1]。它主要分為兩大類，一是基于用戶的協(xié)同過濾算法，另一個(gè)是基于物品的協(xié)同過濾算法?；谟脩舻膮f(xié)同過濾推薦算法主要有兩步：(1)找到和目標(biāo)用戶興趣相似的用戶集合；(2)找到這個(gè)集合中用戶喜歡的，且目標(biāo)用戶沒有聽說(shuō)過的物品推薦給用戶?；趨f(xié)同過濾的推薦系統(tǒng)由于算法特點(diǎn)都更傾向于推薦流行的產(chǎn)品，但由于數(shù)據(jù)稀疏的原因都不能很好地推薦長(zhǎng)尾部分物品[2]。而給用戶推薦熱門物品并不是推薦系統(tǒng)的目的，理想的推薦系統(tǒng)應(yīng)該為用戶推薦用戶感興趣并且不容易發(fā)現(xiàn)的物品。包括新浪微博在內(nèi)的應(yīng)用都希望吸引更多用戶的同時(shí)，增加用戶使用的頻度，深入發(fā)掘長(zhǎng)尾用戶的潛在價(jià)值，好的推薦帶來(lái)的用戶體驗(yàn)起到非常重要的作用。因此，推薦系統(tǒng)還要能夠幫助商家將那些被埋沒在長(zhǎng)尾中的好物品介紹給可能會(huì)對(duì)他們感興趣的用戶。Anderson在介紹長(zhǎng)尾數(shù)據(jù)在商業(yè)上的應(yīng)用時(shí)指出了發(fā)掘長(zhǎng)尾部分價(jià)值的兩個(gè)核心問題：(1)讓每一個(gè)物品都具備被銷售或推薦的可能性；(2)幫助用戶去發(fā)現(xiàn)長(zhǎng)尾部分的物品[3]。這里的第二個(gè)問題是推薦系統(tǒng)需要去解決的。

近些年來(lái)，社交網(wǎng)絡(luò)的快速發(fā)展使得這些社交應(yīng)用積累下了海量的用戶行為數(shù)據(jù)，大量的研究表明這些用戶行為數(shù)據(jù)有一些穩(wěn)定的特性規(guī)律，冪律分布特性就是其中重要的一個(gè)。Mislove等人[4]分析了Flickr、YouTube、LiveJournal和Orkut等線上社交網(wǎng)絡(luò)，發(fā)現(xiàn)其呈現(xiàn)出了冪律分布、小世界和無(wú)標(biāo)度等特性。Fu等人[5]通過分析國(guó)內(nèi)SNS社交網(wǎng)絡(luò)人人網(wǎng)，發(fā)現(xiàn)了其度分布為冪律分布。Yuta等人[6]研究了日本最大的社交網(wǎng)站Mixi，發(fā)現(xiàn)網(wǎng)絡(luò)的度為冪律分布。已有的研究中大部分集中于分析社交網(wǎng)絡(luò)數(shù)據(jù)的冪律特性，而較少涉及該特性的具體應(yīng)用，Helic等人[7]就曾指出如何處理長(zhǎng)尾部分?jǐn)?shù)據(jù)是一個(gè)待研究的有趣問題。從推薦系統(tǒng)的角度出發(fā)，通常將冪律分布分為頭部和尾部，頭部為少數(shù)幾個(gè)出現(xiàn)次數(shù)多的元素，尾部則是大量出現(xiàn)次數(shù)少的元素。頭部的元素一般為熱門的元素，熱門元素能反映出系統(tǒng)中大部分用戶的興趣喜好，但同時(shí)由于熱門元素往往眾人皆知，并不能在個(gè)性化推薦上起到較好的作用。因此，為用戶提供多樣化、個(gè)性化的推薦結(jié)果更符合用戶的需求。對(duì)于長(zhǎng)尾部分?jǐn)?shù)據(jù)的稀疏性問題和冷啟動(dòng)問題，傳統(tǒng)的解決方法主要為相似度計(jì)算的改進(jìn)、信息熵處理、隨機(jī)推薦、平均值方法和結(jié)合其他內(nèi)容信息的推薦[8]，這些解決方法各有優(yōu)缺點(diǎn)。在社交網(wǎng)絡(luò)數(shù)據(jù)量急劇增長(zhǎng)的同時(shí)，越來(lái)越多新的元素也導(dǎo)致了更為嚴(yán)重的長(zhǎng)尾問題，總體來(lái)說(shuō)長(zhǎng)尾部分的數(shù)據(jù)稀疏性問題是推薦系統(tǒng)面臨的一個(gè)挑戰(zhàn)。

作為社交網(wǎng)絡(luò)重要的特性之一，冪律特性在推薦系統(tǒng)上的應(yīng)用已經(jīng)有了一些研究，Park等人[9]提出在推薦系統(tǒng)中對(duì)尾部的資源進(jìn)行聚類后進(jìn)行推薦。Yin等人[2]針對(duì)長(zhǎng)尾推薦進(jìn)行了深入研究，通過構(gòu)建用戶-項(xiàng)目圖提出了一系列可以在長(zhǎng)尾中有效進(jìn)行個(gè)性化推薦的算法。冪律特性作為社交網(wǎng)絡(luò)中的重要特性，對(duì)于社區(qū)發(fā)現(xiàn)、用戶興趣發(fā)掘乃至用戶行為模式發(fā)掘和社交網(wǎng)絡(luò)上的搜索都有重要的應(yīng)用價(jià)值[10]。所以，如何結(jié)合冪律分布特性，充分使用冪律分布的頭部，并且對(duì)長(zhǎng)尾部分的數(shù)據(jù)進(jìn)行有效的挖掘以為用戶提供更加多樣化、個(gè)性化的推薦，解決長(zhǎng)尾部分?jǐn)?shù)據(jù)稀疏性對(duì)推薦效果的影響，充分開發(fā)長(zhǎng)尾部分的潛在價(jià)值，是一個(gè)極具研究意義的課題。

本文在分析新浪微博數(shù)據(jù)冪律特性的基礎(chǔ)上，采用Clauset等人[11]對(duì)于冪律分布研究的數(shù)學(xué)工具，結(jié)合基于用戶的協(xié)同過濾推薦算法，提出了一種結(jié)合冪律特性的混合推薦方法PowerLawCF(Collaboration Filter)來(lái)進(jìn)行個(gè)性化推薦。通過數(shù)據(jù)實(shí)證和對(duì)比實(shí)驗(yàn)證明了冪律特性在推薦系統(tǒng)上的應(yīng)用對(duì)于提高推薦效果有積極作用。

2 新浪微博數(shù)據(jù)集的冪率特性分析

在利用用戶行為數(shù)據(jù)進(jìn)行推薦算法和系統(tǒng)設(shè)計(jì)之前，首先需要對(duì)用戶行為數(shù)據(jù)進(jìn)行分析，了解數(shù)據(jù)中蘊(yùn)含的規(guī)律，以對(duì)推薦算法和系統(tǒng)的設(shè)計(jì)做相應(yīng)的指導(dǎo)。很多關(guān)于互聯(lián)網(wǎng)數(shù)據(jù)的研究發(fā)現(xiàn)，互聯(lián)網(wǎng)上的很多數(shù)據(jù)分布都滿足冪律分布，即長(zhǎng)尾分布。本文所使用的新浪微博數(shù)據(jù)也表現(xiàn)出了這一規(guī)律。這里特別需要指出的是，推薦系統(tǒng)研究中最常用的netflix和movielens的數(shù)據(jù)集經(jīng)過人為清理，去掉了很多的稀疏數(shù)據(jù)，失去了原有的規(guī)律特性。

在線社交網(wǎng)絡(luò)的興起為人類移動(dòng)行為和人類間聯(lián)系的研究提供了有效的位置數(shù)據(jù)來(lái)源。在智能手機(jī)普及之后，基于位置的社交網(wǎng)絡(luò)(Location Based Social Network)越來(lái)越受到研究者的重視。在傳統(tǒng)的社交網(wǎng)絡(luò)中加入位置分享信息后，虛擬世界的社交行為有了一條和現(xiàn)實(shí)社會(huì)生活聯(lián)通的紐帶，這給對(duì)社交網(wǎng)絡(luò)的研究帶來(lái)了無(wú)限的想象。新浪微博是目前國(guó)內(nèi)用戶人數(shù)最多的微博類社交網(wǎng)絡(luò)，它結(jié)合了限制發(fā)布內(nèi)容長(zhǎng)度和用戶社交兩大基本機(jī)制，以簡(jiǎn)單的機(jī)制迎合網(wǎng)民的潛在需求。截至2015年第三季度，新浪微博的總用戶數(shù)約為2.5億，日活躍用戶數(shù)突破1億人。因此，本文選取新浪微博的用戶簽到數(shù)據(jù)作為推薦方法的數(shù)據(jù)集進(jìn)行研究。

由于新浪微博關(guān)閉了其API接口，限制了開發(fā)者對(duì)微博數(shù)據(jù)的獲取功能，本文二次開發(fā)開源爬蟲工具webcollector，通過網(wǎng)頁(yè)爬取的方式對(duì)716位有相互關(guān)注的微博用戶的所有微博條目進(jìn)行了爬取，爬取字段包括用戶ID、微博原文、簽到位置、發(fā)微博時(shí)間、發(fā)微博日期、發(fā)微博時(shí)所用設(shè)備、評(píng)論數(shù)、點(diǎn)贊數(shù)、轉(zhuǎn)發(fā)數(shù)，總微博條目數(shù)為1 994 559條。如表1所示。

Table 1 Data samples表1 數(shù)據(jù)示例

從位置的流行度角度出發(fā)，通過繪制散點(diǎn)圖，可以發(fā)現(xiàn)簽到位置出現(xiàn)的頻次和該位置頻次的排序呈現(xiàn)出冪率分布規(guī)律，如圖1和圖2所示。

Figure 1 Frequency of check-ins圖1 簽到位置頻次圖

Figure 2 Logarithmic plot for frequency of check-ins圖2 簽到位置頻次雙對(duì)數(shù)圖

在實(shí)際數(shù)據(jù)的分析中，繪制的分布圖更多的是采用互補(bǔ)累積分布圖來(lái)接受數(shù)據(jù)所呈現(xiàn)的冪律分布現(xiàn)象，所以用互補(bǔ)累積分布函數(shù)再一次進(jìn)行數(shù)據(jù)驗(yàn)證。對(duì)簽到位置出現(xiàn)頻次的分布，構(gòu)建互補(bǔ)累積分布曲線，設(shè)x為位置出現(xiàn)的次數(shù)，P(X≥x) 為數(shù)據(jù)中位置出現(xiàn)次數(shù)不少于x的概率，數(shù)據(jù)如圖3所示。對(duì)簽到位置頻次累積分布曲線取雙對(duì)數(shù)后如圖4所示。

Figure 3 Cumulative frequency distribution of check-ins圖3 簽到位置頻次累積分布曲線圖

Figure 4 Logarithmic plot for the cumulative frequency distribution of check-ins圖4 簽到位置頻次累計(jì)分布雙對(duì)數(shù)圖

綜上所述，從對(duì)所獲得的微博數(shù)據(jù)分析中可以看出用戶的簽到次數(shù)和簽到位置出現(xiàn)次數(shù)都呈現(xiàn)出了冪率分布規(guī)律。作為復(fù)雜網(wǎng)絡(luò)的特性之一，許多自然世界的觀察數(shù)據(jù)的數(shù)理規(guī)律都有冪率分布的現(xiàn)象，作為連通各學(xué)科的數(shù)學(xué)工具，對(duì)其應(yīng)用的嘗試也必定有著深刻的意義。下文將繼續(xù)從冪率分布的數(shù)理角度進(jìn)行數(shù)據(jù)的分析處理。

3 新浪微博數(shù)據(jù)集用戶簽到次數(shù)冪律分布測(cè)算

冪率分布廣泛出現(xiàn)在物理學(xué)、生物學(xué)、地球和天體科學(xué)、經(jīng)濟(jì)學(xué)、計(jì)算機(jī)科學(xué)、人口統(tǒng)計(jì)學(xué)和社會(huì)科學(xué)中。最早對(duì)冪率分布研究做出突出貢獻(xiàn)的是Pareto和Zipf，分別發(fā)現(xiàn)了Pareto定律和Zipf定律。其他研究發(fā)現(xiàn),城市的規(guī)模、地震的強(qiáng)度、太陽(yáng)耀斑的大小、戰(zhàn)爭(zhēng)的強(qiáng)度、月球環(huán)形火山口的直徑分布、文章的被引次數(shù)、網(wǎng)頁(yè)的點(diǎn)擊次數(shù)等都呈冪率分布[11]。冪率分布作為唯一具有無(wú)標(biāo)度性的分布，被認(rèn)為是復(fù)雜網(wǎng)絡(luò)的基本特性之一，廣泛地被研究者論證。1999年Barabasi和Albert發(fā)現(xiàn)了網(wǎng)絡(luò)的無(wú)標(biāo)度性[12]是對(duì)客觀世界網(wǎng)絡(luò)系統(tǒng)具體特征的概括，這一發(fā)現(xiàn)和網(wǎng)絡(luò)的小世界現(xiàn)象[13]一起極大地激發(fā)了研究者對(duì)網(wǎng)絡(luò)科學(xué)的興趣，也把網(wǎng)絡(luò)科學(xué)理論研究從規(guī)則網(wǎng)絡(luò)和隨機(jī)網(wǎng)絡(luò)階段帶進(jìn)了復(fù)雜網(wǎng)絡(luò)研究階段。隨后許多的真實(shí)網(wǎng)絡(luò)實(shí)證研究表明了真實(shí)世界的網(wǎng)絡(luò)既不是規(guī)則網(wǎng)絡(luò)也不是隨機(jī)網(wǎng)絡(luò)，而是兼具小世界和無(wú)標(biāo)度特性的復(fù)雜網(wǎng)絡(luò)，諸如因特網(wǎng)、郵件網(wǎng)絡(luò)，以及其他各種社會(huì)、生物、物理世界的網(wǎng)絡(luò)[14 - 17]。國(guó)內(nèi)外學(xué)者已經(jīng)驗(yàn)證社交網(wǎng)絡(luò)也是典型的無(wú)標(biāo)度網(wǎng)絡(luò)[18,19]。

Newman在429篇參考文獻(xiàn)的支撐下對(duì)復(fù)雜網(wǎng)絡(luò)領(lǐng)域的發(fā)展進(jìn)行了較為全面的概括和總結(jié)，同時(shí)針對(duì)復(fù)雜網(wǎng)絡(luò)中的冪律分布現(xiàn)象從數(shù)理角度結(jié)合實(shí)證數(shù)據(jù)進(jìn)行了深入的研究。對(duì)實(shí)證數(shù)據(jù)擬合冪律分布的方法做了詳細(xì)介紹，具體論述估算冪律分布指數(shù)參數(shù)α和分布下界的估算，提出了根據(jù)特定參數(shù)生成冪律分布數(shù)據(jù)的方法。對(duì)12組自然世界的觀測(cè)數(shù)據(jù)進(jìn)行了冪律分布擬合驗(yàn)證，對(duì)比指數(shù)分布、正態(tài)分布對(duì)擬合的效果做了統(tǒng)計(jì)檢驗(yàn)，給出了觀測(cè)數(shù)據(jù)擬合冪律分布的嚴(yán)格驗(yàn)證方法[11,20]。

對(duì)于現(xiàn)有的新浪微博數(shù)據(jù)集，存在部分用戶的簽到次數(shù)特別少的情況，簽到次數(shù)過少的用戶可以認(rèn)為是推薦系統(tǒng)中的數(shù)據(jù)稀疏問題，面臨冷啟動(dòng)挑戰(zhàn)。通常的冷啟動(dòng)或者數(shù)據(jù)稀疏問題認(rèn)為是新進(jìn)入系統(tǒng)的用戶或者物品，而實(shí)際上對(duì)于不活躍的用戶也可以認(rèn)為是一種冷啟動(dòng)問題，以往的研究中沒有對(duì)該部分用戶進(jìn)行界定和劃分。本文嘗試使用社交網(wǎng)絡(luò)數(shù)據(jù)自身的內(nèi)在規(guī)律—冪律分布，通過數(shù)學(xué)測(cè)算的方式主動(dòng)鑒別系統(tǒng)中的不活躍用戶，并區(qū)分性地進(jìn)行推薦策略選擇，構(gòu)造混合推薦方法。傳統(tǒng)的推薦系統(tǒng)冷啟動(dòng)解決方法是對(duì)這一部分用戶推薦熱門物品，或者根據(jù)社交的好友關(guān)系推薦熱門物品，而往往熱門的物品已經(jīng)是用戶所接觸的，推薦效果并不理想。同時(shí)，不活躍用戶本身有少量的歷史數(shù)據(jù)，鑒于社交網(wǎng)絡(luò)物品數(shù)量巨大，且增長(zhǎng)迅速，基于物品的協(xié)同過濾算法在技術(shù)上很難實(shí)現(xiàn)，再者不活躍用戶的歷史記錄并不能準(zhǔn)確反映用戶興趣，因此本文以基于用戶的協(xié)同過濾推薦算法為基礎(chǔ)，并改進(jìn)了用戶相似度的計(jì)算。

本節(jié)在Newman對(duì)于冪律分布研究的基礎(chǔ)上，對(duì)用戶的簽到次數(shù)和該簽到次數(shù)的用戶頻數(shù)維度進(jìn)行冪律分布測(cè)算，測(cè)算的目的在于尋找數(shù)據(jù)最優(yōu)擬合特定冪律分布的范圍，并基于該范圍對(duì)數(shù)據(jù)進(jìn)行劃分，認(rèn)為截取位置之前的用戶是系統(tǒng)中不活躍的用戶。

3.1 標(biāo)度值的測(cè)算

構(gòu)建用戶的簽到次數(shù)的概率分布為p(x)=Cx-α，在計(jì)算α值時(shí)常見的方法是用曲線回歸估算，即將式(1)左右同時(shí)取對(duì)數(shù)后轉(zhuǎn)化為一元線性回歸問題，計(jì)算直線的斜率來(lái)估算α值，而這樣的計(jì)算結(jié)果存在較大的誤差。更為精確的估算方法是采用極大似然估計(jì)來(lái)求α值，引用Clauset文中[11]對(duì)極大似然估計(jì)的計(jì)算結(jié)果，估計(jì)值可以用式(1)方法求解。

(1)

根據(jù)概率分布的性質(zhì)可以計(jì)算常數(shù)C，如式(2)和式(3)所示。

(2)

(3)

通過極大似然估計(jì)求出分布的指數(shù)α值之后，極大似然估計(jì)本身并不能告訴我們這個(gè)估計(jì)的結(jié)果是否存在錯(cuò)誤、數(shù)據(jù)對(duì)于冪率分布的擬合程度是否可信、冪率分布是否是對(duì)于數(shù)據(jù)而言最好的分布模型。對(duì)此，需要進(jìn)行進(jìn)一步的檢驗(yàn)。

3.2 標(biāo)度值的檢驗(yàn)

(4)

可以算得σ的值為0.021，這里我們也通過SPSS軟件對(duì)數(shù)據(jù)的分布做了分析，擬合優(yōu)度R方為0.920 423，顯著性值趨近于0，認(rèn)為數(shù)據(jù)對(duì)于冪律分布的擬合是可信的。這里需要說(shuō)明的是，SPSS的數(shù)據(jù)參數(shù)估算方法為曲線回歸估算。

根據(jù)數(shù)據(jù)和計(jì)算得出的分布參數(shù)畫出簽到頻次分布和擬合得出的分布曲線圖如圖5所示，從圖中可以看到x趨近于零的區(qū)域有著明顯的發(fā)散，下一小節(jié)將針對(duì)該問題進(jìn)一步分析。

Figure 5 Curve of frequency distribution and fitting distribution圖5 簽到頻次分布和擬合分布曲線圖

3.3 冪率分布下界的計(jì)算

冪律分布下界的計(jì)算為我們的混合推薦方法的數(shù)據(jù)劃分提供了劃分標(biāo)準(zhǔn)。在前面的分析中發(fā)現(xiàn)，在x→0 時(shí)概率密度是發(fā)散的，所以并不是所有大于零的x值都滿足該分布，數(shù)據(jù)擬合的冪律分布存在一個(gè)下界xmin。

Figure 6 D value graph圖6 D值曲線圖

(5)

在計(jì)算D值時(shí)，需要將概率分布轉(zhuǎn)為互補(bǔ)累積分布，采用前面章節(jié)所提出的方法來(lái)擬合P(x)，根據(jù)實(shí)際數(shù)據(jù)來(lái)計(jì)算具體的累積分布函數(shù)值S(x)。 通過計(jì)算，這里列出xmin分別取1～10的D值，如圖7和表2所示。從圖7中可以看出，xmin取3時(shí)有最小的D值，所以以3作為冪律分布自變量的下界。

Figure 7 D value圖7 D值

xminDxminD10.308860.376120.277070.413930.268480.461240.275990.497150.3421100.5250

不同xmin取值時(shí)D值的變化曲線如圖6所示。

4 依據(jù)冪律分布特征的推薦

研究者們根據(jù)冪律分布特征做了大量的應(yīng)用研究。Gonzalez等人[21]對(duì)100萬(wàn)的手機(jī)用戶軌跡數(shù)據(jù)做了分析發(fā)現(xiàn)，人類的軌跡移動(dòng)模式和之前提出的萊維飛行以及隨機(jī)游走模型有很大不同，位置分布規(guī)律為一個(gè)截尾的冪律分布，認(rèn)為人類的移動(dòng)遵循一種簡(jiǎn)單的可復(fù)制模式，同時(shí)該模式也在人類的其他行為中體現(xiàn)出來(lái)。Barabsi小組[22]通過研究發(fā)現(xiàn)，包括電影演員網(wǎng)絡(luò)和電力網(wǎng)絡(luò)在內(nèi)的其他許多實(shí)際網(wǎng)絡(luò)的度分布也都服從冪律分布，并開創(chuàng)性地提出了無(wú)標(biāo)度網(wǎng)絡(luò)模型——BA 網(wǎng)絡(luò)模型。Palla等人[23]以科學(xué)合作者、詞義聯(lián)想、蛋白質(zhì)交互網(wǎng)絡(luò)這三個(gè)社會(huì)網(wǎng)絡(luò)數(shù)據(jù)做實(shí)證分析，提出了對(duì)于大型重疊社區(qū)的識(shí)別方法，并發(fā)現(xiàn)社區(qū)重疊部分的大小的累積分布呈冪律分布。羅由平等人[24]以新浪微博網(wǎng)絡(luò)之間的關(guān)注關(guān)系為基礎(chǔ)驗(yàn)證了微博網(wǎng)絡(luò)的度分布服從冪律分布，并分析了微博網(wǎng)絡(luò)的度相關(guān)性、互惠性和不同指標(biāo)下的網(wǎng)絡(luò)中心化結(jié)果，試圖以此分析微博節(jié)點(diǎn)的影響力，為研究網(wǎng)絡(luò)輿情提供幫助。Wang等人[25]發(fā)現(xiàn)之前的社區(qū)發(fā)現(xiàn)方法很少有考慮社區(qū)的冪律分布特性，因此將冪律分布特性應(yīng)用到了社區(qū)發(fā)現(xiàn)中，在使用掃描統(tǒng)計(jì)方法發(fā)現(xiàn)社區(qū)時(shí)結(jié)合了冪律分布的特性進(jìn)行社區(qū)劃分。Brach等人[26]研究了冪律分布網(wǎng)絡(luò)在最壞狀況模式下的算法復(fù)雜度，以解釋為什么真實(shí)世界的數(shù)據(jù)下算法運(yùn)行速度更快。

本節(jié)在基于用戶的協(xié)同過濾算法基礎(chǔ)上構(gòu)建了基于冪律特性的混合推薦方法PowerLawCF，對(duì)比使用基于冪律特性的推薦算法和userCF算法對(duì)于新浪微博簽到位置的推薦效果，使用準(zhǔn)確率、召回率、覆蓋率和流行度四個(gè)指標(biāo)來(lái)綜合評(píng)價(jià)推薦系統(tǒng)的離線實(shí)驗(yàn)效果。

4.1 改進(jìn)的相似度計(jì)算方法

userCF算法是推薦系統(tǒng)中最早的一批優(yōu)秀算法之一，最早應(yīng)用于郵件過濾和新聞過濾，后來(lái)的研究者們對(duì)其進(jìn)行了廣泛的研究，基于userCF的推薦系統(tǒng)在諸多推薦系統(tǒng)實(shí)踐中有很好的表現(xiàn)[27]。

相似度計(jì)算是協(xié)同過濾算法中的第一步，常見的計(jì)算方法主要有兩類：

(1)余弦相似度：

(2)皮爾森相關(guān)性：

基礎(chǔ)的相似度計(jì)算方法在大多數(shù)情況下都具有很好的使用效果，隨著研究的不斷深入，推薦系統(tǒng)面臨各種不同的使用場(chǎng)景，提出了越來(lái)越多的改進(jìn)相似度計(jì)算方法。這些改進(jìn)后的相似度計(jì)算方法更適用于具體的推薦場(chǎng)景中，而不是能在各類推薦中普遍使用的方法，研究者通常會(huì)針對(duì)推薦需要適當(dāng)?shù)馗倪M(jìn)相似度計(jì)算方法，以到達(dá)所需要的推薦效果。例如，余弦相似度在使用過程中會(huì)出現(xiàn)熱門的項(xiàng)目干擾相似度的情況，以買書來(lái)看，如果兩個(gè)用戶都買過《新華字典》，由于《新華字典》是熱門商品，幾乎每個(gè)人都曾經(jīng)買過，那么它對(duì)兩個(gè)用戶之間相似度的貢獻(xiàn)是不如兩個(gè)用戶同時(shí)購(gòu)買《推薦系統(tǒng)實(shí)踐》的，冷門的《推薦系統(tǒng)實(shí)踐》更能反映出用戶的個(gè)性化興趣。針對(duì)該問題，本文結(jié)合冪律特性進(jìn)行相似度計(jì)算的改進(jìn)，以改善推薦系統(tǒng)對(duì)于長(zhǎng)尾的推薦。

(6)

4.2 PowerLawCF

使用上一節(jié)提出的數(shù)據(jù)冪律特性擬合方法，對(duì)數(shù)據(jù)進(jìn)行劃分，獲得正常用戶數(shù)據(jù)集合不活躍用戶數(shù)據(jù)集，運(yùn)用上一節(jié)提出的相似度改進(jìn)算法作為相似度計(jì)算，對(duì)正常用戶數(shù)據(jù)集采用用戶相似度改進(jìn)的userCF算法進(jìn)行topN推薦；對(duì)于不活躍用戶數(shù)據(jù)集采用隨機(jī)推薦，構(gòu)建PowerLawCF推薦方法。

算法如下：

1.input:用戶簽到位置數(shù)據(jù)集，用戶。

2.output:對(duì)用戶的topN推薦Recomm。

3.構(gòu)建用戶簽到位置向量ui;

4.while 推薦目標(biāo)用戶

7.simPL(ux,uy);//x,y∈UPL

8. forn←0 toN

9. {L=L∩Ly;//Ly∈LocationtopN(simPL)

10.L=L-Lx;}

11.Recomm=topN(L);}

12. else{

14.L=∑Lu;

16.ReturnRecomm;

推薦算法首先利用上一節(jié)提到的冪率分布下界的計(jì)算，第5行判斷用戶簽到次數(shù)X的范圍；UPL表示位于簽到次數(shù)下界之上的活躍用戶集合，對(duì)該部分用戶使用基于冪率特性改進(jìn)的相似度計(jì)算方法進(jìn)行topN推薦；URandom表示簽到次數(shù)在下界以外的不活躍用戶，進(jìn)行隨機(jī)N個(gè)推薦。

5 實(shí)證對(duì)比

使用上文提到的新浪微博用戶數(shù)據(jù)進(jìn)行實(shí)證分析，通過訓(xùn)練集訓(xùn)練之后，使用相同測(cè)試集選取K為10的情況下兩種推薦方法的評(píng)價(jià)參數(shù)如表3所示。從兩種方法的對(duì)比結(jié)果來(lái)看，相比較PowerLawCF算法的召回率提高了28.57%，準(zhǔn)確率提高了20.26%，在改善推薦的召回率和準(zhǔn)確率的同時(shí)推薦覆蓋率提高了32.09%，并且降低了推薦位置的平均流行度，有較好的長(zhǎng)尾推薦效果。值得一提的是，這里由于使用的簽到位置數(shù)據(jù)集整體上較為稀疏，導(dǎo)致了推薦的幾個(gè)評(píng)價(jià)參數(shù)整體偏低。

Table 3 Comparison between PowerLawCF and UserCF表3 PowerLawCF算法和UserCF算法對(duì)比

在不同的K值下兩種方法的召回率和準(zhǔn)確率如圖8和圖9所示。從圖中可以看出，準(zhǔn)確率的提升不太明顯，召回率有較明顯的提高，并且在增大K值之后該提升效果有所增加。綜合來(lái)看，結(jié)合改進(jìn)后的推薦算法的推薦效果更好。

Figure 8 Recall of PowerLawCF and UserCF under different K圖8 不同K值下PowerLawCF和userCF的召回率

Figure 9 Precision of PowerLawCF and UserCF under different K圖9 不同K值下PowerLawCF和userCF的準(zhǔn)確率

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

本文從解決長(zhǎng)尾推薦問題出發(fā)，分析了推薦數(shù)據(jù)的冪律分布特性，并將該特性應(yīng)用于推薦方法的構(gòu)造中，所提出的推薦方法較之前的推薦方法在長(zhǎng)尾推薦、數(shù)據(jù)稀疏性問題以及提高推薦覆蓋率上有積極的效果，從實(shí)驗(yàn)上論證了冪律分布特性在推薦系統(tǒng)中具體應(yīng)用的價(jià)值。但是，本文還存在諸多缺陷和不足之處，例如未能使用多種不同類型的數(shù)據(jù)集進(jìn)行驗(yàn)證，以及用更多的推薦方法進(jìn)行對(duì)比；此外對(duì)于長(zhǎng)尾部分不活躍用戶的推薦，本文簡(jiǎn)單地使用了隨機(jī)推薦，對(duì)于長(zhǎng)尾部分用戶還可以進(jìn)行更為深入的推薦研究等。

推薦系統(tǒng)目前依然是研究的熱點(diǎn)問題，隨著社交網(wǎng)絡(luò)的繼續(xù)蓬勃發(fā)展，對(duì)于推薦系統(tǒng)的要求會(huì)越來(lái)越高，并且推薦方法的實(shí)際效果依賴于具體的推薦場(chǎng)景，對(duì)于推薦系統(tǒng)的研究離不開實(shí)際數(shù)據(jù)集的驗(yàn)證。如今不斷增長(zhǎng)的社交網(wǎng)絡(luò)用戶行為數(shù)據(jù)為研究者們提供了充足的研究資源，社交網(wǎng)絡(luò)用戶行為的大數(shù)據(jù)能反映出例如冪律分布特性在內(nèi)的更多更深刻的規(guī)律特性，如何挖掘出這些數(shù)據(jù)背后的內(nèi)在規(guī)律，并且應(yīng)用于具體的推薦場(chǎng)景是研究中的一個(gè)挑戰(zhàn)。如何將冪律特性和用戶興趣模型相結(jié)合進(jìn)行個(gè)性化推薦，以及如何使用冪律分布的頭部，同時(shí)對(duì)尾部進(jìn)行深度挖掘，為用戶提供更流行、更加個(gè)性化的推薦，也是一個(gè)極具研究意義的課題。此外，基于位置的社交網(wǎng)絡(luò)正在興起，對(duì)于位置維度數(shù)據(jù)在推薦系統(tǒng)中的應(yīng)用也是一個(gè)值得深入研究的課題。

參考文獻(xiàn):

[1] Ma Hong-wei,Zhang Guang-wei,Li Peng.Survey of collaborative filtering algorithms [J].Journal of Chinese Computer Systems,2009,30(7):1282-1288.(in Chinese)

[2] Yin H,Cui B,Li J,et al.Challenging the long tail recommendation [J].Proceedings of the VLDB Endowment,2012,5(9):896-907.

[3] Anderson C,Hitt M A.The long tail:Why the future of business is selling less of more[J].Academy of Management, 2007,21(2):83-85.

[4] Mislove A,Marcon M,Gummadi K P,et al.Measurement and analysis of online social networks[C]∥Proc of the 7th ACM SIGCOMM Conference on Internet Measurement,2007:29-42.

[5] Fu F,Chen X,Liu L,et al.Social dilemmas in an online social network:The structure and evolution of cooperation[J].Physics Letters A,2007,371(1):58-64.

[6] Yuta K,Ono N,Fujiwara Y.A gap in the community-size distribution of a large-scale social networking site[J].arXiv preprint physics/0701168,2007.

[7] Helic D,Strohmaier M.Building directories for social tagging systems[C]∥Proc of the 20th ACM International Conference on Information and Knowledge Management,2011:525-534.

[8] Bashir F I, Khokhar A A,Schonfeld D.Object trajectory-based activity classification and recognition using hidden Markov models[J].IEEE Transactions on Image Processing,2007,16(7):1912-1919.

[9] Park S T,Chu W.Pairwise preference regression for cold-start recommendation[C]∥Proc of the 3rd ACM Conference on Recommender Systems,2009:21-28.

[10] Wu Zhen-yu, Hu Jun,Li De-yi.Analysis of the power law characteristics in social tagging systems [J].Complex System and Complexity Science,2014,11(2):5-16.(in Chinese)

[11] Clauset A,Shalizi C R,Newman M E J.Power-law distributions in empirical data[J].SIAM Review,2009,51(4):661-703.

[12] Albert R,Jeong H,Barabási A L.Internet:Diameter of the world-wide web[J].Nature,1999,401(6749):130-131.

[13] Watts D J, Strogatz S H.Collective dynamics of small-world networks[J].Nature,1998,393(6684):440-442.

[14] Zhou Hua-ren,Ma Ya-ping,Ma Yuan-zheng,et al.Overview of development of network science [J].Computer Engineering and Applications,2009,45(24):7-10.(in Chinese)

[15] Venter J C,Adams M D,Myers E W,et al.The sequence of the human genome[J].Science,2001,291(5507):1304-1351.

[16] Girvan M,Newman M E J.Community structure in social and biological networks[J].Proceedings of the National Academy of Sciences,2002,99(12):7821-7826.

[17] Jeong H,Tombor B,Albert R,et al.The large-scale organization of metabolic networks[J].Nature,2000,407(6804):651-654.

[18] Costa L F,Rodrigues F A,Travieso G,et al.Characterization of complex networks:A survey of measurements[J].Advances in Physics,2007,56(1):167-242.

[19] Xiong Xi,Cao Wei,Zhou Xin,et al.Research on the feature model of the formation and evolution of social networks [J].Journal of Sichuan University (Engineering Science Edition),2012,44(4):140-144.(in Chinese)

[20] Newman M E J.Power laws,Pareto distributions and Zipf’s law[J].Contemporary Physics,2005,46(5):323-351.

[21] Gonzalez M C,Hidalgo C A,Barabasi A L.Understanding individual human mobility patterns[J].Nature,2008,453(7196):779-782.

[22] Barabási A L, Albert R.Emergence of scaling in random networks[J].Science,1999,286(5439):509-512.

[23] Palla G,Derényi I,Farkas I,et al.Uncovering the overlapping community structure of complex networks in nature and society[J].Nature,2005,435(7043):814-818.

[24] Luo You-ping,Zhou Zhao-min,Li Li-juan,et al.Social network discipline analysis based on power-law distribution [J].Computer Engineering,2015,41(7):299-304.(in Chinese)

[25] Wang T C,Phoa F K H,Hsu T C.Power-law distributions of attributes in community detection[J].Social Network Analysis and Mining,2015,5(1):1-10.

[26] Brach P,Cygan M,Lacki J,et al.Algorithmic complexity of power law networks[C]∥Proc of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms,2016:1306-1325.

[27] Yang Bo,Zhao Peng-fei.Overview of recommendation algorithms [J].Journal of Shanxi University(Natural Science Edition),2011,34(3):337-350.(in Chinese)

附中文參考文獻(xiàn)：

[1] 馬宏偉,張光衛(wèi),李鵬.協(xié)同過濾推薦算法綜述[J].小型微型計(jì)算機(jī)系統(tǒng),2009,30(7):1282-1288.

[10] 吳振宇,胡軍,李德毅.社會(huì)標(biāo)注系統(tǒng)冪律特性分析 [J].復(fù)雜系統(tǒng)與復(fù)雜性科學(xué),2014,11(2):5-16.

[14] 周華任,馬亞平,馬元正,等.網(wǎng)絡(luò)科學(xué)發(fā)展綜述 [J].計(jì)算機(jī)工程與應(yīng)用,2009,45(24):7-10.

[19] 熊熙,曹偉,周欣,等.社交網(wǎng)絡(luò)形成和演化的特征模型研究[J].四川大學(xué)學(xué)報(bào)(工程科學(xué)版),2012,44(4):140-144.

[24] 羅由平，周召敏，李麗娟，等.基于冪律分布的社交網(wǎng)絡(luò)規(guī)律分析[J].計(jì)算機(jī)工程，2015,41(7):299-304.

[27] 楊博,趙鵬飛.推薦算法綜述[J].山西大學(xué)學(xué)報(bào) (自然科學(xué)版),2011,34(3):337-350.