基于約束推薦的網(wǎng)絡(luò)可視化分析

張超杰，吳果林,2

(1.桂林航天工業(yè)學(xué)院 理學(xué)院，廣西 桂林 541004;2.桂林航天工業(yè)學(xué)院 廣西航空物流研究中心，廣西 桂林 541004)

0 引 言

隨著網(wǎng)絡(luò)購(gòu)物的興起，如何在成千上萬(wàn)的商品中給出用戶需求的產(chǎn)品推薦列表,就成了亟待解決的問(wèn)題?；谥R(shí)的推薦系統(tǒng)[1-3]能夠根據(jù)用戶的明確需求、產(chǎn)品的領(lǐng)域知識(shí)、通過(guò)推理為用戶給出推薦。由于不依賴于用戶評(píng)分等關(guān)于用戶偏好的歷史數(shù)據(jù)，故不存在冷啟動(dòng)問(wèn)題。在已應(yīng)用的案例中[4-6]，基于知識(shí)的推薦技術(shù)表現(xiàn)出優(yōu)異的性能，已成為推薦系統(tǒng)研究的一個(gè)重要分支和熱點(diǎn)。一般地，基于知識(shí)的推薦系統(tǒng)有兩種類型[1]：基于約束的推薦[2]和基于案例的推薦[3]。雖然基于知識(shí)的推薦技術(shù)不依賴用戶的評(píng)分，但是從復(fù)雜網(wǎng)絡(luò)的觀點(diǎn)來(lái)看，以往的推薦記錄形成一個(gè)用戶需求與用戶意向物品的二部圖網(wǎng)[7]。顯然這個(gè)二部圖網(wǎng)絡(luò)隱藏了用戶需求與意向物品的內(nèi)在聯(lián)系，也包含了用戶之間、物品之間的深層聯(lián)系。為了能更好地分析這些深層聯(lián)系，將這些信息用于推薦系統(tǒng)，提高推薦技術(shù)的性能，文中對(duì)基于約束的推薦過(guò)程中形成的用戶需求與意向物品的二部圖網(wǎng)絡(luò)進(jìn)行了可視化分析，主要包括以下幾方面的內(nèi)容：二部圖結(jié)構(gòu)可視化，用戶、物品節(jié)點(diǎn)的度分布，單模網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)可視化等。

1 基于約束推薦的網(wǎng)絡(luò)整理與分析

基于約束推薦網(wǎng)絡(luò)對(duì)優(yōu)質(zhì)雪茄領(lǐng)域推薦的數(shù)據(jù)集進(jìn)行分析研究,以期找到用戶和物品之間的一些深層聯(lián)系。該數(shù)據(jù)集是由瑞士一個(gè)在線雪茄銷售商店于2005年10月至2009年5月收集，并由Zanker等[8]整理后應(yīng)用于約束推薦研究的案例數(shù)據(jù)集，包含了535個(gè)顯示用戶偏好與用戶意向物品的會(huì)話。表1顯示了其中3個(gè)用戶會(huì)話的數(shù)據(jù)。

表1 用戶偏好與意向物品數(shù)據(jù)(部分)

表1中，用戶變量列表示用戶偏好提問(wèn)，值列表示用戶偏好回答，其中用戶變量UM010所對(duì)應(yīng)的值表示用戶意向物品回答，關(guān)于每個(gè)用戶變量的意義以及用戶變量與物品屬性之間的約束關(guān)系等其他詳細(xì)信息可參考文獻(xiàn)[9]。這些數(shù)據(jù)堆砌在一起時(shí)，如果僅用數(shù)據(jù)表格或文字的形式來(lái)表示，則理解的內(nèi)容非常有限。易見(jiàn)，上面數(shù)據(jù)集包含了用戶偏好與意向物品的二元關(guān)系，為了更直觀、更清晰地描述用戶偏好與意向物品、用戶之間、物品之間的聯(lián)系，因而將該數(shù)據(jù)集提煉成一個(gè)關(guān)于用戶偏好與意向物品的二部圖網(wǎng)絡(luò)。為方便計(jì)，可以將一個(gè)用戶的所有偏好看成一個(gè)節(jié)點(diǎn)(即每個(gè)用戶看成一個(gè)節(jié)點(diǎn))，每個(gè)物品看成一個(gè)節(jié)點(diǎn)，這樣得到一個(gè)由535個(gè)用戶偏好節(jié)點(diǎn)、141個(gè)物品節(jié)點(diǎn)以及1 422條邊構(gòu)成的二部圖網(wǎng)絡(luò)，如圖1所示。

