李 梁，張海寧，李宗博，陳佳瑜

(重慶理工大學(xué)，重慶 400054)

隨著信息技術(shù)的迅猛發(fā)展，越來(lái)越多的信息以前所未有的速度產(chǎn)生并傳播。據(jù)intel的統(tǒng)計(jì)，2013年，在一分鐘內(nèi)，互聯(lián)網(wǎng)上各種設(shè)備產(chǎn)生的數(shù)據(jù)多達(dá)4 ZB?；ヂ?lián)網(wǎng)上的電子設(shè)備還在持續(xù)增加，預(yù)計(jì)到2017年將會(huì)有3倍于人口數(shù)量的電子設(shè)備接入互聯(lián)網(wǎng)［1］。龐大的數(shù)據(jù)所包含的信息給人們理解問(wèn)題和制定決策帶來(lái)了困擾，這就產(chǎn)生了“信息過(guò)載”問(wèn)題［2］。搜索引擎解決了用戶檢索信息的問(wèn)題。隨著電子商務(wù)的興起，僅僅等待用戶檢索是遠(yuǎn)遠(yuǎn)不夠的，于是推薦系統(tǒng)應(yīng)運(yùn)而生。傳統(tǒng)的廣告也可以認(rèn)為是一種推薦系統(tǒng)，只是廣告的方向性不強(qiáng)，不夠準(zhǔn)確。

推薦系統(tǒng)最初應(yīng)用在電子商務(wù)個(gè)性化服務(wù)中，目前幾乎所有的大型電子商務(wù)網(wǎng)站均使用了推薦系統(tǒng)，例如亞馬遜、淘寶、京東等。

政府采購(gòu)中，采購(gòu)人在確定購(gòu)買意向時(shí)往往由于專業(yè)知識(shí)的匱乏而不能進(jìn)行有效的決策［3］。本文結(jié)合政府采購(gòu)數(shù)據(jù)中沒(méi)有用戶反饋信息的特點(diǎn)，參考國(guó)內(nèi)外相關(guān)研究成果［4－6］，將用戶自身的屬性信息融入到用戶相似度的計(jì)算中，進(jìn)而運(yùn)用協(xié)同過(guò)濾算法進(jìn)行推薦，輔助采購(gòu)人有效確定購(gòu)買意向。

1 研究現(xiàn)狀

目前基于協(xié)同過(guò)濾算法(collaborative filtering)的個(gè)性化推薦系統(tǒng)被廣泛應(yīng)用于電子商務(wù)推薦系統(tǒng)中［7－10］。與傳統(tǒng)的基于內(nèi)容過(guò)濾的推薦不同，協(xié)同過(guò)濾算法的基本思想是根據(jù)用戶的歷史行為分析用戶的興趣，在所有用戶中尋找與目標(biāo)用戶興趣相似的用戶，綜合這些興趣相似的用戶對(duì)不同項(xiàng)目的評(píng)分，預(yù)測(cè)目標(biāo)用戶對(duì)這些項(xiàng)目的可能評(píng)分，進(jìn)而產(chǎn)生推薦［11］。

協(xié)同過(guò)濾算法采用一個(gè)m×n的評(píng)分矩陣作為輸入，根據(jù)項(xiàng)目評(píng)分情況計(jì)算用戶間的相似度，尋找與目標(biāo)用戶相似的用戶。這類用戶稱作目標(biāo)用戶的鄰居用戶。然后根據(jù)鄰居用戶的購(gòu)買、評(píng)分行為等對(duì)目標(biāo)用戶進(jìn)行相關(guān)項(xiàng)目的推薦。

一般情況下，協(xié)同過(guò)濾算法主要包括3個(gè)步驟:評(píng)分矩陣的構(gòu)建、鄰居用戶的形成和推薦的產(chǎn)生。

1.1 評(píng)分矩陣的構(gòu)建

