推薦系統(tǒng)算法

1.ItemCF：

原文鏈接

  協(xié)同過濾是什么？
    協(xié)同過濾 (Collaborative filtering)，指的是，通過收集群體用戶的偏好信息，自動化預(yù)測（過濾）個體用戶可能感興趣的內(nèi)容。協(xié)（collaborating）是群體行為，過濾（filtering）則是針對個人的行為。

    ItemCF：Item Collaboration Filter，基于物品的協(xié)同過濾。
    核心思想：給用戶推薦那些和他們之前喜歡的物品相似的物品。
    基本假設(shè)：物品A和物品B具有很大的相似度是因為喜歡物品A的用戶大都也喜歡B。
    算法步驟：
        1.計算物品之間的相似度；
        2.根據(jù)物品的相似度和用戶的歷史行為給用戶生成推薦列表；
    計算物品之間的相似度：

    |N(i)|是喜歡物品i的用戶數(shù)，|N(j)|是喜歡物品j的用戶數(shù)。
    對用戶熱度做懲罰：

        3.給用戶推薦物品。
        用戶u對物品j的興趣程度：

        基本思想：如果要計算用戶u與物品j的興趣度， 先找到與j最相似的k個物品，再看用戶u與這些物品的感興趣程度，加權(quán)得到用戶u對物品j的興趣程度。

舉個例子：

    ItemCF流程：
    1、根據(jù)用戶下單數(shù)據(jù)計算poi相似度

       CalSim為計算poi相似度的模塊，基于論文Scalable Similarity-Based Neighborhood Methods with MapReduce實現(xiàn)。

        CalSim模塊：
        Preprocess: 將（user, poi, score）輸入轉(zhuǎn)換成 poi,(user, score);(user, score); ...形式，
針對不同相似度度量方法對score進行轉(zhuǎn)換；
        Norm:針對不同相似度度量方法計算poi vector的norm；
        Reverse:將Preprocess中生成的poi,(user, score);(user, score); ...數(shù)據(jù)，轉(zhuǎn)化成
user,(poi, score);(poi, score); ...的倒排形式，以便Similarity按照user進行數(shù)據(jù)分塊；
        Similarity：組織mapper，combiner & reducer實施相似度計算。

理論部分已經(jīng)介紹完畢，下面是代碼部分：

#-*-coding:utf-8-*-'''Created on 2016-5-30@author: thinkgamer'''import mathclass ItemBasedCF:def __init__(self,train_file):self.train_file = train_fileself.readData()def readData(self):#讀取文件，并生成用戶-物品的評分表和測試集self.train = dict()     #用戶-物品的評分表for line in open(self.train_file):# user,item,score = line.strip().split(",")user,score,item = line.strip().split(",")self.train.setdefault(user,{})self.train[user][item] = int(float(score))def ItemSimilarity(self):#建立物品-物品的共現(xiàn)矩陣C = dict()  #物品-物品的共現(xiàn)矩陣N = dict()  #物品被多少個不同用戶購買for user,items in self.train.items():for i in items.keys():N.setdefault(i,0)N[i] += 1C.setdefault(i,{})for j in items.keys():if i == j : continueC[i].setdefault(j,0)C[i][j] += 1#計算相似度矩陣self.W = dict()for i,related_items in C.items():self.W.setdefault(i,{})for j,cij in related_items.items():self.W[i][j] = cij / (math.sqrt(N[i] * N[j]))return self.W#給用戶user推薦，前K個相關(guān)用戶def Recommend(self,user,K=3,N=10):rank = dict()action_item = self.train[user]     #用戶user產(chǎn)生過行為的item和評分for item,score in action_item.items():for j,wj in sorted(self.W[item].items(),key=lambda x:x[1],reverse=True)[0:K]:if j in action_item.keys():continuerank.setdefault(j,0)rank[j] += score * wjreturn dict(sorted(rank.items(),key=lambda x:x[1],reverse=True)[0:N])#聲明一個ItemBased推薦的對象Item = ItemBasedCF("uid_score_bid")Item.ItemSimilarity()recommedDic = Item.Recommend("xiyuweilan")for k,v in recommedDic.iteritems():print k,"\t",v

2.MF(ALS)矩陣分解

