協同過濾算法中相似度計算問題研究

樊艷清，梁宏宇，紀佳琪

(1.河北民族師范學院 信息中心，河北 承德 067000；2. 河北民族師范學院 數學與計算機科學學院，河北 承德 067000)

0 引 言

隨著大數據時代的到來，信息過載問題越來越嚴重[1-2]，現有的技術已不能很好地處理日益加速增長的數據，數據的增長率已遠大于人們的處理能力。在海量的文章、聲音、視頻中人們無法有效地查詢到需要的信息，技術的壁壘成為人們在海量數據中獲取有價值信息的障礙。雖然傳統的搜索引擎技術能夠解決人們在海量數據中搜索有效信息的問題，但是搜索結果依賴于用戶輸入的關鍵字且不能針對不同用戶的喜好給出個性化的結果，為此推薦系統應運而生[3-4]。

推薦系統根據實現方式的不同又可分為基于內容的推薦系統、協同過濾推薦系統、混合推薦系統和基于深度學習的推薦系統。其中協同過濾是推薦系統眾多算法中使用最廣泛、推薦效果較好的一種算法[5-6]。協同過濾算法并不需要獲取用戶信息和物品的屬性信息，只需要獲取用戶對物品的評分即可，因此數據獲取簡單，不需要抽取用戶或物品特征，算法實現也相對簡單。根據應用場景不同，協同過濾算法可劃分為基于用戶的協同過濾算法和基于物品的協同過濾算法[7-8]。基于用戶的協同過濾算法的主要思想是：根據用戶對物品的評分，計算用戶間的相似度，然后推薦相似用戶喜好而自己又沒購買的物品[9]。但是這種方法的可擴展性不好，隨著系統中用戶數量的不斷增加，用戶間的相似度計算將越來越困難?；谖锲返膮f同過濾算法的主要思想是：根據用戶對物品的評分，計算物品間的相似度，然后推薦給用戶和他們之前購買物品相似的物品[7,10]，由于系統中物品一般不會過多，因此可擴展性好，計算速度快。但是無論是基于用戶的還是基于物品的協同過濾算法，相似度的計算都是一個重要的中間環節，其采用不同的相似度計算方式，將會對最終的推薦結果產生較大影響。

然而，雖然目前很多研究給出了不同相似度計算方法[5,11-12]，但是卻很少有全面深入分析不同相似度計算方式對推薦結果產生影響的研究，也缺少從不同評價指標進行的對比評測。因此無法很好地指導工業實踐。為此，文中總結了基于物品的協同過濾算法中各種相似度的計算方式，并從準確率、召回率、平均調和數和覆蓋率這些指標進行了評測，并根據評測結果給出了理論上的解釋說明。

1 相似度計算

文中以基于物品的協同過濾算法實現為基礎，即計算物品與物品之間的相似度從而得到物品相似度矩陣。基于物品的協同過濾算法中最關鍵的步驟是如何計算物品間的相似度，然后選取最相似的k個物品。相似度計算的基本思想是找到所有用戶對兩個物品i和j的共同評分項，然后使用某種相似度計算方法計算物品i和j之間的相似度sij。例如，所有用戶對物品i的評分為[1,?,2,3,?](?號表示沒有評分),所有用戶對物品j的評分為[2,5,4,?,1],則需要計算向量[1,2]和向量[2,4]之間的相似度。文中提出的相似度的度量方式有[13-15]：

(1)余弦相似度(cosine similarity)；(2)調整的余弦相似度(adjusted cosine similarity)；(3)皮爾遜相關系數(Pearson correlation coefficient)；(4)歐幾里德相似度(Euclidean similarity)；(5)谷本系數(Tanimoto coefficient)。

為了論述清晰，首先給出文中用到的數學符號定義。設R表示用戶評分矩陣，在R中每一行表示用戶所有物品的評分，每一列表示某一物品被所有用戶的評分。rij表示R中的單元格，即第i行第j列，表示用戶i對物品j的評分。假設R中含有3個用戶對4個物品的評分，則R可以表示為：

1.1 余弦相似度

此時，兩個待計算相似度的物品被看作m維的兩個向量。余弦相似度通過計算兩個向量間的夾角余弦值來度量相似度，其取值范圍為[0,1]。夾角越小，余弦值越接近1，相似度越高。反之，夾角越大，余弦值越接近0，相似度越低。其計算公式如下：

(1)

1.2 調整的余弦相似度

基于用戶的協同過濾與基于物品的協同過濾在計算相似度時的不同處是：基于用戶的協同過濾是沿著評分矩陣R的行進行的，而基于物品的評分矩陣是沿著評分矩陣的列進行的，每一對共同評分項對應的都是不同的用戶，因此使用余弦相似度計算物品間相似度有一個重大缺陷：沒有考慮不同用戶對不同物品的評分尺度。而且余弦相似度從夾角(或方向)上度量了差異，對維度的數值并不敏感。例如，兩個用戶對兩個物品的評分分別為(1,2)和(4,5)，使用余弦相似度計算兩個物品的相似度結果都是0.98，說明兩個物品很相似，但從評分上顯然可以看出這兩個物品是不相似的。為了修正這種不合理性，需要在所有維度上減去一個均值，則調整的余弦相似度定義如下：

