一種基于二部分圖的推薦算法

宋中山，王曉華

(中南民族大學(xué) 計算機科學(xué)學(xué)院，武漢430074)

摘要在對基于二部分圖網(wǎng)絡(luò)結(jié)構(gòu)的推薦算法NBI和基于Pearson系數(shù)的協(xié)同過濾推薦算法CF，以及當(dāng)前廣泛應(yīng)用的完全排序算法GRM進行詳細分析的基礎(chǔ)上，針對這些算法的局限性，提出了一種基于二部分圖的推薦算法.采用Movielens數(shù)據(jù)庫對NBI、CF和GRM以及文中所提算法用2個不同的參數(shù)進行了比較.實驗結(jié)果表明：除了當(dāng)向每個用戶推薦50個電影這一種情況外，文中給出算法的推薦準(zhǔn)確率均高于其他3種推薦方法.

關(guān)鍵詞個性化推薦；數(shù)據(jù)挖掘；二部分圖；推薦算法

收稿日期2015-01-10

作者簡介宋中山(1963-) ，男，副教授，研究方向：數(shù)據(jù)挖掘，E-mail: songzs2005@ tom.com

基金項目國家民委科研基金資助項目(CMZY13010)

中圖分類號TP399文獻標(biāo)識碼A

Based on a Bipartite Graph of Recommendation Algorithm

SongZhongshan,WangXiaohua

(College of Computer Science, South-Central University for Nationalities, Wuhan 430074, China)

AbstractThe foundation of this paper is the recommendation algorithm based on bipartite graph network structure, the collaborative filtering recommendation algorithm (CF) based on Pearson coefficients, and the fully sorting algorithm (CRM) that is most widely used. After the detailed analysis of these algorithms, in consideration of their limitations, a new recommendation algorithm based on bipartite graph is proposed. Movielens database is drawn upon to compare NBI, CF, GRM and the proposed algorithm with two parameters. The results show that the accuracy of the recommendation produced by the proposed algorithm is higher than that of the other three algorithms except when recommending 50 movies to users.

Keywordspersonalized recommendation；data mining；bipartite graph；recommendation algorithm

個性化推薦是數(shù)據(jù)挖掘領(lǐng)域研究的熱點問題之一， 它依據(jù)用戶的興趣特色和購置活動，向用戶推薦能夠感興趣的消息或商品[1,2].

1995年Robert Armstrong等人在美國人工智能協(xié)會上提出了個性化導(dǎo)航系統(tǒng)Web Watcher；斯坦福大學(xué)的Marko Balabanovic等人在同一會議上推出了個性化推薦系統(tǒng)LIRA[3,4]，在文獻[5]中楊銘等人對在線商品評論的效用進行了分析，這為推薦提供了依據(jù).1994年明尼蘇達大學(xué)Grouplens實驗室Resink教授的團隊創(chuàng)建了第一個自動推薦系統(tǒng)Grouplens ，最初只是做Usenet新聞、文章推薦的研究.在1997年又建立了以學(xué)術(shù)研究為目的的Movielens網(wǎng)站，主要技術(shù)是通過獲取用戶對電影的評價信息，利用協(xié)同過濾算法[6]和關(guān)聯(lián)規(guī)則算法相結(jié)合[7]，向用戶推薦電影，該網(wǎng)站面向用戶的信息資源是公開的.

本文通過對基于二部分圖網(wǎng)絡(luò)結(jié)構(gòu)的推薦算法[8]、基于Person系數(shù)的協(xié)同過濾算法[9]、全局排序算法的分析，針對這些算法的局限性，給出了基于二部分圖的推薦算法.該算法不僅能夠清晰地獲得用戶和信息之間的映射關(guān)系，而且可以通過分析用戶的歷史信息，發(fā)現(xiàn)用戶選擇電影的喜好，能夠?qū)⑿畔?zhǔn)確地推薦給用戶，提高算法的準(zhǔn)確性.

1相關(guān)算法分析

1.1基于二部分圖網(wǎng)絡(luò)結(jié)構(gòu)的推薦算法