原理和代碼可以參考https://blog.csdn.net/pearl8899/article/details/80336938，這是18年夏天使用該算法的時候，做的筆記，寫的略微繁瑣，這里精簡一下。論文名字：matrix factorization techniques for recommender systems

先放一張圖留著：

MF(matrix factorization)：矩陣分解，分解的是什么矩陣，元素如何獲取？

       這個矩陣是上圖的“Rating”，是user對deal，也就是item的行為，在論文中，Rating是電影評分的意思，在工業(yè)界中，這個Rating，可以是user對deal的點擊、下單、瀏覽的匯總，至于匯總的方式是什么，根據(jù)你對業(yè)務(wù)的理解，自己定義。比如user對deal1點擊1次算1分，下單算5分，也即是給不同行為加權(quán)累積。這里要注意，在使用spark ML中ALS的時候，要注意迭代分解的時候是顯示還是隱式，像上述給出的Rating，那便是顯示行為，人為的給這個user-deal之間強加了一個rating.

基于矩陣分解的推薦算法的核心假設(shè)是用隱語義（隱變量）來表達用戶和物品，他們的乘積關(guān)系就成為了原始的元素。這種假設(shè)之所以成立，是因為我們認為實際的交互數(shù)據(jù)是由一系列的隱變量的影響下產(chǎn)生的（通常隱變量帶有統(tǒng)計分布的假設(shè)，就是隱變量之間，或者隱變量和顯式變量之間的關(guān)系，我們往往認為是由某種分布產(chǎn)生的。），這些隱變量代表了用戶和物品一部分共有的特征，在物品身上表現(xiàn)為屬性特征，在用戶身上表現(xiàn)為偏好特征，只不過這些因子并不具有實際意義，也不一定具有非常好的可解釋性，每一個維度也沒有確定的標簽名字，所以才會叫做 “隱變量”。而矩陣分解后得到的兩個包含隱變量的小矩陣，一個代表用戶的隱含特征，一個代表物品的隱含特征，矩陣的元素值代表著相應(yīng)用戶或物品對各項隱因子的符合程度，有正面的也有負面的。

ALS 是什么？----同SGD一樣，求解參數(shù)的一種方法

      ALS 是交替最小二乘 （alternating least squares）的簡稱。在機器學(xué)習(xí)的上下文中，ALS 特指使用交替最小二乘求解的一個協(xié)同推薦算法。

ALS 的核心就是下面這個假設(shè)：打分矩陣是近似低秩的。換句話說，一個m*n的大矩陣 A 可以用兩個小矩陣U(m*k)和V(n*k)的乘積來近似：

ALS 的名字里給出——交替最小二乘。ALS 的目標函數(shù)不是凸的，而且變量互相耦合在一起，所以它并不算好解。但如果我們把用戶特征矩陣U和產(chǎn)品特征矩陣V固定其一，這個問題立刻變成了一個凸的而且可拆分的問題。比如我們固定U，那么目標函數(shù)就可以寫成。其中關(guān)于每個產(chǎn)品特征vj的部分是獨立的，也就是說固定U求vj我們只需要最小化就好了，這個問題就是經(jīng)典的最小二乘問題。所謂“交替”，就是指我們先隨機生成U0然后固定它求解V0,在固定V0求解U1，這樣交替進行下去。因為每步迭代都會降低重構(gòu)誤差，并且誤差是有下界的，所以 ALS 一定會收斂。但由于問題是非凸的，ALS 并不保證會收斂到全局最優(yōu)解。但在實際應(yīng)用中，ALS 對初始點不是很敏感，是不是全局最優(yōu)解造成的影響并不大。

匯總：

        對于一個users-products-rating的評分數(shù)據(jù)集，ALS會建立一個user*product的m*n的矩陣。其中，m為users的數(shù)量，n為products的數(shù)量。但是在這個數(shù)據(jù)集中，并不是每個用戶都對每個產(chǎn)品進行過評分，所以這個矩陣往往是稀疏的，用戶i對產(chǎn)品j的評分往往是空的。

        ALS所做的事情就是將這個稀疏矩陣通過一定的規(guī)律填滿，這樣就可以從矩陣中得到任意一個user對任意一個product的評分，ALS填充的評分項也稱為用戶i對產(chǎn)品j的預(yù)測得分。所以說，ALS算法的核心就是通過什么樣子的規(guī)律來填滿（預(yù)測）這個稀疏矩陣

