基于用戶模糊相似度的協同過濾算法

吳毅濤，張興明，王興茂，李晗

?

基于用戶模糊相似度的協同過濾算法

吳毅濤，張興明，王興茂，李晗

(國家數字交換系統工程技術研究中心，河南鄭州 450002)

針對離散評分不能合理表達用戶觀點和傳統協同過濾算法存在稀疏性等問題，借鑒年齡模糊模型，提出了梯形模糊評分模型。該模型將離散評分模糊化為梯形模糊數，考慮了評分模糊性和信息量，通過梯形模糊數來計算用戶相似度，據此設計了協同過濾算法，并證明了該算法是傳統協同過濾算法在模糊域的擴展。實驗表明，該算法在數據稀疏且用戶數遠多于項目數時性能突出，并且算法運行時間遠小于傳統協同過濾算法。

協同過濾；梯形模糊評分模型；模糊距離；模糊相似度

1 引言

電子商務的快速發展，使用戶難以處理種類繁多的信息。而推薦系統已經被證明能幫助用戶過濾無用信息，做出合理選擇[1~3]。推薦系統根據使用內容不同，可分為基于內容推薦系統和協同過濾推薦系統[4]。

基于內容推薦系統主要利用用戶的統計信息，如年齡、收入等，根據統計信息的關系進行推薦。協同過濾推薦系統根據評分信息尋找相似用戶，尋找相似性大的前個鄰居，根據鄰居的評分進行預測。算法的關鍵是選取合理的相似性計算方法。傳統算法大多采用余弦、Pearson等方法來計算用戶相似度。協同過濾推薦系統易于處理數據并易于實現，是最成功和流行的推薦系統。

但目前協同過濾推薦系統大都使用離散評分[5]，用戶在5評分等級集合{1,2,3,4,5}中選擇對項目的評分。但用戶對項目的喜好程度是非常模糊的，沒有特定的標準，離散評分不能合理表達用戶的觀點，例如離散評分不能表達介于評分4和評分5之間的喜好程度[6]。并且協同過濾系統沒有考慮評分信息量的問題，例如用戶評分為1攜帶的信息量比用戶評分為3攜帶的信息量要多。當評分矩陣稀疏時，協同過濾推薦系統的性能非常差。

為了合理表述用戶間的關系，Yager[7]引入模糊理論，用模糊子集表示統計信息間的關系；Shamri等[8]提出了統計信息模糊模型，建立統計信息同模糊語言的映射關系，通過模糊語言來計算其相似度；Le[9]利用統計信息模糊模型，計算其統計信息相似度，再利用Pearson算法計算評分相似度，加權兩部分得到最終相似度。在數據稀疏時，引入模糊理論的推薦系統精確度較高[10]，但忽略了評分的模糊性，只能片面表述用戶觀點，并且統計信息難于獲得和處理，引入模糊理論的推薦系統適用范圍很小。

上述研究表明，協同過濾推薦系統不能合理表達用戶的觀點，沒有考慮評分信息量，且存在稀疏性等問題，引入模糊理論的推薦系統只能片面表述用戶的觀點，且系統的適用范圍很小。

針對以上問題，本文借鑒統計信息模糊模型，提出了一種梯形模糊相似度模型，用模糊子集來表示用戶評分間的關系，建立離散評分值和梯形模糊評分值的映射關系，將用戶評分模糊化，并且考慮了評分的信息量，能合理表達用戶觀點。用梯形模糊評分進行用戶相似度計算，設計了基于用戶模糊相似度的協同過濾推薦（Fuzzy-UBCF）算法。實驗結果表明，在數據稀疏且用戶數遠多于項目數時，準確度高，并且算法運行時間遠小于傳統協同過濾算法。

2 理論基礎

2.1 模糊子集

引入模糊理論的推薦系統用模糊子集來表示統計信息間的關系，模糊子集是經典子集的推廣，它是具有不分明邊界的集合。Zadeh[11]對模糊子集的定義是：給定論域上的一個模糊子集，就是給定論域到區間[0,1]的一個映射，如式(1)所示。

(1)

