基于小世界網(wǎng)絡的用戶位置行為興趣模型*

張少中，俞東云

（浙江萬里學院電子信息學院 寧波315100）

1引言

在商務活動中，對顧客而言，總是希望花最少的時間和精力購買到自己最滿意的商品或服務；對商家和企業(yè)而言，總是希望投入最少的花費了解并滿足用戶的需求。通過了解用戶的位置信息，分析用戶的位置變化習慣和特征，并與位置資源內(nèi)容信息結(jié)合起來，可以挖掘并發(fā)現(xiàn)用戶的服務需求，為商家的定向廣告和定向服務提供有利支持。位置行為分析是網(wǎng)絡結(jié)構(gòu)挖掘，它不同于傳統(tǒng)的數(shù)據(jù)挖掘中基于個體目標數(shù)據(jù)模式抽取的方法，而是基于目標之間的關(guān)系進行模式挖掘[1,2]，這種基于對象間的關(guān)系進行模式挖掘的目的是在目標網(wǎng)絡中提取正確的、新穎的、有用的結(jié)構(gòu)模式。結(jié)構(gòu)模式指的是網(wǎng)絡結(jié)構(gòu)中的蘊涵的規(guī)律、內(nèi)在機制、變化趨勢等知識。

網(wǎng)絡結(jié)構(gòu)挖掘方法是這類研究中最受關(guān)注的問題，其中小世界網(wǎng)絡模型[3]是Watts和Strogatz在1998年提出的基于人類社會關(guān)系分析的網(wǎng)絡模型，用于描述具有相互作用的個體所構(gòu)成的社會或者生態(tài)系統(tǒng)，小世界網(wǎng)絡已被成功應用于說明各種社會網(wǎng)絡結(jié)構(gòu)。Batul J Mirza提出了一種“跳轉(zhuǎn)連接”的圖模型推薦方法，采用小世界網(wǎng)絡模型描述結(jié)點間的關(guān)系，利用“jumping connections”將圖中具有相似偏好的用戶連接成一個有向邊，該有向邊所指用戶的偏好就是連接該用戶的前一個用戶推薦集[4]；Adriana Iamnitchi等提出了一種基于小世界網(wǎng)絡的文件共享模型，該模型能夠根據(jù)用戶的興趣分析共享文件的關(guān)系，提出一種表示用戶感興趣的數(shù)據(jù)共享圖[5]。Kashif Ali提出了一種基于小世界網(wǎng)絡的網(wǎng)格資源發(fā)現(xiàn)方法[6]；竇文采用一種全局可信度的方法進行P2P網(wǎng)絡拓撲結(jié)構(gòu)的構(gòu)建[7]；鄭耿忠等將小世界網(wǎng)絡引入無線傳感器網(wǎng)絡分析，研究無線傳感器網(wǎng)絡拓撲結(jié)構(gòu)，發(fā)現(xiàn)其中隱藏的規(guī)律從而有效提高網(wǎng)絡性能[8]；梁活民等結(jié)合Cayley圖和小世界網(wǎng)絡，采用基于群論中的半直積方法構(gòu)造了一個具有良好性質(zhì)的靜態(tài)互連網(wǎng)絡[9]。

本文采用小世界網(wǎng)絡模型進行位置資源結(jié)點特征分析，對用戶的位置行為路徑和特征進行描述和分析，獲得用戶所處的地理位置、行為路徑特征與當前位置資源直接的相似性，并將用戶位置信息看作一個樹根，將位置資源內(nèi)容看作結(jié)點，采用改進的最短路徑算法計算根結(jié)點到各個結(jié)點的路徑長度，從而分析出用戶最感興趣的位置資源結(jié)點。

2 結(jié)點推薦度與位置資源結(jié)點網(wǎng)絡結(jié)構(gòu)

