基于標(biāo)簽和協(xié)同過(guò)濾的改進(jìn)推薦算法研究

金晶， 懷麗波

( 延邊大學(xué) 工學(xué)院， 吉林 延吉 133002 )

0 引言

個(gè)性化推薦因有助于用戶快速地獲取所需信息，目前被廣泛地應(yīng)用于各種社交網(wǎng)絡(luò)、音視頻娛樂(lè)網(wǎng)站以及網(wǎng)絡(luò)商務(wù)平臺(tái)等.目前,推薦算法主要有協(xié)同過(guò)濾、混合推薦、基于內(nèi)容和基于人口統(tǒng)計(jì)的推薦等[1],但這些方法普遍存在數(shù)據(jù)稀疏、冷啟動(dòng)和可擴(kuò)展性的問(wèn)題.為緩解算法中存在的冷啟動(dòng)和數(shù)據(jù)稀疏問(wèn)題,一些學(xué)者對(duì)此進(jìn)行了研究.例如：劉健以TF-IDF(term frequency-inverse document frequency)計(jì)算用戶-標(biāo)簽相關(guān)度和項(xiàng)目-標(biāo)簽相關(guān)度的值,并依此構(gòu)建了用戶興趣模型,提高了推薦精度[2]；蔡強(qiáng)等以TF-IDF方法分別生成用戶和資源的標(biāo)簽特征向量來(lái)構(gòu)造用戶對(duì)資源的偏好矩陣，以余弦相似度(SIM)計(jì)算了資源相似性，該方法大大降低了計(jì)算的復(fù)雜度[3]71.針對(duì)標(biāo)簽無(wú)法準(zhǔn)確地反映用戶的喜好程度的問(wèn)題，郭彩云等利用標(biāo)簽、用戶評(píng)分值以及指數(shù)遺忘函數(shù)等評(píng)價(jià)指標(biāo)捕捉了用戶興趣的變化程度，得到了較好的推薦效果[4].對(duì)于標(biāo)簽的語(yǔ)義歧義問(wèn)題，李昊陽(yáng)等用標(biāo)簽生成主題標(biāo)簽簇，然后通過(guò)對(duì)目標(biāo)項(xiàng)目預(yù)測(cè)產(chǎn)生推薦目錄，以此提高了推薦精度[5]； G.Pitsilis等使用標(biāo)簽聚類(lèi)方法提高了推薦的準(zhǔn)確性，并降低了信息過(guò)載[6].針對(duì)標(biāo)簽推薦中忽略項(xiàng)目和標(biāo)簽間具有相互作用的問(wèn)題， Zheng Xiaolin等提出了一種可解釋性的項(xiàng)目標(biāo)簽聯(lián)合推薦方法，該方法不僅可提高推薦的準(zhǔn)確性，同時(shí)也可緩解冷啟動(dòng)的問(wèn)題[7].但在上述研究中，研究者均沒(méi)有綜合考慮評(píng)分?jǐn)?shù)據(jù)和標(biāo)簽數(shù)據(jù)的作用，仍存在標(biāo)簽數(shù)據(jù)稀少的問(wèn)題.基于此，本文在基于標(biāo)簽和協(xié)同過(guò)濾的個(gè)性化推薦算法的基礎(chǔ)上，提出一種基于標(biāo)簽和協(xié)同過(guò)濾的改進(jìn)推薦算法，并通過(guò)實(shí)驗(yàn)驗(yàn)證本文方法的有效性.

1 TCF算法介紹

1.1 基于標(biāo)簽的推薦算法

基于標(biāo)簽的協(xié)同過(guò)濾推薦算法(TCF)是在傳統(tǒng)的協(xié)同過(guò)濾算法中引入標(biāo)簽因子，即通過(guò)標(biāo)簽反映用戶偏好和項(xiàng)目特征的優(yōu)勢(shì)，以此改進(jìn)推薦質(zhì)量.在信息推薦時(shí)，標(biāo)簽通常被分成用戶-標(biāo)簽、項(xiàng)目-標(biāo)簽兩個(gè)部分來(lái)挖掘用戶的喜好，并依此構(gòu)造用戶興趣模型.

定義用戶集合U={u1,u2，…,ui,…,um}，m為用戶總數(shù)；標(biāo)簽集T={t1,t2，…,tk,…,tl}，l為標(biāo)簽總數(shù).項(xiàng)目集I={i1,i2,…,ij,…,in}，n是項(xiàng)目總數(shù).用戶-標(biāo)簽相關(guān)度(UTu,t)的計(jì)算公式[3]70為：