(2)

1.3 皮爾森相關系數

皮爾森相關系數描述了2個向量的線性相關性，其取值范圍為[-1,1]，越接近1表示越線性正相關，越接近-1表示越線性負相關，越接近0表示線性不相關。其定義為2個向量的協方差與2個向量標準差乘積的商，具體表示為：

(3)

1.4 歐幾里德相似度

歐幾里德一般是用來度量距離的，數值越大，其距離越遠[16]。因此可以取其倒數，這樣距離越遠，其倒數值越接近0，表示其相似度越低，數學定義如下：

(4)

公式中分母加1的主要原因是防止分母為0的情況出現，從公式中可以看出歐幾里得相似度的取值范圍為(0,1]。由于歐幾里得相似度需要參加計算的向量單位是一致的，因此，在應用該公式前，需要對參與計算的向量做標準化處理，公式如下：

(5)

1.5 谷本系數

谷本系數又稱廣義的杰卡德(Jaccard)相似系數[17]，它的實質是2個物品交集與并集的比值。傳統的杰卡德相似度只能計算只含0和1的向量，而谷本系數把其擴展到了實數范圍內，其定義如下：

(6)

2 基于物品的協同過濾算法

本節先介紹基于物品的協同過濾算法。與基于用戶的協同過濾算法不同，基于物品的協同過濾關注的是用戶評分的物品間的相似度。其主要思想是：計算物品i與其他物品間的相似度，并選擇k個最相似的物品{i1,i2,…,ik},物品i與其他k個物品間的相似度可以記為{si1,si2,…,sik}。找到最相似的k個物品后，通過計算待推薦用戶u對該物品的加權平均值就可以得到用戶u對物品i的喜好程度。因此基于物品的協同過濾算法主要是兩個過程：一是相似度的計算，二是喜好程度(用戶對物品的預測打分)的計算。

圖1展示了基于物品的協同過濾算法的主要過程：

(1)圖1左側是用戶評分矩陣R，每一行代表一個用戶，每一列代表一個物品，每一單元格代表某一用戶對某一物品的評分值。其評分值根據用戶的喜好程度從1至5不等(不同的數據集該處取值可能不同)。如果用戶尚未對某物品評分，則用一問號表示，也就是要預測的評分值。

(2)根據用戶評分矩陣R,利用第1部分介紹的相似度計算方法，可以計算得到兩兩物品間的相似度，從而得到物品間相似度矩陣。顯然采用不同的相似度計算方式，將得到不同的物品相似度矩陣。由于該矩陣是對稱矩陣(因為物品i1和物品i2的相似度與物品i2和物品i1的相似度是相同的)，因此在計算時只需計算不含對角線的上半角矩陣即可(對角線上的值全為1，即自身與自身的相似度為1)。

(3)計算用戶對物品的喜好程度，由式(7)完成用戶u對未購買的物品i進行評分預測。其原理是物品i被其他用戶評分的平均值加上用戶u對與i相似的k個物品的加權評分值。

(7)

其中，Pu,i表示用戶u對物品i的預測評分，s(n)表示與物品i最相似的k個物品的集合，即物品i的近鄰。

(4)根據對預測物品的評分值由高到低進行排序。

(5)選取n個預測評分最高的物品作為最終的推薦結果。

還有一種與上述方法相似的方法稱為回歸方法，這種方法使用回歸模型來近似評分而不再做權重的加和。

在實踐中，使用余弦相似度或皮爾遜相似度有可能得出一些錯誤結果，比如某兩個向量間距離很遠(使用歐幾里得距離計算)，但是計算出來的相似度卻很高。因此使用所謂的相似度計算可能導致不好的結果。但文中不考慮這種極端情況的出現，只做一個樸素的假設，即計算得出的相似度高就認為兩個物品間的相似度高。

圖1 基于物品的協同過濾算法流程

3 實 驗

3.1 實驗環境

為驗證不同相似度計算對推薦結果的影響，使用Java語言對所有算法進行了實現。使用的硬件環境為：Intel(R) Core(TM)i5-6200U CPU @ 2.30 GHz 2.40 GHz，內存8 G，250 G固態硬盤；軟件環境為：Win10操作系統，JDK1.7，Ecplise 3.5。

在實驗中，使用5折交叉驗證對推薦性能進行評價，即數據集被隨機分成互不相關的5份，在每一次迭代中做5次訓練，使用4份作為訓練集，使用1份作為驗證集，最后5次結果的平均值作為最終結果。

3.2 數據集

