国产乱屌精品,国产码亚洲码专区在线

Recommended System

相似度的衡量

歐式距離，是個(gè)人都知道，不提了。
Pearson Correlation相似度： $Corr(x,y) = \frac{<x-x',y-y'>}{|x-x'||y-y'|}$ <x,y>指的就是內(nèi)積操作、皮爾遜相似度的好處就在于對(duì)于級(jí)數(shù)不敏感，級(jí)數(shù)相差過(guò)大帶來(lái)的影響不大。
余弦相似度： $cos(x,y) = \frac{<x,y>}{|x||y|}$ 這個(gè)就不用多說(shuō)了，一般就是用在了文本編碼之后的向量相似度比較，因?yàn)檫@時(shí)候很多向量都不在歐式空間上了，一般就用他們夾角的大小來(lái)

推薦算法

基于內(nèi)容的推薦

基于關(guān)聯(lián)規(guī)則的推薦

協(xié)同過(guò)濾的推薦

基于知識(shí)的推薦

基于圖的推薦

組合推薦

當(dāng)然不會(huì)講解這么多，只會(huì)提到一兩個(gè)。

基于內(nèi)容的推薦系統(tǒng)

基于內(nèi)容就是基于用戶喜歡的物品的屬性/內(nèi)容進(jìn)行推薦，需要分析內(nèi)容，無(wú)需考慮用戶和用戶直接的關(guān)系。通常就是在文本相關(guān)的產(chǎn)品上進(jìn)行推薦。所以一般就是通過(guò)內(nèi)容上的關(guān)鍵詞進(jìn)行推薦，然后編碼比對(duì)物品內(nèi)容的異同進(jìn)行推薦。事實(shí)上編碼之后就可以隨意發(fā)揮了，直接使用KNN都是可以的。
最簡(jiǎn)單的文本推薦，對(duì)于一份文本，首先就是要建立資料這個(gè)時(shí)候就是叫編碼過(guò)程了，因?yàn)椴豢赡馨牙锩娴奈淖侄汲槿〕鰜?lái)，這樣工作量非常大，使用首先就是要分詞去掉重復(fù)的詞語(yǔ)，然后抽取關(guān)鍵字做編碼。TF-IDF，詞袋模型，ont-hot編碼，詞 $k_{ij}$ 在文件 $d_j$ 中權(quán)重 $w_{ij}$ 都是可以的，得到這些向量之后，就可以用相似度衡量，選擇合適的算法做相似度排序選擇了。比如對(duì)于書(shū)本《Building data mining application for CRM》這個(gè)本書(shū)感興趣。

以上是商品總和。

出現(xiàn)過(guò)的單詞扣一，沒(méi)有的都是0，這種編碼叫做one-hot編碼，這里商品少，單詞也就那么幾個(gè)，所以ont-hot編碼不長(zhǎng)，就是一點(diǎn)點(diǎn)而已。比較牛逼點(diǎn)的就是TF-IDF了：

把文檔出現(xiàn)詞的概率算了進(jìn)來(lái)。得到這些向量之后只需要做近似就好了，比如KNN最簡(jiǎn)單的。

協(xié)同過(guò)濾的推薦

NeiNeighborhood-based Algorithm是一種基于近鄰的推薦，協(xié)同過(guò)濾有兩種，一種是基于用戶的協(xié)同過(guò)濾，一種是基于物品的協(xié)同過(guò)濾。

user-based CF

其實(shí)過(guò)程是非常簡(jiǎn)單的，簡(jiǎn)單到飛起。首先我們是要得到一個(gè)相似度矩陣，這個(gè)相似度矩陣首先是一個(gè)對(duì)稱的，其次它的對(duì)角線都是0,。計(jì)算完用戶之間的相似度之后利用用戶之間的相似度為沒(méi)有打分的項(xiàng)打分。其實(shí)就是 $p(u,i) = \sum_{v \in N(j)}w_{u,v}r_{v,j}$ 找到當(dāng)前這個(gè)用戶沒(méi)有打分的商品，然后把對(duì)這個(gè)商品評(píng)價(jià)過(guò)的用戶的得分乘上相似矩陣的對(duì)應(yīng)權(quán)重相加即可。
代碼實(shí)現(xiàn)
工具包的實(shí)現(xiàn)：
求余弦相似度：

def cos_sim(x, y):
    numerator = x * y.T
    denominator = np.sqrt(x * x.T)
    return (numerator / denominator)[0, 0]

求相似度矩陣：

def similarity(data):
    m = np.shape(data)[0]
    w = np.mat(np.zeros((m, m)))
    for i in range(m):
        for j in range(i, m):
            if j != i:
                w[i, j] = cos_sim(data[i, ], data[j, ])
                w[j, i] = w[i, j]
            else:
                w[i, j] = 0
    return w

求top N的商品是什么：

