姜 鵬，許 峰，周文歡

（河海大學(xué)計算機與信息學(xué)院，江蘇 南京 211100）

1 引言

如今人們的生活、工作、娛樂都離不開互聯(lián)網(wǎng)，互聯(lián)網(wǎng)也為人們提供了極其豐富的信息和資源?；ヂ?lián)網(wǎng)的用戶不斷地增加，Web 信息也隨之成幾何級數(shù)地增長。這些海量的信息，使用戶無法在第一時刻找到自己最想要的資源，這就是“信息過載”所造成的“信息迷向”的現(xiàn)象。推薦系統(tǒng)[1，2.則可以有效地緩解此類問題。

推薦系統(tǒng)根據(jù)用戶的相關(guān)行為構(gòu)造用戶與項目之間的二元關(guān)系模型，對冗雜的互聯(lián)網(wǎng)信息進行過濾和篩選，并將結(jié)果推薦給用戶。目前，一些電子商務(wù)網(wǎng)站（如Amazon、Taobao 等）、搜索引擎（如Google、百度等）、社交網(wǎng)站（如Facebook、豆瓣）甚至微博（如Twitter、新浪微博）都不同程度使用到推薦系統(tǒng)[3]。

推薦系統(tǒng)利用其在互聯(lián)網(wǎng)信息推薦方面的優(yōu)勢快速發(fā)展。早在2000 年，Haubl與Trifts[4]在研究電子商務(wù)系統(tǒng)時發(fā)現(xiàn)，93%的消費者選擇購買推薦系統(tǒng)提供的商品，而此前，能夠購買到高質(zhì)量產(chǎn)品的消費者僅有65%。不僅如此，在另外一些在線商店中，用戶的購買行為往往并非事先計劃（如圖書、音樂、電影等）。此時，一個好的推薦系統(tǒng)，不僅能向用戶有效傳達最新商品信息，而且可以勾起消費者的購買欲望，推動產(chǎn)業(yè)發(fā)展。推薦系統(tǒng)會在用戶與商品間建立好橋梁關(guān)系，用戶也會對推薦系統(tǒng)產(chǎn)生依賴。

本文第2節(jié)介紹推薦系統(tǒng)研究現(xiàn)狀；第3節(jié)介紹相似度計算方法；第4節(jié)介紹網(wǎng)絡(luò)的分割規(guī)則，并給出SCSG 算法流程；第5節(jié)是實驗仿真及結(jié)果對比；最后給出全文總結(jié)。

2 研究現(xiàn)狀

可以認為，推薦系統(tǒng)是由智能檢索、預(yù)測理論等發(fā)展而來的，其核心部分為推薦引擎。推薦引擎算法的優(yōu)劣直接影響到推薦系統(tǒng)的性能[2]。一般地，推薦引擎分為三類，一類是協(xié)同過濾推薦（Collaborative Filtering），另一類是內(nèi)容分析（Content-Based），最后一類是混合推薦（Hybrid）[5]。協(xié)同過濾的主要思想是根據(jù)用戶在系統(tǒng)中的行為（通常為評級操作）計算用戶間的相似性，進而根據(jù)其“相似用戶”的行為預(yù)測目標用戶的潛在偏好；而內(nèi)容分析的主要思想是根據(jù)用戶之前對某些內(nèi)容的行為，推測用戶對相似內(nèi)容的行為；混合推薦則針對單一推薦的不足，按照不同的策略進行預(yù)測。協(xié)同過濾的運行效率取決于場景是否滿足如下假設(shè)：若用戶對一些內(nèi)容的行為相似，則他們對其他內(nèi)容的行為也大致相似。在古希臘，有這樣一句諺語：“觀其友，知其人”，在中國也有“近朱者赤，近墨者黑”的俗語。可見在大部分場景中，如Grundy、Amazon等，這個假設(shè)基本成立。

隨著推薦系統(tǒng)中用戶和內(nèi)容的不斷擴充，用戶的行為數(shù)據(jù)將出現(xiàn)極端稀疏性[6]，不僅降低了系統(tǒng)的推薦質(zhì)量，同時大大降低了算法的運行效率。

文獻[7]通過對用戶未知評分的項目的預(yù)測來降低稀疏性，但評分預(yù)測的正確性難以保證，需要大量有效數(shù)據(jù)進行訓(xùn)練。文獻[8]通過單值分解的方式降低項目空間維數(shù)，而降低維數(shù)導(dǎo)致部分有效數(shù)據(jù)丟失，難以保證推薦效果。文獻[9]通過項目分類信息，采用修正的條件概率方法計算項目相似性，同時通過預(yù)測降低稀疏性，從而提高推薦質(zhì)量。但在問題復(fù)雜度上并未做任何優(yōu)化，過多的預(yù)測值也制約著算法的可信度。

本文在上述改進的協(xié)同過濾算法的基礎(chǔ)上，針對大規(guī)模網(wǎng)絡(luò)環(huán)境的特征，設(shè)計了一種對網(wǎng)絡(luò)的合理分割與分組的用戶相似度計算方法SCSG（Similarity Calculate method based on Segmentation and Group，下文簡稱SCSG 算法），該方法能有效降低算法規(guī)模，同時緩解網(wǎng)絡(luò)稀疏性。

3 相似度計算

相似度計算算法是推薦系統(tǒng)中最核心的算法。相似度用于比較兩個用戶行為的相近程度。通常相似度沒有固定或者完全準確的值，在不同的環(huán)境中，相似度應(yīng)當有相對較為合理的一個計算公式。

習(xí)慣上，相似度通常滿足如下三個條件（這里使用Sim（α，β）表示用戶α和β 之間的相似度）：

（1）Sim（α，β）∈[0，1]，且相似度越高取值越接近1。

（2）Sim（α，α）＝1，即行為完全相同的用戶相似度為1。

（3）Sim（α，β）＝Sim（β，α），相似度具有無向性。

可見，相似度在性質(zhì)上與距離十分相似，故相似度的計算通常與距離的計算有一定的關(guān)系。

定義1 用戶特征向量pα為在某系統(tǒng)中用戶a 在n 維項目空間中的所有評分組成的向量。用戶a對項目i的評分用rα，i表示，用戶α 的特征向量表示為：

用戶特征向量在一定程度上可以反映該用戶對所有項目的喜好程度。但是，不同用戶之間對項目評分有不同尺度，為改善這種缺陷，引入用戶特征修正向量。

定義2 用戶特征修正向量是用戶的各評分減去用戶評分的平均分。用戶a 的修正向量表示為：

用戶相似性的計算方法常見的有三種：

（1）余弦法：用兩個用戶的用戶特征向量間的余弦夾角表示。

該方法可以度量用戶間的相似度，但用戶特征向量未考慮到用戶的評分特性。

（2）修正余弦法：考慮到不同用戶間對評分存在偏好，使用修正特征向量的余弦夾角表示相似度。

令I(lǐng)α表示用戶α 的所有評分項，令I(lǐng)αβ表示用戶α和β共同評分項，rα，c表示用戶α對項目c的評分，rβ，c表示用戶β 對項目c 的評分，對上式展開后為：

修正特征向量減去了用戶對項目的平均評分，該方法則更多體現(xiàn)了用戶間的相關(guān)性。

（3）相關(guān)相似性法：修正余弦法是對兩個用戶的所有評分項進行計算，而判斷用戶間的相似性更應(yīng)該關(guān)心用戶共同評分項。相關(guān)相似法的計算方法為：

若用戶α和β間存在關(guān)系Iα＝Iβ，則相關(guān)相似性法與修正余弦法等價。該算法能夠較好地體現(xiàn)用戶的相似度，但在大規(guī)模的互聯(lián)網(wǎng)應(yīng)用系統(tǒng)中，共同評分數(shù)據(jù)將出現(xiàn)極端稀疏性，影響相似度計算與算法效率。

可見，在大規(guī)模的應(yīng)用場景中，傳統(tǒng)的相似度算法存在極端稀疏性，對此文獻[7]提出對未知項目的評分進行預(yù)測，在一定程度上緩解了該問題。但是，預(yù)測值與實際情況難免存在誤差，這制約著預(yù)測算法的可信度。為避免出現(xiàn)上述情況，本文提出一種SCSG 算法，該算法通過對網(wǎng)絡(luò)的分割與分組，降低分割后每組網(wǎng)絡(luò)的稀疏程度，使得在分割后的組間計算相似度不出現(xiàn)極端稀疏現(xiàn)象。同時，分割后的網(wǎng)絡(luò)規(guī)模大大降低，提高了算法的運行效率。

4 分割算法

4.1 傳統(tǒng)解決稀疏性方法

目前，解決用戶-項目稀疏性的方法主要有以下兩種：

（1）矩陣填充技術(shù)。該方法旨在通過增加數(shù)據(jù)來緩解稀疏性。最簡單的填充方法為固定值填充，而不同用戶的評分一般不同，用固定值不符合實際情況，容易導(dǎo)致相似性失真。文獻[10]提出基于BP神經(jīng)網(wǎng)絡(luò)的內(nèi)容預(yù)測算法，該算法利用神經(jīng)網(wǎng)絡(luò)的學(xué)習(xí)能力對未知值進行預(yù)測，具有一定的可靠性。

（2）矩陣降維技術(shù)。文獻[9，11]提出一種奇異值分解的降維技術(shù)，它將m＊n 的矩陣分解為三個大小分別為m＊m、m＊n、n＊n 的矩陣，然后將分解后的矩陣進行降維處理。降維不僅使稀疏性問題得到解決，還降低了算法的復(fù)雜度。

上述兩種方法應(yīng)用在大規(guī)模網(wǎng)絡(luò)中存在一些問題，即忽略了算法預(yù)處理的復(fù)雜度：在基于BP神經(jīng)網(wǎng)絡(luò)的預(yù)測值填充方法中，很明顯，計算預(yù)測值的復(fù)雜度較高，通常網(wǎng)絡(luò)規(guī)模越大，矩陣的稀疏性越明顯，則要預(yù)測的值也非常多，在預(yù)測這一步驟中會消耗大量資源。同時，預(yù)測值終究不是確定值，在使用時難免出現(xiàn)誤差；而降維的方法，雖然表面上最終的計算量是減少了，但為了緩解降維時的信息丟失，在處理時需要通過選取合適的維度k，枚舉k的過程會造成較多的時間消耗。

在大規(guī)模網(wǎng)絡(luò)系統(tǒng)環(huán)境中，上述方法的預(yù)處理時間將會無法承受，直接影響相似度計算的效率。不難發(fā)現(xiàn)，上述算法在最終計算相似度時，數(shù)據(jù)集仍然為全部數(shù)據(jù)，這在網(wǎng)絡(luò)數(shù)據(jù)量很大時，計算時間將無法承受。

4.2 網(wǎng)絡(luò)分割

4.2.1 大規(guī)模網(wǎng)絡(luò)特征

網(wǎng)絡(luò)系統(tǒng)的數(shù)據(jù)量雖然制約著一些算法的實現(xiàn)，但通過分析不難發(fā)現(xiàn)，網(wǎng)絡(luò)具有一些其他性質(zhì)：

（1）網(wǎng)絡(luò)數(shù)據(jù)過多，存在相當一部分無效數(shù)據(jù)。這些數(shù)據(jù)在相似度計算時有負作用。

（2）網(wǎng)絡(luò)數(shù)據(jù)多，在分析時即使丟失一些有效值，對結(jié)論的影響不明顯。

（3）網(wǎng)絡(luò)數(shù)據(jù)龐大、隨機且復(fù)雜，這使得全網(wǎng)絡(luò)的某些特性不如某些子網(wǎng)的特征明顯。例如，分析學(xué)校學(xué)生的特性，以全校學(xué)生作為研究對象，得到的特征將會比較少，且大眾化，但若根據(jù)學(xué)院、性別等分別分析，得到的特征將更具有代表性。

從上面的特征可以看出，針對大規(guī)模網(wǎng)絡(luò)的分析，在不影響結(jié)論的前提下，對網(wǎng)絡(luò)進行合適的分割將會得到不錯的效果。

4.2.2 二分圖建立

定義3 用戶-項目圖Gu-i＝Vu∪Vi∪Er，其中，Vu為用戶頂點集，Vi為項目頂點集，Er為評分邊集。

所以用戶-項目圖是一個二分圖。

由于計算相似度時涉及矩陣運算，采用鄰接矩陣保存該圖。

4.2.3 圖的分割

將所有數(shù)據(jù)保存到一個圖結(jié)構(gòu)中，該圖必然相當龐大，不便于計算和分析。根據(jù)4.2.1節(jié)給出的大規(guī)模網(wǎng)絡(luò)特征，本節(jié)設(shè)計并給出以下四種分割規(guī)則，同時給出每種分割規(guī)則的算法描述與詳細流程。

這里以用戶u 為計算目標用戶，數(shù)據(jù)源為MovieLens給出的數(shù)據(jù)。

（1）連通分組。找到被預(yù)測用戶u的一個連通二分圖Gu。

連通分組剔除了與待測用戶毫無交集的用戶與項目集。由于是根據(jù)連通性分組的，這些被剔除的用戶-項目對預(yù)測結(jié)果的影響將非常小。

求連通圖的過程類似于對圖的染色，建立用戶-項目二分圖，利用FloodFill算法對用戶u 進行染色。

不難發(fā)現(xiàn)，使用FloodFill直接進行遞歸，將進行多次迭代，導(dǎo)致棧溢出。在遞歸時限制遞歸深度，防止算法執(zhí)行時過分盲目遞歸。

具體步驟如算法1所示。

算法1 連通分組算法UnionGroup（long Uid）

輸入：用戶u（Uid）。

輸出：連通二分圖Gu。

算法描述：計算包含用戶u的連通子圖。

在實際數(shù)據(jù)測試時發(fā)現(xiàn)，采用完全連通分量，最終得到的結(jié)果與原圖幾乎一樣，這樣不僅浪費了計算連通分量的時間，還未起到分割的作用。

不同的連通深度，在不同數(shù)據(jù)量下的分割情況如圖1所示。實驗數(shù)據(jù)表明，當遞歸深度在3以上時，子圖的規(guī)模大概為原圖的80%～90%，且隨著深度遞增；而當深度大于6 時，規(guī)模接近100%。該實驗數(shù)據(jù)與“六度分離”理論不謀而合。

Figure 1 Divided connected subgraph圖1 分割連通子圖

考慮到分割的效率，最終使用的深度為3。

具體步驟如算法2所示。

算法2 常規(guī)分割算法NormalR（Group Gu）

輸入：連通二分圖Gu。

算法描述：刪除常規(guī)項，并得到連通子圖。

在實際應(yīng)用中，常規(guī)項的選取將直接決定分割的實用效果，應(yīng)該由專用的數(shù)據(jù)挖掘系統(tǒng)給出，本文對此不作詳細討論。本文在實驗時采用的是選擇在邊中出現(xiàn)頻率最高的項代替常規(guī)項。

不同數(shù)據(jù)規(guī)模下，刪除多個常規(guī)項的分割結(jié)果如圖2所示。

根據(jù)實驗結(jié)果可知，前兩種算法適合數(shù)據(jù)量相對較小的網(wǎng)絡(luò)，隨著網(wǎng)絡(luò)的增大，對網(wǎng)絡(luò)微量的修改無法起到關(guān)鍵作用。

（3）無效項分割。若計算用戶u 對項目i 的一個預(yù)測評分，且i不屬于常規(guī)項。根據(jù)有效數(shù)據(jù)優(yōu)先原則，刪除對i項目無評價的用戶，并進一步連通分組。

Figure 2 General items divided subgraph圖2 常規(guī)項分割子圖

詳細步驟由算法3給出。

算法描述：刪除無效項，并得到連通子圖。

該分割策略帶有一定隨機性，由于無效項的刪除直接導(dǎo)致用戶數(shù)的減少，網(wǎng)絡(luò)的規(guī)模也隨之減少。根據(jù)實驗數(shù)據(jù)，平均的數(shù)據(jù)減少量可達30%。

（4）項目分類分割。

項目分類分割是在矩陣規(guī)模較大時設(shè)計的一種根據(jù)項目分類信息進行分割的分治算法。

由于有些項目可能有多種分組，在實際計算時需要對每個組分別進行相似度計算。

具體步驟如算法4所示。

算法描述：針對待預(yù)測項，對連通二分圖進行分類，并分組計算相似性。

項目分組分割可以將求解規(guī)模較大的矩陣分解為多個規(guī)模很小的矩陣間的運算，大大提升了相似度計算的效率。同時，采用同類不同種的項目的評分作為相似度的判定標準，在實際應(yīng)用場景中較不分組的方法，更具實際意義。

4.3 改進的協(xié)同過濾算法

4.2 節(jié)簡要敘述了網(wǎng)絡(luò)分割對運算復(fù)雜性的影響，同時給出了四種網(wǎng)絡(luò)分割算法，并分析了每種分割算法的特點。本節(jié)給出結(jié)合上述網(wǎng)絡(luò)分割的相似度計算流程。

相似度計算的最終結(jié)果為相似度矩陣。

定義4 用戶-項目相關(guān)相似度矩陣為：

其中Simi（α，β）表示α與β關(guān)于項目i之間的相似度。

計算組內(nèi)預(yù)測值的公式如下（用戶Uid 對項目Iid 的預(yù)測評分）[12]：

其中FUid＝｛F1，F(xiàn)2，…，F(xiàn)n｝為用戶u的組內(nèi)最近鄰居集。

具體步驟如算法5所示。

算法5 SCSG 算法SCSGCalcuSim（long Uid）

輸入：系統(tǒng)數(shù)據(jù)集DataSet，用戶編號Uid。

輸出：用戶的前10個推薦項目。

算法描述：生成用戶關(guān)于項目i的相關(guān)相似度矩陣。

5 實驗結(jié)果

本文的所有實驗數(shù)據(jù)均使用MovieLens網(wǎng)站公布的大規(guī)模數(shù)據(jù)測試集，同時MovieLens自身也是一個互聯(lián)網(wǎng)推薦系統(tǒng)。該測試樣例包含10 000 054項評分記錄、95 580個標簽、10 681部影片、71 567名用戶。為驗證計算結(jié)果的準確性，將評分數(shù)據(jù)的90%作為訓(xùn)練數(shù)據(jù)，10%作為測試數(shù)據(jù)。

平均絕對偏差MAE（Mean Absolute Error）是常用的衡量推薦系統(tǒng)推薦質(zhì)量的評價指標之一[13]。MAE 的計算方法如下所示：

本節(jié)使用MAE 作為指標，將對SCSG 的協(xié)同過濾法與傳統(tǒng)的余弦、基于修正數(shù)據(jù)的協(xié)同過濾法進行比較，判斷推薦質(zhì)量；使用算法運行時間作為指標判斷算法運行效率。

為測試算法運行效率，在測試數(shù)據(jù)中抽取20組樣例數(shù)據(jù)，分別使用傳統(tǒng)協(xié)同過濾法、修正協(xié)同過濾法和SCSG 協(xié)同過濾法進行測試。測試結(jié)果如圖3和圖4所示。

從圖3中可以明顯看出，在推薦優(yōu)劣程度上，SCSG 算法較傳統(tǒng)的協(xié)同過濾算法相似，MAE 略低于其他算法，原因主要在于對項目分組之后使得用戶之間的相似關(guān)系更加明顯。

Figure 3 Change of MAE with the number of neighbors圖3 MAE 隨鄰居個數(shù)變化圖

從圖4中可以看出，SCSG 算法的效率明顯優(yōu)于傳統(tǒng)的協(xié)同過濾算法。

Figure 4 Comparison of running time圖4 運行時間對比圖

可見，本文提出的算法在效率上較傳統(tǒng)的算法有明顯的提高，在推薦質(zhì)量上與傳統(tǒng)的推薦算法相似，效率上的提升使得該算法可以應(yīng)用于大規(guī)?；ヂ?lián)網(wǎng)環(huán)境中。