(1)

其中Nmt代表打標(biāo)簽t的用戶總數(shù)，Nu,t代表用戶u打標(biāo)簽t的次數(shù)，Nlu代表用戶u打標(biāo)簽的次數(shù)總和.

項(xiàng)目-標(biāo)簽相關(guān)度(ITi,t)的計(jì)算公式[3]70為：

(2)

其中Nnt代表被打標(biāo)簽t的項(xiàng)目總數(shù)，Ni,t代表項(xiàng)目i被打標(biāo)簽t的次數(shù)，Nli代表項(xiàng)目i被打標(biāo)簽的次數(shù)總和.

構(gòu)建用戶興趣模型時(shí)先分別以公式(1)和(2)建立相關(guān)矩陣UTm ×l、ITn ×l， 然后再利用ITn ×l的轉(zhuǎn)置矩陣TIl ×n計(jì)算用戶ui對(duì)已有用戶行為的項(xiàng)目ij的喜愛(ài)程度HPui,ij， 以此獲得用戶的歷史興趣矩陣HPm ×n.HPui,ij的計(jì)算公式[3]70為：

(3)

其中T(ij)是項(xiàng)目ij的標(biāo)簽集.

1.2 基于協(xié)同過(guò)濾的推薦算法

協(xié)同過(guò)濾推薦是指建立好用戶興趣模型后，以項(xiàng)目間的相似性預(yù)測(cè)用戶ui對(duì)未操作項(xiàng)目ii的偏愛(ài)程度(PPui,ii),并以此構(gòu)建矩陣PPm ×n.然后將PPm ×n的每行按照由高到低的順序排序，取前N個(gè)進(jìn)行推薦.協(xié)同過(guò)濾推薦的原理簡(jiǎn)單，因此目前被廣泛采用在推薦系統(tǒng)領(lǐng)域中[8-9].PPui,ii的計(jì)算公式[3]71為：

(4)

其中NotI(ui)是用戶ui未使用的項(xiàng)目集，I(ui)是用戶ui的歷史項(xiàng)目集,S1ii,ij是項(xiàng)目ii和ij的余弦相似度.

2 融入評(píng)分并擴(kuò)展標(biāo)簽的TCF改進(jìn)推薦算法

針對(duì)標(biāo)簽數(shù)據(jù)稀少的問(wèn)題，本文提出一種基于標(biāo)簽和協(xié)同過(guò)濾的改進(jìn)推薦算法(ITCF).首先利用項(xiàng)目-標(biāo)簽相關(guān)度構(gòu)造項(xiàng)目特征向量，并結(jié)合評(píng)分構(gòu)造用戶-標(biāo)簽關(guān)聯(lián)度，然后對(duì)用戶的偏好標(biāo)簽集進(jìn)行基于標(biāo)簽相似性和基于鄰居用戶偏好的擴(kuò)展.

2.1 項(xiàng)目特征向量的構(gòu)建

因?yàn)轫?xiàng)目-標(biāo)簽相關(guān)度能很好地代表項(xiàng)目的內(nèi)容特性，所以本文以項(xiàng)目-標(biāo)簽相關(guān)度ITij,tk表示項(xiàng)目ij的特征向量ij， 其定義為ij=(ITij,t1,ITij,t 2,…,ITij,tk,…,ITij,tl).該特征向量是構(gòu)建項(xiàng)目-標(biāo)簽相關(guān)矩陣ITn ×l和項(xiàng)目相似矩陣S1n ×n的計(jì)算依據(jù).構(gòu)造項(xiàng)目-標(biāo)簽相關(guān)矩陣和項(xiàng)目相似矩陣的算法步驟如下:

Step 1 統(tǒng)計(jì)每個(gè)項(xiàng)目ij的標(biāo)簽集T(ij)和標(biāo)簽tk標(biāo)記項(xiàng)目ij的次數(shù)nij,tk;

Step 2 記錄項(xiàng)目總數(shù)n和step 1中的標(biāo)簽集個(gè)數(shù)N(T(ij));

Step 3 采用TF-IDF計(jì)算項(xiàng)目-標(biāo)簽相關(guān)度ITij,tk， 建立ITn ×l矩陣;

Step 4 取ITn ×l矩陣的任意兩個(gè)行向量(即特征向量)進(jìn)行余弦相似度計(jì)算，得到項(xiàng)目相似程度S1ii,ij并建立矩陣S1n ×n.

