王茜，王艷明

（重慶大學計算機學院，重慶 400044）

一種改進的協(xié)同過濾推薦算法

王茜，王艷明

（重慶大學計算機學院，重慶 400044）

在協(xié)同過濾推薦系統(tǒng)中，商品被視為特征，用戶提供他們對購買的商品的評分。通過對用戶評分的學習，推薦系統(tǒng)可以向用戶推薦他們可能需要的產(chǎn)品。然而電子商務通常有相當多的產(chǎn)品，如果在推薦前要對每一個商品都進行考慮，推薦系統(tǒng)將是非常低效的。提出一種改進的ItemRank方法，應用自構(gòu)建聚類算法來減少商品數(shù)量相關的維度，然后直接在聚類上運行推薦算法。最后，對推薦聚類進行變換得到推薦商品列表推薦給不同的用戶。所提出的方法在計算推薦商品時所需的時間大大減少。實驗結(jié)果表明，在不影響推薦質(zhì)量的前提下，推薦系統(tǒng)的效率得到了提高。

協(xié)同過濾推薦系統(tǒng)；ItemRank

0 引言

隨著網(wǎng)絡的快速發(fā)展，網(wǎng)絡商店中商品的數(shù)量、種類變得越來越多，網(wǎng)絡購物的人群也越來越多，從如此數(shù)量眾多、種類繁雜的商品中選擇適合自己的商品也變得越來越困難。因此，推薦系統(tǒng)應運而生，以幫助人們在網(wǎng)上找到他們感興趣的商品，節(jié)約他們的檢索時間[1]。對于用戶來說，推薦系統(tǒng)可以通過他們的購買、瀏覽記錄分析出他們的喜好，從而把他們感興趣的商品推薦給他們。在過去的幾年中，推薦系統(tǒng)得到了快速的發(fā)展，在本質(zhì)上，他們可以分為兩類，基于內(nèi)容和協(xié)同過濾，雖然近幾年來混合系統(tǒng)[2]趨勢不斷增長。

基于內(nèi)容的推薦系統(tǒng)根據(jù)產(chǎn)品的類別和其他屬性等內(nèi)容向用戶推薦商品。通過一些技術(shù)分析這些數(shù)據(jù)，如貝葉斯模型[3]，基于內(nèi)容的推薦系統(tǒng)向用戶推薦那些最有吸引力的商品。一般來說基于內(nèi)容的推薦系統(tǒng)需要商品和用戶的詳細信息，它可以向用戶推薦新商品，但是它需求的信息是巨大的，而且很難獲取所有用戶和商品的屬性及其他信息。此外收集代表用戶或商品的唯一屬性也很難。

協(xié)同過濾推薦系統(tǒng)[4-8]不需要用戶或商品屬性的詳細信息。相反，它通過用戶和商品之間的交互信息向用戶推薦商品，通常交互信息表示為用戶對購買的商品的評分。通過對用戶項目評分矩陣的分析，系統(tǒng)可以向他們推送和他們有相同興趣用戶購買的而且他們還沒有購買的商品?？傮w來說協(xié)同過濾系統(tǒng)更易實現(xiàn)和高效。

然而網(wǎng)絡商店中通常有相當多的產(chǎn)品，如果在推薦前要對每一個商品都進行考慮，推薦系統(tǒng)將是非常低效的。降維技術(shù)已經(jīng)在面對大規(guī)模數(shù)據(jù)產(chǎn)生快速、高效推薦系統(tǒng)中得到了廣泛的應用。K-means的一種變形B-Kmeans[9]算法已經(jīng)應用在對用戶進行不同的劃分中。通過分析給定用戶所屬的分區(qū)中用戶的鄰域，向用戶推薦商品。Ba Q[10]等人將用戶按照性別、年齡、職業(yè)等屬性分組，然后用戶項目評分矩陣重組后再計算兩個用戶之間的相似度。CAI[11]等人用模糊聚類方法運用到用戶上對用戶進行聚類，利用用戶組特征向量代表用戶，對用戶代表的維度降維。Sarwat[12]等人在一個框架內(nèi)使用三種類型的基于位置的評級的分類法產(chǎn)生推薦，利用用戶劃分和旅行點向查詢用戶推送跟接近的候選人。在PRM2[13]算法中，個人興趣、人際關系相似性和人際影響被融合成一個統(tǒng)一的個性化推薦模型，并且使用奇異值分解（SVD）來對原始的用戶項目評分矩陣進行降維。ICCRS[14]算法是一種迭代評分算法，它對有偏見的評價者有很大的魯棒性，與之前的迭代方法不同，它不是基于將提交的評分與最終評分的近似進行比較，而是完全將評分評估的可信度與排名本身分離，這使得它比先前的迭代過濾算法對復雜的攻擊有更強的魯棒性。

