基于蟻群模糊聚類的協(xié)同過濾推薦算法

黃金鳳，雷筱珍

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

0 引 言

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

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

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

1 協(xié)同過濾算法

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

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

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

首先，計算每個用戶對以往評價過的信息資源項目的平均打分：

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

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

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

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

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

2 蟻群模糊聚類算法

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

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

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

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

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

算法的偽代碼如下：

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

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

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

3.1 離線時的蟻群模糊聚類

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

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

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

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

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

4 仿真實驗及分析

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

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

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

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

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

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

4.3 實驗結(jié)果及分析

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

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

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

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

5 結(jié) 論

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

［1］ 鄧愛林，左子葉，朱揚勇.基于項目聚類的協(xié)同過濾推薦算法［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ī)工程與應(yīng)用，2007，43（32）：62－64.

［6］ 馬溪駿，潘若愚，楊善林.基于信息素遞減的蟻群算法［J］.系統(tǒng)仿真學(xué)報，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.