黃金鳳，雷筱珍

（福建交通職業(yè)技術(shù)學(xué)院 信息系，福州350007）

0 引 言

企業(yè)通過電子商務(wù)網(wǎng)站能增強(qiáng)自身的競爭優(yōu)勢，個(gè)人通過使用電子商務(wù)網(wǎng)站能感受到足不出戶購物的方便與快樂.但是電子商務(wù)網(wǎng)站存在一個(gè)亟待解決的問題：推薦適合當(dāng)前瀏覽用戶的商品給該瀏覽用戶，從而避免用戶由于在過多的商品中找到自己所需商品過于耗時(shí)耗力而離開.電子商務(wù)推薦系統(tǒng)就是解決此類問題的解決方案.許多大型電子商務(wù)網(wǎng)站早已開始使用電子商務(wù)推薦系統(tǒng)，如Amazon、當(dāng)當(dāng)網(wǎng)等.

在推薦系統(tǒng)中，協(xié)同過濾（Collaborative Filtering，CF）正迅速成為一項(xiàng)很受歡迎的技術(shù).協(xié)同過濾分析用戶興趣，即用戶會(huì)對鄰居所喜歡的商品產(chǎn)生興趣.在用戶群中找到指定用戶的相似興趣用戶，即鄰居用戶，綜合這些鄰居用戶對某一項(xiàng)目的評價(jià)，形成系統(tǒng)對該指定用戶對此項(xiàng)目的喜好程度預(yù)測，進(jìn)而將預(yù)測評價(jià)最好的前N項(xiàng)商品推薦給該指定用戶.

當(dāng)網(wǎng)站的用戶和項(xiàng)目數(shù)量增加時(shí)，CF的算法復(fù)雜度迅速遞增，從而使得系統(tǒng)推薦性能不斷下降，最終影響推薦的及時(shí)性［1］［2］.正是鑒于該問題，本文提出了基于蟻群模糊聚類的協(xié)同過濾推薦算法（CF－based ACVC，Collaborative filtering recommendation algorithm based on Ant Colony Vague clustering）.基本思想是分先離線再在線兩階段.離線時(shí)利用蟻群模糊聚類算法對用戶進(jìn)行聚類，生成若干用戶聚類中心，再計(jì)算每個(gè)用戶和各聚類中心的相似性以得到相似性度量矩陣；在線時(shí)計(jì)算目標(biāo)用戶與各聚類中心的相似性，再以此搜索相似性度量矩陣找到其最近鄰居并進(jìn)行評論預(yù)測，最后生成推薦.同時(shí)，仿真實(shí)驗(yàn)結(jié)果表明，本算法在一定程度上提高了推薦速度和質(zhì)量.

1 協(xié)同過濾算法

協(xié)同過濾算法是基于評分相似的最近鄰居的評分?jǐn)?shù)據(jù)向目標(biāo)用戶產(chǎn)生推薦.目標(biāo)用戶對未評分項(xiàng)目的評分可以通過最近鄰居對該項(xiàng)目評分的加權(quán)平均值逼近.它通過構(gòu)造用戶對項(xiàng)目的偏好數(shù)據(jù)集來實(shí)現(xiàn).

算法1協(xié)同過濾算法

協(xié)同過濾算法的輸入數(shù)據(jù)通常表述為一個(gè)m×n的用戶－項(xiàng)目評價(jià)矩陣R（m，n），其中m行表示m 個(gè)用戶，n列表示n個(gè)項(xiàng)目，矩陣元素Ri，j表示用戶i對項(xiàng)目j的評估值.

首先，計(jì)算每個(gè)用戶對以往評價(jià)過的信息資源項(xiàng)目的平均打分：

其中，Iu為用戶u的評分向量，｜Iu｜為Iu的長度，即用戶打過分的數(shù)字資源數(shù)目，Ruj表示用戶u對項(xiàng)目j的評分.

其次，計(jì)算目標(biāo)用戶對未評價(jià)過的信息資源項(xiàng)目的預(yù)測評分值：其中，Puj為目標(biāo)用戶u對信息資源項(xiàng)j的預(yù)測值.算法根據(jù)與目標(biāo)用戶相似的N個(gè)用戶的評價(jià)進(jìn)行預(yù)測，并非所有用戶都參與預(yù)測Puj值，sim（u，v）為用戶u和v之間的興趣相似度，k為歸一化因子.

