鬼佬大哥大
  • / 12
  • 下載費用:30 金幣  

一種基于轉發鏈相似度的用戶關注對象推薦計算方法.pdf

摘要
申請專利號:

CN201510331056.X

申請日:

2015.06.15

公開號:

CN105069003A

公開日:

2015.11.18

當前法律狀態:

授權

有效性:

有權

法律詳情: 授權|||實質審查的生效IPC(主分類):G06F 17/30申請日:20150615|||公開
IPC分類號: G06F17/30; G06Q50/00(2012.01)I 主分類號: G06F17/30
申請人: 北京工業大學
發明人: 毋立芳; 荊羽晨; 王丹; 馮澤猛; 張加楠
地址: 100124北京市朝陽區平樂園100號
優先權:
專利代理機構: 北京思海天達知識產權代理有限公司11203 代理人: 劉萍
PDF完整版下載: PDF下載
法律狀態
申請(專利)號:

CN201510331056.X

授權公告號:

||||||

法律狀態公告日:

2018.06.29|||2015.12.16|||2015.11.18

法律狀態類型:

授權|||實質審查的生效|||公開

摘要

一種基于轉發鏈相似度的用戶關注對象推薦計算方法,涉及網絡分析和推薦系統領域。本發明獲取收藏條目到原始收藏條目的數據,以轉發的收藏條目的創建用戶來代表該轉發鏈上的結點;引入最小操作代價函數作為相似度計算的初步輸入;結合轉發鏈長度以及轉發鏈的信息流向根據最小操作代價值計算轉發鏈間的相似度;根據轉發鏈之間相同用戶節點產生候選的推薦用戶,利用目標用戶轉發鏈集合中轉發鏈數據兩兩之間的相似度,結合轉發鏈路徑長度以及轉發鏈上的候選用戶密度對候選推薦用戶目標計算推薦權重值;對候選用戶權重值排序產生推薦結果。本發明利用用戶的轉發行為及轉發對應的關系數據進行用戶的潛在關注對象挖掘,實現用戶關注推薦。

權利要求書