文中選取MovieLens ml-100k數據集，該數據集包含了1 000個用戶對1 700部電影的共10萬條評分，每條評分分值范圍都是1至5，分值越高表示用戶對該電影越喜歡。該數據集的提供者在發布前已經對其進行了數據清洗，保證每個用戶至少有20條評分。實驗前對數據集進行了隨機抽樣，其中80%作為訓練集，20%作為測試集。

3.3 評價指標

不同相似度計算方法對推薦結果影響的評價從以下幾個方面考量：

(1)精確度(precision)：是廣泛用于推薦系統中的一個度量指標。其反映的是推薦給用戶的物品中是用戶感興趣的占總推薦物品數的比例，即推薦出的物品有多少是準確的。設P(u)是根據訓練集得到的用戶u的推薦結果列表，T(u)是用戶u在測試集上的評分列表，則形式化定義如下：

(8)

(2)召回率(recall)：也稱查全率。其反映的是推薦給用戶物品中用戶感興趣的物品占用戶所有感興趣物品的比例，即用戶感興趣的物品中有多少被推薦出來了。其形式化定義如下：

(9)

(3)調和平均數(harmonic mean)：精確度和召回率是2個相互對立的評價指標，例如如果系統把所有物品都作為推薦物品，顯然這時精確度很低，但是召回率卻最高為1；反之如果系統推薦的物品都在測試集中出現，則此時精確度最高為1，但是召回率卻不高。從定義中可以看出精確度用來度量推薦的準確程度，而召回率用來度量推薦的查全程度。為了綜合這兩個指標，提出了調和平均數這個度量方式：

(10)

(4)覆蓋率：覆蓋率反映了系統給不同用戶推薦物品的集合(該集合內的物品是不重復的)占系統總物品數的比例。這個值越高說明系統能夠盡可能多地把每個物品都推薦出來。其定義如下：

(11)

其中，|I|表示系統中物品總數。

3.4 結果分析

在實驗中，固定選擇近鄰的個數為50，推薦列表的長度為20。同時為了提高實驗的準確性，采用5折交叉驗證方法，并取平均值作為最終的實驗結果。其實驗數據如表1所示。

表1 5種不同相似度計算方式在4種評價指標上的實驗數據

為了對上述數據進行分析與解釋，使用了5幅不同的圖形進行描述。圖2顯示了5種不同相似度對推薦精確度的影響，結果表明除了使用谷本系數時推薦精確度較低外，其余4種方式精確度非常接近，但皮爾森相關系數相對準確度最高。但余弦相似度和皮爾森相似度也有其固有的缺點，具體可以概括為如下四個方面：(1)扁平值問題：如果所有的評分值都一致，如(1,1,1),使用皮爾遜相似度會由于其分母為0而無法計算；使用余弦相似度的結果會都是1。(2)反向值問題：如果兩個用戶對物品的評分都是相反的，則皮爾遜相似度的值總是-1。(3)單值問題：如果兩個用戶只對一個物品有評分，則皮爾遜相關系數無法計算，余弦相似度的值總是1。(4)交叉值問題：如果2個用戶僅對2個物品評分并且2個向量相互交叉,如(1,3)和(3,1)，皮爾遜相關系數總為-1。

圖2 相似度計算方式對精確度的影響

圖3 相似度計算方式對召回率的影響

從圖3可以看出，除谷本系數外，其余4者的召回率依然非常接近，比較而言皮爾森系數和歐幾里德相似度表現略佳。皮爾森相似度與歐幾里德相似度的最大區別在于前者更重視數據集的整體性，因為皮爾森相似度計算的是相對距離，而歐幾里德距離計算的是絕對距離。就實際情況來說，使用皮爾森相似度可以適應不同量綱的數據集，而歐幾里德距離需要針對數據最歸一化，即使數據有相同的量綱。

圖4 相似度計算方式對調和平均數的影響

圖5 相似度計算方式對覆蓋率的影響

圖4中調和平均數是精確度與召回率的綜合考量，更加綜合地反映了對推薦結果的影響。不難看出皮爾森相關系數和杰卡德相似度相對表現最優異。

圖5反映了推薦給用戶的物品數占總物品數的比例，此時使用余弦相似度要好于其他相似度。

綜上分析，皮爾森相似系數在精確度、召回率、調和平均數指標中表現最佳，余弦相似度在覆蓋率指標上表現良好，而谷本系數無論在哪個指標上都遠遠落后于其他相似度計算方法。

4 結束語

協同過濾算法由于其良好的推薦效果得到了廣泛的應用。由于協同過濾算法的核心是相似度的計算方式，不同的相似度計算方式會對結果造成一定的影響。由于目前缺乏不同相似度計算方式對推薦結果能夠產生哪些影響的研究，因此文中詳細研究了5種不同相似度計算方法對基于物品的協同過濾推薦結果的影響，并通過不同的評價指標如準確率、召回率、調和平均數和覆蓋率進行了對比分析。下一步將研究其他協同過濾算法中相似度計算對推薦結果的影響，并基于不同數據集進行對比研究。