張超杰，吳果林,2

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

0 引 言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖4 物品網(wǎng)絡的社團結構

3 結束語

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

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