基于加權二部圖的個性化方案推薦

楊 珍，耿秀麗

（上海理工大學 管理學院，上海 200093）

隨著互聯網的快速發展，數據日益以幾億級別的速度增長，導致所需信息的獲取難度提升，推薦系統就是為了解決信息超載問題而出現的，它主要根據用戶歷史行為推薦相似產品或服務。電子商務類網站的推薦系統已經較為成熟，如阿里巴巴、亞馬遜等，都采用推薦技術向用戶推薦其可能感興趣的產品，挖掘潛在客戶，從而提高產品收益。方案設計是根據顧客需求確定設計方案的過程，隨著市場環境的變化，客戶需求越來越有個性化，企業需要設計個性化的產品/服務方案。傳統產品/服務設計方案的生成方法主要有配置技術、規則技術等，本文采用電子商務領域成熟的推薦技術研究個性化方案推薦技術，用于提高方案設計的精度和效率。

推薦技術是推薦系統的核心技術，根據以往顧客需求偏好、行為信息等建立興趣模型，并用推薦算法向新顧客推薦其未曾產生行為的產品或服務。協同過濾算法(collaborative filtering algorithm,CFA)作為推薦技術中應用比較成熟的算法之一，其基本思想是根據顧客需求行為的相似度來推薦資源。協同過濾算法的缺陷包括數據稀疏性、冷啟動性及用戶偏好各異等。其中，稀疏性是指用戶對已有產品或服務方案評分很少，導致形成的數據矩陣稀疏。冷啟動性是指在已有用戶-項目規則庫中，沒有可以依據的新用戶行為記錄，難以對其推薦預測目標。協同過濾算法理論研究主要分為兩種：基于模型的方法和基于內存的方法[1]。基于模型的CFA一般通過數據集訓練出用戶興趣模型，并基于此模型對新用戶進行推薦；而基于內存的方法則是通過建立用戶-項目的評分矩陣，既可以預測用戶缺失的數據，彌補數據稀疏性的問題，又能夠向用戶推薦相似的項目[2]。基于模型的方法構造模型的前期時間較長，但對用戶的響應速度最快，而基于內存的方法可以節省模型構建時間，且注重內部數據的完整性。本文側重于研究基于內存的CFA，并融合了基于模型的CFA建模的思想，即結合兩者的優勢。

協同過濾算法具有稀疏性、冷啟動及用戶偏好不一致等問題，基于內存的CFA也有類似問題，學者們對其進行了改進或修正，主要包含以下兩種情況：一是通過相似性度量的修改、最近鄰的選擇等提高推薦準確度；二是結合其他算法的CFA提高推薦效率，如結合矩陣分解、概率模型、貝葉斯模型及云模型等。針對第一種情況，文獻[3]采用基于改進相似度的CFA，構建網絡項目的特征相似性模型，得到項目特征鄰居并選擇前N項推薦給用戶，實現網絡干擾的有效過濾，從而避免稀疏數據評價中產生的不足；文獻[4]提出基于最近鄰的CFA，保證推薦精度提高的情況下，降低計算過程的復雜度；文獻[5]根據用戶歷史行為數據差異性，提出基于改進用戶相似度的算法，在相似度計算過程中添加平衡閾值，顯著優化用戶相似性并得到好的推薦結果。文獻[4-6]主要采用基于最近鄰的改進CFA方法，相互彌補最近鄰和CFA兩種方法的優劣勢，進而提高推薦精度。如文獻[6]在推薦算法中引入聚類方法，通過用戶評分構建動態多維用戶網絡，采用改進K-means 算法對用戶聚類，將預測目標推薦給用戶，形成應用于動態多維社會網絡中的個性化推薦算法，從而提高推薦精度。上述文獻中CFA的研究僅僅解決協同過濾中的數據稀疏性、冷啟動、用戶偏好不一致中的某項問題，并未全面考慮一次性解決這3個問題來提高推薦效率。本文綜合考慮這3個問題，提出基于二部圖的個性化推薦方法。首先，針對CFA的稀疏性問題，已有研究都是從彌補數據稀疏性的角度研究，文獻[7]采用二部圖算法，清理掉孤立的網頁服務結點和工作流結點，提高數據完整性以及網頁服務的推薦效率；文獻[8-9]采用二部圖與CFA結合的算法，解決數據稀疏性問題。考慮到二部圖可以緩解CFA稀疏性，但合并數據精度不高，本文引入文獻[10]中加權二部圖的思想，合并關聯度高的稀疏數據，形成完整性數據，提高數據處理的效率。其次，針對CFA的冷啟動問題，相關文獻研究采用基于內存的CFA預測目標，即改進自身算法，或是結合其他算法彌補CFA缺陷，而本文基于加權網絡改進CFA，對新用戶預測推薦方案，提高預測目標的精確性，解決冷啟動問題。最后，針對用戶興趣各異的問題，本文提出采用基于用戶特征以及方案特征評分的協同過濾算法，不僅解決了用戶偏好相異的問題，而且能夠依據用戶的簡單需求提供合適的方案，即通過計算產品功能性特征的相似度，將相似度高的產品予以推薦。