6 結(jié)束語

本文通過分析傳統(tǒng)的推薦系統(tǒng)的算法，在協(xié)同過濾算法的基礎(chǔ)上，結(jié)合大規(guī)模網(wǎng)絡(luò)的特性，提出一種基于網(wǎng)絡(luò)分割與分組的協(xié)同過濾算法SCSG。該算法通過四種規(guī)則對網(wǎng)絡(luò)進行分割、分組后，再利用協(xié)同過濾算法計算相似度，并進一步計算出預(yù)測評分，最終得到推薦項。該算法利用分治的思想，改善了傳統(tǒng)算法在大規(guī)模應(yīng)用場景中效率偏低的不足。算法主要探討了如何對網(wǎng)絡(luò)進行分割處理，網(wǎng)絡(luò)中的其他細節(jié)，如合理構(gòu)造常規(guī)項、制定項目分類標準等都有助于分割算法的進一步優(yōu)化。

[1]Adomavicius G，Tuzhilin A.Toward the next generation of recommender systems：A survey of the state-of-the-art and possible extensions[J].IEEE Transactions on Knowledge and Data Engineering，2005，17（6）：734-749.

[2]Xu Hai-ling，Wu Xiao，Li Xiao-dong，et al.Comparison study of Internet recommendation system[J].Journal of Software，2009，2.（2）：350-362.（in Chinese）

