孫麗梅，李　悅，Ejike Ifeanyi Michael，曹科研

(沈陽(yáng)建筑大學(xué) 信息與控制工程學(xué)院，沈陽(yáng) 110168)(*通信作者電子郵箱limeisun@126.com)

0　引言

在當(dāng)今大數(shù)據(jù)時(shí)代，各種基于互聯(lián)網(wǎng)的信息系統(tǒng)普遍存在嚴(yán)重的信息過(guò)載問(wèn)題。推薦系統(tǒng)可以通過(guò)對(duì)信息進(jìn)行過(guò)濾從而為用戶提供個(gè)性化的推薦結(jié)果，因此已經(jīng)成為大數(shù)據(jù)時(shí)代信息處理的有效工具。協(xié)同過(guò)濾算法是推薦系統(tǒng)中最常用的算法之一，它無(wú)需像基于內(nèi)容的推薦算法[1-3]那樣考慮內(nèi)容的表示形式和相似度計(jì)算方法，而是主要通過(guò)推薦系統(tǒng)中用戶的歷史行為數(shù)據(jù)獲取用戶或項(xiàng)目的偏好特征進(jìn)行預(yù)測(cè)，來(lái)向用戶推薦感興趣的商品或信息[4]。協(xié)同過(guò)濾算法通常分為基于記憶(Memory-based)的協(xié)同過(guò)濾和基于模型(Model-based)的協(xié)同過(guò)濾，其中基于記憶的協(xié)同過(guò)濾應(yīng)用較廣，又分為基于用戶(User-based)的協(xié)同過(guò)濾和基于項(xiàng)目(Item-based)的協(xié)同過(guò)濾[5-7]，這類推薦算法先根據(jù)歷史數(shù)據(jù)進(jìn)行訓(xùn)練，然后根據(jù)訓(xùn)練結(jié)果預(yù)測(cè)目標(biāo)用戶對(duì)項(xiàng)目的評(píng)分，最后將評(píng)分高的項(xiàng)目推薦給用戶。

推薦系統(tǒng)面臨的主要問(wèn)題中，數(shù)據(jù)稀疏問(wèn)題一直是影響推薦質(zhì)量的重要原因之一。推薦系統(tǒng)中，由于每個(gè)用戶選擇的項(xiàng)目數(shù)量有限，因此用戶對(duì)大多數(shù)項(xiàng)目的評(píng)分為空，導(dǎo)致預(yù)測(cè)不準(zhǔn)確，這就是數(shù)據(jù)稀疏問(wèn)題。為了解決數(shù)據(jù)稀疏問(wèn)題，一些研究者提出通過(guò)基于隨機(jī)游走[8]、多層最近鄰[9]、概率矩陣分解建模[10]等方法先對(duì)空評(píng)分預(yù)測(cè)。這些方法雖然在一定程度上提高了推薦精度，但也增加了算法的復(fù)雜性，不利于在線推薦。另一些研究者提出通過(guò)奇異值分解(Singular Value Decomposition, SVD)減少項(xiàng)目空間維數(shù)的方法[11-12]，但降維會(huì)導(dǎo)致信息損失，在項(xiàng)目空間維數(shù)很高時(shí)降維的效果難以保證[13]。因此，本文考慮選擇實(shí)時(shí)性較好的在線推薦算法來(lái)進(jìn)一步緩解數(shù)據(jù)稀疏問(wèn)題，因?yàn)閷?shí)時(shí)性較好的推薦算法可以使新的評(píng)分記錄迅速補(bǔ)充到歷史評(píng)分記錄中，能有效解決歷史評(píng)分的數(shù)據(jù)稀疏問(wèn)題。

Slope One[14]算法本質(zhì)上是一種基于項(xiàng)目的協(xié)同過(guò)濾推薦算法，與其他的基于項(xiàng)目的推薦算法不同，該算法采用項(xiàng)目之間的歷史評(píng)分差來(lái)度量項(xiàng)目之間的相似程度，然后對(duì)項(xiàng)目評(píng)分進(jìn)行預(yù)測(cè)，對(duì)稀疏數(shù)據(jù)有較好的適應(yīng)性。由于Slope One算法易于實(shí)現(xiàn)、預(yù)測(cè)速度快[15]，比傳統(tǒng)的Item-based協(xié)同過(guò)濾算法預(yù)測(cè)精度高[16]，被應(yīng)用于許多在線推薦系統(tǒng)中，如hitflip DVD推薦系統(tǒng)、Value Investing News 股票新聞網(wǎng)站、AllTheBests 購(gòu)物推薦引擎等。