2.2 結(jié)合評(píng)分的用戶標(biāo)簽關(guān)聯(lián)度的計(jì)算

以用戶ui打過(guò)標(biāo)簽的項(xiàng)目集I(ui)的評(píng)分集R(I(ui))表示用戶ui的特征向量ui,ui=(rui,i1,rui,i2,…,rui,ij,…,rui,in).因?yàn)橛脩?標(biāo)簽相關(guān)度的大小通常與用戶使用標(biāo)簽次數(shù)的多少和用戶對(duì)該標(biāo)簽項(xiàng)目的評(píng)分高低有關(guān)，所以本文利用公式(5)來(lái)表示用戶對(duì)標(biāo)簽的喜愛(ài)程度.

(5)

其中u是用戶集中的用戶，I(u)是用戶u打過(guò)標(biāo)簽和評(píng)分的項(xiàng)目集，T(u)是用戶項(xiàng)目集中含有的標(biāo)簽集，UTu,t是用戶-標(biāo)簽偏愛(ài)程度，ITi,t是采取TF-IDF計(jì)算的項(xiàng)目-標(biāo)簽相關(guān)度.

建立用戶-標(biāo)簽相關(guān)矩陣的算法步驟如下：

Step 1 統(tǒng)計(jì)每個(gè)用戶u的未使用項(xiàng)目集NotI(u)、 使用過(guò)的項(xiàng)目集I(u)及對(duì)應(yīng)的評(píng)分集R(I(u))， 并以R(I(u))表示用戶的特征向量u；

Step 2 通過(guò)余弦相似度計(jì)算用戶特征向量ui和uj的相似度S2ui,uj，并建立相似度矩陣S2m ×m；

Step 3 統(tǒng)計(jì)每個(gè)用戶u使用過(guò)的標(biāo)簽集T(u)及未使用的標(biāo)簽集NotT(u)；

Step 4 以公式(5)計(jì)算用戶-標(biāo)簽相關(guān)度UTu,t， 并以此建立UTm ×l矩陣.

2.3 用戶偏好標(biāo)簽集的擴(kuò)展

2.3.1基于近鄰用戶的標(biāo)簽擴(kuò)展 用戶在接受推薦時(shí)，因?qū)εd趣相同的用戶(即近鄰用戶)所推薦的項(xiàng)目更感興趣，所以可以根據(jù)用戶uj近鄰用戶的用戶-標(biāo)簽相關(guān)度計(jì)算uj對(duì)沒(méi)有歷史行為的標(biāo)簽t的相關(guān)度UT1uj,t.本文將UT1uj,t的計(jì)算公式定義為：

(6)

其中UT1uj,t是經(jīng)近鄰擴(kuò)充得到的用戶uj對(duì)標(biāo)簽t的偏愛(ài)程度，Nei(uj)是與用戶uj相似度最高的前K個(gè)用戶組成的近鄰集合，S2uj,ui是用戶與近鄰用戶間的相似度.

基于近鄰用戶的標(biāo)簽擴(kuò)展的算法步驟為:

Step 1 對(duì)S2m ×m的每行進(jìn)行相似度排序，并取前K個(gè)相似的用戶集Nei(uj)；

Step 2 統(tǒng)計(jì)鄰居用戶ui∈Nei(uj)使用過(guò)而用戶uj未使用過(guò)的標(biāo)簽集T(Nei(uj))；

Step 3 利用公式(6)計(jì)算基于鄰居用戶標(biāo)簽的擴(kuò)展用戶-標(biāo)簽相關(guān)度UT1uj,t的值，并構(gòu)建用戶-標(biāo)簽矩陣UT1m ×l.

2.3.2基于標(biāo)簽相似度的標(biāo)簽擴(kuò)展 本文根據(jù)標(biāo)簽相似度對(duì)用戶-標(biāo)簽矩陣進(jìn)行擴(kuò)充，即根據(jù)標(biāo)簽的相似度引入用戶對(duì)未有歷史行為的標(biāo)簽的喜愛(ài)程度(UT2u,tj)， 其計(jì)算公式定義如下：

(7)

其中UT2u,tj是以標(biāo)簽相似度擴(kuò)充的用戶u對(duì)標(biāo)簽tj的喜愛(ài)程度，NotT(u)是不在原標(biāo)簽集里的標(biāo)簽，S3tj,ti是不在原用戶標(biāo)簽集里的標(biāo)簽tj與原標(biāo)簽ti的相似度.

