范 瑩,郝琳娜,易 華,吉青晶,許華虎,尹方敏
(1.國(guó)家電網(wǎng)上海市電力公司培訓(xùn)中心,上海 200438;2.國(guó)家電網(wǎng)上海市電力公司檢修公司,上海 200029;3.上海大學(xué) 計(jì)算機(jī)工程與科學(xué)學(xué)院,上海 200444)
基于最大期望和協(xié)同過(guò)濾算法的研究與應(yīng)用
范 瑩1,郝琳娜1,易 華1,吉青晶2,許華虎3,尹方敏3
(1.國(guó)家電網(wǎng)上海市電力公司培訓(xùn)中心,上海 200438;2.國(guó)家電網(wǎng)上海市電力公司檢修公司,上海 200029;3.上海大學(xué) 計(jì)算機(jī)工程與科學(xué)學(xué)院,上海 200444)
推薦系統(tǒng)中新用戶在信息搜索中易出現(xiàn)信息稀疏的問(wèn)題,以致給用戶推薦相關(guān)模塊的時(shí)候帶來(lái)了極大困難。針對(duì)該問(wèn)題,采用人口統(tǒng)計(jì)學(xué)中的最大期望算法對(duì)用戶進(jìn)行聚類找到近鄰用戶,然后將其作為協(xié)同過(guò)濾算法的輸入。由于用戶對(duì)不同項(xiàng)目的評(píng)分表明他們需求,相同用戶評(píng)價(jià)的項(xiàng)目中存在一定的需求關(guān)聯(lián)性。而且隨著個(gè)人需求的變化,這種關(guān)聯(lián)度也逐漸在變化。所以通過(guò)引入一個(gè)時(shí)間權(quán)重函數(shù)的形式,給出一種基于用戶需求變化的協(xié)同過(guò)濾算法,緩解傳統(tǒng)協(xié)同過(guò)濾推薦算法的短板??梢宰粉櫟接脩舻男枨螅M(jìn)而預(yù)測(cè)評(píng)分矩陣。通過(guò)實(shí)驗(yàn)和比較,該算法有助于解決用戶的評(píng)分矩陣稀疏性問(wèn)題,從而提高推薦質(zhì)量。
稀疏性;最大期望算法;協(xié)同過(guò)濾;個(gè)性化推薦
處在如今這樣一個(gè)大數(shù)據(jù)信息時(shí)代,用戶對(duì)信息的需求得到了滿足,但隨著網(wǎng)絡(luò)信息量的大幅度增長(zhǎng),使得用戶在搜索信息時(shí)無(wú)法直接有效地獲取到自己需要的信息,“信息爆炸”也因此而形成。數(shù)據(jù)挖掘網(wǎng)站逐漸興起,協(xié)同過(guò)濾相關(guān)的推薦系統(tǒng)[1-5]在國(guó)外應(yīng)用廣泛,并取得了很高的應(yīng)用價(jià)值。
國(guó)外著名的應(yīng)用案例有協(xié)同過(guò)濾系統(tǒng)[6]和Amazon個(gè)性化系統(tǒng)[7]。Tapestry[6]是已知的最早投入使用的協(xié)同過(guò)濾系統(tǒng),主要用于解決信息過(guò)載問(wèn)題;Group Lens[8]通過(guò)用戶-項(xiàng)目的評(píng)分矩陣來(lái)計(jì)算用戶的相似性,尋找目標(biāo)用戶的最相似鄰居的數(shù)據(jù)集,并根據(jù)這個(gè)數(shù)據(jù)集來(lái)產(chǎn)生推薦結(jié)果;Amazon個(gè)性化系統(tǒng)在給用戶推薦個(gè)性化圖書的同時(shí),極大地提高了銷售額。
國(guó)內(nèi)的相關(guān)使用在近些年慢慢起步,研究水平和引用規(guī)模正逐年提升。國(guó)內(nèi)比較好的應(yīng)用[9]有互動(dòng)出版網(wǎng)網(wǎng)上書店(http://www.china-pub.com/)以及網(wǎng)上文章推薦小助手(http://www.360doc.com/)等?;?dòng)出版網(wǎng)的會(huì)員[6]有一個(gè)“我的China-Pub”頁(yè)面,上面記錄會(huì)員用戶的歷史日志,會(huì)員還可以個(gè)性化定制個(gè)人的喜好;360doc通過(guò)對(duì)網(wǎng)站文章進(jìn)行相關(guān)性分析和判斷,在內(nèi)容高度相關(guān)的文章間建立關(guān)聯(lián),能夠看到很多“相關(guān)文章”。
在給用戶提供個(gè)性化服務(wù)之前,大多數(shù)時(shí)候系統(tǒng)已經(jīng)記錄了用戶的基本信息。但是新用戶沒(méi)有歷史行為信息以供參考,因?yàn)樾掠脩魧?duì)系統(tǒng)里所有項(xiàng)目的評(píng)分都為空,也即是說(shuō)新用戶的可用信息是很稀疏的,因此無(wú)法獲取到其需求點(diǎn)。文中采用人口統(tǒng)計(jì)學(xué)中的最大期望算法,把用戶的基本信息數(shù)據(jù)源進(jìn)行聚類,找到其近鄰用戶,然后將其作為協(xié)同過(guò)濾的輸入。
在協(xié)同過(guò)濾推薦系統(tǒng)[10-11]中,基于用戶的需求挖掘是個(gè)復(fù)雜問(wèn)題,用戶需求也就是對(duì)推薦項(xiàng)目的選擇和偏好。但是這種需求可能會(huì)隨著年齡、季節(jié)以及環(huán)境等的變化而變化。文中主要提出基于用戶需求的協(xié)同過(guò)濾算法。該算法描述了用戶需求的變換,可以預(yù)測(cè)用戶項(xiàng)目的評(píng)分矩陣并進(jìn)行補(bǔ)充。
新用戶在信息搜索的過(guò)程中會(huì)出現(xiàn)信息稀疏的問(wèn)題,這會(huì)使系統(tǒng)給用戶推薦相關(guān)模塊時(shí)出現(xiàn)極大困難。文中引入人口統(tǒng)計(jì)學(xué)中的最大期望算法[12]來(lái)進(jìn)行聚類,將用戶的個(gè)人信息進(jìn)行聚類分析[13-16],之后目標(biāo)用戶的鄰居用戶就能被找到,后續(xù)在協(xié)同過(guò)濾時(shí)將其作為用戶集輸入。
在用戶聚類時(shí),選用性別、年齡、職務(wù)、學(xué)歷等作為特征維度。因?yàn)榍叭送ㄟ^(guò)研究決策樹技術(shù)發(fā)現(xiàn)這些特征信息對(duì)用戶興趣的偏好能產(chǎn)生較大影響。
在有了全部用戶數(shù)據(jù)a的情況下,并不能確認(rèn)他們來(lái)自哪個(gè)類別。若將用戶的所有數(shù)據(jù)表示成(a,b),其中b代表a所屬分支的標(biāo)簽,取值范圍為b∈(1,…,θ)。此時(shí),全部數(shù)據(jù)的概率密度[17]的定義為:
(1)
其中,θ為密度分支的個(gè)數(shù);r1,r2,…,rθ(1,…,θ)為分支占總體分支的比例;fi為第i個(gè)分支的密度。
θi為相應(yīng)分支的未知參數(shù),在用戶數(shù)據(jù)集{x1,x2,…,xn}確定之后,再用極大似然函數(shù)[18]估計(jì)的方法計(jì)算θmax:
(2)
最大期望算法[19-21]本質(zhì)上是迭代算法,從初始解θ0迭代,陸續(xù)得到θ1,θ2,…,θt。在迭代過(guò)程中,似然函數(shù)的值一直遞增。算法流程如下:
(1)給定一個(gè)初始化分布參數(shù)θ0;
(2)對(duì)每一個(gè)遞增的θ1,θ2,…,θt,重復(fù)執(zhí)行以下步驟直至收斂:
①給定用戶數(shù)據(jù)和當(dāng)前解θt,求用戶數(shù)據(jù)的對(duì)數(shù)似然函數(shù)的期望值:
(3)
其在,Eb是關(guān)于隨機(jī)變量b的期望。
②給定一個(gè)新的參數(shù)?t+1,使得這時(shí)的對(duì)數(shù)似然函數(shù)期望值達(dá)到最大值:
?t+1=argmaxQ(?|?t)
(4)
(3)一直循環(huán)迭代,可獲得?t,到最終算法收斂為止。
這樣通過(guò)最大期望迭代自適應(yīng)的計(jì)算,可得到各類用戶簇和各個(gè)類別的分布特征。
在推薦系統(tǒng)[22]中,用戶集合U={U1,U2,…,Us}和項(xiàng)目集合I={I1,I2,…,It}間存在一個(gè)用戶-項(xiàng)目評(píng)分矩陣,如表1所示。
表1 用戶-項(xiàng)目評(píng)分矩陣Rs×t
其中,矩陣[23]共有s行,代表s個(gè)用戶,t列代表t個(gè)項(xiàng)目。某個(gè)用戶Ui對(duì)項(xiàng)目Ij的評(píng)分Ri,j代表用戶i對(duì)項(xiàng)目j的偏好和興趣。由于用戶不可能對(duì)每個(gè)項(xiàng)目都有評(píng)分,所以在評(píng)分矩陣Rs×t中,有些評(píng)分是沒(méi)有的,造成了用戶-項(xiàng)目評(píng)分矩陣的稀疏性,使得用戶間的相似度計(jì)算變得困難。
(1)標(biāo)準(zhǔn)余弦相似度計(jì)算用戶相似性[23]。
(5)
因?yàn)橥ㄟ^(guò)標(biāo)準(zhǔn)余弦相似度[24]更多地是從方向上區(qū)別向量的不同,而且對(duì)絕對(duì)的數(shù)值不敏感,不能很好地衡量每個(gè)維度上數(shù)值的差異,從而造成巨大的誤差。所以通過(guò)對(duì)所有的維度上的數(shù)值都減去一個(gè)均值來(lái)進(jìn)行調(diào)整。
(2)調(diào)整余弦相似度。
為了調(diào)整因?yàn)椴煌脩魧?duì)同種項(xiàng)目評(píng)分的偏差,通過(guò)對(duì)所有維度上的數(shù)值都減去一個(gè)均值來(lái)降低結(jié)果的誤差。
Sim(Ua,Ub)=
(6)
(1)基于時(shí)間的權(quán)重函數(shù)。
為了更好地觀察用戶的需求變化問(wèn)題,提出一個(gè)時(shí)間權(quán)重函數(shù)TWF(u,i):
(7)
其中,tui表示用戶u當(dāng)前訪問(wèn)項(xiàng)目i的時(shí)間減去最近一次訪問(wèn)項(xiàng)目i的時(shí)間的差值; Ltui表示用戶u當(dāng)前訪問(wèn)項(xiàng)目i的時(shí)間與最遠(yuǎn)一次訪問(wèn)項(xiàng)目i的時(shí)間的差值;ε表示權(quán)重變化指數(shù),ε∈(0,1),ε越大說(shuō)明用戶對(duì)項(xiàng)目i的關(guān)注越頻繁。
(2)改進(jìn)的余弦相似性。
在計(jì)算用戶的相似性時(shí),將用戶-項(xiàng)目評(píng)分矩陣中的每一個(gè)評(píng)分值都乘上基于時(shí)間的權(quán)重函數(shù),以獲得更高的精度。
(8)
在用戶相似度取得一個(gè)比較精確的值后,可以對(duì)用戶-項(xiàng)目評(píng)分矩陣中沒(méi)有的評(píng)分值進(jìn)行預(yù)測(cè)。采用全局?jǐn)?shù)值算法,以用戶對(duì)相似產(chǎn)品的評(píng)分的相似度作為權(quán)值來(lái)生成預(yù)測(cè)評(píng)分。
(9)
其中,n為用戶數(shù)量;Prai為用戶a對(duì)項(xiàng)目i的預(yù)測(cè)評(píng)分。
輸入:用戶特征維度,用戶-產(chǎn)品評(píng)分矩陣Rs×t,s個(gè)用戶對(duì)t個(gè)項(xiàng)目評(píng)分的歷史記錄時(shí)間,時(shí)間權(quán)重指數(shù)ε;
輸出:給用戶的N個(gè)推薦項(xiàng)目。
Step1:利用給定的用戶集合U={U1,U2,…,Us}和相關(guān)特征數(shù)據(jù),通過(guò)最大期望迭代聚類找到目標(biāo)用戶的近鄰用戶,見式(3)和式(4);
Step2:利用用戶-產(chǎn)品評(píng)分矩陣Rs×t和時(shí)間權(quán)重函數(shù)TWF(u,i),計(jì)算基于用戶興趣的評(píng)分相似性,見式(8);
Step3:在式(8)的基礎(chǔ)上,采用全局?jǐn)?shù)值算法對(duì)用戶對(duì)產(chǎn)品的評(píng)分進(jìn)行預(yù)測(cè),見式(9)。
如圖1所示,用戶登錄系統(tǒng)后,首先判斷其個(gè)人信息數(shù)據(jù)是否稀疏,看是否需要通過(guò)最大期望聚類操作來(lái)為其選取近鄰用戶。之后以此數(shù)據(jù)作為協(xié)同過(guò)濾的數(shù)據(jù)集,并根據(jù)用戶-項(xiàng)目評(píng)分矩陣和時(shí)間權(quán)重函數(shù)計(jì)算基于用戶興趣的評(píng)分相似性,進(jìn)而為目標(biāo)用戶進(jìn)行資源推薦。
圖1 整體框圖
4.3.1 評(píng)估標(biāo)準(zhǔn)
對(duì)于推薦系統(tǒng)的有效性,研究人員提出了許多評(píng)估標(biāo)準(zhǔn)來(lái)進(jìn)行驗(yàn)證,大概包括兩類:驗(yàn)證推薦結(jié)果的準(zhǔn)確性;驗(yàn)證算法時(shí)間和空間的復(fù)雜度。平均絕對(duì)誤差(MAE)能更好地反映預(yù)測(cè)值誤差的實(shí)際情況,文中選擇其作為評(píng)估標(biāo)準(zhǔn)。這種評(píng)估標(biāo)準(zhǔn)首先隱藏目標(biāo)用戶的真實(shí)評(píng)分,然后通過(guò)基于用戶需求的協(xié)同過(guò)濾推薦算法預(yù)測(cè)其對(duì)項(xiàng)目的評(píng)分,最后通過(guò)預(yù)測(cè)值和真實(shí)值之間的差異累積得到平均絕對(duì)誤差。
假設(shè)預(yù)測(cè)評(píng)分值為{p1,p2,…,pn},對(duì)應(yīng)的真實(shí)評(píng)分值為{q1,q2,…,qn},通過(guò)式(10)計(jì)算得到平均絕對(duì)誤差:
(10)
MAE的值與推薦的準(zhǔn)確率呈反比。
4.3.2 數(shù)據(jù)源
選擇網(wǎng)站http://grouplens.org/datasets/moviele-ns/上提供的數(shù)據(jù)集進(jìn)行驗(yàn)證,提取該數(shù)據(jù)集中1 000個(gè)用戶對(duì)1 700部電影的評(píng)分?jǐn)?shù)據(jù)作為實(shí)驗(yàn)數(shù)據(jù)。
4.3.3 實(shí)驗(yàn)環(huán)境
實(shí)驗(yàn)環(huán)境如表2所示。
表2 實(shí)驗(yàn)環(huán)境信息
4.3.4 實(shí)驗(yàn)結(jié)果
實(shí)驗(yàn)結(jié)果如圖2所示。
圖2 MAE值比較
由實(shí)驗(yàn)結(jié)果可見,基于用戶需求變化的協(xié)同過(guò)濾算法(CFBUIE)的精確性高于傳統(tǒng)的協(xié)同過(guò)濾算法(CF)。
在上海市電力公司職工的“電力行業(yè)考試中心系統(tǒng)”在線版的基礎(chǔ)上,實(shí)現(xiàn)了最大期望算法聚類和基于用戶需求的協(xié)同過(guò)濾推薦相關(guān)算法。運(yùn)用Android編程技術(shù)為其開發(fā)了移動(dòng)端版本,將其在線版的數(shù)據(jù)移植到APP的版本上,在延續(xù)網(wǎng)頁(yè)版的同時(shí),為廣大職工提供個(gè)性化推薦服務(wù)。整體流程如圖3所示。
圖3 整體流程
Android應(yīng)用界面如圖4所示。功能涉及到考試學(xué)習(xí)的信息發(fā)布與管理,自助學(xué)習(xí),自助練習(xí),自助測(cè)試。移動(dòng)平臺(tái)可以建立針對(duì)個(gè)人的學(xué)習(xí)內(nèi)容管理、學(xué)習(xí)進(jìn)度管理、練習(xí)管理、練習(xí)成果分析、模擬考試等多種功能,能夠滿足用戶的個(gè)性化需求。
圖4 Android應(yīng)用界面展示
針對(duì)新用戶可用信息稀疏的問(wèn)題,采用最大期望算法對(duì)用戶進(jìn)行聚類;針對(duì)現(xiàn)有協(xié)同過(guò)濾算法不能快速發(fā)現(xiàn)用戶需求變化的問(wèn)題,提出基于時(shí)間的數(shù)據(jù)權(quán)重函數(shù),將其引進(jìn)到傳統(tǒng)的協(xié)同過(guò)濾推薦算法中以反映用戶需求的動(dòng)態(tài)變化,緩解了傳統(tǒng)協(xié)同過(guò)濾推薦算法的短板,提高了推薦的準(zhǔn)確性。今后會(huì)繼續(xù)對(duì)相關(guān)算法展開研究,提高其使用范圍,推廣到各行各業(yè)。
[1] Tevreen L, Hill W,Amento B,et al. PHOAKS:a system for sharing recommendations[J].Communications of the ACM,1997,40(3):59-62.
[2] Shardanand U,Maes R.Social information filtering:algorithms for automating “word of mouth”[C]//Proceedings of the computer-human interaction conference.Denver:ACM Perss,1995.
[3] Rucker J,Polanco M J. Siteseer:personalized navigation for the Web[J].Communications of the ACM,1997,40(3):73-76.
[4] 簡(jiǎn)士堯.以內(nèi)容為基礎(chǔ)之網(wǎng)絡(luò)學(xué)習(xí)導(dǎo)覽推薦之研究[D].臺(tái)灣:銘傳大學(xué),2004.
[5] Lieberman H,Dyke N W V,Vivacqua A S.Let’s browse:a collaborative web browsing agent[C]//International confer-ence on intelligent user interfaces.[s.l.]:[s.n.],1999.
[6] 孫小華.協(xié)同過(guò)濾系統(tǒng)的稀疏性與冷啟動(dòng)問(wèn)題研究[D].杭州:浙江大學(xué),2005.
[7] 楊 博,趙鵬飛.推薦算法綜述[J].山西大學(xué)學(xué)報(bào):自然科學(xué)版,2011,34(3):337-350.
[8] 馮旻遠(yuǎn).綜合用戶特征的協(xié)同過(guò)濾推薦算法的研究[D].南京:南京郵電大學(xué),2014.
[9] 涂金龍.基于tag的個(gè)性化推薦技術(shù)研究[D].重慶:重慶大學(xué),2013.
[10] 張 馳,陳 剛,王慧敏.基于混合推薦技術(shù)的推薦模型[J].計(jì)算機(jī)工程,2010,36(22):248-250.
[11] Liu Z.Collaborative filtering recommendation algorithm based on user interests[J].International Journal of u- and e- Service,Science and Technology,2015,8(4):311-320.
[12] 劉 鋼,王敏娟,張 馳,等.移動(dòng)學(xué)習(xí)中的數(shù)據(jù)挖掘研究[J].中國(guó)遠(yuǎn)程教育,2011(1):31-35.
[13] 路東方,許俊富,項(xiàng)超娟,等.生物大數(shù)據(jù)中的聚類方法分析[J].上海大學(xué)學(xué)報(bào):自然科學(xué)版,2016,22(1):45-57.
[14] 許麗利.聚類分析的算法及應(yīng)用[D].長(zhǎng)春:吉林大學(xué),2010.
[15] 陳 俊,吳紹春,盛春健.基于概念格的聚類分析[J].上海大學(xué)學(xué)報(bào):自然科學(xué)版,2008,14(4):432-435.
[16] 杜瑞杰.貝葉斯分類器及其應(yīng)用研究[D].上海:上海大學(xué),2012.
[17] 程劍鋒,徐俊艷.基于EM算法的有監(jiān)督LVQ神經(jīng)網(wǎng)絡(luò)及其應(yīng)用[J].系統(tǒng)工程與電子技術(shù),2005,27(1):121-123.
[18] 李 慧,馬小平,胡 云,等.融合社會(huì)網(wǎng)絡(luò)與信任度的個(gè)性化推薦方法研究[J].計(jì)算機(jī)應(yīng)用研究,2014,31(3):808-810.
[19] 黃創(chuàng)光,印 鑒,汪 靜,等.不確定近鄰的協(xié)同過(guò)濾推薦算法[J].計(jì)算機(jī)學(xué)報(bào),2010,33(8):1369-1377.
[20] 陳宗言,顏 俊.基于稀疏數(shù)據(jù)預(yù)處理的協(xié)同過(guò)濾推薦算法[J].計(jì)算機(jī)技術(shù)與發(fā)展,2016,26(7):59-64.
[21] 高 倩,何聚厚.改進(jìn)的面向數(shù)據(jù)稀疏的協(xié)同過(guò)濾推薦算法[J].計(jì)算機(jī)技術(shù)與展,2016,26(3):63-66.
[22] 張拭心.余弦距離、歐氏距離和杰卡德相似性度量的對(duì)比分析[EB/OL].2013.http://www.cnblogs.com/chaosimple/archive/2013/06/28/3160839.html.
[23] 趙琴琴,魯 凱,王 斌.SPCF:一種基于內(nèi)存的傳播式協(xié)同過(guò)濾推薦算法[J].計(jì)算機(jī)學(xué)報(bào),2013,36(3):671-676.
[24] 吳想想.基于Android平臺(tái)軟件開發(fā)方法的研究與應(yīng)用[D].北京:北京郵電大學(xué),2011.
ResearchandApplicationofAlgorithmBasedonMaximumExpectationandCollaborativeFiltering
FAN Ying1,HAO Lin-na1,YI Hua1,JI Qing-jing2,XU Hua-hu3,YIN Fang-min3
(1.State Grid Shanghai Municipal Electric Power Company Training Center,Shanghai 200438,China;2.State Grid Shanghai Municipal Electric Power Company Overhauls Company,Shanghai 200029,China;3.School of Computer Engineering and Science,Shanghai University,Shanghai 200444,China)
The problem of sparse information is easily found in the information search for new user in recommendation system,and the difficulty is produced when recommending the relevant module for users.In view of the problem,the maximum expectation algorithm in demographics is adopted to cluster users for neighboring users,and then it is regarded as input of collaborative filtering algorithm.As the user’s scores on different projects show that they demand,in the evaluation of the project from same user there is certain demand relevance.And this kind of relevance degree is gradually changing with the change of individual demand.Therefore,a cooperative filtering algorithm based on the change of user demand is put forward by introducing a time weight function,which alleviates the shortness of traditional cooperative filtering recommendation algorithm.Can track the needs of users,and then predict the score matrix.According to experiments comparison,this algorithm can help solve the problem of sparseness of user’s scoring matrix and the recommendation quality is improved.
sparseness;maximum expectation algorithm;collaborative filtering;personalized recommendation
TP391
A
1673-629X(2017)12-0139-05
10.3969/j.issn.1673-629X.2017.12.030
2016-11-16
2017-03-22 < class="emphasis_bold">網(wǎng)絡(luò)出版時(shí)間
時(shí)間:2017-08-01
國(guó)家自然科學(xué)基金資助項(xiàng)目(61572306,61502294);上海市自然科學(xué)基金(15ZR1415200);上海市科委重點(diǎn)項(xiàng)目(14590500500);2015年教育科研網(wǎng)-賽爾網(wǎng)絡(luò)下一代互聯(lián)網(wǎng)技術(shù)創(chuàng)新項(xiàng)目(NGII20150609)
范 瑩(1987-),女,碩士研究生,研究方向?yàn)樾畔⒒夹g(shù)在教育培訓(xùn)中的應(yīng)用;許華虎,博士,教授,研究方向?yàn)槎嗝襟w網(wǎng)絡(luò)技術(shù)、教育大數(shù)據(jù)。
http://kns.cnki.net/kcms/detail/61.1450.TP.20170801.1551.040.html