基于二部分圖網(wǎng)絡(luò)結(jié)構(gòu)的推薦算法NBI[10]，是基于對象的，而不是針對客戶的.它是把對象和用戶抽象成2類節(jié)點，并且把這2類節(jié)點之間用邊進行連接，這樣便構(gòu)成了2個節(jié)點之間的關(guān)系圖.它的具體思想是：在任意X節(jié)點的資源都應(yīng)該有可以分配給其它的與它有關(guān)聯(lián)的節(jié)點的資源，類似的，資源在任意的Y節(jié)點也應(yīng)該具有可以分配給與它有關(guān)聯(lián)的資源.具體的實施思想，如圖1所示.

圖1　二部分圖的構(gòu)造 Fig.1　Bipartite graph structure

以此得出項目和項目之間的關(guān)聯(lián)指數(shù).具體的基于項目的關(guān)聯(lián)網(wǎng)絡(luò)圖如圖2所示.

圖2　基于項目的關(guān)聯(lián)網(wǎng)絡(luò) Fig.2　Based on project of associated network

根據(jù)上面的推薦，我們可以得出對于每個用戶i和未分配的項目j都有一個排名，用公式(1)表示.

(1)

1.2基于Pearson系數(shù)的協(xié)同過濾推薦算法

協(xié)同過濾技術(shù)[11]，首先，要計算出用戶與目標(biāo)項目的相似性.其次，根據(jù)用戶和目標(biāo)用戶的相似性、對項目的評價以及這些評價的分?jǐn)?shù)預(yù)測出對用戶的推薦分?jǐn)?shù).最后，從預(yù)測的推薦分?jǐn)?shù)值中選取最大的n項作為推薦結(jié)果，即通過用戶之間的相似性來推薦商品項目[12]，進行相應(yīng)的比較.具體的算法思想如下.

用戶i和j之間的相似性(用戶i和j同時愛好的電影的數(shù)量)由公式 (2) 進行推測.

(2)

根據(jù)公式(2)得出的用戶之間的相似性，也就是權(quán)值的大小，就可以算出推薦給某一用戶i的電影的推薦分?jǐn)?shù)，計算由公式 (3) 表示.

(3)

1.3完全排序算法

完全排序算法(GRM)是對用戶沒有看過的所有的電影根據(jù)某一個條件進行排序，計算由公式(4)表示.

(4)

根據(jù)公式(4)得出計算結(jié)果，然后按照從高到低的順序排列，并且把排名較高的電影推薦給相應(yīng)的用戶.

2本文算法

2.1算法思想描述

本文是基于二部分圖的基礎(chǔ)上，給出用戶和用戶關(guān)聯(lián)的推薦算法，具體的算法思想如下：若user1和user2共同選擇了10部相同的電影[13]，user1和user3 共同選擇了5部相同的電影，user1和user4 共同選擇了10部相同的電影，user2和user3共同選擇了15部相同的電影，并且他們對這些電影的評分≥3(代表該用戶喜歡該電影)，那么得出用戶與用戶之間的網(wǎng)絡(luò)結(jié)構(gòu)圖如圖3所示.

圖3　用戶與用戶之間的網(wǎng)絡(luò)結(jié)構(gòu)圖 Fig.3　Network structure between user and user

以user1為例，根據(jù)算法思想就可以把user2、user3、user4喜歡的電影根據(jù)他們之間的關(guān)聯(lián)關(guān)系都推薦給user1, 并且對這些推薦的電影以推薦分?jǐn)?shù)做一個降序排名.

如果user2、user3、user4分別喜歡的電影是2部、2部、3部，并且這幾個用戶都和用戶user1有關(guān)聯(lián)，那么就把這7部電影都推薦給用戶user1.其結(jié)構(gòu)如圖4所示.

圖4　用戶和電影的網(wǎng)絡(luò)結(jié)構(gòu)圖 Fig.4　Network structure between user and movie

然后計算出推薦給用戶的電影的推薦分?jǐn)?shù)，并將其按推薦分?jǐn)?shù)(定義為W(i,j))進行一個降序的排名，W(i,j1)≥W(i,j2)…≥W(i,jk)根據(jù)這個排名做相關(guān)的推薦，并進行實驗的驗證和分析，得出該算法的優(yōu)劣評價.