def top_k(predict, k):
    top_recom = []
    len_result = len(predict)
    if k >= len_result:
        top_recom = predict
    else:
        for i in range(k):
            top_recom.append(predict[i])
    return top_recom

基于用戶的協(xié)同過(guò)濾：

def user_based_recommend(data, w, user):
    m, n = np.shape(data)
    interaction = data[user, ]
    not_inter = []
    for i in range(n):
        if interaction[0, i] == 0:
            not_inter.append(i)
    predict = {}
    for x in not_inter:
        item = np.copy(data[:, x])
        for i in range(m):
            if item[i, 0] != 0:
                if x not in predict:
                    predict[x] = w[user, i] * item[i, 0]
                else:
                    predict[x] = predict[x] + w[user, i] * item[i, 0]
    return sorted(predict.items(), key=lambda  d:d[1], reverse=True)

相似度矩陣

為每一個(gè)用戶所推薦的商品。

item_based CF

也是一樣，只需要把數(shù)據(jù)轉(zhuǎn)置一下就好了。

def item_based_recommend(data, w, user):
    m, n = np.shape(data)
    interation = data[:, user]
    not_inter = []
    for i in range(n):
        if interation[0, i] == 0:
            not_inter.append(i)

    predict = {}
    for x in not_inter:
        item = np.copy(interation)
        for j in range(m):
            if item[0, j] != 0:
                if x not in predict:
                    predict[x] = w[x, j] * item[0, j]
                else:
                    predict[x] = predict[x] + w[x, j] * item[0, j]
    return sorted(predict.items(), key=lambda d:d[1], reverse=True)

相似度矩陣

每位用戶的推薦。

user-based vs item-based

這兩種方法各有優(yōu)缺點(diǎn)。對(duì)于UserCF，適用于用戶較少的場(chǎng)景，如果用戶是非常多的的情況下，計(jì)算用戶相似度矩陣的代價(jià)是很大的。這個(gè)時(shí)候如果物品相對(duì)用戶要少，那么就可以用ItemCF來(lái)計(jì)算相似度矩陣。對(duì)于兩種算法的領(lǐng)域也有很大的區(qū)別，UserCF的時(shí)效性較強(qiáng)，對(duì)于用戶興趣不太明顯的領(lǐng)域是有可能會(huì)推薦出來(lái)的，也就是說(shuō)覆蓋性會(huì)好一些，因?yàn)樗歉鶕?jù)用戶之間的相似度決定的，用戶之間的興趣點(diǎn)是相似但是不會(huì)都相同的，所以可以削弱馬太效應(yīng)。而對(duì)于ItemCF，這個(gè)物品相似度是死的，相似的基本都很相似，所以可能會(huì)有很大的長(zhǎng)尾，一般是用戶需求很強(qiáng)烈的地方使用。還有冷啟動(dòng)問(wèn)題，對(duì)于一個(gè)新用戶進(jìn)來(lái)的時(shí)候，不能立刻對(duì)他進(jìn)行推薦，因?yàn)橛脩舻南嗨贫染仃囀且欢螘r(shí)間后離線計(jì)算的，新物品上線之后一旦有用戶對(duì)這個(gè)商品產(chǎn)生行為就可以將物品推薦給它產(chǎn)生行為的用戶了。但是這樣就沒(méi)有辦法在不離線更新相似度表的情況下將新物品推薦給用戶了。還有就是推薦理由，對(duì)于UserCF，用一個(gè)我根本不認(rèn)識(shí)的人的習(xí)慣來(lái)推薦給我，對(duì)于用戶的說(shuō)服力肯定是不夠的，商品就不一樣了，商品是死的。

CF的優(yōu)缺點(diǎn)

優(yōu)點(diǎn)：基于用戶的行為對(duì)于推薦內(nèi)容是不需要先驗(yàn)知識(shí)的，只需要建立用戶或者是商品的相似矩陣即可，結(jié)構(gòu)很簡(jiǎn)單，在用戶豐富的情況下效果很好，而且很簡(jiǎn)單。
缺點(diǎn)：需要大量的行為，也就是歷史數(shù)據(jù)，需要通過(guò)完全相同的商品關(guān)聯(lián)起來(lái)，相似的不行。而且·使用CF是有前提的了，要求就是用戶只會(huì)完全取決于之前的行為，上下文是沒(méi)有關(guān)系的了。而且在數(shù)據(jù)稀疏的情況下效果是不好的，還可能需要二度關(guān)聯(lián)，因?yàn)槿绻幌律唐窙](méi)有什么人買(mǎi)，基本就沒(méi)得推薦了。

基于隱語(yǔ)義的推薦

基于隱語(yǔ)義的推薦，其實(shí)就是矩陣分解。之前寫(xiě)過(guò)一篇叫Matrix Factorization的文章講的就是這個(gè)：http://www.itdecent.cn/p/af49053832c5
首先對(duì)用戶進(jìn)行一些簡(jiǎn)單的編碼，因?yàn)橛脩羧绻前衙钟浬先ナ亲霾涣擞?jì)算的，所以我們把用戶進(jìn)行編碼，比如有4個(gè)用戶，一號(hào)用戶就 $[1,0,0,0]$ ，二號(hào) $[0,1,0,0]$ 等等以此類推。