它是這么做的：假設(shè)m*n的評分矩陣R，可以被近似分解成U*(V)T，U為m*d的用戶特征向量矩陣，V為n*d的產(chǎn)品特征向量矩陣（(V)T代表V的轉(zhuǎn)置），d為user/product的特征值的數(shù)量。ALS算法的核心就是將稀疏評分矩陣分解為用戶特征向量矩陣和產(chǎn)品特征向量矩陣的乘積交替使用最小二乘法逐步計算用戶/產(chǎn)品特征向量，使得差平方和最小通過用戶/產(chǎn)品特征向量的矩陣來預(yù)測某個用戶對某個產(chǎn)品的評分。

spark ALS代碼解釋

常被應(yīng)用于推薦系統(tǒng)。這些技術(shù)旨在補充用戶-商品關(guān)聯(lián)矩陣中所缺失的部分。MLlib當(dāng)前支持基于模型的協(xié)同過濾，其中用戶和商品通過一小組隱語義因子進行表達，并且這些因子也用于預(yù)測缺失的元素。為此，我們實現(xiàn)了ALS來學(xué)習(xí)這些隱性語義因子。在 MLlib 中的實現(xiàn)有如下的參數(shù):

numBlocks 是用于并行化計算的分塊個數(shù) (設(shè)置為-1為自動配置)。

rank 是模型中隱語義因子的個數(shù)。就是平時的特征向量的長度。

maxIter：iterations 是迭代的次數(shù)。

lambda 是ALS的正則化參數(shù)。

implicitPrefs 決定了是用顯性反饋ALS的版本還是用適用隱性反饋數(shù)據(jù)集的版本，如果是隱性反饋則需要將其參數(shù)設(shè)置為true。

alpha 是一個針對于隱性反饋 ALS 版本的參數(shù)，這個參數(shù)決定了偏好行為強度的基準。

itemCol:deal的字段名字，需要跟表中的字段名字是一樣的。

nonnegative:是否使用非負約束，默認不使用 false。

predictionCol:預(yù)測列的名字

ratingCol：評論字段的列名字，要跟表中的數(shù)據(jù)字段一致。

userCol：用戶字段的名字，同樣要保持一致。

實踐小技巧：
1.調(diào)參，推薦使用網(wǎng)格搜索進行調(diào)參。

包括三步： 

println("end als and begin paramGrid ----------")val paramGrid = new ParamGridBuilder().addGrid(als.maxIter,Array(50,100,150)).addGrid(als.rank,Array(32,64,128,256)).build()val evaluator = new RegressionEvaluator().setMetricName("rmse").setLabelCol("rating").setPredictionCol("prediction")println("end evaluator and begin TV ")val trainValidationSplit = new TrainValidationSplit().setEstimator(als).setEvaluator(evaluator).setTrainRatio(0.8).setEstimatorParamMaps(paramGrid).setSeed(567812)println("begin tv model__________")val tvModel: TrainValidationSplitModel = trainValidationSplit.fit(training)

第一步：確定paramGrid。這里加入對迭代次數(shù)和分裂維度進行網(wǎng)格搜索。其實就是貪婪搜索，遍歷每一種可能。

第二步：確定評估方法evaluator。這里用rmse進行評估。

第三步：TV方法進行訓(xùn)練。

第四步：可能需要模型之間的轉(zhuǎn)換。

2. ALS中還有一個加速分解的參數(shù)：

.setNumBlocks(200)

這個參數(shù)官網(wǎng)文檔說這個參數(shù)可以設(shè)置為-1，加速分解，但是我將其設(shè)置為-1的時候，出bug，說是該參數(shù)設(shè)置無效。因此只能盡量的將這些參數(shù)設(shè)置的大一些，加速矩陣分解。我采用了rating矩陣中有5億數(shù)據(jù)進行分解，分200塊，速度確實提高了不少，具體沒有衡量。

3.

寫在最后，感謝孟祥瑞大佬、銘霏大佬以及各位大佬在als在sparkML中的實現(xiàn)。

參考博客：

1.https://blog.csdn.net/u012102306/article/details/51097502
2.關(guān)于矩陣分解用于推薦系統(tǒng)的博客：https:///recommendation-algorithm-based-on-matrix-decomposition.html

    補充知識：
        準確率：最終的推薦列表中推薦對了的比率。
        召回率：推薦對了的占全集的比率。