復雜網絡觀點傳播模型下的推薦系統評分預測

艾 均，卞紫鶯，蘇 湛

0 引言

各種現實世界的系統都可以用復雜網絡建模［1-3］，然后通過復雜網絡理論進行分析，包括生物系統［4］、社交網絡［5-10］、語義分析［11］、互聯網［12］、鏈路預測［13-15］、軟件［16-18］等，甚至流行的推薦系統也可以用社交網絡［19］或復雜的網絡模型進行補充，以進行分析和改進［20-24］。

復雜網絡理論為人們提供了多種有效工具以分析甚至控制復雜系統［25-29］。例如，中心性可用于衡量復雜系統中節點的相對重要性，并對網絡中的個體進行定量排序［30-31］。社團檢測可以發現在復雜系統中緊密耦合的小組，并有效地分組［4，32］。諸如中心性和社團發現之類的復雜網絡分析方法可以幫助本研究更深入地了解復雜系統的特征。

具體而言，推薦系統也可以使用復雜的網絡進行建模和分析，包括使用二部圖模型進行評分預測［33］，使用社交網絡信任關系以提高推薦系統的準確性［34］，以及對用戶關系或物品之間的關系進行建模以構建用戶—用戶網絡或物品網絡，研究推薦系統中個體之間的關系［22］。

在推薦系統中，如果將用戶和物品視為兩種類型的節點，則將物品的用戶評分視為鏈接，而評分分值是鏈接的權重。推薦算法或評分預測算法有效預測用戶和商品之間的加權鏈接，假定指向鏈接權重較高的物品可能被用戶偏愛，并向他們推薦這些物品。這樣的算法不僅可以預測用戶評分，還可以分析缺少數據的網絡，并預測可能在網絡演化中未來出現的鏈接［33］。

目前已有基于計算個體之間歷史評分相似性矩陣進行預測或分析的方法［35］。例如，基于Pearson 系數的協同過濾（Collaborative Filtering，CF）通過衡量用戶間共同評分以評估相似性［36-37］；基于余弦系數的協同過濾使用余弦相似性代替皮爾遜相似性［37-38］。用戶觀點傳播（User Opinion Spreading，UOS）方法結合CF 算法和用戶觀點傳播過程使評分預測更精確［39］。

基于網絡拓撲結構局部信息的共同鄰居（Common Neighbor，CN）指標在較小時間復雜度下有較高的預測精度［40］。為了提高連邊之間的分辨率，Adamic 和Adar 在此基礎上提出了（Adamic-Adar，AA）指標［41］，通過共同鄰居的度突出節點對于共同鄰居不同的重要性。Javari 等［42］使用了資源分配（Resource Allocation，RA）指標［43］，該指標顯示了對用戶和物品雙向網絡中缺失鏈路的較好預估。物品全局配置文件擴展（Item Global Profile Expansion，IGPE）是一種推薦方法，它通過使用與用戶已評分項相似的項來擴展用戶評分文件［44］。Lemire 等［45］提出Slope One 算法，預先計算用戶對兩種商品評分的平均偏差。

為了進一步提高算法預測精度，本文在做各類算法實驗時對用戶觀點傳播算法進行著重研究。該算法假定用戶觀點在推薦系統的二部圖模型中傳播并且相互影響，相互影響的總和作為計算兩個用戶之間相似度的基礎。但該算法有兩個問題：首先，相似度計算結果分布太小（最大相似度可能小于0.03）；其次，該算法需要太多的鄰居才能獲得最佳預測精度。第二個問題可能源于前者，由于不可能準確區分哪個用戶更相似，因此需要通過更多相似鄰居以獲得最優預測結果。

1 相關工作

1.1 用戶觀點傳播

如文獻［39］所示，由于用戶的偏好或習慣，他們對物品評分會有所不同，因此，式（1）用于標準化評分以抵消偏差。

從理論上講，如果兩個用戶的所有共同評分都相似，則這兩個用戶應該相似。在式（2）中，使用以下方法評估用戶關系。

其中，di是物品i的度，du是用戶u的度。ɑui是可以推斷用戶u是否對物品i進行了評分的值。如果用戶u對物品i評分，則ɑui=1，否則，則ɑui=0。r～ui表示用戶u對物品i執行的標準化評分結果。