小世界網(wǎng)絡是一種無向無權(quán)網(wǎng)絡，其網(wǎng)絡中的連接邊只有兩種情況，例如，對于任何兩個結(jié)點之間是否存在鄰接邊可以表示為0、1兩種情況，其中0為兩結(jié)點之間不存在邊；1為存在邊。但是許多真實網(wǎng)絡中結(jié)點之間的聯(lián)系不能單純地僅用存在和不存在來表示。在與商務信息相關(guān)的位置服務中，在某一位置或者區(qū)域范圍內(nèi)的商務信息結(jié)點的關(guān)聯(lián)程度差異很大，采用小世界網(wǎng)絡模型的無向無權(quán)圖難以表示位置資源結(jié)點之間的聯(lián)系。本文在小世界網(wǎng)絡模型中引入推薦度方法，用于建立小世界網(wǎng)絡的邊連接權(quán)值，構(gòu)建位置資源網(wǎng)絡，從而更準確描述位置信息資源之間的關(guān)聯(lián)程度。本文采用局部推薦度與全局推薦度描述結(jié)點間的關(guān)聯(lián)程度。

假設整個位置資源網(wǎng)絡為N，N中包含的資源結(jié)點集合為O，O由n個不同的資源結(jié)點構(gòu)成，即：O={o1,o2,o3,…,on}。采用P2P網(wǎng)絡可信度的方法，位置資源網(wǎng)絡可定義局部推薦度和全局推薦度。

定義1（局部推薦度）設pi,j表示結(jié)點i對結(jié)點j的推薦度，該推薦度取決于結(jié)點i與結(jié)點j的交互歷史，有其中Ii,j為結(jié)點i與結(jié)點j在某固定時間τ內(nèi)產(chǎn)生直接交互的次數(shù)，具體可以是用戶位置從結(jié)點i直接到達結(jié)點j的次數(shù)，Si,j為在結(jié)點看來交易成功的次數(shù)，其中，當Ii,j=0 時，pi,j=0。

定義2（全局推薦度）在網(wǎng)絡N中，結(jié)點i對于任意結(jié)點j的全局推薦度為Tj，設：

其中N為網(wǎng)絡規(guī)模，pi,j為局部推薦度，Kj為與結(jié)點j發(fā)生關(guān)聯(lián)的結(jié)點集合，當Kj=覫時，即所有結(jié)點均不與結(jié)點j發(fā)生關(guān)聯(lián)時，此時的結(jié)點j的全局推薦度為0。

3 基于小世界網(wǎng)絡的用戶位置行為分析與聚類

3.1 用戶位置行為分析小世界網(wǎng)絡的路徑長度和聚類系數(shù)

小世界網(wǎng)絡包括了兩個重要的參數(shù)，平均路徑長度和聚類系數(shù)。其中平均路徑長度用來度量整體網(wǎng)絡結(jié)點之間關(guān)聯(lián)的程度和有效性，聚類系數(shù)用來表示鄰近結(jié)點之間的緊密程度。用戶的位置行為分析是通過用戶所處位置和路徑來搜索用戶到其位置資源結(jié)點的路徑權(quán)值，進而分析用戶可能感興趣的位置資源結(jié)點。路徑權(quán)值是關(guān)聯(lián)用戶興趣和位置資源最基本的組成元素，就是推薦度值。用戶位置結(jié)點與位置資源結(jié)點的路徑權(quán)值記為w，用來描述用戶位置結(jié)點vi和位置資源結(jié)點uj間的關(guān)聯(lián)程度。w(vi,uj)的定義如下。

定義3 用戶位置結(jié)點vi和位置資源結(jié)點uj間的路徑權(quán)值為：

其中，gj(Γ*)為推薦度。

定義4 網(wǎng)絡中結(jié)點之間的路徑長度用路徑權(quán)值的倒數(shù)表示，即：

當 w(vi,uj)=0時，L(vi,uj)=∞。

3.2 用戶位置行為小世界網(wǎng)絡聚類分析算法

