版權聲明：本文為部落客原創文章，未經部落客允許不得轉載。 https://blog.csdn.net/qq1010885678/article/details/50751607

ItermCF的MR并行實作

@(Hadoop)

ItermCF的基本思想

基于物品相似度的協同過濾推薦的思想大緻可分為兩部分：

1.計算物與物之前的相似度

2.根據使用者的行為曆史，給出和曆史清單中的物品相似度最高的推薦

通俗的來講就是：

對于物品 A,根據所有使用者的曆史偏好,喜歡物品 A 的使用者都 喜歡物品 C,得出物品 A 和物品 C 比較相似,而使用者 C 喜歡物品 A,那麼可以推斷出 使用者 C 可能也喜歡物品 C。

ItermCF的算法實作思路

對于以下的資料集：

UserId	ItermId	Preference
1	101	5
	102	3
	103	2.5
2
	104
		4
	105	4.5
	107
	106
		3.5
6

使用者評分矩陣

首先可以建立使用者對物品的評分矩陣，大概長這個樣子：

1011021031041051061071532.50000222.552000320044.50545034.504454324340

列為UserId，行為ItermId，矩陣中的值代表該使用者對該物品的評分。

從列的方向看，該矩陣的每一個列在mr程式中可以用一行簡單的字元串來表示：

1   101:5,102:3,103:2.5 ...              

這樣一來，上面的矩陣5個列就可以由5行類似的字元串來構成。

那麼第一個mr任務的功能就是一個簡單的資料轉換過程：

1.輸入的key為行偏移量，value為每行内容，形如：1,101,5.0

2.在map階段，分割每行内容，輸出的key為1，value為101:5.0

3.在reduce階段，将UserId相同的所有評分記錄進行彙總拼接，輸出的key仍然為1，value形如：101:5,102:3,103:2.5 …

如此一來通過第一個mr任務得到了使用者的評分矩陣。

物品同現矩陣

該矩陣大概長這個樣子：

矩陣的值表示，兩個物品同時被使用者喜歡（評過分）的次數，例如：101和102這個組合被1，2，5三個使用者喜歡過，那麼在矩陣中101和102對應的值就是3。

這個矩陣的意義就是各個物品之間的相似度，為什麼可以這麼說？

如果兩個物品經常同時被很多使用者喜歡，那麼可以說這兩個物品是相似的，同時被越多的使用者喜歡（即為通同現度，上面矩陣中的值），這兩個物品的相似度就越高。

其實觀察可以發現，行和列上相同的（比如101和101）相比其他值（比如101和102，101和103）都是最大的，因為101和101就是同一個物品，相似度肯定是最大的。

從列的方向上看，這個同現矩陣的每一列在mr程式中可以通過下面簡單的字元串來表示：

101:101 5   
101:102 3
101:103 4
...           

m*n的同現矩陣就由m個以上的字元串（n行）組成。

那麼第二個mr任務的功能就是在第一個mr任務的輸出結果上得到物品同現矩陣：

1.輸入的key為偏移量，輸入的value為UserId+制表符+ItermId1:Perference1,ItermId2:Perference2…

2.輸入的value中，UserId和Perference是不需要關心的，觀察物品的同現矩陣，map階段的工作就是将每行包含的ItermId都解析出來，全排列組合作為key輸出，每個key的value記為1。

3.在reduce階段所做的就是根據key對value進行累加輸出。

如此一來便能夠得到物品的同現矩陣。

物品同現矩陣和使用者評分矩陣的相乘

物品同現矩陣*使用者評分矩陣=推薦結果：

為什麼兩個矩陣相乘可以得到推薦結果？

物品1和各個物品的同現度*使用者對各個物品的喜好度，反應出使用者對物品1的喜好度。

例如，要預測使用者3對103物品的喜好度，我們需要找到和103相似的物品，比如101物品，和103的同現度為4，是很類似的物品，使用者3對101的評分為2，那麼一定程度上可以反映出使用者對103的喜好度，101和103的相似度（即同現度）*使用者3對101的評分可以得到使用者3對103的喜好度權重，将使用者3對各個物品的權重相加，可以反映出使用者3對103的喜好度。

了解矩陣相乘的意義之後，第三個mr任務的功能就是實作兩個矩陣的相乘，并将結果輸出。

在這個mr任務中，這兩個矩陣的相乘可以這樣來計算：

将同現矩陣存入一個Map中，形如：

Map<String, Map<String, Double>> colItermOccurrenceMap = new HashMap<String, Map<String, Double>>();           

同現矩陣中的每一行就是大Map中的一條記錄，每行對應的每列都在該記錄的小Map中。

在map階段的開始的時候初始化這個Map，輸入的value形如101:101 5,101:102 3，将101作為大Map的key，value為小Map，小Map的key為101/102，value為5/3。

由于map函數讀取檔案是并發讀取的，不能保證兩個輸入檔案的讀取順序（在同一個檔案中也不能保證），是以這裡使用Hadoop提供的分布式緩存機制來對同現矩陣進行共享。

關于Hadoop的分布式緩存機制請看：

Hadoop的DistributedCache機制

初始化同現矩陣之後，讀取評分矩陣的每一行，輸入的value為1 101:5,102:3,103:2.5 …

将每行的itermIds和對應的評分數提取出來，周遊itermId，根據itermId到itermOccurrenceMap中找到對應的List集合，找到每個itermId在該集合中對應的itermId2記錄，将評分數*同現度，之後進行累加，以UserId:ItermID作為key，累加值作為value輸出。

reduce的工作就很簡單了，根據key對value進行累加輸出即可。

項目代碼

源碼Github位址

作者：

@小黑