Chen[12]定義梯形模糊數為(,,,;)，、、、分別表示梯形的4個頂點，并且是實數；表示對模糊數的最大隸屬度，0<≤1。梯形模糊數可以描述用戶對項目的喜好程度，梯形模糊數如圖1所示。

2.2 年齡模糊模型

Shamri[8]提出的年齡模糊模型描述了年齡同模糊語言的映射關系，如圖2所示。

將年齡作為給定論域，以梯形隸屬函數映射到模糊語言集中。相應的模糊語言集為{青年，中年，老年}，這種模型有以下優點。

1) 用模糊語言表示沒有特定標準的統計信息，一個年齡可能映射到2個不同的模糊語言集，能合理地表述統計信息間的關系。

2) 在實際中，統計信息和模糊語言的隸屬函數近似于正態分布，用梯形函數近似隸屬函數比較合理。

3) 模型左右對稱，用模糊梯形數表示模糊語言，計算簡單。

年齡模糊模型是統計信息模糊模型的一種，但統計信息模糊模型只考慮了用戶的部分信息，精確度較低，適用范圍小。

3 基于用戶模糊相似度的協同過濾推薦算法

本文用模糊子集來表示用戶評分間的關系，建立了梯形模糊評分模型，將模糊理論引入協同過濾推薦系統中。

3.1 梯形模糊評分模型

本文在年齡模糊模型優點的基礎上，對于一個5評分等級的集合，提出一種梯形模糊評分模型，如圖3所示。

梯形模糊評分模型將滿意度作為給定論域，用等腰梯形隸屬函數將滿意度映射到離散評分集中，滿意度表示用戶對項目的滿意程度，滿意度值越大，用戶對項目越滿意。梯形隸屬函數的隸屬度用信息量W來表示，信息量表示模糊數攜帶的信息的多少，信息量越大，模糊數攜帶的信息越多，信息量同模糊數出現的概率成反比，也就是同等腰梯形隸屬函數的面積成反比，梯形面積越大，信息量越小。

本文定義了2個參數：和。和可以表示用戶對一個項目的喜好程度，線段表示滿意度區間對離散評分為1的確定度，在此范圍內，離散評分和滿意度是一一映射；線段表示滿意度區間對離散評分為1的模糊度，在此范圍內，離散評分和滿意度不是一一映射。根據模型關系可得：≤0.25,≤。當不變，變大時，模糊評分數的確定度增加，適用于用戶和項目關系較緊密的數據集，也就是稀疏度低的數據集；當不變，變小時，適用于稀疏度高的數據集。同理，當不變，變大時，適用于稀疏度高的數據集；當不變，變小時，適用于稀疏度低的數據集。

由模型左右對稱，可知1=5，2=4。為了使W的值域為[0,1]，對W進行歸一化處理，如式(3)所示。

(3)

其中，max(1,2,3)表示1,2,3中的最大值。

根據模型對稱關系，得到5評分等級集合的梯形模糊評分值如式(4)所示。

(4)

3.2 模糊相似度計算

本文首次將Chen等[13]提出的梯形模糊數相似度計算方法引入推薦系統中，以此設計了用戶模糊相似度計算方法，并證明模糊相似度是余弦相似度在模糊域的擴展。梯形模糊數相似度計算方法考慮了梯形模糊數的常規距離和重心距離，如式(5)所示。

其中，a為梯形的第個頂點，(,)為梯形的重心，如式(6)所示。

W為梯形的信息量，用來決定是否運用重心距離，定義如式(7)所示。

(7)

根據式(5)可以得出2個用戶關于一個項目的相似度，加權所有項目的相似度就可以得到用戶模糊相似度，如式(8)所示。

其中，代表用戶和用戶的共同評過分的項目的集合，R,i表示用戶對項目的評分，為用戶評分的項目數，上式還考慮了用戶共同評分項目占總評分項目的比例，更能體現出用戶和間的差異。

可以證明模糊相似度是余弦相似度在模糊域的擴展。

其中，為用戶和共同評分的項目集合，()為集合中的項目數，為用戶評分的項目數。即曼哈頓距離M，是指2個點在標準坐標系上的絕對軸距離總和，也就是歐氏距離在坐標軸上投影的距離總和，歐氏距離E表示2個點的實際距離，如式(10)所示。它們的關系如圖4所示。