給定規(guī)則網(wǎng)絡為G=(V,E)，網(wǎng)絡度數(shù)為k，V為結(jié)點集合，E為邊集合，其子圖是一個小世界網(wǎng)絡，該子圖可以通過刪除規(guī)則網(wǎng)絡中的某些連接邊的方法得到，得到的網(wǎng)絡能夠使函數(shù)f=aL+bC|m最大化，其中，a和b為常數(shù)，m為整數(shù),L和C分別是特征路徑長度和聚類系數(shù)。給定用戶位置信息并確定結(jié)點屬性集合，由于關(guān)于小世界網(wǎng)絡的優(yōu)化問題是一個NP難題，需要在聚類系數(shù)和路徑長度間進行平衡處理。將該位置結(jié)點作為用戶興趣結(jié)點，采用的小世界網(wǎng)絡聚類算法如下。

算法1 小世界網(wǎng)絡的用戶位置行為聚類

（1）重復刪除1條邊，刪除后可以使得函數(shù)f最大，直到共有m條邊被刪除。

（2）加入1條邊，使得函數(shù)f最大，并進行調(diào)整，如果加入的邊與刪除的邊相同，則轉(zhuǎn)到（3）。

（3）刪除 1 條邊，使得函數(shù) f最大，則轉(zhuǎn)到（2）。

（4）輸出當前滿足fmax的參數(shù)L和C。

這樣獲得的網(wǎng)絡即為滿足條件的小世界網(wǎng)絡，其結(jié)點集合為：V′={vi,ui|vi,ui∈V∧L(vi,ui)≤L}。

4 改進的最短路徑搜索算法

在位置資源環(huán)境中，用戶的興趣對推薦系統(tǒng)來說是未知的，需要通過搜索聚類子空間所有位置資源的特征才能給出用戶可能感興趣的商品，因此，本文以經(jīng)典的Dijltstra算法為基礎(chǔ)，通過改進其搜索策略，提高其搜索速度。使用一種最短路徑根樹算法對經(jīng)典Dijltstra算法進行改進，該算法構(gòu)建了一個最短路徑根樹，在最短路徑根樹中所包括的結(jié)點就是已經(jīng)搜索到最短路徑的那些結(jié)點和路徑。在該根樹中，每個結(jié)點都有一個父親結(jié)點，表示為Pa(u)，使用一系列的標記記錄從結(jié)點u到根的路徑，記為SP。在搜索過程中，首先從候選結(jié)點集合中選擇與源點距離最小的一個結(jié)點，將其加入根樹中，重復這個過程，直到所有的結(jié)點都包含在根樹為止。這樣在這個根樹中，所有的源點到其他結(jié)點的最短路徑就都搜索到了。改進的最短路徑算法如下。

