簡(jiǎn)書(shū)不支持Markdown Math語(yǔ)法，請(qǐng)移步https://glassywing.github.io/2018/06/28/spark_linear_itemcf/
傳統(tǒng)的ItemCF算法爱态，物品間不具有先后關(guān)系，可以任意進(jìn)行推薦鸳碧。這樣的算法并不適用某些場(chǎng)景（見(jiàn)下文背景），對(duì)于此類(lèi)場(chǎng)景，對(duì)ItemCF算法進(jìn)行了擴(kuò)展，使其可以依據(jù)當(dāng)前用戶(hù)使用的物品進(jìn)行推薦米碰。
注意：該算法只是在原有的ItemCF實(shí)現(xiàn)上進(jìn)行了擴(kuò)展，它只能根據(jù)當(dāng)前使用的物品推薦下一個(gè)物品躲履，并不記憶之前使用的物品（不依據(jù)上下文信息進(jìn)行推薦）。
語(yǔ)義
- 構(gòu)件：SOA程序模型設(shè)計(jì)過(guò)程中以實(shí)現(xiàn)某種功能的程序片段或模塊
- 流程：使用多個(gè)構(gòu)件進(jìn)行線(xiàn)性組合后的以實(shí)現(xiàn)某種特定功能的執(zhí)行過(guò)程聊闯，即SOA工作流
背景
SOA工作流中具有很多的構(gòu)件工猜，這些構(gòu)件能以線(xiàn)性方式組合成一條流程（流程按照線(xiàn)性關(guān)系被依次執(zhí)行）。在使用一個(gè)構(gòu)件之后菱蔬，可隨之使用另一個(gè)后續(xù)的構(gòu)件篷帅，前一個(gè)構(gòu)件和后一個(gè)構(gòu)件間具有嚴(yán)明的先后關(guān)系史侣，即后一個(gè)構(gòu)件不能反向使用前一個(gè)構(gòu)件，前一個(gè)構(gòu)件可以使用不同的后續(xù)構(gòu)件魏身。
由于前一個(gè)構(gòu)件使用后可以使用不同的后續(xù)構(gòu)件惊橱，對(duì)于新用戶(hù)來(lái)說(shuō)，必須翻閱文檔才知道可用的下一個(gè)構(gòu)件箭昵，最終才能進(jìn)行選擇。使操作變得相當(dāng)繁瑣正林，造成大量的時(shí)間浪費(fèi)涵但，因此需要一種能通過(guò)以往用戶(hù)記錄為用戶(hù)推薦下一個(gè)可用構(gòu)件的方式來(lái)減輕工作負(fù)擔(dān)瞳脓。
目標(biāo)
要求用戶(hù)在工作流中連接一個(gè)構(gòu)件后埋涧，推薦出下一個(gè)可用的構(gòu)件棘催，下一個(gè)構(gòu)件按照預(yù)測(cè)的用戶(hù)評(píng)分從高到低進(jìn)行排列，并可指定推薦的構(gòu)件數(shù)量。
數(shù)據(jù)存儲(chǔ)格式
用戶(hù)歷史行為日志
用戶(hù)歷史記錄以表：history表示，其中userId表示用戶(hù)ID诱篷，compId表示構(gòu)件ID，folloCompId表示使用了compId后使用的構(gòu)件ID，count表示用戶(hù)使用了comp之后又繼續(xù)使用folloComp的使用次數(shù)。
| userId | compId | followCompId | count | timestamp |
|---|---|---|---|---|
| 1 | 1 | 2 | 1 | |
| 1 | 1 | 3 | 2 | |
| 2 | 1 | 2 | 1 | |
| 2 | 1 | 4 | 3 |
算法說(shuō)明
相似度度量算法
這里我們選擇使用同現(xiàn)相似度作為相似度度量標(biāo)準(zhǔn)：
同現(xiàn)相似度公式
$$ w(x,y)=\frac{|N(x)\cap{N(y)}|}{|N(x)|} $$
公式中分母是喜歡物品x的用戶(hù)數(shù)瓤狐，而分子則是同時(shí)對(duì)物品x和物品y感興趣的用戶(hù)數(shù)。因此信姓，上述公式可用理解為對(duì)物品x感興趣的用戶(hù)有多大概率也對(duì)y感興趣 (和關(guān)聯(lián)規(guī)則類(lèi)似)
但上述的公式存在一個(gè)問(wèn)題，如果物品y是熱門(mén)物品，有很多人都喜歡，則會(huì)導(dǎo)致W(x, y)很大，接近于1。因此會(huì)造成任何物品都和熱門(mén)物品交有很大的相似度也切。為此我們用如下公式進(jìn)行修正:
改進(jìn)型同現(xiàn)相似度公式
$$ w(x,y)=\frac{|N(x)\cap{N(y)}|}{\sqrt{|N(x)||N(y)|}} $$
這個(gè)格式懲罰了物品y的權(quán)重，因此減輕了熱門(mén)物品和很多物品相似的可能性。(也歸一化了)
預(yù)測(cè)用戶(hù)評(píng)分公式
$$ pred_{u,p}=\frac{\sum_{i\in{ratedItems(u)}}{sim(i,p)r_{u,i}}}{\sum_{i\in{ratedItems(u)}}{sim(i,p)}} $$
公式中u指用戶(hù)，p值物品，ratedItems(u)指用戶(hù)u評(píng)價(jià)過(guò)的物品，sim指相似度（item之間的），r指用戶(hù)對(duì)使用過(guò)的物品i的評(píng)分（這里指使用次數(shù)）。
算法實(shí)現(xiàn)
計(jì)算過(guò)程
假設(shè)現(xiàn)在用戶(hù)1在流程中連接了一個(gè)構(gòu)件a旬牲，在用戶(hù)歷史記錄中晌区，構(gòu)件a之后可用的構(gòu)件有b和c契讲。根據(jù)同現(xiàn)相似度的定義，計(jì)算過(guò)程如下：
- 多少用戶(hù)使用了a之后使用過(guò)b：numAToB
- 多少用戶(hù)使用了a之后使用過(guò)c：numAToC
- 多少用戶(hù)使用了a之后既使用過(guò)b又使用過(guò)c: numAToBC
- 通過(guò)相似度計(jì)算公式計(jì)算b和c之間的相似度: simBC
- 按照用戶(hù)評(píng)分公式預(yù)測(cè)用戶(hù)1對(duì)b，c的評(píng)分
- 按照評(píng)分高低從高到低進(jìn)行排列
具體實(shí)現(xiàn)
物品相似度計(jì)算
-
統(tǒng)計(jì)在使用了第一個(gè)構(gòu)件后又使用第二個(gè)構(gòu)件的用戶(hù)數(shù)量:
通過(guò)在用戶(hù)歷史原表上按
(compId,followCompId)進(jìn)行聚合計(jì)數(shù)操作琉预，可以得到在使用了第一個(gè)構(gòu)件后又使用第二個(gè)構(gòu)件的用戶(hù)數(shù)量：表：numRaters
compId followCompId numRaters 1 2 2 1 3 1 1 4 1 -
將表
numRaters和表history進(jìn)行內(nèi)聯(lián)操作啄栓，并忽略掉count：表：historyWithSize
userId compId followCompId numRaters 1 1 2 2 1 1 3 1 2 1 2 2 2 1 4 1 -
將表
historyWithSize和表historyWithSize按照(userId, compId)進(jìn)行內(nèi)聯(lián)并按照f(shuō)ollowCompId1 < followCompId2進(jìn)行過(guò)濾：userId compId followCompId1 numRaters1 followCompId2 numRaters2 1 1 2 2 3 1 2 1 2 2 4 1 -
統(tǒng)計(jì)在使用過(guò)
comp后既使用過(guò)followComp1又使用過(guò)followComp2的用戶(hù)數(shù)，使用列size表示：compId followCompId1 numRaters1 followCompId2 numRaters2 size 1 2 2 3 2 1 1 2 2 4 1 1 -
計(jì)算
followComp1和followComp2的相似度：表：
similaritiescompId followCompId1 followCompId2 cosSim 1 2 3 0.5 1 2 4 0.7
對(duì)用戶(hù)進(jìn)行推薦
-
要計(jì)算用戶(hù)對(duì)物品的興趣度螃宙，需要首先獲取用戶(hù)的歷史行為，由于用戶(hù)連接一個(gè)構(gòu)件后才進(jìn)行推薦伺糠，因此用戶(hù)歷史記錄以
(userId, compId)進(jìn)行限制：userId compId followCompId count timestamp 1 1 2 1 1 1 3 2 2 1 2 1 2 1 4 3 -
將指定用戶(hù)的歷史表
history與表similarities按照(compId, followCompId)做內(nèi)聯(lián)操作，獲得用戶(hù)感興趣的物品與其它物品的相似度：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 -
按照
(userId, compId, followCompId2)分組計(jì)算用戶(hù)對(duì)其構(gòu)件的評(píng)分：userId compId followCompId2 sum(simProduct) / sum(cosSim) 1 1 2 1 1 1 3 1 2 1 2 3 2 1 4 3
