劉偉友，吳 陳

（江蘇科技大學(xué)計算機學(xué)院，江蘇鎮(zhèn)江 212100）

0 引言

在互聯(lián)網(wǎng)深度融合和大數(shù)據(jù)蓬勃發(fā)展的時代背景下，信息資源呈現(xiàn)爆發(fā)式增長，由此帶來信息過載、用戶需求不明確等問題［1］。目前，應(yīng)對這些問題的主要手段包括搜索引擎和推薦系統(tǒng)。其中，搜索引擎可對信息資源進行過濾、篩選，但當(dāng)用戶難以鍵入需求時，搜索引擎便無法發(fā)揮作用；推薦系統(tǒng)則是一種智能化應(yīng)用軟件，旨在滿足用戶當(dāng)前最需要或最感興趣的信息［2］，即使在用戶需求不明確的情況下，也能提供持續(xù)、有效的個性化推薦服務(wù)，因而具有巨大的應(yīng)用優(yōu)勢和商業(yè)價值，被廣泛運用于新聞、音樂、視頻和電商等領(lǐng)域，例如谷歌新聞［3］、網(wǎng)易云音樂、Netflix網(wǎng)絡(luò)流媒體、Amazon 電商等。

推薦算法作為推薦系統(tǒng)的核心引擎，是專家學(xué)者研究的熱點與重點，主要可分為基于內(nèi)容的推薦算法、基于協(xié)同過濾（Collaborative Filtering，CF）的推薦算法和混合推薦算法［4］。具體的，基于協(xié)同過濾的推薦算法是影響最深遠、應(yīng)用最廣泛的傳統(tǒng)推薦算法，最早可追溯至1992 年Goldberg 等［5］設(shè)計的Tapestry 電子郵件過濾系統(tǒng)，但由于算法的輸入數(shù)據(jù)通常呈現(xiàn)高維性和稀疏性，存在準(zhǔn)確性、實時性、可擴展性不足等問題［6-7］。為此，劉晴晴等［8］采用奇異值分解（Singular Value Decomposition，SVD）算法分解、填充評分矩陣，有效緩解數(shù)據(jù)稀疏問題，但傳統(tǒng)SVD 算法并未考慮用戶評分習(xí)慣和上下文環(huán)境因素，預(yù)測評分效果一般。張陽等［9］提出一種融合用戶顯式反饋和隱式反饋的SVD++自適應(yīng)推薦算法，但算法實時性較差。Frémal 等［10］利用組合聚類算法對項目特征進行聚類。Chen 等［11］根據(jù)群體智能思想劃分用戶群組，加快查找最近鄰居的時間，提升算法實時性，但忽視輸入數(shù)據(jù)自身稀疏性。

由此可見，僅使用單一算法推薦存在明顯的性能瓶頸，目前往往混合使用多種推薦算法解決該問題。例如，魏浩等［12］先對用戶進行聚類得到近鄰用戶集，再取用戶集的平均評分填充稀疏矩陣，最后使用SVD 算法分解重構(gòu)矩陣產(chǎn)生推薦結(jié)果。劉超等［13］利用改進BiasSVD 算法預(yù)測評分，對用戶進行聚類并調(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)確性要求，但均未解決用戶冷啟動問題［15］，且無法反映用戶興趣變化造成的評分影響。

為此，本文提出一種基于多源數(shù)據(jù)聚類和奇異值分解的混合推薦算法，主要貢獻包括：①提出一種從多源數(shù)據(jù)中充分挖掘并有效整合用戶信息的處理辦法，改善傳統(tǒng)K-means 聚類算法輸入數(shù)據(jù)單一的問題，提升算法推薦準(zhǔn)確性，在一定程度上緩解了用戶冷啟動問題；②定義一種新的時間衰減函數(shù)改進預(yù)測評分計算公式和BiasSVD 算法的損失函數(shù)，以反映用戶興趣變化對電影評分造成的影響；③將基于多源數(shù)據(jù)的K-means 聚類算法和融合時間衰減函數(shù)的BiasSVD 算法相互結(jié)合，通過實驗選取模型最佳參數(shù)進行比較，分析兩種改進因素各自的作用效果和本文所提出算法的推薦性能。

1 相關(guān)工作

1.1 K-means聚類算法

