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

1、基于小世界網(wǎng)絡(luò)的用戶(hù)位置行為興趣模型研究與開(kāi)發(fā)基于小世界網(wǎng)絡(luò)的用戶(hù)位置行為興趣模型(浙江萬(wàn)里學(xué)院電子信息學(xué)院寧波315100)1引言描述結(jié)點(diǎn)之間的相似性.通過(guò)將用戶(hù)位置作為一個(gè)樹(shù)根.把位置資源作為用戶(hù)的興趣結(jié)點(diǎn),將興趣搜索轉(zhuǎn)換為最短路徑計(jì)算問(wèn)題.通過(guò)改進(jìn)的最短路徑算法計(jì)算根結(jié)點(diǎn)到各個(gè)結(jié)點(diǎn)的推薦度,分析用戶(hù)最感興趣的位置資源結(jié)點(diǎn).實(shí)驗(yàn)結(jié)果表明,采用該方法建立的用戶(hù)位置行為興趣模型能夠很好地描述用戶(hù)基于位置的興趣和意愿,算法在結(jié)果精度和計(jì)算時(shí)間上都具有良好的性能.在商務(wù)活動(dòng)中,對(duì)顧客而言,總是希望花最少的時(shí)間和精力購(gòu)買(mǎi)到自己最滿(mǎn)意的商品或服務(wù);對(duì)商家和企業(yè)而戶(hù)的服務(wù)需求,為商家的定向廣告和定向服務(wù)

2、提供有利支之間的關(guān)系進(jìn)行模式挖掘l】,21,這種基于對(duì)象間的關(guān)系進(jìn)行模式挖掘的目的是在目標(biāo)網(wǎng)絡(luò)中提取正確的,新穎的,有律,內(nèi)在機(jī)制,變化趨勢(shì)等知識(shí).網(wǎng)絡(luò)結(jié)構(gòu)挖掘方法是這類(lèi)研究中最受關(guān)注的問(wèn)題,其國(guó)家自然科學(xué)基金資助項(xiàng)目(No.71071145),浙江省自然科學(xué)基金資助項(xiàng)目(No.Y6090027),寧波市自然科學(xué)基金資助項(xiàng)目(No.2009A610076)中小世界網(wǎng)絡(luò)模型l3_是Watts和Strogatz在1998年提出的基于人類(lèi)社會(huì)關(guān)系分析的網(wǎng)絡(luò)模型,用于描述具有相互作用的個(gè)體所構(gòu)成的社會(huì)或者生態(tài)系統(tǒng),小世界網(wǎng)絡(luò)已被成種"跳轉(zhuǎn)連接"的圖模型推薦方法,采用小世界網(wǎng)絡(luò)模型描

3、述結(jié)點(diǎn)問(wèn)的關(guān)系,利用"j'umpin'gconnections"將圖中具有相好就是連接該用戶(hù)的前一個(gè)用戶(hù)推薦集;AdrianaIamnitchi等提出了一種基于小世界網(wǎng)絡(luò)的文件共享模型,該模型能夠根據(jù)用戶(hù)的興趣分析共享文件的關(guān)系,提出一種表示用戶(hù)感興趣的數(shù)據(jù)共享圖_5】.KashifAli提出了一種基于小世界網(wǎng)絡(luò)的網(wǎng)格資源發(fā)現(xiàn)方法【6j:竇文采用一種全局可信度的方法進(jìn)行P2P網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的構(gòu)建;鄭耿忠群論中的半直積方法構(gòu)造了一個(gè)具有良好性質(zhì)的靜態(tài)互連網(wǎng)絡(luò)91.硪窕與評(píng)發(fā)本文采用小世界網(wǎng)絡(luò)模型進(jìn)行位置資源結(jié)點(diǎn)特征分析.對(duì)用戶(hù)的位置行為路徑和特征進(jìn)行描述和分析,

4、獲得用戶(hù)所處的地理位置,行為路徑特征與當(dāng)前位置資源直接的相似性,并將用戶(hù)位置信息看作一個(gè)樹(shù)根,將位置資源內(nèi)容點(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)之間不存的位置服務(wù)中,在某一位置或者區(qū)域范圍內(nèi)的商務(wù)信息結(jié)值,構(gòu)建位置資源網(wǎng)絡(luò),從而更準(zhǔn)確描述位置信息資源之點(diǎn)間的關(guān)聯(lián)程度.假設(shè)整個(gè)位置資源網(wǎng)絡(luò)為,N中包含的資源結(jié)點(diǎn)集合為0,0由n個(gè)不同的資源結(jié)點(diǎn)構(gòu)成,即:0=o,0,0",On.采用P2P網(wǎng)絡(luò)可信度的方

