李?yuàn)^華 趙潤(rùn)林

(運(yùn)城學(xué)院數(shù)學(xué)與信息技術(shù)學(xué)院 山西 運(yùn)城 044000)

0 引 言

個(gè)性化推薦技術(shù)已經(jīng)在電子商務(wù)領(lǐng)域獲得了較廣泛的應(yīng)用[1]。在推薦系統(tǒng)中，推薦算法是推薦系統(tǒng)的核心部分，協(xié)同過(guò)濾算法作為經(jīng)典的推薦算法在推薦系統(tǒng)中獲得了較成功的應(yīng)用[2-3]。但是協(xié)同過(guò)濾算法自身存在一些問(wèn)題，例如：在數(shù)據(jù)稀疏的情況下，其推薦效果較差，且在推薦過(guò)程中并沒(méi)有考慮實(shí)體間的一些附加有用信息[2]。有些學(xué)者提出了基于鏈路預(yù)測(cè)的個(gè)性化推薦算法，這些算法主要是利用顧客商品二分網(wǎng)絡(luò)中顧客與商品之間的關(guān)聯(lián)信息來(lái)彌補(bǔ)數(shù)據(jù)稀疏的問(wèn)題，通過(guò)使用二分網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)信息來(lái)改善算法的推薦質(zhì)量。然而，這些算法在推薦過(guò)程中僅僅利用了二分網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)信息，并沒(méi)有考慮商品的領(lǐng)域知識(shí)。文獻(xiàn)[3]提出采用顧客商品二分網(wǎng)絡(luò)中商品的領(lǐng)域信息進(jìn)行推薦，能夠進(jìn)一步改善推薦的精度和效果。

本文結(jié)合顧客商品二分網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)和網(wǎng)絡(luò)中節(jié)點(diǎn)的相關(guān)屬性，提出一種基于領(lǐng)域知識(shí)的鏈路預(yù)測(cè)方法。在該方法中，推薦給顧客的不同商品有不同的權(quán)重，權(quán)重的大小由與該商品相關(guān)的領(lǐng)域知識(shí)來(lái)決定，權(quán)重越大的商品被認(rèn)為是越符合顧客需求的，越值得推薦給顧客。

1 鏈路預(yù)測(cè)算法

1.1 典型的鏈路預(yù)測(cè)算法

鏈接預(yù)測(cè)(Link prediction)是指如何通過(guò)已知的邊(即網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu))或者節(jié)點(diǎn)的特征等信息來(lái)預(yù)測(cè)評(píng)估社會(huì)網(wǎng)絡(luò)中節(jié)點(diǎn)之間未知鏈接(包括已存在而丟失的鏈接、未來(lái)的鏈接)存在的可能性[4-5]。幾種典型的鏈路預(yù)測(cè)算法介紹如下：

1) 共同鄰居方法(Common Neighbors，CN)：該方法是基于待預(yù)測(cè)節(jié)點(diǎn)對(duì)的共同鄰居節(jié)點(diǎn)的數(shù)量來(lái)對(duì)社會(huì)網(wǎng)絡(luò)進(jìn)行鏈接預(yù)測(cè)[6-9]。在這里，假設(shè)Γ(x)代表節(jié)點(diǎn)x的共同鄰居的集合[10-11]。一般來(lái)說(shuō)，如果待預(yù)測(cè)節(jié)點(diǎn)對(duì)(x,y)具有的共同鄰居數(shù)量越多，那么就認(rèn)為節(jié)點(diǎn)x和節(jié)點(diǎn)y之間存在連邊的可能性越大。因此，共同鄰居方法的節(jié)點(diǎn)相似性度量指標(biāo)定義如下：

(1)

2) Adamic Adar方法(簡(jiǎn)稱AA)：該方法是基于待預(yù)測(cè)節(jié)點(diǎn)對(duì)的共同鄰居集合來(lái)進(jìn)行鏈接預(yù)測(cè)的。針對(duì)待預(yù)測(cè)節(jié)點(diǎn)對(duì)的每個(gè)共同鄰居節(jié)點(diǎn)在鏈接預(yù)測(cè)中的作用不同，它賦予每個(gè)共同鄰居一個(gè)權(quán)值，該權(quán)值是對(duì)應(yīng)共同鄰居節(jié)點(diǎn)度值對(duì)數(shù)的倒數(shù)[12-13]。如果一個(gè)節(jié)點(diǎn)的度值比其他節(jié)點(diǎn)小，那么該節(jié)點(diǎn)在鏈接預(yù)測(cè)中的作用比其他節(jié)點(diǎn)更重要[4-5，14-15]。該方法的節(jié)點(diǎn)相似性度量指標(biāo)定義如下：

