范 瑩，郝琳娜，易 華，吉青晶，許華虎，尹方敏

(1.國家電網(wǎng)上海市電力公司培訓中心,上海 200438;2.國家電網(wǎng)上海市電力公司檢修公司,上海 200029；3.上海大學 計算機工程與科學學院,上海 200444)

基于最大期望和協(xié)同過濾算法的研究與應用

范 瑩1，郝琳娜1，易 華1，吉青晶2，許華虎3，尹方敏3

(1.國家電網(wǎng)上海市電力公司培訓中心,上海 200438;2.國家電網(wǎng)上海市電力公司檢修公司,上海 200029；3.上海大學 計算機工程與科學學院,上海 200444)

推薦系統(tǒng)中新用戶在信息搜索中易出現(xiàn)信息稀疏的問題，以致給用戶推薦相關模塊的時候帶來了極大困難。針對該問題，采用人口統(tǒng)計學中的最大期望算法對用戶進行聚類找到近鄰用戶，然后將其作為協(xié)同過濾算法的輸入。由于用戶對不同項目的評分表明他們需求，相同用戶評價的項目中存在一定的需求關聯(lián)性。而且隨著個人需求的變化，這種關聯(lián)度也逐漸在變化。所以通過引入一個時間權重函數(shù)的形式，給出一種基于用戶需求變化的協(xié)同過濾算法，緩解傳統(tǒng)協(xié)同過濾推薦算法的短板?？梢宰粉櫟接脩舻男枨?，進而預測評分矩陣。通過實驗和比較，該算法有助于解決用戶的評分矩陣稀疏性問題，從而提高推薦質(zhì)量。

稀疏性；最大期望算法；協(xié)同過濾；個性化推薦

1 概 述

1.1 研究現(xiàn)狀

處在如今這樣一個大數(shù)據(jù)信息時代，用戶對信息的需求得到了滿足，但隨著網(wǎng)絡信息量的大幅度增長，使得用戶在搜索信息時無法直接有效地獲取到自己需要的信息，“信息爆炸”也因此而形成。數(shù)據(jù)挖掘網(wǎng)站逐漸興起，協(xié)同過濾相關的推薦系統(tǒng)[1-5]在國外應用廣泛，并取得了很高的應用價值。

國外著名的應用案例有協(xié)同過濾系統(tǒng)[6]和Amazon個性化系統(tǒng)[7]。Tapestry[6]是已知的最早投入使用的協(xié)同過濾系統(tǒng)，主要用于解決信息過載問題；Group Lens[8]通過用戶-項目的評分矩陣來計算用戶的相似性，尋找目標用戶的最相似鄰居的數(shù)據(jù)集，并根據(jù)這個數(shù)據(jù)集來產(chǎn)生推薦結果；Amazon個性化系統(tǒng)在給用戶推薦個性化圖書的同時，極大地提高了銷售額。

