基于融合GMM聚類與FOA-GRNN模型的推薦算法

李毅鵬，阮葉麗，張杰

?

基于融合GMM聚類與FOA-GRNN模型的推薦算法

李毅鵬，阮葉麗，張杰

（中南財經政法大學信息與安全工程學院，湖北 武漢 430073)

針對傳統基于物品的推薦算法由于數據稀疏性導致的低推薦精度問題，提出了一種融合GMM聚類和FOA-GRNN模型的推薦算法。該算法首先使用高斯混合模型（GMM）方法對物品特征進行聚類；然后根據聚類結果分別構造評分矩陣，并使用Slope One算法填充評分矩陣；最后計算用戶對物品的相似度預測評分作為輸入，通過FOA-GRNN模型輸出最終的評分。基于movielens-2k數據集的實驗結果表明，與其他3種算法相比，該算法能夠更好地處理高稀疏性數據，推薦精度更優，并能夠在一定程度上解決冷啟動問題。

推薦算法；GMM聚類；果繩優化；廣義回歸神經網絡；Slope One算法

1 引言

隨著互聯網技術的發展，人們在線獲取的數據越來越豐富，然而大量無關冗余數據嚴重干擾了人們對有用信息的選擇，這種現象被稱為“信息過載”。因此，推薦系統成為幫助用戶獲取有用信息的必要工具，其原理是基于用戶的興趣偏好、歷史評分、需求、行為等信息產生一個排序序列，將排序靠前的商品或信息推薦給用戶。近年來，越來越多的個性化推薦方法被相繼提出，協同過濾推薦算法由于其推薦過程自動高效，并且僅利用用戶對物品的評分信息而被廣泛使用，成為互聯網時代的新寵。協同過濾推薦算法有2種不同的推薦途徑，分為基于用戶的協同過濾和基于物品的協同過濾。

雖然協同過濾算法由于其簡單、有效和準確性而被廣泛應用，在信息時代節約了用戶獲取信息的時間代價，但是用戶評分數據的稀疏性和冷啟動問題成為制約其推薦精度的主要原因。對此，國外學者率先進行了相關研究，Deshpande等[1]提出SVD奇異值分解法可以對用戶?項目評分矩陣進行降維，通過刪除冗余信息實現降低數據稀疏度的目的。Rendle[2]則從貝葉斯原理出發，使用貝葉斯概率修正用戶對項目的預測評分，降低了算法的預測偏差。Ocepek[3]就冷啟動的問題，在傳統協同過濾算法基礎上加入用戶認知信任信息，提升了推薦精度。國內學者在協同過濾推薦算法的研究上雖起步較晚，但已取得了可觀的研究成果。張鋒等[4]首先將機器學習的思想融入協同過濾算法中，利用BP網絡降低數據稀疏度，取得了不錯的實證效果。詹增榮[5]則通過RBF函數插值法對稀疏數據進行填補，接著采用SVM進行評分預測，使算法克服了數據質量的不足，增加了穩定性。張玉連等[6]另辟蹊徑，提供了一種簡單高效的優化方案。用最小二乘法對Slope One算法進行加權，從而實現對稀疏數據的填充。郭蘭杰等[7]考慮到“朋友關系”可能影響不同用戶對于物品的選擇，故引入用戶社交網絡信息對物品相似度計算和最終預測評分階段的缺失值進行填充，在降低評分誤差的同時提高了分類準確率，但卻增加了相關數據獲取的難度以及算法整體的復雜性。針對傳統協同過濾算法未充分重視用戶反饋信息的問題，張宇等[8]提出了基于正負反饋的支持向量機協同過濾，篩選了用戶較為喜歡的物品進行排序，加快了算法的推薦速度。龐海龍等[9]將真實評分與預測評分的插值作為線性回歸模型的輸入訓練模型，從而產生最終推薦，為緩解數據稀疏性提供了另一種解決方案。與此同時，丁永剛等[10]提出碼本聚類的思想獲取用戶評分風格信息，降低了推薦成本。龔敏等[11]利用-means方法對用戶進行聚類，提高了推薦算法的可擴展性。陶維成等[12]則引入灰色關聯度的聚類方法對物品特征進行聚類，取得了類似的實證效果。楊大鑫等[13]在上述研究的基礎上，利用最小方差對-means算法進行優化后對用戶聚類，對協同過濾算法做了進一步改進。