(2)

式中：Γ(x)、Γ(y)分別代表節(jié)點(diǎn)x、y的共同鄰居的集合；Kz表示節(jié)點(diǎn)z的度。

3) Jaccard Index方法(簡(jiǎn)稱JA)：該方法由Jaccard提出[10]，是信息檢索領(lǐng)域被廣泛應(yīng)用的一種相似度度量方法[16-17]。它的主要思想是：給定一個(gè)節(jié)點(diǎn)對(duì)(x,y)，在節(jié)點(diǎn)x、y的鄰居并集中，將隨機(jī)選擇一個(gè)鄰居節(jié)點(diǎn)是該節(jié)點(diǎn)對(duì)共同鄰居的概率作為節(jié)點(diǎn)相似度的度量指標(biāo)。該方法定義如下：

(3)

一般來(lái)說(shuō)，評(píng)估預(yù)測(cè)算法精確度的主要有兩個(gè)指標(biāo)：AUC和Precision。AUC是從整體上來(lái)考慮算法的預(yù)測(cè)精度；Precision是從局部層面來(lái)考慮算法的預(yù)測(cè)精度[18]。

1.2 顧客商品二分網(wǎng)絡(luò)

復(fù)雜系統(tǒng)在現(xiàn)實(shí)生活中普遍存在，復(fù)雜網(wǎng)絡(luò)是表示和研究復(fù)雜系統(tǒng)的有效方法之一。在復(fù)雜網(wǎng)絡(luò)中，節(jié)點(diǎn)表示復(fù)雜系統(tǒng)中的個(gè)體，邊表示個(gè)體之間存在的關(guān)系[5，16]。二分網(wǎng)絡(luò)是復(fù)雜網(wǎng)絡(luò)的一種特殊形式，在該網(wǎng)絡(luò)中節(jié)點(diǎn)被分成不同的兩類(lèi)節(jié)點(diǎn)，同類(lèi)節(jié)點(diǎn)之間不存在關(guān)系，只有在不同類(lèi)節(jié)點(diǎn)之間才存在關(guān)系[19]。在電子商務(wù)領(lǐng)域，顧客購(gòu)買(mǎi)商品構(gòu)成的網(wǎng)絡(luò)就是二分網(wǎng)絡(luò)，假設(shè)P={p1,p2,…,pn}表示顧客商品網(wǎng)絡(luò)中的商品集合，C={c1,c2,…,cm}表示顧客商品網(wǎng)絡(luò)中的顧客集合，因此，能夠獲得一個(gè)隸屬關(guān)系矩陣A=(aij)n×m，其中aij表示網(wǎng)絡(luò)中節(jié)點(diǎn)i代表的特定對(duì)象(即商品i)與節(jié)點(diǎn)j代表的特定對(duì)象(即顧客j)的隸屬(即購(gòu)買(mǎi))關(guān)系值，也就是說(shuō)，在該矩陣中如果顧客ci購(gòu)買(mǎi)了商品pj，那么aij賦值為1，否則aij賦值為0。在顧客商品二分網(wǎng)絡(luò)中，如何選擇顧客沒(méi)有購(gòu)買(mǎi)過(guò)的合適商品推薦給每個(gè)顧客是個(gè)性化推薦中很關(guān)鍵的問(wèn)題，傳統(tǒng)的協(xié)同過(guò)濾算法雖然有時(shí)能夠取得較好的推薦效果，但是該算法僅僅考慮網(wǎng)絡(luò)節(jié)點(diǎn)(顧客/商品)的直接鄰居，具有一定的局限性[20]。圖1為一個(gè)顧客商品二分網(wǎng)絡(luò)，在該網(wǎng)絡(luò)中平行四邊形代表顧客，橢圓代表商品，實(shí)線表示顧客已購(gòu)買(mǎi)商品，虛線表示將來(lái)顧客可能購(gòu)買(mǎi)的商品(即個(gè)性化推薦)。

圖1 顧客商品二分網(wǎng)絡(luò)

2 方法設(shè)計(jì)與實(shí)現(xiàn)

2.1 基于領(lǐng)域知識(shí)的鏈路預(yù)測(cè)方法