由于用戶—項目評分矩陣具有高維性和稀疏性特性，首先引入K-means 聚類算法［16］對用戶進行聚類，以此構(gòu)建多個較低維的用戶類簇評分矩陣。如此，一方面可減少系統(tǒng)內(nèi)存消耗，加快后續(xù)矩陣分解計算，提升算法整體運行效率；另一方面，基于相似度較高的用戶類簇進行評分預(yù)測，推薦結(jié)果更準(zhǔn)確。

聚類是將一個數(shù)據(jù)集合劃分為多個由相似數(shù)據(jù)對象組成的子集合（即類簇）的過程，每一個數(shù)據(jù)對象和本類簇的其它數(shù)據(jù)對象相似，但與其它類簇的數(shù)據(jù)對象相異。Kmeans 算法是一種簡單、有效的聚類算法。其中，K 為要劃分的類簇數(shù)目，即質(zhì)心個數(shù)；means 代表類簇中全部數(shù)據(jù)對象的均值，數(shù)據(jù)對象之間的相似度通過彼此的距離來衡量，距離越小表明數(shù)據(jù)對象之間相似度越高，越應(yīng)該被劃分至同一類簇。K-means 算法具體過程如算法1所示。

算法1K-means 聚類算法

1.2 詞頻—逆文檔頻率公式

為評估用戶對某一類型項目的喜愛偏好程度，利用詞頻—逆文檔頻率（Term Frequency-Inverse Document Frequency，TF-IDF）公式［17］對該指標(biāo)進行評估：

其中，t為文檔d中的某一詞條，TFt，d為詞條t在文檔d中出現(xiàn)的頻率，nt，d為詞條t在文檔d中出現(xiàn)的次數(shù)表示文檔d的總詞數(shù)，IDFt為詞條t在文檔總集中的逆文檔頻率，表示詞條t的普遍程度，D為文檔總集中的文檔總個數(shù)，Dt為文檔總集中包含詞條t的文檔個數(shù)，將兩者相乘可得到詞條t的詞頻—逆文檔頻率TF-IDFt，d。

由式（1）可知，當(dāng)某一詞條在某篇文檔出現(xiàn)的頻率越高（即TF值越大），且在文檔總集中被較少的文檔包含（即IDF值越大）時，TF-IDF值越大，說明該詞條越重要。

1.3 SVD算法

基于協(xié)同過濾的推薦算法包含基于用戶和基于物品的傳統(tǒng)協(xié)同過濾推薦算法及基于模型的推薦算法?；谀Ｐ偷耐扑]算法將機器學(xué)習(xí)的思想運用到推薦算法中，主要包括矩陣分解算法、圖模型算法、隱語義模型算法、神經(jīng)網(wǎng)絡(luò)算法等。其中，矩陣分解算法［18］由于易于實現(xiàn)且可擴展性好被普遍使用。

本文采用矩陣分解算法對稀疏的用戶—項目評分矩陣進行降維處理，由此得到用戶和項目的多維隱式特征向量，并利用隨機梯度下降算法產(chǎn)生預(yù)測評分，進而填充稀疏評分矩陣。現(xiàn)有矩陣分解算法有很多種，奇異值分解（SVD）算法［19］最為經(jīng)典，該算法主要將評分矩陣R分解為3個低維矩陣乘積，計算公式定義如下：

其中，Rm×n為評分矩陣為用戶隱式特征正交矩陣的轉(zhuǎn)置，Qk×n為項目隱式特征正交矩陣，Σk×k為奇異值對角矩陣。

然而，SVD 計算過程非常復(fù)雜，且運用SVD 的前提是Rm×n是稠密的，但推薦系統(tǒng)中Rm×n往往非常稀疏。為此，Simon［20］提出一種FunkSVD 算法，將評分矩陣R近似分解為兩個低秩矩陣乘積的形式，計算公式如下：

其中，μ為所有用戶對所有項目評分的均值，bu為用戶評分的偏置，bi為項目被評分的偏置。

2 混合推薦算法

2.1 數(shù)據(jù)預(yù)處理

