[發明專利]基于Spark的節點相似度計算方法、裝置及終端

有效

• 申請號: 201810811936.0
• 申請日: 2018-07-23
• 公開（公告）號: CN110751161B
• 公開（公告）日: 2023-08-22
• 發明（設計）人: 魏紅亮
• 申請（專利權）人: 阿里巴巴（中國）有限公司
• 主分類號: G06F18/22
• 分類號: G06F18/22
• 代理公司: 上海知錦知識產權代理事務所(特殊普通合伙) 31327
• 代理人: 潘彥君

本發明實施例提供一種基于Spark的節點相似度計算方法、裝置及終端，方法包括：獲取待處理的二部圖中的節點數據，對節點數據進行序列化處理；根據處理后的節點數據生成概率轉移矩陣和相似度矩陣；對概率轉移矩陣和相似度矩陣進行多級自適應分片迭代處理，獲得中間結果矩陣；將中間結果矩陣與預先設置的衰減系數做乘積運算，獲得最終結果矩陣；根據最終結果矩陣獲得節點之間的相似度。本發明提供的技術方案，具體為一種基于Spark的大規模矩陣乘法算法，能夠對數據進行多級自適應分片，并可以將Simrank計算公式過程拆分為兩部分，降低了計算規模和中間數據存儲規模；從而能夠高效地計算億級別節點之間的相似度。

技術領域

本發明涉及數據處理技術領域，尤其涉及一種基于Spark的節點相似度計算方法、裝置及終端。

背景技術

Simrank是一種用于計算圖中節點之間相似度的技術，如在二部圖中，圖中有兩種類型的節點，同一種類型的節點之間沒有邊相連，兩種不同類型的節點之間才有邊相連，Simrank算法可以計算同一種類型節點之間的相似度。如電商場景的個性化推薦中，用戶集合與商品集合的關系可以抽象為二部圖，用戶點擊過商品，則該用戶與點擊的商品之間可以有邊相連，通過Simrank可以計算二部圖中用戶之間或者商品之間的相似度；在搜索廣告場景中，用戶搜索并點擊過廣告，用戶使用過的檢索內容(稱作query)的集合與廣告(稱作ad)的集合的關系可以抽象為二部圖，指定的query檢索得到的ad列表中有ad被點擊，則指定的query與被點擊的ad之間可以有邊相連，通過Simrank可以計算二部圖中query之間或者ad之間的相似度。Simrank這種基于圖的結構關系計算節點間的相似度，以及相似度傳播的特點，常常被應用在推薦、搜索廣告的召回階段，為后續排序過程挖掘出候選項。

對于應用Simrank算法計算二部圖中同一種類型節點間的相似度而言，當面對大規模的數據量，如億級別數量的節點間相似度時，會發生數據異構、時間和空間太大等問題，在計算過程中，會出現計算和存儲開銷大導致無法計算或計算耗時的問題：

1)以搜索廣告中的query-ad構建的二部圖為例，query是用戶輸入的字符串，可能出現中文、英文、可見/不可見字符、數字等，而且長短不一；

2)Simrank的時間復雜度為O(n⁴)，當二部圖中一種類型的節點數量為10⁶量級(百萬)時，時間復雜度非常高；盡管并不是同一種類型節點，任何兩個之間都相似，都需要計算相似度。不過，Simrank基于整個圖的結構關系計算節點間的相似度，并且兩個節點之間即時沒有共同連接的節點，因為相似度傳播的特點，也可能產生相似度。因此，在計算過程中，需要計算節點間相似度。

3)Simrank的空間復雜度為O(n²)，當二部圖中一種類型的節點數量為10⁶量級(百萬)時，最終會得到10¹²量級(千億)的相似對，空間復雜度非常高。而且，在迭代計算Simrank時，本輪迭代計算需要使用上一輪計算的結果，隨著迭代輪數增加，每輪會有越來越多的節點間產生相似度，因此，需要存儲這些大量的數據，并且，需要快速從這些大量的相似對中檢索出指定的節點對在上一輪計算的相似度結果。計算過程中，非常容易發生單點內存溢出的問題，以及計算耗時久的問題。

目前實現Simrank的方法，包括：普通的計算方法、基于MapReduce模型的計算方法、空間換時間的方法、近似的方法和普通的矩陣乘法，這些方法在實現Simrank時存在一定的局限性：

1)普通的計算方法，即按照Simrank公式步驟計算，這種計算方式不適合分布式計算，只能在一臺計算機上計算，在面臨大數據量時容易發生內存溢出；

2)基于MapReduce模型的計算方法，其中，MapReduce模型為一個開源的大數據分布式并行計算框架，計算過程分為Map階段和Reduce階段；Map階段得到的數據項在數據量非常大的情況下，在Reduce階段按照key求和時，會出現讀取和存儲數據，以及網絡傳輸開銷非常大，任務容易失?。?/p>