3實驗設(shè)計

實驗環(huán)境如下.

硬件環(huán)境：CPU：2.83GHz，內(nèi)存：4GB.

軟件環(huán)境：Win7(32)、數(shù)據(jù)庫 SQL Server 2008 R2.

本文使用Movielens(http://www.movielens.org)數(shù)據(jù)集的數(shù)據(jù)進行算法的驗證，實驗步驟如下.

(1) 從用戶對100000條電影的評論中篩選出評分≥3的所有評論，共有82520條記錄，并且以9∶1的比例分別存放于表T_Training和T_Test中，用來作為訓(xùn)練集和測試集，分別有74268和8252條記錄.訓(xùn)練集中的數(shù)據(jù)用來構(gòu)造用戶與用戶之間的關(guān)聯(lián)，并且根據(jù)相應(yīng)的關(guān)聯(lián)做出推薦，測試集中的數(shù)據(jù)則是用來驗證推薦算法的準(zhǔn)確性.

(2) 對訓(xùn)練集T_Training 中的數(shù)據(jù)進行分析，建立用戶和電影之間的二部分圖映射關(guān)系，然后根據(jù)用戶共同喜歡的電影找出用戶與用戶之間的關(guān)聯(lián)，存放在表T_SameID3中.

SELECT T_Training.UserID AS UserID1, T2.UserID AS UserID2

INTO T_SameID3

FROM T_Training, T_Training AS T2

WHERE(T_Training.ItermID= T2.ItermID)

AND (T_Training.UserID <> T2.UserID)

(3) 根據(jù)以上的結(jié)果，找出用戶與用戶之間關(guān)聯(lián)權(quán)值的大小，也就是用戶與用戶之間喜歡相同電影的數(shù)目.存放在表T_Weights中.

SELECT UserID1, UserID2, COUNT(*) AS Weights INTO T_Weights

FROM T_SameID3

GROUP BY UserID1, UserID2

(4) 在測試數(shù)據(jù)集 T_Test 表中，找出所有電影編號不重復(fù)的記錄，在這些記錄中找出滿足T_Training 表中被選擇電影的編號ItemID與測試數(shù)據(jù)集中電影的編號ItemID相等的記錄保存到T_InTest 表中，也就是找出既在訓(xùn)練集也在測試集中的電影.

SELECT B.UserID, B.ItermID

INTO T_InTest

FROM(SELECT DISTINCT ItermID

FROM T_Test ) AS A, T_Training AS B

WHERE A.ItermID = B.ItermID

(5) 計算推薦分?jǐn)?shù)，即把所有與某一個用戶的某一個電影有關(guān)系的用戶的權(quán)值進行累計.

SELECT ItermID,UserID2,

COUNT(Weights) AS CommScore

INTO Comm

FROM T_InTest , T_Weights

WHERE T_InTest.UserID=T_Weights.

UserID1

GROUP BY ItermID, UserID2

(6) 根據(jù)測試集和推薦分?jǐn)?shù)的集合找出推薦給用戶的電影在測試集中也存在相應(yīng)的電影的用戶集合，保存在UserINTest 表中，方便以后根據(jù)用戶做電影的推薦，并且分別排名，為求平均相對位置做準(zhǔn)備.

SELECT DISTINCT UserID2

INTO UserINTest

FROM Comm ,T_Test

WHERE T_Test.UserID=Comm.UserID2

AND T_Test.ItermID=Comm.ItermID

(7) 計算出所有用戶看過的電影的數(shù)量，保存在表T_Watch中.

SELECT UserINTest.UserID2 ,

COUNT(*) AS Watch INTO T_Watch

FROM T_Training,UserINTest

WHERE(T_Training.UserID=UserINTest.UserID2) GROUP BY UserINTest.UserID2

根據(jù)上面的實驗步驟得到的數(shù)據(jù)表，即可以求出推薦準(zhǔn)確的電影的平均相對位置，來驗證我們算法的準(zhǔn)確率.

3.1實驗結(jié)果