傳統(tǒng)K-means 聚類算法的輸入通常為用戶—項目評分?jǐn)?shù)據(jù)，但該輸入的基本假設(shè)是推薦系統(tǒng)已經(jīng)運行了一段時間，采集到用戶和項目之間的顯式和隱式反饋數(shù)據(jù)。為進一步提高推薦算法準(zhǔn)確性，緩解推薦系統(tǒng)用戶冷啟動的問題，結(jié)合基于人口統(tǒng)計學(xué)的推薦和基于內(nèi)容的推薦的算法思想，對傳統(tǒng)K-means 聚類算法的輸入數(shù)據(jù)進行改進。

以MovieLens 數(shù)據(jù)集為例，改進后的K-means 聚類算法在用戶—電影評分?jǐn)?shù)據(jù)的基礎(chǔ)上增加了用戶特征數(shù)據(jù)和電影類型特征數(shù)據(jù)。為此，對于輸入的多源數(shù)據(jù)，首先要進行以特征工程為主的數(shù)據(jù)預(yù)處理，具體操作如下：

（1）特征選擇。例如，去除電影的來源網(wǎng)址數(shù)據(jù)。

（2）連續(xù)數(shù)值型特征的歸一化和離散化。例如，將用戶年齡從小到大劃分為7個年齡階段。

（3）非數(shù)值型特征采用One-Hot 編碼。例如，將用戶性別采用［0］、［1］進行編碼；將電影分為19 種類型，按照類型假定的先后順序分別用［0］、［1］進行編碼。

數(shù)據(jù)預(yù)處理完成后，可得到用戶特征矩陣A、用戶—電影評分矩陣R和電影類型特征矩陣B：

其中，um表示第m位用戶，fs表示用戶的第s個特征，表示第m位用戶在第s個特征上的取值，in表示第n部電影，gt表示電影的第t種類型特征表示第n部電影在第t種類型特征上的取值，該值為0 時，代表電影in沒有類型特征gt。由于某些電影包含多種類型，因此表示第m位用戶對第n部電影的評分，該值取[1，5]內(nèi)的整數(shù)。

此外，用戶對電影的喜好除了直接通過用戶對某電影的評分進行衡量，還可通過用戶觀看某類型電影的個數(shù)進行體現(xiàn)。因此，對用戶—電影評分矩陣R進行統(tǒng)計處理可得到用戶—電影觀看矩陣R'，在此基礎(chǔ)上，結(jié)合電影類型特征矩陣B并利用TF -IDF 公式可得到用戶—電影偏好矩陣H。R'和H的形式分別定義如下：

其中，被乘數(shù)的分子表示用戶ux觀看過的電影中含有類型gz的電影總數(shù)，分母表示用戶ux觀看過的電影中各個類型的電影個數(shù)的和，log 中的分子表示所有電影中各個類型的電影個數(shù)之和，分母表示所有電影中含有類型gz的電影總數(shù)。由式（8）可知，當(dāng)某一類型電影在某用戶的觀看列表中出現(xiàn)的頻率越高，且包含該類型的電影在所有電影中占比較小時，對應(yīng)的值越大，說明該用戶更偏愛此類型電影。

最后，合并用戶特征矩陣A，用戶—電影評分矩陣R和用戶—電影偏好矩陣H可得到用戶矩陣W，定義如下：

2.2 基于多源數(shù)據(jù)的K-means聚類算法

傳統(tǒng)的K-means 聚類算法中距離包括歐氏距離及余弦相似度。其中，歐氏距離反映的是向量各維度數(shù)值上的絕對差異性，余弦相似度反映的是向量整體方向上的相對差異性。由于本文算法輸入包含較多的非數(shù)值型特征，例如用戶性別、電影類型等信息，采用余弦相似度更能刻畫兩個用戶特征向量之間的相似程度。余弦相似度定義如下：