綜上所述，國內外學者對協同過濾算法的改進大多是從稀疏矩陣的填充以及用戶信息的擴展兩方面提出，對物品特征之間的聯系兼顧較少，或考慮到物品類別，但未對用戶項目評分做進一步優化，并且對用戶信息的擴展增加了數據獲取的難度。因此，本文從物品特征出發，提出了融合高斯混合模型（GMM）聚類和果蠅優化?廣義回歸神經網絡（FOA-GRNN）模型的推薦算法，結合物品特征信息以及廣義回歸神經網絡（GRNN）模型的非線性擬合能力產生推薦。

2 融合GMM聚類和FOA-GRNN模型的推薦算法

基于高斯混合模型聚類算法、果蠅優化算法、廣義回歸神經網絡，本文構建了融合GMM聚類和FOA-GRNN模型的協同過濾算法。整套算法以基于物品的協同過濾算法為核心加以優化，算法構建的基本流程細化如下。

2.1 基于物品特征的GMM聚類

相較于-means等傳統的聚類方法，GMM聚類不用指定類別的個數，將樣本特征假設為服從高斯分布，在大樣本條件下更符合中心極限定理，最終的聚類結果是每個樣本分屬于不同類別的概率，相較于-means聚類更為合理，同時GMM算法的時間復雜度較-means有所減小，降低了算法運行開銷。

2.2 計算物品相似度以及用戶?物品預測評分

2.2.1 結合GMM聚類結果計算物品間相似度

表1 用戶?物品評分矩陣

與傳統協同過濾算法只通過用戶評分矩陣計算物品之間相似度不同，本文提出的算法結合了對物品特征進行GMM聚類的結果，將物品的特征信息深入融合到物品相似度計算中。根據2.1節的假設，所有物品被聚為類，對于每一類中的物品，分別計算其與同屬于一類中的其他物品的相似度，相似度采用常用的皮爾遜相似度度量，即

2.2.2 基于物品相似度預測評分

在相似度計算的基礎上，通過用戶對物品的最相似鄰居的評分值進行相似度加權后得到用戶對物品的評分預測值，計算公式如下。

其中，表示物品的最相似鄰居集合。

2.2.3 Slope One算法填充缺失值

由于用戶評分矩陣的高稀疏性，對式(1)、式(2)的計算有所不便。在此采用Lemire等[14]于2005年提出的一種有效的缺失值填充方法，即Slope One算法[14]，本文在式(1)、式(2)的計算過程中采用Slope One算法對可能的缺失值進行選擇性填充，Slope One算法重復利用用戶?物品評分矩陣中已評分數據，計算相關的未評分數據以改善數據的稀疏性。

2.3 FOA-GRNN模型預測最終評分

用戶?物品評分矩陣中的缺失值由式(2)的計算結果代替，將所有相似度預測評分作為GRNN模型的輸入，以聚類結果為依據，按物品所屬類分別訓練FOA-GRNN神經網絡模型，以FOA-GRNN神經網絡模型的輸出結果作為最終的預測評分。

表2 第類用戶對物品評分信息

2.4 評價指標

本文選用推薦算法常用的2種評價指標來評價算法推薦結果的優劣[15-16]，這2種評價指標分別為平均絕對誤差（MAE）和均方根誤差（RMSE），即

3 實驗分析

3.1 實驗數據集