(10)

3.3 算法的流程

綜合模糊相似度的計算，本節給出Fuzzy-UBCF對目標用戶未知項目的預測評分集的流程。

算法 Fuzzy-UBCF (,)

輸入：用戶對項目的評分矩陣，用戶鄰居數。

Begin：

1) 用戶相似度計算。

①根據式(5)計算目標用戶和其他用戶關于一個共同評分的項目的相似度(R,R)。

②根據式(8)得出目標用戶和其他用戶的模糊相似度()。

2) 產生推薦集

①挑選出相似度最高的個用戶，作為鄰居集。

②對近鄰采用平均加權方法進行評分預測[14]，如式(12)所示。

其中，P表示用戶對項目的預測評分，()表示用戶和用戶之間的相似度，表示用戶項目評分的均值，通過參數來減弱平均值對預測評分的影響，增加預測的模糊性，本文令=0.8。

我們家那時生活條件差，穿的都是自己家紡織的土布，添置一件新衣服后穿上要愛惜，新衣服平時不能穿，只是出門時穿一下。一件衣服大的穿后小的穿，直到爛得不能再穿了。出門時沒有新衣服就是舊的也要洗干凈，家里人很重視儀表和聲譽。

輸出：目標用戶未知項目的預測評分集。

End

4 算法分析

4.1 基于用戶模糊相似度算法正確性分析

傳統相似性同用戶向量的夾角是正相關關系，同用戶向量的方向直接相關。模糊相似度同用戶間的距離是負相關關系，同個體特征的維度，即同用戶向量的長度直接相關。當用戶向量的方向保持不變，長度增加時，傳統相似度的值不變，而向量間的距離會變大，造成模糊相似度變小。所以項目數越多，模糊相似度的精確度越低。

傳統的相似性計算，是從整體上計算用戶差異，對單個用戶對項目的評分值不敏感，項目越多，評分矩陣越密集，越容易分析其差異，故傳統相似性適用于項目數多，且評分稀疏度低的數據集。而模糊相似性，分析的是用戶評分的絕對差異，對單個用戶項目的評分值敏感，用戶越多，項目數越小，即用戶項目比越大，越容易分析其差異，故模糊相似性適用于用戶項目比大的評分矩陣。

雖然模糊相似度只考慮用戶間的共同評分項目，一般來說共同評分項目很少，但本文將評分模糊化后，可以從項目較少的集合中獲取更多信息，在評分矩陣很稀疏時也有很好的效果。故模糊相似度算法適用評分稀疏且用戶項目比大的數據集。

協同過濾算法的時間開銷主要在相似度計算中，本文只考慮相似性計算的運行時間，若用戶的數量為，項目的數量為，余弦相似度算法的運行時間分析如表1所示。

表1 余弦相似度算法的運行時間分析

由于5遠遠大于1、2、3和4，故()=52=(2)，算法時間復雜度為(2)。

因為用戶模糊相似性需要先計算(R,R)，即用戶對單個項目的相似度，但只有5種評分，(R,R)只有25種可能值，可以提前計算出，這部分計算開銷可以忽略不計。模糊相似度算法的運行時間分析如表2所示。

表2 模糊相似度算法的運行時間分析

由于6遠遠大于1、2、3和4，故()=62=(2)，算法時間復雜度為(2)。

雖然模糊相似度和傳統相似度的算法復雜度都為(2)，但開銷5需要進行3+1次乘法，2(?1)加法，2次開方和1次除法，開銷6只需進行?1次加法和一次除法，故。Pearson相似度算法的運行時間遠高于余弦相似度算法的運行時間，所以模糊相似性算法的運行時間遠小于傳統相似性算法。

5 實驗與分析

5.1 數據集及實驗環境

本文使用的是Netflix電影評分數據集(評分值為1~5的整數)，用于Netflix Prize比賽中。Netflix有2個不同大小的數據集，具體參數如表3所示。

表3 數據集的具體參數

本文實驗環境為：win 7 操作系統，8 GB內存，Inter(R) Core(TM) i7-2600 CPU 3.40 GHz，實驗程序使用 java 1.5語言開發。