評分預測可以通過文獻［39］中給出的公式進行計算，本文引用了式（3）。

1.2 度中心性對推薦系統相似性網絡的影響

在文獻［24］的工作中，基于文獻［22］的復雜網絡建模方法，研究了物品度值在物品—物品復雜網絡中推薦算法評分預測誤差的影響，并發現物品度值所代表的受歡迎程度被高估了，這對評分預測的準確性產生了負面影響。因此，他們設計了抵消影響的方法。在此基礎上，本文通過設計相似度計算方法，研究度中心性對預測準確性的影響在推薦系統的用戶—用戶復雜網絡中是否同樣有效。如果可能，本文將使用該方法進一步提高推薦系統評分預測準確性。

1.3 推薦系統相似性網絡中的社團

對推薦系統的復雜網絡建模研究可以進一步分析物品社團差異對評分預測的影響［20］。研究表明，在相似復雜網絡中，同一社團的物品在預測過程中應具有更高的權重；相反，分布在不同社團中的物品應具有較低的權重。本文使用權重系數調整預測公式中不同鄰居的權重。與預測目標在同一社團中鄰居的權重增至1.3，不同社團中鄰居的權重減小到0.7。各種算法實驗表明，基于相似復雜網絡中社團分布差異的加權可以有效地提高預測準確性。但他們沒有使用這種方法檢測用戶觀點傳播（UOS）模型的特性。因此，本文結合這種方法對UOS 作進一步研究。

1.4 用戶相似度與置信度

Su 等［21］進行了一項研究，他們發現用于計算相似性的評分數目對評分預測具有重要影響。該工作設計了如下置信系數（Confidence Coefficient）。

其中，tuv是用戶u和v共同的評分數目。

該研究主要集中在設計一種新的相似性方法，同時考慮用戶之間的評分差異和置信度系數。

2 復雜網絡建模中觀點傳播的推薦系統評分預測

本研究基于置信度系數改進UOS 相似度，以解決UOS相似度總體較小的問題。因此，基于現有研究，可以設計如式（5）的相似性計算公式，該公式綜合考慮評分偏好觀點的傳播，以及計算時使用的評分數量。

圖1 顯示了訓練集中相似度值的分布情況（彩圖掃OSID 碼可見，下同）。兩種類型的相似性等式包括用戶觀點傳播（UOS）相似性和具有置信度系數的UOS 相似性（User Opinion Spreading-Confidence Coefficient，UOS-CC）。y軸是相似度值，x軸指示兩種不同的方法，它們的形狀寬度可以推斷相似度的分布概率。圖1 證實了UOS-CC 將UOS相似度的分布從0.03 增加到0.06，需要在實驗中探索這種相似性分布變化的影響。

Fig.1 Distribution of similarity degree value in training set圖1 訓練集中相似度值分布

研究基于改進的UOS 相似性，對用戶之間的關系進行復雜網絡建模。通過刪除低相似度的鏈接，將剩余的相似度作為用戶之間鏈接的權重，并且將用戶作為構建復雜網絡模型的節點；然后基于該模型，計算用戶節點的中心性及其社團差異；最后根據目標用戶相似度選擇目標用戶的鄰居集，并通過鄰居評分、鄰居度值、社團之間的差異以及鄰居與用戶之間改進的UOS 相似度預測目標用戶評分。此過程可以總結如下：①基于置信系數改進相似性，并計算用戶之間的相似性；②通過表示用戶的n個節點和表示用戶相似性的kn條鏈接的復雜網絡建立推薦系統模型；③計算建模網絡中節點的度值和社團；④根據改進的相似性結果，為每個目標用戶選擇一組鄰居；⑤基于共同評分、鄰居置信度的UOS 相似性、鄰居的度值和鄰居的社團差異預測目標用戶評分。

當通過復雜網絡對推薦系統進行建模時，關鍵問題是控制邊的數目。由于節點數由用戶數（n）決定，因此本文使用k操縱邊的數目。為了防止相似度低的節點被孤立，先為每個節點保留具有最高正相似度的邊。如果總共保留了nr條邊，則在其余邊中具有最高相似性的前kn=nr條邊將進一步保留，使k=m/n在網絡中保持不變。具有低相似性或負相似性的所有其它邊將從網絡中刪除。

表1 列出了具有不同k值建模網絡的詳細特征，表中3C 是UOS-3C 的縮寫。