一個(gè)典型的評(píng)分矩陣R如表1所示:在評(píng)分矩陣中，每一行代表一個(gè)用戶對(duì)所涉及項(xiàng)目的評(píng)分，這個(gè)評(píng)價(jià)可以是用戶顯式的對(duì)商品的評(píng)分(如在京東購(gòu)物后，京東會(huì)以“京豆”這種虛擬貨幣來(lái)吸引用戶對(duì)商品進(jìn)行評(píng)分)，也可以是通過(guò)用戶對(duì)項(xiàng)目的點(diǎn)擊率、瀏覽時(shí)長(zhǎng)等采用一定方法的計(jì)算得到的評(píng)分。將這些評(píng)分按某種方式映射為1～5，其中1代表不喜歡，5代表最喜歡。表格中的數(shù)字代表用戶Ui對(duì)項(xiàng)目Ij的評(píng)分。有些評(píng)分為“?”則代表用戶Ui和項(xiàng)目Ij無(wú)關(guān)聯(lián)，也就是用戶沒(méi)有購(gòu)買或?yàn)g覽過(guò)該項(xiàng)目，該項(xiàng)目是要針對(duì)此用戶進(jìn)行預(yù)測(cè)推薦的項(xiàng)目。

表1 評(píng)分矩陣

1.2 鄰居用戶的形成

根據(jù)評(píng)分矩陣尋找目標(biāo)用戶的鄰居用戶是協(xié)同過(guò)濾算法至關(guān)重要的一步［12］。為了尋找鄰居用戶，通常的做法是計(jì)算目標(biāo)用戶與其他用戶間的相似度，并依相似度從大到小排列，形成一個(gè)鄰居集合 N={u1，u2，…，un}，其中目標(biāo)用戶 u?N。也可以對(duì)用戶先進(jìn)行聚類，然后再尋找鄰居用戶［13］。

計(jì)算用戶相似度的常用方法有余弦相似度方法、Pearson系數(shù)法、Jaccard系數(shù)法等。下面給出這3種相似度計(jì)算方法的公式及說(shuō)明。

1)余弦相似度

用戶對(duì)項(xiàng)目的評(píng)分被看成向量。用戶的相似度被定義為用戶的評(píng)分向量夾角的余弦值，其公式如下:

其中:a，b代表兩個(gè)用戶;ai代表用戶a對(duì)項(xiàng)目i的評(píng)分。

2)Pearson系數(shù)法

計(jì)算公式如下:

其中:a，b代表兩個(gè)用戶;ra，i代表用戶a對(duì)項(xiàng)目i的評(píng)分;ˉra代表用戶a對(duì)已評(píng)分項(xiàng)目的評(píng)分均值;i∈T，T為a，b兩個(gè)用戶共同評(píng)分項(xiàng)目的集合。

3)Jaccard系數(shù)法

利用Jaccard系數(shù)來(lái)計(jì)算用戶相似度的一個(gè)優(yōu)勢(shì)就是基于此系數(shù)計(jì)算用戶間的相似度不需要評(píng)分?jǐn)?shù)據(jù)。計(jì)算公式如下:

其中:ai表示與用戶a有關(guān)聯(lián)的所有項(xiàng)目的集合;bj表示與用戶 b有關(guān)聯(lián)的所有項(xiàng)目的集合;card(A)表示集合A中元素的個(gè)數(shù)。特別地，若用戶a的關(guān)聯(lián)項(xiàng)目集合和用戶b的關(guān)聯(lián)項(xiàng)目集合均為空集，即ai=Φ且bi=Φ，則定義sim(a，b)=1。

1.3 推薦的產(chǎn)生

基于目標(biāo)用戶u的鄰居集合N可以產(chǎn)生兩類推薦:對(duì)任意項(xiàng)進(jìn)行評(píng)分預(yù)測(cè)和Top-N推薦。

對(duì)任意項(xiàng)進(jìn)行評(píng)分預(yù)測(cè):已知目標(biāo)用戶u的已評(píng)分集合Ru，則用戶u對(duì)任意未評(píng)分項(xiàng)目i的評(píng)分預(yù)測(cè)值計(jì)算方法如式(4)所示。