上述基于維度降低的推薦系統(tǒng)具有一些缺點。一些系統(tǒng)[10，12]需要關于用戶或商品的額外屬性來將用戶或商品進行聚類，而這些屬性通常是很難在實際應用中得到的。另一些系統(tǒng)[11,15]需要預先給出聚類的數(shù)量，這對用戶來說是很難確定的，只能通過重復訓練，這是一個很大的負擔。此外，使用降維的推薦系統(tǒng)在計算相似性的時候僅僅考慮聚類的中心，忽略聚類的方差可能導致推薦結(jié)果的不精確。

在本文中，我們提出了一種改進的ItenRank方法，應用自構(gòu)建聚類算法來減少商品的維度，創(chuàng)建出商品聚類之間相互關系的相關圖。然后執(zhí)行一系列的隨機游動，為每個用戶生成商品聚類的推薦列表。最后執(zhí)行將商品聚類推薦列表轉(zhuǎn)換成單個商品的推薦列表。利用我們提出的方法，不需要搜集用戶和商品的額外屬性信息，而且不需要用戶提供預定的聚類數(shù)量。此外，在計算相似性的時候我們不僅考慮聚類中心，還應用聚類方差等因素。由于商品數(shù)量維度的減少，我們提出推薦商品的處理時間也大大減少。

1 相關算法

假設一個有N個用戶的集合ui，1≤i≤N，一個有M個商品的集合pj，1≤i≤M。用戶ui通過對商品pj的評分ri，j（ri，j為一個正整數(shù)）來表達自己對商品的喜好程度。通常，評分越高表明用戶對商品的喜好程度越高。如果用戶ui未提供對商品pj的評分，ri，j=0。這些信息用一個用戶項目評分矩陣來表示R：

此矩陣為N×M矩陣，把Ri記為Ri=[ri1ri2…riM]，1≤i≤N。矩陣R的每一行代表一個用戶，每一列代表一個商品。協(xié)同過濾推薦系統(tǒng)的目標是給定用戶項目評分矩陣，預測用戶對商品的喜好程度，向用戶推薦商品。

ItemRank[16-17]是協(xié)同過濾推薦的基本方法之一。它應用基于圖模型的推薦算法，通過項目（商品）節(jié)點來構(gòu)圖，形成項目間的關聯(lián)關系圖并計算得到用戶的偏好向量，然后利用隨機游走算法預測用戶對項目的預測評分，最后向用戶推薦生成的Top-K商品。在關聯(lián)關系圖創(chuàng)建步驟中，每個節(jié)點都是一個商品，商品節(jié)點pi與pj之間的連線wi，j具有的權(quán)重是同時購買商品pi和pj的數(shù)量。構(gòu)建完關聯(lián)關系圖后得到矩陣W：

此矩陣為M×M矩陣，然后對矩陣W的每一列進行歸一化。在隨機游走算法中，假設用戶ui，1≤i≤N，設Si（0）=[1/M 1/M…1/M]T，然后執(zhí)行Si（t+1）= αWSi（t）+（1-α）RiT操作，t=0，1，2，…，直至達到收斂。α∈[0，1]是用戶定義的一個常數(shù)，通常α取0.85，在執(zhí)行20次迭代后達到收斂效果。設Si為收斂后的向量，即用戶ui的預測偏好列表。然后可以根據(jù)Si中元素的大小順序向用戶ui推薦商品。