如果是使用神經(jīng)網(wǎng)絡(luò)來(lái)解決這個(gè)問(wèn)題，首先就是要設(shè)計(jì)一個(gè)網(wǎng)絡(luò)，

N-d-M

，N輸入用戶的數(shù)量，d就是網(wǎng)絡(luò)的維度，M就是輸出的結(jié)果，M就是物品的數(shù)量，因?yàn)樽詈蟮妮敵鼍褪怯脩魧?duì)商品的評(píng)分。

但實(shí)際上還是有一個(gè)問(wèn)題，就是對(duì)于激活函數(shù)，也就是非線性函數(shù)是否需要的問(wèn)題。事實(shí)上是不需要的，因?yàn)槿绻挥幸粋€(gè)

x

是有效的，那么這個(gè)

x

就是只有一行有效的，所以只會(huì)有一個(gè)x經(jīng)過(guò)了tanh函數(shù)，從效果上講一個(gè)tanh(x)和x是沒(méi)有什么區(qū)別的。所以可以忽略非線性：

整合一下公式

h(x) = W^TVx

由于x就是一行有效，所以

h(x) = W^Tv_n

所以，第m個(gè)用戶的第n個(gè)商品的評(píng)分就是

r_{nm} = w_{m}^Tv_n

這樣就分解得到了我們要的公式，最后求導(dǎo)即可。事實(shí)上分解出來(lái)的兩個(gè)矩陣?yán)锩娴淖兞看淼臄?shù)據(jù)的意義其實(shí)是不明確的，也就是說(shuō)比較抽象，怎么想象都行。分解出來(lái)的矩陣

R_{nxk},Q_{kxm}

，k代表的就是分解的度，分解的越多有可能會(huì)過(guò)擬合，所以這里也是可以加正則化的。

不要嘗試的去理解所有分解的贏語(yǔ)義，這是沒(méi)有意義的，比如神經(jīng)網(wǎng)絡(luò)的每一個(gè)神經(jīng)元，事實(shí)上你們是不知道他們到底是在干什么，只是知道他們?cè)谟^察而又，這里也是一樣的，這里面分解出來(lái)的東西，如果是電影，你可以說(shuō)是喜劇成分，武大成分，也可以說(shuō)是演員等等，相當(dāng)于一指示變量而已，只是指明了這個(gè)物品是多少分，但是沒(méi)有給出具體的意義。
具體的公式之前的博客都有，例子也提到，這里就不重復(fù)了。

上面提到的只是最簡(jiǎn)單的MF模型，但是這類模型有一個(gè)缺點(diǎn)，他們分解出來(lái)的東西會(huì)有負(fù)數(shù)，這就尷尬了，因?yàn)楹苌儆凶兞恳蛩貢?huì)其負(fù)作用的，于是便出現(xiàn)了非負(fù)矩陣分解。

非負(fù)矩陣分解出現(xiàn)的根本原因就矩陣分解解釋性差的問(wèn)題。

NMF

矩陣非負(fù)分解，這個(gè)就有點(diǎn)厲害了。首先引入一下KL離散度： $D(A|B) = \sum_{i,j}(A_{i,j}log \frac{A}{B}-A_{i,j}+B_{i,j})$

KL損失函數(shù)

對(duì)于KL散度的推導(dǎo)其實(shí)很簡(jiǎn)單：
$f(x) - f(x_0) = \nabla f(x_0)(x-x_0) \\ f(y) = f(x) - \nabla f(x) (x-y)$ 所以一階Tayor逼近的誤差是： $f(x) - f(y) - \nabla f(x) (x-y)$ 代入熵 $f(x) = \sum_{i=1}^k x_iInx_i$ ： $D(x||y) = xInx - yIny - (Iny + 1)(x-y) \\ D(x||y) = xlog \frac{x}{y} - x + y$ 這樣推導(dǎo)出來(lái)了。平方差損失函數(shù)對(duì)應(yīng)著高斯分布，那么KL肯定也對(duì)應(yīng)著另一個(gè)分布——泊松分布： $P(X = x) = \frac{\lambda ^x}{x!}e^{-\lambda} \\ P_1(X = x) = \frac{\lambda_1 ^x}{x!}e^{-\lambda_1} \\ P_2(X = x) = \frac{\lambda_2 ^x}{x!}e^{-\lambda_2} \\ In \frac{P_1(X=x)}{P_2(X = x)} = xIn \frac{\lambda_1}{\lambda_2} - \lambda_1 + \lambda_2$ 因?yàn)?img class="math-inline" src="https://math.jianshu.com/math?formula=x" alt="x" mathimg="1">是隨機(jī)數(shù)，所以求一下期望： $\sum_{x = 0}^{+\infty}P_1(X=x)In(\frac{P_1(X=x)}{P_2(X=x)}) = \sum_{i=1}^{+ \infty}P_1{X=x}[xIn \frac{\lambda_1}{\lambda_2}-\lambda_1+\lambda_2] \\ = \lambda_1 In \frac{\lambda_1}{\lambda_2}-\lambda_1 + \lambda_2$ 所以KL離散度就對(duì)應(yīng)了泊松分布。