國內(nèi)的相關使用在近些年慢慢起步，研究水平和引用規(guī)模正逐年提升。國內(nèi)比較好的應用[9]有互動出版網(wǎng)網(wǎng)上書店(http://www.china-pub.com/)以及網(wǎng)上文章推薦小助手(http://www.360doc.com/)等?；映霭婢W(wǎng)的會員[6]有一個“我的China-Pub”頁面,上面記錄會員用戶的歷史日志，會員還可以個性化定制個人的喜好；360doc通過對網(wǎng)站文章進行相關性分析和判斷，在內(nèi)容高度相關的文章間建立關聯(lián)，能夠看到很多“相關文章”。

1.2 存在的問題

在給用戶提供個性化服務之前，大多數(shù)時候系統(tǒng)已經(jīng)記錄了用戶的基本信息。但是新用戶沒有歷史行為信息以供參考，因為新用戶對系統(tǒng)里所有項目的評分都為空，也即是說新用戶的可用信息是很稀疏的，因此無法獲取到其需求點。文中采用人口統(tǒng)計學中的最大期望算法，把用戶的基本信息數(shù)據(jù)源進行聚類，找到其近鄰用戶，然后將其作為協(xié)同過濾的輸入。

在協(xié)同過濾推薦系統(tǒng)[10-11]中，基于用戶的需求挖掘是個復雜問題，用戶需求也就是對推薦項目的選擇和偏好。但是這種需求可能會隨著年齡、季節(jié)以及環(huán)境等的變化而變化。文中主要提出基于用戶需求的協(xié)同過濾算法。該算法描述了用戶需求的變換，可以預測用戶項目的評分矩陣并進行補充。

2 最大期望算法

2.1 新用戶的特征聚類

新用戶在信息搜索的過程中會出現(xiàn)信息稀疏的問題，這會使系統(tǒng)給用戶推薦相關模塊時出現(xiàn)極大困難。文中引入人口統(tǒng)計學中的最大期望算法[12]來進行聚類，將用戶的個人信息進行聚類分析[13-16]，之后目標用戶的鄰居用戶就能被找到，后續(xù)在協(xié)同過濾時將其作為用戶集輸入。

在用戶聚類時，選用性別、年齡、職務、學歷等作為特征維度。因為前人通過研究決策樹技術發(fā)現(xiàn)這些特征信息對用戶興趣的偏好能產(chǎn)生較大影響。

2.2 最大期望算法聚類

在有了全部用戶數(shù)據(jù)a的情況下，并不能確認他們來自哪個類別。若將用戶的所有數(shù)據(jù)表示成(a,b)，其中b代表a所屬分支的標簽，取值范圍為b∈(1,…,θ)。此時，全部數(shù)據(jù)的概率密度[17]的定義為：

(1)

其中，θ為密度分支的個數(shù)；r1,r2,…,rθ(1,…,θ)為分支占總體分支的比例；fi為第i個分支的密度。

θi為相應分支的未知參數(shù),在用戶數(shù)據(jù)集{x1,x2,…,xn}確定之后，再用極大似然函數(shù)[18]估計的方法計算θmax:

(2)

最大期望算法[19-21]本質(zhì)上是迭代算法，從初始解θ0迭代，陸續(xù)得到θ1,θ2,…,θt。在迭代過程中，似然函數(shù)的值一直遞增。算法流程如下：

(1)給定一個初始化分布參數(shù)θ0；

(2)對每一個遞增的θ1,θ2,…,θt，重復執(zhí)行以下步驟直至收斂：

①給定用戶數(shù)據(jù)和當前解θt，求用戶數(shù)據(jù)的對數(shù)似然函數(shù)的期望值：

(3)

其在，Eb是關于隨機變量b的期望。

②給定一個新的參數(shù)?t+1，使得這時的對數(shù)似然函數(shù)期望值達到最大值：

?t+1=argmaxQ(?|?t)

(4)

(3)一直循環(huán)迭代，可獲得?t，到最終算法收斂為止。

這樣通過最大期望迭代自適應的計算，可得到各類用戶簇和各個類別的分布特征。

3 協(xié)同過濾算法

3.1 項目評分矩陣

在推薦系統(tǒng)[22]中,用戶集合U={U1,U2,…,Us}和項目集合I={I1,I2,…,It}間存在一個用戶-項目評分矩陣，如表1所示。

表1 用戶-項目評分矩陣Rs×t

其中，矩陣[23]共有s行，代表s個用戶，t列代表t個項目。某個用戶Ui對項目Ij的評分Ri,j代表用戶i對項目j的偏好和興趣。由于用戶不可能對每個項目都有評分，所以在評分矩陣Rs×t中，有些評分是沒有的，造成了用戶-項目評分矩陣的稀疏性，使得用戶間的相似度計算變得困難。

3.2 用戶相似度計算

(1)標準余弦相似度計算用戶相似性[23]。

(5)

因為通過標準余弦相似度[24]更多地是從方向上區(qū)別向量的不同，而且對絕對的數(shù)值不敏感，不能很好地衡量每個維度上數(shù)值的差異，從而造成巨大的誤差。所以通過對所有的維度上的數(shù)值都減去一個均值來進行調(diào)整。

(2)調(diào)整余弦相似度。

為了調(diào)整因為不同用戶對同種項目評分的偏差，通過對所有維度上的數(shù)值都減去一個均值來降低結果的誤差。

Sim(Ua,Ub)=

(6)

3.3 用戶需求變化問題

(1)基于時間的權重函數(shù)。

為了更好地觀察用戶的需求變化問題，提出一個時間權重函數(shù)TWF(u,i):

(7)

其中，tui表示用戶u當前訪問項目i的時間減去最近一次訪問項目i的時間的差值; Ltui表示用戶u當前訪問項目i的時間與最遠一次訪問項目i的時間的差值；ε表示權重變化指數(shù)，ε∈(0,1)，ε越大說明用戶對項目i的關注越頻繁。

(2)改進的余弦相似性。

在計算用戶的相似性時，將用戶-項目評分矩陣中的每一個評分值都乘上基于時間的權重函數(shù)，以獲得更高的精度。

(8)

3.4 用戶-項目評分預測

在用戶相似度取得一個比較精確的值后，可以對用戶-項目評分矩陣中沒有的評分值進行預測。采用全局數(shù)值算法，以用戶對相似產(chǎn)品的評分的相似度作為權值來生成預測評分。

(9)

其中，n為用戶數(shù)量；Prai為用戶a對項目i的預測評分。

4 算法設計和分析

4.1 算法步驟

輸入：用戶特征維度，用戶-產(chǎn)品評分矩陣Rs×t，s個用戶對t個項目評分的歷史記錄時間，時間權重指數(shù)ε；

輸出：給用戶的N個推薦項目。

Step1:利用給定的用戶集合U={U1,U2,…,Us}和相關特征數(shù)據(jù)，通過最大期望迭代聚類找到目標用戶的近鄰用戶，見式(3)和式(4)；

Step2:利用用戶-產(chǎn)品評分矩陣Rs×t和時間權重函數(shù)TWF(u,i)，計算基于用戶興趣的評分相似性，見式(8)；

Step3:在式(8)的基礎上，采用全局數(shù)值算法對用戶對產(chǎn)品的評分進行預測，見式(9)。

4.2 算法流程

如圖1所示，用戶登錄系統(tǒng)后，首先判斷其個人信息數(shù)據(jù)是否稀疏，看是否需要通過最大期望聚類操作來為其選取近鄰用戶。之后以此數(shù)據(jù)作為協(xié)同過濾的數(shù)據(jù)集，并根據(jù)用戶-項目評分矩陣和時間權重函數(shù)計算基于用戶興趣的評分相似性，進而為目標用戶進行資源推薦。

圖1 整體框圖

4.3 實驗分析

4.3.1 評估標準

對于推薦系統(tǒng)的有效性，研究人員提出了許多評估標準來進行驗證，大概包括兩類：驗證推薦結果的準確性；驗證算法時間和空間的復雜度。平均絕對誤差(MAE)能更好地反映預測值誤差的實際情況,文中選擇其作為評估標準。這種評估標準首先隱藏目標用戶的真實評分，然后通過基于用戶需求的協(xié)同過濾推薦算法預測其對項目的評分，最后通過預測值和真實值之間的差異累積得到平均絕對誤差。

假設預測評分值為{p1,p2,…,pn}，對應的真實評分值為{q1,q2,…,qn}，通過式(10)計算得到平均絕對誤差：

(10)

MAE的值與推薦的準確率呈反比。

4.3.2 數(shù)據(jù)源

選擇網(wǎng)站http://grouplens.org/datasets/moviele-ns/上提供的數(shù)據(jù)集進行驗證，提取該數(shù)據(jù)集中1 000個用戶對1 700部電影的評分數(shù)據(jù)作為實驗數(shù)據(jù)。

4.3.3 實驗環(huán)境

實驗環(huán)境如表2所示。

表2 實驗環(huán)境信息

4.3.4 實驗結果

實驗結果如圖2所示。

圖2 MAE值比較

由實驗結果可見，基于用戶需求變化的協(xié)同過濾算法(CFBUIE)的精確性高于傳統(tǒng)的協(xié)同過濾算法(CF)。

5 算法應用

5.1 應用設計

在上海市電力公司職工的“電力行業(yè)考試中心系統(tǒng)”在線版的基礎上，實現(xiàn)了最大期望算法聚類和基于用戶需求的協(xié)同過濾推薦相關算法。運用Android編程技術為其開發(fā)了移動端版本，將其在線版的數(shù)據(jù)移植到APP的版本上，在延續(xù)網(wǎng)頁版的同時，為廣大職工提供個性化推薦服務。整體流程如圖3所示。

圖3 整體流程

5.2 應用展示

Android應用界面如圖4所示。功能涉及到考試學習的信息發(fā)布與管理，自助學習，自助練習，自助測試。移動平臺可以建立針對個人的學習內(nèi)容管理、學習進度管理、練習管理、練習成果分析、模擬考試等多種功能，能夠滿足用戶的個性化需求。

圖4 Android應用界面展示

6 結束語

針對新用戶可用信息稀疏的問題，采用最大期望算法對用戶進行聚類；針對現(xiàn)有協(xié)同過濾算法不能快速發(fā)現(xiàn)用戶需求變化的問題,提出基于時間的數(shù)據(jù)權重函數(shù)，將其引進到傳統(tǒng)的協(xié)同過濾推薦算法中以反映用戶需求的動態(tài)變化,緩解了傳統(tǒng)協(xié)同過濾推薦算法的短板，提高了推薦的準確性。今后會繼續(xù)對相關算法展開研究，提高其使用范圍，推廣到各行各業(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] 簡士堯.以內(nèi)容為基礎之網(wǎng)絡學習導覽推薦之研究[D].臺灣:銘傳大學,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é)同過濾系統(tǒng)的稀疏性與冷啟動問題研究[D].杭州:浙江大學,2005.