Top-N推薦:針對(duì)目標(biāo)用戶u的每個(gè)未評(píng)價(jià)項(xiàng)目i計(jì)算出對(duì)應(yīng)的pu，i值，將這些未評(píng)價(jià)項(xiàng)目按照pu，i的降序進(jìn)行排列，然后將前N個(gè)項(xiàng)目推薦給用戶u。

協(xié)同過(guò)濾技術(shù)在實(shí)際應(yīng)用中獲得了極大的成功［14］，例如:淘寶網(wǎng)的“發(fā)現(xiàn)－好貨”欄目就是根據(jù)基于項(xiàng)目的推薦進(jìn)行的展示;京東商城在瀏覽一個(gè)商品時(shí)也有一個(gè)“人氣組合”的欄目，同樣是根據(jù)基于項(xiàng)目的推薦算法計(jì)算得出的。

2 算法設(shè)計(jì)

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

本文采用的數(shù)據(jù)集來(lái)自政府采購(gòu)訂單信息中提取的兩部分?jǐn)?shù)據(jù):采購(gòu)單位和采購(gòu)商品的對(duì)應(yīng)信息A、采購(gòu)單位類型信息B，其數(shù)據(jù)格式如圖1、2所示。

圖1 實(shí)驗(yàn)數(shù)據(jù)集A格式

圖2 實(shí)驗(yàn)數(shù)據(jù)集B格式

A數(shù)據(jù)集包含兩列數(shù)據(jù)，第1列為采購(gòu)單位代碼，第2列為采購(gòu)商品代碼，中間以制表符Tab分隔，共包含42860條有效數(shù)據(jù)。其中有購(gòu)買行為的采購(gòu)人有12778個(gè)，有交易的采購(gòu)商品有12707個(gè)。

可以看出，同一采購(gòu)人購(gòu)買的同一商品在原始數(shù)據(jù)中也是要同時(shí)展現(xiàn)，不能合并，因?yàn)檫@代表了用戶購(gòu)買的頻次信息。

B數(shù)據(jù)集包含3列數(shù)據(jù)，同A數(shù)據(jù)集一樣，第1列為采購(gòu)單位代碼，不同的是，第2列為采購(gòu)單位對(duì)應(yīng)的單位類型代碼，第3列是第2列的代碼對(duì)應(yīng)的單位類型。B中共有12782條數(shù)據(jù)，包含12782個(gè)采購(gòu)單位及其對(duì)應(yīng)的34個(gè)單位類型信息。

2.2 算法說(shuō)明

基于用戶的協(xié)同過(guò)濾算法是基于用戶行為數(shù)據(jù)來(lái)進(jìn)行推薦的。在電子商務(wù)中，用戶行為主要是指網(wǎng)頁(yè)瀏覽及其時(shí)長(zhǎng)、點(diǎn)擊量、購(gòu)買動(dòng)作和評(píng)價(jià)信息等。

政府采購(gòu)數(shù)據(jù)中不包含評(píng)價(jià)信息這種顯性反饋行為，且目前也不能收集到商品的瀏覽時(shí)間和點(diǎn)擊次數(shù)等隱性反饋行為數(shù)據(jù)。從政府采購(gòu)的數(shù)據(jù)集中只能獲取到用戶的購(gòu)買記錄，得不到評(píng)分信息。Google的一項(xiàng)統(tǒng)計(jì)［15］顯示:對(duì)于大部分項(xiàng)目，用戶只有在很喜歡或很不喜歡的時(shí)候才會(huì)去評(píng)分，對(duì)于大部分普通的項(xiàng)目很少有評(píng)分信息。可見(jiàn)即使有評(píng)分系統(tǒng)，也很難說(shuō)這樣的評(píng)分信息能產(chǎn)生好的推薦結(jié)果。因此，本文不進(jìn)行用戶評(píng)分的預(yù)測(cè)填充，而是借鑒無(wú)評(píng)分?jǐn)?shù)據(jù)的推薦系統(tǒng)中常用的Jaccard相關(guān)系數(shù)的計(jì)算方法來(lái)進(jìn)行用戶相似度的計(jì)算。

