呂 巍，鄔春學(xué)，3，張明西，鐘 聃

（1.上海理工大學(xué) 光電信息與計(jì)算機(jī)工程學(xué)院，上海200093；2.上海理工大學(xué) 出版印刷與藝術(shù)設(shè)計(jì)學(xué)院，上海200093；3.上海理工大學(xué) 新聞出版總署重點(diǎn)實(shí)驗(yàn)室，上海200093；4.中國民用航空西北地區(qū)空中交通管理局 計(jì)保中心通信室，陜西 西安710075）

0 引 言

傳統(tǒng)基于局部結(jié)構(gòu)的相似性搜索方法依據(jù)實(shí)體之間的直接鏈接關(guān)系計(jì)算實(shí)體相似性，沒有考慮間接鏈接關(guān)系，容易忽略一些潛在相似的結(jié)果?；谌志W(wǎng)絡(luò)的相似性計(jì)算方法［1－4］考慮實(shí)體之間的間接鏈接關(guān)系，返回結(jié)果比較全面，具有較高的精確度，但卻因?yàn)闀r(shí)間和存儲(chǔ)開銷巨大無法適應(yīng)大規(guī)模網(wǎng)絡(luò)。其中，P－Rank［5］算法在相似性計(jì)算時(shí)充分考慮入鏈接和出鏈接信息，具有較高的精確度，能夠用于網(wǎng)絡(luò)書店的相似性搜索，但時(shí)間和存儲(chǔ)開銷同樣很高。為提高網(wǎng)絡(luò)書店相似性搜索效率，降低時(shí)間和存儲(chǔ)開銷，提出基于P－Rank的相似性搜索的優(yōu)化方法ProductP－Rank，預(yù)計(jì)算一步相似性矩陣，在線計(jì)算兩步相似性矩陣，實(shí)驗(yàn)驗(yàn)證了該方法是一種準(zhǔn)確有效的相似性搜索算法。

1 相關(guān)工作

目前，有許多相似性搜索算法被提出并被廣泛應(yīng)用［6］。早期的相似性計(jì)算模型都是直接鄰居模型，沒有充分利用網(wǎng)絡(luò)模型信息，因此計(jì)算效果并不理想。近年來，很多基于間接共同鄰居的相似性計(jì)算方法被提出，并得到了深入的研究［7，8］，但在相似性計(jì)算過程中要考慮網(wǎng)絡(luò)全局結(jié)構(gòu)信息，時(shí)間和存儲(chǔ)開銷都非常大，且精確度不高，不適用于大型信息網(wǎng)絡(luò)，無法快速響應(yīng)用戶搜索［9］。近幾年研究者針對(duì)相似性計(jì)算的效果和效率問題進(jìn)行研究，提出ERank［10］、Pathsim［11］、SimFusion＋［12］、WebSimRank［13］、P－Rank［5］等相似性計(jì)算模型。其中，E－Rank在計(jì)算相似性時(shí)，考慮實(shí)體任意距離的相遇概率，返回了比較全面的計(jì)算結(jié)果。PathSim 采用用戶指定元路徑 （Meta－path）的方法計(jì)算實(shí)體相似性，用戶可以選擇不同的相似性判斷角度。SimFusion＋針對(duì)SimFusion不收斂的問題進(jìn)行了改進(jìn)，同時(shí)優(yōu)化計(jì)算過程。WebSimRank提出針對(duì)Web頁面的兩步迭代基本思想，明顯提高了相似性的計(jì)算效率。P.Zhao和J.Han等提出P－Rank算法，在計(jì)算過程中同時(shí)考慮了入鏈接和出鏈接，提高了精確度，但是時(shí)間和存儲(chǔ)開銷同樣很大，不適用于大型信息網(wǎng)絡(luò)的相似性計(jì)算，而目前針對(duì)P－Rank的優(yōu)化方法方面的研究較少。

2 構(gòu)建“消費(fèi)者－商品”關(guān)系網(wǎng)絡(luò)

2.1 數(shù)據(jù)描述

