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

西南石油大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院，成都 610500

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

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

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

其次，利用兩個(gè)項(xiàng)目的特征向量構(gòu)建新三角距離．該距離將三角距離和Jaccard系數(shù)結(jié)合．這是因?yàn)樵谔崛√卣飨蛄亢?，損失了用戶、 項(xiàng)目以及評(píng)分之間的關(guān)系信息，僅保留用戶對(duì)項(xiàng)目評(píng)分的數(shù)量信息．若僅考慮三角距離，則無法精確判斷項(xiàng)目之間的相似度．考慮到Jaccard系數(shù)能充分利用共同評(píng)分項(xiàng)目數(shù)占所有項(xiàng)目數(shù)的比值信息，故結(jié)合Jaccard系數(shù)，從而在一定程度上彌補(bǔ)了原始評(píng)分信息.

最后，將設(shè)計(jì)的新三角距離用于k近鄰算法中，以判斷兩個(gè)項(xiàng)目的相似度．本文提出的NTRFC算法與基于其他距離的k近鄰算法在4個(gè)真實(shí)數(shù)據(jù)集上進(jìn)行對(duì)比實(shí)驗(yàn)，利用6種準(zhǔn)確度指標(biāo)和運(yùn)行時(shí)間進(jìn)行評(píng)價(jià)．實(shí)驗(yàn)結(jié)果表明：NTRFC算法運(yùn)行時(shí)間低于已有算法，并在大部分準(zhǔn)確度指標(biāo)上占優(yōu).

1 相關(guān)工作

本節(jié)介紹評(píng)分系統(tǒng)[10]定義和常見的幾種距離，本文使用的符號(hào)見表1.

表1 符號(hào)系統(tǒng)

1.1 評(píng)分系統(tǒng)

現(xiàn)回顧評(píng)分系統(tǒng)[10]的定義，令U={u1，u2，…，un}為一個(gè)推薦系統(tǒng)的用戶集合，令T={t1，t2，…，tm}為推薦給用戶的項(xiàng)目集合，由此，評(píng)分函數(shù)定義為

R：U×T→C

(1)

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

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

表2 評(píng)分矩陣(R)

1.2 已有的距離

k近鄰算法通常計(jì)算用戶或項(xiàng)目之間的距離來尋找用戶或項(xiàng)目的鄰居，從而預(yù)測(cè)用戶對(duì)項(xiàng)目的評(píng)分．表3列出了9個(gè)常用距離度量公式，并分析它們的時(shí)間復(fù)雜度.

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

表3 不同距離公式

2 NTRFC

NTRFC首先利用原始評(píng)分矩陣提取特征向量，然后基于特征向量設(shè)計(jì)新三角距離，最后將新三角距離應(yīng)用到k近鄰算法中.

2.1 特征向量的提取

項(xiàng)目的評(píng)分等級(jí)構(gòu)成通道集合C．例如，當(dāng)評(píng)分等級(jí)為1～5分時(shí)，通道集合C={1，2，3，4，5}．該集合包含有通道1～5，通道數(shù)l為5．為了處理項(xiàng)目的離散評(píng)分，本文將每個(gè)項(xiàng)目的評(píng)分映射到多個(gè)通道.

用戶ui對(duì)項(xiàng)目tp的評(píng)分rip與通道的關(guān)系為

(2)

其中c表示當(dāng)前通道數(shù)值.

當(dāng)rip與c相等時(shí)，連接用戶ui和通道c的邊的數(shù)量加1．項(xiàng)目tp上通道c的連接數(shù)為

(3)

對(duì)于長(zhǎng)度為l的通道，項(xiàng)目tp提取后的特征向量為

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

(4)

以表2展示的評(píng)分矩陣為例，項(xiàng)目t1對(duì)應(yīng)的特征向量為v1=[0，2，0，1，0]，如圖1.

圖1 多通道特征向量的構(gòu)建

2.2 新三角距離

利用特征向量，設(shè)計(jì)新三角距離公式為

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

(5)

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

NT(vp，vq)為

(6)

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

(7)

其中，Ip為對(duì)項(xiàng)目tp評(píng)過分的用戶集合；Iq為對(duì)項(xiàng)目tq評(píng)過分的用戶集合； |·|表示集合的基.

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

以表2展示的評(píng)分矩陣為例，使用新三角距離計(jì)算項(xiàng)目t1和t2相似度流程如下：

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

2) 計(jì)算NT距離為

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

將新三角距離應(yīng)用到k近鄰算法[19]中，預(yù)測(cè)用戶對(duì)項(xiàng)目的評(píng)分．其計(jì)算公式[20]定義為

(8)

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

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

2.4 算法描述

算法總結(jié)了NTRFC的具體步驟．步驟1讀取并初始化評(píng)分?jǐn)?shù)據(jù)； 步驟2根據(jù)式(2)至式(4)為每一個(gè)項(xiàng)目提取多通道特征向量； 步驟3初始化k個(gè)鄰居，并計(jì)算與鄰居的新三角距離，得到最遠(yuǎn)距離D； 步驟4至步驟10根據(jù)式(5)至式(7)計(jì)算與其余項(xiàng)目之間的新三角距離，并得到最終k個(gè)最近鄰居； 步驟11根據(jù)式(8)計(jì)算預(yù)測(cè)評(píng)分.