[7] 楊 博,趙鵬飛.推薦算法綜述[J].山西大學學報:自然科學版,2011,34(3):337-350.

[8] 馮旻遠.綜合用戶特征的協(xié)同過濾推薦算法的研究[D].南京:南京郵電大學,2014.

[9] 涂金龍.基于tag的個性化推薦技術研究[D].重慶:重慶大學,2013.

[10] 張 馳,陳 剛,王慧敏.基于混合推薦技術的推薦模型[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] 劉 鋼,王敏娟,張 馳,等.移動學習中的數(shù)據(jù)挖掘研究[J].中國遠程教育,2011(1):31-35.

[13] 路東方,許俊富,項超娟,等.生物大數(shù)據(jù)中的聚類方法分析[J].上海大學學報:自然科學版,2016,22(1):45-57.

[14] 許麗利.聚類分析的算法及應用[D].長春:吉林大學,2010.

[15] 陳 俊,吳紹春,盛春健.基于概念格的聚類分析[J].上海大學學報：自然科學版,2008,14(4):432-435.

[16] 杜瑞杰.貝葉斯分類器及其應用研究[D].上海：上海大學,2012.

[17] 程劍鋒,徐俊艷.基于EM算法的有監(jiān)督LVQ神經(jīng)網(wǎng)絡及其應用[J].系統(tǒng)工程與電子技術,2005,27(1):121-123.