使用SNAP （Stanford network analysis project）提供的亞馬遜購物數(shù)據(jù) （Amazon product co－purchasing network metadata.http：／／snap.stanford.edu／data／amazon－meta.html），構(gòu) 建“消費(fèi)者－商品”關(guān)系網(wǎng)絡(luò) （簡(jiǎn)稱購物網(wǎng)絡(luò)）。數(shù)據(jù)集中有548 552 個(gè)商品 （書 籍、音樂、DVD 以 及 視 頻 錄 影 帶），7 781 990條評(píng)論，2 509 699個(gè)商品目錄層次，393 561本圖書，19 828張DVDs，10 3144張音樂CDs以及26 132個(gè)視頻錄影帶。表1 為數(shù)據(jù)集中的一條數(shù)據(jù)，對(duì)于每種商品，其包含的基本數(shù)據(jù)為商品ID、商品的識(shí)別碼ASIN、商品名稱Title、商品所屬分類Group、商品銷售排行Salesrank、相似商品列表List of similar products、商品分類信息Detailed product categorization以及商品使用信息Product reviews。

2.2 構(gòu)建方法

為構(gòu)建亞馬遜購物網(wǎng)絡(luò)，將商品信息進(jìn)行化簡(jiǎn)，只保留商品識(shí)別碼 （ASIN）以及商品使用信息 （product reviews）中所包含的消費(fèi)者信息，將消費(fèi)者和商品作為實(shí)體，二者之間的關(guān)系包含“購買”以及“被購買”兩種含義。

圖1為購物網(wǎng)絡(luò)模式，其中消費(fèi)者類型和商品類型分別記為U 和P，則實(shí)體類型的集合是 ｛U，P｝，其中P 包括Book、CD、Video和DVD 類型的產(chǎn)品。關(guān)系類型的集合是 ｛UP，PU｝，其中UP、PU 分別表示消費(fèi)者與商品之間的購買與被購買的關(guān)系。

圖1 購物網(wǎng)絡(luò)模式

圖2為購物網(wǎng)絡(luò)實(shí)例，｛u1，u2，u3，u4｝代表消費(fèi)者實(shí)體集合，｛p1，p2，p3，p4｝代表商品實(shí)體集合，消費(fèi)者購買了商品則存在一條有向邊連接兩者，表示消費(fèi)者與商品購買與被購買的關(guān)系，如圖2 中消費(fèi)者u1購買了商品p1，則存在一條連接u1與p1的有向邊，表示u1與p1之間是購買與被購買的關(guān)系，其它關(guān)系同理。

圖2 購物網(wǎng)絡(luò)

根據(jù)真實(shí)的亞馬遜消費(fèi)者購物數(shù)據(jù)構(gòu)建有向圖G（V，E），其中V（v∈V）是有向圖的實(shí)體的集合，代表不同的實(shí)體集合，V＝Vu＋Vp，Vu代表消費(fèi)者實(shí)體集合，Vp表示商品實(shí)體集合，E 是有向圖的邊的集合，代表實(shí)體之間的關(guān)系的集合，有向邊＜u，v＞∈E，u，v∈V 代表實(shí)體u 到v的關(guān)系，E＝E0，E0表示消費(fèi)者與商品之間的聯(lián)系。

對(duì)于有向圖中的一個(gè)實(shí)體v，用I（v）表示v的入鄰居（In－neighbor）的集合，O（v）表示v的出鄰居（Out－neighbor）的集合；用Ii（v）表示v的單個(gè)入鄰居（1≤i≤｜I（v）｜），Oj（v）表示v的單個(gè)出鄰居（1≤j≤｜O（v）｜）。

3 P－Rank

3.1 P－Rank算法思想介紹

P－Rank主要思想是：在信息網(wǎng)絡(luò)中，如果兩個(gè)實(shí)體都與相似的實(shí)體相似，那么這兩個(gè)實(shí)體就是相似的。

表1 亞馬遜某商品的信息

若定義S（a，b）為實(shí)體a和b之間的相似性，S（a，b）∈［0，1］，則

其中，c（0＜c＜1）為衰減系數(shù)，λ∈［0，1］為平衡因子，實(shí)驗(yàn)結(jié)果表明，λ＝0.5，c＝0.8時(shí)計(jì)算結(jié)果最精確。