直覺(jué)上，相似的用戶就會(huì)有相似的行為。傳統(tǒng)方法在利用 Jaccard相關(guān)系數(shù)來(lái)進(jìn)行用戶相似度的計(jì)算時(shí)，只考慮了用戶和購(gòu)買項(xiàng)目之間的關(guān)聯(lián)，沒(méi)有考慮用戶本身的屬性對(duì)用戶相似度的影響。而在政府采購(gòu)數(shù)據(jù)中，由于用戶單位類型很容易獲取，因此考慮將用戶類型作為相似度計(jì)算的一個(gè)重要影響因素?；诖耍疚奶岢隽艘环N考慮用戶自身屬性的基于用戶的協(xié)同過(guò)濾算法(MPUBCF)，其用戶相似度計(jì)算公式如下:

其中:sim(a，b)∈［0，1］;α 為調(diào)節(jié)參數(shù)，代表類型對(duì)用戶相似度的影響程度。k表示用戶a和用戶b的各自項(xiàng)目列表長(zhǎng)度的差的倒數(shù)，引入此參數(shù)的目的是區(qū)分擁有不同項(xiàng)目列表長(zhǎng)度的用戶之間的相似度差異。本實(shí)驗(yàn)中分別令α=0.3，0.6，0.9，這3個(gè)數(shù)值代表的影響程度為輕微、適中、嚴(yán)重。

2.3 算法過(guò)程

輸入:如圖1所示的采購(gòu)單位和采購(gòu)物品對(duì)應(yīng)數(shù)據(jù)A，如圖2所示的采購(gòu)單位和單位類型對(duì)應(yīng)數(shù)據(jù)B。

輸出:推薦集S。

Begin:

1)數(shù)據(jù)集劃分

將數(shù)據(jù)集A按照均勻分布隨機(jī)分成9份，選取其中1份作為測(cè)試集，其他8份作為訓(xùn)練集。

2)相似度的計(jì)算

根據(jù)數(shù)據(jù)集B確定α的值。若兩個(gè)用戶的類型不相同，則令α=0;若兩個(gè)用戶的類型相同，則令α分別取值0.3，0.6，0.9進(jìn)行實(shí)驗(yàn)。將選定的α代入式(5)進(jìn)行用戶相似度的計(jì)算。

3)產(chǎn)生鄰居用戶

根據(jù)步驟2)中的用戶相似度，確定目標(biāo)用戶u的鄰居用戶集合Neighbor。

4)產(chǎn)生推薦集

將步驟3)中的鄰居用戶集合Neighbor中與用戶相關(guān)聯(lián)的項(xiàng)目(即采購(gòu)商品)按出現(xiàn)頻次依次從大到小排序，選取前N個(gè)作為目標(biāo)用戶u的Top-N推薦集S。

End

2.4 推薦評(píng)價(jià)

在推薦系統(tǒng)中，主要采用用戶調(diào)查、在線實(shí)驗(yàn)和離線實(shí)驗(yàn)這3種方法來(lái)進(jìn)行系統(tǒng)指標(biāo)的評(píng)測(cè)［16］。由于離線實(shí)驗(yàn)這種方法不需要真實(shí)用戶參與，實(shí)驗(yàn)周期短，實(shí)施方便，可以快速測(cè)試大量不同算法，故本文采用該方法進(jìn)行評(píng)價(jià)。在算法過(guò)程的步驟1)，按照離線實(shí)驗(yàn)的要求將數(shù)據(jù)集劃分為訓(xùn)練集和測(cè)試集。

由于政府采購(gòu)數(shù)據(jù)中不含評(píng)分信息，且本算法也沒(méi)有采用傳統(tǒng)方法對(duì)評(píng)分進(jìn)行預(yù)測(cè)填充，對(duì)于算法的評(píng)估無(wú)法使用評(píng)分預(yù)測(cè)中常用的均方根誤差(RMSE)和平均絕對(duì)誤差(MAE)，因此本文采用Top-N推薦的準(zhǔn)確率度量值來(lái)進(jìn)行結(jié)果的評(píng)價(jià)。準(zhǔn)確率計(jì)算公式如下:

其中:S(u)是為用戶u產(chǎn)生的推薦集;I(u)是用戶u的歷史購(gòu)買項(xiàng)目集合。