[18] 李 慧,馬小平,胡 云,等.融合社會網(wǎng)絡與信任度的個性化推薦方法研究[J].計算機應用研究,2014,31(3):808-810.

[19] 黃創(chuàng)光,印 鑒,汪 靜,等.不確定近鄰的協(xié)同過濾推薦算法[J].計算機學報,2010,33(8):1369-1377.

[20] 陳宗言,顏 俊.基于稀疏數(shù)據(jù)預處理的協(xié)同過濾推薦算法[J].計算機技術與發(fā)展,2016,26(7):59-64.

[21] 高 倩,何聚厚.改進的面向數(shù)據(jù)稀疏的協(xié)同過濾推薦算法[J].計算機技術與展,2016,26(3):63-66.

[22] 張拭心.余弦距離、歐氏距離和杰卡德相似性度量的對比分析[EB/OL].2013.http://www.cnblogs.com/chaosimple/archive/2013/06/28/3160839.html.

[23] 趙琴琴,魯 凱,王 斌.SPCF:一種基于內(nèi)存的傳播式協(xié)同過濾推薦算法[J].計算機學報,2013,36(3):671-676.

[24] 吳想想.基于Android平臺軟件開發(fā)方法的研究與應用[D].北京:北京郵電大學,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)絡出版時間

時間：2017-08-01

國家自然科學基金資助項目(61572306,61502294)；上海市自然科學基金(15ZR1415200)；上海市科委重點項目(14590500500)；2015年教育科研網(wǎng)-賽爾網(wǎng)絡下一代互聯(lián)網(wǎng)技術創(chuàng)新項目(NGII20150609)

范 瑩(1987-)，女，碩士研究生，研究方向為信息化技術在教育培訓中的應用；許華虎，博士，教授，研究方向為多媒體網(wǎng)絡技術、教育大數(shù)據(jù)。

http://kns.cnki.net/kcms/detail/61.1450.TP.20170801.1551.040.html