2 提出的改進算法

電子商務中可能包含數(shù)量巨大的商品，這使得ItemRank在生成項目節(jié)點圖的矩陣W時耗時較長，導致ItemRank不適合處理大規(guī)模數(shù)據(jù)。本文中，我們主要是針對ItemRank算法的改進。首先我們用自構(gòu)建聚類（SCC）算法[18-19]為用戶分配類標簽，其次用自構(gòu)建聚類（SCC）算法對商品進行聚類以降低維度，然后創(chuàng)建項目關聯(lián)圖，隨后利用隨機游走算法預測用戶對項目聚類評分，最后進行聚類轉(zhuǎn)換到商品個體對用戶進行推薦商品。結(jié)果表明ItemRank的效率可以大大提高。

2.1 自構(gòu)建聚類（SCC）算法

假設X集合有n個模式X1，X2，…，Xn，其中Xi=xi1，xi2，…，xip，1≤i≤n，SCC算法目的是將這些模式分配到不同的聚類中。假設現(xiàn)在存在K個聚類，分別是G1，G2，…，Gk，每個聚類Gj（1≤j≤k）的平均值為mj=mj1，mj2，…，mjp，標準差為σj=σj1，σj2，…，σjp，Gj的大小為sj，即Gj含有的模式個數(shù)。最初我們沒有聚類，K=0，我們計算每個模式Xi對聚類Gj的隸屬度μGj（Xi），

如果隸屬度不小于預定義的閾值，μGj（Xi）≥ρ， 0≤ρ≤1，我們就說Xi通過了聚類Gj的相似度檢測。較大的ρ導致較小的聚類，較小的ρ導致較大的聚類。此時可能有兩種情況。一種情況為Xi沒有通過對現(xiàn)存的任何聚類Gj的相似度檢測。這種情況下我們創(chuàng)建一個新聚類Gh，h=K+1，mh=xi，σh=σ0，σ0=σ0，σ0，…，σ0是用戶定義的一個常數(shù)向量。此時聚類的數(shù)目增加了1，聚類Gh的大小初始化為1，即K=h，s1=1。第二種情況Xi通過了某些現(xiàn)存的聚類相似度檢測，設最大隸屬度的聚類為Gt，此時把Xi歸入到聚類Gt中，更新聚類Gt的均值和標準差，這種情況下K不改變。該過程一直跌到所有的模式被處理完，最終得到K個聚類。

2.2 標記用戶類標簽

為了有效的降低維數(shù)，我們用SCC算法對用戶進行聚類，標記用戶類標簽，而且不需要用戶輸入聚類個數(shù)。為了消除用戶評分的尺度不同，我們對用戶評分進行歸一化：

設Xi=xi1，xi2，…，xiM，1≤i≤N，X={Xi│1≤i≤N}，我們對X運用SCC算法，假設得到z個聚類，G1，G2，…，Gz，每個聚類當做一個類標簽，分別標記為c1，c2，…，cz。對所有屬于聚類Gj的用戶我們標記類標簽為cj。此時我們將原始數(shù)據(jù)集合R擴展為R+，（R1，y1），（R2，y2），…（RN，yN），yi∈{c1，c2，…，cz}，1≤i≤N。

2.3 降維

這個步驟中我們使用Jiang[19]等提出的類似方法降低商品維數(shù)。對于每件商品pj，1≤j≤M，我們構(gòu)造一個特征模式Xj=xj1，xj2，…，xjz，其中：

因此我們有M個特征模式X1，X2，…，XM，每個具有z個分量。設Y={Xi│1≤i≤M}。

然后我們在Y上應用SCC算法，假設我們獲得q個聚類G1，G2，…，Gq，同一聚類中的商品相似。由于有q個聚類，用戶對商品評價的維度由M降維到q，得到矩陣T：