雖然Slope One算法比較適合實(shí)時(shí)在線評(píng)分預(yù)測(cè)，但在訓(xùn)練階段需要花費(fèi)大量時(shí)間計(jì)算任意兩個(gè)項(xiàng)目的評(píng)分差。由于推薦系統(tǒng)的評(píng)分表中只保存單個(gè)用戶對(duì)單個(gè)項(xiàng)目的評(píng)分，計(jì)算任意兩個(gè)項(xiàng)目的評(píng)分差相當(dāng)于數(shù)據(jù)庫(kù)中評(píng)分表的自連接操作，時(shí)間和空間開銷極大，因此算法的訓(xùn)練階段通常需要離線進(jìn)行。而推薦系統(tǒng)往往應(yīng)用于數(shù)據(jù)規(guī)模增長(zhǎng)迅速、全年不間斷運(yùn)行的大型電子商務(wù)系統(tǒng)，在離線訓(xùn)練的間隔內(nèi)，評(píng)分?jǐn)?shù)據(jù)仍在迅速增長(zhǎng)。

本文在Slope One算法的基礎(chǔ)上進(jìn)一步簡(jiǎn)化Slope One算法中最耗時(shí)的計(jì)算評(píng)分差的步驟，以項(xiàng)目的歷史平均分計(jì)算不同項(xiàng)目之間的評(píng)分差，進(jìn)而提出了Simplified Slope One算法。這樣一方面可以降低算法的時(shí)間復(fù)雜度和空間復(fù)雜度，使之無(wú)需耗時(shí)的離線計(jì)算，更加適用于需要實(shí)時(shí)推薦的在線推薦系統(tǒng)；另一方面，簡(jiǎn)化后的算法不需要兩個(gè)項(xiàng)目被相同的用戶評(píng)價(jià)過(guò)才能計(jì)算評(píng)分差，任何兩個(gè)項(xiàng)目只要有歷史評(píng)分記錄就可以計(jì)算評(píng)分差，有效提高了評(píng)分?jǐn)?shù)據(jù)的利用率，對(duì)稀疏數(shù)據(jù)有更好的適應(yīng)性。

本文提出的Simplified Slope One算法預(yù)測(cè)準(zhǔn)確性與原Slope One算法接近，除了保持Slope One算法原有的簡(jiǎn)單有效特性之外，主要具有以下特點(diǎn)：1)比原Slope One算法更易于實(shí)現(xiàn)和維護(hù)；2)降低了原Slope One算法的時(shí)間復(fù)雜度和空間復(fù)雜度；3)新增加的評(píng)分可以立即用于預(yù)測(cè)，易于實(shí)時(shí)在線推薦；4)提高了評(píng)分?jǐn)?shù)據(jù)利用率，解決推薦系統(tǒng)中的數(shù)據(jù)稀疏問(wèn)題。

1　Slope One及其相關(guān)算法

推薦系統(tǒng)中，假設(shè)有m個(gè)用戶和n個(gè)項(xiàng)目，設(shè)用戶集合為U={U1,U2,…,Um},項(xiàng)目集合為I={I1,I2,…,In},用戶對(duì)項(xiàng)目的評(píng)分為m×n的矩陣，用R(m,n)表示，其中rij代表用戶Ui對(duì)項(xiàng)目Ij的評(píng)分，評(píng)分為0代表未評(píng)分。評(píng)分矩陣如表1所示。

Slope One算法是一種經(jīng)典的基于評(píng)分預(yù)測(cè)的算法，采用簡(jiǎn)單的基于f(x)=x+b形式的線性回歸公式進(jìn)行預(yù)測(cè)，參數(shù)x為目標(biāo)用戶對(duì)參照項(xiàng)目的評(píng)分，參數(shù)b為參照用戶對(duì)參照項(xiàng)目和目標(biāo)項(xiàng)目評(píng)分的平均差,f(x)即為預(yù)測(cè)的目標(biāo)用戶對(duì)目標(biāo)項(xiàng)目的評(píng)分。其中b是由所有同時(shí)評(píng)價(jià)過(guò)這兩個(gè)項(xiàng)目的參照用戶求得評(píng)分差之后再求平均得到。實(shí)際預(yù)測(cè)中，會(huì)有大量的參照用戶和參照項(xiàng)目，因此需要對(duì)用戶和項(xiàng)目分別加權(quán)平均處理。

表1　評(píng)分矩陣R(m,n)Tab. 1　Rating matrix R(m,n)

圖1演示了當(dāng)只有一個(gè)參照用戶UserA和一個(gè)參照項(xiàng)目Itemi時(shí)，如何預(yù)測(cè)目標(biāo)用戶UserB對(duì)目標(biāo)項(xiàng)目Itemj的評(píng)分的方法，“？”代表用戶B對(duì)項(xiàng)目j的預(yù)測(cè)評(píng)分，計(jì)算公式為：

rBj=rBi+(rAj-rAi)

(1)

圖1　基本Slope One算法示意圖Fig. 1　Schematic diagram of basic Slope One algorithm

基本的Slope One預(yù)測(cè)算法首先采用式(2)計(jì)算目標(biāo)項(xiàng)目與參照物項(xiàng)目的平均評(píng)分差devj,k,再采用式(3)預(yù)測(cè)目標(biāo)用戶u對(duì)目標(biāo)項(xiàng)目的評(píng)分P(u)j。

(2)

(3)

