[發(fā)明專利]基于單源SimRank的協(xié)同過濾推薦方法

有效

• 申請?zhí)枺?/td>: 201910577524.X
• 申請日: 2019-06-28
• 公開（公告）號: CN110287424B
• 公開（公告）日: 2021-07-20
• 發(fā)明（設(shè)計）人: 魏哲巍;何曉東;王涵之;蕭小奎;王思博;劉鈺;杜小勇
• 申請（專利權(quán)）人: 中國人民大學(xué)
• 主分類號: G06F16/9536
• 分類號: G06F16/9536
• 代理公司: 北京中譽威圣知識產(chǎn)權(quán)代理有限公司 11279
• 代理人: 周際;李秀琴

1.一種基于單源SimRank的協(xié)同過濾推薦方法，其特征在于，包括：

將待推薦用戶、用戶以及用戶間的關(guān)系轉(zhuǎn)換為圖結(jié)構(gòu)，其中，所述圖結(jié)構(gòu)中包括多個與所述用戶對應(yīng)的節(jié)點以及多條與所述用戶間的關(guān)系對應(yīng)的邊，所述邊包括出邊以及入邊，所述待推薦用戶為圖結(jié)構(gòu)中的源節(jié)點u；

根據(jù)從源節(jié)點u出發(fā)的隨機游走經(jīng)過l步到達節(jié)點w并停止的概率π_l(u,w)、從節(jié)點w出發(fā)的兩條隨機游走在行走過程中不再相遇的概率η(w)以及從節(jié)點w出發(fā)的反向游走經(jīng)過l步到達節(jié)點v并停止的概率π_l(v,w)來進行節(jié)點v與所述源節(jié)點u之間的SimRank相似度的估計s(u,v)，其中，隨機游走為以的概率隨機走向當前節(jié)點的一個入鄰居節(jié)點，以的概率停止在當前節(jié)點的游走，c為衰減系數(shù)，0≤c≤1，v為所述圖結(jié)構(gòu)中的任一節(jié)點；

重復(fù)執(zhí)行SimRank相似度的估計，直至完成圖結(jié)構(gòu)中所有節(jié)點與源節(jié)點u之間的SimRank相似度的估計；

根據(jù)SimRank相似度的估計結(jié)果，找到與所述待推薦節(jié)點相似度最高的前k個節(jié)點；

獲取所述前k個節(jié)點的行為信息，將所述行為信息整合推送給所述源節(jié)點u；

所述根據(jù)從源節(jié)點u出發(fā)的隨機游走經(jīng)過l步到達節(jié)點w并停止的概率π_l(u,w)、從節(jié)點w出發(fā)的兩條隨機游走在行走過程中不再相遇的概率η(w)以及從節(jié)點w出發(fā)的反向游走經(jīng)過l步到達節(jié)點v并停止的概率π_l(v,w)來進行節(jié)點v與所述源節(jié)點u之間的SimRank相似度的估計s(u,v)，包括：

計算(π_l(u,w)·η(w))的估計值；

判斷節(jié)點w是否為核心節(jié)點；

若是，則從預(yù)存的索引表中獲取所述核心節(jié)點的π_l(v,w)的估計值；

若否，則通過后向游走的方法動態(tài)計算π_l(v,w)的估計值，其中，所述后向游走指從當前節(jié)點出發(fā)以一定的概率分布走向當前節(jié)點的出鄰居；

根據(jù)公式一來進行節(jié)點v與所述源節(jié)點u之間的SimRank相似度的估計s(u,v)，所述公式一為：

其中，V為圖結(jié)構(gòu)上的所有節(jié)點組成的集合。

2.如權(quán)利要求1所述的協(xié)同過濾推薦方法，其特征在于，所述判斷節(jié)點w是否為核心節(jié)點之前，包括：

根據(jù)圖結(jié)構(gòu)中節(jié)點的佩奇排名，確定圖結(jié)構(gòu)中的核心節(jié)點，其中，所述核心節(jié)點是逆佩奇排名降序排名后處于前j₀位的節(jié)點，其中，j₀為整數(shù)且0≤j₀≤n，n為圖結(jié)構(gòu)中的節(jié)點數(shù)；

判斷是否滿足預(yù)設(shè)條件，若不滿足預(yù)設(shè)條件則從所述核心節(jié)點開始，沿出邊方向進行隨機游走；

若滿足預(yù)設(shè)條件，則停止隨機游走，并確定π_l(v,w)的估計值。

3.如權(quán)利要求2所述的協(xié)同過濾推薦方法，其特征在于，所述沿出邊方向進行隨機游走之后包括：

在進行隨機游走時，根據(jù)公式二更新從節(jié)點w出發(fā)的反向隨機游走經(jīng)過l+1步到達節(jié)點v′的殘余值r_l+1(v′,w)，所述公式二為：

其中，d_in(v′)表示節(jié)點v′的入度，v′為隨機選取的節(jié)點v的一個出鄰居節(jié)點，r_l(v,w)為從節(jié)點w出發(fā)的反向隨機游走經(jīng)過l步到達節(jié)點v的殘余值；

根據(jù)公式三更新在第l步隨機游走時到達節(jié)點v對應(yīng)的π_l(v,w)，所述公式三為：

4.如權(quán)利要求3所述的協(xié)同過濾推薦方法，其特征在于，所述預(yù)設(shè)條件包括：

圖結(jié)構(gòu)上的所有節(jié)點在進行了l步隨機游走到達節(jié)點v的殘余值r_l(v,w)均小于預(yù)設(shè)值r_max時。

5.如權(quán)利要求3所述的協(xié)同過濾推薦方法，其特征在于，所述若滿足預(yù)設(shè)條件，則停止隨機游走，并確定π_l(v,w)的值包括：

若滿足預(yù)設(shè)條件，則停止隨機游走；

將停止隨機游走時更新的π_l(v,w)的值存儲在索引表中。