通過(guò)實(shí)驗(yàn)發(fā)現(xiàn):當(dāng)α=0.6時(shí)，MPUBCF能達(dá)到最好效果;當(dāng)最近鄰居個(gè)數(shù)為2，推薦集大小在17左右時(shí)，本文提出的MPUBCF算法和傳統(tǒng)算法均達(dá)到各自的最好效果。實(shí)驗(yàn)結(jié)果如圖3所示。

圖3 MPUBCF與傳統(tǒng)算法(CLASSIC)效果對(duì)比

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

圖3顯示了兩種推薦算法的準(zhǔn)確率隨著α值和推薦集中項(xiàng)目個(gè)數(shù)的改變而變化的趨勢(shì)。

由圖3可以看出:當(dāng)α=0.3和0.9時(shí)其推薦準(zhǔn)確率和傳統(tǒng)算法基本相同，沒(méi)有明顯的效果提高;而當(dāng)α=0.6時(shí)，本文提出的MPUBCF算法的推薦準(zhǔn)確率從總體上相比傳統(tǒng)算法有所提高。α值過(guò)小或過(guò)大都會(huì)影響算法效果。

當(dāng)α=0.6時(shí)，由圖3可以看出:當(dāng)推薦集中項(xiàng)目個(gè)數(shù)小于15時(shí)，MPUBCF算法的準(zhǔn)確率是近似線性增長(zhǎng)的，而傳統(tǒng)算法的準(zhǔn)確率則徘徊在0.3以下，基本保持穩(wěn)定;當(dāng)推薦集中項(xiàng)目個(gè)數(shù)介于15和20之間時(shí)，兩種推薦算法的準(zhǔn)確率達(dá)到了各自的峰值，且MPUBCF算法相比傳統(tǒng)算法高約1個(gè)百分點(diǎn);當(dāng)推薦集中項(xiàng)目個(gè)數(shù)大于20時(shí)，兩種推薦算法的準(zhǔn)確率均開(kāi)始下降，其原因是推薦集中新增加的項(xiàng)目與用戶相關(guān)的項(xiàng)目的比值開(kāi)始減少，即推薦集中開(kāi)始引入大量與用戶非相關(guān)的項(xiàng)目。

本文提出的MPUBCF算法相比傳統(tǒng)算法在準(zhǔn)確率方面有一定的提高，特別是推薦集數(shù)目較小時(shí)，其優(yōu)勢(shì)更加明顯，有較高的實(shí)用價(jià)值。這是因?yàn)橄蛴脩敉扑]時(shí)不可能推薦很多項(xiàng)目，太多的選擇會(huì)讓用戶無(wú)所適從，無(wú)法發(fā)揮推薦系統(tǒng)的作用;其次，在頁(yè)面上也不會(huì)預(yù)留很多空間來(lái)展示推薦項(xiàng)目。

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

考慮到政府采購(gòu)領(lǐng)域的數(shù)據(jù)特點(diǎn)，本文通過(guò)改進(jìn)無(wú)評(píng)分?jǐn)?shù)據(jù)的推薦算法中的用戶相似度計(jì)算方法，提出了一種融合用戶自身屬性的基于用戶的協(xié)同過(guò)濾算法(MPUBCF)。通過(guò)對(duì)比實(shí)驗(yàn)驗(yàn)證了新算法的可行性，證實(shí)新算法在推薦效果方面有所提升。算法的不足之處在于:推薦準(zhǔn)確率最高僅有0.5左右，還有很大的提升空間。另外，很多研究結(jié)果表明:準(zhǔn)確的預(yù)測(cè)并不代表好的推薦［17］，用戶作為推薦系統(tǒng)的重要參與者，其滿意度也是評(píng)測(cè)推薦系統(tǒng)的重要指標(biāo)。

下一步研究將繼續(xù)優(yōu)化屬性參數(shù)α的取值，并考慮價(jià)格監(jiān)測(cè)問(wèn)題［18］，對(duì)本算法做進(jìn)一步的改進(jìn)，并將其應(yīng)用到實(shí)際采購(gòu)系統(tǒng)中進(jìn)行在線實(shí)驗(yàn)，提高推薦系統(tǒng)的性能，更好地協(xié)助采購(gòu)單位從事采購(gòu)活動(dòng)。