3.2 P－Rank算法計(jì)算

在P－Rank算法迭代開始時(shí)，任意兩個(gè)實(shí)體間的相似性按照式 （2）初始化

式中：R0（a，b）——第0次迭代 （初始狀態(tài)）下a 和b 之間的相似性，以后每次迭代都在前一次結(jié)果的基礎(chǔ)上對(duì)相似性按照式 （3）進(jìn)行更新

式中：n——節(jié)點(diǎn)數(shù)目，l——迭代次數(shù)，上述迭代過程不斷進(jìn)行，直到收斂為止，最后得到的Rl＋1（a，b）就是實(shí)體a和b 之間的相似性。

P－Rank算法的空間復(fù)雜度是O（n2），空間復(fù)雜度為O（k（）n2），其中，d1和d2分別為有向圖G 中所有節(jié)點(diǎn)的平均入度和平均出度，在最壞情況下時(shí)間復(fù)雜度變?yōu)镺（n4）?？梢?，P－Rank的時(shí)間和空間復(fù)雜度較大，不適用于大型信息網(wǎng)絡(luò)的相似性計(jì)算。

4 算法改進(jìn) （ProductP－Rank）

根據(jù)亞馬遜購物網(wǎng)絡(luò)特征，結(jié)合二分網(wǎng)絡(luò)的特點(diǎn)來對(duì)P－Rank進(jìn)行優(yōu)化。采取預(yù)計(jì)算一步迭代相似性，在線計(jì)算兩步迭代相似性的方法，在不影響準(zhǔn)確率的情況下，可以顯著減少時(shí)間和存儲(chǔ)開銷，進(jìn)而可以提高離線計(jì)算的速率。

圖3和圖4對(duì)比了P－Rank和ProductP－Rank兩種算法的相似性矩陣存儲(chǔ)情況。圖3 中M1表示消費(fèi)者相似性矩陣，M2表示商品的相似性矩陣，經(jīng)過多次迭代后，M1及M2接近滿秩，所需存儲(chǔ)空間巨大。圖4中M3表示一步預(yù)計(jì)算消費(fèi)者相似性矩陣，存儲(chǔ)時(shí)僅需存儲(chǔ)M3即可?？梢奝roductP－Rank所需的存儲(chǔ)空間遠(yuǎn)遠(yuǎn)少于P－Rank。

圖3 P－Rank相似性矩陣的存儲(chǔ)情況

圖4 ProductP－Rank相似性矩陣的存儲(chǔ)情況

4.1 預(yù)計(jì)算

預(yù)計(jì)算1步相似性矩陣只需計(jì)算消費(fèi)者與消費(fèi)者之間的相似性，其過程如下：

對(duì)于任意兩個(gè)消費(fèi)者u1和u2，u1，u2∈Vu，進(jìn)行初始化

R1（u1，u2）計(jì)算過程為：如果u1＝u2，那么R1（u1，u2）＝1，否則

離線計(jì)算1 步相似性矩陣的時(shí)間復(fù)雜度為O（2｜Vu｜2d2），空間復(fù)雜度為O（｜Vu｜2）。

4.2 在線查詢

算法1給出了ProductP－Rank在線查詢算法的基本過程的偽代碼。算法需要輸入預(yù)計(jì)算的1 步相似性矩陣R1，亞馬遜購物網(wǎng)絡(luò)圖G（V，E）和消費(fèi)者指定參數(shù)k。對(duì)于查詢q來說，算法根據(jù)這些輸入返回k［14］個(gè)最相似的商品。

在線查詢算法的時(shí)間復(fù)雜度為O（n（2d2＋k）＋ι（k）），其中，所有節(jié)點(diǎn)的平均入度和平均出度都為d，ι（k）表示對(duì)于鏈表L 中元素排序的時(shí)間開銷，依賴于具體的排序算法，這里采用選擇排序算法。經(jīng)化簡(jiǎn)，在線查詢處理算法的時(shí)間復(fù)雜度為O（nd2）。