算法的核心部分是計(jì)算用戶的興趣相似度sim（u，v），相似度量方法主要有三種：余弦相似性、相關(guān)相似性及修正的余弦相似性.鑒于文獻(xiàn)［4］的結(jié)論，我們選擇選用Pearson相關(guān)相似性度量作為本文的用戶相似性度量方式.

設(shè)I表示用戶u、v的共同評分項(xiàng)集，則用戶u、v之間的相似性sim（u，v）通過Pearson度量，其計(jì)算公式：

最后，按Pu，i值從大到小取前N 個(gè)項(xiàng)目組成推薦集Irec＝｛i1，i2…iN｝推薦給用戶u，從而完成整個(gè)推薦過程.

2 蟻群模糊聚類算法

聚類是基于“物以類聚”的思想，實(shí)質(zhì)是依據(jù)項(xiàng)目在屬性特征上的相似性對項(xiàng)目進(jìn)行分類，將相似性高的項(xiàng)目歸為一類，而不同類的項(xiàng)目之間的相似性低.FCM算法［4］是一種基于劃分的在模糊集理論上的聚類算法.

螞蟻覓食過程中，信息傳遞主要是通過信息素?cái)U(kuò)散完成的，是以信息素來決定螞蟻的運(yùn)動(dòng)方向.先前螞蟻對后面螞蟻的行為發(fā)生影響時(shí)，后面螞蟻一般不在先前螞蟻的運(yùn)動(dòng)軌跡上，而是與該運(yùn)動(dòng)軌跡有著或大或小的距離.當(dāng)距離比較小時(shí)，后面螞蟻的行為受影響較大，這一特點(diǎn)對數(shù)據(jù)聚類是十分有用的.本文借鑒這一原理及文獻(xiàn)［5］，提出一種蟻群模糊聚類（基于蟻群算法的模糊聚類）算法.

該算法將數(shù)據(jù)對象視為具有不同屬性的螞蟻，聚類中心看作是螞蟻所要尋找的“食物源”，這樣，數(shù)據(jù)聚類過程就可以被看作是螞蟻尋找食物的過程.

算法的思想是：在螞蟻從食物源i到食物源j的過程中，如果找到合適的路徑（子解），它就釋放出相應(yīng)濃度的信息素，該信息素一方面直接影響位于子解的兩個(gè)聚類中心上的螞蟻，另一方面它會(huì)以該路徑為中心向外擴(kuò)散，影響附近其他螞蟻的行為，使它們在尋找路徑時(shí)以更大的概率在下一步選擇此路徑［6］.通過這種基于信息素的協(xié)作方式，其他數(shù)據(jù)對象在選擇聚類中心時(shí)所受的干擾會(huì)減小，從而可提高算法的收斂速度.數(shù)據(jù)對象的歸屬根據(jù)轉(zhuǎn)移概率的大小來決定；在下一輪循環(huán)中，引入聚類偏差的衡量標(biāo)準(zhǔn)，更新聚類中心，計(jì)算偏差，再次判斷，直到偏差沒有變化或在一定誤差范圍內(nèi)，算法結(jié)束.

算法2 蟻群模糊聚類算法

令：X＝｛Xi｜Xi＝（Xi1，Xi2，…，Xin），i＝1，2，…，n｝是待聚類的數(shù)據(jù)集合：

令：dij＝‖P（Xi－Yi）‖2中，dij表示Xi到Y(jié)i之間的加權(quán)歐氏距離；P為權(quán)因子，可以根據(jù)各分量在聚類中的貢獻(xiàn)不同而定.

t時(shí)刻，對于其他數(shù)據(jù)對象l，第k只螞蟻從i到食物源j（聚類中心）的路徑（i，j）上的信息素量（t）（如式（4）），此時(shí)，螞蟻將分別以i和j為中心以r為半徑向周圍擴(kuò)散信息素，則數(shù)據(jù)對象l由螞蟻k所產(chǎn)生的信息量）定義為［69］：

以i為中心向周圍擴(kuò)散信息素，數(shù)據(jù)對象l由螞蟻k所產(chǎn)生的信息量Δ（t）為：

以j為中心向周圍擴(kuò)散信息素，數(shù)據(jù)對象l由螞蟻k所產(chǎn)生的信息量Δ（t）為：

數(shù)據(jù)對象Xi是否歸并到聚類中心由轉(zhuǎn)移概率Pij決定：

其中，S＝｛Xs｜dsj≤R，s＝1，2，…，n｝，表示分布在聚類中心領(lǐng)域內(nèi)的數(shù)據(jù)對象的集合；α表示殘留信息的相對重要程度，β期望值的相對重要程度，ηij為t時(shí)刻螞蟻由城市i選擇城市j的某種啟發(fā)信息.若Pij（t）≥P0（P0為一設(shè)定值），則 Xi歸并到；否則，不歸并.