算法NTRFC

輸入：用戶-項(xiàng)目評(píng)分矩陣R

step 1：初始化評(píng)分?jǐn)?shù)據(jù)

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

step 3：初始化k個(gè)鄰居，并計(jì)算新三角距離，得到最遠(yuǎn)距離D

step 4：for其余有評(píng)分的項(xiàng)目do

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

step 6：if (d

step 7：用該項(xiàng)目替代最遠(yuǎn)距離項(xiàng)目

step 8：D=d

step 9：end if

step10：end for

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

3 實(shí) 驗(yàn)

針對(duì)提出的算法進(jìn)行兩組對(duì)比實(shí)驗(yàn)，用來回答以下兩個(gè)問題：1) 本文算法是否能提高推薦效率? 2) 本文提出的新三角距離能否保證較好的推薦準(zhǔn)確度?

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

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

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

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

表4 數(shù)據(jù)集

3.2 實(shí)驗(yàn)設(shè)計(jì)

通過兩組實(shí)驗(yàn)Exp1和Exp2分別回答本節(jié)開始提出的兩個(gè)問題.

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

Exp2：在輸入為特征向量時(shí)，分別采用本文提出的NTJ距離與另外9種距離進(jìn)行推薦準(zhǔn)確度對(duì)比實(shí)驗(yàn).

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

采用交叉驗(yàn)證的方式進(jìn)行實(shí)驗(yàn)，首先將原始評(píng)分隨機(jī)分為5等份，從中選取其中4份作為訓(xùn)練集，1份作為測(cè)試集； 其次，提取多通道特征向量，結(jié)合不同的距離預(yù)測(cè)評(píng)分； 最后，通過6個(gè)指標(biāo)來衡量預(yù)測(cè)評(píng)分與真實(shí)評(píng)分的差距．上述步驟重復(fù)5次，每個(gè)指標(biāo)下將得到5次不同的數(shù)據(jù)，將這些指標(biāo)平均后做對(duì)比實(shí)驗(yàn).

表5給出了6個(gè)準(zhǔn)確度評(píng)價(jià)指標(biāo).

表5 評(píng)價(jià)指標(biāo)

3.3 實(shí)驗(yàn)結(jié)果

3.3.1 Exp1的結(jié)果

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

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

圖2 4個(gè)數(shù)據(jù)集上的運(yùn)行時(shí)間結(jié)果

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

3.3.2 Exp2的結(jié)果

不同距離在4個(gè)數(shù)據(jù)集上的準(zhǔn)確度結(jié)果如表6．每一個(gè)子表包括5次實(shí)驗(yàn)的平均結(jié)果、 標(biāo)準(zhǔn)差和平均性能排名，NTRFC為本文提出的算法，括號(hào)中的數(shù)字表示當(dāng)前距離的性能排名．若平均結(jié)果相同，則比較標(biāo)準(zhǔn)差，標(biāo)準(zhǔn)差越小，性能越好.

在Amazon數(shù)據(jù)集上，本文提出的NTRFC算法在F1，Accuracy，Precision，MAE及RMSE評(píng)價(jià)指標(biāo)上排名第一，如表6(a)所示．在Movielens943u數(shù)據(jù)集上，本文提出的NTRFC算法在F1，Accuracy，Precision及Recall評(píng)價(jià)指標(biāo)上排名第一，如表6(b)所示．在Movielens706u數(shù)據(jù)集上，本文提出的NTRFC算法在F1，Precision及MAE評(píng)價(jià)指標(biāo)上排名第一，如表6(c)所示．在Eachmovie數(shù)據(jù)集上，本文提出的NTRFC算法在F1，Accuracy及Recall評(píng)價(jià)指標(biāo)上排名第一，如表6(d)所示．總體而言，在4個(gè)數(shù)據(jù)集上，NTRFC算法在個(gè)數(shù)準(zhǔn)確度指標(biāo)上占優(yōu).

表6 6個(gè)評(píng)價(jià)指標(biāo)下的實(shí)驗(yàn)結(jié)果對(duì)比

續(xù)表6

綜上所述，本文提出的NTRFC算法能有效提高算法效率節(jié)省時(shí)間，并保持較好的推薦準(zhǔn)確度.

4 結(jié) 論

本文提出了基于多通道特征向量的新三角距離高效推薦算法．多通道特征向量能降低算法的時(shí)間復(fù)雜度，新三角距離能更精準(zhǔn)地描述特征向量之間的相似度．在4個(gè)真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明，本文算法比已有算法在多個(gè)指標(biāo)上表現(xiàn)得更好.

下一步工作擬替換Jaccard系數(shù)，使用其他距離公式與三角距離結(jié)合，構(gòu)建新的距離公式．另外，考慮將新三角距離應(yīng)用到可解釋性推薦系統(tǒng)中，以期提升可解釋性推薦系統(tǒng)的性能.