多源數(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 聚類算法

2.3 融合時間衰減函數(shù)的BiasSVD算法

一般情況下，用戶對電影的興趣并非一成不變，而隨著時間發(fā)生變化。相較于用戶早期觀影行為，用戶近期觀影行為更能反映用戶當(dāng)前的興趣。

然而，傳統(tǒng)BiasSVD 算法并未考慮時間因素的影響，無法反映用戶興趣的變化。因此，本文引入一種時間衰減函數(shù)對該算法進行優(yōu)化：

其中，τu，i為用戶u對電影i評分時的時間，T為系統(tǒng)當(dāng)前時間，θ為時間衰減參數(shù)，根據(jù)推薦系統(tǒng)中用戶興趣變化的快慢程度自行設(shè)定。如果用戶興趣變化較快，則θ取較大數(shù)值；反之，θ取較小數(shù)值。鑒于用戶觀影興趣變化較慢，本文θ取較小數(shù)值。

其中，μ為所有用戶對所有項目評分的均值，bu為用戶評分的偏置，bi為項目被評分的偏置，β為調(diào)節(jié)參數(shù)，qi，l(τu，i)表示時間衰減函數(shù)φ(τu，i)對電影i的隱式特征l的影響程度?？傻萌诤蠒r間衰減函數(shù)的BiasSVD 的損失函數(shù)為：

其中，Loss前半部分為平方誤差項，后半部分為正則化項，λ為正則化系數(shù)，設(shè)學(xué)習(xí)率為α，分別對pu、qi、bu、bi和β求偏導(dǎo)，根據(jù)隨機梯度下降算法的思想，可得如下遞推公式：

2.4 混合推薦算法

結(jié)合多源數(shù)據(jù)的K-means 聚類算法與融合時間衰減函數(shù)的BiasSVD 算法，可發(fā)揮兩種算法的各自優(yōu)勢?；旌贤扑]算法如算法3所示：

算法3基于多源數(shù)據(jù)聚類和奇異值分解的混合推薦算法

3 實驗結(jié)果與分析

3.1 數(shù)據(jù)集

采用美國明尼蘇達大學(xué)收集整理的MovieLens-100k公開數(shù)據(jù)集進行實驗［22］，該數(shù)據(jù)集的評分?jǐn)?shù)據(jù)整體稀疏度約為93.70%，屬于高維稀疏矩陣。其中，文件u.item 為電影屬性數(shù)據(jù)，主要包含電影ID、電影名稱、發(fā)布日期、電影類型4 個字段；文件u.user 為用戶人口統(tǒng)計學(xué)數(shù)據(jù)，主要包含用戶ID、年齡、性別、職業(yè)4 個字段；文件u.data 為用戶—電影評分?jǐn)?shù)據(jù)，包含用戶ID、電影ID、電影評分、時間戳4個字段。每位用戶至少對20 部電影進行評分，評分取[1，5]內(nèi)的整數(shù)值，評分越高表明用戶對該電影越喜愛。實驗采用5 折交叉驗證法，最終實驗結(jié)果取多次實驗的平均值。

3.2 評測指標(biāo)

采用平均絕對誤差（MAE）評估用戶實際評分與算法預(yù)測評分之間的差異，計算公式如下：

其中，|T|為測試集中的評分總數(shù)分別為用戶u對電影i的實際評分和預(yù)測評分。MAE越小，說明模型預(yù)測評分與用戶實際評分越接近，算法預(yù)測評分準(zhǔn)確度越高。

晨讀時，我發(fā)現(xiàn)教室內(nèi)空位很多，一問才知道，兩人在機房準(zhǔn)備余姚市編程復(fù)賽，三人在書法教室準(zhǔn)備校書法比賽，兩名校男足隊員正在操場訓(xùn)練……一日之計在于晨，見到這種情形，班主任兼語文老師的我是不是該著急了呢？更著急的是家長，眼看再過半年多就要畢業(yè)了，先后好幾位家長都十分擔(dān)心地問我：參加這些活動會不會影響孩子的成績？

采用精確率（Precision）和召回率（Recall）評價算法的推薦性能，計算公式如下：

其中，R(u)表示訓(xùn)練集中為用戶u生成的推薦列表，T(u)表示測試集中用戶u實際的興趣列表。Precision值越高，說明推薦列表中用戶喜歡的電影部數(shù)占推薦列表總數(shù)的比例越高；Recall值越高，說明推薦列表中用戶喜歡的電影部數(shù)占用戶喜歡的電影總數(shù)的比例越高。

采用F_measure對Precision、Recall的值進行調(diào)和，計算公式如下：

3.3 參數(shù)選取