其中:Ijk為評(píng)價(jià)過(guò)項(xiàng)目Ij、Ik的參照用戶集合;uj表示用戶u對(duì)項(xiàng)目Ij的評(píng)分;Rj為與項(xiàng)目Ij同時(shí)被評(píng)價(jià)過(guò)的參照項(xiàng)目集合;card(Rj)代表集合Rj中的參照項(xiàng)目個(gè)數(shù)。

Slope One算法的作者同時(shí)提出了兩種改進(jìn)算法：Weighted Slope One算法和BI-Polar Slope One算法。前者以同時(shí)評(píng)價(jià)過(guò)項(xiàng)目Ij、Ik的用戶數(shù)作為這兩個(gè)項(xiàng)目評(píng)分差的權(quán)重；后者以用戶平均分作為用戶對(duì)項(xiàng)目喜歡和不喜歡的判斷閾值，將用戶對(duì)項(xiàng)目的評(píng)分分成喜歡評(píng)分和不喜歡評(píng)分，分別計(jì)算喜歡評(píng)分差和不喜歡評(píng)分差，再加權(quán)平均進(jìn)行預(yù)測(cè)。

許多研究者在Slope One算法基礎(chǔ)上提出了一些改進(jìn)，如引入SVD進(jìn)行數(shù)據(jù)預(yù)處理[17]，采用動(dòng)態(tài)k近鄰[18]、基于用戶的協(xié)同過(guò)濾算法[19-20]對(duì)用戶進(jìn)行篩選，采用Pearson相似性計(jì)算進(jìn)行數(shù)據(jù)處理[21]，預(yù)先對(duì)項(xiàng)目進(jìn)行聚類處理[22]，對(duì)用戶進(jìn)行模糊聚類處理[23]等，這些改進(jìn)雖然可以在一定程度上提高預(yù)測(cè)評(píng)分的準(zhǔn)確性，但往往增加了算法的復(fù)雜度。因此，本文的研究重點(diǎn)是如何在不影響Slope One算法推薦準(zhǔn)確性的前提下盡量降低其時(shí)間和空間復(fù)雜度。

2　Simplified Slope One算法

2.1　Slope One算法的參照用戶和參照項(xiàng)目

Slope One算法中，用戶對(duì)項(xiàng)目的預(yù)測(cè)評(píng)分可由參照用戶對(duì)參照項(xiàng)目的評(píng)分計(jì)算得到。被同一用戶評(píng)價(jià)過(guò)的任意兩個(gè)項(xiàng)目可互為參照項(xiàng)目。在只有較少的參照用戶和參照項(xiàng)目時(shí)，訓(xùn)練和預(yù)測(cè)算法都比較簡(jiǎn)單，但實(shí)際推薦時(shí)，推薦系統(tǒng)中的參照用戶和參照項(xiàng)目都非常多。以Movielens數(shù)據(jù)集為例，943個(gè)用戶貢獻(xiàn)了10萬(wàn)條評(píng)分記錄，平均每個(gè)用戶評(píng)價(jià)了106個(gè)項(xiàng)目，即平均每個(gè)項(xiàng)目有105個(gè)參照項(xiàng)目。

圖2演示了用戶C預(yù)測(cè)項(xiàng)目k時(shí)，同時(shí)有2個(gè)參照用戶和2個(gè)參照項(xiàng)目時(shí)的預(yù)測(cè)過(guò)程。可以看出，預(yù)測(cè)目標(biāo)用戶對(duì)目標(biāo)項(xiàng)目的評(píng)分時(shí)，由于參照用戶和參照項(xiàng)目各代表一個(gè)維度，因此當(dāng)推薦系統(tǒng)中有m個(gè)用戶和n個(gè)項(xiàng)目時(shí)，算法的時(shí)間復(fù)雜度趨近于O(mn)。

圖2　多個(gè)參照用戶和參照項(xiàng)目的Slope One算法示意圖Fig. 2　Schematic diagram of Slope One algorithm with multiple referential users and items

2.2　Simplified Slope One算法

簡(jiǎn)化后項(xiàng)目i,j的評(píng)分差devj,i根據(jù)式(4)計(jì)算。

(4)

以圖3為例，簡(jiǎn)化后，參照用戶A、B…合并為全體用戶，用戶這個(gè)維度的時(shí)間復(fù)雜度從O(m)降至O(1)。兩個(gè)項(xiàng)目的平均分之差仍能代表兩個(gè)項(xiàng)目在評(píng)分上的差異。這個(gè)簡(jiǎn)化使原算法中由于參照用戶過(guò)多而導(dǎo)致的時(shí)間和空間復(fù)雜度較高的現(xiàn)象得到改善，另外也解決了數(shù)據(jù)稀疏問(wèn)題，因?yàn)樵谠璖lope One算法中，用戶至少貢獻(xiàn)2個(gè)以上的歷史評(píng)分才對(duì)預(yù)測(cè)其他評(píng)分有參照價(jià)值，而簡(jiǎn)化后的算法中，用戶即使只有1個(gè)歷史評(píng)分，也對(duì)項(xiàng)目歷史平均分有貢獻(xiàn)。