1.一種基于轉發鏈相似度的用戶關注對象推薦計算方法,其特征在于包括:A、根據目標用戶的所有收藏條目進行轉發數據的采集,根據收藏條目中轉發自何人的數據,獲取每一條收藏條目到原始收藏條目的數據;從當前收藏條目開始向父級爬取數據;根據轉發自何處這一數據作為指導,一直追溯到原始收藏條目位置;在追溯過程中的每一個結點都是原始收藏條目的一個拷貝,而由這些結點構成了一條鏈狀的路徑圖,稱之為轉發鏈;每個轉發鏈均由一個包含若干收藏條目的集合構成;以每個轉發的收藏條目的創建用戶來代表該轉發鏈上的一個結點;B、對于目標用戶的所有轉發鏈數據構成的集合,取集合中的所有兩兩轉發鏈組合,對組合求取轉發鏈相似度值;C、根據B步計算的相似度計算值獲取候選的推薦對象用戶,并計算每一個候選的推薦對象的權重值;D、根據步驟C中計算得到的候選的推薦對象權重值大小,將候選的推薦對象用戶進行降序排序,權重值越大的用戶越靠前,也越可能被推薦。2.如權利要求1所述的方法,其特征在于,所述步驟B具體包括:B1、定義目標用戶轉發鏈集合中轉發鏈數據的具體表達式;將一條轉發鏈數據以轉發鏈上各個節點收藏條目的創建用戶的編號為標記,以鏈表的形式表示為R={p1,p2,p3,…,pn|<pi,pi+1>∈E,p1∈S};n表示轉發鏈的長度,pn為當前的收藏條目,E為轉發關系集合,S為原始收藏條目集合;將每一條轉發鏈數據的最后兩個結點pn-1和pn去除;B2、計算轉發鏈之間轉換的最小操作代價;設在轉發鏈結構的鏈表中存在插入一個結點、刪除一個結點和以另一個結點替換當前結點這三種基本操作,每個操作所要花費的代價均為1;則長度為k的轉發鏈Ri通過三種基本操作變為長度為l的轉發鏈Rj所需的最小操作代價Cost(Ri,Rj)通過回溯搜索算法計算得到;B3、根據上一步的計算結果Cost(Ri,Rj),計算轉發鏈Ri和轉發鏈Rj的相似度sim(Ri,Rj);相似度sim(Ri,Rj)的計算公式如下:max{k,l}表示求取k和l中的最大值。3.如權利要求1所述的方法,其特征在于,所述步驟C具體包括:C1、確定候選的推薦對象用戶集合;C2、根據轉發鏈相似度計算結果給每一條轉發鏈上的候選推薦對象計算權重值;C3、加和所有轉發鏈上的權重值計算結果。4.如權利要求3所述的方法,其特征在于,所述步驟C1具體包括:C11、設目標用戶u的所有轉發鏈集合為Tu={R1,R2,…,Rn},其中n表示目標用戶所包含的所有收藏條目個數;根據步驟B1中對轉發鏈數據的定義,轉發鏈Ri和轉發鏈Rj上的共同用戶集合Si,j由Ri∩Rj得到,設Si,j表示為m表示Si,j中用戶的總數;C12、設Di為轉發鏈Ri上所有候選的推薦對象用戶的集合,則Di由公式計算,其中n表示目標用戶所包含的所有收藏條目個數,∪為求并集符號;C13、對目標用戶所有轉發鏈集合Tu上候選的推薦對象用戶構成的集合Θ,則由如下公式計算:其中n表示目標用戶所包含的所有收藏條目個數,∪為求并集符號。5.如權利要求3所述的方法,其特征在于,所述步驟C2具體包括:C21、給所有的存在與其它轉發鏈相似度不為0的轉發鏈1單位的分配權重;C22、根據步驟B中所得的轉發鏈相似度計算結果,轉發鏈Ri上的任意一個候選的推薦對象ui所得到的分配權重值weight(ui)為其中j為枚舉用的臨時變量,n表示目標用戶所包含的所有收藏條目個數,Si,j表示轉發鏈Ri和轉發鏈Rj上的共同用戶集合;C23、反復執行步驟C22直到所有轉發鏈上所有的候選的推薦對象所得的分配權重值全部被單獨計算完畢。6.如權利要求3所述的方法,其特征在于,所述步驟C3具體包括:C31、設I(ui,Di)為判定函數,如果ui∈Di則函數返回值為1,否則為0;C32、根據步驟C2中計算得到的每個轉發鏈上候選推薦對象所得的權重值,進行求和操作,得到全體候選用戶集合Θ中每個用戶的最終權重值:其中,Θ表示目標用戶所有轉發鏈上候選的推薦對象用戶構成的集合,u表示等待計算的候選用戶對象,ui表示當前等待計算的候選對象u在第i條轉發鏈上環境下的標記,weight(ui)表示當前等待計算的候選對象在第i條轉發鏈上所得到的分配權重值,n表示目標用戶所包含的所有收藏條目個數;至此,所有候選的推薦對象所得的權重值全部計算完畢。

說明書

一種基于轉發鏈相似度的用戶關注對象推薦計算方法

技術領域

本發明涉及社交網絡分析和推薦系統領域,具體涉及一種基于轉發鏈相似度的用戶關注對象推薦計算方法的研究及實現。

背景技術

新型社交策展網絡中存在用戶的關注與被關注關系。針對社交網絡的用戶關注推薦算法很多,大都利用用戶參與過的內容記錄,使用內容、標簽等比對手段發現用戶的潛在興趣以及關注對象。推薦系統中用戶隱私的保護一直以來是一個重要問題。如何在盡可能少使用用戶隱私數據的前提下充分挖掘用戶的興趣點,為用戶提供用戶關注推薦。

在社交策展網絡中,用戶的每一個公開的收藏條目均可以被其他用戶進行轉發。轉發行為在一定程度上體現了用戶對被轉內容的喜好程度,同時轉發的路徑也表現了用戶的信息來源以及信息流向。大量針對社交網絡的數據挖掘相關研究針對其中的轉發特性而開展。研究者通過對微博、Twitter上博文轉發關系、轉發路徑以及用戶參與頻數的分析,來進行如:話題提取、社區分割、熱點預測等方面的工作。針對轉發關系的分析研究,主要通過用戶的個人屬性,轉發微博的標簽、關鍵詞,各結點轉發量等數據進行分析。通過如TD-IDF、主題建模等方法對文本數據進行處理,通過圖論算法對網絡結構進行提取化簡,得到所需的特征。而事實上,就轉發路徑上看,一個信息的流向也包含了用戶的興趣偏好,并且,不同轉發鏈路徑上重合節點的密度關系到用戶對每個結點的感興趣程度。單個用戶的收藏條目對應的轉發關系包含的相關數據從結構、信息流向、重合節點密度上都存在許多值得研究的特性。如何從收藏條目的轉發路徑上獲取用戶潛在的關注對象就成了研究的要點。