為了使算法取得最佳效果，首先對相關(guān)參數(shù)進行調(diào)節(jié)。具體參數(shù)包括聚類質(zhì)心個數(shù)k、隱式特征維度K、學(xué)習(xí)率α、最大迭代次數(shù)svd_max_iter和推薦列表長度N。由于α和svd_max_iter對推薦算法的性能影響較小，根據(jù)以往經(jīng)驗，先取α=0.02、svd_max_iter=100 并結(jié)合評測指標(biāo)進行控制變量實驗。

為了確定聚類質(zhì)心個數(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ì)心個數(shù)k對平均絕對誤差MAE的影響

由圖2 可見，隨著k取值不斷增大，MAE先遞減后遞增，在k=22 處取得最小值，故選取k=22 作為聚類的質(zhì)心個數(shù)。

由于隱式特征維度K的大小直接影響到重構(gòu)后評分預(yù)測的準(zhǔn)確度，K過小會導(dǎo)致原評分矩陣信息損失嚴(yán)重，最終預(yù)測誤差大；K過大會導(dǎo)致算法的時間和空間復(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 時，MAE隨著K的增大而下降；當(dāng)K≥40 時，MAE的下降趨勢趨于平緩。綜合考慮算法準(zhǔn)確度、時間復(fù)雜度和空間復(fù)雜度等方面的要求，設(shè)定K=40。

為了確定學(xué)習(xí)率α和最大迭代次數(shù)svd_max_iter，實驗采取調(diào)節(jié)學(xué)習(xí)率α，記錄算法收斂時的迭代次數(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ù)最少，算法收斂最快，對應(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]左右時，F(xiàn)_measure最大，當(dāng)N=27，此時綜合推薦性能最佳。

根據(jù)上述實驗結(jié)果表明，本文算法的模型最佳參數(shù)分別為k=22、K=40、α=0.016、svd_max_iter=90、N=27。

3.4 實驗比較

采用MovieLens-100k 公開數(shù)據(jù)集，將本文提出的混合推薦算法（MC-TimeSVD）與只考慮單一改進因素的基于多源數(shù)據(jù)的K-means 聚類協(xié)同過濾推薦算法（MCKMeans）、融合時間衰減函數(shù)的BiasSVD 協(xié)同過濾推薦算法（TimeSVD）、傳統(tǒng)基于K-means 聚類的協(xié)同過濾推薦算法（K-Means）和基于SVD 的協(xié)同過濾推薦算法進行比較。具體結(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ù)據(jù)中充分挖掘并有效整合用戶信息能夠改善用戶聚類效果，緩解用戶冷啟動問題；相較于傳統(tǒng)SVD 推薦算法，TimeSVD 推薦算法在Precision和Recall上分別提升2.9%和3.5%，證實融合新的時間衰減函數(shù)能夠較好反映用戶興趣的變化對電影評分造成的影響；相較于SVD 推薦算法，MC-TimeSVD 混合推薦算法在Precision和Recall上分別提升5.4%和6.8%，證實MC-TimeSVD 混合推薦算法能夠較好結(jié)合兩者算法的各自優(yōu)勢，有效提升了推薦綜合性能。

相較于綜合考慮兩種改進因素的MC-TimeSVD 混合推薦算法，只考慮單一改進因素的MC-KMeans 推薦算法和TimeSVD 推薦算法在Precision和Recall上分別下降3.7%、4.0%和2.5%、3.3%，既證實MC-TimeSVD 混合推薦算法的推薦性能是兩種改進因素共同作用的結(jié)果，又說明MC-KMeans 推薦算法對混合推薦算法性能提升的作用更大。

4 結(jié)語

本文提出基于多源數(shù)據(jù)聚類和奇異值分解的混合推薦算法，以提升算法的推薦性能，緩解用戶冷啟動問題。該算法將用戶屬性數(shù)據(jù)、用戶—電影評分?jǐn)?shù)據(jù)和項目屬性數(shù)據(jù)作為輸入數(shù)據(jù)，較好地緩解了用戶冷啟動問題，并且引入改進的K-means 聚類算法和時間衰減函數(shù)的BiasSVD算法的優(yōu)勢。實驗結(jié)果表明，以上改進方法均提升算法的綜合推薦性能，但僅集中在一個用戶全特征矩陣處理多源數(shù)據(jù)，后續(xù)將從多視圖聚類和模型結(jié)構(gòu)優(yōu)化角度進行研究。