然后我們把高維的N×M矩陣R降維成低維矩陣B：

我們將B中的每一列稱為一個商品類，因此我們有q個商品類，記為g1，g2，…，gq。由此，原來具有M個商品評分的用戶記錄降維成具有q個商品組評分。ItemRank算法運行在R矩陣上，我們的算法將運行在降維后的B矩陣上。

2.4 創(chuàng)建關聯(lián)關系圖

此步驟中我們創(chuàng)建一個相關圖，顯示q個商品類之間的關聯(lián)關系。由于我們使用的是B，我們以不同的方式派生關聯(lián)關系圖。每個商品類被視為一個節(jié)點，我們有q個節(jié)點。節(jié)點gi和gj之間的權(quán)重為wij，1≤i，j≤q，計算方式如下：

如果wij太大，則某些商品類可能占主導地位，并且妨礙一些商品被劃分到其他商品組，因此我們對wij設置上限為1。當關聯(lián)關系圖完成后，我們得到如下矩陣：

然后我們對W矩陣的列進行歸一化。

2.5 隨機游走

在隨機游走步驟中，執(zhí)行一系列隨機游走。任一用戶ui，1≤i≤N，設：

然后執(zhí)行如下步驟，直至vi收斂。

其中W是根據(jù)公式（14）得到的，Bi是根據(jù)公式（11）得到的。假設Vi為收斂后的向量，則Vi是為用戶ui生成的推薦商品組。

2.6 再轉(zhuǎn)換

在上面步驟中，我們得到q個商品類，為用戶ui推薦的商品類包含q個商品。但是，最終我們不是向用戶推薦商品類，而是向用戶推薦單個商品，因此，我們要將Vi轉(zhuǎn)化成包含單個商品列表的Si。根據(jù)公式（9），我們得到xj對商品聚類G1，G2，…，Gq的隸屬度分別為tj1= μG1（Xj），tj2=μG1（Xj），…，tjq=μGq（Xj）。首先我們對公式（8）中的矩陣T的列進行歸一化：

對每一行進行如下計算：

Si[j]是Si的第j個分量，Vi[k]是Vi的第k個分量。tjk是商品pj對商品類gk的貢獻值，Vi[k]表示用戶ui對商品類gk的喜好程度。因此tjkVi[k]表示用戶ui在商品類gk中對商品pj的喜好程度，累加得出用戶ui對商品pj的喜好程度。最終，我們得到用戶ui的推薦商品列表Si。

3 實驗結(jié)果與分析

3.1 時間復雜度分析

在標記用戶類標簽步驟時，我們必須計算每個用戶和每個現(xiàn)有聚類之間的相似性，N為用戶數(shù)，M為商品數(shù)，每個用戶向量有M個分量，z為類標簽個數(shù)，所以這步驟復雜度為O（NzM）。在降維步驟中，我們需要計算特征模式和現(xiàn)有聚類之間的相似性，特征模式為M，商品類為q，每個特征模式包含z個分量，所以這步驟復雜度為O（Mqz）。在關聯(lián)關系圖步驟中，兩點之間的權(quán)重wij都需要計算，所以這步驟復雜度為O（q2）。在隨機游走算法中，公式（16）必須要進行迭代，每次的跌倒需要q q2次運算，對所有用戶（N個）的復雜度為O（Nq2）。最后，對一個用戶來說，公式（19）需要進行M次運算，每次涉及q次乘法和q-1次加法，所以此步復雜度為O（NqM）。所以，總共的時間復雜度為O（NzM）+O（Mqz）+O（q2）+O（Nq2）+O（NqM）。

3.2 實驗結(jié)果分析

