基于協(xié)同過濾算法的推薦系統(tǒng)設(shè)計(jì)

□邵 娜

隨著互聯(lián)網(wǎng)的迅速普及，大量的信息充斥著人們的生活，這種現(xiàn)象稱為信息超載。面對(duì)這一現(xiàn)象，推薦系統(tǒng)應(yīng)運(yùn)而生。推薦系統(tǒng)結(jié)合推薦算法，通過分析數(shù)據(jù)庫中記錄的興趣愛好，進(jìn)行個(gè)性化計(jì)算，由系統(tǒng)分析得到推薦信息，引領(lǐng)用戶發(fā)現(xiàn)自己真實(shí)需要的物品信息。

一、協(xié)同過濾的推薦算法

本系統(tǒng)設(shè)計(jì)假定用戶與商品評(píng)價(jià)之間是最簡(jiǎn)單的線性關(guān)系，我們將基于這種最簡(jiǎn)單的線性關(guān)系來敘述數(shù)據(jù)挖掘是如何計(jì)算參數(shù)的。當(dāng)要處理更復(fù)雜的關(guān)系時(shí)，需要做的就是替換這種關(guān)系，但模型及算法步驟是很相似的。

(一)線性回歸。假定有一組數(shù)據(jù)記作xi,其中i=1,2,…n這是定義域，值域也就是輸出yi,i=1,2,…n，yi=theta0+theta1*xi，這就是假定的線性關(guān)系。數(shù)據(jù)挖掘的一般過程如下。

1.觀測(cè)數(shù)據(jù)。進(jìn)行統(tǒng)計(jì)假設(shè)，可以假設(shè)數(shù)據(jù)近似服從線性關(guān)系y=theta0+theta1*x,同時(shí)這個(gè)數(shù)學(xué)表達(dá)也就是我們的目標(biāo)函數(shù)。

2.建立代價(jià)函數(shù)。假設(shè)后要建立標(biāo)準(zhǔn)，看假設(shè)與實(shí)際情況相差如何，利用常用的代價(jià)函數(shù)最小二乘法以求出最優(yōu)參數(shù)：J=sum(theta0-theta1*x-yi)2/n。將這個(gè)表達(dá)式記作J，要求的就是使J達(dá)到最小的theta=[theta0;theta1]。

3.求解代價(jià)函數(shù)的梯度。這是一個(gè)具有凸性的函數(shù)。利用凸優(yōu)化的方法求出全局最優(yōu)解。其核心部分就是求解代價(jià)函數(shù)的梯度，這里我們對(duì)theta進(jìn)行求偏導(dǎo)，以得出梯度，

J'=X*(X*theta-y)/m。

4.梯度下降法。給定theta的初值，我們計(jì)算代價(jià)函數(shù)在每個(gè)點(diǎn)的梯度，讓參數(shù)沿梯度反方向移動(dòng)一個(gè)很小的值，然后再重新計(jì)算梯度，直到算法收斂，這就是梯度下降法。用該方法得到的線性回歸結(jié)果。其中核心代碼在MATLAB中如下：

for r=1:num_iters

theta=theta-alpha*X'*(X*theta-y)/m;

Theta(:,r)=theta;

end

(二)協(xié)同過濾。協(xié)同過濾算法架構(gòu)較為復(fù)雜，但具體到每一步其實(shí)很簡(jiǎn)單，幾乎和線性回歸一樣。本文將使用的算法是共軛梯度下降法。核心步驟就是計(jì)算代價(jià)函數(shù)的梯度，這一步獨(dú)立于算法，是算法的輸出部分。

X=x-alphasumTj-y*Tj+lambda*x

Tj=Tj-alpha(sumTj-y*x+lambda*Tj)

步驟如下：第一，初始化x和theta，這個(gè)初始化是隨機(jī)的，一般用高斯函數(shù)來產(chǎn)生。注意隨機(jī)不代表隨意，如果胡亂取值，是不會(huì)得到好的結(jié)果的，事實(shí)上收斂速度和你取的初值是有關(guān)聯(lián)的。第二，用梯度下降法來計(jì)算X和theta，方法是固定X用公式f求theta，固定theta，用公式求X。核心代碼如下：J=(X*Theta'-Y).*R;X_grad=J*Theta+lambda*X;Theta_grad=J'*X+lambda*Theta;J=J(:)'*J(:)/2+(Theta(:)'*Theta(:)+X(:)'*X(:))*lambda/2。第三，用共軛梯度下降法反復(fù)迭代直到收斂，得到想要的數(shù)據(jù)關(guān)系。

圖1 正則化后的數(shù)據(jù)

(三)共軛梯度下降算法。首先是數(shù)據(jù)需要進(jìn)行中心化和單位化。比如Y=[5 5 3; 3 2 1; 0 1 3]，中心化后為[2. 33 2.33 0.667 ; 0.333 -0.667 -1.333; -2.667 -1.667 0.667]，然后進(jìn)行單位化，這個(gè)在計(jì)算過程中特別重要，特別是對(duì)參數(shù)lambda的影響。關(guān)于共軛梯度下降法需要注意兩個(gè)關(guān)鍵點(diǎn)，一是收斂條件，選取的是Wolfe-Powell條件。這個(gè)條件講的是，當(dāng)找到梯度之后，沿著這個(gè)梯度方向移動(dòng)最適合。二是共軛梯度的計(jì)算。采用的是Polack-Ribiere共軛梯度法。共軛梯度法并沒有計(jì)算函數(shù)的二次導(dǎo)數(shù)，即Hessian矩陣，而是將Hessian矩陣與數(shù)據(jù)矩陣的乘積看成一個(gè)整體進(jìn)行估計(jì)。

圖2 填充后的結(jié)果

二、系統(tǒng)設(shè)計(jì)

以某個(gè)電影數(shù)據(jù)庫為例，通過系統(tǒng)如下的設(shè)計(jì)原理：第一，將己有數(shù)據(jù)載入，并進(jìn)行預(yù)處理；第二，協(xié)同過濾算法，構(gòu)造代價(jià)函數(shù)和梯度函數(shù)；第三，梯度下降法求解參數(shù)；第四，參數(shù)對(duì)用戶的愛好進(jìn)行預(yù)測(cè)。設(shè)計(jì)電影為代價(jià)函數(shù)中的X的前綴，對(duì)應(yīng)的評(píng)分就是數(shù)據(jù)矩陣,上千部電影，900+用戶評(píng)分。正則化之后的數(shù)據(jù)矩陣如圖1所示。那么推薦系統(tǒng)需要做的工作就是求出theta,然后對(duì)數(shù)字為0的地方進(jìn)行填充，得到結(jié)果如圖2所示。

對(duì)數(shù)據(jù)再進(jìn)行一些后續(xù)加工處理就可以得到輸出結(jié)果，比如對(duì)某電影的平均評(píng)分，還可以得到某用戶對(duì)某些電影的喜好預(yù)測(cè)等。上述就是協(xié)同過濾的全過程。

三、結(jié)語

本文提出一種新的電影推薦方法，詳細(xì)描述了協(xié)同過濾的過程及系統(tǒng)的設(shè)計(jì)。但是由于時(shí)間的限制，電影系統(tǒng)的功能只實(shí)現(xiàn)了簡(jiǎn)單的電影推薦以及電影信息查看。在以后的研究中需進(jìn)一步完善系統(tǒng)的功能，使推薦系統(tǒng)在實(shí)際生活中，為用戶提供更多的功能選擇。