5、法,位置資源網(wǎng)絡(luò)可定義局部推薦度和全局推薦度.定義1(局部推薦度)設(shè)P"表示結(jié)點(diǎn)i對(duì)結(jié)點(diǎn).的推薦度,該推薦度取決于結(jié)點(diǎn)i與結(jié)點(diǎn)的交互歷史,有P"=,其中,為結(jié)點(diǎn)i與結(jié)點(diǎn).在某固定時(shí)間7_內(nèi)產(chǎn)生直,J接交互的次數(shù),具體可以是用戶(hù)位置從結(jié)點(diǎn)i直接到達(dá)結(jié)點(diǎn)f的次數(shù),5"為在結(jié)點(diǎn)看來(lái)交易成功的次數(shù),其中,當(dāng)ff.,=0時(shí)PFO.定義2(全局推薦度)在網(wǎng)絡(luò)N中,結(jié)點(diǎn)i對(duì)于任意結(jié)點(diǎn)的全局推薦度為T(mén)j,設(shè):,iK_,當(dāng)Kj0時(shí)(1)iEKj0.當(dāng)Kj:O時(shí)其中N為網(wǎng)絡(luò)規(guī)模,P"為局部推薦度,為與結(jié)點(diǎn)發(fā)生關(guān)聯(lián)的結(jié)點(diǎn)集合,當(dāng)K=時(shí),即所有結(jié)點(diǎn)均不與結(jié)/Z,J發(fā)生關(guān)聯(lián)時(shí),此

