Platform For AI：SimRank++相似性計算演算法

演算法簡介

SimRank演算法是一種用于衡量結構上下文中個體相似性的方法，其基本思想是：如果兩個對象a和b分別與另外兩個對象c和d關聯，且已知c與d是相似的，則a與b也是相似的；並且任意節點與其自身擁有最大的相似性值為1。SimRank演算法的主要出發點是利用已有個體的相似性來推算其他與之有關聯個體的相似性。

SimRank演算法基於一個簡單和直觀的圖論模型，它把對象和對象之間的關係建模為一個有向圖G = (V, E)，其中V是有向圖的節點集合，代表應用領域中的所有對象；E是有向圖的邊的集合，表示對象間的關係。對於圖中的一個節點，與其所有入邊關聯的鄰節點集合（in-neighbors）記為，同時，其出邊對應的鄰節點集合（out-neighbors）集合記為。用表示對象和對象之間的相似性，其計算公式為：

從該計算公式可以看出，個體, 的相似性取決於所有與, 相連節點的相似性。式中是一個常量衰減因子。

上述公式可以用矩陣的形式表示出來。假設S表示有向圖G的SimRank分數矩陣，其中表示對象和之間的相似性分數； P表示G的串連矩陣，其中表示從頂點到頂點的邊數，則

用矩陣的符號表示，即為：

其中，矩陣表示按列歸一化的矩陣， 是的單位矩陣。 的作用是把矩陣 的主對角線元素設為1。

SimRank++演算法在SimRank演算法的基礎上引入一個新的函數表示二部圖中節點間的轉移機率：

從而，新的演算法迭代公式如下：

其中，和表示任意兩個查詢，和表示任意兩個廣告，因子和的定義如下：

對SimRank演算法進行上述兩個方面的擴充，即通過“權值”和“證據值”對原始計算結果進行校正，所得的新演算法就是SimRank++演算法。

SimRank++演算法由Antonellis等人於2008年專門針對贊助商廣告檢索領域的查詢重寫應用提出的。

在推薦系統中的應用

原始的SimRank++演算法是在計算廣告領域做Query Rewrite的，一般會用最近一段時間的累計點擊行為資料來計算Query-Query、Ad-Ad之間的相關性。

由於Query所表達的查詢意圖短期內能夠保持穩定，所以用多天的行為資料來計算相似性是合理的。

在推薦系統中，沒有意圖明確的Query資料，一般用User-Item的點擊或其他行為二部圖作為SimRank++演算法的輸入。

在沒有Query相關性的限制下，使用者在推薦情境的行為意圖相對來說不是很明確，同一使用者在同一時期可能會有多個興趣，並且使用者的興趣也會隨時間發生演化。

另一方面，使用者的量級通常比Query的量級大很多，從百萬到數十億不等，這給SimRank++演算法的實現帶來了不小的挑戰。

基於以上原因，我們推薦使用Session-Based的行為二部圖計算item-item的相似性。因為在同一個session內使用者的興趣點比較集中，一般不會分手到多個類目的item上。在沒有明確session id埋點的情境，可以使用 concat（user_id, date） 作為session_id。

增量計算

由於session id的量級非常大，為了計算的可行性，不推薦合并多天的資料作為演算法輸入。

由此帶來的覆蓋率問題，我們提出了增量計算的方案。即SimRank++演算法工具包會保留多天的item-item相似性資料，計算第T天的相似性時使用T-1天的物品相似性初始化item-item相似性矩陣。工具包不會保留session與session之間的相似性資料。

最終，累加多天的物品相似性分數作為最終的i2i相似性分 。

其中， 是一個折扣因子，即過去的相似性分累加到當前時刻時需要打一個折扣，時間越久折扣越大。

注意：我們不保證多天累加的相似性分數 ，如有需要請自行歸一化。

改進點1：熱門打壓

在推薦情境很容易發生"哈利傳輸速率"效應，即因為熱門item會得到更多的曝光機會，因而演算法在不加幹預時很可能認為熱門item與很多其他item之間都存在相似關係，這樣會導致"富者越富"的馬太效應。為了緩解這一問題，本SimRank演算法工具包引入了一個熱門打壓機制。