令：CSj＝｛Xi｜dij≤R，i＝1，2，…，J｝，表示所有歸并到聚類中心Cj的數(shù)據(jù)對象的集合，J為該集合中數(shù)據(jù)對象的個(gè)數(shù).根據(jù)公式（8）和公式（9）分別計(jì)算新的聚類中心和隸屬矩陣ujl.第j個(gè)聚類的偏離誤差εJ及此次分析的總體誤差ε分別由公式（10）和公式（11）給出.

算法的偽代碼如下：

算法的輸出是K個(gè)聚類中心點(diǎn)向量和K＊N的一個(gè)模糊劃分矩陣，這個(gè)矩陣表示的是每個(gè)樣本點(diǎn)屬于每個(gè)類的隸屬度.根據(jù)這個(gè)劃分矩陣按照模糊集合中的最大隸屬原則就能夠確定每個(gè)樣本點(diǎn)歸為哪個(gè)類.聚類中心表示的是每個(gè)類的平均特征，可以認(rèn)為是這個(gè)類的代表點(diǎn).

3 基于蟻群模糊聚類的協(xié)同過濾算法（CF－based ACVC）

離線階段，先對用戶進(jìn)行蟻群模糊聚類，產(chǎn)生若干聚類中心和一個(gè)類別隸屬矩陣，這個(gè)矩陣表示每個(gè)用戶屬于每個(gè)類的隸屬度.根據(jù)這個(gè)劃分矩陣按照模糊集合中的最大隸屬原則就能獲得用戶與聚類中心的相似性度量矩陣.在線階段，只要計(jì)算目標(biāo)用戶與各個(gè)聚類中心的相似性，再通過對比離線時(shí)獲得的相似性度量搜索矩陣搜索目標(biāo)用戶的最近鄰居，并產(chǎn)生推薦.基于聚類的實(shí)質(zhì)，離線階段獲得的聚類數(shù)目遠(yuǎn)遠(yuǎn)小于用戶數(shù)目，在線階段系統(tǒng)只需計(jì)算目標(biāo)用戶與少量的聚類中心的相似性，因此，提高了推薦的實(shí)時(shí)性.

3.1 離線時(shí)的蟻群模糊聚類

先用公式（3）代替蟻群模糊聚類算法中的公式（9）的右半部分計(jì)算隸屬矩陣μjl，再利用算法2獲得用戶聚類中心C（k，n）以及每個(gè)用戶屬于每個(gè)類的隸屬度矩陣U（k，n）.

用戶聚類中心C（k，n）表示n個(gè)項(xiàng)目的k個(gè)聚類中心，其元素cij表示用戶聚類中心i對項(xiàng)目j的評分，也是第i類中的所有用戶對項(xiàng)目j的平均評分.

基本用戶的類別隸屬度矩陣U（k，n）表示k個(gè)基本用戶的n個(gè)用戶聚類，其元素uij表示用戶i對聚類中心j的相似性，即用戶i和第j個(gè)用戶聚類中心之間的Pearson相關(guān)相似性度量.

3.2 在線時(shí)查找目標(biāo)用戶的最近鄰居并產(chǎn)生推薦

在離線處理結(jié)果的基礎(chǔ)上，在線階段，利用算法1完成整個(gè)推薦過程.

4 仿真實(shí)驗(yàn)及分析

通過仿真實(shí)驗(yàn)驗(yàn)證本文提出的算法，并文獻(xiàn)［2］的算法進(jìn)行了比較.

4.1 實(shí)驗(yàn)環(huán)境及實(shí)驗(yàn)數(shù)據(jù)集

實(shí)驗(yàn)所用PC機(jī)的配置為Intel（R）Core（TM）2Duo CPU T9550 2.66GHz、2GB RAM，Windows XP操作系統(tǒng)，Access數(shù)據(jù)庫，算法用Matlab實(shí)現(xiàn).

實(shí)驗(yàn)數(shù)據(jù)集采用 MovieLens數(shù)據(jù)集［8］.MovieLens數(shù)據(jù)庫集是美國Minnesota大學(xué)GroupLens項(xiàng)目組提供的，用于接收用戶對電影的評分并提供相應(yīng)的電影推薦列表.該數(shù)據(jù)集包含了943位用戶對1682部電影作出的1000000條評分?jǐn)?shù)據(jù)，分為5個(gè)base數(shù)據(jù)集和5個(gè)test數(shù)據(jù)集.我們使用十折交叉驗(yàn)證（10－fold cross－validation）方法進(jìn)行實(shí)驗(yàn).每次選擇一對base數(shù)據(jù)集和test數(shù)據(jù)集，使用base數(shù)據(jù)集中的記錄作為基本用戶，對test數(shù)據(jù)集中的目標(biāo)用戶進(jìn)行推薦測試.