Table 1 Detailed characteristics of the modeling network with k as input表1 以k 為輸入的建模網絡詳細特征

表1 中的結果顯示了一種模式，隨著k值和鏈路數量的增加，以及網絡直徑的持續減小，模塊度持續下降，平均聚類系數增加，平均路徑長度減小。即使在k增加到k=20后，平均聚類系數仍然不夠高，這意味著該網絡不是小世界網絡，結果與采用其他相似方法（如Pearson 或Cosine）開展的實驗不同。通常，基于Pearson 相似性和相同數據集的建模網絡具有較高的平均聚類系數，并且當k≥10 時，平均路徑長度較短（平均聚類系數可以大于0.74）。這種現象表明，由于系統中用戶核心觀點的傳播，UOS 的相似性與其他相似性方法不同。

圖2 通過訓練集中的數據將建模的推薦系統顯示為網絡。節點代表用戶，鏈接代表他們的相似性。節點顏色表示其社團的差異，節點大小表示其度值，邊的寬度表示它們的相似程度。不同用戶節點的度值在很大程度上是可變的，并且不同社團中的用戶與社團中節點的聯系更加緊密，這是本研究用度值和社團改進UOS 的原因所在。

Fig.2 UOS similarity network based on confidence coefficient（k=1.5）圖2 基于置信系數的UOS 相似性網絡（k=1.5）

在這樣的網絡中，用戶度值表示用戶的受歡迎程度，鏈接代表用戶之間的相似性，因此網絡中的高度值用戶意味著他的口味或偏好是普遍的。

在某些情況下，用戶的度值很重要，例如用戶u有兩個相似的用戶v1和用戶v2作為鄰居，它們相似度相同，suv1=suv2=0.8，度值高的v1有多數偏好，度值低的v2有少數偏好，后一個用戶v1應該根據文獻［24］中已有研究進行優先級排序。

因此，本研究基于相似度方法等式（5）和UOS 預測公式（3），利用如式（6）預測方法分析對用戶程度的影響。

其中，svu是用戶v和u之間的相似性，是用戶v給出的平均評分。該式選擇了n個用戶進行預測，而Degree*(v)是用戶—用戶復雜網絡模型中用戶v的歸一化程度。

此外，本文還知道在預測中應該相應地考慮在同一社團或不同社團的節點［20］。本文通過式（7）進行預測。

其中，w(uv)用于調整每對用戶之間的權重；cu和cv分別表示用戶u和用戶v的社團，這些社團由社團發現算法標記［46］。

本研究同時考慮用戶觀點傳播相似度和置信系數（Confidence Coefficient），節點在復雜網絡模型中的度值（Degree Centrality），以及節點社團特征（Community）進行推薦系統評分預測，故將本文算法命名為UOS-3C。

3 實驗設置

3.1 數據集與參數

為了測試所提出算法的性能，選擇MovieLens 作為基準數據集。Movielens 有671 個用戶和9 125 個電影，并且有105個評分（范圍從0.5 到5）。

為了更精確地測試所提出的算法，將折十交叉驗證應用于數據集。訓練集隨機分為10 個組。每組數據都被測試過，其余9 個組用于訓練。測試中的任何算法都會根據其他9 組提供的信息預測每個組，其中該算法會選擇ω個鄰居（ω∈{1,2,3,4,5,…,19,20,25,30,…,150}），將多個實驗取平均值以得出最終結果。

3.2 算法比較

由于目標方法主要集中在UOS 問題上，因此在下文中將使用UOS［39］進行比較。本文還基于文獻［20］添加了模塊化用戶觀點傳播（MUOS），被標記為MUOS，并用于基于物品的評分預測。本文提議的方法縮寫為UOS-3C，其中3C 表示置信系數、度中心性和社團差異。

3.3 評估標準

本研究選擇兩個度量標準衡量預測準確性，即平均絕對誤差（MAE）和均方根誤差（RMSE）［35］。通過將用戶給出的實際評分與算法給出的預測評分進行比較，MAE 和RMSE 越小，算法越精確。RMSE 在求和之前預測誤差平方，從而使大誤差更加明顯。

其中，測試集有n個用戶對物品的評分，是預測評分，而rui是測試集中的真實評分。

4 實驗結果

