劉晉佩，曾建平

（廈門大學信息科學與技術學院，福建 廈門361005）

隨著計算機技術和網絡的迅速發(fā)展，互聯網的信息量呈爆炸式增長，信息過載成為互聯網發(fā)展所面臨的主要挑戰(zhàn).尤其在電子商務領域，信息過載問題更加突出，推薦系統(tǒng)正是解決該問題的有效手段之一.在電子商務推薦系統(tǒng)中［1］，協(xié)同過濾算法是應用最為廣泛的方法，它具有推薦效果好，實現和維護代價低等優(yōu)點，成為最成功的個性化推薦技術之一.Xerox PARC研究中心提供的Tapestry［2］被認為是第1個協(xié)同過濾推薦系統(tǒng)，該系統(tǒng)用于過濾E－mail信息和Usent文章.由于協(xié)同過濾技術是基于用戶對項目的評分數據，隨著電子商務系統(tǒng)中用戶和項目的快速增長，數據稀疏程度不斷擴大，從而造成整個推薦系統(tǒng)的準確度不斷降低.此外，推薦系統(tǒng)中新用戶和新商品的加入還會造成系統(tǒng)無法完成推薦的冷啟動問題.為了解決上述問題，需要探索新的推薦算法.

1 預備知識

Dorigo等［3］在1991年提出了蟻群算法，此后在他的其他著作中詳細地闡述了該算法的基本原理和數學模型.蟻群算法是種群進化算法中的一種，具有良好的協(xié)作和搜索能力.同時還是一種本質并行的算法，能夠迅速發(fā)現最優(yōu)解.因此，蟻群算法非常適合應用于推薦系統(tǒng)中解決由數據集稀疏帶來的問題.

根據蟻群算法［4］，一個完整的推薦系統(tǒng)可以看作是由螞蟻所代表的用戶以及螞蟻所要尋找的“食物”所代表的商品項目構成，因此，有如下假設：

1）將用戶看作是推薦系統(tǒng)中的螞蟻，螞蟻之間通過信息素進行交流；

2）將推薦系統(tǒng)中的目標商品項目看作螞蟻要尋找的“食物”；

3）螞蟻和食物之間存在很多非目標商品項目，將他們視為螞蟻覓食路徑上的節(jié)點，用戶瀏覽這些商品項目就等同于螞蟻訪問這些節(jié)點，并留下信息素.這里信息素為用戶對商品項目的評分.

設推薦系統(tǒng)中用戶的總數為M，商品項目總數為N，記用戶i對商品項目j的原始評分為a′ij，實時評分為a″ij，最終評分為aij.

用戶間相似度的計算通常是利用用戶對商品的評分信息來計算得到的［5］，其中Pearson相似性和余弦相似性是最常用的方法，由于Pearson相似性考慮了不同用戶的評分喜好，因此可以提高尋找鄰居用戶的準確度，本文計算用戶間的相似度所采用的便是Pearson相似性算法.定義用戶i1和i2共同打過分的商品項目集合為Si1i2，則用戶i1和i2之間的相似度sim（i1，i2）定義為：

目標用戶u的最近鄰居集合用Su表示［6］，在Su中的用戶是按與目標用戶的相似度從高到低排列的，則目標用戶u對未評分項目j的預測評分Puj為：

綜上，用戶i對項目j的最終評分［7］可表示為：

2 基于蟻群算法的推薦系統(tǒng)

2.1 轉移概率函數的建立

用戶在瀏覽商品時會根據瀏覽路徑上信息素的強弱來決定下一個將要瀏覽的商品，這里用禁忌表集合tabu來記錄用戶瀏覽過的商品項目，集合D＝｛1，2，…，N｝為推薦系統(tǒng)中項目的集合，用戶從項目j1轉移到項目j2的轉移概率為：

其中，allowed＝D－tabu表示用戶下一步可選擇的商品集，ηj1j2為能見度，它表示用戶從項目j1轉移到項目j2的期望程度，可根據某種啟發(fā)式函數來確定，具體形式將在下文中給出.參數α和β分別表示信息素強度和能見度在轉移概率中的相對重要性.α越大，表示用戶更傾向于選擇最近鄰居集中用戶選擇過的商品.β越大，表示用戶更傾向于選擇與當前瀏覽項目相似的商品.

2.2 啟發(fā)式函數的設計

