基于協(xié)同過濾的多節(jié)點信息資源分配推薦算法

佘學(xué)兵，占清華，鄔昌興

(1. 江西科技學(xué)院信息工程學(xué)院，江西 南昌330098；2. 華東交通大學(xué)軟件學(xué)院，江西 南昌 330013)

1 引言

目前網(wǎng)絡(luò)信息技術(shù)飛速發(fā)展，網(wǎng)絡(luò)上留存著大量的信息數(shù)據(jù)[1]。由于這些數(shù)據(jù)屬性不同并且較為雜亂，因此在用戶進行信息搜索時，常?；ㄙM較長的時間卻找不到相對有用的信息[2]。目前的信息資源分配算法只能對用戶已知的信息進行推薦，而不能對未知信息進行推薦，所以急需一種新的信息資源分配推薦算法滿足用戶需求。

文獻[3]提出基于改進物質(zhì)擴散的數(shù)據(jù)信息資源分配推薦算法。采用信任機制得到目標用戶最優(yōu)鄰居集，利用用戶信任度初始資源分配信息，根據(jù)物品雙向擴散能力對參數(shù)進行調(diào)優(yōu)，實現(xiàn)信息資源的再分配，優(yōu)化目標用戶完成推薦。該算法能夠提高推薦結(jié)果的多樣性，但其信息資源分配時間較長。文獻[4]提出基于受限馬爾可夫決策過程的節(jié)點信息資源分配推薦算法。采用馬爾可夫決策理論，構(gòu)建動態(tài)優(yōu)化模型，利用近似動態(tài)規(guī)劃理論，定義基函數(shù)的分配行為，調(diào)整外部環(huán)境學(xué)習(xí)和資源分配策略完成推薦。該算法能夠有效減少計算維度，但是其信息資源分配推薦列表覆蓋率較低。為了解決上述信息資源分配算法中所存在的問題，提出了基于協(xié)同過濾的多節(jié)點信息資源分配推薦算法。

2 基于協(xié)同過濾算法的信息分類處理

2.1 構(gòu)建信息數(shù)據(jù)評分模型

利用預(yù)處理技術(shù)與數(shù)據(jù)挖掘技術(shù)，對節(jié)點中的信息資源進行處理分類，構(gòu)建評分數(shù)據(jù)模型。一般選擇用M×N的評分矩陣R(如下式1所示)。

(1)

式(1)中，M代表矩陣中的行數(shù)，N代表矩陣中的列數(shù)，且數(shù)據(jù)i對項目j的評價值用Rij表示。數(shù)據(jù)評價值用0到5之間的整數(shù)來表示，作為數(shù)據(jù)對項目的評分，值越大表示此數(shù)據(jù)受歡迎程度越高，0則表示沒有對數(shù)據(jù)進行評價[5]。也可以用整數(shù)區(qū)間來表示評價級別，級越高表示越受歡迎。

2.2 查找最近鄰居集

利用構(gòu)建的評分數(shù)據(jù)模型對網(wǎng)絡(luò)信息數(shù)據(jù)進行查找，獲取網(wǎng)絡(luò)信息數(shù)據(jù)中評分信息的評分向量。根據(jù)相似度公式對評分向量進行計算，獲取數(shù)據(jù)評分矩陣中數(shù)據(jù)u與數(shù)據(jù)uj的評分相似度sim(u，uj)[6]。再將取得的節(jié)點信息相似度進行降序排列，可得知sim(u，u1)>sim(u，u2)，>…>sim(u，ux)。然后依據(jù)選擇策略決定最近鄰居值的大小。選擇鄰居策略有兩種主要形式，第一種預(yù)先設(shè)置最近鄰居數(shù)k，第二種是設(shè)置固定的相似度閾值，若目標相似度大于閾值，就可將對應(yīng)的數(shù)據(jù)劃分到目標的最近鄰居集中。但是長時間的經(jīng)驗累積已經(jīng)能夠證明用固定值k確定最近鄰居值的方法優(yōu)于后者，所以一般都會采取設(shè)固定鄰居數(shù)k，確認最相似的鄰居數(shù)，最近鄰居集可表示為KNN(u)={u1，u2，…uk}，u?KNN(u)，k∈(1，m)。

假設(shè)尋找數(shù)據(jù)0的最近鄰居，選K值為5，可用矢量距離代表網(wǎng)絡(luò)信息數(shù)據(jù)之間的相似度，數(shù)據(jù)0的最近鄰居便是距離它最近的五個數(shù)據(jù)1、2、3、4、5。

2.3 相似性計算

在協(xié)同過濾算法中，最近相似度的計算是查找鄰居集的重要前提[7]。相似度的計算函數(shù)又分為余弦相似性、修正余弦相似性、相關(guān)相似性三種。其中，余弦相似性是計算網(wǎng)絡(luò)節(jié)點信息與項目空間向量上的內(nèi)積夾角余弦值，并用此余弦值計算數(shù)據(jù)之間的相似度，過程如下式

(2)