算法 2 選擇一個結(jié)點vi作為樹Tree的根結(jié)點s，對于每一個SPk(k

（1）s→hl路徑在 SPj上，則將該路徑融入 s。

（2）hl是 SPk的中間結(jié)點，而且也在 SPj上，則刪除 hl，將其父結(jié)點和子結(jié)點連接。

（3）hl→t路徑在 SPj上，則將該路徑融入 t，直到所有的SPk(k

（4）除了結(jié)點s和uj外，沒有其他結(jié)點在另一條路徑上，則得到的路徑為最短路徑D。

5 實驗與分析

5.1 實驗設計

通過對Movieslens數(shù)據(jù)集[10]改造，令其中的電影數(shù)據(jù)表示位置資源結(jié)點，通過用戶的打分建立電影資源的小世界網(wǎng)絡，利用部分用戶打分作為測試數(shù)據(jù)，即為用戶位置結(jié)點進行模型和算法的評價和測試。本文選擇的Movieslens興趣網(wǎng)絡包括943個用戶對1 682個電影的100 000條打分評價，實驗中使用900個用戶對1 682個電影的50 000條評價進行模型訓練，使用其他用戶的1 000條進行驗證測試。

算法1實驗結(jié)果見表1。

算法2實驗中，用戶興趣的有效性分析采用準確性和時間效率值表示。當用戶的興趣結(jié)點同時在推薦集合和測試集合中的時候，表明該預測是正確的；當用戶的興趣點在推薦集合中，但是不在測試集合中的時候，表明該預測是錯誤的；當用戶的興趣點不在推薦集合中，但是卻在測試集合中，表明該預測也是錯誤的。

表1 不同參數(shù)下模型錯誤邊的數(shù)目

本文采用經(jīng)典最短路徑算法與本文提出的改進的最短路徑算法進行比較，為簡化實驗，本文采用全樣本空間搜索方法，沒有限定某一聚類子空間，對算法的執(zhí)行沒有影響。其精確度和時間分析如圖1和圖2所示。

5.2 性能分析

從表1的實驗統(tǒng)計結(jié)果可以看出，本文提出的小世界模型及其聚類算法可以實現(xiàn)用戶的位置行為分析和聚類，在網(wǎng)絡結(jié)構(gòu)中多余的邊數(shù)和缺失的邊數(shù)相對于網(wǎng)絡復雜度來說在可以接受的范圍內(nèi)，并且可以通過對參數(shù)的調(diào)整提高其精度，減少錯誤的邊數(shù)和缺失的邊數(shù)的數(shù)目。當參數(shù)選擇合適的情況下，例如本文中當參數(shù)a、b和m值分別取 0.4、0.6、100 和0.3、0.7、200 時，算法具有較好的精度。

圖1 兩種算法的精確度比較

圖2 兩種算法的時間復雜度比較

從圖1的實驗結(jié)果可以看出，改進的最短路徑算法可以正確推薦用戶基于位置興趣結(jié)點，并較經(jīng)典的最短路徑算法具有一定程度提升，其準確率根據(jù)測試集合樣本數(shù)目的不同會有小的波動，其準確率基本在80%左右，可以滿足目前商務應用需求。從圖2可以看出，改進的最短路徑算法較經(jīng)典最短路徑有較大改進，這種情況隨測試集樣本數(shù)量的增加變得尤為明顯，當樣本接近1 000個時，經(jīng)典最短路徑算法等待時間較長。

6 結(jié)束語

本文引入了一種小世界網(wǎng)絡模型用于用戶基于位置的行為分析，可為商務活動提供有價值的個性化服務。采用推薦度計算方法和小世界網(wǎng)絡進行用戶行為屬性聚類，將資源結(jié)點推薦轉(zhuǎn)化為路徑搜索問題，通過將用戶位置作為一個樹根，把位置資源作為用戶的興趣結(jié)點，采用改進的最短路徑算法計算根結(jié)點到各個結(jié)點的推薦度，從而給出用戶最感興趣的位置資源結(jié)點。實驗結(jié)果表明，采用該方法建立的用戶位置行為興趣模型能夠很好地描述用戶基于位置的興趣和意愿，算法在結(jié)果精度和計算時間上都具有良好的性能。

1 Joseph A Cazier,Benjamin B M Shao,Robert D St Louis.Sharing information and building trust through value congruence.Information System Front,2007(9):515～529

2 Culnan M J.Mapping the Intellectual Structure of MIS,1980-1985:a co-citation analysis.MIS Quarterly,1987，11(3):341～353

3 Watts D,Strogatz S.Collective dynamics ofsmall-world networks.Nature,1998

4 BatulJ M,Benjamin J K,Ramakrishnan N.Studying recommendation algorithms by graph analysis. Journal of intelligent information systems,2003,20(2):131～160

5 Adriana I,Matei R,Ian T F.Small-world file-sharing communities.INFOCOM,2004

6 Ali K,Datta S,Aboelaze M.Grid resource discovery using small world overlay graphs.Proceedings of the 18th IEEE Canadian Conference on Electrical and Computer Engineering,2005

7 竇文.信任敏感的P2P拓撲構(gòu)造及其相關(guān)技術(shù)研究.國防科技大學博士學位論文，2003

8 鄭耿忠，劉三陽，齊小剛.基于小世界網(wǎng)絡模型的無線傳感器網(wǎng)絡拓撲研究綜述.控制與決策，2010,25(12):1 761～1 768

9 梁活民,肖文俊.一種具有小世界網(wǎng)絡特征的常數(shù)度結(jié)構(gòu)化覆蓋網(wǎng)絡.計算機學報,2010,33(9):1 541～1 547

10 MovieLens.http://movielens.umn.edu