圖3　Simplified Slope One算法示意圖Fig. 3　Schematic diagram of Simplified Slope One algorithm

相應(yīng)地，預(yù)測(cè)目標(biāo)用戶UserC對(duì)目標(biāo)項(xiàng)目Itemj的評(píng)分公式變?yōu)椋?/p>

(5)

預(yù)測(cè)目標(biāo)用戶u對(duì)目標(biāo)項(xiàng)目j的評(píng)分p(u)j時(shí)，首先找出目標(biāo)用戶評(píng)價(jià)過(guò)的項(xiàng)目作為參照項(xiàng)目集合Rj,再根據(jù)式(6)預(yù)測(cè)評(píng)分,其中rui為目標(biāo)用戶u對(duì)參照項(xiàng)目i的歷史評(píng)分。

(6)

2.3　時(shí)間復(fù)雜度和空間復(fù)雜度分析

原Slope One算法中，由于預(yù)測(cè)采用的線性回歸模型時(shí)間復(fù)雜度較低，比較適合實(shí)時(shí)預(yù)測(cè)；但與其他推薦算法類似，訓(xùn)練的時(shí)間較長(zhǎng)，需要離線計(jì)算。推薦系統(tǒng)的歷史信息中只保存單個(gè)用戶對(duì)單個(gè)項(xiàng)目的評(píng)分，因此要想得到兩個(gè)項(xiàng)目的評(píng)分差，需要進(jìn)行復(fù)雜的連接操作。評(píng)分差簡(jiǎn)化后的Slope One算法中，較好地降低了算法訓(xùn)練的時(shí)間和空間復(fù)雜度。

設(shè)推薦系統(tǒng)中共有m個(gè)用戶，n個(gè)項(xiàng)目，N個(gè)評(píng)分。

1)訓(xùn)練階段時(shí)間復(fù)雜度對(duì)比。

原Slope One算法中，訓(xùn)練階段的主要計(jì)算單位為計(jì)算任意兩個(gè)項(xiàng)目之間的評(píng)分差。計(jì)算每對(duì)項(xiàng)目的評(píng)分差共需要n(n-1)/2 個(gè)時(shí)間單位，時(shí)間復(fù)雜度為O(n2)。而Simplified Slope One算法中只需要維護(hù)n個(gè)項(xiàng)目的平均分，因此時(shí)間復(fù)雜度為O(n)。

2)預(yù)測(cè)階段時(shí)間復(fù)雜度對(duì)比。

預(yù)測(cè)階段的主要計(jì)算單位為查找任意兩個(gè)項(xiàng)目的評(píng)分差。原Slope One算法中，查找每對(duì)項(xiàng)目的評(píng)分差需要用兩個(gè)項(xiàng)目id作為關(guān)鍵字進(jìn)行查找，雙關(guān)鍵字查找次數(shù)與具體數(shù)據(jù)庫(kù)的實(shí)現(xiàn)有關(guān)，時(shí)間復(fù)雜度介于O(n)和O(n2)之間。Simplified Slope One算法中，只需要分別查找這兩個(gè)項(xiàng)目的平均分，然后增加一次減法計(jì)算，時(shí)間復(fù)雜度仍為O(n)。

3)空間復(fù)雜度對(duì)比。

原Slope One算法中，要存儲(chǔ)任意兩個(gè)項(xiàng)目之間的評(píng)分差，需存儲(chǔ)2個(gè)項(xiàng)目id、總評(píng)分次數(shù)、總評(píng)分差，假設(shè)各字段所需單位相同，所需存儲(chǔ)空間為4n(n-1)/2=2n(n-1)，即空間復(fù)雜度為O(n2)。而Simplified Slope One算法中只需要存儲(chǔ)n個(gè)項(xiàng)目的項(xiàng)目id、總評(píng)分次數(shù)、總評(píng)分，所需空間為3n,因此空間復(fù)雜度仍為O(n)。

Simplified Slope One算法在時(shí)間復(fù)雜度和空間復(fù)雜度方面都優(yōu)于原Slope One算法。

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

3.1　時(shí)間敏感的Movielens數(shù)據(jù)集分析

本文采用推薦系統(tǒng)研究中常用的由美國(guó)明尼蘇達(dá)大學(xué)GroupLens研究小組提供的Movielens電影評(píng)分?jǐn)?shù)據(jù)集(10萬(wàn)條評(píng)分版本)進(jìn)行實(shí)驗(yàn)。該數(shù)據(jù)集包含943個(gè)用戶對(duì)1 682部電影的10萬(wàn)條評(píng)分記錄，評(píng)分范圍為1～5，每個(gè)用戶至少評(píng)價(jià)20部電影，時(shí)間跨度約7個(gè)月。數(shù)據(jù)集中的評(píng)分記錄由用戶id、項(xiàng)目id、評(píng)分、時(shí)間戳組成。MovieLens數(shù)據(jù)集的數(shù)據(jù)稀疏度為93.7%，即評(píng)分矩陣中有93.7%的評(píng)分為空。