本文用了四個數(shù)據(jù)集進行實驗，分別是Movie-Lens，BookCrossing和Epinions。這三個數(shù)據(jù)集的特征如表1所示。通過與ItemRank算法，PRM2算法，BiFu算法和ICRRS算法進行比對。ItemRank算法不采用任何降維技術(shù)，PRM2算法應用奇異值分解（SVD）方法來降維，BiFu算法應用K-means算法進行聚類降維，ICCRS算法將評分估計的可信度與排名本身分離。因為K-means需要預先輸入聚類數(shù)目，所以我們先運行本文的方法得到聚類數(shù)目，然后把聚類輸入應用到BiFu算法中。

表2顯示了本文方法（IRSCC）和BiFu中涉及的用戶項目聚類數(shù)。表3顯示了算法之間絕對平均誤差（MAE）的比較。對MAE來說，獲得的值越小，方法越好?？梢钥闯鰧τ谌齻€數(shù)據(jù)集來說，ItemRank和IRSCC在MAE方面表現(xiàn)相當好。表4顯示了不同方法之間的執(zhí)行時間（以秒為單位）的對比。我們可以看出IRSCC運行速度要比其他方法好很多。

表1 數(shù)據(jù)特征

表2 聚類數(shù)目

表3 不同方法的MAE比較

表4 不同方法執(zhí)行時間比較

因為ItemRank算法設計的維數(shù)是商品的數(shù)量，例如，對于BookCrossing數(shù)據(jù)集來說ItemRank要處理一個9846×9846矩陣，所以ItemRank在BookCrossing上運行9121.29s。相反，IRSCC應用自構(gòu)建聚類以降低維度，把9846個商品聚類到56個聚類中。所以在公式（16）中使用的關聯(lián)關系矩陣減小到56×56，所以IRSCC運行的很快。BiFu通過K-means進行降維，這是非常耗時的，所以BiFu也比IRSCC算法慢很多。

為本算法選擇一個合適的ρ仍然是一個難題，還是經(jīng)受一些試驗和錯誤。在第3節(jié)中指出ρ的選擇直接影響算法的效果。當ρ選擇的較大時，聚類較小，生成的聚類數(shù)目就較多，這將導致算法運行時間增加。

4 結(jié)語

在協(xié)同過濾系統(tǒng)中，商品被視為特征。然而，涉及電子商務時，通常有相當多的商品，如果每一個商品在推薦前都要考慮的話，推薦效率將是非常低效的。我們提出了一種應用自構(gòu)建聚類算法來降維，以達到效率的提高。實驗結(jié)果表明，推薦系統(tǒng)的效率大大提高，而且不損害推薦質(zhì)量。

[1]Marko Balabanovic，Yoav Shoham.Content-Based Collaborative Recommendation.Communications of the ACM.March 1997.Pages 66-72.

[2]Gatzioura，A.，Sànchez-Marrè，M.A Case-Based Recommendation Approach for Market Basket Data.IEEE Intell.Syst.30（1），2014. Pages20-27.

[3]Rish，I.An Empirical Study of the Naive Bayes Classifier.In:International Joint Conferences on Artificial Intelligence（IJCAI）Workshop on Empirical Methods in AI，pp.41-46.

[4]Cui，H.，Zhu，M.Collaboration Filtering Recommendation Optimization with User Imp licit Feedback.J.Comput.Inf.Syst.10（14），5855-5862,2014.

[5]Guo，G.，Zhang，J.，Thalmann，D.，Yorke-Smith，N.Leveraging Prior Ratings for Recommender Systems in E-Commerce.Electron. Comm.Res.Appl.13，440-455，2014.

[6]Nikolakopoulos，A.N.，Kouneli，M.，Garofalakis，J.A Novel Hierarchical Approach to Ranking-Based Collaborative Filtering.Commun.Comput.Inf.Sci.384，50-59，2013.

[7]Jiang，M.，Cui，P.，Liu，R.，Yang，Q.，F(xiàn)ei，W.，Zhu，S.Yang，Social Contextual Recommendation.In:21st ACM International Conference on Information and Knowledge Management，pp.45-54，2012.

[8]Porcel，C.，Tejeda-Lorente，A.，Martinez，M.，Herrera-Viedma，E.A Hybrid Recommender System for the Selective Dissemination of Research Resources in a Technology Transfer Office.Inf.Sci.184，1-19，2012.