對(duì)于這個(gè)KL離散度： $D(A|B) = \sum_{i,j}(A_{i,j}log \frac{A}{B}-A_{i,j}+B_{i,j})$ KL離散度一定是大于等于0的，當(dāng) $A == B$ 的時(shí)候，這個(gè)離散度就是等于0的了，所以我們要求的就是不斷的 $minimizeD(A||B)$ 即可。
所以現(xiàn)在NMF的損失函數(shù)有兩種了①均方差損失函數(shù): $loss = \frac{1}{2}(y - y')^2$ ；②KL離散度： $loss = \sum_{i,j}(A_{i,j}log \frac{A}{B}-A_{i,j}+B_{i,j})$ ，還是用第一種吧！
問(wèn)題來(lái)了，既然是非負(fù)數(shù)的，怎么保證是正數(shù)是一個(gè)問(wèn)題，這里有一個(gè)很牛逼的技巧：
$loss = [R - (PQ)]^2 \\ \frac{\delta loss}{\delta Q} = 2[R - (PQ)]P \\ = -2[(P^TR)-(P^TPQ)]$
所以更新方式： $Q = Q + n*[(P^TR) - (P^TPQ)]$ 要做的就是設(shè)計(jì)一個(gè)n，使得乘上之后可以抵消前面的Q即可。 $n = \frac{Q}{P^TPQ}$ ，帶進(jìn)去之后： $Q = Q \frac{(P^TR)}{(P^TPQ)} \\ P = P \frac{(RQ^T)}{PQQ^T}$ 使用KL離散也是一樣的。

代碼實(shí)現(xiàn)

def train(V, r, maxCycles, e):
    m, n = np.shape(V)
    W = np.mat(np.random.random((m, r)))
    H = np.mat(np.mat(np.random.random((r, n))))

    for step in range(maxCycles):
        V_pre = W * H
        E = V - V_pre
        err = 0.0
        for i in range(m):
            for j in range(n):
                err += E[i, j] * E[i, j]
        if err < e:
            break
        if step % 1000 == 0:
            print("\Interator: ", step, " Loss: ", err)
        a = W.T * V
        b = W.T * W * H
        for i in range(r):
            for j in range(n):
                if b[i, j] != 0:
                    H[i, j] = H[i, j] * a[i, j] / b[i, j]
        c = V * H.T
        d = W * H * H.T
        for i in range(m):
            for j in range(r):
                if d[i, j] != 0:
                    W[i, j] = W[i, j] * c[i, j] / d[i, j]
    return W, H

效果：

效果還是可以的。

CF VS隱語(yǔ)義

隱語(yǔ)義其實(shí)還有一種分解方式，就是SVD，SVD也可以的，但是SVD的分解是 $O(m^3)$ ，而且如果原矩陣是有很多缺省值的話，那么SVD就會(huì)用0填充，這樣不太好的。相比之下CF跟簡(jiǎn)單，而且可解釋性也強(qiáng)，但是隱語(yǔ)義模型可以挖掘出更深層的物體或者是用戶之間的關(guān)系，覆蓋性會(huì)更好，雙方各有優(yōu)缺點(diǎn)。

基于圖的推薦

PageRank Algorithm

首先要提到的就是PageRank算法，等下還要改進(jìn)一下這個(gè)算法才會(huì)得到真正的推薦系統(tǒng)算法。這個(gè)算法是在Google初期使用的一個(gè)網(wǎng)頁(yè)排序算法，用于對(duì)網(wǎng)頁(yè)重要性的排序。一開(kāi)始的網(wǎng)頁(yè)排序都是按照人工篩選或者是關(guān)鍵詞篩選的，但是這樣效率不高而且效果不好，經(jīng)常是有很多網(wǎng)頁(yè)有很多重復(fù)關(guān)鍵詞的然后被置頂，這個(gè)時(shí)候就需要一個(gè)新的方法來(lái)重新評(píng)估網(wǎng)頁(yè)的質(zhì)量，重新排序了。
把互聯(lián)網(wǎng)上的網(wǎng)頁(yè)模擬成一個(gè)節(jié)點(diǎn)，出鏈就是指向其他網(wǎng)頁(yè)的一條有向邊，也就是當(dāng)前這個(gè)網(wǎng)頁(yè)有一條指向其他網(wǎng)頁(yè)的邊，入鏈就是一個(gè)指向當(dāng)前頁(yè)面的邊，也就是說(shuō)有一個(gè)網(wǎng)頁(yè)是指向了當(dāng)前這個(gè)網(wǎng)頁(yè)的。這個(gè)時(shí)候當(dāng)前網(wǎng)頁(yè)就是其他網(wǎng)頁(yè)轉(zhuǎn)進(jìn)來(lái)的了。所以網(wǎng)頁(yè)評(píng)估是帶有以下的兩個(gè)假設(shè)的：數(shù)量假設(shè)：一個(gè)網(wǎng)頁(yè)的入度，也就是入鏈越大，質(zhì)量越高。質(zhì)量假設(shè)：一個(gè)節(jié)點(diǎn)的入度來(lái)源質(zhì)量越高，那么當(dāng)前節(jié)點(diǎn)質(zhì)量就越高。但是，問(wèn)題來(lái)了，網(wǎng)頁(yè)A和網(wǎng)頁(yè)B的質(zhì)量有關(guān)系，網(wǎng)頁(yè)B又和網(wǎng)頁(yè)C有關(guān)系，以此類推要是網(wǎng)頁(yè)C又和A有關(guān)系那就陷入了循環(huán)里面了。這樣就解不出來(lái)了，所以簡(jiǎn)化一下模型，假設(shè)，所有的網(wǎng)頁(yè)都和前一個(gè)網(wǎng)頁(yè)有關(guān)系，這樣就叫隨機(jī)游走模型，也就是一階馬爾科夫模型。隨機(jī)游走可以看做是馬爾科夫鏈的一種特例。也叫做醉漢模型，沒(méi)一次走的方向或者步數(shù)只于前一次走的有關(guān)系而已，這一點(diǎn)有點(diǎn)像布朗運(yùn)動(dòng)。
現(xiàn)在將這個(gè)模型數(shù)學(xué)化一下下，假設(shè)現(xiàn)在有N個(gè)網(wǎng)頁(yè)，一開(kāi)始初始化肯定每一個(gè)網(wǎng)頁(yè)的概率都是一樣大的，都是 $\frac{1}{N}$ ，比如下圖：

每一個(gè)網(wǎng)頁(yè)的概率就是

[\frac{1}{4},\frac{1}{4},\frac{1}{4},\frac{1}{4}]

，每一個(gè)網(wǎng)頁(yè)轉(zhuǎn)向其他網(wǎng)頁(yè)的概率都是一樣的：

\left\{ \begin{matrix} 0 & \frac{1}{2} & 1 & 0 \\ \frac{1}{3} & 0 & 0 & \frac{1}{2}\\ \frac{1}{3} & 0 & 0 & \frac{1}{2}\\ \frac{1}{3} & \frac{1}{2} & 0 & 0 \end{matrix} \right\}

記這個(gè)矩陣為

T

矩陣，

T[i][j]

代表的就網(wǎng)頁(yè)j跳轉(zhuǎn)到網(wǎng)頁(yè)i的概率，

\sum_{j=1}^n T[i][j] = 1

。根據(jù)這個(gè)矩陣，我們是可以計(jì)算出用戶訪問(wèn)每一個(gè)網(wǎng)頁(yè)的概率：

V_1 = T*V_{0} = \left\{ \begin{matrix} 0 & \frac{1}{2} & 1 & 0 \\ \frac{1}{3} & 0 & 0 & \frac{1}{2}\\ \frac{1}{3} & 0 & 0 & \frac{1}{2}\\ \frac{1}{3} & \frac{1}{2} & 0 & 0 \end{matrix} \right\} * \left\{ \begin{matrix} \frac{1}{4} \\ \frac{1}{4} \\ \frac{1}{4} \\ \frac{1}{4} \end{matrix} \right\} = \left\{ \begin{matrix} \frac{9}{24} \\ \frac{5}{24} \\ \frac{5}{24} \\ \frac{5}{24} \end{matrix} \right\} \\ V_n = T*V_{n-1} = T^n * V_0

當(dāng)?shù)啻沃螅?div id="u0z1t8os" class="image-package">

