基于P－Rank的網絡書店相似性搜索

呂 巍，鄔春學，3，張明西，鐘 聃

（1.上海理工大學 光電信息與計算機工程學院，上海200093；2.上海理工大學 出版印刷與藝術設計學院，上海200093；3.上海理工大學 新聞出版總署重點實驗室，上海200093；4.中國民用航空西北地區空中交通管理局 計保中心通信室，陜西 西安710075）

0 引 言

傳統基于局部結構的相似性搜索方法依據實體之間的直接鏈接關系計算實體相似性，沒有考慮間接鏈接關系，容易忽略一些潛在相似的結果。基于全局網絡的相似性計算方法［1－4］考慮實體之間的間接鏈接關系，返回結果比較全面，具有較高的精確度，但卻因為時間和存儲開銷巨大無法適應大規模網絡。其中，P－Rank［5］算法在相似性計算時充分考慮入鏈接和出鏈接信息，具有較高的精確度，能夠用于網絡書店的相似性搜索，但時間和存儲開銷同樣很高。為提高網絡書店相似性搜索效率，降低時間和存儲開銷，提出基于P－Rank的相似性搜索的優化方法ProductP－Rank，預計算一步相似性矩陣，在線計算兩步相似性矩陣，實驗驗證了該方法是一種準確有效的相似性搜索算法。

1 相關工作

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

2 構建“消費者－商品”關系網絡

2.1 數據描述

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

2.2 構建方法

為構建亞馬遜購物網絡，將商品信息進行化簡，只保留商品識別碼 （ASIN）以及商品使用信息 （product reviews）中所包含的消費者信息，將消費者和商品作為實體，二者之間的關系包含“購買”以及“被購買”兩種含義。

圖1為購物網絡模式，其中消費者類型和商品類型分別記為U 和P，則實體類型的集合是 ｛U，P｝，其中P 包括Book、CD、Video和DVD 類型的產品。關系類型的集合是 ｛UP，PU｝，其中UP、PU 分別表示消費者與商品之間的購買與被購買的關系。

圖1 購物網絡模式

圖2為購物網絡實例，｛u1，u2，u3，u4｝代表消費者實體集合，｛p1，p2，p3，p4｝代表商品實體集合，消費者購買了商品則存在一條有向邊連接兩者，表示消費者與商品購買與被購買的關系，如圖2 中消費者u1購買了商品p1，則存在一條連接u1與p1的有向邊，表示u1與p1之間是購買與被購買的關系，其它關系同理。

圖2 購物網絡

根據真實的亞馬遜消費者購物數據構建有向圖G（V，E），其中V（v∈V）是有向圖的實體的集合，代表不同的實體集合，V＝Vu＋Vp，Vu代表消費者實體集合，Vp表示商品實體集合，E 是有向圖的邊的集合，代表實體之間的關系的集合，有向邊＜u，v＞∈E，u，v∈V 代表實體u 到v的關系，E＝E0，E0表示消費者與商品之間的聯系。

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

3 P－Rank

3.1 P－Rank算法思想介紹

P－Rank主要思想是：在信息網絡中，如果兩個實體都與相似的實體相似，那么這兩個實體就是相似的。

表1 亞馬遜某商品的信息

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

其中，c（0＜c＜1）為衰減系數，λ∈［0，1］為平衡因子，實驗結果表明，λ＝0.5，c＝0.8時計算結果最精確。

3.2 P－Rank算法計算

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

式中：R0（a，b）——第0次迭代 （初始狀態）下a 和b 之間的相似性，以后每次迭代都在前一次結果的基礎上對相似性按照式 （3）進行更新

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

P－Rank算法的空間復雜度是O（n2），空間復雜度為O（k（）n2），其中，d1和d2分別為有向圖G 中所有節點的平均入度和平均出度，在最壞情況下時間復雜度變為O（n4）。可見，P－Rank的時間和空間復雜度較大，不適用于大型信息網絡的相似性計算。

4 算法改進 （ProductP－Rank）

根據亞馬遜購物網絡特征，結合二分網絡的特點來對P－Rank進行優化。采取預計算一步迭代相似性，在線計算兩步迭代相似性的方法，在不影響準確率的情況下，可以顯著減少時間和存儲開銷，進而可以提高離線計算的速率。

圖3和圖4對比了P－Rank和ProductP－Rank兩種算法的相似性矩陣存儲情況。圖3 中M1表示消費者相似性矩陣，M2表示商品的相似性矩陣，經過多次迭代后，M1及M2接近滿秩，所需存儲空間巨大。圖4中M3表示一步預計算消費者相似性矩陣，存儲時僅需存儲M3即可。可見ProductP－Rank所需的存儲空間遠遠少于P－Rank。

圖3 P－Rank相似性矩陣的存儲情況

圖4 ProductP－Rank相似性矩陣的存儲情況

4.1 預計算

預計算1步相似性矩陣只需計算消費者與消費者之間的相似性，其過程如下：

對于任意兩個消費者u1和u2，u1，u2∈Vu，進行初始化

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

離線計算1 步相似性矩陣的時間復雜度為O（2｜Vu｜2d2），空間復雜度為O（｜Vu｜2）。

4.2 在線查詢

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

在線查詢算法的時間復雜度為O（n（2d2＋k）＋ι（k）），其中，所有節點的平均入度和平均出度都為d，ι（k）表示對于鏈表L 中元素排序的時間開銷，依賴于具體的排序算法，這里采用選擇排序算法。經化簡，在線查詢處理算法的時間復雜度為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 實 驗

