物品间具有先后关系的ItemCF算法实现

简书不支持Markdown Math语法，请移步https://glassywing.github.io/2018/06/28/spark_linear_itemcf/

传统的ItemCF算法，物品间不具有先后关系，可以任意进行推荐。这样的算法并不适用某些场景（见下文背景），对于此类场景，对ItemCF算法进行了扩展，使其可以依据当前用户使用的物品进行推荐。

注意：该算法只是在原有的ItemCF实现上进行了扩展，它只能根据当前使用的物品推荐下一个物品，并不记忆之前使用的物品（不依据上下文信息进行推荐）。

语义

• 构件：SOA程序模型设计过程中以实现某种功能的程序片段或模块
• 流程：使用多个构件进行线性组合后的以实现某种特定功能的执行过程，即SOA工作流

背景

SOA工作流中具有很多的构件，这些构件能以线性方式组合成一条流程（流程按照线性关系被依次执行）。在使用一个构件之后，可随之使用另一个后续的构件，前一个构件和后一个构件间具有严明的先后关系，即后一个构件不能反向使用前一个构件，前一个构件可以使用不同的后续构件。

由于前一个构件使用后可以使用不同的后续构件，对于新用户来说，必须翻阅文档才知道可用的下一个构件，最终才能进行选择。使操作变得相当繁琐，造成大量的时间浪费，因此需要一种能通过以往用户记录为用户推荐下一个可用构件的方式来减轻工作负担。

目标

要求用户在工作流中连接一个构件后，推荐出下一个可用的构件，下一个构件按照预测的用户评分从高到低进行排列，并可指定推荐的构件数量。

数据存储格式

用户历史行为日志

用户历史记录以表：history表示，其中userId表示用户ID，compId表示构件ID，folloCompId表示使用了compId后使用的构件ID，count表示用户使用了comp之后又继续使用folloComp的使用次数。

userId	compId	followCompId	count	timestamp
1	1	2	1
1	1	3	2
2	1	2	1
2	1	4	3

算法说明

相似度度量算法

这里我们选择使用同现相似度作为相似度度量标准：

同现相似度公式

$$ w(x,y)=\frac{|N(x)\cap{N(y)}|}{|N(x)|} $$

公式中分母是喜欢物品x的用户数，而分子则是同时对物品x和物品y感兴趣的用户数。因此，上述公式可用理解为对物品x感兴趣的用户有多大概率也对y感兴趣 (和关联规则类似)

但上述的公式存在一个问题，如果物品y是热门物品，有很多人都喜欢，则会导致W(x, y)很大，接近于1。因此会造成任何物品都和热门物品交有很大的相似度。为此我们用如下公式进行修正:

改进型同现相似度公式

$$ w(x,y)=\frac{|N(x)\cap{N(y)}|}{\sqrt{|N(x)||N(y)|}} $$

这个格式惩罚了物品y的权重，因此减轻了热门物品和很多物品相似的可能性。(也归一化了)

预测用户评分公式

$$ pred_{u,p}=\frac{\sum_{i\in{ratedItems(u)}}{sim(i,p)r_{u,i}}}{\sum_{i\in{ratedItems(u)}}{sim(i,p)}} $$

公式中u指用户，p值物品，ratedItems(u)指用户u评价过的物品，sim指相似度（item之间的），r指用户对使用过的物品i的评分（这里指使用次数）。

算法实现

计算过程

假设现在用户1在流程中连接了一个构件a，在用户历史记录中，构件a之后可用的构件有b和c。根据同现相似度的定义，计算过程如下：

1. 多少用户使用了a之后使用过b：numAToB
2. 多少用户使用了a之后使用过c：numAToC
3. 多少用户使用了a之后既使用过b又使用过c: numAToBC
4. 通过相似度计算公式计算b和c之间的相似度: simBC
5. 按照用户评分公式预测用户1对b，c的评分
6. 按照评分高低从高到低进行排列

具体实现

物品相似度计算

1. 统计在使用了第一个构件后又使用第二个构件的用户数量:

   通过在用户历史原表上按(compId,followCompId)进行聚合计数操作，可以得到在使用了第一个构件后又使用第二个构件的用户数量：

   表：numRaters

   compId	followCompId	numRaters
   1	2	2
   1	3	1
   1	4	1

2. 将表numRaters和表history进行内联操作，并忽略掉count：

   表：historyWithSize

   userId	compId	followCompId	numRaters
   1	1	2	2
   1	1	3	1
   2	1	2	2
   2	1	4	1

3. 将表historyWithSize和表historyWithSize按照(userId, compId)进行内联并按照followCompId1 < followCompId2进行过滤：

   userId	compId	followCompId1	numRaters1	followCompId2	numRaters2
   1	1	2	2	3	1
   2	1	2	2	4	1

4. 统计在使用过comp后既使用过followComp1又使用过followComp2的用户数，使用列size表示：

   compId	followCompId1	numRaters1	followCompId2	numRaters2	size
   1	2	2	3	2	1
   1	2	2	4	1	1

5. 计算followComp1和followComp2的相似度：

   表：similarities

   compId	followCompId1	followCompId2	cosSim
   1	2	3	0.5
   1	2	4	0.7

对用户进行推荐

1. 要计算用户对物品的兴趣度，需要首先获取用户的历史行为，由于用户连接一个构件后才进行推荐，因此用户历史记录以(userId, compId)进行限制：

   userId	compId	followCompId	count	timestamp
   1	1	2	1
   1	1	3	2
   2	1	2	1
   2	1	4	3

2. 将指定用户的历史表history与表similarities按照(compId, followCompId)做内联操作，获得用户感兴趣的物品与其它物品的相似度：

   userId	compId	followCompId1	followCompId2	cosSim	cosSim * count as simProduct
   1	1	2	3	0.5	0.5
   1	1	3	2	0.5	0.5
   2	1	2	4	0.7	2.1
   2	1	4	2	0.7	2.1

3. 按照(userId, compId, followCompId2)分组计算用户对其构件的评分：

   userId	compId	followCompId2	sum(simProduct) / sum(cosSim)
   1	1	2	1
   1	1	3	1
   2	1	2	3
   2	1	4	3