V_n

這個(gè)矩陣會(huì)最終穩(wěn)定下來(lái)，這個(gè)矩陣叫馬爾科夫矩陣。

矩陣T的條件

對(duì)于轉(zhuǎn)移矩陣T是存在條件的：
①T要是隨機(jī)矩陣：所有元素大于0，而且要求列相加要是等于1的。
②T是不可約的：所謂的不可約就是強(qiáng)連通性，即圖中任何一個(gè)節(jié)點(diǎn)可以到達(dá)其他任何一個(gè)節(jié)點(diǎn)。比如有某一個(gè)節(jié)點(diǎn)是不能到達(dá)任何一個(gè)節(jié)點(diǎn)的，在那個(gè)節(jié)點(diǎn)所在的列都是0，或者是只有回到自己，也就是自環(huán)路。這兩種就是在后面提到的終止點(diǎn)和陷阱了。
③T要是非周期的：也就是符合馬爾科夫鏈的周期性變化。

周期性迭代之后最終結(jié)果會(huì)固定住，比如上面的結(jié)果就是 $[\frac{3}{9},\frac{2}{9},\frac{2}{9},\frac{2}{9}]^T$ ，也就是說(shuō)第一個(gè)頁(yè)面訪問(wèn)的頻率是很高的。

終止點(diǎn)