發明內容

本發明主要解決如何利用用戶的轉發行為以及轉發對應的關系數據進行用戶的潛在關注對象挖掘,實現用戶關注推薦。

為了實現上述問題,本發明提供了一種基于轉發鏈相似度的用戶關注對象推薦計算方法。該方法包括:

A、根據目標用戶的所有收藏條目進行轉發數據的采集,根據收藏條目中轉發自何人的數據,獲取每一條收藏條目到原始收藏條目的數據。從當前收藏條目開始向父級爬取數據。根據轉發自何處這一數據作為指導,一直追溯到原始收藏條目位置。在追溯過程中的每一個結點都是原始收藏條目的一個拷貝,而由這些結點構成了一條鏈狀的路徑圖,稱之為轉發鏈。每個轉發鏈均由一個包含若干收藏條目的集合構成。以每個轉發的收藏條目的創建用戶來代表該轉發鏈上的一個結點。

B、對于目標用戶的所有轉發鏈數據構成的集合,取集合中的所有兩兩轉發鏈組合,對組合求取轉發鏈相似度值。

進一步地,所述步驟B具體包括:

B1、定義目標用戶轉發鏈集合中轉發鏈數據的具體表達式。設pn為當前的收藏條目,E為轉發關系集合,S為原始收藏條目集合。將一條轉發鏈數據以轉發鏈上各個節點收藏條目的創建用戶的編號為標記,以鏈表的形式表示為R={p1,p2,p3,…,pn|〈pi,pi+1〉∈E,p1∈S}。設Ri,p表示轉發鏈i的第p個結點位置上用戶的編號。由于對目標用戶的推薦不需要考慮目標用戶自身和目標用戶已經關注的用戶,所以,在計算時將每一條轉發鏈數據的最后兩個結點pn-1和pn去除。

B2、計算轉發鏈之間轉換的最小操作代價。設在轉發鏈結構的鏈表中存在插入一個結點、刪除一個結點和以另一個結點替換當前結點這三種基本操作,每個操作所要花費的代價均為1。則長度為k的轉發鏈Ri通過三種基本操作變為長度為l的轉發鏈Rj所需的最小操作代價Cost(Ri,Rj)通過回溯搜索算法計算得到。

B3、根據上一步的計算結果Cost(Ri,Rj),計算轉發鏈Ri和轉發鏈Rj的相似度sim(Ri,Rj)。相似度sim(Ri,Rj)的計算公式如下:

max{k,l}表示求取k和l中的最大值。

至此對于目標用戶的所有轉發鏈數據集合中任意兩個轉發鏈都得到一個相似度計算值sim(Ri,Rj)。

C、根據B步計算的相似度計算值sim(Ri,Rj)獲取候選的推薦對象用戶,并計算每一個候選的推薦對象的權重值。

進一步地,所述步驟C具體包括:

C1、確定候選的推薦對象用戶集合。

C2、根據轉發鏈相似度計算結果給每一條轉發鏈上的候選推薦對象計算權重值。

C3、加和所有轉發鏈上的權重值計算結果

進一步地,所述步驟C1具體包括:

C11、設目標用戶u的所有轉發鏈集合為Tu={R1,R2,…,Rn},其中n表示目標用戶所包含的所有收藏條目個數。根據步驟B1中對轉發鏈數據的定義,轉發鏈Ri和轉發鏈Rj上的共同用戶集合Si,j由Ri∩Rj得到,設Si,j表示為 S i , j = { u 1 i j , u 2 i j , ... , u m i j } , ]]>m表示Si,j中用戶的總數。

C12、設目標用戶轉發鏈集合Tu中所有相似度不為0的轉發鏈中所有重復出現在2個或2個以上轉發鏈數據中的用戶編號定義為候選的推薦對象用戶。設Di為轉發鏈Ri上所有候選的推薦對象用戶的集合,則Di由公式計算,其中n表示目標用戶所包含的所有收藏條目個數,∪為求并集符號。

C14、對目標用戶所有轉發鏈上候選的推薦對象用戶構成的集合Θ,則由如下公式計算:其中n表示目標用戶所包含的所有收藏條目個數,∪為求并集符號。

所述步驟C2具體包括:

C21、給所有的存在與其它轉發鏈相似度不為0的轉發鏈1單位的分配權重。