本文采用加權二部圖與加權網絡的協同過濾混合算法，考慮用戶偏好相異，將用戶特征引入推薦系統，合理化資源分配過程，提高推薦精度。該方法的具體過程分為3個部分。首先，確定用戶的特征屬性以及方案屬性，對原始數據庫中的用戶特征采用加權二部圖將用戶進行分類，形成新的用戶集；然后，采用加權二部圖計算方案特征相似度，將相似度高的用戶進行聚類，并采用TOP-N方法將相似用戶進行排序，形成規則庫；最后，采用協同過濾算法將新用戶的特征與規則庫中的用戶特征進行匹配，并推薦已有的定制方案。

1 研究框架

U=U1,U2,U3,···,UmUi(1≤i≤m)S=S1S2假設企業中的數據庫包含用戶數據集和方案數據集，用戶集 ，表示用戶類型，用戶定制產品的方案集表示方案類型。用戶集中的特征集為其中，與U組成用戶-特征的二維矩陣。方案集中的產品特征集為與 Sj組成方案-特征的二維矩陣。本文是對用戶與方案間的特征匹配，首先匯集用戶已定制的方案，采用加權二部圖，即確定用戶-方案間的權重，根據用戶相似特征分類，形成用戶-方案規則庫；然后采用基于加權網絡的CFA，對新用戶C=C1,C2,C3,···,Ck推 薦定制方案， Ch(1≤h≤k)表示單個用戶 ，其 所 提 需 求 特征CP=CP1,CP2,CP3,···,CPlCPq(1≤q≤l)與用戶-方案規則庫中的用戶特征進行相似度匹配，對方案集進行TOP-N排序并推薦，框架如圖1所示。

2 基于加權二部圖的用戶-方案模型

為了提高個性化方案推薦方法提供可靠方案的準確率，本文提出采用加權二部圖方法，合并高相似特征的用戶，建立用戶-多方案模型并對用戶方案排序，建立用戶-方案規則庫，這是整個方案推薦過程中的核心部分。因此，采用CFA匹配新用戶與規則庫中的用戶，推薦相應方案集，即如果有新用戶需要定制方案，可以根據其描述特征，從已有用戶-方案規則庫提取用戶特征匹配的規則，篩選適合的用戶方案予以推薦。

2.1 二部圖的概念

Guimera提出的原始二部圖，是指從隨機圖的期望值中，得出邊緣集數的累積偏差。無向圖G =(V,E)，G的每條邊為E，其頂點集合V可分為2個子集U和S。

圖1 用戶-方案評分二部圖Fig. 1 User-scheme score bipartite chart

定義1[7]二部圖。

二部圖是一類特殊的圖，圖中結點根據特性分為兩類，其中，被歸到同一類中的結點都具有相似的特性。邊則連接來自不同類的2個結點，表示結點之間的關聯。定義二部圖

式中：U為圖的一類結點的集合，U= {Ui}， Ui為一類結點集合的元素；S為另一類結點的集合，S={Sj}，Sj為另一類結點集合的元素；E為兩類結點連接的邊的集合，E={eij}，eij為集合的元素。

定義2[7]鄰邊。

二部圖鄰接矩陣A，B用于表示二部圖中的信息。aij，big為鄰接矩陣中的元素。

aij數值用于判斷結點間是否有連接，即用戶Ui有無選擇方案Sj，若選擇，則aij值為1，反之值為0，m和n分別表示二部圖中兩類結點的數量。big是指用戶Ui有無描述特征fg，若有，則該值為1，反之為0。

定義3[7]權重。

邊的權重是指邊兩端的結點間關聯的重要程度，用戶-方案之間的權重為 wij，表示方案Sj在Ui所有方案中評價值的比重，即用戶對方案的偏好度， wij越大，表示用戶對方案越認可，則用戶和方案之間的關聯性越強。

式中，rij表示用戶Ui對方案Sj的評分。

定義4 評分矩陣。

方案-特征間的評分表示為SPnt，是指特征在方案中的重要程度。用戶Ui對非功能性特征fg評分結果為 ，用戶對每個特征的認可程度從差到好表示為1-5，0表示用戶未選擇該特征，評分結果形成二維矩陣B。

