多通道特征向量的新三角距離高效推薦

呂亞蘭，張恒汝，秦 琴，徐媛媛

西南石油大學 計算機科學學院，成都 610500

推薦系統是目前解決信息過載的有效手段．協同過濾[1]是主流的推薦算法之一，它利用歷史評分數據來獲取用戶對項目的偏好．協同過濾按照不同的實現方式可以分為基于k近鄰[2]、 基于矩陣分解[3]以及基于神經網絡的協同過濾算法[4]等．k近鄰利用歷史評分獲取k個具有相似偏好的用戶或者具有相似屬性的項目[2]，常用表征用戶或項目相似度的距離有：Cosine[5]，PCC(pearson correlation coefficient)[6]，Jaccard[7]和CPC(constrained pearson correlation)[8]．然而這些算法大都采用用戶或者項目的全局評分來計算相似度，導致其時間復雜度較高，推薦效率低.

本文提出了一種多通道特征向量的新三角距離推薦算法(new triangular distance recommendation algorithm for multi-channel feature vector，NTRFC)．算法的輸入為從原始評分矩陣中提取的多通道特征向量(簡稱特征向量)，在k近鄰算法中采用新三角距離，從而提高推薦效率并保持較好的推薦準確度.

首先，從原始評分矩陣中提取得到特征向量，其通道數目為原始評分矩陣中評分等級的數目[9]，將其作為輸入，可有效降低算法的復雜度．假定評分矩陣有n個用戶，m個項目，以及l個評分等級．以原始評分矩陣為輸入，計算相似度的時間復雜度為O(nm)，而以多通道特征向量為輸入，計算相似度的時間復雜度是O(lm)．評分矩陣中用戶數目n遠遠大于評分等級數目l，故O(lm)遠遠小于O(nm)．例如，數據集Amazon(http：//snap. stanford. edu/data/web-Amazonlinks. html)和Movielens943u (https：//grouplens. org/ datasets/movielens/100k/)的評分等級均為1～5分，故它們的通道數目為5，即每個項目的特征向量長度為5.

其次，利用兩個項目的特征向量構建新三角距離．該距離將三角距離和Jaccard系數結合．這是因為在提取特征向量后，損失了用戶、 項目以及評分之間的關系信息，僅保留用戶對項目評分的數量信息．若僅考慮三角距離，則無法精確判斷項目之間的相似度．考慮到Jaccard系數能充分利用共同評分項目數占所有項目數的比值信息，故結合Jaccard系數，從而在一定程度上彌補了原始評分信息.

最后，將設計的新三角距離用于k近鄰算法中，以判斷兩個項目的相似度．本文提出的NTRFC算法與基于其他距離的k近鄰算法在4個真實數據集上進行對比實驗，利用6種準確度指標和運行時間進行評價．實驗結果表明：NTRFC算法運行時間低于已有算法，并在大部分準確度指標上占優.

1 相關工作

本節介紹評分系統[10]定義和常見的幾種距離，本文使用的符號見表1.

表1 符號系統

1.1 評分系統

現回顧評分系統[10]的定義，令U={u1，u2，…，un}為一個推薦系統的用戶集合，令T={t1，t2，…，tm}為推薦給用戶的項目集合，由此，評分函數定義為

R：U×T→C

(1)

其中，R為一個n×m的評分矩陣；R=(rip)n×m；C表示用戶評價每個項目的評分等級構成的集合，如C={1，2，3，4，5}.

表2給出了一個用戶數為5和項目數為6的評分矩陣．評級為1～5分，則通道數為5．評分反映出用戶對項目的喜愛程度，分值越高表示用戶越喜愛該項目，0表示用戶未給項目評分．rip表示用戶ui給項目tp的實際評分，G(tp，tq)表示對項目tp和tq共同評分的用戶集合．例如，r12=3表示用戶u1給項目t2評分為3分，G(t1，t2)={u1，u4}表示對項目t1和t2共同評分的用戶是u1和u4.

表2 評分矩陣(R)

1.2 已有的距離

k近鄰算法通常計算用戶或項目之間的距離來尋找用戶或項目的鄰居，從而預測用戶對項目的評分．表3列出了9個常用距離度量公式，并分析它們的時間復雜度.

表3中，Cosine[5]，ED[11]，BC[12]，PCC[6]，MD[13]，S?rensen[14-15]，Canberra[16]，Lorentzian[17]和Divergence[18]距離的時間復雜度均為O(n)，但BC[12]距離的時間復雜度為O(l)．其中，n表示輸入向量的長度，l表示評分的等級數.

表3 不同距離公式

2 NTRFC

NTRFC首先利用原始評分矩陣提取特征向量，然后基于特征向量設計新三角距離，最后將新三角距離應用到k近鄰算法中.

2.1 特征向量的提取

項目的評分等級構成通道集合C．例如，當評分等級為1～5分時，通道集合C={1，2，3，4，5}．該集合包含有通道1～5，通道數l為5．為了處理項目的離散評分，本文將每個項目的評分映射到多個通道.

用戶ui對項目tp的評分rip與通道的關系為

(2)

其中c表示當前通道數值.

當rip與c相等時，連接用戶ui和通道c的邊的數量加1．項目tp上通道c的連接數為

(3)

對于長度為l的通道，項目tp提取后的特征向量為

vp=[d(tp，c1)，d(tp，c2)，…，d(tp，cl)]

(4)

以表2展示的評分矩陣為例，項目t1對應的特征向量為v1=[0，2，0，1，0]，如圖1.

圖1 多通道特征向量的構建

2.2 新三角距離

利用特征向量，設計新三角距離公式為

NTJ(vp，vq，tp，tq)=NT(vp，vq)×Jaccard(tp，tq)

(5)

其中，vp，vq分別為項目tp，tq的特征向量．NT(vp，vq)為三角距離，Jaccard(tp，tq)為Jaccard系數.

NT(vp，vq)為

(6)

其中‖·‖為向量的二范數．Jaccard(tp，tq)為

(7)

其中，Ip為對項目tp評過分的用戶集合；Iq為對項目tq評過分的用戶集合； |·|表示集合的基.

為了更準確地描述項目之間的相似度，新三角距離引入Jaccard系數．這是由于原始評分矩陣進行特征向量提取后，損失了用戶、 項目以及評分之間的對應關系信息，只保留了用戶對項目評分的數量信息．如果僅使用三角距離或其他一般距離則無法準確計算項目之間的相似度．以表2中項目t5和t6為例，通過提取后它們的特征向量v5和v6均為[0，0，0，1，1]，使用三角距離計算后相似度為1，使用Cosine距離計算后相似度也為1．但實際上，t5和t6的評分分別來源于完全不同的用戶u1，u2和u4，u5．使用新三角距離計算得到相似度為0，更加合理.

以表2展示的評分矩陣為例，使用新三角距離計算項目t1和t2相似度流程如下：

1) 提取項目t1和t2的特征向量v1=[0，2，0，1，0]和v2=[0，1，1，1，0].