標(biāo)簽相似度的計(jì)算公式[10]為：

(8)

其中tj和ti表示兩個(gè)不同的標(biāo)簽，I(ti)表示標(biāo)簽ti的項(xiàng)目集，ni,ti表示對(duì)項(xiàng)目i標(biāo)注標(biāo)簽ti的次數(shù).

基于標(biāo)簽相似度的標(biāo)簽擴(kuò)展算法的步驟為:

Step 1 統(tǒng)計(jì)每個(gè)項(xiàng)目集I(ti)；

Step 2 利用式(8)計(jì)算標(biāo)簽間的相似程度S3tj,ti， 并建立S3l ×l矩陣；

Step 3 采用式(7)計(jì)算基于相似標(biāo)簽的擴(kuò)展用戶-標(biāo)簽相關(guān)度UT2u,tj的值,并構(gòu)建UT2m ×l矩陣.

2.3.3融入標(biāo)簽擴(kuò)展的用戶-標(biāo)簽相關(guān)矩陣 本文將融入標(biāo)簽擴(kuò)展的用戶-標(biāo)簽相關(guān)度的計(jì)算公式定義為：

(9)

其中，TE1(u)是用戶u基于近鄰用戶的標(biāo)簽擴(kuò)展所得到的前E個(gè)標(biāo)簽組成的標(biāo)簽集，TE2(u)是基于標(biāo)簽相似度的標(biāo)簽擴(kuò)展所得到的前E個(gè)標(biāo)簽組成的標(biāo)簽集，α是賦予UT1u,t的結(jié)合權(quán)重(用于UT1和UT2的信息融合).考慮到二者對(duì)預(yù)測(cè)用戶-標(biāo)簽相關(guān)度的影響同樣重要，因此本文將α取為0.5.由此得到的UT3u,t即為包含歷史行為標(biāo)簽和擴(kuò)展后標(biāo)簽的用戶-標(biāo)簽相關(guān)度，其相關(guān)度的矩陣為UT3m ×l.

2.4 ITCF過(guò)程及算法描述

輸入: 〈用戶，項(xiàng)目，標(biāo)簽，評(píng)分值〉，鄰居數(shù)K， 推薦個(gè)數(shù)N， 近鄰用戶、標(biāo)簽擴(kuò)展標(biāo)簽數(shù)E.

輸出: 輸入的用戶偏好的TopN推薦列表.

步驟1 按2.1中的步驟得到每個(gè)項(xiàng)目ij的標(biāo)簽集T(ij)、項(xiàng)目-標(biāo)簽關(guān)聯(lián)矩陣ITn ×l、項(xiàng)目相似程度矩陣S1n ×n.

步驟2 按2.2中的步驟得到每個(gè)用戶ui的歷史項(xiàng)目集I(ui)所未使用過(guò)的項(xiàng)目集NotI(ui)、用戶相似程度矩陣S2m ×m以及用戶-標(biāo)簽關(guān)聯(lián)矩陣UTm ×l.

步驟3 按2.3中的公式得到標(biāo)簽相似程度矩陣S3l ×l、綜合擴(kuò)展后的用戶-標(biāo)簽矩陣UT3m ×l， 并賦值給UTm ×l.

步驟4 對(duì)ii∈NotI(ui)，ij∈I(ui),tk∈T(ij)，根據(jù)S1n ×n、UTm ×l和ITn ×l的轉(zhuǎn)置矩陣TIl ×n，按照式(3)建立用戶興趣模型，按式(4)預(yù)測(cè)用戶ui對(duì)未操作項(xiàng)目ij的偏愛(ài)程度PPui,ij，并以此構(gòu)建矩陣PPm ×n.

步驟5 對(duì)PPm ×n的每行進(jìn)行排序，記錄所有行前N個(gè)標(biāo)簽的集合，由此得到推薦列表Rcmd(u).

3 實(shí)驗(yàn)結(jié)果與分析

3.1 實(shí)驗(yàn)數(shù)據(jù)與環(huán)境

實(shí)驗(yàn)采用MovieLens數(shù)據(jù)集(10 M)，實(shí)驗(yàn)環(huán)境為Intel 1.60 GHz CPU, 4.00 GB運(yùn)行內(nèi)存的PC機(jī).