C22、根據步驟B中所得的轉發鏈相似度計算結果,轉發鏈Ri上第k個候選的推薦對象ui所得到的分配權重值weight(ui)為 w e i g h t ( u i ) = Σ j = 1 n s i m ( R i , R j ) × | s i , j { u i } | | s i , j | , ]]>其中j為枚舉用的臨時變量,n表示目標用戶所包含的所有收藏條目個數,Si,j表示轉發鏈Ri和轉發鏈Rj上的共同用戶集合。

C23、反復執行步驟C22直到所有轉發鏈上所有的候選的推薦對象所得的分配權重值全部被單獨計算完畢。

所述步驟C3具體包括:

C31、設I(ui,Di)為判定函數,如果ui∈Di則函數返回值為1,否則為0。

C32、根據步驟C2中計算得到的每個轉發鏈上候選推薦對象所得的權重值,進行求和操作,得到全體候選用戶集合Θ中每個用戶的最終權重值:

r u = 1 2 Σ i = 1 n w e i g h t ( u i ) × I ( u i , D i ) ]]>其中ui∈Θ

其中,Θ表示目標用戶所有轉發鏈上候選的推薦對象用戶構成的集合,u表示等待計算的候選用戶對象,ui表示當前等待計算的候選對象在第i條轉發鏈上環境下的標記,weight(ui)表示當前等待計算的候選對象在第i條轉發鏈上所得到的分配權重值,n表示目標用戶所包含的所有收藏條目個數。

至此,所有候選的推薦對象所得的權重值全部計算完畢。

D、根據步驟C中計算得到的候選的推薦對象權重值大小,將候選的推薦對象用戶進行降序排序,權重值越大的用戶越靠前,也越可能被推薦。

附圖說明

圖1為實施例一中步驟B3所有轉發鏈的相似度計算可視化結果圖

圖2為實施例一中推薦產生示意圖

圖3為實施例一中轉發鏈示意圖

圖4為實施例一的推薦結果在實驗測試集上與對比算法的查準率、查全率和F1指數結果對比圖

具體實施方式

下面將結合附圖及實施例對本發明的技術方案進行更詳細的說明。

本實施例是針對某社交策展網絡真實數據進行的,例中的用戶為網絡中的真實用戶,包含有69個收藏條目以及收藏條目對應的轉發鏈,有214個關注對象。

A、讀入用戶的關注對象數據和收藏條目轉發鏈數據。

B、提取轉發鏈集合上的用戶編號,并計算轉發鏈之間的相似度值。

所述步驟B具體包括:

B1、將一條轉發鏈數據以轉發鏈上各個節點收藏條目的創建用戶的編號為標記,以鏈表的形式表示為R={p1,p2,p3,…,pn|〈pi,pi+1〉∈E,p1∈S}。設Ri,p表示轉發鏈i的第p個結點位置上用戶的編號,將每一條轉發鏈數據的最后兩個結點pn-1和pn去除。本實例中目標用戶的第一條轉發鏈可以用用戶編號表示為{8089456,6589657,889106}。

B2、根據目標用戶的轉發鏈數據,計算轉發鏈之間轉換的最小操作代價,在本實例中,目標用戶的第四條的數據表示為{9550825,6308943,6363423,1265655,6589657,8889106},第五條轉發鏈的數據表示為{9550825,10138913,11219171,286421,305714,57678,853734,960710,485684889716,889106},根據B1步驟去除最后兩個結點的數據后,第一條轉發鏈與第四條轉發鏈之間的最小操作代價Cost(R1,R4)的計算結果為4,而第四條和第五條轉發鏈的最小操作代價Cost(R4,R5)計算結果為8。

B3、根據上一步的計算結果,計算目標用戶的各轉發鏈之間的兩兩相似度sim(Ri,Rj),在本實例中,目標用戶第一條轉發鏈與第四條轉發鏈的相似度sim(R1,R4)計算結果為0,第四條轉發鏈與第五條轉發鏈的相似度sim(R4,R5)計算結果為1/9。

至此,算法得到目標用戶所有轉發鏈兩兩之間的相似度計算結果,