具體來說，我們首先從輸入的行為二部圖中匯總item對應的邊的權重（求和），以便發現熱門的item。然後，對Item的熱度（記為 ）做一個z-score變換：

接著，再把 轉換為範圍在（0, 1） 區間內的一個單調遞減函數：

最後，用 乘上原來的邊的權重作為新的權重。這就相當於在隨機遊走時增加了往熱門item遊走的阻力。

改進點2：Reweight by prefer category

推薦情境下使用者的點擊行為可能有雜訊，比如誤點的情況；為了消除雜訊的幹擾，我們通過計算使用者對item類目的偏好來調整行為二部圖的權重。

給定一個使用者，其對類目 的偏好分如下：

Ta 對物品 的權重從原來的 調整為 ，其中物品 屬於類目 。

輸入輸出格式

輸入表（支援分區表）包含四列：

• 輸入表中不可有重複的 <user_id, item_id> 二元組，請預先合并權重

• 當使用category資料增強演算法效果時，該field為空白值的記錄將會被刪除；注意檢查category列是否存在空值

• 注意：需要控制同一Query對應的weight的方差在一定範圍內，太大會導致權重轉移矩陣的元素值為0，召回率嚴重下降。

  • 建議為weight列提前做好歸一化或者標準化，比如施加 "min-max", "z-score", "log", "sigmoid"等變換。

  • 也可以配置input_weight_normalizer參數。

• 合理設定二部圖邊的權重，會顯著提升演算法效果

  • 用ctr作為權重時容易引入雜訊資料，因為ctr高的record的曝光次數（pv）可能很低

  • 可以考慮用log(1+click)作為邊的權重

• 建議做好資料清洗，過濾掉一些雜訊資料

  • 給定一個Query，可以過濾掉click/sum(click) < threshold的資料；例如，threshold=3e-5

Item相似性（i2i）輸出表格式（支援分區列）：

備忘：$$score\in (0,1)$$、cumulative_score 沒有做歸一化

Query相似性（q2q）輸出表格式（支援分區列）：

提交任務

1. 下載 simrank_plus_plus-1.3.jar 演算法包。

2. 作為資源上傳到MaxCompute專案空間。

   

3. 在DataWorks上建立 ODPS MR 節點（ODPS SQL類型的節點可能會報錯），使用如下命令提交Job。

   --@resource_reference{"simrank_plus_plus-1.3.jar"}
   jar -resources simrank_plus_plus-1.3.jar
   -classpath simrank_plus_plus-1.3.jar
   com.aliyun.pai.simrank.SimRankDriver
   -project ${max_compute_project}
   -end_point http://service.cn-hangzhou.maxcompute.aliyun.com/api
   -access_id ${access_id}
   -access_key ${access_key}
   -input_table simrank_i2i_input
   -input_table_partition ds=${bizdate}
   -output_table simrank_i2i_output
   -output_table_partition ds=${bizdate}
   -init_partition ds=${yesterday}
   -session_column device_id
   -item_column item_id
   -category_column cate_lv3_id
   -num_matmul_reducer 2000
   ;

參數說明

搜尋情境，如Query Rewrite，可以把anti_popular置為false；推薦情境則置為true。

案例分析

某搜尋情境，輸入資料約1700萬，query量級為120萬，item量級為150萬，使用如下參數跑通整個流程耗時約87分鐘。

--@resource_reference{"simrank_plus_plus-1.0.jar"}
jar -resources simrank_plus_plus-1.0.jar
-classpath simrank_plus_plus-1.0.jar
com.aliyun.pai.simrank.SimRankDriver
-project ${project}
-end_point http://service.cn-shanghai.maxcompute.aliyun.com/api
-access_id ${access_id}
-access_key ${access_key}
-input_table ${input_table}
-input_table_partition dt=20240512
-output_table simrank_i2i_score
-output_table_partition dt=20240512
-session_output_table simrank_q2q_score
-session_output_table_partition dt=20240512
-output_table_lifecycle 7
-session_column query_word
-item_column item_id
-category_column category
-anti_popular false
-num_matmul_reducer 2000
-num_evidence_reducer1 1000
-num_evidence_reducer2 200

參考資料

• 一文說盡協同過濾演算法中的相似性計算

• SimRank++演算法原理解析