圖1 用戶偏好與意向物品網(wǎng)絡(luò)

圖1中黑色表示用戶節(jié)點(diǎn)，灰色表示物品節(jié)點(diǎn)，節(jié)點(diǎn)的大小由節(jié)點(diǎn)的度來(lái)決定。不難發(fā)現(xiàn)，圖中除了一個(gè)物品節(jié)點(diǎn)與一個(gè)用戶節(jié)點(diǎn)單獨(dú)相連外，其余的節(jié)點(diǎn)都相互鏈接且組成一個(gè)連通圖。另外，從圖1也可以看出，多數(shù)用戶選擇一、兩個(gè)物品，少數(shù)用戶選擇多個(gè)物品。也即大部分用戶節(jié)點(diǎn)只有少數(shù)幾個(gè)鏈接，某些用戶節(jié)點(diǎn)卻擁有與物品節(jié)點(diǎn)的大量鏈接，在度分布上具有冪律形式。相對(duì)而言，物品節(jié)點(diǎn)也有度數(shù)較大的集散節(jié)點(diǎn)，但是度數(shù)較少的節(jié)點(diǎn)也不是很多，分布相對(duì)比較平均，冪律分布不明顯。圖2顯示了用戶與物品節(jié)點(diǎn)的度分布。

圖2 用戶與物品節(jié)點(diǎn)的度分布

圖2中點(diǎn)劃線表示用戶節(jié)點(diǎn)，虛線表示物品節(jié)點(diǎn)，實(shí)線表示BA無(wú)標(biāo)度網(wǎng)絡(luò)[10]。圖中顯示的是500個(gè)節(jié)點(diǎn)，連邊為1的BA無(wú)標(biāo)度網(wǎng)絡(luò)，記為BA(500, 1)。BA(500, 1)模型有兩個(gè)重要特性：(1)每次引入一個(gè)新的節(jié)點(diǎn)，并且連到1個(gè)已存在的節(jié)點(diǎn)上；(2)一個(gè)新節(jié)點(diǎn)與一個(gè)已經(jīng)存在的節(jié)點(diǎn)vi相連接的概率pi與節(jié)點(diǎn)vi的度ki滿足如下關(guān)系：

易見(jiàn)，用戶節(jié)點(diǎn)的度分布近似于BA(500, 1)的度分布。如果將每次用戶偏好調(diào)查看成引入一個(gè)新的節(jié)點(diǎn)，就能很好地解釋度分布近似于BA(500, 1)的度分布。這是因?yàn)?，多?shù)用戶選擇一、兩個(gè)物品類似于BA(500, 1)模型的特性(1)；BA(500, 1)模型隨著節(jié)點(diǎn)的增加，大度的節(jié)點(diǎn)也開(kāi)始少量出現(xiàn)，而在基于約束推薦的網(wǎng)絡(luò)中，也有少量用戶選擇多個(gè)意向物品，這與BA(500, 1)模型的第二個(gè)特性相吻合。從物品節(jié)點(diǎn)的度分布來(lái)看，盡管多數(shù)用戶選擇一、兩個(gè)物品，但物品節(jié)點(diǎn)的度為1、2的概率不是最高的，度為3的概率最大，度為4～9的概率都要大于度數(shù)為1、2的節(jié)點(diǎn)。此外，物品節(jié)點(diǎn)的度分布不像用戶節(jié)點(diǎn)的度分布那樣直線下降，而是緩慢下降，且大度節(jié)點(diǎn)的數(shù)量也比用戶節(jié)點(diǎn)的數(shù)量要多，這體現(xiàn)了一些物品獲得用戶的普遍愛(ài)好。

2 基于約束推薦的網(wǎng)絡(luò)社團(tuán)可視化

