融合用戶屬性的協(xié)同過濾推薦算法在政府采購中的應用

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

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

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

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

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

1 研究現(xiàn)狀

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

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

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

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

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

表1 評分矩陣

1.2 鄰居用戶的形成

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

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

1)余弦相似度

用戶對項目的評分被看成向量。用戶的相似度被定義為用戶的評分向量夾角的余弦值，其公式如下:

其中:a，b代表兩個用戶;ai代表用戶a對項目i的評分。

2)Pearson系數(shù)法

計算公式如下:

其中:a，b代表兩個用戶;ra，i代表用戶a對項目i的評分;ˉra代表用戶a對已評分項目的評分均值;i∈T，T為a，b兩個用戶共同評分項目的集合。

3)Jaccard系數(shù)法

利用Jaccard系數(shù)來計算用戶相似度的一個優(yōu)勢就是基于此系數(shù)計算用戶間的相似度不需要評分數(shù)據(jù)。計算公式如下:

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

1.3 推薦的產(chǎn)生

基于目標用戶u的鄰居集合N可以產(chǎn)生兩類推薦:對任意項進行評分預測和Top-N推薦。

對任意項進行評分預測:已知目標用戶u的已評分集合Ru，則用戶u對任意未評分項目i的評分預測值計算方法如式(4)所示。

Top-N推薦:針對目標用戶u的每個未評價項目i計算出對應的pu，i值，將這些未評價項目按照pu，i的降序進行排列，然后將前N個項目推薦給用戶u。

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

2 算法設計

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

本文采用的數(shù)據(jù)集來自政府采購訂單信息中提取的兩部分數(shù)據(jù):采購單位和采購商品的對應信息A、采購單位類型信息B，其數(shù)據(jù)格式如圖1、2所示。

圖1 實驗數(shù)據(jù)集A格式

圖2 實驗數(shù)據(jù)集B格式

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

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

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

2.2 算法說明

基于用戶的協(xié)同過濾算法是基于用戶行為數(shù)據(jù)來進行推薦的。在電子商務中，用戶行為主要是指網(wǎng)頁瀏覽及其時長、點擊量、購買動作和評價信息等。

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

直覺上，相似的用戶就會有相似的行為。傳統(tǒng)方法在利用 Jaccard相關(guān)系數(shù)來進行用戶相似度的計算時，只考慮了用戶和購買項目之間的關(guān)聯(lián)，沒有考慮用戶本身的屬性對用戶相似度的影響。而在政府采購數(shù)據(jù)中，由于用戶單位類型很容易獲取，因此考慮將用戶類型作為相似度計算的一個重要影響因素。基于此，本文提出了一種考慮用戶自身屬性的基于用戶的協(xié)同過濾算法(MPUBCF)，其用戶相似度計算公式如下:

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

2.3 算法過程

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

輸出:推薦集S。

Begin:

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

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

2)相似度的計算

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

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

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

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

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

End

2.4 推薦評價

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

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

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

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

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

3 實驗結(jié)果分析

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

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

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

本文提出的MPUBCF算法相比傳統(tǒng)算法在準確率方面有一定的提高，特別是推薦集數(shù)目較小時，其優(yōu)勢更加明顯，有較高的實用價值。這是因為向用戶推薦時不可能推薦很多項目，太多的選擇會讓用戶無所適從，無法發(fā)揮推薦系統(tǒng)的作用;其次，在頁面上也不會預留很多空間來展示推薦項目。

4 結(jié)束語

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

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

［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］.計算機軟件，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］杜茂康，劉苗，李韶華，等.基于鄰近項目的Slope One協(xié)同過濾算法［J］.重慶郵電大學學報:自然科學版，2014，26(3):421－426.

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

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

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

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

［13］王輝，高利軍.個性化服務中基于用戶聚類的協(xié)同過濾推薦［J］.計算機應用，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］項亮.推薦系統(tǒng)實踐［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］王群勇，陳燕平.我國政府采購的價格監(jiān)測［J］.統(tǒng)計研究，2014(2):18－23.