如果用戶沒有選擇任何特征標簽，可以根據其定性描述，將其按專家打分重要性進行分類，轉化成定量化數據，從而解決模糊不確定的評價信息。

定義5 評價指標。

針對定性化描述的評價指標，具有模糊不確定性，而式（6）通過定量化方式來計算方案分配給用戶的比重。本文通過專家評分將定性指標轉為定量數據，采用式（6）計算出具體評分指標值。

式中：R表示適合用戶Ui的方案Sj排名計算方式； wij表示方案Sj在Ui所有方案中評分值的比重，為方案Sj被采用后被用戶評價的分值總和。

定義6[10]二部圖相似度。

當新用戶選擇方案時，根據其所描述的功能性或非功能性特征，計算新用戶Us特征fg與規則庫中用戶Ui特征相似度為simCU。

式中：big，bsg表示用戶Ui和Us是否選擇特征fg，表示用戶Ui和Us對特征fg的評價值；對共同評分特征的加權值。

2.2 基于加權二部圖的用戶-特征聚類過程

考慮到新用戶先前沒有方案推薦行為記錄,難以計算該用戶和其他用戶的相似度,即推薦算法的冷啟動問題,也是目前推薦系統面臨的關鍵問題。所以，在用戶-方案規則基礎上引入特征標簽，形成用戶-特征的推薦方案模型。采用加權二部圖對用戶特征分類，用戶將已有的特征評分矩陣投影在二部圖中，通過式（6）對用戶非功能性特征進行聚類，形成新用戶集這樣既減少冗余數據，節省存儲空間，又便于個性化方案的查詢和推薦，具體如圖2～4所示。

圖2 用戶-方案初始集Fig.2 User-scheme initial set

圖3 用戶-特征評分Fig.3 User-feature score

圖4 新的用戶-方案集Fig.4 New user-scheme set

首先取出用戶對特征的評分，其次利用式（6）求出用戶特征的相似度，將相似性高的近鄰用戶對應方案以及用戶-方案間的權重合并，形成一對多的方案集，既能壓縮用戶集，節約存儲空間，又能根據用戶-方案規則庫中的用戶特征匹配方案推薦，給予新用戶更多選擇推薦方案的機會。

對于大型體育賽事而言，觀眾是其最為重要的因素之一，研究觀眾的消費特點是運作管理大型體育賽事的前提所在。通過對三省省會城市觀賞型體育消費者的調查，到實地觀看體育賽事的男性比例為78.2%，女性為21.8%.表明較女性而言，男性更容易接受競爭與對抗的體育賽事。在影響觀眾的負面消費因素中，競賽水平欠佳、門票價格無法接受、運動員水平有限分別位于前三(如表2所示)。

2.3 基于加權二部圖的方案過濾推薦

依據形成的新用戶-方案集，針對局部用戶對應的方案集太多，如果都推薦給用戶，難以保證滿意度且效率低。對此，采用二部圖的鄰居元素、權重以及二部圖評價指標的計算方式，將同一用戶對應方案集由高到低排序，選取前N項的方案推薦，具體的過程用偽代碼描述如下：

現介紹具體步驟。

步驟1首先通過以往用戶方案的評價信息，計算并輸入到二部圖中，連接2個二部圖構建用戶-方案集，方案-特征集如圖5所示。SP表示方案特征的評分。

圖5 二部圖組合Fig.5 Combination of bipartite graphs

步驟2遍歷二部圖的結點，如用戶結點對應的方案結點為S2和S3，這是用戶-方案集的二部圖，方案S2對應特征為 P1，P2，P4，方案S3對應特征為P1，P3，這是方案-特征的二部圖。本步驟計算方案-特征之間的關系，先計算特征P在方案中對應的比重，如P1在S2的比重為P2，P4同理，得出加權分

同理，

式中：a21表示 S2與 P1之間的評分；a22，a24，a31，a33同理。

步驟3計算方案S2和S3在用戶結點的比重，對的值排序，篩選自己所需的方案。

通過以上步驟，本文對特征相似的用戶聚類及對應方案排序和推薦，形成用戶-方案規則庫，便于給新用戶推薦已有定制方案，提高方案推薦的效率。

3 改進的協同過濾算法

3.1 相關概念

皮爾森系數常用于推薦系統中的相似性計算，確定非功能屬性值的相似性。式（8）為皮爾森相關系數的計算方法。

