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

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

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

1 引言

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

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

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

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

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

(1)

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

2.2 查找最近鄰居集

利用構(gòu)建的評(píng)分?jǐn)?shù)據(jù)模型對(duì)網(wǎng)絡(luò)信息數(shù)據(jù)進(jìn)行查找，獲取網(wǎng)絡(luò)信息數(shù)據(jù)中評(píng)分信息的評(píng)分向量。根據(jù)相似度公式對(duì)評(píng)分向量進(jìn)行計(jì)算，獲取數(shù)據(jù)評(píng)分矩陣中數(shù)據(jù)u與數(shù)據(jù)uj的評(píng)分相似度sim(u，uj)[6]。再將取得的節(jié)點(diǎn)信息相似度進(jìn)行降序排列，可得知sim(u，u1)>sim(u，u2)，>…>sim(u，ux)。然后依據(jù)選擇策略決定最近鄰居值的大小。選擇鄰居策略有兩種主要形式，第一種預(yù)先設(shè)置最近鄰居數(shù)k，第二種是設(shè)置固定的相似度閾值，若目標(biāo)相似度大于閾值，就可將對(duì)應(yīng)的數(shù)據(jù)劃分到目標(biāo)的最近鄰居集中。但是長(zhǎng)時(shí)間的經(jīng)驗(yàn)累積已經(jīng)能夠證明用固定值k確定最近鄰居值的方法優(yōu)于后者，所以一般都會(huì)采取設(shè)固定鄰居數(shù)k，確認(rèn)最相似的鄰居數(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的最近鄰居便是距離它最近的五個(gè)數(shù)據(jù)1、2、3、4、5。

2.3 相似性計(jì)算

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

(2)

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

(3)

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

(4)

2.4 預(yù)測(cè)評(píng)分

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

(5)

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

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

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

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

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

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

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

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

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

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

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

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

(6)

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

2)從P集合中挑選任意用戶v中未選擇項(xiàng)目資源作為選定的目標(biāo)用戶u，過(guò)程如下式

(7)

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

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

(8)

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

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

(9)

矩陣W則如下表示為

(10)

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

f=Wfo

(11)

按由大到小順序排列最終向量f按照資源值，取前k個(gè)用戶u沒(méi)選擇過(guò)的項(xiàng)目形成推薦列表推薦給用戶，完成信息資源的分配并推薦。

4 仿真分析

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

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

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

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

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

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

分析圖3可知，在相同量的數(shù)據(jù)信息中，與文獻(xiàn)[3]算法和文獻(xiàn)[4]算法相比，所提算法的信息資源分配正確率較高且檢測(cè)的正確率趨于平穩(wěn)，這是因?yàn)樗崴惴ㄔ谛畔①Y源預(yù)處理時(shí)對(duì)數(shù)據(jù)進(jìn)行了協(xié)同過(guò)濾的相似性計(jì)算，提高了數(shù)據(jù)信息在資源分配時(shí)的準(zhǔn)確性。

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

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

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

5 結(jié)束語(yǔ)

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