從上面物品節(jié)點(diǎn)的度分布結(jié)構(gòu)可以看出，一些物品被多數(shù)用戶所喜好，一些物品被部分用戶所喜好，而另一些物品被少數(shù)用戶所喜好，物品節(jié)點(diǎn)存在明顯的社團(tuán)屬性。因此可以對(duì)物品節(jié)點(diǎn)進(jìn)行社團(tuán)可視化，觀察它們的社團(tuán)結(jié)構(gòu)。然而，物品節(jié)點(diǎn)處于一個(gè)二部圖網(wǎng)絡(luò)，對(duì)物品節(jié)點(diǎn)進(jìn)行社團(tuán)劃分不像單模網(wǎng)絡(luò)那樣可以直接應(yīng)用現(xiàn)有的社團(tuán)分割算法。當(dāng)前，針對(duì)二部圖網(wǎng)絡(luò)社團(tuán)劃分有兩種思路：一種是直接作用在二部圖網(wǎng)絡(luò)上，設(shè)計(jì)專門針對(duì)二部圖網(wǎng)絡(luò)的社團(tuán)分割算法或者在原有針對(duì)單模網(wǎng)絡(luò)的算法上進(jìn)行修改使之能夠用于二部圖網(wǎng)絡(luò)的算法，諸如Barber基于模塊的算法[11]、Barber與Clark的LPAb算法[12]以及Aikin與Francis的統(tǒng)計(jì)模型方法[13]；另一種是將二部圖網(wǎng)絡(luò)映射成單模網(wǎng)絡(luò)，利用已有的單模網(wǎng)絡(luò)的社團(tuán)探測(cè)算法進(jìn)行社團(tuán)劃分。在已知的單模網(wǎng)絡(luò)的社團(tuán)探測(cè)算法中，比較優(yōu)秀的算法有Blondel等的Louvain算法[14]、Rosvall與Bergstrom的Infomap算法[15]以及Newman的基于模塊的算法[16-17]。鑒于Guimera發(fā)現(xiàn)在二部圖網(wǎng)絡(luò)其中一類節(jié)點(diǎn)社團(tuán)探測(cè)時(shí)，無(wú)論是先映射到該類節(jié)點(diǎn)后模塊最大化社團(tuán)劃分，還是先二部圖網(wǎng)絡(luò)模塊最大化社團(tuán)劃分再映射到這類節(jié)點(diǎn)上，兩者之間沒(méi)有差別[18]。因此，文中采用先將二部圖網(wǎng)絡(luò)映射到物品節(jié)點(diǎn)上，形成一個(gè)關(guān)于物品節(jié)點(diǎn)的單模網(wǎng)絡(luò)，然后再利用單模網(wǎng)絡(luò)劃分社團(tuán)的方式來(lái)劃分物品節(jié)點(diǎn)的社團(tuán)。

考慮一個(gè)基于約束的推薦網(wǎng)絡(luò)G=(U∪I,E)，其中U為用戶節(jié)點(diǎn)，I為物品節(jié)點(diǎn)，E為兩者之間的連邊。GI=(I,EI)為網(wǎng)絡(luò)G在物品節(jié)點(diǎn)上的映射，GI中的邊由網(wǎng)絡(luò)G確定，當(dāng)且僅當(dāng)I的節(jié)點(diǎn)vi，vj在U中至少有一個(gè)共同鄰居節(jié)點(diǎn)時(shí)，則節(jié)點(diǎn)vi，vj之間存在一條邊。映射有權(quán)重映射與非權(quán)重映射兩種。在基于約束的推薦網(wǎng)絡(luò)G中，I中的節(jié)點(diǎn)vi，vj有多個(gè)共同鄰居節(jié)點(diǎn)表示有多個(gè)用戶都喜好物品vi，vj，也即權(quán)重映射更能清楚地表達(dá)節(jié)點(diǎn)之間鏈接的信息[19]。因此文中選擇權(quán)重映射作為圖G到圖GI的映射。設(shè)f為圖G到圖GI的映射，圖GI的邊(vi,vj)的權(quán)重wij定義如下：

wij=|n(vi)∩n(vj)|，i≠j

其中，n(vi)表示節(jié)點(diǎn)vi的鄰居節(jié)點(diǎn)。