啟發(fā)式函數的設計來源于兩部分，一部分來自于不同用戶對同一項目的評分，為保持項目的原始屬性，用項目j的原始評分向量Cj＝（a′1j，a′2j，…，a′Mj）來表示項目的評價屬性值，項目j1和j2的相似性由余弦相似性公式來表示：

余弦值越大說明Ij1和Ij2越相似.

啟發(fā)式函數的另一部分來自項目本身的屬性值.設I為m個具有l(wèi)維屬性的項目數據集合I＝｛Ii｜Ii，i＝1，2，…，m｝，其中Iij指項目i的第j個屬性值，則項目j1和j2間的相似度由歐氏距離公式來表示：

Ij1和Ij2的歐氏距離越小說明Ij1和Ij2越相似.

綜上，啟發(fā)式函數ηj1j2就可以表示為：

ηj1j2值越大，表明用戶從項目j1轉移到項目j2的期望程度越大，反之越小.

2.3 項目評分更新規(guī)則

螞蟻在它行走的過程中會在其運動軌跡上留下信息素，信息素的強弱會影響到其他螞蟻的行為，如果某條運動軌跡上的信息素越強，那么其他螞蟻選擇該軌跡的概率也就越大，當有螞蟻從這條軌跡上經過時還會繼續(xù)增加該軌跡上信息素的強度，當然，如果隨后該軌跡上沒有螞蟻經過，信息素的強度就會逐漸減弱.這里信息素的更新實質上就是項目評分的更新，推薦系統(tǒng)每做一次推薦或遍歷完所有的項目都會依據用戶的反應，更新項目的評分，更新規(guī)則如下所示：

其中，ρ（0≤ρ＜1）表示信息素揮發(fā)因子，1－ρ為信息素殘留因子，ξ為本次遍歷過程中的信息素增量.

信息素殘留因子表示不同螞蟻間相互影響的關系［8］：當信息素殘留因子過大時，之前搜索過的路徑被再次搜索的可能性會增大，降低了算法的隨機性和全局搜索能力；雖然通過減小信息素殘留因子可以提高算法的隨機性和全局搜索能力，但又會降低算法的收斂速度.ξ的初值為0，如果用戶瀏覽并購買推薦項目時，會使項目評分增加，即ξ＞0；如果用戶未瀏覽或瀏覽后未購買推薦項目時，ξ＝0.

3 實驗結果與分析

3.1 數據集

實驗采用由美國Minnesota大學的GroupLens研究小組創(chuàng)建并維護的MovieLens數據集，該數據集由943名用戶對1 682部電影的100 000條評分記錄所組成，其中，任一用戶都至少對20部電影打過評分，評分范圍是1～5，5表示“非常喜歡”，1表示“不喜歡”.評分的稀疏等級為ψ＝1－100 000／（943×1 682）＝0.93 695，可見，該數據集的評分矩陣是非常稀疏的.實驗隨機地把數據按8∶2的比例分為訓練集和測試集，訓練集用來產生實驗結果，測試集用來測試實驗結果的性能.

3.2 推薦質量的評價標準

這里采用分類準確度作為評價該算法優(yōu)劣的標準［9］，分類準確度表示的是推薦系統(tǒng)能否正確預測用戶是否喜歡某個商品的能力.網站在提供推薦服務時，一般給用戶一個個性化推薦列表，長度為L.根據預測評分對訓練集上的商品進行排序，記R（u）為用戶u在訓練集上的最可能喜歡商品列表，T（u）為用戶u在測試集上的最喜歡商品列表，Tu為用戶u在測試集上喜歡的商品數目，Npt為用戶u在R（u）和T（u）上共有的商品數目.那么對用戶u，其推薦結果的準確率Pu（L）（precision）和召回率Ru（L）（recall）分別表示為：

這里，Pu（L）表示系統(tǒng)所推薦的L個商品中用戶真正喜歡的商品所占的比例，Ru（L）表示一個用戶真正喜歡的商品能被推薦出來的概率.

3.3 實驗結果分析

實驗使用5對數據集進行測試，取5次實驗的平均值作為實驗的結果.實驗中當取ρ＝0.3，ξ＝1.5，α＝1.8，β＝1.3時，取得較好的結果.為了驗證本文提出的算法的有效性［10］，以ItemRank和 Maximum－frequency（MaxF）推薦算法作為對照，推薦長度從10增加到60，間隔為10，然后與本文提出的算法作比較，實驗結果如表1所示.