終止點(diǎn)就是指沒(méi)有任何出鏈的網(wǎng)頁(yè)，比如：

節(jié)點(diǎn)C就是一個(gè)終止點(diǎn)。

\left\{ \begin{matrix} 0 & \frac{1}{2} & 0 & 0 \\ \frac{1}{3} & 0 & 0 & \frac{1}{2}\\ \frac{1}{3} & 0 & 0 & \frac{1}{2}\\ \frac{1}{3} & \frac{1}{2} & 0 & 0 \end{matrix} \right\}

這樣的結(jié)果顯然是毫無(wú)意義的。但是這并不意味著涼了，任何的算法都是人想出來(lái)的，也就是模擬人的做法。如果你遇到一個(gè)直進(jìn)不出的網(wǎng)站，那么肯定是開(kāi)溜去另外一個(gè)網(wǎng)站，所以遇到這種情況，那直接就是退出去啊。所以遇到這種情況就是直接把這個(gè)圖的終止點(diǎn)改成到每一個(gè)節(jié)點(diǎn)都有一條邊，因?yàn)橥顺鲋匦逻x擇網(wǎng)頁(yè)就相當(dāng)于是從這個(gè)網(wǎng)頁(yè)轉(zhuǎn)移到其他網(wǎng)頁(yè)去了。成功改變結(jié)果。

陷阱

只是指向了自己，多次收斂之后：

這個(gè)結(jié)果也是毫無(wú)意義的。同樣，一個(gè)用戶是不可能總是在一個(gè)網(wǎng)頁(yè)里面打轉(zhuǎn)。剛剛的添加轉(zhuǎn)移的邊方法也是可以的，但是比較常用的一種方法是用一個(gè)概率轉(zhuǎn)移的方法，沒(méi)一次用戶不是都是一定會(huì)按照狀態(tài)轉(zhuǎn)移矩陣走的，所以可以加上一個(gè)退出的概率。

V_n = \alpha TV_{n-1}+ (1-\alpha)V_0

這樣就穩(wěn)了。

Summary

首先一個(gè)就是鏈接的質(zhì)量問(wèn)題，有很多導(dǎo)航欄的鏈接是不能和正常的跳轉(zhuǎn)鏈接相比較的，比如CSDN兩邊的那些博客，都是自己寫(xiě)的，這些很影響判斷的。還有一個(gè)就是沒(méi)有過(guò)濾廣告的鏈接，這些也是影響判斷的。還有一個(gè)是類似于冷啟動(dòng)的問(wèn)題，一個(gè)新網(wǎng)友如果是剛剛加了進(jìn)來(lái)，一般是沒(méi)有什么入度的，出度可能有，可能還要花些時(shí)間適應(yīng)。

對(duì)于PageRank的公式化

每一個(gè)節(jié)點(diǎn)我們都給一個(gè)PR值給他們，也就是說(shuō)會(huì)根據(jù)這個(gè)PR值來(lái)判斷哪個(gè)網(wǎng)站走的概率最大。

這個(gè)時(shí)候

PR(A) = PR(B)+PR(C)

，然而，圖中的B是不止一條的，B到A有兩條路徑，那么就是二分之一了，所以

PR(A) = \frac{PR(B)}{2}+\frac{PR(C)}{1}

，不斷往下迭代即可。所以一個(gè)網(wǎng)頁(yè)的迭代公式：

PR(i) = \alpha \sum_{j \in in(i)} \frac{PR(j)}{|L(P_j)|}+\frac{(1-\alpha)}{4}

N表示網(wǎng)頁(yè)總數(shù)，in(i)表示的是指向網(wǎng)頁(yè)i的網(wǎng)頁(yè)集合，out(j)表示的就是網(wǎng)頁(yè)j指向的網(wǎng)頁(yè)集合。后面代碼實(shí)現(xiàn)就是按照這個(gè)。

馬爾科夫鏈的收斂性的證明

這個(gè)就有點(diǎn)牛逼了。
$T = \alpha T + \frac{(1-\alpha)}{N}ee^T \\ P_{n+1} = TP_{n}$
對(duì)于收斂性，有三個(gè)性質(zhì)要證明的：

存在一個(gè)特征值 $\lambda = 1$

假設(shè)一個(gè)向量 $1_n = [1,1,...,1]^T$ ，由于每一列相加都是1，所以 $1_n^TT = 1_n^T = A^T1_n = 1_n$ 這個(gè)是直接根據(jù)性質(zhì)證明的。