本文采用的實驗數據集是推薦系統常用的movielens-2k數據集，包含在HetRec2011 Dataset中。該數據集是movielens 10M數據集的擴展，包含更多的電影特征信息。除了基本的“release time”“genre”外，還有“Top Critics Rating”“Top Critics NumReviews”“Top Critics Score”“Audience Rating”等連續型數據，相比movielens 10M數據集更加利于項目聚類算法的開展。該數據集的核心是2 113位用戶對10 197部電影的評分，共855 598個記錄，而每部電影只有84個評分記錄，保證了高稀疏度的數據要求，因此，本文選用該數據集作為融合GMM聚類和FOA-GRNN模型推薦算法的實驗數據集。

3.2 實驗結果分析

對movielens-2k數據集的電影信息進行整理后發現，其可供聚類使用的有效特征數為16個，剔除其中含有的無效記錄后可供研究的電影數目為10 105個，即整個實驗的物品數目為10 105個，用戶數目為2 111個，涵蓋855 598個評分記錄，其中不難發現實驗數據集的評分稀疏度已達到96%。本文所提算法的第一步根據電影特征對10 105部影片進行聚類，由于電影特征數較多，在此先用PCA主成分分析法對電影特征進行降維，并識別出3個主成分，再對主成分進行GMM聚類。GMM聚類能夠自動生成聚類的簇數，并不需要自己設定，最終的聚類結果如圖1所示。

圖1 GMM聚類結果

從圖1中可以看出，GMM聚類根據電影特征信息將10 105部電影聚成9類，各個電影所屬的類別根據EM算法計算出的最終概率而定。聚類結果中各類含有的影片數目大體較為均勻，其中含有電影數目最多的類是第3類，包含2 202部影片，而所含電影數目最少的類別為第9類，僅有39部電影。

根據上述聚類結果，分別對每個類別中的物品計算相似度，再根據每個物品的相似度大小進行排序，構建每個物品的最相似物品鄰居集合，計算過程的缺失值使用Slope One算法選擇性填充，以相似度為基礎計算出的用戶?物品預測評分作為FOA-GRNN神經網絡模型的輸入，得到最終的預測評分信息。其中，FOA算法對GRNN模型平滑因子進行迭代尋優的過程如圖2所示。

圖2 FOA優化GRNN迭代路徑

根據MAE和RMSE這2種推薦算法優劣的評價指標，本文計算了在每一類中訓練出的FOA-GRNN模型的MAE值和RMSE的值，根據文獻[7]，本文將物品的相似度鄰居數設置為30進行對比，每一類的MAE和RMSE值均為5折交叉驗證的平均結果，如圖3所示。

圖3 各個類中的RMSE和MAE值

從圖3可以看出，各個類別的MAE值和RMSE值較為穩定，其中的少許波動一定程度上是由于各類樣本數大小不同引起的，其中，第4類中的用戶?電影評分矩陣的稀疏程度較大，故得到較大的MAE和RMSE，相對正常。總體來看，RMSE值略大于MAE，RMSE和MAE指標均未出現極端值，這也說明本文提出的推薦算法具有較高的泛化能力。

為了進一步比較驗證本文提出的算法與已有的推薦算法性能的優劣，這里分別將新算法與如下3種算法的性能進行對比分析，所用的評價指標依然是MAE和RMSE。

第1種算法為傳統的基于物品的協同過濾算法（UCF），只根據用戶?物品評分矩陣計算物品之間的相似度，進而根據物品的最相似集合計算用戶對物品的預測評分。

第2種算法為采用-means算法對物品聚類，然后采用FOA優化GRNN模型得出最終預測評分的算法，即在本文算法的基礎上，將GMM聚類算法替換為-means算法后得到的算法，以比較-means算法和GMM算法在處理本文問題的表現優劣，記為-FOA-GRNN。

第3種算法為本文算法中的FOA優化GRNN模型替換為傳統的BP神經網絡模型，以預測最終的評分值，以此比較FOA-GRNN模型同BP模型在本文問題上的預測效果，記為GMM-BP。

采用相同的數據集實驗后，4種算法的對比結果如圖4和圖5所示。其中，橫軸代表相似度鄰居數，縱軸則表示誤差MAE和RMSE值。