調(diào)整余弦相似度的目的在于克服網(wǎng)絡(luò)信息數(shù)據(jù)在評價時受個體因素影響而導(dǎo)致的評分尺度不同的問題。在余弦相似性的公式上進行修改，主要是將獲取的余弦相似性向量減去信息數(shù)據(jù)平均評分向量后，進行夾角的余弦計算。過程如下式

(3)

相關(guān)相似性也叫做皮爾森系數(shù)，首先找到信息數(shù)據(jù)進行過共同評分的項目集，其次在共同評分項目集中計算向量的相關(guān)系數(shù)，以此來表示不同網(wǎng)絡(luò)信息數(shù)據(jù)的相似性，如下式所示。

(4)

2.4 預(yù)測評分

在目標信息數(shù)據(jù)的最近鄰居集KNN(u)確定后，以sim(u，v)為權(quán)重加權(quán)的平均最近鄰居集對信息數(shù)據(jù)的未評價項目i進行評分[8]，并引入信息數(shù)據(jù)對歷史項目評分的平均水平進行調(diào)整，產(chǎn)生u對i的預(yù)測評分，過程如下式；

(5)

在訪問網(wǎng)絡(luò)信息數(shù)據(jù)時，根據(jù)一些歷史信息，適時對未評分的數(shù)據(jù)進行評分，劃入相對應(yīng)的最近鄰居集，利用相似度計算完成對網(wǎng)絡(luò)信息數(shù)據(jù)的分類。

3 多節(jié)點信息資源分配推薦算法

在基于協(xié)同過濾算法將節(jié)點信息進行分類后，利用二部圖網(wǎng)絡(luò)結(jié)構(gòu)對分類的節(jié)點信息進行資源分配并對信息資源進行推薦。

設(shè)二部圖網(wǎng)絡(luò)用G={V，E}表示，U表示分類信息的用戶類，L表示分類信息的項目類，這樣就由U類數(shù)據(jù)信息節(jié)點和L類數(shù)據(jù)信息節(jié)點以及圍繞在它們之間的數(shù)據(jù)信息邊集E組成了一個網(wǎng)絡(luò)結(jié)構(gòu)[9]。若假設(shè)這個網(wǎng)絡(luò)結(jié)構(gòu)中有N個用戶L={l1，l2，…lN}，M個項目U={u1，u2，…uM}，那么在用戶和項目之間便會由此形成一種選擇關(guān)系，可以用一個鄰接矩陣A={αul}M，N來代表這種關(guān)系。如果項目l被用戶u選擇了，則αu，i=1，若否αul=2。

每一個用戶都有各自的愛好，所以根據(jù)用戶選擇的項目就可以準確了解用戶在這一階段對某些項目的喜好程度。若把這些抽象意義上各不相同的喜好進行信息提取再具象的表現(xiàn)出來，就可以清晰的看到，不同用戶選擇的不同項目能夠互相連接，形成關(guān)系網(wǎng)。再讓獲取的資源值在這些關(guān)系中進行流動[10-11]。當選定目標用戶將其獲取的資源值通過未選定用戶分配給用戶未選擇項目時，該目標用戶便具備了推薦用戶的未選擇項，就此形成推薦過程。二部圖網(wǎng)絡(luò)結(jié)構(gòu)的多節(jié)點信息資源推薦過程如圖1所示。

圖1 二部圖網(wǎng)絡(luò)結(jié)構(gòu)的多節(jié)點信息資源推薦過程

如圖1所示，設(shè)目標用戶為u1，二部圖的多節(jié)點信息資源分配過程如下：

1)對信息數(shù)據(jù)項目設(shè)定初始資源值。設(shè)定“1”為L類節(jié)點信息中目標用戶u1選定項目的初始資源值，而未被選擇的項目則為2。初始資源值為1的項目集合為S={l1，l3}，具體過程如圖1(a)。

2)根據(jù)選定的關(guān)系，將S集合所被賦予的資源值進行整合并分配到跟其相鄰的U節(jié)點里，這樣用戶集P={u1，u2，u3}就都能夠獲取資源值。而用戶集P中所有用戶取得的資源值實際上就是S集中所有項目節(jié)點l的資源值除以l節(jié)點中度的總和，具體如圖1(a)到圖1(b)所示。

3)再依據(jù)選定的關(guān)系，先把P集合中的推薦資源值進行整合，再將整合后的用戶節(jié)點資源值分配到P集合所相鄰的l類項目節(jié)點里，最后得到的信息項目資源值里將包含未選擇的所有項目。這種情況下，所獲取的l類信息節(jié)點資源值就包含了用戶集P中全部用戶u的信息項目資源值除去l信息節(jié)點度的總和。過程如圖1(b)到圖1(c)所示。

對于以二部圖網(wǎng)絡(luò)結(jié)構(gòu)為基礎(chǔ)的多節(jié)點信息資源分配算法所提出的資源擴散過程，在設(shè)定目標用戶為u的情況后，具體步驟如下；

1)初始資源值確定，用下式表示

(6)

式(6)中，用戶u所對應(yīng)的信息項目l是所設(shè)定的初始資源值用αu，l表示。

2)從P集合中挑選任意用戶v中未選擇項目資源作為選定的目標用戶u，過程如下式