式中：Iu和Iv分別表示用戶U和V評價過的非功能性特征F的集合；和分別表示用戶U和V對非功能性特征的評分；和分別表示用戶U和V對共同評價非功能性特征F的平均值。所以，用戶相似度的數值屬于閉區間[-1, 1]，值越大表示用戶U和V越相似。

式（9）為Jaccard系數的計算方法。

3.2 基于加權網絡的協同過濾算法

為了解決新用戶的方案定制推薦問題，建立一個加權網絡的評分項目，其中，每條邊的權重值為共同評分用戶的數量。此外，為了預測推薦目標的精確性,本文通過閾值限制匹配用戶，所以，在加權網絡中，2個用戶必須滿足其共同評分項的數量大于閾值這個條件，從而過濾掉權重低于閾值的用戶集[11]。

由于皮爾森相關系數主要在求解2個用戶之間評分相似度起作用，Jaccard系數側重于解決項目的評分相似度方面的問題，但是，都存在數據稀疏性問題，導致目標預測結果不精確。而連接強度通過拓撲結構弱化了稀疏性問題，一定程度上提高了預測準確率。綜合考慮以上3種方法，本文提出采用新用戶相似度計算公式：

4 實例研究及對比分析

4.1 實例研究

某汽車4S店想要提高銷售的效率，希望定制產品的個性化推薦方案，能夠準確地推送給新用戶，滿足其需求。與文獻[12]建立用戶偏好模型不同，本文建立用戶-特征和方案-特征2個模型，并用二部圖建立2個模型間的聯系。通過整理以往顧客購買產品歷史記錄信息，本文主要選取用戶購買實用性的家庭裝車型，選擇代表性強的數據，得出用戶特征包括: 變速箱f1，座位數f2，經濟環保f3，安全性f4，舒適性f5，售后服務f6，成本f7，用戶選擇的方案包括：小型車S1，S2，S3，SUV車型 S4，S5，S6，MPV車型S7，S8。方案特征包括：動力性P1，燃油經濟性P2，制動性能P3，汽車通過性P4，輪胎性能P5，載客數P6，汽車噪音P7，排放性能P8，安全性P9。具體的指標如表1和表2所示。

該企業的汽車銷售數據庫包括用戶方案對應的非功能性和功能性特征的數據。首先將非功能性數據，即用戶特征集取出，設置相似度閾值為0.9，并基于用戶特征計算相似度，超過給定閾值則合并用戶對應的方案集；其次采用基于二部圖排序的方法，篩選并得到某用戶的多方案，篩選前N項的方案給予推薦；最后采用改進CFA，對新用戶的某些需求特征與生成的方案規則庫匹配，現介紹具體的步驟。

步驟1根據汽車購買用戶特征，f2，f3，f4，f7由低到高用1-5表示，f1，f5，f6由低到高用1-4表示。采用式（6）計算特征數據相似度，但如果用戶并未對特征打分，依據其定性描述，采用專家已評定好的標準將其轉化為定量化數據。采用二部圖相似度式（6），計算用戶評價汽車特征的數據，如圖6所示，其中，權重設置為0.5。

表1 用戶特征指標Tab.1 User characteristics indicators

表2 方案特征指標Tab.2 Programme characteristic indicators

圖6 用戶-特征圖Fig.6 User-feature chart

以U1和U3的相似度計算為例，超過閾值0.9，因此，合并U1和U3的用戶特征，將U1和U3定制的方案聚集并組成。同理，合并用戶之間特征相似度超過0.9的方案，并以用戶共同評價特征的最大值作為新用戶評分值，相異的評價特征不變并保留，得出用戶-方案集其中，用戶方案權重由用戶對方案評分的比值決定，并代入圖7，具體過程如圖8所示。

圖7 合并后的用戶-方案集Fig. 7 Merged users-scheme set

圖8 合并后的用戶-特征集Fig. 8 Merged user-feature set

步驟2采用加權二部圖對每個購買汽車的用戶其對應的方案集排序，即根據方案特征的評分，通過1，2，3來表示方案特征的好壞，采用加權二部圖的方法計算并排序，選取排名靠前N項的方案推薦，具體如圖9所示。

圖9 用戶方案-特征集Fig.9 User scheme-feature set

步驟3基于步驟3生成的方案規則庫，給欲購買汽車的新用戶提供便利。當新用戶進入4S店購買汽車時，讓其提出需求汽車的非功能性特征F，采用1-5這5個等級評分。據此，本文采用CFA方法對相似度進行改進，將Jaccard系數閾值設置為0.8以及連接強度閾值都為0.6，如果計算出的連接強度或者Jaccard系數低于這個閾值，直接省去從用戶-方案規則庫中匹配的過程；如果滿足這個閾值范圍，則計算新相似度并用TOP-N算法排序，找出相似性最大的用戶所對應的方案集并推薦，如圖10所示。