[3]Zhang G W，Li D Y，Li P，et al.A collaborative filtering recommendation algorithm based on cloud model[J].Journal of Software，2007，18（10）：2403-2411.（in Chinese）

[4]H?ubl G，Trifts V.Consumer decision making in online shopping environments：The effects of interactive decision aids[J].Marketing Science，2000，19（1）：4-21.

[5]Meng Xiang-wu，Hu Xun，Wang Li-cai，et al.Mobile recommender systems and their applications[J].Journal of Software，2013，2.（1）：91-108.（in Chinese）

[6]Huang Z，Chen H，Zeng D.Applying associative retrieval techniques to alleviate the sparsity problem in collaborative filtering[J].ACM Transactions on Information Systems（TOIS），2004，2.（1）：116-142.

[7]Deng Ai-lin，Zhu Yang-yong，Shi Bo-le.A collaborative filtering recommendation algorithm based on item rating prediction[J].Journal of Software，2003，14（9）：1621-1628.（in Chinese）

[8]Zhao Liang，Hu Nai-jing，Zhang Shou-zhi.Algorithm design for personalization recommendation systems[J].Journal of Computer Research and Development，2002，39（8）：986-991.（in Chinese）

[9]Zhou Jun-feng，Tang Xian，Guo Jing-feng.An optimized collaborative filtering recommendation algorithm[J].Journal of Computer Research and Development，2004，41（10）：1842-1847.（in Chinese）