鏈路預(yù)測(cè)實(shí)際上是根據(jù)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)的特點(diǎn)來(lái)推斷未來(lái)有可能出現(xiàn)的關(guān)系。在生物研究領(lǐng)域，研究者根據(jù)共有鄰居的數(shù)量來(lái)計(jì)算蛋白質(zhì)對(duì)之間的拓?fù)湎嗨贫?，以此?lái)進(jìn)行預(yù)測(cè)和推薦。文獻(xiàn)[3]利用二分網(wǎng)絡(luò)的拓?fù)涮攸c(diǎn)，在電子商務(wù)中的商品推薦方面做了一定的研究。在此啟發(fā)下，根據(jù)顧客商品二分網(wǎng)絡(luò)的拓?fù)涮攸c(diǎn)，把鏈路預(yù)測(cè)和領(lǐng)域知識(shí)相融合，描述了一種顧客商品推薦方法。假設(shè)顧客商品二分網(wǎng)絡(luò)G，通過(guò)相似度分值來(lái)計(jì)算未來(lái)顧客c購(gòu)買(mǎi)商品P的連邊的可能性大小，以此作為推薦的依據(jù)。對(duì)于節(jié)點(diǎn)x，Γ(x)代表節(jié)點(diǎn)x的共同鄰居的集合，那么節(jié)點(diǎn)x的鄰居的鄰居集合定義如下：

?！?x)=Γc″∈Γ(x)(c″)

(4)

對(duì)式(1)作修改后，連邊可能性的度量標(biāo)準(zhǔn)如下：

CP_CN(p,c)=|Γ(p)∩Γ′(c)|

(5)

同理，對(duì)式(3)作修改后，可獲得連邊可能性的度量標(biāo)準(zhǔn)如下：

(6)

在文獻(xiàn)[3]的啟發(fā)下，根據(jù)實(shí)際顧客商品網(wǎng)絡(luò)中商品的分類(lèi)，構(gòu)建商品的分類(lèi)層次結(jié)構(gòu)樹(shù)，在此分類(lèi)結(jié)構(gòu)樹(shù)的基礎(chǔ)上，構(gòu)建商品之間的語(yǔ)義相似度的度量標(biāo)準(zhǔn)，如下：

(7)

式中:dis(pi)表示商品分類(lèi)樹(shù)中商品pi與根節(jié)點(diǎn)的路徑長(zhǎng)度；set(P)表示商品pi和商品pj共同的祖先節(jié)點(diǎn)的集合；n表示set(P)中祖先節(jié)點(diǎn)的個(gè)數(shù)。

把式(7)和式(5)、式(6)相融合就得到在顧客商品二分網(wǎng)絡(luò)中基于鏈路預(yù)測(cè)和領(lǐng)域知識(shí)的推薦評(píng)估指標(biāo)，如下：

(8)

(9)

式中：pi表示顧客c已經(jīng)購(gòu)買(mǎi)的商品；CHB(c)表示顧客c已經(jīng)購(gòu)買(mǎi)商品的集合；m表示顧客已經(jīng)購(gòu)買(mǎi)商品的數(shù)量(即CHB(c)集合的大小)。

2.2 實(shí)驗(yàn)分析

根據(jù)2.1節(jié)中描述的顧客商品推薦方法，在實(shí)際的超市購(gòu)買(mǎi)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，該數(shù)據(jù)集包含了近1年3 542名顧客的購(gòu)買(mǎi)信息，其中涉及到的商品有487種，交易次數(shù)達(dá)到36 873次。在本實(shí)驗(yàn)中，用鏈路預(yù)測(cè)中的AUC作為推薦結(jié)果的度量標(biāo)準(zhǔn)，把該方法中的分值最高的前20種商品推薦給顧客，分別把數(shù)據(jù)集的70%、80%作為訓(xùn)練集，剩余的作為測(cè)試集，實(shí)驗(yàn)結(jié)果如表1和圖2所示。

表1 顧客商品二分網(wǎng)絡(luò)中不同推薦方法的推薦精度比較

圖2 顧客商品網(wǎng)絡(luò)中不同推薦方法的精度比較

從表1和圖2的實(shí)驗(yàn)結(jié)果來(lái)看，在顧客商品二分網(wǎng)絡(luò)中采用鏈路預(yù)測(cè)和領(lǐng)域知識(shí)相融合的推薦方法能夠取得較理想的推薦效果。

3 結(jié) 語(yǔ)

基于電子商務(wù)二分網(wǎng)絡(luò)個(gè)性化推薦精度低的現(xiàn)狀，本文描述一種基于領(lǐng)域知識(shí)的鏈路預(yù)測(cè)方法，并在真實(shí)的超市顧客商品數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)。結(jié)果表明，該方法推薦效果較好，能夠在一定程度上提高個(gè)性化推薦的精度，具有一定的實(shí)用價(jià)值。