算法1：ProductP－Rank 在線查詢算法 Input：NetworkG（V，E），matrix R1，queryq，parameter k；Output：Top－k most similar sorted products to query q；1： Initialize set L＜P，S＞to be empty；2： for all pi∈Vpdo 3： Compute R2（q，pi）using Equation（3）；4： if L.size（）＜kthen 5： L←L∪ ｛＜pi，R2（q，pi）＞｝；6： else 7： Get pj with minimal similarity score from set P；8： if R2（q，pi）＞R2（q，pj）then 9： L← （L－｛＜pj，R2 （q，pj）＞｝）∪ ｛＜pi，R2（q，pi）＞｝；10： end if 11： end if 12： end for 13： Sort products in L according to similarities and output；

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

5.1 實(shí)驗(yàn)環(huán)境

機(jī)器配置為CPU 為Intel（R）Xeon（R），頻率為2.27 GHz 2.26GHz（2處理器），內(nèi)存為16.0GB。操作系統(tǒng)為Windows Server 2008 R2 Enterprise，開 發(fā) 環(huán) 境 為 VS C＋＋2010，所有實(shí)驗(yàn)程序都在內(nèi)存中執(zhí)行。

5.2 實(shí)驗(yàn)數(shù)據(jù)

從亞馬遜購物網(wǎng)絡(luò)中提取出有代表性的5308 個(gè)實(shí)體，其中包含1417個(gè)消費(fèi)者，3891個(gè)商品，這些消費(fèi)者和消費(fèi)者間擁有2341個(gè)連接關(guān)系，消費(fèi)者和商品間擁有14 987個(gè)連接關(guān)系。

5.3 實(shí)驗(yàn)評(píng)估方法

實(shí)驗(yàn)評(píng)估主要是通過和P－Rank相比來評(píng)估提出的方法（ProductP－Rank）的效率和效果。依據(jù)文獻(xiàn) ［5］，將P－Rank的步長(zhǎng)設(shè)置為10，參數(shù)c設(shè)置為0.8，參數(shù)λ設(shè)置為0.5。

5.3.1 實(shí)驗(yàn)效率

實(shí)驗(yàn)效率分為離線階段的時(shí)間和存儲(chǔ)開銷以及在線查詢階段的時(shí)間開銷兩個(gè)方面。離線計(jì)算時(shí)間對(duì)比兩種方法迭代計(jì)算的最終結(jié)束時(shí)間；存儲(chǔ)開銷方面，實(shí)驗(yàn)主要是對(duì)比相似性矩陣的非零元素的規(guī)模。

5.3.2 實(shí)驗(yàn)效果

實(shí)驗(yàn)采用的評(píng)估方法是NDCG （normalized discounted cumulative gain），對(duì)于一個(gè)給定查詢實(shí)體，NDCG 在第p個(gè)位置的值 （NDCG＠p）根據(jù)實(shí)體在結(jié)果序列中的位置以及他們的相似性評(píng)估等級(jí)來計(jì)算。

給定一個(gè)排序后的實(shí)體序列，在第p 位的NDCG 值NDCG＠p 的計(jì)算公式為

式中：DCG＠p （discounted cumulative gain at p）的計(jì)算公式如下

式中：IDCG＠p 為理想的DCG＠p，rel為相似性等級(jí)，這里將P－Rank作為評(píng)估ProductP－Rank 的基準(zhǔn)，rel的值就是l＝10時(shí)對(duì)應(yīng)的查詢和當(dāng)前商品的P－Rank相似性。

在線查詢階段，實(shí)驗(yàn)隨機(jī)選取100 個(gè)商品作為查詢，返回與每個(gè)查詢最相似的Top－k 個(gè)結(jié)果，然后計(jì)算在線查詢時(shí)間和NDCG 的值。

5.4 實(shí)驗(yàn)效率分析

5.4.1 離線計(jì)算時(shí)間

表2表示兩種方法預(yù)計(jì)算相似性矩陣的時(shí)間開銷。通過觀察可知，P－Rank 離線計(jì)算時(shí)間遠(yuǎn)遠(yuǎn)超過ProductPRank，這是由于ProductP－Rank只需計(jì)算一步相似性矩陣，而P－Rank經(jīng)過10次迭代，時(shí)間開銷為所有迭代計(jì)算時(shí)間的總和。實(shí)驗(yàn)結(jié)果表明，ProductP－Rank離線計(jì)算時(shí)間開銷遠(yuǎn)遠(yuǎn)低于P－Rank。

