[發明專利]基于單源SimRank的協同過濾推薦方法

有效

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

本發明公開了一種基于單源SimRank的協同過濾推薦方法，包括：將待推薦用戶、用戶以及用戶間的關系轉換為圖結構，根據從源節點u出發的隨機游走經過l步到達節點w并停止的概率π_l(u，w)、從節點w出發的兩條隨機游走在行走過程中不再相遇的概率η(w)以及從節點w出發的反向游走經過l步到達節點v并停止的概率π_l(v，w)來進行節點u、v之間的SimRank相似度的估計，重復執行相似度的估計，直至完成圖結構中所有節點與源節點u之間的估計；根據估計結果，找到與待推薦節點相似度最高的前k個節點；獲取前k個節點的行為信息，將行為信息整合推送給源節點u。本實施例提供的基于單源SimRank的協同過濾推薦方法，降低了時間復雜度，滿足實時推薦、交互查詢的需求。

技術領域

本發明是關于協同過濾推薦，特別是關于一種基于單源SimRank的協同過濾推薦方法。

背景技術

推薦系統作為電子商務、社交網絡分析、個性化廣告投放、用戶興趣推薦等多個領域的核心技術，在互聯網發展的浪潮中重要性日益凸顯。

根據已有的歷史數據，分析用戶的興趣和需求，將其感興趣的信息、產品、服務等推薦給用戶的個性化信息系統稱為推薦系統。根據推薦算法的不同，我們可以將其劃分為基于協同過濾的推薦、基于內容的推薦、混合推薦三種。其中，基于協同過濾的推薦由于不需預先獲得用戶或物品的特征數據，僅依賴于用戶的歷史行為對用戶進行建模，有很強的可移植性，得到了人們的廣泛使用。具體的，在面向社交網絡的推薦系統中，可以根據已有的好友關系，為指定用戶推薦與其相似程度較高的用戶，還可以將相似用戶喜歡的商品推薦給目標用戶，以擴展推薦系統的適用場景，提升推薦系統的魯棒性和可移植性。

在協同過濾推薦方法的執行過程中，需要進行圖節點相似度的計算和比較。如何準確地定義圖節點的相似度并且能對之進行高效的計算，一直是研究者們持續探索的問題。為了方便具體問題的抽象和定義，我們將社交網絡轉化為圖論中的圖結構G＝(V,E)，其中，V、E分別表示圖結構上的所有節點、邊組成的集合，對應于實際社交網絡中的用戶群體和用戶之間的好友關系。因此，可以將尋找社交網絡上相似用戶的實際問題轉化為計算圖結構上節點之間相似度的抽象問題。

在節點相似度定義方法中，SimRank相似度作為圖節點相似度計算領域的一種重要算法，因為其定義完全基于圖結構、不依賴于其他額外特征，并借助迭代的形式整合了節點多階鄰居的環境信息等優良特性，引起了人們的重點關注。下面為SimRank的基本定義式：

基于此，本申請的發明人發現，由于SimRank迭代定義的性質，直接計算單源節點的SimRank需要耗費O(td²n²)的時間復雜度和O(n²)的空間復雜度，這里t表示迭代次數，d表示圖上節點的平均度數，n表示圖節點的個數。

而隨著大數據時代的到來，現實生活中產生的圖結構規模越來越大，比如上億用戶的微信、推特(Twitter)形成的社交網絡等，根據原始定義計算SimRank的時間復雜度太高，很難在有效時間內計算出大圖上的單源SimRank的結果，無法滿足實時推薦、交互查詢的需求。

公開于該背景技術部分的信息僅僅旨在增加對本發明的總體背景的理解，而不應當被視為承認或以任何形式暗示該信息構成已為本領域一般技術人員所公知的現有技術。

發明內容

本發明的目的在于提供一種基于單源SimRank的協同過濾推薦方法，其能夠在有效時間內計算出大圖的單源SimRank的結果，滿足實時推薦、交互查詢的需求。