將表1中的數據轉換成圖的形式，實驗結果如圖1所示.

由于MaxF算法只是將推薦系統(tǒng)內的項按被用戶所瀏覽的次數進行簡單的降序排序，將用戶沒有看過且排序靠前的項推薦給用戶，沒有考慮項目的評價屬性和項目自身的屬性，而ItemRank算法在將用戶－項目評分二部圖轉換為相關圖時會導致用戶評分信息的丟失.本文提出的算法在運用蟻群算法強大的協(xié)作和搜索能力時，啟發(fā)式函數的設計考慮了項目的評價屬性和項目自身的屬性，提高了尋找相似項目的準確度，同時保留了協(xié)同過濾算法來尋找目標用戶的最近鄰居集.從圖1中可以看出，隨著推薦長度的增加，3種算法的準確率均降低，召回率增加，但本文提出的算法不論準確率還是召回率都比MaxF和ItemRank算法有了明顯提高，在推薦長度為40時本文提出的算法的準確率和召回率分別為27.14%和31.82%，比MaxF算法分別高出了10.82%和10.62%，比Item－Rank算法分別高出了9.91%和9.23%，證明了算法的有效性.

4 結 論

本文提出一種基于蟻群算法的電子商務推薦系統(tǒng).該方法可有效地減少由數據集稀疏帶來的問題，提高推薦系統(tǒng)的推薦質量，且通過設置相關參數解決新用戶的冷啟動問題.然而，蟻群算法中各參數的取值尚無嚴格的理論依據，至今還沒有確定參數取值的一般方法，需要依靠大量的重復性實驗尋找較優(yōu)的結果.此外，由于推薦系統(tǒng)中的用戶－評分矩陣是一個高維度的龐大矩陣［11］，且數據稀疏度極高，目前只能通過掃描評分矩陣來進行查詢，并且蟻群算法的引入也提高了掃面時間的復雜度.因此，未來可以通過建立多維的動態(tài)索引結構，從而提高推薦系統(tǒng)的實時性.

表1 不同推薦長度下各算法的準確率和召回率Tab.1 Precision and recall under the different length of recommended list

圖1 3種算法在MovieLense數據集上的準確率（a）和召回率（b）Fig.1 Three algorithms performances of the MovieLens data set：（a）precision，（b）recall.

［1］Sarwar B，Karypis G，Konstan J，et al.Item－based collaborative filtering recommendation algorithms［C］∥Proceedings of the 10th International Conference on World Wide Web.New York，USA：ACM，2001：285－295.

［2］Deshpande M，Karypis G.Item－based top－N recommendation algorithms［J］.ACM Transactions on Information Systems（TOIS），2004，2（1）：143－177.

［3］Dorigo M，Maniezzo V，Colorni A.Ant system：optimization by a colony of cooperating agents［J］.Systems Man and Cybernetics，Part B：Cybernetics，1996，26（1）：29－41.

［4］王晗，夏自謙.基于蟻群算法和瀏覽路徑的推薦算法研究［J］.中國科技信息，2009，33（7）：103－104.

［5］吳月萍，王娜，馬良.基于蟻群算法的協(xié)同過濾推薦系統(tǒng)的研究［J］.計算機技術與發(fā)展，2010，21（10）：73－76.

［6］鄧愛林，朱揚勇，施伯樂.基于項目評分預測的協(xié)同過濾推薦算法［J］.軟件學報，2003，14（9）：1621－1628.

［7］周玉妮.基于蟻群算法的移動商務個性化推薦體系研究［D］.南京：南京郵電大學，2012.

［8］詹士昌，徐婕，吳俊.蟻群算法中有關參數的最優(yōu)選擇［J］.科技通報，2003，19（5）：381－386.

［9］朱郁筱，呂琳媛.推薦系統(tǒng)評價指標綜述［J］.電子科技大學學報，2012，41（2）：163－175.

［10］Zhang Y，Wu J，Zhuang Y.Random walk models for top－N recommendation task［J］.Journal of Zhejiang University Science A，2009，10（7）：927－936.

［11］陳健，印鑒.基于影響集的協(xié)作過濾推薦算法［J］.軟件學報，2007，18（7）：1685－1694.