存在的特征值都是 $|\lambda| <= 1$

假設(shè)一個(gè)函數(shù) $s(x) = \sum_{i=1}^n x_i$ ，假設(shè) $T^2_i$ 代表的就是列向量，那么有： $s(T^2_l) = s(\sum_{i=1}^na_iali) = \sum_{i=1}^n s(a_i)a_{li} = \sum_{i=1}^na_{li} = 1$ 所以， $T^2$ 就還是馬爾科夫矩陣，無(wú)論上面疊多少次方都還是。根據(jù)特征值的冪還有特征向量有 $T^n x = \lambda^n x$ ，如果 $\ambda > 1$ 那么就是無(wú)限大了，但是馬爾科夫矩陣是小于1的，所以和假設(shè)矛盾 $\lambda <= 1$ 。

收斂性

$T^n u_0 = c_11^nx_1 + c_2 \lambda^n_2x_2+c_3 \lambda^n_3x_3+......+c_n \lambda^n_nx_n$ 因?yàn)橹挥幸粋€(gè)特征值是1的，其他都是小于1的，n次方更不要說(shuō)了，所以迭代多次之后絕壁收斂，實(shí)錘。參考：http://blog.sina.com.cn/s/blog_80ce3a550102xas8.html
這樣就完整證明了PageRank算法。

代碼實(shí)現(xiàn)

from pygraph.classes.digraph import digraph
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt

class pageRank(object):

    def __init__(self, dg):
        self.alpha = 0.85
        self.maxCycles = 200
        self.min_delta = 0.0001
        self.graph = dg

    def page_rank(self):
        #沒(méi)有出鏈的點(diǎn)先加上和所有點(diǎn)的邊
        for node in self.graph.nodes():
            if len(self.graph.neighbors(node)) == 0:
                for node2 in self.graph.nodes():
                    digraph.add_edge(self.graph, (node, node2))
        nodes = self.graph.nodes()
        graphs_size = len(nodes)

        if graphs_size == 0:
            return 'nodes set is empty!'

        page_rank = dict.fromkeys(nodes, 1.0/graphs_size)
        runAway = (1.0 - self.alpha) / graphs_size
        flag = False
        for i in range(self.maxCycles):
            change = 0
            for node in nodes:
                rank = 0
                for incident_page in self.graph.incidents(node):
                    rank += self.alpha * (page_rank[incident_page] / len(self.graph.neighbors(incident_page)))
                rank += runAway
                change += abs(page_rank[node] - rank)
                page_rank[node] = rank

            print("NO.%s iteration" % (i + 1))
            print(page_rank)

            if change < self.min_delta:
                flag = True
                break
        return page_rank

導(dǎo)入數(shù)據(jù)代碼我懶得寫(xiě)了，直接用了一個(gè)包里面的。

if __name__ == '__main__':
    dg = digraph()

    dg.add_nodes(["A", "B", "C", "D", "E"])

    dg.add_edge(("A", "B"))
    dg.add_edge(("A", "C"))
    dg.add_edge(("A", "D"))
    dg.add_edge(("B", "D"))
    dg.add_edge(("C", "E"))
    dg.add_edge(("D", "E"))
    dg.add_edge(("B", "E"))
    dg.add_edge(("E", "A"))

    pr = pageRank(dg)
    page_ranks = pr.page_rank()

    print("The final page rank is\n", page_ranks)

最后效果：

好像和推薦系統(tǒng)扯遠(yuǎn)了，但是這個(gè)算法要用到后面退出PersonalRank算法。

PersonalRank Algorithm

在PageRank算法中，計(jì)算出的PR值是每一個(gè)節(jié)點(diǎn)相對(duì)于全局的重要性程度，而在推薦問(wèn)題里面要求的是商品對(duì)于用戶的重要性了，而不是全局的重要性。比如，當(dāng)這個(gè)用戶U1計(jì)算的時(shí)候，就要遍歷所有的商品進(jìn)行計(jì)算，看看哪個(gè)商品的重要性相對(duì)于這個(gè)用戶是最高的就推薦即可。
PersonalRank Algorithm是PageRank的變形，用于計(jì)算商品節(jié)點(diǎn) $D_j$ 相對(duì)于用戶節(jié)點(diǎn)U的重要程度。假設(shè)用戶為 $U_1$ ，則從節(jié)點(diǎn) $U_1$ 開(kāi)始在用戶——商品二部圖中游走，游走到容易一個(gè)節(jié)點(diǎn)的時(shí)候，和PageRank算法一樣，會(huì)按照一定的概率選擇停止或者繼續(xù)游走。直到每一個(gè)節(jié)點(diǎn)訪問(wèn)的概率不再變化位置。
首先引入二部圖：

二部圖是無(wú)向圖的一種，若無(wú)向圖

G=<V,E>

中，其中，V是無(wú)向圖中的頂點(diǎn)的集合，E是無(wú)向圖中邊的集合。在無(wú)向圖G中，邊的集合V可以分成兩個(gè)子集