5.2 評價指標

本文采用平均絕對誤差作為算法性能的評價指標，如式(13)所示[15]。

其中，p為算法的預測評分，r為測試數據中的實際評分，為測試集中項目數目。越小，推薦精度越高。

5.3 比較算法及參數確定

本文采用以下2種算法作為對比算法。

余弦相似性的協同過濾算法(Cosine-CF)是協同過濾原始的經典算法。Pearson相似性的協同過濾算法(Pearson-CF)，在Cosine-CF的基礎上進行改進，是目前應用廣泛的算法，并且是基于用戶的共同評分項目進行計算相似度，和本文提出的算法相同。

為了選取合理的和，本實驗通過netflix_ 3m1k_split.txt文件，將Netflix_3m1k數據集中的95%作為訓練集，5%作為測試集。將各組合的減去基準（0.735 0），在把差值擴大500倍，對比在不同和組合下大小，實驗結果如圖5所示。可得，當0.36≤+≤0.38時，值比較小，經過多次實驗，本文選取=0.13,=0.23進行后續實驗。

5.4 實驗結果與分析

本實驗中隨機將80%的數據集作為訓練集，20%的數據集作為測試集。為了減少隨機分割數據集帶來的誤差，所有實驗都進行10次，取平均值作為最終結果。

實驗1 近鄰數對算法精度的影響

當近鄰數從5~50變化時，比較3種算法的大小。實驗結果如圖6和圖7所示。

從實驗結果可以得出以下結論。

1) 隨著的增大，3種算法的精度都會提高，但算法復雜度也會增加。當>20時，算法精度趨于平穩，故本文選取=20進行后續實驗。

2) 在Netflix_3m1k數據集中，隨著鄰居數的變化，Fuzzy-UBCF的精確度始終高于Cosine-CF，Cosine-CF的精確度始終高于Pearson-CF。

3) 在Netflix_5m3k數據集中，用戶項目比減小，隨著鄰居數的變化，Fuzzy-UBCF的精確度略低于Cosine-CF，Fuzzy-UBCF的精確度始終高于Pearson-CF。

實驗結果表明：Fuzzy-UBCF的算法在鄰居數較少時，有較高的精度，因為將評分模糊化后，一個鄰居所攜帶的信息更多。當用戶項目比減少時，Fuzzy-UBCF的精確度就會下降，因為Fuzzy-UBCF考慮用戶向量的距離，用戶項目比越小，用戶向量長度越長，精確度越低。當用戶項目比減小時，Fuzzy-UBCF性能變差。

Pearson-CF的效果很差，是因為本數據集稀疏度很高，用戶的共同評分項目很少，Pearson-CF沒有發揮出自己的優勢，在稀疏度低的數據集中，Pearson-CF的精度優于Cosine-CF。但Fuzzy-UBCF也是通過用戶的共同評分項目進行計算，說明了Fuzzy-UBCF的優點。

實驗2 稀疏度對算法精度的影響

在4.1節中，分析了Fuzzy-UBCF適用于評分矩陣稀疏的數據集，為了比較稀疏度對算法精度的影響，本實驗在Netflix_5m3k數據集中，保證用戶數和項目數不變，減少評分矩陣的稀疏度，當=20，比較3種算法的精度，實驗結果如圖8所示。

根據結果可以得出以下結論。

1) 隨著稀疏度增加，可用信息減少，3種算法的精確度都會下降。

2) Pearson-CF的精度很差，不適用于稀疏度高的數據集。

3) 在稀疏度低于99.1%時，Fuzzy-UBCF比Cosine-CF稍差，但隨著稀疏度的增高Fuzzy-UBCF的精確度高于Cosine-CF，而Cosine-CF隨稀疏度變大，性能惡化很嚴重。

Fuzzy-UBCF將評分模糊化后，適用于用戶和項目關系不明顯的數據集，也就是適用于稀疏度高的數據集。

實驗3 用戶項目比對算法精度的影響

在4.1節分析中，本文得出Fuzzy-UBCF適用于用戶項目比大的數據集，本實驗在Netflix_5m3k數據集中，=20，保證用戶和稀疏度不變，減少項目數來提高用戶項目比，比較3種算法的精度，實驗結果如圖9所示。