［1］Intel.What happens in an Internet Minute?［EB/OL］.［2014－05－18］.http://www.intel.com/content/www/us/en/communications/internet-minute-infographic.html.

［2］Eppler，Martin J，Jeanne Mengis.The concept of information overload:A review of literature from organization science，accounting，marketing，MIS，and related disciplines［J］.The information society，2004，20(5):325－344.

［3］Qin Z，Li D.The application research of E-Governmentprocurement in china based on business component frame-work［C］//Proceedings of the 3rd International Conference on Digital Society(ICDS’09).USA:［s.n.］，2009:30－39.

［4］Dou Yijie，Joseph Sarkis，Chunguang Bai.Government Green Procurement:A Fuzzy-DEMATEL Analysis of Barriers［J］.Springer Berlin Heidelberg，2014(8):567－589.

［5］Hong-Sik(Justin)Chung.Government Procurement in the United States-Korea Free Trade Agreement:Great Opportunities for Both Sides?［J］.Nw J Int’l L Bus，2014，34(2):299.

［6］許海玲，吳瀟.互聯(lián)網(wǎng)推薦系統(tǒng)比較研究［J］.計(jì)算機(jī)軟件，2009，20(2):350－362.

［7］ZHAO Z D，SHANG M S.User-based collaborative—filtering recommendation algorithms on hadoop［C］//Knowledge Discovery and Data Mining，WKDD’10 Third International Conference on IEEE.USA:［s.n.］，2010:478－481.

［8］杜茂康，劉苗，李韶華，等.基于鄰近項(xiàng)目的Slope One協(xié)同過(guò)濾算法［J］.重慶郵電大學(xué)學(xué)報(bào):自然科學(xué)版，2014，26(3):421－426.

［9］王越，程昌正.協(xié)同過(guò)濾算法在電影推薦中的應(yīng)用［J］.四川兵工學(xué)報(bào)，2014(5):86－88.

［10］廉飚，王莉，裴艷艷.一種基于子周期社區(qū)挖掘的電視節(jié)目推薦方法［J］.太原理工大學(xué)學(xué)報(bào)，2013，44(3):352－355.

［11］吳顏，沈潔，顧天竺，等.協(xié)同過(guò)濾推薦系統(tǒng)中數(shù)據(jù)稀疏 問(wèn)題的解決［J］.計(jì)算機(jī)應(yīng)用研究，2007，24(6):94－97.

［12］羅新，歐陽(yáng)元新.通過(guò)相似度支持度優(yōu)化基于K近鄰的協(xié)同過(guò)濾算法［J］.計(jì)算機(jī)學(xué)報(bào)，2010，33(8):1437－1445.

［13］王輝，高利軍.個(gè)性化服務(wù)中基于用戶聚類的協(xié)同過(guò)濾推薦［J］.計(jì)算機(jī)應(yīng)用，2007，27(5):1225－1227.

［14］Pazzani M.A framework for collaborative，content-based，and demographic filtering［J］.Artificial Intelligence Review，1999，13(5/6):393－408.

［15］Shiva Rajaraman.Five Stars Dominate Ratings［EB/OL］.［2009－11－ 12］.http://youtube-global.blogspot.com/2009/09/five-stars-dominate-ratings.html.

［16］項(xiàng)亮.推薦系統(tǒng)實(shí)踐［M］.北京:人民郵電出版社，2012:20.

［17］Sean M McNee，John Riedl，Joseph A.Konstan.Being accurate is not enough:how accuracy metrics have hurt recommender systems［C］//CHI’06 Extended Abstracts on Human Factors in Computing Systems(CHI EA’06).USA:［s.n.］，2006:1097－1101.

［18］王群勇，陳燕平.我國(guó)政府采購(gòu)的價(jià)格監(jiān)測(cè)［J］.統(tǒng)計(jì)研究，2014(2):18－23.