圖10 新用戶-特征集Fig.10 New user-feature set

以新用戶C1特征匹配過程為例，將新用戶C1與規則庫中的用戶的非功能性特征匹配，采用式（7）～（11）計算，得出 J=11/18，雖然滿足給定的閾值0.6，但是，J不滿足給定值0.8，所以，省略此匹配用戶，與其他用戶特征重新匹配。將都符合給定的閾值，則繼續計算所以，同理，根據特征計算其他用戶與新用戶C1的相似度，如等，并排序。由此得出與新用戶C1的相似性最大，從而將經過篩選后的方案推薦給C1，的非功能性特征，包含汽車變速箱自動、耗油多、安全高、價位在20～30萬左右。據此，其所對應的方案Sn，汽車功能必須是越障能力高、輪胎防抱死性能好、汽車噪音中等、能保護頭頸，如SUV類型的車可以推薦給用戶。由此可見，本文的算法可以滿足潛在的或者不熟悉產品功能特征的但又想獲取性價比高的方案的用戶需求，既能幫助企業提高收益，又能提高方案推薦效率。

4.2 算法性能的對比分析

針對協同過濾算法的缺點，考慮數據稀疏性、冷啟動及用戶偏好不一致這3個問題，采取基于加權二部圖的個性化推薦方法來解決。加權二部圖方法是通過計算用戶-方案相似度，形成用戶-方案規則庫。推薦方案分為采用和未采用兩種形式，采用方案分為規則庫推薦和未推薦，分別用tp和fp表示；未采用方案分為規則庫推薦和未推薦，分別用tn和fn表示。 為了證明該算法的優越性，本文提出采用F-Score評價體系[13]，衡量該算法與傳統協同過濾預測目標的性能，主要包含準確率P，召回率R以及F-Score評價體系，具體定義為

準確率和召回率是用于衡量該算法構建規則庫的覆蓋率以及推薦精度，而F-Score是衡量這兩者間的綜合指標。本文以對某汽車4S店的方案的問卷調查數據為例，根據傳統協同過濾算法、已有的加權二部圖算法以及本文算法對Top-N中的前100，200，300，400，500項方案，分別計算評估體系的參數的總體平均值，結果如圖11所示。

由圖11可知，本文算法相比較協同過濾算法、加權二部圖算法而言，優越性很大。如在前300項的數據下，傳統CFA的綜合F-Score評價指標為0.47，加權二部圖的F-Score評價指標為0.60，而本文算法F-Score評價指標為0.783，明顯高于其他2個算法。在方案數較少的情況下，CFA和加權二部圖的F-Score評價指標值不相上下，直到方案數在200之后，綜合指標的差距才開始拉大，并且加權二部圖推薦性能明顯優于CFA。從圖11中可知，隨著方案數的增加，相比較CFA、加權二部圖的推薦效果，本文算法的推薦精度性能優勢越明顯，說明在推薦目標方案方面，本文算法更加有效，進一步證明本文算法能夠更好地預測新用戶的目標方案。

圖11 不同算法F-Score比較結果Fig. 11 F-Score comparison results of different algorithms

5 結束語

針對協同過濾算法執行過程中存在數據稀疏性、用戶興趣各異以及冷啟動問題，提出基于加權二部圖的個性化推薦算法予以解決，提高了推薦效率。本文算法的優點如下：

a. 采用二部圖方法計算用戶特征的相似度，將相似度高的用戶聚類，形成一對多的用戶方案集，節約了數據庫存儲空間，減輕了數據稀疏性。

b. 針對聚類后的用戶方案集，根據用戶對方案特征的評分，采用加權二部圖計算方案評分值，并用TOP-N排序，保留前N項方案，解決了用戶興趣各異的情況，為新用戶推薦不同的方案。

c. 對于零購買記錄的新用戶，本文采用改進相似度，即將皮爾森系數、Jaccard系數以及連接強度相結合，如對Jaccard系數以及連接強度設定閾值，相似度不滿足該閾值，直接省略推薦過程，反之，將與新用戶相似性高的用戶方案予以推薦。該方法解決了以往推薦算法的冷啟動問題，提高了算法執行時間以及推薦效率。

以上是本文算法的優點，但對于小型數據庫而言，方案相似度TOP-N排序方法效果不很明顯。此外，本文算法在實例分析中，也只是展示方案了解和實施過程，即將用戶-方案庫中的方案推薦給新用戶，并未針對用戶某些特殊需求，定制特殊方案，這也是本文下一步想拓展的研究方向。