表2 計(jì)算相似性矩陣的時(shí)間開銷

5.4.2 存儲(chǔ)開銷

表3表示P－Rank和ProductP－Rank在預(yù)計(jì)算之后的相似性矩陣規(guī)模。相似性矩陣規(guī)模是指相似性矩陣中非零元素的個(gè)數(shù)。從表中可知，ProductP－Rank的矩陣規(guī)模明顯小于P－Rank，這是因?yàn)楝F(xiàn)實(shí)網(wǎng)絡(luò)通常是比較稀疏的，1步迭代計(jì)算后，非零元素占的比例并不是很大，所以矩陣存儲(chǔ)開銷很小，而P－Rank相似性矩陣經(jīng)過10步迭代后，幾乎達(dá)到滿矩陣。結(jié)果表明，ProductP－Rank存儲(chǔ)開銷遠(yuǎn)遠(yuǎn)低于P－Rank。

表3 相似性矩陣規(guī)模

5.4.3 在線查詢時(shí)間

表4表示使用ProductP－Rank方法在不同k取值對(duì)應(yīng)平均在線查詢時(shí)間開銷，其中l(wèi)＝2。P－Rank這里不作對(duì)比。實(shí)驗(yàn)結(jié)果顯示ProductP－Rank的平均在線查詢時(shí)間開銷隨著k取值變化呈現(xiàn)波動(dòng)，但是基本穩(wěn)定在區(qū)間內(nèi)。k 是常數(shù)，對(duì)在線查詢時(shí)間幾乎沒影響，與之前的時(shí)間復(fù)雜度分析一致，ProductP－Rank的在線查詢時(shí)間小于0.376s，能夠快速響應(yīng)查詢請(qǐng)求。

表4 不同k取值對(duì)應(yīng)平均在線查詢時(shí)間開銷

5.5 實(shí)驗(yàn)效果分析

5.5.1 NDCG

表5表示不同的路徑長(zhǎng)度l對(duì)應(yīng)的NDCG＠50值的變化，其中k＝50。通過觀察實(shí)驗(yàn)結(jié)果可知，ProductP－Rank返回的查詢結(jié)果精確度很高，始終為0.99958。實(shí)驗(yàn)結(jié)果表明，ProductP－Rank 與P－Rank 返 回 結(jié) 果 的 精 確 度 相 近，ProductP－Rank精確度損失很低。

表5 不同l取值對(duì)應(yīng)NDCG 值

表6 表示不同k 取值對(duì)NDCG＠k 值的影響，其中P－Rank的l＝10，ProductP－Rank 的l＝2。從表中可以發(fā)現(xiàn)，P－Rank的NDCG 值不隨k取值變化而變化，始終為1，ProductP－Rank的NDCG 值略微有所波動(dòng)，但是總的來說其值接近1。實(shí)驗(yàn)結(jié)果表明，ProductP－Rank在k 取不同值時(shí)都具有較高的精確度。

表6 不同k取值對(duì)應(yīng)NDCG 值

5.5.2 實(shí)例分析

在Amazon數(shù)據(jù)集上用ProductP－Rank進(jìn)行相似性計(jì)算并選擇了4個(gè)不同的查詢，對(duì)于每個(gè)查詢，依據(jù)ProductPRank相似性計(jì)算方法返回了Top－10個(gè)結(jié)果。表7 給出了ProductP－Rank在Amazon數(shù)據(jù)集上關(guān)于不同查詢的返回結(jié)果。分 析 查 詢 “HowtoMakeAnyoneFallinLovewithYou”，該查詢是一本 “Health，Mind ＆Body”方面的書。從結(jié)果可以看到，排序1、2、3、4、5、6、7、8對(duì)應(yīng)的結(jié)果都是相關(guān)的，均為 “Health，Mind ＆Body”方面的圖書；排序9對(duì)應(yīng)的結(jié)果是關(guān)于 “Literature ＆Fiction”方面的，也算是有些相關(guān)的；排序10 對(duì)應(yīng)的結(jié)果是關(guān)于 “Science ＆Mathematics”方面的，是不相關(guān)的。