為了更準(zhǔn)確地驗(yàn)證算法的有效性，實(shí)驗(yàn)選取標(biāo)簽數(shù)大于10的標(biāo)簽集，以排除冷門(mén)標(biāo)簽對(duì)用戶和項(xiàng)目的影響.另外，為分析算法在稠密數(shù)據(jù)集和稀疏數(shù)據(jù)集下的性能，本文選取標(biāo)簽數(shù)量為前98位的用戶和標(biāo)簽數(shù)在10～100的用戶集來(lái)進(jìn)行分析.數(shù)據(jù)集的分類(lèi)如表1所示.

表1 數(shù)據(jù)集分類(lèi)

3.2 評(píng)價(jià)標(biāo)準(zhǔn)

本文采用準(zhǔn)確率(Recall)和召回率(Precision)對(duì)推薦算法進(jìn)行性能評(píng)測(cè)，其計(jì)算公式如下：

(10)

(11)

其中U表示用戶集，|Rcmd(u)|表示推薦集中的項(xiàng)目個(gè)數(shù)，|Test(u)|表示測(cè)試集中的項(xiàng)目個(gè)數(shù)，|Rcmd(u)∩Test(u)|表示兩個(gè)集合的交集個(gè)數(shù).

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

根據(jù)文獻(xiàn)[11]，測(cè)試每組樣例集時(shí)，鄰居用戶數(shù)K取5， 擴(kuò)展標(biāo)簽數(shù)E取40.推薦個(gè)數(shù)N的值分別取5、10、15、20、25、30、35、40和45進(jìn)行測(cè)試，并與文獻(xiàn)[2]和[3]中的兩種TCF算法進(jìn)行比較，實(shí)驗(yàn)結(jié)果見(jiàn)表2 —表5和圖1 —圖4.

表2 不同算法對(duì)data 1的準(zhǔn)確率

表3 不同算法對(duì)data 1的召回率

表4 不同算法對(duì)data 2的準(zhǔn)確率

表5 不同算法對(duì)data 2的召回率

圖1 不同算法對(duì)data 1的準(zhǔn)確率

圖2 不同算法對(duì)data 1的召回率

圖3 不同算法對(duì)data 2的準(zhǔn)確率

圖4 不同算法對(duì)data 2的召回率

由圖1和圖2可以看出，在稠密的數(shù)據(jù)集中， ITCF的平均準(zhǔn)確率和平均召回率比文獻(xiàn)[2]和文獻(xiàn)[3]的平均準(zhǔn)確率和平均召回率分別提升約2.0%和1.7%.由圖3和圖4可以看出，在稀疏的數(shù)據(jù)集中，當(dāng)5≤N≤20時(shí)， ITCF的準(zhǔn)確率和召回率均高于其他兩種TCF算法，其中準(zhǔn)確率約提升0.2%，召回率約提升0.8%；N>20時(shí)， ITCF算法的準(zhǔn)確率和召回率均略低于文獻(xiàn)[3]的TCF算法，但與文獻(xiàn)[2]的算法相近.其原因是當(dāng)N>20時(shí)，數(shù)據(jù)集中的很多項(xiàng)目已不存在相似標(biāo)簽，因此導(dǎo)致ITCF的準(zhǔn)確率和召回率降低.

Data 1的準(zhǔn)確率和召回率比data 2的準(zhǔn)確率、召回率提升得更高，其原因是由于data 1利用用戶相似度和標(biāo)簽相似度擴(kuò)充了用戶-標(biāo)簽矩陣，因此在一定程度上緩解了數(shù)據(jù)稀少問(wèn)題，進(jìn)而提高了準(zhǔn)確率和召回率.而data 2因用戶歷史行為數(shù)據(jù)過(guò)于稀少、訓(xùn)練樣本不足，因此導(dǎo)致標(biāo)簽相似度普遍較低，進(jìn)而使得其準(zhǔn)確率和召回率提升幅度低于data 1.

4 結(jié)論

研究表明，本文提出的基于標(biāo)簽和協(xié)同過(guò)濾的改進(jìn)推薦算法(ITCF)與文獻(xiàn)[2 - 3]相比，其準(zhǔn)確率和召回率均有所提高，因此本文方法對(duì)因標(biāo)簽過(guò)少而影響推薦質(zhì)量的問(wèn)題具有一定程度地緩解作用.本文在研究中未考慮用戶興趣的動(dòng)態(tài)變化情況，在推薦實(shí)時(shí)性方面有所欠缺，因此我們?cè)诮窈蟮难芯恐袑⒁霑r(shí)間因子，建立隨時(shí)間變化的動(dòng)態(tài)用戶興趣模型，以更好地完善本文模型.