目錄
1、Personal Rank 算法背景
2决侈、二分圖的概念
3词渤、文件解析原理及其物理意義
4牵舱、PR公式推導(dǎo)
5、python實(shí)現(xiàn)
6缺虐、總結(jié)
Personal Rank算法背景：
用戶(hù)行為很容易表示為圖
圖推薦在個(gè)性化推薦領(lǐng)域效果顯著芜壁，UI矩陣就是典型的二分圖。
二分圖：又稱(chēng)為二部圖高氮，是圖論中的一種特殊模型慧妄。設(shè)G=(V,E)是一個(gè)無(wú)向圖，如果頂點(diǎn)V可分割為兩個(gè)互不相交的子集（A,B）剪芍，并且圖中的每條邊（i,j）所關(guān)聯(lián)的兩個(gè)頂點(diǎn)i和j分別屬于這兩個(gè)不同的頂點(diǎn)集（i in A塞淹，i in B），則稱(chēng)圖G為一個(gè)二分圖紊浩。
下面舉例并從物理意義角度解析窖铡，二分圖算法是如何將UI矩陣表示為二分圖，計(jì)算出Item集合對(duì)固定user的重要程度排序?
1坊谁、兩個(gè)頂點(diǎn)之間連通的路徑數(shù)费彼？
A到c：A->a->B->c；A->d->D->c兩條連通路徑口芍；
A到e：A->b->C->e一條連通路徑
故箍铲，A對(duì)物品c的偏好程度大于對(duì)物品e的偏好。
2鬓椭、兩個(gè)頂點(diǎn)之間的連通路徑長(zhǎng)度颠猴？
A->c兩條路徑4個(gè)頂點(diǎn)，連通路徑長(zhǎng)度都是3小染；A->e也為3
3翘瓮、兩個(gè)頂點(diǎn)之間連通路徑經(jīng)過(guò)頂點(diǎn)的初度？
A到c：A->a->B->c：3+2+2+2裤翩；A->d->D->c：3+2+2+2
A到e：A->b->C->e：3+2+2+1
可見(jiàn)资盅，PR算法是將UI矩陣表示為二分圖存儲(chǔ)后，通過(guò)統(tǒng)計(jì)兩頂點(diǎn)連通路徑長(zhǎng)度踊赠、連通路徑數(shù)以及頂點(diǎn)初度信息來(lái)計(jì)算Item集合每個(gè)Item對(duì)固定user的重要程度的一種算法呵扛。
算法文字描述：對(duì)用戶(hù)A進(jìn)行個(gè)性化推薦，從用戶(hù)A結(jié)點(diǎn)開(kāi)始在用戶(hù)物品二分圖random walk 筐带，以alpha的概率從A的出邊中等概率選擇一條游走過(guò)去今穿，到達(dá)頂點(diǎn)后（例如a），有alpha的概率繼續(xù)從頂點(diǎn)a的出邊中等概率選擇一條繼續(xù)游走到下一個(gè)結(jié)點(diǎn)伦籍，或者（1-alpha）的概率回到起點(diǎn)A蓝晒，多次迭代腮出。直到所有的頂點(diǎn)對(duì)于用戶(hù)A的重要度收斂。（二分圖有且只有一個(gè)頂點(diǎn)）
算法公式推導(dǎo)：
按照上面UI矩陣的二分圖表示法結(jié)合算法文字描述拔创，以節(jié)點(diǎn)A和a來(lái)舉例解釋公式利诺。
：表示不同節(jié)點(diǎn)重要度。
以a為例剩燥，公式上部分表示節(jié)點(diǎn)a與之相連的節(jié)點(diǎn)A和B慢逾，分別從各自出邊等概率貢獻(xiàn)了1/3和1/2的重要度加和后乘以，
取經(jīng)值為0-1之間（經(jīng)驗(yàn)值0.6）灭红。
以A為例侣滩，公式下部分表示與A相連的節(jié)點(diǎn)a,b,d，分別從各自的出邊等概率貢獻(xiàn)了1/2的重要度变擒，同時(shí)它們又是直接與A相連的節(jié)點(diǎn)君珠，從PR算法文字描述可知，都可以以1-的概率回到A節(jié)點(diǎn)娇斑。
公式（1）的矩陣表達(dá)方式為： (2)
其中是n維向量策添，每一個(gè)元素代表一個(gè)節(jié)點(diǎn)的PR重要度；
也是n維向量毫缆，第i個(gè)位置為1唯竹，其余位置為0，我們就是要為第i個(gè)節(jié)點(diǎn)進(jìn)行推薦苦丁。其中
是n階轉(zhuǎn)移矩陣：
?
由（2）進(jìn)行恒等變形可得
(3)
(4) 浸颓，其中
就是所有節(jié)點(diǎn)的推薦結(jié)果，乘以
就是取出矩陣的第i列旺拉。
Python實(shí)現(xiàn)：https://github.com/SolodanceMagicq/RecommendSys/tree/master/PersonalRank
總結(jié)：
1产上、personalrank二分圖算法，是一種無(wú)向圖蛾狗，有且只有一個(gè)root頂點(diǎn)晋涣。
2、算法核心思想是將UI矩陣以二分圖存儲(chǔ)沉桌，通過(guò)頂點(diǎn)按等概率隨機(jī)游走谢鹊，迭代計(jì)算關(guān)聯(lián)節(jié)點(diǎn)pr值的過(guò)程。首次迭代只計(jì)算推薦用戶(hù)（root頂點(diǎn)）與其直接關(guān)聯(lián)的節(jié)點(diǎn)pr值蒲牧，然后每次基于上次節(jié)點(diǎn)進(jìn)一步迭代計(jì)算關(guān)聯(lián)節(jié)點(diǎn)，直至收斂赌莺。
3冰抢、PersonalRank算法迭代的時(shí)間復(fù)雜度過(guò)高，須進(jìn)一步優(yōu)化艘狭，工業(yè)界一般會(huì)借助spark離線(xiàn)計(jì)算或mapreduce將多節(jié)點(diǎn)并行計(jì)算提高計(jì)算性能挎扰。