MovieLens提供5個(gè)子數(shù)據(jù)集u1～u5，每個(gè)子數(shù)據(jù)集中包含一個(gè)訓(xùn)練集和一個(gè)測(cè)試集，分別是將全部評(píng)分記錄按80%和20%比例隨機(jī)選擇，用于交叉驗(yàn)證。查詢結(jié)果顯示，這5個(gè)子數(shù)據(jù)集并不是嚴(yán)格按照評(píng)價(jià)的時(shí)間排序的。正常情況下，訓(xùn)練集為歷史記錄，評(píng)分時(shí)間應(yīng)該先于測(cè)試集的記錄評(píng)分時(shí)間，但實(shí)際的時(shí)間戳如表2所示。

表2　Movielens數(shù)據(jù)集時(shí)間戳統(tǒng)計(jì)Tab. 2　Timestamp statistics of Movielens dataset

新用戶和新項(xiàng)目的冷啟動(dòng)問(wèn)題是數(shù)據(jù)稀疏問(wèn)題的一個(gè)特例。實(shí)驗(yàn)數(shù)據(jù)中，如果測(cè)試集中的用戶在訓(xùn)練集中無(wú)評(píng)分記錄，則視該用戶為新用戶，反之為非新用戶。同理，如果測(cè)試集中的項(xiàng)目在訓(xùn)練集中無(wú)評(píng)分記錄，則視該項(xiàng)目為新項(xiàng)目，反之為非新項(xiàng)目。這5個(gè)子數(shù)據(jù)集的測(cè)試集中非新用戶和非新項(xiàng)目的統(tǒng)計(jì)結(jié)果如表3所示。

由表3統(tǒng)計(jì)結(jié)果可知，在這5個(gè)子數(shù)據(jù)集中，測(cè)試集中根本不存在新用戶，新項(xiàng)目的比例平均為2.2%。以u(píng)5為例，整個(gè)測(cè)試集的20 000條評(píng)分記錄中，非新用戶對(duì)非新項(xiàng)目的評(píng)分?jǐn)?shù)為19 964，占全部評(píng)分記錄的99.8%。因此可見，采用Movielens數(shù)據(jù)集中事先劃分好的u1～u5子數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)時(shí)由于新用戶和新項(xiàng)目引起的冷啟動(dòng)問(wèn)題比較少。

在實(shí)際應(yīng)用中，推薦系統(tǒng)的訓(xùn)練集為歷史記錄，評(píng)分時(shí)間應(yīng)先于測(cè)試集的記錄評(píng)分時(shí)間。因此，應(yīng)依據(jù)此原則劃分?jǐn)?shù)據(jù)集，即將全部評(píng)分?jǐn)?shù)據(jù)先按照時(shí)間戳排序后再按比例劃分成訓(xùn)練集和測(cè)試集，簡(jiǎn)稱時(shí)間戳數(shù)據(jù)集。例如按80%比例劃分訓(xùn)練集時(shí)，將按照時(shí)間戳排序的全部評(píng)分記錄的前80%作為訓(xùn)練集，后20%作為測(cè)試集，這樣劃分得到的數(shù)據(jù)集為80%時(shí)間戳數(shù)據(jù)集。表4為分別按50%～90%比例劃分訓(xùn)練集時(shí)，測(cè)試集中的非新用戶和非新項(xiàng)目所占比例情況。

由表4可知，按照時(shí)間戳劃分的測(cè)試集中，新用戶的比例非常高，平均達(dá)到65.1%，新項(xiàng)目平均約為7.8%。同時(shí)也可以看出，隨著訓(xùn)練集比例的擴(kuò)大，非新用戶和非新項(xiàng)目的比例上升比較明顯。

表3　Movielens子數(shù)據(jù)集中的非新用戶和非新項(xiàng)目統(tǒng)計(jì)Tab. 3　Statistics of non-new users and non-new items in Movielens subdataset

表4　按時(shí)間戳劃分?jǐn)?shù)據(jù)集中的非新用戶和非新項(xiàng)目統(tǒng)計(jì)Tab. 4　Statistics of non-new users and non-new items by using timestamp of dataset

Movielens數(shù)據(jù)集本身已經(jīng)經(jīng)過(guò)篩選，只保留了評(píng)分?jǐn)?shù)在20以上的用戶的評(píng)分?jǐn)?shù)據(jù)，因此，真實(shí)的推薦系統(tǒng)中數(shù)據(jù)稀疏問(wèn)題和冷啟動(dòng)問(wèn)題將更加嚴(yán)重。

本文采用推薦系統(tǒng)中常用的平均絕對(duì)偏差(Mean Absolute Error, MAE)作為預(yù)測(cè)評(píng)分準(zhǔn)確性的度量標(biāo)準(zhǔn)，其計(jì)算公式如式(7)所示，MAE值越小越好。其中測(cè)試集中的評(píng)分?jǐn)?shù)為N,實(shí)際用戶評(píng)分集合為{q1,q2,…,qN}，預(yù)測(cè)得到的評(píng)分集合為{p1,p2,…,pN}。