2) 計算NT距離為

2.3 基于新三角距離的k近鄰算法

將新三角距離應用到k近鄰算法[19]中，預測用戶對項目的評分．其計算公式[20]定義為

(8)

1) 分別提取項目t1，t3和t4的特征向量v1=[0，2，0，1，0]，v3=[1，1，0，2，1]和v4=[1，2，0，1，1].

2) 使用新三角距離分別計算項目t1和t3，t4之間的相似度NTJ(v1，v3，t1，t3)=0.11，NTJ(v1，v4，t1，t4)=0.25.

2.4 算法描述

算法總結了NTRFC的具體步驟．步驟1讀取并初始化評分數據； 步驟2根據式(2)至式(4)為每一個項目提取多通道特征向量； 步驟3初始化k個鄰居，并計算與鄰居的新三角距離，得到最遠距離D； 步驟4至步驟10根據式(5)至式(7)計算與其余項目之間的新三角距離，并得到最終k個最近鄰居； 步驟11根據式(8)計算預測評分.

算法NTRFC

輸入：用戶-項目評分矩陣R

step 1：初始化評分數據

step 2：根據式(2)至式(4)提取特征向量

step 3：初始化k個鄰居，并計算新三角距離，得到最遠距離D

step 4：for其余有評分的項目do

step 5：根據式(5)至式(7)計算新三角距離d

step 6：if (d

step 7：用該項目替代最遠距離項目

step 8：D=d

step 9：end if

step10：end for

算法時間復雜度分析如下：步驟1讀取評分數據的時間為O(nm)； 步驟2提取多通道特征向量的時間為O(nm)； 步驟3初始化并計算與k個鄰居的距離時間為O(kl)； 步驟4至步驟10獲得最近k個鄰居的時間為O(ml)； 步驟11預測評分的時間為O(k)．故整個模型的時間復雜度為O(nm).

3 實 驗

針對提出的算法進行兩組對比實驗，用來回答以下兩個問題：1) 本文算法是否能提高推薦效率? 2) 本文提出的新三角距離能否保證較好的推薦準確度?

問題一中采用特征向量或原始評分矩陣作為輸入，使用本文提出的NTJ距離與另外9種距離計算項目間的相似度，利用k近鄰算法進行協同過濾推薦，比較兩者的運行時間從而判斷何種輸入下的推薦效率更高.

