劉偉友,吳 陳
(江蘇科技大學(xué)計(jì)算機(jī)學(xué)院,江蘇鎮(zhèn)江 212100)
在互聯(lián)網(wǎng)深度融合和大數(shù)據(jù)蓬勃發(fā)展的時(shí)代背景下,信息資源呈現(xiàn)爆發(fā)式增長,由此帶來信息過載、用戶需求不明確等問題[1]。目前,應(yīng)對這些問題的主要手段包括搜索引擎和推薦系統(tǒng)。其中,搜索引擎可對信息資源進(jìn)行過濾、篩選,但當(dāng)用戶難以鍵入需求時(shí),搜索引擎便無法發(fā)揮作用;推薦系統(tǒng)則是一種智能化應(yīng)用軟件,旨在滿足用戶當(dāng)前最需要或最感興趣的信息[2],即使在用戶需求不明確的情況下,也能提供持續(xù)、有效的個(gè)性化推薦服務(wù),因而具有巨大的應(yīng)用優(yōu)勢和商業(yè)價(jià)值,被廣泛運(yùn)用于新聞、音樂、視頻和電商等領(lǐng)域,例如谷歌新聞[3]、網(wǎng)易云音樂、Netflix網(wǎng)絡(luò)流媒體、Amazon 電商等。
推薦算法作為推薦系統(tǒng)的核心引擎,是專家學(xué)者研究的熱點(diǎn)與重點(diǎn),主要可分為基于內(nèi)容的推薦算法、基于協(xié)同過濾(Collaborative Filtering,CF)的推薦算法和混合推薦算法[4]。具體的,基于協(xié)同過濾的推薦算法是影響最深遠(yuǎn)、應(yīng)用最廣泛的傳統(tǒng)推薦算法,最早可追溯至1992 年Goldberg 等[5]設(shè)計(jì)的Tapestry 電子郵件過濾系統(tǒng),但由于算法的輸入數(shù)據(jù)通常呈現(xiàn)高維性和稀疏性,存在準(zhǔn)確性、實(shí)時(shí)性、可擴(kuò)展性不足等問題[6-7]。為此,劉晴晴等[8]采用奇異值分解(Singular Value Decomposition,SVD)算法分解、填充評分矩陣,有效緩解數(shù)據(jù)稀疏問題,但傳統(tǒng)SVD 算法并未考慮用戶評分習(xí)慣和上下文環(huán)境因素,預(yù)測評分效果一般。張陽等[9]提出一種融合用戶顯式反饋和隱式反饋的SVD++自適應(yīng)推薦算法,但算法實(shí)時(shí)性較差。Frémal 等[10]利用組合聚類算法對項(xiàng)目特征進(jìn)行聚類。Chen 等[11]根據(jù)群體智能思想劃分用戶群組,加快查找最近鄰居的時(shí)間,提升算法實(shí)時(shí)性,但忽視輸入數(shù)據(jù)自身稀疏性。
由此可見,僅使用單一算法推薦存在明顯的性能瓶頸,目前往往混合使用多種推薦算法解決該問題。例如,魏浩等[12]先對用戶進(jìn)行聚類得到近鄰用戶集,再取用戶集的平均評分填充稀疏矩陣,最后使用SVD 算法分解重構(gòu)矩陣產(chǎn)生推薦結(jié)果。劉超等[13]利用改進(jìn)BiasSVD 算法預(yù)測評分,對用戶進(jìn)行聚類并調(diào)整預(yù)測偏差。Nilashi 等[14]結(jié)合主成分分析(Principal Component Analysis,PCA)、自組織映射(Self-Organizing Map,SOM)和期望最大化(Expectation Maximization,EM)技術(shù)構(gòu)建旅游推薦系統(tǒng)。以上混合推薦算法兼顧了數(shù)據(jù)稀疏性問題和算法準(zhǔn)確性要求,但均未解決用戶冷啟動(dòng)問題[15],且無法反映用戶興趣變化造成的評分影響。
為此,本文提出一種基于多源數(shù)據(jù)聚類和奇異值分解的混合推薦算法,主要貢獻(xiàn)包括:①提出一種從多源數(shù)據(jù)中充分挖掘并有效整合用戶信息的處理辦法,改善傳統(tǒng)K-means 聚類算法輸入數(shù)據(jù)單一的問題,提升算法推薦準(zhǔn)確性,在一定程度上緩解了用戶冷啟動(dòng)問題;②定義一種新的時(shí)間衰減函數(shù)改進(jìn)預(yù)測評分計(jì)算公式和BiasSVD 算法的損失函數(shù),以反映用戶興趣變化對電影評分造成的影響;③將基于多源數(shù)據(jù)的K-means 聚類算法和融合時(shí)間衰減函數(shù)的BiasSVD 算法相互結(jié)合,通過實(shí)驗(yàn)選取模型最佳參數(shù)進(jìn)行比較,分析兩種改進(jìn)因素各自的作用效果和本文所提出算法的推薦性能。
由于用戶—項(xiàng)目評分矩陣具有高維性和稀疏性特性,首先引入K-means 聚類算法[16]對用戶進(jìn)行聚類,以此構(gòu)建多個(gè)較低維的用戶類簇評分矩陣。如此,一方面可減少系統(tǒng)內(nèi)存消耗,加快后續(xù)矩陣分解計(jì)算,提升算法整體運(yùn)行效率;另一方面,基于相似度較高的用戶類簇進(jìn)行評分預(yù)測,推薦結(jié)果更準(zhǔn)確。
聚類是將一個(gè)數(shù)據(jù)集合劃分為多個(gè)由相似數(shù)據(jù)對象組成的子集合(即類簇)的過程,每一個(gè)數(shù)據(jù)對象和本類簇的其它數(shù)據(jù)對象相似,但與其它類簇的數(shù)據(jù)對象相異。Kmeans 算法是一種簡單、有效的聚類算法。其中,K 為要?jiǎng)澐值念惔財(cái)?shù)目,即質(zhì)心個(gè)數(shù);means 代表類簇中全部數(shù)據(jù)對象的均值,數(shù)據(jù)對象之間的相似度通過彼此的距離來衡量,距離越小表明數(shù)據(jù)對象之間相似度越高,越應(yīng)該被劃分至同一類簇。K-means 算法具體過程如算法1所示。
算法1K-means 聚類算法
為評估用戶對某一類型項(xiàng)目的喜愛偏好程度,利用詞頻—逆文檔頻率(Term Frequency-Inverse Document Frequency,TF-IDF)公式[17]對該指標(biāo)進(jìn)行評估:
其中,t為文檔d中的某一詞條,TFt,d為詞條t在文檔d中出現(xiàn)的頻率,nt,d為詞條t在文檔d中出現(xiàn)的次數(shù)表示文檔d的總詞數(shù),IDFt為詞條t在文檔總集中的逆文檔頻率,表示詞條t的普遍程度,D為文檔總集中的文檔總個(gè)數(shù),Dt為文檔總集中包含詞條t的文檔個(gè)數(shù),將兩者相乘可得到詞條t的詞頻—逆文檔頻率TF-IDFt,d。
由式(1)可知,當(dāng)某一詞條在某篇文檔出現(xiàn)的頻率越高(即TF值越大),且在文檔總集中被較少的文檔包含(即IDF值越大)時(shí),TF-IDF值越大,說明該詞條越重要。
基于協(xié)同過濾的推薦算法包含基于用戶和基于物品的傳統(tǒng)協(xié)同過濾推薦算法及基于模型的推薦算法?;谀P偷耐扑]算法將機(jī)器學(xué)習(xí)的思想運(yùn)用到推薦算法中,主要包括矩陣分解算法、圖模型算法、隱語義模型算法、神經(jīng)網(wǎng)絡(luò)算法等。其中,矩陣分解算法[18]由于易于實(shí)現(xiàn)且可擴(kuò)展性好被普遍使用。
本文采用矩陣分解算法對稀疏的用戶—項(xiàng)目評分矩陣進(jìn)行降維處理,由此得到用戶和項(xiàng)目的多維隱式特征向量,并利用隨機(jī)梯度下降算法產(chǎn)生預(yù)測評分,進(jìn)而填充稀疏評分矩陣?,F(xiàn)有矩陣分解算法有很多種,奇異值分解(SVD)算法[19]最為經(jīng)典,該算法主要將評分矩陣R分解為3個(gè)低維矩陣乘積,計(jì)算公式定義如下:
其中,Rm×n為評分矩陣為用戶隱式特征正交矩陣的轉(zhuǎn)置,Qk×n為項(xiàng)目隱式特征正交矩陣,Σk×k為奇異值對角矩陣。
然而,SVD 計(jì)算過程非常復(fù)雜,且運(yùn)用SVD 的前提是Rm×n是稠密的,但推薦系統(tǒng)中Rm×n往往非常稀疏。為此,Simon[20]提出一種FunkSVD 算法,將評分矩陣R近似分解為兩個(gè)低秩矩陣乘積的形式,計(jì)算公式如下:
其中,μ為所有用戶對所有項(xiàng)目評分的均值,bu為用戶評分的偏置,bi為項(xiàng)目被評分的偏置。
傳統(tǒng)K-means 聚類算法的輸入通常為用戶—項(xiàng)目評分?jǐn)?shù)據(jù),但該輸入的基本假設(shè)是推薦系統(tǒng)已經(jīng)運(yùn)行了一段時(shí)間,采集到用戶和項(xiàng)目之間的顯式和隱式反饋數(shù)據(jù)。為進(jìn)一步提高推薦算法準(zhǔn)確性,緩解推薦系統(tǒng)用戶冷啟動(dòng)的問題,結(jié)合基于人口統(tǒng)計(jì)學(xué)的推薦和基于內(nèi)容的推薦的算法思想,對傳統(tǒng)K-means 聚類算法的輸入數(shù)據(jù)進(jìn)行改進(jìn)。
以MovieLens 數(shù)據(jù)集為例,改進(jìn)后的K-means 聚類算法在用戶—電影評分?jǐn)?shù)據(jù)的基礎(chǔ)上增加了用戶特征數(shù)據(jù)和電影類型特征數(shù)據(jù)。為此,對于輸入的多源數(shù)據(jù),首先要進(jìn)行以特征工程為主的數(shù)據(jù)預(yù)處理,具體操作如下:
(1)特征選擇。例如,去除電影的來源網(wǎng)址數(shù)據(jù)。
(2)連續(xù)數(shù)值型特征的歸一化和離散化。例如,將用戶年齡從小到大劃分為7個(gè)年齡階段。
(3)非數(shù)值型特征采用One-Hot 編碼。例如,將用戶性別采用[0]、[1]進(jìn)行編碼;將電影分為19 種類型,按照類型假定的先后順序分別用[0]、[1]進(jìn)行編碼。
數(shù)據(jù)預(yù)處理完成后,可得到用戶特征矩陣A、用戶—電影評分矩陣R和電影類型特征矩陣B:
其中,um表示第m位用戶,fs表示用戶的第s個(gè)特征,表示第m位用戶在第s個(gè)特征上的取值,in表示第n部電影,gt表示電影的第t種類型特征表示第n部電影在第t種類型特征上的取值,該值為0 時(shí),代表電影in沒有類型特征gt。由于某些電影包含多種類型,因此表示第m位用戶對第n部電影的評分,該值取[1,5]內(nèi)的整數(shù)。
此外,用戶對電影的喜好除了直接通過用戶對某電影的評分進(jìn)行衡量,還可通過用戶觀看某類型電影的個(gè)數(shù)進(jìn)行體現(xiàn)。因此,對用戶—電影評分矩陣R進(jìn)行統(tǒng)計(jì)處理可得到用戶—電影觀看矩陣R',在此基礎(chǔ)上,結(jié)合電影類型特征矩陣B并利用TF -IDF 公式可得到用戶—電影偏好矩陣H。R'和H的形式分別定義如下:
其中,被乘數(shù)的分子表示用戶ux觀看過的電影中含有類型gz的電影總數(shù),分母表示用戶ux觀看過的電影中各個(gè)類型的電影個(gè)數(shù)的和,log 中的分子表示所有電影中各個(gè)類型的電影個(gè)數(shù)之和,分母表示所有電影中含有類型gz的電影總數(shù)。由式(8)可知,當(dāng)某一類型電影在某用戶的觀看列表中出現(xiàn)的頻率越高,且包含該類型的電影在所有電影中占比較小時(shí),對應(yīng)的值越大,說明該用戶更偏愛此類型電影。
最后,合并用戶特征矩陣A,用戶—電影評分矩陣R和用戶—電影偏好矩陣H可得到用戶矩陣W,定義如下:
傳統(tǒng)的K-means 聚類算法中距離包括歐氏距離及余弦相似度。其中,歐氏距離反映的是向量各維度數(shù)值上的絕對差異性,余弦相似度反映的是向量整體方向上的相對差異性。由于本文算法輸入包含較多的非數(shù)值型特征,例如用戶性別、電影類型等信息,采用余弦相似度更能刻畫兩個(gè)用戶特征向量之間的相似程度。余弦相似度定義如下:
多源數(shù)據(jù)的K-means 聚類算法如算法2,對應(yīng)的算法流程圖如圖1所示。
Fig.1 Flow chart of K-means clustering algorithm based on multisource data圖1 基于多源數(shù)據(jù)的K-means聚類算法流程圖
算法2基于多源數(shù)據(jù)的K-means 聚類算法
一般情況下,用戶對電影的興趣并非一成不變,而隨著時(shí)間發(fā)生變化。相較于用戶早期觀影行為,用戶近期觀影行為更能反映用戶當(dāng)前的興趣。
然而,傳統(tǒng)BiasSVD 算法并未考慮時(shí)間因素的影響,無法反映用戶興趣的變化。因此,本文引入一種時(shí)間衰減函數(shù)對該算法進(jìn)行優(yōu)化:
其中,τu,i為用戶u對電影i評分時(shí)的時(shí)間,T為系統(tǒng)當(dāng)前時(shí)間,θ為時(shí)間衰減參數(shù),根據(jù)推薦系統(tǒng)中用戶興趣變化的快慢程度自行設(shè)定。如果用戶興趣變化較快,則θ取較大數(shù)值;反之,θ取較小數(shù)值。鑒于用戶觀影興趣變化較慢,本文θ取較小數(shù)值。
其中,μ為所有用戶對所有項(xiàng)目評分的均值,bu為用戶評分的偏置,bi為項(xiàng)目被評分的偏置,β為調(diào)節(jié)參數(shù),qi,l(τu,i)表示時(shí)間衰減函數(shù)φ(τu,i)對電影i的隱式特征l的影響程度??傻萌诤蠒r(shí)間衰減函數(shù)的BiasSVD 的損失函數(shù)為:
其中,Loss前半部分為平方誤差項(xiàng),后半部分為正則化項(xiàng),λ為正則化系數(shù),設(shè)學(xué)習(xí)率為α,分別對pu、qi、bu、bi和β求偏導(dǎo),根據(jù)隨機(jī)梯度下降算法的思想,可得如下遞推公式:
結(jié)合多源數(shù)據(jù)的K-means 聚類算法與融合時(shí)間衰減函數(shù)的BiasSVD 算法,可發(fā)揮兩種算法的各自優(yōu)勢。混合推薦算法如算法3所示:
算法3基于多源數(shù)據(jù)聚類和奇異值分解的混合推薦算法
采用美國明尼蘇達(dá)大學(xué)收集整理的MovieLens-100k公開數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)[22],該數(shù)據(jù)集的評分?jǐn)?shù)據(jù)整體稀疏度約為93.70%,屬于高維稀疏矩陣。其中,文件u.item 為電影屬性數(shù)據(jù),主要包含電影ID、電影名稱、發(fā)布日期、電影類型4 個(gè)字段;文件u.user 為用戶人口統(tǒng)計(jì)學(xué)數(shù)據(jù),主要包含用戶ID、年齡、性別、職業(yè)4 個(gè)字段;文件u.data 為用戶—電影評分?jǐn)?shù)據(jù),包含用戶ID、電影ID、電影評分、時(shí)間戳4個(gè)字段。每位用戶至少對20 部電影進(jìn)行評分,評分取[1,5]內(nèi)的整數(shù)值,評分越高表明用戶對該電影越喜愛。實(shí)驗(yàn)采用5 折交叉驗(yàn)證法,最終實(shí)驗(yàn)結(jié)果取多次實(shí)驗(yàn)的平均值。
采用平均絕對誤差(MAE)評估用戶實(shí)際評分與算法預(yù)測評分之間的差異,計(jì)算公式如下:
其中,|T|為測試集中的評分總數(shù)分別為用戶u對電影i的實(shí)際評分和預(yù)測評分。MAE越小,說明模型預(yù)測評分與用戶實(shí)際評分越接近,算法預(yù)測評分準(zhǔn)確度越高。
晨讀時(shí),我發(fā)現(xiàn)教室內(nèi)空位很多,一問才知道,兩人在機(jī)房準(zhǔn)備余姚市編程復(fù)賽,三人在書法教室準(zhǔn)備校書法比賽,兩名校男足隊(duì)員正在操場訓(xùn)練……一日之計(jì)在于晨,見到這種情形,班主任兼語文老師的我是不是該著急了呢?更著急的是家長,眼看再過半年多就要畢業(yè)了,先后好幾位家長都十分擔(dān)心地問我:參加這些活動(dòng)會(huì)不會(huì)影響孩子的成績?
采用精確率(Precision)和召回率(Recall)評價(jià)算法的推薦性能,計(jì)算公式如下:
其中,R(u)表示訓(xùn)練集中為用戶u生成的推薦列表,T(u)表示測試集中用戶u實(shí)際的興趣列表。Precision值越高,說明推薦列表中用戶喜歡的電影部數(shù)占推薦列表總數(shù)的比例越高;Recall值越高,說明推薦列表中用戶喜歡的電影部數(shù)占用戶喜歡的電影總數(shù)的比例越高。
采用F_measure對Precision、Recall的值進(jìn)行調(diào)和,計(jì)算公式如下:
為了使算法取得最佳效果,首先對相關(guān)參數(shù)進(jìn)行調(diào)節(jié)。具體參數(shù)包括聚類質(zhì)心個(gè)數(shù)k、隱式特征維度K、學(xué)習(xí)率α、最大迭代次數(shù)svd_max_iter和推薦列表長度N。由于α和svd_max_iter對推薦算法的性能影響較小,根據(jù)以往經(jīng)驗(yàn),先取α=0.02、svd_max_iter=100 并結(jié)合評測指標(biāo)進(jìn)行控制變量實(shí)驗(yàn)。
為了確定聚類質(zhì)心個(gè)數(shù)k的最優(yōu)取值,固定K=5、N=3觀察k的取值變化對MAE的影響,結(jié)果如圖2所示。
Fig.2 The influence of different clustering number k on MAE圖2 聚類質(zhì)心個(gè)數(shù)k對平均絕對誤差MAE的影響
由圖2 可見,隨著k取值不斷增大,MAE先遞減后遞增,在k=22 處取得最小值,故選取k=22 作為聚類的質(zhì)心個(gè)數(shù)。
由于隱式特征維度K的大小直接影響到重構(gòu)后評分預(yù)測的準(zhǔn)確度,K過小會(huì)導(dǎo)致原評分矩陣信息損失嚴(yán)重,最終預(yù)測誤差大;K過大會(huì)導(dǎo)致算法的時(shí)間和空間復(fù)雜度過高。為此,設(shè)定k=22、N=30 評估K對MAE值的影響,結(jié)果如圖3所示。
Fig.3 The influence of different implicit feature dimension number K on MAE圖3 隱式特征維度K對平均絕對誤差MAE的影響
由圖3 可見,當(dāng)K<40 時(shí),MAE隨著K的增大而下降;當(dāng)K≥40 時(shí),MAE的下降趨勢趨于平緩。綜合考慮算法準(zhǔn)確度、時(shí)間復(fù)雜度和空間復(fù)雜度等方面的要求,設(shè)定K=40。
為了確定學(xué)習(xí)率α和最大迭代次數(shù)svd_max_iter,實(shí)驗(yàn)采取調(diào)節(jié)學(xué)習(xí)率α,記錄算法收斂時(shí)的迭代次數(shù)Steps和MAE分析α的取值,結(jié)果如表1所示。
Table 1 The influence of different learning rate α on iterations number Steps and MAE表1 學(xué)習(xí)率α對迭代次數(shù)Steps和平均絕對誤差MAE的影響
由表1 可知,在0.010~0.031 內(nèi),以0.003 遞增調(diào)節(jié)α的過程中,當(dāng)α=0.016 時(shí)迭代次數(shù)最少,算法收斂最快,對應(yīng)的MAE也相對較小。
在 確 定k=22、K=40、α=0.016、svd_max_iter=90后,研究推薦列表長度N對算法精確率Precision和召回率Recall的影響,并結(jié)合F_measure選取最佳N值,結(jié)果如圖4所示。
Fig.4 The influence of different recommended list length N on Precision,Recall and F-measure圖4 推薦列表長度N對精確率Precision、召回率Recall和F-measure值的影響
由圖4 可見,隨著N值的不斷增大,Precision先增大后逐漸減小,而Recall則不斷上升。當(dāng)N∈[25,30]左右時(shí),F(xiàn)_measure最大,當(dāng)N=27,此時(shí)綜合推薦性能最佳。
根據(jù)上述實(shí)驗(yàn)結(jié)果表明,本文算法的模型最佳參數(shù)分別為k=22、K=40、α=0.016、svd_max_iter=90、N=27。
采用MovieLens-100k 公開數(shù)據(jù)集,將本文提出的混合推薦算法(MC-TimeSVD)與只考慮單一改進(jìn)因素的基于多源數(shù)據(jù)的K-means 聚類協(xié)同過濾推薦算法(MCKMeans)、融合時(shí)間衰減函數(shù)的BiasSVD 協(xié)同過濾推薦算法(TimeSVD)、傳統(tǒng)基于K-means 聚類的協(xié)同過濾推薦算法(K-Means)和基于SVD 的協(xié)同過濾推薦算法進(jìn)行比較。具體結(jié)果如表2所示。
Table 2 The best precision and recall of each algorithm表2 5種算法各自最佳的精確率Precision和召回率Recall(%)
由表2 可知,相較于傳統(tǒng)K-Means 推薦算法,MCKMeans 推薦算法在Precision和Recall分別提升3.4%和3.7%,證實(shí)從多源數(shù)據(jù)中充分挖掘并有效整合用戶信息能夠改善用戶聚類效果,緩解用戶冷啟動(dòng)問題;相較于傳統(tǒng)SVD 推薦算法,TimeSVD 推薦算法在Precision和Recall上分別提升2.9%和3.5%,證實(shí)融合新的時(shí)間衰減函數(shù)能夠較好反映用戶興趣的變化對電影評分造成的影響;相較于SVD 推薦算法,MC-TimeSVD 混合推薦算法在Precision和Recall上分別提升5.4%和6.8%,證實(shí)MC-TimeSVD 混合推薦算法能夠較好結(jié)合兩者算法的各自優(yōu)勢,有效提升了推薦綜合性能。
相較于綜合考慮兩種改進(jìn)因素的MC-TimeSVD 混合推薦算法,只考慮單一改進(jìn)因素的MC-KMeans 推薦算法和TimeSVD 推薦算法在Precision和Recall上分別下降3.7%、4.0%和2.5%、3.3%,既證實(shí)MC-TimeSVD 混合推薦算法的推薦性能是兩種改進(jìn)因素共同作用的結(jié)果,又說明MC-KMeans 推薦算法對混合推薦算法性能提升的作用更大。
本文提出基于多源數(shù)據(jù)聚類和奇異值分解的混合推薦算法,以提升算法的推薦性能,緩解用戶冷啟動(dòng)問題。該算法將用戶屬性數(shù)據(jù)、用戶—電影評分?jǐn)?shù)據(jù)和項(xiàng)目屬性數(shù)據(jù)作為輸入數(shù)據(jù),較好地緩解了用戶冷啟動(dòng)問題,并且引入改進(jìn)的K-means 聚類算法和時(shí)間衰減函數(shù)的BiasSVD算法的優(yōu)勢。實(shí)驗(yàn)結(jié)果表明,以上改進(jìn)方法均提升算法的綜合推薦性能,但僅集中在一個(gè)用戶全特征矩陣處理多源數(shù)據(jù),后續(xù)將從多視圖聚類和模型結(jié)構(gòu)優(yōu)化角度進(jìn)行研究。