張少中，俞東云

（浙江萬(wàn)里學(xué)院電子信息學(xué)院 寧波315100）

1引言

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

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

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

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

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

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

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

定義2（全局推薦度）在網(wǎng)絡(luò)N中，結(jié)點(diǎn)i對(duì)于任意結(jié)點(diǎn)j的全局推薦度為T(mén)j，設(shè)：

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

3 基于小世界網(wǎng)絡(luò)的用戶(hù)位置行為分析與聚類(lèi)

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

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

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

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

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

當(dāng) w(vi,uj)=0時(shí)，L(vi,uj)=∞。

3.2 用戶(hù)位置行為小世界網(wǎng)絡(luò)聚類(lèi)分析算法

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

算法1 小世界網(wǎng)絡(luò)的用戶(hù)位置行為聚類(lèi)

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

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

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

（4）輸出當(dāng)前滿(mǎn)足fmax的參數(shù)L和C。

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

4 改進(jìn)的最短路徑搜索算法

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

算法 2 選擇一個(gè)結(jié)點(diǎn)vi作為樹(shù)Tree的根結(jié)點(diǎn)s，對(duì)于每一個(gè)SPk(k

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

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

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

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

5 實(shí)驗(yàn)與分析

5.1 實(shí)驗(yàn)設(shè)計(jì)

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

算法1實(shí)驗(yàn)結(jié)果見(jiàn)表1。

算法2實(shí)驗(yàn)中，用戶(hù)興趣的有效性分析采用準(zhǔn)確性和時(shí)間效率值表示。當(dāng)用戶(hù)的興趣結(jié)點(diǎn)同時(shí)在推薦集合和測(cè)試集合中的時(shí)候，表明該預(yù)測(cè)是正確的；當(dāng)用戶(hù)的興趣點(diǎn)在推薦集合中，但是不在測(cè)試集合中的時(shí)候，表明該預(yù)測(cè)是錯(cuò)誤的；當(dāng)用戶(hù)的興趣點(diǎn)不在推薦集合中，但是卻在測(cè)試集合中，表明該預(yù)測(cè)也是錯(cuò)誤的。

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

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

5.2 性能分析

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

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

圖2 兩種算法的時(shí)間復(fù)雜度比較

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

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

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

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拓?fù)錁?gòu)造及其相關(guān)技術(shù)研究.國(guó)防科技大學(xué)博士學(xué)位論文，2003

8 鄭耿忠，劉三陽(yáng)，齊小剛.基于小世界網(wǎng)絡(luò)模型的無(wú)線(xiàn)傳感器網(wǎng)絡(luò)拓?fù)溲芯烤C述.控制與決策，2010,25(12):1 761～1 768

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

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