4.2 評價(jià)標(biāo)準(zhǔn)

實(shí)驗(yàn)采用統(tǒng)計(jì)精度度量方法中廣泛使用的平均絕對誤差MAE（Mean Absolute Error）來衡量算法的預(yù)測精度.MAE是測試集中所有用戶對資源打分的實(shí)際值與預(yù)測值的偏差的絕對值的平均［8］.MAE值越小，說明推薦算法的預(yù)測精度越高.

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

為了驗(yàn)證本文提出算法的有效性，我們進(jìn)行了仿真實(shí)驗(yàn)并與文獻(xiàn)［2］的算法進(jìn)行了對比.

在對MovieLens數(shù)據(jù)集的數(shù)據(jù)的預(yù)處理過程中，我們發(fā)現(xiàn)原始類別的前7類中，每個(gè)原始類別都包含相對較多的基本用戶，而其他類則包含相對少量的用戶，所以在驗(yàn)證本文算法時(shí)，我們?nèi)【垲悢?shù)目k的值為7.采用最近鄰用戶數(shù)K分別取10、15、20、25、30、35、40，用戶相似性度量方法采用Pearson相關(guān)系數(shù)，運(yùn)行本文提出的算法CF－based ACVC和文獻(xiàn)［2］的算法（IRP－CF），計(jì)算在不同最近鄰用戶數(shù)時(shí)兩種算法各自的MAE.實(shí)驗(yàn)結(jié)果如圖1所示.

圖1 兩種算法的評分預(yù)測質(zhì)量比較

由圖1可知CF－based ACVC具有更小的MAE

5 結(jié) 論

由前文對CF－based ACVC算法的分析可知，傳統(tǒng)協(xié)同過濾算法是直接計(jì)算目標(biāo)用戶與所有的m個(gè)基本用戶之間的相似性，而本文算法首先計(jì)算目標(biāo)用戶與基本用戶聚類中心之間的相似性，基本用戶聚類中心的個(gè)數(shù)相比于所有基本用戶是小了很多，所以本文提出的算法提高了在線搜索目標(biāo)用戶的最近鄰居的速度，從而在一定程度上提高了推薦系統(tǒng)的實(shí)時(shí)性.實(shí)驗(yàn)結(jié)果表明，本文算法在一定程度上提高了在線時(shí)的推薦生成速度，同時(shí)推薦質(zhì)量也有一定的提高.實(shí)驗(yàn)結(jié)果還表明對于離線時(shí)基本用戶的聚類，雖然我們并沒有特別要求，比如聚類過程中k的選取等，CF－based ACVC仍然能夠在一定程度上加快推薦產(chǎn)生速度.

［1］ 鄧愛林，左子葉，朱揚(yáng)勇.基于項(xiàng)目聚類的協(xié)同過濾推薦算法［J］.小型微型計(jì)算機(jī)系統(tǒng)，2004，25（9）：1665－1670.

［2］ B M Sarwar.Sparsity，Scalability，and Distribution in Recommender system［D］.Minneapolis，MN：University of Minnesota，2001.

［3］ H J Ahn.A New Similarity Measure for Collaborative Filtering to Alleviate the New User Cold－starting Problem［J］.Inforamtion Sciences，2008，178（1）：37－51.

［4］ KANADE PM，HALL LO.Fuzzy Ants as a Cluste－ring Concept［A］.Proceedings of the 22nd Interna－tional Conference of the North American Fuzzy In－formation Processing Society［C］.USA，2003：227－232.

［5］ 姜長元.基于混合信息素遞減的蟻群算法［J］.計(jì)算機(jī)工程與應(yīng)用，2007，43（32）：62－64.

［6］ 馬溪駿，潘若愚，楊善林.基于信息素遞減的蟻群算法［J］.系統(tǒng)仿真學(xué)報(bào)，2006，18（11）：3297－3300.

［7］ http：／／www.grouplens.org／node／73［EB／OL］.

［8］ Mobasher B，Jin X，Zhou Y Z.Semantically Enhanced Collaborative Filtering on the Web，Springer－Verlag，2004：57－76.