[9]Sarwar，B.M.，Karypis，G.，Konstan，J.，Riedl，J.，Recommender Systems for Large-Scale E-Commerce:Scalable Neighborhood Formation Using Clustering.In:5th International Conference on Computer and Information Technology，2002.

[10]Ba Q，Li X，Bai Z.Clustering Collaborative Filtering Recommendation System Based on SVD Algorithm[C].Software Engineering and Service Science（ICSESS），2013 4th IEEE International Conference on.IEEE，2013:963-967.

[11]Cai Y，Leung H，Li Q，et al.Typicality-Based Collaborative Filtering Recommendation[J].IEEE Transactions on Know ledge and Data Engineering，2014，26（3）：766-779.

[12]Sarwat M，Levandoski J J，Eldawy A，et al.LARS*:An Efficient and Scalable Location-Aware Recommender System[J].IEEE Transactions on Knowledge and Data Engineering，2014，26（6）：1384-1399.

[13]Qian X，F(xiàn)eng H，Zhao G，et al.Personalized Recommendation Combining User Interest and Social Circle[J].IEEE Transactions on Knowledge and Data Engineering，2014，26（7）：1763-1777.

[14]A llahbakhsh M，Ignjatovic A.An Iterative Method for Calculating Robust Rating Scores[J].IEEE Transactions on Parallel and Distributed Systems，2015，26（2）：340-350.

[15]Xue，G.-R.，Lin，C.，Yang，Q.，Xi，W.，Zeng，H.-J.，Yu，Y.，Chen，Z.Scalable Collaborative Filtering Using Cluster-Based Smoothing.In:ACM SIGIR Conference，2005.

[16]范家兵，王鵬，周渭博，等.在推薦系統(tǒng)中利用時間因素的方法[J].計算機應用，2015，35（5）:1324-1327.

[17]Pucci，A.，Gori，M.，Maggini，M.A Random-Walk Based Scoring A lgorithm Applied to Recommender Engines，Lecture Notes in Computer Science-Advances in Web Mining and Web Usage Analysis 4811（2007）：127-146.

[18]Lee，S.-J.，Ouyang，C.-S.A Neuro-Fuzzy System Modeling with Selfconstructing Rule Generation and Hybrid SVD-Based Learning. IEEE Trans.Fuzzy Syst.11（3），341-353，2003.

[19]Jiang，J.-Y.，Liou，R.-J.，Lee，S.-J.，2011.A Fuzzy Self-Constructing Feature Clustering Algorithm for Text Classification.IEEE Trans.Knowl.Data Eng.23（3），335-349.

Improved Collaborative Filtering Recommendation Algorithm

WANG Qian，WANG Yan-ming

（College of Computer Science，Chongqing University，Chongqing 400044）

In collaborative filtering recommender systems，products are regarded as features and users are requested to provide ratings to the products they have purchased.By learning from the ratings，such a recommender system can recommend interesting products to users.However，there are usually quite a lot of products involved in E-commerce and itwould be very inefficient if every product needs to be considered beforemaking recommendations.Proposes an improved approach based ItemRank which applies a self-constructing clustering algorithm to reduce the dimensionality related to the number of products,Recommendation is then donewith the clusters.Finally,re-transformation is performed and a ranked list of recommended products is offered to each user.With the proposed approach,the processing time formaking recommendations ismuch reduced.Experimental results show that the efficiency of the recommender system can be improved without compromising the recommendation quality.

王茜（1970-），女，重慶人，教授，研究方向為網(wǎng)絡安全、電子商務、數(shù)據(jù)挖掘

2017-03-14

2017-05-10

1007-1423（2017）15-0008-06

10.3969/j.issn.1007-1423.2017.15.002

王艷明（1990-），男，河北邯鄲人，碩士，研究方向為數(shù)據(jù)挖掘

Collaborative Filtering Recommender System;ItemRank