圖4 4種算法MAE值對比

圖5 4種算法RMSE值對比

由圖4和圖5可以看出，隨著物品相似度鄰居的增加，每種算法的MAE值和RMSE值都有一個先降后升的趨勢，在鄰居數為30時，MAE和RMSE都達到一個最小值。與其他3種已有算法相比較，本文提出的算法無論在MAE還是RMSE上，均小于其他3種已有算法，MAE和RMSE值均有較大幅度的降低，在各個鄰居數下皆是如此。因此，本文提出的新算法較已有的協同過濾算法，有更好的推薦性能，適用范圍更加廣泛。

4 結束語

本文在已有研究的基礎上，提出了一種融合GMM聚類與FOA-GRNN模型的協同過濾算法。該算法以傳統面向物品的協同過濾算法為核心，充分利用物品特征的信息反饋，先通過GMM聚類方法將物品進行聚類，再根據聚類結果計算各個類別的物品之間的相似度，并用Slope One算法對計算過程的確實值進行填充，緩解了數據的稀疏性問題。最后將基于物品相似度鄰居集合計算出的用戶對物品的預測評分作為GRNN模型的輸入，利用FOA算法對GRNN模型的平滑因子進行迭代尋優，從而獲得最終的用戶物品預測評分，得益于GRNN模型多變量輸出功能，可以較為有效地解決評分稀疏性問題。在movielens-2k數據集上的實證分析顯示，改進的算法推薦誤差較小，精度較高，并且較其他3種協同過濾算法有更好的推薦能力和泛化能力。

[1] DESHPANDE M, KARYPIS G. Item-based top-, recommendation algorithms[M]. ACM, 2004.

[2] RENDLE S, FREUDENTHALER C, GANTNER Z, et al. BPR: Bayesian personalized ranking from implicit feedback[M]. AUAI Press, 2009:452-461.

[3] OCEPEK U, RUGELJ J, BOSNI? Z. Improving matrix factorization recommendations for examples in cold start[J]. Expert Systems with Applications, 2015, 42(19):6784-6794.

[4] 張鋒, 常會友. 使用BP神經網絡緩解協同過濾推薦算法的稀疏性問題[J]. 計算機研究與發展, 2006, 43(4):667-672.ZHANG F, CHANG H Y. Employing bp neural networks to alleviate the sparsity issue in colaborative filtering recommendation algorithms[J]. Journal of Computer Research and Development,2006, 43(4):667-672.

[5] 詹增榮, 曾青松. 基于協方差矩陣表示的圖像集匹配[J].湖南師范大學自然科學學報,2015, 38(4):74-79.ZHAN Z R, ZENG Qing-song image set matching based on covariance matrix[J]. Journal of Natural Science of Hunan Normal University, 2015, 38(4): 74-79.

[6] 張玉連, 郇思思, 梁順攀. 融合機器學習的加權Slope One算法[J].小型微型計算機系統, 2016,37(8):1712-1716.ZHANG Y L, HUAN S S, LIANG S P, ?Integrating machine learning into weighted Slope One algorithm[J]. Journal of Chinese Computer Systems, 2016, 37(8): 1712-1716.

[7] 郭蘭杰, 梁吉業, 趙興旺. 融合社交網絡信息的協同過濾推薦算法[J]. 模式識別與人工智能, 2016, 29(3):281-288.GUO L J, LIANG J Y, ZHAO X W. collaborative filtering recommendation algorithm incorporationg social network information[J]. PR&AI, 2016, 29(3): 281-288.

[8] 張宇, 王文劍, 趙勝男. 基于正負反饋的SVM協同過濾Top-推薦算法[J]. 小型微型計算機系統, 2017, 38(5):961-966.ZHANG Y, WANG W J, ZHAO S N. SVM collaborative filtering Top-recommendation algorithm based on positive and negative feedback[J]. Journal of Chinese Computer Systems, 2017, 38(5): 961-966.

