基于多源數據聚類與奇異值分解的混合推薦算法

劉偉友，吳 陳

（江蘇科技大學計算機學院，江蘇鎮江 212100）

0 引言

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

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

由此可見，僅使用單一算法推薦存在明顯的性能瓶頸，目前往往混合使用多種推薦算法解決該問題。例如，魏浩等［12］先對用戶進行聚類得到近鄰用戶集，再取用戶集的平均評分填充稀疏矩陣，最后使用SVD 算法分解重構矩陣產生推薦結果。劉超等［13］利用改進BiasSVD 算法預測評分，對用戶進行聚類并調整預測偏差。Nilashi 等［14］結合主成分分析（Principal Component Analysis，PCA）、自組織映射（Self-Organizing Map，SOM）和期望最大化（Expectation Maximization，EM）技術構建旅游推薦系統。以上混合推薦算法兼顧了數據稀疏性問題和算法準確性要求，但均未解決用戶冷啟動問題［15］，且無法反映用戶興趣變化造成的評分影響。

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

1 相關工作

1.1 K-means聚類算法

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

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

算法1K-means 聚類算法

1.2 詞頻—逆文檔頻率公式

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

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

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

1.3 SVD算法

基于協同過濾的推薦算法包含基于用戶和基于物品的傳統協同過濾推薦算法及基于模型的推薦算法。基于模型的推薦算法將機器學習的思想運用到推薦算法中，主要包括矩陣分解算法、圖模型算法、隱語義模型算法、神經網絡算法等。其中，矩陣分解算法［18］由于易于實現且可擴展性好被普遍使用。

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

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

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

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

2 混合推薦算法

2.1 數據預處理

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

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

（1）特征選擇。例如，去除電影的來源網址數據。

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

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

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

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

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

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

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

2.2 基于多源數據的K-means聚類算法

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

多源數據的K-means 聚類算法如算法2，對應的算法流程圖如圖1所示。

Fig.1 Flow chart of K-means clustering algorithm based on multisource data圖1 基于多源數據的K-means聚類算法流程圖

算法2基于多源數據的K-means 聚類算法

2.3 融合時間衰減函數的BiasSVD算法

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

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

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

其中，μ為所有用戶對所有項目評分的均值，bu為用戶評分的偏置，bi為項目被評分的偏置，β為調節參數，qi，l(τu，i)表示時間衰減函數φ(τu，i)對電影i的隱式特征l的影響程度。可得融合時間衰減函數的BiasSVD 的損失函數為：

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

2.4 混合推薦算法

結合多源數據的K-means 聚類算法與融合時間衰減函數的BiasSVD 算法，可發揮兩種算法的各自優勢。混合推薦算法如算法3所示：

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

3 實驗結果與分析

3.1 數據集

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

3.2 評測指標

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

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

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

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

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

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

3.3 參數選取

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

為了確定聚類質心個數k的最優取值，固定K=5、N=3觀察k的取值變化對MAE的影響，結果如圖2所示。

Fig.2 The influence of different clustering number k on MAE圖2 聚類質心個數k對平均絕對誤差MAE的影響

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

由于隱式特征維度K的大小直接影響到重構后評分預測的準確度，K過小會導致原評分矩陣信息損失嚴重，最終預測誤差大；K過大會導致算法的時間和空間復雜度過高。為此，設定k=22、N=30 評估K對MAE值的影響，結果如圖3所示。

Fig.3 The influence of different implicit feature dimension number K on MAE圖3 隱式特征維度K對平均絕對誤差MAE的影響

由圖3 可見，當K<40 時，MAE隨著K的增大而下降；當K≥40 時，MAE的下降趨勢趨于平緩。綜合考慮算法準確度、時間復雜度和空間復雜度等方面的要求，設定K=40。

為了確定學習率α和最大迭代次數svd_max_iter，實驗采取調節學習率α，記錄算法收斂時的迭代次數Steps和MAE分析α的取值，結果如表1所示。

Table 1 The influence of different learning rate α on iterations number Steps and MAE表1 學習率α對迭代次數Steps和平均絕對誤差MAE的影響

由表1 可知，在0.010～0.031 內，以0.003 遞增調節α的過程中，當α=0.016 時迭代次數最少，算法收斂最快，對應的MAE也相對較小。

在 確 定k=22、K=40、α=0.016、svd_max_iter=90后，研究推薦列表長度N對算法精確率Precision和召回率Recall的影響，并結合F_measure選取最佳N值，結果如圖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則不斷上升。當N∈[25，30]左右時，F_measure最大，當N=27，此時綜合推薦性能最佳。

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

3.4 實驗比較

采用MovieLens-100k 公開數據集，將本文提出的混合推薦算法（MC-TimeSVD）與只考慮單一改進因素的基于多源數據的K-means 聚類協同過濾推薦算法（MCKMeans）、融合時間衰減函數的BiasSVD 協同過濾推薦算法（TimeSVD）、傳統基于K-means 聚類的協同過濾推薦算法（K-Means）和基于SVD 的協同過濾推薦算法進行比較。具體結果如表2所示。

Table 2 The best precision and recall of each algorithm表2 5種算法各自最佳的精確率Precision和召回率Recall（%）

由表2 可知，相較于傳統K-Means 推薦算法，MCKMeans 推薦算法在Precision和Recall分別提升3.4%和3.7%，證實從多源數據中充分挖掘并有效整合用戶信息能夠改善用戶聚類效果，緩解用戶冷啟動問題；相較于傳統SVD 推薦算法，TimeSVD 推薦算法在Precision和Recall上分別提升2.9%和3.5%，證實融合新的時間衰減函數能夠較好反映用戶興趣的變化對電影評分造成的影響；相較于SVD 推薦算法，MC-TimeSVD 混合推薦算法在Precision和Recall上分別提升5.4%和6.8%，證實MC-TimeSVD 混合推薦算法能夠較好結合兩者算法的各自優勢，有效提升了推薦綜合性能。

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

4 結語

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