[10]Zhang Feng，Chang Hui-you.Employing BP nerual networks to alleviate the sparsity issue in collaborative filtering recommendation system[J].Journal of Computer Research and Development，2006，43（4）：667-672.（in Chinese）

[11]Sarwar B M，Karypis G，Konstan J A，et al.Application of dimensionality reduction in recommender system—a case study[C]∥Proc of ACM Web KDD Workshop，2000：1.

[12]Breese J S，Heckerman D，Kadie C.Empirical analysis of predictive algorithms for collaborative filtering[C]∥Proc of the 14th Conference on Uncertainty in Artificial Intelligence，1998：43-52.

[13]Zhang Bing-qi.A collaborative filtering recommend action algorithm based on domain knowledge[J].Computer Engineering，2005，31（21）：7-9.（in Chinese）

附中文參考文獻：

[2]許海玲，吳瀟，李曉東，等.互聯(lián)網(wǎng)推薦系統(tǒng)比較研究[J].軟件學(xué)報，2009，2.（2）：350-362.

[3]張光衛(wèi)，李德毅，李鵬，等.基于云模型的協(xié)同過濾推薦算法[J].軟件學(xué)報，2007，18（10）：2403-2411.

[5]孟祥武，胡勛，王立才，等.移動推薦系統(tǒng)及其應(yīng)用[J／OL].軟件學(xué)報，2013，2.（1）：91-108.

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

[8]趙亮，胡乃靜，張守志.個性化推薦算法設(shè)計[J].計算機研究與發(fā)展，2002，39（8）：986-991.

[9]周軍鋒，湯顯，郭景峰.一種優(yōu)化的協(xié)同過濾推薦算法[J].計算機研究與發(fā)展，2004，41（10）：1842-1847.

[10]張鋒，常會友.使用BP神經(jīng)網(wǎng)絡(luò)緩解協(xié)同過濾推薦算法的稀疏性問題[J].計算機研究與發(fā)展，2006，43（4）：667-672.

[13]張丙奇.基于領(lǐng)域知識的個性化推薦算法研究[J].計算機工程，2005，31（21）：7-9.