表7 ProductP－Rank在Amazon數(shù)據(jù)集上關(guān)于不同查詢的返回結(jié)果

通過實(shí)例分析發(fā)現(xiàn)，ProductP－Rank能夠發(fā)現(xiàn)相似的實(shí)體。在查詢序列中，排序靠前的結(jié)果的相關(guān)程度更大，排序靠后的結(jié)果的相關(guān)程度更小。

6 結(jié)束語

提出一種高效的相似性搜索方法ProductP－Rank，結(jié)合P－Rank快速收斂的特點(diǎn)，通過預(yù)計(jì)算一步相似性矩陣，在線計(jì)算兩步相似性，顯著降低了存儲(chǔ)空間和預(yù)計(jì)算時(shí)間開銷。實(shí)驗(yàn)結(jié)果表明，該方法極大地降低了存儲(chǔ)和預(yù)計(jì)算時(shí)間開銷，且具有較高精確度，能夠適用于大規(guī)模信息網(wǎng)絡(luò)的相似性計(jì)算。

ProductP－Rank方法降低了整體的時(shí)間開銷，但是在線查詢響應(yīng)時(shí)間仍然有待于進(jìn)一步提高，在接下來的工作中，將著重于對(duì)在線查詢響應(yīng)時(shí)間進(jìn)行優(yōu)化。

［1］Sun Y，Yu Y，Han J.Ranking－based clustering of heterogeneous information networks with star network schema ［C］／／ACM SIGKDD International Conference on Knowledge Discovery and Data Mining，2009：797－806.

［2］David Carmel，Naama Zwerdling，Ido Guy，et al.Personalized social search based on the user’s social network ［C］／／International Conference on Information and Knowledge Management－CIKM，2009：1227－1236.

［3］Ido Guy，Naama Zwerdling，David Carmel，et al.Personalized recommendation of social software items based on social relations［C］／／Proceedings of the 3rd ACM Conference on Recommender Systems，2009：53－60.

［4］Moricz M，Dosbayev Y，Berlyant M.Pymk：Friend recommendation at MySpace ［C］／／Proceedings of the ACM SIGMOD International Conference on Management of Data，2010：999－1002.

［5］Zhao P，Han J，Sun Y.P－rank：A comprehensive structural similarity measure over information networks ［C］／／Proceedings of the 18th ACM Conference on Information and Knowledge Management，2009：553－562.

［6］Li C，Han J，He G，et al.Fast computation of SimRank for static and dynamic information networks ［C］／／13th International Conference on Extending Database Technology，2010.

［7］Cai Y，Cong G，Jia X，et al.Efficient algorithms for computing link based similarity in real world networks ［C］／／9th IEEE International Conference on Data Mining，2009：734－739.

［8］Cai Y，Liu H，He J，et al.An adaptive method for efficient similarity calculation［C］／／Proc of DASFAA，2009：339－353.

［9］Li P，Liu H，Xu Yu J，et al.Fast single－pair simrank computation ［C］／／Proc of SDM，2010：571－582.

［10］Zhang M，He Z，Hu H，et al.E－rank：A structural－based similarity measure in social networks ［C］／／Proc of WI，2012：415－422.

［11］Sun Y，Han J，Yan X，et al.Pathsim：Meta path－based top－k similarity search in heterogeneous information networks［C］／／Proc of VLDB，2011：992－1003.

［12］Yu W，Lin XM，Zhang W，et al.SimFusion＋：Extending simfusion towards efficient estimation on large and dynamic networks［C］／／Proc of SIGIR，2012：365－374.

［13］JIN Dailu，ZHANG Yueqin，ZHANG Mingxi.Link－based similarity search among Web pages ［J］.Computer Applications and Software，2014 （1）：57－61 （in Chinese）. ［靳 黛露，張?jiān)虑?，張明?基于鏈接關(guān)系的Web頁面相似度搜索［J］.計(jì)算機(jī)應(yīng)用與軟件，2014 （1）：57－61.］

［14］Lee P，Lakshmanan L，Yu J.On top－k structural similarity search ［C］／／In Proc of ICDE，2012：774－785.