(7)

新用戶和新項(xiàng)目在測(cè)試集中所占的比例直接影響預(yù)測(cè)評(píng)分的準(zhǔn)確性。以常用的基于用戶的協(xié)同過(guò)濾(User-Based Collaborative Filtering, UBCF)推薦算法和Weighted Slope One算法為例，在不按時(shí)間戳排序劃分的數(shù)據(jù)集u1～u5上的MAE測(cè)試結(jié)果比按照時(shí)間戳排序取前80%作為訓(xùn)練集劃分的數(shù)據(jù)集(以下簡(jiǎn)稱timestamp80)低13.5%。測(cè)試時(shí)近鄰數(shù)k默認(rèn)設(shè)置為10，測(cè)試結(jié)果如表5所示。

從表5中可看出，測(cè)試集中新用戶和新項(xiàng)目的比例越高，MAE越大，表明評(píng)分預(yù)測(cè)越不準(zhǔn)確，因?yàn)橹挥蟹切掠脩艉头切马?xiàng)目的歷史評(píng)分才能貢獻(xiàn)預(yù)測(cè)。而時(shí)間戳數(shù)據(jù)集timestamp80中，數(shù)據(jù)的稀疏程度遠(yuǎn)遠(yuǎn)高于u1～u5子數(shù)據(jù)集。真實(shí)的推薦系統(tǒng)中，歷史數(shù)據(jù)必然先發(fā)生于測(cè)試數(shù)據(jù)，也就是說(shuō)，要模擬真實(shí)的推薦系統(tǒng)，應(yīng)該嚴(yán)格按照時(shí)間戳來(lái)劃分訓(xùn)練集和測(cè)試集。因此本文的實(shí)驗(yàn)在對(duì)MovieLens數(shù)據(jù)集按照時(shí)間戳排序后劃分得到的訓(xùn)練集和測(cè)試集上進(jìn)行。

表5　Movielens和timestamp80數(shù)據(jù)集的平均絕對(duì)偏差對(duì)比Tab. 5　MAE comparison of Movielens and timestamp80 dataset

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

將Simplified Slope One算法同改進(jìn)前的Weighted Slope One算法、BI-Polar Slope One算法以及傳統(tǒng)的基于用戶的協(xié)同過(guò)濾算法UBCF(k=10)進(jìn)行對(duì)比實(shí)驗(yàn)。實(shí)驗(yàn)采用的數(shù)據(jù)集為Movielens數(shù)據(jù)集全部943個(gè)用戶對(duì)1 682部電影的10萬(wàn)條評(píng)分記錄。為了模擬真實(shí)的推薦系統(tǒng)環(huán)境，所有評(píng)分記錄嚴(yán)格按照時(shí)間戳排序，然后依照訓(xùn)練集比例依次從50%～90%劃分出訓(xùn)練集，剩余記錄為測(cè)試集。實(shí)驗(yàn)環(huán)境的主要參數(shù)如下：Intel Core i7- 4510U CPU；8 GB內(nèi)存；Windows 8.1(64位)操作系統(tǒng)；MySQL 5.5數(shù)據(jù)庫(kù)；jdk1.7開發(fā)環(huán)境；Java語(yǔ)言。

表6所示為隨機(jī)抽取500個(gè)用戶，按50%比例劃分訓(xùn)練集和測(cè)試集時(shí)，各算法的訓(xùn)練時(shí)間和數(shù)據(jù)存儲(chǔ)空間的對(duì)比。可以看出，由于推薦系統(tǒng)中的項(xiàng)目數(shù)比用戶數(shù)大得多，因此基于項(xiàng)目的Weighted Slope One和BI-polar Slope One算法的訓(xùn)練時(shí)間和存儲(chǔ)空間都遠(yuǎn)遠(yuǎn)大于基于用戶的UBCF算法；而本文提出的Simplified Slope One算法雖然也是基于項(xiàng)目的推薦算法，但由于簡(jiǎn)化后降低了時(shí)間復(fù)雜度和空間復(fù)雜度，因此，其訓(xùn)練時(shí)間和數(shù)據(jù)存儲(chǔ)空間均遠(yuǎn)遠(yuǎn)小于其他算法。

表6　訓(xùn)練時(shí)間和數(shù)據(jù)存儲(chǔ)空間對(duì)比Tab. 6　Comparison of training time and data storage space

圖4、5為各算法預(yù)測(cè)評(píng)分準(zhǔn)確性的測(cè)試結(jié)果，通過(guò)計(jì)算推薦算法對(duì)測(cè)試數(shù)據(jù)集中用戶的預(yù)測(cè)評(píng)分與其實(shí)際評(píng)分之間的平均差來(lái)度量預(yù)測(cè)評(píng)分的準(zhǔn)確性，采用的準(zhǔn)確性度量指標(biāo)為平均絕對(duì)偏差MAE。其中圖4為隨機(jī)抽取500個(gè)用戶的結(jié)果，圖5則為采用全部943個(gè)用戶的結(jié)果。