6、時(shí)的結(jié)點(diǎn)的全局推薦度為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)度和關(guān)聯(lián)的程度和有效性,聚類(lèi)系數(shù)用來(lái)表示鄰近結(jié)點(diǎn)之間的徑來(lái)搜索用戶(hù)到其位置資源結(jié)點(diǎn)的路徑權(quán)值,進(jìn)而分析用與位置資源結(jié)點(diǎn)的路徑權(quán)值記為W,用來(lái)描述用戶(hù)位置結(jié)點(diǎn)和位置資源結(jié)點(diǎn)問(wèn)的關(guān)聯(lián)程度.w(v【,"J的定義如下.定義3用戶(hù)位置結(jié)點(diǎn)和位置資源結(jié)點(diǎn)間的路徑權(quán)值為:,)=茍(r),0-<<w(v)1(2)其中,gj(r)為推薦度.定義4網(wǎng)絡(luò)中結(jié)點(diǎn)之間的路徑長(zhǎng)度用路徑權(quán)值的倒數(shù)表示,即:1(,:_(3)&qu

7、ot;J當(dāng),)=O時(shí),=o.給定規(guī)則網(wǎng)絡(luò)為G=(,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+bCI最大化,其中,a和b為常數(shù),m為位置信息并確定結(jié)點(diǎn)屬性集合,由于關(guān)于小世界網(wǎng)絡(luò)的優(yōu)行平衡處理.將該位置結(jié)點(diǎn)作為用戶(hù)興趣結(jié)點(diǎn),采用的小世界網(wǎng)絡(luò)聚類(lèi)算法如下.算法1小世界網(wǎng)絡(luò)的用戶(hù)位置行為聚類(lèi)(1)重復(fù)刪除1條邊,刪除后可以使得函數(shù)廠最大,直到共有m條邊被刪除.(2)加入l條邊,使得函數(shù)廠最大,并進(jìn)行調(diào)整,如果加入的邊與刪除的邊相同,則轉(zhuǎn)到(3).(3)刪除l條邊,使得函數(shù)廠最大,則轉(zhuǎn)到(2)

8、.(4)輸出當(dāng)前滿(mǎn)足的參數(shù)和C.這樣獲得的網(wǎng)絡(luò)即為滿(mǎn)足條件的小世界網(wǎng)絡(luò),其結(jié)點(diǎn)電信科學(xué)鬻2(2:囀繁鬻集合為:=,ttlv,VL(v,地).4改進(jìn)的最短路徑搜索算法在位置資源環(huán)境中,用戶(hù)的興趣對(duì)推薦系統(tǒng)來(lái)說(shuō)是未知的,需要通過(guò)搜索聚類(lèi)子空間所有位置資源的特征才能給出用戶(hù)可能感興趣的商品.因此,本文以經(jīng)典的Dijltstra一種最短路徑根樹(shù)算法對(duì)經(jīng)典Dijltstra算法進(jìn)行改進(jìn),該算法構(gòu)建了一個(gè)最短路徑根樹(shù),在最短路徑根樹(shù)中所包括根樹(shù)中,每個(gè)結(jié)點(diǎn)都有一個(gè)父親結(jié)點(diǎn),表示為(").使用一結(jié)點(diǎn),將其加入根樹(shù)中,重復(fù)這個(gè)過(guò)程,直到所有的結(jié)點(diǎn)都包含在根樹(shù)為止.這樣在這個(gè)根樹(shù)中,所有的源點(diǎn)到其他結(jié)

9、點(diǎn)的最短路徑就都搜索到了.改進(jìn)的最短路徑算法如下.算法2選擇一個(gè)結(jié)點(diǎn)作為樹(shù)Tree的根結(jié)點(diǎn),對(duì)于每一個(gè)<)路徑上的結(jié)點(diǎn)h,有以下步驟.(1)5一路徑在上,則將該路徑融人s.(2)h是S的中問(wèn)結(jié)點(diǎn),而且也在S上,則刪除h,將其父結(jié)點(diǎn)和子結(jié)點(diǎn)連接.(3)ht-t路徑在上,則將該路徑融人t,直到所有的SPk(k<i)路徑上無(wú)的結(jié)點(diǎn);若得到的樹(shù)有一條路徑的結(jié)點(diǎn)集合的子集是另一條路徑的結(jié)點(diǎn)集合,則刪除該路徑,然后將葉子結(jié)點(diǎn)融合為一結(jié)點(diǎn),得到路徑D.(4)除了結(jié)點(diǎn)s和u,外,沒(méi)有其他結(jié)點(diǎn)在另一條路徑上,則得到的路徑為最短路徑D.5實(shí)驗(yàn)與分析通過(guò)對(duì)Movieslens數(shù)據(jù)集l10

10、1改造,令其中的電影數(shù)據(jù)表示位置資源結(jié)點(diǎn),通過(guò)用戶(hù)的打分建立電影資源的小世界網(wǎng)絡(luò).利用部分用戶(hù)打分作為測(cè)試數(shù)據(jù),即為用戶(hù)位置Movieslens興趣網(wǎng)絡(luò)包括943個(gè)用戶(hù)對(duì)I682個(gè)電影的電影的50000條評(píng)價(jià)進(jìn)行模型訓(xùn)練,使用其他用戶(hù)的l000條進(jìn)行驗(yàn)證測(cè)試.算法l實(shí)驗(yàn)結(jié)果見(jiàn)表1.表1不同參數(shù)下模型錯(cuò)誤邊的數(shù)目參數(shù)a的值參數(shù)b的值參數(shù)lr$的值多余的邊數(shù)缺失的邊數(shù)試集合中的時(shí)候,表明該預(yù)測(cè)是正確的;當(dāng)用戶(hù)的興趣點(diǎn)在推薦集合中,但是不在測(cè)試集合中的時(shí)候,表明該預(yù)測(cè)是錯(cuò)誤的:當(dāng)用戶(hù)的興趣點(diǎn)不在推薦集合中,但是卻在測(cè)試集合中,表明該預(yù)測(cè)也是錯(cuò)誤的.本文采用經(jīng)典最短路徑算法與本文提出的改進(jìn)的最短路徑算

11、法進(jìn)行比較,為簡(jiǎn)化實(shí)驗(yàn),本文采用全樣本空間搜索方法,沒(méi)有限定某一聚類(lèi)子空間,對(duì)算法的執(zhí)行沒(méi)有影響.其精確度和時(shí)間分析如圖l和圖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)整數(shù)選擇合適的情況下,例如本文中當(dāng)參數(shù)a,b和m值分別取0.4,0.6,100和0.3,0.7,200時(shí),算法具有較好的精度.從圖1的實(shí)驗(yàn)結(jié)果可以看出,改進(jìn)的最短路徑算法可圖1兩種算法的精確度比較研究與湃發(fā)測(cè)試數(shù)據(jù)(條)圖2兩種算法的時(shí)間復(fù)雜度比較以正確推薦用戶(hù)基于位置興趣

12、結(jié)點(diǎn),并較經(jīng)典的最短路徑算法具有一定程度提升,其準(zhǔn)確率根據(jù)測(cè)試集合樣本數(shù)目的不同會(huì)有小的波動(dòng),其準(zhǔn)確率基本在80%左右,可以滿(mǎn)足目前商務(wù)應(yīng)用需求.從圖2可以看出,改進(jìn)的最短路徑數(shù)量的增加變得尤為明顯,當(dāng)樣本接近1000個(gè)時(shí),經(jīng)典最短路徑算法等待時(shí)間較長(zhǎng).6結(jié)束語(yǔ)本文引入了一種小世界網(wǎng)絡(luò)模型用于用戶(hù)基于位置用推薦度計(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ù)位置行為興趣模型能夠很好地描述

13、用戶(hù)基于位置的興趣和意愿,算法在結(jié)果精度和計(jì)算時(shí)間上都具有良好的性能.參考文獻(xiàn)1JosephACazier,BenjaminBMShao,RobertDStLouis.Sharinginformationandbuildingtrustthroughvaluecongruence.InformationSystemFront.2o07(9):5155292CulnanMJ.MappingtheIntellectualStructureofMIS,19801985:acocitationanalysis.MISQuarterly,1987,11(3):341N353worldnetworks.N

14、ature,1998intelligentinformationsystems,2003,20(2):131160worldfile-sharingConferenceonElectricalandComputerEngineering,2005網(wǎng)絡(luò)拓?fù)溲芯烤C述.控制與決策,2010,25(12):1761l768蓋網(wǎng)絡(luò).計(jì)算機(jī),2010,33(9):15411547InterestModelforLocationoftheUserBehaviorZhangShaozhong,YuDongyun(CollegeofElectronicsandInformation,ZhejiangWanliU

15、niversity,Ningbo315100,China)AbstraetThepaperintroducesasmallworldnetworkmodeltoanalyzeuserbehaviorcharacteristicsandfindthebehavioroftheuserattributesandlocationbetweennodesandlookattheuserlocationasaroot.Itlooksatthelocationoftheuser'sinterestinresourcesasnodesandthismethodestablishedbythelocationof