5.1 實驗環境

機器配置為CPU 為Intel（R）Xeon（R），頻率為2.27 GHz 2.26GHz（2處理器），內存為16.0GB。操作系統為Windows Server 2008 R2 Enterprise，開 發 環 境 為 VS C＋＋2010，所有實驗程序都在內存中執行。

5.2 實驗數據

從亞馬遜購物網絡中提取出有代表性的5308 個實體，其中包含1417個消費者，3891個商品，這些消費者和消費者間擁有2341個連接關系，消費者和商品間擁有14 987個連接關系。

5.3 實驗評估方法

實驗評估主要是通過和P－Rank相比來評估提出的方法（ProductP－Rank）的效率和效果。依據文獻 ［5］，將P－Rank的步長設置為10，參數c設置為0.8，參數λ設置為0.5。

5.3.1 實驗效率

實驗效率分為離線階段的時間和存儲開銷以及在線查詢階段的時間開銷兩個方面。離線計算時間對比兩種方法迭代計算的最終結束時間；存儲開銷方面，實驗主要是對比相似性矩陣的非零元素的規模。

5.3.2 實驗效果

實驗采用的評估方法是NDCG （normalized discounted cumulative gain），對于一個給定查詢實體，NDCG 在第p個位置的值 （NDCG＠p）根據實體在結果序列中的位置以及他們的相似性評估等級來計算。

給定一個排序后的實體序列，在第p 位的NDCG 值NDCG＠p 的計算公式為

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

式中：IDCG＠p 為理想的DCG＠p，rel為相似性等級，這里將P－Rank作為評估ProductP－Rank 的基準，rel的值就是l＝10時對應的查詢和當前商品的P－Rank相似性。

在線查詢階段，實驗隨機選取100 個商品作為查詢，返回與每個查詢最相似的Top－k 個結果，然后計算在線查詢時間和NDCG 的值。

5.4 實驗效率分析

5.4.1 離線計算時間

表2表示兩種方法預計算相似性矩陣的時間開銷。通過觀察可知，P－Rank 離線計算時間遠遠超過ProductPRank，這是由于ProductP－Rank只需計算一步相似性矩陣，而P－Rank經過10次迭代，時間開銷為所有迭代計算時間的總和。實驗結果表明，ProductP－Rank離線計算時間開銷遠遠低于P－Rank。

表2 計算相似性矩陣的時間開銷

5.4.2 存儲開銷

表3表示P－Rank和ProductP－Rank在預計算之后的相似性矩陣規模。相似性矩陣規模是指相似性矩陣中非零元素的個數。從表中可知，ProductP－Rank的矩陣規模明顯小于P－Rank，這是因為現實網絡通常是比較稀疏的，1步迭代計算后，非零元素占的比例并不是很大，所以矩陣存儲開銷很小，而P－Rank相似性矩陣經過10步迭代后，幾乎達到滿矩陣。結果表明，ProductP－Rank存儲開銷遠遠低于P－Rank。

表3 相似性矩陣規模

5.4.3 在線查詢時間

表4表示使用ProductP－Rank方法在不同k取值對應平均在線查詢時間開銷，其中l＝2。P－Rank這里不作對比。實驗結果顯示ProductP－Rank的平均在線查詢時間開銷隨著k取值變化呈現波動，但是基本穩定在區間內。k 是常數，對在線查詢時間幾乎沒影響，與之前的時間復雜度分析一致，ProductP－Rank的在線查詢時間小于0.376s，能夠快速響應查詢請求。

表4 不同k取值對應平均在線查詢時間開銷

5.5 實驗效果分析

5.5.1 NDCG

表5表示不同的路徑長度l對應的NDCG＠50值的變化，其中k＝50。通過觀察實驗結果可知，ProductP－Rank返回的查詢結果精確度很高，始終為0.99958。實驗結果表明，ProductP－Rank 與P－Rank 返 回 結 果 的 精 確 度 相 近，ProductP－Rank精確度損失很低。

表5 不同l取值對應NDCG 值

表6 表示不同k 取值對NDCG＠k 值的影響，其中P－Rank的l＝10，ProductP－Rank 的l＝2。從表中可以發現，P－Rank的NDCG 值不隨k取值變化而變化，始終為1，ProductP－Rank的NDCG 值略微有所波動，但是總的來說其值接近1。實驗結果表明，ProductP－Rank在k 取不同值時都具有較高的精確度。

表6 不同k取值對應NDCG 值

5.5.2 實例分析

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

表7 ProductP－Rank在Amazon數據集上關于不同查詢的返回結果

通過實例分析發現，ProductP－Rank能夠發現相似的實體。在查詢序列中，排序靠前的結果的相關程度更大，排序靠后的結果的相關程度更小。

6 結束語

提出一種高效的相似性搜索方法ProductP－Rank，結合P－Rank快速收斂的特點，通過預計算一步相似性矩陣，在線計算兩步相似性，顯著降低了存儲空間和預計算時間開銷。實驗結果表明，該方法極大地降低了存儲和預計算時間開銷，且具有較高精確度，能夠適用于大規模信息網絡的相似性計算。

ProductP－Rank方法降低了整體的時間開銷，但是在線查詢響應時間仍然有待于進一步提高，在接下來的工作中，將著重于對在線查詢響應時間進行優化。

［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）. ［靳 黛露，張月琴，張明西.基于鏈接關系的Web頁面相似度搜索［J］.計算機應用與軟件，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.