協(xié)同過濾算法中相似度計算問題研究

樊艷清，梁宏宇，紀佳琪

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

0 引 言

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

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

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

1 相似度計算

文中以基于物品的協(xié)同過濾算法實現(xiàn)為基礎，即計算物品與物品之間的相似度從而得到物品相似度矩陣?；谖锲返膮f(xié)同過濾算法中最關鍵的步驟是如何計算物品間的相似度，然后選取最相似的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)調(diào)整的余弦相似度(adjusted cosine similarity)；(3)皮爾遜相關系數(shù)(Pearson correlation coefficient)；(4)歐幾里德相似度(Euclidean similarity)；(5)谷本系數(shù)(Tanimoto coefficient)。

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

1.1 余弦相似度

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

(1)

1.2 調(diào)整的余弦相似度

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

(2)

1.3 皮爾森相關系數(shù)

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

(3)

1.4 歐幾里德相似度

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

(4)

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

(5)

1.5 谷本系數(shù)

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

(6)

2 基于物品的協(xié)同過濾算法

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

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

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

(2)根據(jù)用戶評分矩陣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)根據(jù)對預測物品的評分值由高到低進行排序。

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

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

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

圖1 基于物品的協(xié)同過濾算法流程

3 實 驗

3.1 實驗環(huán)境

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

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

3.2 數(shù)據(jù)集

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

3.3 評價指標

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

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

(8)

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

(9)

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

(10)

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

(11)

其中，|I|表示系統(tǒng)中物品總數(shù)。

3.4 結果分析

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

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

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

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

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

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

圖4 相似度計算方式對調(diào)和平均數(shù)的影響

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

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

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

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

4 結束語

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