用hadoop實作SimRank++算法(1)----權值轉移矩陣的計算

本文主要針對廣告檢索領域的查詢重寫應用，根據查詢-廣告點選二部圖，在mapreduce架構上實作simrank++算法，關于simrank++算法的背景和原理請參看前一篇文章《》。

simrank++的矩陣形式的計算公式為：

算法主要步驟如下：

step1: 計算權值矩陣，并擷取最大query編号和最大廣告編号；

step2: 以step1的輸出作為輸入，疊代計算simrank相似度。

step3: 計算證據矩陣，并用計算結果修正step2的輸出，計算出最終的經過歸一化的相似度分數。

step4: 把step3的輸出轉化為固定的格式，得到最終的相似度分數結果。

其中step2疊代計算simrank相似度分數比較複雜，由一系列的mapreduce作業組成。本文主要關注step1，即計算權值矩陣的計算。step2~4将在後續的文章中給出。

為了簡單起見，在我們的實作中，用點選次數作為邊的權值。一個更好的選擇是用廣告點選率(click through rate, ctr)作為權值，理由如下：某個廣告在q1下展示10000次，點選100次（ctr為0.01）；在q2下展示1000次，點選90次（ctr為0.09）；在q3下展示1000次，點選100次（ctr為0.1）；顯然q3和q2的相似度要比q3和q1的相似度要高，然而如果隻考慮點選次數，那麼算法會認為q3和q1的相似度比q3和q2的高。

期待的輸入資料的檔案格式：

1. query和廣告的點選關系資料檔案（以下記為qas檔案）的每一行的格式如下：

qas ^a queryid { ^a adid ^b clicknum}

其中，{ }表示内部的内容可以重複1次或多次，但至少一次；“qas”的辨別字元串；‘^a’是ascii碼為1的不可見字元；‘^b’是ascii碼為2的不可見字元。

2. 廣告和query的點選關系資料檔案（以下記為aqs檔案）的每一行的格式如下：

aqs ^a adid { ^a queryid ^b clicknum}

其中，{ }表示内部的内容可以重複1次或多次，但至少一次；“aqs”的辨別字元串；‘^a’是ascii碼為1的不可見字元；‘^b’是ascii碼為2的不可見字元。

上圖所示的查詢和廣告之間的點選關系對應的檔案格式如下：

權值矩陣元素的計算公式為：

可以看出， variance(a)的計算需要用到aqs檔案， normalize_weight(q,a)的計算需要用到qas檔案； variance(q)的計算需要用到qas檔案， normalize(q,a)的計算需要用到aqs檔案。進而，在計算w(a,q) 和 w(q,a)時都要用到aqs檔案和qas檔案，這使得mapreduce算法的設計比較困難。

考慮前面所述的一個簡單例子。”mapper”任務在處理qas檔案時會計算出如下所示的内容。

”mapper”任務在處理aqs檔案時會計算出如下所示的内容。

在計算w(q,a)時需要使用到variance(a)和normalizedweight(q, a)；在計算w(a,q)時需要使用到variance(q)和normalizedweight(a, q)。是以，根據以上分析，對于一個特定的q和a，需要把map任務的輸出中的variance(a)和normalizedweight(q, a)”shuffle”到同一個”reduce”節點，由該”reduce”節點計算出w(q,a)；同理，需要把”map”任務的輸出中的variance(q)和normalizedweight(a,

q) ”shuffle”到同一個”reduce”節點，由該”reduce”節點計算出w(a,q)。

另外，可以看出，在計算w(q1,a), w(q2,a),……. 時都需要用到variance(a)，是以我們希望計算 的“reduce”節點接受到的值清單中variance(a)項排在所有normalized_weight(q, a)項之前。mapreduce架構在記錄到達”reducer”之前按鍵對記錄排序，但鍵所對應的值并沒有被排序。由于值來自不同的map任務，是以在多次運作程式時，值的出現順序并不固定，導緻每次運作作業的時間會各有不同。一般來說，大多數mapreduce程式無需考慮值在”reduce”函數中出現的順序。但是，像我們這裡碰到的情況一樣，有時确實需要通過對鍵進行排序和分組等以實作對值的排序。通過mapreduce架構輔助對記錄值排序的方法總結如下：

(1) 定義包括自然鍵和自然值的組合鍵。

(2) 鍵的comparator根據組合鍵對記錄進行排序，即同時利用自然鍵和自然值進行排序。

(3) 針對組合鍵partitioner和分組comparator在進行分區和分組時均隻考慮自然鍵。

基于以上分析，計算權值矩陣的mapreduce任務需要小心地設計”map”任務輸出的key和value的資料結構以及”partitioner”函數。

(1) map任務輸出的鍵(key)的資料結構

鍵(key)由一個三元組構成：< type, index1, index2 >

type用于辨別index1是廣告的編号(0)，還是query的編号(1)；當type = 0時，對應的值(value)表示normalizedweight(q,a)，其中q等于index1，a等于index2；當type = 1時，value表示normalizedweight(a,q)，其中a等于index1，q等于index2；

另外，當index2 = -1時，表示對應的值為方差（variance(index1)）。設為-1是為了保證同一組key對應的值清單中方差項排在第一個。

鍵(key)的三個元素都參與comparator的比較。

(2) map任務輸出的值(value)的資料結構

值(value)有一個二進制組構成：< index, value >，其中index總是等于對應的鍵的第三個元素index2。這裡看似備援，其實不然。因為我們在利用mapreduce架構輔助排序時，分組函數(groupcomparator)隻比較key的前兩個元素，忽略key的第三個元素，這樣隻有key的前兩個元素的值相同，那麼他們的值将合并到同一個清單中，有唯一的一個“reduce”函數處理。mapreduce架構在預設情況下隻會把key完全相同值合并到同一個清單中。是以我們需要設定outputvaluegroupingcomparator為我們自定義的groupcomparator。可以利用如下的語句設定：

(3) 分區函數

分區函數控制”map”任務的每個輸出記錄由哪一個”reduce”節點處理。在權值矩陣的計算作業中該函數的地位特别重要。根據上一小節的分析和輔助排序的要求，分區函數隻考慮鍵的前兩個元素。我們把”reduce”節點分成兩部分，一部分計算 ，另外一部分計算 。”partition”函數的代碼如下。

(4) “map”函數和”reduce”函數

“map”函數和”reduce”函數并行地處理主要的工作。其中”map”函數讀入qas檔案，計算出variance(q)和normalizedweight(a, q)；讀入aqs檔案，輸出variance(a)和normalizedweight(q, a)。同時為了以後的計算友善，”map”函數還記錄下最大的query編号和最大的ad編号。由于多個”map”函數之間不能互相通信，為了得到全局的最大query編号和ad編号，每個map函數結束的時候在一個指定的hdfs目錄下建立一個以本函數統計出的目前最大編号為檔案名的空檔案，前提條件是此時該指定目錄下還沒有更大編号的檔案存在。

“reduce”函數比較簡單，直接根據公式計算出最終的權值就可以了。”reduce”輸出的key是一個二進制組，表示權值矩陣的行号和列号。輸出的值為相應的權值。由于我們在同一個作業中同時計算了query-ad的權值矩陣和ad-query的權值矩陣，這兩個矩陣在後面的simrank實作過程中需要單獨使用，是以必須要把兩種的輸出區分開來。我們使用multipleoutputs類定義了兩個資料收集對象，這兩個資料收集對象輸出的檔案名有不同的字首。

“mapper”和”reducer”的僞代碼如下。

計算權值矩陣的”map”函數

計算權值矩陣的”reduce”函數