問題二比較使用NTJ距離或其他9種距離的k近鄰算法推薦準確度的高低.

3.1 數據集

本文使用Amazon，Movielens943u，Movielens706u (https：//grouplens.org/datasets/movielens/100k/)和Eachmovie (http：//www.research.digital.com/SRC/eachmovie/)數據集．表4給出了它們的基本信息，前3個數據集采用的評分等級是1～5分，Eachmovie數據集采用的評分等級是0.2～1分，0分表示用戶沒有給項目評分．在提取特征向量時，將Eachmovie數據集的評分等級擴展為1～5分，預測后按比例還原.

表4 數據集

3.2 實驗設計

通過兩組實驗Exp1和Exp2分別回答本節開始提出的兩個問題.

Exp1：比較輸入分別為特征向量和原始評分矩陣的算法的運行時間．使用本文提出的NTJ距離與另外9種距離計算項目間的相似度，并將其應用于k近鄰算法．記錄不同輸入下，使用同樣距離公式的算法在4個數據集下的運行時間，運行時間越少，表示推薦效率越高.

Exp2：在輸入為特征向量時，分別采用本文提出的NTJ距離與另外9種距離進行推薦準確度對比實驗.

在本文使用的k近鄰算法中，設置兩個參數LR和TR．LR表示用戶是否喜歡某項目的門限值，設置為3．TR表示是否給用戶推薦某項目的門限值，設置為3.5.

采用交叉驗證的方式進行實驗，首先將原始評分隨機分為5等份，從中選取其中4份作為訓練集，1份作為測試集； 其次，提取多通道特征向量，結合不同的距離預測評分； 最后，通過6個指標來衡量預測評分與真實評分的差距．上述步驟重復5次，每個指標下將得到5次不同的數據，將這些指標平均后做對比實驗.

表5給出了6個準確度評價指標.

表5 評價指標

3.3 實驗結果

3.3.1 Exp1的結果

在4個數據集上，分別使用特征向量和原始評分作為輸入，采用本文提出的NTJ距離和其余9種已有距離計算項目相似度的k近鄰算法的運行時間結果，如圖2，其中圖2(d)在Eachmovie上的運行時間進行了對數處理.

以NTJ距離為例，對運行時間結果進行簡要分析．在Amazon數據集上，采用特征向量作為輸入使得運行時間下降了39.33%，如圖2(a)．在Movielens943u數據集上，采用特征向量作為輸入使得運行時間下降了48.79%，如圖2(b)．在Movielens706u數據集上，采用特征向量作為輸入使得運行時間下降了40.67%，如圖2(c)．在Eachmovie數據集上，采用特征向量作為輸入使得運行時間下降了52.54%，如圖2(d).

圖2 4個數據集上的運行時間結果

綜上所述，使用特征向量作為輸入，能有效提高算法效率并大幅減少運行時間.

3.3.2 Exp2的結果

不同距離在4個數據集上的準確度結果如表6．每一個子表包括5次實驗的平均結果、 標準差和平均性能排名，NTRFC為本文提出的算法，括號中的數字表示當前距離的性能排名．若平均結果相同，則比較標準差，標準差越小，性能越好.

在Amazon數據集上，本文提出的NTRFC算法在F1，Accuracy，Precision，MAE及RMSE評價指標上排名第一，如表6(a)所示．在Movielens943u數據集上，本文提出的NTRFC算法在F1，Accuracy，Precision及Recall評價指標上排名第一，如表6(b)所示．在Movielens706u數據集上，本文提出的NTRFC算法在F1，Precision及MAE評價指標上排名第一，如表6(c)所示．在Eachmovie數據集上，本文提出的NTRFC算法在F1，Accuracy及Recall評價指標上排名第一，如表6(d)所示．總體而言，在4個數據集上，NTRFC算法在個數準確度指標上占優.

表6 6個評價指標下的實驗結果對比

續表6

綜上所述，本文提出的NTRFC算法能有效提高算法效率節省時間，并保持較好的推薦準確度.

4 結 論

本文提出了基于多通道特征向量的新三角距離高效推薦算法．多通道特征向量能降低算法的時間復雜度，新三角距離能更精準地描述特征向量之間的相似度．在4個真實數據集上的實驗結果表明，本文算法比已有算法在多個指標上表現得更好.

下一步工作擬替換Jaccard系數，使用其他距離公式與三角距離結合，構建新的距離公式．另外，考慮將新三角距離應用到可解釋性推薦系統中，以期提升可解釋性推薦系統的性能.