(1) 找出推薦給每一個用戶的電影，并且根據(jù)推薦分?jǐn)?shù)進行降序排名.執(zhí)行以下代碼，可以得出推薦給該用戶的電影的排名信息記錄.

CREATE PROCEDURE[dbo].[Pro_數(shù)據(jù)整理]

AS

declare @max int--用來做循環(huán)條件的.

declare @rowNo int--用來逐一讀取用戶ID

declare IDSet CURSOR LOCAL SCROLL FOR SELECT UserID FROM UserINTest

BEGIN

SELECT @max=0

--如果表T存在則首先刪除

if exists (SELECT 1 FROM sysobjects

WHERE id = object_id('T')

AND type = 'U') DELETE FROM T

Open IDSet

fetch next FROM IDSet into @rowNO

--循環(huán)開始

while @@FETCH_STATUS = 0 --對每一個rowNumber進行循環(huán)操作

BEGIN

--這兒對每一行要進行的操作的代碼

IF @max=0

BEGIN

SELECT ItermID ,UserID2,CommScore, DENSE_RANK()

over(order by CommScore desc) as 排名

INTO T FROM Comm

WHERE UserID2=@rowNo

SET @max=1

END

ELSE

BEGIN

INSERT INTO T

SELECT ItermID ,UserID2,CommScore, DENSE_RANK()

over(order by CommScore desc) as 排名

FROM Comm

WHERE UserID2=@rowNo

END

Fetch next FROM IDSet into @rowNO

END

close IDSet

deallocate IDSet

--循環(huán)結(jié)束

END

(2) 求平均相對位置.找出推薦給用戶的電影，并且這些電影既在測試集中，也在推薦集中，查出他們在推薦集中的排名，以及相應(yīng)的用戶看過的電影數(shù)量.將結(jié)果保存在Result表中.

SELECT T.UserID2 ,T.ItermID ,排名,

T_Watch.Watch INTO Result

FROM T ,T_Test ,T_Watch

WHERE T_Test.UserID=T.UserID2

AND T.ItermID =T_Test .ItermID

AND T_Watch.UserID2 = T.UserID2

ORDER BY T.UserID2

根據(jù)Result中電影的排名信息，和用戶看過的電影數(shù)量求出平均相對位置.

其中，推薦準(zhǔn)確的電影指的是推薦給用戶的電影既在測試集中也在訓(xùn)練集中.得出的平均相對位置的結(jié)果是：0.073120024.

(3) 求命中率的結(jié)果.根據(jù)推薦給用戶的電影在測試集中也存在相應(yīng)的電影的用戶集合UserINTest，找出在測試集中對應(yīng)的用戶的電影在測試集中的個數(shù)，保存在T_TestNumberOfUser中.

SELECT UserINTest.UserID,

COUNT(ItermID) AS 測試集中個數(shù)

INTO T_TestNumberOfUser

FROM T_Test,UserINTest

WHEREUserINTest.UserID=T_Test.UserID

GROUP BY UserINTest.UserID

根據(jù)對應(yīng)的表篩選出用戶在測試集中的電影在推薦集中的排名信息，以及對應(yīng)的用戶在測試集中包含電影的個數(shù).

接下來就可以計算命中率，為了比較這里以10、20、50、100為長度.分別求出每一個階段命中的個數(shù)來計算命中率.

例如計算長度為10 的命中率.

SELECT UserID2 ,T_TestNumberOfUser.測試集中電影個數(shù),

COUNT(排名) AS 長度10

FROM Result,T_TestNumberOfUser

WHERE Result.UserID2=T_TestNumberOf

User.UserID AND 排名<=10

GROUP BY UserID2 ,

T_TestNumberOfUser.測試集中電影個數(shù)

ORDER BY UserID2

同理，分別計算出長度為20、50和100的命中率，結(jié)果如表1所示.

表1　命中率的結(jié)果

結(jié)合上面分析的幾種推薦算法和本文算法得出的結(jié)果給出比較.

平均相對位置的結(jié)果比較，如表2所示.

表2　平均相對位置的比較

命中率的結(jié)果比較，如表3所示.