利用上述映射方法，將基于約束的優(yōu)質(zhì)雪茄推薦網(wǎng)絡(luò)映射到物品節(jié)點(diǎn)上，得到一個(gè)由141個(gè)物品節(jié)點(diǎn)以及2 300條邊構(gòu)成的單模網(wǎng)絡(luò)，并測(cè)得網(wǎng)絡(luò)的模塊度為0.321，是一個(gè)具有明顯社團(tuán)結(jié)構(gòu)的網(wǎng)絡(luò)。應(yīng)用Louvain算法[14]，計(jì)算出物品單模網(wǎng)絡(luò)可分成7個(gè)社團(tuán)，每個(gè)社團(tuán)的節(jié)點(diǎn)數(shù)量分布如圖3所示。

圖3 物品網(wǎng)絡(luò)的社團(tuán)數(shù)量分布

從圖3可知，有1個(gè)社團(tuán)只有1個(gè)物品節(jié)點(diǎn)，這與二部圖網(wǎng)絡(luò)中只有1個(gè)物品和1個(gè)用戶組成的連通子集相對(duì)應(yīng)，可見(jiàn)Louvain算法能夠很好地區(qū)分連通分支。除此之外，在其他的社團(tuán)中，最大的社團(tuán)含有34個(gè)物品節(jié)點(diǎn)，次大的社團(tuán)有31個(gè)節(jié)點(diǎn)，次小的社團(tuán)也有12個(gè)節(jié)點(diǎn)。整個(gè)網(wǎng)絡(luò)除了一個(gè)只含單個(gè)節(jié)點(diǎn)的社團(tuán)外，聚集程度還是很大的，表現(xiàn)了大社團(tuán)的特征。圖4可視化了社團(tuán)分類的結(jié)果。由圖4不難看出，權(quán)重較大的邊所對(duì)應(yīng)的節(jié)點(diǎn)大都?xì)w屬于同一類，這與定義的節(jié)點(diǎn)間權(quán)重越大，兩個(gè)節(jié)點(diǎn)包含更豐富的關(guān)聯(lián)信息一致。

圖4 物品網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)

3 結(jié)束語(yǔ)

基于約束的推薦系統(tǒng)能夠根據(jù)用戶指定的需求進(jìn)行個(gè)性化的推薦，在Felfernig和Zanker等[2-6,8-9]許多學(xué)者的努力下，基于約束的推薦已成為基于知識(shí)的推薦系統(tǒng)一個(gè)主要的研究方向，并成為一個(gè)研究熱點(diǎn)。盡管基于約束的推薦不依賴于用戶評(píng)分等關(guān)于用戶偏好的歷史數(shù)據(jù)，但以往的推薦記錄形成的用戶需求與用戶意向物品的二部圖網(wǎng)絡(luò)顯然包含了許多對(duì)推薦有價(jià)值的信息。且混合的推薦方法也是當(dāng)前推薦技術(shù)發(fā)展的一種趨勢(shì)[1,20-21]。通過(guò)可視化客戶購(gòu)物的歷史記錄形成的二部圖網(wǎng)絡(luò)，以期發(fā)現(xiàn)對(duì)推薦有價(jià)值的信息，為開(kāi)發(fā)或構(gòu)造混合的推薦算法提供直觀的幫助。分析某在線雪茄銷售記錄表明：在基于用戶需求與用戶意向物品的二部圖網(wǎng)絡(luò)中，用戶節(jié)點(diǎn)的度表現(xiàn)為類似BA(500, 1)的分布；物品節(jié)點(diǎn)里含有許多大度的節(jié)點(diǎn)，呈現(xiàn)出集結(jié)性、社團(tuán)性特點(diǎn)；對(duì)物品節(jié)點(diǎn)的社團(tuán)分析顯示，物品節(jié)點(diǎn)可以分為7個(gè)網(wǎng)絡(luò)社團(tuán)，這些社團(tuán)具有很強(qiáng)的層次性。

社團(tuán)可視化表明，社團(tuán)中的節(jié)點(diǎn)通過(guò)共同用戶的多少聚集在一起，因此對(duì)于給定物品，可以根據(jù)物品社團(tuán)內(nèi)給定節(jié)點(diǎn)間的度進(jìn)行排序，然后進(jìn)行相應(yīng)的推薦，將此推薦方法加入到基于約束的推薦方法中，構(gòu)造一個(gè)混合的推薦算法，增加推薦的精確度，為推薦算法的設(shè)計(jì)提供幫助。