(7)

式(7)中，al代表有多少用戶選擇過信息項目l，即這個信息項目的維度。

3)獲取P集合中的任意項目x的資源過程，用下式表示

(8)

式(8)中，rx是項目x在目標用戶u推薦項目x時產(chǎn)生的推薦資源值。而任意用戶v選擇過的項目數(shù)dv則為任意用戶v的度。

利用二部圖網(wǎng)絡(luò)結(jié)構(gòu)為基礎(chǔ)的多節(jié)點信息資源分配算法，將未選中的目標用戶進行再次計算。在信息資源庫中，設(shè)二部圖中有Y個信息項目節(jié)點，這種情況下可以創(chuàng)建一個y行y列的W矩陣，用作表示二部圖結(jié)構(gòu)上所存在與項目中的一維投影[12]。W矩陣中的Wl，x則表示l行x列的資源值在項目傳遞時對項目x的初始加權(quán)。圍繞信息資源分配過程，可以用下式表示

(9)

矩陣W則如下表示為

(10)

假設(shè)向目標用戶u進行信息資源推薦，項目集L的最終資源值用向量fο=(i1，i2，…，in)T表示，則如下式所示；

f=Wfo

(11)

按由大到小順序排列最終向量f按照資源值，取前k個用戶u沒選擇過的項目形成推薦列表推薦給用戶，完成信息資源的分配并推薦。

4 仿真分析

為了驗證所提算法的有效性，在MATLAB軟件平臺上進行對比測試，采用的Java作為編程開發(fā)語言、數(shù)據(jù)庫為MySQL關(guān)系數(shù)據(jù)庫、平臺為Eclipse、操作系統(tǒng)為Windows 7、內(nèi)存為1G DDR、CPU為Intel Pentium。分別采用所提算法、文獻[3]算法和文獻[4]算法進行測試。

在網(wǎng)絡(luò)信息數(shù)據(jù)相同的情況下，對比不同資源分配推薦算法推薦信息資源所需要時間，測試結(jié)果如圖2所示。

圖2 不同算法的信息資源分配時間測試結(jié)果

分析圖2可知，在相同的數(shù)據(jù)信息下，所提算法比文獻[3]算法和文獻[4]算法的測試時間短，因為所提算法在前期處理數(shù)據(jù)時對信息數(shù)據(jù)進行協(xié)同過濾處理，構(gòu)建了信息數(shù)據(jù)評分模型，短時間內(nèi)快速查找最近鄰居集并對數(shù)據(jù)進行了預(yù)測評分，以此完成了對信息數(shù)據(jù)的分類處理。減少了信息資源分配時間，提高了分配效率。

在相同量的信息數(shù)據(jù)下，所提算法、文獻[3]算法與文獻[4]算法對信息資源分配的正確率進行測試，測試結(jié)果如圖3所示。

圖3 不同算法的信息資源分配正確率測試結(jié)果

分析圖3可知，在相同量的數(shù)據(jù)信息中，與文獻[3]算法和文獻[4]算法相比，所提算法的信息資源分配正確率較高且檢測的正確率趨于平穩(wěn)，這是因為所提算法在信息資源預(yù)處理時對數(shù)據(jù)進行了協(xié)同過濾的相似性計算，提高了數(shù)據(jù)信息在資源分配時的準確性。

基于上述兩種測試結(jié)果，對三種算法進行不同推薦列表數(shù)量的準確覆蓋率測試，測試結(jié)果如圖4所示。

圖4 不同算法的推薦列表覆蓋率測試結(jié)果

分析圖4可知，在不同數(shù)量的推薦列表下所提算法比文獻[3]算法和文獻[4]算法的覆蓋率更加全面并且較為平穩(wěn)，穩(wěn)定性較好。這主要是由于所提算法在信息資源分配時對網(wǎng)絡(luò)信息數(shù)據(jù)進行了協(xié)同過濾的數(shù)據(jù)分類，根據(jù)歷史信息，對數(shù)據(jù)進行預(yù)測評分，再由多節(jié)點信息資源分配算法進行計算，最后生成推薦列表。所以，所提算法在不同推薦列表下的覆蓋率要高于文獻[3]算法和文獻[4]算法。

5 結(jié)束語

為縮短目前算法多節(jié)點信息資源分配時間，提高信息資源分配正確率和推薦列表覆蓋率，提出基于協(xié)同過濾的多節(jié)點信息資源分配推薦算法?；趨f(xié)同過濾算法，將數(shù)據(jù)信息整合，構(gòu)建信息數(shù)據(jù)評分模型，依據(jù)建好模型查找數(shù)據(jù)的最近鄰居集進行評分預(yù)測，完成數(shù)據(jù)分類。由二部圖網(wǎng)絡(luò)結(jié)構(gòu)的多節(jié)點信息資源分配推薦算法對分類過的數(shù)據(jù)信息進行二次計算，實現(xiàn)信息資源分配并對用戶進行推薦。所提算法能夠有效縮短多節(jié)點信息資源分配時間，提高信息資源分配正確率和推薦列表覆蓋率。