[9] 龐海龍, 趙輝, 李萬龍, 等. 融合協同過濾的線性回歸推薦算法[J].計算機應用研究, 2019(5).PANG H L, ZHAO H, LI W L, et al. Linear regression recommendation algorithm with collaborative filtering[J]. Application Research of Computers , 2019(5).

[10] 丁永剛, 李石君, 余偉, 等. 基于碼本聚類和因子分解機的多指標推薦算法[J]. 計算機科學, 2017, 44(10):182-186.DING Y G, LI S J, YU W, et al. Multi-criteria recommendation algorithm based on codebook-clustering and factorization machines[J]. Computer Science. 2017, 44(10): 182-186.

[11] 龔敏, 鄧珍榮, 黃文明. 基于用戶聚類與Slope One填充的協同推薦算法[J]. 計算機工程與應用. 2018, 20(8):102-110.GONG M, DENG Z R, HUANG W M. Collaborative recommendation algorithm based on user clustering and Slope One filling[J]. Computer Engineering and Applications, 2018, 20(8): 102-110.

[12] 陶維成, 黨耀國. 基于灰色關聯聚類的協同過濾推薦算法[J]. 運籌與管理, 2018(1):84-88.TAO W C, DANG Y G. Collaborative filtering recommendation algorithm based on grey incidence clustering[J]. Operations Research and Management Science, 2018(1):84-88.

[13] 楊大鑫, 王榮波, 黃孝喜, 等. 基于最小方差的K-means用戶聚類推薦算法[J]. 計算機技術與發展, 2018(1):104-107.YANG D X, WANG R B, HUANG X X, et al. K-means user clustering recommendation algorithm based on minimum variance[J]. Computer Technology and Development, 2018(1): 104-107.

[14] LEMIRE D, MACLACHLAN A. Slope One Predictors for online: rating-based collaborative filtering[C]//Proc of SIAM Data Mining. 2005: 471-476

[15] BREESE J S, HECKERMAN D, KADIE C. Empirical analysis of predictive algorithm for collaborative filtering[R]. MSR-TR-98-12, Redmond, Microsoft, 1998.

[16] SEHAFER J, FRANKOWSKI D, HERLOCKER J. Collaborative filtering recommender systems[M]. Berlin: Springer. 2007.

Recommendation algorithm based on GMM clustering and FOA-GRNN model

LI Yipeng, RUAN Yeli, ZHANG Jie

School of Information and Safety Engineering, Zhongnan University of Economics and Law, Wuhan 430073, China

Aiming at the problem of low recommendation accuracy caused by sparse data in traditional item-based recommendation algorithm, a recommendation algorithm based on GMM clustering and FOA-GRNN model is proposed. The algorithm firstly uses Gaussian mixture model (GMM) to cluster the item features, then constructs the score matrix according to the clustering results, and fills the score matrix with slope one algorithm. Finally, the user's score based on similarity prediction is taken as input, and the final score is output through FOA-GRNN model. Experimental results based on movielens-2k dataset show that the proposed algorithm can deal with highly sparse data better and has better recommendation accuracy than the other three algorithms.

recommendation algorithm, GMM clustering, FOA, GRNN, Slope One algorithm

TP311

A

10.11959/j.issn.2096-109x.2018097

2018-11-10；

2018-11-29

阮葉麗，yeli_ruan@126.com

校級中央高校基本科研基金資助項目；教育教學改革基金資助項目（No.2018-9）

The Fundamental Research Funds for the Central Universities,The Education and Teaching Reform Fund (No.2018-9)

李毅鵬（1980-），男，湖北武漢人，中南財經政法大學副教授，主要研究方向為管理信息系統、DSS、Mobile電子商務。

阮葉麗（1994-），女，貴州仁懷人，中南財經政法大學碩士生，主要研究方向為推薦系統。

張杰（1995-），男，安徽六安人，中南財經政法大學碩士生，主要研究方向為金融統計。