表3　命中率的比較

從表2和表3可以看出，基于二部分圖的推薦算法的準(zhǔn)確率是最高的，但是在長度為50的時候基于二部分圖的推薦算法的命中率是38.05%，而基于二部分網(wǎng)絡(luò)結(jié)構(gòu)的推薦算法(NBI)的命中率是41.20%，很顯然在這一個階段我們的算法的準(zhǔn)確率還是沒有NBI的高，經(jīng)過分析和比較，出現(xiàn)這種現(xiàn)象可能的原因有很多，其中包括我們算法的準(zhǔn)確率有待于提高，其次，也是因為我們推薦的準(zhǔn)確率高，所以在10、20的長度時命中率是明顯地高出其他的算法，而在長度增加時，命中率就不會有明顯的提高，甚至還會降低，因為我們推薦命中的電影都比較靠前.還有也可能受用戶主觀因素的影響，比如電影的評價不當(dāng)?shù)鹊龋砸院笤谶@一方面還有待于改進.

4結(jié)語

本文給出了一種基于二部分圖的推薦算法，該算法結(jié)合了二部分圖的映射關(guān)系，分析了用戶與用戶之間的關(guān)聯(lián)，使得推薦給用戶的電影更加準(zhǔn)確.經(jīng)過實驗的驗證，對比了基于二部分圖網(wǎng)絡(luò)結(jié)構(gòu)的推薦算法、基于Person系數(shù)的協(xié)同過濾算法、全局排序算法和本文算法的準(zhǔn)確性，實驗結(jié)果顯示，在相同數(shù)據(jù)條件下，基于二部分圖推薦算法的準(zhǔn)確率是最高的.

參考文獻

[1]宋中山,楊敏,周易.基于模糊集的時序關(guān)聯(lián)規(guī)則的度量準(zhǔn)則[J] .中南民族大學(xué)學(xué)報:自然科學(xué)版,2014,33(1):86-90.

[2]宋中山,周騰,周晶平.一種改進的蟻群聚類算法在客戶細分中的應(yīng)用[J].中南民族大學(xué)學(xué)報:自然科學(xué)版,2013,32(3):77-81.

[3]王國霞,劉賀平.個性化推薦系統(tǒng)綜述[J] .計算機工程與應(yīng)用,2012,48(7):66-76.

[4]Linyuan Lü,Matú? Medo,Chi Ho Yeung,et al. Recommender systems [J].Physics Reports, 2012, 519(1) : 1-49.

[5]楊銘,祁巍,閆相斌,等.在線商品評論的效用分析研究[J].管理科學(xué)報, 2012,15(5):65-75.

[6]Zan-HUANG, ZENGD, CHENG. Comparisi-on of collaborative filtering recommendation algorithms for E-commerce [J] . IEEE Intelligent Systems, 2007, 22(5):68 -78.

[7]Preeti Paranjape-Voditel, Umesh Deshpande . A stock

market portfolio recommender system based on association rule mining [J] .Applied Soft Computing Journal, 2013, 13(2) :1055-1063.

[8]Yuchen Fu,Quan Liu,Zhiming Cui,et al. A collaborative

recommend algorithmbased on bipartite community [J] .The Scientific World Journal, 2014,20(14) :430-452.

[9]Yehuda Koren. Collaborative filtering with temporal

dynamics [J] . Communications of the ACM , 2010 (4): 89-97.

[10]Liu Jianguo, Zhou Tao,Che Hongan, et al . Effects of high order correlations on alized recommendation for bipartite networks [J] . Physica A, 2010,3(89) : 881- 886.

[11]Jian-guo LIU, Bing-hong WANG,Qiang GUO.Improved collaborative filtering algorithm via information transformation [J]. International Jouranal of Modern Physics C,2009, 20(2):285-293

[12]冷亞軍,陸青,梁昌勇. 協(xié)同過濾推薦技術(shù)綜述[J].模式識別與人工智能, 2014,7(8):720-734.

[13]Sang-Min Choi .A movie recommendation algorithm based on genre correlations[J] .Expert Systemswith Applications, 2012, 39 (9) :8079-8085.