從圖4、5中可以看出，在嚴(yán)格按照時(shí)間戳排序后劃分的數(shù)據(jù)集中，MAE整體偏高，這是由于新用戶和新項(xiàng)目所占比例較高，數(shù)據(jù)較稀疏。但本文提出的Simplified Slope One算法與原來(lái)的Weighted Slope One算法的MAE幾乎重合，圖5中，僅在訓(xùn)練集比例超過(guò)80%之后略高于Weighted Slope One算法，而通常推薦系統(tǒng)中訓(xùn)練集在全部數(shù)據(jù)中所占比例都小于80%，這表明本文提出的Simplified Slope One算法雖然簡(jiǎn)化了原算法的計(jì)算評(píng)分差過(guò)程，但對(duì)預(yù)測(cè)評(píng)分的準(zhǔn)確性影響較小，而且無(wú)論時(shí)間復(fù)雜度還是空間復(fù)雜度都降低至僅為O(n),遠(yuǎn)優(yōu)于Weighted Slope One算法和BI-polar Slope One算法,因此，Simplified Slope One算法能更好地適應(yīng)數(shù)據(jù)規(guī)模增長(zhǎng)迅速的推薦系統(tǒng)。

圖4　算法的MAE對(duì)比(隨機(jī)選取500個(gè)用戶)Fig. 4　MAE Comparison among algorithms (500 randomly selected users)

圖5　算法的MAE對(duì)比(采用全部943個(gè)用戶)Fig. 5　MAE Comparison among algorithms (all 943 users)

4　結(jié)語(yǔ)

本文提出了Simplified Slope One算法，以項(xiàng)目的歷史平均評(píng)分之差代替原Slope One算法中相同用戶同時(shí)評(píng)價(jià)兩項(xiàng)目得到的評(píng)分差。由于推薦系統(tǒng)中只保存單個(gè)用戶對(duì)單個(gè)項(xiàng)目的評(píng)分，因此原算法中需要執(zhí)行耗時(shí)的表連接操作才能得到任意兩項(xiàng)目的評(píng)分差，而簡(jiǎn)化后的Simplified Slope One算法將時(shí)間復(fù)雜度和空間復(fù)雜度均降低至O(n)。此外，Simplified Slope One算法不需要用戶同時(shí)評(píng)價(jià)兩個(gè)項(xiàng)目才能計(jì)算評(píng)分差，使任何兩個(gè)項(xiàng)目只要有歷史評(píng)分記錄就可以計(jì)算評(píng)分差，因而有效提高了評(píng)分?jǐn)?shù)據(jù)的利用率。Simplified Slope One算法減少了訓(xùn)練時(shí)間以后，可以縮短訓(xùn)練周期，使新的評(píng)分記錄迅速補(bǔ)充到歷史記錄中，對(duì)后面的預(yù)測(cè)起到訓(xùn)練作用，有效地解決了測(cè)試集中的數(shù)據(jù)稀疏問(wèn)題。在按照時(shí)間戳排序后劃分的Movielens數(shù)據(jù)集上的測(cè)試結(jié)果表明，Simplified Slope One算法對(duì)評(píng)分預(yù)測(cè)的準(zhǔn)確性與原 Slope One算法非常接近，但時(shí)間復(fù)雜度和空間復(fù)雜度均優(yōu)于原Slope One算法，因此更適合在數(shù)據(jù)規(guī)模增長(zhǎng)迅速的大型推薦系統(tǒng)中應(yīng)用。

參考文獻(xiàn):

[1]LOPS P, de GEMMIS M, SEMERARO G, et al. Content-based and collaborative techniques for tag recommendation: an empirical evaluation [J]. Journal of Intelligent Information Systems, 2013, 40(1): 41-61.

[2]FENG S, CAO J, WANG J, et al. Recommendations based on comprehensively exploiting the latent factors hidden in items’ ratings and content [J]. ACM Transactions on Knowledge Discovery from Data, 2017, 11(3): Article No. 35.

[3]GEORGIOU T, EL ABBADI A, YAN X. Extracting topics with focused communities for social content recommendation [C]// Proceedings of the 2017 ACM Conference on Computer Supported Cooperative Work and Social Computing. New York: ACM, 2017: 1432-1443.

[4]ALEXANDRIDIS G, SIOLAS G, STAFYLOPATIS A. Enhancing social collaborative filtering through the application of non-negative matrix factorization and exponential random graph models [J]. Data Mining & Knowledge Discovery, 2017, 31(4): 1031-1059.

[5]WANG J, DE VRIES A P, REINDERS M J T. Unifying user-based and item-based collaborative filtering approaches by similarity fusion [C]// SIGIR 2006: Proceedings of the 29th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. New York: ACM, 2006: 501-508.

[6]SARWAR B, KARYPIS G, KONSTAN J, et al. Item-based collaborative filtering recommendation algorithms [C]// WWW ’01: Proceedings of the 10th International Conference on World Wide Web. New York: ACM, 2001: 285-295.