本文介紹了MAE 和RMSE 兩種比較預測結果好壞的方法。比較不同k、ω1和ω2參數下 評分預測的MAE 和RMSE 結果，通過實驗可以確定所提出方法的最合適參數。將本文方法與最近工作進行比較，以測試USO-3C 的有效性，如圖3 和圖4 所示。

Fig.3 MAE results predicted by UOS-3C algorithm under different k、ω1 and ω2 parameters圖3 UOS-3C 算法在不同的k、ω1 和ω2 參數下預測的MAE 結果

Fig.4 RMSE results predicted by UOS-3C algorithm under different k、ω1 and ω2 parameters圖4 UOS-3C 算法在不同的k、ω1 和ω2 參數下預測的RMSE 結果

對數據集進行折十驗證的實驗證明了本文方法的有效性。實驗結果表明，基于改進的UOS 相似度對推薦系統建模，根據用戶節點的度中心性和社團差異可以穩步提高系統評分預測準確性，提高幅度為0.7%～5.5%，獲得最好評分預測精度所需的鄰居數從130 個減少到20 個（減少84%）。

圖3 和圖4 顯示了在不同k、ω1和ω2參數下預測的MAE和RMSE 結果。可以看出，k=3，ω1=1.0，ω2=0.7 提供了最佳精度，增大或減小參數k都會增加預測總體誤差。與ω2=0.6和ω2=0.8 相比，ω2=0.7 會使具有不同社團鄰居的重要性降低30%，且準確性更高。

圖5 和 圖6 顯示了由UOS、MUOS 與提出的UOS-3C 進行評分預測的MAE 和RMSE 結果。可以看出，對于MAE 和RMSE，k=3，ω1=1.0 和ω2=0.7 提供了最佳精度。與原始UOS模型相比，UOS-3C 將預測準確度平均提高了1.3%，最高5.5%，最低0.7%，MAE 的最佳值為0.8%，平均提高了1.2%。RMSE 分別為最高5.4%至最低0.8%，最佳1.0%。

Fig.5 Results of MAE of UOS，MUOS and proposed UOS-3C algorithm in different neighbor numbers圖5 UOS、MUOS 與UOS-3C 算法在不同鄰居數目的MAE 結果

Fig.6 Results of RMSE of UOS，MUOS and proposed UOS-3C algorithm in different neighbor numbers圖6 UOS、MUOS 與UOS-3C 算法在不同鄰居數目的RMSE 結果

與UOS 模型相比，本文使用置信系數改進相似性計算結果［39］，后者將相似度分布增加到更大的數字（從0.03 到0.06）。此外，本研究還在推薦系統的建模復雜網絡中利用了用戶的度值和社團。實驗結果表明，與文獻［20］中的現有結果相比，UOS-3C 網絡的局限性在于，參數k必須很小（k=3）才能提供最佳精度，而不是文獻［20］中具有更多鏈接的更大的k=10。此外，研究結果表明，同一社團中用戶之間權重的增加對預測準確性會產生負面影響。

5 結語

用戶觀點傳播算法在推薦系統中的應用具有重要意義，為了解決用戶觀點傳播模型的兩個問題，即UOS 相似性的較小值分布和為達到最佳預測精度而需要大量鄰居，本文設計了一種方法，即通過復雜網絡模型中的置信系數、度中心性和社團差異，提高用戶觀點傳播的評分預測。

本文研究表明，基于中心性、社團和置信系數的方法可以將預測精確度提高最小0.7%、最大5.5%，同時，達到最佳精度所需的鄰居數量減少84%，說明本文方法的合理性與有效性。研究表明，在推薦系統中，用戶觀點的傳播在特定用戶中更為明顯，這些用戶有更多共同評分的物品、小眾品味且身處同一個社團中。

本文預測方法與實驗中的k值有關，與文獻［20］中使用的k不同，因此k與評分的最優預測精度之間的關系尚未完全確定。本文假設相似度計算方法對該現象具有決定性影響，不同相似性設計中所涉及的不同因素會影響由網絡拓撲表示的系統特性。

為了進一步研究該問題，本文設想了一系列推薦系統的復雜網絡模型，這些模型可以專門適用于各種相似性方法，本文比較并討論了實驗結果。并且，在k與最佳預測精度之間的關系中可以找到其他見解。后續將在其他作品中對該問題作進一步研究。