從結果可以得出以下結論。

1) 隨著用戶項目比增加，3種算法的精確度都會下降。這是因為項目數減少，可用信息減少，精度會降低。

2) 隨著用戶項目比的增加，Fuzzy-UBCF的精度會優于傳統的相似性算法。

可見，Fuzzy-UBCF適用于用戶項目比高的數據集。在實際系統中，用戶數是遠遠大于項目數的，并且數據集的稀疏度很高，所以Fuzzy-UBCF有很強的實用性。

實驗4 算法運行時間

在4.2節中分析了Fuzzy-UBCF的運行時間，本實驗來比較3種算法的運行時間，實驗結果如圖10所示。

可以得出，算法的運行時間關系為Pearson- CF>Cosine-CF>Fuzzy-UBCF。Fuzzy-UBCF的運行時間遠小于傳統的相似性計算方法。

實驗5和參數對算法精度的影響

在3.1節中，分析了和組合的適用范圍，本實驗對此進行驗證。在Netflix_5m3k數據集中，保證用戶數和項目數不變，減少評分矩陣的稀疏度，為了避免出現大的誤差，本實驗只對參數進行微調。

當=0.23時，分別為0.125、0.13和0.135時，比較Fuzzy-UBCF的精度。由于3組參數的實驗值很接近，為了便于比較，本文以=0.13、=0.23組合為基準，比較3種組合與=0.13、=0.23組合的差值。實驗結果如圖11所示。

從結果可以得出：當不變，變大時，適用稀疏度低的數據集；而不變，當變小時，適用于稀疏度高的數據集。

當0.13，分別為0.225、0.23和0.235時，比較Fuzzy-UBCF的精度。和上實驗一樣，比較3種組合與=0.13，=0.23組合的差值。實驗結果如圖12所示。

由實驗結果可知：當不變，變大，適用于稀疏度高的數據集；當不變，變小時，適用于稀疏度低的數據集。

6 結束語

本文提出了一種梯形模糊評分模型，將離散的評分模糊化，考慮了評分信息量等因素，能更合理地表達用戶的觀點，并提出了一種基于用戶模糊相似度的協同過濾算法，證明了Fuzzy-UBCF是傳統協同過濾算法在模糊域上的擴展，通過與傳統協同過濾算法比較，實驗結果表明本文提出的算法有以下優點。

1) Fuzzy-UBCF更適用于評分矩陣稀疏的數據集。

2) Fuzzy-UBCF適用于用戶項目比大的數據集，而現實的系統中用戶項目比都很大，故Fuzzy-UBCF有很強的實用性。

3) Fuzzy-UBCF的算法運行時間遠小于傳統的協同過濾算法。

本文下一步計劃，考慮用戶的評分尺度，對梯形模糊評分模型進行優化，并優化模糊相似度中信息量計算部分，尋找到更合理的模糊相似度的加權方法，進一步提高算法精度。

[1] 榮輝桂, 火生旭, 胡春華, 等. 基于用戶相似度的協同過濾推薦算法[J]. 通信學報, 2014,35(2):16-24. RONG H G, HUO S X, HU C H, et al. User similarity based couaborative fettering recommendation algorithm[J]. Journal on Communications, 2014,35(2):16-24.

[2] 李英壯, 高拓, 李先毅. 基于云計算的視頻推薦系統的設計[J].通信學報, 2013,34(Z2):138-140. LI Y Z, GAO T, LI X Y. Design of video recommender system based on cloud computing[J]. Journal on Communications, 2013, 34(Z2): 138-140.

[3] 丁欣, 馬嚴, 吳軍. 適用于校園網的視頻推薦系統的設計與實現[J].通信學報, 2013,34(Z2):175-179. DING X, MA Y, WU J. Design and implementation of a video recommendation system in campus network[J]. Journal on Communications, 2013,34(Z2):175-179.

[4] ZHAO Z D, SHANG M S. User-based collaborative-filtering recommendation algorithms on hadoop[C]//WKDD'10 Third International Conference on Knowledge Discovery and Data Mining. c2010: 478-481.