[7]JAMALI M, ESTER M. Trustwalker: a random walk model for combining trust-based and item-based recommendation [C]// KDD ’09: Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM, 2009: 397-406.

[8]YILDIRIM H, KRISHNAMOORTHY M S. A random walk method for alleviating the sparsity problem in collaborative filtering [C]// RecSys ’08: Proceedings of the 2008 ACM Conference on Recommender Systems. New York: ACM, 2008: 131-138.

[9]YIN F. Sparsity-tolerated algorithm with missing value recovering in user-based collaborative filtering recommendation [J]. Journal of Information & Computational Science, 2013, 10(15): 4939-4948.

[10]REN X, SONG M, HAIHONG E, et al. Context-aware probabilistic matrix factorization modeling for point-of-interest recommendation [J]. Neurocomputing, 2017, 241: 38-55.

[11]SARWAR B M, KARYPIS G, KONSTAN J A, et al. Application of dimensionality reduction in recommender system — a case study [C]// Proceedings of the 2000 ACM WebKDD Web Mining for E-Commerce Workshop. New York: ACM, 2000: 82-90.

[12]柴華,劉建毅.一種改進(jìn)的Slope One推薦算法研究[J].信息網(wǎng)絡(luò)安全,2015(2):77-81. (CHAI H, LIU J Y. Research on improved Slope One recommendation algorithm [J]. Netinfo Security, 2015(2): 77-81.)

[13]孫麗梅,李晶皎,孫煥良.基于動(dòng)態(tài)k近鄰的Slope One協(xié)同過(guò)濾推薦算法[J].計(jì)算機(jī)科學(xué)與探索,2011,5(9):857-864. (SUN L M, LI J J, SUN H L. Slope One collaborative filtering recommendation algorithm based on dynamick-nearest-neighborhood [J]. Journal of Frontiers of Computer Science and Technology, 2011, 5(9): 857-864.)

[14]LEMIRE D, MACLACHLAN A. Slope One predictors for online rating-based collaborative filtering [C]// SDM ’05: Proceedings of the 2005 SIAM Data Mining Conference. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM), 2005: 471-475.

[15]JANNACH D, ZANKER M, FELFERNIG A, et al.推薦系統(tǒng)[M].蔣凡,譯.北京:人民郵電出版社,2013:26-28. (JANNACH D, ZANKER M, FELFERNIG A, et al. Recommender Systems [M]. JIANG F, translated. Beijing: Posts & Telecom Press, 2013: 26-28.)

[16]董麗,邢春曉,王克宏.基于不同數(shù)據(jù)集的協(xié)作過(guò)濾算法評(píng)測(cè)[J].清華大學(xué)學(xué)報(bào)(自然科學(xué)版),2009,49(4):590-594. (DONG L, XING C X, WANG K H. Collaborative filtering algorithm evaluation for various datasets [J]. Journal of Tsinghua University (Science and Technology), 2009, 49(4): 590-594.)

[17]LIU Y, LIU D, XIE H, et al. A research on the improved Slope One algorithm for collaborative filtering [J]. International Journal of Computing Science & Mathematics, 2016, 7(3): 245-253.

[18]LI J, SUN L, WANG J. A Slope One collaborative filtering recommendation algorithm using uncertain neighbors optimizing [C]// WAIM 2011: Proceedings of the 2011 International Conference on Web-Age Information Management, LNCS 7142. Berlin: Springer, 2011: 160-166.

[19]TIAN S, OU L. An improved Slope One algorithm combining KNN method weighted by user similarity [C]// WAIM 2016: Proceedings of the 2016 International Conference on Web-Age Information Management, LNCS 9998. Cham: Springer, 2016: 88-98.

[20]王潘潘,錢謙,王鋒.改進(jìn)加權(quán)Slope One協(xié)同過(guò)濾推薦算法研究[J].傳感器與微系統(tǒng),2017,36(7):138-141. (WANG P P, QIAN Q, WANG F. Study on improved weighted Slope one collaborative filtering algorithm [J]. Transducer and Microsystem Technologies, 2017, 36(7): 138-141.)

[21]VADIVELOU G, ILAVARASAN E. Fusion of Pearson similarity and Slope One methods for QoS prediction for Web services [C]// IC3I 2015: Proceedings of the 2014 International Conference on Contemporary Computing and Informatics. Piscataway, NJ: IEEE, 2014: 1118-1124.

[22]MI Z, XU C. A recommendation algorithm combining clustering method and Slope One scheme [C]// ICIC 2011： Proceedings of the 2011 Bio-Inspired Computing and Applications — International Conference on Intelligent Computing, LNCS 6840. Berlin: Springer, 2011: 160-167.

[23]LIANG T, FAN J, ZHAO J, et al. Improved Slope One collaborative filtering predictor using fuzzy clustering [C]// ADMA 2013: Proceedings of the 2013 International Conference on Advanced Data Mining and Applications, LNCS 8346. Berlin: Springer, 2013: 181-192.