對相似度計算結果進行可視化分析可以得到對稱的矩陣可視化熱度圖,通過可視化熱度圖本實例中用戶的操作中信息流向的聚集行為得到直觀體現。在此給出實施例中的可視化熱度圖結果說明,圖中每一個方形色塊代表一個轉發鏈對,對應的橫縱坐標表示轉發鏈的編號值,當相似度為0時色塊顏色為純紅色,當相似度越接近于1時,色塊由紅變黃逐漸變白,當相似度為1時,色塊顏色為純白,表明當前兩條轉發鏈存在完全一致的信息流向。由于專利不收彩圖,所以只能用灰度圖來表示。

C、根據B步計算的相似度計算值sim(Ri,Rj)獲取候選的推薦對象用戶,并計算每一個候選的推薦對象的權重值。

進一步地,所述步驟C具體包括:

C1、確定候選的推薦對象用戶集合。

C2、根據轉發鏈相似度計算結果給每一條轉發鏈上的候選推薦對象計算權重值。

C3、加和所有轉發鏈上的權重值計算結果

進一步地,所述步驟C1具體包括:

C11、設目標用戶u的所有轉發鏈集合為Uu={R1,R2,…,Rn}。根據B1中對轉發鏈數據的定義,轉發鏈Ri和轉發鏈Rj上的共同用戶集合Si,j可以由Ri∩Rj得到,設Si,j表示為 S i , j = { u 1 i j , u 2 i j , ... , u m i j } . ]]>

C12、設目標用戶轉發鏈集合Uu中所有相似度不為0的轉發鏈中所有重復出現在2個或以上轉發鏈數據中的用戶編號定義為候選的推薦對象用戶。設Di為轉發鏈Ri上所有候選的推薦對象用戶的集合,則Di可由如下公式計算:

D i = j = 1 n s i , j ]]>

C14、對目標用戶所有轉發鏈上候選的推薦對象用戶構成的集合Θ,則可以由如下公式計算:

Θ = i = 1 n D i ]]>

所述步驟C2具體包括:

C21、給所有的存在與其它轉發鏈相似度不為0的轉發鏈1單位的分配權重。

C22、根據步驟B中所得的轉發鏈相似度計算結果,轉發鏈Ri上的任意一個候選的推薦對象ui所得到的分配權重值為 w e i g h t ( u i ) = Σ j = 1 n s i m ( R i , R j ) × ]]> | s i , j { u i } | | s i , j | . ]]>

C23、反復執行步驟C22直到所有轉發鏈上所有的候選的推薦對象所得的分配權重值全部被單獨計算完畢。

所述步驟C3具體包括:

C31、設I(ui,Di)為判定函數,如果ui∈Di則函數返回值為1,否則為0。

C32、根據步驟C2中計算得到的每個轉發鏈上候選推薦對象所得的權重值,進行求和操作,得到全體候選用戶集合Θ中每個用戶的最終權重值,可由如下公式計算:

r u = 1 2 Σ i = 1 n w e i g h t ( u i ) × I ( u i , D i ) ]]>其中ui∈Θ

至此,所有候選的推薦對象所得的權重值全部計算完畢,所有候選的推薦對象獲得的權重值保存在數據記錄文件中。

D、根據步驟C中計算得到的候選的推薦對象權重值大小,將候選的推薦對象用戶進行降序排序,權重值越大的用戶越靠前,也越可能被推薦,根據推薦系統的具體需求產生前1、前5、前10等不同集合大小的推薦結果。在本實例中,前1的推薦結果為311860號用戶,對應的權重值為2.125992。前5的推薦結果為311860號用戶,對應的權重值為2.125992、19930號用戶,對應的權重值為0.9285714、788701號用戶,對應的權重值為0.8、6312241號用戶,對應的權重值為0.2、838588號用戶,對應的權重值為0.2。本算法與隨機猜測算法、根據操作頻數產生的流行度推薦算法從查準率、查全率和F1指數三個指標上進行對比,推薦效果取得了明顯的提升。

關 鍵 詞:
一種 基于 轉發 相似 用戶 關注 對象 推薦 計算方法
  專利查詢網所有資源均是用戶自行上傳分享,僅供網友學習交流,未經上傳用戶書面授權,請勿作他用。
關于本文
本文標題:一種基于轉發鏈相似度的用戶關注對象推薦計算方法.pdf
鏈接地址:http://www.wwszu.club/p-6386042.html
關于我們 - 網站聲明 - 網站地圖 - 資源地圖 - 友情鏈接 - 網站客服客服 - 聯系我們

[email protected] 2017-2018 zhuanlichaxun.net網站版權所有
經營許可證編號:粵ICP備17046363號-1 
 


收起
展開
鬼佬大哥大