V_1,V_2

，而且滿足這兩個(gè)子集交集為空?；氐絇ersonalRank算法，在這個(gè)算法中不用區(qū)分用戶和商品，上述節(jié)點(diǎn)的感興趣程度就變成了對(duì)用戶

U_1

計(jì)算各個(gè)節(jié)點(diǎn)

U_2,...,U_5,D_1,...,D_5

的重要程度。算法具體流程：
①初始化： $PR(U_1) = 1,PR(U_2) = 0,...,PR(U_5) = 0,PR(D_1) = 0,...,PR(D_5) = 0$ 。
②開(kāi)始在圖上游走，每次選擇PR值不為0的節(jié)點(diǎn)開(kāi)始，沿著邊往前的概率為 $\alpha$ ，停在當(dāng)前點(diǎn)的概率就是 $1-\alpha$ 了。
③首先U1開(kāi)始，從U1到D2,D3,D4的概率就是 $\frac{1}{3}$ ，則此時(shí)D1,D2和D4的PR就是 $\alpha*PR(U_1)*\frac{1}{3}$ ，U1的PR值就變成了 $1-\alpha$ 。
④此時(shí)PR值不為0的節(jié)點(diǎn)為 $U_1,D_1,D_2,D_4$ ，則此時(shí)從這三點(diǎn)出發(fā)，繼續(xù)上述的過(guò)程直到收斂為止。所以更新公式為： $PR(i) = (1-\alpha)r_i + \alpha \sum_{j \in in(i)} \frac{PR(j)}{|out(j)|} \\ r_i = 1:0?i = u$ 如果是在當(dāng)前節(jié)點(diǎn)那么就要加上一個(gè)停留的概率了。

代碼實(shí)現(xiàn)

def generate_dict(dataTmp):
    m, n = np.shape(dataTmp)
    data_dict = {}
    for i in range(m):
        tmp_dict = {}
        for j in range(n):
            if dataTmp[i, j] != 0:
                tmp_dict["D_" + str(j)] = dataTmp[i, j]
        data_dict["U_" + str(i)] = tmp_dict
    for j in range(n):
        tmp_dict = {}
        for i in range(m):
            if dataTmp[i, j] != 0:
                tmp_dict["U_" + str(i)] = dataTmp[i, j]
        data_dict["D_" + str(j)] = tmp_dict
    return data_dict

轉(zhuǎn)換成二部圖。


def PersonalRank(data_dict, alpha, user, maxCycles):
    rank = {}
    for x in data_dict.keys():
        rank[x] = 0
    rank[user] = 1
    step = 0
    while step < maxCycles:
        tmp = {}
        for x in data_dict.keys():
            tmp[x] = 0
        for i, ri in data_dict.items():
            for j in ri.keys():
                if j not in tmp:
                    tmp[j] = 0
                tmp[j] += alpha * rank[i] / (1.0 * len(ri))
                if j == user:
                    tmp[j] += (1-alpha)
        check = []
        for k in tmp.keys():
            check.append(tmp[k] - rank[k])
        if sum(check) <= 0.0001:
            break
        rank = tmp
        if step % 20 == 0:
            print('NO: ', step)
        step += 1
    return rank

效果：

最后附上GitHub代碼：https://github.com/GreenArrow2017/MachineLearning/tree/master/MachineLearning/Recmmended%20System

最后編輯于：2018.09.29 17:18:33

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書(shū)系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

Recommended System

推薦系統(tǒng)

推薦系統(tǒng)的評(píng)估方法

準(zhǔn)確度

覆蓋率

多樣性

冷啟動(dòng)

相似度的衡量

推薦算法

基于內(nèi)容的推薦

基于關(guān)聯(lián)規(guī)則的推薦

協(xié)同過(guò)濾的推薦

基于知識(shí)的推薦

基于圖的推薦

組合推薦

基于內(nèi)容的推薦系統(tǒng)

協(xié)同過(guò)濾的推薦

user-based CF

item_based CF

user-based vs item-based

CF的優(yōu)缺點(diǎn)

基于隱語(yǔ)義的推薦

NMF

KL損失函數(shù)

代碼實(shí)現(xiàn)

CF VS隱語(yǔ)義

基于圖的推薦

PageRank Algorithm

矩陣T的條件

終止點(diǎn)

陷阱

Summary

對(duì)于PageRank的公式化

馬爾科夫鏈的收斂性的證明

存在一個(gè)特征值

存在的特征值都是

收斂性

代碼實(shí)現(xiàn)

PersonalRank Algorithm

代碼實(shí)現(xiàn)

最后附上GitHub代碼：https://github.com/GreenArrow2017/MachineLearning/tree/master/MachineLearning/Recmmended%20System

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

存在一個(gè)特征值 $\lambda = 1$

存在的特征值都是 $|\lambda| <= 1$