[5] YANG J M, LI K F. Recommendation based on rational inferences in collaborative filtering[J]. Knowledge-Based Systems, 2009, 22 (1):105-114.

[6] HUANG C K. Mining the change of customer behavior in fuzzy time-interval sequential patterns[J]. Applied Soft Computing, 2012, 12(3):1068-1086.

[7] YAGER R R. Fuzzy logic methods in recommender systems[J]. Fuzzy Sets and Systems, 2003, 136(2):133-149.

[8] SHAMRI M Y H, BHARADWAJ K K. Fuzzy-genetic approach to recommender system based on a novel hybrid user model[J]. Expert Systems with Applications, 2008, 35(3): 1386-1399 .

[9] LE H S. HU-FCF: a hybrid user-based fuzzy collaborative filtering method in recommender systems[J]. Expert Systems with Applications, 2014, 41(15):6861-6870.

[10] LUCAS J P, LUZ N, MORENO M N, et al. A hybrid recommendation approach for a tourism system[J]. Expert Systems with Applications, 2013, 40(9):3532-3550.

[11] ZADEH L A. Probability measures of fuzzy events[J]. Journal of Mathematical Analysis and Applications, 1968, 23(2):421-427.

[12] CHEN S H. Ranking generalized fuzzy number with graded mean integration[C]//The Eighth International Fuzzy Systems Association World Congress. c1999: 899-902.

[13] CHEN S J, CHEN S M. Fuzzy risk analysis based on similarity measures of generalized fuzzy numbers[J]. IEEE Transactions on Fuzzy Systems, 2003, 11(1):45-56.

[14] ZIEGLER C N, LAUSEN G. Analyzing correlation between trust and user similarity in online communities[J]. Lecture Notes in Computer Science, 2004:251-265.

[15] 朱郁筱, 呂琳媛. 推薦系統評價指標綜述[J]. 電子科技大學學報, 2012, 41(2): 163-175.

ZHU Y X, LYU L Y. Evaluation metrics for recommender systems[J]. Journal of University of Electronic Science and Technology of China, 2012, 41(2): 163-175.

User fuzzy similarity-based collaborative filtering recommendation algorithm

WU Yi-tao, ZHANG Xing-ming, WANG Xing-mao, LI Han

（National Digital Switching System Engineering and Technological R&D Center, Zhengzhou 450002, China)

In order to reflect the actual case of human decisions and solve the data sparseness problem of traditional collaborative filtering recommendation algorithm, a trapezoid fuzzy model based on age fuzzy model was proposed. In this model, crisp point was fuzzified into trapezoid fuzzy number and the fuzziness and information of users’ grade was taken into account when calculating user’s similarity by trapezoid fuzzy number. Based on this model, the user fuzzy similarity-based collaborative filtering recommendation algorithm was designed. The algorithm was proved to be an extension of traditional collaborative filtering algorithm in fuzzy fields. The experimental results show that, the proposed algorithm performs better when implemented in the sparse dataset with more user than item, and its running time is much less than traditional collaborative filtering algorithm.

collaborative filtering, trapezoid fuzzy model, fuzzy distance, fuzzy similarity

TP393

A

10.11959/j.issn.1000-436x.2016024

2014-12-08；

2015-06-15

國家重點基礎研究發展計劃（“973”計劃）基金資助項目（No.2012CB315901）；國家高技術研究發展計劃（“863”計劃）基金資助項目（No.2011AA01AA103）

The National Basic Research Program of China(973 Program)(No.2012CB315901), The National High Technology Research and Development Program of China (863 Program)(No.2011AA01AA103)

吳毅濤（1991-），男，陜西西安人，國家數字交換系統工程技術研究中心碩士生，主要研究方向為數據挖掘、社會化網絡、推薦算法。

張興明（1963-），男，河南新鄉人，國家數字交換系統工程技術研究中心教授，主要研究方向為通信與信息系統、寬帶信息網絡等。

王興茂（1989-），男，遼寧營口人，國家數字交換系統工程技術研究中心碩士生，主要研究方向為數據挖掘、用戶行為分析、推薦算法。

李晗（1987-），女，河南湯陰人，國家數字交換系統工程技術研究中心工程師，主要研究方向為嵌入式系統。